Deoptimization-based BCE for unknown loop bounds.
For loop like:
for (int i = start; i < end; i++) {
array[i] = 1;
}
We add the following to the loop pre-header:
if (start < 0) deoptimize();
if (end > array.length) deoptimize();
Then we can eliminate bounds-check of array[i] inside the loop.
We also take care of indexing with induction variable plus some offsets,
like array[i - 1]/array[i + 1] inside the loop, and adjust the condition
for deoptimization accordingly.
Change-Id: I9e24c6b5e134ff95eff5b5605ff8f95d6546616f
diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index 6511120..9faead5 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -246,6 +246,108 @@
int32_t constant_;
};
+// Collect array access data for a loop.
+// TODO: make it work for multiple arrays inside the loop.
+class ArrayAccessInsideLoopFinder : public ValueObject {
+ public:
+ explicit ArrayAccessInsideLoopFinder(HInstruction* induction_variable)
+ : induction_variable_(induction_variable),
+ found_array_length_(nullptr),
+ offset_low_(INT_MAX),
+ offset_high_(INT_MIN) {
+ Run();
+ }
+
+ HArrayLength* GetFoundArrayLength() const { return found_array_length_; }
+ bool HasFoundArrayLength() const { return found_array_length_ != nullptr; }
+ int32_t GetOffsetLow() const { return offset_low_; }
+ int32_t GetOffsetHigh() const { return offset_high_; }
+
+ void Run() {
+ HLoopInformation* loop_info = induction_variable_->GetBlock()->GetLoopInformation();
+ // Must be simplified loop.
+ DCHECK_EQ(loop_info->GetBackEdges().Size(), 1U);
+ // In order not to trigger deoptimization unnecessarily, make sure
+ // that all array accesses collected are really executed in the loop.
+ // For array accesses in a branch inside the loop, don't collect the
+ // access. The bounds check in that branch might not be eliminated.
+ for (HBasicBlock* block = loop_info->GetBackEdges().Get(0);
+ block != loop_info->GetPreHeader();
+ block = block->GetDominator()) {
+ for (HInstruction* instruction = block->GetFirstInstruction();
+ instruction != nullptr;
+ instruction = instruction->GetNext()) {
+ if (!instruction->IsArrayGet() && !instruction->IsArraySet()) {
+ continue;
+ }
+ HInstruction* index = instruction->InputAt(1);
+ if (!index->IsBoundsCheck()) {
+ continue;
+ }
+
+ HArrayLength* array_length = index->InputAt(1)->AsArrayLength();
+ if (array_length == nullptr) {
+ DCHECK(index->InputAt(1)->IsIntConstant());
+ // TODO: may optimize for constant case.
+ continue;
+ }
+
+ HInstruction* array = array_length->InputAt(0);
+ if (array->IsNullCheck()) {
+ array = array->AsNullCheck()->InputAt(0);
+ }
+ if (loop_info->Contains(*array->GetBlock())) {
+ // Array is defined inside the loop. Skip.
+ continue;
+ }
+
+ if (found_array_length_ != nullptr && found_array_length_ != array_length) {
+ // There is already access for another array recorded for the loop.
+ // TODO: handle multiple arrays.
+ continue;
+ }
+
+ index = index->AsBoundsCheck()->InputAt(0);
+ HInstruction* left = index;
+ int32_t right = 0;
+ if (left == induction_variable_ ||
+ (ValueBound::IsAddOrSubAConstant(index, &left, &right) &&
+ left == induction_variable_)) {
+ // For patterns like array[i] or array[i + 2].
+ if (right < offset_low_) {
+ offset_low_ = right;
+ }
+ if (right > offset_high_) {
+ offset_high_ = right;
+ }
+ } else {
+ // Access not in induction_variable/(induction_variable_ + constant)
+ // format. Skip.
+ continue;
+ }
+ // Record this array.
+ found_array_length_ = array_length;
+ }
+ }
+ }
+
+ private:
+ // The instruction that corresponds to a MonotonicValueRange.
+ HInstruction* induction_variable_;
+
+ // The array length of the array that's accessed inside the loop.
+ HArrayLength* found_array_length_;
+
+ // The lowest and highest constant offsets relative to induction variable
+ // instruction_ in all array accesses.
+ // If array access are: array[i-1], array[i], array[i+1],
+ // offset_low_ is -1 and offset_high is 1.
+ int32_t offset_low_;
+ int32_t offset_high_;
+
+ DISALLOW_COPY_AND_ASSIGN(ArrayAccessInsideLoopFinder);
+};
+
/**
* Represent a range of lower bound and upper bound, both being inclusive.
* Currently a ValueRange may be generated as a result of the following:
@@ -332,21 +434,31 @@
class MonotonicValueRange : public ValueRange {
public:
MonotonicValueRange(ArenaAllocator* allocator,
+ HPhi* induction_variable,
HInstruction* initial,
int32_t increment,
ValueBound bound)
// To be conservative, give it full range [INT_MIN, INT_MAX] in case it's
// used as a regular value range, due to possible overflow/underflow.
: ValueRange(allocator, ValueBound::Min(), ValueBound::Max()),
+ induction_variable_(induction_variable),
initial_(initial),
+ end_(nullptr),
+ inclusive_(false),
increment_(increment),
bound_(bound) {}
virtual ~MonotonicValueRange() {}
+ HInstruction* GetInductionVariable() const { return induction_variable_; }
int32_t GetIncrement() const { return increment_; }
-
ValueBound GetBound() const { return bound_; }
+ void SetEnd(HInstruction* end) { end_ = end; }
+ void SetInclusive(bool inclusive) { inclusive_ = inclusive; }
+ HBasicBlock* GetLoopHead() const {
+ DCHECK(induction_variable_->GetBlock()->IsLoopHeader());
+ return induction_variable_->GetBlock();
+ }
MonotonicValueRange* AsMonotonicValueRange() OVERRIDE { return this; }
@@ -371,6 +483,10 @@
if (increment_ > 0) {
// Monotonically increasing.
ValueBound lower = ValueBound::NarrowLowerBound(bound_, range->GetLower());
+ if (!lower.IsConstant() || lower.GetConstant() == INT_MIN) {
+ // Lower bound isn't useful. Leave it to deoptimization.
+ return this;
+ }
// We currently conservatively assume max array length is INT_MAX. If we can
// make assumptions about the max array length, e.g. due to the max heap size,
@@ -417,6 +533,11 @@
DCHECK_NE(increment_, 0);
// Monotonically decreasing.
ValueBound upper = ValueBound::NarrowUpperBound(bound_, range->GetUpper());
+ if ((!upper.IsConstant() || upper.GetConstant() == INT_MAX) &&
+ !upper.IsRelatedToArrayLength()) {
+ // Upper bound isn't useful. Leave it to deoptimization.
+ return this;
+ }
// Need to take care of underflow. Try to prove underflow won't happen
// for common cases.
@@ -432,10 +553,216 @@
}
}
+ // Returns true if adding a (constant >= value) check for deoptimization
+ // is allowed and will benefit compiled code.
+ bool CanAddDeoptimizationConstant(HInstruction* value,
+ int32_t constant,
+ bool* is_proven) {
+ *is_proven = false;
+ // See if we can prove the relationship first.
+ if (value->IsIntConstant()) {
+ if (value->AsIntConstant()->GetValue() >= constant) {
+ // Already true.
+ *is_proven = true;
+ return true;
+ } else {
+ // May throw exception. Don't add deoptimization.
+ // Keep bounds checks in the loops.
+ return false;
+ }
+ }
+ // Can benefit from deoptimization.
+ return true;
+ }
+
+ // Adds a check that (value >= constant), and HDeoptimize otherwise.
+ void AddDeoptimizationConstant(HInstruction* value,
+ int32_t constant) {
+ HBasicBlock* block = induction_variable_->GetBlock();
+ DCHECK(block->IsLoopHeader());
+ HGraph* graph = block->GetGraph();
+ HBasicBlock* pre_header = block->GetLoopInformation()->GetPreHeader();
+ HSuspendCheck* suspend_check = block->GetLoopInformation()->GetSuspendCheck();
+ HIntConstant* const_instr = graph->GetIntConstant(constant);
+ HCondition* cond = new (graph->GetArena()) HLessThan(value, const_instr);
+ HDeoptimize* deoptimize = new (graph->GetArena())
+ HDeoptimize(cond, suspend_check->GetDexPc());
+ pre_header->InsertInstructionBefore(cond, pre_header->GetLastInstruction());
+ pre_header->InsertInstructionBefore(deoptimize, pre_header->GetLastInstruction());
+ deoptimize->CopyEnvironmentFromWithLoopPhiAdjustment(
+ suspend_check->GetEnvironment(), block);
+ }
+
+ // Returns true if adding a (value <= array_length + offset) check for deoptimization
+ // is allowed and will benefit compiled code.
+ bool CanAddDeoptimizationArrayLength(HInstruction* value,
+ HArrayLength* array_length,
+ int32_t offset,
+ bool* is_proven) {
+ *is_proven = false;
+ if (offset > 0) {
+ // There might be overflow issue.
+ // TODO: handle this, possibly with some distance relationship between
+ // offset_low and offset_high, or using another deoptimization to make
+ // sure (array_length + offset) doesn't overflow.
+ return false;
+ }
+
+ // See if we can prove the relationship first.
+ if (value == array_length) {
+ if (offset >= 0) {
+ // Already true.
+ *is_proven = true;
+ return true;
+ } else {
+ // May throw exception. Don't add deoptimization.
+ // Keep bounds checks in the loops.
+ return false;
+ }
+ }
+ // Can benefit from deoptimization.
+ return true;
+ }
+
+ // Adds a check that (value <= array_length + offset), and HDeoptimize otherwise.
+ void AddDeoptimizationArrayLength(HInstruction* value,
+ HArrayLength* array_length,
+ int32_t offset) {
+ HBasicBlock* block = induction_variable_->GetBlock();
+ DCHECK(block->IsLoopHeader());
+ HGraph* graph = block->GetGraph();
+ HBasicBlock* pre_header = block->GetLoopInformation()->GetPreHeader();
+ HSuspendCheck* suspend_check = block->GetLoopInformation()->GetSuspendCheck();
+
+ // We may need to hoist null-check and array_length out of loop first.
+ if (!array_length->GetBlock()->Dominates(pre_header)) {
+ HInstruction* array = array_length->InputAt(0);
+ HNullCheck* null_check = array->AsNullCheck();
+ if (null_check != nullptr) {
+ array = null_check->InputAt(0);
+ }
+ // We've already made sure array is defined before the loop when collecting
+ // array accesses for the loop.
+ DCHECK(array->GetBlock()->Dominates(pre_header));
+ if (null_check != nullptr && !null_check->GetBlock()->Dominates(pre_header)) {
+ // Hoist null check out of loop with a deoptimization.
+ HNullConstant* null_constant = graph->GetNullConstant();
+ HCondition* null_check_cond = new (graph->GetArena()) HEqual(array, null_constant);
+ // TODO: for one dex_pc, share the same deoptimization slow path.
+ HDeoptimize* null_check_deoptimize = new (graph->GetArena())
+ HDeoptimize(null_check_cond, suspend_check->GetDexPc());
+ pre_header->InsertInstructionBefore(null_check_cond, pre_header->GetLastInstruction());
+ pre_header->InsertInstructionBefore(
+ null_check_deoptimize, pre_header->GetLastInstruction());
+ // Eliminate null check in the loop.
+ null_check->ReplaceWith(array);
+ null_check->GetBlock()->RemoveInstruction(null_check);
+ null_check_deoptimize->CopyEnvironmentFromWithLoopPhiAdjustment(
+ suspend_check->GetEnvironment(), block);
+ }
+ // Hoist array_length out of loop.
+ array_length->MoveBefore(pre_header->GetLastInstruction());
+ }
+
+ HIntConstant* offset_instr = graph->GetIntConstant(offset);
+ HAdd* add = new (graph->GetArena()) HAdd(Primitive::kPrimInt, array_length, offset_instr);
+ HCondition* cond = new (graph->GetArena()) HGreaterThan(value, add);
+ HDeoptimize* deoptimize = new (graph->GetArena())
+ HDeoptimize(cond, suspend_check->GetDexPc());
+ pre_header->InsertInstructionBefore(add, pre_header->GetLastInstruction());
+ pre_header->InsertInstructionBefore(cond, pre_header->GetLastInstruction());
+ pre_header->InsertInstructionBefore(deoptimize, pre_header->GetLastInstruction());
+ deoptimize->CopyEnvironmentFromWithLoopPhiAdjustment(
+ suspend_check->GetEnvironment(), block);
+ }
+
+ // Add deoptimizations in loop pre-header with the collected array access
+ // data so that value ranges can be established in loop body.
+ // Returns true if deoptimizations are successfully added, or if it's proven
+ // it's not necessary.
+ bool AddDeoptimization(const ArrayAccessInsideLoopFinder& finder) {
+ int32_t offset_low = finder.GetOffsetLow();
+ int32_t offset_high = finder.GetOffsetHigh();
+ HArrayLength* array_length = finder.GetFoundArrayLength();
+
+ HBasicBlock* pre_header =
+ induction_variable_->GetBlock()->GetLoopInformation()->GetPreHeader();
+ if (!initial_->GetBlock()->Dominates(pre_header) ||
+ !end_->GetBlock()->Dominates(pre_header)) {
+ // Can't move initial_ or end_ into pre_header for comparisons.
+ return false;
+ }
+
+ bool is_constant_proven, is_length_proven;
+ if (increment_ == 1) {
+ // Increasing from initial_ to end_.
+ int32_t offset = inclusive_ ? -offset_high - 1 : -offset_high;
+ if (CanAddDeoptimizationConstant(initial_, -offset_low, &is_constant_proven) &&
+ CanAddDeoptimizationArrayLength(end_, array_length, offset, &is_length_proven)) {
+ if (!is_constant_proven) {
+ AddDeoptimizationConstant(initial_, -offset_low);
+ }
+ if (!is_length_proven) {
+ AddDeoptimizationArrayLength(end_, array_length, offset);
+ }
+ return true;
+ }
+ } else if (increment_ == -1) {
+ // Decreasing from initial_ to end_.
+ int32_t constant = inclusive_ ? -offset_low : -offset_low - 1;
+ if (CanAddDeoptimizationConstant(end_, constant, &is_constant_proven) &&
+ CanAddDeoptimizationArrayLength(
+ initial_, array_length, -offset_high - 1, &is_length_proven)) {
+ if (!is_constant_proven) {
+ AddDeoptimizationConstant(end_, constant);
+ }
+ if (!is_length_proven) {
+ AddDeoptimizationArrayLength(initial_, array_length, -offset_high - 1);
+ }
+ return true;
+ }
+ }
+ return false;
+ }
+
+ // Try to add HDeoptimize's in the loop pre-header first to narrow this range.
+ ValueRange* NarrowWithDeoptimization() {
+ if (increment_ != 1 && increment_ != -1) {
+ // TODO: possibly handle overflow/underflow issues with deoptimization.
+ return this;
+ }
+
+ if (end_ == nullptr) {
+ // No full info to add deoptimization.
+ return this;
+ }
+
+ ArrayAccessInsideLoopFinder finder(induction_variable_);
+
+ if (!finder.HasFoundArrayLength()) {
+ // No array access inside the loop.
+ return this;
+ }
+
+ if (!AddDeoptimization(finder)) {
+ return this;
+ }
+
+ // After added deoptimizations, induction variable fits in
+ // [-offset_low, array.length-1-offset_high], adjusted with collected offsets.
+ ValueBound lower = ValueBound(0, -finder.GetOffsetLow());
+ ValueBound upper = ValueBound(finder.GetFoundArrayLength(), -1 - finder.GetOffsetHigh());
+ // We've narrowed the range after added deoptimizations.
+ return new (GetAllocator()) ValueRange(GetAllocator(), lower, upper);
+ }
+
private:
- HInstruction* const initial_;
- const int32_t increment_;
- ValueBound bound_; // Additional value bound info for initial_;
+ HPhi* const induction_variable_; // Induction variable for this monotonic value range.
+ HInstruction* const initial_; // Initial value.
+ HInstruction* end_; // End value.
+ bool inclusive_; // Whether end value is inclusive.
+ const int32_t increment_; // Increment for each loop iteration.
+ const ValueBound bound_; // Additional value bound info for initial_.
DISALLOW_COPY_AND_ASSIGN(MonotonicValueRange);
};
@@ -598,6 +925,20 @@
// There should be no critical edge at this point.
DCHECK_EQ(false_successor->GetPredecessors().Size(), 1u);
+ ValueRange* left_range = LookupValueRange(left, block);
+ MonotonicValueRange* left_monotonic_range = nullptr;
+ if (left_range != nullptr) {
+ left_monotonic_range = left_range->AsMonotonicValueRange();
+ if (left_monotonic_range != nullptr) {
+ HBasicBlock* loop_head = left_monotonic_range->GetLoopHead();
+ if (instruction->GetBlock() != loop_head) {
+ // For monotonic value range, don't handle `instruction`
+ // if it's not defined in the loop header.
+ return;
+ }
+ }
+ }
+
bool found;
ValueBound bound = ValueBound::DetectValueBoundFromValue(right, &found);
// Each comparison can establish a lower bound and an upper bound
@@ -610,7 +951,6 @@
ValueRange* right_range = LookupValueRange(right, block);
if (right_range != nullptr) {
if (right_range->IsMonotonicValueRange()) {
- ValueRange* left_range = LookupValueRange(left, block);
if (left_range != nullptr && left_range->IsMonotonicValueRange()) {
HandleIfBetweenTwoMonotonicValueRanges(instruction, left, right, cond,
left_range->AsMonotonicValueRange(),
@@ -628,6 +968,17 @@
bool overflow, underflow;
if (cond == kCondLT || cond == kCondLE) {
+ if (left_monotonic_range != nullptr) {
+ // Update the info for monotonic value range.
+ if (left_monotonic_range->GetInductionVariable() == left &&
+ left_monotonic_range->GetIncrement() < 0 &&
+ block == left_monotonic_range->GetLoopHead() &&
+ instruction->IfFalseSuccessor()->GetLoopInformation() == block->GetLoopInformation()) {
+ left_monotonic_range->SetEnd(right);
+ left_monotonic_range->SetInclusive(cond == kCondLT);
+ }
+ }
+
if (!upper.Equals(ValueBound::Max())) {
int32_t compensation = (cond == kCondLT) ? -1 : 0; // upper bound is inclusive
ValueBound new_upper = upper.Add(compensation, &overflow, &underflow);
@@ -651,6 +1002,17 @@
ApplyRangeFromComparison(left, block, false_successor, new_range);
}
} else if (cond == kCondGT || cond == kCondGE) {
+ if (left_monotonic_range != nullptr) {
+ // Update the info for monotonic value range.
+ if (left_monotonic_range->GetInductionVariable() == left &&
+ left_monotonic_range->GetIncrement() > 0 &&
+ block == left_monotonic_range->GetLoopHead() &&
+ instruction->IfFalseSuccessor()->GetLoopInformation() == block->GetLoopInformation()) {
+ left_monotonic_range->SetEnd(right);
+ left_monotonic_range->SetInclusive(cond == kCondGT);
+ }
+ }
+
// array.length as a lower bound isn't considered useful.
if (!lower.Equals(ValueBound::Min()) && !lower.IsRelatedToArrayLength()) {
int32_t compensation = (cond == kCondGT) ? 1 : 0; // lower bound is inclusive
@@ -790,6 +1152,7 @@
}
range = new (GetGraph()->GetArena()) MonotonicValueRange(
GetGraph()->GetArena(),
+ phi,
initial_value,
increment,
bound);
@@ -809,6 +1172,36 @@
HInstruction* left = cond->GetLeft();
HInstruction* right = cond->GetRight();
HandleIf(instruction, left, right, cmp);
+
+ HBasicBlock* block = instruction->GetBlock();
+ ValueRange* left_range = LookupValueRange(left, block);
+ if (left_range == nullptr) {
+ return;
+ }
+
+ if (left_range->IsMonotonicValueRange() &&
+ block == left_range->AsMonotonicValueRange()->GetLoopHead()) {
+ // The comparison is for an induction variable in the loop header.
+ DCHECK(left == left_range->AsMonotonicValueRange()->GetInductionVariable());
+ HBasicBlock* loop_body_successor;
+ if (UNLIKELY(block->GetLoopInformation() !=
+ instruction->IfFalseSuccessor()->GetLoopInformation())) {
+ loop_body_successor = instruction->IfTrueSuccessor();
+ } else {
+ loop_body_successor = instruction->IfFalseSuccessor();
+ }
+ ValueRange* new_left_range = LookupValueRange(left, loop_body_successor);
+ if (new_left_range == left_range) {
+ // We are not successful in narrowing the monotonic value range to
+ // a regular value range. Try using deoptimization.
+ new_left_range = left_range->AsMonotonicValueRange()->
+ NarrowWithDeoptimization();
+ if (new_left_range != left_range) {
+ GetValueRangeMap(instruction->IfFalseSuccessor())->
+ Overwrite(left->GetId(), new_left_range);
+ }
+ }
+ }
}
}
}
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index c158ddf..ca470f4 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -498,6 +498,28 @@
}
}
+void HEnvironment::CopyFromWithLoopPhiAdjustment(HEnvironment* env,
+ HBasicBlock* loop_header) {
+ DCHECK(loop_header->IsLoopHeader());
+ for (size_t i = 0; i < env->Size(); i++) {
+ HInstruction* instruction = env->GetInstructionAt(i);
+ SetRawEnvAt(i, instruction);
+ if (instruction == nullptr) {
+ continue;
+ }
+ if (instruction->IsLoopHeaderPhi() && (instruction->GetBlock() == loop_header)) {
+ // At the end of the loop pre-header, the corresponding value for instruction
+ // is the first input of the phi.
+ HInstruction* initial = instruction->AsPhi()->InputAt(0);
+ DCHECK(initial->GetBlock()->Dominates(loop_header));
+ SetRawEnvAt(i, initial);
+ initial->AddEnvUseAt(this, i);
+ } else {
+ instruction->AddEnvUseAt(this, i);
+ }
+ }
+}
+
void HEnvironment::RemoveAsUserOfInput(size_t index) const {
const HUserRecord<HEnvironment*> user_record = vregs_.Get(index);
user_record.GetInstruction()->RemoveEnvironmentUser(user_record.GetUseNode());
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 6b9d72d..181122f 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -1007,6 +1007,10 @@
}
void CopyFrom(HEnvironment* env);
+ // Copy from `env`. If it's a loop phi for `loop_header`, copy the first
+ // input to the loop phi instead. This is for inserting instructions that
+ // require an environment (like HDeoptimization) in the loop pre-header.
+ void CopyFromWithLoopPhiAdjustment(HEnvironment* env, HBasicBlock* loop_header);
void SetRawEnvAt(size_t index, HInstruction* instruction) {
vregs_.Put(index, HUserRecord<HEnvironment*>(instruction));
@@ -1242,6 +1246,13 @@
environment_->CopyFrom(environment);
}
+ void CopyEnvironmentFromWithLoopPhiAdjustment(HEnvironment* environment,
+ HBasicBlock* block) {
+ ArenaAllocator* allocator = GetBlock()->GetGraph()->GetArena();
+ environment_ = new (allocator) HEnvironment(allocator, environment->Size());
+ environment_->CopyFromWithLoopPhiAdjustment(environment, block);
+ }
+
// Returns the number of entries in the environment. Typically, that is the
// number of dex registers in a method. It could be more in case of inlining.
size_t EnvironmentSize() const;
diff --git a/test/449-checker-bce/expected.txt b/test/449-checker-bce/expected.txt
index 29d6383..e69de29 100644
--- a/test/449-checker-bce/expected.txt
+++ b/test/449-checker-bce/expected.txt
@@ -1 +0,0 @@
-100
diff --git a/test/449-checker-bce/src/Main.java b/test/449-checker-bce/src/Main.java
index 17039a3..f60fd16 100644
--- a/test/449-checker-bce/src/Main.java
+++ b/test/449-checker-bce/src/Main.java
@@ -608,6 +608,349 @@
}
+ int sum;
+
+ // CHECK-START: void Main.foo1(int[], int, int) BCE (before)
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArrayGet
+
+ // CHECK-START: void Main.foo1(int[], int, int) BCE (after)
+ // CHECK: Deoptimize
+ // CHECK: Deoptimize
+ // CHECK: Deoptimize
+ // CHECK-NOT: Deoptimize
+ // CHECK: Phi
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArrayGet
+
+ void foo1(int[] array, int start, int end) {
+ // Three HDeoptimize will be added. One for
+ // start >= 0, one for end <= array.length,
+ // and one for null check on array (to hoist null
+ // check and array.length out of loop).
+ for (int i = start ; i < end; i++) {
+ array[i] = 1;
+ sum += array[i];
+ }
+ }
+
+
+ // CHECK-START: void Main.foo2(int[], int, int) BCE (before)
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArrayGet
+
+ // CHECK-START: void Main.foo2(int[], int, int) BCE (after)
+ // CHECK: Deoptimize
+ // CHECK: Deoptimize
+ // CHECK: Deoptimize
+ // CHECK-NOT: Deoptimize
+ // CHECK: Phi
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArrayGet
+
+ void foo2(int[] array, int start, int end) {
+ // Three HDeoptimize will be added. One for
+ // start >= 0, one for end <= array.length,
+ // and one for null check on array (to hoist null
+ // check and array.length out of loop).
+ for (int i = start ; i <= end; i++) {
+ array[i] = 1;
+ sum += array[i];
+ }
+ }
+
+
+ // CHECK-START: void Main.foo3(int[], int) BCE (before)
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArrayGet
+
+ // CHECK-START: void Main.foo3(int[], int) BCE (after)
+ // CHECK: Deoptimize
+ // CHECK: Deoptimize
+ // CHECK-NOT: Deoptimize
+ // CHECK: Phi
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArrayGet
+
+ void foo3(int[] array, int end) {
+ // Two HDeoptimize will be added. One for end < array.length,
+ // and one for null check on array (to hoist null check
+ // and array.length out of loop).
+ for (int i = 3 ; i <= end; i++) {
+ array[i] = 1;
+ sum += array[i];
+ }
+ }
+
+ // CHECK-START: void Main.foo4(int[], int) BCE (before)
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArrayGet
+
+ // CHECK-START: void Main.foo4(int[], int) BCE (after)
+ // CHECK: Deoptimize
+ // CHECK: Deoptimize
+ // CHECK-NOT: Deoptimize
+ // CHECK: Phi
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArrayGet
+
+ void foo4(int[] array, int end) {
+ // Two HDeoptimize will be added. One for end <= array.length,
+ // and one for null check on array (to hoist null check
+ // and array.length out of loop).
+ for (int i = end ; i > 0; i--) {
+ array[i - 1] = 1;
+ sum += array[i - 1];
+ }
+ }
+
+
+ // CHECK-START: void Main.foo5(int[], int) BCE (before)
+ // CHECK: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK: BoundsCheck
+ // CHECK: ArrayGet
+ // CHECK: BoundsCheck
+ // CHECK: ArrayGet
+ // CHECK: BoundsCheck
+ // CHECK: ArrayGet
+
+ // CHECK-START: void Main.foo5(int[], int) BCE (after)
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArraySet
+ // CHECK: Deoptimize
+ // CHECK-NOT: Deoptimize
+ // CHECK: Phi
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArrayGet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArrayGet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArrayGet
+
+ void foo5(int[] array, int end) {
+ // Bounds check in this loop can be eliminated without deoptimization.
+ for (int i = array.length - 1 ; i >= 0; i--) {
+ array[i] = 1;
+ }
+ // One HDeoptimize will be added.
+ // It's for (end - 2 <= array.length - 2).
+ for (int i = end - 2 ; i > 0; i--) {
+ sum += array[i - 1];
+ sum += array[i];
+ sum += array[i + 1];
+ }
+ }
+
+
+ // CHECK-START: void Main.foo6(int[], int, int) BCE (before)
+ // CHECK: BoundsCheck
+ // CHECK: ArrayGet
+ // CHECK: BoundsCheck
+ // CHECK: ArrayGet
+ // CHECK: BoundsCheck
+ // CHECK: ArrayGet
+ // CHECK: BoundsCheck
+ // CHECK: ArrayGet
+ // CHECK: BoundsCheck
+ // CHECK: ArrayGet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArraySet
+
+ // CHECK-START: void Main.foo6(int[], int, int) BCE (after)
+ // CHECK: Deoptimize
+ // CHECK: Deoptimize
+ // CHECK: Deoptimize
+ // CHECK-NOT: Deoptimize
+ // CHECK: Phi
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArrayGet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArrayGet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArrayGet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArrayGet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArrayGet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArraySet
+
+ void foo6(int[] array, int start, int end) {
+ // Three HDeoptimize will be added. One for
+ // start >= 2, one for end <= array.length - 3,
+ // and one for null check on array (to hoist null
+ // check and array.length out of loop).
+ for (int i = end; i >= start; i--) {
+ array[i] = (array[i-2] + array[i-1] + array[i] + array[i+1] + array[i+2]) / 5;
+ }
+ }
+
+
+ // CHECK-START: void Main.foo7(int[], int, int, boolean) BCE (before)
+ // CHECK: BoundsCheck
+ // CHECK: ArrayGet
+ // CHECK: BoundsCheck
+ // CHECK: ArrayGet
+
+ // CHECK-START: void Main.foo7(int[], int, int, boolean) BCE (after)
+ // CHECK: Deoptimize
+ // CHECK: Deoptimize
+ // CHECK: Deoptimize
+ // CHECK-NOT: Deoptimize
+ // CHECK: Phi
+ // CHECK: BoundsCheck
+ // CHECK: ArrayGet
+ // CHECK-NOT: BoundsCheck
+ // CHECK: ArrayGet
+
+ void foo7(int[] array, int start, int end, boolean lowEnd) {
+ // Three HDeoptimize will be added. One for
+ // start >= 0, one for end <= array.length,
+ // and one for null check on array (to hoist null
+ // check and array.length out of loop).
+ for (int i = start ; i < end; i++) {
+ if (lowEnd) {
+ // This array access isn't certain. So we don't
+ // use +1000 offset in decision making for deoptimization
+ // conditions.
+ sum += array[i + 1000];
+ }
+ sum += array[i];
+ }
+ }
+
+
+ static void testUnknownBounds() {
+ boolean caught = false;
+ Main main = new Main();
+ main.foo1(new int[10], 0, 10);
+ if (main.sum != 10) {
+ System.out.println("foo1 failed!");
+ }
+
+ caught = false;
+ main = new Main();
+ try {
+ main.foo1(new int[10], 0, 11);
+ } catch (ArrayIndexOutOfBoundsException e) {
+ caught = true;
+ }
+ if (!caught || main.sum != 10) {
+ System.out.println("foo1 exception failed!");
+ }
+
+ main = new Main();
+ main.foo2(new int[10], 0, 9);
+ if (main.sum != 10) {
+ System.out.println("foo2 failed!");
+ }
+
+ caught = false;
+ main = new Main();
+ try {
+ main.foo2(new int[10], 0, 10);
+ } catch (ArrayIndexOutOfBoundsException e) {
+ caught = true;
+ }
+ if (!caught || main.sum != 10) {
+ System.out.println("foo2 exception failed!");
+ }
+
+ main = new Main();
+ main.foo3(new int[10], 9);
+ if (main.sum != 7) {
+ System.out.println("foo3 failed!");
+ }
+
+ caught = false;
+ main = new Main();
+ try {
+ main.foo3(new int[10], 10);
+ } catch (ArrayIndexOutOfBoundsException e) {
+ caught = true;
+ }
+ if (!caught || main.sum != 7) {
+ System.out.println("foo3 exception failed!");
+ }
+
+ main = new Main();
+ main.foo4(new int[10], 10);
+ if (main.sum != 10) {
+ System.out.println("foo4 failed!");
+ }
+
+ caught = false;
+ main = new Main();
+ try {
+ main.foo4(new int[10], 11);
+ } catch (ArrayIndexOutOfBoundsException e) {
+ caught = true;
+ }
+ if (!caught || main.sum != 0) {
+ System.out.println("foo4 exception failed!");
+ }
+
+ main = new Main();
+ main.foo5(new int[10], 10);
+ if (main.sum != 24) {
+ System.out.println("foo5 failed!");
+ }
+
+ caught = false;
+ main = new Main();
+ try {
+ main.foo5(new int[10], 11);
+ } catch (ArrayIndexOutOfBoundsException e) {
+ caught = true;
+ }
+ if (!caught || main.sum != 2) {
+ System.out.println("foo5 exception failed!");
+ }
+
+ main = new Main();
+ main.foo6(new int[10], 2, 7);
+
+ caught = false;
+ main = new Main();
+ try {
+ main.foo6(new int[10], 2, 8);
+ } catch (ArrayIndexOutOfBoundsException e) {
+ caught = true;
+ }
+ if (!caught) {
+ System.out.println("foo6 exception failed!");
+ }
+
+ caught = false;
+ main = new Main();
+ try {
+ main.foo6(new int[10], 1, 7);
+ } catch (ArrayIndexOutOfBoundsException e) {
+ caught = true;
+ }
+ if (!caught) {
+ System.out.println("foo6 exception failed!");
+ }
+
+ }
+
// Make sure this method is compiled with optimizing.
// CHECK-START: void Main.main(java.lang.String[]) register (after)
// CHECK: ParallelMove
@@ -643,7 +986,11 @@
// Make sure this value is kept after deoptimization.
int i = 1;
- System.out.println(foo() + i);
+ if (foo() + i != 100) {
+ System.out.println("foo failed!");
+ };
+
+ testUnknownBounds();
}
}