21#ifndef LLVM_SUPPORT_SCALEDNUMBER_H
22#define LLVM_SUPPORT_SCALEDNUMBER_H
33namespace ScaledNumbers {
42template <
class DigitsT>
inline int getWidth() {
return sizeof(DigitsT) * 8; }
51template <
class DigitsT>
52inline std::pair<DigitsT, int16_t>
getRounded(DigitsT Digits, int16_t Scale,
54 static_assert(!std::numeric_limits<DigitsT>::is_signed,
"expected unsigned");
59 return std::make_pair(DigitsT(1) << (getWidth<DigitsT>() - 1), Scale + 1);
60 return std::make_pair(Digits, Scale);
78template <
class DigitsT>
81 static_assert(!std::numeric_limits<DigitsT>::is_signed,
"expected unsigned");
83 const int Width = getWidth<DigitsT>();
84 if (Width == 64 || Digits <= std::numeric_limits<DigitsT>::max())
85 return std::make_pair(Digits, Scale);
89 return getRounded<DigitsT>(Digits >> Shift, Scale + Shift,
90 Digits & (UINT64_C(1) << (Shift - 1)));
96 return getAdjusted<uint32_t>(Digits, Scale);
102 return getAdjusted<uint64_t>(Digits, Scale);
113template <
class DigitsT>
115 static_assert(!std::numeric_limits<DigitsT>::is_signed,
"expected unsigned");
117 if (getWidth<DigitsT>() <= 32 || (
LHS <= UINT32_MAX &&
RHS <= UINT32_MAX))
152template <
class DigitsT>
153std::pair<DigitsT, int16_t>
getQuotient(DigitsT Dividend, DigitsT Divisor) {
154 static_assert(!std::numeric_limits<DigitsT>::is_signed,
"expected unsigned");
155 static_assert(
sizeof(DigitsT) == 4 ||
sizeof(DigitsT) == 8,
156 "expected 32-bit or 64-bit digits");
160 return std::make_pair(0, 0);
162 return std::make_pair(std::numeric_limits<DigitsT>::max(),
MaxScale);
164 if (getWidth<DigitsT>() == 64)
187template <
class DigitsT>
188inline std::pair<int32_t, int>
getLgImpl(DigitsT Digits, int16_t Scale) {
189 static_assert(!std::numeric_limits<DigitsT>::is_signed,
"expected unsigned");
192 return std::make_pair(INT32_MIN, 0);
195 static_assert(
sizeof(Digits) <=
sizeof(
uint64_t));
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);
214template <
class DigitsT> int32_t
getLg(DigitsT Digits, int16_t Scale) {
223template <
class DigitsT> int32_t
getLgFloor(DigitsT Digits, int16_t Scale) {
225 return Lg.first - (Lg.second > 0);
233template <
class DigitsT> int32_t
getLgCeiling(DigitsT Digits, int16_t Scale) {
235 return Lg.first + (Lg.second < 0);
251template <
class DigitsT>
252int 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);
286template <
class DigitsT>
287int16_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");
332template <
class DigitsT>
333std::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);
364 return getSum(LDigits, LScale, RDigits, RScale);
372template <
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>()))
393 return std::make_pair(std::numeric_limits<DigitsT>::max(), RLgFloor);
395 return std::make_pair(LDigits, LScale);
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 constexpr int Width =
sizeof(
DigitsType) * 8;
504 static_assert(Width <= 64,
"invalid integer width for digits");
514 : Digits(Digits), Scale(Scale) {}
518 : Digits(
X.first), Scale(
X.second) {}
531 return getQuotient(
N,
D);
541 template <
class IntT> IntT
toInt()
const;
546 if (Scale > 0 || Scale <= -Width)
610 std::tie(Digits, Scale) =
618 std::tie(Digits, Scale) =
634 void shiftLeft(int32_t Shift);
635 void shiftRight(int32_t Shift);
673 return ScaledNumbers::compare<uint64_t>(Digits, Scale,
N, 0);
688 static int countLeadingZerosWidth(
DigitsType Digits) {
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
730template <
class DigitsT>
731ScaledNumber<DigitsT>
operator<<(
const ScaledNumber<DigitsT> &L,
733 return ScaledNumber<DigitsT>(L) <<= Shift;
736template <
class DigitsT>
742template <
class DigitsT>
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
770template <
class DigitsT>
772 if (Width == 64 ||
N <= DigitsLimits::max())
773 return (
get(
N) * *
this).template toInt<uint64_t>();
779template <
class DigitsT>
782 typedef std::numeric_limits<IntT> Limits;
785 if (*
this >= Limits::max())
786 return Limits::max();
790 assert(
size_t(Scale) <
sizeof(IntT) * 8);
794 assert(
size_t(-Scale) <
sizeof(IntT) * 8);
800template <
class DigitsT>
809 int32_t Scales = int32_t(Scale) + int32_t(
X.Scale);
812 *
this = getProduct(Digits,
X.Digits);
815 return *
this <<= Scales;
817template <
class DigitsT>
823 return *
this = getLargest();
826 int32_t Scales = int32_t(Scale) - int32_t(
X.Scale);
829 *
this = getQuotient(Digits,
X.Digits);
832 return *
this <<= Scales;
837 assert(Shift != INT32_MIN);
846 if (ScaleShift == Shift)
855 if (Shift > countLeadingZerosWidth(Digits)) {
857 *
this = getLargest();
864template <
class DigitsT>
void ScaledNumber<DigitsT>::shiftRight(int32_t Shift) {
867 assert(Shift != INT32_MIN);
876 if (ScaleShift == Shift)
881 if (Shift >= Width) {
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
#define SCALED_NUMBER_BOP(op, base)
#define SCALED_NUMBER_COMPARE_TO(op)
static int countLeadingZeros64(uint64_t N)
static int countLeadingZeros32(uint32_t N)
static constexpr int DefaultPrecision
static int64_t joinSigned(uint64_t U, bool IsNeg)
static raw_ostream & print(raw_ostream &OS, uint64_t D, int16_t E, int Width, unsigned Precision)
static std::string toString(uint64_t D, int16_t E, int Width, unsigned Precision)
static void dump(uint64_t D, int16_t E, int Width)
static uint64_t getHalf(uint64_t N)
static std::pair< uint64_t, bool > splitSigned(int64_t N)
Simple representation of a scaled number.
bool operator!=(const ScaledNumber &X) const
raw_ostream & print(raw_ostream &OS, unsigned Precision=DefaultPrecision) const
Print a decimal representation.
ScaledNumber & operator*=(const ScaledNumber &X)
static ScaledNumber getLargest()
ScaledNumber & operator/=(const ScaledNumber &X)
ScaledNumber & operator<<=(int16_t Shift)
int32_t lgFloor() const
The log base 2, rounded towards INT32_MIN.
ScaledNumber inverse() const
bool operator<=(const ScaledNumber &X) const
ScaledNumber & operator+=(const ScaledNumber &X)
bool operator==(const ScaledNumber &X) const
int compare(const ScaledNumber &X) const
std::string toString(unsigned Precision=DefaultPrecision)
Convert to a decimal representation in a string.
static ScaledNumber get(uint64_t N)
static ScaledNumber getZero()
DigitsType getDigits() const
static ScaledNumber getOne()
uint64_t scale(uint64_t N) const
Scale a large number accurately.
bool operator>(const ScaledNumber &X) const
ScaledNumber & operator>>=(int16_t Shift)
static ScaledNumber getFraction(DigitsType N, DigitsType D)
int64_t scaleByInverse(int64_t N) const
constexpr ScaledNumber(DigitsType Digits, int16_t Scale)
int32_t lgCeiling() const
The log base 2, rounded towards INT32_MAX.
uint64_t scaleByInverse(uint64_t N) const
bool operator<(const ScaledNumber &X) const
bool operator>=(const ScaledNumber &X) const
int32_t lg() const
The log base 2, rounded.
int compareTo(uint64_t N) const
static ScaledNumber getInverse(uint64_t N)
IntT toInt() const
Convert to the given integer type.
ScaledNumber & operator-=(const ScaledNumber &X)
int64_t scale(int64_t N) const
int compareTo(int64_t N) const
This class implements an extremely fast bulk output stream that can only output to a stream.
int compare(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale)
Compare two scaled numbers.
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.
int32_t getLgFloor(DigitsT Digits, int16_t Scale)
Get the lg floor of a scaled number.
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.
std::pair< DigitsT, int16_t > getSum(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale)
Get the sum of two scaled numbers.
std::pair< uint32_t, int16_t > getAdjusted32(uint64_t Digits, int16_t Scale=0)
Convenience helper for adjusting to 32 bits.
const int32_t MinScale
Maximum scale; same as APFloat for easy debug printing.
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< uint64_t, int16_t > getAdjusted64(uint64_t Digits, int16_t Scale=0)
Convenience helper for adjusting to 64 bits.
std::pair< uint32_t, int16_t > getQuotient32(uint32_t Dividend, uint32_t Divisor)
Convenience helper for 32-bit quotient.
std::pair< int32_t, int > getLgImpl(DigitsT Digits, int16_t Scale)
Implementation of getLg() and friends.
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.
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 > 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< uint64_t, int16_t > getQuotient64(uint64_t Dividend, uint64_t Divisor)
Convenience helper for 64-bit quotient.
std::pair< uint32_t, int16_t > getRounded32(uint32_t Digits, int16_t Scale, bool ShouldRound)
Convenience helper for 32-bit rounding.
int16_t matchScales(DigitsT &LDigits, int16_t &LScale, DigitsT &RDigits, int16_t &RScale)
Match scales of two numbers.
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.
const int32_t MaxScale
Maximum scale; same as APFloat for easy debug printing.
std::pair< uint32_t, int16_t > getProduct32(uint32_t LHS, uint32_t RHS)
Convenience helper for 32-bit product.
int32_t getLg(DigitsT Digits, int16_t Scale)
Get the lg (rounded) of a scaled number.
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< DigitsT, int16_t > getDifference(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale)
Get the difference of two scaled numbers.
std::pair< DigitsT, int16_t > getQuotient(DigitsT Dividend, DigitsT Divisor)
Divide two 32-bit numbers to create a 32-bit scaled number.
int compareImpl(uint64_t L, uint64_t R, int ScaleDiff)
Implementation for comparing scaled numbers.
int getWidth()
Get the width of a number.
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.
int32_t getLgCeiling(DigitsT Digits, int16_t Scale)
Get the lg ceiling of a scaled number.
std::pair< uint64_t, int16_t > getRounded64(uint64_t Digits, int16_t Scale, bool ShouldRound)
Convenience helper for 64-bit rounding.
std::pair< uint64_t, int16_t > getProduct64(uint64_t LHS, uint64_t RHS)
Convenience helper for 64-bit product.
This is an optimization pass for GlobalISel generic memory operations.
int bit_width(T Value)
Returns the number of bits needed to represent Value if Value is nonzero.
unsigned Log2_64(uint64_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
int countl_zero(T Val)
Count number of 0's from the most significant bit to the least stopping at the first 1.
decltype(auto) get(const PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info > &Pair)
static lostFraction shiftRight(APFloatBase::integerPart *dst, unsigned int parts, unsigned int bits)
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
ScaledNumber< DigitsT > operator>>(const ScaledNumber< DigitsT > &L, int16_t Shift)