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
diff --git a/compiler/optimizing/ssa_phi_elimination.cc b/compiler/optimizing/ssa_phi_elimination.cc
index 917341a..a9f04cd 100644
--- a/compiler/optimizing/ssa_phi_elimination.cc
+++ b/compiler/optimizing/ssa_phi_elimination.cc
@@ -98,7 +98,8 @@
}
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 @@
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 2ddcbce..710e849 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)