Added polynomial induction variables analysis. With tests.
Rationale:
Information on polynomial sequences is nice to further enhance
BCE and last-value assignment. In this case, this CL enables more
loop optimizations for benchpress' Sum (80 x speedup). Also
changed rem-based geometric induction to wrap-around induction.
Test: test-art-host
Change-Id: Ie4d2659edefb814edda2c971c1f70ba400c31111
diff --git a/test/618-checker-induction/src/Main.java b/test/618-checker-induction/src/Main.java
index f85479a..87a69b2 100644
--- a/test/618-checker-induction/src/Main.java
+++ b/test/618-checker-induction/src/Main.java
@@ -25,7 +25,7 @@
/// 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
+ /// CHECK-NOT: Phi
static void deadSingleLoop() {
for (int i = 0; i < 4; i++) {
}
@@ -35,7 +35,7 @@
/// 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
+ /// CHECK-NOT: Phi
static void deadSingleLoopN(int n) {
for (int i = 0; i < n; i++) {
}
@@ -56,7 +56,7 @@
/// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:<<Loop>>
//
/// CHECK-START: void Main.deadNestedLoops() loop_optimization (after)
- /// CHECK-NOT: Phi loop:{{B\d+}}
+ /// CHECK-NOT: Phi
static void deadNestedLoops() {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
@@ -74,7 +74,7 @@
/// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:none
//
/// CHECK-START: void Main.deadNestedAndFollowingLoops() loop_optimization (after)
- /// CHECK-NOT: Phi loop:{{B\d+}}
+ /// CHECK-NOT: Phi
static void deadNestedAndFollowingLoops() {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
@@ -96,7 +96,7 @@
/// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:none
//
/// CHECK-START: void Main.deadConditional(int) loop_optimization (after)
- /// CHECK-NOT: Phi loop:{{B\d+}}
+ /// CHECK-NOT: Phi
public static void deadConditional(int n) {
int k = 0;
int m = 0;
@@ -116,7 +116,7 @@
/// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none
//
/// CHECK-START: void Main.deadConditionalCycle(int) loop_optimization (after)
- /// CHECK-NOT: Phi loop:{{B\d+}}
+ /// CHECK-NOT: Phi
public static void deadConditionalCycle(int n) {
int k = 0;
int m = 0;
@@ -215,12 +215,11 @@
/// 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
+ /// CHECK-NOT: Phi
//
/// CHECK-START: int Main.closedFormInductionUp() instruction_simplifier$after_bce (after)
- /// CHECK-DAG: <<Int:i\d+>> IntConstant 12395
- /// CHECK-DAG: Return [<<Int>>] loop:none
+ /// CHECK-DAG: <<Int:i\d+>> IntConstant 12395 loop:none
+ /// CHECK-DAG: Return [<<Int>>] loop:none
static int closedFormInductionUp() {
int closed = 12345;
for (int i = 0; i < 10; i++) {
@@ -235,8 +234,13 @@
/// 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
+ /// CHECK-NOT: Phi
+ //
+ /// CHECK-START: int Main.closedFormInductionInAndDown(int) instruction_simplifier$after_bce (after)
+ /// CHECK-DAG: <<Par:i\d+>> ParameterValue loop:none
+ /// CHECK-DAG: <<Int:i\d+>> IntConstant -50 loop:none
+ /// CHECK-DAG: <<Add:i\d+>> Add [<<Int>>,<<Par>>] loop:none
+ /// CHECK-DAG: Return [<<Add>>] loop:none
static int closedFormInductionInAndDown(int closed) {
for (int i = 0; i < 10; i++) {
closed -= 5;
@@ -252,12 +256,10 @@
/// 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
+ /// CHECK-NOT: Phi
//
/// CHECK-START: int Main.closedFormNested() instruction_simplifier$after_bce (after)
- /// CHECK-DAG: <<Int:i\d+>> IntConstant 100
+ /// CHECK-DAG: <<Int:i\d+>> IntConstant 100 loop:none
/// CHECK-DAG: Return [<<Int>>] loop:none
static int closedFormNested() {
int closed = 0;
@@ -277,13 +279,11 @@
/// 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
+ /// CHECK-NOT: Phi
//
/// CHECK-START: int Main.closedFormNestedAlt() instruction_simplifier$after_bce (after)
- /// CHECK-DAG: <<Int:i\d+>> IntConstant 15082
- /// CHECK-DAG: Return [<<Int>>] loop:none
+ /// CHECK-DAG: <<Int:i\d+>> IntConstant 15082 loop:none
+ /// CHECK-DAG: Return [<<Int>>] loop:none
static int closedFormNestedAlt() {
int closed = 12345;
for (int i = 0; i < 17; i++) {
@@ -360,11 +360,10 @@
/// CHECK-DAG: Return [<<Phi>>] loop:none
//
/// CHECK-START: int Main.mainIndexReturned() loop_optimization (after)
- /// CHECK-NOT: Phi loop:{{B\d+}} outer_loop:none
- /// CHECK-DAG: Return loop:none
+ /// CHECK-NOT: Phi
//
/// CHECK-START: int Main.mainIndexReturned() instruction_simplifier$after_bce (after)
- /// CHECK-DAG: <<Int:i\d+>> IntConstant 10
+ /// CHECK-DAG: <<Int:i\d+>> IntConstant 10 loop:none
/// CHECK-DAG: Return [<<Int>>] loop:none
static int mainIndexReturned() {
int i;
@@ -378,11 +377,10 @@
/// CHECK-DAG: Return [<<Phi2>>] loop:none
//
/// CHECK-START: int Main.periodicReturned9() loop_optimization (after)
- /// CHECK-NOT: Phi loop:{{B\d+}} outer_loop:none
- /// CHECK-DAG: Return loop:none
+ /// CHECK-NOT: Phi
//
/// CHECK-START: int Main.periodicReturned9() instruction_simplifier$after_bce (after)
- /// CHECK-DAG: <<Int:i\d+>> IntConstant 1
+ /// CHECK-DAG: <<Int:i\d+>> IntConstant 1 loop:none
/// CHECK-DAG: Return [<<Int>>] loop:none
static int periodicReturned9() {
int k = 0;
@@ -398,11 +396,10 @@
/// CHECK-DAG: Return [<<Phi2>>] loop:none
//
/// CHECK-START: int Main.periodicReturned10() loop_optimization (after)
- /// CHECK-NOT: Phi loop:{{B\d+}} outer_loop:none
- /// CHECK-DAG: Return loop:none
+ /// CHECK-NOT: Phi
//
/// CHECK-START: int Main.periodicReturned10() instruction_simplifier$after_bce (after)
- /// CHECK-DAG: <<Int:i\d+>> IntConstant 0
+ /// CHECK-DAG: <<Int:i\d+>> IntConstant 0 loop:none
/// CHECK-DAG: Return [<<Int>>] loop:none
static int periodicReturned10() {
int k = 0;
@@ -412,7 +409,18 @@
return k;
}
- // If ever replaced by closed form, last value should be correct!
+ /// CHECK-START: int Main.getSum21() 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: <<Phi3:i\d+>> Phi loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: Return [<<Phi3>>] loop:none
+ //
+ /// CHECK-START: int Main.getSum21() loop_optimization (after)
+ /// CHECK-NOT: Phi
+ //
+ /// CHECK-START: int Main.getSum21() instruction_simplifier$after_bce (after)
+ /// CHECK-DAG: <<Int:i\d+>> IntConstant 21 loop:none
+ /// CHECK-DAG: Return [<<Int>>] loop:none
private static int getSum21() {
int k = 0;
int sum = 0;
@@ -436,8 +444,7 @@
/// CHECK-DAG: Return [<<Phi2>>] loop:none
//
/// CHECK-START: int Main.periodicReturnedN(int) loop_optimization (after)
- /// CHECK-NOT: Phi loop:{{B\d+}} outer_loop:none
- /// CHECK-DAG: Return loop:none
+ /// CHECK-NOT: Phi
static int periodicReturnedN(int n) {
int k = 0;
for (int i = 0; i < n; i++) {
@@ -480,11 +487,10 @@
/// 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
+ /// CHECK-NOT: Phi
//
/// CHECK-START: int Main.closedFeed() instruction_simplifier$after_bce (after)
- /// CHECK-DAG: <<Int:i\d+>> IntConstant 20
+ /// CHECK-DAG: <<Int:i\d+>> IntConstant 20 loop:none
/// CHECK-DAG: Return [<<Int>>] loop:none
private static int closedFeed() {
int closed = 0;
@@ -505,11 +511,10 @@
/// 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
+ /// CHECK-NOT: Phi
//
/// CHECK-START: int Main.closedLargeUp() instruction_simplifier$after_bce (after)
- /// CHECK-DAG: <<Int:i\d+>> IntConstant -10
+ /// CHECK-DAG: <<Int:i\d+>> IntConstant -10 loop:none
/// CHECK-DAG: Return [<<Int>>] loop:none
private static int closedLargeUp() {
int closed = 0;
@@ -525,11 +530,10 @@
/// 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
+ /// CHECK-NOT: Phi
//
/// CHECK-START: int Main.closedLargeDown() instruction_simplifier$after_bce (after)
- /// CHECK-DAG: <<Int:i\d+>> IntConstant 10
+ /// CHECK-DAG: <<Int:i\d+>> IntConstant 10 loop:none
/// CHECK-DAG: Return [<<Int>>] loop:none
private static int closedLargeDown() {
int closed = 0;
@@ -548,11 +552,10 @@
/// CHECK-DAG: Return [<<Phi5>>] loop:none
//
/// CHECK-START: int Main.waterFall() loop_optimization (after)
- /// CHECK-NOT: Phi loop:B\d+ outer_loop:none
- /// CHECK-DAG: Return loop:none
+ /// CHECK-NOT: Phi
//
/// CHECK-START: int Main.waterFall() instruction_simplifier$after_bce (after)
- /// CHECK-DAG: <<Int:i\d+>> IntConstant 50
+ /// CHECK-DAG: <<Int:i\d+>> IntConstant 50 loop:none
/// CHECK-DAG: Return [<<Int>>] loop:none
private static int waterFall() {
int i = 0;
@@ -570,11 +573,10 @@
/// CHECK-DAG: Return [<<Phi2>>] loop:none
//
/// CHECK-START: boolean Main.periodicBoolIdiom1() loop_optimization (after)
- /// CHECK-NOT: Phi loop:{{B\d+}} outer_loop:none
- /// CHECK-DAG: Return loop:none
+ /// CHECK-NOT: Phi
//
/// CHECK-START: boolean Main.periodicBoolIdiom1() instruction_simplifier$after_bce (after)
- /// CHECK-DAG: <<Int:i\d+>> IntConstant 0
+ /// CHECK-DAG: <<Int:i\d+>> IntConstant 0 loop:none
/// CHECK-DAG: Return [<<Int>>] loop:none
private static boolean periodicBoolIdiom1() {
boolean x = true;
@@ -590,11 +592,10 @@
/// CHECK-DAG: Return [<<Phi2>>] loop:none
//
/// CHECK-START: boolean Main.periodicBoolIdiom2() loop_optimization (after)
- /// CHECK-NOT: Phi loop:{{B\d+}} outer_loop:none
- /// CHECK-DAG: Return loop:none
+ /// CHECK-NOT: Phi
//
/// CHECK-START: boolean Main.periodicBoolIdiom2() instruction_simplifier$after_bce (after)
- /// CHECK-DAG: <<Int:i\d+>> IntConstant 0
+ /// CHECK-DAG: <<Int:i\d+>> IntConstant 0 loop:none
/// CHECK-DAG: Return [<<Int>>] loop:none
private static boolean periodicBoolIdiom2() {
boolean x = true;
@@ -610,11 +611,10 @@
/// CHECK-DAG: Return [<<Phi2>>] loop:none
//
/// CHECK-START: boolean Main.periodicBoolIdiom3() loop_optimization (after)
- /// CHECK-NOT: Phi loop:{{B\d+}} outer_loop:none
- /// CHECK-DAG: Return loop:none
+ /// CHECK-NOT: Phi
//
/// CHECK-START: boolean Main.periodicBoolIdiom3() instruction_simplifier$after_bce (after)
- /// CHECK-DAG: <<Int:i\d+>> IntConstant 0
+ /// CHECK-DAG: <<Int:i\d+>> IntConstant 0 loop:none
/// CHECK-DAG: Return [<<Int>>] loop:none
private static boolean periodicBoolIdiom3() {
boolean x = true;
@@ -630,8 +630,7 @@
/// CHECK-DAG: Return [<<Phi2>>] loop:none
//
/// CHECK-START: boolean Main.periodicBoolIdiom1N(boolean, int) loop_optimization (after)
- /// CHECK-NOT: Phi loop:{{B\d+}} outer_loop:none
- /// CHECK-DAG: Return loop:none
+ /// CHECK-NOT: Phi
private static boolean periodicBoolIdiom1N(boolean x, int n) {
for (int i = 0; i < n; i++) {
x = !x;
@@ -645,8 +644,7 @@
/// CHECK-DAG: Return [<<Phi2>>] loop:none
//
/// CHECK-START: boolean Main.periodicBoolIdiom2N(boolean, int) loop_optimization (after)
- /// CHECK-NOT: Phi loop:{{B\d+}} outer_loop:none
- /// CHECK-DAG: Return loop:none
+ /// CHECK-NOT: Phi
private static boolean periodicBoolIdiom2N(boolean x, int n) {
for (int i = 0; i < n; i++) {
x = (x != true);
@@ -660,8 +658,7 @@
/// CHECK-DAG: Return [<<Phi2>>] loop:none
//
/// CHECK-START: boolean Main.periodicBoolIdiom3N(boolean, int) loop_optimization (after)
- /// CHECK-NOT: Phi loop:{{B\d+}} outer_loop:none
- /// CHECK-DAG: Return loop:none
+ /// CHECK-NOT: Phi
private static boolean periodicBoolIdiom3N(boolean x, int n) {
for (int i = 0; i < n; i++) {
x = (x == false);