[InstCombine] fold one-bit set/clear icmp with mul operand

[spatel]

Summary

((X1 * C1) & C2) ==/!= 0 --> (X1 & 1) ==/!= 0

... iff C2 is a power-of-2 and C1 is a multiple of C2, and C2 does not have known zero low-bits set

This is a reduced form of one proposed transform in D114272.

If I translated the pre-conditions correctly, then this is just a test of the LSB of the input operand:
https://alive2.llvm.org/ce/z/YB_4pn

[lebedev.ri]

LGTM, thanks.
The proof looks correct to me, but a fear that we are missing things due to extra artificial uses due to the preconditions has struck me before.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1863

This fold should probably be in foldICmpAndConstConst()

[spatel]

Patch updated:
Moved the code into foldICmpAndConstConst, so we have more shared matches/captures with existing code.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

1863

Yes, will move.

[spatel]

I had regrets about this patch shortly after my previous comment. It's not an icmp fold that we're looking for. It's either "one-demanded-bit-of-multiply" or an "and" fold:
https://alive2.llvm.org/ce/z/D_Rma8

[spatel]

Abandoned in favor of a more general demanded-bits fold:
0236c571810d

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

if (Cmp.isEquality() && C1.isZero()) {
     // Restrict this fold only for single-use 'and' (PR10267).
     // ((%x & C) == 0) --> %x u< (-C)  iff (-C) is power of two.
     if ((~(*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);
     }
+
+    // ((X1 * MulC) & C2) ==/!= 0 --> (X1 & 1) ==/!= 0
+    //   iff C2 is a power-of-2 and MulC is a multiple of C2
+    Value *X1;
+    const APInt *MulC;
+    if (match(X, m_Mul(m_Value(X1), m_APInt(MulC))) && C2->isPowerOf2() &&
+        MulC->urem(*C2).isZero()) {
+      // To make the transform safe, make sure the mask constant does not
+      // include bits that must be zero. Demanded bits should clear those bits,
+      // but it may not have been applied yet.
+      unsigned MulTZ = MulC->countTrailingZeros();
+      if (C2->lshr(MulTZ).shl(MulTZ) == *C2) {
+        Value *And1 = Builder.CreateAnd(X1, ConstantInt::get(X->getType(), 1));
+        return new ICmpInst(Cmp.getPredicate(), And1, Cmp.getOperand(1));
+      }
+    }
   }
 
   // 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
Instruction *InstCombinerImpl::foldICmpAndConstConst(ICmpInst &Cmp,
 
   return nullptr;
 }
 
 /// Fold icmp (and X, Y), C.
 Instruction *InstCombinerImpl::foldICmpAndConstant(ICmpInst &Cmp,
                                                    BinaryOperator *And,
                                                    const APInt &C) {
   if (Instruction *I = foldICmpAndConstConst(Cmp, And, C))
     return I;
 
   const ICmpInst::Predicate Pred = Cmp.getPredicate();
   bool TrueIfNeg;
   if (isSignBitCheck(Pred, C, TrueIfNeg)) {
     // ((X - 1) & ~X) <  0 --> X == 0
     // ((X - 1) & ~X) >= 0 --> X != 0
     Value *X;

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 declare void @use(i8)
 
 define i1 @mul_mask_pow2_eq0(i8 %x) {
 ; CHECK-LABEL: @mul_mask_pow2_eq0(
-; CHECK-NEXT:    [[MUL:%.*]] = mul i8 [[X:%.*]], 44
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[MUL]], 4
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[AND]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %mul = mul i8 %x, 44
   %and = and i8 %mul, 4
   %cmp = icmp eq i8 %and, 0
   ret i1 %cmp
 }
 
+; extra use of mul is ok.
+
 define i1 @mul_mask_pow2_ne0_use1(i8 %x) {
 ; CHECK-LABEL: @mul_mask_pow2_ne0_use1(
 ; CHECK-NEXT:    [[MUL:%.*]] = mul i8 [[X:%.*]], 40
 ; CHECK-NEXT:    call void @use(i8 [[MUL]])
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[MUL]], 8
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[AND]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %mul = mul i8 %x, 40
   call void @use(i8 %mul)
   %and = and i8 %mul, 8
   %cmp = icmp ne i8 %and, 0
   ret i1 %cmp
 }
 
+; negative test - extra use of 'and' would require more instructions
+
 define i1 @mul_mask_pow2_ne0_use2(i8 %x) {
 ; CHECK-LABEL: @mul_mask_pow2_ne0_use2(
 ; CHECK-NEXT:    [[MUL:%.*]] = mul i8 [[X:%.*]], 40
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[MUL]], 8
 ; CHECK-NEXT:    call void @use(i8 [[AND]])
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[AND]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %mul = mul i8 %x, 40
   %and = and i8 %mul, 8
   call void @use(i8 %and)
   %cmp = icmp ne i8 %and, 0
   ret i1 %cmp
 }
 
+; non-equality predicates are converted to equality
+
 define i1 @mul_mask_pow2_sgt0(i8 %x) {
 ; CHECK-LABEL: @mul_mask_pow2_sgt0(
-; CHECK-NEXT:    [[MUL:%.*]] = mul i8 [[X:%.*]], 44
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[MUL]], 4
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[AND]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %mul = mul i8 %x, 44
   %and = and i8 %mul, 4
   %cmp = icmp sgt i8 %and, 0
   ret i1 %cmp
 }
 
+; unnecessary mask bits are removed
+
 define i1 @mul_mask_fakepow2_ne0(i8 %x) {
 ; CHECK-LABEL: @mul_mask_fakepow2_ne0(
-; CHECK-NEXT:    [[MUL:%.*]] = mul i8 [[X:%.*]], 44
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[MUL]], 4
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[AND]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %mul = mul i8 %x, 44
   %and = and i8 %mul, 5
   %cmp = icmp ne i8 %and, 0
   ret i1 %cmp
 }
 
+; non-zero cmp constant is converted
+
 define i1 @mul_mask_pow2_eq4(i8 %x) {
 ; CHECK-LABEL: @mul_mask_pow2_eq4(
-; CHECK-NEXT:    [[MUL:%.*]] = mul i8 [[X:%.*]], 44
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[MUL]], 4
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[AND]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %mul = mul i8 %x, 44
   %and = and i8 %mul, 4
   %cmp = icmp eq i8 %and, 4
   ret i1 %cmp
 }
 
+; negative test - must be pow2 mask constant
+
 define i1 @mul_mask_notpow2_ne(i8 %x) {
 ; CHECK-LABEL: @mul_mask_notpow2_ne(
 ; CHECK-NEXT:    [[MUL:%.*]] = mul i8 [[X:%.*]], 60
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[MUL]], 12
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i8 [[AND]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %mul = mul i8 %x, 60
   %and = and i8 %mul, 12
   %cmp = icmp ne i8 %and, 0
   ret i1 %cmp
 }
 
 define i1 @pr40493(i32 %area) {
 ; CHECK-LABEL: @pr40493(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[AREA:%.*]], 12
-; CHECK-NEXT:    [[REM:%.*]] = and i32 [[MUL]], 4
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[REM]], 0
+; CHECK-NEXT:    [[TMP0:%.*]] = and i32 [[AREA:%.*]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[TMP0]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
 entry:
   %mul = mul i32 %area, 12
   %rem = and i32 %mul, 4
   %cmp = icmp eq i32 %rem, 0
   ret i1 %cmp
 }
entry:
   %mul = mul i32 %area, 12
   %rem = and i32 %mul, 4
   ret i32 %rem
 }
 
 define <4 x i1> @pr40493_vec1(<4 x i32> %area) {
 ; CHECK-LABEL: @pr40493_vec1(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[MUL:%.*]] = mul <4 x i32> [[AREA:%.*]], <i32 12, i32 12, i32 12, i32 12>
-; CHECK-NEXT:    [[REM:%.*]] = and <4 x i32> [[MUL]], <i32 4, i32 4, i32 4, i32 4>
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <4 x i32> [[REM]], zeroinitializer
+; CHECK-NEXT:    [[TMP0:%.*]] = and <4 x i32> [[AREA:%.*]], <i32 1, i32 1, i32 1, i32 1>
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <4 x i32> [[TMP0]], zeroinitializer
 ; CHECK-NEXT:    ret <4 x i1> [[CMP]]
 ;
 entry:
   %mul = mul <4 x i32> %area, <i32 12, i32 12, i32 12, i32 12>
   %rem = and <4 x i32> %mul, <i32 4, i32 4, i32 4, i32 4>
   %cmp = icmp eq <4 x i32> %rem, zeroinitializer
   ret <4 x i1> %cmp
 }