Enhance BCE range analysis with length "alias" case.

Rationale:
Removes bounds check when trip count uses
an array length "alias" in the SSA flow.
Yields about 5% on micro benchmark.

Bug: b/70688025

Test: test-art-host test-art-target
Change-Id: I9047432622bddba4c6afd8b309dcc5b7496912ac

2 files changed, 115 insertions, 18 deletions

diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index 9c2068ec5e..147df1e3e8 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -302,7 +302,7 @@ class ValueRange : public ArenaObject<kArenaAllocBoundsCheckElimination> {
   ValueBound GetLower() const { return lower_; }
   ValueBound GetUpper() const { return upper_; }
 
-  bool IsConstantValueRange() { return lower_.IsConstant() && upper_.IsConstant(); }
+  bool IsConstantValueRange() const { return lower_.IsConstant() && upper_.IsConstant(); }
 
   // If it's certain that this value range fits in other_range.
   virtual bool FitsIn(ValueRange* other_range) const {
@@ -789,24 +789,33 @@ class BCEVisitor : public HGraphVisitor {
         ApplyRangeFromComparison(left, block, false_successor, new_range);
       }
     } else if (cond == kCondNE || cond == kCondEQ) {
-      if (left->IsArrayLength() && lower.IsConstant() && upper.IsConstant()) {
-        // Special case:
-        //   length == [c,d] yields [c, d] along true
-        //   length != [c,d] yields [c, d] along false
-        if (!lower.Equals(ValueBound::Min()) || !upper.Equals(ValueBound::Max())) {
-          ValueRange* new_range = new (&allocator_) ValueRange(&allocator_, lower, upper);
-          ApplyRangeFromComparison(
-              left, block, cond == kCondEQ ? true_successor : false_successor, new_range);
-        }
-        // In addition:
-        //   length == 0 yields [1, max] along false
-        //   length != 0 yields [1, max] along true
-        if (lower.GetConstant() == 0 && upper.GetConstant() == 0) {
-          ValueRange* new_range = new (&allocator_) ValueRange(
-              &allocator_, ValueBound(nullptr, 1), ValueBound::Max());
-          ApplyRangeFromComparison(
-              left, block, cond == kCondEQ ? false_successor : true_successor, new_range);
+      if (left->IsArrayLength()) {
+        if (lower.IsConstant() && upper.IsConstant()) {
+          // Special case:
+          //   length == [c,d] yields [c, d] along true
+          //   length != [c,d] yields [c, d] along false
+          if (!lower.Equals(ValueBound::Min()) || !upper.Equals(ValueBound::Max())) {
+            ValueRange* new_range = new (&allocator_) ValueRange(&allocator_, lower, upper);
+            ApplyRangeFromComparison(
+                left, block, cond == kCondEQ ? true_successor : false_successor, new_range);
+          }
+          // In addition:
+          //   length == 0 yields [1, max] along false
+          //   length != 0 yields [1, max] along true
+          if (lower.GetConstant() == 0 && upper.GetConstant() == 0) {
+            ValueRange* new_range = new (&allocator_) ValueRange(
+                &allocator_, ValueBound(nullptr, 1), ValueBound::Max());
+            ApplyRangeFromComparison(
+                left, block, cond == kCondEQ ? false_successor : true_successor, new_range);
+          }
         }
+      } else if (lower.IsRelatedToArrayLength() && lower.Equals(upper)) {
+        // Special aliasing case, with x not array length itself:
+        //   x == [length,length] yields x == length along true
+        //   x != [length,length] yields x == length along false
+        ValueRange* new_range = new (&allocator_) ValueRange(&allocator_, lower, upper);
+        ApplyRangeFromComparison(
+            left, block, cond == kCondEQ ? true_successor : false_successor, new_range);
       }
     }
   }
diff --git a/test/449-checker-bce/src/Main.java b/test/449-checker-bce/src/Main.java
index 60e653c72f..3506649d3c 100644
--- a/test/449-checker-bce/src/Main.java
+++ b/test/449-checker-bce/src/Main.java
@@ -1057,6 +1057,64 @@ public class Main {
     }
   }
 
+  /// CHECK-START: void Main.lengthAlias1(int[], int) BCE (before)
+  /// CHECK-DAG: <<Arr:l\d+>> ParameterValue                loop:none
+  /// CHECK-DAG: <<Par:i\d+>> ParameterValue                loop:none
+  /// CHECK-DAG: <<Nul:l\d+>> NullCheck [<<Arr>>]           loop:none
+  /// CHECK-DAG: <<Len:i\d+>> ArrayLength [<<Nul>>]         loop:none
+  /// CHECK-DAG:              NotEqual [<<Par>>,<<Len>>]    loop:none
+  /// CHECK-DAG: <<Idx:i\d+>> Phi                           loop:<<Loop:B\d+>>
+  /// CHECK-DAG:              BoundsCheck [<<Idx>>,<<Len>>] loop:<<Loop>>
+  //
+  /// CHECK-START: void Main.lengthAlias1(int[], int) BCE (after)
+  /// CHECK-NOT:              BoundsCheck
+  public static void lengthAlias1(int[] a, int len) {
+    if (len == a.length) {
+      for (int i = 0; i < len; i++) {
+        a[i] = 1;
+      }
+    }
+  }
+
+  /// CHECK-START: void Main.lengthAlias2(int[], int) BCE (before)
+  /// CHECK-DAG: <<Arr:l\d+>> ParameterValue                loop:none
+  /// CHECK-DAG: <<Par:i\d+>> ParameterValue                loop:none
+  /// CHECK-DAG: <<Nul:l\d+>> NullCheck [<<Arr>>]           loop:none
+  /// CHECK-DAG: <<Len:i\d+>> ArrayLength [<<Nul>>]         loop:none
+  /// CHECK-DAG:              Equal [<<Par>>,<<Len>>]       loop:none
+  /// CHECK-DAG: <<Idx:i\d+>> Phi                           loop:<<Loop:B\d+>>
+  /// CHECK-DAG:              BoundsCheck [<<Idx>>,<<Len>>] loop:<<Loop>>
+  //
+  /// CHECK-START: void Main.lengthAlias2(int[], int) BCE (after)
+  /// CHECK-NOT:              BoundsCheck
+  public static void lengthAlias2(int[] a, int len) {
+    if (len != a.length) {
+      return;
+    }
+    for (int i = 0; i < len; i++) {
+      a[i] = 2;
+    }
+  }
+
+  /// CHECK-START: void Main.lengthAlias3(int[], int) BCE (before)
+  /// CHECK-DAG: <<Arr:l\d+>> ParameterValue                loop:none
+  /// CHECK-DAG: <<Par:i\d+>> ParameterValue                loop:none
+  /// CHECK-DAG: <<Nul:l\d+>> NullCheck [<<Arr>>]           loop:none
+  /// CHECK-DAG: <<Len:i\d+>> ArrayLength [<<Nul>>]         loop:none
+  /// CHECK-DAG:              NotEqual [<<Par>>,<<Len>>]    loop:none
+  /// CHECK-DAG: <<Idx:i\d+>> Phi                           loop:<<Loop:B\d+>>
+  /// CHECK-DAG:              BoundsCheck [<<Idx>>,<<Len>>] loop:<<Loop>>
+  //
+  /// CHECK-START: void Main.lengthAlias3(int[], int) BCE (after)
+  /// CHECK-NOT:              BoundsCheck
+  public static void lengthAlias3(int[] a, int len) {
+    if (a.length == len) {
+      for (int i = 0; i < len; i++) {
+        a[i] = 3;
+      }
+    }
+  }
+
   static int[][] mA;
 
   /// CHECK-START: void Main.dynamicBCEAndIntrinsic(int) BCE (before)
@@ -1747,10 +1805,40 @@ public class Main {
       System.out.println("nonzero length failed!");
     }
 
+    array = new int[8];
+    lengthAlias1(array, 8);
+    for (int i = 0; i < 8; i++) {
+      if (array[i] != 1) {
+        System.out.println("alias1 failed!");
+      }
+    }
+    lengthAlias2(array, 8);
+    for (int i = 0; i < 8; i++) {
+      if (array[i] != 2) {
+        System.out.println("alias2 failed!");
+      }
+    }
+    lengthAlias3(array, 8);
+    for (int i = 0; i < 8; i++) {
+      if (array[i] != 3) {
+        System.out.println("alias3 failed!");
+      }
+    }
+
+    lengthAlias1(array, /*mismatched value*/ 32);
+    for (int i = 0; i < 8; i++) {
+      if (array[i] != 3) {
+        System.out.println("mismatch failed!");
+      }
+    }
+
     // Zero length array does not break.
     array = new int[0];
     nonzeroLength(array);
     knownLength(array);
+    lengthAlias1(array, 0);
+    lengthAlias2(array, 0);
+    lengthAlias3(array, 0);
 
     mA = new int[4][4];
     for (int i = 0; i < 4; i++) {