Various improvements in finding induction variables.
Rationale:
(1) Analyze multi-way phis (requested by Nicolas, Igor, and Mingyao).
(2) Analyze trip count for restricted != loops
(3) Added unit test for public API of range analysis (static methods
were already well-tested).
Change-Id: I9285d22d3bb927f141204cc4697ea6fe5120994d
diff --git a/test/530-checker-loops/src/Main.java b/test/530-checker-loops/src/Main.java
index e518a61..1c5b5d6 100644
--- a/test/530-checker-loops/src/Main.java
+++ b/test/530-checker-loops/src/Main.java
@@ -62,6 +62,19 @@
return result;
}
+ /// CHECK-START: int Main.linearVeryObscure(int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.linearVeryObscure(int[]) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int linearVeryObscure(int[] x) {
+ int result = 0;
+ for (int i = 0; i < x.length; i++) {
+ int k = (-i) + (i << 5) + i - (32 * i) + 5 + (int) i;
+ result += x[k - 5];
+ }
+ return result;
+ }
+
/// CHECK-START: int Main.linearWhile(int[]) BCE (before)
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.linearWhile(int[]) BCE (after)
@@ -75,6 +88,42 @@
return result;
}
+ /// CHECK-START: int Main.linearThreeWayPhi(int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.linearThreeWayPhi(int[]) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int linearThreeWayPhi(int[] x) {
+ int result = 0;
+ for (int i = 0; i < x.length; ) {
+ if (x[i] == 5) {
+ i++;
+ continue;
+ }
+ result += x[i++];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.linearFourWayPhi(int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.linearFourWayPhi(int[]) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int linearFourWayPhi(int[] x) {
+ int result = 0;
+ for (int i = 0; i < x.length; ) {
+ if (x[i] == 5) {
+ i++;
+ continue;
+ } else if (x[i] == 6) {
+ i++;
+ result += 7;
+ continue;
+ }
+ result += x[i++];
+ }
+ return result;
+ }
+
/// CHECK-START: int Main.wrapAroundThenLinear(int[]) BCE (before)
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.wrapAroundThenLinear(int[]) BCE (after)
@@ -90,6 +139,25 @@
return result;
}
+ /// CHECK-START: int Main.wrapAroundThenLinearThreeWayPhi(int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.wrapAroundThenLinearThreeWayPhi(int[]) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int wrapAroundThenLinearThreeWayPhi(int[] x) {
+ // Loop with wrap around (length - 1, 0, 1, 2, ..).
+ int w = x.length - 1;
+ int result = 0;
+ for (int i = 0; i < x.length; ) {
+ if (x[w] == 1) {
+ w = i++;
+ continue;
+ }
+ result += x[w];
+ w = i++;
+ }
+ return result;
+ }
+
/// CHECK-START: int[] Main.linearWithParameter(int) BCE (before)
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int[] Main.linearWithParameter(int) BCE (after)
@@ -102,6 +170,19 @@
return x;
}
+ /// CHECK-START: int[] Main.linearCopy(int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int[] Main.linearCopy(int[]) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int[] linearCopy(int x[]) {
+ int n = x.length;
+ int y[] = new int[n];
+ for (int i = 0; i < n; i++) {
+ y[i] = x[i];
+ }
+ return y;
+ }
+
/// CHECK-START: int Main.linearWithCompoundStride() BCE (before)
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.linearWithCompoundStride() BCE (after)
@@ -126,7 +207,7 @@
int result = 0;
int k = 0;
// Range analysis has no problem with a trip-count defined by a
- // reasonably large positive stride.
+ // reasonably large positive stride far away from upper bound.
for (int i = 1; i <= 10 * 10000000 + 1; i += 10000000) {
result += x[k++];
}
@@ -143,7 +224,7 @@
int k = 0;
// Range analysis conservatively bails due to potential of wrap-around
// arithmetic while computing the trip-count for this very large stride.
- for (int i = 1; i < 2147483647; i += 195225786) {
+ for (int i = 1; i < Integer.MAX_VALUE; i += 195225786) {
result += x[k++];
}
return result;
@@ -158,7 +239,7 @@
int result = 0;
int k = 0;
// Range analysis has no problem with a trip-count defined by a
- // reasonably large negative stride.
+ // reasonably large negative stride far away from lower bound.
for (int i = -1; i >= -10 * 10000000 - 1; i -= 10000000) {
result += x[k++];
}
@@ -175,12 +256,54 @@
int k = 0;
// Range analysis conservatively bails due to potential of wrap-around
// arithmetic while computing the trip-count for this very large stride.
- for (int i = -2; i > -2147483648; i -= 195225786) {
+ for (int i = -2; i > Integer.MIN_VALUE; i -= 195225786) {
result += x[k++];
}
return result;
}
+ /// CHECK-START: int Main.linearForNE() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.linearForNE() BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int linearForNE() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ for (int i = 0; i != 10; i++) {
+ result += x[i];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.linearDoWhile() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.linearDoWhile() BCE (after)
+ /// CHECK-DAG: BoundsCheck
+ private static int linearDoWhile() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ int i = 0;
+ // TODO: make this work
+ do {
+ result += x[i++];
+ } while (i < 10);
+ return result;
+ }
+
+ /// CHECK-START: int Main.linearShort() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.linearShort() BCE (after)
+ /// CHECK-DAG: BoundsCheck
+ private static int linearShort() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ // TODO: make this work
+ for (short i = 0; i < 10; i++) {
+ result += x[i];
+ }
+ return result;
+ }
+
/// CHECK-START: int Main.periodicIdiom(int) BCE (before)
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.periodicIdiom(int) BCE (after)
@@ -242,6 +365,112 @@
return result;
}
+ /// CHECK-START: int Main.justRightUp1() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.justRightUp1() BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int justRightUp1() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ for (int i = Integer.MAX_VALUE - 10, k = 0; i < Integer.MAX_VALUE; i++) {
+ result += x[k++];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.justRightUp2() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.justRightUp2() BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int justRightUp2() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ for (int i = Integer.MAX_VALUE - 10; i < Integer.MAX_VALUE; i++) {
+ result += x[i - Integer.MAX_VALUE + 10];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.justRightUp3() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.justRightUp3() BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int justRightUp3() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ for (int i = Integer.MAX_VALUE - 10, k = 0; i <= Integer.MAX_VALUE - 1; i++) {
+ result += x[k++];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.justOOBUp() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.justOOBUp() BCE (after)
+ /// CHECK-DAG: BoundsCheck
+ private static int justOOBUp() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ // Infinite loop!
+ for (int i = Integer.MAX_VALUE - 9, k = 0; i <= Integer.MAX_VALUE; i++) {
+ result += x[k++];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.justRightDown1() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.justRightDown1() BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int justRightDown1() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ for (int i = Integer.MIN_VALUE + 10, k = 0; i > Integer.MIN_VALUE; i--) {
+ result += x[k++];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.justRightDown2() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.justRightDown2() BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int justRightDown2() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ for (int i = Integer.MIN_VALUE + 10; i > Integer.MIN_VALUE; i--) {
+ result += x[Integer.MAX_VALUE + i];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.justRightDown3() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.justRightDown3() BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int justRightDown3() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ for (int i = Integer.MIN_VALUE + 10, k = 0; i >= Integer.MIN_VALUE + 1; i--) {
+ result += x[k++];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.justOOBDown() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.justOOBDown() BCE (after)
+ /// CHECK-DAG: BoundsCheck
+ private static int justOOBDown() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ // Infinite loop!
+ for (int i = Integer.MIN_VALUE + 9, k = 0; i >= Integer.MIN_VALUE; i--) {
+ result += x[k++];
+ }
+ return result;
+ }
+
//
// Cases that actually go out of bounds. These test cases
// ensure the exceptions are thrown at the right places.
@@ -274,10 +503,18 @@
expectEquals(55, linearDown(x));
expectEquals(0, linearObscure(empty));
expectEquals(55, linearObscure(x));
+ expectEquals(0, linearVeryObscure(empty));
+ expectEquals(55, linearVeryObscure(x));
expectEquals(0, linearWhile(empty));
expectEquals(55, linearWhile(x));
+ expectEquals(0, linearThreeWayPhi(empty));
+ expectEquals(50, linearThreeWayPhi(x));
+ expectEquals(0, linearFourWayPhi(empty));
+ expectEquals(51, linearFourWayPhi(x));
expectEquals(0, wrapAroundThenLinear(empty));
expectEquals(55, wrapAroundThenLinear(x));
+ expectEquals(0, wrapAroundThenLinearThreeWayPhi(empty));
+ expectEquals(54, wrapAroundThenLinearThreeWayPhi(x));
// Linear with parameter.
sResult = 0;
@@ -295,6 +532,16 @@
}
}
+ // Linear copy.
+ expectEquals(0, linearCopy(empty).length);
+ {
+ int[] r = linearCopy(x);
+ expectEquals(x.length, r.length);
+ for (int i = 0; i < x.length; i++) {
+ expectEquals(x[i], r[i]);
+ }
+ }
+
// Linear with non-unit strides.
expectEquals(56, linearWithCompoundStride());
expectEquals(66, linearWithLargePositiveStride());
@@ -302,6 +549,11 @@
expectEquals(66, linearWithLargeNegativeStride());
expectEquals(66, linearWithVeryLargeNegativeStride());
+ // Special forms.
+ expectEquals(55, linearForNE());
+ expectEquals(55, linearDoWhile());
+ expectEquals(55, linearShort());
+
// Periodic adds (1, 3), one at the time.
expectEquals(0, periodicIdiom(-1));
for (int tc = 0; tc < 32; tc++) {
@@ -326,6 +578,28 @@
expectEquals(tc * 16, periodicSequence4(tc));
}
+ // Large bounds.
+ expectEquals(55, justRightUp1());
+ expectEquals(55, justRightUp2());
+ expectEquals(55, justRightUp3());
+ expectEquals(55, justRightDown1());
+ expectEquals(55, justRightDown2());
+ expectEquals(55, justRightDown3());
+ sResult = 0;
+ try {
+ justOOBUp();
+ } catch (ArrayIndexOutOfBoundsException e) {
+ sResult = 1;
+ }
+ expectEquals(1, sResult);
+ sResult = 0;
+ try {
+ justOOBDown();
+ } catch (ArrayIndexOutOfBoundsException e) {
+ sResult = 1;
+ }
+ expectEquals(1, sResult);
+
// Lower bound goes OOB.
sResult = 0;
try {