LLVM  14.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 
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 constexpr int DefaultPrecision = 10;
422 
423  static void dump(uint64_t D, int16_t E, int Width);
424  static raw_ostream &print(raw_ostream &OS, uint64_t D, int16_t E, int Width,
425  unsigned Precision);
426  static std::string toString(uint64_t D, int16_t E, int Width,
427  unsigned Precision);
430  static uint64_t getHalf(uint64_t N) { return (N >> 1) + (N & 1); }
431 
432  static std::pair<uint64_t, bool> splitSigned(int64_t N) {
433  if (N >= 0)
434  return std::make_pair(N, false);
435  uint64_t Unsigned = N == INT64_MIN ? UINT64_C(1) << 63 : uint64_t(-N);
436  return std::make_pair(Unsigned, true);
437  }
438  static int64_t joinSigned(uint64_t U, bool IsNeg) {
439  if (U > uint64_t(INT64_MAX))
440  return IsNeg ? INT64_MIN : INT64_MAX;
441  return IsNeg ? -int64_t(U) : int64_t(U);
442  }
443 };
444 
445 /// Simple representation of a scaled number.
446 ///
447 /// ScaledNumber is a number represented by digits and a scale. It uses simple
448 /// saturation arithmetic and every operation is well-defined for every value.
449 /// It's somewhat similar in behaviour to a soft-float, but is *not* a
450 /// replacement for one. If you're doing numerics, look at \a APFloat instead.
451 /// Nevertheless, we've found these semantics useful for modelling certain cost
452 /// metrics.
453 ///
454 /// The number is split into a signed scale and unsigned digits. The number
455 /// represented is \c getDigits()*2^getScale(). In this way, the digits are
456 /// much like the mantissa in the x87 long double, but there is no canonical
457 /// form so the same number can be represented by many bit representations.
458 ///
459 /// ScaledNumber is templated on the underlying integer type for digits, which
460 /// is expected to be unsigned.
461 ///
462 /// Unlike APFloat, ScaledNumber does not model architecture floating point
463 /// behaviour -- while this might make it a little faster and easier to reason
464 /// about, it certainly makes it more dangerous for general numerics.
465 ///
466 /// ScaledNumber is totally ordered. However, there is no canonical form, so
467 /// there are multiple representations of most scalars. E.g.:
468 ///
469 /// ScaledNumber(8u, 0) == ScaledNumber(4u, 1)
470 /// ScaledNumber(4u, 1) == ScaledNumber(2u, 2)
471 /// ScaledNumber(2u, 2) == ScaledNumber(1u, 3)
472 ///
473 /// ScaledNumber implements most arithmetic operations. Precision is kept
474 /// where possible. Uses simple saturation arithmetic, so that operations
475 /// saturate to 0.0 or getLargest() rather than under or overflowing. It has
476 /// some extra arithmetic for unit inversion. 0.0/0.0 is defined to be 0.0.
477 /// Any other division by 0.0 is defined to be getLargest().
478 ///
479 /// As a convenience for modifying the exponent, left and right shifting are
480 /// both implemented, and both interpret negative shifts as positive shifts in
481 /// the opposite direction.
482 ///
483 /// Scales are limited to the range accepted by x87 long double. This makes
484 /// it trivial to add functionality to convert to APFloat (this is already
485 /// relied on for the implementation of printing).
486 ///
487 /// Possible (and conflicting) future directions:
488 ///
489 /// 1. Turn this into a wrapper around \a APFloat.
490 /// 2. Share the algorithm implementations with \a APFloat.
491 /// 3. Allow \a ScaledNumber to represent a signed number.
492 template <class DigitsT> class ScaledNumber : ScaledNumberBase {
493 public:
494  static_assert(!std::numeric_limits<DigitsT>::is_signed,
495  "only unsigned floats supported");
496 
497  typedef DigitsT DigitsType;
498 
499 private:
500  typedef std::numeric_limits<DigitsType> DigitsLimits;
501 
502  static constexpr int Width = sizeof(DigitsType) * 8;
503  static_assert(Width <= 64, "invalid integer width for digits");
504 
505 private:
506  DigitsType Digits = 0;
507  int16_t Scale = 0;
508 
509 public:
510  ScaledNumber() = default;
511 
512  constexpr ScaledNumber(DigitsType Digits, int16_t Scale)
513  : Digits(Digits), Scale(Scale) {}
514 
515 private:
516  ScaledNumber(const std::pair<DigitsT, int16_t> &X)
517  : Digits(X.first), Scale(X.second) {}
518 
519 public:
520  static ScaledNumber getZero() { return ScaledNumber(0, 0); }
521  static ScaledNumber getOne() { return ScaledNumber(1, 0); }
524  }
525  static ScaledNumber get(uint64_t N) { return adjustToWidth(N, 0); }
527  return get(N).invert();
528  }
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  }
624  shiftLeft(Shift);
625  return *this;
626  }
628  shiftRight(Shift);
629  return *this;
630  }
631 
632 private:
633  void shiftLeft(int32_t Shift);
634  void shiftRight(int32_t Shift);
635 
636  /// Adjust two floats to have matching exponents.
637  ///
638  /// Adjust \c this and \c X to have matching exponents. Returns the new \c X
639  /// by value. Does nothing if \a isZero() for either.
640  ///
641  /// The value that compares smaller will lose precision, and possibly become
642  /// \a isZero().
643  ScaledNumber matchScales(ScaledNumber X) {
644  ScaledNumbers::matchScales(Digits, Scale, X.Digits, X.Scale);
645  return X;
646  }
647 
648 public:
649  /// Scale a large number accurately.
650  ///
651  /// Scale N (multiply it by this). Uses full precision multiplication, even
652  /// if Width is smaller than 64, so information is not lost.
653  uint64_t scale(uint64_t N) const;
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");
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>
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>
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>
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
llvm::ScaledNumbers::getProduct32
std::pair< uint32_t, int16_t > getProduct32(uint32_t LHS, uint32_t RHS)
Convenience helper for 32-bit product.
Definition: ScaledNumber.h:124
MathExtras.h
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::ScaledNumber::get
static ScaledNumber get(uint64_t N)
Definition: ScaledNumber.h:525
llvm::ScaledNumber::getZero
static ScaledNumber getZero()
Definition: ScaledNumber.h:520
llvm::ScaledNumber::scaleByInverse
uint64_t scaleByInverse(uint64_t N) const
Definition: ScaledNumber.h:654
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::ScaledNumber::dump
void dump() const
Definition: ScaledNumber.h:606
llvm::ScaledNumber::operator!=
bool operator!=(const ScaledNumber &X) const
Definition: ScaledNumber.h:569
llvm::ScaledNumbers::getProduct
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
llvm::ScaledNumbers::getDifference64
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
llvm::ScaledNumber::lgCeiling
int32_t lgCeiling() const
The log base 2, rounded towards INT32_MAX.
Definition: ScaledNumber.h:563
llvm::ScaledNumber::operator<=
bool operator<=(const ScaledNumber &X) const
Definition: ScaledNumber.h:571
llvm::ScaledNumbers::getDifference
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
llvm::ScaledNumber::inverse
ScaledNumber inverse() const
Definition: ScaledNumber.h:677
llvm::ScaledNumberBase::splitSigned
static std::pair< uint64_t, bool > splitSigned(int64_t N)
Definition: ScaledNumber.h:432
llvm::ScaledNumber::operator==
bool operator==(const ScaledNumber &X) const
Definition: ScaledNumber.h:567
llvm::ScaledNumbers::MaxScale
const int32_t MaxScale
Maximum scale; same as APFloat for easy debug printing.
Definition: ScaledNumber.h:36
Shift
bool Shift
Definition: README.txt:468
llvm::ScaledNumber::operator-=
ScaledNumber & operator-=(const ScaledNumber &X)
Definition: ScaledNumber.h:616
llvm::ScaledNumber::operator>
bool operator>(const ScaledNumber &X) const
Definition: ScaledNumber.h:570
llvm::ScaledNumberBase::DefaultPrecision
static constexpr int DefaultPrecision
Definition: ScaledNumber.h:421
llvm::ScaledNumbers::MinScale
const int32_t MinScale
Maximum scale; same as APFloat for easy debug printing.
Definition: ScaledNumber.h:39
llvm::ScaledNumberBase::getHalf
static uint64_t getHalf(uint64_t N)
Definition: ScaledNumber.h:430
llvm::ScaledNumber::invert
ScaledNumber & invert()
Definition: ScaledNumber.h:676
llvm::ScaledNumber::scaleByInverse
int64_t scaleByInverse(int64_t N) const
Definition: ScaledNumber.h:663
llvm::ScaledNumbers::getAdjusted32
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
llvm::operator>>
ScaledNumber< DigitsT > operator>>(const ScaledNumber< DigitsT > &L, int16_t Shift)
Definition: ScaledNumber.h:736
isZero
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
Definition: Lint.cpp:519
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::ScaledNumbers::getWidth
int getWidth()
Get the width of a number.
Definition: ScaledNumber.h:42
llvm::ScaledNumber::lg
int32_t lg() const
The log base 2, rounded.
Definition: ScaledNumber.h:553
llvm::ScaledNumber::compareTo
int compareTo(int64_t N) const
Definition: ScaledNumber.h:674
llvm::ScaledNumber::getLargest
static ScaledNumber getLargest()
Definition: ScaledNumber.h:522
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::ScaledNumber::print
raw_ostream & print(raw_ostream &OS, unsigned Precision=DefaultPrecision) const
Print a decimal representation.
Definition: ScaledNumber.h:602
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:230
INT64_MAX
#define INT64_MAX
Definition: DataTypes.h:71
llvm::ScaledNumbers::matchScales
int16_t matchScales(DigitsT &LDigits, int16_t &LScale, DigitsT &RDigits, int16_t &RScale)
Match scales of two numbers.
Definition: ScaledNumber.h:286
llvm::ScaledNumbers::getAdjusted64
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
llvm::ScaledNumbers::divide32
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.
Definition: ScaledNumber.cpp:57
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::ScaledNumberBase::print
static raw_ostream & print(raw_ostream &OS, uint64_t D, int16_t E, int Width, unsigned Precision)
Definition: ScaledNumber.cpp:315
llvm::ScaledNumber::operator!
bool operator!() const
Definition: ScaledNumber.h:574
llvm::ScaledNumbers::getAdjusted
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
uint64_t
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::ScaledNumbers::getQuotient64
std::pair< uint64_t, int16_t > getQuotient64(uint64_t Dividend, uint64_t Divisor)
Convenience helper for 64-bit quotient.
Definition: ScaledNumber.h:176
llvm::ScaledNumber::isOne
bool isOne() const
Definition: ScaledNumber.h:544
llvm::ScaledNumbers::getRounded64
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
llvm::ScaledNumber::isZero
bool isZero() const
Definition: ScaledNumber.h:542
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::ScaledNumber::getInverse
static ScaledNumber getInverse(uint64_t N)
Definition: ScaledNumber.h:526
llvm::ScaledNumbers::compare
int compare(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale)
Compare two scaled numbers.
Definition: ScaledNumber.h:251
llvm::ScaledNumber::getScale
int16_t getScale() const
Definition: ScaledNumber.h:533
llvm::ScaledNumber::getFraction
static ScaledNumber getFraction(DigitsType N, DigitsType D)
Definition: ScaledNumber.h:529
llvm::ScaledNumbers::getRounded
std::pair< DigitsT, int16_t > getRounded(DigitsT Digits, int16_t Scale, bool ShouldRound)
Conditionally round up a scaled number.
Definition: ScaledNumber.h:52
llvm::ScaledNumber::operator>=
bool operator>=(const ScaledNumber &X) const
Definition: ScaledNumber.h:572
llvm::ScaledNumber::operator<
bool operator<(const ScaledNumber &X) const
Definition: ScaledNumber.h:568
llvm::ScaledNumberBase::joinSigned
static int64_t joinSigned(uint64_t U, bool IsNeg)
Definition: ScaledNumber.h:438
llvm::ScaledNumbers::getLg
int32_t getLg(DigitsT Digits, int16_t Scale)
Get the lg (rounded) of a scaled number.
Definition: ScaledNumber.h:213
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
llvm::ScaledNumber::toString
std::string toString(unsigned Precision=DefaultPrecision)
Convert to a decimal representation in a string.
Definition: ScaledNumber.h:595
llvm::ScaledNumbers::getRounded32
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
llvm::ScaledNumber::operator*=
ScaledNumber & operator*=(const ScaledNumber &X)
Definition: ScaledNumber.h:801
llvm::ScaledNumber::toInt
IntT toInt() const
Convert to the given integer type.
Definition: ScaledNumber.h:780
uint32_t
llvm::ScaledNumbers::compareImpl
int compareImpl(uint64_t L, uint64_t R, int ScaleDiff)
Implementation for comparing scaled numbers.
Definition: ScaledNumber.cpp:124
SCALED_NUMBER_COMPARE_TO
#define SCALED_NUMBER_COMPARE_TO(op)
Definition: ScaledNumber.h:755
Unsigned
@ Unsigned
Definition: NVPTXISelLowering.cpp:4637
llvm::ScaledNumber::DigitsType
DigitsT DigitsType
Definition: ScaledNumber.h:495
llvm::ScaledNumber::scale
uint64_t scale(uint64_t N) const
Scale a large number accurately.
Definition: ScaledNumber.h:770
llvm::ScaledNumbers::getLgImpl
std::pair< int32_t, int > getLgImpl(DigitsT Digits, int16_t Scale)
Implementation of getLg() and friends.
Definition: ScaledNumber.h:188
llvm::ScaledNumbers::getSum64
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
llvm::ScaledNumbers::getQuotient32
std::pair< uint32_t, int16_t > getQuotient32(uint32_t Dividend, uint32_t Divisor)
Convenience helper for 32-bit quotient.
Definition: ScaledNumber.h:170
llvm::ScaledNumber::ScaledNumber
constexpr ScaledNumber(DigitsType Digits, int16_t Scale)
Definition: ScaledNumber.h:512
llvm::ScaledNumber::operator+=
ScaledNumber & operator+=(const ScaledNumber &X)
Definition: ScaledNumber.h:608
llvm::ScaledNumbers::getQuotient
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
llvm::ScaledNumberBase::toString
static std::string toString(uint64_t D, int16_t E, int Width, unsigned Precision)
Definition: ScaledNumber.cpp:201
llvm::ScaledNumbers::multiply64
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.
Definition: ScaledNumber.cpp:22
llvm::ScaledNumber
Simple representation of a scaled number.
Definition: ScaledNumber.h:492
llvm::ScaledNumbers::getLgFloor
int32_t getLgFloor(DigitsT Digits, int16_t Scale)
Get the lg floor of a scaled number.
Definition: ScaledNumber.h:222
llvm::ScaledNumber::getOne
static ScaledNumber getOne()
Definition: ScaledNumber.h:521
llvm::ScaledNumbers::getSum32
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
get
Should compile to something r4 addze r3 instead we get
Definition: README.txt:24
llvm::ScaledNumbers::getProduct64
std::pair< uint64_t, int16_t > getProduct64(uint64_t LHS, uint64_t RHS)
Convenience helper for 64-bit product.
Definition: ScaledNumber.h:129
llvm::ScaledNumbers::getLgCeiling
int32_t getLgCeiling(DigitsT Digits, int16_t Scale)
Get the lg ceiling of a scaled number.
Definition: ScaledNumber.h:232
llvm::ScaledNumberBase
Definition: ScaledNumber.h:419
llvm::ScaledNumbers::getSum
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
llvm::ScaledNumber::operator/=
ScaledNumber & operator/=(const ScaledNumber &X)
Definition: ScaledNumber.h:818
llvm::countLeadingZeros
unsigned countLeadingZeros(T Val, ZeroBehavior ZB=ZB_Width)
Count number of 0's from the most significant bit to the least stopping at the first 1.
Definition: MathExtras.h:225
llvm::ScaledNumberBase::countLeadingZeros64
static int countLeadingZeros64(uint64_t N)
Definition: ScaledNumber.h:429
llvm::AMDGPU::Hwreg::Width
Width
Definition: SIDefines.h:410
llvm::ScaledNumber::isLargest
bool isLargest() const
Definition: ScaledNumber.h:543
llvm::ScaledNumbers::divide64
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.
Definition: ScaledNumber.cpp:80
llvm::ScaledNumber::scale
int64_t scale(int64_t N) const
Definition: ScaledNumber.h:659
llvm::ScaledNumber::compare
int compare(const ScaledNumber &X) const
Definition: ScaledNumber.h:668
N
#define N
llvm::shiftRight
static lostFraction shiftRight(APFloatBase::integerPart *dst, unsigned int parts, unsigned int bits)
Definition: APFloat.cpp:514
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
llvm::ScaledNumber::lgFloor
int32_t lgFloor() const
The log base 2, rounded towards INT32_MIN.
Definition: ScaledNumber.h:558
llvm::ScaledNumbers::getDifference32
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
llvm::ScaledNumber::ScaledNumber
ScaledNumber()=default
llvm::ScaledNumberBase::dump
static void dump(uint64_t D, int16_t E, int Width)
Definition: ScaledNumber.cpp:320
llvm::ScaledNumber::compareTo
int compareTo(uint64_t N) const
Definition: ScaledNumber.h:671
llvm::ScaledNumber::operator>>=
ScaledNumber & operator>>=(int16_t Shift)
Definition: ScaledNumber.h:627
SCALED_NUMBER_BOP
#define SCALED_NUMBER_BOP(op, base)
Definition: ScaledNumber.h:717
llvm::ScaledNumberBase::countLeadingZeros32
static int countLeadingZeros32(uint32_t N)
Definition: ScaledNumber.h:428
llvm::ScaledNumber::getDigits
DigitsType getDigits() const
Definition: ScaledNumber.h:534
llvm::ScaledNumber::operator<<=
ScaledNumber & operator<<=(int16_t Shift)
Definition: ScaledNumber.h:623
INT64_MIN
#define INT64_MIN
Definition: DataTypes.h:74