BumpPtrAllocator: do the size check without moving any pointers
[oota-llvm.git] / include / llvm / Support / MathExtras.h
index ff41608f5f5178df0dbf17f2cd83187c438ea986..6a104e738fa7919b0f83bf89c60c3c7d642c8400 100644 (file)
@@ -16,9 +16,9 @@
 
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/SwapByteOrder.h"
-#include "llvm/Support/type_traits.h"
-
+#include <cassert>
 #include <cstring>
+#include <type_traits>
 
 #ifdef _MSC_VER
 #include <intrin.h>
@@ -44,8 +44,8 @@ enum ZeroBehavior {
 /// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are
 ///   valid arguments.
 template <typename T>
-typename enable_if_c<std::numeric_limits<T>::is_integer &&
-                     !std::numeric_limits<T>::is_signed, std::size_t>::type
+typename std::enable_if<std::numeric_limits<T>::is_integer &&
+                        !std::numeric_limits<T>::is_signed, std::size_t>::type
 countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
   (void)ZB;
 
@@ -71,8 +71,8 @@ countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
 
 // Disable signed.
 template <typename T>
-typename enable_if_c<std::numeric_limits<T>::is_integer &&
-                     std::numeric_limits<T>::is_signed, std::size_t>::type
+typename std::enable_if<std::numeric_limits<T>::is_integer &&
+                        std::numeric_limits<T>::is_signed, std::size_t>::type
 countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) LLVM_DELETED_FUNCTION;
 
 #if __GNUC__ >= 4 || _MSC_VER
@@ -115,8 +115,8 @@ inline std::size_t countTrailingZeros<uint64_t>(uint64_t Val, ZeroBehavior ZB) {
 /// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are
 ///   valid arguments.
 template <typename T>
-typename enable_if_c<std::numeric_limits<T>::is_integer &&
-                     !std::numeric_limits<T>::is_signed, std::size_t>::type
+typename std::enable_if<std::numeric_limits<T>::is_integer &&
+                        !std::numeric_limits<T>::is_signed, std::size_t>::type
 countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
   (void)ZB;
 
@@ -137,8 +137,8 @@ countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
 
 // Disable signed.
 template <typename T>
-typename enable_if_c<std::numeric_limits<T>::is_integer &&
-                     std::numeric_limits<T>::is_signed, std::size_t>::type
+typename std::enable_if<std::numeric_limits<T>::is_integer &&
+                        std::numeric_limits<T>::is_signed, std::size_t>::type
 countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) LLVM_DELETED_FUNCTION;
 
 #if __GNUC__ >= 4 || _MSC_VER
@@ -181,8 +181,8 @@ inline std::size_t countLeadingZeros<uint64_t>(uint64_t Val, ZeroBehavior ZB) {
 /// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
 ///   valid arguments.
 template <typename T>
-typename enable_if_c<std::numeric_limits<T>::is_integer &&
-                     !std::numeric_limits<T>::is_signed, T>::type
+typename std::enable_if<std::numeric_limits<T>::is_integer &&
+                       !std::numeric_limits<T>::is_signed, T>::type
 findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) {
   if (ZB == ZB_Max && Val == 0)
     return std::numeric_limits<T>::max();
@@ -192,8 +192,8 @@ findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) {
 
 // Disable signed.
 template <typename T>
-typename enable_if_c<std::numeric_limits<T>::is_integer &&
-                     std::numeric_limits<T>::is_signed, T>::type
+typename std::enable_if<std::numeric_limits<T>::is_integer &&
+                        std::numeric_limits<T>::is_signed, T>::type
 findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) LLVM_DELETED_FUNCTION;
 
 /// \brief Get the index of the last set bit starting from the least
@@ -204,8 +204,8 @@ findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) LLVM_DELETED_FUNCTION;
 /// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
 ///   valid arguments.
 template <typename T>
-typename enable_if_c<std::numeric_limits<T>::is_integer &&
-                     !std::numeric_limits<T>::is_signed, T>::type
+typename std::enable_if<std::numeric_limits<T>::is_integer &&
+                        !std::numeric_limits<T>::is_signed, T>::type
 findLastSet(T Val, ZeroBehavior ZB = ZB_Max) {
   if (ZB == ZB_Max && Val == 0)
     return std::numeric_limits<T>::max();
@@ -218,8 +218,8 @@ findLastSet(T Val, ZeroBehavior ZB = ZB_Max) {
 
 // Disable signed.
 template <typename T>
-typename enable_if_c<std::numeric_limits<T>::is_integer &&
-                     std::numeric_limits<T>::is_signed, T>::type
+typename std::enable_if<std::numeric_limits<T>::is_integer &&
+                        std::numeric_limits<T>::is_signed, T>::type
 findLastSet(T Val, ZeroBehavior ZB = ZB_Max) LLVM_DELETED_FUNCTION;
 
 /// \brief Macro compressed bit reversal table for 256 bits.
@@ -230,6 +230,9 @@ static const unsigned char BitReverseTable256[256] = {
 #define R4(n) R2(n), R2(n + 2 * 16), R2(n + 1 * 16), R2(n + 3 * 16)
 #define R6(n) R4(n), R4(n + 2 * 4), R4(n + 1 * 4), R4(n + 3 * 4)
   R6(0), R6(2), R6(1), R6(3)
+#undef R2
+#undef R4
+#undef R6
 };
 
 /// \brief Reverse the bits in \p Val.
@@ -258,6 +261,12 @@ inline uint32_t Lo_32(uint64_t Value) {
   return static_cast<uint32_t>(Value);
 }
 
+/// Make_64 - This functions makes a 64-bit integer from a high / low pair of
+///           32-bit integers.
+inline uint64_t Make_64(uint32_t High, uint32_t Low) {
+  return ((uint64_t)High << 32) | (uint64_t)Low;
+}
+
 /// isInt - Checks if an integer fits into the given bit width.
 template<unsigned N>
 inline bool isInt(int64_t x) {
@@ -541,6 +550,25 @@ inline uint64_t MinAlign(uint64_t A, uint64_t B) {
   return (A | B) & (1 + ~(A | B));
 }
 
+/// \brief Aligns \c Addr to \c Alignment bytes, rounding up.
+///
+/// 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) {
+  assert(Alignment && isPowerOf2_64((uint64_t)Alignment) &&
+         "Alignment is not a power of two!");
+
+  assert((uintptr_t)Addr + Alignment - 1 >= (uintptr_t)Addr);
+
+  return (((uintptr_t)Addr + Alignment - 1) & ~(uintptr_t)(Alignment - 1));
+}
+
+/// \brief Returns the necessary adjustment for aligning \c Ptr to \c Alignment
+/// bytes, rounding up.
+inline size_t alignmentAdjustment(void *Ptr, size_t Alignment) {
+  return alignAddr(Ptr, Alignment) - (uintptr_t)Ptr;
+}
+
 /// NextPowerOf2 - Returns the next power of two (in 64-bits)
 /// that is strictly greater than A.  Returns zero on overflow.
 inline uint64_t NextPowerOf2(uint64_t A) {
@@ -553,6 +581,13 @@ inline uint64_t NextPowerOf2(uint64_t A) {
   return A + 1;
 }
 
+/// Returns the power of two which is less than or equal to the given value.
+/// Essentially, it is a floor operation across the domain of powers of two.
+inline uint64_t PowerOf2Floor(uint64_t A) {
+  if (!A) return 0;
+  return 1ull << (63 - countLeadingZeros(A, ZB_Undefined));
+}
+
 /// 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.
 ///