Use induction variable range analysis in BCE (statically).
Rationale: Finally! After lots of very large CLs, now a small CL
that uses the new induction variable analysis in BCE
(statically, using this dynamically with de-opt is TBD).
Despite its relative small size, be aware though,
since the CL introduces a new phase to the compiler.
Change-Id: If5555a173fd5d55d147c63138ef51fc296fa1414
diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index 326a92b..71a55bb 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -249,6 +249,7 @@
compiler/optimizing/graph_test.cc \
compiler/optimizing/gvn_test.cc \
compiler/optimizing/induction_var_analysis_test.cc \
+ compiler/optimizing/induction_var_range_test.cc \
compiler/optimizing/licm_test.cc \
compiler/optimizing/live_interval_test.cc \
compiler/optimizing/nodes_test.cc \
diff --git a/compiler/Android.mk b/compiler/Android.mk
index ce9e367..41e9744 100644
--- a/compiler/Android.mk
+++ b/compiler/Android.mk
@@ -72,6 +72,7 @@
optimizing/graph_visualizer.cc \
optimizing/gvn.cc \
optimizing/induction_var_analysis.cc \
+ optimizing/induction_var_range.cc \
optimizing/inliner.cc \
optimizing/instruction_simplifier.cc \
optimizing/intrinsics.cc \
diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index 70ad408..0d95390 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -16,6 +16,7 @@
#include "base/arena_containers.h"
#include "bounds_check_elimination.h"
+#include "induction_var_range.h"
#include "nodes.h"
namespace art {
@@ -126,14 +127,17 @@
return instruction_ == bound.instruction_ && constant_ == bound.constant_;
}
- static HInstruction* FromArrayLengthToArray(HInstruction* instruction) {
- DCHECK(instruction->IsArrayLength() || instruction->IsNewArray());
- if (instruction->IsArrayLength()) {
- HInstruction* input = instruction->InputAt(0);
- if (input->IsNullCheck()) {
- input = input->AsNullCheck()->InputAt(0);
- }
- return input;
+ /*
+ * Hunt "under the hood" of array lengths (leading to array references),
+ * null checks (also leading to array references), and new arrays
+ * (leading to the actual length). This makes it more likely related
+ * instructions become actually comparable.
+ */
+ static HInstruction* HuntForDeclaration(HInstruction* instruction) {
+ while (instruction->IsArrayLength() ||
+ instruction->IsNullCheck() ||
+ instruction->IsNewArray()) {
+ instruction = instruction->InputAt(0);
}
return instruction;
}
@@ -142,16 +146,11 @@
if (instruction1 == instruction2) {
return true;
}
-
if (instruction1 == nullptr || instruction2 == nullptr) {
return false;
}
-
- // Some bounds are created with HNewArray* as the instruction instead
- // of HArrayLength*. They are treated the same.
- // HArrayLength with the same array input are considered equal also.
- instruction1 = FromArrayLengthToArray(instruction1);
- instruction2 = FromArrayLengthToArray(instruction2);
+ instruction1 = HuntForDeclaration(instruction1);
+ instruction2 = HuntForDeclaration(instruction2);
return instruction1 == instruction2;
}
@@ -1108,9 +1107,12 @@
return block->GetBlockId() >= initial_block_size_;
}
- explicit BCEVisitor(HGraph* graph)
- : HGraphVisitor(graph), maps_(graph->GetBlocks().Size()),
- need_to_revisit_block_(false), initial_block_size_(graph->GetBlocks().Size()) {}
+ BCEVisitor(HGraph* graph, HInductionVarAnalysis* induction_analysis)
+ : HGraphVisitor(graph),
+ maps_(graph->GetBlocks().Size()),
+ need_to_revisit_block_(false),
+ initial_block_size_(graph->GetBlocks().Size()),
+ induction_range_(induction_analysis) {}
void VisitBasicBlock(HBasicBlock* block) OVERRIDE {
DCHECK(!IsAddedBlock(block));
@@ -1159,6 +1161,23 @@
return nullptr;
}
+ // Return the range resulting from induction variable analysis of "instruction" when the value
+ // is used from "context", for example, an index used from a bounds-check inside a loop body.
+ ValueRange* LookupInductionRange(HInstruction* context, HInstruction* instruction) {
+ InductionVarRange::Value v1 = induction_range_.GetMinInduction(context, instruction);
+ InductionVarRange::Value v2 = induction_range_.GetMaxInduction(context, instruction);
+ if ((v1.a_constant == 0 || v1.a_constant == 1) && v1.b_constant != INT_MIN &&
+ (v2.a_constant == 0 || v2.a_constant == 1) && v2.b_constant != INT_MAX) {
+ DCHECK(v1.a_constant == 1 || v1.instruction == nullptr);
+ DCHECK(v2.a_constant == 1 || v2.instruction == nullptr);
+ ValueBound low = ValueBound(v1.instruction, v1.b_constant);
+ ValueBound up = ValueBound(v2.instruction, v2.b_constant);
+ return new (GetGraph()->GetArena()) ValueRange(GetGraph()->GetArena(), low, up);
+ }
+ // Didn't find anything useful.
+ return nullptr;
+ }
+
// 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,
@@ -1390,16 +1409,20 @@
}
if (!index->IsIntConstant()) {
+ ValueBound lower = ValueBound(nullptr, 0); // constant 0
+ ValueBound upper = ValueBound(array_length, -1); // array_length - 1
+ ValueRange array_range(GetGraph()->GetArena(), lower, upper);
+ // Try range obtained by local analysis.
ValueRange* index_range = LookupValueRange(index, block);
- if (index_range != nullptr) {
- ValueBound lower = ValueBound(nullptr, 0); // constant 0
- ValueBound upper = ValueBound(array_length, -1); // array_length - 1
- ValueRange* array_range = new (GetGraph()->GetArena())
- ValueRange(GetGraph()->GetArena(), lower, upper);
- if (index_range->FitsIn(array_range)) {
- ReplaceBoundsCheck(bounds_check, index);
- return;
- }
+ if (index_range != nullptr && index_range->FitsIn(&array_range)) {
+ ReplaceBoundsCheck(bounds_check, index);
+ return;
+ }
+ // Try range obtained by induction variable analysis.
+ index_range = LookupInductionRange(bounds_check, index);
+ if (index_range != nullptr && index_range->FitsIn(&array_range)) {
+ ReplaceBoundsCheck(bounds_check, index);
+ return;
}
} else {
int32_t constant = index->AsIntConstant()->GetValue();
@@ -1831,6 +1854,9 @@
// Initial number of blocks.
int32_t initial_block_size_;
+ // Range analysis based on induction variables.
+ InductionVarRange induction_range_;
+
DISALLOW_COPY_AND_ASSIGN(BCEVisitor);
};
@@ -1839,7 +1865,7 @@
return;
}
- BCEVisitor visitor(graph_);
+ BCEVisitor visitor(graph_, induction_analysis_);
// Reverse post order guarantees a node's dominators are visited first.
// We want to visit in the dominator-based order since if a value is known to
// be bounded by a range at one instruction, it must be true that all uses of
diff --git a/compiler/optimizing/bounds_check_elimination.h b/compiler/optimizing/bounds_check_elimination.h
index 24b8ea7..cdff3ca 100644
--- a/compiler/optimizing/bounds_check_elimination.h
+++ b/compiler/optimizing/bounds_check_elimination.h
@@ -21,16 +21,21 @@
namespace art {
+class HInductionVarAnalysis;
+
class BoundsCheckElimination : public HOptimization {
public:
- explicit BoundsCheckElimination(HGraph* graph)
- : HOptimization(graph, kBoundsCheckEliminiationPassName) {}
+ BoundsCheckElimination(HGraph* graph, HInductionVarAnalysis* induction_analysis)
+ : HOptimization(graph, kBoundsCheckEliminiationPassName),
+ induction_analysis_(induction_analysis) {}
void Run() OVERRIDE;
static constexpr const char* kBoundsCheckEliminiationPassName = "BCE";
private:
+ HInductionVarAnalysis* induction_analysis_;
+
DISALLOW_COPY_AND_ASSIGN(BoundsCheckElimination);
};
diff --git a/compiler/optimizing/bounds_check_elimination_test.cc b/compiler/optimizing/bounds_check_elimination_test.cc
index 4701bdd..08e1e36 100644
--- a/compiler/optimizing/bounds_check_elimination_test.cc
+++ b/compiler/optimizing/bounds_check_elimination_test.cc
@@ -18,6 +18,7 @@
#include "bounds_check_elimination.h"
#include "builder.h"
#include "gvn.h"
+#include "induction_var_analysis.h"
#include "instruction_simplifier.h"
#include "nodes.h"
#include "optimizing_unit_test.h"
@@ -27,101 +28,122 @@
namespace art {
-static void RunSimplifierAndGvn(HGraph* graph) {
- InstructionSimplifier simplify(graph);
- simplify.Run();
- SideEffectsAnalysis side_effects(graph);
- side_effects.Run();
- GVNOptimization(graph, side_effects).Run();
-}
+/**
+ * Fixture class for the BoundsCheckElimination tests.
+ */
+class BoundsCheckEliminationTest : public testing::Test {
+ public:
+ BoundsCheckEliminationTest() : pool_(), allocator_(&pool_) {
+ graph_ = CreateGraph(&allocator_);
+ graph_->SetHasBoundsChecks(true);
+ }
+
+ ~BoundsCheckEliminationTest() { }
+
+ void RunBCE() {
+ graph_->BuildDominatorTree();
+ graph_->AnalyzeNaturalLoops();
+
+ InstructionSimplifier(graph_).Run();
+
+ SideEffectsAnalysis side_effects(graph_);
+ side_effects.Run();
+
+ GVNOptimization(graph_, side_effects).Run();
+
+ HInductionVarAnalysis induction(graph_);
+ induction.Run();
+
+ BoundsCheckElimination(graph_, &induction).Run();
+ }
+
+ ArenaPool pool_;
+ ArenaAllocator allocator_;
+ HGraph* graph_;
+};
+
// if (i < 0) { array[i] = 1; // Can't eliminate. }
// else if (i >= array.length) { array[i] = 1; // Can't eliminate. }
// else { array[i] = 1; // Can eliminate. }
-TEST(BoundsCheckEliminationTest, NarrowingRangeArrayBoundsElimination) {
- ArenaPool pool;
- ArenaAllocator allocator(&pool);
-
- HGraph* graph = CreateGraph(&allocator);
- graph->SetHasBoundsChecks(true);
-
- HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
- graph->AddBlock(entry);
- graph->SetEntryBlock(entry);
- HInstruction* parameter1 = new (&allocator)
+TEST_F(BoundsCheckEliminationTest, NarrowingRangeArrayBoundsElimination) {
+ HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(entry);
+ graph_->SetEntryBlock(entry);
+ HInstruction* parameter1 = new (&allocator_)
HParameterValue(0, Primitive::kPrimNot); // array
- HInstruction* parameter2 = new (&allocator)
+ HInstruction* parameter2 = new (&allocator_)
HParameterValue(0, Primitive::kPrimInt); // i
entry->AddInstruction(parameter1);
entry->AddInstruction(parameter2);
- HInstruction* constant_1 = graph->GetIntConstant(1);
- HInstruction* constant_0 = graph->GetIntConstant(0);
+ HInstruction* constant_1 = graph_->GetIntConstant(1);
+ HInstruction* constant_0 = graph_->GetIntConstant(0);
- HBasicBlock* block1 = new (&allocator) HBasicBlock(graph);
- graph->AddBlock(block1);
- HInstruction* cmp = new (&allocator) HGreaterThanOrEqual(parameter2, constant_0);
- HIf* if_inst = new (&allocator) HIf(cmp);
+ HBasicBlock* block1 = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(block1);
+ HInstruction* cmp = new (&allocator_) HGreaterThanOrEqual(parameter2, constant_0);
+ HIf* if_inst = new (&allocator_) HIf(cmp);
block1->AddInstruction(cmp);
block1->AddInstruction(if_inst);
entry->AddSuccessor(block1);
- HBasicBlock* block2 = new (&allocator) HBasicBlock(graph);
- graph->AddBlock(block2);
- HNullCheck* null_check = new (&allocator) HNullCheck(parameter1, 0);
- HArrayLength* array_length = new (&allocator) HArrayLength(null_check);
- HBoundsCheck* bounds_check2 = new (&allocator)
+ HBasicBlock* block2 = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(block2);
+ HNullCheck* null_check = new (&allocator_) HNullCheck(parameter1, 0);
+ HArrayLength* array_length = new (&allocator_) HArrayLength(null_check);
+ HBoundsCheck* bounds_check2 = new (&allocator_)
HBoundsCheck(parameter2, array_length, 0);
- HArraySet* array_set = new (&allocator) HArraySet(
+ HArraySet* array_set = new (&allocator_) HArraySet(
null_check, bounds_check2, constant_1, Primitive::kPrimInt, 0);
block2->AddInstruction(null_check);
block2->AddInstruction(array_length);
block2->AddInstruction(bounds_check2);
block2->AddInstruction(array_set);
- HBasicBlock* block3 = new (&allocator) HBasicBlock(graph);
- graph->AddBlock(block3);
- null_check = new (&allocator) HNullCheck(parameter1, 0);
- array_length = new (&allocator) HArrayLength(null_check);
- cmp = new (&allocator) HLessThan(parameter2, array_length);
- if_inst = new (&allocator) HIf(cmp);
+ HBasicBlock* block3 = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(block3);
+ null_check = new (&allocator_) HNullCheck(parameter1, 0);
+ array_length = new (&allocator_) HArrayLength(null_check);
+ cmp = new (&allocator_) HLessThan(parameter2, array_length);
+ if_inst = new (&allocator_) HIf(cmp);
block3->AddInstruction(null_check);
block3->AddInstruction(array_length);
block3->AddInstruction(cmp);
block3->AddInstruction(if_inst);
- HBasicBlock* block4 = new (&allocator) HBasicBlock(graph);
- graph->AddBlock(block4);
- null_check = new (&allocator) HNullCheck(parameter1, 0);
- array_length = new (&allocator) HArrayLength(null_check);
- HBoundsCheck* bounds_check4 = new (&allocator)
+ HBasicBlock* block4 = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(block4);
+ null_check = new (&allocator_) HNullCheck(parameter1, 0);
+ array_length = new (&allocator_) HArrayLength(null_check);
+ HBoundsCheck* bounds_check4 = new (&allocator_)
HBoundsCheck(parameter2, array_length, 0);
- array_set = new (&allocator) HArraySet(
+ array_set = new (&allocator_) HArraySet(
null_check, bounds_check4, constant_1, Primitive::kPrimInt, 0);
block4->AddInstruction(null_check);
block4->AddInstruction(array_length);
block4->AddInstruction(bounds_check4);
block4->AddInstruction(array_set);
- HBasicBlock* block5 = new (&allocator) HBasicBlock(graph);
- graph->AddBlock(block5);
- null_check = new (&allocator) HNullCheck(parameter1, 0);
- array_length = new (&allocator) HArrayLength(null_check);
- HBoundsCheck* bounds_check5 = new (&allocator)
+ HBasicBlock* block5 = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(block5);
+ null_check = new (&allocator_) HNullCheck(parameter1, 0);
+ array_length = new (&allocator_) HArrayLength(null_check);
+ HBoundsCheck* bounds_check5 = new (&allocator_)
HBoundsCheck(parameter2, array_length, 0);
- array_set = new (&allocator) HArraySet(
+ array_set = new (&allocator_) HArraySet(
null_check, bounds_check5, constant_1, Primitive::kPrimInt, 0);
block5->AddInstruction(null_check);
block5->AddInstruction(array_length);
block5->AddInstruction(bounds_check5);
block5->AddInstruction(array_set);
- HBasicBlock* exit = new (&allocator) HBasicBlock(graph);
- graph->AddBlock(exit);
+ HBasicBlock* exit = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(exit);
block2->AddSuccessor(exit);
block4->AddSuccessor(exit);
block5->AddSuccessor(exit);
- exit->AddInstruction(new (&allocator) HExit());
+ exit->AddInstruction(new (&allocator_) HExit());
block1->AddSuccessor(block3); // True successor
block1->AddSuccessor(block2); // False successor
@@ -129,10 +151,8 @@
block3->AddSuccessor(block5); // True successor
block3->AddSuccessor(block4); // False successor
- graph->BuildDominatorTree();
- RunSimplifierAndGvn(graph);
- BoundsCheckElimination bounds_check_elimination(graph);
- bounds_check_elimination.Run();
+ RunBCE();
+
ASSERT_FALSE(IsRemoved(bounds_check2));
ASSERT_FALSE(IsRemoved(bounds_check4));
ASSERT_TRUE(IsRemoved(bounds_check5));
@@ -143,230 +163,203 @@
// int j = i + Integer.MAX_VALUE;
// if (j < array.length) array[j] = 1; // Can't eliminate.
// }
-TEST(BoundsCheckEliminationTest, OverflowArrayBoundsElimination) {
- ArenaPool pool;
- ArenaAllocator allocator(&pool);
-
- HGraph* graph = CreateGraph(&allocator);
- graph->SetHasBoundsChecks(true);
-
- HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
- graph->AddBlock(entry);
- graph->SetEntryBlock(entry);
- HInstruction* parameter1 = new (&allocator)
+TEST_F(BoundsCheckEliminationTest, OverflowArrayBoundsElimination) {
+ HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(entry);
+ graph_->SetEntryBlock(entry);
+ HInstruction* parameter1 = new (&allocator_)
HParameterValue(0, Primitive::kPrimNot); // array
- HInstruction* parameter2 = new (&allocator)
+ HInstruction* parameter2 = new (&allocator_)
HParameterValue(0, Primitive::kPrimInt); // i
entry->AddInstruction(parameter1);
entry->AddInstruction(parameter2);
- HInstruction* constant_1 = graph->GetIntConstant(1);
- HInstruction* constant_0 = graph->GetIntConstant(0);
- HInstruction* constant_max_int = graph->GetIntConstant(INT_MAX);
+ HInstruction* constant_1 = graph_->GetIntConstant(1);
+ HInstruction* constant_0 = graph_->GetIntConstant(0);
+ HInstruction* constant_max_int = graph_->GetIntConstant(INT_MAX);
- HBasicBlock* block1 = new (&allocator) HBasicBlock(graph);
- graph->AddBlock(block1);
- HInstruction* cmp = new (&allocator) HLessThanOrEqual(parameter2, constant_0);
- HIf* if_inst = new (&allocator) HIf(cmp);
+ HBasicBlock* block1 = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(block1);
+ HInstruction* cmp = new (&allocator_) HLessThanOrEqual(parameter2, constant_0);
+ HIf* if_inst = new (&allocator_) HIf(cmp);
block1->AddInstruction(cmp);
block1->AddInstruction(if_inst);
entry->AddSuccessor(block1);
- HBasicBlock* block2 = new (&allocator) HBasicBlock(graph);
- graph->AddBlock(block2);
- HInstruction* add = new (&allocator) HAdd(Primitive::kPrimInt, parameter2, constant_max_int);
- HNullCheck* null_check = new (&allocator) HNullCheck(parameter1, 0);
- HArrayLength* array_length = new (&allocator) HArrayLength(null_check);
- HInstruction* cmp2 = new (&allocator) HGreaterThanOrEqual(add, array_length);
- if_inst = new (&allocator) HIf(cmp2);
+ HBasicBlock* block2 = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(block2);
+ HInstruction* add = new (&allocator_) HAdd(Primitive::kPrimInt, parameter2, constant_max_int);
+ HNullCheck* null_check = new (&allocator_) HNullCheck(parameter1, 0);
+ HArrayLength* array_length = new (&allocator_) HArrayLength(null_check);
+ HInstruction* cmp2 = new (&allocator_) HGreaterThanOrEqual(add, array_length);
+ if_inst = new (&allocator_) HIf(cmp2);
block2->AddInstruction(add);
block2->AddInstruction(null_check);
block2->AddInstruction(array_length);
block2->AddInstruction(cmp2);
block2->AddInstruction(if_inst);
- HBasicBlock* block3 = new (&allocator) HBasicBlock(graph);
- graph->AddBlock(block3);
- HBoundsCheck* bounds_check = new (&allocator)
+ HBasicBlock* block3 = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(block3);
+ HBoundsCheck* bounds_check = new (&allocator_)
HBoundsCheck(add, array_length, 0);
- HArraySet* array_set = new (&allocator) HArraySet(
+ HArraySet* array_set = new (&allocator_) HArraySet(
null_check, bounds_check, constant_1, Primitive::kPrimInt, 0);
block3->AddInstruction(bounds_check);
block3->AddInstruction(array_set);
- HBasicBlock* exit = new (&allocator) HBasicBlock(graph);
- graph->AddBlock(exit);
- exit->AddInstruction(new (&allocator) HExit());
+ HBasicBlock* exit = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(exit);
+ exit->AddInstruction(new (&allocator_) HExit());
block1->AddSuccessor(exit); // true successor
block1->AddSuccessor(block2); // false successor
block2->AddSuccessor(exit); // true successor
block2->AddSuccessor(block3); // false successor
block3->AddSuccessor(exit);
- graph->BuildDominatorTree();
- RunSimplifierAndGvn(graph);
- BoundsCheckElimination bounds_check_elimination(graph);
- bounds_check_elimination.Run();
+ RunBCE();
+
ASSERT_FALSE(IsRemoved(bounds_check));
}
// if (i < array.length) {
// int j = i - Integer.MAX_VALUE;
-// j = j - Integer.MAX_VALUE; // j is (i+2) after substracting MAX_INT twice
+// j = j - Integer.MAX_VALUE; // j is (i+2) after subtracting MAX_INT twice
// if (j > 0) array[j] = 1; // Can't eliminate.
// }
-TEST(BoundsCheckEliminationTest, UnderflowArrayBoundsElimination) {
- ArenaPool pool;
- ArenaAllocator allocator(&pool);
-
- HGraph* graph = CreateGraph(&allocator);
- graph->SetHasBoundsChecks(true);
-
- HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
- graph->AddBlock(entry);
- graph->SetEntryBlock(entry);
- HInstruction* parameter1 = new (&allocator)
+TEST_F(BoundsCheckEliminationTest, UnderflowArrayBoundsElimination) {
+ HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(entry);
+ graph_->SetEntryBlock(entry);
+ HInstruction* parameter1 = new (&allocator_)
HParameterValue(0, Primitive::kPrimNot); // array
- HInstruction* parameter2 = new (&allocator)
+ HInstruction* parameter2 = new (&allocator_)
HParameterValue(0, Primitive::kPrimInt); // i
entry->AddInstruction(parameter1);
entry->AddInstruction(parameter2);
- HInstruction* constant_1 = graph->GetIntConstant(1);
- HInstruction* constant_0 = graph->GetIntConstant(0);
- HInstruction* constant_max_int = graph->GetIntConstant(INT_MAX);
+ HInstruction* constant_1 = graph_->GetIntConstant(1);
+ HInstruction* constant_0 = graph_->GetIntConstant(0);
+ HInstruction* constant_max_int = graph_->GetIntConstant(INT_MAX);
- HBasicBlock* block1 = new (&allocator) HBasicBlock(graph);
- graph->AddBlock(block1);
- HNullCheck* null_check = new (&allocator) HNullCheck(parameter1, 0);
- HArrayLength* array_length = new (&allocator) HArrayLength(null_check);
- HInstruction* cmp = new (&allocator) HGreaterThanOrEqual(parameter2, array_length);
- HIf* if_inst = new (&allocator) HIf(cmp);
+ HBasicBlock* block1 = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(block1);
+ HNullCheck* null_check = new (&allocator_) HNullCheck(parameter1, 0);
+ HArrayLength* array_length = new (&allocator_) HArrayLength(null_check);
+ HInstruction* cmp = new (&allocator_) HGreaterThanOrEqual(parameter2, array_length);
+ HIf* if_inst = new (&allocator_) HIf(cmp);
block1->AddInstruction(null_check);
block1->AddInstruction(array_length);
block1->AddInstruction(cmp);
block1->AddInstruction(if_inst);
entry->AddSuccessor(block1);
- HBasicBlock* block2 = new (&allocator) HBasicBlock(graph);
- graph->AddBlock(block2);
- HInstruction* sub1 = new (&allocator) HSub(Primitive::kPrimInt, parameter2, constant_max_int);
- HInstruction* sub2 = new (&allocator) HSub(Primitive::kPrimInt, sub1, constant_max_int);
- HInstruction* cmp2 = new (&allocator) HLessThanOrEqual(sub2, constant_0);
- if_inst = new (&allocator) HIf(cmp2);
+ HBasicBlock* block2 = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(block2);
+ HInstruction* sub1 = new (&allocator_) HSub(Primitive::kPrimInt, parameter2, constant_max_int);
+ HInstruction* sub2 = new (&allocator_) HSub(Primitive::kPrimInt, sub1, constant_max_int);
+ HInstruction* cmp2 = new (&allocator_) HLessThanOrEqual(sub2, constant_0);
+ if_inst = new (&allocator_) HIf(cmp2);
block2->AddInstruction(sub1);
block2->AddInstruction(sub2);
block2->AddInstruction(cmp2);
block2->AddInstruction(if_inst);
- HBasicBlock* block3 = new (&allocator) HBasicBlock(graph);
- graph->AddBlock(block3);
- HBoundsCheck* bounds_check = new (&allocator)
+ HBasicBlock* block3 = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(block3);
+ HBoundsCheck* bounds_check = new (&allocator_)
HBoundsCheck(sub2, array_length, 0);
- HArraySet* array_set = new (&allocator) HArraySet(
+ HArraySet* array_set = new (&allocator_) HArraySet(
null_check, bounds_check, constant_1, Primitive::kPrimInt, 0);
block3->AddInstruction(bounds_check);
block3->AddInstruction(array_set);
- HBasicBlock* exit = new (&allocator) HBasicBlock(graph);
- graph->AddBlock(exit);
- exit->AddInstruction(new (&allocator) HExit());
+ HBasicBlock* exit = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(exit);
+ exit->AddInstruction(new (&allocator_) HExit());
block1->AddSuccessor(exit); // true successor
block1->AddSuccessor(block2); // false successor
block2->AddSuccessor(exit); // true successor
block2->AddSuccessor(block3); // false successor
block3->AddSuccessor(exit);
- graph->BuildDominatorTree();
- RunSimplifierAndGvn(graph);
- BoundsCheckElimination bounds_check_elimination(graph);
- bounds_check_elimination.Run();
+ RunBCE();
+
ASSERT_FALSE(IsRemoved(bounds_check));
}
// array[6] = 1; // Can't eliminate.
// array[5] = 1; // Can eliminate.
// array[4] = 1; // Can eliminate.
-TEST(BoundsCheckEliminationTest, ConstantArrayBoundsElimination) {
- ArenaPool pool;
- ArenaAllocator allocator(&pool);
-
- HGraph* graph = CreateGraph(&allocator);
- graph->SetHasBoundsChecks(true);
-
- HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
- graph->AddBlock(entry);
- graph->SetEntryBlock(entry);
- HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimNot);
+TEST_F(BoundsCheckEliminationTest, ConstantArrayBoundsElimination) {
+ HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(entry);
+ graph_->SetEntryBlock(entry);
+ HInstruction* parameter = new (&allocator_) HParameterValue(0, Primitive::kPrimNot);
entry->AddInstruction(parameter);
- HInstruction* constant_5 = graph->GetIntConstant(5);
- HInstruction* constant_4 = graph->GetIntConstant(4);
- HInstruction* constant_6 = graph->GetIntConstant(6);
- HInstruction* constant_1 = graph->GetIntConstant(1);
+ HInstruction* constant_5 = graph_->GetIntConstant(5);
+ HInstruction* constant_4 = graph_->GetIntConstant(4);
+ HInstruction* constant_6 = graph_->GetIntConstant(6);
+ HInstruction* constant_1 = graph_->GetIntConstant(1);
- HBasicBlock* block = new (&allocator) HBasicBlock(graph);
- graph->AddBlock(block);
+ HBasicBlock* block = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(block);
entry->AddSuccessor(block);
- HNullCheck* null_check = new (&allocator) HNullCheck(parameter, 0);
- HArrayLength* array_length = new (&allocator) HArrayLength(null_check);
- HBoundsCheck* bounds_check6 = new (&allocator)
+ HNullCheck* null_check = new (&allocator_) HNullCheck(parameter, 0);
+ HArrayLength* array_length = new (&allocator_) HArrayLength(null_check);
+ HBoundsCheck* bounds_check6 = new (&allocator_)
HBoundsCheck(constant_6, array_length, 0);
- HInstruction* array_set = new (&allocator) HArraySet(
+ HInstruction* array_set = new (&allocator_) HArraySet(
null_check, bounds_check6, constant_1, Primitive::kPrimInt, 0);
block->AddInstruction(null_check);
block->AddInstruction(array_length);
block->AddInstruction(bounds_check6);
block->AddInstruction(array_set);
- null_check = new (&allocator) HNullCheck(parameter, 0);
- array_length = new (&allocator) HArrayLength(null_check);
- HBoundsCheck* bounds_check5 = new (&allocator)
+ null_check = new (&allocator_) HNullCheck(parameter, 0);
+ array_length = new (&allocator_) HArrayLength(null_check);
+ HBoundsCheck* bounds_check5 = new (&allocator_)
HBoundsCheck(constant_5, array_length, 0);
- array_set = new (&allocator) HArraySet(
+ array_set = new (&allocator_) HArraySet(
null_check, bounds_check5, constant_1, Primitive::kPrimInt, 0);
block->AddInstruction(null_check);
block->AddInstruction(array_length);
block->AddInstruction(bounds_check5);
block->AddInstruction(array_set);
- null_check = new (&allocator) HNullCheck(parameter, 0);
- array_length = new (&allocator) HArrayLength(null_check);
- HBoundsCheck* bounds_check4 = new (&allocator)
+ null_check = new (&allocator_) HNullCheck(parameter, 0);
+ array_length = new (&allocator_) HArrayLength(null_check);
+ HBoundsCheck* bounds_check4 = new (&allocator_)
HBoundsCheck(constant_4, array_length, 0);
- array_set = new (&allocator) HArraySet(
+ array_set = new (&allocator_) HArraySet(
null_check, bounds_check4, constant_1, Primitive::kPrimInt, 0);
block->AddInstruction(null_check);
block->AddInstruction(array_length);
block->AddInstruction(bounds_check4);
block->AddInstruction(array_set);
- block->AddInstruction(new (&allocator) HGoto());
+ block->AddInstruction(new (&allocator_) HGoto());
- HBasicBlock* exit = new (&allocator) HBasicBlock(graph);
- graph->AddBlock(exit);
+ HBasicBlock* exit = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(exit);
block->AddSuccessor(exit);
- exit->AddInstruction(new (&allocator) HExit());
+ exit->AddInstruction(new (&allocator_) HExit());
- graph->BuildDominatorTree();
- RunSimplifierAndGvn(graph);
- BoundsCheckElimination bounds_check_elimination(graph);
- bounds_check_elimination.Run();
+ RunBCE();
+
ASSERT_FALSE(IsRemoved(bounds_check6));
ASSERT_TRUE(IsRemoved(bounds_check5));
ASSERT_TRUE(IsRemoved(bounds_check4));
}
// for (int i=initial; i<array.length; i+=increment) { array[i] = 10; }
-static HGraph* BuildSSAGraph1(ArenaAllocator* allocator,
- HInstruction** bounds_check,
- int initial,
- int increment,
- IfCondition cond = kCondGE) {
- HGraph* graph = CreateGraph(allocator);
- graph->SetHasBoundsChecks(true);
-
+static HInstruction* BuildSSAGraph1(HGraph* graph,
+ ArenaAllocator* allocator,
+ int initial,
+ int increment,
+ IfCondition cond = kCondGE) {
HBasicBlock* entry = new (allocator) HBasicBlock(graph);
graph->AddBlock(entry);
graph->SetEntryBlock(entry);
@@ -414,14 +407,14 @@
null_check = new (allocator) HNullCheck(parameter, 0);
array_length = new (allocator) HArrayLength(null_check);
- *bounds_check = new (allocator) HBoundsCheck(phi, array_length, 0);
+ HInstruction* bounds_check = new (allocator) HBoundsCheck(phi, array_length, 0);
HInstruction* array_set = new (allocator) HArraySet(
- null_check, *bounds_check, constant_10, Primitive::kPrimInt, 0);
+ null_check, bounds_check, constant_10, Primitive::kPrimInt, 0);
HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_increment);
loop_body->AddInstruction(null_check);
loop_body->AddInstruction(array_length);
- loop_body->AddInstruction(*bounds_check);
+ loop_body->AddInstruction(bounds_check);
loop_body->AddInstruction(array_set);
loop_body->AddInstruction(add);
loop_body->AddInstruction(new (allocator) HGoto());
@@ -429,79 +422,58 @@
exit->AddInstruction(new (allocator) HExit());
- return graph;
+ return bounds_check;
}
-TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination1) {
- ArenaPool pool;
- ArenaAllocator allocator(&pool);
-
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1a) {
// for (int i=0; i<array.length; i++) { array[i] = 10; // Can eliminate with gvn. }
- HInstruction* bounds_check = nullptr;
- HGraph* graph = BuildSSAGraph1(&allocator, &bounds_check, 0, 1);
- graph->BuildDominatorTree();
- graph->AnalyzeNaturalLoops();
- RunSimplifierAndGvn(graph);
- BoundsCheckElimination bounds_check_elimination(graph);
- bounds_check_elimination.Run();
+ HInstruction* bounds_check = BuildSSAGraph1(graph_, &allocator_, 0, 1);
+ RunBCE();
ASSERT_TRUE(IsRemoved(bounds_check));
+}
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1b) {
// for (int i=1; i<array.length; i++) { array[i] = 10; // Can eliminate. }
- graph = BuildSSAGraph1(&allocator, &bounds_check, 1, 1);
- graph->BuildDominatorTree();
- graph->AnalyzeNaturalLoops();
- RunSimplifierAndGvn(graph);
- BoundsCheckElimination bounds_check_elimination_with_initial_1(graph);
- bounds_check_elimination_with_initial_1.Run();
+ HInstruction* bounds_check = BuildSSAGraph1(graph_, &allocator_, 1, 1);
+ RunBCE();
ASSERT_TRUE(IsRemoved(bounds_check));
+}
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1c) {
// for (int i=-1; i<array.length; i++) { array[i] = 10; // Can't eliminate. }
- graph = BuildSSAGraph1(&allocator, &bounds_check, -1, 1);
- graph->BuildDominatorTree();
- graph->AnalyzeNaturalLoops();
- RunSimplifierAndGvn(graph);
- BoundsCheckElimination bounds_check_elimination_with_initial_minus_1(graph);
- bounds_check_elimination_with_initial_minus_1.Run();
+ HInstruction* bounds_check = BuildSSAGraph1(graph_, &allocator_, -1, 1);
+ RunBCE();
ASSERT_FALSE(IsRemoved(bounds_check));
+}
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1d) {
// for (int i=0; i<=array.length; i++) { array[i] = 10; // Can't eliminate. }
- graph = BuildSSAGraph1(&allocator, &bounds_check, 0, 1, kCondGT);
- graph->BuildDominatorTree();
- graph->AnalyzeNaturalLoops();
- RunSimplifierAndGvn(graph);
- BoundsCheckElimination bounds_check_elimination_with_greater_than(graph);
- bounds_check_elimination_with_greater_than.Run();
+ HInstruction* bounds_check = BuildSSAGraph1(graph_, &allocator_, 0, 1, kCondGT);
+ RunBCE();
ASSERT_FALSE(IsRemoved(bounds_check));
+}
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1e) {
// for (int i=0; i<array.length; i += 2) {
// array[i] = 10; // Can't eliminate due to overflow concern. }
- graph = BuildSSAGraph1(&allocator, &bounds_check, 0, 2);
- graph->BuildDominatorTree();
- graph->AnalyzeNaturalLoops();
- RunSimplifierAndGvn(graph);
- BoundsCheckElimination bounds_check_elimination_with_increment_2(graph);
- bounds_check_elimination_with_increment_2.Run();
+ HInstruction* bounds_check = BuildSSAGraph1(graph_, &allocator_, 0, 2);
+ RunBCE();
ASSERT_FALSE(IsRemoved(bounds_check));
+}
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination1f) {
// for (int i=1; i<array.length; i += 2) { array[i] = 10; // Can eliminate. }
- graph = BuildSSAGraph1(&allocator, &bounds_check, 1, 2);
- graph->BuildDominatorTree();
- graph->AnalyzeNaturalLoops();
- RunSimplifierAndGvn(graph);
- BoundsCheckElimination bounds_check_elimination_with_increment_2_from_1(graph);
- bounds_check_elimination_with_increment_2_from_1.Run();
+ HInstruction* bounds_check = BuildSSAGraph1(graph_, &allocator_, 1, 2);
+ RunBCE();
ASSERT_TRUE(IsRemoved(bounds_check));
}
// for (int i=array.length; i>0; i+=increment) { array[i-1] = 10; }
-static HGraph* BuildSSAGraph2(ArenaAllocator* allocator,
- HInstruction** bounds_check,
- int initial,
- int increment = -1,
- IfCondition cond = kCondLE) {
- HGraph* graph = CreateGraph(allocator);
- graph->SetHasBoundsChecks(true);
-
+static HInstruction* BuildSSAGraph2(HGraph *graph,
+ ArenaAllocator* allocator,
+ int initial,
+ int increment = -1,
+ IfCondition cond = kCondLE) {
HBasicBlock* entry = new (allocator) HBasicBlock(graph);
graph->AddBlock(entry);
graph->SetEntryBlock(entry);
@@ -551,14 +523,14 @@
HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_minus_1);
null_check = new (allocator) HNullCheck(parameter, 0);
array_length = new (allocator) HArrayLength(null_check);
- *bounds_check = new (allocator) HBoundsCheck(add, array_length, 0);
+ HInstruction* bounds_check = new (allocator) HBoundsCheck(add, array_length, 0);
HInstruction* array_set = new (allocator) HArraySet(
- null_check, *bounds_check, constant_10, Primitive::kPrimInt, 0);
+ null_check, bounds_check, constant_10, Primitive::kPrimInt, 0);
HInstruction* add_phi = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_increment);
loop_body->AddInstruction(add);
loop_body->AddInstruction(null_check);
loop_body->AddInstruction(array_length);
- loop_body->AddInstruction(*bounds_check);
+ loop_body->AddInstruction(bounds_check);
loop_body->AddInstruction(array_set);
loop_body->AddInstruction(add_phi);
loop_body->AddInstruction(new (allocator) HGoto());
@@ -566,70 +538,51 @@
exit->AddInstruction(new (allocator) HExit());
- return graph;
+ return bounds_check;
}
-TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination2) {
- ArenaPool pool;
- ArenaAllocator allocator(&pool);
-
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2a) {
// for (int i=array.length; i>0; i--) { array[i-1] = 10; // Can eliminate with gvn. }
- HInstruction* bounds_check = nullptr;
- HGraph* graph = BuildSSAGraph2(&allocator, &bounds_check, 0);
- graph->BuildDominatorTree();
- graph->AnalyzeNaturalLoops();
- RunSimplifierAndGvn(graph);
- BoundsCheckElimination bounds_check_elimination(graph);
- bounds_check_elimination.Run();
+ HInstruction* bounds_check = BuildSSAGraph2(graph_, &allocator_, 0);
+ RunBCE();
ASSERT_TRUE(IsRemoved(bounds_check));
+}
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2b) {
// for (int i=array.length; i>1; i--) { array[i-1] = 10; // Can eliminate. }
- graph = BuildSSAGraph2(&allocator, &bounds_check, 1);
- graph->BuildDominatorTree();
- graph->AnalyzeNaturalLoops();
- RunSimplifierAndGvn(graph);
- BoundsCheckElimination bounds_check_elimination_with_initial_1(graph);
- bounds_check_elimination_with_initial_1.Run();
+ HInstruction* bounds_check = BuildSSAGraph2(graph_, &allocator_, 1);
+ RunBCE();
ASSERT_TRUE(IsRemoved(bounds_check));
+}
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2c) {
// for (int i=array.length; i>-1; i--) { array[i-1] = 10; // Can't eliminate. }
- graph = BuildSSAGraph2(&allocator, &bounds_check, -1);
- graph->BuildDominatorTree();
- graph->AnalyzeNaturalLoops();
- RunSimplifierAndGvn(graph);
- BoundsCheckElimination bounds_check_elimination_with_initial_minus_1(graph);
- bounds_check_elimination_with_initial_minus_1.Run();
+ HInstruction* bounds_check = BuildSSAGraph2(graph_, &allocator_, -1);
+ RunBCE();
ASSERT_FALSE(IsRemoved(bounds_check));
+}
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2d) {
// for (int i=array.length; i>=0; i--) { array[i-1] = 10; // Can't eliminate. }
- graph = BuildSSAGraph2(&allocator, &bounds_check, 0, -1, kCondLT);
- graph->BuildDominatorTree();
- graph->AnalyzeNaturalLoops();
- RunSimplifierAndGvn(graph);
- BoundsCheckElimination bounds_check_elimination_with_less_than(graph);
- bounds_check_elimination_with_less_than.Run();
+ HInstruction* bounds_check = BuildSSAGraph2(graph_, &allocator_, 0, -1, kCondLT);
+ RunBCE();
ASSERT_FALSE(IsRemoved(bounds_check));
+}
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination2e) {
// for (int i=array.length; i>0; i-=2) { array[i-1] = 10; // Can eliminate. }
- graph = BuildSSAGraph2(&allocator, &bounds_check, 0, -2);
- graph->BuildDominatorTree();
- graph->AnalyzeNaturalLoops();
- RunSimplifierAndGvn(graph);
- BoundsCheckElimination bounds_check_elimination_increment_minus_2(graph);
- bounds_check_elimination_increment_minus_2.Run();
+ HInstruction* bounds_check = BuildSSAGraph2(graph_, &allocator_, 0, -2);
+ RunBCE();
ASSERT_TRUE(IsRemoved(bounds_check));
}
// int[] array = new int[10];
// for (int i=0; i<10; i+=increment) { array[i] = 10; }
-static HGraph* BuildSSAGraph3(ArenaAllocator* allocator,
- HInstruction** bounds_check,
- int initial,
- int increment,
- IfCondition cond) {
- HGraph* graph = CreateGraph(allocator);
- graph->SetHasBoundsChecks(true);
-
+static HInstruction* BuildSSAGraph3(HGraph* graph,
+ ArenaAllocator* allocator,
+ int initial,
+ int increment,
+ IfCondition cond) {
HBasicBlock* entry = new (allocator) HBasicBlock(graph);
graph->AddBlock(entry);
graph->SetEntryBlock(entry);
@@ -679,13 +632,13 @@
HNullCheck* null_check = new (allocator) HNullCheck(new_array, 0);
HArrayLength* array_length = new (allocator) HArrayLength(null_check);
- *bounds_check = new (allocator) HBoundsCheck(phi, array_length, 0);
+ HInstruction* bounds_check = new (allocator) HBoundsCheck(phi, array_length, 0);
HInstruction* array_set = new (allocator) HArraySet(
- null_check, *bounds_check, constant_10, Primitive::kPrimInt, 0);
+ null_check, bounds_check, constant_10, Primitive::kPrimInt, 0);
HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_increment);
loop_body->AddInstruction(null_check);
loop_body->AddInstruction(array_length);
- loop_body->AddInstruction(*bounds_check);
+ loop_body->AddInstruction(bounds_check);
loop_body->AddInstruction(array_set);
loop_body->AddInstruction(add);
loop_body->AddInstruction(new (allocator) HGoto());
@@ -693,63 +646,46 @@
exit->AddInstruction(new (allocator) HExit());
- return graph;
+ return bounds_check;
}
-TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination3) {
- ArenaPool pool;
- ArenaAllocator allocator(&pool);
-
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3a) {
// 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);
- graph->BuildDominatorTree();
- graph->AnalyzeNaturalLoops();
- RunSimplifierAndGvn(graph);
- BoundsCheckElimination bounds_check_elimination(graph);
- bounds_check_elimination.Run();
+ HInstruction* bounds_check = BuildSSAGraph3(graph_, &allocator_, 0, 1, kCondGE);
+ RunBCE();
ASSERT_TRUE(IsRemoved(bounds_check));
+}
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3b) {
// 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();
- graph->AnalyzeNaturalLoops();
- RunSimplifierAndGvn(graph);
- BoundsCheckElimination bounds_check_elimination_with_initial_1(graph);
- bounds_check_elimination_with_initial_1.Run();
+ HInstruction* bounds_check = BuildSSAGraph3(graph_, &allocator_, 1, 1, kCondGE);
+ RunBCE();
ASSERT_TRUE(IsRemoved(bounds_check));
+}
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3c) {
// 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();
- graph->AnalyzeNaturalLoops();
- RunSimplifierAndGvn(graph);
- BoundsCheckElimination bounds_check_elimination_with_greater_than(graph);
- bounds_check_elimination_with_greater_than.Run();
+ HInstruction* bounds_check = BuildSSAGraph3(graph_, &allocator_, 0, 1, kCondGT);
+ RunBCE();
ASSERT_FALSE(IsRemoved(bounds_check));
+}
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination3d) {
// 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();
- graph->AnalyzeNaturalLoops();
- RunSimplifierAndGvn(graph);
- BoundsCheckElimination bounds_check_elimination_increment_8(graph);
- bounds_check_elimination_increment_8.Run();
+ HInstruction* bounds_check = BuildSSAGraph3(graph_, &allocator_, 1, 8, kCondGE);
+ RunBCE();
ASSERT_TRUE(IsRemoved(bounds_check));
}
// for (int i=initial; i<array.length; i++) { array[array.length-i-1] = 10; }
-static HGraph* BuildSSAGraph4(ArenaAllocator* allocator,
- HInstruction** bounds_check,
- int initial,
- IfCondition cond = kCondGE) {
- HGraph* graph = CreateGraph(allocator);
- graph->SetHasBoundsChecks(true);
-
+static HInstruction* BuildSSAGraph4(HGraph* graph,
+ ArenaAllocator* allocator,
+ int initial,
+ IfCondition cond = kCondGE) {
HBasicBlock* entry = new (allocator) HBasicBlock(graph);
graph->AddBlock(entry);
graph->SetEntryBlock(entry);
@@ -800,15 +736,15 @@
HInstruction* sub = new (allocator) HSub(Primitive::kPrimInt, array_length, phi);
HInstruction* add_minus_1 = new (allocator)
HAdd(Primitive::kPrimInt, sub, constant_minus_1);
- *bounds_check = new (allocator) HBoundsCheck(add_minus_1, array_length, 0);
+ HInstruction* bounds_check = new (allocator) HBoundsCheck(add_minus_1, array_length, 0);
HInstruction* array_set = new (allocator) HArraySet(
- null_check, *bounds_check, constant_10, Primitive::kPrimInt, 0);
+ null_check, bounds_check, constant_10, Primitive::kPrimInt, 0);
HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_1);
loop_body->AddInstruction(null_check);
loop_body->AddInstruction(array_length);
loop_body->AddInstruction(sub);
loop_body->AddInstruction(add_minus_1);
- loop_body->AddInstruction(*bounds_check);
+ loop_body->AddInstruction(bounds_check);
loop_body->AddInstruction(array_set);
loop_body->AddInstruction(add);
loop_body->AddInstruction(new (allocator) HGoto());
@@ -816,39 +752,27 @@
exit->AddInstruction(new (allocator) HExit());
- return graph;
+ return bounds_check;
}
-TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination4) {
- ArenaPool pool;
- ArenaAllocator allocator(&pool);
-
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination4a) {
// for (int i=0; i<array.length; i++) { array[array.length-i-1] = 10; // Can eliminate with gvn. }
- HInstruction* bounds_check = nullptr;
- HGraph* graph = BuildSSAGraph4(&allocator, &bounds_check, 0);
- graph->BuildDominatorTree();
- graph->AnalyzeNaturalLoops();
- RunSimplifierAndGvn(graph);
- BoundsCheckElimination bounds_check_elimination(graph);
- bounds_check_elimination.Run();
+ HInstruction* bounds_check = BuildSSAGraph4(graph_, &allocator_, 0);
+ RunBCE();
ASSERT_TRUE(IsRemoved(bounds_check));
+}
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination4b) {
// for (int i=1; i<array.length; i++) { array[array.length-i-1] = 10; // Can eliminate. }
- graph = BuildSSAGraph4(&allocator, &bounds_check, 1);
- graph->BuildDominatorTree();
- graph->AnalyzeNaturalLoops();
- RunSimplifierAndGvn(graph);
- BoundsCheckElimination bounds_check_elimination_with_initial_1(graph);
- bounds_check_elimination_with_initial_1.Run();
+ HInstruction* bounds_check = BuildSSAGraph4(graph_, &allocator_, 1);
+ RunBCE();
ASSERT_TRUE(IsRemoved(bounds_check));
+}
+TEST_F(BoundsCheckEliminationTest, LoopArrayBoundsElimination4c) {
// for (int i=0; i<=array.length; i++) { array[array.length-i] = 10; // Can't eliminate. }
- graph = BuildSSAGraph4(&allocator, &bounds_check, 0, kCondGT);
- graph->BuildDominatorTree();
- graph->AnalyzeNaturalLoops();
- RunSimplifierAndGvn(graph);
- BoundsCheckElimination bounds_check_elimination_with_greater_than(graph);
- bounds_check_elimination_with_greater_than.Run();
+ HInstruction* bounds_check = BuildSSAGraph4(graph_, &allocator_, 0, kCondGT);
+ RunBCE();
ASSERT_FALSE(IsRemoved(bounds_check));
}
@@ -863,40 +787,34 @@
// }
// }
// }
-TEST(BoundsCheckEliminationTest, BubbleSortArrayBoundsElimination) {
- ArenaPool pool;
- ArenaAllocator allocator(&pool);
-
- HGraph* graph = CreateGraph(&allocator);
- graph->SetHasBoundsChecks(true);
-
- HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
- graph->AddBlock(entry);
- graph->SetEntryBlock(entry);
- HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimNot);
+TEST_F(BoundsCheckEliminationTest, BubbleSortArrayBoundsElimination) {
+ HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(entry);
+ graph_->SetEntryBlock(entry);
+ HInstruction* parameter = new (&allocator_) HParameterValue(0, Primitive::kPrimNot);
entry->AddInstruction(parameter);
- HInstruction* constant_0 = graph->GetIntConstant(0);
- HInstruction* constant_minus_1 = graph->GetIntConstant(-1);
- HInstruction* constant_1 = graph->GetIntConstant(1);
+ HInstruction* constant_0 = graph_->GetIntConstant(0);
+ HInstruction* constant_minus_1 = graph_->GetIntConstant(-1);
+ HInstruction* constant_1 = graph_->GetIntConstant(1);
- HBasicBlock* block = new (&allocator) HBasicBlock(graph);
- graph->AddBlock(block);
+ HBasicBlock* block = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(block);
entry->AddSuccessor(block);
- block->AddInstruction(new (&allocator) HGoto());
+ block->AddInstruction(new (&allocator_) HGoto());
- HBasicBlock* exit = new (&allocator) HBasicBlock(graph);
- graph->AddBlock(exit);
- exit->AddInstruction(new (&allocator) HExit());
+ HBasicBlock* exit = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(exit);
+ exit->AddInstruction(new (&allocator_) HExit());
- HBasicBlock* outer_header = new (&allocator) HBasicBlock(graph);
- graph->AddBlock(outer_header);
- HPhi* phi_i = new (&allocator) HPhi(&allocator, 0, 0, Primitive::kPrimInt);
- HNullCheck* null_check = new (&allocator) HNullCheck(parameter, 0);
- HArrayLength* array_length = new (&allocator) HArrayLength(null_check);
- HAdd* add = new (&allocator) HAdd(Primitive::kPrimInt, array_length, constant_minus_1);
- HInstruction* cmp = new (&allocator) HGreaterThanOrEqual(phi_i, add);
- HIf* if_inst = new (&allocator) HIf(cmp);
+ HBasicBlock* outer_header = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(outer_header);
+ HPhi* phi_i = new (&allocator_) HPhi(&allocator_, 0, 0, Primitive::kPrimInt);
+ HNullCheck* null_check = new (&allocator_) HNullCheck(parameter, 0);
+ HArrayLength* array_length = new (&allocator_) HArrayLength(null_check);
+ HAdd* add = new (&allocator_) HAdd(Primitive::kPrimInt, array_length, constant_minus_1);
+ HInstruction* cmp = new (&allocator_) HGreaterThanOrEqual(phi_i, add);
+ HIf* if_inst = new (&allocator_) HIf(cmp);
outer_header->AddPhi(phi_i);
outer_header->AddInstruction(null_check);
outer_header->AddInstruction(array_length);
@@ -905,15 +823,15 @@
outer_header->AddInstruction(if_inst);
phi_i->AddInput(constant_0);
- HBasicBlock* inner_header = new (&allocator) HBasicBlock(graph);
- graph->AddBlock(inner_header);
- HPhi* phi_j = new (&allocator) HPhi(&allocator, 0, 0, Primitive::kPrimInt);
- null_check = new (&allocator) HNullCheck(parameter, 0);
- array_length = new (&allocator) HArrayLength(null_check);
- HSub* sub = new (&allocator) HSub(Primitive::kPrimInt, array_length, phi_i);
- add = new (&allocator) HAdd(Primitive::kPrimInt, sub, constant_minus_1);
- cmp = new (&allocator) HGreaterThanOrEqual(phi_j, add);
- if_inst = new (&allocator) HIf(cmp);
+ HBasicBlock* inner_header = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(inner_header);
+ HPhi* phi_j = new (&allocator_) HPhi(&allocator_, 0, 0, Primitive::kPrimInt);
+ null_check = new (&allocator_) HNullCheck(parameter, 0);
+ array_length = new (&allocator_) HArrayLength(null_check);
+ HSub* sub = new (&allocator_) HSub(Primitive::kPrimInt, array_length, phi_i);
+ add = new (&allocator_) HAdd(Primitive::kPrimInt, sub, constant_minus_1);
+ cmp = new (&allocator_) HGreaterThanOrEqual(phi_j, add);
+ if_inst = new (&allocator_) HIf(cmp);
inner_header->AddPhi(phi_j);
inner_header->AddInstruction(null_check);
inner_header->AddInstruction(array_length);
@@ -923,25 +841,25 @@
inner_header->AddInstruction(if_inst);
phi_j->AddInput(constant_0);
- HBasicBlock* inner_body_compare = new (&allocator) HBasicBlock(graph);
- graph->AddBlock(inner_body_compare);
- null_check = new (&allocator) HNullCheck(parameter, 0);
- array_length = new (&allocator) HArrayLength(null_check);
- HBoundsCheck* bounds_check1 = new (&allocator) HBoundsCheck(phi_j, array_length, 0);
- HArrayGet* array_get_j = new (&allocator)
+ HBasicBlock* inner_body_compare = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(inner_body_compare);
+ null_check = new (&allocator_) HNullCheck(parameter, 0);
+ array_length = new (&allocator_) HArrayLength(null_check);
+ HBoundsCheck* bounds_check1 = new (&allocator_) HBoundsCheck(phi_j, array_length, 0);
+ HArrayGet* array_get_j = new (&allocator_)
HArrayGet(null_check, bounds_check1, Primitive::kPrimInt);
inner_body_compare->AddInstruction(null_check);
inner_body_compare->AddInstruction(array_length);
inner_body_compare->AddInstruction(bounds_check1);
inner_body_compare->AddInstruction(array_get_j);
- HInstruction* j_plus_1 = new (&allocator) HAdd(Primitive::kPrimInt, phi_j, constant_1);
- null_check = new (&allocator) HNullCheck(parameter, 0);
- array_length = new (&allocator) HArrayLength(null_check);
- HBoundsCheck* bounds_check2 = new (&allocator) HBoundsCheck(j_plus_1, array_length, 0);
- HArrayGet* array_get_j_plus_1 = new (&allocator)
+ HInstruction* j_plus_1 = new (&allocator_) HAdd(Primitive::kPrimInt, phi_j, constant_1);
+ null_check = new (&allocator_) HNullCheck(parameter, 0);
+ array_length = new (&allocator_) HArrayLength(null_check);
+ HBoundsCheck* bounds_check2 = new (&allocator_) HBoundsCheck(j_plus_1, array_length, 0);
+ HArrayGet* array_get_j_plus_1 = new (&allocator_)
HArrayGet(null_check, bounds_check2, Primitive::kPrimInt);
- cmp = new (&allocator) HGreaterThanOrEqual(array_get_j, array_get_j_plus_1);
- if_inst = new (&allocator) HIf(cmp);
+ cmp = new (&allocator_) HGreaterThanOrEqual(array_get_j, array_get_j_plus_1);
+ if_inst = new (&allocator_) HIf(cmp);
inner_body_compare->AddInstruction(j_plus_1);
inner_body_compare->AddInstruction(null_check);
inner_body_compare->AddInstruction(array_length);
@@ -950,14 +868,14 @@
inner_body_compare->AddInstruction(cmp);
inner_body_compare->AddInstruction(if_inst);
- HBasicBlock* inner_body_swap = new (&allocator) HBasicBlock(graph);
- graph->AddBlock(inner_body_swap);
- j_plus_1 = new (&allocator) HAdd(Primitive::kPrimInt, phi_j, constant_1);
+ HBasicBlock* inner_body_swap = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(inner_body_swap);
+ j_plus_1 = new (&allocator_) HAdd(Primitive::kPrimInt, phi_j, constant_1);
// temp = array[j+1]
- null_check = new (&allocator) HNullCheck(parameter, 0);
- array_length = new (&allocator) HArrayLength(null_check);
- HInstruction* bounds_check3 = new (&allocator) HBoundsCheck(j_plus_1, array_length, 0);
- array_get_j_plus_1 = new (&allocator)
+ null_check = new (&allocator_) HNullCheck(parameter, 0);
+ array_length = new (&allocator_) HArrayLength(null_check);
+ HInstruction* bounds_check3 = new (&allocator_) HBoundsCheck(j_plus_1, array_length, 0);
+ array_get_j_plus_1 = new (&allocator_)
HArrayGet(null_check, bounds_check3, Primitive::kPrimInt);
inner_body_swap->AddInstruction(j_plus_1);
inner_body_swap->AddInstruction(null_check);
@@ -965,48 +883,48 @@
inner_body_swap->AddInstruction(bounds_check3);
inner_body_swap->AddInstruction(array_get_j_plus_1);
// array[j+1] = array[j]
- null_check = new (&allocator) HNullCheck(parameter, 0);
- array_length = new (&allocator) HArrayLength(null_check);
- HInstruction* bounds_check4 = new (&allocator) HBoundsCheck(phi_j, array_length, 0);
- array_get_j = new (&allocator)
+ null_check = new (&allocator_) HNullCheck(parameter, 0);
+ array_length = new (&allocator_) HArrayLength(null_check);
+ HInstruction* bounds_check4 = new (&allocator_) HBoundsCheck(phi_j, array_length, 0);
+ array_get_j = new (&allocator_)
HArrayGet(null_check, bounds_check4, Primitive::kPrimInt);
inner_body_swap->AddInstruction(null_check);
inner_body_swap->AddInstruction(array_length);
inner_body_swap->AddInstruction(bounds_check4);
inner_body_swap->AddInstruction(array_get_j);
- null_check = new (&allocator) HNullCheck(parameter, 0);
- array_length = new (&allocator) HArrayLength(null_check);
- HInstruction* bounds_check5 = new (&allocator) HBoundsCheck(j_plus_1, array_length, 0);
- HArraySet* array_set_j_plus_1 = new (&allocator)
+ null_check = new (&allocator_) HNullCheck(parameter, 0);
+ array_length = new (&allocator_) HArrayLength(null_check);
+ HInstruction* bounds_check5 = new (&allocator_) HBoundsCheck(j_plus_1, array_length, 0);
+ HArraySet* array_set_j_plus_1 = new (&allocator_)
HArraySet(null_check, bounds_check5, array_get_j, Primitive::kPrimInt, 0);
inner_body_swap->AddInstruction(null_check);
inner_body_swap->AddInstruction(array_length);
inner_body_swap->AddInstruction(bounds_check5);
inner_body_swap->AddInstruction(array_set_j_plus_1);
// array[j] = temp
- null_check = new (&allocator) HNullCheck(parameter, 0);
- array_length = new (&allocator) HArrayLength(null_check);
- HInstruction* bounds_check6 = new (&allocator) HBoundsCheck(phi_j, array_length, 0);
- HArraySet* array_set_j = new (&allocator)
+ null_check = new (&allocator_) HNullCheck(parameter, 0);
+ array_length = new (&allocator_) HArrayLength(null_check);
+ HInstruction* bounds_check6 = new (&allocator_) HBoundsCheck(phi_j, array_length, 0);
+ HArraySet* array_set_j = new (&allocator_)
HArraySet(null_check, bounds_check6, array_get_j_plus_1, Primitive::kPrimInt, 0);
inner_body_swap->AddInstruction(null_check);
inner_body_swap->AddInstruction(array_length);
inner_body_swap->AddInstruction(bounds_check6);
inner_body_swap->AddInstruction(array_set_j);
- inner_body_swap->AddInstruction(new (&allocator) HGoto());
+ inner_body_swap->AddInstruction(new (&allocator_) HGoto());
- HBasicBlock* inner_body_add = new (&allocator) HBasicBlock(graph);
- graph->AddBlock(inner_body_add);
- add = new (&allocator) HAdd(Primitive::kPrimInt, phi_j, constant_1);
+ HBasicBlock* inner_body_add = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(inner_body_add);
+ add = new (&allocator_) HAdd(Primitive::kPrimInt, phi_j, constant_1);
inner_body_add->AddInstruction(add);
- inner_body_add->AddInstruction(new (&allocator) HGoto());
+ inner_body_add->AddInstruction(new (&allocator_) HGoto());
phi_j->AddInput(add);
- HBasicBlock* outer_body_add = new (&allocator) HBasicBlock(graph);
- graph->AddBlock(outer_body_add);
- add = new (&allocator) HAdd(Primitive::kPrimInt, phi_i, constant_1);
+ HBasicBlock* outer_body_add = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(outer_body_add);
+ add = new (&allocator_) HAdd(Primitive::kPrimInt, phi_i, constant_1);
outer_body_add->AddInstruction(add);
- outer_body_add->AddInstruction(new (&allocator) HGoto());
+ outer_body_add->AddInstruction(new (&allocator_) HGoto());
phi_i->AddInput(add);
block->AddSuccessor(outer_header);
@@ -1020,19 +938,8 @@
inner_body_add->AddSuccessor(inner_header);
outer_body_add->AddSuccessor(outer_header);
- graph->BuildDominatorTree();
- graph->AnalyzeNaturalLoops();
- RunSimplifierAndGvn(graph);
- // gvn should remove the same bounds check.
- ASSERT_FALSE(IsRemoved(bounds_check1));
- ASSERT_FALSE(IsRemoved(bounds_check2));
- ASSERT_TRUE(IsRemoved(bounds_check3));
- ASSERT_TRUE(IsRemoved(bounds_check4));
- ASSERT_TRUE(IsRemoved(bounds_check5));
- ASSERT_TRUE(IsRemoved(bounds_check6));
+ RunBCE(); // gvn removes same bounds check already
- BoundsCheckElimination bounds_check_elimination(graph);
- bounds_check_elimination.Run();
ASSERT_TRUE(IsRemoved(bounds_check1));
ASSERT_TRUE(IsRemoved(bounds_check2));
ASSERT_TRUE(IsRemoved(bounds_check3));
diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc
index 3f5a6e7..92c732c 100644
--- a/compiler/optimizing/induction_var_analysis.cc
+++ b/compiler/optimizing/induction_var_analysis.cc
@@ -15,6 +15,7 @@
*/
#include "induction_var_analysis.h"
+#include "induction_var_range.h"
namespace art {
@@ -42,6 +43,40 @@
instruction->GetBlock() == loop->GetHeader();
}
+/**
+ * Since graph traversal may enter a SCC at any position, an initial representation may be rotated,
+ * along dependences, viz. any of (a, b, c, d), (d, a, b, c) (c, d, a, b), (b, c, d, a) assuming
+ * a chain of dependences (mutual independent items may occur in arbitrary order). For proper
+ * classification, the lexicographically first entry-phi is rotated to the front.
+ */
+static void RotateEntryPhiFirst(HLoopInformation* loop,
+ ArenaVector<HInstruction*>* scc,
+ ArenaVector<HInstruction*>* new_scc) {
+ // Find very first entry-phi.
+ const HInstructionList& phis = loop->GetHeader()->GetPhis();
+ HInstruction* phi = nullptr;
+ size_t phi_pos = -1;
+ const size_t size = scc->size();
+ for (size_t i = 0; i < size; i++) {
+ if (IsEntryPhi(loop, scc->at(i)) && (phi == nullptr || phis.FoundBefore(scc->at(i), phi))) {
+ phi = scc->at(i);
+ phi_pos = i;
+ }
+ }
+
+ // If found, bring that entry-phi to front.
+ if (phi != nullptr) {
+ new_scc->clear();
+ for (size_t i = 0; i < size; i++) {
+ DCHECK_LT(phi_pos, size);
+ new_scc->push_back(scc->at(phi_pos));
+ if (++phi_pos >= size) phi_pos = 0;
+ }
+ DCHECK_EQ(size, new_scc->size());
+ scc->swap(*new_scc);
+ }
+}
+
//
// Class methods.
//
@@ -203,7 +238,15 @@
void HInductionVarAnalysis::ClassifyNonTrivial(HLoopInformation* loop) {
const size_t size = scc_.size();
DCHECK_GE(size, 1u);
- HInstruction* phi = scc_[size - 1];
+
+ // Rotate proper entry-phi to front.
+ if (size > 1) {
+ ArenaVector<HInstruction*> other(graph_->GetArena()->Adapter());
+ RotateEntryPhiFirst(loop, &scc_, &other);
+ }
+
+ // Analyze from phi onwards.
+ HInstruction* phi = scc_[0];
if (!IsEntryPhi(loop, phi)) {
return;
}
@@ -225,7 +268,7 @@
// Inspect remainder of the cycle that resides in scc_. The cycle_ mapping assigns
// temporary meaning to its nodes, seeded from the phi instruction and back.
- for (size_t i = 0; i < size - 1; i++) {
+ for (size_t i = 1; i < size; i++) {
HInstruction* instruction = scc_[i];
InductionInfo* update = nullptr;
if (instruction->IsPhi()) {
@@ -249,19 +292,19 @@
InductionInfo* induction = it->second;
switch (induction->induction_class) {
case kInvariant:
- // Classify phi (last element in scc_) and then the rest of the cycle "on-demand".
- // Statements are scanned in the Tarjan SCC order, with phi first.
+ // Classify first phi and then the rest of the cycle "on-demand".
+ // Statements are scanned in order.
AssignInfo(loop, phi, CreateInduction(kLinear, induction, initial));
- for (size_t i = 0; i < size - 1; i++) {
+ for (size_t i = 1; i < size; i++) {
ClassifyTrivial(loop, scc_[i]);
}
break;
case kPeriodic:
- // Classify all elements in the cycle with the found periodic induction while rotating
- // each first element to the end. Lastly, phi (last element in scc_) is classified.
- // Statements are scanned in the reverse Tarjan SCC order, with phi last.
- for (size_t i = 2; i <= size; i++) {
- AssignInfo(loop, scc_[size - i], induction);
+ // Classify all elements in the cycle with the found periodic induction while
+ // rotating each first element to the end. Lastly, phi is classified.
+ // Statements are scanned in reverse order.
+ for (size_t i = size - 1; i >= 1; i--) {
+ AssignInfo(loop, scc_[i], induction);
induction = RotatePeriodicInduction(induction->op_b, induction->op_a);
}
AssignInfo(loop, phi, induction);
@@ -511,12 +554,15 @@
InductionInfo* stride = a->op_a;
InductionInfo* lo_val = a->op_b;
InductionInfo* hi_val = b;
- int64_t value = -1;
- if (IsIntAndGet(stride, &value)) {
- if ((value > 0 && (cmp == kCondLT || cmp == kCondLE)) ||
- (value < 0 && (cmp == kCondGT || cmp == kCondGE))) {
+ // Analyze the stride thoroughly, since its representation may be compound at this point.
+ InductionVarRange::Value v1 = InductionVarRange::GetMin(stride, nullptr);
+ InductionVarRange::Value v2 = InductionVarRange::GetMax(stride, nullptr);
+ if (v1.a_constant == 0 && v2.a_constant == 0 && v1.b_constant == v2.b_constant) {
+ const int32_t stride_value = v1.b_constant;
+ if ((stride_value > 0 && (cmp == kCondLT || cmp == kCondLE)) ||
+ (stride_value < 0 && (cmp == kCondGT || cmp == kCondGE))) {
bool is_strict = cmp == kCondLT || cmp == kCondGT;
- VisitTripCount(loop, lo_val, hi_val, stride, value, type, is_strict);
+ VisitTripCount(loop, lo_val, hi_val, stride, stride_value, type, is_strict);
}
}
}
@@ -544,7 +590,7 @@
// least once. Otherwise TC is 0. Also, the expression assumes the loop does not
// have any early-exits. Otherwise, TC is an upper bound.
//
- bool cancels = is_strict && abs(stride_value) == 1; // compensation cancels conversion?
+ bool cancels = is_strict && std::abs(stride_value) == 1; // compensation cancels conversion?
if (!cancels) {
// Convert exclusive integral inequality into inclusive integral inequality,
// viz. condition i < U is i <= U - 1 and condition i > U is i >= U + 1.
@@ -557,7 +603,7 @@
}
// Assign the trip-count expression to the loop control. Clients that use the information
- // should be aware that due to the L <= U assumption, the expression is only valid in the
+ // should be aware that due to the top-test assumption, the expression is only valid in the
// loop-body proper, and not yet in the loop-header. If the loop has any early exits, the
// trip-count forms a conservative upper bound on the number of loop iterations.
InductionInfo* trip_count =
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
index bd90334..486e904 100644
--- a/compiler/optimizing/induction_var_range.cc
+++ b/compiler/optimizing/induction_var_range.cc
@@ -126,6 +126,7 @@
}
InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction,
+ HInductionVarAnalysis::InductionInfo* trip,
int32_t fail_value) {
// Detect constants and chase the fetch a bit deeper into the HIR tree, so that it becomes
// more likely range analysis will compare the same instructions as terminal nodes.
@@ -134,9 +135,16 @@
return Value(value);
} else if (instruction->IsAdd()) {
if (IsIntAndGet(instruction->InputAt(0), &value)) {
- return AddValue(Value(value), GetFetch(instruction->InputAt(1), fail_value), fail_value);
+ return AddValue(Value(value),
+ GetFetch(instruction->InputAt(1), trip, fail_value), fail_value);
} else if (IsIntAndGet(instruction->InputAt(1), &value)) {
- return AddValue(GetFetch(instruction->InputAt(0), fail_value), Value(value), fail_value);
+ return AddValue(GetFetch(instruction->InputAt(0), trip, fail_value),
+ Value(value), fail_value);
+ }
+ } else if (fail_value < 0) {
+ // Special case: within the loop-body, minimum of trip-count is 1.
+ if (trip != nullptr && instruction == trip->op_b->fetch) {
+ return Value(1);
}
}
return Value(instruction, 1, 0);
@@ -163,7 +171,7 @@
case HInductionVarAnalysis::kDiv:
return GetDiv(info->op_a, info->op_b, trip, INT_MIN);
case HInductionVarAnalysis::kFetch:
- return GetFetch(info->fetch, INT_MIN);
+ return GetFetch(info->fetch, trip, INT_MIN);
}
break;
case HInductionVarAnalysis::kLinear:
@@ -200,7 +208,7 @@
case HInductionVarAnalysis::kDiv:
return GetDiv(info->op_a, info->op_b, trip, INT_MAX);
case HInductionVarAnalysis::kFetch:
- return GetFetch(info->fetch, INT_MAX);
+ return GetFetch(info->fetch, trip, INT_MAX);
}
break;
case HInductionVarAnalysis::kLinear:
diff --git a/compiler/optimizing/induction_var_range.h b/compiler/optimizing/induction_var_range.h
index b079076..e002e5f 100644
--- a/compiler/optimizing/induction_var_range.h
+++ b/compiler/optimizing/induction_var_range.h
@@ -27,7 +27,7 @@
* API to obtain a conservative lower and upper bound value on each instruction in the HIR.
*
* For example, given a linear induction 2 * i + x where 0 <= i <= 10, range analysis yields lower
- * bound value x and upper bound value x + 20 for the expression, thus, the range [0, x + 20].
+ * bound value x and upper bound value x + 20 for the expression, thus, the range [x, x + 20].
*/
class InductionVarRange {
public:
@@ -39,7 +39,7 @@
*/
struct Value {
Value(HInstruction* i, int32_t a, int32_t b)
- : instruction(a ? i : nullptr),
+ : instruction(a != 0 ? i : nullptr),
a_constant(a),
b_constant(b) {}
explicit Value(int32_t b) : Value(nullptr, 0, b) {}
@@ -70,7 +70,9 @@
HInductionVarAnalysis::InductionInfo* GetTripCount(HLoopInformation* loop,
HInstruction* context);
- static Value GetFetch(HInstruction* instruction, int32_t fail_value);
+ static Value GetFetch(HInstruction* instruction,
+ HInductionVarAnalysis::InductionInfo* trip,
+ int32_t fail_value);
static Value GetMin(HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip);
@@ -78,10 +80,12 @@
HInductionVarAnalysis::InductionInfo* trip);
static Value GetMul(HInductionVarAnalysis::InductionInfo* info1,
HInductionVarAnalysis::InductionInfo* info2,
- HInductionVarAnalysis::InductionInfo* trip, int32_t fail_value);
+ HInductionVarAnalysis::InductionInfo* trip,
+ int32_t fail_value);
static Value GetDiv(HInductionVarAnalysis::InductionInfo* info1,
HInductionVarAnalysis::InductionInfo* info2,
- HInductionVarAnalysis::InductionInfo* trip, int32_t fail_value);
+ HInductionVarAnalysis::InductionInfo* trip,
+ int32_t fail_value);
static Value AddValue(Value v1, Value v2, int32_t fail_value);
static Value SubValue(Value v1, Value v2, int32_t fail_value);
@@ -93,6 +97,7 @@
/** Results of prior induction variable analysis. */
HInductionVarAnalysis *induction_analysis_;
+ friend class HInductionVarAnalysis;
friend class InductionVarRangeTest;
DISALLOW_COPY_AND_ASSIGN(InductionVarRange);
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 4421460..8fc1e4e 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -51,6 +51,7 @@
#include "graph_checker.h"
#include "graph_visualizer.h"
#include "gvn.h"
+#include "induction_var_analysis.h"
#include "inliner.h"
#include "instruction_simplifier.h"
#include "intrinsics.h"
@@ -462,7 +463,8 @@
SideEffectsAnalysis* side_effects = new (arena) SideEffectsAnalysis(graph);
GVNOptimization* gvn = new (arena) GVNOptimization(graph, *side_effects);
LICM* licm = new (arena) LICM(graph, *side_effects);
- BoundsCheckElimination* bce = new (arena) BoundsCheckElimination(graph);
+ HInductionVarAnalysis* induction = new (arena) HInductionVarAnalysis(graph);
+ BoundsCheckElimination* bce = new (arena) BoundsCheckElimination(graph, induction);
ReferenceTypePropagation* type_propagation =
new (arena) ReferenceTypePropagation(graph, handles);
InstructionSimplifier* simplify2 = new (arena) InstructionSimplifier(
@@ -510,6 +512,7 @@
side_effects,
gvn,
licm,
+ induction,
bce,
simplify3,
dce2,
diff --git a/test/530-checker-loops/expected.txt b/test/530-checker-loops/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/530-checker-loops/expected.txt
diff --git a/test/530-checker-loops/info.txt b/test/530-checker-loops/info.txt
new file mode 100644
index 0000000..f5d334d
--- /dev/null
+++ b/test/530-checker-loops/info.txt
@@ -0,0 +1 @@
+Test on loop optimizations.
diff --git a/test/530-checker-loops/src/Main.java b/test/530-checker-loops/src/Main.java
new file mode 100644
index 0000000..e518a61
--- /dev/null
+++ b/test/530-checker-loops/src/Main.java
@@ -0,0 +1,354 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+//
+// Test on loop optimizations.
+//
+public class Main {
+
+ static int sResult;
+
+ //
+ // Various sequence variables where bound checks can be removed from loop.
+ //
+
+ /// CHECK-START: int Main.linear(int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.linear(int[]) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int linear(int[] x) {
+ int result = 0;
+ for (int i = 0; i < x.length; i++) {
+ result += x[i];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.linearDown(int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.linearDown(int[]) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int linearDown(int[] x) {
+ int result = 0;
+ for (int i = x.length - 1; i >= 0; i--) {
+ result += x[i];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.linearObscure(int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.linearObscure(int[]) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int linearObscure(int[] x) {
+ int result = 0;
+ for (int i = x.length - 1; i >= 0; i--) {
+ int k = i + 5;
+ result += x[k - 5];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.linearWhile(int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.linearWhile(int[]) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int linearWhile(int[] x) {
+ int i = 0;
+ int result = 0;
+ while (i < x.length) {
+ result += x[i++];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.wrapAroundThenLinear(int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.wrapAroundThenLinear(int[]) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int wrapAroundThenLinear(int[] x) {
+ // Loop with wrap around (length - 1, 0, 1, 2, ..).
+ int w = x.length - 1;
+ int result = 0;
+ for (int i = 0; i < x.length; i++) {
+ result += x[w];
+ w = i;
+ }
+ return result;
+ }
+
+ /// CHECK-START: int[] Main.linearWithParameter(int) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int[] Main.linearWithParameter(int) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int[] linearWithParameter(int n) {
+ int[] x = new int[n];
+ for (int i = 0; i < n; i++) {
+ x[i] = i;
+ }
+ return x;
+ }
+
+ /// CHECK-START: int Main.linearWithCompoundStride() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.linearWithCompoundStride() BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int linearWithCompoundStride() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 };
+ int result = 0;
+ for (int i = 0; i <= 12; ) {
+ i++;
+ result += x[i];
+ i++;
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.linearWithLargePositiveStride() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.linearWithLargePositiveStride() BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int linearWithLargePositiveStride() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
+ int result = 0;
+ int k = 0;
+ // Range analysis has no problem with a trip-count defined by a
+ // reasonably large positive stride.
+ for (int i = 1; i <= 10 * 10000000 + 1; i += 10000000) {
+ result += x[k++];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.linearWithVeryLargePositiveStride() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.linearWithVeryLargePositiveStride() BCE (after)
+ /// CHECK-DAG: BoundsCheck
+ private static int linearWithVeryLargePositiveStride() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
+ int result = 0;
+ int k = 0;
+ // Range analysis conservatively bails due to potential of wrap-around
+ // arithmetic while computing the trip-count for this very large stride.
+ for (int i = 1; i < 2147483647; i += 195225786) {
+ result += x[k++];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.linearWithLargeNegativeStride() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.linearWithLargeNegativeStride() BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int linearWithLargeNegativeStride() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
+ int result = 0;
+ int k = 0;
+ // Range analysis has no problem with a trip-count defined by a
+ // reasonably large negative stride.
+ for (int i = -1; i >= -10 * 10000000 - 1; i -= 10000000) {
+ result += x[k++];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.linearWithVeryLargeNegativeStride() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.linearWithVeryLargeNegativeStride() BCE (after)
+ /// CHECK-DAG: BoundsCheck
+ private static int linearWithVeryLargeNegativeStride() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
+ int result = 0;
+ int k = 0;
+ // Range analysis conservatively bails due to potential of wrap-around
+ // arithmetic while computing the trip-count for this very large stride.
+ for (int i = -2; i > -2147483648; i -= 195225786) {
+ result += x[k++];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.periodicIdiom(int) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.periodicIdiom(int) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int periodicIdiom(int tc) {
+ int[] x = { 1, 3 };
+ // Loop with periodic sequence (0, 1).
+ int k = 0;
+ int result = 0;
+ for (int i = 0; i < tc; i++) {
+ result += x[k];
+ k = 1 - k;
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.periodicSequence2(int) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.periodicSequence2(int) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int periodicSequence2(int tc) {
+ int[] x = { 1, 3 };
+ // Loop with periodic sequence (0, 1).
+ int k = 0;
+ int l = 1;
+ int result = 0;
+ for (int i = 0; i < tc; i++) {
+ result += x[k];
+ int t = l;
+ l = k;
+ k = t;
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.periodicSequence4(int) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.periodicSequence4(int) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int periodicSequence4(int tc) {
+ int[] x = { 1, 3, 5, 7 };
+ // Loop with periodic sequence (0, 1, 2, 3).
+ int k = 0;
+ int l = 1;
+ int m = 2;
+ int n = 3;
+ int result = 0;
+ for (int i = 0; i < tc; i++) {
+ result += x[k] + x[l] + x[m] + x[n]; // all used at once
+ int t = n;
+ n = k;
+ k = l;
+ l = m;
+ m = t;
+ }
+ return result;
+ }
+
+ //
+ // Cases that actually go out of bounds. These test cases
+ // ensure the exceptions are thrown at the right places.
+ //
+
+ private static void lowerOOB(int[] x) {
+ for (int i = -1; i < x.length; i++) {
+ sResult += x[i];
+ }
+ }
+
+ private static void upperOOB(int[] x) {
+ for (int i = 0; i <= x.length; i++) {
+ sResult += x[i];
+ }
+ }
+
+ //
+ // Verifier.
+ //
+
+ public static void main(String[] args) {
+ int[] empty = { };
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+
+ // Linear and wrap-around.
+ expectEquals(0, linear(empty));
+ expectEquals(55, linear(x));
+ expectEquals(0, linearDown(empty));
+ expectEquals(55, linearDown(x));
+ expectEquals(0, linearObscure(empty));
+ expectEquals(55, linearObscure(x));
+ expectEquals(0, linearWhile(empty));
+ expectEquals(55, linearWhile(x));
+ expectEquals(0, wrapAroundThenLinear(empty));
+ expectEquals(55, wrapAroundThenLinear(x));
+
+ // Linear with parameter.
+ sResult = 0;
+ try {
+ linearWithParameter(-1);
+ } catch (NegativeArraySizeException e) {
+ sResult = 1;
+ }
+ expectEquals(1, sResult);
+ for (int n = 0; n < 32; n++) {
+ int[] r = linearWithParameter(n);
+ expectEquals(n, r.length);
+ for (int i = 0; i < n; i++) {
+ expectEquals(i, r[i]);
+ }
+ }
+
+ // Linear with non-unit strides.
+ expectEquals(56, linearWithCompoundStride());
+ expectEquals(66, linearWithLargePositiveStride());
+ expectEquals(66, linearWithVeryLargePositiveStride());
+ expectEquals(66, linearWithLargeNegativeStride());
+ expectEquals(66, linearWithVeryLargeNegativeStride());
+
+ // Periodic adds (1, 3), one at the time.
+ expectEquals(0, periodicIdiom(-1));
+ for (int tc = 0; tc < 32; tc++) {
+ int expected = (tc >> 1) << 2;
+ if ((tc & 1) != 0)
+ expected += 1;
+ expectEquals(expected, periodicIdiom(tc));
+ }
+
+ // Periodic adds (1, 3), one at the time.
+ expectEquals(0, periodicSequence2(-1));
+ for (int tc = 0; tc < 32; tc++) {
+ int expected = (tc >> 1) << 2;
+ if ((tc & 1) != 0)
+ expected += 1;
+ expectEquals(expected, periodicSequence2(tc));
+ }
+
+ // Periodic adds (1, 3, 5, 7), all at once.
+ expectEquals(0, periodicSequence4(-1));
+ for (int tc = 0; tc < 32; tc++) {
+ expectEquals(tc * 16, periodicSequence4(tc));
+ }
+
+ // Lower bound goes OOB.
+ sResult = 0;
+ try {
+ lowerOOB(x);
+ } catch (ArrayIndexOutOfBoundsException e) {
+ sResult += 1000;
+ }
+ expectEquals(1000, sResult);
+
+ // Upper bound goes OOB.
+ sResult = 0;
+ try {
+ upperOOB(x);
+ } catch (ArrayIndexOutOfBoundsException e) {
+ sResult += 1000;
+ }
+ expectEquals(1055, sResult);
+
+ }
+
+ private static void expectEquals(int expected, int result) {
+ if (expected != result) {
+ throw new Error("Expected: " + expected + ", found: " + result);
+ }
+ }
+}