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
3// BSD-style license that can be found in the LICENSE file.
4
5#include "vm/compiler/backend/range_analysis.h"
6#include "vm/unit_test.h"
7
8namespace dart {
9
10TEST_CASE(RangeTests) {
11 Range* zero =
12 new Range(RangeBoundary::FromConstant(0), RangeBoundary::FromConstant(0));
13 Range* positive = new Range(RangeBoundary::FromConstant(0),
14 RangeBoundary::FromConstant(100));
15 Range* negative = new Range(RangeBoundary::FromConstant(-1),
16 RangeBoundary::FromConstant(-100));
17 Range* range_x = new Range(RangeBoundary::FromConstant(-15),
18 RangeBoundary::FromConstant(100));
19 EXPECT(positive->IsPositive());
20 EXPECT(zero->Overlaps(0, 0));
21 EXPECT(positive->Overlaps(0, 0));
22 EXPECT(!negative->Overlaps(0, 0));
23 EXPECT(range_x->Overlaps(0, 0));
24 EXPECT(range_x->IsWithin(-15, 100));
25 EXPECT(!range_x->IsWithin(-15, 99));
26 EXPECT(!range_x->IsWithin(-14, 100));
27
28#define TEST_RANGE_OP_(Op, l_min, l_max, r_min, r_max, Clamp, res_min, \
29 res_max) \
30 { \
31 RangeBoundary min, max; \
32 Range* left_range = new Range(RangeBoundary::FromConstant(l_min), \
33 RangeBoundary::FromConstant(l_max)); \
34 Range* shift_range = new Range(RangeBoundary::FromConstant(r_min), \
35 RangeBoundary::FromConstant(r_max)); \
36 Op(left_range, shift_range, &min, &max); \
37 min = Clamp(min); \
38 max = Clamp(max); \
39 EXPECT(min.Equals(res_min)); \
40 if (FLAG_support_il_printer && !min.Equals(res_min)) { \
41 OS::PrintErr("%s\n", min.ToCString()); \
42 } \
43 EXPECT(max.Equals(res_max)); \
44 if (FLAG_support_il_printer && !max.Equals(res_max)) { \
45 OS::PrintErr("%s\n", max.ToCString()); \
46 } \
47 }
48
49#define NO_CLAMP(b) (b)
50#define TEST_RANGE_OP(Op, l_min, l_max, r_min, r_max, result_min, result_max) \
51 TEST_RANGE_OP_(Op, l_min, l_max, r_min, r_max, NO_CLAMP, result_min, \
52 result_max)
53
54#define CLAMP_TO_SMI(b) (b.Clamp(RangeBoundary::kRangeBoundarySmi))
55#define TEST_RANGE_OP_SMI(Op, l_min, l_max, r_min, r_max, res_min, res_max) \
56 TEST_RANGE_OP_(Op, l_min, l_max, r_min, r_max, CLAMP_TO_SMI, res_min, res_max)
57
58 TEST_RANGE_OP(Range::Shl, -15, 100, 0, 2, RangeBoundary(-60),
59 RangeBoundary(400));
60 TEST_RANGE_OP(Range::Shl, -15, 100, -2, 2, RangeBoundary(-60),
61 RangeBoundary(400));
62 TEST_RANGE_OP(Range::Shl, -15, -10, 1, 2, RangeBoundary(-60),
63 RangeBoundary(-20));
64 TEST_RANGE_OP(Range::Shl, 5, 10, -2, 2, RangeBoundary(5), RangeBoundary(40));
65 TEST_RANGE_OP(Range::Shl, -15, 100, 0, 64, RangeBoundary::NegativeInfinity(),
66 RangeBoundary::PositiveInfinity());
67 TEST_RANGE_OP(Range::Shl, -1, 1, 63, 63, RangeBoundary(kMinInt64),
68 RangeBoundary::PositiveInfinity());
69 if (kBitsPerWord == 64) {
70 TEST_RANGE_OP_SMI(Range::Shl, -1, 1, 62, 62,
71 RangeBoundary(compiler::target::kSmiMin),
72 RangeBoundary(compiler::target::kSmiMax));
73 TEST_RANGE_OP_SMI(Range::Shl, -1, 1, 30, 30, RangeBoundary(-(1 << 30)),
74 RangeBoundary(1 << 30));
75 } else {
76 TEST_RANGE_OP_SMI(Range::Shl, -1, 1, 30, 30,
77 RangeBoundary(compiler::target::kSmiMin),
78 RangeBoundary(compiler::target::kSmiMax));
79 TEST_RANGE_OP_SMI(Range::Shl, -1, 1, 62, 62,
80 RangeBoundary(compiler::target::kSmiMin),
81 RangeBoundary(compiler::target::kSmiMax));
82 }
83 TEST_RANGE_OP(Range::Shl, 0, 100, 0, 64, RangeBoundary(0),
84 RangeBoundary::PositiveInfinity());
85 TEST_RANGE_OP(Range::Shl, -100, 0, 0, 64, RangeBoundary::NegativeInfinity(),
86 RangeBoundary(0));
87
88 TEST_RANGE_OP(Range::Shr, -8, 8, 1, 2, RangeBoundary(-4), RangeBoundary(4));
89 TEST_RANGE_OP(Range::Shr, 1, 8, 1, 2, RangeBoundary(0), RangeBoundary(4));
90 TEST_RANGE_OP(Range::Shr, -16, -8, 1, 2, RangeBoundary(-8),
91 RangeBoundary(-2));
92 TEST_RANGE_OP(Range::Shr, 2, 4, -1, 1, RangeBoundary(1), RangeBoundary(4));
93 TEST_RANGE_OP(Range::Shr, kMaxInt64, kMaxInt64, 0, 1,
94 RangeBoundary(kMaxInt64 >> 1), RangeBoundary(kMaxInt64));
95 TEST_RANGE_OP(Range::Shr, kMinInt64, kMinInt64, 0, 1,
96 RangeBoundary(kMinInt64), RangeBoundary(kMinInt64 >> 1));
97#undef TEST_RANGE_OP
98}
99
100TEST_CASE(RangeTestsInfinity) {
101 // +/- inf overflowed.
102 EXPECT(RangeBoundary::NegativeInfinity().OverflowedSmi());
103 EXPECT(RangeBoundary::PositiveInfinity().OverflowedSmi());
104
105 EXPECT(RangeBoundary::NegativeInfinity().OverflowedMint());
106 EXPECT(RangeBoundary::PositiveInfinity().OverflowedMint());
107
108 const Range fullInt64Range = Range::Full(RangeBoundary::kRangeBoundaryInt64);
109
110 Range* all = new Range(RangeBoundary::NegativeInfinity(),
111 RangeBoundary::PositiveInfinity());
112 EXPECT(all->Equals(&fullInt64Range));
113 EXPECT(all->Overlaps(0, 0));
114 EXPECT(all->Overlaps(-1, 1));
115 EXPECT(!all->IsWithin(0, 100));
116
117 Range* positive = new Range(RangeBoundary::FromConstant(0),
118 RangeBoundary::PositiveInfinity());
119 EXPECT(positive->Equals(&fullInt64Range));
120 EXPECT(positive->Overlaps(0, 1));
121 EXPECT(positive->Overlaps(1, 100));
122 EXPECT(positive->Overlaps(-1, 0));
123
124 Range* negative = new Range(RangeBoundary::NegativeInfinity(),
125 RangeBoundary::FromConstant(-1));
126 EXPECT(positive->Equals(&fullInt64Range));
127 EXPECT(negative->Overlaps(-1, 0));
128 EXPECT(negative->Overlaps(-2, -1));
129
130 Range* negpos = new Range(RangeBoundary::NegativeInfinity(),
131 RangeBoundary::FromConstant(0));
132 EXPECT(negpos->Equals(&fullInt64Range));
133 EXPECT(!negpos->IsPositive());
134
135 Range* a = new Range(RangeBoundary::NegativeInfinity(),
136 RangeBoundary::FromConstant(1));
137
138 Range* b = new Range(RangeBoundary::NegativeInfinity(),
139 RangeBoundary::FromConstant(31));
140
141 Range* c = new Range(RangeBoundary::NegativeInfinity(),
142 RangeBoundary::FromConstant(32));
143
144 EXPECT(a->Equals(&fullInt64Range));
145 EXPECT(b->Equals(&fullInt64Range));
146 EXPECT(c->Equals(&fullInt64Range));
147 EXPECT(!c->OnlyLessThanOrEqualTo(31));
148
149 Range* unsatisfiable = new Range(RangeBoundary::PositiveInfinity(),
150 RangeBoundary::NegativeInfinity());
151 EXPECT(unsatisfiable->Equals(&fullInt64Range));
152
153 Range* unsatisfiable_right = new Range(RangeBoundary::PositiveInfinity(),
154 RangeBoundary::FromConstant(0));
155 EXPECT(unsatisfiable_right->Equals(&fullInt64Range));
156
157 Range* unsatisfiable_left = new Range(RangeBoundary::FromConstant(0),
158 RangeBoundary::NegativeInfinity());
159 EXPECT(unsatisfiable_left->Equals(&fullInt64Range));
160}
161
162TEST_CASE(RangeUtils) {
163 // Use kMin/kMax instead of +/-inf as any range with a +/-inf bound is
164 // converted to the full int64 range due to wrap-around.
165 const RangeBoundary negativeInfinity =
166 RangeBoundary::FromConstant(RangeBoundary::kMin);
167 const RangeBoundary positiveInfinity =
168 RangeBoundary::FromConstant(RangeBoundary::kMax);
169
170 // [-inf, +inf].
171 const Range& range_0 = *(new Range(negativeInfinity, positiveInfinity));
172 // [-inf, -1].
173 const Range& range_a =
174 *(new Range(negativeInfinity, RangeBoundary::FromConstant(-1)));
175 // [-inf, 0].
176 const Range& range_b =
177 *(new Range(negativeInfinity, RangeBoundary::FromConstant(0)));
178 // [-inf, 1].
179 const Range& range_c =
180 *(new Range(negativeInfinity, RangeBoundary::FromConstant(1)));
181 // [-1, +inf]
182 const Range& range_d =
183 *(new Range(RangeBoundary::FromConstant(-1), positiveInfinity));
184 // [0, +inf]
185 const Range& range_e =
186 *(new Range(RangeBoundary::FromConstant(0), positiveInfinity));
187 // [1, +inf].
188 const Range& range_f =
189 *(new Range(RangeBoundary::FromConstant(1), positiveInfinity));
190 // [1, 2].
191 const Range& range_g = *(new Range(RangeBoundary::FromConstant(1),
192 RangeBoundary::FromConstant(2)));
193 // [-1, -2].
194 const Range& range_h = *(new Range(RangeBoundary::FromConstant(-1),
195 RangeBoundary::FromConstant(-2)));
196 // [-1, 1].
197 const Range& range_i = *(new Range(RangeBoundary::FromConstant(-1),
198 RangeBoundary::FromConstant(1)));
199
200 // OnlyPositiveOrZero.
201 EXPECT(!Range::OnlyPositiveOrZero(range_a, range_b));
202 EXPECT(!Range::OnlyPositiveOrZero(range_b, range_c));
203 EXPECT(!Range::OnlyPositiveOrZero(range_c, range_d));
204 EXPECT(!Range::OnlyPositiveOrZero(range_d, range_e));
205 EXPECT(Range::OnlyPositiveOrZero(range_e, range_f));
206 EXPECT(!Range::OnlyPositiveOrZero(range_d, range_d));
207 EXPECT(Range::OnlyPositiveOrZero(range_e, range_e));
208 EXPECT(Range::OnlyPositiveOrZero(range_f, range_g));
209 EXPECT(!Range::OnlyPositiveOrZero(range_g, range_h));
210 EXPECT(!Range::OnlyPositiveOrZero(range_i, range_i));
211
212 // OnlyNegativeOrZero.
213 EXPECT(Range::OnlyNegativeOrZero(range_a, range_b));
214 EXPECT(!Range::OnlyNegativeOrZero(range_b, range_c));
215 EXPECT(Range::OnlyNegativeOrZero(range_b, range_b));
216 EXPECT(!Range::OnlyNegativeOrZero(range_c, range_c));
217 EXPECT(!Range::OnlyNegativeOrZero(range_c, range_d));
218 EXPECT(!Range::OnlyNegativeOrZero(range_d, range_e));
219 EXPECT(!Range::OnlyNegativeOrZero(range_e, range_f));
220 EXPECT(!Range::OnlyNegativeOrZero(range_f, range_g));
221 EXPECT(!Range::OnlyNegativeOrZero(range_g, range_h));
222 EXPECT(Range::OnlyNegativeOrZero(range_h, range_h));
223 EXPECT(!Range::OnlyNegativeOrZero(range_i, range_i));
224
225 // [-inf, +inf].
226 EXPECT(!Range::OnlyNegativeOrZero(range_0, range_0));
227 EXPECT(!Range::OnlyPositiveOrZero(range_0, range_0));
228
229 EXPECT(Range::ConstantAbsMax(&range_0) == RangeBoundary::kMax);
230 EXPECT(Range::ConstantAbsMax(&range_h) == 2);
231 EXPECT(Range::ConstantAbsMax(&range_i) == 1);
232
233 // RangeBOundary.Equals.
234 EXPECT(RangeBoundary::FromConstant(1).Equals(RangeBoundary::FromConstant(1)));
235 EXPECT(
236 !RangeBoundary::FromConstant(2).Equals(RangeBoundary::FromConstant(1)));
237 EXPECT(RangeBoundary::PositiveInfinity().Equals(
238 RangeBoundary::PositiveInfinity()));
239 EXPECT(!RangeBoundary::PositiveInfinity().Equals(
240 RangeBoundary::NegativeInfinity()));
241 EXPECT(RangeBoundary::NegativeInfinity().Equals(
242 RangeBoundary::NegativeInfinity()));
243 EXPECT(!RangeBoundary::NegativeInfinity().Equals(
244 RangeBoundary::PositiveInfinity()));
245 EXPECT(!RangeBoundary::FromConstant(1).Equals(
246 RangeBoundary::NegativeInfinity()));
247 EXPECT(!RangeBoundary::FromConstant(1).Equals(
248 RangeBoundary::NegativeInfinity()));
249 EXPECT(!RangeBoundary::FromConstant(2).Equals(
250 RangeBoundary::PositiveInfinity()));
251}
252
253TEST_CASE(RangeBinaryOp) {
254 Range* range_a = new Range(RangeBoundary::FromConstant(-1),
255 RangeBoundary::FromConstant(RangeBoundary::kMax));
256 range_a->Clamp(RangeBoundary::kRangeBoundaryInt32);
257 EXPECT(range_a->min().ConstantValue() == -1);
258 EXPECT(range_a->max().ConstantValue() == kMaxInt32);
259 range_a->set_max(RangeBoundary::FromConstant(RangeBoundary::kMax));
260
261 Range* range_b = new Range(RangeBoundary::FromConstant(RangeBoundary::kMin),
262 RangeBoundary::FromConstant(1));
263 range_b->Clamp(RangeBoundary::kRangeBoundaryInt32);
264 EXPECT(range_b->min().ConstantValue() == kMinInt32);
265 EXPECT(range_b->max().ConstantValue() == 1);
266 range_b->set_min(RangeBoundary::FromConstant(RangeBoundary::kMin));
267
268 {
269 Range result;
270 Range::BinaryOp(Token::kADD, range_a, range_b, NULL, &result);
271 ASSERT(!Range::IsUnknown(&result));
272 EXPECT(!result.min().IsNegativeInfinity());
273 EXPECT(!result.max().IsPositiveInfinity());
274 EXPECT(result.min().Equals(
275 RangeBoundary::MinConstant(RangeBoundary::kRangeBoundaryInt64)));
276 EXPECT(result.max().Equals(
277 RangeBoundary::MaxConstant(RangeBoundary::kRangeBoundaryInt64)));
278 }
279
280 // Test that [5, 10] + [0, 5] = [5, 15].
281 Range* range_c = new Range(RangeBoundary::FromConstant(5),
282 RangeBoundary::FromConstant(10));
283 Range* range_d =
284 new Range(RangeBoundary::FromConstant(0), RangeBoundary::FromConstant(5));
285
286 {
287 Range result;
288 Range::BinaryOp(Token::kADD, range_c, range_d, NULL, &result);
289 ASSERT(!Range::IsUnknown(&result));
290 EXPECT(result.min().ConstantValue() == 5);
291 EXPECT(result.max().ConstantValue() == 15);
292 }
293
294 // Test that [0xff, 0xfff] & [0xf, 0xf] = [0x0, 0xf].
295 Range* range_e = new Range(RangeBoundary::FromConstant(0xff),
296 RangeBoundary::FromConstant(0xfff));
297 Range* range_f = new Range(RangeBoundary::FromConstant(0xf),
298 RangeBoundary::FromConstant(0xf));
299 {
300 Range result;
301 Range::BinaryOp(Token::kBIT_AND, range_e, range_f, NULL, &result);
302 ASSERT(!Range::IsUnknown(&result));
303 EXPECT(result.min().ConstantValue() == 0x0);
304 EXPECT(result.max().ConstantValue() == 0xf);
305 }
306}
307
308TEST_CASE(RangeAdd) {
309#define TEST_RANGE_ADD(l_min, l_max, r_min, r_max, result_min, result_max) \
310 { \
311 RangeBoundary min, max; \
312 Range* left_range = new Range(RangeBoundary::FromConstant(l_min), \
313 RangeBoundary::FromConstant(l_max)); \
314 Range* right_range = new Range(RangeBoundary::FromConstant(r_min), \
315 RangeBoundary::FromConstant(r_max)); \
316 EXPECT(left_range->min().ConstantValue() == l_min); \
317 EXPECT(left_range->max().ConstantValue() == l_max); \
318 EXPECT(right_range->min().ConstantValue() == r_min); \
319 EXPECT(right_range->max().ConstantValue() == r_max); \
320 Range::Add(left_range, right_range, &min, &max, NULL); \
321 EXPECT(min.Equals(result_min)); \
322 if (FLAG_support_il_printer && !min.Equals(result_min)) { \
323 OS::PrintErr("%s != %s\n", min.ToCString(), result_min.ToCString()); \
324 } \
325 EXPECT(max.Equals(result_max)); \
326 if (FLAG_support_il_printer && !max.Equals(result_max)) { \
327 OS::PrintErr("%s != %s\n", max.ToCString(), result_max.ToCString()); \
328 } \
329 }
330
331 // [kMaxInt32, kMaxInt32 + 15] + [10, 20] = [kMaxInt32 + 10, kMaxInt32 + 35].
332 TEST_RANGE_ADD(static_cast<int64_t>(kMaxInt32),
333 static_cast<int64_t>(kMaxInt32) + 15, static_cast<int64_t>(10),
334 static_cast<int64_t>(20),
335 RangeBoundary(static_cast<int64_t>(kMaxInt32) + 10),
336 RangeBoundary(static_cast<int64_t>(kMaxInt32) + 35));
337
338 // [kMaxInt32 - 15, kMaxInt32 + 15] + [15, -15] = [kMaxInt32, kMaxInt32].
339 TEST_RANGE_ADD(static_cast<int64_t>(kMaxInt32) - 15,
340 static_cast<int64_t>(kMaxInt32) + 15, static_cast<int64_t>(15),
341 static_cast<int64_t>(-15),
342 RangeBoundary(static_cast<int64_t>(kMaxInt32)),
343 RangeBoundary(static_cast<int64_t>(kMaxInt32)));
344
345 // [kMaxInt32, kMaxInt32 + 15] + [10, kMaxInt64] = [kMaxInt32 + 10, +inf].
346 TEST_RANGE_ADD(static_cast<int64_t>(kMaxInt32),
347 static_cast<int64_t>(kMaxInt32) + 15, static_cast<int64_t>(10),
348 static_cast<int64_t>(kMaxInt64),
349 RangeBoundary(static_cast<int64_t>(kMaxInt32) + 10),
350 RangeBoundary::PositiveInfinity());
351
352 // [kMinInt64, kMaxInt32 + 15] + [10, 20] = [kMinInt64 + 10, kMaxInt32 + 35].
353 TEST_RANGE_ADD(static_cast<int64_t>(kMinInt64),
354 static_cast<int64_t>(kMaxInt32) + 15, static_cast<int64_t>(10),
355 static_cast<int64_t>(20),
356 RangeBoundary(static_cast<int64_t>(kMinInt64) + 10),
357 RangeBoundary(static_cast<int64_t>(kMaxInt32) + 35));
358
359 // [0, 0] + [kMinInt64, kMaxInt64] = [kMinInt64, kMaxInt64].
360 TEST_RANGE_ADD(static_cast<int64_t>(0), static_cast<int64_t>(0),
361 static_cast<int64_t>(kMinInt64),
362 static_cast<int64_t>(kMaxInt64), RangeBoundary(kMinInt64),
363 RangeBoundary(kMaxInt64));
364
365 // Overflows.
366
367 // [-1, 1] + [kMinInt64, kMaxInt64] = [-inf, +inf].
368 TEST_RANGE_ADD(
369 static_cast<int64_t>(-1), static_cast<int64_t>(1),
370 static_cast<int64_t>(kMinInt64), static_cast<int64_t>(kMaxInt64),
371 RangeBoundary::NegativeInfinity(), RangeBoundary::PositiveInfinity());
372
373 // [kMaxInt64, kMaxInt64] + [kMaxInt64, kMaxInt64] = [-inf, +inf].
374 TEST_RANGE_ADD(
375 static_cast<int64_t>(kMaxInt64), static_cast<int64_t>(kMaxInt64),
376 static_cast<int64_t>(kMaxInt64), static_cast<int64_t>(kMaxInt64),
377 RangeBoundary::NegativeInfinity(), RangeBoundary::PositiveInfinity());
378
379 // [kMaxInt64, kMaxInt64] + [1, 1] = [-inf, +inf].
380 TEST_RANGE_ADD(static_cast<int64_t>(kMaxInt64),
381 static_cast<int64_t>(kMaxInt64), static_cast<int64_t>(1),
382 static_cast<int64_t>(1), RangeBoundary::NegativeInfinity(),
383 RangeBoundary::PositiveInfinity());
384
385#undef TEST_RANGE_ADD
386}
387
388TEST_CASE(RangeSub) {
389#define TEST_RANGE_SUB(l_min, l_max, r_min, r_max, result_min, result_max) \
390 { \
391 RangeBoundary min, max; \
392 Range* left_range = new Range(RangeBoundary::FromConstant(l_min), \
393 RangeBoundary::FromConstant(l_max)); \
394 Range* right_range = new Range(RangeBoundary::FromConstant(r_min), \
395 RangeBoundary::FromConstant(r_max)); \
396 EXPECT(left_range->min().ConstantValue() == l_min); \
397 EXPECT(left_range->max().ConstantValue() == l_max); \
398 EXPECT(right_range->min().ConstantValue() == r_min); \
399 EXPECT(right_range->max().ConstantValue() == r_max); \
400 Range::Sub(left_range, right_range, &min, &max, NULL); \
401 EXPECT(min.Equals(result_min)); \
402 if (FLAG_support_il_printer && !min.Equals(result_min)) { \
403 OS::PrintErr("%s != %s\n", min.ToCString(), result_min.ToCString()); \
404 } \
405 EXPECT(max.Equals(result_max)); \
406 if (FLAG_support_il_printer && !max.Equals(result_max)) { \
407 OS::PrintErr("%s != %s\n", max.ToCString(), result_max.ToCString()); \
408 } \
409 }
410
411 // [kMaxInt32, kMaxInt32 + 15] - [10, 20] = [kMaxInt32 - 20, kMaxInt32 + 5].
412 TEST_RANGE_SUB(static_cast<int64_t>(kMaxInt32),
413 static_cast<int64_t>(kMaxInt32) + 15, static_cast<int64_t>(10),
414 static_cast<int64_t>(20),
415 RangeBoundary(static_cast<int64_t>(kMaxInt32) - 20),
416 RangeBoundary(static_cast<int64_t>(kMaxInt32) + 5));
417
418 // [kMintInt64, kMintInt64] - [1, 1] = [-inf, +inf].
419 TEST_RANGE_SUB(static_cast<int64_t>(kMinInt64),
420 static_cast<int64_t>(kMinInt64), static_cast<int64_t>(1),
421 static_cast<int64_t>(1), RangeBoundary::NegativeInfinity(),
422 RangeBoundary::PositiveInfinity());
423
424 // [1, 1] - [kMintInt64, kMintInt64] = [-inf, +inf].
425 TEST_RANGE_SUB(
426 static_cast<int64_t>(1), static_cast<int64_t>(1),
427 static_cast<int64_t>(kMinInt64), static_cast<int64_t>(kMinInt64),
428 RangeBoundary::NegativeInfinity(), RangeBoundary::PositiveInfinity());
429
430 // [kMaxInt32 + 10, kMaxInt32 + 20] - [-20, -20] =
431 // [kMaxInt32 + 30, kMaxInt32 + 40].
432 TEST_RANGE_SUB(static_cast<int64_t>(kMaxInt32) + 10,
433 static_cast<int64_t>(kMaxInt32) + 20,
434 static_cast<int64_t>(-20), static_cast<int64_t>(-20),
435 RangeBoundary(static_cast<int64_t>(kMaxInt32) + 30),
436 RangeBoundary(static_cast<int64_t>(kMaxInt32) + 40));
437
438#undef TEST_RANGE_SUB
439}
440
441TEST_CASE(RangeAnd) {
442#define TEST_RANGE_AND(l_min, l_max, r_min, r_max, result_min, result_max) \
443 { \
444 RangeBoundary min, max; \
445 Range* left_range = new Range(RangeBoundary::FromConstant(l_min), \
446 RangeBoundary::FromConstant(l_max)); \
447 Range* right_range = new Range(RangeBoundary::FromConstant(r_min), \
448 RangeBoundary::FromConstant(r_max)); \
449 EXPECT(left_range->min().ConstantValue() == l_min); \
450 EXPECT(left_range->max().ConstantValue() == l_max); \
451 EXPECT(right_range->min().ConstantValue() == r_min); \
452 EXPECT(right_range->max().ConstantValue() == r_max); \
453 Range::And(left_range, right_range, &min, &max); \
454 EXPECT(min.Equals(result_min)); \
455 if (FLAG_support_il_printer && !min.Equals(result_min)) { \
456 OS::PrintErr("%s != %s\n", min.ToCString(), result_min.ToCString()); \
457 } \
458 EXPECT(max.Equals(result_max)); \
459 if (FLAG_support_il_printer && !max.Equals(result_max)) { \
460 OS::PrintErr("%s != %s\n", max.ToCString(), result_max.ToCString()); \
461 } \
462 }
463
464 // [0xff, 0xfff] & [0xf, 0xf] = [0x0, 0xf].
465 TEST_RANGE_AND(static_cast<int64_t>(0xff), static_cast<int64_t>(0xfff),
466 static_cast<int64_t>(0xf), static_cast<int64_t>(0xf),
467 RangeBoundary(0), RangeBoundary(0xf));
468
469 // [0xffffffff, 0xffffffff] & [0xfffffffff, 0xfffffffff] = [0x0, 0xfffffffff].
470 TEST_RANGE_AND(
471 static_cast<int64_t>(0xffffffff), static_cast<int64_t>(0xffffffff),
472 static_cast<int64_t>(0xfffffffff), static_cast<int64_t>(0xfffffffff),
473 RangeBoundary(0), RangeBoundary(static_cast<int64_t>(0xfffffffff)));
474
475 // [0xffffffff, 0xffffffff] & [-20, 20] = [0x0, 0xffffffff].
476 TEST_RANGE_AND(static_cast<int64_t>(0xffffffff),
477 static_cast<int64_t>(0xffffffff), static_cast<int64_t>(-20),
478 static_cast<int64_t>(20), RangeBoundary(0),
479 RangeBoundary(static_cast<int64_t>(0xffffffff)));
480
481 // [-20, 20] & [0xffffffff, 0xffffffff] = [0x0, 0xffffffff].
482 TEST_RANGE_AND(static_cast<int64_t>(-20), static_cast<int64_t>(20),
483 static_cast<int64_t>(0xffffffff),
484 static_cast<int64_t>(0xffffffff), RangeBoundary(0),
485 RangeBoundary(static_cast<int64_t>(0xffffffff)));
486
487 // Test that [-20, 20] & [-20, 20] = [-32, 31].
488 TEST_RANGE_AND(static_cast<int64_t>(-20), static_cast<int64_t>(20),
489 static_cast<int64_t>(-20), static_cast<int64_t>(20),
490 RangeBoundary(-32), RangeBoundary(31));
491
492#undef TEST_RANGE_AND
493}
494
495TEST_CASE(RangeIntersectionMinMax) {
496 // Test IntersectionMin and IntersectionMax methods which for constants are
497 // simply defined as Max/Min respectively.
498
499 // Constants.
500 // MIN(0, 1) == 0
501 EXPECT(RangeBoundary::IntersectionMax(RangeBoundary::FromConstant(0),
502 RangeBoundary::FromConstant(1))
503 .ConstantValue() == 0);
504 // MIN(0, -1) == -1
505 EXPECT(RangeBoundary::IntersectionMax(RangeBoundary::FromConstant(0),
506 RangeBoundary::FromConstant(-1))
507 .ConstantValue() == -1);
508
509 // MIN(1, 0) == 0
510 EXPECT(RangeBoundary::IntersectionMax(RangeBoundary::FromConstant(1),
511 RangeBoundary::FromConstant(0))
512 .ConstantValue() == 0);
513 // MIN(-1, 0) == -1
514 EXPECT(RangeBoundary::IntersectionMax(RangeBoundary::FromConstant(-1),
515 RangeBoundary::FromConstant(0))
516 .ConstantValue() == -1);
517
518 // MAX(0, 1) == 1
519 EXPECT(RangeBoundary::IntersectionMin(RangeBoundary::FromConstant(0),
520 RangeBoundary::FromConstant(1))
521 .ConstantValue() == 1);
522
523 // MAX(0, -1) == 0
524 EXPECT(RangeBoundary::IntersectionMin(RangeBoundary::FromConstant(0),
525 RangeBoundary::FromConstant(-1))
526 .ConstantValue() == 0);
527
528 // MAX(1, 0) == 1
529 EXPECT(RangeBoundary::IntersectionMin(RangeBoundary::FromConstant(1),
530 RangeBoundary::FromConstant(0))
531 .ConstantValue() == 1);
532 // MAX(-1, 0) == 0
533 EXPECT(RangeBoundary::IntersectionMin(RangeBoundary::FromConstant(-1),
534 RangeBoundary::FromConstant(0))
535 .ConstantValue() == 0);
536
537 RangeBoundary n_infinity = RangeBoundary::NegativeInfinity();
538 RangeBoundary p_infinity = RangeBoundary::PositiveInfinity();
539
540 // Constants vs. infinity.
541 EXPECT(RangeBoundary::IntersectionMin(n_infinity,
542 RangeBoundary::FromConstant(-1))
543 .ConstantValue() == -1);
544
545 EXPECT(RangeBoundary::IntersectionMin(RangeBoundary::FromConstant(-1),
546 n_infinity)
547 .ConstantValue() == -1);
548
549 EXPECT(
550 RangeBoundary::IntersectionMin(RangeBoundary::FromConstant(1), n_infinity)
551 .ConstantValue() == 1);
552
553 EXPECT(
554 RangeBoundary::IntersectionMin(n_infinity, RangeBoundary::FromConstant(1))
555 .ConstantValue() == 1);
556
557 EXPECT(RangeBoundary::IntersectionMax(p_infinity,
558 RangeBoundary::FromConstant(-1))
559 .ConstantValue() == -1);
560
561 EXPECT(RangeBoundary::IntersectionMax(RangeBoundary::FromConstant(-1),
562 p_infinity)
563 .ConstantValue() == -1);
564
565 EXPECT(
566 RangeBoundary::IntersectionMax(RangeBoundary::FromConstant(1), p_infinity)
567 .ConstantValue() == 1);
568
569 EXPECT(
570 RangeBoundary::IntersectionMax(p_infinity, RangeBoundary::FromConstant(1))
571 .ConstantValue() == 1);
572}
573
574TEST_CASE(RangeJoinMinMax) {
575 // Test IntersectionMin and IntersectionMax methods which for constants are
576 // simply defined as Min/Max respectively.
577 const RangeBoundary::RangeSize size = RangeBoundary::kRangeBoundarySmi;
578
579 // Constants.
580 EXPECT(RangeBoundary::JoinMax(RangeBoundary::FromConstant(0),
581 RangeBoundary::FromConstant(1), size)
582 .ConstantValue() == 1);
583 EXPECT(RangeBoundary::JoinMax(RangeBoundary::FromConstant(0),
584 RangeBoundary::FromConstant(-1), size)
585 .ConstantValue() == 0);
586 EXPECT(RangeBoundary::JoinMax(RangeBoundary::FromConstant(1),
587 RangeBoundary::FromConstant(0), size)
588 .ConstantValue() == 1);
589 EXPECT(RangeBoundary::JoinMax(RangeBoundary::FromConstant(-1),
590 RangeBoundary::FromConstant(0), size)
591 .ConstantValue() == 0);
592 EXPECT(RangeBoundary::JoinMin(RangeBoundary::FromConstant(0),
593 RangeBoundary::FromConstant(1), size)
594 .ConstantValue() == 0);
595 EXPECT(RangeBoundary::JoinMin(RangeBoundary::FromConstant(0),
596 RangeBoundary::FromConstant(-1), size)
597 .ConstantValue() == -1);
598 EXPECT(RangeBoundary::JoinMin(RangeBoundary::FromConstant(1),
599 RangeBoundary::FromConstant(0), size)
600 .ConstantValue() == 0);
601 EXPECT(RangeBoundary::JoinMin(RangeBoundary::FromConstant(-1),
602 RangeBoundary::FromConstant(0), size)
603 .ConstantValue() == -1);
604
605 RangeBoundary n_infinity = RangeBoundary::NegativeInfinity();
606 RangeBoundary p_infinity = RangeBoundary::PositiveInfinity();
607
608 // Constants vs. infinity.
609 EXPECT(
610 RangeBoundary::JoinMin(n_infinity, RangeBoundary::FromConstant(-1), size)
611 .IsMinimumOrBelow(size));
612
613 EXPECT(
614 RangeBoundary::JoinMin(RangeBoundary::FromConstant(-1), n_infinity, size)
615 .IsMinimumOrBelow(size));
616
617 EXPECT(
618 RangeBoundary::JoinMin(RangeBoundary::FromConstant(1), n_infinity, size)
619 .IsMinimumOrBelow(size));
620
621 EXPECT(
622 RangeBoundary::JoinMin(n_infinity, RangeBoundary::FromConstant(1), size)
623 .IsMinimumOrBelow(size));
624
625 EXPECT(
626 RangeBoundary::JoinMax(p_infinity, RangeBoundary::FromConstant(-1), size)
627 .IsMaximumOrAbove(size));
628
629 EXPECT(
630 RangeBoundary::JoinMax(RangeBoundary::FromConstant(-1), p_infinity, size)
631 .IsMaximumOrAbove(size));
632
633 EXPECT(
634 RangeBoundary::JoinMax(RangeBoundary::FromConstant(1), p_infinity, size)
635 .IsMaximumOrAbove(size));
636
637 EXPECT(
638 RangeBoundary::JoinMax(p_infinity, RangeBoundary::FromConstant(1), size)
639 .IsMaximumOrAbove(size));
640}
641
642} // namespace dart
643