| /* |
| * 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: |
| ValueBound(HInstruction* instruction, int constant) { |
| if (instruction != nullptr && instruction->IsIntConstant()) { |
| // Normalizing ValueBound with constant instruction. |
| int instr_const = instruction->AsIntConstant()->GetValue(); |
| if (constant >= 0 && (instr_const <= INT_MAX - constant)) { |
| // No overflow. |
| instruction_ = nullptr; |
| constant_ = instr_const + constant; |
| return; |
| } |
| if (constant < 0 && (instr_const >= INT_MIN - constant)) { |
| // No underflow. |
| instruction_ = nullptr; |
| constant_ = instr_const + constant; |
| return; |
| } |
| } |
| instruction_ = instruction; |
| constant_ = constant; |
| } |
| |
| // 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) { |
| DCHECK(instruction != nullptr); |
| if (instruction->IsIntConstant()) { |
| *found = true; |
| return ValueBound(nullptr, instruction->AsIntConstant()->GetValue()); |
| } |
| |
| if (instruction->IsArrayLength()) { |
| *found = true; |
| 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()) { |
| *found = true; |
| return ValueBound(left, right->AsIntConstant()->GetValue()); |
| } |
| } |
| |
| // No useful bound detected. |
| *found = false; |
| return ValueBound::Max(); |
| } |
| |
| 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* 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 Max(); |
| } else { |
| new_constant = constant_ + c; |
| } |
| } else { |
| if (constant_ < INT_MIN - c) { |
| // Constant part underflows. |
| *overflow_or_underflow = true; |
| return Max(); |
| } else { |
| new_constant = constant_ + c; |
| } |
| } |
| return ValueBound(instruction_, new_constant); |
| } |
| |
| private: |
| 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, &overflow_or_underflow); |
| if (overflow_or_underflow) { |
| // We can't accurately represent the bounds anymore. |
| return FullIntRange(); |
| } |
| ValueBound upper = upper_.Add(constant, &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: |
| MonotonicValueRange(ArenaAllocator* allocator, |
| HInstruction* initial, |
| int increment, |
| ValueBound bound) |
| // To be conservative, give it full range [INT_MIN, INT_MAX] in case it's |
| // used as a regular value range, due to possible overflow/underflow. |
| : ValueRange(allocator, ValueBound::Min(), ValueBound::Max()), |
| initial_(initial), |
| increment_(increment), |
| bound_(bound) {} |
| |
| 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(bound_, 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(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. |
| 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: |
| HInstruction* const initial_; |
| const int increment_; |
| ValueBound bound_; // Additional value bound info for initial_; |
| |
| DISALLOW_COPY_AND_ASSIGN(MonotonicValueRange); |
| }; |
| |
| class BCEVisitor : public HGraphVisitor { |
| public: |
| explicit 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; |
| } |
| |
| // 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); |
| |
| bool found; |
| ValueBound bound = ValueBound::DetectValueBoundFromValue(right, &found); |
| 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, &overflow_or_underflow); |
| if (overflow_or_underflow) { |
| new_upper = ValueBound::Max(); |
| } |
| 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, &overflow_or_underflow); |
| if (overflow_or_underflow) { |
| new_lower = ValueBound::Min(); |
| } |
| 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, &overflow_or_underflow); |
| if (overflow_or_underflow) { |
| new_lower = ValueBound::Min(); |
| } |
| 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, &overflow_or_underflow); |
| if (overflow_or_underflow) { |
| new_upper = ValueBound::Max(); |
| } |
| 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(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()) { |
| ReplaceBoundsCheck(bounds_check, index); |
| return; |
| } |
| } |
| |
| // Once we have an array access like 'array[5] = 1', we record array.length >= 6. |
| 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); |
| } |
| } |
| |
| 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_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* 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( |
| GetGraph()->GetArena(), |
| ValueBound(initial_value, 0), |
| ValueBound(initial_value, 0)); |
| } else { |
| // Monotonically increasing/decreasing. |
| bool found; |
| ValueBound bound = ValueBound::DetectValueBoundFromValue( |
| initial_value, &found); |
| 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* initial_range = LookupValueRange(initial_value, phi->GetBlock()); |
| if (initial_range != nullptr) { |
| bound = increment > 0 ? initial_range->GetLower() : |
| initial_range->GetUpper(); |
| } else { |
| bound = increment > 0 ? ValueBound::Min() : ValueBound::Max(); |
| } |
| } |
| range = new (GetGraph()->GetArena()) MonotonicValueRange( |
| GetGraph()->GetArena(), |
| initial_value, |
| increment, |
| bound); |
| } |
| 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(nullptr, - upper.GetConstant()), |
| ValueBound(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 |
