[APInt.h] Reduce the APInt header file interface a bit. NFC

[lattner]

Summary

This moves one mid-size function out of line, inlines the
trivial tcAnd/tcOr/tcXor/tcComplement methods into their only
caller, and moves the magic/umagic functions into SelectionDAG
since they are implementation details of its algorithm. This
also removes the unit tests for magic, but these are already
tested in the divide lowering logic for various targets.

This also upgrades some C style comments to C++.

[lattner]

Self approving as obvious, but will wait for pre submit tests to grind on this before submitting.

[lattner]

Yes, clang tidy, I agree the naming is inconsistent. This change is a step forward, but there are many left to go :-)

[craig.topper]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

5135

Will this end up being needed by GlobalISel? Is there a better place we could share?

[lattner]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

5135

Good question. If so, it should go in lib/CodeGen somewhere. I haven't been following GlobalISel, so I'm not sure where they are putting shared utilities between the two frameworks.

[dsanders]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

5135

I don't think GlobalISel is using it at the moment but we were using it downstream in our targets GlobalISel legalizer. DAGISel and GlobalISel don't really share much so I'm not currently aware of a suitable home for it. Would it make sense in MathExtras.h?

[lattner]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

5135

Yeah, that could make sense, or it could even be moved up to lib/Codegen. It is a *really* specific algorithm for APInt.h.

[ctetreau]

This patch actually broke my downstream as well. I uploaded a patch to move this to a new file in Support: https://reviews.llvm.org/D110747

llvm/include/llvm/ADT/APInt.h

   ///
   /// NOTE: When we have a BitWidth of 1, we define:
   ///
   ///   log2(0) = UINT32_MAX
   ///   log2(1) = 0
   ///
   /// to get around any mathematical concerns resulting from
   /// referencing 2 in a space where 2 does no exist.
-  unsigned nearestLogBase2() const {
-    // Special case when we have a bitwidth of 1. If VAL is 1, then we
-    // get 0. If VAL is 0, we get WORDTYPE_MAX which gets truncated to
-    // UINT32_MAX.
-    if (BitWidth == 1)
-      return U.VAL - 1;
-
-    // Handle the zero case.
-    if (isNullValue())
-      return UINT32_MAX;
-
-    // The non-zero case is handled by computing:
-    //
-    //   nearestLogBase2(x) = logBase2(x) + x[logBase2(x)-1].
-    //
-    // where x[i] is referring to the value of the ith bit of x.
-    unsigned lg = logBase2();
-    return lg + unsigned((*this)[lg - 1]);
-  }
+  unsigned nearestLogBase2() const;
 
   /// \returns the log base 2 of this APInt if its an exact power of two, -1
   /// otherwise
   int32_t exactLogBase2() const {
     if (!isPowerOf2())
       return -1;
     return logBase2();
   }
 
-  /// Compute the square root
+  /// Compute the square root.
   APInt sqrt() const;
 
-  /// Get the absolute value;
-  ///
-  /// If *this is < 0 then return -(*this), otherwise *this;
+  /// Get the absolute value.  If *this is < 0 then return -(*this), otherwise
+  /// *this.  Note that the "most negative" signed number (e.g. -128 for 8 bit
+  /// wide APInt) is unchanged due to how negation works.
   APInt abs() const {
     if (isNegative())
       return -(*this);
     return *this;
   }
 
   /// \returns the multiplicative inverse for a given modulo.
   APInt multiplicativeInverse(const APInt &modulo) const;
 
   /// @}
-  /// \name Support for division by constant
-  /// @{
-
-  /// Calculate the magic number for signed division by a constant.
-  struct ms;
-  ms magic() const;
-
-  /// Calculate the magic number for unsigned division by a constant.
-  struct mu;
-  mu magicu(unsigned LeadingZeros = 0) const;
-
-  /// @}
   /// \name Building-block Operations for APInt and APFloat
   /// @{
 
   // These building block operations operate on a representation of arbitrary
   // precision, two's-complement, bignum integer values. They should be
   // sufficient to implement APInt and APFloat bignum requirements. Inputs are
   // generally a pointer to the base of an array of integer parts, representing
   // an unsigned bignum, and a count of how many parts there are.

   /// Shift a bignum left Count bits. Shifted in bits are zero. There are no
   /// restrictions on Count.
   static void tcShiftLeft(WordType *, unsigned Words, unsigned Count);
 
   /// Shift a bignum right Count bits.  Shifted in bits are zero.  There are no
   /// restrictions on Count.
   static void tcShiftRight(WordType *, unsigned Words, unsigned Count);
 
-  /// The obvious AND, OR and XOR and complement operations.
-  static void tcAnd(WordType *, const WordType *, unsigned);
-  static void tcOr(WordType *, const WordType *, unsigned);
-  static void tcXor(WordType *, const WordType *, unsigned);
-  static void tcComplement(WordType *, unsigned);
-
   /// Comparison (unsigned) of two bignums.
   static int tcCompare(const WordType *, const WordType *, unsigned);
 
   /// Increment a bignum in-place.  Return the carry flag.
   static WordType tcIncrement(WordType *dst, unsigned parts) {
     return tcAddPart(dst, 1, parts);
   }
 
   /// Decrement a bignum in-place.  Return the borrow flag.
   static WordType tcDecrement(WordType *dst, unsigned parts) {
     return tcSubtractPart(dst, 1, parts);
   }
 
-  /// Set the least significant BITS and clear the rest.
-  static void tcSetLeastSignificantBits(WordType *, unsigned, unsigned bits);
-
   /// Used to insert APInt objects, or objects that contain APInt objects, into
   ///  FoldingSets.
   void Profile(FoldingSetNodeID &id) const;
 
   /// debug method
   void dump() const;
 
   /// Returns whether this instance allocated memory.
private:
 
   /// Signed comparison. Returns -1, 0, or 1 if this APInt is less than, equal
   /// to, or greater than RHS.
   int compareSigned(const APInt &RHS) const LLVM_READONLY;
 
   /// @}
 };
 
