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
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index cfebb77..e4bc9e68 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -89,6 +89,33 @@
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 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::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 @@
}
}
}
+
+ // 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 @@
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, "
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 188cb49..61dadc2 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -564,6 +564,13 @@
return false;
}
+void HBasicBlock::AddExceptionalPredecessor(HInstruction* exceptional_predecessor) {
+ DCHECK(exceptional_predecessor->CanThrow());
+ DCHECK(exceptional_predecessor->GetBlock()->IsInTry());
+ DCHECK(exceptional_predecessor->GetBlock()->GetTryEntry()->HasExceptionHandler(*this));
+ exceptional_predecessors_.Add(exceptional_predecessor);
+}
+
static void UpdateInputsUsers(HInstruction* instruction) {
for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) {
instruction->InputAt(i)->AddUseAt(instruction, i);
@@ -1225,10 +1232,12 @@
return false;
}
- // Exception handler lists cannot contain duplicates, which makes it
- // sufficient to test inclusion only in one direction.
- for (HExceptionHandlerIterator it(other); !it.Done(); it.Advance()) {
- if (!HasExceptionHandler(*it.Current())) {
+ // 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()) {
return false;
}
}
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 003900c..9b8521d 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -58,6 +58,7 @@
static const int kDefaultNumberOfBlocks = 8;
static const int kDefaultNumberOfSuccessors = 2;
static const int kDefaultNumberOfPredecessors = 2;
+static const int kDefaultNumberOfExceptionalPredecessors = 0;
static const int kDefaultNumberOfDominatedBlocks = 1;
static const int kDefaultNumberOfBackEdges = 1;
@@ -564,6 +565,7 @@
explicit HBasicBlock(HGraph* graph, uint32_t dex_pc = kNoDexPc)
: graph_(graph),
predecessors_(graph->GetArena(), kDefaultNumberOfPredecessors),
+ exceptional_predecessors_(graph->GetArena(), kDefaultNumberOfExceptionalPredecessors),
successors_(graph->GetArena(), kDefaultNumberOfSuccessors),
loop_information_(nullptr),
dominator_(nullptr),
@@ -578,6 +580,10 @@
return predecessors_;
}
+ const GrowableArray<HInstruction*>& GetExceptionalPredecessors() const {
+ return exceptional_predecessors_;
+ }
+
const GrowableArray<HBasicBlock*>& GetSuccessors() const {
return successors_;
}
@@ -646,6 +652,8 @@
HInstruction* GetLastPhi() const { return phis_.last_instruction_; }
const HInstructionList& GetPhis() const { return phis_; }
+ void AddExceptionalPredecessor(HInstruction* exceptional_predecessor);
+
void AddSuccessor(HBasicBlock* block) {
successors_.Add(block);
block->predecessors_.Add(this);
@@ -685,6 +693,10 @@
predecessors_.Delete(block);
}
+ void RemoveExceptionalPredecessor(HInstruction* instruction) {
+ exceptional_predecessors_.Delete(instruction);
+ }
+
void RemoveSuccessor(HBasicBlock* block) {
successors_.Delete(block);
}
@@ -721,6 +733,15 @@
return -1;
}
+ size_t GetExceptionalPredecessorIndexOf(HInstruction* exceptional_predecessor) const {
+ for (size_t i = 0, e = exceptional_predecessors_.Size(); i < e; ++i) {
+ if (exceptional_predecessors_.Get(i) == exceptional_predecessor) {
+ return i;
+ }
+ }
+ return -1;
+ }
+
size_t GetSuccessorIndexOf(HBasicBlock* successor) const {
for (size_t i = 0, e = successors_.Size(); i < e; ++i) {
if (successors_.Get(i) == successor) {
@@ -881,6 +902,7 @@
private:
HGraph* graph_;
GrowableArray<HBasicBlock*> predecessors_;
+ GrowableArray<HInstruction*> exceptional_predecessors_;
GrowableArray<HBasicBlock*> successors_;
HInstructionList instructions_;
HInstructionList phis_;
diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index ff2e6ad..2c34e4d 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -570,7 +570,9 @@
if (instruction->GetBlock()->IsInTry() && instruction->CanThrow()) {
HTryBoundary* try_block = instruction->GetBlock()->GetTryEntry();
for (HExceptionHandlerIterator it(*try_block); !it.Done(); it.Advance()) {
- GrowableArray<HInstruction*>* handler_locals = GetLocalsFor(it.Current());
+ HBasicBlock* handler = it.Current();
+ handler->AddExceptionalPredecessor(instruction);
+ GrowableArray<HInstruction*>* handler_locals = GetLocalsFor(handler);
for (size_t i = 0, e = current_locals_->Size(); i < e; ++i) {
HInstruction* local_value = current_locals_->Get(i);
if (local_value != nullptr) {
