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

1 files changed, 10 insertions, 11 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);
   }