Home | History | Annotate | Download | only in Support
      1 //===- llvm/Support/ScaledNumber.h - Support for scaled numbers -*- C++ -*-===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     10 // This file contains functions (and a class) useful for working with scaled
     11 // numbers -- in particular, pairs of integers where one represents digits and
     12 // another represents a scale.  The functions are helpers and live in the
     13 // namespace ScaledNumbers.  The class ScaledNumber is useful for modelling
     14 // certain cost metrics that need simple, integer-like semantics that are easy
     15 // to reason about.
     16 //
     17 // These might remind you of soft-floats.  If you want one of those, you're in
     18 // the wrong place.  Look at include/llvm/ADT/APFloat.h instead.
     19 //
     20 //===----------------------------------------------------------------------===//
     21 
     22 #ifndef LLVM_SUPPORT_SCALEDNUMBER_H
     23 #define LLVM_SUPPORT_SCALEDNUMBER_H
     24 
     25 #include "llvm/Support/MathExtras.h"
     26 #include <algorithm>
     27 #include <cstdint>
     28 #include <limits>
     29 #include <string>
     30 #include <tuple>
     31 #include <utility>
     32 
     33 namespace llvm {
     34 namespace ScaledNumbers {
     35 
     36 /// \brief Maximum scale; same as APFloat for easy debug printing.
     37 const int32_t MaxScale = 16383;
     38 
     39 /// \brief Maximum scale; same as APFloat for easy debug printing.
     40 const int32_t MinScale = -16382;
     41 
     42 /// \brief Get the width of a number.
     43 template <class DigitsT> inline int getWidth() { return sizeof(DigitsT) * 8; }
     44 
     45 /// \brief Conditionally round up a scaled number.
     46 ///
     47 /// Given \c Digits and \c Scale, round up iff \c ShouldRound is \c true.
     48 /// Always returns \c Scale unless there's an overflow, in which case it
     49 /// returns \c 1+Scale.
     50 ///
     51 /// \pre adding 1 to \c Scale will not overflow INT16_MAX.
     52 template <class DigitsT>
     53 inline std::pair<DigitsT, int16_t> getRounded(DigitsT Digits, int16_t Scale,
     54                                               bool ShouldRound) {
     55   static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
     56 
     57   if (ShouldRound)
     58     if (!++Digits)
     59       // Overflow.
     60       return std::make_pair(DigitsT(1) << (getWidth<DigitsT>() - 1), Scale + 1);
     61   return std::make_pair(Digits, Scale);
     62 }
     63 
     64 /// \brief Convenience helper for 32-bit rounding.
     65 inline std::pair<uint32_t, int16_t> getRounded32(uint32_t Digits, int16_t Scale,
     66                                                  bool ShouldRound) {
     67   return getRounded(Digits, Scale, ShouldRound);
     68 }
     69 
     70 /// \brief Convenience helper for 64-bit rounding.
     71 inline std::pair<uint64_t, int16_t> getRounded64(uint64_t Digits, int16_t Scale,
     72                                                  bool ShouldRound) {
     73   return getRounded(Digits, Scale, ShouldRound);
     74 }
     75 
     76 /// \brief Adjust a 64-bit scaled number down to the appropriate width.
     77 ///
     78 /// \pre Adding 64 to \c Scale will not overflow INT16_MAX.
     79 template <class DigitsT>
     80 inline std::pair<DigitsT, int16_t> getAdjusted(uint64_t Digits,
     81                                                int16_t Scale = 0) {
     82   static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
     83 
     84   const int Width = getWidth<DigitsT>();
     85   if (Width == 64 || Digits <= std::numeric_limits<DigitsT>::max())
     86     return std::make_pair(Digits, Scale);
     87 
     88   // Shift right and round.
     89   int Shift = 64 - Width - countLeadingZeros(Digits);
     90   return getRounded<DigitsT>(Digits >> Shift, Scale + Shift,
     91                              Digits & (UINT64_C(1) << (Shift - 1)));
     92 }
     93 
     94 /// \brief Convenience helper for adjusting to 32 bits.
     95 inline std::pair<uint32_t, int16_t> getAdjusted32(uint64_t Digits,
     96                                                   int16_t Scale = 0) {
     97   return getAdjusted<uint32_t>(Digits, Scale);
     98 }
     99 
    100 /// \brief Convenience helper for adjusting to 64 bits.
    101 inline std::pair<uint64_t, int16_t> getAdjusted64(uint64_t Digits,
    102                                                   int16_t Scale = 0) {
    103   return getAdjusted<uint64_t>(Digits, Scale);
    104 }
    105 
    106 /// \brief Multiply two 64-bit integers to create a 64-bit scaled number.
    107 ///
    108 /// Implemented with four 64-bit integer multiplies.
    109 std::pair<uint64_t, int16_t> multiply64(uint64_t LHS, uint64_t RHS);
    110 
    111 /// \brief Multiply two 32-bit integers to create a 32-bit scaled number.
    112 ///
    113 /// Implemented with one 64-bit integer multiply.
    114 template <class DigitsT>
    115 inline std::pair<DigitsT, int16_t> getProduct(DigitsT LHS, DigitsT RHS) {
    116   static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
    117 
    118   if (getWidth<DigitsT>() <= 32 || (LHS <= UINT32_MAX && RHS <= UINT32_MAX))
    119     return getAdjusted<DigitsT>(uint64_t(LHS) * RHS);
    120 
    121   return multiply64(LHS, RHS);
    122 }
    123 
    124 /// \brief Convenience helper for 32-bit product.
    125 inline std::pair<uint32_t, int16_t> getProduct32(uint32_t LHS, uint32_t RHS) {
    126   return getProduct(LHS, RHS);
    127 }
    128 
    129 /// \brief Convenience helper for 64-bit product.
    130 inline std::pair<uint64_t, int16_t> getProduct64(uint64_t LHS, uint64_t RHS) {
    131   return getProduct(LHS, RHS);
    132 }
    133 
    134 /// \brief Divide two 64-bit integers to create a 64-bit scaled number.
    135 ///
    136 /// Implemented with long division.
    137 ///
    138 /// \pre \c Dividend and \c Divisor are non-zero.
    139 std::pair<uint64_t, int16_t> divide64(uint64_t Dividend, uint64_t Divisor);
    140 
    141 /// \brief Divide two 32-bit integers to create a 32-bit scaled number.
    142 ///
    143 /// Implemented with one 64-bit integer divide/remainder pair.
    144 ///
    145 /// \pre \c Dividend and \c Divisor are non-zero.
    146 std::pair<uint32_t, int16_t> divide32(uint32_t Dividend, uint32_t Divisor);
    147 
    148 /// \brief Divide two 32-bit numbers to create a 32-bit scaled number.
    149 ///
    150 /// Implemented with one 64-bit integer divide/remainder pair.
    151 ///
    152 /// Returns \c (DigitsT_MAX, MaxScale) for divide-by-zero (0 for 0/0).
    153 template <class DigitsT>
    154 std::pair<DigitsT, int16_t> getQuotient(DigitsT Dividend, DigitsT Divisor) {
    155   static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
    156   static_assert(sizeof(DigitsT) == 4 || sizeof(DigitsT) == 8,
    157                 "expected 32-bit or 64-bit digits");
    158 
    159   // Check for zero.
    160   if (!Dividend)
    161     return std::make_pair(0, 0);
    162   if (!Divisor)
    163     return std::make_pair(std::numeric_limits<DigitsT>::max(), MaxScale);
    164 
    165   if (getWidth<DigitsT>() == 64)
    166     return divide64(Dividend, Divisor);
    167   return divide32(Dividend, Divisor);
    168 }
    169 
    170 /// \brief Convenience helper for 32-bit quotient.
    171 inline std::pair<uint32_t, int16_t> getQuotient32(uint32_t Dividend,
    172                                                   uint32_t Divisor) {
    173   return getQuotient(Dividend, Divisor);
    174 }
    175 
    176 /// \brief Convenience helper for 64-bit quotient.
    177 inline std::pair<uint64_t, int16_t> getQuotient64(uint64_t Dividend,
    178                                                   uint64_t Divisor) {
    179   return getQuotient(Dividend, Divisor);
    180 }
    181 
    182 /// \brief Implementation of getLg() and friends.
    183 ///
    184 /// Returns the rounded lg of \c Digits*2^Scale and an int specifying whether
    185 /// this was rounded up (1), down (-1), or exact (0).
    186 ///
    187 /// Returns \c INT32_MIN when \c Digits is zero.
    188 template <class DigitsT>
    189 inline std::pair<int32_t, int> getLgImpl(DigitsT Digits, int16_t Scale) {
    190   static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
    191 
    192   if (!Digits)
    193     return std::make_pair(INT32_MIN, 0);
    194 
    195   // Get the floor of the lg of Digits.
    196   int32_t LocalFloor = sizeof(Digits) * 8 - countLeadingZeros(Digits) - 1;
    197 
    198   // Get the actual floor.
    199   int32_t Floor = Scale + LocalFloor;
    200   if (Digits == UINT64_C(1) << LocalFloor)
    201     return std::make_pair(Floor, 0);
    202 
    203   // Round based on the next digit.
    204   assert(LocalFloor >= 1);
    205   bool Round = Digits & UINT64_C(1) << (LocalFloor - 1);
    206   return std::make_pair(Floor + Round, Round ? 1 : -1);
    207 }
    208 
    209 /// \brief Get the lg (rounded) of a scaled number.
    210 ///
    211 /// Get the lg of \c Digits*2^Scale.
    212 ///
    213 /// Returns \c INT32_MIN when \c Digits is zero.
    214 template <class DigitsT> int32_t getLg(DigitsT Digits, int16_t Scale) {
    215   return getLgImpl(Digits, Scale).first;
    216 }
    217 
    218 /// \brief Get the lg floor of a scaled number.
    219 ///
    220 /// Get the floor of the lg of \c Digits*2^Scale.
    221 ///
    222 /// Returns \c INT32_MIN when \c Digits is zero.
    223 template <class DigitsT> int32_t getLgFloor(DigitsT Digits, int16_t Scale) {
    224   auto Lg = getLgImpl(Digits, Scale);
    225   return Lg.first - (Lg.second > 0);
    226 }
    227 
    228 /// \brief Get the lg ceiling of a scaled number.
    229 ///
    230 /// Get the ceiling of the lg of \c Digits*2^Scale.
    231 ///
    232 /// Returns \c INT32_MIN when \c Digits is zero.
    233 template <class DigitsT> int32_t getLgCeiling(DigitsT Digits, int16_t Scale) {
    234   auto Lg = getLgImpl(Digits, Scale);
    235   return Lg.first + (Lg.second < 0);
    236 }
    237 
    238 /// \brief Implementation for comparing scaled numbers.
    239 ///
    240 /// Compare two 64-bit numbers with different scales.  Given that the scale of
    241 /// \c L is higher than that of \c R by \c ScaleDiff, compare them.  Return -1,
    242 /// 1, and 0 for less than, greater than, and equal, respectively.
    243 ///
    244 /// \pre 0 <= ScaleDiff < 64.
    245 int compareImpl(uint64_t L, uint64_t R, int ScaleDiff);
    246 
    247 /// \brief Compare two scaled numbers.
    248 ///
    249 /// Compare two scaled numbers.  Returns 0 for equal, -1 for less than, and 1
    250 /// for greater than.
    251 template <class DigitsT>
    252 int compare(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale) {
    253   static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
    254 
    255   // Check for zero.
    256   if (!LDigits)
    257     return RDigits ? -1 : 0;
    258   if (!RDigits)
    259     return 1;
    260 
    261   // Check for the scale.  Use getLgFloor to be sure that the scale difference
    262   // is always lower than 64.
    263   int32_t lgL = getLgFloor(LDigits, LScale), lgR = getLgFloor(RDigits, RScale);
    264   if (lgL != lgR)
    265     return lgL < lgR ? -1 : 1;
    266 
    267   // Compare digits.
    268   if (LScale < RScale)
    269     return compareImpl(LDigits, RDigits, RScale - LScale);
    270 
    271   return -compareImpl(RDigits, LDigits, LScale - RScale);
    272 }
    273 
    274 /// \brief Match scales of two numbers.
    275 ///
    276 /// Given two scaled numbers, match up their scales.  Change the digits and
    277 /// scales in place.  Shift the digits as necessary to form equivalent numbers,
    278 /// losing precision only when necessary.
    279 ///
    280 /// If the output value of \c LDigits (\c RDigits) is \c 0, the output value of
    281 /// \c LScale (\c RScale) is unspecified.
    282 ///
    283 /// As a convenience, returns the matching scale.  If the output value of one
    284 /// number is zero, returns the scale of the other.  If both are zero, which
    285 /// scale is returned is unspecified.
    286 template <class DigitsT>
    287 int16_t matchScales(DigitsT &LDigits, int16_t &LScale, DigitsT &RDigits,
    288                     int16_t &RScale) {
    289   static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
    290 
    291   if (LScale < RScale)
    292     // Swap arguments.
    293     return matchScales(RDigits, RScale, LDigits, LScale);
    294   if (!LDigits)
    295     return RScale;
    296   if (!RDigits || LScale == RScale)
    297     return LScale;
    298 
    299   // Now LScale > RScale.  Get the difference.
    300   int32_t ScaleDiff = int32_t(LScale) - RScale;
    301   if (ScaleDiff >= 2 * getWidth<DigitsT>()) {
    302     // Don't bother shifting.  RDigits will get zero-ed out anyway.
    303     RDigits = 0;
    304     return LScale;
    305   }
    306 
    307   // Shift LDigits left as much as possible, then shift RDigits right.
    308   int32_t ShiftL = std::min<int32_t>(countLeadingZeros(LDigits), ScaleDiff);
    309   assert(ShiftL < getWidth<DigitsT>() && "can't shift more than width");
    310 
    311   int32_t ShiftR = ScaleDiff - ShiftL;
    312   if (ShiftR >= getWidth<DigitsT>()) {
    313     // Don't bother shifting.  RDigits will get zero-ed out anyway.
    314     RDigits = 0;
    315     return LScale;
    316   }
    317 
    318   LDigits <<= ShiftL;
    319   RDigits >>= ShiftR;
    320 
    321   LScale -= ShiftL;
    322   RScale += ShiftR;
    323   assert(LScale == RScale && "scales should match");
    324   return LScale;
    325 }
    326 
    327 /// \brief Get the sum of two scaled numbers.
    328 ///
    329 /// Get the sum of two scaled numbers with as much precision as possible.
    330 ///
    331 /// \pre Adding 1 to \c LScale (or \c RScale) will not overflow INT16_MAX.
    332 template <class DigitsT>
    333 std::pair<DigitsT, int16_t> getSum(DigitsT LDigits, int16_t LScale,
    334                                    DigitsT RDigits, int16_t RScale) {
    335   static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
    336 
    337   // Check inputs up front.  This is only relevant if addition overflows, but
    338   // testing here should catch more bugs.
    339   assert(LScale < INT16_MAX && "scale too large");
    340   assert(RScale < INT16_MAX && "scale too large");
    341 
    342   // Normalize digits to match scales.
    343   int16_t Scale = matchScales(LDigits, LScale, RDigits, RScale);
    344 
    345   // Compute sum.
    346   DigitsT Sum = LDigits + RDigits;
    347   if (Sum >= RDigits)
    348     return std::make_pair(Sum, Scale);
    349 
    350   // Adjust sum after arithmetic overflow.
    351   DigitsT HighBit = DigitsT(1) << (getWidth<DigitsT>() - 1);
    352   return std::make_pair(HighBit | Sum >> 1, Scale + 1);
    353 }
    354 
    355 /// \brief Convenience helper for 32-bit sum.
    356 inline std::pair<uint32_t, int16_t> getSum32(uint32_t LDigits, int16_t LScale,
    357                                              uint32_t RDigits, int16_t RScale) {
    358   return getSum(LDigits, LScale, RDigits, RScale);
    359 }
    360 
    361 /// \brief Convenience helper for 64-bit sum.
    362 inline std::pair<uint64_t, int16_t> getSum64(uint64_t LDigits, int16_t LScale,
    363                                              uint64_t RDigits, int16_t RScale) {
    364   return getSum(LDigits, LScale, RDigits, RScale);
    365 }
    366 
    367 /// \brief Get the difference of two scaled numbers.
    368 ///
    369 /// Get LHS minus RHS with as much precision as possible.
    370 ///
    371 /// Returns \c (0, 0) if the RHS is larger than the LHS.
    372 template <class DigitsT>
    373 std::pair<DigitsT, int16_t> getDifference(DigitsT LDigits, int16_t LScale,
    374                                           DigitsT RDigits, int16_t RScale) {
    375   static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
    376 
    377   // Normalize digits to match scales.
    378   const DigitsT SavedRDigits = RDigits;
    379   const int16_t SavedRScale = RScale;
    380   matchScales(LDigits, LScale, RDigits, RScale);
    381 
    382   // Compute difference.
    383   if (LDigits <= RDigits)
    384     return std::make_pair(0, 0);
    385   if (RDigits || !SavedRDigits)
    386     return std::make_pair(LDigits - RDigits, LScale);
    387 
    388   // Check if RDigits just barely lost its last bit.  E.g., for 32-bit:
    389   //
    390   //   1*2^32 - 1*2^0 == 0xffffffff != 1*2^32
    391   const auto RLgFloor = getLgFloor(SavedRDigits, SavedRScale);
    392   if (!compare(LDigits, LScale, DigitsT(1), RLgFloor + getWidth<DigitsT>()))
    393     return std::make_pair(std::numeric_limits<DigitsT>::max(), RLgFloor);
    394 
    395   return std::make_pair(LDigits, LScale);
    396 }
    397 
    398 /// \brief Convenience helper for 32-bit difference.
    399 inline std::pair<uint32_t, int16_t> getDifference32(uint32_t LDigits,
    400                                                     int16_t LScale,
    401                                                     uint32_t RDigits,
    402                                                     int16_t RScale) {
    403   return getDifference(LDigits, LScale, RDigits, RScale);
    404 }
    405 
    406 /// \brief Convenience helper for 64-bit difference.
    407 inline std::pair<uint64_t, int16_t> getDifference64(uint64_t LDigits,
    408                                                     int16_t LScale,
    409                                                     uint64_t RDigits,
    410                                                     int16_t RScale) {
    411   return getDifference(LDigits, LScale, RDigits, RScale);
    412 }
    413 
    414 } // end namespace ScaledNumbers
    415 } // end namespace llvm
    416 
    417 namespace llvm {
    418 
    419 class raw_ostream;
    420 class ScaledNumberBase {
    421 public:
    422   static const int DefaultPrecision = 10;
    423 
    424   static void dump(uint64_t D, int16_t E, int Width);
    425   static raw_ostream &print(raw_ostream &OS, uint64_t D, int16_t E, int Width,
    426                             unsigned Precision);
    427   static std::string toString(uint64_t D, int16_t E, int Width,
    428                               unsigned Precision);
    429   static int countLeadingZeros32(uint32_t N) { return countLeadingZeros(N); }
    430   static int countLeadingZeros64(uint64_t N) { return countLeadingZeros(N); }
    431   static uint64_t getHalf(uint64_t N) { return (N >> 1) + (N & 1); }
    432 
    433   static std::pair<uint64_t, bool> splitSigned(int64_t N) {
    434     if (N >= 0)
    435       return std::make_pair(N, false);
    436     uint64_t Unsigned = N == INT64_MIN ? UINT64_C(1) << 63 : uint64_t(-N);
    437     return std::make_pair(Unsigned, true);
    438   }
    439   static int64_t joinSigned(uint64_t U, bool IsNeg) {
    440     if (U > uint64_t(INT64_MAX))
    441       return IsNeg ? INT64_MIN : INT64_MAX;
    442     return IsNeg ? -int64_t(U) : int64_t(U);
    443   }
    444 };
    445 
    446 /// \brief Simple representation of a scaled number.
    447 ///
    448 /// ScaledNumber is a number represented by digits and a scale.  It uses simple
    449 /// saturation arithmetic and every operation is well-defined for every value.
    450 /// It's somewhat similar in behaviour to a soft-float, but is *not* a
    451 /// replacement for one.  If you're doing numerics, look at \a APFloat instead.
    452 /// Nevertheless, we've found these semantics useful for modelling certain cost
    453 /// metrics.
    454 ///
    455 /// The number is split into a signed scale and unsigned digits.  The number
    456 /// represented is \c getDigits()*2^getScale().  In this way, the digits are
    457 /// much like the mantissa in the x87 long double, but there is no canonical
    458 /// form so the same number can be represented by many bit representations.
    459 ///
    460 /// ScaledNumber is templated on the underlying integer type for digits, which
    461 /// is expected to be unsigned.
    462 ///
    463 /// Unlike APFloat, ScaledNumber does not model architecture floating point
    464 /// behaviour -- while this might make it a little faster and easier to reason
    465 /// about, it certainly makes it more dangerous for general numerics.
    466 ///
    467 /// ScaledNumber is totally ordered.  However, there is no canonical form, so
    468 /// there are multiple representations of most scalars.  E.g.:
    469 ///
    470 ///     ScaledNumber(8u, 0) == ScaledNumber(4u, 1)
    471 ///     ScaledNumber(4u, 1) == ScaledNumber(2u, 2)
    472 ///     ScaledNumber(2u, 2) == ScaledNumber(1u, 3)
    473 ///
    474 /// ScaledNumber implements most arithmetic operations.  Precision is kept
    475 /// where possible.  Uses simple saturation arithmetic, so that operations
    476 /// saturate to 0.0 or getLargest() rather than under or overflowing.  It has
    477 /// some extra arithmetic for unit inversion.  0.0/0.0 is defined to be 0.0.
    478 /// Any other division by 0.0 is defined to be getLargest().
    479 ///
    480 /// As a convenience for modifying the exponent, left and right shifting are
    481 /// both implemented, and both interpret negative shifts as positive shifts in
    482 /// the opposite direction.
    483 ///
    484 /// Scales are limited to the range accepted by x87 long double.  This makes
    485 /// it trivial to add functionality to convert to APFloat (this is already
    486 /// relied on for the implementation of printing).
    487 ///
    488 /// Possible (and conflicting) future directions:
    489 ///
    490 ///  1. Turn this into a wrapper around \a APFloat.
    491 ///  2. Share the algorithm implementations with \a APFloat.
    492 ///  3. Allow \a ScaledNumber to represent a signed number.
    493 template <class DigitsT> class ScaledNumber : ScaledNumberBase {
    494 public:
    495   static_assert(!std::numeric_limits<DigitsT>::is_signed,
    496                 "only unsigned floats supported");
    497 
    498   typedef DigitsT DigitsType;
    499 
    500 private:
    501   typedef std::numeric_limits<DigitsType> DigitsLimits;
    502 
    503   static const int Width = sizeof(DigitsType) * 8;
    504   static_assert(Width <= 64, "invalid integer width for digits");
    505 
    506 private:
    507   DigitsType Digits;
    508   int16_t Scale;
    509 
    510 public:
    511   ScaledNumber() : Digits(0), Scale(0) {}
    512 
    513   ScaledNumber(DigitsType Digits, int16_t Scale)
    514       : Digits(Digits), Scale(Scale) {}
    515 
    516 private:
    517   ScaledNumber(const std::pair<DigitsT, int16_t> &X)
    518       : Digits(X.first), Scale(X.second) {}
    519 
    520 public:
    521   static ScaledNumber getZero() { return ScaledNumber(0, 0); }
    522   static ScaledNumber getOne() { return ScaledNumber(1, 0); }
    523   static ScaledNumber getLargest() {
    524     return ScaledNumber(DigitsLimits::max(), ScaledNumbers::MaxScale);
    525   }
    526   static ScaledNumber get(uint64_t N) { return adjustToWidth(N, 0); }
    527   static ScaledNumber getInverse(uint64_t N) {
    528     return get(N).invert();
    529   }
    530   static ScaledNumber getFraction(DigitsType N, DigitsType D) {
    531     return getQuotient(N, D);
    532   }
    533 
    534   int16_t getScale() const { return Scale; }
    535   DigitsType getDigits() const { return Digits; }
    536 
    537   /// \brief Convert to the given integer type.
    538   ///
    539   /// Convert to \c IntT using simple saturating arithmetic, truncating if
    540   /// necessary.
    541   template <class IntT> IntT toInt() const;
    542 
    543   bool isZero() const { return !Digits; }
    544   bool isLargest() const { return *this == getLargest(); }
    545   bool isOne() const {
    546     if (Scale > 0 || Scale <= -Width)
    547       return false;
    548     return Digits == DigitsType(1) << -Scale;
    549   }
    550 
    551   /// \brief The log base 2, rounded.
    552   ///
    553   /// Get the lg of the scalar.  lg 0 is defined to be INT32_MIN.
    554   int32_t lg() const { return ScaledNumbers::getLg(Digits, Scale); }
    555 
    556   /// \brief The log base 2, rounded towards INT32_MIN.
    557   ///
    558   /// Get the lg floor.  lg 0 is defined to be INT32_MIN.
    559   int32_t lgFloor() const { return ScaledNumbers::getLgFloor(Digits, Scale); }
    560 
    561   /// \brief The log base 2, rounded towards INT32_MAX.
    562   ///
    563   /// Get the lg ceiling.  lg 0 is defined to be INT32_MIN.
    564   int32_t lgCeiling() const {
    565     return ScaledNumbers::getLgCeiling(Digits, Scale);
    566   }
    567 
    568   bool operator==(const ScaledNumber &X) const { return compare(X) == 0; }
    569   bool operator<(const ScaledNumber &X) const { return compare(X) < 0; }
    570   bool operator!=(const ScaledNumber &X) const { return compare(X) != 0; }
    571   bool operator>(const ScaledNumber &X) const { return compare(X) > 0; }
    572   bool operator<=(const ScaledNumber &X) const { return compare(X) <= 0; }
    573   bool operator>=(const ScaledNumber &X) const { return compare(X) >= 0; }
    574 
    575   bool operator!() const { return isZero(); }
    576 
    577   /// \brief Convert to a decimal representation in a string.
    578   ///
    579   /// Convert to a string.  Uses scientific notation for very large/small
    580   /// numbers.  Scientific notation is used roughly for numbers outside of the
    581   /// range 2^-64 through 2^64.
    582   ///
    583   /// \c Precision indicates the number of decimal digits of precision to use;
    584   /// 0 requests the maximum available.
    585   ///
    586   /// As a special case to make debugging easier, if the number is small enough
    587   /// to convert without scientific notation and has more than \c Precision
    588   /// digits before the decimal place, it's printed accurately to the first
    589   /// digit past zero.  E.g., assuming 10 digits of precision:
    590   ///
    591   ///     98765432198.7654... => 98765432198.8
    592   ///      8765432198.7654... =>  8765432198.8
    593   ///       765432198.7654... =>   765432198.8
    594   ///        65432198.7654... =>    65432198.77
    595   ///         5432198.7654... =>     5432198.765
    596   std::string toString(unsigned Precision = DefaultPrecision) {
    597     return ScaledNumberBase::toString(Digits, Scale, Width, Precision);
    598   }
    599 
    600   /// \brief Print a decimal representation.
    601   ///
    602   /// Print a string.  See toString for documentation.
    603   raw_ostream &print(raw_ostream &OS,
    604                      unsigned Precision = DefaultPrecision) const {
    605     return ScaledNumberBase::print(OS, Digits, Scale, Width, Precision);
    606   }
    607   void dump() const { return ScaledNumberBase::dump(Digits, Scale, Width); }
    608 
    609   ScaledNumber &operator+=(const ScaledNumber &X) {
    610     std::tie(Digits, Scale) =
    611         ScaledNumbers::getSum(Digits, Scale, X.Digits, X.Scale);
    612     // Check for exponent past MaxScale.
    613     if (Scale > ScaledNumbers::MaxScale)
    614       *this = getLargest();
    615     return *this;
    616   }
    617   ScaledNumber &operator-=(const ScaledNumber &X) {
    618     std::tie(Digits, Scale) =
    619         ScaledNumbers::getDifference(Digits, Scale, X.Digits, X.Scale);
    620     return *this;
    621   }
    622   ScaledNumber &operator*=(const ScaledNumber &X);
    623   ScaledNumber &operator/=(const ScaledNumber &X);
    624   ScaledNumber &operator<<=(int16_t Shift) {
    625     shiftLeft(Shift);
    626     return *this;
    627   }
    628   ScaledNumber &operator>>=(int16_t Shift) {
    629     shiftRight(Shift);
    630     return *this;
    631   }
    632 
    633 private:
    634   void shiftLeft(int32_t Shift);
    635   void shiftRight(int32_t Shift);
    636 
    637   /// \brief Adjust two floats to have matching exponents.
    638   ///
    639   /// Adjust \c this and \c X to have matching exponents.  Returns the new \c X
    640   /// by value.  Does nothing if \a isZero() for either.
    641   ///
    642   /// The value that compares smaller will lose precision, and possibly become
    643   /// \a isZero().
    644   ScaledNumber matchScales(ScaledNumber X) {
    645     ScaledNumbers::matchScales(Digits, Scale, X.Digits, X.Scale);
    646     return X;
    647   }
    648 
    649 public:
    650   /// \brief Scale a large number accurately.
    651   ///
    652   /// Scale N (multiply it by this).  Uses full precision multiplication, even
    653   /// if Width is smaller than 64, so information is not lost.
    654   uint64_t scale(uint64_t N) const;
    655   uint64_t scaleByInverse(uint64_t N) const {
    656     // TODO: implement directly, rather than relying on inverse.  Inverse is
    657     // expensive.
    658     return inverse().scale(N);
    659   }
    660   int64_t scale(int64_t N) const {
    661     std::pair<uint64_t, bool> Unsigned = splitSigned(N);
    662     return joinSigned(scale(Unsigned.first), Unsigned.second);
    663   }
    664   int64_t scaleByInverse(int64_t N) const {
    665     std::pair<uint64_t, bool> Unsigned = splitSigned(N);
    666     return joinSigned(scaleByInverse(Unsigned.first), Unsigned.second);
    667   }
    668 
    669   int compare(const ScaledNumber &X) const {
    670     return ScaledNumbers::compare(Digits, Scale, X.Digits, X.Scale);
    671   }
    672   int compareTo(uint64_t N) const {
    673     return ScaledNumbers::compare<uint64_t>(Digits, Scale, N, 0);
    674   }
    675   int compareTo(int64_t N) const { return N < 0 ? 1 : compareTo(uint64_t(N)); }
    676 
    677   ScaledNumber &invert() { return *this = ScaledNumber::get(1) / *this; }
    678   ScaledNumber inverse() const { return ScaledNumber(*this).invert(); }
    679 
    680 private:
    681   static ScaledNumber getProduct(DigitsType LHS, DigitsType RHS) {
    682     return ScaledNumbers::getProduct(LHS, RHS);
    683   }
    684   static ScaledNumber getQuotient(DigitsType Dividend, DigitsType Divisor) {
    685     return ScaledNumbers::getQuotient(Dividend, Divisor);
    686   }
    687 
    688   static int countLeadingZerosWidth(DigitsType Digits) {
    689     if (Width == 64)
    690       return countLeadingZeros64(Digits);
    691     if (Width == 32)
    692       return countLeadingZeros32(Digits);
    693     return countLeadingZeros32(Digits) + Width - 32;
    694   }
    695 
    696   /// \brief Adjust a number to width, rounding up if necessary.
    697   ///
    698   /// Should only be called for \c Shift close to zero.
    699   ///
    700   /// \pre Shift >= MinScale && Shift + 64 <= MaxScale.
    701   static ScaledNumber adjustToWidth(uint64_t N, int32_t Shift) {
    702     assert(Shift >= ScaledNumbers::MinScale && "Shift should be close to 0");
    703     assert(Shift <= ScaledNumbers::MaxScale - 64 &&
    704            "Shift should be close to 0");
    705     auto Adjusted = ScaledNumbers::getAdjusted<DigitsT>(N, Shift);
    706     return Adjusted;
    707   }
    708 
    709   static ScaledNumber getRounded(ScaledNumber P, bool Round) {
    710     // Saturate.
    711     if (P.isLargest())
    712       return P;
    713 
    714     return ScaledNumbers::getRounded(P.Digits, P.Scale, Round);
    715   }
    716 };
    717 
    718 #define SCALED_NUMBER_BOP(op, base)                                            \
    719   template <class DigitsT>                                                     \
    720   ScaledNumber<DigitsT> operator op(const ScaledNumber<DigitsT> &L,            \
    721                                     const ScaledNumber<DigitsT> &R) {          \
    722     return ScaledNumber<DigitsT>(L) base R;                                    \
    723   }
    724 SCALED_NUMBER_BOP(+, += )
    725 SCALED_NUMBER_BOP(-, -= )
    726 SCALED_NUMBER_BOP(*, *= )
    727 SCALED_NUMBER_BOP(/, /= )
    728 #undef SCALED_NUMBER_BOP
    729 
    730 template <class DigitsT>
    731 ScaledNumber<DigitsT> operator<<(const ScaledNumber<DigitsT> &L,
    732                                  int16_t Shift) {
    733   return ScaledNumber<DigitsT>(L) <<= Shift;
    734 }
    735 
    736 template <class DigitsT>
    737 ScaledNumber<DigitsT> operator>>(const ScaledNumber<DigitsT> &L,
    738                                  int16_t Shift) {
    739   return ScaledNumber<DigitsT>(L) >>= Shift;
    740 }
    741 
    742 template <class DigitsT>
    743 raw_ostream &operator<<(raw_ostream &OS, const ScaledNumber<DigitsT> &X) {
    744   return X.print(OS, 10);
    745 }
    746 
    747 #define SCALED_NUMBER_COMPARE_TO_TYPE(op, T1, T2)                              \
    748   template <class DigitsT>                                                     \
    749   bool operator op(const ScaledNumber<DigitsT> &L, T1 R) {                     \
    750     return L.compareTo(T2(R)) op 0;                                            \
    751   }                                                                            \
    752   template <class DigitsT>                                                     \
    753   bool operator op(T1 L, const ScaledNumber<DigitsT> &R) {                     \
    754     return 0 op R.compareTo(T2(L));                                            \
    755   }
    756 #define SCALED_NUMBER_COMPARE_TO(op)                                           \
    757   SCALED_NUMBER_COMPARE_TO_TYPE(op, uint64_t, uint64_t)                        \
    758   SCALED_NUMBER_COMPARE_TO_TYPE(op, uint32_t, uint64_t)                        \
    759   SCALED_NUMBER_COMPARE_TO_TYPE(op, int64_t, int64_t)                          \
    760   SCALED_NUMBER_COMPARE_TO_TYPE(op, int32_t, int64_t)
    761 SCALED_NUMBER_COMPARE_TO(< )
    762 SCALED_NUMBER_COMPARE_TO(> )
    763 SCALED_NUMBER_COMPARE_TO(== )
    764 SCALED_NUMBER_COMPARE_TO(!= )
    765 SCALED_NUMBER_COMPARE_TO(<= )
    766 SCALED_NUMBER_COMPARE_TO(>= )
    767 #undef SCALED_NUMBER_COMPARE_TO
    768 #undef SCALED_NUMBER_COMPARE_TO_TYPE
    769 
    770 template <class DigitsT>
    771 uint64_t ScaledNumber<DigitsT>::scale(uint64_t N) const {
    772   if (Width == 64 || N <= DigitsLimits::max())
    773     return (get(N) * *this).template toInt<uint64_t>();
    774 
    775   // Defer to the 64-bit version.
    776   return ScaledNumber<uint64_t>(Digits, Scale).scale(N);
    777 }
    778 
    779 template <class DigitsT>
    780 template <class IntT>
    781 IntT ScaledNumber<DigitsT>::toInt() const {
    782   typedef std::numeric_limits<IntT> Limits;
    783   if (*this < 1)
    784     return 0;
    785   if (*this >= Limits::max())
    786     return Limits::max();
    787 
    788   IntT N = Digits;
    789   if (Scale > 0) {
    790     assert(size_t(Scale) < sizeof(IntT) * 8);
    791     return N << Scale;
    792   }
    793   if (Scale < 0) {
    794     assert(size_t(-Scale) < sizeof(IntT) * 8);
    795     return N >> -Scale;
    796   }
    797   return N;
    798 }
    799 
    800 template <class DigitsT>
    801 ScaledNumber<DigitsT> &ScaledNumber<DigitsT>::
    802 operator*=(const ScaledNumber &X) {
    803   if (isZero())
    804     return *this;
    805   if (X.isZero())
    806     return *this = X;
    807 
    808   // Save the exponents.
    809   int32_t Scales = int32_t(Scale) + int32_t(X.Scale);
    810 
    811   // Get the raw product.
    812   *this = getProduct(Digits, X.Digits);
    813 
    814   // Combine with exponents.
    815   return *this <<= Scales;
    816 }
    817 template <class DigitsT>
    818 ScaledNumber<DigitsT> &ScaledNumber<DigitsT>::
    819 operator/=(const ScaledNumber &X) {
    820   if (isZero())
    821     return *this;
    822   if (X.isZero())
    823     return *this = getLargest();
    824 
    825   // Save the exponents.
    826   int32_t Scales = int32_t(Scale) - int32_t(X.Scale);
    827 
    828   // Get the raw quotient.
    829   *this = getQuotient(Digits, X.Digits);
    830 
    831   // Combine with exponents.
    832   return *this <<= Scales;
    833 }
    834 template <class DigitsT> void ScaledNumber<DigitsT>::shiftLeft(int32_t Shift) {
    835   if (!Shift || isZero())
    836     return;
    837   assert(Shift != INT32_MIN);
    838   if (Shift < 0) {
    839     shiftRight(-Shift);
    840     return;
    841   }
    842 
    843   // Shift as much as we can in the exponent.
    844   int32_t ScaleShift = std::min(Shift, ScaledNumbers::MaxScale - Scale);
    845   Scale += ScaleShift;
    846   if (ScaleShift == Shift)
    847     return;
    848 
    849   // Check this late, since it's rare.
    850   if (isLargest())
    851     return;
    852 
    853   // Shift the digits themselves.
    854   Shift -= ScaleShift;
    855   if (Shift > countLeadingZerosWidth(Digits)) {
    856     // Saturate.
    857     *this = getLargest();
    858     return;
    859   }
    860 
    861   Digits <<= Shift;
    862   return;
    863 }
    864 
    865 template <class DigitsT> void ScaledNumber<DigitsT>::shiftRight(int32_t Shift) {
    866   if (!Shift || isZero())
    867     return;
    868   assert(Shift != INT32_MIN);
    869   if (Shift < 0) {
    870     shiftLeft(-Shift);
    871     return;
    872   }
    873 
    874   // Shift as much as we can in the exponent.
    875   int32_t ScaleShift = std::min(Shift, Scale - ScaledNumbers::MinScale);
    876   Scale -= ScaleShift;
    877   if (ScaleShift == Shift)
    878     return;
    879 
    880   // Shift the digits themselves.
    881   Shift -= ScaleShift;
    882   if (Shift >= Width) {
    883     // Saturate.
    884     *this = getZero();
    885     return;
    886   }
    887 
    888   Digits >>= Shift;
    889   return;
    890 }
    891 
    892 template <typename T> struct isPodLike;
    893 template <typename T> struct isPodLike<ScaledNumber<T>> {
    894   static const bool value = true;
    895 };
    896 
    897 } // end namespace llvm
    898 
    899 #endif
    900