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, 525 APIntOps::avgFloorS); 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 } 534 535 TEST(KnownBitsTest, UnaryExhaustive) { 536 testUnaryOpExhaustive( 537 "abs", [](const KnownBits &Known) { return Known.abs(); }, 538 [](const APInt &N) { return N.abs(); }); 539 540 testUnaryOpExhaustive( 541 "abs(true)", [](const KnownBits &Known) { return Known.abs(true); }, 542 [](const APInt &N) -> std::optional<APInt> { 543 if (N.isMinSignedValue()) 544 return std::nullopt; 545 return N.abs(); 546 }); 547 548 testUnaryOpExhaustive( 549 "blsi", [](const KnownBits &Known) { return Known.blsi(); }, 550 [](const APInt &N) { return N & -N; }); 551 testUnaryOpExhaustive( 552 "blsmsk", [](const KnownBits &Known) { return Known.blsmsk(); }, 553 [](const APInt &N) { return N ^ (N - 1); }); 554 555 testUnaryOpExhaustive( 556 "mul self", 557 [](const KnownBits &Known) { 558 return KnownBits::mul(Known, Known, /*SelfMultiply=*/true); 559 }, 560 [](const APInt &N) { return N * N; }, /*CheckOptimality=*/false); 561 } 562 563 TEST(KnownBitsTest, WideShifts) { 564 unsigned BitWidth = 128; 565 KnownBits Unknown(BitWidth); 566 KnownBits AllOnes = KnownBits::makeConstant(APInt::getAllOnes(BitWidth)); 567 568 KnownBits ShlResult(BitWidth); 569 ShlResult.makeNegative(); 570 EXPECT_EQ(KnownBits::shl(AllOnes, Unknown), ShlResult); 571 KnownBits LShrResult(BitWidth); 572 LShrResult.One.setBit(0); 573 EXPECT_EQ(KnownBits::lshr(AllOnes, Unknown), LShrResult); 574 EXPECT_EQ(KnownBits::ashr(AllOnes, Unknown), AllOnes); 575 } 576 577 TEST(KnownBitsTest, ICmpExhaustive) { 578 unsigned Bits = 4; 579 ForeachKnownBits(Bits, [&](const KnownBits &Known1) { 580 ForeachKnownBits(Bits, [&](const KnownBits &Known2) { 581 bool AllEQ = true, NoneEQ = true; 582 bool AllNE = true, NoneNE = true; 583 bool AllUGT = true, NoneUGT = true; 584 bool AllUGE = true, NoneUGE = true; 585 bool AllULT = true, NoneULT = true; 586 bool AllULE = true, NoneULE = true; 587 bool AllSGT = true, NoneSGT = true; 588 bool AllSGE = true, NoneSGE = true; 589 bool AllSLT = true, NoneSLT = true; 590 bool AllSLE = true, NoneSLE = true; 591 592 ForeachNumInKnownBits(Known1, [&](const APInt &N1) { 593 ForeachNumInKnownBits(Known2, [&](const APInt &N2) { 594 AllEQ &= N1.eq(N2); 595 AllNE &= N1.ne(N2); 596 AllUGT &= N1.ugt(N2); 597 AllUGE &= N1.uge(N2); 598 AllULT &= N1.ult(N2); 599 AllULE &= N1.ule(N2); 600 AllSGT &= N1.sgt(N2); 601 AllSGE &= N1.sge(N2); 602 AllSLT &= N1.slt(N2); 603 AllSLE &= N1.sle(N2); 604 NoneEQ &= !N1.eq(N2); 605 NoneNE &= !N1.ne(N2); 606 NoneUGT &= !N1.ugt(N2); 607 NoneUGE &= !N1.uge(N2); 608 NoneULT &= !N1.ult(N2); 609 NoneULE &= !N1.ule(N2); 610 NoneSGT &= !N1.sgt(N2); 611 NoneSGE &= !N1.sge(N2); 612 NoneSLT &= !N1.slt(N2); 613 NoneSLE &= !N1.sle(N2); 614 }); 615 }); 616 617 std::optional<bool> KnownEQ = KnownBits::eq(Known1, Known2); 618 std::optional<bool> KnownNE = KnownBits::ne(Known1, Known2); 619 std::optional<bool> KnownUGT = KnownBits::ugt(Known1, Known2); 620 std::optional<bool> KnownUGE = KnownBits::uge(Known1, Known2); 621 std::optional<bool> KnownULT = KnownBits::ult(Known1, Known2); 622 std::optional<bool> KnownULE = KnownBits::ule(Known1, Known2); 623 std::optional<bool> KnownSGT = KnownBits::sgt(Known1, Known2); 624 std::optional<bool> KnownSGE = KnownBits::sge(Known1, Known2); 625 std::optional<bool> KnownSLT = KnownBits::slt(Known1, Known2); 626 std::optional<bool> KnownSLE = KnownBits::sle(Known1, Known2); 627 628 if (Known1.hasConflict() || Known2.hasConflict()) 629 return; 630 631 EXPECT_EQ(AllEQ || NoneEQ, KnownEQ.has_value()); 632 EXPECT_EQ(AllNE || NoneNE, KnownNE.has_value()); 633 EXPECT_EQ(AllUGT || NoneUGT, KnownUGT.has_value()); 634 EXPECT_EQ(AllUGE || NoneUGE, KnownUGE.has_value()); 635 EXPECT_EQ(AllULT || NoneULT, KnownULT.has_value()); 636 EXPECT_EQ(AllULE || NoneULE, KnownULE.has_value()); 637 EXPECT_EQ(AllSGT || NoneSGT, KnownSGT.has_value()); 638 EXPECT_EQ(AllSGE || NoneSGE, KnownSGE.has_value()); 639 EXPECT_EQ(AllSLT || NoneSLT, KnownSLT.has_value()); 640 EXPECT_EQ(AllSLE || NoneSLE, KnownSLE.has_value()); 641 642 EXPECT_EQ(AllEQ, KnownEQ.has_value() && *KnownEQ); 643 EXPECT_EQ(AllNE, KnownNE.has_value() && *KnownNE); 644 EXPECT_EQ(AllUGT, KnownUGT.has_value() && *KnownUGT); 645 EXPECT_EQ(AllUGE, KnownUGE.has_value() && *KnownUGE); 646 EXPECT_EQ(AllULT, KnownULT.has_value() && *KnownULT); 647 EXPECT_EQ(AllULE, KnownULE.has_value() && *KnownULE); 648 EXPECT_EQ(AllSGT, KnownSGT.has_value() && *KnownSGT); 649 EXPECT_EQ(AllSGE, KnownSGE.has_value() && *KnownSGE); 650 EXPECT_EQ(AllSLT, KnownSLT.has_value() && *KnownSLT); 651 EXPECT_EQ(AllSLE, KnownSLE.has_value() && *KnownSLE); 652 653 EXPECT_EQ(NoneEQ, KnownEQ.has_value() && !*KnownEQ); 654 EXPECT_EQ(NoneNE, KnownNE.has_value() && !*KnownNE); 655 EXPECT_EQ(NoneUGT, KnownUGT.has_value() && !*KnownUGT); 656 EXPECT_EQ(NoneUGE, KnownUGE.has_value() && !*KnownUGE); 657 EXPECT_EQ(NoneULT, KnownULT.has_value() && !*KnownULT); 658 EXPECT_EQ(NoneULE, KnownULE.has_value() && !*KnownULE); 659 EXPECT_EQ(NoneSGT, KnownSGT.has_value() && !*KnownSGT); 660 EXPECT_EQ(NoneSGE, KnownSGE.has_value() && !*KnownSGE); 661 EXPECT_EQ(NoneSLT, KnownSLT.has_value() && !*KnownSLT); 662 EXPECT_EQ(NoneSLE, KnownSLE.has_value() && !*KnownSLE); 663 }); 664 }); 665 } 666 667 TEST(KnownBitsTest, GetMinMaxVal) { 668 unsigned Bits = 4; 669 ForeachKnownBits(Bits, [&](const KnownBits &Known) { 670 APInt Min = APInt::getMaxValue(Bits); 671 APInt Max = APInt::getMinValue(Bits); 672 ForeachNumInKnownBits(Known, [&](const APInt &N) { 673 Min = APIntOps::umin(Min, N); 674 Max = APIntOps::umax(Max, N); 675 }); 676 if (!Known.hasConflict()) { 677 EXPECT_EQ(Min, Known.getMinValue()); 678 EXPECT_EQ(Max, Known.getMaxValue()); 679 } 680 }); 681 } 682 683 TEST(KnownBitsTest, GetSignedMinMaxVal) { 684 unsigned Bits = 4; 685 ForeachKnownBits(Bits, [&](const KnownBits &Known) { 686 APInt Min = APInt::getSignedMaxValue(Bits); 687 APInt Max = APInt::getSignedMinValue(Bits); 688 ForeachNumInKnownBits(Known, [&](const APInt &N) { 689 Min = APIntOps::smin(Min, N); 690 Max = APIntOps::smax(Max, N); 691 }); 692 if (!Known.hasConflict()) { 693 EXPECT_EQ(Min, Known.getSignedMinValue()); 694 EXPECT_EQ(Max, Known.getSignedMaxValue()); 695 } 696 }); 697 } 698 699 TEST(KnownBitsTest, CountMaxActiveBits) { 700 unsigned Bits = 4; 701 ForeachKnownBits(Bits, [&](const KnownBits &Known) { 702 unsigned Expected = 0; 703 ForeachNumInKnownBits(Known, [&](const APInt &N) { 704 Expected = std::max(Expected, N.getActiveBits()); 705 }); 706 if (!Known.hasConflict()) { 707 EXPECT_EQ(Expected, Known.countMaxActiveBits()); 708 } 709 }); 710 } 711 712 TEST(KnownBitsTest, CountMaxSignificantBits) { 713 unsigned Bits = 4; 714 ForeachKnownBits(Bits, [&](const KnownBits &Known) { 715 unsigned Expected = 0; 716 ForeachNumInKnownBits(Known, [&](const APInt &N) { 717 Expected = std::max(Expected, N.getSignificantBits()); 718 }); 719 if (!Known.hasConflict()) { 720 EXPECT_EQ(Expected, Known.countMaxSignificantBits()); 721 } 722 }); 723 } 724 725 TEST(KnownBitsTest, SExtOrTrunc) { 726 const unsigned NarrowerSize = 4; 727 const unsigned BaseSize = 6; 728 const unsigned WiderSize = 8; 729 APInt NegativeFitsNarrower(BaseSize, -4, /*isSigned=*/true); 730 APInt NegativeDoesntFitNarrower(BaseSize, -28, /*isSigned=*/true); 731 APInt PositiveFitsNarrower(BaseSize, 14); 732 APInt PositiveDoesntFitNarrower(BaseSize, 36); 733 auto InitKnownBits = [&](KnownBits &Res, const APInt &Input) { 734 Res = KnownBits(Input.getBitWidth()); 735 Res.One = Input; 736 Res.Zero = ~Input; 737 }; 738 739 for (unsigned Size : {NarrowerSize, BaseSize, WiderSize}) { 740 for (const APInt &Input : 741 {NegativeFitsNarrower, NegativeDoesntFitNarrower, PositiveFitsNarrower, 742 PositiveDoesntFitNarrower}) { 743 KnownBits Test; 744 InitKnownBits(Test, Input); 745 KnownBits Baseline; 746 InitKnownBits(Baseline, Input.sextOrTrunc(Size)); 747 Test = Test.sextOrTrunc(Size); 748 EXPECT_EQ(Test, Baseline); 749 } 750 } 751 } 752 753 TEST(KnownBitsTest, SExtInReg) { 754 unsigned Bits = 4; 755 for (unsigned FromBits = 1; FromBits <= Bits; ++FromBits) { 756 ForeachKnownBits(Bits, [&](const KnownBits &Known) { 757 APInt CommonOne = APInt::getAllOnes(Bits); 758 APInt CommonZero = APInt::getAllOnes(Bits); 759 unsigned ExtBits = Bits - FromBits; 760 ForeachNumInKnownBits(Known, [&](const APInt &N) { 761 APInt Ext = N << ExtBits; 762 Ext.ashrInPlace(ExtBits); 763 CommonOne &= Ext; 764 CommonZero &= ~Ext; 765 }); 766 KnownBits KnownSExtInReg = Known.sextInReg(FromBits); 767 if (!Known.hasConflict()) { 768 EXPECT_EQ(CommonOne, KnownSExtInReg.One); 769 EXPECT_EQ(CommonZero, KnownSExtInReg.Zero); 770 } 771 }); 772 } 773 } 774 775 TEST(KnownBitsTest, CommonBitsSet) { 776 unsigned Bits = 4; 777 ForeachKnownBits(Bits, [&](const KnownBits &Known1) { 778 ForeachKnownBits(Bits, [&](const KnownBits &Known2) { 779 bool HasCommonBitsSet = false; 780 ForeachNumInKnownBits(Known1, [&](const APInt &N1) { 781 ForeachNumInKnownBits(Known2, [&](const APInt &N2) { 782 HasCommonBitsSet |= N1.intersects(N2); 783 }); 784 }); 785 if (!Known1.hasConflict() && !Known2.hasConflict()) { 786 EXPECT_EQ(!HasCommonBitsSet, 787 KnownBits::haveNoCommonBitsSet(Known1, Known2)); 788 } 789 }); 790 }); 791 } 792 793 TEST(KnownBitsTest, ConcatBits) { 794 unsigned Bits = 4; 795 for (unsigned LoBits = 1; LoBits < Bits; ++LoBits) { 796 unsigned HiBits = Bits - LoBits; 797 ForeachKnownBits(LoBits, [&](const KnownBits &KnownLo) { 798 ForeachKnownBits(HiBits, [&](const KnownBits &KnownHi) { 799 KnownBits KnownAll = KnownHi.concat(KnownLo); 800 801 EXPECT_EQ(KnownLo.countMinPopulation() + KnownHi.countMinPopulation(), 802 KnownAll.countMinPopulation()); 803 EXPECT_EQ(KnownLo.countMaxPopulation() + KnownHi.countMaxPopulation(), 804 KnownAll.countMaxPopulation()); 805 806 KnownBits ExtractLo = KnownAll.extractBits(LoBits, 0); 807 KnownBits ExtractHi = KnownAll.extractBits(HiBits, LoBits); 808 809 EXPECT_EQ(KnownLo.One.getZExtValue(), ExtractLo.One.getZExtValue()); 810 EXPECT_EQ(KnownHi.One.getZExtValue(), ExtractHi.One.getZExtValue()); 811 EXPECT_EQ(KnownLo.Zero.getZExtValue(), ExtractLo.Zero.getZExtValue()); 812 EXPECT_EQ(KnownHi.Zero.getZExtValue(), ExtractHi.Zero.getZExtValue()); 813 }); 814 }); 815 } 816 } 817 818 } // end anonymous namespace 819