Merge "Implement irreducible loop support in optimizing."

1 files changed, 111 insertions, 74 deletions

diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 8de9700250..b80c6bde82 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -13,7 +13,6 @@
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
-
 #include "nodes.h"
 
 #include "code_generator.h"
@@ -90,6 +89,7 @@ void HGraph::RemoveInstructionsAsUsersFromDeadBlocks(const ArenaBitVector& visit
   for (size_t i = 0; i < blocks_.size(); ++i) {
     if (!visited.IsBitSet(i)) {
       HBasicBlock* block = blocks_[i];
+      if (block == nullptr) continue;
       DCHECK(block->GetPhis().IsEmpty()) << "Phis are not inserted at this stage";
       for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
         RemoveAsUser(it.Current());
@@ -102,6 +102,7 @@ void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) {
   for (size_t i = 0; i < blocks_.size(); ++i) {
     if (!visited.IsBitSet(i)) {
       HBasicBlock* block = blocks_[i];
+      if (block == nullptr) continue;
       // We only need to update the successor, which might be live.
       for (HBasicBlock* successor : block->GetSuccessors()) {
         successor->RemovePredecessor(block);
@@ -113,7 +114,7 @@ void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) {
   }
 }
 
-void HGraph::BuildDominatorTree() {
+GraphAnalysisResult HGraph::BuildDominatorTree() {
   // (1) Simplify the CFG so that catch blocks have only exceptional incoming
   //     edges. This invariant simplifies building SSA form because Phis cannot
   //     collect both normal- and exceptional-flow values at the same time.
@@ -130,7 +131,7 @@ void HGraph::BuildDominatorTree() {
   RemoveInstructionsAsUsersFromDeadBlocks(visited);
 
   // (4) Remove blocks not visited during the initial DFS.
-  //     Step (4) requires dead blocks to be removed from the
+  //     Step (5) requires dead blocks to be removed from the
   //     predecessors list of live blocks.
   RemoveDeadBlocks(visited);
 
@@ -140,6 +141,20 @@ void HGraph::BuildDominatorTree() {
 
   // (6) Compute the dominance information and the reverse post order.
   ComputeDominanceInformation();
+
+  // (7) Analyze loops discover through back edge analysis, and
+  //     set the loop information on each block.
+  GraphAnalysisResult result = AnalyzeLoops();
+  if (result != kAnalysisSuccess) {
+    return result;
+  }
+
+  // (8) Precompute per-block try membership before entering the SSA builder,
+  //     which needs the information to build catch block phis from values of
+  //     locals at throwing instructions inside try blocks.
+  ComputeTryBlockInformation();
+
+  return kAnalysisSuccess;
 }
 
 void HGraph::ClearDominanceInformation() {
@@ -149,6 +164,17 @@ void HGraph::ClearDominanceInformation() {
   reverse_post_order_.clear();
 }
 
+void HGraph::ClearLoopInformation() {
+  SetHasIrreducibleLoops(false);
+  for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
+    HBasicBlock* current = it.Current();
+    if (current->IsLoopHeader()) {
+      current->RemoveInstruction(current->GetLoopInformation()->GetSuspendCheck());
+    }
+    current->SetLoopInformation(nullptr);
+  }
+}
+
 void HBasicBlock::ClearDominanceInformation() {
   dominated_blocks_.clear();
   dominator_ = nullptr;
@@ -190,31 +216,28 @@ void HGraph::ComputeDominanceInformation() {
       // dominator of the block. We can then start visiting its successors.
       if (++visits[successor->GetBlockId()] ==
           successor->GetPredecessors().size() - successor->NumberOfBackEdges()) {
-        successor->GetDominator()->AddDominatedBlock(successor);
         reverse_post_order_.push_back(successor);
         worklist.push_back(successor);
       }
     }
   }
-}
 
-BuildSsaResult HGraph::TryBuildingSsa(StackHandleScopeCollection* handles) {
-  BuildDominatorTree();
+  // Populate `dominated_blocks_` information after computing all dominators.
+  // The potential presence of irreducible loops require to do it after.
+  for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
+    HBasicBlock* block = it.Current();
+    if (!block->IsEntryBlock()) {
+      block->GetDominator()->AddDominatedBlock(block);
+    }
+  }
+}
 
-  // The SSA builder requires loops to all be natural. Specifically, the dead phi
-  // elimination phase checks the consistency of the graph when doing a post-order
-  // visit for eliminating dead phis: a dead phi can only have loop header phi
-  // users remaining when being visited.
-  BuildSsaResult result = AnalyzeNaturalLoops();
-  if (result != kBuildSsaSuccess) {
+GraphAnalysisResult HGraph::TryBuildingSsa(StackHandleScopeCollection* handles) {
+  GraphAnalysisResult result = BuildDominatorTree();
+  if (result != kAnalysisSuccess) {
     return result;
   }
 
-  // Precompute per-block try membership before entering the SSA builder,
-  // which needs the information to build catch block phis from values of
-  // locals at throwing instructions inside try blocks.
-  ComputeTryBlockInformation();
-
   // Create the inexact Object reference type and store it in the HGraph.
   ScopedObjectAccess soa(Thread::Current());
   ClassLinker* linker = Runtime::Current()->GetClassLinker();
@@ -224,12 +247,12 @@ BuildSsaResult HGraph::TryBuildingSsa(StackHandleScopeCollection* handles) {
 
   // Tranforms graph to SSA form.
   result = SsaBuilder(this, handles).BuildSsa();
-  if (result != kBuildSsaSuccess) {
+  if (result != kAnalysisSuccess) {
     return result;
   }
 
   in_ssa_form_ = true;
-  return kBuildSsaSuccess;
+  return kAnalysisSuccess;
 }
 
 HBasicBlock* HGraph::SplitEdge(HBasicBlock* block, HBasicBlock* successor) {
@@ -331,7 +354,7 @@ void HGraph::SimplifyCatchBlocks() {
   // can be invalidated. We remember the initial size to avoid iterating over the new blocks.
   for (size_t block_id = 0u, end = blocks_.size(); block_id != end; ++block_id) {
     HBasicBlock* catch_block = blocks_[block_id];
-    if (!catch_block->IsCatchBlock()) {
+    if (catch_block == nullptr || !catch_block->IsCatchBlock()) {
       continue;
     }
 
@@ -438,7 +461,7 @@ void HGraph::SimplifyCFG() {
   }
 }
 
-BuildSsaResult HGraph::AnalyzeNaturalLoops() const {
+GraphAnalysisResult HGraph::AnalyzeLoops() const {
   // Order does not matter.
   for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
     HBasicBlock* block = it.Current();
@@ -446,16 +469,26 @@ BuildSsaResult HGraph::AnalyzeNaturalLoops() const {
       if (block->IsCatchBlock()) {
         // TODO: Dealing with exceptional back edges could be tricky because
         //       they only approximate the real control flow. Bail out for now.
-        return kBuildSsaFailThrowCatchLoop;
-      }
-      HLoopInformation* info = block->GetLoopInformation();
-      if (!info->Populate()) {
-        // Abort if the loop is non natural. We currently bailout in such cases.
-        return kBuildSsaFailNonNaturalLoop;
+        return kAnalysisFailThrowCatchLoop;
       }
+      block->GetLoopInformation()->Populate();
     }
   }
-  return kBuildSsaSuccess;
+  return kAnalysisSuccess;
+}
+
+void HLoopInformation::Dump(std::ostream& os) {
+  os << "header: " << header_->GetBlockId() << std::endl;
+  os << "pre header: " << GetPreHeader()->GetBlockId() << std::endl;
+  for (HBasicBlock* block : back_edges_) {
+    os << "back edge: " << block->GetBlockId() << std::endl;
+  }
+  for (HBasicBlock* block : header_->GetPredecessors()) {
+    os << "predecessor: " << block->GetBlockId() << std::endl;
+  }
+  for (uint32_t idx : blocks_.Indexes()) {
+    os << "  in loop: " << idx << std::endl;
+  }
 }
 
 void HGraph::InsertConstant(HConstant* constant) {
@@ -555,61 +588,65 @@ void HLoopInformation::PopulateRecursive(HBasicBlock* block) {
   }
 }
 
-bool HLoopInformation::Populate() {
-  DCHECK_EQ(blocks_.NumSetBits(), 0u) << "Loop information has already been populated";
-  for (HBasicBlock* back_edge : GetBackEdges()) {
-    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);
+void HLoopInformation::PopulateIrreducibleRecursive(HBasicBlock* block) {
+  if (blocks_.IsBitSet(block->GetBlockId())) {
+    return;
   }
-  return true;
-}
 
-void HLoopInformation::Update() {
-  HGraph* graph = header_->GetGraph();
-  for (uint32_t id : blocks_.Indexes()) {
-    HBasicBlock* block = graph->GetBlocks()[id];
-    // Reset loop information of non-header blocks inside the loop, except
-    // members of inner nested loops because those should already have been
-    // updated by their own LoopInformation.
-    if (block->GetLoopInformation() == this && block != header_) {
-      block->SetLoopInformation(nullptr);
+  if (block->IsLoopHeader()) {
+    // If we hit a loop header in an irreducible loop, we first check if the
+    // pre header of that loop belongs to the currently analyzed loop. If it does,
+    // then we visit the back edges.
+    // Note that we cannot use GetPreHeader, as the loop may have not been populated
+    // yet.
+    HBasicBlock* pre_header = block->GetPredecessors()[0];
+    PopulateIrreducibleRecursive(pre_header);
+    if (blocks_.IsBitSet(pre_header->GetBlockId())) {
+      blocks_.SetBit(block->GetBlockId());
+      block->SetInLoop(this);
+      HLoopInformation* info = block->GetLoopInformation();
+      for (HBasicBlock* back_edge : info->GetBackEdges()) {
+        PopulateIrreducibleRecursive(back_edge);
+      }
     }
-  }
-  blocks_.ClearAllBits();
-
-  if (back_edges_.empty()) {
-    // The loop has been dismantled, delete its suspend check and remove info
-    // from the header.
-    DCHECK(HasSuspendCheck());
-    header_->RemoveInstruction(suspend_check_);
-    header_->SetLoopInformation(nullptr);
-    header_ = nullptr;
-    suspend_check_ = nullptr;
   } else {
-    if (kIsDebugBuild) {
-      for (HBasicBlock* back_edge : back_edges_) {
-        DCHECK(header_->Dominates(back_edge));
+    // Visit all predecessors. If one predecessor is part of the loop, this
+    // block is also part of this loop.
+    for (HBasicBlock* predecessor : block->GetPredecessors()) {
+      PopulateIrreducibleRecursive(predecessor);
+      if (blocks_.IsBitSet(predecessor->GetBlockId())) {
+        blocks_.SetBit(block->GetBlockId());
+        block->SetInLoop(this);
       }
     }
-    // This loop still has reachable back edges. Repopulate the list of blocks.
-    bool populate_successful = Populate();
-    DCHECK(populate_successful);
+  }
+}
+
+void HLoopInformation::Populate() {
+  DCHECK_EQ(blocks_.NumSetBits(), 0u) << "Loop information has already been populated";
+  // 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());
+  header_->SetInLoop(this);
+  for (HBasicBlock* back_edge : GetBackEdges()) {
+    DCHECK(back_edge->GetDominator() != nullptr);
+    if (!header_->Dominates(back_edge)) {
+      irreducible_ = true;
+      header_->GetGraph()->SetHasIrreducibleLoops(true);
+      PopulateIrreducibleRecursive(back_edge);
+    } else {
+      PopulateRecursive(back_edge);
+    }
   }
 }
 
 HBasicBlock* HLoopInformation::GetPreHeader() const {
-  return header_->GetDominator();
+  HBasicBlock* block = header_->GetPredecessors()[0];
+  DCHECK(irreducible_ || (block == header_->GetDominator()));
+  return block;
 }
 
 bool HLoopInformation::Contains(const HBasicBlock& block) const {