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

4 files changed, 52 insertions, 17 deletions

diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc
index d808f2ca3a..ee868db759 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 @@ static bool RemoveNonNullControlDependences(HBasicBlock* block, HBasicBlock* thr
 //          |   ...
 //          |   instr_n
 //          |   foo()  // always throws
+//          |   instr_n+2
+//          |   ...
+//          |   instr_n+m
 //          \   goto B2
 //           \ /
 //            B2
@@ -234,7 +239,7 @@ static bool RemoveNonNullControlDependences(HBasicBlock* block, HBasicBlock* thr
 // 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 @@ bool HDeadCodeElimination::SimplifyAlwaysThrows() {
       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 2b8c04b4a5..d8ace5eadd 100644
--- a/compiler/optimizing/inliner.cc
+++ b/compiler/optimizing/inliner.cc
@@ -201,6 +201,10 @@ bool HInliner::Run() {
     }
   }
 
+  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 90c8f748a5..ba6d1a7da2 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -2108,8 +2108,9 @@ void HInstruction::MoveBeforeFirstUserAndOutOfLoops() {
   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 @@ HInstruction* HGraph::InlineInto(HGraph* outer_graph, HInvoke* invoke) {
   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 a923123e9f..a1a6747601 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -406,6 +406,7 @@ class HGraph : public ArenaObject<kArenaAllocGraph> {
         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 @@ class HGraph : public ArenaObject<kArenaAllocGraph> {
   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 @@ class HGraph : public ArenaObject<kArenaAllocGraph> {
   // 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 @@ class HBasicBlock : public ArenaObject<kArenaAllocBasicBlock> {
   // 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,