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