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