Debian Codegraph @

llvm-project/llvm/unittests/IR/ConstantRangeTest.cpp

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