LCOV - code coverage report
Current view: top level - include/llvm/Support - ScaledNumber.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 334 446 74.9 %
Date: 2018-10-20 13:21:21 Functions: 26 45 57.8 %
Legend: Lines: hit not hit

          Line data    Source code
       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             : /// Maximum scale; same as APFloat for easy debug printing.
      37             : const int32_t MaxScale = 16383;
      38             : 
      39             : /// Maximum scale; same as APFloat for easy debug printing.
      40             : const int32_t MinScale = -16382;
      41             : 
      42             : /// Get the width of a number.
      43             : template <class DigitsT> inline int getWidth() { return sizeof(DigitsT) * 8; }
      44             : 
      45             : /// 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      204368 :   if (ShouldRound)
      58     1228211 :     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             : /// 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             : /// 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             : /// 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          37 : 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          37 :   if (Width == 64 || Digits <= std::numeric_limits<DigitsT>::max())
      86          14 :     return std::make_pair(Digits, Scale);
      87             : 
      88             :   // Shift right and round.
      89          23 :   int Shift = 64 - Width - countLeadingZeros(Digits);
      90          23 :   return getRounded<DigitsT>(Digits >> Shift, Scale + Shift,
      91          23 :                              Digits & (UINT64_C(1) << (Shift - 1)));
      92             : }
      93             : 
      94             : /// 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           9 :   return getAdjusted<uint32_t>(Digits, Scale);
      98             : }
      99             : 
     100             : /// 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             : /// 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             : /// 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     4102737 : inline std::pair<DigitsT, int16_t> getProduct(DigitsT LHS, DigitsT RHS) {
     116             :   static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
     117             : 
     118     4102737 :   if (getWidth<DigitsT>() <= 32 || (LHS <= UINT32_MAX && RHS <= UINT32_MAX))
     119     1337183 :     return getAdjusted<DigitsT>(uint64_t(LHS) * RHS);
     120             : 
     121     2765568 :   return multiply64(LHS, RHS);
     122             : }
     123             : 
     124             : /// 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             : /// Convenience helper for 64-bit product.
     130             : inline std::pair<uint64_t, int16_t> getProduct64(uint64_t LHS, uint64_t RHS) {
     131           2 :   return getProduct(LHS, RHS);
     132             : }
     133             : 
     134             : /// 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             : /// 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             : /// 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     2698461 : 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     2698461 :   if (!Dividend)
     161           6 :     return std::make_pair(0, 0);
     162     2698455 :   if (!Divisor)
     163           4 :     return std::make_pair(std::numeric_limits<DigitsT>::max(), MaxScale);
     164             : 
     165             :   if (getWidth<DigitsT>() == 64)
     166     2698440 :     return divide64(Dividend, Divisor);
     167          11 :   return divide32(Dividend, Divisor);
     168             : }
     169          16 : 
     170             : /// 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          16 : 
     176           3 : /// Convenience helper for 64-bit quotient.
     177          13 : inline std::pair<uint64_t, int16_t> getQuotient64(uint64_t Dividend,
     178           2 :                                                   uint64_t Divisor) {
     179             :   return getQuotient(Dividend, Divisor);
     180             : }
     181          11 : 
     182             : /// Implementation of getLg() and friends.
     183             : ///
     184          16 : /// 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    27908410 : inline std::pair<int32_t, int> getLgImpl(DigitsT Digits, int16_t Scale) {
     190          16 :   static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
     191           3 : 
     192    27908423 :   if (!Digits)
     193           2 :     return std::make_pair(INT32_MIN, 0);
     194             : 
     195             :   // Get the floor of the lg of Digits.
     196    27908410 :   int32_t LocalFloor = sizeof(Digits) * 8 - countLeadingZeros(Digits) - 1;
     197          11 : 
     198             :   // Get the actual floor.
     199    27908410 :   int32_t Floor = Scale + LocalFloor;
     200    27908410 :   if (Digits == UINT64_C(1) << LocalFloor)
     201             :     return std::make_pair(Floor, 0);
     202             : 
     203          15 :   // Round based on the next digit.
     204             :   assert(LocalFloor >= 1);
     205    16587013 :   bool Round = Digits & UINT64_C(1) << (LocalFloor - 1);
     206    22239926 :   return std::make_pair(Floor + Round, Round ? 1 : -1);
     207             : }
     208             : 
     209          14 : /// 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     1314189 :   return getLgImpl(Digits, Scale).first;
     216             : }
     217             : 
     218             : /// Get the lg floor of a scaled number.
     219         180 : ///
     220             : /// Get the floor of the lg of \c Digits*2^Scale.
     221             : ///
     222         180 : /// Returns \c INT32_MIN when \c Digits is zero.
     223          18 : template <class DigitsT> int32_t getLgFloor(DigitsT Digits, int16_t Scale) {
     224    26594220 :   auto Lg = getLgImpl(Digits, Scale);
     225    26594220 :   return Lg.first - (Lg.second > 0);
     226         162 : }
     227             : 
     228             : /// Get the lg ceiling of a scaled number.
     229         162 : ///
     230         162 : /// 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          46 :   return Lg.first + (Lg.second < 0);
     236          70 : }
     237             : 
     238          93 : /// Implementation for comparing scaled numbers.
     239             : ///
     240             : /// Compare two 64-bit numbers with different scales.  Given that the scale of
     241          93 : /// \c L is higher than that of \c R by \c ScaleDiff, compare them.  Return -1,
     242           9 : /// 1, and 0 for less than, greater than, and equal, respectively.
     243             : ///
     244             : /// \pre 0 <= ScaleDiff < 64.
     245          84 : int compareImpl(uint64_t L, uint64_t R, int ScaleDiff);
     246             : 
     247             : /// Compare two scaled numbers.
     248          84 : ///
     249          84 : /// Compare two scaled numbers.  Returns 0 for equal, -1 for less than, and 1
     250             : /// for greater than.
     251             : template <class DigitsT>
     252    14611300 : int compare(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale) {
     253             :   static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
     254          24 : 
     255          36 :   // Check for zero.
     256    14611300 :   if (!LDigits)
     257     1314277 :     return RDigits ? -1 : 0;
     258    13297110 :   if (!RDigits)
     259             :     return 1;
     260          87 : 
     261           9 :   // Check for the scale.  Use getLgFloor to be sure that the scale difference
     262             :   // is always lower than 64.
     263    13297110 :   int32_t lgL = getLgFloor(LDigits, LScale), lgR = getLgFloor(RDigits, RScale);
     264    13297188 :   if (lgL != lgR)
     265    20634555 :     return lgL < lgR ? -1 : 1;
     266             : 
     267          78 :   // Compare digits.
     268      354860 :   if (LScale < RScale)
     269       14188 :     return compareImpl(LDigits, RDigits, RScale - LScale);
     270             : 
     271      340594 :   return -compareImpl(RDigits, LDigits, LScale - RScale);
     272             : }
     273          22 : 
     274          34 : /// 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          30 : /// 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          26 :     // Swap arguments.
     293          26 :     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          26 :     // Don't bother shifting.  RDigits will get zero-ed out anyway.
     303          26 :     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          45 : 
     321             :   LScale -= ShiftL;
     322             :   RScale += ShiftR;
     323             :   assert(LScale == RScale && "scales should match");
     324          45 :   return LScale;
     325           0 : }
     326          45 : 
     327             : /// Get the sum of two scaled numbers.
     328             : ///
     329             : /// Get the sum of two scaled numbers with as much precision as possible.
     330             : ///
     331          45 : /// \pre Adding 1 to \c LScale (or \c RScale) will not overflow INT16_MAX.
     332          45 : template <class DigitsT>
     333           6 : 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          39 : 
     337          22 :   // Check inputs up front.  This is only relevant if addition overflows, but
     338             :   // testing here should catch more bugs.
     339          17 :   assert(LScale < INT16_MAX && "scale too large");
     340             :   assert(RScale < INT16_MAX && "scale too large");
     341          24 : 
     342             :   // Normalize digits to match scales.
     343             :   int16_t Scale = matchScales(LDigits, LScale, RDigits, RScale);
     344             : 
     345          24 :   // Compute sum.
     346           0 :   DigitsT Sum = LDigits + RDigits;
     347          24 :   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          24 :   return std::make_pair(HighBit | Sum >> 1, Scale + 1);
     353          24 : }
     354           4 : 
     355             : /// Convenience helper for 32-bit sum.
     356             : inline std::pair<uint32_t, int16_t> getSum32(uint32_t LDigits, int16_t LScale,
     357          20 :                                              uint32_t RDigits, int16_t RScale) {
     358          11 :   return getSum(LDigits, LScale, RDigits, RScale);
     359             : }
     360           9 : 
     361             : /// Convenience helper for 64-bit sum.
     362          21 : 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          21 : 
     367           0 : /// Get the difference of two scaled numbers.
     368          21 : ///
     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          21 : std::pair<DigitsT, int16_t> getDifference(DigitsT LDigits, int16_t LScale,
     374          21 :                                           DigitsT RDigits, int16_t RScale) {
     375           2 :   static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
     376             : 
     377             :   // Normalize digits to match scales.
     378          19 :   const DigitsT SavedRDigits = RDigits;
     379          11 :   const int16_t SavedRScale = RScale;
     380             :   matchScales(LDigits, LScale, RDigits, RScale);
     381           8 : 
     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         129 : 
     398             : /// Convenience helper for 32-bit difference.
     399             : inline std::pair<uint32_t, int16_t> getDifference32(uint32_t LDigits,
     400             :                                                     int16_t LScale,
     401         171 :                                                     uint32_t RDigits,
     402             :                                                     int16_t RScale) {
     403             :   return getDifference(LDigits, LScale, RDigits, RScale);
     404         129 : }
     405             : 
     406         107 : /// 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          77 :                                                     int16_t RScale) {
     411          77 :   return getDifference(LDigits, LScale, RDigits, RScale);
     412             : }
     413           0 : 
     414           0 : } // end namespace ScaledNumbers
     415             : } // end namespace llvm
     416             : 
     417             : namespace llvm {
     418          77 : 
     419             : class raw_ostream;
     420             : class ScaledNumberBase {
     421          77 : public:
     422          77 :   static const int DefaultPrecision = 10;
     423             : 
     424           0 :   static void dump(uint64_t D, int16_t E, int Width);
     425           0 :   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          77 :                               unsigned Precision);
     429          77 :   static int countLeadingZeros32(uint32_t N) { return countLeadingZeros(N); }
     430           0 :   static int countLeadingZeros64(uint64_t N) { return countLeadingZeros(N); }
     431          77 :   static uint64_t getHalf(uint64_t N) { return (N >> 1) + (N & 1); }
     432          77 : 
     433             :   static std::pair<uint64_t, bool> splitSigned(int64_t N) {
     434          77 :     if (N >= 0)
     435             :       return std::make_pair(N, false);
     436          64 :     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          85 :     if (U > uint64_t(INT64_MAX))
     441             :       return IsNeg ? INT64_MIN : INT64_MAX;
     442             :     return IsNeg ? -int64_t(U) : int64_t(U);
     443          64 :   }
     444             : };
     445          53 : 
     446             : /// Simple representation of a scaled number.
     447             : ///
     448             : /// ScaledNumber is a number represented by digits and a scale.  It uses simple
     449          38 : /// saturation arithmetic and every operation is well-defined for every value.
     450          38 : /// 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           0 : /// Nevertheless, we've found these semantics useful for modelling certain cost
     453           0 : /// 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          38 : /// 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          38 : /// ScaledNumber is templated on the underlying integer type for digits, which
     461          38 : /// is expected to be unsigned.
     462             : ///
     463           0 : /// Unlike APFloat, ScaledNumber does not model architecture floating point
     464           0 : /// 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          38 : /// ScaledNumber is totally ordered.  However, there is no canonical form, so
     468          38 : /// there are multiple representations of most scalars.  E.g.:
     469             : ///
     470          38 : ///     ScaledNumber(8u, 0) == ScaledNumber(4u, 1)
     471          38 : ///     ScaledNumber(4u, 1) == ScaledNumber(2u, 2)
     472             : ///     ScaledNumber(2u, 2) == ScaledNumber(1u, 3)
     473          38 : ///
     474             : /// ScaledNumber implements most arithmetic operations.  Precision is kept
     475          65 : /// 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          86 : ///
     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          65 : /// the opposite direction.
     483             : ///
     484          54 : /// 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          39 : /// Possible (and conflicting) future directions:
     489          39 : ///
     490             : ///  1. Turn this into a wrapper around \a APFloat.
     491           0 : ///  2. Share the algorithm implementations with \a APFloat.
     492           0 : ///  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          39 :                 "only unsigned floats supported");
     497             : 
     498             :   typedef DigitsT DigitsType;
     499          39 : 
     500          39 : private:
     501             :   typedef std::numeric_limits<DigitsType> DigitsLimits;
     502           0 : 
     503           0 :   static const int Width = sizeof(DigitsType) * 8;
     504             :   static_assert(Width <= 64, "invalid integer width for digits");
     505             : 
     506          39 : private:
     507          39 :   DigitsType Digits = 0;
     508             :   int16_t Scale = 0;
     509          39 : 
     510          39 : public:
     511       72153 :   ScaledNumber() = default;
     512          39 : 
     513         283 :   constexpr ScaledNumber(DigitsType Digits, int16_t Scale)
     514         283 :       : Digits(Digits), Scale(Scale) {}
     515             : 
     516             : private:
     517             :   ScaledNumber(const std::pair<DigitsT, int16_t> &X)
     518     6801165 :       : Digits(X.first), Scale(X.second) {}
     519             : 
     520             : public:
     521          52 :   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          52 :     return getQuotient(N, D);
     532             :   }
     533             : 
     534          52 :   int16_t getScale() const { return Scale; }
     535          52 :   DigitsType getDigits() const { return Digits; }
     536             : 
     537             :   /// Convert to the given integer type.
     538             :   ///
     539             :   /// Convert to \c IntT using simple saturating arithmetic, truncating if
     540           8 :   /// necessary.
     541             :   template <class IntT> IntT toInt() const;
     542          26 : 
     543           0 :   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             :   /// The log base 2, rounded.
     552          26 :   ///
     553             :   /// Get the lg of the scalar.  lg 0 is defined to be INT32_MIN.
     554           0 :   int32_t lg() const { return ScaledNumbers::getLg(Digits, Scale); }
     555          26 : 
     556          26 :   /// 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           4 :   /// The log base 2, rounded towards INT32_MAX.
     562             :   ///
     563          26 :   /// 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     7306075 :   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          26 :   bool operator>=(const ScaledNumber &X) const { return compare(X) >= 0; }
     574             : 
     575             :   bool operator!() const { return isZero(); }
     576          26 : 
     577          26 :   /// 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           4 :   ///
     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          25 :   /// 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          25 :   ///        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             :   /// Print a decimal representation.
     601             :   ///
     602             :   /// Print a string.  See toString for documentation.
     603          39 :   raw_ostream &print(raw_ostream &OS,
     604             :                      unsigned Precision = DefaultPrecision) const {
     605         532 :     return ScaledNumberBase::print(OS, Digits, Scale, Width, Precision);
     606             :   }
     607             :   void dump() const { return ScaledNumberBase::dump(Digits, Scale, Width); }
     608          39 : 
     609          39 :   ScaledNumber &operator+=(const ScaledNumber &X) {
     610          39 :     std::tie(Digits, Scale) =
     611             :         ScaledNumbers::getSum(Digits, Scale, X.Digits, X.Scale);
     612             :     // Check for exponent past MaxScale.
     613          39 :     if (Scale > ScaledNumbers::MaxScale)
     614          18 :       *this = getLargest();
     615          21 :     return *this;
     616          13 :   }
     617             :   ScaledNumber &operator-=(const ScaledNumber &X) {
     618             :     std::tie(Digits, Scale) =
     619             :         ScaledNumbers::getDifference(Digits, Scale, X.Digits, X.Scale);
     620             :     return *this;
     621           8 :   }
     622           8 :   ScaledNumber &operator*=(const ScaledNumber &X);
     623           4 :   ScaledNumber &operator/=(const ScaledNumber &X);
     624             :   ScaledNumber &operator<<=(int16_t Shift) {
     625     4010752 :     shiftLeft(Shift);
     626             :     return *this;
     627          19 :   }
     628             :   ScaledNumber &operator>>=(int16_t Shift) {
     629             :     shiftRight(Shift);
     630             :     return *this;
     631             :   }
     632          19 : 
     633          19 : private:
     634          19 :   void shiftLeft(int32_t Shift);
     635             :   void shiftRight(int32_t Shift);
     636             : 
     637          19 :   /// Adjust two floats to have matching exponents.
     638           9 :   ///
     639          10 :   /// Adjust \c this and \c X to have matching exponents.  Returns the new \c X
     640           6 :   /// 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           4 :     ScaledNumbers::matchScales(Digits, Scale, X.Digits, X.Scale);
     646           4 :     return X;
     647           2 :   }
     648             : 
     649           2 : public:
     650             :   /// Scale a large number accurately.
     651          20 :   ///
     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          20 :     // TODO: implement directly, rather than relying on inverse.  Inverse is
     657          20 :     // expensive.
     658          20 :     return inverse().scale(N);
     659             :   }
     660             :   int64_t scale(int64_t N) const {
     661          20 :     std::pair<uint64_t, bool> Unsigned = splitSigned(N);
     662           9 :     return joinSigned(scale(Unsigned.first), Unsigned.second);
     663          11 :   }
     664           7 :   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           4 :   int compare(const ScaledNumber &X) const {
     670     7306079 :     return ScaledNumbers::compare(Digits, Scale, X.Digits, X.Scale);
     671           2 :   }
     672           0 :   int compareTo(uint64_t N) const {
     673           2 :     return ScaledNumbers::compare<uint64_t>(Digits, Scale, N, 0);
     674             :   }
     675     3653321 :   int compareTo(int64_t N) const { return N < 0 ? 1 : compareTo(uint64_t(N)); }
     676             : 
     677     2764169 :   ScaledNumber &invert() { return *this = ScaledNumber::get(1) / *this; }
     678     1382084 :   ScaledNumber inverse() const { return ScaledNumber(*this).invert(); }
     679             : 
     680             : private:
     681          19 :   static ScaledNumber getProduct(DigitsType LHS, DigitsType RHS) {
     682     8205468 :     return ScaledNumbers::getProduct(LHS, RHS);
     683             :   }
     684             :   static ScaledNumber getQuotient(DigitsType Dividend, DigitsType Divisor) {
     685     5396861 :     return ScaledNumbers::getQuotient(Dividend, Divisor);
     686             :   }
     687             : 
     688             :   static int countLeadingZerosWidth(DigitsType Digits) {
     689          18 :     if (Width == 64)
     690             :       return countLeadingZeros64(Digits);
     691             :     if (Width == 32)
     692             :       return countLeadingZeros32(Digits);
     693             :     return countLeadingZeros32(Digits) + Width - 32;
     694             :   }
     695             : 
     696             :   /// 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           0 :   }
     708           0 : 
     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     4030574 : SCALED_NUMBER_BOP(*, *= )
     727     2698147 : 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           0 :   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     3651903 : 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     3653321 : IntT ScaledNumber<DigitsT>::toInt() const {
     782             :   typedef std::numeric_limits<IntT> Limits;
     783     3653321 :   if (*this < 1)
     784             :     return 0;
     785     3651903 :   if (*this >= Limits::max())
     786             :     return Limits::max();
     787             : 
     788     3649385 :   IntT N = Digits;
     789     3649385 :   if (Scale > 0) {
     790             :     assert(size_t(Scale) < sizeof(IntT) * 8);
     791     1309149 :     return N << Scale;
     792          12 :   }
     793     2340256 :   if (Scale < 0) {
     794             :     assert(size_t(-Scale) < sizeof(IntT) * 8);
     795     2308026 :     return N >> -Scale;
     796           3 :   }
     797             :   return N;
     798             : }
     799             : 
     800             : template <class DigitsT>
     801     4102734 : ScaledNumber<DigitsT> &ScaledNumber<DigitsT>::
     802             : operator*=(const ScaledNumber &X) {
     803     4102734 :   if (isZero())
     804             :     return *this;
     805     4102734 :   if (X.isZero())
     806           0 :     return *this = X;
     807             : 
     808             :   // Save the exponents.
     809     4102734 :   int32_t Scales = int32_t(Scale) + int32_t(X.Scale);
     810             : 
     811             :   // Get the raw product.
     812     4102734 :   *this = getProduct(Digits, X.Digits);
     813             : 
     814             :   // Combine with exponents.
     815     4102734 :   return *this <<= Scales;
     816             : }
     817             : template <class DigitsT>
     818     2698430 : ScaledNumber<DigitsT> &ScaledNumber<DigitsT>::
     819             : operator/=(const ScaledNumber &X) {
     820     2698430 :   if (isZero())
     821           0 :     return *this;
     822     2698430 :   if (X.isZero())
     823           0 :     return *this = getLargest();
     824             : 
     825             :   // Save the exponents.
     826     2698430 :   int32_t Scales = int32_t(Scale) - int32_t(X.Scale);
     827             : 
     828             :   // Get the raw quotient.
     829     2698431 :   *this = getQuotient(Digits, X.Digits);
     830             : 
     831             :   // Combine with exponents.
     832     2698431 :   return *this <<= Scales;
     833             : }
     834     8113481 : template <class DigitsT> void ScaledNumber<DigitsT>::shiftLeft(int32_t Shift) {
     835     8113481 :   if (!Shift || isZero())
     836             :     return;
     837             :   assert(Shift != INT32_MIN);
     838     5707158 :   if (Shift < 0) {
     839     2777437 :     shiftRight(-Shift);
     840     2777437 :     return;
     841             :   }
     842             : 
     843             :   // Shift as much as we can in the exponent.
     844     2929721 :   int32_t ScaleShift = std::min(Shift, ScaledNumbers::MaxScale - Scale);
     845     2929721 :   Scale += ScaleShift;
     846     2929733 :   if (ScaleShift == Shift)
     847             :     return;
     848             : 
     849             :   // Check this late, since it's rare.
     850           0 :   if (isLargest())
     851             :     return;
     852             : 
     853             :   // Shift the digits themselves.
     854           0 :   Shift -= ScaleShift;
     855           0 :   if (Shift > countLeadingZerosWidth(Digits)) {
     856             :     // Saturate.
     857           0 :     *this = getLargest();
     858           0 :     return;
     859             :   }
     860             : 
     861           0 :   Digits <<= Shift;
     862             : }
     863             : 
     864     2777437 : template <class DigitsT> void ScaledNumber<DigitsT>::shiftRight(int32_t Shift) {
     865     2777437 :   if (!Shift || isZero())
     866             :     return;
     867             :   assert(Shift != INT32_MIN);
     868     2777437 :   if (Shift < 0) {
     869           0 :     shiftLeft(-Shift);
     870           0 :     return;
     871             :   }
     872             : 
     873             :   // Shift as much as we can in the exponent.
     874     2777437 :   int32_t ScaleShift = std::min(Shift, Scale - ScaledNumbers::MinScale);
     875     2777437 :   Scale -= ScaleShift;
     876     2777437 :   if (ScaleShift == Shift)
     877             :     return;
     878             : 
     879             :   // Shift the digits themselves.
     880           0 :   Shift -= ScaleShift;
     881           0 :   if (Shift >= Width) {
     882             :     // Saturate.
     883           0 :     *this = getZero();
     884           0 :     return;
     885             :   }
     886             : 
     887           0 :   Digits >>= Shift;
     888           0 : }
     889           0 : 
     890             : template <typename T> struct isPodLike;
     891           0 : template <typename T> struct isPodLike<ScaledNumber<T>> {
     892           0 :   static const bool value = true;
     893           0 : };
     894             : 
     895           0 : } // end namespace llvm
     896           0 : 
     897           0 : #endif // LLVM_SUPPORT_SCALEDNUMBER_H

Generated by: LCOV version 1.13