More checker tests for BCE.
Also make sure the check on MonotonicValueRange narrow is more strict.
Plus some handling on array length division such as array.length/2.
Added checker tests for each case.
Change-Id: I9f32fc5f6ca1f3da8edec576de66b44d85a50bc6
diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index bcee563..26e58db 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -32,14 +32,7 @@
if (instruction != nullptr && instruction->IsIntConstant()) {
// Normalize ValueBound with constant instruction.
int32_t instr_const = instruction->AsIntConstant()->GetValue();
- if (constant >= 0 && (instr_const <= INT_MAX - constant)) {
- // No overflow.
- instruction_ = nullptr;
- constant_ = instr_const + constant;
- return;
- }
- if (constant < 0 && (instr_const >= INT_MIN - constant)) {
- // No underflow.
+ if (!WouldAddOverflowOrUnderflow(instr_const, constant)) {
instruction_ = nullptr;
constant_ = instr_const + constant;
return;
@@ -49,6 +42,22 @@
constant_ = constant;
}
+ // Return whether (left + right) overflows or underflows.
+ static bool WouldAddOverflowOrUnderflow(int32_t left, int32_t right) {
+ if (right == 0) {
+ return false;
+ }
+ if ((right > 0) && (left <= INT_MAX - right)) {
+ // No overflow.
+ return false;
+ }
+ if ((right < 0) && (left >= INT_MIN - right)) {
+ // No underflow.
+ return false;
+ }
+ return true;
+ }
+
static bool IsAddOrSubAConstant(HInstruction* instruction,
HInstruction** left_instruction,
int* right_constant) {
@@ -463,10 +472,23 @@
// Narrow the value range of `instruction` at the end of `basic_block` with `range`,
// and push the narrowed value range to `successor`.
void ApplyRangeFromComparison(HInstruction* instruction, HBasicBlock* basic_block,
- HBasicBlock* successor, ValueRange* range) {
+ HBasicBlock* successor, ValueRange* range) {
ValueRange* existing_range = LookupValueRange(instruction, basic_block);
- ValueRange* narrowed_range = (existing_range == nullptr) ?
- range : existing_range->Narrow(range);
+ if (existing_range == nullptr) {
+ if (range != nullptr) {
+ GetValueRangeMap(successor)->Overwrite(instruction->GetId(), range);
+ }
+ return;
+ }
+ if (existing_range->IsMonotonicValueRange()) {
+ DCHECK(instruction->IsLoopHeaderPhi());
+ // Make sure the comparison is in the loop header so each increment is
+ // checked with a comparison.
+ if (instruction->GetBlock() != basic_block) {
+ return;
+ }
+ }
+ ValueRange* narrowed_range = existing_range->Narrow(range);
if (narrowed_range != nullptr) {
GetValueRangeMap(successor)->Overwrite(instruction->GetId(), narrowed_range);
}
@@ -705,6 +727,15 @@
// Here we are interested in the typical triangular case of nested loops,
// such as the inner loop 'for (int j=0; j<array.length-i; j++)' where i
// is the index for outer loop. In this case, we know j is bounded by array.length-1.
+
+ // Try to handle (array.length - i) or (array.length + c - i) format.
+ HInstruction* left_of_left; // left input of left.
+ int32_t right_const = 0;
+ if (ValueBound::IsAddOrSubAConstant(left, &left_of_left, &right_const)) {
+ left = left_of_left;
+ }
+ // The value of left input of the sub equals (left + right_const).
+
if (left->IsArrayLength()) {
HInstruction* array_length = left->AsArrayLength();
ValueRange* right_range = LookupValueRange(right, sub->GetBlock());
@@ -715,19 +746,83 @@
HInstruction* upper_inst = upper.GetInstruction();
// Make sure it's the same array.
if (ValueBound::Equal(array_length, upper_inst)) {
- // (array.length - v) where v is in [c1, array.length + c2]
- // gets [-c2, array.length - c1] as its value range.
- ValueRange* range = new (GetGraph()->GetArena()) ValueRange(
- GetGraph()->GetArena(),
- ValueBound(nullptr, - upper.GetConstant()),
- ValueBound(array_length, - lower.GetConstant()));
- GetValueRangeMap(sub->GetBlock())->Overwrite(sub->GetId(), range);
+ int32_t c0 = right_const;
+ int32_t c1 = lower.GetConstant();
+ int32_t c2 = upper.GetConstant();
+ // (array.length + c0 - v) where v is in [c1, array.length + c2]
+ // gets [c0 - c2, array.length + c0 - c1] as its value range.
+ if (!ValueBound::WouldAddOverflowOrUnderflow(c0, -c2) &&
+ !ValueBound::WouldAddOverflowOrUnderflow(c0, -c1)) {
+ if ((c0 - c1) <= 0) {
+ // array.length + (c0 - c1) won't overflow/underflow.
+ ValueRange* range = new (GetGraph()->GetArena()) ValueRange(
+ GetGraph()->GetArena(),
+ ValueBound(nullptr, right_const - upper.GetConstant()),
+ ValueBound(array_length, right_const - lower.GetConstant()));
+ GetValueRangeMap(sub->GetBlock())->Overwrite(sub->GetId(), range);
+ }
+ }
}
}
}
}
}
+ void FindAndHandlePartialArrayLength(HBinaryOperation* instruction) {
+ DCHECK(instruction->IsDiv() || instruction->IsShr() || instruction->IsUShr());
+ HInstruction* right = instruction->GetRight();
+ int32_t right_const;
+ if (right->IsIntConstant()) {
+ right_const = right->AsIntConstant()->GetValue();
+ // Detect division by two or more.
+ if ((instruction->IsDiv() && right_const <= 1) ||
+ (instruction->IsShr() && right_const < 1) ||
+ (instruction->IsUShr() && right_const < 1)) {
+ return;
+ }
+ } else {
+ return;
+ }
+
+ // Try to handle array.length/2 or (array.length-1)/2 format.
+ HInstruction* left = instruction->GetLeft();
+ HInstruction* left_of_left; // left input of left.
+ int32_t c = 0;
+ if (ValueBound::IsAddOrSubAConstant(left, &left_of_left, &c)) {
+ left = left_of_left;
+ }
+ // The value of left input of instruction equals (left + c).
+
+ // (array_length + 1) or smaller divided by two or more
+ // always generate a value in [INT_MIN, array_length].
+ // This is true even if array_length is INT_MAX.
+ if (left->IsArrayLength() && c <= 1) {
+ if (instruction->IsUShr() && c < 0) {
+ // Make sure for unsigned shift, left side is not negative.
+ // e.g. if array_length is 2, ((array_length - 3) >>> 2) is way bigger
+ // than array_length.
+ return;
+ }
+ ValueRange* range = new (GetGraph()->GetArena()) ValueRange(
+ GetGraph()->GetArena(),
+ ValueBound(nullptr, INT_MIN),
+ ValueBound(left, 0));
+ GetValueRangeMap(instruction->GetBlock())->Overwrite(instruction->GetId(), range);
+ }
+ }
+
+ void VisitDiv(HDiv* div) {
+ FindAndHandlePartialArrayLength(div);
+ }
+
+ void VisitShr(HShr* shr) {
+ FindAndHandlePartialArrayLength(shr);
+ }
+
+ void VisitUShr(HUShr* ushr) {
+ FindAndHandlePartialArrayLength(ushr);
+ }
+
void VisitNewArray(HNewArray* new_array) {
HInstruction* len = new_array->InputAt(0);
if (!len->IsIntConstant()) {
diff --git a/compiler/optimizing/bounds_check_elimination_test.cc b/compiler/optimizing/bounds_check_elimination_test.cc
index 662834a..162e20a 100644
--- a/compiler/optimizing/bounds_check_elimination_test.cc
+++ b/compiler/optimizing/bounds_check_elimination_test.cc
@@ -632,7 +632,7 @@
ASSERT_TRUE(IsRemoved(bounds_check));
}
-// int[] array = new array[10];
+// int[] array = new int[10];
// for (int i=0; i<10; i+=increment) { array[i] = 10; }
static HGraph* BuildSSAGraph3(ArenaAllocator* allocator,
HInstruction** bounds_check,
@@ -708,7 +708,7 @@
ArenaPool pool;
ArenaAllocator allocator(&pool);
- // int[] array = new array[10];
+ // int[] array = new int[10];
// for (int i=0; i<10; i++) { array[i] = 10; // Can eliminate. }
HInstruction* bounds_check = nullptr;
HGraph* graph = BuildSSAGraph3(&allocator, &bounds_check, 0, 1, kCondGE);
@@ -718,7 +718,7 @@
bounds_check_elimination_after_gvn.Run();
ASSERT_TRUE(IsRemoved(bounds_check));
- // int[] array = new array[10];
+ // int[] array = new int[10];
// for (int i=1; i<10; i++) { array[i] = 10; // Can eliminate. }
graph = BuildSSAGraph3(&allocator, &bounds_check, 1, 1, kCondGE);
graph->BuildDominatorTree();
@@ -727,7 +727,7 @@
bounds_check_elimination_with_initial_1.Run();
ASSERT_TRUE(IsRemoved(bounds_check));
- // int[] array = new array[10];
+ // int[] array = new int[10];
// for (int i=0; i<=10; i++) { array[i] = 10; // Can't eliminate. }
graph = BuildSSAGraph3(&allocator, &bounds_check, 0, 1, kCondGT);
graph->BuildDominatorTree();
@@ -736,7 +736,7 @@
bounds_check_elimination_with_greater_than.Run();
ASSERT_FALSE(IsRemoved(bounds_check));
- // int[] array = new array[10];
+ // int[] array = new int[10];
// for (int i=1; i<10; i+=8) { array[i] = 10; // Can eliminate. }
graph = BuildSSAGraph3(&allocator, &bounds_check, 1, 8, kCondGE);
graph->BuildDominatorTree();
diff --git a/test/449-checker-bce/src/Main.java b/test/449-checker-bce/src/Main.java
index 5a0e13b..ad4092b 100644
--- a/test/449-checker-bce/src/Main.java
+++ b/test/449-checker-bce/src/Main.java
@@ -46,6 +46,7 @@
return primeCount;
}
+
// CHECK-START: void Main.narrow(int[], int) BCE (before)
// CHECK: BoundsCheck
// CHECK: ArraySet
@@ -61,8 +62,12 @@
// CHECK: ArraySet
// CHECK: BoundsCheck
// CHECK: ArraySet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
- static void narrow(int array[], int offset) {
+ static void narrow(int[] array, int offset) {
if (offset < 0) {
return;
}
@@ -87,10 +92,386 @@
// eliminate this bounds check.
array[biased_offset2] = 1;
}
+
+ // offset_sub1 won't underflow since offset is no less than 0.
+ int offset_sub1 = offset - Integer.MAX_VALUE;
+ if (offset_sub1 >= 0) {
+ array[offset_sub1] = 1; // Bounds check can be eliminated.
+ }
+
+ // offset_sub2 can underflow.
+ int offset_sub2 = offset_sub1 - Integer.MAX_VALUE;
+ if (offset_sub2 >= 0) {
+ array[offset_sub2] = 1; // Bounds check can't be eliminated.
+ }
}
}
+
+ // CHECK-START: void Main.constantIndexing(int[]) BCE (before)
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+
+ // CHECK-START: void Main.constantIndexing(int[]) BCE (after)
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+
+ static void constantIndexing(int[] array) {
+ array[5] = 1;
+ array[4] = 1;
+ array[6] = 1;
+ }
+
+
+ // CHECK-START: void Main.loopPattern1(int[]) BCE (before)
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+
+ // CHECK-START: void Main.loopPattern1(int[]) BCE (after)
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArraySet
+
+ static void loopPattern1(int[] array) {
+ for (int i = 0; i < array.length; i++) {
+ array[i] = 1; // Bounds check can be eliminated.
+ }
+
+ for (int i = 1; i < array.length; i++) {
+ array[i] = 1; // Bounds check can be eliminated.
+ }
+
+ for (int i = 1; i < array.length - 1; i++) {
+ array[i] = 1; // Bounds check can be eliminated.
+ }
+
+ for (int i = -1; i < array.length; i++) {
+ array[i] = 1; // Bounds check can't be eliminated.
+ }
+
+ for (int i = 0; i <= array.length; i++) {
+ array[i] = 1; // Bounds check can't be eliminated.
+ }
+
+ for (int i = 0; i < array.length; i += 2) {
+ // We don't have any assumption on max array length yet.
+ // Bounds check can't be eliminated due to overflow concern.
+ array[i] = 1;
+ }
+
+ for (int i = 1; i < array.length; i += 2) {
+ // Bounds check can be eliminated since i is odd so the last
+ // i that's less than array.length is at most (Integer.MAX_VALUE - 2).
+ array[i] = 1;
+ }
+ }
+
+
+ // CHECK-START: void Main.loopPattern2(int[]) BCE (before)
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+
+ // CHECK-START: void Main.loopPattern2(int[]) BCE (after)
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArraySet
+
+ static void loopPattern2(int[] array) {
+ for (int i = array.length - 1; i >= 0; i--) {
+ array[i] = 1; // Bounds check can be eliminated.
+ }
+
+ for (int i = array.length; i > 0; i--) {
+ array[i - 1] = 1; // Bounds check can be eliminated.
+ }
+
+ for (int i = array.length - 1; i > 0; i--) {
+ array[i] = 1; // Bounds check can be eliminated.
+ }
+
+ for (int i = array.length; i >= 0; i--) {
+ array[i] = 1; // Bounds check can't be eliminated.
+ }
+
+ for (int i = array.length; i >= 0; i--) {
+ array[i - 1] = 1; // Bounds check can't be eliminated.
+ }
+
+ for (int i = array.length; i > 0; i -= 20) {
+ // For i >= 0, (i - 20 - 1) is guaranteed not to underflow.
+ array[i - 1] = 1; // Bounds check can be eliminated.
+ }
+ }
+
+
+ // CHECK-START: void Main.loopPattern3(int[]) BCE (before)
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+
+ // CHECK-START: void Main.loopPattern3(int[]) BCE (after)
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+
+ static void loopPattern3(int[] array) {
+ java.util.Random random = new java.util.Random();
+ for (int i = 0; ; i++) {
+ if (random.nextInt() % 1000 == 0 && i < array.length) {
+ // Can't eliminate the bound check since not every i++ is
+ // matched with a array length check, so there is some chance that i
+ // overflows and is negative.
+ array[i] = 1;
+ }
+ }
+ }
+
+
+ // CHECK-START: void Main.constantNewArray() BCE (before)
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+
+ // CHECK-START: void Main.constantNewArray() BCE (after)
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+
+ static void constantNewArray() {
+ int[] array = new int[10];
+ for (int i = 0; i < 10; i++) {
+ array[i] = 1; // Bounds check can be eliminated.
+ }
+
+ for (int i = 0; i <= 10; i++) {
+ array[i] = 1; // Bounds check can't be eliminated.
+ }
+
+ array[0] = 1; // Bounds check can be eliminated.
+ array[9] = 1; // Bounds check can be eliminated.
+ array[10] = 1; // Bounds check can't be eliminated.
+ }
+
+ // CHECK-START: void Main.pyramid1(int[]) BCE (before)
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+
+ // CHECK-START: void Main.pyramid1(int[]) BCE (after)
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArraySet
+
+ // Set array to something like {0, 1, 2, 3, 2, 1, 0}.
+ static void pyramid1(int[] array) {
+ for (int i = 0; i < (array.length + 1) / 2; i++) {
+ array[i] = i;
+ array[array.length - 1 - i] = i;
+ }
+ }
+
+
+ // CHECK-START: void Main.pyramid2(int[]) BCE (before)
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+
+ // CHECK-START: void Main.pyramid2(int[]) BCE (after)
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArraySet
+
+ // Set array to something like {0, 1, 2, 3, 2, 1, 0}.
+ static void pyramid2(int[] array) {
+ for (int i = 0; i < (array.length + 1) >> 1; i++) {
+ array[i] = i;
+ array[array.length - 1 - i] = i;
+ }
+ }
+
+
+ // CHECK-START: void Main.pyramid3(int[]) BCE (before)
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+
+ // CHECK-START: void Main.pyramid3(int[]) BCE (after)
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArraySet
+
+ // Set array to something like {0, 1, 2, 3, 2, 1, 0}.
+ static void pyramid3(int[] array) {
+ for (int i = 0; i < (array.length + 1) >>> 1; i++) {
+ array[i] = i;
+ array[array.length - 1 - i] = i;
+ }
+ }
+
+
+ // TODO: bce on the array accesses in this method.
+ static boolean isPyramid(int[] array) {
+ int i = 0;
+ int j = array.length - 1;
+ while (i <= j) {
+ if (array[i] != i) {
+ return false;
+ }
+ if (array[j] != i) {
+ return false;
+ }
+ i++; j--;
+ }
+ return true;
+ }
+
+
+ // CHECK-START: void Main.bubbleSort(int[]) GVN (before)
+ // CHECK: BoundsCheck
+ // CHECK: ArrayGet
+ // CHECK: BoundsCheck
+ // CHECK: ArrayGet
+ // CHECK: BoundsCheck
+ // CHECK: ArrayGet
+ // CHECK: BoundsCheck
+ // CHECK: ArrayGet
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+
+ // CHECK-START: void Main.bubbleSort(int[]) GVN (after)
+ // CHECK: BoundsCheck
+ // CHECK: ArrayGet
+ // CHECK: BoundsCheck
+ // CHECK: ArrayGet
+ // CHECK-NOT: ArrayGet
+ // CHECK-NOT: ArrayGet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArraySet
+
+ // CHECK-START: void Main.bubbleSort(int[]) BCE (after)
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArrayGet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArrayGet
+ // CHECK-NOT: ArrayGet
+ // CHECK-NOT: ArrayGet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArraySet
+
+ static void bubbleSort(int[] array) {
+ for (int i = 0; i < array.length - 1; i++) {
+ for (int j = 0; j < array.length - i - 1; j++) {
+ if (array[j] > array[j + 1]) {
+ int temp = array[j + 1];
+ array[j + 1] = array[j];
+ array[j] = temp;
+ }
+ }
+ }
+ }
+
+
public static void main(String[] args) {
sieve(20);
+
+ int[] array = {5, 2, 3, 7, 0, 1, 6, 4};
+ bubbleSort(array);
+ for (int i = 0; i < 8; i++) {
+ if (array[i] != i) {
+ System.out.println("bubble sort failed!");
+ }
+ }
+
+ array = new int[7];
+ pyramid1(array);
+ if (!isPyramid(array)) {
+ System.out.println("pyramid1 failed!");
+ }
+
+ array = new int[8];
+ pyramid2(array);
+ if (!isPyramid(array)) {
+ System.out.println("pyramid2 failed!");
+ }
+
+ java.util.Arrays.fill(array, -1);
+ pyramid3(array);
+ if (!isPyramid(array)) {
+ System.out.println("pyramid3 failed!");
+ }
}
}