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