Step-wise improvement of range analysis with outer loop induction.
Rationale: Using a step-wise approach (rather than expanding all ranges
at once) increases the opportunities for statically removing
bound checks, as demonstrated by the new checker tests.
Change-Id: Icbfd9406523a069e1fb7508546ea94f896e5a255
diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index a448302..7dbfd7c 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -1228,19 +1228,26 @@
InductionVarRange::Value v2;
bool needs_finite_test = false;
induction_range_.GetInductionRange(context, index, &v1, &v2, &needs_finite_test);
- if (v1.is_known && (v1.a_constant == 0 || v1.a_constant == 1) &&
- v2.is_known && (v2.a_constant == 0 || v2.a_constant == 1)) {
- DCHECK(v1.a_constant == 1 || v1.instruction == nullptr);
- DCHECK(v2.a_constant == 1 || v2.instruction == nullptr);
- ValueRange index_range(GetGraph()->GetArena(),
- ValueBound(v1.instruction, v1.b_constant),
- ValueBound(v2.instruction, v2.b_constant));
- // If analysis reveals a certain OOB, disable dynamic BCE.
- *try_dynamic_bce = !index_range.GetLower().LessThan(array_range->GetLower()) &&
- !index_range.GetUpper().GreaterThan(array_range->GetUpper());
- // Use analysis for static bce only if loop is finite.
- return !needs_finite_test && index_range.FitsIn(array_range);
- }
+ do {
+ if (v1.is_known && (v1.a_constant == 0 || v1.a_constant == 1) &&
+ v2.is_known && (v2.a_constant == 0 || v2.a_constant == 1)) {
+ DCHECK(v1.a_constant == 1 || v1.instruction == nullptr);
+ DCHECK(v2.a_constant == 1 || v2.instruction == nullptr);
+ ValueRange index_range(GetGraph()->GetArena(),
+ ValueBound(v1.instruction, v1.b_constant),
+ ValueBound(v2.instruction, v2.b_constant));
+ // If analysis reveals a certain OOB, disable dynamic BCE.
+ if (index_range.GetLower().LessThan(array_range->GetLower()) ||
+ index_range.GetUpper().GreaterThan(array_range->GetUpper())) {
+ *try_dynamic_bce = false;
+ return false;
+ }
+ // Use analysis for static bce only if loop is finite.
+ if (!needs_finite_test && index_range.FitsIn(array_range)) {
+ return true;
+ }
+ }
+ } while (induction_range_.RefineOuter(&v1, &v2));
return false;
}
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
index 2ac1e15..9d0cde7 100644
--- a/compiler/optimizing/induction_var_range.cc
+++ b/compiler/optimizing/induction_var_range.cc
@@ -119,6 +119,17 @@
}
}
+bool InductionVarRange::RefineOuter(/*in-out*/Value* min_val, /*in-out*/Value* max_val) {
+ Value v1 = RefineOuter(*min_val, /* is_min */ true);
+ Value v2 = RefineOuter(*max_val, /* is_min */ false);
+ if (v1.instruction != min_val->instruction || v2.instruction != max_val->instruction) {
+ *min_val = v1;
+ *max_val = v2;
+ return true;
+ }
+ return false;
+}
+
bool InductionVarRange::CanGenerateCode(HInstruction* context,
HInstruction* instruction,
/*out*/bool* needs_finite_test,
@@ -202,6 +213,8 @@
} else if (IsIntAndGet(instruction->InputAt(1), &value)) {
return AddValue(GetFetch(instruction->InputAt(0), trip, in_body, is_min), Value(value));
}
+ } else if (instruction->IsArrayLength() && instruction->InputAt(0)->IsNewArray()) {
+ return GetFetch(instruction->InputAt(0)->InputAt(0), trip, in_body, is_min);
} else if (is_min) {
// Special case for finding minimum: minimum of trip-count in loop-body is 1.
if (trip != nullptr && in_body && instruction == trip->op_a->fetch) {
@@ -404,6 +417,25 @@
return Value();
}
+InductionVarRange::Value InductionVarRange::RefineOuter(Value v, bool is_min) {
+ if (v.instruction != nullptr) {
+ HLoopInformation* loop =
+ v.instruction->GetBlock()->GetLoopInformation(); // closest enveloping loop
+ if (loop != nullptr) {
+ // Set up loop information.
+ bool in_body = true; // use is always in body of outer loop
+ HInductionVarAnalysis::InductionInfo* info =
+ induction_analysis_->LookupInfo(loop, v.instruction);
+ HInductionVarAnalysis::InductionInfo* trip =
+ induction_analysis_->LookupInfo(loop, loop->GetHeader()->GetLastInstruction());
+ // Try to refine "a x instruction + b" with outer loop range information on instruction.
+ return AddValue(MulValue(Value(v.a_constant), GetVal(info, trip, in_body, is_min)),
+ Value(v.b_constant));
+ }
+ }
+ return v;
+}
+
bool InductionVarRange::GenerateCode(HInstruction* context,
HInstruction* instruction,
HGraph* graph,
diff --git a/compiler/optimizing/induction_var_range.h b/compiler/optimizing/induction_var_range.h
index 7984871..71b0b1b 100644
--- a/compiler/optimizing/induction_var_range.h
+++ b/compiler/optimizing/induction_var_range.h
@@ -68,6 +68,9 @@
/*out*/Value* max_val,
/*out*/bool* needs_finite_test);
+ /** Refines the values with induction of next outer loop. Returns true on change. */
+ bool RefineOuter(/*in-out*/Value* min_val, /*in-out*/Value* max_val);
+
/**
* Returns true if range analysis is able to generate code for the lower and upper
* bound expressions on the instruction in the given context. The need_finite_test
@@ -149,6 +152,12 @@
static Value MergeVal(Value v1, Value v2, bool is_min);
/**
+ * Returns refined value using induction of next outer loop or the input value if no
+ * further refinement is possible.
+ */
+ Value RefineOuter(Value val, bool is_min);
+
+ /**
* Generates code for lower/upper/taken-test in the HIR. Returns true on success.
* With values nullptr, the method can be used to determine if code generation
* would be successful without generating actual code yet.
diff --git a/compiler/optimizing/induction_var_range_test.cc b/compiler/optimizing/induction_var_range_test.cc
index c2ba157..128b5bb 100644
--- a/compiler/optimizing/induction_var_range_test.cc
+++ b/compiler/optimizing/induction_var_range_test.cc
@@ -473,16 +473,19 @@
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(0), v1);
ExpectEqual(Value(1000), v2);
+ EXPECT_FALSE(range.RefineOuter(&v1, &v2));
// In context of loop-body: known.
range.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(0), v1);
ExpectEqual(Value(999), v2);
+ EXPECT_FALSE(range.RefineOuter(&v1, &v2));
range.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(1), v1);
ExpectEqual(Value(1000), v2);
+ EXPECT_FALSE(range.RefineOuter(&v1, &v2));
}
TEST_F(InductionVarRangeTest, ConstantTripCountDown) {
@@ -498,16 +501,19 @@
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(0), v1);
ExpectEqual(Value(1000), v2);
+ EXPECT_FALSE(range.RefineOuter(&v1, &v2));
// In context of loop-body: known.
range.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(1), v1);
ExpectEqual(Value(1000), v2);
+ EXPECT_FALSE(range.RefineOuter(&v1, &v2));
range.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(0), v1);
ExpectEqual(Value(999), v2);
+ EXPECT_FALSE(range.RefineOuter(&v1, &v2));
}
TEST_F(InductionVarRangeTest, SymbolicTripCountUp) {
@@ -527,16 +533,19 @@
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(0), v1);
ExpectEqual(Value(), v2);
+ EXPECT_FALSE(range.RefineOuter(&v1, &v2));
// In context of loop-body: known.
range.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(0), v1);
ExpectEqual(Value(parameter, 1, -1), v2);
+ EXPECT_FALSE(range.RefineOuter(&v1, &v2));
range.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(1), v1);
ExpectEqual(Value(parameter, 1, 0), v2);
+ EXPECT_FALSE(range.RefineOuter(&v1, &v2));
HInstruction* lower = nullptr;
HInstruction* upper = nullptr;
@@ -597,16 +606,19 @@
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(), v1);
ExpectEqual(Value(1000), v2);
+ EXPECT_FALSE(range.RefineOuter(&v1, &v2));
// In context of loop-body: known.
range.GetInductionRange(increment_, condition_->InputAt(0), &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(parameter, 1, 1), v1);
ExpectEqual(Value(1000), v2);
+ EXPECT_FALSE(range.RefineOuter(&v1, &v2));
range.GetInductionRange(increment_, increment_, &v1, &v2, &needs_finite_test);
EXPECT_FALSE(needs_finite_test);
ExpectEqual(Value(parameter, 1, 0), v1);
ExpectEqual(Value(999), v2);
+ EXPECT_FALSE(range.RefineOuter(&v1, &v2));
HInstruction* lower = nullptr;
HInstruction* upper = nullptr;
diff --git a/test/530-checker-loops/src/Main.java b/test/530-checker-loops/src/Main.java
index 34d2f64..3f6e48b 100644
--- a/test/530-checker-loops/src/Main.java
+++ b/test/530-checker-loops/src/Main.java
@@ -415,6 +415,135 @@
return result;
}
+ /// CHECK-START: void Main.linearTriangularOnTwoArrayLengths(int) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: ArraySet
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: ArraySet
+ /// CHECK-START: void Main.linearTriangularOnTwoArrayLengths(int) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: ArraySet
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: ArraySet
+ /// CHECK-NOT: Deoptimize
+ private static void linearTriangularOnTwoArrayLengths(int n) {
+ int[] a = new int[n];
+ for (int i = 0; i < a.length; i++) {
+ int[] b = new int[i];
+ for (int j = 0; j < b.length; j++) {
+ // Need to know j < b.length < a.length for static bce.
+ a[j] += 1;
+ // Need to know just j < b.length for static bce.
+ b[j] += 1;
+ }
+ verifyTriangular(a, b, i, n);
+ }
+ }
+
+ /// CHECK-START: void Main.linearTriangularOnOneArrayLength(int) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: ArraySet
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: ArraySet
+ /// CHECK-START: void Main.linearTriangularOnOneArrayLength(int) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: ArraySet
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: ArraySet
+ /// CHECK-NOT: Deoptimize
+ private static void linearTriangularOnOneArrayLength(int n) {
+ int[] a = new int[n];
+ for (int i = 0; i < a.length; i++) {
+ int[] b = new int[i];
+ for (int j = 0; j < i; j++) {
+ // Need to know j < i < a.length for static bce.
+ a[j] += 1;
+ // Need to know just j < i for static bce.
+ b[j] += 1;
+ }
+ verifyTriangular(a, b, i, n);
+ }
+ }
+
+ /// CHECK-START: void Main.linearTriangularOnParameter(int) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: ArraySet
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: ArraySet
+ /// CHECK-START: void Main.linearTriangularOnParameter(int) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: ArraySet
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: ArraySet
+ /// CHECK-NOT: Deoptimize
+ private static void linearTriangularOnParameter(int n) {
+ int[] a = new int[n];
+ for (int i = 0; i < n; i++) {
+ int[] b = new int[i];
+ for (int j = 0; j < i; j++) {
+ // Need to know j < i < n for static bce.
+ a[j] += 1;
+ // Need to know just j < i for static bce.
+ b[j] += 1;
+ }
+ verifyTriangular(a, b, i, n);
+ }
+ }
+
+ // Verifier for triangular methods.
+ private static void verifyTriangular(int[] a, int[] b, int m, int n) {
+ expectEquals(n, a.length);
+ for (int i = 0, k = m; i < n; i++) {
+ expectEquals(a[i], k);
+ if (k > 0) k--;
+ }
+ expectEquals(m, b.length);
+ for (int i = 0; i < m; i++) {
+ expectEquals(b[i], 1);
+ }
+ }
+
+ /// CHECK-START: void Main.bubble(int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: If
+ /// CHECK-DAG: ArraySet
+ /// CHECK-DAG: ArraySet
+ /// CHECK-START: void Main.bubble(int[]) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: If
+ /// CHECK-DAG: ArraySet
+ /// CHECK-DAG: ArraySet
+ /// CHECK-NOT: Deoptimize
+ private static void bubble(int[] a) {
+ for (int i = a.length; --i >= 0;) {
+ for (int j = 0; j < i; j++) {
+ if (a[j] > a[j+1]) {
+ int tmp = a[j];
+ a[j] = a[j+1];
+ a[j+1] = tmp;
+ }
+ }
+ }
+ }
+
/// CHECK-START: int Main.periodicIdiom(int) BCE (before)
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.periodicIdiom(int) BCE (after)
@@ -1012,6 +1141,16 @@
expectEquals(55, linearDoWhileDown());
expectEquals(55, linearShort());
expectEquals(55, invariantFromPreLoop(x, 1));
+ linearTriangularOnTwoArrayLengths(10);
+ linearTriangularOnOneArrayLength(10);
+ linearTriangularOnParameter(10);
+
+ // Sorting.
+ int[] sort = { 5, 4, 1, 9, 10, 2, 7, 6, 3, 8 };
+ bubble(sort);
+ for (int i = 0; i < 10; i++) {
+ expectEquals(sort[i], x[i]);
+ }
// Periodic adds (1, 3), one at the time.
expectEquals(0, periodicIdiom(-1));
