Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Support/ScaledNumber.h
Line
Count
Source (jump to first uncovered line)
1
//===- llvm/Support/ScaledNumber.h - Support for scaled numbers -*- C++ -*-===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
// This file contains functions (and a class) useful for working with scaled
10
// numbers -- in particular, pairs of integers where one represents digits and
11
// another represents a scale.  The functions are helpers and live in the
12
// namespace ScaledNumbers.  The class ScaledNumber is useful for modelling
13
// certain cost metrics that need simple, integer-like semantics that are easy
14
// to reason about.
15
//
16
// These might remind you of soft-floats.  If you want one of those, you're in
17
// the wrong place.  Look at include/llvm/ADT/APFloat.h instead.
18
//
19
//===----------------------------------------------------------------------===//
20
21
#ifndef LLVM_SUPPORT_SCALEDNUMBER_H
22
#define LLVM_SUPPORT_SCALEDNUMBER_H
23
24
#include "llvm/Support/MathExtras.h"
25
#include <algorithm>
26
#include <cstdint>
27
#include <limits>
28
#include <string>
29
#include <tuple>
30
#include <utility>
31
32
namespace llvm {
33
namespace ScaledNumbers {
34
35
/// Maximum scale; same as APFloat for easy debug printing.
36
const int32_t MaxScale = 16383;
37
38
/// Maximum scale; same as APFloat for easy debug printing.
39
const int32_t MinScale = -16382;
40
41
/// Get the width of a number.
42
57.5M
template <class DigitsT> inline int getWidth() { return sizeof(DigitsT) * 8; }
int llvm::ScaledNumbers::getWidth<unsigned int>()
Line
Count
Source
42
151
template <class DigitsT> inline int getWidth() { return sizeof(DigitsT) * 8; }
int llvm::ScaledNumbers::getWidth<unsigned long long>()
Line
Count
Source
42
57.5M
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
28.5M
                                              bool ShouldRound) {
54
28.5M
  static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
55
28.5M
56
28.5M
  if (ShouldRound)
57
13.0M
    if (!++Digits)
58
619k
      // Overflow.
59
619k
      return std::make_pair(DigitsT(1) << (getWidth<DigitsT>() - 1), Scale + 1);
60
27.9M
  return std::make_pair(Digits, Scale);
61
27.9M
}
std::__1::pair<unsigned int, short> llvm::ScaledNumbers::getRounded<unsigned int>(unsigned int, short, bool)
Line
Count
Source
53
28
                                              bool ShouldRound) {
54
28
  static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
55
28
56
28
  if (ShouldRound)
57
7
    if (!++Digits)
58
2
      // Overflow.
59
2
      return std::make_pair(DigitsT(1) << (getWidth<DigitsT>() - 1), Scale + 1);
60
26
  return std::make_pair(Digits, Scale);
61
26
}
std::__1::pair<unsigned long long, short> llvm::ScaledNumbers::getRounded<unsigned long long>(unsigned long long, short, bool)
Line
Count
Source
53
28.5M
                                              bool ShouldRound) {
54
28.5M
  static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
55
28.5M
56
28.5M
  if (ShouldRound)
57
13.0M
    if (!++Digits)
58
619k
      // Overflow.
59
619k
      return std::make_pair(DigitsT(1) << (getWidth<DigitsT>() - 1), Scale + 1);
60
27.9M
  return std::make_pair(Digits, Scale);
61
27.9M
}
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
10.3M
                                               int16_t Scale = 0) {
81
10.3M
  static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
82
10.3M
83
10.3M
  const int Width = getWidth<DigitsT>();
84
10.3M
  if (Width == 64 || 
Digits <= std::numeric_limits<DigitsT>::max()37
)
85
10.3M
    return std::make_pair(Digits, Scale);
86
22
87
22
  // Shift right and round.
88
22
  int Shift = 64 - Width - countLeadingZeros(Digits);
89
22
  return getRounded<DigitsT>(Digits >> Shift, Scale + Shift,
90
22
                             Digits & (UINT64_C(1) << (Shift - 1)));
91
22
}
std::__1::pair<unsigned int, short> llvm::ScaledNumbers::getAdjusted<unsigned int>(unsigned long long, short)
Line
Count
Source
80
37
                                               int16_t Scale = 0) {
81
37
  static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
82
37
83
37
  const int Width = getWidth<DigitsT>();
84
37
  if (Width == 64 || Digits <= std::numeric_limits<DigitsT>::max())
85
14
    return std::make_pair(Digits, Scale);
86
23
87
23
  // Shift right and round.
88
23
  int Shift = 64 - Width - countLeadingZeros(Digits);
89
23
  return getRounded<DigitsT>(Digits >> Shift, Scale + Shift,
90
23
                             Digits & (UINT64_C(1) << (Shift - 1)));
91
23
}
std::__1::pair<unsigned long long, short> llvm::ScaledNumbers::getAdjusted<unsigned long long>(unsigned long long, short)
Line
Count
Source
80
10.3M
                                               int16_t Scale = 0) {
81
10.3M
  static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
82
10.3M
83
10.3M
  const int Width = getWidth<DigitsT>();
84
10.3M
  if (Width == 64 || 
Digits <= std::numeric_limits<DigitsT>::max()0
)
85
10.3M
    return std::make_pair(Digits, Scale);
86
18.4E
87
18.4E
  // Shift right and round.
88
18.4E
  int Shift = 64 - Width - countLeadingZeros(Digits);
89
18.4E
  return getRounded<DigitsT>(Digits >> Shift, Scale + Shift,
90
18.4E
                             Digits & (UINT64_C(1) << (Shift - 1)));
91
18.4E
}
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
35.8M
inline std::pair<DigitsT, int16_t> getProduct(DigitsT LHS, DigitsT RHS) {
115
35.8M
  static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
116
35.8M
117
35.8M
  if (
getWidth<DigitsT>() <= 3235.8M
|| (LHS <= UINT32_MAX &&
RHS <= UINT32_MAX6.75M
))
118
3.99M
    return getAdjusted<DigitsT>(uint64_t(LHS) * RHS);
119
31.8M
120
31.8M
  return multiply64(LHS, RHS);
121
31.8M
}
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
10.7M
std::pair<DigitsT, int16_t> getQuotient(DigitsT Dividend, DigitsT Divisor) {
154
10.7M
  static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
155
10.7M
  static_assert(sizeof(DigitsT) == 4 || sizeof(DigitsT) == 8,
156
10.7M
                "expected 32-bit or 64-bit digits");
157
10.7M
158
10.7M
  // Check for zero.
159
10.7M
  if (!Dividend)
160
3
    return std::make_pair(0, 0);
161
10.7M
  if (!Divisor)
162
2
    return std::make_pair(std::numeric_limits<DigitsT>::max(), MaxScale);
163
10.7M
164
10.7M
  if (getWidth<DigitsT>() == 64)
165
10.7M
    return divide64(Dividend, Divisor);
166
21
  return divide32(Dividend, Divisor);
167
21
}
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
208M
inline std::pair<int32_t, int> getLgImpl(DigitsT Digits, int16_t Scale) {
189
208M
  static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
190
208M
191
208M
  if (!Digits)
192
9
    return std::make_pair(INT32_MIN, 0);
193
208M
194
208M
  // Get the floor of the lg of Digits.
195
208M
  int32_t LocalFloor = sizeof(Digits) * 8 - countLeadingZeros(Digits) - 1;
196
208M
197
208M
  // Get the actual floor.
198
208M
  int32_t Floor = Scale + LocalFloor;
199
208M
  if (Digits == UINT64_C(1) << LocalFloor)
200
71.5M
    return std::make_pair(Floor, 0);
201
136M
202
136M
  // Round based on the next digit.
203
136M
  assert(LocalFloor >= 1);
204
136M
  bool Round = Digits & UINT64_C(1) << (LocalFloor - 1);
205
136M
  return std::make_pair(Floor + Round, Round ? 
185.3M
:
-151.2M
);
206
136M
}
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
4.33M
template <class DigitsT> int32_t getLg(DigitsT Digits, int16_t Scale) {
214
4.33M
  return getLgImpl(Digits, Scale).first;
215
4.33M
}
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
203M
template <class DigitsT> int32_t getLgFloor(DigitsT Digits, int16_t Scale) {
223
203M
  auto Lg = getLgImpl(Digits, Scale);
224
203M
  return Lg.first - (Lg.second > 0);
225
203M
}
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
106M
int compare(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale) {
252
106M
  static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
253
106M
254
106M
  // Check for zero.
255
106M
  if (!LDigits)
256
4.33M
    return RDigits ? 
-14.33M
:
03
;
257
101M
  if (!RDigits)
258
1
    return 1;
259
101M
260
101M
  // Check for the scale.  Use getLgFloor to be sure that the scale difference
261
101M
  // is always lower than 64.
262
101M
  int32_t lgL = getLgFloor(LDigits, LScale), lgR = getLgFloor(RDigits, RScale);
263
101M
  if (lgL != lgR)
264
96.4M
    return lgL < lgR ? 
-135.8M
:
160.5M
;
265
5.53M
266
5.53M
  // Compare digits.
267
5.53M
  if (LScale < RScale)
268
220k
    return compareImpl(LDigits, RDigits, RScale - LScale);
269
5.31M
270
5.31M
  return -compareImpl(RDigits, LDigits, LScale - RScale);
271
5.31M
}
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
95
                    int16_t &RScale) {
288
95
  static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
289
95
290
95
  if (LScale < RScale)
291
21
    // Swap arguments.
292
21
    return matchScales(RDigits, RScale, LDigits, LScale);
293
74
  if (!LDigits)
294
16
    return RScale;
295
58
  if (!RDigits || 
LScale == RScale54
)
296
15
    return LScale;
297
43
298
43
  // Now LScale > RScale.  Get the difference.
299
43
  int32_t ScaleDiff = int32_t(LScale) - RScale;
300
43
  if (ScaleDiff >= 2 * getWidth<DigitsT>()) {
301
0
    // Don't bother shifting.  RDigits will get zero-ed out anyway.
302
0
    RDigits = 0;
303
0
    return LScale;
304
0
  }
305
43
306
43
  // Shift LDigits left as much as possible, then shift RDigits right.
307
43
  int32_t ShiftL = std::min<int32_t>(countLeadingZeros(LDigits), ScaleDiff);
308
43
  assert(ShiftL < getWidth<DigitsT>() && "can't shift more than width");
309
43
310
43
  int32_t ShiftR = ScaleDiff - ShiftL;
311
43
  if (ShiftR >= getWidth<DigitsT>()) {
312
0
    // Don't bother shifting.  RDigits will get zero-ed out anyway.
313
0
    RDigits = 0;
314
0
    return LScale;
315
0
  }
316
43
317
43
  LDigits <<= ShiftL;
318
43
  RDigits >>= ShiftR;
319
43
320
43
  LScale -= ShiftL;
321
43
  RScale += ShiftR;
322
43
  assert(LScale == RScale && "scales should match");
323
43
  return LScale;
324
43
}
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
36
                                   DigitsT RDigits, int16_t RScale) {
334
36
  static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
335
36
336
36
  // Check inputs up front.  This is only relevant if addition overflows, but
337
36
  // testing here should catch more bugs.
338
36
  assert(LScale < INT16_MAX && "scale too large");
339
36
  assert(RScale < INT16_MAX && "scale too large");
340
36
341
36
  // Normalize digits to match scales.
342
36
  int16_t Scale = matchScales(LDigits, LScale, RDigits, RScale);
343
36
344
36
  // Compute sum.
345
36
  DigitsT Sum = LDigits + RDigits;
346
36
  if (Sum >= RDigits)
347
34
    return std::make_pair(Sum, Scale);
348
2
349
2
  // Adjust sum after arithmetic overflow.
350
2
  DigitsT HighBit = DigitsT(1) << (getWidth<DigitsT>() - 1);
351
2
  return std::make_pair(HighBit | Sum >> 1, Scale + 1);
352
2
}
353
354
/// Convenience helper for 32-bit sum.
355
inline std::pair<uint32_t, int16_t> getSum32(uint32_t LDigits, int16_t LScale,
356
                                             uint32_t RDigits, int16_t RScale) {
357
  return getSum(LDigits, LScale, RDigits, RScale);
358
}
359
360
/// Convenience helper for 64-bit sum.
361
inline std::pair<uint64_t, int16_t> getSum64(uint64_t LDigits, int16_t LScale,
362
                                             uint64_t RDigits, int16_t RScale) {
363
  return getSum(LDigits, LScale, RDigits, RScale);
364
}
365
366
/// Get the difference of two scaled numbers.
367
///
368
/// Get LHS minus RHS with as much precision as possible.
369
///
370
/// Returns \c (0, 0) if the RHS is larger than the LHS.
371
template <class DigitsT>
372
std::pair<DigitsT, int16_t> getDifference(DigitsT LDigits, int16_t LScale,
373
                                          DigitsT RDigits, int16_t RScale) {
374
  static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
375
376
  // Normalize digits to match scales.
377
  const DigitsT SavedRDigits = RDigits;
378
  const int16_t SavedRScale = RScale;
379
  matchScales(LDigits, LScale, RDigits, RScale);
380
381
  // Compute difference.
382
  if (LDigits <= RDigits)
383
    return std::make_pair(0, 0);
384
  if (RDigits || !SavedRDigits)
385
    return std::make_pair(LDigits - RDigits, LScale);
386
387
  // Check if RDigits just barely lost its last bit.  E.g., for 32-bit:
388
  //
389
  //   1*2^32 - 1*2^0 == 0xffffffff != 1*2^32
390
  const auto RLgFloor = getLgFloor(SavedRDigits, SavedRScale);
391
  if (!compare(LDigits, LScale, DigitsT(1), RLgFloor + getWidth<DigitsT>()))
392
    return std::make_pair(std::numeric_limits<DigitsT>::max(), RLgFloor);
393
394
  return std::make_pair(LDigits, LScale);
395
}
396
397
/// Convenience helper for 32-bit difference.
398
inline std::pair<uint32_t, int16_t> getDifference32(uint32_t LDigits,
399
                                                    int16_t LScale,
400
                                                    uint32_t RDigits,
401
                                                    int16_t RScale) {
402
  return getDifference(LDigits, LScale, RDigits, RScale);
403
}
404
405
/// Convenience helper for 64-bit difference.
406
inline std::pair<uint64_t, int16_t> getDifference64(uint64_t LDigits,
407
                                                    int16_t LScale,
408
                                                    uint64_t RDigits,
409
                                                    int16_t RScale) {
410
  return getDifference(LDigits, LScale, RDigits, RScale);
411
}
412
413
} // end namespace ScaledNumbers
414
} // end namespace llvm
415
416
namespace llvm {
417
418
class raw_ostream;
419
class ScaledNumberBase {
420
public:
421
  static 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
0
  static int countLeadingZeros32(uint32_t N) { return countLeadingZeros(N); }
429
2
  static int countLeadingZeros64(uint64_t N) { return countLeadingZeros(N); }
430
0
  static uint64_t getHalf(uint64_t N) { return (N >> 1) + (N & 1); }
431
432
0
  static std::pair<uint64_t, bool> splitSigned(int64_t N) {
433
0
    if (N >= 0)
434
0
      return std::make_pair(N, false);
435
0
    uint64_t Unsigned = N == INT64_MIN ? UINT64_C(1) << 63 : uint64_t(-N);
436
0
    return std::make_pair(Unsigned, true);
437
0
  }
438
0
  static int64_t joinSigned(uint64_t U, bool IsNeg) {
439
0
    if (U > uint64_t(INT64_MAX))
440
0
      return IsNeg ? INT64_MIN : INT64_MAX;
441
0
    return IsNeg ? -int64_t(U) : int64_t(U);
442
0
  }
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
32.9M
  ScaledNumber() = default;
511
512
  constexpr ScaledNumber(DigitsType Digits, int16_t Scale)
513
41.3M
      : Digits(Digits), Scale(Scale) {}
514
515
private:
516
  ScaledNumber(const std::pair<DigitsT, int16_t> &X)
517
52.9M
      : Digits(X.first), Scale(X.second) {}
518
519
public:
520
4.33M
  static ScaledNumber getZero() { return ScaledNumber(0, 0); }
521
  static ScaledNumber getOne() { return ScaledNumber(1, 0); }
522
4.33M
  static ScaledNumber getLargest() {
523
4.33M
    return ScaledNumber(DigitsLimits::max(), ScaledNumbers::MaxScale);
524
4.33M
  }
525
6.37M
  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
169M
  bool isZero() const { return !Digits; }
543
0
  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
4.33M
  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
6
  bool operator==(const ScaledNumber &X) const { return compare(X) == 0; }
568
53.1M
  bool operator<(const ScaledNumber &X) const { return compare(X) < 0; }
569
  bool operator!=(const ScaledNumber &X) const { return compare(X) != 0; }
570
  bool operator>(const ScaledNumber &X) const { return compare(X) > 0; }
571
  bool operator<=(const ScaledNumber &X) const { return compare(X) <= 0; }
572
  bool operator>=(const ScaledNumber &X) const { return compare(X) >= 0; }
573
574
  bool operator!() const { return isZero(); }
575
576
  /// Convert to a decimal representation in a string.
577
  ///
578
  /// Convert to a string.  Uses scientific notation for very large/small
579
  /// numbers.  Scientific notation is used roughly for numbers outside of the
580
  /// range 2^-64 through 2^64.
581
  ///
582
  /// \c Precision indicates the number of decimal digits of precision to use;
583
  /// 0 requests the maximum available.
584
  ///
585
  /// As a special case to make debugging easier, if the number is small enough
586
  /// to convert without scientific notation and has more than \c Precision
587
  /// digits before the decimal place, it's printed accurately to the first
588
  /// digit past zero.  E.g., assuming 10 digits of precision:
589
  ///
590
  ///     98765432198.7654... => 98765432198.8
591
  ///      8765432198.7654... =>  8765432198.8
592
  ///       765432198.7654... =>   765432198.8
593
  ///        65432198.7654... =>    65432198.77
594
  ///         5432198.7654... =>     5432198.765
595
  std::string toString(unsigned Precision = DefaultPrecision) {
596
    return ScaledNumberBase::toString(Digits, Scale, Width, Precision);
597
  }
598
599
  /// Print a decimal representation.
600
  ///
601
  /// Print a string.  See toString for documentation.
602
  raw_ostream &print(raw_ostream &OS,
603
609
                     unsigned Precision = DefaultPrecision) const {
604
609
    return ScaledNumberBase::print(OS, Digits, Scale, Width, Precision);
605
609
  }
606
  void dump() const { return ScaledNumberBase::dump(Digits, Scale, Width); }
607
608
11
  ScaledNumber &operator+=(const ScaledNumber &X) {
609
11
    std::tie(Digits, Scale) =
610
11
        ScaledNumbers::getSum(Digits, Scale, X.Digits, X.Scale);
611
11
    // Check for exponent past MaxScale.
612
11
    if (Scale > ScaledNumbers::MaxScale)
613
0
      *this = getLargest();
614
11
    return *this;
615
11
  }
616
  ScaledNumber &operator-=(const ScaledNumber &X) {
617
    std::tie(Digits, Scale) =
618
        ScaledNumbers::getDifference(Digits, Scale, X.Digits, X.Scale);
619
    return *this;
620
  }
621
  ScaledNumber &operator*=(const ScaledNumber &X);
622
  ScaledNumber &operator/=(const ScaledNumber &X);
623
50.9M
  ScaledNumber &operator<<=(int16_t Shift) {
624
50.9M
    shiftLeft(Shift);
625
50.9M
    return *this;
626
50.9M
  }
627
  ScaledNumber &operator>>=(int16_t Shift) {
628
    shiftRight(Shift);
629
    return *this;
630
  }
631
632
private:
633
  void shiftLeft(int32_t Shift);
634
  void shiftRight(int32_t Shift);
635
636
  /// Adjust two floats to have matching exponents.
637
  ///
638
  /// Adjust \c this and \c X to have matching exponents.  Returns the new \c X
639
  /// by value.  Does nothing if \a isZero() for either.
640
  ///
641
  /// The value that compares smaller will lose precision, and possibly become
642
  /// \a isZero().
643
  ScaledNumber matchScales(ScaledNumber X) {
644
    ScaledNumbers::matchScales(Digits, Scale, X.Digits, X.Scale);
645
    return X;
646
  }
647
648
public:
649
  /// Scale a large number accurately.
650
  ///
651
  /// Scale N (multiply it by this).  Uses full precision multiplication, even
652
  /// if Width is smaller than 64, so information is not lost.
653
  uint64_t scale(uint64_t N) const;
654
  uint64_t scaleByInverse(uint64_t N) const {
655
    // TODO: implement directly, rather than relying on inverse.  Inverse is
656
    // expensive.
657
    return inverse().scale(N);
658
  }
659
  int64_t scale(int64_t N) const {
660
    std::pair<uint64_t, bool> Unsigned = splitSigned(N);
661
    return joinSigned(scale(Unsigned.first), Unsigned.second);
662
  }
663
  int64_t scaleByInverse(int64_t N) const {
664
    std::pair<uint64_t, bool> Unsigned = splitSigned(N);
665
    return joinSigned(scaleByInverse(Unsigned.first), Unsigned.second);
666
  }
667
668
53.1M
  int compare(const ScaledNumber &X) const {
669
53.1M
    return ScaledNumbers::compare(Digits, Scale, X.Digits, X.Scale);
670
53.1M
  }
671
53.1M
  int compareTo(uint64_t N) const {
672
53.1M
    return ScaledNumbers::compare<uint64_t>(Digits, Scale, N, 0);
673
53.1M
  }
674
26.5M
  int compareTo(int64_t N) const { return N < 0 ? 
10
: compareTo(uint64_t(N)); }
675
676
6.37M
  ScaledNumber &invert() { return *this = ScaledNumber::get(1) / *this; }
677
6.37M
  ScaledNumber inverse() const { return ScaledNumber(*this).invert(); }
678
679
private:
680
35.8M
  static ScaledNumber getProduct(DigitsType LHS, DigitsType RHS) {
681
35.8M
    return ScaledNumbers::getProduct(LHS, RHS);
682
35.8M
  }
683
10.7M
  static ScaledNumber getQuotient(DigitsType Dividend, DigitsType Divisor) {
684
10.7M
    return ScaledNumbers::getQuotient(Dividend, Divisor);
685
10.7M
  }
686
687
0
  static int countLeadingZerosWidth(DigitsType Digits) {
688
0
    if (Width == 64)
689
0
      return countLeadingZeros64(Digits);
690
0
    if (Width == 32)
691
0
      return countLeadingZeros32(Digits);
692
0
    return countLeadingZeros32(Digits) + Width - 32;
693
0
  }
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
6.37M
  static ScaledNumber adjustToWidth(uint64_t N, int32_t Shift) {
701
6.37M
    assert(Shift >= ScaledNumbers::MinScale && "Shift should be close to 0");
702
6.37M
    assert(Shift <= ScaledNumbers::MaxScale - 64 &&
703
6.37M
           "Shift should be close to 0");
704
6.37M
    auto Adjusted = ScaledNumbers::getAdjusted<DigitsT>(N, Shift);
705
6.37M
    return Adjusted;
706
6.37M
  }
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
44.5M
                                    const ScaledNumber<DigitsT> &R) {          \
721
44.5M
    return ScaledNumber<DigitsT>(L) base R;                                    \
722
44.5M
  }
llvm::ScaledNumber<unsigned long long> llvm::operator*<unsigned long long>(llvm::ScaledNumber<unsigned long long> const&, llvm::ScaledNumber<unsigned long long> const&)
Line
Count
Source
720
33.8M
                                    const ScaledNumber<DigitsT> &R) {          \
721
33.8M
    return ScaledNumber<DigitsT>(L) base R;                                    \
722
33.8M
  }
