[InstCombine] Fold icmp eq/ne (and %x, signbit), 0 -> %x s>=/s< 0 earlier

[huihuiz]

Summary

To generate simplified IR, make sure fold

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

is scheduled before fold

((X << Y) & C) == 0 -> (X & (C >> Y)) == 0.

https://rise4fun.com/Alive/fbdh

[huihuiz]

This fix D63025
Split from D62818

[lebedev.ri]

Yep, first fold looks good, some nits.

lib/Transforms/InstCombine/InstCombineCompares.cpp

1643–1644

Move after the newly added code, this restriction does not apply for the pattern in question.

1654

X u< 8

1654–1662

I'm sorry that i keep nagging, but this is a second, not unrelated, but separate fold.
Please put it into a separate review :)

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

125

It didn't though (:

142

Similarly, should fold.

160

Here too

[huihuiz]

lib/Transforms/InstCombine/InstCombineCompares.cpp

1643–1644

The restriction "And operation having only one use" was introduced in r134379 (resolving PR10267).

When And operation has more than one use, applying the following folds will transform an equality compare into an inequality compare, without cutting done any extra instructions. Inequalities are generally more expensive.

This restriction should apply to fold "(X & signbit) ==/!= 0) --> X s>=/s< 0"and "((X & ~C) ==/!= 0) C+1 is power of 2 --> X u</u>= C+1".

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

125

Actually fold happened even without this reordering.
look for the generate ll

**%shl = shl i32 %x, %y**
%xor = xor i32 %shl, %z
store i32 %xor, i32* %p, align 4
**%r = icmp sgt i32 %shl, -1**

we are trying to schedule (X & signbit) ==/!= 0) -> X s>=/s< 0; before ((X << Y) & C) == 0 -> (X & (C >> Y)) == 0.
The second fold has restriction on "shift having only one use", which failed for this case.

So fold happened even without reorder, extra use of shift doesn't restrict on the first fold

142

Should still comply with restriction on "And operation having only one use", as explained in r134379.

160

Similar as above. And operation has extra use, should comply with the restriction.

[lebedev.ri]

lib/Transforms/InstCombine/InstCombineCompares.cpp

1643–1644

Aha, thank you for digging that up.

The restriction "And operation having only one use" was introduced in r134379 (resolving PR10267).
When And operation has more than one use, applying the following folds will transform an equality compare into an inequality compare, without cutting done any extra instructions. Inequalities are generally more expensive.

All that (including rL134379) reads wrong to me.
There is no such cost-model in middle-end,
here in instcombine we only care about not increasing instruction count.
If something is worse for backend/target, then the opposite fold should be done in backend.

Not having this one-use restriction does not result in increasing
instruction count, and decreases "the dependency chain" of the icmp,
since it no longer depends on and, i.e. the restriction is incorrect/harmful.

But i suppose lifting it up first requires a backend fix, so let's leave it for now :/

[lebedev.ri]

I think this looks good now, thank you for working on this!
Can you please link the patch into which you split the second fold from here?

lib/Transforms/InstCombine/InstCombineCompares.cpp

1025–1033

Can you please link the patch to which you split this out?

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1647 ↗

