LLVM  9.0.0svn
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 
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;
420 public:
421  static const 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 const 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); }
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.
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 
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  }
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().
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>
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)
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>
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>
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>
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
void dump() const
Definition: ScaledNumber.h:606
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:222
static uint64_t getHalf(uint64_t N)
Definition: ScaledNumber.h:430
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:70
This class represents lattice values for constants.
Definition: AllocatorList.h:23
int getWidth()
Get the width of a number.
Definition: ScaledNumber.h:42
bool operator==(const ScaledNumber &X) const
Definition: ScaledNumber.h:567
static ScaledNumber getOne()
Definition: ScaledNumber.h:521
static lostFraction shiftRight(APFloatBase::integerPart *dst, unsigned int parts, unsigned int bits)
Definition: APFloat.cpp:479
raw_ostream & print(raw_ostream &OS, unsigned Precision=DefaultPrecision) const
Print a decimal representation.
Definition: ScaledNumber.h:602
int compareTo(int64_t N) const
Definition: ScaledNumber.h:674
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
ScaledNumber & invert()
Definition: ScaledNumber.h:676
static void dump(uint64_t D, int16_t E, int Width)
static int64_t joinSigned(uint64_t U, bool IsNeg)
Definition: ScaledNumber.h:438
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 > 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< DigitsT, int16_t > getDifference(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale)
Get the difference of two scaled numbers.
Definition: ScaledNumber.h:372
const int32_t MaxScale
Maximum scale; same as APFloat for easy debug printing.
Definition: ScaledNumber.h:36
bool isLargest() const
Definition: ScaledNumber.h:543
bool operator!() const
Definition: ScaledNumber.h:574
std::string toString(Error E)
Write all error messages (if any) in E to a string.
Definition: Error.h:966
#define INT64_MIN
Definition: DataTypes.h:80
int32_t lg() const
The log base 2, rounded.
Definition: ScaledNumber.h:553
#define INT64_MAX
Definition: DataTypes.h:77
ScaledNumber & operator>>=(int16_t Shift)
Definition: ScaledNumber.h:627
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 lgFloor() const
The log base 2, rounded towards INT32_MIN.
Definition: ScaledNumber.h:558
static int countLeadingZeros64(uint64_t N)
Definition: ScaledNumber.h:429
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:398
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
bool operator>(const ScaledNumber &X) const
Definition: ScaledNumber.h:570
ScaledNumber & operator/=(const ScaledNumber &X)
Definition: ScaledNumber.h:818
bool operator<(const ScaledNumber &X) const
Definition: ScaledNumber.h:568
#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:677
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:129
ScaledNumber & operator-=(const ScaledNumber &X)
Definition: ScaledNumber.h:616
DigitsType getDigits() const
Definition: ScaledNumber.h:534
int64_t scaleByInverse(int64_t N) const
Definition: ScaledNumber.h:663
ScaledNumber & operator+=(const ScaledNumber &X)
Definition: ScaledNumber.h:608
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:332
std::string toString(unsigned Precision=DefaultPrecision)
Convert to a decimal representation in a string.
Definition: ScaledNumber.h:595
int16_t matchScales(DigitsT &LDigits, int16_t &LScale, DigitsT &RDigits, int16_t &RScale)
Match scales of two numbers.
Definition: ScaledNumber.h:286
static ScaledNumber getInverse(uint64_t N)
Definition: ScaledNumber.h:526
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:780
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
ScaledNumber & operator<<=(int16_t Shift)
Definition: ScaledNumber.h:623
Simple representation of a scaled number.
Definition: ScaledNumber.h:492
unsigned 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:188
bool isZero() const
Definition: ScaledNumber.h:542
int compareTo(uint64_t N) const
Definition: ScaledNumber.h:671
int compare(const ScaledNumber &X) const
Definition: ScaledNumber.h:668
int compareImpl(uint64_t L, uint64_t R, int ScaleDiff)
Implementation for comparing scaled numbers.
bool operator!=(const ScaledNumber &X) const
Definition: ScaledNumber.h:569
ScaledNumber & operator*=(const ScaledNumber &X)
Definition: ScaledNumber.h:801
static std::pair< uint64_t, bool > splitSigned(int64_t N)
Definition: ScaledNumber.h:432
static ScaledNumber get(uint64_t N)
Definition: ScaledNumber.h:525
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
static ScaledNumber getLargest()
Definition: ScaledNumber.h:522
constexpr ScaledNumber(DigitsType Digits, int16_t Scale)
Definition: ScaledNumber.h:512
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:406
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:232
bool operator<=(const ScaledNumber &X) const
Definition: ScaledNumber.h:571
std::pair< uint64_t, int16_t > getQuotient64(uint64_t Dividend, uint64_t Divisor)
Convenience helper for 64-bit quotient.
Definition: ScaledNumber.h:176
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static int countLeadingZeros32(uint32_t N)
Definition: ScaledNumber.h:428
bool isOne() const
Definition: ScaledNumber.h:544
static ScaledNumber getZero()
Definition: ScaledNumber.h:520
#define SCALED_NUMBER_BOP(op, base)
Definition: ScaledNumber.h:717
uint64_t scale(uint64_t N) const
Scale a large number accurately.
Definition: ScaledNumber.h:770
int16_t getScale() const
Definition: ScaledNumber.h:533
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:361
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:549
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 > getQuotient32(uint32_t Dividend, uint32_t Divisor)
Convenience helper for 32-bit quotient.
Definition: ScaledNumber.h:170
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
int64_t scale(int64_t N) const
Definition: ScaledNumber.h:659
#define N
static ScaledNumber getFraction(DigitsType N, DigitsType D)
Definition: ScaledNumber.h:529
bool operator>=(const ScaledNumber &X) const
Definition: ScaledNumber.h:572
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:355
int compare(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale)
Compare two scaled numbers.
Definition: ScaledNumber.h:251
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
int32_t lgCeiling() const
The log base 2, rounded towards INT32_MAX.
Definition: ScaledNumber.h:563
uint64_t scaleByInverse(uint64_t N) const
Definition: ScaledNumber.h:654
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
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:755
int32_t getLg(DigitsT Digits, int16_t Scale)
Get the lg (rounded) of a scaled number.
Definition: ScaledNumber.h:213
ScaledNumber< DigitsT > operator>>(const ScaledNumber< DigitsT > &L, int16_t Shift)
Definition: ScaledNumber.h:736
const int32_t MinScale
Maximum scale; same as APFloat for easy debug printing.
Definition: ScaledNumber.h:39
static raw_ostream & print(raw_ostream &OS, uint64_t D, int16_t E, int Width, unsigned Precision)