bounds_check_elimination.cc revision 4a34277c55279ba57ab361f7580db846a201d9b1
1/* 2 * Copyright (C) 2014 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17#include "bounds_check_elimination.h" 18 19#include <limits> 20 21#include "base/arena_containers.h" 22#include "induction_var_range.h" 23#include "side_effects_analysis.h" 24#include "nodes.h" 25 26namespace art { 27 28class MonotonicValueRange; 29 30/** 31 * A value bound is represented as a pair of value and constant, 32 * e.g. array.length - 1. 33 */ 34class ValueBound : public ValueObject { 35 public: 36 ValueBound(HInstruction* instruction, int32_t constant) { 37 if (instruction != nullptr && instruction->IsIntConstant()) { 38 // Normalize ValueBound with constant instruction. 39 int32_t instr_const = instruction->AsIntConstant()->GetValue(); 40 if (!WouldAddOverflowOrUnderflow(instr_const, constant)) { 41 instruction_ = nullptr; 42 constant_ = instr_const + constant; 43 return; 44 } 45 } 46 instruction_ = instruction; 47 constant_ = constant; 48 } 49 50 // Return whether (left + right) overflows or underflows. 51 static bool WouldAddOverflowOrUnderflow(int32_t left, int32_t right) { 52 if (right == 0) { 53 return false; 54 } 55 if ((right > 0) && (left <= (std::numeric_limits<int32_t>::max() - right))) { 56 // No overflow. 57 return false; 58 } 59 if ((right < 0) && (left >= (std::numeric_limits<int32_t>::min() - right))) { 60 // No underflow. 61 return false; 62 } 63 return true; 64 } 65 66 static bool IsAddOrSubAConstant(HInstruction* instruction, 67 HInstruction** left_instruction, 68 int* right_constant) { 69 if (instruction->IsAdd() || instruction->IsSub()) { 70 HBinaryOperation* bin_op = instruction->AsBinaryOperation(); 71 HInstruction* left = bin_op->GetLeft(); 72 HInstruction* right = bin_op->GetRight(); 73 if (right->IsIntConstant()) { 74 *left_instruction = left; 75 int32_t c = right->AsIntConstant()->GetValue(); 76 *right_constant = instruction->IsAdd() ? c : -c; 77 return true; 78 } 79 } 80 *left_instruction = nullptr; 81 *right_constant = 0; 82 return false; 83 } 84 85 // Try to detect useful value bound format from an instruction, e.g. 86 // a constant or array length related value. 87 static ValueBound DetectValueBoundFromValue(HInstruction* instruction, bool* found) { 88 DCHECK(instruction != nullptr); 89 if (instruction->IsIntConstant()) { 90 *found = true; 91 return ValueBound(nullptr, instruction->AsIntConstant()->GetValue()); 92 } 93 94 if (instruction->IsArrayLength()) { 95 *found = true; 96 return ValueBound(instruction, 0); 97 } 98 // Try to detect (array.length + c) format. 99 HInstruction *left; 100 int32_t right; 101 if (IsAddOrSubAConstant(instruction, &left, &right)) { 102 if (left->IsArrayLength()) { 103 *found = true; 104 return ValueBound(left, right); 105 } 106 } 107 108 // No useful bound detected. 109 *found = false; 110 return ValueBound::Max(); 111 } 112 113 HInstruction* GetInstruction() const { return instruction_; } 114 int32_t GetConstant() const { return constant_; } 115 116 bool IsRelatedToArrayLength() const { 117 // Some bounds are created with HNewArray* as the instruction instead 118 // of HArrayLength*. They are treated the same. 119 return (instruction_ != nullptr) && 120 (instruction_->IsArrayLength() || instruction_->IsNewArray()); 121 } 122 123 bool IsConstant() const { 124 return instruction_ == nullptr; 125 } 126 127 static ValueBound Min() { return ValueBound(nullptr, std::numeric_limits<int32_t>::min()); } 128 static ValueBound Max() { return ValueBound(nullptr, std::numeric_limits<int32_t>::max()); } 129 130 bool Equals(ValueBound bound) const { 131 return instruction_ == bound.instruction_ && constant_ == bound.constant_; 132 } 133 134 /* 135 * Hunt "under the hood" of array lengths (leading to array references), 136 * null checks (also leading to array references), and new arrays 137 * (leading to the actual length). This makes it more likely related 138 * instructions become actually comparable. 139 */ 140 static HInstruction* HuntForDeclaration(HInstruction* instruction) { 141 while (instruction->IsArrayLength() || 142 instruction->IsNullCheck() || 143 instruction->IsNewArray()) { 144 instruction = instruction->InputAt(0); 145 } 146 return instruction; 147 } 148 149 static bool Equal(HInstruction* instruction1, HInstruction* instruction2) { 150 if (instruction1 == instruction2) { 151 return true; 152 } 153 if (instruction1 == nullptr || instruction2 == nullptr) { 154 return false; 155 } 156 instruction1 = HuntForDeclaration(instruction1); 157 instruction2 = HuntForDeclaration(instruction2); 158 return instruction1 == instruction2; 159 } 160 161 // Returns if it's certain this->bound >= `bound`. 162 bool GreaterThanOrEqualTo(ValueBound bound) const { 163 if (Equal(instruction_, bound.instruction_)) { 164 return constant_ >= bound.constant_; 165 } 166 // Not comparable. Just return false. 167 return false; 168 } 169 170 // Returns if it's certain this->bound <= `bound`. 171 bool LessThanOrEqualTo(ValueBound bound) const { 172 if (Equal(instruction_, bound.instruction_)) { 173 return constant_ <= bound.constant_; 174 } 175 // Not comparable. Just return false. 176 return false; 177 } 178 179 // Returns if it's certain this->bound > `bound`. 180 bool GreaterThan(ValueBound bound) const { 181 if (Equal(instruction_, bound.instruction_)) { 182 return constant_ > bound.constant_; 183 } 184 // Not comparable. Just return false. 185 return false; 186 } 187 188 // Returns if it's certain this->bound < `bound`. 189 bool LessThan(ValueBound bound) const { 190 if (Equal(instruction_, bound.instruction_)) { 191 return constant_ < bound.constant_; 192 } 193 // Not comparable. Just return false. 194 return false; 195 } 196 197 // Try to narrow lower bound. Returns the greatest of the two if possible. 198 // Pick one if they are not comparable. 199 static ValueBound NarrowLowerBound(ValueBound bound1, ValueBound bound2) { 200 if (bound1.GreaterThanOrEqualTo(bound2)) { 201 return bound1; 202 } 203 if (bound2.GreaterThanOrEqualTo(bound1)) { 204 return bound2; 205 } 206 207 // Not comparable. Just pick one. We may lose some info, but that's ok. 208 // Favor constant as lower bound. 209 return bound1.IsConstant() ? bound1 : bound2; 210 } 211 212 // Try to narrow upper bound. Returns the lowest of the two if possible. 213 // Pick one if they are not comparable. 214 static ValueBound NarrowUpperBound(ValueBound bound1, ValueBound bound2) { 215 if (bound1.LessThanOrEqualTo(bound2)) { 216 return bound1; 217 } 218 if (bound2.LessThanOrEqualTo(bound1)) { 219 return bound2; 220 } 221 222 // Not comparable. Just pick one. We may lose some info, but that's ok. 223 // Favor array length as upper bound. 224 return bound1.IsRelatedToArrayLength() ? bound1 : bound2; 225 } 226 227 // Add a constant to a ValueBound. 228 // `overflow` or `underflow` will return whether the resulting bound may 229 // overflow or underflow an int. 230 ValueBound Add(int32_t c, bool* overflow, bool* underflow) const { 231 *overflow = *underflow = false; 232 if (c == 0) { 233 return *this; 234 } 235 236 int32_t new_constant; 237 if (c > 0) { 238 if (constant_ > (std::numeric_limits<int32_t>::max() - c)) { 239 *overflow = true; 240 return Max(); 241 } 242 243 new_constant = constant_ + c; 244 // (array.length + non-positive-constant) won't overflow an int. 245 if (IsConstant() || (IsRelatedToArrayLength() && new_constant <= 0)) { 246 return ValueBound(instruction_, new_constant); 247 } 248 // Be conservative. 249 *overflow = true; 250 return Max(); 251 } else { 252 if (constant_ < (std::numeric_limits<int32_t>::min() - c)) { 253 *underflow = true; 254 return Min(); 255 } 256 257 new_constant = constant_ + c; 258 // Regardless of the value new_constant, (array.length+new_constant) will 259 // never underflow since array.length is no less than 0. 260 if (IsConstant() || IsRelatedToArrayLength()) { 261 return ValueBound(instruction_, new_constant); 262 } 263 // Be conservative. 264 *underflow = true; 265 return Min(); 266 } 267 } 268 269 private: 270 HInstruction* instruction_; 271 int32_t constant_; 272}; 273 274/** 275 * Represent a range of lower bound and upper bound, both being inclusive. 276 * Currently a ValueRange may be generated as a result of the following: 277 * comparisons related to array bounds, array bounds check, add/sub on top 278 * of an existing value range, NewArray or a loop phi corresponding to an 279 * incrementing/decrementing array index (MonotonicValueRange). 280 */ 281class ValueRange : public ArenaObject<kArenaAllocBoundsCheckElimination> { 282 public: 283 ValueRange(ArenaAllocator* allocator, ValueBound lower, ValueBound upper) 284 : allocator_(allocator), lower_(lower), upper_(upper) {} 285 286 virtual ~ValueRange() {} 287 288 virtual MonotonicValueRange* AsMonotonicValueRange() { return nullptr; } 289 bool IsMonotonicValueRange() { 290 return AsMonotonicValueRange() != nullptr; 291 } 292 293 ArenaAllocator* GetAllocator() const { return allocator_; } 294 ValueBound GetLower() const { return lower_; } 295 ValueBound GetUpper() const { return upper_; } 296 297 bool IsConstantValueRange() { return lower_.IsConstant() && upper_.IsConstant(); } 298 299 // If it's certain that this value range fits in other_range. 300 virtual bool FitsIn(ValueRange* other_range) const { 301 if (other_range == nullptr) { 302 return true; 303 } 304 DCHECK(!other_range->IsMonotonicValueRange()); 305 return lower_.GreaterThanOrEqualTo(other_range->lower_) && 306 upper_.LessThanOrEqualTo(other_range->upper_); 307 } 308 309 // Returns the intersection of this and range. 310 // If it's not possible to do intersection because some 311 // bounds are not comparable, it's ok to pick either bound. 312 virtual ValueRange* Narrow(ValueRange* range) { 313 if (range == nullptr) { 314 return this; 315 } 316 317 if (range->IsMonotonicValueRange()) { 318 return this; 319 } 320 321 return new (allocator_) ValueRange( 322 allocator_, 323 ValueBound::NarrowLowerBound(lower_, range->lower_), 324 ValueBound::NarrowUpperBound(upper_, range->upper_)); 325 } 326 327 // Shift a range by a constant. 328 ValueRange* Add(int32_t constant) const { 329 bool overflow, underflow; 330 ValueBound lower = lower_.Add(constant, &overflow, &underflow); 331 if (underflow) { 332 // Lower bound underflow will wrap around to positive values 333 // and invalidate the upper bound. 334 return nullptr; 335 } 336 ValueBound upper = upper_.Add(constant, &overflow, &underflow); 337 if (overflow) { 338 // Upper bound overflow will wrap around to negative values 339 // and invalidate the lower bound. 340 return nullptr; 341 } 342 return new (allocator_) ValueRange(allocator_, lower, upper); 343 } 344 345 private: 346 ArenaAllocator* const allocator_; 347 const ValueBound lower_; // inclusive 348 const ValueBound upper_; // inclusive 349 350 DISALLOW_COPY_AND_ASSIGN(ValueRange); 351}; 352 353/** 354 * A monotonically incrementing/decrementing value range, e.g. 355 * the variable i in "for (int i=0; i<array.length; i++)". 356 * Special care needs to be taken to account for overflow/underflow 357 * of such value ranges. 358 */ 359class MonotonicValueRange : public ValueRange { 360 public: 361 MonotonicValueRange(ArenaAllocator* allocator, 362 HPhi* induction_variable, 363 HInstruction* initial, 364 int32_t increment, 365 ValueBound bound) 366 // To be conservative, give it full range [Min(), Max()] in case it's 367 // used as a regular value range, due to possible overflow/underflow. 368 : ValueRange(allocator, ValueBound::Min(), ValueBound::Max()), 369 induction_variable_(induction_variable), 370 initial_(initial), 371 increment_(increment), 372 bound_(bound) {} 373 374 virtual ~MonotonicValueRange() {} 375 376 int32_t GetIncrement() const { return increment_; } 377 ValueBound GetBound() const { return bound_; } 378 HBasicBlock* GetLoopHeader() const { 379 DCHECK(induction_variable_->GetBlock()->IsLoopHeader()); 380 return induction_variable_->GetBlock(); 381 } 382 383 MonotonicValueRange* AsMonotonicValueRange() OVERRIDE { return this; } 384 385 // If it's certain that this value range fits in other_range. 386 bool FitsIn(ValueRange* other_range) const OVERRIDE { 387 if (other_range == nullptr) { 388 return true; 389 } 390 DCHECK(!other_range->IsMonotonicValueRange()); 391 return false; 392 } 393 394 // Try to narrow this MonotonicValueRange given another range. 395 // Ideally it will return a normal ValueRange. But due to 396 // possible overflow/underflow, that may not be possible. 397 ValueRange* Narrow(ValueRange* range) OVERRIDE { 398 if (range == nullptr) { 399 return this; 400 } 401 DCHECK(!range->IsMonotonicValueRange()); 402 403 if (increment_ > 0) { 404 // Monotonically increasing. 405 ValueBound lower = ValueBound::NarrowLowerBound(bound_, range->GetLower()); 406 if (!lower.IsConstant() || lower.GetConstant() == std::numeric_limits<int32_t>::min()) { 407 // Lower bound isn't useful. Leave it to deoptimization. 408 return this; 409 } 410 411 // We currently conservatively assume max array length is Max(). 412 // If we can make assumptions about the max array length, e.g. due to the max heap size, 413 // divided by the element size (such as 4 bytes for each integer array), we can 414 // lower this number and rule out some possible overflows. 415 int32_t max_array_len = std::numeric_limits<int32_t>::max(); 416 417 // max possible integer value of range's upper value. 418 int32_t upper = std::numeric_limits<int32_t>::max(); 419 // Try to lower upper. 420 ValueBound upper_bound = range->GetUpper(); 421 if (upper_bound.IsConstant()) { 422 upper = upper_bound.GetConstant(); 423 } else if (upper_bound.IsRelatedToArrayLength() && upper_bound.GetConstant() <= 0) { 424 // Normal case. e.g. <= array.length - 1. 425 upper = max_array_len + upper_bound.GetConstant(); 426 } 427 428 // If we can prove for the last number in sequence of initial_, 429 // initial_ + increment_, initial_ + 2 x increment_, ... 430 // that's <= upper, (last_num_in_sequence + increment_) doesn't trigger overflow, 431 // then this MonoticValueRange is narrowed to a normal value range. 432 433 // Be conservative first, assume last number in the sequence hits upper. 434 int32_t last_num_in_sequence = upper; 435 if (initial_->IsIntConstant()) { 436 int32_t initial_constant = initial_->AsIntConstant()->GetValue(); 437 if (upper <= initial_constant) { 438 last_num_in_sequence = upper; 439 } else { 440 // Cast to int64_t for the substraction part to avoid int32_t overflow. 441 last_num_in_sequence = initial_constant + 442 ((int64_t)upper - (int64_t)initial_constant) / increment_ * increment_; 443 } 444 } 445 if (last_num_in_sequence <= (std::numeric_limits<int32_t>::max() - increment_)) { 446 // No overflow. The sequence will be stopped by the upper bound test as expected. 447 return new (GetAllocator()) ValueRange(GetAllocator(), lower, range->GetUpper()); 448 } 449 450 // There might be overflow. Give up narrowing. 451 return this; 452 } else { 453 DCHECK_NE(increment_, 0); 454 // Monotonically decreasing. 455 ValueBound upper = ValueBound::NarrowUpperBound(bound_, range->GetUpper()); 456 if ((!upper.IsConstant() || upper.GetConstant() == std::numeric_limits<int32_t>::max()) && 457 !upper.IsRelatedToArrayLength()) { 458 // Upper bound isn't useful. Leave it to deoptimization. 459 return this; 460 } 461 462 // Need to take care of underflow. Try to prove underflow won't happen 463 // for common cases. 464 if (range->GetLower().IsConstant()) { 465 int32_t constant = range->GetLower().GetConstant(); 466 if (constant >= (std::numeric_limits<int32_t>::min() - increment_)) { 467 return new (GetAllocator()) ValueRange(GetAllocator(), range->GetLower(), upper); 468 } 469 } 470 471 // For non-constant lower bound, just assume might be underflow. Give up narrowing. 472 return this; 473 } 474 } 475 476 private: 477 HPhi* const induction_variable_; // Induction variable for this monotonic value range. 478 HInstruction* const initial_; // Initial value. 479 const int32_t increment_; // Increment for each loop iteration. 480 const ValueBound bound_; // Additional value bound info for initial_. 481 482 DISALLOW_COPY_AND_ASSIGN(MonotonicValueRange); 483}; 484 485class BCEVisitor : public HGraphVisitor { 486 public: 487 // The least number of bounds checks that should be eliminated by triggering 488 // the deoptimization technique. 489 static constexpr size_t kThresholdForAddingDeoptimize = 2; 490 491 // Very large constant index is considered as an anomaly. This is a threshold 492 // beyond which we don't bother to apply the deoptimization technique since 493 // it's likely some AIOOBE will be thrown. 494 static constexpr int32_t kMaxConstantForAddingDeoptimize = 495 std::numeric_limits<int32_t>::max() - 1024 * 1024; 496 497 // Added blocks for loop body entry test. 498 bool IsAddedBlock(HBasicBlock* block) const { 499 return block->GetBlockId() >= initial_block_size_; 500 } 501 502 BCEVisitor(HGraph* graph, 503 const SideEffectsAnalysis& side_effects, 504 HInductionVarAnalysis* induction_analysis) 505 : HGraphVisitor(graph), 506 maps_(graph->GetBlocks().size(), 507 ArenaSafeMap<int, ValueRange*>( 508 std::less<int>(), 509 graph->GetArena()->Adapter(kArenaAllocBoundsCheckElimination)), 510 graph->GetArena()->Adapter(kArenaAllocBoundsCheckElimination)), 511 first_constant_index_bounds_check_map_( 512 std::less<int>(), 513 graph->GetArena()->Adapter(kArenaAllocBoundsCheckElimination)), 514 early_exit_loop_( 515 std::less<uint32_t>(), 516 graph->GetArena()->Adapter(kArenaAllocBoundsCheckElimination)), 517 taken_test_loop_( 518 std::less<uint32_t>(), 519 graph->GetArena()->Adapter(kArenaAllocBoundsCheckElimination)), 520 finite_loop_(graph->GetArena()->Adapter(kArenaAllocBoundsCheckElimination)), 521 need_to_revisit_block_(false), 522 has_deoptimization_on_constant_subscripts_(false), 523 initial_block_size_(graph->GetBlocks().size()), 524 side_effects_(side_effects), 525 induction_range_(induction_analysis) {} 526 527 void VisitBasicBlock(HBasicBlock* block) OVERRIDE { 528 DCHECK(!IsAddedBlock(block)); 529 first_constant_index_bounds_check_map_.clear(); 530 HGraphVisitor::VisitBasicBlock(block); 531 if (need_to_revisit_block_) { 532 AddComparesWithDeoptimization(block); 533 need_to_revisit_block_ = false; 534 first_constant_index_bounds_check_map_.clear(); 535 GetValueRangeMap(block)->clear(); 536 HGraphVisitor::VisitBasicBlock(block); 537 } 538 } 539 540 void Finish() { 541 // Preserve SSA structure which may have been broken by adding one or more 542 // new taken-test structures (see TransformLoopForDeoptimizationIfNeeded()). 543 InsertPhiNodes(); 544 545 // Clear the loop data structures. 546 early_exit_loop_.clear(); 547 taken_test_loop_.clear(); 548 finite_loop_.clear(); 549 } 550 551 private: 552 // Return the map of proven value ranges at the beginning of a basic block. 553 ArenaSafeMap<int, ValueRange*>* GetValueRangeMap(HBasicBlock* basic_block) { 554 if (IsAddedBlock(basic_block)) { 555 // Added blocks don't keep value ranges. 556 return nullptr; 557 } 558 uint32_t block_id = basic_block->GetBlockId(); 559 return &maps_[block_id]; 560 } 561 562 // Traverse up the dominator tree to look for value range info. 563 ValueRange* LookupValueRange(HInstruction* instruction, HBasicBlock* basic_block) { 564 while (basic_block != nullptr) { 565 ArenaSafeMap<int, ValueRange*>* map = GetValueRangeMap(basic_block); 566 if (map != nullptr) { 567 if (map->find(instruction->GetId()) != map->end()) { 568 return map->Get(instruction->GetId()); 569 } 570 } else { 571 DCHECK(IsAddedBlock(basic_block)); 572 } 573 basic_block = basic_block->GetDominator(); 574 } 575 // Didn't find any. 576 return nullptr; 577 } 578 579 // Narrow the value range of `instruction` at the end of `basic_block` with `range`, 580 // and push the narrowed value range to `successor`. 581 void ApplyRangeFromComparison(HInstruction* instruction, HBasicBlock* basic_block, 582 HBasicBlock* successor, ValueRange* range) { 583 ValueRange* existing_range = LookupValueRange(instruction, basic_block); 584 if (existing_range == nullptr) { 585 if (range != nullptr) { 586 GetValueRangeMap(successor)->Overwrite(instruction->GetId(), range); 587 } 588 return; 589 } 590 if (existing_range->IsMonotonicValueRange()) { 591 DCHECK(instruction->IsLoopHeaderPhi()); 592 // Make sure the comparison is in the loop header so each increment is 593 // checked with a comparison. 594 if (instruction->GetBlock() != basic_block) { 595 return; 596 } 597 } 598 ValueRange* narrowed_range = existing_range->Narrow(range); 599 GetValueRangeMap(successor)->Overwrite(instruction->GetId(), narrowed_range); 600 } 601 602 // Special case that we may simultaneously narrow two MonotonicValueRange's to 603 // regular value ranges. 604 void HandleIfBetweenTwoMonotonicValueRanges(HIf* instruction, 605 HInstruction* left, 606 HInstruction* right, 607 IfCondition cond, 608 MonotonicValueRange* left_range, 609 MonotonicValueRange* right_range) { 610 DCHECK(left->IsLoopHeaderPhi()); 611 DCHECK(right->IsLoopHeaderPhi()); 612 if (instruction->GetBlock() != left->GetBlock()) { 613 // Comparison needs to be in loop header to make sure it's done after each 614 // increment/decrement. 615 return; 616 } 617 618 // Handle common cases which also don't have overflow/underflow concerns. 619 if (left_range->GetIncrement() == 1 && 620 left_range->GetBound().IsConstant() && 621 right_range->GetIncrement() == -1 && 622 right_range->GetBound().IsRelatedToArrayLength() && 623 right_range->GetBound().GetConstant() < 0) { 624 HBasicBlock* successor = nullptr; 625 int32_t left_compensation = 0; 626 int32_t right_compensation = 0; 627 if (cond == kCondLT) { 628 left_compensation = -1; 629 right_compensation = 1; 630 successor = instruction->IfTrueSuccessor(); 631 } else if (cond == kCondLE) { 632 successor = instruction->IfTrueSuccessor(); 633 } else if (cond == kCondGT) { 634 successor = instruction->IfFalseSuccessor(); 635 } else if (cond == kCondGE) { 636 left_compensation = -1; 637 right_compensation = 1; 638 successor = instruction->IfFalseSuccessor(); 639 } else { 640 // We don't handle '=='/'!=' test in case left and right can cross and 641 // miss each other. 642 return; 643 } 644 645 if (successor != nullptr) { 646 bool overflow; 647 bool underflow; 648 ValueRange* new_left_range = new (GetGraph()->GetArena()) ValueRange( 649 GetGraph()->GetArena(), 650 left_range->GetBound(), 651 right_range->GetBound().Add(left_compensation, &overflow, &underflow)); 652 if (!overflow && !underflow) { 653 ApplyRangeFromComparison(left, instruction->GetBlock(), successor, 654 new_left_range); 655 } 656 657 ValueRange* new_right_range = new (GetGraph()->GetArena()) ValueRange( 658 GetGraph()->GetArena(), 659 left_range->GetBound().Add(right_compensation, &overflow, &underflow), 660 right_range->GetBound()); 661 if (!overflow && !underflow) { 662 ApplyRangeFromComparison(right, instruction->GetBlock(), successor, 663 new_right_range); 664 } 665 } 666 } 667 } 668 669 // Handle "if (left cmp_cond right)". 670 void HandleIf(HIf* instruction, HInstruction* left, HInstruction* right, IfCondition cond) { 671 HBasicBlock* block = instruction->GetBlock(); 672 673 HBasicBlock* true_successor = instruction->IfTrueSuccessor(); 674 // There should be no critical edge at this point. 675 DCHECK_EQ(true_successor->GetPredecessors().size(), 1u); 676 677 HBasicBlock* false_successor = instruction->IfFalseSuccessor(); 678 // There should be no critical edge at this point. 679 DCHECK_EQ(false_successor->GetPredecessors().size(), 1u); 680 681 ValueRange* left_range = LookupValueRange(left, block); 682 MonotonicValueRange* left_monotonic_range = nullptr; 683 if (left_range != nullptr) { 684 left_monotonic_range = left_range->AsMonotonicValueRange(); 685 if (left_monotonic_range != nullptr) { 686 HBasicBlock* loop_head = left_monotonic_range->GetLoopHeader(); 687 if (instruction->GetBlock() != loop_head) { 688 // For monotonic value range, don't handle `instruction` 689 // if it's not defined in the loop header. 690 return; 691 } 692 } 693 } 694 695 bool found; 696 ValueBound bound = ValueBound::DetectValueBoundFromValue(right, &found); 697 // Each comparison can establish a lower bound and an upper bound 698 // for the left hand side. 699 ValueBound lower = bound; 700 ValueBound upper = bound; 701 if (!found) { 702 // No constant or array.length+c format bound found. 703 // For i<j, we can still use j's upper bound as i's upper bound. Same for lower. 704 ValueRange* right_range = LookupValueRange(right, block); 705 if (right_range != nullptr) { 706 if (right_range->IsMonotonicValueRange()) { 707 if (left_range != nullptr && left_range->IsMonotonicValueRange()) { 708 HandleIfBetweenTwoMonotonicValueRanges(instruction, left, right, cond, 709 left_range->AsMonotonicValueRange(), 710 right_range->AsMonotonicValueRange()); 711 return; 712 } 713 } 714 lower = right_range->GetLower(); 715 upper = right_range->GetUpper(); 716 } else { 717 lower = ValueBound::Min(); 718 upper = ValueBound::Max(); 719 } 720 } 721 722 bool overflow, underflow; 723 if (cond == kCondLT || cond == kCondLE) { 724 if (!upper.Equals(ValueBound::Max())) { 725 int32_t compensation = (cond == kCondLT) ? -1 : 0; // upper bound is inclusive 726 ValueBound new_upper = upper.Add(compensation, &overflow, &underflow); 727 if (overflow || underflow) { 728 return; 729 } 730 ValueRange* new_range = new (GetGraph()->GetArena()) 731 ValueRange(GetGraph()->GetArena(), ValueBound::Min(), new_upper); 732 ApplyRangeFromComparison(left, block, true_successor, new_range); 733 } 734 735 // array.length as a lower bound isn't considered useful. 736 if (!lower.Equals(ValueBound::Min()) && !lower.IsRelatedToArrayLength()) { 737 int32_t compensation = (cond == kCondLE) ? 1 : 0; // lower bound is inclusive 738 ValueBound new_lower = lower.Add(compensation, &overflow, &underflow); 739 if (overflow || underflow) { 740 return; 741 } 742 ValueRange* new_range = new (GetGraph()->GetArena()) 743 ValueRange(GetGraph()->GetArena(), new_lower, ValueBound::Max()); 744 ApplyRangeFromComparison(left, block, false_successor, new_range); 745 } 746 } else if (cond == kCondGT || cond == kCondGE) { 747 // array.length as a lower bound isn't considered useful. 748 if (!lower.Equals(ValueBound::Min()) && !lower.IsRelatedToArrayLength()) { 749 int32_t compensation = (cond == kCondGT) ? 1 : 0; // lower bound is inclusive 750 ValueBound new_lower = lower.Add(compensation, &overflow, &underflow); 751 if (overflow || underflow) { 752 return; 753 } 754 ValueRange* new_range = new (GetGraph()->GetArena()) 755 ValueRange(GetGraph()->GetArena(), new_lower, ValueBound::Max()); 756 ApplyRangeFromComparison(left, block, true_successor, new_range); 757 } 758 759 if (!upper.Equals(ValueBound::Max())) { 760 int32_t compensation = (cond == kCondGE) ? -1 : 0; // upper bound is inclusive 761 ValueBound new_upper = upper.Add(compensation, &overflow, &underflow); 762 if (overflow || underflow) { 763 return; 764 } 765 ValueRange* new_range = new (GetGraph()->GetArena()) 766 ValueRange(GetGraph()->GetArena(), ValueBound::Min(), new_upper); 767 ApplyRangeFromComparison(left, block, false_successor, new_range); 768 } 769 } 770 } 771 772 void VisitBoundsCheck(HBoundsCheck* bounds_check) OVERRIDE { 773 HBasicBlock* block = bounds_check->GetBlock(); 774 HInstruction* index = bounds_check->InputAt(0); 775 HInstruction* array_length = bounds_check->InputAt(1); 776 DCHECK(array_length->IsIntConstant() || 777 array_length->IsArrayLength() || 778 array_length->IsPhi()); 779 bool try_dynamic_bce = true; 780 781 if (!index->IsIntConstant()) { 782 // Non-constant subscript. 783 ValueBound lower = ValueBound(nullptr, 0); // constant 0 784 ValueBound upper = ValueBound(array_length, -1); // array_length - 1 785 ValueRange array_range(GetGraph()->GetArena(), lower, upper); 786 // Try range obtained by dominator-based analysis. 787 ValueRange* index_range = LookupValueRange(index, block); 788 if (index_range != nullptr && index_range->FitsIn(&array_range)) { 789 ReplaceInstruction(bounds_check, index); 790 return; 791 } 792 // Try range obtained by induction variable analysis. 793 // Disables dynamic bce if OOB is certain. 794 if (InductionRangeFitsIn(&array_range, bounds_check, index, &try_dynamic_bce)) { 795 ReplaceInstruction(bounds_check, index); 796 return; 797 } 798 } else { 799 // Constant subscript. 800 int32_t constant = index->AsIntConstant()->GetValue(); 801 if (constant < 0) { 802 // Will always throw exception. 803 return; 804 } 805 if (array_length->IsIntConstant()) { 806 if (constant < array_length->AsIntConstant()->GetValue()) { 807 ReplaceInstruction(bounds_check, index); 808 } 809 return; 810 } 811 812 DCHECK(array_length->IsArrayLength()); 813 ValueRange* existing_range = LookupValueRange(array_length, block); 814 if (existing_range != nullptr) { 815 ValueBound lower = existing_range->GetLower(); 816 DCHECK(lower.IsConstant()); 817 if (constant < lower.GetConstant()) { 818 ReplaceInstruction(bounds_check, index); 819 return; 820 } else { 821 // Existing range isn't strong enough to eliminate the bounds check. 822 // Fall through to update the array_length range with info from this 823 // bounds check. 824 } 825 } 826 827 if (first_constant_index_bounds_check_map_.find(array_length->GetId()) == 828 first_constant_index_bounds_check_map_.end()) { 829 // Remember the first bounds check against array_length of a constant index. 830 // That bounds check instruction has an associated HEnvironment where we 831 // may add an HDeoptimize to eliminate bounds checks of constant indices 832 // against array_length. 833 first_constant_index_bounds_check_map_.Put(array_length->GetId(), bounds_check); 834 } else { 835 // We've seen it at least twice. It's beneficial to introduce a compare with 836 // deoptimization fallback to eliminate the bounds checks. 837 need_to_revisit_block_ = true; 838 } 839 840 // Once we have an array access like 'array[5] = 1', we record array.length >= 6. 841 // We currently don't do it for non-constant index since a valid array[i] can't prove 842 // a valid array[i-1] yet due to the lower bound side. 843 if (constant == std::numeric_limits<int32_t>::max()) { 844 // Max() as an index will definitely throw AIOOBE. 845 return; 846 } 847 ValueBound lower = ValueBound(nullptr, constant + 1); 848 ValueBound upper = ValueBound::Max(); 849 ValueRange* range = new (GetGraph()->GetArena()) 850 ValueRange(GetGraph()->GetArena(), lower, upper); 851 GetValueRangeMap(block)->Overwrite(array_length->GetId(), range); 852 } 853 854 // If static analysis fails, and OOB is not certain, try dynamic elimination. 855 if (try_dynamic_bce) { 856 TryDynamicBCE(bounds_check); 857 } 858 } 859 860 static bool HasSameInputAtBackEdges(HPhi* phi) { 861 DCHECK(phi->IsLoopHeaderPhi()); 862 // Start with input 1. Input 0 is from the incoming block. 863 HInstruction* input1 = phi->InputAt(1); 864 DCHECK(phi->GetBlock()->GetLoopInformation()->IsBackEdge( 865 *phi->GetBlock()->GetPredecessors()[1])); 866 for (size_t i = 2, e = phi->InputCount(); i < e; ++i) { 867 DCHECK(phi->GetBlock()->GetLoopInformation()->IsBackEdge( 868 *phi->GetBlock()->GetPredecessors()[i])); 869 if (input1 != phi->InputAt(i)) { 870 return false; 871 } 872 } 873 return true; 874 } 875 876 void VisitPhi(HPhi* phi) OVERRIDE { 877 if (phi->IsLoopHeaderPhi() 878 && (phi->GetType() == Primitive::kPrimInt) 879 && HasSameInputAtBackEdges(phi)) { 880 HInstruction* instruction = phi->InputAt(1); 881 HInstruction *left; 882 int32_t increment; 883 if (ValueBound::IsAddOrSubAConstant(instruction, &left, &increment)) { 884 if (left == phi) { 885 HInstruction* initial_value = phi->InputAt(0); 886 ValueRange* range = nullptr; 887 if (increment == 0) { 888 // Add constant 0. It's really a fixed value. 889 range = new (GetGraph()->GetArena()) ValueRange( 890 GetGraph()->GetArena(), 891 ValueBound(initial_value, 0), 892 ValueBound(initial_value, 0)); 893 } else { 894 // Monotonically increasing/decreasing. 895 bool found; 896 ValueBound bound = ValueBound::DetectValueBoundFromValue( 897 initial_value, &found); 898 if (!found) { 899 // No constant or array.length+c bound found. 900 // For i=j, we can still use j's upper bound as i's upper bound. 901 // Same for lower. 902 ValueRange* initial_range = LookupValueRange(initial_value, phi->GetBlock()); 903 if (initial_range != nullptr) { 904 bound = increment > 0 ? initial_range->GetLower() : 905 initial_range->GetUpper(); 906 } else { 907 bound = increment > 0 ? ValueBound::Min() : ValueBound::Max(); 908 } 909 } 910 range = new (GetGraph()->GetArena()) MonotonicValueRange( 911 GetGraph()->GetArena(), 912 phi, 913 initial_value, 914 increment, 915 bound); 916 } 917 GetValueRangeMap(phi->GetBlock())->Overwrite(phi->GetId(), range); 918 } 919 } 920 } 921 } 922 923 void VisitIf(HIf* instruction) OVERRIDE { 924 if (instruction->InputAt(0)->IsCondition()) { 925 HCondition* cond = instruction->InputAt(0)->AsCondition(); 926 IfCondition cmp = cond->GetCondition(); 927 if (cmp == kCondGT || cmp == kCondGE || 928 cmp == kCondLT || cmp == kCondLE) { 929 HInstruction* left = cond->GetLeft(); 930 HInstruction* right = cond->GetRight(); 931 HandleIf(instruction, left, right, cmp); 932 } 933 } 934 } 935 936 void VisitAdd(HAdd* add) OVERRIDE { 937 HInstruction* right = add->GetRight(); 938 if (right->IsIntConstant()) { 939 ValueRange* left_range = LookupValueRange(add->GetLeft(), add->GetBlock()); 940 if (left_range == nullptr) { 941 return; 942 } 943 ValueRange* range = left_range->Add(right->AsIntConstant()->GetValue()); 944 if (range != nullptr) { 945 GetValueRangeMap(add->GetBlock())->Overwrite(add->GetId(), range); 946 } 947 } 948 } 949 950 void VisitSub(HSub* sub) OVERRIDE { 951 HInstruction* left = sub->GetLeft(); 952 HInstruction* right = sub->GetRight(); 953 if (right->IsIntConstant()) { 954 ValueRange* left_range = LookupValueRange(left, sub->GetBlock()); 955 if (left_range == nullptr) { 956 return; 957 } 958 ValueRange* range = left_range->Add(-right->AsIntConstant()->GetValue()); 959 if (range != nullptr) { 960 GetValueRangeMap(sub->GetBlock())->Overwrite(sub->GetId(), range); 961 return; 962 } 963 } 964 965 // Here we are interested in the typical triangular case of nested loops, 966 // such as the inner loop 'for (int j=0; j<array.length-i; j++)' where i 967 // is the index for outer loop. In this case, we know j is bounded by array.length-1. 968 969 // Try to handle (array.length - i) or (array.length + c - i) format. 970 HInstruction* left_of_left; // left input of left. 971 int32_t right_const = 0; 972 if (ValueBound::IsAddOrSubAConstant(left, &left_of_left, &right_const)) { 973 left = left_of_left; 974 } 975 // The value of left input of the sub equals (left + right_const). 976 977 if (left->IsArrayLength()) { 978 HInstruction* array_length = left->AsArrayLength(); 979 ValueRange* right_range = LookupValueRange(right, sub->GetBlock()); 980 if (right_range != nullptr) { 981 ValueBound lower = right_range->GetLower(); 982 ValueBound upper = right_range->GetUpper(); 983 if (lower.IsConstant() && upper.IsRelatedToArrayLength()) { 984 HInstruction* upper_inst = upper.GetInstruction(); 985 // Make sure it's the same array. 986 if (ValueBound::Equal(array_length, upper_inst)) { 987 int32_t c0 = right_const; 988 int32_t c1 = lower.GetConstant(); 989 int32_t c2 = upper.GetConstant(); 990 // (array.length + c0 - v) where v is in [c1, array.length + c2] 991 // gets [c0 - c2, array.length + c0 - c1] as its value range. 992 if (!ValueBound::WouldAddOverflowOrUnderflow(c0, -c2) && 993 !ValueBound::WouldAddOverflowOrUnderflow(c0, -c1)) { 994 if ((c0 - c1) <= 0) { 995 // array.length + (c0 - c1) won't overflow/underflow. 996 ValueRange* range = new (GetGraph()->GetArena()) ValueRange( 997 GetGraph()->GetArena(), 998 ValueBound(nullptr, right_const - upper.GetConstant()), 999 ValueBound(array_length, right_const - lower.GetConstant())); 1000 GetValueRangeMap(sub->GetBlock())->Overwrite(sub->GetId(), range); 1001 } 1002 } 1003 } 1004 } 1005 } 1006 } 1007 } 1008 1009 void FindAndHandlePartialArrayLength(HBinaryOperation* instruction) { 1010 DCHECK(instruction->IsDiv() || instruction->IsShr() || instruction->IsUShr()); 1011 HInstruction* right = instruction->GetRight(); 1012 int32_t right_const; 1013 if (right->IsIntConstant()) { 1014 right_const = right->AsIntConstant()->GetValue(); 1015 // Detect division by two or more. 1016 if ((instruction->IsDiv() && right_const <= 1) || 1017 (instruction->IsShr() && right_const < 1) || 1018 (instruction->IsUShr() && right_const < 1)) { 1019 return; 1020 } 1021 } else { 1022 return; 1023 } 1024 1025 // Try to handle array.length/2 or (array.length-1)/2 format. 1026 HInstruction* left = instruction->GetLeft(); 1027 HInstruction* left_of_left; // left input of left. 1028 int32_t c = 0; 1029 if (ValueBound::IsAddOrSubAConstant(left, &left_of_left, &c)) { 1030 left = left_of_left; 1031 } 1032 // The value of left input of instruction equals (left + c). 1033 1034 // (array_length + 1) or smaller divided by two or more 1035 // always generate a value in [Min(), array_length]. 1036 // This is true even if array_length is Max(). 1037 if (left->IsArrayLength() && c <= 1) { 1038 if (instruction->IsUShr() && c < 0) { 1039 // Make sure for unsigned shift, left side is not negative. 1040 // e.g. if array_length is 2, ((array_length - 3) >>> 2) is way bigger 1041 // than array_length. 1042 return; 1043 } 1044 ValueRange* range = new (GetGraph()->GetArena()) ValueRange( 1045 GetGraph()->GetArena(), 1046 ValueBound(nullptr, std::numeric_limits<int32_t>::min()), 1047 ValueBound(left, 0)); 1048 GetValueRangeMap(instruction->GetBlock())->Overwrite(instruction->GetId(), range); 1049 } 1050 } 1051 1052 void VisitDiv(HDiv* div) OVERRIDE { 1053 FindAndHandlePartialArrayLength(div); 1054 } 1055 1056 void VisitShr(HShr* shr) OVERRIDE { 1057 FindAndHandlePartialArrayLength(shr); 1058 } 1059 1060 void VisitUShr(HUShr* ushr) OVERRIDE { 1061 FindAndHandlePartialArrayLength(ushr); 1062 } 1063 1064 void VisitAnd(HAnd* instruction) OVERRIDE { 1065 if (instruction->GetRight()->IsIntConstant()) { 1066 int32_t constant = instruction->GetRight()->AsIntConstant()->GetValue(); 1067 if (constant > 0) { 1068 // constant serves as a mask so any number masked with it 1069 // gets a [0, constant] value range. 1070 ValueRange* range = new (GetGraph()->GetArena()) ValueRange( 1071 GetGraph()->GetArena(), 1072 ValueBound(nullptr, 0), 1073 ValueBound(nullptr, constant)); 1074 GetValueRangeMap(instruction->GetBlock())->Overwrite(instruction->GetId(), range); 1075 } 1076 } 1077 } 1078 1079 void VisitNewArray(HNewArray* new_array) OVERRIDE { 1080 HInstruction* len = new_array->InputAt(0); 1081 if (!len->IsIntConstant()) { 1082 HInstruction *left; 1083 int32_t right_const; 1084 if (ValueBound::IsAddOrSubAConstant(len, &left, &right_const)) { 1085 // (left + right_const) is used as size to new the array. 1086 // We record "-right_const <= left <= new_array - right_const"; 1087 ValueBound lower = ValueBound(nullptr, -right_const); 1088 // We use new_array for the bound instead of new_array.length, 1089 // which isn't available as an instruction yet. new_array will 1090 // be treated the same as new_array.length when it's used in a ValueBound. 1091 ValueBound upper = ValueBound(new_array, -right_const); 1092 ValueRange* range = new (GetGraph()->GetArena()) 1093 ValueRange(GetGraph()->GetArena(), lower, upper); 1094 ValueRange* existing_range = LookupValueRange(left, new_array->GetBlock()); 1095 if (existing_range != nullptr) { 1096 range = existing_range->Narrow(range); 1097 } 1098 GetValueRangeMap(new_array->GetBlock())->Overwrite(left->GetId(), range); 1099 } 1100 } 1101 } 1102 1103 void VisitDeoptimize(HDeoptimize* deoptimize) OVERRIDE { 1104 if (!deoptimize->InputAt(0)->IsLessThanOrEqual()) { 1105 return; 1106 } 1107 // If this instruction was added by AddCompareWithDeoptimization(), narrow 1108 // the range accordingly in subsequent basic blocks. 1109 HLessThanOrEqual* less_than_or_equal = deoptimize->InputAt(0)->AsLessThanOrEqual(); 1110 HInstruction* instruction = less_than_or_equal->InputAt(0); 1111 if (instruction->IsArrayLength()) { 1112 HInstruction* constant = less_than_or_equal->InputAt(1); 1113 DCHECK(constant->IsIntConstant()); 1114 DCHECK(constant->AsIntConstant()->GetValue() <= kMaxConstantForAddingDeoptimize); 1115 ValueBound lower = ValueBound(nullptr, constant->AsIntConstant()->GetValue() + 1); 1116 ValueRange* range = new (GetGraph()->GetArena()) 1117 ValueRange(GetGraph()->GetArena(), lower, ValueBound::Max()); 1118 GetValueRangeMap(deoptimize->GetBlock())->Overwrite(instruction->GetId(), range); 1119 } 1120 } 1121 1122 /** 1123 * After null/bounds checks are eliminated, some invariant array references 1124 * may be exposed underneath which can be hoisted out of the loop to the 1125 * preheader or, in combination with dynamic bce, the deoptimization block. 1126 * 1127 * for (int i = 0; i < n; i++) { 1128 * <-------+ 1129 * for (int j = 0; j < n; j++) | 1130 * a[i][j] = 0; --a[i]--+ 1131 * } 1132 * 1133 * Note: this optimization is no longer applied after deoptimization on array references 1134 * with constant subscripts has occurred (see AddCompareWithDeoptimization()), since in 1135 * those cases it would be unsafe to hoist array references across their deoptimization 1136 * instruction inside a loop. 1137 */ 1138 void VisitArrayGet(HArrayGet* array_get) OVERRIDE { 1139 if (!has_deoptimization_on_constant_subscripts_ && array_get->IsInLoop()) { 1140 HLoopInformation* loop = array_get->GetBlock()->GetLoopInformation(); 1141 if (loop->IsLoopInvariant(array_get->InputAt(0), false) && 1142 loop->IsLoopInvariant(array_get->InputAt(1), false)) { 1143 SideEffects loop_effects = side_effects_.GetLoopEffects(loop->GetHeader()); 1144 if (!array_get->GetSideEffects().MayDependOn(loop_effects)) { 1145 HoistToPreheaderOrDeoptBlock(loop, array_get); 1146 } 1147 } 1148 } 1149 } 1150 1151 void AddCompareWithDeoptimization(HInstruction* array_length, 1152 HIntConstant* const_instr, 1153 HBasicBlock* block) { 1154 DCHECK(array_length->IsArrayLength()); 1155 ValueRange* range = LookupValueRange(array_length, block); 1156 ValueBound lower_bound = range->GetLower(); 1157 DCHECK(lower_bound.IsConstant()); 1158 DCHECK(const_instr->GetValue() <= kMaxConstantForAddingDeoptimize); 1159 // Note that the lower bound of the array length may have been refined 1160 // through other instructions (such as `HNewArray(length - 4)`). 1161 DCHECK_LE(const_instr->GetValue() + 1, lower_bound.GetConstant()); 1162 1163 // If array_length is less than lower_const, deoptimize. 1164 HBoundsCheck* bounds_check = first_constant_index_bounds_check_map_.Get( 1165 array_length->GetId())->AsBoundsCheck(); 1166 HCondition* cond = new (GetGraph()->GetArena()) HLessThanOrEqual(array_length, const_instr); 1167 HDeoptimize* deoptimize = new (GetGraph()->GetArena()) 1168 HDeoptimize(cond, bounds_check->GetDexPc()); 1169 block->InsertInstructionBefore(cond, bounds_check); 1170 block->InsertInstructionBefore(deoptimize, bounds_check); 1171 deoptimize->CopyEnvironmentFrom(bounds_check->GetEnvironment()); 1172 // Flag that this kind of deoptimization on array references with constant 1173 // subscripts has occurred to prevent further hoisting of these references. 1174 has_deoptimization_on_constant_subscripts_ = true; 1175 } 1176 1177 void AddComparesWithDeoptimization(HBasicBlock* block) { 1178 for (ArenaSafeMap<int, HBoundsCheck*>::iterator it = 1179 first_constant_index_bounds_check_map_.begin(); 1180 it != first_constant_index_bounds_check_map_.end(); 1181 ++it) { 1182 HBoundsCheck* bounds_check = it->second; 1183 HInstruction* array_length = bounds_check->InputAt(1); 1184 if (!array_length->IsArrayLength()) { 1185 // Prior deoptimizations may have changed the array length to a phi. 1186 // TODO(mingyao): propagate the range to the phi? 1187 DCHECK(array_length->IsPhi()) << array_length->DebugName(); 1188 continue; 1189 } 1190 HIntConstant* lower_bound_const_instr = nullptr; 1191 int32_t lower_bound_const = std::numeric_limits<int32_t>::min(); 1192 size_t counter = 0; 1193 // Count the constant indexing for which bounds checks haven't 1194 // been removed yet. 1195 for (HUseIterator<HInstruction*> it2(array_length->GetUses()); 1196 !it2.Done(); 1197 it2.Advance()) { 1198 HInstruction* user = it2.Current()->GetUser(); 1199 if (user->GetBlock() == block && 1200 user->IsBoundsCheck() && 1201 user->AsBoundsCheck()->InputAt(0)->IsIntConstant()) { 1202 DCHECK_EQ(array_length, user->AsBoundsCheck()->InputAt(1)); 1203 HIntConstant* const_instr = user->AsBoundsCheck()->InputAt(0)->AsIntConstant(); 1204 if (const_instr->GetValue() > lower_bound_const) { 1205 lower_bound_const = const_instr->GetValue(); 1206 lower_bound_const_instr = const_instr; 1207 } 1208 counter++; 1209 } 1210 } 1211 if (counter >= kThresholdForAddingDeoptimize && 1212 lower_bound_const_instr->GetValue() <= kMaxConstantForAddingDeoptimize) { 1213 AddCompareWithDeoptimization(array_length, lower_bound_const_instr, block); 1214 } 1215 } 1216 } 1217 1218 /** 1219 * Returns true if static range analysis based on induction variables can determine the bounds 1220 * check on the given array range is always satisfied with the computed index range. The output 1221 * parameter try_dynamic_bce is set to false if OOB is certain. 1222 */ 1223 bool InductionRangeFitsIn(ValueRange* array_range, 1224 HInstruction* context, 1225 HInstruction* index, 1226 bool* try_dynamic_bce) { 1227 InductionVarRange::Value v1; 1228 InductionVarRange::Value v2; 1229 bool needs_finite_test = false; 1230 induction_range_.GetInductionRange(context, index, &v1, &v2, &needs_finite_test); 1231 if (v1.is_known && (v1.a_constant == 0 || v1.a_constant == 1) && 1232 v2.is_known && (v2.a_constant == 0 || v2.a_constant == 1)) { 1233 DCHECK(v1.a_constant == 1 || v1.instruction == nullptr); 1234 DCHECK(v2.a_constant == 1 || v2.instruction == nullptr); 1235 ValueRange index_range(GetGraph()->GetArena(), 1236 ValueBound(v1.instruction, v1.b_constant), 1237 ValueBound(v2.instruction, v2.b_constant)); 1238 // If analysis reveals a certain OOB, disable dynamic BCE. 1239 *try_dynamic_bce = !index_range.GetLower().LessThan(array_range->GetLower()) && 1240 !index_range.GetUpper().GreaterThan(array_range->GetUpper()); 1241 // Use analysis for static bce only if loop is finite. 1242 return !needs_finite_test && index_range.FitsIn(array_range); 1243 } 1244 return false; 1245 } 1246 1247 /** 1248 * When the compiler fails to remove a bounds check statically, we try to remove the bounds 1249 * check dynamically by adding runtime tests that trigger a deoptimization in case bounds 1250 * will go out of range (we want to be rather certain of that given the slowdown of 1251 * deoptimization). If no deoptimization occurs, the loop is executed with all corresponding 1252 * bounds checks and related null checks removed. 1253 */ 1254 void TryDynamicBCE(HBoundsCheck* instruction) { 1255 HLoopInformation* loop = instruction->GetBlock()->GetLoopInformation(); 1256 HInstruction* index = instruction->InputAt(0); 1257 HInstruction* length = instruction->InputAt(1); 1258 // If dynamic bounds check elimination seems profitable and is possible, then proceed. 1259 bool needs_finite_test = false; 1260 bool needs_taken_test = false; 1261 if (DynamicBCESeemsProfitable(loop, instruction->GetBlock()) && 1262 induction_range_.CanGenerateCode( 1263 instruction, index, &needs_finite_test, &needs_taken_test) && 1264 CanHandleInfiniteLoop(loop, index, needs_finite_test) && 1265 CanHandleLength(loop, length, needs_taken_test)) { // do this test last (may code gen) 1266 HInstruction* lower = nullptr; 1267 HInstruction* upper = nullptr; 1268 // Generate the following unsigned comparisons 1269 // if (lower > upper) deoptimize; 1270 // if (upper >= length) deoptimize; 1271 // or, for a non-induction index, just the unsigned comparison on its 'upper' value 1272 // if (upper >= length) deoptimize; 1273 // as runtime test. By restricting dynamic bce to unit strides (with a maximum of 32-bit 1274 // iterations) and by not combining access (e.g. a[i], a[i-3], a[i+5] etc.), these tests 1275 // correctly guard against any possible OOB (including arithmetic wrap-around cases). 1276 HBasicBlock* block = TransformLoopForDeoptimizationIfNeeded(loop, needs_taken_test); 1277 induction_range_.GenerateRangeCode(instruction, index, GetGraph(), block, &lower, &upper); 1278 if (lower != nullptr) { 1279 InsertDeopt(loop, block, new (GetGraph()->GetArena()) HAbove(lower, upper)); 1280 } 1281 InsertDeopt(loop, block, new (GetGraph()->GetArena()) HAboveOrEqual(upper, length)); 1282 ReplaceInstruction(instruction, index); 1283 } 1284 } 1285 1286 /** 1287 * Returns true if heuristics indicate that dynamic bce may be profitable. 1288 */ 1289 bool DynamicBCESeemsProfitable(HLoopInformation* loop, HBasicBlock* block) { 1290 if (loop != nullptr) { 1291 // A try boundary preheader is hard to handle. 1292 // TODO: remove this restriction 1293 if (loop->GetPreHeader()->GetLastInstruction()->IsTryBoundary()) { 1294 return false; 1295 } 1296 // Does loop have early-exits? If so, the full range may not be covered by the loop 1297 // at runtime and testing the range may apply deoptimization unnecessarily. 1298 if (IsEarlyExitLoop(loop)) { 1299 return false; 1300 } 1301 // Does the current basic block dominate all back edges? If not, 1302 // don't apply dynamic bce to something that may not be executed. 1303 for (HBasicBlock* back_edge : loop->GetBackEdges()) { 1304 if (!block->Dominates(back_edge)) { 1305 return false; 1306 } 1307 } 1308 // Success! 1309 return true; 1310 } 1311 return false; 1312 } 1313 1314 /** 1315 * Returns true if the loop has early exits, which implies it may not cover 1316 * the full range computed by range analysis based on induction variables. 1317 */ 1318 bool IsEarlyExitLoop(HLoopInformation* loop) { 1319 const uint32_t loop_id = loop->GetHeader()->GetBlockId(); 1320 // If loop has been analyzed earlier for early-exit, don't repeat the analysis. 1321 auto it = early_exit_loop_.find(loop_id); 1322 if (it != early_exit_loop_.end()) { 1323 return it->second; 1324 } 1325 // First time early-exit analysis for this loop. Since analysis requires scanning 1326 // the full loop-body, results of the analysis is stored for subsequent queries. 1327 HBlocksInLoopReversePostOrderIterator it_loop(*loop); 1328 for (it_loop.Advance(); !it_loop.Done(); it_loop.Advance()) { 1329 for (HBasicBlock* successor : it_loop.Current()->GetSuccessors()) { 1330 if (!loop->Contains(*successor)) { 1331 early_exit_loop_.Put(loop_id, true); 1332 return true; 1333 } 1334 } 1335 } 1336 early_exit_loop_.Put(loop_id, false); 1337 return false; 1338 } 1339 1340 /** 1341 * Returns true if the array length is already loop invariant, or can be made so 1342 * by handling the null check under the hood of the array length operation. 1343 */ 1344 bool CanHandleLength(HLoopInformation* loop, HInstruction* length, bool needs_taken_test) { 1345 if (loop->IsLoopInvariant(length, false)) { 1346 return true; 1347 } else if (length->IsArrayLength() && length->GetBlock()->GetLoopInformation() == loop) { 1348 if (CanHandleNullCheck(loop, length->InputAt(0), needs_taken_test)) { 1349 HoistToPreheaderOrDeoptBlock(loop, length); 1350 return true; 1351 } 1352 } 1353 return false; 1354 } 1355 1356 /** 1357 * Returns true if the null check is already loop invariant, or can be made so 1358 * by generating a deoptimization test. 1359 */ 1360 bool CanHandleNullCheck(HLoopInformation* loop, HInstruction* check, bool needs_taken_test) { 1361 if (loop->IsLoopInvariant(check, false)) { 1362 return true; 1363 } else if (check->IsNullCheck() && check->GetBlock()->GetLoopInformation() == loop) { 1364 HInstruction* array = check->InputAt(0); 1365 if (loop->IsLoopInvariant(array, false)) { 1366 // Generate: if (array == null) deoptimize; 1367 HBasicBlock* block = TransformLoopForDeoptimizationIfNeeded(loop, needs_taken_test); 1368 HInstruction* cond = 1369 new (GetGraph()->GetArena()) HEqual(array, GetGraph()->GetNullConstant()); 1370 InsertDeopt(loop, block, cond); 1371 ReplaceInstruction(check, array); 1372 return true; 1373 } 1374 } 1375 return false; 1376 } 1377 1378 /** 1379 * Returns true if compiler can apply dynamic bce to loops that may be infinite 1380 * (e.g. for (int i = 0; i <= U; i++) with U = MAX_INT), which would invalidate 1381 * the range analysis evaluation code by "overshooting" the computed range. 1382 * Since deoptimization would be a bad choice, and there is no other version 1383 * of the loop to use, dynamic bce in such cases is only allowed if other tests 1384 * ensure the loop is finite. 1385 */ 1386 bool CanHandleInfiniteLoop( 1387 HLoopInformation* loop, HInstruction* index, bool needs_infinite_test) { 1388 if (needs_infinite_test) { 1389 // If we already forced the loop to be finite, allow directly. 1390 const uint32_t loop_id = loop->GetHeader()->GetBlockId(); 1391 if (finite_loop_.find(loop_id) != finite_loop_.end()) { 1392 return true; 1393 } 1394 // Otherwise, allow dynamic bce if the index (which is necessarily an induction at 1395 // this point) is the direct loop index (viz. a[i]), since then the runtime tests 1396 // ensure upper bound cannot cause an infinite loop. 1397 HInstruction* control = loop->GetHeader()->GetLastInstruction(); 1398 if (control->IsIf()) { 1399 HInstruction* if_expr = control->AsIf()->InputAt(0); 1400 if (if_expr->IsCondition()) { 1401 HCondition* condition = if_expr->AsCondition(); 1402 if (index == condition->InputAt(0) || 1403 index == condition->InputAt(1)) { 1404 finite_loop_.insert(loop_id); 1405 return true; 1406 } 1407 } 1408 } 1409 return false; 1410 } 1411 return true; 1412 } 1413 1414 /** Inserts a deoptimization test. */ 1415 void InsertDeopt(HLoopInformation* loop, HBasicBlock* block, HInstruction* condition) { 1416 HInstruction* suspend = loop->GetSuspendCheck(); 1417 block->InsertInstructionBefore(condition, block->GetLastInstruction()); 1418 HDeoptimize* deoptimize = 1419 new (GetGraph()->GetArena()) HDeoptimize(condition, suspend->GetDexPc()); 1420 block->InsertInstructionBefore(deoptimize, block->GetLastInstruction()); 1421 if (suspend->HasEnvironment()) { 1422 deoptimize->CopyEnvironmentFromWithLoopPhiAdjustment( 1423 suspend->GetEnvironment(), loop->GetHeader()); 1424 } 1425 } 1426 1427 /** Hoists instruction out of the loop to preheader or deoptimization block. */ 1428 void HoistToPreheaderOrDeoptBlock(HLoopInformation* loop, HInstruction* instruction) { 1429 // Use preheader unless there is an earlier generated deoptimization block since 1430 // hoisted expressions may depend on and/or used by the deoptimization tests. 1431 const uint32_t loop_id = loop->GetHeader()->GetBlockId(); 1432 HBasicBlock* preheader = loop->GetPreHeader(); 1433 HBasicBlock* block = preheader; 1434 auto it = taken_test_loop_.find(loop_id); 1435 if (it != taken_test_loop_.end()) { 1436 block = it->second; 1437 } 1438 // Hoist the instruction. 1439 DCHECK(!instruction->HasEnvironment()); 1440 instruction->MoveBefore(block->GetLastInstruction()); 1441 } 1442 1443 /** 1444 * Adds a new taken-test structure to a loop if needed (and not already done). 1445 * The taken-test protects range analysis evaluation code to avoid any 1446 * deoptimization caused by incorrect trip-count evaluation in non-taken loops. 1447 * 1448 * Returns block in which deoptimizations/invariants can be put. 1449 * 1450 * old_preheader 1451 * | 1452 * if_block <- taken-test protects deoptimization block 1453 * / \ 1454 * true_block false_block <- deoptimizations/invariants are placed in true_block 1455 * \ / 1456 * new_preheader <- may require phi nodes to preserve SSA structure 1457 * | 1458 * header 1459 * 1460 * For example, this loop: 1461 * 1462 * for (int i = lower; i < upper; i++) { 1463 * array[i] = 0; 1464 * } 1465 * 1466 * will be transformed to: 1467 * 1468 * if (lower < upper) { 1469 * if (array == null) deoptimize; 1470 * array_length = array.length; 1471 * if (lower > upper) deoptimize; // unsigned 1472 * if (upper >= array_length) deoptimize; // unsigned 1473 * } else { 1474 * array_length = 0; 1475 * } 1476 * for (int i = lower; i < upper; i++) { 1477 * // Loop without null check and bounds check, and any array.length replaced with array_length. 1478 * array[i] = 0; 1479 * } 1480 */ 1481 HBasicBlock* TransformLoopForDeoptimizationIfNeeded(HLoopInformation* loop, bool needs_taken_test) { 1482 // Not needed (can use preheader), or already done (can reuse)? 1483 const uint32_t loop_id = loop->GetHeader()->GetBlockId(); 1484 if (!needs_taken_test) { 1485 return loop->GetPreHeader(); 1486 } else { 1487 auto it = taken_test_loop_.find(loop_id); 1488 if (it != taken_test_loop_.end()) { 1489 return it->second; 1490 } 1491 } 1492 1493 // Generate top test structure. 1494 HBasicBlock* header = loop->GetHeader(); 1495 GetGraph()->TransformLoopHeaderForBCE(header); 1496 HBasicBlock* new_preheader = loop->GetPreHeader(); 1497 HBasicBlock* if_block = new_preheader->GetDominator(); 1498 HBasicBlock* true_block = if_block->GetSuccessors()[0]; // True successor. 1499 HBasicBlock* false_block = if_block->GetSuccessors()[1]; // False successor. 1500 1501 // Goto instructions. 1502 true_block->AddInstruction(new (GetGraph()->GetArena()) HGoto()); 1503 false_block->AddInstruction(new (GetGraph()->GetArena()) HGoto()); 1504 new_preheader->AddInstruction(new (GetGraph()->GetArena()) HGoto()); 1505 1506 // Insert the taken-test to see if the loop body is entered. If the 1507 // loop isn't entered at all, it jumps around the deoptimization block. 1508 if_block->AddInstruction(new (GetGraph()->GetArena()) HGoto()); // placeholder 1509 HInstruction* condition = nullptr; 1510 induction_range_.GenerateTakenTest(header->GetLastInstruction(), 1511 GetGraph(), 1512 if_block, 1513 &condition); 1514 DCHECK(condition != nullptr); 1515 if_block->RemoveInstruction(if_block->GetLastInstruction()); 1516 if_block->AddInstruction(new (GetGraph()->GetArena()) HIf(condition)); 1517 1518 taken_test_loop_.Put(loop_id, true_block); 1519 return true_block; 1520 } 1521 1522 /** 1523 * Inserts phi nodes that preserve SSA structure in generated top test structures. 1524 * All uses of instructions in the deoptimization block that reach the loop need 1525 * a phi node in the new loop preheader to fix the dominance relation. 1526 * 1527 * Example: 1528 * if_block 1529 * / \ 1530 * x_0 = .. false_block 1531 * \ / 1532 * x_1 = phi(x_0, null) <- synthetic phi 1533 * | 1534 * header 1535 */ 1536 void InsertPhiNodes() { 1537 // Scan all new deoptimization blocks. 1538 for (auto it1 = taken_test_loop_.begin(); it1 != taken_test_loop_.end(); ++it1) { 1539 HBasicBlock* true_block = it1->second; 1540 HBasicBlock* new_preheader = true_block->GetSingleSuccessor(); 1541 // Scan all instructions in a new deoptimization block. 1542 for (HInstructionIterator it(true_block->GetInstructions()); !it.Done(); it.Advance()) { 1543 HInstruction* instruction = it.Current(); 1544 Primitive::Type type = instruction->GetType(); 1545 HPhi* phi = nullptr; 1546 // Scan all uses of an instruction and replace each later use with a phi node. 1547 for (HUseIterator<HInstruction*> it2(instruction->GetUses()); 1548 !it2.Done(); 1549 it2.Advance()) { 1550 HInstruction* user = it2.Current()->GetUser(); 1551 if (user->GetBlock() != true_block) { 1552 if (phi == nullptr) { 1553 phi = NewPhi(new_preheader, instruction, type); 1554 } 1555 user->ReplaceInput(phi, it2.Current()->GetIndex()); 1556 } 1557 } 1558 // Scan all environment uses of an instruction and replace each later use with a phi node. 1559 for (HUseIterator<HEnvironment*> it2(instruction->GetEnvUses()); 1560 !it2.Done(); 1561 it2.Advance()) { 1562 HEnvironment* user = it2.Current()->GetUser(); 1563 if (user->GetHolder()->GetBlock() != true_block) { 1564 if (phi == nullptr) { 1565 phi = NewPhi(new_preheader, instruction, type); 1566 } 1567 user->RemoveAsUserOfInput(it2.Current()->GetIndex()); 1568 user->SetRawEnvAt(it2.Current()->GetIndex(), phi); 1569 phi->AddEnvUseAt(user, it2.Current()->GetIndex()); 1570 } 1571 } 1572 } 1573 } 1574 } 1575 1576 /** 1577 * Construct a phi(instruction, 0) in the new preheader to fix the dominance relation. 1578 * These are synthetic phi nodes without a virtual register. 1579 */ 1580 HPhi* NewPhi(HBasicBlock* new_preheader, 1581 HInstruction* instruction, 1582 Primitive::Type type) { 1583 HGraph* graph = GetGraph(); 1584 HInstruction* zero; 1585 switch (type) { 1586 case Primitive::Type::kPrimNot: zero = graph->GetNullConstant(); break; 1587 case Primitive::Type::kPrimFloat: zero = graph->GetFloatConstant(0); break; 1588 case Primitive::Type::kPrimDouble: zero = graph->GetDoubleConstant(0); break; 1589 default: zero = graph->GetConstant(type, 0); break; 1590 } 1591 HPhi* phi = new (graph->GetArena()) 1592 HPhi(graph->GetArena(), kNoRegNumber, /*number_of_inputs*/ 2, HPhi::ToPhiType(type)); 1593 phi->SetRawInputAt(0, instruction); 1594 phi->SetRawInputAt(1, zero); 1595 new_preheader->AddPhi(phi); 1596 return phi; 1597 } 1598 1599 /** Helper method to replace an instruction with another instruction. */ 1600 static void ReplaceInstruction(HInstruction* instruction, HInstruction* replacement) { 1601 instruction->ReplaceWith(replacement); 1602 instruction->GetBlock()->RemoveInstruction(instruction); 1603 } 1604 1605 // A set of maps, one per basic block, from instruction to range. 1606 ArenaVector<ArenaSafeMap<int, ValueRange*>> maps_; 1607 1608 // Map an HArrayLength instruction's id to the first HBoundsCheck instruction in 1609 // a block that checks a constant index against that HArrayLength. 1610 ArenaSafeMap<int, HBoundsCheck*> first_constant_index_bounds_check_map_; 1611 1612 // Early-exit loop bookkeeping. 1613 ArenaSafeMap<uint32_t, bool> early_exit_loop_; 1614 1615 // Taken-test loop bookkeeping. 1616 ArenaSafeMap<uint32_t, HBasicBlock*> taken_test_loop_; 1617 1618 // Finite loop bookkeeping. 1619 ArenaSet<uint32_t> finite_loop_; 1620 1621 // For the block, there is at least one HArrayLength instruction for which there 1622 // is more than one bounds check instruction with constant indexing. And it's 1623 // beneficial to add a compare instruction that has deoptimization fallback and 1624 // eliminate those bounds checks. 1625 bool need_to_revisit_block_; 1626 1627 // Flag that denotes whether deoptimization has occurred on array references 1628 // with constant subscripts (see AddCompareWithDeoptimization()). 1629 bool has_deoptimization_on_constant_subscripts_; 1630 1631 // Initial number of blocks. 1632 uint32_t initial_block_size_; 1633 1634 // Side effects. 1635 const SideEffectsAnalysis& side_effects_; 1636 1637 // Range analysis based on induction variables. 1638 InductionVarRange induction_range_; 1639 1640 DISALLOW_COPY_AND_ASSIGN(BCEVisitor); 1641}; 1642 1643void BoundsCheckElimination::Run() { 1644 if (!graph_->HasBoundsChecks()) { 1645 return; 1646 } 1647 1648 // Reverse post order guarantees a node's dominators are visited first. 1649 // We want to visit in the dominator-based order since if a value is known to 1650 // be bounded by a range at one instruction, it must be true that all uses of 1651 // that value dominated by that instruction fits in that range. Range of that 1652 // value can be narrowed further down in the dominator tree. 1653 BCEVisitor visitor(graph_, side_effects_, induction_analysis_); 1654 HBasicBlock* last_visited_block = nullptr; 1655 for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { 1656 HBasicBlock* current = it.Current(); 1657 if (current == last_visited_block) { 1658 // We may insert blocks into the reverse post order list when processing 1659 // a loop header. Don't process it again. 1660 DCHECK(current->IsLoopHeader()); 1661 continue; 1662 } 1663 if (visitor.IsAddedBlock(current)) { 1664 // Skip added blocks. Their effects are already taken care of. 1665 continue; 1666 } 1667 visitor.VisitBasicBlock(current); 1668 last_visited_block = current; 1669 } 1670 1671 // Perform cleanup. 1672 visitor.Finish(); 1673} 1674 1675} // namespace art 1676