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