]>
git.proxmox.com Git - rustc.git/blob - src/llvm/lib/Support/ScaledNumber.cpp
1 //==- lib/Support/ScaledNumber.cpp - Support for scaled numbers -*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Implementation of some scaled number algorithms.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/Support/ScaledNumber.h"
15 #include "llvm/ADT/APFloat.h"
16 #include "llvm/Support/Debug.h"
19 using namespace llvm::ScaledNumbers
;
21 std::pair
<uint64_t, int16_t> ScaledNumbers::multiply64(uint64_t LHS
,
23 // Separate into two 32-bit digits (U.L).
24 auto getU
= [](uint64_t N
) { return N
>> 32; };
25 auto getL
= [](uint64_t N
) { return N
& UINT32_MAX
; };
26 uint64_t UL
= getU(LHS
), LL
= getL(LHS
), UR
= getU(RHS
), LR
= getL(RHS
);
28 // Compute cross products.
29 uint64_t P1
= UL
* UR
, P2
= UL
* LR
, P3
= LL
* UR
, P4
= LL
* LR
;
31 // Sum into two 64-bit digits.
32 uint64_t Upper
= P1
, Lower
= P4
;
33 auto addWithCarry
= [&](uint64_t N
) {
34 uint64_t NewLower
= Lower
+ (getL(N
) << 32);
35 Upper
+= getU(N
) + (NewLower
< Lower
);
41 // Check whether the upper digit is empty.
43 return std::make_pair(Lower
, 0);
45 // Shift as little as possible to maximize precision.
46 unsigned LeadingZeros
= countLeadingZeros(Upper
);
47 int Shift
= 64 - LeadingZeros
;
49 Upper
= Upper
<< LeadingZeros
| Lower
>> Shift
;
50 return getRounded(Upper
, Shift
,
51 Shift
&& (Lower
& UINT64_C(1) << (Shift
- 1)));
54 static uint64_t getHalf(uint64_t N
) { return (N
>> 1) + (N
& 1); }
56 std::pair
<uint32_t, int16_t> ScaledNumbers::divide32(uint32_t Dividend
,
58 assert(Dividend
&& "expected non-zero dividend");
59 assert(Divisor
&& "expected non-zero divisor");
61 // Use 64-bit math and canonicalize the dividend to gain precision.
62 uint64_t Dividend64
= Dividend
;
64 if (int Zeros
= countLeadingZeros(Dividend64
)) {
68 uint64_t Quotient
= Dividend64
/ Divisor
;
69 uint64_t Remainder
= Dividend64
% Divisor
;
71 // If Quotient needs to be shifted, leave the rounding to getAdjusted().
72 if (Quotient
> UINT32_MAX
)
73 return getAdjusted
<uint32_t>(Quotient
, Shift
);
75 // Round based on the value of the next bit.
76 return getRounded
<uint32_t>(Quotient
, Shift
, Remainder
>= getHalf(Divisor
));
79 std::pair
<uint64_t, int16_t> ScaledNumbers::divide64(uint64_t Dividend
,
81 assert(Dividend
&& "expected non-zero dividend");
82 assert(Divisor
&& "expected non-zero divisor");
84 // Minimize size of divisor.
86 if (int Zeros
= countTrailingZeros(Divisor
)) {
91 // Check for powers of two.
93 return std::make_pair(Dividend
, Shift
);
95 // Maximize size of dividend.
96 if (int Zeros
= countLeadingZeros(Dividend
)) {
101 // Start with the result of a divide.
102 uint64_t Quotient
= Dividend
/ Divisor
;
105 // Continue building the quotient with long division.
106 while (!(Quotient
>> 63) && Dividend
) {
107 // Shift Dividend and check for overflow.
108 bool IsOverflow
= Dividend
>> 63;
112 // Get the next bit of Quotient.
114 if (IsOverflow
|| Divisor
<= Dividend
) {
120 return getRounded(Quotient
, Shift
, Dividend
>= getHalf(Divisor
));
123 int ScaledNumbers::compareImpl(uint64_t L
, uint64_t R
, int ScaleDiff
) {
124 assert(ScaleDiff
>= 0 && "wrong argument order");
125 assert(ScaleDiff
< 64 && "numbers too far apart");
127 uint64_t L_adjusted
= L
>> ScaleDiff
;
133 return L
> L_adjusted
<< ScaleDiff
? 1 : 0;
136 static void appendDigit(std::string
&Str
, unsigned D
) {
141 static void appendNumber(std::string
&Str
, uint64_t N
) {
143 appendDigit(Str
, N
% 10);
148 static bool doesRoundUp(char Digit
) {
161 static std::string
toStringAPFloat(uint64_t D
, int E
, unsigned Precision
) {
162 assert(E
>= ScaledNumbers::MinScale
);
163 assert(E
<= ScaledNumbers::MaxScale
);
165 // Find a new E, but don't let it increase past MaxScale.
166 int LeadingZeros
= ScaledNumberBase::countLeadingZeros64(D
);
167 int NewE
= std::min(ScaledNumbers::MaxScale
, E
+ 63 - LeadingZeros
);
168 int Shift
= 63 - (NewE
- E
);
169 assert(Shift
<= LeadingZeros
);
170 assert(Shift
== LeadingZeros
|| NewE
== ScaledNumbers::MaxScale
);
171 assert(Shift
>= 0 && Shift
< 64 && "undefined behavior");
175 // Check for a denormal.
176 unsigned AdjustedE
= E
+ 16383;
178 assert(E
== ScaledNumbers::MaxScale
);
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());
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");
194 if (Float
[NonZero
] == '.')
197 return Float
.substr(0, NonZero
+ 1);
200 std::string
ScaledNumberBase::toString(uint64_t D
, int16_t E
, int Width
,
201 unsigned Precision
) {
205 // Canonicalize exponent and digits.
213 if (int Shift
= std::min(int16_t(countLeadingZeros64(D
)), E
)) {
220 } else if (E
> -64) {
222 Below0
= D
<< (64 + E
);
223 } else if (E
== -64) {
224 // Special case: shift by 64 bits is undefined behavior.
226 } else if (E
> -120) {
227 Below0
= D
>> (-E
- 64);
228 Extra
= D
<< (128 + E
);
229 ExtraShift
= -64 - E
;
232 // Fall back on APFloat for very small and very large numbers.
233 if (!Above0
&& !Below0
)
234 return toStringAPFloat(D
, E
, Precision
);
236 // Append the digits before the decimal.
238 size_t DigitsOut
= 0;
240 appendNumber(Str
, Above0
);
241 DigitsOut
= Str
.size();
244 std::reverse(Str
.begin(), Str
.end());
246 // Return early if there's nothing after the decimal.
250 // Append the decimal and beyond.
252 uint64_t Error
= UINT64_C(1) << (64 - Width
);
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);
259 size_t AfterDot
= Str
.size();
269 Below0
+= (Extra
>> 60);
270 Extra
= Extra
& (UINT64_MAX
>> 4);
271 appendDigit(Str
, Below0
>> 60);
272 Below0
= Below0
& (UINT64_MAX
>> 4);
273 if (DigitsOut
|| Str
.back() != '0')
276 } while (Error
&& (Below0
<< 4 | Extra
>> 60) >= Error
/ 2 &&
277 (!Precision
|| DigitsOut
<= Precision
|| SinceDot
< 2));
279 // Return early for maximum precision.
280 if (!Precision
|| DigitsOut
<= Precision
)
281 return stripTrailingZeros(Str
);
283 // Find where to truncate.
285 std::max(Str
.size() - (DigitsOut
- Precision
), AfterDot
+ 1);
287 // Check if there's anything to truncate.
288 if (Truncate
>= Str
.size())
289 return stripTrailingZeros(Str
);
291 bool Carry
= doesRoundUp(Str
[Truncate
]);
293 return stripTrailingZeros(Str
.substr(0, Truncate
));
295 // Round with the first truncated digit.
296 for (std::string::reverse_iterator
I(Str
.begin() + Truncate
), E
= Str
.rend();
310 // Add "1" in front if we still need to carry.
311 return stripTrailingZeros(std::string(Carry
, '1') + Str
.substr(0, Truncate
));
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
);
319 void ScaledNumberBase::dump(uint64_t D
, int16_t E
, int Width
) {
320 print(dbgs(), D
, E
, Width
, 0) << "[" << Width
<< ":" << D
<< "*2^" << E