[InstCombine] try to fold one-demanded-bit-of-multiply

[spatel]

Summary

This is a generalization of the icmp fold in D118061 (and that can probably be abandoned if this is sufficient).
We're looking for a disguised form of "odd * odd must be odd".
Some Alive2 proofs to show correctness:
https://alive2.llvm.org/ce/z/60Y8hz
https://alive2.llvm.org/ce/z/HfAP6R

[RKSimon]

I don't suppose this can handle D117995? If we can do this in SimplifyDemandedBits then we can add the knownbits fold with the additional NeverUndefOrPoison check.

Otherwise I think I'll just add a (DemandedMask ==2 && X == Y) -> 0 special case.

[spatel]

In D118539#3281894, @RKSimon wrote:

I don't suppose this can handle D117995? If we can do this in SimplifyDemandedBits then we can add the knownbits fold with the additional NeverUndefOrPoison check.

Otherwise I think I'll just add a (DemandedMask ==2 && X == Y) -> 0 special case.

Hmm, not sure if I understood the question. I'm not seeing how we'd do it other than a special-case here. The knownbits fold isn't going to work in general because of the potential undef input?

[spatel]

In D118539#3281913, @spatel wrote:

In D118539#3281894, @RKSimon wrote:

I don't suppose this can handle D117995? If we can do this in SimplifyDemandedBits then we can add the knownbits fold with the additional NeverUndefOrPoison check.

Otherwise I think I'll just add a (DemandedMask ==2 && X == Y) -> 0 special case.

Hmm, not sure if I understood the question. I'm not seeing how we'd do it other than a special-case here. The knownbits fold isn't going to work in general because of the potential undef input?

Also, if we're adding the Mask==2 special-case for self-multiply, we could add the Mask==1 case as well:
https://alive2.llvm.org/ce/z/3HcD76

[spatel]

Ping.

Note that 2d1390efbe610 added one special-case for the backend. Presumably, we should keep these in sync as much as possible, so I can add that in follow-ups after adding tests.

[lebedev.ri]

LGTM, thank you!

llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

548

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

549–550

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

551–560

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

[RKSimon]

In D118539#3296618, @spatel wrote:

Ping.

Note that 2d1390efbe610 added one special-case for the backend. Presumably, we should keep these in sync as much as possible, so I can add that in follow-ups after adding tests.

Cheers @spatel !

llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

if ((I->getOpcode() == Instruction::Add || DemandedFromOps.isOne()) &&
       return I->getOperand(1);
 
     // Otherwise just compute the known bits of the result.
     bool NSW = cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap();
     Known = KnownBits::computeForAddSub(I->getOpcode() == Instruction::Add,
                                         NSW, LHSKnown, RHSKnown);
     break;
   }
+  case Instruction::Mul: {
+    // The LSB of X*Y is set only if (X & 1) == 1 and (Y & 1) == 1.
+    // If we demand exactly one bit N and we have "X * (C' << N)" where C' is
+    // odd (has LSB set), then the left-shifted low bit of X is the answer.
+    if (DemandedMask.isPowerOf2()) {
+      unsigned CTZ = DemandedMask.countTrailingZeros();
+      const APInt *C;
+      if (match(I->getOperand(1), m_APInt(C)) &&
+          C->countTrailingZeros() == CTZ) {
+        Constant *ShiftC = ConstantInt::get(I->getType(), CTZ);
+        Instruction *Shl = BinaryOperator::CreateShl(I->getOperand(0), ShiftC);
+        return InsertNewInstWith(Shl, *I);
+      }
+    }
+    computeKnownBits(I, Known, Depth, CxtI);
+    break;
+  }
   case Instruction::Shl: {
     const APInt *SA;
     if (match(I->getOperand(1), m_APInt(SA))) {
       const APInt *ShrAmt;
       if (match(I->getOperand(0), m_Shr(m_Value(), m_APInt(ShrAmt))))
         if (Instruction *Shr = dyn_cast<Instruction>(I->getOperand(0)))
           if (Value *R = simplifyShrShlDemandedBits(Shr, *ShrAmt, I, *SA,
                                                     DemandedMask, Known))

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
 }
 
+; TODO: Demanded bits does not convert the mul to shift,
+; but the 'and' could be of 'x' directly.
+
 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:    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:    [[TMP1:%.*]] = shl i8 [[X:%.*]], 3
+; CHECK-NEXT:    [[AND:%.*]] = and i8 [[TMP1]], 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:
   %rem = and i32 %mul, 15
   %cmp = icmp eq i32 %rem, 0
   ret i1 %cmp
 }
 
 define i32 @pr40493_neg3(i32 %area) {
 ; CHECK-LABEL: @pr40493_neg3(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[AREA:%.*]], 12
-; CHECK-NEXT:    [[REM:%.*]] = and i32 [[MUL]], 4
+; CHECK-NEXT:    [[TMP0:%.*]] = shl i32 [[AREA:%.*]], 2
+; CHECK-NEXT:    [[REM:%.*]] = and i32 [[TMP0]], 4
 ; CHECK-NEXT:    ret i32 [[REM]]
 ;
 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
 }

llvm/test/Transforms/InstCombine/mul-masked-bits.ll

;
   %a = mul <4 x i32> %x, %x
   %b = and <4 x i32> %a, <i32 2, i32 2, i32 2, i32 undef>
   %c = icmp ne <4 x i32> %b, zeroinitializer
   ret <4 x i1> %c
 }
 
 define i8 @one_demanded_bit(i8 %x) {
 ; CHECK-LABEL: @one_demanded_bit(
-; CHECK-NEXT:    [[M:%.*]] = mul i8 [[X:%.*]], -64
-; CHECK-NEXT:    [[R:%.*]] = or i8 [[M]], -65
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i8 [[X:%.*]], 6
+; CHECK-NEXT:    [[R:%.*]] = or i8 [[TMP1]], -65
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %m = mul i8 %x, 192  ; 0b1100_0000
   %r = or i8 %m, 191   ; 0b1011_1111
   ret i8 %r
 }
 
 define <2 x i8> @one_demanded_bit_splat(<2 x i8> %x) {
 ; CHECK-LABEL: @one_demanded_bit_splat(
-; CHECK-NEXT:    [[M:%.*]] = mul <2 x i8> [[X:%.*]], <i8 -96, i8 -96>
-; CHECK-NEXT:    [[R:%.*]] = and <2 x i8> [[M]], <i8 32, i8 32>
+; CHECK-NEXT:    [[TMP1:%.*]] = shl <2 x i8> [[X:%.*]], <i8 5, i8 5>
+; CHECK-NEXT:    [[R:%.*]] = and <2 x i8> [[TMP1]], <i8 32, i8 32>
 ; CHECK-NEXT:    ret <2 x i8> [[R]]
 ;
   %m = mul <2 x i8> %x, <i8 160, i8 160> ; 0b1010_0000
   %r = and <2 x i8> %m, <i8 32, i8 32>   ; 0b0010_0000
   ret <2 x i8> %r
 }
 
 define i67 @one_demanded_low_bit(i67 %x) {
 ; CHECK-LABEL: @one_demanded_low_bit(
-; CHECK-NEXT:    [[M:%.*]] = mul i67 [[X:%.*]], -63
-; CHECK-NEXT:    [[R:%.*]] = and i67 [[M]], 1
+; CHECK-NEXT:    [[R:%.*]] = and i67 [[X:%.*]], 1
 ; CHECK-NEXT:    ret i67 [[R]]
 ;
   %m = mul i67 %x, -63 ; any odd number will do
   %r = and i67 %m, 1
   ret i67 %r
 }