[InstCombine] Optimise shift+and+boolean conversion pattern to simple comparison

[bcl5980]

Summary

if (C1 is pow2) & ((C2 & ~(C1-1)) + C1) is pow2):

((C1 << X) & C2) == 0 -> X >= (Log2(C2+C1) - Log2(C1));

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

((C1 << X) & C2) != 0 -> X  < (Log2(C2+C1) - Log2(C1));

https://alive2.llvm.org/ce/z/3bVRVz

And remove dead code.

Fix: https://github.com/llvm/llvm-project/issues/56124

[bcl5980]

update the test result after code change.
Will land test baseline after test also be reviewed.

[spatel]

This patch is not sufficient to solve the bug in general. The IR for the bug report does not contain any icmp, so we can write alternate forms of the source from that bug report and fail to optimize again (and gcc may fail to canonicalize):
https://godbolt.org/z/n9oaWTa8s

Either we need to convert the IR to cmp+select or make this a codegen optimization.

I'm not sure what impact this will have in IR, but you could try to write transforms like this in instcombine and see if that exposes other problems:
https://alive2.llvm.org/ce/z/jA_tNb

[bcl5980]

I'm also worry if we should canonicalize shift+and to icmp+select

I'm not sure what impact this will have in IR, but you could try to write transforms like this in instcombine and see if that exposes other problems:
https://alive2.llvm.org/ce/z/jA_tNb

So can we write transforms below to fix this issue?:
https://alive2.llvm.org/ce/z/DiF6Wo
https://alive2.llvm.org/ce/z/nQtvt5

[spatel]

In D126591#3544029, @bcl5980 wrote:

So can we write transforms below to fix this issue?:
https://alive2.llvm.org/ce/z/DiF6Wo
https://alive2.llvm.org/ce/z/nQtvt5

Yes, it is worth trying. After you create those, run tests (ninja check at least and possibly test-suite) and see if it uncovers any regressions. Also, check the assembly output for each of those patterns and verify that most in-tree targets (x86, AArch/ARM, riscv) show improvements.

[bcl5980]

update shift+lshr+and transform

[bcl5980]

55739_x86.s4 KBDownload

55739_x86_orig.s5 KBDownload

55739_powerpc_orig.s5 KBDownload

55739_aarch64.s4 KBDownload

55739_powerpc.s5 KBDownload

55739_riscv.s2 KBDownload

55739.cpp739 BDownload

55739_aarch64_orig.s4 KBDownload

55739_riscv_orig.s2 KBDownload

[spatel]

Codegen looks better in all cases that I checked, so that's good. And I'm assuming there are no existing regressions on tests.

But this is really 3-4 independent patches together now. Please split it up for easier review and less risk.

I'd start with the 'shift+and' transforms: please add tests where the intermediate values have extra uses and commit those with baseline results. Then post those as new reviews with the corresponding Alive2 proofs, so we have the correctness check for each transform.

[bcl5980]

In D126591#3544495, @spatel wrote:

Codegen looks better in all cases that I checked, so that's good. And I'm assuming there are no existing regressions on tests.

But this is really 3-4 independent patches together now. Please split it up for easier review and less risk.

I'd start with the 'shift+and' transforms: please add tests where the intermediate values have extra uses and commit those with baseline results. Then post those as new reviews with the corresponding Alive2 proofs, so we have the correctness check for each transform.

I'm sorry but I have a question about the ninja check. What is difference between pre-merge checks and local ninja check test? I try to test local but a lot of test failures on bolt, clang, lld. There is no IR failure.

[bcl5980]

1. remove shift+lshr+and pattern
2. update second pattern to make it more general

[spatel]

In D126591#3544585, @bcl5980 wrote:

I'm sorry but I have a question about the ninja check. What is difference between pre-merge checks and local ninja check test? I try to test local but a lot of test failures on bolt, clang, lld. There is no IR failure.

The pre-merge checks are probably running more/different tests on a variety of targets.

I'm not sure how reliable those results are. You can see similar failures for seemingly unrelated patches like D126638.

It is not necessary to pass all pre-merge tests before committing a patch - I think it is still experimental. If the failure is real, then bots and their owners will definitely let you know after you commit.

[bcl5980]

In D126591#3545542, @spatel wrote:

In D126591#3544585, @bcl5980 wrote:

I'm sorry but I have a question about the ninja check. What is difference between pre-merge checks and local ninja check test? I try to test local but a lot of test failures on bolt, clang, lld. There is no IR failure.

The pre-merge checks are probably running more/different tests on a variety of targets.

I'm not sure how reliable those results are. You can see similar failures for seemingly unrelated patches like D126638.

It is not necessary to pass all pre-merge tests before committing a patch - I think it is still experimental. If the failure is real, then bots and their owners will definitely let you know after you commit.

Thanks for the explaination.
One other question for this change itself:
D126617 can fix below two cases also

iff (C1 is pow2) & (C2 is pow2) & (C1 <= C2):
((C1 << X) & C2) == 0 -> X != (Log2(C2) - Log2(C1)); https://alive2.llvm.org/ce/z/SVtcJM
((C1 << X) & C2) != 0 -> X == (Log2(C2) - Log2(C1)); https://alive2.llvm.org/ce/z/eLzTjS

iff (C1 is pow2) & (C2 is pow2):
((C1 >>u X) & C2) == 0 -> X != (Log2(C1) - Log2(C2)); https://alive2.llvm.org/ce/z/9p362A
((C1 >>u X) & C2) != 0 -> X == (Log2(C1) - Log2(C2)); https://alive2.llvm.org/ce/z/FsiU-A

