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 |