[KnownBits] Add blsi and blsmsk

[craig.topper]

llvm/lib/Support/KnownBits.cpp

639

Its -> It's

[goldstein.w.n]

Fix spelling

[foad]

Personally I still think this is too much extra complexity for uncertain benefit, but I won't stand in the way if the other reviewers are happy.

In any case the comments need work and the new functions should have exhaustive tests.

llvm/lib/Support/KnownBits.cpp

639–642

This description seems confused about whether C is added to X or subtracted from X.

[goldstein.w.n]

In D142519#4079179, @foad wrote:

Personally I still think this is too much extra complexity for uncertain benefit, but I won't stand in the way if the other reviewers are happy.

In any case the comments need work and the new functions should have exhaustive tests.

Do the overloaded blsmsk functions need exhaustive? They are unimplemented. Just think its
easier to design the full API now in case it ever becomes desired.

[foad]

Things that are implemented should be tested. Things that aren't implemented shouldn't have the prototypes. (Of course you can design the full API now, but don't put the unimplemented parts in a patch and expect to commit it.)

[goldstein.w.n]

Revert to foad's method

[goldstein.w.n]

In D142519#4080713, @foad wrote:

Things that are implemented should be tested. Things that aren't implemented shouldn't have the prototypes. (Of course you can design the full API now, but don't put the unimplemented parts in a patch and expect to commit it.)

Okay, fair enough. Reverted back to your code.

[nikic]

LGTM. I'd suggest adding a description of what the operation is supposed to do in the comment, for those not familiar with bmi instructions.

llvm/include/llvm/Support/KnownBits.h

425

429

[goldstein.w.n]

In D142519#4081105, @nikic wrote:

LGTM. I'd suggest adding a description of what the operation is supposed to do in the comment, for those not familiar with bmi instructions.

Thanks will do before pushing. How does the rest of the series look?

[goldstein.w.n]

Rebase + update comments

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

llvm/include/llvm/Support/KnownBits.h

public:
   KnownBits byteSwap() const {
     return KnownBits(Zero.byteSwap(), One.byteSwap());
   }
 
   KnownBits reverseBits() const {
     return KnownBits(Zero.reverseBits(), One.reverseBits());
   }
 
+  /// Compute known bits for X & -X. The name comes from the X86 BMI instruction
+  /// BLSI.
+  KnownBits blsi(const KnownBits &NegX) const;
+  KnownBits blsi() const {
+    KnownBits NegX(getBitWidth());
+    return blsi(NegX);
+  }
+
+  /// Compute known bits for X ^ (X - 1). The name comes from the X86 BMI
+  /// instruction BLSMSK.
+  KnownBits blsmsk(const KnownBits &XMinusC, const APInt &C) const;
+  KnownBits blsmsk(const KnownBits &XMinusC) const {
+    APInt C = APInt::getAllOnes(getBitWidth());
+    return blsmsk(XMinusC, C);
+  }
+  KnownBits blsmsk() const {
+    KnownBits XMinusC(getBitWidth());
+    return blsmsk(XMinusC);
+  }
+
   bool operator==(const KnownBits &Other) const {
     return Zero == Other.Zero && One == Other.One;
   }
 
   bool operator!=(const KnownBits &Other) const { return !(*this == Other); }
 
   void print(raw_ostream &OS) const;
   void dump() const;

llvm/lib/Support/KnownBits.cpp

KnownBits &KnownBits::operator^=(const KnownBits &RHS) {
   // Result bit is 0 if both operand bits are 0 or both are 1.
   APInt Z = (Zero & RHS.Zero) | (One & RHS.One);
   // Result bit is 1 if one operand bit is 0 and the other is 1.
   One = (Zero & RHS.One) | (One & RHS.Zero);
   Zero = std::move(Z);
   return *this;
 }
 
+KnownBits KnownBits::blsi(const KnownBits &NegX) const {
+  KnownBits Known = *this & NegX;
+  unsigned BitWidth = getBitWidth();
+  unsigned Max =
+      std::min(countMaxTrailingZeros(), NegX.countMaxTrailingZeros());
+  Known.Zero.setBitsFrom(std::min(Max + 1, BitWidth));
+  unsigned Min =
+      std::max(countMinTrailingZeros(), NegX.countMinTrailingZeros());
+  if (Max == Min && Max < BitWidth)
+    Known.One.setBit(Max);
+  return Known;
+}
+
+// TODO: It's possible for use to have more information on `XMinusC` than `X`
+// (if there is an assume or branch on `X-C` for example). The logic could be
+// more complete by trying to get min set bit from (XMinusOne + C). Note, `C`
+// is generally `-1` but in some cases can be shrunk by SimplifyDemandedBits.
+KnownBits KnownBits::blsmsk(const KnownBits &XMinusC, const APInt &C) const {
+  KnownBits Known = *this ^ XMinusC;
+  unsigned BitWidth = getBitWidth();
+  unsigned Max = countMaxTrailingZeros();
+  Known.Zero.setBitsFrom(std::min(Max + 1, BitWidth));
+  unsigned Min = countMinTrailingZeros();
+  Known.One.setLowBits(std::min(Min + 1, BitWidth));
+  return Known;
+  (void)XMinusC;
+  (void)C;
+}
+
 void KnownBits::print(raw_ostream &OS) const {
   OS << "{Zero=" << Zero << ", One=" << One << "}";
 }
 void KnownBits::dump() const {
   print(dbgs());
   dbgs() << "\n";
 }

llvm/unittests/Support/KnownBitsTest.cpp

 
 TEST(KnownBitsTest, UnaryExhaustive) {
   unsigned Bits = 4;
   ForeachKnownBits(Bits, [&](const KnownBits &Known) {
     KnownBits KnownAbs(Bits);
     KnownAbs.Zero.setAllBits();
     KnownAbs.One.setAllBits();
     KnownBits KnownAbsPoison(KnownAbs);
+    KnownBits KnownBlsi(Bits);
+    KnownBlsi.Zero.setAllBits();
+    KnownBlsi.One.setAllBits();
+    KnownBits KnownBlsmsk(Bits);
+    KnownBlsmsk.Zero.setAllBits();
+    KnownBlsmsk.One.setAllBits();
 
     ForeachNumInKnownBits(Known, [&](const APInt &N) {
       APInt Res = N.abs();
       KnownAbs.One &= Res;
       KnownAbs.Zero &= ~Res;
 
       if (!N.isMinSignedValue()) {
         KnownAbsPoison.One &= Res;
         KnownAbsPoison.Zero &= ~Res;
       }
+
+      Res = N & -N;
+      KnownBlsi.One &= Res;
+      KnownBlsi.Zero &= ~Res;
+
+      Res = N ^ (N - 1);
+      KnownBlsmsk.One &= Res;
+      KnownBlsmsk.Zero &= ~Res;
     });
 
     // abs() is conservatively correct, but not guaranteed to be precise.
     KnownBits ComputedAbs = Known.abs();
     EXPECT_TRUE(ComputedAbs.Zero.isSubsetOf(KnownAbs.Zero));
     EXPECT_TRUE(ComputedAbs.One.isSubsetOf(KnownAbs.One));
 
     KnownBits ComputedAbsPoison = Known.abs(true);
     EXPECT_TRUE(ComputedAbsPoison.Zero.isSubsetOf(KnownAbsPoison.Zero));
     EXPECT_TRUE(ComputedAbsPoison.One.isSubsetOf(KnownAbsPoison.One));
+
+    KnownBits ComputedBlsi = Known.blsi();
+    EXPECT_EQ(KnownBlsi, ComputedBlsi);
+
+    KnownBits ComputedBlsmsk = Known.blsmsk();
+    EXPECT_EQ(KnownBlsmsk, ComputedBlsmsk);
   });
 }
 
 TEST(KnownBitsTest, ICmpExhaustive) {
   unsigned Bits = 4;
   ForeachKnownBits(Bits, [&](const KnownBits &Known1) {
     ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
       bool AllEQ = true, NoneEQ = true;