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 2384 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2395 *result_min = RangeBoundary::Shr( | 2395 *result_min = RangeBoundary::Shr( |
2396 left_min, | 2396 left_min, |
2397 left_min.ConstantValue() > 0 ? right_max : right_min); | 2397 left_min.ConstantValue() > 0 ? right_max : right_min); |
2398 | 2398 |
2399 *result_max = RangeBoundary::Shr( | 2399 *result_max = RangeBoundary::Shr( |
2400 left_max, | 2400 left_max, |
2401 left_max.ConstantValue() > 0 ? right_min : right_max); | 2401 left_max.ConstantValue() > 0 ? right_min : right_max); |
2402 } | 2402 } |
2403 | 2403 |
2404 | 2404 |
2405 bool Range::And(const Range* left_range, | 2405 void Range::And(const Range* left_range, |
2406 const Range* right_range, | 2406 const Range* right_range, |
2407 RangeBoundary* result_min, | 2407 RangeBoundary* result_min, |
2408 RangeBoundary* result_max) { | 2408 RangeBoundary* result_max) { |
2409 ASSERT(left_range != NULL); | 2409 ASSERT(left_range != NULL); |
2410 ASSERT(right_range != NULL); | 2410 ASSERT(right_range != NULL); |
2411 ASSERT(result_min != NULL); | 2411 ASSERT(result_min != NULL); |
2412 ASSERT(result_max != NULL); | 2412 ASSERT(result_max != NULL); |
2413 | 2413 |
2414 if (Range::ConstantMin(right_range).ConstantValue() >= 0) { | 2414 if (Range::ConstantMin(right_range).ConstantValue() >= 0) { |
2415 *result_min = RangeBoundary::FromConstant(0); | 2415 *result_min = RangeBoundary::FromConstant(0); |
2416 *result_max = Range::ConstantMax(right_range); | 2416 *result_max = Range::ConstantMax(right_range); |
2417 return true; | 2417 return; |
2418 } | 2418 } |
2419 | 2419 |
2420 if (Range::ConstantMin(left_range).ConstantValue() >= 0) { | 2420 if (Range::ConstantMin(left_range).ConstantValue() >= 0) { |
2421 *result_min = RangeBoundary::FromConstant(0); | 2421 *result_min = RangeBoundary::FromConstant(0); |
2422 *result_max = Range::ConstantMax(left_range); | 2422 *result_max = Range::ConstantMax(left_range); |
2423 return true; | 2423 return; |
2424 } | 2424 } |
2425 | 2425 |
2426 return false; | 2426 *result_min = RangeBoundary::MinConstant(RangeBoundary::kRangeBoundaryInt64); |
| 2427 *result_max = RangeBoundary::MaxConstant(RangeBoundary::kRangeBoundaryInt64); |
2427 } | 2428 } |
2428 | 2429 |
2429 | 2430 |
2430 static int BitSize(const Range* range) { | 2431 static int BitSize(const Range* range) { |
2431 const int64_t min = Range::ConstantMin(range).ConstantValue(); | 2432 const int64_t min = Range::ConstantMin(range).ConstantValue(); |
2432 const int64_t max = Range::ConstantMax(range).ConstantValue(); | 2433 const int64_t max = Range::ConstantMax(range).ConstantValue(); |
2433 return Utils::Maximum(Utils::BitLength(min), Utils::BitLength(max)); | 2434 return Utils::Maximum(Utils::BitLength(min), Utils::BitLength(max)); |
2434 } | 2435 } |
2435 | 2436 |
2436 | 2437 |
(...skipping 80 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2517 RangeBoundary::NegativeInfinity()); | 2518 RangeBoundary::NegativeInfinity()); |
2518 } | 2519 } |
2519 if (!RangeBoundary::SymbolicSub(left_max, right_range->min(), result_max)) { | 2520 if (!RangeBoundary::SymbolicSub(left_max, right_range->min(), result_max)) { |
2520 *result_max = RangeBoundary::Sub(left_range->max().UpperBound(), | 2521 *result_max = RangeBoundary::Sub(left_range->max().UpperBound(), |
2521 right_range->min().LowerBound(), | 2522 right_range->min().LowerBound(), |
2522 RangeBoundary::PositiveInfinity()); | 2523 RangeBoundary::PositiveInfinity()); |
2523 } | 2524 } |
2524 } | 2525 } |
2525 | 2526 |
2526 | 2527 |
2527 bool Range::Mul(const Range* left_range, | 2528 void Range::Mul(const Range* left_range, |
2528 const Range* right_range, | 2529 const Range* right_range, |
2529 RangeBoundary* result_min, | 2530 RangeBoundary* result_min, |
2530 RangeBoundary* result_max) { | 2531 RangeBoundary* result_max) { |
2531 ASSERT(left_range != NULL); | 2532 ASSERT(left_range != NULL); |
2532 ASSERT(right_range != NULL); | 2533 ASSERT(right_range != NULL); |
2533 ASSERT(result_min != NULL); | 2534 ASSERT(result_min != NULL); |
2534 ASSERT(result_max != NULL); | 2535 ASSERT(result_max != NULL); |
2535 | 2536 |
2536 const int64_t left_max = ConstantAbsMax(left_range); | 2537 const int64_t left_max = ConstantAbsMax(left_range); |
2537 const int64_t right_max = ConstantAbsMax(right_range); | 2538 const int64_t right_max = ConstantAbsMax(right_range); |
2538 if ((left_max <= -kSmiMin) && (right_max <= -kSmiMin) && | 2539 if ((left_max <= -kSmiMin) && (right_max <= -kSmiMin) && |
2539 ((left_max == 0) || (right_max <= kMaxInt64 / left_max))) { | 2540 ((left_max == 0) || (right_max <= kMaxInt64 / left_max))) { |
2540 // 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. |
2541 const int64_t mul_max = left_max * right_max; | 2542 const int64_t mul_max = left_max * right_max; |
2542 const int64_t r_min = | 2543 const int64_t r_min = |
2543 OnlyPositiveOrZero(*left_range, *right_range) ? 0 : -mul_max; | 2544 OnlyPositiveOrZero(*left_range, *right_range) ? 0 : -mul_max; |
2544 *result_min = RangeBoundary::FromConstant(r_min); | 2545 *result_min = RangeBoundary::FromConstant(r_min); |
2545 const int64_t r_max = | 2546 const int64_t r_max = |
2546 OnlyNegativeOrZero(*left_range, *right_range) ? 0 : mul_max; | 2547 OnlyNegativeOrZero(*left_range, *right_range) ? 0 : mul_max; |
2547 *result_max = RangeBoundary::FromConstant(r_max); | 2548 *result_max = RangeBoundary::FromConstant(r_max); |
2548 return true; | 2549 return; |
2549 } | 2550 } |
2550 | 2551 |
2551 // TODO(vegorov): handle mixed sign case that leads to (-Infinity, 0] range. | 2552 // TODO(vegorov): handle mixed sign case that leads to (-Infinity, 0] range. |
2552 if (OnlyPositiveOrZero(*left_range, *right_range) || | 2553 if (OnlyPositiveOrZero(*left_range, *right_range) || |
2553 OnlyNegativeOrZero(*left_range, *right_range)) { | 2554 OnlyNegativeOrZero(*left_range, *right_range)) { |
2554 *result_min = RangeBoundary::FromConstant(0); | 2555 *result_min = RangeBoundary::FromConstant(0); |
2555 *result_max = RangeBoundary::PositiveInfinity(); | 2556 *result_max = RangeBoundary::PositiveInfinity(); |
2556 return true; | 2557 return; |
2557 } | 2558 } |
2558 | 2559 |
2559 return false; | 2560 *result_min = RangeBoundary::NegativeInfinity(); |
| 2561 *result_max = RangeBoundary::PositiveInfinity(); |
2560 } | 2562 } |
2561 | 2563 |
2562 | 2564 |
2563 // Both the a and b ranges are >= 0. | 2565 // Both the a and b ranges are >= 0. |
2564 bool Range::OnlyPositiveOrZero(const Range& a, const Range& b) { | 2566 bool Range::OnlyPositiveOrZero(const Range& a, const Range& b) { |
2565 return a.OnlyGreaterThanOrEqualTo(0) && b.OnlyGreaterThanOrEqualTo(0); | 2567 return a.OnlyGreaterThanOrEqualTo(0) && b.OnlyGreaterThanOrEqualTo(0); |
2566 } | 2568 } |
2567 | 2569 |
2568 | 2570 |
2569 // Both the a and b ranges are <= 0. | 2571 // Both the a and b ranges are <= 0. |
(...skipping 26 matching lines...) Expand all Loading... |
2596 ASSERT(right_range->IsFinite()); | 2598 ASSERT(right_range->IsFinite()); |
2597 | 2599 |
2598 RangeBoundary min; | 2600 RangeBoundary min; |
2599 RangeBoundary max; | 2601 RangeBoundary max; |
2600 ASSERT(min.IsUnknown() && max.IsUnknown()); | 2602 ASSERT(min.IsUnknown() && max.IsUnknown()); |
2601 | 2603 |
2602 switch (op) { | 2604 switch (op) { |
2603 case Token::kADD: | 2605 case Token::kADD: |
2604 Range::Add(left_range, right_range, &min, &max, left_defn); | 2606 Range::Add(left_range, right_range, &min, &max, left_defn); |
2605 break; | 2607 break; |
| 2608 |
2606 case Token::kSUB: | 2609 case Token::kSUB: |
2607 Range::Sub(left_range, right_range, &min, &max, left_defn); | 2610 Range::Sub(left_range, right_range, &min, &max, left_defn); |
2608 break; | 2611 break; |
2609 case Token::kMUL: { | 2612 |
2610 if (!Range::Mul(left_range, right_range, &min, &max)) { | 2613 case Token::kMUL: |
2611 *result = Range::Full(RangeBoundary::kRangeBoundaryInt64); | 2614 Range::Mul(left_range, right_range, &min, &max); |
2612 return; | |
2613 } | |
2614 break; | 2615 break; |
2615 } | 2616 |
2616 case Token::kSHL: { | 2617 case Token::kSHL: |
2617 Range::Shl(left_range, right_range, &min, &max); | 2618 Range::Shl(left_range, right_range, &min, &max); |
2618 break; | 2619 break; |
2619 } | 2620 |
2620 case Token::kSHR: { | 2621 case Token::kSHR: |
2621 Range::Shr(left_range, right_range, &min, &max); | 2622 Range::Shr(left_range, right_range, &min, &max); |
2622 break; | 2623 break; |
2623 } | |
2624 | 2624 |
2625 case Token::kBIT_AND: | 2625 case Token::kBIT_AND: |
2626 if (!Range::And(left_range, right_range, &min, &max)) { | 2626 Range::And(left_range, right_range, &min, &max); |
2627 *result = Range::Full(RangeBoundary::kRangeBoundaryInt64); | |
2628 return; | |
2629 } | |
2630 break; | 2627 break; |
2631 | 2628 |
2632 case Token::kBIT_XOR: | 2629 case Token::kBIT_XOR: |
2633 Range::Xor(left_range, right_range, &min, &max); | 2630 Range::Xor(left_range, right_range, &min, &max); |
2634 break; | 2631 break; |
2635 | 2632 |
| 2633 case Token::kBIT_OR: |
| 2634 *result = Range::Full(RangeBoundary::kRangeBoundaryInt64); |
| 2635 return; |
| 2636 |
2636 default: | 2637 default: |
2637 *result = Range::Full(RangeBoundary::kRangeBoundaryInt64); | 2638 *result = Range(RangeBoundary::NegativeInfinity(), |
| 2639 RangeBoundary::PositiveInfinity()); |
2638 return; | 2640 return; |
2639 } | 2641 } |
2640 | 2642 |
2641 ASSERT(!min.IsUnknown() && !max.IsUnknown()); | 2643 ASSERT(!min.IsUnknown() && !max.IsUnknown()); |
2642 | 2644 |
2643 *result = Range(min, max); | 2645 *result = Range(min, max); |
2644 } | 2646 } |
2645 | 2647 |
2646 | 2648 |
2647 void Definition::set_range(const Range& range) { | 2649 void Definition::set_range(const Range& range) { |
(...skipping 478 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3126 } | 3128 } |
3127 } while (CanonicalizeMaxBoundary(&max) || | 3129 } while (CanonicalizeMaxBoundary(&max) || |
3128 CanonicalizeMinBoundary(&canonical_length)); | 3130 CanonicalizeMinBoundary(&canonical_length)); |
3129 | 3131 |
3130 // Failed to prove that maximum is bounded with array length. | 3132 // Failed to prove that maximum is bounded with array length. |
3131 return false; | 3133 return false; |
3132 } | 3134 } |
3133 | 3135 |
3134 | 3136 |
3135 } // namespace dart | 3137 } // namespace dart |
OLD | NEW |