Revert "Revert "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).
This reverts commit 3e18738bd338e9f8363b26bc895f38c0ec682824.
Change-Id: I4f5ea961848a0b83d8db3673763861633e9bfcfb
diff --git a/compiler/optimizing/builder.cc b/compiler/optimizing/builder.cc
index e527e8b..bde2c70 100644
--- a/compiler/optimizing/builder.cc
+++ b/compiler/optimizing/builder.cc
@@ -259,6 +259,165 @@
return false;
}
+bool HGraphBuilder::IsBlockInPcRange(HBasicBlock* block,
+ uint32_t dex_pc_start,
+ uint32_t dex_pc_end) {
+ uint32_t dex_pc = block->GetDexPc();
+ return block != entry_block_
+ && block != exit_block_
+ && dex_pc >= dex_pc_start
+ && dex_pc < dex_pc_end;
+}
+
+void HGraphBuilder::CreateBlocksForTryCatch(const DexFile::CodeItem& code_item) {
+ if (code_item.tries_size_ == 0) {
+ return;
+ }
+
+ // Create branch targets at the start/end of the TryItem range. These are
+ // places where the program might fall through into/out of the a block and
+ // where TryBoundary instructions will be inserted later. Other edges which
+ // enter/exit the try blocks are a result of branches/switches.
+ for (size_t idx = 0; idx < code_item.tries_size_; ++idx) {
+ const DexFile::TryItem* try_item = DexFile::GetTryItems(code_item, idx);
+ uint32_t dex_pc_start = try_item->start_addr_;
+ uint32_t dex_pc_end = dex_pc_start + try_item->insn_count_;
+ FindOrCreateBlockStartingAt(dex_pc_start);
+ if (dex_pc_end < code_item.insns_size_in_code_units_) {
+ // TODO: Do not create block if the last instruction cannot fall through.
+ FindOrCreateBlockStartingAt(dex_pc_end);
+ } else {
+ // The TryItem spans until the very end of the CodeItem (or beyond if
+ // invalid) and therefore cannot have any code afterwards.
+ }
+ }
+
+ // Create branch targets for exception handlers.
+ const uint8_t* handlers_ptr = DexFile::GetCatchHandlerData(code_item, 0);
+ uint32_t handlers_size = DecodeUnsignedLeb128(&handlers_ptr);
+ for (uint32_t idx = 0; idx < handlers_size; ++idx) {
+ CatchHandlerIterator iterator(handlers_ptr);
+ for (; iterator.HasNext(); iterator.Next()) {
+ uint32_t address = iterator.GetHandlerAddress();
+ HBasicBlock* block = FindOrCreateBlockStartingAt(address);
+ block->SetIsCatchBlock();
+ }
+ handlers_ptr = iterator.EndDataPointer();
+ }
+}
+
+void HGraphBuilder::InsertTryBoundaryBlocks(const DexFile::CodeItem& code_item) {
+ if (code_item.tries_size_ == 0) {
+ return;
+ }
+
+ for (size_t idx = 0; idx < code_item.tries_size_; ++idx) {
+ const DexFile::TryItem* try_item = DexFile::GetTryItems(code_item, idx);
+ uint32_t try_start = try_item->start_addr_;
+ uint32_t try_end = try_start + try_item->insn_count_;
+
+ // Iterate over all blocks in the dex pc range of the TryItem and:
+ // (a) split edges which enter/exit the try range,
+ // (b) create TryBoundary instructions in the new blocks,
+ // (c) link the new blocks to corresponding exception handlers.
+ for (uint32_t inner_pc = try_start; inner_pc < try_end; ++inner_pc) {
+ HBasicBlock* try_block = FindBlockStartingAt(inner_pc);
+ if (try_block == nullptr) {
+ continue;
+ }
+
+ // Find predecessors which are not covered by the same TryItem range. Such
+ // edges enter the try block and will have a TryBoundary inserted.
+ for (size_t i = 0; i < try_block->GetPredecessors().Size(); ++i) {
+ HBasicBlock* predecessor = try_block->GetPredecessors().Get(i);
+ HTryBoundary* try_boundary = nullptr;
+ if (predecessor->IsSingleTryBoundary()) {
+ try_boundary = predecessor->GetLastInstruction()->AsTryBoundary();
+ if (try_boundary->GetNormalFlowSuccessor() == try_block
+ && try_block->IsFirstIndexOfPredecessor(predecessor, i)) {
+ // The edge was already split because of an exit from a neighbouring
+ // TryItem and `predecessor` is the block with a TryBoundary created
+ // between the two original blocks. We do not split the edge again.
+ DCHECK(!IsBlockInPcRange(predecessor->GetSinglePredecessor(), try_start, try_end));
+ DCHECK(try_boundary->IsTryExit());
+ DCHECK(!try_boundary->IsTryEntry());
+ try_boundary->SetIsTryEntry();
+ } else {
+ // This is an edge between a previously created TryBoundary and its
+ // handler. We skip it because it is exceptional flow.
+ DCHECK(try_block->IsCatchBlock());
+ DCHECK(try_boundary->HasExceptionHandler(try_block));
+ continue;
+ }
+ } else if (!IsBlockInPcRange(predecessor, try_start, try_end)) {
+ // This is an entry point into the TryItem and the edge has not been
+ // split yet. That means that either `predecessor` is not in a TryItem,
+ // or it is in a different TryItem and we happened to iterate over
+ // this block first. We split the edge and `predecessor` may add its
+ // own exception handlers later.
+ try_boundary = new (arena_) HTryBoundary(/* is_entry */ true, /* is_exit */ false);
+ HBasicBlock* try_entry_block = graph_->SplitEdge(predecessor, try_block);
+ try_entry_block->AddInstruction(try_boundary);
+ } else {
+ // Not an edge on the boundary of the try block.
+ continue;
+ }
+ DCHECK(try_boundary != nullptr);
+
+ // Link the TryBoundary block to the handlers of this TryItem.
+ for (CatchHandlerIterator it(code_item, *try_item); it.HasNext(); it.Next()) {
+ try_boundary->AddExceptionHandler(FindBlockStartingAt(it.GetHandlerAddress()));
+ }
+ }
+
+ // Find successors which are not covered by the same TryItem range. Such
+ // edges exit the try block and will have a TryBoundary inserted.
+ for (size_t i = 0; i < try_block->GetSuccessors().Size(); ++i) {
+ HBasicBlock* successor = try_block->GetSuccessors().Get(i);
+ HTryBoundary* try_boundary = nullptr;
+ if (successor->IsSingleTryBoundary()) {
+ // The edge was already split because of an entry into a neighbouring
+ // TryItem. We do not split the edge again.
+ try_boundary = successor->GetLastInstruction()->AsTryBoundary();
+ DCHECK_EQ(try_block, successor->GetSinglePredecessor());
+ DCHECK(try_boundary->IsTryEntry());
+ DCHECK(!try_boundary->IsTryExit());
+ DCHECK(!IsBlockInPcRange(try_boundary->GetNormalFlowSuccessor(), try_start, try_end));
+ try_boundary->SetIsTryExit();
+ } else if (!IsBlockInPcRange(successor, try_start, try_end)) {
+ // This is an exit out of the TryItem and the edge has not been split
+ // yet. That means that either `successor` is not in a TryItem, or it
+ // is in a different TryItem and we happened to iterate over this
+ // block first. We split the edge and `successor` may add its own
+ // exception handlers later.
+ HInstruction* last_instruction = try_block->GetLastInstruction();
+ if (last_instruction->IsReturn() || last_instruction->IsReturnVoid()) {
+ DCHECK_EQ(successor, exit_block_);
+ // Control flow exits the try block with a Return(Void). Because
+ // splitting the edge would invalidate the invariant that Return
+ // always jumps to Exit, we move the Return outside the try block.
+ HBasicBlock* return_block = try_block->SplitBefore(last_instruction);
+ graph_->AddBlock(return_block);
+ successor = return_block;
+ }
+ try_boundary = new (arena_) HTryBoundary(/* is_entry */ false, /* is_exit */ true);
+ HBasicBlock* try_exit_block = graph_->SplitEdge(try_block, successor);
+ try_exit_block->AddInstruction(try_boundary);
+ } else {
+ // Not an edge on the boundary of the try block.
+ continue;
+ }
+ DCHECK(try_boundary != nullptr);
+
+ // Link the TryBoundary block to the handlers of this TryItem.
+ for (CatchHandlerIterator it(code_item, *try_item); it.HasNext(); it.Next()) {
+ try_boundary->AddExceptionHandler(FindBlockStartingAt(it.GetHandlerAddress()));
+ }
+ }
+ }
+ }
+}
+
bool HGraphBuilder::BuildGraph(const DexFile::CodeItem& code_item) {
DCHECK(graph_->GetBlocks().IsEmpty());
@@ -292,24 +451,7 @@
return false;
}
- // Also create blocks for catch handlers.
- if (code_item.tries_size_ != 0) {
- const uint8_t* handlers_ptr = DexFile::GetCatchHandlerData(code_item, 0);
- uint32_t handlers_size = DecodeUnsignedLeb128(&handlers_ptr);
- for (uint32_t idx = 0; idx < handlers_size; ++idx) {
- CatchHandlerIterator iterator(handlers_ptr);
- for (; iterator.HasNext(); iterator.Next()) {
- uint32_t address = iterator.GetHandlerAddress();
- HBasicBlock* block = FindBlockStartingAt(address);
- if (block == nullptr) {
- block = new (arena_) HBasicBlock(graph_, address);
- branch_targets_.Put(address, block);
- }
- block->SetIsCatchBlock();
- }
- handlers_ptr = iterator.EndDataPointer();
- }
- }
+ CreateBlocksForTryCatch(code_item);
InitializeParameters(code_item.ins_size_);
@@ -325,18 +467,24 @@
code_ptr += instruction.SizeInCodeUnits();
}
- // Add the exit block at the end to give it the highest id.
- graph_->AddBlock(exit_block_);
+ // Add Exit to the exit block.
exit_block_->AddInstruction(new (arena_) HExit());
// Add the suspend check to the entry block.
entry_block_->AddInstruction(new (arena_) HSuspendCheck(0));
entry_block_->AddInstruction(new (arena_) HGoto());
+ // Iterate over blocks covered by TryItems and insert TryBoundaries at entry
+ // and exit points. This requires all control-flow instructions and
+ // non-exceptional edges to have been created.
+ InsertTryBoundaryBlocks(code_item);
+
+ // Add the exit block at the end to give it the highest id.
+ graph_->AddBlock(exit_block_);
return true;
}
-void HGraphBuilder::MaybeUpdateCurrentBlock(size_t index) {
- HBasicBlock* block = FindBlockStartingAt(index);
+void HGraphBuilder::MaybeUpdateCurrentBlock(size_t dex_pc) {
+ HBasicBlock* block = FindBlockStartingAt(dex_pc);
if (block == nullptr) {
return;
}
@@ -371,10 +519,8 @@
(*number_of_branches)++;
int32_t target = instruction.GetTargetOffset() + dex_pc;
// Create a block for the target instruction.
- if (FindBlockStartingAt(target) == nullptr) {
- block = new (arena_) HBasicBlock(graph_, target);
- branch_targets_.Put(target, block);
- }
+ FindOrCreateBlockStartingAt(target);
+
dex_pc += instruction.SizeInCodeUnits();
code_ptr += instruction.SizeInCodeUnits();
@@ -383,9 +529,8 @@
// In the normal case we should never hit this but someone can artificially forge a dex
// file to fall-through out the method code. In this case we bail out compilation.
return false;
- } else if (FindBlockStartingAt(dex_pc) == nullptr) {
- block = new (arena_) HBasicBlock(graph_, dex_pc);
- branch_targets_.Put(dex_pc, block);
+ } else {
+ FindOrCreateBlockStartingAt(dex_pc);
}
}
} else if (instruction.IsSwitch()) {
@@ -401,10 +546,7 @@
for (size_t i = 0; i < num_entries; ++i) {
// The target of the case.
uint32_t target = dex_pc + table.GetEntryAt(i + offset);
- if (FindBlockStartingAt(target) == nullptr) {
- block = new (arena_) HBasicBlock(graph_, target);
- branch_targets_.Put(target, block);
- }
+ FindOrCreateBlockStartingAt(target);
// The next case gets its own block.
if (i < num_entries) {
@@ -421,9 +563,8 @@
// file to fall-through out the method code. In this case we bail out compilation.
// (A switch can fall-through so we don't need to check CanFlowThrough().)
return false;
- } else if (FindBlockStartingAt(dex_pc) == nullptr) {
- block = new (arena_) HBasicBlock(graph_, dex_pc);
- branch_targets_.Put(dex_pc, block);
+ } else {
+ FindOrCreateBlockStartingAt(dex_pc);
}
} else {
code_ptr += instruction.SizeInCodeUnits();
@@ -433,9 +574,19 @@
return true;
}
-HBasicBlock* HGraphBuilder::FindBlockStartingAt(int32_t index) const {
- DCHECK_GE(index, 0);
- return branch_targets_.Get(index);
+HBasicBlock* HGraphBuilder::FindBlockStartingAt(int32_t dex_pc) const {
+ DCHECK_GE(dex_pc, 0);
+ DCHECK_LT(static_cast<size_t>(dex_pc), branch_targets_.Size());
+ return branch_targets_.Get(dex_pc);
+}
+
+HBasicBlock* HGraphBuilder::FindOrCreateBlockStartingAt(int32_t dex_pc) {
+ HBasicBlock* block = FindBlockStartingAt(dex_pc);
+ if (block == nullptr) {
+ block = new (arena_) HBasicBlock(graph_, dex_pc);
+ branch_targets_.Put(dex_pc, block);
+ }
+ return block;
}
template<typename T>
@@ -2108,15 +2259,33 @@
case Instruction::MOVE_RESULT:
case Instruction::MOVE_RESULT_WIDE:
- case Instruction::MOVE_RESULT_OBJECT:
+ case Instruction::MOVE_RESULT_OBJECT: {
if (latest_result_ == nullptr) {
// Only dead code can lead to this situation, where the verifier
// does not reject the method.
} else {
- UpdateLocal(instruction.VRegA(), latest_result_);
+ // An Invoke/FilledNewArray and its MoveResult could have landed in
+ // different blocks if there was a try/catch block boundary between
+ // them. For Invoke, we insert a StoreLocal after the instruction. For
+ // FilledNewArray, the local needs to be updated after the array was
+ // filled, otherwise we might overwrite an input vreg.
+ HStoreLocal* update_local =
+ new (arena_) HStoreLocal(GetLocalAt(instruction.VRegA()), latest_result_);
+ HBasicBlock* block = latest_result_->GetBlock();
+ if (block == current_block_) {
+ // MoveResult and the previous instruction are in the same block.
+ current_block_->AddInstruction(update_local);
+ } else {
+ // The two instructions are in different blocks. Insert the MoveResult
+ // before the final control-flow instruction of the previous block.
+ DCHECK(block->EndsWithControlFlowInstruction());
+ DCHECK(current_block_->GetInstructions().IsEmpty());
+ block->InsertInstructionBefore(update_local, block->GetLastInstruction());
+ }
latest_result_ = nullptr;
}
break;
+ }
case Instruction::CMP_LONG: {
Binop_23x_cmp(instruction, Primitive::kPrimLong, HCompare::kNoBias, dex_pc);