Merge "Fix SsaDeadPhiElimination in the presence of dependent phis."
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index cb3dd0f..bb699e4 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -501,6 +501,7 @@
void SetBlock(HBasicBlock* block) { block_ = block; }
bool IsInBlock() const { return block_ != nullptr; }
bool IsInLoop() const { return block_->IsInLoop(); }
+ bool IsLoopHeaderPhi() { return IsPhi() && block_->IsLoopHeader(); }
virtual size_t InputCount() const = 0;
virtual HInstruction* InputAt(size_t i) const = 0;
diff --git a/compiler/optimizing/register_allocator_test.cc b/compiler/optimizing/register_allocator_test.cc
index a7283ab..bafe577 100644
--- a/compiler/optimizing/register_allocator_test.cc
+++ b/compiler/optimizing/register_allocator_test.cc
@@ -22,6 +22,7 @@
#include "optimizing_unit_test.h"
#include "register_allocator.h"
#include "ssa_liveness_analysis.h"
+#include "ssa_phi_elimination.h"
#include "utils/arena_allocator.h"
#include "gtest/gtest.h"
@@ -356,4 +357,38 @@
ASSERT_EQ(new_interval->FirstRegisterUse(), last_add->GetLifetimePosition() + 1);
}
+TEST(RegisterAllocatorTest, DeadPhi) {
+ /* Test for a dead loop phi taking as back-edge input a phi that also has
+ * this loop phi as input. Walking backwards in SsaDeadPhiElimination
+ * does not solve the problem because the loop phi will be visited last.
+ *
+ * Test the following snippet:
+ * int a = 0
+ * do {
+ * if (true) {
+ * a = 2;
+ * }
+ * } while (true);
+ */
+
+ const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
+ Instruction::CONST_4 | 0 | 0,
+ Instruction::CONST_4 | 1 << 8 | 0,
+ Instruction::IF_NE | 1 << 8 | 1 << 12, 3,
+ Instruction::CONST_4 | 2 << 12 | 0 << 8,
+ Instruction::GOTO | 0xFD00,
+ Instruction::RETURN_VOID);
+
+ ArenaPool pool;
+ ArenaAllocator allocator(&pool);
+ HGraph* graph = BuildSSAGraph(data, &allocator);
+ SsaDeadPhiElimination(graph).Run();
+ CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, kX86);
+ SsaLivenessAnalysis liveness(*graph, codegen);
+ liveness.Analyze();
+ RegisterAllocator register_allocator(&allocator, codegen, liveness);
+ register_allocator.AllocateRegisters();
+ ASSERT_TRUE(register_allocator.Validate(false));
+}
+
} // namespace art
diff --git a/compiler/optimizing/ssa_phi_elimination.cc b/compiler/optimizing/ssa_phi_elimination.cc
index 13fa03f..a079954 100644
--- a/compiler/optimizing/ssa_phi_elimination.cc
+++ b/compiler/optimizing/ssa_phi_elimination.cc
@@ -53,8 +53,9 @@
}
}
- // Remove phis that are not live. Visit in post order to ensure
- // we only remove phis with no users (dead phis might use dead phis).
+ // Remove phis that are not live. Visit in post order so that phis
+ // that are not inputs of loop phis can be removed when they have
+ // no users left (dead phis might use dead phis).
for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
HBasicBlock* block = it.Current();
HInstruction* current = block->GetFirstPhi();
@@ -62,6 +63,17 @@
while (current != nullptr) {
next = current->GetNext();
if (current->AsPhi()->IsDead()) {
+ if (current->HasUses()) {
+ for (HUseIterator<HInstruction> it(current->GetUses()); !it.Done(); it.Advance()) {
+ HUseListNode<HInstruction>* user_node = it.Current();
+ HInstruction* user = user_node->GetUser();
+ DCHECK(user->IsLoopHeaderPhi());
+ DCHECK(user->AsPhi()->IsDead());
+ // Just put itself as an input. The phi will be removed in this loop anyway.
+ user->SetRawInputAt(user_node->GetIndex(), user);
+ current->RemoveUser(user, user_node->GetIndex());
+ }
+ }
block->RemovePhi(current->AsPhi());
}
current = next;
