Move adding extra goto blocks to InlineInto

There are some cases in which we need to add extra goto blocks
when inlining to avoid critical edges. The `TryBoundary` of
`kind:exit` instructions will always have more than one successor
(normal flow and exceptional flow). If its normal flow successor
has more than one predecessor, we would be introducing a critical edge.

We can avoid the critical edge in InlineInto instead of doing it in
the builder which helps decoupling those two stages as well as
simplifying surrounding code.

We also have the benefit of adding the extra goto blocks only
when necessary.

Bug: 227283224
Test: art/test/testrunner/testrunner.py --host --64 --optimizing -b
Change-Id: Ibe21623c94c798f7cea60ff892064e63a38a787a

4 files changed, 19 insertions, 82 deletions

diff --git a/compiler/optimizing/builder.cc b/compiler/optimizing/builder.cc
index c9609e0bda..9e871c41bc 100644
--- a/compiler/optimizing/builder.cc
+++ b/compiler/optimizing/builder.cc
@@ -96,55 +96,7 @@ bool HGraphBuilder::SkipCompilation(size_t number_of_branches) {
   return false;
 }
 
-static bool NeedsExtraGotoBlock(HBasicBlock* block) {
-  if (!block->IsSingleTryBoundary()) {
-    return false;
-  }
-
-  const HTryBoundary* boundary = block->GetLastInstruction()->AsTryBoundary();
-  DCHECK(boundary->GetNormalFlowSuccessor()->IsExitBlock());
-  DCHECK(!boundary->IsEntry());
-
-  const HInstruction* last_instruction = block->GetSinglePredecessor()->GetLastInstruction();
-  DCHECK(last_instruction->IsReturn() ||
-         last_instruction->IsReturnVoid() ||
-         last_instruction->IsThrow());
-
-  return !last_instruction->IsThrow();
-}
-
-void HGraphBuilder::MaybeAddExtraGotoBlocks() {
-  HBasicBlock* exit = graph_->GetExitBlock();
-  if (exit == nullptr) {
-    return;
-  }
-
-  for (size_t pred = 0, size = exit->GetPredecessors().size(); pred < size; ++pred) {
-    HBasicBlock* predecessor = exit->GetPredecessors()[pred];
-    if (NeedsExtraGotoBlock(predecessor)) {
-      HBasicBlock* new_goto = graph_->SplitEdgeAndUpdateRPO(predecessor, exit);
-      new_goto->AddInstruction(new (graph_->GetAllocator()) HGoto(predecessor->GetDexPc()));
-      if (predecessor->IsInLoop()) {
-        new_goto->SetLoopInformation(predecessor->GetLoopInformation());
-      }
-
-      // Update domination chain
-      if (!predecessor->GetDominatedBlocks().empty()) {
-        DCHECK_EQ(predecessor->GetDominatedBlocks().size(), 1u);
-        DCHECK_EQ(predecessor->GetDominatedBlocks()[0], exit);
-        new_goto->AddDominatedBlock(exit);
-        predecessor->RemoveDominatedBlock(exit);
-        exit->SetDominator(new_goto);
-      }
-
-      DCHECK(predecessor->GetDominatedBlocks().empty());
-      predecessor->AddDominatedBlock(new_goto);
-      new_goto->SetDominator(predecessor);
-    }
-  }
-}
-
-GraphAnalysisResult HGraphBuilder::BuildGraph(bool build_for_inline) {
+GraphAnalysisResult HGraphBuilder::BuildGraph() {
   DCHECK(code_item_accessor_.HasCodeItem());
   DCHECK(graph_->GetBlocks().empty());
 
@@ -195,13 +147,7 @@ GraphAnalysisResult HGraphBuilder::BuildGraph(bool build_for_inline) {
     return kAnalysisInvalidBytecode;
   }
 
-  // 5) When inlining, we want to add a Goto block if we have Return/ReturnVoid->TryBoundary->Exit
-  // since we will have Return/ReturnVoid->TryBoundary->`continue to normal execution` once inlined.
-  if (build_for_inline) {
-    MaybeAddExtraGotoBlocks();
-  }
-
-  // 6) Type the graph and eliminate dead/redundant phis.
+  // 5) Type the graph and eliminate dead/redundant phis.
   return ssa_builder.BuildSsa();
 }
 
diff --git a/compiler/optimizing/builder.h b/compiler/optimizing/builder.h
index 145dbfb6b9..ef225d9a6a 100644
--- a/compiler/optimizing/builder.h
+++ b/compiler/optimizing/builder.h
@@ -47,7 +47,7 @@ class HGraphBuilder : public ValueObject {
                 const CodeItemDebugInfoAccessor& accessor,
                 DataType::Type return_type = DataType::Type::kInt32);
 
-  GraphAnalysisResult BuildGraph(bool build_for_inline = false);
+  GraphAnalysisResult BuildGraph();
   void BuildIntrinsicGraph(ArtMethod* method);
 
   static constexpr const char* kBuilderPassName = "builder";
@@ -55,10 +55,6 @@ class HGraphBuilder : public ValueObject {
  private:
   bool SkipCompilation(size_t number_of_branches);
 
-  // When inlining, we sometimes want to add an extra Goto block before the Exit block. This is done
-  // in the building phase as we do not allow the inlining phase to add new instructions.
-  void MaybeAddExtraGotoBlocks();
-
   HGraph* const graph_;
   const DexFile* const dex_file_;
   const CodeItemDebugInfoAccessor code_item_accessor_;  // null for intrinsic graph.
diff --git a/compiler/optimizing/inliner.cc b/compiler/optimizing/inliner.cc
index 1f7ef2cf4c..2645cf1e49 100644
--- a/compiler/optimizing/inliner.cc
+++ b/compiler/optimizing/inliner.cc
@@ -2119,7 +2119,7 @@ bool HInliner::TryBuildAndInlineHelper(HInvoke* invoke_instruction,
                         codegen_,
                         inline_stats_);
 
-  if (builder.BuildGraph(/* build_for_inline= */ true) != kAnalysisSuccess) {
+  if (builder.BuildGraph() != kAnalysisSuccess) {
     LOG_FAIL(stats_, MethodCompilationStat::kNotInlinedCannotBuild)
         << "Method " << callee_dex_file.PrettyMethod(method_index)
         << " could not be built, so cannot be inlined";
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 85d0fe7245..8491c24b23 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -2893,19 +2893,8 @@ HInstruction* HGraph::InlineInto(HGraph* outer_graph, HInvoke* invoke) {
       HInstruction* last = predecessor->GetLastInstruction();
 
       // 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) `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) {
-        DCHECK(predecessor->IsSingleGoto());
-        predecessor = predecessor->GetSinglePredecessor();
-        last = predecessor->GetLastInstruction();
-      }
+      // A) Return/ReturnVoid/Throw as the last instruction, or
+      // B) `Return/ReturnVoid/Throw->TryBoundary` as the last instruction chain
 
       const bool saw_try_boundary = last->IsTryBoundary();
       if (saw_try_boundary) {
@@ -2915,14 +2904,7 @@ HInstruction* HGraph::InlineInto(HGraph* outer_graph, HInvoke* invoke) {
         last = predecessor->GetLastInstruction();
       }
 
-      // Check that if we have an instruction chain, it is one of the allowed ones.
-      DCHECK_IMPLIES(saw_goto, last->IsReturnVoid() || last->IsReturn());
-
       if (last->IsThrow()) {
-        // The chain `Throw->TryBoundary` is allowed but not `Throw->TryBoundary->Goto` since that
-        // would mean a Goto will point to exit after ReplaceSuccessor.
-        DCHECK(!saw_goto);
-
         if (at->IsTryBlock()) {
           DCHECK(!saw_try_boundary) << "We don't support inlining of try blocks into try blocks.";
           // Create a TryBoundary of kind:exit and point it to the Exit block.
@@ -2982,6 +2964,19 @@ HInstruction* HGraph::InlineInto(HGraph* outer_graph, HInvoke* invoke) {
         }
         predecessor->AddInstruction(new (allocator) HGoto(last->GetDexPc()));
         predecessor->RemoveInstruction(last);
+
+        if (saw_try_boundary) {
+          predecessor = to->GetPredecessors()[pred];
+          DCHECK(predecessor->EndsWithTryBoundary());
+          DCHECK_EQ(predecessor->GetNormalSuccessors().size(), 1u);
+          if (predecessor->GetSuccessors()[0]->GetPredecessors().size() > 1) {
+            outer_graph->SplitCriticalEdge(predecessor, to);
+            rerun_dominance = true;
+            if (predecessor->GetLoopInformation() != nullptr) {
+              rerun_loop_analysis = true;
+            }
+          }
+        }
       }
     }
     if (rerun_loop_analysis) {