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