[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 ↗

(On Diff #204435)

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

1654 ↗

(On Diff #204435)

X u< 8

1654–1662 ↗

(On Diff #204435)

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 ↗

(On Diff #204435)

It didn't though (:

142 ↗

(On Diff #204435)

Similarly, should fold.

160 ↗

(On Diff #204435)

Here too

[huihuiz]

lib/Transforms/InstCombine/InstCombineCompares.cpp

1643–1644 ↗

(On Diff #204435)

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 ↗

(On Diff #204435)

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 ↗

(On Diff #204435)

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

160 ↗

(On Diff #204435)

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

[lebedev.ri]

lib/Transforms/InstCombine/InstCombineCompares.cpp

1643–1644 ↗

(On Diff #204435)

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 ↗

(On Diff #204435)

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)

llvm/trunk/lib/Transforms/InstCombine/InstCombineCompares.cpp

Instruction *InstCombiner::foldICmpAndShift(ICmpInst &Cmp, BinaryOperator *And,
 
   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;
 
+  // Don't perform the following transforms if the AND has multiple uses
   if (!And->hasOneUse())
     return nullptr;
 
+  if (Cmp.isEquality() && C1.isNullValue()) {
+    // Restrict this fold to single-use 'and' (PR10267).
+    // 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);
+    }
+  }
+
   // 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 (match(BOp1, m_APInt(BOC))) {
       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;

llvm/trunk/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
 }
 

llvm/trunk/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
 }