ART: Build SSA form when try/catch is present
This patch implements support for try/catch in the SsaBuilder.
Values of locals are propagated from throwing sites inside try
blocks to their respective catch blocks and phis ("catch phis")
are created when necessary.
Change-Id: I0736565c2c4ff3f9f0924b6e3a785a50023f875a
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index 9679d0a..cfebb77 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -136,6 +136,33 @@
VisitInstruction(check);
}
+void GraphChecker::VisitTryBoundary(HTryBoundary* try_boundary) {
+ // Ensure that all exception handlers are catch blocks and that handlers
+ // are not listed multiple times.
+ // Note that a normal-flow successor may be a catch block before CFG
+ // simplification. We only test normal-flow successors in SsaChecker.
+ for (HExceptionHandlerIterator it(*try_boundary); !it.Done(); it.Advance()) {
+ HBasicBlock* handler = it.Current();
+ if (!handler->IsCatchBlock()) {
+ AddError(StringPrintf("Block %d with %s:%d has exceptional successor %d which "
+ "is not a catch block.",
+ current_block_->GetBlockId(),
+ try_boundary->DebugName(),
+ try_boundary->GetId(),
+ handler->GetBlockId()));
+ }
+ if (current_block_->GetSuccessors().Contains(
+ handler, /* start_from */ it.CurrentSuccessorIndex() + 1)) {
+ AddError(StringPrintf("Exception handler block %d of %s:%d is listed multiple times.",
+ handler->GetBlockId(),
+ try_boundary->DebugName(),
+ try_boundary->GetId()));
+ }
+ }
+
+ VisitInstruction(try_boundary);
+}
+
void GraphChecker::VisitInstruction(HInstruction* instruction) {
if (seen_ids_.IsBitSet(instruction->GetId())) {
AddError(StringPrintf("Instruction id %d is duplicate in graph.",
@@ -301,11 +328,32 @@
void SSAChecker::VisitBasicBlock(HBasicBlock* block) {
super_type::VisitBasicBlock(block);
+ // Ensure that catch blocks are not normal successors, and normal blocks are
+ // never exceptional successors.
+ const size_t num_normal_successors = block->NumberOfNormalSuccessors();
+ for (size_t j = 0; j < num_normal_successors; ++j) {
+ HBasicBlock* successor = block->GetSuccessors().Get(j);
+ if (successor->IsCatchBlock()) {
+ AddError(StringPrintf("Catch block %d is a normal successor of block %d.",
+ successor->GetBlockId(),
+ block->GetBlockId()));
+ }
+ }
+ for (size_t j = num_normal_successors, e = block->GetSuccessors().Size(); j < e; ++j) {
+ HBasicBlock* successor = block->GetSuccessors().Get(j);
+ if (!successor->IsCatchBlock()) {
+ AddError(StringPrintf("Normal block %d is an exceptional successor of block %d.",
+ successor->GetBlockId(),
+ block->GetBlockId()));
+ }
+ }
+
// Ensure there is no critical edge (i.e., an edge connecting a
// block with multiple successors to a block with multiple
- // predecessors).
- if (block->GetSuccessors().Size() > 1) {
- for (size_t j = 0; j < block->GetSuccessors().Size(); ++j) {
+ // predecessors). Exceptional edges are synthesized and hence
+ // not accounted for.
+ if (block->NumberOfNormalSuccessors() > 1) {
+ for (size_t j = 0, e = block->NumberOfNormalSuccessors(); j < e; ++j) {
HBasicBlock* successor = block->GetSuccessors().Get(j);
if (successor->GetPredecessors().Size() > 1) {
AddError(StringPrintf("Critical edge between blocks %d and %d.",
@@ -326,6 +374,54 @@
}
}
+ // Ensure try membership information is consistent.
+ HTryBoundary* try_entry = block->GetTryEntry();
+ if (block->IsCatchBlock()) {
+ if (try_entry != nullptr) {
+ AddError(StringPrintf("Catch blocks should not be try blocks but catch block %d "
+ "has try entry %s:%d.",
+ block->GetBlockId(),
+ try_entry->DebugName(),
+ try_entry->GetId()));
+ }
+
+ if (block->IsLoopHeader()) {
+ AddError(StringPrintf("Catch blocks should not be loop headers but catch block %d is.",
+ block->GetBlockId()));
+ }
+ } else {
+ for (size_t i = 0; i < block->GetPredecessors().Size(); ++i) {
+ HBasicBlock* predecessor = block->GetPredecessors().Get(i);
+ HTryBoundary* incoming_try_entry = predecessor->ComputeTryEntryOfSuccessors();
+ if (try_entry == nullptr) {
+ if (incoming_try_entry != nullptr) {
+ AddError(StringPrintf("Block %d has no try entry but try entry %s:%d follows "
+ "from predecessor %d.",
+ block->GetBlockId(),
+ incoming_try_entry->DebugName(),
+ incoming_try_entry->GetId(),
+ predecessor->GetBlockId()));
+ }
+ } else if (incoming_try_entry == nullptr) {
+ AddError(StringPrintf("Block %d has try entry %s:%d but no try entry follows "
+ "from predecessor %d.",
+ block->GetBlockId(),
+ try_entry->DebugName(),
+ try_entry->GetId(),
+ predecessor->GetBlockId()));
+ } else if (!incoming_try_entry->HasSameExceptionHandlersAs(*try_entry)) {
+ AddError(StringPrintf("Block %d has try entry %s:%d which is not consistent "
+ "with %s:%d that follows from predecessor %d.",
+ block->GetBlockId(),
+ try_entry->DebugName(),
+ try_entry->GetId(),
+ incoming_try_entry->DebugName(),
+ incoming_try_entry->GetId(),
+ predecessor->GetBlockId()));
+ }
+ }
+ }
+
if (block->IsLoopHeader()) {
CheckLoop(block);
}
@@ -472,32 +568,6 @@
phi->GetBlock()->GetBlockId()));
}
- // Ensure the number of inputs of a phi is the same as the number of
- // its predecessors.
- const GrowableArray<HBasicBlock*>& predecessors =
- phi->GetBlock()->GetPredecessors();
- if (phi->InputCount() != predecessors.Size()) {
- AddError(StringPrintf(
- "Phi %d in block %d has %zu inputs, "
- "but block %d has %zu predecessors.",
- phi->GetId(), phi->GetBlock()->GetBlockId(), phi->InputCount(),
- phi->GetBlock()->GetBlockId(), predecessors.Size()));
- } else {
- // Ensure phi input at index I either comes from the Ith
- // predecessor or from a block that dominates this predecessor.
- for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
- HInstruction* input = phi->InputAt(i);
- HBasicBlock* predecessor = predecessors.Get(i);
- if (!(input->GetBlock() == predecessor
- || input->GetBlock()->Dominates(predecessor))) {
- AddError(StringPrintf(
- "Input %d at index %zu of phi %d from block %d is not defined in "
- "predecessor number %zu nor in a block dominating it.",
- input->GetId(), i, phi->GetId(), phi->GetBlock()->GetBlockId(),
- i));
- }
- }
- }
// Ensure that the inputs have the same primitive kind as the phi.
for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
HInstruction* input = phi->InputAt(i);
@@ -516,6 +586,38 @@
phi->GetBlock()->GetBlockId(),
Primitive::PrettyDescriptor(phi->GetType())));
}
+
+ if (phi->IsCatchPhi()) {
+ // The number of inputs of a catch phi corresponds to the total number of
+ // throwing instructions caught by this catch block.
+ } 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();
+ if (phi->InputCount() != predecessors.Size()) {
+ AddError(StringPrintf(
+ "Phi %d in block %d has %zu inputs, "
+ "but block %d has %zu predecessors.",
+ phi->GetId(), phi->GetBlock()->GetBlockId(), phi->InputCount(),
+ phi->GetBlock()->GetBlockId(), predecessors.Size()));
+ } else {
+ // Ensure phi input at index I either comes from the Ith
+ // predecessor or from a block that dominates this predecessor.
+ for (size_t i = 0, e = phi->InputCount(); i < e; ++i) {
+ HInstruction* input = phi->InputAt(i);
+ HBasicBlock* predecessor = predecessors.Get(i);
+ if (!(input->GetBlock() == predecessor
+ || input->GetBlock()->Dominates(predecessor))) {
+ AddError(StringPrintf(
+ "Input %d at index %zu of phi %d from block %d is not defined in "
+ "predecessor number %zu nor in a block dominating it.",
+ input->GetId(), i, phi->GetId(), phi->GetBlock()->GetBlockId(),
+ i));
+ }
+ }
+ }
+ }
}
void SSAChecker::HandleBooleanInput(HInstruction* instruction, size_t input_index) {
diff --git a/compiler/optimizing/graph_checker.h b/compiler/optimizing/graph_checker.h
index 7c72e23..0e270db 100644
--- a/compiler/optimizing/graph_checker.h
+++ b/compiler/optimizing/graph_checker.h
@@ -48,6 +48,9 @@
// Check that the HasBoundsChecks() flag is set for bounds checks.
void VisitBoundsCheck(HBoundsCheck* check) OVERRIDE;
+ // Check successors of blocks ending in TryBoundary.
+ void VisitTryBoundary(HTryBoundary* try_boundary) OVERRIDE;
+
// Check that HCheckCast and HInstanceOf have HLoadClass as second input.
void VisitCheckCast(HCheckCast* check) OVERRIDE;
void VisitInstanceOf(HInstanceOf* check) OVERRIDE;
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index 37c060c..afea403 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -158,12 +158,14 @@
std::ostream& output,
const char* pass_name,
bool is_after_pass,
+ bool graph_in_bad_state,
const CodeGenerator& codegen,
const DisassemblyInformation* disasm_info = nullptr)
: HGraphDelegateVisitor(graph),
output_(output),
pass_name_(pass_name),
is_after_pass_(is_after_pass),
+ graph_in_bad_state_(graph_in_bad_state),
codegen_(codegen),
disasm_info_(disasm_info),
disassembler_(disasm_info_ != nullptr
@@ -251,11 +253,9 @@
void PrintSuccessors(HBasicBlock* block) {
AddIndent();
output_ << "successors";
- for (size_t i = 0, e = block->GetSuccessors().Size(); i < e; ++i) {
- if (!block->IsExceptionalSuccessor(i)) {
- HBasicBlock* successor = block->GetSuccessors().Get(i);
- output_ << " \"B" << successor->GetBlockId() << "\" ";
- }
+ for (size_t i = 0; i < block->NumberOfNormalSuccessors(); ++i) {
+ HBasicBlock* successor = block->GetSuccessors().Get(i);
+ output_ << " \"B" << successor->GetBlockId() << "\" ";
}
output_<< std::endl;
}
@@ -263,11 +263,9 @@
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() << "\" ";
- }
+ for (size_t i = block->NumberOfNormalSuccessors(); i < block->GetSuccessors().Size(); ++i) {
+ HBasicBlock* handler = block->GetSuccessors().Get(i);
+ output_ << " \"B" << handler->GetBlockId() << "\" ";
}
if (block->IsExitBlock() &&
(disasm_info_ != nullptr) &&
@@ -351,6 +349,7 @@
void VisitPhi(HPhi* phi) OVERRIDE {
StartAttributeStream("reg") << phi->GetRegNumber();
+ StartAttributeStream("is_catch_phi") << std::boolalpha << phi->IsCatchPhi() << std::noboolalpha;
}
void VisitMemoryBarrier(HMemoryBarrier* barrier) OVERRIDE {
@@ -582,7 +581,11 @@
void Run() {
StartTag("cfg");
- std::string pass_desc = std::string(pass_name_) + (is_after_pass_ ? " (after)" : " (before)");
+ std::string pass_desc = std::string(pass_name_)
+ + " ("
+ + (is_after_pass_ ? "after" : "before")
+ + (graph_in_bad_state_ ? ", bad_state" : "")
+ + ")";
PrintProperty("name", pass_desc.c_str());
if (disasm_info_ != nullptr) {
DumpDisassemblyBlockForFrameEntry();
@@ -651,6 +654,7 @@
std::ostream& output_;
const char* pass_name_;
const bool is_after_pass_;
+ const bool graph_in_bad_state_;
const CodeGenerator& codegen_;
const DisassemblyInformation* disasm_info_;
std::unique_ptr<HGraphVisualizerDisassembler> disassembler_;
@@ -666,7 +670,7 @@
void HGraphVisualizer::PrintHeader(const char* method_name) const {
DCHECK(output_ != nullptr);
- HGraphVisualizerPrinter printer(graph_, *output_, "", true, codegen_);
+ HGraphVisualizerPrinter printer(graph_, *output_, "", true, false, codegen_);
printer.StartTag("compilation");
printer.PrintProperty("name", method_name);
printer.PrintProperty("method", method_name);
@@ -674,10 +678,17 @@
printer.EndTag("compilation");
}
-void HGraphVisualizer::DumpGraph(const char* pass_name, bool is_after_pass) const {
+void HGraphVisualizer::DumpGraph(const char* pass_name,
+ bool is_after_pass,
+ bool graph_in_bad_state) const {
DCHECK(output_ != nullptr);
if (!graph_->GetBlocks().IsEmpty()) {
- HGraphVisualizerPrinter printer(graph_, *output_, pass_name, is_after_pass, codegen_);
+ HGraphVisualizerPrinter printer(graph_,
+ *output_,
+ pass_name,
+ is_after_pass,
+ graph_in_bad_state,
+ codegen_);
printer.Run();
}
}
@@ -685,8 +696,13 @@
void HGraphVisualizer::DumpGraphWithDisassembly() const {
DCHECK(output_ != nullptr);
if (!graph_->GetBlocks().IsEmpty()) {
- HGraphVisualizerPrinter printer(
- graph_, *output_, "disassembly", true, codegen_, codegen_.GetDisassemblyInformation());
+ HGraphVisualizerPrinter printer(graph_,
+ *output_,
+ "disassembly",
+ /* is_after_pass */ true,
+ /* graph_in_bad_state */ false,
+ codegen_,
+ codegen_.GetDisassemblyInformation());
printer.Run();
}
}
diff --git a/compiler/optimizing/graph_visualizer.h b/compiler/optimizing/graph_visualizer.h
index b6b66df..66588f6 100644
--- a/compiler/optimizing/graph_visualizer.h
+++ b/compiler/optimizing/graph_visualizer.h
@@ -104,7 +104,7 @@
const CodeGenerator& codegen);
void PrintHeader(const char* method_name) const;
- void DumpGraph(const char* pass_name, bool is_after_pass = true) const;
+ void DumpGraph(const char* pass_name, bool is_after_pass, bool graph_in_bad_state) const;
void DumpGraphWithDisassembly() const;
private:
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 588ab70..519fa00 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -98,26 +98,31 @@
}
void HGraph::BuildDominatorTree() {
+ // (1) Simplify the CFG so that catch blocks have only exceptional incoming
+ // edges. This invariant simplifies building SSA form because Phis cannot
+ // collect both normal- and exceptional-flow values at the same time.
+ SimplifyCatchBlocks();
+
ArenaBitVector visited(arena_, blocks_.Size(), false);
- // (1) Find the back edges in the graph doing a DFS traversal.
+ // (2) Find the back edges in the graph doing a DFS traversal.
FindBackEdges(&visited);
- // (2) Remove instructions and phis from blocks not visited during
+ // (3) Remove instructions and phis from blocks not visited during
// the initial DFS as users from other instructions, so that
// users can be safely removed before uses later.
RemoveInstructionsAsUsersFromDeadBlocks(visited);
- // (3) Remove blocks not visited during the initial DFS.
+ // (4) Remove blocks not visited during the initial DFS.
// Step (4) requires dead blocks to be removed from the
// predecessors list of live blocks.
RemoveDeadBlocks(visited);
- // (4) Simplify the CFG now, so that we don't need to recompute
+ // (5) Simplify the CFG now, so that we don't need to recompute
// dominators and the reverse post order.
SimplifyCFG();
- // (5) Compute the dominance information and the reverse post order.
+ // (6) Compute the dominance information and the reverse post order.
ComputeDominanceInformation();
}
@@ -261,6 +266,83 @@
info->SetSuspendCheck(first_instruction->AsSuspendCheck());
}
+static bool CheckIfPredecessorAtIsExceptional(const HBasicBlock& block, size_t pred_idx) {
+ HBasicBlock* predecessor = block.GetPredecessors().Get(pred_idx);
+ if (!predecessor->EndsWithTryBoundary()) {
+ // Only edges from HTryBoundary can be exceptional.
+ return false;
+ }
+ HTryBoundary* try_boundary = predecessor->GetLastInstruction()->AsTryBoundary();
+ if (try_boundary->GetNormalFlowSuccessor() == &block) {
+ // This block is the normal-flow successor of `try_boundary`, but it could
+ // also be one of its exception handlers if catch blocks have not been
+ // simplified yet. Predecessors are unordered, so we will consider the first
+ // occurrence to be the normal edge and a possible second occurrence to be
+ // the exceptional edge.
+ return !block.IsFirstIndexOfPredecessor(predecessor, pred_idx);
+ } else {
+ // This is not the normal-flow successor of `try_boundary`, hence it must be
+ // one of its exception handlers.
+ DCHECK(try_boundary->HasExceptionHandler(block));
+ return true;
+ }
+}
+
+void HGraph::SimplifyCatchBlocks() {
+ for (size_t i = 0; i < blocks_.Size(); ++i) {
+ HBasicBlock* catch_block = blocks_.Get(i);
+ if (!catch_block->IsCatchBlock()) {
+ continue;
+ }
+
+ bool exceptional_predecessors_only = true;
+ for (size_t j = 0; j < catch_block->GetPredecessors().Size(); ++j) {
+ if (!CheckIfPredecessorAtIsExceptional(*catch_block, j)) {
+ exceptional_predecessors_only = false;
+ break;
+ }
+ }
+
+ if (!exceptional_predecessors_only) {
+ // Catch block has normal-flow predecessors and needs to be simplified.
+ // Splitting the block before its first instruction moves all its
+ // instructions into `normal_block` and links the two blocks with a Goto.
+ // Afterwards, incoming normal-flow edges are re-linked to `normal_block`,
+ // leaving `catch_block` with the exceptional edges only.
+ // Note that catch blocks with normal-flow predecessors cannot begin with
+ // a MOVE_EXCEPTION instruction, as guaranteed by the verifier.
+ DCHECK(!catch_block->GetFirstInstruction()->IsLoadException());
+ HBasicBlock* normal_block = catch_block->SplitBefore(catch_block->GetFirstInstruction());
+ for (size_t j = 0; j < catch_block->GetPredecessors().Size(); ++j) {
+ if (!CheckIfPredecessorAtIsExceptional(*catch_block, j)) {
+ catch_block->GetPredecessors().Get(j)->ReplaceSuccessor(catch_block, normal_block);
+ --j;
+ }
+ }
+ }
+ }
+}
+
+void HGraph::ComputeTryBlockInformation() {
+ // Iterate in reverse post order to propagate try membership information from
+ // predecessors to their successors.
+ for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
+ HBasicBlock* block = it.Current();
+ if (block->IsEntryBlock() || block->IsCatchBlock()) {
+ // Catch blocks after simplification have only exceptional predecessors
+ // and hence are never in tries.
+ continue;
+ }
+
+ // Infer try membership from the first predecessor. Having simplified loops,
+ // the first predecessor can never be a back edge and therefore it must have
+ // been visited already and had its try membership set.
+ HBasicBlock* first_predecessor = block->GetPredecessors().Get(0);
+ DCHECK(!block->IsLoopHeader() || !block->GetLoopInformation()->IsBackEdge(*first_predecessor));
+ block->SetTryEntry(first_predecessor->ComputeTryEntryOfSuccessors());
+ }
+}
+
void HGraph::SimplifyCFG() {
// Simplify the CFG for future analysis, and code generation:
// (1): Split critical edges.
@@ -268,9 +350,10 @@
for (size_t i = 0; i < blocks_.Size(); ++i) {
HBasicBlock* block = blocks_.Get(i);
if (block == nullptr) continue;
- if (block->GetSuccessors().Size() > 1) {
+ if (block->NumberOfNormalSuccessors() > 1) {
for (size_t j = 0; j < block->GetSuccessors().Size(); ++j) {
HBasicBlock* successor = block->GetSuccessors().Get(j);
+ DCHECK(!successor->IsCatchBlock());
if (successor->GetPredecessors().Size() > 1) {
SplitCriticalEdge(block, successor);
--j;
@@ -288,6 +371,11 @@
for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
HBasicBlock* block = it.Current();
if (block->IsLoopHeader()) {
+ if (block->IsCatchBlock()) {
+ // TODO: Dealing with exceptional back edges could be tricky because
+ // they only approximate the real control flow. Bail out for now.
+ return false;
+ }
HLoopInformation* info = block->GetLoopInformation();
if (!info->Populate()) {
// Abort if the loop is non natural. We currently bailout in such cases.
@@ -1086,10 +1174,20 @@
return new_block;
}
-bool HBasicBlock::IsExceptionalSuccessor(size_t idx) const {
- return !GetInstructions().IsEmpty()
- && GetLastInstruction()->IsTryBoundary()
- && GetLastInstruction()->AsTryBoundary()->IsExceptionalSuccessor(idx);
+HTryBoundary* HBasicBlock::ComputeTryEntryOfSuccessors() const {
+ if (EndsWithTryBoundary()) {
+ HTryBoundary* try_boundary = GetLastInstruction()->AsTryBoundary();
+ if (try_boundary->IsEntry()) {
+ DCHECK(try_entry_ == nullptr);
+ return try_boundary;
+ } else {
+ DCHECK(try_entry_ != nullptr);
+ DCHECK(try_entry_->HasSameExceptionHandlersAs(*try_boundary));
+ return nullptr;
+ }
+ } else {
+ return try_entry_;
+ }
}
static bool HasOnlyOneInstruction(const HBasicBlock& block) {
@@ -1114,10 +1212,29 @@
return !GetInstructions().IsEmpty() && GetLastInstruction()->IsIf();
}
+bool HBasicBlock::EndsWithTryBoundary() const {
+ return !GetInstructions().IsEmpty() && GetLastInstruction()->IsTryBoundary();
+}
+
bool HBasicBlock::HasSinglePhi() const {
return !GetPhis().IsEmpty() && GetFirstPhi()->GetNext() == nullptr;
}
+bool HTryBoundary::HasSameExceptionHandlersAs(const HTryBoundary& other) const {
+ if (GetBlock()->GetSuccessors().Size() != other.GetBlock()->GetSuccessors().Size()) {
+ 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())) {
+ return false;
+ }
+ }
+ return true;
+}
+
size_t HInstructionList::CountSize() const {
size_t size = 0;
HInstruction* current = first_instruction_;
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 8546a10..fd2a04d 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -49,6 +49,7 @@
class HNullConstant;
class HPhi;
class HSuspendCheck;
+class HTryBoundary;
class LiveInterval;
class LocationSummary;
class SlowPathCode;
@@ -182,6 +183,10 @@
// visit for eliminating dead phis: a dead phi can only have loop header phi
// users remaining when being visited.
if (!AnalyzeNaturalLoops()) return false;
+ // Precompute per-block try membership before entering the SSA builder,
+ // which needs the information to build catch block phis from values of
+ // locals at throwing instructions inside try blocks.
+ ComputeTryBlockInformation();
TransformToSsa();
in_ssa_form_ = true;
return true;
@@ -193,12 +198,17 @@
void BuildDominatorTree();
void TransformToSsa();
void SimplifyCFG();
+ void SimplifyCatchBlocks();
// Analyze all natural loops in this graph. Returns false if one
// loop is not natural, that is the header does not dominate the
// back edge.
bool AnalyzeNaturalLoops() const;
+ // Iterate over blocks to compute try block membership. Needs reverse post
+ // order and loop information.
+ void ComputeTryBlockInformation();
+
// Inline this graph in `outer_graph`, replacing the given `invoke` instruction.
void InlineInto(HGraph* outer_graph, HInvoke* invoke);
@@ -730,8 +740,11 @@
return GetPredecessorIndexOf(predecessor) == idx;
}
- // Returns whether successor at index `idx` is an exception handler.
- bool IsExceptionalSuccessor(size_t idx) const;
+ // Returns the number of non-exceptional successors. SsaChecker ensures that
+ // these are stored at the beginning of the successor list.
+ size_t NumberOfNormalSuccessors() const {
+ return EndsWithTryBoundary() ? 1 : GetSuccessors().Size();
+ }
// Split the block into two blocks just before `cursor`. Returns the newly
// created, latter block. Note that this method will add the block to the
@@ -830,6 +843,15 @@
bool IsInLoop() const { return loop_information_ != nullptr; }
+ HTryBoundary* GetTryEntry() const { return try_entry_; }
+ void SetTryEntry(HTryBoundary* try_entry) { try_entry_ = try_entry; }
+ bool IsInTry() const { return try_entry_ != nullptr; }
+
+ // Returns the try entry that this block's successors should have. They will
+ // be in the same try, unless the block ends in a try boundary. In that case,
+ // the appropriate try entry will be returned.
+ HTryBoundary* ComputeTryEntryOfSuccessors() const;
+
// Returns whether this block dominates the blocked passed as parameter.
bool Dominates(HBasicBlock* block) const;
@@ -846,6 +868,7 @@
bool EndsWithControlFlowInstruction() const;
bool EndsWithIf() const;
+ bool EndsWithTryBoundary() const;
bool HasSinglePhi() const;
private:
@@ -864,6 +887,10 @@
size_t lifetime_end_;
bool is_catch_block_;
+ // If this block is in a try block, `try_entry_` stores one of, possibly
+ // several, TryBoundary instructions entering it.
+ HTryBoundary* try_entry_;
+
friend class HGraph;
friend class HInstruction;
@@ -1975,29 +2002,24 @@
// 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;
+ bool HasExceptionHandler(const HBasicBlock& handler) const {
+ DCHECK(handler.IsCatchBlock());
+ return GetBlock()->GetSuccessors().Contains(
+ const_cast<HBasicBlock*>(&handler), /* start_from */ 1);
}
// If not present already, adds `handler` to its block's list of exception
// handlers.
void AddExceptionHandler(HBasicBlock* handler) {
- if (!HasExceptionHandler(handler)) {
+ if (!HasExceptionHandler(*handler)) {
GetBlock()->AddSuccessor(handler);
}
}
bool IsEntry() const { return kind_ == BoundaryKind::kEntry; }
+ bool HasSameExceptionHandlersAs(const HTryBoundary& other) const;
+
DECLARE_INSTRUCTION(TryBoundary);
private:
@@ -2006,6 +2028,24 @@
DISALLOW_COPY_AND_ASSIGN(HTryBoundary);
};
+// Iterator over exception handlers of a given HTryBoundary, i.e. over
+// exceptional successors of its basic block.
+class HExceptionHandlerIterator : public ValueObject {
+ public:
+ explicit HExceptionHandlerIterator(const HTryBoundary& try_boundary)
+ : block_(*try_boundary.GetBlock()), index_(block_.NumberOfNormalSuccessors()) {}
+
+ bool Done() const { return index_ == block_.GetSuccessors().Size(); }
+ HBasicBlock* Current() const { return block_.GetSuccessors().Get(index_); }
+ size_t CurrentSuccessorIndex() const { return index_; }
+ void Advance() { ++index_; }
+
+ private:
+ const HBasicBlock& block_;
+ size_t index_;
+
+ DISALLOW_COPY_AND_ASSIGN(HExceptionHandlerIterator);
+};
// Deoptimize to interpreter, upon checking a condition.
class HDeoptimize : public HTemplateInstruction<1> {
@@ -3367,6 +3407,8 @@
}
}
+ bool IsCatchPhi() const { return GetBlock()->IsCatchBlock(); }
+
size_t InputCount() const OVERRIDE { return inputs_.Size(); }
void AddInput(HInstruction* input);
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 4568a46..aeb1ae2 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -132,7 +132,7 @@
void StartPass(const char* pass_name) {
// Dump graph first, then start timer.
if (visualizer_enabled_) {
- visualizer_.DumpGraph(pass_name, /* is_after_pass */ false);
+ visualizer_.DumpGraph(pass_name, /* is_after_pass */ false, graph_in_bad_state_);
}
if (timing_logger_enabled_) {
timing_logger_.StartTiming(pass_name);
@@ -145,7 +145,7 @@
timing_logger_.EndTiming();
}
if (visualizer_enabled_) {
- visualizer_.DumpGraph(pass_name, /* is_after_pass */ true);
+ visualizer_.DumpGraph(pass_name, /* is_after_pass */ true, graph_in_bad_state_);
}
// Validate the HGraph if running in debug mode.
@@ -628,7 +628,7 @@
// or the debuggable flag). If it is set, we can run baseline. Otherwise, we fall back
// to Quick.
bool can_use_baseline = !run_optimizations_ && builder.CanUseBaselineForStringInit();
- if (run_optimizations_ && can_optimize && can_allocate_registers) {
+ if (run_optimizations_ && can_allocate_registers) {
VLOG(compiler) << "Optimizing " << method_name;
{
@@ -637,16 +637,21 @@
// We could not transform the graph to SSA, bailout.
LOG(INFO) << "Skipping compilation of " << method_name << ": it contains a non natural loop";
MaybeRecordStat(MethodCompilationStat::kNotCompiledCannotBuildSSA);
+ pass_observer.SetGraphInBadState();
return nullptr;
}
}
- return CompileOptimized(graph,
- codegen.get(),
- compiler_driver,
- dex_compilation_unit,
- &pass_observer);
- } else if (shouldOptimize && can_allocate_registers) {
+ if (can_optimize) {
+ return CompileOptimized(graph,
+ codegen.get(),
+ compiler_driver,
+ dex_compilation_unit,
+ &pass_observer);
+ }
+ }
+
+ if (shouldOptimize && can_allocate_registers) {
LOG(FATAL) << "Could not allocate registers in optimizing compiler";
UNREACHABLE();
} else if (can_use_baseline) {
diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc
index c37b199..ff2e6ad 100644
--- a/compiler/optimizing/ssa_builder.cc
+++ b/compiler/optimizing/ssa_builder.cc
@@ -350,7 +350,9 @@
void SsaBuilder::VisitBasicBlock(HBasicBlock* block) {
current_locals_ = GetLocalsFor(block);
- if (block->IsLoopHeader()) {
+ if (block->IsCatchBlock()) {
+ // Catch phis were already created and inputs collected from throwing sites.
+ } else if (block->IsLoopHeader()) {
// If the block is a loop header, we know we only have visited the pre header
// because we are visiting in reverse post order. We create phis for all initialized
// locals from the pre header. Their inputs will be populated at the end of
@@ -551,19 +553,32 @@
}
void SsaBuilder::VisitInstruction(HInstruction* instruction) {
- if (!instruction->NeedsEnvironment()) {
- return;
+ if (instruction->NeedsEnvironment()) {
+ HEnvironment* environment = new (GetGraph()->GetArena()) HEnvironment(
+ GetGraph()->GetArena(),
+ current_locals_->Size(),
+ GetGraph()->GetDexFile(),
+ GetGraph()->GetMethodIdx(),
+ instruction->GetDexPc(),
+ GetGraph()->GetInvokeType(),
+ instruction);
+ environment->CopyFrom(*current_locals_);
+ instruction->SetRawEnvironment(environment);
}
- HEnvironment* environment = new (GetGraph()->GetArena()) HEnvironment(
- GetGraph()->GetArena(),
- current_locals_->Size(),
- GetGraph()->GetDexFile(),
- GetGraph()->GetMethodIdx(),
- instruction->GetDexPc(),
- GetGraph()->GetInvokeType(),
- instruction);
- environment->CopyFrom(*current_locals_);
- instruction->SetRawEnvironment(environment);
+
+ // If in a try block, propagate values of locals into catch blocks.
+ 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());
+ for (size_t i = 0, e = current_locals_->Size(); i < e; ++i) {
+ HInstruction* local_value = current_locals_->Get(i);
+ if (local_value != nullptr) {
+ handler_locals->Get(i)->AsPhi()->AddInput(local_value);
+ }
+ }
+ }
+ }
}
void SsaBuilder::VisitTemporary(HTemporary* temp) {
diff --git a/compiler/optimizing/ssa_builder.h b/compiler/optimizing/ssa_builder.h
index 1c83c4b..64600db 100644
--- a/compiler/optimizing/ssa_builder.h
+++ b/compiler/optimizing/ssa_builder.h
@@ -61,9 +61,22 @@
GrowableArray<HInstruction*>* GetLocalsFor(HBasicBlock* block) {
GrowableArray<HInstruction*>* locals = locals_for_.Get(block->GetBlockId());
if (locals == nullptr) {
- locals = new (GetGraph()->GetArena()) GrowableArray<HInstruction*>(
- GetGraph()->GetArena(), GetGraph()->GetNumberOfVRegs());
- locals->SetSize(GetGraph()->GetNumberOfVRegs());
+ const size_t vregs = GetGraph()->GetNumberOfVRegs();
+ ArenaAllocator* arena = GetGraph()->GetArena();
+ locals = new (arena) GrowableArray<HInstruction*>(arena, vregs);
+ locals->SetSize(vregs);
+
+ if (block->IsCatchBlock()) {
+ // We record incoming inputs of catch phis at throwing instructions and
+ // must therefore eagerly create the phis. Unused phis will be removed
+ // in the dead phi analysis.
+ for (size_t i = 0; i < vregs; ++i) {
+ HPhi* phi = new (arena) HPhi(arena, i, 0, Primitive::kPrimVoid);
+ block->AddPhi(phi);
+ locals->Put(i, phi);
+ }
+ }
+
locals_for_.Put(block->GetBlockId(), locals);
}
return locals;
diff --git a/compiler/optimizing/ssa_phi_elimination.cc b/compiler/optimizing/ssa_phi_elimination.cc
index 2f2e2d1..917341a 100644
--- a/compiler/optimizing/ssa_phi_elimination.cc
+++ b/compiler/optimizing/ssa_phi_elimination.cc
@@ -114,6 +114,12 @@
continue;
}
+ if (phi->InputCount() == 0) {
+ DCHECK(phi->IsCatchPhi());
+ DCHECK(phi->IsDead());
+ continue;
+ }
+
// Find if the inputs of the phi are the same instruction.
HInstruction* candidate = phi->InputAt(0);
// A loop phi cannot have itself as the first phi. Note that this
@@ -137,6 +143,11 @@
continue;
}
+ // The candidate may not dominate a phi in a catch block.
+ if (phi->IsCatchPhi() && !candidate->StrictlyDominates(phi)) {
+ continue;
+ }
+
if (phi->IsInLoop()) {
// Because we're updating the users of this phi, we may have new
// phis candidate for elimination if this phi is in a loop. Add phis that
diff --git a/test/510-checker-try-catch/smali/SsaBuilder.smali b/test/510-checker-try-catch/smali/SsaBuilder.smali
new file mode 100644
index 0000000..2ddcbce
--- /dev/null
+++ b/test/510-checker-try-catch/smali/SsaBuilder.smali
@@ -0,0 +1,199 @@
+# Copyright (C) 2015 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+.class public LSsaBuilder;
+
+.super Ljava/lang/Object;
+
+# Tests that catch blocks with both normal and exceptional predecessors are
+# split in two.
+
+## CHECK-START: int SsaBuilder.testSimplifyCatchBlock(int, int, int) ssa_builder (after)
+
+## CHECK: name "B0"
+## CHECK-NEXT: from_bci
+## CHECK-NEXT: to_bci
+## CHECK-NEXT: predecessors
+## CHECK-NEXT: successors "<<BExtracted:B\d+>>"
+
+## CHECK: name "<<BCatch:B\d+>>"
+## CHECK-NEXT: from_bci
+## CHECK-NEXT: to_bci
+## CHECK-NEXT: predecessors
+## CHECK-NEXT: successors "<<BExtracted>>"
+## CHECK-NEXT: xhandlers
+## CHECK-NEXT: flags "catch_block"
+## CHECK-NOT: Add
+
+## CHECK: name "<<BExtracted>>"
+## CHECK-NEXT: from_bci
+## CHECK-NEXT: to_bci
+## CHECK-NEXT: predecessors "B0" "<<BCatch>>"
+## CHECK-NOT: flags "catch_block"
+## CHECK: Add
+
+.method public static testSimplifyCatchBlock(III)I
+ .registers 4
+
+ :catch_all
+ add-int/2addr p0, p1
+
+ :try_start
+ div-int/2addr p0, p2
+ :try_end
+ .catchall {:try_start .. :try_end} :catch_all
+
+ return p0
+.end method
+
+# Should be rejected because :catch_all is a loop header.
+
+## CHECK-START: int SsaBuilder.testCatchLoopHeader(int, int, int) ssa_builder (after, bad_state)
+
+.method public static testCatchLoopHeader(III)I
+ .registers 4
+
+ :try_start_1
+ div-int/2addr p0, p1
+ return p0
+ :try_end_1
+ .catchall {:try_start_1 .. :try_end_1} :catch_all
+
+ :catch_all
+ :try_start_2
+ div-int/2addr p0, p2
+ return p0
+ :try_end_2
+ .catchall {:try_start_2 .. :try_end_2} :catch_all
+
+.end method
+
+# Tests creation of catch Phis.
+
+## CHECK-START: int SsaBuilder.testPhiCreation(int, int, int) ssa_builder (after)
+## CHECK-DAG: <<P0:i\d+>> ParameterValue
+## CHECK-DAG: <<P1:i\d+>> ParameterValue
+## CHECK-DAG: <<P2:i\d+>> ParameterValue
+
+## CHECK-DAG: <<DZC1:i\d+>> DivZeroCheck [<<P1>>]
+## CHECK-DAG: <<Div1:i\d+>> Div [<<P0>>,<<DZC1>>]
+## CHECK-DAG: <<DZC2:i\d+>> DivZeroCheck [<<P1>>]
+## CHECK-DAG: <<Div2:i\d+>> Div [<<Div1>>,<<DZC2>>]
+## CHECK-DAG: <<DZC3:i\d+>> DivZeroCheck [<<P1>>]
+## CHECK-DAG: <<Div3:i\d+>> Div [<<Div2>>,<<DZC3>>]
+
+## CHECK-DAG: <<Phi1:i\d+>> Phi [<<P0>>,<<P1>>,<<P2>>] reg:0 is_catch_phi:true
+## CHECK-DAG: <<Phi2:i\d+>> Phi [<<Div3>>,<<Phi1>>] reg:0 is_catch_phi:false
+## CHECK-DAG: Return [<<Phi2>>]
+
+.method public static testPhiCreation(III)I
+ .registers 4
+
+ :try_start
+ move v0, p0
+ div-int/2addr p0, p1
+
+ move v0, p1
+ div-int/2addr p0, p1
+
+ move v0, p2
+ div-int/2addr p0, p1
+
+ move v0, p0
+ :try_end
+ .catchall {:try_start .. :try_end} :catch_all
+
+ :return
+ return v0
+
+ :catch_all
+ goto :return
+.end method
+
+# Tests that phi elimination does not remove catch phis where the value does
+# not dominate the phi.
+
+## CHECK-START: int SsaBuilder.testPhiElimination(int, int) ssa_builder (after)
+## CHECK-DAG: <<P0:i\d+>> ParameterValue
+## CHECK-DAG: <<P1:i\d+>> ParameterValue
+## CHECK-DAG: <<Cst5:i\d+>> IntConstant 5
+## CHECK-DAG: <<Cst7:i\d+>> IntConstant 7
+
+## CHECK-DAG: <<Add1:i\d+>> Add [<<Cst7>>,<<Cst7>>]
+## CHECK-DAG: <<DZC:i\d+>> DivZeroCheck [<<P1>>]
+## CHECK-DAG: <<Div:i\d+>> Div [<<P0>>,<<DZC>>]
+
+## CHECK-DAG: <<Phi1:i\d+>> Phi [<<Add1>>] reg:1 is_catch_phi:true
+## CHECK-DAG: <<Add2:i\d+>> Add [<<Cst5>>,<<Phi1>>]
+
+## CHECK-DAG: <<Phi2:i\d+>> Phi [<<Cst5>>,<<Add2>>] reg:0 is_catch_phi:false
+## CHECK-DAG: Return [<<Phi2>>]
+
+.method public static testPhiElimination(II)I
+ .registers 4
+
+ :try_start
+ # The constant in entry block will dominate the vreg 0 catch phi.
+ const v0, 5
+
+ # Insert addition so that the value of vreg 1 does not dominate the phi.
+ const v1, 7
+ add-int/2addr v1, v1
+
+ div-int/2addr p0, p1
+ :try_end
+ .catchall {:try_start .. :try_end} :catch_all
+
+ :return
+ return v0
+
+ :catch_all
+ add-int/2addr v0, v1
+ goto :return
+.end method
+
+# Tests that dead catch blocks are removed.
+
+## CHECK-START: int SsaBuilder.testDeadCatchBlock(int, int, int) ssa_builder (before)
+## CHECK: Mul
+
+## CHECK-START: int SsaBuilder.testDeadCatchBlock(int, int, int) ssa_builder (after)
+## CHECK-DAG: <<P0:i\d+>> ParameterValue
+## CHECK-DAG: <<P1:i\d+>> ParameterValue
+## CHECK-DAG: <<P2:i\d+>> ParameterValue
+## CHECK-DAG: <<Add1:i\d+>> Add [<<P0>>,<<P1>>]
+## CHECK-DAG: <<Add2:i\d+>> Add [<<Add1>>,<<P2>>]
+## CHECK-DAG: Return [<<Add2>>]
+
+## CHECK-START: int SsaBuilder.testDeadCatchBlock(int, int, int) ssa_builder (after)
+## CHECK-NOT: flags "catch_block"
+## CHECK-NOT: Mul
+
+.method public static testDeadCatchBlock(III)I
+ .registers 4
+
+ :try_start
+ add-int/2addr p0, p1
+ add-int/2addr p0, p2
+ move v0, p0
+ :try_end
+ .catchall {:try_start .. :try_end} :catch_all
+
+ :return
+ return v0
+
+ :catch_all
+ mul-int/2addr v1, v1
+ goto :return
+.end method
