22 #ifndef LLVM_SUPPORT_SCALEDNUMBER_H 23 #define LLVM_SUPPORT_SCALEDNUMBER_H 34 namespace ScaledNumbers {
43 template <
class DigitsT>
inline int getWidth() {
return sizeof(DigitsT) * 8; }
52 template <
class DigitsT>
53 inline std::pair<DigitsT, int16_t>
getRounded(DigitsT Digits, int16_t Scale,
55 static_assert(!std::numeric_limits<DigitsT>::is_signed,
"expected unsigned");
60 return std::make_pair(DigitsT(1) << (getWidth<DigitsT>() - 1), Scale + 1);
61 return std::make_pair(Digits, Scale);
71 inline std::pair<uint64_t, int16_t>
getRounded64(uint64_t Digits, int16_t Scale,
79 template <
class DigitsT>
80 inline std::pair<DigitsT, int16_t>
getAdjusted(uint64_t Digits,
82 static_assert(!std::numeric_limits<DigitsT>::is_signed,
"expected unsigned");
84 const int Width = getWidth<DigitsT>();
86 return std::make_pair(Digits, Scale);
90 return getRounded<DigitsT>(Digits >> Shift, Scale + Shift,
91 Digits & (UINT64_C(1) << (Shift - 1)));
97 return getAdjusted<uint32_t>(Digits, Scale);
103 return getAdjusted<uint64_t>(Digits, Scale);
109 std::pair<uint64_t, int16_t>
multiply64(uint64_t LHS, uint64_t RHS);
114 template <
class DigitsT>
115 inline std::pair<DigitsT, int16_t>
getProduct(DigitsT LHS, DigitsT RHS) {
116 static_assert(!std::numeric_limits<DigitsT>::is_signed,
"expected unsigned");
118 if (getWidth<DigitsT>() <= 32 || (LHS <= UINT32_MAX && RHS <= UINT32_MAX))
119 return getAdjusted<DigitsT>(uint64_t(LHS) * RHS);
130 inline std::pair<uint64_t, int16_t>
getProduct64(uint64_t LHS, uint64_t RHS) {
139 std::pair<uint64_t, int16_t>
divide64(uint64_t Dividend, uint64_t Divisor);
153 template <
class DigitsT>
154 std::pair<DigitsT, int16_t>
getQuotient(DigitsT Dividend, DigitsT Divisor) {
155 static_assert(!std::numeric_limits<DigitsT>::is_signed,
"expected unsigned");
156 static_assert(
sizeof(DigitsT) == 4 ||
sizeof(DigitsT) == 8,
157 "expected 32-bit or 64-bit digits");
161 return std::make_pair(0, 0);
165 if (getWidth<DigitsT>() == 64)
188 template <
class DigitsT>
189 inline std::pair<int32_t, int>
getLgImpl(DigitsT Digits, int16_t Scale) {
190 static_assert(!std::numeric_limits<DigitsT>::is_signed,
"expected unsigned");
193 return std::make_pair(INT32_MIN, 0);
199 int32_t Floor = Scale + LocalFloor;
200 if (Digits == UINT64_C(1) << LocalFloor)
201 return std::make_pair(Floor, 0);
205 bool Round = Digits & UINT64_C(1) << (LocalFloor - 1);
206 return std::make_pair(Floor + Round, Round ? 1 : -1);
214 template <
class DigitsT> int32_t
getLg(DigitsT Digits, int16_t Scale) {
223 template <
class DigitsT> int32_t
getLgFloor(DigitsT Digits, int16_t Scale) {
225 return Lg.first - (Lg.second > 0);
233 template <
class DigitsT> int32_t
getLgCeiling(DigitsT Digits, int16_t Scale) {
235 return Lg.first + (Lg.second < 0);
245 int compareImpl(uint64_t L, uint64_t R,
int ScaleDiff);
251 template <
class DigitsT>
252 int compare(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale) {
253 static_assert(!std::numeric_limits<DigitsT>::is_signed,
"expected unsigned");
257 return RDigits ? -1 : 0;
265 return lgL < lgR ? -1 : 1;
269 return compareImpl(LDigits, RDigits, RScale - LScale);
271 return -
compareImpl(RDigits, LDigits, LScale - RScale);
286 template <
class DigitsT>
287 int16_t
matchScales(DigitsT &LDigits, int16_t &LScale, DigitsT &RDigits,
289 static_assert(!std::numeric_limits<DigitsT>::is_signed,
"expected unsigned");
293 return matchScales(RDigits, RScale, LDigits, LScale);
296 if (!RDigits || LScale == RScale)
300 int32_t ScaleDiff = int32_t(LScale) - RScale;
301 if (ScaleDiff >= 2 * getWidth<DigitsT>()) {
309 assert(ShiftL < getWidth<DigitsT>() &&
"can't shift more than width");
311 int32_t ShiftR = ScaleDiff - ShiftL;
312 if (ShiftR >= getWidth<DigitsT>()) {
323 assert(LScale == RScale &&
"scales should match");
332 template <
class DigitsT>
333 std::pair<DigitsT, int16_t>
getSum(DigitsT LDigits, int16_t LScale,
334 DigitsT RDigits, int16_t RScale) {
335 static_assert(!std::numeric_limits<DigitsT>::is_signed,
"expected unsigned");
339 assert(LScale < INT16_MAX &&
"scale too large");
340 assert(RScale < INT16_MAX &&
"scale too large");
343 int16_t Scale =
matchScales(LDigits, LScale, RDigits, RScale);
346 DigitsT Sum = LDigits + RDigits;
348 return std::make_pair(Sum, Scale);
351 DigitsT HighBit = DigitsT(1) << (getWidth<DigitsT>() - 1);
352 return std::make_pair(HighBit | Sum >> 1, Scale + 1);
358 return getSum(LDigits, LScale, RDigits, RScale);
362 inline std::pair<uint64_t, int16_t>
getSum64(uint64_t LDigits, int16_t LScale,
363 uint64_t RDigits, int16_t RScale) {
364 return getSum(LDigits, LScale, RDigits, RScale);
372 template <
class DigitsT>
374 DigitsT RDigits, int16_t RScale) {
375 static_assert(!std::numeric_limits<DigitsT>::is_signed,
"expected unsigned");
378 const DigitsT SavedRDigits = RDigits;
379 const int16_t SavedRScale = RScale;
383 if (LDigits <= RDigits)
384 return std::make_pair(0, 0);
385 if (RDigits || !SavedRDigits)
386 return std::make_pair(LDigits - RDigits, LScale);
391 const auto RLgFloor =
getLgFloor(SavedRDigits, SavedRScale);
392 if (!
compare(LDigits, LScale, DigitsT(1), RLgFloor + getWidth<DigitsT>()))
395 return std::make_pair(LDigits, LScale);
422 static const int DefaultPrecision = 10;
424 static void dump(uint64_t
D, int16_t
E,
int Width);
427 static std::string
toString(uint64_t
D, int16_t
E,
int Width,
431 static uint64_t
getHalf(uint64_t
N) {
return (N >> 1) + (N & 1); }
435 return std::make_pair(N,
false);
437 return std::make_pair(Unsigned,
true);
442 return IsNeg ? -int64_t(U) : int64_t(U);
495 static_assert(!std::numeric_limits<DigitsT>::is_signed,
496 "only unsigned floats supported");
501 typedef std::numeric_limits<DigitsType> DigitsLimits;
503 static const int Width =
sizeof(DigitsType) * 8;
504 static_assert(Width <= 64,
"invalid integer width for digits");
507 DigitsType Digits = 0;
514 : Digits(Digits), Scale(Scale) {}
518 : Digits(X.first), Scale(X.second) {}
528 return get(
N).invert();
541 template <
class IntT> IntT toInt()
const;
544 bool isLargest()
const {
return *
this == getLargest(); }
546 if (Scale > 0 || Scale <= -Width)
548 return Digits == DigitsType(1) << -Scale;
596 std::string
toString(
unsigned Precision = DefaultPrecision) {
604 unsigned Precision = DefaultPrecision)
const {
610 std::tie(Digits, Scale) =
614 *
this = getLargest();
618 std::tie(Digits, Scale) =
634 void shiftLeft(int32_t Shift);
654 uint64_t
scale(uint64_t
N)
const;
658 return inverse().scale(N);
661 std::pair<uint64_t, bool>
Unsigned = splitSigned(N);
662 return joinSigned(
scale(Unsigned.first), Unsigned.second);
665 std::pair<uint64_t, bool>
Unsigned = splitSigned(N);
666 return joinSigned(scaleByInverse(Unsigned.first), Unsigned.second);
673 return ScaledNumbers::compare<uint64_t>(Digits, Scale,
N, 0);
688 static int countLeadingZerosWidth(DigitsType Digits) {
690 return countLeadingZeros64(Digits);
692 return countLeadingZeros32(Digits);
693 return countLeadingZeros32(Digits) + Width - 32;
701 static ScaledNumber adjustToWidth(uint64_t N, int32_t Shift) {
704 "Shift should be close to 0");
705 auto Adjusted = ScaledNumbers::getAdjusted<DigitsT>(
N, Shift);
718 #define SCALED_NUMBER_BOP(op, base) \ 719 template <class DigitsT> \ 720 ScaledNumber<DigitsT> operator op(const ScaledNumber<DigitsT> &L, \ 721 const ScaledNumber<DigitsT> &R) { \ 722 return ScaledNumber<DigitsT>(L) base R; \ 728 #undef SCALED_NUMBER_BOP 730 template <
class DigitsT>
736 template <
class DigitsT>
742 template <
class DigitsT>
743 raw_ostream &operator<<(raw_ostream &OS, const ScaledNumber<DigitsT> &
X) {
744 return X.print(OS, 10);
747 #define SCALED_NUMBER_COMPARE_TO_TYPE(op, T1, T2) \ 748 template <class DigitsT> \ 749 bool operator op(const ScaledNumber<DigitsT> &L, T1 R) { \ 750 return L.compareTo(T2(R)) op 0; \ 752 template <class DigitsT> \ 753 bool operator op(T1 L, const ScaledNumber<DigitsT> &R) { \ 754 return 0 op R.compareTo(T2(L)); \ 756 #define SCALED_NUMBER_COMPARE_TO(op) \ 757 SCALED_NUMBER_COMPARE_TO_TYPE(op, uint64_t, uint64_t) \ 758 SCALED_NUMBER_COMPARE_TO_TYPE(op, uint32_t, uint64_t) \ 759 SCALED_NUMBER_COMPARE_TO_TYPE(op, int64_t, int64_t) \ 760 SCALED_NUMBER_COMPARE_TO_TYPE(op, int32_t, int64_t) 767 #undef SCALED_NUMBER_COMPARE_TO 768 #undef SCALED_NUMBER_COMPARE_TO_TYPE 770 template <
class DigitsT>
773 return (
get(N) * *
this).template toInt<uint64_t>();
779 template <
class DigitsT>
780 template <
class IntT>
782 typedef std::numeric_limits<IntT> Limits;
790 assert(
size_t(Scale) <
sizeof(IntT) * 8);
794 assert(
size_t(-Scale) <
sizeof(IntT) * 8);
800 template <
class DigitsT>
809 int32_t Scales = int32_t(Scale) + int32_t(X.Scale);
815 return *
this <<= Scales;
817 template <
class DigitsT>
823 return *
this = getLargest();
826 int32_t Scales = int32_t(Scale) - int32_t(X.Scale);
832 return *
this <<= Scales;
837 assert(Shift != INT32_MIN);
846 if (ScaleShift == Shift)
855 if (Shift > countLeadingZerosWidth(Digits)) {
857 *
this = getLargest();
867 assert(Shift != INT32_MIN);
876 if (ScaleShift == Shift)
881 if (Shift >= Width) {
892 static const bool value =
true;
897 #endif // LLVM_SUPPORT_SCALEDNUMBER_H
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
int32_t getLgFloor(DigitsT Digits, int16_t Scale)
Get the lg floor of a scaled number.
static uint64_t getHalf(uint64_t N)
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
std::pair< uint64_t, int16_t > getRounded64(uint64_t Digits, int16_t Scale, bool ShouldRound)
Convenience helper for 64-bit rounding.
This class represents lattice values for constants.
int getWidth()
Get the width of a number.
bool operator==(const ScaledNumber &X) const
static ScaledNumber getOne()
static lostFraction shiftRight(APFloatBase::integerPart *dst, unsigned int parts, unsigned int bits)
raw_ostream & print(raw_ostream &OS, unsigned Precision=DefaultPrecision) const
Print a decimal representation.
int compareTo(int64_t N) const
std::pair< uint64_t, int16_t > getAdjusted64(uint64_t Digits, int16_t Scale=0)
Convenience helper for adjusting to 64 bits.
static void dump(uint64_t D, int16_t E, int Width)
static int64_t joinSigned(uint64_t U, bool IsNeg)
std::size_t countLeadingZeros(T Val, ZeroBehavior ZB=ZB_Width)
Count number of 0's from the most significant bit to the least stopping at the first 1...
std::pair< DigitsT, int16_t > getProduct(DigitsT LHS, DigitsT RHS)
Multiply two 32-bit integers to create a 32-bit scaled number.
std::pair< DigitsT, int16_t > getAdjusted(uint64_t Digits, int16_t Scale=0)
Adjust a 64-bit scaled number down to the appropriate width.
std::pair< DigitsT, int16_t > getDifference(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale)
Get the difference of two scaled numbers.
const int32_t MaxScale
Maximum scale; same as APFloat for easy debug printing.
std::string toString(Error E)
Write all error messages (if any) in E to a string.
int32_t lg() const
The log base 2, rounded.
ScaledNumber & operator>>=(int16_t Shift)
std::pair< uint32_t, int16_t > getProduct32(uint32_t LHS, uint32_t RHS)
Convenience helper for 32-bit product.
int32_t lgFloor() const
The log base 2, rounded towards INT32_MIN.
static int countLeadingZeros64(uint64_t N)
std::pair< DigitsT, int16_t > getRounded(DigitsT Digits, int16_t Scale, bool ShouldRound)
Conditionally round up a scaled number.
std::pair< uint32_t, int16_t > getDifference32(uint32_t LDigits, int16_t LScale, uint32_t RDigits, int16_t RScale)
Convenience helper for 32-bit difference.
std::pair< uint32_t, int16_t > getAdjusted32(uint64_t Digits, int16_t Scale=0)
Convenience helper for adjusting to 32 bits.
bool operator>(const ScaledNumber &X) const
ScaledNumber & operator/=(const ScaledNumber &X)
bool operator<(const ScaledNumber &X) const
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
static std::string toString(uint64_t D, int16_t E, int Width, unsigned Precision)
ScaledNumber inverse() const
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
std::pair< uint64_t, int16_t > getProduct64(uint64_t LHS, uint64_t RHS)
Convenience helper for 64-bit product.
ScaledNumber & operator-=(const ScaledNumber &X)
DigitsType getDigits() const
int64_t scaleByInverse(int64_t N) const
ScaledNumber & operator+=(const ScaledNumber &X)
std::pair< DigitsT, int16_t > getSum(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale)
Get the sum of two scaled numbers.
std::string toString(unsigned Precision=DefaultPrecision)
Convert to a decimal representation in a string.
int16_t matchScales(DigitsT &LDigits, int16_t &LScale, DigitsT &RDigits, int16_t &RScale)
Match scales of two numbers.
static ScaledNumber getInverse(uint64_t N)
static uint64_t scale(uint64_t Num, uint32_t N, uint32_t D)
IntT toInt() const
Convert to the given integer type.
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
ScaledNumber & operator<<=(int16_t Shift)
Simple representation of a scaled number.
int compareTo(uint64_t N) const
int compare(const ScaledNumber &X) const
int compareImpl(uint64_t L, uint64_t R, int ScaleDiff)
Implementation for comparing scaled numbers.
bool operator!=(const ScaledNumber &X) const
ScaledNumber & operator*=(const ScaledNumber &X)
static std::pair< uint64_t, bool > splitSigned(int64_t N)
static ScaledNumber get(uint64_t N)
std::pair< DigitsT, int16_t > getQuotient(DigitsT Dividend, DigitsT Divisor)
Divide two 32-bit numbers to create a 32-bit scaled number.
isPodLike - This is a type trait that is used to determine whether a given type can be copied around ...
static ScaledNumber getLargest()
constexpr ScaledNumber(DigitsType Digits, int16_t Scale)
std::pair< uint64_t, int16_t > getDifference64(uint64_t LDigits, int16_t LScale, uint64_t RDigits, int16_t RScale)
Convenience helper for 64-bit difference.
std::pair< uint64_t, int16_t > multiply64(uint64_t LHS, uint64_t RHS)
Multiply two 64-bit integers to create a 64-bit scaled number.
int32_t getLgCeiling(DigitsT Digits, int16_t Scale)
Get the lg ceiling of a scaled number.
bool operator<=(const ScaledNumber &X) const
std::pair< uint64_t, int16_t > getQuotient64(uint64_t Dividend, uint64_t Divisor)
Convenience helper for 64-bit quotient.
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static int countLeadingZeros32(uint32_t N)
static ScaledNumber getZero()
#define SCALED_NUMBER_BOP(op, base)
uint64_t scale(uint64_t N) const
Scale a large number accurately.
std::pair< uint64_t, int16_t > getSum64(uint64_t LDigits, int16_t LScale, uint64_t RDigits, int16_t RScale)
Convenience helper for 64-bit sum.
std::pair< uint64_t, int16_t > divide64(uint64_t Dividend, uint64_t Divisor)
Divide two 64-bit integers to create a 64-bit scaled number.
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
std::pair< int32_t, int > getLgImpl(DigitsT Digits, int16_t Scale)
Implementation of getLg() and friends.
std::pair< uint32_t, int16_t > getQuotient32(uint32_t Dividend, uint32_t Divisor)
Convenience helper for 32-bit quotient.
std::pair< uint32_t, int16_t > getRounded32(uint32_t Digits, int16_t Scale, bool ShouldRound)
Convenience helper for 32-bit rounding.
int64_t scale(int64_t N) const
static ScaledNumber getFraction(DigitsType N, DigitsType D)
bool operator>=(const ScaledNumber &X) const
std::pair< uint32_t, int16_t > getSum32(uint32_t LDigits, int16_t LScale, uint32_t RDigits, int16_t RScale)
Convenience helper for 32-bit sum.
int compare(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale)
Compare two scaled numbers.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
int32_t lgCeiling() const
The log base 2, rounded towards INT32_MAX.
uint64_t scaleByInverse(uint64_t N) const
This class implements an extremely fast bulk output stream that can only output to a stream...
std::pair< uint32_t, int16_t > divide32(uint32_t Dividend, uint32_t Divisor)
Divide two 32-bit integers to create a 32-bit scaled number.
#define SCALED_NUMBER_COMPARE_TO(op)
int32_t getLg(DigitsT Digits, int16_t Scale)
Get the lg (rounded) of a scaled number.
ScaledNumber< DigitsT > operator>>(const ScaledNumber< DigitsT > &L, int16_t Shift)
const int32_t MinScale
Maximum scale; same as APFloat for easy debug printing.
static raw_ostream & print(raw_ostream &OS, uint64_t D, int16_t E, int Width, unsigned Precision)