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

[goldstein.w.n]

Summary

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

[craig.topper]

llvm/lib/Analysis/ValueTracking.cpp

1121–1122

The description of blsmsk says "Sets all the lower bits of the destination operand to “1” up to and including lowest set bit (=1) in the source operand".

[craig.topper]

llvm/lib/Analysis/ValueTracking.cpp

1083

that sounds more like reassociating than commuting.

[goldstein.w.n]

llvm/lib/Analysis/ValueTracking.cpp

1083

that sounds more like reassociating than commuting.

Yup, yet again I get my properties wrong :(

1121–1122

The description of blsmsk says "Sets all the lower bits of the destination operand to “1” up to and including lowest set bit (=1) in the source operand".

Err, yeah should be 'clear all bits above the lowest set bit'. Will fix.

[goldstein.w.n]

Fix spellings / grammars

[nikic]

I believe this is missing negative tests (e.g. x & -y, x ^ (x + 2)). We should also have tests for commuted variants and basic vector tests.

llvm/lib/Analysis/ValueTracking.cpp

1080

1091

APInt::getBitsSetFrom(BitWidth, MinBit + 1)

1093

Redundant parentheses.

1131

I'd suggest to combine these two matches as match(I, m_c_BinOp(m_Value(X), m_Add(m_Deferred(X), m_AllOnes()))).

1135

APInt::getBitsSetFrom here again.

[foad]

I suggest implementing this in new helper functions KnownBits::blsi and KnownBits::blsmsk (if we're happy with those names), plus comprehensive test coverage in unittests/Support/KnownBitsTest.cpp.

llvm/lib/Analysis/ValueTracking.cpp

1121–1122

'clear all bits above the lowest set bit' isn't enough. It also sets all bits below the lowest set bit.

[goldstein.w.n]

llvm/lib/Analysis/ValueTracking.cpp

1121–1122

'clear all bits above the lowest set bit' isn't enough. It also sets all bits below the lowest set bit.

If we know all bits below the first known set bit, then yes we can full evaluate (although this is already handled by the normal constant propegation of bits through the xor/sub.

But if we only know a single bit, we don't know if there is a bit below it that is also set, so I don't see a way we can start setting the bits below it.

You are right though that we can always set Known.One.setBit(0). In fact we can make it a bit more generic:

(xor (x, (sub x, OddC))) -> isOdd

https://alive2.llvm.org/ce/z/aaABdS

Will add that.

[goldstein.w.n]

In D142271#4073849, @foad wrote:

I suggest implementing this in new helper functions KnownBits::blsi and KnownBits::blsmsk (if we're happy with those names), plus comprehensive test coverage in unittests/Support/KnownBitsTest.cpp.

So started doing this. I realized, however, that what we really want is something like computeKnownBitsFromAndXor.

I think though doing all that in one patch is too much. Think it makes sense here to do the following:

1. Add the BMI patterns (this patch)
2. Factor our and/xor into common function (this will cleanup the BMI logics) + get the odd bit pattern for XOR
3. Going to apply this in simplifydemanded bits: https://reviews.llvm.org/D142300

So for this patch would prefer skipping adding into new functions as it will just be temporary anyways (unless @nikic you are okay with me bloating this patch with addition of factoring and / xor logic into common function and combining there logic, otherwise will make it follow up).

[craig.topper]

llvm/lib/Analysis/ValueTracking.cpp

1088

I'm not sure about this min. The -x operand will potentially find less trailing bits due to the recursion limit in computeKnownBits. It has one more node to walk through. Using the tailing zeros bits based on which operand is x seems more reliable.

[goldstein.w.n]

llvm/lib/Analysis/ValueTracking.cpp

1088

I'm not sure about this min. The -x operand will potentially find less trailing bits due to the recursion limit in computeKnownBits. It has one more node to walk through. Using the tailing zeros bits based on which operand is x seems more reliable.

I think its possible for -x to find more bits if, for example, there is an llvm.assume on -x but but not on x.

[goldstein.w.n]

Improve test coverage + fix nits

[goldstein.w.n]

llvm/test/Transforms/InstCombine/ctpop-pow2.ll

150

This regression is fixed in: https://reviews.llvm.org/D142429

What is happening is computeKnownBits is allowing instsimplify to optimize out the ctpop b.c its ctpop(x & 1), but since SimplifyDemandedUseBits doesn't have this logic yet, it never gets optimized out. D142429 starts using computeKnownBits in SimplifyDemandedUseBits which fixed this.

[foad]

In D142271#4073849, @foad wrote:

I suggest implementing this in new helper functions KnownBits::blsi and KnownBits::blsmsk (if we're happy with those names), plus comprehensive test coverage in unittests/Support/KnownBitsTest.cpp.

I was thinking of something like D142469. Is this any use to you?

[goldstein.w.n]

In D142271#4077056, @foad wrote:

In D142271#4073849, @foad wrote:

I suggest implementing this in new helper functions KnownBits::blsi and KnownBits::blsmsk (if we're happy with those names), plus comprehensive test coverage in unittests/Support/KnownBitsTest.cpp.

I was thinking of something like D142469. Is this any use to you?

I see, yeah that makes sense although I would design it as a static API b.c we can technically get more information from -x or x - 1 than x itself if it happens to match some assume.
I.e:

static KnownBits blsi(KnowBits X, KnownBits NegX) const;
static KnownBits blsmsk(KnowBits X, KnownBits XMinus1) const;

(Also realized there is a bug in the current impl as XMinus1.One.countTrailingZeros() can't be used for low bound).

Do you want to make that an independent patch or want me to just combine it with this?

[foad]

In D142271#4077955, @goldstein.w.n wrote:

I see, yeah that makes sense although I would design it as a static API b.c we can technically get more information from -x or x - 1 than x itself if it happens to match some assume.

Is that really going to happen in practice? To me it seems so unlikely as to be not worth worrying about, for the sake a a nice simple API.

[goldstein.w.n]

In D142271#4077990, @foad wrote:

In D142271#4077955, @goldstein.w.n wrote:

I see, yeah that makes sense although I would design it as a static API b.c we can technically get more information from -x or x - 1 than x itself if it happens to match some assume.

Is that really going to happen in practice? To me it seems so unlikely as to be not worth worrying about, for the sake a a nice simple API.

Personally in favor of completeness. Or at least writing an API that makes it easy to make complete at a later time with a TODO.

[goldstein.w.n]

Rebase and use blsi/blsmsk api

[goldstein.w.n]

In D142271#4077990, @foad wrote:

In D142271#4077955, @goldstein.w.n wrote:

I see, yeah that makes sense although I would design it as a static API b.c we can technically get more information from -x or x - 1 than x itself if it happens to match some assume.

Is that really going to happen in practice? To me it seems so unlikely as to be not worth worrying about, for the sake a a nice simple API.

This is how I'd do it: D142519. Keeps you code but adds overloads for specifying the exact knownbits for -x / x-C.

[goldstein.w.n]

Rebase

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

1087

Add a comment that as -(-x) == x, we can view this as a blsi operation on either operand, and pick whichever produces the best result.

1090

break here? Don't think we want to fall through.

1131

m_APInt(C) -> m_AllOnes().

1133

Shouldn't this be ? Known : Known2? We want the known bits of X, not of X-1.

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

1133

Ignore this comment, the variable naming is a bit confusing here.

[goldstein.w.n]

Rebase + update comments + allones > apint

[goldstein.w.n]

NB; Applied all relevant changes here to D142427

llvm/lib/Analysis/ValueTracking.cpp

1090

break here? Don't think we want to fall through.

Fallthrough here has no issue. While I think the blsi case is mutually exclusive with the other transform, I generally think breaking early in this type of code (where you have back-to-back cases) can make things unclear as the assumption is generally we will try them all.

1131

m_APInt(C) -> m_AllOnes().

1131

m_APInt(C) -> m_AllOnes().

Sure, had changed to m_APInt(C) for the todo to stress that C could be any constant but guess no real reason for it.

1133

Ignore this comment, the variable naming is a bit confusing here.

[goldstein.w.n]

Rebase

[nikic]

LGTM

llvm/lib/Analysis/ValueTracking.cpp

1090

At least with this current code structure, falling through is pretty confusing. Known was previously the known bits of the second operand (that is either X or -X) and now it will be the known bits of X & -X. I guess this is fine in practice because & is idempotent, so we end up computing something like X & X & -X.

The new code structure in D142427 avoids this problem, but for this patch I would not do the fall through.

[foad]

llvm/lib/Analysis/ValueTracking.cpp

1087

A less "if"fy way to implement this would be:

Known = Known.blsi();
Known2 = Known2.blsi();
// should probably have a helper for the following two lines, similar to KnownBits::commonBits
Known.Zero |= Known2.Zero;
Known.One |= Known2.One;

(But I'm still sceptical that it gives any practical benefit.)

[goldstein.w.n]

Add Break

llvm/lib/Analysis/ValueTracking.cpp

1087

A less "if"fy way to implement this would be:

Known = Known.blsi();
Known2 = Known2.blsi();
// should probably have a helper for the following two lines, similar to KnownBits::commonBits
Known.Zero |= Known2.Zero;
Known.One |= Known2.One;

I'm not sure this is cleaner / clearer / faster.

(But I'm still sceptical that it gives any practical benefit.)

Agreeds its not a big deal, but it can change the result and we don't need any extra expensive calls to handle it so seems like "why not" (would agree with you if we would need an extra computeKnownBits call or something). I added two new tests: blsi_differing_lowbits and blsi_differing_lowbits2 which only work if we pick the minimum.

1090

At least with this current code structure, falling through is pretty confusing. Known was previously the known bits of the second operand (that is either X or -X) and now it will be the known bits of X & -X. I guess this is fine in practice because & is idempotent, so we end up computing something like X & X & -X.

The new code structure in D142427 avoids this problem, but for this patch I would not do the fall through.

Okay added the break, guess its only temporary anyways and doesn't change any of the tests.

[goldstein.w.n]

Rebase

[nikic]

Any reason not to commit the first three patches in this stack yet?

[goldstein.w.n]

In D142271#4136983, @nikic wrote:

Any reason not to commit the first three patches in this stack yet?

I generally like to keep series together, but not strong reason.

Are the following 4 problematic?

But not issue pushing first 3 if youd prefer

[goldstein.w.n]

In D142271#4136983, @nikic wrote:

Any reason not to commit the first three patches in this stack yet?

Pushed first three, but the following four not be forgotten? They have been sitting around for a while (likewise will push for two of the series starting at D142827, but the last 4 have also been sitting around for a while. Can they be looked at?)

llvm/lib/Analysis/ValueTracking.cpp

if (MDNode *MD =
             Q.IIQ.getMetadata(cast<LoadInst>(I), LLVMContext::MD_range))
       computeKnownBitsFromRangeMetadata(*MD, Known);
     break;
   case Instruction::And: {
     // If either the LHS or the RHS are Zero, the result is zero.
     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;
     // here we handle the more general case of adding any odd number by
     // 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();
       computeKnownBits(Y, DemandedElts, Known2, Depth + 1, Q);
       if (Known2.countMinTrailingOnes() > 0)
         Known.Zero.setBit(0);
     }
     break;
   }
   case Instruction::Or:
     computeKnownBits(I->getOperand(1), DemandedElts, Known, Depth + 1, Q);
     computeKnownBits(I->getOperand(0), DemandedElts, Known2, Depth + 1, Q);
 
     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);
 
+    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;
+    }
+  } break;
   case Instruction::Mul: {
     bool NSW = Q.IIQ.hasNoSignedWrap(cast<OverflowingBinaryOperator>(I));
     computeKnownBitsMul(I->getOperand(0), I->getOperand(1), NSW, DemandedElts,
                         Known, Known2, Depth, Q);
     break;
   }
   case Instruction::UDiv: {
     computeKnownBits(I->getOperand(0), Known, Depth + 1, Q);

llvm/test/Analysis/ValueTracking/knownbits-bmi-pattern.ll

;
   %x2 = sub <2 x i32> %x1, <i32 1, i32 1>
   %x3 = xor <2 x i32> %x2, %x1
   %z = icmp ne <2 x i32> %x3, <i32 8, i32 8>
   ret <2 x i1> %z
 }
 
 define <2 x i1> @blsmsk_ne_is_true_diff_vec(<2 x i32> %x) {
 ; CHECK-LABEL: @blsmsk_ne_is_true_diff_vec(
-; CHECK-NEXT:    [[X1:%.*]] = or <2 x i32> [[X:%.*]], <i32 10, i32 130>
-; CHECK-NEXT:    [[X2:%.*]] = add nsw <2 x i32> [[X1]], <i32 -1, i32 -1>
-; CHECK-NEXT:    [[X3:%.*]] = xor <2 x i32> [[X2]], [[X1]]
-; CHECK-NEXT:    [[Z:%.*]] = icmp ne <2 x i32> [[X3]], <i32 8, i32 8>
-; CHECK-NEXT:    ret <2 x i1> [[Z]]
+; CHECK-NEXT:    ret <2 x i1> <i1 true, i1 true>
 ;
   %x1 = or <2 x i32> %x, <i32 10, i32 130>
   %x2 = sub <2 x i32> %x1, <i32 1, i32 1>
   %x3 = xor <2 x i32> %x2, %x1
   %z = icmp ne <2 x i32> %x3, <i32 8, i32 8>
   ret <2 x i1> %z
 }
 
;
   %x2 = sub <2 x i32> %x1, <i32 1, i32 1>
   %x3 = xor <2 x i32> %x2, %x1
   %z = icmp ugt <2 x i32> %x3, <i32 8, i32 8>
   ret <2 x i1> %z
 }
 
 define i1 @blsmsk_signed_is_false(i32 %x) {
 ; CHECK-LABEL: @blsmsk_signed_is_false(
-; CHECK-NEXT:    [[X1:%.*]] = or i32 [[X:%.*]], 10
-; CHECK-NEXT:    [[X2:%.*]] = add nsw i32 [[X1]], -1
-; CHECK-NEXT:    [[X3:%.*]] = xor i32 [[X2]], [[X]]
-; CHECK-NEXT:    [[Z:%.*]] = icmp slt i32 [[X3]], 0
-; CHECK-NEXT:    ret i1 [[Z]]
+; CHECK-NEXT:    ret i1 false
 ;
   %x1 = or i32 %x, 10
   %x2 = sub i32 %x1, 1
   %x3 = xor i32 %x1, %x2
   %z = icmp slt i32 %x3, 0
   ret i1 %z
 }
 
 define i32 @blsmsk_add_eval(i32 %x) {
 ; CHECK-LABEL: @blsmsk_add_eval(
-; CHECK-NEXT:    [[X1:%.*]] = or i32 [[X:%.*]], 9
-; CHECK-NEXT:    [[X2:%.*]] = add nsw i32 [[X1]], -1
-; CHECK-NEXT:    [[X3:%.*]] = xor i32 [[X2]], [[X1]]
-; CHECK-NEXT:    [[Z:%.*]] = add i32 [[X3]], 32
-; CHECK-NEXT:    ret i32 [[Z]]
+; CHECK-NEXT:    ret i32 33
 ;
   %x1 = or i32 %x, 9
   %x2 = sub i32 %x1, 1
   %x3 = xor i32 %x2, %x1
   %z = add i32 %x3, 32
   ret i32 %z
 }
 
 define <2 x i32> @blsmsk_add_eval_vec(<2 x i32> %x) {
 ; CHECK-LABEL: @blsmsk_add_eval_vec(
 ; CHECK-NEXT:    [[X1:%.*]] = or <2 x i32> [[X:%.*]], <i32 9, i32 9>
 ; CHECK-NEXT:    [[X2:%.*]] = add nsw <2 x i32> [[X1]], <i32 -1, i32 -1>
 ; CHECK-NEXT:    [[X3:%.*]] = xor <2 x i32> [[X2]], [[X1]]
-; CHECK-NEXT:    [[Z:%.*]] = add <2 x i32> [[X3]], <i32 32, i32 32>
+; CHECK-NEXT:    [[Z:%.*]] = or <2 x i32> [[X3]], <i32 32, i32 32>
 ; CHECK-NEXT:    ret <2 x i32> [[Z]]
 ;
   %x1 = or <2 x i32> %x, <i32 9, i32 9>
   %x2 = add <2 x i32> %x1, <i32 -1, i32 -1>
   %x3 = xor <2 x i32> %x2, %x1
   %z = add <2 x i32> %x3, <i32 32, i32 32>
   ret <2 x i32> %z
 }
 
 define i32 @blsmsk_sub_eval(i32 %x) {
 ; CHECK-LABEL: @blsmsk_sub_eval(
 ; CHECK-NEXT:    [[X1:%.*]] = or i32 [[X:%.*]], 9
-; CHECK-NEXT:    [[X2:%.*]] = add nsw i32 [[X1]], -1
+; CHECK-NEXT:    [[X2:%.*]] = add i32 [[X1]], 31
 ; CHECK-NEXT:    [[X3:%.*]] = xor i32 [[X1]], [[X2]]
-; CHECK-NEXT:    [[Z:%.*]] = add i32 [[X3]], -32
+; CHECK-NEXT:    [[Z:%.*]] = or i32 [[X3]], -32
 ; CHECK-NEXT:    ret i32 [[Z]]
 ;
   %x1 = or i32 %x, 9
   %x2 = sub i32 %x1, 1
   %x3 = xor i32 %x1, %x2
   %z = sub i32 %x3, 32
   ret i32 %z
 }
 
 define i32 @blsmsk_or_eval(i32 %x) {
 ; CHECK-LABEL: @blsmsk_or_eval(
-; CHECK-NEXT:    [[X1:%.*]] = or i32 [[X:%.*]], 129
-; CHECK-NEXT:    [[X2:%.*]] = add nsw i32 [[X1]], -1
-; CHECK-NEXT:    [[X3:%.*]] = xor i32 [[X2]], [[X1]]
-; CHECK-NEXT:    [[Z:%.*]] = or i32 [[X3]], 32
-; CHECK-NEXT:    ret i32 [[Z]]
+; CHECK-NEXT:    ret i32 33
 ;
   %x1 = or i32 %x, 129
   %x2 = sub i32 %x1, 1
   %x3 = xor i32 %x2, %x1
   %z = or i32 %x3, 32
   ret i32 %z
 }
 
;
   %x2 = add <2 x i32> %x1, <i32 -1, i32 -1>
   %x3 = xor <2 x i32> %x2, %x1
   %z = or <2 x i32> %x3, <i32 32, i32 32>
   ret <2 x i32> %z
 }
 
 define i32 @blsmsk_xor_eval(i32 %x) {
 ; CHECK-LABEL: @blsmsk_xor_eval(
-; CHECK-NEXT:    [[X1:%.*]] = or i32 [[X:%.*]], 255
-; CHECK-NEXT:    [[X2:%.*]] = add nsw i32 [[X1]], -1
-; CHECK-NEXT:    [[X3:%.*]] = xor i32 [[X1]], [[X2]]
-; CHECK-NEXT:    [[Z1:%.*]] = or i32 [[X3]], 32
-; CHECK-NEXT:    ret i32 [[Z1]]
+; CHECK-NEXT:    ret i32 33
 ;
   %x1 = or i32 %x, 255
   %x2 = sub i32 %x1, 1
   %x3 = xor i32 %x1, %x2
   %z = xor i32 %x3, 32
   ret i32 %z
 }
 
;
   ret <2 x i32> %z
 }
 
 define i1 @blsmsk_eq_is_false_assume(i32 %x) {
 ; CHECK-LABEL: @blsmsk_eq_is_false_assume(
 ; CHECK-NEXT:    [[LB:%.*]] = and i32 [[X:%.*]], 4
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[LB]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
-; CHECK-NEXT:    [[X2:%.*]] = add nsw i32 [[X]], -1
-; CHECK-NEXT:    [[X3:%.*]] = xor i32 [[X2]], [[X]]
-; CHECK-NEXT:    [[Z:%.*]] = icmp eq i32 [[X3]], 8
-; CHECK-NEXT:    ret i1 [[Z]]
+; CHECK-NEXT:    ret i1 false
 ;
   %lb = and i32 %x, 4
   %cmp = icmp ne i32 %lb, 0
   call void @llvm.assume(i1 %cmp)
   %x2 = add i32 %x, -1
   %x3 = xor i32 %x2, %x
   %z = icmp eq i32 %x3, 8
   ret i1 %z
;
   ret i1 %z
 }
 
 define i32 @blsmsk_add_eval_assume(i32 %x) {
 ; CHECK-LABEL: @blsmsk_add_eval_assume(
 ; CHECK-NEXT:    [[LB:%.*]] = and i32 [[X:%.*]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[LB]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
-; CHECK-NEXT:    [[X2:%.*]] = add nsw i32 [[X]], -1
-; CHECK-NEXT:    [[X3:%.*]] = xor i32 [[X2]], [[X]]
-; CHECK-NEXT:    [[Z:%.*]] = add i32 [[X3]], 32
-; CHECK-NEXT:    ret i32 [[Z]]
+; CHECK-NEXT:    ret i32 33
 ;
   %lb = and i32 %x, 1
   %cmp = icmp ne i32 %lb, 0
   call void @llvm.assume(i1 %cmp)
   %x2 = sub i32 %x, 1
   %x3 = xor i32 %x2, %x
   %z = add i32 %x3, 32
   ret i32 %z
;
   ret <2 x i32> %z
 }
 
 define i32 @blsmsk_sub_eval_assume(i32 %x) {
 ; CHECK-LABEL: @blsmsk_sub_eval_assume(
 ; CHECK-NEXT:    [[LB:%.*]] = and i32 [[X:%.*]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[LB]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
-; CHECK-NEXT:    [[X2:%.*]] = add nsw i32 [[X]], -1
+; CHECK-NEXT:    [[X2:%.*]] = add i32 [[X]], 31
 ; CHECK-NEXT:    [[X3:%.*]] = xor i32 [[X2]], [[X]]
-; CHECK-NEXT:    [[Z:%.*]] = add i32 [[X3]], -32
+; CHECK-NEXT:    [[Z:%.*]] = or i32 [[X3]], -32
 ; CHECK-NEXT:    ret i32 [[Z]]
 ;
   %lb = and i32 %x, 1
   %cmp = icmp ne i32 %lb, 0
   call void @llvm.assume(i1 %cmp)
   %x2 = sub i32 %x, 1
   %x3 = xor i32 %x, %x2
   %z = sub i32 %x3, 32
   ret i32 %z
 }
 
 define i32 @blsmsk_or_eval_assume(i32 %x) {
 ; CHECK-LABEL: @blsmsk_or_eval_assume(
 ; CHECK-NEXT:    [[LB:%.*]] = and i32 [[X:%.*]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[LB]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
-; CHECK-NEXT:    [[X2:%.*]] = add nsw i32 [[X]], -1
-; CHECK-NEXT:    [[X3:%.*]] = xor i32 [[X2]], [[X]]
-; CHECK-NEXT:    [[Z:%.*]] = or i32 [[X3]], 32
-; CHECK-NEXT:    ret i32 [[Z]]
+; CHECK-NEXT:    ret i32 33
 ;
   %lb = and i32 %x, 1
   %cmp = icmp ne i32 %lb, 0
   call void @llvm.assume(i1 %cmp)
   %x2 = sub i32 %x, 1
   %x3 = xor i32 %x2, %x
   %z = or i32 %x3, 32
   ret i32 %z
;
   %x3 = and i32 %x2, %x1
   %z = icmp ugt i32 %x3, 8
   ret i1 %z
 }
 
 
 define i32 @blsi_add_eval(i32 %x) {
 ; CHECK-LABEL: @blsi_add_eval(
-; CHECK-NEXT:    [[X1:%.*]] = or i32 [[X:%.*]], 9
-; CHECK-NEXT:    [[X2:%.*]] = sub nsw i32 0, [[X1]]
-; CHECK-NEXT:    [[X3:%.*]] = and i32 [[X1]], [[X2]]
-; CHECK-NEXT:    [[Z:%.*]] = add i32 [[X3]], 32
-; CHECK-NEXT:    ret i32 [[Z]]
+; CHECK-NEXT:    ret i32 33
 ;
   %x1 = or i32 %x, 9
   %x2 = sub i32 0, %x1
   %x3 = and i32 %x2, %x1
   %z = add i32 %x3, 32
   ret i32 %z
 }
 
 define i32 @blsi_sub_eval(i32 %x) {
 ; CHECK-LABEL: @blsi_sub_eval(
-; CHECK-NEXT:    [[X1:%.*]] = or i32 [[X:%.*]], 33
-; CHECK-NEXT:    [[X2:%.*]] = sub nsw i32 0, [[X1]]
-; CHECK-NEXT:    [[X3:%.*]] = and i32 [[X1]], [[X2]]
-; CHECK-NEXT:    [[Z:%.*]] = add i32 [[X3]], -32
-; CHECK-NEXT:    ret i32 [[Z]]
+; CHECK-NEXT:    ret i32 -31
 ;
   %x1 = or i32 %x, 33
   %x2 = sub i32 0, %x1
   %x3 = and i32 %x2, %x1
   %z = sub i32 %x3, 32
   ret i32 %z
 }
 
 define <2 x i32> @blsi_sub_eval_vec(<2 x i32> %x) {
 ; CHECK-LABEL: @blsi_sub_eval_vec(
 ; CHECK-NEXT:    [[X1:%.*]] = or <2 x i32> [[X:%.*]], <i32 33, i32 33>
 ; CHECK-NEXT:    [[X2:%.*]] = sub nsw <2 x i32> zeroinitializer, [[X1]]
 ; CHECK-NEXT:    [[X3:%.*]] = and <2 x i32> [[X1]], [[X2]]
-; CHECK-NEXT:    [[Z:%.*]] = add <2 x i32> [[X3]], <i32 -32, i32 -32>
+; CHECK-NEXT:    [[Z:%.*]] = or <2 x i32> [[X3]], <i32 -32, i32 -32>
 ; CHECK-NEXT:    ret <2 x i32> [[Z]]
 ;
   %x1 = or <2 x i32> %x, <i32 33, i32 33>
   %x2 = sub <2 x i32> <i32 0, i32 0>, %x1
   %x3 = and <2 x i32> %x1, %x2
   %z = sub <2 x i32> %x3, <i32 32, i32 32>
   ret <2 x i32> %z
 }
 
 define i32 @blsi_or_eval(i32 %x) {
 ; CHECK-LABEL: @blsi_or_eval(
-; CHECK-NEXT:    [[X1:%.*]] = or i32 [[X:%.*]], 129
-; CHECK-NEXT:    [[X2:%.*]] = sub nsw i32 0, [[X1]]
-; CHECK-NEXT:    [[X3:%.*]] = and i32 [[X1]], [[X2]]
-; CHECK-NEXT:    [[Z:%.*]] = or i32 [[X3]], 32
-; CHECK-NEXT:    ret i32 [[Z]]
+; CHECK-NEXT:    ret i32 33
 ;
   %x1 = or i32 %x, 129
   %x2 = sub i32 0, %x1
   %x3 = and i32 %x2, %x1
   %z = or i32 %x3, 32
   ret i32 %z
 }
 
;
   ret <2 x i1> %z
 }
 
 define i1 @blsi_ne_is_true_assume(i32 %x) {
 ; CHECK-LABEL: @blsi_ne_is_true_assume(
 ; CHECK-NEXT:    [[LB:%.*]] = and i32 [[X:%.*]], 4
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[LB]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
-; CHECK-NEXT:    [[X2:%.*]] = sub nsw i32 0, [[X]]
-; CHECK-NEXT:    [[X3:%.*]] = and i32 [[X2]], [[X]]
-; CHECK-NEXT:    [[Z:%.*]] = icmp ne i32 [[X3]], 8
-; CHECK-NEXT:    ret i1 [[Z]]
+; CHECK-NEXT:    ret i1 true
 ;
   %lb = and i32 %x, 4
   %cmp = icmp ne i32 %lb, 0
   call void @llvm.assume(i1 %cmp)
   %x2 = sub i32 0, %x
   %x3 = and i32 %x2, %x
   %z = icmp ne i32 %x3, 8
   ret i1 %z
;
   ret <2 x i1> %z
 }
 
 define i32 @blsi_xor_eval_assume(i32 %x) {
 ; CHECK-LABEL: @blsi_xor_eval_assume(
 ; CHECK-NEXT:    [[LB:%.*]] = and i32 [[X:%.*]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[LB]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
-; CHECK-NEXT:    [[X2:%.*]] = sub nsw i32 0, [[X]]
-; CHECK-NEXT:    [[X3:%.*]] = and i32 [[X2]], [[X]]
-; CHECK-NEXT:    [[Z:%.*]] = xor i32 [[X3]], 32
-; CHECK-NEXT:    ret i32 [[Z]]
+; CHECK-NEXT:    ret i32 33
 ;
   %lb = and i32 %x, 1
   %cmp = icmp ne i32 %lb, 0
   call void @llvm.assume(i1 %cmp)
   %x2 = sub i32 0, %x
   %x3 = and i32 %x2, %x
   %z = xor i32 %x3, 32
   ret i32 %z
 }
 
 define i32 @blsi_and_eval_assume(i32 %x) {
 ; CHECK-LABEL: @blsi_and_eval_assume(
 ; CHECK-NEXT:    [[LB:%.*]] = and i32 [[X:%.*]], 8
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[LB]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
-; CHECK-NEXT:    [[X2:%.*]] = sub nsw i32 0, [[X]]
-; CHECK-NEXT:    [[X3:%.*]] = and i32 [[X2]], [[X]]
-; CHECK-NEXT:    [[Z:%.*]] = and i32 [[X3]], 32
-; CHECK-NEXT:    ret i32 [[Z]]
+; CHECK-NEXT:    ret i32 0
 ;
   %lb = and i32 %x, 8
   %cmp = icmp ne i32 %lb, 0
   call void @llvm.assume(i1 %cmp)
   %x2 = sub i32 0, %x
   %x3 = and i32 %x2, %x
   %z = and i32 %x3, 32
   ret i32 %z
;
   ret i32 %z
 }
 
 define i32 @blsmsk_add_no_eval2(i32 %x) {
 ; CHECK-LABEL: @blsmsk_add_no_eval2(
 ; CHECK-NEXT:    [[X1:%.*]] = or i32 [[X:%.*]], 256
 ; CHECK-NEXT:    [[X2:%.*]] = add nsw i32 [[X1]], -1
 ; CHECK-NEXT:    [[X3:%.*]] = xor i32 [[X1]], [[X2]]
-; CHECK-NEXT:    [[Z:%.*]] = add i32 [[X3]], 32
+; CHECK-NEXT:    [[Z:%.*]] = add nuw nsw i32 [[X3]], 32
 ; CHECK-NEXT:    ret i32 [[Z]]
 ;
   %x1 = or i32 %x, 256
   %x2 = sub i32 %x1, 1
   %x3 = xor i32 %x1, %x2
   %z = add i32 %x3, 32
   ret i32 %z
 }
;
   %z = or <2 x i32> %x3, <i32 32, i32 32>
   ret <2 x i32> %z
 }
 
 
 ;; Test that if we have different knowledge about lowbit of X/-X that we select the minimum.
 define i1 @blsi_differing_lowbits(i8 %x) {
 ; CHECK-LABEL: @blsi_differing_lowbits(
-; CHECK-NEXT:    [[Y:%.*]] = or i8 [[X:%.*]], 8
-; CHECK-NEXT:    [[Z:%.*]] = sub nsw i8 0, [[Y]]
+; CHECK-NEXT:    [[Z:%.*]] = sub i8 0, [[X:%.*]]
 ; CHECK-NEXT:    [[LB:%.*]] = and i8 [[Z]], 2
 ; CHECK-NEXT:    [[NE:%.*]] = icmp ne i8 [[LB]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[NE]])
-; CHECK-NEXT:    [[O:%.*]] = and i8 [[Y]], [[Z]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[O]], 4
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %y = or i8 %x, 8
   %z = sub i8 0, %y
   %lb = and i8 %z, 2
   %ne = icmp ne i8 %lb, 0
   call void @llvm.assume(i1 %ne)
   %o = and i8 %z, %y
   %r = icmp eq i8 %o, 4
   ret i1 %r
 }
 
 define i1 @blsi_differing_lowbits2(i8 %x) {
 ; CHECK-LABEL: @blsi_differing_lowbits2(
 ; CHECK-NEXT:    [[Z:%.*]] = sub nsw i8 0, [[X:%.*]]
 ; CHECK-NEXT:    [[LB:%.*]] = and i8 [[Z]], 8
 ; CHECK-NEXT:    [[NE:%.*]] = icmp ne i8 [[LB]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[NE]])
 ; CHECK-NEXT:    [[LB2:%.*]] = and i8 [[X]], 2
 ; CHECK-NEXT:    [[NE2:%.*]] = icmp ne i8 [[LB2]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[NE2]])
-; CHECK-NEXT:    [[O:%.*]] = and i8 [[Z]], [[X]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[O]], 4
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %z = sub i8 0, %x
   %lb = and i8 %z, 8
   %ne = icmp ne i8 %lb, 0
   call void @llvm.assume(i1 %ne)
   %lb2 = and i8 %x, 2
   %ne2 = icmp ne i8 %lb2, 0
   call void @llvm.assume(i1 %ne2)
   %o = and i8 %z, %x
   %r = icmp eq i8 %o, 4
   ret i1 %r
 }

llvm/test/Transforms/InstCombine/ctpop-pow2.ll

;
   %sub = sub <2 x i64> <i64 0 ,i64 0>, %x
   %and = and <2 x i64> %sub, %x
   %cnt = call <2 x i64> @llvm.ctpop.v2i64(<2 x i64> %and)
   ret <2 x i64> %cnt
 }
 
 define <2 x i32> @ctpop_x_and_negx_vec_nz(<2 x i32> %x) {
 ; CHECK-LABEL: @ctpop_x_and_negx_vec_nz(
-; CHECK-NEXT:    ret <2 x i32> <i32 1, i32 1>
+; CHECK-NEXT:    [[X1:%.*]] = or <2 x i32> [[X:%.*]], <i32 1, i32 1>
+; CHECK-NEXT:    [[SUB:%.*]] = sub nsw <2 x i32> zeroinitializer, [[X1]]
+; CHECK-NEXT:    [[AND:%.*]] = and <2 x i32> [[X1]], [[SUB]]
+; CHECK-NEXT:    ret <2 x i32> [[AND]]
 ;
   %x1 = or <2 x i32> %x, <i32 1 ,i32 1>
   %sub = sub <2 x i32> <i32 0 ,i32 0>, %x1
   %and = and <2 x i32> %sub, %x1
   %cnt = call <2 x i32> @llvm.ctpop.v2i32(<2 x i32> %and)
   ret <2 x i32> %cnt
 }

llvm/test/Transforms/InstSimplify/ctpop-pow2.ll

;
   ret i16 %cnt
 }
 
 define i8 @ctpop_x_nz_and_negx(i8 %x) {
 ; CHECK-LABEL: @ctpop_x_nz_and_negx(
 ; CHECK-NEXT:    [[X1:%.*]] = or i8 [[X:%.*]], 1
 ; CHECK-NEXT:    [[V0:%.*]] = sub i8 0, [[X1]]
 ; CHECK-NEXT:    [[V1:%.*]] = and i8 [[X1]], [[V0]]
-; CHECK-NEXT:    [[CNT:%.*]] = call i8 @llvm.ctpop.i8(i8 [[V1]])
-; CHECK-NEXT:    ret i8 [[CNT]]
+; CHECK-NEXT:    ret i8 [[V1]]
 ;
   %x1 = or i8 %x, 1
   %v0 = sub i8 0, %x1
   %v1 = and i8 %x1, %v0
   %cnt = call i8 @llvm.ctpop.i8(i8 %v1)
   ret i8 %cnt
 }