Added geometric induction variables analysis.
Rationale:
Information on geometric and polynomial (coming soon) sequences
are nice to have to further enhance BCE and last-value assignment.
Test: test-art-host
Change-Id: Ib5e2998c3eb1009def6fd00b82935da7c3ba7c6e
diff --git a/test/530-checker-loops1/info.txt b/test/530-checker-loops1/info.txt
index f5d334d..ecefa7e 100644
--- a/test/530-checker-loops1/info.txt
+++ b/test/530-checker-loops1/info.txt
@@ -1 +1 @@
-Test on loop optimizations.
+Test on loop optimizations, in particular around common induction.
diff --git a/test/530-checker-loops1/src/Main.java b/test/530-checker-loops1/src/Main.java
index dde4d62..383c28f 100644
--- a/test/530-checker-loops1/src/Main.java
+++ b/test/530-checker-loops1/src/Main.java
@@ -15,7 +15,7 @@
*/
//
-// Test on loop optimizations.
+// Test on loop optimizations, in particular around common induction.
//
public class Main {
diff --git a/test/530-checker-loops2/info.txt b/test/530-checker-loops2/info.txt
index f5d334d..3b5a7ad 100644
--- a/test/530-checker-loops2/info.txt
+++ b/test/530-checker-loops2/info.txt
@@ -1 +1 @@
-Test on loop optimizations.
+Test on loop optimizations, in particular around less common induction.
diff --git a/test/530-checker-loops2/src/Main.java b/test/530-checker-loops2/src/Main.java
index 47b6475..a94d69b 100644
--- a/test/530-checker-loops2/src/Main.java
+++ b/test/530-checker-loops2/src/Main.java
@@ -15,7 +15,7 @@
*/
//
-// Test on loop optimizations.
+// Test on loop optimizations, in particular around less common induction.
//
public class Main {
diff --git a/test/530-checker-loops3/info.txt b/test/530-checker-loops3/info.txt
index 07d99a3..e262f8e 100644
--- a/test/530-checker-loops3/info.txt
+++ b/test/530-checker-loops3/info.txt
@@ -1 +1 @@
-Test on loop optimizations, in particular loop-based dynamic bce.
+Test on loop optimizations, in particular around loop-based dynamic bce.
diff --git a/test/530-checker-loops4/expected.txt b/test/530-checker-loops4/expected.txt
new file mode 100644
index 0000000..b0aad4d
--- /dev/null
+++ b/test/530-checker-loops4/expected.txt
@@ -0,0 +1 @@
+passed
diff --git a/test/530-checker-loops4/info.txt b/test/530-checker-loops4/info.txt
new file mode 100644
index 0000000..10cf3b1
--- /dev/null
+++ b/test/530-checker-loops4/info.txt
@@ -0,0 +1 @@
+Test on loop optimizations, in particular with geometric induction.
diff --git a/test/530-checker-loops4/src/Main.java b/test/530-checker-loops4/src/Main.java
new file mode 100644
index 0000000..2e19c88
--- /dev/null
+++ b/test/530-checker-loops4/src/Main.java
@@ -0,0 +1,323 @@
+/*
+ * 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 around geometric induction.
+//
+public class Main {
+
+ /// CHECK-START: int Main.geo1(int) loop_optimization (before)
+ /// CHECK-DAG: Phi loop:<<Loop:B\d+>>
+ /// CHECK-DAG: Mul loop:<<Loop>>
+ //
+ /// CHECK-START: int Main.geo1(int) loop_optimization (after)
+ /// CHECK-DAG: <<Par:i\d+>> ParameterValue loop:none
+ /// CHECK-DAG: <<Zer:i\d+>> IntConstant 0 loop:none
+ /// CHECK-DAG: <<Int:i\d+>> IntConstant 1410065408 loop:none
+ /// CHECK-DAG: <<Mul:i\d+>> Mul [<<Par>>,<<Int>>] loop:none
+ /// CHECK-DAG: <<Add:i\d+>> Add [<<Mul>>,<<Zer>>] loop:none
+ /// CHECK-DAG: Return [<<Add>>] loop:none
+ //
+ /// CHECK-START: int Main.geo1(int) loop_optimization (after)
+ /// CHECK-NOT: Phi
+ public static int geo1(int a) {
+ for (int i = 0; i < 10; i++) {
+ a *= 10;
+ }
+ return a;
+ }
+
+ /// CHECK-START: int Main.geo2(int) loop_optimization (before)
+ /// CHECK-DAG: Phi loop:<<Loop:B\d+>>
+ /// CHECK-DAG: Shl loop:<<Loop>>
+ //
+ /// CHECK-START: int Main.geo2(int) loop_optimization (after)
+ /// CHECK-DAG: <<Par:i\d+>> ParameterValue loop:none
+ /// CHECK-DAG: <<Zer:i\d+>> IntConstant 0 loop:none
+ /// CHECK-DAG: <<Int:i\d+>> IntConstant 1024 loop:none
+ /// CHECK-DAG: <<Mul:i\d+>> Mul [<<Par>>,<<Int>>] loop:none
+ /// CHECK-DAG: <<Add:i\d+>> Add [<<Mul>>,<<Zer>>] loop:none
+ /// CHECK-DAG: Return [<<Add>>] loop:none
+ //
+ /// CHECK-START: int Main.geo2(int) loop_optimization (after)
+ /// CHECK-NOT: Phi
+ public static int geo2(int a) {
+ for (int i = 0; i < 10; i++) {
+ a <<= 1;
+ }
+ return a;
+ }
+
+ /// CHECK-START: int Main.geo3(int) loop_optimization (before)
+ /// CHECK-DAG: Phi loop:<<Loop:B\d+>>
+ /// CHECK-DAG: Div loop:<<Loop>>
+ //
+ /// CHECK-START: int Main.geo3(int) loop_optimization (after)
+ /// CHECK-DAG: <<Par:i\d+>> ParameterValue loop:none
+ /// CHECK-DAG: <<Zer:i\d+>> IntConstant 0 loop:none
+ /// CHECK-DAG: <<Int:i\d+>> IntConstant 59049 loop:none
+ /// CHECK-DAG: <<Div:i\d+>> Div [<<Par>>,<<Int>>] loop:none
+ /// CHECK-DAG: <<Add:i\d+>> Add [<<Div>>,<<Zer>>] loop:none
+ /// CHECK-DAG: Return [<<Add>>] loop:none
+ //
+ /// CHECK-START: int Main.geo3(int) loop_optimization (after)
+ /// CHECK-NOT: Phi
+ public static int geo3(int a) {
+ for (int i = 0; i < 10; i++) {
+ a /= 3;
+ }
+ return a;
+ }
+
+ /// CHECK-START: int Main.geo4(int) loop_optimization (before)
+ /// CHECK-DAG: Phi loop:<<Loop:B\d+>>
+ /// CHECK-DAG: Rem loop:<<Loop>>
+ //
+ /// CHECK-START: int Main.geo4(int) loop_optimization (after)
+ /// CHECK-DAG: <<Par:i\d+>> ParameterValue loop:none
+ /// CHECK-DAG: <<Zer:i\d+>> IntConstant 0 loop:none
+ /// CHECK-DAG: <<Int:i\d+>> IntConstant 7 loop:none
+ /// CHECK-DAG: <<Rem:i\d+>> Rem [<<Par>>,<<Int>>] loop:none
+ /// CHECK-DAG: <<Add:i\d+>> Add [<<Rem>>,<<Zer>>] loop:none
+ /// CHECK-DAG: Return [<<Add>>] loop:none
+ //
+ /// CHECK-START: int Main.geo4(int) loop_optimization (after)
+ /// CHECK-NOT: Phi
+ public static int geo4(int a) {
+ for (int i = 0; i < 10; i++) {
+ a %= 7;
+ }
+ return a;
+ }
+
+ // TODO: someday?
+ public static int geo1BCE() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
+ 11, 12, 13, 14, 15, 16, 17, 19, 19, 20,
+ 21, 22, 23, 24, 25, 26 };
+ int a = 1;
+ int r = 0;
+ for (int i = 0; i < 3; i++) {
+ r += x[a];
+ a *= 5;
+ }
+ return r;
+ }
+
+ // TODO: someday?
+ public static int geo2BCE() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
+ 11, 12, 13, 14, 15, 16, 17, 19, 19, 20,
+ 21, 22, 23, 24, 25, 26 };
+ int a = 1;
+ int r = 0;
+ for (int i = 0; i < 5; i++) {
+ r += x[a];
+ a <<= 1;
+ }
+ return r;
+ }
+
+ /// CHECK-START: int Main.geo3BCE() BCE (before)
+ /// CHECK-DAG: BoundsCheck loop:none
+ /// CHECK-DAG: BoundsCheck loop:{{B\d+}}
+ //
+ /// CHECK-START: int Main.geo3BCE() BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
+ public static int geo3BCE() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
+ 11, 12, 13, 14, 15, 16, 17, 19, 19, 20,
+ 21, 22, 23, 24, 25, 26 };
+ int a = 25;
+ int r = 0;
+ for (int i = 0; i < 100; i++) { // a converges to 0
+ r += x[a];
+ a /= 5;
+ }
+ return r;
+ }
+
+ /// CHECK-START: int Main.geo4BCE() BCE (before)
+ /// CHECK-DAG: BoundsCheck loop:none
+ /// CHECK-DAG: BoundsCheck loop:{{B\d+}}
+ //
+ /// CHECK-START: int Main.geo4BCE() BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
+ public static int geo4BCE() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
+ 11, 12, 13, 14, 15, 16, 17, 19, 19, 20,
+ 21, 22, 23, 24, 25, 26 };
+ int a = 25;
+ int r = 0;
+ for (int i = 0; i < 100; i++) { // a converges to 0
+ r += x[a];
+ a %= 5;
+ }
+ return r;
+ }
+
+ /// CHECK-START: int Main.geoMulBlackHole(int) loop_optimization (before)
+ /// CHECK-DAG: Phi loop:<<Loop:B\d+>>
+ /// CHECK-DAG: Mul loop:<<Loop>>
+ //
+ /// CHECK-START: int Main.geoMulBlackHole(int) loop_optimization (after)
+ /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0
+ /// CHECK-DAG: Return [<<Zero>>]
+ //
+ /// CHECK-START: int Main.geoMulBlackHole(int) loop_optimization (after)
+ /// CHECK-NOT: Phi
+ /// CHECK-NOT: Mul
+ public static int geoMulBlackHole(int a) {
+ for (int i = 0; i < 100; i++) {
+ a *= 10;
+ }
+ return a;
+ }
+
+ /// CHECK-START: int Main.geoShlBlackHole(int) loop_optimization (before)
+ /// CHECK-DAG: Phi loop:<<Loop:B\d+>>
+ /// CHECK-DAG: Shl loop:<<Loop>>
+ //
+ /// CHECK-START: int Main.geoShlBlackHole(int) loop_optimization (after)
+ /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0
+ /// CHECK-DAG: Return [<<Zero>>]
+ //
+ /// CHECK-START: int Main.geoShlBlackHole(int) loop_optimization (after)
+ /// CHECK-NOT: Phi
+ /// CHECK-NOT: Shl
+ public static int geoShlBlackHole(int a) {
+ for (int i = 0; i < 100; i++) {
+ a <<= 1;
+ }
+ return a;
+ }
+
+ /// CHECK-START: int Main.geoDivBlackHole(int) loop_optimization (before)
+ /// CHECK-DAG: Phi loop:<<Loop:B\d+>>
+ /// CHECK-DAG: Div loop:<<Loop>>
+ //
+ /// CHECK-START: int Main.geoDivBlackHole(int) loop_optimization (after)
+ /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0
+ /// CHECK-DAG: Return [<<Zero>>]
+ //
+ /// CHECK-START: int Main.geoDivBlackHole(int) loop_optimization (after)
+ /// CHECK-NOT: Phi
+ /// CHECK-NOT: Div
+ public static int geoDivBlackHole(int a) {
+ for (int i = 0; i < 100; i++) {
+ a /= 10;
+ }
+ return a;
+ }
+
+ // TODO: Rem is already optimized away by the time the loop optimizer runs;
+ // we could still optimize this case with last value on wrap-around!
+ //
+ /// CHECK-START: int Main.geoRemBlackHole(int) loop_optimization (before)
+ /// CHECK-DAG: Phi loop:<<Loop:B\d+>>
+ /// CHECK-DAG: Phi loop:<<Loop>>
+ //
+ /// CHECK-START: int Main.geoRemBlackHole(int) loop_optimization (after)
+ /// CHECK-DAG: Phi loop:<<Loop:B\d+>>
+ /// CHECK-DAG: Phi loop:<<Loop>>
+ public static int geoRemBlackHole(int a) {
+ for (int i = 0; i < 100; i++) {
+ a %= 1;
+ }
+ return a;
+ }
+
+ //
+ // Verifier.
+ //
+
+ public static void main(String[] args) {
+ int m = 1410065408;
+ for (int i = -100; i <= 100; i++) {
+ expectEquals(m * i, geo1(i));
+ }
+ for (int i = 1; i <= 1000000000; i *= 10) {
+ expectEquals( m * i, geo1( i));
+ expectEquals(-m * i, geo1(-i));
+ }
+
+ for (int i = -100; i <= 100; i++) {
+ expectEquals(i << 10, geo2(i));
+ }
+ for (int i = 0; i < 22; i++) {
+ expectEquals(1 << (i + 10), geo2(1 << i));
+ }
+ expectEquals(0x80000400, geo2(0x00200001));
+ expectEquals(0x00000000, geo2(0x00400000));
+ expectEquals(0x00000400, geo2(0x00400001));
+
+ int d = 59049;
+ for (int i = -100; i <= 100; i++) {
+ expectEquals(0, geo3(i));
+ }
+ for (int i = 1; i <= 100; i++) {
+ expectEquals( i, geo3( i * d));
+ expectEquals( i, geo3( i * d + 1));
+ expectEquals(-i, geo3(-i * d));
+ expectEquals(-i, geo3(-i * d - 1));
+ }
+
+ for (int i = -100; i <= 100; i++) {
+ expectEquals(i % 7, geo4(i));
+ }
+
+ expectEquals(34, geo1BCE());
+ expectEquals(36, geo2BCE());
+ expectEquals(131, geo3BCE());
+ expectEquals(125, geo4BCE());
+
+ // Nothing escapes!
+ expectEquals(0, geoMulBlackHole(0));
+ expectEquals(0, geoShlBlackHole(0));
+ expectEquals(0, geoDivBlackHole(0));
+ expectEquals(0, geoRemBlackHole(0));
+ for (int i = -100; i <= 100; i++) {
+ expectEquals(0, geoMulBlackHole(i));
+ expectEquals(0, geoShlBlackHole(i));
+ expectEquals(0, geoDivBlackHole(i));
+ expectEquals(0, geoRemBlackHole(i));
+ }
+ for (int i = 0; i < 31; i++) {
+ expectEquals(0, geoMulBlackHole(1 << i));
+ expectEquals(0, geoShlBlackHole(1 << i));
+ expectEquals(0, geoDivBlackHole(1 << i));
+ expectEquals(0, geoRemBlackHole(1 << i));
+ }
+ expectEquals(0, geoMulBlackHole(0x7fffffff));
+ expectEquals(0, geoShlBlackHole(0x7fffffff));
+ expectEquals(0, geoDivBlackHole(0x7fffffff));
+ expectEquals(0, geoRemBlackHole(0x7fffffff));
+ expectEquals(0, geoMulBlackHole(0x80000000));
+ expectEquals(0, geoShlBlackHole(0x80000000));
+ expectEquals(0, geoDivBlackHole(0x80000000));
+ expectEquals(0, geoRemBlackHole(0x80000000));
+
+ System.out.println("passed");
+ }
+
+ private static void expectEquals(int expected, int result) {
+ if (expected != result) {
+ throw new Error("Expected: " + expected + ", found: " + result);
+ }
+ }
+}