[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, which has only the lowest bit set of X set.
+  /// The name comes from the X86 BMI instruction
+  KnownBits blsi() const;
+
+  /// Compute known bits for X ^ (X - 1), which has all bits up to and including
+  /// the lowest set bit of X set. The name comes from the X86 BMI instruction.
+  KnownBits blsmsk() const;
+
   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 {
+  unsigned BitWidth = getBitWidth();
+  KnownBits Known(Zero, APInt(BitWidth, 0));
+  unsigned Max = countMaxTrailingZeros();
+  Known.Zero.setBitsFrom(std::min(Max + 1, BitWidth));
+  unsigned Min = countMinTrailingZeros();
+  if (Max == Min && Max < BitWidth)
+    Known.One.setBit(Max);
+  return Known;
+}
+
+KnownBits KnownBits::blsmsk() const {
+  unsigned BitWidth = getBitWidth();
+  KnownBits Known(BitWidth);
+  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 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;