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
diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index 9c2068e..147df1e 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -302,7 +302,7 @@
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 @@
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);
+ 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);
+ }
}
- // 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 60e653c..3506649 100644
--- a/test/449-checker-bce/src/Main.java
+++ b/test/449-checker-bce/src/Main.java
@@ -1057,6 +1057,64 @@
}
}
+ /// 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 @@
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++) {