[InstCombine] Introduce fold for icmp pred (and X, (sh signbit, Y)), 0.

[huihuiz]

Summary

Fold:

(X & (signbit l>> Y)) ==/!= 0 -> (X << Y) s>=/s< 0
(X & (signbit << Y)) ==/!= 0 -> (X l>> Y) s>=/s< 0

[huihuiz]

For thumb target, this optimization allow generation of more compacted instructions.
run: clang -mcpu=cortex-m0 -target armv6m-none-eabi icmp-shl-and.ll -O2 -S -o t.s

@ %bb.0:                                @ %entry
        subs    r0, r0, #1
        lsls    r1, r0
        cmp     r1, #0
        blt     .LBB0_2
@ %bb.1:                                @ %entry
        mov     r2, r3
.LBB0_2:                                @ %entry
        mov     r0, r2
        bx      lr

Otherwise will generate more instructions with signmask shifting

@ %bb.0:                                @ %entry
        .save   {r4, lr}
        push    {r4, lr}
        subs    r0, r0, #1
        movs    r4, #1
        lsls    r4, r4, #31
        lsrs    r4, r0
        tst     r4, r1
        beq     .LBB0_2
@ %bb.1:                                @ %entry
        mov     r3, r2
.LBB0_2:                                @ %entry
        mov     r0, r3
        pop     {r4, pc}

ARM and thumb2 target allow flexible second operand, for this case test bit instruction with shift. This optimization does not affect performance of generated instructions.
Run: clang -mcpu=cortex-a53 -target armv8-none-musleabi icmp-shl-and.ll -O2 -S -o t.s

With this optimization

@ %bb.0:                                @ %entry
        sub     r0, r0, #1
        lsl     r0, r1, r0
        cmp     r0, #0
        movge   r2, r3
        mov     r0, r2
        bx      lr

Without this optimization:

@ %bb.0:                                @ %entry
        sub     r12, r0, #1
        mov     r0, #-2147483648
        tst     r1, r0, lsr r12
        moveq   r2, r3
        mov     r0, r2
        bx      lr

[lebedev.ri]

This looks like a missing backend-level transform, either a generic-one in DAGCombiner, or in ARMISelLowering.cpp.

This fix is not the right thing to do because even if you disable this fold,
you can still receive this 'bad' IR you are trying to avoid here,
and will still end up generating bad ASM.

[lebedev.ri]

Though this transform is also bad for X86: https://godbolt.org/z/KFM3gQ
When the C2 << Y isn't being hoisted out of the loop that is of course.

[lebedev.ri]

