OLD | NEW |
1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2014, 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/flow_graph_range_analysis.h" | 5 #include "vm/flow_graph_range_analysis.h" |
6 | 6 |
7 #include "vm/bit_vector.h" | 7 #include "vm/bit_vector.h" |
8 #include "vm/il_printer.h" | 8 #include "vm/il_printer.h" |
9 | 9 |
10 namespace dart { | 10 namespace dart { |
(...skipping 2522 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2533 ASSERT(right_range != NULL); | 2533 ASSERT(right_range != NULL); |
2534 ASSERT(result_min != NULL); | 2534 ASSERT(result_min != NULL); |
2535 ASSERT(result_max != NULL); | 2535 ASSERT(result_max != NULL); |
2536 | 2536 |
2537 const int64_t left_max = ConstantAbsMax(left_range); | 2537 const int64_t left_max = ConstantAbsMax(left_range); |
2538 const int64_t right_max = ConstantAbsMax(right_range); | 2538 const int64_t right_max = ConstantAbsMax(right_range); |
2539 if ((left_max <= -kSmiMin) && (right_max <= -kSmiMin) && | 2539 if ((left_max <= -kSmiMin) && (right_max <= -kSmiMin) && |
2540 ((left_max == 0) || (right_max <= kMaxInt64 / left_max))) { | 2540 ((left_max == 0) || (right_max <= kMaxInt64 / left_max))) { |
2541 // Product of left and right max values stays in 64 bit range. | 2541 // Product of left and right max values stays in 64 bit range. |
2542 const int64_t mul_max = left_max * right_max; | 2542 const int64_t mul_max = left_max * right_max; |
2543 const int64_t r_min = | 2543 if (OnlyPositiveOrZero(*left_range, *right_range) || |
2544 OnlyPositiveOrZero(*left_range, *right_range) ? 0 : -mul_max; | 2544 OnlyNegativeOrZero(*left_range, *right_range)) { |
2545 *result_min = RangeBoundary::FromConstant(r_min); | 2545 // If both ranges are of the same sign then the range of the result |
2546 const int64_t r_max = | 2546 // is positive and is between multiplications of absolute minimums |
2547 OnlyNegativeOrZero(*left_range, *right_range) ? 0 : mul_max; | 2547 // and absolute maximums. |
2548 *result_max = RangeBoundary::FromConstant(r_max); | 2548 const int64_t mul_min = |
| 2549 ConstantAbsMin(left_range) * ConstantAbsMin(right_range); |
| 2550 *result_min = RangeBoundary::FromConstant(mul_min); |
| 2551 *result_max = RangeBoundary::FromConstant(mul_max); |
| 2552 } else { |
| 2553 // If ranges have mixed signs then use conservative approximation: |
| 2554 // absolute value of the result is less or equal to multiplication |
| 2555 // of absolute maximums. |
| 2556 *result_min = RangeBoundary::FromConstant(-mul_max); |
| 2557 *result_max = RangeBoundary::FromConstant(mul_max); |
| 2558 } |
2549 return; | 2559 return; |
2550 } | 2560 } |
2551 | 2561 |
2552 // TODO(vegorov): handle mixed sign case that leads to (-Infinity, 0] range. | 2562 // TODO(vegorov): handle mixed sign case that leads to (-Infinity, 0] range. |
2553 if (OnlyPositiveOrZero(*left_range, *right_range) || | 2563 if (OnlyPositiveOrZero(*left_range, *right_range) || |
2554 OnlyNegativeOrZero(*left_range, *right_range)) { | 2564 OnlyNegativeOrZero(*left_range, *right_range)) { |
2555 *result_min = RangeBoundary::FromConstant(0); | 2565 *result_min = RangeBoundary::FromConstant(0); |
2556 *result_max = RangeBoundary::PositiveInfinity(); | 2566 *result_max = RangeBoundary::PositiveInfinity(); |
2557 return; | 2567 return; |
2558 } | 2568 } |
(...skipping 19 matching lines...) Expand all Loading... |
2578 int64_t Range::ConstantAbsMax(const Range* range) { | 2588 int64_t Range::ConstantAbsMax(const Range* range) { |
2579 if (range == NULL) { | 2589 if (range == NULL) { |
2580 return RangeBoundary::kMax; | 2590 return RangeBoundary::kMax; |
2581 } | 2591 } |
2582 const int64_t abs_min = Utils::Abs(Range::ConstantMin(range).ConstantValue()); | 2592 const int64_t abs_min = Utils::Abs(Range::ConstantMin(range).ConstantValue()); |
2583 const int64_t abs_max = Utils::Abs(Range::ConstantMax(range).ConstantValue()); | 2593 const int64_t abs_max = Utils::Abs(Range::ConstantMax(range).ConstantValue()); |
2584 return Utils::Maximum(abs_min, abs_max); | 2594 return Utils::Maximum(abs_min, abs_max); |
2585 } | 2595 } |
2586 | 2596 |
2587 | 2597 |
| 2598 // Return the minimum absolute value included in range. |
| 2599 int64_t Range::ConstantAbsMin(const Range* range) { |
| 2600 if (range == NULL) { |
| 2601 return 0; |
| 2602 } |
| 2603 const int64_t abs_min = Utils::Abs(Range::ConstantMin(range).ConstantValue()); |
| 2604 const int64_t abs_max = Utils::Abs(Range::ConstantMax(range).ConstantValue()); |
| 2605 return Utils::Minimum(abs_min, abs_max); |
| 2606 } |
| 2607 |
| 2608 |
2588 void Range::BinaryOp(const Token::Kind op, | 2609 void Range::BinaryOp(const Token::Kind op, |
2589 const Range* left_range, | 2610 const Range* left_range, |
2590 const Range* right_range, | 2611 const Range* right_range, |
2591 Definition* left_defn, | 2612 Definition* left_defn, |
2592 Range* result) { | 2613 Range* result) { |
2593 ASSERT(left_range != NULL); | 2614 ASSERT(left_range != NULL); |
2594 ASSERT(right_range != NULL); | 2615 ASSERT(right_range != NULL); |
2595 | 2616 |
2596 // Both left and right ranges are finite. | 2617 // Both left and right ranges are finite. |
2597 ASSERT(left_range->IsFinite()); | 2618 ASSERT(left_range->IsFinite()); |
(...skipping 530 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3128 } | 3149 } |
3129 } while (CanonicalizeMaxBoundary(&max) || | 3150 } while (CanonicalizeMaxBoundary(&max) || |
3130 CanonicalizeMinBoundary(&canonical_length)); | 3151 CanonicalizeMinBoundary(&canonical_length)); |
3131 | 3152 |
3132 // Failed to prove that maximum is bounded with array length. | 3153 // Failed to prove that maximum is bounded with array length. |
3133 return false; | 3154 return false; |
3134 } | 3155 } |
3135 | 3156 |
3136 | 3157 |
3137 } // namespace dart | 3158 } // namespace dart |
OLD | NEW |