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