llvm/unittests/Support/KnownBitsTest.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-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