Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(102)

Side by Side Diff: runtime/vm/intermediate_language.cc

Issue 328503003: Extend Range analysis to 64-bit range and mint operations (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Created 6 years, 6 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « runtime/vm/intermediate_language.h ('k') | runtime/vm/intermediate_language_test.cc » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file 1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file
2 // for details. All rights reserved. Use of this source code is governed by a 2 // for details. All rights reserved. Use of this source code is governed by a
3 // BSD-style license that can be found in the LICENSE file. 3 // BSD-style license that can be found in the LICENSE file.
4 4
5 #include "vm/intermediate_language.h" 5 #include "vm/intermediate_language.h"
6 6
7 #include "vm/bigint_operations.h" 7 #include "vm/bigint_operations.h"
8 #include "vm/bit_vector.h" 8 #include "vm/bit_vector.h"
9 #include "vm/cpu.h" 9 #include "vm/cpu.h"
10 #include "vm/dart_entry.h" 10 #include "vm/dart_entry.h"
(...skipping 2431 matching lines...) Expand 10 before | Expand all | Expand 10 after
2442 intptr_t use_index = instr->env()->Length(); // Start index after inner. 2442 intptr_t use_index = instr->env()->Length(); // Start index after inner.
2443 for (Environment::DeepIterator it(copy); !it.Done(); it.Advance()) { 2443 for (Environment::DeepIterator it(copy); !it.Done(); it.Advance()) {
2444 Value* value = it.CurrentValue(); 2444 Value* value = it.CurrentValue();
2445 value->set_instruction(instr); 2445 value->set_instruction(instr);
2446 value->set_use_index(use_index++); 2446 value->set_use_index(use_index++);
2447 value->definition()->AddEnvUse(value); 2447 value->definition()->AddEnvUse(value);
2448 } 2448 }
2449 } 2449 }
2450 2450
2451 2451
2452 RangeBoundary RangeBoundary::FromDefinition(Definition* defn, intptr_t offs) { 2452 RangeBoundary RangeBoundary::FromDefinition(Definition* defn, int64_t offs) {
2453 if (defn->IsConstant() && defn->AsConstant()->value().IsSmi()) { 2453 if (defn->IsConstant() && defn->AsConstant()->value().IsSmi()) {
2454 return FromConstant(Smi::Cast(defn->AsConstant()->value()).Value() + offs); 2454 return FromConstant(Smi::Cast(defn->AsConstant()->value()).Value() + offs);
2455 } 2455 }
2456 return RangeBoundary(kSymbol, reinterpret_cast<intptr_t>(defn), offs); 2456 return RangeBoundary(kSymbol, reinterpret_cast<intptr_t>(defn), offs);
2457 } 2457 }
2458 2458
2459 2459
2460 RangeBoundary RangeBoundary::LowerBound() const { 2460 RangeBoundary RangeBoundary::LowerBound() const {
2461 if (IsNegativeInfinity()) return *this; 2461 if (IsInfinity()) {
2462 return NegativeInfinity();
2463 }
2462 if (IsConstant()) return *this; 2464 if (IsConstant()) return *this;
2463 return Add(Range::ConstantMin(symbol()->range()), 2465 return Add(Range::ConstantMin(symbol()->range()),
2464 RangeBoundary::FromConstant(offset_), 2466 RangeBoundary::FromConstant(offset_),
2465 NegativeInfinity()); 2467 NegativeInfinity());
2466 } 2468 }
2467 2469
2468 2470
2469 RangeBoundary RangeBoundary::UpperBound() const { 2471 RangeBoundary RangeBoundary::UpperBound() const {
2470 if (IsPositiveInfinity()) return *this; 2472 if (IsInfinity()) {
2473 return PositiveInfinity();
2474 }
2471 if (IsConstant()) return *this; 2475 if (IsConstant()) return *this;
2472 return Add(Range::ConstantMax(symbol()->range()), 2476 return Add(Range::ConstantMax(symbol()->range()),
2473 RangeBoundary::FromConstant(offset_), 2477 RangeBoundary::FromConstant(offset_),
2474 PositiveInfinity()); 2478 PositiveInfinity());
2475 } 2479 }
2476 2480
2477 2481
2482 RangeBoundary RangeBoundary::Add(const RangeBoundary& a,
2483 const RangeBoundary& b,
2484 const RangeBoundary& overflow) {
2485 ASSERT(a.IsConstant() && b.IsConstant());
2486
2487 if (Utils::WillAddOverflow(a.ConstantValue(), b.ConstantValue())) {
2488 return overflow;
2489 }
2490
2491 int64_t result = a.ConstantValue() + b.ConstantValue();
2492
2493 return RangeBoundary::FromConstant(result);
2494 }
2495
2496
2497 RangeBoundary RangeBoundary::Sub(const RangeBoundary& a,
2498 const RangeBoundary& b,
2499 const RangeBoundary& overflow) {
2500 ASSERT(a.IsConstant() && b.IsConstant());
2501
2502 if (Utils::WillSubOverflow(a.ConstantValue(), b.ConstantValue())) {
2503 return overflow;
2504 }
2505
2506 int64_t result = a.ConstantValue() - b.ConstantValue();
2507
2508 return RangeBoundary::FromConstant(result);
2509 }
2510
2511
2512 bool RangeBoundary::SymbolicAdd(const RangeBoundary& a,
2513 const RangeBoundary& b,
2514 RangeBoundary* result) {
2515 if (a.IsSymbol() && b.IsConstant()) {
2516 if (Utils::WillAddOverflow(a.offset(), b.ConstantValue())) {
2517 return false;
2518 }
2519
2520 const int64_t offset = a.offset() + b.ConstantValue();
2521
2522 *result = RangeBoundary::FromDefinition(a.symbol(), offset);
2523 return true;
2524 } else if (b.IsSymbol() && a.IsConstant()) {
2525 return SymbolicAdd(b, a, result);
2526 }
2527 return false;
2528 }
2529
2530
2531 bool RangeBoundary::SymbolicSub(const RangeBoundary& a,
2532 const RangeBoundary& b,
2533 RangeBoundary* result) {
2534 if (a.IsSymbol() && b.IsConstant()) {
2535 if (Utils::WillSubOverflow(a.offset(), b.ConstantValue())) {
2536 return false;
2537 }
2538
2539 const int64_t offset = a.offset() - b.ConstantValue();
2540
2541 *result = RangeBoundary::FromDefinition(a.symbol(), offset);
2542 return true;
2543 }
2544 return false;
2545 }
2546
2547
2478 static Definition* UnwrapConstraint(Definition* defn) { 2548 static Definition* UnwrapConstraint(Definition* defn) {
2479 while (defn->IsConstraint()) { 2549 while (defn->IsConstraint()) {
2480 defn = defn->AsConstraint()->value()->definition(); 2550 defn = defn->AsConstraint()->value()->definition();
2481 } 2551 }
2482 return defn; 2552 return defn;
2483 } 2553 }
2484 2554
2485 2555
2486 static bool AreEqualDefinitions(Definition* a, Definition* b) { 2556 static bool AreEqualDefinitions(Definition* a, Definition* b) {
2487 a = UnwrapConstraint(a); 2557 a = UnwrapConstraint(a);
2488 b = UnwrapConstraint(b); 2558 b = UnwrapConstraint(b);
2489 return (a == b) || 2559 return (a == b) ||
2490 (a->AllowsCSE() && 2560 (a->AllowsCSE() &&
2491 a->Dependencies().IsNone() && 2561 a->Dependencies().IsNone() &&
2492 b->AllowsCSE() && 2562 b->AllowsCSE() &&
2493 b->Dependencies().IsNone() && 2563 b->Dependencies().IsNone() &&
2494 a->Equals(b)); 2564 a->Equals(b));
2495 } 2565 }
2496 2566
2497 2567
2498 // Returns true if two range boundaries refer to the same symbol. 2568 // Returns true if two range boundaries refer to the same symbol.
2499 static bool DependOnSameSymbol(const RangeBoundary& a, const RangeBoundary& b) { 2569 static bool DependOnSameSymbol(const RangeBoundary& a, const RangeBoundary& b) {
2500 return a.IsSymbol() && b.IsSymbol() && 2570 return a.IsSymbol() && b.IsSymbol() &&
2501 AreEqualDefinitions(a.symbol(), b.symbol()); 2571 AreEqualDefinitions(a.symbol(), b.symbol());
2502 } 2572 }
2503 2573
2504 2574
2505 // Returns true if range has a least specific minimum value. 2575 bool RangeBoundary::Equals(const RangeBoundary& other) const {
2506 static bool IsMinSmi(Range* range) { 2576 if (IsConstant() && other.IsConstant()) {
2507 return (range == NULL) || 2577 return ConstantValue() == other.ConstantValue();
2508 (range->min().IsConstant() && 2578 } else if (IsInfinity() && other.IsInfinity()) {
2509 (range->min().value() <= Smi::kMinValue)); 2579 return kind() == other.kind();
2580 } else if (IsSymbol() && other.IsSymbol()) {
2581 return (offset() == other.offset()) && DependOnSameSymbol(*this, other);
2582 } else if (IsUnknown() && other.IsUnknown()) {
2583 return true;
2584 }
2585 return false;
2510 } 2586 }
2511 2587
2512 2588
2513 // Returns true if range has a least specific maximium value. 2589 RangeBoundary RangeBoundary::Shl(const RangeBoundary& value_boundary,
2514 static bool IsMaxSmi(Range* range) { 2590 int64_t shift_count,
2515 return (range == NULL) || 2591 const RangeBoundary& overflow) {
2516 (range->max().IsConstant() && 2592 ASSERT(value_boundary.IsConstant());
2517 (range->max().value() >= Smi::kMaxValue)); 2593 ASSERT(shift_count >= 0);
2518 } 2594 int64_t limit = 64 - shift_count;
2595 int64_t value = static_cast<int64_t>(value_boundary.ConstantValue());
2519 2596
2597 if ((value == 0) ||
2598 (shift_count == 0) ||
2599 ((limit > 0) && (Utils::IsInt(limit, value)))) {
2600 // Result stays in 64 bit range.
2601 int64_t result = value << shift_count;
2602 return Smi::IsValid64(result) ? RangeBoundary(result) : overflow;
2603 }
2520 2604
2521 // Returns true if two range boundaries can be proven to be equal. 2605 return overflow;
2522 static bool IsEqual(const RangeBoundary& a, const RangeBoundary& b) {
2523 if (a.IsConstant() && b.IsConstant()) {
2524 return a.value() == b.value();
2525 } else if (a.IsSymbol() && b.IsSymbol()) {
2526 return (a.offset() == b.offset()) && DependOnSameSymbol(a, b);
2527 } else {
2528 return false;
2529 }
2530 } 2606 }
2531 2607
2532 2608
2533 static RangeBoundary CanonicalizeBoundary(const RangeBoundary& a, 2609 static RangeBoundary CanonicalizeBoundary(const RangeBoundary& a,
2534 const RangeBoundary& overflow) { 2610 const RangeBoundary& overflow) {
2535 if (a.IsConstant() || a.IsNegativeInfinity() || a.IsPositiveInfinity()) { 2611 if (a.IsConstant() || a.IsInfinity()) {
2536 return a; 2612 return a;
2537 } 2613 }
2538 2614
2539 intptr_t offset = a.offset(); 2615 int64_t offset = a.offset();
2540 Definition* symbol = a.symbol(); 2616 Definition* symbol = a.symbol();
2541 2617
2542 bool changed; 2618 bool changed;
2543 do { 2619 do {
2544 changed = false; 2620 changed = false;
2545 if (symbol->IsConstraint()) { 2621 if (symbol->IsConstraint()) {
2546 symbol = symbol->AsConstraint()->value()->definition(); 2622 symbol = symbol->AsConstraint()->value()->definition();
2547 changed = true; 2623 changed = true;
2548 } else if (symbol->IsBinarySmiOp()) { 2624 } else if (symbol->IsBinarySmiOp()) {
2549 BinarySmiOpInstr* op = symbol->AsBinarySmiOp(); 2625 BinarySmiOpInstr* op = symbol->AsBinarySmiOp();
2550 Definition* left = op->left()->definition(); 2626 Definition* left = op->left()->definition();
2551 Definition* right = op->right()->definition(); 2627 Definition* right = op->right()->definition();
2552 switch (op->op_kind()) { 2628 switch (op->op_kind()) {
2553 case Token::kADD: 2629 case Token::kADD:
2554 if (right->IsConstant()) { 2630 if (right->IsConstant()) {
2555 offset += Smi::Cast(right->AsConstant()->value()).Value(); 2631 int64_t rhs = Smi::Cast(right->AsConstant()->value()).Value();
2632 if (Utils::WillAddOverflow(offset, rhs)) {
2633 return overflow;
2634 }
2635 offset += rhs;
2556 symbol = left; 2636 symbol = left;
2557 changed = true; 2637 changed = true;
2558 } else if (left->IsConstant()) { 2638 } else if (left->IsConstant()) {
2559 offset += Smi::Cast(left->AsConstant()->value()).Value(); 2639 int64_t rhs = Smi::Cast(left->AsConstant()->value()).Value();
2640 if (Utils::WillAddOverflow(offset, rhs)) {
2641 return overflow;
2642 }
2643 offset += rhs;
2560 symbol = right; 2644 symbol = right;
2561 changed = true; 2645 changed = true;
2562 } 2646 }
2563 break; 2647 break;
2564 2648
2565 case Token::kSUB: 2649 case Token::kSUB:
2566 if (right->IsConstant()) { 2650 if (right->IsConstant()) {
2567 offset -= Smi::Cast(right->AsConstant()->value()).Value(); 2651 int64_t rhs = Smi::Cast(right->AsConstant()->value()).Value();
2652 if (Utils::WillSubOverflow(offset, rhs)) {
2653 return overflow;
2654 }
2655 offset -= rhs;
2568 symbol = left; 2656 symbol = left;
2569 changed = true; 2657 changed = true;
2570 } 2658 }
2571 break; 2659 break;
2572 2660
2573 default: 2661 default:
2574 break; 2662 break;
2575 } 2663 }
2576 } 2664 }
2577
2578 if (!Smi::IsValid(offset)) return overflow;
2579 } while (changed); 2665 } while (changed);
2580 2666
2581 return RangeBoundary::FromDefinition(symbol, offset); 2667 return RangeBoundary::FromDefinition(symbol, offset);
2582 } 2668 }
2583 2669
2584 2670
2585 static bool CanonicalizeMaxBoundary(RangeBoundary* a) { 2671 static bool CanonicalizeMaxBoundary(RangeBoundary* a) {
2586 if (!a->IsSymbol()) return false; 2672 if (!a->IsSymbol()) return false;
2587 2673
2588 Range* range = a->symbol()->range(); 2674 Range* range = a->symbol()->range();
2589 if ((range == NULL) || !range->max().IsSymbol()) return false; 2675 if ((range == NULL) || !range->max().IsSymbol()) return false;
2590 2676
2591 const intptr_t offset = range->max().offset() + a->offset();
2592 2677
2593 if (!Smi::IsValid(offset)) { 2678 if (Utils::WillAddOverflow(range->max().offset(), a->offset())) {
2594 *a = RangeBoundary::PositiveInfinity(); 2679 *a = RangeBoundary::PositiveInfinity();
2595 return true; 2680 return true;
2596 } 2681 }
2597 2682
2683 const int64_t offset = range->max().offset() + a->offset();
2684
2685
2598 *a = CanonicalizeBoundary( 2686 *a = CanonicalizeBoundary(
2599 RangeBoundary::FromDefinition(range->max().symbol(), offset), 2687 RangeBoundary::FromDefinition(range->max().symbol(), offset),
2600 RangeBoundary::PositiveInfinity()); 2688 RangeBoundary::PositiveInfinity());
2601 2689
2602 return true; 2690 return true;
2603 } 2691 }
2604 2692
2605 2693
2606 static bool CanonicalizeMinBoundary(RangeBoundary* a) { 2694 static bool CanonicalizeMinBoundary(RangeBoundary* a) {
2607 if (!a->IsSymbol()) return false; 2695 if (!a->IsSymbol()) return false;
2608 2696
2609 Range* range = a->symbol()->range(); 2697 Range* range = a->symbol()->range();
2610 if ((range == NULL) || !range->min().IsSymbol()) return false; 2698 if ((range == NULL) || !range->min().IsSymbol()) return false;
2611 2699
2612 const intptr_t offset = range->min().offset() + a->offset(); 2700 if (Utils::WillAddOverflow(range->min().offset(), a->offset())) {
2613 if (!Smi::IsValid(offset)) {
2614 *a = RangeBoundary::NegativeInfinity(); 2701 *a = RangeBoundary::NegativeInfinity();
2615 return true; 2702 return true;
2616 } 2703 }
2617 2704
2705 const int64_t offset = range->min().offset() + a->offset();
2706
2618 *a = CanonicalizeBoundary( 2707 *a = CanonicalizeBoundary(
2619 RangeBoundary::FromDefinition(range->min().symbol(), offset), 2708 RangeBoundary::FromDefinition(range->min().symbol(), offset),
2620 RangeBoundary::NegativeInfinity()); 2709 RangeBoundary::NegativeInfinity());
2621 2710
2622 return true; 2711 return true;
2623 } 2712 }
2624 2713
2625 2714
2626 RangeBoundary RangeBoundary::Min(RangeBoundary a, RangeBoundary b) { 2715 RangeBoundary RangeBoundary::Min(RangeBoundary a, RangeBoundary b,
2716 RangeSize size) {
2717 ASSERT(!(a.IsNegativeInfinity() || b.IsNegativeInfinity()));
2718 ASSERT(!a.IsUnknown() || !b.IsUnknown());
2719 if (a.IsUnknown() && !b.IsUnknown()) {
2720 return b;
2721 }
2722 if (!a.IsUnknown() && b.IsUnknown()) {
2723 return a;
2724 }
2725 if (size == kRangeBoundarySmi) {
2726 if (a.IsSmiMaximumOrAbove() && !b.IsSmiMaximumOrAbove()) {
2727 return b;
2728 }
2729 if (!a.IsSmiMaximumOrAbove() && b.IsSmiMaximumOrAbove()) {
2730 return a;
2731 }
2732 } else {
2733 ASSERT(size == kRangeBoundaryInt64);
2734 if (a.IsMaximumOrAbove() && !b.IsMaximumOrAbove()) {
2735 return b;
2736 }
2737 if (!a.IsMaximumOrAbove() && b.IsMaximumOrAbove()) {
2738 return a;
2739 }
2740 }
2741
2742 if (a.Equals(b)) {
2743 return b;
2744 }
2745
2746 {
2747 RangeBoundary canonical_a =
2748 CanonicalizeBoundary(a, RangeBoundary::PositiveInfinity());
2749 RangeBoundary canonical_b =
2750 CanonicalizeBoundary(b, RangeBoundary::PositiveInfinity());
2751 do {
2752 if (DependOnSameSymbol(canonical_a, canonical_b)) {
2753 a = canonical_a;
2754 b = canonical_b;
2755 break;
2756 }
2757 } while (CanonicalizeMaxBoundary(&canonical_a) ||
2758 CanonicalizeMaxBoundary(&canonical_b));
2759 }
2760
2627 if (DependOnSameSymbol(a, b)) { 2761 if (DependOnSameSymbol(a, b)) {
2628 return (a.offset() <= b.offset()) ? a : b; 2762 return (a.offset() <= b.offset()) ? a : b;
2629 } 2763 }
2630 2764
2631 const intptr_t min_a = a.LowerBound().Clamp().value(); 2765 const int64_t min_a = a.UpperBound().Clamp(size).ConstantValue();
2632 const intptr_t min_b = b.LowerBound().Clamp().value(); 2766 const int64_t min_b = b.UpperBound().Clamp(size).ConstantValue();
2633 2767
2634 return RangeBoundary::FromConstant(Utils::Minimum(min_a, min_b)); 2768 return RangeBoundary::FromConstant(Utils::Minimum(min_a, min_b));
2635 } 2769 }
2636 2770
2637 2771
2638 RangeBoundary RangeBoundary::Max(RangeBoundary a, RangeBoundary b) { 2772 RangeBoundary RangeBoundary::Max(RangeBoundary a, RangeBoundary b,
2639 if (DependOnSameSymbol(a, b)) { 2773 RangeSize size) {
2640 return (a.offset() >= b.offset()) ? a : b; 2774 ASSERT(!(a.IsPositiveInfinity() || b.IsPositiveInfinity()));
2775 ASSERT(!a.IsUnknown() || !b.IsUnknown());
2776 if (a.IsUnknown() && !b.IsUnknown()) {
2777 return b;
2778 }
2779 if (!a.IsUnknown() && b.IsUnknown()) {
2780 return a;
2781 }
2782 if (size == kRangeBoundarySmi) {
2783 if (a.IsSmiMinimumOrBelow() && !b.IsSmiMinimumOrBelow()) {
2784 return b;
2785 }
2786 if (!a.IsSmiMinimumOrBelow() && b.IsSmiMinimumOrBelow()) {
2787 return a;
2788 }
2789 } else {
2790 ASSERT(size == kRangeBoundaryInt64);
2791 if (a.IsMinimumOrBelow() && !b.IsMinimumOrBelow()) {
2792 return b;
2793 }
2794 if (!a.IsMinimumOrBelow() && b.IsMinimumOrBelow()) {
2795 return a;
2796 }
2797 }
2798 if (a.Equals(b)) {
2799 return b;
2641 } 2800 }
2642 2801
2643 const intptr_t max_a = a.UpperBound().Clamp().value(); 2802 {
2644 const intptr_t max_b = b.UpperBound().Clamp().value(); 2803 RangeBoundary canonical_a =
2804 CanonicalizeBoundary(a, RangeBoundary::NegativeInfinity());
2805 RangeBoundary canonical_b =
2806 CanonicalizeBoundary(b, RangeBoundary::NegativeInfinity());
2807
2808 do {
2809 if (DependOnSameSymbol(canonical_a, canonical_b)) {
2810 a = canonical_a;
2811 b = canonical_b;
2812 break;
2813 }
2814 } while (CanonicalizeMinBoundary(&canonical_a) ||
2815 CanonicalizeMinBoundary(&canonical_b));
2816 }
2817
2818 if (DependOnSameSymbol(a, b)) {
2819 return (a.offset() <= b.offset()) ? b : a;
2820 }
2821
2822 const int64_t max_a = a.LowerBound().Clamp(size).ConstantValue();
2823 const int64_t max_b = b.LowerBound().Clamp(size).ConstantValue();
2645 2824
2646 return RangeBoundary::FromConstant(Utils::Maximum(max_a, max_b)); 2825 return RangeBoundary::FromConstant(Utils::Maximum(max_a, max_b));
2647 } 2826 }
2648 2827
2649 2828
2829 int64_t RangeBoundary::ConstantValue() const {
2830 ASSERT(IsConstant());
2831 return value_;
2832 }
2833
2834
2650 void Definition::InferRange() { 2835 void Definition::InferRange() {
2651 ASSERT(Type()->ToCid() == kSmiCid); // Has meaning only for smis. 2836 if (Type()->ToCid() == kSmiCid) {
2652 if (range_ == NULL) { 2837 if (range_ == NULL) {
2653 range_ = Range::Unknown(); 2838 range_ = Range::UnknownSmi();
2839 }
2840 } else if (IsMintDefinition()) {
2841 if (range_ == NULL) {
2842 range_ = Range::Unknown();
2843 }
2844 } else {
2845 // Only Smi and Mint supported.
2846 UNREACHABLE();
2654 } 2847 }
2655 } 2848 }
2656 2849
2657 2850
2658 void ConstantInstr::InferRange() { 2851 void ConstantInstr::InferRange() {
2659 ASSERT(value_.IsSmi()); 2852 if (value_.IsSmi()) {
2660 if (range_ == NULL) { 2853 if (range_ == NULL) {
2661 intptr_t value = Smi::Cast(value_).Value(); 2854 int64_t value = Smi::Cast(value_).Value();
2662 range_ = new Range(RangeBoundary::FromConstant(value), 2855 range_ = new Range(RangeBoundary::FromConstant(value),
2663 RangeBoundary::FromConstant(value)); 2856 RangeBoundary::FromConstant(value));
2857 }
2858 } else if (value_.IsMint()) {
2859 if (range_ == NULL) {
2860 int64_t value = Mint::Cast(value_).value();
2861 range_ = new Range(RangeBoundary::FromConstant(value),
2862 RangeBoundary::FromConstant(value));
2863 }
2864 } else {
2865 // Only Smi and Mint supported.
2866 UNREACHABLE();
2664 } 2867 }
2665 } 2868 }
2666 2869
2870
2871 void UnboxIntegerInstr::InferRange() {
2872 if (range_ == NULL) {
2873 Definition* unboxed = value()->definition();
2874 ASSERT(unboxed != NULL);
2875 Range* range = unboxed->range();
2876 if (range == NULL) {
2877 range_ = Range::Unknown();
2878 return;
2879 }
2880 range_ = new Range(range->min(), range->max());
2881 }
2882 }
2883
2667 2884
2668 void ConstraintInstr::InferRange() { 2885 void ConstraintInstr::InferRange() {
2669 Range* value_range = value()->definition()->range(); 2886 Range* value_range = value()->definition()->range();
2670 2887
2888 // Only constraining smi values.
2889 ASSERT(value()->IsSmiValue());
2890
2671 RangeBoundary min; 2891 RangeBoundary min;
2672 RangeBoundary max; 2892 RangeBoundary max;
2673 2893
2674 if (IsMinSmi(value_range) && !IsMinSmi(constraint())) { 2894 {
2675 min = constraint()->min(); 2895 RangeBoundary value_min = (value_range == NULL) ?
2676 } else if (IsMinSmi(constraint()) && !IsMinSmi(value_range)) { 2896 RangeBoundary() : value_range->min();
2677 min = value_range->min(); 2897 RangeBoundary constraint_min = constraint()->min();
2678 } else if ((value_range != NULL) && 2898 min = RangeBoundary::Max(value_min, constraint_min,
2679 IsEqual(constraint()->min(), value_range->min())) { 2899 RangeBoundary::kRangeBoundarySmi);
2680 min = constraint()->min();
2681 } else {
2682 if (value_range != NULL) {
2683 RangeBoundary canonical_a =
2684 CanonicalizeBoundary(constraint()->min(),
2685 RangeBoundary::NegativeInfinity());
2686 RangeBoundary canonical_b =
2687 CanonicalizeBoundary(value_range->min(),
2688 RangeBoundary::NegativeInfinity());
2689
2690 do {
2691 if (DependOnSameSymbol(canonical_a, canonical_b)) {
2692 min = (canonical_a.offset() <= canonical_b.offset()) ? canonical_b
2693 : canonical_a;
2694 }
2695 } while (CanonicalizeMinBoundary(&canonical_a) ||
2696 CanonicalizeMinBoundary(&canonical_b));
2697 }
2698
2699 if (min.IsUnknown()) {
2700 min = RangeBoundary::Max(Range::ConstantMin(value_range),
2701 Range::ConstantMin(constraint()));
2702 }
2703 } 2900 }
2704 2901
2705 if (IsMaxSmi(value_range) && !IsMaxSmi(constraint())) { 2902 ASSERT(!min.IsUnknown());
2706 max = constraint()->max();
2707 } else if (IsMaxSmi(constraint()) && !IsMaxSmi(value_range)) {
2708 max = value_range->max();
2709 } else if ((value_range != NULL) &&
2710 IsEqual(constraint()->max(), value_range->max())) {
2711 max = constraint()->max();
2712 } else {
2713 if (value_range != NULL) {
2714 RangeBoundary canonical_b =
2715 CanonicalizeBoundary(value_range->max(),
2716 RangeBoundary::PositiveInfinity());
2717 RangeBoundary canonical_a =
2718 CanonicalizeBoundary(constraint()->max(),
2719 RangeBoundary::PositiveInfinity());
2720 2903
2721 do { 2904 {
2722 if (DependOnSameSymbol(canonical_a, canonical_b)) { 2905 RangeBoundary value_max = (value_range == NULL) ?
2723 max = (canonical_a.offset() <= canonical_b.offset()) ? canonical_a 2906 RangeBoundary() : value_range->max();
2724 : canonical_b; 2907 RangeBoundary constraint_max = constraint()->max();
2725 break; 2908 max = RangeBoundary::Min(value_max, constraint_max,
2726 } 2909 RangeBoundary::kRangeBoundarySmi);
2727 } while (CanonicalizeMaxBoundary(&canonical_a) || 2910 }
2728 CanonicalizeMaxBoundary(&canonical_b));
2729 }
2730 2911
2731 if (max.IsUnknown()) { 2912 ASSERT(!max.IsUnknown());
2732 max = RangeBoundary::Min(Range::ConstantMax(value_range),
2733 Range::ConstantMax(constraint()));
2734 }
2735 }
2736 2913
2737 range_ = new Range(min, max); 2914 range_ = new Range(min, max);
2738 2915
2739 // Mark branches that generate unsatisfiable constraints as constant. 2916 // Mark branches that generate unsatisfiable constraints as constant.
2740 if (target() != NULL && range_->IsUnsatisfiable()) { 2917 if (target() != NULL && range_->IsUnsatisfiable()) {
2741 BranchInstr* branch = 2918 BranchInstr* branch =
2742 target()->PredecessorAt(0)->last_instruction()->AsBranch(); 2919 target()->PredecessorAt(0)->last_instruction()->AsBranch();
2743 if (target() == branch->true_successor()) { 2920 if (target() == branch->true_successor()) {
2744 // True unreachable. 2921 // True unreachable.
2745 if (FLAG_trace_constant_propagation) { 2922 if (FLAG_trace_constant_propagation) {
(...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after
2798 RangeBoundary::FromConstant(255)); 2975 RangeBoundary::FromConstant(255));
2799 break; 2976 break;
2800 case kTypedDataInt16ArrayCid: 2977 case kTypedDataInt16ArrayCid:
2801 range_ = new Range(RangeBoundary::FromConstant(-32768), 2978 range_ = new Range(RangeBoundary::FromConstant(-32768),
2802 RangeBoundary::FromConstant(32767)); 2979 RangeBoundary::FromConstant(32767));
2803 break; 2980 break;
2804 case kTypedDataUint16ArrayCid: 2981 case kTypedDataUint16ArrayCid:
2805 range_ = new Range(RangeBoundary::FromConstant(0), 2982 range_ = new Range(RangeBoundary::FromConstant(0),
2806 RangeBoundary::FromConstant(65535)); 2983 RangeBoundary::FromConstant(65535));
2807 break; 2984 break;
2985 case kTypedDataInt32ArrayCid:
2986 if (CanDeoptimize()) {
2987 range_ = Range::UnknownSmi();
2988 } else {
2989 range_ = new Range(RangeBoundary::FromConstant(kMinInt32),
2990 RangeBoundary::FromConstant(kMaxInt32));
2991 }
2992 break;
2993 case kTypedDataUint32ArrayCid:
2994 if (CanDeoptimize()) {
2995 range_ = Range::UnknownSmi();
2996 } else {
2997 range_ = new Range(RangeBoundary::FromConstant(0),
2998 RangeBoundary::FromConstant(kMaxUint32));
2999 }
3000 break;
2808 case kOneByteStringCid: 3001 case kOneByteStringCid:
2809 range_ = new Range(RangeBoundary::FromConstant(0), 3002 range_ = new Range(RangeBoundary::FromConstant(0),
2810 RangeBoundary::FromConstant(0xFF)); 3003 RangeBoundary::FromConstant(0xFF));
2811 break; 3004 break;
2812 case kTwoByteStringCid: 3005 case kTwoByteStringCid:
2813 range_ = new Range(RangeBoundary::FromConstant(0), 3006 range_ = new Range(RangeBoundary::FromConstant(0),
2814 RangeBoundary::FromConstant(0xFFFF)); 3007 RangeBoundary::FromConstant(0xFFFF));
2815 break; 3008 break;
2816 default: 3009 default:
2817 Definition::InferRange(); 3010 Definition::InferRange();
(...skipping 98 matching lines...) Expand 10 before | Expand all | Expand 10 after
2916 return false; 3109 return false;
2917 } 3110 }
2918 return is_smi_result; 3111 return is_smi_result;
2919 } 3112 }
2920 3113
2921 3114
2922 void PhiInstr::InferRange() { 3115 void PhiInstr::InferRange() {
2923 RangeBoundary new_min; 3116 RangeBoundary new_min;
2924 RangeBoundary new_max; 3117 RangeBoundary new_max;
2925 3118
3119 ASSERT(Type()->ToCid() == kSmiCid);
3120
2926 for (intptr_t i = 0; i < InputCount(); i++) { 3121 for (intptr_t i = 0; i < InputCount(); i++) {
2927 Range* input_range = InputAt(i)->definition()->range(); 3122 Range* input_range = InputAt(i)->definition()->range();
2928 if (input_range == NULL) { 3123 if (input_range == NULL) {
2929 range_ = Range::Unknown(); 3124 range_ = Range::UnknownSmi();
2930 return; 3125 return;
2931 } 3126 }
2932 3127
2933 if (new_min.IsUnknown()) { 3128 if (new_min.IsUnknown()) {
2934 new_min = Range::ConstantMin(input_range); 3129 new_min = Range::ConstantMin(input_range);
2935 } else { 3130 } else {
2936 new_min = RangeBoundary::Min(new_min, Range::ConstantMin(input_range)); 3131 new_min = RangeBoundary::Min(new_min,
3132 Range::ConstantMinSmi(input_range),
3133 RangeBoundary::kRangeBoundarySmi);
2937 } 3134 }
2938 3135
2939 if (new_max.IsUnknown()) { 3136 if (new_max.IsUnknown()) {
2940 new_max = Range::ConstantMax(input_range); 3137 new_max = Range::ConstantMax(input_range);
2941 } else { 3138 } else {
2942 new_max = RangeBoundary::Max(new_max, Range::ConstantMax(input_range)); 3139 new_max = RangeBoundary::Max(new_max,
3140 Range::ConstantMaxSmi(input_range),
3141 RangeBoundary::kRangeBoundarySmi);
2943 } 3142 }
2944 } 3143 }
2945 3144
2946 ASSERT(new_min.IsUnknown() == new_max.IsUnknown()); 3145 ASSERT(new_min.IsUnknown() == new_max.IsUnknown());
2947 if (new_min.IsUnknown()) { 3146 if (new_min.IsUnknown()) {
2948 range_ = Range::Unknown(); 3147 range_ = Range::UnknownSmi();
2949 return; 3148 return;
2950 } 3149 }
2951 3150
2952 range_ = new Range(new_min, new_max); 3151 range_ = new Range(new_min, new_max);
2953 } 3152 }
2954 3153
2955 3154
2956 bool PhiInstr::IsRedundant() const { 3155 bool PhiInstr::IsRedundant() const {
2957 ASSERT(InputCount() > 1); 3156 ASSERT(InputCount() > 1);
2958 Definition* first = InputAt(0)->definition(); 3157 Definition* first = InputAt(0)->definition();
2959 for (intptr_t i = 1; i < InputCount(); ++i) { 3158 for (intptr_t i = 1; i < InputCount(); ++i) {
2960 Definition* def = InputAt(i)->definition(); 3159 Definition* def = InputAt(i)->definition();
2961 if (def != first) return false; 3160 if (def != first) return false;
2962 } 3161 }
2963 return true; 3162 return true;
2964 } 3163 }
2965 3164
2966 3165
2967 static bool SymbolicSub(const RangeBoundary& a,
2968 const RangeBoundary& b,
2969 RangeBoundary* result) {
2970 if (a.IsSymbol() && b.IsConstant() && !b.Overflowed()) {
2971 const intptr_t offset = a.offset() - b.value();
2972 if (!Smi::IsValid(offset)) return false;
2973
2974 *result = RangeBoundary::FromDefinition(a.symbol(), offset);
2975 return true;
2976 }
2977 return false;
2978 }
2979
2980
2981 static bool SymbolicAdd(const RangeBoundary& a,
2982 const RangeBoundary& b,
2983 RangeBoundary* result) {
2984 if (a.IsSymbol() && b.IsConstant() && !b.Overflowed()) {
2985 const intptr_t offset = a.offset() + b.value();
2986 if (!Smi::IsValid(offset)) return false;
2987
2988 *result = RangeBoundary::FromDefinition(a.symbol(), offset);
2989 return true;
2990 } else if (b.IsSymbol() && a.IsConstant() && !a.Overflowed()) {
2991 const intptr_t offset = b.offset() + a.value();
2992 if (!Smi::IsValid(offset)) return false;
2993
2994 *result = RangeBoundary::FromDefinition(b.symbol(), offset);
2995 return true;
2996 }
2997 return false;
2998 }
2999
3000
3001 static bool IsArrayLength(Definition* defn) { 3166 static bool IsArrayLength(Definition* defn) {
3167 if (defn == NULL) {
3168 return false;
3169 }
3002 LoadFieldInstr* load = defn->AsLoadField(); 3170 LoadFieldInstr* load = defn->AsLoadField();
3003 return (load != NULL) && load->IsImmutableLengthLoad(); 3171 return (load != NULL) && load->IsImmutableLengthLoad();
3004 } 3172 }
3005 3173
3006 3174
3007 static int64_t ConstantAbsMax(const Range* range) {
3008 if (range == NULL) return Smi::kMaxValue;
3009 const int64_t abs_min = Utils::Abs(Range::ConstantMin(range).value());
3010 const int64_t abs_max = Utils::Abs(Range::ConstantMax(range).value());
3011 return abs_min > abs_max ? abs_min : abs_max;
3012 }
3013
3014
3015 static bool OnlyPositiveOrZero(const Range* a, const Range* b) {
3016 if ((a == NULL) || (b == NULL)) return false;
3017 if (Range::ConstantMin(a).value() < 0) return false;
3018 if (Range::ConstantMin(b).value() < 0) return false;
3019 return true;
3020 }
3021
3022
3023 static bool OnlyNegativeOrZero(const Range* a, const Range* b) {
3024 if ((a == NULL) || (b == NULL)) return false;
3025 if (Range::ConstantMax(a).value() > 0) return false;
3026 if (Range::ConstantMax(b).value() > 0) return false;
3027 return true;
3028 }
3029
3030
3031 void BinarySmiOpInstr::InferRange() { 3175 void BinarySmiOpInstr::InferRange() {
3032 // TODO(vegorov): canonicalize BinarySmiOp to always have constant on the 3176 // TODO(vegorov): canonicalize BinarySmiOp to always have constant on the
3033 // right and a non-constant on the left. 3177 // right and a non-constant on the left.
3034 Definition* left_defn = left()->definition(); 3178 Definition* left_defn = left()->definition();
3035 3179
3036 Range* left_range = left_defn->range(); 3180 Range* left_range = left_defn->range();
3037 Range* right_range = right()->definition()->range(); 3181 Range* right_range = right()->definition()->range();
3038 3182
3039 if ((left_range == NULL) || (right_range == NULL)) { 3183 if ((left_range == NULL) || (right_range == NULL)) {
3040 range_ = new Range(RangeBoundary::MinSmi(), RangeBoundary::MaxSmi()); 3184 range_ = Range::UnknownSmi();
3041 return; 3185 return;
3042 } 3186 }
3043 3187
3044 RangeBoundary left_min = 3188 Range* possible_range = Range::BinaryOp(op_kind(),
3045 IsArrayLength(left_defn) ? 3189 left_range,
3046 RangeBoundary::FromDefinition(left_defn) : left_range->min(); 3190 right_range,
3191 left_defn);
3047 3192
3048 RangeBoundary left_max = 3193 if ((range_ == NULL) && (possible_range == NULL)) {
3049 IsArrayLength(left_defn) ? 3194 // Initialize.
3050 RangeBoundary::FromDefinition(left_defn) : left_range->max(); 3195 range_ = Range::UnknownSmi();
3051 3196 return;
3052 RangeBoundary min;
3053 RangeBoundary max;
3054 switch (op_kind()) {
3055 case Token::kADD:
3056 if (!SymbolicAdd(left_min, right_range->min(), &min)) {
3057 min =
3058 RangeBoundary::Add(Range::ConstantMin(left_range),
3059 Range::ConstantMin(right_range),
3060 RangeBoundary::NegativeInfinity());
3061 }
3062
3063 if (!SymbolicAdd(left_max, right_range->max(), &max)) {
3064 max =
3065 RangeBoundary::Add(Range::ConstantMax(right_range),
3066 Range::ConstantMax(left_range),
3067 RangeBoundary::PositiveInfinity());
3068 }
3069 break;
3070
3071 case Token::kSUB:
3072 if (!SymbolicSub(left_min, right_range->max(), &min)) {
3073 min =
3074 RangeBoundary::Sub(Range::ConstantMin(left_range),
3075 Range::ConstantMax(right_range),
3076 RangeBoundary::NegativeInfinity());
3077 }
3078
3079 if (!SymbolicSub(left_max, right_range->min(), &max)) {
3080 max =
3081 RangeBoundary::Sub(Range::ConstantMax(left_range),
3082 Range::ConstantMin(right_range),
3083 RangeBoundary::PositiveInfinity());
3084 }
3085 break;
3086
3087 case Token::kMUL: {
3088 const int64_t left_max = ConstantAbsMax(left_range);
3089 const int64_t right_max = ConstantAbsMax(right_range);
3090 ASSERT(left_max <= -kSmiMin);
3091 ASSERT(right_max <= -kSmiMin);
3092 if ((left_max == 0) || (right_max <= kMaxInt64 / left_max)) {
3093 // Product of left and right max values stays in 64 bit range.
3094 const int64_t result_max = left_max * right_max;
3095 if (Smi::IsValid64(result_max) && Smi::IsValid64(-result_max)) {
3096 const intptr_t r_min =
3097 OnlyPositiveOrZero(left_range, right_range) ? 0 : -result_max;
3098 min = RangeBoundary::FromConstant(r_min);
3099 const intptr_t r_max =
3100 OnlyNegativeOrZero(left_range, right_range) ? 0 : result_max;
3101 max = RangeBoundary::FromConstant(r_max);
3102 break;
3103 }
3104 }
3105 if (range_ == NULL) {
3106 range_ = Range::Unknown();
3107 }
3108 return;
3109 }
3110 case Token::kSHL: {
3111 Range::Shl(left_range, right_range, &min, &max);
3112 break;
3113 }
3114 case Token::kBIT_AND:
3115 if (Range::ConstantMin(right_range).value() >= 0) {
3116 min = RangeBoundary::FromConstant(0);
3117 max = Range::ConstantMax(right_range);
3118 break;
3119 }
3120 if (Range::ConstantMin(left_range).value() >= 0) {
3121 min = RangeBoundary::FromConstant(0);
3122 max = Range::ConstantMax(left_range);
3123 break;
3124 }
3125
3126 if (range_ == NULL) {
3127 range_ = Range::Unknown();
3128 }
3129 return;
3130
3131 default:
3132 if (range_ == NULL) {
3133 range_ = Range::Unknown();
3134 }
3135 return;
3136 } 3197 }
3137 3198
3138 ASSERT(!min.IsUnknown() && !max.IsUnknown()); 3199 if (possible_range == NULL) {
3139 set_overflow(min.LowerBound().Overflowed() || max.UpperBound().Overflowed()); 3200 // Nothing new.
3201 return;
3202 }
3140 3203
3141 if (min.IsConstant()) min.Clamp(); 3204 range_ = possible_range;
3142 if (max.IsConstant()) max.Clamp();
3143 3205
3144 range_ = new Range(min, max); 3206 ASSERT(!range_->min().IsUnknown() && !range_->max().IsUnknown());
3207 // Calculate overflowed status before clamping.
3208 const bool overflowed = range_->min().LowerBound().OverflowedSmi() ||
3209 range_->max().UpperBound().OverflowedSmi();
3210
3211 // Clamp value to be within smi range.
3212 range_->Clamp(RangeBoundary::kRangeBoundarySmi);
3213
3214 set_overflow(overflowed);
3145 } 3215 }
3146 3216
3147 3217
3218 void BinaryMintOpInstr::InferRange() {
3219 // TODO(vegorov): canonicalize BinaryMintOpInstr to always have constant on
3220 // the right and a non-constant on the left.
3221 Definition* left_defn = left()->definition();
3222
3223 Range* left_range = left_defn->range();
3224 Range* right_range = right()->definition()->range();
3225
3226 if ((left_range == NULL) || (right_range == NULL)) {
3227 range_ = Range::Unknown();
3228 return;
3229 }
3230
3231 Range* possible_range = Range::BinaryOp(op_kind(),
3232 left_range,
3233 right_range,
3234 left_defn);
3235
3236 if ((range_ == NULL) && (possible_range == NULL)) {
3237 // Initialize.
3238 range_ = Range::Unknown();
3239 return;
3240 }
3241
3242 if (possible_range == NULL) {
3243 // Nothing new.
3244 return;
3245 }
3246
3247 range_ = possible_range;
3248
3249 ASSERT(!range_->min().IsUnknown() && !range_->max().IsUnknown());
3250
3251 // Clamp value to be within mint range.
3252 range_->Clamp(RangeBoundary::kRangeBoundaryInt64);
3253 }
3254
3255
3148 bool Range::IsPositive() const { 3256 bool Range::IsPositive() const {
3149 if (min().IsNegativeInfinity()) { 3257 if (min().IsNegativeInfinity()) {
3150 return false; 3258 return false;
3151 } 3259 }
3152 if (min().LowerBound().value() < 0) { 3260 if (min().LowerBound().ConstantValue() < 0) {
3153 return false; 3261 return false;
3154 } 3262 }
3155 if (max().IsPositiveInfinity()) { 3263 if (max().IsPositiveInfinity()) {
3156 return true; 3264 return true;
3157 } 3265 }
3158 return max().UpperBound().value() >= 0; 3266 return max().UpperBound().ConstantValue() >= 0;
3159 } 3267 }
3160 3268
3161 3269
3162 bool Range::IsNegative() const { 3270 bool Range::OnlyLessThanOrEqualTo(int64_t val) const {
3163 if (max().IsPositiveInfinity()) {
3164 return false;
3165 }
3166 if (max().UpperBound().value() >= 0) {
3167 return false;
3168 }
3169 if (min().IsNegativeInfinity()) {
3170 return true;
3171 }
3172 return min().LowerBound().value() < 0;
3173 }
3174
3175
3176 bool Range::OnlyLessThanOrEqualTo(intptr_t val) const {
3177 if (max().IsPositiveInfinity()) { 3271 if (max().IsPositiveInfinity()) {
3178 // Cannot be true. 3272 // Cannot be true.
3179 return false; 3273 return false;
3180 } 3274 }
3181 if (max().UpperBound().value() > val) { 3275 if (max().UpperBound().ConstantValue() > val) {
3182 // Not true. 3276 // Not true.
3183 return false; 3277 return false;
3184 } 3278 }
3185 if (!min().IsNegativeInfinity()) { 3279 return true;
3186 if (min().LowerBound().value() > val) { 3280 }
3187 // Lower bound is > value. 3281
3188 return false; 3282
3189 } 3283 bool Range::OnlyGreaterThanOrEqualTo(int64_t val) const {
3284 if (min().IsNegativeInfinity()) {
3285 return false;
3286 }
3287 if (min().LowerBound().ConstantValue() < val) {
3288 return false;
3190 } 3289 }
3191 return true; 3290 return true;
3192 } 3291 }
3193 3292
3194 3293
3195 // Inclusive. 3294 // Inclusive.
3196 bool Range::IsWithin(intptr_t min_int, intptr_t max_int) const { 3295 bool Range::IsWithin(int64_t min_int, int64_t max_int) const {
3197 RangeBoundary lower_min = min().LowerBound(); 3296 RangeBoundary lower_min = min().LowerBound();
3198 if (lower_min.IsNegativeInfinity() || (lower_min.value() < min_int)) { 3297 if (lower_min.IsNegativeInfinity() || (lower_min.ConstantValue() < min_int)) {
3199 return false; 3298 return false;
3200 } 3299 }
3201 RangeBoundary upper_max = max().UpperBound(); 3300 RangeBoundary upper_max = max().UpperBound();
3202 if (upper_max.IsPositiveInfinity() || (upper_max.value() > max_int)) { 3301 if (upper_max.IsPositiveInfinity() || (upper_max.ConstantValue() > max_int)) {
3203 return false; 3302 return false;
3204 } 3303 }
3205 return true; 3304 return true;
3206 } 3305 }
3207 3306
3208 3307
3209 bool Range::Overlaps(intptr_t min_int, intptr_t max_int) const { 3308 bool Range::Overlaps(int64_t min_int, int64_t max_int) const {
3210 const intptr_t this_min = min().IsNegativeInfinity() ? 3309 RangeBoundary lower = min().LowerBound();
3211 kIntptrMin : min().LowerBound().value(); 3310 RangeBoundary upper = max().UpperBound();
3212 const intptr_t this_max = max().IsPositiveInfinity() ? 3311 const int64_t this_min = lower.IsNegativeInfinity() ?
3213 kIntptrMax : max().UpperBound().value(); 3312 RangeBoundary::kMin : lower.ConstantValue();
3313 const int64_t this_max = upper.IsPositiveInfinity() ?
3314 RangeBoundary::kMax : upper.ConstantValue();
3214 if ((this_min <= min_int) && (min_int <= this_max)) return true; 3315 if ((this_min <= min_int) && (min_int <= this_max)) return true;
3215 if ((this_min <= max_int) && (max_int <= this_max)) return true; 3316 if ((this_min <= max_int) && (max_int <= this_max)) return true;
3216 if ((min_int < this_min) && (max_int > this_max)) return true; 3317 if ((min_int < this_min) && (max_int > this_max)) return true;
3217 return false; 3318 return false;
3218 } 3319 }
3219 3320
3220 3321
3221 bool Range::IsUnsatisfiable() const { 3322 bool Range::IsUnsatisfiable() const {
3222 // Infinity case: [+inf, ...] || [..., -inf] 3323 // Infinity case: [+inf, ...] || [..., -inf]
3223 if (min().IsPositiveInfinity() || max().IsNegativeInfinity()) { 3324 if (min().IsPositiveInfinity() || max().IsNegativeInfinity()) {
3224 return true; 3325 return true;
3225 } 3326 }
3226 // Constant case: For example [0, -1]. 3327 // Constant case: For example [0, -1].
3227 if (Range::ConstantMin(this).value() > Range::ConstantMax(this).value()) { 3328 if (Range::ConstantMin(this).ConstantValue() >
3329 Range::ConstantMax(this).ConstantValue()) {
3228 return true; 3330 return true;
3229 } 3331 }
3230 // Symbol case: For example [v+1, v]. 3332 // Symbol case: For example [v+1, v].
3231 if (DependOnSameSymbol(min(), max()) && min().offset() > max().offset()) { 3333 if (DependOnSameSymbol(min(), max()) && min().offset() > max().offset()) {
3232 return true; 3334 return true;
3233 } 3335 }
3234 return false; 3336 return false;
3235 } 3337 }
3236 3338
3237 3339
3238 void Range::Shl(Range* left, 3340 void Range::Clamp(RangeBoundary::RangeSize size) {
3239 Range* right, 3341 min_ = min_.Clamp(size);
3342 max_ = max_.Clamp(size);
3343 }
3344
3345
3346 void Range::Shl(const Range* left,
3347 const Range* right,
3240 RangeBoundary* result_min, 3348 RangeBoundary* result_min,
3241 RangeBoundary* result_max) { 3349 RangeBoundary* result_max) {
3350 ASSERT(left != NULL);
3351 ASSERT(right != NULL);
3352 ASSERT(result_min != NULL);
3353 ASSERT(result_max != NULL);
3242 RangeBoundary left_max = Range::ConstantMax(left); 3354 RangeBoundary left_max = Range::ConstantMax(left);
3243 RangeBoundary left_min = Range::ConstantMin(left); 3355 RangeBoundary left_min = Range::ConstantMin(left);
3244 // A negative shift count always deoptimizes (and throws), so the minimum 3356 // A negative shift count always deoptimizes (and throws), so the minimum
3245 // shift count is zero. 3357 // shift count is zero.
3246 intptr_t right_max = Utils::Maximum(Range::ConstantMax(right).value(), 3358 int64_t right_max = Utils::Maximum(Range::ConstantMax(right).ConstantValue(),
3247 static_cast<intptr_t>(0)); 3359 static_cast<int64_t>(0));
3248 intptr_t right_min = Utils::Maximum(Range::ConstantMin(right).value(), 3360 int64_t right_min = Utils::Maximum(Range::ConstantMin(right).ConstantValue(),
3249 static_cast<intptr_t>(0)); 3361 static_cast<int64_t>(0));
3250 3362
3251 *result_min = RangeBoundary::Shl( 3363 *result_min = RangeBoundary::Shl(
3252 left_min, 3364 left_min,
3253 left_min.value() > 0 ? right_min : right_max, 3365 left_min.ConstantValue() > 0 ? right_min : right_max,
3254 left_min.value() > 0 3366 left_min.ConstantValue() > 0
3255 ? RangeBoundary::PositiveInfinity() 3367 ? RangeBoundary::PositiveInfinity()
3256 : RangeBoundary::NegativeInfinity()); 3368 : RangeBoundary::NegativeInfinity());
3257 3369
3258 *result_max = RangeBoundary::Shl( 3370 *result_max = RangeBoundary::Shl(
3259 left_max, 3371 left_max,
3260 left_max.value() > 0 ? right_max : right_min, 3372 left_max.ConstantValue() > 0 ? right_max : right_min,
3261 left_max.value() > 0 3373 left_max.ConstantValue() > 0
3262 ? RangeBoundary::PositiveInfinity() 3374 ? RangeBoundary::PositiveInfinity()
3263 : RangeBoundary::NegativeInfinity()); 3375 : RangeBoundary::NegativeInfinity());
3264 } 3376 }
3265 3377
3266 3378
3379 bool Range::And(const Range* left_range,
3380 const Range* right_range,
3381 RangeBoundary* result_min,
3382 RangeBoundary* result_max) {
3383 ASSERT(left_range != NULL);
3384 ASSERT(right_range != NULL);
3385 ASSERT(result_min != NULL);
3386 ASSERT(result_max != NULL);
3387
3388 if (Range::ConstantMin(right_range).ConstantValue() >= 0) {
3389 *result_min = RangeBoundary::FromConstant(0);
3390 *result_max = Range::ConstantMax(right_range);
3391 return true;
3392 }
3393
3394 if (Range::ConstantMin(left_range).ConstantValue() >= 0) {
3395 *result_min = RangeBoundary::FromConstant(0);
3396 *result_max = Range::ConstantMax(left_range);
3397 return true;
3398 }
3399
3400 return false;
3401 }
3402
3403
3404 void Range::Add(const Range* left_range,
3405 const Range* right_range,
3406 RangeBoundary* result_min,
3407 RangeBoundary* result_max,
3408 Definition* left_defn) {
3409 ASSERT(left_range != NULL);
3410 ASSERT(right_range != NULL);
3411 ASSERT(result_min != NULL);
3412 ASSERT(result_max != NULL);
3413
3414 RangeBoundary left_min =
3415 IsArrayLength(left_defn) ?
3416 RangeBoundary::FromDefinition(left_defn) : left_range->min();
3417
3418 RangeBoundary left_max =
3419 IsArrayLength(left_defn) ?
3420 RangeBoundary::FromDefinition(left_defn) : left_range->max();
3421
3422 if (!RangeBoundary::SymbolicAdd(left_min, right_range->min(), result_min)) {
3423 *result_min = RangeBoundary::Add(left_range->min().LowerBound(),
3424 right_range->min().LowerBound(),
3425 RangeBoundary::NegativeInfinity());
3426 }
3427 if (!RangeBoundary::SymbolicAdd(left_max, right_range->max(), result_max)) {
3428 *result_max = RangeBoundary::Add(right_range->max().UpperBound(),
3429 left_range->max().UpperBound(),
3430 RangeBoundary::PositiveInfinity());
3431 }
3432 }
3433
3434
3435 void Range::Sub(const Range* left_range,
3436 const Range* right_range,
3437 RangeBoundary* result_min,
3438 RangeBoundary* result_max,
3439 Definition* left_defn) {
3440 ASSERT(left_range != NULL);
3441 ASSERT(right_range != NULL);
3442 ASSERT(result_min != NULL);
3443 ASSERT(result_max != NULL);
3444
3445 RangeBoundary left_min =
3446 IsArrayLength(left_defn) ?
3447 RangeBoundary::FromDefinition(left_defn) : left_range->min();
3448
3449 RangeBoundary left_max =
3450 IsArrayLength(left_defn) ?
3451 RangeBoundary::FromDefinition(left_defn) : left_range->max();
3452
3453 if (!RangeBoundary::SymbolicSub(left_min, right_range->max(), result_min)) {
3454 *result_min = RangeBoundary::Sub(left_range->min().LowerBound(),
3455 right_range->max().UpperBound(),
3456 RangeBoundary::NegativeInfinity());
3457 }
3458 if (!RangeBoundary::SymbolicSub(left_max, right_range->min(), result_max)) {
3459 *result_max = RangeBoundary::Sub(left_range->max().UpperBound(),
3460 right_range->min().LowerBound(),
3461 RangeBoundary::PositiveInfinity());
3462 }
3463 }
3464
3465
3466 bool Range::Mul(const Range* left_range,
3467 const Range* right_range,
3468 RangeBoundary* result_min,
3469 RangeBoundary* result_max) {
3470 ASSERT(left_range != NULL);
3471 ASSERT(right_range != NULL);
3472 ASSERT(result_min != NULL);
3473 ASSERT(result_max != NULL);
3474
3475 const int64_t left_max = ConstantAbsMax(left_range);
3476 const int64_t right_max = ConstantAbsMax(right_range);
3477 if ((left_max <= -kSmiMin) && (right_max <= -kSmiMin) &&
3478 ((left_max == 0) || (right_max <= kMaxInt64 / left_max))) {
3479 // Product of left and right max values stays in 64 bit range.
3480 const int64_t mul_max = left_max * right_max;
3481 if (Smi::IsValid64(mul_max) && Smi::IsValid64(-mul_max)) {
3482 const intptr_t r_min =
3483 OnlyPositiveOrZero(*left_range, *right_range) ? 0 : -mul_max;
3484 *result_min = RangeBoundary::FromConstant(r_min);
3485 const intptr_t r_max =
3486 OnlyNegativeOrZero(*left_range, *right_range) ? 0 : mul_max;
3487 *result_max = RangeBoundary::FromConstant(r_max);
3488 return true;
3489 }
3490 }
3491 return false;
3492 }
3493
3494
3495 // Both the a and b ranges are >= 0.
3496 bool Range::OnlyPositiveOrZero(const Range& a, const Range& b) {
3497 return a.OnlyGreaterThanOrEqualTo(0) && b.OnlyGreaterThanOrEqualTo(0);
3498 }
3499
3500
3501 // Both the a and b ranges are <= 0.
3502 bool Range::OnlyNegativeOrZero(const Range& a, const Range& b) {
3503 return a.OnlyLessThanOrEqualTo(0) && b.OnlyLessThanOrEqualTo(0);
3504 }
3505
3506
3507 // Return the maximum absolute value included in range.
3508 int64_t Range::ConstantAbsMax(const Range* range) {
3509 if (range == NULL) {
3510 return RangeBoundary::kMax;
3511 }
3512 const int64_t abs_min = Utils::Abs(Range::ConstantMin(range).ConstantValue());
3513 const int64_t abs_max = Utils::Abs(Range::ConstantMax(range).ConstantValue());
3514 return Utils::Maximum(abs_min, abs_max);
3515 }
3516
3517
3518 Range* Range::BinaryOp(const Token::Kind op,
3519 const Range* left_range,
3520 const Range* right_range,
3521 Definition* left_defn) {
3522 ASSERT(left_range != NULL);
3523 ASSERT(right_range != NULL);
3524
3525 // Both left and right ranges are finite.
3526 ASSERT(left_range->IsFinite());
3527 ASSERT(right_range->IsFinite());
3528
3529 RangeBoundary min;
3530 RangeBoundary max;
3531 ASSERT(min.IsUnknown() && max.IsUnknown());
3532
3533 switch (op) {
3534 case Token::kADD:
3535 Range::Add(left_range, right_range, &min, &max, left_defn);
3536 break;
3537 case Token::kSUB:
3538 Range::Sub(left_range, right_range, &min, &max, left_defn);
3539 break;
3540 case Token::kMUL: {
3541 if (!Range::Mul(left_range, right_range, &min, &max)) {
3542 return NULL;
3543 }
3544 break;
3545 }
3546 case Token::kSHL: {
3547 Range::Shl(left_range, right_range, &min, &max);
3548 break;
3549 }
3550 case Token::kBIT_AND:
3551 if (!Range::And(left_range, right_range, &min, &max)) {
3552 return NULL;
3553 }
3554 break;
3555 default:
3556 return NULL;
3557 break;
3558 }
3559
3560 ASSERT(!min.IsUnknown() && !max.IsUnknown());
3561
3562 return new Range(min, max);
3563 }
3564
3565
3267 bool CheckArrayBoundInstr::IsFixedLengthArrayType(intptr_t cid) { 3566 bool CheckArrayBoundInstr::IsFixedLengthArrayType(intptr_t cid) {
3268 return LoadFieldInstr::IsFixedLengthArrayCid(cid); 3567 return LoadFieldInstr::IsFixedLengthArrayCid(cid);
3269 } 3568 }
3270 3569
3271 3570
3272 bool CheckArrayBoundInstr::IsRedundant(RangeBoundary length) { 3571 bool CheckArrayBoundInstr::IsRedundant(RangeBoundary length) {
3273 Range* index_range = index()->definition()->range(); 3572 Range* index_range = index()->definition()->range();
3274 3573
3275 // Range of the index is unknown can't decide if the check is redundant. 3574 // Range of the index is unknown can't decide if the check is redundant.
3276 if (index_range == NULL) { 3575 if (index_range == NULL) {
3277 return false; 3576 return false;
3278 } 3577 }
3279 3578
3280 // Range of the index is not positive. Check can't be redundant. 3579 // Range of the index is not positive. Check can't be redundant.
3281 if (Range::ConstantMin(index_range).value() < 0) { 3580 if (Range::ConstantMinSmi(index_range).ConstantValue() < 0) {
3282 return false; 3581 return false;
3283 } 3582 }
3284 3583
3285 RangeBoundary max = CanonicalizeBoundary(index_range->max(), 3584 RangeBoundary max = CanonicalizeBoundary(index_range->max(),
3286 RangeBoundary::PositiveInfinity()); 3585 RangeBoundary::PositiveInfinity());
3287 3586
3288 if (max.Overflowed()) { 3587 if (max.OverflowedSmi()) {
3289 return false; 3588 return false;
3290 } 3589 }
3291 3590
3292 3591
3293 RangeBoundary max_upper = max.UpperBound(); 3592 RangeBoundary max_upper = max.UpperBound();
3294 RangeBoundary length_lower = length.LowerBound(); 3593 RangeBoundary length_lower = length.LowerBound();
3295 3594
3296 if (max_upper.Overflowed() || length_lower.Overflowed()) { 3595 if (max_upper.OverflowedSmi() || length_lower.OverflowedSmi()) {
3297 return false; 3596 return false;
3298 } 3597 }
3299 3598
3300 // Try to compare constant boundaries. 3599 // Try to compare constant boundaries.
3301 if (max_upper.value() < length_lower.value()) { 3600 if (max_upper.ConstantValue() < length_lower.ConstantValue()) {
3302 return true; 3601 return true;
3303 } 3602 }
3304 3603
3305 length = CanonicalizeBoundary(length, RangeBoundary::PositiveInfinity()); 3604 length = CanonicalizeBoundary(length, RangeBoundary::PositiveInfinity());
3306 if (length.Overflowed()) { 3605 if (length.OverflowedSmi()) {
3307 return false; 3606 return false;
3308 } 3607 }
3309 3608
3310 // Try symbolic comparison. 3609 // Try symbolic comparison.
3311 do { 3610 do {
3312 if (DependOnSameSymbol(max, length)) return max.offset() < length.offset(); 3611 if (DependOnSameSymbol(max, length)) return max.offset() < length.offset();
3313 } while (CanonicalizeMaxBoundary(&max) || CanonicalizeMinBoundary(&length)); 3612 } while (CanonicalizeMaxBoundary(&max) || CanonicalizeMinBoundary(&length));
3314 3613
3315 // Failed to prove that maximum is bounded with array length. 3614 // Failed to prove that maximum is bounded with array length.
3316 return false; 3615 return false;
(...skipping 272 matching lines...) Expand 10 before | Expand all | Expand 10 after
3589 case Token::kTRUNCDIV: return 0; 3888 case Token::kTRUNCDIV: return 0;
3590 case Token::kMOD: return 1; 3889 case Token::kMOD: return 1;
3591 default: UNIMPLEMENTED(); return -1; 3890 default: UNIMPLEMENTED(); return -1;
3592 } 3891 }
3593 } 3892 }
3594 3893
3595 3894
3596 #undef __ 3895 #undef __
3597 3896
3598 } // namespace dart 3897 } // namespace dart
OLDNEW
« no previous file with comments | « runtime/vm/intermediate_language.h ('k') | runtime/vm/intermediate_language_test.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698