849 lines · cpp
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-exception6//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 20using namespace llvm;21 22using UnaryBitsFn = llvm::function_ref<KnownBits(const KnownBits &)>;23using UnaryIntFn = llvm::function_ref<std::optional<APInt>(const APInt &)>;24 25using BinaryBitsFn =26 llvm::function_ref<KnownBits(const KnownBits &, const KnownBits &)>;27using BinaryIntFn =28 llvm::function_ref<std::optional<APInt>(const APInt &, const APInt &)>;29 30static 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 is36 // 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 54static 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 78static 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 always104 // poison.105 if (RefinePoisonToZero && Exact.hasConflict() &&106 !Known1.hasConflict() && !Known2.hasConflict()) {107 EXPECT_TRUE(Computed.isZero());108 }109 });110 });111 }112}113 114namespace {115 116TEST(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 all122 // 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 149static 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 224TEST(KnownBitsTest, AddSubExhaustive) {225 TestAddSubExhaustive(true);226 TestAddSubExhaustive(false);227}228 229TEST(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 all235 // 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 262TEST(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 284TEST(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 531TEST(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 559TEST(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 573TEST(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 663TEST(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 679TEST(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 695TEST(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 708TEST(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 721TEST(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 749TEST(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 771TEST(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 789TEST(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 814TEST(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 order833 // 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 namespace849