[InstCombine] Provide a way to calculate KnownZero/One for Add/Sub in SimplifyDemandedUseBits without recursing into ComputeKnownBits

[craig.topper]

Summary

SimplifyDemandedUseBits for Add/Sub already recursed down LHS and RHS for simplifying bits. If that didn't provide any simplifications we fall back to calling computeKnownBits which will recurse again. Instead just take the known bits for LHS and RHS we already have and call into a new function in ValueTracking that can calculate the known bits given the LHS/RHS bits.

[spatel]

lib/Analysis/ValueTracking.cpp

309

Can we call these params RHSKnownZero and RHSKnownOne at this point?

lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

551

"commute" confused me here. "compute"?
As in:
Compute more known bits based on the existing known bits and the fact that this is an add/sub.

[craig.topper]

lib/Analysis/ValueTracking.cpp

309

They don't contain the RHS known bits at the start of the call so it could be misleading. We're only passing it in because computeKnownBits preallocated them and we want to reuse that.

lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

551

Typo. Maybe I've spent too much time commuting instructions in the backend.

[craig.topper]

Fix comment

[spatel]

LGTM.

include/llvm/Analysis/ValueTracking.h

template <typename T> class ArrayRef;
   /// same width as the vector element, and the bit is set only if it is true
   /// for all of the elements in the vector.
   void computeKnownBits(const Value *V, APInt &KnownZero, APInt &KnownOne,
                         const DataLayout &DL, unsigned Depth = 0,
                         AssumptionCache *AC = nullptr,
                         const Instruction *CxtI = nullptr,
                         const DominatorTree *DT = nullptr,
                         OptimizationRemarkEmitter *ORE = nullptr);
