1 files changed, 111 insertions, 49 deletions

diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index b2407c520c..ef89932e3b 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -20,6 +20,7 @@
 #include "ssa_builder.h"
 #include "base/bit_vector-inl.h"
 #include "base/bit_utils.h"
+#include "base/stl_util.h"
 #include "mirror/class-inl.h"
 #include "utils/growable_array.h"
 #include "scoped_thread_state_change.h"
@@ -32,8 +33,41 @@ void HGraph::AddBlock(HBasicBlock* block) {
 }
 
 void HGraph::FindBackEdges(ArenaBitVector* visited) {
+  // "visited" must be empty on entry, it's an output argument for all visited (i.e. live) blocks.
+  DCHECK_EQ(visited->GetHighestBitSet(), -1);
+
+  // Nodes that we're currently visiting, indexed by block id.
   ArenaBitVector visiting(arena_, blocks_.size(), false);
-  VisitBlockForBackEdges(entry_block_, visited, &visiting);
+  // Number of successors visited from a given node, indexed by block id.
+  ArenaVector<size_t> successors_visited(blocks_.size(), 0u, arena_->Adapter());
+  // Stack of nodes that we're currently visiting (same as marked in "visiting" above).
+  ArenaVector<HBasicBlock*> worklist(arena_->Adapter());
+  constexpr size_t kDefaultWorklistSize = 8;
+  worklist.reserve(kDefaultWorklistSize);
+  visited->SetBit(entry_block_->GetBlockId());
+  visiting.SetBit(entry_block_->GetBlockId());
+  worklist.push_back(entry_block_);
+
+  while (!worklist.empty()) {
+    HBasicBlock* current = worklist.back();
+    uint32_t current_id = current->GetBlockId();
+    if (successors_visited[current_id] == current->GetSuccessors().size()) {
+      visiting.ClearBit(current_id);
+      worklist.pop_back();
+    } else {
+      DCHECK_LT(successors_visited[current_id], current->GetSuccessors().size());
+      HBasicBlock* successor = current->GetSuccessors()[successors_visited[current_id]++];
+      uint32_t successor_id = successor->GetBlockId();
+      if (visiting.IsBitSet(successor_id)) {
+        DCHECK(ContainsElement(worklist, successor));
+        successor->AddBackEdge(current);
+      } else if (!visited->IsBitSet(successor_id)) {
+        visited->SetBit(successor_id);
+        visiting.SetBit(successor_id);
+        worklist.push_back(successor);
+      }
+    }
+  }
 }
 
 static void RemoveAsUser(HInstruction* instruction) {
@@ -79,24 +113,6 @@ void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) {
   }
 }
 
