contrib/llvm/include/llvm/Support/ScaledNumber.h

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