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/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