include/llvm/Support/ScaledNumber.h

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