Add loop recognition and CFG simplifications in new compiler.

We do three simplifications:
- Split critical edges, for code generation from SSA (new).
- Ensure one back edge per loop, to simplify loop recognition (new).
- Ensure only one pre header for a loop, to simplify SSA creation (existing).

Change-Id: I9bfccd4b236a00486a261078627b091c8a68be33

1 files changed, 163 insertions, 46 deletions

diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index d153bf7..cf2d1ee 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -31,11 +31,11 @@ void HGraph::FindBackEdges(ArenaBitVector* visited) {
 }
 
 void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) const {
-  for (size_t i = 0; i < blocks_.Size(); i++) {
+  for (size_t i = 0; i < blocks_.Size(); ++i) {
     if (!visited.IsBitSet(i)) {
       HBasicBlock* block = blocks_.Get(i);
-      for (size_t j = 0; j < block->GetSuccessors()->Size(); j++) {
-        block->GetSuccessors()->Get(j)->RemovePredecessor(block, false);
+      for (size_t j = 0; j < block->GetSuccessors().Size(); ++j) {
+        block->GetSuccessors().Get(j)->RemovePredecessor(block, false);
       }
       for (HInstructionIterator it(*block->GetPhis()); !it.Done(); it.Advance()) {
         block->RemovePhi(it.Current()->AsPhi());
@@ -55,15 +55,14 @@ void HGraph::VisitBlockForBackEdges(HBasicBlock* block,
 
   visited->SetBit(id);
   visiting->SetBit(id);
-  for (size_t i = 0; i < block->GetSuccessors()->Size(); i++) {
-    HBasicBlock* successor = block->GetSuccessors()->Get(i);
+  for (size_t i = 0; i < block->GetSuccessors().Size(); i++) {
+    HBasicBlock* successor = block->GetSuccessors().Get(i);
     if (visiting->IsBitSet(successor->GetBlockId())) {
       successor->AddBackEdge(block);
     } else {
       VisitBlockForBackEdges(successor, visited, visiting);
     }
   }
-  post_order_.Add(block);
   visiting->ClearBit(id);
 }
 
@@ -78,13 +77,18 @@ void HGraph::BuildDominatorTree() {
   //     predecessors list of live blocks.
   RemoveDeadBlocks(visited);
 
-  // (3) Compute the immediate dominator of each block. We visit
+  // (3) Simplify the CFG now, so that we don't need to recompute
+  //     dominators and the reverse post order.
+  SimplifyCFG();
+
+  // (4) Compute the immediate dominator of each block. We visit
   //     the successors of a block only when all its forward branches
   //     have been processed.
   GrowableArray<size_t> visits(arena_, blocks_.Size());
   visits.SetSize(blocks_.Size());
-  for (size_t i = 0; i < entry_block_->GetSuccessors()->Size(); i++) {
-    VisitBlockForDominatorTree(entry_block_->GetSuccessors()->Get(i), entry_block_, &visits);
+  reverse_post_order_.Add(entry_block_);
+  for (size_t i = 0; i < entry_block_->GetSuccessors().Size(); i++) {
+    VisitBlockForDominatorTree(entry_block_->GetSuccessors().Get(i), entry_block_, &visits);
   }
 }
 
@@ -119,59 +123,172 @@ void HGraph::VisitBlockForDominatorTree(HBasicBlock* block,
   // Once all the forward edges have been visited, we know the immediate
   // dominator of the block. We can then start visiting its successors.
   if (visits->Get(block->GetBlockId()) ==
-      block->GetPredecessors()->Size() - block->NumberOfBackEdges()) {
-    for (size_t i = 0; i < block->GetSuccessors()->Size(); i++) {
-      VisitBlockForDominatorTree(block->GetSuccessors()->Get(i), block, visits);
+      block->GetPredecessors().Size() - block->NumberOfBackEdges()) {
+    reverse_post_order_.Add(block);
+    for (size_t i = 0; i < block->GetSuccessors().Size(); i++) {
+      VisitBlockForDominatorTree(block->GetSuccessors().Get(i), block, visits);
     }
   }
 }
 
 void HGraph::TransformToSSA() {
-  DCHECK(!post_order_.IsEmpty());
-  SimplifyCFG();
+  DCHECK(!reverse_post_order_.IsEmpty());
   SsaBuilder ssa_builder(this);
   ssa_builder.BuildSsa();
 }
 
+void HGraph::SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor) {
+  // Insert a new node between `block` and `successor` to split the
+  // critical edge.
+  HBasicBlock* new_block = new (arena_) HBasicBlock(this);
+  AddBlock(new_block);
+  new_block->AddInstruction(new (arena_) HGoto());
+  block->RemoveSuccessor(successor);
+  block->AddSuccessor(new_block);
+  new_block->AddSuccessor(successor);
+  if (successor->IsLoopHeader()) {
+    // If we split at a back edge boundary, make the new block the back edge.
+    HLoopInformation* info = successor->GetLoopInformation();
+    if (info->IsBackEdge(block)) {
+      info->RemoveBackEdge(block);
+      info->AddBackEdge(new_block);
+    }
+  }
+}
+
+void HGraph::SimplifyLoop(HBasicBlock* header) {
+  HLoopInformation* info = header->GetLoopInformation();
+
+  // If there are more than one back edge, make them branch to the same block that
+  // will become the only back edge. This simplifies finding natural loops in the
+  // graph.
+  if (info->NumberOfBackEdges() > 1) {
+    HBasicBlock* new_back_edge = new (arena_) HBasicBlock(this);
+    AddBlock(new_back_edge);
+    new_back_edge->AddInstruction(new (arena_) HGoto());
+    for (size_t pred = 0, e = info->GetBackEdges().Size(); pred < e; ++pred) {
+      HBasicBlock* back_edge = info->GetBackEdges().Get(pred);
+      header->RemovePredecessor(back_edge);
+      back_edge->AddSuccessor(new_back_edge);
+    }
+    info->ClearBackEdges();
+    info->AddBackEdge(new_back_edge);
+    new_back_edge->AddSuccessor(header);
+  }
+
+  // Make sure the loop has only one pre header. This simplifies SSA building by having
+  // to just look at the pre header to know which locals are initialized at entry of the
+  // loop.
+  size_t number_of_incomings = header->GetPredecessors().Size() - info->NumberOfBackEdges();
+  if (number_of_incomings != 1) {
+    HBasicBlock* pre_header = new (arena_) HBasicBlock(this);
+    AddBlock(pre_header);
+    pre_header->AddInstruction(new (arena_) HGoto());
+
+    ArenaBitVector back_edges(arena_, GetBlocks().Size(), false);
+    HBasicBlock* back_edge = info->GetBackEdges().Get(0);
+    for (size_t pred = 0; pred < header->GetPredecessors().Size(); ++pred) {
+      HBasicBlock* predecessor = header->GetPredecessors().Get(pred);
+      if (predecessor != back_edge) {
+        header->RemovePredecessor(predecessor);
+        pred--;
+        predecessor->AddSuccessor(pre_header);
+      }
+    }
+    pre_header->AddSuccessor(header);
+  }
+}
+
 void HGraph::SimplifyCFG() {
-  for (size_t i = post_order_.Size(); i > 0; --i) {
-    HBasicBlock* current = post_order_.Get(i - 1);
-    if (current->IsLoopHeader()) {
-      // Make sure the loop has only one pre header. This simplifies SSA building by having
-      // to just look at the pre header to know which locals are initialized at entry of the
-      // loop.
-      HLoopInformation* info = current->GetLoopInformation();
-      size_t number_of_incomings = current->GetPredecessors()->Size() - info->NumberOfBackEdges();
-      if (number_of_incomings != 1) {
-        HBasicBlock* pre_header = new (arena_) HBasicBlock(this);
-        AddBlock(pre_header);
-        pre_header->AddInstruction(new (arena_) HGoto());
-        pre_header->SetDominator(current->GetDominator());
-        current->SetDominator(pre_header);
-        post_order_.InsertAt(i, pre_header);
-
-        ArenaBitVector back_edges(arena_, GetBlocks().Size(), false);
-        for (size_t pred = 0; pred < info->GetBackEdges()->Size(); pred++) {
-          back_edges.SetBit(info->GetBackEdges()->Get(pred)->GetBlockId());
+  // Simplify the CFG for future analysis, and code generation:
+  // (1): Split critical edges.
+  // (2): Simplify loops by having only one back edge, and one preheader.
+  for (size_t i = 0; i < blocks_.Size(); ++i) {
+    HBasicBlock* block = blocks_.Get(i);
+    if (block->GetSuccessors().Size() > 1) {
+      for (size_t j = 0; j < block->GetSuccessors().Size(); ++j) {
+        HBasicBlock* successor = block->GetSuccessors().Get(j);
+        if (successor->GetPredecessors().Size() > 1) {
+          SplitCriticalEdge(block, successor);
+          --j;
         }
-        for (size_t pred = 0; pred < current->GetPredecessors()->Size(); pred++) {
-          HBasicBlock* predecessor = current->GetPredecessors()->Get(pred);
-          if (!back_edges.IsBitSet(predecessor->GetBlockId())) {
-            current->RemovePredecessor(predecessor);
-            pred--;
-            predecessor->AddSuccessor(pre_header);
-          }
-        }
-        pre_header->AddSuccessor(current);
       }
-      info->SetPreHeader(current->GetDominator());
     }
+    if (block->IsLoopHeader()) {
+      SimplifyLoop(block);
+    }
+  }
+}
+
+bool HGraph::FindNaturalLoops() const {
+  for (size_t i = 0; i < blocks_.Size(); ++i) {
+    HBasicBlock* block = blocks_.Get(i);
+    if (block->IsLoopHeader()) {
+      HLoopInformation* info = block->GetLoopInformation();
+      if (!info->Populate()) {
+        // Abort if the loop is non natural. We currently bailout in such cases.
+        return false;
+      }
+    }
+  }
+  return true;
+}
+
+void HLoopInformation::PopulateRecursive(HBasicBlock* block) {
+  if (blocks_.IsBitSet(block->GetBlockId())) {
+    return;
+  }
+
+  blocks_.SetBit(block->GetBlockId());
+  block->SetInLoop(this);
+  for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) {
+    PopulateRecursive(block->GetPredecessors().Get(i));
+  }
+}
+
+bool HLoopInformation::Populate() {
+  DCHECK_EQ(GetBackEdges().Size(), 1u);
+  HBasicBlock* back_edge = GetBackEdges().Get(0);
+  DCHECK(back_edge->GetDominator() != nullptr);
+  if (!header_->Dominates(back_edge)) {
+    // This loop is not natural. Do not bother going further.
+    return false;
   }
+
+  // Populate this loop: starting with the back edge, recursively add predecessors
+  // that are not already part of that loop. Set the header as part of the loop
+  // to end the recursion.
+  // This is a recursive implementation of the algorithm described in
+  // "Advanced Compiler Design & Implementation" (Muchnick) p192.
+  blocks_.SetBit(header_->GetBlockId());
+  PopulateRecursive(back_edge);
+  return true;
+}
+
+HBasicBlock* HLoopInformation::GetPreHeader() const {
+  DCHECK_EQ(header_->GetPredecessors().Size(), 2u);
+  return header_->GetDominator();
+}
+
+bool HLoopInformation::Contains(const HBasicBlock& block) const {
+  return blocks_.IsBitSet(block.GetBlockId());
 }
 
-void HLoopInformation::SetPreHeader(HBasicBlock* block) {
-  DCHECK_EQ(header_->GetDominator(), block);
-  pre_header_ = block;
+bool HLoopInformation::IsIn(const HLoopInformation& other) const {
+  return other.blocks_.IsBitSet(header_->GetBlockId());
+}
+
+bool HBasicBlock::Dominates(HBasicBlock* other) const {
+  // Walk up the dominator tree from `other`, to find out if `this`
+  // is an ancestor.
+  HBasicBlock* current = other;
+  while (current != nullptr) {
+    if (current == this) {
+      return true;
+    }
+    current = current->GetDominator();
+  }
+  return false;
 }
 
 static void Add(HInstructionList* instruction_list,