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 #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