LLVM  8.0.1
ScaledNumber.h
Go to the documentation of this file.
1 //===- llvm/Support/ScaledNumber.h - Support for scaled numbers -*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file contains functions (and a class) useful for working with scaled
11 // numbers -- in particular, pairs of integers where one represents digits and
12 // another represents a scale. The functions are helpers and live in the
13 // namespace ScaledNumbers. The class ScaledNumber is useful for modelling
14 // certain cost metrics that need simple, integer-like semantics that are easy
15 // to reason about.
16 //
17 // These might remind you of soft-floats. If you want one of those, you're in
18 // the wrong place. Look at include/llvm/ADT/APFloat.h instead.
19 //
20 //===----------------------------------------------------------------------===//
21 
22 #ifndef LLVM_SUPPORT_SCALEDNUMBER_H
23 #define LLVM_SUPPORT_SCALEDNUMBER_H
24 
26 #include <algorithm>
27 #include <cstdint>
28 #include <limits>
29 #include <string>
30 #include <tuple>
31 #include <utility>
32 
33 namespace llvm {
34 namespace ScaledNumbers {
35 
36 /// Maximum scale; same as APFloat for easy debug printing.
37 const int32_t MaxScale = 16383;
38 
39 /// Maximum scale; same as APFloat for easy debug printing.
40 const int32_t MinScale = -16382;
41 
42 /// Get the width of a number.
43 template <class DigitsT> inline int getWidth() { return sizeof(DigitsT) * 8; }
44 
45 /// Conditionally round up a scaled number.
46 ///
47 /// Given \c Digits and \c Scale, round up iff \c ShouldRound is \c true.
48 /// Always returns \c Scale unless there's an overflow, in which case it
49 /// returns \c 1+Scale.
50 ///
51 /// \pre adding 1 to \c Scale will not overflow INT16_MAX.
52 template <class DigitsT>
53 inline std::pair<DigitsT, int16_t> getRounded(DigitsT Digits, int16_t Scale,
54  bool ShouldRound) {
55  static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
56 
57  if (ShouldRound)
58  if (!++Digits)
59  // Overflow.
60  return std::make_pair(DigitsT(1) << (getWidth<DigitsT>() - 1), Scale + 1);
61  return std::make_pair(Digits, Scale);
62 }
63 
64 /// Convenience helper for 32-bit rounding.
65 inline std::pair<uint32_t, int16_t> getRounded32(uint32_t Digits, int16_t Scale,
66  bool ShouldRound) {
67  return getRounded(Digits, Scale, ShouldRound);
68 }
69 
70 /// Convenience helper for 64-bit rounding.
71 inline std::pair<uint64_t, int16_t> getRounded64(uint64_t Digits, int16_t Scale,
72  bool ShouldRound) {
73  return getRounded(Digits, Scale, ShouldRound);
74 }
75 
76 /// Adjust a 64-bit scaled number down to the appropriate width.
77 ///
78 /// \pre Adding 64 to \c Scale will not overflow INT16_MAX.
79 template <class DigitsT>
80 inline std::pair<DigitsT, int16_t> getAdjusted(uint64_t Digits,
81  int16_t Scale = 0) {
82  static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
83 
84  const int Width = getWidth<DigitsT>();
85  if (Width == 64 || Digits <= std::numeric_limits<DigitsT>::max())
86  return std::make_pair(Digits, Scale);
87 
88  // Shift right and round.
89  int Shift = 64 - Width - countLeadingZeros(Digits);
90  return getRounded<DigitsT>(Digits >> Shift, Scale + Shift,
91  Digits & (UINT64_C(1) << (Shift - 1)));
92 }
93 
94 /// Convenience helper for adjusting to 32 bits.
95 inline std::pair<uint32_t, int16_t> getAdjusted32(uint64_t Digits,
96  int16_t Scale = 0) {
97  return getAdjusted<uint32_t>(Digits, Scale);
98 }
99 
100 /// Convenience helper for adjusting to 64 bits.
101 inline std::pair<uint64_t, int16_t> getAdjusted64(uint64_t Digits,
102  int16_t Scale = 0) {
103  return getAdjusted<uint64_t>(Digits, Scale);
104 }
105 
106 /// Multiply two 64-bit integers to create a 64-bit scaled number.
107 ///
108 /// Implemented with four 64-bit integer multiplies.
109 std::pair<uint64_t, int16_t> multiply64(uint64_t LHS, uint64_t RHS);
110 
111 /// Multiply two 32-bit integers to create a 32-bit scaled number.
112 ///
113 /// Implemented with one 64-bit integer multiply.
114 template <class DigitsT>
115 inline std::pair<DigitsT, int16_t> getProduct(DigitsT LHS, DigitsT RHS) {
116  static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
117 
118  if (getWidth<DigitsT>() <= 32 || (LHS <= UINT32_MAX && RHS <= UINT32_MAX))
119  return getAdjusted<DigitsT>(uint64_t(LHS) * RHS);
120 
121  return multiply64(LHS, RHS);
122 }
123 
124 /// Convenience helper for 32-bit product.
125 inline std::pair<uint32_t, int16_t> getProduct32(uint32_t LHS, uint32_t RHS) {
126  return getProduct(LHS, RHS);
127 }
128 
129 /// Convenience helper for 64-bit product.
130 inline std::pair<uint64_t, int16_t> getProduct64(uint64_t LHS, uint64_t RHS) {
131  return getProduct(LHS, RHS);
132 }
133 
134 /// Divide two 64-bit integers to create a 64-bit scaled number.
135 ///
136 /// Implemented with long division.
137 ///
138 /// \pre \c Dividend and \c Divisor are non-zero.
139 std::pair<uint64_t, int16_t> divide64(uint64_t Dividend, uint64_t Divisor);
140 
141 /// Divide two 32-bit integers to create a 32-bit scaled number.
142 ///
143 /// Implemented with one 64-bit integer divide/remainder pair.
144 ///
145 /// \pre \c Dividend and \c Divisor are non-zero.
146 std::pair<uint32_t, int16_t> divide32(uint32_t Dividend, uint32_t Divisor);
147 
148 /// Divide two 32-bit numbers to create a 32-bit scaled number.
149 ///
150 /// Implemented with one 64-bit integer divide/remainder pair.
151 ///
152 /// Returns \c (DigitsT_MAX, MaxScale) for divide-by-zero (0 for 0/0).
153 template <class DigitsT>
154 std::pair<DigitsT, int16_t> getQuotient(DigitsT Dividend, DigitsT Divisor) {
155  static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
156  static_assert(sizeof(DigitsT) == 4 || sizeof(DigitsT) == 8,
157  "expected 32-bit or 64-bit digits");
158 
159  // Check for zero.
160  if (!Dividend)
161  return std::make_pair(0, 0);
162  if (!Divisor)
163  return std::make_pair(std::numeric_limits<DigitsT>::max(), MaxScale);
164 
165  if (getWidth<DigitsT>() == 64)
166  return divide64(Dividend, Divisor);
167  return divide32(Dividend, Divisor);
168 }
169 
170 /// Convenience helper for 32-bit quotient.
171 inline std::pair<uint32_t, int16_t> getQuotient32(uint32_t Dividend,
172  uint32_t Divisor) {
173  return getQuotient(Dividend, Divisor);
174 }
175 
176 /// Convenience helper for 64-bit quotient.
177 inline std::pair<uint64_t, int16_t> getQuotient64(uint64_t Dividend,
178  uint64_t Divisor) {
179  return getQuotient(Dividend, Divisor);
180 }
181 
182 /// Implementation of getLg() and friends.
183 ///
184 /// Returns the rounded lg of \c Digits*2^Scale and an int specifying whether
185 /// this was rounded up (1), down (-1), or exact (0).
186 ///
187 /// Returns \c INT32_MIN when \c Digits is zero.
188 template <class DigitsT>
189 inline std::pair<int32_t, int> getLgImpl(DigitsT Digits, int16_t Scale) {
190  static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
191 
192  if (!Digits)
193  return std::make_pair(INT32_MIN, 0);
194 
195  // Get the floor of the lg of Digits.
196  int32_t LocalFloor = sizeof(Digits) * 8 - countLeadingZeros(Digits) - 1;
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.
214 template <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.
223 template <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.
233 template <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.
245 int 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.
251 template <class DigitsT>
252 int 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.
286 template <class DigitsT>
287 int16_t matchScales(DigitsT &LDigits, int16_t &LScale, DigitsT &RDigits,
288  int16_t &RScale) {
289  static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
290 
291  if (LScale < RScale)
292  // 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>(countLeadingZeros(LDigits), ScaleDiff);
309  assert(ShiftL < getWidth<DigitsT>() && "can't shift more than width");
310 
311  int32_t ShiftR = ScaleDiff - ShiftL;
312  if (ShiftR >= getWidth<DigitsT>()) {
313  // Don't bother shifting. RDigits will get zero-ed out anyway.
314  RDigits = 0;
315  return LScale;
316  }
317 
318  LDigits <<= ShiftL;
319  RDigits >>= ShiftR;
320 
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.
332 template <class DigitsT>
333 std::pair<DigitsT, int16_t> getSum(DigitsT LDigits, int16_t LScale,
334  DigitsT RDigits, int16_t RScale) {
335  static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
336 
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.
356 inline 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.
362 inline std::pair<uint64_t, int16_t> getSum64(uint64_t LDigits, int16_t LScale,
363  uint64_t RDigits, int16_t RScale) {
364  return getSum(LDigits, LScale, RDigits, RScale);
365 }
366 
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.
372 template <class DigitsT>
373 std::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.
399 inline 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.
407 inline 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 
417 namespace llvm {
418 
419 class raw_ostream;
421 public:
422  static const 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);
429  static int countLeadingZeros32(uint32_t N) { return countLeadingZeros(N); }
430  static int countLeadingZeros64(uint64_t N) { return countLeadingZeros(N); }
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.
493 template <class DigitsT> class ScaledNumber : ScaledNumberBase {
494 public:
495  static_assert(!std::numeric_limits<DigitsT>::is_signed,
496  "only unsigned floats supported");
497 
498  typedef DigitsT DigitsType;
499 
500 private:
501  typedef std::numeric_limits<DigitsType> DigitsLimits;
502 
503  static const int Width = sizeof(DigitsType) * 8;
504  static_assert(Width <= 64, "invalid integer width for digits");
505 
506 private:
507  DigitsType Digits = 0;
508  int16_t Scale = 0;
509 
510 public:
511  ScaledNumber() = default;
512 
513  constexpr ScaledNumber(DigitsType Digits, int16_t Scale)
514  : Digits(Digits), Scale(Scale) {}
515 
516 private:
517  ScaledNumber(const std::pair<DigitsT, int16_t> &X)
518  : Digits(X.first), Scale(X.second) {}
519 
520 public:
521  static ScaledNumber getZero() { return ScaledNumber(0, 0); }
522  static ScaledNumber getOne() { return ScaledNumber(1, 0); }
525  }
526  static ScaledNumber get(uint64_t N) { return adjustToWidth(N, 0); }
527  static ScaledNumber getInverse(uint64_t N) {
528  return get(N).invert();
529  }
530  static ScaledNumber getFraction(DigitsType N, DigitsType D) {
531  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  }
622  ScaledNumber &operator*=(const ScaledNumber &X);
623  ScaledNumber &operator/=(const ScaledNumber &X);
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 
633 private:
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().
645  ScaledNumbers::matchScales(Digits, Scale, X.Digits, X.Scale);
646  return X;
647  }
648 
649 public:
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.
654  uint64_t scale(uint64_t N) const;
655  uint64_t scaleByInverse(uint64_t N) const {
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 
680 private:
681  static ScaledNumber getProduct(DigitsType LHS, DigitsType RHS) {
682  return ScaledNumbers::getProduct(LHS, 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  }
724 SCALED_NUMBER_BOP(+, += )
725 SCALED_NUMBER_BOP(-, -= )
726 SCALED_NUMBER_BOP(*, *= )
727 SCALED_NUMBER_BOP(/, /= )
728 #undef SCALED_NUMBER_BOP
729 
730 template <class DigitsT>
731 ScaledNumber<DigitsT> operator<<(const ScaledNumber<DigitsT> &L,
732  int16_t Shift) {
733  return ScaledNumber<DigitsT>(L) <<= Shift;
734 }
735 
736 template <class DigitsT>
738  int16_t Shift) {
739  return ScaledNumber<DigitsT>(L) >>= Shift;
740 }
741 
742 template <class DigitsT>
743 raw_ostream &operator<<(raw_ostream &OS, const ScaledNumber<DigitsT> &X) {
744  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 
770 template <class DigitsT>
771 uint64_t ScaledNumber<DigitsT>::scale(uint64_t N) const {
772  if (Width == 64 || N <= DigitsLimits::max())
773  return (get(N) * *this).template toInt<uint64_t>();
774 
775  // Defer to the 64-bit version.
776  return ScaledNumber<uint64_t>(Digits, Scale).scale(N);
777 }
778 
779 template <class DigitsT>
780 template <class IntT>
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 
800 template <class DigitsT>
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 }
817 template <class DigitsT>
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 }
834 template <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 
864 template <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 template <typename T> struct isPodLike;
891 template <typename T> struct isPodLike<ScaledNumber<T>> {
892  static const bool value = true;
893 };
894 
895 } // end namespace llvm
896 
897 #endif // LLVM_SUPPORT_SCALEDNUMBER_H
void dump() const
Definition: ScaledNumber.h:607
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
int32_t getLgFloor(DigitsT Digits, int16_t Scale)
Get the lg floor of a scaled number.
Definition: ScaledNumber.h:223
static uint64_t getHalf(uint64_t N)
Definition: ScaledNumber.h:431
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
std::pair< uint64_t, int16_t > getRounded64(uint64_t Digits, int16_t Scale, bool ShouldRound)
Convenience helper for 64-bit rounding.
Definition: ScaledNumber.h:71
This class represents lattice values for constants.
Definition: AllocatorList.h:24
int getWidth()
Get the width of a number.
Definition: ScaledNumber.h:43
bool operator==(const ScaledNumber &X) const
Definition: ScaledNumber.h:568
static ScaledNumber getOne()
Definition: ScaledNumber.h:522
static lostFraction shiftRight(APFloatBase::integerPart *dst, unsigned int parts, unsigned int bits)
Definition: APFloat.cpp:441
raw_ostream & print(raw_ostream &OS, unsigned Precision=DefaultPrecision) const
Print a decimal representation.
Definition: ScaledNumber.h:603
int compareTo(int64_t N) const
Definition: ScaledNumber.h:675
std::pair< uint64_t, int16_t > getAdjusted64(uint64_t Digits, int16_t Scale=0)
Convenience helper for adjusting to 64 bits.
Definition: ScaledNumber.h:101
ScaledNumber & invert()
Definition: ScaledNumber.h:677
static void dump(uint64_t D, int16_t E, int Width)
static int64_t joinSigned(uint64_t U, bool IsNeg)
Definition: ScaledNumber.h:439
std::size_t countLeadingZeros(T Val, ZeroBehavior ZB=ZB_Width)
Count number of 0&#39;s from the most significant bit to the least stopping at the first 1...
Definition: MathExtras.h:189
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:115
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:80
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
const int32_t MaxScale
Maximum scale; same as APFloat for easy debug printing.
Definition: ScaledNumber.h:37
bool isLargest() const
Definition: ScaledNumber.h:544
bool operator!() const
Definition: ScaledNumber.h:575
std::string toString(Error E)
Write all error messages (if any) in E to a string.
Definition: Error.h:967
#define INT64_MIN
Definition: DataTypes.h:80
int32_t lg() const
The log base 2, rounded.
Definition: ScaledNumber.h:554
#define INT64_MAX
Definition: DataTypes.h:77
ScaledNumber & operator>>=(int16_t Shift)
Definition: ScaledNumber.h:628
std::pair< uint32_t, int16_t > getProduct32(uint32_t LHS, uint32_t RHS)
Convenience helper for 32-bit product.
Definition: ScaledNumber.h:125
int32_t lgFloor() const
The log base 2, rounded towards INT32_MIN.
Definition: ScaledNumber.h:559
static int countLeadingZeros64(uint64_t N)
Definition: ScaledNumber.h:430
std::pair< DigitsT, int16_t > getRounded(DigitsT Digits, int16_t Scale, bool ShouldRound)
Conditionally round up a scaled number.
Definition: ScaledNumber.h:53
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< uint32_t, int16_t > getAdjusted32(uint64_t Digits, int16_t Scale=0)
Convenience helper for adjusting to 32 bits.
Definition: ScaledNumber.h:95
bool operator>(const ScaledNumber &X) const
Definition: ScaledNumber.h:571
ScaledNumber & operator/=(const ScaledNumber &X)
Definition: ScaledNumber.h:819
bool operator<(const ScaledNumber &X) const
Definition: ScaledNumber.h:569
#define P(N)
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
static std::string toString(uint64_t D, int16_t E, int Width, unsigned Precision)
ScaledNumber inverse() const
Definition: ScaledNumber.h:678
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
std::pair< uint64_t, int16_t > getProduct64(uint64_t LHS, uint64_t RHS)
Convenience helper for 64-bit product.
Definition: ScaledNumber.h:130
ScaledNumber & operator-=(const ScaledNumber &X)
Definition: ScaledNumber.h:617
DigitsType getDigits() const
Definition: ScaledNumber.h:535
int64_t scaleByInverse(int64_t N) const
Definition: ScaledNumber.h:664
ScaledNumber & operator+=(const ScaledNumber &X)
Definition: ScaledNumber.h:609
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::string toString(unsigned Precision=DefaultPrecision)
Convert to a decimal representation in a string.
Definition: ScaledNumber.h:596
int16_t matchScales(DigitsT &LDigits, int16_t &LScale, DigitsT &RDigits, int16_t &RScale)
Match scales of two numbers.
Definition: ScaledNumber.h:287
static ScaledNumber getInverse(uint64_t N)
Definition: ScaledNumber.h:527
static uint64_t scale(uint64_t Num, uint32_t N, uint32_t D)
IntT toInt() const
Convert to the given integer type.
Definition: ScaledNumber.h:781
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
ScaledNumber & operator<<=(int16_t Shift)
Definition: ScaledNumber.h:624
Simple representation of a scaled number.
Definition: ScaledNumber.h:493
bool isZero() const
Definition: ScaledNumber.h:543
int compareTo(uint64_t N) const
Definition: ScaledNumber.h:672
int compare(const ScaledNumber &X) const
Definition: ScaledNumber.h:669
int compareImpl(uint64_t L, uint64_t R, int ScaleDiff)
Implementation for comparing scaled numbers.
bool operator!=(const ScaledNumber &X) const
Definition: ScaledNumber.h:570
ScaledNumber & operator*=(const ScaledNumber &X)
Definition: ScaledNumber.h:802
static std::pair< uint64_t, bool > splitSigned(int64_t N)
Definition: ScaledNumber.h:433
static ScaledNumber get(uint64_t N)
Definition: ScaledNumber.h:526
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:154
isPodLike - This is a type trait that is used to determine whether a given type can be copied around ...
Definition: ArrayRef.h:530
static ScaledNumber getLargest()
Definition: ScaledNumber.h:523
constexpr ScaledNumber(DigitsType Digits, int16_t Scale)
Definition: ScaledNumber.h:513
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
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.
int32_t getLgCeiling(DigitsT Digits, int16_t Scale)
Get the lg ceiling of a scaled number.
Definition: ScaledNumber.h:233
bool operator<=(const ScaledNumber &X) const
Definition: ScaledNumber.h:572
std::pair< uint64_t, int16_t > getQuotient64(uint64_t Dividend, uint64_t Divisor)
Convenience helper for 64-bit quotient.
Definition: ScaledNumber.h:177
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static int countLeadingZeros32(uint32_t N)
Definition: ScaledNumber.h:429
bool isOne() const
Definition: ScaledNumber.h:545
static ScaledNumber getZero()
Definition: ScaledNumber.h:521
#define SCALED_NUMBER_BOP(op, base)
Definition: ScaledNumber.h:718
uint64_t scale(uint64_t N) const
Scale a large number accurately.
Definition: ScaledNumber.h:771
int16_t getScale() const
Definition: ScaledNumber.h:534
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< uint64_t, int16_t > divide64(uint64_t Dividend, uint64_t Divisor)
Divide two 64-bit integers to create a 64-bit scaled number.
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
Definition: Lint.cpp:546
std::pair< int32_t, int > getLgImpl(DigitsT Digits, int16_t Scale)
Implementation of getLg() and friends.
Definition: ScaledNumber.h:189
std::pair< uint32_t, int16_t > getQuotient32(uint32_t Dividend, uint32_t Divisor)
Convenience helper for 32-bit quotient.
Definition: ScaledNumber.h:171
std::pair< uint32_t, int16_t > getRounded32(uint32_t Digits, int16_t Scale, bool ShouldRound)
Convenience helper for 32-bit rounding.
Definition: ScaledNumber.h:65
int64_t scale(int64_t N) const
Definition: ScaledNumber.h:660
#define N
static ScaledNumber getFraction(DigitsType N, DigitsType D)
Definition: ScaledNumber.h:530
bool operator>=(const ScaledNumber &X) const
Definition: ScaledNumber.h:573
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
int compare(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale)
Compare two scaled numbers.
Definition: ScaledNumber.h:252
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
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.
#define SCALED_NUMBER_COMPARE_TO(op)
Definition: ScaledNumber.h:756
int32_t getLg(DigitsT Digits, int16_t Scale)
Get the lg (rounded) of a scaled number.
Definition: ScaledNumber.h:214
ScaledNumber< DigitsT > operator>>(const ScaledNumber< DigitsT > &L, int16_t Shift)
Definition: ScaledNumber.h:737
const int32_t MinScale
Maximum scale; same as APFloat for easy debug printing.
Definition: ScaledNumber.h:40
static raw_ostream & print(raw_ostream &OS, uint64_t D, int16_t E, int Width, unsigned Precision)