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( 304 "add", 305 [](const KnownBits &Known1, const KnownBits &Known2) { 306 return KnownBits::add(Known1, Known2); 307 }, 308 [](const APInt &N1, const APInt &N2) { return N1 + N2; }); 309 testBinaryOpExhaustive( 310 "sub", 311 [](const KnownBits &Known1, const KnownBits &Known2) { 312 return KnownBits::sub(Known1, Known2); 313 }, 314 [](const APInt &N1, const APInt &N2) { return N1 - N2; }); 315 testBinaryOpExhaustive("umax", KnownBits::umax, APIntOps::umax); 316 testBinaryOpExhaustive("umin", KnownBits::umin, APIntOps::umin); 317 testBinaryOpExhaustive("smax", KnownBits::smax, APIntOps::smax); 318 testBinaryOpExhaustive("smin", KnownBits::smin, APIntOps::smin); 319 testBinaryOpExhaustive("abdu", KnownBits::abdu, APIntOps::abdu); 320 testBinaryOpExhaustive("abds", KnownBits::abds, APIntOps::abds); 321 testBinaryOpExhaustive( 322 "udiv", 323 [](const KnownBits &Known1, const KnownBits &Known2) { 324 return KnownBits::udiv(Known1, Known2); 325 }, 326 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 327 if (N2.isZero()) 328 return std::nullopt; 329 return N1.udiv(N2); 330 }, 331 /*CheckOptimality=*/false); 332 testBinaryOpExhaustive( 333 "udiv exact", 334 [](const KnownBits &Known1, const KnownBits &Known2) { 335 return KnownBits::udiv(Known1, Known2, /*Exact=*/true); 336 }, 337 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 338 if (N2.isZero() || !N1.urem(N2).isZero()) 339 return std::nullopt; 340 return N1.udiv(N2); 341 }, 342 /*CheckOptimality=*/false); 343 testBinaryOpExhaustive( 344 "sdiv", 345 [](const KnownBits &Known1, const KnownBits &Known2) { 346 return KnownBits::sdiv(Known1, Known2); 347 }, 348 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 349 if (N2.isZero() || (N1.isMinSignedValue() && N2.isAllOnes())) 350 return std::nullopt; 351 return N1.sdiv(N2); 352 }, 353 /*CheckOptimality=*/false); 354 testBinaryOpExhaustive( 355 "sdiv exact", 356 [](const KnownBits &Known1, const KnownBits &Known2) { 357 return KnownBits::sdiv(Known1, Known2, /*Exact=*/true); 358 }, 359 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 360 if (N2.isZero() || (N1.isMinSignedValue() && N2.isAllOnes()) || 361 !N1.srem(N2).isZero()) 362 return std::nullopt; 363 return N1.sdiv(N2); 364 }, 365 /*CheckOptimality=*/false); 366 testBinaryOpExhaustive( 367 "urem", KnownBits::urem, 368 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 369 if (N2.isZero()) 370 return std::nullopt; 371 return N1.urem(N2); 372 }, 373 /*CheckOptimality=*/false); 374 testBinaryOpExhaustive( 375 "srem", KnownBits::srem, 376 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 377 if (N2.isZero()) 378 return std::nullopt; 379 return N1.srem(N2); 380 }, 381 /*CheckOptimality=*/false); 382 testBinaryOpExhaustive( 383 "sadd_sat", KnownBits::sadd_sat, 384 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 385 return N1.sadd_sat(N2); 386 }, 387 /*CheckOptimality=*/false); 388 testBinaryOpExhaustive( 389 "uadd_sat", KnownBits::uadd_sat, 390 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 391 return N1.uadd_sat(N2); 392 }, 393 /*CheckOptimality=*/false); 394 testBinaryOpExhaustive( 395 "ssub_sat", KnownBits::ssub_sat, 396 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 397 return N1.ssub_sat(N2); 398 }, 399 /*CheckOptimality=*/false); 400 testBinaryOpExhaustive( 401 "usub_sat", KnownBits::usub_sat, 402 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 403 return N1.usub_sat(N2); 404 }, 405 /*CheckOptimality=*/false); 406 testBinaryOpExhaustive( 407 "shl", 408 [](const KnownBits &Known1, const KnownBits &Known2) { 409 return KnownBits::shl(Known1, Known2); 410 }, 411 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 412 if (N2.uge(N2.getBitWidth())) 413 return std::nullopt; 414 return N1.shl(N2); 415 }, 416 /*CheckOptimality=*/true, /*RefinePoisonToZero=*/true); 417 testBinaryOpExhaustive( 418 "ushl_ov", 419 [](const KnownBits &Known1, const KnownBits &Known2) { 420 return KnownBits::shl(Known1, Known2, /*NUW=*/true); 421 }, 422 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 423 bool Overflow; 424 APInt Res = N1.ushl_ov(N2, Overflow); 425 if (Overflow) 426 return std::nullopt; 427 return Res; 428 }, 429 /*CheckOptimality=*/true, /*RefinePoisonToZero=*/true); 430 testBinaryOpExhaustive( 431 "shl nsw", 432 [](const KnownBits &Known1, const KnownBits &Known2) { 433 return KnownBits::shl(Known1, Known2, /*NUW=*/false, /*NSW=*/true); 434 }, 435 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 436 bool Overflow; 437 APInt Res = N1.sshl_ov(N2, Overflow); 438 if (Overflow) 439 return std::nullopt; 440 return Res; 441 }, 442 /*CheckOptimality=*/true, /*RefinePoisonToZero=*/true); 443 testBinaryOpExhaustive( 444 "shl nuw", 445 [](const KnownBits &Known1, const KnownBits &Known2) { 446 return KnownBits::shl(Known1, Known2, /*NUW=*/true, /*NSW=*/true); 447 }, 448 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 449 bool OverflowUnsigned, OverflowSigned; 450 APInt Res = N1.ushl_ov(N2, OverflowUnsigned); 451 (void)N1.sshl_ov(N2, OverflowSigned); 452 if (OverflowUnsigned || OverflowSigned) 453 return std::nullopt; 454 return Res; 455 }, 456 /*CheckOptimality=*/true, /*RefinePoisonToZero=*/true); 457 458 testBinaryOpExhaustive( 459 "lshr", 460 [](const KnownBits &Known1, const KnownBits &Known2) { 461 return KnownBits::lshr(Known1, Known2); 462 }, 463 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 464 if (N2.uge(N2.getBitWidth())) 465 return std::nullopt; 466 return N1.lshr(N2); 467 }, 468 /*CheckOptimality=*/true, /*RefinePoisonToZero=*/true); 469 testBinaryOpExhaustive( 470 "lshr exact", 471 [](const KnownBits &Known1, const KnownBits &Known2) { 472 return KnownBits::lshr(Known1, Known2, /*ShAmtNonZero=*/false, 473 /*Exact=*/true); 474 }, 475 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 476 if (N2.uge(N2.getBitWidth())) 477 return std::nullopt; 478 if (!N1.extractBits(N2.getZExtValue(), 0).isZero()) 479 return std::nullopt; 480 return N1.lshr(N2); 481 }, 482 /*CheckOptimality=*/true, /*RefinePoisonToZero=*/true); 483 testBinaryOpExhaustive( 484 "ashr", 485 [](const KnownBits &Known1, const KnownBits &Known2) { 486 return KnownBits::ashr(Known1, Known2); 487 }, 488 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 489 if (N2.uge(N2.getBitWidth())) 490 return std::nullopt; 491 return N1.ashr(N2); 492 }, 493 /*CheckOptimality=*/true, /*RefinePoisonToZero=*/true); 494 testBinaryOpExhaustive( 495 "ashr exact", 496 [](const KnownBits &Known1, const KnownBits &Known2) { 497 return KnownBits::ashr(Known1, Known2, /*ShAmtNonZero=*/false, 498 /*Exact=*/true); 499 }, 500 [](const APInt &N1, const APInt &N2) -> std::optional<APInt> { 501 if (N2.uge(N2.getBitWidth())) 502 return std::nullopt; 503 if (!N1.extractBits(N2.getZExtValue(), 0).isZero()) 504 return std::nullopt; 505 return N1.ashr(N2); 506 }, 507 /*CheckOptimality=*/true, /*RefinePoisonToZero=*/true); 508 testBinaryOpExhaustive( 509 "mul", 510 [](const KnownBits &Known1, const KnownBits &Known2) { 511 return KnownBits::mul(Known1, Known2); 512 }, 513 [](const APInt &N1, const APInt &N2) { return N1 * N2; }, 514 /*CheckOptimality=*/false); 515 testBinaryOpExhaustive( 516 "mulhs", KnownBits::mulhs, 517 [](const APInt &N1, const APInt &N2) { return APIntOps::mulhs(N1, N2); }, 518 /*CheckOptimality=*/false); 519 testBinaryOpExhaustive( 520 "mulhu", KnownBits::mulhu, 521 [](const APInt &N1, const APInt &N2) { return APIntOps::mulhu(N1, N2); }, 522 /*CheckOptimality=*/false); 523 524 testBinaryOpExhaustive("avgFloorS", KnownBits::avgFloorS, APIntOps::avgFloorS, 525 /*CheckOptimality=*/false); 526 527 testBinaryOpExhaustive("avgFloorU", KnownBits::avgFloorU, 528 APIntOps::avgFloorU); 529 530 testBinaryOpExhaustive("avgCeilU", KnownBits::avgCeilU, APIntOps::avgCeilU); 531 532 testBinaryOpExhaustive("avgCeilS", KnownBits::avgCeilS, APIntOps::avgCeilS, 533 /*CheckOptimality=*/false); 534 } 535 536 TEST(KnownBitsTest, UnaryExhaustive) { 537 testUnaryOpExhaustive( 538 "abs", [](const KnownBits &Known) { return Known.abs(); }, 539 [](const APInt &N) { return N.abs(); }); 540 541 testUnaryOpExhaustive( 542 "abs(true)", [](const KnownBits &Known) { return Known.abs(true); }, 543 [](const APInt &N) -> std::optional<APInt> { 544 if (N.isMinSignedValue()) 545 return std::nullopt; 546 return N.abs(); 547 }); 548 549 testUnaryOpExhaustive( 550 "blsi", [](const KnownBits &Known) { return Known.blsi(); }, 551 [](const APInt &N) { return N & -N; }); 552 testUnaryOpExhaustive( 553 "blsmsk", [](const KnownBits &Known) { return Known.blsmsk(); }, 554 [](const APInt &N) { return N ^ (N - 1); }); 555 556 testUnaryOpExhaustive( 557 "mul self", 558 [](const KnownBits &Known) { 559 return KnownBits::mul(Known, Known, /*SelfMultiply=*/true); 560 }, 561 [](const APInt &N) { return N * N; }, /*CheckOptimality=*/false); 562 } 563 564 TEST(KnownBitsTest, WideShifts) { 565 unsigned BitWidth = 128; 566 KnownBits Unknown(BitWidth); 567 KnownBits AllOnes = KnownBits::makeConstant(APInt::getAllOnes(BitWidth)); 568 569 KnownBits ShlResult(BitWidth); 570 ShlResult.makeNegative(); 571 EXPECT_EQ(KnownBits::shl(AllOnes, Unknown), ShlResult); 572 KnownBits LShrResult(BitWidth); 573 LShrResult.One.setBit(0); 574 EXPECT_EQ(KnownBits::lshr(AllOnes, Unknown), LShrResult); 575 EXPECT_EQ(KnownBits::ashr(AllOnes, Unknown), AllOnes); 576 } 577 578 TEST(KnownBitsTest, ICmpExhaustive) { 579 unsigned Bits = 4; 580 ForeachKnownBits(Bits, [&](const KnownBits &Known1) { 581 ForeachKnownBits(Bits, [&](const KnownBits &Known2) { 582 bool AllEQ = true, NoneEQ = true; 583 bool AllNE = true, NoneNE = true; 584 bool AllUGT = true, NoneUGT = true; 585 bool AllUGE = true, NoneUGE = true; 586 bool AllULT = true, NoneULT = true; 587 bool AllULE = true, NoneULE = true; 588 bool AllSGT = true, NoneSGT = true; 589 bool AllSGE = true, NoneSGE = true; 590 bool AllSLT = true, NoneSLT = true; 591 bool AllSLE = true, NoneSLE = true; 592 593 ForeachNumInKnownBits(Known1, [&](const APInt &N1) { 594 ForeachNumInKnownBits(Known2, [&](const APInt &N2) { 595 AllEQ &= N1.eq(N2); 596 AllNE &= N1.ne(N2); 597 AllUGT &= N1.ugt(N2); 598 AllUGE &= N1.uge(N2); 599 AllULT &= N1.ult(N2); 600 AllULE &= N1.ule(N2); 601 AllSGT &= N1.sgt(N2); 602 AllSGE &= N1.sge(N2); 603 AllSLT &= N1.slt(N2); 604 AllSLE &= N1.sle(N2); 605 NoneEQ &= !N1.eq(N2); 606 NoneNE &= !N1.ne(N2); 607 NoneUGT &= !N1.ugt(N2); 608 NoneUGE &= !N1.uge(N2); 609 NoneULT &= !N1.ult(N2); 610 NoneULE &= !N1.ule(N2); 611 NoneSGT &= !N1.sgt(N2); 612 NoneSGE &= !N1.sge(N2); 613 NoneSLT &= !N1.slt(N2); 614 NoneSLE &= !N1.sle(N2); 615 }); 616 }); 617 618 std::optional<bool> KnownEQ = KnownBits::eq(Known1, Known2); 619 std::optional<bool> KnownNE = KnownBits::ne(Known1, Known2); 620 std::optional<bool> KnownUGT = KnownBits::ugt(Known1, Known2); 621 std::optional<bool> KnownUGE = KnownBits::uge(Known1, Known2); 622 std::optional<bool> KnownULT = KnownBits::ult(Known1, Known2); 623 std::optional<bool> KnownULE = KnownBits::ule(Known1, Known2); 624 std::optional<bool> KnownSGT = KnownBits::sgt(Known1, Known2); 625 std::optional<bool> KnownSGE = KnownBits::sge(Known1, Known2); 626 std::optional<bool> KnownSLT = KnownBits::slt(Known1, Known2); 627 std::optional<bool> KnownSLE = KnownBits::sle(Known1, Known2); 628 629 if (Known1.hasConflict() || Known2.hasConflict()) 630 return; 631 632 EXPECT_EQ(AllEQ || NoneEQ, KnownEQ.has_value()); 633 EXPECT_EQ(AllNE || NoneNE, KnownNE.has_value()); 634 EXPECT_EQ(AllUGT || NoneUGT, KnownUGT.has_value()); 635 EXPECT_EQ(AllUGE || NoneUGE, KnownUGE.has_value()); 636 EXPECT_EQ(AllULT || NoneULT, KnownULT.has_value()); 637 EXPECT_EQ(AllULE || NoneULE, KnownULE.has_value()); 638 EXPECT_EQ(AllSGT || NoneSGT, KnownSGT.has_value()); 639 EXPECT_EQ(AllSGE || NoneSGE, KnownSGE.has_value()); 640 EXPECT_EQ(AllSLT || NoneSLT, KnownSLT.has_value()); 641 EXPECT_EQ(AllSLE || NoneSLE, KnownSLE.has_value()); 642 643 EXPECT_EQ(AllEQ, KnownEQ.has_value() && *KnownEQ); 644 EXPECT_EQ(AllNE, KnownNE.has_value() && *KnownNE); 645 EXPECT_EQ(AllUGT, KnownUGT.has_value() && *KnownUGT); 646 EXPECT_EQ(AllUGE, KnownUGE.has_value() && *KnownUGE); 647 EXPECT_EQ(AllULT, KnownULT.has_value() && *KnownULT); 648 EXPECT_EQ(AllULE, KnownULE.has_value() && *KnownULE); 649 EXPECT_EQ(AllSGT, KnownSGT.has_value() && *KnownSGT); 650 EXPECT_EQ(AllSGE, KnownSGE.has_value() && *KnownSGE); 651 EXPECT_EQ(AllSLT, KnownSLT.has_value() && *KnownSLT); 652 EXPECT_EQ(AllSLE, KnownSLE.has_value() && *KnownSLE); 653 654 EXPECT_EQ(NoneEQ, KnownEQ.has_value() && !*KnownEQ); 655 EXPECT_EQ(NoneNE, KnownNE.has_value() && !*KnownNE); 656 EXPECT_EQ(NoneUGT, KnownUGT.has_value() && !*KnownUGT); 657 EXPECT_EQ(NoneUGE, KnownUGE.has_value() && !*KnownUGE); 658 EXPECT_EQ(NoneULT, KnownULT.has_value() && !*KnownULT); 659 EXPECT_EQ(NoneULE, KnownULE.has_value() && !*KnownULE); 660 EXPECT_EQ(NoneSGT, KnownSGT.has_value() && !*KnownSGT); 661 EXPECT_EQ(NoneSGE, KnownSGE.has_value() && !*KnownSGE); 662 EXPECT_EQ(NoneSLT, KnownSLT.has_value() && !*KnownSLT); 663 EXPECT_EQ(NoneSLE, KnownSLE.has_value() && !*KnownSLE); 664 }); 665 }); 666 } 667 668 TEST(KnownBitsTest, GetMinMaxVal) { 669 unsigned Bits = 4; 670 ForeachKnownBits(Bits, [&](const KnownBits &Known) { 671 APInt Min = APInt::getMaxValue(Bits); 672 APInt Max = APInt::getMinValue(Bits); 673 ForeachNumInKnownBits(Known, [&](const APInt &N) { 674 Min = APIntOps::umin(Min, N); 675 Max = APIntOps::umax(Max, N); 676 }); 677 if (!Known.hasConflict()) { 678 EXPECT_EQ(Min, Known.getMinValue()); 679 EXPECT_EQ(Max, Known.getMaxValue()); 680 } 681 }); 682 } 683 684 TEST(KnownBitsTest, GetSignedMinMaxVal) { 685 unsigned Bits = 4; 686 ForeachKnownBits(Bits, [&](const KnownBits &Known) { 687 APInt Min = APInt::getSignedMaxValue(Bits); 688 APInt Max = APInt::getSignedMinValue(Bits); 689 ForeachNumInKnownBits(Known, [&](const APInt &N) { 690 Min = APIntOps::smin(Min, N); 691 Max = APIntOps::smax(Max, N); 692 }); 693 if (!Known.hasConflict()) { 694 EXPECT_EQ(Min, Known.getSignedMinValue()); 695 EXPECT_EQ(Max, Known.getSignedMaxValue()); 696 } 697 }); 698 } 699 700 TEST(KnownBitsTest, CountMaxActiveBits) { 701 unsigned Bits = 4; 702 ForeachKnownBits(Bits, [&](const KnownBits &Known) { 703 unsigned Expected = 0; 704 ForeachNumInKnownBits(Known, [&](const APInt &N) { 705 Expected = std::max(Expected, N.getActiveBits()); 706 }); 707 if (!Known.hasConflict()) { 708 EXPECT_EQ(Expected, Known.countMaxActiveBits()); 709 } 710 }); 711 } 712 713 TEST(KnownBitsTest, CountMaxSignificantBits) { 714 unsigned Bits = 4; 715 ForeachKnownBits(Bits, [&](const KnownBits &Known) { 716 unsigned Expected = 0; 717 ForeachNumInKnownBits(Known, [&](const APInt &N) { 718 Expected = std::max(Expected, N.getSignificantBits()); 719 }); 720 if (!Known.hasConflict()) { 721 EXPECT_EQ(Expected, Known.countMaxSignificantBits()); 722 } 723 }); 724 } 725 726 TEST(KnownBitsTest, SExtOrTrunc) { 727 const unsigned NarrowerSize = 4; 728 const unsigned BaseSize = 6; 729 const unsigned WiderSize = 8; 730 APInt NegativeFitsNarrower(BaseSize, -4, /*isSigned=*/true); 731 APInt NegativeDoesntFitNarrower(BaseSize, -28, /*isSigned=*/true); 732 APInt PositiveFitsNarrower(BaseSize, 14); 733 APInt PositiveDoesntFitNarrower(BaseSize, 36); 734 auto InitKnownBits = [&](KnownBits &Res, const APInt &Input) { 735 Res = KnownBits(Input.getBitWidth()); 736 Res.One = Input; 737 Res.Zero = ~Input; 738 }; 739 740 for (unsigned Size : {NarrowerSize, BaseSize, WiderSize}) { 741 for (const APInt &Input : 742 {NegativeFitsNarrower, NegativeDoesntFitNarrower, PositiveFitsNarrower, 743 PositiveDoesntFitNarrower}) { 744 KnownBits Test; 745 InitKnownBits(Test, Input); 746 KnownBits Baseline; 747 InitKnownBits(Baseline, Input.sextOrTrunc(Size)); 748 Test = Test.sextOrTrunc(Size); 749 EXPECT_EQ(Test, Baseline); 750 } 751 } 752 } 753 754 TEST(KnownBitsTest, SExtInReg) { 755 unsigned Bits = 4; 756 for (unsigned FromBits = 1; FromBits <= Bits; ++FromBits) { 757 ForeachKnownBits(Bits, [&](const KnownBits &Known) { 758 APInt CommonOne = APInt::getAllOnes(Bits); 759 APInt CommonZero = APInt::getAllOnes(Bits); 760 unsigned ExtBits = Bits - FromBits; 761 ForeachNumInKnownBits(Known, [&](const APInt &N) { 762 APInt Ext = N << ExtBits; 763 Ext.ashrInPlace(ExtBits); 764 CommonOne &= Ext; 765 CommonZero &= ~Ext; 766 }); 767 KnownBits KnownSExtInReg = Known.sextInReg(FromBits); 768 if (!Known.hasConflict()) { 769 EXPECT_EQ(CommonOne, KnownSExtInReg.One); 770 EXPECT_EQ(CommonZero, KnownSExtInReg.Zero); 771 } 772 }); 773 } 774 } 775 776 TEST(KnownBitsTest, CommonBitsSet) { 777 unsigned Bits = 4; 778 ForeachKnownBits(Bits, [&](const KnownBits &Known1) { 779 ForeachKnownBits(Bits, [&](const KnownBits &Known2) { 780 bool HasCommonBitsSet = false; 781 ForeachNumInKnownBits(Known1, [&](const APInt &N1) { 782 ForeachNumInKnownBits(Known2, [&](const APInt &N2) { 783 HasCommonBitsSet |= N1.intersects(N2); 784 }); 785 }); 786 if (!Known1.hasConflict() && !Known2.hasConflict()) { 787 EXPECT_EQ(!HasCommonBitsSet, 788 KnownBits::haveNoCommonBitsSet(Known1, Known2)); 789 } 790 }); 791 }); 792 } 793 794 TEST(KnownBitsTest, ConcatBits) { 795 unsigned Bits = 4; 796 for (unsigned LoBits = 1; LoBits < Bits; ++LoBits) { 797 unsigned HiBits = Bits - LoBits; 798 ForeachKnownBits(LoBits, [&](const KnownBits &KnownLo) { 799 ForeachKnownBits(HiBits, [&](const KnownBits &KnownHi) { 800 KnownBits KnownAll = KnownHi.concat(KnownLo); 801 802 EXPECT_EQ(KnownLo.countMinPopulation() + KnownHi.countMinPopulation(), 803 KnownAll.countMinPopulation()); 804 EXPECT_EQ(KnownLo.countMaxPopulation() + KnownHi.countMaxPopulation(), 805 KnownAll.countMaxPopulation()); 806 807 KnownBits ExtractLo = KnownAll.extractBits(LoBits, 0); 808 KnownBits ExtractHi = KnownAll.extractBits(HiBits, LoBits); 809 810 EXPECT_EQ(KnownLo.One.getZExtValue(), ExtractLo.One.getZExtValue()); 811 EXPECT_EQ(KnownHi.One.getZExtValue(), ExtractHi.One.getZExtValue()); 812 EXPECT_EQ(KnownLo.Zero.getZExtValue(), ExtractLo.Zero.getZExtValue()); 813 EXPECT_EQ(KnownHi.Zero.getZExtValue(), ExtractHi.Zero.getZExtValue()); 814 }); 815 }); 816 } 817 } 818 819 } // end anonymous namespace 820