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
diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc
index 909ff83..ea91462 100644
--- a/compiler/optimizing/dead_code_elimination.cc
+++ b/compiler/optimizing/dead_code_elimination.cc
@@ -486,6 +486,189 @@
}
}
+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<HBasicBlock*> blocks_in_try;
+ // Which other try entries are referencing this same try.
+ ScopedArenaSet<HBasicBlock*> 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<HBasicBlock*, TryBelongingInformation> 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 @@
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 a3e993c..873e13f 100644
--- a/compiler/optimizing/dead_code_elimination.h
+++ b/compiler/optimizing/dead_code_elimination.h
@@ -46,6 +46,26 @@
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 e1199df..2de9446 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -909,6 +909,10 @@
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 d40ce7a..841576a 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -2885,7 +2885,10 @@
// 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 @@
}
// 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 192519b..02f1fe9 100644
--- a/compiler/optimizing/optimizing_compiler_stats.h
+++ b/compiler/optimizing/optimizing_compiler_stats.h
@@ -47,6 +47,7 @@
kUnresolvedFieldNotAFastAccess,
kRemovedCheckedCast,
kRemovedDeadInstruction,
+ kRemovedTry,
kRemovedNullCheck,
kNotCompiledSkipped,
kNotCompiledInvalidBytecode,