summaryrefslogtreecommitdiff
path: root/compiler
diff options
context:
space:
mode:
Diffstat (limited to 'compiler')
-rw-r--r--compiler/optimizing/bounds_check_elimination.cc131
-rw-r--r--compiler/optimizing/bounds_check_elimination_test.cc10
2 files changed, 118 insertions, 23 deletions
diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index bcee5638fc..26e58dbc8d 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -32,14 +32,7 @@ class ValueBound : public ValueObject {
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 @@ class ValueBound : public ValueObject {
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 @@ class BCEVisitor : public HGraphVisitor {
// 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 @@ class BCEVisitor : public HGraphVisitor {
// 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 @@ class BCEVisitor : public HGraphVisitor {
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 662834a91c..162e20ade8 100644
--- a/compiler/optimizing/bounds_check_elimination_test.cc
+++ b/compiler/optimizing/bounds_check_elimination_test.cc
@@ -632,7 +632,7 @@ TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination2) {
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 @@ TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination3) {
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 @@ TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination3) {
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 @@ TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination3) {
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 @@ TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination3) {
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();
generated by cgit v1.2.3-59-g8ed1b (git 2.39.0) at 2026-01-08 06:51:50 +0000