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);
}