Merge "HRem support in BCE."
diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index c166deb..2f96cfa 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -1121,6 +1121,66 @@
}
}
+ void VisitRem(HRem* instruction) OVERRIDE {
+ HInstruction* left = instruction->GetLeft();
+ HInstruction* right = instruction->GetRight();
+
+ // Handle 'i % CONST' format expression in array index, e.g:
+ // array[i % 20];
+ if (right->IsIntConstant()) {
+ int32_t right_const = std::abs(right->AsIntConstant()->GetValue());
+ if (right_const == 0) {
+ return;
+ }
+ // The sign of divisor CONST doesn't affect the sign final value range.
+ // For example:
+ // if (i > 0) {
+ // array[i % 10]; // index value range [0, 9]
+ // array[i % -10]; // index value range [0, 9]
+ // }
+ ValueRange* right_range = new (GetGraph()->GetArena()) ValueRange(
+ GetGraph()->GetArena(),
+ ValueBound(nullptr, 1 - right_const),
+ ValueBound(nullptr, right_const - 1));
+
+ ValueRange* left_range = LookupValueRange(left, left->GetBlock());
+ if (left_range != nullptr) {
+ right_range = left_range->Narrow(right_range);
+ }
+ AssignRange(instruction->GetBlock(), instruction, right_range);
+ return;
+ }
+
+ // Handle following pattern:
+ // i0 NullCheck
+ // i1 ArrayLength[i0]
+ // i2 DivByZeroCheck [i1] <-- right
+ // i3 Rem [i5, i2] <-- we are here.
+ // i4 BoundsCheck [i3,i1]
+ if (right->IsDivZeroCheck()) {
+ // if array_length can pass div-by-zero check,
+ // array_length must be > 0.
+ right = right->AsDivZeroCheck()->InputAt(0);
+ }
+
+ // Handle 'i % array.length' format expression in array index, e.g:
+ // array[(i+7) % array.length];
+ if (right->IsArrayLength()) {
+ ValueBound lower = ValueBound::Min(); // ideally, lower should be '1-array_length'.
+ ValueBound upper = ValueBound(right, -1); // array_length - 1
+ ValueRange* right_range = new (GetGraph()->GetArena()) ValueRange(
+ GetGraph()->GetArena(),
+ lower,
+ upper);
+ ValueRange* left_range = LookupValueRange(left, left->GetBlock());
+ if (left_range != nullptr) {
+ right_range = left_range->Narrow(right_range);
+ }
+ AssignRange(instruction->GetBlock(), instruction, right_range);
+ return;
+ }
+ }
+
void VisitNewArray(HNewArray* new_array) OVERRIDE {
HInstruction* len = new_array->GetLength();
if (!len->IsIntConstant()) {
diff --git a/compiler/optimizing/bounds_check_elimination_test.cc b/compiler/optimizing/bounds_check_elimination_test.cc
index 575e2fc..2aaf058 100644
--- a/compiler/optimizing/bounds_check_elimination_test.cc
+++ b/compiler/optimizing/bounds_check_elimination_test.cc
@@ -951,4 +951,152 @@
ASSERT_TRUE(IsRemoved(bounds_check6));
}
+// int[] array = new int[10];
+// for (int i=0; i<200; i++) {
+// array[i%10] = 10; // Can eliminate
+// array[i%1] = 10; // Can eliminate
+// array[i%200] = 10; // Cannot eliminate
+// array[i%-10] = 10; // Can eliminate
+// array[i%array.length] = 10; // Can eliminate
+// array[param_i%10] = 10; // Can't eliminate, when param_i < 0
+// }
+TEST_F(BoundsCheckEliminationTest, ModArrayBoundsElimination) {
+ HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(entry);
+ graph_->SetEntryBlock(entry);
+ HInstruction* param_i = new (&allocator_)
+ HParameterValue(graph_->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimInt);
+ entry->AddInstruction(param_i);
+
+ HInstruction* constant_0 = graph_->GetIntConstant(0);
+ HInstruction* constant_1 = graph_->GetIntConstant(1);
+ HInstruction* constant_10 = graph_->GetIntConstant(10);
+ HInstruction* constant_200 = graph_->GetIntConstant(200);
+ HInstruction* constant_minus_10 = graph_->GetIntConstant(-10);
+
+ HBasicBlock* block = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(block);
+ entry->AddSuccessor(block);
+ // We pass a bogus constant for the class to avoid mocking one.
+ HInstruction* new_array = new (&allocator_) HNewArray(constant_10, constant_10, 0);
+ block->AddInstruction(new_array);
+ block->AddInstruction(new (&allocator_) HGoto());
+
+ HBasicBlock* loop_header = new (&allocator_) HBasicBlock(graph_);
+ HBasicBlock* loop_body = new (&allocator_) HBasicBlock(graph_);
+ HBasicBlock* exit = new (&allocator_) HBasicBlock(graph_);
+
+ graph_->AddBlock(loop_header);
+ graph_->AddBlock(loop_body);
+ graph_->AddBlock(exit);
+ block->AddSuccessor(loop_header);
+ loop_header->AddSuccessor(exit); // true successor
+ loop_header->AddSuccessor(loop_body); // false successor
+ loop_body->AddSuccessor(loop_header);
+
+ HPhi* phi = new (&allocator_) HPhi(&allocator_, 0, 0, Primitive::kPrimInt);
+ HInstruction* cmp = new (&allocator_) HGreaterThanOrEqual(phi, constant_200);
+ HInstruction* if_inst = new (&allocator_) HIf(cmp);
+ loop_header->AddPhi(phi);
+ loop_header->AddInstruction(cmp);
+ loop_header->AddInstruction(if_inst);
+ phi->AddInput(constant_0);
+
+ //////////////////////////////////////////////////////////////////////////////////
+ // LOOP BODY:
+ // array[i % 10] = 10;
+ HRem* i_mod_10 = new (&allocator_) HRem(Primitive::kPrimInt, phi, constant_10, 0);
+ HBoundsCheck* bounds_check_i_mod_10 = new (&allocator_) HBoundsCheck(i_mod_10, constant_10, 0);
+ HInstruction* array_set = new (&allocator_) HArraySet(
+ new_array, bounds_check_i_mod_10, constant_10, Primitive::kPrimInt, 0);
+ loop_body->AddInstruction(i_mod_10);
+ loop_body->AddInstruction(bounds_check_i_mod_10);
+ loop_body->AddInstruction(array_set);
+
+ // array[i % 1] = 10;
+ HRem* i_mod_1 = new (&allocator_) HRem(Primitive::kPrimInt, phi, constant_1, 0);
+ HBoundsCheck* bounds_check_i_mod_1 = new (&allocator_) HBoundsCheck(i_mod_1, constant_10, 0);
+ array_set = new (&allocator_) HArraySet(
+ new_array, bounds_check_i_mod_1, constant_10, Primitive::kPrimInt, 0);
+ loop_body->AddInstruction(i_mod_1);
+ loop_body->AddInstruction(bounds_check_i_mod_1);
+ loop_body->AddInstruction(array_set);
+
+ // array[i % 200] = 10;
+ HRem* i_mod_200 = new (&allocator_) HRem(Primitive::kPrimInt, phi, constant_1, 0);
+ HBoundsCheck* bounds_check_i_mod_200 = new (&allocator_) HBoundsCheck(i_mod_200, constant_10, 0);
+ array_set = new (&allocator_) HArraySet(
+ new_array, bounds_check_i_mod_200, constant_10, Primitive::kPrimInt, 0);
+ loop_body->AddInstruction(i_mod_200);
+ loop_body->AddInstruction(bounds_check_i_mod_200);
+ loop_body->AddInstruction(array_set);
+
+ // array[i % -10] = 10;
+ HRem* i_mod_minus_10 = new (&allocator_) HRem(Primitive::kPrimInt, phi, constant_minus_10, 0);
+ HBoundsCheck* bounds_check_i_mod_minus_10 = new (&allocator_) HBoundsCheck(
+ i_mod_minus_10, constant_10, 0);
+ array_set = new (&allocator_) HArraySet(
+ new_array, bounds_check_i_mod_minus_10, constant_10, Primitive::kPrimInt, 0);
+ loop_body->AddInstruction(i_mod_minus_10);
+ loop_body->AddInstruction(bounds_check_i_mod_minus_10);
+ loop_body->AddInstruction(array_set);
+
+ // array[i%array.length] = 10;
+ HNullCheck* null_check = new (&allocator_) HNullCheck(new_array, 0);
+ HArrayLength* array_length = new (&allocator_) HArrayLength(null_check, 0);
+ HRem* i_mod_array_length = new (&allocator_) HRem(Primitive::kPrimInt, phi, array_length, 0);
+ HBoundsCheck* bounds_check_i_mod_array_len = new (&allocator_) HBoundsCheck(
+ i_mod_array_length, array_length, 0);
+ array_set = new (&allocator_) HArraySet(
+ null_check, bounds_check_i_mod_array_len, constant_10, Primitive::kPrimInt, 0);
+ loop_body->AddInstruction(null_check);
+ loop_body->AddInstruction(array_length);
+ loop_body->AddInstruction(i_mod_array_length);
+ loop_body->AddInstruction(bounds_check_i_mod_array_len);
+ loop_body->AddInstruction(array_set);
+
+ // array[param_i % 10] = 10;
+ HRem* param_i_mod_10 = new (&allocator_) HRem(Primitive::kPrimInt, param_i, constant_10, 0);
+ HBoundsCheck* bounds_check_param_i_mod_10 = new (&allocator_) HBoundsCheck(
+ param_i_mod_10, constant_10, 0);
+ array_set = new (&allocator_) HArraySet(
+ new_array, bounds_check_param_i_mod_10, constant_10, Primitive::kPrimInt, 0);
+ loop_body->AddInstruction(param_i_mod_10);
+ loop_body->AddInstruction(bounds_check_param_i_mod_10);
+ loop_body->AddInstruction(array_set);
+
+ // array[param_i%array.length] = 10;
+ null_check = new (&allocator_) HNullCheck(new_array, 0);
+ array_length = new (&allocator_) HArrayLength(null_check, 0);
+ HRem* param_i_mod_array_length = new (&allocator_) HRem(
+ Primitive::kPrimInt, param_i, array_length, 0);
+ HBoundsCheck* bounds_check_param_i_mod_array_len = new (&allocator_) HBoundsCheck(
+ param_i_mod_array_length, array_length, 0);
+ array_set = new (&allocator_) HArraySet(
+ null_check, bounds_check_param_i_mod_array_len, constant_10, Primitive::kPrimInt, 0);
+ loop_body->AddInstruction(null_check);
+ loop_body->AddInstruction(array_length);
+ loop_body->AddInstruction(param_i_mod_array_length);
+ loop_body->AddInstruction(bounds_check_param_i_mod_array_len);
+ loop_body->AddInstruction(array_set);
+
+ // i++;
+ HInstruction* add = new (&allocator_) HAdd(Primitive::kPrimInt, phi, constant_1);
+ loop_body->AddInstruction(add);
+ loop_body->AddInstruction(new (&allocator_) HGoto());
+ phi->AddInput(add);
+ //////////////////////////////////////////////////////////////////////////////////
+
+ exit->AddInstruction(new (&allocator_) HExit());
+
+ RunBCE();
+
+ ASSERT_TRUE(IsRemoved(bounds_check_i_mod_10));
+ ASSERT_TRUE(IsRemoved(bounds_check_i_mod_1));
+ ASSERT_TRUE(IsRemoved(bounds_check_i_mod_200));
+ ASSERT_TRUE(IsRemoved(bounds_check_i_mod_minus_10));
+ ASSERT_TRUE(IsRemoved(bounds_check_i_mod_array_len));
+ ASSERT_FALSE(IsRemoved(bounds_check_param_i_mod_10));
+}
+
} // namespace art
diff --git a/test/449-checker-bce/src/Main.java b/test/449-checker-bce/src/Main.java
index 5103540..f466eea 100644
--- a/test/449-checker-bce/src/Main.java
+++ b/test/449-checker-bce/src/Main.java
@@ -876,6 +876,91 @@
return true;
}
+ /// CHECK-START: void Main.modArrayIndex1(int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArraySet
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArraySet
+
+ /// CHECK-START: void Main.modArrayIndex1(int[]) BCE (after)
+ /// CHECK-NOT: Deoptimize
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArraySet
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK-DAG: ArraySet
+ public static void modArrayIndex1(int[] array) {
+ for(int i = 0; i < 100; i++) {
+ // Cannot statically eliminate, for example, when array.length == 5.
+ // Currently dynamic BCE isn't applied for this case.
+ array[i % 10] = i;
+ // Can be eliminated by BCE.
+ array[i % array.length] = i;
+ }
+ }
+
+ /// CHECK-START: void Main.modArrayIndex2(int[], int) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArraySet
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArraySet
+
+ /// CHECK-START: void Main.modArrayIndex2(int[], int) BCE (after)
+ /// CHECK-NOT: Deoptimize
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArraySet
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArraySet
+ public static void modArrayIndex2(int array[], int index) {
+ for(int i = 0; i < 100; i++) {
+ // Both bounds checks cannot be statically eliminated, because index can be < 0.
+ // Currently dynamic BCE isn't applied for this case.
+ array[(index+i) % 10] = i;
+ array[(index+i) % array.length] = i;
+ }
+ }
+
+ static final int[] staticArray = new int[10];
+
+ /// CHECK-START: void Main.modArrayIndex3() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArraySet
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArraySet
+
+ /// CHECK-START: void Main.modArrayIndex3() BCE (after)
+ /// CHECK-NOT: Deoptimize
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArraySet
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK-DAG: ArraySet
+ public static void modArrayIndex3() {
+ for(int i = 0; i < 100; i++) {
+ // Currently dynamic BCE isn't applied for this case.
+ staticArray[i % 10] = i;
+ // Can be eliminated by BCE.
+ staticArray[i % staticArray.length] = i;
+ }
+ }
+
+ /// CHECK-START: void Main.modArrayIndex4() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArraySet
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArraySet
+
+ /// CHECK-START: void Main.modArrayIndex4() BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK-DAG: ArraySet
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK-DAG: ArraySet
+ public static void modArrayIndex4() {
+ int[] array = new int[20];
+ for(int i = 0; i < 100; i++) {
+ // The local array length is statically know. Both can be eliminated by BCE.
+ array[i % 10] = i;
+ array[i % array.length] = i;
+ }
+ }
/// CHECK-START: void Main.bubbleSort(int[]) GVN (before)
/// CHECK: BoundsCheck