Should I only keep this pattern in this differential?

iff (C1 is pow2) & ((C2 & ~(C1-1)) + C1) is pow2) & (C1 < C2):
((C1 << X) & C2) == 0 -> X >= (Log2(C2+C1) - Log2(C1)); https://alive2.llvm.org/ce/z/JQYFnn
((C1 << X) & C2) != 0 -> X  < (Log2(C2+C1) - Log2(C1)); https://alive2.llvm.org/ce/z/BnyEmk

[bcl5980]

rebase code
remove lshr case as it can handled by rGa0c3c60728ee

[bcl5980]

coding style update

[bcl5980]

remove C1 < C2

[spatel]

I added a similar fold here:
0399473de886

It seems like we might be missing some generalization for power-of-2 values, but this patch seems fine. Please add alive2 links to the patch summary (these are in issue #56124?).

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

5546–5547

Is this just a special-case of the next pattern? If so, I think it is better to reduce the patch. We might have slightly less efficiency at run-time, but there's less code to maintain here.

[bcl5980]

In D126591#3596021, @spatel wrote:

I added a similar fold here:
0399473de886

It seems like we might be missing some generalization for power-of-2 values, but this patch seems fine. Please add alive2 links to the patch summary (these are in issue #56124?).

alive2 link should already in the summary.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

5546–5547

I think it is not. But we can remove that after rGbfde861.
And we can also remove line 5590's transform after rGa0c3c607.
Do we need to remvoe these on this patch?

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

5546–5547

Yes, I prefer to remove code if we have other transforms to handle the patterns now. We do not want to keep dead code around - it makes the compiler slower and harder to understand.

[bcl5980]

remove dead code

[spatel]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (match(Op0, m_OneUse(m_BinOp(BO))) && isSuitableBinOpcode(BO)) {
         Value *BinOp = isa<ZExtInst>(BO->getOperand(0))
                            ? Builder.CreateBinOp(BO->getOpcode(), X, TruncC1)
                            : Builder.CreateBinOp(BO->getOpcode(), TruncC1, X);
         Constant *TruncC = ConstantInt::get(X->getType(), C->trunc(XWidth));
         Value *And = Builder.CreateAnd(BinOp, TruncC);
         return new ZExtInst(And, Ty);
       }
     }
+
+    const APInt *C1;
+    const APInt *C2;
+    Value *X;
+    if (C->isPowerOf2()) {
+      if (match(Op0, m_OneUse(m_LShr(m_Shl(m_APInt(C1), m_Value(X)),
+                                     m_APInt(C2)))) &&
+          C1->isPowerOf2()) {
+        unsigned Log2C1 = C1->countTrailingZeros();
+        unsigned Log2C = C->countTrailingZeros();
+        unsigned LShrEqBits = Log2C + C2->getZExtValue();
+        if (LShrEqBits >= Log2C1 && LShrEqBits < Width) {
+          // iff C,C1 is pow2 and Log2(C1) < Log2(C)+C2 < BitWidth:
+          // ((C1 << X) >> C2) & C -> X == (Log2(C)+C2-Log2(C1)) ? C : 0
+          unsigned CmpC = LShrEqBits - Log2C1;
+          Value *Cmp = Builder.CreateICmpEQ(X, ConstantInt::get(Ty, CmpC));
+          return SelectInst::Create(Cmp, ConstantInt::get(Ty, *C),
+                                    ConstantInt::getNullValue(Ty));
+        }
+      }
+      if (match(Op0, m_OneUse(m_LShr(m_LShr(m_APInt(C1), m_Value(X)),
+                                     m_APInt(C2)))) &&
+          C1->isPowerOf2()) {
+        unsigned Log2C1 = C1->countTrailingZeros();
+        unsigned Log2C = C->countTrailingZeros();
+        unsigned LShrEqBits = Log2C + C2->getZExtValue();
+        if (LShrEqBits < Log2C1) {
+          // iff C,C1 is pow2 and Log2(C)+C2 < Log2(C1):
+          // ((C1 >> X) >> C2) & C -> X == (Log2(C1)-Log2(C)-C2) ? C : 0
+          unsigned CmpC = Log2C1 - LShrEqBits;
+          Value *Cmp = Builder.CreateICmpEQ(X, ConstantInt::get(Ty, CmpC));
+          return SelectInst::Create(Cmp, ConstantInt::get(Ty, *C),
+                                    ConstantInt::getNullValue(Ty));
+        }
+      }
+    }
   }
 
   if (match(&I, m_And(m_OneUse(m_Shl(m_ZExt(m_Value(X)), m_Value(Y))),
                       m_SignMask())) &&
       match(Y, m_SpecificInt_ICMP(
                    ICmpInst::Predicate::ICMP_EQ,
                    APInt(Ty->getScalarSizeInBits(),
                          Ty->getScalarSizeInBits() -

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

if (Op1Known.isZero()) {
       // If the LHS is an AND with the same constant, look through it.
       Value *LHS = nullptr;
       const APInt *LHSC;
       if (!match(Op0, m_And(m_Value(LHS), m_APInt(LHSC))) ||
           *LHSC != Op0KnownZeroInverted)
         LHS = Op0;
 
       Value *X;
-      if (match(LHS, m_Shl(m_One(), m_Value(X)))) {
-        APInt ValToCheck = Op0KnownZeroInverted;
+      APInt C2 = Op0KnownZeroInverted;
+      const APInt *C1;
+      if (match(LHS, m_Shl(m_Power2(C1), m_Value(X)))) {
         Type *XTy = X->getType();
-        if (ValToCheck.isPowerOf2()) {
-          // ((1 << X) & 8) == 0 -> X != 3
-          // ((1 << X) & 8) != 0 -> X == 3
-          auto *CmpC = ConstantInt::get(XTy, ValToCheck.countTrailingZeros());
+        unsigned Log2C1 = C1->countTrailingZeros();
+        if (C2.isPowerOf2()) {
+          // iff (C1 is pow2) & (C2 is pow2) & (C1 <= C2):
+          // ((C1 << X) & C2) == 0 -> X != (Log2(C2) - Log2(C1))
+          // ((C1 << X) & C2) != 0 -> X == (Log2(C2) - Log2(C1))
+          unsigned Log2C2 = C2.countTrailingZeros();
+          if (Log2C1 <= Log2C2) {
+            auto *CmpC = ConstantInt::get(XTy, Log2C2 - Log2C1);
             auto NewPred = ICmpInst::getInversePredicate(Pred);
             return new ICmpInst(NewPred, X, CmpC);
-        } else if ((++ValToCheck).isPowerOf2()) {
-          // ((1 << X) & 7) == 0 -> X >= 3
-          // ((1 << X) & 7) != 0 -> X  < 3
-          auto *CmpC = ConstantInt::get(XTy, ValToCheck.countTrailingZeros());
-          auto NewPred =
-              Pred == CmpInst::ICMP_EQ ? CmpInst::ICMP_UGE : CmpInst::ICMP_ULT;
+          }
+        } else if ((++C2).isPowerOf2()) {
+          // iff (C1 is pow2) & (C2 is pow2) & (C1 <= C2):
+          // ((C1 << X) & (C2 - 1)) == 0 -> X >= (Log2(C2) - Log2(C1))
+          // ((C1 << X) & (C2 - 1)) != 0 -> X  < (Log2(C2) - Log2(C1))
+          unsigned Log2C2 = C2.countTrailingZeros();
+          if (Log2C1 <= Log2C2) {
+            auto *CmpC = ConstantInt::get(XTy, Log2C2 - Log2C1);
+            auto NewPred = Pred == CmpInst::ICMP_EQ ? CmpInst::ICMP_UGE
+                                                    : CmpInst::ICMP_ULT;
             return new ICmpInst(NewPred, X, CmpC);
           }
         }
+      }
 
-      // Check if the LHS is 8 >>u x and the result is a power of 2 like 1.
-      const APInt *CI;
-      if (Op0KnownZeroInverted.isOne() &&
-          match(LHS, m_LShr(m_Power2(CI), m_Value(X)))) {
-        // ((8 >>u X) & 1) == 0 -> X != 3
-        // ((8 >>u X) & 1) != 0 -> X == 3
-        unsigned CmpVal = CI->countTrailingZeros();
+      // Check if the LHS is C1 >>u x and the result is a power of 2 like 1.
+      if (C2.isPowerOf2() && match(LHS, m_LShr(m_Power2(C1), m_Value(X)))) {
+        unsigned CmpVal = C1->countTrailingZeros() - C2.countTrailingZeros();
+        // iff (C1 is pow2) & (C2 is pow2):
+        // ((C1 >>u X) & C2) == 0 -> X != (Log2(C1) - Log2(C2))
+        // ((C1 >>u X) & C2) != 0 -> X == (Log2(C1) - Log2(C2))
         auto NewPred = ICmpInst::getInversePredicate(Pred);
         return new ICmpInst(NewPred, X, ConstantInt::get(X->getType(), CmpVal));
       }
     }
     break;
   }
   case ICmpInst::ICMP_ULT: {
     if (Op0Max.ult(Op1Min)) // A <u B -> true if max(A) < min(B)

llvm/test/Transforms/InstCombine/and.ll

 ; CHECK-NEXT:    [[R:%.*]] = and i8 [[NOT]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %sign = lshr i8 %x, 7
   %not = xor i8 %sign, -1
   %r = and i8 %not, %y
   ret i8 %r
 }
+
+define i16 @shl_lshr_pow2_const(i16 %x) {
+; CHECK-LABEL: @shl_lshr_pow2_const(
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i16 [[X:%.*]], 7
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[TMP1]], i16 8, i16 0
+; CHECK-NEXT:    ret i16 [[R]]
+;
+  %lshr1 = shl i16 4, %x
+  %lshr2 = lshr i16 %lshr1, 6
+  %r = and i16 %lshr2, 8
+  ret i16 %r
+}
+
+define i16 @shl_lshr_pow2_const_negative_nopow2_1(i16 %x) {
+; CHECK-LABEL: @shl_lshr_pow2_const_negative_nopow2_1(
+; CHECK-NEXT:    [[LSHR1:%.*]] = shl i16 3, [[X:%.*]]
+; CHECK-NEXT:    [[LSHR2:%.*]] = lshr i16 [[LSHR1]], 6
+; CHECK-NEXT:    [[R:%.*]] = and i16 [[LSHR2]], 8
+; CHECK-NEXT:    ret i16 [[R]]
+;
+  %lshr1 = shl i16 3, %x
+  %lshr2 = lshr i16 %lshr1, 6
+  %r = and i16 %lshr2, 8
+  ret i16 %r
+}
+
+define i16 @shl_lshr_pow2_const_negative_nopow2_2(i16 %x) {
+; CHECK-LABEL: @shl_lshr_pow2_const_negative_nopow2_2(
+; CHECK-NEXT:    [[LSHR1:%.*]] = shl i16 3, [[X:%.*]]
+; CHECK-NEXT:    [[LSHR2:%.*]] = lshr i16 [[LSHR1]], 6
+; CHECK-NEXT:    [[R:%.*]] = and i16 [[LSHR2]], 7
+; CHECK-NEXT:    ret i16 [[R]]
+;
+  %lshr1 = shl i16 3, %x
+  %lshr2 = lshr i16 %lshr1, 6
+  %r = and i16 %lshr2, 7
+  ret i16 %r
+}
+
+define i16 @shl_lshr_pow2_const_negative_overflow1(i16 %x) {
+; CHECK-LABEL: @shl_lshr_pow2_const_negative_overflow1(
+; CHECK-NEXT:    ret i16 0
+;
+  %lshr1 = shl i16 4096, %x
+  %lshr2 = lshr i16 %lshr1, 6
+  %r = and i16 %lshr2, 8
+  ret i16 %r
+}
+
+define i16 @shl_lshr_pow2_const_negative_overflow2(i16 %x) {
+; CHECK-LABEL: @shl_lshr_pow2_const_negative_overflow2(
+; CHECK-NEXT:    ret i16 0
+;
+  %lshr1 = shl i16 8, %x
+  %lshr2 = lshr i16 %lshr1, 6
+  %r = and i16 %lshr2, 32768
+  ret i16 %r
+}
+
+define i16 @lshr_lshr_pow2_const(i16 %x) {
+; CHECK-LABEL: @lshr_lshr_pow2_const(
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i16 [[X:%.*]], 3
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[TMP1]], i16 4, i16 0
+; CHECK-NEXT:    ret i16 [[R]]
+;
+  %lshr1 = lshr i16 2048, %x
+  %lshr2 = lshr i16 %lshr1, 6
+  %r = and i16 %lshr2, 4
+  ret i16 %r
+}
+
+define i16 @lshr_lshr_pow2_const_negative_nopow2_1(i16 %x) {
+; CHECK-LABEL: @lshr_lshr_pow2_const_negative_nopow2_1(
+; CHECK-NEXT:    [[LSHR1:%.*]] = lshr i16 2047, [[X:%.*]]
+; CHECK-NEXT:    [[LSHR2:%.*]] = lshr i16 [[LSHR1]], 6
+; CHECK-NEXT:    [[R:%.*]] = and i16 [[LSHR2]], 4
+; CHECK-NEXT:    ret i16 [[R]]
+;
+  %lshr1 = lshr i16 2047, %x
+  %lshr2 = lshr i16 %lshr1, 6
+  %r = and i16 %lshr2, 4
+  ret i16 %r
+}
+
+define i16 @lshr_lshr_pow2_const_negative_nopow2_2(i16 %x) {
+; CHECK-LABEL: @lshr_lshr_pow2_const_negative_nopow2_2(
+; CHECK-NEXT:    [[LSHR1:%.*]] = lshr i16 8192, [[X:%.*]]
+; CHECK-NEXT:    [[LSHR2:%.*]] = lshr i16 [[LSHR1]], 6
+; CHECK-NEXT:    [[R:%.*]] = and i16 [[LSHR2]], 3
+; CHECK-NEXT:    ret i16 [[R]]
+;
+  %lshr1 = lshr i16 8192, %x
+  %lshr2 = lshr i16 %lshr1, 6
+  %r = and i16 %lshr2, 3
+  ret i16 %r
+}
+
+define i16 @lshr_lshr_pow2_const_negative_overflow(i16 %x) {
+; CHECK-LABEL: @lshr_lshr_pow2_const_negative_overflow(
+; CHECK-NEXT:    ret i16 0
+;
+  %lshr1 = lshr i16 32768, %x
+  %lshr2 = lshr i16 %lshr1, 15
+  %r = and i16 %lshr2, 4
+  ret i16 %r
+}

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

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -passes=instcombine -S | FileCheck %s
+
+declare void @use(i8)
+
+define i32 @icmp_eq_and_pow2_shl1(i32 %0) {
+; CHECK-LABEL: @icmp_eq_and_pow2_shl1(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[TMP0:%.*]], 4
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[CMP]] to i32
+; CHECK-NEXT:    ret i32 [[CONV]]
+;
+  %shl = shl i32 1, %0
+  %and = and i32 %shl, 16
+  %cmp = icmp eq i32 %and, 0
+  %conv = zext i1 %cmp to i32
+  ret i32 %conv
+}
+
+define <2 x i32> @icmp_eq_and_pow2_shl1_vec(<2 x i32> %0) {
+; CHECK-LABEL: @icmp_eq_and_pow2_shl1_vec(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne <2 x i32> [[TMP0:%.*]], <i32 4, i32 4>
+; CHECK-NEXT:    [[CONV:%.*]] = zext <2 x i1> [[CMP]] to <2 x i32>
+; CHECK-NEXT:    ret <2 x i32> [[CONV]]
+;
+  %shl = shl <2 x i32> <i32 1, i32 1>, %0
+  %and = and <2 x i32> %shl, <i32 16, i32 16>
+  %cmp = icmp eq <2 x i32> %and, <i32 0, i32 0>
+  %conv = zext <2 x i1> %cmp to <2 x i32>
+  ret <2 x i32> %conv
+}
+
+define i32 @icmp_ne_and_pow2_shl1(i32 %0) {
+; CHECK-LABEL: @icmp_ne_and_pow2_shl1(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[TMP0:%.*]], 4
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[CMP]] to i32
+; CHECK-NEXT:    ret i32 [[CONV]]
+;
+  %shl = shl i32 1, %0
+  %and = and i32 %shl, 16
+  %cmp = icmp ne i32 %and, 0
+  %conv = zext i1 %cmp to i32
+  ret i32 %conv
+}
+
+define <2 x i32> @icmp_ne_and_pow2_shl1_vec(<2 x i32> %0) {
+; CHECK-LABEL: @icmp_ne_and_pow2_shl1_vec(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <2 x i32> [[TMP0:%.*]], <i32 4, i32 4>
+; CHECK-NEXT:    [[CONV:%.*]] = zext <2 x i1> [[CMP]] to <2 x i32>
+; CHECK-NEXT:    ret <2 x i32> [[CONV]]
+;
+  %shl = shl <2 x i32> <i32 1, i32 1>, %0
+  %and = and <2 x i32> %shl, <i32 16, i32 16>
+  %cmp = icmp ne <2 x i32> %and, <i32 0, i32 0>
+  %conv = zext <2 x i1> %cmp to <2 x i32>
+  ret <2 x i32> %conv
+}
+
+define i32 @icmp_eq_and_pow2_shl_pow2(i32 %0) {
+; CHECK-LABEL: @icmp_eq_and_pow2_shl_pow2(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[TMP0:%.*]], 3
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[CMP]] to i32
+; CHECK-NEXT:    ret i32 [[CONV]]
+;
+  %shl = shl i32 2, %0
+  %and = and i32 %shl, 16
+  %cmp = icmp eq i32 %and, 0
+  %conv = zext i1 %cmp to i32
+  ret i32 %conv
+}
+
+define <2 x i32> @icmp_eq_and_pow2_shl_pow2_vec(<2 x i32> %0) {
+; CHECK-LABEL: @icmp_eq_and_pow2_shl_pow2_vec(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne <2 x i32> [[TMP0:%.*]], <i32 2, i32 2>
+; CHECK-NEXT:    [[CONV:%.*]] = zext <2 x i1> [[CMP]] to <2 x i32>
+; CHECK-NEXT:    ret <2 x i32> [[CONV]]
+;
+  %shl = shl <2 x i32> <i32 4, i32 4>, %0
+  %and = and <2 x i32> %shl, <i32 16, i32 16>
+  %cmp = icmp eq <2 x i32> %and, <i32 0, i32 0>
+  %conv = zext <2 x i1> %cmp to <2 x i32>
+  ret <2 x i32> %conv
+}
+
+define i32 @icmp_ne_and_pow2_shl_pow2(i32 %0) {
+; CHECK-LABEL: @icmp_ne_and_pow2_shl_pow2(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[TMP0:%.*]], 3
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[CMP]] to i32
+; CHECK-NEXT:    ret i32 [[CONV]]
+;
+  %shl = shl i32 2, %0
+  %and = and i32 %shl, 16
+  %cmp = icmp ne i32 %and, 0
+  %conv = zext i1 %cmp to i32
+  ret i32 %conv
+}
+
+define <2 x i32> @icmp_ne_and_pow2_shl_pow2_vec(<2 x i32> %0) {
+; CHECK-LABEL: @icmp_ne_and_pow2_shl_pow2_vec(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <2 x i32> [[TMP0:%.*]], <i32 2, i32 2>
+; CHECK-NEXT:    [[CONV:%.*]] = zext <2 x i1> [[CMP]] to <2 x i32>
+; CHECK-NEXT:    ret <2 x i32> [[CONV]]
+;
+  %shl = shl <2 x i32> <i32 4, i32 4>, %0
+  %and = and <2 x i32> %shl, <i32 16, i32 16>
+  %cmp = icmp ne <2 x i32> %and, <i32 0, i32 0>
+  %conv = zext <2 x i1> %cmp to <2 x i32>
+  ret <2 x i32> %conv
+}
+
+define i32 @icmp_eq_and_pow2_shl_pow2_negative1(i32 %0) {
+; CHECK-LABEL: @icmp_eq_and_pow2_shl_pow2_negative1(
+; CHECK-NEXT:    [[SHL:%.*]] = shl i32 11, [[TMP0:%.*]]
+; CHECK-NEXT:    [[AND:%.*]] = lshr i32 [[SHL]], 4
+; CHECK-NEXT:    [[AND_LOBIT:%.*]] = and i32 [[AND]], 1
+; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[AND_LOBIT]], 1
+; CHECK-NEXT:    ret i32 [[TMP2]]
+;
+  %shl = shl i32 11, %0
+  %and = and i32 %shl, 16
+  %cmp = icmp eq i32 %and, 0
+  %conv = zext i1 %cmp to i32
+  ret i32 %conv
+}
+
+define i32 @icmp_eq_and_pow2_shl_pow2_negative2(i32 %0) {
+; CHECK-LABEL: @icmp_eq_and_pow2_shl_pow2_negative2(
+; CHECK-NEXT:    [[SHL:%.*]] = shl i32 2, [[TMP0:%.*]]
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[SHL]], 14
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 0
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[CMP]] to i32
+; CHECK-NEXT:    ret i32 [[CONV]]
+;
+  %shl = shl i32 2, %0
+  %and = and i32 %shl, 14
+  %cmp = icmp eq i32 %and, 0
+  %conv = zext i1 %cmp to i32
+  ret i32 %conv
+}
+
+define i32 @icmp_eq_and_pow2_shl_pow2_negative3(i32 %0) {
+; CHECK-LABEL: @icmp_eq_and_pow2_shl_pow2_negative3(
+; CHECK-NEXT:    ret i32 1
+;
+  %shl = shl i32 32, %0
+  %and = and i32 %shl, 16
+  %cmp = icmp eq i32 %and, 0
+  %conv = zext i1 %cmp to i32
+  ret i32 %conv
+}
+
+
+define i32 @icmp_eq_and_pow2_minus1_shl1(i32 %0) {
+; CHECK-LABEL: @icmp_eq_and_pow2_minus1_shl1(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i32 [[TMP0:%.*]], 3
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[CMP]] to i32
+; CHECK-NEXT:    ret i32 [[CONV]]
+;
+  %shl = shl i32 1, %0
+  %and = and i32 %shl, 15
+  %cmp = icmp eq i32 %and, 0
+  %conv = zext i1 %cmp to i32
+  ret i32 %conv
+}
+
+define <2 x i32> @icmp_eq_and_pow2_minus1_shl1_vec(<2 x i32> %0) {
+; CHECK-LABEL: @icmp_eq_and_pow2_minus1_shl1_vec(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt <2 x i32> [[TMP0:%.*]], <i32 3, i32 3>
+; CHECK-NEXT:    [[CONV:%.*]] = zext <2 x i1> [[CMP]] to <2 x i32>
+; CHECK-NEXT:    ret <2 x i32> [[CONV]]
+;
+  %shl = shl <2 x i32> <i32 1, i32 1>, %0
+  %and = and <2 x i32> %shl, <i32 15, i32 15>
+  %cmp = icmp eq <2 x i32> %and, <i32 0, i32 0>
+  %conv = zext <2 x i1> %cmp to <2 x i32>
+  ret <2 x i32> %conv
+}
+
+define i32 @icmp_ne_and_pow2_minus1_shl1(i32 %0) {
+; CHECK-LABEL: @icmp_ne_and_pow2_minus1_shl1(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[TMP0:%.*]], 4
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[CMP]] to i32
+; CHECK-NEXT:    ret i32 [[CONV]]
+;
+  %shl = shl i32 1, %0
+  %and = and i32 %shl, 15
+  %cmp = icmp ne i32 %and, 0
+  %conv = zext i1 %cmp to i32
+  ret i32 %conv
+}
+
+define <2 x i32> @icmp_ne_and_pow2_minus1_shl1_vec(<2 x i32> %0) {
+; CHECK-LABEL: @icmp_ne_and_pow2_minus1_shl1_vec(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult <2 x i32> [[TMP0:%.*]], <i32 4, i32 4>
+; CHECK-NEXT:    [[CONV:%.*]] = zext <2 x i1> [[CMP]] to <2 x i32>
+; CHECK-NEXT:    ret <2 x i32> [[CONV]]
+;
+  %shl = shl <2 x i32> <i32 1, i32 1>, %0
+  %and = and <2 x i32> %shl, <i32 15, i32 15>
+  %cmp = icmp ne <2 x i32> %and, <i32 0, i32 0>
+  %conv = zext <2 x i1> %cmp to <2 x i32>
+  ret <2 x i32> %conv
+}
+
+define i32 @icmp_eq_and_pow2_minus1_shl_pow2(i32 %0) {
+; CHECK-LABEL: @icmp_eq_and_pow2_minus1_shl_pow2(
+; CHECK-NEXT:    [[SHL:%.*]] = shl i32 2, [[TMP0:%.*]]
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[SHL]], 14
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 0
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[CMP]] to i32
+; CHECK-NEXT:    ret i32 [[CONV]]
+;
+  %shl = shl i32 2, %0
+  %and = and i32 %shl, 15
+  %cmp = icmp eq i32 %and, 0
+  %conv = zext i1 %cmp to i32
+  ret i32 %conv
+}
+
+define <2 x i32> @icmp_eq_and_pow2_minus1_shl_pow2_vec(<2 x i32> %0) {
+; CHECK-LABEL: @icmp_eq_and_pow2_minus1_shl_pow2_vec(
+; CHECK-NEXT:    [[SHL:%.*]] = shl <2 x i32> <i32 4, i32 4>, [[TMP0:%.*]]
+; CHECK-NEXT:    [[AND:%.*]] = and <2 x i32> [[SHL]], <i32 12, i32 12>
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <2 x i32> [[AND]], zeroinitializer
+; CHECK-NEXT:    [[CONV:%.*]] = zext <2 x i1> [[CMP]] to <2 x i32>
+; CHECK-NEXT:    ret <2 x i32> [[CONV]]
+;
+  %shl = shl <2 x i32> <i32 4, i32 4>, %0
+  %and = and <2 x i32> %shl, <i32 15, i32 15>
+  %cmp = icmp eq <2 x i32> %and, <i32 0, i32 0>
+  %conv = zext <2 x i1> %cmp to <2 x i32>
+  ret <2 x i32> %conv
+}
+
+define i32 @icmp_ne_and_pow2_minus1_shl_pow2(i32 %0) {
+; CHECK-LABEL: @icmp_ne_and_pow2_minus1_shl_pow2(
+; CHECK-NEXT:    [[SHL:%.*]] = shl i32 2, [[TMP0:%.*]]
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[SHL]], 14
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[AND]], 0
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[CMP]] to i32
+; CHECK-NEXT:    ret i32 [[CONV]]
+;
+  %shl = shl i32 2, %0
+  %and = and i32 %shl, 15
+  %cmp = icmp ne i32 %and, 0
+  %conv = zext i1 %cmp to i32
+  ret i32 %conv
+}
+
+define <2 x i32> @icmp_ne_and_pow2_minus1_shl_pow2_vec(<2 x i32> %0) {
+; CHECK-LABEL: @icmp_ne_and_pow2_minus1_shl_pow2_vec(
+; CHECK-NEXT:    [[SHL:%.*]] = shl <2 x i32> <i32 4, i32 4>, [[TMP0:%.*]]
+; CHECK-NEXT:    [[AND:%.*]] = and <2 x i32> [[SHL]], <i32 12, i32 12>
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne <2 x i32> [[AND]], zeroinitializer
+; CHECK-NEXT:    [[CONV:%.*]] = zext <2 x i1> [[CMP]] to <2 x i32>
+; CHECK-NEXT:    ret <2 x i32> [[CONV]]
+;
+  %shl = shl <2 x i32> <i32 4, i32 4>, %0
+  %and = and <2 x i32> %shl, <i32 15, i32 15>
+  %cmp = icmp ne <2 x i32> %and, <i32 0, i32 0>
+  %conv = zext <2 x i1> %cmp to <2 x i32>
+  ret <2 x i32> %conv
+}
+
+define i32 @icmp_eq_and_pow2_minus1_shl1_negative1(i32 %0) {
+; CHECK-LABEL: @icmp_eq_and_pow2_minus1_shl1_negative1(
+; CHECK-NEXT:    [[SHL:%.*]] = shl i32 3, [[TMP0:%.*]]
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[SHL]], 15
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 0
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[CMP]] to i32
+; CHECK-NEXT:    ret i32 [[CONV]]
+;
+  %shl = shl i32 3, %0
+  %and = and i32 %shl, 15
+  %cmp = icmp eq i32 %and, 0
+  %conv = zext i1 %cmp to i32
+  ret i32 %conv
+}
+
+define i32 @icmp_eq_and_pow2_minus1_shl1_negative2(i32 %0) {
+; CHECK-LABEL: @icmp_eq_and_pow2_minus1_shl1_negative2(
+; CHECK-NEXT:    ret i32 1
+;
+  %shl = shl i32 32, %0
+  %and = and i32 %shl, 15
+  %cmp = icmp eq i32 %and, 0
+  %conv = zext i1 %cmp to i32
+  ret i32 %conv
+}
+
+
+define i32 @icmp_eq_and1_lshr_pow2(i32 %0) {
+; CHECK-LABEL: @icmp_eq_and1_lshr_pow2(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[TMP0:%.*]], 3
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[CMP]] to i32
+; CHECK-NEXT:    ret i32 [[CONV]]
+;
+  %lshr = lshr i32 8, %0
+  %and  = and i32 %lshr, 1
+  %cmp  = icmp eq i32 %and, 0
+  %conv = zext i1 %cmp to i32
+  ret i32 %conv
+}
+
+define <2 x i32> @icmp_eq_and1_lshr_pow2_vec(<2 x i32> %0) {
+; CHECK-LABEL: @icmp_eq_and1_lshr_pow2_vec(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne <2 x i32> [[TMP0:%.*]], <i32 3, i32 3>
+; CHECK-NEXT:    [[CONV:%.*]] = zext <2 x i1> [[CMP]] to <2 x i32>
+; CHECK-NEXT:    ret <2 x i32> [[CONV]]
+;
+  %lshr = lshr <2 x i32> <i32 8, i32 8>, %0
+  %and  = and <2 x i32> %lshr, <i32 1, i32 1>
+  %cmp  = icmp eq <2 x i32> %and, <i32 0, i32 0>
+  %conv = zext <2 x i1> %cmp to <2 x i32>
+  ret <2 x i32> %conv
+}
+
+define i32 @icmp_ne_and1_lshr_pow2(i32 %0) {
+; CHECK-LABEL: @icmp_ne_and1_lshr_pow2(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[TMP0:%.*]], 3
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[CMP]] to i32
+; CHECK-NEXT:    ret i32 [[CONV]]
+;
+  %lshr = lshr i32 8, %0
+  %and  = and i32 %lshr, 1
+  %cmp  = icmp eq i32 %and, 0
+  %conv = zext i1 %cmp to i32
+  ret i32 %conv
+}
+
+define <2 x i32> @icmp_ne_and1_lshr_pow2_vec(<2 x i32> %0) {
+; CHECK-LABEL: @icmp_ne_and1_lshr_pow2_vec(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <2 x i32> [[TMP0:%.*]], <i32 1, i32 1>
+; CHECK-NEXT:    [[CONV:%.*]] = zext <2 x i1> [[CMP]] to <2 x i32>
+; CHECK-NEXT:    ret <2 x i32> [[CONV]]
+;
+  %lshr = lshr <2 x i32> <i32 8, i32 8>, %0
+  %and  = and <2 x i32> %lshr, <i32 4, i32 4>
+  %cmp  = icmp ne <2 x i32> %and, <i32 0, i32 0>
+  %conv = zext <2 x i1> %cmp to <2 x i32>
+  ret <2 x i32> %conv
+}
+
+define i32 @icmp_eq_and_pow2_lshr_pow2(i32 %0) {
+; CHECK-LABEL: @icmp_eq_and_pow2_lshr_pow2(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[TMP0:%.*]], 1
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[CMP]] to i32
+; CHECK-NEXT:    ret i32 [[CONV]]
+;
+  %lshr = lshr i32 8, %0
+  %and  = and i32 %lshr, 4
+  %cmp  = icmp eq i32 %and, 0
+  %conv = zext i1 %cmp to i32
+  ret i32 %conv
+}
+
+define i32 @icmp_eq_and_pow2_lshr_pow2_case2(i32 %0) {
+; CHECK-LABEL: @icmp_eq_and_pow2_lshr_pow2_case2(
+; CHECK-NEXT:    ret i32 1
+;
+  %lshr = lshr i32 4, %0
+  %and  = and i32 %lshr, 8
+  %cmp  = icmp eq i32 %and, 0
+  %conv = zext i1 %cmp to i32
+  ret i32 %conv
+}
+
+define <2 x i32> @icmp_eq_and_pow2_lshr_pow2_vec(<2 x i32> %0) {
+; CHECK-LABEL: @icmp_eq_and_pow2_lshr_pow2_vec(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne <2 x i32> [[TMP0:%.*]], <i32 1, i32 1>
+; CHECK-NEXT:    [[CONV:%.*]] = zext <2 x i1> [[CMP]] to <2 x i32>
+; CHECK-NEXT:    ret <2 x i32> [[CONV]]
+;
+  %lshr = lshr <2 x i32> <i32 8, i32 8>, %0
+  %and  = and <2 x i32> %lshr, <i32 4, i32 4>
+  %cmp  = icmp eq <2 x i32> %and, <i32 0, i32 0>
+  %conv = zext <2 x i1> %cmp to <2 x i32>
+  ret <2 x i32> %conv
+}
+
+define i32 @icmp_ne_and_pow2_lshr_pow2(i32 %0) {
+; CHECK-LABEL: @icmp_ne_and_pow2_lshr_pow2(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[TMP0:%.*]], 1
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[CMP]] to i32
+; CHECK-NEXT:    ret i32 [[CONV]]
+;
+  %lshr = lshr i32 8, %0
+  %and  = and i32 %lshr, 4
+  %cmp  = icmp eq i32 %and, 0
+  %conv = zext i1 %cmp to i32
+  ret i32 %conv
+}
+
+define i32 @icmp_ne_and_pow2_lshr_pow2_case2(i32 %0) {
+; CHECK-LABEL: @icmp_ne_and_pow2_lshr_pow2_case2(
+; CHECK-NEXT:    ret i32 1
+;
+  %lshr = lshr i32 4, %0
+  %and  = and i32 %lshr, 8
+  %cmp  = icmp eq i32 %and, 0
+  %conv = zext i1 %cmp to i32
+  ret i32 %conv
+}
+
+define <2 x i32> @icmp_ne_and_pow2_lshr_pow2_vec(<2 x i32> %0) {
+; CHECK-LABEL: @icmp_ne_and_pow2_lshr_pow2_vec(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <2 x i32> [[TMP0:%.*]], <i32 1, i32 1>
+; CHECK-NEXT:    [[CONV:%.*]] = zext <2 x i1> [[CMP]] to <2 x i32>
+; CHECK-NEXT:    ret <2 x i32> [[CONV]]
+;
+  %lshr = lshr <2 x i32> <i32 8, i32 8>, %0
+  %and  = and <2 x i32> %lshr, <i32 4, i32 4>
+  %cmp  = icmp ne <2 x i32> %and, <i32 0, i32 0>
+  %conv = zext <2 x i1> %cmp to <2 x i32>
+  ret <2 x i32> %conv
+}
+
+define i32 @icmp_eq_and1_lshr_pow2_negative1(i32 %0) {
+; CHECK-LABEL: @icmp_eq_and1_lshr_pow2_negative1(
+; CHECK-NEXT:    [[LSHR:%.*]] = lshr i32 7, [[TMP0:%.*]]
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[LSHR]], 1
+; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[AND]], 1
+; CHECK-NEXT:    ret i32 [[TMP2]]
+;
+  %lshr = lshr i32 7, %0
+  %and  = and i32 %lshr, 1
+  %cmp  = icmp eq i32 %and, 0
+  %conv = zext i1 %cmp to i32
+  ret i32 %conv
+}
+
+define i32 @icmp_eq_and1_lshr_pow2_negative2(i32 %0) {
+; CHECK-LABEL: @icmp_eq_and1_lshr_pow2_negative2(
+; CHECK-NEXT:    [[LSHR:%.*]] = lshr i32 8, [[TMP0:%.*]]
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[LSHR]], 3
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 0
+; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[CMP]] to i32
+; CHECK-NEXT:    ret i32 [[CONV]]
+;
+  %lshr = lshr i32 8, %0
+  %and  = and i32 %lshr, 3
+  %cmp  = icmp eq i32 %and, 0
+  %conv = zext i1 %cmp to i32
+  ret i32 %conv
+}

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

;
   %lshr = lshr i32 12345, %y
   %and = and i32 %lshr, 2147483648
   %r = icmp eq i32 %and, 0
   ret i1 %r
 }
 
 define i1 @scalar_i32_lshr_and_negC_eq_X_is_constant2(i32 %y) {
 ; CHECK-LABEL: @scalar_i32_lshr_and_negC_eq_X_is_constant2(
-; CHECK-NEXT:    [[LSHR:%.*]] = lshr i32 -2147483648, [[Y:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp sgt i32 [[LSHR]], -1
+; CHECK-NEXT:    [[R:%.*]] = icmp ne i32 [[Y:%.*]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %lshr = lshr i32 2147483648, %y
   %and = and i32 %lshr, 2147483648
   %r = icmp eq i32 %and, 0
   ret i1 %r
 }