//===----------------------------------------------------------------------===//
//
-// PositiveFloat definition.
+// UnsignedFloat definition.
//
// TODO: Make this private to BlockFrequencyInfoImpl or delete.
//
//===----------------------------------------------------------------------===//
namespace llvm {
-class PositiveFloatBase {
+class UnsignedFloatBase {
public:
static const int32_t MaxExponent = 16383;
static const int32_t MinExponent = -16382;
}
};
-/// \brief Simple representation of a positive floating point.
+/// \brief Simple representation of an unsigned floating point.
///
-/// PositiveFloat is a positive floating point number. It uses simple
+/// UnsignedFloat is a unsigned 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
/// 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
+/// UnsignedFloat 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 builtin floating point types, UnsignedFloat is portable.
///
-/// Unlike APFloat, PositiveFloat does not model architecture floating point
+/// Unlike APFloat, UnsignedFloat 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
+/// UnsignedFloat 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)
+/// UnsignedFloat(8u, 0) == UnsignedFloat(4u, 1)
+/// UnsignedFloat(4u, 1) == UnsignedFloat(2u, 2)
+/// UnsignedFloat(2u, 2) == UnsignedFloat(1u, 3)
///
-/// PositiveFloat implements most arithmetic operations. Precision is kept
+/// UnsignedFloat 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.
/// 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 {
+///
+/// The current plan is to gut this and make the necessary parts of it (even
+/// more) private to BlockFrequencyInfo.
+template <class DigitsT> class UnsignedFloat : UnsignedFloatBase {
public:
static_assert(!std::numeric_limits<DigitsT>::is_signed,
"only unsigned floats supported");
int16_t Exponent;
public:
- PositiveFloat() : Digits(0), Exponent(0) {}
+ UnsignedFloat() : Digits(0), Exponent(0) {}
- PositiveFloat(DigitsType Digits, int16_t Exponent)
+ UnsignedFloat(DigitsType Digits, int16_t Exponent)
: Digits(Digits), Exponent(Exponent) {}
private:
- PositiveFloat(const std::pair<uint64_t, int16_t> &X)
+ UnsignedFloat(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 UnsignedFloat getZero() { return UnsignedFloat(0, 0); }
+ static UnsignedFloat getOne() { return UnsignedFloat(1, 0); }
+ static UnsignedFloat getLargest() {
+ return UnsignedFloat(DigitsLimits::max(), MaxExponent);
}
- static PositiveFloat getFloat(uint64_t N) { return adjustToWidth(N, 0); }
- static PositiveFloat getInverseFloat(uint64_t N) {
+ static UnsignedFloat getFloat(uint64_t N) { return adjustToWidth(N, 0); }
+ static UnsignedFloat getInverseFloat(uint64_t N) {
return getFloat(N).invert();
}
- static PositiveFloat getFraction(DigitsType N, DigitsType D) {
+ static UnsignedFloat getFraction(DigitsType N, DigitsType D) {
return getQuotient(N, D);
}
/// 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 UnsignedFloat &X) const { return compare(X) == 0; }
+ bool operator<(const UnsignedFloat &X) const { return compare(X) < 0; }
+ bool operator!=(const UnsignedFloat &X) const { return compare(X) != 0; }
+ bool operator>(const UnsignedFloat &X) const { return compare(X) > 0; }
+ bool operator<=(const UnsignedFloat &X) const { return compare(X) <= 0; }
+ bool operator>=(const UnsignedFloat &X) const { return compare(X) >= 0; }
bool operator!() const { return isZero(); }
/// 65432198.7654... => 65432198.77
/// 5432198.7654... => 5432198.765
std::string toString(unsigned Precision = DefaultPrecision) {
- return PositiveFloatBase::toString(Digits, Exponent, Width, Precision);
+ return UnsignedFloatBase::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);
+ return UnsignedFloatBase::print(OS, Digits, Exponent, Width, Precision);
}
- void dump() const { return PositiveFloatBase::dump(Digits, Exponent, Width); }
+ void dump() const { return UnsignedFloatBase::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; }
+ UnsignedFloat &operator+=(const UnsignedFloat &X);
+ UnsignedFloat &operator-=(const UnsignedFloat &X);
+ UnsignedFloat &operator*=(const UnsignedFloat &X);
+ UnsignedFloat &operator/=(const UnsignedFloat &X);
+ UnsignedFloat &operator<<=(int16_t Shift) { shiftLeft(Shift); return *this; }
+ UnsignedFloat &operator>>=(int16_t Shift) { shiftRight(Shift); return *this; }
private:
void shiftLeft(int32_t Shift);
///
/// The value that compares smaller will lose precision, and possibly become
/// \a isZero().
- PositiveFloat matchExponents(PositiveFloat X);
+ UnsignedFloat matchExponents(UnsignedFloat 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);
+ void increaseExponentToMatch(UnsignedFloat &X, int32_t ExponentDiff);
public:
/// \brief Scale a large number accurately.
return joinSigned(scaleByInverse(Unsigned.first), Unsigned.second);
}
- int compare(const PositiveFloat &X) const;
+ int compare(const UnsignedFloat &X) const;
int compareTo(uint64_t N) const {
- PositiveFloat Float = getFloat(N);
+ UnsignedFloat Float = getFloat(N);
int Compare = compare(Float);
if (Width == 64 || Compare != 0)
return Compare;
}
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(); }
+ UnsignedFloat &invert() { return *this = UnsignedFloat::getFloat(1) / *this; }
+ UnsignedFloat inverse() const { return UnsignedFloat(*this).invert(); }
private:
- static PositiveFloat getProduct(DigitsType L, DigitsType R);
- static PositiveFloat getQuotient(DigitsType Dividend, DigitsType Divisor);
+ static UnsignedFloat getProduct(DigitsType L, DigitsType R);
+ static UnsignedFloat getQuotient(DigitsType Dividend, DigitsType Divisor);
std::pair<int32_t, int> lgImpl() const;
static int countLeadingZerosWidth(DigitsType Digits) {
return countLeadingZeros32(Digits) + Width - 32;
}
- static PositiveFloat adjustToWidth(uint64_t N, int32_t S) {
+ static UnsignedFloat adjustToWidth(uint64_t N, int32_t S) {
assert(S >= MinExponent);
assert(S <= MaxExponent);
if (Width == 64 || N <= DigitsLimits::max())
- return PositiveFloat(N, S);
+ return UnsignedFloat(N, S);
// Shift right.
int Shift = 64 - Width - countLeadingZeros64(N);
// Round.
assert(S + Shift <= MaxExponent);
- return getRounded(PositiveFloat(Shifted, S + Shift),
+ return getRounded(UnsignedFloat(Shifted, S + Shift),
N & UINT64_C(1) << (Shift - 1));
}
- static PositiveFloat getRounded(PositiveFloat P, bool Round) {
+ static UnsignedFloat getRounded(UnsignedFloat 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);
+ return UnsignedFloat(1, P.Exponent) <<= Width;
+ return UnsignedFloat(P.Digits + 1, P.Exponent);
}
};
-#define POSITIVE_FLOAT_BOP(op, base) \
+#define UNSIGNED_FLOAT_BOP(op, base) \
template <class DigitsT> \
- PositiveFloat<DigitsT> operator op(const PositiveFloat<DigitsT> &L, \
- const PositiveFloat<DigitsT> &R) { \
- return PositiveFloat<DigitsT>(L) base R; \
+ UnsignedFloat<DigitsT> operator op(const UnsignedFloat<DigitsT> &L, \
+ const UnsignedFloat<DigitsT> &R) { \
+ return UnsignedFloat<DigitsT>(L) base R; \
}
-POSITIVE_FLOAT_BOP(+, += )
-POSITIVE_FLOAT_BOP(-, -= )
-POSITIVE_FLOAT_BOP(*, *= )
-POSITIVE_FLOAT_BOP(/, /= )
-POSITIVE_FLOAT_BOP(<<, <<= )
-POSITIVE_FLOAT_BOP(>>, >>= )
-#undef POSITIVE_FLOAT_BOP
+UNSIGNED_FLOAT_BOP(+, += )
+UNSIGNED_FLOAT_BOP(-, -= )
+UNSIGNED_FLOAT_BOP(*, *= )
+UNSIGNED_FLOAT_BOP(/, /= )
+UNSIGNED_FLOAT_BOP(<<, <<= )
+UNSIGNED_FLOAT_BOP(>>, >>= )
+#undef UNSIGNED_FLOAT_BOP
template <class DigitsT>
-raw_ostream &operator<<(raw_ostream &OS, const PositiveFloat<DigitsT> &X) {
+raw_ostream &operator<<(raw_ostream &OS, const UnsignedFloat<DigitsT> &X) {
return X.print(OS, 10);
}
-#define POSITIVE_FLOAT_COMPARE_TO_TYPE(op, T1, T2) \
+#define UNSIGNED_FLOAT_COMPARE_TO_TYPE(op, T1, T2) \
template <class DigitsT> \
- bool operator op(const PositiveFloat<DigitsT> &L, T1 R) { \
+ bool operator op(const UnsignedFloat<DigitsT> &L, T1 R) { \
return L.compareTo(T2(R)) op 0; \
} \
template <class DigitsT> \
- bool operator op(T1 L, const PositiveFloat<DigitsT> &R) { \
+ bool operator op(T1 L, const UnsignedFloat<DigitsT> &R) { \
return 0 op R.compareTo(T2(L)); \
}
-#define POSITIVE_FLOAT_COMPARE_TO(op) \
- POSITIVE_FLOAT_COMPARE_TO_TYPE(op, uint64_t, uint64_t) \
- POSITIVE_FLOAT_COMPARE_TO_TYPE(op, uint32_t, uint64_t) \
- POSITIVE_FLOAT_COMPARE_TO_TYPE(op, int64_t, int64_t) \
- POSITIVE_FLOAT_COMPARE_TO_TYPE(op, int32_t, int64_t)
-POSITIVE_FLOAT_COMPARE_TO(< )
-POSITIVE_FLOAT_COMPARE_TO(> )
-POSITIVE_FLOAT_COMPARE_TO(== )
-POSITIVE_FLOAT_COMPARE_TO(!= )
-POSITIVE_FLOAT_COMPARE_TO(<= )
-POSITIVE_FLOAT_COMPARE_TO(>= )
-#undef POSITIVE_FLOAT_COMPARE_TO
-#undef POSITIVE_FLOAT_COMPARE_TO_TYPE
+#define UNSIGNED_FLOAT_COMPARE_TO(op) \
+ UNSIGNED_FLOAT_COMPARE_TO_TYPE(op, uint64_t, uint64_t) \
+ UNSIGNED_FLOAT_COMPARE_TO_TYPE(op, uint32_t, uint64_t) \
+ UNSIGNED_FLOAT_COMPARE_TO_TYPE(op, int64_t, int64_t) \
+ UNSIGNED_FLOAT_COMPARE_TO_TYPE(op, int32_t, int64_t)
+UNSIGNED_FLOAT_COMPARE_TO(< )
+UNSIGNED_FLOAT_COMPARE_TO(> )
+UNSIGNED_FLOAT_COMPARE_TO(== )
+UNSIGNED_FLOAT_COMPARE_TO(!= )
+UNSIGNED_FLOAT_COMPARE_TO(<= )
+UNSIGNED_FLOAT_COMPARE_TO(>= )
+#undef UNSIGNED_FLOAT_COMPARE_TO
+#undef UNSIGNED_FLOAT_COMPARE_TO_TYPE
template <class DigitsT>
-uint64_t PositiveFloat<DigitsT>::scale(uint64_t N) const {
+uint64_t UnsignedFloat<DigitsT>::scale(uint64_t N) const {
if (Width == 64 || N <= DigitsLimits::max())
return (getFloat(N) * *this).template toInt<uint64_t>();
// Defer to the 64-bit version.
- return PositiveFloat<uint64_t>(Digits, Exponent).scale(N);
+ return UnsignedFloat<uint64_t>(Digits, Exponent).scale(N);
}
template <class DigitsT>
-PositiveFloat<DigitsT> PositiveFloat<DigitsT>::getProduct(DigitsType L,
+UnsignedFloat<DigitsT> UnsignedFloat<DigitsT>::getProduct(DigitsType L,
DigitsType R) {
// Check for zero.
if (!L || !R)
return adjustToWidth(uint64_t(L) * uint64_t(R), 0);
// Do the full thing.
- return PositiveFloat(multiply64(L, R));
+ return UnsignedFloat(multiply64(L, R));
}
template <class DigitsT>
-PositiveFloat<DigitsT> PositiveFloat<DigitsT>::getQuotient(DigitsType Dividend,
+UnsignedFloat<DigitsT> UnsignedFloat<DigitsT>::getQuotient(DigitsType Dividend,
DigitsType Divisor) {
// Check for zero.
if (!Dividend)
return getLargest();
if (Width == 64)
- return PositiveFloat(divide64(Dividend, Divisor));
+ return UnsignedFloat(divide64(Dividend, Divisor));
// We can compute this with 64-bit math.
int Shift = countLeadingZeros64(Dividend);
return adjustToWidth(Quotient, -Shift);
// Round based on the value of the next bit.
- return getRounded(PositiveFloat(Quotient, -Shift),
+ return getRounded(UnsignedFloat(Quotient, -Shift),
Shifted % Divisor >= getHalf(Divisor));
}
template <class DigitsT>
template <class IntT>
-IntT PositiveFloat<DigitsT>::toInt() const {
+IntT UnsignedFloat<DigitsT>::toInt() const {
typedef std::numeric_limits<IntT> Limits;
if (*this < 1)
return 0;
}
template <class DigitsT>
-std::pair<int32_t, int> PositiveFloat<DigitsT>::lgImpl() const {
+std::pair<int32_t, int> UnsignedFloat<DigitsT>::lgImpl() const {
if (isZero())
return std::make_pair(INT32_MIN, 0);
}
template <class DigitsT>
-PositiveFloat<DigitsT> PositiveFloat<DigitsT>::matchExponents(PositiveFloat X) {
+UnsignedFloat<DigitsT> UnsignedFloat<DigitsT>::matchExponents(UnsignedFloat X) {
if (isZero() || X.isZero() || Exponent == X.Exponent)
return X;
return X;
}
template <class DigitsT>
-void PositiveFloat<DigitsT>::increaseExponentToMatch(PositiveFloat &X,
+void UnsignedFloat<DigitsT>::increaseExponentToMatch(UnsignedFloat &X,
int32_t ExponentDiff) {
assert(ExponentDiff > 0);
if (ExponentDiff >= 2 * Width) {
}
template <class DigitsT>
-PositiveFloat<DigitsT> &PositiveFloat<DigitsT>::
-operator+=(const PositiveFloat &X) {
+UnsignedFloat<DigitsT> &UnsignedFloat<DigitsT>::
+operator+=(const UnsignedFloat &X) {
if (isLargest() || X.isZero())
return *this;
if (isZero() || X.isLargest())
return *this = X;
// Normalize exponents.
- PositiveFloat Scaled = matchExponents(X);
+ UnsignedFloat Scaled = matchExponents(X);
// Check for zero again.
if (isZero())
return *this;
}
template <class DigitsT>
-PositiveFloat<DigitsT> &PositiveFloat<DigitsT>::
-operator-=(const PositiveFloat &X) {
+UnsignedFloat<DigitsT> &UnsignedFloat<DigitsT>::
+operator-=(const UnsignedFloat &X) {
if (X.isZero())
return *this;
if (*this <= X)
return *this = getZero();
// Normalize exponents.
- PositiveFloat Scaled = matchExponents(X);
+ UnsignedFloat Scaled = matchExponents(X);
assert(Digits >= Scaled.Digits);
// Compute difference.
// Check if X just barely lost its last bit. E.g., for 32-bit:
//
// 1*2^32 - 1*2^0 == 0xffffffff != 1*2^32
- if (*this == PositiveFloat(1, X.lgFloor() + Width)) {
+ if (*this == UnsignedFloat(1, X.lgFloor() + Width)) {
Digits = DigitsType(0) - 1;
--Exponent;
}
return *this;
}
template <class DigitsT>
-PositiveFloat<DigitsT> &PositiveFloat<DigitsT>::
-operator*=(const PositiveFloat &X) {
+UnsignedFloat<DigitsT> &UnsignedFloat<DigitsT>::
+operator*=(const UnsignedFloat &X) {
if (isZero())
return *this;
if (X.isZero())
return *this <<= Exponents;
}
template <class DigitsT>
-PositiveFloat<DigitsT> &PositiveFloat<DigitsT>::
-operator/=(const PositiveFloat &X) {
+UnsignedFloat<DigitsT> &UnsignedFloat<DigitsT>::
+operator/=(const UnsignedFloat &X) {
if (isZero())
return *this;
if (X.isZero())
return *this <<= Exponents;
}
template <class DigitsT>
-void PositiveFloat<DigitsT>::shiftLeft(int32_t Shift) {
+void UnsignedFloat<DigitsT>::shiftLeft(int32_t Shift) {
if (!Shift || isZero())
return;
assert(Shift != INT32_MIN);
}
template <class DigitsT>
-void PositiveFloat<DigitsT>::shiftRight(int32_t Shift) {
+void UnsignedFloat<DigitsT>::shiftRight(int32_t Shift) {
if (!Shift || isZero())
return;
assert(Shift != INT32_MIN);
}
template <class DigitsT>
-int PositiveFloat<DigitsT>::compare(const PositiveFloat &X) const {
+int UnsignedFloat<DigitsT>::compare(const UnsignedFloat &X) const {
// Check for zero.
if (isZero())
return X.isZero() ? 0 : -1;
// Compare digits.
if (Exponent < X.Exponent)
- return PositiveFloatBase::compare(Digits, X.Digits, X.Exponent - Exponent);
+ return UnsignedFloatBase::compare(Digits, X.Digits, X.Exponent - Exponent);
- return -PositiveFloatBase::compare(X.Digits, Digits, Exponent - X.Exponent);
+ return -UnsignedFloatBase::compare(X.Digits, Digits, Exponent - X.Exponent);
}
-template <class T> struct isPodLike<PositiveFloat<T>> {
+template <class T> struct isPodLike<UnsignedFloat<T>> {
static const bool value = true;
};
}
///
/// Convert to a float. \a isFull() gives 1.0, while \a isEmpty() gives
/// slightly above 0.0.
- PositiveFloat<uint64_t> toFloat() const;
+ UnsignedFloat<uint64_t> toFloat() const;
void dump() const;
raw_ostream &print(raw_ostream &OS) const;
/// BlockFrequencyInfoImpl. See there for details.
class BlockFrequencyInfoImplBase {
public:
- typedef PositiveFloat<uint64_t> Float;
+ typedef UnsignedFloat<uint64_t> Float;
/// \brief Representative of a block.
///
/// MachineBlockFrequencyInfo, and calculates the relative frequencies of
/// blocks.
///
-/// This algorithm leverages BlockMass and PositiveFloat to maintain precision,
+/// This algorithm leverages BlockMass and UnsignedFloat to maintain precision,
/// separates mass distribution from loop scaling, and dithers to eliminate
/// probability mass loss.
///
projects / oota-llvm.git / blobdiff