[InstCombine] Try not to demand low order bits for Add

[foad]

Summary

Don't demand low order bits from the LHS of an Add if:

• they are not demanded in the result, and
• they are known to be zero in the RHS, so they can't possibly overflow and affect higher bit positions

This is intended to avoid a regression from a future patch to change
the order of canonicalization of ADD and AND.

[foad]

This is still WIP because I need to write a better test for it.

Related to D129844.

llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

521–523

This is the important change. The rest is just refactoring.

[foad]

Simpler test diffs

[fhahn]

llvm/test/Transforms/LoopVectorize/X86/float-induction-x86.ll

302

Is dropping exact here intentional?

It looks like we are missing a dedicated instcombine test for this scenario?

[foad]

llvm/test/Transforms/LoopVectorize/X86/float-induction-x86.ll

302

Is dropping exact here intentional?

Yes, because the value we are shifting is now based on SMAX (an arbitrary i64 value) instead of N_VEC which is SMAX & 0x7ffffffffffffff0 (i.e. known to have 0 in the low bits).

[foad]

Add a test case.

[foad]

Ping! The immediate motivation for this is to avoid D130080 (already accepted) causing this regression:

diff --git a/llvm/test/Transforms/InstCombine/cast.ll b/llvm/test/Transforms/InstCombine/cast.ll
index 3fafbd69e032..ec17b24f4c2a 100644
--- a/llvm/test/Transforms/InstCombine/cast.ll
+++ b/llvm/test/Transforms/InstCombine/cast.ll
@@ -680,18 +680,19 @@ define i64 @test49(i64 %A) {
   %C = or i32 %B, 1
   %D = sext i32 %C to i64
   ret i64 %D
 }
 
 define i64 @test50(i64 %x) {
 ; ALL-LABEL: @test50(
 ; ALL-NEXT:    [[TMP1:%.*]] = shl i64 [[X:%.*]], 30
-; ALL-NEXT:    [[TMP2:%.*]] = add i64 [[TMP1]], -4294967296
-; ALL-NEXT:    [[E:%.*]] = ashr i64 [[TMP2]], 32
+; ALL-NEXT:    [[D:%.*]] = and i64 [[TMP1]], -4294967296
+; ALL-NEXT:    [[SEXT:%.*]] = add i64 [[D]], -4294967296
+; ALL-NEXT:    [[E:%.*]] = ashr exact i64 [[SEXT]], 32
 ; ALL-NEXT:    ret i64 [[E]]
 ;
   %a = lshr i64 %x, 2
   %B = trunc i64 %a to i32
   %D = add i32 %B, -1
   %E = sext i32 %D to i64
   ret i64 %E
 }

The current patch fixes it by noticing that the "and" is redundant because it only affects bits that are not demanded by the "add".

[spatel]

Sorry, I didn't notice the dependency between D130080 and this one.

But I'm not seeing test coverage for the change here - the instcombine test is already folded without this patch:
https://alive2.llvm.org/ce/z/RtXYQq

I thought this patch would have an effect like this:
https://alive2.llvm.org/ce/z/XwHTxg
...but I don't see that change.

Should there be at least 2 tests (one each with add and sub) that are improved with this change?

[foad]

Rebase.

[foad]

But I'm not seeing test coverage for the change here - the instcombine test is already folded without this patch:
https://alive2.llvm.org/ce/z/RtXYQq

Yeah, sorry, that was confusing because the test was already being folded by the very transform that I'm working towards removing in D130080. I've added a couple of new tests that should better demonstrate the effect of the current patch.

[spatel]

LGTM

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();
 
+  // Update flags after simplifying an operand based on the fact that some high
+  // order bits are not demanded.
+  auto disableWrapFlagsBasedOnUnusedHighBits = [](Instruction *I,
+                                                  unsigned NLZ) {
+    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 I;
+  };
+
   // 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);
-      }
+      disableWrapFlagsBasedOnUnusedHighBits(I, NLZ);
       return true;
     }
     return false;
   };
 
   switch (I->getOpcode()) {
   default:
     computeKnownBits(I, Known, Depth, CxtI);
case Instruction::SExt: {
      }
 
     // If the sign bit of the input is known set or clear, then we know the
     // top bits of the result.
     Known = InputKnown.sext(BitWidth);
     assert(!Known.hasConflict() && "Bits known to be one AND zero?");
     break;
   }
