ART: Store and check exceptional predecessors

Future CL on register allocation for try/catch will require the
knowledge of instructions which throw into a catch block. This patch
stores that information with the basic block and verifies it in the
graph checker.

More checks on try catch also added to the graph checker and an order
of exception handlers is enforced in TryBoundary successors.

Change-Id: I3034c610791ea51d96724bcca97f49ec6ecf2af3

1 files changed, 101 insertions, 1 deletions

diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index cfebb77dd7..e4bc9e68e1 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -89,6 +89,33 @@ void GraphChecker::VisitBasicBlock(HBasicBlock* block) {
                           block->GetBlockId()));
   }
 
+  // Ensure that the only Return(Void) and Throw jump to Exit. An exiting
+  // TryBoundary may be between a Throw and the Exit if the Throw is in a try.
+  if (block->IsExitBlock()) {
+    for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) {
+      HBasicBlock* predecessor = block->GetPredecessors().Get(i);
+      if (predecessor->IsSingleTryBoundary()
+          && !predecessor->GetLastInstruction()->AsTryBoundary()->IsEntry()) {
+        HBasicBlock* real_predecessor = predecessor->GetSinglePredecessor();
+        HInstruction* last_instruction = real_predecessor->GetLastInstruction();
+        if (!last_instruction->IsThrow()) {
+          AddError(StringPrintf("Unexpected TryBoundary between %s:%d and Exit.",
+                                last_instruction->DebugName(),
+                                last_instruction->GetId()));
+        }
+      } else {
+        HInstruction* last_instruction = predecessor->GetLastInstruction();
+        if (!last_instruction->IsReturn()
+            && !last_instruction->IsReturnVoid()
+            && !last_instruction->IsThrow()) {
+          AddError(StringPrintf("Unexpected instruction %s:%d jumps into the exit block.",
+                                last_instruction->DebugName(),
+                                last_instruction->GetId()));
+        }
+      }
+    }
+  }
+
   // Visit this block's list of phis.
   for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
     HInstruction* current = it.Current();
@@ -328,6 +355,39 @@ void GraphChecker::VisitInstanceOf(HInstanceOf* instruction) {
 void SSAChecker::VisitBasicBlock(HBasicBlock* block) {
   super_type::VisitBasicBlock(block);
 
+  // Ensure that only catch blocks have exceptional predecessors, and if they do
+  // these are instructions which throw into them.
+  if (block->IsCatchBlock()) {
+    for (size_t i = 0, e = block->GetExceptionalPredecessors().Size(); i < e; ++i) {
+      HInstruction* thrower = block->GetExceptionalPredecessors().Get(i);
+      HBasicBlock* try_block = thrower->GetBlock();
+      if (!thrower->CanThrow()) {
+        AddError(StringPrintf("Exceptional predecessor %s:%d of catch block %d does not throw.",
+                              thrower->DebugName(),
+                              thrower->GetId(),
+                              block->GetBlockId()));
+      } else if (!try_block->IsInTry()) {
+        AddError(StringPrintf("Exceptional predecessor %s:%d of catch block %d "
+                              "is not in a try block.",
+                              thrower->DebugName(),
+                              thrower->GetId(),
+                              block->GetBlockId()));
+      } else if (!try_block->GetTryEntry()->HasExceptionHandler(*block)) {
+        AddError(StringPrintf("Catch block %d is not an exception handler of "
+                              "its exceptional predecessor %s:%d.",
+                              block->GetBlockId(),
+                              thrower->DebugName(),
+                              thrower->GetId()));
+      }
+    }
+  } else {
+    if (!block->GetExceptionalPredecessors().IsEmpty()) {
+      AddError(StringPrintf("Normal block %d has %zu exceptional predecessors.",
+                            block->GetBlockId(),
+                            block->GetExceptionalPredecessors().Size()));
+    }
+  }
+
   // Ensure that catch blocks are not normal successors, and normal blocks are
   // never exceptional successors.
   const size_t num_normal_successors = block->NumberOfNormalSuccessors();
@@ -512,6 +572,7 @@ void SSAChecker::CheckLoop(HBasicBlock* loop_header) {
 
 void SSAChecker::VisitInstruction(HInstruction* instruction) {
   super_type::VisitInstruction(instruction);
+  HBasicBlock* block = instruction->GetBlock();
 
   // Ensure an instruction dominates all its uses.
   for (HUseIterator<HInstruction*> use_it(instruction->GetUses());
@@ -543,6 +604,24 @@ void SSAChecker::VisitInstruction(HInstruction* instruction) {
       }
     }
   }
+
+  // Ensure that throwing instructions in try blocks are listed as exceptional
+  // predecessors in their exception handlers.
+  if (instruction->CanThrow() && block->IsInTry()) {
+    for (HExceptionHandlerIterator handler_it(*block->GetTryEntry());
+         !handler_it.Done();
+         handler_it.Advance()) {
+      if (!handler_it.Current()->GetExceptionalPredecessors().Contains(instruction)) {
+        AddError(StringPrintf("Instruction %s:%d is in try block %d and can throw "
+                              "but its exception handler %d does not list it in "
+                              "its exceptional predecessors.",
+                              instruction->DebugName(),
+                              instruction->GetId(),
+                              block->GetBlockId(),
+                              handler_it.Current()->GetBlockId()));
+      }
+    }
+  }
 }
 
 static Primitive::Type PrimitiveKind(Primitive::Type type) {
@@ -590,11 +669,32 @@ void SSAChecker::VisitPhi(HPhi* phi) {
   if (phi->IsCatchPhi()) {
     // The number of inputs of a catch phi corresponds to the total number of
     // throwing instructions caught by this catch block.
+    const GrowableArray<HInstruction*>& predecessors =
+        phi->GetBlock()->GetExceptionalPredecessors();
+    if (phi->InputCount() != predecessors.Size()) {
+      AddError(StringPrintf(
+          "Phi %d in catch block %d has %zu inputs, "
+          "but catch block %d has %zu exceptional predecessors.",
+          phi->GetId(), phi->GetBlock()->GetBlockId(), phi->InputCount(),
+          phi->GetBlock()->GetBlockId(), predecessors.Size()));
+    } else {
+      for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
+        HInstruction* input = phi->InputAt(i);
+        HInstruction* thrower = predecessors.Get(i);
+        if (!input->StrictlyDominates(thrower)) {
+          AddError(StringPrintf(
+              "Input %d at index %zu of phi %d from catch block %d does not "
+              "dominate the throwing instruction %s:%d.",
+              input->GetId(), i, phi->GetId(), phi->GetBlock()->GetBlockId(),
+              thrower->DebugName(), thrower->GetId()));
+        }
+      }
+    }
   } else {
     // Ensure the number of inputs of a non-catch phi is the same as the number
     // of its predecessors.
     const GrowableArray<HBasicBlock*>& predecessors =
-      phi->GetBlock()->GetPredecessors();
+        phi->GetBlock()->GetPredecessors();
     if (phi->InputCount() != predecessors.Size()) {
       AddError(StringPrintf(
           "Phi %d in block %d has %zu inputs, "