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
diff --git a/compiler/optimizing/code_generator.cc b/compiler/optimizing/code_generator.cc
index a164b15..a353d07 100644
--- a/compiler/optimizing/code_generator.cc
+++ b/compiler/optimizing/code_generator.cc
@@ -1114,7 +1114,7 @@
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 d1769ce..55a505c 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -674,13 +674,14 @@
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 02ee4ec..cd05482 100644
--- a/compiler/optimizing/loop_optimization.cc
+++ b/compiler/optimizing/loop_optimization.cc
@@ -636,6 +636,47 @@
}
//
+// 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::OptimizeInnerLoop(LoopNode* node) {
- return TryOptimizeInnerLoopFinite(node) || TryPeelingAndUnrolling(node);
+ return TryOptimizeInnerLoopFinite(node) || TryLoopScalarOpts(node);
}
@@ -885,7 +926,7 @@
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 @@
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 @@
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 d3583ed..0ca16b5 100644
--- a/compiler/optimizing/loop_optimization.h
+++ b/compiler/optimizing/loop_optimization.h
@@ -47,6 +47,11 @@
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 @@
// 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 69ca520..d6b3726 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -675,6 +675,13 @@
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 0000000..e69de29
--- /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 0000000..e69de29
--- /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 0000000..fe8d8eb
--- /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 0000000..f943f38
--- /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);
+ }
+}