-//===----------------------------------------------------------------------===//
-//
-// PositiveFloat definition.
-//
-// TODO: Make this private to BlockFrequencyInfoImpl or delete.
-//
-//===----------------------------------------------------------------------===//
-namespace llvm {
-
-class PositiveFloatBase {
-public:
- static const int32_t MaxExponent = 16383;
- static const int32_t MinExponent = -16382;
- static const int DefaultPrecision = 10;
-
- static void dump(uint64_t D, int16_t E, int Width);
- 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 int countLeadingZeros32(uint32_t N) { return countLeadingZeros(N); }
- static int countLeadingZeros64(uint64_t N) { return countLeadingZeros(N); }
- static uint64_t getHalf(uint64_t N) { return (N >> 1) + (N & 1); }
-
- static std::pair<uint64_t, bool> splitSigned(int64_t N) {
- if (N >= 0)
- return std::make_pair(N, false);
- uint64_t Unsigned = N == INT64_MIN ? UINT64_C(1) << 63 : uint64_t(-N);
- return std::make_pair(Unsigned, true);
- }
- static int64_t joinSigned(uint64_t U, bool IsNeg) {
- if (U > uint64_t(INT64_MAX))
- return IsNeg ? INT64_MIN : INT64_MAX;
- return IsNeg ? -int64_t(U) : int64_t(U);
- }
-
- static int32_t extractLg(const std::pair<int32_t, int> &Lg) {
- return Lg.first;
- }
- static int32_t extractLgFloor(const std::pair<int32_t, int> &Lg) {
- return Lg.first - (Lg.second > 0);
- }
- static int32_t extractLgCeiling(const std::pair<int32_t, int> &Lg) {
- return Lg.first + (Lg.second < 0);
- }
-
- static std::pair<uint64_t, int16_t> divide64(uint64_t L, uint64_t R);
- static std::pair<uint64_t, int16_t> multiply64(uint64_t L, uint64_t R);
-
- static int compare(uint64_t L, uint64_t R, int Shift) {
- assert(Shift >= 0);
- assert(Shift < 64);
-
- uint64_t L_adjusted = L >> Shift;
- if (L_adjusted < R)
- return -1;
- if (L_adjusted > R)
- return 1;
-
- return L > L_adjusted << Shift ? 1 : 0;
- }
-};
-
-/// \brief Simple representation of a positive floating point.
-///
-/// PositiveFloat is a positive floating point number. It uses simple
-/// saturation arithmetic, and every operation is well-defined for every value.
-///
-/// The number is split into a signed exponent and unsigned digits. The number
-/// represented is \c getDigits()*2^getExponent(). In this way, the digits are
-/// much like the mantissa in the x87 long double, but there is no canonical
-/// form, so the same number can be represented by many bit representations
-/// (it's always in "denormal" mode).
-///
-/// PositiveFloat is templated on the underlying integer type for digits, which
-/// is expected to be one of uint64_t, uint32_t, uint16_t or uint8_t.
-///
-/// Unlike builtin floating point types, PositiveFloat is portable.
-///
-/// Unlike APFloat, PositiveFloat does not model architecture floating point
-/// behaviour (this should make it a little faster), and implements most
-/// operators (this makes it usable).
-///
-/// PositiveFloat is totally ordered. However, there is no canonical form, so
-/// there are multiple representations of most scalars. E.g.:
-///
-/// PositiveFloat(8u, 0) == PositiveFloat(4u, 1)
-/// PositiveFloat(4u, 1) == PositiveFloat(2u, 2)
-/// PositiveFloat(2u, 2) == PositiveFloat(1u, 3)
-///
-/// PositiveFloat implements most arithmetic operations. Precision is kept
-/// where possible. Uses simple saturation arithmetic, so that operations
-/// saturate to 0.0 or getLargest() rather than under or overflowing. It has
-/// some extra arithmetic for unit inversion. 0.0/0.0 is defined to be 0.0.
-/// Any other division by 0.0 is defined to be getLargest().
-///
-/// As a convenience for modifying the exponent, left and right shifting are
-/// both implemented, and both interpret negative shifts as positive shifts in
-/// the opposite direction.
-///
-/// Future work might extract most of the implementation into a base class
-/// (e.g., \c Float) that has an \c IsSigned template parameter. The initial
-/// use case for this only needed positive semantics, but it wouldn't take much
-/// work to extend.
-///
-/// Exponents are limited to the range accepted by x87 long double. This makes
-/// it trivial to add functionality to convert to APFloat (this is already
-/// relied on for the implementation of printing).
-template <class DigitsT> class PositiveFloat : PositiveFloatBase {
-public:
- static_assert(!std::numeric_limits<DigitsT>::is_signed,
- "only unsigned floats supported");
-
- typedef DigitsT DigitsType;
-
-private:
- typedef std::numeric_limits<DigitsType> DigitsLimits;
-
- static const int Width = sizeof(DigitsType) * 8;
- static_assert(Width <= 64, "invalid integer width for digits");
-
-private:
- DigitsType Digits;
- int16_t Exponent;
-
-public:
- PositiveFloat() : Digits(0), Exponent(0) {}
-
- PositiveFloat(DigitsType Digits, int16_t Exponent)
- : Digits(Digits), Exponent(Exponent) {}
-
-private:
- PositiveFloat(const std::pair<uint64_t, int16_t> &X)
- : Digits(X.first), Exponent(X.second) {}
-
-public:
- static PositiveFloat getZero() { return PositiveFloat(0, 0); }
- static PositiveFloat getOne() { return PositiveFloat(1, 0); }
- static PositiveFloat getLargest() {
- return PositiveFloat(DigitsLimits::max(), MaxExponent);
- }
- static PositiveFloat getFloat(uint64_t N) { return adjustToWidth(N, 0); }
- static PositiveFloat getInverseFloat(uint64_t N) {
- return getFloat(N).invert();
- }
- static PositiveFloat getFraction(DigitsType N, DigitsType D) {
- return getQuotient(N, D);
- }
-
- int16_t getExponent() const { return Exponent; }
- DigitsType getDigits() const { return Digits; }
-
- /// \brief Convert to the given integer type.
- ///
- /// Convert to \c IntT using simple saturating arithmetic, truncating if
- /// necessary.
- template <class IntT> IntT toInt() const;
-
- bool isZero() const { return !Digits; }
- bool isLargest() const { return *this == getLargest(); }
- bool isOne() const {
- if (Exponent > 0 || Exponent <= -Width)
- return false;
- return Digits == DigitsType(1) << -Exponent;
- }
-
- /// \brief The log base 2, rounded.
- ///
- /// Get the lg of the scalar. lg 0 is defined to be INT32_MIN.
- int32_t lg() const { return extractLg(lgImpl()); }
-
- /// \brief The log base 2, rounded towards INT32_MIN.
- ///
- /// Get the lg floor. lg 0 is defined to be INT32_MIN.
- int32_t lgFloor() const { return extractLgFloor(lgImpl()); }
-
- /// \brief The log base 2, rounded towards INT32_MAX.
- ///
- /// Get the lg ceiling. lg 0 is defined to be INT32_MIN.
- int32_t lgCeiling() const { return extractLgCeiling(lgImpl()); }
-
- bool operator==(const PositiveFloat &X) const { return compare(X) == 0; }
- bool operator<(const PositiveFloat &X) const { return compare(X) < 0; }
- bool operator!=(const PositiveFloat &X) const { return compare(X) != 0; }
- bool operator>(const PositiveFloat &X) const { return compare(X) > 0; }
- bool operator<=(const PositiveFloat &X) const { return compare(X) <= 0; }
- bool operator>=(const PositiveFloat &X) const { return compare(X) >= 0; }
-
- bool operator!() const { return isZero(); }
-
- /// \brief Convert to a decimal representation in a string.
- ///
- /// Convert to a string. Uses scientific notation for very large/small
- /// numbers. Scientific notation is used roughly for numbers outside of the
- /// range 2^-64 through 2^64.
- ///
- /// \c Precision indicates the number of decimal digits of precision to use;
- /// 0 requests the maximum available.
- ///
- /// As a special case to make debugging easier, if the number is small enough
- /// to convert without scientific notation and has more than \c Precision
- /// digits before the decimal place, it's printed accurately to the first
- /// digit past zero. E.g., assuming 10 digits of precision:
- ///
- /// 98765432198.7654... => 98765432198.8
- /// 8765432198.7654... => 8765432198.8
- /// 765432198.7654... => 765432198.8
- /// 65432198.7654... => 65432198.77
- /// 5432198.7654... => 5432198.765
- std::string toString(unsigned Precision = DefaultPrecision) {
- return PositiveFloatBase::toString(Digits, Exponent, Width, Precision);
- }
-
- /// \brief Print a decimal representation.
- ///
- /// Print a string. See toString for documentation.
- raw_ostream &print(raw_ostream &OS,
- unsigned Precision = DefaultPrecision) const {
- return PositiveFloatBase::print(OS, Digits, Exponent, Width, Precision);
- }
- void dump() const { return PositiveFloatBase::dump(Digits, Exponent, Width); }
-
- PositiveFloat &operator+=(const PositiveFloat &X);
- PositiveFloat &operator-=(const PositiveFloat &X);
- PositiveFloat &operator*=(const PositiveFloat &X);
- PositiveFloat &operator/=(const PositiveFloat &X);
- PositiveFloat &operator<<=(int16_t Shift) { shiftLeft(Shift); return *this; }
- PositiveFloat &operator>>=(int16_t Shift) { shiftRight(Shift); return *this; }
-
-private:
- void shiftLeft(int32_t Shift);
- void shiftRight(int32_t Shift);
-
- /// \brief Adjust two floats to have matching exponents.
- ///
- /// Adjust \c this and \c X to have matching exponents. Returns the new \c X
- /// by value. Does nothing if \a isZero() for either.
- ///
- /// The value that compares smaller will lose precision, and possibly become
- /// \a isZero().
- PositiveFloat matchExponents(PositiveFloat X);
-
- /// \brief Increase exponent to match another float.
- ///
- /// Increases \c this to have an exponent matching \c X. May decrease the
- /// exponent of \c X in the process, and \c this may possibly become \a
- /// isZero().
- void increaseExponentToMatch(PositiveFloat &X, int32_t ExponentDiff);
-
-public:
- /// \brief Scale a large number accurately.
- ///
- /// Scale N (multiply it by this). Uses full precision multiplication, even
- /// if Width is smaller than 64, so information is not lost.
- uint64_t scale(uint64_t N) const;
- uint64_t scaleByInverse(uint64_t N) const {
- // TODO: implement directly, rather than relying on inverse. Inverse is
- // expensive.
- return inverse().scale(N);
- }
- int64_t scale(int64_t N) const {
- std::pair<uint64_t, bool> Unsigned = splitSigned(N);
- return joinSigned(scale(Unsigned.first), Unsigned.second);
- }
- int64_t scaleByInverse(int64_t N) const {
- std::pair<uint64_t, bool> Unsigned = splitSigned(N);
- return joinSigned(scaleByInverse(Unsigned.first), Unsigned.second);
- }
-
- int compare(const PositiveFloat &X) const;
- int compareTo(uint64_t N) const {
- PositiveFloat Float = getFloat(N);
- int Compare = compare(Float);
- if (Width == 64 || Compare != 0)
- return Compare;
-
- // Check for precision loss. We know *this == RoundTrip.
- uint64_t RoundTrip = Float.template toInt<uint64_t>();
- return N == RoundTrip ? 0 : RoundTrip < N ? -1 : 1;
- }
- int compareTo(int64_t N) const { return N < 0 ? 1 : compareTo(uint64_t(N)); }
-
- PositiveFloat &invert() { return *this = PositiveFloat::getFloat(1) / *this; }
- PositiveFloat inverse() const { return PositiveFloat(*this).invert(); }
-
-private:
- static PositiveFloat getProduct(DigitsType L, DigitsType R);
- static PositiveFloat getQuotient(DigitsType Dividend, DigitsType Divisor);
-
- std::pair<int32_t, int> lgImpl() const;
- static int countLeadingZerosWidth(DigitsType Digits) {
- if (Width == 64)
- return countLeadingZeros64(Digits);
- if (Width == 32)
- return countLeadingZeros32(Digits);
- return countLeadingZeros32(Digits) + Width - 32;
- }
-
- static PositiveFloat adjustToWidth(uint64_t N, int32_t S) {
- assert(S >= MinExponent);
- assert(S <= MaxExponent);
- if (Width == 64 || N <= DigitsLimits::max())
- return PositiveFloat(N, S);
-
- // Shift right.
- int Shift = 64 - Width - countLeadingZeros64(N);
- DigitsType Shifted = N >> Shift;
-
- // Round.
- assert(S + Shift <= MaxExponent);
- return getRounded(PositiveFloat(Shifted, S + Shift),
- N & UINT64_C(1) << (Shift - 1));
- }
-
- static PositiveFloat getRounded(PositiveFloat P, bool Round) {
- if (!Round)
- return P;
- if (P.Digits == DigitsLimits::max())
- // Careful of overflow in the exponent.
- return PositiveFloat(1, P.Exponent) <<= Width;
- return PositiveFloat(P.Digits + 1, P.Exponent);
- }
-};