?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Bump version to 19.1.0-rc3
[llvm-project.git] / llvm / unittests / IR / ConstantRangeTest.cpp
blob0181e2ce6ac92cdc0b7dd0180c006ad6c7a49698
1 //===- ConstantRangeTest.cpp - ConstantRange tests ------------------------===//
2 //
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
6 //
7 //===----------------------------------------------------------------------===//
8
9 #include "llvm/IR/ConstantRange.h"
10 #include "llvm/ADT/BitVector.h"
11 #include "llvm/ADT/Sequence.h"
12 #include "llvm/ADT/SmallBitVector.h"
13 #include "llvm/IR/Instructions.h"
14 #include "llvm/IR/Operator.h"
15 #include "llvm/Support/KnownBits.h"
16 #include "gtest/gtest.h"
17
18 using namespace llvm;
19
20 namespace {
21
22 class ConstantRangeTest : public ::testing::Test {
23 protected:
24 static ConstantRange Full;
25 static ConstantRange Empty;
26 static ConstantRange One;
27 static ConstantRange Some;
28 static ConstantRange Wrap;
29 };
30
31 template<typename Fn>
32 static void EnumerateAPInts(unsigned Bits, Fn TestFn) {
33 APInt N(Bits, 0);
34 do {
35 TestFn(N);
36 } while (++N != 0);
37 }
38
39 template<typename Fn>
40 static void EnumerateConstantRanges(unsigned Bits, Fn TestFn) {
41 unsigned Max = 1 << Bits;
42 for (unsigned Lo = 0; Lo < Max; Lo++) {
43 for (unsigned Hi = 0; Hi < Max; Hi++) {
44 // Enforce ConstantRange invariant.
45 if (Lo == Hi && Lo != 0 && Lo != Max - 1)
46 continue;
47
48 ConstantRange CR(APInt(Bits, Lo), APInt(Bits, Hi));
49 TestFn(CR);
50 }
51 }
52 }
53
54 template <typename Fn>
55 static void EnumerateInterestingConstantRanges(Fn TestFn) {
56 // Check 1 bit ranges, because they may have special cases.
57 EnumerateConstantRanges(/* Bits */ 1, TestFn);
58 // Check 4 bit ranges to have decent coverage without being too slow.
59 EnumerateConstantRanges(/* Bits */ 4, TestFn);
60 }
61
62 template <typename Fn>
63 static void EnumerateTwoInterestingConstantRanges(Fn TestFn) {
64 for (unsigned Bits : {1, 4}) {
65 EnumerateConstantRanges(Bits, [&](const ConstantRange &CR1) {
66 EnumerateConstantRanges(
67 Bits, [&](const ConstantRange &CR2) { TestFn(CR1, CR2); });
68 });
69 }
70 }
71
72 template <typename Fn>
73 static void ForeachNumInConstantRange(const ConstantRange &CR, Fn TestFn) {
74 if (!CR.isEmptySet()) {
75 APInt N = CR.getLower();
76 do TestFn(N);
77 while (++N != CR.getUpper());
78 }
79 }
80
81 using PreferFn = llvm::function_ref<bool(const ConstantRange &,
82 const ConstantRange &)>;
83
84 bool PreferSmallest(const ConstantRange &CR1, const ConstantRange &CR2) {
85 return CR1.isSizeStrictlySmallerThan(CR2);
86 }
87
88 bool PreferSmallestUnsigned(const ConstantRange &CR1,
89 const ConstantRange &CR2) {
90 if (CR1.isWrappedSet() != CR2.isWrappedSet())
91 return CR1.isWrappedSet() < CR2.isWrappedSet();
92 return PreferSmallest(CR1, CR2);
93 }
94
95 bool PreferSmallestSigned(const ConstantRange &CR1, const ConstantRange &CR2) {
96 if (CR1.isSignWrappedSet() != CR2.isSignWrappedSet())
97 return CR1.isSignWrappedSet() < CR2.isSignWrappedSet();
98 return PreferSmallest(CR1, CR2);
99 }
100
101 bool PreferSmallestNonFullUnsigned(const ConstantRange &CR1,
102 const ConstantRange &CR2) {
103 if (CR1.isFullSet() != CR2.isFullSet())
104 return CR1.isFullSet() < CR2.isFullSet();
105 return PreferSmallestUnsigned(CR1, CR2);
106 }
107
108 bool PreferSmallestNonFullSigned(const ConstantRange &CR1,
109 const ConstantRange &CR2) {
110 if (CR1.isFullSet() != CR2.isFullSet())
111 return CR1.isFullSet() < CR2.isFullSet();
112 return PreferSmallestSigned(CR1, CR2);
113 }
114
115 testing::AssertionResult rangeContains(const ConstantRange &CR, const APInt &N,
116 ArrayRef<ConstantRange> Inputs) {
117 if (CR.contains(N))
118 return testing::AssertionSuccess();
119
120 testing::AssertionResult Result = testing::AssertionFailure();
121 Result << CR << " does not contain " << N << " for inputs: ";
122 for (const ConstantRange &Input : Inputs)
123 Result << Input << ", ";
124 return Result;
125 }
126
127 // Check whether constant range CR is an optimal approximation of the set
128 // Elems under the given PreferenceFn. The preference function should return
129 // true if the first range argument is strictly preferred to the second one.
130 static void TestRange(const ConstantRange &CR, const SmallBitVector &Elems,
131 PreferFn PreferenceFn, ArrayRef<ConstantRange> Inputs,
132 bool CheckOptimality = true) {
133 unsigned BitWidth = CR.getBitWidth();
134
135 // Check conservative correctness.
136 for (unsigned Elem : Elems.set_bits()) {
137 EXPECT_TRUE(rangeContains(CR, APInt(BitWidth, Elem), Inputs));
138 }
139
140 if (!CheckOptimality)
141 return;
142
143 // Make sure we have at least one element for the code below.
144 if (Elems.none()) {
145 EXPECT_TRUE(CR.isEmptySet());
146 return;
147 }
148
149 auto NotPreferred = [&](const ConstantRange &PossibleCR) {
150 if (!PreferenceFn(PossibleCR, CR))
151 return testing::AssertionSuccess();
152
153 testing::AssertionResult Result = testing::AssertionFailure();
154 Result << "Inputs = ";
155 for (const ConstantRange &Input : Inputs)
156 Result << Input << ", ";
157 Result << "CR = " << CR << ", BetterCR = " << PossibleCR;
158 return Result;
159 };
160
161 // Look at all pairs of adjacent elements and the slack-free ranges
162 // [Elem, PrevElem] they imply. Check that none of the ranges are strictly
163 // preferred over the computed range (they may have equal preference).
164 int FirstElem = Elems.find_first();
165 int PrevElem = FirstElem, Elem;
166 do {
167 Elem = Elems.find_next(PrevElem);
168 if (Elem < 0)
169 Elem = FirstElem; // Wrap around to first element.
170
171 ConstantRange PossibleCR =
172 ConstantRange::getNonEmpty(APInt(BitWidth, Elem),
173 APInt(BitWidth, PrevElem) + 1);
174 // We get a full range any time PrevElem and Elem are adjacent. Avoid
175 // repeated checks by skipping here, and explicitly checking below instead.
176 if (!PossibleCR.isFullSet()) {
177 EXPECT_TRUE(NotPreferred(PossibleCR));
178 }
179
180 PrevElem = Elem;
181 } while (Elem != FirstElem);
182
183 EXPECT_TRUE(NotPreferred(ConstantRange::getFull(BitWidth)));
184 }
185
186 using UnaryRangeFn = llvm::function_ref<ConstantRange(const ConstantRange &)>;
187 using UnaryIntFn = llvm::function_ref<std::optional<APInt>(const APInt &)>;
188
189 static void TestUnaryOpExhaustive(UnaryRangeFn RangeFn, UnaryIntFn IntFn,
190 PreferFn PreferenceFn = PreferSmallest) {
191 EnumerateInterestingConstantRanges([&](const ConstantRange &CR) {
192 SmallBitVector Elems(1 << CR.getBitWidth());
193 ForeachNumInConstantRange(CR, [&](const APInt &N) {
194 if (std::optional<APInt> ResultN = IntFn(N))
195 Elems.set(ResultN->getZExtValue());
196 });
197 TestRange(RangeFn(CR), Elems, PreferenceFn, {CR});
198 });
199 }
200
201 using BinaryRangeFn = llvm::function_ref<ConstantRange(const ConstantRange &,
202 const ConstantRange &)>;
203 using BinaryIntFn =
204 llvm::function_ref<std::optional<APInt>(const APInt &, const APInt &)>;
205 using BinaryCheckFn = llvm::function_ref<bool(const ConstantRange &,
206 const ConstantRange &)>;
207
208 static bool CheckAll(const ConstantRange &, const ConstantRange &) {
209 return true;
210 }
211
212 static bool CheckCorrectnessOnly(const ConstantRange &, const ConstantRange &) {
213 return false;
214 }
215
216 static bool CheckSingleElementsOnly(const ConstantRange &CR1,
217 const ConstantRange &CR2) {
218 return CR1.isSingleElement() && CR2.isSingleElement();
219 }
220
221 static bool CheckNonWrappedOnly(const ConstantRange &CR1,
222 const ConstantRange &CR2) {
223 return !CR1.isWrappedSet() && !CR2.isWrappedSet();
224 }
225
226 static bool CheckNonSignWrappedOnly(const ConstantRange &CR1,
227 const ConstantRange &CR2) {
228 return !CR1.isSignWrappedSet() && !CR2.isSignWrappedSet();
229 }
230
231 static bool CheckNonWrappedOrSignWrappedOnly(const ConstantRange &CR1,
232 const ConstantRange &CR2) {
233 return !CR1.isWrappedSet() && !CR1.isSignWrappedSet() &&
234 !CR2.isWrappedSet() && !CR2.isSignWrappedSet();
235 }
236
237 // CheckFn determines whether optimality is checked for a given range pair.
238 // Correctness is always checked.
239 static void TestBinaryOpExhaustive(BinaryRangeFn RangeFn, BinaryIntFn IntFn,
240 PreferFn PreferenceFn = PreferSmallest,
241 BinaryCheckFn CheckFn = CheckAll) {
242 EnumerateTwoInterestingConstantRanges(
243 [&](const ConstantRange &CR1, const ConstantRange &CR2) {
244 SmallBitVector Elems(1 << CR1.getBitWidth());
245 ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
246 ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
247 if (std::optional<APInt> ResultN = IntFn(N1, N2))
248 Elems.set(ResultN->getZExtValue());
249 });
250 });
251 TestRange(RangeFn(CR1, CR2), Elems, PreferenceFn, {CR1, CR2},
252 CheckFn(CR1, CR2));
253 });
254 }
255
256 ConstantRange ConstantRangeTest::Full(16, true);
257 ConstantRange ConstantRangeTest::Empty(16, false);
258 ConstantRange ConstantRangeTest::One(APInt(16, 0xa));
259 ConstantRange ConstantRangeTest::Some(APInt(16, 0xa), APInt(16, 0xaaa));
260 ConstantRange ConstantRangeTest::Wrap(APInt(16, 0xaaa), APInt(16, 0xa));
261
262 TEST_F(ConstantRangeTest, Basics) {
263 EXPECT_TRUE(Full.isFullSet());
264 EXPECT_FALSE(Full.isEmptySet());
265 EXPECT_TRUE(Full.inverse().isEmptySet());
266 EXPECT_FALSE(Full.isWrappedSet());
267 EXPECT_TRUE(Full.contains(APInt(16, 0x0)));
268 EXPECT_TRUE(Full.contains(APInt(16, 0x9)));
269 EXPECT_TRUE(Full.contains(APInt(16, 0xa)));
270 EXPECT_TRUE(Full.contains(APInt(16, 0xaa9)));
271 EXPECT_TRUE(Full.contains(APInt(16, 0xaaa)));
272
273 EXPECT_FALSE(Empty.isFullSet());
274 EXPECT_TRUE(Empty.isEmptySet());
275 EXPECT_TRUE(Empty.inverse().isFullSet());
276 EXPECT_FALSE(Empty.isWrappedSet());
277 EXPECT_FALSE(Empty.contains(APInt(16, 0x0)));
278 EXPECT_FALSE(Empty.contains(APInt(16, 0x9)));
279 EXPECT_FALSE(Empty.contains(APInt(16, 0xa)));
280 EXPECT_FALSE(Empty.contains(APInt(16, 0xaa9)));
281 EXPECT_FALSE(Empty.contains(APInt(16, 0xaaa)));
282
283 EXPECT_FALSE(One.isFullSet());
284 EXPECT_FALSE(One.isEmptySet());
285 EXPECT_FALSE(One.isWrappedSet());
286 EXPECT_FALSE(One.contains(APInt(16, 0x0)));
287 EXPECT_FALSE(One.contains(APInt(16, 0x9)));
288 EXPECT_TRUE(One.contains(APInt(16, 0xa)));
289 EXPECT_FALSE(One.contains(APInt(16, 0xaa9)));
290 EXPECT_FALSE(One.contains(APInt(16, 0xaaa)));
291 EXPECT_FALSE(One.inverse().contains(APInt(16, 0xa)));
292
293 EXPECT_FALSE(Some.isFullSet());
294 EXPECT_FALSE(Some.isEmptySet());
295 EXPECT_FALSE(Some.isWrappedSet());
296 EXPECT_FALSE(Some.contains(APInt(16, 0x0)));
297 EXPECT_FALSE(Some.contains(APInt(16, 0x9)));
298 EXPECT_TRUE(Some.contains(APInt(16, 0xa)));
299 EXPECT_TRUE(Some.contains(APInt(16, 0xaa9)));
300 EXPECT_FALSE(Some.contains(APInt(16, 0xaaa)));
301
302 EXPECT_FALSE(Wrap.isFullSet());
303 EXPECT_FALSE(Wrap.isEmptySet());
304 EXPECT_TRUE(Wrap.isWrappedSet());
305 EXPECT_TRUE(Wrap.contains(APInt(16, 0x0)));
306 EXPECT_TRUE(Wrap.contains(APInt(16, 0x9)));
307 EXPECT_FALSE(Wrap.contains(APInt(16, 0xa)));
308 EXPECT_FALSE(Wrap.contains(APInt(16, 0xaa9)));
309 EXPECT_TRUE(Wrap.contains(APInt(16, 0xaaa)));
310 }
311
312 TEST_F(ConstantRangeTest, Equality) {
313 EXPECT_EQ(Full, Full);
314 EXPECT_EQ(Empty, Empty);
315 EXPECT_EQ(One, One);
316 EXPECT_EQ(Some, Some);
317 EXPECT_EQ(Wrap, Wrap);
318 EXPECT_NE(Full, Empty);
319 EXPECT_NE(Full, One);
320 EXPECT_NE(Full, Some);
321 EXPECT_NE(Full, Wrap);
322 EXPECT_NE(Empty, One);
323 EXPECT_NE(Empty, Some);
324 EXPECT_NE(Empty, Wrap);
325 EXPECT_NE(One, Some);
326 EXPECT_NE(One, Wrap);
327 EXPECT_NE(Some, Wrap);
328 }
329
330 TEST_F(ConstantRangeTest, SingleElement) {
331 EXPECT_EQ(Full.getSingleElement(), static_cast<APInt *>(nullptr));
332 EXPECT_EQ(Empty.getSingleElement(), static_cast<APInt *>(nullptr));
333 EXPECT_EQ(Full.getSingleMissingElement(), static_cast<APInt *>(nullptr));
334 EXPECT_EQ(Empty.getSingleMissingElement(), static_cast<APInt *>(nullptr));
335
336 EXPECT_EQ(*One.getSingleElement(), APInt(16, 0xa));
337 EXPECT_EQ(Some.getSingleElement(), static_cast<APInt *>(nullptr));
338 EXPECT_EQ(Wrap.getSingleElement(), static_cast<APInt *>(nullptr));
339
340 EXPECT_EQ(One.getSingleMissingElement(), static_cast<APInt *>(nullptr));
341 EXPECT_EQ(Some.getSingleMissingElement(), static_cast<APInt *>(nullptr));
342
343 ConstantRange OneInverse = One.inverse();
344 EXPECT_EQ(*OneInverse.getSingleMissingElement(), *One.getSingleElement());
345
346 EXPECT_FALSE(Full.isSingleElement());
347 EXPECT_FALSE(Empty.isSingleElement());
348 EXPECT_TRUE(One.isSingleElement());
349 EXPECT_FALSE(Some.isSingleElement());
350 EXPECT_FALSE(Wrap.isSingleElement());
351 }
352
353 TEST_F(ConstantRangeTest, GetMinsAndMaxes) {
354 EXPECT_EQ(Full.getUnsignedMax(), APInt(16, UINT16_MAX));
355 EXPECT_EQ(One.getUnsignedMax(), APInt(16, 0xa));
356 EXPECT_EQ(Some.getUnsignedMax(), APInt(16, 0xaa9));
357 EXPECT_EQ(Wrap.getUnsignedMax(), APInt(16, UINT16_MAX));
358
359 EXPECT_EQ(Full.getUnsignedMin(), APInt(16, 0));
360 EXPECT_EQ(One.getUnsignedMin(), APInt(16, 0xa));
361 EXPECT_EQ(Some.getUnsignedMin(), APInt(16, 0xa));
362 EXPECT_EQ(Wrap.getUnsignedMin(), APInt(16, 0));
363
364 EXPECT_EQ(Full.getSignedMax(), APInt(16, INT16_MAX));
365 EXPECT_EQ(One.getSignedMax(), APInt(16, 0xa));
366 EXPECT_EQ(Some.getSignedMax(), APInt(16, 0xaa9));
367 EXPECT_EQ(Wrap.getSignedMax(), APInt(16, INT16_MAX));
368
369 EXPECT_EQ(Full.getSignedMin(), APInt(16, (uint64_t)INT16_MIN));
370 EXPECT_EQ(One.getSignedMin(), APInt(16, 0xa));
371 EXPECT_EQ(Some.getSignedMin(), APInt(16, 0xa));
372 EXPECT_EQ(Wrap.getSignedMin(), APInt(16, (uint64_t)INT16_MIN));
373
374 // Found by Klee
375 EXPECT_EQ(ConstantRange(APInt(4, 7), APInt(4, 0)).getSignedMax(),
376 APInt(4, 7));
377 }
378
379 TEST_F(ConstantRangeTest, SignWrapped) {
380 EXPECT_FALSE(Full.isSignWrappedSet());
381 EXPECT_FALSE(Empty.isSignWrappedSet());
382 EXPECT_FALSE(One.isSignWrappedSet());
383 EXPECT_FALSE(Some.isSignWrappedSet());
384 EXPECT_TRUE(Wrap.isSignWrappedSet());
385
386 EXPECT_FALSE(ConstantRange(APInt(8, 127), APInt(8, 128)).isSignWrappedSet());
387 EXPECT_TRUE(ConstantRange(APInt(8, 127), APInt(8, 129)).isSignWrappedSet());
388 EXPECT_FALSE(ConstantRange(APInt(8, 128), APInt(8, 129)).isSignWrappedSet());
389 EXPECT_TRUE(ConstantRange(APInt(8, 10), APInt(8, 9)).isSignWrappedSet());
390 EXPECT_TRUE(ConstantRange(APInt(8, 10), APInt(8, 250)).isSignWrappedSet());
391 EXPECT_FALSE(ConstantRange(APInt(8, 250), APInt(8, 10)).isSignWrappedSet());
392 EXPECT_FALSE(ConstantRange(APInt(8, 250), APInt(8, 251)).isSignWrappedSet());
393 }
394
395 TEST_F(ConstantRangeTest, UpperWrapped) {
396 // The behavior here is the same as for isWrappedSet() / isSignWrappedSet().
397 EXPECT_FALSE(Full.isUpperWrapped());
398 EXPECT_FALSE(Empty.isUpperWrapped());
399 EXPECT_FALSE(One.isUpperWrapped());
400 EXPECT_FALSE(Some.isUpperWrapped());
401 EXPECT_TRUE(Wrap.isUpperWrapped());
402 EXPECT_FALSE(Full.isUpperSignWrapped());
403 EXPECT_FALSE(Empty.isUpperSignWrapped());
404 EXPECT_FALSE(One.isUpperSignWrapped());
405 EXPECT_FALSE(Some.isUpperSignWrapped());
406 EXPECT_TRUE(Wrap.isUpperSignWrapped());
407
408 // The behavior differs if Upper is the Min/SignedMin value.
409 ConstantRange CR1(APInt(8, 42), APInt::getMinValue(8));
410 EXPECT_FALSE(CR1.isWrappedSet());
411 EXPECT_TRUE(CR1.isUpperWrapped());
412
413 ConstantRange CR2(APInt(8, 42), APInt::getSignedMinValue(8));
414 EXPECT_FALSE(CR2.isSignWrappedSet());
415 EXPECT_TRUE(CR2.isUpperSignWrapped());
416 }
417
418 TEST_F(ConstantRangeTest, Trunc) {
419 ConstantRange TFull = Full.truncate(10);
420 ConstantRange TEmpty = Empty.truncate(10);
421 ConstantRange TOne = One.truncate(10);
422 ConstantRange TSome = Some.truncate(10);
423 ConstantRange TWrap = Wrap.truncate(10);
424 EXPECT_TRUE(TFull.isFullSet());
425 EXPECT_TRUE(TEmpty.isEmptySet());
426 EXPECT_EQ(TOne, ConstantRange(One.getLower().trunc(10),
427 One.getUpper().trunc(10)));
428 EXPECT_TRUE(TSome.isFullSet());
429 EXPECT_TRUE(TWrap.isFullSet());
430
431 // trunc([2, 5), 3->2) = [2, 1)
432 ConstantRange TwoFive(APInt(3, 2), APInt(3, 5));
433 EXPECT_EQ(TwoFive.truncate(2), ConstantRange(APInt(2, 2), APInt(2, 1)));
434
435 // trunc([2, 6), 3->2) = full
436 ConstantRange TwoSix(APInt(3, 2), APInt(3, 6));
437 EXPECT_TRUE(TwoSix.truncate(2).isFullSet());
438
439 // trunc([5, 7), 3->2) = [1, 3)
440 ConstantRange FiveSeven(APInt(3, 5), APInt(3, 7));
441 EXPECT_EQ(FiveSeven.truncate(2), ConstantRange(APInt(2, 1), APInt(2, 3)));
442
443 // trunc([7, 1), 3->2) = [3, 1)
444 ConstantRange SevenOne(APInt(3, 7), APInt(3, 1));
445 EXPECT_EQ(SevenOne.truncate(2), ConstantRange(APInt(2, 3), APInt(2, 1)));
446 }
447
448 TEST_F(ConstantRangeTest, ZExt) {
449 ConstantRange ZFull = Full.zeroExtend(20);
450 ConstantRange ZEmpty = Empty.zeroExtend(20);
451 ConstantRange ZOne = One.zeroExtend(20);
452 ConstantRange ZSome = Some.zeroExtend(20);
453 ConstantRange ZWrap = Wrap.zeroExtend(20);
454 EXPECT_EQ(ZFull, ConstantRange(APInt(20, 0), APInt(20, 0x10000)));
455 EXPECT_TRUE(ZEmpty.isEmptySet());
456 EXPECT_EQ(ZOne, ConstantRange(One.getLower().zext(20),
457 One.getUpper().zext(20)));
458 EXPECT_EQ(ZSome, ConstantRange(Some.getLower().zext(20),
459 Some.getUpper().zext(20)));
460 EXPECT_EQ(ZWrap, ConstantRange(APInt(20, 0), APInt(20, 0x10000)));
461
462 // zext([5, 0), 3->7) = [5, 8)
463 ConstantRange FiveZero(APInt(3, 5), APInt(3, 0));
464 EXPECT_EQ(FiveZero.zeroExtend(7), ConstantRange(APInt(7, 5), APInt(7, 8)));
465 }
466
467 TEST_F(ConstantRangeTest, SExt) {
468 ConstantRange SFull = Full.signExtend(20);
469 ConstantRange SEmpty = Empty.signExtend(20);
470 ConstantRange SOne = One.signExtend(20);
471 ConstantRange SSome = Some.signExtend(20);
472 ConstantRange SWrap = Wrap.signExtend(20);
473 EXPECT_EQ(SFull, ConstantRange(APInt(20, (uint64_t)INT16_MIN, true),
474 APInt(20, INT16_MAX + 1, true)));
475 EXPECT_TRUE(SEmpty.isEmptySet());
476 EXPECT_EQ(SOne, ConstantRange(One.getLower().sext(20),
477 One.getUpper().sext(20)));
478 EXPECT_EQ(SSome, ConstantRange(Some.getLower().sext(20),
479 Some.getUpper().sext(20)));
480 EXPECT_EQ(SWrap, ConstantRange(APInt(20, (uint64_t)INT16_MIN, true),
481 APInt(20, INT16_MAX + 1, true)));
482
483 EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, 140)).signExtend(16),
484 ConstantRange(APInt(16, -128), APInt(16, 128)));
485
486 EXPECT_EQ(ConstantRange(APInt(16, 0x0200), APInt(16, 0x8000)).signExtend(19),
487 ConstantRange(APInt(19, 0x0200), APInt(19, 0x8000)));
488 }
489
490 TEST_F(ConstantRangeTest, IntersectWith) {
491 EXPECT_EQ(Empty.intersectWith(Full), Empty);
492 EXPECT_EQ(Empty.intersectWith(Empty), Empty);
493 EXPECT_EQ(Empty.intersectWith(One), Empty);
494 EXPECT_EQ(Empty.intersectWith(Some), Empty);
495 EXPECT_EQ(Empty.intersectWith(Wrap), Empty);
496 EXPECT_EQ(Full.intersectWith(Full), Full);
497 EXPECT_EQ(Some.intersectWith(Some), Some);
498 EXPECT_EQ(Some.intersectWith(One), One);
499 EXPECT_EQ(Full.intersectWith(One), One);
500 EXPECT_EQ(Full.intersectWith(Some), Some);
501 EXPECT_EQ(Some.intersectWith(Wrap), Empty);
502 EXPECT_EQ(One.intersectWith(Wrap), Empty);
503 EXPECT_EQ(One.intersectWith(Wrap), Wrap.intersectWith(One));
504
505 // Klee generated testcase from PR4545.
506 // The intersection of i16 [4, 2) and [6, 5) is disjoint, looking like
507 // 01..4.6789ABCDEF where the dots represent values not in the intersection.
508 ConstantRange LHS(APInt(16, 4), APInt(16, 2));
509 ConstantRange RHS(APInt(16, 6), APInt(16, 5));
510 EXPECT_TRUE(LHS.intersectWith(RHS) == LHS);
511
512 // previous bug: intersection of [min, 3) and [2, max) should be 2
513 LHS = ConstantRange(APInt(32, -2147483646), APInt(32, 3));
514 RHS = ConstantRange(APInt(32, 2), APInt(32, 2147483646));
515 EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 2)));
516
517 // [2, 0) /\ [4, 3) = [2, 0)
518 LHS = ConstantRange(APInt(32, 2), APInt(32, 0));
519 RHS = ConstantRange(APInt(32, 4), APInt(32, 3));
520 EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 2), APInt(32, 0)));
521
522 // [2, 0) /\ [4, 2) = [4, 0)
523 LHS = ConstantRange(APInt(32, 2), APInt(32, 0));
524 RHS = ConstantRange(APInt(32, 4), APInt(32, 2));
525 EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 4), APInt(32, 0)));
526
527 // [4, 2) /\ [5, 1) = [5, 1)
528 LHS = ConstantRange(APInt(32, 4), APInt(32, 2));
529 RHS = ConstantRange(APInt(32, 5), APInt(32, 1));
530 EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 5), APInt(32, 1)));
531
532 // [2, 0) /\ [7, 4) = [7, 4)
533 LHS = ConstantRange(APInt(32, 2), APInt(32, 0));
534 RHS = ConstantRange(APInt(32, 7), APInt(32, 4));
535 EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 7), APInt(32, 4)));
536
537 // [4, 2) /\ [1, 0) = [1, 0)
538 LHS = ConstantRange(APInt(32, 4), APInt(32, 2));
539 RHS = ConstantRange(APInt(32, 1), APInt(32, 0));
540 EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 4), APInt(32, 2)));
541
542 // [15, 0) /\ [7, 6) = [15, 0)
543 LHS = ConstantRange(APInt(32, 15), APInt(32, 0));
544 RHS = ConstantRange(APInt(32, 7), APInt(32, 6));
545 EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 15), APInt(32, 0)));
546 }
547
548 template <typename Fn1, typename Fn2, typename Fn3>
549 void testBinarySetOperationExhaustive(Fn1 OpFn, Fn2 ExactOpFn, Fn3 InResultFn) {
550 EnumerateTwoInterestingConstantRanges(
551 [=](const ConstantRange &CR1, const ConstantRange &CR2) {
552 unsigned Bits = CR1.getBitWidth();
553 SmallBitVector Elems(1 << Bits);
554 APInt Num(Bits, 0);
555 for (unsigned I = 0, Limit = 1 << Bits; I < Limit; ++I, ++Num)
556 if (InResultFn(CR1, CR2, Num))
557 Elems.set(Num.getZExtValue());
558
559 ConstantRange SmallestCR = OpFn(CR1, CR2, ConstantRange::Smallest);
560 TestRange(SmallestCR, Elems, PreferSmallest, {CR1, CR2});
561
562 ConstantRange UnsignedCR = OpFn(CR1, CR2, ConstantRange::Unsigned);
563 TestRange(UnsignedCR, Elems, PreferSmallestNonFullUnsigned, {CR1, CR2});
564
565 ConstantRange SignedCR = OpFn(CR1, CR2, ConstantRange::Signed);
566 TestRange(SignedCR, Elems, PreferSmallestNonFullSigned, {CR1, CR2});
567
568 std::optional<ConstantRange> ExactCR = ExactOpFn(CR1, CR2);
569 if (SmallestCR.isSizeLargerThan(Elems.count())) {
570 EXPECT_TRUE(!ExactCR);
571 } else {
572 EXPECT_EQ(SmallestCR, *ExactCR);
573 }
574 });
575 }
576
577 TEST_F(ConstantRangeTest, IntersectWithExhaustive) {
578 testBinarySetOperationExhaustive(
579 [](const ConstantRange &CR1, const ConstantRange &CR2,
580 ConstantRange::PreferredRangeType Type) {
581 return CR1.intersectWith(CR2, Type);
582 },
583 [](const ConstantRange &CR1, const ConstantRange &CR2) {
584 return CR1.exactIntersectWith(CR2);
585 },
586 [](const ConstantRange &CR1, const ConstantRange &CR2, const APInt &N) {
587 return CR1.contains(N) && CR2.contains(N);
588 });
589 }
590
591 TEST_F(ConstantRangeTest, UnionWithExhaustive) {
592 testBinarySetOperationExhaustive(
593 [](const ConstantRange &CR1, const ConstantRange &CR2,
594 ConstantRange::PreferredRangeType Type) {
595 return CR1.unionWith(CR2, Type);
596 },
597 [](const ConstantRange &CR1, const ConstantRange &CR2) {
598 return CR1.exactUnionWith(CR2);
599 },
600 [](const ConstantRange &CR1, const ConstantRange &CR2, const APInt &N) {
601 return CR1.contains(N) || CR2.contains(N);
602 });
603 }
604
605 TEST_F(ConstantRangeTest, UnionWith) {
606 EXPECT_EQ(Wrap.unionWith(One),
607 ConstantRange(APInt(16, 0xaaa), APInt(16, 0xb)));
608 EXPECT_EQ(One.unionWith(Wrap), Wrap.unionWith(One));
609 EXPECT_EQ(Empty.unionWith(Empty), Empty);
610 EXPECT_EQ(Full.unionWith(Full), Full);
611 EXPECT_EQ(Some.unionWith(Wrap), Full);
612
613 // PR4545
614 EXPECT_EQ(ConstantRange(APInt(16, 14), APInt(16, 1)).unionWith(
615 ConstantRange(APInt(16, 0), APInt(16, 8))),
616 ConstantRange(APInt(16, 14), APInt(16, 8)));
617 EXPECT_EQ(ConstantRange(APInt(16, 6), APInt(16, 4)).unionWith(
618 ConstantRange(APInt(16, 4), APInt(16, 0))),
619 ConstantRange::getFull(16));
620 EXPECT_EQ(ConstantRange(APInt(16, 1), APInt(16, 0)).unionWith(
621 ConstantRange(APInt(16, 2), APInt(16, 1))),
622 ConstantRange::getFull(16));
623 }
624
625 TEST_F(ConstantRangeTest, SetDifference) {
626 EXPECT_EQ(Full.difference(Empty), Full);
627 EXPECT_EQ(Full.difference(Full), Empty);
628 EXPECT_EQ(Empty.difference(Empty), Empty);
629 EXPECT_EQ(Empty.difference(Full), Empty);
630
631 ConstantRange A(APInt(16, 3), APInt(16, 7));
632 ConstantRange B(APInt(16, 5), APInt(16, 9));
633 ConstantRange C(APInt(16, 3), APInt(16, 5));
634 ConstantRange D(APInt(16, 7), APInt(16, 9));
635 ConstantRange E(APInt(16, 5), APInt(16, 4));
636 ConstantRange F(APInt(16, 7), APInt(16, 3));
637 EXPECT_EQ(A.difference(B), C);
638 EXPECT_EQ(B.difference(A), D);
639 EXPECT_EQ(E.difference(A), F);
640 }
641
642 TEST_F(ConstantRangeTest, getActiveBits) {
643 EnumerateInterestingConstantRanges([&](const ConstantRange &CR) {
644 unsigned Exact = 0;
645 ForeachNumInConstantRange(CR, [&](const APInt &N) {
646 Exact = std::max(Exact, N.getActiveBits());
647 });
648
649 unsigned ResultCR = CR.getActiveBits();
650 EXPECT_EQ(Exact, ResultCR);
651 });
652 }
653 TEST_F(ConstantRangeTest, losslessUnsignedTruncationZeroext) {
654 EnumerateInterestingConstantRanges([&](const ConstantRange &CR) {
655 unsigned Bits = CR.getBitWidth();
656 unsigned MinBitWidth = CR.getActiveBits();
657 if (MinBitWidth == 0) {
658 EXPECT_TRUE(CR.isEmptySet() ||
659 (CR.isSingleElement() && CR.getSingleElement()->isZero()));
660 return;
661 }
662 if (MinBitWidth == Bits)
663 return;
664 EXPECT_EQ(CR, CR.truncate(MinBitWidth).zeroExtend(Bits));
665 });
666 }
667
668 TEST_F(ConstantRangeTest, getMinSignedBits) {
669 EnumerateInterestingConstantRanges([&](const ConstantRange &CR) {
670 unsigned Exact = 0;
671 ForeachNumInConstantRange(CR, [&](const APInt &N) {
672 Exact = std::max(Exact, N.getSignificantBits());
673 });
674
675 unsigned ResultCR = CR.getMinSignedBits();
676 EXPECT_EQ(Exact, ResultCR);
677 });
678 }
679 TEST_F(ConstantRangeTest, losslessSignedTruncationSignext) {
680 EnumerateInterestingConstantRanges([&](const ConstantRange &CR) {
681 unsigned Bits = CR.getBitWidth();
682 unsigned MinBitWidth = CR.getMinSignedBits();
683 if (MinBitWidth == 0) {
684 EXPECT_TRUE(CR.isEmptySet());
685 return;
686 }
687 if (MinBitWidth == Bits)
688 return;
689 EXPECT_EQ(CR, CR.truncate(MinBitWidth).signExtend(Bits));
690 });
691 }
692
693 TEST_F(ConstantRangeTest, SubtractAPInt) {
694 EXPECT_EQ(Full.subtract(APInt(16, 4)), Full);
695 EXPECT_EQ(Empty.subtract(APInt(16, 4)), Empty);
696 EXPECT_EQ(Some.subtract(APInt(16, 4)),
697 ConstantRange(APInt(16, 0x6), APInt(16, 0xaa6)));
698 EXPECT_EQ(Wrap.subtract(APInt(16, 4)),
699 ConstantRange(APInt(16, 0xaa6), APInt(16, 0x6)));
700 EXPECT_EQ(One.subtract(APInt(16, 4)),
701 ConstantRange(APInt(16, 0x6)));
702 }
703
704 TEST_F(ConstantRangeTest, Add) {
705 EXPECT_EQ(Full.add(APInt(16, 4)), Full);
706 EXPECT_EQ(Full.add(Full), Full);
707 EXPECT_EQ(Full.add(Empty), Empty);
708 EXPECT_EQ(Full.add(One), Full);
709 EXPECT_EQ(Full.add(Some), Full);
710 EXPECT_EQ(Full.add(Wrap), Full);
711 EXPECT_EQ(Empty.add(Empty), Empty);
712 EXPECT_EQ(Empty.add(One), Empty);
713 EXPECT_EQ(Empty.add(Some), Empty);
714 EXPECT_EQ(Empty.add(Wrap), Empty);
715 EXPECT_EQ(Empty.add(APInt(16, 4)), Empty);
716 EXPECT_EQ(Some.add(APInt(16, 4)),
717 ConstantRange(APInt(16, 0xe), APInt(16, 0xaae)));
718 EXPECT_EQ(Wrap.add(APInt(16, 4)),
719 ConstantRange(APInt(16, 0xaae), APInt(16, 0xe)));
720 EXPECT_EQ(One.add(APInt(16, 4)),
721 ConstantRange(APInt(16, 0xe)));
722
723 TestBinaryOpExhaustive(
724 [](const ConstantRange &CR1, const ConstantRange &CR2) {
725 return CR1.add(CR2);
726 },
727 [](const APInt &N1, const APInt &N2) {
728 return N1 + N2;
729 });
730 }
731
732 TEST_F(ConstantRangeTest, AddWithNoWrap) {
733 typedef OverflowingBinaryOperator OBO;
734 EXPECT_EQ(Empty.addWithNoWrap(Some, OBO::NoSignedWrap), Empty);
735 EXPECT_EQ(Some.addWithNoWrap(Empty, OBO::NoSignedWrap), Empty);
736 EXPECT_EQ(Full.addWithNoWrap(Full, OBO::NoSignedWrap), Full);
737 EXPECT_NE(Full.addWithNoWrap(Some, OBO::NoSignedWrap), Full);
738 EXPECT_NE(Some.addWithNoWrap(Full, OBO::NoSignedWrap), Full);
739 EXPECT_EQ(Full.addWithNoWrap(ConstantRange(APInt(16, 1), APInt(16, 2)),
740 OBO::NoSignedWrap),
741 ConstantRange(APInt(16, INT16_MIN + 1), APInt(16, INT16_MIN)));
742 EXPECT_EQ(ConstantRange(APInt(16, 1), APInt(16, 2))
743 .addWithNoWrap(Full, OBO::NoSignedWrap),
744 ConstantRange(APInt(16, INT16_MIN + 1), APInt(16, INT16_MIN)));
745 EXPECT_EQ(Full.addWithNoWrap(ConstantRange(APInt(16, -1), APInt(16, 0)),
746 OBO::NoSignedWrap),
747 ConstantRange(APInt(16, INT16_MIN), APInt(16, INT16_MAX)));
748 EXPECT_EQ(ConstantRange(APInt(8, 100), APInt(8, 120))
749 .addWithNoWrap(ConstantRange(APInt(8, 120), APInt(8, 123)),
750 OBO::NoSignedWrap),
751 ConstantRange(8, false));
752 EXPECT_EQ(ConstantRange(APInt(8, -120), APInt(8, -100))
753 .addWithNoWrap(ConstantRange(APInt(8, -110), APInt(8, -100)),
754 OBO::NoSignedWrap),
755 ConstantRange(8, false));
756 EXPECT_EQ(ConstantRange(APInt(8, 0), APInt(8, 101))
757 .addWithNoWrap(ConstantRange(APInt(8, -128), APInt(8, 28)),
758 OBO::NoSignedWrap),
759 ConstantRange(8, true));
760 EXPECT_EQ(ConstantRange(APInt(8, 0), APInt(8, 101))
761 .addWithNoWrap(ConstantRange(APInt(8, -120), APInt(8, 29)),
762 OBO::NoSignedWrap),
763 ConstantRange(APInt(8, -120), APInt(8, -128)));
764 EXPECT_EQ(ConstantRange(APInt(8, -50), APInt(8, 50))
765 .addWithNoWrap(ConstantRange(APInt(8, 10), APInt(8, 20)),
766 OBO::NoSignedWrap),
767 ConstantRange(APInt(8, -40), APInt(8, 69)));
768 EXPECT_EQ(ConstantRange(APInt(8, 10), APInt(8, 20))
769 .addWithNoWrap(ConstantRange(APInt(8, -50), APInt(8, 50)),
770 OBO::NoSignedWrap),
771 ConstantRange(APInt(8, -40), APInt(8, 69)));
772 EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, -10))
773 .addWithNoWrap(ConstantRange(APInt(8, 5), APInt(8, 20)),
774 OBO::NoSignedWrap),
775 ConstantRange(APInt(8, 125), APInt(8, 9)));
776 EXPECT_EQ(ConstantRange(APInt(8, 5), APInt(8, 20))
777 .addWithNoWrap(ConstantRange(APInt(8, 120), APInt(8, -10)),
778 OBO::NoSignedWrap),
779 ConstantRange(APInt(8, 125), APInt(8, 9)));
780
781 TestBinaryOpExhaustive(
782 [](const ConstantRange &CR1, const ConstantRange &CR2) {
783 return CR1.addWithNoWrap(CR2, OBO::NoSignedWrap);
784 },
785 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
786 bool IsOverflow;
787 APInt Res = N1.sadd_ov(N2, IsOverflow);
788 if (IsOverflow)
789 return std::nullopt;
790 return Res;
791 },
792 PreferSmallest, CheckNonSignWrappedOnly);
793
794 EXPECT_EQ(Empty.addWithNoWrap(Some, OBO::NoUnsignedWrap), Empty);
795 EXPECT_EQ(Some.addWithNoWrap(Empty, OBO::NoUnsignedWrap), Empty);
796 EXPECT_EQ(Full.addWithNoWrap(Full, OBO::NoUnsignedWrap), Full);
797 EXPECT_NE(Full.addWithNoWrap(Some, OBO::NoUnsignedWrap), Full);
798 EXPECT_NE(Some.addWithNoWrap(Full, OBO::NoUnsignedWrap), Full);
799 EXPECT_EQ(Full.addWithNoWrap(ConstantRange(APInt(16, 1), APInt(16, 2)),
800 OBO::NoUnsignedWrap),
801 ConstantRange(APInt(16, 1), APInt(16, 0)));
802 EXPECT_EQ(ConstantRange(APInt(16, 1), APInt(16, 2))
803 .addWithNoWrap(Full, OBO::NoUnsignedWrap),
804 ConstantRange(APInt(16, 1), APInt(16, 0)));
805 EXPECT_EQ(ConstantRange(APInt(8, 200), APInt(8, 220))
806 .addWithNoWrap(ConstantRange(APInt(8, 100), APInt(8, 123)),
807 OBO::NoUnsignedWrap),
808 ConstantRange(8, false));
809 EXPECT_EQ(ConstantRange(APInt(8, 0), APInt(8, 101))
810 .addWithNoWrap(ConstantRange(APInt(8, 0), APInt(8, 156)),
811 OBO::NoUnsignedWrap),
812 ConstantRange(8, true));
813 EXPECT_EQ(ConstantRange(APInt(8, 0), APInt(8, 101))
814 .addWithNoWrap(ConstantRange(APInt(8, 10), APInt(8, 29)),
815 OBO::NoUnsignedWrap),
816 ConstantRange(APInt(8, 10), APInt(8, 129)));
817 EXPECT_EQ(ConstantRange(APInt(8, 20), APInt(8, 10))
818 .addWithNoWrap(ConstantRange(APInt(8, 50), APInt(8, 200)),
819 OBO::NoUnsignedWrap),
820 ConstantRange(APInt(8, 50), APInt(8, 0)));
821 EXPECT_EQ(ConstantRange(APInt(8, 10), APInt(8, 20))
822 .addWithNoWrap(ConstantRange(APInt(8, 50), APInt(8, 200)),
823 OBO::NoUnsignedWrap),
824 ConstantRange(APInt(8, 60), APInt(8, -37)));
825 EXPECT_EQ(ConstantRange(APInt(8, 20), APInt(8, -30))
826 .addWithNoWrap(ConstantRange(APInt(8, 5), APInt(8, 20)),
827 OBO::NoUnsignedWrap),
828 ConstantRange(APInt(8, 25), APInt(8, -11)));
829 EXPECT_EQ(ConstantRange(APInt(8, 5), APInt(8, 20))
830 .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, -30)),
831 OBO::NoUnsignedWrap),
832 ConstantRange(APInt(8, 25), APInt(8, -11)));
833
834 TestBinaryOpExhaustive(
835 [](const ConstantRange &CR1, const ConstantRange &CR2) {
836 return CR1.addWithNoWrap(CR2, OBO::NoUnsignedWrap);
837 },
838 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
839 bool IsOverflow;
840 APInt Res = N1.uadd_ov(N2, IsOverflow);
841 if (IsOverflow)
842 return std::nullopt;
843 return Res;
844 },
845 PreferSmallest, CheckNonWrappedOnly);
846
847 EXPECT_EQ(ConstantRange(APInt(8, 50), APInt(8, 100))
848 .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 70)),
849 OBO::NoSignedWrap),
850 ConstantRange(APInt(8, 70), APInt(8, -128)));
851 EXPECT_EQ(ConstantRange(APInt(8, 50), APInt(8, 100))
852 .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 70)),
853 OBO::NoUnsignedWrap),
854 ConstantRange(APInt(8, 70), APInt(8, 169)));
855 EXPECT_EQ(ConstantRange(APInt(8, 50), APInt(8, 100))
856 .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 70)),
857 OBO::NoUnsignedWrap | OBO::NoSignedWrap),
858 ConstantRange(APInt(8, 70), APInt(8, -128)));
859
860 EXPECT_EQ(ConstantRange(APInt(8, -100), APInt(8, -50))
861 .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 30)),
862 OBO::NoSignedWrap),
863 ConstantRange(APInt(8, -80), APInt(8, -21)));
864 EXPECT_EQ(ConstantRange(APInt(8, -100), APInt(8, -50))
865 .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 30)),
866 OBO::NoUnsignedWrap),
867 ConstantRange(APInt(8, 176), APInt(8, 235)));
868 EXPECT_EQ(ConstantRange(APInt(8, -100), APInt(8, -50))
869 .addWithNoWrap(ConstantRange(APInt(8, 20), APInt(8, 30)),
870 OBO::NoUnsignedWrap | OBO::NoSignedWrap),
871 ConstantRange(APInt(8, 176), APInt(8, 235)));
872
873 TestBinaryOpExhaustive(
874 [](const ConstantRange &CR1, const ConstantRange &CR2) {
875 return CR1.addWithNoWrap(CR2, OBO::NoUnsignedWrap | OBO::NoSignedWrap);
876 },
877 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
878 bool IsOverflow1, IsOverflow2;
879 APInt Res1 = N1.uadd_ov(N2, IsOverflow1);
880 APInt Res2 = N1.sadd_ov(N2, IsOverflow2);
881 if (IsOverflow1 || IsOverflow2)
882 return std::nullopt;
883 assert(Res1 == Res2 && "Addition results differ?");
884 return Res1;
885 },
886 PreferSmallest, CheckNonWrappedOrSignWrappedOnly);
887 }
888
889 TEST_F(ConstantRangeTest, Sub) {
890 EXPECT_EQ(Full.sub(APInt(16, 4)), Full);
891 EXPECT_EQ(Full.sub(Full), Full);
892 EXPECT_EQ(Full.sub(Empty), Empty);
893 EXPECT_EQ(Full.sub(One), Full);
894 EXPECT_EQ(Full.sub(Some), Full);
895 EXPECT_EQ(Full.sub(Wrap), Full);
896 EXPECT_EQ(Empty.sub(Empty), Empty);
897 EXPECT_EQ(Empty.sub(One), Empty);
898 EXPECT_EQ(Empty.sub(Some), Empty);
899 EXPECT_EQ(Empty.sub(Wrap), Empty);
900 EXPECT_EQ(Empty.sub(APInt(16, 4)), Empty);
901 EXPECT_EQ(Some.sub(APInt(16, 4)),
902 ConstantRange(APInt(16, 0x6), APInt(16, 0xaa6)));
903 EXPECT_EQ(Some.sub(Some),
904 ConstantRange(APInt(16, 0xf561), APInt(16, 0xaa0)));
905 EXPECT_EQ(Wrap.sub(APInt(16, 4)),
906 ConstantRange(APInt(16, 0xaa6), APInt(16, 0x6)));
907 EXPECT_EQ(One.sub(APInt(16, 4)),
908 ConstantRange(APInt(16, 0x6)));
909
910 TestBinaryOpExhaustive(
911 [](const ConstantRange &CR1, const ConstantRange &CR2) {
912 return CR1.sub(CR2);
913 },
914 [](const APInt &N1, const APInt &N2) {
915 return N1 - N2;
916 });
917 }
918
919 TEST_F(ConstantRangeTest, SubWithNoWrap) {
920 typedef OverflowingBinaryOperator OBO;
921 TestBinaryOpExhaustive(
922 [](const ConstantRange &CR1, const ConstantRange &CR2) {
923 return CR1.subWithNoWrap(CR2, OBO::NoSignedWrap);
924 },
925 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
926 bool IsOverflow;
927 APInt Res = N1.ssub_ov(N2, IsOverflow);
928 if (IsOverflow)
929 return std::nullopt;
930 return Res;
931 },
932 PreferSmallest, CheckNonSignWrappedOnly);
933 TestBinaryOpExhaustive(
934 [](const ConstantRange &CR1, const ConstantRange &CR2) {
935 return CR1.subWithNoWrap(CR2, OBO::NoUnsignedWrap);
936 },
937 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
938 bool IsOverflow;
939 APInt Res = N1.usub_ov(N2, IsOverflow);
940 if (IsOverflow)
941 return std::nullopt;
942 return Res;
943 },
944 PreferSmallest, CheckNonWrappedOnly);
945 TestBinaryOpExhaustive(
946 [](const ConstantRange &CR1, const ConstantRange &CR2) {
947 return CR1.subWithNoWrap(CR2, OBO::NoUnsignedWrap | OBO::NoSignedWrap);
948 },
949 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
950 bool IsOverflow1, IsOverflow2;
951 APInt Res1 = N1.usub_ov(N2, IsOverflow1);
952 APInt Res2 = N1.ssub_ov(N2, IsOverflow2);
953 if (IsOverflow1 || IsOverflow2)
954 return std::nullopt;
955 assert(Res1 == Res2 && "Subtraction results differ?");
956 return Res1;
957 },
958 PreferSmallest, CheckNonWrappedOrSignWrappedOnly);
959 }
960
961 TEST_F(ConstantRangeTest, Multiply) {
962 EXPECT_EQ(Full.multiply(Full), Full);
963 EXPECT_EQ(Full.multiply(Empty), Empty);
964 EXPECT_EQ(Full.multiply(One), Full);
965 EXPECT_EQ(Full.multiply(Some), Full);
966 EXPECT_EQ(Full.multiply(Wrap), Full);
967 EXPECT_EQ(Empty.multiply(Empty), Empty);
968 EXPECT_EQ(Empty.multiply(One), Empty);
969 EXPECT_EQ(Empty.multiply(Some), Empty);
970 EXPECT_EQ(Empty.multiply(Wrap), Empty);
971 EXPECT_EQ(One.multiply(One), ConstantRange(APInt(16, 0xa*0xa),
972 APInt(16, 0xa*0xa + 1)));
973 EXPECT_EQ(One.multiply(Some), ConstantRange(APInt(16, 0xa*0xa),
974 APInt(16, 0xa*0xaa9 + 1)));
975 EXPECT_EQ(One.multiply(Wrap), Full);
976 EXPECT_EQ(Some.multiply(Some), Full);
977 EXPECT_EQ(Some.multiply(Wrap), Full);
978 EXPECT_EQ(Wrap.multiply(Wrap), Full);
979
980 ConstantRange Zero(APInt(16, 0));
981 EXPECT_EQ(Zero.multiply(Full), Zero);
982 EXPECT_EQ(Zero.multiply(Some), Zero);
983 EXPECT_EQ(Zero.multiply(Wrap), Zero);
984 EXPECT_EQ(Full.multiply(Zero), Zero);
985 EXPECT_EQ(Some.multiply(Zero), Zero);
986 EXPECT_EQ(Wrap.multiply(Zero), Zero);
987
988 // http://llvm.org/PR4545
989 EXPECT_EQ(ConstantRange(APInt(4, 1), APInt(4, 6)).multiply(
990 ConstantRange(APInt(4, 6), APInt(4, 2))),
991 ConstantRange(4, /*isFullSet=*/true));
992
993 EXPECT_EQ(ConstantRange(APInt(8, 254), APInt(8, 0)).multiply(
994 ConstantRange(APInt(8, 252), APInt(8, 4))),
995 ConstantRange(APInt(8, 250), APInt(8, 9)));
996 EXPECT_EQ(ConstantRange(APInt(8, 254), APInt(8, 255)).multiply(
997 ConstantRange(APInt(8, 2), APInt(8, 4))),
998 ConstantRange(APInt(8, 250), APInt(8, 253)));
999
1000 // TODO: This should be return [-2, 0]
1001 EXPECT_EQ(ConstantRange(APInt(8, -2)).multiply(
1002 ConstantRange(APInt(8, 0), APInt(8, 2))),
1003 ConstantRange(APInt(8, -2), APInt(8, 1)));
1004
1005 // Multiplication by -1 should give precise results.
1006 EXPECT_EQ(ConstantRange(APInt(8, 3), APInt(8, -11))
1007 .multiply(ConstantRange(APInt(8, -1))),
1008 ConstantRange(APInt(8, 12), APInt(8, -2)));
1009 EXPECT_EQ(ConstantRange(APInt(8, -1))
1010 .multiply(ConstantRange(APInt(8, 3), APInt(8, -11))),
1011 ConstantRange(APInt(8, 12), APInt(8, -2)));
1012
1013 TestBinaryOpExhaustive(
1014 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1015 return CR1.multiply(CR2);
1016 },
1017 [](const APInt &N1, const APInt &N2) {
1018 return N1 * N2;
1019 },
1020 PreferSmallest,
1021 [](const ConstantRange &, const ConstantRange &) {
1022 return false; // Check correctness only.
1023 });
1024 }
1025
1026 TEST_F(ConstantRangeTest, MultiplyWithNoWrap) {
1027 using OBO = OverflowingBinaryOperator;
1028
1029 EXPECT_EQ(Empty.multiplyWithNoWrap(Some, OBO::NoUnsignedWrap), Empty);
1030 EXPECT_EQ(Some.multiplyWithNoWrap(Empty, OBO::NoUnsignedWrap), Empty);
1031 EXPECT_EQ(Full.multiplyWithNoWrap(Full, OBO::NoUnsignedWrap), Full);
1032 EXPECT_EQ(Full.multiplyWithNoWrap(Some, OBO::NoUnsignedWrap), Full);
1033 EXPECT_EQ(Some.multiplyWithNoWrap(Full, OBO::NoUnsignedWrap), Full);
1034 EXPECT_EQ(ConstantRange(APInt(4, 0), APInt(4, 2))
1035 .multiplyWithNoWrap(ConstantRange(APInt(4, 2), APInt(4, 0)),
1036 OBO::NoUnsignedWrap),
1037 ConstantRange::getFull(4));
1038 EXPECT_EQ(ConstantRange(APInt(4, 1), APInt(4, 5))
1039 .multiplyWithNoWrap(ConstantRange(APInt(4, 1), APInt(4, 5)),
1040 OBO::NoUnsignedWrap),
1041 ConstantRange(APInt(4, 1), APInt(4, 0)));
1042 EXPECT_EQ(ConstantRange(APInt(8, 254), APInt(8, 0))
1043 .multiplyWithNoWrap(ConstantRange(APInt(8, 252), APInt(8, 4)),
1044 OBO::NoUnsignedWrap),
1045 ConstantRange(APInt(8, 250), APInt(8, 9)));
1046 EXPECT_EQ(ConstantRange(APInt(8, 254), APInt(8, 255))
1047 .multiplyWithNoWrap(ConstantRange(APInt(8, 2), APInt(8, 4)),
1048 OBO::NoUnsignedWrap),
1049 ConstantRange::getEmpty(8));
1050
1051 EXPECT_EQ(Empty.multiplyWithNoWrap(Some, OBO::NoSignedWrap), Empty);
1052 EXPECT_EQ(Some.multiplyWithNoWrap(Empty, OBO::NoSignedWrap), Empty);
1053 EXPECT_EQ(Full.multiplyWithNoWrap(Full, OBO::NoSignedWrap), Full);
1054 EXPECT_EQ(Full.multiplyWithNoWrap(Some, OBO::NoSignedWrap), Full);
1055 EXPECT_EQ(Some.multiplyWithNoWrap(Full, OBO::NoSignedWrap), Full);
1056 EXPECT_EQ(
1057 ConstantRange(APInt(4, 0), APInt(4, 4))
1058 .multiplyWithNoWrap(ConstantRange(APInt(4, -5, true), APInt(4, 4)),
1059 OBO::NoSignedWrap),
1060 ConstantRange::getFull(4));
1061 EXPECT_EQ(ConstantRange(APInt(4, 0), APInt(4, 3))
1062 .multiplyWithNoWrap(ConstantRange(APInt(4, 0), APInt(4, 5)),
1063 OBO::NoSignedWrap),
1064 ConstantRange(APInt(4, 0), APInt(4, -8, true)));
1065 EXPECT_EQ(ConstantRange(APInt(8, 3), APInt(8, -11, true))
1066 .multiplyWithNoWrap(ConstantRange(APInt(8, -1, true)),
1067 OBO::NoSignedWrap),
1068 ConstantRange(APInt(8, 12), APInt(8, -2, true)));
1069 EXPECT_EQ(ConstantRange(APInt(8, 254), APInt(8, 255))
1070 .multiplyWithNoWrap(ConstantRange(APInt(8, 100), APInt(8, 121)),
1071 OBO::NoSignedWrap),
1072 ConstantRange::getEmpty(8));
1073
1074 TestBinaryOpExhaustive(
1075 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1076 return CR1.multiplyWithNoWrap(CR2, OBO::NoUnsignedWrap);
1077 },
1078 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
1079 bool IsOverflow;
1080 APInt Res = N1.umul_ov(N2, IsOverflow);
1081 if (IsOverflow)
1082 return std::nullopt;
1083 return Res;
1084 },
1085 PreferSmallest, CheckCorrectnessOnly);
1086 TestBinaryOpExhaustive(
1087 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1088 return CR1.multiplyWithNoWrap(CR2, OBO::NoSignedWrap);
1089 },
1090 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
1091 bool IsOverflow;
1092 APInt Res = N1.smul_ov(N2, IsOverflow);
1093 if (IsOverflow)
1094 return std::nullopt;
1095 return Res;
1096 },
1097 PreferSmallest, CheckCorrectnessOnly);
1098 TestBinaryOpExhaustive(
1099 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1100 return CR1.multiplyWithNoWrap(CR2,
1101 OBO::NoUnsignedWrap | OBO::NoSignedWrap);
1102 },
1103 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
1104 bool IsOverflow1, IsOverflow2;
1105 APInt Res1 = N1.umul_ov(N2, IsOverflow1);
1106 APInt Res2 = N1.smul_ov(N2, IsOverflow2);
1107 if (IsOverflow1 || IsOverflow2)
1108 return std::nullopt;
1109 assert(Res1 == Res2 && "Multiplication results differ?");
1110 return Res1;
1111 },
1112 PreferSmallest, CheckCorrectnessOnly);
1113 }
1114
1115 TEST_F(ConstantRangeTest, smul_fast) {
1116 TestBinaryOpExhaustive(
1117 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1118 return CR1.smul_fast(CR2);
1119 },
1120 [](const APInt &N1, const APInt &N2) { return N1 * N2; }, PreferSmallest,
1121 CheckCorrectnessOnly);
1122 }
1123
1124 TEST_F(ConstantRangeTest, UMax) {
1125 EXPECT_EQ(Full.umax(Full), Full);
1126 EXPECT_EQ(Full.umax(Empty), Empty);
1127 EXPECT_EQ(Full.umax(Some), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
1128 EXPECT_EQ(Full.umax(Wrap), Full);
1129 EXPECT_EQ(Full.umax(Some), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
1130 EXPECT_EQ(Empty.umax(Empty), Empty);
1131 EXPECT_EQ(Empty.umax(Some), Empty);
1132 EXPECT_EQ(Empty.umax(Wrap), Empty);
1133 EXPECT_EQ(Empty.umax(One), Empty);
1134 EXPECT_EQ(Some.umax(Some), Some);
1135 EXPECT_EQ(Some.umax(Wrap), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
1136 EXPECT_EQ(Some.umax(One), Some);
1137 EXPECT_EQ(Wrap.umax(Wrap), Wrap);
1138 EXPECT_EQ(Wrap.umax(One), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
1139 EXPECT_EQ(One.umax(One), One);
1140
1141 TestBinaryOpExhaustive(
1142 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1143 return CR1.umax(CR2);
1144 },
1145 [](const APInt &N1, const APInt &N2) {
1146 return APIntOps::umax(N1, N2);
1147 },
1148 PreferSmallestNonFullUnsigned);
1149 }
1150
1151 TEST_F(ConstantRangeTest, SMax) {
1152 EXPECT_EQ(Full.smax(Full), Full);
1153 EXPECT_EQ(Full.smax(Empty), Empty);
1154 EXPECT_EQ(Full.smax(Some), ConstantRange(APInt(16, 0xa),
1155 APInt::getSignedMinValue(16)));
1156 EXPECT_EQ(Full.smax(Wrap), Full);
1157 EXPECT_EQ(Full.smax(One), ConstantRange(APInt(16, 0xa),
1158 APInt::getSignedMinValue(16)));
1159 EXPECT_EQ(Empty.smax(Empty), Empty);
1160 EXPECT_EQ(Empty.smax(Some), Empty);
1161 EXPECT_EQ(Empty.smax(Wrap), Empty);
1162 EXPECT_EQ(Empty.smax(One), Empty);
1163 EXPECT_EQ(Some.smax(Some), Some);
1164 EXPECT_EQ(Some.smax(Wrap), ConstantRange(APInt(16, 0xa),
1165 APInt(16, (uint64_t)INT16_MIN)));
1166 EXPECT_EQ(Some.smax(One), Some);
1167 EXPECT_EQ(Wrap.smax(One), ConstantRange(APInt(16, 0xa),
1168 APInt(16, (uint64_t)INT16_MIN)));
1169 EXPECT_EQ(One.smax(One), One);
1170
1171 TestBinaryOpExhaustive(
1172 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1173 return CR1.smax(CR2);
1174 },
1175 [](const APInt &N1, const APInt &N2) {
1176 return APIntOps::smax(N1, N2);
1177 },
1178 PreferSmallestNonFullSigned);
1179 }
1180
1181 TEST_F(ConstantRangeTest, UMin) {
1182 EXPECT_EQ(Full.umin(Full), Full);
1183 EXPECT_EQ(Full.umin(Empty), Empty);
1184 EXPECT_EQ(Full.umin(Some), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
1185 EXPECT_EQ(Full.umin(Wrap), Full);
1186 EXPECT_EQ(Empty.umin(Empty), Empty);
1187 EXPECT_EQ(Empty.umin(Some), Empty);
1188 EXPECT_EQ(Empty.umin(Wrap), Empty);
1189 EXPECT_EQ(Empty.umin(One), Empty);
1190 EXPECT_EQ(Some.umin(Some), Some);
1191 EXPECT_EQ(Some.umin(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
1192 EXPECT_EQ(Some.umin(One), One);
1193 EXPECT_EQ(Wrap.umin(Wrap), Wrap);
1194 EXPECT_EQ(Wrap.umin(One), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
1195 EXPECT_EQ(One.umin(One), One);
1196
1197 TestBinaryOpExhaustive(
1198 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1199 return CR1.umin(CR2);
1200 },
1201 [](const APInt &N1, const APInt &N2) {
1202 return APIntOps::umin(N1, N2);
1203 },
1204 PreferSmallestNonFullUnsigned);
1205 }
1206
1207 TEST_F(ConstantRangeTest, SMin) {
1208 EXPECT_EQ(Full.smin(Full), Full);
1209 EXPECT_EQ(Full.smin(Empty), Empty);
1210 EXPECT_EQ(Full.smin(Some), ConstantRange(APInt(16, (uint64_t)INT16_MIN),
1211 APInt(16, 0xaaa)));
1212 EXPECT_EQ(Full.smin(Wrap), Full);
1213 EXPECT_EQ(Empty.smin(Empty), Empty);
1214 EXPECT_EQ(Empty.smin(Some), Empty);
1215 EXPECT_EQ(Empty.smin(Wrap), Empty);
1216 EXPECT_EQ(Empty.smin(One), Empty);
1217 EXPECT_EQ(Some.smin(Some), Some);
1218 EXPECT_EQ(Some.smin(Wrap), ConstantRange(APInt(16, (uint64_t)INT16_MIN),
1219 APInt(16, 0xaaa)));
1220 EXPECT_EQ(Some.smin(One), One);
1221 EXPECT_EQ(Wrap.smin(Wrap), Wrap);
1222 EXPECT_EQ(Wrap.smin(One), ConstantRange(APInt(16, (uint64_t)INT16_MIN),
1223 APInt(16, 0xb)));
1224 EXPECT_EQ(One.smin(One), One);
1225
1226 TestBinaryOpExhaustive(
1227 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1228 return CR1.smin(CR2);
1229 },
1230 [](const APInt &N1, const APInt &N2) {
1231 return APIntOps::smin(N1, N2);
1232 },
1233 PreferSmallestNonFullSigned);
1234 }
1235
1236 TEST_F(ConstantRangeTest, UDiv) {
1237 EXPECT_EQ(Full.udiv(Full), Full);
1238 EXPECT_EQ(Full.udiv(Empty), Empty);
1239 EXPECT_EQ(Full.udiv(One), ConstantRange(APInt(16, 0),
1240 APInt(16, 0xffff / 0xa + 1)));
1241 EXPECT_EQ(Full.udiv(Some), ConstantRange(APInt(16, 0),
1242 APInt(16, 0xffff / 0xa + 1)));
1243 EXPECT_EQ(Full.udiv(Wrap), Full);
1244 EXPECT_EQ(Empty.udiv(Empty), Empty);
1245 EXPECT_EQ(Empty.udiv(One), Empty);
1246 EXPECT_EQ(Empty.udiv(Some), Empty);
1247 EXPECT_EQ(Empty.udiv(Wrap), Empty);
1248 EXPECT_EQ(One.udiv(One), ConstantRange(APInt(16, 1)));
1249 EXPECT_EQ(One.udiv(Some), ConstantRange(APInt(16, 0), APInt(16, 2)));
1250 EXPECT_EQ(One.udiv(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
1251 EXPECT_EQ(Some.udiv(Some), ConstantRange(APInt(16, 0), APInt(16, 0x111)));
1252 EXPECT_EQ(Some.udiv(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
1253 EXPECT_EQ(Wrap.udiv(Wrap), Full);
1254
1255
1256 ConstantRange Zero(APInt(16, 0));
1257 EXPECT_EQ(Zero.udiv(One), Zero);
1258 EXPECT_EQ(Zero.udiv(Full), Zero);
1259
1260 EXPECT_EQ(ConstantRange(APInt(16, 0), APInt(16, 99)).udiv(Full),
1261 ConstantRange(APInt(16, 0), APInt(16, 99)));
1262 EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 99)).udiv(Full),
1263 ConstantRange(APInt(16, 0), APInt(16, 99)));
1264 }
1265
1266 TEST_F(ConstantRangeTest, SDiv) {
1267 ConstantRange OneBit = ConstantRange::getFull(1);
1268 EXPECT_EQ(OneBit.sdiv(OneBit), ConstantRange(APInt(1, 0)));
1269
1270 EnumerateTwoInterestingConstantRanges([&](const ConstantRange &CR1,
1271 const ConstantRange &CR2) {
1272 // Collect possible results in a bit vector. We store the signed value plus
1273 // a bias to make it unsigned.
1274 unsigned Bits = CR1.getBitWidth();
1275 int Bias = 1 << (Bits - 1);
1276 BitVector Results(1 << Bits);
1277 ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
1278 ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
1279 // Division by zero is UB.
1280 if (N2 == 0)
1281 return;
1282
1283 // SignedMin / -1 is UB.
1284 if (N1.isMinSignedValue() && N2.isAllOnes())
1285 return;
1286
1287 APInt N = N1.sdiv(N2);
1288 Results.set(N.getSExtValue() + Bias);
1289 });
1290 });
1291
1292 ConstantRange CR = CR1.sdiv(CR2);
1293 if (Results.none()) {
1294 EXPECT_TRUE(CR.isEmptySet());
1295 return;
1296 }
1297
1298 // If there is a non-full signed envelope, that should be the result.
1299 APInt SMin(Bits, Results.find_first() - Bias);
1300 APInt SMax(Bits, Results.find_last() - Bias);
1301 ConstantRange Envelope = ConstantRange::getNonEmpty(SMin, SMax + 1);
1302 if (!Envelope.isFullSet()) {
1303 EXPECT_EQ(Envelope, CR);
1304 return;
1305 }
1306
1307 // If the signed envelope is a full set, try to find a smaller sign wrapped
1308 // set that is separated in negative and positive components (or one which
1309 // can also additionally contain zero).
1310 int LastNeg = Results.find_last_in(0, Bias) - Bias;
1311 int LastPos = Results.find_next(Bias) - Bias;
1312 if (Results[Bias]) {
1313 if (LastNeg == -1)
1314 ++LastNeg;
1315 else if (LastPos == 1)
1316 --LastPos;
1317 }
1318
1319 APInt WMax(Bits, LastNeg);
1320 APInt WMin(Bits, LastPos);
1321 ConstantRange Wrapped = ConstantRange::getNonEmpty(WMin, WMax + 1);
1322 EXPECT_EQ(Wrapped, CR);
1323 });
1324 }
1325
1326 TEST_F(ConstantRangeTest, URem) {
1327 EXPECT_EQ(Full.urem(Empty), Empty);
1328 EXPECT_EQ(Empty.urem(Full), Empty);
1329 // urem by zero is poison.
1330 EXPECT_EQ(Full.urem(ConstantRange(APInt(16, 0))), Empty);
1331 // urem by full range doesn't contain MaxValue.
1332 EXPECT_EQ(Full.urem(Full), ConstantRange(APInt(16, 0), APInt(16, 0xffff)));
1333 // urem is upper bounded by maximum RHS minus one.
1334 EXPECT_EQ(Full.urem(ConstantRange(APInt(16, 0), APInt(16, 123))),
1335 ConstantRange(APInt(16, 0), APInt(16, 122)));
1336 // urem is upper bounded by maximum LHS.
1337 EXPECT_EQ(ConstantRange(APInt(16, 0), APInt(16, 123)).urem(Full),
1338 ConstantRange(APInt(16, 0), APInt(16, 123)));
1339 // If the LHS is always lower than the RHS, the result is the LHS.
1340 EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 20))
1341 .urem(ConstantRange(APInt(16, 20), APInt(16, 30))),
1342 ConstantRange(APInt(16, 10), APInt(16, 20)));
1343 // It has to be strictly lower, otherwise the top value may wrap to zero.
1344 EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 20))
1345 .urem(ConstantRange(APInt(16, 19), APInt(16, 30))),
1346 ConstantRange(APInt(16, 0), APInt(16, 20)));
1347 // [12, 14] % 10 is [2, 4], but we conservatively compute [0, 9].
1348 EXPECT_EQ(ConstantRange(APInt(16, 12), APInt(16, 15))
1349 .urem(ConstantRange(APInt(16, 10))),
1350 ConstantRange(APInt(16, 0), APInt(16, 10)));
1351
1352 TestBinaryOpExhaustive(
1353 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1354 return CR1.urem(CR2);
1355 },
1356 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
1357 if (N2.isZero())
1358 return std::nullopt;
1359 return N1.urem(N2);
1360 },
1361 PreferSmallest, CheckSingleElementsOnly);
1362 }
1363
1364 TEST_F(ConstantRangeTest, SRem) {
1365 EXPECT_EQ(Full.srem(Empty), Empty);
1366 EXPECT_EQ(Empty.srem(Full), Empty);
1367 // srem by zero is UB.
1368 EXPECT_EQ(Full.srem(ConstantRange(APInt(16, 0))), Empty);
1369 // srem by full range doesn't contain SignedMinValue.
1370 EXPECT_EQ(Full.srem(Full), ConstantRange(APInt::getSignedMinValue(16) + 1,
1371 APInt::getSignedMinValue(16)));
1372
1373 ConstantRange PosMod(APInt(16, 10), APInt(16, 21)); // [10, 20]
1374 ConstantRange NegMod(APInt(16, -20), APInt(16, -9)); // [-20, -10]
1375 ConstantRange IntMinMod(APInt::getSignedMinValue(16));
1376
1377 ConstantRange Expected(16, true);
1378
1379 // srem is bounded by abs(RHS) minus one.
1380 ConstantRange PosLargeLHS(APInt(16, 0), APInt(16, 41));
1381 Expected = ConstantRange(APInt(16, 0), APInt(16, 20));
1382 EXPECT_EQ(PosLargeLHS.srem(PosMod), Expected);
1383 EXPECT_EQ(PosLargeLHS.srem(NegMod), Expected);
1384 ConstantRange NegLargeLHS(APInt(16, -40), APInt(16, 1));
1385 Expected = ConstantRange(APInt(16, -19), APInt(16, 1));
1386 EXPECT_EQ(NegLargeLHS.srem(PosMod), Expected);
1387 EXPECT_EQ(NegLargeLHS.srem(NegMod), Expected);
1388 ConstantRange PosNegLargeLHS(APInt(16, -32), APInt(16, 38));
1389 Expected = ConstantRange(APInt(16, -19), APInt(16, 20));
1390 EXPECT_EQ(PosNegLargeLHS.srem(PosMod), Expected);
1391 EXPECT_EQ(PosNegLargeLHS.srem(NegMod), Expected);
1392
1393 // srem is bounded by LHS.
1394 ConstantRange PosLHS(APInt(16, 0), APInt(16, 16));
1395 EXPECT_EQ(PosLHS.srem(PosMod), PosLHS);
1396 EXPECT_EQ(PosLHS.srem(NegMod), PosLHS);
1397 EXPECT_EQ(PosLHS.srem(IntMinMod), PosLHS);
1398 ConstantRange NegLHS(APInt(16, -15), APInt(16, 1));
1399 EXPECT_EQ(NegLHS.srem(PosMod), NegLHS);
1400 EXPECT_EQ(NegLHS.srem(NegMod), NegLHS);
1401 EXPECT_EQ(NegLHS.srem(IntMinMod), NegLHS);
1402 ConstantRange PosNegLHS(APInt(16, -12), APInt(16, 18));
1403 EXPECT_EQ(PosNegLHS.srem(PosMod), PosNegLHS);
1404 EXPECT_EQ(PosNegLHS.srem(NegMod), PosNegLHS);
1405 EXPECT_EQ(PosNegLHS.srem(IntMinMod), PosNegLHS);
1406
1407 // srem is LHS if it is smaller than RHS.
1408 ConstantRange PosSmallLHS(APInt(16, 3), APInt(16, 8));
1409 EXPECT_EQ(PosSmallLHS.srem(PosMod), PosSmallLHS);
1410 EXPECT_EQ(PosSmallLHS.srem(NegMod), PosSmallLHS);
1411 EXPECT_EQ(PosSmallLHS.srem(IntMinMod), PosSmallLHS);
1412 ConstantRange NegSmallLHS(APInt(16, -7), APInt(16, -2));
1413 EXPECT_EQ(NegSmallLHS.srem(PosMod), NegSmallLHS);
1414 EXPECT_EQ(NegSmallLHS.srem(NegMod), NegSmallLHS);
1415 EXPECT_EQ(NegSmallLHS.srem(IntMinMod), NegSmallLHS);
1416 ConstantRange PosNegSmallLHS(APInt(16, -3), APInt(16, 8));
1417 EXPECT_EQ(PosNegSmallLHS.srem(PosMod), PosNegSmallLHS);
1418 EXPECT_EQ(PosNegSmallLHS.srem(NegMod), PosNegSmallLHS);
1419 EXPECT_EQ(PosNegSmallLHS.srem(IntMinMod), PosNegSmallLHS);
1420
1421 // Example of a suboptimal result:
1422 // [12, 14] srem 10 is [2, 4], but we conservatively compute [0, 9].
1423 EXPECT_EQ(ConstantRange(APInt(16, 12), APInt(16, 15))
1424 .srem(ConstantRange(APInt(16, 10))),
1425 ConstantRange(APInt(16, 0), APInt(16, 10)));
1426
1427 TestBinaryOpExhaustive(
1428 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1429 return CR1.srem(CR2);
1430 },
1431 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
1432 if (N2.isZero())
1433 return std::nullopt;
1434 return N1.srem(N2);
1435 },
1436 PreferSmallest, CheckSingleElementsOnly);
1437 }
1438
1439 TEST_F(ConstantRangeTest, Shl) {
1440 ConstantRange Some2(APInt(16, 0xfff), APInt(16, 0x8000));
1441 ConstantRange WrapNullMax(APInt(16, 0x1), APInt(16, 0x0));
1442 EXPECT_EQ(Full.shl(Full), Full);
1443 EXPECT_EQ(Full.shl(Empty), Empty);
1444 EXPECT_EQ(Full.shl(One), ConstantRange(APInt(16, 0),
1445 APInt(16, 0xfc00) + 1));
1446 EXPECT_EQ(Full.shl(Some), Full); // TODO: [0, (-1 << 0xa) + 1)
1447 EXPECT_EQ(Full.shl(Wrap), Full);
1448 EXPECT_EQ(Empty.shl(Empty), Empty);
1449 EXPECT_EQ(Empty.shl(One), Empty);
1450 EXPECT_EQ(Empty.shl(Some), Empty);
1451 EXPECT_EQ(Empty.shl(Wrap), Empty);
1452 EXPECT_EQ(One.shl(One), ConstantRange(APInt(16, 0xa << 0xa),
1453 APInt(16, (0xa << 0xa) + 1)));
1454 EXPECT_EQ(One.shl(Some), Full); // TODO: [0xa << 0xa, 0)
1455 EXPECT_EQ(One.shl(Wrap), Full); // TODO: [0xa, 0xa << 14 + 1)
1456 EXPECT_EQ(Some.shl(Some), Full); // TODO: [0xa << 0xa, 0xfc01)
1457 EXPECT_EQ(Some.shl(Wrap), Full); // TODO: [0xa, 0x7ff << 0x5 + 1)
1458 EXPECT_EQ(Wrap.shl(Wrap), Full);
1459 EXPECT_EQ(
1460 Some2.shl(ConstantRange(APInt(16, 0x1))),
1461 ConstantRange(APInt(16, 0xfff << 0x1), APInt(16, 0x7fff << 0x1) + 1));
1462 EXPECT_EQ(One.shl(WrapNullMax), Full);
1463
1464 ConstantRange NegOne(APInt(16, 0xffff));
1465 EXPECT_EQ(NegOne.shl(ConstantRange(APInt(16, 0), APInt(16, 5))),
1466 ConstantRange(APInt(16, 0xfff0), APInt(16, 0)));
1467 EXPECT_EQ(ConstantRange(APInt(16, 0xfffe), APInt(16, 0))
1468 .shl(ConstantRange(APInt(16, 0), APInt(16, 5))),
1469 ConstantRange(APInt(16, 0xffe0), APInt(16, 0)));
1470
1471 TestBinaryOpExhaustive(
1472 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1473 return CR1.shl(CR2);
1474 },
1475 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
1476 if (N2.uge(N2.getBitWidth()))
1477 return std::nullopt;
1478 return N1.shl(N2);
1479 },
1480 PreferSmallestUnsigned,
1481 [](const ConstantRange &, const ConstantRange &CR2) {
1482 // We currently only produce precise results for single element RHS.
1483 return CR2.isSingleElement();
1484 });
1485 }
1486
1487 TEST_F(ConstantRangeTest, Lshr) {
1488 EXPECT_EQ(Full.lshr(Full), Full);
1489 EXPECT_EQ(Full.lshr(Empty), Empty);
1490 EXPECT_EQ(Full.lshr(One), ConstantRange(APInt(16, 0),
1491 APInt(16, (0xffff >> 0xa) + 1)));
1492 EXPECT_EQ(Full.lshr(Some), ConstantRange(APInt(16, 0),
1493 APInt(16, (0xffff >> 0xa) + 1)));
1494 EXPECT_EQ(Full.lshr(Wrap), Full);
1495 EXPECT_EQ(Empty.lshr(Empty), Empty);
1496 EXPECT_EQ(Empty.lshr(One), Empty);
1497 EXPECT_EQ(Empty.lshr(Some), Empty);
1498 EXPECT_EQ(Empty.lshr(Wrap), Empty);
1499 EXPECT_EQ(One.lshr(One), ConstantRange(APInt(16, 0)));
1500 EXPECT_EQ(One.lshr(Some), ConstantRange(APInt(16, 0)));
1501 EXPECT_EQ(One.lshr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
1502 EXPECT_EQ(Some.lshr(Some), ConstantRange(APInt(16, 0),
1503 APInt(16, (0xaaa >> 0xa) + 1)));
1504 EXPECT_EQ(Some.lshr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
1505 EXPECT_EQ(Wrap.lshr(Wrap), Full);
1506 }
1507
1508 TEST_F(ConstantRangeTest, Ashr) {
1509 EXPECT_EQ(Full.ashr(Full), Full);
1510 EXPECT_EQ(Full.ashr(Empty), Empty);
1511 EXPECT_EQ(Full.ashr(One), ConstantRange(APInt(16, 0xffe0),
1512 APInt(16, (0x7fff >> 0xa) + 1 )));
1513 ConstantRange Small(APInt(16, 0xa), APInt(16, 0xb));
1514 EXPECT_EQ(Full.ashr(Small), ConstantRange(APInt(16, 0xffe0),
1515 APInt(16, (0x7fff >> 0xa) + 1 )));
1516 EXPECT_EQ(Full.ashr(Some), ConstantRange(APInt(16, 0xffe0),
1517 APInt(16, (0x7fff >> 0xa) + 1 )));
1518 EXPECT_EQ(Full.ashr(Wrap), Full);
1519 EXPECT_EQ(Empty.ashr(Empty), Empty);
1520 EXPECT_EQ(Empty.ashr(One), Empty);
1521 EXPECT_EQ(Empty.ashr(Some), Empty);
1522 EXPECT_EQ(Empty.ashr(Wrap), Empty);
1523 EXPECT_EQ(One.ashr(One), ConstantRange(APInt(16, 0)));
1524 EXPECT_EQ(One.ashr(Some), ConstantRange(APInt(16, 0)));
1525 EXPECT_EQ(One.ashr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
1526 EXPECT_EQ(Some.ashr(Some), ConstantRange(APInt(16, 0),
1527 APInt(16, (0xaaa >> 0xa) + 1)));
1528 EXPECT_EQ(Some.ashr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
1529 EXPECT_EQ(Wrap.ashr(Wrap), Full);
1530 ConstantRange Neg(APInt(16, 0xf3f0, true), APInt(16, 0xf7f8, true));
1531 EXPECT_EQ(Neg.ashr(Small), ConstantRange(APInt(16, 0xfffc, true),
1532 APInt(16, 0xfffe, true)));
1533 }
1534
1535 TEST(ConstantRange, MakeAllowedICmpRegion) {
1536 // PR8250
1537 ConstantRange SMax = ConstantRange(APInt::getSignedMaxValue(32));
1538 EXPECT_TRUE(ConstantRange::makeAllowedICmpRegion(ICmpInst::ICMP_SGT, SMax)
1539 .isEmptySet());
1540 }
1541
1542 TEST(ConstantRange, MakeSatisfyingICmpRegion) {
1543 ConstantRange LowHalf(APInt(8, 0), APInt(8, 128));
1544 ConstantRange HighHalf(APInt(8, 128), APInt(8, 0));
1545 ConstantRange EmptySet(8, /* isFullSet = */ false);
1546
1547 EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_NE, LowHalf),
1548 HighHalf);
1549
1550 EXPECT_EQ(
1551 ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_NE, HighHalf),
1552 LowHalf);
1553
1554 EXPECT_TRUE(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_EQ,
1555 HighHalf).isEmptySet());
1556
1557 ConstantRange UnsignedSample(APInt(8, 5), APInt(8, 200));
1558
1559 EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_ULT,
1560 UnsignedSample),
1561 ConstantRange(APInt(8, 0), APInt(8, 5)));
1562
1563 EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_ULE,
1564 UnsignedSample),
1565 ConstantRange(APInt(8, 0), APInt(8, 6)));
1566
1567 EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_UGT,
1568 UnsignedSample),
1569 ConstantRange(APInt(8, 200), APInt(8, 0)));
1570
1571 EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_UGE,
1572 UnsignedSample),
1573 ConstantRange(APInt(8, 199), APInt(8, 0)));
1574
1575 ConstantRange SignedSample(APInt(8, -5), APInt(8, 5));
1576
1577 EXPECT_EQ(
1578 ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SLT, SignedSample),
1579 ConstantRange(APInt(8, -128), APInt(8, -5)));
1580
1581 EXPECT_EQ(
1582 ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SLE, SignedSample),
1583 ConstantRange(APInt(8, -128), APInt(8, -4)));
1584
1585 EXPECT_EQ(
1586 ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SGT, SignedSample),
1587 ConstantRange(APInt(8, 5), APInt(8, -128)));
1588
1589 EXPECT_EQ(
1590 ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SGE, SignedSample),
1591 ConstantRange(APInt(8, 4), APInt(8, -128)));
1592 }
1593
1594 void ICmpTestImpl(CmpInst::Predicate Pred) {
1595 EnumerateTwoInterestingConstantRanges(
1596 [&](const ConstantRange &CR1, const ConstantRange &CR2) {
1597 bool Exhaustive = true;
1598 ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
1599 ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
1600 Exhaustive &= ICmpInst::compare(N1, N2, Pred);
1601 });
1602 });
1603 EXPECT_EQ(CR1.icmp(Pred, CR2), Exhaustive);
1604 });
1605 }
1606
1607 TEST(ConstantRange, ICmp) {
1608 for (auto Pred : ICmpInst::predicates())
1609 ICmpTestImpl(Pred);
1610 }
1611
1612 TEST(ConstantRange, MakeGuaranteedNoWrapRegion) {
1613 const int IntMin4Bits = 8;
1614 const int IntMax4Bits = 7;
1615 typedef OverflowingBinaryOperator OBO;
1616
1617 for (int Const : {0, -1, -2, 1, 2, IntMin4Bits, IntMax4Bits}) {
1618 APInt C(4, Const, true /* = isSigned */);
1619
1620 auto NUWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
1621 Instruction::Add, C, OBO::NoUnsignedWrap);
1622
1623 EXPECT_FALSE(NUWRegion.isEmptySet());
1624
1625 auto NSWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
1626 Instruction::Add, C, OBO::NoSignedWrap);
1627
1628 EXPECT_FALSE(NSWRegion.isEmptySet());
1629
1630 for (APInt I = NUWRegion.getLower(), E = NUWRegion.getUpper(); I != E;
1631 ++I) {
1632 bool Overflow = false;
1633 (void)I.uadd_ov(C, Overflow);
1634 EXPECT_FALSE(Overflow);
1635 }
1636
1637 for (APInt I = NSWRegion.getLower(), E = NSWRegion.getUpper(); I != E;
1638 ++I) {
1639 bool Overflow = false;
1640 (void)I.sadd_ov(C, Overflow);
1641 EXPECT_FALSE(Overflow);
1642 }
1643 }
1644
1645 for (int Const : {0, -1, -2, 1, 2, IntMin4Bits, IntMax4Bits}) {
1646 APInt C(4, Const, true /* = isSigned */);
1647
1648 auto NUWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
1649 Instruction::Sub, C, OBO::NoUnsignedWrap);
1650
1651 EXPECT_FALSE(NUWRegion.isEmptySet());
1652
1653 auto NSWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
1654 Instruction::Sub, C, OBO::NoSignedWrap);
1655
1656 EXPECT_FALSE(NSWRegion.isEmptySet());
1657
1658 for (APInt I = NUWRegion.getLower(), E = NUWRegion.getUpper(); I != E;
1659 ++I) {
1660 bool Overflow = false;
1661 (void)I.usub_ov(C, Overflow);
1662 EXPECT_FALSE(Overflow);
1663 }
1664
1665 for (APInt I = NSWRegion.getLower(), E = NSWRegion.getUpper(); I != E;
1666 ++I) {
1667 bool Overflow = false;
1668 (void)I.ssub_ov(C, Overflow);
1669 EXPECT_FALSE(Overflow);
1670 }
1671 }
1672
1673 auto NSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
1674 Instruction::Add, ConstantRange(32, /* isFullSet = */ true),
1675 OBO::NoSignedWrap);
1676 EXPECT_TRUE(NSWForAllValues.isSingleElement() &&
1677 NSWForAllValues.getSingleElement()->isMinValue());
1678
1679 NSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
1680 Instruction::Sub, ConstantRange(32, /* isFullSet = */ true),
1681 OBO::NoSignedWrap);
1682 EXPECT_TRUE(NSWForAllValues.isSingleElement() &&
1683 NSWForAllValues.getSingleElement()->isMaxValue());
1684
1685 auto NUWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
1686 Instruction::Add, ConstantRange(32, /* isFullSet = */ true),
1687 OBO::NoUnsignedWrap);
1688 EXPECT_TRUE(NUWForAllValues.isSingleElement() &&
1689 NUWForAllValues.getSingleElement()->isMinValue());
1690
1691 NUWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
1692 Instruction::Sub, ConstantRange(32, /* isFullSet = */ true),
1693 OBO::NoUnsignedWrap);
1694 EXPECT_TRUE(NUWForAllValues.isSingleElement() &&
1695 NUWForAllValues.getSingleElement()->isMaxValue());
1696
1697 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
1698 Instruction::Add, APInt(32, 0), OBO::NoUnsignedWrap).isFullSet());
1699 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
1700 Instruction::Add, APInt(32, 0), OBO::NoSignedWrap).isFullSet());
1701 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
1702 Instruction::Sub, APInt(32, 0), OBO::NoUnsignedWrap).isFullSet());
1703 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
1704 Instruction::Sub, APInt(32, 0), OBO::NoSignedWrap).isFullSet());
1705
1706 ConstantRange OneToFive(APInt(32, 1), APInt(32, 6));
1707 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1708 Instruction::Add, OneToFive, OBO::NoSignedWrap),
1709 ConstantRange(APInt::getSignedMinValue(32),
1710 APInt::getSignedMaxValue(32) - 4));
1711 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1712 Instruction::Add, OneToFive, OBO::NoUnsignedWrap),
1713 ConstantRange(APInt::getMinValue(32), APInt::getMinValue(32) - 5));
1714 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1715 Instruction::Sub, OneToFive, OBO::NoSignedWrap),
1716 ConstantRange(APInt::getSignedMinValue(32) + 5,
1717 APInt::getSignedMinValue(32)));
1718 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1719 Instruction::Sub, OneToFive, OBO::NoUnsignedWrap),
1720 ConstantRange(APInt::getMinValue(32) + 5, APInt::getMinValue(32)));
1721
1722 ConstantRange MinusFiveToMinusTwo(APInt(32, -5), APInt(32, -1));
1723 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1724 Instruction::Add, MinusFiveToMinusTwo, OBO::NoSignedWrap),
1725 ConstantRange(APInt::getSignedMinValue(32) + 5,
1726 APInt::getSignedMinValue(32)));
1727 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1728 Instruction::Add, MinusFiveToMinusTwo, OBO::NoUnsignedWrap),
1729 ConstantRange(APInt(32, 0), APInt(32, 2)));
1730 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1731 Instruction::Sub, MinusFiveToMinusTwo, OBO::NoSignedWrap),
1732 ConstantRange(APInt::getSignedMinValue(32),
1733 APInt::getSignedMaxValue(32) - 4));
1734 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1735 Instruction::Sub, MinusFiveToMinusTwo, OBO::NoUnsignedWrap),
1736 ConstantRange(APInt::getMaxValue(32) - 1,
1737 APInt::getMinValue(32)));
1738
1739 ConstantRange MinusOneToOne(APInt(32, -1), APInt(32, 2));
1740 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1741 Instruction::Add, MinusOneToOne, OBO::NoSignedWrap),
1742 ConstantRange(APInt::getSignedMinValue(32) + 1,
1743 APInt::getSignedMinValue(32) - 1));
1744 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1745 Instruction::Add, MinusOneToOne, OBO::NoUnsignedWrap),
1746 ConstantRange(APInt(32, 0), APInt(32, 1)));
1747 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1748 Instruction::Sub, MinusOneToOne, OBO::NoSignedWrap),
1749 ConstantRange(APInt::getSignedMinValue(32) + 1,
1750 APInt::getSignedMinValue(32) - 1));
1751 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1752 Instruction::Sub, MinusOneToOne, OBO::NoUnsignedWrap),
1753 ConstantRange(APInt::getMaxValue(32),
1754 APInt::getMinValue(32)));
1755
1756 ConstantRange One(APInt(32, 1), APInt(32, 2));
1757 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1758 Instruction::Add, One, OBO::NoSignedWrap),
1759 ConstantRange(APInt::getSignedMinValue(32),
1760 APInt::getSignedMaxValue(32)));
1761 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1762 Instruction::Add, One, OBO::NoUnsignedWrap),
1763 ConstantRange(APInt::getMinValue(32), APInt::getMaxValue(32)));
1764 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1765 Instruction::Sub, One, OBO::NoSignedWrap),
1766 ConstantRange(APInt::getSignedMinValue(32) + 1,
1767 APInt::getSignedMinValue(32)));
1768 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1769 Instruction::Sub, One, OBO::NoUnsignedWrap),
1770 ConstantRange(APInt::getMinValue(32) + 1, APInt::getMinValue(32)));
1771
1772 ConstantRange OneLessThanBitWidth(APInt(32, 0), APInt(32, 31) + 1);
1773 ConstantRange UpToBitWidth(APInt(32, 0), APInt(32, 32) + 1);
1774 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1775 Instruction::Shl, UpToBitWidth, OBO::NoUnsignedWrap),
1776 ConstantRange::makeGuaranteedNoWrapRegion(
1777 Instruction::Shl, OneLessThanBitWidth, OBO::NoUnsignedWrap));
1778 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1779 Instruction::Shl, UpToBitWidth, OBO::NoSignedWrap),
1780 ConstantRange::makeGuaranteedNoWrapRegion(
1781 Instruction::Shl, OneLessThanBitWidth, OBO::NoSignedWrap));
1782 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1783 Instruction::Shl, UpToBitWidth, OBO::NoUnsignedWrap),
1784 ConstantRange(APInt(32, 0), APInt(32, 1) + 1));
1785 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1786 Instruction::Shl, UpToBitWidth, OBO::NoSignedWrap),
1787 ConstantRange(APInt(32, -1), APInt(32, 0) + 1));
1788
1789 EXPECT_EQ(
1790 ConstantRange::makeGuaranteedNoWrapRegion(
1791 Instruction::Shl, ConstantRange::getFull(32), OBO::NoUnsignedWrap),
1792 ConstantRange::makeGuaranteedNoWrapRegion(
1793 Instruction::Shl, OneLessThanBitWidth, OBO::NoUnsignedWrap));
1794 EXPECT_EQ(
1795 ConstantRange::makeGuaranteedNoWrapRegion(
1796 Instruction::Shl, ConstantRange::getFull(32), OBO::NoSignedWrap),
1797 ConstantRange::makeGuaranteedNoWrapRegion(
1798 Instruction::Shl, OneLessThanBitWidth, OBO::NoSignedWrap));
1799
1800 ConstantRange IllegalShAmt(APInt(32, 32), APInt(32, 0) + 1);
1801 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1802 Instruction::Shl, IllegalShAmt, OBO::NoUnsignedWrap),
1803 ConstantRange::getFull(32));
1804 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1805 Instruction::Shl, IllegalShAmt, OBO::NoSignedWrap),
1806 ConstantRange::getFull(32));
1807
1808 EXPECT_EQ(
1809 ConstantRange::makeGuaranteedNoWrapRegion(
1810 Instruction::Shl, ConstantRange(APInt(32, -32), APInt(32, 16) + 1),
1811 OBO::NoUnsignedWrap),
1812 ConstantRange::makeGuaranteedNoWrapRegion(
1813 Instruction::Shl, ConstantRange(APInt(32, 0), APInt(32, 16) + 1),
1814 OBO::NoUnsignedWrap));
1815 EXPECT_EQ(
1816 ConstantRange::makeGuaranteedNoWrapRegion(
1817 Instruction::Shl, ConstantRange(APInt(32, -32), APInt(32, 16) + 1),
1818 OBO::NoSignedWrap),
1819 ConstantRange::makeGuaranteedNoWrapRegion(
1820 Instruction::Shl, ConstantRange(APInt(32, 0), APInt(32, 16) + 1),
1821 OBO::NoSignedWrap));
1822
1823 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1824 Instruction::Shl,
1825 ConstantRange(APInt(32, -32), APInt(32, 16) + 1),
1826 OBO::NoUnsignedWrap),
1827 ConstantRange(APInt(32, 0), APInt(32, 65535) + 1));
1828 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1829 Instruction::Shl,
1830 ConstantRange(APInt(32, -32), APInt(32, 16) + 1),
1831 OBO::NoSignedWrap),
1832 ConstantRange(APInt(32, -32768), APInt(32, 32767) + 1));
1833 }
1834
1835 template<typename Fn>
1836 void TestNoWrapRegionExhaustive(Instruction::BinaryOps BinOp,
1837 unsigned NoWrapKind, Fn OverflowFn) {
1838 for (unsigned Bits : {1, 5}) {
1839 EnumerateConstantRanges(Bits, [&](const ConstantRange &CR) {
1840 if (CR.isEmptySet())
1841 return;
1842 if (Instruction::isShift(BinOp) && CR.getUnsignedMax().uge(Bits))
1843 return;
1844
1845 ConstantRange NoWrap =
1846 ConstantRange::makeGuaranteedNoWrapRegion(BinOp, CR, NoWrapKind);
1847 EnumerateAPInts(Bits, [&](const APInt &N1) {
1848 bool NoOverflow = true;
1849 bool Overflow = true;
1850 ForeachNumInConstantRange(CR, [&](const APInt &N2) {
1851 if (OverflowFn(N1, N2))
1852 NoOverflow = false;
1853 else
1854 Overflow = false;
1855 });
1856 EXPECT_EQ(NoOverflow, NoWrap.contains(N1));
1857
1858 // The no-wrap range is exact for single-element ranges.
1859 if (CR.isSingleElement()) {
1860 EXPECT_EQ(Overflow, !NoWrap.contains(N1));
1861 }
1862 });
1863 });
1864 }
1865 }
1866
1867 // Show that makeGuaranteedNoWrapRegion() is maximal, and for single-element
1868 // ranges also exact.
1869 TEST(ConstantRange, NoWrapRegionExhaustive) {
1870 TestNoWrapRegionExhaustive(
1871 Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap,
1872 [](const APInt &N1, const APInt &N2) {
1873 bool Overflow;
1874 (void) N1.uadd_ov(N2, Overflow);
1875 return Overflow;
1876 });
1877 TestNoWrapRegionExhaustive(
1878 Instruction::Add, OverflowingBinaryOperator::NoSignedWrap,
1879 [](const APInt &N1, const APInt &N2) {
1880 bool Overflow;
1881 (void) N1.sadd_ov(N2, Overflow);
1882 return Overflow;
1883 });
1884 TestNoWrapRegionExhaustive(
1885 Instruction::Sub, OverflowingBinaryOperator::NoUnsignedWrap,
1886 [](const APInt &N1, const APInt &N2) {
1887 bool Overflow;
1888 (void) N1.usub_ov(N2, Overflow);
1889 return Overflow;
1890 });
1891 TestNoWrapRegionExhaustive(
1892 Instruction::Sub, OverflowingBinaryOperator::NoSignedWrap,
1893 [](const APInt &N1, const APInt &N2) {
1894 bool Overflow;
1895 (void) N1.ssub_ov(N2, Overflow);
1896 return Overflow;
1897 });
1898 TestNoWrapRegionExhaustive(
1899 Instruction::Mul, OverflowingBinaryOperator::NoUnsignedWrap,
1900 [](const APInt &N1, const APInt &N2) {
1901 bool Overflow;
1902 (void) N1.umul_ov(N2, Overflow);
1903 return Overflow;
1904 });
1905 TestNoWrapRegionExhaustive(
1906 Instruction::Mul, OverflowingBinaryOperator::NoSignedWrap,
1907 [](const APInt &N1, const APInt &N2) {
1908 bool Overflow;
1909 (void) N1.smul_ov(N2, Overflow);
1910 return Overflow;
1911 });
1912 TestNoWrapRegionExhaustive(Instruction::Shl,
1913 OverflowingBinaryOperator::NoUnsignedWrap,
1914 [](const APInt &N1, const APInt &N2) {
1915 bool Overflow;
1916 (void)N1.ushl_ov(N2, Overflow);
1917 return Overflow;
1918 });
1919 TestNoWrapRegionExhaustive(Instruction::Shl,
1920 OverflowingBinaryOperator::NoSignedWrap,
1921 [](const APInt &N1, const APInt &N2) {
1922 bool Overflow;
1923 (void)N1.sshl_ov(N2, Overflow);
1924 return Overflow;
1925 });
1926 }
1927
1928 TEST(ConstantRange, GetEquivalentICmp) {
1929 APInt RHS;
1930 CmpInst::Predicate Pred;
1931
1932 EXPECT_TRUE(ConstantRange(APInt::getMinValue(32), APInt(32, 100))
1933 .getEquivalentICmp(Pred, RHS));
1934 EXPECT_EQ(Pred, CmpInst::ICMP_ULT);
1935 EXPECT_EQ(RHS, APInt(32, 100));
1936
1937 EXPECT_TRUE(ConstantRange(APInt::getSignedMinValue(32), APInt(32, 100))
1938 .getEquivalentICmp(Pred, RHS));
1939 EXPECT_EQ(Pred, CmpInst::ICMP_SLT);
1940 EXPECT_EQ(RHS, APInt(32, 100));
1941
1942 EXPECT_TRUE(ConstantRange(APInt(32, 100), APInt::getMinValue(32))
1943 .getEquivalentICmp(Pred, RHS));
1944 EXPECT_EQ(Pred, CmpInst::ICMP_UGE);
1945 EXPECT_EQ(RHS, APInt(32, 100));
1946
1947 EXPECT_TRUE(ConstantRange(APInt(32, 100), APInt::getSignedMinValue(32))
1948 .getEquivalentICmp(Pred, RHS));
1949 EXPECT_EQ(Pred, CmpInst::ICMP_SGE);
1950 EXPECT_EQ(RHS, APInt(32, 100));
1951
1952 EXPECT_TRUE(
1953 ConstantRange(32, /*isFullSet=*/true).getEquivalentICmp(Pred, RHS));
1954 EXPECT_EQ(Pred, CmpInst::ICMP_UGE);
1955 EXPECT_EQ(RHS, APInt(32, 0));
1956
1957 EXPECT_TRUE(
1958 ConstantRange(32, /*isFullSet=*/false).getEquivalentICmp(Pred, RHS));
1959 EXPECT_EQ(Pred, CmpInst::ICMP_ULT);
1960 EXPECT_EQ(RHS, APInt(32, 0));
1961
1962 EXPECT_FALSE(ConstantRange(APInt(32, 100), APInt(32, 200))
1963 .getEquivalentICmp(Pred, RHS));
1964
1965 EXPECT_FALSE(ConstantRange(APInt::getSignedMinValue(32) - APInt(32, 100),
1966 APInt::getSignedMinValue(32) + APInt(32, 100))
1967 .getEquivalentICmp(Pred, RHS));
1968
1969 EXPECT_FALSE(ConstantRange(APInt::getMinValue(32) - APInt(32, 100),
1970 APInt::getMinValue(32) + APInt(32, 100))
1971 .getEquivalentICmp(Pred, RHS));
1972
1973 EXPECT_TRUE(ConstantRange(APInt(32, 100)).getEquivalentICmp(Pred, RHS));
1974 EXPECT_EQ(Pred, CmpInst::ICMP_EQ);
1975 EXPECT_EQ(RHS, APInt(32, 100));
1976
1977 EXPECT_TRUE(
1978 ConstantRange(APInt(32, 100)).inverse().getEquivalentICmp(Pred, RHS));
1979 EXPECT_EQ(Pred, CmpInst::ICMP_NE);
1980 EXPECT_EQ(RHS, APInt(32, 100));
1981
1982 EXPECT_TRUE(
1983 ConstantRange(APInt(512, 100)).inverse().getEquivalentICmp(Pred, RHS));
1984 EXPECT_EQ(Pred, CmpInst::ICMP_NE);
1985 EXPECT_EQ(RHS, APInt(512, 100));
1986
1987 // NB! It would be correct for the following four calls to getEquivalentICmp
1988 // to return ordered predicates like CmpInst::ICMP_ULT or CmpInst::ICMP_UGT.
1989 // However, that's not the case today.
1990
1991 EXPECT_TRUE(ConstantRange(APInt(32, 0)).getEquivalentICmp(Pred, RHS));
1992 EXPECT_EQ(Pred, CmpInst::ICMP_EQ);
1993 EXPECT_EQ(RHS, APInt(32, 0));
1994
1995 EXPECT_TRUE(
1996 ConstantRange(APInt(32, 0)).inverse().getEquivalentICmp(Pred, RHS));
1997 EXPECT_EQ(Pred, CmpInst::ICMP_NE);
1998 EXPECT_EQ(RHS, APInt(32, 0));
1999
2000 EXPECT_TRUE(ConstantRange(APInt(32, -1)).getEquivalentICmp(Pred, RHS));
2001 EXPECT_EQ(Pred, CmpInst::ICMP_EQ);
2002 EXPECT_EQ(RHS, APInt(32, -1));
2003
2004 EXPECT_TRUE(
2005 ConstantRange(APInt(32, -1)).inverse().getEquivalentICmp(Pred, RHS));
2006 EXPECT_EQ(Pred, CmpInst::ICMP_NE);
2007 EXPECT_EQ(RHS, APInt(32, -1));
2008
2009 EnumerateInterestingConstantRanges([](const ConstantRange &CR) {
2010 unsigned Bits = CR.getBitWidth();
2011 CmpInst::Predicate Pred;
2012 APInt RHS, Offset;
2013 CR.getEquivalentICmp(Pred, RHS, Offset);
2014 EnumerateAPInts(Bits, [&](const APInt &N) {
2015 bool Result = ICmpInst::compare(N + Offset, RHS, Pred);
2016 EXPECT_EQ(CR.contains(N), Result);
2017 });
2018
2019 if (CR.getEquivalentICmp(Pred, RHS)) {
2020 EnumerateAPInts(Bits, [&](const APInt &N) {
2021 bool Result = ICmpInst::compare(N, RHS, Pred);
2022 EXPECT_EQ(CR.contains(N), Result);
2023 });
2024 }
2025 });
2026 }
2027
2028 #define EXPECT_MAY_OVERFLOW(op) \
2029 EXPECT_EQ(ConstantRange::OverflowResult::MayOverflow, (op))
2030 #define EXPECT_ALWAYS_OVERFLOWS_LOW(op) \
2031 EXPECT_EQ(ConstantRange::OverflowResult::AlwaysOverflowsLow, (op))
2032 #define EXPECT_ALWAYS_OVERFLOWS_HIGH(op) \
2033 EXPECT_EQ(ConstantRange::OverflowResult::AlwaysOverflowsHigh, (op))
2034 #define EXPECT_NEVER_OVERFLOWS(op) \
2035 EXPECT_EQ(ConstantRange::OverflowResult::NeverOverflows, (op))
2036
2037 TEST_F(ConstantRangeTest, UnsignedAddOverflow) {
2038 // Ill-defined - may overflow is a conservative result.
2039 EXPECT_MAY_OVERFLOW(Some.unsignedAddMayOverflow(Empty));
2040 EXPECT_MAY_OVERFLOW(Empty.unsignedAddMayOverflow(Some));
2041
2042 // Never overflow despite one full/wrap set.
2043 ConstantRange Zero(APInt::getZero(16));
2044 EXPECT_NEVER_OVERFLOWS(Full.unsignedAddMayOverflow(Zero));
2045 EXPECT_NEVER_OVERFLOWS(Wrap.unsignedAddMayOverflow(Zero));
2046 EXPECT_NEVER_OVERFLOWS(Zero.unsignedAddMayOverflow(Full));
2047 EXPECT_NEVER_OVERFLOWS(Zero.unsignedAddMayOverflow(Wrap));
2048
2049 // But usually full/wrap always may overflow.
2050 EXPECT_MAY_OVERFLOW(Full.unsignedAddMayOverflow(One));
2051 EXPECT_MAY_OVERFLOW(Wrap.unsignedAddMayOverflow(One));
2052 EXPECT_MAY_OVERFLOW(One.unsignedAddMayOverflow(Full));
2053 EXPECT_MAY_OVERFLOW(One.unsignedAddMayOverflow(Wrap));
2054
2055 ConstantRange A(APInt(16, 0xfd00), APInt(16, 0xfe00));
2056 ConstantRange B1(APInt(16, 0x0100), APInt(16, 0x0201));
2057 ConstantRange B2(APInt(16, 0x0100), APInt(16, 0x0202));
2058 EXPECT_NEVER_OVERFLOWS(A.unsignedAddMayOverflow(B1));
2059 EXPECT_MAY_OVERFLOW(A.unsignedAddMayOverflow(B2));
2060 EXPECT_NEVER_OVERFLOWS(B1.unsignedAddMayOverflow(A));
2061 EXPECT_MAY_OVERFLOW(B2.unsignedAddMayOverflow(A));
2062
2063 ConstantRange C1(APInt(16, 0x0299), APInt(16, 0x0400));
2064 ConstantRange C2(APInt(16, 0x0300), APInt(16, 0x0400));
2065 EXPECT_MAY_OVERFLOW(A.unsignedAddMayOverflow(C1));
2066 EXPECT_ALWAYS_OVERFLOWS_HIGH(A.unsignedAddMayOverflow(C2));
2067 EXPECT_MAY_OVERFLOW(C1.unsignedAddMayOverflow(A));
2068 EXPECT_ALWAYS_OVERFLOWS_HIGH(C2.unsignedAddMayOverflow(A));
2069 }
2070
2071 TEST_F(ConstantRangeTest, UnsignedSubOverflow) {
2072 // Ill-defined - may overflow is a conservative result.
2073 EXPECT_MAY_OVERFLOW(Some.unsignedSubMayOverflow(Empty));
2074 EXPECT_MAY_OVERFLOW(Empty.unsignedSubMayOverflow(Some));
2075
2076 // Never overflow despite one full/wrap set.
2077 ConstantRange Zero(APInt::getZero(16));
2078 ConstantRange Max(APInt::getAllOnes(16));
2079 EXPECT_NEVER_OVERFLOWS(Full.unsignedSubMayOverflow(Zero));
2080 EXPECT_NEVER_OVERFLOWS(Wrap.unsignedSubMayOverflow(Zero));
2081 EXPECT_NEVER_OVERFLOWS(Max.unsignedSubMayOverflow(Full));
2082 EXPECT_NEVER_OVERFLOWS(Max.unsignedSubMayOverflow(Wrap));
2083
2084 // But usually full/wrap always may overflow.
2085 EXPECT_MAY_OVERFLOW(Full.unsignedSubMayOverflow(One));
2086 EXPECT_MAY_OVERFLOW(Wrap.unsignedSubMayOverflow(One));
2087 EXPECT_MAY_OVERFLOW(One.unsignedSubMayOverflow(Full));
2088 EXPECT_MAY_OVERFLOW(One.unsignedSubMayOverflow(Wrap));
2089
2090 ConstantRange A(APInt(16, 0x0000), APInt(16, 0x0100));
2091 ConstantRange B(APInt(16, 0x0100), APInt(16, 0x0200));
2092 EXPECT_NEVER_OVERFLOWS(B.unsignedSubMayOverflow(A));
2093 EXPECT_ALWAYS_OVERFLOWS_LOW(A.unsignedSubMayOverflow(B));
2094
2095 ConstantRange A1(APInt(16, 0x0000), APInt(16, 0x0101));
2096 ConstantRange B1(APInt(16, 0x0100), APInt(16, 0x0201));
2097 EXPECT_NEVER_OVERFLOWS(B1.unsignedSubMayOverflow(A1));
2098 EXPECT_MAY_OVERFLOW(A1.unsignedSubMayOverflow(B1));
2099
2100 ConstantRange A2(APInt(16, 0x0000), APInt(16, 0x0102));
2101 ConstantRange B2(APInt(16, 0x0100), APInt(16, 0x0202));
2102 EXPECT_MAY_OVERFLOW(B2.unsignedSubMayOverflow(A2));
2103 EXPECT_MAY_OVERFLOW(A2.unsignedSubMayOverflow(B2));
2104 }
2105
2106 TEST_F(ConstantRangeTest, SignedAddOverflow) {
2107 // Ill-defined - may overflow is a conservative result.
2108 EXPECT_MAY_OVERFLOW(Some.signedAddMayOverflow(Empty));
2109 EXPECT_MAY_OVERFLOW(Empty.signedAddMayOverflow(Some));
2110
2111 // Never overflow despite one full/wrap set.
2112 ConstantRange Zero(APInt::getZero(16));
2113 EXPECT_NEVER_OVERFLOWS(Full.signedAddMayOverflow(Zero));
2114 EXPECT_NEVER_OVERFLOWS(Wrap.signedAddMayOverflow(Zero));
2115 EXPECT_NEVER_OVERFLOWS(Zero.signedAddMayOverflow(Full));
2116 EXPECT_NEVER_OVERFLOWS(Zero.signedAddMayOverflow(Wrap));
2117
2118 // But usually full/wrap always may overflow.
2119 EXPECT_MAY_OVERFLOW(Full.signedAddMayOverflow(One));
2120 EXPECT_MAY_OVERFLOW(Wrap.signedAddMayOverflow(One));
2121 EXPECT_MAY_OVERFLOW(One.signedAddMayOverflow(Full));
2122 EXPECT_MAY_OVERFLOW(One.signedAddMayOverflow(Wrap));
2123
2124 ConstantRange A(APInt(16, 0x7d00), APInt(16, 0x7e00));
2125 ConstantRange B1(APInt(16, 0x0100), APInt(16, 0x0201));
2126 ConstantRange B2(APInt(16, 0x0100), APInt(16, 0x0202));
2127 EXPECT_NEVER_OVERFLOWS(A.signedAddMayOverflow(B1));
2128 EXPECT_MAY_OVERFLOW(A.signedAddMayOverflow(B2));
2129 ConstantRange B3(APInt(16, 0x8000), APInt(16, 0x0201));
2130 ConstantRange B4(APInt(16, 0x8000), APInt(16, 0x0202));
2131 EXPECT_NEVER_OVERFLOWS(A.signedAddMayOverflow(B3));
2132 EXPECT_MAY_OVERFLOW(A.signedAddMayOverflow(B4));
2133 ConstantRange B5(APInt(16, 0x0299), APInt(16, 0x0400));
2134 ConstantRange B6(APInt(16, 0x0300), APInt(16, 0x0400));
2135 EXPECT_MAY_OVERFLOW(A.signedAddMayOverflow(B5));
2136 EXPECT_ALWAYS_OVERFLOWS_HIGH(A.signedAddMayOverflow(B6));
2137
2138 ConstantRange C(APInt(16, 0x8200), APInt(16, 0x8300));
2139 ConstantRange D1(APInt(16, 0xfe00), APInt(16, 0xff00));
2140 ConstantRange D2(APInt(16, 0xfd99), APInt(16, 0xff00));
2141 EXPECT_NEVER_OVERFLOWS(C.signedAddMayOverflow(D1));
2142 EXPECT_MAY_OVERFLOW(C.signedAddMayOverflow(D2));
2143 ConstantRange D3(APInt(16, 0xfe00), APInt(16, 0x8000));
2144 ConstantRange D4(APInt(16, 0xfd99), APInt(16, 0x8000));
2145 EXPECT_NEVER_OVERFLOWS(C.signedAddMayOverflow(D3));
2146 EXPECT_MAY_OVERFLOW(C.signedAddMayOverflow(D4));
2147 ConstantRange D5(APInt(16, 0xfc00), APInt(16, 0xfd02));
2148 ConstantRange D6(APInt(16, 0xfc00), APInt(16, 0xfd01));
2149 EXPECT_MAY_OVERFLOW(C.signedAddMayOverflow(D5));
2150 EXPECT_ALWAYS_OVERFLOWS_LOW(C.signedAddMayOverflow(D6));
2151
2152 ConstantRange E(APInt(16, 0xff00), APInt(16, 0x0100));
2153 EXPECT_NEVER_OVERFLOWS(E.signedAddMayOverflow(E));
2154 ConstantRange F(APInt(16, 0xf000), APInt(16, 0x7000));
2155 EXPECT_MAY_OVERFLOW(F.signedAddMayOverflow(F));
2156 }
2157
2158 TEST_F(ConstantRangeTest, SignedSubOverflow) {
2159 // Ill-defined - may overflow is a conservative result.
2160 EXPECT_MAY_OVERFLOW(Some.signedSubMayOverflow(Empty));
2161 EXPECT_MAY_OVERFLOW(Empty.signedSubMayOverflow(Some));
2162
2163 // Never overflow despite one full/wrap set.
2164 ConstantRange Zero(APInt::getZero(16));
2165 EXPECT_NEVER_OVERFLOWS(Full.signedSubMayOverflow(Zero));
2166 EXPECT_NEVER_OVERFLOWS(Wrap.signedSubMayOverflow(Zero));
2167
2168 // But usually full/wrap always may overflow.
2169 EXPECT_MAY_OVERFLOW(Full.signedSubMayOverflow(One));
2170 EXPECT_MAY_OVERFLOW(Wrap.signedSubMayOverflow(One));
2171 EXPECT_MAY_OVERFLOW(One.signedSubMayOverflow(Full));
2172 EXPECT_MAY_OVERFLOW(One.signedSubMayOverflow(Wrap));
2173
2174 ConstantRange A(APInt(16, 0x7d00), APInt(16, 0x7e00));
2175 ConstantRange B1(APInt(16, 0xfe00), APInt(16, 0xff00));
2176 ConstantRange B2(APInt(16, 0xfd99), APInt(16, 0xff00));
2177 EXPECT_NEVER_OVERFLOWS(A.signedSubMayOverflow(B1));
2178 EXPECT_MAY_OVERFLOW(A.signedSubMayOverflow(B2));
2179 ConstantRange B3(APInt(16, 0xfc00), APInt(16, 0xfd02));
2180 ConstantRange B4(APInt(16, 0xfc00), APInt(16, 0xfd01));
2181 EXPECT_MAY_OVERFLOW(A.signedSubMayOverflow(B3));
2182 EXPECT_ALWAYS_OVERFLOWS_HIGH(A.signedSubMayOverflow(B4));
2183
2184 ConstantRange C(APInt(16, 0x8200), APInt(16, 0x8300));
2185 ConstantRange D1(APInt(16, 0x0100), APInt(16, 0x0201));
2186 ConstantRange D2(APInt(16, 0x0100), APInt(16, 0x0202));
2187 EXPECT_NEVER_OVERFLOWS(C.signedSubMayOverflow(D1));
2188 EXPECT_MAY_OVERFLOW(C.signedSubMayOverflow(D2));
2189 ConstantRange D3(APInt(16, 0x0299), APInt(16, 0x0400));
2190 ConstantRange D4(APInt(16, 0x0300), APInt(16, 0x0400));
2191 EXPECT_MAY_OVERFLOW(C.signedSubMayOverflow(D3));
2192 EXPECT_ALWAYS_OVERFLOWS_LOW(C.signedSubMayOverflow(D4));
2193
2194 ConstantRange E(APInt(16, 0xff00), APInt(16, 0x0100));
2195 EXPECT_NEVER_OVERFLOWS(E.signedSubMayOverflow(E));
2196 ConstantRange F(APInt(16, 0xf000), APInt(16, 0x7001));
2197 EXPECT_MAY_OVERFLOW(F.signedSubMayOverflow(F));
2198 }
2199
2200 template <typename Fn1, typename Fn2>
2201 static void TestOverflowExhaustive(Fn1 OverflowFn, Fn2 MayOverflowFn) {
2202 // Constant range overflow checks are tested exhaustively on 4-bit numbers.
2203 EnumerateTwoInterestingConstantRanges([=](const ConstantRange &CR1,
2204 const ConstantRange &CR2) {
2205 // Loop over all N1 in CR1 and N2 in CR2 and check whether any of the
2206 // operations have overflow / have no overflow.
2207 bool RangeHasOverflowLow = false;
2208 bool RangeHasOverflowHigh = false;
2209 bool RangeHasNoOverflow = false;
2210 ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
2211 ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
2212 bool IsOverflowHigh;
2213 if (!OverflowFn(IsOverflowHigh, N1, N2)) {
2214 RangeHasNoOverflow = true;
2215 return;
2216 }
2217
2218 if (IsOverflowHigh)
2219 RangeHasOverflowHigh = true;
2220 else
2221 RangeHasOverflowLow = true;
2222 });
2223 });
2224
2225 ConstantRange::OverflowResult OR = MayOverflowFn(CR1, CR2);
2226 switch (OR) {
2227 case ConstantRange::OverflowResult::AlwaysOverflowsLow:
2228 EXPECT_TRUE(RangeHasOverflowLow);
2229 EXPECT_FALSE(RangeHasOverflowHigh);
2230 EXPECT_FALSE(RangeHasNoOverflow);
2231 break;
2232 case ConstantRange::OverflowResult::AlwaysOverflowsHigh:
2233 EXPECT_TRUE(RangeHasOverflowHigh);
2234 EXPECT_FALSE(RangeHasOverflowLow);
2235 EXPECT_FALSE(RangeHasNoOverflow);
2236 break;
2237 case ConstantRange::OverflowResult::NeverOverflows:
2238 EXPECT_FALSE(RangeHasOverflowLow);
2239 EXPECT_FALSE(RangeHasOverflowHigh);
2240 EXPECT_TRUE(RangeHasNoOverflow);
2241 break;
2242 case ConstantRange::OverflowResult::MayOverflow:
2243 // We return MayOverflow for empty sets as a conservative result,
2244 // but of course neither the RangeHasOverflow nor the
2245 // RangeHasNoOverflow flags will be set.
2246 if (CR1.isEmptySet() || CR2.isEmptySet())
2247 break;
2248
2249 EXPECT_TRUE(RangeHasOverflowLow || RangeHasOverflowHigh);
2250 EXPECT_TRUE(RangeHasNoOverflow);
2251 break;
2252 }
2253 });
2254 }
2255
2256 TEST_F(ConstantRangeTest, UnsignedAddOverflowExhaustive) {
2257 TestOverflowExhaustive(
2258 [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
2259 bool Overflow;
2260 (void) N1.uadd_ov(N2, Overflow);
2261 IsOverflowHigh = true;
2262 return Overflow;
2263 },
2264 [](const ConstantRange &CR1, const ConstantRange &CR2) {
2265 return CR1.unsignedAddMayOverflow(CR2);
2266 });
2267 }
2268
2269 TEST_F(ConstantRangeTest, UnsignedSubOverflowExhaustive) {
2270 TestOverflowExhaustive(
2271 [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
2272 bool Overflow;
2273 (void) N1.usub_ov(N2, Overflow);
2274 IsOverflowHigh = false;
2275 return Overflow;
2276 },
2277 [](const ConstantRange &CR1, const ConstantRange &CR2) {
2278 return CR1.unsignedSubMayOverflow(CR2);
2279 });
2280 }
2281
2282 TEST_F(ConstantRangeTest, UnsignedMulOverflowExhaustive) {
2283 TestOverflowExhaustive(
2284 [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
2285 bool Overflow;
2286 (void) N1.umul_ov(N2, Overflow);
2287 IsOverflowHigh = true;
2288 return Overflow;
2289 },
2290 [](const ConstantRange &CR1, const ConstantRange &CR2) {
2291 return CR1.unsignedMulMayOverflow(CR2);
2292 });
2293 }
2294
2295 TEST_F(ConstantRangeTest, SignedAddOverflowExhaustive) {
2296 TestOverflowExhaustive(
2297 [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
2298 bool Overflow;
2299 (void) N1.sadd_ov(N2, Overflow);
2300 IsOverflowHigh = N1.isNonNegative();
2301 return Overflow;
2302 },
2303 [](const ConstantRange &CR1, const ConstantRange &CR2) {
2304 return CR1.signedAddMayOverflow(CR2);
2305 });
2306 }
2307
2308 TEST_F(ConstantRangeTest, SignedSubOverflowExhaustive) {
2309 TestOverflowExhaustive(
2310 [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
2311 bool Overflow;
2312 (void) N1.ssub_ov(N2, Overflow);
2313 IsOverflowHigh = N1.isNonNegative();
2314 return Overflow;
2315 },
2316 [](const ConstantRange &CR1, const ConstantRange &CR2) {
2317 return CR1.signedSubMayOverflow(CR2);
2318 });
2319 }
2320
2321 TEST_F(ConstantRangeTest, FromKnownBits) {
2322 KnownBits Unknown(16);
2323 EXPECT_EQ(Full, ConstantRange::fromKnownBits(Unknown, /*signed*/false));
2324 EXPECT_EQ(Full, ConstantRange::fromKnownBits(Unknown, /*signed*/true));
2325
2326 // .10..01. -> unsigned 01000010 (66) to 11011011 (219)
2327 // -> signed 11000010 (194) to 01011011 (91)
2328 KnownBits Known(8);
2329 Known.Zero = 36;
2330 Known.One = 66;
2331 ConstantRange Unsigned(APInt(8, 66), APInt(8, 219 + 1));
2332 ConstantRange Signed(APInt(8, 194), APInt(8, 91 + 1));
2333 EXPECT_EQ(Unsigned, ConstantRange::fromKnownBits(Known, /*signed*/false));
2334 EXPECT_EQ(Signed, ConstantRange::fromKnownBits(Known, /*signed*/true));
2335
2336 // 1.10.10. -> 10100100 (164) to 11101101 (237)
2337 Known.Zero = 18;
2338 Known.One = 164;
2339 ConstantRange CR1(APInt(8, 164), APInt(8, 237 + 1));
2340 EXPECT_EQ(CR1, ConstantRange::fromKnownBits(Known, /*signed*/false));
2341 EXPECT_EQ(CR1, ConstantRange::fromKnownBits(Known, /*signed*/true));
2342
2343 // 01.0.1.0 -> 01000100 (68) to 01101110 (110)
2344 Known.Zero = 145;
2345 Known.One = 68;
2346 ConstantRange CR2(APInt(8, 68), APInt(8, 110 + 1));
2347 EXPECT_EQ(CR2, ConstantRange::fromKnownBits(Known, /*signed*/false));
2348 EXPECT_EQ(CR2, ConstantRange::fromKnownBits(Known, /*signed*/true));
2349 }
2350
2351 TEST_F(ConstantRangeTest, FromKnownBitsExhaustive) {
2352 unsigned Bits = 4;
2353 unsigned Max = 1 << Bits;
2354 KnownBits Known(Bits);
2355 for (unsigned Zero = 0; Zero < Max; ++Zero) {
2356 for (unsigned One = 0; One < Max; ++One) {
2357 Known.Zero = Zero;
2358 Known.One = One;
2359 if (Known.hasConflict() || Known.isUnknown())
2360 continue;
2361
2362 SmallBitVector Elems(1 << Bits);
2363 for (unsigned N = 0; N < Max; ++N) {
2364 APInt Num(Bits, N);
2365 if ((Num & Known.Zero) != 0 || (~Num & Known.One) != 0)
2366 continue;
2367 Elems.set(Num.getZExtValue());
2368 }
2369
2370 TestRange(ConstantRange::fromKnownBits(Known, false),
2371 Elems, PreferSmallestUnsigned, {});
2372 TestRange(ConstantRange::fromKnownBits(Known, true),
2373 Elems, PreferSmallestSigned, {});
2374 }
2375 }
2376 }
2377
2378 TEST_F(ConstantRangeTest, ToKnownBits) {
2379 EnumerateInterestingConstantRanges([&](const ConstantRange &CR) {
2380 KnownBits Known = CR.toKnownBits();
2381 KnownBits ExpectedKnown(CR.getBitWidth());
2382 ExpectedKnown.Zero.setAllBits();
2383 ExpectedKnown.One.setAllBits();
2384 ForeachNumInConstantRange(CR, [&](const APInt &N) {
2385 ExpectedKnown.One &= N;
2386 ExpectedKnown.Zero &= ~N;
2387 });
2388 // For an empty CR any result would be legal.
2389 if (!CR.isEmptySet()) {
2390 EXPECT_EQ(ExpectedKnown, Known);
2391 }
2392 });
2393 }
2394
2395 TEST_F(ConstantRangeTest, Negative) {
2396 // All elements in an empty set (of which there are none) are both negative
2397 // and non-negative. Empty & full sets checked explicitly for clarity, but
2398 // they are also covered by the exhaustive test below.
2399 EXPECT_TRUE(Empty.isAllNegative());
2400 EXPECT_TRUE(Empty.isAllNonNegative());
2401 EXPECT_TRUE(Empty.isAllPositive());
2402 EXPECT_FALSE(Full.isAllNegative());
2403 EXPECT_FALSE(Full.isAllNonNegative());
2404 EXPECT_FALSE(Full.isAllPositive());
2405
2406 EnumerateInterestingConstantRanges([](const ConstantRange &CR) {
2407 bool AllNegative = true;
2408 bool AllNonNegative = true;
2409 bool AllPositive = true;
2410 ForeachNumInConstantRange(CR, [&](const APInt &N) {
2411 if (!N.isNegative())
2412 AllNegative = false;
2413 if (!N.isNonNegative())
2414 AllNonNegative = false;
2415 if (!N.isStrictlyPositive())
2416 AllPositive = false;
2417 });
2418 assert(
2419 (CR.isEmptySet() || !AllNegative || !AllNonNegative || !AllPositive) &&
2420 "Only empty set can be all negative, all non-negative, and all "
2421 "positive");
2422
2423 EXPECT_EQ(AllNegative, CR.isAllNegative());
2424 EXPECT_EQ(AllNonNegative, CR.isAllNonNegative());
2425 EXPECT_EQ(AllPositive, CR.isAllPositive());
2426 });
2427 }
2428
2429 TEST_F(ConstantRangeTest, UAddSat) {
2430 TestBinaryOpExhaustive(
2431 [](const ConstantRange &CR1, const ConstantRange &CR2) {
2432 return CR1.uadd_sat(CR2);
2433 },
2434 [](const APInt &N1, const APInt &N2) {
2435 return N1.uadd_sat(N2);
2436 },
2437 PreferSmallestUnsigned);
2438 }
2439
2440 TEST_F(ConstantRangeTest, USubSat) {
2441 TestBinaryOpExhaustive(
2442 [](const ConstantRange &CR1, const ConstantRange &CR2) {
2443 return CR1.usub_sat(CR2);
2444 },
2445 [](const APInt &N1, const APInt &N2) {
2446 return N1.usub_sat(N2);
2447 },
2448 PreferSmallestUnsigned);
2449 }
2450
2451 TEST_F(ConstantRangeTest, UMulSat) {
2452 TestBinaryOpExhaustive(
2453 [](const ConstantRange &CR1, const ConstantRange &CR2) {
2454 return CR1.umul_sat(CR2);
2455 },
2456 [](const APInt &N1, const APInt &N2) { return N1.umul_sat(N2); },
2457 PreferSmallestUnsigned);
2458 }
2459
2460 TEST_F(ConstantRangeTest, UShlSat) {
2461 TestBinaryOpExhaustive(
2462 [](const ConstantRange &CR1, const ConstantRange &CR2) {
2463 return CR1.ushl_sat(CR2);
2464 },
2465 [](const APInt &N1, const APInt &N2) { return N1.ushl_sat(N2); },
2466 PreferSmallestUnsigned);
2467 }
2468
2469 TEST_F(ConstantRangeTest, SAddSat) {
2470 TestBinaryOpExhaustive(
2471 [](const ConstantRange &CR1, const ConstantRange &CR2) {
2472 return CR1.sadd_sat(CR2);
2473 },
2474 [](const APInt &N1, const APInt &N2) {
2475 return N1.sadd_sat(N2);
2476 },
2477 PreferSmallestSigned);
2478 }
2479
2480 TEST_F(ConstantRangeTest, SSubSat) {
2481 TestBinaryOpExhaustive(
2482 [](const ConstantRange &CR1, const ConstantRange &CR2) {
2483 return CR1.ssub_sat(CR2);
2484 },
2485 [](const APInt &N1, const APInt &N2) {
2486 return N1.ssub_sat(N2);
2487 },
2488 PreferSmallestSigned);
2489 }
2490
2491 TEST_F(ConstantRangeTest, SMulSat) {
2492 TestBinaryOpExhaustive(
2493 [](const ConstantRange &CR1, const ConstantRange &CR2) {
2494 return CR1.smul_sat(CR2);
2495 },
2496 [](const APInt &N1, const APInt &N2) { return N1.smul_sat(N2); },
2497 PreferSmallestSigned);
2498 }
2499
2500 TEST_F(ConstantRangeTest, SShlSat) {
2501 TestBinaryOpExhaustive(
2502 [](const ConstantRange &CR1, const ConstantRange &CR2) {
2503 return CR1.sshl_sat(CR2);
2504 },
2505 [](const APInt &N1, const APInt &N2) { return N1.sshl_sat(N2); },
2506 PreferSmallestSigned);
2507 }
2508
2509 TEST_F(ConstantRangeTest, Abs) {
2510 TestUnaryOpExhaustive(
2511 [](const ConstantRange &CR) { return CR.abs(); },
2512 [](const APInt &N) { return N.abs(); });
2513
2514 TestUnaryOpExhaustive(
2515 [](const ConstantRange &CR) { return CR.abs(/*IntMinIsPoison=*/true); },
2516 [](const APInt &N) -> std::optional<APInt> {
2517 if (N.isMinSignedValue())
2518 return std::nullopt;
2519 return N.abs();
2520 });
2521 }
2522
2523 TEST_F(ConstantRangeTest, Ctlz) {
2524 TestUnaryOpExhaustive(
2525 [](const ConstantRange &CR) { return CR.ctlz(); },
2526 [](const APInt &N) { return APInt(N.getBitWidth(), N.countl_zero()); });
2527
2528 TestUnaryOpExhaustive(
2529 [](const ConstantRange &CR) { return CR.ctlz(/*ZeroIsPoison=*/true); },
2530 [](const APInt &N) -> std::optional<APInt> {
2531 if (N.isZero())
2532 return std::nullopt;
2533 return APInt(N.getBitWidth(), N.countl_zero());
2534 });
2535 }
2536
2537 TEST_F(ConstantRangeTest, Cttz) {
2538 TestUnaryOpExhaustive(
2539 [](const ConstantRange &CR) { return CR.cttz(); },
2540 [](const APInt &N) { return APInt(N.getBitWidth(), N.countr_zero()); });
2541
2542 TestUnaryOpExhaustive(
2543 [](const ConstantRange &CR) { return CR.cttz(/*ZeroIsPoison=*/true); },
2544 [](const APInt &N) -> std::optional<APInt> {
2545 if (N.isZero())
2546 return std::nullopt;
2547 return APInt(N.getBitWidth(), N.countr_zero());
2548 });
2549 }
2550
2551 TEST_F(ConstantRangeTest, Ctpop) {
2552 TestUnaryOpExhaustive(
2553 [](const ConstantRange &CR) { return CR.ctpop(); },
2554 [](const APInt &N) { return APInt(N.getBitWidth(), N.popcount()); });
2555 }
2556
2557 TEST_F(ConstantRangeTest, castOps) {
2558 ConstantRange A(APInt(16, 66), APInt(16, 128));
2559 ConstantRange FpToI8 = A.castOp(Instruction::FPToSI, 8);
2560 EXPECT_EQ(8u, FpToI8.getBitWidth());
2561 EXPECT_TRUE(FpToI8.isFullSet());
2562
2563 ConstantRange FpToI16 = A.castOp(Instruction::FPToSI, 16);
2564 EXPECT_EQ(16u, FpToI16.getBitWidth());
2565 EXPECT_EQ(A, FpToI16);
2566
2567 ConstantRange FPExtToDouble = A.castOp(Instruction::FPExt, 64);
2568 EXPECT_EQ(64u, FPExtToDouble.getBitWidth());
2569 EXPECT_TRUE(FPExtToDouble.isFullSet());
2570
2571 ConstantRange PtrToInt = A.castOp(Instruction::PtrToInt, 64);
2572 EXPECT_EQ(64u, PtrToInt.getBitWidth());
2573 EXPECT_TRUE(PtrToInt.isFullSet());
2574
2575 ConstantRange IntToPtr = A.castOp(Instruction::IntToPtr, 64);
2576 EXPECT_EQ(64u, IntToPtr.getBitWidth());
2577 EXPECT_TRUE(IntToPtr.isFullSet());
2578
2579 ConstantRange UIToFP = A.castOp(Instruction::UIToFP, 16);
2580 EXPECT_EQ(16u, UIToFP.getBitWidth());
2581 EXPECT_TRUE(UIToFP.isFullSet());
2582
2583 ConstantRange UIToFP2 = A.castOp(Instruction::UIToFP, 64);
2584 ConstantRange B(APInt(64, 0), APInt(64, 65536));
2585 EXPECT_EQ(64u, UIToFP2.getBitWidth());
2586 EXPECT_EQ(B, UIToFP2);
2587
2588 ConstantRange SIToFP = A.castOp(Instruction::SIToFP, 16);
2589 EXPECT_EQ(16u, SIToFP.getBitWidth());
2590 EXPECT_TRUE(SIToFP.isFullSet());
2591
2592 ConstantRange SIToFP2 = A.castOp(Instruction::SIToFP, 64);
2593 ConstantRange C(APInt(64, -32768), APInt(64, 32768));
2594 EXPECT_EQ(64u, SIToFP2.getBitWidth());
2595 EXPECT_EQ(C, SIToFP2);
2596 }
2597
2598 TEST_F(ConstantRangeTest, binaryAnd) {
2599 // Single element ranges.
2600 ConstantRange R16(APInt(8, 16));
2601 ConstantRange R20(APInt(8, 20));
2602 EXPECT_EQ(*R16.binaryAnd(R16).getSingleElement(), APInt(8, 16));
2603 EXPECT_EQ(*R16.binaryAnd(R20).getSingleElement(), APInt(8, 16 & 20));
2604
2605 ConstantRange R16_32(APInt(8, 16), APInt(8, 32));
2606 // 'And' with a high bits mask.
2607 ConstantRange R32(APInt(8, 32));
2608 EXPECT_TRUE(R16_32.binaryAnd(R32).getSingleElement()->isZero());
2609 EXPECT_TRUE(R32.binaryAnd(R16_32).getSingleElement()->isZero());
2610 // 'And' with a low bits mask. Handled conservatively for now.
2611 ConstantRange R4(APInt(8, 4));
2612 ConstantRange R0_5(APInt(8, 0), APInt(8, 5));
2613 EXPECT_EQ(R16_32.binaryAnd(R4), R0_5);
2614 EXPECT_EQ(R4.binaryAnd(R16_32), R0_5);
2615
2616 // Ranges with more than one element. Handled conservatively for now.
2617 ConstantRange R0_99(APInt(8, 0), APInt(8, 99));
2618 ConstantRange R0_32(APInt(8, 0), APInt(8, 32));
2619 EXPECT_EQ(R16_32.binaryAnd(R0_99), R0_32);
2620 EXPECT_EQ(R0_99.binaryAnd(R16_32), R0_32);
2621
2622 TestBinaryOpExhaustive(
2623 [](const ConstantRange &CR1, const ConstantRange &CR2) {
2624 return CR1.binaryAnd(CR2);
2625 },
2626 [](const APInt &N1, const APInt &N2) { return N1 & N2; }, PreferSmallest,
2627 CheckSingleElementsOnly);
2628 }
2629
2630 TEST_F(ConstantRangeTest, binaryOr) {
2631 // Single element ranges.
2632 ConstantRange R16(APInt(8, 16));
2633 ConstantRange R20(APInt(8, 20));
2634 EXPECT_EQ(*R16.binaryOr(R16).getSingleElement(), APInt(8, 16));
2635 EXPECT_EQ(*R16.binaryOr(R20).getSingleElement(), APInt(8, 16 | 20));
2636
2637 ConstantRange R16_32(APInt(8, 16), APInt(8, 32));
2638 // 'Or' with a high bits mask.
2639 // KnownBits estimate is important, otherwise the maximum included element
2640 // would be 2^8 - 1.
2641 ConstantRange R32(APInt(8, 32));
2642 ConstantRange R48_64(APInt(8, 48), APInt(8, 64));
2643 EXPECT_EQ(R16_32.binaryOr(R32), R48_64);
2644 EXPECT_EQ(R32.binaryOr(R16_32), R48_64);
2645 // 'Or' with a low bits mask.
2646 ConstantRange R4(APInt(8, 4));
2647 ConstantRange R0_16(APInt(8, 0), APInt(8, 16));
2648 ConstantRange R4_16(APInt(8, 4), APInt(8, 16));
2649 EXPECT_EQ(R0_16.binaryOr(R4), R4_16);
2650 EXPECT_EQ(R4.binaryOr(R0_16), R4_16);
2651
2652 // Ranges with more than one element. Handled conservatively for now.
2653 // UMaxUMin estimate is important, otherwise the lower bound would be zero.
2654 ConstantRange R0_64(APInt(8, 0), APInt(8, 64));
2655 ConstantRange R5_32(APInt(8, 5), APInt(8, 32));
2656 ConstantRange R5_64(APInt(8, 5), APInt(8, 64));
2657 EXPECT_EQ(R0_64.binaryOr(R5_32), R5_64);
2658 EXPECT_EQ(R5_32.binaryOr(R0_64), R5_64);
2659
2660 TestBinaryOpExhaustive(
2661 [](const ConstantRange &CR1, const ConstantRange &CR2) {
2662 return CR1.binaryOr(CR2);
2663 },
2664 [](const APInt &N1, const APInt &N2) { return N1 | N2; }, PreferSmallest,
2665 CheckSingleElementsOnly);
2666 }
2667
2668 TEST_F(ConstantRangeTest, binaryXor) {
2669 // Single element ranges.
2670 ConstantRange R16(APInt(8, 16));
2671 ConstantRange R20(APInt(8, 20));
2672 EXPECT_EQ(*R16.binaryXor(R16).getSingleElement(), APInt(8, 0));
2673 EXPECT_EQ(*R16.binaryXor(R20).getSingleElement(), APInt(8, 16 ^ 20));
2674
2675 // Ranges with more than a single element.
2676 ConstantRange R16_35(APInt(8, 16), APInt(8, 35));
2677 ConstantRange R0_99(APInt(8, 0), APInt(8, 99));
2678 EXPECT_EQ(R16_35.binaryXor(R16_35), ConstantRange(APInt(8, 0), APInt(8, 64)));
2679 EXPECT_EQ(R16_35.binaryXor(R0_99), ConstantRange(APInt(8, 0), APInt(8, 128)));
2680 EXPECT_EQ(R0_99.binaryXor(R16_35), ConstantRange(APInt(8, 0), APInt(8, 128)));
2681
2682 // Treat xor A, B as sub nsw nuw A, B
2683 ConstantRange R0_51(APInt(8, 0), APInt(8, 51));
2684 ConstantRange R63(APInt(8, 63));
2685 EXPECT_EQ(R0_51.binaryXor(R63), ConstantRange(APInt(8, 13), APInt(8, 64)));
2686 EXPECT_EQ(R63.binaryXor(R0_51), ConstantRange(APInt(8, 13), APInt(8, 64)));
2687
2688 TestBinaryOpExhaustive(
2689 [](const ConstantRange &CR1, const ConstantRange &CR2) {
2690 return CR1.binaryXor(CR2);
2691 },
2692 [](const APInt &N1, const APInt &N2) {
2693 return N1 ^ N2;
2694 },
2695 PreferSmallest,
2696 CheckSingleElementsOnly);
2697 }
2698
2699 TEST_F(ConstantRangeTest, binaryNot) {
2700 TestUnaryOpExhaustive(
2701 [](const ConstantRange &CR) { return CR.binaryNot(); },
2702 [](const APInt &N) { return ~N; },
2703 PreferSmallest);
2704 TestUnaryOpExhaustive(
2705 [](const ConstantRange &CR) {
2706 return CR.binaryXor(ConstantRange(APInt::getAllOnes(CR.getBitWidth())));
2707 },
2708 [](const APInt &N) { return ~N; }, PreferSmallest);
2709 TestUnaryOpExhaustive(
2710 [](const ConstantRange &CR) {
2711 return ConstantRange(APInt::getAllOnes(CR.getBitWidth())).binaryXor(CR);
2712 },
2713 [](const APInt &N) { return ~N; }, PreferSmallest);
2714 }
2715
2716 template <typename T>
2717 void testConstantRangeICmpPredEquivalence(ICmpInst::Predicate SrcPred, T Func) {
2718 EnumerateTwoInterestingConstantRanges(
2719 [&](const ConstantRange &CR1, const ConstantRange &CR2) {
2720 ICmpInst::Predicate TgtPred;
2721 bool ExpectedEquivalent;
2722 std::tie(TgtPred, ExpectedEquivalent) = Func(CR1, CR2);
2723 if (TgtPred == CmpInst::Predicate::BAD_ICMP_PREDICATE)
2724 return;
2725 bool TrulyEquivalent = true;
2726 ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
2727 if (!TrulyEquivalent)
2728 return;
2729 ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
2730 if (!TrulyEquivalent)
2731 return;
2732 TrulyEquivalent &= ICmpInst::compare(N1, N2, SrcPred) ==
2733 ICmpInst::compare(N1, N2, TgtPred);
2734 });
2735 });
2736 ASSERT_EQ(TrulyEquivalent, ExpectedEquivalent);
2737 });
2738 }
2739
2740 TEST_F(ConstantRangeTest, areInsensitiveToSignednessOfICmpPredicate) {
2741 for (auto Pred : ICmpInst::predicates()) {
2742 if (ICmpInst::isEquality(Pred))
2743 continue;
2744 ICmpInst::Predicate FlippedSignednessPred =
2745 ICmpInst::getFlippedSignednessPredicate(Pred);
2746 testConstantRangeICmpPredEquivalence(Pred, [FlippedSignednessPred](
2747 const ConstantRange &CR1,
2748 const ConstantRange &CR2) {
2749 return std::make_pair(
2750 FlippedSignednessPred,
2751 ConstantRange::areInsensitiveToSignednessOfICmpPredicate(CR1, CR2));
2752 });
2753 }
2754 }
2755
2756 TEST_F(ConstantRangeTest, areInsensitiveToSignednessOfInvertedICmpPredicate) {
2757 for (auto Pred : ICmpInst::predicates()) {
2758 if (ICmpInst::isEquality(Pred))
2759 continue;
2760 ICmpInst::Predicate InvertedFlippedSignednessPred =
2761 ICmpInst::getInversePredicate(
2762 ICmpInst::getFlippedSignednessPredicate(Pred));
2763 testConstantRangeICmpPredEquivalence(
2764 Pred, [InvertedFlippedSignednessPred](const ConstantRange &CR1,
2765 const ConstantRange &CR2) {
2766 return std::make_pair(
2767 InvertedFlippedSignednessPred,
2768 ConstantRange::areInsensitiveToSignednessOfInvertedICmpPredicate(
2769 CR1, CR2));
2770 });
2771 }
2772 }
2773
2774 TEST_F(ConstantRangeTest, getEquivalentPredWithFlippedSignedness) {
2775 for (auto Pred : ICmpInst::predicates()) {
2776 if (ICmpInst::isEquality(Pred))
2777 continue;
2778 testConstantRangeICmpPredEquivalence(
2779 Pred, [Pred](const ConstantRange &CR1, const ConstantRange &CR2) {
2780 return std::make_pair(
2781 ConstantRange::getEquivalentPredWithFlippedSignedness(Pred, CR1,
2782 CR2),
2783 /*ExpectedEquivalent=*/true);
2784 });
2785 }
2786 }
2787
2788 TEST_F(ConstantRangeTest, isSizeLargerThan) {
2789 EXPECT_FALSE(Empty.isSizeLargerThan(0));
2790
2791 EXPECT_TRUE(Full.isSizeLargerThan(0));
2792 EXPECT_TRUE(Full.isSizeLargerThan(65535));
2793 EXPECT_FALSE(Full.isSizeLargerThan(65536));
2794
2795 EXPECT_TRUE(One.isSizeLargerThan(0));
2796 EXPECT_FALSE(One.isSizeLargerThan(1));
2797 }
2798
2799 TEST_F(ConstantRangeTest, MakeMaskNotEqualRange) {
2800 // Mask: 0b0001, C: 0b0001. MMNE() = [2, 1)
2801 ConstantRange CR(APInt(4, 2), APInt(4, 1));
2802 EXPECT_EQ(CR, ConstantRange::makeMaskNotEqualRange(APInt(4, 1), APInt(4, 1)));
2803 EXPECT_NE(CR, ConstantRange::makeMaskNotEqualRange(APInt(4, 0),
2804 APInt(4, -1, true)));
2805 EXPECT_TRUE(CR.contains(APInt(4, 7)));
2806 EXPECT_TRUE(CR.contains(APInt(4, 15)));
2807
2808 // Mask: 0b0100, C: 0b0100. MMNE() = [-8, 4)
2809 ConstantRange CR2(APInt(4, -8, true), APInt(4, 4));
2810 auto MMNE = ConstantRange::makeMaskNotEqualRange(APInt(4, 4), APInt(4, 4));
2811 EXPECT_EQ(CR2, MMNE);
2812 EXPECT_NE(ConstantRange::getNonEmpty(APInt(4, 0), APInt(4, -4, true)), MMNE);
2813
2814 // CR: [-16, -8). MMNE() = [-8, -16)
2815 ConstantRange CR3(APInt(8, 240), APInt(8, 248));
2816 EXPECT_EQ(CR3.inverse(),
2817 ConstantRange::makeMaskNotEqualRange(APInt(8, 248), APInt(8, 240)));
2818
2819 // Mask: 0, C: 0b1111: unsatisfiable.
2820 EXPECT_EQ(ConstantRange::getFull(4),
2821 ConstantRange::makeMaskNotEqualRange(APInt(4, 0), APInt(4, 15)));
2822 }
2823
2824 TEST_F(ConstantRangeTest, MakeMaskNotEqualRangeExhaustive) {
2825 unsigned Bits = 4;
2826 unsigned Max = 1 << Bits;
2827
2828 EnumerateAPInts(Bits, [&](const APInt &Mask) {
2829 EnumerateAPInts(Bits, [&](const APInt &C) {
2830 SmallBitVector Elems(Max);
2831 for (unsigned N = 0; N < Max; ++N) {
2832 APInt Num(Bits, N);
2833 if ((Num & Mask) == C)
2834 continue;
2835 Elems.set(Num.getZExtValue());
2836 }
2837
2838 // Only test optimality with PreferSmallest. E.g., given Mask = 0b0001, C
2839 // = 0b0001, a possible better range would be [0, 15) when preferring the
2840 // smallest unsigned, however we conservatively return [2, 1).
2841 TestRange(ConstantRange::makeMaskNotEqualRange(Mask, C), Elems,
2842 PreferSmallest, {});
2843 });
2844 });
2845 }
2846
2847 } // anonymous namespace
LLVM monorepo