So we're missing an undo fold: https://rise4fun.com/Alive/w25
Not sure if it should be guarded by a TTI hook, i would expect it to be always beneficial.
(that doesn't mind the original fold is always not beneficial though)
I'll try to take a look.

[efriedma]

On the instcombine side, one thing worth noting which isn't called out in the commit message is the interaction with other instcombine patterns. In the testcase, note that the final IR actually doesn't contain any mask; instead, it checks icmp slt i32 [[SHL]], 0. Huihui, please update the commit message to make this clear.

It's possible we should also implement the related pattern to transform (x & (signbit >> y)) != 0 to (x << y) < 0, sure.

In terms of whether it's universally profitable, I'm not sure... I guess if somehow "icmp ne X, 0" is free, but "icmp slt X, 0" isn't, it could be an issue, but I don't think that applies to any architecture I can think of.

[lebedev.ri]

I'm about to post dagcominer undo-fold, hold on..

In D62818#1528149, @efriedma wrote:

On the instcombine side, one thing worth noting which isn't called out in the commit message is the interaction with other instcombine patterns. In the testcase, note that the final IR actually doesn't contain any mask; instead, it checks icmp slt i32 [[SHL]], 0. Huihui, please update the commit message to make this clear.

It's possible we should also implement the related pattern to transform (x & (signbit >> y)) != 0 to (x << y) < 0, sure.

Yes, now that would be a good patch, +see inline comment.

In terms of whether it's universally profitable, I'm not sure... I guess if somehow "icmp ne X, 0" is free, but "icmp slt X, 0" isn't, it could be an issue, but I don't think that applies to any architecture I can think of.

I think there may or may not bea confusion here. We are in a middle-end here. Other than TTI,
we don't really care about what ever backed/target may find troubling/unprofitable.
We only care about producing most simple IR, that is most suited for further transforms.
That new IR may, or may not, be optimal for any particular target.
If IR is not optimal for back-end, then an opposite transform should be present in backend.

lib/Transforms/InstCombine/InstCombineCompares.cpp

1606–1611 ↗

(On Diff #202749)

There should also be a sibling fold with swapped shift directions

[lebedev.ri]

test/Transforms/InstCombine/icmp-shl-and.ll

12–13 ↗

(On Diff #202749)

Hmm, this already should be folding: https://godbolt.org/z/77mvnv
I guess the order of folds is wrong.

[lebedev.ri]

And posted: D62871

As for the instcombine side,
i guess i would recommend a new differential,
with actual folds, not this blacklisting.

[huihuiz]

The other approach could be changing the order of folding. Move foldICmpBinOpEqualityWithConstant to the very beginning of foldICmpInstWithConstant.
foldICmpBinOpEqualityWithConstant has rules to replace (and X, (1 << size(X)-1) != 0) with x s< 0.
Let me know if this approach is more preferable?

[lebedev.ri]

In D62818#1529921, @huihuiz wrote:

The other approach could be changing the order of folding. Move foldICmpBinOpEqualityWithConstant to the very beginning of foldICmpInstWithConstant.
foldICmpBinOpEqualityWithConstant has rules to replace (and X, (1 << size(X)-1) != 0) with x s< 0.
Let me know if this approach is more preferable?

You want (1+1*2)*2 = 6 folds: https://rise4fun.com/Alive/Y8Ct

[huihuiz]

Yes , changing the order would allow these folds.

(X & (signbit >> Y)) != 0  ->  (X << Y) s< 0
(X & (signbit >> Y)) == 0  ->  (X << Y) >= 0
((X << Y) & signbit) != 0  ->  (X << Y) s< 0
((X << Y) & signbit) == 0  ->  (X << Y) >= 0

[lebedev.ri]

lib/Transforms/InstCombine/InstCombineCompares.cpp

1762–1778 ↗

(On Diff #203024)

Eww, this looks too much like backend pattern matching :)
Here you want something more like

// (V0 & (signbit l>> V1)) ==/!= 0 -> (V0 << V1) >=/< 0
// (V0 & (signbit << V1)) ==/!= 0 -> (V0 l>> V1) >=/< 0
Value *V0, *V1, *Shift, *Zero;
ICmpInst::Predicate Pred;
if (match(&Cmp,
          m_ICmp(Pred,
                 m_OneUse(m_c_And(
                     m_CombineAnd(
                         m_CombineAnd(m_Shift(m_SignMask(), m_Value(V1)),
                                      m_Value(Shift)),
                         m_CombineOr(m_Shl(m_Value(), m_Value()),
                                     m_LShr(m_Value(), m_Value()))),
                     m_Value(V0))),
                 m_CombineAnd(m_Zero(), m_Value(Zero)))) &&
    Cmp.isEquality(Pred)) {
  Value *NewShift = cast<Instruction>(Shift)->getOpcode() == Instruction::LShr
                        ? Builder.CreateShl(V0, V1)
                        : Builder.CreateLShr(V0, V1);
  ICmpInst::Predicate NewPred =
      Pred == CmpInst::ICMP_EQ ? CmpInst::ICMP_SGE : CmpInst::ICMP_SLT;
  return new ICmpInst(NewPred, NewShift, Zero);
}

[lebedev.ri]

lib/Transforms/InstCombine/InstCombineCompares.cpp

2664–2666 ↗

(On Diff #203024)

I'm not looking forward seeing the fallout of this move.
I will be extremely surprised if, while fixing the target problem,
this won't expose numerous other fold order issues.

Can you instead simply follow the TODO, and simply refactor the single interesting fold
out of foldICmpBinOpEqualityWithConstant() into foldICmpAndConstant() i guess?

[huihuiz]

Test cases in icmp-shift-and-signbit.ll shows the updated fold order can generate better IR.

[lebedev.ri]

Nice, getting closer.
Could you please split this up:

1. A patch that adds your original motivational testcase that shows that the fold order is wrong.
2. The move of the // Replace (and X, (1 << size(X)-1) != 0) with x s< 0 fold
3. A patch with just new test/Transforms/InstCombine/icmp-shift-and-signbit.ll
4. The fold itself, showing the changes to the check lines

lib/Transforms/InstCombine/InstCombineCompares.cpp

1646 ↗

(On Diff #203284)

Here the codegen is irrelevant.
We do this because it results in simpler IR.
Not sure if that new comment adds anything useful

1660 ↗

(On Diff #203284)

C2->negate().isPowerOf2()

2791–2792 ↗

(On Diff #203284)

Uhm, where did this check that we were comparing with 0?

test/Transforms/InstCombine/icmp-shift-and-signbit.ll

2 ↗

(On Diff #203284)

Please

1. Move this to a new differential
2. In that same patch, re-add your initial motivational pattern, that shows that fold reordering did something
3. Use llvm/utils/update_test_checks.py to generate check lines
4. Rebase *this* diff ontop of that new patch, so this diff shows how the check lines change

13 ↗

(On Diff #203284)

select is not relevant for this pattern, drop it

68 ↗

(On Diff #203284)

You also want a few extra tests:

1. A trivial vector test with <i32 -2147483648, i32 -2147483648> and <i32 0, i32 0>
2. 3 vector tests with undefs:
   • <i32 -2147483648, i32 undef, i32 -2147483648> and <i32 0, i32 0, i32 0>
   • <i32 -2147483648, i32 -2147483648, i32 -2147483648> and <i32 0, i32 undef, i32 0>
   • <i32 -2147483648, i32 undef, i32 -2147483648> and <i32 0, i32 undef, i32 0>
3. A tests to verify single-use constraints:
   • a test with extra use on %shr (should get folded, but not others)
   • a test with extra use on %and
   • a test with extra use on %shr and %and.
     
     How to introduce extra uses see e.g. llvm/test/Transforms/InstCombine/unfold-masked-merge-with-const-mask-scalar.ll

test/Transforms/InstCombine/pr17827.ll

66 ↗

(On Diff #203284)

These don't look like improvements to me.
Looks like that reordering exposes yet another missing fold.

[huihuiz]

Thank you so much for all the review feedback, really appreciate it! :)

lib/Transforms/InstCombine/InstCombineCompares.cpp

1660 ↗

(On Diff #203284)

Should not call C2->negate()
If C2 negate is not power of 2, then calling negate() will replace C2 with C2 negate.
C2 should not be modified.

2791–2792 ↗

(On Diff #203284)

What happened was, C being 0, signbit, other number

1. we are ok with 0

2. if C is signbit, consider test: X & signbit == signbit

fold:
X & -C == -C -> X > u ~C
X & -C != -C -> X <= u ~C
and fold:
For i32: x >u 2147483647 -> x <s 0 -> true if sign bit set

are scheduled before
fold: (and X, (1 << size(X)-1) != 0) with x s< 0

3. if C is other number, SimplifyICmpInst will do its job

test/Transforms/InstCombine/pr17827.ll

66 ↗

(On Diff #203284)

in D63026
I am moving fold ((X & ~7) == 0) --> X < 8 ahead.

If X is (BinOp Y, C3), should allow other rules to fold C3 with C2,
eg (X >> C3) & C2 != C1 -> (X & (C2 << C3)) != (C1 << C3)

[huihuiz]

D62818 is now split into D63025 , D63026 , D63028 and D62818

[xbolva00]

More signum, sgn patterns
https://godbolt.org/z/tE00f4

[huihuiz]

In D62818#1534806, @xbolva00 wrote:

More signum, sgn patterns
https://godbolt.org/z/tE00f4

Hey @xbolva00 , I don't see there is much difference between codegen of x86-clang and x86-gcc.
Let's focus on the missing folds we are trying to resolve here:

(X & (signbit l>> Y)) ==/!= 0 -> (X << Y) >=/< 0
(X & (signbit << Y)) ==/!= 0 -> (X l>> Y) >=/< 0

and fold order issue of

((X << Y) & signbit) ==/!= 0) -> (X << Y) >=/< 0;
(X << Y) & ~C ==/!= 0 -> (X << Y) </>= C+1, C+1 is power of 2;
and
((X << Y) & C) == 0 -> (X & (C >> Y)) == 0.

[lebedev.ri]

Oh, i thought i commented on these reviews, apparently not :(
I still see random changes to test coverage (new tests being added) in an non-nfc patches.
Let me rephrase: can you put all the test updates, new tests into *ONE* review, and the rest of the patches should not add new/change existing tests?

[huihuiz]

Original test cases are added in D63025 . Hopefully would be good coverage :)
D63026 fix fold order issue
this differential introduce new fold for icmp pred (and X, (sh signbit, Y)), 0

[lebedev.ri]

Is this the only remaining patch?
I don't think i should review my own code, perhaps @spatel can take a look?

lib/Transforms/InstCombine/InstCombineCompares.cpp

1796 ↗

(On Diff #204436)

I'm not sure why i have added m_OneUse() here, it should not be here.

[spatel]

lib/Transforms/InstCombine/InstCombineCompares.cpp

1792–1795 ↗

(On Diff #204436)

m_LogicalShift() ?

test/Transforms/InstCombine/signbit-shl-and-icmpeq-zero.ll

180 ↗

(On Diff #204436)

I didn't step through the transforms, but it seems wrong to call this a 'negative test'. This patch must have fired and allowed further simplification?

[huihuiz]

I simplify the code for pattern matching, more readable.

[huihuiz]

lib/Transforms/InstCombine/InstCombineCompares.cpp

1796 ↗

(On Diff #204436)

I agree that m_OneUse() should not be in the pattern matching. V0 might be constant value, which will have more than one use outside of its current function.

Actually I added, not you, sorry about that.

There is a regression, see test file: test/Transforms/InstCombine/onehot_merge.ll

define i1 @foo1_and(i32 %k, i32 %c1, i32 %c2) {
bb:
  %tmp = shl i32 1, %c1
  %tmp4 = lshr i32 -2147483648, %c2
  %tmp1 = and i32 %tmp, %k
  %tmp2 = icmp eq i32 %tmp1, 0
  %tmp5 = and i32 %tmp4, %k
  %tmp6 = icmp eq i32 %tmp5, 0
  %or = or i1 %tmp2, %tmp6
  ret i1 %or
}

failed to fold
(iszero(A&K1) | iszero(A&K2)) -> (A&(K1|K2)) != (K1|K2) , where K1 and K2 are 'one-hot' (only one bit is on).
Here K1 is one, K2 is signbit.

I am still thinking how to get over this regression.

test/Transforms/InstCombine/signbit-shl-and-icmpeq-zero.ll

180 ↗

(On Diff #204436)

Yes, X being constant is positive case. Fold happened, and allowed further simplification.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1806–1808

m_Value(V0) will always match, it's best to swap them.

llvm/test/Transforms/InstCombine/onehot_merge.ll

17–18

Can you please regenerate the original test?

17–18

I'm not sure what's on the LHS of the diff, but ignoring the instruction count this looks like improvement to me.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1801–1802

// (V0 & (signbit l>> V1)) ==/!= 0 -> (V0 << V1) s>=/s< 0
// (V0 & (signbit << V1)) ==/!= 0 -> (V0 l>> V1) s>=/s< 0

llvm/test/Transforms/InstCombine/onehot_merge.ll

17–18

AH, you also want to str-replace %tmp with %t, it confuses the update script likely.

[spatel]

llvm/test/Transforms/InstCombine/onehot_merge.ll

17–18

rL364546

[huihuiz]

Rebased patch, and addressed review comments.

llvm/test/Transforms/InstCombine/onehot_merge.ll

17–18

Actually we missed the fold for

((k & ( 1 l<< C1 )) == 0) || ((k & ( signbit l>> C2 )) == 0)
-->
((k & (( 1 l<< C1 ) || ( signbit l>> C2 ))) != 0)

[lebedev.ri]

llvm/test/Transforms/InstCombine/onehot_merge.ll

17–18

Thanks for the analysis!
@spatel does this fall into the nowadays reasoning that we shouldn't be doing too much folds into bitmath
here in instcombine? I'm almost tempted to say that this isn't a regression,
but the original fold that now no longer happens should be removed instead.

[huihuiz]

for onehot_merge.ll
mathematically speaking

(signbit l>> C)

is equivalent to

(one l<< (bitwidth - C - 1))

In D63903, I update the test input, so that we are still checking fold for 'or' of ICmps and 'and' of ICmps.

[spatel]

llvm/test/Transforms/InstCombine/onehot_merge.ll

17–18

If we say that the longer IR sequence is more canonical, then we'd want to add a transform to create that longer sequence starting from the shorter sequence. Are we willing to do that to improve analysis in IR?

As a practical matter, we probably also want to look at asm output for the alternatives on a few targets to see how much backend logic is required to do/undo this.

[spatel]

llvm/test/Transforms/InstCombine/onehot_merge.ll

17–18

Sorry - I haven't followed this patch and its friends closely; scrolling back through the comments, I think the backend questions are covered by D62871.

[lebedev.ri]

This isn't specific to sign bit, the more general pattern is https://rise4fun.com/Alive/2zpl
I'm apparently working on it..

[lebedev.ri]

llvm/test/Transforms/InstCombine/onehot_merge.ll

115–122

Looks like to support this pattern, InstCombiner::foldAndOrOfICmpsOfAndWithPow2() will need to be generalized.

[huihuiz]

llvm/test/Transforms/InstCombine/onehot_merge.ll

115–122

I am looking into this, hold on.

[huihuiz]

Generalize InstCombiner::foldAndOrOfICmpsOfAndWithPow2() in D64275

[lebedev.ri]

This review seems to be stuck/dead, consider abandoning if no longer relevant.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

if (ExactLogBase2 != -1 && DL.isLegalInteger(ExactLogBase2 + 1)) {
         NTy = VectorType::get(NTy, And->getType()->getVectorNumElements());
       Value *Trunc = Builder.CreateTrunc(X, NTy);
       auto NewPred = Cmp.getPredicate() == CmpInst::ICMP_EQ ? CmpInst::ICMP_SGE
                                                             : CmpInst::ICMP_SLT;
       return new ICmpInst(NewPred, Trunc, Constant::getNullValue(NTy));
     }
   }
 
+  // (V0 & (signbit l>> V1)) ==/!= 0 -> (V0 << V1) s>=/s< 0
+  // (V0 & (signbit << V1)) ==/!= 0 -> (V0 l>> V1) s>=/s< 0
+  Value *V0, *V1, *Shift;
+  if (C.isNullValue() &&
+      match(And, m_OneUse(m_c_And(
+                     m_CombineAnd(m_LogicalShift(m_SignMask(), m_Value(V1)),
+                                  m_Value(Shift)),
+                     m_Value(V0))))) {
+    Value *NewShift = cast<Instruction>(Shift)->getOpcode() == Instruction::LShr
+                          ? Builder.CreateShl(V0, V1)
+                          : Builder.CreateLShr(V0, V1);
+    return new ICmpInst(Cmp.getPredicate() == CmpInst::ICMP_EQ
+                            ? ICmpInst::ICMP_SGE
+                            : ICmpInst::ICMP_SLT,
+                        NewShift, Cmp.getOperand(1));
+  }
+
   return nullptr;
 }
 
 /// Fold icmp (or X, Y), C.
 Instruction *InstCombiner::foldICmpOrConstant(ICmpInst &Cmp, BinaryOperator *Or,
                                               const APInt &C) {
   ICmpInst::Predicate Pred = Cmp.getPredicate();
   if (C.isOneValue()) {

llvm/test/Transforms/InstCombine/onehot_merge.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 define i1 @and_consts(i32 %k, i32 %c1, i32 %c2) {
 ; CHECK-LABEL: @and_consts(
 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[K:%.*]], 12
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i32 [[TMP1]], 12
 ; CHECK-NEXT:    ret i1 [[TMP2]]
 ;
   %t1 = and i32 4, %k
   %t2 = icmp eq i32 %t1, 0
   %t5 = and i32 8, %k
   %t6 = icmp eq i32 %t5, 0
   %or = or i1 %t2, %t6
   ret i1 %or
 }
 
 define i1 @foo1_and(i32 %k, i32 %c1, i32 %c2) {
 ; CHECK-LABEL: @foo1_and(
 ; CHECK-NEXT:    [[T:%.*]] = shl i32 1, [[C1:%.*]]
 ; CHECK-NEXT:    [[T4:%.*]] = shl i32 1, [[C2:%.*]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[T]], [[T4]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[K:%.*]]
 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[TMP2]], [[TMP1]]
 ; CHECK-NEXT:    ret i1 [[TMP3]]
 ;
;
   %t2 = icmp ne i32 %t1, 0
   %t5 = and i32 %t4, %k2
   %t6 = icmp ne i32 %t5, 0
   %or = and i1 %t2, %t6
   ret i1 %or
 }
 
 define i1 @foo1_and_signbit_lshr(i32 %k, i32 %c1, i32 %c2) {
 ; CHECK-LABEL: @foo1_and_signbit_lshr(
 ; CHECK-NEXT:    [[T:%.*]] = shl i32 1, [[C1:%.*]]
-; CHECK-NEXT:    [[T4:%.*]] = lshr i32 -2147483648, [[C2:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[T]], [[T4]]
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[K:%.*]]
-; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[TMP2]], [[TMP1]]
-; CHECK-NEXT:    ret i1 [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 -2147483648, [[C2:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[T]], [[TMP1]]
+; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[TMP2]], [[K:%.*]]
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp ne i32 [[TMP3]], [[TMP2]]
+; CHECK-NEXT:    ret i1 [[TMP4]]
 ;
   %t = shl i32 1, %c1
   %t4 = lshr i32 -2147483648, %c2
   %t1 = and i32 %t, %k
   %t2 = icmp eq i32 %t1, 0
   %t5 = and i32 %t4, %k
   %t6 = icmp eq i32 %t5, 0
   %or = or i1 %t2, %t6
   ret i1 %or
 }
 
 define i1 @foo1_or_signbit_lshr(i32 %k, i32 %c1, i32 %c2) {
 ; CHECK-LABEL: @foo1_or_signbit_lshr(
 ; CHECK-NEXT:    [[T:%.*]] = shl i32 1, [[C1:%.*]]
-; CHECK-NEXT:    [[T4:%.*]] = lshr i32 -2147483648, [[C2:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[T]], [[T4]]
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[K:%.*]]
-; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[TMP2]], [[TMP1]]
-; CHECK-NEXT:    ret i1 [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 -2147483648, [[C2:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[T]], [[TMP1]]
+; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[TMP2]], [[K:%.*]]
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i32 [[TMP3]], [[TMP2]]
+; CHECK-NEXT:    ret i1 [[TMP4]]
 ;
   %t = shl i32 1, %c1
   %t4 = lshr i32 -2147483648, %c2
   %t1 = and i32 %t, %k
   %t2 = icmp ne i32 %t1, 0
   %t5 = and i32 %t4, %k
   %t6 = icmp ne i32 %t5, 0
   %or = and i1 %t2, %t6

llvm/test/Transforms/InstCombine/signbit-lshr-and-icmpeq-zero.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt %s -instcombine -S | FileCheck %s
 
 ; For pattern (X & (signbit l>> Y)) ==/!= 0
 ; it may be optimal to fold into (X << Y) >=/< 0
 
 ; Scalar tests
 
 define i1 @scalar_i8_signbit_lshr_and_eq(i8 %x, i8 %y) {
 ; CHECK-LABEL: @scalar_i8_signbit_lshr_and_eq(
-; CHECK-NEXT:    [[LSHR:%.*]] = lshr i8 -128, [[Y:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[LSHR]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[AND]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i8 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt i8 [[TMP1]], -1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %lshr = lshr i8 128, %y
   %and = and i8 %lshr, %x
   %r = icmp eq i8 %and, 0
   ret i1 %r
 }
 
 define i1 @scalar_i16_signbit_lshr_and_eq(i16 %x, i16 %y) {
 ; CHECK-LABEL: @scalar_i16_signbit_lshr_and_eq(
-; CHECK-NEXT:    [[LSHR:%.*]] = lshr i16 -32768, [[Y:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = and i16 [[LSHR]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i16 [[AND]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i16 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt i16 [[TMP1]], -1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %lshr = lshr i16 32768, %y
   %and = and i16 %lshr, %x
   %r = icmp eq i16 %and, 0
   ret i1 %r
 }
 
 define i1 @scalar_i32_signbit_lshr_and_eq(i32 %x, i32 %y) {
 ; CHECK-LABEL: @scalar_i32_signbit_lshr_and_eq(
-; CHECK-NEXT:    [[LSHR:%.*]] = lshr i32 -2147483648, [[Y:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[LSHR]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i32 [[AND]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt i32 [[TMP1]], -1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %lshr = lshr i32 2147483648, %y
   %and = and i32 %lshr, %x
   %r = icmp eq i32 %and, 0
   ret i1 %r
 }
 
 define i1 @scalar_i64_signbit_lshr_and_eq(i64 %x, i64 %y) {
 ; CHECK-LABEL: @scalar_i64_signbit_lshr_and_eq(
-; CHECK-NEXT:    [[LSHR:%.*]] = lshr i64 -9223372036854775808, [[Y:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = and i64 [[LSHR]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i64 [[AND]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i64 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt i64 [[TMP1]], -1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %lshr = lshr i64 9223372036854775808, %y
   %and = and i64 %lshr, %x
   %r = icmp eq i64 %and, 0
   ret i1 %r
 }
 
 define i1 @scalar_i32_signbit_lshr_and_ne(i32 %x, i32 %y) {
 ; CHECK-LABEL: @scalar_i32_signbit_lshr_and_ne(
-; CHECK-NEXT:    [[LSHR:%.*]] = lshr i32 -2147483648, [[Y:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[LSHR]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ne i32 [[AND]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp slt i32 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %lshr = lshr i32 2147483648, %y
   %and = and i32 %lshr, %x
   %r = icmp ne i32 %and, 0  ; check 'ne' predicate
   ret i1 %r
 }
 
 ; Vector tests
 
 define <4 x i1> @vec_4xi32_signbit_lshr_and_eq(<4 x i32> %x, <4 x i32> %y) {
 ; CHECK-LABEL: @vec_4xi32_signbit_lshr_and_eq(
-; CHECK-NEXT:    [[LSHR:%.*]] = lshr <4 x i32> <i32 -2147483648, i32 -2147483648, i32 -2147483648, i32 -2147483648>, [[Y:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = and <4 x i32> [[LSHR]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq <4 x i32> [[AND]], zeroinitializer
+; CHECK-NEXT:    [[TMP1:%.*]] = shl <4 x i32> [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt <4 x i32> [[TMP1]], <i32 -1, i32 -1, i32 -1, i32 -1>
 ; CHECK-NEXT:    ret <4 x i1> [[R]]
 ;
   %lshr = lshr <4 x i32> <i32 2147483648, i32 2147483648, i32 2147483648, i32 2147483648>, %y
   %and = and <4 x i32> %lshr, %x
   %r = icmp eq <4 x i32> %and, <i32 0, i32 0, i32 0, i32 0>
   ret <4 x i1> %r
 }
 

 ; Extra use
 
 ; Fold happened
 define i1 @scalar_i32_signbit_lshr_and_eq_extra_use_lshr(i32 %x, i32 %y, i32 %z, i32* %p) {
 ; CHECK-LABEL: @scalar_i32_signbit_lshr_and_eq_extra_use_lshr(
 ; CHECK-NEXT:    [[LSHR:%.*]] = lshr i32 -2147483648, [[Y:%.*]]
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[LSHR]], [[Z:%.*]]
 ; CHECK-NEXT:    store i32 [[XOR]], i32* [[P:%.*]], align 4
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[LSHR]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i32 [[AND]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[X:%.*]], [[Y]]
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt i32 [[TMP1]], -1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %lshr = lshr i32 2147483648, %y
   %xor = xor i32 %lshr, %z  ; extra use of lshr
   store i32 %xor, i32* %p
   %and = and i32 %lshr, %x
   %r = icmp eq i32 %and, 0
   ret i1 %r
;
   %r = icmp eq i32 %and, 0
   ret i1 %r
 }
 
 ; X is constant
 
 define i1 @scalar_i32_signbit_lshr_and_eq_X_is_constant1(i32 %y) {
 ; CHECK-LABEL: @scalar_i32_signbit_lshr_and_eq_X_is_constant1(
-; CHECK-NEXT:    [[LSHR:%.*]] = lshr i32 -2147483648, [[Y:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[LSHR]], 12345
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i32 [[AND]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 12345, [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt i32 [[TMP1]], -1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %lshr = lshr i32 2147483648, %y
   %and = and i32 %lshr, 12345
   %r = icmp eq i32 %and, 0
   ret i1 %r
 }
 

llvm/test/Transforms/InstCombine/signbit-shl-and-icmpeq-zero.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt %s -instcombine -S | FileCheck %s
 
 ; For pattern (X & (signbit << Y)) ==/!= 0
 ; it may be optimal to fold into (X l>> Y) >=/< 0
 
 ; Scalar tests
 
 define i1 @scalar_i8_signbit_shl_and_eq(i8 %x, i8 %y) {
 ; CHECK-LABEL: @scalar_i8_signbit_shl_and_eq(
-; CHECK-NEXT:    [[SHL:%.*]] = shl i8 -128, [[Y:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[SHL]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[AND]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i8 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt i8 [[TMP1]], -1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %shl = shl i8 128, %y
   %and = and i8 %shl, %x
   %r = icmp eq i8 %and, 0
   ret i1 %r
 }
 
 define i1 @scalar_i16_signbit_shl_and_eq(i16 %x, i16 %y) {
 ; CHECK-LABEL: @scalar_i16_signbit_shl_and_eq(
-; CHECK-NEXT:    [[SHL:%.*]] = shl i16 -32768, [[Y:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = and i16 [[SHL]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i16 [[AND]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i16 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt i16 [[TMP1]], -1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %shl = shl i16 32768, %y
   %and = and i16 %shl, %x
   %r = icmp eq i16 %and, 0
   ret i1 %r
 }
 
 define i1 @scalar_i32_signbit_shl_and_eq(i32 %x, i32 %y) {
 ; CHECK-LABEL: @scalar_i32_signbit_shl_and_eq(
-; CHECK-NEXT:    [[SHL:%.*]] = shl i32 -2147483648, [[Y:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[SHL]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i32 [[AND]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt i32 [[TMP1]], -1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %shl = shl i32 2147483648, %y
   %and = and i32 %shl, %x
   %r = icmp eq i32 %and, 0
   ret i1 %r
 }
 
 define i1 @scalar_i64_signbit_shl_and_eq(i64 %x, i64 %y) {
 ; CHECK-LABEL: @scalar_i64_signbit_shl_and_eq(
-; CHECK-NEXT:    [[SHL:%.*]] = shl i64 -9223372036854775808, [[Y:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = and i64 [[SHL]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i64 [[AND]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i64 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt i64 [[TMP1]], -1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %shl = shl i64 9223372036854775808, %y
   %and = and i64 %shl, %x
   %r = icmp eq i64 %and, 0
   ret i1 %r
 }
 
 define i1 @scalar_i32_signbit_shl_and_ne(i32 %x, i32 %y) {
 ; CHECK-LABEL: @scalar_i32_signbit_shl_and_ne(
-; CHECK-NEXT:    [[SHL:%.*]] = shl i32 -2147483648, [[Y:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[SHL]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ne i32 [[AND]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp slt i32 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %shl = shl i32 2147483648, %y
   %and = and i32 %shl, %x
   %r = icmp ne i32 %and, 0  ; check 'ne' predicate
   ret i1 %r
 }
 
 ; Vector tests
 
 define <4 x i1> @vec_4xi32_signbit_shl_and_eq(<4 x i32> %x, <4 x i32> %y) {
 ; CHECK-LABEL: @vec_4xi32_signbit_shl_and_eq(
-; CHECK-NEXT:    [[SHL:%.*]] = shl <4 x i32> <i32 -2147483648, i32 -2147483648, i32 -2147483648, i32 -2147483648>, [[Y:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = and <4 x i32> [[SHL]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq <4 x i32> [[AND]], zeroinitializer
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr <4 x i32> [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt <4 x i32> [[TMP1]], <i32 -1, i32 -1, i32 -1, i32 -1>
 ; CHECK-NEXT:    ret <4 x i1> [[R]]
 ;
   %shl = shl <4 x i32> <i32 2147483648, i32 2147483648, i32 2147483648, i32 2147483648>, %y
   %and = and <4 x i32> %shl, %x
   %r = icmp eq <4 x i32> %and, <i32 0, i32 0, i32 0, i32 0>
   ret <4 x i1> %r
 }
 

 ; Extra use
 
 ; Fold happened
 define i1 @scalar_i32_signbit_shl_and_eq_extra_use_shl(i32 %x, i32 %y, i32 %z, i32* %p) {
 ; CHECK-LABEL: @scalar_i32_signbit_shl_and_eq_extra_use_shl(
 ; CHECK-NEXT:    [[SHL:%.*]] = shl i32 -2147483648, [[Y:%.*]]
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[SHL]], [[Z:%.*]]
 ; CHECK-NEXT:    store i32 [[XOR]], i32* [[P:%.*]], align 4
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[SHL]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i32 [[AND]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[X:%.*]], [[Y]]
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt i32 [[TMP1]], -1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %shl = shl i32 2147483648, %y
   %xor = xor i32 %shl, %z  ; extra use of shl
   store i32 %xor, i32* %p
   %and = and i32 %shl, %x
   %r = icmp eq i32 %and, 0
   ret i1 %r
;
   %r = icmp eq i32 %and, 0
   ret i1 %r
 }
 
 ; X is constant
 
 define i1 @scalar_i32_signbit_shl_and_eq_X_is_constant1(i32 %y) {
 ; CHECK-LABEL: @scalar_i32_signbit_shl_and_eq_X_is_constant1(
-; CHECK-NEXT:    [[SHL:%.*]] = shl i32 -2147483648, [[Y:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[SHL]], 12345
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i32 [[AND]], 0
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 true
 ;
   %shl = shl i32 2147483648, %y
   %and = and i32 %shl, 12345
   %r = icmp eq i32 %and, 0
   ret i1 %r
 }
 
 define i1 @scalar_i32_signbit_shl_and_eq_X_is_constant2(i32 %y) {
 ; CHECK-LABEL: @scalar_i32_signbit_shl_and_eq_X_is_constant2(
-; CHECK-NEXT:    [[SHL:%.*]] = shl i32 -2147483648, [[Y:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[SHL]], 1
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i32 [[AND]], 0
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 true
 ;
   %shl = shl i32 2147483648, %y
   %and = and i32 %shl, 1
   %r = icmp eq i32 %and, 0
   ret i1 %r
 }
 
 ; Negative tests