[InstCombine] reduce mul operands based on undemanded high bits

[spatel]

Summary

We already do this in SDAG, but mul was left out of the fold for unused high bits in IR.
The high bits of a mul's operands do not change the low bits of the result:
https://alive2.llvm.org/ce/z/XRj5Ek

Verify some test diffs to confirm that they are correct:
https://alive2.llvm.org/ce/z/y_W8DW
https://alive2.llvm.org/ce/z/7DM5uf
https://alive2.llvm.org/ce/z/GDiHCK

This gets a fold that was presumed not possible in D114272:
https://alive2.llvm.org/ce/z/tAN-WY

Removing nsw/nuw is needed for general correctness (and is also done in the codegen version), but we might be able to recover more of those with better analysis.

[lebedev.ri]

LGTM, thank you.
The same is true for and/or/xor.

[spatel]

In D119369#3308910, @lebedev.ri wrote:

LGTM, thank you.

Thanks!

The same is true for and/or/xor.

Yes - those are more general, Any undemanded bit (not just high bits) in the result is also undemanded in the operands. Those appear to be handled optimally already.

llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

Value *InstCombinerImpl::SimplifyDemandedUseBits(Value *V, APInt DemandedMask,
 
   // If this is the root being simplified, allow it to have multiple uses,
   // just set the DemandedMask to all bits so that we can try to simplify the
   // operands.  This allows visitTruncInst (for example) to simplify the
   // operand of a trunc without duplicating all the logic below.
   if (Depth == 0 && !V->hasOneUse())
     DemandedMask.setAllBits();
 
+  // If the high-bits of an ADD/SUB/MUL are not demanded, then we do not care
+  // about the high bits of the operands.
+  auto simplifyOperandsBasedOnUnusedHighBits = [&](APInt &DemandedFromOps) {
+    unsigned NLZ = DemandedMask.countLeadingZeros();
+    // Right fill the mask of bits for the operands to demand the most
+    // significant bit and all those below it.
+    DemandedFromOps = APInt::getLowBitsSet(BitWidth, BitWidth - NLZ);
+    if (ShrinkDemandedConstant(I, 0, DemandedFromOps) ||
+        SimplifyDemandedBits(I, 0, DemandedFromOps, LHSKnown, Depth + 1) ||
+        ShrinkDemandedConstant(I, 1, DemandedFromOps) ||
+        SimplifyDemandedBits(I, 1, DemandedFromOps, RHSKnown, Depth + 1)) {
+      if (NLZ > 0) {
+        // Disable the nsw and nuw flags here: We can no longer guarantee that
+        // we won't wrap after simplification. Removing the nsw/nuw flags is
+        // legal here because the top bit is not demanded.
+        I->setHasNoSignedWrap(false);
+        I->setHasNoUnsignedWrap(false);
+      }
+      return true;
+    }
+    return false;
+  };
+
   switch (I->getOpcode()) {
   default:
     computeKnownBits(I, Known, Depth, CxtI);
     break;
   case Instruction::And: {
     // If either the LHS or the RHS are Zero, the result is zero.
     if (SimplifyDemandedBits(I, 1, DemandedMask, RHSKnown, Depth + 1) ||
         SimplifyDemandedBits(I, 0, DemandedMask & ~RHSKnown.Zero, LHSKnown,
if ((DemandedMask & 1) == 0) {
         IRBuilderBase::InsertPointGuard Guard(Builder);
         Builder.SetInsertPoint(I);
         Value *Or = Builder.CreateOr(X, Y);
         return Builder.CreateSExt(Or, VTy);
       }
     }
     LLVM_FALLTHROUGH;
   case Instruction::Sub: {
-    /// If the high-bits of an ADD/SUB are not demanded, then we do not care
-    /// about the high bits of the operands.
-    unsigned NLZ = DemandedMask.countLeadingZeros();
-    // Right fill the mask of bits for this ADD/SUB to demand the most
-    // significant bit and all those below it.
-    APInt DemandedFromOps(APInt::getLowBitsSet(BitWidth, BitWidth-NLZ));
-    if (ShrinkDemandedConstant(I, 0, DemandedFromOps) ||
-        SimplifyDemandedBits(I, 0, DemandedFromOps, LHSKnown, Depth + 1) ||
-        ShrinkDemandedConstant(I, 1, DemandedFromOps) ||
-        SimplifyDemandedBits(I, 1, DemandedFromOps, RHSKnown, Depth + 1)) {
-      if (NLZ > 0) {
-        // Disable the nsw and nuw flags here: We can no longer guarantee that
-        // we won't wrap after simplification. Removing the nsw/nuw flags is
-        // legal here because the top bit is not demanded.
-        BinaryOperator &BinOP = *cast<BinaryOperator>(I);
-        BinOP.setHasNoSignedWrap(false);
-        BinOP.setHasNoUnsignedWrap(false);
-      }
+    APInt DemandedFromOps;
+    if (simplifyOperandsBasedOnUnusedHighBits(DemandedFromOps))
       return I;
-    }
 
     // If we are known to be adding/subtracting zeros to every bit below
     // the highest demanded bit, we just return the other side.
     if (DemandedFromOps.isSubsetOf(RHSKnown.Zero))
       return I->getOperand(0);
     // We can't do this with the LHS for subtraction, unless we are only
     // demanding the LSB.
     if ((I->getOpcode() == Instruction::Add || DemandedFromOps.isOne()) &&
         DemandedFromOps.isSubsetOf(LHSKnown.Zero))
       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: {
+    APInt DemandedFromOps;
+    if (simplifyOperandsBasedOnUnusedHighBits(DemandedFromOps))
+      return I;
+
     if (DemandedMask.isPowerOf2()) {
       // 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.
       unsigned CTZ = DemandedMask.countTrailingZeros();
       const APInt *C;
       if (match(I->getOperand(1), m_APInt(C)) &&
           C->countTrailingZeros() == CTZ) {

llvm/test/Transforms/InstCombine/and-or.ll

;
   %sh = lshr <2 x i8> %a, <i8 6, i8 6>
   %xor = xor <2 x i8> %sh, %b
   %and = and <2 x i8> %xor, <i8 3, i8 3>
   ret <2 x i8> %and
 }
 
 define i8 @and_xor_hoist_mask_commute(i8 %a, i8 %b) {
 ; CHECK-LABEL: @and_xor_hoist_mask_commute(
-; CHECK-NEXT:    [[C:%.*]] = mul i8 [[B:%.*]], 43
+; CHECK-NEXT:    [[C:%.*]] = mul i8 [[B:%.*]], 3
 ; CHECK-NEXT:    [[SH:%.*]] = lshr i8 [[A:%.*]], 6
 ; CHECK-NEXT:    [[C_MASKED:%.*]] = and i8 [[C]], 3
 ; CHECK-NEXT:    [[AND:%.*]] = xor i8 [[C_MASKED]], [[SH]]
 ; CHECK-NEXT:    ret i8 [[AND]]
 ;
   %c = mul i8 %b, 43 ; thwart complexity-based ordering
   %sh = lshr i8 %a, 6
   %xor = xor i8 %c, %sh
   %and = and i8 %xor, 3
   ret i8 %and
 }
 
 define <2 x i8> @and_or_hoist_mask_commute_vec_splat(<2 x i8> %a, <2 x i8> %b) {
 ; CHECK-LABEL: @and_or_hoist_mask_commute_vec_splat(
-; CHECK-NEXT:    [[C:%.*]] = mul <2 x i8> [[B:%.*]], <i8 43, i8 43>
+; CHECK-NEXT:    [[C:%.*]] = mul <2 x i8> [[B:%.*]], <i8 3, i8 3>
 ; CHECK-NEXT:    [[SH:%.*]] = lshr <2 x i8> [[A:%.*]], <i8 6, i8 6>
 ; CHECK-NEXT:    [[C_MASKED:%.*]] = and <2 x i8> [[C]], <i8 3, i8 3>
 ; CHECK-NEXT:    [[AND:%.*]] = or <2 x i8> [[C_MASKED]], [[SH]]
 ; CHECK-NEXT:    ret <2 x i8> [[AND]]
 ;
   %c = mul <2 x i8> %b, <i8 43, i8 43> ; thwart complexity-based ordering
   %sh = lshr <2 x i8> %a, <i8 6, i8 6>
   %or = or <2 x i8> %c, %sh

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

;
   %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:    [[TMP1:%.*]] = shl i8 [[X:%.*]], 3
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[TMP1]], 8
+; CHECK-NEXT:    [[MUL:%.*]] = shl i8 [[X:%.*]], 3
+; 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
;
   %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:    [[MUL:%.*]] = mul i8 [[X:%.*]], 12
 ; 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:    [[TMP1:%.*]] = and i32 [[AREA:%.*]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %mul = mul i32 %area, 12
   %rem = and i32 %mul, 4
   %cmp = icmp eq i32 %rem, 0
   ret i1 %cmp
 }
 
 define i1 @pr40493_neg1(i32 %area) {
 ; CHECK-LABEL: @pr40493_neg1(
-; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[AREA:%.*]], 11
+; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[AREA:%.*]], 3
 ; CHECK-NEXT:    [[REM:%.*]] = and i32 [[MUL]], 4
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[REM]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %mul = mul i32 %area, 11
   %rem = and i32 %mul, 4
   %cmp = icmp eq i32 %rem, 0
   ret i1 %cmp
;
   %mul = mul i32 %area, 12
   %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:    [[TMP1:%.*]] = shl i32 [[AREA:%.*]], 2
-; CHECK-NEXT:    [[REM:%.*]] = and i32 [[TMP1]], 4
+; CHECK-NEXT:    [[MUL:%.*]] = shl i32 [[AREA:%.*]], 2
+; CHECK-NEXT:    [[REM:%.*]] = and i32 [[MUL]], 4
 ; CHECK-NEXT:    ret i32 [[REM]]
 ;
   %mul = mul i32 %area, 12
   %rem = and i32 %mul, 4
   ret i32 %rem
 }
 
 define <4 x i1> @pr40493_vec1(<4 x i32> %area) {
;
   %mul = mul <4 x i32> %area, <i32 12, i32 12, i32 20, i32 20>
   %rem = and <4 x i32> %mul, <i32 2, i32 4, i32 2, i32 4>
   %cmp = icmp eq <4 x i32> %rem, zeroinitializer
   ret <4 x i1> %cmp
 }
 
 define i1 @pr51551(i32 %x, i32 %y) {
 ; CHECK-LABEL: @pr51551(
-; CHECK-NEXT:    [[T0:%.*]] = and i32 [[Y:%.*]], -8
-; CHECK-NEXT:    [[T1:%.*]] = or i32 [[T0]], 1
-; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i32 [[T1]], [[X:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[MUL]], 3
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 3
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %t0 = and i32 %y, -7
   %t1 = or i32 %t0, 1
   %mul = mul nsw i32 %t1, %x
   %and = and i32 %mul, 3
   %cmp = icmp eq i32 %and, 0
   ret i1 %cmp
 }
 
 define i1 @pr51551_2(i32 %x, i32 %y) {
 ; CHECK-LABEL: @pr51551_2(
-; CHECK-NEXT:    [[T0:%.*]] = and i32 [[Y:%.*]], -8
-; CHECK-NEXT:    [[T1:%.*]] = or i32 [[T0]], 1
-; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i32 [[T1]], [[X:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[MUL]], 1
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %t0 = and i32 %y, -7
   %t1 = or i32 %t0, 1
   %mul = mul nsw i32 %t1, %x
   %and = and i32 %mul, 1
   %cmp = icmp eq i32 %and, 0
   ret i1 %cmp
 }
 
 define i1 @pr51551_neg1(i32 %x, i32 %y) {
 ; CHECK-LABEL: @pr51551_neg1(
-; CHECK-NEXT:    [[T0:%.*]] = and i32 [[Y:%.*]], -4
+; CHECK-NEXT:    [[T0:%.*]] = and i32 [[Y:%.*]], 4
 ; CHECK-NEXT:    [[T1:%.*]] = or i32 [[T0]], 1
-; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i32 [[T1]], [[X:%.*]]
+; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[T1]], [[X:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[MUL]], 7
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %t0 = and i32 %y, -3
   %t1 = or i32 %t0, 1
   %mul = mul nsw i32 %t1, %x
   %and = and i32 %mul, 7
   %cmp = icmp eq i32 %and, 0
   ret i1 %cmp
 }
 
 define i1 @pr51551_neg2(i32 %x, i32 %y) {
 ; CHECK-LABEL: @pr51551_neg2(
-; CHECK-NEXT:    [[T0:%.*]] = and i32 [[Y:%.*]], -7
-; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i32 [[T0]], [[X:%.*]]
+; CHECK-NEXT:    [[T0:%.*]] = and i32 [[Y:%.*]], 1
+; CHECK-NEXT:    [[MUL:%.*]] = mul nuw i32 [[T0]], [[X:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[MUL]], 7
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %t0 = and i32 %y, -7
   %mul = mul nsw i32 %t0, %x
   %and = and i32 %mul, 7
   %cmp = icmp eq i32 %and, 0
   ret i1 %cmp
 }
 
 define i32 @pr51551_demand3bits(i32 %x, i32 %y) {
 ; CHECK-LABEL: @pr51551_demand3bits(
-; CHECK-NEXT:    [[T0:%.*]] = and i32 [[Y:%.*]], -8
-; CHECK-NEXT:    [[T1:%.*]] = or i32 [[T0]], 1
-; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i32 [[T1]], [[X:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[MUL]], 7
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 7
 ; CHECK-NEXT:    ret i32 [[AND]]
 ;
   %t0 = and i32 %y, -7
   %t1 = or i32 %t0, 1
   %mul = mul nsw i32 %t1, %x
   %and = and i32 %mul, 7
   ret i32 %and
 }

llvm/test/Transforms/InstCombine/mul-inseltpoison.ll

 ;
   %add = add <2 x i32> %a0, <i32 16, i32 32>
   %mul = mul <2 x i32> %add, <i32 -4, i32 undef>
   ret <2 x i32> %mul
 }
 
 define i32 @mulmuladd2(i32 %a0, i32 %a1) {
 ; CHECK-LABEL: @mulmuladd2(
-; CHECK-NEXT:    [[ADD_NEG:%.*]] = sub i32 -16, [[A0:%.*]]
+; CHECK-NEXT:    [[ADD_NEG:%.*]] = sub i32 1073741808, [[A0:%.*]]
 ; CHECK-NEXT:    [[MUL1_NEG:%.*]] = mul i32 [[ADD_NEG]], [[A1:%.*]]
 ; CHECK-NEXT:    [[MUL2:%.*]] = shl i32 [[MUL1_NEG]], 2
 ; CHECK-NEXT:    ret i32 [[MUL2]]
 ;
   %add = add i32 %a0, 16
   %mul1 = mul i32 %add, %a1
   %mul2 = mul i32 %mul1, -4
   ret i32 %mul2

llvm/test/Transforms/InstCombine/mul.ll

 ;
   %add = add <2 x i32> %a0, <i32 16, i32 32>
   %mul = mul <2 x i32> %add, <i32 -4, i32 undef>
   ret <2 x i32> %mul
 }
 
 define i32 @mulmuladd2(i32 %a0, i32 %a1) {
 ; CHECK-LABEL: @mulmuladd2(
-; CHECK-NEXT:    [[ADD_NEG:%.*]] = sub i32 -16, [[A0:%.*]]
+; CHECK-NEXT:    [[ADD_NEG:%.*]] = sub i32 1073741808, [[A0:%.*]]
 ; CHECK-NEXT:    [[MUL1_NEG:%.*]] = mul i32 [[ADD_NEG]], [[A1:%.*]]
 ; CHECK-NEXT:    [[MUL2:%.*]] = shl i32 [[MUL1_NEG]], 2
 ; CHECK-NEXT:    ret i32 [[MUL2]]
 ;
   %add = add i32 %a0, 16
   %mul1 = mul i32 %add, %a1
   %mul2 = mul i32 %mul1, -4
   ret i32 %mul2