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);
diff --git a/compiler/optimizing/builder.h b/compiler/optimizing/builder.h
index 052aaf8..58d85e9 100644
--- a/compiler/optimizing/builder.h
+++ b/compiler/optimizing/builder.h
@@ -94,8 +94,12 @@
bool ComputeBranchTargets(const uint16_t* start,
const uint16_t* end,
size_t* number_of_branches);
- void MaybeUpdateCurrentBlock(size_t index);
- HBasicBlock* FindBlockStartingAt(int32_t index) const;
+ void MaybeUpdateCurrentBlock(size_t dex_pc);
+ HBasicBlock* FindBlockStartingAt(int32_t dex_pc) const;
+ HBasicBlock* FindOrCreateBlockStartingAt(int32_t dex_pc);
+ bool IsBlockInPcRange(HBasicBlock* block, uint32_t dex_pc_start, uint32_t dex_pc_end);
+ void CreateBlocksForTryCatch(const DexFile::CodeItem& code_item);
+ void InsertTryBoundaryBlocks(const DexFile::CodeItem& code_item);
void InitializeLocals(uint16_t count);
HLocal* GetLocalAt(int register_index) const;
diff --git a/compiler/optimizing/code_generator.cc b/compiler/optimizing/code_generator.cc
index cd10935..4607ebe 100644
--- a/compiler/optimizing/code_generator.cc
+++ b/compiler/optimizing/code_generator.cc
@@ -146,7 +146,7 @@
HBasicBlock* CodeGenerator::GetNextBlockToEmit() const {
for (size_t i = current_block_index_ + 1; i < block_order_->Size(); ++i) {
HBasicBlock* block = block_order_->Get(i);
- if (!block->IsSingleGoto()) {
+ if (!block->IsSingleJump()) {
return block;
}
}
@@ -154,7 +154,7 @@
}
HBasicBlock* CodeGenerator::FirstNonEmptyBlock(HBasicBlock* block) const {
- while (block->IsSingleGoto()) {
+ while (block->IsSingleJump()) {
block = block->GetSuccessors().Get(0);
}
return block;
@@ -214,7 +214,7 @@
// Don't generate code for an empty block. Its predecessors will branch to its successor
// directly. Also, the label of that block will not be emitted, so this helps catch
// errors where we reference that label.
- if (block->IsSingleGoto()) continue;
+ if (block->IsSingleJump()) continue;
Bind(block);
for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
HInstruction* current = it.Current();
diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc
index 9abe2e7..ff9373a 100644
--- a/compiler/optimizing/code_generator_arm.cc
+++ b/compiler/optimizing/code_generator_arm.cc
@@ -431,7 +431,7 @@
// FirstNonEmptyBlock() which could lead to adjusting a label more than once.
DCHECK_LT(static_cast<size_t>(block->GetBlockId()), block_labels_.Size());
Label* block_label = &block_labels_.GetRawStorage()[block->GetBlockId()];
- DCHECK_EQ(block_label->IsBound(), !block->IsSingleGoto());
+ DCHECK_EQ(block_label->IsBound(), !block->IsSingleJump());
if (block_label->IsBound()) {
__ AdjustLabelPosition(block_label);
}
@@ -962,12 +962,7 @@
|| !IsLeafMethod());
}
-void LocationsBuilderARM::VisitGoto(HGoto* got) {
- got->SetLocations(nullptr);
-}
-
-void InstructionCodeGeneratorARM::VisitGoto(HGoto* got) {
- HBasicBlock* successor = got->GetSuccessor();
+void InstructionCodeGeneratorARM::HandleGoto(HInstruction* got, HBasicBlock* successor) {
DCHECK(!successor->IsExitBlock());
HBasicBlock* block = got->GetBlock();
@@ -988,6 +983,25 @@
}
}
+void LocationsBuilderARM::VisitGoto(HGoto* got) {
+ got->SetLocations(nullptr);
+}
+
+void InstructionCodeGeneratorARM::VisitGoto(HGoto* got) {
+ HandleGoto(got, got->GetSuccessor());
+}
+
+void LocationsBuilderARM::VisitTryBoundary(HTryBoundary* try_boundary) {
+ try_boundary->SetLocations(nullptr);
+}
+
+void InstructionCodeGeneratorARM::VisitTryBoundary(HTryBoundary* try_boundary) {
+ HBasicBlock* successor = try_boundary->GetNormalFlowSuccessor();
+ if (!successor->IsExitBlock()) {
+ HandleGoto(try_boundary, successor);
+ }
+}
+
void LocationsBuilderARM::VisitExit(HExit* exit) {
exit->SetLocations(nullptr);
}
diff --git a/compiler/optimizing/code_generator_arm.h b/compiler/optimizing/code_generator_arm.h
index 953e733..a96ecbd 100644
--- a/compiler/optimizing/code_generator_arm.h
+++ b/compiler/optimizing/code_generator_arm.h
@@ -211,6 +211,7 @@
void DivRemByPowerOfTwo(HBinaryOperation* instruction);
void GenerateDivRemWithAnyConstant(HBinaryOperation* instruction);
void GenerateDivRemConstantIntegral(HBinaryOperation* instruction);
+ void HandleGoto(HInstruction* got, HBasicBlock* successor);
ArmAssembler* const assembler_;
CodeGeneratorARM* const codegen_;
diff --git a/compiler/optimizing/code_generator_arm64.cc b/compiler/optimizing/code_generator_arm64.cc
index 7ec6b54..9b7124d 100644
--- a/compiler/optimizing/code_generator_arm64.cc
+++ b/compiler/optimizing/code_generator_arm64.cc
@@ -1971,12 +1971,7 @@
// Will be generated at use site.
}
-void LocationsBuilderARM64::VisitGoto(HGoto* got) {
- got->SetLocations(nullptr);
-}
-
-void InstructionCodeGeneratorARM64::VisitGoto(HGoto* got) {
- HBasicBlock* successor = got->GetSuccessor();
+void InstructionCodeGeneratorARM64::HandleGoto(HInstruction* got, HBasicBlock* successor) {
DCHECK(!successor->IsExitBlock());
HBasicBlock* block = got->GetBlock();
HInstruction* previous = got->GetPrevious();
@@ -1995,6 +1990,25 @@
}
}
+void LocationsBuilderARM64::VisitGoto(HGoto* got) {
+ got->SetLocations(nullptr);
+}
+
+void InstructionCodeGeneratorARM64::VisitGoto(HGoto* got) {
+ HandleGoto(got, got->GetSuccessor());
+}
+
+void LocationsBuilderARM64::VisitTryBoundary(HTryBoundary* try_boundary) {
+ try_boundary->SetLocations(nullptr);
+}
+
+void InstructionCodeGeneratorARM64::VisitTryBoundary(HTryBoundary* try_boundary) {
+ HBasicBlock* successor = try_boundary->GetNormalFlowSuccessor();
+ if (!successor->IsExitBlock()) {
+ HandleGoto(try_boundary, successor);
+ }
+}
+
void InstructionCodeGeneratorARM64::GenerateTestAndBranch(HInstruction* instruction,
vixl::Label* true_target,
vixl::Label* false_target,
diff --git a/compiler/optimizing/code_generator_arm64.h b/compiler/optimizing/code_generator_arm64.h
index bbe3adc..2c61038 100644
--- a/compiler/optimizing/code_generator_arm64.h
+++ b/compiler/optimizing/code_generator_arm64.h
@@ -181,7 +181,7 @@
void DivRemByPowerOfTwo(HBinaryOperation* instruction);
void GenerateDivRemWithAnyConstant(HBinaryOperation* instruction);
void GenerateDivRemIntegral(HBinaryOperation* instruction);
-
+ void HandleGoto(HInstruction* got, HBasicBlock* successor);
Arm64Assembler* const assembler_;
CodeGeneratorARM64* const codegen_;
diff --git a/compiler/optimizing/code_generator_mips64.cc b/compiler/optimizing/code_generator_mips64.cc
index ab684d4..aa4fd26 100644
--- a/compiler/optimizing/code_generator_mips64.cc
+++ b/compiler/optimizing/code_generator_mips64.cc
@@ -1938,12 +1938,7 @@
// Will be generated at use site.
}
-void LocationsBuilderMIPS64::VisitGoto(HGoto* got) {
- got->SetLocations(nullptr);
-}
-
-void InstructionCodeGeneratorMIPS64::VisitGoto(HGoto* got) {
- HBasicBlock* successor = got->GetSuccessor();
+void InstructionCodeGeneratorMIPS64::HandleGoto(HInstruction* got, HBasicBlock* successor) {
DCHECK(!successor->IsExitBlock());
HBasicBlock* block = got->GetBlock();
HInstruction* previous = got->GetPrevious();
@@ -1962,6 +1957,25 @@
}
}
+void LocationsBuilderMIPS64::VisitGoto(HGoto* got) {
+ got->SetLocations(nullptr);
+}
+
+void InstructionCodeGeneratorMIPS64::VisitGoto(HGoto* got) {
+ HandleGoto(got, got->GetSuccessor());
+}
+
+void LocationsBuilderMIPS64::VisitTryBoundary(HTryBoundary* try_boundary) {
+ try_boundary->SetLocations(nullptr);
+}
+
+void InstructionCodeGeneratorMIPS64::VisitTryBoundary(HTryBoundary* try_boundary) {
+ HBasicBlock* successor = try_boundary->GetNormalFlowSuccessor();
+ if (!successor->IsExitBlock()) {
+ HandleGoto(try_boundary, successor);
+ }
+}
+
void InstructionCodeGeneratorMIPS64::GenerateTestAndBranch(HInstruction* instruction,
Label* true_target,
Label* false_target,
diff --git a/compiler/optimizing/code_generator_mips64.h b/compiler/optimizing/code_generator_mips64.h
index ec36496..c724a21 100644
--- a/compiler/optimizing/code_generator_mips64.h
+++ b/compiler/optimizing/code_generator_mips64.h
@@ -196,6 +196,7 @@
Label* true_target,
Label* false_target,
Label* always_true_target);
+ void HandleGoto(HInstruction* got, HBasicBlock* successor);
Mips64Assembler* const assembler_;
CodeGeneratorMIPS64* const codegen_;
diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc
index 4d106c4..6c82fe9 100644
--- a/compiler/optimizing/code_generator_x86.cc
+++ b/compiler/optimizing/code_generator_x86.cc
@@ -842,12 +842,7 @@
}
}
-void LocationsBuilderX86::VisitGoto(HGoto* got) {
- got->SetLocations(nullptr);
-}
-
-void InstructionCodeGeneratorX86::VisitGoto(HGoto* got) {
- HBasicBlock* successor = got->GetSuccessor();
+void InstructionCodeGeneratorX86::HandleGoto(HInstruction* got, HBasicBlock* successor) {
DCHECK(!successor->IsExitBlock());
HBasicBlock* block = got->GetBlock();
@@ -867,6 +862,25 @@
}
}
+void LocationsBuilderX86::VisitGoto(HGoto* got) {
+ got->SetLocations(nullptr);
+}
+
+void InstructionCodeGeneratorX86::VisitGoto(HGoto* got) {
+ HandleGoto(got, got->GetSuccessor());
+}
+
+void LocationsBuilderX86::VisitTryBoundary(HTryBoundary* try_boundary) {
+ try_boundary->SetLocations(nullptr);
+}
+
+void InstructionCodeGeneratorX86::VisitTryBoundary(HTryBoundary* try_boundary) {
+ HBasicBlock* successor = try_boundary->GetNormalFlowSuccessor();
+ if (!successor->IsExitBlock()) {
+ HandleGoto(try_boundary, successor);
+ }
+}
+
void LocationsBuilderX86::VisitExit(HExit* exit) {
exit->SetLocations(nullptr);
}
diff --git a/compiler/optimizing/code_generator_x86.h b/compiler/optimizing/code_generator_x86.h
index 1ad89c9..623e832 100644
--- a/compiler/optimizing/code_generator_x86.h
+++ b/compiler/optimizing/code_generator_x86.h
@@ -201,6 +201,7 @@
Label* true_target,
Label* false_target,
Label* always_true_target);
+ void HandleGoto(HInstruction* got, HBasicBlock* successor);
X86Assembler* const assembler_;
CodeGeneratorX86* const codegen_;
diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc
index a8f57cc..22f5d96 100644
--- a/compiler/optimizing/code_generator_x86_64.cc
+++ b/compiler/optimizing/code_generator_x86_64.cc
@@ -786,12 +786,7 @@
}
}
-void LocationsBuilderX86_64::VisitGoto(HGoto* got) {
- got->SetLocations(nullptr);
-}
-
-void InstructionCodeGeneratorX86_64::VisitGoto(HGoto* got) {
- HBasicBlock* successor = got->GetSuccessor();
+void InstructionCodeGeneratorX86_64::HandleGoto(HInstruction* got, HBasicBlock* successor) {
DCHECK(!successor->IsExitBlock());
HBasicBlock* block = got->GetBlock();
@@ -811,6 +806,25 @@
}
}
+void LocationsBuilderX86_64::VisitGoto(HGoto* got) {
+ got->SetLocations(nullptr);
+}
+
+void InstructionCodeGeneratorX86_64::VisitGoto(HGoto* got) {
+ HandleGoto(got, got->GetSuccessor());
+}
+
+void LocationsBuilderX86_64::VisitTryBoundary(HTryBoundary* try_boundary) {
+ try_boundary->SetLocations(nullptr);
+}
+
+void InstructionCodeGeneratorX86_64::VisitTryBoundary(HTryBoundary* try_boundary) {
+ HBasicBlock* successor = try_boundary->GetNormalFlowSuccessor();
+ if (!successor->IsExitBlock()) {
+ HandleGoto(try_boundary, successor);
+ }
+}
+
void LocationsBuilderX86_64::VisitExit(HExit* exit) {
exit->SetLocations(nullptr);
}
diff --git a/compiler/optimizing/code_generator_x86_64.h b/compiler/optimizing/code_generator_x86_64.h
index a18e89a..c2aa56b 100644
--- a/compiler/optimizing/code_generator_x86_64.h
+++ b/compiler/optimizing/code_generator_x86_64.h
@@ -202,6 +202,7 @@
Label* true_target,
Label* false_target,
Label* always_true_target);
+ void HandleGoto(HInstruction* got, HBasicBlock* successor);
X86_64Assembler* const assembler_;
CodeGeneratorX86_64* const codegen_;
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index fd28f0b..d7e6bd8 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -81,7 +81,10 @@
}
// Ensure `block` ends with a branch instruction.
- if (!block->EndsWithControlFlowInstruction()) {
+ // This invariant is not enforced on non-SSA graphs. Graph built from DEX with
+ // dead code that falls out of the method will not end with a control-flow
+ // instruction. Such code is removed during the SSA-building DCE phase.
+ if (GetGraph()->IsInSsaForm() && !block->EndsWithControlFlowInstruction()) {
AddError(StringPrintf("Block %d does not end with a branch instruction.",
block->GetBlockId()));
}
@@ -253,6 +256,22 @@
}
}
+void GraphChecker::VisitReturn(HReturn* ret) {
+ if (!ret->GetBlock()->GetSingleSuccessor()->IsExitBlock()) {
+ AddError(StringPrintf("%s:%d does not jump to the exit block.",
+ ret->DebugName(),
+ ret->GetId()));
+ }
+}
+
+void GraphChecker::VisitReturnVoid(HReturnVoid* ret) {
+ if (!ret->GetBlock()->GetSingleSuccessor()->IsExitBlock()) {
+ AddError(StringPrintf("%s:%d does not jump to the exit block.",
+ ret->DebugName(),
+ ret->GetId()));
+ }
+}
+
void SSAChecker::VisitBasicBlock(HBasicBlock* block) {
super_type::VisitBasicBlock(block);
diff --git a/compiler/optimizing/graph_checker.h b/compiler/optimizing/graph_checker.h
index b4314da..bafa69d 100644
--- a/compiler/optimizing/graph_checker.h
+++ b/compiler/optimizing/graph_checker.h
@@ -48,6 +48,10 @@
// Check that the HasBoundsChecks() flag is set for bounds checks.
void VisitBoundsCheck(HBoundsCheck* check) OVERRIDE;
+ // Check that the Return and ReturnVoid jump to the exit block.
+ void VisitReturn(HReturn* ret) OVERRIDE;
+ void VisitReturnVoid(HReturnVoid* ret) OVERRIDE;
+
// Was the last visit of the graph valid?
bool IsValid() const {
return errors_.empty();
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index 7d723ef..30d61ef 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -252,8 +252,22 @@
AddIndent();
output_ << "successors";
for (size_t i = 0, e = block->GetSuccessors().Size(); i < e; ++i) {
- HBasicBlock* successor = block->GetSuccessors().Get(i);
- output_ << " \"B" << successor->GetBlockId() << "\" ";
+ if (!block->IsExceptionalSuccessor(i)) {
+ HBasicBlock* successor = block->GetSuccessors().Get(i);
+ output_ << " \"B" << successor->GetBlockId() << "\" ";
+ }
+ }
+ output_<< std::endl;
+ }
+
+ void PrintExceptionHandlers(HBasicBlock* block) {
+ AddIndent();
+ output_ << "xhandlers";
+ for (size_t i = 0, e = block->GetSuccessors().Size(); i < e; ++i) {
+ if (block->IsExceptionalSuccessor(i)) {
+ HBasicBlock* handler = block->GetSuccessors().Get(i);
+ output_ << " \"B" << handler->GetBlockId() << "\" ";
+ }
}
if (block->IsExitBlock() &&
(disasm_info_ != nullptr) &&
@@ -365,6 +379,15 @@
<< std::noboolalpha;
}
+ void VisitTryBoundary(HTryBoundary* try_boundary) OVERRIDE {
+ StartAttributeStream("is_entry") << std::boolalpha
+ << try_boundary->IsTryEntry()
+ << std::noboolalpha;
+ StartAttributeStream("is_exit") << std::boolalpha
+ << try_boundary->IsTryExit()
+ << std::noboolalpha;
+ }
+
bool IsPass(const char* name) {
return strcmp(pass_name_, name) == 0;
}
@@ -579,8 +602,14 @@
}
PrintPredecessors(block);
PrintSuccessors(block);
- PrintEmptyProperty("xhandlers");
- PrintEmptyProperty("flags");
+ PrintExceptionHandlers(block);
+
+ if (block->IsCatchBlock()) {
+ PrintProperty("flags", "catch_block");
+ } else {
+ PrintEmptyProperty("flags");
+ }
+
if (block->GetDominator() != nullptr) {
PrintProperty("dominator", "B", block->GetDominator()->GetBlockId());
}
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index a6390af..881f9ec 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -189,15 +189,20 @@
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 @@
}
}
+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 @@
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 {
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 0f5b1ab..f2e9e22 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -39,6 +39,7 @@
class HDoubleConstant;
class HEnvironment;
class HFloatConstant;
+class HGraphBuilder;
class HGraphVisitor;
class HInstruction;
class HIntConstant;
@@ -207,6 +208,12 @@
// Removes `block` from the graph.
void DeleteDeadBlock(HBasicBlock* block);
+ // Splits the edge between `block` and `successor` while preserving the
+ // indices in the predecessor/successor lists. If there are multiple edges
+ // between the blocks, the lowest indices are used.
+ // Returns the new block which is empty and has the same dex pc as `successor`.
+ HBasicBlock* SplitEdge(HBasicBlock* block, HBasicBlock* successor);
+
void SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor);
void SimplifyLoop(HBasicBlock* header);
@@ -566,6 +573,15 @@
}
bool IsSingleGoto() const;
+ bool IsSingleTryBoundary() const;
+
+ // Returns true if this block emits nothing but a jump.
+ bool IsSingleJump() const {
+ HLoopInformation* loop_info = GetLoopInformation();
+ return (IsSingleGoto() || IsSingleTryBoundary())
+ // Back edges generate a suspend check.
+ && (loop_info == nullptr || !loop_info->IsBackEdge(*this));
+ }
void AddBackEdge(HBasicBlock* back_edge) {
if (loop_information_ == nullptr) {
@@ -674,7 +690,7 @@
successors_.Put(1, temp);
}
- size_t GetPredecessorIndexOf(HBasicBlock* predecessor) {
+ size_t GetPredecessorIndexOf(HBasicBlock* predecessor) const {
for (size_t i = 0, e = predecessors_.Size(); i < e; ++i) {
if (predecessors_.Get(i) == predecessor) {
return i;
@@ -683,7 +699,7 @@
return -1;
}
- size_t GetSuccessorIndexOf(HBasicBlock* successor) {
+ size_t GetSuccessorIndexOf(HBasicBlock* successor) const {
for (size_t i = 0, e = successors_.Size(); i < e; ++i) {
if (successors_.Get(i) == successor) {
return i;
@@ -692,6 +708,32 @@
return -1;
}
+ HBasicBlock* GetSinglePredecessor() const {
+ DCHECK_EQ(GetPredecessors().Size(), 1u);
+ return GetPredecessors().Get(0);
+ }
+
+ HBasicBlock* GetSingleSuccessor() const {
+ DCHECK_EQ(GetSuccessors().Size(), 1u);
+ return GetSuccessors().Get(0);
+ }
+
+ // Returns whether the first occurrence of `predecessor` in the list of
+ // predecessors is at index `idx`.
+ bool IsFirstIndexOfPredecessor(HBasicBlock* predecessor, size_t idx) const {
+ DCHECK_EQ(GetPredecessors().Get(idx), predecessor);
+ return GetPredecessorIndexOf(predecessor) == idx;
+ }
+
+ // Returns whether successor at index `idx` is an exception handler.
+ bool IsExceptionalSuccessor(size_t idx) const;
+
+ // Split the block into two blocks just before `cursor`. Returns the newly
+ // created, latter block. Note that this method will create a Goto at the end
+ // of the former block and will create an edge between them. It will not,
+ // however, update the graph, reverse post order or loop information.
+ HBasicBlock* SplitBefore(HInstruction* cursor);
+
// Split the block into two blocks just after `cursor`. Returns the newly
// created block. Note that this method just updates raw block information,
// like predecessors, successors, dominators, and instruction list. It does not
@@ -913,6 +955,7 @@
M(SuspendCheck, Instruction) \
M(Temporary, Instruction) \
M(Throw, Instruction) \
+ M(TryBoundary, Instruction) \
M(TypeConversion, Instruction) \
M(UShr, BinaryOperation) \
M(Xor, BinaryOperation) \
@@ -1858,7 +1901,7 @@
bool IsControlFlow() const OVERRIDE { return true; }
HBasicBlock* GetSuccessor() const {
- return GetBlock()->GetSuccessors().Get(0);
+ return GetBlock()->GetSingleSuccessor();
}
DECLARE_INSTRUCTION(Goto);
@@ -1892,6 +1935,65 @@
DISALLOW_COPY_AND_ASSIGN(HIf);
};
+
+// Abstract instruction which marks the beginning and/or end of a try block and
+// links it to the respective exception handlers. Behaves the same as a Goto in
+// non-exceptional control flow.
+// Normal-flow successor is stored at index zero, exception handlers under
+// higher indices in no particular order.
+class HTryBoundary : public HTemplateInstruction<0> {
+ public:
+ HTryBoundary(bool is_entry, bool is_exit)
+ : HTemplateInstruction(SideEffects::None()), is_entry_(is_entry), is_exit_(is_exit) {}
+
+ bool IsControlFlow() const OVERRIDE { return true; }
+
+ // Returns the block's non-exceptional successor (index zero).
+ HBasicBlock* GetNormalFlowSuccessor() const { return GetBlock()->GetSuccessors().Get(0); }
+
+ // Returns whether `handler` is among its exception handlers (non-zero index
+ // successors).
+ bool HasExceptionHandler(HBasicBlock* handler) const {
+ DCHECK(handler->IsCatchBlock());
+ return GetBlock()->GetSuccessors().Contains(handler, /* start_from */ 1);
+ }
+
+ // Returns whether successor at index `idx` is an exception handler.
+ bool IsExceptionalSuccessor(size_t idx) const {
+ DCHECK_LT(idx, GetBlock()->GetSuccessors().Size());
+ bool is_handler = (idx != 0);
+ DCHECK(!is_handler || GetBlock()->GetSuccessors().Get(idx)->IsCatchBlock());
+ return is_handler;
+ }
+
+ // If not present already, adds `handler` to its block's list of exception
+ // handlers.
+ void AddExceptionHandler(HBasicBlock* handler) {
+ if (!HasExceptionHandler(handler)) {
+ GetBlock()->AddSuccessor(handler);
+ }
+ }
+
+ bool IsTryEntry() const { return is_entry_; }
+ bool IsTryExit() const { return is_exit_; }
+
+ DECLARE_INSTRUCTION(TryBoundary);
+
+ private:
+ // Only for debugging purposes.
+ bool is_entry_;
+ bool is_exit_;
+
+ // Only set by HGraphBuilder.
+ void SetIsTryEntry() { is_entry_ = true; }
+ void SetIsTryExit() { is_exit_ = true; }
+
+ friend HGraphBuilder;
+
+ DISALLOW_COPY_AND_ASSIGN(HTryBoundary);
+};
+
+
// Deoptimize to interpreter, upon checking a condition.
class HDeoptimize : public HTemplateInstruction<1> {
public:
diff --git a/compiler/utils/growable_array.h b/compiler/utils/growable_array.h
index e4b1e7d..f85e026 100644
--- a/compiler/utils/growable_array.h
+++ b/compiler/utils/growable_array.h
@@ -46,8 +46,8 @@
}
}
- bool Contains(T value) const {
- for (size_t i = 0; i < num_used_; ++i) {
+ bool Contains(T value, size_t start_from = 0) const {
+ for (size_t i = start_from; i < num_used_; ++i) {
if (elem_list_[i] == value) {
return true;
}