[ValueTracking] Compute known bits for add/sub with less temporary APInts

[craig.topper]

Summary

The previous operation used quite a few temporary objects which can allocate memory for larger than 64-bit types and made no use of the storage already allocated storage for KnownZeroes/Ones.

This patch tries to make more intelligent reuse of the objects. Computing the overall known bits is still kind of bad as the OR operation for LHS and RHS both create a temporary to hold the OR result.

lib/Analysis/ValueTracking.cpp

void llvm::computeKnownBitsForAddSub(bool Add, bool NSW,
   // Carry in a 1 for a subtract, rather than a 0.
   uint64_t CarryIn = 0;
   if (!Add) {
     // Sum = LHS + ~RHS + 1
     std::swap(RHSKnownZero, RHSKnownOne);
     CarryIn = 1;
   }
 
-  APInt PossibleSumZero = ~LHSKnownZero + ~RHSKnownZero + CarryIn;
-  APInt PossibleSumOne = LHSKnownOne + RHSKnownOne + CarryIn;
+  // Flip the known zeroes so we can add them.
+  LHSKnownZero.flipAllBits();
+  RHSKnownZero.flipAllBits();
+
+  // Create a sum for the known zeros.
+  KnownZero |= CarryIn;
+  KnownZero += LHSKnownZero;
+  KnownZero += RHSKnownZero;
+
+  // Restore the known zeroes and flip the sum.
+  LHSKnownZero.flipAllBits();
+  RHSKnownZero.flipAllBits();
+  KnownZero.flipAllBits();
+
+  // Create a sum for the known ones.
+  KnownOne |= CarryIn;
+  KnownOne += RHSKnownOne;
+  KnownOne += LHSKnownOne;
 
   // Compute known bits of the carry.
-  APInt CarryKnownZero = ~(PossibleSumZero ^ LHSKnownZero ^ RHSKnownZero);
-  APInt CarryKnownOne = PossibleSumOne ^ LHSKnownOne ^ RHSKnownOne;
+  APInt CarryKnownZero = KnownZero ^ LHSKnownZero ^ RHSKnownZero;
+  APInt CarryKnownOne = KnownOne ^ LHSKnownOne ^ RHSKnownOne;
 
   // Compute set of known bits (where all three relevant bits are known).
-  APInt LHSKnown = LHSKnownZero | LHSKnownOne;
-  APInt RHSKnown = RHSKnownZero | RHSKnownOne;
-  APInt CarryKnown = CarryKnownZero | CarryKnownOne;
-  APInt Known = LHSKnown & RHSKnown & CarryKnown;
-
-  assert((PossibleSumZero & Known) == (PossibleSumOne & Known) &&
+  APInt Known = std::move(CarryKnownZero) | std::move(CarryKnownOne);
+  Known &= LHSKnownZero | LHSKnownOne;
+  Known &= RHSKnownZero | RHSKnownOne;
+  assert((~KnownZero & Known) == (KnownOne & Known) &&
          "known bits of sum differ");
 
-  // Compute known bits of the result.
-  KnownZero = ~PossibleSumOne & Known;
-  KnownOne = PossibleSumOne & Known;
+  // Bits of sums are only known if all input bits were known.
+  KnownZero &= Known;
+  KnownOne &= 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() && RHSKnownZero.isNegative())
         KnownZero.setSignBit();