diff options
Diffstat (limited to 'compiler/optimizing')
| -rw-r--r-- | compiler/optimizing/bounds_check_elimination.cc | 337 |
1 files changed, 184 insertions, 153 deletions
diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc index c307522f2b..c694ea8118 100644 --- a/compiler/optimizing/bounds_check_elimination.cc +++ b/compiler/optimizing/bounds_check_elimination.cc @@ -63,9 +63,10 @@ class ValueBound : public ValueObject { 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 @@ class ValueBound : public ValueObject { 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 @@ class ValueBound : public ValueObject { // 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 @@ class BCEVisitor : public HGraphVisitor { // 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 @@ class BCEVisitor : public HGraphVisitor { 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 @@ class BCEVisitor : public HGraphVisitor { 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 @@ class BCEVisitor : public HGraphVisitor { // 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 @@ class BCEVisitor : public HGraphVisitor { 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 @@ class BCEVisitor : public HGraphVisitor { 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 @@ class BCEVisitor : public HGraphVisitor { 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 @@ class BCEVisitor : public HGraphVisitor { 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 @@ class BCEVisitor : public HGraphVisitor { // 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 @@ class BCEVisitor : public HGraphVisitor { increment, bound); } - GetValueRangeMap(phi->GetBlock())->Overwrite(phi->GetId(), range); + AssignRange(phi->GetBlock(), phi, range); } } } @@ -942,7 +950,7 @@ class BCEVisitor : public HGraphVisitor { } 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 @@ class BCEVisitor : public HGraphVisitor { } 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 @@ class BCEVisitor : public HGraphVisitor { 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 @@ class BCEVisitor : public HGraphVisitor { 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 @@ class BCEVisitor : public HGraphVisitor { GetGraph()->GetArena(), ValueBound(nullptr, 0), ValueBound(nullptr, constant)); - GetValueRangeMap(instruction->GetBlock())->Overwrite(instruction->GetId(), range); + AssignRange(instruction->GetBlock(), instruction, range); } } } @@ -1095,30 +1103,11 @@ class BCEVisitor : public HGraphVisitor { 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 @@ class BCEVisitor : public HGraphVisitor { * 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 @@ class BCEVisitor : public HGraphVisitor { } } - 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 @@ class BCEVisitor : public HGraphVisitor { * 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 @@ class BCEVisitor : public HGraphVisitor { 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 @@ class BCEVisitor : public HGraphVisitor { 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 @@ class BCEVisitor : public HGraphVisitor { 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 @@ class BCEVisitor : public HGraphVisitor { } } + /** 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 @@ class BCEVisitor : public HGraphVisitor { // 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 @@ class BCEVisitor : public HGraphVisitor { // 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_; |