Code sinking cleanups

* Reword/refactor sinking throwing instructions
* Removed redundant GetSuccessors().empty() check
* Created a check in GraphCheker regarding no successors
* Update gtest to comply with the new check
* Typo fixes

Test: art/test/testrunner/testrunner.py --host --64 --optimizing -b
Change-Id: Ibf27266f29570a4b1b63bb9bd80e5906207527c0

1 files changed, 73 insertions, 80 deletions

diff --git a/compiler/optimizing/code_sinking.cc b/compiler/optimizing/code_sinking.cc
index 76885ec0a6..ac1cefe7c5 100644
--- a/compiler/optimizing/code_sinking.cc
+++ b/compiler/optimizing/code_sinking.cc
@@ -19,6 +19,7 @@
 #include "base/arena_bit_vector.h"
 #include "base/array_ref.h"
 #include "base/bit_vector-inl.h"
+#include "base/globals.h"
 #include "base/logging.h"
 #include "base/scoped_arena_allocator.h"
 #include "base/scoped_arena_containers.h"
@@ -105,7 +106,7 @@ static bool IsInterestingInstruction(HInstruction* instruction) {
 
   // We can only store on local allocations. Other heap references can
   // be escaping. Note that allocations can escape too, but we only move
-  // allocations if their users can move to, or are in the list of
+  // allocations if their users can move too, or are in the list of
   // post dominated blocks.
   if (instruction->IsInstanceFieldSet()) {
     if (!instruction->InputAt(0)->IsNewInstance()) {
@@ -119,7 +120,7 @@ static bool IsInterestingInstruction(HInstruction* instruction) {
     }
   }
 
-  // Heap accesses cannot go pass instructions that have memory side effects, which
+  // Heap accesses cannot go past instructions that have memory side effects, which
   // we are not tracking here. Note that the load/store elimination optimization
   // runs before this optimization, and should have removed interesting ones.
   // In theory, we could handle loads of local allocations, but this is currently
@@ -236,48 +237,42 @@ static HInstruction* FindIdealPosition(HInstruction* instruction,
     target_block = target_block->GetDominator();
     DCHECK(target_block != nullptr);
   }
-  const bool was_in_loop = target_block->IsInLoop();
-
-  // For throwing instructions we can move them into:
-  //   * Blocks that are not part of a try
-  //     * Catch blocks are suitable as well, as long as they are not part of an outer try.
-  //   * Blocks that are part of the same try that the instrucion was already in.
-  //
-  // We cannot move an instruction that can throw into a try that said instruction is not a part of
-  // already, as that would mean it will throw into a different catch block. If we detect that
-  // `target_block` is not a valid block to move `instruction` to, we traverse up the dominator tree
-  // to find if we have a suitable block.
-  while (instruction->CanThrow() && target_block->GetTryCatchInformation() != nullptr) {
-    if (target_block->IsCatchBlock()) {
-      // If the catch block has an xhandler, it means it is inside of an outer try.
-      const bool inside_of_another_try_catch = target_block->GetSuccessors().size() != 1;
-      if (!inside_of_another_try_catch) {
-        // If we have a catch block, it's okay to sink as long as that catch is not inside of
-        // another try catch.
-        break;
+
+  if (instruction->CanThrow()) {
+    // Consistency check: We shouldn't land in a loop if we weren't in one before traversing up the
+    // dominator tree regarding try catches.
+    const bool was_in_loop = target_block->IsInLoop();
+
+    // We cannot move an instruction that can throw into a try that said instruction is not a part
+    // of already, as that would mean it will throw into a different catch block. In short, for
+    // throwing instructions:
+    // * If the throwing instruction is part of a try, they should only be sunk into that same try.
+    // * If the throwing instruction is not part of any try, they shouldn't be sunk to any try.
+    if (instruction->GetBlock()->IsTryBlock()) {
+      const HTryBoundary& try_entry =
+          instruction->GetBlock()->GetTryCatchInformation()->GetTryEntry();
+      while (!(target_block->IsTryBlock() &&
+               try_entry.HasSameExceptionHandlersAs(
+                   target_block->GetTryCatchInformation()->GetTryEntry()))) {
+        target_block = target_block->GetDominator();
+        if (!post_dominated.IsBitSet(target_block->GetBlockId())) {
+          // We couldn't find a suitable block.
+          return nullptr;
+        }
       }
     } else {
-      DCHECK(target_block->IsTryBlock());
-      if (instruction->GetBlock()->IsTryBlock() &&
-          instruction->GetBlock()->GetTryCatchInformation()->GetTryEntry().GetId() ==
-              target_block->GetTryCatchInformation()->GetTryEntry().GetId()) {
-        // Sink within the same try block is allowed.
-        break;
+      // Search for the first block also not in a try block
+      while (target_block->IsTryBlock()) {
+        target_block = target_block->GetDominator();
+        if (!post_dominated.IsBitSet(target_block->GetBlockId())) {
+          // We couldn't find a suitable block.
+          return nullptr;
+        }
       }
     }
-    // We are now in the case where we would be moving to a different try. Since we don't want
-    // that, traverse up the dominator tree to find a suitable block.
-    if (!post_dominated.IsBitSet(target_block->GetDominator()->GetBlockId())) {
-      // We couldn't find a suitable block.
-      return nullptr;
-    }
-    target_block = target_block->GetDominator();
-    DCHECK(target_block != nullptr);
-  }
 
-  // We shouldn't land in a loop if we weren't in one before traversing up the dominator tree
-  // regarding try catches.
-  DCHECK_IMPLIES(target_block->IsInLoop(), was_in_loop);
+    DCHECK_IMPLIES(target_block->IsInLoop(), was_in_loop);
+  }
 
   // Find insertion position. No need to filter anymore, as we have found a
   // target block.
@@ -339,8 +334,8 @@ void CodeSinking::SinkCodeToUncommonBranch(HBasicBlock* end_block) {
   ScopedArenaVector<HInstruction*> move_in_order(allocator.Adapter(kArenaAllocMisc));
 
   // Step (1): Visit post order to get a subset of blocks post dominated by `end_block`.
-  // TODO(ngeoffray): Getting the full set of post-dominated shoud be done by
-  // computint the post dominator tree, but that could be too time consuming. Also,
+  // TODO(ngeoffray): Getting the full set of post-dominated should be done by
+  // computing the post dominator tree, but that could be too time consuming. Also,
   // we should start the analysis from blocks dominated by an uncommon branch, but we
   // don't profile branches yet.
   bool found_block = false;
@@ -350,45 +345,43 @@ void CodeSinking::SinkCodeToUncommonBranch(HBasicBlock* end_block) {
       post_dominated.SetBit(block->GetBlockId());
     } else if (found_block) {
       bool is_post_dominated = true;
-      if (block->GetSuccessors().empty()) {
-        // We currently bail for loops.
-        is_post_dominated = false;
-      } else {
-        // BasicBlock that are try entries look like this:
-        //   BasicBlock i:
-        //     instr 1
-        //     ...
-        //     instr N
-        //     TryBoundary kind:entry ---Try begins here---
-        //
-        // Due to how our BasicBlocks are structured, BasicBlock i will have an xhandler successor
-        // since we are starting a try. If we use `GetSuccessors` for this case, we will check if
-        // the catch block is post_dominated.
-        //
-        // However, this catch block doesn't matter: when we sink the instruction into that
-        // BasicBlock i, we do it before the TryBoundary (i.e. outside of the try and outside the
-        // catch's domain). We can ignore catch blocks using `GetNormalSuccessors` to sink code
-        // right before the start of a try block.
-        //
-        // On the other side of the coin, BasicBlock that are try exits look like this:
-        //   BasicBlock j:
-        //     instr 1
-        //     ...
-        //     instr N
-        //     TryBoundary kind:exit ---Try ends here---
-        //
-        // If we sink to these basic blocks we would be sinking inside of the try so we would like
-        // to check the catch block for post dominance.
-        const bool ends_with_try_boundary_entry =
-            block->EndsWithTryBoundary() && block->GetLastInstruction()->AsTryBoundary()->IsEntry();
-        ArrayRef<HBasicBlock* const> successors =
-            ends_with_try_boundary_entry ? block->GetNormalSuccessors() :
-                                           ArrayRef<HBasicBlock* const>(block->GetSuccessors());
-        for (HBasicBlock* successor : successors) {
-          if (!post_dominated.IsBitSet(successor->GetBlockId())) {
-            is_post_dominated = false;
-            break;
-          }
+      DCHECK_NE(block, graph_->GetExitBlock())
+          << "We shouldn't encounter the exit block after `end_block`.";
+
+      // BasicBlock that are try entries look like this:
+      //   BasicBlock i:
+      //     instr 1
+      //     ...
+      //     instr N
+      //     TryBoundary kind:entry ---Try begins here---
+      //
+      // Due to how our BasicBlocks are structured, BasicBlock i will have an xhandler successor
+      // since we are starting a try. If we use `GetSuccessors` for this case, we will check if
+      // the catch block is post_dominated.
+      //
+      // However, this catch block doesn't matter: when we sink the instruction into that
+      // BasicBlock i, we do it before the TryBoundary (i.e. outside of the try and outside the
+      // catch's domain). We can ignore catch blocks using `GetNormalSuccessors` to sink code
+      // right before the start of a try block.
+      //
+      // On the other side of the coin, BasicBlock that are try exits look like this:
+      //   BasicBlock j:
+      //     instr 1
+      //     ...
+      //     instr N
+      //     TryBoundary kind:exit ---Try ends here---
+      //
+      // If we sink to these basic blocks we would be sinking inside of the try so we would like
+      // to check the catch block for post dominance.
+      const bool ends_with_try_boundary_entry =
+          block->EndsWithTryBoundary() && block->GetLastInstruction()->AsTryBoundary()->IsEntry();
+      ArrayRef<HBasicBlock* const> successors =
+          ends_with_try_boundary_entry ? block->GetNormalSuccessors() :
+                                         ArrayRef<HBasicBlock* const>(block->GetSuccessors());
+      for (HBasicBlock* successor : successors) {
+        if (!post_dominated.IsBitSet(successor->GetBlockId())) {
+          is_post_dominated = false;
+          break;
         }
       }
       if (is_post_dominated) {