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, 16 insertions, 0 deletions

diff --git a/compiler/optimizing/licm.cc b/compiler/optimizing/licm.cc
index 02befc011a..a6b4078f46 100644
--- a/compiler/optimizing/licm.cc
+++ b/compiler/optimizing/licm.cc
@@ -94,6 +94,16 @@ void LICM::Run() {
     SideEffects loop_effects = side_effects_.GetLoopEffects(block);
     HBasicBlock* pre_header = loop_info->GetPreHeader();
 
+    bool contains_irreducible_loop = false;
+    if (graph_->HasIrreducibleLoops()) {
+      for (HBlocksInLoopIterator it_loop(*loop_info); !it_loop.Done(); it_loop.Advance()) {
+        if (it_loop.Current()->GetLoopInformation()->IsIrreducible()) {
+          contains_irreducible_loop = true;
+          break;
+        }
+      }
+    }
+
     for (HBlocksInLoopIterator it_loop(*loop_info); !it_loop.Done(); it_loop.Advance()) {
       HBasicBlock* inner = it_loop.Current();
       DCHECK(inner->IsInLoop());
@@ -104,6 +114,12 @@ void LICM::Run() {
       }
       visited.SetBit(inner->GetBlockId());
 
+      if (contains_irreducible_loop) {
+        // We cannot licm in an irreducible loop, or in a natural loop containing an
+        // irreducible loop.
+        continue;
+      }
+
       // We can move an instruction that can throw only if it is the first
       // throwing instruction in the loop. Note that the first potentially
       // throwing instruction encountered that is not hoisted stops this