-void HGraph::VisitBlockForBackEdges(HBasicBlock* block,
-                                    ArenaBitVector* visited,
-                                    ArenaBitVector* visiting) {
-  int id = block->GetBlockId();
-  if (visited->IsBitSet(id)) return;
-
-  visited->SetBit(id);
-  visiting->SetBit(id);
-  for (HBasicBlock* successor : block->GetSuccessors()) {
-    if (visiting->IsBitSet(successor->GetBlockId())) {
-      successor->AddBackEdge(block);
-    } else {
-      VisitBlockForBackEdges(successor, visited, visiting);
-    }
-  }
-  visiting->ClearBit(id);
-}
-
 void HGraph::BuildDominatorTree() {
   // (1) Simplify the CFG so that catch blocks have only exceptional incoming
   //     edges. This invariant simplifies building SSA form because Phis cannot
@@ -141,10 +157,43 @@ void HBasicBlock::ClearDominanceInformation() {
 void HGraph::ComputeDominanceInformation() {
   DCHECK(reverse_post_order_.empty());
   reverse_post_order_.reserve(blocks_.size());
-  ArenaVector<size_t> visits(blocks_.size(), 0u, arena_->Adapter());
   reverse_post_order_.push_back(entry_block_);
-  for (HBasicBlock* successor : entry_block_->GetSuccessors()) {
-    VisitBlockForDominatorTree(successor, entry_block_, &visits);
+
+  // Number of visits of a given node, indexed by block id.
+  ArenaVector<size_t> visits(blocks_.size(), 0u, arena_->Adapter());
+  // Number of successors visited from a given node, indexed by block id.
+  ArenaVector<size_t> successors_visited(blocks_.size(), 0u, arena_->Adapter());
+  // Nodes for which we need to visit successors.
+  ArenaVector<HBasicBlock*> worklist(arena_->Adapter());
+  constexpr size_t kDefaultWorklistSize = 8;
+  worklist.reserve(kDefaultWorklistSize);
+  worklist.push_back(entry_block_);
+
+  while (!worklist.empty()) {
+    HBasicBlock* current = worklist.back();
+    uint32_t current_id = current->GetBlockId();
+    if (successors_visited[current_id] == current->GetSuccessors().size()) {
+      worklist.pop_back();
+    } else {
+      DCHECK_LT(successors_visited[current_id], current->GetSuccessors().size());
+      HBasicBlock* successor = current->GetSuccessors()[successors_visited[current_id]++];
+
+      if (successor->GetDominator() == nullptr) {
+        successor->SetDominator(current);
+      } else {
+        successor->SetDominator(FindCommonDominator(successor->GetDominator(), current));
+      }
+
+      // Once all the forward edges have been visited, we know the immediate
+      // dominator of the block. We can then start visiting its successors.
+      DCHECK_LT(successor->GetBlockId(), visits.size());
+      if (++visits[successor->GetBlockId()] ==
+          successor->GetPredecessors().size() - successor->NumberOfBackEdges()) {
+        successor->GetDominator()->AddDominatedBlock(successor);
+        reverse_post_order_.push_back(successor);
+        worklist.push_back(successor);
+      }
+    }
   }
 }
 
@@ -166,28 +215,6 @@ HBasicBlock* HGraph::FindCommonDominator(HBasicBlock* first, HBasicBlock* second
   return nullptr;
 }
 
-void HGraph::VisitBlockForDominatorTree(HBasicBlock* block,
-                                        HBasicBlock* predecessor,
-                                        ArenaVector<size_t>* visits) {
-  if (block->GetDominator() == nullptr) {
-    block->SetDominator(predecessor);
-  } else {
-    block->SetDominator(FindCommonDominator(block->GetDominator(), predecessor));
-  }
-
-  // Once all the forward edges have been visited, we know the immediate
-  // dominator of the block. We can then start visiting its successors.
-  DCHECK_LT(block->GetBlockId(), visits->size());
-  if (++(*visits)[block->GetBlockId()] ==
-      block->GetPredecessors().size() - block->NumberOfBackEdges()) {
-    block->GetDominator()->AddDominatedBlock(block);
-    reverse_post_order_.push_back(block);
-    for (HBasicBlock* successor : block->GetSuccessors()) {
-      VisitBlockForDominatorTree(successor, block, visits);
-    }
-  }
-}
-
 void HGraph::TransformToSsa() {
   DCHECK(!reverse_post_order_.empty());
   SsaBuilder ssa_builder(this);
@@ -1143,6 +1170,23 @@ HBasicBlock* HBasicBlock::SplitBefore(HInstruction* cursor) {
   return new_block;
 }
 
+HBasicBlock* HBasicBlock::CreateImmediateDominator() {
+  DCHECK(!graph_->IsInSsaForm()) << "Support for SSA form not implemented";
+  DCHECK(!IsCatchBlock()) << "Support for updating try/catch information not implemented.";
+
+  HBasicBlock* new_block = new (GetGraph()->GetArena()) HBasicBlock(GetGraph(), GetDexPc());
+
+  for (HBasicBlock* predecessor : GetPredecessors()) {
+    new_block->predecessors_.push_back(predecessor);
+    predecessor->successors_[predecessor->GetSuccessorIndexOf(this)] = new_block;
+  }
+  predecessors_.clear();
+  AddPredecessor(new_block);
+
+  GetGraph()->AddBlock(new_block);
+  return new_block;
+}
+
 HBasicBlock* HBasicBlock::SplitAfter(HInstruction* cursor) {
   DCHECK(!cursor->IsControlFlow());
   DCHECK_NE(instructions_.last_instruction_, cursor);
@@ -1188,6 +1232,15 @@ const HTryBoundary* HBasicBlock::ComputeTryEntryOfSuccessors() const {
   }
 }
 
+bool HBasicBlock::HasThrowingInstructions() const {
+  for (HInstructionIterator it(GetInstructions()); !it.Done(); it.Advance()) {
+    if (it.Current()->CanThrow()) {
+      return true;
+    }
+  }
+  return false;
+}
+
 static bool HasOnlyOneInstruction(const HBasicBlock& block) {
   return block.GetPhis().IsEmpty()
       && !block.GetInstructions().IsEmpty()
@@ -1297,16 +1350,25 @@ void HBasicBlock::DisconnectAndDelete() {
   // instructions.
   for (HBasicBlock* predecessor : predecessors_) {
     HInstruction* last_instruction = predecessor->GetLastInstruction();
-    predecessor->RemoveInstruction(last_instruction);
     predecessor->RemoveSuccessor(this);
-    if (predecessor->GetSuccessors().size() == 1u) {
-      DCHECK(last_instruction->IsIf());
+    uint32_t num_pred_successors = predecessor->GetSuccessors().size();
+    if (num_pred_successors == 1u) {
+      // If we have one successor after removing one, then we must have
+      // had an HIf or HPackedSwitch, as they have more than one successor.
+      // Replace those with a HGoto.
+      DCHECK(last_instruction->IsIf() || last_instruction->IsPackedSwitch());
+      predecessor->RemoveInstruction(last_instruction);
       predecessor->AddInstruction(new (graph_->GetArena()) HGoto(last_instruction->GetDexPc()));
-    } else {
+    } else if (num_pred_successors == 0u) {
       // The predecessor has no remaining successors and therefore must be dead.
       // We deliberately leave it without a control-flow instruction so that the
       // SSAChecker fails unless it is not removed during the pass too.
-      DCHECK_EQ(predecessor->GetSuccessors().size(), 0u);
+      predecessor->RemoveInstruction(last_instruction);
+    } else {
+      // There are multiple successors left.  This must come from a HPackedSwitch
+      // and we are in the middle of removing the HPackedSwitch. Like above, leave
+      // this alone, and the SSAChecker will fail if it is not removed as well.
+      DCHECK(last_instruction->IsPackedSwitch());
     }
   }
   predecessors_.clear();