Merge "Recognize for (int i = 0; i != x.length; i++) loops"

3 files changed, 43 insertions, 3 deletions

diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc
index a1e1cde9df..82a898a9f1 100644
--- a/compiler/optimizing/induction_var_analysis.cc
+++ b/compiler/optimizing/induction_var_analysis.cc
@@ -552,9 +552,11 @@ void HInductionVarAnalysis::VisitCondition(HLoopInformation* loop,
     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 b162696a42..f9b6910acd 100644
--- a/compiler/optimizing/induction_var_range.cc
+++ b/compiler/optimizing/induction_var_range.cc
@@ -216,6 +216,14 @@ bool InductionVarRange::IsConstant(HInductionVarAnalysis::InductionInfo* info,
         }
       }
     } 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 8633745a8a..d5111b0c14 100644
--- a/test/530-checker-loops/src/Main.java
+++ b/test/530-checker-loops/src/Main.java
@@ -394,6 +394,34 @@ public class Main {
     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
   //
@@ -670,6 +698,8 @@ public class Main {
     // 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());