ART: Implement try/catch blocks in Builder

This patch enables the GraphBuilder to generate blocks and edges which
represent the exceptional control flow when try/catch blocks are
present in the code. Actual compilation is still delegated to Quick
and Baseline ignores the additional code.

To represent the relationship between try and catch blocks, Builder
splits the edges which enter/exit a try block and links the newly
created blocks to the corresponding exception handlers. This layout
will later enable the SsaBuilder to correctly infer the dominators of
the catch blocks and to produce the appropriate reverse post ordering.
It will not, however, allow for building the complete SSA form of the
catch blocks and consequently optimizing such blocks.

To this end, a new TryBoundary control-flow instruction is introduced.
Codegen treats it the same as a Goto but it allows for additional
successors (the handlers).

Change-Id: I415b985596d5bebb7b1bb358a46e08b7b04bb53a

1 files changed, 55 insertions, 11 deletions

diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index a6390af1f2..881f9ec117 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -189,15 +189,20 @@ void HGraph::TransformToSsa() {
   ssa_builder.BuildSsa();
 }
 
-void HGraph::SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor) {
-  // Insert a new node between `block` and `successor` to split the
-  // critical edge.
+HBasicBlock* HGraph::SplitEdge(HBasicBlock* block, HBasicBlock* successor) {
   HBasicBlock* new_block = new (arena_) HBasicBlock(this, successor->GetDexPc());
   AddBlock(new_block);
-  new_block->AddInstruction(new (arena_) HGoto());
   // Use `InsertBetween` to ensure the predecessor index and successor index of
   // `block` and `successor` are preserved.
   new_block->InsertBetween(block, successor);
+  return new_block;
+}
+
+void HGraph::SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor) {
+  // Insert a new node between `block` and `successor` to split the
+  // critical edge.
+  HBasicBlock* new_block = SplitEdge(block, successor);
+  new_block->AddInstruction(new (arena_) HGoto());
   if (successor->IsLoopHeader()) {
     // If we split at a back edge boundary, make the new block the back edge.
     HLoopInformation* info = successor->GetLoopInformation();
@@ -1019,6 +1024,35 @@ void HInstruction::MoveBefore(HInstruction* cursor) {
   }
 }
 
+HBasicBlock* HBasicBlock::SplitBefore(HInstruction* cursor) {
+  DCHECK(!graph_->IsInSsaForm()) << "Support for SSA form not implemented";
+  DCHECK_EQ(cursor->GetBlock(), this);
+
+  HBasicBlock* new_block = new (GetGraph()->GetArena()) HBasicBlock(GetGraph(), GetDexPc());
+  new_block->instructions_.first_instruction_ = cursor;
+  new_block->instructions_.last_instruction_ = instructions_.last_instruction_;
+  instructions_.last_instruction_ = cursor->previous_;
+  if (cursor->previous_ == nullptr) {
+    instructions_.first_instruction_ = nullptr;
+  } else {
+    cursor->previous_->next_ = nullptr;
+    cursor->previous_ = nullptr;
+  }
+
+  new_block->instructions_.SetBlockOfInstructions(new_block);
+  AddInstruction(new (GetGraph()->GetArena()) HGoto());
+
+  for (size_t i = 0, e = GetSuccessors().Size(); i < e; ++i) {
+    HBasicBlock* successor = GetSuccessors().Get(i);
+    new_block->successors_.Add(successor);
+    successor->predecessors_.Put(successor->GetPredecessorIndexOf(this), new_block);
+  }
+  successors_.Reset();
+  AddSuccessor(new_block);
+
+  return new_block;
+}
+
 HBasicBlock* HBasicBlock::SplitAfter(HInstruction* cursor) {
   DCHECK(!cursor->IsControlFlow());
   DCHECK_NE(instructions_.last_instruction_, cursor);
@@ -1048,14 +1082,24 @@ HBasicBlock* HBasicBlock::SplitAfter(HInstruction* cursor) {
   return new_block;
 }
 
+bool HBasicBlock::IsExceptionalSuccessor(size_t idx) const {
+  return !GetInstructions().IsEmpty()
+      && GetLastInstruction()->IsTryBoundary()
+      && GetLastInstruction()->AsTryBoundary()->IsExceptionalSuccessor(idx);
+}
+
+static bool HasOnlyOneInstruction(const HBasicBlock& block) {
+  return block.GetPhis().IsEmpty()
+      && !block.GetInstructions().IsEmpty()
+      && block.GetFirstInstruction() == block.GetLastInstruction();
+}
+
 bool HBasicBlock::IsSingleGoto() const {
-  HLoopInformation* loop_info = GetLoopInformation();
-  DCHECK(EndsWithControlFlowInstruction());
-  return GetPhis().IsEmpty()
-         && GetFirstInstruction() == GetLastInstruction()
-         && GetLastInstruction()->IsGoto()
-         // Back edges generate the suspend check.
-         && (loop_info == nullptr || !loop_info->IsBackEdge(*this));
+  return HasOnlyOneInstruction(*this) && GetLastInstruction()->IsGoto();
+}
+
+bool HBasicBlock::IsSingleTryBoundary() const {
+  return HasOnlyOneInstruction(*this) && GetLastInstruction()->IsTryBoundary();
 }
 
 bool HBasicBlock::EndsWithControlFlowInstruction() const {