llvm::ScaledNumber<unsigned long long> llvm::operator/<unsigned long long>(llvm::ScaledNumber<unsigned long long> const&, llvm::ScaledNumber<unsigned long long> const&)
Line
Count
Source
720
10.7M
                                    const ScaledNumber<DigitsT> &R) {          \
721
10.7M
    return ScaledNumber<DigitsT>(L) base R;                                    \
722
10.7M
  }
723
SCALED_NUMBER_BOP(+, += )
724
SCALED_NUMBER_BOP(-, -= )
725
SCALED_NUMBER_BOP(*, *= )
726
SCALED_NUMBER_BOP(/, /= )
727
#undef SCALED_NUMBER_BOP
728
729
template <class DigitsT>
730
ScaledNumber<DigitsT> operator<<(const ScaledNumber<DigitsT> &L,
731
                                 int16_t Shift) {
732
  return ScaledNumber<DigitsT>(L) <<= Shift;
733
}
734
735
template <class DigitsT>
736
ScaledNumber<DigitsT> operator>>(const ScaledNumber<DigitsT> &L,
737
                                 int16_t Shift) {
738
  return ScaledNumber<DigitsT>(L) >>= Shift;
739
}
740
741
template <class DigitsT>
742
0
raw_ostream &operator<<(raw_ostream &OS, const ScaledNumber<DigitsT> &X) {
743
0
  return X.print(OS, 10);
744
0
}
745
746
#define SCALED_NUMBER_COMPARE_TO_TYPE(op, T1, T2)                              \
747
  template <class DigitsT>                                                     \
