refactor: using pair to replace uint64_t array

[m0dulo]

refactor: using pair to replace uint64_t array

[m0dulo]

refactor: using pair to replace uint64_t array

llvm/include/llvm/ADT/APInt.h

 /// and increase as long as they are within the same interval.
 /// Specifically, adding of two negative numbers should not cause an
 /// overflow (as long as the magnitude does not exceed the bit width).
 /// On the other hand, given a positive number, adding a negative
 /// number to it can give a negative result, which would cause the
 /// value to go from [-2^BW, 0) to [0, 2^BW). In that sense, zero is
 /// treated as a special case of an overflow.
 ///
-/// This function returns std::nullopt if after finding k that minimizes the
+/// This function returns None if after finding k that minimizes the
 /// positive solution to q(n) = kR, both solutions are contained between
 /// two consecutive integers.
 ///
 /// There are cases where q(n) > T, and q(n+1) < T (assuming evaluation
 /// in arithmetic modulo 2^BW, and treating the values as signed) by the
 /// virtue of *signed* overflow. This function will *not* find such an n,
 /// however it may find a value of n satisfying the inequalities due to
 /// an *unsigned* overflow (if the values are treated as unsigned).

llvm/include/llvm/AsmParser/LLLexer.h

 #ifndef LLVM_ASMPARSER_LLLEXER_H
 #define LLVM_ASMPARSER_LLLEXER_H
 
 #include "LLToken.h"
 #include "llvm/ADT/APFloat.h"
 #include "llvm/ADT/APSInt.h"
 #include "llvm/Support/SMLoc.h"
 #include <string>
+#include <utility>
 
 namespace llvm {
   class Type;
   class SMDiagnostic;
   class SourceMgr;
   class LLVMContext;
 
   class LLLexer {
private:
     lltok::Kind LexVar(lltok::Kind Var, lltok::Kind VarID);
     lltok::Kind LexQuote();
     lltok::Kind Lex0x();
     lltok::Kind LexHash();
     lltok::Kind LexCaret();
 
     uint64_t atoull(const char *Buffer, const char *End);
     uint64_t HexIntToVal(const char *Buffer, const char *End);
-    void HexToIntPair(const char *Buffer, const char *End, uint64_t Pair[2]);
-    void FP80HexToIntPair(const char *Buffer, const char *End, uint64_t Pair[2]);
+    void HexToIntPair(const char *Buffer, const char *End,
+                      std::pair<uint64_t, uint64_t> *Pair);
+    void FP80HexToIntPair(const char *Buffer, const char *End,
+                          std::pair<uint64_t, uint64_t> *Pair);
   };
 } // end namespace llvm
 
 #endif

llvm/lib/AsmParser/LLLexer.cpp

