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/scoped_arena_allocator.h" 22 #include "base/scoped_arena_containers.h" 23 #include "induction_var_range.h" 24 #include "nodes.h" 25 #include "side_effects_analysis.h" 26 27 namespace art { 28 29 class MonotonicValueRange; 30 31 /** 32 * A value bound is represented as a pair of value and constant, 33 * e.g. array.length - 1. 34 */ 35 class ValueBound : public ValueObject { 36 public: 37 ValueBound(HInstruction* instruction, int32_t constant) { 38 if (instruction != nullptr && instruction->IsIntConstant()) { 39 // Normalize ValueBound with constant instruction. 40 int32_t instr_const = instruction->AsIntConstant()->GetValue(); 41 if (!WouldAddOverflowOrUnderflow(instr_const, constant)) { 42 instruction_ = nullptr; 43 constant_ = instr_const + constant; 44 return; 45 } 46 } 47 instruction_ = instruction; 48 constant_ = constant; 49 } 50 51 // Return whether (left + right) overflows or underflows. 52 static bool WouldAddOverflowOrUnderflow(int32_t left, int32_t right) { 53 if (right == 0) { 54 return false; 55 } 56 if ((right > 0) && (left <= (std::numeric_limits<int32_t>::max() - right))) { 57 // No overflow. 58 return false; 59 } 60 if ((right < 0) && (left >= (std::numeric_limits<int32_t>::min() - right))) { 61 // No underflow. 62 return false; 63 } 64 return true; 65 } 66 67 // Return true if instruction can be expressed as "left_instruction + right_constant". 68 static bool IsAddOrSubAConstant(HInstruction* instruction, 69 /* out */ HInstruction** left_instruction, 70 /* out */ int32_t* right_constant) { 71 HInstruction* left_so_far = nullptr; 72 int32_t right_so_far = 0; 73 while (instruction->IsAdd() || instruction->IsSub()) { 74 HBinaryOperation* bin_op = instruction->AsBinaryOperation(); 75 HInstruction* left = bin_op->GetLeft(); 76 HInstruction* right = bin_op->GetRight(); 77 if (right->IsIntConstant()) { 78 int32_t v = right->AsIntConstant()->GetValue(); 79 int32_t c = instruction->IsAdd() ? v : -v; 80 if (!WouldAddOverflowOrUnderflow(right_so_far, c)) { 81 instruction = left; 82 left_so_far = left; 83 right_so_far += c; 84 continue; 85 } 86 } 87 break; 88 } 89 // Return result: either false and "null+0" or true and "instr+constant". 90 *left_instruction = left_so_far; 91 *right_constant = right_so_far; 92 return left_so_far != nullptr; 93 } 94 95 // Expresses any instruction as a value bound. 96 static ValueBound AsValueBound(HInstruction* instruction) { 97 if (instruction->IsIntConstant()) { 98 return ValueBound(nullptr, instruction->AsIntConstant()->GetValue()); 99 } 100 HInstruction *left; 101 int32_t right; 102 if (IsAddOrSubAConstant(instruction, &left, &right)) { 103 return ValueBound(left, right); 104 } 105 return ValueBound(instruction, 0); 106 } 107 108 // Try to detect useful value bound format from an instruction, e.g. 109 // a constant or array length related value. 110 static ValueBound DetectValueBoundFromValue(HInstruction* instruction, /* out */ bool* found) { 111 DCHECK(instruction != nullptr); 112 if (instruction->IsIntConstant()) { 113 *found = true; 114 return ValueBound(nullptr, instruction->AsIntConstant()->GetValue()); 115 } 116 117 if (instruction->IsArrayLength()) { 118 *found = true; 119 return ValueBound(instruction, 0); 120 } 121 // Try to detect (array.length + c) format. 122 HInstruction *left; 123 int32_t right; 124 if (IsAddOrSubAConstant(instruction, &left, &right)) { 125 if (left->IsArrayLength()) { 126 *found = true; 127 return ValueBound(left, right); 128 } 129 } 130 131 // No useful bound detected. 132 *found = false; 133 return ValueBound::Max(); 134 } 135 136 HInstruction* GetInstruction() const { return instruction_; } 137 int32_t GetConstant() const { return constant_; } 138 139 bool IsRelatedToArrayLength() const { 140 // Some bounds are created with HNewArray* as the instruction instead 141 // of HArrayLength*. They are treated the same. 142 return (instruction_ != nullptr) && 143 (instruction_->IsArrayLength() || instruction_->IsNewArray()); 144 } 145 146 bool IsConstant() const { 147 return instruction_ == nullptr; 148 } 149 150 static ValueBound Min() { return ValueBound(nullptr, std::numeric_limits<int32_t>::min()); } 151 static ValueBound Max() { return ValueBound(nullptr, std::numeric_limits<int32_t>::max()); } 152 153 bool Equals(ValueBound bound) const { 154 return instruction_ == bound.instruction_ && constant_ == bound.constant_; 155 } 156 157 static bool Equal(HInstruction* instruction1, HInstruction* instruction2) { 158 if (instruction1 == instruction2) { 159 return true; 160 } 161 if (instruction1 == nullptr || instruction2 == nullptr) { 162 return false; 163 } 164 instruction1 = HuntForDeclaration(instruction1); 165 instruction2 = HuntForDeclaration(instruction2); 166 return instruction1 == instruction2; 167 } 168 169 // Returns if it's certain this->bound >= `bound`. 170 bool GreaterThanOrEqualTo(ValueBound bound) const { 171 if (Equal(instruction_, bound.instruction_)) { 172 return constant_ >= bound.constant_; 173 } 174 // Not comparable. Just return false. 175 return false; 176 } 177 178 // Returns if it's certain this->bound <= `bound`. 179 bool LessThanOrEqualTo(ValueBound bound) const { 180 if (Equal(instruction_, bound.instruction_)) { 181 return constant_ <= bound.constant_; 182 } 183 // Not comparable. Just return false. 184 return false; 185 } 186 187 // Returns if it's certain this->bound > `bound`. 188 bool GreaterThan(ValueBound bound) const { 189 if (Equal(instruction_, bound.instruction_)) { 190 return constant_ > bound.constant_; 191 } 192 // Not comparable. Just return false. 193 return false; 194 } 195 196 // Returns if it's certain this->bound < `bound`. 197 bool LessThan(ValueBound bound) const { 198 if (Equal(instruction_, bound.instruction_)) { 199 return constant_ < bound.constant_; 200 } 201 // Not comparable. Just return false. 202 return false; 203 } 204 205 // Try to narrow lower bound. Returns the greatest of the two if possible. 206 // Pick one if they are not comparable. 207 static ValueBound NarrowLowerBound(ValueBound bound1, ValueBound bound2) { 208 if (bound1.GreaterThanOrEqualTo(bound2)) { 209 return bound1; 210 } 211 if (bound2.GreaterThanOrEqualTo(bound1)) { 212 return bound2; 213 } 214 215 // Not comparable. Just pick one. We may lose some info, but that's ok. 216 // Favor constant as lower bound. 217 return bound1.IsConstant() ? bound1 : bound2; 218 } 219 220 // Try to narrow upper bound. Returns the lowest of the two if possible. 221 // Pick one if they are not comparable. 222 static ValueBound NarrowUpperBound(ValueBound bound1, ValueBound bound2) { 223 if (bound1.LessThanOrEqualTo(bound2)) { 224 return bound1; 225 } 226 if (bound2.LessThanOrEqualTo(bound1)) { 227 return bound2; 228 } 229 230 // Not comparable. Just pick one. We may lose some info, but that's ok. 231 // Favor array length as upper bound. 232 return bound1.IsRelatedToArrayLength() ? bound1 : bound2; 233 } 234 235 // Add a constant to a ValueBound. 236 // `overflow` or `underflow` will return whether the resulting bound may 237 // overflow or underflow an int. 238 ValueBound Add(int32_t c, /* out */ bool* overflow, /* out */ bool* underflow) const { 239 *overflow = *underflow = false; 240 if (c == 0) { 241 return *this; 242 } 243 244 int32_t new_constant; 245 if (c > 0) { 246 if (constant_ > (std::numeric_limits<int32_t>::max() - c)) { 247 *overflow = true; 248 return Max(); 249 } 250 251 new_constant = constant_ + c; 252 // (array.length + non-positive-constant) won't overflow an int. 253 if (IsConstant() || (IsRelatedToArrayLength() && new_constant <= 0)) { 254 return ValueBound(instruction_, new_constant); 255 } 256 // Be conservative. 257 *overflow = true; 258 return Max(); 259 } else { 260 if (constant_ < (std::numeric_limits<int32_t>::min() - c)) { 261 *underflow = true; 262 return Min(); 263 } 264 265 new_constant = constant_ + c; 266 // Regardless of the value new_constant, (array.length+new_constant) will 267 // never underflow since array.length is no less than 0. 268 if (IsConstant() || IsRelatedToArrayLength()) { 269 return ValueBound(instruction_, new_constant); 270 } 271 // Be conservative. 272 *underflow = true; 273 return Min(); 274 } 275 } 276 277 private: 278 HInstruction* instruction_; 279 int32_t constant_; 280 }; 281 282 /** 283 * Represent a range of lower bound and upper bound, both being inclusive. 284 * Currently a ValueRange may be generated as a result of the following: 285 * comparisons related to array bounds, array bounds check, add/sub on top 286 * of an existing value range, NewArray or a loop phi corresponding to an 287 * incrementing/decrementing array index (MonotonicValueRange). 288 */ 289 class ValueRange : public ArenaObject<kArenaAllocBoundsCheckElimination> { 290 public: 291 ValueRange(ScopedArenaAllocator* allocator, ValueBound lower, ValueBound upper) 292 : allocator_(allocator), lower_(lower), upper_(upper) {} 293 294 virtual ~ValueRange() {} 295 296 virtual MonotonicValueRange* AsMonotonicValueRange() { return nullptr; } 297 bool IsMonotonicValueRange() { 298 return AsMonotonicValueRange() != nullptr; 299 } 300 301 ScopedArenaAllocator* GetAllocator() const { return allocator_; } 302 ValueBound GetLower() const { return lower_; } 303 ValueBound GetUpper() const { return upper_; } 304 305 bool IsConstantValueRange() const { return lower_.IsConstant() && upper_.IsConstant(); } 306 307 // If it's certain that this value range fits in other_range. 308 virtual bool FitsIn(ValueRange* other_range) const { 309 if (other_range == nullptr) { 310 return true; 311 } 312 DCHECK(!other_range->IsMonotonicValueRange()); 313 return lower_.GreaterThanOrEqualTo(other_range->lower_) && 314 upper_.LessThanOrEqualTo(other_range->upper_); 315 } 316 317 // Returns the intersection of this and range. 318 // If it's not possible to do intersection because some 319 // bounds are not comparable, it's ok to pick either bound. 320 virtual ValueRange* Narrow(ValueRange* range) { 321 if (range == nullptr) { 322 return this; 323 } 324 325 if (range->IsMonotonicValueRange()) { 326 return this; 327 } 328 329 return new (allocator_) ValueRange( 330 allocator_, 331 ValueBound::NarrowLowerBound(lower_, range->lower_), 332 ValueBound::NarrowUpperBound(upper_, range->upper_)); 333 } 334 335 // Shift a range by a constant. 336 ValueRange* Add(int32_t constant) const { 337 bool overflow, underflow; 338 ValueBound lower = lower_.Add(constant, &overflow, &underflow); 339 if (underflow) { 340 // Lower bound underflow will wrap around to positive values 341 // and invalidate the upper bound. 342 return nullptr; 343 } 344 ValueBound upper = upper_.Add(constant, &overflow, &underflow); 345 if (overflow) { 346 // Upper bound overflow will wrap around to negative values 347 // and invalidate the lower bound. 348 return nullptr; 349 } 350 return new (allocator_) ValueRange(allocator_, lower, upper); 351 } 352 353 private: 354 ScopedArenaAllocator* const allocator_; 355 const ValueBound lower_; // inclusive 356 const ValueBound upper_; // inclusive 357 358 DISALLOW_COPY_AND_ASSIGN(ValueRange); 359 }; 360 361 /** 362 * A monotonically incrementing/decrementing value range, e.g. 363 * the variable i in "for (int i=0; i<array.length; i++)". 364 * Special care needs to be taken to account for overflow/underflow 365 * of such value ranges. 366 */ 367 class MonotonicValueRange : public ValueRange { 368 public: 369 MonotonicValueRange(ScopedArenaAllocator* allocator, 370 HPhi* induction_variable, 371 HInstruction* initial, 372 int32_t increment, 373 ValueBound bound) 374 // To be conservative, give it full range [Min(), Max()] in case it's 375 // used as a regular value range, due to possible overflow/underflow. 376 : ValueRange(allocator, ValueBound::Min(), ValueBound::Max()), 377 induction_variable_(induction_variable), 378 initial_(initial), 379 increment_(increment), 380 bound_(bound) {} 381 382 virtual ~MonotonicValueRange() {} 383 384 int32_t GetIncrement() const { return increment_; } 385 ValueBound GetBound() const { return bound_; } 386 HBasicBlock* GetLoopHeader() const { 387 DCHECK(induction_variable_->GetBlock()->IsLoopHeader()); 388 return induction_variable_->GetBlock(); 389 } 390 391 MonotonicValueRange* AsMonotonicValueRange() OVERRIDE { return this; } 392 393 // If it's certain that this value range fits in other_range. 394 bool FitsIn(ValueRange* other_range) const OVERRIDE { 395 if (other_range == nullptr) { 396 return true; 397 } 398 DCHECK(!other_range->IsMonotonicValueRange()); 399 return false; 400 } 401 402 // Try to narrow this MonotonicValueRange given another range. 403 // Ideally it will return a normal ValueRange. But due to 404 // possible overflow/underflow, that may not be possible. 405 ValueRange* Narrow(ValueRange* range) OVERRIDE { 406 if (range == nullptr) { 407 return this; 408 } 409 DCHECK(!range->IsMonotonicValueRange()); 410 411 if (increment_ > 0) { 412 // Monotonically increasing. 413 ValueBound lower = ValueBound::NarrowLowerBound(bound_, range->GetLower()); 414 if (!lower.IsConstant() || lower.GetConstant() == std::numeric_limits<int32_t>::min()) { 415 // Lower bound isn't useful. Leave it to deoptimization. 416 return this; 417 } 418 419 // We currently conservatively assume max array length is Max(). 420 // If we can make assumptions about the max array length, e.g. due to the max heap size, 421 // divided by the element size (such as 4 bytes for each integer array), we can 422 // lower this number and rule out some possible overflows. 423 int32_t max_array_len = std::numeric_limits<int32_t>::max(); 424 425 // max possible integer value of range's upper value. 426 int32_t upper = std::numeric_limits<int32_t>::max(); 427 // Try to lower upper. 428 ValueBound upper_bound = range->GetUpper(); 429 if (upper_bound.IsConstant()) { 430 upper = upper_bound.GetConstant(); 431 } else if (upper_bound.IsRelatedToArrayLength() && upper_bound.GetConstant() <= 0) { 432 // Normal case. e.g. <= array.length - 1. 433 upper = max_array_len + upper_bound.GetConstant(); 434 } 435 436 // If we can prove for the last number in sequence of initial_, 437 // initial_ + increment_, initial_ + 2 x increment_, ... 438 // that's <= upper, (last_num_in_sequence + increment_) doesn't trigger overflow, 439 // then this MonoticValueRange is narrowed to a normal value range. 440 441 // Be conservative first, assume last number in the sequence hits upper. 442 int32_t last_num_in_sequence = upper; 443 if (initial_->IsIntConstant()) { 444 int32_t initial_constant = initial_->AsIntConstant()->GetValue(); 445 if (upper <= initial_constant) { 446 last_num_in_sequence = upper; 447 } else { 448 // Cast to int64_t for the substraction part to avoid int32_t overflow. 449 last_num_in_sequence = initial_constant + 450 ((int64_t)upper - (int64_t)initial_constant) / increment_ * increment_; 451 } 452 } 453 if (last_num_in_sequence <= (std::numeric_limits<int32_t>::max() - increment_)) { 454 // No overflow. The sequence will be stopped by the upper bound test as expected. 455 return new (GetAllocator()) ValueRange(GetAllocator(), lower, range->GetUpper()); 456 } 457 458 // There might be overflow. Give up narrowing. 459 return this; 460 } else { 461 DCHECK_NE(increment_, 0); 462 // Monotonically decreasing. 463 ValueBound upper = ValueBound::NarrowUpperBound(bound_, range->GetUpper()); 464 if ((!upper.IsConstant() || upper.GetConstant() == std::numeric_limits<int32_t>::max()) && 465 !upper.IsRelatedToArrayLength()) { 466 // Upper bound isn't useful. Leave it to deoptimization. 467 return this; 468 } 469 470 // Need to take care of underflow. Try to prove underflow won't happen 471 // for common cases. 472 if (range->GetLower().IsConstant()) { 473 int32_t constant = range->GetLower().GetConstant(); 474 if (constant >= (std::numeric_limits<int32_t>::min() - increment_)) { 475 return new (GetAllocator()) ValueRange(GetAllocator(), range->GetLower(), upper); 476 } 477 } 478 479 // For non-constant lower bound, just assume might be underflow. Give up narrowing. 480 return this; 481 } 482 } 483 484 private: 485 HPhi* const induction_variable_; // Induction variable for this monotonic value range. 486 HInstruction* const initial_; // Initial value. 487 const int32_t increment_; // Increment for each loop iteration. 488 const ValueBound bound_; // Additional value bound info for initial_. 489 490 DISALLOW_COPY_AND_ASSIGN(MonotonicValueRange); 491 }; 492 493 class BCEVisitor : public HGraphVisitor { 494 public: 495 // The least number of bounds checks that should be eliminated by triggering 496 // the deoptimization technique. 497 static constexpr size_t kThresholdForAddingDeoptimize = 2; 498 499 // Very large lengths are considered an anomaly. This is a threshold beyond which we don't 500 // bother to apply the deoptimization technique since it's likely, or sometimes certain, 501 // an AIOOBE will be thrown. 502 static constexpr uint32_t kMaxLengthForAddingDeoptimize = 503 std::numeric_limits<int32_t>::max() - 1024 * 1024; 504 505 // Added blocks for loop body entry test. 506 bool IsAddedBlock(HBasicBlock* block) const { 507 return block->GetBlockId() >= initial_block_size_; 508 } 509 510 BCEVisitor(HGraph* graph, 511 const SideEffectsAnalysis& side_effects, 512 HInductionVarAnalysis* induction_analysis) 513 : HGraphVisitor(graph), 514 allocator_(graph->GetArenaStack()), 515 maps_(graph->GetBlocks().size(), 516 ScopedArenaSafeMap<int, ValueRange*>( 517 std::less<int>(), 518 allocator_.Adapter(kArenaAllocBoundsCheckElimination)), 519 allocator_.Adapter(kArenaAllocBoundsCheckElimination)), 520 first_index_bounds_check_map_(std::less<int>(), 521 allocator_.Adapter(kArenaAllocBoundsCheckElimination)), 522 early_exit_loop_(std::less<uint32_t>(), 523 allocator_.Adapter(kArenaAllocBoundsCheckElimination)), 524 taken_test_loop_(std::less<uint32_t>(), 525 allocator_.Adapter(kArenaAllocBoundsCheckElimination)), 526 finite_loop_(allocator_.Adapter(kArenaAllocBoundsCheckElimination)), 527 has_dom_based_dynamic_bce_(false), 528 initial_block_size_(graph->GetBlocks().size()), 529 side_effects_(side_effects), 530 induction_range_(induction_analysis), 531 next_(nullptr) {} 532 533 void VisitBasicBlock(HBasicBlock* block) OVERRIDE { 534 DCHECK(!IsAddedBlock(block)); 535 first_index_bounds_check_map_.clear(); 536 // Visit phis and instructions using a safe iterator. The iteration protects 537 // against deleting the current instruction during iteration. However, it 538 // must advance next_ if that instruction is deleted during iteration. 539 for (HInstruction* instruction = block->GetFirstPhi(); instruction != nullptr;) { 540 DCHECK(instruction->IsInBlock()); 541 next_ = instruction->GetNext(); 542 instruction->Accept(this); 543 instruction = next_; 544 } 545 for (HInstruction* instruction = block->GetFirstInstruction(); instruction != nullptr;) { 546 DCHECK(instruction->IsInBlock()); 547 next_ = instruction->GetNext(); 548 instruction->Accept(this); 549 instruction = next_; 550 } 551 // We should never deoptimize from an osr method, otherwise we might wrongly optimize 552 // code dominated by the deoptimization. 553 if (!GetGraph()->IsCompilingOsr()) { 554 AddComparesWithDeoptimization(block); 555 } 556 } 557 558 void Finish() { 559 // Preserve SSA structure which may have been broken by adding one or more 560 // new taken-test structures (see TransformLoopForDeoptimizationIfNeeded()). 561 InsertPhiNodes(); 562 563 // Clear the loop data structures. 564 early_exit_loop_.clear(); 565 taken_test_loop_.clear(); 566 finite_loop_.clear(); 567 } 568 569 private: 570 // Return the map of proven value ranges at the beginning of a basic block. 571 ScopedArenaSafeMap<int, ValueRange*>* GetValueRangeMap(HBasicBlock* basic_block) { 572 if (IsAddedBlock(basic_block)) { 573 // Added blocks don't keep value ranges. 574 return nullptr; 575 } 576 return &maps_[basic_block->GetBlockId()]; 577 } 578 579 // Traverse up the dominator tree to look for value range info. 580 ValueRange* LookupValueRange(HInstruction* instruction, HBasicBlock* basic_block) { 581 while (basic_block != nullptr) { 582 ScopedArenaSafeMap<int, ValueRange*>* map = GetValueRangeMap(basic_block); 583 if (map != nullptr) { 584 if (map->find(instruction->GetId()) != map->end()) { 585 return map->Get(instruction->GetId()); 586 } 587 } else { 588 DCHECK(IsAddedBlock(basic_block)); 589 } 590 basic_block = basic_block->GetDominator(); 591 } 592 // Didn't find any. 593 return nullptr; 594 } 595 596 // Helper method to assign a new range to an instruction in given basic block. 597 void AssignRange(HBasicBlock* basic_block, HInstruction* instruction, ValueRange* range) { 598 DCHECK(!range->IsMonotonicValueRange() || instruction->IsLoopHeaderPhi()); 599 GetValueRangeMap(basic_block)->Overwrite(instruction->GetId(), range); 600 } 601 602 // Narrow the value range of `instruction` at the end of `basic_block` with `range`, 603 // and push the narrowed value range to `successor`. 604 void ApplyRangeFromComparison(HInstruction* instruction, HBasicBlock* basic_block, 605 HBasicBlock* successor, ValueRange* range) { 606 ValueRange* existing_range = LookupValueRange(instruction, basic_block); 607 if (existing_range == nullptr) { 608 if (range != nullptr) { 609 AssignRange(successor, instruction, range); 610 } 611 return; 612 } 613 if (existing_range->IsMonotonicValueRange()) { 614 DCHECK(instruction->IsLoopHeaderPhi()); 615 // Make sure the comparison is in the loop header so each increment is 616 // checked with a comparison. 617 if (instruction->GetBlock() != basic_block) { 618 return; 619 } 620 } 621 AssignRange(successor, instruction, existing_range->Narrow(range)); 622 } 623 624 // Special case that we may simultaneously narrow two MonotonicValueRange's to 625 // regular value ranges. 626 void HandleIfBetweenTwoMonotonicValueRanges(HIf* instruction, 627 HInstruction* left, 628 HInstruction* right, 629 IfCondition cond, 630 MonotonicValueRange* left_range, 631 MonotonicValueRange* right_range) { 632 DCHECK(left->IsLoopHeaderPhi()); 633 DCHECK(right->IsLoopHeaderPhi()); 634 if (instruction->GetBlock() != left->GetBlock()) { 635 // Comparison needs to be in loop header to make sure it's done after each 636 // increment/decrement. 637 return; 638 } 639 640 // Handle common cases which also don't have overflow/underflow concerns. 641 if (left_range->GetIncrement() == 1 && 642 left_range->GetBound().IsConstant() && 643 right_range->GetIncrement() == -1 && 644 right_range->GetBound().IsRelatedToArrayLength() && 645 right_range->GetBound().GetConstant() < 0) { 646 HBasicBlock* successor = nullptr; 647 int32_t left_compensation = 0; 648 int32_t right_compensation = 0; 649 if (cond == kCondLT) { 650 left_compensation = -1; 651 right_compensation = 1; 652 successor = instruction->IfTrueSuccessor(); 653 } else if (cond == kCondLE) { 654 successor = instruction->IfTrueSuccessor(); 655 } else if (cond == kCondGT) { 656 successor = instruction->IfFalseSuccessor(); 657 } else if (cond == kCondGE) { 658 left_compensation = -1; 659 right_compensation = 1; 660 successor = instruction->IfFalseSuccessor(); 661 } else { 662 // We don't handle '=='/'!=' test in case left and right can cross and 663 // miss each other. 664 return; 665 } 666 667 if (successor != nullptr) { 668 bool overflow; 669 bool underflow; 670 ValueRange* new_left_range = new (&allocator_) ValueRange( 671 &allocator_, 672 left_range->GetBound(), 673 right_range->GetBound().Add(left_compensation, &overflow, &underflow)); 674 if (!overflow && !underflow) { 675 ApplyRangeFromComparison(left, instruction->GetBlock(), successor, 676 new_left_range); 677 } 678 679 ValueRange* new_right_range = new (&allocator_) ValueRange( 680 &allocator_, 681 left_range->GetBound().Add(right_compensation, &overflow, &underflow), 682 right_range->GetBound()); 683 if (!overflow && !underflow) { 684 ApplyRangeFromComparison(right, instruction->GetBlock(), successor, 685 new_right_range); 686 } 687 } 688 } 689 } 690 691 // Handle "if (left cmp_cond right)". 692 void HandleIf(HIf* instruction, HInstruction* left, HInstruction* right, IfCondition cond) { 693 HBasicBlock* block = instruction->GetBlock(); 694 695 HBasicBlock* true_successor = instruction->IfTrueSuccessor(); 696 // There should be no critical edge at this point. 697 DCHECK_EQ(true_successor->GetPredecessors().size(), 1u); 698 699 HBasicBlock* false_successor = instruction->IfFalseSuccessor(); 700 // There should be no critical edge at this point. 701 DCHECK_EQ(false_successor->GetPredecessors().size(), 1u); 702 703 ValueRange* left_range = LookupValueRange(left, block); 704 MonotonicValueRange* left_monotonic_range = nullptr; 705 if (left_range != nullptr) { 706 left_monotonic_range = left_range->AsMonotonicValueRange(); 707 if (left_monotonic_range != nullptr) { 708 HBasicBlock* loop_head = left_monotonic_range->GetLoopHeader(); 709 if (instruction->GetBlock() != loop_head) { 710 // For monotonic value range, don't handle `instruction` 711 // if it's not defined in the loop header. 712 return; 713 } 714 } 715 } 716 717 bool found; 718 ValueBound bound = ValueBound::DetectValueBoundFromValue(right, &found); 719 // Each comparison can establish a lower bound and an upper bound 720 // for the left hand side. 721 ValueBound lower = bound; 722 ValueBound upper = bound; 723 if (!found) { 724 // No constant or array.length+c format bound found. 725 // For i<j, we can still use j's upper bound as i's upper bound. Same for lower. 726 ValueRange* right_range = LookupValueRange(right, block); 727 if (right_range != nullptr) { 728 if (right_range->IsMonotonicValueRange()) { 729 if (left_range != nullptr && left_range->IsMonotonicValueRange()) { 730 HandleIfBetweenTwoMonotonicValueRanges(instruction, left, right, cond, 731 left_range->AsMonotonicValueRange(), 732 right_range->AsMonotonicValueRange()); 733 return; 734 } 735 } 736 lower = right_range->GetLower(); 737 upper = right_range->GetUpper(); 738 } else { 739 lower = ValueBound::Min(); 740 upper = ValueBound::Max(); 741 } 742 } 743 744 bool overflow, underflow; 745 if (cond == kCondLT || cond == kCondLE) { 746 if (!upper.Equals(ValueBound::Max())) { 747 int32_t compensation = (cond == kCondLT) ? -1 : 0; // upper bound is inclusive 748 ValueBound new_upper = upper.Add(compensation, &overflow, &underflow); 749 if (overflow || underflow) { 750 return; 751 } 752 ValueRange* new_range = new (&allocator_) ValueRange( 753 &allocator_, ValueBound::Min(), new_upper); 754 ApplyRangeFromComparison(left, block, true_successor, new_range); 755 } 756 757 // array.length as a lower bound isn't considered useful. 758 if (!lower.Equals(ValueBound::Min()) && !lower.IsRelatedToArrayLength()) { 759 int32_t compensation = (cond == kCondLE) ? 1 : 0; // lower bound is inclusive 760 ValueBound new_lower = lower.Add(compensation, &overflow, &underflow); 761 if (overflow || underflow) { 762 return; 763 } 764 ValueRange* new_range = new (&allocator_) ValueRange( 765 &allocator_, new_lower, ValueBound::Max()); 766 ApplyRangeFromComparison(left, block, false_successor, new_range); 767 } 768 } else if (cond == kCondGT || cond == kCondGE) { 769 // array.length as a lower bound isn't considered useful. 770 if (!lower.Equals(ValueBound::Min()) && !lower.IsRelatedToArrayLength()) { 771 int32_t compensation = (cond == kCondGT) ? 1 : 0; // lower bound is inclusive 772 ValueBound new_lower = lower.Add(compensation, &overflow, &underflow); 773 if (overflow || underflow) { 774 return; 775 } 776 ValueRange* new_range = new (&allocator_) ValueRange( 777 &allocator_, new_lower, ValueBound::Max()); 778 ApplyRangeFromComparison(left, block, true_successor, new_range); 779 } 780 781 if (!upper.Equals(ValueBound::Max())) { 782 int32_t compensation = (cond == kCondGE) ? -1 : 0; // upper bound is inclusive 783 ValueBound new_upper = upper.Add(compensation, &overflow, &underflow); 784 if (overflow || underflow) { 785 return; 786 } 787 ValueRange* new_range = new (&allocator_) ValueRange( 788 &allocator_, ValueBound::Min(), new_upper); 789 ApplyRangeFromComparison(left, block, false_successor, new_range); 790 } 791 } else if (cond == kCondNE || cond == kCondEQ) { 792 if (left->IsArrayLength()) { 793 if (lower.IsConstant() && upper.IsConstant()) { 794 // Special case: 795 // length == [c,d] yields [c, d] along true 796 // length != [c,d] yields [c, d] along false 797 if (!lower.Equals(ValueBound::Min()) || !upper.Equals(ValueBound::Max())) { 798 ValueRange* new_range = new (&allocator_) ValueRange(&allocator_, lower, upper); 799 ApplyRangeFromComparison( 800 left, block, cond == kCondEQ ? true_successor : false_successor, new_range); 801 } 802 // In addition: 803 // length == 0 yields [1, max] along false 804 // length != 0 yields [1, max] along true 805 if (lower.GetConstant() == 0 && upper.GetConstant() == 0) { 806 ValueRange* new_range = new (&allocator_) ValueRange( 807 &allocator_, ValueBound(nullptr, 1), ValueBound::Max()); 808 ApplyRangeFromComparison( 809 left, block, cond == kCondEQ ? false_successor : true_successor, new_range); 810 } 811 } 812 } else if (lower.IsRelatedToArrayLength() && lower.Equals(upper)) { 813 // Special aliasing case, with x not array length itself: 814 // x == [length,length] yields x == length along true 815 // x != [length,length] yields x == length along false 816 ValueRange* new_range = new (&allocator_) ValueRange(&allocator_, lower, upper); 817 ApplyRangeFromComparison( 818 left, block, cond == kCondEQ ? true_successor : false_successor, new_range); 819 } 820 } 821 } 822 823 void VisitBoundsCheck(HBoundsCheck* bounds_check) OVERRIDE { 824 HBasicBlock* block = bounds_check->GetBlock(); 825 HInstruction* index = bounds_check->InputAt(0); 826 HInstruction* array_length = bounds_check->InputAt(1); 827 DCHECK(array_length->IsIntConstant() || 828 array_length->IsArrayLength() || 829 array_length->IsPhi()); 830 bool try_dynamic_bce = true; 831 // Analyze index range. 832 if (!index->IsIntConstant()) { 833 // Non-constant index. 834 ValueBound lower = ValueBound(nullptr, 0); // constant 0 835 ValueBound upper = ValueBound(array_length, -1); // array_length - 1 836 ValueRange array_range(&allocator_, lower, upper); 837 // Try index range obtained by dominator-based analysis. 838 ValueRange* index_range = LookupValueRange(index, block); 839 if (index_range != nullptr) { 840 if (index_range->FitsIn(&array_range)) { 841 ReplaceInstruction(bounds_check, index); 842 return; 843 } else if (index_range->IsConstantValueRange()) { 844 // If the non-constant index turns out to have a constant range, 845 // make one more attempt to get a constant in the array range. 846 ValueRange* existing_range = LookupValueRange(array_length, block); 847 if (existing_range != nullptr && 848 existing_range->IsConstantValueRange()) { 849 ValueRange constant_array_range(&allocator_, lower, existing_range->GetLower()); 850 if (index_range->FitsIn(&constant_array_range)) { 851 ReplaceInstruction(bounds_check, index); 852 return; 853 } 854 } 855 } 856 } 857 // Try index range obtained by induction variable analysis. 858 // Disables dynamic bce if OOB is certain. 859 if (InductionRangeFitsIn(&array_range, bounds_check, &try_dynamic_bce)) { 860 ReplaceInstruction(bounds_check, index); 861 return; 862 } 863 } else { 864 // Constant index. 865 int32_t constant = index->AsIntConstant()->GetValue(); 866 if (constant < 0) { 867 // Will always throw exception. 868 return; 869 } else if (array_length->IsIntConstant()) { 870 if (constant < array_length->AsIntConstant()->GetValue()) { 871 ReplaceInstruction(bounds_check, index); 872 } 873 return; 874 } 875 // Analyze array length range. 876 DCHECK(array_length->IsArrayLength()); 877 ValueRange* existing_range = LookupValueRange(array_length, block); 878 if (existing_range != nullptr) { 879 ValueBound lower = existing_range->GetLower(); 880 DCHECK(lower.IsConstant()); 881 if (constant < lower.GetConstant()) { 882 ReplaceInstruction(bounds_check, index); 883 return; 884 } else { 885 // Existing range isn't strong enough to eliminate the bounds check. 886 // Fall through to update the array_length range with info from this 887 // bounds check. 888 } 889 } 890 // Once we have an array access like 'array[5] = 1', we record array.length >= 6. 891 // We currently don't do it for non-constant index since a valid array[i] can't prove 892 // a valid array[i-1] yet due to the lower bound side. 893 if (constant == std::numeric_limits<int32_t>::max()) { 894 // Max() as an index will definitely throw AIOOBE. 895 return; 896 } else { 897 ValueBound lower = ValueBound(nullptr, constant + 1); 898 ValueBound upper = ValueBound::Max(); 899 ValueRange* range = new (&allocator_) ValueRange(&allocator_, lower, upper); 900 AssignRange(block, array_length, range); 901 } 902 } 903 904 // If static analysis fails, and OOB is not certain, try dynamic elimination. 905 if (try_dynamic_bce) { 906 // Try loop-based dynamic elimination. 907 HLoopInformation* loop = bounds_check->GetBlock()->GetLoopInformation(); 908 bool needs_finite_test = false; 909 bool needs_taken_test = false; 910 if (DynamicBCESeemsProfitable(loop, bounds_check->GetBlock()) && 911 induction_range_.CanGenerateRange( 912 bounds_check, index, &needs_finite_test, &needs_taken_test) && 913 CanHandleInfiniteLoop(loop, index, needs_finite_test) && 914 // Do this test last, since it may generate code. 915 CanHandleLength(loop, array_length, needs_taken_test)) { 916 TransformLoopForDeoptimizationIfNeeded(loop, needs_taken_test); 917 TransformLoopForDynamicBCE(loop, bounds_check); 918 return; 919 } 920 // Otherwise, prepare dominator-based dynamic elimination. 921 if (first_index_bounds_check_map_.find(array_length->GetId()) == 922 first_index_bounds_check_map_.end()) { 923 // Remember the first bounds check against each array_length. That bounds check 924 // instruction has an associated HEnvironment where we may add an HDeoptimize 925 // to eliminate subsequent bounds checks against the same array_length. 926 first_index_bounds_check_map_.Put(array_length->GetId(), bounds_check); 927 } 928 } 929 } 930 931 static bool HasSameInputAtBackEdges(HPhi* phi) { 932 DCHECK(phi->IsLoopHeaderPhi()); 933 HConstInputsRef inputs = phi->GetInputs(); 934 // Start with input 1. Input 0 is from the incoming block. 935 const HInstruction* input1 = inputs[1]; 936 DCHECK(phi->GetBlock()->GetLoopInformation()->IsBackEdge( 937 *phi->GetBlock()->GetPredecessors()[1])); 938 for (size_t i = 2; i < inputs.size(); ++i) { 939 DCHECK(phi->GetBlock()->GetLoopInformation()->IsBackEdge( 940 *phi->GetBlock()->GetPredecessors()[i])); 941 if (input1 != inputs[i]) { 942 return false; 943 } 944 } 945 return true; 946 } 947 948 void VisitPhi(HPhi* phi) OVERRIDE { 949 if (phi->IsLoopHeaderPhi() 950 && (phi->GetType() == DataType::Type::kInt32) 951 && HasSameInputAtBackEdges(phi)) { 952 HInstruction* instruction = phi->InputAt(1); 953 HInstruction *left; 954 int32_t increment; 955 if (ValueBound::IsAddOrSubAConstant(instruction, &left, &increment)) { 956 if (left == phi) { 957 HInstruction* initial_value = phi->InputAt(0); 958 ValueRange* range = nullptr; 959 if (increment == 0) { 960 // Add constant 0. It's really a fixed value. 961 range = new (&allocator_) ValueRange( 962 &allocator_, 963 ValueBound(initial_value, 0), 964 ValueBound(initial_value, 0)); 965 } else { 966 // Monotonically increasing/decreasing. 967 bool found; 968 ValueBound bound = ValueBound::DetectValueBoundFromValue( 969 initial_value, &found); 970 if (!found) { 971 // No constant or array.length+c bound found. 972 // For i=j, we can still use j's upper bound as i's upper bound. 973 // Same for lower. 974 ValueRange* initial_range = LookupValueRange(initial_value, phi->GetBlock()); 975 if (initial_range != nullptr) { 976 bound = increment > 0 ? initial_range->GetLower() : 977 initial_range->GetUpper(); 978 } else { 979 bound = increment > 0 ? ValueBound::Min() : ValueBound::Max(); 980 } 981 } 982 range = new (&allocator_) MonotonicValueRange( 983 &allocator_, 984 phi, 985 initial_value, 986 increment, 987 bound); 988 } 989 AssignRange(phi->GetBlock(), phi, range); 990 } 991 } 992 } 993 } 994 995 void VisitIf(HIf* instruction) OVERRIDE { 996 if (instruction->InputAt(0)->IsCondition()) { 997 HCondition* cond = instruction->InputAt(0)->AsCondition(); 998 HandleIf(instruction, cond->GetLeft(), cond->GetRight(), cond->GetCondition()); 999 } 1000 } 1001 1002 void VisitAdd(HAdd* add) OVERRIDE { 1003 HInstruction* right = add->GetRight(); 1004 if (right->IsIntConstant()) { 1005 ValueRange* left_range = LookupValueRange(add->GetLeft(), add->GetBlock()); 1006 if (left_range == nullptr) { 1007 return; 1008 } 1009 ValueRange* range = left_range->Add(right->AsIntConstant()->GetValue()); 1010 if (range != nullptr) { 1011 AssignRange(add->GetBlock(), add, range); 1012 } 1013 } 1014 } 1015 1016 void VisitSub(HSub* sub) OVERRIDE { 1017 HInstruction* left = sub->GetLeft(); 1018 HInstruction* right = sub->GetRight(); 1019 if (right->IsIntConstant()) { 1020 ValueRange* left_range = LookupValueRange(left, sub->GetBlock()); 1021 if (left_range == nullptr) { 1022 return; 1023 } 1024 ValueRange* range = left_range->Add(-right->AsIntConstant()->GetValue()); 1025 if (range != nullptr) { 1026 AssignRange(sub->GetBlock(), sub, range); 1027 return; 1028 } 1029 } 1030 1031 // Here we are interested in the typical triangular case of nested loops, 1032 // such as the inner loop 'for (int j=0; j<array.length-i; j++)' where i 1033 // is the index for outer loop. In this case, we know j is bounded by array.length-1. 1034 1035 // Try to handle (array.length - i) or (array.length + c - i) format. 1036 HInstruction* left_of_left; // left input of left. 1037 int32_t right_const = 0; 1038 if (ValueBound::IsAddOrSubAConstant(left, &left_of_left, &right_const)) { 1039 left = left_of_left; 1040 } 1041 // The value of left input of the sub equals (left + right_const). 1042 1043 if (left->IsArrayLength()) { 1044 HInstruction* array_length = left->AsArrayLength(); 1045 ValueRange* right_range = LookupValueRange(right, sub->GetBlock()); 1046 if (right_range != nullptr) { 1047 ValueBound lower = right_range->GetLower(); 1048 ValueBound upper = right_range->GetUpper(); 1049 if (lower.IsConstant() && upper.IsRelatedToArrayLength()) { 1050 HInstruction* upper_inst = upper.GetInstruction(); 1051 // Make sure it's the same array. 1052 if (ValueBound::Equal(array_length, upper_inst)) { 1053 int32_t c0 = right_const; 1054 int32_t c1 = lower.GetConstant(); 1055 int32_t c2 = upper.GetConstant(); 1056 // (array.length + c0 - v) where v is in [c1, array.length + c2] 1057 // gets [c0 - c2, array.length + c0 - c1] as its value range. 1058 if (!ValueBound::WouldAddOverflowOrUnderflow(c0, -c2) && 1059 !ValueBound::WouldAddOverflowOrUnderflow(c0, -c1)) { 1060 if ((c0 - c1) <= 0) { 1061 // array.length + (c0 - c1) won't overflow/underflow. 1062 ValueRange* range = new (&allocator_) ValueRange( 1063 &allocator_, 1064 ValueBound(nullptr, right_const - upper.GetConstant()), 1065 ValueBound(array_length, right_const - lower.GetConstant())); 1066 AssignRange(sub->GetBlock(), sub, range); 1067 } 1068 } 1069 } 1070 } 1071 } 1072 } 1073 } 1074 1075 void FindAndHandlePartialArrayLength(HBinaryOperation* instruction) { 1076 DCHECK(instruction->IsDiv() || instruction->IsShr() || instruction->IsUShr()); 1077 HInstruction* right = instruction->GetRight(); 1078 int32_t right_const; 1079 if (right->IsIntConstant()) { 1080 right_const = right->AsIntConstant()->GetValue(); 1081 // Detect division by two or more. 1082 if ((instruction->IsDiv() && right_const <= 1) || 1083 (instruction->IsShr() && right_const < 1) || 1084 (instruction->IsUShr() && right_const < 1)) { 1085 return; 1086 } 1087 } else { 1088 return; 1089 } 1090 1091 // Try to handle array.length/2 or (array.length-1)/2 format. 1092 HInstruction* left = instruction->GetLeft(); 1093 HInstruction* left_of_left; // left input of left. 1094 int32_t c = 0; 1095 if (ValueBound::IsAddOrSubAConstant(left, &left_of_left, &c)) { 1096 left = left_of_left; 1097 } 1098 // The value of left input of instruction equals (left + c). 1099 1100 // (array_length + 1) or smaller divided by two or more 1101 // always generate a value in [Min(), array_length]. 1102 // This is true even if array_length is Max(). 1103 if (left->IsArrayLength() && c <= 1) { 1104 if (instruction->IsUShr() && c < 0) { 1105 // Make sure for unsigned shift, left side is not negative. 1106 // e.g. if array_length is 2, ((array_length - 3) >>> 2) is way bigger 1107 // than array_length. 1108 return; 1109 } 1110 ValueRange* range = new (&allocator_) ValueRange( 1111 &allocator_, 1112 ValueBound(nullptr, std::numeric_limits<int32_t>::min()), 1113 ValueBound(left, 0)); 1114 AssignRange(instruction->GetBlock(), instruction, range); 1115 } 1116 } 1117 1118 void VisitDiv(HDiv* div) OVERRIDE { 1119 FindAndHandlePartialArrayLength(div); 1120 } 1121 1122 void VisitShr(HShr* shr) OVERRIDE { 1123 FindAndHandlePartialArrayLength(shr); 1124 } 1125 1126 void VisitUShr(HUShr* ushr) OVERRIDE { 1127 FindAndHandlePartialArrayLength(ushr); 1128 } 1129 1130 void VisitAnd(HAnd* instruction) OVERRIDE { 1131 if (instruction->GetRight()->IsIntConstant()) { 1132 int32_t constant = instruction->GetRight()->AsIntConstant()->GetValue(); 1133 if (constant > 0) { 1134 // constant serves as a mask so any number masked with it 1135 // gets a [0, constant] value range. 1136 ValueRange* range = new (&allocator_) ValueRange( 1137 &allocator_, 1138 ValueBound(nullptr, 0), 1139 ValueBound(nullptr, constant)); 1140 AssignRange(instruction->GetBlock(), instruction, range); 1141 } 1142 } 1143 } 1144 1145 void VisitRem(HRem* instruction) OVERRIDE { 1146 HInstruction* left = instruction->GetLeft(); 1147 HInstruction* right = instruction->GetRight(); 1148 1149 // Handle 'i % CONST' format expression in array index, e.g: 1150 // array[i % 20]; 1151 if (right->IsIntConstant()) { 1152 int32_t right_const = std::abs(right->AsIntConstant()->GetValue()); 1153 if (right_const == 0) { 1154 return; 1155 } 1156 // The sign of divisor CONST doesn't affect the sign final value range. 1157 // For example: 1158 // if (i > 0) { 1159 // array[i % 10]; // index value range [0, 9] 1160 // array[i % -10]; // index value range [0, 9] 1161 // } 1162 ValueRange* right_range = new (&allocator_) ValueRange( 1163 &allocator_, 1164 ValueBound(nullptr, 1 - right_const), 1165 ValueBound(nullptr, right_const - 1)); 1166 1167 ValueRange* left_range = LookupValueRange(left, instruction->GetBlock()); 1168 if (left_range != nullptr) { 1169 right_range = right_range->Narrow(left_range); 1170 } 1171 AssignRange(instruction->GetBlock(), instruction, right_range); 1172 return; 1173 } 1174 1175 // Handle following pattern: 1176 // i0 NullCheck 1177 // i1 ArrayLength[i0] 1178 // i2 DivByZeroCheck [i1] <-- right 1179 // i3 Rem [i5, i2] <-- we are here. 1180 // i4 BoundsCheck [i3,i1] 1181 if (right->IsDivZeroCheck()) { 1182 // if array_length can pass div-by-zero check, 1183 // array_length must be > 0. 1184 right = right->AsDivZeroCheck()->InputAt(0); 1185 } 1186 1187 // Handle 'i % array.length' format expression in array index, e.g: 1188 // array[(i+7) % array.length]; 1189 if (right->IsArrayLength()) { 1190 ValueBound lower = ValueBound::Min(); // ideally, lower should be '1-array_length'. 1191 ValueBound upper = ValueBound(right, -1); // array_length - 1 1192 ValueRange* right_range = new (&allocator_) ValueRange( 1193 &allocator_, 1194 lower, 1195 upper); 1196 ValueRange* left_range = LookupValueRange(left, instruction->GetBlock()); 1197 if (left_range != nullptr) { 1198 right_range = right_range->Narrow(left_range); 1199 } 1200 AssignRange(instruction->GetBlock(), instruction, right_range); 1201 return; 1202 } 1203 } 1204 1205 void VisitNewArray(HNewArray* new_array) OVERRIDE { 1206 HInstruction* len = new_array->GetLength(); 1207 if (!len->IsIntConstant()) { 1208 HInstruction *left; 1209 int32_t right_const; 1210 if (ValueBound::IsAddOrSubAConstant(len, &left, &right_const)) { 1211 // (left + right_const) is used as size to new the array. 1212 // We record "-right_const <= left <= new_array - right_const"; 1213 ValueBound lower = ValueBound(nullptr, -right_const); 1214 // We use new_array for the bound instead of new_array.length, 1215 // which isn't available as an instruction yet. new_array will 1216 // be treated the same as new_array.length when it's used in a ValueBound. 1217 ValueBound upper = ValueBound(new_array, -right_const); 1218 ValueRange* range = new (&allocator_) ValueRange(&allocator_, lower, upper); 1219 ValueRange* existing_range = LookupValueRange(left, new_array->GetBlock()); 1220 if (existing_range != nullptr) { 1221 range = existing_range->Narrow(range); 1222 } 1223 AssignRange(new_array->GetBlock(), left, range); 1224 } 1225 } 1226 } 1227 1228 /** 1229 * After null/bounds checks are eliminated, some invariant array references 1230 * may be exposed underneath which can be hoisted out of the loop to the 1231 * preheader or, in combination with dynamic bce, the deoptimization block. 1232 * 1233 * for (int i = 0; i < n; i++) { 1234 * <-------+ 1235 * for (int j = 0; j < n; j++) | 1236 * a[i][j] = 0; --a[i]--+ 1237 * } 1238 * 1239 * Note: this optimization is no longer applied after dominator-based dynamic deoptimization 1240 * has occurred (see AddCompareWithDeoptimization()), since in those cases it would be 1241 * unsafe to hoist array references across their deoptimization instruction inside a loop. 1242 */ 1243 void VisitArrayGet(HArrayGet* array_get) OVERRIDE { 1244 if (!has_dom_based_dynamic_bce_ && array_get->IsInLoop()) { 1245 HLoopInformation* loop = array_get->GetBlock()->GetLoopInformation(); 1246 if (loop->IsDefinedOutOfTheLoop(array_get->InputAt(0)) && 1247 loop->IsDefinedOutOfTheLoop(array_get->InputAt(1))) { 1248 SideEffects loop_effects = side_effects_.GetLoopEffects(loop->GetHeader()); 1249 if (!array_get->GetSideEffects().MayDependOn(loop_effects)) { 1250 // We can hoist ArrayGet only if its execution is guaranteed on every iteration. 1251 // In other words only if array_get_bb dominates all back branches. 1252 if (loop->DominatesAllBackEdges(array_get->GetBlock())) { 1253 HoistToPreHeaderOrDeoptBlock(loop, array_get); 1254 } 1255 } 1256 } 1257 } 1258 } 1259 1260 /** Performs dominator-based dynamic elimination on suitable set of bounds checks. */ 1261 void AddCompareWithDeoptimization(HBasicBlock* block, 1262 HInstruction* array_length, 1263 HInstruction* base, 1264 int32_t min_c, int32_t max_c) { 1265 HBoundsCheck* bounds_check = 1266 first_index_bounds_check_map_.Get(array_length->GetId())->AsBoundsCheck(); 1267 // Construct deoptimization on single or double bounds on range [base-min_c,base+max_c], 1268 // for example either for a[0]..a[3] just 3 or for a[base-1]..a[base+3] both base-1 1269 // and base+3, since we made the assumption any in between value may occur too. 1270 // In code, using unsigned comparisons: 1271 // (1) constants only 1272 // if (max_c >= a.length) deoptimize; 1273 // (2) general case 1274 // if (base-min_c > base+max_c) deoptimize; 1275 // if (base+max_c >= a.length ) deoptimize; 1276 static_assert(kMaxLengthForAddingDeoptimize < std::numeric_limits<int32_t>::max(), 1277 "Incorrect max length may be subject to arithmetic wrap-around"); 1278 HInstruction* upper = GetGraph()->GetIntConstant(max_c); 1279 if (base == nullptr) { 1280 DCHECK_GE(min_c, 0); 1281 } else { 1282 HInstruction* lower = new (GetGraph()->GetAllocator()) 1283 HAdd(DataType::Type::kInt32, base, GetGraph()->GetIntConstant(min_c)); 1284 upper = new (GetGraph()->GetAllocator()) HAdd(DataType::Type::kInt32, base, upper); 1285 block->InsertInstructionBefore(lower, bounds_check); 1286 block->InsertInstructionBefore(upper, bounds_check); 1287 InsertDeoptInBlock(bounds_check, new (GetGraph()->GetAllocator()) HAbove(lower, upper)); 1288 } 1289 InsertDeoptInBlock( 1290 bounds_check, new (GetGraph()->GetAllocator()) HAboveOrEqual(upper, array_length)); 1291 // Flag that this kind of deoptimization has occurred. 1292 has_dom_based_dynamic_bce_ = true; 1293 } 1294 1295 /** Attempts dominator-based dynamic elimination on remaining candidates. */ 1296 void AddComparesWithDeoptimization(HBasicBlock* block) { 1297 for (const auto& entry : first_index_bounds_check_map_) { 1298 HBoundsCheck* bounds_check = entry.second; 1299 HInstruction* index = bounds_check->InputAt(0); 1300 HInstruction* array_length = bounds_check->InputAt(1); 1301 if (!array_length->IsArrayLength()) { 1302 continue; // disregard phis and constants 1303 } 1304 // Collect all bounds checks that are still there and that are related as "a[base + constant]" 1305 // for a base instruction (possibly absent) and various constants. Note that no attempt 1306 // is made to partition the set into matching subsets (viz. a[0], a[1] and a[base+1] and 1307 // a[base+2] are considered as one set). 1308 // TODO: would such a partitioning be worthwhile? 1309 ValueBound value = ValueBound::AsValueBound(index); 1310 HInstruction* base = value.GetInstruction(); 1311 int32_t min_c = base == nullptr ? 0 : value.GetConstant(); 1312 int32_t max_c = value.GetConstant(); 1313 ScopedArenaVector<HBoundsCheck*> candidates( 1314 allocator_.Adapter(kArenaAllocBoundsCheckElimination)); 1315 ScopedArenaVector<HBoundsCheck*> standby( 1316 allocator_.Adapter(kArenaAllocBoundsCheckElimination)); 1317 for (const HUseListNode<HInstruction*>& use : array_length->GetUses()) { 1318 // Another bounds check in same or dominated block? 1319 HInstruction* user = use.GetUser(); 1320 HBasicBlock* other_block = user->GetBlock(); 1321 if (user->IsBoundsCheck() && block->Dominates(other_block)) { 1322 HBoundsCheck* other_bounds_check = user->AsBoundsCheck(); 1323 HInstruction* other_index = other_bounds_check->InputAt(0); 1324 HInstruction* other_array_length = other_bounds_check->InputAt(1); 1325 ValueBound other_value = ValueBound::AsValueBound(other_index); 1326 if (array_length == other_array_length && base == other_value.GetInstruction()) { 1327 // Reject certain OOB if BoundsCheck(l, l) occurs on considered subset. 1328 if (array_length == other_index) { 1329 candidates.clear(); 1330 standby.clear(); 1331 break; 1332 } 1333 // Since a subsequent dominated block could be under a conditional, only accept 1334 // the other bounds check if it is in same block or both blocks dominate the exit. 1335 // TODO: we could improve this by testing proper post-dominance, or even if this 1336 // constant is seen along *all* conditional paths that follow. 1337 HBasicBlock* exit = GetGraph()->GetExitBlock(); 1338 if (block == user->GetBlock() || 1339 (block->Dominates(exit) && other_block->Dominates(exit))) { 1340 int32_t other_c = other_value.GetConstant(); 1341 min_c = std::min(min_c, other_c); 1342 max_c = std::max(max_c, other_c); 1343 candidates.push_back(other_bounds_check); 1344 } else { 1345 // Add this candidate later only if it falls into the range. 1346 standby.push_back(other_bounds_check); 1347 } 1348 } 1349 } 1350 } 1351 // Add standby candidates that fall in selected range. 1352 for (HBoundsCheck* other_bounds_check : standby) { 1353 HInstruction* other_index = other_bounds_check->InputAt(0); 1354 int32_t other_c = ValueBound::AsValueBound(other_index).GetConstant(); 1355 if (min_c <= other_c && other_c <= max_c) { 1356 candidates.push_back(other_bounds_check); 1357 } 1358 } 1359 // Perform dominator-based deoptimization if it seems profitable, where we eliminate 1360 // bounds checks and replace these with deopt checks that guard against any possible 1361 // OOB. Note that we reject cases where the distance min_c:max_c range gets close to 1362 // the maximum possible array length, since those cases are likely to always deopt 1363 // (such situations do not necessarily go OOB, though, since the array could be really 1364 // large, or the programmer could rely on arithmetic wrap-around from max to min). 1365 size_t threshold = kThresholdForAddingDeoptimize + (base == nullptr ? 0 : 1); // extra test? 1366 uint32_t distance = static_cast<uint32_t>(max_c) - static_cast<uint32_t>(min_c); 1367 if (candidates.size() >= threshold && 1368 (base != nullptr || min_c >= 0) && // reject certain OOB 1369 distance <= kMaxLengthForAddingDeoptimize) { // reject likely/certain deopt 1370 AddCompareWithDeoptimization(block, array_length, base, min_c, max_c); 1371 for (HBoundsCheck* other_bounds_check : candidates) { 1372 // Only replace if still in the graph. This avoids visiting the same 1373 // bounds check twice if it occurred multiple times in the use list. 1374 if (other_bounds_check->IsInBlock()) { 1375 ReplaceInstruction(other_bounds_check, other_bounds_check->InputAt(0)); 1376 } 1377 } 1378 } 1379 } 1380 } 1381 1382 /** 1383 * Returns true if static range analysis based on induction variables can determine the bounds 1384 * check on the given array range is always satisfied with the computed index range. The output 1385 * parameter try_dynamic_bce is set to false if OOB is certain. 1386 */ 1387 bool InductionRangeFitsIn(ValueRange* array_range, 1388 HBoundsCheck* context, 1389 bool* try_dynamic_bce) { 1390 InductionVarRange::Value v1; 1391 InductionVarRange::Value v2; 1392 bool needs_finite_test = false; 1393 HInstruction* index = context->InputAt(0); 1394 HInstruction* hint = HuntForDeclaration(context->InputAt(1)); 1395 if (induction_range_.GetInductionRange(context, index, hint, &v1, &v2, &needs_finite_test)) { 1396 if (v1.is_known && (v1.a_constant == 0 || v1.a_constant == 1) && 1397 v2.is_known && (v2.a_constant == 0 || v2.a_constant == 1)) { 1398 DCHECK(v1.a_constant == 1 || v1.instruction == nullptr); 1399 DCHECK(v2.a_constant == 1 || v2.instruction == nullptr); 1400 ValueRange index_range(&allocator_, 1401 ValueBound(v1.instruction, v1.b_constant), 1402 ValueBound(v2.instruction, v2.b_constant)); 1403 // If analysis reveals a certain OOB, disable dynamic BCE. Otherwise, 1404 // use analysis for static bce only if loop is finite. 1405 if (index_range.GetLower().LessThan(array_range->GetLower()) || 1406 index_range.GetUpper().GreaterThan(array_range->GetUpper())) { 1407 *try_dynamic_bce = false; 1408 } else if (!needs_finite_test && index_range.FitsIn(array_range)) { 1409 return true; 1410 } 1411 } 1412 } 1413 return false; 1414 } 1415 1416 /** 1417 * Performs loop-based dynamic elimination on a bounds check. In order to minimize the 1418 * number of eventually generated tests, related bounds checks with tests that can be 1419 * combined with tests for the given bounds check are collected first. 1420 */ 1421 void TransformLoopForDynamicBCE(HLoopInformation* loop, HBoundsCheck* bounds_check) { 1422 HInstruction* index = bounds_check->InputAt(0); 1423 HInstruction* array_length = bounds_check->InputAt(1); 1424 DCHECK(loop->IsDefinedOutOfTheLoop(array_length)); // pre-checked 1425 DCHECK(loop->DominatesAllBackEdges(bounds_check->GetBlock())); 1426 // Collect all bounds checks in the same loop that are related as "a[base + constant]" 1427 // for a base instruction (possibly absent) and various constants. 1428 ValueBound value = ValueBound::AsValueBound(index); 1429 HInstruction* base = value.GetInstruction(); 1430 int32_t min_c = base == nullptr ? 0 : value.GetConstant(); 1431 int32_t max_c = value.GetConstant(); 1432 ScopedArenaVector<HBoundsCheck*> candidates( 1433 allocator_.Adapter(kArenaAllocBoundsCheckElimination)); 1434 ScopedArenaVector<HBoundsCheck*> standby( 1435 allocator_.Adapter(kArenaAllocBoundsCheckElimination)); 1436 for (const HUseListNode<HInstruction*>& use : array_length->GetUses()) { 1437 HInstruction* user = use.GetUser(); 1438 if (user->IsBoundsCheck() && loop == user->GetBlock()->GetLoopInformation()) { 1439 HBoundsCheck* other_bounds_check = user->AsBoundsCheck(); 1440 HInstruction* other_index = other_bounds_check->InputAt(0); 1441 HInstruction* other_array_length = other_bounds_check->InputAt(1); 1442 ValueBound other_value = ValueBound::AsValueBound(other_index); 1443 int32_t other_c = other_value.GetConstant(); 1444 if (array_length == other_array_length && base == other_value.GetInstruction()) { 1445 // Ensure every candidate could be picked for code generation. 1446 bool b1 = false, b2 = false; 1447 if (!induction_range_.CanGenerateRange(other_bounds_check, other_index, &b1, &b2)) { 1448 continue; 1449 } 1450 // Does the current basic block dominate all back edges? If not, 1451 // add this candidate later only if it falls into the range. 1452 if (!loop->DominatesAllBackEdges(user->GetBlock())) { 1453 standby.push_back(other_bounds_check); 1454 continue; 1455 } 1456 min_c = std::min(min_c, other_c); 1457 max_c = std::max(max_c, other_c); 1458 candidates.push_back(other_bounds_check); 1459 } 1460 } 1461 } 1462 // Add standby candidates that fall in selected range. 1463 for (HBoundsCheck* other_bounds_check : standby) { 1464 HInstruction* other_index = other_bounds_check->InputAt(0); 1465 int32_t other_c = ValueBound::AsValueBound(other_index).GetConstant(); 1466 if (min_c <= other_c && other_c <= max_c) { 1467 candidates.push_back(other_bounds_check); 1468 } 1469 } 1470 // Perform loop-based deoptimization if it seems profitable, where we eliminate bounds 1471 // checks and replace these with deopt checks that guard against any possible OOB. 1472 DCHECK_LT(0u, candidates.size()); 1473 uint32_t distance = static_cast<uint32_t>(max_c) - static_cast<uint32_t>(min_c); 1474 if ((base != nullptr || min_c >= 0) && // reject certain OOB 1475 distance <= kMaxLengthForAddingDeoptimize) { // reject likely/certain deopt 1476 HBasicBlock* block = GetPreHeader(loop, bounds_check); 1477 HInstruction* min_lower = nullptr; 1478 HInstruction* min_upper = nullptr; 1479 HInstruction* max_lower = nullptr; 1480 HInstruction* max_upper = nullptr; 1481 // Iterate over all bounds checks. 1482 for (HBoundsCheck* other_bounds_check : candidates) { 1483 // Only handle if still in the graph. This avoids visiting the same 1484 // bounds check twice if it occurred multiple times in the use list. 1485 if (other_bounds_check->IsInBlock()) { 1486 HInstruction* other_index = other_bounds_check->InputAt(0); 1487 int32_t other_c = ValueBound::AsValueBound(other_index).GetConstant(); 1488 // Generate code for either the maximum or minimum. Range analysis already was queried 1489 // whether code generation on the original and, thus, related bounds check was possible. 1490 // It handles either loop invariants (lower is not set) or unit strides. 1491 if (other_c == max_c) { 1492 induction_range_.GenerateRange( 1493 other_bounds_check, other_index, GetGraph(), block, &max_lower, &max_upper); 1494 } else if (other_c == min_c && base != nullptr) { 1495 induction_range_.GenerateRange( 1496 other_bounds_check, other_index, GetGraph(), block, &min_lower, &min_upper); 1497 } 1498 ReplaceInstruction(other_bounds_check, other_index); 1499 } 1500 } 1501 // In code, using unsigned comparisons: 1502 // (1) constants only 1503 // if (max_upper >= a.length ) deoptimize; 1504 // (2) two symbolic invariants 1505 // if (min_upper > max_upper) deoptimize; unless min_c == max_c 1506 // if (max_upper >= a.length ) deoptimize; 1507 // (3) general case, unit strides (where lower would exceed upper for arithmetic wrap-around) 1508 // if (min_lower > max_lower) deoptimize; unless min_c == max_c 1509 // if (max_lower > max_upper) deoptimize; 1510 // if (max_upper >= a.length ) deoptimize; 1511 if (base == nullptr) { 1512 // Constants only. 1513 DCHECK_GE(min_c, 0); 1514 DCHECK(min_lower == nullptr && min_upper == nullptr && 1515 max_lower == nullptr && max_upper != nullptr); 1516 } else if (max_lower == nullptr) { 1517 // Two symbolic invariants. 1518 if (min_c != max_c) { 1519 DCHECK(min_lower == nullptr && min_upper != nullptr && 1520 max_lower == nullptr && max_upper != nullptr); 1521 InsertDeoptInLoop( 1522 loop, block, new (GetGraph()->GetAllocator()) HAbove(min_upper, max_upper)); 1523 } else { 1524 DCHECK(min_lower == nullptr && min_upper == nullptr && 1525 max_lower == nullptr && max_upper != nullptr); 1526 } 1527 } else { 1528 // General case, unit strides. 1529 if (min_c != max_c) { 1530 DCHECK(min_lower != nullptr && min_upper != nullptr && 1531 max_lower != nullptr && max_upper != nullptr); 1532 InsertDeoptInLoop( 1533 loop, block, new (GetGraph()->GetAllocator()) HAbove(min_lower, max_lower)); 1534 } else { 1535 DCHECK(min_lower == nullptr && min_upper == nullptr && 1536 max_lower != nullptr && max_upper != nullptr); 1537 } 1538 InsertDeoptInLoop( 1539 loop, block, new (GetGraph()->GetAllocator()) HAbove(max_lower, max_upper)); 1540 } 1541 InsertDeoptInLoop( 1542 loop, block, new (GetGraph()->GetAllocator()) HAboveOrEqual(max_upper, array_length)); 1543 } else { 1544 // TODO: if rejected, avoid doing this again for subsequent instructions in this set? 1545 } 1546 } 1547 1548 /** 1549 * Returns true if heuristics indicate that dynamic bce may be profitable. 1550 */ 1551 bool DynamicBCESeemsProfitable(HLoopInformation* loop, HBasicBlock* block) { 1552 if (loop != nullptr) { 1553 // The loop preheader of an irreducible loop does not dominate all the blocks in 1554 // the loop. We would need to find the common dominator of all blocks in the loop. 1555 if (loop->IsIrreducible()) { 1556 return false; 1557 } 1558 // We should never deoptimize from an osr method, otherwise we might wrongly optimize 1559 // code dominated by the deoptimization. 1560 if (GetGraph()->IsCompilingOsr()) { 1561 return false; 1562 } 1563 // A try boundary preheader is hard to handle. 1564 // TODO: remove this restriction. 1565 if (loop->GetPreHeader()->GetLastInstruction()->IsTryBoundary()) { 1566 return false; 1567 } 1568 // Does loop have early-exits? If so, the full range may not be covered by the loop 1569 // at runtime and testing the range may apply deoptimization unnecessarily. 1570 if (IsEarlyExitLoop(loop)) { 1571 return false; 1572 } 1573 // Does the current basic block dominate all back edges? If not, 1574 // don't apply dynamic bce to something that may not be executed. 1575 return loop->DominatesAllBackEdges(block); 1576 } 1577 return false; 1578 } 1579 1580 /** 1581 * Returns true if the loop has early exits, which implies it may not cover 1582 * the full range computed by range analysis based on induction variables. 1583 */ 1584 bool IsEarlyExitLoop(HLoopInformation* loop) { 1585 const uint32_t loop_id = loop->GetHeader()->GetBlockId(); 1586 // If loop has been analyzed earlier for early-exit, don't repeat the analysis. 1587 auto it = early_exit_loop_.find(loop_id); 1588 if (it != early_exit_loop_.end()) { 1589 return it->second; 1590 } 1591 // First time early-exit analysis for this loop. Since analysis requires scanning 1592 // the full loop-body, results of the analysis is stored for subsequent queries. 1593 HBlocksInLoopReversePostOrderIterator it_loop(*loop); 1594 for (it_loop.Advance(); !it_loop.Done(); it_loop.Advance()) { 1595 for (HBasicBlock* successor : it_loop.Current()->GetSuccessors()) { 1596 if (!loop->Contains(*successor)) { 1597 early_exit_loop_.Put(loop_id, true); 1598 return true; 1599 } 1600 } 1601 } 1602 early_exit_loop_.Put(loop_id, false); 1603 return false; 1604 } 1605 1606 /** 1607 * Returns true if the array length is already loop invariant, or can be made so 1608 * by handling the null check under the hood of the array length operation. 1609 */ 1610 bool CanHandleLength(HLoopInformation* loop, HInstruction* length, bool needs_taken_test) { 1611 if (loop->IsDefinedOutOfTheLoop(length)) { 1612 return true; 1613 } else if (length->IsArrayLength() && length->GetBlock()->GetLoopInformation() == loop) { 1614 if (CanHandleNullCheck(loop, length->InputAt(0), needs_taken_test)) { 1615 HoistToPreHeaderOrDeoptBlock(loop, length); 1616 return true; 1617 } 1618 } 1619 return false; 1620 } 1621 1622 /** 1623 * Returns true if the null check is already loop invariant, or can be made so 1624 * by generating a deoptimization test. 1625 */ 1626 bool CanHandleNullCheck(HLoopInformation* loop, HInstruction* check, bool needs_taken_test) { 1627 if (loop->IsDefinedOutOfTheLoop(check)) { 1628 return true; 1629 } else if (check->IsNullCheck() && check->GetBlock()->GetLoopInformation() == loop) { 1630 HInstruction* array = check->InputAt(0); 1631 if (loop->IsDefinedOutOfTheLoop(array)) { 1632 // Generate: if (array == null) deoptimize; 1633 TransformLoopForDeoptimizationIfNeeded(loop, needs_taken_test); 1634 HBasicBlock* block = GetPreHeader(loop, check); 1635 HInstruction* cond = 1636 new (GetGraph()->GetAllocator()) HEqual(array, GetGraph()->GetNullConstant()); 1637 InsertDeoptInLoop(loop, block, cond, /* is_null_check */ true); 1638 ReplaceInstruction(check, array); 1639 return true; 1640 } 1641 } 1642 return false; 1643 } 1644 1645 /** 1646 * Returns true if compiler can apply dynamic bce to loops that may be infinite 1647 * (e.g. for (int i = 0; i <= U; i++) with U = MAX_INT), which would invalidate 1648 * the range analysis evaluation code by "overshooting" the computed range. 1649 * Since deoptimization would be a bad choice, and there is no other version 1650 * of the loop to use, dynamic bce in such cases is only allowed if other tests 1651 * ensure the loop is finite. 1652 */ 1653 bool CanHandleInfiniteLoop(HLoopInformation* loop, HInstruction* index, bool needs_infinite_test) { 1654 if (needs_infinite_test) { 1655 // If we already forced the loop to be finite, allow directly. 1656 const uint32_t loop_id = loop->GetHeader()->GetBlockId(); 1657 if (finite_loop_.find(loop_id) != finite_loop_.end()) { 1658 return true; 1659 } 1660 // Otherwise, allow dynamic bce if the index (which is necessarily an induction at 1661 // this point) is the direct loop index (viz. a[i]), since then the runtime tests 1662 // ensure upper bound cannot cause an infinite loop. 1663 HInstruction* control = loop->GetHeader()->GetLastInstruction(); 1664 if (control->IsIf()) { 1665 HInstruction* if_expr = control->AsIf()->InputAt(0); 1666 if (if_expr->IsCondition()) { 1667 HCondition* condition = if_expr->AsCondition(); 1668 if (index == condition->InputAt(0) || 1669 index == condition->InputAt(1)) { 1670 finite_loop_.insert(loop_id); 1671 return true; 1672 } 1673 } 1674 } 1675 return false; 1676 } 1677 return true; 1678 } 1679 1680 /** 1681 * Returns appropriate preheader for the loop, depending on whether the 1682 * instruction appears in the loop header or proper loop-body. 1683 */ 1684 HBasicBlock* GetPreHeader(HLoopInformation* loop, HInstruction* instruction) { 1685 // Use preheader unless there is an earlier generated deoptimization block since 1686 // hoisted expressions may depend on and/or used by the deoptimization tests. 1687 HBasicBlock* header = loop->GetHeader(); 1688 const uint32_t loop_id = header->GetBlockId(); 1689 auto it = taken_test_loop_.find(loop_id); 1690 if (it != taken_test_loop_.end()) { 1691 HBasicBlock* block = it->second; 1692 // If always taken, keep it that way by returning the original preheader, 1693 // which can be found by following the predecessor of the true-block twice. 1694 if (instruction->GetBlock() == header) { 1695 return block->GetSinglePredecessor()->GetSinglePredecessor(); 1696 } 1697 return block; 1698 } 1699 return loop->GetPreHeader(); 1700 } 1701 1702 /** Inserts a deoptimization test in a loop preheader. */ 1703 void InsertDeoptInLoop(HLoopInformation* loop, 1704 HBasicBlock* block, 1705 HInstruction* condition, 1706 bool is_null_check = false) { 1707 HInstruction* suspend = loop->GetSuspendCheck(); 1708 block->InsertInstructionBefore(condition, block->GetLastInstruction()); 1709 DeoptimizationKind kind = 1710 is_null_check ? DeoptimizationKind::kLoopNullBCE : DeoptimizationKind::kLoopBoundsBCE; 1711 HDeoptimize* deoptimize = new (GetGraph()->GetAllocator()) HDeoptimize( 1712 GetGraph()->GetAllocator(), condition, kind, suspend->GetDexPc()); 1713 block->InsertInstructionBefore(deoptimize, block->GetLastInstruction()); 1714 if (suspend->HasEnvironment()) { 1715 deoptimize->CopyEnvironmentFromWithLoopPhiAdjustment( 1716 suspend->GetEnvironment(), loop->GetHeader()); 1717 } 1718 } 1719 1720 /** Inserts a deoptimization test right before a bounds check. */ 1721 void InsertDeoptInBlock(HBoundsCheck* bounds_check, HInstruction* condition) { 1722 HBasicBlock* block = bounds_check->GetBlock(); 1723 block->InsertInstructionBefore(condition, bounds_check); 1724 HDeoptimize* deoptimize = new (GetGraph()->GetAllocator()) HDeoptimize( 1725 GetGraph()->GetAllocator(), 1726 condition, 1727 DeoptimizationKind::kBlockBCE, 1728 bounds_check->GetDexPc()); 1729 block->InsertInstructionBefore(deoptimize, bounds_check); 1730 deoptimize->CopyEnvironmentFrom(bounds_check->GetEnvironment()); 1731 } 1732 1733 /** Hoists instruction out of the loop to preheader or deoptimization block. */ 1734 void HoistToPreHeaderOrDeoptBlock(HLoopInformation* loop, HInstruction* instruction) { 1735 HBasicBlock* block = GetPreHeader(loop, instruction); 1736 DCHECK(!instruction->HasEnvironment()); 1737 instruction->MoveBefore(block->GetLastInstruction()); 1738 } 1739 1740 /** 1741 * Adds a new taken-test structure to a loop if needed and not already done. 1742 * The taken-test protects range analysis evaluation code to avoid any 1743 * deoptimization caused by incorrect trip-count evaluation in non-taken loops. 1744 * 1745 * old_preheader 1746 * | 1747 * if_block <- taken-test protects deoptimization block 1748 * / \ 1749 * true_block false_block <- deoptimizations/invariants are placed in true_block 1750 * \ / 1751 * new_preheader <- may require phi nodes to preserve SSA structure 1752 * | 1753 * header 1754 * 1755 * For example, this loop: 1756 * 1757 * for (int i = lower; i < upper; i++) { 1758 * array[i] = 0; 1759 * } 1760 * 1761 * will be transformed to: 1762 * 1763 * if (lower < upper) { 1764 * if (array == null) deoptimize; 1765 * array_length = array.length; 1766 * if (lower > upper) deoptimize; // unsigned 1767 * if (upper >= array_length) deoptimize; // unsigned 1768 * } else { 1769 * array_length = 0; 1770 * } 1771 * for (int i = lower; i < upper; i++) { 1772 * // Loop without null check and bounds check, and any array.length replaced with array_length. 1773 * array[i] = 0; 1774 * } 1775 */ 1776 void TransformLoopForDeoptimizationIfNeeded(HLoopInformation* loop, bool needs_taken_test) { 1777 // Not needed (can use preheader) or already done (can reuse)? 1778 const uint32_t loop_id = loop->GetHeader()->GetBlockId(); 1779 if (!needs_taken_test || taken_test_loop_.find(loop_id) != taken_test_loop_.end()) { 1780 return; 1781 } 1782 1783 // Generate top test structure. 1784 HBasicBlock* header = loop->GetHeader(); 1785 GetGraph()->TransformLoopHeaderForBCE(header); 1786 HBasicBlock* new_preheader = loop->GetPreHeader(); 1787 HBasicBlock* if_block = new_preheader->GetDominator(); 1788 HBasicBlock* true_block = if_block->GetSuccessors()[0]; // True successor. 1789 HBasicBlock* false_block = if_block->GetSuccessors()[1]; // False successor. 1790 1791 // Goto instructions. 1792 true_block->AddInstruction(new (GetGraph()->GetAllocator()) HGoto()); 1793 false_block->AddInstruction(new (GetGraph()->GetAllocator()) HGoto()); 1794 new_preheader->AddInstruction(new (GetGraph()->GetAllocator()) HGoto()); 1795 1796 // Insert the taken-test to see if the loop body is entered. If the 1797 // loop isn't entered at all, it jumps around the deoptimization block. 1798 if_block->AddInstruction(new (GetGraph()->GetAllocator()) HGoto()); // placeholder 1799 HInstruction* condition = induction_range_.GenerateTakenTest( 1800 header->GetLastInstruction(), GetGraph(), if_block); 1801 DCHECK(condition != nullptr); 1802 if_block->RemoveInstruction(if_block->GetLastInstruction()); 1803 if_block->AddInstruction(new (GetGraph()->GetAllocator()) HIf(condition)); 1804 1805 taken_test_loop_.Put(loop_id, true_block); 1806 } 1807 1808 /** 1809 * Inserts phi nodes that preserve SSA structure in generated top test structures. 1810 * All uses of instructions in the deoptimization block that reach the loop need 1811 * a phi node in the new loop preheader to fix the dominance relation. 1812 * 1813 * Example: 1814 * if_block 1815 * / \ 1816 * x_0 = .. false_block 1817 * \ / 1818 * x_1 = phi(x_0, null) <- synthetic phi 1819 * | 1820 * new_preheader 1821 */ 1822 void InsertPhiNodes() { 1823 // Scan all new deoptimization blocks. 1824 for (const auto& entry : taken_test_loop_) { 1825 HBasicBlock* true_block = entry.second; 1826 HBasicBlock* new_preheader = true_block->GetSingleSuccessor(); 1827 // Scan all instructions in a new deoptimization block. 1828 for (HInstructionIterator it(true_block->GetInstructions()); !it.Done(); it.Advance()) { 1829 HInstruction* instruction = it.Current(); 1830 DataType::Type type = instruction->GetType(); 1831 HPhi* phi = nullptr; 1832 // Scan all uses of an instruction and replace each later use with a phi node. 1833 const HUseList<HInstruction*>& uses = instruction->GetUses(); 1834 for (auto it2 = uses.begin(), end2 = uses.end(); it2 != end2; /* ++it2 below */) { 1835 HInstruction* user = it2->GetUser(); 1836 size_t index = it2->GetIndex(); 1837 // Increment `it2` now because `*it2` may disappear thanks to user->ReplaceInput(). 1838 ++it2; 1839 if (user->GetBlock() != true_block) { 1840 if (phi == nullptr) { 1841 phi = NewPhi(new_preheader, instruction, type); 1842 } 1843 user->ReplaceInput(phi, index); // Removes the use node from the list. 1844 induction_range_.Replace(user, instruction, phi); // update induction 1845 } 1846 } 1847 // Scan all environment uses of an instruction and replace each later use with a phi node. 1848 const HUseList<HEnvironment*>& env_uses = instruction->GetEnvUses(); 1849 for (auto it2 = env_uses.begin(), end2 = env_uses.end(); it2 != end2; /* ++it2 below */) { 1850 HEnvironment* user = it2->GetUser(); 1851 size_t index = it2->GetIndex(); 1852 // Increment `it2` now because `*it2` may disappear thanks to user->RemoveAsUserOfInput(). 1853 ++it2; 1854 if (user->GetHolder()->GetBlock() != true_block) { 1855 if (phi == nullptr) { 1856 phi = NewPhi(new_preheader, instruction, type); 1857 } 1858 user->RemoveAsUserOfInput(index); 1859 user->SetRawEnvAt(index, phi); 1860 phi->AddEnvUseAt(user, index); 1861 } 1862 } 1863 } 1864 } 1865 } 1866 1867 /** 1868 * Construct a phi(instruction, 0) in the new preheader to fix the dominance relation. 1869 * These are synthetic phi nodes without a virtual register. 1870 */ 1871 HPhi* NewPhi(HBasicBlock* new_preheader, 1872 HInstruction* instruction, 1873 DataType::Type type) { 1874 HGraph* graph = GetGraph(); 1875 HInstruction* zero; 1876 switch (type) { 1877 case DataType::Type::kReference: zero = graph->GetNullConstant(); break; 1878 case DataType::Type::kFloat32: zero = graph->GetFloatConstant(0); break; 1879 case DataType::Type::kFloat64: zero = graph->GetDoubleConstant(0); break; 1880 default: zero = graph->GetConstant(type, 0); break; 1881 } 1882 HPhi* phi = new (graph->GetAllocator()) 1883 HPhi(graph->GetAllocator(), kNoRegNumber, /*number_of_inputs*/ 2, HPhi::ToPhiType(type)); 1884 phi->SetRawInputAt(0, instruction); 1885 phi->SetRawInputAt(1, zero); 1886 if (type == DataType::Type::kReference) { 1887 phi->SetReferenceTypeInfo(instruction->GetReferenceTypeInfo()); 1888 } 1889 new_preheader->AddPhi(phi); 1890 return phi; 1891 } 1892 1893 /** Helper method to replace an instruction with another instruction. */ 1894 void ReplaceInstruction(HInstruction* instruction, HInstruction* replacement) { 1895 // Safe iteration. 1896 if (instruction == next_) { 1897 next_ = next_->GetNext(); 1898 } 1899 // Replace and remove. 1900 instruction->ReplaceWith(replacement); 1901 instruction->GetBlock()->RemoveInstruction(instruction); 1902 } 1903 1904 // Use local allocator for allocating memory. 1905 ScopedArenaAllocator allocator_; 1906 1907 // A set of maps, one per basic block, from instruction to range. 1908 ScopedArenaVector<ScopedArenaSafeMap<int, ValueRange*>> maps_; 1909 1910 // Map an HArrayLength instruction's id to the first HBoundsCheck instruction 1911 // in a block that checks an index against that HArrayLength. 1912 ScopedArenaSafeMap<int, HBoundsCheck*> first_index_bounds_check_map_; 1913 1914 // Early-exit loop bookkeeping. 1915 ScopedArenaSafeMap<uint32_t, bool> early_exit_loop_; 1916 1917 // Taken-test loop bookkeeping. 1918 ScopedArenaSafeMap<uint32_t, HBasicBlock*> taken_test_loop_; 1919 1920 // Finite loop bookkeeping. 1921 ScopedArenaSet<uint32_t> finite_loop_; 1922 1923 // Flag that denotes whether dominator-based dynamic elimination has occurred. 1924 bool has_dom_based_dynamic_bce_; 1925 1926 // Initial number of blocks. 1927 uint32_t initial_block_size_; 1928 1929 // Side effects. 1930 const SideEffectsAnalysis& side_effects_; 1931 1932 // Range analysis based on induction variables. 1933 InductionVarRange induction_range_; 1934 1935 // Safe iteration. 1936 HInstruction* next_; 1937 1938 DISALLOW_COPY_AND_ASSIGN(BCEVisitor); 1939 }; 1940 1941 void BoundsCheckElimination::Run() { 1942 if (!graph_->HasBoundsChecks()) { 1943 return; 1944 } 1945 1946 // Reverse post order guarantees a node's dominators are visited first. 1947 // We want to visit in the dominator-based order since if a value is known to 1948 // be bounded by a range at one instruction, it must be true that all uses of 1949 // that value dominated by that instruction fits in that range. Range of that 1950 // value can be narrowed further down in the dominator tree. 1951 BCEVisitor visitor(graph_, side_effects_, induction_analysis_); 1952 for (size_t i = 0, size = graph_->GetReversePostOrder().size(); i != size; ++i) { 1953 HBasicBlock* current = graph_->GetReversePostOrder()[i]; 1954 if (visitor.IsAddedBlock(current)) { 1955 // Skip added blocks. Their effects are already taken care of. 1956 continue; 1957 } 1958 visitor.VisitBasicBlock(current); 1959 // Skip forward to the current block in case new basic blocks were inserted 1960 // (which always appear earlier in reverse post order) to avoid visiting the 1961 // same basic block twice. 1962 size_t new_size = graph_->GetReversePostOrder().size(); 1963 DCHECK_GE(new_size, size); 1964 i += new_size - size; 1965 DCHECK_EQ(current, graph_->GetReversePostOrder()[i]); 1966 size = new_size; 1967 } 1968 1969 // Perform cleanup. 1970 visitor.Finish(); 1971 } 1972 1973 } // namespace art 1974