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