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