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

1 files changed, 11 insertions, 0 deletions

diff --git a/compiler/optimizing/ssa_phi_elimination.cc b/compiler/optimizing/ssa_phi_elimination.cc
index 2eef307295..6816b6a028 100644
--- a/compiler/optimizing/ssa_phi_elimination.cc
+++ b/compiler/optimizing/ssa_phi_elimination.cc
@@ -154,6 +154,7 @@ void SsaRedundantPhiElimination::Run() {
     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 @@ void SsaRedundantPhiElimination::Run() {
               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 @@ void SsaRedundantPhiElimination::Run() {
       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