[ValueTracking] Add KnownBits patterns `xor(x, x - 1)` and `and(x, -x)` for knowing upper bits to be zero

These two BMI pattern will clear the upper bits of result past the
first set bit. So if we know a single bit in `x` is set, we know that
`results[bitwidth - 1, log2(x) + 1] = 0`.

Alive2:
blsmsk: https://alive2.llvm.org/ce/z/a397BS
blsi: https://alive2.llvm.org/ce/z/tsbQhC

Differential Revision: https://reviews.llvm.org/D142271

1 files changed, 33 insertions, 4 deletions

diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp
index 05b802c..536d880 100644
--- a/llvm/lib/Analysis/ValueTracking.cpp
+++ b/llvm/lib/Analysis/ValueTracking.cpp
@@ -1077,6 +1077,22 @@ static void computeKnownBitsFromOperator(const Operator *I,
     computeKnownBits(I->getOperand(1), DemandedElts, Known, Depth + 1, Q);
     computeKnownBits(I->getOperand(0), DemandedElts, Known2, Depth + 1, Q);
 
+    Value *X = nullptr, *Y = nullptr;
+    // and(x, -x) is a common idiom for clearing all but lowest set bit. If we
+    // have a single known bit in x, we can clear all bits above it.
+    // TODO: instcombine often reassociates independent `and` which can hide
+    // this pattern. Try to match and(x, and(-x, y)) / and(and(x, y), -x).
+    if (!Known.One.isZero() || !Known2.One.isZero()) {
+      if (match(I, m_c_BinOp(m_Value(X), m_Neg(m_Deferred(X))))) {
+        // -(-x) == x so pick whichever we can get a better result with.
+        if (Known.countMaxTrailingZeros() <= Known2.countMaxTrailingZeros())
+          Known = Known.blsi();
+        else
+          Known = Known2.blsi();
+
+        break;
+      }
+    }
     Known &= Known2;
 
     // and(x, add (x, -1)) is a common idiom that always clears the low bit;
@@ -1084,7 +1100,6 @@ static void computeKnownBitsFromOperator(const Operator *I,
     // matching the form add(x, add(x, y)) where y is odd.
     // TODO: This could be generalized to clearing any bit set in y where the
     // following bit is known to be unset in y.
-    Value *X = nullptr, *Y = nullptr;
     if (!Known.Zero[0] && !Known.One[0] &&
         match(I, m_c_BinOp(m_Value(X), m_Add(m_Deferred(X), m_Value(Y))))) {
       Known2.resetAll();
@@ -1100,12 +1115,26 @@ static void computeKnownBitsFromOperator(const Operator *I,
 
     Known |= Known2;
     break;
-  case Instruction::Xor:
+  case Instruction::Xor: {
     computeKnownBits(I->getOperand(1), DemandedElts, Known, Depth + 1, Q);
     computeKnownBits(I->getOperand(0), DemandedElts, Known2, Depth + 1, Q);
 
-    Known ^= Known2;
-    break;
+    Value *X = nullptr;
+    // xor(x, x + -1) is a common idiom that will clear all bits above
+    // the lowest set bit. We can safely say any bit past the lowest
+    // known one must be zero.
+    // TODO: `x + -1` is often shrunk `x + C` which `C` is minimum bits needed
+    // for demanded. This can cause us to miss this pattern. Expand to account
+    // for `x + -1` in the context of demanded bits.
+    if ((!Known.One.isZero() || !Known2.One.isZero()) &&
+        match(I, m_c_BinOp(m_Value(X), m_c_Add(m_Deferred(X), m_AllOnes())))) {
+      // Known2 is confusingly LHS.
+      const KnownBits &XBits = I->getOperand(0) == X ? Known2 : Known;
+      Known = XBits.blsmsk();
+    } else {
+      Known ^= Known2;
+    }
+  } break;
   case Instruction::Mul: {
     bool NSW = Q.IIQ.hasNoSignedWrap(cast<OverflowingBinaryOperator>(I));
     computeKnownBitsMul(I->getOperand(0), I->getOperand(1), NSW, DemandedElts,