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 constexpr 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 constexpr 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 893