Flutter Engine
The Flutter Engine
Loading...
Searching...
No Matches
range_analysis_test.cc
Go to the documentation of this 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
3// BSD-style license that can be found in the LICENSE file.
4
5#include "vm/compiler/backend/range_analysis.h"
6#include "vm/compiler/backend/il_test_helper.h"
7#include "vm/unit_test.h"
8
9namespace dart {
10
11TEST_CASE(RangeTests) {
12 Range* zero =
13 new Range(RangeBoundary::FromConstant(0), RangeBoundary::FromConstant(0));
14 Range* positive = new Range(RangeBoundary::FromConstant(0),
15 RangeBoundary::FromConstant(100));
16 Range* negative = new Range(RangeBoundary::FromConstant(-1),
17 RangeBoundary::FromConstant(-100));
18 Range* range_x = new Range(RangeBoundary::FromConstant(-15),
19 RangeBoundary::FromConstant(100));
20 EXPECT(positive->IsPositive());
21 EXPECT(zero->Overlaps(0, 0));
22 EXPECT(positive->Overlaps(0, 0));
23 EXPECT(!negative->Overlaps(0, 0));
24 EXPECT(range_x->Overlaps(0, 0));
25 EXPECT(range_x->IsWithin(-15, 100));
26 EXPECT(!range_x->IsWithin(-15, 99));
27 EXPECT(!range_x->IsWithin(-14, 100));
28
29#define TEST_RANGE_OP_(Op, l_min, l_max, r_min, r_max, Clamp, res_min, \
30 res_max) \
31 { \
32 RangeBoundary min, max; \
33 Range* left_range = new Range(RangeBoundary::FromConstant(l_min), \
34 RangeBoundary::FromConstant(l_max)); \
35 Range* shift_range = new Range(RangeBoundary::FromConstant(r_min), \
36 RangeBoundary::FromConstant(r_max)); \
37 Op(left_range, shift_range, &min, &max); \
38 min = Clamp(min); \
39 max = Clamp(max); \
40 EXPECT(min.Equals(res_min)); \
41 if (FLAG_support_il_printer && !min.Equals(res_min)) { \
42 OS::PrintErr("%s\n", min.ToCString()); \
43 } \
44 EXPECT(max.Equals(res_max)); \
45 if (FLAG_support_il_printer && !max.Equals(res_max)) { \
46 OS::PrintErr("%s\n", max.ToCString()); \
47 } \
48 }
49
50#define NO_CLAMP(b) (b)
51#define TEST_RANGE_OP(Op, l_min, l_max, r_min, r_max, result_min, result_max) \
52 TEST_RANGE_OP_(Op, l_min, l_max, r_min, r_max, NO_CLAMP, result_min, \
53 result_max)
54
55#define CLAMP_TO_SMI(b) (b.Clamp(RangeBoundary::kRangeBoundarySmi))
56#define TEST_RANGE_OP_SMI(Op, l_min, l_max, r_min, r_max, res_min, res_max) \
57 TEST_RANGE_OP_(Op, l_min, l_max, r_min, r_max, CLAMP_TO_SMI, res_min, res_max)
58
59 TEST_RANGE_OP(Range::Shl, -15, 100, 0, 2, RangeBoundary(-60),
60 RangeBoundary(400));
61 TEST_RANGE_OP(Range::Shl, -15, 100, -2, 2, RangeBoundary(-60),
62 RangeBoundary(400));
63 TEST_RANGE_OP(Range::Shl, -15, -10, 1, 2, RangeBoundary(-60),
64 RangeBoundary(-20));
65 TEST_RANGE_OP(Range::Shl, 5, 10, -2, 2, RangeBoundary(5), RangeBoundary(40));
66 TEST_RANGE_OP(Range::Shl, -15, 100, 0, 64, RangeBoundary(kMinInt64),
67 RangeBoundary(kMaxInt64));
68 TEST_RANGE_OP(Range::Shl, -1, 1, 63, 63, RangeBoundary(kMinInt64),
69 RangeBoundary(kMaxInt64));
70 if (compiler::target::kSmiBits == 62) {
71 TEST_RANGE_OP_SMI(Range::Shl, -1, 1, 62, 62,
72 RangeBoundary(compiler::target::kSmiMin),
73 RangeBoundary(compiler::target::kSmiMax));
74 TEST_RANGE_OP_SMI(Range::Shl, -1, 1, 30, 30, RangeBoundary(-(1 << 30)),
75 RangeBoundary(1 << 30));
76 } else {
77 ASSERT(compiler::target::kSmiBits == 30);
78 TEST_RANGE_OP_SMI(Range::Shl, -1, 1, 30, 30,
79 RangeBoundary(compiler::target::kSmiMin),
80 RangeBoundary(compiler::target::kSmiMax));
81 TEST_RANGE_OP_SMI(Range::Shl, -1, 1, 62, 62,
82 RangeBoundary(compiler::target::kSmiMin),
83 RangeBoundary(compiler::target::kSmiMax));
84 }
85 TEST_RANGE_OP(Range::Shl, 0, 100, 0, 64, RangeBoundary(kMinInt64),
86 RangeBoundary(kMaxInt64));
87 TEST_RANGE_OP(Range::Shl, -100, 0, 0, 64, RangeBoundary(kMinInt64),
88 RangeBoundary(kMaxInt64));
89
90 TEST_RANGE_OP(Range::Shr, -8, 8, 1, 2, RangeBoundary(-4), RangeBoundary(4));
91 TEST_RANGE_OP(Range::Shr, 1, 8, 1, 2, RangeBoundary::FromConstant(0),
92 RangeBoundary(4));
93 TEST_RANGE_OP(Range::Shr, -16, -8, 1, 2, RangeBoundary(-8),
94 RangeBoundary(-2));
95 TEST_RANGE_OP(Range::Shr, 2, 4, -1, 1, RangeBoundary(1), RangeBoundary(4));
96 TEST_RANGE_OP(Range::Shr, kMaxInt64, kMaxInt64, 0, 1,
97 RangeBoundary(kMaxInt64 >> 1), RangeBoundary(kMaxInt64));
98 TEST_RANGE_OP(Range::Shr, kMinInt64, kMinInt64, 0, 1,
99 RangeBoundary(kMinInt64), RangeBoundary(kMinInt64 >> 1));
100#undef TEST_RANGE_OP
101}
102
103TEST_CASE(RangeTestsInt64Range) {
104 const Range fullInt64Range = Range::Full(RangeBoundary::kRangeBoundaryInt64);
105
106 Range* all = new Range(RangeBoundary(kMinInt64), RangeBoundary(kMaxInt64));
107 EXPECT(all->Equals(&fullInt64Range));
108 EXPECT(all->Overlaps(0, 0));
109 EXPECT(all->Overlaps(-1, 1));
110 EXPECT(!all->IsWithin(0, 100));
111
112 Range* positive =
113 new Range(RangeBoundary::FromConstant(0), RangeBoundary(kMaxInt64));
114 EXPECT(positive->Overlaps(0, 1));
115 EXPECT(positive->Overlaps(1, 100));
116 EXPECT(positive->Overlaps(-1, 0));
117
118 Range* negative =
119 new Range(RangeBoundary(kMinInt64), RangeBoundary::FromConstant(-1));
120 EXPECT(negative->Overlaps(-1, 0));
121 EXPECT(negative->Overlaps(-2, -1));
122
123 Range* negpos =
124 new Range(RangeBoundary(kMinInt64), RangeBoundary::FromConstant(0));
125 EXPECT(!negpos->IsPositive());
126
127 Range* c =
128 new Range(RangeBoundary(kMinInt64), RangeBoundary::FromConstant(32));
129
130 EXPECT(!c->OnlyLessThanOrEqualTo(31));
131}
132
133TEST_CASE(RangeUtils) {
134 // Use kMin/kMax instead of +/-inf as any range with a +/-inf bound is
135 // converted to the full int64 range due to wrap-around.
136 const RangeBoundary negativeInfinity =
137 RangeBoundary::FromConstant(RangeBoundary::kMin);
138 const RangeBoundary positiveInfinity =
139 RangeBoundary::FromConstant(RangeBoundary::kMax);
140
141 // [-inf, +inf].
142 const Range& range_0 = *(new Range(negativeInfinity, positiveInfinity));
143 // [-inf, -1].
144 const Range& range_a =
145 *(new Range(negativeInfinity, RangeBoundary::FromConstant(-1)));
146 // [-inf, 0].
147 const Range& range_b =
148 *(new Range(negativeInfinity, RangeBoundary::FromConstant(0)));
149 // [-inf, 1].
150 const Range& range_c =
151 *(new Range(negativeInfinity, RangeBoundary::FromConstant(1)));
152 // [-1, +inf]
153 const Range& range_d =
154 *(new Range(RangeBoundary::FromConstant(-1), positiveInfinity));
155 // [0, +inf]
156 const Range& range_e =
157 *(new Range(RangeBoundary::FromConstant(0), positiveInfinity));
158 // [1, +inf].
159 const Range& range_f =
160 *(new Range(RangeBoundary::FromConstant(1), positiveInfinity));
161 // [1, 2].
162 const Range& range_g = *(new Range(RangeBoundary::FromConstant(1),
163 RangeBoundary::FromConstant(2)));
164 // [-1, -2].
165 const Range& range_h = *(new Range(RangeBoundary::FromConstant(-1),
166 RangeBoundary::FromConstant(-2)));
167 // [-1, 1].
168 const Range& range_i = *(new Range(RangeBoundary::FromConstant(-1),
169 RangeBoundary::FromConstant(1)));
170
171 // OnlyPositiveOrZero.
172 EXPECT(!Range::OnlyPositiveOrZero(range_a, range_b));
173 EXPECT(!Range::OnlyPositiveOrZero(range_b, range_c));
174 EXPECT(!Range::OnlyPositiveOrZero(range_c, range_d));
175 EXPECT(!Range::OnlyPositiveOrZero(range_d, range_e));
176 EXPECT(Range::OnlyPositiveOrZero(range_e, range_f));
177 EXPECT(!Range::OnlyPositiveOrZero(range_d, range_d));
178 EXPECT(Range::OnlyPositiveOrZero(range_e, range_e));
179 EXPECT(Range::OnlyPositiveOrZero(range_f, range_g));
180 EXPECT(!Range::OnlyPositiveOrZero(range_g, range_h));
181 EXPECT(!Range::OnlyPositiveOrZero(range_i, range_i));
182
183 // OnlyNegativeOrZero.
184 EXPECT(Range::OnlyNegativeOrZero(range_a, range_b));
185 EXPECT(!Range::OnlyNegativeOrZero(range_b, range_c));
186 EXPECT(Range::OnlyNegativeOrZero(range_b, range_b));
187 EXPECT(!Range::OnlyNegativeOrZero(range_c, range_c));
188 EXPECT(!Range::OnlyNegativeOrZero(range_c, range_d));
189 EXPECT(!Range::OnlyNegativeOrZero(range_d, range_e));
190 EXPECT(!Range::OnlyNegativeOrZero(range_e, range_f));
191 EXPECT(!Range::OnlyNegativeOrZero(range_f, range_g));
192 EXPECT(!Range::OnlyNegativeOrZero(range_g, range_h));
193 EXPECT(Range::OnlyNegativeOrZero(range_h, range_h));
194 EXPECT(!Range::OnlyNegativeOrZero(range_i, range_i));
195
196 // [-inf, +inf].
197 EXPECT(!Range::OnlyNegativeOrZero(range_0, range_0));
198 EXPECT(!Range::OnlyPositiveOrZero(range_0, range_0));
199
200 EXPECT(Range::ConstantAbsMax(&range_0) == RangeBoundary::kMax);
201 EXPECT(Range::ConstantAbsMax(&range_h) == 2);
202 EXPECT(Range::ConstantAbsMax(&range_i) == 1);
203
204 // RangeBoundary.Equals.
205 EXPECT(RangeBoundary::FromConstant(1).Equals(RangeBoundary::FromConstant(1)));
206 EXPECT(
207 !RangeBoundary::FromConstant(2).Equals(RangeBoundary::FromConstant(1)));
208}
209
210TEST_CASE(RangeBinaryOp) {
211 Range* range_a = new Range(RangeBoundary::FromConstant(-1),
212 RangeBoundary::FromConstant(RangeBoundary::kMax));
213 range_a->Clamp(RangeBoundary::kRangeBoundaryInt32);
214 EXPECT(range_a->min().ConstantValue() == -1);
215 EXPECT(range_a->max().ConstantValue() == kMaxInt32);
216 range_a->set_max(RangeBoundary::FromConstant(RangeBoundary::kMax));
217
218 Range* range_b = new Range(RangeBoundary::FromConstant(RangeBoundary::kMin),
219 RangeBoundary::FromConstant(1));
220 range_b->Clamp(RangeBoundary::kRangeBoundaryInt32);
221 EXPECT(range_b->min().ConstantValue() == kMinInt32);
222 EXPECT(range_b->max().ConstantValue() == 1);
223 range_b->set_min(RangeBoundary::FromConstant(RangeBoundary::kMin));
224
225 {
226 Range result;
227 Range::BinaryOp(Token::kADD, range_a, range_b, nullptr, &result);
228 ASSERT(!Range::IsUnknown(&result));
229 EXPECT(result.min().Equals(
230 RangeBoundary::MinConstant(RangeBoundary::kRangeBoundaryInt64)));
231 EXPECT(result.max().Equals(
232 RangeBoundary::MaxConstant(RangeBoundary::kRangeBoundaryInt64)));
233 }
234
235 // Test that [5, 10] + [0, 5] = [5, 15].
236 Range* range_c = new Range(RangeBoundary::FromConstant(5),
237 RangeBoundary::FromConstant(10));
238 Range* range_d =
239 new Range(RangeBoundary::FromConstant(0), RangeBoundary::FromConstant(5));
240
241 {
242 Range result;
243 Range::BinaryOp(Token::kADD, range_c, range_d, nullptr, &result);
244 ASSERT(!Range::IsUnknown(&result));
245 EXPECT(result.min().ConstantValue() == 5);
246 EXPECT(result.max().ConstantValue() == 15);
247 }
248
249 // Test that [0xff, 0xfff] & [0xf, 0xf] = [0x0, 0xf].
250 Range* range_e = new Range(RangeBoundary::FromConstant(0xff),
251 RangeBoundary::FromConstant(0xfff));
252 Range* range_f = new Range(RangeBoundary::FromConstant(0xf),
253 RangeBoundary::FromConstant(0xf));
254 {
255 Range result;
256 Range::BinaryOp(Token::kBIT_AND, range_e, range_f, nullptr, &result);
257 ASSERT(!Range::IsUnknown(&result));
258 EXPECT(result.min().ConstantValue() == 0x0);
259 EXPECT(result.max().ConstantValue() == 0xf);
260 }
261}
262
263TEST_CASE(RangeAdd) {
264#define TEST_RANGE_ADD(l_min, l_max, r_min, r_max, result_min, result_max) \
265 { \
266 RangeBoundary min, max; \
267 Range* left_range = new Range(RangeBoundary::FromConstant(l_min), \
268 RangeBoundary::FromConstant(l_max)); \
269 Range* right_range = new Range(RangeBoundary::FromConstant(r_min), \
270 RangeBoundary::FromConstant(r_max)); \
271 EXPECT(left_range->min().ConstantValue() == l_min); \
272 EXPECT(left_range->max().ConstantValue() == l_max); \
273 EXPECT(right_range->min().ConstantValue() == r_min); \
274 EXPECT(right_range->max().ConstantValue() == r_max); \
275 Range::Add(left_range, right_range, &min, &max, nullptr); \
276 EXPECT(min.Equals(result_min)); \
277 if (FLAG_support_il_printer && !min.Equals(result_min)) { \
278 OS::PrintErr("%s != %s\n", min.ToCString(), result_min.ToCString()); \
279 } \
280 EXPECT(max.Equals(result_max)); \
281 if (FLAG_support_il_printer && !max.Equals(result_max)) { \
282 OS::PrintErr("%s != %s\n", max.ToCString(), result_max.ToCString()); \
283 } \
284 }
285
286 // [kMaxInt32, kMaxInt32 + 15] + [10, 20] = [kMaxInt32 + 10, kMaxInt32 + 35].
287 TEST_RANGE_ADD(static_cast<int64_t>(kMaxInt32),
288 static_cast<int64_t>(kMaxInt32) + 15, static_cast<int64_t>(10),
289 static_cast<int64_t>(20),
290 RangeBoundary(static_cast<int64_t>(kMaxInt32) + 10),
291 RangeBoundary(static_cast<int64_t>(kMaxInt32) + 35));
292
293 // [kMaxInt32 - 15, kMaxInt32 + 15] + [15, -15] = [kMaxInt32, kMaxInt32].
294 TEST_RANGE_ADD(static_cast<int64_t>(kMaxInt32) - 15,
295 static_cast<int64_t>(kMaxInt32) + 15, static_cast<int64_t>(15),
296 static_cast<int64_t>(-15),
297 RangeBoundary(static_cast<int64_t>(kMaxInt32)),
298 RangeBoundary(static_cast<int64_t>(kMaxInt32)));
299
300 // [kMaxInt32, kMaxInt32 + 15] + [10, kMaxInt64] = [kMinInt64, kMaxInt64].
301 TEST_RANGE_ADD(static_cast<int64_t>(kMaxInt32),
302 static_cast<int64_t>(kMaxInt32) + 15, static_cast<int64_t>(10),
303 static_cast<int64_t>(kMaxInt64), RangeBoundary(kMinInt64),
304 RangeBoundary(kMaxInt64));
305
306 // [kMinInt64, kMaxInt32 + 15] + [10, 20] = [kMinInt64 + 10, kMaxInt32 + 35].
307 TEST_RANGE_ADD(static_cast<int64_t>(kMinInt64),
308 static_cast<int64_t>(kMaxInt32) + 15, static_cast<int64_t>(10),
309 static_cast<int64_t>(20),
310 RangeBoundary(static_cast<int64_t>(kMinInt64) + 10),
311 RangeBoundary(static_cast<int64_t>(kMaxInt32) + 35));
312
313 // [0, 0] + [kMinInt64, kMaxInt64] = [kMinInt64, kMaxInt64].
314 TEST_RANGE_ADD(static_cast<int64_t>(0), static_cast<int64_t>(0),
315 static_cast<int64_t>(kMinInt64),
316 static_cast<int64_t>(kMaxInt64), RangeBoundary(kMinInt64),
317 RangeBoundary(kMaxInt64));
318
319 // Overflows.
320
321 // [-1, 1] + [kMinInt64, kMaxInt64] = [kMinInt64, kMaxInt64].
322 TEST_RANGE_ADD(static_cast<int64_t>(-1), static_cast<int64_t>(1),
323 static_cast<int64_t>(kMinInt64),
324 static_cast<int64_t>(kMaxInt64), RangeBoundary(kMinInt64),
325 RangeBoundary(kMaxInt64));
326
327 // [kMaxInt64, kMaxInt64] + [kMaxInt64, kMaxInt64] = [kMinInt64, kMaxInt64].
328 TEST_RANGE_ADD(
329 static_cast<int64_t>(kMaxInt64), static_cast<int64_t>(kMaxInt64),
330 static_cast<int64_t>(kMaxInt64), static_cast<int64_t>(kMaxInt64),
331 RangeBoundary(kMinInt64), RangeBoundary(kMaxInt64));
332
333 // [kMaxInt64, kMaxInt64] + [1, 1] = [kMinInt64, kMaxInt64].
334 TEST_RANGE_ADD(static_cast<int64_t>(kMaxInt64),
335 static_cast<int64_t>(kMaxInt64), static_cast<int64_t>(1),
336 static_cast<int64_t>(1), RangeBoundary(kMinInt64),
337 RangeBoundary(kMaxInt64));
338
339#undef TEST_RANGE_ADD
340}
341
342TEST_CASE(RangeSub) {
343#define TEST_RANGE_SUB(l_min, l_max, r_min, r_max, result_min, result_max) \
344 { \
345 RangeBoundary min, max; \
346 Range* left_range = new Range(RangeBoundary::FromConstant(l_min), \
347 RangeBoundary::FromConstant(l_max)); \
348 Range* right_range = new Range(RangeBoundary::FromConstant(r_min), \
349 RangeBoundary::FromConstant(r_max)); \
350 EXPECT(left_range->min().ConstantValue() == l_min); \
351 EXPECT(left_range->max().ConstantValue() == l_max); \
352 EXPECT(right_range->min().ConstantValue() == r_min); \
353 EXPECT(right_range->max().ConstantValue() == r_max); \
354 Range::Sub(left_range, right_range, &min, &max, nullptr); \
355 EXPECT(min.Equals(result_min)); \
356 if (FLAG_support_il_printer && !min.Equals(result_min)) { \
357 OS::PrintErr("%s != %s\n", min.ToCString(), result_min.ToCString()); \
358 } \
359 EXPECT(max.Equals(result_max)); \
360 if (FLAG_support_il_printer && !max.Equals(result_max)) { \
361 OS::PrintErr("%s != %s\n", max.ToCString(), result_max.ToCString()); \
362 } \
363 }
364
365 // [kMaxInt32, kMaxInt32 + 15] - [10, 20] = [kMaxInt32 - 20, kMaxInt32 + 5].
366 TEST_RANGE_SUB(static_cast<int64_t>(kMaxInt32),
367 static_cast<int64_t>(kMaxInt32) + 15, static_cast<int64_t>(10),
368 static_cast<int64_t>(20),
369 RangeBoundary(static_cast<int64_t>(kMaxInt32) - 20),
370 RangeBoundary(static_cast<int64_t>(kMaxInt32) + 5));
371
372 // [kMintInt64, kMintInt64] - [1, 1] = [kMinInt64, kMaxInt64].
373 TEST_RANGE_SUB(static_cast<int64_t>(kMinInt64),
374 static_cast<int64_t>(kMinInt64), static_cast<int64_t>(1),
375 static_cast<int64_t>(1), RangeBoundary(kMinInt64),
376 RangeBoundary(kMaxInt64));
377
378 // [1, 1] - [kMintInt64, kMintInt64] = [kMinInt64, kMaxInt64].
379 TEST_RANGE_SUB(static_cast<int64_t>(1), static_cast<int64_t>(1),
380 static_cast<int64_t>(kMinInt64),
381 static_cast<int64_t>(kMinInt64), RangeBoundary(kMinInt64),
382 RangeBoundary(kMaxInt64));
383
384 // [kMaxInt32 + 10, kMaxInt32 + 20] - [-20, -20] =
385 // [kMaxInt32 + 30, kMaxInt32 + 40].
386 TEST_RANGE_SUB(static_cast<int64_t>(kMaxInt32) + 10,
387 static_cast<int64_t>(kMaxInt32) + 20,
388 static_cast<int64_t>(-20), static_cast<int64_t>(-20),
389 RangeBoundary(static_cast<int64_t>(kMaxInt32) + 30),
390 RangeBoundary(static_cast<int64_t>(kMaxInt32) + 40));
391
392#undef TEST_RANGE_SUB
393}
394
395TEST_CASE(RangeAnd) {
396#define TEST_RANGE_AND(l_min, l_max, r_min, r_max, result_min, result_max) \
397 { \
398 RangeBoundary min, max; \
399 Range* left_range = new Range(RangeBoundary::FromConstant(l_min), \
400 RangeBoundary::FromConstant(l_max)); \
401 Range* right_range = new Range(RangeBoundary::FromConstant(r_min), \
402 RangeBoundary::FromConstant(r_max)); \
403 EXPECT(left_range->min().ConstantValue() == l_min); \
404 EXPECT(left_range->max().ConstantValue() == l_max); \
405 EXPECT(right_range->min().ConstantValue() == r_min); \
406 EXPECT(right_range->max().ConstantValue() == r_max); \
407 Range::And(left_range, right_range, &min, &max); \
408 EXPECT(min.Equals(result_min)); \
409 if (FLAG_support_il_printer && !min.Equals(result_min)) { \
410 OS::PrintErr("%s != %s\n", min.ToCString(), result_min.ToCString()); \
411 } \
412 EXPECT(max.Equals(result_max)); \
413 if (FLAG_support_il_printer && !max.Equals(result_max)) { \
414 OS::PrintErr("%s != %s\n", max.ToCString(), result_max.ToCString()); \
415 } \
416 }
417
418 // [0xff, 0xfff] & [0xf, 0xf] = [0x0, 0xf].
419 TEST_RANGE_AND(static_cast<int64_t>(0xff), static_cast<int64_t>(0xfff),
420 static_cast<int64_t>(0xf), static_cast<int64_t>(0xf),
421 RangeBoundary::FromConstant(0), RangeBoundary(0xf));
422
423 // [0xffffffff, 0xffffffff] & [0xfffffffff, 0xfffffffff] = [0x0, 0xfffffffff].
424 TEST_RANGE_AND(
425 static_cast<int64_t>(0xffffffff), static_cast<int64_t>(0xffffffff),
426 static_cast<int64_t>(0xfffffffff), static_cast<int64_t>(0xfffffffff),
427 RangeBoundary::FromConstant(0),
428 RangeBoundary(static_cast<int64_t>(0xfffffffff)));
429
430 // [0xffffffff, 0xffffffff] & [-20, 20] = [0x0, 0xffffffff].
431 TEST_RANGE_AND(static_cast<int64_t>(0xffffffff),
432 static_cast<int64_t>(0xffffffff), static_cast<int64_t>(-20),
433 static_cast<int64_t>(20), RangeBoundary::FromConstant(0),
434 RangeBoundary(static_cast<int64_t>(0xffffffff)));
435
436 // [-20, 20] & [0xffffffff, 0xffffffff] = [0x0, 0xffffffff].
437 TEST_RANGE_AND(static_cast<int64_t>(-20), static_cast<int64_t>(20),
438 static_cast<int64_t>(0xffffffff),
439 static_cast<int64_t>(0xffffffff),
440 RangeBoundary::FromConstant(0),
441 RangeBoundary(static_cast<int64_t>(0xffffffff)));
442
443 // Test that [-20, 20] & [-20, 20] = [-32, 31].
444 TEST_RANGE_AND(static_cast<int64_t>(-20), static_cast<int64_t>(20),
445 static_cast<int64_t>(-20), static_cast<int64_t>(20),
446 RangeBoundary(-32), RangeBoundary(31));
447
448#undef TEST_RANGE_AND
449}
450
451TEST_CASE(RangeIntersectionMinMax) {
452 // Test IntersectionMin and IntersectionMax methods which for constants are
453 // simply defined as Max/Min respectively.
454
455 // Constants.
456 // MIN(0, 1) == 0
457 EXPECT(RangeBoundary::IntersectionMax(RangeBoundary::FromConstant(0),
458 RangeBoundary::FromConstant(1))
459 .ConstantValue() == 0);
460 // MIN(0, -1) == -1
461 EXPECT(RangeBoundary::IntersectionMax(RangeBoundary::FromConstant(0),
462 RangeBoundary::FromConstant(-1))
463 .ConstantValue() == -1);
464
465 // MIN(1, 0) == 0
466 EXPECT(RangeBoundary::IntersectionMax(RangeBoundary::FromConstant(1),
467 RangeBoundary::FromConstant(0))
468 .ConstantValue() == 0);
469 // MIN(-1, 0) == -1
470 EXPECT(RangeBoundary::IntersectionMax(RangeBoundary::FromConstant(-1),
471 RangeBoundary::FromConstant(0))
472 .ConstantValue() == -1);
473
474 // MAX(0, 1) == 1
475 EXPECT(RangeBoundary::IntersectionMin(RangeBoundary::FromConstant(0),
476 RangeBoundary::FromConstant(1))
477 .ConstantValue() == 1);
478
479 // MAX(0, -1) == 0
480 EXPECT(RangeBoundary::IntersectionMin(RangeBoundary::FromConstant(0),
481 RangeBoundary::FromConstant(-1))
482 .ConstantValue() == 0);
483
484 // MAX(1, 0) == 1
485 EXPECT(RangeBoundary::IntersectionMin(RangeBoundary::FromConstant(1),
486 RangeBoundary::FromConstant(0))
487 .ConstantValue() == 1);
488 // MAX(-1, 0) == 0
489 EXPECT(RangeBoundary::IntersectionMin(RangeBoundary::FromConstant(-1),
490 RangeBoundary::FromConstant(0))
491 .ConstantValue() == 0);
492
493 // Constants vs. kMinInt64 / kMaxInt64.
494 EXPECT(RangeBoundary::IntersectionMin(RangeBoundary(kMinInt64),
495 RangeBoundary::FromConstant(-1))
496 .ConstantValue() == -1);
497
498 EXPECT(RangeBoundary::IntersectionMin(RangeBoundary::FromConstant(-1),
499 RangeBoundary(kMinInt64))
500 .ConstantValue() == -1);
501
502 EXPECT(RangeBoundary::IntersectionMin(RangeBoundary::FromConstant(1),
503 RangeBoundary(kMinInt64))
504 .ConstantValue() == 1);
505
506 EXPECT(RangeBoundary::IntersectionMin(RangeBoundary(kMinInt64),
507 RangeBoundary::FromConstant(1))
508 .ConstantValue() == 1);
509
510 EXPECT(RangeBoundary::IntersectionMax(RangeBoundary(kMaxInt64),
511 RangeBoundary::FromConstant(-1))
512 .ConstantValue() == -1);
513
514 EXPECT(RangeBoundary::IntersectionMax(RangeBoundary::FromConstant(-1),
515 RangeBoundary(kMaxInt64))
516 .ConstantValue() == -1);
517
518 EXPECT(RangeBoundary::IntersectionMax(RangeBoundary::FromConstant(1),
519 RangeBoundary(kMaxInt64))
520 .ConstantValue() == 1);
521
522 EXPECT(RangeBoundary::IntersectionMax(RangeBoundary(kMaxInt64),
523 RangeBoundary::FromConstant(1))
524 .ConstantValue() == 1);
525}
526
527TEST_CASE(RangeJoinMinMax) {
528 // Test IntersectionMin and IntersectionMax methods which for constants are
529 // simply defined as Min/Max respectively.
530 const RangeBoundary::RangeSize size = RangeBoundary::kRangeBoundarySmi;
531
532 // Constants.
533 EXPECT(RangeBoundary::JoinMax(RangeBoundary::FromConstant(0),
534 RangeBoundary::FromConstant(1), size)
535 .ConstantValue() == 1);
536 EXPECT(RangeBoundary::JoinMax(RangeBoundary::FromConstant(0),
537 RangeBoundary::FromConstant(-1), size)
538 .ConstantValue() == 0);
539 EXPECT(RangeBoundary::JoinMax(RangeBoundary::FromConstant(1),
540 RangeBoundary::FromConstant(0), size)
541 .ConstantValue() == 1);
542 EXPECT(RangeBoundary::JoinMax(RangeBoundary::FromConstant(-1),
543 RangeBoundary::FromConstant(0), size)
544 .ConstantValue() == 0);
545 EXPECT(RangeBoundary::JoinMin(RangeBoundary::FromConstant(0),
546 RangeBoundary::FromConstant(1), size)
547 .ConstantValue() == 0);
548 EXPECT(RangeBoundary::JoinMin(RangeBoundary::FromConstant(0),
549 RangeBoundary::FromConstant(-1), size)
550 .ConstantValue() == -1);
551 EXPECT(RangeBoundary::JoinMin(RangeBoundary::FromConstant(1),
552 RangeBoundary::FromConstant(0), size)
553 .ConstantValue() == 0);
554 EXPECT(RangeBoundary::JoinMin(RangeBoundary::FromConstant(-1),
555 RangeBoundary::FromConstant(0), size)
556 .ConstantValue() == -1);
557
558 // Constants vs. kMinInt64 / kMaxInt64.
559 EXPECT(RangeBoundary::JoinMin(RangeBoundary(kMinInt64),
560 RangeBoundary::FromConstant(-1), size)
561 .IsMinimumOrBelow(size));
562
563 EXPECT(RangeBoundary::JoinMin(RangeBoundary::FromConstant(-1),
564 RangeBoundary(kMinInt64), size)
565 .IsMinimumOrBelow(size));
566
567 EXPECT(RangeBoundary::JoinMin(RangeBoundary::FromConstant(1),
568 RangeBoundary(kMinInt64), size)
569 .IsMinimumOrBelow(size));
570
571 EXPECT(RangeBoundary::JoinMin(RangeBoundary(kMinInt64),
572 RangeBoundary::FromConstant(1), size)
573 .IsMinimumOrBelow(size));
574
575 EXPECT(RangeBoundary::JoinMax(RangeBoundary(kMaxInt64),
576 RangeBoundary::FromConstant(-1), size)
577 .IsMaximumOrAbove(size));
578
579 EXPECT(RangeBoundary::JoinMax(RangeBoundary::FromConstant(-1),
580 RangeBoundary(kMaxInt64), size)
581 .IsMaximumOrAbove(size));
582
583 EXPECT(RangeBoundary::JoinMax(RangeBoundary::FromConstant(1),
584 RangeBoundary(kMaxInt64), size)
585 .IsMaximumOrAbove(size));
586
587 EXPECT(RangeBoundary::JoinMax(RangeBoundary(kMaxInt64),
588 RangeBoundary::FromConstant(1), size)
589 .IsMaximumOrAbove(size));
590}
591
592#if defined(DART_PRECOMPILER) && defined(TARGET_ARCH_IS_64_BIT)
593
594// Regression test for https://github.com/dart-lang/sdk/issues/48153.
595ISOLATE_UNIT_TEST_CASE(RangeAnalysis_ShiftUint32Op) {
596 const char* kScript = R"(
597 @pragma('vm:never-inline')
598 int foo(int hash) {
599 return 0x1fffffff & (hash + ((0x0007ffff & hash) << 10));
600 }
601 void main() {
602 foo(42);
603 }
604 )";
605
606 const auto& root_library = Library::Handle(LoadTestScript(kScript));
607
608 Invoke(root_library, "main");
609
610 const auto& function = Function::Handle(GetFunction(root_library, "foo"));
611 TestPipeline pipeline(function, CompilerPass::kAOT);
612 FlowGraph* flow_graph = pipeline.RunPasses({});
613
614 auto entry = flow_graph->graph_entry()->normal_entry();
615 EXPECT(entry != nullptr);
616 ILMatcher cursor(flow_graph, entry, /*trace=*/true,
617 ParallelMovesHandling::kSkip);
618
619 ShiftUint32OpInstr* shift = nullptr;
620
621 RELEASE_ASSERT(cursor.TryMatch({
622 kMoveGlob,
623 kMatchAndMoveBinaryUint32Op,
624 kMoveGlob,
625 {kMatchAndMoveShiftUint32Op, &shift},
626 kMoveGlob,
627 kMatchAndMoveBinaryUint32Op,
628 kMoveGlob,
629 kMatchAndMoveBinaryUint32Op,
630 kMoveGlob,
631 kMatchDartReturn,
632 }));
633
634 EXPECT(shift->shift_range() != nullptr);
635 EXPECT(shift->shift_range()->min().ConstantValue() == 10);
636 EXPECT(shift->shift_range()->max().ConstantValue() == 10);
637}
638
639#endif // defined(DART_PRECOMPILER) && defined(TARGET_ARCH_IS_64_BIT)
640
641ISOLATE_UNIT_TEST_CASE(RangeAnalysis_LoadClassId) {
642 const char* kScript = R"(
643 @pragma('vm:never-inline')
644 bool foo(num x) {
645 return x is int;
646 }
647 void main() {
648 foo(42);
649 }
650 )";
651
652 const auto& root_library = Library::Handle(LoadTestScript(kScript));
653 Invoke(root_library, "main");
654
655 const auto& function = Function::Handle(GetFunction(root_library, "foo"));
656 TestPipeline pipeline(function, CompilerPass::kAOT);
657 FlowGraph* flow_graph = pipeline.RunPasses({});
658
659 auto entry = flow_graph->graph_entry()->normal_entry();
660 EXPECT(entry != nullptr);
661 ILMatcher cursor(flow_graph, entry, /*trace=*/true,
662 ParallelMovesHandling::kSkip);
663
664 LoadClassIdInstr* load_cid = nullptr;
665
666 RELEASE_ASSERT(cursor.TryMatch({
667 kMoveGlob,
668 {kMatchAndMoveLoadClassId, &load_cid},
669 kMoveGlob,
670 kMatchAndMoveTestRange,
671 kMoveGlob,
672 kMatchDartReturn,
673 }));
674
675 EXPECT(load_cid->range() != nullptr);
676 EXPECT(kSmiCid < kMintCid);
677 EXPECT(kMintCid < kDoubleCid);
678 EXPECT(load_cid->range()->min().ConstantValue() == kSmiCid);
679 EXPECT(load_cid->range()->max().ConstantValue() == kDoubleCid);
680}
681
682} // namespace dart
EXPECT
#define EXPECT(type, expectedAlignment, expectedSize)
Definition UniformOffsetCalculatorTest.cpp:33
RELEASE_ASSERT
#define RELEASE_ASSERT(cond)
Definition assert.h:327
dart::FlowGraph::graph_entry
GraphEntryInstr * graph_entry() const
Definition flow_graph.h:268
dart::GraphEntryInstr::normal_entry
FunctionEntryInstr * normal_entry() const
Definition il.h:1986
dart::ILMatcher::TryMatch
bool TryMatch(std::initializer_list< MatchCode > match_codes, MatchOpCode insert_before=kInvalidMatchOpCode)
Definition il_test_helper.cc:283
dart::Object::Handle
static Object & Handle()
Definition object.h:407
dart::RangeBoundary::MinConstant
static RangeBoundary MinConstant(RangeSize size)
Definition range_analysis.h:83
dart::RangeBoundary::kMin
static constexpr int64_t kMin
Definition range_analysis.h:54
dart::RangeBoundary::JoinMax
static RangeBoundary JoinMax(RangeBoundary a, RangeBoundary b, RangeBoundary::RangeSize size)
Definition range_analysis.cc:2009
dart::RangeBoundary::IntersectionMin
static RangeBoundary IntersectionMin(RangeBoundary a, RangeBoundary b)
Definition range_analysis.cc:2036
dart::RangeBoundary::IntersectionMax
static RangeBoundary IntersectionMax(RangeBoundary a, RangeBoundary b)
Definition range_analysis.cc:2065
dart::RangeBoundary::ConstantValue
int64_t ConstantValue() const
Definition range_analysis.cc:2094
dart::RangeBoundary::JoinMin
static RangeBoundary JoinMin(RangeBoundary a, RangeBoundary b, RangeBoundary::RangeSize size)
Definition range_analysis.cc:1983
dart::RangeBoundary::kMax
static constexpr int64_t kMax
Definition range_analysis.h:55
dart::RangeBoundary::MaxConstant
static RangeBoundary MaxConstant(RangeSize size)
Definition range_analysis.h:100
dart::RangeBoundary::FromConstant
static RangeBoundary FromConstant(int64_t val)
Definition range_analysis.h:58
dart::Range::ConstantAbsMax
static int64_t ConstantAbsMax(const Range *range)
Definition range_analysis.cc:2550
dart::Range::OnlyNegativeOrZero
static bool OnlyNegativeOrZero(const Range &a, const Range &b)
Definition range_analysis.cc:2545
dart::Range::IsPositive
bool IsPositive() const
Definition range_analysis.cc:2126
dart::Range::set_max
void set_max(const RangeBoundary &value)
Definition range_analysis.h:324
dart::Range::Shr
static void Shr(const Range *left_range, const Range *right_range, RangeBoundary *min, RangeBoundary *max)
Definition range_analysis.cc:2229
dart::Range::IsWithin
bool IsWithin(int64_t min_int, int64_t max_int) const
Definition range_analysis.cc:2145
dart::Range::OnlyPositiveOrZero
static bool OnlyPositiveOrZero(const Range &a, const Range &b)
Definition range_analysis.cc:2540
dart::Range::IsUnknown
static bool IsUnknown(const Range *other)
Definition range_analysis.h:294
dart::Range::min
const RangeBoundary & min() const
Definition range_analysis.h:319
dart::Range::BinaryOp
static void BinaryOp(const Token::Kind op, const Range *left_range, const Range *right_range, Definition *left_defn, Range *result)
Definition range_analysis.cc:2573
dart::Range::max
const RangeBoundary & max() const
Definition range_analysis.h:320
dart::Range::Full
static Range Full(RangeBoundary::RangeSize size)
Definition range_analysis.h:301
dart::Range::Clamp
void Clamp(RangeBoundary::RangeSize size)
Definition range_analysis.cc:2176
dart::Range::Shl
static void Shl(const Range *left_range, const Range *right_range, RangeBoundary *min, RangeBoundary *max)
Definition range_analysis.cc:2186
dart::Range::set_min
void set_min(const RangeBoundary &value)
Definition range_analysis.h:322
dart::Range::OnlyLessThanOrEqualTo
bool OnlyLessThanOrEqualTo(int64_t val) const
Definition range_analysis.cc:2134
dart::Range::Overlaps
bool Overlaps(int64_t min_int, int64_t max_int) const
Definition range_analysis.cc:2155
dart::TestPipeline::RunPasses
FlowGraph * RunPasses(std::initializer_list< CompilerPass::Id > passes)
Definition il_test_helper.cc:116
ASSERT
#define ASSERT(E)
Definition entrypoints_verification_test.cc:25
result
GAsyncResult * result
Definition fl_text_input_plugin.cc:106
function
Dart_NativeFunction function
Definition fuchsia.cc:51
il_test_helper.h
dart::kMaxInt64
constexpr int64_t kMaxInt64
Definition globals.h:486
dart::Equals
static bool Equals(const Object &expected, const Object &actual)
Definition snapshot_test.cc:26
dart::kMinInt64
constexpr int64_t kMinInt64
Definition globals.h:485
dart::LoadTestScript
LibraryPtr LoadTestScript(const char *script, Dart_NativeEntryResolver resolver, const char *lib_uri)
Definition il_test_helper.cc:26
dart::kMinInt32
constexpr int32_t kMinInt32
Definition globals.h:482
dart::Invoke
ObjectPtr Invoke(const Library &lib, const char *name)
Definition il_test_helper.cc:84
dart::GetFunction
FunctionPtr GetFunction(const Library &lib, const char *name)
Definition il_test_helper.cc:56
dart::kMaxInt32
constexpr int32_t kMaxInt32
Definition globals.h:483
range_analysis.h
TEST_RANGE_AND
#define TEST_RANGE_AND(l_min, l_max, r_min, r_max, result_min, result_max)
TEST_RANGE_SUB
#define TEST_RANGE_SUB(l_min, l_max, r_min, r_max, result_min, result_max)
TEST_RANGE_ADD
#define TEST_RANGE_ADD(l_min, l_max, r_min, r_max, result_min, result_max)
TEST_RANGE_OP
#define TEST_RANGE_OP(Op, l_min, l_max, r_min, r_max, result_min, result_max)
TEST_RANGE_OP_SMI
#define TEST_RANGE_OP_SMI(Op, l_min, l_max, r_min, r_max, res_min, res_max)
unit_test.h
ISOLATE_UNIT_TEST_CASE
#define ISOLATE_UNIT_TEST_CASE(name)
Definition unit_test.h:64
TEST_CASE
#define TEST_CASE(name)
Definition unit_test.h:85
Generated on Fri Apr 26 2024 06:14:57 for Flutter Engine by doxygen 1.9.8