Improve DCE's SimplifyAlwaysThrows regarding Invoke location
Allow SimplifyAlwaysThrows to run on any invoke that always throws,
and not just the second to last instruction.
As a bonus, there are two places that would make a graph have
invokes that always throws:
1) When inlining a method that has invokes that always throw.
2) When trying to inline a method, and not doing it since it
always throws.
Since we only have those two places, we can add a flag to the graph
that tracks this. We then skip the SimplifyAlwaysThrows optimization
altogether if the graph doesn't have that flag set.
Bug: 227316307
Test: art/test/testrunner/testrunner.py --host --64 --optimizing -b
Change-Id: Ia353fcf2c055885cc04e10790584210c2e488e32
diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc
index d808f2c..ee868db 100644
--- a/compiler/optimizing/dead_code_elimination.cc
+++ b/compiler/optimizing/dead_code_elimination.cc
@@ -16,11 +16,13 @@
#include "dead_code_elimination.h"
+#include "android-base/logging.h"
#include "base/array_ref.h"
#include "base/bit_vector-inl.h"
#include "base/scoped_arena_allocator.h"
#include "base/scoped_arena_containers.h"
#include "base/stl_util.h"
+#include "optimizing/nodes.h"
#include "ssa_phi_elimination.h"
namespace art {
@@ -213,6 +215,9 @@
// | ...
// | instr_n
// | foo() // always throws
+// | instr_n+2
+// | ...
+// | instr_n+m
// \ goto B2
// \ /
// B2
@@ -234,7 +239,7 @@
// other optimization opportunities, such as code sinking.
bool HDeadCodeElimination::SimplifyAlwaysThrows() {
HBasicBlock* exit = graph_->GetExitBlock();
- if (exit == nullptr) {
+ if (!graph_->HasAlwaysThrowingInvokes() || exit == nullptr) {
return false;
}
@@ -260,28 +265,43 @@
continue;
}
- HInstruction* last = block->GetLastInstruction();
- HInstruction* prev = last->GetPrevious();
- if (prev == nullptr) {
- DCHECK_EQ(block->GetFirstInstruction(), block->GetLastInstruction());
- continue;
- }
-
- if (prev->AlwaysThrows() &&
- last->IsGoto() &&
+ if (block->GetLastInstruction()->IsGoto() &&
block->GetPhis().IsEmpty() &&
block->GetPredecessors().size() == 1u) {
HBasicBlock* pred = block->GetSinglePredecessor();
HBasicBlock* succ = block->GetSingleSuccessor();
- // Ensure no computations are merged through throwing block.
- // This does not prevent the optimization per se, but would
- // require an elaborate clean up of the SSA graph.
+ // Ensure no computations are merged through throwing block. This does not prevent the
+ // optimization per se, but would require an elaborate clean up of the SSA graph.
if (succ != exit &&
!block->Dominates(pred) &&
pred->Dominates(succ) &&
succ->GetPredecessors().size() > 1u &&
succ->GetPhis().IsEmpty()) {
- block->ReplaceSuccessor(succ, exit);
+ // We iterate to find the first instruction that always throws. If two instructions always
+ // throw, the first one will throw and the second one will never be reached.
+ HInstruction* throwing_instruction = nullptr;
+ for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
+ if (it.Current()->AlwaysThrows()) {
+ throwing_instruction = it.Current();
+ break;
+ }
+ }
+
+ if (throwing_instruction == nullptr) {
+ // No always-throwing instruction found. Continue with the rest of the blocks.
+ continue;
+ }
+
+ // We split the block at the throwing instruction, and the instructions after the throwing
+ // instructions will be disconnected from the graph after `block` points to the exit.
+ // `RemoveDeadBlocks` will take care of removing this new block and its instructions.
+ // Even though `SplitBefore` doesn't guarantee the graph to remain in SSA form, it is fine
+ // since we do not break it.
+ HBasicBlock* new_block = block->SplitBefore(throwing_instruction->GetNext(),
+ /* require_graph_not_in_ssa_form= */ false);
+ DCHECK_EQ(block->GetSingleSuccessor(), new_block);
+ block->ReplaceSuccessor(new_block, exit);
+
rerun_dominance_and_loop_analysis = true;
MaybeRecordStat(stats_, MethodCompilationStat::kSimplifyThrowingInvoke);
// Perform a quick follow up optimization on object != null control dependences
diff --git a/compiler/optimizing/inliner.cc b/compiler/optimizing/inliner.cc
index 2b8c04b..d8ace5e 100644
--- a/compiler/optimizing/inliner.cc
+++ b/compiler/optimizing/inliner.cc
@@ -201,6 +201,10 @@
}
}
+ if (did_set_always_throws) {
+ graph_->SetHasAlwaysThrowingInvokes(/* value= */ true);
+ }
+
return did_inline || did_set_always_throws;
}
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 90c8f74..ba6d1a7 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -2108,8 +2108,9 @@
MoveBefore(insert_pos);
}
-HBasicBlock* HBasicBlock::SplitBefore(HInstruction* cursor) {
- DCHECK(!graph_->IsInSsaForm()) << "Support for SSA form not implemented.";
+HBasicBlock* HBasicBlock::SplitBefore(HInstruction* cursor, bool require_graph_not_in_ssa_form) {
+ DCHECK_IMPLIES(require_graph_not_in_ssa_form, !graph_->IsInSsaForm())
+ << "Support for SSA form not implemented.";
DCHECK_EQ(cursor->GetBlock(), this);
HBasicBlock* new_block =
@@ -2733,6 +2734,9 @@
if (HasSIMD()) {
outer_graph->SetHasSIMD(true);
}
+ if (HasAlwaysThrowingInvokes()) {
+ outer_graph->SetHasAlwaysThrowingInvokes(true);
+ }
HInstruction* return_value = nullptr;
if (GetBlocks().size() == 3) {
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index a923123..a1a6747 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -406,6 +406,7 @@
has_loops_(false),
has_irreducible_loops_(false),
has_direct_critical_native_call_(false),
+ has_always_throwing_invokes_(false),
dead_reference_safe_(dead_reference_safe),
debuggable_(debuggable),
current_instruction_id_(start_instruction_id),
@@ -711,6 +712,9 @@
bool HasDirectCriticalNativeCall() const { return has_direct_critical_native_call_; }
void SetHasDirectCriticalNativeCall(bool value) { has_direct_critical_native_call_ = value; }
+ bool HasAlwaysThrowingInvokes() const { return has_always_throwing_invokes_; }
+ void SetHasAlwaysThrowingInvokes(bool value) { has_always_throwing_invokes_ = value; }
+
ArtMethod* GetArtMethod() const { return art_method_; }
void SetArtMethod(ArtMethod* method) { art_method_ = method; }
@@ -833,6 +837,9 @@
// for @CriticalNative methods.
bool has_direct_critical_native_call_;
+ // Flag whether the graph contains invokes that always throw.
+ bool has_always_throwing_invokes_;
+
// Is the code known to be robust against eliminating dead references
// and the effects of early finalization? If false, dead reference variables
// are kept if they might be visible to the garbage collector.
@@ -1298,7 +1305,7 @@
// graph, create a Goto at the end of the former block and will create an edge
// between the blocks. It will not, however, update the reverse post order or
// loop and try/catch information.
- HBasicBlock* SplitBefore(HInstruction* cursor);
+ HBasicBlock* SplitBefore(HInstruction* cursor, bool require_graph_not_in_ssa_form = true);
// Split the block into two blocks just before `cursor`. Returns the newly
// created block. Note that this method just updates raw block information,
diff --git a/test/2042-checker-dce-always-throw/src/Main.java b/test/2042-checker-dce-always-throw/src/Main.java
index 99738a7..a82bbc3 100644
--- a/test/2042-checker-dce-always-throw/src/Main.java
+++ b/test/2042-checker-dce-always-throw/src/Main.java
@@ -20,6 +20,7 @@
assertEquals(0, $noinline$testSimplifyThrow(1));
// Basic test for non-trivial blocks (i.e. not just an invoke and a Goto)
+ assertEquals(0, $noinline$testSimplifyThrowAndPrint(1));
assertEquals(0, $noinline$testSimplifyTwoThrows(1));
// Try catch tests
@@ -51,6 +52,28 @@
return 0;
}
+ /// CHECK-START: int Main.$noinline$testSimplifyThrowAndPrint(int) dead_code_elimination$after_inlining (before)
+ /// CHECK-DAG: InvokeStaticOrDirect block:<<InvokeBlock:B\d+>> method_name:Main.alwaysThrows always_throws:true
+ /// CHECK-DAG: InvokeVirtual method_name:java.io.PrintStream.println
+ /// CHECK-DAG: Exit block:<<ExitBlock:B\d+>>
+ /// CHECK-DAG: Goto block:<<InvokeBlock>> target:<<TargetBlock:B\d+>>
+ /// CHECK-EVAL: "<<ExitBlock>>" != "<<TargetBlock>>"
+
+ /// CHECK-START: int Main.$noinline$testSimplifyThrowAndPrint(int) dead_code_elimination$after_inlining (after)
+ /// CHECK-DAG: InvokeStaticOrDirect block:<<InvokeBlock:B\d+>> method_name:Main.alwaysThrows always_throws:true
+ /// CHECK-DAG: Exit block:<<ExitBlock:B\d+>>
+ /// CHECK-DAG: Goto block:<<InvokeBlock>> target:<<ExitBlock>>
+
+ /// CHECK-START: int Main.$noinline$testSimplifyThrowAndPrint(int) dead_code_elimination$after_inlining (after)
+ /// CHECK-NOT: InvokeVirtual method_name:java.io.PrintStream.println
+ private static int $noinline$testSimplifyThrowAndPrint(int num) {
+ if (num == 0) {
+ alwaysThrows();
+ System.out.println("I am unrechable!");
+ }
+ return 0;
+ }
+
/// CHECK-START: int Main.$noinline$testSimplifyTwoThrows(int) dead_code_elimination$after_inlining (before)
/// CHECK-DAG: InvokeStaticOrDirect block:<<InvokeBlock:B\d+>> method_name:Main.alwaysThrows always_throws:true
/// CHECK-DAG: InvokeStaticOrDirect block:<<InvokeBlock>> method_name:Main.alwaysThrows always_throws:true
@@ -60,10 +83,14 @@
/// CHECK-START: int Main.$noinline$testSimplifyTwoThrows(int) dead_code_elimination$after_inlining (after)
/// CHECK-DAG: InvokeStaticOrDirect block:<<InvokeBlock:B\d+>> method_name:Main.alwaysThrows always_throws:true
- /// CHECK-DAG: InvokeStaticOrDirect block:<<InvokeBlock>> method_name:Main.alwaysThrows always_throws:true
/// CHECK-DAG: Exit block:<<ExitBlock:B\d+>>
/// CHECK-DAG: Goto block:<<InvokeBlock>> target:<<ExitBlock>>
+ // Check that the second `alwaysThrows` gets removed.
+ /// CHECK-START: int Main.$noinline$testSimplifyTwoThrows(int) dead_code_elimination$after_inlining (after)
+ /// CHECK: InvokeStaticOrDirect method_name:Main.alwaysThrows always_throws:true
+ /// CHECK-NOT: InvokeStaticOrDirect method_name:Main.alwaysThrows always_throws:true
+
// Tests that we simplify the always throwing branch directly to the exit, even with blocks that
// are not just the throwing instruction and a Goto.
private static int $noinline$testSimplifyTwoThrows(int num) {