diff options
| -rw-r--r-- | build/Android.gtest.mk | 1 | ||||
| -rw-r--r-- | compiler/Android.mk | 1 | ||||
| -rw-r--r-- | compiler/optimizing/bounds_check_elimination.cc | 691 | ||||
| -rw-r--r-- | compiler/optimizing/bounds_check_elimination.h | 36 | ||||
| -rw-r--r-- | compiler/optimizing/bounds_check_elimination_test.cc | 1045 | ||||
| -rw-r--r-- | compiler/optimizing/optimizing_compiler.cc | 7 | ||||
| -rw-r--r-- | compiler/optimizing/optimizing_unit_test.h | 5 |
7 files changed, 1784 insertions, 2 deletions
diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk index 10b0400109..bb634f7ca3 100644 --- a/build/Android.gtest.mk +++ b/build/Android.gtest.mk @@ -147,6 +147,7 @@ COMPILER_GTEST_COMMON_SRC_FILES := \ compiler/image_test.cc \ compiler/jni/jni_compiler_test.cc \ compiler/oat_test.cc \ + compiler/optimizing/bounds_check_elimination_test.cc \ compiler/optimizing/codegen_test.cc \ compiler/optimizing/dead_code_elimination_test.cc \ compiler/optimizing/constant_folding_test.cc \ diff --git a/compiler/Android.mk b/compiler/Android.mk index 70c7e521a6..a75417bcbc 100644 --- a/compiler/Android.mk +++ b/compiler/Android.mk @@ -86,6 +86,7 @@ LIBART_COMPILER_SRC_FILES := \ jni/quick/jni_compiler.cc \ llvm/llvm_compiler.cc \ optimizing/builder.cc \ + optimizing/bounds_check_elimination.cc \ optimizing/code_generator.cc \ optimizing/code_generator_arm.cc \ optimizing/code_generator_arm64.cc \ diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc new file mode 100644 index 0000000000..91455bc7c4 --- /dev/null +++ b/compiler/optimizing/bounds_check_elimination.cc @@ -0,0 +1,691 @@ +/* + * Copyright (C) 2014 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "bounds_check_elimination.h" +#include "nodes.h" +#include "utils/arena_containers.h" + +namespace art { + +class MonotonicValueRange; + +/** + * A value bound is represented as a pair of value and constant, + * e.g. array.length - 1. + */ +class ValueBound : public ValueObject { + public: + static ValueBound Create(HInstruction* instruction, int constant) { + if (instruction == nullptr) { + return ValueBound(nullptr, constant); + } + if (instruction->IsIntConstant()) { + return ValueBound(nullptr, instruction->AsIntConstant()->GetValue() + constant); + } + return ValueBound(instruction, constant); + } + + HInstruction* GetInstruction() const { return instruction_; } + int GetConstant() const { return constant_; } + + bool IsRelativeToArrayLength() const { + return instruction_ != nullptr && instruction_->IsArrayLength(); + } + + bool IsConstant() const { + return instruction_ == nullptr; + } + + static ValueBound Min() { return ValueBound(nullptr, INT_MIN); } + static ValueBound Max() { return ValueBound(nullptr, INT_MAX); } + + bool Equals(ValueBound bound) const { + 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. + return false; + } + // 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; + } + } + + // 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; + } + + // 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_)); + } + + // Not comparable. Just pick one. We may lose some info, but that's ok. + // Favor constant as lower bound. + return bound1.IsConstant() ? bound1 : bound2; + } + + // 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_)); + } + + // 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; + } + + // 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 for_lower_bound, bool* overflow_or_underflow) const { + *overflow_or_underflow = false; + if (c == 0) { + return *this; + } + + int new_constant; + if (c > 0) { + if (constant_ > INT_MAX - c) { + // Constant part overflows. + *overflow_or_underflow = true; + return for_lower_bound ? Min() : Max(); + } else { + new_constant = constant_ + c; + } + } else { + if (constant_ < INT_MIN - c) { + // Constant part underflows. + *overflow_or_underflow = true; + return for_lower_bound ? Min() : Max(); + } else { + new_constant = constant_ + c; + } + } + return ValueBound(instruction_, new_constant); + } + + private: + ValueBound(HInstruction* instruction, int constant) + : instruction_(instruction), constant_(constant) {} + + HInstruction* instruction_; + int 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 + * incrementing/decrementing array index (MonotonicValueRange). + */ +class ValueRange : public ArenaObject<kArenaAllocMisc> { + public: + ValueRange(ArenaAllocator* allocator, ValueBound lower, ValueBound upper) + : allocator_(allocator), lower_(lower), upper_(upper) {} + + virtual ~ValueRange() {} + + virtual const MonotonicValueRange* AsMonotonicValueRange() const { return nullptr; } + bool IsMonotonicValueRange() const { + return AsMonotonicValueRange() != nullptr; + } + + ArenaAllocator* GetAllocator() const { return allocator_; } + ValueBound GetLower() const { return lower_; } + ValueBound GetUpper() const { return upper_; } + + // If it's certain that this value range fits in other_range. + virtual bool FitsIn(ValueRange* other_range) const { + if (other_range == nullptr) { + return true; + } + DCHECK(!other_range->IsMonotonicValueRange()); + return lower_.GreaterThanOrEqual(other_range->lower_) && + upper_.LessThanOrEqual(other_range->upper_); + } + + // Returns the intersection of this and range. + // If it's not possible to do intersection because some + // bounds are not comparable, it's ok to pick either bound. + virtual ValueRange* Narrow(ValueRange* range) { + if (range == nullptr) { + return this; + } + + if (range->IsMonotonicValueRange()) { + return this; + } + + return new (allocator_) ValueRange( + allocator_, + ValueBound::NarrowLowerBound(lower_, range->lower_), + 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, true, &overflow_or_underflow); + if (overflow_or_underflow) { + // We can't accurately represent the bounds anymore. + return FullIntRange(); + } + ValueBound upper = upper_.Add(constant, false, &overflow_or_underflow); + if (overflow_or_underflow) { + // We can't accurately represent the bounds anymore. + return FullIntRange(); + } + 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 + const ValueBound upper_; // inclusive + + DISALLOW_COPY_AND_ASSIGN(ValueRange); +}; + +/** + * A monotonically incrementing/decrementing value range, e.g. + * the variable i in "for (int i=0; i<array.length; i++)". + * Special care needs to be taken to account for overflow/underflow + * of such value ranges. + */ +class MonotonicValueRange : public ValueRange { + public: + static MonotonicValueRange* Create(ArenaAllocator* allocator, + HInstruction* initial, int increment) { + DCHECK_NE(increment, 0); + // 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. + return new (allocator) MonotonicValueRange( + allocator, ValueBound::Min(), ValueBound::Max(), initial, increment); + } + + virtual ~MonotonicValueRange() {} + + const MonotonicValueRange* AsMonotonicValueRange() const OVERRIDE { return this; } + + // If it's certain that this value range fits in other_range. + bool FitsIn(ValueRange* other_range) const OVERRIDE { + if (other_range == nullptr) { + return true; + } + DCHECK(!other_range->IsMonotonicValueRange()); + return false; + } + + // Try to narrow this MonotonicValueRange given another range. + // Ideally it will return a normal ValueRange. But due to + // possible overflow/underflow, that may not be possible. + ValueRange* Narrow(ValueRange* range) OVERRIDE { + if (range == nullptr) { + return this; + } + DCHECK(!range->IsMonotonicValueRange()); + + if (increment_ > 0) { + // Monotonically increasing. + ValueBound lower = ValueBound::NarrowLowerBound( + ValueBound::Create(initial_, 0), range->GetLower()); + + // 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, + // 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; + + 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; + } + + // If we can prove for the last number in sequence of initial_, + // initial_ + increment_, initial_ + 2 x increment_, ... + // that's <= upper, (last_num_in_sequence + increment_) doesn't trigger overflow, + // 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; + if (initial_->IsIntConstant()) { + int 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. + last_num_in_sequence = initial_constant + + ((int64_t)upper - (int64_t)initial_constant) / increment_ * increment_; + } + } + if (last_num_in_sequence <= INT_MAX - increment_) { + // No overflow. The sequence will be stopped by the upper bound test as expected. + return new (GetAllocator()) ValueRange(GetAllocator(), lower, range->GetUpper()); + } + + // There might be overflow. Give up narrowing. + return this; + } else { + DCHECK_NE(increment_, 0); + // Monotonically decreasing. + ValueBound upper = ValueBound::NarrowUpperBound( + ValueBound::Create(initial_, 0), 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. + if (range->GetLower().IsConstant()) { + int constant = range->GetLower().GetConstant(); + if (constant >= INT_MIN - increment_) { + return new (GetAllocator()) ValueRange(GetAllocator(), range->GetLower(), upper); + } + } + + // There might be underflow. Give up narrowing. + return this; + } + } + + private: + MonotonicValueRange(ArenaAllocator* allocator, ValueBound lower, + ValueBound upper, HInstruction* initial, int increment) + : ValueRange(allocator, lower, upper), + initial_(initial), + increment_(increment) {} + + HInstruction* const initial_; + const int increment_; + + DISALLOW_COPY_AND_ASSIGN(MonotonicValueRange); +}; + +class BCEVisitor : public HGraphVisitor { + public: + BCEVisitor(HGraph* graph) + : HGraphVisitor(graph), + maps_(graph->GetBlocks().Size()) {} + + private: + // Return the map of proven value ranges at the beginning of a basic block. + ArenaSafeMap<int, ValueRange*>* GetValueRangeMap(HBasicBlock* basic_block) { + int block_id = basic_block->GetBlockId(); + if (maps_.at(block_id) == nullptr) { + std::unique_ptr<ArenaSafeMap<int, ValueRange*>> map( + new ArenaSafeMap<int, ValueRange*>( + std::less<int>(), GetGraph()->GetArena()->Adapter())); + maps_.at(block_id) = std::move(map); + } + return maps_.at(block_id).get(); + } + + // Traverse up the dominator tree to look for value range info. + ValueRange* LookupValueRange(HInstruction* instruction, HBasicBlock* basic_block) { + while (basic_block != nullptr) { + ArenaSafeMap<int, ValueRange*>* map = GetValueRangeMap(basic_block); + if (map->find(instruction->GetId()) != map->end()) { + return map->Get(instruction->GetId()); + } + basic_block = basic_block->GetDominator(); + } + // Didn't find any. + return nullptr; + } + + // Try to detect useful value bound format from an instruction, e.g. + // a constant or array length related value. + ValueBound DetectValueBoundFromValue(HInstruction* instruction) { + if (instruction->IsIntConstant()) { + return ValueBound::Create(nullptr, instruction->AsIntConstant()->GetValue()); + } + + if (instruction->IsArrayLength()) { + return ValueBound::Create(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()) { + return ValueBound::Create(left, right->AsIntConstant()->GetValue()); + } + } + + // No useful bound detected. + return ValueBound::Max(); + } + + // 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); + ValueRange* narrowed_range = (existing_range == nullptr) ? + range : existing_range->Narrow(range); + if (narrowed_range != nullptr) { + GetValueRangeMap(successor)->Overwrite(instruction->GetId(), narrowed_range); + } + } + + // Handle "if (left cmp_cond right)". + void HandleIf(HIf* instruction, HInstruction* left, HInstruction* right, IfCondition cond) { + HBasicBlock* block = instruction->GetBlock(); + + HBasicBlock* true_successor = instruction->IfTrueSuccessor(); + // There should be no critical edge at this point. + DCHECK_EQ(true_successor->GetPredecessors().Size(), 1u); + + HBasicBlock* false_successor = instruction->IfFalseSuccessor(); + // There should be no critical edge at this point. + DCHECK_EQ(false_successor->GetPredecessors().Size(), 1u); + + ValueBound bound = DetectValueBoundFromValue(right); + bool found = !bound.Equals(ValueBound::Max()); + + ValueBound lower = bound; + ValueBound upper = bound; + if (!found) { + // No constant or array.length+c 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) { + lower = range->GetLower(); + upper = range->GetUpper(); + } else { + lower = ValueBound::Min(); + upper = ValueBound::Max(); + } + } + + bool overflow_or_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, false, &overflow_or_underflow); + // overflow_or_underflow is ignored here since we already use ValueBound::Min() + // for lower bound. + ValueRange* new_range = new (GetGraph()->GetArena()) + ValueRange(GetGraph()->GetArena(), ValueBound::Min(), new_upper); + ApplyRangeFromComparison(left, block, true_successor, new_range); + } + + // 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, true, &overflow_or_underflow); + // overflow_or_underflow is ignored here since we already use ValueBound::Max() + // for upper bound. + ValueRange* new_range = new (GetGraph()->GetArena()) + ValueRange(GetGraph()->GetArena(), new_lower, ValueBound::Max()); + ApplyRangeFromComparison(left, block, false_successor, new_range); + } + } 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, true, &overflow_or_underflow); + // overflow_or_underflow is ignored here since we already use ValueBound::Max() + // for upper bound. + ValueRange* new_range = new (GetGraph()->GetArena()) + ValueRange(GetGraph()->GetArena(), new_lower, ValueBound::Max()); + ApplyRangeFromComparison(left, block, true_successor, new_range); + } + + if (!upper.Equals(ValueBound::Max())) { + int compensation = (cond == kCondGE) ? -1 : 0; // upper bound is inclusive + ValueBound new_upper = upper.Add(compensation, false, &overflow_or_underflow); + // overflow_or_underflow is ignored here since we already use ValueBound::Min() + // for lower bound. + ValueRange* new_range = new (GetGraph()->GetArena()) + ValueRange(GetGraph()->GetArena(), ValueBound::Min(), new_upper); + ApplyRangeFromComparison(left, block, false_successor, new_range); + } + } + } + + void VisitBoundsCheck(HBoundsCheck* bounds_check) { + HBasicBlock* block = bounds_check->GetBlock(); + HInstruction* index = bounds_check->InputAt(0); + HInstruction* array_length = bounds_check->InputAt(1); + ValueRange* index_range = LookupValueRange(index, block); + + if (index_range != nullptr) { + ValueBound lower = ValueBound::Create(nullptr, 0); // constant 0 + ValueBound upper = ValueBound::Create(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()) { + ReplaceBoundsCheck(bounds_check, index); + return; + } + } + + // Once we have an array access like 'array[5] = 1', we record array.length >= 6. + ValueBound lower = ValueBound::Create(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); + } + } + + void ReplaceBoundsCheck(HInstruction* bounds_check, HInstruction* index) { + bounds_check->ReplaceWith(index); + bounds_check->GetBlock()->RemoveInstruction(bounds_check); + } + + void VisitPhi(HPhi* phi) { + if (phi->IsLoopHeaderPhi() && phi->GetType() == Primitive::kPrimInt) { + DCHECK(phi->InputCount() == 2); + 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* initial_value = phi->InputAt(0); + ValueRange* range = nullptr; + if (right->AsIntConstant()->GetValue() == 0) { + // Add constant 0. It's really a fixed value. + range = new (GetGraph()->GetArena()) ValueRange( + GetGraph()->GetArena(), + ValueBound::Create(initial_value, 0), + ValueBound::Create(initial_value, 0)); + } else { + // Monotonically increasing/decreasing. + range = MonotonicValueRange::Create( + GetGraph()->GetArena(), + initial_value, + right->AsIntConstant()->GetValue()); + } + GetValueRangeMap(phi->GetBlock())->Overwrite(phi->GetId(), range); + } + } + } + } + + void VisitIf(HIf* instruction) { + if (instruction->InputAt(0)->IsCondition()) { + HCondition* cond = instruction->InputAt(0)->AsCondition(); + IfCondition cmp = cond->GetCondition(); + if (cmp == kCondGT || cmp == kCondGE || + cmp == kCondLT || cmp == kCondLE) { + HInstruction* left = cond->GetLeft(); + HInstruction* right = cond->GetRight(); + HandleIf(instruction, left, right, cmp); + } + } + } + + void VisitAdd(HAdd* add) { + HInstruction* right = add->GetRight(); + if (right->IsIntConstant()) { + ValueRange* left_range = LookupValueRange(add->GetLeft(), add->GetBlock()); + if (left_range == nullptr) { + return; + } + ValueRange* range = left_range->Add(right->AsIntConstant()->GetValue()); + if (range != nullptr) { + GetValueRangeMap(add->GetBlock())->Overwrite(add->GetId(), range); + } + } + } + + void VisitSub(HSub* sub) { + HInstruction* left = sub->GetLeft(); + HInstruction* right = sub->GetRight(); + if (right->IsIntConstant()) { + ValueRange* left_range = LookupValueRange(left, sub->GetBlock()); + if (left_range == nullptr) { + return; + } + ValueRange* range = left_range->Add(-right->AsIntConstant()->GetValue()); + if (range != nullptr) { + GetValueRangeMap(sub->GetBlock())->Overwrite(sub->GetId(), range); + return; + } + } + + // Here we are interested in the typical triangular case of nested loops, + // such as the inner loop 'for (int j=0; j<array.length-i; j++)' where i + // is the index for outer loop. In this case, we know j is bounded by array.length-1. + if (left->IsArrayLength()) { + HInstruction* array_length = left->AsArrayLength(); + ValueRange* right_range = LookupValueRange(right, sub->GetBlock()); + if (right_range != nullptr) { + ValueBound lower = right_range->GetLower(); + ValueBound upper = right_range->GetUpper(); + if (lower.IsConstant() && upper.IsRelativeToArrayLength()) { + HInstruction* upper_inst = upper.GetInstruction(); + if (upper_inst->IsArrayLength() && + upper_inst->AsArrayLength() == array_length) { + // (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( + GetGraph()->GetArena(), + ValueBound::Create(nullptr, - upper.GetConstant()), + ValueBound::Create(array_length, - lower.GetConstant())); + GetValueRangeMap(sub->GetBlock())->Overwrite(sub->GetId(), range); + } + } + } + } + } + + std::vector<std::unique_ptr<ArenaSafeMap<int, ValueRange*>>> maps_; + + DISALLOW_COPY_AND_ASSIGN(BCEVisitor); +}; + +void BoundsCheckElimination::Run() { + BCEVisitor visitor(graph_); + // Reverse post order guarantees a node's dominators are visited first. + // We want to visit in the dominator-based order since if a value is known to + // be bounded by a range at one instruction, it must be true that all uses of + // that value dominated by that instruction fits in that range. Range of that + // value can be narrowed further down in the dominator tree. + // + // TODO: only visit blocks that dominate some array accesses. + visitor.VisitReversePostOrder(); +} + +} // namespace art diff --git a/compiler/optimizing/bounds_check_elimination.h b/compiler/optimizing/bounds_check_elimination.h new file mode 100644 index 0000000000..25551d55ca --- /dev/null +++ b/compiler/optimizing/bounds_check_elimination.h @@ -0,0 +1,36 @@ +/* + * Copyright (C) 2014 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef ART_COMPILER_OPTIMIZING_BOUNDS_CHECK_ELIMINATION_H_ +#define ART_COMPILER_OPTIMIZING_BOUNDS_CHECK_ELIMINATION_H_ + +#include "optimization.h" + +namespace art { + +class BoundsCheckElimination : public HOptimization { + public: + BoundsCheckElimination(HGraph* graph) : HOptimization(graph, true, "BCE") {} + + void Run() OVERRIDE; + + private: + DISALLOW_COPY_AND_ASSIGN(BoundsCheckElimination); +}; + +} // namespace art + +#endif // ART_COMPILER_OPTIMIZING_BOUNDS_CHECK_ELIMINATION_H_ diff --git a/compiler/optimizing/bounds_check_elimination_test.cc b/compiler/optimizing/bounds_check_elimination_test.cc new file mode 100644 index 0000000000..5e2e62c5ea --- /dev/null +++ b/compiler/optimizing/bounds_check_elimination_test.cc @@ -0,0 +1,1045 @@ +/* + * Copyright (C) 2014 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "bounds_check_elimination.h" +#include "builder.h" +#include "gvn.h" +#include "nodes.h" +#include "optimizing_unit_test.h" +#include "utils/arena_allocator.h" + +#include "gtest/gtest.h" + +namespace art { + +// if (i < 0) { array[i] = 1; // Can't eliminate. } +// else if (i >= array.length) { array[i] = 1; // Can't eliminate. } +// else { array[i] = 1; // Can eliminate. } +TEST(BoundsCheckEliminationTest, NarrowingRangeArrayBoundsElimination) { + ArenaPool pool; + ArenaAllocator allocator(&pool); + + HGraph* graph = new (&allocator) HGraph(&allocator); + + HBasicBlock* entry = new (&allocator) HBasicBlock(graph); + graph->AddBlock(entry); + graph->SetEntryBlock(entry); + HInstruction* parameter1 = new (&allocator) + HParameterValue(0, Primitive::kPrimNot); // array + HInstruction* parameter2 = new (&allocator) + HParameterValue(0, Primitive::kPrimInt); // i + HInstruction* constant_1 = new (&allocator) HIntConstant(1); + HInstruction* constant_0 = new (&allocator) HIntConstant(0); + entry->AddInstruction(parameter1); + entry->AddInstruction(parameter2); + entry->AddInstruction(constant_1); + entry->AddInstruction(constant_0); + + HBasicBlock* block1 = new (&allocator) HBasicBlock(graph); + graph->AddBlock(block1); + HInstruction* cmp = new (&allocator) HGreaterThanOrEqual(parameter2, constant_0); + HIf* if_inst = new (&allocator) HIf(cmp); + block1->AddInstruction(cmp); + block1->AddInstruction(if_inst); + entry->AddSuccessor(block1); + + HBasicBlock* block2 = new (&allocator) HBasicBlock(graph); + graph->AddBlock(block2); + HNullCheck* null_check = new (&allocator) HNullCheck(parameter1, 0); + HArrayLength* array_length = new (&allocator) HArrayLength(null_check); + HBoundsCheck* bounds_check2 = new (&allocator) + HBoundsCheck(parameter2, array_length, 0); + HArraySet* array_set = new (&allocator) HArraySet( + null_check, bounds_check2, constant_1, Primitive::kPrimInt, 0); + block2->AddInstruction(null_check); + block2->AddInstruction(array_length); + block2->AddInstruction(bounds_check2); + block2->AddInstruction(array_set); + + HBasicBlock* block3 = new (&allocator) HBasicBlock(graph); + graph->AddBlock(block3); + null_check = new (&allocator) HNullCheck(parameter1, 0); + array_length = new (&allocator) HArrayLength(null_check); + cmp = new (&allocator) HLessThan(parameter2, array_length); + if_inst = new (&allocator) HIf(cmp); + block3->AddInstruction(null_check); + block3->AddInstruction(array_length); + block3->AddInstruction(cmp); + block3->AddInstruction(if_inst); + + HBasicBlock* block4 = new (&allocator) HBasicBlock(graph); + graph->AddBlock(block4); + null_check = new (&allocator) HNullCheck(parameter1, 0); + array_length = new (&allocator) HArrayLength(null_check); + HBoundsCheck* bounds_check4 = new (&allocator) + HBoundsCheck(parameter2, array_length, 0); + array_set = new (&allocator) HArraySet( + null_check, bounds_check4, constant_1, Primitive::kPrimInt, 0); + block4->AddInstruction(null_check); + block4->AddInstruction(array_length); + block4->AddInstruction(bounds_check4); + block4->AddInstruction(array_set); + + HBasicBlock* block5 = new (&allocator) HBasicBlock(graph); + graph->AddBlock(block5); + null_check = new (&allocator) HNullCheck(parameter1, 0); + array_length = new (&allocator) HArrayLength(null_check); + HBoundsCheck* bounds_check5 = new (&allocator) + HBoundsCheck(parameter2, array_length, 0); + array_set = new (&allocator) HArraySet( + null_check, bounds_check5, constant_1, Primitive::kPrimInt, 0); + block5->AddInstruction(null_check); + block5->AddInstruction(array_length); + block5->AddInstruction(bounds_check5); + block5->AddInstruction(array_set); + + HBasicBlock* exit = new (&allocator) HBasicBlock(graph); + graph->AddBlock(exit); + block2->AddSuccessor(exit); + block4->AddSuccessor(exit); + block5->AddSuccessor(exit); + exit->AddInstruction(new (&allocator) HExit()); + + block1->AddSuccessor(block3); // True successor + block1->AddSuccessor(block2); // False successor + + block3->AddSuccessor(block5); // True successor + block3->AddSuccessor(block4); // False successor + + graph->BuildDominatorTree(); + GlobalValueNumberer(&allocator, graph).Run(); + BoundsCheckElimination bounds_check_elimination(graph); + bounds_check_elimination.Run(); + ASSERT_FALSE(IsRemoved(bounds_check2)); + ASSERT_FALSE(IsRemoved(bounds_check4)); + ASSERT_TRUE(IsRemoved(bounds_check5)); +} + +// if (i > 0) { +// // Positive number plus MAX_INT will overflow and be negative. +// int j = i + Integer.MAX_VALUE; +// if (j < array.length) array[j] = 1; // Can't eliminate. +// } +TEST(BoundsCheckEliminationTest, OverflowArrayBoundsElimination) { + ArenaPool pool; + ArenaAllocator allocator(&pool); + + HGraph* graph = new (&allocator) HGraph(&allocator); + + HBasicBlock* entry = new (&allocator) HBasicBlock(graph); + graph->AddBlock(entry); + graph->SetEntryBlock(entry); + HInstruction* parameter1 = new (&allocator) + HParameterValue(0, Primitive::kPrimNot); // array + HInstruction* parameter2 = new (&allocator) + HParameterValue(0, Primitive::kPrimInt); // i + HInstruction* constant_1 = new (&allocator) HIntConstant(1); + HInstruction* constant_0 = new (&allocator) HIntConstant(0); + HInstruction* constant_max_int = new (&allocator) HIntConstant(INT_MAX); + entry->AddInstruction(parameter1); + entry->AddInstruction(parameter2); + entry->AddInstruction(constant_1); + entry->AddInstruction(constant_0); + entry->AddInstruction(constant_max_int); + + HBasicBlock* block1 = new (&allocator) HBasicBlock(graph); + graph->AddBlock(block1); + HInstruction* cmp = new (&allocator) HLessThanOrEqual(parameter2, constant_0); + HIf* if_inst = new (&allocator) HIf(cmp); + block1->AddInstruction(cmp); + block1->AddInstruction(if_inst); + entry->AddSuccessor(block1); + + HBasicBlock* block2 = new (&allocator) HBasicBlock(graph); + graph->AddBlock(block2); + HInstruction* add = new (&allocator) HAdd(Primitive::kPrimInt, parameter2, constant_max_int); + HNullCheck* null_check = new (&allocator) HNullCheck(parameter1, 0); + HArrayLength* array_length = new (&allocator) HArrayLength(null_check); + HInstruction* cmp2 = new (&allocator) HGreaterThanOrEqual(add, array_length); + if_inst = new (&allocator) HIf(cmp2); + block2->AddInstruction(add); + block2->AddInstruction(null_check); + block2->AddInstruction(array_length); + block2->AddInstruction(cmp2); + block2->AddInstruction(if_inst); + + HBasicBlock* block3 = new (&allocator) HBasicBlock(graph); + graph->AddBlock(block3); + HBoundsCheck* bounds_check = new (&allocator) + HBoundsCheck(add, array_length, 0); + HArraySet* array_set = new (&allocator) HArraySet( + null_check, bounds_check, constant_1, Primitive::kPrimInt, 0); + block3->AddInstruction(bounds_check); + block3->AddInstruction(array_set); + + HBasicBlock* exit = new (&allocator) HBasicBlock(graph); + graph->AddBlock(exit); + exit->AddInstruction(new (&allocator) HExit()); + block1->AddSuccessor(exit); // true successor + block1->AddSuccessor(block2); // false successor + block2->AddSuccessor(exit); // true successor + block2->AddSuccessor(block3); // false successor + block3->AddSuccessor(exit); + + graph->BuildDominatorTree(); + GlobalValueNumberer(&allocator, graph).Run(); + BoundsCheckElimination bounds_check_elimination(graph); + bounds_check_elimination.Run(); + ASSERT_FALSE(IsRemoved(bounds_check)); +} + +// if (i < array.length) { +// int j = i - Integer.MAX_VALUE; +// j = j - Integer.MAX_VALUE; // j is (i+2) after substracting MAX_INT twice +// if (j > 0) array[j] = 1; // Can't eliminate. +// } +TEST(BoundsCheckEliminationTest, UnderflowArrayBoundsElimination) { + ArenaPool pool; + ArenaAllocator allocator(&pool); + + HGraph* graph = new (&allocator) HGraph(&allocator); + + HBasicBlock* entry = new (&allocator) HBasicBlock(graph); + graph->AddBlock(entry); + graph->SetEntryBlock(entry); + HInstruction* parameter1 = new (&allocator) + HParameterValue(0, Primitive::kPrimNot); // array + HInstruction* parameter2 = new (&allocator) + HParameterValue(0, Primitive::kPrimInt); // i + HInstruction* constant_1 = new (&allocator) HIntConstant(1); + HInstruction* constant_0 = new (&allocator) HIntConstant(0); + HInstruction* constant_max_int = new (&allocator) HIntConstant(INT_MAX); + entry->AddInstruction(parameter1); + entry->AddInstruction(parameter2); + entry->AddInstruction(constant_1); + entry->AddInstruction(constant_0); + entry->AddInstruction(constant_max_int); + + HBasicBlock* block1 = new (&allocator) HBasicBlock(graph); + graph->AddBlock(block1); + HNullCheck* null_check = new (&allocator) HNullCheck(parameter1, 0); + HArrayLength* array_length = new (&allocator) HArrayLength(null_check); + HInstruction* cmp = new (&allocator) HGreaterThanOrEqual(parameter2, array_length); + HIf* if_inst = new (&allocator) HIf(cmp); + block1->AddInstruction(null_check); + block1->AddInstruction(array_length); + block1->AddInstruction(cmp); + block1->AddInstruction(if_inst); + entry->AddSuccessor(block1); + + HBasicBlock* block2 = new (&allocator) HBasicBlock(graph); + graph->AddBlock(block2); + HInstruction* sub1 = new (&allocator) HSub(Primitive::kPrimInt, parameter2, constant_max_int); + HInstruction* sub2 = new (&allocator) HSub(Primitive::kPrimInt, sub1, constant_max_int); + HInstruction* cmp2 = new (&allocator) HLessThanOrEqual(sub2, constant_0); + if_inst = new (&allocator) HIf(cmp2); + block2->AddInstruction(sub1); + block2->AddInstruction(sub2); + block2->AddInstruction(cmp2); + block2->AddInstruction(if_inst); + + HBasicBlock* block3 = new (&allocator) HBasicBlock(graph); + graph->AddBlock(block3); + HBoundsCheck* bounds_check = new (&allocator) + HBoundsCheck(sub2, array_length, 0); + HArraySet* array_set = new (&allocator) HArraySet( + null_check, bounds_check, constant_1, Primitive::kPrimInt, 0); + block3->AddInstruction(bounds_check); + block3->AddInstruction(array_set); + + HBasicBlock* exit = new (&allocator) HBasicBlock(graph); + graph->AddBlock(exit); + exit->AddInstruction(new (&allocator) HExit()); + block1->AddSuccessor(exit); // true successor + block1->AddSuccessor(block2); // false successor + block2->AddSuccessor(exit); // true successor + block2->AddSuccessor(block3); // false successor + block3->AddSuccessor(exit); + + graph->BuildDominatorTree(); + GlobalValueNumberer(&allocator, graph).Run(); + BoundsCheckElimination bounds_check_elimination(graph); + bounds_check_elimination.Run(); + ASSERT_FALSE(IsRemoved(bounds_check)); +} + +// array[5] = 1; // Can't eliminate. +// array[4] = 1; // Can eliminate. +// array[6] = 1; // Can't eliminate. +TEST(BoundsCheckEliminationTest, ConstantArrayBoundsElimination) { + ArenaPool pool; + ArenaAllocator allocator(&pool); + + HGraph* graph = new (&allocator) HGraph(&allocator); + + HBasicBlock* entry = new (&allocator) HBasicBlock(graph); + graph->AddBlock(entry); + graph->SetEntryBlock(entry); + HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimNot); + HInstruction* constant_5 = new (&allocator) HIntConstant(5); + HInstruction* constant_4 = new (&allocator) HIntConstant(4); + HInstruction* constant_6 = new (&allocator) HIntConstant(6); + HInstruction* constant_1 = new (&allocator) HIntConstant(1); + entry->AddInstruction(parameter); + entry->AddInstruction(constant_5); + entry->AddInstruction(constant_4); + entry->AddInstruction(constant_6); + entry->AddInstruction(constant_1); + + HBasicBlock* block = new (&allocator) HBasicBlock(graph); + graph->AddBlock(block); + entry->AddSuccessor(block); + + HNullCheck* null_check = new (&allocator) HNullCheck(parameter, 0); + HArrayLength* array_length = new (&allocator) HArrayLength(null_check); + HBoundsCheck* bounds_check5 = new (&allocator) + HBoundsCheck(constant_5, array_length, 0); + HInstruction* array_set = new (&allocator) HArraySet( + null_check, bounds_check5, constant_1, Primitive::kPrimInt, 0); + block->AddInstruction(null_check); + block->AddInstruction(array_length); + block->AddInstruction(bounds_check5); + block->AddInstruction(array_set); + + null_check = new (&allocator) HNullCheck(parameter, 0); + array_length = new (&allocator) HArrayLength(null_check); + HBoundsCheck* bounds_check4 = new (&allocator) + HBoundsCheck(constant_4, array_length, 0); + array_set = new (&allocator) HArraySet( + null_check, bounds_check4, constant_1, Primitive::kPrimInt, 0); + block->AddInstruction(null_check); + block->AddInstruction(array_length); + block->AddInstruction(bounds_check4); + block->AddInstruction(array_set); + + null_check = new (&allocator) HNullCheck(parameter, 0); + array_length = new (&allocator) HArrayLength(null_check); + HBoundsCheck* bounds_check6 = new (&allocator) + HBoundsCheck(constant_6, array_length, 0); + array_set = new (&allocator) HArraySet( + null_check, bounds_check6, constant_1, Primitive::kPrimInt, 0); + block->AddInstruction(null_check); + block->AddInstruction(array_length); + block->AddInstruction(bounds_check6); + block->AddInstruction(array_set); + + block->AddInstruction(new (&allocator) HGoto()); + + HBasicBlock* exit = new (&allocator) HBasicBlock(graph); + graph->AddBlock(exit); + block->AddSuccessor(exit); + exit->AddInstruction(new (&allocator) HExit()); + + graph->BuildDominatorTree(); + GlobalValueNumberer(&allocator, graph).Run(); + BoundsCheckElimination bounds_check_elimination(graph); + bounds_check_elimination.Run(); + ASSERT_FALSE(IsRemoved(bounds_check5)); + ASSERT_TRUE(IsRemoved(bounds_check4)); + ASSERT_FALSE(IsRemoved(bounds_check6)); +} + +// for (int i=initial; i<array.length; i+=increment) { array[i] = 10; } +static HGraph* BuildSSAGraph1(ArenaAllocator* allocator, + HInstruction** bounds_check, + int initial, + int increment, + IfCondition cond = kCondGE) { + HGraph* graph = new (allocator) HGraph(allocator); + + HBasicBlock* entry = new (allocator) HBasicBlock(graph); + graph->AddBlock(entry); + graph->SetEntryBlock(entry); + HInstruction* parameter = new (allocator) HParameterValue(0, Primitive::kPrimNot); + HInstruction* constant_initial = new (allocator) HIntConstant(initial); + HInstruction* constant_increment = new (allocator) HIntConstant(increment); + HInstruction* constant_10 = new (allocator) HIntConstant(10); + entry->AddInstruction(parameter); + entry->AddInstruction(constant_initial); + entry->AddInstruction(constant_increment); + entry->AddInstruction(constant_10); + + HBasicBlock* block = new (allocator) HBasicBlock(graph); + graph->AddBlock(block); + entry->AddSuccessor(block); + block->AddInstruction(new (allocator) HGoto()); + + HBasicBlock* loop_header = new (allocator) HBasicBlock(graph); + HBasicBlock* loop_body = new (allocator) HBasicBlock(graph); + HBasicBlock* exit = new (allocator) HBasicBlock(graph); + + graph->AddBlock(loop_header); + graph->AddBlock(loop_body); + graph->AddBlock(exit); + block->AddSuccessor(loop_header); + loop_header->AddSuccessor(exit); // true successor + loop_header->AddSuccessor(loop_body); // false successor + loop_body->AddSuccessor(loop_header); + + HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt); + phi->AddInput(constant_initial); + HInstruction* null_check = new (allocator) HNullCheck(parameter, 0); + HInstruction* array_length = new (allocator) HArrayLength(null_check); + HInstruction* cmp = nullptr; + if (cond == kCondGE) { + cmp = new (allocator) HGreaterThanOrEqual(phi, array_length); + } else { + DCHECK(cond == kCondGT); + cmp = new (allocator) HGreaterThan(phi, array_length); + } + HInstruction* if_inst = new (allocator) HIf(cmp); + loop_header->AddPhi(phi); + loop_header->AddInstruction(null_check); + loop_header->AddInstruction(array_length); + loop_header->AddInstruction(cmp); + loop_header->AddInstruction(if_inst); + + null_check = new (allocator) HNullCheck(parameter, 0); + array_length = new (allocator) HArrayLength(null_check); + *bounds_check = new (allocator) HBoundsCheck(phi, array_length, 0); + HInstruction* array_set = new (allocator) HArraySet( + null_check, *bounds_check, constant_10, Primitive::kPrimInt, 0); + + HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_increment); + loop_body->AddInstruction(null_check); + loop_body->AddInstruction(array_length); + loop_body->AddInstruction(*bounds_check); + loop_body->AddInstruction(array_set); + loop_body->AddInstruction(add); + loop_body->AddInstruction(new (allocator) HGoto()); + phi->AddInput(add); + + exit->AddInstruction(new (allocator) HExit()); + + return graph; +} + +TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination1) { + ArenaPool pool; + ArenaAllocator allocator(&pool); + + // for (int i=0; i<array.length; i++) { array[i] = 10; // Can eliminate with gvn. } + HInstruction* bounds_check = nullptr; + HGraph* graph = BuildSSAGraph1(&allocator, &bounds_check, 0, 1); + graph->BuildDominatorTree(); + BoundsCheckElimination bounds_check_elimination(graph); + bounds_check_elimination.Run(); + ASSERT_FALSE(IsRemoved(bounds_check)); + + // This time add gvn. Need gvn to eliminate the second + // HArrayLength which uses the null check as its input. + graph = BuildSSAGraph1(&allocator, &bounds_check, 0, 1); + graph->BuildDominatorTree(); + GlobalValueNumberer(&allocator, graph).Run(); + BoundsCheckElimination bounds_check_elimination_after_gvn(graph); + bounds_check_elimination_after_gvn.Run(); + ASSERT_TRUE(IsRemoved(bounds_check)); + + // for (int i=1; i<array.length; i++) { array[i] = 10; // Can eliminate. } + graph = BuildSSAGraph1(&allocator, &bounds_check, 1, 1); + graph->BuildDominatorTree(); + GlobalValueNumberer(&allocator, graph).Run(); + BoundsCheckElimination bounds_check_elimination_with_initial_1(graph); + bounds_check_elimination_with_initial_1.Run(); + ASSERT_TRUE(IsRemoved(bounds_check)); + + // for (int i=-1; i<array.length; i++) { array[i] = 10; // Can't eliminate. } + graph = BuildSSAGraph1(&allocator, &bounds_check, -1, 1); + graph->BuildDominatorTree(); + GlobalValueNumberer(&allocator, graph).Run(); + BoundsCheckElimination bounds_check_elimination_with_initial_minus_1(graph); + bounds_check_elimination_with_initial_minus_1.Run(); + ASSERT_FALSE(IsRemoved(bounds_check)); + + // for (int i=0; i<=array.length; i++) { array[i] = 10; // Can't eliminate. } + graph = BuildSSAGraph1(&allocator, &bounds_check, 0, 1, kCondGT); + graph->BuildDominatorTree(); + GlobalValueNumberer(&allocator, graph).Run(); + BoundsCheckElimination bounds_check_elimination_with_greater_than(graph); + bounds_check_elimination_with_greater_than.Run(); + ASSERT_FALSE(IsRemoved(bounds_check)); + + // for (int i=0; i<array.length; i += 2) { + // array[i] = 10; // Can't eliminate due to overflow concern. } + graph = BuildSSAGraph1(&allocator, &bounds_check, 0, 2); + graph->BuildDominatorTree(); + GlobalValueNumberer(&allocator, graph).Run(); + BoundsCheckElimination bounds_check_elimination_with_increment_2(graph); + bounds_check_elimination_with_increment_2.Run(); + ASSERT_FALSE(IsRemoved(bounds_check)); + + // for (int i=1; i<array.length; i += 2) { array[i] = 10; // Can eliminate. } + graph = BuildSSAGraph1(&allocator, &bounds_check, 1, 2); + graph->BuildDominatorTree(); + GlobalValueNumberer(&allocator, graph).Run(); + BoundsCheckElimination bounds_check_elimination_with_increment_2_from_1(graph); + bounds_check_elimination_with_increment_2_from_1.Run(); + ASSERT_TRUE(IsRemoved(bounds_check)); +} + +// for (int i=array.length; i>0; i+=increment) { array[i-1] = 10; } +static HGraph* BuildSSAGraph2(ArenaAllocator* allocator, + HInstruction** bounds_check, + int initial, + int increment = -1, + IfCondition cond = kCondLE) { + HGraph* graph = new (allocator) HGraph(allocator); + + HBasicBlock* entry = new (allocator) HBasicBlock(graph); + graph->AddBlock(entry); + graph->SetEntryBlock(entry); + HInstruction* parameter = new (allocator) HParameterValue(0, Primitive::kPrimNot); + HInstruction* constant_initial = new (allocator) HIntConstant(initial); + HInstruction* constant_increment = new (allocator) HIntConstant(increment); + HInstruction* constant_minus_1 = new (allocator) HIntConstant(-1); + HInstruction* constant_10 = new (allocator) HIntConstant(10); + entry->AddInstruction(parameter); + entry->AddInstruction(constant_initial); + entry->AddInstruction(constant_increment); + entry->AddInstruction(constant_minus_1); + entry->AddInstruction(constant_10); + + HBasicBlock* block = new (allocator) HBasicBlock(graph); + graph->AddBlock(block); + entry->AddSuccessor(block); + HInstruction* null_check = new (allocator) HNullCheck(parameter, 0); + HInstruction* array_length = new (allocator) HArrayLength(null_check); + block->AddInstruction(null_check); + block->AddInstruction(array_length); + block->AddInstruction(new (allocator) HGoto()); + + HBasicBlock* loop_header = new (allocator) HBasicBlock(graph); + HBasicBlock* loop_body = new (allocator) HBasicBlock(graph); + HBasicBlock* exit = new (allocator) HBasicBlock(graph); + + graph->AddBlock(loop_header); + graph->AddBlock(loop_body); + graph->AddBlock(exit); + block->AddSuccessor(loop_header); + loop_header->AddSuccessor(exit); // true successor + loop_header->AddSuccessor(loop_body); // false successor + loop_body->AddSuccessor(loop_header); + + HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt); + phi->AddInput(array_length); + HInstruction* cmp = nullptr; + if (cond == kCondLE) { + cmp = new (allocator) HLessThanOrEqual(phi, constant_initial); + } else { + DCHECK(cond == kCondLT); + cmp = new (allocator) HLessThan(phi, constant_initial); + } + HInstruction* if_inst = new (allocator) HIf(cmp); + loop_header->AddPhi(phi); + loop_header->AddInstruction(cmp); + loop_header->AddInstruction(if_inst); + + HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_minus_1); + null_check = new (allocator) HNullCheck(parameter, 0); + array_length = new (allocator) HArrayLength(null_check); + *bounds_check = new (allocator) HBoundsCheck(add, array_length, 0); + HInstruction* array_set = new (allocator) HArraySet( + null_check, *bounds_check, constant_10, Primitive::kPrimInt, 0); + HInstruction* add_phi = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_increment); + loop_body->AddInstruction(add); + loop_body->AddInstruction(null_check); + loop_body->AddInstruction(array_length); + loop_body->AddInstruction(*bounds_check); + loop_body->AddInstruction(array_set); + loop_body->AddInstruction(add_phi); + loop_body->AddInstruction(new (allocator) HGoto()); + phi->AddInput(add); + + exit->AddInstruction(new (allocator) HExit()); + + return graph; +} + +TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination2) { + ArenaPool pool; + ArenaAllocator allocator(&pool); + + // for (int i=array.length; i>0; i--) { array[i-1] = 10; // Can eliminate with gvn. } + HInstruction* bounds_check = nullptr; + HGraph* graph = BuildSSAGraph2(&allocator, &bounds_check, 0); + graph->BuildDominatorTree(); + BoundsCheckElimination bounds_check_elimination(graph); + bounds_check_elimination.Run(); + ASSERT_FALSE(IsRemoved(bounds_check)); + + // This time add gvn. Need gvn to eliminate the second + // HArrayLength which uses the null check as its input. + graph = BuildSSAGraph2(&allocator, &bounds_check, 0); + graph->BuildDominatorTree(); + GlobalValueNumberer(&allocator, graph).Run(); + BoundsCheckElimination bounds_check_elimination_after_gvn(graph); + bounds_check_elimination_after_gvn.Run(); + ASSERT_TRUE(IsRemoved(bounds_check)); + + // for (int i=array.length; i>1; i--) { array[i-1] = 10; // Can eliminate. } + graph = BuildSSAGraph2(&allocator, &bounds_check, 1); + graph->BuildDominatorTree(); + GlobalValueNumberer(&allocator, graph).Run(); + BoundsCheckElimination bounds_check_elimination_with_initial_1(graph); + bounds_check_elimination_with_initial_1.Run(); + ASSERT_TRUE(IsRemoved(bounds_check)); + + // for (int i=array.length; i>-1; i--) { array[i-1] = 10; // Can't eliminate. } + graph = BuildSSAGraph2(&allocator, &bounds_check, -1); + graph->BuildDominatorTree(); + GlobalValueNumberer(&allocator, graph).Run(); + BoundsCheckElimination bounds_check_elimination_with_initial_minus_1(graph); + bounds_check_elimination_with_initial_minus_1.Run(); + ASSERT_FALSE(IsRemoved(bounds_check)); + + // 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(); + GlobalValueNumberer(&allocator, graph).Run(); + BoundsCheckElimination bounds_check_elimination_with_less_than(graph); + bounds_check_elimination_with_less_than.Run(); + ASSERT_FALSE(IsRemoved(bounds_check)); + + // for (int i=array.length; i>0; i-=2) { array[i-1] = 10; // Can eliminate. } + graph = BuildSSAGraph2(&allocator, &bounds_check, 0, -2); + graph->BuildDominatorTree(); + GlobalValueNumberer(&allocator, graph).Run(); + BoundsCheckElimination bounds_check_elimination_increment_minus_2(graph); + bounds_check_elimination_increment_minus_2.Run(); + ASSERT_TRUE(IsRemoved(bounds_check)); +} + +// int[] array = new array[10]; +// for (int i=0; i<10; i+=increment) { array[i] = 10; } +static HGraph* BuildSSAGraph3(ArenaAllocator* allocator, + HInstruction** bounds_check, + int initial, + int increment, + IfCondition cond) { + HGraph* graph = new (allocator) HGraph(allocator); + + HBasicBlock* entry = new (allocator) HBasicBlock(graph); + graph->AddBlock(entry); + graph->SetEntryBlock(entry); + HInstruction* constant_10 = new (allocator) HIntConstant(10); + HInstruction* constant_initial = new (allocator) HIntConstant(initial); + HInstruction* constant_increment = new (allocator) HIntConstant(increment); + entry->AddInstruction(constant_10); + entry->AddInstruction(constant_initial); + entry->AddInstruction(constant_increment); + + HBasicBlock* block = new (allocator) HBasicBlock(graph); + graph->AddBlock(block); + entry->AddSuccessor(block); + HInstruction* new_array = new (allocator) + HNewArray(constant_10, 0, Primitive::kPrimInt); + block->AddInstruction(new_array); + block->AddInstruction(new (allocator) HGoto()); + + HBasicBlock* loop_header = new (allocator) HBasicBlock(graph); + HBasicBlock* loop_body = new (allocator) HBasicBlock(graph); + HBasicBlock* exit = new (allocator) HBasicBlock(graph); + + graph->AddBlock(loop_header); + graph->AddBlock(loop_body); + graph->AddBlock(exit); + block->AddSuccessor(loop_header); + loop_header->AddSuccessor(exit); // true successor + loop_header->AddSuccessor(loop_body); // false successor + loop_body->AddSuccessor(loop_header); + + HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt); + phi->AddInput(constant_initial); + HInstruction* cmp = nullptr; + if (cond == kCondGE) { + cmp = new (allocator) HGreaterThanOrEqual(phi, constant_10); + } else { + DCHECK(cond == kCondGT); + cmp = new (allocator) HGreaterThan(phi, constant_10); + } + HInstruction* if_inst = new (allocator) HIf(cmp); + loop_header->AddPhi(phi); + loop_header->AddInstruction(cmp); + loop_header->AddInstruction(if_inst); + + HNullCheck* null_check = new (allocator) HNullCheck(new_array, 0); + HArrayLength* array_length = new (allocator) HArrayLength(null_check); + *bounds_check = new (allocator) HBoundsCheck(phi, array_length, 0); + HInstruction* array_set = new (allocator) HArraySet( + null_check, *bounds_check, constant_10, Primitive::kPrimInt, 0); + HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_increment); + loop_body->AddInstruction(null_check); + loop_body->AddInstruction(array_length); + loop_body->AddInstruction(*bounds_check); + loop_body->AddInstruction(array_set); + loop_body->AddInstruction(add); + loop_body->AddInstruction(new (allocator) HGoto()); + phi->AddInput(add); + + exit->AddInstruction(new (allocator) HExit()); + + return graph; +} + +TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination3) { + ArenaPool pool; + ArenaAllocator allocator(&pool); + + // int[] array = new array[10]; + // for (int i=0; i<10; i++) { array[i] = 10; // Can eliminate. } + HInstruction* bounds_check = nullptr; + HGraph* graph = BuildSSAGraph3(&allocator, &bounds_check, 0, 1, kCondGE); + graph->BuildDominatorTree(); + GlobalValueNumberer(&allocator, graph).Run(); + BoundsCheckElimination bounds_check_elimination_after_gvn(graph); + bounds_check_elimination_after_gvn.Run(); + ASSERT_TRUE(IsRemoved(bounds_check)); + + // int[] array = new array[10]; + // for (int i=1; i<10; i++) { array[i] = 10; // Can eliminate. } + graph = BuildSSAGraph3(&allocator, &bounds_check, 1, 1, kCondGE); + graph->BuildDominatorTree(); + GlobalValueNumberer(&allocator, graph).Run(); + BoundsCheckElimination bounds_check_elimination_with_initial_1(graph); + bounds_check_elimination_with_initial_1.Run(); + ASSERT_TRUE(IsRemoved(bounds_check)); + + // int[] array = new array[10]; + // for (int i=0; i<=10; i++) { array[i] = 10; // Can't eliminate. } + graph = BuildSSAGraph3(&allocator, &bounds_check, 0, 1, kCondGT); + graph->BuildDominatorTree(); + GlobalValueNumberer(&allocator, graph).Run(); + BoundsCheckElimination bounds_check_elimination_with_greater_than(graph); + bounds_check_elimination_with_greater_than.Run(); + ASSERT_FALSE(IsRemoved(bounds_check)); + + // int[] array = new array[10]; + // for (int i=1; i<10; i+=8) { array[i] = 10; // Can eliminate. } + graph = BuildSSAGraph3(&allocator, &bounds_check, 1, 8, kCondGE); + graph->BuildDominatorTree(); + GlobalValueNumberer(&allocator, graph).Run(); + BoundsCheckElimination bounds_check_elimination_increment_8(graph); + bounds_check_elimination_increment_8.Run(); + ASSERT_TRUE(IsRemoved(bounds_check)); +} + +// for (int i=initial; i<array.length; i++) { array[array.length-i-1] = 10; } +static HGraph* BuildSSAGraph4(ArenaAllocator* allocator, + HInstruction** bounds_check, + int initial, + IfCondition cond = kCondGE) { + HGraph* graph = new (allocator) HGraph(allocator); + + HBasicBlock* entry = new (allocator) HBasicBlock(graph); + graph->AddBlock(entry); + graph->SetEntryBlock(entry); + HInstruction* parameter = new (allocator) HParameterValue(0, Primitive::kPrimNot); + HInstruction* constant_initial = new (allocator) HIntConstant(initial); + HInstruction* constant_1 = new (allocator) HIntConstant(1); + HInstruction* constant_10 = new (allocator) HIntConstant(10); + HInstruction* constant_minus_1 = new (allocator) HIntConstant(-1); + entry->AddInstruction(parameter); + entry->AddInstruction(constant_initial); + entry->AddInstruction(constant_1); + entry->AddInstruction(constant_10); + entry->AddInstruction(constant_minus_1); + + HBasicBlock* block = new (allocator) HBasicBlock(graph); + graph->AddBlock(block); + entry->AddSuccessor(block); + block->AddInstruction(new (allocator) HGoto()); + + HBasicBlock* loop_header = new (allocator) HBasicBlock(graph); + HBasicBlock* loop_body = new (allocator) HBasicBlock(graph); + HBasicBlock* exit = new (allocator) HBasicBlock(graph); + + graph->AddBlock(loop_header); + graph->AddBlock(loop_body); + graph->AddBlock(exit); + block->AddSuccessor(loop_header); + loop_header->AddSuccessor(exit); // true successor + loop_header->AddSuccessor(loop_body); // false successor + loop_body->AddSuccessor(loop_header); + + HPhi* phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt); + phi->AddInput(constant_initial); + HInstruction* null_check = new (allocator) HNullCheck(parameter, 0); + HInstruction* array_length = new (allocator) HArrayLength(null_check); + HInstruction* cmp = nullptr; + if (cond == kCondGE) { + cmp = new (allocator) HGreaterThanOrEqual(phi, array_length); + } else if (cond == kCondGT) { + cmp = new (allocator) HGreaterThan(phi, array_length); + } + HInstruction* if_inst = new (allocator) HIf(cmp); + loop_header->AddPhi(phi); + loop_header->AddInstruction(null_check); + loop_header->AddInstruction(array_length); + loop_header->AddInstruction(cmp); + loop_header->AddInstruction(if_inst); + + null_check = new (allocator) HNullCheck(parameter, 0); + array_length = new (allocator) HArrayLength(null_check); + HInstruction* sub = new (allocator) HSub(Primitive::kPrimInt, array_length, phi); + HInstruction* add_minus_1 = new (allocator) + HAdd(Primitive::kPrimInt, sub, constant_minus_1); + *bounds_check = new (allocator) HBoundsCheck(add_minus_1, array_length, 0); + HInstruction* array_set = new (allocator) HArraySet( + null_check, *bounds_check, constant_10, Primitive::kPrimInt, 0); + HInstruction* add = new (allocator) HAdd(Primitive::kPrimInt, phi, constant_1); + loop_body->AddInstruction(null_check); + loop_body->AddInstruction(array_length); + loop_body->AddInstruction(sub); + loop_body->AddInstruction(add_minus_1); + loop_body->AddInstruction(*bounds_check); + loop_body->AddInstruction(array_set); + loop_body->AddInstruction(add); + loop_body->AddInstruction(new (allocator) HGoto()); + phi->AddInput(add); + + exit->AddInstruction(new (allocator) HExit()); + + return graph; +} + +TEST(BoundsCheckEliminationTest, LoopArrayBoundsElimination4) { + ArenaPool pool; + ArenaAllocator allocator(&pool); + + // for (int i=0; i<array.length; i++) { array[array.length-i-1] = 10; // Can eliminate with gvn. } + HInstruction* bounds_check = nullptr; + HGraph* graph = BuildSSAGraph4(&allocator, &bounds_check, 0); + graph->BuildDominatorTree(); + BoundsCheckElimination bounds_check_elimination(graph); + bounds_check_elimination.Run(); + ASSERT_FALSE(IsRemoved(bounds_check)); + + // This time add gvn. Need gvn to eliminate the second + // HArrayLength which uses the null check as its input. + graph = BuildSSAGraph4(&allocator, &bounds_check, 0); + graph->BuildDominatorTree(); + GlobalValueNumberer(&allocator, graph).Run(); + BoundsCheckElimination bounds_check_elimination_after_gvn(graph); + bounds_check_elimination_after_gvn.Run(); + ASSERT_TRUE(IsRemoved(bounds_check)); + + // for (int i=1; i<array.length; i++) { array[array.length-i-1] = 10; // Can eliminate. } + graph = BuildSSAGraph4(&allocator, &bounds_check, 1); + graph->BuildDominatorTree(); + GlobalValueNumberer(&allocator, graph).Run(); + BoundsCheckElimination bounds_check_elimination_with_initial_1(graph); + bounds_check_elimination_with_initial_1.Run(); + ASSERT_TRUE(IsRemoved(bounds_check)); + + // 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(); + GlobalValueNumberer(&allocator, graph).Run(); + BoundsCheckElimination bounds_check_elimination_with_greater_than(graph); + bounds_check_elimination_with_greater_than.Run(); + ASSERT_FALSE(IsRemoved(bounds_check)); +} + +// Bubble sort: +// (Every array access bounds-check can be eliminated.) +// for (int i=0; i<array.length-1; i++) { +// for (int j=0; j<array.length-i-1; j++) { +// if (array[j] > array[j+1]) { +// int temp = array[j+1]; +// array[j+1] = array[j]; +// array[j] = temp; +// } +// } +// } +TEST(BoundsCheckEliminationTest, BubbleSortArrayBoundsElimination) { + ArenaPool pool; + ArenaAllocator allocator(&pool); + + HGraph* graph = new (&allocator) HGraph(&allocator); + + HBasicBlock* entry = new (&allocator) HBasicBlock(graph); + graph->AddBlock(entry); + graph->SetEntryBlock(entry); + HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimNot); + HInstruction* constant_0 = new (&allocator) HIntConstant(0); + HInstruction* constant_minus_1 = new (&allocator) HIntConstant(-1); + HInstruction* constant_1 = new (&allocator) HIntConstant(1); + entry->AddInstruction(parameter); + entry->AddInstruction(constant_0); + entry->AddInstruction(constant_minus_1); + entry->AddInstruction(constant_1); + + HBasicBlock* block = new (&allocator) HBasicBlock(graph); + graph->AddBlock(block); + entry->AddSuccessor(block); + block->AddInstruction(new (&allocator) HGoto()); + + HBasicBlock* exit = new (&allocator) HBasicBlock(graph); + graph->AddBlock(exit); + exit->AddInstruction(new (&allocator) HExit()); + + HBasicBlock* outer_header = new (&allocator) HBasicBlock(graph); + graph->AddBlock(outer_header); + HPhi* phi_i = new (&allocator) HPhi(&allocator, 0, 0, Primitive::kPrimInt); + phi_i->AddInput(constant_0); + HNullCheck* null_check = new (&allocator) HNullCheck(parameter, 0); + HArrayLength* array_length = new (&allocator) HArrayLength(null_check); + HAdd* add = new (&allocator) HAdd(Primitive::kPrimInt, array_length, constant_minus_1); + HInstruction* cmp = new (&allocator) HGreaterThanOrEqual(phi_i, add); + HIf* if_inst = new (&allocator) HIf(cmp); + outer_header->AddPhi(phi_i); + outer_header->AddInstruction(null_check); + outer_header->AddInstruction(array_length); + outer_header->AddInstruction(add); + outer_header->AddInstruction(cmp); + outer_header->AddInstruction(if_inst); + + HBasicBlock* inner_header = new (&allocator) HBasicBlock(graph); + graph->AddBlock(inner_header); + HPhi* phi_j = new (&allocator) HPhi(&allocator, 0, 0, Primitive::kPrimInt); + phi_j->AddInput(constant_0); + null_check = new (&allocator) HNullCheck(parameter, 0); + array_length = new (&allocator) HArrayLength(null_check); + HSub* sub = new (&allocator) HSub(Primitive::kPrimInt, array_length, phi_i); + add = new (&allocator) HAdd(Primitive::kPrimInt, sub, constant_minus_1); + cmp = new (&allocator) HGreaterThanOrEqual(phi_j, add); + if_inst = new (&allocator) HIf(cmp); + inner_header->AddPhi(phi_j); + inner_header->AddInstruction(null_check); + inner_header->AddInstruction(array_length); + inner_header->AddInstruction(sub); + inner_header->AddInstruction(add); + inner_header->AddInstruction(cmp); + inner_header->AddInstruction(if_inst); + + HBasicBlock* inner_body_compare = new (&allocator) HBasicBlock(graph); + graph->AddBlock(inner_body_compare); + null_check = new (&allocator) HNullCheck(parameter, 0); + array_length = new (&allocator) HArrayLength(null_check); + HBoundsCheck* bounds_check1 = new (&allocator) HBoundsCheck(phi_j, array_length, 0); + HArrayGet* array_get_j = new (&allocator) + HArrayGet(null_check, bounds_check1, Primitive::kPrimInt); + inner_body_compare->AddInstruction(null_check); + inner_body_compare->AddInstruction(array_length); + inner_body_compare->AddInstruction(bounds_check1); + inner_body_compare->AddInstruction(array_get_j); + HInstruction* j_plus_1 = new (&allocator) HAdd(Primitive::kPrimInt, phi_j, constant_1); + null_check = new (&allocator) HNullCheck(parameter, 0); + array_length = new (&allocator) HArrayLength(null_check); + HBoundsCheck* bounds_check2 = new (&allocator) HBoundsCheck(j_plus_1, array_length, 0); + HArrayGet* array_get_j_plus_1 = new (&allocator) + HArrayGet(null_check, bounds_check2, Primitive::kPrimInt); + cmp = new (&allocator) HGreaterThanOrEqual(array_get_j, array_get_j_plus_1); + if_inst = new (&allocator) HIf(cmp); + inner_body_compare->AddInstruction(j_plus_1); + inner_body_compare->AddInstruction(null_check); + inner_body_compare->AddInstruction(array_length); + inner_body_compare->AddInstruction(bounds_check2); + inner_body_compare->AddInstruction(array_get_j_plus_1); + inner_body_compare->AddInstruction(cmp); + inner_body_compare->AddInstruction(if_inst); + + HBasicBlock* inner_body_swap = new (&allocator) HBasicBlock(graph); + graph->AddBlock(inner_body_swap); + j_plus_1 = new (&allocator) HAdd(Primitive::kPrimInt, phi_j, constant_1); + // temp = array[j+1] + null_check = new (&allocator) HNullCheck(parameter, 0); + array_length = new (&allocator) HArrayLength(null_check); + HInstruction* bounds_check3 = new (&allocator) HBoundsCheck(j_plus_1, array_length, 0); + array_get_j_plus_1 = new (&allocator) + HArrayGet(null_check, bounds_check3, Primitive::kPrimInt); + inner_body_swap->AddInstruction(j_plus_1); + inner_body_swap->AddInstruction(null_check); + inner_body_swap->AddInstruction(array_length); + inner_body_swap->AddInstruction(bounds_check3); + inner_body_swap->AddInstruction(array_get_j_plus_1); + // array[j+1] = array[j] + null_check = new (&allocator) HNullCheck(parameter, 0); + array_length = new (&allocator) HArrayLength(null_check); + HInstruction* bounds_check4 = new (&allocator) HBoundsCheck(phi_j, array_length, 0); + array_get_j = new (&allocator) + HArrayGet(null_check, bounds_check4, Primitive::kPrimInt); + inner_body_swap->AddInstruction(null_check); + inner_body_swap->AddInstruction(array_length); + inner_body_swap->AddInstruction(bounds_check4); + inner_body_swap->AddInstruction(array_get_j); + null_check = new (&allocator) HNullCheck(parameter, 0); + array_length = new (&allocator) HArrayLength(null_check); + HInstruction* bounds_check5 = new (&allocator) HBoundsCheck(j_plus_1, array_length, 0); + HArraySet* array_set_j_plus_1 = new (&allocator) + HArraySet(null_check, bounds_check5, array_get_j, Primitive::kPrimInt, 0); + inner_body_swap->AddInstruction(null_check); + inner_body_swap->AddInstruction(array_length); + inner_body_swap->AddInstruction(bounds_check5); + inner_body_swap->AddInstruction(array_set_j_plus_1); + // array[j] = temp + null_check = new (&allocator) HNullCheck(parameter, 0); + array_length = new (&allocator) HArrayLength(null_check); + HInstruction* bounds_check6 = new (&allocator) HBoundsCheck(phi_j, array_length, 0); + HArraySet* array_set_j = new (&allocator) + HArraySet(null_check, bounds_check6, array_get_j_plus_1, Primitive::kPrimInt, 0); + inner_body_swap->AddInstruction(null_check); + inner_body_swap->AddInstruction(array_length); + inner_body_swap->AddInstruction(bounds_check6); + inner_body_swap->AddInstruction(array_set_j); + inner_body_swap->AddInstruction(new (&allocator) HGoto()); + + HBasicBlock* inner_body_add = new (&allocator) HBasicBlock(graph); + graph->AddBlock(inner_body_add); + add = new (&allocator) HAdd(Primitive::kPrimInt, phi_j, constant_1); + inner_body_add->AddInstruction(add); + inner_body_add->AddInstruction(new (&allocator) HGoto()); + phi_j->AddInput(add); + + HBasicBlock* outer_body_add = new (&allocator) HBasicBlock(graph); + graph->AddBlock(outer_body_add); + add = new (&allocator) HAdd(Primitive::kPrimInt, phi_i, constant_1); + outer_body_add->AddInstruction(add); + outer_body_add->AddInstruction(new (&allocator) HGoto()); + phi_i->AddInput(add); + + block->AddSuccessor(outer_header); + outer_header->AddSuccessor(exit); + outer_header->AddSuccessor(inner_header); + inner_header->AddSuccessor(outer_body_add); + inner_header->AddSuccessor(inner_body_compare); + inner_body_compare->AddSuccessor(inner_body_add); + inner_body_compare->AddSuccessor(inner_body_swap); + inner_body_swap->AddSuccessor(inner_body_add); + inner_body_add->AddSuccessor(inner_header); + outer_body_add->AddSuccessor(outer_header); + + graph->BuildDominatorTree(); + GlobalValueNumberer(&allocator, graph).Run(); + // gvn should remove the same bounds check. + ASSERT_FALSE(IsRemoved(bounds_check1)); + ASSERT_FALSE(IsRemoved(bounds_check2)); + ASSERT_TRUE(IsRemoved(bounds_check3)); + ASSERT_TRUE(IsRemoved(bounds_check4)); + ASSERT_TRUE(IsRemoved(bounds_check5)); + ASSERT_TRUE(IsRemoved(bounds_check6)); + + BoundsCheckElimination bounds_check_elimination(graph); + bounds_check_elimination.Run(); + ASSERT_TRUE(IsRemoved(bounds_check1)); + ASSERT_TRUE(IsRemoved(bounds_check2)); + ASSERT_TRUE(IsRemoved(bounds_check3)); + ASSERT_TRUE(IsRemoved(bounds_check4)); + ASSERT_TRUE(IsRemoved(bounds_check5)); + ASSERT_TRUE(IsRemoved(bounds_check6)); +} + +} // namespace art diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc index 100a6bc4a3..11fc9bf9b9 100644 --- a/compiler/optimizing/optimizing_compiler.cc +++ b/compiler/optimizing/optimizing_compiler.cc @@ -19,6 +19,7 @@ #include <fstream> #include <stdint.h> +#include "bounds_check_elimination.h" #include "builder.h" #include "code_generator.h" #include "compiler.h" @@ -198,7 +199,8 @@ static void RunOptimizations(HGraph* graph, const HGraphVisualizer& visualizer) SsaDeadPhiElimination opt4(graph); InstructionSimplifier opt5(graph); GVNOptimization opt6(graph); - InstructionSimplifier opt7(graph); + BoundsCheckElimination bce(graph); + InstructionSimplifier opt8(graph); HOptimization* optimizations[] = { &opt1, @@ -207,7 +209,8 @@ static void RunOptimizations(HGraph* graph, const HGraphVisualizer& visualizer) &opt4, &opt5, &opt6, - &opt7 + &bce, + &opt8 }; for (size_t i = 0; i < arraysize(optimizations); ++i) { diff --git a/compiler/optimizing/optimizing_unit_test.h b/compiler/optimizing/optimizing_unit_test.h index c4106b72b5..04b56345c4 100644 --- a/compiler/optimizing/optimizing_unit_test.h +++ b/compiler/optimizing/optimizing_unit_test.h @@ -96,6 +96,11 @@ inline std::string Patch(const std::string& original, const diff_t& diff) { return result; } +// Returns if the instruction is removed from the graph. +inline bool IsRemoved(HInstruction* instruction) { + return instruction->GetBlock() == nullptr; +} + } // namespace art #endif // ART_COMPILER_OPTIMIZING_OPTIMIZING_UNIT_TEST_H_ |