Deoptimization-based bce.
A mechanism is introduced that a runtime method can be called
from code compiled with optimizing compiler to deoptimize into
interpreter. This can be used to establish invariants in the managed code
If the invariant does not hold at runtime, we will deoptimize and continue
execution in the interpreter. This allows to optimize the managed code as
if the invariant was proven during compile time. However, the exception
will be thrown according to the semantics demanded by the spec.
The invariant and optimization included in this patch are based on the
length of an array. Given a set of array accesses with constant indices
{c1, ..., cn}, we can optimize away all bounds checks iff all 0 <= min(ci) and
max(ci) < array-length. The first can be proven statically. The second can be
established with a deoptimization-based invariant. This replaces n bounds
checks with one invariant check (plus slow-path code).
Change-Id: I8c6e34b56c85d25b91074832d13dba1db0a81569
diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index 1d16794..7444f6e 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -443,9 +443,31 @@
class BCEVisitor : public HGraphVisitor {
public:
+ // The least number of bounds checks that should be eliminated by triggering
+ // 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 = INT_MAX - 1024 * 1024;
+
explicit BCEVisitor(HGraph* graph)
: HGraphVisitor(graph),
- maps_(graph->GetBlocks().Size()) {}
+ maps_(graph->GetBlocks().Size()),
+ need_to_revisit_block_(false) {}
+
+ void VisitBasicBlock(HBasicBlock* block) OVERRIDE {
+ first_constant_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);
+ }
+ }
private:
// Return the map of proven value ranges at the beginning of a basic block.
@@ -701,9 +723,26 @@
}
}
+ 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 == INT_MAX) {
+ // INT_MAX as an index will definitely throw AIOOBE.
+ return;
+ }
ValueBound lower = ValueBound(nullptr, constant + 1);
ValueBound upper = ValueBound::Max();
ValueRange* range = new (GetGraph()->GetArena())
@@ -938,8 +977,90 @@
}
}
+ void VisitDeoptimize(HDeoptimize* deoptimize) {
+ // Right now it's only HLessThanOrEqual.
+ DCHECK(deoptimize->InputAt(0)->IsLessThanOrEqual());
+ 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() != INT_MAX);
+ 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);
+ }
+ }
+
+ 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);
+ DCHECK_EQ(lower_bound.GetConstant(), const_instr->GetValue() + 1);
+
+ // 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->SetEnvironment(bounds_check->GetEnvironment());
+ }
+
+ 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;
+ HArrayLength* array_length = bounds_check->InputAt(1)->AsArrayLength();
+ HIntConstant* lower_bound_const_instr = nullptr;
+ int32_t lower_bound_const = INT_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()) {
+ 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;
+ }
+ counter++;
+ }
+ }
+ if (counter >= kThresholdForAddingDeoptimize &&
+ lower_bound_const_instr->GetValue() <= kMaxConstantForAddingDeoptimize) {
+ AddCompareWithDeoptimization(array_length, lower_bound_const_instr, block);
+ }
+ }
+ }
+
std::vector<std::unique_ptr<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.
+ SafeMap<int, HBoundsCheck*> first_constant_index_bounds_check_map_;
+
+ // 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_;
+
DISALLOW_COPY_AND_ASSIGN(BCEVisitor);
};