Combine offsets in loop-based dynamic BCE.
Rationale:
Similar to what I did recently for dom-based dynamic BCE, this
CL combines offsets for the tests generated for loop-based
dynamic BCE. For a set of n references, this reduces the
number of generated tests from 2*n+1 down to at most 4
(in some cases even less).
TEST: 530-checker-loops3
BUG=27430379
Change-Id: Ic80c2563eaae23f514c1fd52965dd83bccb9d190
diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index 1fc247f..8aefd9e 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -533,9 +533,6 @@
first_index_bounds_check_map_(
std::less<int>(),
graph->GetArena()->Adapter(kArenaAllocBoundsCheckElimination)),
- dynamic_bce_standby_(
- graph->GetArena()->Adapter(kArenaAllocBoundsCheckElimination)),
- record_dynamic_bce_standby_(true),
early_exit_loop_(
std::less<uint32_t>(),
graph->GetArena()->Adapter(kArenaAllocBoundsCheckElimination)),
@@ -560,14 +557,6 @@
}
void Finish() {
- // Retry dynamic bce candidates on standby that are still in the graph.
- record_dynamic_bce_standby_ = false;
- for (HBoundsCheck* bounds_check : dynamic_bce_standby_) {
- if (bounds_check->IsInBlock()) {
- TryDynamicBCE(bounds_check);
- }
- }
-
// Preserve SSA structure which may have been broken by adding one or more
// new taken-test structures (see TransformLoopForDeoptimizationIfNeeded()).
InsertPhiNodes();
@@ -576,7 +565,6 @@
early_exit_loop_.clear();
taken_test_loop_.clear();
finite_loop_.clear();
- dynamic_bce_standby_.clear();
}
private:
@@ -832,7 +820,6 @@
array_length->IsArrayLength() ||
array_length->IsPhi());
bool try_dynamic_bce = true;
-
// Analyze index range.
if (!index->IsIntConstant()) {
// Non-constant index.
@@ -896,10 +883,20 @@
// If static analysis fails, and OOB is not certain, try dynamic elimination.
if (try_dynamic_bce) {
// Try loop-based dynamic elimination.
- if (TryDynamicBCE(bounds_check)) {
+ HLoopInformation* loop = bounds_check->GetBlock()->GetLoopInformation();
+ bool needs_finite_test = false;
+ bool needs_taken_test = false;
+ if (DynamicBCESeemsProfitable(loop, bounds_check->GetBlock()) &&
+ induction_range_.CanGenerateCode(
+ bounds_check, index, &needs_finite_test, &needs_taken_test) &&
+ CanHandleInfiniteLoop(loop, index, needs_finite_test) &&
+ // Do this test last, since it may generate code.
+ CanHandleLength(loop, array_length, needs_taken_test)) {
+ TransformLoopForDeoptimizationIfNeeded(loop, needs_taken_test);
+ TransformLoopForDynamicBCE(loop, bounds_check);
return;
}
- // Prepare dominator-based dynamic elimination.
+ // Otherwise, prepare dominator-based dynamic elimination.
if (first_index_bounds_check_map_.find(array_length->GetId()) ==
first_index_bounds_check_map_.end()) {
// Remember the first bounds check against each array_length. That bounds check
@@ -1180,7 +1177,7 @@
}
}
- // Perform dominator-based dynamic elimination on suitable set of bounds checks.
+ /** Performs dominator-based dynamic elimination on suitable set of bounds checks. */
void AddCompareWithDeoptimization(HBasicBlock* block,
HInstruction* array_length,
HInstruction* base,
@@ -1190,6 +1187,12 @@
// Construct deoptimization on single or double bounds on range [base-min_c,base+max_c],
// for example either for a[0]..a[3] just 3 or for a[base-1]..a[base+3] both base-1
// and base+3, since we made the assumption any in between value may occur too.
+ // In code, using unsigned comparisons:
+ // (1) constants only
+ // if (max_c >= a.length) deoptimize;
+ // (2) general case
+ // if (base-min_c > base+max_c) deoptimize;
+ // if (base+max_c >= a.length ) deoptimize;
static_assert(kMaxLengthForAddingDeoptimize < std::numeric_limits<int32_t>::max(),
"Incorrect max length may be subject to arithmetic wrap-around");
HInstruction* upper = GetGraph()->GetIntConstant(max_c);
@@ -1208,7 +1211,7 @@
has_dom_based_dynamic_bce_ = true;
}
- // Attempt dominator-based dynamic elimination on remaining candidates.
+ /** Attempts dominator-based dynamic elimination on remaining candidates. */
void AddComparesWithDeoptimization(HBasicBlock* block) {
for (const auto& entry : first_index_bounds_check_map_) {
HBoundsCheck* bounds_check = entry.second;
@@ -1272,17 +1275,19 @@
candidates.push_back(other_bounds_check);
}
}
- // Perform dominator-based deoptimization if it seems profitable. Note that we reject cases
- // where the distance min_c:max_c range gets close to the maximum possible array length,
- // since those cases are likely to always deopt (such situations do not necessarily go
- // OOB, though, since the programmer could rely on wrap-around from max to min).
+ // Perform dominator-based deoptimization if it seems profitable, where we eliminate
+ // bounds checks and replace these with deopt checks that guard against any possible
+ // OOB. Note that we reject cases where the distance min_c:max_c range gets close to
+ // the maximum possible array length, since those cases are likely to always deopt
+ // (such situations do not necessarily go OOB, though, since the array could be really
+ // large, or the programmer could rely on arithmetic wrap-around from max to min).
size_t threshold = kThresholdForAddingDeoptimize + (base == nullptr ? 0 : 1); // extra test?
uint32_t distance = static_cast<uint32_t>(max_c) - static_cast<uint32_t>(min_c);
if (candidates.size() >= threshold &&
(base != nullptr || min_c >= 0) && // reject certain OOB
distance <= kMaxLengthForAddingDeoptimize) { // reject likely/certain deopt
AddCompareWithDeoptimization(block, array_length, base, min_c, max_c);
- for (HInstruction* other_bounds_check : candidates) {
+ for (HBoundsCheck* other_bounds_check : candidates) {
// Only replace if still in the graph. This avoids visiting the same
// bounds check twice if it occurred multiple times in the use list.
if (other_bounds_check->IsInBlock()) {
@@ -1328,45 +1333,127 @@
}
/**
- * When the compiler fails to remove a bounds check statically, we try to remove the bounds
- * check dynamically by adding runtime tests that trigger a deoptimization in case bounds
- * will go out of range (we want to be rather certain of that given the slowdown of
- * deoptimization). If no deoptimization occurs, the loop is executed with all corresponding
- * bounds checks and related null checks removed.
+ * Performs loop-based dynamic elimination on a bounds check. In order to minimize the
+ * number of eventually generated tests, related bounds checks with tests that can be
+ * combined with tests for the given bounds check are collected first.
*/
- bool TryDynamicBCE(HBoundsCheck* instruction) {
- HLoopInformation* loop = instruction->GetBlock()->GetLoopInformation();
- HInstruction* index = instruction->InputAt(0);
- HInstruction* length = instruction->InputAt(1);
- // If dynamic bounds check elimination seems profitable and is possible, then proceed.
- bool needs_finite_test = false;
- bool needs_taken_test = false;
- if (DynamicBCESeemsProfitable(loop, instruction->GetBlock()) &&
- induction_range_.CanGenerateCode(
- instruction, index, &needs_finite_test, &needs_taken_test) &&
- CanHandleInfiniteLoop(loop, instruction, index, needs_finite_test) &&
- CanHandleLength(loop, length, needs_taken_test)) { // do this test last (may code gen)
- HInstruction* lower = nullptr;
- HInstruction* upper = nullptr;
- // Generate the following unsigned comparisons
- // if (lower > upper) deoptimize;
- // if (upper >= length) deoptimize;
- // or, for a non-induction index, just the unsigned comparison on its 'upper' value
- // if (upper >= length) deoptimize;
- // as runtime test. By restricting dynamic bce to unit strides (with a maximum of 32-bit
- // iterations) and by not combining access (e.g. a[i], a[i-3], a[i+5] etc.), these tests
- // correctly guard against any possible OOB (including arithmetic wrap-around cases).
- TransformLoopForDeoptimizationIfNeeded(loop, needs_taken_test);
- HBasicBlock* block = GetPreHeader(loop, instruction);
- induction_range_.GenerateRangeCode(instruction, index, GetGraph(), block, &lower, &upper);
- if (lower != nullptr) {
- InsertDeoptInLoop(loop, block, new (GetGraph()->GetArena()) HAbove(lower, upper));
+ void TransformLoopForDynamicBCE(HLoopInformation* loop, HBoundsCheck* bounds_check) {
+ HInstruction* index = bounds_check->InputAt(0);
+ HInstruction* array_length = bounds_check->InputAt(1);
+ DCHECK(loop->IsDefinedOutOfTheLoop(array_length)); // pre-checked
+ DCHECK(loop->DominatesAllBackEdges(bounds_check->GetBlock()));
+ // Collect all bounds checks in the same loop that are related as "a[base + constant]"
+ // for a base instruction (possibly absent) and various constants.
+ ValueBound value = ValueBound::AsValueBound(index);
+ HInstruction* base = value.GetInstruction();
+ int32_t min_c = base == nullptr ? 0 : value.GetConstant();
+ int32_t max_c = value.GetConstant();
+ ArenaVector<HBoundsCheck*> candidates(
+ GetGraph()->GetArena()->Adapter(kArenaAllocBoundsCheckElimination));
+ ArenaVector<HBoundsCheck*> standby(
+ GetGraph()->GetArena()->Adapter(kArenaAllocBoundsCheckElimination));
+ for (const HUseListNode<HInstruction*>& use : array_length->GetUses()) {
+ HInstruction* user = use.GetUser();
+ if (user->IsBoundsCheck() && loop == user->GetBlock()->GetLoopInformation()) {
+ HBoundsCheck* other_bounds_check = user->AsBoundsCheck();
+ HInstruction* other_index = other_bounds_check->InputAt(0);
+ HInstruction* other_array_length = other_bounds_check->InputAt(1);
+ ValueBound other_value = ValueBound::AsValueBound(other_index);
+ int32_t other_c = other_value.GetConstant();
+ if (array_length == other_array_length && base == other_value.GetInstruction()) {
+ // Does the current basic block dominate all back edges? If not,
+ // add this candidate later only if it falls into the range.
+ if (!loop->DominatesAllBackEdges(user->GetBlock())) {
+ standby.push_back(other_bounds_check);
+ continue;
+ }
+ min_c = std::min(min_c, other_c);
+ max_c = std::max(max_c, other_c);
+ candidates.push_back(other_bounds_check);
+ }
}
- InsertDeoptInLoop(loop, block, new (GetGraph()->GetArena()) HAboveOrEqual(upper, length));
- ReplaceInstruction(instruction, index);
- return true;
}
- return false;
+ // Add standby candidates that fall in selected range.
+ for (HBoundsCheck* other_bounds_check : standby) {
+ HInstruction* other_index = other_bounds_check->InputAt(0);
+ int32_t other_c = ValueBound::AsValueBound(other_index).GetConstant();
+ if (min_c <= other_c && other_c <= max_c) {
+ candidates.push_back(other_bounds_check);
+ }
+ }
+ // Perform loop-based deoptimization if it seems profitable, where we eliminate bounds
+ // checks and replace these with deopt checks that guard against any possible OOB.
+ DCHECK_LT(0u, candidates.size());
+ uint32_t distance = static_cast<uint32_t>(max_c) - static_cast<uint32_t>(min_c);
+ if ((base != nullptr || min_c >= 0) && // reject certain OOB
+ distance <= kMaxLengthForAddingDeoptimize) { // reject likely/certain deopt
+ HBasicBlock* block = GetPreHeader(loop, bounds_check);
+ HInstruction* min_lower = nullptr;
+ HInstruction* min_upper = nullptr;
+ HInstruction* max_lower = nullptr;
+ HInstruction* max_upper = nullptr;
+ // Iterate over all bounds checks.
+ for (HBoundsCheck* other_bounds_check : candidates) {
+ // Only handle if still in the graph. This avoids visiting the same
+ // bounds check twice if it occurred multiple times in the use list.
+ if (other_bounds_check->IsInBlock()) {
+ HInstruction* other_index = other_bounds_check->InputAt(0);
+ int32_t other_c = ValueBound::AsValueBound(other_index).GetConstant();
+ // Generate code for either the maximum or minimum. Range analysis already was queried
+ // whether code generation on the original and, thus, related bounds check was possible.
+ // It handles either loop invariants (lower is not set) or unit strides.
+ if (other_c == max_c) {
+ induction_range_.GenerateRangeCode(
+ other_bounds_check, other_index, GetGraph(), block, &max_lower, &max_upper);
+ } else if (other_c == min_c && base != nullptr) {
+ induction_range_.GenerateRangeCode(
+ other_bounds_check, other_index, GetGraph(), block, &min_lower, &min_upper);
+ }
+ ReplaceInstruction(other_bounds_check, other_index);
+ }
+ }
+ // In code, using unsigned comparisons:
+ // (1) constants only
+ // if (max_upper >= a.length ) deoptimize;
+ // (2) two symbolic invariants
+ // if (min_upper > max_upper) deoptimize; unless min_c == max_c
+ // if (max_upper >= a.length ) deoptimize;
+ // (3) general case, unit strides (where lower would exceed upper for arithmetic wrap-around)
+ // if (min_lower > max_lower) deoptimize; unless min_c == max_c
+ // if (max_lower > max_upper) deoptimize;
+ // if (max_upper >= a.length ) deoptimize;
+ if (base == nullptr) {
+ // Constants only.
+ DCHECK_GE(min_c, 0);
+ DCHECK(min_lower == nullptr && min_upper == nullptr &&
+ max_lower == nullptr && max_upper != nullptr);
+ } else if (max_lower == nullptr) {
+ // Two symbolic invariants.
+ if (min_c != max_c) {
+ DCHECK(min_lower == nullptr && min_upper != nullptr &&
+ max_lower == nullptr && max_upper != nullptr);
+ InsertDeoptInLoop(loop, block, new (GetGraph()->GetArena()) HAbove(min_upper, max_upper));
+ } else {
+ DCHECK(min_lower == nullptr && min_upper == nullptr &&
+ max_lower == nullptr && max_upper != nullptr);
+ }
+ } else {
+ // General case, unit strides.
+ if (min_c != max_c) {
+ DCHECK(min_lower != nullptr && min_upper != nullptr &&
+ max_lower != nullptr && max_upper != nullptr);
+ InsertDeoptInLoop(loop, block, new (GetGraph()->GetArena()) HAbove(min_lower, max_lower));
+ } else {
+ DCHECK(min_lower == nullptr && min_upper == nullptr &&
+ max_lower != nullptr && max_upper != nullptr);
+ }
+ InsertDeoptInLoop(loop, block, new (GetGraph()->GetArena()) HAbove(max_lower, max_upper));
+ }
+ InsertDeoptInLoop(
+ loop, block, new (GetGraph()->GetArena()) HAboveOrEqual(max_upper, array_length));
+ } else {
+ // TODO: if rejected, avoid doing this again for subsequent instructions in this set?
+ }
}
/**
@@ -1474,8 +1561,7 @@
* of the loop to use, dynamic bce in such cases is only allowed if other tests
* ensure the loop is finite.
*/
- bool CanHandleInfiniteLoop(
- HLoopInformation* loop, HBoundsCheck* check, HInstruction* index, bool needs_infinite_test) {
+ bool CanHandleInfiniteLoop(HLoopInformation* loop, HInstruction* index, bool needs_infinite_test) {
if (needs_infinite_test) {
// If we already forced the loop to be finite, allow directly.
const uint32_t loop_id = loop->GetHeader()->GetBlockId();
@@ -1497,11 +1583,6 @@
}
}
}
- // If bounds check made it this far, it is worthwhile to check later if
- // the loop was forced finite by another candidate.
- if (record_dynamic_bce_standby_) {
- dynamic_bce_standby_.push_back(check);
- }
return false;
}
return true;
@@ -1727,10 +1808,6 @@
// in a block that checks an index against that HArrayLength.
ArenaSafeMap<int, HBoundsCheck*> first_index_bounds_check_map_;
- // Stand by list for dynamic bce.
- ArenaVector<HBoundsCheck*> dynamic_bce_standby_;
- bool record_dynamic_bce_standby_;
-
// Early-exit loop bookkeeping.
ArenaSafeMap<uint32_t, bool> early_exit_loop_;
diff --git a/test/449-checker-bce/src/Main.java b/test/449-checker-bce/src/Main.java
index 41771b5..c125e33 100644
--- a/test/449-checker-bce/src/Main.java
+++ b/test/449-checker-bce/src/Main.java
@@ -1204,9 +1204,6 @@
/// CHECK: Deoptimize
/// CHECK: Deoptimize
/// CHECK: Deoptimize
- /// CHECK: Deoptimize
- /// CHECK: Deoptimize
- /// CHECK: Deoptimize
/// CHECK-NOT: Deoptimize
/// CHECK: Goto
/// CHECK: Goto
@@ -1217,7 +1214,7 @@
for (int i = array.length - 1 ; i >= 0; i--) {
array[i] = 1;
}
- // Several HDeoptimize will be added. Two for each index.
+ // Three HDeoptimize will be added for the bounds.
// The null check is not necessary.
for (int i = end - 2 ; i > 0; i--) {
if (expectInterpreter) {
@@ -1266,20 +1263,12 @@
/// CHECK: Deoptimize
/// CHECK: Deoptimize
/// CHECK: Deoptimize
- /// CHECK: Deoptimize
- /// CHECK: Deoptimize
- /// CHECK: Deoptimize
- /// CHECK: Deoptimize
- /// CHECK: Deoptimize
- /// CHECK: Deoptimize
- /// CHECK: Deoptimize
/// CHECK-NOT: Deoptimize
/// CHECK: Goto
/// CHECK: Goto
/// CHECK: Goto
void foo6(int[] array, int start, int end, boolean expectInterpreter) {
- // Several HDeoptimize will be added.
for (int i = end; i >= start; i--) {
if (expectInterpreter) {
assertIsInterpreted();
@@ -1398,8 +1387,8 @@
/// CHECK-NOT: Deoptimize
void foo9(int[] array, boolean expectInterpreter) {
- // Two HDeoptimize will be added. Two for the index
- // and one for null check on array.
+ // Three HDeoptimize will be added. Two for the index and one for null check on array. Then
+ // simplification removes one redundant HDeoptimize.
for (int i = 0 ; i < 10; i++) {
if (expectInterpreter) {
assertIsInterpreted();
diff --git a/test/530-checker-loops3/expected.txt b/test/530-checker-loops3/expected.txt
new file mode 100644
index 0000000..b0aad4d
--- /dev/null
+++ b/test/530-checker-loops3/expected.txt
@@ -0,0 +1 @@
+passed
diff --git a/test/530-checker-loops3/info.txt b/test/530-checker-loops3/info.txt
new file mode 100644
index 0000000..07d99a3
--- /dev/null
+++ b/test/530-checker-loops3/info.txt
@@ -0,0 +1 @@
+Test on loop optimizations, in particular loop-based dynamic bce.
diff --git a/test/530-checker-loops3/src/Main.java b/test/530-checker-loops3/src/Main.java
new file mode 100644
index 0000000..5ffcbe9
--- /dev/null
+++ b/test/530-checker-loops3/src/Main.java
@@ -0,0 +1,327 @@
+/*
+ * Copyright (C) 2016 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.
+ */
+
+//
+// Test on loop optimizations, in particular dynamic BCE. In all cases,
+// bounds check on a[] is resolved statically. Bounds checks on b[]
+// exercise various different scenarios. In all cases, loop-based
+// dynamic BCE is better than the dominator-based BCE, since it
+// generates the test outside the loop.
+//
+public class Main {
+
+ /// CHECK-START: void Main.oneConstantIndex(int[], int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck loop:<<Loop:B\d+>>
+ /// CHECK-DAG: BoundsCheck loop:<<Loop>>
+ //
+ /// CHECK-START: void Main.oneConstantIndex(int[], int[]) BCE (after)
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-NOT: Deoptimize
+ //
+ /// CHECK-START: void Main.oneConstantIndex(int[], int[]) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ public static void oneConstantIndex(int[] a, int[] b) {
+ // Dynamic bce on b requires two deopts: one null and one bound.
+ for (int i = 0; i < a.length; i++) {
+ a[i] = b[1];
+ }
+ }
+
+ /// CHECK-START: void Main.multipleConstantIndices(int[], int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck loop:<<Loop:B\d+>>
+ /// CHECK-DAG: BoundsCheck loop:<<Loop>>
+ /// CHECK-DAG: BoundsCheck loop:<<Loop>>
+ /// CHECK-DAG: BoundsCheck loop:<<Loop>>
+ //
+ /// CHECK-START: void Main.multipleConstantIndices(int[], int[]) BCE (after)
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-NOT: Deoptimize
+ //
+ /// CHECK-START: void Main.multipleConstantIndices(int[], int[]) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ public static void multipleConstantIndices(int[] a, int[] b) {
+ // Dynamic bce on b requires two deopts: one null and one bound.
+ for (int i = 0; i < a.length; i++) {
+ a[i] = b[0] + b[1] + b[2];
+ }
+ }
+
+ /// CHECK-START: void Main.oneInvariantIndex(int[], int[], int) BCE (before)
+ /// CHECK-DAG: BoundsCheck loop:<<Loop:B\d+>>
+ /// CHECK-DAG: BoundsCheck loop:<<Loop>>
+ //
+ /// CHECK-START: void Main.oneInvariantIndex(int[], int[], int) BCE (after)
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-NOT: Deoptimize
+ //
+ /// CHECK-START: void Main.oneInvariantIndex(int[], int[], int) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ public static void oneInvariantIndex(int[] a, int[] b, int c) {
+ // Dynamic bce on b requires two deopts: one null and one bound.
+ for (int i = 0; i < a.length; i++) {
+ a[i] = b[c];
+ }
+ }
+
+ /// CHECK-START: void Main.multipleInvariantIndices(int[], int[], int) BCE (before)
+ /// CHECK-DAG: BoundsCheck loop:<<Loop:B\d+>>
+ /// CHECK-DAG: BoundsCheck loop:<<Loop>>
+ /// CHECK-DAG: BoundsCheck loop:<<Loop>>
+ /// CHECK-DAG: BoundsCheck loop:<<Loop>>
+ //
+ /// CHECK-START: void Main.multipleInvariantIndices(int[], int[], int) BCE (after)
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-NOT: Deoptimize
+ //
+ /// CHECK-START: void Main.multipleInvariantIndices(int[], int[], int) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ public static void multipleInvariantIndices(int[] a, int[] b, int c) {
+ // Dynamic bce on b requires three deopts: one null and two bounds.
+ for (int i = 0; i < a.length; i++) {
+ a[i] = b[c-1] + b[c] + b[c+1];
+ }
+ }
+
+ /// CHECK-START: void Main.oneUnitStride(int[], int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck loop:<<Loop:B\d+>>
+ /// CHECK-DAG: BoundsCheck loop:<<Loop>>
+ //
+ /// CHECK-START: void Main.oneUnitStride(int[], int[]) BCE (after)
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-NOT: Deoptimize
+ //
+ /// CHECK-START: void Main.oneUnitStride(int[], int[]) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ public static void oneUnitStride(int[] a, int[] b) {
+ // Dynamic bce on b requires three deopts: one null and two bounds.
+ for (int i = 0; i < a.length; i++) {
+ a[i] = b[i];
+ }
+ }
+
+ /// CHECK-START: void Main.multipleUnitStrides(int[], int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck loop:<<Loop:B\d+>>
+ /// CHECK-DAG: BoundsCheck loop:<<Loop>>
+ /// CHECK-DAG: BoundsCheck loop:<<Loop>>
+ /// CHECK-DAG: BoundsCheck loop:<<Loop>>
+ //
+ /// CHECK-START: void Main.multipleUnitStrides(int[], int[]) BCE (after)
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-NOT: Deoptimize
+ //
+ /// CHECK-START: void Main.multipleUnitStrides(int[], int[]) instruction_simplifier_after_bce (after)
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-NOT: Deoptimize
+ //
+ /// CHECK-START: void Main.multipleUnitStrides(int[], int[]) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ public static void multipleUnitStrides(int[] a, int[] b) {
+ // Dynamic bce on b requires four deopts: one null and three bounds.
+ // One redundant deopt is removed by simplifier.
+ // TODO: range information could remove another
+ for (int i = 1; i < a.length - 1; i++) {
+ a[i] = b[i-1] + b[i] + b[i+1];
+ }
+ }
+
+ /// CHECK-START: void Main.multipleUnitStridesConditional(int[], int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck loop:<<Loop:B\d+>>
+ /// CHECK-DAG: BoundsCheck loop:<<Loop>>
+ /// CHECK-DAG: BoundsCheck loop:<<Loop>>
+ /// CHECK-DAG: BoundsCheck loop:<<Loop>>
+ /// CHECK-DAG: BoundsCheck loop:<<Loop>>
+ /// CHECK-DAG: BoundsCheck loop:<<Loop>>
+ //
+ /// CHECK-START: void Main.multipleUnitStridesConditional(int[], int[]) BCE (after)
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-NOT: Deoptimize
+ //
+ /// CHECK-START: void Main.multipleUnitStridesConditional(int[], int[]) instruction_simplifier_after_bce (after)
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-NOT: Deoptimize
+ //
+ /// CHECK-START: void Main.multipleUnitStridesConditional(int[], int[]) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ public static void multipleUnitStridesConditional(int[] a, int[] b) {
+ // Dynamic bce on b requires four deopts: one null and three bounds.
+ // The two conditional references may be included, since they are in range.
+ // One redundant deopt is removed by simplifier.
+ for (int i = 2; i < a.length - 2; i++) {
+ int t = b[i-2] + b[i] + b[i+2] + (((i & 1) == 0) ? b[i+1] : b[i-1]);
+ a[i] = t;
+ }
+ }
+
+ /// CHECK-START: void Main.shifter(int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck loop:<<Loop:B\d+>>
+ /// CHECK-DAG: BoundsCheck loop:<<Loop>>
+ /// CHECK-DAG: BoundsCheck loop:<<Loop>>
+ /// CHECK-DAG: BoundsCheck loop:<<Loop>>
+ /// CHECK-DAG: BoundsCheck loop:<<Loop>>
+ //
+ /// CHECK-START: void Main.shifter(int[]) BCE (after)
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-NOT: Deoptimize
+ //
+ /// CHECK-START: void Main.shifter(int[]) instruction_simplifier_after_bce (after)
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-NOT: Deoptimize
+ //
+ /// CHECK-START: void Main.shifter(int[]) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ public static void shifter(int[] x) {
+ // Real-life example: should have four deopts: one null and three bounds.
+ // Two redundant deopts are removed by simplifier.
+ for (int i = 16; i < 80; i++) {
+ int t = x[i - 3] ^ x[i - 8] ^ x[i - 14] ^ x[i - 16];
+ x[i] = t << 1 | t >>> 31;
+ }
+ }
+
+ /// CHECK-START: void Main.stencil(int[], int, int) BCE (before)
+ /// CHECK-DAG: BoundsCheck loop:<<Loop:B\d+>>
+ /// CHECK-DAG: BoundsCheck loop:<<Loop>>
+ /// CHECK-DAG: BoundsCheck loop:<<Loop>>
+ /// CHECK-DAG: BoundsCheck loop:<<Loop>>
+ /// CHECK-DAG: BoundsCheck loop:<<Loop>>
+ //
+ /// CHECK-START: void Main.stencil(int[], int, int) BCE (after)
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-DAG: Deoptimize loop:none
+ /// CHECK-NOT: Deoptimize
+ //
+ /// CHECK-START: void Main.stencil(int[], int, int) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ public static void stencil(int[] array, int start, int end) {
+ // Real-life example: should have four deopts: one null and three bounds.
+ for (int i = end; i >= start; i--) {
+ array[i] = (array[i-2] + array[i-1] + array[i] + array[i+1] + array[i+2]) / 5;
+ }
+ }
+
+ //
+ // Verifier.
+ //
+
+ public static void main(String[] args) {
+ int[] a = new int[10];
+ int b[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int b1[] = { 100 };
+
+ oneConstantIndex(a, b);
+ for (int i = 0; i < a.length; i++) {
+ expectEquals(2, a[i]);;
+ }
+ try {
+ oneConstantIndex(a, b1);
+ throw new Error("Should throw AIOOBE");
+ } catch (ArrayIndexOutOfBoundsException e) {
+ }
+
+ multipleConstantIndices(a, b);
+ for (int i = 0; i < a.length; i++) {
+ expectEquals(6, a[i]);;
+ }
+ try {
+ multipleConstantIndices(a, b1);
+ throw new Error("Should throw AIOOBE");
+ } catch (ArrayIndexOutOfBoundsException e) {
+ }
+
+ oneInvariantIndex(a, b, 1);
+ for (int i = 0; i < a.length; i++) {
+ expectEquals(2, a[i]);;
+ }
+ try {
+ oneInvariantIndex(a, b1, 1);
+ throw new Error("Should throw AIOOBE");
+ } catch (ArrayIndexOutOfBoundsException e) {
+ }
+
+ multipleInvariantIndices(a, b, 1);
+ for (int i = 0; i < a.length; i++) {
+ expectEquals(6, a[i]);;
+ }
+ try {
+ multipleInvariantIndices(a, b1, 1);
+ throw new Error("Should throw AIOOBE");
+ } catch (ArrayIndexOutOfBoundsException e) {
+ }
+
+ oneUnitStride(a, b);
+ for (int i = 0; i < a.length; i++) {
+ expectEquals(i + 1, a[i]);;
+ }
+ try {
+ oneUnitStride(a, b1);
+ throw new Error("Should throw AIOOBE");
+ } catch (ArrayIndexOutOfBoundsException e) {
+ expectEquals(100, a[0]);;
+ }
+
+ multipleUnitStrides(a, b);
+ for (int i = 1; i < a.length - 1; i++) {
+ expectEquals(3 * i + 3, a[i]);;
+ }
+ try {
+ multipleUnitStrides(a, b1);
+ throw new Error("Should throw AIOOBE");
+ } catch (ArrayIndexOutOfBoundsException e) {
+ }
+
+ multipleUnitStridesConditional(a, b);
+ for (int i = 2; i < a.length - 2; i++) {
+ int e = 3 * i + 3 + (((i & 1) == 0) ? i + 2 : i);
+ expectEquals(e, a[i]);;
+ }
+ try {
+ multipleUnitStridesConditional(a, b1);
+ throw new Error("Should throw AIOOBE");
+ } catch (ArrayIndexOutOfBoundsException e) {
+ }
+
+ System.out.println("passed");
+ }
+
+ private static void expectEquals(int expected, int result) {
+ if (expected != result) {
+ throw new Error("Expected: " + expected + ", found: " + result);
+ }
+ }
+}