Update loop information correctly when removing tries

When removing tries we were relying on RemoveDeadBlocks to recompute
the dominance and loop information. In some cases, the removed
blocks are not part of the loop even though the removed try was
part of a loop. In those cases, we have to update the loop
information even when the deleted catch block is not part of a loop.
In order to do that, we can add some parameters to RemoveDeadBlocks
to force recomputation when we know it is needed.

Bug: 252803203
Fixes: 252803203
Test: dex2oat compiling apps in the bug
Test: art/test/testrunner/testrunner.py --host --64 --optimizing -b
Change-Id: Id54edd0d16cedc6b95fc312e2018cd0dab82f0ae

3 files changed, 107 insertions, 29 deletions

diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc
index 410ef0aa5a..e15e731fcd 100644
--- a/compiler/optimizing/dead_code_elimination.cc
+++ b/compiler/optimizing/dead_code_elimination.cc
@@ -19,6 +19,7 @@
 #include "android-base/logging.h"
 #include "base/array_ref.h"
 #include "base/bit_vector-inl.h"
+#include "base/logging.h"
 #include "base/scoped_arena_allocator.h"
 #include "base/scoped_arena_containers.h"
 #include "base/stl_util.h"
@@ -510,7 +511,11 @@ bool HDeadCodeElimination::CanPerformTryRemoval(const TryBelongingInformation& t
 
 void HDeadCodeElimination::DisconnectHandlersAndUpdateTryBoundary(
     HBasicBlock* block,
-    /* out */ bool* any_handler_in_loop) {
+    /* out */ bool* any_block_in_loop) {
+  if (block->IsInLoop()) {
+    *any_block_in_loop = true;
+  }
+
   // Disconnect the handlers.
   while (block->GetSuccessors().size() > 1) {
     HBasicBlock* handler = block->GetSuccessors()[1];
@@ -518,7 +523,7 @@ void HDeadCodeElimination::DisconnectHandlersAndUpdateTryBoundary(
     block->RemoveSuccessor(handler);
     handler->RemovePredecessor(block);
     if (handler->IsInLoop()) {
-      *any_handler_in_loop = true;
+      *any_block_in_loop = true;
     }
   }
 
@@ -532,27 +537,30 @@ void HDeadCodeElimination::DisconnectHandlersAndUpdateTryBoundary(
 
 void HDeadCodeElimination::RemoveTry(HBasicBlock* try_entry,
                                      const TryBelongingInformation& try_belonging_info,
-                                     /* out */ bool* any_handler_in_loop) {
+                                     /* out */ bool* any_block_in_loop) {
   // Update all try entries.
   DCHECK(try_entry->EndsWithTryBoundary());
   DCHECK(try_entry->GetLastInstruction()->AsTryBoundary()->IsEntry());
-  DisconnectHandlersAndUpdateTryBoundary(try_entry, any_handler_in_loop);
+  DisconnectHandlersAndUpdateTryBoundary(try_entry, any_block_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);
+    DisconnectHandlersAndUpdateTryBoundary(other_try_entry, any_block_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->IsInLoop()) {
+      *any_block_in_loop = true;
+    }
 
     if (block->EndsWithTryBoundary()) {
       // Try exits.
       DCHECK(!block->GetLastInstruction()->AsTryBoundary()->IsEntry());
-      DisconnectHandlersAndUpdateTryBoundary(block, any_handler_in_loop);
+      DisconnectHandlersAndUpdateTryBoundary(block, any_block_in_loop);
 
       if (block->GetSingleSuccessor()->IsExitBlock()) {
         // `block` used to be a single exit TryBoundary that got turned into a Goto. It
@@ -623,13 +631,13 @@ bool HDeadCodeElimination::RemoveUnneededTries() {
 
   const size_t total_tries = tries.size();
   size_t removed_tries = 0;
-  bool any_handler_in_loop = false;
+  bool any_block_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);
+      RemoveTry(entry.first, entry.second, &any_block_in_loop);
     }
   }
 
@@ -644,8 +652,7 @@ bool HDeadCodeElimination::RemoveUnneededTries() {
     // 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.
+    // inconsistent state. So, what we can do is run RemoveDeadBlocks and force a recomputation.
     // Note that we are not guaranteed to remove a catch block if we have nested try blocks:
     //
     //   try {
@@ -659,18 +666,7 @@ bool HDeadCodeElimination::RemoveUnneededTries() {
     // 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();
-      }
-    }
+    RemoveDeadBlocks(/* force_recomputation= */ true, any_block_in_loop);
     MaybeRecordStat(stats_, MethodCompilationStat::kRemovedTry, removed_tries);
     return true;
   } else {
@@ -678,7 +674,10 @@ bool HDeadCodeElimination::RemoveUnneededTries() {
   }
 }
 
-bool HDeadCodeElimination::RemoveDeadBlocks() {
+bool HDeadCodeElimination::RemoveDeadBlocks(bool force_recomputation,
+                                            bool force_loop_recomputation) {
+  DCHECK_IMPLIES(force_loop_recomputation, force_recomputation);
+
   // Use local allocator for allocating memory.
   ScopedArenaAllocator allocator(graph_->GetArenaStack());
 
@@ -707,8 +706,8 @@ bool HDeadCodeElimination::RemoveDeadBlocks() {
 
   // If we removed at least one block, we need to recompute the full
   // dominator tree and try block membership.
-  if (removed_one_or_more_blocks) {
-    if (rerun_dominance_and_loop_analysis) {
+  if (removed_one_or_more_blocks || force_recomputation) {
+    if (rerun_dominance_and_loop_analysis || force_loop_recomputation) {
       graph_->ClearLoopInformation();
       graph_->ClearDominanceInformation();
       graph_->BuildDominatorTree();
diff --git a/compiler/optimizing/dead_code_elimination.h b/compiler/optimizing/dead_code_elimination.h
index 873e13f244..1988733d75 100644
--- a/compiler/optimizing/dead_code_elimination.h
+++ b/compiler/optimizing/dead_code_elimination.h
@@ -40,7 +40,10 @@ class HDeadCodeElimination : public HOptimization {
  private:
   void MaybeRecordDeadBlock(HBasicBlock* block);
   void MaybeRecordSimplifyIf();
-  bool RemoveDeadBlocks();
+  // If `force_recomputation` is true, we will recompute the dominance information even when we
+  // didn't delete any blocks. `force_loop_recomputation` is similar but it also forces the loop
+  // information recomputation.
+  bool RemoveDeadBlocks(bool force_recomputation = false, bool force_loop_recomputation = false);
   void RemoveDeadInstructions();
   bool SimplifyAlwaysThrows();
   bool SimplifyIfs();
@@ -49,10 +52,10 @@ class HDeadCodeElimination : public HOptimization {
   // 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
+  // Sets `any_block_in_loop` to true if any block is currently a loop to later update the loop
   // information if needed.
   void DisconnectHandlersAndUpdateTryBoundary(HBasicBlock* block,
-                                              /* out */ bool* any_handler_in_loop);
+                                              /* out */ bool* any_block_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
@@ -60,7 +63,7 @@ class HDeadCodeElimination : public HOptimization {
   // its successor.
   void RemoveTry(HBasicBlock* try_entry,
                  const TryBelongingInformation& try_belonging_info,
-                 bool* any_catch_in_loop);
+                 bool* any_block_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.
diff --git a/test/2244-checker-remove-try-boundary/src/Main.java b/test/2244-checker-remove-try-boundary/src/Main.java
index efc8ca75f8..1b616a5ecc 100644
--- a/test/2244-checker-remove-try-boundary/src/Main.java
+++ b/test/2244-checker-remove-try-boundary/src/Main.java
@@ -28,6 +28,7 @@ public class Main {
     assertEquals(10, $noinline$testRemoveTryBoundaryNested(60));
     assertEquals(-2000, $noinline$testRemoveTryBoundaryNestedButNotCatch(60, true));
     assertEquals(30, $noinline$testRemoveTryBoundaryNestedButNotCatch(60, false));
+    assertEquals(30, $noinline$testNestedTryBoundariesWithLoopAndCatchOutsideOfLoop(60, false));
   }
 
   public static void assertEquals(int expected, int result) {
@@ -280,4 +281,79 @@ public class Main {
     }
     return a;
   }
+
+  // We eliminate the return -1000 catch block which is outside of the loop in
+  // dead_code_elimination$initial. We can do so since we eliminated the TryBoundary of `a /= 2;`.
+
+  /// CHECK-START: int Main.$noinline$testNestedTryBoundariesWithLoopAndCatchOutsideOfLoop(int, boolean) dead_code_elimination$initial (before)
+  /// CHECK:     TryBoundary
+  /// CHECK:     TryBoundary
+  /// CHECK:     TryBoundary
+  /// CHECK:     TryBoundary
+  /// CHECK-NOT: TryBoundary
+
+  /// CHECK-START: int Main.$noinline$testNestedTryBoundariesWithLoopAndCatchOutsideOfLoop(int, boolean) dead_code_elimination$initial (before)
+  /// CHECK:     flags "catch_block"
+  /// CHECK:     flags "catch_block"
+  /// CHECK:     flags "catch_block"
+  /// CHECK-NOT: flags "catch_block"
+
+  /// CHECK-START: int Main.$noinline$testNestedTryBoundariesWithLoopAndCatchOutsideOfLoop(int, boolean) dead_code_elimination$initial (before)
+  /// CHECK:     IntConstant -1000
+
+  /// CHECK-START: int Main.$noinline$testNestedTryBoundariesWithLoopAndCatchOutsideOfLoop(int, boolean) dead_code_elimination$initial (after)
+  /// CHECK:     TryBoundary
+  /// CHECK:     TryBoundary
+  /// CHECK-NOT: TryBoundary
+
+  /// CHECK-START: int Main.$noinline$testNestedTryBoundariesWithLoopAndCatchOutsideOfLoop(int, boolean) dead_code_elimination$initial (after)
+  /// CHECK:     flags "catch_block"
+  /// CHECK:     flags "catch_block"
+  /// CHECK-NOT: flags "catch_block"
+
+  /// CHECK-START: int Main.$noinline$testNestedTryBoundariesWithLoopAndCatchOutsideOfLoop(int, boolean) dead_code_elimination$initial (after)
+  /// CHECK-NOT: IntConstant -1000
+
+  // When removing that block, we are removing a block outside of a loop but we still need to update
+  // the loop information in the graph since we removed TryBoundary instructions inside of a loop
+  // and now `a /= 2;` is not considered part of a loop (Cannot throw so it will not `continue` and
+  // will always return).
+
+  /// CHECK-START: int Main.$noinline$testNestedTryBoundariesWithLoopAndCatchOutsideOfLoop(int, boolean) dead_code_elimination$initial (before)
+  /// CHECK:     Div loop:B2
+
+  /// CHECK-START: int Main.$noinline$testNestedTryBoundariesWithLoopAndCatchOutsideOfLoop(int, boolean) dead_code_elimination$initial (after)
+  /// CHECK-NOT:  Div loop:B2
+
+  /// CHECK-START: int Main.$noinline$testNestedTryBoundariesWithLoopAndCatchOutsideOfLoop(int, boolean) dead_code_elimination$initial (after)
+  /// CHECK:      Div
+  /// CHECK-NOT:  Div
+  public static int $noinline$testNestedTryBoundariesWithLoopAndCatchOutsideOfLoop(
+          int a, boolean val) {
+    try {
+      for (int i = 0; i < 4; ++i) {
+        try {
+          try {
+            if (val) {
+              // TryBoundary kind:entry
+              throw new Error();
+              // TryBoundary kind:exit
+            }
+            // TryBoundary kind:exit
+          } catch (Exception e) {
+              continue;
+          }
+          // TryBoundary kind:entry
+          a /= 2;
+          // TryBoundary kind:exit
+          return a;
+        } catch (Error e) {
+          continue;
+        }
+      }
+    } catch (Exception e) {
+      return -1000;
+    }
+    return a;
+  }
 }