Implement irreducible loop support in optimizing.
So we don't fallback to the interpreter in the presence of
irreducible loops.
Implications:
- A loop pre-header does not necessarily dominate a loop header.
- Non-constant redundant phis will be kept in loop headers, to
satisfy our linear scan register allocation algorithm.
- while-graph optimizations, such as gvn, licm, lse, and dce
need to know when they are dealing with irreducible loops.
Change-Id: I2cea8934ce0b40162d215353497c7f77d6c9137e
diff --git a/compiler/optimizing/ssa_phi_elimination.cc b/compiler/optimizing/ssa_phi_elimination.cc
index 2eef307..6816b6a 100644
--- a/compiler/optimizing/ssa_phi_elimination.cc
+++ b/compiler/optimizing/ssa_phi_elimination.cc
@@ -154,6 +154,7 @@
cycle_worklist.push_back(phi);
visited_phis_in_cycle.insert(phi->GetId());
bool catch_phi_in_cycle = phi->IsCatchPhi();
+ bool irreducible_loop_phi_in_cycle = phi->IsIrreducibleLoopHeaderPhi();
// First do a simple loop over inputs and check if they are all the same.
for (size_t j = 0; j < phi->InputCount(); ++j) {
@@ -187,6 +188,7 @@
cycle_worklist.push_back(input->AsPhi());
visited_phis_in_cycle.insert(input->GetId());
catch_phi_in_cycle |= input->AsPhi()->IsCatchPhi();
+ irreducible_loop_phi_in_cycle |= input->IsIrreducibleLoopHeaderPhi();
} else {
// Already visited, nothing to do.
}
@@ -206,6 +208,15 @@
continue;
}
+ if (irreducible_loop_phi_in_cycle && !candidate->IsConstant()) {
+ // For irreducible loops, we need to keep the phis to satisfy our linear scan
+ // algorithm.
+ // There is one exception for constants, as the type propagation requires redundant
+ // cyclic phis of a constant to be removed. This is ok for the linear scan as it
+ // has to deal with constants anyway, and they can trivially be rematerialized.
+ continue;
+ }
+
for (HPhi* current : cycle_worklist) {
// The candidate may not dominate a phi in a catch block: there may be non-throwing
// instructions at the beginning of a try range, that may be the first input of