bounds_check_elimination.cc revision 9d750efd66ae7f4b790af3c1ff8de972bbe826d9
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 "base/arena_containers.h" 18#include "bounds_check_elimination.h" 19#include "nodes.h" 20 21namespace art { 22 23class MonotonicValueRange; 24 25/** 26 * A value bound is represented as a pair of value and constant, 27 * e.g. array.length - 1. 28 */ 29class ValueBound : public ValueObject { 30 public: 31 ValueBound(HInstruction* instruction, int32_t constant) { 32 if (instruction != nullptr && instruction->IsIntConstant()) { 33 // Normalize ValueBound with constant instruction. 34 int32_t instr_const = instruction->AsIntConstant()->GetValue(); 35 if (!WouldAddOverflowOrUnderflow(instr_const, constant)) { 36 instruction_ = nullptr; 37 constant_ = instr_const + constant; 38 return; 39 } 40 } 41 instruction_ = instruction; 42 constant_ = constant; 43 } 44 45 // Return whether (left + right) overflows or underflows. 46 static bool WouldAddOverflowOrUnderflow(int32_t left, int32_t right) { 47 if (right == 0) { 48 return false; 49 } 50 if ((right > 0) && (left <= INT_MAX - right)) { 51 // No overflow. 52 return false; 53 } 54 if ((right < 0) && (left >= INT_MIN - right)) { 55 // No underflow. 56 return false; 57 } 58 return true; 59 } 60 61 static bool IsAddOrSubAConstant(HInstruction* instruction, 62 HInstruction** left_instruction, 63 int* right_constant) { 64 if (instruction->IsAdd() || instruction->IsSub()) { 65 HBinaryOperation* bin_op = instruction->AsBinaryOperation(); 66 HInstruction* left = bin_op->GetLeft(); 67 HInstruction* right = bin_op->GetRight(); 68 if (right->IsIntConstant()) { 69 *left_instruction = left; 70 int32_t c = right->AsIntConstant()->GetValue(); 71 *right_constant = instruction->IsAdd() ? c : -c; 72 return true; 73 } 74 } 75 *left_instruction = nullptr; 76 *right_constant = 0; 77 return false; 78 } 79 80 // Try to detect useful value bound format from an instruction, e.g. 81 // a constant or array length related value. 82 static ValueBound DetectValueBoundFromValue(HInstruction* instruction, bool* found) { 83 DCHECK(instruction != nullptr); 84 if (instruction->IsIntConstant()) { 85 *found = true; 86 return ValueBound(nullptr, instruction->AsIntConstant()->GetValue()); 87 } 88 89 if (instruction->IsArrayLength()) { 90 *found = true; 91 return ValueBound(instruction, 0); 92 } 93 // Try to detect (array.length + c) format. 94 HInstruction *left; 95 int32_t right; 96 if (IsAddOrSubAConstant(instruction, &left, &right)) { 97 if (left->IsArrayLength()) { 98 *found = true; 99 return ValueBound(left, right); 100 } 101 } 102 103 // No useful bound detected. 104 *found = false; 105 return ValueBound::Max(); 106 } 107 108 HInstruction* GetInstruction() const { return instruction_; } 109 int32_t GetConstant() const { return constant_; } 110 111 bool IsRelatedToArrayLength() const { 112 // Some bounds are created with HNewArray* as the instruction instead 113 // of HArrayLength*. They are treated the same. 114 return (instruction_ != nullptr) && 115 (instruction_->IsArrayLength() || instruction_->IsNewArray()); 116 } 117 118 bool IsConstant() const { 119 return instruction_ == nullptr; 120 } 121 122 static ValueBound Min() { return ValueBound(nullptr, INT_MIN); } 123 static ValueBound Max() { return ValueBound(nullptr, INT_MAX); } 124 125 bool Equals(ValueBound bound) const { 126 return instruction_ == bound.instruction_ && constant_ == bound.constant_; 127 } 128 129 static HInstruction* FromArrayLengthToNewArrayIfPossible(HInstruction* instruction) { 130 // Null check on the NewArray should have been eliminated by instruction 131 // simplifier already. 132 if (instruction->IsArrayLength() && instruction->InputAt(0)->IsNewArray()) { 133 return instruction->InputAt(0)->AsNewArray(); 134 } 135 return instruction; 136 } 137 138 static bool Equal(HInstruction* instruction1, HInstruction* instruction2) { 139 if (instruction1 == instruction2) { 140 return true; 141 } 142 143 if (instruction1 == nullptr || instruction2 == nullptr) { 144 return false; 145 } 146 147 // Some bounds are created with HNewArray* as the instruction instead 148 // of HArrayLength*. They are treated the same. 149 instruction1 = FromArrayLengthToNewArrayIfPossible(instruction1); 150 instruction2 = FromArrayLengthToNewArrayIfPossible(instruction2); 151 return instruction1 == instruction2; 152 } 153 154 // Returns if it's certain this->bound >= `bound`. 155 bool GreaterThanOrEqualTo(ValueBound bound) const { 156 if (Equal(instruction_, bound.instruction_)) { 157 return constant_ >= bound.constant_; 158 } 159 // Not comparable. Just return false. 160 return false; 161 } 162 163 // Returns if it's certain this->bound <= `bound`. 164 bool LessThanOrEqualTo(ValueBound bound) const { 165 if (Equal(instruction_, bound.instruction_)) { 166 return constant_ <= bound.constant_; 167 } 168 // Not comparable. Just return false. 169 return false; 170 } 171 172 // Try to narrow lower bound. Returns the greatest of the two if possible. 173 // Pick one if they are not comparable. 174 static ValueBound NarrowLowerBound(ValueBound bound1, ValueBound bound2) { 175 if (bound1.GreaterThanOrEqualTo(bound2)) { 176 return bound1; 177 } 178 if (bound2.GreaterThanOrEqualTo(bound1)) { 179 return bound2; 180 } 181 182 // Not comparable. Just pick one. We may lose some info, but that's ok. 183 // Favor constant as lower bound. 184 return bound1.IsConstant() ? bound1 : bound2; 185 } 186 187 // Try to narrow upper bound. Returns the lowest of the two if possible. 188 // Pick one if they are not comparable. 189 static ValueBound NarrowUpperBound(ValueBound bound1, ValueBound bound2) { 190 if (bound1.LessThanOrEqualTo(bound2)) { 191 return bound1; 192 } 193 if (bound2.LessThanOrEqualTo(bound1)) { 194 return bound2; 195 } 196 197 // Not comparable. Just pick one. We may lose some info, but that's ok. 198 // Favor array length as upper bound. 199 return bound1.IsRelatedToArrayLength() ? bound1 : bound2; 200 } 201 202 // Add a constant to a ValueBound. 203 // `overflow` or `underflow` will return whether the resulting bound may 204 // overflow or underflow an int. 205 ValueBound Add(int32_t c, bool* overflow, bool* underflow) const { 206 *overflow = *underflow = false; 207 if (c == 0) { 208 return *this; 209 } 210 211 int32_t new_constant; 212 if (c > 0) { 213 if (constant_ > INT_MAX - c) { 214 *overflow = true; 215 return Max(); 216 } 217 218 new_constant = constant_ + c; 219 // (array.length + non-positive-constant) won't overflow an int. 220 if (IsConstant() || (IsRelatedToArrayLength() && new_constant <= 0)) { 221 return ValueBound(instruction_, new_constant); 222 } 223 // Be conservative. 224 *overflow = true; 225 return Max(); 226 } else { 227 if (constant_ < INT_MIN - c) { 228 *underflow = true; 229 return Min(); 230 } 231 232 new_constant = constant_ + c; 233 // Regardless of the value new_constant, (array.length+new_constant) will 234 // never underflow since array.length is no less than 0. 235 if (IsConstant() || IsRelatedToArrayLength()) { 236 return ValueBound(instruction_, new_constant); 237 } 238 // Be conservative. 239 *underflow = true; 240 return Min(); 241 } 242 } 243 244 private: 245 HInstruction* instruction_; 246 int32_t constant_; 247}; 248 249// Collect array access data for a loop. 250// TODO: make it work for multiple arrays inside the loop. 251class ArrayAccessInsideLoopFinder : public ValueObject { 252 public: 253 explicit ArrayAccessInsideLoopFinder(HInstruction* induction_variable) 254 : induction_variable_(induction_variable), 255 found_array_length_(nullptr), 256 offset_low_(INT_MAX), 257 offset_high_(INT_MIN) { 258 Run(); 259 } 260 261 HArrayLength* GetFoundArrayLength() const { return found_array_length_; } 262 bool HasFoundArrayLength() const { return found_array_length_ != nullptr; } 263 int32_t GetOffsetLow() const { return offset_low_; } 264 int32_t GetOffsetHigh() const { return offset_high_; } 265 266 // Returns if `block` that is in loop_info may exit the loop, unless it's 267 // the loop header for loop_info. 268 static bool EarlyExit(HBasicBlock* block, HLoopInformation* loop_info) { 269 DCHECK(loop_info->Contains(*block)); 270 if (block == loop_info->GetHeader()) { 271 // Loop header of loop_info. Exiting loop is normal. 272 return false; 273 } 274 const GrowableArray<HBasicBlock*> successors = block->GetSuccessors(); 275 for (size_t i = 0; i < successors.Size(); i++) { 276 if (!loop_info->Contains(*successors.Get(i))) { 277 // One of the successors exits the loop. 278 return true; 279 } 280 } 281 return false; 282 } 283 284 void Run() { 285 HLoopInformation* loop_info = induction_variable_->GetBlock()->GetLoopInformation(); 286 // Must be simplified loop. 287 DCHECK_EQ(loop_info->GetBackEdges().Size(), 1U); 288 for (HBlocksInLoopIterator it_loop(*loop_info); !it_loop.Done(); it_loop.Advance()) { 289 HBasicBlock* block = it_loop.Current(); 290 DCHECK(block->IsInLoop()); 291 HBasicBlock* back_edge = loop_info->GetBackEdges().Get(0); 292 if (!block->Dominates(back_edge)) { 293 // In order not to trigger deoptimization unnecessarily, make sure 294 // that all array accesses collected are really executed in the loop. 295 // For array accesses in a branch inside the loop, don't collect the 296 // access. The bounds check in that branch might not be eliminated. 297 continue; 298 } 299 if (EarlyExit(block, loop_info)) { 300 // If the loop body can exit loop (like break, return, etc.), it's not guaranteed 301 // that the loop will loop through the full monotonic value range from 302 // initial_ to end_. So adding deoptimization might be too aggressive and can 303 // trigger deoptimization unnecessarily even if the loop won't actually throw 304 // AIOOBE. Otherwise, the loop induction variable is going to cover the full 305 // monotonic value range from initial_ to end_, and deoptimizations are added 306 // iff the loop will throw AIOOBE. 307 found_array_length_ = nullptr; 308 return; 309 } 310 for (HInstruction* instruction = block->GetFirstInstruction(); 311 instruction != nullptr; 312 instruction = instruction->GetNext()) { 313 if (!instruction->IsArrayGet() && !instruction->IsArraySet()) { 314 continue; 315 } 316 HInstruction* index = instruction->InputAt(1); 317 if (!index->IsBoundsCheck()) { 318 continue; 319 } 320 321 HArrayLength* array_length = index->InputAt(1)->AsArrayLength(); 322 if (array_length == nullptr) { 323 DCHECK(index->InputAt(1)->IsIntConstant()); 324 // TODO: may optimize for constant case. 325 continue; 326 } 327 328 HInstruction* array = array_length->InputAt(0); 329 if (array->IsNullCheck()) { 330 array = array->AsNullCheck()->InputAt(0); 331 } 332 if (loop_info->Contains(*array->GetBlock())) { 333 // Array is defined inside the loop. Skip. 334 continue; 335 } 336 337 if (found_array_length_ != nullptr && found_array_length_ != array_length) { 338 // There is already access for another array recorded for the loop. 339 // TODO: handle multiple arrays. 340 continue; 341 } 342 343 index = index->AsBoundsCheck()->InputAt(0); 344 HInstruction* left = index; 345 int32_t right = 0; 346 if (left == induction_variable_ || 347 (ValueBound::IsAddOrSubAConstant(index, &left, &right) && 348 left == induction_variable_)) { 349 // For patterns like array[i] or array[i + 2]. 350 if (right < offset_low_) { 351 offset_low_ = right; 352 } 353 if (right > offset_high_) { 354 offset_high_ = right; 355 } 356 } else { 357 // Access not in induction_variable/(induction_variable_ + constant) 358 // format. Skip. 359 continue; 360 } 361 // Record this array. 362 found_array_length_ = array_length; 363 } 364 } 365 } 366 367 private: 368 // The instruction that corresponds to a MonotonicValueRange. 369 HInstruction* induction_variable_; 370 371 // The array length of the array that's accessed inside the loop. 372 HArrayLength* found_array_length_; 373 374 // The lowest and highest constant offsets relative to induction variable 375 // instruction_ in all array accesses. 376 // If array access are: array[i-1], array[i], array[i+1], 377 // offset_low_ is -1 and offset_high is 1. 378 int32_t offset_low_; 379 int32_t offset_high_; 380 381 DISALLOW_COPY_AND_ASSIGN(ArrayAccessInsideLoopFinder); 382}; 383 384/** 385 * Represent a range of lower bound and upper bound, both being inclusive. 386 * Currently a ValueRange may be generated as a result of the following: 387 * comparisons related to array bounds, array bounds check, add/sub on top 388 * of an existing value range, NewArray or a loop phi corresponding to an 389 * incrementing/decrementing array index (MonotonicValueRange). 390 */ 391class ValueRange : public ArenaObject<kArenaAllocMisc> { 392 public: 393 ValueRange(ArenaAllocator* allocator, ValueBound lower, ValueBound upper) 394 : allocator_(allocator), lower_(lower), upper_(upper) {} 395 396 virtual ~ValueRange() {} 397 398 virtual MonotonicValueRange* AsMonotonicValueRange() { return nullptr; } 399 bool IsMonotonicValueRange() { 400 return AsMonotonicValueRange() != nullptr; 401 } 402 403 ArenaAllocator* GetAllocator() const { return allocator_; } 404 ValueBound GetLower() const { return lower_; } 405 ValueBound GetUpper() const { return upper_; } 406 407 // If it's certain that this value range fits in other_range. 408 virtual bool FitsIn(ValueRange* other_range) const { 409 if (other_range == nullptr) { 410 return true; 411 } 412 DCHECK(!other_range->IsMonotonicValueRange()); 413 return lower_.GreaterThanOrEqualTo(other_range->lower_) && 414 upper_.LessThanOrEqualTo(other_range->upper_); 415 } 416 417 // Returns the intersection of this and range. 418 // If it's not possible to do intersection because some 419 // bounds are not comparable, it's ok to pick either bound. 420 virtual ValueRange* Narrow(ValueRange* range) { 421 if (range == nullptr) { 422 return this; 423 } 424 425 if (range->IsMonotonicValueRange()) { 426 return this; 427 } 428 429 return new (allocator_) ValueRange( 430 allocator_, 431 ValueBound::NarrowLowerBound(lower_, range->lower_), 432 ValueBound::NarrowUpperBound(upper_, range->upper_)); 433 } 434 435 // Shift a range by a constant. 436 ValueRange* Add(int32_t constant) const { 437 bool overflow, underflow; 438 ValueBound lower = lower_.Add(constant, &overflow, &underflow); 439 if (underflow) { 440 // Lower bound underflow will wrap around to positive values 441 // and invalidate the upper bound. 442 return nullptr; 443 } 444 ValueBound upper = upper_.Add(constant, &overflow, &underflow); 445 if (overflow) { 446 // Upper bound overflow will wrap around to negative values 447 // and invalidate the lower bound. 448 return nullptr; 449 } 450 return new (allocator_) ValueRange(allocator_, lower, upper); 451 } 452 453 private: 454 ArenaAllocator* const allocator_; 455 const ValueBound lower_; // inclusive 456 const ValueBound upper_; // inclusive 457 458 DISALLOW_COPY_AND_ASSIGN(ValueRange); 459}; 460 461/** 462 * A monotonically incrementing/decrementing value range, e.g. 463 * the variable i in "for (int i=0; i<array.length; i++)". 464 * Special care needs to be taken to account for overflow/underflow 465 * of such value ranges. 466 */ 467class MonotonicValueRange : public ValueRange { 468 public: 469 MonotonicValueRange(ArenaAllocator* allocator, 470 HPhi* induction_variable, 471 HInstruction* initial, 472 int32_t increment, 473 ValueBound bound) 474 // To be conservative, give it full range [INT_MIN, INT_MAX] in case it's 475 // used as a regular value range, due to possible overflow/underflow. 476 : ValueRange(allocator, ValueBound::Min(), ValueBound::Max()), 477 induction_variable_(induction_variable), 478 initial_(initial), 479 end_(nullptr), 480 inclusive_(false), 481 increment_(increment), 482 bound_(bound) {} 483 484 virtual ~MonotonicValueRange() {} 485 486 HInstruction* GetInductionVariable() const { return induction_variable_; } 487 int32_t GetIncrement() const { return increment_; } 488 ValueBound GetBound() const { return bound_; } 489 void SetEnd(HInstruction* end) { end_ = end; } 490 void SetInclusive(bool inclusive) { inclusive_ = inclusive; } 491 HBasicBlock* GetLoopHead() const { 492 DCHECK(induction_variable_->GetBlock()->IsLoopHeader()); 493 return induction_variable_->GetBlock(); 494 } 495 496 MonotonicValueRange* AsMonotonicValueRange() OVERRIDE { return this; } 497 498 // If it's certain that this value range fits in other_range. 499 bool FitsIn(ValueRange* other_range) const OVERRIDE { 500 if (other_range == nullptr) { 501 return true; 502 } 503 DCHECK(!other_range->IsMonotonicValueRange()); 504 return false; 505 } 506 507 // Try to narrow this MonotonicValueRange given another range. 508 // Ideally it will return a normal ValueRange. But due to 509 // possible overflow/underflow, that may not be possible. 510 ValueRange* Narrow(ValueRange* range) OVERRIDE { 511 if (range == nullptr) { 512 return this; 513 } 514 DCHECK(!range->IsMonotonicValueRange()); 515 516 if (increment_ > 0) { 517 // Monotonically increasing. 518 ValueBound lower = ValueBound::NarrowLowerBound(bound_, range->GetLower()); 519 if (!lower.IsConstant() || lower.GetConstant() == INT_MIN) { 520 // Lower bound isn't useful. Leave it to deoptimization. 521 return this; 522 } 523 524 // We currently conservatively assume max array length is INT_MAX. If we can 525 // make assumptions about the max array length, e.g. due to the max heap size, 526 // divided by the element size (such as 4 bytes for each integer array), we can 527 // lower this number and rule out some possible overflows. 528 int32_t max_array_len = INT_MAX; 529 530 // max possible integer value of range's upper value. 531 int32_t upper = INT_MAX; 532 // Try to lower upper. 533 ValueBound upper_bound = range->GetUpper(); 534 if (upper_bound.IsConstant()) { 535 upper = upper_bound.GetConstant(); 536 } else if (upper_bound.IsRelatedToArrayLength() && upper_bound.GetConstant() <= 0) { 537 // Normal case. e.g. <= array.length - 1. 538 upper = max_array_len + upper_bound.GetConstant(); 539 } 540 541 // If we can prove for the last number in sequence of initial_, 542 // initial_ + increment_, initial_ + 2 x increment_, ... 543 // that's <= upper, (last_num_in_sequence + increment_) doesn't trigger overflow, 544 // then this MonoticValueRange is narrowed to a normal value range. 545 546 // Be conservative first, assume last number in the sequence hits upper. 547 int32_t last_num_in_sequence = upper; 548 if (initial_->IsIntConstant()) { 549 int32_t initial_constant = initial_->AsIntConstant()->GetValue(); 550 if (upper <= initial_constant) { 551 last_num_in_sequence = upper; 552 } else { 553 // Cast to int64_t for the substraction part to avoid int32_t overflow. 554 last_num_in_sequence = initial_constant + 555 ((int64_t)upper - (int64_t)initial_constant) / increment_ * increment_; 556 } 557 } 558 if (last_num_in_sequence <= INT_MAX - increment_) { 559 // No overflow. The sequence will be stopped by the upper bound test as expected. 560 return new (GetAllocator()) ValueRange(GetAllocator(), lower, range->GetUpper()); 561 } 562 563 // There might be overflow. Give up narrowing. 564 return this; 565 } else { 566 DCHECK_NE(increment_, 0); 567 // Monotonically decreasing. 568 ValueBound upper = ValueBound::NarrowUpperBound(bound_, range->GetUpper()); 569 if ((!upper.IsConstant() || upper.GetConstant() == INT_MAX) && 570 !upper.IsRelatedToArrayLength()) { 571 // Upper bound isn't useful. Leave it to deoptimization. 572 return this; 573 } 574 575 // Need to take care of underflow. Try to prove underflow won't happen 576 // for common cases. 577 if (range->GetLower().IsConstant()) { 578 int32_t constant = range->GetLower().GetConstant(); 579 if (constant >= INT_MIN - increment_) { 580 return new (GetAllocator()) ValueRange(GetAllocator(), range->GetLower(), upper); 581 } 582 } 583 584 // For non-constant lower bound, just assume might be underflow. Give up narrowing. 585 return this; 586 } 587 } 588 589 // Returns true if adding a (constant >= value) check for deoptimization 590 // is allowed and will benefit compiled code. 591 bool CanAddDeoptimizationConstant(HInstruction* value, 592 int32_t constant, 593 bool* is_proven) { 594 *is_proven = false; 595 // See if we can prove the relationship first. 596 if (value->IsIntConstant()) { 597 if (value->AsIntConstant()->GetValue() >= constant) { 598 // Already true. 599 *is_proven = true; 600 return true; 601 } else { 602 // May throw exception. Don't add deoptimization. 603 // Keep bounds checks in the loops. 604 return false; 605 } 606 } 607 // Can benefit from deoptimization. 608 return true; 609 } 610 611 // Adds a check that (value >= constant), and HDeoptimize otherwise. 612 void AddDeoptimizationConstant(HInstruction* value, 613 int32_t constant) { 614 HBasicBlock* block = induction_variable_->GetBlock(); 615 DCHECK(block->IsLoopHeader()); 616 HGraph* graph = block->GetGraph(); 617 HBasicBlock* pre_header = block->GetLoopInformation()->GetPreHeader(); 618 HSuspendCheck* suspend_check = block->GetLoopInformation()->GetSuspendCheck(); 619 HIntConstant* const_instr = graph->GetIntConstant(constant); 620 HCondition* cond = new (graph->GetArena()) HLessThan(value, const_instr); 621 HDeoptimize* deoptimize = new (graph->GetArena()) 622 HDeoptimize(cond, suspend_check->GetDexPc()); 623 pre_header->InsertInstructionBefore(cond, pre_header->GetLastInstruction()); 624 pre_header->InsertInstructionBefore(deoptimize, pre_header->GetLastInstruction()); 625 deoptimize->CopyEnvironmentFromWithLoopPhiAdjustment( 626 suspend_check->GetEnvironment(), block); 627 } 628 629 // Returns true if adding a (value <= array_length + offset) check for deoptimization 630 // is allowed and will benefit compiled code. 631 bool CanAddDeoptimizationArrayLength(HInstruction* value, 632 HArrayLength* array_length, 633 int32_t offset, 634 bool* is_proven) { 635 *is_proven = false; 636 if (offset > 0) { 637 // There might be overflow issue. 638 // TODO: handle this, possibly with some distance relationship between 639 // offset_low and offset_high, or using another deoptimization to make 640 // sure (array_length + offset) doesn't overflow. 641 return false; 642 } 643 644 // See if we can prove the relationship first. 645 if (value == array_length) { 646 if (offset >= 0) { 647 // Already true. 648 *is_proven = true; 649 return true; 650 } else { 651 // May throw exception. Don't add deoptimization. 652 // Keep bounds checks in the loops. 653 return false; 654 } 655 } 656 // Can benefit from deoptimization. 657 return true; 658 } 659 660 // Adds a check that (value <= array_length + offset), and HDeoptimize otherwise. 661 void AddDeoptimizationArrayLength(HInstruction* value, 662 HArrayLength* array_length, 663 int32_t offset) { 664 HBasicBlock* block = induction_variable_->GetBlock(); 665 DCHECK(block->IsLoopHeader()); 666 HGraph* graph = block->GetGraph(); 667 HBasicBlock* pre_header = block->GetLoopInformation()->GetPreHeader(); 668 HSuspendCheck* suspend_check = block->GetLoopInformation()->GetSuspendCheck(); 669 670 // We may need to hoist null-check and array_length out of loop first. 671 if (!array_length->GetBlock()->Dominates(pre_header)) { 672 HInstruction* array = array_length->InputAt(0); 673 HNullCheck* null_check = array->AsNullCheck(); 674 if (null_check != nullptr) { 675 array = null_check->InputAt(0); 676 } 677 // We've already made sure array is defined before the loop when collecting 678 // array accesses for the loop. 679 DCHECK(array->GetBlock()->Dominates(pre_header)); 680 if (null_check != nullptr && !null_check->GetBlock()->Dominates(pre_header)) { 681 // Hoist null check out of loop with a deoptimization. 682 HNullConstant* null_constant = graph->GetNullConstant(); 683 HCondition* null_check_cond = new (graph->GetArena()) HEqual(array, null_constant); 684 // TODO: for one dex_pc, share the same deoptimization slow path. 685 HDeoptimize* null_check_deoptimize = new (graph->GetArena()) 686 HDeoptimize(null_check_cond, suspend_check->GetDexPc()); 687 pre_header->InsertInstructionBefore(null_check_cond, pre_header->GetLastInstruction()); 688 pre_header->InsertInstructionBefore( 689 null_check_deoptimize, pre_header->GetLastInstruction()); 690 // Eliminate null check in the loop. 691 null_check->ReplaceWith(array); 692 null_check->GetBlock()->RemoveInstruction(null_check); 693 null_check_deoptimize->CopyEnvironmentFromWithLoopPhiAdjustment( 694 suspend_check->GetEnvironment(), block); 695 } 696 // Hoist array_length out of loop. 697 array_length->MoveBefore(pre_header->GetLastInstruction()); 698 } 699 700 HIntConstant* offset_instr = graph->GetIntConstant(offset); 701 HAdd* add = new (graph->GetArena()) HAdd(Primitive::kPrimInt, array_length, offset_instr); 702 HCondition* cond = new (graph->GetArena()) HGreaterThan(value, add); 703 HDeoptimize* deoptimize = new (graph->GetArena()) 704 HDeoptimize(cond, suspend_check->GetDexPc()); 705 pre_header->InsertInstructionBefore(add, pre_header->GetLastInstruction()); 706 pre_header->InsertInstructionBefore(cond, pre_header->GetLastInstruction()); 707 pre_header->InsertInstructionBefore(deoptimize, pre_header->GetLastInstruction()); 708 deoptimize->CopyEnvironmentFromWithLoopPhiAdjustment( 709 suspend_check->GetEnvironment(), block); 710 } 711 712 // Add deoptimizations in loop pre-header with the collected array access 713 // data so that value ranges can be established in loop body. 714 // Returns true if deoptimizations are successfully added, or if it's proven 715 // it's not necessary. 716 bool AddDeoptimization(const ArrayAccessInsideLoopFinder& finder) { 717 int32_t offset_low = finder.GetOffsetLow(); 718 int32_t offset_high = finder.GetOffsetHigh(); 719 HArrayLength* array_length = finder.GetFoundArrayLength(); 720 721 HBasicBlock* pre_header = 722 induction_variable_->GetBlock()->GetLoopInformation()->GetPreHeader(); 723 if (!initial_->GetBlock()->Dominates(pre_header) || 724 !end_->GetBlock()->Dominates(pre_header)) { 725 // Can't move initial_ or end_ into pre_header for comparisons. 726 return false; 727 } 728 729 bool is_constant_proven, is_length_proven; 730 if (increment_ == 1) { 731 // Increasing from initial_ to end_. 732 int32_t offset = inclusive_ ? -offset_high - 1 : -offset_high; 733 if (CanAddDeoptimizationConstant(initial_, -offset_low, &is_constant_proven) && 734 CanAddDeoptimizationArrayLength(end_, array_length, offset, &is_length_proven)) { 735 if (!is_constant_proven) { 736 AddDeoptimizationConstant(initial_, -offset_low); 737 } 738 if (!is_length_proven) { 739 AddDeoptimizationArrayLength(end_, array_length, offset); 740 } 741 return true; 742 } 743 } else if (increment_ == -1) { 744 // Decreasing from initial_ to end_. 745 int32_t constant = inclusive_ ? -offset_low : -offset_low - 1; 746 if (CanAddDeoptimizationConstant(end_, constant, &is_constant_proven) && 747 CanAddDeoptimizationArrayLength( 748 initial_, array_length, -offset_high - 1, &is_length_proven)) { 749 if (!is_constant_proven) { 750 AddDeoptimizationConstant(end_, constant); 751 } 752 if (!is_length_proven) { 753 AddDeoptimizationArrayLength(initial_, array_length, -offset_high - 1); 754 } 755 return true; 756 } 757 } 758 return false; 759 } 760 761 // Try to add HDeoptimize's in the loop pre-header first to narrow this range. 762 ValueRange* NarrowWithDeoptimization() { 763 if (increment_ != 1 && increment_ != -1) { 764 // TODO: possibly handle overflow/underflow issues with deoptimization. 765 return this; 766 } 767 768 if (end_ == nullptr) { 769 // No full info to add deoptimization. 770 return this; 771 } 772 773 ArrayAccessInsideLoopFinder finder(induction_variable_); 774 775 if (!finder.HasFoundArrayLength()) { 776 // No array access was found inside the loop that can benefit 777 // from deoptimization. 778 return this; 779 } 780 781 if (!AddDeoptimization(finder)) { 782 return this; 783 } 784 785 // After added deoptimizations, induction variable fits in 786 // [-offset_low, array.length-1-offset_high], adjusted with collected offsets. 787 ValueBound lower = ValueBound(0, -finder.GetOffsetLow()); 788 ValueBound upper = ValueBound(finder.GetFoundArrayLength(), -1 - finder.GetOffsetHigh()); 789 // We've narrowed the range after added deoptimizations. 790 return new (GetAllocator()) ValueRange(GetAllocator(), lower, upper); 791 } 792 793 private: 794 HPhi* const induction_variable_; // Induction variable for this monotonic value range. 795 HInstruction* const initial_; // Initial value. 796 HInstruction* end_; // End value. 797 bool inclusive_; // Whether end value is inclusive. 798 const int32_t increment_; // Increment for each loop iteration. 799 const ValueBound bound_; // Additional value bound info for initial_. 800 801 DISALLOW_COPY_AND_ASSIGN(MonotonicValueRange); 802}; 803 804class BCEVisitor : public HGraphVisitor { 805 public: 806 // The least number of bounds checks that should be eliminated by triggering 807 // the deoptimization technique. 808 static constexpr size_t kThresholdForAddingDeoptimize = 2; 809 810 // Very large constant index is considered as an anomaly. This is a threshold 811 // beyond which we don't bother to apply the deoptimization technique since 812 // it's likely some AIOOBE will be thrown. 813 static constexpr int32_t kMaxConstantForAddingDeoptimize = INT_MAX - 1024 * 1024; 814 815 explicit BCEVisitor(HGraph* graph) 816 : HGraphVisitor(graph), 817 maps_(graph->GetBlocks().Size()), 818 need_to_revisit_block_(false) {} 819 820 void VisitBasicBlock(HBasicBlock* block) OVERRIDE { 821 first_constant_index_bounds_check_map_.clear(); 822 HGraphVisitor::VisitBasicBlock(block); 823 if (need_to_revisit_block_) { 824 AddComparesWithDeoptimization(block); 825 need_to_revisit_block_ = false; 826 first_constant_index_bounds_check_map_.clear(); 827 GetValueRangeMap(block)->clear(); 828 HGraphVisitor::VisitBasicBlock(block); 829 } 830 } 831 832 private: 833 // Return the map of proven value ranges at the beginning of a basic block. 834 ArenaSafeMap<int, ValueRange*>* GetValueRangeMap(HBasicBlock* basic_block) { 835 int block_id = basic_block->GetBlockId(); 836 if (maps_.at(block_id) == nullptr) { 837 std::unique_ptr<ArenaSafeMap<int, ValueRange*>> map( 838 new ArenaSafeMap<int, ValueRange*>( 839 std::less<int>(), GetGraph()->GetArena()->Adapter())); 840 maps_.at(block_id) = std::move(map); 841 } 842 return maps_.at(block_id).get(); 843 } 844 845 // Traverse up the dominator tree to look for value range info. 846 ValueRange* LookupValueRange(HInstruction* instruction, HBasicBlock* basic_block) { 847 while (basic_block != nullptr) { 848 ArenaSafeMap<int, ValueRange*>* map = GetValueRangeMap(basic_block); 849 if (map->find(instruction->GetId()) != map->end()) { 850 return map->Get(instruction->GetId()); 851 } 852 basic_block = basic_block->GetDominator(); 853 } 854 // Didn't find any. 855 return nullptr; 856 } 857 858 // Narrow the value range of `instruction` at the end of `basic_block` with `range`, 859 // and push the narrowed value range to `successor`. 860 void ApplyRangeFromComparison(HInstruction* instruction, HBasicBlock* basic_block, 861 HBasicBlock* successor, ValueRange* range) { 862 ValueRange* existing_range = LookupValueRange(instruction, basic_block); 863 if (existing_range == nullptr) { 864 if (range != nullptr) { 865 GetValueRangeMap(successor)->Overwrite(instruction->GetId(), range); 866 } 867 return; 868 } 869 if (existing_range->IsMonotonicValueRange()) { 870 DCHECK(instruction->IsLoopHeaderPhi()); 871 // Make sure the comparison is in the loop header so each increment is 872 // checked with a comparison. 873 if (instruction->GetBlock() != basic_block) { 874 return; 875 } 876 } 877 ValueRange* narrowed_range = existing_range->Narrow(range); 878 if (narrowed_range != nullptr) { 879 GetValueRangeMap(successor)->Overwrite(instruction->GetId(), narrowed_range); 880 } 881 } 882 883 // Special case that we may simultaneously narrow two MonotonicValueRange's to 884 // regular value ranges. 885 void HandleIfBetweenTwoMonotonicValueRanges(HIf* instruction, 886 HInstruction* left, 887 HInstruction* right, 888 IfCondition cond, 889 MonotonicValueRange* left_range, 890 MonotonicValueRange* right_range) { 891 DCHECK(left->IsLoopHeaderPhi()); 892 DCHECK(right->IsLoopHeaderPhi()); 893 if (instruction->GetBlock() != left->GetBlock()) { 894 // Comparison needs to be in loop header to make sure it's done after each 895 // increment/decrement. 896 return; 897 } 898 899 // Handle common cases which also don't have overflow/underflow concerns. 900 if (left_range->GetIncrement() == 1 && 901 left_range->GetBound().IsConstant() && 902 right_range->GetIncrement() == -1 && 903 right_range->GetBound().IsRelatedToArrayLength() && 904 right_range->GetBound().GetConstant() < 0) { 905 HBasicBlock* successor = nullptr; 906 int32_t left_compensation = 0; 907 int32_t right_compensation = 0; 908 if (cond == kCondLT) { 909 left_compensation = -1; 910 right_compensation = 1; 911 successor = instruction->IfTrueSuccessor(); 912 } else if (cond == kCondLE) { 913 successor = instruction->IfTrueSuccessor(); 914 } else if (cond == kCondGT) { 915 successor = instruction->IfFalseSuccessor(); 916 } else if (cond == kCondGE) { 917 left_compensation = -1; 918 right_compensation = 1; 919 successor = instruction->IfFalseSuccessor(); 920 } else { 921 // We don't handle '=='/'!=' test in case left and right can cross and 922 // miss each other. 923 return; 924 } 925 926 if (successor != nullptr) { 927 bool overflow; 928 bool underflow; 929 ValueRange* new_left_range = new (GetGraph()->GetArena()) ValueRange( 930 GetGraph()->GetArena(), 931 left_range->GetBound(), 932 right_range->GetBound().Add(left_compensation, &overflow, &underflow)); 933 if (!overflow && !underflow) { 934 ApplyRangeFromComparison(left, instruction->GetBlock(), successor, 935 new_left_range); 936 } 937 938 ValueRange* new_right_range = new (GetGraph()->GetArena()) ValueRange( 939 GetGraph()->GetArena(), 940 left_range->GetBound().Add(right_compensation, &overflow, &underflow), 941 right_range->GetBound()); 942 if (!overflow && !underflow) { 943 ApplyRangeFromComparison(right, instruction->GetBlock(), successor, 944 new_right_range); 945 } 946 } 947 } 948 } 949 950 // Handle "if (left cmp_cond right)". 951 void HandleIf(HIf* instruction, HInstruction* left, HInstruction* right, IfCondition cond) { 952 HBasicBlock* block = instruction->GetBlock(); 953 954 HBasicBlock* true_successor = instruction->IfTrueSuccessor(); 955 // There should be no critical edge at this point. 956 DCHECK_EQ(true_successor->GetPredecessors().Size(), 1u); 957 958 HBasicBlock* false_successor = instruction->IfFalseSuccessor(); 959 // There should be no critical edge at this point. 960 DCHECK_EQ(false_successor->GetPredecessors().Size(), 1u); 961 962 ValueRange* left_range = LookupValueRange(left, block); 963 MonotonicValueRange* left_monotonic_range = nullptr; 964 if (left_range != nullptr) { 965 left_monotonic_range = left_range->AsMonotonicValueRange(); 966 if (left_monotonic_range != nullptr) { 967 HBasicBlock* loop_head = left_monotonic_range->GetLoopHead(); 968 if (instruction->GetBlock() != loop_head) { 969 // For monotonic value range, don't handle `instruction` 970 // if it's not defined in the loop header. 971 return; 972 } 973 } 974 } 975 976 bool found; 977 ValueBound bound = ValueBound::DetectValueBoundFromValue(right, &found); 978 // Each comparison can establish a lower bound and an upper bound 979 // for the left hand side. 980 ValueBound lower = bound; 981 ValueBound upper = bound; 982 if (!found) { 983 // No constant or array.length+c format bound found. 984 // For i<j, we can still use j's upper bound as i's upper bound. Same for lower. 985 ValueRange* right_range = LookupValueRange(right, block); 986 if (right_range != nullptr) { 987 if (right_range->IsMonotonicValueRange()) { 988 if (left_range != nullptr && left_range->IsMonotonicValueRange()) { 989 HandleIfBetweenTwoMonotonicValueRanges(instruction, left, right, cond, 990 left_range->AsMonotonicValueRange(), 991 right_range->AsMonotonicValueRange()); 992 return; 993 } 994 } 995 lower = right_range->GetLower(); 996 upper = right_range->GetUpper(); 997 } else { 998 lower = ValueBound::Min(); 999 upper = ValueBound::Max(); 1000 } 1001 } 1002 1003 bool overflow, underflow; 1004 if (cond == kCondLT || cond == kCondLE) { 1005 if (left_monotonic_range != nullptr) { 1006 // Update the info for monotonic value range. 1007 if (left_monotonic_range->GetInductionVariable() == left && 1008 left_monotonic_range->GetIncrement() < 0 && 1009 block == left_monotonic_range->GetLoopHead() && 1010 instruction->IfFalseSuccessor()->GetLoopInformation() == block->GetLoopInformation()) { 1011 left_monotonic_range->SetEnd(right); 1012 left_monotonic_range->SetInclusive(cond == kCondLT); 1013 } 1014 } 1015 1016 if (!upper.Equals(ValueBound::Max())) { 1017 int32_t compensation = (cond == kCondLT) ? -1 : 0; // upper bound is inclusive 1018 ValueBound new_upper = upper.Add(compensation, &overflow, &underflow); 1019 if (overflow || underflow) { 1020 return; 1021 } 1022 ValueRange* new_range = new (GetGraph()->GetArena()) 1023 ValueRange(GetGraph()->GetArena(), ValueBound::Min(), new_upper); 1024 ApplyRangeFromComparison(left, block, true_successor, new_range); 1025 } 1026 1027 // array.length as a lower bound isn't considered useful. 1028 if (!lower.Equals(ValueBound::Min()) && !lower.IsRelatedToArrayLength()) { 1029 int32_t compensation = (cond == kCondLE) ? 1 : 0; // lower bound is inclusive 1030 ValueBound new_lower = lower.Add(compensation, &overflow, &underflow); 1031 if (overflow || underflow) { 1032 return; 1033 } 1034 ValueRange* new_range = new (GetGraph()->GetArena()) 1035 ValueRange(GetGraph()->GetArena(), new_lower, ValueBound::Max()); 1036 ApplyRangeFromComparison(left, block, false_successor, new_range); 1037 } 1038 } else if (cond == kCondGT || cond == kCondGE) { 1039 if (left_monotonic_range != nullptr) { 1040 // Update the info for monotonic value range. 1041 if (left_monotonic_range->GetInductionVariable() == left && 1042 left_monotonic_range->GetIncrement() > 0 && 1043 block == left_monotonic_range->GetLoopHead() && 1044 instruction->IfFalseSuccessor()->GetLoopInformation() == block->GetLoopInformation()) { 1045 left_monotonic_range->SetEnd(right); 1046 left_monotonic_range->SetInclusive(cond == kCondGT); 1047 } 1048 } 1049 1050 // array.length as a lower bound isn't considered useful. 1051 if (!lower.Equals(ValueBound::Min()) && !lower.IsRelatedToArrayLength()) { 1052 int32_t compensation = (cond == kCondGT) ? 1 : 0; // lower bound is inclusive 1053 ValueBound new_lower = lower.Add(compensation, &overflow, &underflow); 1054 if (overflow || underflow) { 1055 return; 1056 } 1057 ValueRange* new_range = new (GetGraph()->GetArena()) 1058 ValueRange(GetGraph()->GetArena(), new_lower, ValueBound::Max()); 1059 ApplyRangeFromComparison(left, block, true_successor, new_range); 1060 } 1061 1062 if (!upper.Equals(ValueBound::Max())) { 1063 int32_t compensation = (cond == kCondGE) ? -1 : 0; // upper bound is inclusive 1064 ValueBound new_upper = upper.Add(compensation, &overflow, &underflow); 1065 if (overflow || underflow) { 1066 return; 1067 } 1068 ValueRange* new_range = new (GetGraph()->GetArena()) 1069 ValueRange(GetGraph()->GetArena(), ValueBound::Min(), new_upper); 1070 ApplyRangeFromComparison(left, block, false_successor, new_range); 1071 } 1072 } 1073 } 1074 1075 void VisitBoundsCheck(HBoundsCheck* bounds_check) { 1076 HBasicBlock* block = bounds_check->GetBlock(); 1077 HInstruction* index = bounds_check->InputAt(0); 1078 HInstruction* array_length = bounds_check->InputAt(1); 1079 DCHECK(array_length->IsIntConstant() || array_length->IsArrayLength()); 1080 1081 if (!index->IsIntConstant()) { 1082 ValueRange* index_range = LookupValueRange(index, block); 1083 if (index_range != nullptr) { 1084 ValueBound lower = ValueBound(nullptr, 0); // constant 0 1085 ValueBound upper = ValueBound(array_length, -1); // array_length - 1 1086 ValueRange* array_range = new (GetGraph()->GetArena()) 1087 ValueRange(GetGraph()->GetArena(), lower, upper); 1088 if (index_range->FitsIn(array_range)) { 1089 ReplaceBoundsCheck(bounds_check, index); 1090 return; 1091 } 1092 } 1093 } else { 1094 int32_t constant = index->AsIntConstant()->GetValue(); 1095 if (constant < 0) { 1096 // Will always throw exception. 1097 return; 1098 } 1099 if (array_length->IsIntConstant()) { 1100 if (constant < array_length->AsIntConstant()->GetValue()) { 1101 ReplaceBoundsCheck(bounds_check, index); 1102 } 1103 return; 1104 } 1105 1106 DCHECK(array_length->IsArrayLength()); 1107 ValueRange* existing_range = LookupValueRange(array_length, block); 1108 if (existing_range != nullptr) { 1109 ValueBound lower = existing_range->GetLower(); 1110 DCHECK(lower.IsConstant()); 1111 if (constant < lower.GetConstant()) { 1112 ReplaceBoundsCheck(bounds_check, index); 1113 return; 1114 } else { 1115 // Existing range isn't strong enough to eliminate the bounds check. 1116 // Fall through to update the array_length range with info from this 1117 // bounds check. 1118 } 1119 } 1120 1121 if (first_constant_index_bounds_check_map_.find(array_length->GetId()) == 1122 first_constant_index_bounds_check_map_.end()) { 1123 // Remember the first bounds check against array_length of a constant index. 1124 // That bounds check instruction has an associated HEnvironment where we 1125 // may add an HDeoptimize to eliminate bounds checks of constant indices 1126 // against array_length. 1127 first_constant_index_bounds_check_map_.Put(array_length->GetId(), bounds_check); 1128 } else { 1129 // We've seen it at least twice. It's beneficial to introduce a compare with 1130 // deoptimization fallback to eliminate the bounds checks. 1131 need_to_revisit_block_ = true; 1132 } 1133 1134 // Once we have an array access like 'array[5] = 1', we record array.length >= 6. 1135 // We currently don't do it for non-constant index since a valid array[i] can't prove 1136 // a valid array[i-1] yet due to the lower bound side. 1137 if (constant == INT_MAX) { 1138 // INT_MAX as an index will definitely throw AIOOBE. 1139 return; 1140 } 1141 ValueBound lower = ValueBound(nullptr, constant + 1); 1142 ValueBound upper = ValueBound::Max(); 1143 ValueRange* range = new (GetGraph()->GetArena()) 1144 ValueRange(GetGraph()->GetArena(), lower, upper); 1145 GetValueRangeMap(block)->Overwrite(array_length->GetId(), range); 1146 } 1147 } 1148 1149 void ReplaceBoundsCheck(HInstruction* bounds_check, HInstruction* index) { 1150 bounds_check->ReplaceWith(index); 1151 bounds_check->GetBlock()->RemoveInstruction(bounds_check); 1152 } 1153 1154 void VisitPhi(HPhi* phi) { 1155 if (phi->IsLoopHeaderPhi() && phi->GetType() == Primitive::kPrimInt) { 1156 DCHECK_EQ(phi->InputCount(), 2U); 1157 HInstruction* instruction = phi->InputAt(1); 1158 HInstruction *left; 1159 int32_t increment; 1160 if (ValueBound::IsAddOrSubAConstant(instruction, &left, &increment)) { 1161 if (left == phi) { 1162 HInstruction* initial_value = phi->InputAt(0); 1163 ValueRange* range = nullptr; 1164 if (increment == 0) { 1165 // Add constant 0. It's really a fixed value. 1166 range = new (GetGraph()->GetArena()) ValueRange( 1167 GetGraph()->GetArena(), 1168 ValueBound(initial_value, 0), 1169 ValueBound(initial_value, 0)); 1170 } else { 1171 // Monotonically increasing/decreasing. 1172 bool found; 1173 ValueBound bound = ValueBound::DetectValueBoundFromValue( 1174 initial_value, &found); 1175 if (!found) { 1176 // No constant or array.length+c bound found. 1177 // For i=j, we can still use j's upper bound as i's upper bound. 1178 // Same for lower. 1179 ValueRange* initial_range = LookupValueRange(initial_value, phi->GetBlock()); 1180 if (initial_range != nullptr) { 1181 bound = increment > 0 ? initial_range->GetLower() : 1182 initial_range->GetUpper(); 1183 } else { 1184 bound = increment > 0 ? ValueBound::Min() : ValueBound::Max(); 1185 } 1186 } 1187 range = new (GetGraph()->GetArena()) MonotonicValueRange( 1188 GetGraph()->GetArena(), 1189 phi, 1190 initial_value, 1191 increment, 1192 bound); 1193 } 1194 GetValueRangeMap(phi->GetBlock())->Overwrite(phi->GetId(), range); 1195 } 1196 } 1197 } 1198 } 1199 1200 void VisitIf(HIf* instruction) { 1201 if (instruction->InputAt(0)->IsCondition()) { 1202 HCondition* cond = instruction->InputAt(0)->AsCondition(); 1203 IfCondition cmp = cond->GetCondition(); 1204 if (cmp == kCondGT || cmp == kCondGE || 1205 cmp == kCondLT || cmp == kCondLE) { 1206 HInstruction* left = cond->GetLeft(); 1207 HInstruction* right = cond->GetRight(); 1208 HandleIf(instruction, left, right, cmp); 1209 1210 HBasicBlock* block = instruction->GetBlock(); 1211 ValueRange* left_range = LookupValueRange(left, block); 1212 if (left_range == nullptr) { 1213 return; 1214 } 1215 1216 if (left_range->IsMonotonicValueRange() && 1217 block == left_range->AsMonotonicValueRange()->GetLoopHead()) { 1218 // The comparison is for an induction variable in the loop header. 1219 DCHECK(left == left_range->AsMonotonicValueRange()->GetInductionVariable()); 1220 HBasicBlock* loop_body_successor; 1221 if (LIKELY(block->GetLoopInformation()-> 1222 Contains(*instruction->IfFalseSuccessor()))) { 1223 loop_body_successor = instruction->IfFalseSuccessor(); 1224 } else { 1225 loop_body_successor = instruction->IfTrueSuccessor(); 1226 } 1227 ValueRange* new_left_range = LookupValueRange(left, loop_body_successor); 1228 if (new_left_range == left_range) { 1229 // We are not successful in narrowing the monotonic value range to 1230 // a regular value range. Try using deoptimization. 1231 new_left_range = left_range->AsMonotonicValueRange()-> 1232 NarrowWithDeoptimization(); 1233 if (new_left_range != left_range) { 1234 GetValueRangeMap(instruction->IfFalseSuccessor())-> 1235 Overwrite(left->GetId(), new_left_range); 1236 } 1237 } 1238 } 1239 } 1240 } 1241 } 1242 1243 void VisitAdd(HAdd* add) { 1244 HInstruction* right = add->GetRight(); 1245 if (right->IsIntConstant()) { 1246 ValueRange* left_range = LookupValueRange(add->GetLeft(), add->GetBlock()); 1247 if (left_range == nullptr) { 1248 return; 1249 } 1250 ValueRange* range = left_range->Add(right->AsIntConstant()->GetValue()); 1251 if (range != nullptr) { 1252 GetValueRangeMap(add->GetBlock())->Overwrite(add->GetId(), range); 1253 } 1254 } 1255 } 1256 1257 void VisitSub(HSub* sub) { 1258 HInstruction* left = sub->GetLeft(); 1259 HInstruction* right = sub->GetRight(); 1260 if (right->IsIntConstant()) { 1261 ValueRange* left_range = LookupValueRange(left, sub->GetBlock()); 1262 if (left_range == nullptr) { 1263 return; 1264 } 1265 ValueRange* range = left_range->Add(-right->AsIntConstant()->GetValue()); 1266 if (range != nullptr) { 1267 GetValueRangeMap(sub->GetBlock())->Overwrite(sub->GetId(), range); 1268 return; 1269 } 1270 } 1271 1272 // Here we are interested in the typical triangular case of nested loops, 1273 // such as the inner loop 'for (int j=0; j<array.length-i; j++)' where i 1274 // is the index for outer loop. In this case, we know j is bounded by array.length-1. 1275 1276 // Try to handle (array.length - i) or (array.length + c - i) format. 1277 HInstruction* left_of_left; // left input of left. 1278 int32_t right_const = 0; 1279 if (ValueBound::IsAddOrSubAConstant(left, &left_of_left, &right_const)) { 1280 left = left_of_left; 1281 } 1282 // The value of left input of the sub equals (left + right_const). 1283 1284 if (left->IsArrayLength()) { 1285 HInstruction* array_length = left->AsArrayLength(); 1286 ValueRange* right_range = LookupValueRange(right, sub->GetBlock()); 1287 if (right_range != nullptr) { 1288 ValueBound lower = right_range->GetLower(); 1289 ValueBound upper = right_range->GetUpper(); 1290 if (lower.IsConstant() && upper.IsRelatedToArrayLength()) { 1291 HInstruction* upper_inst = upper.GetInstruction(); 1292 // Make sure it's the same array. 1293 if (ValueBound::Equal(array_length, upper_inst)) { 1294 int32_t c0 = right_const; 1295 int32_t c1 = lower.GetConstant(); 1296 int32_t c2 = upper.GetConstant(); 1297 // (array.length + c0 - v) where v is in [c1, array.length + c2] 1298 // gets [c0 - c2, array.length + c0 - c1] as its value range. 1299 if (!ValueBound::WouldAddOverflowOrUnderflow(c0, -c2) && 1300 !ValueBound::WouldAddOverflowOrUnderflow(c0, -c1)) { 1301 if ((c0 - c1) <= 0) { 1302 // array.length + (c0 - c1) won't overflow/underflow. 1303 ValueRange* range = new (GetGraph()->GetArena()) ValueRange( 1304 GetGraph()->GetArena(), 1305 ValueBound(nullptr, right_const - upper.GetConstant()), 1306 ValueBound(array_length, right_const - lower.GetConstant())); 1307 GetValueRangeMap(sub->GetBlock())->Overwrite(sub->GetId(), range); 1308 } 1309 } 1310 } 1311 } 1312 } 1313 } 1314 } 1315 1316 void FindAndHandlePartialArrayLength(HBinaryOperation* instruction) { 1317 DCHECK(instruction->IsDiv() || instruction->IsShr() || instruction->IsUShr()); 1318 HInstruction* right = instruction->GetRight(); 1319 int32_t right_const; 1320 if (right->IsIntConstant()) { 1321 right_const = right->AsIntConstant()->GetValue(); 1322 // Detect division by two or more. 1323 if ((instruction->IsDiv() && right_const <= 1) || 1324 (instruction->IsShr() && right_const < 1) || 1325 (instruction->IsUShr() && right_const < 1)) { 1326 return; 1327 } 1328 } else { 1329 return; 1330 } 1331 1332 // Try to handle array.length/2 or (array.length-1)/2 format. 1333 HInstruction* left = instruction->GetLeft(); 1334 HInstruction* left_of_left; // left input of left. 1335 int32_t c = 0; 1336 if (ValueBound::IsAddOrSubAConstant(left, &left_of_left, &c)) { 1337 left = left_of_left; 1338 } 1339 // The value of left input of instruction equals (left + c). 1340 1341 // (array_length + 1) or smaller divided by two or more 1342 // always generate a value in [INT_MIN, array_length]. 1343 // This is true even if array_length is INT_MAX. 1344 if (left->IsArrayLength() && c <= 1) { 1345 if (instruction->IsUShr() && c < 0) { 1346 // Make sure for unsigned shift, left side is not negative. 1347 // e.g. if array_length is 2, ((array_length - 3) >>> 2) is way bigger 1348 // than array_length. 1349 return; 1350 } 1351 ValueRange* range = new (GetGraph()->GetArena()) ValueRange( 1352 GetGraph()->GetArena(), 1353 ValueBound(nullptr, INT_MIN), 1354 ValueBound(left, 0)); 1355 GetValueRangeMap(instruction->GetBlock())->Overwrite(instruction->GetId(), range); 1356 } 1357 } 1358 1359 void VisitDiv(HDiv* div) { 1360 FindAndHandlePartialArrayLength(div); 1361 } 1362 1363 void VisitShr(HShr* shr) { 1364 FindAndHandlePartialArrayLength(shr); 1365 } 1366 1367 void VisitUShr(HUShr* ushr) { 1368 FindAndHandlePartialArrayLength(ushr); 1369 } 1370 1371 void VisitAnd(HAnd* instruction) { 1372 if (instruction->GetRight()->IsIntConstant()) { 1373 int32_t constant = instruction->GetRight()->AsIntConstant()->GetValue(); 1374 if (constant > 0) { 1375 // constant serves as a mask so any number masked with it 1376 // gets a [0, constant] value range. 1377 ValueRange* range = new (GetGraph()->GetArena()) ValueRange( 1378 GetGraph()->GetArena(), 1379 ValueBound(nullptr, 0), 1380 ValueBound(nullptr, constant)); 1381 GetValueRangeMap(instruction->GetBlock())->Overwrite(instruction->GetId(), range); 1382 } 1383 } 1384 } 1385 1386 void VisitNewArray(HNewArray* new_array) { 1387 HInstruction* len = new_array->InputAt(0); 1388 if (!len->IsIntConstant()) { 1389 HInstruction *left; 1390 int32_t right_const; 1391 if (ValueBound::IsAddOrSubAConstant(len, &left, &right_const)) { 1392 // (left + right_const) is used as size to new the array. 1393 // We record "-right_const <= left <= new_array - right_const"; 1394 ValueBound lower = ValueBound(nullptr, -right_const); 1395 // We use new_array for the bound instead of new_array.length, 1396 // which isn't available as an instruction yet. new_array will 1397 // be treated the same as new_array.length when it's used in a ValueBound. 1398 ValueBound upper = ValueBound(new_array, -right_const); 1399 ValueRange* range = new (GetGraph()->GetArena()) 1400 ValueRange(GetGraph()->GetArena(), lower, upper); 1401 GetValueRangeMap(new_array->GetBlock())->Overwrite(left->GetId(), range); 1402 } 1403 } 1404 } 1405 1406 void VisitDeoptimize(HDeoptimize* deoptimize) { 1407 // Right now it's only HLessThanOrEqual. 1408 DCHECK(deoptimize->InputAt(0)->IsLessThanOrEqual()); 1409 HLessThanOrEqual* less_than_or_equal = deoptimize->InputAt(0)->AsLessThanOrEqual(); 1410 HInstruction* instruction = less_than_or_equal->InputAt(0); 1411 if (instruction->IsArrayLength()) { 1412 HInstruction* constant = less_than_or_equal->InputAt(1); 1413 DCHECK(constant->IsIntConstant()); 1414 DCHECK(constant->AsIntConstant()->GetValue() <= kMaxConstantForAddingDeoptimize); 1415 ValueBound lower = ValueBound(nullptr, constant->AsIntConstant()->GetValue() + 1); 1416 ValueRange* range = new (GetGraph()->GetArena()) 1417 ValueRange(GetGraph()->GetArena(), lower, ValueBound::Max()); 1418 GetValueRangeMap(deoptimize->GetBlock())->Overwrite(instruction->GetId(), range); 1419 } 1420 } 1421 1422 void AddCompareWithDeoptimization(HInstruction* array_length, 1423 HIntConstant* const_instr, 1424 HBasicBlock* block) { 1425 DCHECK(array_length->IsArrayLength()); 1426 ValueRange* range = LookupValueRange(array_length, block); 1427 ValueBound lower_bound = range->GetLower(); 1428 DCHECK(lower_bound.IsConstant()); 1429 DCHECK(const_instr->GetValue() <= kMaxConstantForAddingDeoptimize); 1430 DCHECK_EQ(lower_bound.GetConstant(), const_instr->GetValue() + 1); 1431 1432 // If array_length is less than lower_const, deoptimize. 1433 HBoundsCheck* bounds_check = first_constant_index_bounds_check_map_.Get( 1434 array_length->GetId())->AsBoundsCheck(); 1435 HCondition* cond = new (GetGraph()->GetArena()) HLessThanOrEqual(array_length, const_instr); 1436 HDeoptimize* deoptimize = new (GetGraph()->GetArena()) 1437 HDeoptimize(cond, bounds_check->GetDexPc()); 1438 block->InsertInstructionBefore(cond, bounds_check); 1439 block->InsertInstructionBefore(deoptimize, bounds_check); 1440 deoptimize->CopyEnvironmentFrom(bounds_check->GetEnvironment()); 1441 } 1442 1443 void AddComparesWithDeoptimization(HBasicBlock* block) { 1444 for (ArenaSafeMap<int, HBoundsCheck*>::iterator it = 1445 first_constant_index_bounds_check_map_.begin(); 1446 it != first_constant_index_bounds_check_map_.end(); 1447 ++it) { 1448 HBoundsCheck* bounds_check = it->second; 1449 HArrayLength* array_length = bounds_check->InputAt(1)->AsArrayLength(); 1450 HIntConstant* lower_bound_const_instr = nullptr; 1451 int32_t lower_bound_const = INT_MIN; 1452 size_t counter = 0; 1453 // Count the constant indexing for which bounds checks haven't 1454 // been removed yet. 1455 for (HUseIterator<HInstruction*> it2(array_length->GetUses()); 1456 !it2.Done(); 1457 it2.Advance()) { 1458 HInstruction* user = it2.Current()->GetUser(); 1459 if (user->GetBlock() == block && 1460 user->IsBoundsCheck() && 1461 user->AsBoundsCheck()->InputAt(0)->IsIntConstant()) { 1462 DCHECK_EQ(array_length, user->AsBoundsCheck()->InputAt(1)); 1463 HIntConstant* const_instr = user->AsBoundsCheck()->InputAt(0)->AsIntConstant(); 1464 if (const_instr->GetValue() > lower_bound_const) { 1465 lower_bound_const = const_instr->GetValue(); 1466 lower_bound_const_instr = const_instr; 1467 } 1468 counter++; 1469 } 1470 } 1471 if (counter >= kThresholdForAddingDeoptimize && 1472 lower_bound_const_instr->GetValue() <= kMaxConstantForAddingDeoptimize) { 1473 AddCompareWithDeoptimization(array_length, lower_bound_const_instr, block); 1474 } 1475 } 1476 } 1477 1478 std::vector<std::unique_ptr<ArenaSafeMap<int, ValueRange*>>> maps_; 1479 1480 // Map an HArrayLength instruction's id to the first HBoundsCheck instruction in 1481 // a block that checks a constant index against that HArrayLength. 1482 SafeMap<int, HBoundsCheck*> first_constant_index_bounds_check_map_; 1483 1484 // For the block, there is at least one HArrayLength instruction for which there 1485 // is more than one bounds check instruction with constant indexing. And it's 1486 // beneficial to add a compare instruction that has deoptimization fallback and 1487 // eliminate those bounds checks. 1488 bool need_to_revisit_block_; 1489 1490 DISALLOW_COPY_AND_ASSIGN(BCEVisitor); 1491}; 1492 1493void BoundsCheckElimination::Run() { 1494 if (!graph_->HasBoundsChecks()) { 1495 return; 1496 } 1497 1498 BCEVisitor visitor(graph_); 1499 // Reverse post order guarantees a node's dominators are visited first. 1500 // We want to visit in the dominator-based order since if a value is known to 1501 // be bounded by a range at one instruction, it must be true that all uses of 1502 // that value dominated by that instruction fits in that range. Range of that 1503 // value can be narrowed further down in the dominator tree. 1504 // 1505 // TODO: only visit blocks that dominate some array accesses. 1506 visitor.VisitReversePostOrder(); 1507} 1508 1509} // namespace art 1510