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