1 //===- ConstantRangeTest.cpp - ConstantRange tests ------------------------===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 #include "llvm/ADT/BitVector.h"
10 #include "llvm/IR/ConstantRange.h"
11 #include "llvm/IR/Instructions.h"
12 #include "llvm/IR/Operator.h"
13 #include "llvm/Support/KnownBits.h"
14 #include "gtest/gtest.h"
20 class ConstantRangeTest
: public ::testing::Test
{
22 static ConstantRange Full
;
23 static ConstantRange Empty
;
24 static ConstantRange One
;
25 static ConstantRange Some
;
26 static ConstantRange Wrap
;
30 static void EnumerateConstantRanges(unsigned Bits
, Fn TestFn
) {
31 unsigned Max
= 1 << Bits
;
32 for (unsigned Lo
= 0; Lo
< Max
; Lo
++) {
33 for (unsigned Hi
= 0; Hi
< Max
; Hi
++) {
34 // Enforce ConstantRange invariant.
35 if (Lo
== Hi
&& Lo
!= 0 && Lo
!= Max
- 1)
38 ConstantRange
CR(APInt(Bits
, Lo
), APInt(Bits
, Hi
));
45 static void EnumerateTwoConstantRanges(unsigned Bits
, Fn TestFn
) {
46 EnumerateConstantRanges(Bits
, [&](const ConstantRange
&CR1
) {
47 EnumerateConstantRanges(Bits
, [&](const ConstantRange
&CR2
) {
54 static void ForeachNumInConstantRange(const ConstantRange
&CR
, Fn TestFn
) {
55 if (!CR
.isEmptySet()) {
56 APInt N
= CR
.getLower();
58 while (++N
!= CR
.getUpper());
62 template<typename Fn1
, typename Fn2
>
63 static void TestUnsignedBinOpExhaustive(
64 Fn1 RangeFn
, Fn2 IntFn
,
65 bool SkipZeroRHS
= false, bool CorrectnessOnly
= false) {
67 EnumerateTwoConstantRanges(Bits
, [&](const ConstantRange
&CR1
,
68 const ConstantRange
&CR2
) {
69 APInt Min
= APInt::getMaxValue(Bits
);
70 APInt Max
= APInt::getMinValue(Bits
);
71 ForeachNumInConstantRange(CR1
, [&](const APInt
&N1
) {
72 ForeachNumInConstantRange(CR2
, [&](const APInt
&N2
) {
73 if (SkipZeroRHS
&& N2
== 0)
76 APInt N
= IntFn(N1
, N2
);
84 ConstantRange CR
= RangeFn(CR1
, CR2
);
86 EXPECT_TRUE(CR
.isEmptySet());
90 ConstantRange Exact
= ConstantRange::getNonEmpty(Min
, Max
+ 1);
91 if (CorrectnessOnly
) {
92 EXPECT_TRUE(CR
.contains(Exact
));
99 template<typename Fn1
, typename Fn2
>
100 static void TestSignedBinOpExhaustive(
101 Fn1 RangeFn
, Fn2 IntFn
,
102 bool SkipZeroRHS
= false, bool CorrectnessOnly
= false) {
104 EnumerateTwoConstantRanges(Bits
, [&](const ConstantRange
&CR1
,
105 const ConstantRange
&CR2
) {
106 APInt Min
= APInt::getSignedMaxValue(Bits
);
107 APInt Max
= APInt::getSignedMinValue(Bits
);
108 ForeachNumInConstantRange(CR1
, [&](const APInt
&N1
) {
109 ForeachNumInConstantRange(CR2
, [&](const APInt
&N2
) {
110 if (SkipZeroRHS
&& N2
== 0)
113 APInt N
= IntFn(N1
, N2
);
121 ConstantRange CR
= RangeFn(CR1
, CR2
);
123 EXPECT_TRUE(CR
.isEmptySet());
127 ConstantRange Exact
= ConstantRange::getNonEmpty(Min
, Max
+ 1);
128 if (CorrectnessOnly
) {
129 EXPECT_TRUE(CR
.contains(Exact
));
131 EXPECT_EQ(Exact
, CR
);
136 ConstantRange
ConstantRangeTest::Full(16, true);
137 ConstantRange
ConstantRangeTest::Empty(16, false);
138 ConstantRange
ConstantRangeTest::One(APInt(16, 0xa));
139 ConstantRange
ConstantRangeTest::Some(APInt(16, 0xa), APInt(16, 0xaaa));
140 ConstantRange
ConstantRangeTest::Wrap(APInt(16, 0xaaa), APInt(16, 0xa));
142 TEST_F(ConstantRangeTest
, Basics
) {
143 EXPECT_TRUE(Full
.isFullSet());
144 EXPECT_FALSE(Full
.isEmptySet());
145 EXPECT_TRUE(Full
.inverse().isEmptySet());
146 EXPECT_FALSE(Full
.isWrappedSet());
147 EXPECT_TRUE(Full
.contains(APInt(16, 0x0)));
148 EXPECT_TRUE(Full
.contains(APInt(16, 0x9)));
149 EXPECT_TRUE(Full
.contains(APInt(16, 0xa)));
150 EXPECT_TRUE(Full
.contains(APInt(16, 0xaa9)));
151 EXPECT_TRUE(Full
.contains(APInt(16, 0xaaa)));
153 EXPECT_FALSE(Empty
.isFullSet());
154 EXPECT_TRUE(Empty
.isEmptySet());
155 EXPECT_TRUE(Empty
.inverse().isFullSet());
156 EXPECT_FALSE(Empty
.isWrappedSet());
157 EXPECT_FALSE(Empty
.contains(APInt(16, 0x0)));
158 EXPECT_FALSE(Empty
.contains(APInt(16, 0x9)));
159 EXPECT_FALSE(Empty
.contains(APInt(16, 0xa)));
160 EXPECT_FALSE(Empty
.contains(APInt(16, 0xaa9)));
161 EXPECT_FALSE(Empty
.contains(APInt(16, 0xaaa)));
163 EXPECT_FALSE(One
.isFullSet());
164 EXPECT_FALSE(One
.isEmptySet());
165 EXPECT_FALSE(One
.isWrappedSet());
166 EXPECT_FALSE(One
.contains(APInt(16, 0x0)));
167 EXPECT_FALSE(One
.contains(APInt(16, 0x9)));
168 EXPECT_TRUE(One
.contains(APInt(16, 0xa)));
169 EXPECT_FALSE(One
.contains(APInt(16, 0xaa9)));
170 EXPECT_FALSE(One
.contains(APInt(16, 0xaaa)));
171 EXPECT_FALSE(One
.inverse().contains(APInt(16, 0xa)));
173 EXPECT_FALSE(Some
.isFullSet());
174 EXPECT_FALSE(Some
.isEmptySet());
175 EXPECT_FALSE(Some
.isWrappedSet());
176 EXPECT_FALSE(Some
.contains(APInt(16, 0x0)));
177 EXPECT_FALSE(Some
.contains(APInt(16, 0x9)));
178 EXPECT_TRUE(Some
.contains(APInt(16, 0xa)));
179 EXPECT_TRUE(Some
.contains(APInt(16, 0xaa9)));
180 EXPECT_FALSE(Some
.contains(APInt(16, 0xaaa)));
182 EXPECT_FALSE(Wrap
.isFullSet());
183 EXPECT_FALSE(Wrap
.isEmptySet());
184 EXPECT_TRUE(Wrap
.isWrappedSet());
185 EXPECT_TRUE(Wrap
.contains(APInt(16, 0x0)));
186 EXPECT_TRUE(Wrap
.contains(APInt(16, 0x9)));
187 EXPECT_FALSE(Wrap
.contains(APInt(16, 0xa)));
188 EXPECT_FALSE(Wrap
.contains(APInt(16, 0xaa9)));
189 EXPECT_TRUE(Wrap
.contains(APInt(16, 0xaaa)));
192 TEST_F(ConstantRangeTest
, Equality
) {
193 EXPECT_EQ(Full
, Full
);
194 EXPECT_EQ(Empty
, Empty
);
196 EXPECT_EQ(Some
, Some
);
197 EXPECT_EQ(Wrap
, Wrap
);
198 EXPECT_NE(Full
, Empty
);
199 EXPECT_NE(Full
, One
);
200 EXPECT_NE(Full
, Some
);
201 EXPECT_NE(Full
, Wrap
);
202 EXPECT_NE(Empty
, One
);
203 EXPECT_NE(Empty
, Some
);
204 EXPECT_NE(Empty
, Wrap
);
205 EXPECT_NE(One
, Some
);
206 EXPECT_NE(One
, Wrap
);
207 EXPECT_NE(Some
, Wrap
);
210 TEST_F(ConstantRangeTest
, SingleElement
) {
211 EXPECT_EQ(Full
.getSingleElement(), static_cast<APInt
*>(nullptr));
212 EXPECT_EQ(Empty
.getSingleElement(), static_cast<APInt
*>(nullptr));
213 EXPECT_EQ(Full
.getSingleMissingElement(), static_cast<APInt
*>(nullptr));
214 EXPECT_EQ(Empty
.getSingleMissingElement(), static_cast<APInt
*>(nullptr));
216 EXPECT_EQ(*One
.getSingleElement(), APInt(16, 0xa));
217 EXPECT_EQ(Some
.getSingleElement(), static_cast<APInt
*>(nullptr));
218 EXPECT_EQ(Wrap
.getSingleElement(), static_cast<APInt
*>(nullptr));
220 EXPECT_EQ(One
.getSingleMissingElement(), static_cast<APInt
*>(nullptr));
221 EXPECT_EQ(Some
.getSingleMissingElement(), static_cast<APInt
*>(nullptr));
223 ConstantRange OneInverse
= One
.inverse();
224 EXPECT_EQ(*OneInverse
.getSingleMissingElement(), *One
.getSingleElement());
226 EXPECT_FALSE(Full
.isSingleElement());
227 EXPECT_FALSE(Empty
.isSingleElement());
228 EXPECT_TRUE(One
.isSingleElement());
229 EXPECT_FALSE(Some
.isSingleElement());
230 EXPECT_FALSE(Wrap
.isSingleElement());
233 TEST_F(ConstantRangeTest
, GetMinsAndMaxes
) {
234 EXPECT_EQ(Full
.getUnsignedMax(), APInt(16, UINT16_MAX
));
235 EXPECT_EQ(One
.getUnsignedMax(), APInt(16, 0xa));
236 EXPECT_EQ(Some
.getUnsignedMax(), APInt(16, 0xaa9));
237 EXPECT_EQ(Wrap
.getUnsignedMax(), APInt(16, UINT16_MAX
));
239 EXPECT_EQ(Full
.getUnsignedMin(), APInt(16, 0));
240 EXPECT_EQ(One
.getUnsignedMin(), APInt(16, 0xa));
241 EXPECT_EQ(Some
.getUnsignedMin(), APInt(16, 0xa));
242 EXPECT_EQ(Wrap
.getUnsignedMin(), APInt(16, 0));
244 EXPECT_EQ(Full
.getSignedMax(), APInt(16, INT16_MAX
));
245 EXPECT_EQ(One
.getSignedMax(), APInt(16, 0xa));
246 EXPECT_EQ(Some
.getSignedMax(), APInt(16, 0xaa9));
247 EXPECT_EQ(Wrap
.getSignedMax(), APInt(16, INT16_MAX
));
249 EXPECT_EQ(Full
.getSignedMin(), APInt(16, (uint64_t)INT16_MIN
));
250 EXPECT_EQ(One
.getSignedMin(), APInt(16, 0xa));
251 EXPECT_EQ(Some
.getSignedMin(), APInt(16, 0xa));
252 EXPECT_EQ(Wrap
.getSignedMin(), APInt(16, (uint64_t)INT16_MIN
));
255 EXPECT_EQ(ConstantRange(APInt(4, 7), APInt(4, 0)).getSignedMax(),
259 TEST_F(ConstantRangeTest
, SignWrapped
) {
260 EXPECT_FALSE(Full
.isSignWrappedSet());
261 EXPECT_FALSE(Empty
.isSignWrappedSet());
262 EXPECT_FALSE(One
.isSignWrappedSet());
263 EXPECT_FALSE(Some
.isSignWrappedSet());
264 EXPECT_TRUE(Wrap
.isSignWrappedSet());
266 EXPECT_FALSE(ConstantRange(APInt(8, 127), APInt(8, 128)).isSignWrappedSet());
267 EXPECT_TRUE(ConstantRange(APInt(8, 127), APInt(8, 129)).isSignWrappedSet());
268 EXPECT_FALSE(ConstantRange(APInt(8, 128), APInt(8, 129)).isSignWrappedSet());
269 EXPECT_TRUE(ConstantRange(APInt(8, 10), APInt(8, 9)).isSignWrappedSet());
270 EXPECT_TRUE(ConstantRange(APInt(8, 10), APInt(8, 250)).isSignWrappedSet());
271 EXPECT_FALSE(ConstantRange(APInt(8, 250), APInt(8, 10)).isSignWrappedSet());
272 EXPECT_FALSE(ConstantRange(APInt(8, 250), APInt(8, 251)).isSignWrappedSet());
275 TEST_F(ConstantRangeTest
, UpperWrapped
) {
276 // The behavior here is the same as for isWrappedSet() / isSignWrappedSet().
277 EXPECT_FALSE(Full
.isUpperWrapped());
278 EXPECT_FALSE(Empty
.isUpperWrapped());
279 EXPECT_FALSE(One
.isUpperWrapped());
280 EXPECT_FALSE(Some
.isUpperWrapped());
281 EXPECT_TRUE(Wrap
.isUpperWrapped());
282 EXPECT_FALSE(Full
.isUpperSignWrapped());
283 EXPECT_FALSE(Empty
.isUpperSignWrapped());
284 EXPECT_FALSE(One
.isUpperSignWrapped());
285 EXPECT_FALSE(Some
.isUpperSignWrapped());
286 EXPECT_TRUE(Wrap
.isUpperSignWrapped());
288 // The behavior differs if Upper is the Min/SignedMin value.
289 ConstantRange
CR1(APInt(8, 42), APInt::getMinValue(8));
290 EXPECT_FALSE(CR1
.isWrappedSet());
291 EXPECT_TRUE(CR1
.isUpperWrapped());
293 ConstantRange
CR2(APInt(8, 42), APInt::getSignedMinValue(8));
294 EXPECT_FALSE(CR2
.isSignWrappedSet());
295 EXPECT_TRUE(CR2
.isUpperSignWrapped());
298 TEST_F(ConstantRangeTest
, Trunc
) {
299 ConstantRange TFull
= Full
.truncate(10);
300 ConstantRange TEmpty
= Empty
.truncate(10);
301 ConstantRange TOne
= One
.truncate(10);
302 ConstantRange TSome
= Some
.truncate(10);
303 ConstantRange TWrap
= Wrap
.truncate(10);
304 EXPECT_TRUE(TFull
.isFullSet());
305 EXPECT_TRUE(TEmpty
.isEmptySet());
306 EXPECT_EQ(TOne
, ConstantRange(One
.getLower().trunc(10),
307 One
.getUpper().trunc(10)));
308 EXPECT_TRUE(TSome
.isFullSet());
309 EXPECT_TRUE(TWrap
.isFullSet());
311 // trunc([2, 5), 3->2) = [2, 1)
312 ConstantRange
TwoFive(APInt(3, 2), APInt(3, 5));
313 EXPECT_EQ(TwoFive
.truncate(2), ConstantRange(APInt(2, 2), APInt(2, 1)));
315 // trunc([2, 6), 3->2) = full
316 ConstantRange
TwoSix(APInt(3, 2), APInt(3, 6));
317 EXPECT_TRUE(TwoSix
.truncate(2).isFullSet());
319 // trunc([5, 7), 3->2) = [1, 3)
320 ConstantRange
FiveSeven(APInt(3, 5), APInt(3, 7));
321 EXPECT_EQ(FiveSeven
.truncate(2), ConstantRange(APInt(2, 1), APInt(2, 3)));
323 // trunc([7, 1), 3->2) = [3, 1)
324 ConstantRange
SevenOne(APInt(3, 7), APInt(3, 1));
325 EXPECT_EQ(SevenOne
.truncate(2), ConstantRange(APInt(2, 3), APInt(2, 1)));
328 TEST_F(ConstantRangeTest
, ZExt
) {
329 ConstantRange ZFull
= Full
.zeroExtend(20);
330 ConstantRange ZEmpty
= Empty
.zeroExtend(20);
331 ConstantRange ZOne
= One
.zeroExtend(20);
332 ConstantRange ZSome
= Some
.zeroExtend(20);
333 ConstantRange ZWrap
= Wrap
.zeroExtend(20);
334 EXPECT_EQ(ZFull
, ConstantRange(APInt(20, 0), APInt(20, 0x10000)));
335 EXPECT_TRUE(ZEmpty
.isEmptySet());
336 EXPECT_EQ(ZOne
, ConstantRange(One
.getLower().zext(20),
337 One
.getUpper().zext(20)));
338 EXPECT_EQ(ZSome
, ConstantRange(Some
.getLower().zext(20),
339 Some
.getUpper().zext(20)));
340 EXPECT_EQ(ZWrap
, ConstantRange(APInt(20, 0), APInt(20, 0x10000)));
342 // zext([5, 0), 3->7) = [5, 8)
343 ConstantRange
FiveZero(APInt(3, 5), APInt(3, 0));
344 EXPECT_EQ(FiveZero
.zeroExtend(7), ConstantRange(APInt(7, 5), APInt(7, 8)));
347 TEST_F(ConstantRangeTest
, SExt
) {
348 ConstantRange SFull
= Full
.signExtend(20);
349 ConstantRange SEmpty
= Empty
.signExtend(20);
350 ConstantRange SOne
= One
.signExtend(20);
351 ConstantRange SSome
= Some
.signExtend(20);
352 ConstantRange SWrap
= Wrap
.signExtend(20);
353 EXPECT_EQ(SFull
, ConstantRange(APInt(20, (uint64_t)INT16_MIN
, true),
354 APInt(20, INT16_MAX
+ 1, true)));
355 EXPECT_TRUE(SEmpty
.isEmptySet());
356 EXPECT_EQ(SOne
, ConstantRange(One
.getLower().sext(20),
357 One
.getUpper().sext(20)));
358 EXPECT_EQ(SSome
, ConstantRange(Some
.getLower().sext(20),
359 Some
.getUpper().sext(20)));
360 EXPECT_EQ(SWrap
, ConstantRange(APInt(20, (uint64_t)INT16_MIN
, true),
361 APInt(20, INT16_MAX
+ 1, true)));
363 EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, 140)).signExtend(16),
364 ConstantRange(APInt(16, -128), APInt(16, 128)));
366 EXPECT_EQ(ConstantRange(APInt(16, 0x0200), APInt(16, 0x8000)).signExtend(19),
367 ConstantRange(APInt(19, 0x0200), APInt(19, 0x8000)));
370 TEST_F(ConstantRangeTest
, IntersectWith
) {
371 EXPECT_EQ(Empty
.intersectWith(Full
), Empty
);
372 EXPECT_EQ(Empty
.intersectWith(Empty
), Empty
);
373 EXPECT_EQ(Empty
.intersectWith(One
), Empty
);
374 EXPECT_EQ(Empty
.intersectWith(Some
), Empty
);
375 EXPECT_EQ(Empty
.intersectWith(Wrap
), Empty
);
376 EXPECT_EQ(Full
.intersectWith(Full
), Full
);
377 EXPECT_EQ(Some
.intersectWith(Some
), Some
);
378 EXPECT_EQ(Some
.intersectWith(One
), One
);
379 EXPECT_EQ(Full
.intersectWith(One
), One
);
380 EXPECT_EQ(Full
.intersectWith(Some
), Some
);
381 EXPECT_EQ(Some
.intersectWith(Wrap
), Empty
);
382 EXPECT_EQ(One
.intersectWith(Wrap
), Empty
);
383 EXPECT_EQ(One
.intersectWith(Wrap
), Wrap
.intersectWith(One
));
385 // Klee generated testcase from PR4545.
386 // The intersection of i16 [4, 2) and [6, 5) is disjoint, looking like
387 // 01..4.6789ABCDEF where the dots represent values not in the intersection.
388 ConstantRange
LHS(APInt(16, 4), APInt(16, 2));
389 ConstantRange
RHS(APInt(16, 6), APInt(16, 5));
390 EXPECT_TRUE(LHS
.intersectWith(RHS
) == LHS
);
392 // previous bug: intersection of [min, 3) and [2, max) should be 2
393 LHS
= ConstantRange(APInt(32, -2147483646), APInt(32, 3));
394 RHS
= ConstantRange(APInt(32, 2), APInt(32, 2147483646));
395 EXPECT_EQ(LHS
.intersectWith(RHS
), ConstantRange(APInt(32, 2)));
397 // [2, 0) /\ [4, 3) = [2, 0)
398 LHS
= ConstantRange(APInt(32, 2), APInt(32, 0));
399 RHS
= ConstantRange(APInt(32, 4), APInt(32, 3));
400 EXPECT_EQ(LHS
.intersectWith(RHS
), ConstantRange(APInt(32, 2), APInt(32, 0)));
402 // [2, 0) /\ [4, 2) = [4, 0)
403 LHS
= ConstantRange(APInt(32, 2), APInt(32, 0));
404 RHS
= ConstantRange(APInt(32, 4), APInt(32, 2));
405 EXPECT_EQ(LHS
.intersectWith(RHS
), ConstantRange(APInt(32, 4), APInt(32, 0)));
407 // [4, 2) /\ [5, 1) = [5, 1)
408 LHS
= ConstantRange(APInt(32, 4), APInt(32, 2));
409 RHS
= ConstantRange(APInt(32, 5), APInt(32, 1));
410 EXPECT_EQ(LHS
.intersectWith(RHS
), ConstantRange(APInt(32, 5), APInt(32, 1)));
412 // [2, 0) /\ [7, 4) = [7, 4)
413 LHS
= ConstantRange(APInt(32, 2), APInt(32, 0));
414 RHS
= ConstantRange(APInt(32, 7), APInt(32, 4));
415 EXPECT_EQ(LHS
.intersectWith(RHS
), ConstantRange(APInt(32, 7), APInt(32, 4)));
417 // [4, 2) /\ [1, 0) = [1, 0)
418 LHS
= ConstantRange(APInt(32, 4), APInt(32, 2));
419 RHS
= ConstantRange(APInt(32, 1), APInt(32, 0));
420 EXPECT_EQ(LHS
.intersectWith(RHS
), ConstantRange(APInt(32, 4), APInt(32, 2)));
422 // [15, 0) /\ [7, 6) = [15, 0)
423 LHS
= ConstantRange(APInt(32, 15), APInt(32, 0));
424 RHS
= ConstantRange(APInt(32, 7), APInt(32, 6));
425 EXPECT_EQ(LHS
.intersectWith(RHS
), ConstantRange(APInt(32, 15), APInt(32, 0)));
428 template<typename Fn1
, typename Fn2
>
429 void testBinarySetOperationExhaustive(Fn1 OpFn
, Fn2 InResultFn
) {
431 EnumerateTwoConstantRanges(Bits
,
432 [=](const ConstantRange
&CR1
, const ConstantRange
&CR2
) {
433 // Collect up to three contiguous unsigned ranges. The HaveInterrupt
434 // variables are used determine when we have to switch to the next
435 // range because the previous one ended.
436 APInt
Lower1(Bits
, 0), Upper1(Bits
, 0);
437 APInt
Lower2(Bits
, 0), Upper2(Bits
, 0);
438 APInt
Lower3(Bits
, 0), Upper3(Bits
, 0);
439 bool HaveRange1
= false, HaveInterrupt1
= false;
440 bool HaveRange2
= false, HaveInterrupt2
= false;
441 bool HaveRange3
= false, HaveInterrupt3
= false;
444 for (unsigned I
= 0, Limit
= 1 << Bits
; I
< Limit
; ++I
, ++Num
) {
445 if (!InResultFn(CR1
, CR2
, Num
)) {
447 HaveInterrupt3
= true;
449 HaveInterrupt2
= true;
451 HaveInterrupt1
= true;
457 } else if (HaveInterrupt2
) {
459 Lower3
= Upper3
= Num
;
460 } else if (HaveRange2
) {
462 } else if (HaveInterrupt1
) {
464 Lower2
= Upper2
= Num
;
465 } else if (HaveRange1
) {
469 Lower1
= Upper1
= Num
;
473 (void)HaveInterrupt3
;
474 assert(!HaveInterrupt3
&& "Should have at most three ranges");
476 ConstantRange SmallestCR
= OpFn(CR1
, CR2
, ConstantRange::Smallest
);
477 ConstantRange UnsignedCR
= OpFn(CR1
, CR2
, ConstantRange::Unsigned
);
478 ConstantRange SignedCR
= OpFn(CR1
, CR2
, ConstantRange::Signed
);
481 EXPECT_TRUE(SmallestCR
.isEmptySet());
482 EXPECT_TRUE(UnsignedCR
.isEmptySet());
483 EXPECT_TRUE(SignedCR
.isEmptySet());
488 if (Lower1
== Upper1
+ 1) {
489 EXPECT_TRUE(SmallestCR
.isFullSet());
490 EXPECT_TRUE(UnsignedCR
.isFullSet());
491 EXPECT_TRUE(SignedCR
.isFullSet());
493 ConstantRange
Expected(Lower1
, Upper1
+ 1);
494 EXPECT_EQ(Expected
, SmallestCR
);
495 EXPECT_EQ(Expected
, UnsignedCR
);
496 EXPECT_EQ(Expected
, SignedCR
);
501 ConstantRange
Variant1(Bits
, /*full*/ true);
502 ConstantRange
Variant2(Bits
, /*full*/ true);
504 // Compute the two possible ways to cover two disjoint ranges.
505 if (Lower1
!= Upper2
+ 1)
506 Variant1
= ConstantRange(Lower1
, Upper2
+ 1);
507 if (Lower2
!= Upper1
+ 1)
508 Variant2
= ConstantRange(Lower2
, Upper1
+ 1);
510 // If we have three ranges, the first and last one have to be adjacent
511 // to the unsigned domain. It's better to think of this as having two
512 // holes, and we can construct one range using each hole.
513 assert(Lower1
.isNullValue() && Upper3
.isMaxValue());
514 Variant1
= ConstantRange(Lower2
, Upper1
+ 1);
515 Variant2
= ConstantRange(Lower3
, Upper2
+ 1);
518 // Smallest: Smaller set, then any set.
519 if (Variant1
.isSizeStrictlySmallerThan(Variant2
))
520 EXPECT_EQ(Variant1
, SmallestCR
);
521 else if (Variant2
.isSizeStrictlySmallerThan(Variant1
))
522 EXPECT_EQ(Variant2
, SmallestCR
);
524 EXPECT_TRUE(Variant1
== SmallestCR
|| Variant2
== SmallestCR
);
526 // Unsigned: Non-wrapped set, then smaller set, then any set.
527 bool Variant1Full
= Variant1
.isFullSet() || Variant1
.isWrappedSet();
528 bool Variant2Full
= Variant2
.isFullSet() || Variant2
.isWrappedSet();
529 if (!Variant1Full
&& Variant2Full
)
530 EXPECT_EQ(Variant1
, UnsignedCR
);
531 else if (Variant1Full
&& !Variant2Full
)
532 EXPECT_EQ(Variant2
, UnsignedCR
);
533 else if (Variant1
.isSizeStrictlySmallerThan(Variant2
))
534 EXPECT_EQ(Variant1
, UnsignedCR
);
535 else if (Variant2
.isSizeStrictlySmallerThan(Variant1
))
536 EXPECT_EQ(Variant2
, UnsignedCR
);
538 EXPECT_TRUE(Variant1
== UnsignedCR
|| Variant2
== UnsignedCR
);
540 // Signed: Signed non-wrapped set, then smaller set, then any set.
541 Variant1Full
= Variant1
.isFullSet() || Variant1
.isSignWrappedSet();
542 Variant2Full
= Variant2
.isFullSet() || Variant2
.isSignWrappedSet();
543 if (!Variant1Full
&& Variant2Full
)
544 EXPECT_EQ(Variant1
, SignedCR
);
545 else if (Variant1Full
&& !Variant2Full
)
546 EXPECT_EQ(Variant2
, SignedCR
);
547 else if (Variant1
.isSizeStrictlySmallerThan(Variant2
))
548 EXPECT_EQ(Variant1
, SignedCR
);
549 else if (Variant2
.isSizeStrictlySmallerThan(Variant1
))
550 EXPECT_EQ(Variant2
, SignedCR
);
552 EXPECT_TRUE(Variant1
== SignedCR
|| Variant2
== SignedCR
);
556 TEST_F(ConstantRangeTest
, IntersectWithExhaustive
) {
557 testBinarySetOperationExhaustive(
558 [](const ConstantRange
&CR1
, const ConstantRange
&CR2
,
559 ConstantRange::PreferredRangeType Type
) {
560 return CR1
.intersectWith(CR2
, Type
);
562 [](const ConstantRange
&CR1
, const ConstantRange
&CR2
, const APInt
&N
) {
563 return CR1
.contains(N
) && CR2
.contains(N
);
567 TEST_F(ConstantRangeTest
, UnionWithExhaustive
) {
568 testBinarySetOperationExhaustive(
569 [](const ConstantRange
&CR1
, const ConstantRange
&CR2
,
570 ConstantRange::PreferredRangeType Type
) {
571 return CR1
.unionWith(CR2
, Type
);
573 [](const ConstantRange
&CR1
, const ConstantRange
&CR2
, const APInt
&N
) {
574 return CR1
.contains(N
) || CR2
.contains(N
);
578 TEST_F(ConstantRangeTest
, UnionWith
) {
579 EXPECT_EQ(Wrap
.unionWith(One
),
580 ConstantRange(APInt(16, 0xaaa), APInt(16, 0xb)));
581 EXPECT_EQ(One
.unionWith(Wrap
), Wrap
.unionWith(One
));
582 EXPECT_EQ(Empty
.unionWith(Empty
), Empty
);
583 EXPECT_EQ(Full
.unionWith(Full
), Full
);
584 EXPECT_EQ(Some
.unionWith(Wrap
), Full
);
587 EXPECT_EQ(ConstantRange(APInt(16, 14), APInt(16, 1)).unionWith(
588 ConstantRange(APInt(16, 0), APInt(16, 8))),
589 ConstantRange(APInt(16, 14), APInt(16, 8)));
590 EXPECT_EQ(ConstantRange(APInt(16, 6), APInt(16, 4)).unionWith(
591 ConstantRange(APInt(16, 4), APInt(16, 0))),
592 ConstantRange::getFull(16));
593 EXPECT_EQ(ConstantRange(APInt(16, 1), APInt(16, 0)).unionWith(
594 ConstantRange(APInt(16, 2), APInt(16, 1))),
595 ConstantRange::getFull(16));
598 TEST_F(ConstantRangeTest
, SetDifference
) {
599 EXPECT_EQ(Full
.difference(Empty
), Full
);
600 EXPECT_EQ(Full
.difference(Full
), Empty
);
601 EXPECT_EQ(Empty
.difference(Empty
), Empty
);
602 EXPECT_EQ(Empty
.difference(Full
), Empty
);
604 ConstantRange
A(APInt(16, 3), APInt(16, 7));
605 ConstantRange
B(APInt(16, 5), APInt(16, 9));
606 ConstantRange
C(APInt(16, 3), APInt(16, 5));
607 ConstantRange
D(APInt(16, 7), APInt(16, 9));
608 ConstantRange
E(APInt(16, 5), APInt(16, 4));
609 ConstantRange
F(APInt(16, 7), APInt(16, 3));
610 EXPECT_EQ(A
.difference(B
), C
);
611 EXPECT_EQ(B
.difference(A
), D
);
612 EXPECT_EQ(E
.difference(A
), F
);
615 TEST_F(ConstantRangeTest
, SubtractAPInt
) {
616 EXPECT_EQ(Full
.subtract(APInt(16, 4)), Full
);
617 EXPECT_EQ(Empty
.subtract(APInt(16, 4)), Empty
);
618 EXPECT_EQ(Some
.subtract(APInt(16, 4)),
619 ConstantRange(APInt(16, 0x6), APInt(16, 0xaa6)));
620 EXPECT_EQ(Wrap
.subtract(APInt(16, 4)),
621 ConstantRange(APInt(16, 0xaa6), APInt(16, 0x6)));
622 EXPECT_EQ(One
.subtract(APInt(16, 4)),
623 ConstantRange(APInt(16, 0x6)));
626 TEST_F(ConstantRangeTest
, Add
) {
627 EXPECT_EQ(Full
.add(APInt(16, 4)), Full
);
628 EXPECT_EQ(Full
.add(Full
), Full
);
629 EXPECT_EQ(Full
.add(Empty
), Empty
);
630 EXPECT_EQ(Full
.add(One
), Full
);
631 EXPECT_EQ(Full
.add(Some
), Full
);
632 EXPECT_EQ(Full
.add(Wrap
), Full
);
633 EXPECT_EQ(Empty
.add(Empty
), Empty
);
634 EXPECT_EQ(Empty
.add(One
), Empty
);
635 EXPECT_EQ(Empty
.add(Some
), Empty
);
636 EXPECT_EQ(Empty
.add(Wrap
), Empty
);
637 EXPECT_EQ(Empty
.add(APInt(16, 4)), Empty
);
638 EXPECT_EQ(Some
.add(APInt(16, 4)),
639 ConstantRange(APInt(16, 0xe), APInt(16, 0xaae)));
640 EXPECT_EQ(Wrap
.add(APInt(16, 4)),
641 ConstantRange(APInt(16, 0xaae), APInt(16, 0xe)));
642 EXPECT_EQ(One
.add(APInt(16, 4)),
643 ConstantRange(APInt(16, 0xe)));
646 template <typename Fn1
, typename Fn2
>
647 static void TestAddWithNoSignedWrapExhaustive(Fn1 RangeFn
, Fn2 IntFn
) {
649 EnumerateTwoConstantRanges(Bits
, [&](const ConstantRange
&CR1
,
650 const ConstantRange
&CR2
) {
651 ConstantRange CR
= RangeFn(CR1
, CR2
);
652 APInt Min
= APInt::getSignedMaxValue(Bits
);
653 APInt Max
= APInt::getSignedMinValue(Bits
);
654 ForeachNumInConstantRange(CR1
, [&](const APInt
&N1
) {
655 ForeachNumInConstantRange(CR2
, [&](const APInt
&N2
) {
656 bool IsOverflow
= false;
657 APInt N
= IntFn(IsOverflow
, N1
, N2
);
663 EXPECT_TRUE(CR
.contains(N
));
667 if (!CR1
.isSignWrappedSet() && !CR2
.isSignWrappedSet()) {
669 EXPECT_TRUE(CR
.isEmptySet());
673 ConstantRange Exact
= ConstantRange::getNonEmpty(Min
, Max
+ 1);
674 EXPECT_EQ(Exact
, CR
);
679 template <typename Fn1
, typename Fn2
>
680 static void TestAddWithNoUnsignedWrapExhaustive(Fn1 RangeFn
, Fn2 IntFn
) {
682 EnumerateTwoConstantRanges(Bits
, [&](const ConstantRange
&CR1
,
683 const ConstantRange
&CR2
) {
684 ConstantRange CR
= RangeFn(CR1
, CR2
);
685 APInt Min
= APInt::getMaxValue(Bits
);
686 APInt Max
= APInt::getMinValue(Bits
);
687 ForeachNumInConstantRange(CR1
, [&](const APInt
&N1
) {
688 ForeachNumInConstantRange(CR2
, [&](const APInt
&N2
) {
689 bool IsOverflow
= false;
690 APInt N
= IntFn(IsOverflow
, N1
, N2
);
696 EXPECT_TRUE(CR
.contains(N
));
701 if (!CR1
.isWrappedSet() && !CR2
.isWrappedSet()) {
703 EXPECT_TRUE(CR
.isEmptySet());
707 ConstantRange Exact
= ConstantRange::getNonEmpty(Min
, Max
+ 1);
708 EXPECT_EQ(Exact
, CR
);
713 template <typename Fn1
, typename Fn2
, typename Fn3
>
714 static void TestAddWithNoSignedUnsignedWrapExhaustive(Fn1 RangeFn
,
718 EnumerateTwoConstantRanges(
719 Bits
, [&](const ConstantRange
&CR1
, const ConstantRange
&CR2
) {
720 ConstantRange CR
= RangeFn(CR1
, CR2
);
721 APInt UMin
= APInt::getMaxValue(Bits
);
722 APInt UMax
= APInt::getMinValue(Bits
);
723 APInt SMin
= APInt::getSignedMaxValue(Bits
);
724 APInt SMax
= APInt::getSignedMinValue(Bits
);
725 ForeachNumInConstantRange(CR1
, [&](const APInt
&N1
) {
726 ForeachNumInConstantRange(CR2
, [&](const APInt
&N2
) {
727 bool IsOverflow
= false, IsSignedOverflow
= false;
728 APInt N
= IntFnSigned(IsSignedOverflow
, N1
, N2
);
729 (void) IntFnUnsigned(IsOverflow
, N1
, N2
);
730 if (!IsSignedOverflow
&& !IsOverflow
) {
739 EXPECT_TRUE(CR
.contains(N
));
744 if (!CR1
.isWrappedSet() && !CR2
.isWrappedSet() &&
745 !CR1
.isSignWrappedSet() && !CR2
.isSignWrappedSet()) {
746 if (UMin
.ugt(UMax
) || SMin
.sgt(SMax
)) {
747 EXPECT_TRUE(CR
.isEmptySet());
751 ConstantRange Exact
=
752 ConstantRange::getNonEmpty(SMin
, SMax
+ 1)
753 .intersectWith(ConstantRange::getNonEmpty(UMin
, UMax
+ 1));
754 EXPECT_EQ(Exact
, CR
);
759 TEST_F(ConstantRangeTest
, AddWithNoWrap
) {
760 typedef OverflowingBinaryOperator OBO
;
761 EXPECT_EQ(Empty
.addWithNoWrap(Some
, OBO::NoSignedWrap
), Empty
);
762 EXPECT_EQ(Some
.addWithNoWrap(Empty
, OBO::NoSignedWrap
), Empty
);
763 EXPECT_EQ(Full
.addWithNoWrap(Full
, OBO::NoSignedWrap
), Full
);
764 EXPECT_NE(Full
.addWithNoWrap(Some
, OBO::NoSignedWrap
), Full
);
765 EXPECT_NE(Some
.addWithNoWrap(Full
, OBO::NoSignedWrap
), Full
);
766 EXPECT_EQ(Full
.addWithNoWrap(ConstantRange(APInt(16, 1), APInt(16, 2)),
768 ConstantRange(APInt(16, INT16_MIN
+ 1), APInt(16, INT16_MIN
)));
769 EXPECT_EQ(ConstantRange(APInt(16, 1), APInt(16, 2))
770 .addWithNoWrap(Full
, OBO::NoSignedWrap
),
771 ConstantRange(APInt(16, INT16_MIN
+ 1), APInt(16, INT16_MIN
)));
772 EXPECT_EQ(Full
.addWithNoWrap(ConstantRange(APInt(16, -1), APInt(16, 0)),
774 ConstantRange(APInt(16, INT16_MIN
), APInt(16, INT16_MAX
)));
775 EXPECT_EQ(ConstantRange(APInt(8, 100), APInt(8, 120))
776 .addWithNoWrap(ConstantRange(APInt(8, 120), APInt(8, 123)),
778 ConstantRange(8, false));
779 EXPECT_EQ(ConstantRange(APInt(8, -120), APInt(8, -100))
780 .addWithNoWrap(ConstantRange(APInt(8, -110), APInt(8, -100)),
782 ConstantRange(8, false));
783 EXPECT_EQ(ConstantRange(APInt(8, 0), APInt(8, 101))
784 .addWithNoWrap(ConstantRange(APInt(8, -128), APInt(8, 28)),
786 ConstantRange(8, true));
787 EXPECT_EQ(ConstantRange(APInt(8, 0), APInt(8, 101))
788 .addWithNoWrap(ConstantRange(APInt(8, -120), APInt(8, 29)),
790 ConstantRange(APInt(8, -120), APInt(8, -128)));
791 EXPECT_EQ(ConstantRange(APInt(8, -50), APInt(8, 50))
792 .addWithNoWrap(ConstantRange(APInt(8, 10), APInt(8, 20)),
794 ConstantRange(APInt(8, -40), APInt(8, 69)));
795 EXPECT_EQ(ConstantRange(APInt(8, 10), APInt(8, 20))
796 .addWithNoWrap(ConstantRange(APInt(8, -50), APInt(8, 50)),
798 ConstantRange(APInt(8, -40), APInt(8, 69)));
799 EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, -10))
800 .addWithNoWrap(ConstantRange(APInt(8, 5), APInt(8, 20)),
802 ConstantRange(APInt(8, 125), APInt(8, 9)));
803 EXPECT_EQ(ConstantRange(APInt(8, 5), APInt(8, 20))
804 .addWithNoWrap(ConstantRange(APInt(8, 120), APInt(8, -10)),
806 ConstantRange(APInt(8, 125), APInt(8, 9)));
808 TestAddWithNoSignedWrapExhaustive(
809 [](const ConstantRange
&CR1
, const ConstantRange
&CR2
) {
810 return CR1
.addWithNoWrap(CR2
, OBO::NoSignedWrap
);
812 [](bool &IsOverflow
, const APInt
&N1
, const APInt
&N2
) {
813 return N1
.sadd_ov(N2
, IsOverflow
);
816 EXPECT_EQ(Empty
.addWithNoWrap(Some
, OBO::NoUnsignedWrap
), Empty
);
817 EXPECT_EQ(Some
.addWithNoWrap(Empty
, OBO::NoUnsignedWrap
), Empty
);
818 EXPECT_EQ(Full
.addWithNoWrap(Full
, OBO::NoUnsignedWrap
), Full
);
819 EXPECT_NE(Full
.addWithNoWrap(Some
, OBO::NoUnsignedWrap
), Full
);
820 EXPECT_NE(Some
.addWithNoWrap(Full
, OBO::NoUnsignedWrap
), Full
);
821 EXPECT_EQ(Full
.addWithNoWrap(ConstantRange(APInt(16, 1), APInt(16, 2)),
822 OBO::NoUnsignedWrap
),
823 ConstantRange(APInt(16, 1), APInt(16, 0)));
824 EXPECT_EQ(ConstantRange(APInt(16, 1), APInt(16, 2))
825 .addWithNoWrap(Full
, OBO::NoUnsignedWrap
),
826 ConstantRange(APInt(16, 1), APInt(16, 0)));
827 EXPECT_EQ(ConstantRange(APInt(8, 200), APInt(8, 220))
828 .addWithNoWrap(ConstantRange(APInt(8, 100), APInt(8, 123)),
829 OBO::NoUnsignedWrap
),
830 ConstantRange(8, false));
831 EXPECT_EQ(ConstantRange(APInt(8, 0), APInt(8, 101))
832 .addWithNoWrap(ConstantRange(APInt(8, 0), APInt(8, 156)),
833 OBO::NoUnsignedWrap
),
834 ConstantRange(8, true));
835 EXPECT_EQ(ConstantRange(APInt(8, 0), APInt(8, 101))
836 .addWithNoWrap(ConstantRange(APInt(8, 10), APInt(8, 29)),
837 OBO::NoUnsignedWrap
),
838 ConstantRange(APInt(8, 10), APInt(8, 129)));
839 EXPECT_EQ(ConstantRange(APInt(8, 20), APInt(8, 10))
840 .addWithNoWrap(ConstantRange(APInt(8, 50), APInt(8, 200)),
841 OBO::NoUnsignedWrap
),
842 ConstantRange(APInt(8, 50), APInt(8, 0)));
843 EXPECT_EQ(ConstantRange(APInt(8, 10), APInt(8, 20))
844 .addWithNoWrap(ConstantRange(APInt(8, 50), APInt(8, 200)),
845 OBO::NoUnsignedWrap
),
846 ConstantRange(APInt(8, 60), APInt(8, -37)));
847 EXPECT_EQ(ConstantRange(APInt(8, 20), APInt(8, -30))
848 .addWithNoWrap(ConstantRange(APInt(8, 5), APInt(8, 20)),
849 OBO::NoUnsignedWrap
),
850 ConstantRange(APInt(8, 25), APInt(8, -11)));
851 EXPECT_EQ(ConstantRange(APInt(8, 5), APInt(8, 20))
852 .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, -30)),
853 OBO::NoUnsignedWrap
),
854 ConstantRange(APInt(8, 25), APInt(8, -11)));
856 TestAddWithNoUnsignedWrapExhaustive(
857 [](const ConstantRange
&CR1
, const ConstantRange
&CR2
) {
858 return CR1
.addWithNoWrap(CR2
, OBO::NoUnsignedWrap
);
860 [](bool &IsOverflow
, const APInt
&N1
, const APInt
&N2
) {
861 return N1
.uadd_ov(N2
, IsOverflow
);
864 EXPECT_EQ(ConstantRange(APInt(8, 50), APInt(8, 100))
865 .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 70)),
867 ConstantRange(APInt(8, 70), APInt(8, -128)));
868 EXPECT_EQ(ConstantRange(APInt(8, 50), APInt(8, 100))
869 .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 70)),
870 OBO::NoUnsignedWrap
),
871 ConstantRange(APInt(8, 70), APInt(8, 169)));
872 EXPECT_EQ(ConstantRange(APInt(8, 50), APInt(8, 100))
873 .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 70)),
874 OBO::NoUnsignedWrap
| OBO::NoSignedWrap
),
875 ConstantRange(APInt(8, 70), APInt(8, -128)));
877 EXPECT_EQ(ConstantRange(APInt(8, -100), APInt(8, -50))
878 .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 30)),
880 ConstantRange(APInt(8, -80), APInt(8, -21)));
881 EXPECT_EQ(ConstantRange(APInt(8, -100), APInt(8, -50))
882 .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 30)),
883 OBO::NoUnsignedWrap
),
884 ConstantRange(APInt(8, 176), APInt(8, 235)));
885 EXPECT_EQ(ConstantRange(APInt(8, -100), APInt(8, -50))
886 .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 30)),
887 OBO::NoUnsignedWrap
| OBO::NoSignedWrap
),
888 ConstantRange(APInt(8, 176), APInt(8, 235)));
890 TestAddWithNoSignedUnsignedWrapExhaustive(
891 [](const ConstantRange
&CR1
, const ConstantRange
&CR2
) {
892 return CR1
.addWithNoWrap(CR2
, OBO::NoUnsignedWrap
| OBO::NoSignedWrap
);
894 [](bool &IsOverflow
, const APInt
&N1
, const APInt
&N2
) {
895 return N1
.sadd_ov(N2
, IsOverflow
);
897 [](bool &IsOverflow
, const APInt
&N1
, const APInt
&N2
) {
898 return N1
.uadd_ov(N2
, IsOverflow
);
902 TEST_F(ConstantRangeTest
, Sub
) {
903 EXPECT_EQ(Full
.sub(APInt(16, 4)), Full
);
904 EXPECT_EQ(Full
.sub(Full
), Full
);
905 EXPECT_EQ(Full
.sub(Empty
), Empty
);
906 EXPECT_EQ(Full
.sub(One
), Full
);
907 EXPECT_EQ(Full
.sub(Some
), Full
);
908 EXPECT_EQ(Full
.sub(Wrap
), Full
);
909 EXPECT_EQ(Empty
.sub(Empty
), Empty
);
910 EXPECT_EQ(Empty
.sub(One
), Empty
);
911 EXPECT_EQ(Empty
.sub(Some
), Empty
);
912 EXPECT_EQ(Empty
.sub(Wrap
), Empty
);
913 EXPECT_EQ(Empty
.sub(APInt(16, 4)), Empty
);
914 EXPECT_EQ(Some
.sub(APInt(16, 4)),
915 ConstantRange(APInt(16, 0x6), APInt(16, 0xaa6)));
916 EXPECT_EQ(Some
.sub(Some
),
917 ConstantRange(APInt(16, 0xf561), APInt(16, 0xaa0)));
918 EXPECT_EQ(Wrap
.sub(APInt(16, 4)),
919 ConstantRange(APInt(16, 0xaa6), APInt(16, 0x6)));
920 EXPECT_EQ(One
.sub(APInt(16, 4)),
921 ConstantRange(APInt(16, 0x6)));
924 TEST_F(ConstantRangeTest
, Multiply
) {
925 EXPECT_EQ(Full
.multiply(Full
), Full
);
926 EXPECT_EQ(Full
.multiply(Empty
), Empty
);
927 EXPECT_EQ(Full
.multiply(One
), Full
);
928 EXPECT_EQ(Full
.multiply(Some
), Full
);
929 EXPECT_EQ(Full
.multiply(Wrap
), Full
);
930 EXPECT_EQ(Empty
.multiply(Empty
), Empty
);
931 EXPECT_EQ(Empty
.multiply(One
), Empty
);
932 EXPECT_EQ(Empty
.multiply(Some
), Empty
);
933 EXPECT_EQ(Empty
.multiply(Wrap
), Empty
);
934 EXPECT_EQ(One
.multiply(One
), ConstantRange(APInt(16, 0xa*0xa),
935 APInt(16, 0xa*0xa + 1)));
936 EXPECT_EQ(One
.multiply(Some
), ConstantRange(APInt(16, 0xa*0xa),
937 APInt(16, 0xa*0xaa9 + 1)));
938 EXPECT_EQ(One
.multiply(Wrap
), Full
);
939 EXPECT_EQ(Some
.multiply(Some
), Full
);
940 EXPECT_EQ(Some
.multiply(Wrap
), Full
);
941 EXPECT_EQ(Wrap
.multiply(Wrap
), Full
);
943 ConstantRange
Zero(APInt(16, 0));
944 EXPECT_EQ(Zero
.multiply(Full
), Zero
);
945 EXPECT_EQ(Zero
.multiply(Some
), Zero
);
946 EXPECT_EQ(Zero
.multiply(Wrap
), Zero
);
947 EXPECT_EQ(Full
.multiply(Zero
), Zero
);
948 EXPECT_EQ(Some
.multiply(Zero
), Zero
);
949 EXPECT_EQ(Wrap
.multiply(Zero
), Zero
);
951 // http://llvm.org/PR4545
952 EXPECT_EQ(ConstantRange(APInt(4, 1), APInt(4, 6)).multiply(
953 ConstantRange(APInt(4, 6), APInt(4, 2))),
954 ConstantRange(4, /*isFullSet=*/true));
956 EXPECT_EQ(ConstantRange(APInt(8, 254), APInt(8, 0)).multiply(
957 ConstantRange(APInt(8, 252), APInt(8, 4))),
958 ConstantRange(APInt(8, 250), APInt(8, 9)));
959 EXPECT_EQ(ConstantRange(APInt(8, 254), APInt(8, 255)).multiply(
960 ConstantRange(APInt(8, 2), APInt(8, 4))),
961 ConstantRange(APInt(8, 250), APInt(8, 253)));
963 // TODO: This should be return [-2, 0]
964 EXPECT_EQ(ConstantRange(APInt(8, -2)).multiply(
965 ConstantRange(APInt(8, 0), APInt(8, 2))),
966 ConstantRange(APInt(8, -2), APInt(8, 1)));
969 TEST_F(ConstantRangeTest
, UMax
) {
970 EXPECT_EQ(Full
.umax(Full
), Full
);
971 EXPECT_EQ(Full
.umax(Empty
), Empty
);
972 EXPECT_EQ(Full
.umax(Some
), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
973 EXPECT_EQ(Full
.umax(Wrap
), Full
);
974 EXPECT_EQ(Full
.umax(Some
), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
975 EXPECT_EQ(Empty
.umax(Empty
), Empty
);
976 EXPECT_EQ(Empty
.umax(Some
), Empty
);
977 EXPECT_EQ(Empty
.umax(Wrap
), Empty
);
978 EXPECT_EQ(Empty
.umax(One
), Empty
);
979 EXPECT_EQ(Some
.umax(Some
), Some
);
980 EXPECT_EQ(Some
.umax(Wrap
), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
981 EXPECT_EQ(Some
.umax(One
), Some
);
982 // TODO: ConstantRange is currently over-conservative here.
983 EXPECT_EQ(Wrap
.umax(Wrap
), Full
);
984 EXPECT_EQ(Wrap
.umax(One
), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
985 EXPECT_EQ(One
.umax(One
), One
);
988 TEST_F(ConstantRangeTest
, SMax
) {
989 EXPECT_EQ(Full
.smax(Full
), Full
);
990 EXPECT_EQ(Full
.smax(Empty
), Empty
);
991 EXPECT_EQ(Full
.smax(Some
), ConstantRange(APInt(16, 0xa),
992 APInt::getSignedMinValue(16)));
993 EXPECT_EQ(Full
.smax(Wrap
), Full
);
994 EXPECT_EQ(Full
.smax(One
), ConstantRange(APInt(16, 0xa),
995 APInt::getSignedMinValue(16)));
996 EXPECT_EQ(Empty
.smax(Empty
), Empty
);
997 EXPECT_EQ(Empty
.smax(Some
), Empty
);
998 EXPECT_EQ(Empty
.smax(Wrap
), Empty
);
999 EXPECT_EQ(Empty
.smax(One
), Empty
);
1000 EXPECT_EQ(Some
.smax(Some
), Some
);
1001 EXPECT_EQ(Some
.smax(Wrap
), ConstantRange(APInt(16, 0xa),
1002 APInt(16, (uint64_t)INT16_MIN
)));
1003 EXPECT_EQ(Some
.smax(One
), Some
);
1004 EXPECT_EQ(Wrap
.smax(One
), ConstantRange(APInt(16, 0xa),
1005 APInt(16, (uint64_t)INT16_MIN
)));
1006 EXPECT_EQ(One
.smax(One
), One
);
1009 TEST_F(ConstantRangeTest
, UMin
) {
1010 EXPECT_EQ(Full
.umin(Full
), Full
);
1011 EXPECT_EQ(Full
.umin(Empty
), Empty
);
1012 EXPECT_EQ(Full
.umin(Some
), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
1013 EXPECT_EQ(Full
.umin(Wrap
), Full
);
1014 EXPECT_EQ(Empty
.umin(Empty
), Empty
);
1015 EXPECT_EQ(Empty
.umin(Some
), Empty
);
1016 EXPECT_EQ(Empty
.umin(Wrap
), Empty
);
1017 EXPECT_EQ(Empty
.umin(One
), Empty
);
1018 EXPECT_EQ(Some
.umin(Some
), Some
);
1019 EXPECT_EQ(Some
.umin(Wrap
), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
1020 EXPECT_EQ(Some
.umin(One
), One
);
1021 // TODO: ConstantRange is currently over-conservative here.
1022 EXPECT_EQ(Wrap
.umin(Wrap
), Full
);
1023 EXPECT_EQ(Wrap
.umin(One
), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
1024 EXPECT_EQ(One
.umin(One
), One
);
1027 TEST_F(ConstantRangeTest
, SMin
) {
1028 EXPECT_EQ(Full
.smin(Full
), Full
);
1029 EXPECT_EQ(Full
.smin(Empty
), Empty
);
1030 EXPECT_EQ(Full
.smin(Some
), ConstantRange(APInt(16, (uint64_t)INT16_MIN
),
1032 EXPECT_EQ(Full
.smin(Wrap
), Full
);
1033 EXPECT_EQ(Empty
.smin(Empty
), Empty
);
1034 EXPECT_EQ(Empty
.smin(Some
), Empty
);
1035 EXPECT_EQ(Empty
.smin(Wrap
), Empty
);
1036 EXPECT_EQ(Empty
.smin(One
), Empty
);
1037 EXPECT_EQ(Some
.smin(Some
), Some
);
1038 EXPECT_EQ(Some
.smin(Wrap
), ConstantRange(APInt(16, (uint64_t)INT16_MIN
),
1040 EXPECT_EQ(Some
.smin(One
), One
);
1041 // TODO: ConstantRange is currently over-conservative here.
1042 EXPECT_EQ(Wrap
.smin(Wrap
), Full
);
1043 EXPECT_EQ(Wrap
.smin(One
), ConstantRange(APInt(16, (uint64_t)INT16_MIN
),
1045 EXPECT_EQ(One
.smin(One
), One
);
1048 TEST_F(ConstantRangeTest
, UDiv
) {
1049 EXPECT_EQ(Full
.udiv(Full
), Full
);
1050 EXPECT_EQ(Full
.udiv(Empty
), Empty
);
1051 EXPECT_EQ(Full
.udiv(One
), ConstantRange(APInt(16, 0),
1052 APInt(16, 0xffff / 0xa + 1)));
1053 EXPECT_EQ(Full
.udiv(Some
), ConstantRange(APInt(16, 0),
1054 APInt(16, 0xffff / 0xa + 1)));
1055 EXPECT_EQ(Full
.udiv(Wrap
), Full
);
1056 EXPECT_EQ(Empty
.udiv(Empty
), Empty
);
1057 EXPECT_EQ(Empty
.udiv(One
), Empty
);
1058 EXPECT_EQ(Empty
.udiv(Some
), Empty
);
1059 EXPECT_EQ(Empty
.udiv(Wrap
), Empty
);
1060 EXPECT_EQ(One
.udiv(One
), ConstantRange(APInt(16, 1)));
1061 EXPECT_EQ(One
.udiv(Some
), ConstantRange(APInt(16, 0), APInt(16, 2)));
1062 EXPECT_EQ(One
.udiv(Wrap
), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
1063 EXPECT_EQ(Some
.udiv(Some
), ConstantRange(APInt(16, 0), APInt(16, 0x111)));
1064 EXPECT_EQ(Some
.udiv(Wrap
), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
1065 EXPECT_EQ(Wrap
.udiv(Wrap
), Full
);
1068 ConstantRange
Zero(APInt(16, 0));
1069 EXPECT_EQ(Zero
.udiv(One
), Zero
);
1070 EXPECT_EQ(Zero
.udiv(Full
), Zero
);
1072 EXPECT_EQ(ConstantRange(APInt(16, 0), APInt(16, 99)).udiv(Full
),
1073 ConstantRange(APInt(16, 0), APInt(16, 99)));
1074 EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 99)).udiv(Full
),
1075 ConstantRange(APInt(16, 0), APInt(16, 99)));
1078 TEST_F(ConstantRangeTest
, SDiv
) {
1080 EnumerateTwoConstantRanges(Bits
, [&](const ConstantRange
&CR1
,
1081 const ConstantRange
&CR2
) {
1082 // Collect possible results in a bit vector. We store the signed value plus
1083 // a bias to make it unsigned.
1084 int Bias
= 1 << (Bits
- 1);
1085 BitVector
Results(1 << Bits
);
1086 ForeachNumInConstantRange(CR1
, [&](const APInt
&N1
) {
1087 ForeachNumInConstantRange(CR2
, [&](const APInt
&N2
) {
1088 // Division by zero is UB.
1092 // SignedMin / -1 is UB.
1093 if (N1
.isMinSignedValue() && N2
.isAllOnesValue())
1096 APInt N
= N1
.sdiv(N2
);
1097 Results
.set(N
.getSExtValue() + Bias
);
1101 ConstantRange CR
= CR1
.sdiv(CR2
);
1102 if (Results
.none()) {
1103 EXPECT_TRUE(CR
.isEmptySet());
1107 // If there is a non-full signed envelope, that should be the result.
1108 APInt
SMin(Bits
, Results
.find_first() - Bias
);
1109 APInt
SMax(Bits
, Results
.find_last() - Bias
);
1110 ConstantRange Envelope
= ConstantRange::getNonEmpty(SMin
, SMax
+ 1);
1111 if (!Envelope
.isFullSet()) {
1112 EXPECT_EQ(Envelope
, CR
);
1116 // If the signed envelope is a full set, try to find a smaller sign wrapped
1117 // set that is separated in negative and positive components (or one which
1118 // can also additionally contain zero).
1119 int LastNeg
= Results
.find_last_in(0, Bias
) - Bias
;
1120 int LastPos
= Results
.find_next(Bias
) - Bias
;
1121 if (Results
[Bias
]) {
1124 else if (LastPos
== 1)
1128 APInt
WMax(Bits
, LastNeg
);
1129 APInt
WMin(Bits
, LastPos
);
1130 ConstantRange Wrapped
= ConstantRange::getNonEmpty(WMin
, WMax
+ 1);
1131 EXPECT_EQ(Wrapped
, CR
);
1135 TEST_F(ConstantRangeTest
, URem
) {
1136 EXPECT_EQ(Full
.urem(Empty
), Empty
);
1137 EXPECT_EQ(Empty
.urem(Full
), Empty
);
1138 // urem by zero is poison.
1139 EXPECT_EQ(Full
.urem(ConstantRange(APInt(16, 0))), Empty
);
1140 // urem by full range doesn't contain MaxValue.
1141 EXPECT_EQ(Full
.urem(Full
), ConstantRange(APInt(16, 0), APInt(16, 0xffff)));
1142 // urem is upper bounded by maximum RHS minus one.
1143 EXPECT_EQ(Full
.urem(ConstantRange(APInt(16, 0), APInt(16, 123))),
1144 ConstantRange(APInt(16, 0), APInt(16, 122)));
1145 // urem is upper bounded by maximum LHS.
1146 EXPECT_EQ(ConstantRange(APInt(16, 0), APInt(16, 123)).urem(Full
),
1147 ConstantRange(APInt(16, 0), APInt(16, 123)));
1148 // If the LHS is always lower than the RHS, the result is the LHS.
1149 EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 20))
1150 .urem(ConstantRange(APInt(16, 20), APInt(16, 30))),
1151 ConstantRange(APInt(16, 10), APInt(16, 20)));
1152 // It has to be strictly lower, otherwise the top value may wrap to zero.
1153 EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 20))
1154 .urem(ConstantRange(APInt(16, 19), APInt(16, 30))),
1155 ConstantRange(APInt(16, 0), APInt(16, 20)));
1156 // [12, 14] % 10 is [2, 4], but we conservatively compute [0, 9].
1157 EXPECT_EQ(ConstantRange(APInt(16, 12), APInt(16, 15))
1158 .urem(ConstantRange(APInt(16, 10))),
1159 ConstantRange(APInt(16, 0), APInt(16, 10)));
1161 TestUnsignedBinOpExhaustive(
1162 [](const ConstantRange
&CR1
, const ConstantRange
&CR2
) {
1163 return CR1
.urem(CR2
);
1165 [](const APInt
&N1
, const APInt
&N2
) {
1168 /* SkipZeroRHS */ true, /* CorrectnessOnly */ true);
1171 TEST_F(ConstantRangeTest
, SRem
) {
1172 EXPECT_EQ(Full
.srem(Empty
), Empty
);
1173 EXPECT_EQ(Empty
.srem(Full
), Empty
);
1174 // srem by zero is UB.
1175 EXPECT_EQ(Full
.srem(ConstantRange(APInt(16, 0))), Empty
);
1176 // srem by full range doesn't contain SignedMinValue.
1177 EXPECT_EQ(Full
.srem(Full
), ConstantRange(APInt::getSignedMinValue(16) + 1,
1178 APInt::getSignedMinValue(16)));
1180 ConstantRange
PosMod(APInt(16, 10), APInt(16, 21)); // [10, 20]
1181 ConstantRange
NegMod(APInt(16, -20), APInt(16, -9)); // [-20, -10]
1182 ConstantRange
IntMinMod(APInt::getSignedMinValue(16));
1184 ConstantRange
Expected(16, true);
1186 // srem is bounded by abs(RHS) minus one.
1187 ConstantRange
PosLargeLHS(APInt(16, 0), APInt(16, 41));
1188 Expected
= ConstantRange(APInt(16, 0), APInt(16, 20));
1189 EXPECT_EQ(PosLargeLHS
.srem(PosMod
), Expected
);
1190 EXPECT_EQ(PosLargeLHS
.srem(NegMod
), Expected
);
1191 ConstantRange
NegLargeLHS(APInt(16, -40), APInt(16, 1));
1192 Expected
= ConstantRange(APInt(16, -19), APInt(16, 1));
1193 EXPECT_EQ(NegLargeLHS
.srem(PosMod
), Expected
);
1194 EXPECT_EQ(NegLargeLHS
.srem(NegMod
), Expected
);
1195 ConstantRange
PosNegLargeLHS(APInt(16, -32), APInt(16, 38));
1196 Expected
= ConstantRange(APInt(16, -19), APInt(16, 20));
1197 EXPECT_EQ(PosNegLargeLHS
.srem(PosMod
), Expected
);
1198 EXPECT_EQ(PosNegLargeLHS
.srem(NegMod
), Expected
);
1200 // srem is bounded by LHS.
1201 ConstantRange
PosLHS(APInt(16, 0), APInt(16, 16));
1202 EXPECT_EQ(PosLHS
.srem(PosMod
), PosLHS
);
1203 EXPECT_EQ(PosLHS
.srem(NegMod
), PosLHS
);
1204 EXPECT_EQ(PosLHS
.srem(IntMinMod
), PosLHS
);
1205 ConstantRange
NegLHS(APInt(16, -15), APInt(16, 1));
1206 EXPECT_EQ(NegLHS
.srem(PosMod
), NegLHS
);
1207 EXPECT_EQ(NegLHS
.srem(NegMod
), NegLHS
);
1208 EXPECT_EQ(NegLHS
.srem(IntMinMod
), NegLHS
);
1209 ConstantRange
PosNegLHS(APInt(16, -12), APInt(16, 18));
1210 EXPECT_EQ(PosNegLHS
.srem(PosMod
), PosNegLHS
);
1211 EXPECT_EQ(PosNegLHS
.srem(NegMod
), PosNegLHS
);
1212 EXPECT_EQ(PosNegLHS
.srem(IntMinMod
), PosNegLHS
);
1214 // srem is LHS if it is smaller than RHS.
1215 ConstantRange
PosSmallLHS(APInt(16, 3), APInt(16, 8));
1216 EXPECT_EQ(PosSmallLHS
.srem(PosMod
), PosSmallLHS
);
1217 EXPECT_EQ(PosSmallLHS
.srem(NegMod
), PosSmallLHS
);
1218 EXPECT_EQ(PosSmallLHS
.srem(IntMinMod
), PosSmallLHS
);
1219 ConstantRange
NegSmallLHS(APInt(16, -7), APInt(16, -2));
1220 EXPECT_EQ(NegSmallLHS
.srem(PosMod
), NegSmallLHS
);
1221 EXPECT_EQ(NegSmallLHS
.srem(NegMod
), NegSmallLHS
);
1222 EXPECT_EQ(NegSmallLHS
.srem(IntMinMod
), NegSmallLHS
);
1223 ConstantRange
PosNegSmallLHS(APInt(16, -3), APInt(16, 8));
1224 EXPECT_EQ(PosNegSmallLHS
.srem(PosMod
), PosNegSmallLHS
);
1225 EXPECT_EQ(PosNegSmallLHS
.srem(NegMod
), PosNegSmallLHS
);
1226 EXPECT_EQ(PosNegSmallLHS
.srem(IntMinMod
), PosNegSmallLHS
);
1228 // Example of a suboptimal result:
1229 // [12, 14] srem 10 is [2, 4], but we conservatively compute [0, 9].
1230 EXPECT_EQ(ConstantRange(APInt(16, 12), APInt(16, 15))
1231 .srem(ConstantRange(APInt(16, 10))),
1232 ConstantRange(APInt(16, 0), APInt(16, 10)));
1234 TestSignedBinOpExhaustive(
1235 [](const ConstantRange
&CR1
, const ConstantRange
&CR2
) {
1236 return CR1
.srem(CR2
);
1238 [](const APInt
&N1
, const APInt
&N2
) {
1241 /* SkipZeroRHS */ true, /* CorrectnessOnly */ true);
1244 TEST_F(ConstantRangeTest
, Shl
) {
1245 ConstantRange
Some2(APInt(16, 0xfff), APInt(16, 0x8000));
1246 ConstantRange
WrapNullMax(APInt(16, 0x1), APInt(16, 0x0));
1247 EXPECT_EQ(Full
.shl(Full
), Full
);
1248 EXPECT_EQ(Full
.shl(Empty
), Empty
);
1249 EXPECT_EQ(Full
.shl(One
), Full
); // TODO: [0, (-1 << 0xa) + 1)
1250 EXPECT_EQ(Full
.shl(Some
), Full
); // TODO: [0, (-1 << 0xa) + 1)
1251 EXPECT_EQ(Full
.shl(Wrap
), Full
);
1252 EXPECT_EQ(Empty
.shl(Empty
), Empty
);
1253 EXPECT_EQ(Empty
.shl(One
), Empty
);
1254 EXPECT_EQ(Empty
.shl(Some
), Empty
);
1255 EXPECT_EQ(Empty
.shl(Wrap
), Empty
);
1256 EXPECT_EQ(One
.shl(One
), ConstantRange(APInt(16, 0xa << 0xa),
1257 APInt(16, (0xa << 0xa) + 1)));
1258 EXPECT_EQ(One
.shl(Some
), Full
); // TODO: [0xa << 0xa, 0)
1259 EXPECT_EQ(One
.shl(Wrap
), Full
); // TODO: [0xa, 0xa << 14 + 1)
1260 EXPECT_EQ(Some
.shl(Some
), Full
); // TODO: [0xa << 0xa, 0xfc01)
1261 EXPECT_EQ(Some
.shl(Wrap
), Full
); // TODO: [0xa, 0x7ff << 0x5 + 1)
1262 EXPECT_EQ(Wrap
.shl(Wrap
), Full
);
1264 Some2
.shl(ConstantRange(APInt(16, 0x1))),
1265 ConstantRange(APInt(16, 0xfff << 0x1), APInt(16, 0x7fff << 0x1) + 1));
1266 EXPECT_EQ(One
.shl(WrapNullMax
), Full
);
1269 TEST_F(ConstantRangeTest
, Lshr
) {
1270 EXPECT_EQ(Full
.lshr(Full
), Full
);
1271 EXPECT_EQ(Full
.lshr(Empty
), Empty
);
1272 EXPECT_EQ(Full
.lshr(One
), ConstantRange(APInt(16, 0),
1273 APInt(16, (0xffff >> 0xa) + 1)));
1274 EXPECT_EQ(Full
.lshr(Some
), ConstantRange(APInt(16, 0),
1275 APInt(16, (0xffff >> 0xa) + 1)));
1276 EXPECT_EQ(Full
.lshr(Wrap
), Full
);
1277 EXPECT_EQ(Empty
.lshr(Empty
), Empty
);
1278 EXPECT_EQ(Empty
.lshr(One
), Empty
);
1279 EXPECT_EQ(Empty
.lshr(Some
), Empty
);
1280 EXPECT_EQ(Empty
.lshr(Wrap
), Empty
);
1281 EXPECT_EQ(One
.lshr(One
), ConstantRange(APInt(16, 0)));
1282 EXPECT_EQ(One
.lshr(Some
), ConstantRange(APInt(16, 0)));
1283 EXPECT_EQ(One
.lshr(Wrap
), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
1284 EXPECT_EQ(Some
.lshr(Some
), ConstantRange(APInt(16, 0),
1285 APInt(16, (0xaaa >> 0xa) + 1)));
1286 EXPECT_EQ(Some
.lshr(Wrap
), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
1287 EXPECT_EQ(Wrap
.lshr(Wrap
), Full
);
1290 TEST_F(ConstantRangeTest
, Ashr
) {
1291 EXPECT_EQ(Full
.ashr(Full
), Full
);
1292 EXPECT_EQ(Full
.ashr(Empty
), Empty
);
1293 EXPECT_EQ(Full
.ashr(One
), ConstantRange(APInt(16, 0xffe0),
1294 APInt(16, (0x7fff >> 0xa) + 1 )));
1295 ConstantRange
Small(APInt(16, 0xa), APInt(16, 0xb));
1296 EXPECT_EQ(Full
.ashr(Small
), ConstantRange(APInt(16, 0xffe0),
1297 APInt(16, (0x7fff >> 0xa) + 1 )));
1298 EXPECT_EQ(Full
.ashr(Some
), ConstantRange(APInt(16, 0xffe0),
1299 APInt(16, (0x7fff >> 0xa) + 1 )));
1300 EXPECT_EQ(Full
.ashr(Wrap
), Full
);
1301 EXPECT_EQ(Empty
.ashr(Empty
), Empty
);
1302 EXPECT_EQ(Empty
.ashr(One
), Empty
);
1303 EXPECT_EQ(Empty
.ashr(Some
), Empty
);
1304 EXPECT_EQ(Empty
.ashr(Wrap
), Empty
);
1305 EXPECT_EQ(One
.ashr(One
), ConstantRange(APInt(16, 0)));
1306 EXPECT_EQ(One
.ashr(Some
), ConstantRange(APInt(16, 0)));
1307 EXPECT_EQ(One
.ashr(Wrap
), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
1308 EXPECT_EQ(Some
.ashr(Some
), ConstantRange(APInt(16, 0),
1309 APInt(16, (0xaaa >> 0xa) + 1)));
1310 EXPECT_EQ(Some
.ashr(Wrap
), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
1311 EXPECT_EQ(Wrap
.ashr(Wrap
), Full
);
1312 ConstantRange
Neg(APInt(16, 0xf3f0, true), APInt(16, 0xf7f8, true));
1313 EXPECT_EQ(Neg
.ashr(Small
), ConstantRange(APInt(16, 0xfffc, true),
1314 APInt(16, 0xfffe, true)));
1317 TEST(ConstantRange
, MakeAllowedICmpRegion
) {
1319 ConstantRange SMax
= ConstantRange(APInt::getSignedMaxValue(32));
1320 EXPECT_TRUE(ConstantRange::makeAllowedICmpRegion(ICmpInst::ICMP_SGT
, SMax
)
1324 TEST(ConstantRange
, MakeSatisfyingICmpRegion
) {
1325 ConstantRange
LowHalf(APInt(8, 0), APInt(8, 128));
1326 ConstantRange
HighHalf(APInt(8, 128), APInt(8, 0));
1327 ConstantRange
EmptySet(8, /* isFullSet = */ false);
1329 EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_NE
, LowHalf
),
1333 ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_NE
, HighHalf
),
1336 EXPECT_TRUE(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_EQ
,
1337 HighHalf
).isEmptySet());
1339 ConstantRange
UnsignedSample(APInt(8, 5), APInt(8, 200));
1341 EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_ULT
,
1343 ConstantRange(APInt(8, 0), APInt(8, 5)));
1345 EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_ULE
,
1347 ConstantRange(APInt(8, 0), APInt(8, 6)));
1349 EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_UGT
,
1351 ConstantRange(APInt(8, 200), APInt(8, 0)));
1353 EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_UGE
,
1355 ConstantRange(APInt(8, 199), APInt(8, 0)));
1357 ConstantRange
SignedSample(APInt(8, -5), APInt(8, 5));
1360 ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SLT
, SignedSample
),
1361 ConstantRange(APInt(8, -128), APInt(8, -5)));
1364 ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SLE
, SignedSample
),
1365 ConstantRange(APInt(8, -128), APInt(8, -4)));
1368 ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SGT
, SignedSample
),
1369 ConstantRange(APInt(8, 5), APInt(8, -128)));
1372 ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SGE
, SignedSample
),
1373 ConstantRange(APInt(8, 4), APInt(8, -128)));
1376 TEST(ConstantRange
, MakeGuaranteedNoWrapRegion
) {
1377 const int IntMin4Bits
= 8;
1378 const int IntMax4Bits
= 7;
1379 typedef OverflowingBinaryOperator OBO
;
1381 for (int Const
: {0, -1, -2, 1, 2, IntMin4Bits
, IntMax4Bits
}) {
1382 APInt
C(4, Const
, true /* = isSigned */);
1384 auto NUWRegion
= ConstantRange::makeGuaranteedNoWrapRegion(
1385 Instruction::Add
, C
, OBO::NoUnsignedWrap
);
1387 EXPECT_FALSE(NUWRegion
.isEmptySet());
1389 auto NSWRegion
= ConstantRange::makeGuaranteedNoWrapRegion(
1390 Instruction::Add
, C
, OBO::NoSignedWrap
);
1392 EXPECT_FALSE(NSWRegion
.isEmptySet());
1394 for (APInt I
= NUWRegion
.getLower(), E
= NUWRegion
.getUpper(); I
!= E
;
1396 bool Overflow
= false;
1397 (void)I
.uadd_ov(C
, Overflow
);
1398 EXPECT_FALSE(Overflow
);
1401 for (APInt I
= NSWRegion
.getLower(), E
= NSWRegion
.getUpper(); I
!= E
;
1403 bool Overflow
= false;
1404 (void)I
.sadd_ov(C
, Overflow
);
1405 EXPECT_FALSE(Overflow
);
1409 for (int Const
: {0, -1, -2, 1, 2, IntMin4Bits
, IntMax4Bits
}) {
1410 APInt
C(4, Const
, true /* = isSigned */);
1412 auto NUWRegion
= ConstantRange::makeGuaranteedNoWrapRegion(
1413 Instruction::Sub
, C
, OBO::NoUnsignedWrap
);
1415 EXPECT_FALSE(NUWRegion
.isEmptySet());
1417 auto NSWRegion
= ConstantRange::makeGuaranteedNoWrapRegion(
1418 Instruction::Sub
, C
, OBO::NoSignedWrap
);
1420 EXPECT_FALSE(NSWRegion
.isEmptySet());
1422 for (APInt I
= NUWRegion
.getLower(), E
= NUWRegion
.getUpper(); I
!= E
;
1424 bool Overflow
= false;
1425 (void)I
.usub_ov(C
, Overflow
);
1426 EXPECT_FALSE(Overflow
);
1429 for (APInt I
= NSWRegion
.getLower(), E
= NSWRegion
.getUpper(); I
!= E
;
1431 bool Overflow
= false;
1432 (void)I
.ssub_ov(C
, Overflow
);
1433 EXPECT_FALSE(Overflow
);
1437 auto NSWForAllValues
= ConstantRange::makeGuaranteedNoWrapRegion(
1438 Instruction::Add
, ConstantRange(32, /* isFullSet = */ true),
1440 EXPECT_TRUE(NSWForAllValues
.isSingleElement() &&
1441 NSWForAllValues
.getSingleElement()->isMinValue());
1443 NSWForAllValues
= ConstantRange::makeGuaranteedNoWrapRegion(
1444 Instruction::Sub
, ConstantRange(32, /* isFullSet = */ true),
1446 EXPECT_TRUE(NSWForAllValues
.isSingleElement() &&
1447 NSWForAllValues
.getSingleElement()->isMaxValue());
1449 auto NUWForAllValues
= ConstantRange::makeGuaranteedNoWrapRegion(
1450 Instruction::Add
, ConstantRange(32, /* isFullSet = */ true),
1451 OBO::NoUnsignedWrap
);
1452 EXPECT_TRUE(NUWForAllValues
.isSingleElement() &&
1453 NUWForAllValues
.getSingleElement()->isMinValue());
1455 NUWForAllValues
= ConstantRange::makeGuaranteedNoWrapRegion(
1456 Instruction::Sub
, ConstantRange(32, /* isFullSet = */ true),
1457 OBO::NoUnsignedWrap
);
1458 EXPECT_TRUE(NUWForAllValues
.isSingleElement() &&
1459 NUWForAllValues
.getSingleElement()->isMaxValue());
1461 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
1462 Instruction::Add
, APInt(32, 0), OBO::NoUnsignedWrap
).isFullSet());
1463 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
1464 Instruction::Add
, APInt(32, 0), OBO::NoSignedWrap
).isFullSet());
1465 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
1466 Instruction::Sub
, APInt(32, 0), OBO::NoUnsignedWrap
).isFullSet());
1467 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
1468 Instruction::Sub
, APInt(32, 0), OBO::NoSignedWrap
).isFullSet());
1470 ConstantRange
OneToFive(APInt(32, 1), APInt(32, 6));
1471 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1472 Instruction::Add
, OneToFive
, OBO::NoSignedWrap
),
1473 ConstantRange(APInt::getSignedMinValue(32),
1474 APInt::getSignedMaxValue(32) - 4));
1475 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1476 Instruction::Add
, OneToFive
, OBO::NoUnsignedWrap
),
1477 ConstantRange(APInt::getMinValue(32), APInt::getMinValue(32) - 5));
1478 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1479 Instruction::Sub
, OneToFive
, OBO::NoSignedWrap
),
1480 ConstantRange(APInt::getSignedMinValue(32) + 5,
1481 APInt::getSignedMinValue(32)));
1482 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1483 Instruction::Sub
, OneToFive
, OBO::NoUnsignedWrap
),
1484 ConstantRange(APInt::getMinValue(32) + 5, APInt::getMinValue(32)));
1486 ConstantRange
MinusFiveToMinusTwo(APInt(32, -5), APInt(32, -1));
1487 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1488 Instruction::Add
, MinusFiveToMinusTwo
, OBO::NoSignedWrap
),
1489 ConstantRange(APInt::getSignedMinValue(32) + 5,
1490 APInt::getSignedMinValue(32)));
1491 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1492 Instruction::Add
, MinusFiveToMinusTwo
, OBO::NoUnsignedWrap
),
1493 ConstantRange(APInt(32, 0), APInt(32, 2)));
1494 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1495 Instruction::Sub
, MinusFiveToMinusTwo
, OBO::NoSignedWrap
),
1496 ConstantRange(APInt::getSignedMinValue(32),
1497 APInt::getSignedMaxValue(32) - 4));
1498 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1499 Instruction::Sub
, MinusFiveToMinusTwo
, OBO::NoUnsignedWrap
),
1500 ConstantRange(APInt::getMaxValue(32) - 1,
1501 APInt::getMinValue(32)));
1503 ConstantRange
MinusOneToOne(APInt(32, -1), APInt(32, 2));
1504 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1505 Instruction::Add
, MinusOneToOne
, OBO::NoSignedWrap
),
1506 ConstantRange(APInt::getSignedMinValue(32) + 1,
1507 APInt::getSignedMinValue(32) - 1));
1508 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1509 Instruction::Add
, MinusOneToOne
, OBO::NoUnsignedWrap
),
1510 ConstantRange(APInt(32, 0), APInt(32, 1)));
1511 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1512 Instruction::Sub
, MinusOneToOne
, OBO::NoSignedWrap
),
1513 ConstantRange(APInt::getSignedMinValue(32) + 1,
1514 APInt::getSignedMinValue(32) - 1));
1515 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1516 Instruction::Sub
, MinusOneToOne
, OBO::NoUnsignedWrap
),
1517 ConstantRange(APInt::getMaxValue(32),
1518 APInt::getMinValue(32)));
1520 ConstantRange
One(APInt(32, 1), APInt(32, 2));
1521 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1522 Instruction::Add
, One
, OBO::NoSignedWrap
),
1523 ConstantRange(APInt::getSignedMinValue(32),
1524 APInt::getSignedMaxValue(32)));
1525 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1526 Instruction::Add
, One
, OBO::NoUnsignedWrap
),
1527 ConstantRange(APInt::getMinValue(32), APInt::getMaxValue(32)));
1528 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1529 Instruction::Sub
, One
, OBO::NoSignedWrap
),
1530 ConstantRange(APInt::getSignedMinValue(32) + 1,
1531 APInt::getSignedMinValue(32)));
1532 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1533 Instruction::Sub
, One
, OBO::NoUnsignedWrap
),
1534 ConstantRange(APInt::getMinValue(32) + 1, APInt::getMinValue(32)));
1536 ConstantRange
OneLessThanBitWidth(APInt(32, 0), APInt(32, 31) + 1);
1537 ConstantRange
UpToBitWidth(APInt(32, 0), APInt(32, 32) + 1);
1538 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1539 Instruction::Shl
, UpToBitWidth
, OBO::NoUnsignedWrap
),
1540 ConstantRange::makeGuaranteedNoWrapRegion(
1541 Instruction::Shl
, OneLessThanBitWidth
, OBO::NoUnsignedWrap
));
1542 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1543 Instruction::Shl
, UpToBitWidth
, OBO::NoSignedWrap
),
1544 ConstantRange::makeGuaranteedNoWrapRegion(
1545 Instruction::Shl
, OneLessThanBitWidth
, OBO::NoSignedWrap
));
1546 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1547 Instruction::Shl
, UpToBitWidth
, OBO::NoUnsignedWrap
),
1548 ConstantRange(APInt(32, 0), APInt(32, 1) + 1));
1549 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1550 Instruction::Shl
, UpToBitWidth
, OBO::NoSignedWrap
),
1551 ConstantRange(APInt(32, -1), APInt(32, 0) + 1));
1554 ConstantRange::makeGuaranteedNoWrapRegion(
1555 Instruction::Shl
, ConstantRange::getFull(32), OBO::NoUnsignedWrap
),
1556 ConstantRange::makeGuaranteedNoWrapRegion(
1557 Instruction::Shl
, OneLessThanBitWidth
, OBO::NoUnsignedWrap
));
1559 ConstantRange::makeGuaranteedNoWrapRegion(
1560 Instruction::Shl
, ConstantRange::getFull(32), OBO::NoSignedWrap
),
1561 ConstantRange::makeGuaranteedNoWrapRegion(
1562 Instruction::Shl
, OneLessThanBitWidth
, OBO::NoSignedWrap
));
1564 ConstantRange
IllegalShAmt(APInt(32, 32), APInt(32, 0) + 1);
1565 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1566 Instruction::Shl
, IllegalShAmt
, OBO::NoUnsignedWrap
),
1567 ConstantRange::getFull(32));
1568 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1569 Instruction::Shl
, IllegalShAmt
, OBO::NoSignedWrap
),
1570 ConstantRange::getFull(32));
1573 ConstantRange::makeGuaranteedNoWrapRegion(
1574 Instruction::Shl
, ConstantRange(APInt(32, -32), APInt(32, 16) + 1),
1575 OBO::NoUnsignedWrap
),
1576 ConstantRange::makeGuaranteedNoWrapRegion(
1577 Instruction::Shl
, ConstantRange(APInt(32, 0), APInt(32, 16) + 1),
1578 OBO::NoUnsignedWrap
));
1580 ConstantRange::makeGuaranteedNoWrapRegion(
1581 Instruction::Shl
, ConstantRange(APInt(32, -32), APInt(32, 16) + 1),
1583 ConstantRange::makeGuaranteedNoWrapRegion(
1584 Instruction::Shl
, ConstantRange(APInt(32, 0), APInt(32, 16) + 1),
1585 OBO::NoSignedWrap
));
1587 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1589 ConstantRange(APInt(32, -32), APInt(32, 16) + 1),
1590 OBO::NoUnsignedWrap
),
1591 ConstantRange(APInt(32, 0), APInt(32, 65535) + 1));
1592 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1594 ConstantRange(APInt(32, -32), APInt(32, 16) + 1),
1596 ConstantRange(APInt(32, -32768), APInt(32, 32767) + 1));
1599 template<typename Fn
>
1600 void TestNoWrapRegionExhaustive(Instruction::BinaryOps BinOp
,
1601 unsigned NoWrapKind
, Fn OverflowFn
) {
1603 EnumerateConstantRanges(Bits
, [&](const ConstantRange
&CR
) {
1604 if (CR
.isEmptySet())
1606 if (Instruction::isShift(BinOp
) && CR
.getUnsignedMax().uge(Bits
))
1609 ConstantRange NoWrap
=
1610 ConstantRange::makeGuaranteedNoWrapRegion(BinOp
, CR
, NoWrapKind
);
1611 ConstantRange Full
= ConstantRange::getFull(Bits
);
1612 ForeachNumInConstantRange(Full
, [&](const APInt
&N1
) {
1613 bool NoOverflow
= true;
1614 bool Overflow
= true;
1615 ForeachNumInConstantRange(CR
, [&](const APInt
&N2
) {
1616 if (OverflowFn(N1
, N2
))
1621 EXPECT_EQ(NoOverflow
, NoWrap
.contains(N1
));
1623 // The no-wrap range is exact for single-element ranges.
1624 if (CR
.isSingleElement()) {
1625 EXPECT_EQ(Overflow
, !NoWrap
.contains(N1
));
1631 // Show that makeGuaranteedNoWrapRegion() is maximal, and for single-element
1632 // ranges also exact.
1633 TEST(ConstantRange
, NoWrapRegionExhaustive
) {
1634 TestNoWrapRegionExhaustive(
1635 Instruction::Add
, OverflowingBinaryOperator::NoUnsignedWrap
,
1636 [](const APInt
&N1
, const APInt
&N2
) {
1638 (void) N1
.uadd_ov(N2
, Overflow
);
1641 TestNoWrapRegionExhaustive(
1642 Instruction::Add
, OverflowingBinaryOperator::NoSignedWrap
,
1643 [](const APInt
&N1
, const APInt
&N2
) {
1645 (void) N1
.sadd_ov(N2
, Overflow
);
1648 TestNoWrapRegionExhaustive(
1649 Instruction::Sub
, OverflowingBinaryOperator::NoUnsignedWrap
,
1650 [](const APInt
&N1
, const APInt
&N2
) {
1652 (void) N1
.usub_ov(N2
, Overflow
);
1655 TestNoWrapRegionExhaustive(
1656 Instruction::Sub
, OverflowingBinaryOperator::NoSignedWrap
,
1657 [](const APInt
&N1
, const APInt
&N2
) {
1659 (void) N1
.ssub_ov(N2
, Overflow
);
1662 TestNoWrapRegionExhaustive(
1663 Instruction::Mul
, OverflowingBinaryOperator::NoUnsignedWrap
,
1664 [](const APInt
&N1
, const APInt
&N2
) {
1666 (void) N1
.umul_ov(N2
, Overflow
);
1669 TestNoWrapRegionExhaustive(
1670 Instruction::Mul
, OverflowingBinaryOperator::NoSignedWrap
,
1671 [](const APInt
&N1
, const APInt
&N2
) {
1673 (void) N1
.smul_ov(N2
, Overflow
);
1676 TestNoWrapRegionExhaustive(Instruction::Shl
,
1677 OverflowingBinaryOperator::NoUnsignedWrap
,
1678 [](const APInt
&N1
, const APInt
&N2
) {
1680 (void)N1
.ushl_ov(N2
, Overflow
);
1683 TestNoWrapRegionExhaustive(Instruction::Shl
,
1684 OverflowingBinaryOperator::NoSignedWrap
,
1685 [](const APInt
&N1
, const APInt
&N2
) {
1687 (void)N1
.sshl_ov(N2
, Overflow
);
1692 TEST(ConstantRange
, GetEquivalentICmp
) {
1694 CmpInst::Predicate Pred
;
1696 EXPECT_TRUE(ConstantRange(APInt::getMinValue(32), APInt(32, 100))
1697 .getEquivalentICmp(Pred
, RHS
));
1698 EXPECT_EQ(Pred
, CmpInst::ICMP_ULT
);
1699 EXPECT_EQ(RHS
, APInt(32, 100));
1701 EXPECT_TRUE(ConstantRange(APInt::getSignedMinValue(32), APInt(32, 100))
1702 .getEquivalentICmp(Pred
, RHS
));
1703 EXPECT_EQ(Pred
, CmpInst::ICMP_SLT
);
1704 EXPECT_EQ(RHS
, APInt(32, 100));
1706 EXPECT_TRUE(ConstantRange(APInt(32, 100), APInt::getMinValue(32))
1707 .getEquivalentICmp(Pred
, RHS
));
1708 EXPECT_EQ(Pred
, CmpInst::ICMP_UGE
);
1709 EXPECT_EQ(RHS
, APInt(32, 100));
1711 EXPECT_TRUE(ConstantRange(APInt(32, 100), APInt::getSignedMinValue(32))
1712 .getEquivalentICmp(Pred
, RHS
));
1713 EXPECT_EQ(Pred
, CmpInst::ICMP_SGE
);
1714 EXPECT_EQ(RHS
, APInt(32, 100));
1717 ConstantRange(32, /*isFullSet=*/true).getEquivalentICmp(Pred
, RHS
));
1718 EXPECT_EQ(Pred
, CmpInst::ICMP_UGE
);
1719 EXPECT_EQ(RHS
, APInt(32, 0));
1722 ConstantRange(32, /*isFullSet=*/false).getEquivalentICmp(Pred
, RHS
));
1723 EXPECT_EQ(Pred
, CmpInst::ICMP_ULT
);
1724 EXPECT_EQ(RHS
, APInt(32, 0));
1726 EXPECT_FALSE(ConstantRange(APInt(32, 100), APInt(32, 200))
1727 .getEquivalentICmp(Pred
, RHS
));
1729 EXPECT_FALSE(ConstantRange(APInt::getSignedMinValue(32) - APInt(32, 100),
1730 APInt::getSignedMinValue(32) + APInt(32, 100))
1731 .getEquivalentICmp(Pred
, RHS
));
1733 EXPECT_FALSE(ConstantRange(APInt::getMinValue(32) - APInt(32, 100),
1734 APInt::getMinValue(32) + APInt(32, 100))
1735 .getEquivalentICmp(Pred
, RHS
));
1737 EXPECT_TRUE(ConstantRange(APInt(32, 100)).getEquivalentICmp(Pred
, RHS
));
1738 EXPECT_EQ(Pred
, CmpInst::ICMP_EQ
);
1739 EXPECT_EQ(RHS
, APInt(32, 100));
1742 ConstantRange(APInt(32, 100)).inverse().getEquivalentICmp(Pred
, RHS
));
1743 EXPECT_EQ(Pred
, CmpInst::ICMP_NE
);
1744 EXPECT_EQ(RHS
, APInt(32, 100));
1747 ConstantRange(APInt(512, 100)).inverse().getEquivalentICmp(Pred
, RHS
));
1748 EXPECT_EQ(Pred
, CmpInst::ICMP_NE
);
1749 EXPECT_EQ(RHS
, APInt(512, 100));
1751 // NB! It would be correct for the following four calls to getEquivalentICmp
1752 // to return ordered predicates like CmpInst::ICMP_ULT or CmpInst::ICMP_UGT.
1753 // However, that's not the case today.
1755 EXPECT_TRUE(ConstantRange(APInt(32, 0)).getEquivalentICmp(Pred
, RHS
));
1756 EXPECT_EQ(Pred
, CmpInst::ICMP_EQ
);
1757 EXPECT_EQ(RHS
, APInt(32, 0));
1760 ConstantRange(APInt(32, 0)).inverse().getEquivalentICmp(Pred
, RHS
));
1761 EXPECT_EQ(Pred
, CmpInst::ICMP_NE
);
1762 EXPECT_EQ(RHS
, APInt(32, 0));
1764 EXPECT_TRUE(ConstantRange(APInt(32, -1)).getEquivalentICmp(Pred
, RHS
));
1765 EXPECT_EQ(Pred
, CmpInst::ICMP_EQ
);
1766 EXPECT_EQ(RHS
, APInt(32, -1));
1769 ConstantRange(APInt(32, -1)).inverse().getEquivalentICmp(Pred
, RHS
));
1770 EXPECT_EQ(Pred
, CmpInst::ICMP_NE
);
1771 EXPECT_EQ(RHS
, APInt(32, -1));
1774 #define EXPECT_MAY_OVERFLOW(op) \
1775 EXPECT_EQ(ConstantRange::OverflowResult::MayOverflow, (op))
1776 #define EXPECT_ALWAYS_OVERFLOWS_LOW(op) \
1777 EXPECT_EQ(ConstantRange::OverflowResult::AlwaysOverflowsLow, (op))
1778 #define EXPECT_ALWAYS_OVERFLOWS_HIGH(op) \
1779 EXPECT_EQ(ConstantRange::OverflowResult::AlwaysOverflowsHigh, (op))
1780 #define EXPECT_NEVER_OVERFLOWS(op) \
1781 EXPECT_EQ(ConstantRange::OverflowResult::NeverOverflows, (op))
1783 TEST_F(ConstantRangeTest
, UnsignedAddOverflow
) {
1784 // Ill-defined - may overflow is a conservative result.
1785 EXPECT_MAY_OVERFLOW(Some
.unsignedAddMayOverflow(Empty
));
1786 EXPECT_MAY_OVERFLOW(Empty
.unsignedAddMayOverflow(Some
));
1788 // Never overflow despite one full/wrap set.
1789 ConstantRange
Zero(APInt::getNullValue(16));
1790 EXPECT_NEVER_OVERFLOWS(Full
.unsignedAddMayOverflow(Zero
));
1791 EXPECT_NEVER_OVERFLOWS(Wrap
.unsignedAddMayOverflow(Zero
));
1792 EXPECT_NEVER_OVERFLOWS(Zero
.unsignedAddMayOverflow(Full
));
1793 EXPECT_NEVER_OVERFLOWS(Zero
.unsignedAddMayOverflow(Wrap
));
1795 // But usually full/wrap always may overflow.
1796 EXPECT_MAY_OVERFLOW(Full
.unsignedAddMayOverflow(One
));
1797 EXPECT_MAY_OVERFLOW(Wrap
.unsignedAddMayOverflow(One
));
1798 EXPECT_MAY_OVERFLOW(One
.unsignedAddMayOverflow(Full
));
1799 EXPECT_MAY_OVERFLOW(One
.unsignedAddMayOverflow(Wrap
));
1801 ConstantRange
A(APInt(16, 0xfd00), APInt(16, 0xfe00));
1802 ConstantRange
B1(APInt(16, 0x0100), APInt(16, 0x0201));
1803 ConstantRange
B2(APInt(16, 0x0100), APInt(16, 0x0202));
1804 EXPECT_NEVER_OVERFLOWS(A
.unsignedAddMayOverflow(B1
));
1805 EXPECT_MAY_OVERFLOW(A
.unsignedAddMayOverflow(B2
));
1806 EXPECT_NEVER_OVERFLOWS(B1
.unsignedAddMayOverflow(A
));
1807 EXPECT_MAY_OVERFLOW(B2
.unsignedAddMayOverflow(A
));
1809 ConstantRange
C1(APInt(16, 0x0299), APInt(16, 0x0400));
1810 ConstantRange
C2(APInt(16, 0x0300), APInt(16, 0x0400));
1811 EXPECT_MAY_OVERFLOW(A
.unsignedAddMayOverflow(C1
));
1812 EXPECT_ALWAYS_OVERFLOWS_HIGH(A
.unsignedAddMayOverflow(C2
));
1813 EXPECT_MAY_OVERFLOW(C1
.unsignedAddMayOverflow(A
));
1814 EXPECT_ALWAYS_OVERFLOWS_HIGH(C2
.unsignedAddMayOverflow(A
));
1817 TEST_F(ConstantRangeTest
, UnsignedSubOverflow
) {
1818 // Ill-defined - may overflow is a conservative result.
1819 EXPECT_MAY_OVERFLOW(Some
.unsignedSubMayOverflow(Empty
));
1820 EXPECT_MAY_OVERFLOW(Empty
.unsignedSubMayOverflow(Some
));
1822 // Never overflow despite one full/wrap set.
1823 ConstantRange
Zero(APInt::getNullValue(16));
1824 ConstantRange
Max(APInt::getAllOnesValue(16));
1825 EXPECT_NEVER_OVERFLOWS(Full
.unsignedSubMayOverflow(Zero
));
1826 EXPECT_NEVER_OVERFLOWS(Wrap
.unsignedSubMayOverflow(Zero
));
1827 EXPECT_NEVER_OVERFLOWS(Max
.unsignedSubMayOverflow(Full
));
1828 EXPECT_NEVER_OVERFLOWS(Max
.unsignedSubMayOverflow(Wrap
));
1830 // But usually full/wrap always may overflow.
1831 EXPECT_MAY_OVERFLOW(Full
.unsignedSubMayOverflow(One
));
1832 EXPECT_MAY_OVERFLOW(Wrap
.unsignedSubMayOverflow(One
));
1833 EXPECT_MAY_OVERFLOW(One
.unsignedSubMayOverflow(Full
));
1834 EXPECT_MAY_OVERFLOW(One
.unsignedSubMayOverflow(Wrap
));
1836 ConstantRange
A(APInt(16, 0x0000), APInt(16, 0x0100));
1837 ConstantRange
B(APInt(16, 0x0100), APInt(16, 0x0200));
1838 EXPECT_NEVER_OVERFLOWS(B
.unsignedSubMayOverflow(A
));
1839 EXPECT_ALWAYS_OVERFLOWS_LOW(A
.unsignedSubMayOverflow(B
));
1841 ConstantRange
A1(APInt(16, 0x0000), APInt(16, 0x0101));
1842 ConstantRange
B1(APInt(16, 0x0100), APInt(16, 0x0201));
1843 EXPECT_NEVER_OVERFLOWS(B1
.unsignedSubMayOverflow(A1
));
1844 EXPECT_MAY_OVERFLOW(A1
.unsignedSubMayOverflow(B1
));
1846 ConstantRange
A2(APInt(16, 0x0000), APInt(16, 0x0102));
1847 ConstantRange
B2(APInt(16, 0x0100), APInt(16, 0x0202));
1848 EXPECT_MAY_OVERFLOW(B2
.unsignedSubMayOverflow(A2
));
1849 EXPECT_MAY_OVERFLOW(A2
.unsignedSubMayOverflow(B2
));
1852 TEST_F(ConstantRangeTest
, SignedAddOverflow
) {
1853 // Ill-defined - may overflow is a conservative result.
1854 EXPECT_MAY_OVERFLOW(Some
.signedAddMayOverflow(Empty
));
1855 EXPECT_MAY_OVERFLOW(Empty
.signedAddMayOverflow(Some
));
1857 // Never overflow despite one full/wrap set.
1858 ConstantRange
Zero(APInt::getNullValue(16));
1859 EXPECT_NEVER_OVERFLOWS(Full
.signedAddMayOverflow(Zero
));
1860 EXPECT_NEVER_OVERFLOWS(Wrap
.signedAddMayOverflow(Zero
));
1861 EXPECT_NEVER_OVERFLOWS(Zero
.signedAddMayOverflow(Full
));
1862 EXPECT_NEVER_OVERFLOWS(Zero
.signedAddMayOverflow(Wrap
));
1864 // But usually full/wrap always may overflow.
1865 EXPECT_MAY_OVERFLOW(Full
.signedAddMayOverflow(One
));
1866 EXPECT_MAY_OVERFLOW(Wrap
.signedAddMayOverflow(One
));
1867 EXPECT_MAY_OVERFLOW(One
.signedAddMayOverflow(Full
));
1868 EXPECT_MAY_OVERFLOW(One
.signedAddMayOverflow(Wrap
));
1870 ConstantRange
A(APInt(16, 0x7d00), APInt(16, 0x7e00));
1871 ConstantRange
B1(APInt(16, 0x0100), APInt(16, 0x0201));
1872 ConstantRange
B2(APInt(16, 0x0100), APInt(16, 0x0202));
1873 EXPECT_NEVER_OVERFLOWS(A
.signedAddMayOverflow(B1
));
1874 EXPECT_MAY_OVERFLOW(A
.signedAddMayOverflow(B2
));
1875 ConstantRange
B3(APInt(16, 0x8000), APInt(16, 0x0201));
1876 ConstantRange
B4(APInt(16, 0x8000), APInt(16, 0x0202));
1877 EXPECT_NEVER_OVERFLOWS(A
.signedAddMayOverflow(B3
));
1878 EXPECT_MAY_OVERFLOW(A
.signedAddMayOverflow(B4
));
1879 ConstantRange
B5(APInt(16, 0x0299), APInt(16, 0x0400));
1880 ConstantRange
B6(APInt(16, 0x0300), APInt(16, 0x0400));
1881 EXPECT_MAY_OVERFLOW(A
.signedAddMayOverflow(B5
));
1882 EXPECT_ALWAYS_OVERFLOWS_HIGH(A
.signedAddMayOverflow(B6
));
1884 ConstantRange
C(APInt(16, 0x8200), APInt(16, 0x8300));
1885 ConstantRange
D1(APInt(16, 0xfe00), APInt(16, 0xff00));
1886 ConstantRange
D2(APInt(16, 0xfd99), APInt(16, 0xff00));
1887 EXPECT_NEVER_OVERFLOWS(C
.signedAddMayOverflow(D1
));
1888 EXPECT_MAY_OVERFLOW(C
.signedAddMayOverflow(D2
));
1889 ConstantRange
D3(APInt(16, 0xfe00), APInt(16, 0x8000));
1890 ConstantRange
D4(APInt(16, 0xfd99), APInt(16, 0x8000));
1891 EXPECT_NEVER_OVERFLOWS(C
.signedAddMayOverflow(D3
));
1892 EXPECT_MAY_OVERFLOW(C
.signedAddMayOverflow(D4
));
1893 ConstantRange
D5(APInt(16, 0xfc00), APInt(16, 0xfd02));
1894 ConstantRange
D6(APInt(16, 0xfc00), APInt(16, 0xfd01));
1895 EXPECT_MAY_OVERFLOW(C
.signedAddMayOverflow(D5
));
1896 EXPECT_ALWAYS_OVERFLOWS_LOW(C
.signedAddMayOverflow(D6
));
1898 ConstantRange
E(APInt(16, 0xff00), APInt(16, 0x0100));
1899 EXPECT_NEVER_OVERFLOWS(E
.signedAddMayOverflow(E
));
1900 ConstantRange
F(APInt(16, 0xf000), APInt(16, 0x7000));
1901 EXPECT_MAY_OVERFLOW(F
.signedAddMayOverflow(F
));
1904 TEST_F(ConstantRangeTest
, SignedSubOverflow
) {
1905 // Ill-defined - may overflow is a conservative result.
1906 EXPECT_MAY_OVERFLOW(Some
.signedSubMayOverflow(Empty
));
1907 EXPECT_MAY_OVERFLOW(Empty
.signedSubMayOverflow(Some
));
1909 // Never overflow despite one full/wrap set.
1910 ConstantRange
Zero(APInt::getNullValue(16));
1911 EXPECT_NEVER_OVERFLOWS(Full
.signedSubMayOverflow(Zero
));
1912 EXPECT_NEVER_OVERFLOWS(Wrap
.signedSubMayOverflow(Zero
));
1914 // But usually full/wrap always may overflow.
1915 EXPECT_MAY_OVERFLOW(Full
.signedSubMayOverflow(One
));
1916 EXPECT_MAY_OVERFLOW(Wrap
.signedSubMayOverflow(One
));
1917 EXPECT_MAY_OVERFLOW(One
.signedSubMayOverflow(Full
));
1918 EXPECT_MAY_OVERFLOW(One
.signedSubMayOverflow(Wrap
));
1920 ConstantRange
A(APInt(16, 0x7d00), APInt(16, 0x7e00));
1921 ConstantRange
B1(APInt(16, 0xfe00), APInt(16, 0xff00));
1922 ConstantRange
B2(APInt(16, 0xfd99), APInt(16, 0xff00));
1923 EXPECT_NEVER_OVERFLOWS(A
.signedSubMayOverflow(B1
));
1924 EXPECT_MAY_OVERFLOW(A
.signedSubMayOverflow(B2
));
1925 ConstantRange
B3(APInt(16, 0xfc00), APInt(16, 0xfd02));
1926 ConstantRange
B4(APInt(16, 0xfc00), APInt(16, 0xfd01));
1927 EXPECT_MAY_OVERFLOW(A
.signedSubMayOverflow(B3
));
1928 EXPECT_ALWAYS_OVERFLOWS_HIGH(A
.signedSubMayOverflow(B4
));
1930 ConstantRange
C(APInt(16, 0x8200), APInt(16, 0x8300));
1931 ConstantRange
D1(APInt(16, 0x0100), APInt(16, 0x0201));
1932 ConstantRange
D2(APInt(16, 0x0100), APInt(16, 0x0202));
1933 EXPECT_NEVER_OVERFLOWS(C
.signedSubMayOverflow(D1
));
1934 EXPECT_MAY_OVERFLOW(C
.signedSubMayOverflow(D2
));
1935 ConstantRange
D3(APInt(16, 0x0299), APInt(16, 0x0400));
1936 ConstantRange
D4(APInt(16, 0x0300), APInt(16, 0x0400));
1937 EXPECT_MAY_OVERFLOW(C
.signedSubMayOverflow(D3
));
1938 EXPECT_ALWAYS_OVERFLOWS_LOW(C
.signedSubMayOverflow(D4
));
1940 ConstantRange
E(APInt(16, 0xff00), APInt(16, 0x0100));
1941 EXPECT_NEVER_OVERFLOWS(E
.signedSubMayOverflow(E
));
1942 ConstantRange
F(APInt(16, 0xf000), APInt(16, 0x7001));
1943 EXPECT_MAY_OVERFLOW(F
.signedSubMayOverflow(F
));
1946 template<typename Fn1
, typename Fn2
>
1947 static void TestOverflowExhaustive(Fn1 OverflowFn
, Fn2 MayOverflowFn
) {
1948 // Constant range overflow checks are tested exhaustively on 4-bit numbers.
1950 EnumerateTwoConstantRanges(Bits
, [=](const ConstantRange
&CR1
,
1951 const ConstantRange
&CR2
) {
1952 // Loop over all N1 in CR1 and N2 in CR2 and check whether any of the
1953 // operations have overflow / have no overflow.
1954 bool RangeHasOverflowLow
= false;
1955 bool RangeHasOverflowHigh
= false;
1956 bool RangeHasNoOverflow
= false;
1957 ForeachNumInConstantRange(CR1
, [&](const APInt
&N1
) {
1958 ForeachNumInConstantRange(CR2
, [&](const APInt
&N2
) {
1959 bool IsOverflowHigh
;
1960 if (!OverflowFn(IsOverflowHigh
, N1
, N2
)) {
1961 RangeHasNoOverflow
= true;
1966 RangeHasOverflowHigh
= true;
1968 RangeHasOverflowLow
= true;
1972 ConstantRange::OverflowResult OR
= MayOverflowFn(CR1
, CR2
);
1974 case ConstantRange::OverflowResult::AlwaysOverflowsLow
:
1975 EXPECT_TRUE(RangeHasOverflowLow
);
1976 EXPECT_FALSE(RangeHasOverflowHigh
);
1977 EXPECT_FALSE(RangeHasNoOverflow
);
1979 case ConstantRange::OverflowResult::AlwaysOverflowsHigh
:
1980 EXPECT_TRUE(RangeHasOverflowHigh
);
1981 EXPECT_FALSE(RangeHasOverflowLow
);
1982 EXPECT_FALSE(RangeHasNoOverflow
);
1984 case ConstantRange::OverflowResult::NeverOverflows
:
1985 EXPECT_FALSE(RangeHasOverflowLow
);
1986 EXPECT_FALSE(RangeHasOverflowHigh
);
1987 EXPECT_TRUE(RangeHasNoOverflow
);
1989 case ConstantRange::OverflowResult::MayOverflow
:
1990 // We return MayOverflow for empty sets as a conservative result,
1991 // but of course neither the RangeHasOverflow nor the
1992 // RangeHasNoOverflow flags will be set.
1993 if (CR1
.isEmptySet() || CR2
.isEmptySet())
1996 EXPECT_TRUE(RangeHasOverflowLow
|| RangeHasOverflowHigh
);
1997 EXPECT_TRUE(RangeHasNoOverflow
);
2003 TEST_F(ConstantRangeTest
, UnsignedAddOverflowExhaustive
) {
2004 TestOverflowExhaustive(
2005 [](bool &IsOverflowHigh
, const APInt
&N1
, const APInt
&N2
) {
2007 (void) N1
.uadd_ov(N2
, Overflow
);
2008 IsOverflowHigh
= true;
2011 [](const ConstantRange
&CR1
, const ConstantRange
&CR2
) {
2012 return CR1
.unsignedAddMayOverflow(CR2
);
2016 TEST_F(ConstantRangeTest
, UnsignedSubOverflowExhaustive
) {
2017 TestOverflowExhaustive(
2018 [](bool &IsOverflowHigh
, const APInt
&N1
, const APInt
&N2
) {
2020 (void) N1
.usub_ov(N2
, Overflow
);
2021 IsOverflowHigh
= false;
2024 [](const ConstantRange
&CR1
, const ConstantRange
&CR2
) {
2025 return CR1
.unsignedSubMayOverflow(CR2
);
2029 TEST_F(ConstantRangeTest
, UnsignedMulOverflowExhaustive
) {
2030 TestOverflowExhaustive(
2031 [](bool &IsOverflowHigh
, const APInt
&N1
, const APInt
&N2
) {
2033 (void) N1
.umul_ov(N2
, Overflow
);
2034 IsOverflowHigh
= true;
2037 [](const ConstantRange
&CR1
, const ConstantRange
&CR2
) {
2038 return CR1
.unsignedMulMayOverflow(CR2
);
2042 TEST_F(ConstantRangeTest
, SignedAddOverflowExhaustive
) {
2043 TestOverflowExhaustive(
2044 [](bool &IsOverflowHigh
, const APInt
&N1
, const APInt
&N2
) {
2046 (void) N1
.sadd_ov(N2
, Overflow
);
2047 IsOverflowHigh
= N1
.isNonNegative();
2050 [](const ConstantRange
&CR1
, const ConstantRange
&CR2
) {
2051 return CR1
.signedAddMayOverflow(CR2
);
2055 TEST_F(ConstantRangeTest
, SignedSubOverflowExhaustive
) {
2056 TestOverflowExhaustive(
2057 [](bool &IsOverflowHigh
, const APInt
&N1
, const APInt
&N2
) {
2059 (void) N1
.ssub_ov(N2
, Overflow
);
2060 IsOverflowHigh
= N1
.isNonNegative();
2063 [](const ConstantRange
&CR1
, const ConstantRange
&CR2
) {
2064 return CR1
.signedSubMayOverflow(CR2
);
2068 TEST_F(ConstantRangeTest
, FromKnownBits
) {
2069 KnownBits
Unknown(16);
2070 EXPECT_EQ(Full
, ConstantRange::fromKnownBits(Unknown
, /*signed*/false));
2071 EXPECT_EQ(Full
, ConstantRange::fromKnownBits(Unknown
, /*signed*/true));
2073 // .10..01. -> unsigned 01000010 (66) to 11011011 (219)
2074 // -> signed 11000010 (194) to 01011011 (91)
2078 ConstantRange
Unsigned(APInt(8, 66), APInt(8, 219 + 1));
2079 ConstantRange
Signed(APInt(8, 194), APInt(8, 91 + 1));
2080 EXPECT_EQ(Unsigned
, ConstantRange::fromKnownBits(Known
, /*signed*/false));
2081 EXPECT_EQ(Signed
, ConstantRange::fromKnownBits(Known
, /*signed*/true));
2083 // 1.10.10. -> 10100100 (164) to 11101101 (237)
2086 ConstantRange
CR1(APInt(8, 164), APInt(8, 237 + 1));
2087 EXPECT_EQ(CR1
, ConstantRange::fromKnownBits(Known
, /*signed*/false));
2088 EXPECT_EQ(CR1
, ConstantRange::fromKnownBits(Known
, /*signed*/true));
2090 // 01.0.1.0 -> 01000100 (68) to 01101110 (110)
2093 ConstantRange
CR2(APInt(8, 68), APInt(8, 110 + 1));
2094 EXPECT_EQ(CR2
, ConstantRange::fromKnownBits(Known
, /*signed*/false));
2095 EXPECT_EQ(CR2
, ConstantRange::fromKnownBits(Known
, /*signed*/true));
2098 TEST_F(ConstantRangeTest
, FromKnownBitsExhaustive
) {
2100 unsigned Max
= 1 << Bits
;
2101 KnownBits
Known(Bits
);
2102 for (unsigned Zero
= 0; Zero
< Max
; ++Zero
) {
2103 for (unsigned One
= 0; One
< Max
; ++One
) {
2106 if (Known
.hasConflict() || Known
.isUnknown())
2109 APInt MinUnsigned
= APInt::getMaxValue(Bits
);
2110 APInt MaxUnsigned
= APInt::getMinValue(Bits
);
2111 APInt MinSigned
= APInt::getSignedMaxValue(Bits
);
2112 APInt MaxSigned
= APInt::getSignedMinValue(Bits
);
2113 for (unsigned N
= 0; N
< Max
; ++N
) {
2115 if ((Num
& Known
.Zero
) != 0 || (~Num
& Known
.One
) != 0)
2118 if (Num
.ult(MinUnsigned
)) MinUnsigned
= Num
;
2119 if (Num
.ugt(MaxUnsigned
)) MaxUnsigned
= Num
;
2120 if (Num
.slt(MinSigned
)) MinSigned
= Num
;
2121 if (Num
.sgt(MaxSigned
)) MaxSigned
= Num
;
2124 ConstantRange
UnsignedCR(MinUnsigned
, MaxUnsigned
+ 1);
2125 ConstantRange
SignedCR(MinSigned
, MaxSigned
+ 1);
2126 EXPECT_EQ(UnsignedCR
, ConstantRange::fromKnownBits(Known
, false));
2127 EXPECT_EQ(SignedCR
, ConstantRange::fromKnownBits(Known
, true));
2132 TEST_F(ConstantRangeTest
, Negative
) {
2133 // All elements in an empty set (of which there are none) are both negative
2134 // and non-negative. Empty & full sets checked explicitly for clarity, but
2135 // they are also covered by the exhaustive test below.
2136 EXPECT_TRUE(Empty
.isAllNegative());
2137 EXPECT_TRUE(Empty
.isAllNonNegative());
2138 EXPECT_FALSE(Full
.isAllNegative());
2139 EXPECT_FALSE(Full
.isAllNonNegative());
2142 EnumerateConstantRanges(Bits
, [](const ConstantRange
&CR
) {
2143 bool AllNegative
= true;
2144 bool AllNonNegative
= true;
2145 ForeachNumInConstantRange(CR
, [&](const APInt
&N
) {
2146 if (!N
.isNegative())
2147 AllNegative
= false;
2148 if (!N
.isNonNegative())
2149 AllNonNegative
= false;
2151 assert((CR
.isEmptySet() || !AllNegative
|| !AllNonNegative
) &&
2152 "Only empty set can be both all negative and all non-negative");
2154 EXPECT_EQ(AllNegative
, CR
.isAllNegative());
2155 EXPECT_EQ(AllNonNegative
, CR
.isAllNonNegative());
2159 TEST_F(ConstantRangeTest
, UAddSat
) {
2160 TestUnsignedBinOpExhaustive(
2161 [](const ConstantRange
&CR1
, const ConstantRange
&CR2
) {
2162 return CR1
.uadd_sat(CR2
);
2164 [](const APInt
&N1
, const APInt
&N2
) {
2165 return N1
.uadd_sat(N2
);
2169 TEST_F(ConstantRangeTest
, USubSat
) {
2170 TestUnsignedBinOpExhaustive(
2171 [](const ConstantRange
&CR1
, const ConstantRange
&CR2
) {
2172 return CR1
.usub_sat(CR2
);
2174 [](const APInt
&N1
, const APInt
&N2
) {
2175 return N1
.usub_sat(N2
);
2179 TEST_F(ConstantRangeTest
, SAddSat
) {
2180 TestSignedBinOpExhaustive(
2181 [](const ConstantRange
&CR1
, const ConstantRange
&CR2
) {
2182 return CR1
.sadd_sat(CR2
);
2184 [](const APInt
&N1
, const APInt
&N2
) {
2185 return N1
.sadd_sat(N2
);
2189 TEST_F(ConstantRangeTest
, SSubSat
) {
2190 TestSignedBinOpExhaustive(
2191 [](const ConstantRange
&CR1
, const ConstantRange
&CR2
) {
2192 return CR1
.ssub_sat(CR2
);
2194 [](const APInt
&N1
, const APInt
&N2
) {
2195 return N1
.ssub_sat(N2
);
2199 TEST_F(ConstantRangeTest
, Abs
) {
2201 EnumerateConstantRanges(Bits
, [&](const ConstantRange
&CR
) {
2202 // We're working with unsigned integers here, because it makes the signed
2203 // min case non-wrapping.
2204 APInt Min
= APInt::getMaxValue(Bits
);
2205 APInt Max
= APInt::getMinValue(Bits
);
2206 ForeachNumInConstantRange(CR
, [&](const APInt
&N
) {
2207 APInt AbsN
= N
.abs();
2214 ConstantRange AbsCR
= CR
.abs();
2216 EXPECT_TRUE(AbsCR
.isEmptySet());
2220 ConstantRange Exact
= ConstantRange::getNonEmpty(Min
, Max
+ 1);
2221 EXPECT_EQ(Exact
, AbsCR
);
2225 } // anonymous namespace