1 //===- ConstantRangeTest.cpp - ConstantRange tests ------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "llvm/IR/ConstantRange.h" 10 #include "llvm/IR/Instructions.h" 11 #include "llvm/IR/Operator.h" 12 #include "llvm/Support/KnownBits.h" 13 #include "gtest/gtest.h" 14 15 using namespace llvm; 16 17 namespace { 18 19 class ConstantRangeTest : public ::testing::Test { 20 protected: 21 static ConstantRange Full; 22 static ConstantRange Empty; 23 static ConstantRange One; 24 static ConstantRange Some; 25 static ConstantRange Wrap; 26 }; 27 28 template<typename Fn> 29 static void EnumerateConstantRanges(unsigned Bits, Fn TestFn) { 30 unsigned Max = 1 << Bits; 31 for (unsigned Lo = 0; Lo < Max; Lo++) { 32 for (unsigned Hi = 0; Hi < Max; Hi++) { 33 // Enforce ConstantRange invariant. 34 if (Lo == Hi && Lo != 0 && Lo != Max - 1) 35 continue; 36 37 ConstantRange CR(APInt(Bits, Lo), APInt(Bits, Hi)); 38 TestFn(CR); 39 } 40 } 41 } 42 43 template<typename Fn> 44 static void EnumerateTwoConstantRanges(unsigned Bits, Fn TestFn) { 45 EnumerateConstantRanges(Bits, [&](const ConstantRange &CR1) { 46 EnumerateConstantRanges(Bits, [&](const ConstantRange &CR2) { 47 TestFn(CR1, CR2); 48 }); 49 }); 50 } 51 52 template<typename Fn> 53 static void ForeachNumInConstantRange(const ConstantRange &CR, Fn TestFn) { 54 if (!CR.isEmptySet()) { 55 APInt N = CR.getLower(); 56 do TestFn(N); 57 while (++N != CR.getUpper()); 58 } 59 } 60 61 template<typename Fn1, typename Fn2> 62 static void TestUnsignedBinOpExhaustive( 63 Fn1 RangeFn, Fn2 IntFn, 64 bool SkipZeroRHS = false, bool CorrectnessOnly = false) { 65 unsigned Bits = 4; 66 EnumerateTwoConstantRanges(Bits, [&](const ConstantRange &CR1, 67 const ConstantRange &CR2) { 68 APInt Min = APInt::getMaxValue(Bits); 69 APInt Max = APInt::getMinValue(Bits); 70 ForeachNumInConstantRange(CR1, [&](const APInt &N1) { 71 ForeachNumInConstantRange(CR2, [&](const APInt &N2) { 72 if (SkipZeroRHS && N2 == 0) 73 return; 74 75 APInt N = IntFn(N1, N2); 76 if (N.ult(Min)) 77 Min = N; 78 if (N.ugt(Max)) 79 Max = N; 80 }); 81 }); 82 83 ConstantRange CR = RangeFn(CR1, CR2); 84 if (Min.ugt(Max)) { 85 EXPECT_TRUE(CR.isEmptySet()); 86 return; 87 } 88 89 ConstantRange Exact = ConstantRange::getNonEmpty(Min, Max + 1); 90 if (CorrectnessOnly) { 91 EXPECT_TRUE(CR.contains(Exact)); 92 } else { 93 EXPECT_EQ(Exact, CR); 94 } 95 }); 96 } 97 98 template<typename Fn1, typename Fn2> 99 static void TestSignedBinOpExhaustive(Fn1 RangeFn, Fn2 IntFn) { 100 unsigned Bits = 4; 101 EnumerateTwoConstantRanges(Bits, [&](const ConstantRange &CR1, 102 const ConstantRange &CR2) { 103 ConstantRange CR = RangeFn(CR1, CR2); 104 if (CR1.isEmptySet() || CR2.isEmptySet()) { 105 EXPECT_TRUE(CR.isEmptySet()); 106 return; 107 } 108 109 APInt Min = APInt::getSignedMaxValue(Bits); 110 APInt Max = APInt::getSignedMinValue(Bits); 111 ForeachNumInConstantRange(CR1, [&](const APInt &N1) { 112 ForeachNumInConstantRange(CR2, [&](const APInt &N2) { 113 APInt N = IntFn(N1, N2); 114 if (N.slt(Min)) 115 Min = N; 116 if (N.sgt(Max)) 117 Max = N; 118 }); 119 }); 120 121 EXPECT_EQ(ConstantRange::getNonEmpty(Min, Max + 1), CR); 122 }); 123 } 124 125 ConstantRange ConstantRangeTest::Full(16, true); 126 ConstantRange ConstantRangeTest::Empty(16, false); 127 ConstantRange ConstantRangeTest::One(APInt(16, 0xa)); 128 ConstantRange ConstantRangeTest::Some(APInt(16, 0xa), APInt(16, 0xaaa)); 129 ConstantRange ConstantRangeTest::Wrap(APInt(16, 0xaaa), APInt(16, 0xa)); 130 131 TEST_F(ConstantRangeTest, Basics) { 132 EXPECT_TRUE(Full.isFullSet()); 133 EXPECT_FALSE(Full.isEmptySet()); 134 EXPECT_TRUE(Full.inverse().isEmptySet()); 135 EXPECT_FALSE(Full.isWrappedSet()); 136 EXPECT_TRUE(Full.contains(APInt(16, 0x0))); 137 EXPECT_TRUE(Full.contains(APInt(16, 0x9))); 138 EXPECT_TRUE(Full.contains(APInt(16, 0xa))); 139 EXPECT_TRUE(Full.contains(APInt(16, 0xaa9))); 140 EXPECT_TRUE(Full.contains(APInt(16, 0xaaa))); 141 142 EXPECT_FALSE(Empty.isFullSet()); 143 EXPECT_TRUE(Empty.isEmptySet()); 144 EXPECT_TRUE(Empty.inverse().isFullSet()); 145 EXPECT_FALSE(Empty.isWrappedSet()); 146 EXPECT_FALSE(Empty.contains(APInt(16, 0x0))); 147 EXPECT_FALSE(Empty.contains(APInt(16, 0x9))); 148 EXPECT_FALSE(Empty.contains(APInt(16, 0xa))); 149 EXPECT_FALSE(Empty.contains(APInt(16, 0xaa9))); 150 EXPECT_FALSE(Empty.contains(APInt(16, 0xaaa))); 151 152 EXPECT_FALSE(One.isFullSet()); 153 EXPECT_FALSE(One.isEmptySet()); 154 EXPECT_FALSE(One.isWrappedSet()); 155 EXPECT_FALSE(One.contains(APInt(16, 0x0))); 156 EXPECT_FALSE(One.contains(APInt(16, 0x9))); 157 EXPECT_TRUE(One.contains(APInt(16, 0xa))); 158 EXPECT_FALSE(One.contains(APInt(16, 0xaa9))); 159 EXPECT_FALSE(One.contains(APInt(16, 0xaaa))); 160 EXPECT_FALSE(One.inverse().contains(APInt(16, 0xa))); 161 162 EXPECT_FALSE(Some.isFullSet()); 163 EXPECT_FALSE(Some.isEmptySet()); 164 EXPECT_FALSE(Some.isWrappedSet()); 165 EXPECT_FALSE(Some.contains(APInt(16, 0x0))); 166 EXPECT_FALSE(Some.contains(APInt(16, 0x9))); 167 EXPECT_TRUE(Some.contains(APInt(16, 0xa))); 168 EXPECT_TRUE(Some.contains(APInt(16, 0xaa9))); 169 EXPECT_FALSE(Some.contains(APInt(16, 0xaaa))); 170 171 EXPECT_FALSE(Wrap.isFullSet()); 172 EXPECT_FALSE(Wrap.isEmptySet()); 173 EXPECT_TRUE(Wrap.isWrappedSet()); 174 EXPECT_TRUE(Wrap.contains(APInt(16, 0x0))); 175 EXPECT_TRUE(Wrap.contains(APInt(16, 0x9))); 176 EXPECT_FALSE(Wrap.contains(APInt(16, 0xa))); 177 EXPECT_FALSE(Wrap.contains(APInt(16, 0xaa9))); 178 EXPECT_TRUE(Wrap.contains(APInt(16, 0xaaa))); 179 } 180 181 TEST_F(ConstantRangeTest, Equality) { 182 EXPECT_EQ(Full, Full); 183 EXPECT_EQ(Empty, Empty); 184 EXPECT_EQ(One, One); 185 EXPECT_EQ(Some, Some); 186 EXPECT_EQ(Wrap, Wrap); 187 EXPECT_NE(Full, Empty); 188 EXPECT_NE(Full, One); 189 EXPECT_NE(Full, Some); 190 EXPECT_NE(Full, Wrap); 191 EXPECT_NE(Empty, One); 192 EXPECT_NE(Empty, Some); 193 EXPECT_NE(Empty, Wrap); 194 EXPECT_NE(One, Some); 195 EXPECT_NE(One, Wrap); 196 EXPECT_NE(Some, Wrap); 197 } 198 199 TEST_F(ConstantRangeTest, SingleElement) { 200 EXPECT_EQ(Full.getSingleElement(), static_cast<APInt *>(nullptr)); 201 EXPECT_EQ(Empty.getSingleElement(), static_cast<APInt *>(nullptr)); 202 EXPECT_EQ(Full.getSingleMissingElement(), static_cast<APInt *>(nullptr)); 203 EXPECT_EQ(Empty.getSingleMissingElement(), static_cast<APInt *>(nullptr)); 204 205 EXPECT_EQ(*One.getSingleElement(), APInt(16, 0xa)); 206 EXPECT_EQ(Some.getSingleElement(), static_cast<APInt *>(nullptr)); 207 EXPECT_EQ(Wrap.getSingleElement(), static_cast<APInt *>(nullptr)); 208 209 EXPECT_EQ(One.getSingleMissingElement(), static_cast<APInt *>(nullptr)); 210 EXPECT_EQ(Some.getSingleMissingElement(), static_cast<APInt *>(nullptr)); 211 212 ConstantRange OneInverse = One.inverse(); 213 EXPECT_EQ(*OneInverse.getSingleMissingElement(), *One.getSingleElement()); 214 215 EXPECT_FALSE(Full.isSingleElement()); 216 EXPECT_FALSE(Empty.isSingleElement()); 217 EXPECT_TRUE(One.isSingleElement()); 218 EXPECT_FALSE(Some.isSingleElement()); 219 EXPECT_FALSE(Wrap.isSingleElement()); 220 } 221 222 TEST_F(ConstantRangeTest, GetMinsAndMaxes) { 223 EXPECT_EQ(Full.getUnsignedMax(), APInt(16, UINT16_MAX)); 224 EXPECT_EQ(One.getUnsignedMax(), APInt(16, 0xa)); 225 EXPECT_EQ(Some.getUnsignedMax(), APInt(16, 0xaa9)); 226 EXPECT_EQ(Wrap.getUnsignedMax(), APInt(16, UINT16_MAX)); 227 228 EXPECT_EQ(Full.getUnsignedMin(), APInt(16, 0)); 229 EXPECT_EQ(One.getUnsignedMin(), APInt(16, 0xa)); 230 EXPECT_EQ(Some.getUnsignedMin(), APInt(16, 0xa)); 231 EXPECT_EQ(Wrap.getUnsignedMin(), APInt(16, 0)); 232 233 EXPECT_EQ(Full.getSignedMax(), APInt(16, INT16_MAX)); 234 EXPECT_EQ(One.getSignedMax(), APInt(16, 0xa)); 235 EXPECT_EQ(Some.getSignedMax(), APInt(16, 0xaa9)); 236 EXPECT_EQ(Wrap.getSignedMax(), APInt(16, INT16_MAX)); 237 238 EXPECT_EQ(Full.getSignedMin(), APInt(16, (uint64_t)INT16_MIN)); 239 EXPECT_EQ(One.getSignedMin(), APInt(16, 0xa)); 240 EXPECT_EQ(Some.getSignedMin(), APInt(16, 0xa)); 241 EXPECT_EQ(Wrap.getSignedMin(), APInt(16, (uint64_t)INT16_MIN)); 242 243 // Found by Klee 244 EXPECT_EQ(ConstantRange(APInt(4, 7), APInt(4, 0)).getSignedMax(), 245 APInt(4, 7)); 246 } 247 248 TEST_F(ConstantRangeTest, SignWrapped) { 249 EXPECT_FALSE(Full.isSignWrappedSet()); 250 EXPECT_FALSE(Empty.isSignWrappedSet()); 251 EXPECT_FALSE(One.isSignWrappedSet()); 252 EXPECT_FALSE(Some.isSignWrappedSet()); 253 EXPECT_TRUE(Wrap.isSignWrappedSet()); 254 255 EXPECT_FALSE(ConstantRange(APInt(8, 127), APInt(8, 128)).isSignWrappedSet()); 256 EXPECT_TRUE(ConstantRange(APInt(8, 127), APInt(8, 129)).isSignWrappedSet()); 257 EXPECT_FALSE(ConstantRange(APInt(8, 128), APInt(8, 129)).isSignWrappedSet()); 258 EXPECT_TRUE(ConstantRange(APInt(8, 10), APInt(8, 9)).isSignWrappedSet()); 259 EXPECT_TRUE(ConstantRange(APInt(8, 10), APInt(8, 250)).isSignWrappedSet()); 260 EXPECT_FALSE(ConstantRange(APInt(8, 250), APInt(8, 10)).isSignWrappedSet()); 261 EXPECT_FALSE(ConstantRange(APInt(8, 250), APInt(8, 251)).isSignWrappedSet()); 262 } 263 264 TEST_F(ConstantRangeTest, UpperWrapped) { 265 // The behavior here is the same as for isWrappedSet() / isSignWrappedSet(). 266 EXPECT_FALSE(Full.isUpperWrapped()); 267 EXPECT_FALSE(Empty.isUpperWrapped()); 268 EXPECT_FALSE(One.isUpperWrapped()); 269 EXPECT_FALSE(Some.isUpperWrapped()); 270 EXPECT_TRUE(Wrap.isUpperWrapped()); 271 EXPECT_FALSE(Full.isUpperSignWrapped()); 272 EXPECT_FALSE(Empty.isUpperSignWrapped()); 273 EXPECT_FALSE(One.isUpperSignWrapped()); 274 EXPECT_FALSE(Some.isUpperSignWrapped()); 275 EXPECT_TRUE(Wrap.isUpperSignWrapped()); 276 277 // The behavior differs if Upper is the Min/SignedMin value. 278 ConstantRange CR1(APInt(8, 42), APInt::getMinValue(8)); 279 EXPECT_FALSE(CR1.isWrappedSet()); 280 EXPECT_TRUE(CR1.isUpperWrapped()); 281 282 ConstantRange CR2(APInt(8, 42), APInt::getSignedMinValue(8)); 283 EXPECT_FALSE(CR2.isSignWrappedSet()); 284 EXPECT_TRUE(CR2.isUpperSignWrapped()); 285 } 286 287 TEST_F(ConstantRangeTest, Trunc) { 288 ConstantRange TFull = Full.truncate(10); 289 ConstantRange TEmpty = Empty.truncate(10); 290 ConstantRange TOne = One.truncate(10); 291 ConstantRange TSome = Some.truncate(10); 292 ConstantRange TWrap = Wrap.truncate(10); 293 EXPECT_TRUE(TFull.isFullSet()); 294 EXPECT_TRUE(TEmpty.isEmptySet()); 295 EXPECT_EQ(TOne, ConstantRange(One.getLower().trunc(10), 296 One.getUpper().trunc(10))); 297 EXPECT_TRUE(TSome.isFullSet()); 298 EXPECT_TRUE(TWrap.isFullSet()); 299 300 // trunc([2, 5), 3->2) = [2, 1) 301 ConstantRange TwoFive(APInt(3, 2), APInt(3, 5)); 302 EXPECT_EQ(TwoFive.truncate(2), ConstantRange(APInt(2, 2), APInt(2, 1))); 303 304 // trunc([2, 6), 3->2) = full 305 ConstantRange TwoSix(APInt(3, 2), APInt(3, 6)); 306 EXPECT_TRUE(TwoSix.truncate(2).isFullSet()); 307 308 // trunc([5, 7), 3->2) = [1, 3) 309 ConstantRange FiveSeven(APInt(3, 5), APInt(3, 7)); 310 EXPECT_EQ(FiveSeven.truncate(2), ConstantRange(APInt(2, 1), APInt(2, 3))); 311 312 // trunc([7, 1), 3->2) = [3, 1) 313 ConstantRange SevenOne(APInt(3, 7), APInt(3, 1)); 314 EXPECT_EQ(SevenOne.truncate(2), ConstantRange(APInt(2, 3), APInt(2, 1))); 315 } 316 317 TEST_F(ConstantRangeTest, ZExt) { 318 ConstantRange ZFull = Full.zeroExtend(20); 319 ConstantRange ZEmpty = Empty.zeroExtend(20); 320 ConstantRange ZOne = One.zeroExtend(20); 321 ConstantRange ZSome = Some.zeroExtend(20); 322 ConstantRange ZWrap = Wrap.zeroExtend(20); 323 EXPECT_EQ(ZFull, ConstantRange(APInt(20, 0), APInt(20, 0x10000))); 324 EXPECT_TRUE(ZEmpty.isEmptySet()); 325 EXPECT_EQ(ZOne, ConstantRange(One.getLower().zext(20), 326 One.getUpper().zext(20))); 327 EXPECT_EQ(ZSome, ConstantRange(Some.getLower().zext(20), 328 Some.getUpper().zext(20))); 329 EXPECT_EQ(ZWrap, ConstantRange(APInt(20, 0), APInt(20, 0x10000))); 330 331 // zext([5, 0), 3->7) = [5, 8) 332 ConstantRange FiveZero(APInt(3, 5), APInt(3, 0)); 333 EXPECT_EQ(FiveZero.zeroExtend(7), ConstantRange(APInt(7, 5), APInt(7, 8))); 334 } 335 336 TEST_F(ConstantRangeTest, SExt) { 337 ConstantRange SFull = Full.signExtend(20); 338 ConstantRange SEmpty = Empty.signExtend(20); 339 ConstantRange SOne = One.signExtend(20); 340 ConstantRange SSome = Some.signExtend(20); 341 ConstantRange SWrap = Wrap.signExtend(20); 342 EXPECT_EQ(SFull, ConstantRange(APInt(20, (uint64_t)INT16_MIN, true), 343 APInt(20, INT16_MAX + 1, true))); 344 EXPECT_TRUE(SEmpty.isEmptySet()); 345 EXPECT_EQ(SOne, ConstantRange(One.getLower().sext(20), 346 One.getUpper().sext(20))); 347 EXPECT_EQ(SSome, ConstantRange(Some.getLower().sext(20), 348 Some.getUpper().sext(20))); 349 EXPECT_EQ(SWrap, ConstantRange(APInt(20, (uint64_t)INT16_MIN, true), 350 APInt(20, INT16_MAX + 1, true))); 351 352 EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, 140)).signExtend(16), 353 ConstantRange(APInt(16, -128), APInt(16, 128))); 354 355 EXPECT_EQ(ConstantRange(APInt(16, 0x0200), APInt(16, 0x8000)).signExtend(19), 356 ConstantRange(APInt(19, 0x0200), APInt(19, 0x8000))); 357 } 358 359 TEST_F(ConstantRangeTest, IntersectWith) { 360 EXPECT_EQ(Empty.intersectWith(Full), Empty); 361 EXPECT_EQ(Empty.intersectWith(Empty), Empty); 362 EXPECT_EQ(Empty.intersectWith(One), Empty); 363 EXPECT_EQ(Empty.intersectWith(Some), Empty); 364 EXPECT_EQ(Empty.intersectWith(Wrap), Empty); 365 EXPECT_EQ(Full.intersectWith(Full), Full); 366 EXPECT_EQ(Some.intersectWith(Some), Some); 367 EXPECT_EQ(Some.intersectWith(One), One); 368 EXPECT_EQ(Full.intersectWith(One), One); 369 EXPECT_EQ(Full.intersectWith(Some), Some); 370 EXPECT_EQ(Some.intersectWith(Wrap), Empty); 371 EXPECT_EQ(One.intersectWith(Wrap), Empty); 372 EXPECT_EQ(One.intersectWith(Wrap), Wrap.intersectWith(One)); 373 374 // Klee generated testcase from PR4545. 375 // The intersection of i16 [4, 2) and [6, 5) is disjoint, looking like 376 // 01..4.6789ABCDEF where the dots represent values not in the intersection. 377 ConstantRange LHS(APInt(16, 4), APInt(16, 2)); 378 ConstantRange RHS(APInt(16, 6), APInt(16, 5)); 379 EXPECT_TRUE(LHS.intersectWith(RHS) == LHS); 380 381 // previous bug: intersection of [min, 3) and [2, max) should be 2 382 LHS = ConstantRange(APInt(32, -2147483646), APInt(32, 3)); 383 RHS = ConstantRange(APInt(32, 2), APInt(32, 2147483646)); 384 EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 2))); 385 386 // [2, 0) /\ [4, 3) = [2, 0) 387 LHS = ConstantRange(APInt(32, 2), APInt(32, 0)); 388 RHS = ConstantRange(APInt(32, 4), APInt(32, 3)); 389 EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 2), APInt(32, 0))); 390 391 // [2, 0) /\ [4, 2) = [4, 0) 392 LHS = ConstantRange(APInt(32, 2), APInt(32, 0)); 393 RHS = ConstantRange(APInt(32, 4), APInt(32, 2)); 394 EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 4), APInt(32, 0))); 395 396 // [4, 2) /\ [5, 1) = [5, 1) 397 LHS = ConstantRange(APInt(32, 4), APInt(32, 2)); 398 RHS = ConstantRange(APInt(32, 5), APInt(32, 1)); 399 EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 5), APInt(32, 1))); 400 401 // [2, 0) /\ [7, 4) = [7, 4) 402 LHS = ConstantRange(APInt(32, 2), APInt(32, 0)); 403 RHS = ConstantRange(APInt(32, 7), APInt(32, 4)); 404 EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 7), APInt(32, 4))); 405 406 // [4, 2) /\ [1, 0) = [1, 0) 407 LHS = ConstantRange(APInt(32, 4), APInt(32, 2)); 408 RHS = ConstantRange(APInt(32, 1), APInt(32, 0)); 409 EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 4), APInt(32, 2))); 410 411 // [15, 0) /\ [7, 6) = [15, 0) 412 LHS = ConstantRange(APInt(32, 15), APInt(32, 0)); 413 RHS = ConstantRange(APInt(32, 7), APInt(32, 6)); 414 EXPECT_EQ(LHS.intersectWith(RHS), ConstantRange(APInt(32, 15), APInt(32, 0))); 415 } 416 417 template<typename Fn1, typename Fn2> 418 void testBinarySetOperationExhaustive(Fn1 OpFn, Fn2 InResultFn) { 419 unsigned Bits = 4; 420 EnumerateTwoConstantRanges(Bits, 421 [=](const ConstantRange &CR1, const ConstantRange &CR2) { 422 // Collect up to three contiguous unsigned ranges. The HaveInterrupt 423 // variables are used determine when we have to switch to the next 424 // range because the previous one ended. 425 APInt Lower1(Bits, 0), Upper1(Bits, 0); 426 APInt Lower2(Bits, 0), Upper2(Bits, 0); 427 APInt Lower3(Bits, 0), Upper3(Bits, 0); 428 bool HaveRange1 = false, HaveInterrupt1 = false; 429 bool HaveRange2 = false, HaveInterrupt2 = false; 430 bool HaveRange3 = false, HaveInterrupt3 = false; 431 432 APInt Num(Bits, 0); 433 for (unsigned I = 0, Limit = 1 << Bits; I < Limit; ++I, ++Num) { 434 if (!InResultFn(CR1, CR2, Num)) { 435 if (HaveRange3) 436 HaveInterrupt3 = true; 437 else if (HaveRange2) 438 HaveInterrupt2 = true; 439 else if (HaveRange1) 440 HaveInterrupt1 = true; 441 continue; 442 } 443 444 if (HaveRange3) { 445 Upper3 = Num; 446 } else if (HaveInterrupt2) { 447 HaveRange3 = true; 448 Lower3 = Upper3 = Num; 449 } else if (HaveRange2) { 450 Upper2 = Num; 451 } else if (HaveInterrupt1) { 452 HaveRange2 = true; 453 Lower2 = Upper2 = Num; 454 } else if (HaveRange1) { 455 Upper1 = Num; 456 } else { 457 HaveRange1 = true; 458 Lower1 = Upper1 = Num; 459 } 460 } 461 462 assert(!HaveInterrupt3 && "Should have at most three ranges"); 463 464 ConstantRange SmallestCR = OpFn(CR1, CR2, ConstantRange::Smallest); 465 ConstantRange UnsignedCR = OpFn(CR1, CR2, ConstantRange::Unsigned); 466 ConstantRange SignedCR = OpFn(CR1, CR2, ConstantRange::Signed); 467 468 if (!HaveRange1) { 469 EXPECT_TRUE(SmallestCR.isEmptySet()); 470 EXPECT_TRUE(UnsignedCR.isEmptySet()); 471 EXPECT_TRUE(SignedCR.isEmptySet()); 472 return; 473 } 474 475 if (!HaveRange2) { 476 if (Lower1 == Upper1 + 1) { 477 EXPECT_TRUE(SmallestCR.isFullSet()); 478 EXPECT_TRUE(UnsignedCR.isFullSet()); 479 EXPECT_TRUE(SignedCR.isFullSet()); 480 } else { 481 ConstantRange Expected(Lower1, Upper1 + 1); 482 EXPECT_EQ(Expected, SmallestCR); 483 EXPECT_EQ(Expected, UnsignedCR); 484 EXPECT_EQ(Expected, SignedCR); 485 } 486 return; 487 } 488 489 ConstantRange Variant1(Bits, /*full*/ true); 490 ConstantRange Variant2(Bits, /*full*/ true); 491 if (!HaveRange3) { 492 // Compute the two possible ways to cover two disjoint ranges. 493 if (Lower1 != Upper2 + 1) 494 Variant1 = ConstantRange(Lower1, Upper2 + 1); 495 if (Lower2 != Upper1 + 1) 496 Variant2 = ConstantRange(Lower2, Upper1 + 1); 497 } else { 498 // If we have three ranges, the first and last one have to be adjacent 499 // to the unsigned domain. It's better to think of this as having two 500 // holes, and we can construct one range using each hole. 501 assert(Lower1.isNullValue() && Upper3.isMaxValue()); 502 Variant1 = ConstantRange(Lower2, Upper1 + 1); 503 Variant2 = ConstantRange(Lower3, Upper2 + 1); 504 } 505 506 // Smallest: Smaller set, then any set. 507 if (Variant1.isSizeStrictlySmallerThan(Variant2)) 508 EXPECT_EQ(Variant1, SmallestCR); 509 else if (Variant2.isSizeStrictlySmallerThan(Variant1)) 510 EXPECT_EQ(Variant2, SmallestCR); 511 else 512 EXPECT_TRUE(Variant1 == SmallestCR || Variant2 == SmallestCR); 513 514 // Unsigned: Non-wrapped set, then smaller set, then any set. 515 bool Variant1Full = Variant1.isFullSet() || Variant1.isWrappedSet(); 516 bool Variant2Full = Variant2.isFullSet() || Variant2.isWrappedSet(); 517 if (!Variant1Full && Variant2Full) 518 EXPECT_EQ(Variant1, UnsignedCR); 519 else if (Variant1Full && !Variant2Full) 520 EXPECT_EQ(Variant2, UnsignedCR); 521 else if (Variant1.isSizeStrictlySmallerThan(Variant2)) 522 EXPECT_EQ(Variant1, UnsignedCR); 523 else if (Variant2.isSizeStrictlySmallerThan(Variant1)) 524 EXPECT_EQ(Variant2, UnsignedCR); 525 else 526 EXPECT_TRUE(Variant1 == UnsignedCR || Variant2 == UnsignedCR); 527 528 // Signed: Signed non-wrapped set, then smaller set, then any set. 529 Variant1Full = Variant1.isFullSet() || Variant1.isSignWrappedSet(); 530 Variant2Full = Variant2.isFullSet() || Variant2.isSignWrappedSet(); 531 if (!Variant1Full && Variant2Full) 532 EXPECT_EQ(Variant1, SignedCR); 533 else if (Variant1Full && !Variant2Full) 534 EXPECT_EQ(Variant2, SignedCR); 535 else if (Variant1.isSizeStrictlySmallerThan(Variant2)) 536 EXPECT_EQ(Variant1, SignedCR); 537 else if (Variant2.isSizeStrictlySmallerThan(Variant1)) 538 EXPECT_EQ(Variant2, SignedCR); 539 else 540 EXPECT_TRUE(Variant1 == SignedCR || Variant2 == SignedCR); 541 }); 542 } 543 544 TEST_F(ConstantRangeTest, IntersectWithExhaustive) { 545 testBinarySetOperationExhaustive( 546 [](const ConstantRange &CR1, const ConstantRange &CR2, 547 ConstantRange::PreferredRangeType Type) { 548 return CR1.intersectWith(CR2, Type); 549 }, 550 [](const ConstantRange &CR1, const ConstantRange &CR2, const APInt &N) { 551 return CR1.contains(N) && CR2.contains(N); 552 }); 553 } 554 555 TEST_F(ConstantRangeTest, UnionWithExhaustive) { 556 testBinarySetOperationExhaustive( 557 [](const ConstantRange &CR1, const ConstantRange &CR2, 558 ConstantRange::PreferredRangeType Type) { 559 return CR1.unionWith(CR2, Type); 560 }, 561 [](const ConstantRange &CR1, const ConstantRange &CR2, const APInt &N) { 562 return CR1.contains(N) || CR2.contains(N); 563 }); 564 } 565 566 TEST_F(ConstantRangeTest, UnionWith) { 567 EXPECT_EQ(Wrap.unionWith(One), 568 ConstantRange(APInt(16, 0xaaa), APInt(16, 0xb))); 569 EXPECT_EQ(One.unionWith(Wrap), Wrap.unionWith(One)); 570 EXPECT_EQ(Empty.unionWith(Empty), Empty); 571 EXPECT_EQ(Full.unionWith(Full), Full); 572 EXPECT_EQ(Some.unionWith(Wrap), Full); 573 574 // PR4545 575 EXPECT_EQ(ConstantRange(APInt(16, 14), APInt(16, 1)).unionWith( 576 ConstantRange(APInt(16, 0), APInt(16, 8))), 577 ConstantRange(APInt(16, 14), APInt(16, 8))); 578 EXPECT_EQ(ConstantRange(APInt(16, 6), APInt(16, 4)).unionWith( 579 ConstantRange(APInt(16, 4), APInt(16, 0))), 580 ConstantRange::getFull(16)); 581 EXPECT_EQ(ConstantRange(APInt(16, 1), APInt(16, 0)).unionWith( 582 ConstantRange(APInt(16, 2), APInt(16, 1))), 583 ConstantRange::getFull(16)); 584 } 585 586 TEST_F(ConstantRangeTest, SetDifference) { 587 EXPECT_EQ(Full.difference(Empty), Full); 588 EXPECT_EQ(Full.difference(Full), Empty); 589 EXPECT_EQ(Empty.difference(Empty), Empty); 590 EXPECT_EQ(Empty.difference(Full), Empty); 591 592 ConstantRange A(APInt(16, 3), APInt(16, 7)); 593 ConstantRange B(APInt(16, 5), APInt(16, 9)); 594 ConstantRange C(APInt(16, 3), APInt(16, 5)); 595 ConstantRange D(APInt(16, 7), APInt(16, 9)); 596 ConstantRange E(APInt(16, 5), APInt(16, 4)); 597 ConstantRange F(APInt(16, 7), APInt(16, 3)); 598 EXPECT_EQ(A.difference(B), C); 599 EXPECT_EQ(B.difference(A), D); 600 EXPECT_EQ(E.difference(A), F); 601 } 602 603 TEST_F(ConstantRangeTest, SubtractAPInt) { 604 EXPECT_EQ(Full.subtract(APInt(16, 4)), Full); 605 EXPECT_EQ(Empty.subtract(APInt(16, 4)), Empty); 606 EXPECT_EQ(Some.subtract(APInt(16, 4)), 607 ConstantRange(APInt(16, 0x6), APInt(16, 0xaa6))); 608 EXPECT_EQ(Wrap.subtract(APInt(16, 4)), 609 ConstantRange(APInt(16, 0xaa6), APInt(16, 0x6))); 610 EXPECT_EQ(One.subtract(APInt(16, 4)), 611 ConstantRange(APInt(16, 0x6))); 612 } 613 614 TEST_F(ConstantRangeTest, Add) { 615 EXPECT_EQ(Full.add(APInt(16, 4)), Full); 616 EXPECT_EQ(Full.add(Full), Full); 617 EXPECT_EQ(Full.add(Empty), Empty); 618 EXPECT_EQ(Full.add(One), Full); 619 EXPECT_EQ(Full.add(Some), Full); 620 EXPECT_EQ(Full.add(Wrap), Full); 621 EXPECT_EQ(Empty.add(Empty), Empty); 622 EXPECT_EQ(Empty.add(One), Empty); 623 EXPECT_EQ(Empty.add(Some), Empty); 624 EXPECT_EQ(Empty.add(Wrap), Empty); 625 EXPECT_EQ(Empty.add(APInt(16, 4)), Empty); 626 EXPECT_EQ(Some.add(APInt(16, 4)), 627 ConstantRange(APInt(16, 0xe), APInt(16, 0xaae))); 628 EXPECT_EQ(Wrap.add(APInt(16, 4)), 629 ConstantRange(APInt(16, 0xaae), APInt(16, 0xe))); 630 EXPECT_EQ(One.add(APInt(16, 4)), 631 ConstantRange(APInt(16, 0xe))); 632 } 633 634 TEST_F(ConstantRangeTest, AddWithNoSignedWrap) { 635 EXPECT_EQ(Empty.addWithNoSignedWrap(APInt(16, 1)), Empty); 636 EXPECT_EQ(Full.addWithNoSignedWrap(APInt(16, 1)), 637 ConstantRange(APInt(16, INT16_MIN+1), APInt(16, INT16_MIN))); 638 EXPECT_EQ(ConstantRange(APInt(8, -50), APInt(8, 50)).addWithNoSignedWrap(APInt(8, 10)), 639 ConstantRange(APInt(8, -40), APInt(8, 60))); 640 EXPECT_EQ(ConstantRange(APInt(8, -50), APInt(8, 120)).addWithNoSignedWrap(APInt(8, 10)), 641 ConstantRange(APInt(8, -40), APInt(8, INT8_MIN))); 642 EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, -10)).addWithNoSignedWrap(APInt(8, 5)), 643 ConstantRange(APInt(8, 125), APInt(8, -5))); 644 EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, -120)).addWithNoSignedWrap(APInt(8, 10)), 645 ConstantRange(APInt(8, INT8_MIN+10), APInt(8, -110))); 646 647 EXPECT_EQ(Empty.addWithNoSignedWrap(APInt(16, -1)), Empty); 648 EXPECT_EQ(Full.addWithNoSignedWrap(APInt(16, -1)), 649 ConstantRange(APInt(16, INT16_MIN), APInt(16, INT16_MAX))); 650 EXPECT_EQ(ConstantRange(APInt(8, -50), APInt(8, 50)).addWithNoSignedWrap(APInt(8, -10)), 651 ConstantRange(APInt(8, -60), APInt(8, 40))); 652 EXPECT_EQ(ConstantRange(APInt(8, -120), APInt(8, 50)).addWithNoSignedWrap(APInt(8, -10)), 653 ConstantRange(APInt(8, INT8_MIN), APInt(8, 40))); 654 EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, -120)).addWithNoSignedWrap(APInt(8, -5)), 655 ConstantRange(APInt(8, 115), APInt(8, -125))); 656 EXPECT_EQ(ConstantRange(APInt(8, 120), APInt(8, -120)).addWithNoSignedWrap(APInt(8, -10)), 657 ConstantRange(APInt(8, 110), APInt(8, INT8_MIN-10))); 658 } 659 660 TEST_F(ConstantRangeTest, Sub) { 661 EXPECT_EQ(Full.sub(APInt(16, 4)), Full); 662 EXPECT_EQ(Full.sub(Full), Full); 663 EXPECT_EQ(Full.sub(Empty), Empty); 664 EXPECT_EQ(Full.sub(One), Full); 665 EXPECT_EQ(Full.sub(Some), Full); 666 EXPECT_EQ(Full.sub(Wrap), Full); 667 EXPECT_EQ(Empty.sub(Empty), Empty); 668 EXPECT_EQ(Empty.sub(One), Empty); 669 EXPECT_EQ(Empty.sub(Some), Empty); 670 EXPECT_EQ(Empty.sub(Wrap), Empty); 671 EXPECT_EQ(Empty.sub(APInt(16, 4)), Empty); 672 EXPECT_EQ(Some.sub(APInt(16, 4)), 673 ConstantRange(APInt(16, 0x6), APInt(16, 0xaa6))); 674 EXPECT_EQ(Some.sub(Some), 675 ConstantRange(APInt(16, 0xf561), APInt(16, 0xaa0))); 676 EXPECT_EQ(Wrap.sub(APInt(16, 4)), 677 ConstantRange(APInt(16, 0xaa6), APInt(16, 0x6))); 678 EXPECT_EQ(One.sub(APInt(16, 4)), 679 ConstantRange(APInt(16, 0x6))); 680 } 681 682 TEST_F(ConstantRangeTest, Multiply) { 683 EXPECT_EQ(Full.multiply(Full), Full); 684 EXPECT_EQ(Full.multiply(Empty), Empty); 685 EXPECT_EQ(Full.multiply(One), Full); 686 EXPECT_EQ(Full.multiply(Some), Full); 687 EXPECT_EQ(Full.multiply(Wrap), Full); 688 EXPECT_EQ(Empty.multiply(Empty), Empty); 689 EXPECT_EQ(Empty.multiply(One), Empty); 690 EXPECT_EQ(Empty.multiply(Some), Empty); 691 EXPECT_EQ(Empty.multiply(Wrap), Empty); 692 EXPECT_EQ(One.multiply(One), ConstantRange(APInt(16, 0xa*0xa), 693 APInt(16, 0xa*0xa + 1))); 694 EXPECT_EQ(One.multiply(Some), ConstantRange(APInt(16, 0xa*0xa), 695 APInt(16, 0xa*0xaa9 + 1))); 696 EXPECT_EQ(One.multiply(Wrap), Full); 697 EXPECT_EQ(Some.multiply(Some), Full); 698 EXPECT_EQ(Some.multiply(Wrap), Full); 699 EXPECT_EQ(Wrap.multiply(Wrap), Full); 700 701 ConstantRange Zero(APInt(16, 0)); 702 EXPECT_EQ(Zero.multiply(Full), Zero); 703 EXPECT_EQ(Zero.multiply(Some), Zero); 704 EXPECT_EQ(Zero.multiply(Wrap), Zero); 705 EXPECT_EQ(Full.multiply(Zero), Zero); 706 EXPECT_EQ(Some.multiply(Zero), Zero); 707 EXPECT_EQ(Wrap.multiply(Zero), Zero); 708 709 // http://llvm.org/PR4545 710 EXPECT_EQ(ConstantRange(APInt(4, 1), APInt(4, 6)).multiply( 711 ConstantRange(APInt(4, 6), APInt(4, 2))), 712 ConstantRange(4, /*isFullSet=*/true)); 713 714 EXPECT_EQ(ConstantRange(APInt(8, 254), APInt(8, 0)).multiply( 715 ConstantRange(APInt(8, 252), APInt(8, 4))), 716 ConstantRange(APInt(8, 250), APInt(8, 9))); 717 EXPECT_EQ(ConstantRange(APInt(8, 254), APInt(8, 255)).multiply( 718 ConstantRange(APInt(8, 2), APInt(8, 4))), 719 ConstantRange(APInt(8, 250), APInt(8, 253))); 720 721 // TODO: This should be return [-2, 0] 722 EXPECT_EQ(ConstantRange(APInt(8, -2)).multiply( 723 ConstantRange(APInt(8, 0), APInt(8, 2))), 724 ConstantRange(APInt(8, -2), APInt(8, 1))); 725 } 726 727 TEST_F(ConstantRangeTest, UMax) { 728 EXPECT_EQ(Full.umax(Full), Full); 729 EXPECT_EQ(Full.umax(Empty), Empty); 730 EXPECT_EQ(Full.umax(Some), ConstantRange(APInt(16, 0xa), APInt(16, 0))); 731 EXPECT_EQ(Full.umax(Wrap), Full); 732 EXPECT_EQ(Full.umax(Some), ConstantRange(APInt(16, 0xa), APInt(16, 0))); 733 EXPECT_EQ(Empty.umax(Empty), Empty); 734 EXPECT_EQ(Empty.umax(Some), Empty); 735 EXPECT_EQ(Empty.umax(Wrap), Empty); 736 EXPECT_EQ(Empty.umax(One), Empty); 737 EXPECT_EQ(Some.umax(Some), Some); 738 EXPECT_EQ(Some.umax(Wrap), ConstantRange(APInt(16, 0xa), APInt(16, 0))); 739 EXPECT_EQ(Some.umax(One), Some); 740 // TODO: ConstantRange is currently over-conservative here. 741 EXPECT_EQ(Wrap.umax(Wrap), Full); 742 EXPECT_EQ(Wrap.umax(One), ConstantRange(APInt(16, 0xa), APInt(16, 0))); 743 EXPECT_EQ(One.umax(One), One); 744 } 745 746 TEST_F(ConstantRangeTest, SMax) { 747 EXPECT_EQ(Full.smax(Full), Full); 748 EXPECT_EQ(Full.smax(Empty), Empty); 749 EXPECT_EQ(Full.smax(Some), ConstantRange(APInt(16, 0xa), 750 APInt::getSignedMinValue(16))); 751 EXPECT_EQ(Full.smax(Wrap), Full); 752 EXPECT_EQ(Full.smax(One), ConstantRange(APInt(16, 0xa), 753 APInt::getSignedMinValue(16))); 754 EXPECT_EQ(Empty.smax(Empty), Empty); 755 EXPECT_EQ(Empty.smax(Some), Empty); 756 EXPECT_EQ(Empty.smax(Wrap), Empty); 757 EXPECT_EQ(Empty.smax(One), Empty); 758 EXPECT_EQ(Some.smax(Some), Some); 759 EXPECT_EQ(Some.smax(Wrap), ConstantRange(APInt(16, 0xa), 760 APInt(16, (uint64_t)INT16_MIN))); 761 EXPECT_EQ(Some.smax(One), Some); 762 EXPECT_EQ(Wrap.smax(One), ConstantRange(APInt(16, 0xa), 763 APInt(16, (uint64_t)INT16_MIN))); 764 EXPECT_EQ(One.smax(One), One); 765 } 766 767 TEST_F(ConstantRangeTest, UMin) { 768 EXPECT_EQ(Full.umin(Full), Full); 769 EXPECT_EQ(Full.umin(Empty), Empty); 770 EXPECT_EQ(Full.umin(Some), ConstantRange(APInt(16, 0), APInt(16, 0xaaa))); 771 EXPECT_EQ(Full.umin(Wrap), Full); 772 EXPECT_EQ(Empty.umin(Empty), Empty); 773 EXPECT_EQ(Empty.umin(Some), Empty); 774 EXPECT_EQ(Empty.umin(Wrap), Empty); 775 EXPECT_EQ(Empty.umin(One), Empty); 776 EXPECT_EQ(Some.umin(Some), Some); 777 EXPECT_EQ(Some.umin(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa))); 778 EXPECT_EQ(Some.umin(One), One); 779 // TODO: ConstantRange is currently over-conservative here. 780 EXPECT_EQ(Wrap.umin(Wrap), Full); 781 EXPECT_EQ(Wrap.umin(One), ConstantRange(APInt(16, 0), APInt(16, 0xb))); 782 EXPECT_EQ(One.umin(One), One); 783 } 784 785 TEST_F(ConstantRangeTest, SMin) { 786 EXPECT_EQ(Full.smin(Full), Full); 787 EXPECT_EQ(Full.smin(Empty), Empty); 788 EXPECT_EQ(Full.smin(Some), ConstantRange(APInt(16, (uint64_t)INT16_MIN), 789 APInt(16, 0xaaa))); 790 EXPECT_EQ(Full.smin(Wrap), Full); 791 EXPECT_EQ(Empty.smin(Empty), Empty); 792 EXPECT_EQ(Empty.smin(Some), Empty); 793 EXPECT_EQ(Empty.smin(Wrap), Empty); 794 EXPECT_EQ(Empty.smin(One), Empty); 795 EXPECT_EQ(Some.smin(Some), Some); 796 EXPECT_EQ(Some.smin(Wrap), ConstantRange(APInt(16, (uint64_t)INT16_MIN), 797 APInt(16, 0xaaa))); 798 EXPECT_EQ(Some.smin(One), One); 799 // TODO: ConstantRange is currently over-conservative here. 800 EXPECT_EQ(Wrap.smin(Wrap), Full); 801 EXPECT_EQ(Wrap.smin(One), ConstantRange(APInt(16, (uint64_t)INT16_MIN), 802 APInt(16, 0xb))); 803 EXPECT_EQ(One.smin(One), One); 804 } 805 806 TEST_F(ConstantRangeTest, UDiv) { 807 EXPECT_EQ(Full.udiv(Full), Full); 808 EXPECT_EQ(Full.udiv(Empty), Empty); 809 EXPECT_EQ(Full.udiv(One), ConstantRange(APInt(16, 0), 810 APInt(16, 0xffff / 0xa + 1))); 811 EXPECT_EQ(Full.udiv(Some), ConstantRange(APInt(16, 0), 812 APInt(16, 0xffff / 0xa + 1))); 813 EXPECT_EQ(Full.udiv(Wrap), Full); 814 EXPECT_EQ(Empty.udiv(Empty), Empty); 815 EXPECT_EQ(Empty.udiv(One), Empty); 816 EXPECT_EQ(Empty.udiv(Some), Empty); 817 EXPECT_EQ(Empty.udiv(Wrap), Empty); 818 EXPECT_EQ(One.udiv(One), ConstantRange(APInt(16, 1))); 819 EXPECT_EQ(One.udiv(Some), ConstantRange(APInt(16, 0), APInt(16, 2))); 820 EXPECT_EQ(One.udiv(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb))); 821 EXPECT_EQ(Some.udiv(Some), ConstantRange(APInt(16, 0), APInt(16, 0x111))); 822 EXPECT_EQ(Some.udiv(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa))); 823 EXPECT_EQ(Wrap.udiv(Wrap), Full); 824 825 826 ConstantRange Zero(APInt(16, 0)); 827 EXPECT_EQ(Zero.udiv(One), Zero); 828 EXPECT_EQ(Zero.udiv(Full), Zero); 829 830 EXPECT_EQ(ConstantRange(APInt(16, 0), APInt(16, 99)).udiv(Full), 831 ConstantRange(APInt(16, 0), APInt(16, 99))); 832 EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 99)).udiv(Full), 833 ConstantRange(APInt(16, 0), APInt(16, 99))); 834 } 835 836 TEST_F(ConstantRangeTest, URem) { 837 EXPECT_EQ(Full.urem(Empty), Empty); 838 EXPECT_EQ(Empty.urem(Full), Empty); 839 // urem by zero is poison. 840 EXPECT_EQ(Full.urem(ConstantRange(APInt(16, 0))), Empty); 841 // urem by full range doesn't contain MaxValue. 842 EXPECT_EQ(Full.urem(Full), ConstantRange(APInt(16, 0), APInt(16, 0xffff))); 843 // urem is upper bounded by maximum RHS minus one. 844 EXPECT_EQ(Full.urem(ConstantRange(APInt(16, 0), APInt(16, 123))), 845 ConstantRange(APInt(16, 0), APInt(16, 122))); 846 // urem is upper bounded by maximum LHS. 847 EXPECT_EQ(ConstantRange(APInt(16, 0), APInt(16, 123)).urem(Full), 848 ConstantRange(APInt(16, 0), APInt(16, 123))); 849 // If the LHS is always lower than the RHS, the result is the LHS. 850 EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 20)) 851 .urem(ConstantRange(APInt(16, 20), APInt(16, 30))), 852 ConstantRange(APInt(16, 10), APInt(16, 20))); 853 // It has to be strictly lower, otherwise the top value may wrap to zero. 854 EXPECT_EQ(ConstantRange(APInt(16, 10), APInt(16, 20)) 855 .urem(ConstantRange(APInt(16, 19), APInt(16, 30))), 856 ConstantRange(APInt(16, 0), APInt(16, 20))); 857 // [12, 14] % 10 is [2, 4], but we conservatively compute [0, 9]. 858 EXPECT_EQ(ConstantRange(APInt(16, 12), APInt(16, 15)) 859 .urem(ConstantRange(APInt(16, 10))), 860 ConstantRange(APInt(16, 0), APInt(16, 10))); 861 862 TestUnsignedBinOpExhaustive( 863 [](const ConstantRange &CR1, const ConstantRange &CR2) { 864 return CR1.urem(CR2); 865 }, 866 [](const APInt &N1, const APInt &N2) { 867 return N1.urem(N2); 868 }, 869 /* SkipZeroRHS */ true, /* CorrectnessOnly */ true); 870 } 871 872 TEST_F(ConstantRangeTest, Shl) { 873 ConstantRange Some2(APInt(16, 0xfff), APInt(16, 0x8000)); 874 ConstantRange WrapNullMax(APInt(16, 0x1), APInt(16, 0x0)); 875 EXPECT_EQ(Full.shl(Full), Full); 876 EXPECT_EQ(Full.shl(Empty), Empty); 877 EXPECT_EQ(Full.shl(One), Full); // TODO: [0, (-1 << 0xa) + 1) 878 EXPECT_EQ(Full.shl(Some), Full); // TODO: [0, (-1 << 0xa) + 1) 879 EXPECT_EQ(Full.shl(Wrap), Full); 880 EXPECT_EQ(Empty.shl(Empty), Empty); 881 EXPECT_EQ(Empty.shl(One), Empty); 882 EXPECT_EQ(Empty.shl(Some), Empty); 883 EXPECT_EQ(Empty.shl(Wrap), Empty); 884 EXPECT_EQ(One.shl(One), ConstantRange(APInt(16, 0xa << 0xa), 885 APInt(16, (0xa << 0xa) + 1))); 886 EXPECT_EQ(One.shl(Some), Full); // TODO: [0xa << 0xa, 0) 887 EXPECT_EQ(One.shl(Wrap), Full); // TODO: [0xa, 0xa << 14 + 1) 888 EXPECT_EQ(Some.shl(Some), Full); // TODO: [0xa << 0xa, 0xfc01) 889 EXPECT_EQ(Some.shl(Wrap), Full); // TODO: [0xa, 0x7ff << 0x5 + 1) 890 EXPECT_EQ(Wrap.shl(Wrap), Full); 891 EXPECT_EQ( 892 Some2.shl(ConstantRange(APInt(16, 0x1))), 893 ConstantRange(APInt(16, 0xfff << 0x1), APInt(16, 0x7fff << 0x1) + 1)); 894 EXPECT_EQ(One.shl(WrapNullMax), Full); 895 } 896 897 TEST_F(ConstantRangeTest, Lshr) { 898 EXPECT_EQ(Full.lshr(Full), Full); 899 EXPECT_EQ(Full.lshr(Empty), Empty); 900 EXPECT_EQ(Full.lshr(One), ConstantRange(APInt(16, 0), 901 APInt(16, (0xffff >> 0xa) + 1))); 902 EXPECT_EQ(Full.lshr(Some), ConstantRange(APInt(16, 0), 903 APInt(16, (0xffff >> 0xa) + 1))); 904 EXPECT_EQ(Full.lshr(Wrap), Full); 905 EXPECT_EQ(Empty.lshr(Empty), Empty); 906 EXPECT_EQ(Empty.lshr(One), Empty); 907 EXPECT_EQ(Empty.lshr(Some), Empty); 908 EXPECT_EQ(Empty.lshr(Wrap), Empty); 909 EXPECT_EQ(One.lshr(One), ConstantRange(APInt(16, 0))); 910 EXPECT_EQ(One.lshr(Some), ConstantRange(APInt(16, 0))); 911 EXPECT_EQ(One.lshr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb))); 912 EXPECT_EQ(Some.lshr(Some), ConstantRange(APInt(16, 0), 913 APInt(16, (0xaaa >> 0xa) + 1))); 914 EXPECT_EQ(Some.lshr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa))); 915 EXPECT_EQ(Wrap.lshr(Wrap), Full); 916 } 917 918 TEST_F(ConstantRangeTest, Ashr) { 919 EXPECT_EQ(Full.ashr(Full), Full); 920 EXPECT_EQ(Full.ashr(Empty), Empty); 921 EXPECT_EQ(Full.ashr(One), ConstantRange(APInt(16, 0xffe0), 922 APInt(16, (0x7fff >> 0xa) + 1 ))); 923 ConstantRange Small(APInt(16, 0xa), APInt(16, 0xb)); 924 EXPECT_EQ(Full.ashr(Small), ConstantRange(APInt(16, 0xffe0), 925 APInt(16, (0x7fff >> 0xa) + 1 ))); 926 EXPECT_EQ(Full.ashr(Some), ConstantRange(APInt(16, 0xffe0), 927 APInt(16, (0x7fff >> 0xa) + 1 ))); 928 EXPECT_EQ(Full.ashr(Wrap), Full); 929 EXPECT_EQ(Empty.ashr(Empty), Empty); 930 EXPECT_EQ(Empty.ashr(One), Empty); 931 EXPECT_EQ(Empty.ashr(Some), Empty); 932 EXPECT_EQ(Empty.ashr(Wrap), Empty); 933 EXPECT_EQ(One.ashr(One), ConstantRange(APInt(16, 0))); 934 EXPECT_EQ(One.ashr(Some), ConstantRange(APInt(16, 0))); 935 EXPECT_EQ(One.ashr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xb))); 936 EXPECT_EQ(Some.ashr(Some), ConstantRange(APInt(16, 0), 937 APInt(16, (0xaaa >> 0xa) + 1))); 938 EXPECT_EQ(Some.ashr(Wrap), ConstantRange(APInt(16, 0), APInt(16, 0xaaa))); 939 EXPECT_EQ(Wrap.ashr(Wrap), Full); 940 ConstantRange Neg(APInt(16, 0xf3f0, true), APInt(16, 0xf7f8, true)); 941 EXPECT_EQ(Neg.ashr(Small), ConstantRange(APInt(16, 0xfffc, true), 942 APInt(16, 0xfffe, true))); 943 } 944 945 TEST(ConstantRange, MakeAllowedICmpRegion) { 946 // PR8250 947 ConstantRange SMax = ConstantRange(APInt::getSignedMaxValue(32)); 948 EXPECT_TRUE(ConstantRange::makeAllowedICmpRegion(ICmpInst::ICMP_SGT, SMax) 949 .isEmptySet()); 950 } 951 952 TEST(ConstantRange, MakeSatisfyingICmpRegion) { 953 ConstantRange LowHalf(APInt(8, 0), APInt(8, 128)); 954 ConstantRange HighHalf(APInt(8, 128), APInt(8, 0)); 955 ConstantRange EmptySet(8, /* isFullSet = */ false); 956 957 EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_NE, LowHalf), 958 HighHalf); 959 960 EXPECT_EQ( 961 ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_NE, HighHalf), 962 LowHalf); 963 964 EXPECT_TRUE(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_EQ, 965 HighHalf).isEmptySet()); 966 967 ConstantRange UnsignedSample(APInt(8, 5), APInt(8, 200)); 968 969 EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_ULT, 970 UnsignedSample), 971 ConstantRange(APInt(8, 0), APInt(8, 5))); 972 973 EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_ULE, 974 UnsignedSample), 975 ConstantRange(APInt(8, 0), APInt(8, 6))); 976 977 EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_UGT, 978 UnsignedSample), 979 ConstantRange(APInt(8, 200), APInt(8, 0))); 980 981 EXPECT_EQ(ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_UGE, 982 UnsignedSample), 983 ConstantRange(APInt(8, 199), APInt(8, 0))); 984 985 ConstantRange SignedSample(APInt(8, -5), APInt(8, 5)); 986 987 EXPECT_EQ( 988 ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SLT, SignedSample), 989 ConstantRange(APInt(8, -128), APInt(8, -5))); 990 991 EXPECT_EQ( 992 ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SLE, SignedSample), 993 ConstantRange(APInt(8, -128), APInt(8, -4))); 994 995 EXPECT_EQ( 996 ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SGT, SignedSample), 997 ConstantRange(APInt(8, 5), APInt(8, -128))); 998 999 EXPECT_EQ( 1000 ConstantRange::makeSatisfyingICmpRegion(ICmpInst::ICMP_SGE, SignedSample), 1001 ConstantRange(APInt(8, 4), APInt(8, -128))); 1002 } 1003 1004 TEST(ConstantRange, MakeGuaranteedNoWrapRegion) { 1005 const int IntMin4Bits = 8; 1006 const int IntMax4Bits = 7; 1007 typedef OverflowingBinaryOperator OBO; 1008 1009 for (int Const : {0, -1, -2, 1, 2, IntMin4Bits, IntMax4Bits}) { 1010 APInt C(4, Const, true /* = isSigned */); 1011 1012 auto NUWRegion = ConstantRange::makeGuaranteedNoWrapRegion( 1013 Instruction::Add, C, OBO::NoUnsignedWrap); 1014 1015 EXPECT_FALSE(NUWRegion.isEmptySet()); 1016 1017 auto NSWRegion = ConstantRange::makeGuaranteedNoWrapRegion( 1018 Instruction::Add, C, OBO::NoSignedWrap); 1019 1020 EXPECT_FALSE(NSWRegion.isEmptySet()); 1021 1022 for (APInt I = NUWRegion.getLower(), E = NUWRegion.getUpper(); I != E; 1023 ++I) { 1024 bool Overflow = false; 1025 (void)I.uadd_ov(C, Overflow); 1026 EXPECT_FALSE(Overflow); 1027 } 1028 1029 for (APInt I = NSWRegion.getLower(), E = NSWRegion.getUpper(); I != E; 1030 ++I) { 1031 bool Overflow = false; 1032 (void)I.sadd_ov(C, Overflow); 1033 EXPECT_FALSE(Overflow); 1034 } 1035 } 1036 1037 for (int Const : {0, -1, -2, 1, 2, IntMin4Bits, IntMax4Bits}) { 1038 APInt C(4, Const, true /* = isSigned */); 1039 1040 auto NUWRegion = ConstantRange::makeGuaranteedNoWrapRegion( 1041 Instruction::Sub, C, OBO::NoUnsignedWrap); 1042 1043 EXPECT_FALSE(NUWRegion.isEmptySet()); 1044 1045 auto NSWRegion = ConstantRange::makeGuaranteedNoWrapRegion( 1046 Instruction::Sub, C, OBO::NoSignedWrap); 1047 1048 EXPECT_FALSE(NSWRegion.isEmptySet()); 1049 1050 for (APInt I = NUWRegion.getLower(), E = NUWRegion.getUpper(); I != E; 1051 ++I) { 1052 bool Overflow = false; 1053 (void)I.usub_ov(C, Overflow); 1054 EXPECT_FALSE(Overflow); 1055 } 1056 1057 for (APInt I = NSWRegion.getLower(), E = NSWRegion.getUpper(); I != E; 1058 ++I) { 1059 bool Overflow = false; 1060 (void)I.ssub_ov(C, Overflow); 1061 EXPECT_FALSE(Overflow); 1062 } 1063 } 1064 1065 auto NSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion( 1066 Instruction::Add, ConstantRange(32, /* isFullSet = */ true), 1067 OBO::NoSignedWrap); 1068 EXPECT_TRUE(NSWForAllValues.isSingleElement() && 1069 NSWForAllValues.getSingleElement()->isMinValue()); 1070 1071 NSWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion( 1072 Instruction::Sub, ConstantRange(32, /* isFullSet = */ true), 1073 OBO::NoSignedWrap); 1074 EXPECT_TRUE(NSWForAllValues.isSingleElement() && 1075 NSWForAllValues.getSingleElement()->isMaxValue()); 1076 1077 auto NUWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion( 1078 Instruction::Add, ConstantRange(32, /* isFullSet = */ true), 1079 OBO::NoUnsignedWrap); 1080 EXPECT_TRUE(NUWForAllValues.isSingleElement() && 1081 NUWForAllValues.getSingleElement()->isMinValue()); 1082 1083 NUWForAllValues = ConstantRange::makeGuaranteedNoWrapRegion( 1084 Instruction::Sub, ConstantRange(32, /* isFullSet = */ true), 1085 OBO::NoUnsignedWrap); 1086 EXPECT_TRUE(NUWForAllValues.isSingleElement() && 1087 NUWForAllValues.getSingleElement()->isMaxValue()); 1088 1089 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion( 1090 Instruction::Add, APInt(32, 0), OBO::NoUnsignedWrap).isFullSet()); 1091 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion( 1092 Instruction::Add, APInt(32, 0), OBO::NoSignedWrap).isFullSet()); 1093 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion( 1094 Instruction::Sub, APInt(32, 0), OBO::NoUnsignedWrap).isFullSet()); 1095 EXPECT_TRUE(ConstantRange::makeGuaranteedNoWrapRegion( 1096 Instruction::Sub, APInt(32, 0), OBO::NoSignedWrap).isFullSet()); 1097 1098 ConstantRange OneToFive(APInt(32, 1), APInt(32, 6)); 1099 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 1100 Instruction::Add, OneToFive, OBO::NoSignedWrap), 1101 ConstantRange(APInt::getSignedMinValue(32), 1102 APInt::getSignedMaxValue(32) - 4)); 1103 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 1104 Instruction::Add, OneToFive, OBO::NoUnsignedWrap), 1105 ConstantRange(APInt::getMinValue(32), APInt::getMinValue(32) - 5)); 1106 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 1107 Instruction::Sub, OneToFive, OBO::NoSignedWrap), 1108 ConstantRange(APInt::getSignedMinValue(32) + 5, 1109 APInt::getSignedMinValue(32))); 1110 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 1111 Instruction::Sub, OneToFive, OBO::NoUnsignedWrap), 1112 ConstantRange(APInt::getMinValue(32) + 5, APInt::getMinValue(32))); 1113 1114 ConstantRange MinusFiveToMinusTwo(APInt(32, -5), APInt(32, -1)); 1115 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 1116 Instruction::Add, MinusFiveToMinusTwo, OBO::NoSignedWrap), 1117 ConstantRange(APInt::getSignedMinValue(32) + 5, 1118 APInt::getSignedMinValue(32))); 1119 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 1120 Instruction::Add, MinusFiveToMinusTwo, OBO::NoUnsignedWrap), 1121 ConstantRange(APInt(32, 0), APInt(32, 2))); 1122 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 1123 Instruction::Sub, MinusFiveToMinusTwo, OBO::NoSignedWrap), 1124 ConstantRange(APInt::getSignedMinValue(32), 1125 APInt::getSignedMaxValue(32) - 4)); 1126 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 1127 Instruction::Sub, MinusFiveToMinusTwo, OBO::NoUnsignedWrap), 1128 ConstantRange(APInt::getMaxValue(32) - 1, 1129 APInt::getMinValue(32))); 1130 1131 ConstantRange MinusOneToOne(APInt(32, -1), APInt(32, 2)); 1132 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 1133 Instruction::Add, MinusOneToOne, OBO::NoSignedWrap), 1134 ConstantRange(APInt::getSignedMinValue(32) + 1, 1135 APInt::getSignedMinValue(32) - 1)); 1136 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 1137 Instruction::Add, MinusOneToOne, OBO::NoUnsignedWrap), 1138 ConstantRange(APInt(32, 0), APInt(32, 1))); 1139 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 1140 Instruction::Sub, MinusOneToOne, OBO::NoSignedWrap), 1141 ConstantRange(APInt::getSignedMinValue(32) + 1, 1142 APInt::getSignedMinValue(32) - 1)); 1143 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 1144 Instruction::Sub, MinusOneToOne, OBO::NoUnsignedWrap), 1145 ConstantRange(APInt::getMaxValue(32), 1146 APInt::getMinValue(32))); 1147 1148 ConstantRange One(APInt(32, 1), APInt(32, 2)); 1149 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 1150 Instruction::Add, One, OBO::NoSignedWrap), 1151 ConstantRange(APInt::getSignedMinValue(32), 1152 APInt::getSignedMaxValue(32))); 1153 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 1154 Instruction::Add, One, OBO::NoUnsignedWrap), 1155 ConstantRange(APInt::getMinValue(32), APInt::getMaxValue(32))); 1156 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 1157 Instruction::Sub, One, OBO::NoSignedWrap), 1158 ConstantRange(APInt::getSignedMinValue(32) + 1, 1159 APInt::getSignedMinValue(32))); 1160 EXPECT_EQ(ConstantRange::makeGuaranteedNoWrapRegion( 1161 Instruction::Sub, One, OBO::NoUnsignedWrap), 1162 ConstantRange(APInt::getMinValue(32) + 1, APInt::getMinValue(32))); 1163 } 1164 1165 template<typename Fn> 1166 void TestNoWrapRegionExhaustive(Instruction::BinaryOps BinOp, 1167 unsigned NoWrapKind, Fn OverflowFn) { 1168 // When using 4 bits this test needs ~3s on a debug build. 1169 unsigned Bits = 3; 1170 EnumerateTwoConstantRanges(Bits, 1171 [&](const ConstantRange &CR1, const ConstantRange &CR2) { 1172 if (CR2.isEmptySet()) 1173 return; 1174 1175 ConstantRange NoWrap = 1176 ConstantRange::makeGuaranteedNoWrapRegion(BinOp, CR2, NoWrapKind); 1177 ForeachNumInConstantRange(CR1, [&](const APInt &N1) { 1178 bool NoOverflow = true; 1179 bool Overflow = true; 1180 ForeachNumInConstantRange(CR2, [&](const APInt &N2) { 1181 if (OverflowFn(N1, N2)) 1182 NoOverflow = false; 1183 else 1184 Overflow = false; 1185 }); 1186 EXPECT_EQ(NoOverflow, NoWrap.contains(N1)); 1187 1188 // The no-wrap range is exact for single-element ranges. 1189 if (CR2.isSingleElement()) { 1190 EXPECT_EQ(Overflow, !NoWrap.contains(N1)); 1191 } 1192 }); 1193 }); 1194 } 1195 1196 // Show that makeGuaranteedNoWrapRegion() is maximal, and for single-element 1197 // ranges also exact. 1198 TEST(ConstantRange, NoWrapRegionExhaustive) { 1199 TestNoWrapRegionExhaustive( 1200 Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap, 1201 [](const APInt &N1, const APInt &N2) { 1202 bool Overflow; 1203 (void) N1.uadd_ov(N2, Overflow); 1204 return Overflow; 1205 }); 1206 TestNoWrapRegionExhaustive( 1207 Instruction::Add, OverflowingBinaryOperator::NoSignedWrap, 1208 [](const APInt &N1, const APInt &N2) { 1209 bool Overflow; 1210 (void) N1.sadd_ov(N2, Overflow); 1211 return Overflow; 1212 }); 1213 TestNoWrapRegionExhaustive( 1214 Instruction::Sub, OverflowingBinaryOperator::NoUnsignedWrap, 1215 [](const APInt &N1, const APInt &N2) { 1216 bool Overflow; 1217 (void) N1.usub_ov(N2, Overflow); 1218 return Overflow; 1219 }); 1220 TestNoWrapRegionExhaustive( 1221 Instruction::Sub, OverflowingBinaryOperator::NoSignedWrap, 1222 [](const APInt &N1, const APInt &N2) { 1223 bool Overflow; 1224 (void) N1.ssub_ov(N2, Overflow); 1225 return Overflow; 1226 }); 1227 TestNoWrapRegionExhaustive( 1228 Instruction::Mul, OverflowingBinaryOperator::NoUnsignedWrap, 1229 [](const APInt &N1, const APInt &N2) { 1230 bool Overflow; 1231 (void) N1.umul_ov(N2, Overflow); 1232 return Overflow; 1233 }); 1234 TestNoWrapRegionExhaustive( 1235 Instruction::Mul, OverflowingBinaryOperator::NoSignedWrap, 1236 [](const APInt &N1, const APInt &N2) { 1237 bool Overflow; 1238 (void) N1.smul_ov(N2, Overflow); 1239 return Overflow; 1240 }); 1241 } 1242 1243 TEST(ConstantRange, GetEquivalentICmp) { 1244 APInt RHS; 1245 CmpInst::Predicate Pred; 1246 1247 EXPECT_TRUE(ConstantRange(APInt::getMinValue(32), APInt(32, 100)) 1248 .getEquivalentICmp(Pred, RHS)); 1249 EXPECT_EQ(Pred, CmpInst::ICMP_ULT); 1250 EXPECT_EQ(RHS, APInt(32, 100)); 1251 1252 EXPECT_TRUE(ConstantRange(APInt::getSignedMinValue(32), APInt(32, 100)) 1253 .getEquivalentICmp(Pred, RHS)); 1254 EXPECT_EQ(Pred, CmpInst::ICMP_SLT); 1255 EXPECT_EQ(RHS, APInt(32, 100)); 1256 1257 EXPECT_TRUE(ConstantRange(APInt(32, 100), APInt::getMinValue(32)) 1258 .getEquivalentICmp(Pred, RHS)); 1259 EXPECT_EQ(Pred, CmpInst::ICMP_UGE); 1260 EXPECT_EQ(RHS, APInt(32, 100)); 1261 1262 EXPECT_TRUE(ConstantRange(APInt(32, 100), APInt::getSignedMinValue(32)) 1263 .getEquivalentICmp(Pred, RHS)); 1264 EXPECT_EQ(Pred, CmpInst::ICMP_SGE); 1265 EXPECT_EQ(RHS, APInt(32, 100)); 1266 1267 EXPECT_TRUE( 1268 ConstantRange(32, /*isFullSet=*/true).getEquivalentICmp(Pred, RHS)); 1269 EXPECT_EQ(Pred, CmpInst::ICMP_UGE); 1270 EXPECT_EQ(RHS, APInt(32, 0)); 1271 1272 EXPECT_TRUE( 1273 ConstantRange(32, /*isFullSet=*/false).getEquivalentICmp(Pred, RHS)); 1274 EXPECT_EQ(Pred, CmpInst::ICMP_ULT); 1275 EXPECT_EQ(RHS, APInt(32, 0)); 1276 1277 EXPECT_FALSE(ConstantRange(APInt(32, 100), APInt(32, 200)) 1278 .getEquivalentICmp(Pred, RHS)); 1279 1280 EXPECT_FALSE(ConstantRange(APInt::getSignedMinValue(32) - APInt(32, 100), 1281 APInt::getSignedMinValue(32) + APInt(32, 100)) 1282 .getEquivalentICmp(Pred, RHS)); 1283 1284 EXPECT_FALSE(ConstantRange(APInt::getMinValue(32) - APInt(32, 100), 1285 APInt::getMinValue(32) + APInt(32, 100)) 1286 .getEquivalentICmp(Pred, RHS)); 1287 1288 EXPECT_TRUE(ConstantRange(APInt(32, 100)).getEquivalentICmp(Pred, RHS)); 1289 EXPECT_EQ(Pred, CmpInst::ICMP_EQ); 1290 EXPECT_EQ(RHS, APInt(32, 100)); 1291 1292 EXPECT_TRUE( 1293 ConstantRange(APInt(32, 100)).inverse().getEquivalentICmp(Pred, RHS)); 1294 EXPECT_EQ(Pred, CmpInst::ICMP_NE); 1295 EXPECT_EQ(RHS, APInt(32, 100)); 1296 1297 EXPECT_TRUE( 1298 ConstantRange(APInt(512, 100)).inverse().getEquivalentICmp(Pred, RHS)); 1299 EXPECT_EQ(Pred, CmpInst::ICMP_NE); 1300 EXPECT_EQ(RHS, APInt(512, 100)); 1301 1302 // NB! It would be correct for the following four calls to getEquivalentICmp 1303 // to return ordered predicates like CmpInst::ICMP_ULT or CmpInst::ICMP_UGT. 1304 // However, that's not the case today. 1305 1306 EXPECT_TRUE(ConstantRange(APInt(32, 0)).getEquivalentICmp(Pred, RHS)); 1307 EXPECT_EQ(Pred, CmpInst::ICMP_EQ); 1308 EXPECT_EQ(RHS, APInt(32, 0)); 1309 1310 EXPECT_TRUE( 1311 ConstantRange(APInt(32, 0)).inverse().getEquivalentICmp(Pred, RHS)); 1312 EXPECT_EQ(Pred, CmpInst::ICMP_NE); 1313 EXPECT_EQ(RHS, APInt(32, 0)); 1314 1315 EXPECT_TRUE(ConstantRange(APInt(32, -1)).getEquivalentICmp(Pred, RHS)); 1316 EXPECT_EQ(Pred, CmpInst::ICMP_EQ); 1317 EXPECT_EQ(RHS, APInt(32, -1)); 1318 1319 EXPECT_TRUE( 1320 ConstantRange(APInt(32, -1)).inverse().getEquivalentICmp(Pred, RHS)); 1321 EXPECT_EQ(Pred, CmpInst::ICMP_NE); 1322 EXPECT_EQ(RHS, APInt(32, -1)); 1323 } 1324 1325 TEST(ConstantRange, MakeGuaranteedNoWrapRegionMulUnsignedSingleValue) { 1326 typedef OverflowingBinaryOperator OBO; 1327 1328 for (uint64_t I = std::numeric_limits<uint8_t>::min(); 1329 I <= std::numeric_limits<uint8_t>::max(); I++) { 1330 auto Range = ConstantRange::makeGuaranteedNoWrapRegion( 1331 Instruction::Mul, ConstantRange(APInt(8, I), APInt(8, I + 1)), 1332 OBO::NoUnsignedWrap); 1333 1334 for (uint64_t V = std::numeric_limits<uint8_t>::min(); 1335 V <= std::numeric_limits<uint8_t>::max(); V++) { 1336 bool Overflow; 1337 (void)APInt(8, I).umul_ov(APInt(8, V), Overflow); 1338 EXPECT_EQ(!Overflow, Range.contains(APInt(8, V))); 1339 } 1340 } 1341 } 1342 1343 TEST(ConstantRange, MakeGuaranteedNoWrapRegionMulSignedSingleValue) { 1344 typedef OverflowingBinaryOperator OBO; 1345 1346 for (int64_t I = std::numeric_limits<int8_t>::min(); 1347 I <= std::numeric_limits<int8_t>::max(); I++) { 1348 auto Range = ConstantRange::makeGuaranteedNoWrapRegion( 1349 Instruction::Mul, 1350 ConstantRange(APInt(8, I, /*isSigned=*/true), 1351 APInt(8, I + 1, /*isSigned=*/true)), 1352 OBO::NoSignedWrap); 1353 1354 for (int64_t V = std::numeric_limits<int8_t>::min(); 1355 V <= std::numeric_limits<int8_t>::max(); V++) { 1356 bool Overflow; 1357 (void)APInt(8, I, /*isSigned=*/true) 1358 .smul_ov(APInt(8, V, /*isSigned=*/true), Overflow); 1359 EXPECT_EQ(!Overflow, Range.contains(APInt(8, V, /*isSigned=*/true))); 1360 } 1361 } 1362 } 1363 1364 TEST(ConstantRange, MakeGuaranteedNoWrapRegionMulUnsignedRange) { 1365 typedef OverflowingBinaryOperator OBO; 1366 1367 for (uint64_t Lo = std::numeric_limits<uint8_t>::min(); 1368 Lo <= std::numeric_limits<uint8_t>::max(); Lo++) { 1369 for (uint64_t Hi = Lo; Hi <= std::numeric_limits<uint8_t>::max(); Hi++) { 1370 EXPECT_EQ( 1371 ConstantRange::makeGuaranteedNoWrapRegion( 1372 Instruction::Mul, ConstantRange(APInt(8, Lo), APInt(8, Hi + 1)), 1373 OBO::NoUnsignedWrap), 1374 ConstantRange::makeGuaranteedNoWrapRegion( 1375 Instruction::Mul, ConstantRange(APInt(8, Hi), APInt(8, Hi + 1)), 1376 OBO::NoUnsignedWrap)); 1377 } 1378 } 1379 } 1380 1381 TEST(ConstantRange, MakeGuaranteedNoWrapRegionMulSignedRange) { 1382 typedef OverflowingBinaryOperator OBO; 1383 1384 int Lo = -12, Hi = 16; 1385 auto Range = ConstantRange::makeGuaranteedNoWrapRegion( 1386 Instruction::Mul, 1387 ConstantRange(APInt(8, Lo, /*isSigned=*/true), 1388 APInt(8, Hi + 1, /*isSigned=*/true)), 1389 OBO::NoSignedWrap); 1390 1391 for (int64_t V = std::numeric_limits<int8_t>::min(); 1392 V <= std::numeric_limits<int8_t>::max(); V++) { 1393 bool AnyOverflow = false; 1394 for (int64_t I = Lo; I <= Hi; I++) { 1395 bool Overflow; 1396 (void)APInt(8, I, /*isSigned=*/true) 1397 .smul_ov(APInt(8, V, /*isSigned=*/true), Overflow); 1398 AnyOverflow |= Overflow; 1399 } 1400 EXPECT_EQ(!AnyOverflow, Range.contains(APInt(8, V, /*isSigned=*/true))); 1401 } 1402 } 1403 1404 #define EXPECT_MAY_OVERFLOW(op) \ 1405 EXPECT_EQ(ConstantRange::OverflowResult::MayOverflow, (op)) 1406 #define EXPECT_ALWAYS_OVERFLOWS(op) \ 1407 EXPECT_EQ(ConstantRange::OverflowResult::AlwaysOverflows, (op)) 1408 #define EXPECT_NEVER_OVERFLOWS(op) \ 1409 EXPECT_EQ(ConstantRange::OverflowResult::NeverOverflows, (op)) 1410 1411 TEST_F(ConstantRangeTest, UnsignedAddOverflow) { 1412 // Ill-defined - may overflow is a conservative result. 1413 EXPECT_MAY_OVERFLOW(Some.unsignedAddMayOverflow(Empty)); 1414 EXPECT_MAY_OVERFLOW(Empty.unsignedAddMayOverflow(Some)); 1415 1416 // Never overflow despite one full/wrap set. 1417 ConstantRange Zero(APInt::getNullValue(16)); 1418 EXPECT_NEVER_OVERFLOWS(Full.unsignedAddMayOverflow(Zero)); 1419 EXPECT_NEVER_OVERFLOWS(Wrap.unsignedAddMayOverflow(Zero)); 1420 EXPECT_NEVER_OVERFLOWS(Zero.unsignedAddMayOverflow(Full)); 1421 EXPECT_NEVER_OVERFLOWS(Zero.unsignedAddMayOverflow(Wrap)); 1422 1423 // But usually full/wrap always may overflow. 1424 EXPECT_MAY_OVERFLOW(Full.unsignedAddMayOverflow(One)); 1425 EXPECT_MAY_OVERFLOW(Wrap.unsignedAddMayOverflow(One)); 1426 EXPECT_MAY_OVERFLOW(One.unsignedAddMayOverflow(Full)); 1427 EXPECT_MAY_OVERFLOW(One.unsignedAddMayOverflow(Wrap)); 1428 1429 ConstantRange A(APInt(16, 0xfd00), APInt(16, 0xfe00)); 1430 ConstantRange B1(APInt(16, 0x0100), APInt(16, 0x0201)); 1431 ConstantRange B2(APInt(16, 0x0100), APInt(16, 0x0202)); 1432 EXPECT_NEVER_OVERFLOWS(A.unsignedAddMayOverflow(B1)); 1433 EXPECT_MAY_OVERFLOW(A.unsignedAddMayOverflow(B2)); 1434 EXPECT_NEVER_OVERFLOWS(B1.unsignedAddMayOverflow(A)); 1435 EXPECT_MAY_OVERFLOW(B2.unsignedAddMayOverflow(A)); 1436 1437 ConstantRange C1(APInt(16, 0x0299), APInt(16, 0x0400)); 1438 ConstantRange C2(APInt(16, 0x0300), APInt(16, 0x0400)); 1439 EXPECT_MAY_OVERFLOW(A.unsignedAddMayOverflow(C1)); 1440 EXPECT_ALWAYS_OVERFLOWS(A.unsignedAddMayOverflow(C2)); 1441 EXPECT_MAY_OVERFLOW(C1.unsignedAddMayOverflow(A)); 1442 EXPECT_ALWAYS_OVERFLOWS(C2.unsignedAddMayOverflow(A)); 1443 } 1444 1445 TEST_F(ConstantRangeTest, UnsignedSubOverflow) { 1446 // Ill-defined - may overflow is a conservative result. 1447 EXPECT_MAY_OVERFLOW(Some.unsignedSubMayOverflow(Empty)); 1448 EXPECT_MAY_OVERFLOW(Empty.unsignedSubMayOverflow(Some)); 1449 1450 // Never overflow despite one full/wrap set. 1451 ConstantRange Zero(APInt::getNullValue(16)); 1452 ConstantRange Max(APInt::getAllOnesValue(16)); 1453 EXPECT_NEVER_OVERFLOWS(Full.unsignedSubMayOverflow(Zero)); 1454 EXPECT_NEVER_OVERFLOWS(Wrap.unsignedSubMayOverflow(Zero)); 1455 EXPECT_NEVER_OVERFLOWS(Max.unsignedSubMayOverflow(Full)); 1456 EXPECT_NEVER_OVERFLOWS(Max.unsignedSubMayOverflow(Wrap)); 1457 1458 // But usually full/wrap always may overflow. 1459 EXPECT_MAY_OVERFLOW(Full.unsignedSubMayOverflow(One)); 1460 EXPECT_MAY_OVERFLOW(Wrap.unsignedSubMayOverflow(One)); 1461 EXPECT_MAY_OVERFLOW(One.unsignedSubMayOverflow(Full)); 1462 EXPECT_MAY_OVERFLOW(One.unsignedSubMayOverflow(Wrap)); 1463 1464 ConstantRange A(APInt(16, 0x0000), APInt(16, 0x0100)); 1465 ConstantRange B(APInt(16, 0x0100), APInt(16, 0x0200)); 1466 EXPECT_NEVER_OVERFLOWS(B.unsignedSubMayOverflow(A)); 1467 EXPECT_ALWAYS_OVERFLOWS(A.unsignedSubMayOverflow(B)); 1468 1469 ConstantRange A1(APInt(16, 0x0000), APInt(16, 0x0101)); 1470 ConstantRange B1(APInt(16, 0x0100), APInt(16, 0x0201)); 1471 EXPECT_NEVER_OVERFLOWS(B1.unsignedSubMayOverflow(A1)); 1472 EXPECT_MAY_OVERFLOW(A1.unsignedSubMayOverflow(B1)); 1473 1474 ConstantRange A2(APInt(16, 0x0000), APInt(16, 0x0102)); 1475 ConstantRange B2(APInt(16, 0x0100), APInt(16, 0x0202)); 1476 EXPECT_MAY_OVERFLOW(B2.unsignedSubMayOverflow(A2)); 1477 EXPECT_MAY_OVERFLOW(A2.unsignedSubMayOverflow(B2)); 1478 } 1479 1480 TEST_F(ConstantRangeTest, SignedAddOverflow) { 1481 // Ill-defined - may overflow is a conservative result. 1482 EXPECT_MAY_OVERFLOW(Some.signedAddMayOverflow(Empty)); 1483 EXPECT_MAY_OVERFLOW(Empty.signedAddMayOverflow(Some)); 1484 1485 // Never overflow despite one full/wrap set. 1486 ConstantRange Zero(APInt::getNullValue(16)); 1487 EXPECT_NEVER_OVERFLOWS(Full.signedAddMayOverflow(Zero)); 1488 EXPECT_NEVER_OVERFLOWS(Wrap.signedAddMayOverflow(Zero)); 1489 EXPECT_NEVER_OVERFLOWS(Zero.signedAddMayOverflow(Full)); 1490 EXPECT_NEVER_OVERFLOWS(Zero.signedAddMayOverflow(Wrap)); 1491 1492 // But usually full/wrap always may overflow. 1493 EXPECT_MAY_OVERFLOW(Full.signedAddMayOverflow(One)); 1494 EXPECT_MAY_OVERFLOW(Wrap.signedAddMayOverflow(One)); 1495 EXPECT_MAY_OVERFLOW(One.signedAddMayOverflow(Full)); 1496 EXPECT_MAY_OVERFLOW(One.signedAddMayOverflow(Wrap)); 1497 1498 ConstantRange A(APInt(16, 0x7d00), APInt(16, 0x7e00)); 1499 ConstantRange B1(APInt(16, 0x0100), APInt(16, 0x0201)); 1500 ConstantRange B2(APInt(16, 0x0100), APInt(16, 0x0202)); 1501 EXPECT_NEVER_OVERFLOWS(A.signedAddMayOverflow(B1)); 1502 EXPECT_MAY_OVERFLOW(A.signedAddMayOverflow(B2)); 1503 ConstantRange B3(APInt(16, 0x8000), APInt(16, 0x0201)); 1504 ConstantRange B4(APInt(16, 0x8000), APInt(16, 0x0202)); 1505 EXPECT_NEVER_OVERFLOWS(A.signedAddMayOverflow(B3)); 1506 EXPECT_MAY_OVERFLOW(A.signedAddMayOverflow(B4)); 1507 ConstantRange B5(APInt(16, 0x0299), APInt(16, 0x0400)); 1508 ConstantRange B6(APInt(16, 0x0300), APInt(16, 0x0400)); 1509 EXPECT_MAY_OVERFLOW(A.signedAddMayOverflow(B5)); 1510 EXPECT_ALWAYS_OVERFLOWS(A.signedAddMayOverflow(B6)); 1511 1512 ConstantRange C(APInt(16, 0x8200), APInt(16, 0x8300)); 1513 ConstantRange D1(APInt(16, 0xfe00), APInt(16, 0xff00)); 1514 ConstantRange D2(APInt(16, 0xfd99), APInt(16, 0xff00)); 1515 EXPECT_NEVER_OVERFLOWS(C.signedAddMayOverflow(D1)); 1516 EXPECT_MAY_OVERFLOW(C.signedAddMayOverflow(D2)); 1517 ConstantRange D3(APInt(16, 0xfe00), APInt(16, 0x8000)); 1518 ConstantRange D4(APInt(16, 0xfd99), APInt(16, 0x8000)); 1519 EXPECT_NEVER_OVERFLOWS(C.signedAddMayOverflow(D3)); 1520 EXPECT_MAY_OVERFLOW(C.signedAddMayOverflow(D4)); 1521 ConstantRange D5(APInt(16, 0xfc00), APInt(16, 0xfd02)); 1522 ConstantRange D6(APInt(16, 0xfc00), APInt(16, 0xfd01)); 1523 EXPECT_MAY_OVERFLOW(C.signedAddMayOverflow(D5)); 1524 EXPECT_ALWAYS_OVERFLOWS(C.signedAddMayOverflow(D6)); 1525 1526 ConstantRange E(APInt(16, 0xff00), APInt(16, 0x0100)); 1527 EXPECT_NEVER_OVERFLOWS(E.signedAddMayOverflow(E)); 1528 ConstantRange F(APInt(16, 0xf000), APInt(16, 0x7000)); 1529 EXPECT_MAY_OVERFLOW(F.signedAddMayOverflow(F)); 1530 } 1531 1532 TEST_F(ConstantRangeTest, SignedSubOverflow) { 1533 // Ill-defined - may overflow is a conservative result. 1534 EXPECT_MAY_OVERFLOW(Some.signedSubMayOverflow(Empty)); 1535 EXPECT_MAY_OVERFLOW(Empty.signedSubMayOverflow(Some)); 1536 1537 // Never overflow despite one full/wrap set. 1538 ConstantRange Zero(APInt::getNullValue(16)); 1539 EXPECT_NEVER_OVERFLOWS(Full.signedSubMayOverflow(Zero)); 1540 EXPECT_NEVER_OVERFLOWS(Wrap.signedSubMayOverflow(Zero)); 1541 1542 // But usually full/wrap always may overflow. 1543 EXPECT_MAY_OVERFLOW(Full.signedSubMayOverflow(One)); 1544 EXPECT_MAY_OVERFLOW(Wrap.signedSubMayOverflow(One)); 1545 EXPECT_MAY_OVERFLOW(One.signedSubMayOverflow(Full)); 1546 EXPECT_MAY_OVERFLOW(One.signedSubMayOverflow(Wrap)); 1547 1548 ConstantRange A(APInt(16, 0x7d00), APInt(16, 0x7e00)); 1549 ConstantRange B1(APInt(16, 0xfe00), APInt(16, 0xff00)); 1550 ConstantRange B2(APInt(16, 0xfd99), APInt(16, 0xff00)); 1551 EXPECT_NEVER_OVERFLOWS(A.signedSubMayOverflow(B1)); 1552 EXPECT_MAY_OVERFLOW(A.signedSubMayOverflow(B2)); 1553 ConstantRange B3(APInt(16, 0xfc00), APInt(16, 0xfd02)); 1554 ConstantRange B4(APInt(16, 0xfc00), APInt(16, 0xfd01)); 1555 EXPECT_MAY_OVERFLOW(A.signedSubMayOverflow(B3)); 1556 EXPECT_ALWAYS_OVERFLOWS(A.signedSubMayOverflow(B4)); 1557 1558 ConstantRange C(APInt(16, 0x8200), APInt(16, 0x8300)); 1559 ConstantRange D1(APInt(16, 0x0100), APInt(16, 0x0201)); 1560 ConstantRange D2(APInt(16, 0x0100), APInt(16, 0x0202)); 1561 EXPECT_NEVER_OVERFLOWS(C.signedSubMayOverflow(D1)); 1562 EXPECT_MAY_OVERFLOW(C.signedSubMayOverflow(D2)); 1563 ConstantRange D3(APInt(16, 0x0299), APInt(16, 0x0400)); 1564 ConstantRange D4(APInt(16, 0x0300), APInt(16, 0x0400)); 1565 EXPECT_MAY_OVERFLOW(C.signedSubMayOverflow(D3)); 1566 EXPECT_ALWAYS_OVERFLOWS(C.signedSubMayOverflow(D4)); 1567 1568 ConstantRange E(APInt(16, 0xff00), APInt(16, 0x0100)); 1569 EXPECT_NEVER_OVERFLOWS(E.signedSubMayOverflow(E)); 1570 ConstantRange F(APInt(16, 0xf000), APInt(16, 0x7001)); 1571 EXPECT_MAY_OVERFLOW(F.signedSubMayOverflow(F)); 1572 } 1573 1574 template<typename Fn1, typename Fn2> 1575 static void TestOverflowExhaustive(Fn1 OverflowFn, Fn2 MayOverflowFn) { 1576 // Constant range overflow checks are tested exhaustively on 4-bit numbers. 1577 unsigned Bits = 4; 1578 EnumerateTwoConstantRanges(Bits, [=](const ConstantRange &CR1, 1579 const ConstantRange &CR2) { 1580 // Loop over all N1 in CR1 and N2 in CR2 and check whether any of the 1581 // operations have overflow / have no overflow. 1582 bool RangeHasOverflow = false; 1583 bool RangeHasNoOverflow = false; 1584 ForeachNumInConstantRange(CR1, [&](const APInt &N1) { 1585 ForeachNumInConstantRange(CR2, [&](const APInt &N2) { 1586 if (OverflowFn(N1, N2)) 1587 RangeHasOverflow = true; 1588 else 1589 RangeHasNoOverflow = true; 1590 }); 1591 }); 1592 1593 ConstantRange::OverflowResult OR = MayOverflowFn(CR1, CR2); 1594 switch (OR) { 1595 case ConstantRange::OverflowResult::AlwaysOverflows: 1596 EXPECT_TRUE(RangeHasOverflow); 1597 EXPECT_FALSE(RangeHasNoOverflow); 1598 break; 1599 case ConstantRange::OverflowResult::NeverOverflows: 1600 EXPECT_FALSE(RangeHasOverflow); 1601 EXPECT_TRUE(RangeHasNoOverflow); 1602 break; 1603 case ConstantRange::OverflowResult::MayOverflow: 1604 // We return MayOverflow for empty sets as a conservative result, 1605 // but of course neither the RangeHasOverflow nor the 1606 // RangeHasNoOverflow flags will be set. 1607 if (CR1.isEmptySet() || CR2.isEmptySet()) 1608 break; 1609 1610 EXPECT_TRUE(RangeHasOverflow); 1611 EXPECT_TRUE(RangeHasNoOverflow); 1612 break; 1613 } 1614 }); 1615 } 1616 1617 TEST_F(ConstantRangeTest, UnsignedAddOverflowExhaustive) { 1618 TestOverflowExhaustive( 1619 [](const APInt &N1, const APInt &N2) { 1620 bool Overflow; 1621 (void) N1.uadd_ov(N2, Overflow); 1622 return Overflow; 1623 }, 1624 [](const ConstantRange &CR1, const ConstantRange &CR2) { 1625 return CR1.unsignedAddMayOverflow(CR2); 1626 }); 1627 } 1628 1629 TEST_F(ConstantRangeTest, UnsignedSubOverflowExhaustive) { 1630 TestOverflowExhaustive( 1631 [](const APInt &N1, const APInt &N2) { 1632 bool Overflow; 1633 (void) N1.usub_ov(N2, Overflow); 1634 return Overflow; 1635 }, 1636 [](const ConstantRange &CR1, const ConstantRange &CR2) { 1637 return CR1.unsignedSubMayOverflow(CR2); 1638 }); 1639 } 1640 1641 TEST_F(ConstantRangeTest, UnsignedMulOverflowExhaustive) { 1642 TestOverflowExhaustive( 1643 [](const APInt &N1, const APInt &N2) { 1644 bool Overflow; 1645 (void) N1.umul_ov(N2, Overflow); 1646 return Overflow; 1647 }, 1648 [](const ConstantRange &CR1, const ConstantRange &CR2) { 1649 return CR1.unsignedMulMayOverflow(CR2); 1650 }); 1651 } 1652 1653 TEST_F(ConstantRangeTest, SignedAddOverflowExhaustive) { 1654 TestOverflowExhaustive( 1655 [](const APInt &N1, const APInt &N2) { 1656 bool Overflow; 1657 (void) N1.sadd_ov(N2, Overflow); 1658 return Overflow; 1659 }, 1660 [](const ConstantRange &CR1, const ConstantRange &CR2) { 1661 return CR1.signedAddMayOverflow(CR2); 1662 }); 1663 } 1664 1665 TEST_F(ConstantRangeTest, SignedSubOverflowExhaustive) { 1666 TestOverflowExhaustive( 1667 [](const APInt &N1, const APInt &N2) { 1668 bool Overflow; 1669 (void) N1.ssub_ov(N2, Overflow); 1670 return Overflow; 1671 }, 1672 [](const ConstantRange &CR1, const ConstantRange &CR2) { 1673 return CR1.signedSubMayOverflow(CR2); 1674 }); 1675 } 1676 1677 TEST_F(ConstantRangeTest, FromKnownBits) { 1678 KnownBits Unknown(16); 1679 EXPECT_EQ(Full, ConstantRange::fromKnownBits(Unknown, /*signed*/false)); 1680 EXPECT_EQ(Full, ConstantRange::fromKnownBits(Unknown, /*signed*/true)); 1681 1682 // .10..01. -> unsigned 01000010 (66) to 11011011 (219) 1683 // -> signed 11000010 (194) to 01011011 (91) 1684 KnownBits Known(8); 1685 Known.Zero = 36; 1686 Known.One = 66; 1687 ConstantRange Unsigned(APInt(8, 66), APInt(8, 219 + 1)); 1688 ConstantRange Signed(APInt(8, 194), APInt(8, 91 + 1)); 1689 EXPECT_EQ(Unsigned, ConstantRange::fromKnownBits(Known, /*signed*/false)); 1690 EXPECT_EQ(Signed, ConstantRange::fromKnownBits(Known, /*signed*/true)); 1691 1692 // 1.10.10. -> 10100100 (164) to 11101101 (237) 1693 Known.Zero = 18; 1694 Known.One = 164; 1695 ConstantRange CR1(APInt(8, 164), APInt(8, 237 + 1)); 1696 EXPECT_EQ(CR1, ConstantRange::fromKnownBits(Known, /*signed*/false)); 1697 EXPECT_EQ(CR1, ConstantRange::fromKnownBits(Known, /*signed*/true)); 1698 1699 // 01.0.1.0 -> 01000100 (68) to 01101110 (110) 1700 Known.Zero = 145; 1701 Known.One = 68; 1702 ConstantRange CR2(APInt(8, 68), APInt(8, 110 + 1)); 1703 EXPECT_EQ(CR2, ConstantRange::fromKnownBits(Known, /*signed*/false)); 1704 EXPECT_EQ(CR2, ConstantRange::fromKnownBits(Known, /*signed*/true)); 1705 } 1706 1707 TEST_F(ConstantRangeTest, FromKnownBitsExhaustive) { 1708 unsigned Bits = 4; 1709 unsigned Max = 1 << Bits; 1710 KnownBits Known(Bits); 1711 for (unsigned Zero = 0; Zero < Max; ++Zero) { 1712 for (unsigned One = 0; One < Max; ++One) { 1713 Known.Zero = Zero; 1714 Known.One = One; 1715 if (Known.hasConflict() || Known.isUnknown()) 1716 continue; 1717 1718 APInt MinUnsigned = APInt::getMaxValue(Bits); 1719 APInt MaxUnsigned = APInt::getMinValue(Bits); 1720 APInt MinSigned = APInt::getSignedMaxValue(Bits); 1721 APInt MaxSigned = APInt::getSignedMinValue(Bits); 1722 for (unsigned N = 0; N < Max; ++N) { 1723 APInt Num(Bits, N); 1724 if ((Num & Known.Zero) != 0 || (~Num & Known.One) != 0) 1725 continue; 1726 1727 if (Num.ult(MinUnsigned)) MinUnsigned = Num; 1728 if (Num.ugt(MaxUnsigned)) MaxUnsigned = Num; 1729 if (Num.slt(MinSigned)) MinSigned = Num; 1730 if (Num.sgt(MaxSigned)) MaxSigned = Num; 1731 } 1732 1733 ConstantRange UnsignedCR(MinUnsigned, MaxUnsigned + 1); 1734 ConstantRange SignedCR(MinSigned, MaxSigned + 1); 1735 EXPECT_EQ(UnsignedCR, ConstantRange::fromKnownBits(Known, false)); 1736 EXPECT_EQ(SignedCR, ConstantRange::fromKnownBits(Known, true)); 1737 } 1738 } 1739 } 1740 1741 TEST_F(ConstantRangeTest, Negative) { 1742 // All elements in an empty set (of which there are none) are both negative 1743 // and non-negative. Empty & full sets checked explicitly for clarity, but 1744 // they are also covered by the exhaustive test below. 1745 EXPECT_TRUE(Empty.isAllNegative()); 1746 EXPECT_TRUE(Empty.isAllNonNegative()); 1747 EXPECT_FALSE(Full.isAllNegative()); 1748 EXPECT_FALSE(Full.isAllNonNegative()); 1749 1750 unsigned Bits = 4; 1751 EnumerateConstantRanges(Bits, [](const ConstantRange &CR) { 1752 bool AllNegative = true; 1753 bool AllNonNegative = true; 1754 ForeachNumInConstantRange(CR, [&](const APInt &N) { 1755 if (!N.isNegative()) 1756 AllNegative = false; 1757 if (!N.isNonNegative()) 1758 AllNonNegative = false; 1759 }); 1760 assert((CR.isEmptySet() || !AllNegative || !AllNonNegative) && 1761 "Only empty set can be both all negative and all non-negative"); 1762 1763 EXPECT_EQ(AllNegative, CR.isAllNegative()); 1764 EXPECT_EQ(AllNonNegative, CR.isAllNonNegative()); 1765 }); 1766 } 1767 1768 TEST_F(ConstantRangeTest, UAddSat) { 1769 TestUnsignedBinOpExhaustive( 1770 [](const ConstantRange &CR1, const ConstantRange &CR2) { 1771 return CR1.uadd_sat(CR2); 1772 }, 1773 [](const APInt &N1, const APInt &N2) { 1774 return N1.uadd_sat(N2); 1775 }); 1776 } 1777 1778 TEST_F(ConstantRangeTest, USubSat) { 1779 TestUnsignedBinOpExhaustive( 1780 [](const ConstantRange &CR1, const ConstantRange &CR2) { 1781 return CR1.usub_sat(CR2); 1782 }, 1783 [](const APInt &N1, const APInt &N2) { 1784 return N1.usub_sat(N2); 1785 }); 1786 } 1787 1788 TEST_F(ConstantRangeTest, SAddSat) { 1789 TestSignedBinOpExhaustive( 1790 [](const ConstantRange &CR1, const ConstantRange &CR2) { 1791 return CR1.sadd_sat(CR2); 1792 }, 1793 [](const APInt &N1, const APInt &N2) { 1794 return N1.sadd_sat(N2); 1795 }); 1796 } 1797 1798 TEST_F(ConstantRangeTest, SSubSat) { 1799 TestSignedBinOpExhaustive( 1800 [](const ConstantRange &CR1, const ConstantRange &CR2) { 1801 return CR1.ssub_sat(CR2); 1802 }, 1803 [](const APInt &N1, const APInt &N2) { 1804 return N1.ssub_sat(N2); 1805 }); 1806 } 1807 1808 TEST_F(ConstantRangeTest, Abs) { 1809 unsigned Bits = 4; 1810 EnumerateConstantRanges(Bits, [&](const ConstantRange &CR) { 1811 // We're working with unsigned integers here, because it makes the signed 1812 // min case non-wrapping. 1813 APInt Min = APInt::getMaxValue(Bits); 1814 APInt Max = APInt::getMinValue(Bits); 1815 ForeachNumInConstantRange(CR, [&](const APInt &N) { 1816 APInt AbsN = N.abs(); 1817 if (AbsN.ult(Min)) 1818 Min = AbsN; 1819 if (AbsN.ugt(Max)) 1820 Max = AbsN; 1821 }); 1822 1823 ConstantRange AbsCR = CR.abs(); 1824 if (Min.ugt(Max)) { 1825 EXPECT_TRUE(AbsCR.isEmptySet()); 1826 return; 1827 } 1828 1829 ConstantRange Exact = ConstantRange::getNonEmpty(Min, Max + 1); 1830 EXPECT_EQ(Exact, AbsCR); 1831 }); 1832 } 1833 1834 } // anonymous namespace 1835