[InstCombine] Teach SimplifyDemandedUseBits that adding or subtractings 0s from every bit below the highest demanded bit can be simplified

[craig.topper]

Summary

If we are adding/subtractings 0s below the highest demanded bit we can just use the other operand and remove the operation.

My primary motivation is observing that we can call ShrinkDemandedConstant for the add/sub and create a 0 constant, rather than removing the add completely. In the case I saw, we modified the constant on an add instruction to a 0, but the add is not put into the worklist. So we didn't revisit it until the next InstCombine iteration. This caused an IR modification to remove add and a subsequent iteration to be ran.

With this change we get bypass the add in the first iteration and prevent the second iteration from changing anything.

Not sure how to test this because we do eventually optimize it. Is there any way to bound instcombine iterations from the command line?

[spatel]

In D31094, @efriedma suggested a debug counter to make this visible in a test.

[craig.topper]

Yeah I saw that. Should we add a debug counter around the top level worklist loop? The semantics of the "skip" part of the counter wouldn't make sense though.

[craig.topper]

Found another way of testing this particular transform.

[spatel]

LGTM.

[spatel]

test/Transforms/InstCombine/and2.ll

125 ↗

(On Diff #93705)

This comment (copy/pasted below too) confused me. Shouldn't it be:
"The add in this test is unnecessary because the LSBs of the RHS are 0 and we do not consume those bits."

[craig.topper]

test/Transforms/InstCombine/and2.ll

125 ↗

(On Diff #93705)

The comment is bad given the immediate used on the and. The optimization is valid even if the and immediate is 255. I'll try to clarify it.

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

case Instruction::Sub: {
     if (NLZ > 0) {
       // 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, LHSKnownZero, LHSKnownOne,
                                Depth + 1) ||
           ShrinkDemandedConstant(I, 1, DemandedFromOps) ||
-          SimplifyDemandedBits(I, 1, DemandedFromOps, LHSKnownZero, LHSKnownOne,
+          SimplifyDemandedBits(I, 1, DemandedFromOps, RHSKnownZero, RHSKnownOne,
                                Depth + 1)) {
         // 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);
         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 & RHSKnownZero) == DemandedFromOps)
+        return I->getOperand(0);
+      // We can't do this with the LHS for subtraction.
+      if (I->getOpcode() == Instruction::Add &&
+          (DemandedFromOps & LHSKnownZero) == DemandedFromOps)
+        return I->getOperand(1);
     }
 
     // Otherwise just hand the add/sub off to computeKnownBits to fill in
     // the known zeros and ones.
     computeKnownBits(V, KnownZero, KnownOne, Depth, CxtI);
     break;
   }
   case Instruction::Shl:

llvm/trunk/test/Transforms/InstCombine/and2.ll

 ; CHECK-NEXT:    ret i64 [[ADD]]
 ;
   %sub = sub nsw i64 0, %x
   %and = and i64 %sub, 1
   %add = add i64 %sub, %and
   ret i64 %add
 }
 
-; The add in this test is unnecessary because the LSBs of the RHS are 0 and we only consume those bits.
+; The add in this test is unnecessary because the LSBs of the LHS are 0 and the 'and' only consumes bits from those LSBs. It doesn't matter what happens to the upper bits.
 define i32 @test11(i32 %a, i32 %b) {
 ; CHECK-LABEL: @test11(
 ; CHECK-NEXT:    [[X:%.*]] = shl i32 [[A:%.*]], 8
-; CHECK-NEXT:    [[Y:%.*]] = add i32 [[X]], [[B:%.*]]
-; CHECK-NEXT:    [[Z:%.*]] = and i32 [[Y]], 128
+; CHECK-NEXT:    [[Z:%.*]] = and i32 [[B:%.*]], 128
 ; CHECK-NEXT:    [[W:%.*]] = mul i32 [[Z]], [[X]]
 ; CHECK-NEXT:    ret i32 [[W]]
 ;
   %x = shl i32 %a, 8
   %y = add i32 %x, %b
   %z = and i32 %y, 128
   %w = mul i32 %z, %x ; to keep the shift from being removed
   ret i32 %w
 }
 
-; The add in this test is unnecessary because the LSBs of the RHS are 0 and we only consume those bits.
+; The add in this test is unnecessary because the LSBs of the RHS are 0 and the 'and' only consumes bits from those LSBs. It doesn't matter what happens to the upper bits.
 define i32 @test12(i32 %a, i32 %b) {
 ; CHECK-LABEL: @test12(
 ; CHECK-NEXT:    [[X:%.*]] = shl i32 [[A:%.*]], 8
-; CHECK-NEXT:    [[Y:%.*]] = add i32 [[X]], [[B:%.*]]
-; CHECK-NEXT:    [[Z:%.*]] = and i32 [[Y]], 128
+; CHECK-NEXT:    [[Z:%.*]] = and i32 [[B:%.*]], 128
 ; CHECK-NEXT:    [[W:%.*]] = mul i32 [[Z]], [[X]]
 ; CHECK-NEXT:    ret i32 [[W]]
 ;
   %x = shl i32 %a, 8
   %y = add i32 %b, %x
   %z = and i32 %y, 128
   %w = mul i32 %z, %x ; to keep the shift from being removed
   ret i32 %w
 }
 
-; The sub in this test is unnecessary because the LSBs of the RHS are 0 and we only consume those bits.
+; The sub in this test is unnecessary because the LSBs of the RHS are 0 and the 'and' only consumes bits from those LSBs. It doesn't matter what happens to the upper bits.
 define i32 @test13(i32 %a, i32 %b) {
 ; CHECK-LABEL: @test13(
 ; CHECK-NEXT:    [[X:%.*]] = shl i32 [[A:%.*]], 8
-; CHECK-NEXT:    [[Y:%.*]] = sub i32 [[B:%.*]], [[X]]
-; CHECK-NEXT:    [[Z:%.*]] = and i32 [[Y]], 128
+; CHECK-NEXT:    [[Z:%.*]] = and i32 [[B:%.*]], 128
 ; CHECK-NEXT:    [[W:%.*]] = mul i32 [[Z]], [[X]]
 ; CHECK-NEXT:    ret i32 [[W]]
 ;
   %x = shl i32 %a, 8
   %y = sub i32 %b, %x
   %z = and i32 %y, 128
   %w = mul i32 %z, %x ; to keep the shift from being removed
   ret i32 %w
 }
 
-; The sub in this test cannot be removed because we need to keep the negation of %b
+; The sub in this test cannot be removed because we need to keep the negation of %b. TODO: But we should be able to replace the LHS of it with a 0.
 define i32 @test14(i32 %a, i32 %b) {
 ; CHECK-LABEL: @test14(
 ; CHECK-NEXT:    [[X:%.*]] = shl i32 [[A:%.*]], 8
 ; CHECK-NEXT:    [[Y:%.*]] = sub i32 [[X]], [[B:%.*]]
 ; CHECK-NEXT:    [[Z:%.*]] = and i32 [[Y]], 128
 ; CHECK-NEXT:    [[W:%.*]] = mul i32 [[Z]], [[X]]
 ; CHECK-NEXT:    ret i32 [[W]]
 ;
   %x = shl i32 %a, 8
   %y = sub i32 %x, %b
   %z = and i32 %y, 128
   %w = mul i32 %z, %x ; to keep the shift from being removed
   ret i32 %w
 }