-  case Instruction::Add:
+  case Instruction::Add: {
     if ((DemandedMask & 1) == 0) {
       // If we do not need the low bit, try to convert bool math to logic:
       // add iN (zext i1 X), (sext i1 Y) --> sext (~X & Y) to iN
       Value *X, *Y;
       if (match(I, m_c_Add(m_OneUse(m_ZExt(m_Value(X))),
                            m_OneUse(m_SExt(m_Value(Y))))) &&
           X->getType()->isIntOrIntVectorTy(1) && X->getType() == Y->getType()) {
         // Truth table for inputs and output signbits:
if ((DemandedMask & 1) == 0) {
         // Y:1  | -1 |  0 |
         //      -----------
         IRBuilderBase::InsertPointGuard Guard(Builder);
         Builder.SetInsertPoint(I);
         Value *Or = Builder.CreateOr(X, Y);
         return Builder.CreateSExt(Or, VTy);
       }
     }
-    [[fallthrough]];
+
+    // Right fill the mask of bits for the operands to demand the most
+    // significant bit and all those below it.
+    unsigned NLZ = DemandedMask.countLeadingZeros();
+    APInt DemandedFromOps = APInt::getLowBitsSet(BitWidth, BitWidth - NLZ);
+    if (ShrinkDemandedConstant(I, 1, DemandedFromOps) ||
+        SimplifyDemandedBits(I, 1, DemandedFromOps, RHSKnown, Depth + 1))
+      return disableWrapFlagsBasedOnUnusedHighBits(I, NLZ);
+
+    // If low order bits are not demanded and known to be zero in one operand,
+    // then we don't need to demand them from the other operand, since they
+    // can't cause overflow into any bits that are demanded in the result.
+    unsigned NTZ = (~DemandedMask & RHSKnown.Zero).countTrailingOnes();
+    APInt DemandedFromLHS = DemandedFromOps;
+    DemandedFromLHS.clearLowBits(NTZ);
+    if (ShrinkDemandedConstant(I, 0, DemandedFromLHS) ||
+        SimplifyDemandedBits(I, 0, DemandedFromLHS, LHSKnown, Depth + 1))
+      return disableWrapFlagsBasedOnUnusedHighBits(I, NLZ);
+
+    // 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);
+    if (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(true, NSW, LHSKnown, RHSKnown);
+    break;
+  }
   case Instruction::Sub: {
-    APInt DemandedFromOps;
-    if (simplifyOperandsBasedOnUnusedHighBits(DemandedFromOps))
-      return I;
+    // Right fill the mask of bits for the operands to demand the most
+    // significant bit and all those below it.
+    unsigned NLZ = DemandedMask.countLeadingZeros();
+    APInt DemandedFromOps = APInt::getLowBitsSet(BitWidth, BitWidth - NLZ);
+    if (ShrinkDemandedConstant(I, 1, DemandedFromOps) ||
+        SimplifyDemandedBits(I, 1, DemandedFromOps, RHSKnown, Depth + 1))
+      return disableWrapFlagsBasedOnUnusedHighBits(I, NLZ);
+    if (ShrinkDemandedConstant(I, 0, DemandedFromOps) ||
+        SimplifyDemandedBits(I, 0, DemandedFromOps, LHSKnown, Depth + 1))
+      return disableWrapFlagsBasedOnUnusedHighBits(I, NLZ);
 
     // 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))
+    if (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);
+    Known = KnownBits::computeForAddSub(false, NSW, LHSKnown, RHSKnown);
     break;
   }
   case Instruction::Mul: {
     APInt DemandedFromOps;
     if (simplifyOperandsBasedOnUnusedHighBits(DemandedFromOps))
       return I;
 
     if (DemandedMask.isPowerOf2()) {

llvm/test/Transforms/InstCombine/add2.ll

;
   %add = add i32 %sel0, %sel1
   ret i32 %add
 }
 
 ; The ADD can't cause overflow out of the low 4 bits so the OR can be removed.
 
 define i32 @add_undemanded_low_bits(i32 %x) {
 ; CHECK-LABEL: @add_undemanded_low_bits(
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[X:%.*]], 15
-; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[OR]], 1616
+; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[X:%.*]], 1616
 ; CHECK-NEXT:    [[SHR:%.*]] = lshr i32 [[ADD]], 4
 ; CHECK-NEXT:    ret i32 [[SHR]]
 ;
   %or = or i32 %x, 15
   %add = add i32 %or, 1616
   %shr = lshr i32 %add, 4
   ret i32 %shr
 }
 
 define i32 @sub_undemanded_low_bits(i32 %x) {
 ; CHECK-LABEL: @sub_undemanded_low_bits(
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[X:%.*]], 15
-; CHECK-NEXT:    [[SUB:%.*]] = add i32 [[OR]], -1616
+; CHECK-NEXT:    [[SUB:%.*]] = add i32 [[X:%.*]], -1616
 ; CHECK-NEXT:    [[SHR:%.*]] = lshr i32 [[SUB]], 4
 ; CHECK-NEXT:    ret i32 [[SHR]]
 ;
   %or = or i32 %x, 15
   %sub = sub i32 %or, 1616
   %shr = lshr i32 %sub, 4
   ret i32 %shr
 }

llvm/test/Transforms/LoopVectorize/X86/float-induction-x86.ll

 ; AUTO_VEC-NEXT:    [[ZEXT:%.*]] = zext i32 [[N]] to i64
 ; AUTO_VEC-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ult i32 [[N]], 32
 ; AUTO_VEC-NEXT:    br i1 [[MIN_ITERS_CHECK]], label [[FOR_BODY:%.*]], label [[VECTOR_PH:%.*]]
 ; AUTO_VEC:       vector.ph:
 ; AUTO_VEC-NEXT:    [[N_VEC:%.*]] = and i64 [[ZEXT]], 4294967264
 ; AUTO_VEC-NEXT:    [[CAST_CRD:%.*]] = sitofp i64 [[N_VEC]] to float
 ; AUTO_VEC-NEXT:    [[TMP0:%.*]] = fmul fast float [[CAST_CRD]], 5.000000e-01
 ; AUTO_VEC-NEXT:    [[IND_END:%.*]] = fadd fast float [[TMP0]], 1.000000e+00
-; AUTO_VEC-NEXT:    [[TMP1:%.*]] = add nsw i64 [[N_VEC]], -32
-; AUTO_VEC-NEXT:    [[TMP2:%.*]] = lshr exact i64 [[TMP1]], 5
+; AUTO_VEC-NEXT:    [[TMP1:%.*]] = add nsw i64 [[ZEXT]], -32
+; AUTO_VEC-NEXT:    [[TMP2:%.*]] = lshr i64 [[TMP1]], 5
 ; AUTO_VEC-NEXT:    [[TMP3:%.*]] = add nuw nsw i64 [[TMP2]], 1
 ; AUTO_VEC-NEXT:    [[XTRAITER:%.*]] = and i64 [[TMP3]], 3
 ; AUTO_VEC-NEXT:    [[TMP4:%.*]] = icmp ult i64 [[TMP1]], 96
 ; AUTO_VEC-NEXT:    br i1 [[TMP4]], label [[MIDDLE_BLOCK_UNR_LCSSA:%.*]], label [[VECTOR_PH_NEW:%.*]]
 ; AUTO_VEC:       vector.ph.new:
 ; AUTO_VEC-NEXT:    [[UNROLL_ITER:%.*]] = and i64 [[TMP3]], 1152921504606846972
 ; AUTO_VEC-NEXT:    br label [[VECTOR_BODY:%.*]]
 ; AUTO_VEC:       vector.body:

 ; AUTO_VEC-NEXT:  entry:
 ; AUTO_VEC-NEXT:    [[SMAX:%.*]] = tail call i64 @llvm.smax.i64(i64 [[N:%.*]], i64 1)
 ; AUTO_VEC-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ult i64 [[SMAX]], 16
 ; AUTO_VEC-NEXT:    br i1 [[MIN_ITERS_CHECK]], label [[FOR_BODY:%.*]], label [[VECTOR_PH:%.*]]
 ; AUTO_VEC:       vector.ph:
 ; AUTO_VEC-NEXT:    [[N_VEC:%.*]] = and i64 [[SMAX]], 9223372036854775792
 ; AUTO_VEC-NEXT:    [[CAST_CRD:%.*]] = sitofp i64 [[N_VEC]] to double
 ; AUTO_VEC-NEXT:    [[TMP0:%.*]] = fmul fast double [[CAST_CRD]], 3.000000e+00
-; AUTO_VEC-NEXT:    [[TMP1:%.*]] = add nsw i64 [[N_VEC]], -16
-; AUTO_VEC-NEXT:    [[TMP2:%.*]] = lshr exact i64 [[TMP1]], 4
+; AUTO_VEC-NEXT:    [[TMP1:%.*]] = add nsw i64 [[SMAX]], -16
+; AUTO_VEC-NEXT:    [[TMP2:%.*]] = lshr i64 [[TMP1]], 4
 ; AUTO_VEC-NEXT:    [[TMP3:%.*]] = add nuw nsw i64 [[TMP2]], 1
 ; AUTO_VEC-NEXT:    [[XTRAITER:%.*]] = and i64 [[TMP3]], 3
 ; AUTO_VEC-NEXT:    [[TMP4:%.*]] = icmp ult i64 [[TMP1]], 48
 ; AUTO_VEC-NEXT:    br i1 [[TMP4]], label [[MIDDLE_BLOCK_UNR_LCSSA:%.*]], label [[VECTOR_PH_NEW:%.*]]
 ; AUTO_VEC:       vector.ph.new:
 ; AUTO_VEC-NEXT:    [[UNROLL_ITER:%.*]] = and i64 [[TMP3]], 2305843009213693948
 ; AUTO_VEC-NEXT:    br label [[VECTOR_BODY:%.*]]
 ; AUTO_VEC:       vector.body:

 ; AUTO_VEC-NEXT:    [[TMP0:%.*]] = zext i32 [[N]] to i64
 ; AUTO_VEC-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ult i32 [[N]], 32
 ; AUTO_VEC-NEXT:    br i1 [[MIN_ITERS_CHECK]], label [[FOR_BODY:%.*]], label [[VECTOR_PH:%.*]]
 ; AUTO_VEC:       vector.ph:
 ; AUTO_VEC-NEXT:    [[N_VEC:%.*]] = and i64 [[TMP0]], 4294967264
 ; AUTO_VEC-NEXT:    [[CAST_CRD:%.*]] = sitofp i64 [[N_VEC]] to float
 ; AUTO_VEC-NEXT:    [[TMP1:%.*]] = fmul reassoc float [[CAST_CRD]], 4.200000e+01
 ; AUTO_VEC-NEXT:    [[IND_END:%.*]] = fadd reassoc float [[TMP1]], 1.000000e+00
-; AUTO_VEC-NEXT:    [[TMP2:%.*]] = add nsw i64 [[N_VEC]], -32
-; AUTO_VEC-NEXT:    [[TMP3:%.*]] = lshr exact i64 [[TMP2]], 5
+; AUTO_VEC-NEXT:    [[TMP2:%.*]] = add nsw i64 [[TMP0]], -32
+; AUTO_VEC-NEXT:    [[TMP3:%.*]] = lshr i64 [[TMP2]], 5
 ; AUTO_VEC-NEXT:    [[TMP4:%.*]] = add nuw nsw i64 [[TMP3]], 1
 ; AUTO_VEC-NEXT:    [[XTRAITER:%.*]] = and i64 [[TMP4]], 1
-; AUTO_VEC-NEXT:    [[TMP5:%.*]] = icmp eq i64 [[TMP2]], 0
+; AUTO_VEC-NEXT:    [[TMP5:%.*]] = icmp ult i64 [[TMP2]], 32
 ; AUTO_VEC-NEXT:    br i1 [[TMP5]], label [[MIDDLE_BLOCK_UNR_LCSSA:%.*]], label [[VECTOR_PH_NEW:%.*]]
 ; AUTO_VEC:       vector.ph.new:
 ; AUTO_VEC-NEXT:    [[UNROLL_ITER:%.*]] = and i64 [[TMP4]], 1152921504606846974
 ; AUTO_VEC-NEXT:    br label [[VECTOR_BODY:%.*]]
 ; AUTO_VEC:       vector.body:
 ; AUTO_VEC-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH_NEW]] ], [ [[INDEX_NEXT_1:%.*]], [[VECTOR_BODY]] ]
 ; AUTO_VEC-NEXT:    [[VEC_IND:%.*]] = phi <8 x float> [ <float 1.000000e+00, float 4.300000e+01, float 8.500000e+01, float 1.270000e+02, float 1.690000e+02, float 2.110000e+02, float 2.530000e+02, float 2.950000e+02>, [[VECTOR_PH_NEW]] ], [ [[VEC_IND_NEXT_1:%.*]], [[VECTOR_BODY]] ]
 ; AUTO_VEC-NEXT:    [[NITER:%.*]] = phi i64 [ 0, [[VECTOR_PH_NEW]] ], [ [[NITER_NEXT_1:%.*]], [[VECTOR_BODY]] ]