748
53.1M
  bool operator op(const ScaledNumber<DigitsT> &L, T1 R) {                     \
749
53.1M
    return L.compareTo(T2(R)) op 0;                                            \
750
53.1M
  }                                                                            \
bool llvm::operator<<unsigned long long>(llvm::ScaledNumber<unsigned long long> const&, int)
Line
Count
Source
748
26.5M
  bool operator op(const ScaledNumber<DigitsT> &L, T1 R) {                     \
749
26.5M
    return L.compareTo(T2(R)) op 0;                                            \
750
26.5M
  }                                                                            \
bool llvm::operator>=<unsigned long long>(llvm::ScaledNumber<unsigned long long> const&, unsigned long long)
Line
Count
Source
748
26.5M
  bool operator op(const ScaledNumber<DigitsT> &L, T1 R) {                     \
749
26.5M
    return L.compareTo(T2(R)) op 0;                                            \
750
26.5M
  }                                                                            \
751
  template <class DigitsT>                                                     \
752
  bool operator op(T1 L, const ScaledNumber<DigitsT> &R) {                     \
753
    return 0 op R.compareTo(T2(L));                                            \
754
  }
755
#define SCALED_NUMBER_COMPARE_TO(op)                                           \
756
  SCALED_NUMBER_COMPARE_TO_TYPE(op, uint64_t, uint64_t)                        \