+  /// Compute known bits for add/sub using LHS/RHS known bits.
+  void computeKnownBitsForAddSub(bool Add, bool NSW,
+                                 APInt &KnownZero, APInt &KnownOne,
+                                 APInt &LHSKnownZero, APInt &LHSKnownOne,
+                                 APInt &RHSKnownZero, APInt &RHSKnownOne);
   /// Compute known bits from the range metadata.
   /// \p KnownZero the set of bits that are known to be zero
   /// \p KnownOne the set of bits that are known to be one
   void computeKnownBitsFromRangeMetadata(const MDNode &Ranges,
                                          APInt &KnownZero, APInt &KnownOne);
   /// Return true if LHS and RHS have no common bits set.
   bool haveNoCommonBitsSet(const Value *LHS, const Value *RHS,
                            const DataLayout &DL,

lib/Analysis/ValueTracking.cpp

 
 unsigned llvm::ComputeNumSignBits(const Value *V, const DataLayout &DL,
                                   unsigned Depth, AssumptionCache *AC,
                                   const Instruction *CxtI,
                                   const DominatorTree *DT) {
   return ::ComputeNumSignBits(V, Depth, Query(DL, AC, safeCxtI(V, CxtI), DT));
 }
 
-static void computeKnownBitsAddSub(bool Add, const Value *Op0, const Value *Op1,
-                                   bool NSW,
+/// Compute known bits for add/sub using LHS/RHS known bits.
+void llvm::computeKnownBitsForAddSub(bool Add, bool NSW,
                                      APInt &KnownZero, APInt &KnownOne,
-                                   APInt &KnownZero2, APInt &KnownOne2,
-                                   unsigned Depth, const Query &Q) {
-  unsigned BitWidth = KnownZero.getBitWidth();
-
-  // If an initial sequence of bits in the result is not needed, the
-  // corresponding bits in the operands are not needed.
-  APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0);
-  computeKnownBits(Op0, LHSKnownZero, LHSKnownOne, Depth + 1, Q);
-  computeKnownBits(Op1, KnownZero2, KnownOne2, Depth + 1, Q);
-
+                                     APInt &LHSKnownZero, APInt &LHSKnownOne,
+                                     APInt &RHSKnownZero, APInt &RHSKnownOne) {
   // Carry in a 1 for a subtract, rather than a 0.
-  APInt CarryIn(BitWidth, 0);
+  APInt CarryIn(KnownZero.getBitWidth(), 0);
   if (!Add) {
     // Sum = LHS + ~RHS + 1
-    std::swap(KnownZero2, KnownOne2);
+    std::swap(RHSKnownZero, RHSKnownOne);
     CarryIn.setBit(0);
   }
 
-  APInt PossibleSumZero = ~LHSKnownZero + ~KnownZero2 + CarryIn;
-  APInt PossibleSumOne = LHSKnownOne + KnownOne2 + CarryIn;
+  APInt PossibleSumZero = ~LHSKnownZero + ~RHSKnownZero + CarryIn;
+  APInt PossibleSumOne = LHSKnownOne + RHSKnownOne + CarryIn;
 
   // Compute known bits of the carry.
-  APInt CarryKnownZero = ~(PossibleSumZero ^ LHSKnownZero ^ KnownZero2);
-  APInt CarryKnownOne = PossibleSumOne ^ LHSKnownOne ^ KnownOne2;
+  APInt CarryKnownZero = ~(PossibleSumZero ^ LHSKnownZero ^ RHSKnownZero);
+  APInt CarryKnownOne = PossibleSumOne ^ LHSKnownOne ^ RHSKnownOne;
 
   // Compute set of known bits (where all three relevant bits are known).
   APInt LHSKnown = LHSKnownZero | LHSKnownOne;
-  APInt RHSKnown = KnownZero2 | KnownOne2;
+  APInt RHSKnown = RHSKnownZero | RHSKnownOne;
   APInt CarryKnown = CarryKnownZero | CarryKnownOne;
   APInt Known = LHSKnown & RHSKnown & CarryKnown;
 
   assert((PossibleSumZero & Known) == (PossibleSumOne & Known) &&
          "known bits of sum differ");
 
   // Compute known bits of the result.
   KnownZero = ~PossibleSumOne & Known;
   KnownOne = PossibleSumOne & Known;
 
   // Are we still trying to solve for the sign bit?
   if (!Known.isNegative()) {
     if (NSW) {
       // Adding two non-negative numbers, or subtracting a negative number from
       // a non-negative one, can't wrap into negative.
-      if (LHSKnownZero.isNegative() && KnownZero2.isNegative())
+      if (LHSKnownZero.isNegative() && RHSKnownZero.isNegative())
         KnownZero.setSignBit();
       // Adding two negative numbers, or subtracting a non-negative number from
       // a negative one, can't wrap into non-negative.
-      else if (LHSKnownOne.isNegative() && KnownOne2.isNegative())
+      else if (LHSKnownOne.isNegative() && RHSKnownOne.isNegative())
         KnownOne.setSignBit();
     }
   }
+
+  // Put the RHS/LHS back how we found them.
+  if (!Add) {
+    std::swap(RHSKnownZero, RHSKnownOne);
+  }
+}
+
+static void computeKnownBitsAddSub(bool Add, const Value *Op0, const Value *Op1,
+                                   bool NSW,
+                                   APInt &KnownZero, APInt &KnownOne,
+                                   APInt &KnownZero2, APInt &KnownOne2,
+                                   unsigned Depth, const Query &Q) {
+  unsigned BitWidth = KnownZero.getBitWidth();
+
+  // If an initial sequence of bits in the result is not needed, the
+  // corresponding bits in the operands are not needed.
+  APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0);
+  computeKnownBits(Op0, LHSKnownZero, LHSKnownOne, Depth + 1, Q);
+  computeKnownBits(Op1, KnownZero2, KnownOne2, Depth + 1, Q);
+
+  computeKnownBitsForAddSub(Add, NSW, KnownZero, KnownOne, LHSKnownZero,
+                            LHSKnownOne, KnownZero2, KnownOne2);
 }
 
 static void computeKnownBitsMul(const Value *Op0, const Value *Op1, bool NSW,
                                 APInt &KnownZero, APInt &KnownOne,
                                 APInt &KnownZero2, APInt &KnownOne2,
                                 unsigned Depth, const Query &Q) {
   unsigned BitWidth = KnownZero.getBitWidth();
   computeKnownBits(Op1, KnownZero, KnownOne, Depth + 1, Q);

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;
       }
     }
 
-    // Otherwise just hand the add/sub off to computeKnownBits to fill in
-    // the known zeros and ones.
-    computeKnownBits(V, KnownZero, KnownOne, Depth, CxtI);
+    // Otherwise commute the known bits using the RHS/LHS known bits.
+    bool NSW = cast<OverflowingBinaryOperator>(I)->hasNoSignedWrap();
+    computeKnownBitsForAddSub(V, NSW, KnownZero, KnownOne, LHSKnownZero,
+                              LHSKnownOne, RHSKnownZero, RHSKnownOne);
     break;
   }
   case Instruction::Shl:
     if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) {
       {
         Value *VarX; ConstantInt *C1;
         if (match(I->getOperand(0), m_Shr(m_Value(VarX), m_ConstantInt(C1)))) {
           Instruction *Shr = cast<Instruction>(I->getOperand(0));