unittests/IR/ConstantRangeTest.cpp

   1 //===- ConstantRangeTest.cpp - ConstantRange tests ------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "llvm/IR/ConstantRange.h"
  11 #include "llvm/IR/Instructions.h"
  12 #include "llvm/IR/Operator.h"
  13 #include "gtest/gtest.h"
  14
  15 using namespace llvm;
  16
  17 namespace {
  18
  19 class ConstantRangeTest : public ::testing::Test {
  20 protected:
  21   static ConstantRange Full;
  22   static ConstantRange Empty;
  23   static ConstantRange One;
  24   static ConstantRange Some;
  25   static ConstantRange Wrap;
  26 };
  27
  28 ConstantRange ConstantRangeTest::Full(16);
  29 ConstantRange ConstantRangeTest::Empty(16, false);
  30 ConstantRange ConstantRangeTest::One(APInt(16, 0xa));
  31 ConstantRange ConstantRangeTest::Some(APInt(16, 0xa), APInt(16, 0xaaa));
  32 ConstantRange ConstantRangeTest::Wrap(APInt(16, 0xaaa), APInt(16, 0xa));
  33
  34 TEST_F(ConstantRangeTest, Basics) {
  35   EXPECT_TRUE(Full.isFullSet());
  36   EXPECT_FALSE(Full.isEmptySet());
  37   EXPECT_TRUE(Full.inverse().isEmptySet());
  38   EXPECT_FALSE(Full.isWrappedSet());
  39   EXPECT_TRUE(Full.contains(APInt(16, 0x0)));
  40   EXPECT_TRUE(Full.contains(APInt(16, 0x9)));
  41   EXPECT_TRUE(Full.contains(APInt(16, 0xa)));
  42   EXPECT_TRUE(Full.contains(APInt(16, 0xaa9)));
  43   EXPECT_TRUE(Full.contains(APInt(16, 0xaaa)));
  44
  45   EXPECT_FALSE(Empty.isFullSet());
  46   EXPECT_TRUE(Empty.isEmptySet());
  47   EXPECT_TRUE(Empty.inverse().isFullSet());
  48   EXPECT_FALSE(Empty.isWrappedSet());
  49   EXPECT_FALSE(Empty.contains(APInt(16, 0x0)));
  50   EXPECT_FALSE(Empty.contains(APInt(16, 0x9)));
  51   EXPECT_FALSE(Empty.contains(APInt(16, 0xa)));
  52   EXPECT_FALSE(Empty.contains(APInt(16, 0xaa9)));
  53   EXPECT_FALSE(Empty.contains(APInt(16, 0xaaa)));
  54
  55   EXPECT_FALSE(One.isFullSet());
  56   EXPECT_FALSE(One.isEmptySet());
  57   EXPECT_FALSE(One.isWrappedSet());
  58   EXPECT_FALSE(One.contains(APInt(16, 0x0)));
  59   EXPECT_FALSE(One.contains(APInt(16, 0x9)));
  60   EXPECT_TRUE(One.contains(APInt(16, 0xa)));
  61   EXPECT_FALSE(One.contains(APInt(16, 0xaa9)));
  62   EXPECT_FALSE(One.contains(APInt(16, 0xaaa)));
  63   EXPECT_FALSE(One.inverse().contains(APInt(16, 0xa)));
  64
  65   EXPECT_FALSE(Some.isFullSet());
  66   EXPECT_FALSE(Some.isEmptySet());
  67   EXPECT_FALSE(Some.isWrappedSet());
  68   EXPECT_FALSE(Some.contains(APInt(16, 0x0)));
  69   EXPECT_FALSE(Some.contains(APInt(16, 0x9)));
  70   EXPECT_TRUE(Some.contains(APInt(16, 0xa)));
  71   EXPECT_TRUE(Some.contains(APInt(16, 0xaa9)));
  72   EXPECT_FALSE(Some.contains(APInt(16, 0xaaa)));
  73
  74   EXPECT_FALSE(Wrap.isFullSet());
  75   EXPECT_FALSE(Wrap.isEmptySet());
  76   EXPECT_TRUE(Wrap.isWrappedSet());
  77   EXPECT_TRUE(Wrap.contains(APInt(16, 0x0)));
  78   EXPECT_TRUE(Wrap.contains(APInt(16, 0x9)));
  79   EXPECT_FALSE(Wrap.contains(APInt(16, 0xa)));
  80   EXPECT_FALSE(Wrap.contains(APInt(16, 0xaa9)));
  81   EXPECT_TRUE(Wrap.contains(APInt(16, 0xaaa)));
  82 }
  83
  84 TEST_F(ConstantRangeTest, Equality) {
  85   EXPECT_EQ(Full, Full);
  86   EXPECT_EQ(Empty, Empty);
  87   EXPECT_EQ(One, One);
  88   EXPECT_EQ(Some, Some);
  89   EXPECT_EQ(Wrap, Wrap);
  90   EXPECT_NE(Full, Empty);
  91   EXPECT_NE(Full, One);
  92   EXPECT_NE(Full, Some);
  93   EXPECT_NE(Full, Wrap);
  94   EXPECT_NE(Empty, One);
  95   EXPECT_NE(Empty, Some);
  96   EXPECT_NE(Empty, Wrap);
  97   EXPECT_NE(One, Some);
  98   EXPECT_NE(One, Wrap);
  99   EXPECT_NE(Some, Wrap);
 100 }
 101
 102 TEST_F(ConstantRangeTest, SingleElement) {
 103   EXPECT_EQ(Full.getSingleElement(), static_cast<APInt *>(nullptr));
 104   EXPECT_EQ(Empty.getSingleElement(), static_cast<APInt *>(nullptr));
 105   EXPECT_EQ(Full.getSingleMissingElement(), static_cast<APInt *>(nullptr));
 106   EXPECT_EQ(Empty.getSingleMissingElement(), static_cast<APInt *>(nullptr));
 107
 108   EXPECT_EQ(*One.getSingleElement(), APInt(16, 0xa));
 109   EXPECT_EQ(Some.getSingleElement(), static_cast<APInt *>(nullptr));
 110   EXPECT_EQ(Wrap.getSingleElement(), static_cast<APInt *>(nullptr));
 111
 112   EXPECT_EQ(One.getSingleMissingElement(), static_cast<APInt *>(nullptr));
 113   EXPECT_EQ(Some.getSingleMissingElement(), static_cast<APInt *>(nullptr));
 114
 115   ConstantRange OneInverse = One.inverse();
 116   EXPECT_EQ(*OneInverse.getSingleMissingElement(), *One.getSingleElement());
 117
 118   EXPECT_FALSE(Full.isSingleElement());
 119   EXPECT_FALSE(Empty.isSingleElement());
 120   EXPECT_TRUE(One.isSingleElement());
 121   EXPECT_FALSE(Some.isSingleElement());
 122   EXPECT_FALSE(Wrap.isSingleElement());
 123 }
 124
 125 TEST_F(ConstantRangeTest, GetSetSize) {
 126   EXPECT_EQ(Full.getSetSize(), APInt(17, 65536));
 127   EXPECT_EQ(Empty.getSetSize(), APInt(17, 0));
 128   EXPECT_EQ(One.getSetSize(), APInt(17, 1));
 129   EXPECT_EQ(Some.getSetSize(), APInt(17, 0xaa0));
 130
 131   ConstantRange Wrap(APInt(4, 7), APInt(4, 3));
 132   ConstantRange Wrap2(APInt(4, 8), APInt(4, 7));
 133   EXPECT_EQ(Wrap.getSetSize(), APInt(5, 12));
 134   EXPECT_EQ(Wrap2.getSetSize(), APInt(5, 15));
 135 }
 136
 137 TEST_F(ConstantRangeTest, GetMinsAndMaxes) {
 138   EXPECT_EQ(Full.getUnsignedMax(), APInt(16, UINT16_MAX));
 139   EXPECT_EQ(One.getUnsignedMax(), APInt(16, 0xa));
 140   EXPECT_EQ(Some.getUnsignedMax(), APInt(16, 0xaa9));
 141   EXPECT_EQ(Wrap.getUnsignedMax(), APInt(16, UINT16_MAX));
 142
 143   EXPECT_EQ(Full.getUnsignedMin(), APInt(16, 0));
 144   EXPECT_EQ(One.getUnsignedMin(), APInt(16, 0xa));
 145   EXPECT_EQ(Some.getUnsignedMin(), APInt(16, 0xa));
 146   EXPECT_EQ(Wrap.getUnsignedMin(), APInt(16, 0));
 147
 148   EXPECT_EQ(Full.getSignedMax(), APInt(16, INT16_MAX));
 149   EXPECT_EQ(One.getSignedMax(), APInt(16, 0xa));
 150   EXPECT_EQ(Some.getSignedMax(), APInt(16, 0xaa9));
 151   EXPECT_EQ(Wrap.getSignedMax(), APInt(16, INT16_MAX));
 152
 153   EXPECT_EQ(Full.getSignedMin(), APInt(16, (uint64_t)INT16_MIN));
 154   EXPECT_EQ(One.getSignedMin(), APInt(16, 0xa));
 155   EXPECT_EQ(Some.getSignedMin(), APInt(16, 0xa));
 156   EXPECT_EQ(Wrap.getSignedMin(), APInt(16, (uint64_t)INT16_MIN));
 157
 158   // Found by Klee
 159   EXPECT_EQ(ConstantRange(APInt(4, 7), APInt(4, 0)).getSignedMax(),
 160             APInt(4, 7));
 161 }
 162
 163 TEST_F(ConstantRangeTest, SignWrapped) {
 164   EXPECT_TRUE(Full.isSignWrappedSet());
 165   EXPECT_FALSE(Empty.isSignWrappedSet());
 166   EXPECT_FALSE(One.isSignWrappedSet());
 167   EXPECT_FALSE(Some.isSignWrappedSet());
 168   EXPECT_TRUE(Wrap.isSignWrappedSet());
 169
 170   EXPECT_FALSE(ConstantRange(APInt(8, 127), APInt(8, 128)).isSignWrappedSet());
 171   EXPECT_TRUE(ConstantRange(APInt(8, 127), APInt(8, 129)).isSignWrappedSet());
 172   EXPECT_FALSE(ConstantRange(APInt(8, 128), APInt(8, 129)).isSignWrappedSet());
 173   EXPECT_TRUE(ConstantRange(APInt(8, 10), APInt(8, 9)).isSignWrappedSet());
 174   EXPECT_TRUE(ConstantRange(APInt(8, 10), APInt(8, 250)).isSignWrappedSet());
 175   EXPECT_FALSE(ConstantRange(APInt(8, 250), APInt(8, 10)).isSignWrappedSet());
 176   EXPECT_FALSE(ConstantRange(APInt(8, 250), APInt(8, 251)).isSignWrappedSet());
 177 }
 178
 179 TEST_F(ConstantRangeTest, Trunc) {
 180   ConstantRange TFull = Full.truncate(10);
 181   ConstantRange TEmpty = Empty.truncate(10);
 182   ConstantRange TOne = One.truncate(10);
 183   ConstantRange TSome = Some.truncate(10);
 184   ConstantRange TWrap = Wrap.truncate(10);
 185   EXPECT_TRUE(TFull.isFullSet());
 186   EXPECT_TRUE(TEmpty.isEmptySet());
 187   EXPECT_EQ(TOne, ConstantRange(One.getLower().trunc(10),
 188                                 One.getUpper().trunc(10)));
 189   EXPECT_TRUE(TSome.isFullSet());
 190   EXPECT_TRUE(TWrap.isFullSet());
 191
 192   // trunc([2, 5), 3->2) = [2, 1)
 193   ConstantRange TwoFive(APInt(3, 2), APInt(3, 5));
 194   EXPECT_EQ(TwoFive.truncate(2), ConstantRange(APInt(2, 2), APInt(2, 1)));
 195
 196   // trunc([2, 6), 3->2) = full
 197   ConstantRange TwoSix(APInt(3, 2), APInt(3, 6));
 198   EXPECT_TRUE(TwoSix.truncate(2).isFullSet());
 199
 200   // trunc([5, 7), 3->2) = [1, 3)
 201   ConstantRange FiveSeven(APInt(3, 5), APInt(3, 7));
 202   EXPECT_EQ(FiveSeven.truncate(2), ConstantRange(APInt(2, 1), APInt(2, 3)));
 203
 204   // trunc([7, 1), 3->2) = [3, 1)
 205   ConstantRange SevenOne(APInt(3, 7), APInt(3, 1));
 206   EXPECT_EQ(SevenOne.truncate(2), ConstantRange(APInt(2, 3), APInt(2, 1)));
 207 }
 208
 209 TEST_F(ConstantRangeTest, ZExt) {
 210   ConstantRange ZFull = Full.zeroExtend(20);
 211   ConstantRange ZEmpty = Empty.zeroExtend(20);
 212   ConstantRange ZOne = One.zeroExtend(20);
 213   ConstantRange ZSome = Some.zeroExtend(20);
 214   ConstantRange ZWrap = Wrap.zeroExtend(20);
 215   EXPECT_EQ(ZFull, ConstantRange(APInt(20, 0), APInt(20, 0x10000)));
 216   EXPECT_TRUE(ZEmpty.isEmptySet());
 217   EXPECT_EQ(ZOne, ConstantRange(One.getLower().zext(20),
 218                                 One.getUpper().zext(20)));
 219   EXPECT_EQ(ZSome, ConstantRange(Some.getLower().zext(20),
 220                                  Some.getUpper().zext(20)));
 221   EXPECT_EQ(ZWrap, ConstantRange(APInt(20, 0), APInt(20, 0x10000)));
 222
 223   // zext([5, 0), 3->7) = [5, 8)
 224   ConstantRange FiveZero(APInt(3, 5), APInt(3, 0));
 225   EXPECT_EQ(FiveZero.zeroExtend(7), ConstantRange(APInt(7, 5), APInt(7, 8)));
 226 }
 227
 228 TEST_F(ConstantRangeTest, SExt) {
 229   ConstantRange SFull = Full.signExtend(20);
 230   ConstantRange SEmpty = Empty.signExtend(20);
 231   ConstantRange SOne = One.signExtend(20);
 232   ConstantRange SSome = Some.signExtend(20);
 233   ConstantRange SWrap = Wrap.signExtend(20);
 234   EXPECT_EQ(SFull, ConstantRange(APInt(20, (uint64_t)INT16_MIN, true),
 235                                  APInt(20, INT16_MAX + 1, true)));
 236   EXPECT_TRUE(SEmpty.isEmptySet());
 237   EXPECT_EQ(SOne, ConstantRange(One.getLower().sext(20),
 238                                 One.getUpper().sext(20)));
 239   EXPECT_EQ(SSome, ConstantRange(Some.getLower().sext(20),
 240                                  Some.getUpper().sext(20)));
 241   EXPECT_EQ(SWrap, ConstantRange(APInt(20, (uint64_t)INT16_MIN, true),
 242                                  APInt(20, INT16_MAX + 1, true)));
 243
 244   EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, 140)).signExtend(16),
 245             ConstantRange(APInt(16, -128), APInt(16, 128)));
 246
 247   EXPECT_EQ(ConstantRange(APInt(16, 0x0200), APInt(16, 0x8000)).signExtend(19),
 248             ConstantRange(APInt(19, 0x0200), APInt(19, 0x8000)));
 249 }
 250
 251 TEST_F(ConstantRangeTest, IntersectWith) {
 252   EXPECT_EQ(Empty.intersectWith(Full), Empty);
 253   EXPECT_EQ(Empty.intersectWith(Empty), Empty);
 254   EXPECT_EQ(Empty.intersectWith(One), Empty);
 255   EXPECT_EQ(Empty.intersectWith(Some), Empty);
 256   EXPECT_EQ(Empty.intersectWith(Wrap), Empty);
 257   EXPECT_EQ(Full.intersectWith(Full), Full);
 258   EXPECT_EQ(Some.intersectWith(Some), Some);
 259   EXPECT_EQ(Some.intersectWith(One), One);
 260   EXPECT_EQ(Full.intersectWith(One), One);
 261   EXPECT_EQ(Full.intersectWith(Some), Some);
 262   EXPECT_EQ(Some.intersectWith(Wrap), Empty);
 263   EXPECT_EQ(One.intersectWith(Wrap), Empty);
 264   EXPECT_EQ(One.intersectWith(Wrap), Wrap.intersectWith(One));
 265
 266   // Klee generated testcase from PR4545.
 267   // The intersection of i16 [4, 2) and [6, 5) is disjoint, looking like
 268   // 01..4.6789ABCDEF where the dots represent values not in the intersection.
 269   ConstantRange LHS(APInt(16, 4), APInt(16, 2));
 270   ConstantRange RHS(APInt(16, 6), APInt(16, 5));
 271   EXPECT_TRUE(LHS.intersectWith(RHS) == LHS);
 272
 273   // previous bug: intersection of [min, 3) and [2, max) should be 2
 274   LHS = ConstantRange(APInt(32, -2147483646), APInt(32, 3));
 275   RHS = ConstantRange(APInt(32, 2), APInt(32, 2147483646));
 276   EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 2)));
 277
 278   // [2, 0) /\ [4, 3) = [2, 0)
 279   LHS = ConstantRange(APInt(32, 2), APInt(32, 0));
 280   RHS = ConstantRange(APInt(32, 4), APInt(32, 3));
 281   EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 2), APInt(32, 0)));
 282
 283   // [2, 0) /\ [4, 2) = [4, 0)
 284   LHS = ConstantRange(APInt(32, 2), APInt(32, 0));
 285   RHS = ConstantRange(APInt(32, 4), APInt(32, 2));
 286   EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 4), APInt(32, 0)));
 287
 288   // [4, 2) /\ [5, 1) = [5, 1)
 289   LHS = ConstantRange(APInt(32, 4), APInt(32, 2));
 290   RHS = ConstantRange(APInt(32, 5), APInt(32, 1));
 291   EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 5), APInt(32, 1)));
 292
 293   // [2, 0) /\ [7, 4) = [7, 4)
 294   LHS = ConstantRange(APInt(32, 2), APInt(32, 0));
 295   RHS = ConstantRange(APInt(32, 7), APInt(32, 4));
 296   EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 7), APInt(32, 4)));
 297
 298   // [4, 2) /\ [1, 0) = [1, 0)
 299   LHS = ConstantRange(APInt(32, 4), APInt(32, 2));
 300   RHS = ConstantRange(APInt(32, 1), APInt(32, 0));
 301   EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 4), APInt(32, 2)));
 302
 303   // [15, 0) /\ [7, 6) = [15, 0)
 304   LHS = ConstantRange(APInt(32, 15), APInt(32, 0));
 305   RHS = ConstantRange(APInt(32, 7), APInt(32, 6));
 306   EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 15), APInt(32, 0)));
 307 }
 308
 309 TEST_F(ConstantRangeTest, UnionWith) {
 310   EXPECT_EQ(Wrap.unionWith(One),
 311             ConstantRange(APInt(16, 0xaaa), APInt(16, 0xb)));
 312   EXPECT_EQ(One.unionWith(Wrap), Wrap.unionWith(One));
 313   EXPECT_EQ(Empty.unionWith(Empty), Empty);
 314   EXPECT_EQ(Full.unionWith(Full), Full);
 315   EXPECT_EQ(Some.unionWith(Wrap), Full);
 316
 317   // PR4545
 318   EXPECT_EQ(ConstantRange(APInt(16, 14), APInt(16, 1)).unionWith(
 319                                     ConstantRange(APInt(16, 0), APInt(16, 8))),
 320             ConstantRange(APInt(16, 14), APInt(16, 8)));
 321   EXPECT_EQ(ConstantRange(APInt(16, 6), APInt(16, 4)).unionWith(
 322                                     ConstantRange(APInt(16, 4), APInt(16, 0))),
 323               ConstantRange(16));
 324   EXPECT_EQ(ConstantRange(APInt(16, 1), APInt(16, 0)).unionWith(
 325                                     ConstantRange(APInt(16, 2), APInt(16, 1))),
 326               ConstantRange(16));
 327 }
 328
 329 TEST_F(ConstantRangeTest, SetDifference) {
 330   EXPECT_EQ(Full.difference(Empty), Full);
 331   EXPECT_EQ(Full.difference(Full), Empty);
 332   EXPECT_EQ(Empty.difference(Empty), Empty);
 333   EXPECT_EQ(Empty.difference(Full), Empty);
 334
 335   ConstantRange A(APInt(16, 3), APInt(16, 7));
 336   ConstantRange B(APInt(16, 5), APInt(16, 9));
 337   ConstantRange C(APInt(16, 3), APInt(16, 5));
 338   ConstantRange D(APInt(16, 7), APInt(16, 9));
 339   ConstantRange E(APInt(16, 5), APInt(16, 4));
 340   ConstantRange F(APInt(16, 7), APInt(16, 3));
 341   EXPECT_EQ(A.difference(B), C);
 342   EXPECT_EQ(B.difference(A), D);
 343   EXPECT_EQ(E.difference(A), F);
 344 }
 345
 346 TEST_F(ConstantRangeTest, SubtractAPInt) {
 347   EXPECT_EQ(Full.subtract(APInt(16, 4)), Full);
 348   EXPECT_EQ(Empty.subtract(APInt(16, 4)), Empty);
 349   EXPECT_EQ(Some.subtract(APInt(16, 4)),
 350             ConstantRange(APInt(16, 0x6), APInt(16, 0xaa6)));
 351   EXPECT_EQ(Wrap.subtract(APInt(16, 4)),
 352             ConstantRange(APInt(16, 0xaa6), APInt(16, 0x6)));
 353   EXPECT_EQ(One.subtract(APInt(16, 4)),
 354             ConstantRange(APInt(16, 0x6)));
 355 }
 356
 357 TEST_F(ConstantRangeTest, Add) {
 358   EXPECT_EQ(Full.add(APInt(16, 4)), Full);
 359   EXPECT_EQ(Full.add(Full), Full);
 360   EXPECT_EQ(Full.add(Empty), Empty);
 361   EXPECT_EQ(Full.add(One), Full);
 362   EXPECT_EQ(Full.add(Some), Full);
 363   EXPECT_EQ(Full.add(Wrap), Full);
 364   EXPECT_EQ(Empty.add(Empty), Empty);
 365   EXPECT_EQ(Empty.add(One), Empty);
 366   EXPECT_EQ(Empty.add(Some), Empty);
 367   EXPECT_EQ(Empty.add(Wrap), Empty);
 368   EXPECT_EQ(Empty.add(APInt(16, 4)), Empty);
 369   EXPECT_EQ(Some.add(APInt(16, 4)),
 370             ConstantRange(APInt(16, 0xe), APInt(16, 0xaae)));
 371   EXPECT_EQ(Wrap.add(APInt(16, 4)),
 372             ConstantRange(APInt(16, 0xaae), APInt(16, 0xe)));
 373   EXPECT_EQ(One.add(APInt(16, 4)),
 374             ConstantRange(APInt(16, 0xe)));
 375 }
 376
 377 TEST_F(ConstantRangeTest, AddWithNoSignedWrap) {
 378   EXPECT_EQ(Empty.addWithNoSignedWrap(APInt(16, 1)), Empty);
 379   EXPECT_EQ(Full.addWithNoSignedWrap(APInt(16, 1)),
 380             ConstantRange(APInt(16, INT16_MIN+1), APInt(16, INT16_MIN)));
 381   EXPECT_EQ(ConstantRange(APInt(8, -50), APInt(8, 50)).addWithNoSignedWrap(APInt(8, 10)),
 382             ConstantRange(APInt(8, -40), APInt(8, 60)));
 383   EXPECT_EQ(ConstantRange(APInt(8, -50), APInt(8, 120)).addWithNoSignedWrap(APInt(8, 10)),
 384             ConstantRange(APInt(8, -40), APInt(8, INT8_MIN)));
 385   EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, -10)).addWithNoSignedWrap(APInt(8, 5)),
 386             ConstantRange(APInt(8, 125), APInt(8, -5)));
 387   EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, -120)).addWithNoSignedWrap(APInt(8, 10)),
 388             ConstantRange(APInt(8, INT8_MIN+10), APInt(8, -110)));
 389
 390   EXPECT_EQ(Empty.addWithNoSignedWrap(APInt(16, -1)), Empty);
 391   EXPECT_EQ(Full.addWithNoSignedWrap(APInt(16, -1)),
 392             ConstantRange(APInt(16, INT16_MIN), APInt(16, INT16_MAX)));
 393   EXPECT_EQ(ConstantRange(APInt(8, -50), APInt(8, 50)).addWithNoSignedWrap(APInt(8, -10)),
 394             ConstantRange(APInt(8, -60), APInt(8, 40)));
 395   EXPECT_EQ(ConstantRange(APInt(8, -120), APInt(8, 50)).addWithNoSignedWrap(APInt(8, -10)),
 396             ConstantRange(APInt(8, INT8_MIN), APInt(8, 40)));
 397   EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, -120)).addWithNoSignedWrap(APInt(8, -5)),
 398             ConstantRange(APInt(8, 115), APInt(8, -125)));
 399   EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, -120)).addWithNoSignedWrap(APInt(8, -10)),
 400             ConstantRange(APInt(8, 110), APInt(8, INT8_MIN-10)));
 401 }
 402
 403 TEST_F(ConstantRangeTest, Sub) {
 404   EXPECT_EQ(Full.sub(APInt(16, 4)), Full);
 405   EXPECT_EQ(Full.sub(Full), Full);
 406   EXPECT_EQ(Full.sub(Empty), Empty);
 407   EXPECT_EQ(Full.sub(One), Full);
 408   EXPECT_EQ(Full.sub(Some), Full);
 409   EXPECT_EQ(Full.sub(Wrap), Full);
 410   EXPECT_EQ(Empty.sub(Empty), Empty);
 411   EXPECT_EQ(Empty.sub(One), Empty);
 412   EXPECT_EQ(Empty.sub(Some), Empty);
 413   EXPECT_EQ(Empty.sub(Wrap), Empty);
 414   EXPECT_EQ(Empty.sub(APInt(16, 4)), Empty);
 415   EXPECT_EQ(Some.sub(APInt(16, 4)),
 416             ConstantRange(APInt(16, 0x6), APInt(16, 0xaa6)));
 417   EXPECT_EQ(Some.sub(Some),
 418             ConstantRange(APInt(16, 0xf561), APInt(16, 0xaa0)));
 419   EXPECT_EQ(Wrap.sub(APInt(16, 4)),
 420             ConstantRange(APInt(16, 0xaa6), APInt(16, 0x6)));
 421   EXPECT_EQ(One.sub(APInt(16, 4)),
 422             ConstantRange(APInt(16, 0x6)));
 423 }
 424
 425 TEST_F(ConstantRangeTest, Multiply) {
 426   EXPECT_EQ(Full.multiply(Full), Full);
 427   EXPECT_EQ(Full.multiply(Empty), Empty);
 428   EXPECT_EQ(Full.multiply(One), Full);
 429   EXPECT_EQ(Full.multiply(Some), Full);
 430   EXPECT_EQ(Full.multiply(Wrap), Full);
 431   EXPECT_EQ(Empty.multiply(Empty), Empty);
 432   EXPECT_EQ(Empty.multiply(One), Empty);
 433   EXPECT_EQ(Empty.multiply(Some), Empty);
 434   EXPECT_EQ(Empty.multiply(Wrap), Empty);
 435   EXPECT_EQ(One.multiply(One), ConstantRange(APInt(16, 0xa*0xa),
 436                                              APInt(16, 0xa*0xa + 1)));
 437   EXPECT_EQ(One.multiply(Some), ConstantRange(APInt(16, 0xa*0xa),
 438                                               APInt(16, 0xa*0xaa9 + 1)));
 439   EXPECT_EQ(One.multiply(Wrap), Full);
 440   EXPECT_EQ(Some.multiply(Some), Full);
 441   EXPECT_EQ(Some.multiply(Wrap), Full);
 442   EXPECT_EQ(Wrap.multiply(Wrap), Full);
 443
 444   ConstantRange Zero(APInt(16, 0));
 445   EXPECT_EQ(Zero.multiply(Full), Zero);
 446   EXPECT_EQ(Zero.multiply(Some), Zero);
 447   EXPECT_EQ(Zero.multiply(Wrap), Zero);
 448   EXPECT_EQ(Full.multiply(Zero), Zero);
 449   EXPECT_EQ(Some.multiply(Zero), Zero);
 450   EXPECT_EQ(Wrap.multiply(Zero), Zero);
 451
 452   // http://llvm.org/PR4545
 453   EXPECT_EQ(ConstantRange(APInt(4, 1), APInt(4, 6)).multiply(
 454                 ConstantRange(APInt(4, 6), APInt(4, 2))),
 455             ConstantRange(4, /*isFullSet=*/true));
 456
 457   EXPECT_EQ(ConstantRange(APInt(8, 254), APInt(8, 0)).multiply(
 458               ConstantRange(APInt(8, 252), APInt(8, 4))),
 459             ConstantRange(APInt(8, 250), APInt(8, 9)));
 460   EXPECT_EQ(ConstantRange(APInt(8, 254), APInt(8, 255)).multiply(
 461               ConstantRange(APInt(8, 2), APInt(8, 4))),
 462             ConstantRange(APInt(8, 250), APInt(8, 253)));
 463
 464   // TODO: This should be return [-2, 0]
 465   EXPECT_EQ(ConstantRange(APInt(8, -2)).multiply(
 466               ConstantRange(APInt(8, 0), APInt(8, 2))),
 467             ConstantRange(APInt(8, -2), APInt(8, 1)));
 468 }
 469
 470 TEST_F(ConstantRangeTest, UMax) {
 471   EXPECT_EQ(Full.umax(Full), Full);
 472   EXPECT_EQ(Full.umax(Empty), Empty);
 473   EXPECT_EQ(Full.umax(Some), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
 474   EXPECT_EQ(Full.umax(Wrap), Full);
 475   EXPECT_EQ(Full.umax(Some), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
 476   EXPECT_EQ(Empty.umax(Empty), Empty);
 477   EXPECT_EQ(Empty.umax(Some), Empty);
 478   EXPECT_EQ(Empty.umax(Wrap), Empty);
 479   EXPECT_EQ(Empty.umax(One), Empty);
 480   EXPECT_EQ(Some.umax(Some), Some);
 481   EXPECT_EQ(Some.umax(Wrap), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
 482   EXPECT_EQ(Some.umax(One), Some);
 483   // TODO: ConstantRange is currently over-conservative here.
 484   EXPECT_EQ(Wrap.umax(Wrap), Full);
 485   EXPECT_EQ(Wrap.umax(One), ConstantRange(APInt(16, 0xa), APInt(16, 0)));
 486   EXPECT_EQ(One.umax(One), One);
 487 }
 488
 489 TEST_F(ConstantRangeTest, SMax) {
 490   EXPECT_EQ(Full.smax(Full), Full);
 491   EXPECT_EQ(Full.smax(Empty), Empty);
 492   EXPECT_EQ(Full.smax(Some), ConstantRange(APInt(16, 0xa),
 493                                            APInt::getSignedMinValue(16)));
 494   EXPECT_EQ(Full.smax(Wrap), Full);
 495   EXPECT_EQ(Full.smax(One), ConstantRange(APInt(16, 0xa),
 496                                           APInt::getSignedMinValue(16)));
 497   EXPECT_EQ(Empty.smax(Empty), Empty);
 498   EXPECT_EQ(Empty.smax(Some), Empty);
 499   EXPECT_EQ(Empty.smax(Wrap), Empty);
 500   EXPECT_EQ(Empty.smax(One), Empty);
 501   EXPECT_EQ(Some.smax(Some), Some);
 502   EXPECT_EQ(Some.smax(Wrap), ConstantRange(APInt(16, 0xa),
 503                                            APInt(16, (uint64_t)INT16_MIN)));
 504   EXPECT_EQ(Some.smax(One), Some);
 505   EXPECT_EQ(Wrap.smax(One), ConstantRange(APInt(16, 0xa),
 506                                           APInt(16, (uint64_t)INT16_MIN)));
 507   EXPECT_EQ(One.smax(One), One);
 508 }
 509
 510 TEST_F(ConstantRangeTest, UMin) {
 511   EXPECT_EQ(Full.umin(Full), Full);
 512   EXPECT_EQ(Full.umin(Empty), Empty);
 513   EXPECT_EQ(Full.umin(Some), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
 514   EXPECT_EQ(Full.umin(Wrap), Full);
 515   EXPECT_EQ(Empty.umin(Empty), Empty);
 516   EXPECT_EQ(Empty.umin(Some), Empty);
 517   EXPECT_EQ(Empty.umin(Wrap), Empty);
 518   EXPECT_EQ(Empty.umin(One), Empty);
 519   EXPECT_EQ(Some.umin(Some), Some);
 520   EXPECT_EQ(Some.umin(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
 521   EXPECT_EQ(Some.umin(One), One);
 522   // TODO: ConstantRange is currently over-conservative here.
 523   EXPECT_EQ(Wrap.umin(Wrap), Full);
 524   EXPECT_EQ(Wrap.umin(One), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
 525   EXPECT_EQ(One.umin(One), One);
 526 }
 527
 528 TEST_F(ConstantRangeTest, SMin) {
 529   EXPECT_EQ(Full.smin(Full), Full);
 530   EXPECT_EQ(Full.smin(Empty), Empty);
 531   EXPECT_EQ(Full.smin(Some), ConstantRange(APInt(16, (uint64_t)INT16_MIN),
 532                                            APInt(16, 0xaaa)));
 533   EXPECT_EQ(Full.smin(Wrap), Full);
 534   EXPECT_EQ(Empty.smin(Empty), Empty);
 535   EXPECT_EQ(Empty.smin(Some), Empty);
 536   EXPECT_EQ(Empty.smin(Wrap), Empty);
 537   EXPECT_EQ(Empty.smin(One), Empty);
 538   EXPECT_EQ(Some.smin(Some), Some);
 539   EXPECT_EQ(Some.smin(Wrap), ConstantRange(APInt(16, (uint64_t)INT16_MIN),
 540                                            APInt(16, 0xaaa)));
 541   EXPECT_EQ(Some.smin(One), One);
 542   // TODO: ConstantRange is currently over-conservative here.
 543   EXPECT_EQ(Wrap.smin(Wrap), Full);
 544   EXPECT_EQ(Wrap.smin(One), ConstantRange(APInt(16, (uint64_t)INT16_MIN),
 545                                           APInt(16, 0xb)));
 546   EXPECT_EQ(One.smin(One), One);
 547 }
 548
 549 TEST_F(ConstantRangeTest, UDiv) {
 550   EXPECT_EQ(Full.udiv(Full), Full);
 551   EXPECT_EQ(Full.udiv(Empty), Empty);
 552   EXPECT_EQ(Full.udiv(One), ConstantRange(APInt(16, 0),
 553                                           APInt(16, 0xffff / 0xa + 1)));
 554   EXPECT_EQ(Full.udiv(Some), ConstantRange(APInt(16, 0),
 555                                            APInt(16, 0xffff / 0xa + 1)));
 556   EXPECT_EQ(Full.udiv(Wrap), Full);
 557   EXPECT_EQ(Empty.udiv(Empty), Empty);
 558   EXPECT_EQ(Empty.udiv(One), Empty);
 559   EXPECT_EQ(Empty.udiv(Some), Empty);
 560   EXPECT_EQ(Empty.udiv(Wrap), Empty);
 561   EXPECT_EQ(One.udiv(One), ConstantRange(APInt(16, 1)));
 562   EXPECT_EQ(One.udiv(Some), ConstantRange(APInt(16, 0), APInt(16, 2)));
 563   EXPECT_EQ(One.udiv(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
 564   EXPECT_EQ(Some.udiv(Some), ConstantRange(APInt(16, 0), APInt(16, 0x111)));
 565   EXPECT_EQ(Some.udiv(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
 566   EXPECT_EQ(Wrap.udiv(Wrap), Full);
 567 }
 568
 569 TEST_F(ConstantRangeTest, Shl) {
 570   EXPECT_EQ(Full.shl(Full), Full);
 571   EXPECT_EQ(Full.shl(Empty), Empty);
 572   EXPECT_EQ(Full.shl(One), Full);    // TODO: [0, (-1 << 0xa) + 1)
 573   EXPECT_EQ(Full.shl(Some), Full);   // TODO: [0, (-1 << 0xa) + 1)
 574   EXPECT_EQ(Full.shl(Wrap), Full);
 575   EXPECT_EQ(Empty.shl(Empty), Empty);
 576   EXPECT_EQ(Empty.shl(One), Empty);
 577   EXPECT_EQ(Empty.shl(Some), Empty);
 578   EXPECT_EQ(Empty.shl(Wrap), Empty);
 579   EXPECT_EQ(One.shl(One), ConstantRange(APInt(16, 0xa << 0xa),
 580                                         APInt(16, (0xa << 0xa) + 1)));
 581   EXPECT_EQ(One.shl(Some), Full);    // TODO: [0xa << 0xa, 0)
 582   EXPECT_EQ(One.shl(Wrap), Full);    // TODO: [0xa, 0xa << 14 + 1)
 583   EXPECT_EQ(Some.shl(Some), Full);   // TODO: [0xa << 0xa, 0xfc01)
 584   EXPECT_EQ(Some.shl(Wrap), Full);   // TODO: [0xa, 0x7ff << 0x5 + 1)
 585   EXPECT_EQ(Wrap.shl(Wrap), Full);
 586 }
 587
 588 TEST_F(ConstantRangeTest, Lshr) {
 589   EXPECT_EQ(Full.lshr(Full), Full);
 590   EXPECT_EQ(Full.lshr(Empty), Empty);
 591   EXPECT_EQ(Full.lshr(One), ConstantRange(APInt(16, 0),
 592                                           APInt(16, (0xffff >> 0xa) + 1)));
 593   EXPECT_EQ(Full.lshr(Some), ConstantRange(APInt(16, 0),
 594                                            APInt(16, (0xffff >> 0xa) + 1)));
 595   EXPECT_EQ(Full.lshr(Wrap), Full);
 596   EXPECT_EQ(Empty.lshr(Empty), Empty);
 597   EXPECT_EQ(Empty.lshr(One), Empty);
 598   EXPECT_EQ(Empty.lshr(Some), Empty);
 599   EXPECT_EQ(Empty.lshr(Wrap), Empty);
 600   EXPECT_EQ(One.lshr(One), ConstantRange(APInt(16, 0)));
 601   EXPECT_EQ(One.lshr(Some), ConstantRange(APInt(16, 0)));
 602   EXPECT_EQ(One.lshr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
 603   EXPECT_EQ(Some.lshr(Some), ConstantRange(APInt(16, 0),
 604                                            APInt(16, (0xaaa >> 0xa) + 1)));
 605   EXPECT_EQ(Some.lshr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
 606   EXPECT_EQ(Wrap.lshr(Wrap), Full);
 607 }
 608
 609 TEST_F(ConstantRangeTest, Ashr) {
 610   EXPECT_EQ(Full.ashr(Full), Full);
 611   EXPECT_EQ(Full.ashr(Empty), Empty);
 612   EXPECT_EQ(Full.ashr(One), ConstantRange(APInt(16, 0xffe0),
 613                                           APInt(16, (0x7fff >> 0xa) + 1 )));
 614   ConstantRange Small(APInt(16, 0xa), APInt(16, 0xb));
 615   EXPECT_EQ(Full.ashr(Small), ConstantRange(APInt(16, 0xffe0),
 616                                            APInt(16, (0x7fff >> 0xa) + 1 )));
 617   EXPECT_EQ(Full.ashr(Some), ConstantRange(APInt(16, 0xffe0),
 618                                            APInt(16, (0x7fff >> 0xa) + 1 )));
 619   EXPECT_EQ(Full.ashr(Wrap), Full);
 620   EXPECT_EQ(Empty.ashr(Empty), Empty);
 621   EXPECT_EQ(Empty.ashr(One), Empty);
 622   EXPECT_EQ(Empty.ashr(Some), Empty);
 623   EXPECT_EQ(Empty.ashr(Wrap), Empty);
 624   EXPECT_EQ(One.ashr(One), ConstantRange(APInt(16, 0)));
 625   EXPECT_EQ(One.ashr(Some), ConstantRange(APInt(16, 0)));
 626   EXPECT_EQ(One.ashr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb)));
 627   EXPECT_EQ(Some.ashr(Some), ConstantRange(APInt(16, 0),
 628                                            APInt(16, (0xaaa >> 0xa) + 1)));
 629   EXPECT_EQ(Some.ashr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa)));
 630   EXPECT_EQ(Wrap.ashr(Wrap), Full);
 631   ConstantRange Neg(APInt(16, 0xf3f0, true), APInt(16, 0xf7f8, true));
 632   EXPECT_EQ(Neg.ashr(Small), ConstantRange(APInt(16, 0xfffc, true),
 633                                            APInt(16, 0xfffe, true)));
 634 }
 635
 636 TEST(ConstantRange, MakeAllowedICmpRegion) {
 637   // PR8250
 638   ConstantRange SMax = ConstantRange(APInt::getSignedMaxValue(32));
 639   EXPECT_TRUE(ConstantRange::makeAllowedICmpRegion(ICmpInst::ICMP_SGT, SMax)
 640                   .isEmptySet());
 641 }
 642
 643 TEST(ConstantRange, MakeSatisfyingICmpRegion) {
 644   ConstantRange LowHalf(APInt(8, 0), APInt(8, 128));
 645   ConstantRange HighHalf(APInt(8, 128), APInt(8, 0));
 646   ConstantRange EmptySet(8, /* isFullSet = */ false);
 647
 648   EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_NE, LowHalf),
 649             HighHalf);
 650
 651   EXPECT_EQ(
 652       ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_NE, HighHalf),
 653       LowHalf);
 654
 655   EXPECT_TRUE(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_EQ,
 656                                                       HighHalf).isEmptySet());
 657
 658   ConstantRange UnsignedSample(APInt(8, 5), APInt(8, 200));
 659
 660   EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_ULT,
 661                                                     UnsignedSample),
 662             ConstantRange(APInt(8, 0), APInt(8, 5)));
 663
 664   EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_ULE,
 665                                                     UnsignedSample),
 666             ConstantRange(APInt(8, 0), APInt(8, 6)));
 667
 668   EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_UGT,
 669                                                     UnsignedSample),
 670             ConstantRange(APInt(8, 200), APInt(8, 0)));
 671
 672   EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_UGE,
 673                                                     UnsignedSample),
 674             ConstantRange(APInt(8, 199), APInt(8, 0)));
 675
 676   ConstantRange SignedSample(APInt(8, -5), APInt(8, 5));
 677
 678   EXPECT_EQ(
 679       ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SLT, SignedSample),
 680       ConstantRange(APInt(8, -128), APInt(8, -5)));
 681
 682   EXPECT_EQ(
 683       ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SLE, SignedSample),
 684       ConstantRange(APInt(8, -128), APInt(8, -4)));
 685
 686   EXPECT_EQ(
 687       ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SGT, SignedSample),
 688       ConstantRange(APInt(8, 5), APInt(8, -128)));
 689
 690   EXPECT_EQ(
 691       ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SGE, SignedSample),
 692       ConstantRange(APInt(8, 4), APInt(8, -128)));
 693 }
 694
 695 TEST(ConstantRange, MakeGuaranteedNoWrapRegion) {
 696   const int IntMin4Bits = 8;
 697   const int IntMax4Bits = 7;
 698   typedef OverflowingBinaryOperator OBO;
 699
 700   for (int Const : {0, -1, -2, 1, 2, IntMin4Bits, IntMax4Bits}) {
 701     APInt C(4, Const, true /* = isSigned */);
 702
 703     auto NUWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
 704         Instruction::Add, C, OBO::NoUnsignedWrap);
 705
 706     EXPECT_FALSE(NUWRegion.isEmptySet());
 707
 708     auto NSWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
 709         Instruction::Add, C, OBO::NoSignedWrap);
 710
 711     EXPECT_FALSE(NSWRegion.isEmptySet());
 712
 713     auto NoWrapRegion = ConstantRange::makeGuaranteedNoWrapRegion(
 714         Instruction::Add, C, OBO::NoSignedWrap | OBO::NoUnsignedWrap);
 715
 716     EXPECT_FALSE(NoWrapRegion.isEmptySet());
 717     EXPECT_TRUE(NUWRegion.intersectWith(NSWRegion).contains(NoWrapRegion));
 718
 719     for (APInt I = NUWRegion.getLower(), E = NUWRegion.getUpper(); I != E;
 720          ++I) {
 721       bool Overflow = false;
 722       (void)I.uadd_ov(C, Overflow);
 723       EXPECT_FALSE(Overflow);
 724     }
 725
 726     for (APInt I = NSWRegion.getLower(), E = NSWRegion.getUpper(); I != E;
 727          ++I) {
 728       bool Overflow = false;
 729       (void)I.sadd_ov(C, Overflow);
 730       EXPECT_FALSE(Overflow);
 731     }
 732
 733     for (APInt I = NoWrapRegion.getLower(), E = NoWrapRegion.getUpper(); I != E;
 734          ++I) {
 735       bool Overflow = false;
 736
 737       (void)I.sadd_ov(C, Overflow);
 738       EXPECT_FALSE(Overflow);
 739
 740       (void)I.uadd_ov(C, Overflow);
 741       EXPECT_FALSE(Overflow);
 742     }
 743   }
 744
 745   for (int Const : {0, -1, -2, 1, 2, IntMin4Bits, IntMax4Bits}) {
 746     APInt C(4, Const, true /* = isSigned */);
 747
 748     auto NUWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
 749         Instruction::Sub, C, OBO::NoUnsignedWrap);
 750
 751     EXPECT_FALSE(NUWRegion.isEmptySet());
 752
 753     auto NSWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
 754         Instruction::Sub, C, OBO::NoSignedWrap);
 755
 756     EXPECT_FALSE(NSWRegion.isEmptySet());
 757
 758     auto NoWrapRegion = ConstantRange::makeGuaranteedNoWrapRegion(
 759         Instruction::Sub, C, OBO::NoSignedWrap | OBO::NoUnsignedWrap);
 760
 761     EXPECT_FALSE(NoWrapRegion.isEmptySet());
 762     EXPECT_TRUE(NUWRegion.intersectWith(NSWRegion).contains(NoWrapRegion));
 763
 764     for (APInt I = NUWRegion.getLower(), E = NUWRegion.getUpper(); I != E;
 765          ++I) {
 766       bool Overflow = false;
 767       (void)I.usub_ov(C, Overflow);
 768       EXPECT_FALSE(Overflow);
 769     }
 770
 771     for (APInt I = NSWRegion.getLower(), E = NSWRegion.getUpper(); I != E;
 772          ++I) {
 773       bool Overflow = false;
 774       (void)I.ssub_ov(C, Overflow);
 775       EXPECT_FALSE(Overflow);
 776     }
 777
 778     for (APInt I = NoWrapRegion.getLower(), E = NoWrapRegion.getUpper(); I != E;
 779          ++I) {
 780       bool Overflow = false;
 781
 782       (void)I.ssub_ov(C, Overflow);
 783       EXPECT_FALSE(Overflow);
 784
 785       (void)I.usub_ov(C, Overflow);
 786       EXPECT_FALSE(Overflow);
 787     }
 788   }
 789
 790   auto NSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
 791       Instruction::Add, ConstantRange(32, /* isFullSet = */ true),
 792       OBO::NoSignedWrap);
 793   EXPECT_TRUE(NSWForAllValues.isSingleElement() &&
 794               NSWForAllValues.getSingleElement()->isMinValue());
 795
 796   NSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
 797       Instruction::Sub, ConstantRange(32, /* isFullSet = */ true),
 798       OBO::NoSignedWrap);
 799   EXPECT_TRUE(NSWForAllValues.isSingleElement() &&
 800               NSWForAllValues.getSingleElement()->isMaxValue());
 801
 802   auto NUWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
 803       Instruction::Add, ConstantRange(32, /* isFullSet = */ true),
 804       OBO::NoUnsignedWrap);
 805   EXPECT_TRUE(NUWForAllValues.isSingleElement() &&
 806               NUWForAllValues.getSingleElement()->isMinValue());
 807
 808   NUWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
 809       Instruction::Sub, ConstantRange(32, /* isFullSet = */ true),
 810       OBO::NoUnsignedWrap);
 811   EXPECT_TRUE(NUWForAllValues.isSingleElement() &&
 812               NUWForAllValues.getSingleElement()->isMaxValue());
 813
 814   auto NUWAndNSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
 815       Instruction::Add, ConstantRange(32, /* isFullSet = */ true),
 816       OBO::NoUnsignedWrap | OBO::NoSignedWrap);
 817   EXPECT_TRUE(NUWAndNSWForAllValues.isSingleElement() &&
 818               NUWAndNSWForAllValues.getSingleElement()->isMinValue());
 819
 820   NUWAndNSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion(
 821       Instruction::Sub, ConstantRange(32, /* isFullSet = */ true),
 822       OBO::NoUnsignedWrap | OBO::NoSignedWrap);
 823   EXPECT_TRUE(NUWAndNSWForAllValues.isSingleElement() &&
 824               NUWAndNSWForAllValues.getSingleElement()->isMaxValue());
 825
 826   EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
 827       Instruction::Add, APInt(32, 0), OBO::NoUnsignedWrap).isFullSet());
 828   EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
 829       Instruction::Add, APInt(32, 0), OBO::NoSignedWrap).isFullSet());
 830   EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
 831       Instruction::Add, APInt(32, 0),
 832       OBO::NoUnsignedWrap | OBO::NoSignedWrap).isFullSet());
 833   EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
 834       Instruction::Sub, APInt(32, 0), OBO::NoUnsignedWrap).isFullSet());
 835   EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
 836       Instruction::Sub, APInt(32, 0), OBO::NoSignedWrap).isFullSet());
 837   EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion(
 838       Instruction::Sub, APInt(32, 0),
 839       OBO::NoUnsignedWrap | OBO::NoSignedWrap).isFullSet());
 840
 841   ConstantRange OneToFive(APInt(32, 1), APInt(32, 6));
 842   EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
 843                 Instruction::Add, OneToFive, OBO::NoSignedWrap),
 844             ConstantRange(APInt::getSignedMinValue(32),
 845                           APInt::getSignedMaxValue(32) - 4));
 846   EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
 847                 Instruction::Add, OneToFive, OBO::NoUnsignedWrap),
 848             ConstantRange(APInt::getMinValue(32), APInt::getMinValue(32) - 5));
 849   EXPECT_EQ(
 850       ConstantRange::makeGuaranteedNoWrapRegion(
 851           Instruction::Add, OneToFive, OBO::NoUnsignedWrap | OBO::NoSignedWrap),
 852       ConstantRange(APInt::getMinValue(32), APInt::getSignedMaxValue(32) - 4));
 853   EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
 854                 Instruction::Sub, OneToFive, OBO::NoSignedWrap),
 855             ConstantRange(APInt::getSignedMinValue(32) + 5,
 856                           APInt::getSignedMinValue(32)));
 857   EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
 858                 Instruction::Sub, OneToFive, OBO::NoUnsignedWrap),
 859             ConstantRange(APInt::getMinValue(32) + 5, APInt::getMinValue(32)));
 860   EXPECT_EQ(
 861       ConstantRange::makeGuaranteedNoWrapRegion(
 862           Instruction::Sub, OneToFive, OBO::NoUnsignedWrap | OBO::NoSignedWrap),
 863       ConstantRange(APInt::getMinValue(32) + 5, APInt::getSignedMinValue(32)));
 864
 865   ConstantRange MinusFiveToMinusTwo(APInt(32, -5), APInt(32, -1));
 866   EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
 867                 Instruction::Add, MinusFiveToMinusTwo, OBO::NoSignedWrap),
 868             ConstantRange(APInt::getSignedMinValue(32) + 5,
 869                           APInt::getSignedMinValue(32)));
 870   EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
 871                 Instruction::Add, MinusFiveToMinusTwo, OBO::NoUnsignedWrap),
 872             ConstantRange(APInt(32, 0), APInt(32, 2)));
 873   EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
 874                 Instruction::Add, MinusFiveToMinusTwo,
 875                 OBO::NoUnsignedWrap | OBO::NoSignedWrap),
 876             ConstantRange(APInt(32, 0), APInt(32, 2)));
 877   EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
 878                 Instruction::Sub, MinusFiveToMinusTwo, OBO::NoSignedWrap),
 879             ConstantRange(APInt::getSignedMinValue(32),
 880                           APInt::getSignedMaxValue(32) - 4));
 881   EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
 882                 Instruction::Sub, MinusFiveToMinusTwo, OBO::NoUnsignedWrap),
 883             ConstantRange(APInt::getMaxValue(32) - 1,
 884                           APInt::getMinValue(32)));
 885   EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
 886                 Instruction::Sub, MinusFiveToMinusTwo,
 887                 OBO::NoUnsignedWrap | OBO::NoSignedWrap),
 888             ConstantRange(APInt::getMaxValue(32) - 1,
 889                           APInt::getMinValue(32)));
 890
 891   ConstantRange MinusOneToOne(APInt(32, -1), APInt(32, 2));
 892   EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
 893                 Instruction::Add, MinusOneToOne, OBO::NoSignedWrap),
 894             ConstantRange(APInt::getSignedMinValue(32) + 1,
 895                           APInt::getSignedMinValue(32) - 1));
 896   EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
 897                 Instruction::Add, MinusOneToOne, OBO::NoUnsignedWrap),
 898             ConstantRange(APInt(32, 0), APInt(32, 1)));
 899   EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
 900                 Instruction::Add, MinusOneToOne,
 901                 OBO::NoUnsignedWrap | OBO::NoSignedWrap),
 902             ConstantRange(APInt(32, 0), APInt(32, 1)));
 903   EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
 904                 Instruction::Sub, MinusOneToOne, OBO::NoSignedWrap),
 905             ConstantRange(APInt::getSignedMinValue(32) + 1,
 906                           APInt::getSignedMinValue(32) - 1));
 907   EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
 908                 Instruction::Sub, MinusOneToOne, OBO::NoUnsignedWrap),
 909             ConstantRange(APInt::getMaxValue(32),
 910                           APInt::getMinValue(32)));
 911   EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
 912                 Instruction::Sub, MinusOneToOne,
 913                 OBO::NoUnsignedWrap | OBO::NoSignedWrap),
 914             ConstantRange(APInt::getMaxValue(32),
 915                           APInt::getMinValue(32)));
 916
 917   ConstantRange One(APInt(32, 1), APInt(32, 2));
 918   EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
 919                 Instruction::Add, One, OBO::NoSignedWrap),
 920             ConstantRange(APInt::getSignedMinValue(32),
 921                           APInt::getSignedMaxValue(32)));
 922   EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
 923                 Instruction::Add, One, OBO::NoUnsignedWrap),
 924             ConstantRange(APInt::getMinValue(32), APInt::getMaxValue(32)));
 925   EXPECT_EQ(
 926       ConstantRange::makeGuaranteedNoWrapRegion(
 927           Instruction::Add, One, OBO::NoUnsignedWrap | OBO::NoSignedWrap),
 928       ConstantRange(APInt(32, 0), APInt::getSignedMaxValue(32)));
 929   EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
 930                 Instruction::Sub, One, OBO::NoSignedWrap),
 931             ConstantRange(APInt::getSignedMinValue(32) + 1,
 932                           APInt::getSignedMinValue(32)));
 933   EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion(
 934                 Instruction::Sub, One, OBO::NoUnsignedWrap),
 935             ConstantRange(APInt::getMinValue(32) + 1, APInt::getMinValue(32)));
 936   EXPECT_EQ(
 937       ConstantRange::makeGuaranteedNoWrapRegion(
 938           Instruction::Sub, One, OBO::NoUnsignedWrap | OBO::NoSignedWrap),
 939       ConstantRange(APInt::getMinValue(32) + 1, APInt::getSignedMinValue(32)));
 940 }
 941
 942 TEST(ConstantRange, GetEquivalentICmp) {
 943   APInt RHS;
 944   CmpInst::Predicate Pred;
 945
 946   EXPECT_TRUE(ConstantRange(APInt::getMinValue(32), APInt(32, 100))
 947                   .getEquivalentICmp(Pred, RHS));
 948   EXPECT_EQ(Pred, CmpInst::ICMP_ULT);
 949   EXPECT_EQ(RHS, APInt(32, 100));
 950
 951   EXPECT_TRUE(ConstantRange(APInt::getSignedMinValue(32), APInt(32, 100))
 952                   .getEquivalentICmp(Pred, RHS));
 953   EXPECT_EQ(Pred, CmpInst::ICMP_SLT);
 954   EXPECT_EQ(RHS, APInt(32, 100));
 955
 956   EXPECT_TRUE(ConstantRange(APInt(32, 100), APInt::getMinValue(32))
 957                   .getEquivalentICmp(Pred, RHS));
 958   EXPECT_EQ(Pred, CmpInst::ICMP_UGE);
 959   EXPECT_EQ(RHS, APInt(32, 100));
 960
 961   EXPECT_TRUE(ConstantRange(APInt(32, 100), APInt::getSignedMinValue(32))
 962                   .getEquivalentICmp(Pred, RHS));
 963   EXPECT_EQ(Pred, CmpInst::ICMP_SGE);
 964   EXPECT_EQ(RHS, APInt(32, 100));
 965
 966   EXPECT_TRUE(
 967       ConstantRange(32, /*isFullSet=*/true).getEquivalentICmp(Pred, RHS));
 968   EXPECT_EQ(Pred, CmpInst::ICMP_UGE);
 969   EXPECT_EQ(RHS, APInt(32, 0));
 970
 971   EXPECT_TRUE(
 972       ConstantRange(32, /*isFullSet=*/false).getEquivalentICmp(Pred, RHS));
 973   EXPECT_EQ(Pred, CmpInst::ICMP_ULT);
 974   EXPECT_EQ(RHS, APInt(32, 0));
 975
 976   EXPECT_FALSE(ConstantRange(APInt(32, 100), APInt(32, 200))
 977                    .getEquivalentICmp(Pred, RHS));
 978
 979   EXPECT_FALSE(ConstantRange(APInt::getSignedMinValue(32) - APInt(32, 100),
 980                              APInt::getSignedMinValue(32) + APInt(32, 100))
 981                    .getEquivalentICmp(Pred, RHS));
 982
 983   EXPECT_FALSE(ConstantRange(APInt::getMinValue(32) - APInt(32, 100),
 984                              APInt::getMinValue(32) + APInt(32, 100))
 985                    .getEquivalentICmp(Pred, RHS));
 986
 987   EXPECT_TRUE(ConstantRange(APInt(32, 100)).getEquivalentICmp(Pred, RHS));
 988   EXPECT_EQ(Pred, CmpInst::ICMP_EQ);
 989   EXPECT_EQ(RHS, APInt(32, 100));
 990
 991   EXPECT_TRUE(
 992       ConstantRange(APInt(32, 100)).inverse().getEquivalentICmp(Pred, RHS));
 993   EXPECT_EQ(Pred, CmpInst::ICMP_NE);
 994   EXPECT_EQ(RHS, APInt(32, 100));
 995
 996   EXPECT_TRUE(
 997       ConstantRange(APInt(512, 100)).inverse().getEquivalentICmp(Pred, RHS));
 998   EXPECT_EQ(Pred, CmpInst::ICMP_NE);
 999   EXPECT_EQ(RHS, APInt(512, 100));
1000
1001   // NB!  It would be correct for the following four calls to getEquivalentICmp
1002   // to return ordered predicates like CmpInst::ICMP_ULT or CmpInst::ICMP_UGT.
1003   // However, that's not the case today.
1004
1005   EXPECT_TRUE(ConstantRange(APInt(32, 0)).getEquivalentICmp(Pred, RHS));
1006   EXPECT_EQ(Pred, CmpInst::ICMP_EQ);
1007   EXPECT_EQ(RHS, APInt(32, 0));
1008
1009   EXPECT_TRUE(
1010       ConstantRange(APInt(32, 0)).inverse().getEquivalentICmp(Pred, RHS));
1011   EXPECT_EQ(Pred, CmpInst::ICMP_NE);
1012   EXPECT_EQ(RHS, APInt(32, 0));
1013
1014   EXPECT_TRUE(ConstantRange(APInt(32, -1)).getEquivalentICmp(Pred, RHS));
1015   EXPECT_EQ(Pred, CmpInst::ICMP_EQ);
1016   EXPECT_EQ(RHS, APInt(32, -1));
1017
1018   EXPECT_TRUE(
1019       ConstantRange(APInt(32, -1)).inverse().getEquivalentICmp(Pred, RHS));
1020   EXPECT_EQ(Pred, CmpInst::ICMP_NE);
1021   EXPECT_EQ(RHS, APInt(32, -1));
1022 }
1023
1024 TEST(ConstantRange, MakeGuaranteedNoWrapRegionMulUnsignedSingleValue) {
1025   typedef OverflowingBinaryOperator OBO;
1026
1027   for (uint64_t I = std::numeric_limits<uint8_t>::min();
1028        I <= std::numeric_limits<uint8_t>::max(); I++) {
1029     auto Range = ConstantRange::makeGuaranteedNoWrapRegion(
1030         Instruction::Mul, ConstantRange(APInt(8, I), APInt(8, I + 1)),
1031         OBO::NoUnsignedWrap);
1032
1033     for (uint64_t V = std::numeric_limits<uint8_t>::min();
1034          V <= std::numeric_limits<uint8_t>::max(); V++) {
1035       bool Overflow;
1036       (void)APInt(8, I).umul_ov(APInt(8, V), Overflow);
1037       EXPECT_EQ(!Overflow, Range.contains(APInt(8, V)));
1038     }
1039   }
1040 }
1041
1042 TEST(ConstantRange, MakeGuaranteedNoWrapRegionMulSignedSingleValue) {
1043   typedef OverflowingBinaryOperator OBO;
1044
1045   for (int64_t I = std::numeric_limits<int8_t>::min();
1046        I <= std::numeric_limits<int8_t>::max(); I++) {
1047     auto Range = ConstantRange::makeGuaranteedNoWrapRegion(
1048         Instruction::Mul,
1049         ConstantRange(APInt(8, I, /*isSigned=*/true),
1050                       APInt(8, I + 1, /*isSigned=*/true)),
1051         OBO::NoSignedWrap);
1052
1053     for (int64_t V = std::numeric_limits<int8_t>::min();
1054          V <= std::numeric_limits<int8_t>::max(); V++) {
1055       bool Overflow;
1056       (void)APInt(8, I, /*isSigned=*/true)
1057           .smul_ov(APInt(8, V, /*isSigned=*/true), Overflow);
1058       EXPECT_EQ(!Overflow, Range.contains(APInt(8, V, /*isSigned=*/true)));
1059     }
1060   }
1061 }
1062
1063 TEST(ConstantRange, MakeGuaranteedNoWrapRegionMulUnsignedAndSignedSingleValue) {
1064   typedef OverflowingBinaryOperator OBO;
1065
1066   for (uint64_t I = std::numeric_limits<uint8_t>::min();
1067        I <= std::numeric_limits<uint8_t>::max(); I++) {
1068     auto Range = ConstantRange::makeGuaranteedNoWrapRegion(
1069         Instruction::Mul, ConstantRange(APInt(8, I), APInt(8, I + 1)),
1070         OBO::NoUnsignedWrap | OBO::NoSignedWrap);
1071
1072     for (uint64_t V = std::numeric_limits<uint8_t>::min();
1073          V <= std::numeric_limits<uint8_t>::max(); V++) {
1074       bool UOverflow;
1075       (void)APInt(8, I).umul_ov(APInt(8, V), UOverflow);
1076       bool SOverflow;
1077       (void)APInt(8, I).smul_ov(APInt(8, V), SOverflow);
1078       EXPECT_EQ(!(UOverflow || SOverflow), Range.contains(APInt(8, V)));
1079     }
1080   }
1081 }
1082
1083 TEST(ConstantRange, MakeGuaranteedNoWrapRegionMulUnsignedRange) {
1084   typedef OverflowingBinaryOperator OBO;
1085
1086   for (uint64_t Lo = std::numeric_limits<uint8_t>::min();
1087        Lo <= std::numeric_limits<uint8_t>::max(); Lo++) {
1088     for (uint64_t Hi = Lo; Hi <= std::numeric_limits<uint8_t>::max(); Hi++) {
1089       EXPECT_EQ(
1090           ConstantRange::makeGuaranteedNoWrapRegion(
1091               Instruction::Mul, ConstantRange(APInt(8, Lo), APInt(8, Hi + 1)),
1092               OBO::NoUnsignedWrap),
1093           ConstantRange::makeGuaranteedNoWrapRegion(
1094               Instruction::Mul, ConstantRange(APInt(8, Hi), APInt(8, Hi + 1)),
1095               OBO::NoUnsignedWrap));
1096     }
1097   }
1098 }
1099
1100 TEST(ConstantRange, MakeGuaranteedNoWrapRegionMulSignedRange) {
1101   typedef OverflowingBinaryOperator OBO;
1102
1103   int Lo = -12, Hi = 16;
1104   auto Range = ConstantRange::makeGuaranteedNoWrapRegion(
1105       Instruction::Mul,
1106       ConstantRange(APInt(8, Lo, /*isSigned=*/true),
1107                     APInt(8, Hi + 1, /*isSigned=*/true)),
1108       OBO::NoSignedWrap);
1109
1110   for (int64_t V = std::numeric_limits<int8_t>::min();
1111        V <= std::numeric_limits<int8_t>::max(); V++) {
1112     bool AnyOverflow = false;
1113     for (int64_t I = Lo; I <= Hi; I++) {
1114       bool Overflow;
1115       (void)APInt(8, I, /*isSigned=*/true)
1116           .smul_ov(APInt(8, V, /*isSigned=*/true), Overflow);
1117       AnyOverflow |= Overflow;
1118     }
1119     EXPECT_EQ(!AnyOverflow, Range.contains(APInt(8, V, /*isSigned=*/true)));
1120   }
1121 }
1122
1123 }  // anonymous namespace