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 "gtest/gtest.h"
  16
  17 using namespace llvm;
  18
  19 namespace {
  20
  21 TEST(KnownBitsTest, AddCarryExhaustive) {
  22   unsigned Bits = 4;
  23   ForeachKnownBits(Bits, [&](const KnownBits &Known1) {
  24     ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
  25       ForeachKnownBits(1, [&](const KnownBits &KnownCarry) {
  26         // Explicitly compute known bits of the addition by trying all
  27         // possibilities.
  28         KnownBits Known(Bits);
  29         Known.Zero.setAllBits();
  30         Known.One.setAllBits();
  31         ForeachNumInKnownBits(Known1, [&](const APInt &N1) {
  32           ForeachNumInKnownBits(Known2, [&](const APInt &N2) {
  33             ForeachNumInKnownBits(KnownCarry, [&](const APInt &Carry) {
  34               APInt Add = N1 + N2;
  35               if (Carry.getBoolValue())
  36                 ++Add;
  37
  38               Known.One &= Add;
  39               Known.Zero &= ~Add;
  40             });
  41           });
  42         });
  43
  44         KnownBits KnownComputed =
  45             KnownBits::computeForAddCarry(Known1, Known2, KnownCarry);
  46         EXPECT_EQ(Known, KnownComputed);
  47       });
  48     });
  49   });
  50 }
  51
  52 static void TestAddSubExhaustive(bool IsAdd) {
  53   unsigned Bits = 4;
  54   ForeachKnownBits(Bits, [&](const KnownBits &Known1) {
  55     ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
  56       KnownBits Known(Bits), KnownNSW(Bits);
  57       Known.Zero.setAllBits();
  58       Known.One.setAllBits();
  59       KnownNSW.Zero.setAllBits();
  60       KnownNSW.One.setAllBits();
  61
  62       ForeachNumInKnownBits(Known1, [&](const APInt &N1) {
  63         ForeachNumInKnownBits(Known2, [&](const APInt &N2) {
  64           bool Overflow;
  65           APInt Res;
  66           if (IsAdd)
  67             Res = N1.sadd_ov(N2, Overflow);
  68           else
  69             Res = N1.ssub_ov(N2, Overflow);
  70
  71           Known.One &= Res;
  72           Known.Zero &= ~Res;
  73
  74           if (!Overflow) {
  75             KnownNSW.One &= Res;
  76             KnownNSW.Zero &= ~Res;
  77           }
  78         });
  79       });
  80
  81       KnownBits KnownComputed =
  82           KnownBits::computeForAddSub(IsAdd, /*NSW*/ false, Known1, Known2);
  83       EXPECT_EQ(Known, KnownComputed);
  84
  85       // The NSW calculation is not precise, only check that it's
  86       // conservatively correct.
  87       KnownBits KnownNSWComputed = KnownBits::computeForAddSub(
  88           IsAdd, /*NSW*/true, Known1, Known2);
  89       EXPECT_TRUE(KnownNSWComputed.Zero.isSubsetOf(KnownNSW.Zero));
  90       EXPECT_TRUE(KnownNSWComputed.One.isSubsetOf(KnownNSW.One));
  91     });
  92   });
  93 }
  94
  95 TEST(KnownBitsTest, AddSubExhaustive) {
  96   TestAddSubExhaustive(true);
  97   TestAddSubExhaustive(false);
  98 }
  99
 100 TEST(KnownBitsTest, BinaryExhaustive) {
 101   unsigned Bits = 4;
 102   ForeachKnownBits(Bits, [&](const KnownBits &Known1) {
 103     ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
 104       KnownBits KnownAnd(Bits);
 105       KnownAnd.Zero.setAllBits();
 106       KnownAnd.One.setAllBits();
 107       KnownBits KnownOr(KnownAnd);
 108       KnownBits KnownXor(KnownAnd);
 109       KnownBits KnownUMax(KnownAnd);
 110       KnownBits KnownUMin(KnownAnd);
 111       KnownBits KnownSMax(KnownAnd);
 112       KnownBits KnownSMin(KnownAnd);
 113       KnownBits KnownMul(KnownAnd);
 114       KnownBits KnownMulHS(KnownAnd);
 115       KnownBits KnownMulHU(KnownAnd);
 116       KnownBits KnownUDiv(KnownAnd);
 117       KnownBits KnownURem(KnownAnd);
 118       KnownBits KnownSRem(KnownAnd);
 119       KnownBits KnownShl(KnownAnd);
 120       KnownBits KnownLShr(KnownAnd);
 121       KnownBits KnownAShr(KnownAnd);
 122
 123       ForeachNumInKnownBits(Known1, [&](const APInt &N1) {
 124         ForeachNumInKnownBits(Known2, [&](const APInt &N2) {
 125           APInt Res;
 126
 127           Res = N1 & N2;
 128           KnownAnd.One &= Res;
 129           KnownAnd.Zero &= ~Res;
 130
 131           Res = N1 | N2;
 132           KnownOr.One &= Res;
 133           KnownOr.Zero &= ~Res;
 134
 135           Res = N1 ^ N2;
 136           KnownXor.One &= Res;
 137           KnownXor.Zero &= ~Res;
 138
 139           Res = APIntOps::umax(N1, N2);
 140           KnownUMax.One &= Res;
 141           KnownUMax.Zero &= ~Res;
 142
 143           Res = APIntOps::umin(N1, N2);
 144           KnownUMin.One &= Res;
 145           KnownUMin.Zero &= ~Res;
 146
 147           Res = APIntOps::smax(N1, N2);
 148           KnownSMax.One &= Res;
 149           KnownSMax.Zero &= ~Res;
 150
 151           Res = APIntOps::smin(N1, N2);
 152           KnownSMin.One &= Res;
 153           KnownSMin.Zero &= ~Res;
 154
 155           Res = N1 * N2;
 156           KnownMul.One &= Res;
 157           KnownMul.Zero &= ~Res;
 158
 159           Res = (N1.sext(2 * Bits) * N2.sext(2 * Bits)).extractBits(Bits, Bits);
 160           KnownMulHS.One &= Res;
 161           KnownMulHS.Zero &= ~Res;
 162
 163           Res = (N1.zext(2 * Bits) * N2.zext(2 * Bits)).extractBits(Bits, Bits);
 164           KnownMulHU.One &= Res;
 165           KnownMulHU.Zero &= ~Res;
 166
 167           if (!N2.isZero()) {
 168             Res = N1.udiv(N2);
 169             KnownUDiv.One &= Res;
 170             KnownUDiv.Zero &= ~Res;
 171
 172             Res = N1.urem(N2);
 173             KnownURem.One &= Res;
 174             KnownURem.Zero &= ~Res;
 175
 176             Res = N1.srem(N2);
 177             KnownSRem.One &= Res;
 178             KnownSRem.Zero &= ~Res;
 179           }
 180
 181           if (N2.ult(1ULL << N1.getBitWidth())) {
 182             Res = N1.shl(N2);
 183             KnownShl.One &= Res;
 184             KnownShl.Zero &= ~Res;
 185
 186             Res = N1.lshr(N2);
 187             KnownLShr.One &= Res;
 188             KnownLShr.Zero &= ~Res;
 189
 190             Res = N1.ashr(N2);
 191             KnownAShr.One &= Res;
 192             KnownAShr.Zero &= ~Res;
 193           } else {
 194             KnownShl.resetAll();
 195             KnownLShr.resetAll();
 196             KnownAShr.resetAll();
 197           }
 198         });
 199       });
 200
 201       KnownBits ComputedAnd = Known1 & Known2;
 202       EXPECT_EQ(KnownAnd, ComputedAnd);
 203
 204       KnownBits ComputedOr = Known1 | Known2;
 205       EXPECT_EQ(KnownOr, ComputedOr);
 206
 207       KnownBits ComputedXor = Known1 ^ Known2;
 208       EXPECT_EQ(KnownXor, ComputedXor);
 209
 210       KnownBits ComputedUMax = KnownBits::umax(Known1, Known2);
 211       EXPECT_EQ(KnownUMax, ComputedUMax);
 212
 213       KnownBits ComputedUMin = KnownBits::umin(Known1, Known2);
 214       EXPECT_EQ(KnownUMin, ComputedUMin);
 215
 216       KnownBits ComputedSMax = KnownBits::smax(Known1, Known2);
 217       EXPECT_EQ(KnownSMax, ComputedSMax);
 218
 219       KnownBits ComputedSMin = KnownBits::smin(Known1, Known2);
 220       EXPECT_EQ(KnownSMin, ComputedSMin);
 221
 222       // The following are conservatively correct, but not guaranteed to be
 223       // precise.
 224       KnownBits ComputedMul = KnownBits::mul(Known1, Known2);
 225       EXPECT_TRUE(ComputedMul.Zero.isSubsetOf(KnownMul.Zero));
 226       EXPECT_TRUE(ComputedMul.One.isSubsetOf(KnownMul.One));
 227
 228       KnownBits ComputedMulHS = KnownBits::mulhs(Known1, Known2);
 229       EXPECT_TRUE(ComputedMulHS.Zero.isSubsetOf(KnownMulHS.Zero));
 230       EXPECT_TRUE(ComputedMulHS.One.isSubsetOf(KnownMulHS.One));
 231
 232       KnownBits ComputedMulHU = KnownBits::mulhu(Known1, Known2);
 233       EXPECT_TRUE(ComputedMulHU.Zero.isSubsetOf(KnownMulHU.Zero));
 234       EXPECT_TRUE(ComputedMulHU.One.isSubsetOf(KnownMulHU.One));
 235
 236       KnownBits ComputedUDiv = KnownBits::udiv(Known1, Known2);
 237       EXPECT_TRUE(ComputedUDiv.Zero.isSubsetOf(KnownUDiv.Zero));
 238       EXPECT_TRUE(ComputedUDiv.One.isSubsetOf(KnownUDiv.One));
 239
 240       KnownBits ComputedURem = KnownBits::urem(Known1, Known2);
 241       EXPECT_TRUE(ComputedURem.Zero.isSubsetOf(KnownURem.Zero));
 242       EXPECT_TRUE(ComputedURem.One.isSubsetOf(KnownURem.One));
 243
 244       KnownBits ComputedSRem = KnownBits::srem(Known1, Known2);
 245       EXPECT_TRUE(ComputedSRem.Zero.isSubsetOf(KnownSRem.Zero));
 246       EXPECT_TRUE(ComputedSRem.One.isSubsetOf(KnownSRem.One));
 247
 248       KnownBits ComputedShl = KnownBits::shl(Known1, Known2);
 249       EXPECT_TRUE(ComputedShl.Zero.isSubsetOf(KnownShl.Zero));
 250       EXPECT_TRUE(ComputedShl.One.isSubsetOf(KnownShl.One));
 251
 252       KnownBits ComputedLShr = KnownBits::lshr(Known1, Known2);
 253       EXPECT_TRUE(ComputedLShr.Zero.isSubsetOf(KnownLShr.Zero));
 254       EXPECT_TRUE(ComputedLShr.One.isSubsetOf(KnownLShr.One));
 255
 256       KnownBits ComputedAShr = KnownBits::ashr(Known1, Known2);
 257       EXPECT_TRUE(ComputedAShr.Zero.isSubsetOf(KnownAShr.Zero));
 258       EXPECT_TRUE(ComputedAShr.One.isSubsetOf(KnownAShr.One));
 259     });
 260   });
 261
 262   // Also test 'unary' binary cases where the same argument is repeated.
 263   ForeachKnownBits(Bits, [&](const KnownBits &Known) {
 264     KnownBits KnownMul(Bits);
 265     KnownMul.Zero.setAllBits();
 266     KnownMul.One.setAllBits();
 267
 268     ForeachNumInKnownBits(Known, [&](const APInt &N) {
 269       APInt Res = N * N;
 270       KnownMul.One &= Res;
 271       KnownMul.Zero &= ~Res;
 272     });
 273
 274     KnownBits ComputedMul = KnownBits::mul(Known, Known, /*SelfMultiply*/ true);
 275     EXPECT_TRUE(ComputedMul.Zero.isSubsetOf(KnownMul.Zero));
 276     EXPECT_TRUE(ComputedMul.One.isSubsetOf(KnownMul.One));
 277   });
 278 }
 279
 280 TEST(KnownBitsTest, UnaryExhaustive) {
 281   unsigned Bits = 4;
 282   ForeachKnownBits(Bits, [&](const KnownBits &Known) {
 283     KnownBits KnownAbs(Bits);
 284     KnownAbs.Zero.setAllBits();
 285     KnownAbs.One.setAllBits();
 286     KnownBits KnownAbsPoison(KnownAbs);
 287
 288     ForeachNumInKnownBits(Known, [&](const APInt &N) {
 289       APInt Res = N.abs();
 290       KnownAbs.One &= Res;
 291       KnownAbs.Zero &= ~Res;
 292
 293       if (!N.isMinSignedValue()) {
 294         KnownAbsPoison.One &= Res;
 295         KnownAbsPoison.Zero &= ~Res;
 296       }
 297     });
 298
 299     // abs() is conservatively correct, but not guaranteed to be precise.
 300     KnownBits ComputedAbs = Known.abs();
 301     EXPECT_TRUE(ComputedAbs.Zero.isSubsetOf(KnownAbs.Zero));
 302     EXPECT_TRUE(ComputedAbs.One.isSubsetOf(KnownAbs.One));
 303
 304     KnownBits ComputedAbsPoison = Known.abs(true);
 305     EXPECT_TRUE(ComputedAbsPoison.Zero.isSubsetOf(KnownAbsPoison.Zero));
 306     EXPECT_TRUE(ComputedAbsPoison.One.isSubsetOf(KnownAbsPoison.One));
 307   });
 308 }
 309
 310 TEST(KnownBitsTest, ICmpExhaustive) {
 311   unsigned Bits = 4;
 312   ForeachKnownBits(Bits, [&](const KnownBits &Known1) {
 313     ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
 314       bool AllEQ = true, NoneEQ = true;
 315       bool AllNE = true, NoneNE = true;
 316       bool AllUGT = true, NoneUGT = true;
 317       bool AllUGE = true, NoneUGE = true;
 318       bool AllULT = true, NoneULT = true;
 319       bool AllULE = true, NoneULE = true;
 320       bool AllSGT = true, NoneSGT = true;
 321       bool AllSGE = true, NoneSGE = true;
 322       bool AllSLT = true, NoneSLT = true;
 323       bool AllSLE = true, NoneSLE = true;
 324
 325       ForeachNumInKnownBits(Known1, [&](const APInt &N1) {
 326         ForeachNumInKnownBits(Known2, [&](const APInt &N2) {
 327           AllEQ &= N1.eq(N2);
 328           AllNE &= N1.ne(N2);
 329           AllUGT &= N1.ugt(N2);
 330           AllUGE &= N1.uge(N2);
 331           AllULT &= N1.ult(N2);
 332           AllULE &= N1.ule(N2);
 333           AllSGT &= N1.sgt(N2);
 334           AllSGE &= N1.sge(N2);
 335           AllSLT &= N1.slt(N2);
 336           AllSLE &= N1.sle(N2);
 337           NoneEQ &= !N1.eq(N2);
 338           NoneNE &= !N1.ne(N2);
 339           NoneUGT &= !N1.ugt(N2);
 340           NoneUGE &= !N1.uge(N2);
 341           NoneULT &= !N1.ult(N2);
 342           NoneULE &= !N1.ule(N2);
 343           NoneSGT &= !N1.sgt(N2);
 344           NoneSGE &= !N1.sge(N2);
 345           NoneSLT &= !N1.slt(N2);
 346           NoneSLE &= !N1.sle(N2);
 347         });
 348       });
 349
 350       Optional<bool> KnownEQ = KnownBits::eq(Known1, Known2);
 351       Optional<bool> KnownNE = KnownBits::ne(Known1, Known2);
 352       Optional<bool> KnownUGT = KnownBits::ugt(Known1, Known2);
 353       Optional<bool> KnownUGE = KnownBits::uge(Known1, Known2);
 354       Optional<bool> KnownULT = KnownBits::ult(Known1, Known2);
 355       Optional<bool> KnownULE = KnownBits::ule(Known1, Known2);
 356       Optional<bool> KnownSGT = KnownBits::sgt(Known1, Known2);
 357       Optional<bool> KnownSGE = KnownBits::sge(Known1, Known2);
 358       Optional<bool> KnownSLT = KnownBits::slt(Known1, Known2);
 359       Optional<bool> KnownSLE = KnownBits::sle(Known1, Known2);
 360
 361       EXPECT_EQ(AllEQ || NoneEQ, KnownEQ.has_value());
 362       EXPECT_EQ(AllNE || NoneNE, KnownNE.has_value());
 363       EXPECT_EQ(AllUGT || NoneUGT, KnownUGT.has_value());
 364       EXPECT_EQ(AllUGE || NoneUGE, KnownUGE.has_value());
 365       EXPECT_EQ(AllULT || NoneULT, KnownULT.has_value());
 366       EXPECT_EQ(AllULE || NoneULE, KnownULE.has_value());
 367       EXPECT_EQ(AllSGT || NoneSGT, KnownSGT.has_value());
 368       EXPECT_EQ(AllSGE || NoneSGE, KnownSGE.has_value());
 369       EXPECT_EQ(AllSLT || NoneSLT, KnownSLT.has_value());
 370       EXPECT_EQ(AllSLE || NoneSLE, KnownSLE.has_value());
 371
 372       EXPECT_EQ(AllEQ, KnownEQ.has_value() && KnownEQ.value());
 373       EXPECT_EQ(AllNE, KnownNE.has_value() && KnownNE.value());
 374       EXPECT_EQ(AllUGT, KnownUGT.has_value() && KnownUGT.value());
 375       EXPECT_EQ(AllUGE, KnownUGE.has_value() && KnownUGE.value());
 376       EXPECT_EQ(AllULT, KnownULT.has_value() && KnownULT.value());
 377       EXPECT_EQ(AllULE, KnownULE.has_value() && KnownULE.value());
 378       EXPECT_EQ(AllSGT, KnownSGT.has_value() && KnownSGT.value());
 379       EXPECT_EQ(AllSGE, KnownSGE.has_value() && KnownSGE.value());
 380       EXPECT_EQ(AllSLT, KnownSLT.has_value() && KnownSLT.value());
 381       EXPECT_EQ(AllSLE, KnownSLE.has_value() && KnownSLE.value());
 382
 383       EXPECT_EQ(NoneEQ, KnownEQ.has_value() && !KnownEQ.value());
 384       EXPECT_EQ(NoneNE, KnownNE.has_value() && !KnownNE.value());
 385       EXPECT_EQ(NoneUGT, KnownUGT.has_value() && !KnownUGT.value());
 386       EXPECT_EQ(NoneUGE, KnownUGE.has_value() && !KnownUGE.value());
 387       EXPECT_EQ(NoneULT, KnownULT.has_value() && !KnownULT.value());
 388       EXPECT_EQ(NoneULE, KnownULE.has_value() && !KnownULE.value());
 389       EXPECT_EQ(NoneSGT, KnownSGT.has_value() && !KnownSGT.value());
 390       EXPECT_EQ(NoneSGE, KnownSGE.has_value() && !KnownSGE.value());
 391       EXPECT_EQ(NoneSLT, KnownSLT.has_value() && !KnownSLT.value());
 392       EXPECT_EQ(NoneSLE, KnownSLE.has_value() && !KnownSLE.value());
 393     });
 394   });
 395 }
 396
 397 TEST(KnownBitsTest, GetMinMaxVal) {
 398   unsigned Bits = 4;
 399   ForeachKnownBits(Bits, [&](const KnownBits &Known) {
 400     APInt Min = APInt::getMaxValue(Bits);
 401     APInt Max = APInt::getMinValue(Bits);
 402     ForeachNumInKnownBits(Known, [&](const APInt &N) {
 403       Min = APIntOps::umin(Min, N);
 404       Max = APIntOps::umax(Max, N);
 405     });
 406     EXPECT_EQ(Min, Known.getMinValue());
 407     EXPECT_EQ(Max, Known.getMaxValue());
 408   });
 409 }
 410
 411 TEST(KnownBitsTest, GetSignedMinMaxVal) {
 412   unsigned Bits = 4;
 413   ForeachKnownBits(Bits, [&](const KnownBits &Known) {
 414     APInt Min = APInt::getSignedMaxValue(Bits);
 415     APInt Max = APInt::getSignedMinValue(Bits);
 416     ForeachNumInKnownBits(Known, [&](const APInt &N) {
 417       Min = APIntOps::smin(Min, N);
 418       Max = APIntOps::smax(Max, N);
 419     });
 420     EXPECT_EQ(Min, Known.getSignedMinValue());
 421     EXPECT_EQ(Max, Known.getSignedMaxValue());
 422   });
 423 }
 424
 425 TEST(KnownBitsTest, CountMaxActiveBits) {
 426   unsigned Bits = 4;
 427   ForeachKnownBits(Bits, [&](const KnownBits &Known) {
 428     unsigned Expected = 0;
 429     ForeachNumInKnownBits(Known, [&](const APInt &N) {
 430       Expected = std::max(Expected, N.getActiveBits());
 431     });
 432     EXPECT_EQ(Expected, Known.countMaxActiveBits());
 433   });
 434 }
 435
 436 TEST(KnownBitsTest, CountMaxSignificantBits) {
 437   unsigned Bits = 4;
 438   ForeachKnownBits(Bits, [&](const KnownBits &Known) {
 439     unsigned Expected = 0;
 440     ForeachNumInKnownBits(Known, [&](const APInt &N) {
 441       Expected = std::max(Expected, N.getSignificantBits());
 442     });
 443     EXPECT_EQ(Expected, Known.countMaxSignificantBits());
 444   });
 445 }
 446
 447 TEST(KnownBitsTest, SExtOrTrunc) {
 448   const unsigned NarrowerSize = 4;
 449   const unsigned BaseSize = 6;
 450   const unsigned WiderSize = 8;
 451   APInt NegativeFitsNarrower(BaseSize, -4, /*isSigned*/ true);
 452   APInt NegativeDoesntFitNarrower(BaseSize, -28, /*isSigned*/ true);
 453   APInt PositiveFitsNarrower(BaseSize, 14);
 454   APInt PositiveDoesntFitNarrower(BaseSize, 36);
 455   auto InitKnownBits = [&](KnownBits &Res, const APInt &Input) {
 456     Res = KnownBits(Input.getBitWidth());
 457     Res.One = Input;
 458     Res.Zero = ~Input;
 459   };
 460
 461   for (unsigned Size : {NarrowerSize, BaseSize, WiderSize}) {
 462     for (const APInt &Input :
 463          {NegativeFitsNarrower, NegativeDoesntFitNarrower, PositiveFitsNarrower,
 464           PositiveDoesntFitNarrower}) {
 465       KnownBits Test;
 466       InitKnownBits(Test, Input);
 467       KnownBits Baseline;
 468       InitKnownBits(Baseline, Input.sextOrTrunc(Size));
 469       Test = Test.sextOrTrunc(Size);
 470       EXPECT_EQ(Test, Baseline);
 471     }
 472   }
 473 }
 474
 475 TEST(KnownBitsTest, SExtInReg) {
 476   unsigned Bits = 4;
 477   for (unsigned FromBits = 1; FromBits <= Bits; ++FromBits) {
 478     ForeachKnownBits(Bits, [&](const KnownBits &Known) {
 479       APInt CommonOne = APInt::getAllOnes(Bits);
 480       APInt CommonZero = APInt::getAllOnes(Bits);
 481       unsigned ExtBits = Bits - FromBits;
 482       ForeachNumInKnownBits(Known, [&](const APInt &N) {
 483         APInt Ext = N << ExtBits;
 484         Ext.ashrInPlace(ExtBits);
 485         CommonOne &= Ext;
 486         CommonZero &= ~Ext;
 487       });
 488       KnownBits KnownSExtInReg = Known.sextInReg(FromBits);
 489       EXPECT_EQ(CommonOne, KnownSExtInReg.One);
 490       EXPECT_EQ(CommonZero, KnownSExtInReg.Zero);
 491     });
 492   }
 493 }
 494
 495 TEST(KnownBitsTest, CommonBitsSet) {
 496   unsigned Bits = 4;
 497   ForeachKnownBits(Bits, [&](const KnownBits &Known1) {
 498     ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
 499       bool HasCommonBitsSet = false;
 500       ForeachNumInKnownBits(Known1, [&](const APInt &N1) {
 501         ForeachNumInKnownBits(Known2, [&](const APInt &N2) {
 502           HasCommonBitsSet |= N1.intersects(N2);
 503         });
 504       });
 505       EXPECT_EQ(!HasCommonBitsSet,
 506                 KnownBits::haveNoCommonBitsSet(Known1, Known2));
 507     });
 508   });
 509 }
 510
 511 TEST(KnownBitsTest, ConcatBits) {
 512   unsigned Bits = 4;
 513   for (unsigned LoBits = 1; LoBits < Bits; ++LoBits) {
 514     unsigned HiBits = Bits - LoBits;
 515     ForeachKnownBits(LoBits, [&](const KnownBits &KnownLo) {
 516       ForeachKnownBits(HiBits, [&](const KnownBits &KnownHi) {
 517         KnownBits KnownAll = KnownHi.concat(KnownLo);
 518
 519         EXPECT_EQ(KnownLo.countMinPopulation() + KnownHi.countMinPopulation(),
 520                   KnownAll.countMinPopulation());
 521         EXPECT_EQ(KnownLo.countMaxPopulation() + KnownHi.countMaxPopulation(),
 522                   KnownAll.countMaxPopulation());
 523
 524         KnownBits ExtractLo = KnownAll.extractBits(LoBits, 0);
 525         KnownBits ExtractHi = KnownAll.extractBits(HiBits, LoBits);
 526
 527         EXPECT_EQ(KnownLo.One.getZExtValue(), ExtractLo.One.getZExtValue());
 528         EXPECT_EQ(KnownHi.One.getZExtValue(), ExtractHi.One.getZExtValue());
 529         EXPECT_EQ(KnownLo.Zero.getZExtValue(), ExtractLo.Zero.getZExtValue());
 530         EXPECT_EQ(KnownHi.Zero.getZExtValue(), ExtractHi.Zero.getZExtValue());
 531       });
 532     });
 533   }
 534 }
 535
 536 } // end anonymous namespace