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