?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Recommit "rL366894: [yaml2obj] - Allow custom fields for the SHT_UNDEF sections."
[llvm-complete.git] / unittests / IR / ConstantRangeTest.cpp
blobc0166b21039c8815712b08d8f8ca07d6d6ef9bb2
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/ADT/BitVector.h"
10 #include "llvm/IR/ConstantRange.h"
11 #include "llvm/IR/Instructions.h"
12 #include "llvm/IR/Operator.h"
13 #include "llvm/Support/KnownBits.h"
14 #include "gtest/gtest.h"
15
16 using namespace llvm;
17
18 namespace {
19
20 class ConstantRangeTest : public ::testing::Test {
21 protected:
22 static ConstantRange Full;
23 static ConstantRange Empty;
24 static ConstantRange One;
25 static ConstantRange Some;
26 static ConstantRange Wrap;
27 };
28
29 template<typename Fn>
30 static void EnumerateConstantRanges(unsigned Bits, Fn TestFn) {
31 unsigned Max = 1 << Bits;
32 for (unsigned Lo = 0; Lo < Max; Lo++) {
33 for (unsigned Hi = 0; Hi < Max; Hi++) {
34 // Enforce ConstantRange invariant.
35 if (Lo == Hi && Lo != 0 && Lo != Max - 1)
36 continue;
37
38 ConstantRange CR(APInt(Bits, Lo), APInt(Bits, Hi));
39 TestFn(CR);
40 }
41 }
42 }
43
44 template<typename Fn>
45 static void EnumerateTwoConstantRanges(unsigned Bits, Fn TestFn) {
46 EnumerateConstantRanges(Bits, [&](const ConstantRange &CR1) {
47 EnumerateConstantRanges(Bits, [&](const ConstantRange &CR2) {
48 TestFn(CR1, CR2);
49 });
50 });
51 }
52
53 template<typename Fn>
54 static void ForeachNumInConstantRange(const ConstantRange &CR, Fn TestFn) {
55 if (!CR.isEmptySet()) {
56 APInt N = CR.getLower();
57 do TestFn(N);
58 while (++N != CR.getUpper());
59 }
60 }
61
62 template<typename Fn1, typename Fn2>
63 static void TestUnsignedBinOpExhaustive(
64 Fn1 RangeFn, Fn2 IntFn,
65 bool SkipZeroRHS = false, bool CorrectnessOnly = false) {
66 unsigned Bits = 4;
67 EnumerateTwoConstantRanges(Bits, [&](const ConstantRange &CR1,
68 const ConstantRange &CR2) {
69 APInt Min = APInt::getMaxValue(Bits);
70 APInt Max = APInt::getMinValue(Bits);
71 ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
72 ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
73 if (SkipZeroRHS && N2 == 0)
74 return;
75
76 APInt N = IntFn(N1, N2);
77 if (N.ult(Min))
78 Min = N;
79 if (N.ugt(Max))
80 Max = N;
81 });
82 });
83
84 ConstantRange CR = RangeFn(CR1, CR2);
85 if (Min.ugt(Max)) {
86 EXPECT_TRUE(CR.isEmptySet());
87 return;
88 }
89
90 ConstantRange Exact = ConstantRange::getNonEmpty(Min, Max + 1);
91 if (CorrectnessOnly) {
92 EXPECT_TRUE(CR.contains(Exact));
93 } else {
94 EXPECT_EQ(Exact, CR);
95 }
96 });
97 }
98
99 template<typename Fn1, typename Fn2>
100 static void TestSignedBinOpExhaustive(
101 Fn1 RangeFn, Fn2 IntFn,
102 bool SkipZeroRHS = false, bool CorrectnessOnly = false) {
103 unsigned Bits = 4;
104 EnumerateTwoConstantRanges(Bits, [&](const ConstantRange &CR1,
105 const ConstantRange &CR2) {
106 APInt Min = APInt::getSignedMaxValue(Bits);
107 APInt Max = APInt::getSignedMinValue(Bits);
108 ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
109 ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
110 if (SkipZeroRHS && N2 == 0)
111 return;
112
113 APInt N = IntFn(N1, N2);
114 if (N.slt(Min))
115 Min = N;
116 if (N.sgt(Max))
117 Max = N;
118 });
119 });
120
121 ConstantRange CR = RangeFn(CR1, CR2);
122 if (Min.sgt(Max)) {
123 EXPECT_TRUE(CR.isEmptySet());
124 return;
125 }
126
127 ConstantRange Exact = ConstantRange::getNonEmpty(Min, Max + 1);
128 if (CorrectnessOnly) {
129 EXPECT_TRUE(CR.contains(Exact));
130 } else {
131 EXPECT_EQ(Exact, CR);
132 }
133 });
134 }
135
136 ConstantRange ConstantRangeTest::Full(16, true);
137 ConstantRange ConstantRangeTest::Empty(16, false);
138 ConstantRange ConstantRangeTest::One(APInt(16, 0xa));
139 ConstantRange ConstantRangeTest::Some(APInt(16, 0xa), APInt(16, 0xaaa));
140 ConstantRange ConstantRangeTest::Wrap(APInt(16, 0xaaa), APInt(16, 0xa));
141
142 TEST_F(ConstantRangeTest, Basics) {
143 EXPECT_TRUE(Full.isFullSet());
144 EXPECT_FALSE(Full.isEmptySet());
145 EXPECT_TRUE(Full.inverse().isEmptySet());
146 EXPECT_FALSE(Full.isWrappedSet());
147 EXPECT_TRUE(Full.contains(APInt(16, 0x0)));
148 EXPECT_TRUE(Full.contains(APInt(16, 0x9)));
149 EXPECT_TRUE(Full.contains(APInt(16, 0xa)));
150 EXPECT_TRUE(Full.contains(APInt(16, 0xaa9)));
151 EXPECT_TRUE(Full.contains(APInt(16, 0xaaa)));
152
153 EXPECT_FALSE(Empty.isFullSet());
154 EXPECT_TRUE(Empty.isEmptySet());
155 EXPECT_TRUE(Empty.inverse().isFullSet());
156 EXPECT_FALSE(Empty.isWrappedSet());
157 EXPECT_FALSE(Empty.contains(APInt(16, 0x0)));
158 EXPECT_FALSE(Empty.contains(APInt(16, 0x9)));
159 EXPECT_FALSE(Empty.contains(APInt(16, 0xa)));
160 EXPECT_FALSE(Empty.contains(APInt(16, 0xaa9)));
161 EXPECT_FALSE(Empty.contains(APInt(16, 0xaaa)));
162
163 EXPECT_FALSE(One.isFullSet());
164 EXPECT_FALSE(One.isEmptySet());
165 EXPECT_FALSE(One.isWrappedSet());
166 EXPECT_FALSE(One.contains(APInt(16, 0x0)));
167 EXPECT_FALSE(One.contains(APInt(16, 0x9)));
168 EXPECT_TRUE(One.contains(APInt(16, 0xa)));
169 EXPECT_FALSE(One.contains(APInt(16, 0xaa9)));
170 EXPECT_FALSE(One.contains(APInt(16, 0xaaa)));
171 EXPECT_FALSE(One.inverse().contains(APInt(16, 0xa)));
172
173 EXPECT_FALSE(Some.isFullSet());
174 EXPECT_FALSE(Some.isEmptySet());
175 EXPECT_FALSE(Some.isWrappedSet());
176 EXPECT_FALSE(Some.contains(APInt(16, 0x0)));
177 EXPECT_FALSE(Some.contains(APInt(16, 0x9)));
178 EXPECT_TRUE(Some.contains(APInt(16, 0xa)));
179 EXPECT_TRUE(Some.contains(APInt(16, 0xaa9)));
180 EXPECT_FALSE(Some.contains(APInt(16, 0xaaa)));
181
182 EXPECT_FALSE(Wrap.isFullSet());
183 EXPECT_FALSE(Wrap.isEmptySet());
184 EXPECT_TRUE(Wrap.isWrappedSet());
185 EXPECT_TRUE(Wrap.contains(APInt(16, 0x0)));
186 EXPECT_TRUE(Wrap.contains(APInt(16, 0x9)));
187 EXPECT_FALSE(Wrap.contains(APInt(16, 0xa)));
188 EXPECT_FALSE(Wrap.contains(APInt(16, 0xaa9)));
189 EXPECT_TRUE(Wrap.contains(APInt(16, 0xaaa)));
190 }
191
192 TEST_F(ConstantRangeTest, Equality) {
193 EXPECT_EQ(Full, Full);
194 EXPECT_EQ(Empty, Empty);
195 EXPECT_EQ(One, One);
196 EXPECT_EQ(Some, Some);
197 EXPECT_EQ(Wrap, Wrap);
198 EXPECT_NE(Full, Empty);
199 EXPECT_NE(Full, One);
200 EXPECT_NE(Full, Some);
201 EXPECT_NE(Full, Wrap);
202 EXPECT_NE(Empty, One);
203 EXPECT_NE(Empty, Some);
204 EXPECT_NE(Empty, Wrap);
205 EXPECT_NE(One, Some);
206 EXPECT_NE(One, Wrap);
207 EXPECT_NE(Some, Wrap);
208 }
209
210 TEST_F(ConstantRangeTest, SingleElement) {
211 EXPECT_EQ(Full.getSingleElement(), static_cast<APInt *>(nullptr));
212 EXPECT_EQ(Empty.getSingleElement(), static_cast<APInt *>(nullptr));
213 EXPECT_EQ(Full.getSingleMissingElement(), static_cast<APInt *>(nullptr));
214 EXPECT_EQ(Empty.getSingleMissingElement(), static_cast<APInt *>(nullptr));
215
216 EXPECT_EQ(*One.getSingleElement(), APInt(16, 0xa));
217 EXPECT_EQ(Some.getSingleElement(), static_cast<APInt *>(nullptr));
218 EXPECT_EQ(Wrap.getSingleElement(), static_cast<APInt *>(nullptr));
219
220 EXPECT_EQ(One.getSingleMissingElement(), static_cast<APInt *>(nullptr));
221 EXPECT_EQ(Some.getSingleMissingElement(), static_cast<APInt *>(nullptr));
222
223 ConstantRange OneInverse = One.inverse();
224 EXPECT_EQ(*OneInverse.getSingleMissingElement(), *One.getSingleElement());
225
226 EXPECT_FALSE(Full.isSingleElement());
227 EXPECT_FALSE(Empty.isSingleElement());
228 EXPECT_TRUE(One.isSingleElement());
229 EXPECT_FALSE(Some.isSingleElement());
230 EXPECT_FALSE(Wrap.isSingleElement());
231 }
232
233 TEST_F(ConstantRangeTest, GetMinsAndMaxes) {
234 EXPECT_EQ(Full.getUnsignedMax(), APInt(16, UINT16_MAX));
235 EXPECT_EQ(One.getUnsignedMax(), APInt(16, 0xa));
236 EXPECT_EQ(Some.getUnsignedMax(), APInt(16, 0xaa9));
237 EXPECT_EQ(Wrap.getUnsignedMax(), APInt(16, UINT16_MAX));
238
239 EXPECT_EQ(Full.getUnsignedMin(), APInt(16, 0));
240 EXPECT_EQ(One.getUnsignedMin(), APInt(16, 0xa));
241 EXPECT_EQ(Some.getUnsignedMin(), APInt(16, 0xa));
242 EXPECT_EQ(Wrap.getUnsignedMin(), APInt(16, 0));
243
244 EXPECT_EQ(Full.getSignedMax(), APInt(16, INT16_MAX));
245 EXPECT_EQ(One.getSignedMax(), APInt(16, 0xa));
246 EXPECT_EQ(Some.getSignedMax(), APInt(16, 0xaa9));
247 EXPECT_EQ(Wrap.getSignedMax(), APInt(16, INT16_MAX));
248
249 EXPECT_EQ(Full.getSignedMin(), APInt(16, (uint64_t)INT16_MIN));
250 EXPECT_EQ(One.getSignedMin(), APInt(16, 0xa));
251 EXPECT_EQ(Some.getSignedMin(), APInt(16, 0xa));
252 EXPECT_EQ(Wrap.getSignedMin(), APInt(16, (uint64_t)INT16_MIN));
253
254 // Found by Klee
255 EXPECT_EQ(ConstantRange(APInt(4, 7), APInt(4, 0)).getSignedMax(),
256 APInt(4, 7));
257 }
258
259 TEST_F(ConstantRangeTest, SignWrapped) {
260 EXPECT_FALSE(Full.isSignWrappedSet());
261 EXPECT_FALSE(Empty.isSignWrappedSet());
262 EXPECT_FALSE(One.isSignWrappedSet());
263 EXPECT_FALSE(Some.isSignWrappedSet());
264 EXPECT_TRUE(Wrap.isSignWrappedSet());
265
266 EXPECT_FALSE(ConstantRange(APInt(8, 127), APInt(8, 128)).isSignWrappedSet());
267 EXPECT_TRUE(ConstantRange(APInt(8, 127), APInt(8, 129)).isSignWrappedSet());
268 EXPECT_FALSE(ConstantRange(APInt(8, 128), APInt(8, 129)).isSignWrappedSet());
269 EXPECT_TRUE(ConstantRange(APInt(8, 10), APInt(8, 9)).isSignWrappedSet());
270 EXPECT_TRUE(ConstantRange(APInt(8, 10), APInt(8, 250)).isSignWrappedSet());
271 EXPECT_FALSE(ConstantRange(APInt(8, 250), APInt(8, 10)).isSignWrappedSet());
272 EXPECT_FALSE(ConstantRange(APInt(8, 250), APInt(8, 251)).isSignWrappedSet());
273 }
274
275 TEST_F(ConstantRangeTest, UpperWrapped) {
276 // The behavior here is the same as for isWrappedSet() / isSignWrappedSet().
277 EXPECT_FALSE(Full.isUpperWrapped());
278 EXPECT_FALSE(Empty.isUpperWrapped());
279 EXPECT_FALSE(One.isUpperWrapped());
280 EXPECT_FALSE(Some.isUpperWrapped());
281 EXPECT_TRUE(Wrap.isUpperWrapped());
282 EXPECT_FALSE(Full.isUpperSignWrapped());
283 EXPECT_FALSE(Empty.isUpperSignWrapped());
284 EXPECT_FALSE(One.isUpperSignWrapped());
285 EXPECT_FALSE(Some.isUpperSignWrapped());
286 EXPECT_TRUE(Wrap.isUpperSignWrapped());
287
288 // The behavior differs if Upper is the Min/SignedMin value.
289 ConstantRange CR1(APInt(8, 42), APInt::getMinValue(8));
290 EXPECT_FALSE(CR1.isWrappedSet());
291 EXPECT_TRUE(CR1.isUpperWrapped());
292
293 ConstantRange CR2(APInt(8, 42), APInt::getSignedMinValue(8));
294 EXPECT_FALSE(CR2.isSignWrappedSet());
295 EXPECT_TRUE(CR2.isUpperSignWrapped());
296 }
297
298 TEST_F(ConstantRangeTest, Trunc) {
299 ConstantRange TFull = Full.truncate(10);
300 ConstantRange TEmpty = Empty.truncate(10);
301 ConstantRange TOne = One.truncate(10);
302 ConstantRange TSome = Some.truncate(10);
303 ConstantRange TWrap = Wrap.truncate(10);
304 EXPECT_TRUE(TFull.isFullSet());
305 EXPECT_TRUE(TEmpty.isEmptySet());
306 EXPECT_EQ(TOne, ConstantRange(One.getLower().trunc(10),
307 One.getUpper().trunc(10)));
308 EXPECT_TRUE(TSome.isFullSet());
309 EXPECT_TRUE(TWrap.isFullSet());
310
311 // trunc([2, 5), 3->2) = [2, 1)
312 ConstantRange TwoFive(APInt(3, 2), APInt(3, 5));
313 EXPECT_EQ(TwoFive.truncate(2), ConstantRange(APInt(2, 2), APInt(2, 1)));
314
315 // trunc([2, 6), 3->2) = full
316 ConstantRange TwoSix(APInt(3, 2), APInt(3, 6));
317 EXPECT_TRUE(TwoSix.truncate(2).isFullSet());
318
319 // trunc([5, 7), 3->2) = [1, 3)
320 ConstantRange FiveSeven(APInt(3, 5), APInt(3, 7));
321 EXPECT_EQ(FiveSeven.truncate(2), ConstantRange(APInt(2, 1), APInt(2, 3)));
322
323 // trunc([7, 1), 3->2) = [3, 1)
324 ConstantRange SevenOne(APInt(3, 7), APInt(3, 1));
325 EXPECT_EQ(SevenOne.truncate(2), ConstantRange(APInt(2, 3), APInt(2, 1)));
326 }
327
328 TEST_F(ConstantRangeTest, ZExt) {
329 ConstantRange ZFull = Full.zeroExtend(20);
330 ConstantRange ZEmpty = Empty.zeroExtend(20);
331 ConstantRange ZOne = One.zeroExtend(20);
332 ConstantRange ZSome = Some.zeroExtend(20);
333 ConstantRange ZWrap = Wrap.zeroExtend(20);
334 EXPECT_EQ(ZFull, ConstantRange(APInt(20, 0), APInt(20, 0x10000)));
335 EXPECT_TRUE(ZEmpty.isEmptySet());
336 EXPECT_EQ(ZOne, ConstantRange(One.getLower().zext(20),
337 One.getUpper().zext(20)));
338 EXPECT_EQ(ZSome, ConstantRange(Some.getLower().zext(20),
339 Some.getUpper().zext(20)));
340 EXPECT_EQ(ZWrap, ConstantRange(APInt(20, 0), APInt(20, 0x10000)));
341
342 // zext([5, 0), 3->7) = [5, 8)
343 ConstantRange FiveZero(APInt(3, 5), APInt(3, 0));
344 EXPECT_EQ(FiveZero.zeroExtend(7), ConstantRange(APInt(7, 5), APInt(7, 8)));
345 }
346
347 TEST_F(ConstantRangeTest, SExt) {
348 ConstantRange SFull = Full.signExtend(20);
349 ConstantRange SEmpty = Empty.signExtend(20);
350 ConstantRange SOne = One.signExtend(20);
351 ConstantRange SSome = Some.signExtend(20);
352 ConstantRange SWrap = Wrap.signExtend(20);
353 EXPECT_EQ(SFull, ConstantRange(APInt(20, (uint64_t)INT16_MIN, true),
354 APInt(20, INT16_MAX + 1, true)));
355 EXPECT_TRUE(SEmpty.isEmptySet());
356 EXPECT_EQ(SOne, ConstantRange(One.getLower().sext(20),
357 One.getUpper().sext(20)));
358 EXPECT_EQ(SSome, ConstantRange(Some.getLower().sext(20),
359 Some.getUpper().sext(20)));
360 EXPECT_EQ(SWrap, ConstantRange(APInt(20, (uint64_t)INT16_MIN, true),
361 APInt(20, INT16_MAX + 1, true)));
362
363 EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, 140)).signExtend(16),
364 ConstantRange(APInt(16, -128), APInt(16, 128)));
365
366 EXPECT_EQ(ConstantRange(APInt(16, 0x0200), APInt(16, 0x8000)).signExtend(19),
367 ConstantRange(APInt(19, 0x0200), APInt(19, 0x8000)));
368 }
369
370 TEST_F(ConstantRangeTest, IntersectWith) {
371 EXPECT_EQ(Empty.intersectWith(Full), Empty);
372 EXPECT_EQ(Empty.intersectWith(Empty), Empty);
373 EXPECT_EQ(Empty.intersectWith(One), Empty);
374 EXPECT_EQ(Empty.intersectWith(Some), Empty);
375 EXPECT_EQ(Empty.intersectWith(Wrap), Empty);
376 EXPECT_EQ(Full.intersectWith(Full), Full);
377 EXPECT_EQ(Some.intersectWith(Some), Some);
378 EXPECT_EQ(Some.intersectWith(One), One);
379 EXPECT_EQ(Full.intersectWith(One), One);
380 EXPECT_EQ(Full.intersectWith(Some), Some);
381 EXPECT_EQ(Some.intersectWith(Wrap), Empty);
382 EXPECT_EQ(One.intersectWith(Wrap), Empty);
383 EXPECT_EQ(One.intersectWith(Wrap), Wrap.intersectWith(One));
384
385 // Klee generated testcase from PR4545.
386 // The intersection of i16 [4, 2) and [6, 5) is disjoint, looking like
387 // 01..4.6789ABCDEF where the dots represent values not in the intersection.
388 ConstantRange LHS(APInt(16, 4), APInt(16, 2));
389 ConstantRange RHS(APInt(16, 6), APInt(16, 5));
390 EXPECT_TRUE(LHS.intersectWith(RHS) == LHS);
391
392 // previous bug: intersection of [min, 3) and [2, max) should be 2
393 LHS = ConstantRange(APInt(32, -2147483646), APInt(32, 3));
394 RHS = ConstantRange(APInt(32, 2), APInt(32, 2147483646));
395 EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 2)));
396
397 // [2, 0) /\ [4, 3) = [2, 0)
398 LHS = ConstantRange(APInt(32, 2), APInt(32, 0));
399 RHS = ConstantRange(APInt(32, 4), APInt(32, 3));
400 EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 2), APInt(32, 0)));
401
402 // [2, 0) /\ [4, 2) = [4, 0)
403 LHS = ConstantRange(APInt(32, 2), APInt(32, 0));
404 RHS = ConstantRange(APInt(32, 4), APInt(32, 2));
405 EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 4), APInt(32, 0)));
406
407 // [4, 2) /\ [5, 1) = [5, 1)
408 LHS = ConstantRange(APInt(32, 4), APInt(32, 2));
409 RHS = ConstantRange(APInt(32, 5), APInt(32, 1));
410 EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 5), APInt(32, 1)));
411
412 // [2, 0) /\ [7, 4) = [7, 4)
413 LHS = ConstantRange(APInt(32, 2), APInt(32, 0));
414 RHS = ConstantRange(APInt(32, 7), APInt(32, 4));
415 EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 7), APInt(32, 4)));
416
417 // [4, 2) /\ [1, 0) = [1, 0)
418 LHS = ConstantRange(APInt(32, 4), APInt(32, 2));
419 RHS = ConstantRange(APInt(32, 1), APInt(32, 0));
420 EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 4), APInt(32, 2)));
421
422 // [15, 0) /\ [7, 6) = [15, 0)
423 LHS = ConstantRange(APInt(32, 15), APInt(32, 0));
424 RHS = ConstantRange(APInt(32, 7), APInt(32, 6));
425 EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 15), APInt(32, 0)));
426 }
427
428 template<typename Fn1, typename Fn2>
429 void testBinarySetOperationExhaustive(Fn1 OpFn, Fn2 InResultFn) {
430 unsigned Bits = 4;
431 EnumerateTwoConstantRanges(Bits,
432 [=](const ConstantRange &CR1, const ConstantRange &CR2) {
433 // Collect up to three contiguous unsigned ranges. The HaveInterrupt
434 // variables are used determine when we have to switch to the next
435 // range because the previous one ended.
436 APInt Lower1(Bits, 0), Upper1(Bits, 0);
437 APInt Lower2(Bits, 0), Upper2(Bits, 0);
438 APInt Lower3(Bits, 0), Upper3(Bits, 0);
439 bool HaveRange1 = false, HaveInterrupt1 = false;
440 bool HaveRange2 = false, HaveInterrupt2 = false;
441 bool HaveRange3 = false, HaveInterrupt3 = false;
442
443 APInt Num(Bits, 0);
444 for (unsigned I = 0, Limit = 1 << Bits; I < Limit; ++I, ++Num) {
445 if (!InResultFn(CR1, CR2, Num)) {
446 if (HaveRange3)
447 HaveInterrupt3 = true;
448 else if (HaveRange2)
449 HaveInterrupt2 = true;
450 else if (HaveRange1)
451 HaveInterrupt1 = true;
452 continue;
453 }
454
455 if (HaveRange3) {
456 Upper3 = Num;
457 } else if (HaveInterrupt2) {
458 HaveRange3 = true;
459 Lower3 = Upper3 = Num;
460 } else if (HaveRange2) {
461 Upper2 = Num;
462 } else if (HaveInterrupt1) {
463 HaveRange2 = true;
464 Lower2 = Upper2 = Num;
465 } else if (HaveRange1) {
466 Upper1 = Num;
467 } else {
468 HaveRange1 = true;
469 Lower1 = Upper1 = Num;
470 }
471 }
472
473 (void)HaveInterrupt3;
474 assert(!HaveInterrupt3 && "Should have at most three ranges");
475
476 ConstantRange SmallestCR = OpFn(CR1, CR2, ConstantRange::Smallest);
477 ConstantRange UnsignedCR = OpFn(CR1, CR2, ConstantRange::Unsigned);
478 ConstantRange SignedCR = OpFn(CR1, CR2, ConstantRange::Signed);
479
480 if (!HaveRange1) {
481 EXPECT_TRUE(SmallestCR.isEmptySet());
482 EXPECT_TRUE(UnsignedCR.isEmptySet());
483 EXPECT_TRUE(SignedCR.isEmptySet());
484 return;
485 }
486
487 if (!HaveRange2) {
488 if (Lower1 == Upper1 + 1) {
489 EXPECT_TRUE(SmallestCR.isFullSet());
490 EXPECT_TRUE(UnsignedCR.isFullSet());
491 EXPECT_TRUE(SignedCR.isFullSet());
492 } else {
493 ConstantRange Expected(Lower1, Upper1 + 1);
494 EXPECT_EQ(Expected, SmallestCR);
495 EXPECT_EQ(Expected, UnsignedCR);
496 EXPECT_EQ(Expected, SignedCR);
497 }
498 return;
499 }
500
501 ConstantRange Variant1(Bits, /*full*/ true);
502 ConstantRange Variant2(Bits, /*full*/ true);
503 if (!HaveRange3) {
504 // Compute the two possible ways to cover two disjoint ranges.
505 if (Lower1 != Upper2 + 1)
506 Variant1 = ConstantRange(Lower1, Upper2 + 1);
507 if (Lower2 != Upper1 + 1)
508 Variant2 = ConstantRange(Lower2, Upper1 + 1);
509 } else {
510 // If we have three ranges, the first and last one have to be adjacent
511 // to the unsigned domain. It's better to think of this as having two
512 // holes, and we can construct one range using each hole.
513 assert(Lower1.isNullValue() && Upper3.isMaxValue());
514 Variant1 = ConstantRange(Lower2, Upper1 + 1);
515 Variant2 = ConstantRange(Lower3, Upper2 + 1);
516 }
517
518 // Smallest: Smaller set, then any set.
519 if (Variant1.isSizeStrictlySmallerThan(Variant2))
520 EXPECT_EQ(Variant1, SmallestCR);
521 else if (Variant2.isSizeStrictlySmallerThan(Variant1))
522 EXPECT_EQ(Variant2, SmallestCR);
523 else
524 EXPECT_TRUE(Variant1 == SmallestCR || Variant2 == SmallestCR);
525
526 // Unsigned: Non-wrapped set, then smaller set, then any set.
527 bool Variant1Full = Variant1.isFullSet() || Variant1.isWrappedSet();
528 bool Variant2Full = Variant2.isFullSet() || Variant2.isWrappedSet();
529 if (!Variant1Full && Variant2Full)
530 EXPECT_EQ(Variant1, UnsignedCR);
531 else if (Variant1Full && !Variant2Full)
532 EXPECT_EQ(Variant2, UnsignedCR);
533 else if (Variant1.isSizeStrictlySmallerThan(Variant2))
534 EXPECT_EQ(Variant1, UnsignedCR);
535 else if (Variant2.isSizeStrictlySmallerThan(Variant1))
536 EXPECT_EQ(Variant2, UnsignedCR);
537 else
538 EXPECT_TRUE(Variant1 == UnsignedCR || Variant2 == UnsignedCR);
539
540 // Signed: Signed non-wrapped set, then smaller set, then any set.
541 Variant1Full = Variant1.isFullSet() || Variant1.isSignWrappedSet();
542 Variant2Full = Variant2.isFullSet() || Variant2.isSignWrappedSet();
543 if (!Variant1Full && Variant2Full)
544 EXPECT_EQ(Variant1, SignedCR);
545 else if (Variant1Full && !Variant2Full)
546 EXPECT_EQ(Variant2, SignedCR);
547 else if (Variant1.isSizeStrictlySmallerThan(Variant2))
548 EXPECT_EQ(Variant1, SignedCR);
549 else if (Variant2.isSizeStrictlySmallerThan(Variant1))
550 EXPECT_EQ(Variant2, SignedCR);
551 else
552 EXPECT_TRUE(Variant1 == SignedCR || Variant2 == SignedCR);
553 });
554 }
555
556 TEST_F(ConstantRangeTest, IntersectWithExhaustive) {
557 testBinarySetOperationExhaustive(
558 [](const ConstantRange &CR1, const ConstantRange &CR2,
559 ConstantRange::PreferredRangeType Type) {
560 return CR1.intersectWith(CR2, Type);
561 },
562 [](const ConstantRange &CR1, const ConstantRange &CR2, const APInt &N) {
563 return CR1.contains(N) && CR2.contains(N);
564 });
565 }
566
567 TEST_F(ConstantRangeTest, UnionWithExhaustive) {
568 testBinarySetOperationExhaustive(
569 [](const ConstantRange &CR1, const ConstantRange &CR2,
570 ConstantRange::PreferredRangeType Type) {
571 return CR1.unionWith(CR2, Type);
572 },
573 [](const ConstantRange &CR1, const ConstantRange &CR2, const APInt &N) {
574 return CR1.contains(N) || CR2.contains(N);
575 });
576 }
577
578 TEST_F(ConstantRangeTest, UnionWith) {
579 EXPECT_EQ(Wrap.unionWith(One),
580 ConstantRange(APInt(16, 0xaaa), APInt(16, 0xb)));
581 EXPECT_EQ(One.unionWith(Wrap), Wrap.unionWith(One));
582 EXPECT_EQ(Empty.unionWith(Empty), Empty);
583 EXPECT_EQ(Full.unionWith(Full), Full);
584 EXPECT_EQ(Some.unionWith(Wrap), Full);
585
586 // PR4545
587 EXPECT_EQ(ConstantRange(APInt(16, 14), APInt(16, 1)).unionWith(
588 ConstantRange(APInt(16, 0), APInt(16, 8))),
589 ConstantRange(APInt(16, 14), APInt(16, 8)));
590 EXPECT_EQ(ConstantRange(APInt(16, 6), APInt(16, 4)).unionWith(
591 ConstantRange(APInt(16, 4), APInt(16, 0))),
592 ConstantRange::getFull(16));
593 EXPECT_EQ(ConstantRange(APInt(16, 1), APInt(16, 0)).unionWith(
594 ConstantRange(APInt(16, 2), APInt(16, 1))),
595 ConstantRange::getFull(16));
596 }
597
598 TEST_F(ConstantRangeTest, SetDifference) {
599 EXPECT_EQ(Full.difference(Empty), Full);
600 EXPECT_EQ(Full.difference(Full), Empty);
601 EXPECT_EQ(Empty.difference(Empty), Empty);
602 EXPECT_EQ(Empty.difference(Full), Empty);
603
604 ConstantRange A(APInt(16, 3), APInt(16, 7));
605 ConstantRange B(APInt(16, 5), APInt(16, 9));
606 ConstantRange C(APInt(16, 3), APInt(16, 5));
607 ConstantRange D(APInt(16, 7), APInt(16, 9));
608 ConstantRange E(APInt(16, 5), APInt(16, 4));
609 ConstantRange F(APInt(16, 7), APInt(16, 3));
610 EXPECT_EQ(A.difference(B), C);
611 EXPECT_EQ(B.difference(A), D);
612 EXPECT_EQ(E.difference(A), F);
613 }
614
615 TEST_F(ConstantRangeTest, SubtractAPInt) {
616 EXPECT_EQ(Full.subtract(APInt(16, 4)), Full);
617 EXPECT_EQ(Empty.subtract(APInt(16, 4)), Empty);
618 EXPECT_EQ(Some.subtract(APInt(16, 4)),
619 ConstantRange(APInt(16, 0x6), APInt(16, 0xaa6)));
620 EXPECT_EQ(Wrap.subtract(APInt(16, 4)),
621 ConstantRange(APInt(16, 0xaa6), APInt(16, 0x6)));
622 EXPECT_EQ(One.subtract(APInt(16, 4)),
623 ConstantRange(APInt(16, 0x6)));
624 }
625
626 TEST_F(ConstantRangeTest, Add) {
627 EXPECT_EQ(Full.add(APInt(16, 4)), Full);
628 EXPECT_EQ(Full.add(Full), Full);
629 EXPECT_EQ(Full.add(Empty), Empty);
630 EXPECT_EQ(Full.add(One), Full);
631 EXPECT_EQ(Full.add(Some), Full);
632 EXPECT_EQ(Full.add(Wrap), Full);
633 EXPECT_EQ(Empty.add(Empty), Empty);
634 EXPECT_EQ(Empty.add(One), Empty);
635 EXPECT_EQ(Empty.add(Some), Empty);
636 EXPECT_EQ(Empty.add(Wrap), Empty);
637 EXPECT_EQ(Empty.add(APInt(16, 4)), Empty);
638 EXPECT_EQ(Some.add(APInt(16, 4)),
639 ConstantRange(APInt(16, 0xe), APInt(16, 0xaae)));
640 EXPECT_EQ(Wrap.add(APInt(16, 4)),
641 ConstantRange(APInt(16, 0xaae), APInt(16, 0xe)));
642 EXPECT_EQ(One.add(APInt(16, 4)),
643 ConstantRange(APInt(16, 0xe)));
644 }
645
646 TEST_F(ConstantRangeTest, AddWithNoSignedWrap) {
647 EXPECT_EQ(Empty.addWithNoSignedWrap(APInt(16, 1)), Empty);
648 EXPECT_EQ(Full.addWithNoSignedWrap(APInt(16, 1)),
649 ConstantRange(APInt(16, INT16_MIN+1), APInt(16, INT16_MIN)));
650 EXPECT_EQ(ConstantRange(APInt(8, -50), APInt(8, 50)).addWithNoSignedWrap(APInt(8, 10)),
651 ConstantRange(APInt(8, -40), APInt(8, 60)));
652 EXPECT_EQ(ConstantRange(APInt(8, -50), APInt(8, 120)).addWithNoSignedWrap(APInt(8, 10)),
653 ConstantRange(APInt(8, -40), APInt(8, INT8_MIN)));
654 EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, -10)).addWithNoSignedWrap(APInt(8, 5)),
655 ConstantRange(APInt(8, 125), APInt(8, -5)));
656 EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, -120)).addWithNoSignedWrap(APInt(8, 10)),
657 ConstantRange(APInt(8, INT8_MIN+10), APInt(8, -110)));
658
659 EXPECT_EQ(Empty.addWithNoSignedWrap(APInt(16, -1)), Empty);
660 EXPECT_EQ(Full.addWithNoSignedWrap(APInt(16, -1)),
661 ConstantRange(APInt(16, INT16_MIN), APInt(16, INT16_MAX)));
662 EXPECT_EQ(ConstantRange(APInt(8, -50), APInt(8, 50)).addWithNoSignedWrap(APInt(8, -10)),
663 ConstantRange(APInt(8, -60), APInt(8, 40)));
664 EXPECT_EQ(ConstantRange(APInt(8, -120), APInt(8, 50)).addWithNoSignedWrap(APInt(8, -10)),
665 ConstantRange(APInt(8, INT8_MIN), APInt(8, 40)));
666 EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, -120)).addWithNoSignedWrap(APInt(8, -5)),
667 ConstantRange(APInt(8, 115), APInt(8, -125)));
668 EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, -120)).addWithNoSignedWrap(APInt(8, -10)),
669 ConstantRange(APInt(8, 110), APInt(8, INT8_MIN-10)));
670 }
671
672 TEST_F(ConstantRangeTest, Sub) {
673 EXPECT_EQ(Full.sub(APInt(16, 4)), Full);
674 EXPECT_EQ(Full.sub(Full), Full);
675 EXPECT_EQ(Full.sub(Empty), Empty);
676 EXPECT_EQ(Full.sub(One), Full);
677 EXPECT_EQ(Full.sub(Some), Full);
678 EXPECT_EQ(Full.sub(Wrap), Full);
679 EXPECT_EQ(Empty.sub(Empty), Empty);
680 EXPECT_EQ(Empty.sub(One), Empty);
681 EXPECT_EQ(Empty.sub(Some), Empty);
682 EXPECT_EQ(Empty.sub(Wrap), Empty);
683 EXPECT_EQ(Empty.sub(APInt(16, 4)), Empty);
684 EXPECT_EQ(Some.sub(APInt(16, 4)),
685 ConstantRange(APInt(16, 0x6), APInt(16, 0xaa6)));
686 EXPECT_EQ(Some.sub(Some),
687 ConstantRange(APInt(16, 0xf561), APInt(16, 0xaa0)));
688 EXPECT_EQ(Wrap.sub(APInt(16, 4)),
689 ConstantRange(APInt(16, 0xaa6), APInt(16, 0x6)));
690 EXPECT_EQ(One.sub(APInt(16, 4)),
691 ConstantRange(APInt(16, 0x6)));
692 }
693
694 TEST_F(ConstantRangeTest, Multiply) {
695 EXPECT_EQ(Full.multiply(Full), Full);
696 EXPECT_EQ(Full.multiply(Empty), Empty);
697 EXPECT_EQ(Full.multiply(One), Full);
698 EXPECT_EQ(Full.multiply(Some), Full);
699 EXPECT_EQ(Full.multiply(Wrap), Full);
700 EXPECT_EQ(Empty.multiply(Empty), Empty);
701 EXPECT_EQ(Empty.multiply(One), Empty);
702 EXPECT_EQ(Empty.multiply(Some), Empty);
703 EXPECT_EQ(Empty.multiply(Wrap), Empty);
704 EXPECT_EQ(One.multiply(One), ConstantRange(APInt(16, 0xa*0xa),
705 APInt(16, 0xa*0xa + 1)));
706 EXPECT_EQ(One.multiply(Some), ConstantRange(APInt(16, 0xa*0xa),
707 APInt(16, 0xa*0xaa9 + 1)));
708 EXPECT_EQ(One.multiply(Wrap), Full);
709 EXPECT_EQ(Some.multiply(Some), Full);
710 EXPECT_EQ(Some.multiply(Wrap), Full);
711 EXPECT_EQ(Wrap.multiply(Wrap), Full);
712
713 ConstantRange Zero(APInt(16, 0));
714 EXPECT_EQ(Zero.multiply(Full), Zero);
715 EXPECT_EQ(Zero.multiply(Some), Zero);
716 EXPECT_EQ(Zero.multiply(Wrap), Zero);
717 EXPECT_EQ(Full.multiply(Zero), Zero);
718 EXPECT_EQ(Some.multiply(Zero), Zero);
719 EXPECT_EQ(Wrap.multiply(Zero), Zero);
720
721 // http://llvm.org/PR4545
722 EXPECT_EQ(ConstantRange(APInt(4, 1), APInt(4, 6)).multiply(
723 ConstantRange(APInt(4, 6), APInt(4, 2))),
724 ConstantRange(4, /*isFullSet=*/true));
725
726 EXPECT_EQ(ConstantRange(APInt(8, 254), APInt(8, 0)).multiply(
727 ConstantRange(APInt(8, 252), APInt(8, 4))),
728 ConstantRange(APInt(8, 250), APInt(8, 9)));
729 EXPECT_EQ(ConstantRange(APInt(8, 254), APInt(8, 255)).multiply(
730 ConstantRange(APInt(8, 2), APInt(8, 4))),
731 ConstantRange(APInt(8, 250), APInt(8, 253)));
732
733 // TODO: This should be return [-2, 0]
734 EXPECT_EQ(ConstantRange(APInt(8, -2)).multiply(
735 ConstantRange(APInt(8, 0), APInt(8, 2))),
736 ConstantRange(APInt(8, -2), APInt(8, 1)));
737 }
738
739 TEST_F(ConstantRangeTest, UMax) {
740 EXPECT_EQ(Full.umax(Full), Full);
741 EXPECT_EQ(Full.umax(Empty), Empty);
742 EXPECT_EQ(Full.umax(Some), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
743 EXPECT_EQ(Full.umax(Wrap), Full);
744 EXPECT_EQ(Full.umax(Some), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
745 EXPECT_EQ(Empty.umax(Empty), Empty);
746 EXPECT_EQ(Empty.umax(Some), Empty);
747 EXPECT_EQ(Empty.umax(Wrap), Empty);
748 EXPECT_EQ(Empty.umax(One), Empty);
749 EXPECT_EQ(Some.umax(Some), Some);
750 EXPECT_EQ(Some.umax(Wrap), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
751 EXPECT_EQ(Some.umax(One), Some);
752 // TODO: ConstantRange is currently over-conservative here.
753 EXPECT_EQ(Wrap.umax(Wrap), Full);
754 EXPECT_EQ(Wrap.umax(One), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
755 EXPECT_EQ(One.umax(One), One);
756 }
757
758 TEST_F(ConstantRangeTest, SMax) {
759 EXPECT_EQ(Full.smax(Full), Full);
760 EXPECT_EQ(Full.smax(Empty), Empty);
761 EXPECT_EQ(Full.smax(Some), ConstantRange(APInt(16, 0xa),
762 APInt::getSignedMinValue(16)));
763 EXPECT_EQ(Full.smax(Wrap), Full);
764 EXPECT_EQ(Full.smax(One), ConstantRange(APInt(16, 0xa),
765 APInt::getSignedMinValue(16)));
766 EXPECT_EQ(Empty.smax(Empty), Empty);
767 EXPECT_EQ(Empty.smax(Some), Empty);
768 EXPECT_EQ(Empty.smax(Wrap), Empty);
769 EXPECT_EQ(Empty.smax(One), Empty);
770 EXPECT_EQ(Some.smax(Some), Some);
771 EXPECT_EQ(Some.smax(Wrap), ConstantRange(APInt(16, 0xa),
772 APInt(16, (uint64_t)INT16_MIN)));
773 EXPECT_EQ(Some.smax(One), Some);
774 EXPECT_EQ(Wrap.smax(One), ConstantRange(APInt(16, 0xa),
775 APInt(16, (uint64_t)INT16_MIN)));
776 EXPECT_EQ(One.smax(One), One);
777 }
778
779 TEST_F(ConstantRangeTest, UMin) {
780 EXPECT_EQ(Full.umin(Full), Full);
781 EXPECT_EQ(Full.umin(Empty), Empty);
782 EXPECT_EQ(Full.umin(Some), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
783 EXPECT_EQ(Full.umin(Wrap), Full);
784 EXPECT_EQ(Empty.umin(Empty), Empty);
785 EXPECT_EQ(Empty.umin(Some), Empty);
786 EXPECT_EQ(Empty.umin(Wrap), Empty);
787 EXPECT_EQ(Empty.umin(One), Empty);
788 EXPECT_EQ(Some.umin(Some), Some);
789 EXPECT_EQ(Some.umin(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
790 EXPECT_EQ(Some.umin(One), One);
791 // TODO: ConstantRange is currently over-conservative here.
792 EXPECT_EQ(Wrap.umin(Wrap), Full);
793 EXPECT_EQ(Wrap.umin(One), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
794 EXPECT_EQ(One.umin(One), One);
795 }
796
797 TEST_F(ConstantRangeTest, SMin) {
798 EXPECT_EQ(Full.smin(Full), Full);
799 EXPECT_EQ(Full.smin(Empty), Empty);
800 EXPECT_EQ(Full.smin(Some), ConstantRange(APInt(16, (uint64_t)INT16_MIN),
801 APInt(16, 0xaaa)));
802 EXPECT_EQ(Full.smin(Wrap), Full);
803 EXPECT_EQ(Empty.smin(Empty), Empty);
804 EXPECT_EQ(Empty.smin(Some), Empty);
805 EXPECT_EQ(Empty.smin(Wrap), Empty);
806 EXPECT_EQ(Empty.smin(One), Empty);
807 EXPECT_EQ(Some.smin(Some), Some);
808 EXPECT_EQ(Some.smin(Wrap), ConstantRange(APInt(16, (uint64_t)INT16_MIN),
809 APInt(16, 0xaaa)));
810 EXPECT_EQ(Some.smin(One), One);
811 // TODO: ConstantRange is currently over-conservative here.
812 EXPECT_EQ(Wrap.smin(Wrap), Full);
813 EXPECT_EQ(Wrap.smin(One), ConstantRange(APInt(16, (uint64_t)INT16_MIN),
814 APInt(16, 0xb)));
815 EXPECT_EQ(One.smin(One), One);
816 }
817
818 TEST_F(ConstantRangeTest, UDiv) {
819 EXPECT_EQ(Full.udiv(Full), Full);
820 EXPECT_EQ(Full.udiv(Empty), Empty);
821 EXPECT_EQ(Full.udiv(One), ConstantRange(APInt(16, 0),
822 APInt(16, 0xffff / 0xa + 1)));
823 EXPECT_EQ(Full.udiv(Some), ConstantRange(APInt(16, 0),
824 APInt(16, 0xffff / 0xa + 1)));
825 EXPECT_EQ(Full.udiv(Wrap), Full);
826 EXPECT_EQ(Empty.udiv(Empty), Empty);
827 EXPECT_EQ(Empty.udiv(One), Empty);
828 EXPECT_EQ(Empty.udiv(Some), Empty);
829 EXPECT_EQ(Empty.udiv(Wrap), Empty);
830 EXPECT_EQ(One.udiv(One), ConstantRange(APInt(16, 1)));
831 EXPECT_EQ(One.udiv(Some), ConstantRange(APInt(16, 0), APInt(16, 2)));
832 EXPECT_EQ(One.udiv(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
833 EXPECT_EQ(Some.udiv(Some), ConstantRange(APInt(16, 0), APInt(16, 0x111)));
834 EXPECT_EQ(Some.udiv(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
835 EXPECT_EQ(Wrap.udiv(Wrap), Full);
836
837
838 ConstantRange Zero(APInt(16, 0));
839 EXPECT_EQ(Zero.udiv(One), Zero);
840 EXPECT_EQ(Zero.udiv(Full), Zero);
841
842 EXPECT_EQ(ConstantRange(APInt(16, 0), APInt(16, 99)).udiv(Full),
843 ConstantRange(APInt(16, 0), APInt(16, 99)));
844 EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 99)).udiv(Full),
845 ConstantRange(APInt(16, 0), APInt(16, 99)));
846 }
847
848 TEST_F(ConstantRangeTest, SDiv) {
849 unsigned Bits = 4;
850 EnumerateTwoConstantRanges(Bits, [&](const ConstantRange &CR1,
851 const ConstantRange &CR2) {
852 // Collect possible results in a bit vector. We store the signed value plus
853 // a bias to make it unsigned.
854 int Bias = 1 << (Bits - 1);
855 BitVector Results(1 << Bits);
856 ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
857 ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
858 // Division by zero is UB.
859 if (N2 == 0)
860 return;
861
862 // SignedMin / -1 is UB.
863 if (N1.isMinSignedValue() && N2.isAllOnesValue())
864 return;
865
866 APInt N = N1.sdiv(N2);
867 Results.set(N.getSExtValue() + Bias);
868 });
869 });
870
871 ConstantRange CR = CR1.sdiv(CR2);
872 if (Results.none()) {
873 EXPECT_TRUE(CR.isEmptySet());
874 return;
875 }
876
877 // If there is a non-full signed envelope, that should be the result.
878 APInt SMin(Bits, Results.find_first() - Bias);
879 APInt SMax(Bits, Results.find_last() - Bias);
880 ConstantRange Envelope = ConstantRange::getNonEmpty(SMin, SMax + 1);
881 if (!Envelope.isFullSet()) {
882 EXPECT_EQ(Envelope, CR);
883 return;
884 }
885
886 // If the signed envelope is a full set, try to find a smaller sign wrapped
887 // set that is separated in negative and positive components (or one which
888 // can also additionally contain zero).
889 int LastNeg = Results.find_last_in(0, Bias) - Bias;
890 int LastPos = Results.find_next(Bias) - Bias;
891 if (Results[Bias]) {
892 if (LastNeg == -1)
893 ++LastNeg;
894 else if (LastPos == 1)
895 --LastPos;
896 }
897
898 APInt WMax(Bits, LastNeg);
899 APInt WMin(Bits, LastPos);
900 ConstantRange Wrapped = ConstantRange::getNonEmpty(WMin, WMax + 1);
901 EXPECT_EQ(Wrapped, CR);
902 });
903 }
904
905 TEST_F(ConstantRangeTest, URem) {
906 EXPECT_EQ(Full.urem(Empty), Empty);
907 EXPECT_EQ(Empty.urem(Full), Empty);
908 // urem by zero is poison.
909 EXPECT_EQ(Full.urem(ConstantRange(APInt(16, 0))), Empty);
910 // urem by full range doesn't contain MaxValue.
911 EXPECT_EQ(Full.urem(Full), ConstantRange(APInt(16, 0), APInt(16, 0xffff)));
912 // urem is upper bounded by maximum RHS minus one.
913 EXPECT_EQ(Full.urem(ConstantRange(APInt(16, 0), APInt(16, 123))),
914 ConstantRange(APInt(16, 0), APInt(16, 122)));
915 // urem is upper bounded by maximum LHS.
916 EXPECT_EQ(ConstantRange(APInt(16, 0), APInt(16, 123)).urem(Full),
917 ConstantRange(APInt(16, 0), APInt(16, 123)));
918 // If the LHS is always lower than the RHS, the result is the LHS.
919 EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 20))
920 .urem(ConstantRange(APInt(16, 20), APInt(16, 30))),
921 ConstantRange(APInt(16, 10), APInt(16, 20)));
922 // It has to be strictly lower, otherwise the top value may wrap to zero.
923 EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 20))
924 .urem(ConstantRange(APInt(16, 19), APInt(16, 30))),
925 ConstantRange(APInt(16, 0), APInt(16, 20)));
926 // [12, 14] % 10 is [2, 4], but we conservatively compute [0, 9].
927 EXPECT_EQ(ConstantRange(APInt(16, 12), APInt(16, 15))
928 .urem(ConstantRange(APInt(16, 10))),
929 ConstantRange(APInt(16, 0), APInt(16, 10)));
930
931 TestUnsignedBinOpExhaustive(
932 [](const ConstantRange &CR1, const ConstantRange &CR2) {
933 return CR1.urem(CR2);
934 },
935 [](const APInt &N1, const APInt &N2) {
936 return N1.urem(N2);
937 },
938 /* SkipZeroRHS */ true, /* CorrectnessOnly */ true);
939 }
940
941 TEST_F(ConstantRangeTest, SRem) {
942 EXPECT_EQ(Full.srem(Empty), Empty);
943 EXPECT_EQ(Empty.srem(Full), Empty);
944 // srem by zero is UB.
945 EXPECT_EQ(Full.srem(ConstantRange(APInt(16, 0))), Empty);
946 // srem by full range doesn't contain SignedMinValue.
947 EXPECT_EQ(Full.srem(Full), ConstantRange(APInt::getSignedMinValue(16) + 1,
948 APInt::getSignedMinValue(16)));
949
950 ConstantRange PosMod(APInt(16, 10), APInt(16, 21)); // [10, 20]
951 ConstantRange NegMod(APInt(16, -20), APInt(16, -9)); // [-20, -10]
952 ConstantRange IntMinMod(APInt::getSignedMinValue(16));
953
954 ConstantRange Expected(16, true);
955
956 // srem is bounded by abs(RHS) minus one.
957 ConstantRange PosLargeLHS(APInt(16, 0), APInt(16, 41));
958 Expected = ConstantRange(APInt(16, 0), APInt(16, 20));
959 EXPECT_EQ(PosLargeLHS.srem(PosMod), Expected);
960 EXPECT_EQ(PosLargeLHS.srem(NegMod), Expected);
961 ConstantRange NegLargeLHS(APInt(16, -40), APInt(16, 1));
962 Expected = ConstantRange(APInt(16, -19), APInt(16, 1));
963 EXPECT_EQ(NegLargeLHS.srem(PosMod), Expected);
964 EXPECT_EQ(NegLargeLHS.srem(NegMod), Expected);
965 ConstantRange PosNegLargeLHS(APInt(16, -32), APInt(16, 38));
966 Expected = ConstantRange(APInt(16, -19), APInt(16, 20));
967 EXPECT_EQ(PosNegLargeLHS.srem(PosMod), Expected);
968 EXPECT_EQ(PosNegLargeLHS.srem(NegMod), Expected);
969
970 // srem is bounded by LHS.
971 ConstantRange PosLHS(APInt(16, 0), APInt(16, 16));
972 EXPECT_EQ(PosLHS.srem(PosMod), PosLHS);
973 EXPECT_EQ(PosLHS.srem(NegMod), PosLHS);
974 EXPECT_EQ(PosLHS.srem(IntMinMod), PosLHS);
975 ConstantRange NegLHS(APInt(16, -15), APInt(16, 1));
976 EXPECT_EQ(NegLHS.srem(PosMod), NegLHS);
977 EXPECT_EQ(NegLHS.srem(NegMod), NegLHS);
978 EXPECT_EQ(NegLHS.srem(IntMinMod), NegLHS);
979 ConstantRange PosNegLHS(APInt(16, -12), APInt(16, 18));
980 EXPECT_EQ(PosNegLHS.srem(PosMod), PosNegLHS);
981 EXPECT_EQ(PosNegLHS.srem(NegMod), PosNegLHS);
982 EXPECT_EQ(PosNegLHS.srem(IntMinMod), PosNegLHS);
983
984 // srem is LHS if it is smaller than RHS.
985 ConstantRange PosSmallLHS(APInt(16, 3), APInt(16, 8));
986 EXPECT_EQ(PosSmallLHS.srem(PosMod), PosSmallLHS);
987 EXPECT_EQ(PosSmallLHS.srem(NegMod), PosSmallLHS);
988 EXPECT_EQ(PosSmallLHS.srem(IntMinMod), PosSmallLHS);
989 ConstantRange NegSmallLHS(APInt(16, -7), APInt(16, -2));
990 EXPECT_EQ(NegSmallLHS.srem(PosMod), NegSmallLHS);
991 EXPECT_EQ(NegSmallLHS.srem(NegMod), NegSmallLHS);
992 EXPECT_EQ(NegSmallLHS.srem(IntMinMod), NegSmallLHS);
993 ConstantRange PosNegSmallLHS(APInt(16, -3), APInt(16, 8));
994 EXPECT_EQ(PosNegSmallLHS.srem(PosMod), PosNegSmallLHS);
995 EXPECT_EQ(PosNegSmallLHS.srem(NegMod), PosNegSmallLHS);
996 EXPECT_EQ(PosNegSmallLHS.srem(IntMinMod), PosNegSmallLHS);
997
998 // Example of a suboptimal result:
999 // [12, 14] srem 10 is [2, 4], but we conservatively compute [0, 9].
1000 EXPECT_EQ(ConstantRange(APInt(16, 12), APInt(16, 15))
1001 .srem(ConstantRange(APInt(16, 10))),
1002 ConstantRange(APInt(16, 0), APInt(16, 10)));
1003
1004 TestSignedBinOpExhaustive(
1005 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1006 return CR1.srem(CR2);
1007 },
1008 [](const APInt &N1, const APInt &N2) {
1009 return N1.srem(N2);
1010 },
1011 /* SkipZeroRHS */ true, /* CorrectnessOnly */ true);
1012 }
1013
1014 TEST_F(ConstantRangeTest, Shl) {
1015 ConstantRange Some2(APInt(16, 0xfff), APInt(16, 0x8000));
1016 ConstantRange WrapNullMax(APInt(16, 0x1), APInt(16, 0x0));
1017 EXPECT_EQ(Full.shl(Full), Full);
1018 EXPECT_EQ(Full.shl(Empty), Empty);
1019 EXPECT_EQ(Full.shl(One), Full); // TODO: [0, (-1 << 0xa) + 1)
1020 EXPECT_EQ(Full.shl(Some), Full); // TODO: [0, (-1 << 0xa) + 1)
1021 EXPECT_EQ(Full.shl(Wrap), Full);
1022 EXPECT_EQ(Empty.shl(Empty), Empty);
1023 EXPECT_EQ(Empty.shl(One), Empty);
1024 EXPECT_EQ(Empty.shl(Some), Empty);
1025 EXPECT_EQ(Empty.shl(Wrap), Empty);
1026 EXPECT_EQ(One.shl(One), ConstantRange(APInt(16, 0xa << 0xa),
1027 APInt(16, (0xa << 0xa) + 1)));
1028 EXPECT_EQ(One.shl(Some), Full); // TODO: [0xa << 0xa, 0)
1029 EXPECT_EQ(One.shl(Wrap), Full); // TODO: [0xa, 0xa << 14 + 1)
1030 EXPECT_EQ(Some.shl(Some), Full); // TODO: [0xa << 0xa, 0xfc01)
1031 EXPECT_EQ(Some.shl(Wrap), Full); // TODO: [0xa, 0x7ff << 0x5 + 1)
1032 EXPECT_EQ(Wrap.shl(Wrap), Full);
1033 EXPECT_EQ(
1034 Some2.shl(ConstantRange(APInt(16, 0x1))),
1035 ConstantRange(APInt(16, 0xfff << 0x1), APInt(16, 0x7fff << 0x1) + 1));
1036 EXPECT_EQ(One.shl(WrapNullMax), Full);
1037 }
1038
1039 TEST_F(ConstantRangeTest, Lshr) {
1040 EXPECT_EQ(Full.lshr(Full), Full);
1041 EXPECT_EQ(Full.lshr(Empty), Empty);
1042 EXPECT_EQ(Full.lshr(One), ConstantRange(APInt(16, 0),
1043 APInt(16, (0xffff >> 0xa) + 1)));
1044 EXPECT_EQ(Full.lshr(Some), ConstantRange(APInt(16, 0),
1045 APInt(16, (0xffff >> 0xa) + 1)));
1046 EXPECT_EQ(Full.lshr(Wrap), Full);
1047 EXPECT_EQ(Empty.lshr(Empty), Empty);
1048 EXPECT_EQ(Empty.lshr(One), Empty);
1049 EXPECT_EQ(Empty.lshr(Some), Empty);
1050 EXPECT_EQ(Empty.lshr(Wrap), Empty);
1051 EXPECT_EQ(One.lshr(One), ConstantRange(APInt(16, 0)));
1052 EXPECT_EQ(One.lshr(Some), ConstantRange(APInt(16, 0)));
1053 EXPECT_EQ(One.lshr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
1054 EXPECT_EQ(Some.lshr(Some), ConstantRange(APInt(16, 0),
1055 APInt(16, (0xaaa >> 0xa) + 1)));
1056 EXPECT_EQ(Some.lshr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
1057 EXPECT_EQ(Wrap.lshr(Wrap), Full);
1058 }
1059
1060 TEST_F(ConstantRangeTest, Ashr) {
1061 EXPECT_EQ(Full.ashr(Full), Full);
1062 EXPECT_EQ(Full.ashr(Empty), Empty);
1063 EXPECT_EQ(Full.ashr(One), ConstantRange(APInt(16, 0xffe0),
1064 APInt(16, (0x7fff >> 0xa) + 1 )));
1065 ConstantRange Small(APInt(16, 0xa), APInt(16, 0xb));
1066 EXPECT_EQ(Full.ashr(Small), ConstantRange(APInt(16, 0xffe0),
1067 APInt(16, (0x7fff >> 0xa) + 1 )));
1068 EXPECT_EQ(Full.ashr(Some), ConstantRange(APInt(16, 0xffe0),
1069 APInt(16, (0x7fff >> 0xa) + 1 )));
1070 EXPECT_EQ(Full.ashr(Wrap), Full);
1071 EXPECT_EQ(Empty.ashr(Empty), Empty);
1072 EXPECT_EQ(Empty.ashr(One), Empty);
1073 EXPECT_EQ(Empty.ashr(Some), Empty);
1074 EXPECT_EQ(Empty.ashr(Wrap), Empty);
1075 EXPECT_EQ(One.ashr(One), ConstantRange(APInt(16, 0)));
1076 EXPECT_EQ(One.ashr(Some), ConstantRange(APInt(16, 0)));
1077 EXPECT_EQ(One.ashr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
1078 EXPECT_EQ(Some.ashr(Some), ConstantRange(APInt(16, 0),
1079 APInt(16, (0xaaa >> 0xa) + 1)));
1080 EXPECT_EQ(Some.ashr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
1081 EXPECT_EQ(Wrap.ashr(Wrap), Full);
1082 ConstantRange Neg(APInt(16, 0xf3f0, true), APInt(16, 0xf7f8, true));
1083 EXPECT_EQ(Neg.ashr(Small), ConstantRange(APInt(16, 0xfffc, true),
1084 APInt(16, 0xfffe, true)));
1085 }
1086
1087 TEST(ConstantRange, MakeAllowedICmpRegion) {
1088 // PR8250
1089 ConstantRange SMax = ConstantRange(APInt::getSignedMaxValue(32));
1090 EXPECT_TRUE(ConstantRange::makeAllowedICmpRegion(ICmpInst::ICMP_SGT, SMax)
1091 .isEmptySet());
1092 }
1093
1094 TEST(ConstantRange, MakeSatisfyingICmpRegion) {
1095 ConstantRange LowHalf(APInt(8, 0), APInt(8, 128));
1096 ConstantRange HighHalf(APInt(8, 128), APInt(8, 0));
1097 ConstantRange EmptySet(8, /* isFullSet = */ false);
1098
1099 EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_NE, LowHalf),
1100 HighHalf);
1101
1102 EXPECT_EQ(
1103 ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_NE, HighHalf),
1104 LowHalf);
1105
1106 EXPECT_TRUE(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_EQ,
1107 HighHalf).isEmptySet());
1108
1109 ConstantRange UnsignedSample(APInt(8, 5), APInt(8, 200));
1110
1111 EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_ULT,
1112 UnsignedSample),
1113 ConstantRange(APInt(8, 0), APInt(8, 5)));
1114
1115 EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_ULE,
1116 UnsignedSample),
1117 ConstantRange(APInt(8, 0), APInt(8, 6)));
1118
1119 EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_UGT,
1120 UnsignedSample),
1121 ConstantRange(APInt(8, 200), APInt(8, 0)));
1122
1123 EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_UGE,
1124 UnsignedSample),
1125 ConstantRange(APInt(8, 199), APInt(8, 0)));
1126
1127 ConstantRange SignedSample(APInt(8, -5), APInt(8, 5));
1128
1129 EXPECT_EQ(
1130 ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SLT, SignedSample),
1131 ConstantRange(APInt(8, -128), APInt(8, -5)));
1132
1133 EXPECT_EQ(
1134 ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SLE, SignedSample),
1135 ConstantRange(APInt(8, -128), APInt(8, -4)));
1136
1137 EXPECT_EQ(
1138 ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SGT, SignedSample),
1139 ConstantRange(APInt(8, 5), APInt(8, -128)));
1140
1141 EXPECT_EQ(
1142 ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SGE, SignedSample),
1143 ConstantRange(APInt(8, 4), APInt(8, -128)));
1144 }
1145
1146 TEST(ConstantRange, MakeGuaranteedNoWrapRegion) {
1147 const int IntMin4Bits = 8;
1148 const int IntMax4Bits = 7;
1149 typedef OverflowingBinaryOperator OBO;
1150
1151 for (int Const : {0, -1, -2, 1, 2, IntMin4Bits, IntMax4Bits}) {
1152 APInt C(4, Const, true /* = isSigned */);
1153
1154 auto NUWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
1155 Instruction::Add, C, OBO::NoUnsignedWrap);
1156
1157 EXPECT_FALSE(NUWRegion.isEmptySet());
1158
1159 auto NSWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
1160 Instruction::Add, C, OBO::NoSignedWrap);
1161
1162 EXPECT_FALSE(NSWRegion.isEmptySet());
1163
1164 for (APInt I = NUWRegion.getLower(), E = NUWRegion.getUpper(); I != E;
1165 ++I) {
1166 bool Overflow = false;
1167 (void)I.uadd_ov(C, Overflow);
1168 EXPECT_FALSE(Overflow);
1169 }
1170
1171 for (APInt I = NSWRegion.getLower(), E = NSWRegion.getUpper(); I != E;
1172 ++I) {
1173 bool Overflow = false;
1174 (void)I.sadd_ov(C, Overflow);
1175 EXPECT_FALSE(Overflow);
1176 }
1177 }
1178
1179 for (int Const : {0, -1, -2, 1, 2, IntMin4Bits, IntMax4Bits}) {
1180 APInt C(4, Const, true /* = isSigned */);
1181
1182 auto NUWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
1183 Instruction::Sub, C, OBO::NoUnsignedWrap);
1184
1185 EXPECT_FALSE(NUWRegion.isEmptySet());
1186
1187 auto NSWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
1188 Instruction::Sub, C, OBO::NoSignedWrap);
1189
1190 EXPECT_FALSE(NSWRegion.isEmptySet());
1191
1192 for (APInt I = NUWRegion.getLower(), E = NUWRegion.getUpper(); I != E;
1193 ++I) {
1194 bool Overflow = false;
1195 (void)I.usub_ov(C, Overflow);
1196 EXPECT_FALSE(Overflow);
1197 }
1198
1199 for (APInt I = NSWRegion.getLower(), E = NSWRegion.getUpper(); I != E;
1200 ++I) {
1201 bool Overflow = false;
1202 (void)I.ssub_ov(C, Overflow);
1203 EXPECT_FALSE(Overflow);
1204 }
1205 }
1206
1207 auto NSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
1208 Instruction::Add, ConstantRange(32, /* isFullSet = */ true),
1209 OBO::NoSignedWrap);
1210 EXPECT_TRUE(NSWForAllValues.isSingleElement() &&
1211 NSWForAllValues.getSingleElement()->isMinValue());
1212
1213 NSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
1214 Instruction::Sub, ConstantRange(32, /* isFullSet = */ true),
1215 OBO::NoSignedWrap);
1216 EXPECT_TRUE(NSWForAllValues.isSingleElement() &&
1217 NSWForAllValues.getSingleElement()->isMaxValue());
1218
1219 auto NUWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
1220 Instruction::Add, ConstantRange(32, /* isFullSet = */ true),
1221 OBO::NoUnsignedWrap);
1222 EXPECT_TRUE(NUWForAllValues.isSingleElement() &&
1223 NUWForAllValues.getSingleElement()->isMinValue());
1224
1225 NUWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
1226 Instruction::Sub, ConstantRange(32, /* isFullSet = */ true),
1227 OBO::NoUnsignedWrap);
1228 EXPECT_TRUE(NUWForAllValues.isSingleElement() &&
1229 NUWForAllValues.getSingleElement()->isMaxValue());
1230
1231 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
1232 Instruction::Add, APInt(32, 0), OBO::NoUnsignedWrap).isFullSet());
1233 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
1234 Instruction::Add, APInt(32, 0), OBO::NoSignedWrap).isFullSet());
1235 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
1236 Instruction::Sub, APInt(32, 0), OBO::NoUnsignedWrap).isFullSet());
1237 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
1238 Instruction::Sub, APInt(32, 0), OBO::NoSignedWrap).isFullSet());
1239
1240 ConstantRange OneToFive(APInt(32, 1), APInt(32, 6));
1241 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1242 Instruction::Add, OneToFive, OBO::NoSignedWrap),
1243 ConstantRange(APInt::getSignedMinValue(32),
1244 APInt::getSignedMaxValue(32) - 4));
1245 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1246 Instruction::Add, OneToFive, OBO::NoUnsignedWrap),
1247 ConstantRange(APInt::getMinValue(32), APInt::getMinValue(32) - 5));
1248 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1249 Instruction::Sub, OneToFive, OBO::NoSignedWrap),
1250 ConstantRange(APInt::getSignedMinValue(32) + 5,
1251 APInt::getSignedMinValue(32)));
1252 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1253 Instruction::Sub, OneToFive, OBO::NoUnsignedWrap),
1254 ConstantRange(APInt::getMinValue(32) + 5, APInt::getMinValue(32)));
1255
1256 ConstantRange MinusFiveToMinusTwo(APInt(32, -5), APInt(32, -1));
1257 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1258 Instruction::Add, MinusFiveToMinusTwo, OBO::NoSignedWrap),
1259 ConstantRange(APInt::getSignedMinValue(32) + 5,
1260 APInt::getSignedMinValue(32)));
1261 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1262 Instruction::Add, MinusFiveToMinusTwo, OBO::NoUnsignedWrap),
1263 ConstantRange(APInt(32, 0), APInt(32, 2)));
1264 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1265 Instruction::Sub, MinusFiveToMinusTwo, OBO::NoSignedWrap),
1266 ConstantRange(APInt::getSignedMinValue(32),
1267 APInt::getSignedMaxValue(32) - 4));
1268 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1269 Instruction::Sub, MinusFiveToMinusTwo, OBO::NoUnsignedWrap),
1270 ConstantRange(APInt::getMaxValue(32) - 1,
1271 APInt::getMinValue(32)));
1272
1273 ConstantRange MinusOneToOne(APInt(32, -1), APInt(32, 2));
1274 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1275 Instruction::Add, MinusOneToOne, OBO::NoSignedWrap),
1276 ConstantRange(APInt::getSignedMinValue(32) + 1,
1277 APInt::getSignedMinValue(32) - 1));
1278 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1279 Instruction::Add, MinusOneToOne, OBO::NoUnsignedWrap),
1280 ConstantRange(APInt(32, 0), APInt(32, 1)));
1281 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1282 Instruction::Sub, MinusOneToOne, OBO::NoSignedWrap),
1283 ConstantRange(APInt::getSignedMinValue(32) + 1,
1284 APInt::getSignedMinValue(32) - 1));
1285 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1286 Instruction::Sub, MinusOneToOne, OBO::NoUnsignedWrap),
1287 ConstantRange(APInt::getMaxValue(32),
1288 APInt::getMinValue(32)));
1289
1290 ConstantRange One(APInt(32, 1), APInt(32, 2));
1291 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1292 Instruction::Add, One, OBO::NoSignedWrap),
1293 ConstantRange(APInt::getSignedMinValue(32),
1294 APInt::getSignedMaxValue(32)));
1295 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1296 Instruction::Add, One, OBO::NoUnsignedWrap),
1297 ConstantRange(APInt::getMinValue(32), APInt::getMaxValue(32)));
1298 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1299 Instruction::Sub, One, OBO::NoSignedWrap),
1300 ConstantRange(APInt::getSignedMinValue(32) + 1,
1301 APInt::getSignedMinValue(32)));
1302 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
1303 Instruction::Sub, One, OBO::NoUnsignedWrap),
1304 ConstantRange(APInt::getMinValue(32) + 1, APInt::getMinValue(32)));
1305 }
1306
1307 template<typename Fn>
1308 void TestNoWrapRegionExhaustive(Instruction::BinaryOps BinOp,
1309 unsigned NoWrapKind, Fn OverflowFn) {
1310 // When using 4 bits this test needs ~3s on a debug build.
1311 unsigned Bits = 3;
1312 EnumerateTwoConstantRanges(Bits,
1313 [&](const ConstantRange &CR1, const ConstantRange &CR2) {
1314 if (CR2.isEmptySet())
1315 return;
1316
1317 ConstantRange NoWrap =
1318 ConstantRange::makeGuaranteedNoWrapRegion(BinOp, CR2, NoWrapKind);
1319 ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
1320 bool NoOverflow = true;
1321 bool Overflow = true;
1322 ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
1323 if (OverflowFn(N1, N2))
1324 NoOverflow = false;
1325 else
1326 Overflow = false;
1327 });
1328 EXPECT_EQ(NoOverflow, NoWrap.contains(N1));
1329
1330 // The no-wrap range is exact for single-element ranges.
1331 if (CR2.isSingleElement()) {
1332 EXPECT_EQ(Overflow, !NoWrap.contains(N1));
1333 }
1334 });
1335 });
1336 }
1337
1338 // Show that makeGuaranteedNoWrapRegion() is maximal, and for single-element
1339 // ranges also exact.
1340 TEST(ConstantRange, NoWrapRegionExhaustive) {
1341 TestNoWrapRegionExhaustive(
1342 Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap,
1343 [](const APInt &N1, const APInt &N2) {
1344 bool Overflow;
1345 (void) N1.uadd_ov(N2, Overflow);
1346 return Overflow;
1347 });
1348 TestNoWrapRegionExhaustive(
1349 Instruction::Add, OverflowingBinaryOperator::NoSignedWrap,
1350 [](const APInt &N1, const APInt &N2) {
1351 bool Overflow;
1352 (void) N1.sadd_ov(N2, Overflow);
1353 return Overflow;
1354 });
1355 TestNoWrapRegionExhaustive(
1356 Instruction::Sub, OverflowingBinaryOperator::NoUnsignedWrap,
1357 [](const APInt &N1, const APInt &N2) {
1358 bool Overflow;
1359 (void) N1.usub_ov(N2, Overflow);
1360 return Overflow;
1361 });
1362 TestNoWrapRegionExhaustive(
1363 Instruction::Sub, OverflowingBinaryOperator::NoSignedWrap,
1364 [](const APInt &N1, const APInt &N2) {
1365 bool Overflow;
1366 (void) N1.ssub_ov(N2, Overflow);
1367 return Overflow;
1368 });
1369 TestNoWrapRegionExhaustive(
1370 Instruction::Mul, OverflowingBinaryOperator::NoUnsignedWrap,
1371 [](const APInt &N1, const APInt &N2) {
1372 bool Overflow;
1373 (void) N1.umul_ov(N2, Overflow);
1374 return Overflow;
1375 });
1376 TestNoWrapRegionExhaustive(
1377 Instruction::Mul, OverflowingBinaryOperator::NoSignedWrap,
1378 [](const APInt &N1, const APInt &N2) {
1379 bool Overflow;
1380 (void) N1.smul_ov(N2, Overflow);
1381 return Overflow;
1382 });
1383 }
1384
1385 TEST(ConstantRange, GetEquivalentICmp) {
1386 APInt RHS;
1387 CmpInst::Predicate Pred;
1388
1389 EXPECT_TRUE(ConstantRange(APInt::getMinValue(32), APInt(32, 100))
1390 .getEquivalentICmp(Pred, RHS));
1391 EXPECT_EQ(Pred, CmpInst::ICMP_ULT);
1392 EXPECT_EQ(RHS, APInt(32, 100));
1393
1394 EXPECT_TRUE(ConstantRange(APInt::getSignedMinValue(32), APInt(32, 100))
1395 .getEquivalentICmp(Pred, RHS));
1396 EXPECT_EQ(Pred, CmpInst::ICMP_SLT);
1397 EXPECT_EQ(RHS, APInt(32, 100));
1398
1399 EXPECT_TRUE(ConstantRange(APInt(32, 100), APInt::getMinValue(32))
1400 .getEquivalentICmp(Pred, RHS));
1401 EXPECT_EQ(Pred, CmpInst::ICMP_UGE);
1402 EXPECT_EQ(RHS, APInt(32, 100));
1403
1404 EXPECT_TRUE(ConstantRange(APInt(32, 100), APInt::getSignedMinValue(32))
1405 .getEquivalentICmp(Pred, RHS));
1406 EXPECT_EQ(Pred, CmpInst::ICMP_SGE);
1407 EXPECT_EQ(RHS, APInt(32, 100));
1408
1409 EXPECT_TRUE(
1410 ConstantRange(32, /*isFullSet=*/true).getEquivalentICmp(Pred, RHS));
1411 EXPECT_EQ(Pred, CmpInst::ICMP_UGE);
1412 EXPECT_EQ(RHS, APInt(32, 0));
1413
1414 EXPECT_TRUE(
1415 ConstantRange(32, /*isFullSet=*/false).getEquivalentICmp(Pred, RHS));
1416 EXPECT_EQ(Pred, CmpInst::ICMP_ULT);
1417 EXPECT_EQ(RHS, APInt(32, 0));
1418
1419 EXPECT_FALSE(ConstantRange(APInt(32, 100), APInt(32, 200))
1420 .getEquivalentICmp(Pred, RHS));
1421
1422 EXPECT_FALSE(ConstantRange(APInt::getSignedMinValue(32) - APInt(32, 100),
1423 APInt::getSignedMinValue(32) + APInt(32, 100))
1424 .getEquivalentICmp(Pred, RHS));
1425
1426 EXPECT_FALSE(ConstantRange(APInt::getMinValue(32) - APInt(32, 100),
1427 APInt::getMinValue(32) + APInt(32, 100))
1428 .getEquivalentICmp(Pred, RHS));
1429
1430 EXPECT_TRUE(ConstantRange(APInt(32, 100)).getEquivalentICmp(Pred, RHS));
1431 EXPECT_EQ(Pred, CmpInst::ICMP_EQ);
1432 EXPECT_EQ(RHS, APInt(32, 100));
1433
1434 EXPECT_TRUE(
1435 ConstantRange(APInt(32, 100)).inverse().getEquivalentICmp(Pred, RHS));
1436 EXPECT_EQ(Pred, CmpInst::ICMP_NE);
1437 EXPECT_EQ(RHS, APInt(32, 100));
1438
1439 EXPECT_TRUE(
1440 ConstantRange(APInt(512, 100)).inverse().getEquivalentICmp(Pred, RHS));
1441 EXPECT_EQ(Pred, CmpInst::ICMP_NE);
1442 EXPECT_EQ(RHS, APInt(512, 100));
1443
1444 // NB! It would be correct for the following four calls to getEquivalentICmp
1445 // to return ordered predicates like CmpInst::ICMP_ULT or CmpInst::ICMP_UGT.
1446 // However, that's not the case today.
1447
1448 EXPECT_TRUE(ConstantRange(APInt(32, 0)).getEquivalentICmp(Pred, RHS));
1449 EXPECT_EQ(Pred, CmpInst::ICMP_EQ);
1450 EXPECT_EQ(RHS, APInt(32, 0));
1451
1452 EXPECT_TRUE(
1453 ConstantRange(APInt(32, 0)).inverse().getEquivalentICmp(Pred, RHS));
1454 EXPECT_EQ(Pred, CmpInst::ICMP_NE);
1455 EXPECT_EQ(RHS, APInt(32, 0));
1456
1457 EXPECT_TRUE(ConstantRange(APInt(32, -1)).getEquivalentICmp(Pred, RHS));
1458 EXPECT_EQ(Pred, CmpInst::ICMP_EQ);
1459 EXPECT_EQ(RHS, APInt(32, -1));
1460
1461 EXPECT_TRUE(
1462 ConstantRange(APInt(32, -1)).inverse().getEquivalentICmp(Pred, RHS));
1463 EXPECT_EQ(Pred, CmpInst::ICMP_NE);
1464 EXPECT_EQ(RHS, APInt(32, -1));
1465 }
1466
1467 TEST(ConstantRange, MakeGuaranteedNoWrapRegionMulUnsignedSingleValue) {
1468 typedef OverflowingBinaryOperator OBO;
1469
1470 for (uint64_t I = std::numeric_limits<uint8_t>::min();
1471 I <= std::numeric_limits<uint8_t>::max(); I++) {
1472 auto Range = ConstantRange::makeGuaranteedNoWrapRegion(
1473 Instruction::Mul, ConstantRange(APInt(8, I), APInt(8, I + 1)),
1474 OBO::NoUnsignedWrap);
1475
1476 for (uint64_t V = std::numeric_limits<uint8_t>::min();
1477 V <= std::numeric_limits<uint8_t>::max(); V++) {
1478 bool Overflow;
1479 (void)APInt(8, I).umul_ov(APInt(8, V), Overflow);
1480 EXPECT_EQ(!Overflow, Range.contains(APInt(8, V)));
1481 }
1482 }
1483 }
1484
1485 TEST(ConstantRange, MakeGuaranteedNoWrapRegionMulSignedSingleValue) {
1486 typedef OverflowingBinaryOperator OBO;
1487
1488 for (int64_t I = std::numeric_limits<int8_t>::min();
1489 I <= std::numeric_limits<int8_t>::max(); I++) {
1490 auto Range = ConstantRange::makeGuaranteedNoWrapRegion(
1491 Instruction::Mul,
1492 ConstantRange(APInt(8, I, /*isSigned=*/true),
1493 APInt(8, I + 1, /*isSigned=*/true)),
1494 OBO::NoSignedWrap);
1495
1496 for (int64_t V = std::numeric_limits<int8_t>::min();
1497 V <= std::numeric_limits<int8_t>::max(); V++) {
1498 bool Overflow;
1499 (void)APInt(8, I, /*isSigned=*/true)
1500 .smul_ov(APInt(8, V, /*isSigned=*/true), Overflow);
1501 EXPECT_EQ(!Overflow, Range.contains(APInt(8, V, /*isSigned=*/true)));
1502 }
1503 }
1504 }
1505
1506 TEST(ConstantRange, MakeGuaranteedNoWrapRegionMulUnsignedRange) {
1507 typedef OverflowingBinaryOperator OBO;
1508
1509 for (uint64_t Lo = std::numeric_limits<uint8_t>::min();
1510 Lo <= std::numeric_limits<uint8_t>::max(); Lo++) {
1511 for (uint64_t Hi = Lo; Hi <= std::numeric_limits<uint8_t>::max(); Hi++) {
1512 EXPECT_EQ(
1513 ConstantRange::makeGuaranteedNoWrapRegion(
1514 Instruction::Mul, ConstantRange(APInt(8, Lo), APInt(8, Hi + 1)),
1515 OBO::NoUnsignedWrap),
1516 ConstantRange::makeGuaranteedNoWrapRegion(
1517 Instruction::Mul, ConstantRange(APInt(8, Hi), APInt(8, Hi + 1)),
1518 OBO::NoUnsignedWrap));
1519 }
1520 }
1521 }
1522
1523 TEST(ConstantRange, MakeGuaranteedNoWrapRegionMulSignedRange) {
1524 typedef OverflowingBinaryOperator OBO;
1525
1526 int Lo = -12, Hi = 16;
1527 auto Range = ConstantRange::makeGuaranteedNoWrapRegion(
1528 Instruction::Mul,
1529 ConstantRange(APInt(8, Lo, /*isSigned=*/true),
1530 APInt(8, Hi + 1, /*isSigned=*/true)),
1531 OBO::NoSignedWrap);
1532
1533 for (int64_t V = std::numeric_limits<int8_t>::min();
1534 V <= std::numeric_limits<int8_t>::max(); V++) {
1535 bool AnyOverflow = false;
1536 for (int64_t I = Lo; I <= Hi; I++) {
1537 bool Overflow;
1538 (void)APInt(8, I, /*isSigned=*/true)
1539 .smul_ov(APInt(8, V, /*isSigned=*/true), Overflow);
1540 AnyOverflow |= Overflow;
1541 }
1542 EXPECT_EQ(!AnyOverflow, Range.contains(APInt(8, V, /*isSigned=*/true)));
1543 }
1544 }
1545
1546 #define EXPECT_MAY_OVERFLOW(op) \
1547 EXPECT_EQ(ConstantRange::OverflowResult::MayOverflow, (op))
1548 #define EXPECT_ALWAYS_OVERFLOWS_LOW(op) \
1549 EXPECT_EQ(ConstantRange::OverflowResult::AlwaysOverflowsLow, (op))
1550 #define EXPECT_ALWAYS_OVERFLOWS_HIGH(op) \
1551 EXPECT_EQ(ConstantRange::OverflowResult::AlwaysOverflowsHigh, (op))
1552 #define EXPECT_NEVER_OVERFLOWS(op) \
1553 EXPECT_EQ(ConstantRange::OverflowResult::NeverOverflows, (op))
1554
1555 TEST_F(ConstantRangeTest, UnsignedAddOverflow) {
1556 // Ill-defined - may overflow is a conservative result.
1557 EXPECT_MAY_OVERFLOW(Some.unsignedAddMayOverflow(Empty));
1558 EXPECT_MAY_OVERFLOW(Empty.unsignedAddMayOverflow(Some));
1559
1560 // Never overflow despite one full/wrap set.
1561 ConstantRange Zero(APInt::getNullValue(16));
1562 EXPECT_NEVER_OVERFLOWS(Full.unsignedAddMayOverflow(Zero));
1563 EXPECT_NEVER_OVERFLOWS(Wrap.unsignedAddMayOverflow(Zero));
1564 EXPECT_NEVER_OVERFLOWS(Zero.unsignedAddMayOverflow(Full));
1565 EXPECT_NEVER_OVERFLOWS(Zero.unsignedAddMayOverflow(Wrap));
1566
1567 // But usually full/wrap always may overflow.
1568 EXPECT_MAY_OVERFLOW(Full.unsignedAddMayOverflow(One));
1569 EXPECT_MAY_OVERFLOW(Wrap.unsignedAddMayOverflow(One));
1570 EXPECT_MAY_OVERFLOW(One.unsignedAddMayOverflow(Full));
1571 EXPECT_MAY_OVERFLOW(One.unsignedAddMayOverflow(Wrap));
1572
1573 ConstantRange A(APInt(16, 0xfd00), APInt(16, 0xfe00));
1574 ConstantRange B1(APInt(16, 0x0100), APInt(16, 0x0201));
1575 ConstantRange B2(APInt(16, 0x0100), APInt(16, 0x0202));
1576 EXPECT_NEVER_OVERFLOWS(A.unsignedAddMayOverflow(B1));
1577 EXPECT_MAY_OVERFLOW(A.unsignedAddMayOverflow(B2));
1578 EXPECT_NEVER_OVERFLOWS(B1.unsignedAddMayOverflow(A));
1579 EXPECT_MAY_OVERFLOW(B2.unsignedAddMayOverflow(A));
1580
1581 ConstantRange C1(APInt(16, 0x0299), APInt(16, 0x0400));
1582 ConstantRange C2(APInt(16, 0x0300), APInt(16, 0x0400));
1583 EXPECT_MAY_OVERFLOW(A.unsignedAddMayOverflow(C1));
1584 EXPECT_ALWAYS_OVERFLOWS_HIGH(A.unsignedAddMayOverflow(C2));
1585 EXPECT_MAY_OVERFLOW(C1.unsignedAddMayOverflow(A));
1586 EXPECT_ALWAYS_OVERFLOWS_HIGH(C2.unsignedAddMayOverflow(A));
1587 }
1588
1589 TEST_F(ConstantRangeTest, UnsignedSubOverflow) {
1590 // Ill-defined - may overflow is a conservative result.
1591 EXPECT_MAY_OVERFLOW(Some.unsignedSubMayOverflow(Empty));
1592 EXPECT_MAY_OVERFLOW(Empty.unsignedSubMayOverflow(Some));
1593
1594 // Never overflow despite one full/wrap set.
1595 ConstantRange Zero(APInt::getNullValue(16));
1596 ConstantRange Max(APInt::getAllOnesValue(16));
1597 EXPECT_NEVER_OVERFLOWS(Full.unsignedSubMayOverflow(Zero));
1598 EXPECT_NEVER_OVERFLOWS(Wrap.unsignedSubMayOverflow(Zero));
1599 EXPECT_NEVER_OVERFLOWS(Max.unsignedSubMayOverflow(Full));
1600 EXPECT_NEVER_OVERFLOWS(Max.unsignedSubMayOverflow(Wrap));
1601
1602 // But usually full/wrap always may overflow.
1603 EXPECT_MAY_OVERFLOW(Full.unsignedSubMayOverflow(One));
1604 EXPECT_MAY_OVERFLOW(Wrap.unsignedSubMayOverflow(One));
1605 EXPECT_MAY_OVERFLOW(One.unsignedSubMayOverflow(Full));
1606 EXPECT_MAY_OVERFLOW(One.unsignedSubMayOverflow(Wrap));
1607
1608 ConstantRange A(APInt(16, 0x0000), APInt(16, 0x0100));
1609 ConstantRange B(APInt(16, 0x0100), APInt(16, 0x0200));
1610 EXPECT_NEVER_OVERFLOWS(B.unsignedSubMayOverflow(A));
1611 EXPECT_ALWAYS_OVERFLOWS_LOW(A.unsignedSubMayOverflow(B));
1612
1613 ConstantRange A1(APInt(16, 0x0000), APInt(16, 0x0101));
1614 ConstantRange B1(APInt(16, 0x0100), APInt(16, 0x0201));
1615 EXPECT_NEVER_OVERFLOWS(B1.unsignedSubMayOverflow(A1));
1616 EXPECT_MAY_OVERFLOW(A1.unsignedSubMayOverflow(B1));
1617
1618 ConstantRange A2(APInt(16, 0x0000), APInt(16, 0x0102));
1619 ConstantRange B2(APInt(16, 0x0100), APInt(16, 0x0202));
1620 EXPECT_MAY_OVERFLOW(B2.unsignedSubMayOverflow(A2));
1621 EXPECT_MAY_OVERFLOW(A2.unsignedSubMayOverflow(B2));
1622 }
1623
1624 TEST_F(ConstantRangeTest, SignedAddOverflow) {
1625 // Ill-defined - may overflow is a conservative result.
1626 EXPECT_MAY_OVERFLOW(Some.signedAddMayOverflow(Empty));
1627 EXPECT_MAY_OVERFLOW(Empty.signedAddMayOverflow(Some));
1628
1629 // Never overflow despite one full/wrap set.
1630 ConstantRange Zero(APInt::getNullValue(16));
1631 EXPECT_NEVER_OVERFLOWS(Full.signedAddMayOverflow(Zero));
1632 EXPECT_NEVER_OVERFLOWS(Wrap.signedAddMayOverflow(Zero));
1633 EXPECT_NEVER_OVERFLOWS(Zero.signedAddMayOverflow(Full));
1634 EXPECT_NEVER_OVERFLOWS(Zero.signedAddMayOverflow(Wrap));
1635
1636 // But usually full/wrap always may overflow.
1637 EXPECT_MAY_OVERFLOW(Full.signedAddMayOverflow(One));
1638 EXPECT_MAY_OVERFLOW(Wrap.signedAddMayOverflow(One));
1639 EXPECT_MAY_OVERFLOW(One.signedAddMayOverflow(Full));
1640 EXPECT_MAY_OVERFLOW(One.signedAddMayOverflow(Wrap));
1641
1642 ConstantRange A(APInt(16, 0x7d00), APInt(16, 0x7e00));
1643 ConstantRange B1(APInt(16, 0x0100), APInt(16, 0x0201));
1644 ConstantRange B2(APInt(16, 0x0100), APInt(16, 0x0202));
1645 EXPECT_NEVER_OVERFLOWS(A.signedAddMayOverflow(B1));
1646 EXPECT_MAY_OVERFLOW(A.signedAddMayOverflow(B2));
1647 ConstantRange B3(APInt(16, 0x8000), APInt(16, 0x0201));
1648 ConstantRange B4(APInt(16, 0x8000), APInt(16, 0x0202));
1649 EXPECT_NEVER_OVERFLOWS(A.signedAddMayOverflow(B3));
1650 EXPECT_MAY_OVERFLOW(A.signedAddMayOverflow(B4));
1651 ConstantRange B5(APInt(16, 0x0299), APInt(16, 0x0400));
1652 ConstantRange B6(APInt(16, 0x0300), APInt(16, 0x0400));
1653 EXPECT_MAY_OVERFLOW(A.signedAddMayOverflow(B5));
1654 EXPECT_ALWAYS_OVERFLOWS_HIGH(A.signedAddMayOverflow(B6));
1655
1656 ConstantRange C(APInt(16, 0x8200), APInt(16, 0x8300));
1657 ConstantRange D1(APInt(16, 0xfe00), APInt(16, 0xff00));
1658 ConstantRange D2(APInt(16, 0xfd99), APInt(16, 0xff00));
1659 EXPECT_NEVER_OVERFLOWS(C.signedAddMayOverflow(D1));
1660 EXPECT_MAY_OVERFLOW(C.signedAddMayOverflow(D2));
1661 ConstantRange D3(APInt(16, 0xfe00), APInt(16, 0x8000));
1662 ConstantRange D4(APInt(16, 0xfd99), APInt(16, 0x8000));
1663 EXPECT_NEVER_OVERFLOWS(C.signedAddMayOverflow(D3));
1664 EXPECT_MAY_OVERFLOW(C.signedAddMayOverflow(D4));
1665 ConstantRange D5(APInt(16, 0xfc00), APInt(16, 0xfd02));
1666 ConstantRange D6(APInt(16, 0xfc00), APInt(16, 0xfd01));
1667 EXPECT_MAY_OVERFLOW(C.signedAddMayOverflow(D5));
1668 EXPECT_ALWAYS_OVERFLOWS_LOW(C.signedAddMayOverflow(D6));
1669
1670 ConstantRange E(APInt(16, 0xff00), APInt(16, 0x0100));
1671 EXPECT_NEVER_OVERFLOWS(E.signedAddMayOverflow(E));
1672 ConstantRange F(APInt(16, 0xf000), APInt(16, 0x7000));
1673 EXPECT_MAY_OVERFLOW(F.signedAddMayOverflow(F));
1674 }
1675
1676 TEST_F(ConstantRangeTest, SignedSubOverflow) {
1677 // Ill-defined - may overflow is a conservative result.
1678 EXPECT_MAY_OVERFLOW(Some.signedSubMayOverflow(Empty));
1679 EXPECT_MAY_OVERFLOW(Empty.signedSubMayOverflow(Some));
1680
1681 // Never overflow despite one full/wrap set.
1682 ConstantRange Zero(APInt::getNullValue(16));
1683 EXPECT_NEVER_OVERFLOWS(Full.signedSubMayOverflow(Zero));
1684 EXPECT_NEVER_OVERFLOWS(Wrap.signedSubMayOverflow(Zero));
1685
1686 // But usually full/wrap always may overflow.
1687 EXPECT_MAY_OVERFLOW(Full.signedSubMayOverflow(One));
1688 EXPECT_MAY_OVERFLOW(Wrap.signedSubMayOverflow(One));
1689 EXPECT_MAY_OVERFLOW(One.signedSubMayOverflow(Full));
1690 EXPECT_MAY_OVERFLOW(One.signedSubMayOverflow(Wrap));
1691
1692 ConstantRange A(APInt(16, 0x7d00), APInt(16, 0x7e00));
1693 ConstantRange B1(APInt(16, 0xfe00), APInt(16, 0xff00));
1694 ConstantRange B2(APInt(16, 0xfd99), APInt(16, 0xff00));
1695 EXPECT_NEVER_OVERFLOWS(A.signedSubMayOverflow(B1));
1696 EXPECT_MAY_OVERFLOW(A.signedSubMayOverflow(B2));
1697 ConstantRange B3(APInt(16, 0xfc00), APInt(16, 0xfd02));
1698 ConstantRange B4(APInt(16, 0xfc00), APInt(16, 0xfd01));
1699 EXPECT_MAY_OVERFLOW(A.signedSubMayOverflow(B3));
1700 EXPECT_ALWAYS_OVERFLOWS_HIGH(A.signedSubMayOverflow(B4));
1701
1702 ConstantRange C(APInt(16, 0x8200), APInt(16, 0x8300));
1703 ConstantRange D1(APInt(16, 0x0100), APInt(16, 0x0201));
1704 ConstantRange D2(APInt(16, 0x0100), APInt(16, 0x0202));
1705 EXPECT_NEVER_OVERFLOWS(C.signedSubMayOverflow(D1));
1706 EXPECT_MAY_OVERFLOW(C.signedSubMayOverflow(D2));
1707 ConstantRange D3(APInt(16, 0x0299), APInt(16, 0x0400));
1708 ConstantRange D4(APInt(16, 0x0300), APInt(16, 0x0400));
1709 EXPECT_MAY_OVERFLOW(C.signedSubMayOverflow(D3));
1710 EXPECT_ALWAYS_OVERFLOWS_LOW(C.signedSubMayOverflow(D4));
1711
1712 ConstantRange E(APInt(16, 0xff00), APInt(16, 0x0100));
1713 EXPECT_NEVER_OVERFLOWS(E.signedSubMayOverflow(E));
1714 ConstantRange F(APInt(16, 0xf000), APInt(16, 0x7001));
1715 EXPECT_MAY_OVERFLOW(F.signedSubMayOverflow(F));
1716 }
1717
1718 template<typename Fn1, typename Fn2>
1719 static void TestOverflowExhaustive(Fn1 OverflowFn, Fn2 MayOverflowFn) {
1720 // Constant range overflow checks are tested exhaustively on 4-bit numbers.
1721 unsigned Bits = 4;
1722 EnumerateTwoConstantRanges(Bits, [=](const ConstantRange &CR1,
1723 const ConstantRange &CR2) {
1724 // Loop over all N1 in CR1 and N2 in CR2 and check whether any of the
1725 // operations have overflow / have no overflow.
1726 bool RangeHasOverflowLow = false;
1727 bool RangeHasOverflowHigh = false;
1728 bool RangeHasNoOverflow = false;
1729 ForeachNumInConstantRange(CR1, [&](const APInt &N1) {
1730 ForeachNumInConstantRange(CR2, [&](const APInt &N2) {
1731 bool IsOverflowHigh;
1732 if (!OverflowFn(IsOverflowHigh, N1, N2)) {
1733 RangeHasNoOverflow = true;
1734 return;
1735 }
1736
1737 if (IsOverflowHigh)
1738 RangeHasOverflowHigh = true;
1739 else
1740 RangeHasOverflowLow = true;
1741 });
1742 });
1743
1744 ConstantRange::OverflowResult OR = MayOverflowFn(CR1, CR2);
1745 switch (OR) {
1746 case ConstantRange::OverflowResult::AlwaysOverflowsLow:
1747 EXPECT_TRUE(RangeHasOverflowLow);
1748 EXPECT_FALSE(RangeHasOverflowHigh);
1749 EXPECT_FALSE(RangeHasNoOverflow);
1750 break;
1751 case ConstantRange::OverflowResult::AlwaysOverflowsHigh:
1752 EXPECT_TRUE(RangeHasOverflowHigh);
1753 EXPECT_FALSE(RangeHasOverflowLow);
1754 EXPECT_FALSE(RangeHasNoOverflow);
1755 break;
1756 case ConstantRange::OverflowResult::NeverOverflows:
1757 EXPECT_FALSE(RangeHasOverflowLow);
1758 EXPECT_FALSE(RangeHasOverflowHigh);
1759 EXPECT_TRUE(RangeHasNoOverflow);
1760 break;
1761 case ConstantRange::OverflowResult::MayOverflow:
1762 // We return MayOverflow for empty sets as a conservative result,
1763 // but of course neither the RangeHasOverflow nor the
1764 // RangeHasNoOverflow flags will be set.
1765 if (CR1.isEmptySet() || CR2.isEmptySet())
1766 break;
1767
1768 EXPECT_TRUE(RangeHasOverflowLow || RangeHasOverflowHigh);
1769 EXPECT_TRUE(RangeHasNoOverflow);
1770 break;
1771 }
1772 });
1773 }
1774
1775 TEST_F(ConstantRangeTest, UnsignedAddOverflowExhaustive) {
1776 TestOverflowExhaustive(
1777 [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
1778 bool Overflow;
1779 (void) N1.uadd_ov(N2, Overflow);
1780 IsOverflowHigh = true;
1781 return Overflow;
1782 },
1783 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1784 return CR1.unsignedAddMayOverflow(CR2);
1785 });
1786 }
1787
1788 TEST_F(ConstantRangeTest, UnsignedSubOverflowExhaustive) {
1789 TestOverflowExhaustive(
1790 [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
1791 bool Overflow;
1792 (void) N1.usub_ov(N2, Overflow);
1793 IsOverflowHigh = false;
1794 return Overflow;
1795 },
1796 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1797 return CR1.unsignedSubMayOverflow(CR2);
1798 });
1799 }
1800
1801 TEST_F(ConstantRangeTest, UnsignedMulOverflowExhaustive) {
1802 TestOverflowExhaustive(
1803 [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
1804 bool Overflow;
1805 (void) N1.umul_ov(N2, Overflow);
1806 IsOverflowHigh = true;
1807 return Overflow;
1808 },
1809 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1810 return CR1.unsignedMulMayOverflow(CR2);
1811 });
1812 }
1813
1814 TEST_F(ConstantRangeTest, SignedAddOverflowExhaustive) {
1815 TestOverflowExhaustive(
1816 [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
1817 bool Overflow;
1818 (void) N1.sadd_ov(N2, Overflow);
1819 IsOverflowHigh = N1.isNonNegative();
1820 return Overflow;
1821 },
1822 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1823 return CR1.signedAddMayOverflow(CR2);
1824 });
1825 }
1826
1827 TEST_F(ConstantRangeTest, SignedSubOverflowExhaustive) {
1828 TestOverflowExhaustive(
1829 [](bool &IsOverflowHigh, const APInt &N1, const APInt &N2) {
1830 bool Overflow;
1831 (void) N1.ssub_ov(N2, Overflow);
1832 IsOverflowHigh = N1.isNonNegative();
1833 return Overflow;
1834 },
1835 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1836 return CR1.signedSubMayOverflow(CR2);
1837 });
1838 }
1839
1840 TEST_F(ConstantRangeTest, FromKnownBits) {
1841 KnownBits Unknown(16);
1842 EXPECT_EQ(Full, ConstantRange::fromKnownBits(Unknown, /*signed*/false));
1843 EXPECT_EQ(Full, ConstantRange::fromKnownBits(Unknown, /*signed*/true));
1844
1845 // .10..01. -> unsigned 01000010 (66) to 11011011 (219)
1846 // -> signed 11000010 (194) to 01011011 (91)
1847 KnownBits Known(8);
1848 Known.Zero = 36;
1849 Known.One = 66;
1850 ConstantRange Unsigned(APInt(8, 66), APInt(8, 219 + 1));
1851 ConstantRange Signed(APInt(8, 194), APInt(8, 91 + 1));
1852 EXPECT_EQ(Unsigned, ConstantRange::fromKnownBits(Known, /*signed*/false));
1853 EXPECT_EQ(Signed, ConstantRange::fromKnownBits(Known, /*signed*/true));
1854
1855 // 1.10.10. -> 10100100 (164) to 11101101 (237)
1856 Known.Zero = 18;
1857 Known.One = 164;
1858 ConstantRange CR1(APInt(8, 164), APInt(8, 237 + 1));
1859 EXPECT_EQ(CR1, ConstantRange::fromKnownBits(Known, /*signed*/false));
1860 EXPECT_EQ(CR1, ConstantRange::fromKnownBits(Known, /*signed*/true));
1861
1862 // 01.0.1.0 -> 01000100 (68) to 01101110 (110)
1863 Known.Zero = 145;
1864 Known.One = 68;
1865 ConstantRange CR2(APInt(8, 68), APInt(8, 110 + 1));
1866 EXPECT_EQ(CR2, ConstantRange::fromKnownBits(Known, /*signed*/false));
1867 EXPECT_EQ(CR2, ConstantRange::fromKnownBits(Known, /*signed*/true));
1868 }
1869
1870 TEST_F(ConstantRangeTest, FromKnownBitsExhaustive) {
1871 unsigned Bits = 4;
1872 unsigned Max = 1 << Bits;
1873 KnownBits Known(Bits);
1874 for (unsigned Zero = 0; Zero < Max; ++Zero) {
1875 for (unsigned One = 0; One < Max; ++One) {
1876 Known.Zero = Zero;
1877 Known.One = One;
1878 if (Known.hasConflict() || Known.isUnknown())
1879 continue;
1880
1881 APInt MinUnsigned = APInt::getMaxValue(Bits);
1882 APInt MaxUnsigned = APInt::getMinValue(Bits);
1883 APInt MinSigned = APInt::getSignedMaxValue(Bits);
1884 APInt MaxSigned = APInt::getSignedMinValue(Bits);
1885 for (unsigned N = 0; N < Max; ++N) {
1886 APInt Num(Bits, N);
1887 if ((Num & Known.Zero) != 0 || (~Num & Known.One) != 0)
1888 continue;
1889
1890 if (Num.ult(MinUnsigned)) MinUnsigned = Num;
1891 if (Num.ugt(MaxUnsigned)) MaxUnsigned = Num;
1892 if (Num.slt(MinSigned)) MinSigned = Num;
1893 if (Num.sgt(MaxSigned)) MaxSigned = Num;
1894 }
1895
1896 ConstantRange UnsignedCR(MinUnsigned, MaxUnsigned + 1);
1897 ConstantRange SignedCR(MinSigned, MaxSigned + 1);
1898 EXPECT_EQ(UnsignedCR, ConstantRange::fromKnownBits(Known, false));
1899 EXPECT_EQ(SignedCR, ConstantRange::fromKnownBits(Known, true));
1900 }
1901 }
1902 }
1903
1904 TEST_F(ConstantRangeTest, Negative) {
1905 // All elements in an empty set (of which there are none) are both negative
1906 // and non-negative. Empty & full sets checked explicitly for clarity, but
1907 // they are also covered by the exhaustive test below.
1908 EXPECT_TRUE(Empty.isAllNegative());
1909 EXPECT_TRUE(Empty.isAllNonNegative());
1910 EXPECT_FALSE(Full.isAllNegative());
1911 EXPECT_FALSE(Full.isAllNonNegative());
1912
1913 unsigned Bits = 4;
1914 EnumerateConstantRanges(Bits, [](const ConstantRange &CR) {
1915 bool AllNegative = true;
1916 bool AllNonNegative = true;
1917 ForeachNumInConstantRange(CR, [&](const APInt &N) {
1918 if (!N.isNegative())
1919 AllNegative = false;
1920 if (!N.isNonNegative())
1921 AllNonNegative = false;
1922 });
1923 assert((CR.isEmptySet() || !AllNegative || !AllNonNegative) &&
1924 "Only empty set can be both all negative and all non-negative");
1925
1926 EXPECT_EQ(AllNegative, CR.isAllNegative());
1927 EXPECT_EQ(AllNonNegative, CR.isAllNonNegative());
1928 });
1929 }
1930
1931 TEST_F(ConstantRangeTest, UAddSat) {
1932 TestUnsignedBinOpExhaustive(
1933 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1934 return CR1.uadd_sat(CR2);
1935 },
1936 [](const APInt &N1, const APInt &N2) {
1937 return N1.uadd_sat(N2);
1938 });
1939 }
1940
1941 TEST_F(ConstantRangeTest, USubSat) {
1942 TestUnsignedBinOpExhaustive(
1943 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1944 return CR1.usub_sat(CR2);
1945 },
1946 [](const APInt &N1, const APInt &N2) {
1947 return N1.usub_sat(N2);
1948 });
1949 }
1950
1951 TEST_F(ConstantRangeTest, SAddSat) {
1952 TestSignedBinOpExhaustive(
1953 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1954 return CR1.sadd_sat(CR2);
1955 },
1956 [](const APInt &N1, const APInt &N2) {
1957 return N1.sadd_sat(N2);
1958 });
1959 }
1960
1961 TEST_F(ConstantRangeTest, SSubSat) {
1962 TestSignedBinOpExhaustive(
1963 [](const ConstantRange &CR1, const ConstantRange &CR2) {
1964 return CR1.ssub_sat(CR2);
1965 },
1966 [](const APInt &N1, const APInt &N2) {
1967 return N1.ssub_sat(N2);
1968 });
1969 }
1970
1971 TEST_F(ConstantRangeTest, Abs) {
1972 unsigned Bits = 4;
1973 EnumerateConstantRanges(Bits, [&](const ConstantRange &CR) {
1974 // We're working with unsigned integers here, because it makes the signed
1975 // min case non-wrapping.
1976 APInt Min = APInt::getMaxValue(Bits);
1977 APInt Max = APInt::getMinValue(Bits);
1978 ForeachNumInConstantRange(CR, [&](const APInt &N) {
1979 APInt AbsN = N.abs();
1980 if (AbsN.ult(Min))
1981 Min = AbsN;
1982 if (AbsN.ugt(Max))
1983 Max = AbsN;
1984 });
1985
1986 ConstantRange AbsCR = CR.abs();
1987 if (Min.ugt(Max)) {
1988 EXPECT_TRUE(AbsCR.isEmptySet());
1989 return;
1990 }
1991
1992 ConstantRange Exact = ConstantRange::getNonEmpty(Min, Max + 1);
1993 EXPECT_EQ(Exact, AbsCR);
1994 });
1995 }
1996
1997 } // anonymous namespace
The low level virtual machine