Improved and simplified loop optimizations.
Rationale:
Empty preheader simplification has been simplified
to a much more general empty block removal optimization
step. Incremental updating of induction variable
analysis enables repeated elimination or simplification
of induction cycles.
This enabled an extra layer of optimization for
e.g. Benchpress Loop (17.5us. -> 0.24us. -> 0.08us).
So the original 73x speedup is now multiplied
by another 3x, for a total of about 218x.
Test: 618-checker-induction et al.
Change-Id: I394699981481cdd5357e0531bce88cd48bd32879
diff --git a/test/618-checker-induction/src/Main.java b/test/618-checker-induction/src/Main.java
index 0ea85da..5c789cd 100644
--- a/test/618-checker-induction/src/Main.java
+++ b/test/618-checker-induction/src/Main.java
@@ -134,17 +134,20 @@
/// 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-NOT: BoundsCheck
//
/// 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
+ /// CHECK-NOT: 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.
+ // Increment value of dead cycle may throw exception. Dynamic
+ // BCE takes care of the bounds check though, which enables
+ // removing the ArrayGet after removing the dead cycle.
dead += a[k];
}
}
@@ -180,7 +183,17 @@
return closed; // only needs last value
}
- // TODO: move closed form even further out?
+ /// CHECK-START: int Main.closedFormNested() 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:<<Loop1>>
+ /// CHECK-DAG: <<Phi4:i\d+>> Phi loop:<<Loop2>> outer_loop:<<Loop1>>
+ /// CHECK-DAG: Return [<<Phi1>>] loop:none
+ //
+ /// CHECK-START: int Main.closedFormNested() loop_optimization (after)
+ /// CHECK-NOT: Phi loop:{{B\d+}} outer_loop:none
+ /// CHECK-NOT: Phi loop:{{B\d+}} outer_loop:loop{{B\d+}}
+ /// CHECK-DAG: Return loop:none
static int closedFormNested() {
int closed = 0;
for (int i = 0; i < 10; i++) {
@@ -191,6 +204,27 @@
return closed; // only needs last-value
}
+ /// CHECK-START: int Main.closedFormNestedAlt() 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:<<Loop1>>
+ /// CHECK-DAG: <<Phi4:i\d+>> Phi loop:<<Loop2>> outer_loop:<<Loop1>>
+ /// CHECK-DAG: Return [<<Phi1>>] loop:none
+ //
+ /// CHECK-START: int Main.closedFormNestedAlt() loop_optimization (after)
+ /// CHECK-NOT: Phi loop:{{B\d+}} outer_loop:none
+ /// CHECK-NOT: Phi loop:{{B\d+}} outer_loop:loop{{B\d+}}
+ /// CHECK-DAG: Return loop:none
+ static int closedFormNestedAlt() {
+ int closed = 12345;
+ for (int i = 0; i < 17; i++) {
+ for (int j = 0; j < 23; j++) {
+ closed += 7;
+ }
+ }
+ return closed; // only needs last-value
+ }
+
// TODO: taken test around closed form?
static int closedFormInductionUpN(int n) {
int closed = 12345;
@@ -220,9 +254,20 @@
}
// TODO: move closed form even further out?
- static int closedFormNestedNN(int n) {
- int closed = 0;
+ static int closedFormNestedNAlt(int n) {
+ int closed = 12345;
for (int i = 0; i < n; i++) {
+ for (int j = 0; j < 23; j++) {
+ closed += 7;
+ }
+ }
+ return closed; // only needs last-value
+ }
+
+ // TODO: move closed form even further out?
+ static int closedFormNestedMN(int m, int n) {
+ int closed = 0;
+ for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
closed++;
}
@@ -230,6 +275,17 @@
return closed; // only needs last-value
}
+ // TODO: move closed form even further out?
+ static int closedFormNestedMNAlt(int m, int n) {
+ int closed = 12345;
+ for (int i = 0; i < m; i++) {
+ for (int j = 0; j < n; j++) {
+ closed += 7;
+ }
+ }
+ return closed; // only needs last-value
+ }
+
/// CHECK-START: int Main.mainIndexReturned() loop_optimization (before)
/// CHECK-DAG: <<Phi:i\d+>> Phi loop:{{B\d+}} outer_loop:none
/// CHECK-DAG: Return [<<Phi>>] loop:none
@@ -444,12 +500,15 @@
expectEquals(12395, closedFormInductionUp());
expectEquals(12295, closedFormInductionInAndDown(12345));
expectEquals(10 * 10, closedFormNested());
+ expectEquals(12345 + 17 * 23 * 7, closedFormNestedAlt());
for (int n = -4; n < 10; n++) {
int tc = (n <= 0) ? 0 : n;
expectEquals(12345 + tc * 5, closedFormInductionUpN(n));
expectEquals(12345 - tc * 5, closedFormInductionInAndDownN(12345, n));
expectEquals(tc * 10, closedFormNestedN(n));
- expectEquals(tc * tc, closedFormNestedNN(n));
+ expectEquals(12345 + tc * 23 * 7, closedFormNestedNAlt(n));
+ expectEquals(tc * (tc + 1), closedFormNestedMN(n, n + 1));
+ expectEquals(12345 + tc * (tc + 1) * 7, closedFormNestedMNAlt(n, n + 1));
}
expectEquals(10, mainIndexReturned());