Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Support/ScaledNumber.cpp
Line
Count
Source (jump to first uncovered line)
1
//==- lib/Support/ScaledNumber.cpp - 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
// Implementation of some scaled number algorithms.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#include "llvm/Support/ScaledNumber.h"
14
#include "llvm/ADT/APFloat.h"
15
#include "llvm/ADT/ArrayRef.h"
16
#include "llvm/Support/Debug.h"
17
#include "llvm/Support/raw_ostream.h"
18
19
using namespace llvm;
20
using namespace llvm::ScaledNumbers;
21
22
std::pair<uint64_t, int16_t> ScaledNumbers::multiply64(uint64_t LHS,
23
31.8M
                                                       uint64_t RHS) {
24
31.8M
  // Separate into two 32-bit digits (U.L).
25
127M
  auto getU = [](uint64_t N) { return N >> 32; };
26
127M
  auto getL = [](uint64_t N) { return N & UINT32_MAX; };
27
31.8M
  uint64_t UL = getU(LHS), LL = getL(LHS), UR = getU(RHS), LR = getL(RHS);
28
31.8M
29
31.8M
  // Compute cross products.
30
31.8M
  uint64_t P1 = UL * UR, P2 = UL * LR, P3 = LL * UR, P4 = LL * LR;
31
31.8M
32
31.8M
  // Sum into two 64-bit digits.
33
31.8M
  uint64_t Upper = P1, Lower = P4;
34
63.7M
  auto addWithCarry = [&](uint64_t N) {
35
63.7M
    uint64_t NewLower = Lower + (getL(N) << 32);
36
63.7M
    Upper += getU(N) + (NewLower < Lower);
37
63.7M
    Lower = NewLower;
38
63.7M
  };
39
31.8M
  addWithCarry(P2);
40
31.8M
  addWithCarry(P3);
41
31.8M
42
31.8M
  // Check whether the upper digit is empty.
43
31.8M
  if (!Upper)
44
7.33M
    return std::make_pair(Lower, 0);
45
24.5M
46
24.5M
  // Shift as little as possible to maximize precision.
47
24.5M
  unsigned LeadingZeros = countLeadingZeros(Upper);
48
24.5M
  int Shift = 64 - LeadingZeros;
49
24.5M
  if (LeadingZeros)
50
18.9M
    Upper = Upper << LeadingZeros | Lower >> Shift;
51
24.5M
  return getRounded(Upper, Shift,
52
24.5M
                    Shift && (Lower & UINT64_C(1) << (Shift - 1)));
53
24.5M
}
54
55
4.04M
static uint64_t getHalf(uint64_t N) { return (N >> 1) + (N & 1); }
56
57
std::pair<uint32_t, int16_t> ScaledNumbers::divide32(uint32_t Dividend,
58
11
                                                     uint32_t Divisor) {
59
11
  assert(Dividend && "expected non-zero dividend");
60
11
  assert(Divisor && "expected non-zero divisor");
61
11
62
11
  // Use 64-bit math and canonicalize the dividend to gain precision.
63
11
  uint64_t Dividend64 = Dividend;
64
11
  int Shift = 0;
65
11
  if (int Zeros = countLeadingZeros(Dividend64)) {
66
11
    Shift -= Zeros;
67
11
    Dividend64 <<= Zeros;
68
11
  }
69
11
  uint64_t Quotient = Dividend64 / Divisor;
70
11
  uint64_t Remainder = Dividend64 % Divisor;
71
11
72
11
  // If Quotient needs to be shifted, leave the rounding to getAdjusted().
73
11
  if (Quotient > UINT32_MAX)
74
11
    return getAdjusted<uint32_t>(Quotient, Shift);
75
0
76
0
  // Round based on the value of the next bit.
77
0
  return getRounded<uint32_t>(Quotient, Shift, Remainder >= getHalf(Divisor));
78
0
}
79
80
std::pair<uint64_t, int16_t> ScaledNumbers::divide64(uint64_t Dividend,
81
10.7M
                                                     uint64_t Divisor) {
82
10.7M
  assert(Dividend && "expected non-zero dividend");
83
10.7M
  assert(Divisor && "expected non-zero divisor");
84
10.7M
85
10.7M
  // Minimize size of divisor.
86
10.7M
  int Shift = 0;
87
10.7M
  if (int Zeros = countTrailingZeros(Divisor)) {
88
2.23M
    Shift -= Zeros;
89
2.23M
    Divisor >>= Zeros;
90
2.23M
  }
91
10.7M
92
10.7M
  // Check for powers of two.
93
10.7M
  if (Divisor == 1)
94
6.66M
    return std::make_pair(Dividend, Shift);
95
4.04M
96
4.04M
  // Maximize size of dividend.
97
4.04M
  if (int Zeros = countLeadingZeros(Dividend)) {
98
3.62M
    Shift -= Zeros;
99
3.62M
    Dividend <<= Zeros;
100
3.62M
  }
101
4.04M
102
4.04M
  // Start with the result of a divide.
103
4.04M
  uint64_t Quotient = Dividend / Divisor;
104
4.04M
  Dividend %= Divisor;
105
4.04M
106
4.04M
  // Continue building the quotient with long division.
107
177M
  while (!(Quotient >> 63) && 
Dividend173M
) {
108
173M
    // Shift Dividend and check for overflow.
109
173M
    bool IsOverflow = Dividend >> 63;
110
173M
    Dividend <<= 1;
111
173M
    --Shift;
112
173M
113
173M
    // Get the next bit of Quotient.
114
173M
    Quotient <<= 1;
115
173M
    if (IsOverflow || 
Divisor <= Dividend170M
) {
116
122M
      Quotient |= 1;
117
122M
      Dividend -= Divisor;
118
122M
    }
119
173M
  }
120
4.04M
121
4.04M
  return getRounded(Quotient, Shift, Dividend >= getHalf(Divisor));
122
4.04M
}
123
124
5.53M
int ScaledNumbers::compareImpl(uint64_t L, uint64_t R, int ScaleDiff) {
125
5.53M
  assert(ScaleDiff >= 0 && "wrong argument order");
126
5.53M
  assert(ScaleDiff < 64 && "numbers too far apart");
127
5.53M
128
5.53M
  uint64_t L_adjusted = L >> ScaleDiff;
129
5.53M
  if (L_adjusted < R)
130
1.71M
    return -1;
131
3.82M
  if (L_adjusted > R)
132
1.32M
    return 1;
133
2.50M
134
2.50M
  return L > L_adjusted << ScaleDiff ? 
1167k
:
02.33M
;
135
2.50M
}
136
137
3.98k
static void appendDigit(std::string &Str, unsigned D) {
138
3.98k
  assert(D < 10);
139
3.98k
  Str += '0' + D % 10;
140
3.98k
}
141
142
416
static void appendNumber(std::string &Str, uint64_t N) {
143
1.19k
  while (N) {
144
778
    appendDigit(Str, N % 10);
145
778
    N /= 10;
146
778
  }
147
416
}
148
149
453
static bool doesRoundUp(char Digit) {
150
453
  switch (Digit) {
151
453
  case '5':
152
318
  case '6':
153
318
  case '7':
154
318
  case '8':
155
318
  case '9':
156
318
    return true;
157
318
  default:
158
135
    return false;
159
453
  }
160
453
}
161
162
0
static std::string toStringAPFloat(uint64_t D, int E, unsigned Precision) {
163
0
  assert(E >= ScaledNumbers::MinScale);
164
0
  assert(E <= ScaledNumbers::MaxScale);
165
0
166
0
  // Find a new E, but don't let it increase past MaxScale.
167
0
  int LeadingZeros = ScaledNumberBase::countLeadingZeros64(D);
168
0
  int NewE = std::min(ScaledNumbers::MaxScale, E + 63 - LeadingZeros);
169
0
  int Shift = 63 - (NewE - E);
170
0
  assert(Shift <= LeadingZeros);
171
0
  assert(Shift == LeadingZeros || NewE == ScaledNumbers::MaxScale);
172
0
  assert(Shift >= 0 && Shift < 64 && "undefined behavior");
173
0
  D <<= Shift;
174
0
  E = NewE;
175
0
176
0
  // Check for a denormal.
177
0
  unsigned AdjustedE = E + 16383;
178
0
  if (!(D >> 63)) {
179
0
    assert(E == ScaledNumbers::MaxScale);
180
0
    AdjustedE = 0;
181
0
  }
182
0
183
0
  // Build the float and print it.
184
0
  uint64_t RawBits[2] = {D, AdjustedE};
185
0
  APFloat Float(APFloat::x87DoubleExtended(), APInt(80, RawBits));
186
0
  SmallVector<char, 24> Chars;
187
0
  Float.toString(Chars, Precision, 0);
188
0
  return std::string(Chars.begin(), Chars.end());
189
0
}
190
191
463
static std::string stripTrailingZeros(const std::string &Float) {
192
463
  size_t NonZero = Float.find_last_not_of('0');
193
463
  assert(NonZero != std::string::npos && "no . in floating point string");
194
463
195
463
  if (Float[NonZero] == '.')
196
150
    ++NonZero;
197
463
198
463
  return Float.substr(0, NonZero + 1);
199
463
}
200
201
std::string ScaledNumberBase::toString(uint64_t D, int16_t E, int Width,
202
609
                                       unsigned Precision) {
203
609
  if (!D)
204
0
    return "0.0";
205
609
206
609
  // Canonicalize exponent and digits.
207
609
  uint64_t Above0 = 0;
208
609
  uint64_t Below0 = 0;
209
609
  uint64_t Extra = 0;
210
609
  int ExtraShift = 0;
211
609
  if (E == 0) {
212
142
    Above0 = D;
213
467
  } else if (E > 0) {
214
2
    if (int Shift = std::min(int16_t(countLeadingZeros64(D)), E)) {
215
2
      D <<= Shift;
216
2
      E -= Shift;
217
2
218
2
      if (!E)
219
2
        Above0 = D;
220
2
    }
221
465
  } else if (E > -64) {
222
272
    Above0 = D >> -E;
223
272
    Below0 = D << (64 + E);
224
272
  } else 
if (193
E == -64193
) {
225
95
    // Special case: shift by 64 bits is undefined behavior.
226
95
    Below0 = D;
227
98
  } else if (E > -120) {
228
98
    Below0 = D >> (-E - 64);
229
98
    Extra = D << (128 + E);
230
98
    ExtraShift = -64 - E;
231
98
  }
232
609
233
609
  // Fall back on APFloat for very small and very large numbers.
234
609
  if (!Above0 && 
!Below0193
)
235
0
    return toStringAPFloat(D, E, Precision);
236
609
237
609
  // Append the digits before the decimal.
238
609
  std::string Str;
239
609
  size_t DigitsOut = 0;
240
609
  if (Above0) {
241
416
    appendNumber(Str, Above0);
242
416
    DigitsOut = Str.size();
243
416
  } else
244
193
    appendDigit(Str, 0);
245
609
  std::reverse(Str.begin(), Str.end());
246
609
247
609
  // Return early if there's nothing after the decimal.
248
609
  if (!Below0)
249
146
    return Str + ".0";
250
463
251
463
  // Append the decimal and beyond.
252
463
  Str += '.';
253
463
  uint64_t Error = UINT64_C(1) << (64 - Width);
254
463
255
463
  // We need to shift Below0 to the right to make space for calculating
256
463
  // digits.  Save the precision we're losing in Extra.
257
463
  Extra = (Below0 & 0xf) << 56 | (Extra >> 8);
258
463
  Below0 >>= 4;
259
463
  size_t SinceDot = 0;
260
463
  size_t AfterDot = Str.size();
261
3.01k
  do {
262
3.01k
    if (ExtraShift) {
263
1.25k
      --ExtraShift;
264
1.25k
      Error *= 5;
265
1.25k
    } else
266
1.76k
      Error *= 10;
267
3.01k
268
3.01k
    Below0 *= 10;
269
3.01k
    Extra *= 10;
270
3.01k
    Below0 += (Extra >> 60);
271
3.01k
    Extra = Extra & (UINT64_MAX >> 4);
272
3.01k
    appendDigit(Str, Below0 >> 60);
273
3.01k
    Below0 = Below0 & (UINT64_MAX >> 4);
274
3.01k
    if (DigitsOut || 
Str.back() != '0'1.01k
)
275
2.19k
      ++DigitsOut;
276
3.01k
    ++SinceDot;
277
3.01k
  } while (Error && (Below0 << 4 | Extra >> 60) >= Error / 2 &&
278
3.01k
           
(3.00k
!Precision3.00k
||
DigitsOut <= Precision3.00k
||
SinceDot < 2480
));
279
463
280
463
  // Return early for maximum precision.
281
463
  if (!Precision || DigitsOut <= Precision)
282
10
    return stripTrailingZeros(Str);
283
453
284
453
  // Find where to truncate.
285
453
  size_t Truncate =
286
453
      std::max(Str.size() - (DigitsOut - Precision), AfterDot + 1);
287
453
288
453
  // Check if there's anything to truncate.
289
453
  if (Truncate >= Str.size())
290
0
    return stripTrailingZeros(Str);
291
453
292
453
  bool Carry = doesRoundUp(Str[Truncate]);
293
453
  if (!Carry)
294
135
    return stripTrailingZeros(Str.substr(0, Truncate));
295
318
296
318
  // Round with the first truncated digit.
297
318
  for (std::string::reverse_iterator I(Str.begin() + Truncate), E = Str.rend();
298
1.06k
       I != E; 
++I744
) {
299
1.05k
    if (*I == '.')
300
114
      continue;
301
940
    if (*I == '9') {
302
630
      *I = '0';
303
630
      continue;
304
630
    }
305
310
306
310
    ++*I;
307
310
    Carry = false;
308
310
    break;
309
310
  }
310
318
311
318
  // Add "1" in front if we still need to carry.
312
318
  return stripTrailingZeros(std::string(Carry, '1') + Str.substr(0, Truncate));
313
318
}
314
315
raw_ostream &ScaledNumberBase::print(raw_ostream &OS, uint64_t D, int16_t E,
316
609
                                     int Width, unsigned Precision) {
317
609
  return OS << toString(D, E, Width, Precision);
318
609
}
319
320
0
void ScaledNumberBase::dump(uint64_t D, int16_t E, int Width) {
321
0
  print(dbgs(), D, E, Width, 0) << "[" << Width << ":" << D << "*2^" << E
322
0
                                << "]";
323
0
}