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