#include <intrin.h>
#endif
+#ifdef __ANDROID_NDK__
+#include <android/api-level.h>
+#endif
+
namespace llvm {
/// \brief The behavior an operation has on an input of 0.
enum ZeroBehavior {
}
};
-#if __GNUC__ >= 4 || _MSC_VER
+#if __GNUC__ >= 4 || defined(_MSC_VER)
template <typename T> struct TrailingZerosCounter<T, 4> {
static std::size_t count(T Val, ZeroBehavior ZB) {
if (ZB != ZB_Undefined && Val == 0)
#if __has_builtin(__builtin_ctz) || LLVM_GNUC_PREREQ(4, 0, 0)
return __builtin_ctz(Val);
-#elif _MSC_VER
+#elif defined(_MSC_VER)
unsigned long Index;
_BitScanForward(&Index, Val);
return Index;
#if __has_builtin(__builtin_ctzll) || LLVM_GNUC_PREREQ(4, 0, 0)
return __builtin_ctzll(Val);
-#elif _MSC_VER
+#elif defined(_MSC_VER)
unsigned long Index;
_BitScanForward64(&Index, Val);
return Index;
}
};
-#if __GNUC__ >= 4 || _MSC_VER
+#if __GNUC__ >= 4 || defined(_MSC_VER)
template <typename T> struct LeadingZerosCounter<T, 4> {
static std::size_t count(T Val, ZeroBehavior ZB) {
if (ZB != ZB_Undefined && Val == 0)
#if __has_builtin(__builtin_clz) || LLVM_GNUC_PREREQ(4, 0, 0)
return __builtin_clz(Val);
-#elif _MSC_VER
+#elif defined(_MSC_VER)
unsigned long Index;
_BitScanReverse(&Index, Val);
return Index ^ 31;
#if __has_builtin(__builtin_clzll) || LLVM_GNUC_PREREQ(4, 0, 0)
return __builtin_clzll(Val);
-#elif _MSC_VER
+#elif defined(_MSC_VER)
unsigned long Index;
_BitScanReverse64(&Index, Val);
return Index ^ 63;
/// isUIntN - Checks if an unsigned integer fits into the given (dynamic)
/// bit width.
inline bool isUIntN(unsigned N, uint64_t x) {
- return x == (x & (~0ULL >> (64 - N)));
+ return N >= 64 || x < (UINT64_C(1)<<(N));
}
/// isIntN - Checks if an signed integer fits into the given (dynamic)
return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1)));
}
-/// isMask_32 - This function returns true if the argument is a sequence of ones
-/// starting at the least significant bit with the remainder zero (32 bit
-/// version). Ex. isMask_32(0x0000FFFFU) == true.
+/// isMask_32 - This function returns true if the argument is a non-empty
+/// sequence of ones starting at the least significant bit with the remainder
+/// zero (32 bit version). Ex. isMask_32(0x0000FFFFU) == true.
inline bool isMask_32(uint32_t Value) {
return Value && ((Value + 1) & Value) == 0;
}
-/// isMask_64 - This function returns true if the argument is a sequence of ones
-/// starting at the least significant bit with the remainder zero (64 bit
-/// version).
+/// isMask_64 - This function returns true if the argument is a non-empty
+/// sequence of ones starting at the least significant bit with the remainder
+/// zero (64 bit version).
inline bool isMask_64(uint64_t Value) {
return Value && ((Value + 1) & Value) == 0;
}
/// isShiftedMask_32 - This function returns true if the argument contains a
-/// sequence of ones with the remainder zero (32 bit version.)
+/// non-empty sequence of ones with the remainder zero (32 bit version.)
/// Ex. isShiftedMask_32(0x0000FF00U) == true.
inline bool isShiftedMask_32(uint32_t Value) {
- return isMask_32((Value - 1) | Value);
+ return Value && isMask_32((Value - 1) | Value);
}
/// isShiftedMask_64 - This function returns true if the argument contains a
-/// sequence of ones with the remainder zero (64 bit version.)
+/// non-empty sequence of ones with the remainder zero (64 bit version.)
inline bool isShiftedMask_64(uint64_t Value) {
- return isMask_64((Value - 1) | Value);
+ return Value && isMask_64((Value - 1) | Value);
}
/// isPowerOf2_32 - This function returns true if the argument is a power of
return detail::PopulationCounter<T, sizeof(T)>::count(Value);
}
+/// Log2 - This function returns the log base 2 of the specified value
+inline double Log2(double Value) {
+#if defined(__ANDROID_API__) && __ANDROID_API__ < 18
+ return __builtin_log(Value) / __builtin_log(2.0);
+#else
+ return log2(Value);
+#endif
+}
+
/// Log2_32 - This function returns the floor log base 2 of the specified value,
/// -1 if the value is zero. (32 bit edition.)
/// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2
inline uint64_t MinAlign(uint64_t A, uint64_t B) {
// The largest power of 2 that divides both A and B.
//
- // Replace "-Value" by "1+~Value" in the following commented code to avoid
+ // Replace "-Value" by "1+~Value" in the following commented code to avoid
// MSVC warning C4146
// return (A | B) & -(A | B);
return (A | B) & (1 + ~(A | B));
///
/// Alignment should be a power of two. This method rounds up, so
/// alignAddr(7, 4) == 8 and alignAddr(8, 4) == 8.
-inline uintptr_t alignAddr(void *Addr, size_t Alignment) {
+inline uintptr_t alignAddr(const void *Addr, size_t Alignment) {
assert(Alignment && isPowerOf2_64((uint64_t)Alignment) &&
"Alignment is not a power of two!");
/// \brief Returns the necessary adjustment for aligning \c Ptr to \c Alignment
/// bytes, rounding up.
-inline size_t alignmentAdjustment(void *Ptr, size_t Alignment) {
+inline size_t alignmentAdjustment(const void *Ptr, size_t Alignment) {
return alignAddr(Ptr, Alignment) - (uintptr_t)Ptr;
}
/// Returns the next integer (mod 2**64) that is greater than or equal to
/// \p Value and is a multiple of \p Align. \p Align must be non-zero.
///
+/// If non-zero \p Skew is specified, the return value will be a minimal
+/// integer that is greater than or equal to \p Value and equal to
+/// \p Align * N + \p Skew for some integer N. If \p Skew is larger than
+/// \p Align, its value is adjusted to '\p Skew mod \p Align'.
+///
/// Examples:
/// \code
/// RoundUpToAlignment(5, 8) = 8
/// RoundUpToAlignment(17, 8) = 24
/// RoundUpToAlignment(~0LL, 8) = 0
/// RoundUpToAlignment(321, 255) = 510
+///
+/// RoundUpToAlignment(5, 8, 7) = 7
+/// RoundUpToAlignment(17, 8, 1) = 17
+/// RoundUpToAlignment(~0LL, 8, 3) = 3
+/// RoundUpToAlignment(321, 255, 42) = 552
/// \endcode
-inline uint64_t RoundUpToAlignment(uint64_t Value, uint64_t Align) {
- return (Value + Align - 1) / Align * Align;
+inline uint64_t RoundUpToAlignment(uint64_t Value, uint64_t Align,
+ uint64_t Skew = 0) {
+ Skew %= Align;
+ return (Value + Align - 1 - Skew) / Align * Align + Skew;
}
/// Returns the offset to the next integer (mod 2**64) that is greater than
return int64_t(X << (64 - B)) >> (64 - B);
}
+/// \brief Add two unsigned integers, X and Y, of type T.
+/// Clamp the result to the maximum representable value of T on overflow.
+/// ResultOverflowed indicates if the result is larger than the maximum
+/// representable value of type T.
+template <typename T>
+typename std::enable_if<std::is_unsigned<T>::value, T>::type
+SaturatingAdd(T X, T Y, bool *ResultOverflowed = nullptr) {
+ bool Dummy;
+ bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
+ // Hacker's Delight, p. 29
+ T Z = X + Y;
+ Overflowed = (Z < X || Z < Y);
+ if (Overflowed)
+ return std::numeric_limits<T>::max();
+ else
+ return Z;
+}
+
+/// \brief Multiply two unsigned integers, X and Y, of type T.
+/// Clamp the result to the maximum representable value of T on overflow.
+/// ResultOverflowed indicates if the result is larger than the maximum
+/// representable value of type T.
+template <typename T>
+typename std::enable_if<std::is_unsigned<T>::value, T>::type
+SaturatingMultiply(T X, T Y, bool *ResultOverflowed = nullptr) {
+ bool Dummy;
+ bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
+
+ // Hacker's Delight, p. 30 has a different algorithm, but we don't use that
+ // because it fails for uint16_t (where multiplication can have undefined
+ // behavior due to promotion to int), and requires a division in addition
+ // to the multiplication.
+
+ Overflowed = false;
+
+ // Log2(Z) would be either Log2Z or Log2Z + 1.
+ // Special case: if X or Y is 0, Log2_64 gives -1, and Log2Z
+ // will necessarily be less than Log2Max as desired.
+ int Log2Z = Log2_64(X) + Log2_64(Y);
+ const T Max = std::numeric_limits<T>::max();
+ int Log2Max = Log2_64(Max);
+ if (Log2Z < Log2Max) {
+ return X * Y;
+ }
+ if (Log2Z > Log2Max) {
+ Overflowed = true;
+ return Max;
+ }
+
+ // We're going to use the top bit, and maybe overflow one
+ // bit past it. Multiply all but the bottom bit then add
+ // that on at the end.
+ T Z = (X >> 1) * Y;
+ if (Z & ~(Max >> 1)) {
+ Overflowed = true;
+ return Max;
+ }
+ Z <<= 1;
+ if (X & 1)
+ return SaturatingAdd(Z, Y, ResultOverflowed);
+
+ return Z;
+}
+
extern const float huge_valf;
} // End llvm namespace
projects / oota-llvm.git / blobdiff