(On Diff #205388)

Please add a comment about the reason (PR10267) this fold is restricted to one-use and.

[lebedev.ri]

Hmm, here too, an undo fold seems to be missing https://godbolt.org/z/T9NwwJ

[huihuiz]

this differential update address inline comment - adding comment for restriction this fold to single-use 'and' (PR10267)

lib/Transforms/InstCombine/InstCombineCompares.cpp

   // can therefore act as if any such guesses are wrong.
   //
   // The code below checks that the alloca doesn't escape, and that it's only
   // used in a comparison once (the current instruction). The
   // single-comparison-use condition ensures that we're trivially folding all
   // comparisons against the alloca consistently, and avoids the risk of
   // erroneously folding a comparison of the pointer with itself.
 
   unsigned MaxIter = 32; // Break cycles and bound to constant-time.
 
   SmallVector<const Use *, 32> Worklist;
   for (const Use &U : Alloca->uses()) {
     if (Worklist.size() >= MaxIter)
       return nullptr;
     Worklist.push_back(&U);
   }
 
   unsigned NumCmps = 0;
   while (!Worklist.empty()) {
     assert(Worklist.size() <= MaxIter);
     const Use *U = Worklist.pop_back_val();
     const Value *V = U->getUser();
     --MaxIter;
 
     if (isa<BitCastInst>(V) || isa<GetElementPtrInst>(V) || isa<PHINode>(V) ||

 
   return nullptr;
 }
 
 /// Fold icmp (and X, C2), C1.
 Instruction *InstCombiner::foldICmpAndConstConst(ICmpInst &Cmp,
                                                  BinaryOperator *And,
                                                  const APInt &C1) {
+  bool isICMP_NE = Cmp.getPredicate() == ICmpInst::ICMP_NE;
+
   // For vectors: icmp ne (and X, 1), 0 --> trunc X to N x i1
   // TODO: We canonicalize to the longer form for scalars because we have
   // better analysis/folds for icmp, and codegen may be better with icmp.
-  if (Cmp.getPredicate() == CmpInst::ICMP_NE && Cmp.getType()->isVectorTy() &&
-      C1.isNullValue() && match(And->getOperand(1), m_One()))
+  if (isICMP_NE && Cmp.getType()->isVectorTy() && C1.isNullValue() &&
+      match(And->getOperand(1), m_One()))
     return new TruncInst(And->getOperand(0), Cmp.getType());
 
   const APInt *C2;
-  if (!match(And->getOperand(1), m_APInt(C2)))
+  Value *X;
+  if (!match(And, m_And(m_Value(X), m_APInt(C2))))
     return nullptr;
 
   if (!And->hasOneUse())
     return nullptr;
 
+  if (Cmp.isEquality() && C1.isNullValue()) {
+    // Replace (and X, (1 << size(X)-1) != 0) with X s< 0
+    if (C2->isSignMask()) {
+      Constant *Zero = Constant::getNullValue(X->getType());
+      auto NewPred = isICMP_NE ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_SGE;
+      return new ICmpInst(NewPred, X, Zero);
+    }
+
+    // ((X & ~7) == 0) --> X < 8
+    // If X is (BinOp Y, C3), allow other rules to fold C3 with C2.
+    if (!match(X, m_c_BinOp(m_Value(), m_Constant())) &&
+        (~(*C2) + 1).isPowerOf2()) {
+      Constant *NegBOC =
+          ConstantExpr::getNeg(cast<Constant>(And->getOperand(1)));
+      auto NewPred = isICMP_NE ? ICmpInst::ICMP_UGE : ICmpInst::ICMP_ULT;
+      return new ICmpInst(NewPred, X, NegBOC);
+    }
+  }
+
   // If the LHS is an 'and' of a truncate and we can widen the and/compare to
   // the input width without changing the value produced, eliminate the cast:
   //
   // icmp (and (trunc W), C2), C1 -> icmp (and W, C2'), C1'
   //
   // We can do this transformation if the constants do not have their sign bits
   // set or if it is an equality comparison. Extending a relational comparison
   // when we're checking the sign bit would not work.

       if (C == *BOC && C.isPowerOf2())
         return new ICmpInst(isICMP_NE ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE,
                             BO, Constant::getNullValue(RHS->getType()));
 
       // Don't perform the following transforms if the AND has multiple uses
       if (!BO->hasOneUse())
         break;
 
-      // Replace (and X, (1 << size(X)-1) != 0) with x s< 0
-      if (BOC->isSignMask()) {
-        Constant *Zero = Constant::getNullValue(BOp0->getType());
-        auto NewPred = isICMP_NE ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_SGE;
-        return new ICmpInst(NewPred, BOp0, Zero);
-      }
-
       // ((X & ~7) == 0) --> X < 8
       if (C.isNullValue() && (~(*BOC) + 1).isPowerOf2()) {
         Constant *NegBOC = ConstantExpr::getNeg(cast<Constant>(BOp1));
         auto NewPred = isICMP_NE ? ICmpInst::ICMP_UGE : ICmpInst::ICMP_ULT;
         return new ICmpInst(NewPred, BOp0, NegBOC);
       }
     }
     break;

test/Transforms/InstCombine/lshr-and-negC-icmpeq-zero.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt %s -instcombine -S | FileCheck %s
 
 ; For pattern ((X l>> Y) & ~C) ==/!= 0; when C+1 is power of 2
 ; it may be optimal to fold into (X l>> Y) </>= C+1
 ; rather than X & (~C << Y) ==/!= 0
 
 ; Scalar tests
 
 define i1 @scalar_i8_lshr_and_negC_eq(i8 %x, i8 %y) {
 ; CHECK-LABEL: @scalar_i8_lshr_and_negC_eq(
-; CHECK-NEXT:    [[TMP1:%.*]] = shl i8 -4, [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = and i8 [[TMP1]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[TMP2]], 0
+; CHECK-NEXT:    [[LSHR:%.*]] = lshr i8 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ult i8 [[LSHR]], 4
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %lshr = lshr i8 %x, %y
   %and = and i8 %lshr, 252  ; ~3
   %r = icmp eq i8 %and, 0
   ret i1 %r
 }
 
 define i1 @scalar_i16_lshr_and_negC_eq(i16 %x, i16 %y) {
 ; CHECK-LABEL: @scalar_i16_lshr_and_negC_eq(
-; CHECK-NEXT:    [[TMP1:%.*]] = shl i16 -128, [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = and i16 [[TMP1]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i16 [[TMP2]], 0
+; CHECK-NEXT:    [[LSHR:%.*]] = lshr i16 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ult i16 [[LSHR]], 128
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %lshr = lshr i16 %x, %y
   %and = and i16 %lshr, 65408  ; ~127
   %r = icmp eq i16 %and, 0
   ret i1 %r
 }
 
 define i1 @scalar_i32_lshr_and_negC_eq(i32 %x, i32 %y) {
 ; CHECK-LABEL: @scalar_i32_lshr_and_negC_eq(
-; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 -262144, [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i32 [[TMP2]], 0
+; CHECK-NEXT:    [[LSHR:%.*]] = lshr i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ult i32 [[LSHR]], 262144
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %lshr = lshr i32 %x, %y
   %and = and i32 %lshr, 4294705152  ; ~262143
   %r = icmp eq i32 %and, 0
   ret i1 %r
 }
 
 define i1 @scalar_i64_lshr_and_negC_eq(i64 %x, i64 %y) {
 ; CHECK-LABEL: @scalar_i64_lshr_and_negC_eq(
-; CHECK-NEXT:    [[TMP1:%.*]] = shl i64 -8589934592, [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = and i64 [[TMP1]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i64 [[TMP2]], 0
+; CHECK-NEXT:    [[LSHR:%.*]] = lshr i64 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ult i64 [[LSHR]], 8589934592
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %lshr = lshr i64 %x, %y
   %and = and i64 %lshr, 18446744065119617024  ; ~8589934591
   %r = icmp eq i64 %and, 0
   ret i1 %r
 }
 
 define i1 @scalar_i32_lshr_and_negC_ne(i32 %x, i32 %y) {
 ; CHECK-LABEL: @scalar_i32_lshr_and_negC_ne(
-; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 -262144, [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ne i32 [[TMP2]], 0
+; CHECK-NEXT:    [[LSHR:%.*]] = lshr i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ugt i32 [[LSHR]], 262143
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %lshr = lshr i32 %x, %y
   %and = and i32 %lshr, 4294705152  ; ~262143
   %r = icmp ne i32 %and, 0   ; check 'ne' predicate
   ret i1 %r
 }
 
 ; Vector tests
 
 define <4 x i1> @vec_4xi32_lshr_and_negC_eq(<4 x i32> %x, <4 x i32> %y) {
 ; CHECK-LABEL: @vec_4xi32_lshr_and_negC_eq(
-; CHECK-NEXT:    [[TMP1:%.*]] = shl <4 x i32> <i32 -8, i32 -8, i32 -8, i32 -8>, [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = and <4 x i32> [[TMP1]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq <4 x i32> [[TMP2]], zeroinitializer
+; CHECK-NEXT:    [[LSHR:%.*]] = lshr <4 x i32> [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ult <4 x i32> [[LSHR]], <i32 8, i32 8, i32 8, i32 8>
 ; CHECK-NEXT:    ret <4 x i1> [[R]]
 ;
   %lshr = lshr <4 x i32> %x, %y
   %and = and <4 x i32> %lshr, <i32 4294967288, i32 4294967288, i32 4294967288, i32 4294967288>  ; ~7
   %r = icmp eq <4 x i32> %and, <i32 0, i32 0, i32 0, i32 0>
   ret <4 x i1> %r
 }
 

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

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

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt %s -instcombine -S | FileCheck %s
 
 ; For pattern ((X << Y) & ~C) ==/!= 0; when C+1 is power of 2
 ; it may be optimal to fold into (X << Y) </>= C+1
 ; rather than X & (~C l>> Y) ==/!= 0
 
 ; Scalar tests
 
 define i1 @scalar_i8_shl_and_negC_eq(i8 %x, i8 %y) {
 ; CHECK-LABEL: @scalar_i8_shl_and_negC_eq(
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr i8 -4, [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = and i8 [[TMP1]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[TMP2]], 0
+; CHECK-NEXT:    [[SHL:%.*]] = shl i8 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ult i8 [[SHL]], 4
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %shl = shl i8 %x, %y
   %and = and i8 %shl, 252  ; ~3
   %r = icmp eq i8 %and, 0
   ret i1 %r
 }
 
 define i1 @scalar_i16_shl_and_negC_eq(i16 %x, i16 %y) {
 ; CHECK-LABEL: @scalar_i16_shl_and_negC_eq(
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr i16 -128, [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = and i16 [[TMP1]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i16 [[TMP2]], 0
+; CHECK-NEXT:    [[SHL:%.*]] = shl i16 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ult i16 [[SHL]], 128
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %shl = shl i16 %x, %y
   %and = and i16 %shl, 65408  ; ~127
   %r = icmp eq i16 %and, 0
   ret i1 %r
 }
 
 define i1 @scalar_i32_shl_and_negC_eq(i32 %x, i32 %y) {
 ; CHECK-LABEL: @scalar_i32_shl_and_negC_eq(
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 -262144, [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i32 [[TMP2]], 0
+; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ult i32 [[SHL]], 262144
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %shl = shl i32 %x, %y
   %and = and i32 %shl, 4294705152  ; ~262143
   %r = icmp eq i32 %and, 0
   ret i1 %r
 }
 
 define i1 @scalar_i64_shl_and_negC_eq(i64 %x, i64 %y) {
 ; CHECK-LABEL: @scalar_i64_shl_and_negC_eq(
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr i64 -8589934592, [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = and i64 [[TMP1]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i64 [[TMP2]], 0
+; CHECK-NEXT:    [[SHL:%.*]] = shl i64 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ult i64 [[SHL]], 8589934592
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %shl = shl i64 %x, %y
   %and = and i64 %shl, 18446744065119617024  ; ~8589934591
   %r = icmp eq i64 %and, 0
   ret i1 %r
 }
 
 define i1 @scalar_i32_shl_and_negC_ne(i32 %x, i32 %y) {
 ; CHECK-LABEL: @scalar_i32_shl_and_negC_ne(
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 -262144, [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ne i32 [[TMP2]], 0
+; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ugt i32 [[SHL]], 262143
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %shl = shl i32 %x, %y
   %and = and i32 %shl, 4294705152  ; ~262143
   %r = icmp ne i32 %and, 0   ; check 'ne' predicate
   ret i1 %r
 }
 
 ; Vector tests
 
 define <4 x i1> @vec_4xi32_shl_and_negC_eq(<4 x i32> %x, <4 x i32> %y) {
 ; CHECK-LABEL: @vec_4xi32_shl_and_negC_eq(
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr <4 x i32> <i32 -8, i32 -8, i32 -8, i32 -8>, [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = and <4 x i32> [[TMP1]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq <4 x i32> [[TMP2]], zeroinitializer
+; CHECK-NEXT:    [[SHL:%.*]] = shl <4 x i32> [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ult <4 x i32> [[SHL]], <i32 8, i32 8, i32 8, i32 8>
 ; CHECK-NEXT:    ret <4 x i1> [[R]]
 ;
   %shl = shl <4 x i32> %x, %y
   %and = and <4 x i32> %shl, <i32 4294967288, i32 4294967288, i32 4294967288, i32 4294967288>  ; ~7
   %r = icmp eq <4 x i32> %and, <i32 0, i32 0, i32 0, i32 0>
   ret <4 x i1> %r
 }
 

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt %s -instcombine -S | FileCheck %s
 
 ; For pattern ((X << Y) & signbit) ==/!= 0
 ; it may be optimal to fold into (X << Y) >=/< 0
 ; rather than X & (signbit l>> Y) ==/!= 0
 
 ; Scalar tests
 
 define i1 @scalar_i8_shl_and_signbit_eq(i8 %x, i8 %y) {
 ; CHECK-LABEL: @scalar_i8_shl_and_signbit_eq(
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr i8 -128, [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = and i8 [[TMP1]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i8 [[TMP2]], 0
+; CHECK-NEXT:    [[SHL:%.*]] = shl i8 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt i8 [[SHL]], -1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %shl = shl i8 %x, %y
   %and = and i8 %shl, 128
   %r = icmp eq i8 %and, 0
   ret i1 %r
 }
 
 define i1 @scalar_i16_shl_and_signbit_eq(i16 %x, i16 %y) {
 ; CHECK-LABEL: @scalar_i16_shl_and_signbit_eq(
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr i16 -32768, [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = and i16 [[TMP1]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i16 [[TMP2]], 0
+; CHECK-NEXT:    [[SHL:%.*]] = shl i16 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt i16 [[SHL]], -1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %shl = shl i16 %x, %y
   %and = and i16 %shl, 32768
   %r = icmp eq i16 %and, 0
   ret i1 %r
 }
 
 define i1 @scalar_i32_shl_and_signbit_eq(i32 %x, i32 %y) {
 ; CHECK-LABEL: @scalar_i32_shl_and_signbit_eq(
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 -2147483648, [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i32 [[TMP2]], 0
+; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt i32 [[SHL]], -1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %shl = shl i32 %x, %y
   %and = and i32 %shl, 2147483648
   %r = icmp eq i32 %and, 0
   ret i1 %r
 }
 
 define i1 @scalar_i64_shl_and_signbit_eq(i64 %x, i64 %y) {
 ; CHECK-LABEL: @scalar_i64_shl_and_signbit_eq(
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr i64 -9223372036854775808, [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = and i64 [[TMP1]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq i64 [[TMP2]], 0
+; CHECK-NEXT:    [[SHL:%.*]] = shl i64 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt i64 [[SHL]], -1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %shl = shl i64 %x, %y
   %and = and i64 %shl, 9223372036854775808
   %r = icmp eq i64 %and, 0
   ret i1 %r
 }
 
 define i1 @scalar_i32_shl_and_signbit_ne(i32 %x, i32 %y) {
 ; CHECK-LABEL: @scalar_i32_shl_and_signbit_ne(
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 -2147483648, [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ne i32 [[TMP2]], 0
+; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp slt i32 [[SHL]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %shl = shl i32 %x, %y
   %and = and i32 %shl, 2147483648
   %r = icmp ne i32 %and, 0  ; check 'ne' predicate
   ret i1 %r
 }
 
 ; Vector tests
 
 define <4 x i1> @vec_4xi32_shl_and_signbit_eq(<4 x i32> %x, <4 x i32> %y) {
 ; CHECK-LABEL: @vec_4xi32_shl_and_signbit_eq(
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr <4 x i32> <i32 -2147483648, i32 -2147483648, i32 -2147483648, i32 -2147483648>, [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = and <4 x i32> [[TMP1]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = icmp eq <4 x i32> [[TMP2]], zeroinitializer
+; CHECK-NEXT:    [[SHL:%.*]] = shl <4 x i32> [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = icmp sgt <4 x i32> [[SHL]], <i32 -1, i32 -1, i32 -1, i32 -1>
 ; CHECK-NEXT:    ret <4 x i1> [[R]]
 ;
   %shl = shl <4 x i32> %x, %y
   %and = and <4 x i32> %shl, <i32 2147483648, i32 2147483648, i32 2147483648, i32 2147483648>
   %r = icmp eq <4 x i32> %and, <i32 0, i32 0, i32 0, i32 0>
   ret <4 x i1> %r
 }
 
;
   %shl = shl <4 x i32> %x, %y
   %and = and <4 x i32> %shl, <i32 2147483648, i32 undef, i32 2147483648, i32 2147483648>
   %r = icmp eq <4 x i32> %and, <i32 0, i32 0, i32 0, i32 undef>
   ret <4 x i1> %r
 }
 
 ; Extra use
 
 ; Fold happened
 define i1 @scalar_shl_and_signbit_eq_extra_use_shl(i32 %x, i32 %y, i32 %z, i32* %p) {
 ; CHECK-LABEL: @scalar_shl_and_signbit_eq_extra_use_shl(
 ; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[SHL]], [[Z:%.*]]
 ; CHECK-NEXT:    store i32 [[XOR]], i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    [[R:%.*]] = icmp sgt i32 [[SHL]], -1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %shl = shl i32 %x, %y
   %xor = xor i32 %shl, %z  ; extra use of shl
   store i32 %xor, i32* %p
   %and = and i32 %shl, 2147483648
   %r = icmp eq i32 %and, 0
   ret i1 %r
 }
 
 ; Not fold
 define i1 @scalar_shl_and_signbit_eq_extra_use_and(i32 %x, i32 %y, i32 %z, i32* %p) {
 ; CHECK-LABEL: @scalar_shl_and_signbit_eq_extra_use_and(
 ; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[SHL]], -2147483648
 ; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[AND]], [[Z:%.*]]
 ; CHECK-NEXT:    store i32 [[MUL]], i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    [[R:%.*]] = icmp eq i32 [[AND]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %shl = shl i32 %x, %y
   %and = and i32 %shl, 2147483648
   %mul = mul i32 %and, %z  ; extra use of and
   store i32 %mul, i32* %p
   %r = icmp eq i32 %and, 0
   ret i1 %r
 }
 
 ; Not fold
 define i1 @scalar_shl_and_signbit_eq_extra_use_shl_and(i32 %x, i32 %y, i32 %z, i32* %p, i32* %q) {
 ; CHECK-LABEL: @scalar_shl_and_signbit_eq_extra_use_shl_and(
 ; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[SHL]], -2147483648
 ; CHECK-NEXT:    store i32 [[AND]], i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[SHL]], [[Z:%.*]]
 ; CHECK-NEXT:    store i32 [[ADD]], i32* [[Q:%.*]], align 4
 ; CHECK-NEXT:    [[R:%.*]] = icmp eq i32 [[AND]], 0