ART: Revisit users in phi elimination

SSA phi elimination visits phis in post order so that loop phis are
visited after their inputs. This prevents elimination of phis with
other phi inputs, exacerbated by the fact that the SSA builder does
create catch phis even if all inputs are the same (unlike with normal
phis). This patch revisits phi users of eliminated phis until no more
phis can be removed.

Change-Id: I403614dd46a8e6f0a5b9dd9e8ddc8832617521eb

2 files changed, 44 insertions, 13 deletions

diff --git a/compiler/optimizing/ssa_phi_elimination.cc b/compiler/optimizing/ssa_phi_elimination.cc
index 917341a1e7..a9f04cd201 100644
--- a/compiler/optimizing/ssa_phi_elimination.cc
+++ b/compiler/optimizing/ssa_phi_elimination.cc
@@ -98,7 +98,8 @@ void SsaDeadPhiElimination::EliminateDeadPhis() {
 }
 
 void SsaRedundantPhiElimination::Run() {
-  // Add all phis in the worklist.
+  // Add all phis in the worklist. Order does not matter for correctness, and
+  // neither will necessarily converge faster.
   for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
     HBasicBlock* block = it.Current();
     for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) {
@@ -148,18 +149,16 @@ void SsaRedundantPhiElimination::Run() {
       continue;
     }
 
-    if (phi->IsInLoop()) {
-      // Because we're updating the users of this phi, we may have new
-      // phis candidate for elimination if this phi is in a loop. Add phis that
-      // used this phi to the worklist.
-      for (HUseIterator<HInstruction*> it(phi->GetUses()); !it.Done(); it.Advance()) {
-        HUseListNode<HInstruction*>* current = it.Current();
-        HInstruction* user = current->GetUser();
-        if (user->IsPhi()) {
-          worklist_.Add(user->AsPhi());
-        }
+    // Because we're updating the users of this phi, we may have new candidates
+    // for elimination. Add phis that use this phi to the worklist.
+    for (HUseIterator<HInstruction*> it(phi->GetUses()); !it.Done(); it.Advance()) {
+      HUseListNode<HInstruction*>* current = it.Current();
+      HInstruction* user = current->GetUser();
+      if (user->IsPhi()) {
+        worklist_.Add(user->AsPhi());
       }
     }
+
     phi->ReplaceWith(candidate);
     phi->GetBlock()->RemovePhi(phi);
   }
diff --git a/test/510-checker-try-catch/smali/SsaBuilder.smali b/test/510-checker-try-catch/smali/SsaBuilder.smali
index 2ddcbced9c..710e849c45 100644
--- a/test/510-checker-try-catch/smali/SsaBuilder.smali
+++ b/test/510-checker-try-catch/smali/SsaBuilder.smali
@@ -124,7 +124,7 @@
 # Tests that phi elimination does not remove catch phis where the value does
 # not dominate the phi.
 
-## CHECK-START: int SsaBuilder.testPhiElimination(int, int) ssa_builder (after)
+## CHECK-START: int SsaBuilder.testPhiElimination_Domination(int, int) ssa_builder (after)
 ## CHECK-DAG:     <<P0:i\d+>>   ParameterValue
 ## CHECK-DAG:     <<P1:i\d+>>   ParameterValue
 ## CHECK-DAG:     <<Cst5:i\d+>> IntConstant 5
@@ -140,7 +140,7 @@
 ## CHECK-DAG:     <<Phi2:i\d+>> Phi [<<Cst5>>,<<Add2>>] reg:0 is_catch_phi:false
 ## CHECK-DAG:                   Return [<<Phi2>>]
 
-.method public static testPhiElimination(II)I
+.method public static testPhiElimination_Domination(II)I
     .registers 4
 
     :try_start
@@ -163,6 +163,38 @@
     goto :return
 .end method
 
+# Tests that phi elimination loops until no more phis can be removed.
+
+## CHECK-START: int SsaBuilder.testPhiElimination_Dependencies(int, int, int) ssa_builder (after)
+## CHECK-NOT:     Phi
+
+.method public static testPhiElimination_Dependencies(III)I
+    .registers 4
+
+    # This constant reaches Return via the normal control-flow path and both
+    # exceptional paths. Since v0 is never changed, there should be no phis.
+    const v0, 5
+
+    :try_start
+    div-int/2addr p0, p1
+    div-int/2addr p0, p2
+    :try_end
+    .catch Ljava/lang/ArithmeticException; {:try_start .. :try_end} :catch_arith
+    .catchall {:try_start .. :try_end} :catch_all
+
+    :return
+    # Phi [v0, CatchPhi1, CatchPhi2]
+    return v0
+
+    :catch_arith
+    # CatchPhi1 [v0, v0]
+    goto :return
+
+    :catch_all
+    # CatchPhi2 [v0, v0]
+    goto :return
+.end method
+
 # Tests that dead catch blocks are removed.
 
 ## CHECK-START: int SsaBuilder.testDeadCatchBlock(int, int, int) ssa_builder (before)