From 31242a99a1b58ce5267c1a74ad96a9d0b6dc1a94 Mon Sep 17 00:00:00 2001
From: Santiago Aboy Solanes <solanes@google.com>
Date: Mon, 5 Dec 2022 14:38:00 +0000
Subject: Update domination chain and RPO manually in MaybeAddExtraGotoBlocks

There's no need to recompute the whole graph as we know what changed.

As a drive-by, we now don't return false for graphs with irreducible
loops so we can remove that restriction from the builder. However,
if a graph with irreducible loops hits this path it means that:
  A) it's being inlined
  B) Has irreducible loops

We don't inline graphs with irreducible loops, and after building
for inline we don't remove them either because constant folding
and instruction simplifier don't remove them, and DCE doesn't
run for graphs with irreducible loops. So, in terms of dex2oat's
outputs nothing should change.

Test: art/test/testrunner/testrunner.py --host --64 --optimizing -b
Change-Id: I8cbf1b5f0518bb5dd14ffd751100ea81f5478863
---
 compiler/optimizing/builder.cc | 56 +++++++++++++++++++++---------------------
 1 file changed, 28 insertions(+), 28 deletions(-)

(limited to 'compiler/optimizing/builder.cc')

diff --git a/compiler/optimizing/builder.cc b/compiler/optimizing/builder.cc
index da791a7cf7..897d8b7015 100644
--- a/compiler/optimizing/builder.cc
+++ b/compiler/optimizing/builder.cc
@@ -113,36 +113,38 @@ static bool NeedsExtraGotoBlock(HBasicBlock* block) {
   return !last_instruction->IsThrow();
 }
 
-bool HGraphBuilder::MaybeAddExtraGotoBlocks() {
-  if (graph_->GetExitBlock() == nullptr) {
-    return true;
+void HGraphBuilder::MaybeAddExtraGotoBlocks() {
+  HBasicBlock* exit = graph_->GetExitBlock();
+  if (exit == nullptr) {
+    return;
   }
 
-  bool added_block = false;
-  for (size_t pred = 0, size = graph_->GetExitBlock()->GetPredecessors().size(); pred < size;
-       ++pred) {
-    HBasicBlock* predecessor = graph_->GetExitBlock()->GetPredecessors()[pred];
+  for (size_t pred = 0, size = exit->GetPredecessors().size(); pred < size; ++pred) {
+    HBasicBlock* predecessor = exit->GetPredecessors()[pred];
     if (NeedsExtraGotoBlock(predecessor)) {
-      added_block = true;
-      graph_->SplitEdge(predecessor, graph_->GetExitBlock())
-          ->AddInstruction(new (graph_->GetAllocator()) HGoto(predecessor->GetDexPc()));
+      HBasicBlock* new_goto = graph_->SplitEdgeAndUpdateRPO(predecessor, exit);
+      new_goto->AddInstruction(new (graph_->GetAllocator()) HGoto(predecessor->GetDexPc()));
+
+      // No need to update loop info of the new block.
+      DCHECK(!predecessor->IsInLoop())
+          << " we should only add the extra Goto blocks for Return/ReturnVoid->TryBoundary->Exit "
+          << "chains. In those chains, the TryBoundary of kind:exit should never be a part of a "
+          << "loop";
+
+      // 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);
     }
   }
-
-  // TODO(solanes): Avoid recomputing the full dominator tree by manually updating the relevant
-  // information (loop information, dominance, try catch information).
-  if (added_block) {
-    if (graph_->HasIrreducibleLoops()) {
-      // Recomputing loop information in graphs with irreducible loops is unsupported, as it could
-      // lead to loop header changes. In this case it is safe to abort since we don't inline graphs
-      // with irreducible loops anyway.
-      return false;
-    }
-    graph_->ClearLoopInformation();
-    graph_->ClearDominanceInformation();
-    graph_->BuildDominatorTree();
-  }
-  return true;
 }
 
 GraphAnalysisResult HGraphBuilder::BuildGraph(bool build_for_inline) {
@@ -199,9 +201,7 @@ GraphAnalysisResult HGraphBuilder::BuildGraph(bool build_for_inline) {
   // 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) {
-    if (!MaybeAddExtraGotoBlocks()) {
-      return kAnalysisFailInliningIrreducibleLoop;
-    }
+    MaybeAddExtraGotoBlocks();
   }
 
   // 6) Type the graph and eliminate dead/redundant phis.
-- 
cgit v1.2.3-59-g8ed1b