ART: Refactor iteration over normal/exceptional successors

Add helper methods on HBasicBlock which return ArrayRef with the
suitable sub-array of the `successors_` list.

Change-Id: I66c83bb56f2984d7550bf77c48110af4087515a8

6 files changed, 69 insertions, 56 deletions

diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index 27949f7fe8..091f1c7e89 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -162,13 +162,20 @@ void GraphChecker::VisitBoundsCheck(HBoundsCheck* check) {
   VisitInstruction(check);
 }
 
+// Returns true if there exists `index2` such that `index2 > index` and
+// `array[index] == array[index2]`.
+static bool ContainsSameValueAfter(ArrayRef<HBasicBlock* const> array, size_t index) {
+  ArrayRef<HBasicBlock* const> tail = array.SubArray(index + 1);
+  return std::find(tail.begin(), tail.end(), array[index]) != tail.end();
+}
+
 void GraphChecker::VisitTryBoundary(HTryBoundary* try_boundary) {
-  // Ensure that all exception handlers are catch blocks and that handlers
-  // are not listed multiple times.
+  ArrayRef<HBasicBlock* const> handlers = try_boundary->GetExceptionHandlers();
+
+  // Ensure that all exception handlers are catch blocks.
   // Note that a normal-flow successor may be a catch block before CFG
   // simplification. We only test normal-flow successors in SsaChecker.
-  for (HExceptionHandlerIterator it(*try_boundary); !it.Done(); it.Advance()) {
-    HBasicBlock* handler = it.Current();
+  for (HBasicBlock* handler : handlers) {
     if (!handler->IsCatchBlock()) {
       AddError(StringPrintf("Block %d with %s:%d has exceptional successor %d which "
                             "is not a catch block.",
@@ -177,9 +184,13 @@ void GraphChecker::VisitTryBoundary(HTryBoundary* try_boundary) {
                             try_boundary->GetId(),
                             handler->GetBlockId()));
     }
-    if (current_block_->HasSuccessor(handler, it.CurrentSuccessorIndex() + 1)) {
+  }
+
+  // Ensure that handlers are not listed multiple times.
+  for (size_t i = 0, e = handlers.size(); i < e; ++i) {
+    if (ContainsSameValueAfter(handlers, i)) {
       AddError(StringPrintf("Exception handler block %d of %s:%d is listed multiple times.",
-                            handler->GetBlockId(),
+                            handlers[i]->GetBlockId(),
                             try_boundary->DebugName(),
                             try_boundary->GetId()));
     }
@@ -371,17 +382,14 @@ void SSAChecker::VisitBasicBlock(HBasicBlock* block) {
 
   // Ensure that catch blocks are not normal successors, and normal blocks are
   // never exceptional successors.
-  const size_t num_normal_successors = block->NumberOfNormalSuccessors();
-  for (size_t j = 0; j < num_normal_successors; ++j) {
-    HBasicBlock* successor = block->GetSuccessors()[j];
+  for (HBasicBlock* successor : block->GetNormalSuccessors()) {
     if (successor->IsCatchBlock()) {
       AddError(StringPrintf("Catch block %d is a normal successor of block %d.",
                             successor->GetBlockId(),
                             block->GetBlockId()));
     }
   }
-  for (size_t j = num_normal_successors, e = block->GetSuccessors().size(); j < e; ++j) {
-    HBasicBlock* successor = block->GetSuccessors()[j];
+  for (HBasicBlock* successor : block->GetExceptionalSuccessors()) {
     if (!successor->IsCatchBlock()) {
       AddError(StringPrintf("Normal block %d is an exceptional successor of block %d.",
                             successor->GetBlockId(),
@@ -394,8 +402,7 @@ void SSAChecker::VisitBasicBlock(HBasicBlock* block) {
   // predecessors). Exceptional edges are synthesized and hence
   // not accounted for.
   if (block->GetSuccessors().size() > 1) {
-    for (size_t j = 0, e = block->NumberOfNormalSuccessors(); j < e; ++j) {
-      HBasicBlock* successor = block->GetSuccessors()[j];
+    for (HBasicBlock* successor : block->GetNormalSuccessors()) {
       if (successor->IsExitBlock() &&
           block->IsSingleTryBoundary() &&
           block->GetPredecessors().size() == 1u &&
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index 4111671a9b..505603a85e 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -252,8 +252,7 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor {
   void PrintSuccessors(HBasicBlock* block) {
     AddIndent();
     output_ << "successors";
-    for (size_t i = 0; i < block->NumberOfNormalSuccessors(); ++i) {
-      HBasicBlock* successor = block->GetSuccessors()[i];
+    for (HBasicBlock* successor : block->GetNormalSuccessors()) {
       output_ << " \"B" << successor->GetBlockId() << "\" ";
     }
     output_<< std::endl;
@@ -262,8 +261,7 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor {
   void PrintExceptionHandlers(HBasicBlock* block) {
     AddIndent();
     output_ << "xhandlers";
-    for (size_t i = block->NumberOfNormalSuccessors(); i < block->GetSuccessors().size(); ++i) {
-      HBasicBlock* handler = block->GetSuccessors()[i];
+    for (HBasicBlock* handler : block->GetExceptionalSuccessors()) {
       output_ << " \"B" << handler->GetBlockId() << "\" ";
     }
     if (block->IsExitBlock() &&
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index f006df1852..8100b58ae6 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -385,8 +385,9 @@ void HGraph::SimplifyCFG() {
       // Only split normal-flow edges. We cannot split exceptional edges as they
       // are synthesized (approximate real control flow), and we do not need to
       // anyway. Moves that would be inserted there are performed by the runtime.
-      for (size_t j = 0, e = block->NumberOfNormalSuccessors(); j < e; ++j) {
-        HBasicBlock* successor = block->GetSuccessors()[j];
+      ArrayRef<HBasicBlock* const> normal_successors = block->GetNormalSuccessors();
+      for (size_t j = 0, e = normal_successors.size(); j < e; ++j) {
+        HBasicBlock* successor = normal_successors[j];
         DCHECK(!successor->IsCatchBlock());
         if (successor == exit_block_) {
           // Throw->TryBoundary->Exit. Special case which we do not want to split
@@ -395,7 +396,11 @@ void HGraph::SimplifyCFG() {
           DCHECK(block->GetSinglePredecessor()->GetLastInstruction()->IsThrow());
         } else if (successor->GetPredecessors().size() > 1) {
           SplitCriticalEdge(block, successor);
-          --j;
+          // SplitCriticalEdge could have invalidated the `normal_successors`
+          // ArrayRef. We must re-acquire it.
+          normal_successors = block->GetNormalSuccessors();
+          DCHECK_EQ(normal_successors[j]->GetSingleSuccessor(), successor);
+          DCHECK_EQ(e, normal_successors.size());
         }
       }
     }
@@ -1329,17 +1334,38 @@ bool HBasicBlock::HasSinglePhi() const {
   return !GetPhis().IsEmpty() && GetFirstPhi()->GetNext() == nullptr;
 }
 
+ArrayRef<HBasicBlock* const> HBasicBlock::GetNormalSuccessors() const {
+  if (EndsWithTryBoundary()) {
+    // The normal-flow successor of HTryBoundary is always stored at index zero.
+    DCHECK_EQ(successors_[0], GetLastInstruction()->AsTryBoundary()->GetNormalFlowSuccessor());
+    return ArrayRef<HBasicBlock* const>(successors_).SubArray(0u, 1u);
+  } else {
+    // All successors of blocks not ending with TryBoundary are normal.
+    return ArrayRef<HBasicBlock* const>(successors_);
+  }
+}
+
+ArrayRef<HBasicBlock* const> HBasicBlock::GetExceptionalSuccessors() const {
+  if (EndsWithTryBoundary()) {
+    return GetLastInstruction()->AsTryBoundary()->GetExceptionHandlers();
+  } else {
+    // Blocks not ending with TryBoundary do not have exceptional successors.
+    return ArrayRef<HBasicBlock* const>();
+  }
+}
+
 bool HTryBoundary::HasSameExceptionHandlersAs(const HTryBoundary& other) const {
-  if (GetBlock()->GetSuccessors().size() != other.GetBlock()->GetSuccessors().size()) {
+  ArrayRef<HBasicBlock* const> handlers1 = GetExceptionHandlers();
+  ArrayRef<HBasicBlock* const> handlers2 = other.GetExceptionHandlers();
+
+  size_t length = handlers1.size();
+  if (length != handlers2.size()) {
     return false;
   }
 
   // Exception handlers need to be stored in the same order.
-  for (HExceptionHandlerIterator it1(*this), it2(other);
-       !it1.Done();
-       it1.Advance(), it2.Advance()) {
-    DCHECK(!it2.Done());
-    if (it1.Current() != it2.Current()) {
+  for (size_t i = 0; i < length; ++i) {
+    if (handlers1[i] != handlers2[i]) {
       return false;
     }
   }
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 4421419f10..a3f3d17b9d 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -35,6 +35,7 @@
 #include "mirror/class.h"
 #include "offsets.h"
 #include "primitive.h"
+#include "utils/array_ref.h"
 
 namespace art {
 
@@ -660,6 +661,9 @@ class HBasicBlock : public ArenaObject<kArenaAllocBasicBlock> {
     return successors_;
   }
 
+  ArrayRef<HBasicBlock* const> GetNormalSuccessors() const;
+  ArrayRef<HBasicBlock* const> GetExceptionalSuccessors() const;
+
   bool HasSuccessor(const HBasicBlock* block, size_t start_from = 0u) {
     return ContainsElement(successors_, block, start_from);
   }
@@ -810,12 +814,6 @@ class HBasicBlock : public ArenaObject<kArenaAllocBasicBlock> {
     return GetPredecessorIndexOf(predecessor) == idx;
   }
 
-  // Returns the number of non-exceptional successors. SsaChecker ensures that
-  // these are stored at the beginning of the successor list.
-  size_t NumberOfNormalSuccessors() const {
-    return EndsWithTryBoundary() ? 1 : GetSuccessors().size();
-  }
-
   // Create a new block between this block and its predecessors. The new block
   // is added to the graph, all predecessor edges are relinked to it and an edge
   // is created to `this`. Returns the new empty block. Reverse post order or
@@ -2398,6 +2396,10 @@ class HTryBoundary : public HTemplateInstruction<0> {
   // Returns the block's non-exceptional successor (index zero).
   HBasicBlock* GetNormalFlowSuccessor() const { return GetBlock()->GetSuccessors()[0]; }
 
+  ArrayRef<HBasicBlock* const> GetExceptionHandlers() const {
+    return ArrayRef<HBasicBlock* const>(GetBlock()->GetSuccessors()).SubArray(1u);
+  }
+
   // Returns whether `handler` is among its exception handlers (non-zero index
   // successors).
   bool HasExceptionHandler(const HBasicBlock& handler) const {
@@ -2425,25 +2427,6 @@ class HTryBoundary : public HTemplateInstruction<0> {
   DISALLOW_COPY_AND_ASSIGN(HTryBoundary);
 };
 
-// Iterator over exception handlers of a given HTryBoundary, i.e. over
-// exceptional successors of its basic block.
-class HExceptionHandlerIterator : public ValueObject {
- public:
-  explicit HExceptionHandlerIterator(const HTryBoundary& try_boundary)
-    : block_(*try_boundary.GetBlock()), index_(block_.NumberOfNormalSuccessors()) {}
-
-  bool Done() const { return index_ == block_.GetSuccessors().size(); }
-  HBasicBlock* Current() const { return block_.GetSuccessors()[index_]; }
-  size_t CurrentSuccessorIndex() const { return index_; }
-  void Advance() { ++index_; }
-
- private:
-  const HBasicBlock& block_;
-  size_t index_;
-
-  DISALLOW_COPY_AND_ASSIGN(HExceptionHandlerIterator);
-};
-
 // Deoptimize to interpreter, upon checking a condition.
 class HDeoptimize : public HTemplateInstruction<1> {
  public:
diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index ef22c816a0..d399bc2d7a 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -1525,7 +1525,7 @@ void RegisterAllocator::InsertParallelMoveAtExitOf(HBasicBlock* block,
   DCHECK(IsValidDestination(destination)) << destination;
   if (source.Equals(destination)) return;
 
-  DCHECK_EQ(block->NumberOfNormalSuccessors(), 1u);
+  DCHECK_EQ(block->GetNormalSuccessors().size(), 1u);
   HInstruction* last = block->GetLastInstruction();
   // We insert moves at exit for phi predecessors and connecting blocks.
   // A block ending with an if or a packed switch cannot branch to a block
@@ -1752,7 +1752,7 @@ void RegisterAllocator::ConnectSplitSiblings(LiveInterval* interval,
 
   // If `from` has only one successor, we can put the moves at the exit of it. Otherwise
   // we need to put the moves at the entry of `to`.
-  if (from->NumberOfNormalSuccessors() == 1) {
+  if (from->GetNormalSuccessors().size() == 1) {
     InsertParallelMoveAtExitOf(from,
                                interval->GetParent()->GetDefinedBy(),
                                source->ToLocation(),
@@ -1894,7 +1894,7 @@ void RegisterAllocator::Resolve() {
         HInstruction* phi = inst_it.Current();
         for (size_t i = 0, e = current->GetPredecessors().size(); i < e; ++i) {
           HBasicBlock* predecessor = current->GetPredecessors()[i];
-          DCHECK_EQ(predecessor->NumberOfNormalSuccessors(), 1u);
+          DCHECK_EQ(predecessor->GetNormalSuccessors().size(), 1u);
           HInstruction* input = phi->InputAt(i);
           Location source = input->GetLiveInterval()->GetLocationAt(
               predecessor->GetLifetimeEnd() - 1);
diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index 4565590bc3..5190eb3b26 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -660,8 +660,7 @@ void SsaBuilder::VisitInstruction(HInstruction* instruction) {
   if (instruction->CanThrowIntoCatchBlock()) {
     const HTryBoundary& try_entry =
         instruction->GetBlock()->GetTryCatchInformation()->GetTryEntry();
-    for (HExceptionHandlerIterator it(try_entry); !it.Done(); it.Advance()) {
-      HBasicBlock* catch_block = it.Current();
+    for (HBasicBlock* catch_block : try_entry.GetExceptionHandlers()) {
       ArenaVector<HInstruction*>* handler_locals = GetLocalsFor(catch_block);
       DCHECK_EQ(handler_locals->size(), current_locals_->size());
       for (size_t vreg = 0, e = current_locals_->size(); vreg < e; ++vreg) {