Generalized "dom-based" dynamic BCE to symbolic base + offset.
Rationale:
So far, if all others failed, BCE would use a dominator-based
dynamic deoptimization to eliminate bounds checks in e.g. a[0],
a[1], a[2], etc. This CL generalizes this to any symbolic base
with offset in e.g. a[base], a[base+1], etc. The runtime tests
(two for symbolic, one for constant) carefully account for
arithmetic wrap-around.
bug=26680114
Change-Id: I7432a200fd69791914ed776c77fa62567b5863c0
diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index c307522..c694ea8 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -63,9 +63,10 @@
return true;
}
+ // Return true if instruction can be expressed as "left_instruction + right_constant".
static bool IsAddOrSubAConstant(HInstruction* instruction,
- HInstruction** left_instruction,
- int* right_constant) {
+ /* out */ HInstruction** left_instruction,
+ /* out */ int32_t* right_constant) {
if (instruction->IsAdd() || instruction->IsSub()) {
HBinaryOperation* bin_op = instruction->AsBinaryOperation();
HInstruction* left = bin_op->GetLeft();
@@ -82,9 +83,22 @@
return false;
}
+ // Expresses any instruction as a value bound.
+ static ValueBound AsValueBound(HInstruction* instruction) {
+ if (instruction->IsIntConstant()) {
+ return ValueBound(nullptr, instruction->AsIntConstant()->GetValue());
+ }
+ HInstruction *left;
+ int32_t right;
+ if (IsAddOrSubAConstant(instruction, &left, &right)) {
+ return ValueBound(left, right);
+ }
+ return ValueBound(instruction, 0);
+ }
+
// Try to detect useful value bound format from an instruction, e.g.
// a constant or array length related value.
- static ValueBound DetectValueBoundFromValue(HInstruction* instruction, bool* found) {
+ static ValueBound DetectValueBoundFromValue(HInstruction* instruction, /* out */ bool* found) {
DCHECK(instruction != nullptr);
if (instruction->IsIntConstant()) {
*found = true;
@@ -227,7 +241,7 @@
// Add a constant to a ValueBound.
// `overflow` or `underflow` will return whether the resulting bound may
// overflow or underflow an int.
- ValueBound Add(int32_t c, bool* overflow, bool* underflow) const {
+ ValueBound Add(int32_t c, /* out */ bool* overflow, /* out */ bool* underflow) const {
*overflow = *underflow = false;
if (c == 0) {
return *this;
@@ -488,10 +502,10 @@
// the deoptimization technique.
static constexpr size_t kThresholdForAddingDeoptimize = 2;
- // Very large constant index is considered as an anomaly. This is a threshold
- // beyond which we don't bother to apply the deoptimization technique since
- // it's likely some AIOOBE will be thrown.
- static constexpr int32_t kMaxConstantForAddingDeoptimize =
+ // Very large lengths are considered an anomaly. This is a threshold beyond which we don't
+ // bother to apply the deoptimization technique since it's likely, or sometimes certain,
+ // an AIOOBE will be thrown.
+ static constexpr uint32_t kMaxLengthForAddingDeoptimize =
std::numeric_limits<int32_t>::max() - 1024 * 1024;
// Added blocks for loop body entry test.
@@ -508,7 +522,7 @@
std::less<int>(),
graph->GetArena()->Adapter(kArenaAllocBoundsCheckElimination)),
graph->GetArena()->Adapter(kArenaAllocBoundsCheckElimination)),
- first_constant_index_bounds_check_map_(
+ first_index_bounds_check_map_(
std::less<int>(),
graph->GetArena()->Adapter(kArenaAllocBoundsCheckElimination)),
early_exit_loop_(
@@ -518,23 +532,16 @@
std::less<uint32_t>(),
graph->GetArena()->Adapter(kArenaAllocBoundsCheckElimination)),
finite_loop_(graph->GetArena()->Adapter(kArenaAllocBoundsCheckElimination)),
- need_to_revisit_block_(false),
- has_deoptimization_on_constant_subscripts_(false),
+ has_dom_based_dynamic_bce_(false),
initial_block_size_(graph->GetBlocks().size()),
side_effects_(side_effects),
induction_range_(induction_analysis) {}
void VisitBasicBlock(HBasicBlock* block) OVERRIDE {
DCHECK(!IsAddedBlock(block));
- first_constant_index_bounds_check_map_.clear();
+ first_index_bounds_check_map_.clear();
HGraphVisitor::VisitBasicBlock(block);
- if (need_to_revisit_block_) {
- AddComparesWithDeoptimization(block);
- need_to_revisit_block_ = false;
- first_constant_index_bounds_check_map_.clear();
- GetValueRangeMap(block)->clear();
- HGraphVisitor::VisitBasicBlock(block);
- }
+ AddComparesWithDeoptimization(block);
}
void Finish() {
@@ -555,8 +562,7 @@
// Added blocks don't keep value ranges.
return nullptr;
}
- uint32_t block_id = basic_block->GetBlockId();
- return &maps_[block_id];
+ return &maps_[basic_block->GetBlockId()];
}
// Traverse up the dominator tree to look for value range info.
@@ -576,6 +582,11 @@
return nullptr;
}
+ // Helper method to assign a new range to an instruction in given basic block.
+ void AssignRange(HBasicBlock* basic_block, HInstruction* instruction, ValueRange* range) {
+ GetValueRangeMap(basic_block)->Overwrite(instruction->GetId(), range);
+ }
+
// 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,
@@ -583,7 +594,7 @@
ValueRange* existing_range = LookupValueRange(instruction, basic_block);
if (existing_range == nullptr) {
if (range != nullptr) {
- GetValueRangeMap(successor)->Overwrite(instruction->GetId(), range);
+ AssignRange(successor, instruction, range);
}
return;
}
@@ -595,8 +606,7 @@
return;
}
}
- ValueRange* narrowed_range = existing_range->Narrow(range);
- GetValueRangeMap(successor)->Overwrite(instruction->GetId(), narrowed_range);
+ AssignRange(successor, instruction, existing_range->Narrow(range));
}
// Special case that we may simultaneously narrow two MonotonicValueRange's to
@@ -778,37 +788,37 @@
array_length->IsPhi());
bool try_dynamic_bce = true;
+ // Analyze index range.
if (!index->IsIntConstant()) {
- // Non-constant subscript.
+ // Non-constant index.
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 dominator-based analysis.
+ // Try index range obtained by dominator-based analysis.
ValueRange* index_range = LookupValueRange(index, block);
if (index_range != nullptr && index_range->FitsIn(&array_range)) {
ReplaceInstruction(bounds_check, index);
return;
}
- // Try range obtained by induction variable analysis.
+ // Try index range obtained by induction variable analysis.
// Disables dynamic bce if OOB is certain.
if (InductionRangeFitsIn(&array_range, bounds_check, index, &try_dynamic_bce)) {
ReplaceInstruction(bounds_check, index);
return;
}
} else {
- // Constant subscript.
+ // Constant index.
int32_t constant = index->AsIntConstant()->GetValue();
if (constant < 0) {
// Will always throw exception.
return;
- }
- if (array_length->IsIntConstant()) {
+ } else if (array_length->IsIntConstant()) {
if (constant < array_length->AsIntConstant()->GetValue()) {
ReplaceInstruction(bounds_check, index);
}
return;
}
-
+ // Analyze array length range.
DCHECK(array_length->IsArrayLength());
ValueRange* existing_range = LookupValueRange(array_length, block);
if (existing_range != nullptr) {
@@ -823,37 +833,35 @@
// bounds check.
}
}
-
- if (first_constant_index_bounds_check_map_.find(array_length->GetId()) ==
- first_constant_index_bounds_check_map_.end()) {
- // Remember the first bounds check against array_length of a constant index.
- // That bounds check instruction has an associated HEnvironment where we
- // may add an HDeoptimize to eliminate bounds checks of constant indices
- // against array_length.
- first_constant_index_bounds_check_map_.Put(array_length->GetId(), bounds_check);
- } else {
- // We've seen it at least twice. It's beneficial to introduce a compare with
- // deoptimization fallback to eliminate the bounds checks.
- need_to_revisit_block_ = true;
- }
-
// Once we have an array access like 'array[5] = 1', we record array.length >= 6.
// We currently don't do it for non-constant index since a valid array[i] can't prove
// a valid array[i-1] yet due to the lower bound side.
if (constant == std::numeric_limits<int32_t>::max()) {
// Max() as an index will definitely throw AIOOBE.
return;
+ } else {
+ ValueBound lower = ValueBound(nullptr, constant + 1);
+ ValueBound upper = ValueBound::Max();
+ ValueRange* range = new (GetGraph()->GetArena())
+ ValueRange(GetGraph()->GetArena(), lower, upper);
+ AssignRange(block, array_length, range);
}
- ValueBound lower = ValueBound(nullptr, constant + 1);
- ValueBound upper = ValueBound::Max();
- ValueRange* range = new (GetGraph()->GetArena())
- ValueRange(GetGraph()->GetArena(), lower, upper);
- GetValueRangeMap(block)->Overwrite(array_length->GetId(), range);
}
// If static analysis fails, and OOB is not certain, try dynamic elimination.
if (try_dynamic_bce) {
- TryDynamicBCE(bounds_check);
+ // Try loop-based dynamic elimination.
+ if (TryDynamicBCE(bounds_check)) {
+ return;
+ }
+ // Prepare dominator-based dynamic elimination.
+ if (first_index_bounds_check_map_.find(array_length->GetId()) ==
+ first_index_bounds_check_map_.end()) {
+ // Remember the first bounds check against each array_length. That bounds check
+ // instruction has an associated HEnvironment where we may add an HDeoptimize
+ // to eliminate subsequent bounds checks against the same array_length.
+ first_index_bounds_check_map_.Put(array_length->GetId(), bounds_check);
+ }
}
}
@@ -914,7 +922,7 @@
increment,
bound);
}
- GetValueRangeMap(phi->GetBlock())->Overwrite(phi->GetId(), range);
+ AssignRange(phi->GetBlock(), phi, range);
}
}
}
@@ -942,7 +950,7 @@
}
ValueRange* range = left_range->Add(right->AsIntConstant()->GetValue());
if (range != nullptr) {
- GetValueRangeMap(add->GetBlock())->Overwrite(add->GetId(), range);
+ AssignRange(add->GetBlock(), add, range);
}
}
}
@@ -957,7 +965,7 @@
}
ValueRange* range = left_range->Add(-right->AsIntConstant()->GetValue());
if (range != nullptr) {
- GetValueRangeMap(sub->GetBlock())->Overwrite(sub->GetId(), range);
+ AssignRange(sub->GetBlock(), sub, range);
return;
}
}
@@ -997,7 +1005,7 @@
GetGraph()->GetArena(),
ValueBound(nullptr, right_const - upper.GetConstant()),
ValueBound(array_length, right_const - lower.GetConstant()));
- GetValueRangeMap(sub->GetBlock())->Overwrite(sub->GetId(), range);
+ AssignRange(sub->GetBlock(), sub, range);
}
}
}
@@ -1045,7 +1053,7 @@
GetGraph()->GetArena(),
ValueBound(nullptr, std::numeric_limits<int32_t>::min()),
ValueBound(left, 0));
- GetValueRangeMap(instruction->GetBlock())->Overwrite(instruction->GetId(), range);
+ AssignRange(instruction->GetBlock(), instruction, range);
}
}
@@ -1071,7 +1079,7 @@
GetGraph()->GetArena(),
ValueBound(nullptr, 0),
ValueBound(nullptr, constant));
- GetValueRangeMap(instruction->GetBlock())->Overwrite(instruction->GetId(), range);
+ AssignRange(instruction->GetBlock(), instruction, range);
}
}
}
@@ -1095,30 +1103,11 @@
if (existing_range != nullptr) {
range = existing_range->Narrow(range);
}
- GetValueRangeMap(new_array->GetBlock())->Overwrite(left->GetId(), range);
+ AssignRange(new_array->GetBlock(), left, range);
}
}
}
- void VisitDeoptimize(HDeoptimize* deoptimize) OVERRIDE {
- if (!deoptimize->InputAt(0)->IsLessThanOrEqual()) {
- return;
- }
- // If this instruction was added by AddCompareWithDeoptimization(), narrow
- // the range accordingly in subsequent basic blocks.
- HLessThanOrEqual* less_than_or_equal = deoptimize->InputAt(0)->AsLessThanOrEqual();
- HInstruction* instruction = less_than_or_equal->InputAt(0);
- if (instruction->IsArrayLength()) {
- HInstruction* constant = less_than_or_equal->InputAt(1);
- DCHECK(constant->IsIntConstant());
- DCHECK(constant->AsIntConstant()->GetValue() <= kMaxConstantForAddingDeoptimize);
- ValueBound lower = ValueBound(nullptr, constant->AsIntConstant()->GetValue() + 1);
- ValueRange* range = new (GetGraph()->GetArena())
- ValueRange(GetGraph()->GetArena(), lower, ValueBound::Max());
- GetValueRangeMap(deoptimize->GetBlock())->Overwrite(instruction->GetId(), range);
- }
- }
-
/**
* After null/bounds checks are eliminated, some invariant array references
* may be exposed underneath which can be hoisted out of the loop to the
@@ -1130,13 +1119,12 @@
* a[i][j] = 0; --a[i]--+
* }
*
- * Note: this optimization is no longer applied after deoptimization on array references
- * with constant subscripts has occurred (see AddCompareWithDeoptimization()), since in
- * those cases it would be unsafe to hoist array references across their deoptimization
- * instruction inside a loop.
+ * Note: this optimization is no longer applied after dominator-based dynamic deoptimization
+ * has occurred (see AddCompareWithDeoptimization()), since in those cases it would be
+ * unsafe to hoist array references across their deoptimization instruction inside a loop.
*/
void VisitArrayGet(HArrayGet* array_get) OVERRIDE {
- if (!has_deoptimization_on_constant_subscripts_ && array_get->IsInLoop()) {
+ if (!has_dom_based_dynamic_bce_ && array_get->IsInLoop()) {
HLoopInformation* loop = array_get->GetBlock()->GetLoopInformation();
if (loop->IsDefinedOutOfTheLoop(array_get->InputAt(0)) &&
loop->IsDefinedOutOfTheLoop(array_get->InputAt(1))) {
@@ -1148,69 +1136,107 @@
}
}
- void AddCompareWithDeoptimization(HInstruction* array_length,
- HIntConstant* const_instr,
- HBasicBlock* block) {
- DCHECK(array_length->IsArrayLength());
- ValueRange* range = LookupValueRange(array_length, block);
- ValueBound lower_bound = range->GetLower();
- DCHECK(lower_bound.IsConstant());
- DCHECK(const_instr->GetValue() <= kMaxConstantForAddingDeoptimize);
- // Note that the lower bound of the array length may have been refined
- // through other instructions (such as `HNewArray(length - 4)`).
- DCHECK_LE(const_instr->GetValue() + 1, lower_bound.GetConstant());
-
- // If array_length is less than lower_const, deoptimize.
- HBoundsCheck* bounds_check = first_constant_index_bounds_check_map_.Get(
- array_length->GetId())->AsBoundsCheck();
- HCondition* cond = new (GetGraph()->GetArena()) HLessThanOrEqual(array_length, const_instr);
- HDeoptimize* deoptimize = new (GetGraph()->GetArena())
- HDeoptimize(cond, bounds_check->GetDexPc());
- block->InsertInstructionBefore(cond, bounds_check);
- block->InsertInstructionBefore(deoptimize, bounds_check);
- deoptimize->CopyEnvironmentFrom(bounds_check->GetEnvironment());
- // Flag that this kind of deoptimization on array references with constant
- // subscripts has occurred to prevent further hoisting of these references.
- has_deoptimization_on_constant_subscripts_ = true;
+ // Perform dominator-based dynamic elimination on suitable set of bounds checks.
+ void AddCompareWithDeoptimization(HBasicBlock* block,
+ HInstruction* array_length,
+ HInstruction* base,
+ int32_t min_c, int32_t max_c) {
+ HBoundsCheck* bounds_check =
+ first_index_bounds_check_map_.Get(array_length->GetId())->AsBoundsCheck();
+ // Construct deoptimization on single or double bounds on range [base-min_c,base+max_c],
+ // for example either for a[0]..a[3] just 3 or for a[base-1]..a[base+3] both base-1
+ // and base+3, since we made the assumption any in between value may occur too.
+ static_assert(kMaxLengthForAddingDeoptimize < std::numeric_limits<int32_t>::max(),
+ "Incorrect max length may be subject to arithmetic wrap-around");
+ HInstruction* upper = GetGraph()->GetIntConstant(max_c);
+ if (base == nullptr) {
+ DCHECK_GE(min_c, 0);
+ } else {
+ HInstruction* lower = new (GetGraph()->GetArena())
+ HAdd(Primitive::kPrimInt, base, GetGraph()->GetIntConstant(min_c));
+ upper = new (GetGraph()->GetArena()) HAdd(Primitive::kPrimInt, base, upper);
+ block->InsertInstructionBefore(lower, bounds_check);
+ block->InsertInstructionBefore(upper, bounds_check);
+ InsertDeoptInBlock(bounds_check, new (GetGraph()->GetArena()) HAbove(lower, upper));
+ }
+ InsertDeoptInBlock(bounds_check, new (GetGraph()->GetArena()) HAboveOrEqual(upper, array_length));
+ // Flag that this kind of deoptimization has occurred.
+ has_dom_based_dynamic_bce_ = true;
}
+ // Attempt dominator-based dynamic elimination on remaining candidates.
void AddComparesWithDeoptimization(HBasicBlock* block) {
- for (ArenaSafeMap<int, HBoundsCheck*>::iterator it =
- first_constant_index_bounds_check_map_.begin();
- it != first_constant_index_bounds_check_map_.end();
- ++it) {
- HBoundsCheck* bounds_check = it->second;
+ for (const auto& it : first_index_bounds_check_map_) {
+ HBoundsCheck* bounds_check = it.second;
+ HInstruction* index = bounds_check->InputAt(0);
HInstruction* array_length = bounds_check->InputAt(1);
if (!array_length->IsArrayLength()) {
- // Prior deoptimizations may have changed the array length to a phi.
- // TODO(mingyao): propagate the range to the phi?
- DCHECK(array_length->IsPhi()) << array_length->DebugName();
- continue;
+ continue; // disregard phis and constants
}
- HIntConstant* lower_bound_const_instr = nullptr;
- int32_t lower_bound_const = std::numeric_limits<int32_t>::min();
- size_t counter = 0;
- // Count the constant indexing for which bounds checks haven't
- // been removed yet.
- for (HUseIterator<HInstruction*> it2(array_length->GetUses());
- !it2.Done();
- it2.Advance()) {
+ // Collect all bounds checks are still there and that are related as "a[base + constant]"
+ // for a base instruction (possibly absent) and various constants. Note that no attempt
+ // is made to partition the set into matching subsets (viz. a[0], a[1] and a[base+1] and
+ // a[base+2] are considered as one set).
+ // TODO: would such a partitioning be worthwhile?
+ ValueBound value = ValueBound::AsValueBound(index);
+ HInstruction* base = value.GetInstruction();
+ int32_t min_c = base == nullptr ? 0 : value.GetConstant();
+ int32_t max_c = value.GetConstant();
+ ArenaVector<HBoundsCheck*> candidates(
+ GetGraph()->GetArena()->Adapter(kArenaAllocBoundsCheckElimination));
+ ArenaVector<HBoundsCheck*> standby(
+ GetGraph()->GetArena()->Adapter(kArenaAllocBoundsCheckElimination));
+ for (HUseIterator<HInstruction*> it2(array_length->GetUses()); !it2.Done(); it2.Advance()) {
+ // Another bounds check in same or dominated block?
HInstruction* user = it2.Current()->GetUser();
- if (user->GetBlock() == block &&
- user->IsBoundsCheck() &&
- user->AsBoundsCheck()->InputAt(0)->IsIntConstant()) {
- DCHECK_EQ(array_length, user->AsBoundsCheck()->InputAt(1));
- HIntConstant* const_instr = user->AsBoundsCheck()->InputAt(0)->AsIntConstant();
- if (const_instr->GetValue() > lower_bound_const) {
- lower_bound_const = const_instr->GetValue();
- lower_bound_const_instr = const_instr;
+ HBasicBlock* other_block = user->GetBlock();
+ if (user->IsBoundsCheck() && block->Dominates(other_block)) {
+ HBoundsCheck* other_bounds_check = user->AsBoundsCheck();
+ HInstruction* other_index = other_bounds_check->InputAt(0);
+ HInstruction* other_array_length = other_bounds_check->InputAt(1);
+ ValueBound other_value = ValueBound::AsValueBound(other_index);
+ if (array_length == other_array_length && base == other_value.GetInstruction()) {
+ int32_t other_c = other_value.GetConstant();
+ // Since a subsequent dominated block could be under a conditional, only accept
+ // the other bounds check if it is in same block or both blocks dominate the exit.
+ // TODO: we could improve this by testing proper post-dominance, or even if this
+ // constant is seen along *all* conditional paths that follow.
+ HBasicBlock* exit = GetGraph()->GetExitBlock();
+ if (block == user->GetBlock() ||
+ (block->Dominates(exit) && other_block->Dominates(exit))) {
+ min_c = std::min(min_c, other_c);
+ max_c = std::max(max_c, other_c);
+ candidates.push_back(other_bounds_check);
+ } else {
+ // Add this candidate later only if it falls into the range.
+ standby.push_back(other_bounds_check);
+ }
}
- counter++;
}
}
- if (counter >= kThresholdForAddingDeoptimize &&
- lower_bound_const_instr->GetValue() <= kMaxConstantForAddingDeoptimize) {
- AddCompareWithDeoptimization(array_length, lower_bound_const_instr, block);
+ // Add standby candidates that fall in selected range.
+ for (size_t i = 0; i < standby.size(); ++i) {
+ HBoundsCheck* other_bounds_check = standby[i]->AsBoundsCheck();
+ HInstruction* other_index = other_bounds_check->InputAt(0);
+ int32_t other_c = ValueBound::AsValueBound(other_index).GetConstant();
+ if (min_c <= other_c && other_c <= max_c) {
+ candidates.push_back(other_bounds_check);
+ }
+ }
+ // Perform dominator-based deoptimization if it seems profitable. Note that we reject cases
+ // where the distance min_c:max_c range gets close to the maximum possible array length,
+ // since those cases are likely to always deopt (such situations do not necessarily go
+ // OOB, though, since the programmer could rely on wrap-around from max to min).
+ size_t threshold = kThresholdForAddingDeoptimize + (base == nullptr ? 0 : 1); // extra test?
+ uint32_t distance = static_cast<uint32_t>(max_c) - static_cast<uint32_t>(min_c);
+ if (candidates.size() >= threshold &&
+ (base != nullptr || min_c >= 0) && // reject certain OOB
+ distance <= kMaxLengthForAddingDeoptimize) { // reject likely/certain deopt
+ AddCompareWithDeoptimization(block, array_length, base, min_c, max_c);
+ for (size_t i = 0; i < candidates.size(); ++i) {
+ HInstruction* other_bounds_check = candidates[i];
+ ReplaceInstruction(other_bounds_check, other_bounds_check->InputAt(0));
+ }
}
}
}
@@ -1259,7 +1285,7 @@
* deoptimization). If no deoptimization occurs, the loop is executed with all corresponding
* bounds checks and related null checks removed.
*/
- void TryDynamicBCE(HBoundsCheck* instruction) {
+ bool TryDynamicBCE(HBoundsCheck* instruction) {
HLoopInformation* loop = instruction->GetBlock()->GetLoopInformation();
HInstruction* index = instruction->InputAt(0);
HInstruction* length = instruction->InputAt(1);
@@ -1285,11 +1311,13 @@
HBasicBlock* block = GetPreHeader(loop, instruction);
induction_range_.GenerateRangeCode(instruction, index, GetGraph(), block, &lower, &upper);
if (lower != nullptr) {
- InsertDeopt(loop, block, new (GetGraph()->GetArena()) HAbove(lower, upper));
+ InsertDeoptInLoop(loop, block, new (GetGraph()->GetArena()) HAbove(lower, upper));
}
- InsertDeopt(loop, block, new (GetGraph()->GetArena()) HAboveOrEqual(upper, length));
+ InsertDeoptInLoop(loop, block, new (GetGraph()->GetArena()) HAboveOrEqual(upper, length));
ReplaceInstruction(instruction, index);
+ return true;
}
+ return false;
}
/**
@@ -1382,7 +1410,7 @@
HBasicBlock* block = GetPreHeader(loop, check);
HInstruction* cond =
new (GetGraph()->GetArena()) HEqual(array, GetGraph()->GetNullConstant());
- InsertDeopt(loop, block, cond);
+ InsertDeoptInLoop(loop, block, cond);
ReplaceInstruction(check, array);
return true;
}
@@ -1448,8 +1476,8 @@
return loop->GetPreHeader();
}
- /** Inserts a deoptimization test. */
- void InsertDeopt(HLoopInformation* loop, HBasicBlock* block, HInstruction* condition) {
+ /** Inserts a deoptimization test in a loop preheader. */
+ void InsertDeoptInLoop(HLoopInformation* loop, HBasicBlock* block, HInstruction* condition) {
HInstruction* suspend = loop->GetSuspendCheck();
block->InsertInstructionBefore(condition, block->GetLastInstruction());
HDeoptimize* deoptimize =
@@ -1461,6 +1489,16 @@
}
}
+ /** Inserts a deoptimization test right before a bounds check. */
+ void InsertDeoptInBlock(HBoundsCheck* bounds_check, HInstruction* condition) {
+ HBasicBlock* block = bounds_check->GetBlock();
+ block->InsertInstructionBefore(condition, bounds_check);
+ HDeoptimize* deoptimize =
+ new (GetGraph()->GetArena()) HDeoptimize(condition, bounds_check->GetDexPc());
+ block->InsertInstructionBefore(deoptimize, bounds_check);
+ deoptimize->CopyEnvironmentFrom(bounds_check->GetEnvironment());
+ }
+
/** Hoists instruction out of the loop to preheader or deoptimization block. */
void HoistToPreHeaderOrDeoptBlock(HLoopInformation* loop, HInstruction* instruction) {
HBasicBlock* block = GetPreHeader(loop, instruction);
@@ -1628,9 +1666,9 @@
// A set of maps, one per basic block, from instruction to range.
ArenaVector<ArenaSafeMap<int, ValueRange*>> maps_;
- // Map an HArrayLength instruction's id to the first HBoundsCheck instruction in
- // a block that checks a constant index against that HArrayLength.
- ArenaSafeMap<int, HBoundsCheck*> first_constant_index_bounds_check_map_;
+ // Map an HArrayLength instruction's id to the first HBoundsCheck instruction
+ // in a block that checks an index against that HArrayLength.
+ ArenaSafeMap<int, HBoundsCheck*> first_index_bounds_check_map_;
// Early-exit loop bookkeeping.
ArenaSafeMap<uint32_t, bool> early_exit_loop_;
@@ -1641,15 +1679,8 @@
// Finite loop bookkeeping.
ArenaSet<uint32_t> finite_loop_;
- // For the block, there is at least one HArrayLength instruction for which there
- // is more than one bounds check instruction with constant indexing. And it's
- // beneficial to add a compare instruction that has deoptimization fallback and
- // eliminate those bounds checks.
- bool need_to_revisit_block_;
-
- // Flag that denotes whether deoptimization has occurred on array references
- // with constant subscripts (see AddCompareWithDeoptimization()).
- bool has_deoptimization_on_constant_subscripts_;
+ // Flag that denotes whether dominator-based dynamic elimination has occurred.
+ bool has_dom_based_dynamic_bce_;
// Initial number of blocks.
uint32_t initial_block_size_;
diff --git a/test/449-checker-bce/src/Main.java b/test/449-checker-bce/src/Main.java
index 8f9a32a..31bb94c 100644
--- a/test/449-checker-bce/src/Main.java
+++ b/test/449-checker-bce/src/Main.java
@@ -122,8 +122,9 @@
/// CHECK: ArraySet
static void constantIndexing1(int[] array) {
- array[5] = 1;
- array[4] = 1;
+ // Decreasing order: bc for 5 but not for 4.
+ array[5] = 11;
+ array[4] = 11;
}
@@ -136,17 +137,18 @@
/// CHECK: ArraySet
/// CHECK: BoundsCheck
/// CHECK: ArraySet
+ /// CHECK: BoundsCheck
+ /// CHECK: ArraySet
/// CHECK-START: void Main.$opt$noinline$constantIndexing2(int[]) BCE (after)
- /// CHECK: LessThanOrEqual
- /// CHECK: Deoptimize
- /// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
+ /// CHECK: BoundsCheck
/// CHECK: ArraySet
- /// CHECK-NOT: BoundsCheck
+ /// CHECK: BoundsCheck
/// CHECK: ArraySet
- /// CHECK-NOT: BoundsCheck
+ /// CHECK: BoundsCheck
/// CHECK: ArraySet
- /// CHECK-NOT: BoundsCheck
+ /// CHECK: BoundsCheck
/// CHECK: ArraySet
/// CHECK: BoundsCheck
/// CHECK: ArraySet
@@ -156,12 +158,39 @@
array[2] = 1;
array[3] = 1;
array[4] = 1;
- array[-1] = 1;
+ array[-1] = 1; // prevents the whole opt on [-1:4]
if (array[1] == 1) {
throw new Error("");
}
}
+ /// CHECK-START: void Main.constantIndexing2b(int[]) BCE (before)
+ /// CHECK: BoundsCheck
+ /// CHECK: ArraySet
+ /// CHECK: BoundsCheck
+ /// CHECK: ArraySet
+ /// CHECK: BoundsCheck
+ /// CHECK: ArraySet
+ /// CHECK: BoundsCheck
+ /// CHECK: ArraySet
+
+ /// CHECK-START: void Main.constantIndexing2b(int[]) BCE (after)
+ /// CHECK: Deoptimize
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK: ArraySet
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK: ArraySet
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK: ArraySet
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK: ArraySet
+
+ static void constantIndexing2b(int[] array) {
+ array[0] = 7;
+ array[1] = 7;
+ array[2] = 7;
+ array[3] = 7;
+ }
/// CHECK-START: int[] Main.constantIndexing3(int[], int[], boolean) BCE (before)
/// CHECK: BoundsCheck
@@ -182,11 +211,9 @@
/// CHECK: ArraySet
/// CHECK-START: int[] Main.constantIndexing3(int[], int[], boolean) BCE (after)
- /// CHECK: LessThanOrEqual
/// CHECK: Deoptimize
/// CHECK-NOT: BoundsCheck
/// CHECK: ArrayGet
- /// CHECK: LessThanOrEqual
/// CHECK: Deoptimize
/// CHECK-NOT: BoundsCheck
/// CHECK: ArraySet
@@ -220,14 +247,14 @@
/// CHECK: ArraySet
/// CHECK-START: void Main.constantIndexing4(int[]) BCE (after)
- /// CHECK-NOT: LessThanOrEqual
+ /// CHECK-NOT: Deoptimize
/// CHECK: BoundsCheck
/// CHECK: ArraySet
// There is only one array access. It's not beneficial
// to create a compare with deoptimization instruction.
static void constantIndexing4(int[] array) {
- array[0] = 1;
+ array[0] = -1;
}
@@ -260,10 +287,221 @@
/// CHECK-START: void Main.constantIndexing6(int[]) BCE (after)
/// CHECK: Deoptimize
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK: ArraySet
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK: ArraySet
static void constantIndexing6(int[] array) {
- array[3] = 1;
- array[4] = 1;
+ array[3] = 111;
+ array[4] = 111;
+ }
+
+ /// CHECK-START: void Main.constantIndexing7(int[], int) BCE (before)
+ /// CHECK: BoundsCheck
+ /// CHECK: ArraySet
+ /// CHECK: BoundsCheck
+ /// CHECK: ArraySet
+ /// CHECK: BoundsCheck
+ /// CHECK: ArraySet
+ /// CHECK: BoundsCheck
+ /// CHECK: ArraySet
+
+ /// CHECK-START: void Main.constantIndexing7(int[], int) BCE (after)
+ /// CHECK: Deoptimize
+ /// CHECK: Deoptimize
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK: ArraySet
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK: ArraySet
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK: ArraySet
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK: ArraySet
+
+ static void constantIndexing7(int[] array, int base) {
+ // With constant offsets to symbolic base.
+ array[base] = 10;
+ array[base + 1] = 20;
+ array[base + 2] = 30;
+ array[base + 3] = 40;
+ }
+
+ /// CHECK-START: void Main.constantIndexing8(int[], int) BCE (before)
+ /// CHECK: BoundsCheck
+ /// CHECK: ArraySet
+ /// CHECK: BoundsCheck
+ /// CHECK: ArraySet
+ /// CHECK: BoundsCheck
+ /// CHECK: ArraySet
+ /// CHECK: BoundsCheck
+ /// CHECK: ArraySet
+
+ /// CHECK-START: void Main.constantIndexing8(int[], int) BCE (after)
+ /// CHECK: Deoptimize
+ /// CHECK: Deoptimize
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK: ArraySet
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK: ArraySet
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK: ArraySet
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK: ArraySet
+
+ static void constantIndexing8(int[] array, int base) {
+ // With constant offsets "both ways" to symbolic base.
+ array[base - 1] = 100;
+ array[base] = 200;
+ array[base + 1] = 300;
+ array[base + 2] = 400;
+ }
+
+ /// CHECK-START: void Main.constantIndexing9(int[], int) BCE (before)
+ /// CHECK: BoundsCheck
+ /// CHECK: ArraySet
+ /// CHECK: BoundsCheck
+ /// CHECK: ArraySet
+ /// CHECK: BoundsCheck
+ /// CHECK: ArraySet
+ /// CHECK: BoundsCheck
+ /// CHECK: ArraySet
+
+ /// CHECK-START: void Main.constantIndexing9(int[], int) BCE (after)
+ /// CHECK: Deoptimize
+ /// CHECK: Deoptimize
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK: ArraySet
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK: ArraySet
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK: ArraySet
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK: ArraySet
+ /// CHECK-NOT: BoundsCheck
+
+ static void constantIndexing9(int[] array, int base) {
+ // Final range is base..base+3 so conditional
+ // references may be included in the end.
+ array[base] = 0;
+ if (base != 12345)
+ array[base + 2] = 2;
+ array[base + 3] = 3;
+ if (base != 67890)
+ array[base + 1] = 1;
+ }
+
+ static void runAllConstantIndices() {
+ int[] a1 = { 0 };
+ int[] a6 = { 0, 0, 0, 0, 0, 0 };
+
+ boolean caught = false;
+ try {
+ constantIndexing1(a1);
+ } catch (ArrayIndexOutOfBoundsException e) {
+ caught = true;
+ }
+ if (!caught) {
+ System.out.println("constant indices 1 failed!");
+ }
+
+ constantIndexing1(a6);
+ if (a6[4] != 11 || a6[5] != 11) {
+ System.out.println("constant indices 1 failed!");
+ }
+
+ caught = false;
+ try {
+ $opt$noinline$constantIndexing2(a6);
+ } catch (ArrayIndexOutOfBoundsException e) {
+ caught = true;
+ }
+ if (!caught || a6[0] != 0 || a6[1] != 1 || a6[2] != 1 ||
+ a6[3] != 1 || a6[4] != 1 || a6[5] != 11) {
+ System.out.println("constant indices 2 failed!");
+ }
+
+ caught = false;
+ try {
+ constantIndexing2b(a1);
+ } catch (ArrayIndexOutOfBoundsException e) {
+ caught = true;
+ }
+ if (!caught || a1[0] != 7) {
+ System.out.println("constant indices 2b failed!");
+ }
+
+ constantIndexing2b(a6);
+ if (a6[0] != 7 || a6[1] != 7 || a6[2] != 7 ||
+ a6[3] != 7 || a6[4] != 1 || a6[5] != 11) {
+ System.out.println("constant indices 2b failed!");
+ }
+
+ int[] b4 = new int[4];
+ constantIndexing3(a6, b4, true);
+ if (b4[0] != 7 || b4[1] != 7 || b4[2] != 7 || b4[3] != 7) {
+ System.out.println("constant indices 3 failed!");
+ }
+
+ constantIndexing4(a1);
+ if (a1[0] != -1) {
+ System.out.println("constant indices 4 failed!");
+ }
+
+ caught = false;
+ try {
+ constantIndexing5(a6);
+ } catch (ArrayIndexOutOfBoundsException e) {
+ caught = true;
+ }
+ if (!caught) {
+ System.out.println("constant indices 5 failed!");
+ }
+
+ constantIndexing6(a6);
+ if (a6[0] != 7 || a6[1] != 7 || a6[2] != 7 ||
+ a6[3] != 111 || a6[4] != 111 || a6[5] != 11) {
+ System.out.println("constant indices 6 failed!");
+ }
+
+ constantIndexing7(a6, 1);
+ if (a6[0] != 7 || a6[1] != 10 || a6[2] != 20 ||
+ a6[3] != 30 || a6[4] != 40 || a6[5] != 11) {
+ System.out.println("constant indices 7 failed!");
+ }
+
+ caught = false;
+ try {
+ constantIndexing7(a6, 5);
+ } catch (ArrayIndexOutOfBoundsException e) {
+ caught = true;
+ }
+ if (!caught || a6[0] != 7 || a6[1] != 10 || a6[2] != 20 ||
+ a6[3] != 30 || a6[4] != 40 || a6[5] != 10) {
+ System.out.println("constant indices 7 failed!");
+ }
+
+ constantIndexing8(a6, 1);
+ if (a6[0] != 100 || a6[1] != 200 || a6[2] != 300 ||
+ a6[3] != 400 || a6[4] != 40 || a6[5] != 10) {
+ System.out.println("constant indices 8 failed!");
+ }
+
+ caught = false;
+ try {
+ constantIndexing8(a6, 0);
+ } catch (ArrayIndexOutOfBoundsException e) {
+ caught = true;
+ }
+ if (!caught || a6[0] != 100) {
+ System.out.println("constant indices 8 failed!");
+ }
+
+ constantIndexing9(a6, 0);
+ if (a6[0] != 0 || a6[1] != 1 || a6[2] != 2 ||
+ a6[3] != 3 || a6[4] != 40 || a6[5] != 10) {
+ System.out.println("constant indices 9 failed!");
+ }
}
// A helper into which the actual throwing function should be inlined.
@@ -1102,6 +1340,9 @@
static void testUnknownBounds() {
boolean caught = false;
+
+ runAllConstantIndices();
+
Main main = new Main();
main.foo1(new int[10], 0, 10, false);
if (main.sum != 10) {