if (Result < OldRes) {   // Uh, oh, overflow detected!!!
       Error("constant bigger than 64 bits detected!");
       return 0;
     }
   }
   return Result;
 }
 
 void LLLexer::HexToIntPair(const char *Buffer, const char *End,
-                           uint64_t Pair[2]) {
-  Pair[0] = 0;
+                           std::pair<uint64_t, uint64_t> *Pair) {
+  Pair->first = 0;
   if (End - Buffer >= 16) {
     for (int i = 0; i < 16; i++, Buffer++) {
       assert(Buffer != End);
-      Pair[0] *= 16;
-      Pair[0] += hexDigitValue(*Buffer);
+      Pair->first *= 16;
+      Pair->first += hexDigitValue(*Buffer);
     }
   }
-  Pair[1] = 0;
+  Pair->second = 0;
   for (int i = 0; i < 16 && Buffer != End; i++, Buffer++) {
-    Pair[1] *= 16;
-    Pair[1] += hexDigitValue(*Buffer);
+    Pair->second *= 16;
+    Pair->second += hexDigitValue(*Buffer);
   }
   if (Buffer != End)
     Error("constant bigger than 128 bits detected!");
 }
 
 /// FP80HexToIntPair - translate an 80 bit FP80 number (20 hexits) into
 /// { low64, high16 } as usual for an APInt.
 void LLLexer::FP80HexToIntPair(const char *Buffer, const char *End,
-                           uint64_t Pair[2]) {
-  Pair[1] = 0;
+                           std::pair<uint64_t, uint64_t> *Pair) {
+  Pair->second = 0;
   for (int i=0; i<4 && Buffer != End; i++, Buffer++) {
     assert(Buffer != End);
-    Pair[1] *= 16;
-    Pair[1] += hexDigitValue(*Buffer);
+    Pair->second *= 16;
+    Pair->second += hexDigitValue(*Buffer);
   }
-  Pair[0] = 0;
+  Pair->first = 0;
   for (int i = 0; i < 16 && Buffer != End; i++, Buffer++) {
-    Pair[0] *= 16;
-    Pair[0] += hexDigitValue(*Buffer);
+    Pair->first *= 16;
+    Pair->first += hexDigitValue(*Buffer);
   }
   if (Buffer != End)
     Error("constant bigger than 128 bits detected!");
 }
 
 // UnEscapeLexed - Run through the specified buffer and change \xx codes to the
 // appropriate character.
 static void UnEscapeLexed(std::string &Str) {
if (Kind == 'J') {
     // HexFPConstant - Floating point constant represented in IEEE format as a
     // hexadecimal number for when exponential notation is not precise enough.
     // Half, BFloat, Float, and double only.
     APFloatVal = APFloat(APFloat::IEEEdouble(),
                          APInt(64, HexIntToVal(TokStart + 2, CurPtr)));
     return lltok::APFloat;
   }
 
-  uint64_t Pair[2];
+  std::pair<uint64_t, uint64_t> Pair;
   switch (Kind) {
   default: llvm_unreachable("Unknown kind!");
   case 'K':
     // F80HexFPConstant - x87 long double in hexadecimal format (10 bytes)
-    FP80HexToIntPair(TokStart+3, CurPtr, Pair);
-    APFloatVal = APFloat(APFloat::x87DoubleExtended(), APInt(80, Pair));
+    FP80HexToIntPair(TokStart+3, CurPtr, &Pair);
+    APFloatVal = APFloat(APFloat::x87DoubleExtended(), APInt(80, {Pair.first, Pair.second}));
     return lltok::APFloat;
   case 'L':
     // F128HexFPConstant - IEEE 128-bit in hexadecimal format (16 bytes)
-    HexToIntPair(TokStart+3, CurPtr, Pair);
-    APFloatVal = APFloat(APFloat::IEEEquad(), APInt(128, Pair));
+    HexToIntPair(TokStart+3, CurPtr, &Pair);
+    APFloatVal = APFloat(APFloat::IEEEquad(), APInt(128, {Pair.first, Pair.second} ));
     return lltok::APFloat;
   case 'M':
     // PPC128HexFPConstant - PowerPC 128-bit in hexadecimal format (16 bytes)
-    HexToIntPair(TokStart+3, CurPtr, Pair);
-    APFloatVal = APFloat(APFloat::PPCDoubleDouble(), APInt(128, Pair));
+    HexToIntPair(TokStart+3, CurPtr, &Pair);
+    APFloatVal = APFloat(APFloat::PPCDoubleDouble(), APInt(128, {Pair.first, Pair.second}));
     return lltok::APFloat;
   case 'H':
     APFloatVal = APFloat(APFloat::IEEEhalf(),
                          APInt(16,HexIntToVal(TokStart+3, CurPtr)));
     return lltok::APFloat;
   case 'R':
     // Brain floating point
     APFloatVal = APFloat(APFloat::BFloat(),

llvm/lib/Support/APInt.cpp

 #include <cmath>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "apint"
 
 /// A utility function for allocating memory, checking for allocation failures,
 /// and ensuring the contents are zeroed.
-inline static uint64_t* getClearedMemory(unsigned numWords) {
+inline static uint64_t *getClearedMemory(unsigned numWords) {
   uint64_t *result = new uint64_t[numWords];
   memset(result, 0, numWords * sizeof(uint64_t));
   return result;
 }
 
 /// A utility function for allocating memory and checking for allocation
 /// failure.  The content is not zeroed.
-inline static uint64_t* getMemory(unsigned numWords) {
+inline static uint64_t *getMemory(unsigned numWords) {
   return new uint64_t[numWords];
 }
 
 /// A utility function that converts a character to a digit.
 inline static unsigned getDigit(char cdigit, uint8_t radix) {
   unsigned r;
 
   if (radix == 16 || radix == 36) {
inline static unsigned getDigit(char cdigit, uint8_t radix) {
 
   r = cdigit - '0';
   if (r < radix)
     return r;
 
   return -1U;
 }
 
-
 void APInt::initSlowCase(uint64_t val, bool isSigned) {
   U.pVal = getClearedMemory(getNumWords());
   U.pVal[0] = val;
   if (isSigned && int64_t(val) < 0)
     for (unsigned i = 1; i < getNumWords(); ++i)
       U.pVal[i] = WORDTYPE_MAX;
   clearUnusedBits();
 }
 
-void APInt::initSlowCase(const APInt& that) {
+void APInt::initSlowCase(const APInt &that) {
   U.pVal = getMemory(getNumWords());
   memcpy(U.pVal, that.U.pVal, getNumWords() * APINT_WORD_SIZE);
 }
 
 void APInt::initFromArray(ArrayRef<uint64_t> bigVal) {
   assert(bigVal.data() && "Null pointer detected!");
   if (isSingleWord())
     U.VAL = bigVal[0];
void APInt::reallocate(unsigned NewBitWidth) {
   // If the number of words is the same we can just change the width and stop.
   if (getNumWords() == getNumWords(NewBitWidth)) {
     BitWidth = NewBitWidth;
     return;
   }
 
   // If we have an allocation, delete it.
   if (!isSingleWord())
-    delete [] U.pVal;
+    delete[] U.pVal;
 
   // Update BitWidth.
   BitWidth = NewBitWidth;
 
   // If we are supposed to have an allocation, create it.
   if (!isSingleWord())
     U.pVal = getMemory(getNumWords());
 }
void APInt::assignSlowCase(const APInt &RHS) {
   // Copy the data.
   if (isSingleWord())
     U.VAL = RHS.U.VAL;
   else
     memcpy(U.pVal, RHS.U.pVal, getNumWords() * APINT_WORD_SIZE);
 }
 
 /// This method 'profiles' an APInt for use with FoldingSet.
-void APInt::Profile(FoldingSetNodeID& ID) const {
+void APInt::Profile(FoldingSetNodeID &ID) const {
   ID.AddInteger(BitWidth);
 
   if (isSingleWord()) {
     ID.AddInteger(U.VAL);
     return;
   }
 
   unsigned NumWords = getNumWords();
   for (unsigned i = 0; i < NumWords; ++i)
     ID.AddInteger(U.pVal[i]);
 }
 
 /// Prefix increment operator. Increments the APInt by one.
-APInt& APInt::operator++() {
+APInt &APInt::operator++() {
   if (isSingleWord())
     ++U.VAL;
   else
     tcIncrement(U.pVal, getNumWords());
   return clearUnusedBits();
 }
 
 /// Prefix decrement operator. Decrements the APInt by one.
-APInt& APInt::operator--() {
+APInt &APInt::operator--() {
   if (isSingleWord())
     --U.VAL;
   else
     tcDecrement(U.pVal, getNumWords());
   return clearUnusedBits();
 }
 
 /// Adds the RHS APInt to this APInt.
 /// @returns this, after addition of RHS.
 /// Addition assignment operator.
-APInt& APInt::operator+=(const APInt& RHS) {
+APInt &APInt::operator+=(const APInt &RHS) {
   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
   if (isSingleWord())
     U.VAL += RHS.U.VAL;
   else
     tcAdd(U.pVal, RHS.U.pVal, 0, getNumWords());
   return clearUnusedBits();
 }
 
-APInt& APInt::operator+=(uint64_t RHS) {
+APInt &APInt::operator+=(uint64_t RHS) {
   if (isSingleWord())
     U.VAL += RHS;
   else
     tcAddPart(U.pVal, RHS, getNumWords());
   return clearUnusedBits();
 }
 
 /// Subtracts the RHS APInt from this APInt
 /// @returns this, after subtraction
 /// Subtraction assignment operator.
-APInt& APInt::operator-=(const APInt& RHS) {
+APInt &APInt::operator-=(const APInt &RHS) {
   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
   if (isSingleWord())
     U.VAL -= RHS.U.VAL;
   else
     tcSubtract(U.pVal, RHS.U.pVal, 0, getNumWords());
   return clearUnusedBits();
 }
 
-APInt& APInt::operator-=(uint64_t RHS) {
+APInt &APInt::operator-=(uint64_t RHS) {
   if (isSingleWord())
     U.VAL -= RHS;
   else
     tcSubtractPart(U.pVal, RHS, getNumWords());
   return clearUnusedBits();
 }
 
-APInt APInt::operator*(const APInt& RHS) const {
+APInt APInt::operator*(const APInt &RHS) const {
   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
   if (isSingleWord())
     return APInt(BitWidth, U.VAL * RHS.U.VAL);
 
   APInt Result(getMemory(getNumWords()), getBitWidth());
   tcMultiply(Result.U.pVal, U.pVal, RHS.U.pVal, getNumWords());
   Result.clearUnusedBits();
   return Result;
for (size_t i = 0, e = getNumWords(); i != e; ++i)
     dst[i] ^= rhs[i];
 }
 
 APInt &APInt::operator*=(const APInt &RHS) {
   *this = *this * RHS;
   return *this;
 }
 
-APInt& APInt::operator*=(uint64_t RHS) {
+APInt &APInt::operator*=(uint64_t RHS) {
   if (isSingleWord()) {
     U.VAL *= RHS;
   } else {
     unsigned NumWords = getNumWords();
     tcMultiplyPart(U.pVal, U.pVal, RHS, 0, NumWords, NumWords, false);
   }
   return clearUnusedBits();
 }
 
 bool APInt::equalSlowCase(const APInt &RHS) const {
   return std::equal(U.pVal, U.pVal + getNumWords(), RHS.U.pVal);
 }
 
-int APInt::compare(const APInt& RHS) const {
+int APInt::compare(const APInt &RHS) const {
   assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
   if (isSingleWord())
     return U.VAL < RHS.U.VAL ? -1 : U.VAL > RHS.U.VAL;
 
   return tcCompare(U.pVal, RHS.U.pVal, getNumWords());
 }
 
-int APInt::compareSigned(const APInt& RHS) const {
+int APInt::compareSigned(const APInt &RHS) const {
   assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
   if (isSingleWord()) {
     int64_t lhsSext = SignExtend64(U.VAL, BitWidth);
     int64_t rhsSext = SignExtend64(RHS.U.VAL, BitWidth);
     return lhsSext < rhsSext ? -1 : lhsSext > rhsSext;
   }
 
   bool lhsNeg = isNegative();
void APInt::insertBits(const APInt &subBits, unsigned bitPosition) {
 
   // General case - set/clear individual bits in dst based on src.
   // TODO - there is scope for optimization here, but at the moment this code
   // path is barely used so prefer readability over performance.
   for (unsigned i = 0; i != subBitWidth; ++i)
     setBitVal(bitPosition + i, subBits[i]);
 }
 
-void APInt::insertBits(uint64_t subBits, unsigned bitPosition, unsigned numBits) {
+void APInt::insertBits(uint64_t subBits, unsigned bitPosition,
+                       unsigned numBits) {
   uint64_t maskBits = maskTrailingOnes<uint64_t>(numBits);
   subBits &= maskBits;
   if (isSingleWord()) {
     U.VAL &= ~(maskBits << bitPosition);
     U.VAL |= subBits << bitPosition;
     return;
   }
 
   unsigned loBit = whichBit(bitPosition);
   unsigned loWord = whichWord(bitPosition);
   unsigned hiWord = whichWord(bitPosition + numBits - 1);
   if (loWord == hiWord) {
     U.pVal[loWord] &= ~(maskBits << loBit);
     U.pVal[loWord] |= subBits << loBit;
     return;
   }
 
-  static_assert(8 * sizeof(WordType) <= 64, "This code assumes only two words affected");
+  static_assert(8 * sizeof(WordType) <= 64,
+                "This code assumes only two words affected");
   unsigned wordBits = 8 * sizeof(WordType);
   U.pVal[loWord] &= ~(maskBits << loBit);
   U.pVal[loWord] |= subBits << loBit;
 
   U.pVal[hiWord] &= ~(maskBits >> (wordBits - loBit));
   U.pVal[hiWord] |= subBits >> (wordBits - loBit);
 }
 
if (isSingleWord())
     return (U.VAL >> bitPosition) & maskBits;
 
   unsigned loBit = whichBit(bitPosition);
   unsigned loWord = whichWord(bitPosition);
   unsigned hiWord = whichWord(bitPosition + numBits - 1);
   if (loWord == hiWord)
     return (U.pVal[loWord] >> loBit) & maskBits;
 
-  static_assert(8 * sizeof(WordType) <= 64, "This code assumes only two words affected");
+  static_assert(8 * sizeof(WordType) <= 64,
+                "This code assumes only two words affected");
   unsigned wordBits = 8 * sizeof(WordType);
   uint64_t retBits = U.pVal[loWord] >> loBit;
   retBits |= U.pVal[hiWord] << (wordBits - loBit);
   retBits &= maskBits;
   return retBits;
 }
 
 unsigned APInt::getSufficientBitsNeeded(StringRef Str, uint8_t Radix) {
unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) {
   StringRef::iterator p = str.begin();
   unsigned isNegative = *p == '-';
   if (*p == '-' || *p == '+') {
     p++;
     slen--;
     assert(slen && "String is only a sign, needs a value.");
   }
 
-
   // Convert to the actual binary value.
   APInt tmp(sufficient, StringRef(p, slen), radix);
 
   // Compute how many bits are required. If the log is infinite, assume we need
   // just bit. If the log is exact and value is negative, then the value is
   // MinSignedValue with (log + 1) bits.
   unsigned log = tmp.logBase2();
   if (log == (unsigned)-1) {
APInt APInt::getSplat(unsigned NewLen, const APInt &V) {
   for (unsigned I = V.getBitWidth(); I < NewLen; I <<= 1)
     Val |= Val << I;
 
   return Val;
 }
 
 unsigned APInt::countLeadingZerosSlowCase() const {
   unsigned Count = 0;
-  for (int i = getNumWords()-1; i >= 0; --i) {
+  for (int i = getNumWords() - 1; i >= 0; --i) {
     uint64_t V = U.pVal[i];
     if (V == 0)
       Count += APINT_BITS_PER_WORD;
     else {
       Count += llvm::countLeadingZeros(V);
       break;
     }
   }
APInt APInt::reverseBits() const {
   }
 
   Reversed <<= S;
   return Reversed;
 }
 
 APInt llvm::APIntOps::GreatestCommonDivisor(APInt A, APInt B) {
   // Fast-path a common case.
-  if (A == B) return A;
+  if (A == B)
+    return A;
 
   // Corner cases: if either operand is zero, the other is the gcd.
-  if (!A) return B;
-  if (!B) return A;
+  if (!A)
+    return B;
+  if (!B)
+    return A;
 
   // Count common powers of 2 and remove all other powers of 2.
   unsigned Pow2;
   {
     unsigned Pow2_A = A.countTrailingZeros();
     unsigned Pow2_B = B.countTrailingZeros();
     if (Pow2_A > Pow2_B) {
       A.lshrInPlace(Pow2_A - Pow2_B);
APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
   if (exp < 0)
     return APInt(width, 0u);
 
   // Extract the mantissa by clearing the top 12 bits (sign + exponent).
   uint64_t mantissa = (I & (~0ULL >> 12)) | 1ULL << 52;
 
   // If the exponent doesn't shift all bits out of the mantissa
   if (exp < 52)
-    return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
-                    APInt(width, mantissa >> (52 - exp));
+    return isNeg ? -APInt(width, mantissa >> (52 - exp))
+                 : APInt(width, mantissa >> (52 - exp));
 
   // If the client didn't provide enough bits for us to shift the mantissa into
   // then the result is undefined, just return 0
   if (width <= exp - 52)
     return APInt(width, 0);
 
   // Otherwise, we have to shift the mantissa bits up to the right location
   APInt Tmp(width, mantissa);
   Tmp <<= (unsigned)exp - 52;
   return isNeg ? -Tmp : Tmp;
 }
 
 /// This function converts this APInt to a double.
 /// The layout for double is as following (IEEE Standard 754):
 ///  --------------------------------------
 /// |  Sign    Exponent    Fraction    Bias |
 /// |-------------------------------------- |
 /// |  1[63]   11[62-52]   52[51-00]   1023 |
 ///  --------------------------------------
 double APInt::roundToDouble(bool isSigned) const {
 
   // Handle the simple case where the value is contained in one uint64_t.
-  // It is wrong to optimize getWord(0) to VAL; there might be more than one word.
+  // It is wrong to optimize getWord(0) to VAL; there might be more than one
+  // word.
   if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
     if (isSigned) {
       int64_t sext = SignExtend64(getWord(0), BitWidth);
       return double(sext);
     } else
       return double(getWord(0));
   }
 
   // Determine if the value is negative.
-  bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
+  bool isNeg = isSigned ? (*this)[BitWidth - 1] : false;
 
   // Construct the absolute value if we're negative.
   APInt Tmp(isNeg ? -(*this) : (*this));
 
   // Figure out how many bits we're using.
   unsigned n = Tmp.getActiveBits();
 
   // The exponent (without bias normalization) is just the number of bits
   // we are using. Note that the sign bit is gone since we constructed the
   // absolute value.
   uint64_t exp = n;
 
   // Return infinity for exponent overflow
   if (exp > 1023) {
     if (!isSigned || !isNeg)
       return std::numeric_limits<double>::infinity();
     else
       return -std::numeric_limits<double>::infinity();
   }
   exp += 1023; // Increment for 1023 bias
 
   // Number of bits in mantissa is 52. To obtain the mantissa value, we must
   // extract the high 52 bits from the correct words in pVal.
   uint64_t mantissa;
-  unsigned hiWord = whichWord(n-1);
+  unsigned hiWord = whichWord(n - 1);
   if (hiWord == 0) {
     mantissa = Tmp.U.pVal[0];
     if (n > 52)
       mantissa >>= n - 52; // shift down, we want the top 52 bits.
   } else {
     assert(hiWord > 0 && "huh?");
     uint64_t hibits = Tmp.U.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
-    uint64_t lobits = Tmp.U.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
+    uint64_t lobits = Tmp.U.pVal[hiWord - 1] >> (11 + n % APINT_BITS_PER_WORD);
     mantissa = hibits | lobits;
   }
 
   // The leading bit of mantissa is implicit, so get rid of it.
   uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
   uint64_t I = sign | (exp << 52) | mantissa;
   return bit_cast<double>(I);
 }
U.pVal[getNumWords() - 1] = SignExtend64(
         U.pVal[getNumWords() - 1], ((BitWidth - 1) % APINT_BITS_PER_WORD) + 1);
 
     // Fastpath for moving by whole words.
     if (BitShift == 0) {
       std::memmove(U.pVal, U.pVal + WordShift, WordsToMove * APINT_WORD_SIZE);
     } else {
       // Move the words containing significant bits.
       for (unsigned i = 0; i != WordsToMove - 1; ++i)
-        U.pVal[i] = (U.pVal[i + WordShift] >> BitShift) |
-                    (U.pVal[i + WordShift + 1] << (APINT_BITS_PER_WORD - BitShift));
+        U.pVal[i] =
+            (U.pVal[i + WordShift] >> BitShift) |
 
       // Handle the last word which has no high bits to copy.
       U.pVal[WordsToMove - 1] = U.pVal[WordShift + WordsToMove - 1] >> BitShift;
       // Sign extend one more time.
       U.pVal[WordsToMove - 1] =
           SignExtend64(U.pVal[WordsToMove - 1], APINT_BITS_PER_WORD - BitShift);
     }
   }
APInt APInt::sqrt() const {
 
   // Determine the magnitude of the value.
   unsigned magnitude = getActiveBits();
 
   // Use a fast table for some small values. This also gets rid of some
   // rounding errors in libc sqrt for small values.
   if (magnitude <= 5) {
     static const uint8_t results[32] = {
         /*     0 */ 0,
         /*  1- 2 */ 1, 1,
         /*  3- 6 */ 2, 2, 2, 2,
         /*  7-12 */ 3, 3, 3, 3, 3, 3,
         /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
         /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
-      /*    31 */ 6
-    };
-    return APInt(BitWidth, results[ (isSingleWord() ? U.VAL : U.pVal[0]) ]);
+        /*    31 */ 6};
+    return APInt(BitWidth, results[(isSingleWord() ? U.VAL : U.pVal[0])]);
   }
 
   // If the magnitude of the value fits in less than 52 bits (the precision of
   // an IEEE double precision floating point value), then we can use the
   // libc sqrt function which will probably use a hardware sqrt computation.
   // This should be faster than the algorithm below.
   if (magnitude < 52) {
-    return APInt(BitWidth,
-                 uint64_t(::round(::sqrt(double(isSingleWord() ? U.VAL
-                                                               : U.pVal[0])))));
+    return APInt(
+        BitWidth,
+        uint64_t(::round(::sqrt(double(isSingleWord() ? U.VAL : U.pVal[0])))));
   }
 
   // Okay, all the short cuts are exhausted. We must compute it. The following
   // is a classical Babylonian method for computing the square root. This code
   // was adapted to APInt from a wikipedia article on such computations.
   // See http://www.wikipedia.org/ and go to the page named
   // Calculate_an_integer_square_root.
   unsigned nbits = BitWidth, i = 4;
APInt APInt::sqrt() const {
 
   // Make sure we return the closest approximation
   // NOTE: The rounding calculation below is correct. It will produce an
   // off-by-one discrepancy with results from pari/gp. That discrepancy has been
   // determined to be a rounding issue with pari/gp as it begins to use a
   // floating point representation after 192 bits. There are no discrepancies
   // between this algorithm and pari/gp for bit widths < 192 bits.
   APInt square(x_old * x_old);
-  APInt nextSquare((x_old + 1) * (x_old +1));
+  APInt nextSquare((x_old + 1) * (x_old + 1));
   if (this->ult(square))
     return x_old;
   assert(this->ule(nextSquare) && "Error in APInt::sqrt computation");
   APInt midpoint((nextSquare - square).udiv(two));
   APInt offset(*this - square);
   if (offset.ult(midpoint))
     return x_old;
   return x_old + 1;
 }
 
 /// Computes the multiplicative inverse of this APInt for a given modulo. The
 /// iterative extended Euclidean algorithm is used to solve for this value,
 /// however we simplify it to speed up calculating only the inverse, and take
 /// advantage of div+rem calculations. We also use some tricks to avoid copying
 /// (potentially large) APInts around.
 /// WARNING: a value of '0' may be returned,
 ///          signifying that no multiplicative inverse exists!
-APInt APInt::multiplicativeInverse(const APInt& modulo) const {
+APInt APInt::multiplicativeInverse(const APInt &modulo) const {
   assert(ult(modulo) && "This APInt must be smaller than the modulo");
 
   // Using the properties listed at the following web page (accessed 06/21/08):
   //   http://www.numbertheory.org/php/euclid.html
   // (especially the properties numbered 3, 4 and 9) it can be proved that
   // BitWidth bits suffice for all the computations in the algorithm implemented
   // below. More precisely, this number of bits suffice if the multiplicative
   // inverse exists, but may not suffice for the general extended Euclidean
   // algorithm.
 
-  APInt r[2] = { modulo, *this };
-  APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
+  APInt r[2] = {modulo, *this};
+  APInt t[2] = {APInt(BitWidth, 0), APInt(BitWidth, 1)};
   APInt q(BitWidth, 0);
 
   unsigned i;
-  for (i = 0; r[i^1] != 0; i ^= 1) {
+  for (i = 0; r[i ^ 1] != 0; i ^= 1) {
     // An overview of the math without the confusing bit-flipping:
     // q = r[i-2] / r[i-1]
     // r[i] = r[i-2] % r[i-1]
     // t[i] = t[i-2] - t[i-1] * q
-    udivrem(r[i], r[i^1], q, r[i]);
-    t[i] -= t[i^1] * q;
+    udivrem(r[i], r[i ^ 1], q, r[i]);
+    t[i] -= t[i ^ 1] * q;
   }
 
   // If this APInt and the modulo are not coprime, there is no multiplicative
   // inverse, so return 0. We check this by looking at the next-to-last
   // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
   // algorithm.
   if (r[i] != 1)
     return APInt(BitWidth, 0);
 
   // The next-to-last t is the multiplicative inverse.  However, we are
   // interested in a positive inverse. Calculate a positive one from a negative
   // 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]);
 }
 
 /// 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,
+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");
   assert(q && "Must provide quotient");
   assert(u != v && u != q && v != q && "Must use different memory");
-  assert(n>1 && "n must be > 1");
+  assert(n > 1 && "n must be > 1");
 
   // b denotes the base of the number system. In our case b is 2^32.
   const uint64_t b = uint64_t(1) << 32;
 
 // The DEBUG macros here tend to be spam in the debug output if you're not
 // debugging this code. Disable them unless KNUTH_DEBUG is defined.
 #ifdef KNUTH_DEBUG
 #define DEBUG_KNUTH(X) LLVM_DEBUG(X)
 #else
-#define DEBUG_KNUTH(X) do {} while(false)
+#define DEBUG_KNUTH(X)                                                         \
+  do {                                                                         \
+  } while (false)
 #endif
 
   DEBUG_KNUTH(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
   DEBUG_KNUTH(dbgs() << "KnuthDiv: original:");
   DEBUG_KNUTH(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i]);
   DEBUG_KNUTH(dbgs() << " by");
   DEBUG_KNUTH(for (int i = n; i > 0; i--) dbgs() << " " << v[i - 1]);
   DEBUG_KNUTH(dbgs() << '\n');
   // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
   // u and v by d. Note that we have taken Knuth's advice here to use a power
   // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
   // 2 allows us to shift instead of multiply and it is easy to determine the
   // shift amount from the leading zeros.  We are basically normalizing the u
   // and v so that its high bits are shifted to the top of v's range without
   // overflow. Note that this can require an extra word in u so that u must
   // be of length m+n+1.
-  unsigned shift = countLeadingZeros(v[n-1]);
+  unsigned shift = countLeadingZeros(v[n - 1]);
   uint32_t v_carry = 0;
   uint32_t u_carry = 0;
   if (shift) {
-    for (unsigned i = 0; i < m+n; ++i) {
+    for (unsigned i = 0; i < m + n; ++i) {
       uint32_t u_tmp = u[i] >> (32 - shift);
       u[i] = (u[i] << shift) | u_carry;
       u_carry = u_tmp;
     }
     for (unsigned i = 0; i < n; ++i) {
       uint32_t v_tmp = v[i] >> (32 - shift);
       v[i] = (v[i] << shift) | v_carry;
       v_carry = v_tmp;
     }
   }
-  u[m+n] = u_carry;
+  u[m + n] = u_carry;
 
   DEBUG_KNUTH(dbgs() << "KnuthDiv:   normal:");
   DEBUG_KNUTH(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i]);
   DEBUG_KNUTH(dbgs() << " by");
   DEBUG_KNUTH(for (int i = n; i > 0; i--) dbgs() << " " << v[i - 1]);
   DEBUG_KNUTH(dbgs() << '\n');
 
   // D2. [Initialize j.]  Set j to m. This is the loop counter over the places.
   int j = m;
   do {
     DEBUG_KNUTH(dbgs() << "KnuthDiv: quotient digit #" << j << '\n');
     // D3. [Calculate q'.].
     //     Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
     //     Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
     // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
     // qp by 1, increase rp by v[n-1], and repeat this test if rp < b. The test
     // on v[n-2] determines at high speed most of the cases in which the trial
     // value qp is one too large, and it eliminates all cases where qp is two
     // too large.
-    uint64_t dividend = Make_64(u[j+n], u[j+n-1]);
+    uint64_t dividend = Make_64(u[j + n], u[j + n - 1]);
     DEBUG_KNUTH(dbgs() << "KnuthDiv: dividend == " << dividend << '\n');
-    uint64_t qp = dividend / v[n-1];
-    uint64_t rp = dividend % v[n-1];
-    if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
+    uint64_t qp = dividend / v[n - 1];
+    uint64_t rp = dividend % v[n - 1];
+    if (qp == b || qp * v[n - 2] > b * rp + u[j + n - 2]) {
       qp--;
-      rp += v[n-1];
-      if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
+      rp += v[n - 1];
+      if (rp < b && (qp == b || qp * v[n - 2] > b * rp + u[j + n - 2]))
         qp--;
     }
     DEBUG_KNUTH(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
 
     // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
     // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
     // consists of a simple multiplication by a one-place number, combined with
     // a subtraction.
     // The digits (u[j+n]...u[j]) should be kept positive; if the result of
     // this step is actually negative, (u[j+n]...u[j]) should be left as the
     // true value plus b**(n+1), namely as the b's complement of
     // the true value, and a "borrow" to the left should be remembered.
     int64_t borrow = 0;
     for (unsigned i = 0; i < n; ++i) {
       uint64_t p = uint64_t(qp) * uint64_t(v[i]);
-      int64_t subres = int64_t(u[j+i]) - borrow - Lo_32(p);
-      u[j+i] = Lo_32(subres);
+      int64_t subres = int64_t(u[j + i]) - borrow - Lo_32(p);
+      u[j + i] = Lo_32(subres);
       borrow = Hi_32(p) - Hi_32(subres);
       DEBUG_KNUTH(dbgs() << "KnuthDiv: u[j+i] = " << u[j + i]
                          << ", borrow = " << borrow << '\n');
     }
-    bool isNeg = u[j+n] < borrow;
-    u[j+n] -= Lo_32(borrow);
+    bool isNeg = u[j + n] < borrow;
+    u[j + n] -= Lo_32(borrow);
 
     DEBUG_KNUTH(dbgs() << "KnuthDiv: after subtraction:");
     DEBUG_KNUTH(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i]);
     DEBUG_KNUTH(dbgs() << '\n');
 
     // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
     // negative, go to step D6; otherwise go on to step D7.
     q[j] = Lo_32(qp);
     if (isNeg) {
       // D6. [Add back]. The probability that this step is necessary is very
       // small, on the order of only 2/b. Make sure that test data accounts for
       // this possibility. Decrease q[j] by 1
       q[j]--;
       // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
       // A carry will occur to the left of u[j+n], and it should be ignored
       // since it cancels with the borrow that occurred in D4.
       bool carry = false;
       for (unsigned i = 0; i < n; i++) {
-        uint32_t limit = std::min(u[j+i],v[i]);
-        u[j+i] += v[i] + carry;
-        carry = u[j+i] < limit || (carry && u[j+i] == limit);
+        uint32_t limit = std::min(u[j + i], v[i]);
+        u[j + i] += v[i] + carry;
+        carry = u[j + i] < limit || (carry && u[j + i] == limit);
       }
-      u[j+n] += carry;
+      u[j + n] += carry;
     }
     DEBUG_KNUTH(dbgs() << "KnuthDiv: after correction:");
     DEBUG_KNUTH(for (int i = m + n; i >= 0; i--) dbgs() << " " << u[i]);
     DEBUG_KNUTH(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
 
     // D7. [Loop on j.]  Decrease j by one. Now if j >= 0, go back to D3.
   } while (--j >= 0);
 
   DEBUG_KNUTH(dbgs() << "KnuthDiv: quotient:");
   DEBUG_KNUTH(for (int i = m; i >= 0; i--) dbgs() << " " << q[i]);
   DEBUG_KNUTH(dbgs() << '\n');
 
   // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
   // remainder may be obtained by dividing u[...] by d. If r is non-null we
   // compute the remainder (urem uses this).
   if (r) {
     // The value d is expressed by the "shift" value above since we avoided
     // multiplication by d by using a shift left. So, all we have to do is
     // shift right here.
     if (shift) {
       uint32_t carry = 0;
       DEBUG_KNUTH(dbgs() << "KnuthDiv: remainder:");
-      for (int i = n-1; i >= 0; i--) {
+      for (int i = n - 1; i >= 0; i--) {
         r[i] = (u[i] >> shift) | carry;
         carry = u[i] << (32 - shift);
         DEBUG_KNUTH(dbgs() << " " << r[i]);
       }
     } else {
-      for (int i = n-1; i >= 0; i--) {
+      for (int i = n - 1; i >= 0; i--) {
         r[i] = u[i];
         DEBUG_KNUTH(dbgs() << " " << r[i]);
       }
     }
     DEBUG_KNUTH(dbgs() << '\n');
   }
   DEBUG_KNUTH(dbgs() << '\n');
 }
void APInt::divide(const WordType *LHS, unsigned lhsWords, const WordType *RHS,
 
   // Allocate space for the temporary values we need either on the stack, if
   // it will fit, or on the heap if it won't.
   uint32_t SPACE[128];
   uint32_t *U = nullptr;
   uint32_t *V = nullptr;
   uint32_t *Q = nullptr;
   uint32_t *R = nullptr;
-  if ((Remainder?4:3)*n+2*m+1 <= 128) {
+  if ((Remainder ? 4 : 3) * n + 2 * m + 1 <= 128) {
     U = &SPACE[0];
-    V = &SPACE[m+n+1];
-    Q = &SPACE[(m+n+1) + n];
+    V = &SPACE[m + n + 1];
+    Q = &SPACE[(m + n + 1) + n];
     if (Remainder)
-      R = &SPACE[(m+n+1) + n + (m+n)];
+      R = &SPACE[(m + n + 1) + n + (m + n)];
   } else {
     U = new uint32_t[m + n + 1];
     V = new uint32_t[n];
-    Q = new uint32_t[m+n];
+    Q = new uint32_t[m + n];
     if (Remainder)
       R = new uint32_t[n];
   }
 
   // Initialize the dividend
-  memset(U, 0, (m+n+1)*sizeof(uint32_t));
+  memset(U, 0, (m + n + 1) * sizeof(uint32_t));
   for (unsigned i = 0; i < lhsWords; ++i) {
     uint64_t tmp = LHS[i];
     U[i * 2] = Lo_32(tmp);
     U[i * 2 + 1] = Hi_32(tmp);
   }
-  U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
+  U[m + n] = 0; // this extra word is for "spill" in the Knuth algorithm.
 
   // Initialize the divisor
-  memset(V, 0, (n)*sizeof(uint32_t));
+  memset(V, 0, (n) * sizeof(uint32_t));
   for (unsigned i = 0; i < rhsWords; ++i) {
     uint64_t tmp = RHS[i];
     V[i * 2] = Lo_32(tmp);
     V[i * 2 + 1] = Hi_32(tmp);
   }
 
   // initialize the quotient and remainder
-  memset(Q, 0, (m+n) * sizeof(uint32_t));
+  memset(Q, 0, (m + n) * sizeof(uint32_t));
   if (Remainder)
     memset(R, 0, n * sizeof(uint32_t));
 
   // Now, adjust m and n for the Knuth division. n is the number of words in
   // the divisor. m is the number of words by which the dividend exceeds the
   // divisor (i.e. m+n is the length of the dividend). These sizes must not
   // contain any zero words or the Knuth algorithm fails.
-  for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
+  for (unsigned i = n; i > 0 && V[i - 1] == 0; i--) {
     n--;
     m++;
   }
-  for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
+  for (unsigned i = m + n; i > 0 && U[i - 1] == 0; i--)
     m--;
 
   // If we're left with only a single word for the divisor, Knuth doesn't work
   // so we implement the short division algorithm here. This is much simpler
   // and faster because we are certain that we can divide a 64-bit quantity
   // by a 32-bit quantity at hardware speed and short division is simply a
   // series of such operations. This is just like doing short division but we
   // are using base 2^32 instead of base 10.
if (n == 1) {
     // Now we're ready to invoke the Knuth classical divide algorithm. In this
     // case n > 1.
     KnuthDiv(U, V, Q, R, m, n);
   }
 
   // If the caller wants the quotient
   if (Quotient) {
     for (unsigned i = 0; i < lhsWords; ++i)
-      Quotient[i] = Make_64(Q[i*2+1], Q[i*2]);
+      Quotient[i] = Make_64(Q[i * 2 + 1], Q[i * 2]);
   }
 
   // If the caller wants the remainder
   if (Remainder) {
     for (unsigned i = 0; i < rhsWords; ++i)
-      Remainder[i] = Make_64(R[i*2+1], R[i*2]);
+      Remainder[i] = Make_64(R[i * 2 + 1], R[i * 2]);
   }
 
   // Clean up the memory we allocated.
   if (U != &SPACE[0]) {
-    delete [] U;
-    delete [] V;
-    delete [] Q;
-    delete [] R;
+    delete[] U;
+    delete[] V;
+    delete[] Q;
+    delete[] R;
   }
 }
 
 APInt APInt::udiv(const APInt &RHS) const {
   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
 
   // First, deal with the easy case
   if (isSingleWord()) {
     assert(RHS.U.VAL != 0 && "Divide by zero?");
     return APInt(BitWidth, U.VAL / RHS.U.VAL);
   }
 
   // Get some facts about the LHS and RHS number of bits and words
   unsigned lhsWords = getNumWords(getActiveBits());
-  unsigned rhsBits  = RHS.getActiveBits();
+  unsigned rhsBits = RHS.getActiveBits();
   unsigned rhsWords = getNumWords(rhsBits);
   assert(rhsWords && "Divided by zero???");
 
   // Deal with some degenerate cases
   if (!lhsWords)
     // 0 / X ===> 0
     return APInt(BitWidth, 0);
   if (rhsBits == 1)
if (RHS < 0)
       return -((-(*this)).urem(-RHS));
     return -((-(*this)).urem(RHS));
   }
   if (RHS < 0)
     return this->urem(-RHS);
   return this->urem(RHS);
 }
 
-void APInt::udivrem(const APInt &LHS, const APInt &RHS,
-                    APInt &Quotient, APInt &Remainder) {
+void APInt::udivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient,
+                    APInt &Remainder) {
   assert(LHS.BitWidth == RHS.BitWidth && "Bit widths must be the same");
   unsigned BitWidth = LHS.BitWidth;
 
   // First, deal with the easy case
   if (LHS.isSingleWord()) {
     assert(RHS.U.VAL != 0 && "Divide by zero?");
     uint64_t QuotVal = LHS.U.VAL / RHS.U.VAL;
     uint64_t RemVal = LHS.U.VAL % RHS.U.VAL;
     Quotient = APInt(BitWidth, QuotVal);
     Remainder = APInt(BitWidth, RemVal);
     return;
   }
 
   // Get some size facts about the dividend and divisor
   unsigned lhsWords = getNumWords(LHS.getActiveBits());
-  unsigned rhsBits  = RHS.getActiveBits();
+  unsigned rhsBits = RHS.getActiveBits();
   unsigned rhsWords = getNumWords(rhsBits);
   assert(rhsWords && "Performing divrem operation by zero ???");
 
   // Check the degenerate cases
   if (lhsWords == 0) {
-    Quotient = APInt(BitWidth, 0);    // 0 / Y ===> 0
-    Remainder = APInt(BitWidth, 0);   // 0 % Y ===> 0
+    Quotient = APInt(BitWidth, 0);  // 0 / Y ===> 0
+    Remainder = APInt(BitWidth, 0); // 0 % Y ===> 0
     return;
   }
 
   if (rhsBits == 1) {
-    Quotient = LHS;                   // X / 1 ===> X
-    Remainder = APInt(BitWidth, 0);   // X % 1 ===> 0
+    Quotient = LHS;                 // X / 1 ===> X
+    Remainder = APInt(BitWidth, 0); // X % 1 ===> 0
   }
 
   if (lhsWords < rhsWords || LHS.ult(RHS)) {
-    Remainder = LHS;                  // X % Y ===> X, iff X < Y
-    Quotient = APInt(BitWidth, 0);    // X / Y ===> 0, iff X < Y
+    Remainder = LHS;               // X % Y ===> X, iff X < Y
+    Quotient = APInt(BitWidth, 0); // X / Y ===> 0, iff X < Y
     return;
   }
 
   if (LHS == RHS) {
-    Quotient  = APInt(BitWidth, 1);   // X / X ===> 1
-    Remainder = APInt(BitWidth, 0);   // X % X ===> 0;
+    Quotient = APInt(BitWidth, 1);  // X / X ===> 1
+    Remainder = APInt(BitWidth, 0); // X % X ===> 0;
     return;
   }
 
   // Make sure there is enough space to hold the results.
   // NOTE: This assumes that reallocate won't affect any bits if it doesn't
   // change the size. This is necessary if Quotient or Remainder is aliased
   // with LHS or RHS.
   Quotient.reallocate(BitWidth);
if (LHS.isSingleWord()) {
     return;
   }
 
   // Get some size facts about the dividend and divisor
   unsigned lhsWords = getNumWords(LHS.getActiveBits());
 
   // Check the degenerate cases
   if (lhsWords == 0) {
-    Quotient = APInt(BitWidth, 0);    // 0 / Y ===> 0
-    Remainder = 0;                    // 0 % Y ===> 0
+    Quotient = APInt(BitWidth, 0); // 0 / Y ===> 0
+    Remainder = 0;                 // 0 % Y ===> 0
     return;
   }
 
   if (RHS == 1) {
-    Quotient = LHS;                   // X / 1 ===> X
-    Remainder = 0;                    // X % 1 ===> 0
+    Quotient = LHS; // X / 1 ===> X
+    Remainder = 0;  // X % 1 ===> 0
     return;
   }
 
   if (LHS.ult(RHS)) {
-    Remainder = LHS.getZExtValue();   // X % Y ===> X, iff X < Y
-    Quotient = APInt(BitWidth, 0);    // X / Y ===> 0, iff X < Y
+    Remainder = LHS.getZExtValue(); // X % Y ===> X, iff X < Y
+    Quotient = APInt(BitWidth, 0);  // X / Y ===> 0, iff X < Y
     return;
   }
 
   if (LHS == RHS) {
-    Quotient  = APInt(BitWidth, 1);   // X / X ===> 1
-    Remainder = 0;                    // X % X ===> 0;
+    Quotient = APInt(BitWidth, 1); // X / X ===> 1
+    Remainder = 0;                 // X % X ===> 0;
     return;
   }
 
   // Make sure there is enough space to hold the results.
   // NOTE: This assumes that reallocate won't affect any bits if it doesn't
   // change the size. This is necessary if Quotient is aliased with LHS.
   Quotient.reallocate(BitWidth);
 
   if (lhsWords == 1) { // rhsWords is 1 if lhsWords is 1.
     // There is only one word to consider so use the native versions.
     uint64_t lhsValue = LHS.U.pVal[0];
     Quotient = lhsValue / RHS;
     Remainder = lhsValue % RHS;
     return;
   }
 
   // Okay, lets do it the long way
   divide(LHS.U.pVal, lhsWords, &RHS, 1, Quotient.U.pVal, &Remainder);
   // Clear the rest of the Quotient.
   std::memset(Quotient.U.pVal + lhsWords, 0,
               (getNumWords(BitWidth) - lhsWords) * APINT_WORD_SIZE);
 }
 
-void APInt::sdivrem(const APInt &LHS, const APInt &RHS,
-                    APInt &Quotient, APInt &Remainder) {
+void APInt::sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient,
+                    APInt &Remainder) {
   if (LHS.isNegative()) {
     if (RHS.isNegative())
       APInt::udivrem(-LHS, -RHS, Quotient, Remainder);
     else {
       APInt::udivrem(-LHS, RHS, Quotient, Remainder);
       Quotient.negate();
     }
     Remainder.negate();
   } else if (RHS.isNegative()) {
     APInt::udivrem(LHS, -RHS, Quotient, Remainder);
     Quotient.negate();
   } else {
     APInt::udivrem(LHS, RHS, Quotient, Remainder);
   }
 }
 
-void APInt::sdivrem(const APInt &LHS, int64_t RHS,
-                    APInt &Quotient, int64_t &Remainder) {
+void APInt::sdivrem(const APInt &LHS, int64_t RHS, APInt &Quotient,
+                    int64_t &Remainder) {
   uint64_t R = Remainder;
   if (LHS.isNegative()) {
     if (RHS < 0)
       APInt::udivrem(-LHS, -RHS, Quotient, R);
     else {
       APInt::udivrem(-LHS, RHS, Quotient, R);
       Quotient.negate();
     }
     R = -R;
   } else if (RHS < 0) {
     APInt::udivrem(LHS, -RHS, Quotient, R);
     Quotient.negate();
   } else {
     APInt::udivrem(LHS, RHS, Quotient, R);
   }
   Remainder = R;
 }
 
 APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {
-  APInt Res = *this+RHS;
+  APInt Res = *this + RHS;
   Overflow = isNonNegative() == RHS.isNonNegative() &&
              Res.isNonNegative() != isNonNegative();
   return Res;
 }
 
 APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {
-  APInt Res = *this+RHS;
+  APInt Res = *this + RHS;
   Overflow = Res.ult(RHS);
   return Res;
 }
 
 APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {
   APInt Res = *this - RHS;
   Overflow = isNonNegative() != RHS.isNonNegative() &&
              Res.isNonNegative() != isNonNegative();
   return Res;
 }
 
 APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {
-  APInt Res = *this-RHS;
+  APInt Res = *this - RHS;
   Overflow = Res.ugt(*this);
   return Res;
 }
 
 APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {
   // MININT/-1  -->  overflow.
   Overflow = isMinSignedValue() && RHS.isAllOnes();
   return sdiv(RHS);
 }
 
 APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {
   APInt Res = *this * RHS;
 
   if (RHS != 0)
-    Overflow = Res.sdiv(RHS) != *this ||
-               (isMinSignedValue() && RHS.isAllOnes());
+    Overflow =
+        Res.sdiv(RHS) != *this || (isMinSignedValue() && RHS.isAllOnes());
   else
     Overflow = false;
   return Res;
 }
 
 APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {
   if (countLeadingZeros() + RHS.countLeadingZeros() + 2 <= BitWidth) {
     Overflow = true;
if (!Overflow)
     return Res;
 
   return APInt::getMaxValue(BitWidth);
 }
 
 void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
   // Check our assumptions here
   assert(!str.empty() && "Invalid string length");
-  assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
-          radix == 36) &&
-         "Radix should be 2, 8, 10, 16, or 36!");
+  assert(
+      (radix == 10 || radix == 8 || radix == 16 || radix == 2 || radix == 36) &&
 
   StringRef::iterator p = str.begin();
   size_t slen = str.size();
   bool isNeg = *p == '-';
   if (*p == '-' || *p == '+') {
     p++;
     slen--;
     assert(slen && "String is only a sign, needs a value.");
   }
   assert((slen <= numbits || radix != 2) && "Insufficient bit width");
-  assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
-  assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
-  assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
+  assert(((slen - 1) * 3 <= numbits || radix != 8) && "Insufficient bit width");
+  assert(((slen - 1) * 4 <= numbits || radix != 16) &&
+         "Insufficient bit width");
+  assert((((slen - 1) * 64) / 22 <= numbits || radix != 10) &&
          "Insufficient bit width");
 
   // Allocate memory if needed
   if (isSingleWord())
     U.VAL = 0;
   else
     U.pVal = getClearedMemory(getNumWords());
 
for (StringRef::iterator e = str.end(); p != e; ++p) {
     // Add in the digit we just interpreted
     *this += digit;
   }
   // If its negative, put it in two's complement form
   if (isNeg)
     this->negate();
 }
 
-void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
-                     bool Signed, bool formatAsCLiteral) const {
-  assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 ||
-          Radix == 36) &&
-         "Radix should be 2, 8, 10, 16, or 36!");
+void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix, bool Signed,
+                     bool formatAsCLiteral) const {
+  assert(
+      (Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 || Radix == 36) &&
 
   const char *Prefix = "";
   if (formatAsCLiteral) {
     switch (Radix) {
-      case 2:
-        // Binary literals are a non-standard extension added in gcc 4.3:
-        // http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html
-        Prefix = "0b";
-        break;
-      case 8:
-        Prefix = "0";
-        break;
-      case 10:
-        break; // No prefix
-      case 16:
-        Prefix = "0x";
-        break;
-      default:
-        llvm_unreachable("Invalid radix!");
     }
   }
 
   // First, check for a zero value and just short circuit the logic below.
   if (isZero()) {
     while (*Prefix) {
       Str.push_back(*Prefix);
       ++Prefix;
while (Tmp.getBoolValue()) {
       uint64_t Digit;
       udivrem(Tmp, Radix, Tmp, Digit);
       assert(Digit < Radix && "divide failed");
       Str.push_back(Digits[Digit]);
     }
   }
 
   // Reverse the digits before returning.
-  std::reverse(Str.begin()+StartDig, Str.end());
+  std::reverse(Str.begin() + StartDig, Str.end());
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD void APInt::dump() const {
   SmallString<40> S, U;
   this->toStringUnsigned(U);
   this->toStringSigned(S);
-  dbgs() << "APInt(" << BitWidth << "b, "
-         << U << "u " << S << "s)\n";
+  dbgs() << "APInt(" << BitWidth << "b, " << U << "u " << S << "s)\n";
 }
 #endif
 
 void APInt::print(raw_ostream &OS, bool isSigned) const {
   SmallString<40> S;
-  this->toString(S, 10, isSigned, /* formatAsCLiteral = */false);
+  this->toString(S, 10, isSigned, /* formatAsCLiteral = */ false);
   OS << S;
 }
 
 // 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!");
 
 // 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);
+  return ~(APInt::WordType)0 >> (APInt::APINT_BITS_PER_WORD - bits);
 }
 
 /// 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.
unsigned APInt::tcMSB(const WordType *parts, unsigned 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.
 /// */
-void
-APInt::tcExtract(WordType *dst, unsigned dstCount, const WordType *src,
+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);
 
   unsigned shift = srcLSB % APINT_BITS_PER_WORD;
   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.
   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);
+    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);
+      dst[dstParts - 1] &= lowBitMask(srcBits % APINT_BITS_PER_WORD);
   }
 
   // Clear high parts.
   while (dstParts < dstCount)
     dst[dstParts++] = 0;
 }
 
 //// 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) {
+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;
       c = (dst[i] <= l);
     } else {
       dst[i] += rhs[i];
       c = (dst[i] < l);
     }
   }
 
   return c;
 }
 
 /// This function adds a single "word" integer, src, to the multiple
 /// "word" integer array, dst[]. dst[] is modified to reflect the addition and
 /// 1 is returned if there is a carry out, otherwise 0 is returned.
 /// @returns the carry of the addition.
-APInt::WordType APInt::tcAddPart(WordType *dst, WordType src,
-                                 unsigned parts) {
+APInt::WordType APInt::tcAddPart(WordType *dst, WordType src, unsigned parts) {
   for (unsigned i = 0; i < parts; ++i) {
     dst[i] += src;
     if (dst[i] >= src)
       return 0; // No need to carry so exit early.
-    src = 1; // Carry one to next digit.
+    src = 1;    // Carry one to next digit.
   }
 
   return 1;
 }
 
 /// 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) {

 /// @returns the borrow out of the subtraction
 APInt::WordType APInt::tcSubtractPart(WordType *dst, WordType src,
                                       unsigned parts) {
   for (unsigned i = 0; i < parts; ++i) {
     WordType Dst = dst[i];
     dst[i] -= src;
     if (src <= Dst)
       return 0; // No need to borrow so exit early.
-    src = 1; // We have to "borrow 1" from next "word"
+    src = 1;    // We have to "borrow 1" from next "word"
   }
 
   return 1;
 }
 
 /// 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.
 int APInt::tcMultiplyPart(WordType *dst, const WordType *src,
                           WordType multiplier, WordType carry,
-                          unsigned srcParts, unsigned dstParts,
-                          bool add) {
+                          unsigned srcParts, unsigned dstParts, bool add) {
   // 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.
   unsigned n = std::min(dstParts, srcParts);
 
   for (unsigned i = 0; i < n; i++) {
int APInt::tcMultiplyPart(WordType *dst, const WordType *src,
   // 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.
-int APInt::tcMultiply(WordType *dst, const WordType *lhs,
-                      const WordType *rhs, unsigned parts) {
+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);
+    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.
   if (lhsParts > rhsParts)
-    return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
+    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.
-int APInt::tcDivide(WordType *lhs, const WordType *rhs,
-                    WordType *remainder, WordType *srhs,
-                    unsigned parts) {
+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);
+  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.
   for (;;) {
     int compare = tcCompare(remainder, srhs, parts);
     if (compare >= 0) {
       tcSubtract(remainder, srhs, 0, parts);
       lhs[n] |= mask;
     }
 
     if (shiftCount == 0)
       break;
     shiftCount--;
     tcShiftRight(srhs, parts, 1);
     if ((mask >>= 1) == 0) {
-      mask = (WordType) 1 << (APINT_BITS_PER_WORD - 1);
+      mask = (WordType)1 << (APINT_BITS_PER_WORD - 1);
       n--;
     }
   }
 
   return false;
 }
 
 /// Shift a bignum left Cound bits in-place. Shifted in bits are zero. There are
void APInt::tcShiftLeft(WordType *Dst, unsigned Words, unsigned Count) {
   // Fastpath for moving by whole words.
   if (BitShift == 0) {
     std::memmove(Dst + WordShift, Dst, (Words - WordShift) * APINT_WORD_SIZE);
   } else {
     while (Words-- > WordShift) {
       Dst[Words] = Dst[Words - WordShift] << BitShift;
       if (Words > WordShift)
         Dst[Words] |=
             Dst[Words - WordShift - 1] >> (APINT_BITS_PER_WORD - BitShift);
     }
   }
 
   // Fill in the remainder with 0s.
   std::memset(Dst, 0, WordShift * APINT_WORD_SIZE);
 }
 
 /// Shift a bignum right Count bits in-place. Shifted in bits are zero. There
if (BitShift == 0) {
     }
   }
 
   // Fill in the remainder with 0s.
   std::memset(Dst + WordsToMove, 0, WordShift * APINT_WORD_SIZE);
 }
 
 // Comparison (unsigned) of two bignums.
-int APInt::tcCompare(const WordType *lhs, const WordType *rhs,
-                     unsigned parts) {
+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;
 }

 llvm::APIntOps::SolveQuadraticEquationWrap(APInt A, APInt B, APInt C,
                                            unsigned RangeWidth) {
   unsigned CoeffWidth = A.getBitWidth();
   assert(CoeffWidth == B.getBitWidth() && CoeffWidth == C.getBitWidth());
   assert(RangeWidth <= CoeffWidth &&
          "Value range width should be less than coefficient width");
   assert(RangeWidth > 1 && "Value range bit width should be > 1");
 
-  LLVM_DEBUG(dbgs() << __func__ << ": solving " << A << "x^2 + " << B
-                    << "x + " << C << ", rw:" << RangeWidth << '\n');
+  LLVM_DEBUG(dbgs() << __func__ << ": solving " << A << "x^2 + " << B << "x + "
+                    << C << ", rw:" << RangeWidth << '\n');
 
   // Identify 0 as a (non)solution immediately.
   if (C.sextOrTrunc(RangeWidth).isZero()) {
     LLVM_DEBUG(dbgs() << __func__ << ": zero solution\n");
     return APInt(CoeffWidth, 0);
   }
 
   // The result of APInt arithmetic has the same bit width as the operands,
llvm::APIntOps::SolveQuadraticEquationWrap(APInt A, APInt B, APInt C,
   // of solving q(x) = kR to solving shifted_q(x) = 0.
   // (The interesting solutions are the ceilings of the real number
   // solutions.)
   APInt R = APInt::getOneBitSet(CoeffWidth, RangeWidth);
   APInt TwoA = 2 * A;
   APInt SqrB = B * B;
   bool PickLow;
 
-  auto RoundUp = [] (const APInt &V, const APInt &A) -> APInt {
+  auto RoundUp = [](const APInt &V, const APInt &A) -> APInt {
     assert(A.isStrictlyPositive());
     APInt T = V.abs().urem(A);
     if (T.isZero())
       return V;
-    return V.isNegative() ? V+T : V+(A-T);
+    return V.isNegative() ? V + T : V + (A - T);
   };
 
   // The vertex of the parabola is at -B/2A, but since A > 0, it's negative
   // iff B is positive.
   if (B.isNonNegative()) {
     // If B >= 0, the vertex it at a negative location (or at 0), so in
     // order to have a non-negative solution we need to pick k that makes
     // C-kR negative. To satisfy all the requirements for the solution
     // that we are looking for, it needs to be closest to 0 of all k.
     C = C.srem(R);
     if (C.isStrictlyPositive())
       C -= R;
     // Pick the greater solution.
     PickLow = false;
   } else {
     // If B < 0, the vertex is at a positive location. For any solution
     // to exist, the discriminant must be non-negative. This means that
     // C-kR <= B^2/4A is a necessary condition for k, i.e. there is a
     // lower bound on values of k: kR >= C - B^2/4A.
-    APInt LowkR = C - SqrB.udiv(2*TwoA); // udiv because all values > 0.
+    APInt LowkR = C - SqrB.udiv(2 * TwoA); // udiv because all values > 0.
     // Round LowkR up (towards +inf) to the nearest kR.
     LowkR = RoundUp(LowkR, R);
 
     // If there exists k meeting the condition above, and such that
     // C-kR > 0, there will be two positive real number solutions of
     // q(x) = kR. Out of all such values of k, pick the one that makes
     // C-kR closest to 0, (i.e. pick maximum k such that C-kR > 0).
     // In other words, find maximum k such that LowkR <= kR < C.
     if (C.sgt(LowkR)) {
       // If LowkR < C, then such a k is guaranteed to exist because
       // LowkR itself is a multiple of R.
-      C -= -RoundUp(-C, R);      // C = C - RoundDown(C, R)
+      C -= -RoundUp(-C, R); // C = C - RoundDown(C, R)
       // Pick the smaller solution.
       PickLow = true;
     } else {
       // If C-kR < 0 for all potential k's, it means that one solution
       // will be negative, while the other will be positive. The positive
       // solution will shift towards 0 if the parabola is moved up.
       // Pick the kR closest to the lower bound (i.e. make C-kR closest
       // to 0, or in other words, out of all parabolas that have solutions,
       // pick the one that is the farthest "up").
       // Since LowkR is itself a multiple of R, simply take C-LowkR.
       C -= LowkR;
       // Pick the greater solution.
       PickLow = false;
     }
   }
 
   LLVM_DEBUG(dbgs() << __func__ << ": updated coefficients " << A << "x^2 + "
                     << B << "x + " << C << ", rw:" << RangeWidth << '\n');
 
-  APInt D = SqrB - 4*A*C;
+  APInt D = SqrB - 4 * A * C;
   assert(D.isNonNegative() && "Negative discriminant");
   APInt SQ = D.sqrt();
 
   APInt Q = SQ * SQ;
   bool InexactSQ = Q != D;
   // The calculated SQ may actually be greater than the exact (non-integer)
   // value. If that's the case, decrement SQ to get a value that is lower.
   if (Q.sgt(D))
     SQ -= 1;
 
   APInt X;
   APInt Rem;
 
   // SQ is rounded down (i.e SQ * SQ <= D), so the roots may be inexact.
   // When using the quadratic formula directly, the calculated low root
   // may be greater than the exact one, since we would be subtracting SQ.
   // To make sure that the calculated root is not greater than the exact
   // one, subtract SQ+1 when calculating the low root (for inexact value
   // of SQ).
   if (PickLow)
-    APInt::sdivrem(-B - (SQ+InexactSQ), TwoA, X, Rem);
+    APInt::sdivrem(-B - (SQ + InexactSQ), TwoA, X, Rem);
   else
     APInt::sdivrem(-B + SQ, TwoA, X, Rem);
 
   // The updated coefficients should be such that the (exact) solution is
   // positive. Since APInt division rounds towards 0, the calculated one
   // can be 0, but cannot be negative.
   assert(X.isNonNegative() && "Solution should be non-negative");
 
   if (!InexactSQ && Rem.isZero()) {
     LLVM_DEBUG(dbgs() << __func__ << ": solution (root): " << X << '\n');
     return X;
   }
 
-  assert((SQ*SQ).sle(D) && "SQ = |_sqrt(D)_|, so SQ*SQ <= D");
+  assert((SQ * SQ).sle(D) && "SQ = |_sqrt(D)_|, so SQ*SQ <= D");
   // The exact value of the square root of D should be between SQ and SQ+1.
   // This implies that the solution should be between that corresponding to
   // SQ (i.e. X) and that corresponding to SQ+1.
   //
   // The calculated X cannot be greater than the exact (real) solution.
   // Actually it must be strictly less than the exact solution, while
   // X+1 will be greater than or equal to it.
 
-  APInt VX = (A*X + B)*X + C;
-  APInt VY = VX + TwoA*X + A + B;
+  APInt VX = (A * X + B) * X + C;
+  APInt VY = VX + TwoA * X + A + B;
   bool SignChange =
       VX.isNegative() != VY.isNegative() || VX.isZero() != VY.isZero();
   // If the sign did not change between X and X+1, X is not a valid solution.
   // This could happen when the actual (exact) roots don't have an integer
   // between them, so they would both be contained between X and X+1.
   if (!SignChange) {
     LLVM_DEBUG(dbgs() << __func__ << ": no valid solution\n");
-    return std::nullopt;
+    return None;
   }
 
   X += 1;
   LLVM_DEBUG(dbgs() << __func__ << ": solution (wrap): " << X << '\n');
   return X;
 }
 
 Optional<unsigned>
 llvm::APIntOps::GetMostSignificantDifferentBit(const APInt &A, const APInt &B) {
   assert(A.getBitWidth() == B.getBitWidth() && "Must have the same bitwidth");
   if (A == B)
-    return std::nullopt;
+    return llvm::None;
   return A.getBitWidth() - ((A ^ B).countLeadingZeros() + 1);
 }
 
 APInt llvm::APIntOps::ScaleBitMask(const APInt &A, unsigned NewBitWidth,
                                    bool MatchAllBits) {
   unsigned OldBitWidth = A.getBitWidth();
   assert((((OldBitWidth % NewBitWidth) == 0) ||
           ((NewBitWidth % OldBitWidth) == 0)) &&
APInt llvm::APIntOps::ScaleBitMask(const APInt &A, unsigned NewBitWidth,
 
   return NewA;
 }
 
 /// StoreIntToMemory - Fills the StoreBytes bytes of memory starting from Dst
 /// with the integer held in IntVal.
 void llvm::StoreIntToMemory(const APInt &IntVal, uint8_t *Dst,
                             unsigned StoreBytes) {
-  assert((IntVal.getBitWidth()+7)/8 >= StoreBytes && "Integer too small!");
+  assert((IntVal.getBitWidth() + 7) / 8 >= StoreBytes && "Integer too small!");
   const uint8_t *Src = (const uint8_t *)IntVal.getRawData();
 
   if (sys::IsLittleEndianHost) {
     // Little-endian host - the source is ordered from LSB to MSB.  Order the
     // destination from LSB to MSB: Do a straight copy.
     memcpy(Dst, Src, StoreBytes);
   } else {
     // Big-endian host - the source is an array of 64 bit words ordered from
if (sys::IsLittleEndianHost) {
     memcpy(Dst, Src + sizeof(uint64_t) - StoreBytes, StoreBytes);
   }
 }
 
 /// LoadIntFromMemory - Loads the integer stored in the LoadBytes bytes starting
 /// from Src into IntVal, which is assumed to be wide enough and to hold zero.
 void llvm::LoadIntFromMemory(APInt &IntVal, const uint8_t *Src,
                              unsigned LoadBytes) {
-  assert((IntVal.getBitWidth()+7)/8 >= LoadBytes && "Integer too small!");
-  uint8_t *Dst = reinterpret_cast<uint8_t *>(
-                   const_cast<uint64_t *>(IntVal.getRawData()));
+  assert((IntVal.getBitWidth() + 7) / 8 >= LoadBytes && "Integer too small!");
+  uint8_t *Dst =
+      reinterpret_cast<uint8_t *>(const_cast<uint64_t *>(IntVal.getRawData()));
 
   if (sys::IsLittleEndianHost)
     // Little-endian host - the destination must be ordered from LSB to MSB.
     // The source is ordered from LSB to MSB: Do a straight copy.
     memcpy(Dst, Src, LoadBytes);
   else {
     // Big-endian - the destination is an array of 64 bit words ordered from
     // LSW to MSW.  Each word must be ordered from MSB to LSB.  The source is