| 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 #include "vm/unit_test.h" | 6 #include "vm/unit_test.h" |
| 7 | 7 |
| 8 namespace dart { | 8 namespace dart { |
| 9 | 9 |
| 10 TEST_CASE(RangeTests) { | 10 TEST_CASE(RangeTests) { |
| (...skipping 76 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 87 TEST_RANGE_OP(Range::Shr, -16, -8, 1, 2, RangeBoundary(-8), | 87 TEST_RANGE_OP(Range::Shr, -16, -8, 1, 2, RangeBoundary(-8), |
| 88 RangeBoundary(-2)); | 88 RangeBoundary(-2)); |
| 89 TEST_RANGE_OP(Range::Shr, 2, 4, -1, 1, RangeBoundary(1), RangeBoundary(4)); | 89 TEST_RANGE_OP(Range::Shr, 2, 4, -1, 1, RangeBoundary(1), RangeBoundary(4)); |
| 90 TEST_RANGE_OP(Range::Shr, kMaxInt64, kMaxInt64, 0, 1, | 90 TEST_RANGE_OP(Range::Shr, kMaxInt64, kMaxInt64, 0, 1, |
| 91 RangeBoundary(kMaxInt64 >> 1), RangeBoundary(kMaxInt64)); | 91 RangeBoundary(kMaxInt64 >> 1), RangeBoundary(kMaxInt64)); |
| 92 TEST_RANGE_OP(Range::Shr, kMinInt64, kMinInt64, 0, 1, | 92 TEST_RANGE_OP(Range::Shr, kMinInt64, kMinInt64, 0, 1, |
| 93 RangeBoundary(kMinInt64), RangeBoundary(kMinInt64 >> 1)); | 93 RangeBoundary(kMinInt64), RangeBoundary(kMinInt64 >> 1)); |
| 94 #undef TEST_RANGE_OP | 94 #undef TEST_RANGE_OP |
| 95 } | 95 } |
| 96 | 96 |
| 97 | |
| 98 TEST_CASE(RangeTestsInfinity) { | 97 TEST_CASE(RangeTestsInfinity) { |
| 99 // +/- inf overflowed. | 98 // +/- inf overflowed. |
| 100 EXPECT(RangeBoundary::NegativeInfinity().OverflowedSmi()); | 99 EXPECT(RangeBoundary::NegativeInfinity().OverflowedSmi()); |
| 101 EXPECT(RangeBoundary::PositiveInfinity().OverflowedSmi()); | 100 EXPECT(RangeBoundary::PositiveInfinity().OverflowedSmi()); |
| 102 | 101 |
| 103 EXPECT(RangeBoundary::NegativeInfinity().OverflowedMint()); | 102 EXPECT(RangeBoundary::NegativeInfinity().OverflowedMint()); |
| 104 EXPECT(RangeBoundary::PositiveInfinity().OverflowedMint()); | 103 EXPECT(RangeBoundary::PositiveInfinity().OverflowedMint()); |
| 105 | 104 |
| 106 Range* all = new Range(RangeBoundary::NegativeInfinity(), | 105 Range* all = new Range(RangeBoundary::NegativeInfinity(), |
| 107 RangeBoundary::PositiveInfinity()); | 106 RangeBoundary::PositiveInfinity()); |
| (...skipping 37 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 145 | 144 |
| 146 Range* unsatisfiable_right = new Range(RangeBoundary::PositiveInfinity(), | 145 Range* unsatisfiable_right = new Range(RangeBoundary::PositiveInfinity(), |
| 147 RangeBoundary::FromConstant(0)); | 146 RangeBoundary::FromConstant(0)); |
| 148 EXPECT(unsatisfiable_right->IsUnsatisfiable()); | 147 EXPECT(unsatisfiable_right->IsUnsatisfiable()); |
| 149 | 148 |
| 150 Range* unsatisfiable_left = new Range(RangeBoundary::FromConstant(0), | 149 Range* unsatisfiable_left = new Range(RangeBoundary::FromConstant(0), |
| 151 RangeBoundary::NegativeInfinity()); | 150 RangeBoundary::NegativeInfinity()); |
| 152 EXPECT(unsatisfiable_left->IsUnsatisfiable()); | 151 EXPECT(unsatisfiable_left->IsUnsatisfiable()); |
| 153 } | 152 } |
| 154 | 153 |
| 155 | |
| 156 TEST_CASE(RangeUtils) { | 154 TEST_CASE(RangeUtils) { |
| 157 // [-inf, +inf]. | 155 // [-inf, +inf]. |
| 158 const Range& range_0 = *(new Range(RangeBoundary::NegativeInfinity(), | 156 const Range& range_0 = *(new Range(RangeBoundary::NegativeInfinity(), |
| 159 RangeBoundary::PositiveInfinity())); | 157 RangeBoundary::PositiveInfinity())); |
| 160 // [-inf, -1]. | 158 // [-inf, -1]. |
| 161 const Range& range_a = *(new Range(RangeBoundary::NegativeInfinity(), | 159 const Range& range_a = *(new Range(RangeBoundary::NegativeInfinity(), |
| 162 RangeBoundary::FromConstant(-1))); | 160 RangeBoundary::FromConstant(-1))); |
| 163 // [-inf, 0]. | 161 // [-inf, 0]. |
| 164 const Range& range_b = *(new Range(RangeBoundary::NegativeInfinity(), | 162 const Range& range_b = *(new Range(RangeBoundary::NegativeInfinity(), |
| 165 RangeBoundary::FromConstant(0))); | 163 RangeBoundary::FromConstant(0))); |
| (...skipping 65 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 231 EXPECT(!RangeBoundary::NegativeInfinity().Equals( | 229 EXPECT(!RangeBoundary::NegativeInfinity().Equals( |
| 232 RangeBoundary::PositiveInfinity())); | 230 RangeBoundary::PositiveInfinity())); |
| 233 EXPECT(!RangeBoundary::FromConstant(1).Equals( | 231 EXPECT(!RangeBoundary::FromConstant(1).Equals( |
| 234 RangeBoundary::NegativeInfinity())); | 232 RangeBoundary::NegativeInfinity())); |
| 235 EXPECT(!RangeBoundary::FromConstant(1).Equals( | 233 EXPECT(!RangeBoundary::FromConstant(1).Equals( |
| 236 RangeBoundary::NegativeInfinity())); | 234 RangeBoundary::NegativeInfinity())); |
| 237 EXPECT(!RangeBoundary::FromConstant(2).Equals( | 235 EXPECT(!RangeBoundary::FromConstant(2).Equals( |
| 238 RangeBoundary::PositiveInfinity())); | 236 RangeBoundary::PositiveInfinity())); |
| 239 } | 237 } |
| 240 | 238 |
| 241 | |
| 242 TEST_CASE(RangeBinaryOp) { | 239 TEST_CASE(RangeBinaryOp) { |
| 243 Range* range_a = new Range(RangeBoundary::FromConstant(-1), | 240 Range* range_a = new Range(RangeBoundary::FromConstant(-1), |
| 244 RangeBoundary::PositiveInfinity()); | 241 RangeBoundary::PositiveInfinity()); |
| 245 range_a->Clamp(RangeBoundary::kRangeBoundaryInt64); | 242 range_a->Clamp(RangeBoundary::kRangeBoundaryInt64); |
| 246 EXPECT(range_a->min().ConstantValue() == -1); | 243 EXPECT(range_a->min().ConstantValue() == -1); |
| 247 EXPECT(range_a->max().ConstantValue() == RangeBoundary::kMax); | 244 EXPECT(range_a->max().ConstantValue() == RangeBoundary::kMax); |
| 248 Range* range_b = new Range(RangeBoundary::NegativeInfinity(), | 245 Range* range_b = new Range(RangeBoundary::NegativeInfinity(), |
| 249 RangeBoundary::FromConstant(1)); | 246 RangeBoundary::FromConstant(1)); |
| 250 range_b->Clamp(RangeBoundary::kRangeBoundaryInt64); | 247 range_b->Clamp(RangeBoundary::kRangeBoundaryInt64); |
| 251 EXPECT(range_b->min().ConstantValue() == RangeBoundary::kMin); | 248 EXPECT(range_b->min().ConstantValue() == RangeBoundary::kMin); |
| (...skipping 28 matching lines...) Expand all Loading... |
| 280 RangeBoundary::FromConstant(0xf)); | 277 RangeBoundary::FromConstant(0xf)); |
| 281 { | 278 { |
| 282 Range result; | 279 Range result; |
| 283 Range::BinaryOp(Token::kBIT_AND, range_e, range_f, NULL, &result); | 280 Range::BinaryOp(Token::kBIT_AND, range_e, range_f, NULL, &result); |
| 284 ASSERT(!Range::IsUnknown(&result)); | 281 ASSERT(!Range::IsUnknown(&result)); |
| 285 EXPECT(result.min().ConstantValue() == 0x0); | 282 EXPECT(result.min().ConstantValue() == 0x0); |
| 286 EXPECT(result.max().ConstantValue() == 0xf); | 283 EXPECT(result.max().ConstantValue() == 0xf); |
| 287 } | 284 } |
| 288 } | 285 } |
| 289 | 286 |
| 290 | |
| 291 TEST_CASE(RangeAdd) { | 287 TEST_CASE(RangeAdd) { |
| 292 #define TEST_RANGE_ADD(l_min, l_max, r_min, r_max, result_min, result_max) \ | 288 #define TEST_RANGE_ADD(l_min, l_max, r_min, r_max, result_min, result_max) \ |
| 293 { \ | 289 { \ |
| 294 RangeBoundary min, max; \ | 290 RangeBoundary min, max; \ |
| 295 Range* left_range = new Range(RangeBoundary::FromConstant(l_min), \ | 291 Range* left_range = new Range(RangeBoundary::FromConstant(l_min), \ |
| 296 RangeBoundary::FromConstant(l_max)); \ | 292 RangeBoundary::FromConstant(l_max)); \ |
| 297 Range* right_range = new Range(RangeBoundary::FromConstant(r_min), \ | 293 Range* right_range = new Range(RangeBoundary::FromConstant(r_min), \ |
| 298 RangeBoundary::FromConstant(r_max)); \ | 294 RangeBoundary::FromConstant(r_max)); \ |
| 299 EXPECT(left_range->min().ConstantValue() == l_min); \ | 295 EXPECT(left_range->min().ConstantValue() == l_min); \ |
| 300 EXPECT(left_range->max().ConstantValue() == l_max); \ | 296 EXPECT(left_range->max().ConstantValue() == l_max); \ |
| (...skipping 60 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 361 | 357 |
| 362 // [kMaxInt64, kMaxInt64] + [1, 1] = [-inf, +inf]. | 358 // [kMaxInt64, kMaxInt64] + [1, 1] = [-inf, +inf]. |
| 363 TEST_RANGE_ADD(static_cast<int64_t>(kMaxInt64), | 359 TEST_RANGE_ADD(static_cast<int64_t>(kMaxInt64), |
| 364 static_cast<int64_t>(kMaxInt64), static_cast<int64_t>(1), | 360 static_cast<int64_t>(kMaxInt64), static_cast<int64_t>(1), |
| 365 static_cast<int64_t>(1), RangeBoundary::NegativeInfinity(), | 361 static_cast<int64_t>(1), RangeBoundary::NegativeInfinity(), |
| 366 RangeBoundary::PositiveInfinity()); | 362 RangeBoundary::PositiveInfinity()); |
| 367 | 363 |
| 368 #undef TEST_RANGE_ADD | 364 #undef TEST_RANGE_ADD |
| 369 } | 365 } |
| 370 | 366 |
| 371 | |
| 372 TEST_CASE(RangeSub) { | 367 TEST_CASE(RangeSub) { |
| 373 #define TEST_RANGE_SUB(l_min, l_max, r_min, r_max, result_min, result_max) \ | 368 #define TEST_RANGE_SUB(l_min, l_max, r_min, r_max, result_min, result_max) \ |
| 374 { \ | 369 { \ |
| 375 RangeBoundary min, max; \ | 370 RangeBoundary min, max; \ |
| 376 Range* left_range = new Range(RangeBoundary::FromConstant(l_min), \ | 371 Range* left_range = new Range(RangeBoundary::FromConstant(l_min), \ |
| 377 RangeBoundary::FromConstant(l_max)); \ | 372 RangeBoundary::FromConstant(l_max)); \ |
| 378 Range* right_range = new Range(RangeBoundary::FromConstant(r_min), \ | 373 Range* right_range = new Range(RangeBoundary::FromConstant(r_min), \ |
| 379 RangeBoundary::FromConstant(r_max)); \ | 374 RangeBoundary::FromConstant(r_max)); \ |
| 380 EXPECT(left_range->min().ConstantValue() == l_min); \ | 375 EXPECT(left_range->min().ConstantValue() == l_min); \ |
| 381 EXPECT(left_range->max().ConstantValue() == l_max); \ | 376 EXPECT(left_range->max().ConstantValue() == l_max); \ |
| (...skipping 30 matching lines...) Expand all Loading... |
| 412 RangeBoundary::NegativeInfinity(), RangeBoundary::PositiveInfinity()); | 407 RangeBoundary::NegativeInfinity(), RangeBoundary::PositiveInfinity()); |
| 413 | 408 |
| 414 // [kMaxInt32 + 10, kMaxInt32 + 20] - [-20, -20] = | 409 // [kMaxInt32 + 10, kMaxInt32 + 20] - [-20, -20] = |
| 415 // [kMaxInt32 + 30, kMaxInt32 + 40]. | 410 // [kMaxInt32 + 30, kMaxInt32 + 40]. |
| 416 TEST_RANGE_SUB(static_cast<int64_t>(kMaxInt32) + 10, | 411 TEST_RANGE_SUB(static_cast<int64_t>(kMaxInt32) + 10, |
| 417 static_cast<int64_t>(kMaxInt32) + 20, | 412 static_cast<int64_t>(kMaxInt32) + 20, |
| 418 static_cast<int64_t>(-20), static_cast<int64_t>(-20), | 413 static_cast<int64_t>(-20), static_cast<int64_t>(-20), |
| 419 RangeBoundary(static_cast<int64_t>(kMaxInt32) + 30), | 414 RangeBoundary(static_cast<int64_t>(kMaxInt32) + 30), |
| 420 RangeBoundary(static_cast<int64_t>(kMaxInt32) + 40)); | 415 RangeBoundary(static_cast<int64_t>(kMaxInt32) + 40)); |
| 421 | 416 |
| 422 | |
| 423 #undef TEST_RANGE_SUB | 417 #undef TEST_RANGE_SUB |
| 424 } | 418 } |
| 425 | 419 |
| 426 | |
| 427 TEST_CASE(RangeAnd) { | 420 TEST_CASE(RangeAnd) { |
| 428 #define TEST_RANGE_AND(l_min, l_max, r_min, r_max, result_min, result_max) \ | 421 #define TEST_RANGE_AND(l_min, l_max, r_min, r_max, result_min, result_max) \ |
| 429 { \ | 422 { \ |
| 430 RangeBoundary min, max; \ | 423 RangeBoundary min, max; \ |
| 431 Range* left_range = new Range(RangeBoundary::FromConstant(l_min), \ | 424 Range* left_range = new Range(RangeBoundary::FromConstant(l_min), \ |
| 432 RangeBoundary::FromConstant(l_max)); \ | 425 RangeBoundary::FromConstant(l_max)); \ |
| 433 Range* right_range = new Range(RangeBoundary::FromConstant(r_min), \ | 426 Range* right_range = new Range(RangeBoundary::FromConstant(r_min), \ |
| 434 RangeBoundary::FromConstant(r_max)); \ | 427 RangeBoundary::FromConstant(r_max)); \ |
| 435 EXPECT(left_range->min().ConstantValue() == l_min); \ | 428 EXPECT(left_range->min().ConstantValue() == l_min); \ |
| 436 EXPECT(left_range->max().ConstantValue() == l_max); \ | 429 EXPECT(left_range->max().ConstantValue() == l_max); \ |
| (...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 471 RangeBoundary(static_cast<int64_t>(0xffffffff))); | 464 RangeBoundary(static_cast<int64_t>(0xffffffff))); |
| 472 | 465 |
| 473 // Test that [-20, 20] & [-20, 20] = [-32, 31]. | 466 // Test that [-20, 20] & [-20, 20] = [-32, 31]. |
| 474 TEST_RANGE_AND(static_cast<int64_t>(-20), static_cast<int64_t>(20), | 467 TEST_RANGE_AND(static_cast<int64_t>(-20), static_cast<int64_t>(20), |
| 475 static_cast<int64_t>(-20), static_cast<int64_t>(20), | 468 static_cast<int64_t>(-20), static_cast<int64_t>(20), |
| 476 RangeBoundary(-32), RangeBoundary(31)); | 469 RangeBoundary(-32), RangeBoundary(31)); |
| 477 | 470 |
| 478 #undef TEST_RANGE_AND | 471 #undef TEST_RANGE_AND |
| 479 } | 472 } |
| 480 | 473 |
| 481 | |
| 482 TEST_CASE(RangeIntersectionMinMax) { | 474 TEST_CASE(RangeIntersectionMinMax) { |
| 483 // Test IntersectionMin and IntersectionMax methods which for constants are | 475 // Test IntersectionMin and IntersectionMax methods which for constants are |
| 484 // simply defined as Max/Min respectively. | 476 // simply defined as Max/Min respectively. |
| 485 | 477 |
| 486 // Constants. | 478 // Constants. |
| 487 // MIN(0, 1) == 0 | 479 // MIN(0, 1) == 0 |
| 488 EXPECT(RangeBoundary::IntersectionMax(RangeBoundary::FromConstant(0), | 480 EXPECT(RangeBoundary::IntersectionMax(RangeBoundary::FromConstant(0), |
| 489 RangeBoundary::FromConstant(1)) | 481 RangeBoundary::FromConstant(1)) |
| 490 .ConstantValue() == 0); | 482 .ConstantValue() == 0); |
| 491 // MIN(0, -1) == -1 | 483 // MIN(0, -1) == -1 |
| (...skipping 59 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 551 | 543 |
| 552 EXPECT( | 544 EXPECT( |
| 553 RangeBoundary::IntersectionMax(RangeBoundary::FromConstant(1), p_infinity) | 545 RangeBoundary::IntersectionMax(RangeBoundary::FromConstant(1), p_infinity) |
| 554 .ConstantValue() == 1); | 546 .ConstantValue() == 1); |
| 555 | 547 |
| 556 EXPECT( | 548 EXPECT( |
| 557 RangeBoundary::IntersectionMax(p_infinity, RangeBoundary::FromConstant(1)) | 549 RangeBoundary::IntersectionMax(p_infinity, RangeBoundary::FromConstant(1)) |
| 558 .ConstantValue() == 1); | 550 .ConstantValue() == 1); |
| 559 } | 551 } |
| 560 | 552 |
| 561 | |
| 562 TEST_CASE(RangeJoinMinMax) { | 553 TEST_CASE(RangeJoinMinMax) { |
| 563 // Test IntersectionMin and IntersectionMax methods which for constants are | 554 // Test IntersectionMin and IntersectionMax methods which for constants are |
| 564 // simply defined as Min/Max respectively. | 555 // simply defined as Min/Max respectively. |
| 565 const RangeBoundary::RangeSize size = RangeBoundary::kRangeBoundarySmi; | 556 const RangeBoundary::RangeSize size = RangeBoundary::kRangeBoundarySmi; |
| 566 | 557 |
| 567 // Constants. | 558 // Constants. |
| 568 EXPECT(RangeBoundary::JoinMax(RangeBoundary::FromConstant(0), | 559 EXPECT(RangeBoundary::JoinMax(RangeBoundary::FromConstant(0), |
| 569 RangeBoundary::FromConstant(1), size) | 560 RangeBoundary::FromConstant(1), size) |
| 570 .ConstantValue() == 1); | 561 .ConstantValue() == 1); |
| 571 EXPECT(RangeBoundary::JoinMax(RangeBoundary::FromConstant(0), | 562 EXPECT(RangeBoundary::JoinMax(RangeBoundary::FromConstant(0), |
| (...skipping 49 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 621 EXPECT( | 612 EXPECT( |
| 622 RangeBoundary::JoinMax(RangeBoundary::FromConstant(1), p_infinity, size) | 613 RangeBoundary::JoinMax(RangeBoundary::FromConstant(1), p_infinity, size) |
| 623 .IsMaximumOrAbove(size)); | 614 .IsMaximumOrAbove(size)); |
| 624 | 615 |
| 625 EXPECT( | 616 EXPECT( |
| 626 RangeBoundary::JoinMax(p_infinity, RangeBoundary::FromConstant(1), size) | 617 RangeBoundary::JoinMax(p_infinity, RangeBoundary::FromConstant(1), size) |
| 627 .IsMaximumOrAbove(size)); | 618 .IsMaximumOrAbove(size)); |
| 628 } | 619 } |
| 629 | 620 |
| 630 } // namespace dart | 621 } // namespace dart |
| OLD | NEW |