OLD | NEW |
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 Loading... |
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 Loading... |
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 Loading... |
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 Loading... |
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 |
OLD | NEW |