From 15bd22849ee6a1ffb3fb3630f686c2870bdf1bbc Mon Sep 17 00:00:00 2001
From: Nicolas Geoffray <ngeoffray@google.com>
Date: Tue, 5 Jan 2016 15:55:41 +0000
Subject: 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
---
 compiler/optimizing/graph_checker.cc | 52 ++++++++++++++++++++++--------------
 1 file changed, 32 insertions(+), 20 deletions(-)

(limited to 'compiler/optimizing/graph_checker.cc')

diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index 6d0bdbe19b..d60f3e31a5 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -391,6 +391,15 @@ void SSAChecker::VisitBasicBlock(HBasicBlock* block) {
     }
   }
 
+  // Ensure dominated blocks have `block` as the dominator.
+  for (HBasicBlock* dominated : block->GetDominatedBlocks()) {
+    if (dominated->GetDominator() != block) {
+      AddError(StringPrintf("Block %d should be the dominator of %d.",
+                            block->GetBlockId(),
+                            dominated->GetBlockId()));
+    }
+  }
+
   // Ensure there is no critical edge (i.e., an edge connecting a
   // block with multiple successors to a block with multiple
   // predecessors). Exceptional edges are synthesized and hence
@@ -467,13 +476,7 @@ void SSAChecker::CheckLoop(HBasicBlock* loop_header) {
   int id = loop_header->GetBlockId();
   HLoopInformation* loop_information = loop_header->GetLoopInformation();
 
-  // Ensure the pre-header block is first in the list of predecessors of a loop
-  // header and that the header block is its only successor.
-  if (!loop_header->IsLoopPreHeaderFirstPredecessor()) {
-    AddError(StringPrintf(
-        "Loop pre-header is not the first predecessor of the loop header %d.",
-        id));
-  } else if (loop_information->GetPreHeader()->GetSuccessors().size() != 1) {
+  if (loop_information->GetPreHeader()->GetSuccessors().size() != 1) {
     AddError(StringPrintf(
         "Loop pre-header %d of loop defined by header %d has %zu successors.",
         loop_information->GetPreHeader()->GetBlockId(),
@@ -532,30 +535,39 @@ void SSAChecker::CheckLoop(HBasicBlock* loop_header) {
     }
   }
 
-  // Ensure all blocks in the loop are live and dominated by the loop header.
+  // If this is a nested loop, ensure the outer loops contain a superset of the blocks.
+  for (HLoopInformationOutwardIterator it(*loop_header); !it.Done(); it.Advance()) {
+    HLoopInformation* outer_info = it.Current();
+    if (!loop_blocks.IsSubsetOf(&outer_info->GetBlocks())) {
+      AddError(StringPrintf("Blocks of loop defined by header %d are not a subset of blocks of "
+                            "an outer loop defined by header %d.",
+                            id,
+                            outer_info->GetHeader()->GetBlockId()));
+    }
+  }
+
+  // Ensure the pre-header block is first in the list of predecessors of a loop
+  // header and that the header block is its only successor.
+  if (!loop_header->IsLoopPreHeaderFirstPredecessor()) {
+    AddError(StringPrintf(
+        "Loop pre-header is not the first predecessor of the loop header %d.",
+        id));
+  }
+
+  // Ensure all blocks in the loop are live and dominated by the loop header in
+  // the case of natural loops.
   for (uint32_t i : loop_blocks.Indexes()) {
     HBasicBlock* loop_block = GetGraph()->GetBlocks()[i];
     if (loop_block == nullptr) {
       AddError(StringPrintf("Loop defined by header %d contains a previously removed block %d.",
                             id,
                             i));
-    } else if (!loop_header->Dominates(loop_block)) {
+    } else if (!loop_information->IsIrreducible() && !loop_header->Dominates(loop_block)) {
       AddError(StringPrintf("Loop block %d not dominated by loop header %d.",
                             i,
                             id));
     }
   }
-
-  // If this is a nested loop, ensure the outer loops contain a superset of the blocks.
-  for (HLoopInformationOutwardIterator it(*loop_header); !it.Done(); it.Advance()) {
-    HLoopInformation* outer_info = it.Current();
-    if (!loop_blocks.IsSubsetOf(&outer_info->GetBlocks())) {
-      AddError(StringPrintf("Blocks of loop defined by header %d are not a subset of blocks of "
-                            "an outer loop defined by header %d.",
-                            id,
-                            outer_info->GetHeader()->GetBlockId()));
-    }
-  }
 }
 
 void SSAChecker::VisitInstruction(HInstruction* instruction) {
-- 
cgit v1.2.3-59-g8ed1b