From b2d364d0eee1d6df4b49e3a7d5b3c4c11af3b3ca Mon Sep 17 00:00:00 2001 From: Santiago Aboy Solanes Date: Thu, 10 Nov 2022 10:26:31 +0000 Subject: Remove tries which don't contain throwing instructions If nothing can throw within a TryBoundary, we are safe to eliminate it. We were already doing this at the builder stage, but this CL takes care of subsequent passes (e.g. we might remove DivZeroCheck instructions which means that now we know we can't throw). Sometimes this means we are able to eliminate catch blocks which brings some code size improvements. Locally on a Pixel 5 compiling with `speed`: * AGSA -684K (0.2%) * services.jar -100K (0.2%) * SystemUIGoogle -88K (0.3%) Bug: 229249867 Test: art/test/testrunner/testrunner.py --host --64 --optimizing -b Change-Id: I36d5880be99c1f1109c94266b1be583de8d6cf72 --- compiler/optimizing/dead_code_elimination.cc | 188 ++++++++++++++++++++++++ compiler/optimizing/dead_code_elimination.h | 20 +++ compiler/optimizing/graph_visualizer.cc | 4 + compiler/optimizing/nodes.cc | 6 +- compiler/optimizing/optimizing_compiler_stats.h | 1 + 5 files changed, 217 insertions(+), 2 deletions(-) (limited to 'compiler') diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc index 909ff838f2..ea914622df 100644 --- a/compiler/optimizing/dead_code_elimination.cc +++ b/compiler/optimizing/dead_code_elimination.cc @@ -486,6 +486,189 @@ void HDeadCodeElimination::ConnectSuccessiveBlocks() { } } +struct HDeadCodeElimination::TryBelongingInformation { + TryBelongingInformation(ScopedArenaAllocator* allocator) + : blocks_in_try(allocator->Adapter(kArenaAllocDCE)), + coalesced_try_entries(allocator->Adapter(kArenaAllocDCE)) {} + + // Which blocks belong in the try. + ScopedArenaSet blocks_in_try; + // Which other try entries are referencing this same try. + ScopedArenaSet coalesced_try_entries; +}; + +bool HDeadCodeElimination::CanPerformTryRemoval(const TryBelongingInformation& try_belonging_info) { + for (HBasicBlock* block : try_belonging_info.blocks_in_try) { + for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { + if (it.Current()->CanThrow()) { + return false; + } + } + } + return true; +} + +void HDeadCodeElimination::DisconnectHandlersAndUpdateTryBoundary( + HBasicBlock* block, + /* out */ bool* any_handler_in_loop) { + // Disconnect the handlers. + while (block->GetSuccessors().size() > 1) { + HBasicBlock* handler = block->GetSuccessors()[1]; + DCHECK(handler->IsCatchBlock()); + block->RemoveSuccessor(handler); + handler->RemovePredecessor(block); + if (handler->IsInLoop()) { + *any_handler_in_loop = true; + } + } + + // Change TryBoundary to Goto. + DCHECK(block->EndsWithTryBoundary()); + HInstruction* last = block->GetLastInstruction(); + block->RemoveInstruction(last); + block->AddInstruction(new (graph_->GetAllocator()) HGoto(last->GetDexPc())); + DCHECK_EQ(block->GetSuccessors().size(), 1u); +} + +void HDeadCodeElimination::RemoveTry(HBasicBlock* try_entry, + const TryBelongingInformation& try_belonging_info, + /* out */ bool* any_handler_in_loop) { + // Update all try entries. + DCHECK(try_entry->EndsWithTryBoundary()); + DCHECK(try_entry->GetLastInstruction()->AsTryBoundary()->IsEntry()); + DisconnectHandlersAndUpdateTryBoundary(try_entry, any_handler_in_loop); + + for (HBasicBlock* other_try_entry : try_belonging_info.coalesced_try_entries) { + DCHECK(other_try_entry->EndsWithTryBoundary()); + DCHECK(other_try_entry->GetLastInstruction()->AsTryBoundary()->IsEntry()); + DisconnectHandlersAndUpdateTryBoundary(other_try_entry, any_handler_in_loop); + } + + // Update the blocks in the try. + for (HBasicBlock* block : try_belonging_info.blocks_in_try) { + // Update the try catch information since now the try doesn't exist. + block->SetTryCatchInformation(nullptr); + + if (block->EndsWithTryBoundary()) { + // Try exits. + DCHECK(!block->GetLastInstruction()->AsTryBoundary()->IsEntry()); + DisconnectHandlersAndUpdateTryBoundary(block, any_handler_in_loop); + + if (block->GetSingleSuccessor()->IsExitBlock()) { + // `predecessor` used to be a single exit TryBoundary that got turned into a Goto. It + // is now pointing to the exit which we don't allow. To fix it, we disconnect + // `predecessor` from its predecessor and RemoveDeadBlocks will remove it from the + // graph. + DCHECK(block->IsSingleGoto()); + HBasicBlock* predecessor = block->GetSinglePredecessor(); + predecessor->ReplaceSuccessor(block, graph_->GetExitBlock()); + } + } + } +} + +bool HDeadCodeElimination::RemoveUnneededTries() { + if (!graph_->HasTryCatch()) { + return false; + } + + // Use local allocator for allocating memory. + ScopedArenaAllocator allocator(graph_->GetArenaStack()); + + // Collect which blocks are part of which try. + std::unordered_map tries; + for (HBasicBlock* block : graph_->GetReversePostOrderSkipEntryBlock()) { + if (block->IsTryBlock()) { + HBasicBlock* key = block->GetTryCatchInformation()->GetTryEntry().GetBlock(); + auto it = tries.find(key); + if (it == tries.end()) { + it = tries.insert({key, TryBelongingInformation(&allocator)}).first; + } + it->second.blocks_in_try.insert(block); + } + } + + // Deduplicate the tries which have different try entries but they are really the same try. + for (auto it = tries.begin(); it != tries.end(); it++) { + DCHECK(it->first->EndsWithTryBoundary()); + HTryBoundary* try_boundary = it->first->GetLastInstruction()->AsTryBoundary(); + for (auto other_it = next(it); other_it != tries.end(); /*other_it++ in the loop*/) { + DCHECK(other_it->first->EndsWithTryBoundary()); + HTryBoundary* other_try_boundary = other_it->first->GetLastInstruction()->AsTryBoundary(); + if (try_boundary->HasSameExceptionHandlersAs(*other_try_boundary)) { + // Merge the entries as they are really the same one. + // Block merging. + it->second.blocks_in_try.insert(other_it->second.blocks_in_try.begin(), + other_it->second.blocks_in_try.end()); + + // Add the coalesced try entry to update it too. + it->second.coalesced_try_entries.insert(other_it->first); + + // Erase the other entry. + other_it = tries.erase(other_it); + } else { + other_it++; + } + } + } + + const size_t total_tries = tries.size(); + size_t removed_tries = 0; + bool any_handler_in_loop = false; + + // Check which tries contain throwing instructions. + for (const auto& entry : tries) { + if (CanPerformTryRemoval(entry.second)) { + ++removed_tries; + RemoveTry(entry.first, entry.second, &any_handler_in_loop); + } + } + + if (removed_tries == total_tries) { + graph_->SetHasTryCatch(false); + } + + if (removed_tries != 0) { + // We want to: + // 1) Update the dominance information + // 2) Remove catch block subtrees, if they are now unreachable. + // If we run the dominance recomputation without removing the code, those catch blocks will + // not be part of the post order and won't be removed. If we don't run the dominance + // recomputation, we risk RemoveDeadBlocks not running it and leaving the graph in an + // inconsistent state. So, what we can do is run RemoveDeadBlocks and if it didn't remove any + // block we trigger a recomputation. + // Note that we are not guaranteed to remove a catch block if we have nested try blocks: + // + // try { + // ... nothing can throw. TryBoundary A ... + // try { + // ... can throw. TryBoundary B... + // } catch (Error e) {} + // } catch (Exception e) {} + // + // In the example above, we can remove the TryBoundary A but the Exception catch cannot be + // removed as the TryBoundary B might still throw into that catch. TryBoundary A and B don't get + // coalesced since they have different catch handlers. + + if (!RemoveDeadBlocks()) { + // If the catches that we modified were in a loop, we have to update the loop information. + if (any_handler_in_loop) { + graph_->ClearLoopInformation(); + graph_->ClearDominanceInformation(); + graph_->BuildDominatorTree(); + } else { + graph_->ClearDominanceInformation(); + graph_->ComputeDominanceInformation(); + graph_->ComputeTryBlockInformation(); + } + } + MaybeRecordStat(stats_, MethodCompilationStat::kRemovedTry, removed_tries); + return true; + } else { + return false; + } +} + bool HDeadCodeElimination::RemoveDeadBlocks() { // Use local allocator for allocating memory. ScopedArenaAllocator allocator(graph_->GetArenaStack()); @@ -561,6 +744,11 @@ bool HDeadCodeElimination::Run() { did_any_simplification |= SimplifyAlwaysThrows(); did_any_simplification |= SimplifyIfs(); did_any_simplification |= RemoveDeadBlocks(); + // We call RemoveDeadBlocks before RemoveUnneededTries to remove the dead blocks from the + // previous optimizations. Otherwise, we might detect that a try has throwing instructions but + // they are actually dead code. RemoveUnneededTryBoundary will call RemoveDeadBlocks again if + // needed. + did_any_simplification |= RemoveUnneededTries(); if (did_any_simplification) { // Connect successive blocks created by dead branches. ConnectSuccessiveBlocks(); diff --git a/compiler/optimizing/dead_code_elimination.h b/compiler/optimizing/dead_code_elimination.h index a3e993c1d7..873e13f244 100644 --- a/compiler/optimizing/dead_code_elimination.h +++ b/compiler/optimizing/dead_code_elimination.h @@ -46,6 +46,26 @@ class HDeadCodeElimination : public HOptimization { bool SimplifyIfs(); void ConnectSuccessiveBlocks(); + // Helper struct to eliminate tries. + struct TryBelongingInformation; + // Disconnects `block`'s handlers and update its `TryBoundary` instruction to a `Goto`. + // Sets `any_handler_in_loop` to true if any handler is currently a loop to later update the loop + // information if needed. + void DisconnectHandlersAndUpdateTryBoundary(HBasicBlock* block, + /* out */ bool* any_handler_in_loop); + // Returns true iff the try doesn't contain throwing instructions. + bool CanPerformTryRemoval(const TryBelongingInformation& try_belonging_info); + // Removes the try by disconnecting all try entries and exits from their handlers. Also updates + // the graph in the case that a `TryBoundary` instruction of kind `exit` has the Exit block as + // its successor. + void RemoveTry(HBasicBlock* try_entry, + const TryBelongingInformation& try_belonging_info, + bool* any_catch_in_loop); + // Checks which tries (if any) are currently in the graph, coalesces the different try entries + // that are referencing the same try, and removes the tries which don't contain any throwing + // instructions. + bool RemoveUnneededTries(); + DISALLOW_COPY_AND_ASSIGN(HDeadCodeElimination); }; diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc index e1199dfb72..2de9446c78 100644 --- a/compiler/optimizing/graph_visualizer.cc +++ b/compiler/optimizing/graph_visualizer.cc @@ -909,6 +909,10 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor { PrintEmptyProperty("flags"); } + if (block->IsTryBlock()) { + PrintProperty("try_start", block->GetTryCatchInformation()->GetTryEntry().GetBlock()); + } + if (block->GetDominator() != nullptr) { PrintProperty("dominator", block->GetDominator()); } diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc index d40ce7a717..841576a5e5 100644 --- a/compiler/optimizing/nodes.cc +++ b/compiler/optimizing/nodes.cc @@ -2885,7 +2885,10 @@ HInstruction* HGraph::InlineInto(HGraph* outer_graph, HInvoke* invoke) { // At this point we might either have: // A) Return/ReturnVoid/Throw as the last instruction // B) `Return/ReturnVoid->TryBoundary->Goto` as the last instruction chain - // C) `Throw->TryBoundary` as the last instruction chain + // C) `Return/ReturnVoid->Goto` as the last instruction chain. This exists when we added the + // extra Goto because we had a TryBoundary which we could eliminate in DCE after + // substituting arguments. + // D) `Throw->TryBoundary` as the last instruction chain const bool saw_goto = last->IsGoto(); if (saw_goto) { @@ -2903,7 +2906,6 @@ HInstruction* HGraph::InlineInto(HGraph* outer_graph, HInvoke* invoke) { } // Check that if we have an instruction chain, it is one of the allowed ones. - DCHECK_IMPLIES(saw_goto, saw_try_boundary); DCHECK_IMPLIES(saw_goto, last->IsReturnVoid() || last->IsReturn()); if (last->IsThrow()) { diff --git a/compiler/optimizing/optimizing_compiler_stats.h b/compiler/optimizing/optimizing_compiler_stats.h index 192519bdd4..02f1fe9d0d 100644 --- a/compiler/optimizing/optimizing_compiler_stats.h +++ b/compiler/optimizing/optimizing_compiler_stats.h @@ -47,6 +47,7 @@ enum class MethodCompilationStat { kUnresolvedFieldNotAFastAccess, kRemovedCheckedCast, kRemovedDeadInstruction, + kRemovedTry, kRemovedNullCheck, kNotCompiledSkipped, kNotCompiledInvalidBytecode, -- cgit v1.2.3-59-g8ed1b