A first implementation of a loop optimization framework.
Rationale:
We are planning to add more and more loop related optimizations
and this framework provides the basis to do so. For starters,
the framework optimizes dead induction, induction that can be
replaced with a simpler closed-form, and eliminates dead loops
completely (either pre-existing or as a result of induction
removal).
Speedup on e.g. Benchpress Loop is 73x (17.5us. -> 0.24us.)
[with the potential for more exploiting outer loop too]
Test: 618-checker-induction et al.
Change-Id: If80a809acf943539bf6726b0030dcabd50c9babc
diff --git a/test/618-checker-induction/src/Main.java b/test/618-checker-induction/src/Main.java
new file mode 100644
index 0000000..a68c383
--- /dev/null
+++ b/test/618-checker-induction/src/Main.java
@@ -0,0 +1,422 @@
+/*
+ * 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.
+ */
+
+/**
+ * Tests on loop optimizations related to induction.
+ */
+public class Main {
+
+ static int[] a = new int[10];
+
+ /// CHECK-START: void Main.deadSingleLoop() loop_optimization (before)
+ /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:none
+ //
+ /// CHECK-START: void Main.deadSingleLoop() loop_optimization (after)
+ /// CHECK-NOT: Phi loop:{{B\d+}} outer_loop:none
+ static void deadSingleLoop() {
+ for (int i = 0; i < 4; i++) {
+ }
+ }
+
+ /// CHECK-START: void Main.deadNestedLoops() loop_optimization (before)
+ /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:<<Loop>>
+ //
+ /// CHECK-START: void Main.deadNestedLoops() loop_optimization (after)
+ /// CHECK-NOT: Phi loop:{{B\d+}}
+ static void deadNestedLoops() {
+ for (int i = 0; i < 4; i++) {
+ for (int j = 0; j < 4; j++) {
+ }
+ }
+ }
+
+ /// CHECK-START: void Main.deadNestedAndFollowingLoops() loop_optimization (before)
+ /// CHECK-DAG: Phi loop:<<Loop1:B\d+>> outer_loop:none
+ /// CHECK-DAG: Phi loop:<<Loop2:B\d+>> outer_loop:<<Loop1>>
+ /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:<<Loop2>>
+ /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:<<Loop2>>
+ /// CHECK-DAG: Phi loop:<<Loop3:B\d+>> outer_loop:<<Loop1>>
+ /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:<<Loop3>>
+ /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:none
+ //
+ /// CHECK-START: void Main.deadNestedAndFollowingLoops() loop_optimization (after)
+ /// CHECK-NOT: Phi loop:{{B\d+}}
+ static void deadNestedAndFollowingLoops() {
+ for (int i = 0; i < 4; i++) {
+ for (int j = 0; j < 4; j++) {
+ for (int k = 0; k < 4; k++) {
+ }
+ for (int k = 0; k < 4; k++) {
+ }
+ }
+ for (int j = 0; j < 4; j++) {
+ for (int k = 0; k < 4; k++) {
+ }
+ }
+ }
+ for (int i = 0; i < 4; i++) {
+ }
+ }
+
+ /// CHECK-START: void Main.deadInduction() loop_optimization (before)
+ /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-START: void Main.deadInduction() loop_optimization (after)
+ /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-NOT: Phi loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
+ static void deadInduction() {
+ int dead = 0;
+ for (int i = 0; i < a.length; i++) {
+ a[i] = 1;
+ dead += 5;
+ }
+ }
+
+ /// CHECK-START: void Main.deadManyInduction() loop_optimization (before)
+ /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-START: void Main.deadManyInduction() loop_optimization (after)
+ /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-NOT: Phi loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
+ static void deadManyInduction() {
+ int dead1 = 0, dead2 = 1, dead3 = 3;
+ for (int i = 0; i < a.length; i++) {
+ dead1 += 5;
+ a[i] = 2;
+ dead2 += 10;
+ dead3 += 100;
+ }
+ }
+
+ /// CHECK-START: void Main.deadSequence() loop_optimization (before)
+ /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-START: void Main.deadSequence() loop_optimization (after)
+ /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-NOT: Phi loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
+ static void deadSequence() {
+ int dead = 0;
+ for (int i = 0; i < a.length; i++) {
+ a[i] = 3;
+ // Increment value defined inside loop,
+ // but sequence itself not used anywhere.
+ dead += i;
+ }
+ }
+
+ /// CHECK-START: void Main.deadCycleWithException(int) loop_optimization (before)
+ /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
+ //
+ /// CHECK-START: void Main.deadCycleWithException(int) loop_optimization (after)
+ /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-NOT: Phi loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
+ static void deadCycleWithException(int k) {
+ int dead = 0;
+ for (int i = 0; i < a.length; i++) {
+ a[i] = 4;
+ // Increment value of dead cycle may throw exception.
+ dead += a[k];
+ }
+ }
+
+ /// CHECK-START: int Main.closedFormInductionUp() loop_optimization (before)
+ /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: Return [<<Phi1>>] loop:none
+ //
+ /// CHECK-START: int Main.closedFormInductionUp() loop_optimization (after)
+ /// CHECK-NOT: Phi loop:B\d+ outer_loop:none
+ /// CHECK-DAG: Return loop:none
+ static int closedFormInductionUp() {
+ int closed = 12345;
+ for (int i = 0; i < 10; i++) {
+ closed += 5;
+ }
+ return closed; // only needs last value
+ }
+
+ /// CHECK-START: int Main.closedFormInductionInAndDown(int) loop_optimization (before)
+ /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: Return [<<Phi2>>] loop:none
+ //
+ /// CHECK-START: int Main.closedFormInductionInAndDown(int) loop_optimization (after)
+ /// CHECK-NOT: Phi loop:B\d+ outer_loop:none
+ /// CHECK-DAG: Return loop:none
+ static int closedFormInductionInAndDown(int closed) {
+ for (int i = 0; i < 10; i++) {
+ closed -= 5;
+ }
+ return closed; // only needs last value
+ }
+
+ // TODO: taken test around closed form?
+ static int closedFormInductionUpN(int n) {
+ int closed = 12345;
+ for (int i = 0; i < n; i++) {
+ closed += 5;
+ }
+ return closed; // only needs last value
+ }
+
+ // TODO: taken test around closed form?
+ static int closedFormInductionInAndDownN(int closed, int n) {
+ for (int i = 0; i < n; i++) {
+ closed -= 5;
+ }
+ return closed; // only needs last value
+ }
+
+ // TODO: move closed form even further out?
+ static int closedFormNested(int n) {
+ int closed = 0;
+ for (int i = 0; i < n; i++) {
+ for (int j = 0; j < 10; j++) {
+ closed++;
+ }
+ }
+ return closed; // only needs last-value
+ }
+
+ // TODO: handle as closed/empty eventually?
+ static int mainIndexReturned(int n) {
+ int i;
+ for (i = 0; i < n; i++);
+ return i;
+ }
+
+ // If ever replaced by closed form, last value should be correct!
+ static int periodicReturned(int n) {
+ int k = 0;
+ for (int i = 0; i < n; i++) {
+ k = 1 - k;
+ }
+ return k;
+ }
+
+ // Same here.
+ private static int getSum(int n) {
+ int k = 0;
+ int sum = 0;
+ for (int i = 0; i < n; i++) {
+ k++;
+ sum += k;
+ }
+ return sum;
+ }
+
+ // Same here.
+ private static int getSum21() {
+ int k = 0;
+ int sum = 0;
+ for (int i = 0; i < 6; i++) {
+ k++;
+ sum += k;
+ }
+ return sum;
+ }
+
+ // Same here.
+ private static int closedTwice() {
+ int closed = 0;
+ for (int i = 0; i < 10; i++) {
+ closed++;
+ }
+ // Closed form of first loop defines trip count of second loop.
+ int other_closed = 0;
+ for (int i = 0; i < closed; i++) {
+ other_closed++;
+ }
+ return other_closed;
+ }
+
+ /// CHECK-START: int Main.closedFeed() loop_optimization (before)
+ /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop1:B\d+>> outer_loop:none
+ /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop1>> outer_loop:none
+ /// CHECK-DAG: <<Phi3:i\d+>> Phi loop:<<Loop2:B\d+>> outer_loop:none
+ /// CHECK-DAG: <<Phi4:i\d+>> Phi loop:<<Loop2>> outer_loop:none
+ /// CHECK-DAG: Return [<<Phi3>>] loop:none
+ /// CHECK-EVAL: "<<Loop1>>" != "<<Loop2>>"
+ //
+ /// CHECK-START: int Main.closedFeed() loop_optimization (after)
+ /// CHECK-NOT: Phi loop:B\d+ outer_loop:none
+ /// CHECK-DAG: Return loop:none
+ private static int closedFeed() {
+ int closed = 0;
+ for (int i = 0; i < 10; i++) {
+ closed++;
+ }
+ // Closed form of first loop feeds into initial value of second loop,
+ // used when generating closed form for the latter.
+ for (int i = 0; i < 10; i++) {
+ closed++;
+ }
+ return closed;
+ }
+
+ /// CHECK-START: int Main.closedLargeUp() loop_optimization (before)
+ /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: Return [<<Phi1>>] loop:none
+ //
+ /// CHECK-START: int Main.closedLargeUp() loop_optimization (after)
+ /// CHECK-NOT: Phi loop:B\d+ outer_loop:none
+ /// CHECK-DAG: Return loop:none
+ private static int closedLargeUp() {
+ int closed = 0;
+ for (int i = 0; i < 10; i++) {
+ closed += 0x7fffffff;
+ }
+ return closed;
+ }
+
+ /// CHECK-START: int Main.closedLargeDown() loop_optimization (before)
+ /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
+ /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: Return [<<Phi1>>] loop:none
+ //
+ /// CHECK-START: int Main.closedLargeDown() loop_optimization (after)
+ /// CHECK-NOT: Phi loop:B\d+ outer_loop:none
+ /// CHECK-DAG: Return loop:none
+ private static int closedLargeDown() {
+ int closed = 0;
+ for (int i = 0; i < 10; i++) {
+ closed -= 0x7fffffff;
+ }
+ return closed;
+ }
+
+ private static int exceptionExitBeforeAdd() {
+ int k = 0;
+ try {
+ for (int i = 0; i < 10; i++) {
+ a[i] = 0;
+ k += 10; // increment last
+ }
+ } catch(Exception e) {
+ // Flag error by returning current
+ // value of k negated.
+ return -k-1;
+ }
+ return k;
+ }
+
+ private static int exceptionExitAfterAdd() {
+ int k = 0;
+ try {
+ for (int i = 0; i < 10; i++) {
+ k += 10; // increment first
+ a[i] = 0;
+ }
+ } catch(Exception e) {
+ // Flag error by returning current
+ // value of k negated.
+ return -k-1;
+ }
+ return k;
+ }
+
+ public static void main(String[] args) {
+ deadSingleLoop();
+ deadNestedLoops();
+ deadNestedAndFollowingLoops();
+
+ deadInduction();
+ for (int i = 0; i < a.length; i++) {
+ expectEquals(1, a[i]);
+ }
+ deadManyInduction();
+ for (int i = 0; i < a.length; i++) {
+ expectEquals(2, a[i]);
+ }
+ deadSequence();
+ for (int i = 0; i < a.length; i++) {
+ expectEquals(3, a[i]);
+ }
+ try {
+ deadCycleWithException(-1);
+ throw new Error("Expected: IOOB exception");
+ } catch (IndexOutOfBoundsException e) {
+ }
+ for (int i = 0; i < a.length; i++) {
+ expectEquals(i == 0 ? 4 : 3, a[i]);
+ }
+ deadCycleWithException(0);
+ for (int i = 0; i < a.length; i++) {
+ expectEquals(4, a[i]);
+ }
+
+ int c = closedFormInductionUp();
+ expectEquals(12395, c);
+ c = closedFormInductionInAndDown(12345);
+ expectEquals(12295, c);
+ for (int n = -4; n < 10; n++) {
+ int tc = (n <= 0) ? 0 : n;
+ c = closedFormInductionUpN(n);
+ expectEquals(12345 + tc * 5, c);
+ c = closedFormInductionInAndDownN(12345, n);
+ expectEquals(12345 - tc * 5, c);
+ c = closedFormNested(n);
+ expectEquals(tc * 10, c);
+ }
+
+ for (int n = -4; n < 4; n++) {
+ int tc = (n <= 0) ? 0 : n;
+ expectEquals(tc, mainIndexReturned(n));
+ expectEquals(tc & 1, periodicReturned(n));
+ expectEquals((tc * (tc + 1)) / 2, getSum(n));
+ }
+ expectEquals(21, getSum21());
+ expectEquals(10, closedTwice());
+ expectEquals(20, closedFeed());
+ expectEquals(-10, closedLargeUp());
+ expectEquals(10, closedLargeDown());
+
+ expectEquals(100, exceptionExitBeforeAdd());
+ expectEquals(100, exceptionExitAfterAdd());
+ a = null;
+ expectEquals(-1, exceptionExitBeforeAdd());
+ expectEquals(-11, exceptionExitAfterAdd());
+ a = new int[4];
+ expectEquals(-41, exceptionExitBeforeAdd());
+ expectEquals(-51, exceptionExitAfterAdd());
+
+ System.out.println("passed");
+ }
+
+ private static void expectEquals(int expected, int result) {
+ if (expected != result) {
+ throw new Error("Expected: " + expected + ", found: " + result);
+ }
+ }
+}