-/// Magic data for optimising signed division by a constant.
-struct APInt::ms {
-  APInt m;    ///< magic number
-  unsigned s; ///< shift amount
-};
-
-/// Magic data for optimising unsigned division by a constant.
-struct APInt::mu {
-  APInt m;    ///< magic number
-  bool a;     ///< add indicator
-  unsigned s; ///< shift amount
-};
-
 inline bool operator==(uint64_t V1, const APInt &V2) { return V2 == V1; }
 
 inline bool operator!=(uint64_t V1, const APInt &V2) { return V2 != V1; }
 
 /// Unary bitwise complement operator.
 ///
 /// \returns an APInt that is the bitwise complement of \p v.
 inline APInt operator~(APInt v) {

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

SDValue TargetLowering::BuildSDIVPow2(SDNode *N, const APInt &Divisor,
                               SmallVectorImpl<SDNode *> &Created) const {
   AttributeList Attr = DAG.getMachineFunction().getFunction().getAttributes();
   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
   if (TLI.isIntDivCheap(N->getValueType(0), Attr))
     return SDValue(N, 0); // Lower SDIV as SDIV
   return SDValue();
 }
 
+namespace {
+/// Magic data for optimising signed division by a constant.
+struct ms {
+  APInt m;    ///< magic number
+  unsigned s; ///< shift amount
+};
+
+/// Magic data for optimising unsigned division by a constant.
+struct mu {
+  APInt m;    ///< magic number
+  bool a;     ///< add indicator
+  unsigned s; ///< shift amount
+};
+} // namespace
+
+/// Calculate the magic numbers required to implement an unsigned integer
+/// division by a constant as a sequence of multiplies, adds and shifts.
+/// Requires that the divisor not be 0.  Taken from "Hacker's Delight", Henry
+/// S. Warren, Jr., chapter 10.
+/// LeadingZeros can be used to simplify the calculation if the upper bits
+/// of the divided value are known zero.
+static mu magicu(const APInt &d, unsigned LeadingZeros = 0) {
+  unsigned p;
+  APInt nc, delta, q1, r1, q2, r2;
+  struct mu magu;
+  magu.a = 0; // initialize "add" indicator
+  APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros);
+  APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
+  APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
+
+  nc = allOnes - (allOnes - d).urem(d);
+  p = d.getBitWidth() - 1;  // initialize p
+  q1 = signedMin.udiv(nc);  // initialize q1 = 2p/nc
+  r1 = signedMin - q1 * nc; // initialize r1 = rem(2p,nc)
+  q2 = signedMax.udiv(d);   // initialize q2 = (2p-1)/d
+  r2 = signedMax - q2 * d;  // initialize r2 = rem((2p-1),d)
+  do {
+    p = p + 1;
+    if (r1.uge(nc - r1)) {
+      q1 = q1 + q1 + 1;  // update q1
+      r1 = r1 + r1 - nc; // update r1
+    } else {
+      q1 = q1 + q1; // update q1
+      r1 = r1 + r1; // update r1
+    }
+    if ((r2 + 1).uge(d - r2)) {
+      if (q2.uge(signedMax))
+        magu.a = 1;
+      q2 = q2 + q2 + 1;     // update q2
+      r2 = r2 + r2 + 1 - d; // update r2
+    } else {
+      if (q2.uge(signedMin))
+        magu.a = 1;
+      q2 = q2 + q2;     // update q2
+      r2 = r2 + r2 + 1; // update r2
+    }
+    delta = d - 1 - r2;
+  } while (p < d.getBitWidth() * 2 &&
+           (q1.ult(delta) || (q1 == delta && r1 == 0)));
+  magu.m = q2 + 1;              // resulting magic number
+  magu.s = p - d.getBitWidth(); // resulting shift
+  return magu;
+}
+
+/// Calculate the magic numbers required to implement a signed integer division
+/// by a constant as a sequence of multiplies, adds and shifts.  Requires that
+/// the divisor not be 0, 1, or -1.  Taken from "Hacker's Delight", Henry S.
+/// Warren, Jr., Chapter 10.
+static ms magic(const APInt &d) {
+  unsigned p;
+  APInt ad, anc, delta, q1, r1, q2, r2, t;
+  APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
+  struct ms mag;
+
+  ad = d.abs();
+  t = signedMin + (d.lshr(d.getBitWidth() - 1));
+  anc = t - 1 - t.urem(ad);  // absolute value of nc
+  p = d.getBitWidth() - 1;   // initialize p
+  q1 = signedMin.udiv(anc);  // initialize q1 = 2p/abs(nc)
+  r1 = signedMin - q1 * anc; // initialize r1 = rem(2p,abs(nc))
+  q2 = signedMin.udiv(ad);   // initialize q2 = 2p/abs(d)
+  r2 = signedMin - q2 * ad;  // initialize r2 = rem(2p,abs(d))
+  do {
+    p = p + 1;
+    q1 = q1 << 1;      // update q1 = 2p/abs(nc)
+    r1 = r1 << 1;      // update r1 = rem(2p/abs(nc))
+    if (r1.uge(anc)) { // must be unsigned comparison
+      q1 = q1 + 1;
+      r1 = r1 - anc;
+    }
+    q2 = q2 << 1;     // update q2 = 2p/abs(d)
+    r2 = r2 << 1;     // update r2 = rem(2p/abs(d))
+    if (r2.uge(ad)) { // must be unsigned comparison
+      q2 = q2 + 1;
+      r2 = r2 - ad;
+    }
+    delta = ad - r2;
+  } while (q1.ult(delta) || (q1 == delta && r1 == 0));
+
+  mag.m = q2 + 1;
+  if (d.isNegative())
+    mag.m = -mag.m;            // resulting magic number
+  mag.s = p - d.getBitWidth(); // resulting shift
+  return mag;
+}
+
 /// Given an ISD::SDIV node expressing a divide by constant,
 /// return a DAG expression to select that will generate the same value by
 /// multiplying by a magic number.
 /// Ref: "Hacker's Delight" or "The PowerPC Compiler Writer's Guide".
 SDValue TargetLowering::BuildSDIV(SDNode *N, SelectionDAG &DAG,
                                   bool IsAfterLegalization,
                                   SmallVectorImpl<SDNode *> &Created) const {
   SDLoc dl(N);
SDValue TargetLowering::BuildSDIV(SDNode *N, SelectionDAG &DAG,
 
   SmallVector<SDValue, 16> MagicFactors, Factors, Shifts, ShiftMasks;
 
   auto BuildSDIVPattern = [&](ConstantSDNode *C) {
     if (C->isNullValue())
       return false;
 
     const APInt &Divisor = C->getAPIntValue();
-    APInt::ms magics = Divisor.magic();
+    ms magics = magic(Divisor);
     int NumeratorFactor = 0;
     int ShiftMask = -1;
 
     if (Divisor.isOneValue() || Divisor.isAllOnesValue()) {
       // If d is +1/-1, we just multiply the numerator by +1/-1.
       NumeratorFactor = Divisor.getSExtValue();
       magics.m = 0;
       magics.s = 0;
SDValue TargetLowering::BuildUDIV(SDNode *N, SelectionDAG &DAG,
   SmallVector<SDValue, 16> PreShifts, PostShifts, MagicFactors, NPQFactors;
 
   auto BuildUDIVPattern = [&](ConstantSDNode *C) {
     if (C->isNullValue())
       return false;
     // FIXME: We should use a narrower constant when the upper
     // bits are known to be zero.
     const APInt& Divisor = C->getAPIntValue();
-    APInt::mu magics = Divisor.magicu();
+    mu magics = magicu(Divisor);
     unsigned PreShift = 0, PostShift = 0;
 
     // If the divisor is even, we can avoid using the expensive fixup by
     // shifting the divided value upfront.
     if (magics.a != 0 && !Divisor[0]) {
       PreShift = Divisor.countTrailingZeros();
       // Get magic number for the shifted divisor.
-      magics = Divisor.lshr(PreShift).magicu(PreShift);
+      magics = magicu(Divisor.lshr(PreShift), PreShift);
       assert(magics.a == 0 && "Should use cheap fixup now");
     }
 
     APInt Magic = magics.m;
 
     unsigned SelNPQ;
     if (magics.a == 0 || Divisor.isOneValue()) {
       assert(magics.s < Divisor.getBitWidth() &&

llvm/lib/Support/APFloat.cpp

IEEEFloat::compareAbsoluteValue(const IEEEFloat &rhs) const {
   if (compare > 0)
     return cmpGreaterThan;
   else if (compare < 0)
     return cmpLessThan;
   else
     return cmpEqual;
 }
 
+/* Set the least significant BITS bits of a bignum, clear the
+   rest.  */
+static void tcSetLeastSignificantBits(APInt::WordType *dst, unsigned parts,
+                                      unsigned bits) {
+  unsigned i = 0;
+  while (bits > APInt::APINT_BITS_PER_WORD) {
+    dst[i++] = ~(APInt::WordType)0;
+    bits -= APInt::APINT_BITS_PER_WORD;
+  }
+
+  if (bits)
+    dst[i++] = ~(APInt::WordType)0 >> (APInt::APINT_BITS_PER_WORD - bits);
+
+  while (i < parts)
+    dst[i++] = 0;
+}
+
 /* Handle overflow.  Sign is preserved.  We either become infinity or
    the largest finite number.  */
 IEEEFloat::opStatus IEEEFloat::handleOverflow(roundingMode rounding_mode) {
   /* Infinity?  */
   if (rounding_mode == rmNearestTiesToEven ||
       rounding_mode == rmNearestTiesToAway ||
       (rounding_mode == rmTowardPositive && !sign) ||
       (rounding_mode == rmTowardNegative && sign)) {
     category = fcInfinity;
     return (opStatus) (opOverflow | opInexact);
   }
 
   /* Otherwise we become the largest finite number.  */
   category = fcNormal;
   exponent = semantics->maxExponent;
-  APInt::tcSetLeastSignificantBits(significandParts(), partCount(),
-                                   semantics->precision);
+  tcSetLeastSignificantBits(significandParts(), partCount(),
 
   return opInexact;
 }
 
 /* Returns TRUE if, when truncating the current number, with BIT the
    new LSB, with the given lost fraction and rounding mode, the result
    would need to be rounded away from zero (i.e., by increasing the
    signficand).  This routine must work for fcZero of both signs, and
if (fs == opInvalidOp) {
 
     if (category == fcNaN)
       bits = 0;
     else if (sign)
       bits = isSigned;
     else
       bits = width - isSigned;
 
-    APInt::tcSetLeastSignificantBits(parts.data(), dstPartsCount, bits);
+    tcSetLeastSignificantBits(parts.data(), dstPartsCount, bits);
     if (sign && isSigned)
       APInt::tcShiftLeft(parts.data(), dstPartsCount, width - 1);
   }
 
   return fs;
 }
 
 /* Convert an unsigned integer SRC to a floating point number,

llvm/lib/Support/APInt.cpp

APInt APInt::operator*(const APInt& RHS) const {
   APInt Result(getMemory(getNumWords()), getBitWidth());
 
   tcMultiply(Result.U.pVal, U.pVal, RHS.U.pVal, getNumWords());
 
   Result.clearUnusedBits();
   return Result;
 }
 
-void APInt::AndAssignSlowCase(const APInt& RHS) {
-  tcAnd(U.pVal, RHS.U.pVal, getNumWords());
+void APInt::AndAssignSlowCase(const APInt &RHS) {
+  WordType *dst = U.pVal, *rhs = RHS.U.pVal;
+  for (size_t i = 0, e = getNumWords(); i != e; ++i)
+    dst[i] &= rhs[i];
 }
 
-void APInt::OrAssignSlowCase(const APInt& RHS) {
-  tcOr(U.pVal, RHS.U.pVal, getNumWords());
+void APInt::OrAssignSlowCase(const APInt &RHS) {
+  WordType *dst = U.pVal, *rhs = RHS.U.pVal;
+  for (size_t i = 0, e = getNumWords(); i != e; ++i)
+    dst[i] |= rhs[i];
 }
 
-void APInt::XorAssignSlowCase(const APInt& RHS) {
-  tcXor(U.pVal, RHS.U.pVal, getNumWords());
+void APInt::XorAssignSlowCase(const APInt &RHS) {
+  WordType *dst = U.pVal, *rhs = RHS.U.pVal;
+  for (size_t i = 0, e = getNumWords(); i != e; ++i)
+    dst[i] ^= rhs[i];
 }
 
 APInt& APInt::operator*=(const APInt& RHS) {
   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
   *this = *this * RHS;
   return *this;
 }
 
void APInt::setBitsSlowCase(unsigned loBit, unsigned hiBit) {
   // Apply the mask to the low word.
   U.pVal[loWord] |= loMask;
 
   // Fill any words between loWord and hiWord with all ones.
   for (unsigned word = loWord + 1; word < hiWord; ++word)
     U.pVal[word] = WORDTYPE_MAX;
 }
 
+// Complement a bignum in-place.
+static void tcComplement(APInt::WordType *dst, unsigned parts) {
+  for (unsigned i = 0; i < parts; i++)
+    dst[i] = ~dst[i];
+}
+
 /// Toggle every bit to its opposite value.
 void APInt::flipAllBitsSlowCase() {
   tcComplement(U.pVal, getNumWords());
   clearUnusedBits();
 }
 
 /// Toggle a given bit to its opposite value whose position is given
 /// as "bitPosition".

 
 APInt APInt::rotr(unsigned rotateAmt) const {
   rotateAmt %= BitWidth;
   if (rotateAmt == 0)
     return *this;
   return lshr(rotateAmt) | shl(BitWidth - rotateAmt);
 }
 
+/// \returns the nearest log base 2 of this APInt. Ties round up.
+///
+/// NOTE: When we have a BitWidth of 1, we define:
+///
+///   log2(0) = UINT32_MAX
+///   log2(1) = 0
+///
+/// to get around any mathematical concerns resulting from
+/// referencing 2 in a space where 2 does no exist.
+unsigned APInt::nearestLogBase2() const {
+  // Special case when we have a bitwidth of 1. If VAL is 1, then we
+  // get 0. If VAL is 0, we get WORDTYPE_MAX which gets truncated to
+  // UINT32_MAX.
+  if (BitWidth == 1)
+    return U.VAL - 1;
+
+  // Handle the zero case.
+  if (isNullValue())
+    return UINT32_MAX;
+
+  // The non-zero case is handled by computing:
+  //
+  //   nearestLogBase2(x) = logBase2(x) + x[logBase2(x)-1].
+  //
+  // where x[i] is referring to the value of the ith bit of x.
+  unsigned lg = logBase2();
+  return lg + unsigned((*this)[lg - 1]);
+}
+
 // Square Root - this method computes and returns the square root of "this".
 // Three mechanisms are used for computation. For small values (<= 5 bits),
 // a table lookup is done. This gets some performance for common cases. For
 // values using less than 52 bits, the value is converted to double and then
 // the libc sqrt function is called. The result is rounded and then converted
 // back to a uint64_t which is then used to construct the result. Finally,
 // the Babylonian method for computing square roots is used.
 APInt APInt::sqrt() const {
APInt APInt::multiplicativeInverse(const APInt& modulo) const {
   // one if necessary. A simple addition of the modulo suffices because
   // abs(t[i]) is known to be less than *this/2 (see the link above).
   if (t[i].isNegative())
     t[i] += modulo;
 
   return std::move(t[i]);
 }
 
-/// Calculate the magic numbers required to implement a signed integer division
-/// by a constant as a sequence of multiplies, adds and shifts.  Requires that
-/// the divisor not be 0, 1, or -1.  Taken from "Hacker's Delight", Henry S.
-/// Warren, Jr., chapter 10.
-APInt::ms APInt::magic() const {
-  const APInt& d = *this;
-  unsigned p;
-  APInt ad, anc, delta, q1, r1, q2, r2, t;
-  APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
-  struct ms mag;
-
-  ad = d.abs();
-  t = signedMin + (d.lshr(d.getBitWidth() - 1));
-  anc = t - 1 - t.urem(ad);   // absolute value of nc
-  p = d.getBitWidth() - 1;    // initialize p
-  q1 = signedMin.udiv(anc);   // initialize q1 = 2p/abs(nc)
-  r1 = signedMin - q1*anc;    // initialize r1 = rem(2p,abs(nc))
-  q2 = signedMin.udiv(ad);    // initialize q2 = 2p/abs(d)
-  r2 = signedMin - q2*ad;     // initialize r2 = rem(2p,abs(d))
-  do {
-    p = p + 1;
-    q1 = q1<<1;          // update q1 = 2p/abs(nc)
-    r1 = r1<<1;          // update r1 = rem(2p/abs(nc))
-    if (r1.uge(anc)) {  // must be unsigned comparison
-      q1 = q1 + 1;
-      r1 = r1 - anc;
-    }
-    q2 = q2<<1;          // update q2 = 2p/abs(d)
-    r2 = r2<<1;          // update r2 = rem(2p/abs(d))
-    if (r2.uge(ad)) {   // must be unsigned comparison
-      q2 = q2 + 1;
-      r2 = r2 - ad;
-    }
-    delta = ad - r2;
-  } while (q1.ult(delta) || (q1 == delta && r1 == 0));
-
-  mag.m = q2 + 1;
-  if (d.isNegative()) mag.m = -mag.m;   // resulting magic number
-  mag.s = p - d.getBitWidth();          // resulting shift
-  return mag;
-}
-
-/// Calculate the magic numbers required to implement an unsigned integer
-/// division by a constant as a sequence of multiplies, adds and shifts.
-/// Requires that the divisor not be 0.  Taken from "Hacker's Delight", Henry
-/// S. Warren, Jr., chapter 10.
-/// LeadingZeros can be used to simplify the calculation if the upper bits
-/// of the divided value are known zero.
-APInt::mu APInt::magicu(unsigned LeadingZeros) const {
-  const APInt& d = *this;
-  unsigned p;
-  APInt nc, delta, q1, r1, q2, r2;
-  struct mu magu;
-  magu.a = 0;               // initialize "add" indicator
-  APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros);
-  APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
-  APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
-
-  nc = allOnes - (allOnes - d).urem(d);
-  p = d.getBitWidth() - 1;  // initialize p
-  q1 = signedMin.udiv(nc);  // initialize q1 = 2p/nc
-  r1 = signedMin - q1*nc;   // initialize r1 = rem(2p,nc)
-  q2 = signedMax.udiv(d);   // initialize q2 = (2p-1)/d
-  r2 = signedMax - q2*d;    // initialize r2 = rem((2p-1),d)
-  do {
-    p = p + 1;
-    if (r1.uge(nc - r1)) {
-      q1 = q1 + q1 + 1;  // update q1
-      r1 = r1 + r1 - nc; // update r1
-    }
-    else {
-      q1 = q1+q1; // update q1
-      r1 = r1+r1; // update r1
-    }
-    if ((r2 + 1).uge(d - r2)) {
-      if (q2.uge(signedMax)) magu.a = 1;
-      q2 = q2+q2 + 1;     // update q2
-      r2 = r2+r2 + 1 - d; // update r2
-    }
-    else {
-      if (q2.uge(signedMin)) magu.a = 1;
-      q2 = q2+q2;     // update q2
-      r2 = r2+r2 + 1; // update r2
-    }
-    delta = d - 1 - r2;
-  } while (p < d.getBitWidth()*2 &&
-           (q1.ult(delta) || (q1 == delta && r1 == 0)));
-  magu.m = q2 + 1; // resulting magic number
-  magu.s = p - d.getBitWidth();  // resulting shift
-  return magu;
-}
-
 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
 /// variables here have the same names as in the algorithm. Comments explain
 /// the algorithm and any deviation from it.
 static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r,
                      unsigned m, unsigned n) {
   assert(u && "Must provide dividend");
   assert(v && "Must provide divisor");

 // This implements a variety of operations on a representation of
 // arbitrary precision, two's-complement, bignum integer values.
 
 // Assumed by lowHalf, highHalf, partMSB and partLSB.  A fairly safe
 // and unrestricting assumption.
 static_assert(APInt::APINT_BITS_PER_WORD % 2 == 0,
               "Part width must be divisible by 2!");
 
-/* Some handy functions local to this file.  */
-
-/* Returns the integer part with the least significant BITS set.
-   BITS cannot be zero.  */
+// Returns the integer part with the least significant BITS set.
+// BITS cannot be zero.
 static inline APInt::WordType lowBitMask(unsigned bits) {
   assert(bits != 0 && bits <= APInt::APINT_BITS_PER_WORD);
-
   return ~(APInt::WordType) 0 >> (APInt::APINT_BITS_PER_WORD - bits);
 }
 
-/* Returns the value of the lower half of PART.  */
+/// Returns the value of the lower half of PART.
 static inline APInt::WordType lowHalf(APInt::WordType part) {
   return part & lowBitMask(APInt::APINT_BITS_PER_WORD / 2);
 }
 
-/* Returns the value of the upper half of PART.  */
+/// Returns the value of the upper half of PART.
 static inline APInt::WordType highHalf(APInt::WordType part) {
   return part >> (APInt::APINT_BITS_PER_WORD / 2);
 }
 
-/* Returns the bit number of the most significant set bit of a part.
-   If the input number has no bits set -1U is returned.  */
+/// Returns the bit number of the most significant set bit of a part.
+/// If the input number has no bits set -1U is returned.
 static unsigned partMSB(APInt::WordType value) {
   return findLastSet(value, ZB_Max);
 }
 
-/* Returns the bit number of the least significant set bit of a
-   part.  If the input number has no bits set -1U is returned.  */
+/// Returns the bit number of the least significant set bit of a part.  If the
+/// input number has no bits set -1U is returned.
 static unsigned partLSB(APInt::WordType value) {
   return findFirstSet(value, ZB_Max);
 }
 
-/* Sets the least significant part of a bignum to the input value, and
-   zeroes out higher parts.  */
+/// Sets the least significant part of a bignum to the input value, and zeroes
+/// out higher parts.
 void APInt::tcSet(WordType *dst, WordType part, unsigned parts) {
   assert(parts > 0);
-
   dst[0] = part;
   for (unsigned i = 1; i < parts; i++)
     dst[i] = 0;
 }
 
-/* Assign one bignum to another.  */
+/// Assign one bignum to another.
 void APInt::tcAssign(WordType *dst, const WordType *src, unsigned parts) {
   for (unsigned i = 0; i < parts; i++)
     dst[i] = src[i];
 }
 
-/* Returns true if a bignum is zero, false otherwise.  */
+/// Returns true if a bignum is zero, false otherwise.
 bool APInt::tcIsZero(const WordType *src, unsigned parts) {
   for (unsigned i = 0; i < parts; i++)
     if (src[i])
       return false;
 
   return true;
 }
 
-/* Extract the given bit of a bignum; returns 0 or 1.  */
+/// Extract the given bit of a bignum; returns 0 or 1.
 int APInt::tcExtractBit(const WordType *parts, unsigned bit) {
   return (parts[whichWord(bit)] & maskBit(bit)) != 0;
 }
 
-/* Set the given bit of a bignum. */
+/// Set the given bit of a bignum.
 void APInt::tcSetBit(WordType *parts, unsigned bit) {
   parts[whichWord(bit)] |= maskBit(bit);
 }
 
-/* Clears the given bit of a bignum. */
+/// Clears the given bit of a bignum.
 void APInt::tcClearBit(WordType *parts, unsigned bit) {
   parts[whichWord(bit)] &= ~maskBit(bit);
 }
 
-/* Returns the bit number of the least significant set bit of a
-   number.  If the input number has no bits set -1U is returned.  */
+/// Returns the bit number of the least significant set bit of a number.  If the
+/// input number has no bits set -1U is returned.
 unsigned APInt::tcLSB(const WordType *parts, unsigned n) {
   for (unsigned i = 0; i < n; i++) {
     if (parts[i] != 0) {
       unsigned lsb = partLSB(parts[i]);
-
       return lsb + i * APINT_BITS_PER_WORD;
     }
   }
 
   return -1U;
 }
 
-/* Returns the bit number of the most significant set bit of a number.
-   If the input number has no bits set -1U is returned.  */
+/// Returns the bit number of the most significant set bit of a number.
+/// If the input number has no bits set -1U is returned.
 unsigned APInt::tcMSB(const WordType *parts, unsigned n) {
   do {
     --n;
 
     if (parts[n] != 0) {
       unsigned msb = partMSB(parts[n]);
 
       return msb + n * APINT_BITS_PER_WORD;
     }
   } while (n);
 
   return -1U;
 }
 
-/* Copy the bit vector of width srcBITS from SRC, starting at bit
-   srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
-   the least significant bit of DST.  All high bits above srcBITS in
-   DST are zero-filled.  */
+/// Copy the bit vector of width srcBITS from SRC, starting at bit srcLSB, to
+/// DST, of dstCOUNT parts, such that the bit srcLSB becomes the least
+/// significant bit of DST.  All high bits above srcBITS in DST are zero-filled.
+/// */
 void
 APInt::tcExtract(WordType *dst, unsigned dstCount, const WordType *src,
                  unsigned srcBits, unsigned srcLSB) {
   unsigned dstParts = (srcBits + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD;
   assert(dstParts <= dstCount);
 
   unsigned firstSrcPart = srcLSB / APINT_BITS_PER_WORD;
-  tcAssign (dst, src + firstSrcPart, dstParts);
+  tcAssign(dst, src + firstSrcPart, dstParts);
 
   unsigned shift = srcLSB % APINT_BITS_PER_WORD;
-  tcShiftRight (dst, dstParts, shift);
+  tcShiftRight(dst, dstParts, shift);
 
-  /* We now have (dstParts * APINT_BITS_PER_WORD - shift) bits from SRC
-     in DST.  If this is less that srcBits, append the rest, else
-     clear the high bits.  */
+  // We now have (dstParts * APINT_BITS_PER_WORD - shift) bits from SRC
+  // in DST.  If this is less that srcBits, append the rest, else
+  // clear the high bits.
   unsigned n = dstParts * APINT_BITS_PER_WORD - shift;
   if (n < srcBits) {
     WordType mask = lowBitMask (srcBits - n);
     dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
                           << n % APINT_BITS_PER_WORD);
   } else if (n > srcBits) {
     if (srcBits % APINT_BITS_PER_WORD)
       dst[dstParts - 1] &= lowBitMask (srcBits % APINT_BITS_PER_WORD);
   }
 
-  /* Clear high parts.  */
+  // Clear high parts.
   while (dstParts < dstCount)
     dst[dstParts++] = 0;
 }
 
-/* DST += RHS + C where C is zero or one.  Returns the carry flag.  */
+//// DST += RHS + C where C is zero or one.  Returns the carry flag.
 APInt::WordType APInt::tcAdd(WordType *dst, const WordType *rhs,
                              WordType c, unsigned parts) {
   assert(c <= 1);
 
   for (unsigned i = 0; i < parts; i++) {
     WordType l = dst[i];
     if (c) {
       dst[i] += rhs[i] + 1;
for (unsigned i = 0; i < parts; ++i) {
     if (dst[i] >= src)
       return 0; // No need to carry so exit early.
     src = 1; // Carry one to next digit.
   }
 
   return 1;
 }
 
-/* DST -= RHS + C where C is zero or one.  Returns the carry flag.  */
+/// DST -= RHS + C where C is zero or one.  Returns the carry flag.
 APInt::WordType APInt::tcSubtract(WordType *dst, const WordType *rhs,
                                   WordType c, unsigned parts) {
   assert(c <= 1);
 
   for (unsigned i = 0; i < parts; i++) {
     WordType l = dst[i];
     if (c) {
       dst[i] -= rhs[i] + 1;
for (unsigned i = 0; i < parts; ++i) {
     if (src <= Dst)
       return 0; // No need to borrow so exit early.
     src = 1; // We have to "borrow 1" from next "word"
   }
 
   return 1;
 }
 
-/* Negate a bignum in-place.  */
+/// Negate a bignum in-place.
 void APInt::tcNegate(WordType *dst, unsigned parts) {
   tcComplement(dst, parts);
   tcIncrement(dst, parts);
 }
 
-/*  DST += SRC * MULTIPLIER + CARRY   if add is true
-    DST  = SRC * MULTIPLIER + CARRY   if add is false
-
-    Requires 0 <= DSTPARTS <= SRCPARTS + 1.  If DST overlaps SRC
-    they must start at the same point, i.e. DST == SRC.
-
-    If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
-    returned.  Otherwise DST is filled with the least significant
-    DSTPARTS parts of the result, and if all of the omitted higher
-    parts were zero return zero, otherwise overflow occurred and
-    return one.  */
+/// DST += SRC * MULTIPLIER + CARRY   if add is true
+/// DST  = SRC * MULTIPLIER + CARRY   if add is false
+/// Requires 0 <= DSTPARTS <= SRCPARTS + 1.  If DST overlaps SRC
+/// they must start at the same point, i.e. DST == SRC.
+/// If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
+/// returned.  Otherwise DST is filled with the least significant
+/// DSTPARTS parts of the result, and if all of the omitted higher
+/// parts were zero return zero, otherwise overflow occurred and
+/// return one.
 int APInt::tcMultiplyPart(WordType *dst, const WordType *src,
                           WordType multiplier, WordType carry,
                           unsigned srcParts, unsigned dstParts,
                           bool add) {
-  /* Otherwise our writes of DST kill our later reads of SRC.  */
+  // Otherwise our writes of DST kill our later reads of SRC.
   assert(dst <= src || dst >= src + srcParts);
   assert(dstParts <= srcParts + 1);
 
-  /* N loops; minimum of dstParts and srcParts.  */
+  // N loops; minimum of dstParts and srcParts.
   unsigned n = std::min(dstParts, srcParts);
 
   for (unsigned i = 0; i < n; i++) {
-    WordType low, mid, high, srcPart;
-
-      /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
-
-         This cannot overflow, because
-
-         (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
-
-         which is less than n^2.  */
-
-    srcPart = src[i];
-
+    // [LOW, HIGH] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
+    // This cannot overflow, because:
+    //   (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
+    // which is less than n^2.
+    WordType srcPart = src[i];
+    WordType low, mid, high;
     if (multiplier == 0 || srcPart == 0) {
       low = carry;
       high = 0;
     } else {
       low = lowHalf(srcPart) * lowHalf(multiplier);
       high = highHalf(srcPart) * highHalf(multiplier);
 
       mid = lowHalf(srcPart) * highHalf(multiplier);
       high += highHalf(mid);
       mid <<= APINT_BITS_PER_WORD / 2;
       if (low + mid < low)
         high++;
       low += mid;
 
       mid = highHalf(srcPart) * lowHalf(multiplier);
       high += highHalf(mid);
       mid <<= APINT_BITS_PER_WORD / 2;
       if (low + mid < low)
         high++;
       low += mid;
 
-      /* Now add carry.  */
+      // Now add carry.
       if (low + carry < low)
         high++;
       low += carry;
     }
 
     if (add) {
-      /* And now DST[i], and store the new low part there.  */
+      // And now DST[i], and store the new low part there.
       if (low + dst[i] < low)
         high++;
       dst[i] += low;
     } else
       dst[i] = low;
 
     carry = high;
   }
 
   if (srcParts < dstParts) {
-    /* Full multiplication, there is no overflow.  */
+    // Full multiplication, there is no overflow.
     assert(srcParts + 1 == dstParts);
     dst[srcParts] = carry;
     return 0;
   }
 
-  /* We overflowed if there is carry.  */
+  // We overflowed if there is carry.
   if (carry)
     return 1;
 
-  /* We would overflow if any significant unwritten parts would be
-     non-zero.  This is true if any remaining src parts are non-zero
-     and the multiplier is non-zero.  */
+  // We would overflow if any significant unwritten parts would be
+  // non-zero.  This is true if any remaining src parts are non-zero
+  // and the multiplier is non-zero.
   if (multiplier)
     for (unsigned i = dstParts; i < srcParts; i++)
       if (src[i])
         return 1;
 
-  /* We fitted in the narrow destination.  */
+  // We fitted in the narrow destination.
   return 0;
 }
 
-/* DST = LHS * RHS, where DST has the same width as the operands and
-   is filled with the least significant parts of the result.  Returns
-   one if overflow occurred, otherwise zero.  DST must be disjoint
-   from both operands.  */
+/// DST = LHS * RHS, where DST has the same width as the operands and
+/// is filled with the least significant parts of the result.  Returns
+/// one if overflow occurred, otherwise zero.  DST must be disjoint
+/// from both operands.
 int APInt::tcMultiply(WordType *dst, const WordType *lhs,
                       const WordType *rhs, unsigned parts) {
   assert(dst != lhs && dst != rhs);
 
   int overflow = 0;
   tcSet(dst, 0, parts);
 
   for (unsigned i = 0; i < parts; i++)
     overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
                                parts - i, true);
 
   return overflow;
 }
 
 /// DST = LHS * RHS, where DST has width the sum of the widths of the
 /// operands. No overflow occurs. DST must be disjoint from both operands.
 void APInt::tcFullMultiply(WordType *dst, const WordType *lhs,
                            const WordType *rhs, unsigned lhsParts,
                            unsigned rhsParts) {
-  /* Put the narrower number on the LHS for less loops below.  */
+  // Put the narrower number on the LHS for less loops below.
   if (lhsParts > rhsParts)
     return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
 
   assert(dst != lhs && dst != rhs);
 
   tcSet(dst, 0, rhsParts);
 
   for (unsigned i = 0; i < lhsParts; i++)
     tcMultiplyPart(&dst[i], rhs, lhs[i], 0, rhsParts, rhsParts + 1, true);
 }
 
-/* If RHS is zero LHS and REMAINDER are left unchanged, return one.
-   Otherwise set LHS to LHS / RHS with the fractional part discarded,
-   set REMAINDER to the remainder, return zero.  i.e.
-
-   OLD_LHS = RHS * LHS + REMAINDER
-
-   SCRATCH is a bignum of the same size as the operands and result for
-   use by the routine; its contents need not be initialized and are
-   destroyed.  LHS, REMAINDER and SCRATCH must be distinct.
-*/
+// If RHS is zero LHS and REMAINDER are left unchanged, return one.
+// Otherwise set LHS to LHS / RHS with the fractional part discarded,
+// set REMAINDER to the remainder, return zero.  i.e.
+//
+//   OLD_LHS = RHS * LHS + REMAINDER
+//
+// SCRATCH is a bignum of the same size as the operands and result for
+// use by the routine; its contents need not be initialized and are
+// destroyed.  LHS, REMAINDER and SCRATCH must be distinct.
 int APInt::tcDivide(WordType *lhs, const WordType *rhs,
                     WordType *remainder, WordType *srhs,
                     unsigned parts) {
   assert(lhs != remainder && lhs != srhs && remainder != srhs);
 
   unsigned shiftCount = tcMSB(rhs, parts) + 1;
   if (shiftCount == 0)
     return true;
 
   shiftCount = parts * APINT_BITS_PER_WORD - shiftCount;
   unsigned n = shiftCount / APINT_BITS_PER_WORD;
   WordType mask = (WordType) 1 << (shiftCount % APINT_BITS_PER_WORD);
 
   tcAssign(srhs, rhs, parts);
   tcShiftLeft(srhs, parts, shiftCount);
   tcAssign(remainder, lhs, parts);
   tcSet(lhs, 0, parts);
 
-  /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
-     the total.  */
+  // Loop, subtracting SRHS if REMAINDER is greater and adding that to the
+  // total.
   for (;;) {
     int compare = tcCompare(remainder, srhs, parts);
     if (compare >= 0) {
       tcSubtract(remainder, srhs, 0, parts);
       lhs[n] |= mask;
     }
 
     if (shiftCount == 0)
for (unsigned i = 0; i != WordsToMove; ++i) {
         Dst[i] |= Dst[i + WordShift + 1] << (APINT_BITS_PER_WORD - BitShift);
     }
   }
 
   // Fill in the remainder with 0s.
   std::memset(Dst + WordsToMove, 0, WordShift * APINT_WORD_SIZE);
 }
 
-/* Bitwise and of two bignums.  */
-void APInt::tcAnd(WordType *dst, const WordType *rhs, unsigned parts) {
-  for (unsigned i = 0; i < parts; i++)
-    dst[i] &= rhs[i];
-}
-
-/* Bitwise inclusive or of two bignums.  */
-void APInt::tcOr(WordType *dst, const WordType *rhs, unsigned parts) {
-  for (unsigned i = 0; i < parts; i++)
-    dst[i] |= rhs[i];
-}
-
-/* Bitwise exclusive or of two bignums.  */
-void APInt::tcXor(WordType *dst, const WordType *rhs, unsigned parts) {
-  for (unsigned i = 0; i < parts; i++)
-    dst[i] ^= rhs[i];
-}
-
-/* Complement a bignum in-place.  */
-void APInt::tcComplement(WordType *dst, unsigned parts) {
-  for (unsigned i = 0; i < parts; i++)
-    dst[i] = ~dst[i];
-}
-
-/* Comparison (unsigned) of two bignums.  */
+// Comparison (unsigned) of two bignums.
 int APInt::tcCompare(const WordType *lhs, const WordType *rhs,
                      unsigned parts) {
   while (parts) {
     parts--;
     if (lhs[parts] != rhs[parts])
       return (lhs[parts] > rhs[parts]) ? 1 : -1;
   }
 
   return 0;
 }
 
-/* Set the least significant BITS bits of a bignum, clear the
-   rest.  */
-void APInt::tcSetLeastSignificantBits(WordType *dst, unsigned parts,
-                                      unsigned bits) {
-  unsigned i = 0;
-  while (bits > APINT_BITS_PER_WORD) {
-    dst[i++] = ~(WordType) 0;
-    bits -= APINT_BITS_PER_WORD;
-  }
-
-  if (bits)
-    dst[i++] = ~(WordType) 0 >> (APINT_BITS_PER_WORD - bits);
-
-  while (i < parts)
-    dst[i++] = 0;
-}
-
 APInt llvm::APIntOps::RoundingUDiv(const APInt &A, const APInt &B,
                                    APInt::Rounding RM) {
   // Currently udivrem always rounds down.
   switch (RM) {
   case APInt::Rounding::DOWN:
   case APInt::Rounding::TOWARD_ZERO:
     return A.udiv(B);
   case APInt::Rounding::UP: {

llvm/unittests/ADT/APIntTest.cpp

TEST(APIntTest, Log2) {
   EXPECT_EQ(APInt(15, 8).logBase2(), 3U);
   EXPECT_EQ(APInt(15, 8).ceilLogBase2(), 3U);
   EXPECT_EQ(APInt(15, 8).exactLogBase2(), 3);
   EXPECT_EQ(APInt(15, 9).logBase2(), 3U);
   EXPECT_EQ(APInt(15, 9).ceilLogBase2(), 4U);
   EXPECT_EQ(APInt(15, 9).exactLogBase2(), -1);
 }
 
-TEST(APIntTest, magic) {
-  EXPECT_EQ(APInt(32, 3).magic().m, APInt(32, "55555556", 16));
-  EXPECT_EQ(APInt(32, 3).magic().s, 0U);
-  EXPECT_EQ(APInt(32, 5).magic().m, APInt(32, "66666667", 16));
-  EXPECT_EQ(APInt(32, 5).magic().s, 1U);
-  EXPECT_EQ(APInt(32, 7).magic().m, APInt(32, "92492493", 16));
-  EXPECT_EQ(APInt(32, 7).magic().s, 2U);
-}
-
-TEST(APIntTest, magicu) {
-  EXPECT_EQ(APInt(32, 3).magicu().m, APInt(32, "AAAAAAAB", 16));
-  EXPECT_EQ(APInt(32, 3).magicu().s, 1U);
-  EXPECT_EQ(APInt(32, 5).magicu().m, APInt(32, "CCCCCCCD", 16));
-  EXPECT_EQ(APInt(32, 5).magicu().s, 2U);
-  EXPECT_EQ(APInt(32, 7).magicu().m, APInt(32, "24924925", 16));
-  EXPECT_EQ(APInt(32, 7).magicu().s, 3U);
-  EXPECT_EQ(APInt(64, 25).magicu(1).m, APInt(64, "A3D70A3D70A3D70B", 16));
-  EXPECT_EQ(APInt(64, 25).magicu(1).s, 4U);
-}
-
 #ifdef GTEST_HAS_DEATH_TEST
 #ifndef NDEBUG
 TEST(APIntTest, StringDeath) {
   EXPECT_DEATH((void)APInt(0, "", 0), "Bitwidth too small");
   EXPECT_DEATH((void)APInt(32, "", 0), "Invalid string length");
   EXPECT_DEATH((void)APInt(32, "0", 0), "Radix should be 2, 8, 10, 16, or 36!");
   EXPECT_DEATH((void)APInt(32, "", 10), "Invalid string length");
   EXPECT_DEATH((void)APInt(32, "-", 10), "String is only a sign, needs a value.");