[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.

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 (SimplifyDemandedBits(I->getOperandUse(0), DemandedFromOps,
                                LHSKnownZero, LHSKnownOne, Depth + 1) ||
           ShrinkDemandedConstant(I, 1, DemandedFromOps) ||
           SimplifyDemandedBits(I->getOperandUse(1), DemandedFromOps,
-                               LHSKnownZero, LHSKnownOne, Depth + 1)) {
+                               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: