?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Run DCE after a LoopFlatten test to reduce spurious output [nfc]
[llvm-project.git] / llvm / unittests / IR / ConstantRangeTest.cpp
blob1cb358a26062ca59db6d3980de72c00c3fed1ed9
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.getSignificantBits());
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 // Multiplication by -1 should give precise results.
1002 EXPECT_EQ(ConstantRange(APInt(8, 3), APInt(8, -11))
1003 .multiply(ConstantRange(APInt(8, -1))),
1004 ConstantRange(APInt(8, 12), APInt(8, -2)));
1005 EXPECT_EQ(ConstantRange(APInt(8, -1))
1006 .multiply(ConstantRange(APInt(8, 3), APInt(8, -11))),
1007 ConstantRange(APInt(8, 12), APInt(8, -2)));
1008
1009 TestBinaryOpExhaustive(
1010 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1011 return CR1.multiply(CR2);
1012 },
1013 [](const APInt &N1, const APInt &N2) {
1014 return N1 * N2;
1015 },
1016 PreferSmallest,
1017 [](const ConstantRange &, const ConstantRange &) {
1018 return false; // Check correctness only.
1019 });
1020 }
1021
1022 TEST_F(ConstantRangeTest, smul_fast) {
1023 TestBinaryOpExhaustive(
1024 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1025 return CR1.smul_fast(CR2);
1026 },
1027 [](const APInt &N1, const APInt &N2) {
1028 return N1 * N2;
1029 },
1030 PreferSmallest,
1031 [](const ConstantRange &, const ConstantRange &) {
1032 return false; // Check correctness only.
1033 });
1034 }
1035
1036 TEST_F(ConstantRangeTest, UMax) {
1037 EXPECT_EQ(Full.umax(Full), Full);
1038 EXPECT_EQ(Full.umax(Empty), Empty);
1039 EXPECT_EQ(Full.umax(Some), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
1040 EXPECT_EQ(Full.umax(Wrap), Full);
1041 EXPECT_EQ(Full.umax(Some), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
1042 EXPECT_EQ(Empty.umax(Empty), Empty);
1043 EXPECT_EQ(Empty.umax(Some), Empty);
1044 EXPECT_EQ(Empty.umax(Wrap), Empty);
1045 EXPECT_EQ(Empty.umax(One), Empty);
1046 EXPECT_EQ(Some.umax(Some), Some);
1047 EXPECT_EQ(Some.umax(Wrap), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
1048 EXPECT_EQ(Some.umax(One), Some);
1049 EXPECT_EQ(Wrap.umax(Wrap), Wrap);
1050 EXPECT_EQ(Wrap.umax(One), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
1051 EXPECT_EQ(One.umax(One), One);
1052
1053 TestBinaryOpExhaustive(
1054 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1055 return CR1.umax(CR2);
1056 },
1057 [](const APInt &N1, const APInt &N2) {
1058 return APIntOps::umax(N1, N2);
1059 },
1060 PreferSmallestNonFullUnsigned);
1061 }
1062
1063 TEST_F(ConstantRangeTest, SMax) {
1064 EXPECT_EQ(Full.smax(Full), Full);
1065 EXPECT_EQ(Full.smax(Empty), Empty);
1066 EXPECT_EQ(Full.smax(Some), ConstantRange(APInt(16, 0xa),
1067 APInt::getSignedMinValue(16)));
1068 EXPECT_EQ(Full.smax(Wrap), Full);
1069 EXPECT_EQ(Full.smax(One), ConstantRange(APInt(16, 0xa),
1070 APInt::getSignedMinValue(16)));
1071 EXPECT_EQ(Empty.smax(Empty), Empty);
1072 EXPECT_EQ(Empty.smax(Some), Empty);
1073 EXPECT_EQ(Empty.smax(Wrap), Empty);
1074 EXPECT_EQ(Empty.smax(One), Empty);
1075 EXPECT_EQ(Some.smax(Some), Some);
1076 EXPECT_EQ(Some.smax(Wrap), ConstantRange(APInt(16, 0xa),
1077 APInt(16, (uint64_t)INT16_MIN)));
1078 EXPECT_EQ(Some.smax(One), Some);
1079 EXPECT_EQ(Wrap.smax(One), ConstantRange(APInt(16, 0xa),
1080 APInt(16, (uint64_t)INT16_MIN)));
1081 EXPECT_EQ(One.smax(One), One);
1082
1083 TestBinaryOpExhaustive(
1084 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1085 return CR1.smax(CR2);
1086 },
1087 [](const APInt &N1, const APInt &N2) {
1088 return APIntOps::smax(N1, N2);
1089 },
1090 PreferSmallestNonFullSigned);
1091 }
1092
1093 TEST_F(ConstantRangeTest, UMin) {
1094 EXPECT_EQ(Full.umin(Full), Full);
1095 EXPECT_EQ(Full.umin(Empty), Empty);
1096 EXPECT_EQ(Full.umin(Some), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
1097 EXPECT_EQ(Full.umin(Wrap), Full);
1098 EXPECT_EQ(Empty.umin(Empty), Empty);
1099 EXPECT_EQ(Empty.umin(Some), Empty);
1100 EXPECT_EQ(Empty.umin(Wrap), Empty);
1101 EXPECT_EQ(Empty.umin(One), Empty);
1102 EXPECT_EQ(Some.umin(Some), Some);
1103 EXPECT_EQ(Some.umin(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
1104 EXPECT_EQ(Some.umin(One), One);
1105 EXPECT_EQ(Wrap.umin(Wrap), Wrap);
1106 EXPECT_EQ(Wrap.umin(One), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
1107 EXPECT_EQ(One.umin(One), One);
1108
1109 TestBinaryOpExhaustive(
1110 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1111 return CR1.umin(CR2);
1112 },
1113 [](const APInt &N1, const APInt &N2) {
1114 return APIntOps::umin(N1, N2);
1115 },
1116 PreferSmallestNonFullUnsigned);
1117 }
1118
1119 TEST_F(ConstantRangeTest, SMin) {
1120 EXPECT_EQ(Full.smin(Full), Full);
1121 EXPECT_EQ(Full.smin(Empty), Empty);
1122 EXPECT_EQ(Full.smin(Some), ConstantRange(APInt(16, (uint64_t)INT16_MIN),
1123 APInt(16, 0xaaa)));
1124 EXPECT_EQ(Full.smin(Wrap), Full);
1125 EXPECT_EQ(Empty.smin(Empty), Empty);
1126 EXPECT_EQ(Empty.smin(Some), Empty);
1127 EXPECT_EQ(Empty.smin(Wrap), Empty);
1128 EXPECT_EQ(Empty.smin(One), Empty);
1129 EXPECT_EQ(Some.smin(Some), Some);
1130 EXPECT_EQ(Some.smin(Wrap), ConstantRange(APInt(16, (uint64_t)INT16_MIN),
1131 APInt(16, 0xaaa)));
1132 EXPECT_EQ(Some.smin(One), One);
1133 EXPECT_EQ(Wrap.smin(Wrap), Wrap);
1134 EXPECT_EQ(Wrap.smin(One), ConstantRange(APInt(16, (uint64_t)INT16_MIN),
1135 APInt(16, 0xb)));
1136 EXPECT_EQ(One.smin(One), One);
1137
1138 TestBinaryOpExhaustive(
1139 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1140 return CR1.smin(CR2);
1141 },
1142 [](const APInt &N1, const APInt &N2) {
1143 return APIntOps::smin(N1, N2);
1144 },
1145 PreferSmallestNonFullSigned);
1146 }
1147
1148 TEST_F(ConstantRangeTest, UDiv) {
1149 EXPECT_EQ(Full.udiv(Full), Full);
1150 EXPECT_EQ(Full.udiv(Empty), Empty);
1151 EXPECT_EQ(Full.udiv(One), ConstantRange(APInt(16, 0),
1152 APInt(16, 0xffff / 0xa + 1)));
1153 EXPECT_EQ(Full.udiv(Some), ConstantRange(APInt(16, 0),
1154 APInt(16, 0xffff / 0xa + 1)));
1155 EXPECT_EQ(Full.udiv(Wrap), Full);
1156 EXPECT_EQ(Empty.udiv(Empty), Empty);
1157 EXPECT_EQ(Empty.udiv(One), Empty);
1158 EXPECT_EQ(Empty.udiv(Some), Empty);
1159 EXPECT_EQ(Empty.udiv(Wrap), Empty);
1160 EXPECT_EQ(One.udiv(One), ConstantRange(APInt(16, 1)));
1161 EXPECT_EQ(One.udiv(Some), ConstantRange(APInt(16, 0), APInt(16, 2)));
1162 EXPECT_EQ(One.udiv(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
1163 EXPECT_EQ(Some.udiv(Some), ConstantRange(APInt(16, 0), APInt(16, 0x111)));
1164 EXPECT_EQ(Some.udiv(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
1165 EXPECT_EQ(Wrap.udiv(Wrap), Full);
1166
1167
1168 ConstantRange Zero(APInt(16, 0));
1169 EXPECT_EQ(Zero.udiv(One), Zero);
1170 EXPECT_EQ(Zero.udiv(Full), Zero);
1171
1172 EXPECT_EQ(ConstantRange(APInt(16, 0), APInt(16, 99)).udiv(Full),
1173 ConstantRange(APInt(16, 0), APInt(16, 99)));
1174 EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 99)).udiv(Full),
1175 ConstantRange(APInt(16, 0), APInt(16, 99)));
1176 }
1177
1178 TEST_F(ConstantRangeTest, SDiv) {
1179 ConstantRange OneBit = ConstantRange::getFull(1);
1180 EXPECT_EQ(OneBit.sdiv(OneBit), ConstantRange(APInt(1, 0)));
1181
1182 EnumerateTwoInterestingConstantRanges([&](const ConstantRange &CR1,
1183 const ConstantRange &CR2) {
1184 // Collect possible results in a bit vector. We store the signed value plus
1185 // a bias to make it unsigned.
1186 unsigned Bits = CR1.getBitWidth();
1187 int Bias = 1 << (Bits - 1);
1188 BitVector Results(1 << Bits);
1189 ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
1190 ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
1191 // Division by zero is UB.
1192 if (N2 == 0)
1193 return;
1194
1195 // SignedMin / -1 is UB.
1196 if (N1.isMinSignedValue() && N2.isAllOnes())
1197 return;
1198
1199 APInt N = N1.sdiv(N2);
1200 Results.set(N.getSExtValue() + Bias);
1201 });
1202 });
1203
1204 ConstantRange CR = CR1.sdiv(CR2);
1205 if (Results.none()) {
1206 EXPECT_TRUE(CR.isEmptySet());
1207 return;
1208 }
1209
1210 // If there is a non-full signed envelope, that should be the result.
1211 APInt SMin(Bits, Results.find_first() - Bias);
1212 APInt SMax(Bits, Results.find_last() - Bias);
1213 ConstantRange Envelope = ConstantRange::getNonEmpty(SMin, SMax + 1);
1214 if (!Envelope.isFullSet()) {
1215 EXPECT_EQ(Envelope, CR);
1216 return;
1217 }
1218
1219 // If the signed envelope is a full set, try to find a smaller sign wrapped
1220 // set that is separated in negative and positive components (or one which
1221 // can also additionally contain zero).
1222 int LastNeg = Results.find_last_in(0, Bias) - Bias;
1223 int LastPos = Results.find_next(Bias) - Bias;
1224 if (Results[Bias]) {
1225 if (LastNeg == -1)
1226 ++LastNeg;
1227 else if (LastPos == 1)
1228 --LastPos;
1229 }
1230
1231 APInt WMax(Bits, LastNeg);
1232 APInt WMin(Bits, LastPos);
1233 ConstantRange Wrapped = ConstantRange::getNonEmpty(WMin, WMax + 1);
1234 EXPECT_EQ(Wrapped, CR);
1235 });
1236 }
1237
1238 TEST_F(ConstantRangeTest, URem) {
1239 EXPECT_EQ(Full.urem(Empty), Empty);
1240 EXPECT_EQ(Empty.urem(Full), Empty);
1241 // urem by zero is poison.
1242 EXPECT_EQ(Full.urem(ConstantRange(APInt(16, 0))), Empty);
1243 // urem by full range doesn't contain MaxValue.
1244 EXPECT_EQ(Full.urem(Full), ConstantRange(APInt(16, 0), APInt(16, 0xffff)));
1245 // urem is upper bounded by maximum RHS minus one.
1246 EXPECT_EQ(Full.urem(ConstantRange(APInt(16, 0), APInt(16, 123))),
1247 ConstantRange(APInt(16, 0), APInt(16, 122)));
1248 // urem is upper bounded by maximum LHS.
1249 EXPECT_EQ(ConstantRange(APInt(16, 0), APInt(16, 123)).urem(Full),
1250 ConstantRange(APInt(16, 0), APInt(16, 123)));
1251 // If the LHS is always lower than the RHS, the result is the LHS.
1252 EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 20))
1253 .urem(ConstantRange(APInt(16, 20), APInt(16, 30))),
1254 ConstantRange(APInt(16, 10), APInt(16, 20)));
1255 // It has to be strictly lower, otherwise the top value may wrap to zero.
1256 EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 20))
1257 .urem(ConstantRange(APInt(16, 19), APInt(16, 30))),
1258 ConstantRange(APInt(16, 0), APInt(16, 20)));
1259 // [12, 14] % 10 is [2, 4], but we conservatively compute [0, 9].
1260 EXPECT_EQ(ConstantRange(APInt(16, 12), APInt(16, 15))
1261 .urem(ConstantRange(APInt(16, 10))),
1262 ConstantRange(APInt(16, 0), APInt(16, 10)));
1263
1264 TestBinaryOpExhaustive(
1265 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1266 return CR1.urem(CR2);
1267 },
1268 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
1269 if (N2.isZero())
1270 return std::nullopt;
1271 return N1.urem(N2);
1272 },
1273 PreferSmallest, CheckSingleElementsOnly);
1274 }
1275
1276 TEST_F(ConstantRangeTest, SRem) {
1277 EXPECT_EQ(Full.srem(Empty), Empty);
1278 EXPECT_EQ(Empty.srem(Full), Empty);
1279 // srem by zero is UB.
1280 EXPECT_EQ(Full.srem(ConstantRange(APInt(16, 0))), Empty);
1281 // srem by full range doesn't contain SignedMinValue.
1282 EXPECT_EQ(Full.srem(Full), ConstantRange(APInt::getSignedMinValue(16) + 1,
1283 APInt::getSignedMinValue(16)));
1284
1285 ConstantRange PosMod(APInt(16, 10), APInt(16, 21)); // [10, 20]
1286 ConstantRange NegMod(APInt(16, -20), APInt(16, -9)); // [-20, -10]
1287 ConstantRange IntMinMod(APInt::getSignedMinValue(16));
1288
1289 ConstantRange Expected(16, true);
1290
1291 // srem is bounded by abs(RHS) minus one.
1292 ConstantRange PosLargeLHS(APInt(16, 0), APInt(16, 41));
1293 Expected = ConstantRange(APInt(16, 0), APInt(16, 20));
1294 EXPECT_EQ(PosLargeLHS.srem(PosMod), Expected);
1295 EXPECT_EQ(PosLargeLHS.srem(NegMod), Expected);
1296 ConstantRange NegLargeLHS(APInt(16, -40), APInt(16, 1));
1297 Expected = ConstantRange(APInt(16, -19), APInt(16, 1));
1298 EXPECT_EQ(NegLargeLHS.srem(PosMod), Expected);
1299 EXPECT_EQ(NegLargeLHS.srem(NegMod), Expected);
1300 ConstantRange PosNegLargeLHS(APInt(16, -32), APInt(16, 38));
1301 Expected = ConstantRange(APInt(16, -19), APInt(16, 20));
1302 EXPECT_EQ(PosNegLargeLHS.srem(PosMod), Expected);
1303 EXPECT_EQ(PosNegLargeLHS.srem(NegMod), Expected);
1304
1305 // srem is bounded by LHS.
1306 ConstantRange PosLHS(APInt(16, 0), APInt(16, 16));
1307 EXPECT_EQ(PosLHS.srem(PosMod), PosLHS);
1308 EXPECT_EQ(PosLHS.srem(NegMod), PosLHS);
1309 EXPECT_EQ(PosLHS.srem(IntMinMod), PosLHS);
1310 ConstantRange NegLHS(APInt(16, -15), APInt(16, 1));
1311 EXPECT_EQ(NegLHS.srem(PosMod), NegLHS);
1312 EXPECT_EQ(NegLHS.srem(NegMod), NegLHS);
1313 EXPECT_EQ(NegLHS.srem(IntMinMod), NegLHS);
1314 ConstantRange PosNegLHS(APInt(16, -12), APInt(16, 18));
1315 EXPECT_EQ(PosNegLHS.srem(PosMod), PosNegLHS);
1316 EXPECT_EQ(PosNegLHS.srem(NegMod), PosNegLHS);
1317 EXPECT_EQ(PosNegLHS.srem(IntMinMod), PosNegLHS);
1318
1319 // srem is LHS if it is smaller than RHS.
1320 ConstantRange PosSmallLHS(APInt(16, 3), APInt(16, 8));
1321 EXPECT_EQ(PosSmallLHS.srem(PosMod), PosSmallLHS);
1322 EXPECT_EQ(PosSmallLHS.srem(NegMod), PosSmallLHS);
1323 EXPECT_EQ(PosSmallLHS.srem(IntMinMod), PosSmallLHS);
1324 ConstantRange NegSmallLHS(APInt(16, -7), APInt(16, -2));
1325 EXPECT_EQ(NegSmallLHS.srem(PosMod), NegSmallLHS);
1326 EXPECT_EQ(NegSmallLHS.srem(NegMod), NegSmallLHS);
1327 EXPECT_EQ(NegSmallLHS.srem(IntMinMod), NegSmallLHS);
1328 ConstantRange PosNegSmallLHS(APInt(16, -3), APInt(16, 8));
1329 EXPECT_EQ(PosNegSmallLHS.srem(PosMod), PosNegSmallLHS);
1330 EXPECT_EQ(PosNegSmallLHS.srem(NegMod), PosNegSmallLHS);
1331 EXPECT_EQ(PosNegSmallLHS.srem(IntMinMod), PosNegSmallLHS);
1332
1333 // Example of a suboptimal result:
1334 // [12, 14] srem 10 is [2, 4], but we conservatively compute [0, 9].
1335 EXPECT_EQ(ConstantRange(APInt(16, 12), APInt(16, 15))
1336 .srem(ConstantRange(APInt(16, 10))),
1337 ConstantRange(APInt(16, 0), APInt(16, 10)));
1338
1339 TestBinaryOpExhaustive(
1340 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1341 return CR1.srem(CR2);
1342 },
1343 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
1344 if (N2.isZero())
1345 return std::nullopt;
1346 return N1.srem(N2);
1347 },
1348 PreferSmallest, CheckSingleElementsOnly);
1349 }
1350
1351 TEST_F(ConstantRangeTest, Shl) {
1352 ConstantRange Some2(APInt(16, 0xfff), APInt(16, 0x8000));
1353 ConstantRange WrapNullMax(APInt(16, 0x1), APInt(16, 0x0));
1354 EXPECT_EQ(Full.shl(Full), Full);
1355 EXPECT_EQ(Full.shl(Empty), Empty);
1356 EXPECT_EQ(Full.shl(One), ConstantRange(APInt(16, 0),
1357 APInt(16, 0xfc00) + 1));
1358 EXPECT_EQ(Full.shl(Some), Full); // TODO: [0, (-1 << 0xa) + 1)
1359 EXPECT_EQ(Full.shl(Wrap), Full);
1360 EXPECT_EQ(Empty.shl(Empty), Empty);
1361 EXPECT_EQ(Empty.shl(One), Empty);
1362 EXPECT_EQ(Empty.shl(Some), Empty);
1363 EXPECT_EQ(Empty.shl(Wrap), Empty);
1364 EXPECT_EQ(One.shl(One), ConstantRange(APInt(16, 0xa << 0xa),
1365 APInt(16, (0xa << 0xa) + 1)));
1366 EXPECT_EQ(One.shl(Some), Full); // TODO: [0xa << 0xa, 0)
1367 EXPECT_EQ(One.shl(Wrap), Full); // TODO: [0xa, 0xa << 14 + 1)
1368 EXPECT_EQ(Some.shl(Some), Full); // TODO: [0xa << 0xa, 0xfc01)
1369 EXPECT_EQ(Some.shl(Wrap), Full); // TODO: [0xa, 0x7ff << 0x5 + 1)
1370 EXPECT_EQ(Wrap.shl(Wrap), Full);
1371 EXPECT_EQ(
1372 Some2.shl(ConstantRange(APInt(16, 0x1))),
1373 ConstantRange(APInt(16, 0xfff << 0x1), APInt(16, 0x7fff << 0x1) + 1));
1374 EXPECT_EQ(One.shl(WrapNullMax), Full);
1375
1376 ConstantRange NegOne(APInt(16, 0xffff));
1377 EXPECT_EQ(NegOne.shl(ConstantRange(APInt(16, 0), APInt(16, 5))),
1378 ConstantRange(APInt(16, 0xfff0), APInt(16, 0)));
1379 EXPECT_EQ(ConstantRange(APInt(16, 0xfffe), APInt(16, 0))
1380 .shl(ConstantRange(APInt(16, 0), APInt(16, 5))),
1381 ConstantRange(APInt(16, 0xffe0), APInt(16, 0)));
1382
1383 TestBinaryOpExhaustive(
1384 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1385 return CR1.shl(CR2);
1386 },
1387 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> {
1388 if (N2.uge(N2.getBitWidth()))
1389 return std::nullopt;
1390 return N1.shl(N2);
1391 },
1392 PreferSmallestUnsigned,
1393 [](const ConstantRange &, const ConstantRange &CR2) {
1394 // We currently only produce precise results for single element RHS.
1395 return CR2.isSingleElement();
1396 });
1397 }
1398
1399 TEST_F(ConstantRangeTest, Lshr) {
1400 EXPECT_EQ(Full.lshr(Full), Full);
1401 EXPECT_EQ(Full.lshr(Empty), Empty);
1402 EXPECT_EQ(Full.lshr(One), ConstantRange(APInt(16, 0),
1403 APInt(16, (0xffff >> 0xa) + 1)));
1404 EXPECT_EQ(Full.lshr(Some), ConstantRange(APInt(16, 0),
1405 APInt(16, (0xffff >> 0xa) + 1)));
1406 EXPECT_EQ(Full.lshr(Wrap), Full);
1407 EXPECT_EQ(Empty.lshr(Empty), Empty);
1408 EXPECT_EQ(Empty.lshr(One), Empty);
1409 EXPECT_EQ(Empty.lshr(Some), Empty);
1410 EXPECT_EQ(Empty.lshr(Wrap), Empty);
1411 EXPECT_EQ(One.lshr(One), ConstantRange(APInt(16, 0)));
1412 EXPECT_EQ(One.lshr(Some), ConstantRange(APInt(16, 0)));
1413 EXPECT_EQ(One.lshr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
1414 EXPECT_EQ(Some.lshr(Some), ConstantRange(APInt(16, 0),
1415 APInt(16, (0xaaa >> 0xa) + 1)));
1416 EXPECT_EQ(Some.lshr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
1417 EXPECT_EQ(Wrap.lshr(Wrap), Full);
1418 }
1419
1420 TEST_F(ConstantRangeTest, Ashr) {
1421 EXPECT_EQ(Full.ashr(Full), Full);
1422 EXPECT_EQ(Full.ashr(Empty), Empty);
1423 EXPECT_EQ(Full.ashr(One), ConstantRange(APInt(16, 0xffe0),
1424 APInt(16, (0x7fff >> 0xa) + 1 )));
1425 ConstantRange Small(APInt(16, 0xa), APInt(16, 0xb));
1426 EXPECT_EQ(Full.ashr(Small), ConstantRange(APInt(16, 0xffe0),
1427 APInt(16, (0x7fff >> 0xa) + 1 )));
1428 EXPECT_EQ(Full.ashr(Some), ConstantRange(APInt(16, 0xffe0),
1429 APInt(16, (0x7fff >> 0xa) + 1 )));
1430 EXPECT_EQ(Full.ashr(Wrap), Full);
1431 EXPECT_EQ(Empty.ashr(Empty), Empty);
1432 EXPECT_EQ(Empty.ashr(One), Empty);
1433 EXPECT_EQ(Empty.ashr(Some), Empty);
1434 EXPECT_EQ(Empty.ashr(Wrap), Empty);
1435 EXPECT_EQ(One.ashr(One), ConstantRange(APInt(16, 0)));
1436 EXPECT_EQ(One.ashr(Some), ConstantRange(APInt(16, 0)));
1437 EXPECT_EQ(One.ashr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
1438 EXPECT_EQ(Some.ashr(Some), ConstantRange(APInt(16, 0),
1439 APInt(16, (0xaaa >> 0xa) + 1)));
1440 EXPECT_EQ(Some.ashr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
1441 EXPECT_EQ(Wrap.ashr(Wrap), Full);
1442 ConstantRange Neg(APInt(16, 0xf3f0, true), APInt(16, 0xf7f8, true));
1443 EXPECT_EQ(Neg.ashr(Small), ConstantRange(APInt(16, 0xfffc, true),
1444 APInt(16, 0xfffe, true)));
1445 }
1446
1447 TEST(ConstantRange, MakeAllowedICmpRegion) {
1448 // PR8250
1449 ConstantRange SMax = ConstantRange(APInt::getSignedMaxValue(32));
1450 EXPECT_TRUE(ConstantRange::makeAllowedICmpRegion(ICmpInst::ICMP_SGT, SMax)
1451 .isEmptySet());
1452 }
1453
1454 TEST(ConstantRange, MakeSatisfyingICmpRegion) {
1455 ConstantRange LowHalf(APInt(8, 0), APInt(8, 128));
1456 ConstantRange HighHalf(APInt(8, 128), APInt(8, 0));
1457 ConstantRange EmptySet(8, /* isFullSet = */ false);
1458
1459 EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_NE, LowHalf),
1460 HighHalf);
1461
1462 EXPECT_EQ(
1463 ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_NE, HighHalf),
1464 LowHalf);
1465
1466 EXPECT_TRUE(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_EQ,
1467 HighHalf).isEmptySet());
1468
1469 ConstantRange UnsignedSample(APInt(8, 5), APInt(8, 200));
1470
1471 EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_ULT,
1472 UnsignedSample),
1473 ConstantRange(APInt(8, 0), APInt(8, 5)));
1474
1475 EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_ULE,
1476 UnsignedSample),
1477 ConstantRange(APInt(8, 0), APInt(8, 6)));
1478
1479 EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_UGT,
1480 UnsignedSample),
1481 ConstantRange(APInt(8, 200), APInt(8, 0)));
1482
1483 EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_UGE,
1484 UnsignedSample),
1485 ConstantRange(APInt(8, 199), APInt(8, 0)));
1486
1487 ConstantRange SignedSample(APInt(8, -5), APInt(8, 5));
1488
1489 EXPECT_EQ(
1490 ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SLT, SignedSample),
1491 ConstantRange(APInt(8, -128), APInt(8, -5)));
1492
1493 EXPECT_EQ(
1494 ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SLE, SignedSample),
1495 ConstantRange(APInt(8, -128), APInt(8, -4)));
1496
1497 EXPECT_EQ(
1498 ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SGT, SignedSample),
1499 ConstantRange(APInt(8, 5), APInt(8, -128)));
1500
1501 EXPECT_EQ(
1502 ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SGE, SignedSample),
1503 ConstantRange(APInt(8, 4), APInt(8, -128)));
1504 }
1505
1506 void ICmpTestImpl(CmpInst::Predicate Pred) {
1507 EnumerateTwoInterestingConstantRanges(
1508 [&](const ConstantRange &CR1, const ConstantRange &CR2) {
1509 bool Exhaustive = true;
1510 ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
1511 ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
1512 Exhaustive &= ICmpInst::compare(N1, N2, Pred);
1513 });
1514 });
1515 EXPECT_EQ(CR1.icmp(Pred, CR2), Exhaustive);
1516 });
1517 }
1518
1519 TEST(ConstantRange, ICmp) {
1520 for (auto Pred : ICmpInst::predicates())
1521 ICmpTestImpl(Pred);
1522 }
1523
1524 TEST(ConstantRange, MakeGuaranteedNoWrapRegion) {
1525 const int IntMin4Bits = 8;
1526 const int IntMax4Bits = 7;
1527 typedef OverflowingBinaryOperator OBO;
1528
1529 for (int Const : {0, -1, -2, 1, 2, IntMin4Bits, IntMax4Bits}) {
1530 APInt C(4, Const, true /* = isSigned */);
1531
1532 auto NUWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
1533 Instruction::Add, C, OBO::NoUnsignedWrap);
1534
1535 EXPECT_FALSE(NUWRegion.isEmptySet());
1536
1537 auto NSWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
1538 Instruction::Add, C, OBO::NoSignedWrap);
1539
1540 EXPECT_FALSE(NSWRegion.isEmptySet());
1541
1542 for (APInt I = NUWRegion.getLower(), E = NUWRegion.getUpper(); I != E;
1543 ++I) {
1544 bool Overflow = false;
1545 (void)I.uadd_ov(C, Overflow);
1546 EXPECT_FALSE(Overflow);
1547 }
1548
1549 for (APInt I = NSWRegion.getLower(), E = NSWRegion.getUpper(); I != E;
1550 ++I) {
1551 bool Overflow = false;
1552 (void)I.sadd_ov(C, Overflow);
1553 EXPECT_FALSE(Overflow);
1554 }
1555 }
1556
1557 for (int Const : {0, -1, -2, 1, 2, IntMin4Bits, IntMax4Bits}) {
1558 APInt C(4, Const, true /* = isSigned */);
1559
1560 auto NUWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
1561 Instruction::Sub, C, OBO::NoUnsignedWrap);
1562
1563 EXPECT_FALSE(NUWRegion.isEmptySet());
1564
1565 auto NSWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
1566 Instruction::Sub, C, OBO::NoSignedWrap);
1567
1568 EXPECT_FALSE(NSWRegion.isEmptySet());
1569
1570 for (APInt I = NUWRegion.getLower(), E = NUWRegion.getUpper(); I != E;
1571 ++I) {
1572 bool Overflow = false;
1573 (void)I.usub_ov(C, Overflow);
1574 EXPECT_FALSE(Overflow);
1575 }
1576
1577 for (APInt I = NSWRegion.getLower(), E = NSWRegion.getUpper(); I != E;
1578 ++I) {
1579 bool Overflow = false;
1580 (void)I.ssub_ov(C, Overflow);
1581 EXPECT_FALSE(Overflow);
1582 }
1583 }
1584
1585 auto NSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
1586 Instruction::Add, ConstantRange(32, /* isFullSet = */ true),
1587 OBO::NoSignedWrap);
1588 EXPECT_TRUE(NSWForAllValues.isSingleElement() &&
1589 NSWForAllValues.getSingleElement()->isMinValue());
1590
1591 NSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
1592 Instruction::Sub, ConstantRange(32, /* isFullSet = */ true),
1593 OBO::NoSignedWrap);
1594 EXPECT_TRUE(NSWForAllValues.isSingleElement() &&
1595 NSWForAllValues.getSingleElement()->isMaxValue());
1596
1597 auto NUWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
1598 Instruction::Add, ConstantRange(32, /* isFullSet = */ true),
1599 OBO::NoUnsignedWrap);
1600 EXPECT_TRUE(NUWForAllValues.isSingleElement() &&
1601 NUWForAllValues.getSingleElement()->isMinValue());
1602
1603 NUWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
1604 Instruction::Sub, ConstantRange(32, /* isFullSet = */ true),
1605 OBO::NoUnsignedWrap);
1606 EXPECT_TRUE(NUWForAllValues.isSingleElement() &&
1607 NUWForAllValues.getSingleElement()->isMaxValue());
1608
1609 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
1610 Instruction::Add, APInt(32, 0), OBO::NoUnsignedWrap).isFullSet());
1611 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
1612 Instruction::Add, APInt(32, 0), OBO::NoSignedWrap).isFullSet());
1613 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
1614 Instruction::Sub, APInt(32, 0), OBO::NoUnsignedWrap).isFullSet());
1615 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
1616 Instruction::Sub, APInt(32, 0), OBO::NoSignedWrap).isFullSet());
1617
1618 ConstantRange OneToFive(APInt(32, 1), APInt(32, 6));
1619 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1620 Instruction::Add, OneToFive, OBO::NoSignedWrap),
1621 ConstantRange(APInt::getSignedMinValue(32),
1622 APInt::getSignedMaxValue(32) - 4));
1623 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1624 Instruction::Add, OneToFive, OBO::NoUnsignedWrap),
1625 ConstantRange(APInt::getMinValue(32), APInt::getMinValue(32) - 5));
1626 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1627 Instruction::Sub, OneToFive, OBO::NoSignedWrap),
1628 ConstantRange(APInt::getSignedMinValue(32) + 5,
1629 APInt::getSignedMinValue(32)));
1630 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1631 Instruction::Sub, OneToFive, OBO::NoUnsignedWrap),
1632 ConstantRange(APInt::getMinValue(32) + 5, APInt::getMinValue(32)));
1633
1634 ConstantRange MinusFiveToMinusTwo(APInt(32, -5), APInt(32, -1));
1635 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1636 Instruction::Add, MinusFiveToMinusTwo, OBO::NoSignedWrap),
1637 ConstantRange(APInt::getSignedMinValue(32) + 5,
1638 APInt::getSignedMinValue(32)));
1639 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1640 Instruction::Add, MinusFiveToMinusTwo, OBO::NoUnsignedWrap),
1641 ConstantRange(APInt(32, 0), APInt(32, 2)));
1642 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1643 Instruction::Sub, MinusFiveToMinusTwo, OBO::NoSignedWrap),
1644 ConstantRange(APInt::getSignedMinValue(32),
1645 APInt::getSignedMaxValue(32) - 4));
1646 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1647 Instruction::Sub, MinusFiveToMinusTwo, OBO::NoUnsignedWrap),
1648 ConstantRange(APInt::getMaxValue(32) - 1,
1649 APInt::getMinValue(32)));
1650
1651 ConstantRange MinusOneToOne(APInt(32, -1), APInt(32, 2));
1652 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1653 Instruction::Add, MinusOneToOne, OBO::NoSignedWrap),
1654 ConstantRange(APInt::getSignedMinValue(32) + 1,
1655 APInt::getSignedMinValue(32) - 1));
1656 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1657 Instruction::Add, MinusOneToOne, OBO::NoUnsignedWrap),
1658 ConstantRange(APInt(32, 0), APInt(32, 1)));
1659 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1660 Instruction::Sub, MinusOneToOne, OBO::NoSignedWrap),
1661 ConstantRange(APInt::getSignedMinValue(32) + 1,
1662 APInt::getSignedMinValue(32) - 1));
1663 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1664 Instruction::Sub, MinusOneToOne, OBO::NoUnsignedWrap),
1665 ConstantRange(APInt::getMaxValue(32),
1666 APInt::getMinValue(32)));
1667
1668 ConstantRange One(APInt(32, 1), APInt(32, 2));
1669 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1670 Instruction::Add, One, OBO::NoSignedWrap),
1671 ConstantRange(APInt::getSignedMinValue(32),
1672 APInt::getSignedMaxValue(32)));
1673 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1674 Instruction::Add, One, OBO::NoUnsignedWrap),
1675 ConstantRange(APInt::getMinValue(32), APInt::getMaxValue(32)));
1676 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1677 Instruction::Sub, One, OBO::NoSignedWrap),
1678 ConstantRange(APInt::getSignedMinValue(32) + 1,
1679 APInt::getSignedMinValue(32)));
1680 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1681 Instruction::Sub, One, OBO::NoUnsignedWrap),
1682 ConstantRange(APInt::getMinValue(32) + 1, APInt::getMinValue(32)));
1683
1684 ConstantRange OneLessThanBitWidth(APInt(32, 0), APInt(32, 31) + 1);
1685 ConstantRange UpToBitWidth(APInt(32, 0), APInt(32, 32) + 1);
1686 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1687 Instruction::Shl, UpToBitWidth, OBO::NoUnsignedWrap),
1688 ConstantRange::makeGuaranteedNoWrapRegion(
1689 Instruction::Shl, OneLessThanBitWidth, OBO::NoUnsignedWrap));
1690 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1691 Instruction::Shl, UpToBitWidth, OBO::NoSignedWrap),
1692 ConstantRange::makeGuaranteedNoWrapRegion(
1693 Instruction::Shl, OneLessThanBitWidth, OBO::NoSignedWrap));
1694 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1695 Instruction::Shl, UpToBitWidth, OBO::NoUnsignedWrap),
1696 ConstantRange(APInt(32, 0), APInt(32, 1) + 1));
1697 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1698 Instruction::Shl, UpToBitWidth, OBO::NoSignedWrap),
1699 ConstantRange(APInt(32, -1), APInt(32, 0) + 1));
1700
1701 EXPECT_EQ(
1702 ConstantRange::makeGuaranteedNoWrapRegion(
1703 Instruction::Shl, ConstantRange::getFull(32), OBO::NoUnsignedWrap),
1704 ConstantRange::makeGuaranteedNoWrapRegion(
1705 Instruction::Shl, OneLessThanBitWidth, OBO::NoUnsignedWrap));
1706 EXPECT_EQ(
1707 ConstantRange::makeGuaranteedNoWrapRegion(
1708 Instruction::Shl, ConstantRange::getFull(32), OBO::NoSignedWrap),
1709 ConstantRange::makeGuaranteedNoWrapRegion(
1710 Instruction::Shl, OneLessThanBitWidth, OBO::NoSignedWrap));
1711
1712 ConstantRange IllegalShAmt(APInt(32, 32), APInt(32, 0) + 1);
1713 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1714 Instruction::Shl, IllegalShAmt, OBO::NoUnsignedWrap),
1715 ConstantRange::getFull(32));
1716 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1717 Instruction::Shl, IllegalShAmt, OBO::NoSignedWrap),
1718 ConstantRange::getFull(32));
1719
1720 EXPECT_EQ(
1721 ConstantRange::makeGuaranteedNoWrapRegion(
1722 Instruction::Shl, ConstantRange(APInt(32, -32), APInt(32, 16) + 1),
1723 OBO::NoUnsignedWrap),
1724 ConstantRange::makeGuaranteedNoWrapRegion(
1725 Instruction::Shl, ConstantRange(APInt(32, 0), APInt(32, 16) + 1),
1726 OBO::NoUnsignedWrap));
1727 EXPECT_EQ(
1728 ConstantRange::makeGuaranteedNoWrapRegion(
1729 Instruction::Shl, ConstantRange(APInt(32, -32), APInt(32, 16) + 1),
1730 OBO::NoSignedWrap),
1731 ConstantRange::makeGuaranteedNoWrapRegion(
1732 Instruction::Shl, ConstantRange(APInt(32, 0), APInt(32, 16) + 1),
1733 OBO::NoSignedWrap));
1734
1735 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1736 Instruction::Shl,
1737 ConstantRange(APInt(32, -32), APInt(32, 16) + 1),
1738 OBO::NoUnsignedWrap),
1739 ConstantRange(APInt(32, 0), APInt(32, 65535) + 1));
1740 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1741 Instruction::Shl,
1742 ConstantRange(APInt(32, -32), APInt(32, 16) + 1),
1743 OBO::NoSignedWrap),
1744 ConstantRange(APInt(32, -32768), APInt(32, 32767) + 1));
1745 }
1746
1747 template<typename Fn>
1748 void TestNoWrapRegionExhaustive(Instruction::BinaryOps BinOp,
1749 unsigned NoWrapKind, Fn OverflowFn) {
1750 for (unsigned Bits : {1, 5}) {
1751 EnumerateConstantRanges(Bits, [&](const ConstantRange &CR) {
1752 if (CR.isEmptySet())
1753 return;
1754 if (Instruction::isShift(BinOp) && CR.getUnsignedMax().uge(Bits))
1755 return;
1756
1757 ConstantRange NoWrap =
1758 ConstantRange::makeGuaranteedNoWrapRegion(BinOp, CR, NoWrapKind);
1759 EnumerateAPInts(Bits, [&](const APInt &N1) {
1760 bool NoOverflow = true;
1761 bool Overflow = true;
1762 ForeachNumInConstantRange(CR, [&](const APInt &N2) {
1763 if (OverflowFn(N1, N2))
1764 NoOverflow = false;
1765 else
1766 Overflow = false;
1767 });
1768 EXPECT_EQ(NoOverflow, NoWrap.contains(N1));
1769
1770 // The no-wrap range is exact for single-element ranges.
1771 if (CR.isSingleElement()) {
1772 EXPECT_EQ(Overflow, !NoWrap.contains(N1));
1773 }
1774 });
1775 });
1776 }
1777 }
1778
1779 // Show that makeGuaranteedNoWrapRegion() is maximal, and for single-element
1780 // ranges also exact.
1781 TEST(ConstantRange, NoWrapRegionExhaustive) {
1782 TestNoWrapRegionExhaustive(
1783 Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap,
1784 [](const APInt &N1, const APInt &N2) {
1785 bool Overflow;
1786 (void) N1.uadd_ov(N2, Overflow);
1787 return Overflow;
1788 });
1789 TestNoWrapRegionExhaustive(
1790 Instruction::Add, OverflowingBinaryOperator::NoSignedWrap,
1791 [](const APInt &N1, const APInt &N2) {
1792 bool Overflow;
1793 (void) N1.sadd_ov(N2, Overflow);
1794 return Overflow;
1795 });
1796 TestNoWrapRegionExhaustive(
1797 Instruction::Sub, OverflowingBinaryOperator::NoUnsignedWrap,
1798 [](const APInt &N1, const APInt &N2) {
1799 bool Overflow;
1800 (void) N1.usub_ov(N2, Overflow);
1801 return Overflow;
1802 });
1803 TestNoWrapRegionExhaustive(
1804 Instruction::Sub, OverflowingBinaryOperator::NoSignedWrap,
1805 [](const APInt &N1, const APInt &N2) {
1806 bool Overflow;
1807 (void) N1.ssub_ov(N2, Overflow);
1808 return Overflow;
1809 });
1810 TestNoWrapRegionExhaustive(
1811 Instruction::Mul, OverflowingBinaryOperator::NoUnsignedWrap,
1812 [](const APInt &N1, const APInt &N2) {
1813 bool Overflow;
1814 (void) N1.umul_ov(N2, Overflow);
1815 return Overflow;
1816 });
1817 TestNoWrapRegionExhaustive(
1818 Instruction::Mul, OverflowingBinaryOperator::NoSignedWrap,
1819 [](const APInt &N1, const APInt &N2) {
1820 bool Overflow;
1821 (void) N1.smul_ov(N2, Overflow);
1822 return Overflow;
1823 });
1824 TestNoWrapRegionExhaustive(Instruction::Shl,
1825 OverflowingBinaryOperator::NoUnsignedWrap,
1826 [](const APInt &N1, const APInt &N2) {
1827 bool Overflow;
1828 (void)N1.ushl_ov(N2, Overflow);
1829 return Overflow;
1830 });
1831 TestNoWrapRegionExhaustive(Instruction::Shl,
1832 OverflowingBinaryOperator::NoSignedWrap,
1833 [](const APInt &N1, const APInt &N2) {
1834 bool Overflow;
1835 (void)N1.sshl_ov(N2, Overflow);
1836 return Overflow;
1837 });
1838 }
1839
1840 TEST(ConstantRange, GetEquivalentICmp) {
1841 APInt RHS;
1842 CmpInst::Predicate Pred;
1843
1844 EXPECT_TRUE(ConstantRange(APInt::getMinValue(32), APInt(32, 100))
1845 .getEquivalentICmp(Pred, RHS));
1846 EXPECT_EQ(Pred, CmpInst::ICMP_ULT);
1847 EXPECT_EQ(RHS, APInt(32, 100));
1848
1849 EXPECT_TRUE(ConstantRange(APInt::getSignedMinValue(32), APInt(32, 100))
1850 .getEquivalentICmp(Pred, RHS));
1851 EXPECT_EQ(Pred, CmpInst::ICMP_SLT);
1852 EXPECT_EQ(RHS, APInt(32, 100));
1853
1854 EXPECT_TRUE(ConstantRange(APInt(32, 100), APInt::getMinValue(32))
1855 .getEquivalentICmp(Pred, RHS));
1856 EXPECT_EQ(Pred, CmpInst::ICMP_UGE);
1857 EXPECT_EQ(RHS, APInt(32, 100));
1858
1859 EXPECT_TRUE(ConstantRange(APInt(32, 100), APInt::getSignedMinValue(32))
1860 .getEquivalentICmp(Pred, RHS));
1861 EXPECT_EQ(Pred, CmpInst::ICMP_SGE);
1862 EXPECT_EQ(RHS, APInt(32, 100));
1863
1864 EXPECT_TRUE(
1865 ConstantRange(32, /*isFullSet=*/true).getEquivalentICmp(Pred, RHS));
1866 EXPECT_EQ(Pred, CmpInst::ICMP_UGE);
1867 EXPECT_EQ(RHS, APInt(32, 0));
1868
1869 EXPECT_TRUE(
1870 ConstantRange(32, /*isFullSet=*/false).getEquivalentICmp(Pred, RHS));
1871 EXPECT_EQ(Pred, CmpInst::ICMP_ULT);
1872 EXPECT_EQ(RHS, APInt(32, 0));
1873
1874 EXPECT_FALSE(ConstantRange(APInt(32, 100), APInt(32, 200))
1875 .getEquivalentICmp(Pred, RHS));
1876
1877 EXPECT_FALSE(ConstantRange(APInt::getSignedMinValue(32) - APInt(32, 100),
1878 APInt::getSignedMinValue(32) + APInt(32, 100))
1879 .getEquivalentICmp(Pred, RHS));
1880
1881 EXPECT_FALSE(ConstantRange(APInt::getMinValue(32) - APInt(32, 100),
1882 APInt::getMinValue(32) + APInt(32, 100))
1883 .getEquivalentICmp(Pred, RHS));
1884
1885 EXPECT_TRUE(ConstantRange(APInt(32, 100)).getEquivalentICmp(Pred, RHS));
1886 EXPECT_EQ(Pred, CmpInst::ICMP_EQ);
1887 EXPECT_EQ(RHS, APInt(32, 100));
1888
1889 EXPECT_TRUE(
1890 ConstantRange(APInt(32, 100)).inverse().getEquivalentICmp(Pred, RHS));
1891 EXPECT_EQ(Pred, CmpInst::ICMP_NE);
1892 EXPECT_EQ(RHS, APInt(32, 100));
1893
1894 EXPECT_TRUE(
1895 ConstantRange(APInt(512, 100)).inverse().getEquivalentICmp(Pred, RHS));
1896 EXPECT_EQ(Pred, CmpInst::ICMP_NE);
1897 EXPECT_EQ(RHS, APInt(512, 100));
1898
1899 // NB! It would be correct for the following four calls to getEquivalentICmp
1900 // to return ordered predicates like CmpInst::ICMP_ULT or CmpInst::ICMP_UGT.
1901 // However, that's not the case today.
1902
1903 EXPECT_TRUE(ConstantRange(APInt(32, 0)).getEquivalentICmp(Pred, RHS));
1904 EXPECT_EQ(Pred, CmpInst::ICMP_EQ);
1905 EXPECT_EQ(RHS, APInt(32, 0));
1906
1907 EXPECT_TRUE(
1908 ConstantRange(APInt(32, 0)).inverse().getEquivalentICmp(Pred, RHS));
1909 EXPECT_EQ(Pred, CmpInst::ICMP_NE);
1910 EXPECT_EQ(RHS, APInt(32, 0));
1911
1912 EXPECT_TRUE(ConstantRange(APInt(32, -1)).getEquivalentICmp(Pred, RHS));
1913 EXPECT_EQ(Pred, CmpInst::ICMP_EQ);
1914 EXPECT_EQ(RHS, APInt(32, -1));
1915
1916 EXPECT_TRUE(
1917 ConstantRange(APInt(32, -1)).inverse().getEquivalentICmp(Pred, RHS));
1918 EXPECT_EQ(Pred, CmpInst::ICMP_NE);
1919 EXPECT_EQ(RHS, APInt(32, -1));
1920
1921 EnumerateInterestingConstantRanges([](const ConstantRange &CR) {
1922 unsigned Bits = CR.getBitWidth();
1923 CmpInst::Predicate Pred;
1924 APInt RHS, Offset;
1925 CR.getEquivalentICmp(Pred, RHS, Offset);
1926 EnumerateAPInts(Bits, [&](const APInt &N) {
1927 bool Result = ICmpInst::compare(N + Offset, RHS, Pred);
1928 EXPECT_EQ(CR.contains(N), Result);
1929 });
1930
1931 if (CR.getEquivalentICmp(Pred, RHS)) {
1932 EnumerateAPInts(Bits, [&](const APInt &N) {
1933 bool Result = ICmpInst::compare(N, RHS, Pred);
1934 EXPECT_EQ(CR.contains(N), Result);
1935 });
1936 }
1937 });
1938 }
1939
1940 #define EXPECT_MAY_OVERFLOW(op) \
1941 EXPECT_EQ(ConstantRange::OverflowResult::MayOverflow, (op))
1942 #define EXPECT_ALWAYS_OVERFLOWS_LOW(op) \
1943 EXPECT_EQ(ConstantRange::OverflowResult::AlwaysOverflowsLow, (op))
1944 #define EXPECT_ALWAYS_OVERFLOWS_HIGH(op) \
1945 EXPECT_EQ(ConstantRange::OverflowResult::AlwaysOverflowsHigh, (op))
1946 #define EXPECT_NEVER_OVERFLOWS(op) \
1947 EXPECT_EQ(ConstantRange::OverflowResult::NeverOverflows, (op))
1948
1949 TEST_F(ConstantRangeTest, UnsignedAddOverflow) {
1950 // Ill-defined - may overflow is a conservative result.
1951 EXPECT_MAY_OVERFLOW(Some.unsignedAddMayOverflow(Empty));
1952 EXPECT_MAY_OVERFLOW(Empty.unsignedAddMayOverflow(Some));
1953
1954 // Never overflow despite one full/wrap set.
1955 ConstantRange Zero(APInt::getZero(16));
1956 EXPECT_NEVER_OVERFLOWS(Full.unsignedAddMayOverflow(Zero));
1957 EXPECT_NEVER_OVERFLOWS(Wrap.unsignedAddMayOverflow(Zero));
1958 EXPECT_NEVER_OVERFLOWS(Zero.unsignedAddMayOverflow(Full));
1959 EXPECT_NEVER_OVERFLOWS(Zero.unsignedAddMayOverflow(Wrap));
1960
1961 // But usually full/wrap always may overflow.
1962 EXPECT_MAY_OVERFLOW(Full.unsignedAddMayOverflow(One));
1963 EXPECT_MAY_OVERFLOW(Wrap.unsignedAddMayOverflow(One));
1964 EXPECT_MAY_OVERFLOW(One.unsignedAddMayOverflow(Full));
1965 EXPECT_MAY_OVERFLOW(One.unsignedAddMayOverflow(Wrap));
1966
1967 ConstantRange A(APInt(16, 0xfd00), APInt(16, 0xfe00));
1968 ConstantRange B1(APInt(16, 0x0100), APInt(16, 0x0201));
1969 ConstantRange B2(APInt(16, 0x0100), APInt(16, 0x0202));
1970 EXPECT_NEVER_OVERFLOWS(A.unsignedAddMayOverflow(B1));
1971 EXPECT_MAY_OVERFLOW(A.unsignedAddMayOverflow(B2));
1972 EXPECT_NEVER_OVERFLOWS(B1.unsignedAddMayOverflow(A));
1973 EXPECT_MAY_OVERFLOW(B2.unsignedAddMayOverflow(A));
1974
1975 ConstantRange C1(APInt(16, 0x0299), APInt(16, 0x0400));
1976 ConstantRange C2(APInt(16, 0x0300), APInt(16, 0x0400));
1977 EXPECT_MAY_OVERFLOW(A.unsignedAddMayOverflow(C1));
1978 EXPECT_ALWAYS_OVERFLOWS_HIGH(A.unsignedAddMayOverflow(C2));
1979 EXPECT_MAY_OVERFLOW(C1.unsignedAddMayOverflow(A));
1980 EXPECT_ALWAYS_OVERFLOWS_HIGH(C2.unsignedAddMayOverflow(A));
1981 }
1982
1983 TEST_F(ConstantRangeTest, UnsignedSubOverflow) {
1984 // Ill-defined - may overflow is a conservative result.
1985 EXPECT_MAY_OVERFLOW(Some.unsignedSubMayOverflow(Empty));
1986 EXPECT_MAY_OVERFLOW(Empty.unsignedSubMayOverflow(Some));
1987
1988 // Never overflow despite one full/wrap set.
1989 ConstantRange Zero(APInt::getZero(16));
1990 ConstantRange Max(APInt::getAllOnes(16));
1991 EXPECT_NEVER_OVERFLOWS(Full.unsignedSubMayOverflow(Zero));
1992 EXPECT_NEVER_OVERFLOWS(Wrap.unsignedSubMayOverflow(Zero));
1993 EXPECT_NEVER_OVERFLOWS(Max.unsignedSubMayOverflow(Full));
1994 EXPECT_NEVER_OVERFLOWS(Max.unsignedSubMayOverflow(Wrap));
1995
1996 // But usually full/wrap always may overflow.
1997 EXPECT_MAY_OVERFLOW(Full.unsignedSubMayOverflow(One));
1998 EXPECT_MAY_OVERFLOW(Wrap.unsignedSubMayOverflow(One));
1999 EXPECT_MAY_OVERFLOW(One.unsignedSubMayOverflow(Full));
2000 EXPECT_MAY_OVERFLOW(One.unsignedSubMayOverflow(Wrap));
2001
2002 ConstantRange A(APInt(16, 0x0000), APInt(16, 0x0100));
2003 ConstantRange B(APInt(16, 0x0100), APInt(16, 0x0200));
2004 EXPECT_NEVER_OVERFLOWS(B.unsignedSubMayOverflow(A));
2005 EXPECT_ALWAYS_OVERFLOWS_LOW(A.unsignedSubMayOverflow(B));
2006
2007 ConstantRange A1(APInt(16, 0x0000), APInt(16, 0x0101));
2008 ConstantRange B1(APInt(16, 0x0100), APInt(16, 0x0201));
2009 EXPECT_NEVER_OVERFLOWS(B1.unsignedSubMayOverflow(A1));
2010 EXPECT_MAY_OVERFLOW(A1.unsignedSubMayOverflow(B1));
2011
2012 ConstantRange A2(APInt(16, 0x0000), APInt(16, 0x0102));
2013 ConstantRange B2(APInt(16, 0x0100), APInt(16, 0x0202));
2014 EXPECT_MAY_OVERFLOW(B2.unsignedSubMayOverflow(A2));
2015 EXPECT_MAY_OVERFLOW(A2.unsignedSubMayOverflow(B2));
2016 }
2017
2018 TEST_F(ConstantRangeTest, SignedAddOverflow) {
2019 // Ill-defined - may overflow is a conservative result.
2020 EXPECT_MAY_OVERFLOW(Some.signedAddMayOverflow(Empty));
2021 EXPECT_MAY_OVERFLOW(Empty.signedAddMayOverflow(Some));
2022
2023 // Never overflow despite one full/wrap set.
2024 ConstantRange Zero(APInt::getZero(16));
2025 EXPECT_NEVER_OVERFLOWS(Full.signedAddMayOverflow(Zero));
2026 EXPECT_NEVER_OVERFLOWS(Wrap.signedAddMayOverflow(Zero));
2027 EXPECT_NEVER_OVERFLOWS(Zero.signedAddMayOverflow(Full));
2028 EXPECT_NEVER_OVERFLOWS(Zero.signedAddMayOverflow(Wrap));
2029
2030 // But usually full/wrap always may overflow.
2031 EXPECT_MAY_OVERFLOW(Full.signedAddMayOverflow(One));
2032 EXPECT_MAY_OVERFLOW(Wrap.signedAddMayOverflow(One));
2033 EXPECT_MAY_OVERFLOW(One.signedAddMayOverflow(Full));
2034 EXPECT_MAY_OVERFLOW(One.signedAddMayOverflow(Wrap));
2035
2036 ConstantRange A(APInt(16, 0x7d00), APInt(16, 0x7e00));
2037 ConstantRange B1(APInt(16, 0x0100), APInt(16, 0x0201));
2038 ConstantRange B2(APInt(16, 0x0100), APInt(16, 0x0202));
2039 EXPECT_NEVER_OVERFLOWS(A.signedAddMayOverflow(B1));
2040 EXPECT_MAY_OVERFLOW(A.signedAddMayOverflow(B2));
2041 ConstantRange B3(APInt(16, 0x8000), APInt(16, 0x0201));
2042 ConstantRange B4(APInt(16, 0x8000), APInt(16, 0x0202));
2043 EXPECT_NEVER_OVERFLOWS(A.signedAddMayOverflow(B3));
2044 EXPECT_MAY_OVERFLOW(A.signedAddMayOverflow(B4));
2045 ConstantRange B5(APInt(16, 0x0299), APInt(16, 0x0400));
2046 ConstantRange B6(APInt(16, 0x0300), APInt(16, 0x0400));
2047 EXPECT_MAY_OVERFLOW(A.signedAddMayOverflow(B5));
2048 EXPECT_ALWAYS_OVERFLOWS_HIGH(A.signedAddMayOverflow(B6));
2049
2050 ConstantRange C(APInt(16, 0x8200), APInt(16, 0x8300));
2051 ConstantRange D1(APInt(16, 0xfe00), APInt(16, 0xff00));
2052 ConstantRange D2(APInt(16, 0xfd99), APInt(16, 0xff00));
2053 EXPECT_NEVER_OVERFLOWS(C.signedAddMayOverflow(D1));
2054 EXPECT_MAY_OVERFLOW(C.signedAddMayOverflow(D2));
2055 ConstantRange D3(APInt(16, 0xfe00), APInt(16, 0x8000));
2056 ConstantRange D4(APInt(16, 0xfd99), APInt(16, 0x8000));
2057 EXPECT_NEVER_OVERFLOWS(C.signedAddMayOverflow(D3));
2058 EXPECT_MAY_OVERFLOW(C.signedAddMayOverflow(D4));
2059 ConstantRange D5(APInt(16, 0xfc00), APInt(16, 0xfd02));
2060 ConstantRange D6(APInt(16, 0xfc00), APInt(16, 0xfd01));
2061 EXPECT_MAY_OVERFLOW(C.signedAddMayOverflow(D5));
2062 EXPECT_ALWAYS_OVERFLOWS_LOW(C.signedAddMayOverflow(D6));
2063
2064 ConstantRange E(APInt(16, 0xff00), APInt(16, 0x0100));
2065 EXPECT_NEVER_OVERFLOWS(E.signedAddMayOverflow(E));
2066 ConstantRange F(APInt(16, 0xf000), APInt(16, 0x7000));
2067 EXPECT_MAY_OVERFLOW(F.signedAddMayOverflow(F));
2068 }
2069
2070 TEST_F(ConstantRangeTest, SignedSubOverflow) {
2071 // Ill-defined - may overflow is a conservative result.
2072 EXPECT_MAY_OVERFLOW(Some.signedSubMayOverflow(Empty));
2073 EXPECT_MAY_OVERFLOW(Empty.signedSubMayOverflow(Some));
2074
2075 // Never overflow despite one full/wrap set.
2076 ConstantRange Zero(APInt::getZero(16));
2077 EXPECT_NEVER_OVERFLOWS(Full.signedSubMayOverflow(Zero));
2078 EXPECT_NEVER_OVERFLOWS(Wrap.signedSubMayOverflow(Zero));
2079
2080 // But usually full/wrap always may overflow.
2081 EXPECT_MAY_OVERFLOW(Full.signedSubMayOverflow(One));
2082 EXPECT_MAY_OVERFLOW(Wrap.signedSubMayOverflow(One));
2083 EXPECT_MAY_OVERFLOW(One.signedSubMayOverflow(Full));
2084 EXPECT_MAY_OVERFLOW(One.signedSubMayOverflow(Wrap));
2085
2086 ConstantRange A(APInt(16, 0x7d00), APInt(16, 0x7e00));
2087 ConstantRange B1(APInt(16, 0xfe00), APInt(16, 0xff00));
2088 ConstantRange B2(APInt(16, 0xfd99), APInt(16, 0xff00));
2089 EXPECT_NEVER_OVERFLOWS(A.signedSubMayOverflow(B1));
2090 EXPECT_MAY_OVERFLOW(A.signedSubMayOverflow(B2));
2091 ConstantRange B3(APInt(16, 0xfc00), APInt(16, 0xfd02));
2092 ConstantRange B4(APInt(16, 0xfc00), APInt(16, 0xfd01));
2093 EXPECT_MAY_OVERFLOW(A.signedSubMayOverflow(B3));
2094 EXPECT_ALWAYS_OVERFLOWS_HIGH(A.signedSubMayOverflow(B4));
2095
2096 ConstantRange C(APInt(16, 0x8200), APInt(16, 0x8300));
2097 ConstantRange D1(APInt(16, 0x0100), APInt(16, 0x0201));
2098 ConstantRange D2(APInt(16, 0x0100), APInt(16, 0x0202));
2099 EXPECT_NEVER_OVERFLOWS(C.signedSubMayOverflow(D1));
2100 EXPECT_MAY_OVERFLOW(C.signedSubMayOverflow(D2));
2101 ConstantRange D3(APInt(16, 0x0299), APInt(16, 0x0400));
2102 ConstantRange D4(APInt(16, 0x0300), APInt(16, 0x0400));
2103 EXPECT_MAY_OVERFLOW(C.signedSubMayOverflow(D3));
2104 EXPECT_ALWAYS_OVERFLOWS_LOW(C.signedSubMayOverflow(D4));
2105
2106 ConstantRange E(APInt(16, 0xff00), APInt(16, 0x0100));
2107 EXPECT_NEVER_OVERFLOWS(E.signedSubMayOverflow(E));
2108 ConstantRange F(APInt(16, 0xf000), APInt(16, 0x7001));
2109 EXPECT_MAY_OVERFLOW(F.signedSubMayOverflow(F));
2110 }
2111
2112 template <typename Fn1, typename Fn2>
2113 static void TestOverflowExhaustive(Fn1 OverflowFn, Fn2 MayOverflowFn) {
2114 // Constant range overflow checks are tested exhaustively on 4-bit numbers.
2115 EnumerateTwoInterestingConstantRanges([=](const ConstantRange &CR1,
2116 const ConstantRange &CR2) {
2117 // Loop over all N1 in CR1 and N2 in CR2 and check whether any of the
2118 // operations have overflow / have no overflow.
2119 bool RangeHasOverflowLow = false;
2120 bool RangeHasOverflowHigh = false;
2121 bool RangeHasNoOverflow = false;
2122 ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
2123 ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
2124 bool IsOverflowHigh;
2125 if (!OverflowFn(IsOverflowHigh, N1, N2)) {
2126 RangeHasNoOverflow = true;
2127 return;
2128 }
2129
2130 if (IsOverflowHigh)
2131 RangeHasOverflowHigh = true;
2132 else
2133 RangeHasOverflowLow = true;
2134 });
2135 });
2136
2137 ConstantRange::OverflowResult OR = MayOverflowFn(CR1, CR2);
2138 switch (OR) {
2139 case ConstantRange::OverflowResult::AlwaysOverflowsLow:
2140 EXPECT_TRUE(RangeHasOverflowLow);
2141 EXPECT_FALSE(RangeHasOverflowHigh);
2142 EXPECT_FALSE(RangeHasNoOverflow);
2143 break;
2144 case ConstantRange::OverflowResult::AlwaysOverflowsHigh:
2145 EXPECT_TRUE(RangeHasOverflowHigh);
2146 EXPECT_FALSE(RangeHasOverflowLow);
2147 EXPECT_FALSE(RangeHasNoOverflow);
2148 break;
2149 case ConstantRange::OverflowResult::NeverOverflows:
2150 EXPECT_FALSE(RangeHasOverflowLow);
2151 EXPECT_FALSE(RangeHasOverflowHigh);
2152 EXPECT_TRUE(RangeHasNoOverflow);
2153 break;
2154 case ConstantRange::OverflowResult::MayOverflow:
2155 // We return MayOverflow for empty sets as a conservative result,
2156 // but of course neither the RangeHasOverflow nor the
2157 // RangeHasNoOverflow flags will be set.
2158 if (CR1.isEmptySet() || CR2.isEmptySet())
2159 break;
2160
2161 EXPECT_TRUE(RangeHasOverflowLow || RangeHasOverflowHigh);
2162 EXPECT_TRUE(RangeHasNoOverflow);
2163 break;
2164 }
2165 });
2166 }
2167
2168 TEST_F(ConstantRangeTest, UnsignedAddOverflowExhaustive) {
2169 TestOverflowExhaustive(
2170 [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
2171 bool Overflow;
2172 (void) N1.uadd_ov(N2, Overflow);
2173 IsOverflowHigh = true;
2174 return Overflow;
2175 },
2176 [](const ConstantRange &CR1, const ConstantRange &CR2) {
2177 return CR1.unsignedAddMayOverflow(CR2);
2178 });
2179 }
2180
2181 TEST_F(ConstantRangeTest, UnsignedSubOverflowExhaustive) {
2182 TestOverflowExhaustive(
2183 [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
2184 bool Overflow;
2185 (void) N1.usub_ov(N2, Overflow);
2186 IsOverflowHigh = false;
2187 return Overflow;
2188 },
2189 [](const ConstantRange &CR1, const ConstantRange &CR2) {
2190 return CR1.unsignedSubMayOverflow(CR2);
2191 });
2192 }
2193
2194 TEST_F(ConstantRangeTest, UnsignedMulOverflowExhaustive) {
2195 TestOverflowExhaustive(
2196 [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
2197 bool Overflow;
2198 (void) N1.umul_ov(N2, Overflow);
2199 IsOverflowHigh = true;
2200 return Overflow;
2201 },
2202 [](const ConstantRange &CR1, const ConstantRange &CR2) {
2203 return CR1.unsignedMulMayOverflow(CR2);
2204 });
2205 }
2206
2207 TEST_F(ConstantRangeTest, SignedAddOverflowExhaustive) {
2208 TestOverflowExhaustive(
2209 [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
2210 bool Overflow;
2211 (void) N1.sadd_ov(N2, Overflow);
2212 IsOverflowHigh = N1.isNonNegative();
2213 return Overflow;
2214 },
2215 [](const ConstantRange &CR1, const ConstantRange &CR2) {
2216 return CR1.signedAddMayOverflow(CR2);
2217 });
2218 }
2219
2220 TEST_F(ConstantRangeTest, SignedSubOverflowExhaustive) {
2221 TestOverflowExhaustive(
2222 [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
2223 bool Overflow;
2224 (void) N1.ssub_ov(N2, Overflow);
2225 IsOverflowHigh = N1.isNonNegative();
2226 return Overflow;
2227 },
2228 [](const ConstantRange &CR1, const ConstantRange &CR2) {
2229 return CR1.signedSubMayOverflow(CR2);
2230 });
2231 }
2232
2233 TEST_F(ConstantRangeTest, FromKnownBits) {
2234 KnownBits Unknown(16);
2235 EXPECT_EQ(Full, ConstantRange::fromKnownBits(Unknown, /*signed*/false));
2236 EXPECT_EQ(Full, ConstantRange::fromKnownBits(Unknown, /*signed*/true));
2237
2238 // .10..01. -> unsigned 01000010 (66) to 11011011 (219)
2239 // -> signed 11000010 (194) to 01011011 (91)
2240 KnownBits Known(8);
2241 Known.Zero = 36;
2242 Known.One = 66;
2243 ConstantRange Unsigned(APInt(8, 66), APInt(8, 219 + 1));
2244 ConstantRange Signed(APInt(8, 194), APInt(8, 91 + 1));
2245 EXPECT_EQ(Unsigned, ConstantRange::fromKnownBits(Known, /*signed*/false));
2246 EXPECT_EQ(Signed, ConstantRange::fromKnownBits(Known, /*signed*/true));
2247
2248 // 1.10.10. -> 10100100 (164) to 11101101 (237)
2249 Known.Zero = 18;
2250 Known.One = 164;
2251 ConstantRange CR1(APInt(8, 164), APInt(8, 237 + 1));
2252 EXPECT_EQ(CR1, ConstantRange::fromKnownBits(Known, /*signed*/false));
2253 EXPECT_EQ(CR1, ConstantRange::fromKnownBits(Known, /*signed*/true));
2254
2255 // 01.0.1.0 -> 01000100 (68) to 01101110 (110)
2256 Known.Zero = 145;
2257 Known.One = 68;
2258 ConstantRange CR2(APInt(8, 68), APInt(8, 110 + 1));
2259 EXPECT_EQ(CR2, ConstantRange::fromKnownBits(Known, /*signed*/false));
2260 EXPECT_EQ(CR2, ConstantRange::fromKnownBits(Known, /*signed*/true));
2261 }
2262
2263 TEST_F(ConstantRangeTest, FromKnownBitsExhaustive) {
2264 unsigned Bits = 4;
2265 unsigned Max = 1 << Bits;
2266 KnownBits Known(Bits);
2267 for (unsigned Zero = 0; Zero < Max; ++Zero) {
2268 for (unsigned One = 0; One < Max; ++One) {
2269 Known.Zero = Zero;
2270 Known.One = One;
2271 if (Known.hasConflict() || Known.isUnknown())
2272 continue;
2273
2274 SmallBitVector Elems(1 << Bits);
2275 for (unsigned N = 0; N < Max; ++N) {
2276 APInt Num(Bits, N);
2277 if ((Num & Known.Zero) != 0 || (~Num & Known.One) != 0)
2278 continue;
2279 Elems.set(Num.getZExtValue());
2280 }
2281
2282 TestRange(ConstantRange::fromKnownBits(Known, false),
2283 Elems, PreferSmallestUnsigned, {});
2284 TestRange(ConstantRange::fromKnownBits(Known, true),
2285 Elems, PreferSmallestSigned, {});
2286 }
2287 }
2288 }
2289
2290 TEST_F(ConstantRangeTest, ToKnownBits) {
2291 EnumerateInterestingConstantRanges([&](const ConstantRange &CR) {
2292 KnownBits Known = CR.toKnownBits();
2293 KnownBits ExpectedKnown(CR.getBitWidth());
2294 ExpectedKnown.Zero.setAllBits();
2295 ExpectedKnown.One.setAllBits();
2296 ForeachNumInConstantRange(CR, [&](const APInt &N) {
2297 ExpectedKnown.One &= N;
2298 ExpectedKnown.Zero &= ~N;
2299 });
2300 // For an empty CR any result would be legal.
2301 if (!CR.isEmptySet()) {
2302 EXPECT_EQ(ExpectedKnown, Known);
2303 }
2304 });
2305 }
2306
2307 TEST_F(ConstantRangeTest, Negative) {
2308 // All elements in an empty set (of which there are none) are both negative
2309 // and non-negative. Empty & full sets checked explicitly for clarity, but
2310 // they are also covered by the exhaustive test below.
2311 EXPECT_TRUE(Empty.isAllNegative());
2312 EXPECT_TRUE(Empty.isAllNonNegative());
2313 EXPECT_FALSE(Full.isAllNegative());
2314 EXPECT_FALSE(Full.isAllNonNegative());
2315
2316 EnumerateInterestingConstantRanges([](const ConstantRange &CR) {
2317 bool AllNegative = true;
2318 bool AllNonNegative = true;
2319 ForeachNumInConstantRange(CR, [&](const APInt &N) {
2320 if (!N.isNegative())
2321 AllNegative = false;
2322 if (!N.isNonNegative())
2323 AllNonNegative = false;
2324 });
2325 assert((CR.isEmptySet() || !AllNegative || !AllNonNegative) &&
2326 "Only empty set can be both all negative and all non-negative");
2327
2328 EXPECT_EQ(AllNegative, CR.isAllNegative());
2329 EXPECT_EQ(AllNonNegative, CR.isAllNonNegative());
2330 });
2331 }
2332
2333 TEST_F(ConstantRangeTest, UAddSat) {
2334 TestBinaryOpExhaustive(
2335 [](const ConstantRange &CR1, const ConstantRange &CR2) {
2336 return CR1.uadd_sat(CR2);
2337 },
2338 [](const APInt &N1, const APInt &N2) {
2339 return N1.uadd_sat(N2);
2340 },
2341 PreferSmallestUnsigned);
2342 }
2343
2344 TEST_F(ConstantRangeTest, USubSat) {
2345 TestBinaryOpExhaustive(
2346 [](const ConstantRange &CR1, const ConstantRange &CR2) {
2347 return CR1.usub_sat(CR2);
2348 },
2349 [](const APInt &N1, const APInt &N2) {
2350 return N1.usub_sat(N2);
2351 },
2352 PreferSmallestUnsigned);
2353 }
2354
2355 TEST_F(ConstantRangeTest, UMulSat) {
2356 TestBinaryOpExhaustive(
2357 [](const ConstantRange &CR1, const ConstantRange &CR2) {
2358 return CR1.umul_sat(CR2);
2359 },
2360 [](const APInt &N1, const APInt &N2) { return N1.umul_sat(N2); },
2361 PreferSmallestUnsigned);
2362 }
2363
2364 TEST_F(ConstantRangeTest, UShlSat) {
2365 TestBinaryOpExhaustive(
2366 [](const ConstantRange &CR1, const ConstantRange &CR2) {
2367 return CR1.ushl_sat(CR2);
2368 },
2369 [](const APInt &N1, const APInt &N2) { return N1.ushl_sat(N2); },
2370 PreferSmallestUnsigned);
2371 }
2372
2373 TEST_F(ConstantRangeTest, SAddSat) {
2374 TestBinaryOpExhaustive(
2375 [](const ConstantRange &CR1, const ConstantRange &CR2) {
2376 return CR1.sadd_sat(CR2);
2377 },
2378 [](const APInt &N1, const APInt &N2) {
2379 return N1.sadd_sat(N2);
2380 },
2381 PreferSmallestSigned);
2382 }
2383
2384 TEST_F(ConstantRangeTest, SSubSat) {
2385 TestBinaryOpExhaustive(
2386 [](const ConstantRange &CR1, const ConstantRange &CR2) {
2387 return CR1.ssub_sat(CR2);
2388 },
2389 [](const APInt &N1, const APInt &N2) {
2390 return N1.ssub_sat(N2);
2391 },
2392 PreferSmallestSigned);
2393 }
2394
2395 TEST_F(ConstantRangeTest, SMulSat) {
2396 TestBinaryOpExhaustive(
2397 [](const ConstantRange &CR1, const ConstantRange &CR2) {
2398 return CR1.smul_sat(CR2);
2399 },
2400 [](const APInt &N1, const APInt &N2) { return N1.smul_sat(N2); },
2401 PreferSmallestSigned);
2402 }
2403
2404 TEST_F(ConstantRangeTest, SShlSat) {
2405 TestBinaryOpExhaustive(
2406 [](const ConstantRange &CR1, const ConstantRange &CR2) {
2407 return CR1.sshl_sat(CR2);
2408 },
2409 [](const APInt &N1, const APInt &N2) { return N1.sshl_sat(N2); },
2410 PreferSmallestSigned);
2411 }
2412
2413 TEST_F(ConstantRangeTest, Abs) {
2414 TestUnaryOpExhaustive(
2415 [](const ConstantRange &CR) { return CR.abs(); },
2416 [](const APInt &N) { return N.abs(); });
2417
2418 TestUnaryOpExhaustive(
2419 [](const ConstantRange &CR) { return CR.abs(/*IntMinIsPoison=*/true); },
2420 [](const APInt &N) -> std::optional<APInt> {
2421 if (N.isMinSignedValue())
2422 return std::nullopt;
2423 return N.abs();
2424 });
2425 }
2426
2427 TEST_F(ConstantRangeTest, Ctlz) {
2428 TestUnaryOpExhaustive(
2429 [](const ConstantRange &CR) { return CR.ctlz(); },
2430 [](const APInt &N) { return APInt(N.getBitWidth(), N.countl_zero()); });
2431
2432 TestUnaryOpExhaustive(
2433 [](const ConstantRange &CR) { return CR.ctlz(/*ZeroIsPoison=*/true); },
2434 [](const APInt &N) -> std::optional<APInt> {
2435 if (N.isZero())
2436 return std::nullopt;
2437 return APInt(N.getBitWidth(), N.countl_zero());
2438 });
2439 }
2440
2441 TEST_F(ConstantRangeTest, castOps) {
2442 ConstantRange A(APInt(16, 66), APInt(16, 128));
2443 ConstantRange FpToI8 = A.castOp(Instruction::FPToSI, 8);
2444 EXPECT_EQ(8u, FpToI8.getBitWidth());
2445 EXPECT_TRUE(FpToI8.isFullSet());
2446
2447 ConstantRange FpToI16 = A.castOp(Instruction::FPToSI, 16);
2448 EXPECT_EQ(16u, FpToI16.getBitWidth());
2449 EXPECT_EQ(A, FpToI16);
2450
2451 ConstantRange FPExtToDouble = A.castOp(Instruction::FPExt, 64);
2452 EXPECT_EQ(64u, FPExtToDouble.getBitWidth());
2453 EXPECT_TRUE(FPExtToDouble.isFullSet());
2454
2455 ConstantRange PtrToInt = A.castOp(Instruction::PtrToInt, 64);
2456 EXPECT_EQ(64u, PtrToInt.getBitWidth());
2457 EXPECT_TRUE(PtrToInt.isFullSet());
2458
2459 ConstantRange IntToPtr = A.castOp(Instruction::IntToPtr, 64);
2460 EXPECT_EQ(64u, IntToPtr.getBitWidth());
2461 EXPECT_TRUE(IntToPtr.isFullSet());
2462 }
2463
2464 TEST_F(ConstantRangeTest, binaryAnd) {
2465 // Single element ranges.
2466 ConstantRange R16(APInt(8, 16));
2467 ConstantRange R20(APInt(8, 20));
2468 EXPECT_EQ(*R16.binaryAnd(R16).getSingleElement(), APInt(8, 16));
2469 EXPECT_EQ(*R16.binaryAnd(R20).getSingleElement(), APInt(8, 16 & 20));
2470
2471 ConstantRange R16_32(APInt(8, 16), APInt(8, 32));
2472 // 'And' with a high bits mask.
2473 ConstantRange R32(APInt(8, 32));
2474 EXPECT_TRUE(R16_32.binaryAnd(R32).getSingleElement()->isZero());
2475 EXPECT_TRUE(R32.binaryAnd(R16_32).getSingleElement()->isZero());
2476 // 'And' with a low bits mask. Handled conservatively for now.
2477 ConstantRange R4(APInt(8, 4));
2478 ConstantRange R0_5(APInt(8, 0), APInt(8, 5));
2479 EXPECT_EQ(R16_32.binaryAnd(R4), R0_5);
2480 EXPECT_EQ(R4.binaryAnd(R16_32), R0_5);
2481
2482 // Ranges with more than one element. Handled conservatively for now.
2483 ConstantRange R0_99(APInt(8, 0), APInt(8, 99));
2484 ConstantRange R0_32(APInt(8, 0), APInt(8, 32));
2485 EXPECT_EQ(R16_32.binaryAnd(R0_99), R0_32);
2486 EXPECT_EQ(R0_99.binaryAnd(R16_32), R0_32);
2487
2488 TestBinaryOpExhaustive(
2489 [](const ConstantRange &CR1, const ConstantRange &CR2) {
2490 return CR1.binaryAnd(CR2);
2491 },
2492 [](const APInt &N1, const APInt &N2) { return N1 & N2; }, PreferSmallest,
2493 CheckSingleElementsOnly);
2494 }
2495
2496 TEST_F(ConstantRangeTest, binaryOr) {
2497 // Single element ranges.
2498 ConstantRange R16(APInt(8, 16));
2499 ConstantRange R20(APInt(8, 20));
2500 EXPECT_EQ(*R16.binaryOr(R16).getSingleElement(), APInt(8, 16));
2501 EXPECT_EQ(*R16.binaryOr(R20).getSingleElement(), APInt(8, 16 | 20));
2502
2503 ConstantRange R16_32(APInt(8, 16), APInt(8, 32));
2504 // 'Or' with a high bits mask.
2505 // KnownBits estimate is important, otherwise the maximum included element
2506 // would be 2^8 - 1.
2507 ConstantRange R32(APInt(8, 32));
2508 ConstantRange R48_64(APInt(8, 48), APInt(8, 64));
2509 EXPECT_EQ(R16_32.binaryOr(R32), R48_64);
2510 EXPECT_EQ(R32.binaryOr(R16_32), R48_64);
2511 // 'Or' with a low bits mask.
2512 ConstantRange R4(APInt(8, 4));
2513 ConstantRange R0_16(APInt(8, 0), APInt(8, 16));
2514 ConstantRange R4_16(APInt(8, 4), APInt(8, 16));
2515 EXPECT_EQ(R0_16.binaryOr(R4), R4_16);
2516 EXPECT_EQ(R4.binaryOr(R0_16), R4_16);
2517
2518 // Ranges with more than one element. Handled conservatively for now.
2519 // UMaxUMin estimate is important, otherwise the lower bound would be zero.
2520 ConstantRange R0_64(APInt(8, 0), APInt(8, 64));
2521 ConstantRange R5_32(APInt(8, 5), APInt(8, 32));
2522 ConstantRange R5_64(APInt(8, 5), APInt(8, 64));
2523 EXPECT_EQ(R0_64.binaryOr(R5_32), R5_64);
2524 EXPECT_EQ(R5_32.binaryOr(R0_64), R5_64);
2525
2526 TestBinaryOpExhaustive(
2527 [](const ConstantRange &CR1, const ConstantRange &CR2) {
2528 return CR1.binaryOr(CR2);
2529 },
2530 [](const APInt &N1, const APInt &N2) { return N1 | N2; }, PreferSmallest,
2531 CheckSingleElementsOnly);
2532 }
2533
2534 TEST_F(ConstantRangeTest, binaryXor) {
2535 // Single element ranges.
2536 ConstantRange R16(APInt(8, 16));
2537 ConstantRange R20(APInt(8, 20));
2538 EXPECT_EQ(*R16.binaryXor(R16).getSingleElement(), APInt(8, 0));
2539 EXPECT_EQ(*R16.binaryXor(R20).getSingleElement(), APInt(8, 16 ^ 20));
2540
2541 // Ranges with more than a single element.
2542 ConstantRange R16_35(APInt(8, 16), APInt(8, 35));
2543 ConstantRange R0_99(APInt(8, 0), APInt(8, 99));
2544 EXPECT_EQ(R16_35.binaryXor(R16_35), ConstantRange(APInt(8, 0), APInt(8, 64)));
2545 EXPECT_EQ(R16_35.binaryXor(R0_99), ConstantRange(APInt(8, 0), APInt(8, 128)));
2546 EXPECT_EQ(R0_99.binaryXor(R16_35), ConstantRange(APInt(8, 0), APInt(8, 128)));
2547
2548 TestBinaryOpExhaustive(
2549 [](const ConstantRange &CR1, const ConstantRange &CR2) {
2550 return CR1.binaryXor(CR2);
2551 },
2552 [](const APInt &N1, const APInt &N2) {
2553 return N1 ^ N2;
2554 },
2555 PreferSmallest,
2556 CheckSingleElementsOnly);
2557 }
2558
2559 TEST_F(ConstantRangeTest, binaryNot) {
2560 TestUnaryOpExhaustive(
2561 [](const ConstantRange &CR) { return CR.binaryNot(); },
2562 [](const APInt &N) { return ~N; },
2563 PreferSmallest);
2564 TestUnaryOpExhaustive(
2565 [](const ConstantRange &CR) {
2566 return CR.binaryXor(ConstantRange(APInt::getAllOnes(CR.getBitWidth())));
2567 },
2568 [](const APInt &N) { return ~N; }, PreferSmallest);
2569 TestUnaryOpExhaustive(
2570 [](const ConstantRange &CR) {
2571 return ConstantRange(APInt::getAllOnes(CR.getBitWidth())).binaryXor(CR);
2572 },
2573 [](const APInt &N) { return ~N; }, PreferSmallest);
2574 }
2575
2576 template <typename T>
2577 void testConstantRangeICmpPredEquivalence(ICmpInst::Predicate SrcPred, T Func) {
2578 EnumerateTwoInterestingConstantRanges(
2579 [&](const ConstantRange &CR1, const ConstantRange &CR2) {
2580 ICmpInst::Predicate TgtPred;
2581 bool ExpectedEquivalent;
2582 std::tie(TgtPred, ExpectedEquivalent) = Func(CR1, CR2);
2583 if (TgtPred == CmpInst::Predicate::BAD_ICMP_PREDICATE)
2584 return;
2585 bool TrulyEquivalent = true;
2586 ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
2587 if (!TrulyEquivalent)
2588 return;
2589 ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
2590 if (!TrulyEquivalent)
2591 return;
2592 TrulyEquivalent &= ICmpInst::compare(N1, N2, SrcPred) ==
2593 ICmpInst::compare(N1, N2, TgtPred);
2594 });
2595 });
2596 ASSERT_EQ(TrulyEquivalent, ExpectedEquivalent);
2597 });
2598 }
2599
2600 TEST_F(ConstantRangeTest, areInsensitiveToSignednessOfICmpPredicate) {
2601 for (auto Pred : ICmpInst::predicates()) {
2602 if (ICmpInst::isEquality(Pred))
2603 continue;
2604 ICmpInst::Predicate FlippedSignednessPred =
2605 ICmpInst::getFlippedSignednessPredicate(Pred);
2606 testConstantRangeICmpPredEquivalence(Pred, [FlippedSignednessPred](
2607 const ConstantRange &CR1,
2608 const ConstantRange &CR2) {
2609 return std::make_pair(
2610 FlippedSignednessPred,
2611 ConstantRange::areInsensitiveToSignednessOfICmpPredicate(CR1, CR2));
2612 });
2613 }
2614 }
2615
2616 TEST_F(ConstantRangeTest, areInsensitiveToSignednessOfInvertedICmpPredicate) {
2617 for (auto Pred : ICmpInst::predicates()) {
2618 if (ICmpInst::isEquality(Pred))
2619 continue;
2620 ICmpInst::Predicate InvertedFlippedSignednessPred =
2621 ICmpInst::getInversePredicate(
2622 ICmpInst::getFlippedSignednessPredicate(Pred));
2623 testConstantRangeICmpPredEquivalence(
2624 Pred, [InvertedFlippedSignednessPred](const ConstantRange &CR1,
2625 const ConstantRange &CR2) {
2626 return std::make_pair(
2627 InvertedFlippedSignednessPred,
2628 ConstantRange::areInsensitiveToSignednessOfInvertedICmpPredicate(
2629 CR1, CR2));
2630 });
2631 }
2632 }
2633
2634 TEST_F(ConstantRangeTest, getEquivalentPredWithFlippedSignedness) {
2635 for (auto Pred : ICmpInst::predicates()) {
2636 if (ICmpInst::isEquality(Pred))
2637 continue;
2638 testConstantRangeICmpPredEquivalence(
2639 Pred, [Pred](const ConstantRange &CR1, const ConstantRange &CR2) {
2640 return std::make_pair(
2641 ConstantRange::getEquivalentPredWithFlippedSignedness(Pred, CR1,
2642 CR2),
2643 /*ExpectedEquivalent=*/true);
2644 });
2645 }
2646 }
2647
2648 TEST_F(ConstantRangeTest, isSizeLargerThan) {
2649 EXPECT_FALSE(Empty.isSizeLargerThan(0));
2650
2651 EXPECT_TRUE(Full.isSizeLargerThan(0));
2652 EXPECT_TRUE(Full.isSizeLargerThan(65535));
2653 EXPECT_FALSE(Full.isSizeLargerThan(65536));
2654
2655 EXPECT_TRUE(One.isSizeLargerThan(0));
2656 EXPECT_FALSE(One.isSizeLargerThan(1));
2657 }
2658
2659 } // anonymous namespace
LLVM monorepo