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