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