From 3ac17fcce8773388512ce72cb491b202872ca1c1 Mon Sep 17 00:00:00 2001
From: Nicolas Geoffray <ngeoffray@google.com>
Date: Wed, 6 Aug 2014 23:02:54 +0100
Subject: [PATCH] Fix SsaDeadPhiElimination in the presence of dependent phis.

This fixes the problem of having a dead loop phi taking as back-edge
input a phi that also has this loop phi as input. Walking backwards
does not solve the problem because the loop phi will be visited last.

Most of the time, dex removes dead locals like this.

Change-Id: I797198cf9c15f8faa6585cca157810e23aaa4940
---
 compiler/optimizing/nodes.h                    |  1 +
 compiler/optimizing/register_allocator_test.cc | 35 ++++++++++++++++++++++++++
 compiler/optimizing/ssa_phi_elimination.cc     | 16 ++++++++++--
 3 files changed, 50 insertions(+), 2 deletions(-)

diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index cb3dd0f69..bb699e47c 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -501,6 +501,7 @@ class HInstruction : public ArenaObject {
   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 a7283ab32..bafe577f9 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 @@ TEST(RegisterAllocatorTest, FirstRegisterUse) {
   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 13fa03f9a..a07995416 100644
--- a/compiler/optimizing/ssa_phi_elimination.cc
+++ b/compiler/optimizing/ssa_phi_elimination.cc
@@ -53,8 +53,9 @@ void SsaDeadPhiElimination::Run() {
     }
   }
 
-  // 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 @@ void SsaDeadPhiElimination::Run() {
     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;
-- 
2.11.0