Go to the documentation of this file.
21 #ifndef LLVM_SUPPORT_SCALEDNUMBER_H
22 #define LLVM_SUPPORT_SCALEDNUMBER_H
33 namespace ScaledNumbers {
42 template <
class DigitsT>
inline int getWidth() {
return sizeof(DigitsT) * 8; }
51 template <
class DigitsT>
52 inline 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);
78 template <
class DigitsT>
81 static_assert(!std::numeric_limits<DigitsT>::is_signed,
"expected unsigned");
83 const int Width = getWidth<DigitsT>();
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);
113 template <
class DigitsT>
115 static_assert(!std::numeric_limits<DigitsT>::is_signed,
"expected unsigned");
117 if (getWidth<DigitsT>() <= 32 || (
LHS <= UINT32_MAX &&
RHS <= UINT32_MAX))
152 template <
class DigitsT>
153 std::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);
164 if (getWidth<DigitsT>() == 64)
187 template <
class DigitsT>
188 inline 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);
198 int32_t Floor = Scale + LocalFloor;
199 if (Digits == UINT64_C(1) << LocalFloor)
200 return std::make_pair(Floor, 0);
204 bool Round = Digits & UINT64_C(1) << (LocalFloor - 1);
205 return std::make_pair(Floor + Round, Round ? 1 : -1);
213 template <
class DigitsT> int32_t
getLg(DigitsT Digits, int16_t Scale) {
222 template <
class DigitsT> int32_t
getLgFloor(DigitsT Digits, int16_t Scale) {
224 return Lg.first - (Lg.second > 0);
232 template <
class DigitsT> int32_t
getLgCeiling(DigitsT Digits, int16_t Scale) {
234 return Lg.first + (Lg.second < 0);
250 template <
class DigitsT>
251 int compare(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale) {
252 static_assert(!std::numeric_limits<DigitsT>::is_signed,
"expected unsigned");
256 return RDigits ? -1 : 0;
264 return lgL < lgR ? -1 : 1;
268 return compareImpl(LDigits, RDigits, RScale - LScale);
270 return -
compareImpl(RDigits, LDigits, LScale - RScale);
285 template <
class DigitsT>
286 int16_t
matchScales(DigitsT &LDigits, int16_t &LScale, DigitsT &RDigits,
288 static_assert(!std::numeric_limits<DigitsT>::is_signed,
"expected unsigned");
292 return matchScales(RDigits, RScale, LDigits, LScale);
295 if (!RDigits || LScale == RScale)
299 int32_t ScaleDiff = int32_t(LScale) - RScale;
300 if (ScaleDiff >= 2 * getWidth<DigitsT>()) {
308 assert(ShiftL < getWidth<DigitsT>() &&
"can't shift more than width");
310 int32_t ShiftR = ScaleDiff - ShiftL;
311 if (ShiftR >= getWidth<DigitsT>()) {
322 assert(LScale == RScale &&
"scales should match");
331 template <
class DigitsT>
332 std::pair<DigitsT, int16_t>
getSum(DigitsT LDigits, int16_t LScale,
333 DigitsT RDigits, int16_t RScale) {
334 static_assert(!std::numeric_limits<DigitsT>::is_signed,
"expected unsigned");
338 assert(LScale < INT16_MAX &&
"scale too large");
339 assert(RScale < INT16_MAX &&
"scale too large");
342 int16_t Scale =
matchScales(LDigits, LScale, RDigits, RScale);
345 DigitsT Sum = LDigits + RDigits;
347 return std::make_pair(Sum, Scale);
350 DigitsT HighBit = DigitsT(1) << (getWidth<DigitsT>() - 1);
351 return std::make_pair(HighBit | Sum >> 1, Scale + 1);
357 return getSum(LDigits, LScale, RDigits, RScale);
363 return getSum(LDigits, LScale, RDigits, RScale);
371 template <
class DigitsT>
373 DigitsT RDigits, int16_t RScale) {
374 static_assert(!std::numeric_limits<DigitsT>::is_signed,
"expected unsigned");
377 const DigitsT SavedRDigits = RDigits;
378 const int16_t SavedRScale = RScale;
382 if (LDigits <= RDigits)
383 return std::make_pair(0, 0);
384 if (RDigits || !SavedRDigits)
385 return std::make_pair(LDigits - RDigits, LScale);
390 const auto RLgFloor =
getLgFloor(SavedRDigits, SavedRScale);
391 if (!
compare(LDigits, LScale, DigitsT(1), RLgFloor + getWidth<DigitsT>()))
394 return std::make_pair(LDigits, LScale);
434 return std::make_pair(
N,
false);
436 return std::make_pair(
Unsigned,
true);
441 return IsNeg ? -int64_t(U) : int64_t(U);
494 static_assert(!std::numeric_limits<DigitsT>::is_signed,
495 "only unsigned floats supported");
500 typedef std::numeric_limits<DigitsType> DigitsLimits;
502 static constexpr
int Width =
sizeof(
DigitsType) * 8;
503 static_assert(Width <= 64,
"invalid integer width for digits");
513 : Digits(Digits), Scale(Scale) {}
517 : Digits(
X.first), Scale(
X.second) {}
530 return getQuotient(
N,
D);
540 template <
class IntT> IntT
toInt()
const;
545 if (Scale > 0 || Scale <= -Width)
609 std::tie(Digits, Scale) =
617 std::tie(Digits, Scale) =
633 void shiftLeft(int32_t
Shift);
634 void shiftRight(int32_t
Shift);
672 return ScaledNumbers::compare<uint64_t>(Digits, Scale,
N, 0);
687 static int countLeadingZerosWidth(
DigitsType Digits) {
703 "Shift should be close to 0");
704 auto Adjusted = ScaledNumbers::getAdjusted<DigitsT>(
N,
Shift);
717 #define SCALED_NUMBER_BOP(op, base) \
718 template <class DigitsT> \
719 ScaledNumber<DigitsT> operator op(const ScaledNumber<DigitsT> &L, \
720 const ScaledNumber<DigitsT> &R) { \
721 return ScaledNumber<DigitsT>(L) base R; \
727 #undef SCALED_NUMBER_BOP
729 template <
class DigitsT>
735 template <
class DigitsT>
741 template <
class DigitsT>
743 return X.print(OS, 10);
746 #define SCALED_NUMBER_COMPARE_TO_TYPE(op, T1, T2) \
747 template <class DigitsT> \
748 bool operator op(const ScaledNumber<DigitsT> &L, T1 R) { \
749 return L.compareTo(T2(R)) op 0; \
751 template <class DigitsT> \
752 bool operator op(T1 L, const ScaledNumber<DigitsT> &R) { \
753 return 0 op R.compareTo(T2(L)); \
755 #define SCALED_NUMBER_COMPARE_TO(op) \
756 SCALED_NUMBER_COMPARE_TO_TYPE(op, uint64_t, uint64_t) \
757 SCALED_NUMBER_COMPARE_TO_TYPE(op, uint32_t, uint64_t) \
758 SCALED_NUMBER_COMPARE_TO_TYPE(op, int64_t, int64_t) \
759 SCALED_NUMBER_COMPARE_TO_TYPE(op, int32_t, int64_t)
766 #undef SCALED_NUMBER_COMPARE_TO
767 #undef SCALED_NUMBER_COMPARE_TO_TYPE
769 template <
class DigitsT>
772 return (
get(
N) * *
this).template toInt<uint64_t>();
778 template <
class DigitsT>
779 template <
class IntT>
781 typedef std::numeric_limits<IntT> Limits;
789 assert(
size_t(Scale) <
sizeof(IntT) * 8);
793 assert(
size_t(-Scale) <
sizeof(IntT) * 8);
799 template <
class DigitsT>
808 int32_t Scales = int32_t(Scale) + int32_t(
X.Scale);
814 return *
this <<= Scales;
816 template <
class DigitsT>
822 return *
this = getLargest();
825 int32_t Scales = int32_t(Scale) - int32_t(
X.Scale);
831 return *
this <<= Scales;
845 if (ScaleShift ==
Shift)
854 if (
Shift > countLeadingZerosWidth(Digits)) {
856 *
this = getLargest();
863 template <
class DigitsT>
void ScaledNumber<DigitsT>::shiftRight(int32_t
Shift) {
875 if (ScaleShift ==
Shift)
892 #endif // LLVM_SUPPORT_SCALEDNUMBER_H
std::pair< uint32_t, int16_t > getProduct32(uint32_t LHS, uint32_t RHS)
Convenience helper for 32-bit product.
This is an optimization pass for GlobalISel generic memory operations.
static ScaledNumber get(uint64_t N)
static ScaledNumber getZero()
uint64_t scaleByInverse(uint64_t N) const
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
bool operator!=(const ScaledNumber &X) const
std::pair< DigitsT, int16_t > getProduct(DigitsT LHS, DigitsT RHS)
Multiply two 32-bit integers to create a 32-bit scaled 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 lgCeiling() const
The log base 2, rounded towards INT32_MAX.
bool operator<=(const ScaledNumber &X) const
std::pair< DigitsT, int16_t > getDifference(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale)
Get the difference of two scaled numbers.
ScaledNumber inverse() const
static std::pair< uint64_t, bool > splitSigned(int64_t N)
bool operator==(const ScaledNumber &X) const
const int32_t MaxScale
Maximum scale; same as APFloat for easy debug printing.
ScaledNumber & operator-=(const ScaledNumber &X)
bool operator>(const ScaledNumber &X) const
static constexpr int DefaultPrecision
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
const int32_t MinScale
Maximum scale; same as APFloat for easy debug printing.
static uint64_t getHalf(uint64_t N)
int64_t scaleByInverse(int64_t N) const
std::pair< uint32_t, int16_t > getAdjusted32(uint64_t Digits, int16_t Scale=0)
Convenience helper for adjusting to 32 bits.
ScaledNumber< DigitsT > operator>>(const ScaledNumber< DigitsT > &L, int16_t Shift)
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
int getWidth()
Get the width of a number.
int32_t lg() const
The log base 2, rounded.
int compareTo(int64_t N) const
static ScaledNumber getLargest()
This class implements an extremely fast bulk output stream that can only output to a stream.
raw_ostream & print(raw_ostream &OS, unsigned Precision=DefaultPrecision) const
Print a decimal representation.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
int16_t matchScales(DigitsT &LDigits, int16_t &LScale, DigitsT &RDigits, int16_t &RScale)
Match scales of two numbers.
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 > divide32(uint32_t Dividend, uint32_t Divisor)
Divide two 32-bit integers to create a 32-bit scaled number.
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static raw_ostream & print(raw_ostream &OS, uint64_t D, int16_t E, int Width, unsigned Precision)
std::pair< DigitsT, int16_t > getAdjusted(uint64_t Digits, int16_t Scale=0)
Adjust a 64-bit scaled number down to the appropriate width.
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
std::pair< uint64_t, int16_t > getQuotient64(uint64_t Dividend, uint64_t Divisor)
Convenience helper for 64-bit quotient.
std::pair< uint64_t, int16_t > getRounded64(uint64_t Digits, int16_t Scale, bool ShouldRound)
Convenience helper for 64-bit rounding.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static ScaledNumber getInverse(uint64_t N)
int compare(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale)
Compare two scaled numbers.
static ScaledNumber getFraction(DigitsType N, DigitsType D)
std::pair< DigitsT, int16_t > getRounded(DigitsT Digits, int16_t Scale, bool ShouldRound)
Conditionally round up a scaled number.
bool operator>=(const ScaledNumber &X) const
bool operator<(const ScaledNumber &X) const
static int64_t joinSigned(uint64_t U, bool IsNeg)
int32_t getLg(DigitsT Digits, int16_t Scale)
Get the lg (rounded) of a scaled number.
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
std::string toString(unsigned Precision=DefaultPrecision)
Convert to a decimal representation in a string.
std::pair< uint32_t, int16_t > getRounded32(uint32_t Digits, int16_t Scale, bool ShouldRound)
Convenience helper for 32-bit rounding.
ScaledNumber & operator*=(const ScaledNumber &X)
IntT toInt() const
Convert to the given integer type.
int compareImpl(uint64_t L, uint64_t R, int ScaleDiff)
Implementation for comparing scaled numbers.
#define SCALED_NUMBER_COMPARE_TO(op)
uint64_t scale(uint64_t N) const
Scale a large number accurately.
std::pair< int32_t, int > getLgImpl(DigitsT Digits, int16_t Scale)
Implementation of getLg() and friends.
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< uint32_t, int16_t > getQuotient32(uint32_t Dividend, uint32_t Divisor)
Convenience helper for 32-bit quotient.
constexpr ScaledNumber(DigitsType Digits, int16_t Scale)
ScaledNumber & operator+=(const ScaledNumber &X)
std::pair< DigitsT, int16_t > getQuotient(DigitsT Dividend, DigitsT Divisor)
Divide two 32-bit numbers to create a 32-bit scaled number.
static std::string toString(uint64_t D, int16_t E, int Width, unsigned Precision)
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.
Simple representation of a scaled number.
int32_t getLgFloor(DigitsT Digits, int16_t Scale)
Get the lg floor of a scaled number.
static ScaledNumber getOne()
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.
Should compile to something r4 addze r3 instead we get
std::pair< uint64_t, int16_t > getProduct64(uint64_t LHS, uint64_t RHS)
Convenience helper for 64-bit product.
int32_t getLgCeiling(DigitsT Digits, int16_t Scale)
Get the lg ceiling of a 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.
ScaledNumber & operator/=(const ScaledNumber &X)
unsigned 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.
static int countLeadingZeros64(uint64_t N)
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.
int64_t scale(int64_t N) const
int compare(const ScaledNumber &X) const
static lostFraction shiftRight(APFloatBase::integerPart *dst, unsigned int parts, unsigned int bits)
int32_t lgFloor() const
The log base 2, rounded towards INT32_MIN.
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.
static void dump(uint64_t D, int16_t E, int Width)
int compareTo(uint64_t N) const
ScaledNumber & operator>>=(int16_t Shift)
#define SCALED_NUMBER_BOP(op, base)
static int countLeadingZeros32(uint32_t N)
DigitsType getDigits() const
ScaledNumber & operator<<=(int16_t Shift)