Improve bce so that more bounds checks can be eliminated.
For pattern like "int[] array = new int[size+1]", we record this range
for size:
[-1, array.length-1]
This can eliminate more bounds checks.
Also simplify overflow/underflow handling and make it more solid.
Enhance instruction simplifier such that if array is a result of
NewArray with a constant size, replace array.length with that constant.
Plan to move all bce gtests to checker in another change.
Change-Id: Ibe7cc7940b68fb6465dc3e0ff3ebdb0fd6487aa9
diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index d6c3515..bcee563 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -28,10 +28,10 @@
*/
class ValueBound : public ValueObject {
public:
- ValueBound(HInstruction* instruction, int constant) {
+ ValueBound(HInstruction* instruction, int32_t constant) {
if (instruction != nullptr && instruction->IsIntConstant()) {
- // Normalizing ValueBound with constant instruction.
- int instr_const = instruction->AsIntConstant()->GetValue();
+ // Normalize ValueBound with constant instruction.
+ int32_t instr_const = instruction->AsIntConstant()->GetValue();
if (constant >= 0 && (instr_const <= INT_MAX - constant)) {
// No overflow.
instruction_ = nullptr;
@@ -49,6 +49,25 @@
constant_ = constant;
}
+ static bool IsAddOrSubAConstant(HInstruction* instruction,
+ HInstruction** left_instruction,
+ int* right_constant) {
+ if (instruction->IsAdd() || instruction->IsSub()) {
+ HBinaryOperation* bin_op = instruction->AsBinaryOperation();
+ HInstruction* left = bin_op->GetLeft();
+ HInstruction* right = bin_op->GetRight();
+ if (right->IsIntConstant()) {
+ *left_instruction = left;
+ int32_t c = right->AsIntConstant()->GetValue();
+ *right_constant = instruction->IsAdd() ? c : -c;
+ return true;
+ }
+ }
+ *left_instruction = nullptr;
+ *right_constant = 0;
+ return false;
+ }
+
// 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) {
@@ -63,13 +82,12 @@
return ValueBound(instruction, 0);
}
// Try to detect (array.length + c) format.
- if (instruction->IsAdd()) {
- HAdd* add = instruction->AsAdd();
- HInstruction* left = add->GetLeft();
- HInstruction* right = add->GetRight();
- if (left->IsArrayLength() && right->IsIntConstant()) {
+ HInstruction *left;
+ int32_t right;
+ if (IsAddOrSubAConstant(instruction, &left, &right)) {
+ if (left->IsArrayLength()) {
*found = true;
- return ValueBound(left, right->AsIntConstant()->GetValue());
+ return ValueBound(left, right);
}
}
@@ -79,10 +97,13 @@
}
HInstruction* GetInstruction() const { return instruction_; }
- int GetConstant() const { return constant_; }
+ int32_t GetConstant() const { return constant_; }
- bool IsRelativeToArrayLength() const {
- return instruction_ != nullptr && instruction_->IsArrayLength();
+ bool IsRelatedToArrayLength() const {
+ // Some bounds are created with HNewArray* as the instruction instead
+ // of HArrayLength*. They are treated the same.
+ return (instruction_ != nullptr) &&
+ (instruction_->IsArrayLength() || instruction_->IsNewArray());
}
bool IsConstant() const {
@@ -96,54 +117,45 @@
return instruction_ == bound.instruction_ && constant_ == bound.constant_;
}
- // Returns if it's certain bound1 >= bound2.
- bool GreaterThanOrEqual(ValueBound bound) const {
- if (instruction_ == bound.instruction_) {
- if (instruction_ == nullptr) {
- // Pure constant.
- return constant_ >= bound.constant_;
- }
- // There might be overflow/underflow. Be conservative for now.
+ static HInstruction* FromArrayLengthToNewArrayIfPossible(HInstruction* instruction) {
+ // Null check on the NewArray should have been eliminated by instruction
+ // simplifier already.
+ if (instruction->IsArrayLength() && instruction->InputAt(0)->IsNewArray()) {
+ return instruction->InputAt(0)->AsNewArray();
+ }
+ return instruction;
+ }
+
+ static bool Equal(HInstruction* instruction1, HInstruction* instruction2) {
+ if (instruction1 == instruction2) {
+ return true;
+ }
+
+ if (instruction1 == nullptr || instruction2 == nullptr) {
return false;
}
+
+ // Some bounds are created with HNewArray* as the instruction instead
+ // of HArrayLength*. They are treated the same.
+ instruction1 = FromArrayLengthToNewArrayIfPossible(instruction1);
+ instruction2 = FromArrayLengthToNewArrayIfPossible(instruction2);
+ return instruction1 == instruction2;
+ }
+
+ // Returns if it's certain this->bound >= `bound`.
+ bool GreaterThanOrEqualTo(ValueBound bound) const {
+ if (Equal(instruction_, bound.instruction_)) {
+ return constant_ >= bound.constant_;
+ }
// Not comparable. Just return false.
return false;
}
- // Returns if it's certain bound1 <= bound2.
- bool LessThanOrEqual(ValueBound bound) const {
- if (instruction_ == bound.instruction_) {
- if (instruction_ == nullptr) {
- // Pure constant.
- return constant_ <= bound.constant_;
- }
- if (IsRelativeToArrayLength()) {
- // Array length is guaranteed to be no less than 0.
- // No overflow/underflow can happen if both constants are negative.
- if (constant_ <= 0 && bound.constant_ <= 0) {
- return constant_ <= bound.constant_;
- }
- // There might be overflow/underflow. Be conservative for now.
- return false;
- }
+ // Returns if it's certain this->bound <= `bound`.
+ bool LessThanOrEqualTo(ValueBound bound) const {
+ if (Equal(instruction_, bound.instruction_)) {
+ return constant_ <= bound.constant_;
}
-
- // In case the array length is some constant, we can
- // still compare.
- if (IsConstant() && bound.IsRelativeToArrayLength()) {
- HInstruction* array = bound.GetInstruction()->AsArrayLength()->InputAt(0);
- if (array->IsNullCheck()) {
- array = array->AsNullCheck()->InputAt(0);
- }
- if (array->IsNewArray()) {
- HInstruction* len = array->InputAt(0);
- if (len->IsIntConstant()) {
- int len_const = len->AsIntConstant()->GetValue();
- return constant_ <= len_const + bound.GetConstant();
- }
- }
- }
-
// Not comparable. Just return false.
return false;
}
@@ -151,10 +163,11 @@
// Try to narrow lower bound. Returns the greatest of the two if possible.
// Pick one if they are not comparable.
static ValueBound NarrowLowerBound(ValueBound bound1, ValueBound bound2) {
- if (bound1.instruction_ == bound2.instruction_) {
- // Same instruction, compare the constant part.
- return ValueBound(bound1.instruction_,
- std::max(bound1.constant_, bound2.constant_));
+ if (bound1.GreaterThanOrEqualTo(bound2)) {
+ return bound1;
+ }
+ if (bound2.GreaterThanOrEqualTo(bound1)) {
+ return bound2;
}
// Not comparable. Just pick one. We may lose some info, but that's ok.
@@ -165,58 +178,71 @@
// Try to narrow upper bound. Returns the lowest of the two if possible.
// Pick one if they are not comparable.
static ValueBound NarrowUpperBound(ValueBound bound1, ValueBound bound2) {
- if (bound1.instruction_ == bound2.instruction_) {
- // Same instruction, compare the constant part.
- return ValueBound(bound1.instruction_,
- std::min(bound1.constant_, bound2.constant_));
+ if (bound1.LessThanOrEqualTo(bound2)) {
+ return bound1;
+ }
+ if (bound2.LessThanOrEqualTo(bound1)) {
+ return bound2;
}
// Not comparable. Just pick one. We may lose some info, but that's ok.
// Favor array length as upper bound.
- return bound1.IsRelativeToArrayLength() ? bound1 : bound2;
+ return bound1.IsRelatedToArrayLength() ? bound1 : bound2;
}
- // Add a constant to a ValueBound. If the constant part of the ValueBound
- // overflows/underflows, then we can't accurately represent it. For correctness,
- // just return Max/Min() depending on whether the returned ValueBound is used for
- // lower/upper bound.
- ValueBound Add(int c, bool* overflow_or_underflow) const {
- *overflow_or_underflow = false;
+ // 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 {
+ *overflow = *underflow = false;
if (c == 0) {
return *this;
}
- int new_constant;
+ int32_t new_constant;
if (c > 0) {
if (constant_ > INT_MAX - c) {
- // Constant part overflows.
- *overflow_or_underflow = true;
+ *overflow = true;
return Max();
- } else {
- new_constant = constant_ + c;
}
+
+ new_constant = constant_ + c;
+ // (array.length + non-positive-constant) won't overflow an int.
+ if (IsConstant() || (IsRelatedToArrayLength() && new_constant <= 0)) {
+ return ValueBound(instruction_, new_constant);
+ }
+ // Be conservative.
+ *overflow = true;
+ return Max();
} else {
if (constant_ < INT_MIN - c) {
- // Constant part underflows.
- *overflow_or_underflow = true;
- return Max();
- } else {
- new_constant = constant_ + c;
+ *underflow = true;
+ return Min();
}
+
+ new_constant = constant_ + c;
+ // Regardless of the value new_constant, (array.length+new_constant) will
+ // never underflow since array.length is no less than 0.
+ if (IsConstant() || IsRelatedToArrayLength()) {
+ return ValueBound(instruction_, new_constant);
+ }
+ // Be conservative.
+ *underflow = true;
+ return Min();
}
return ValueBound(instruction_, new_constant);
}
private:
HInstruction* instruction_;
- int constant_;
+ int32_t constant_;
};
/**
* Represent a range of lower bound and upper bound, both being inclusive.
* Currently a ValueRange may be generated as a result of the following:
* comparisons related to array bounds, array bounds check, add/sub on top
- * of an existing value range, or a loop phi corresponding to an
+ * of an existing value range, NewArray or a loop phi corresponding to an
* incrementing/decrementing array index (MonotonicValueRange).
*/
class ValueRange : public ArenaObject<kArenaAllocMisc> {
@@ -241,8 +267,8 @@
return true;
}
DCHECK(!other_range->IsMonotonicValueRange());
- return lower_.GreaterThanOrEqual(other_range->lower_) &&
- upper_.LessThanOrEqual(other_range->upper_);
+ return lower_.GreaterThanOrEqualTo(other_range->lower_) &&
+ upper_.LessThanOrEqualTo(other_range->upper_);
}
// Returns the intersection of this and range.
@@ -263,29 +289,24 @@
ValueBound::NarrowUpperBound(upper_, range->upper_));
}
- // Shift a range by a constant. If either bound can't be represented
- // as (instruction+c) format due to possible overflow/underflow,
- // return the full integer range.
- ValueRange* Add(int constant) const {
- bool overflow_or_underflow;
- ValueBound lower = lower_.Add(constant, &overflow_or_underflow);
- if (overflow_or_underflow) {
- // We can't accurately represent the bounds anymore.
- return FullIntRange();
+ // Shift a range by a constant.
+ ValueRange* Add(int32_t constant) const {
+ bool overflow, underflow;
+ ValueBound lower = lower_.Add(constant, &overflow, &underflow);
+ if (underflow) {
+ // Lower bound underflow will wrap around to positive values
+ // and invalidate the upper bound.
+ return nullptr;
}
- ValueBound upper = upper_.Add(constant, &overflow_or_underflow);
- if (overflow_or_underflow) {
- // We can't accurately represent the bounds anymore.
- return FullIntRange();
+ ValueBound upper = upper_.Add(constant, &overflow, &underflow);
+ if (overflow) {
+ // Upper bound overflow will wrap around to negative values
+ // and invalidate the lower bound.
+ return nullptr;
}
return new (allocator_) ValueRange(allocator_, lower, upper);
}
- // Return [INT_MIN, INT_MAX].
- ValueRange* FullIntRange() const {
- return new (allocator_) ValueRange(allocator_, ValueBound::Min(), ValueBound::Max());
- }
-
private:
ArenaAllocator* const allocator_;
const ValueBound lower_; // inclusive
@@ -304,7 +325,7 @@
public:
MonotonicValueRange(ArenaAllocator* allocator,
HInstruction* initial,
- int increment,
+ 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.
@@ -343,23 +364,17 @@
// make assumptions about the max array length, e.g. due to the max heap size,
// divided by the element size (such as 4 bytes for each integer array), we can
// lower this number and rule out some possible overflows.
- int max_array_len = INT_MAX;
+ int32_t max_array_len = INT_MAX;
- int upper = INT_MAX;
- if (range->GetUpper().IsConstant()) {
- upper = range->GetUpper().GetConstant();
- } else if (range->GetUpper().IsRelativeToArrayLength()) {
- int constant = range->GetUpper().GetConstant();
- if (constant <= 0) {
- // Normal case. e.g. <= array.length - 1, <= array.length - 2, etc.
- upper = max_array_len + constant;
- } else {
- // There might be overflow. Give up narrowing.
- return this;
- }
- } else {
- // There might be overflow. Give up narrowing.
- return this;
+ // max possible integer value of range's upper value.
+ int32_t upper = INT_MAX;
+ // Try to lower upper.
+ ValueBound upper_bound = range->GetUpper();
+ if (upper_bound.IsConstant()) {
+ upper = upper_bound.GetConstant();
+ } else if (upper_bound.IsRelatedToArrayLength() && upper_bound.GetConstant() <= 0) {
+ // Normal case. e.g. <= array.length - 1.
+ upper = max_array_len + upper_bound.GetConstant();
}
// If we can prove for the last number in sequence of initial_,
@@ -368,13 +383,13 @@
// then this MonoticValueRange is narrowed to a normal value range.
// Be conservative first, assume last number in the sequence hits upper.
- int last_num_in_sequence = upper;
+ int32_t last_num_in_sequence = upper;
if (initial_->IsIntConstant()) {
- int initial_constant = initial_->AsIntConstant()->GetValue();
+ int32_t initial_constant = initial_->AsIntConstant()->GetValue();
if (upper <= initial_constant) {
last_num_in_sequence = upper;
} else {
- // Cast to int64_t for the substraction part to avoid int overflow.
+ // Cast to int64_t for the substraction part to avoid int32_t overflow.
last_num_in_sequence = initial_constant +
((int64_t)upper - (int64_t)initial_constant) / increment_ * increment_;
}
@@ -392,23 +407,22 @@
ValueBound upper = ValueBound::NarrowUpperBound(bound_, range->GetUpper());
// Need to take care of underflow. Try to prove underflow won't happen
- // for common cases. Basically need to be able to prove for any value
- // that's >= range->GetLower(), it won't be positive with value+increment.
+ // for common cases.
if (range->GetLower().IsConstant()) {
- int constant = range->GetLower().GetConstant();
+ int32_t constant = range->GetLower().GetConstant();
if (constant >= INT_MIN - increment_) {
return new (GetAllocator()) ValueRange(GetAllocator(), range->GetLower(), upper);
}
}
- // There might be underflow. Give up narrowing.
+ // For non-constant lower bound, just assume might be underflow. Give up narrowing.
return this;
}
}
private:
HInstruction* const initial_;
- const int increment_;
+ const int32_t increment_;
ValueBound bound_; // Additional value bound info for initial_;
DISALLOW_COPY_AND_ASSIGN(MonotonicValueRange);
@@ -446,8 +460,8 @@
return nullptr;
}
- // Narrow the value range of 'instruction' at the end of 'basic_block' with 'range',
- // and push the narrowed value range to 'successor'.
+ // 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,
HBasicBlock* successor, ValueRange* range) {
ValueRange* existing_range = LookupValueRange(instruction, basic_block);
@@ -472,10 +486,12 @@
bool found;
ValueBound bound = ValueBound::DetectValueBoundFromValue(right, &found);
+ // Each comparison can establish a lower bound and an upper bound
+ // for the left hand side.
ValueBound lower = bound;
ValueBound upper = bound;
if (!found) {
- // No constant or array.length+c bound found.
+ // No constant or array.length+c format bound found.
// For i<j, we can still use j's upper bound as i's upper bound. Same for lower.
ValueRange* range = LookupValueRange(right, block);
if (range != nullptr) {
@@ -487,13 +503,13 @@
}
}
- bool overflow_or_underflow;
+ bool overflow, underflow;
if (cond == kCondLT || cond == kCondLE) {
if (!upper.Equals(ValueBound::Max())) {
- int compensation = (cond == kCondLT) ? -1 : 0; // upper bound is inclusive
- ValueBound new_upper = upper.Add(compensation, &overflow_or_underflow);
- if (overflow_or_underflow) {
- new_upper = ValueBound::Max();
+ int32_t compensation = (cond == kCondLT) ? -1 : 0; // upper bound is inclusive
+ ValueBound new_upper = upper.Add(compensation, &overflow, &underflow);
+ if (overflow || underflow) {
+ return;
}
ValueRange* new_range = new (GetGraph()->GetArena())
ValueRange(GetGraph()->GetArena(), ValueBound::Min(), new_upper);
@@ -501,11 +517,11 @@
}
// array.length as a lower bound isn't considered useful.
- if (!lower.Equals(ValueBound::Min()) && !lower.IsRelativeToArrayLength()) {
- int compensation = (cond == kCondLE) ? 1 : 0; // lower bound is inclusive
- ValueBound new_lower = lower.Add(compensation, &overflow_or_underflow);
- if (overflow_or_underflow) {
- new_lower = ValueBound::Min();
+ if (!lower.Equals(ValueBound::Min()) && !lower.IsRelatedToArrayLength()) {
+ int32_t compensation = (cond == kCondLE) ? 1 : 0; // lower bound is inclusive
+ ValueBound new_lower = lower.Add(compensation, &overflow, &underflow);
+ if (overflow || underflow) {
+ return;
}
ValueRange* new_range = new (GetGraph()->GetArena())
ValueRange(GetGraph()->GetArena(), new_lower, ValueBound::Max());
@@ -513,11 +529,11 @@
}
} else if (cond == kCondGT || cond == kCondGE) {
// array.length as a lower bound isn't considered useful.
- if (!lower.Equals(ValueBound::Min()) && !lower.IsRelativeToArrayLength()) {
- int compensation = (cond == kCondGT) ? 1 : 0; // lower bound is inclusive
- ValueBound new_lower = lower.Add(compensation, &overflow_or_underflow);
- if (overflow_or_underflow) {
- new_lower = ValueBound::Min();
+ if (!lower.Equals(ValueBound::Min()) && !lower.IsRelatedToArrayLength()) {
+ int32_t compensation = (cond == kCondGT) ? 1 : 0; // lower bound is inclusive
+ ValueBound new_lower = lower.Add(compensation, &overflow, &underflow);
+ if (overflow || underflow) {
+ return;
}
ValueRange* new_range = new (GetGraph()->GetArena())
ValueRange(GetGraph()->GetArena(), new_lower, ValueBound::Max());
@@ -525,10 +541,10 @@
}
if (!upper.Equals(ValueBound::Max())) {
- int compensation = (cond == kCondGE) ? -1 : 0; // upper bound is inclusive
- ValueBound new_upper = upper.Add(compensation, &overflow_or_underflow);
- if (overflow_or_underflow) {
- new_upper = ValueBound::Max();
+ int32_t compensation = (cond == kCondGE) ? -1 : 0; // upper bound is inclusive
+ ValueBound new_upper = upper.Add(compensation, &overflow, &underflow);
+ if (overflow || underflow) {
+ return;
}
ValueRange* new_range = new (GetGraph()->GetArena())
ValueRange(GetGraph()->GetArena(), ValueBound::Min(), new_upper);
@@ -541,41 +557,56 @@
HBasicBlock* block = bounds_check->GetBlock();
HInstruction* index = bounds_check->InputAt(0);
HInstruction* array_length = bounds_check->InputAt(1);
- ValueRange* index_range = LookupValueRange(index, block);
+ DCHECK(array_length->IsIntConstant() || array_length->IsArrayLength());
- if (index_range != nullptr) {
- ValueBound lower = ValueBound(nullptr, 0); // constant 0
- ValueBound upper = ValueBound(array_length, -1); // array_length - 1
- ValueRange* array_range = new (GetGraph()->GetArena())
- ValueRange(GetGraph()->GetArena(), lower, upper);
- if (index_range->FitsIn(array_range)) {
- ReplaceBoundsCheck(bounds_check, index);
- return;
- }
- }
-
- if (index->IsIntConstant()) {
- ValueRange* array_length_range = LookupValueRange(array_length, block);
- int constant = index->AsIntConstant()->GetValue();
- if (array_length_range != nullptr &&
- array_length_range->GetLower().IsConstant()) {
- if (constant < array_length_range->GetLower().GetConstant()) {
+ if (!index->IsIntConstant()) {
+ ValueRange* index_range = LookupValueRange(index, block);
+ if (index_range != nullptr) {
+ ValueBound lower = ValueBound(nullptr, 0); // constant 0
+ ValueBound upper = ValueBound(array_length, -1); // array_length - 1
+ ValueRange* array_range = new (GetGraph()->GetArena())
+ ValueRange(GetGraph()->GetArena(), lower, upper);
+ if (index_range->FitsIn(array_range)) {
ReplaceBoundsCheck(bounds_check, index);
return;
}
}
+ } else {
+ int32_t constant = index->AsIntConstant()->GetValue();
+ if (constant < 0) {
+ // Will always throw exception.
+ return;
+ }
+ if (array_length->IsIntConstant()) {
+ if (constant < array_length->AsIntConstant()->GetValue()) {
+ ReplaceBoundsCheck(bounds_check, index);
+ }
+ return;
+ }
+
+ DCHECK(array_length->IsArrayLength());
+ ValueRange* existing_range = LookupValueRange(array_length, block);
+ if (existing_range != nullptr) {
+ ValueBound lower = existing_range->GetLower();
+ DCHECK(lower.IsConstant());
+ if (constant < lower.GetConstant()) {
+ ReplaceBoundsCheck(bounds_check, index);
+ return;
+ } else {
+ // Existing range isn't strong enough to eliminate the bounds check.
+ // Fall through to update the array_length range with info from this
+ // bounds check.
+ }
+ }
// 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.
ValueBound lower = ValueBound(nullptr, constant + 1);
ValueBound upper = ValueBound::Max();
ValueRange* range = new (GetGraph()->GetArena())
ValueRange(GetGraph()->GetArena(), lower, upper);
- ValueRange* existing_range = LookupValueRange(array_length, block);
- ValueRange* new_range = range;
- if (existing_range != nullptr) {
- new_range = range->Narrow(existing_range);
- }
- GetValueRangeMap(block)->Overwrite(array_length->GetId(), new_range);
+ GetValueRangeMap(block)->Overwrite(array_length->GetId(), range);
}
}
@@ -588,14 +619,12 @@
if (phi->IsLoopHeaderPhi() && phi->GetType() == Primitive::kPrimInt) {
DCHECK_EQ(phi->InputCount(), 2U);
HInstruction* instruction = phi->InputAt(1);
- if (instruction->IsAdd()) {
- HAdd* add = instruction->AsAdd();
- HInstruction* left = add->GetLeft();
- HInstruction* right = add->GetRight();
- if (left == phi && right->IsIntConstant()) {
+ HInstruction *left;
+ int32_t increment;
+ if (ValueBound::IsAddOrSubAConstant(instruction, &left, &increment)) {
+ if (left == phi) {
HInstruction* initial_value = phi->InputAt(0);
ValueRange* range = nullptr;
- int increment = right->AsIntConstant()->GetValue();
if (increment == 0) {
// Add constant 0. It's really a fixed value.
range = new (GetGraph()->GetArena()) ValueRange(
@@ -682,10 +711,10 @@
if (right_range != nullptr) {
ValueBound lower = right_range->GetLower();
ValueBound upper = right_range->GetUpper();
- if (lower.IsConstant() && upper.IsRelativeToArrayLength()) {
+ if (lower.IsConstant() && upper.IsRelatedToArrayLength()) {
HInstruction* upper_inst = upper.GetInstruction();
- if (upper_inst->IsArrayLength() &&
- upper_inst->AsArrayLength() == array_length) {
+ // Make sure it's the same array.
+ if (ValueBound::Equal(array_length, upper_inst)) {
// (array.length - v) where v is in [c1, array.length + c2]
// gets [-c2, array.length - c1] as its value range.
ValueRange* range = new (GetGraph()->GetArena()) ValueRange(
@@ -699,6 +728,26 @@
}
}
+ void VisitNewArray(HNewArray* new_array) {
+ HInstruction* len = new_array->InputAt(0);
+ if (!len->IsIntConstant()) {
+ HInstruction *left;
+ int32_t right_const;
+ if (ValueBound::IsAddOrSubAConstant(len, &left, &right_const)) {
+ // (left + right_const) is used as size to new the array.
+ // We record "-right_const <= left <= new_array - right_const";
+ ValueBound lower = ValueBound(nullptr, -right_const);
+ // We use new_array for the bound instead of new_array.length,
+ // which isn't available as an instruction yet. new_array will
+ // be treated the same as new_array.length when it's used in a ValueBound.
+ ValueBound upper = ValueBound(new_array, -right_const);
+ ValueRange* range = new (GetGraph()->GetArena())
+ ValueRange(GetGraph()->GetArena(), lower, upper);
+ GetValueRangeMap(new_array->GetBlock())->Overwrite(left->GetId(), range);
+ }
+ }
+ }
+
std::vector<std::unique_ptr<ArenaSafeMap<int, ValueRange*>>> maps_;
DISALLOW_COPY_AND_ASSIGN(BCEVisitor);
diff --git a/compiler/optimizing/bounds_check_elimination_test.cc b/compiler/optimizing/bounds_check_elimination_test.cc
index 3dcb08d..662834a 100644
--- a/compiler/optimizing/bounds_check_elimination_test.cc
+++ b/compiler/optimizing/bounds_check_elimination_test.cc
@@ -17,6 +17,7 @@
#include "bounds_check_elimination.h"
#include "builder.h"
#include "gvn.h"
+#include "instruction_simplifier.h"
#include "nodes.h"
#include "optimizing_unit_test.h"
#include "side_effects_analysis.h"
@@ -26,7 +27,9 @@
namespace art {
-static void RunGvn(HGraph* graph) {
+static void RunSimplifierAndGvn(HGraph* graph) {
+ InstructionSimplifier simplify(graph);
+ simplify.Run();
SideEffectsAnalysis side_effects(graph);
side_effects.Run();
GVNOptimization(graph, side_effects).Run();
@@ -127,7 +130,7 @@
block3->AddSuccessor(block4); // False successor
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination(graph);
bounds_check_elimination.Run();
ASSERT_FALSE(IsRemoved(bounds_check2));
@@ -202,7 +205,7 @@
block3->AddSuccessor(exit);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination(graph);
bounds_check_elimination.Run();
ASSERT_FALSE(IsRemoved(bounds_check));
@@ -277,7 +280,7 @@
block3->AddSuccessor(exit);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination(graph);
bounds_check_elimination.Run();
ASSERT_FALSE(IsRemoved(bounds_check));
@@ -351,7 +354,7 @@
exit->AddInstruction(new (&allocator) HExit());
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination(graph);
bounds_check_elimination.Run();
ASSERT_FALSE(IsRemoved(bounds_check5));
@@ -450,7 +453,7 @@
// HArrayLength which uses the null check as its input.
graph = BuildSSAGraph1(&allocator, &bounds_check, 0, 1);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_after_gvn(graph);
bounds_check_elimination_after_gvn.Run();
ASSERT_TRUE(IsRemoved(bounds_check));
@@ -458,7 +461,7 @@
// for (int i=1; i<array.length; i++) { array[i] = 10; // Can eliminate. }
graph = BuildSSAGraph1(&allocator, &bounds_check, 1, 1);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_initial_1(graph);
bounds_check_elimination_with_initial_1.Run();
ASSERT_TRUE(IsRemoved(bounds_check));
@@ -466,7 +469,7 @@
// for (int i=-1; i<array.length; i++) { array[i] = 10; // Can't eliminate. }
graph = BuildSSAGraph1(&allocator, &bounds_check, -1, 1);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_initial_minus_1(graph);
bounds_check_elimination_with_initial_minus_1.Run();
ASSERT_FALSE(IsRemoved(bounds_check));
@@ -474,7 +477,7 @@
// for (int i=0; i<=array.length; i++) { array[i] = 10; // Can't eliminate. }
graph = BuildSSAGraph1(&allocator, &bounds_check, 0, 1, kCondGT);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_greater_than(graph);
bounds_check_elimination_with_greater_than.Run();
ASSERT_FALSE(IsRemoved(bounds_check));
@@ -483,7 +486,7 @@
// array[i] = 10; // Can't eliminate due to overflow concern. }
graph = BuildSSAGraph1(&allocator, &bounds_check, 0, 2);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_increment_2(graph);
bounds_check_elimination_with_increment_2.Run();
ASSERT_FALSE(IsRemoved(bounds_check));
@@ -491,7 +494,7 @@
// for (int i=1; i<array.length; i += 2) { array[i] = 10; // Can eliminate. }
graph = BuildSSAGraph1(&allocator, &bounds_check, 1, 2);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_increment_2_from_1(graph);
bounds_check_elimination_with_increment_2_from_1.Run();
ASSERT_TRUE(IsRemoved(bounds_check));
@@ -591,7 +594,7 @@
// HArrayLength which uses the null check as its input.
graph = BuildSSAGraph2(&allocator, &bounds_check, 0);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_after_gvn(graph);
bounds_check_elimination_after_gvn.Run();
ASSERT_TRUE(IsRemoved(bounds_check));
@@ -599,7 +602,7 @@
// for (int i=array.length; i>1; i--) { array[i-1] = 10; // Can eliminate. }
graph = BuildSSAGraph2(&allocator, &bounds_check, 1);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_initial_1(graph);
bounds_check_elimination_with_initial_1.Run();
ASSERT_TRUE(IsRemoved(bounds_check));
@@ -607,7 +610,7 @@
// for (int i=array.length; i>-1; i--) { array[i-1] = 10; // Can't eliminate. }
graph = BuildSSAGraph2(&allocator, &bounds_check, -1);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_initial_minus_1(graph);
bounds_check_elimination_with_initial_minus_1.Run();
ASSERT_FALSE(IsRemoved(bounds_check));
@@ -615,7 +618,7 @@
// for (int i=array.length; i>=0; i--) { array[i-1] = 10; // Can't eliminate. }
graph = BuildSSAGraph2(&allocator, &bounds_check, 0, -1, kCondLT);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_less_than(graph);
bounds_check_elimination_with_less_than.Run();
ASSERT_FALSE(IsRemoved(bounds_check));
@@ -623,7 +626,7 @@
// for (int i=array.length; i>0; i-=2) { array[i-1] = 10; // Can eliminate. }
graph = BuildSSAGraph2(&allocator, &bounds_check, 0, -2);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_increment_minus_2(graph);
bounds_check_elimination_increment_minus_2.Run();
ASSERT_TRUE(IsRemoved(bounds_check));
@@ -710,7 +713,7 @@
HInstruction* bounds_check = nullptr;
HGraph* graph = BuildSSAGraph3(&allocator, &bounds_check, 0, 1, kCondGE);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_after_gvn(graph);
bounds_check_elimination_after_gvn.Run();
ASSERT_TRUE(IsRemoved(bounds_check));
@@ -719,7 +722,7 @@
// for (int i=1; i<10; i++) { array[i] = 10; // Can eliminate. }
graph = BuildSSAGraph3(&allocator, &bounds_check, 1, 1, kCondGE);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_initial_1(graph);
bounds_check_elimination_with_initial_1.Run();
ASSERT_TRUE(IsRemoved(bounds_check));
@@ -728,7 +731,7 @@
// for (int i=0; i<=10; i++) { array[i] = 10; // Can't eliminate. }
graph = BuildSSAGraph3(&allocator, &bounds_check, 0, 1, kCondGT);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_greater_than(graph);
bounds_check_elimination_with_greater_than.Run();
ASSERT_FALSE(IsRemoved(bounds_check));
@@ -737,7 +740,7 @@
// for (int i=1; i<10; i+=8) { array[i] = 10; // Can eliminate. }
graph = BuildSSAGraph3(&allocator, &bounds_check, 1, 8, kCondGE);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_increment_8(graph);
bounds_check_elimination_increment_8.Run();
ASSERT_TRUE(IsRemoved(bounds_check));
@@ -838,7 +841,7 @@
// HArrayLength which uses the null check as its input.
graph = BuildSSAGraph4(&allocator, &bounds_check, 0);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_after_gvn(graph);
bounds_check_elimination_after_gvn.Run();
ASSERT_TRUE(IsRemoved(bounds_check));
@@ -846,7 +849,7 @@
// for (int i=1; i<array.length; i++) { array[array.length-i-1] = 10; // Can eliminate. }
graph = BuildSSAGraph4(&allocator, &bounds_check, 1);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_initial_1(graph);
bounds_check_elimination_with_initial_1.Run();
ASSERT_TRUE(IsRemoved(bounds_check));
@@ -854,7 +857,7 @@
// for (int i=0; i<=array.length; i++) { array[array.length-i] = 10; // Can't eliminate. }
graph = BuildSSAGraph4(&allocator, &bounds_check, 0, kCondGT);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_greater_than(graph);
bounds_check_elimination_with_greater_than.Run();
ASSERT_FALSE(IsRemoved(bounds_check));
@@ -1030,7 +1033,7 @@
outer_body_add->AddSuccessor(outer_header);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
// gvn should remove the same bounds check.
ASSERT_FALSE(IsRemoved(bounds_check1));
ASSERT_FALSE(IsRemoved(bounds_check2));
diff --git a/compiler/optimizing/instruction_simplifier.cc b/compiler/optimizing/instruction_simplifier.cc
index 17c8f33..44dbb9d 100644
--- a/compiler/optimizing/instruction_simplifier.cc
+++ b/compiler/optimizing/instruction_simplifier.cc
@@ -28,6 +28,7 @@
void VisitArraySet(HArraySet* equal) OVERRIDE;
void VisitTypeConversion(HTypeConversion* instruction) OVERRIDE;
void VisitNullCheck(HNullCheck* instruction) OVERRIDE;
+ void VisitArrayLength(HArrayLength* instruction) OVERRIDE;
};
void InstructionSimplifier::Run() {
@@ -75,6 +76,18 @@
}
}
+void InstructionSimplifierVisitor::VisitArrayLength(HArrayLength* instruction) {
+ HInstruction* input = instruction->InputAt(0);
+ // If the array is a NewArray with constant size, replace the array length
+ // with the constant instruction. This helps the bounds check elimination phase.
+ if (input->IsNewArray()) {
+ input = input->InputAt(0);
+ if (input->IsIntConstant()) {
+ instruction->ReplaceWith(input);
+ }
+ }
+}
+
void InstructionSimplifierVisitor::VisitArraySet(HArraySet* instruction) {
HInstruction* value = instruction->GetValue();
if (value->GetType() != Primitive::kPrimNot) return;