llvm/test/Transforms/PhaseOrdering/X86/excessive-unrolling.ll

 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp sgt i32 [[N:%.*]], 0
 ; CHECK-NEXT:    br i1 [[CMP1]], label [[FOR_BODY_PREHEADER:%.*]], label [[EXIT:%.*]]
 ; CHECK:       for.body.preheader:
 ; CHECK-NEXT:    [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[N]] to i64
 ; CHECK-NEXT:    [[MIN_ITERS_CHECK:%.*]] = icmp ult i32 [[N]], 4
 ; CHECK-NEXT:    br i1 [[MIN_ITERS_CHECK]], label [[FOR_BODY_PREHEADER7:%.*]], label [[VECTOR_PH:%.*]]
 ; CHECK:       vector.ph:
 ; CHECK-NEXT:    [[N_VEC:%.*]] = and i64 [[WIDE_TRIP_COUNT]], 4294967292
-; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i64 [[N_VEC]], -4
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr exact i64 [[TMP0]], 2
+; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i64 [[WIDE_TRIP_COUNT]], -4
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i64 [[TMP0]], 2
 ; CHECK-NEXT:    [[TMP2:%.*]] = add nuw nsw i64 [[TMP1]], 1
 ; CHECK-NEXT:    [[XTRAITER:%.*]] = and i64 [[TMP2]], 7
 ; CHECK-NEXT:    [[TMP3:%.*]] = icmp ult i64 [[TMP0]], 28
 ; CHECK-NEXT:    br i1 [[TMP3]], label [[MIDDLE_BLOCK_UNR_LCSSA:%.*]], label [[VECTOR_PH_NEW:%.*]]
 ; CHECK:       vector.ph.new:
 ; CHECK-NEXT:    [[UNROLL_ITER:%.*]] = and i64 [[TMP2]], 9223372036854775800
 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
 ; CHECK:       vector.body: