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