Yi Kong | e5b9f24 | 2023-04-26 13:35:57 +0900 | [diff] [blame^] | 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 |