Recognize for (int i = 0; i != x.length; i++) loops
Rationale:
Idiom occurs in real-life and is very straightforwardly
recognized by existing induction/range machinery.
Change-Id: I965a16e9de72f3523ea5023d30ed1c4e47ed5010
diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc
index a1e1cde..82a898a 100644
--- a/compiler/optimizing/induction_var_analysis.cc
+++ b/compiler/optimizing/induction_var_analysis.cc
@@ -552,9 +552,11 @@
if (!IsExact(stride_expr, &stride_value)) {
return;
}
- // Rewrite condition i != U into i < U or i > U if end condition is reached exactly.
- if (cmp == kCondNE && ((stride_value == +1 && IsTaken(lower_expr, upper_expr, kCondLT)) ||
- (stride_value == -1 && IsTaken(lower_expr, upper_expr, kCondGT)))) {
+ // Rewrite condition i != U into strict end condition i < U or i > U if this end condition
+ // is reached exactly (tested by verifying if the loop has a unit stride and the non-strict
+ // condition would be always taken).
+ if (cmp == kCondNE && ((stride_value == +1 && IsTaken(lower_expr, upper_expr, kCondLE)) ||
+ (stride_value == -1 && IsTaken(lower_expr, upper_expr, kCondGE)))) {
cmp = stride_value > 0 ? kCondLT : kCondGT;
}
// Normalize a linear loop control with a nonzero stride:
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
index b162696..f9b6910 100644
--- a/compiler/optimizing/induction_var_range.cc
+++ b/compiler/optimizing/induction_var_range.cc
@@ -216,6 +216,14 @@
}
}
} while (RefineOuter(&v_min, &v_max));
+ // Exploit array length + c >= c, with c <= 0 to avoid arithmetic wrap-around anomalies
+ // (e.g. array length == maxint and c == 1 would yield minint).
+ if (request == kAtLeast) {
+ if (v_min.a_constant == 1 && v_min.b_constant <= 0 && v_min.instruction->IsArrayLength()) {
+ *value = v_min.b_constant;
+ return true;
+ }
+ }
}
return false;
}
diff --git a/test/530-checker-loops/src/Main.java b/test/530-checker-loops/src/Main.java
index 0c32491..8db7338 100644
--- a/test/530-checker-loops/src/Main.java
+++ b/test/530-checker-loops/src/Main.java
@@ -394,6 +394,34 @@
return result;
}
+ /// CHECK-START: int Main.linearForNEArrayLengthUp(int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ //
+ /// CHECK-START: int Main.linearForNEArrayLengthUp(int[]) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
+ private static int linearForNEArrayLengthUp(int[] x) {
+ int result = 0;
+ for (int i = 0; i != x.length; i++) {
+ result += x[i];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.linearForNEArrayLengthDown(int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ //
+ /// CHECK-START: int Main.linearForNEArrayLengthDown(int[]) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
+ private static int linearForNEArrayLengthDown(int[] x) {
+ int result = 0;
+ for (int i = x.length - 1; i != -1; i--) {
+ result += x[i];
+ }
+ return result;
+ }
+
/// CHECK-START: int Main.linearDoWhileUp() BCE (before)
/// CHECK-DAG: BoundsCheck
//
@@ -1392,6 +1420,8 @@
// Special forms.
expectEquals(55, linearForNEUp());
expectEquals(55, linearForNEDown());
+ expectEquals(55, linearForNEArrayLengthUp(x));
+ expectEquals(55, linearForNEArrayLengthDown(x));
expectEquals(55, linearDoWhileUp());
expectEquals(55, linearDoWhileDown());
expectEquals(55, linearShort());
