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