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