diff options
-rw-r--r-- | compiler/optimizing/graph_checker.cc | 160 | ||||
-rw-r--r-- | compiler/optimizing/graph_checker.h | 3 | ||||
-rw-r--r-- | compiler/optimizing/graph_visualizer.cc | 48 | ||||
-rw-r--r-- | compiler/optimizing/graph_visualizer.h | 2 | ||||
-rw-r--r-- | compiler/optimizing/nodes.cc | 137 | ||||
-rw-r--r-- | compiler/optimizing/nodes.h | 70 | ||||
-rw-r--r-- | compiler/optimizing/optimizing_compiler.cc | 23 | ||||
-rw-r--r-- | compiler/optimizing/ssa_builder.cc | 41 | ||||
-rw-r--r-- | compiler/optimizing/ssa_builder.h | 19 | ||||
-rw-r--r-- | compiler/optimizing/ssa_phi_elimination.cc | 11 | ||||
-rw-r--r-- | test/510-checker-try-catch/smali/SsaBuilder.smali | 199 |
11 files changed, 618 insertions, 95 deletions
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc index 9679d0ab70..cfebb77dd7 100644 --- a/compiler/optimizing/graph_checker.cc +++ b/compiler/optimizing/graph_checker.cc @@ -136,6 +136,33 @@ void GraphChecker::VisitBoundsCheck(HBoundsCheck* check) { 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 GraphChecker::VisitInstanceOf(HInstanceOf* instruction) { 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 @@ void SSAChecker::VisitBasicBlock(HBasicBlock* block) { } } + // 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 @@ void SSAChecker::VisitPhi(HPhi* phi) { 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 @@ void SSAChecker::VisitPhi(HPhi* phi) { 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 7c72e23e2d..0e270dbe18 100644 --- a/compiler/optimizing/graph_checker.h +++ b/compiler/optimizing/graph_checker.h @@ -48,6 +48,9 @@ class GraphChecker : public HGraphDelegateVisitor { // 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 37c060c1b1..afea40316c 100644 --- a/compiler/optimizing/graph_visualizer.cc +++ b/compiler/optimizing/graph_visualizer.cc @@ -158,12 +158,14 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor { 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 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor { 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 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor { 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 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor { 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 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor { 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 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor { 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 @@ HGraphVisualizer::HGraphVisualizer(std::ostream* output, 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 @@ void HGraphVisualizer::PrintHeader(const char* method_name) const { 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::DumpGraph(const char* pass_name, bool is_after_pass) cons 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 b6b66df601..66588f6e36 100644 --- a/compiler/optimizing/graph_visualizer.h +++ b/compiler/optimizing/graph_visualizer.h @@ -104,7 +104,7 @@ class HGraphVisualizer : public ValueObject { 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 588ab70001..519fa005a6 100644 --- a/compiler/optimizing/nodes.cc +++ b/compiler/optimizing/nodes.cc @@ -98,26 +98,31 @@ void HGraph::VisitBlockForBackEdges(HBasicBlock* block, } 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 @@ void HGraph::SimplifyLoop(HBasicBlock* header) { 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 @@ void HGraph::SimplifyCFG() { 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 @@ bool HGraph::AnalyzeNaturalLoops() const { 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 @@ HBasicBlock* HBasicBlock::SplitAfter(HInstruction* cursor) { 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 @@ bool HBasicBlock::EndsWithIf() const { 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 8546a1066f..fd2a04d892 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -49,6 +49,7 @@ class HLongConstant; class HNullConstant; class HPhi; class HSuspendCheck; +class HTryBoundary; class LiveInterval; class LocationSummary; class SlowPathCode; @@ -182,6 +183,10 @@ class HGraph : public ArenaObject<kArenaAllocMisc> { // 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 @@ class HGraph : public ArenaObject<kArenaAllocMisc> { 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 @@ class HBasicBlock : public ArenaObject<kArenaAllocMisc> { 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 @@ class HBasicBlock : public ArenaObject<kArenaAllocMisc> { 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 @@ class HBasicBlock : public ArenaObject<kArenaAllocMisc> { bool EndsWithControlFlowInstruction() const; bool EndsWithIf() const; + bool EndsWithTryBoundary() const; bool HasSinglePhi() const; private: @@ -864,6 +887,10 @@ class HBasicBlock : public ArenaObject<kArenaAllocMisc> { 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 @@ class HTryBoundary : public HTemplateInstruction<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; + 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 @@ class HTryBoundary : public HTemplateInstruction<0> { 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 @@ class HPhi : public HInstruction { } } + 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 4568a463db..aeb1ae20a3 100644 --- a/compiler/optimizing/optimizing_compiler.cc +++ b/compiler/optimizing/optimizing_compiler.cc @@ -132,7 +132,7 @@ class PassObserver : public ValueObject { 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 @@ class PassObserver : public ValueObject { 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 @@ CompiledMethod* OptimizingCompiler::TryCompile(const DexFile::CodeItem* code_ite // 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 @@ CompiledMethod* OptimizingCompiler::TryCompile(const DexFile::CodeItem* code_ite // 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 c37b1995fa..ff2e6ad821 100644 --- a/compiler/optimizing/ssa_builder.cc +++ b/compiler/optimizing/ssa_builder.cc @@ -350,7 +350,9 @@ HInstruction* SsaBuilder::ValueOfLocal(HBasicBlock* block, size_t local) { 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::VisitStoreLocal(HStoreLocal* store) { } 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); + } + + // 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); + } + } + } } - 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); } void SsaBuilder::VisitTemporary(HTemporary* temp) { diff --git a/compiler/optimizing/ssa_builder.h b/compiler/optimizing/ssa_builder.h index 1c83c4ba48..64600db648 100644 --- a/compiler/optimizing/ssa_builder.h +++ b/compiler/optimizing/ssa_builder.h @@ -61,9 +61,22 @@ class SsaBuilder : public HGraphVisitor { 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 2f2e2d1fab..917341a1e7 100644 --- a/compiler/optimizing/ssa_phi_elimination.cc +++ b/compiler/optimizing/ssa_phi_elimination.cc @@ -114,6 +114,12 @@ void SsaRedundantPhiElimination::Run() { 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 @@ void SsaRedundantPhiElimination::Run() { 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 0000000000..2ddcbced9c --- /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 |