757
  SCALED_NUMBER_COMPARE_TO_TYPE(op, uint32_t, uint64_t)                        \
758
  SCALED_NUMBER_COMPARE_TO_TYPE(op, int64_t, int64_t)                          \
759
  SCALED_NUMBER_COMPARE_TO_TYPE(op, int32_t, int64_t)
760
SCALED_NUMBER_COMPARE_TO(< )
761
SCALED_NUMBER_COMPARE_TO(> )
762
SCALED_NUMBER_COMPARE_TO(== )
763
SCALED_NUMBER_COMPARE_TO(!= )
764
SCALED_NUMBER_COMPARE_TO(<= )
765
SCALED_NUMBER_COMPARE_TO(>= )
766
#undef SCALED_NUMBER_COMPARE_TO
767
#undef SCALED_NUMBER_COMPARE_TO_TYPE
768
769
template <class DigitsT>
770
uint64_t ScaledNumber<DigitsT>::scale(uint64_t N) const {
771
  if (Width == 64 || N <= DigitsLimits::max())
772
    return (get(N) * *this).template toInt<uint64_t>();
773
774
  // Defer to the 64-bit version.
775
  return ScaledNumber<uint64_t>(Digits, Scale).scale(N);
776
}
777
778
template <class DigitsT>
779
template <class IntT>
780
26.5M
IntT ScaledNumber<DigitsT>::toInt() const {
781
26.5M
  typedef std::numeric_limits<IntT> Limits;
782
26.5M
  if (*this < 1)
783
67.3k
    return 0;
784
26.5M
  if (*this >= Limits::max())
785
6.08k
    return Limits::max();
786
26.5M
787
26.5M
  IntT N = Digits;
788
26.5M
  if (Scale > 0) {
789
3.83M
    assert(size_t(Scale) < sizeof(IntT) * 8);
790
3.83M
    return N << Scale;
791
3.83M
  }
792
22.6M
  if (Scale < 0) {
793
22.4M
    assert(size_t(-Scale) < sizeof(IntT) * 8);
794
22.4M
    return N >> -Scale;
795
22.4M
  }
796
222k
  return N;
797
222k
}
798
799
template <class DigitsT>
800
ScaledNumber<DigitsT> &ScaledNumber<DigitsT>::
801
35.8M
operator*=(const ScaledNumber &X) {
802
35.8M
  if (isZero())
803
2
    return *this;
804
35.8M
  if (X.isZero())
805
0
    return *this = X;
806
35.8M
807
35.8M
  // Save the exponents.
808
35.8M
  int32_t Scales = int32_t(Scale) + int32_t(X.Scale);
809
35.8M
810
35.8M
  // Get the raw product.
811
35.8M
  *this = getProduct(Digits, X.Digits);
812
35.8M
813
35.8M
  // Combine with exponents.
814
35.8M
  return *this <<= Scales;
815
35.8M
}
816
template <class DigitsT>
817
ScaledNumber<DigitsT> &ScaledNumber<DigitsT>::
818
10.7M
operator/=(const ScaledNumber &X) {
819
10.7M
  if (isZero())
820
0
    return *this;
821
10.7M
  if (X.isZero())
822
0
    return *this = getLargest();
823
10.7M
824
10.7M
  // Save the exponents.
825
10.7M
  int32_t Scales = int32_t(Scale) - int32_t(X.Scale);
826
10.7M
827
10.7M
  // Get the raw quotient.
828
10.7M
  *this = getQuotient(Digits, X.Digits);
829
10.7M
830
10.7M
  // Combine with exponents.
831
10.7M
  return *this <<= Scales;
832
10.7M
}
833
50.9M
template <class DigitsT> void ScaledNumber<DigitsT>::shiftLeft(int32_t Shift) {
834
50.9M
  if (!Shift || 
isZero()44.9M
)
835
5.96M
    return;
836
44.9M
  assert(Shift != INT32_MIN);
837
44.9M
  if (Shift < 0) {
838
31.8M
    shiftRight(-Shift);
839
31.8M
    return;
840
31.8M
  }
841
13.0M
842
13.0M
  // Shift as much as we can in the exponent.
843
13.0M
  int32_t ScaleShift = std::min(Shift, ScaledNumbers::MaxScale - Scale);
844
13.0M
  Scale += ScaleShift;
845
13.0M
  if (ScaleShift == Shift)
846
13.0M
    return;
847
18.4E
848
18.4E
  // Check this late, since it's rare.
849
18.4E
  if (isLargest())
850
0
    return;
851
18.4E
852
18.4E
  // Shift the digits themselves.
853
18.4E
  Shift -= ScaleShift;
854
18.4E
  if (Shift > countLeadingZerosWidth(Digits)) {
855
0
    // Saturate.
856
0
    *this = getLargest();
857
0
    return;
858
0
  }
859
18.4E
860
18.4E
  Digits <<= Shift;
861
18.4E
}
862
863
31.8M
template <class DigitsT> void ScaledNumber<DigitsT>::shiftRight(int32_t Shift) {
864
31.8M
  if (!Shift || isZero())
865
0
    return;
866
31.8M
  assert(Shift != INT32_MIN);
867
31.8M
  if (Shift < 0) {
868
0
    shiftLeft(-Shift);
869
0
    return;
870
0
  }
871
31.8M
872
31.8M
  // Shift as much as we can in the exponent.
873
31.8M
  int32_t ScaleShift = std::min(Shift, Scale - ScaledNumbers::MinScale);
874
31.8M
  Scale -= ScaleShift;
875
31.8M
  if (ScaleShift == Shift)
876
31.8M
    return;
877
0
878
0
  // Shift the digits themselves.
879
0
  Shift -= ScaleShift;
880
0
  if (Shift >= Width) {
881
0
    // Saturate.
882
0
    *this = getZero();
883
0
    return;
884
0
  }
885
0
886
0
  Digits >>= Shift;
887
0
}
888
889
890
} // end namespace llvm
891
892
#endif // LLVM_SUPPORT_SCALEDNUMBER_H