ART: Removes SuspendCheck for plain loops with a low trip count.

This change removes SuspendCheck for plain loops with a low trip count.

The SuspendCheck in the codegen makes sure that the thread can be
interrupted during execution for GC. Not being able to do so might
decrease the responsiveness of GC in the case when a very long loop
or a long recursion is being executed.

However, for plain loops with a small trip count, the removal of
SuspendCheck should not affect the GC's responsiveness by a large
margin. Consequently, since the thread won't be interrupted for
plain loops, it is assumed that the performance might increase
by removing SuspendCheck.

Test: art/test.py -v -j12 --host --64 -t 2233-checker\
-remove-loop-suspend-check --run-test --optimizing

Change-Id: Ic9f1387059669645ad836d8277bfbc7553aa6e2f

9 files changed, 168 insertions, 12 deletions

diff --git a/compiler/optimizing/code_generator.cc b/compiler/optimizing/code_generator.cc
index a164b15a04..a353d0758e 100644
--- a/compiler/optimizing/code_generator.cc
+++ b/compiler/optimizing/code_generator.cc
@@ -1114,7 +1114,7 @@ static void CheckLoopEntriesCanBeUsedForOsr(const HGraph& graph,
   for (HBasicBlock* block : graph.GetReversePostOrder()) {
     if (block->IsLoopHeader()) {
       HSuspendCheck* suspend_check = block->GetLoopInformation()->GetSuspendCheck();
-      if (!suspend_check->GetEnvironment()->IsFromInlinedInvoke()) {
+      if (suspend_check != nullptr && !suspend_check->GetEnvironment()->IsFromInlinedInvoke()) {
         loop_headers.push_back(suspend_check);
       }
     }
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index d1769cea0d..55a505c5ea 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -674,13 +674,14 @@ void GraphChecker::HandleLoop(HBasicBlock* loop_header) {
         loop_information->GetPreHeader()->GetSuccessors().size()));
   }
 
-  if (loop_information->GetSuspendCheck() == nullptr) {
-    AddError(StringPrintf(
-        "Loop with header %d does not have a suspend check.",
-        loop_header->GetBlockId()));
+  if (!GetGraph()->SuspendChecksAreAllowedToBeRemoved() &&
+      loop_information->GetSuspendCheck() == nullptr) {
+    AddError(StringPrintf("Loop with header %d does not have a suspend check.",
+                          loop_header->GetBlockId()));
   }
 
-  if (loop_information->GetSuspendCheck() != loop_header->GetFirstInstructionDisregardMoves()) {
+  if (!GetGraph()->SuspendChecksAreAllowedToBeRemoved() &&
+      loop_information->GetSuspendCheck() != loop_header->GetFirstInstructionDisregardMoves()) {
     AddError(StringPrintf(
         "Loop header %d does not have the loop suspend check as the first instruction.",
         loop_header->GetBlockId()));
diff --git a/compiler/optimizing/loop_optimization.cc b/compiler/optimizing/loop_optimization.cc
index 02ee4ec057..cd054822cd 100644
--- a/compiler/optimizing/loop_optimization.cc
+++ b/compiler/optimizing/loop_optimization.cc
@@ -636,6 +636,47 @@ bool HLoopOptimization::TraverseLoopsInnerToOuter(LoopNode* node) {
 }
 
 //
+// This optimization applies to loops with plain simple operations
+// (I.e. no calls to java code or runtime) with a known small trip_count * instr_count
+// value.
+//
+bool HLoopOptimization::TryToRemoveSuspendCheckFromLoopHeader(LoopAnalysisInfo* analysis_info,
+                                                              bool generate_code) {
+  if (!graph_->SuspendChecksAreAllowedToBeRemoved()) {
+    return false;
+  }
+
+  int64_t trip_count = analysis_info->GetTripCount();
+
+  if (trip_count == LoopAnalysisInfo::kUnknownTripCount) {
+    return false;
+  }
+
+  int64_t instruction_count = analysis_info->GetNumberOfInstructions();
+  int64_t total_instruction_count = trip_count * instruction_count;
+
+  // The inclusion of the HasInstructionsPreventingScalarOpts() prevents this
+  // optimization from being applied to loops that have calls.
+  bool can_optimize =
+      total_instruction_count <= HLoopOptimization::kMaxTotalInstRemoveSuspendCheck &&
+      !analysis_info->HasInstructionsPreventingScalarOpts();
+
+  if (!can_optimize) {
+    return false;
+  }
+
+  if (generate_code) {
+    HLoopInformation* loop_info = analysis_info->GetLoopInfo();
+    HBasicBlock* header = loop_info->GetHeader();
+    HInstruction* instruction = header->GetLoopInformation()->GetSuspendCheck();
+    header->RemoveInstruction(instruction);
+    loop_info->SetSuspendCheck(nullptr);
+  }
+
+  return true;
+}
+
+//
 // Optimization.
 //
 
@@ -779,7 +820,7 @@ bool HLoopOptimization::TryOptimizeInnerLoopFinite(LoopNode* node) {
 }
 
 bool HLoopOptimization::OptimizeInnerLoop(LoopNode* node) {
-  return TryOptimizeInnerLoopFinite(node) || TryPeelingAndUnrolling(node);
+  return TryOptimizeInnerLoopFinite(node) || TryLoopScalarOpts(node);
 }
 
 
@@ -885,7 +926,7 @@ bool HLoopOptimization::TryFullUnrolling(LoopAnalysisInfo* analysis_info, bool g
   return true;
 }
 
-bool HLoopOptimization::TryPeelingAndUnrolling(LoopNode* node) {
+bool HLoopOptimization::TryLoopScalarOpts(LoopNode* node) {
   HLoopInformation* loop_info = node->loop_info;
   int64_t trip_count = LoopAnalysis::GetLoopTripCount(loop_info, &induction_range_);
   LoopAnalysisInfo analysis_info(loop_info);
@@ -898,10 +939,16 @@ bool HLoopOptimization::TryPeelingAndUnrolling(LoopNode* node) {
 
   if (!TryFullUnrolling(&analysis_info, /*generate_code*/ false) &&
       !TryPeelingForLoopInvariantExitsElimination(&analysis_info, /*generate_code*/ false) &&
-      !TryUnrollingForBranchPenaltyReduction(&analysis_info, /*generate_code*/ false)) {
+      !TryUnrollingForBranchPenaltyReduction(&analysis_info, /*generate_code*/ false) &&
+      !TryToRemoveSuspendCheckFromLoopHeader(&analysis_info, /*generate_code*/ false)) {
     return false;
   }
 
+  // Try the suspend check removal even for non-clonable loops. Also this
+  // optimization doesn't interfere with other scalar loop optimizations so it can
+  // be done prior to them.
+  bool removed_suspend_check = TryToRemoveSuspendCheckFromLoopHeader(&analysis_info);
+
   // Run 'IsLoopClonable' the last as it might be time-consuming.
   if (!LoopClonerHelper::IsLoopClonable(loop_info)) {
     return false;
@@ -909,7 +956,7 @@ bool HLoopOptimization::TryPeelingAndUnrolling(LoopNode* node) {
 
   return TryFullUnrolling(&analysis_info) ||
          TryPeelingForLoopInvariantExitsElimination(&analysis_info) ||
-         TryUnrollingForBranchPenaltyReduction(&analysis_info);
+         TryUnrollingForBranchPenaltyReduction(&analysis_info) || removed_suspend_check;
 }
 
 //
diff --git a/compiler/optimizing/loop_optimization.h b/compiler/optimizing/loop_optimization.h
index d3583ed8a6..0ca16b543d 100644
--- a/compiler/optimizing/loop_optimization.h
+++ b/compiler/optimizing/loop_optimization.h
@@ -47,6 +47,11 @@ class HLoopOptimization : public HOptimization {
 
   static constexpr const char* kLoopOptimizationPassName = "loop_optimization";
 
+  // The maximum number of total instructions (trip_count * instruction_count),
+  // where the optimization of removing SuspendChecks from the loop header could
+  // be performed.
+  static constexpr int64_t kMaxTotalInstRemoveSuspendCheck = 128;
+
  private:
   /**
    * A single loop inside the loop hierarchy representation.
@@ -163,8 +168,19 @@ class HLoopOptimization : public HOptimization {
   // should be actually applied.
   bool TryFullUnrolling(LoopAnalysisInfo* analysis_info, bool generate_code = true);
 
-  // Tries to apply scalar loop peeling and unrolling.
-  bool TryPeelingAndUnrolling(LoopNode* node);
+  // Tries to remove SuspendCheck for plain loops with a low trip count. The
+  // SuspendCheck in the codegen makes sure that the thread can be interrupted
+  // during execution for GC. Not being able to do so might decrease the
+  // responsiveness of GC when a very long loop or a long recursion is being
+  // executed. However, for plain loops with a small trip count, the removal of
+  // SuspendCheck should not affect the GC's responsiveness by a large margin.
+  // Consequently, since the thread won't be interrupted for plain loops, it is
+  // assumed that the performance might increase by removing SuspendCheck.
+  bool TryToRemoveSuspendCheckFromLoopHeader(LoopAnalysisInfo* analysis_info,
+                                             bool generate_code = true);
+
+  // Tries to apply scalar loop optimizations.
+  bool TryLoopScalarOpts(LoopNode* node);
 
   //
   // Vectorization analysis and synthesis.
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 69ca520f5a..d6b3726fe1 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -675,6 +675,13 @@ class HGraph : public ArenaObject<kArenaAllocGraph> {
     return cha_single_implementation_list_;
   }
 
+  // In case of OSR we intend to use SuspendChecks as an entry point to the
+  // function; for debuggable graphs we might deoptimize to interpreter from
+  // SuspendChecks. In these cases we shouldn't remove them.
+  bool SuspendChecksAreAllowedToBeRemoved() const {
+    return !IsDebuggable() && !IsCompilingOsr();
+  }
+
   void AddCHASingleImplementationDependency(ArtMethod* method) {
     cha_single_implementation_list_.insert(method);
   }
diff --git a/test/2233-checker-remove-loop-suspend-check/expected-stderr.txt b/test/2233-checker-remove-loop-suspend-check/expected-stderr.txt
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/test/2233-checker-remove-loop-suspend-check/expected-stderr.txt
diff --git a/test/2233-checker-remove-loop-suspend-check/expected-stdout.txt b/test/2233-checker-remove-loop-suspend-check/expected-stdout.txt
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/test/2233-checker-remove-loop-suspend-check/expected-stdout.txt
diff --git a/test/2233-checker-remove-loop-suspend-check/info.txt b/test/2233-checker-remove-loop-suspend-check/info.txt
new file mode 100644
index 0000000000..fe8d8eb3c5
--- /dev/null
+++ b/test/2233-checker-remove-loop-suspend-check/info.txt
@@ -0,0 +1 @@
+Test to check the removal of SuspendCheck for finite simple plain loops.
diff --git a/test/2233-checker-remove-loop-suspend-check/src/Main.java b/test/2233-checker-remove-loop-suspend-check/src/Main.java
new file mode 100644
index 0000000000..f943f381f1
--- /dev/null
+++ b/test/2233-checker-remove-loop-suspend-check/src/Main.java
@@ -0,0 +1,84 @@
+/*
+ * Copyright (C) 2021 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+public class Main {
+
+  static final int ITERATIONS = 16;
+
+  // Test 1: This test checks whether the SuspendCheck is removed from the
+  // header.
+
+  /// CHECK-START: void Main.$noinline$testRemoveSuspendCheck(int[]) loop_optimization (before)
+  /// CHECK:       SuspendCheck         loop:{{B\d+}}
+  /// CHECK-START: void Main.$noinline$testRemoveSuspendCheck(int[]) loop_optimization (after)
+  /// CHECK-NOT:   SuspendCheck         loop:{{B\d+}}
+  public static void $noinline$testRemoveSuspendCheck(int[] a) {
+    for (int i = 0; i < ITERATIONS; i++) {
+      a[i++] = i;
+    }
+  }
+
+  // Test 2: This test checks that the SuspendCheck is not removed from the
+  // header because it contains a call to another function.
+
+  /// CHECK-START: void Main.testRemoveSuspendCheckWithCall(int[]) loop_optimization (before)
+  /// CHECK:       SuspendCheck         loop:{{B\d+}}
+  /// CHECK-START: void Main.testRemoveSuspendCheckWithCall(int[]) loop_optimization (after)
+  /// CHECK:       SuspendCheck         loop:{{B\d+}}
+
+  public static void testRemoveSuspendCheckWithCall(int[] a) {
+    for (int i = 0; i < ITERATIONS; i++) {
+      a[i++] = i;
+      $noinline$testRemoveSuspendCheck(a);
+    }
+  }
+
+  // Test 3:  This test checks that the SuspendCheck is not removed from the
+  // header because INSTR_COUNT * TRIP_COUNT exceeds the defined heuristic.
+
+  /// CHECK-START: void Main.testRemoveSuspendCheckAboveHeuristic(int[]) loop_optimization (before)
+  /// CHECK:       SuspendCheck         loop:{{B\d+}}
+  /// CHECK-START: void Main.testRemoveSuspendCheckAboveHeuristic(int[]) loop_optimization (after)
+  /// CHECK:       SuspendCheck         loop:{{B\d+}}
+
+  public static void testRemoveSuspendCheckAboveHeuristic(int[] a) {
+    for (int i = 0; i < ITERATIONS * 6; i++) {
+      a[i++] = i;
+    }
+  }
+
+  // Test 4:  This test checks that the SuspendCheck is not removed from the
+  // header because the trip count is not known at compile time.
+
+  /// CHECK-START: void Main.testRemoveSuspendCheckUnknownCount(int[], int) loop_optimization (before)
+  /// CHECK:       SuspendCheck         loop:{{B\d+}}
+  /// CHECK-START: void Main.testRemoveSuspendCheckUnknownCount(int[], int) loop_optimization (after)
+  /// CHECK:       SuspendCheck         loop:{{B\d+}}
+
+  public static void testRemoveSuspendCheckUnknownCount(int[] a, int n) {
+    for (int i = 0; i < n; i++) {
+      a[i++] = i;
+    }
+  }
+
+  public static void main(String[] args) {
+    int[] a = new int[100];
+    $noinline$testRemoveSuspendCheck(a);
+    testRemoveSuspendCheckWithCall(a);
+    testRemoveSuspendCheckAboveHeuristic(a);
+    testRemoveSuspendCheckUnknownCount(a, 4);
+  }
+}