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