1 //===- llvm/unittest/Support/KnownBitsTest.cpp - KnownBits 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 // This file implements unit tests for KnownBits functions. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "llvm/Support/KnownBits.h" 14 #include "KnownBitsTest.h" 15 #include "llvm/ADT/ArrayRef.h" 16 #include "llvm/ADT/StringRef.h" 17 #include "llvm/ADT/Twine.h" 18 #include "gtest/gtest.h" 19 20 using namespace llvm; 21 22 using UnaryBitsFn = llvm::function_ref<KnownBits(const KnownBits &)>; 23 using UnaryIntFn = llvm::function_ref<std::optional<APInt>(const APInt &)>; 24 25 using BinaryBitsFn = 26 llvm::function_ref<KnownBits(const KnownBits &, const KnownBits &)>; 27 using BinaryIntFn = 28 llvm::function_ref<std::optional<APInt>(const APInt &, const APInt &)>; 29 30 static testing::AssertionResult checkResult(Twine Name, const KnownBits &Exact, 31 const KnownBits &Computed, 32 ArrayRef<KnownBits> Inputs, 33 bool CheckOptimality) { 34 if (CheckOptimality) { 35 // We generally don't want to return conflicting known bits, even if it is 36 // legal for always poison results. 37 if (Exact.hasConflict() || Computed == Exact) 38 return testing::AssertionSuccess(); 39 } else { 40 if (Computed.Zero.isSubsetOf(Exact.Zero) && 41 Computed.One.isSubsetOf(Exact.One)) 42 return testing::AssertionSuccess(); 43 } 44 45 testing::AssertionResult Result = testing::AssertionFailure(); 46 Result << Name << ": "; 47 Result << "Inputs = "; 48 for (const KnownBits &Input : Inputs) 49 Result << Input << ", "; 50 Result << "Computed = " << Computed << ", Exact = " << Exact; 51 return Result; 52 } 53 54 static void testUnaryOpExhaustive(StringRef Name, UnaryBitsFn BitsFn, 55 UnaryIntFn IntFn, 56 bool CheckOptimality = true) { 57 for (unsigned Bits : {1, 4}) { 58 ForeachKnownBits(Bits, [&](const KnownBits &Known) { 59 KnownBits Computed = BitsFn(Known); 60 KnownBits Exact(Bits); 61 Exact.Zero.setAllBits(); 62 Exact.One.setAllBits(); 63 64 ForeachNumInKnownBits(Known, [&](const APInt &N) { 65 if (std::optional<APInt> Res = IntFn(N)) { 66 Exact.One &= *Res; 67 Exact.Zero &= ~*Res; 68 } 69 }); 70 71 if (!Exact.hasConflict()) { 72 EXPECT_TRUE(checkResult(Name, Exact, Computed, Known, CheckOptimality)); 73 } 74 }); 75 } 76 } 77 78 static void testBinaryOpExhaustive(StringRef Name, BinaryBitsFn BitsFn, 79 BinaryIntFn IntFn, 80 bool CheckOptimality = true, 81 bool RefinePoisonToZero = false) { 82 for (unsigned Bits : {1, 4}) { 83 ForeachKnownBits(Bits, [&](const KnownBits &Known1) { 84 ForeachKnownBits(Bits, [&](const KnownBits &Known2) { 85 KnownBits Computed = BitsFn(Known1, Known2); 86 KnownBits Exact(Bits); 87 Exact.Zero.setAllBits(); 88 Exact.One.setAllBits(); 89 90 ForeachNumInKnownBits(Known1, [&](const APInt &N1) { 91 ForeachNumInKnownBits(Known2, [&](const APInt &N2) { 92 if (std::optional<APInt> Res = IntFn(N1, N2)) { 93 Exact.One &= *Res; 94 Exact.Zero &= ~*Res; 95 } 96 }); 97 }); 98 99 if (!Exact.hasConflict()) { 100 EXPECT_TRUE(checkResult(Name, Exact, Computed, {Known1, Known2}, 101 CheckOptimality)); 102 } 103 // In some cases we choose to return zero if the result is always 104 // poison. 105 if (RefinePoisonToZero && Exact.hasConflict() && 106 !Known1.hasConflict() && !Known2.hasConflict()) { 107 EXPECT_TRUE(Computed.isZero()); 108 } 109 }); 110 }); 111 } 112 } 113 114 namespace { 115 116 TEST(KnownBitsTest, AddCarryExhaustive) { 117 unsigned Bits = 4; 118 ForeachKnownBits(Bits, [&](const KnownBits &Known1) { 119 ForeachKnownBits(Bits, [&](const KnownBits &Known2) { 120 ForeachKnownBits(1, [&](const KnownBits &KnownCarry) { 121 // Explicitly compute known bits of the addition by trying all 122 // possibilities. 123 KnownBits Exact(Bits); 124 Exact.Zero.setAllBits(); 125 Exact.One.setAllBits(); 126 ForeachNumInKnownBits(Known1, [&](const APInt &N1) { 127 ForeachNumInKnownBits(Known2, [&](const APInt &N2) { 128 ForeachNumInKnownBits(KnownCarry, [&](const APInt &Carry) { 129 APInt Add = N1 + N2; 130 if (Carry.getBoolValue()) 131 ++Add; 132 133 Exact.One &= Add; 134 Exact.Zero &= ~Add; 135 }); 136 }); 137 }); 138 139 KnownBits Computed = 140 KnownBits::computeForAddCarry(Known1, Known2, KnownCarry); 141 if (!Exact.hasConflict()) { 142 EXPECT_EQ(Exact, Computed); 143 } 144 }); 145 }); 146 }); 147 } 148 149 static void TestAddSubExhaustive(bool IsAdd) { 150 Twine Name = IsAdd ? "add" : "sub"; 151 unsigned Bits = 4; 152 ForeachKnownBits(Bits, [&](const KnownBits &Known1) { 153 ForeachKnownBits(Bits, [&](const KnownBits &Known2) { 154 KnownBits Exact(Bits), ExactNSW(Bits), ExactNUW(Bits), 155 ExactNSWAndNUW(Bits); 156 Exact.Zero.setAllBits(); 157 Exact.One.setAllBits(); 158 ExactNSW.Zero.setAllBits(); 159 ExactNSW.One.setAllBits(); 160 ExactNUW.Zero.setAllBits(); 161 ExactNUW.One.setAllBits(); 162 ExactNSWAndNUW.Zero.setAllBits(); 163 ExactNSWAndNUW.One.setAllBits(); 164 165 ForeachNumInKnownBits(Known1, [&](const APInt &N1) { 166 ForeachNumInKnownBits(Known2, [&](const APInt &N2) { 167 bool SignedOverflow; 168 bool UnsignedOverflow; 169 APInt Res; 170 if (IsAdd) { 171 Res = N1.uadd_ov(N2, UnsignedOverflow); 172 Res = N1.sadd_ov(N2, SignedOverflow); 173 } else { 174 Res = N1.usub_ov(N2, UnsignedOverflow); 175 Res = N1.ssub_ov(N2, SignedOverflow); 176 } 177 178 Exact.One &= Res; 179 Exact.Zero &= ~Res; 180 181 if (!SignedOverflow) { 182 ExactNSW.One &= Res; 183 ExactNSW.Zero &= ~Res; 184 } 185 186 if (!UnsignedOverflow) { 187 ExactNUW.One &= Res; 188 ExactNUW.Zero &= ~Res; 189 } 190 191 if (!UnsignedOverflow && !SignedOverflow) { 192 ExactNSWAndNUW.One &= Res; 193 ExactNSWAndNUW.Zero &= ~Res; 194 } 195 }); 196 }); 197 198 KnownBits Computed = KnownBits::computeForAddSub( 199 IsAdd, /*NSW=*/false, /*NUW=*/false, Known1, Known2); 200 EXPECT_TRUE(checkResult(Name, Exact, Computed, {Known1, Known2}, 201 /*CheckOptimality=*/true)); 202 203 KnownBits ComputedNSW = KnownBits::computeForAddSub( 204 IsAdd, /*NSW=*/true, /*NUW=*/false, Known1, Known2); 205 EXPECT_TRUE(checkResult(Name + " nsw", ExactNSW, ComputedNSW, 206 {Known1, Known2}, 207 /*CheckOptimality=*/true)); 208 209 KnownBits ComputedNUW = KnownBits::computeForAddSub( 210 IsAdd, /*NSW=*/false, /*NUW=*/true, Known1, Known2); 211 EXPECT_TRUE(checkResult(Name + " nuw", ExactNUW, ComputedNUW, 212 {Known1, Known2}, 213 /*CheckOptimality=*/true)); 214 215 KnownBits ComputedNSWAndNUW = KnownBits::computeForAddSub( 216 IsAdd, /*NSW=*/true, /*NUW=*/true, Known1, Known2); 217 EXPECT_TRUE(checkResult(Name + " nsw nuw", ExactNSWAndNUW, 218 ComputedNSWAndNUW, {Known1, Known2}, 219 /*CheckOptimality=*/true)); 220 }); 221 }); 222 } 223 224 TEST(KnownBitsTest, AddSubExhaustive) { 225 TestAddSubExhaustive(true); 226 TestAddSubExhaustive(false); 227 } 228 229 TEST(KnownBitsTest, SubBorrowExhaustive) { 230 unsigned Bits = 4; 231 ForeachKnownBits(Bits, [&](const KnownBits &Known1) { 232 ForeachKnownBits(Bits, [&](const KnownBits &Known2) { 233 ForeachKnownBits(1, [&](const KnownBits &KnownBorrow) { 234 // Explicitly compute known bits of the subtraction by trying all 235 // possibilities. 236 KnownBits Exact(Bits); 237 Exact.Zero.setAllBits(); 238 Exact.One.setAllBits(); 239 ForeachNumInKnownBits(Known1, [&](const APInt &N1) { 240 ForeachNumInKnownBits(Known2, [&](const APInt &N2) { 241 ForeachNumInKnownBits(KnownBorrow, [&](const APInt &Borrow) { 242 APInt Sub = N1 - N2; 243 if (Borrow.getBoolValue()) 244 --Sub; 245 246 Exact.One &= Sub; 247 Exact.Zero &= ~Sub; 248 }); 249 }); 250 }); 251 252 KnownBits Computed = 253 KnownBits::computeForSubBorrow(Known1, Known2, KnownBorrow); 254 if (!Exact.hasConflict()) { 255 EXPECT_EQ(Exact, Computed); 256 } 257 }); 258 }); 259 }); 260 } 261 262 TEST(KnownBitsTest, SignBitUnknown) { 263 KnownBits Known(2); 264 EXPECT_TRUE(Known.isSignUnknown()); 265 Known.Zero.setBit(0); 266 EXPECT_TRUE(Known.isSignUnknown()); 267 Known.Zero.setBit(1); 268 EXPECT_FALSE(Known.isSignUnknown()); 269 Known.Zero.clearBit(0); 270 EXPECT_FALSE(Known.isSignUnknown()); 271 Known.Zero.clearBit(1); 272 EXPECT_TRUE(Known.isSignUnknown()); 273 274 Known.One.setBit(0); 275 EXPECT_TRUE(Known.isSignUnknown()); 276 Known.One.setBit(1); 277 EXPECT_FALSE(Known.isSignUnknown()); 278 Known.One.clearBit(0); 279 EXPECT_FALSE(Known.isSignUnknown()); 280 Known.One.clearBit(1); 281 EXPECT_TRUE(Known.isSignUnknown()); 282 } 283 284 TEST(KnownBitsTest, BinaryExhaustive) { 285 testBinaryOpExhaustive( 286 "and", 287 [](const KnownBits &Known1, const KnownBits &Known2) { 288 return Known1 & Known2; 289 }, 290 [](const APInt &N1, const APInt &N2) { return N1 & N2; }); 291 testBinaryOpExhaustive( 292 "or", 293 [](const KnownBits &Known1, const KnownBits &Known2) { 294 return Known1 | Known2; 295 }, 296 [](const APInt &N1, const APInt &N2) { return N1 | N2; }); 297 testBinaryOpExhaustive( 298 "xor", 299 [](const KnownBits &Known1, const KnownBits &Known2) { 300 return Known1 ^ Known2; 301 }, 302 [](const APInt &N1, const APInt &N2) { return N1 ^ N2; }); 303 testBinaryOpExhaustive("umax", KnownBits::umax, APIntOps::umax); 304 testBinaryOpExhaustive("umin", KnownBits::umin, APIntOps::umin); 305 testBinaryOpExhaustive("smax", KnownBits::smax, APIntOps::smax); 306 testBinaryOpExhaustive("smin", KnownBits::smin, APIntOps::smin); 307 testBinaryOpExhaustive("abdu", KnownBits::abdu, APIntOps::abdu); 308 testBinaryOpExhaustive("abds", KnownBits::abds, APIntOps::abds); 309 testBinaryOpExhaustive( 310 "udiv", 311 [](const KnownBits &Known1, const KnownBits &Known2) { 312 return KnownBits::udiv(Known1, Known2); 313 }, 314 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 315 if (N2.isZero()) 316 return std::nullopt; 317 return N1.udiv(N2); 318 }, 319 /*CheckOptimality=*/false); 320 testBinaryOpExhaustive( 321 "udiv exact", 322 [](const KnownBits &Known1, const KnownBits &Known2) { 323 return KnownBits::udiv(Known1, Known2, /*Exact=*/true); 324 }, 325 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 326 if (N2.isZero() || !N1.urem(N2).isZero()) 327 return std::nullopt; 328 return N1.udiv(N2); 329 }, 330 /*CheckOptimality=*/false); 331 testBinaryOpExhaustive( 332 "sdiv", 333 [](const KnownBits &Known1, const KnownBits &Known2) { 334 return KnownBits::sdiv(Known1, Known2); 335 }, 336 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 337 if (N2.isZero() || (N1.isMinSignedValue() && N2.isAllOnes())) 338 return std::nullopt; 339 return N1.sdiv(N2); 340 }, 341 /*CheckOptimality=*/false); 342 testBinaryOpExhaustive( 343 "sdiv exact", 344 [](const KnownBits &Known1, const KnownBits &Known2) { 345 return KnownBits::sdiv(Known1, Known2, /*Exact=*/true); 346 }, 347 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 348 if (N2.isZero() || (N1.isMinSignedValue() && N2.isAllOnes()) || 349 !N1.srem(N2).isZero()) 350 return std::nullopt; 351 return N1.sdiv(N2); 352 }, 353 /*CheckOptimality=*/false); 354 testBinaryOpExhaustive( 355 "urem", KnownBits::urem, 356 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 357 if (N2.isZero()) 358 return std::nullopt; 359 return N1.urem(N2); 360 }, 361 /*CheckOptimality=*/false); 362 testBinaryOpExhaustive( 363 "srem", KnownBits::srem, 364 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 365 if (N2.isZero()) 366 return std::nullopt; 367 return N1.srem(N2); 368 }, 369 /*CheckOptimality=*/false); 370 testBinaryOpExhaustive( 371 "sadd_sat", KnownBits::sadd_sat, 372 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 373 return N1.sadd_sat(N2); 374 }, 375 /*CheckOptimality=*/false); 376 testBinaryOpExhaustive( 377 "uadd_sat", KnownBits::uadd_sat, 378 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 379 return N1.uadd_sat(N2); 380 }, 381 /*CheckOptimality=*/false); 382 testBinaryOpExhaustive( 383 "ssub_sat", KnownBits::ssub_sat, 384 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 385 return N1.ssub_sat(N2); 386 }, 387 /*CheckOptimality=*/false); 388 testBinaryOpExhaustive( 389 "usub_sat", KnownBits::usub_sat, 390 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 391 return N1.usub_sat(N2); 392 }, 393 /*CheckOptimality=*/false); 394 testBinaryOpExhaustive( 395 "shl", 396 [](const KnownBits &Known1, const KnownBits &Known2) { 397 return KnownBits::shl(Known1, Known2); 398 }, 399 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 400 if (N2.uge(N2.getBitWidth())) 401 return std::nullopt; 402 return N1.shl(N2); 403 }, 404 /*CheckOptimality=*/true, /*RefinePoisonToZero=*/true); 405 testBinaryOpExhaustive( 406 "ushl_ov", 407 [](const KnownBits &Known1, const KnownBits &Known2) { 408 return KnownBits::shl(Known1, Known2, /*NUW=*/true); 409 }, 410 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 411 bool Overflow; 412 APInt Res = N1.ushl_ov(N2, Overflow); 413 if (Overflow) 414 return std::nullopt; 415 return Res; 416 }, 417 /*CheckOptimality=*/true, /*RefinePoisonToZero=*/true); 418 testBinaryOpExhaustive( 419 "shl nsw", 420 [](const KnownBits &Known1, const KnownBits &Known2) { 421 return KnownBits::shl(Known1, Known2, /*NUW=*/false, /*NSW=*/true); 422 }, 423 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 424 bool Overflow; 425 APInt Res = N1.sshl_ov(N2, Overflow); 426 if (Overflow) 427 return std::nullopt; 428 return Res; 429 }, 430 /*CheckOptimality=*/true, /*RefinePoisonToZero=*/true); 431 testBinaryOpExhaustive( 432 "shl nuw", 433 [](const KnownBits &Known1, const KnownBits &Known2) { 434 return KnownBits::shl(Known1, Known2, /*NUW=*/true, /*NSW=*/true); 435 }, 436 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 437 bool OverflowUnsigned, OverflowSigned; 438 APInt Res = N1.ushl_ov(N2, OverflowUnsigned); 439 (void)N1.sshl_ov(N2, OverflowSigned); 440 if (OverflowUnsigned || OverflowSigned) 441 return std::nullopt; 442 return Res; 443 }, 444 /*CheckOptimality=*/true, /*RefinePoisonToZero=*/true); 445 446 testBinaryOpExhaustive( 447 "lshr", 448 [](const KnownBits &Known1, const KnownBits &Known2) { 449 return KnownBits::lshr(Known1, Known2); 450 }, 451 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 452 if (N2.uge(N2.getBitWidth())) 453 return std::nullopt; 454 return N1.lshr(N2); 455 }, 456 /*CheckOptimality=*/true, /*RefinePoisonToZero=*/true); 457 testBinaryOpExhaustive( 458 "lshr exact", 459 [](const KnownBits &Known1, const KnownBits &Known2) { 460 return KnownBits::lshr(Known1, Known2, /*ShAmtNonZero=*/false, 461 /*Exact=*/true); 462 }, 463 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 464 if (N2.uge(N2.getBitWidth())) 465 return std::nullopt; 466 if (!N1.extractBits(N2.getZExtValue(), 0).isZero()) 467 return std::nullopt; 468 return N1.lshr(N2); 469 }, 470 /*CheckOptimality=*/true, /*RefinePoisonToZero=*/true); 471 testBinaryOpExhaustive( 472 "ashr", 473 [](const KnownBits &Known1, const KnownBits &Known2) { 474 return KnownBits::ashr(Known1, Known2); 475 }, 476 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 477 if (N2.uge(N2.getBitWidth())) 478 return std::nullopt; 479 return N1.ashr(N2); 480 }, 481 /*CheckOptimality=*/true, /*RefinePoisonToZero=*/true); 482 testBinaryOpExhaustive( 483 "ashr exact", 484 [](const KnownBits &Known1, const KnownBits &Known2) { 485 return KnownBits::ashr(Known1, Known2, /*ShAmtNonZero=*/false, 486 /*Exact=*/true); 487 }, 488 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 489 if (N2.uge(N2.getBitWidth())) 490 return std::nullopt; 491 if (!N1.extractBits(N2.getZExtValue(), 0).isZero()) 492 return std::nullopt; 493 return N1.ashr(N2); 494 }, 495 /*CheckOptimality=*/true, /*RefinePoisonToZero=*/true); 496 testBinaryOpExhaustive( 497 "mul", 498 [](const KnownBits &Known1, const KnownBits &Known2) { 499 return KnownBits::mul(Known1, Known2); 500 }, 501 [](const APInt &N1, const APInt &N2) { return N1 * N2; }, 502 /*CheckOptimality=*/false); 503 testBinaryOpExhaustive( 504 "mulhs", KnownBits::mulhs, 505 [](const APInt &N1, const APInt &N2) { return APIntOps::mulhs(N1, N2); }, 506 /*CheckOptimality=*/false); 507 testBinaryOpExhaustive( 508 "mulhu", KnownBits::mulhu, 509 [](const APInt &N1, const APInt &N2) { return APIntOps::mulhu(N1, N2); }, 510 /*CheckOptimality=*/false); 511 512 testBinaryOpExhaustive("avgFloorS", KnownBits::avgFloorS, APIntOps::avgFloorS, 513 false); 514 515 testBinaryOpExhaustive("avgFloorU", KnownBits::avgFloorU, APIntOps::avgFloorU, 516 false); 517 518 testBinaryOpExhaustive("avgCeilU", KnownBits::avgCeilU, APIntOps::avgCeilU, 519 false); 520 521 testBinaryOpExhaustive("avgCeilS", KnownBits::avgCeilS, APIntOps::avgCeilS, 522 false); 523 } 524 525 TEST(KnownBitsTest, UnaryExhaustive) { 526 testUnaryOpExhaustive( 527 "abs", [](const KnownBits &Known) { return Known.abs(); }, 528 [](const APInt &N) { return N.abs(); }); 529 530 testUnaryOpExhaustive( 531 "abs(true)", [](const KnownBits &Known) { return Known.abs(true); }, 532 [](const APInt &N) -> std::optional<APInt> { 533 if (N.isMinSignedValue()) 534 return std::nullopt; 535 return N.abs(); 536 }); 537 538 testUnaryOpExhaustive( 539 "blsi", [](const KnownBits &Known) { return Known.blsi(); }, 540 [](const APInt &N) { return N & -N; }); 541 testUnaryOpExhaustive( 542 "blsmsk", [](const KnownBits &Known) { return Known.blsmsk(); }, 543 [](const APInt &N) { return N ^ (N - 1); }); 544 545 testUnaryOpExhaustive( 546 "mul self", 547 [](const KnownBits &Known) { 548 return KnownBits::mul(Known, Known, /*SelfMultiply=*/true); 549 }, 550 [](const APInt &N) { return N * N; }, /*CheckOptimality=*/false); 551 } 552 553 TEST(KnownBitsTest, WideShifts) { 554 unsigned BitWidth = 128; 555 KnownBits Unknown(BitWidth); 556 KnownBits AllOnes = KnownBits::makeConstant(APInt::getAllOnes(BitWidth)); 557 558 KnownBits ShlResult(BitWidth); 559 ShlResult.makeNegative(); 560 EXPECT_EQ(KnownBits::shl(AllOnes, Unknown), ShlResult); 561 KnownBits LShrResult(BitWidth); 562 LShrResult.One.setBit(0); 563 EXPECT_EQ(KnownBits::lshr(AllOnes, Unknown), LShrResult); 564 EXPECT_EQ(KnownBits::ashr(AllOnes, Unknown), AllOnes); 565 } 566 567 TEST(KnownBitsTest, ICmpExhaustive) { 568 unsigned Bits = 4; 569 ForeachKnownBits(Bits, [&](const KnownBits &Known1) { 570 ForeachKnownBits(Bits, [&](const KnownBits &Known2) { 571 bool AllEQ = true, NoneEQ = true; 572 bool AllNE = true, NoneNE = true; 573 bool AllUGT = true, NoneUGT = true; 574 bool AllUGE = true, NoneUGE = true; 575 bool AllULT = true, NoneULT = true; 576 bool AllULE = true, NoneULE = true; 577 bool AllSGT = true, NoneSGT = true; 578 bool AllSGE = true, NoneSGE = true; 579 bool AllSLT = true, NoneSLT = true; 580 bool AllSLE = true, NoneSLE = true; 581 582 ForeachNumInKnownBits(Known1, [&](const APInt &N1) { 583 ForeachNumInKnownBits(Known2, [&](const APInt &N2) { 584 AllEQ &= N1.eq(N2); 585 AllNE &= N1.ne(N2); 586 AllUGT &= N1.ugt(N2); 587 AllUGE &= N1.uge(N2); 588 AllULT &= N1.ult(N2); 589 AllULE &= N1.ule(N2); 590 AllSGT &= N1.sgt(N2); 591 AllSGE &= N1.sge(N2); 592 AllSLT &= N1.slt(N2); 593 AllSLE &= N1.sle(N2); 594 NoneEQ &= !N1.eq(N2); 595 NoneNE &= !N1.ne(N2); 596 NoneUGT &= !N1.ugt(N2); 597 NoneUGE &= !N1.uge(N2); 598 NoneULT &= !N1.ult(N2); 599 NoneULE &= !N1.ule(N2); 600 NoneSGT &= !N1.sgt(N2); 601 NoneSGE &= !N1.sge(N2); 602 NoneSLT &= !N1.slt(N2); 603 NoneSLE &= !N1.sle(N2); 604 }); 605 }); 606 607 std::optional<bool> KnownEQ = KnownBits::eq(Known1, Known2); 608 std::optional<bool> KnownNE = KnownBits::ne(Known1, Known2); 609 std::optional<bool> KnownUGT = KnownBits::ugt(Known1, Known2); 610 std::optional<bool> KnownUGE = KnownBits::uge(Known1, Known2); 611 std::optional<bool> KnownULT = KnownBits::ult(Known1, Known2); 612 std::optional<bool> KnownULE = KnownBits::ule(Known1, Known2); 613 std::optional<bool> KnownSGT = KnownBits::sgt(Known1, Known2); 614 std::optional<bool> KnownSGE = KnownBits::sge(Known1, Known2); 615 std::optional<bool> KnownSLT = KnownBits::slt(Known1, Known2); 616 std::optional<bool> KnownSLE = KnownBits::sle(Known1, Known2); 617 618 if (Known1.hasConflict() || Known2.hasConflict()) 619 return; 620 621 EXPECT_EQ(AllEQ || NoneEQ, KnownEQ.has_value()); 622 EXPECT_EQ(AllNE || NoneNE, KnownNE.has_value()); 623 EXPECT_EQ(AllUGT || NoneUGT, KnownUGT.has_value()); 624 EXPECT_EQ(AllUGE || NoneUGE, KnownUGE.has_value()); 625 EXPECT_EQ(AllULT || NoneULT, KnownULT.has_value()); 626 EXPECT_EQ(AllULE || NoneULE, KnownULE.has_value()); 627 EXPECT_EQ(AllSGT || NoneSGT, KnownSGT.has_value()); 628 EXPECT_EQ(AllSGE || NoneSGE, KnownSGE.has_value()); 629 EXPECT_EQ(AllSLT || NoneSLT, KnownSLT.has_value()); 630 EXPECT_EQ(AllSLE || NoneSLE, KnownSLE.has_value()); 631 632 EXPECT_EQ(AllEQ, KnownEQ.has_value() && *KnownEQ); 633 EXPECT_EQ(AllNE, KnownNE.has_value() && *KnownNE); 634 EXPECT_EQ(AllUGT, KnownUGT.has_value() && *KnownUGT); 635 EXPECT_EQ(AllUGE, KnownUGE.has_value() && *KnownUGE); 636 EXPECT_EQ(AllULT, KnownULT.has_value() && *KnownULT); 637 EXPECT_EQ(AllULE, KnownULE.has_value() && *KnownULE); 638 EXPECT_EQ(AllSGT, KnownSGT.has_value() && *KnownSGT); 639 EXPECT_EQ(AllSGE, KnownSGE.has_value() && *KnownSGE); 640 EXPECT_EQ(AllSLT, KnownSLT.has_value() && *KnownSLT); 641 EXPECT_EQ(AllSLE, KnownSLE.has_value() && *KnownSLE); 642 643 EXPECT_EQ(NoneEQ, KnownEQ.has_value() && !*KnownEQ); 644 EXPECT_EQ(NoneNE, KnownNE.has_value() && !*KnownNE); 645 EXPECT_EQ(NoneUGT, KnownUGT.has_value() && !*KnownUGT); 646 EXPECT_EQ(NoneUGE, KnownUGE.has_value() && !*KnownUGE); 647 EXPECT_EQ(NoneULT, KnownULT.has_value() && !*KnownULT); 648 EXPECT_EQ(NoneULE, KnownULE.has_value() && !*KnownULE); 649 EXPECT_EQ(NoneSGT, KnownSGT.has_value() && !*KnownSGT); 650 EXPECT_EQ(NoneSGE, KnownSGE.has_value() && !*KnownSGE); 651 EXPECT_EQ(NoneSLT, KnownSLT.has_value() && !*KnownSLT); 652 EXPECT_EQ(NoneSLE, KnownSLE.has_value() && !*KnownSLE); 653 }); 654 }); 655 } 656 657 TEST(KnownBitsTest, GetMinMaxVal) { 658 unsigned Bits = 4; 659 ForeachKnownBits(Bits, [&](const KnownBits &Known) { 660 APInt Min = APInt::getMaxValue(Bits); 661 APInt Max = APInt::getMinValue(Bits); 662 ForeachNumInKnownBits(Known, [&](const APInt &N) { 663 Min = APIntOps::umin(Min, N); 664 Max = APIntOps::umax(Max, N); 665 }); 666 if (!Known.hasConflict()) { 667 EXPECT_EQ(Min, Known.getMinValue()); 668 EXPECT_EQ(Max, Known.getMaxValue()); 669 } 670 }); 671 } 672 673 TEST(KnownBitsTest, GetSignedMinMaxVal) { 674 unsigned Bits = 4; 675 ForeachKnownBits(Bits, [&](const KnownBits &Known) { 676 APInt Min = APInt::getSignedMaxValue(Bits); 677 APInt Max = APInt::getSignedMinValue(Bits); 678 ForeachNumInKnownBits(Known, [&](const APInt &N) { 679 Min = APIntOps::smin(Min, N); 680 Max = APIntOps::smax(Max, N); 681 }); 682 if (!Known.hasConflict()) { 683 EXPECT_EQ(Min, Known.getSignedMinValue()); 684 EXPECT_EQ(Max, Known.getSignedMaxValue()); 685 } 686 }); 687 } 688 689 TEST(KnownBitsTest, CountMaxActiveBits) { 690 unsigned Bits = 4; 691 ForeachKnownBits(Bits, [&](const KnownBits &Known) { 692 unsigned Expected = 0; 693 ForeachNumInKnownBits(Known, [&](const APInt &N) { 694 Expected = std::max(Expected, N.getActiveBits()); 695 }); 696 if (!Known.hasConflict()) { 697 EXPECT_EQ(Expected, Known.countMaxActiveBits()); 698 } 699 }); 700 } 701 702 TEST(KnownBitsTest, CountMaxSignificantBits) { 703 unsigned Bits = 4; 704 ForeachKnownBits(Bits, [&](const KnownBits &Known) { 705 unsigned Expected = 0; 706 ForeachNumInKnownBits(Known, [&](const APInt &N) { 707 Expected = std::max(Expected, N.getSignificantBits()); 708 }); 709 if (!Known.hasConflict()) { 710 EXPECT_EQ(Expected, Known.countMaxSignificantBits()); 711 } 712 }); 713 } 714 715 TEST(KnownBitsTest, SExtOrTrunc) { 716 const unsigned NarrowerSize = 4; 717 const unsigned BaseSize = 6; 718 const unsigned WiderSize = 8; 719 APInt NegativeFitsNarrower(BaseSize, -4, /*isSigned=*/true); 720 APInt NegativeDoesntFitNarrower(BaseSize, -28, /*isSigned=*/true); 721 APInt PositiveFitsNarrower(BaseSize, 14); 722 APInt PositiveDoesntFitNarrower(BaseSize, 36); 723 auto InitKnownBits = [&](KnownBits &Res, const APInt &Input) { 724 Res = KnownBits(Input.getBitWidth()); 725 Res.One = Input; 726 Res.Zero = ~Input; 727 }; 728 729 for (unsigned Size : {NarrowerSize, BaseSize, WiderSize}) { 730 for (const APInt &Input : 731 {NegativeFitsNarrower, NegativeDoesntFitNarrower, PositiveFitsNarrower, 732 PositiveDoesntFitNarrower}) { 733 KnownBits Test; 734 InitKnownBits(Test, Input); 735 KnownBits Baseline; 736 InitKnownBits(Baseline, Input.sextOrTrunc(Size)); 737 Test = Test.sextOrTrunc(Size); 738 EXPECT_EQ(Test, Baseline); 739 } 740 } 741 } 742 743 TEST(KnownBitsTest, SExtInReg) { 744 unsigned Bits = 4; 745 for (unsigned FromBits = 1; FromBits <= Bits; ++FromBits) { 746 ForeachKnownBits(Bits, [&](const KnownBits &Known) { 747 APInt CommonOne = APInt::getAllOnes(Bits); 748 APInt CommonZero = APInt::getAllOnes(Bits); 749 unsigned ExtBits = Bits - FromBits; 750 ForeachNumInKnownBits(Known, [&](const APInt &N) { 751 APInt Ext = N << ExtBits; 752 Ext.ashrInPlace(ExtBits); 753 CommonOne &= Ext; 754 CommonZero &= ~Ext; 755 }); 756 KnownBits KnownSExtInReg = Known.sextInReg(FromBits); 757 if (!Known.hasConflict()) { 758 EXPECT_EQ(CommonOne, KnownSExtInReg.One); 759 EXPECT_EQ(CommonZero, KnownSExtInReg.Zero); 760 } 761 }); 762 } 763 } 764 765 TEST(KnownBitsTest, CommonBitsSet) { 766 unsigned Bits = 4; 767 ForeachKnownBits(Bits, [&](const KnownBits &Known1) { 768 ForeachKnownBits(Bits, [&](const KnownBits &Known2) { 769 bool HasCommonBitsSet = false; 770 ForeachNumInKnownBits(Known1, [&](const APInt &N1) { 771 ForeachNumInKnownBits(Known2, [&](const APInt &N2) { 772 HasCommonBitsSet |= N1.intersects(N2); 773 }); 774 }); 775 if (!Known1.hasConflict() && !Known2.hasConflict()) { 776 EXPECT_EQ(!HasCommonBitsSet, 777 KnownBits::haveNoCommonBitsSet(Known1, Known2)); 778 } 779 }); 780 }); 781 } 782 783 TEST(KnownBitsTest, ConcatBits) { 784 unsigned Bits = 4; 785 for (unsigned LoBits = 1; LoBits < Bits; ++LoBits) { 786 unsigned HiBits = Bits - LoBits; 787 ForeachKnownBits(LoBits, [&](const KnownBits &KnownLo) { 788 ForeachKnownBits(HiBits, [&](const KnownBits &KnownHi) { 789 KnownBits KnownAll = KnownHi.concat(KnownLo); 790 791 EXPECT_EQ(KnownLo.countMinPopulation() + KnownHi.countMinPopulation(), 792 KnownAll.countMinPopulation()); 793 EXPECT_EQ(KnownLo.countMaxPopulation() + KnownHi.countMaxPopulation(), 794 KnownAll.countMaxPopulation()); 795 796 KnownBits ExtractLo = KnownAll.extractBits(LoBits, 0); 797 KnownBits ExtractHi = KnownAll.extractBits(HiBits, LoBits); 798 799 EXPECT_EQ(KnownLo.One.getZExtValue(), ExtractLo.One.getZExtValue()); 800 EXPECT_EQ(KnownHi.One.getZExtValue(), ExtractHi.One.getZExtValue()); 801 EXPECT_EQ(KnownLo.Zero.getZExtValue(), ExtractLo.Zero.getZExtValue()); 802 EXPECT_EQ(KnownHi.Zero.getZExtValue(), ExtractHi.Zero.getZExtValue()); 803 }); 804 }); 805 } 806 } 807 808 } // end anonymous namespace 809