Jan Voung | 8acded0 | 2014-09-22 18:02:25 -0700 | [diff] [blame] | 1 | //===- subzero/src/IceUtils.h - Utility functions ---------------*- C++ -*-===// |
| 2 | // |
| 3 | // The Subzero Code Generator |
| 4 | // |
| 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
Andrew Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 9 | /// |
| 10 | /// \file |
Jim Stichnoth | 92a6e5b | 2015-12-02 16:52:44 -0800 | [diff] [blame] | 11 | /// \brief Defines some utility functions. |
Andrew Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 12 | /// |
Jan Voung | 8acded0 | 2014-09-22 18:02:25 -0700 | [diff] [blame] | 13 | //===----------------------------------------------------------------------===// |
| 14 | |
| 15 | #ifndef SUBZERO_SRC_ICEUTILS_H |
| 16 | #define SUBZERO_SRC_ICEUTILS_H |
John Porto | 67f8de9 | 2015-06-25 10:14:17 -0700 | [diff] [blame] | 17 | |
Jan Voung | 8acded0 | 2014-09-22 18:02:25 -0700 | [diff] [blame] | 18 | #include <climits> |
John Porto | ccea793 | 2015-11-17 04:58:36 -0800 | [diff] [blame] | 19 | #include <cmath> // std::signbit() |
Jan Voung | 8acded0 | 2014-09-22 18:02:25 -0700 | [diff] [blame] | 20 | |
| 21 | namespace Ice { |
Jim Stichnoth | b0051df | 2016-01-13 11:39:15 -0800 | [diff] [blame] | 22 | namespace Utils { |
Jan Voung | 8acded0 | 2014-09-22 18:02:25 -0700 | [diff] [blame] | 23 | |
Jim Stichnoth | b0051df | 2016-01-13 11:39:15 -0800 | [diff] [blame] | 24 | /// Allows copying from types of unrelated sizes. This method was introduced to |
| 25 | /// enable the strict aliasing optimizations of GCC 4.4. Basically, GCC |
| 26 | /// mindlessly relies on obscure details in the C++ standard that make |
| 27 | /// reinterpret_cast virtually useless. |
| 28 | template <typename D, typename S> inline D bitCopy(const S &Source) { |
| 29 | static_assert(sizeof(D) <= sizeof(S), |
| 30 | "bitCopy between incompatible type widths"); |
| 31 | static_assert(!std::is_pointer<S>::value, ""); |
| 32 | D Destination; |
Jan Voung | 8acded0 | 2014-09-22 18:02:25 -0700 | [diff] [blame] | 33 | // This use of memcpy is safe: source and destination cannot overlap. |
Jim Stichnoth | b0051df | 2016-01-13 11:39:15 -0800 | [diff] [blame] | 34 | memcpy(&Destination, reinterpret_cast<const void *>(&Source), sizeof(D)); |
| 35 | return Destination; |
Jan Voung | 8acded0 | 2014-09-22 18:02:25 -0700 | [diff] [blame] | 36 | } |
| 37 | |
Jim Stichnoth | b0051df | 2016-01-13 11:39:15 -0800 | [diff] [blame] | 38 | /// Check whether an N-bit two's-complement representation can hold value. |
Jim Stichnoth | 2f00bf6 | 2016-03-11 14:59:43 -0800 | [diff] [blame] | 39 | template <typename T> inline bool IsInt(int N, T value) { |
Jim Stichnoth | b0051df | 2016-01-13 11:39:15 -0800 | [diff] [blame] | 40 | assert((0 < N) && |
| 41 | (static_cast<unsigned int>(N) < (CHAR_BIT * sizeof(value)))); |
| 42 | T limit = static_cast<T>(1) << (N - 1); |
| 43 | return (-limit <= value) && (value < limit); |
| 44 | } |
Jim Stichnoth | c6ead20 | 2015-02-24 09:30:30 -0800 | [diff] [blame] | 45 | |
Jim Stichnoth | 2f00bf6 | 2016-03-11 14:59:43 -0800 | [diff] [blame] | 46 | template <typename T> inline bool IsUint(int N, T value) { |
Jim Stichnoth | b0051df | 2016-01-13 11:39:15 -0800 | [diff] [blame] | 47 | assert((0 < N) && |
| 48 | (static_cast<unsigned int>(N) < (CHAR_BIT * sizeof(value)))); |
| 49 | T limit = static_cast<T>(1) << N; |
| 50 | return (0 <= value) && (value < limit); |
| 51 | } |
Jan Voung | 8acded0 | 2014-09-22 18:02:25 -0700 | [diff] [blame] | 52 | |
Jim Stichnoth | b0051df | 2016-01-13 11:39:15 -0800 | [diff] [blame] | 53 | /// Check whether the magnitude of value fits in N bits, i.e., whether an |
| 54 | /// (N+1)-bit sign-magnitude representation can hold value. |
Jim Stichnoth | 2f00bf6 | 2016-03-11 14:59:43 -0800 | [diff] [blame] | 55 | template <typename T> inline bool IsAbsoluteUint(int N, T Value) { |
Jim Stichnoth | b0051df | 2016-01-13 11:39:15 -0800 | [diff] [blame] | 56 | assert((0 < N) && |
| 57 | (static_cast<unsigned int>(N) < (CHAR_BIT * sizeof(Value)))); |
| 58 | if (Value < 0) |
| 59 | Value = -Value; |
| 60 | return IsUint(N, Value); |
| 61 | } |
Jan Voung | 8acded0 | 2014-09-22 18:02:25 -0700 | [diff] [blame] | 62 | |
Jim Stichnoth | b0051df | 2016-01-13 11:39:15 -0800 | [diff] [blame] | 63 | /// Return true if the addition X + Y will cause integer overflow for integers |
| 64 | /// of type T. |
Jim Stichnoth | 2f00bf6 | 2016-03-11 14:59:43 -0800 | [diff] [blame] | 65 | template <typename T> inline bool WouldOverflowAdd(T X, T Y) { |
Jim Stichnoth | b0051df | 2016-01-13 11:39:15 -0800 | [diff] [blame] | 66 | return ((X > 0 && Y > 0 && (X > std::numeric_limits<T>::max() - Y)) || |
| 67 | (X < 0 && Y < 0 && (X < std::numeric_limits<T>::min() - Y))); |
| 68 | } |
Jan Voung | b2d5084 | 2015-05-12 09:53:50 -0700 | [diff] [blame] | 69 | |
Jim Stichnoth | b0051df | 2016-01-13 11:39:15 -0800 | [diff] [blame] | 70 | /// Adds x to y and stores the result in sum. Returns true if the addition |
| 71 | /// overflowed. |
Jim Stichnoth | 2f00bf6 | 2016-03-11 14:59:43 -0800 | [diff] [blame] | 72 | inline bool add_overflow(uint32_t x, uint32_t y, uint32_t *sum) { |
Jim Stichnoth | b0051df | 2016-01-13 11:39:15 -0800 | [diff] [blame] | 73 | static_assert(std::is_same<uint32_t, unsigned>::value, "Must match type"); |
Andrew Scull | aa6c109 | 2015-09-03 17:50:30 -0700 | [diff] [blame] | 74 | #if __has_builtin(__builtin_uadd_overflow) |
Jim Stichnoth | b0051df | 2016-01-13 11:39:15 -0800 | [diff] [blame] | 75 | return __builtin_uadd_overflow(x, y, sum); |
Andrew Scull | aa6c109 | 2015-09-03 17:50:30 -0700 | [diff] [blame] | 76 | #else |
Jim Stichnoth | b0051df | 2016-01-13 11:39:15 -0800 | [diff] [blame] | 77 | *sum = x + y; |
| 78 | return WouldOverflowAdd(x, y); |
Andrew Scull | aa6c109 | 2015-09-03 17:50:30 -0700 | [diff] [blame] | 79 | #endif |
Jim Stichnoth | b0051df | 2016-01-13 11:39:15 -0800 | [diff] [blame] | 80 | } |
Andrew Scull | aa6c109 | 2015-09-03 17:50:30 -0700 | [diff] [blame] | 81 | |
Jim Stichnoth | b0051df | 2016-01-13 11:39:15 -0800 | [diff] [blame] | 82 | /// Return true if X is already aligned by N, where N is a power of 2. |
Jim Stichnoth | 2f00bf6 | 2016-03-11 14:59:43 -0800 | [diff] [blame] | 83 | template <typename T> inline bool IsAligned(T X, intptr_t N) { |
Jim Stichnoth | b0051df | 2016-01-13 11:39:15 -0800 | [diff] [blame] | 84 | assert(llvm::isPowerOf2_64(N)); |
| 85 | return (X & (N - 1)) == 0; |
| 86 | } |
Jan Voung | b2d5084 | 2015-05-12 09:53:50 -0700 | [diff] [blame] | 87 | |
Jim Stichnoth | b0051df | 2016-01-13 11:39:15 -0800 | [diff] [blame] | 88 | /// Return Value adjusted to the next highest multiple of Alignment. |
Jim Stichnoth | 2f00bf6 | 2016-03-11 14:59:43 -0800 | [diff] [blame] | 89 | inline uint32_t applyAlignment(uint32_t Value, uint32_t Alignment) { |
Jim Stichnoth | b0051df | 2016-01-13 11:39:15 -0800 | [diff] [blame] | 90 | assert(llvm::isPowerOf2_32(Alignment)); |
| 91 | return (Value + Alignment - 1) & -Alignment; |
| 92 | } |
Jan Voung | 55500db | 2015-05-26 14:25:40 -0700 | [diff] [blame] | 93 | |
Jim Stichnoth | b0051df | 2016-01-13 11:39:15 -0800 | [diff] [blame] | 94 | /// Return amount which must be added to adjust Pos to the next highest |
| 95 | /// multiple of Align. |
Jim Stichnoth | 2f00bf6 | 2016-03-11 14:59:43 -0800 | [diff] [blame] | 96 | inline uint64_t OffsetToAlignment(uint64_t Pos, uint64_t Align) { |
Jim Stichnoth | b0051df | 2016-01-13 11:39:15 -0800 | [diff] [blame] | 97 | assert(llvm::isPowerOf2_64(Align)); |
| 98 | uint64_t Mod = Pos & (Align - 1); |
| 99 | if (Mod == 0) |
| 100 | return 0; |
| 101 | return Align - Mod; |
| 102 | } |
Jan Voung | b3401d2 | 2015-05-18 09:38:21 -0700 | [diff] [blame] | 103 | |
Jim Stichnoth | b0051df | 2016-01-13 11:39:15 -0800 | [diff] [blame] | 104 | /// Rotate the value bit pattern to the left by shift bits. |
| 105 | /// Precondition: 0 <= shift < 32 |
Jim Stichnoth | 2f00bf6 | 2016-03-11 14:59:43 -0800 | [diff] [blame] | 106 | inline uint32_t rotateLeft32(uint32_t value, uint32_t shift) { |
Jim Stichnoth | b0051df | 2016-01-13 11:39:15 -0800 | [diff] [blame] | 107 | if (shift == 0) |
| 108 | return value; |
| 109 | return (value << shift) | (value >> (32 - shift)); |
| 110 | } |
Jan Voung | b3401d2 | 2015-05-18 09:38:21 -0700 | [diff] [blame] | 111 | |
Jim Stichnoth | b0051df | 2016-01-13 11:39:15 -0800 | [diff] [blame] | 112 | /// Rotate the value bit pattern to the right by shift bits. |
Jim Stichnoth | 2f00bf6 | 2016-03-11 14:59:43 -0800 | [diff] [blame] | 113 | inline uint32_t rotateRight32(uint32_t value, uint32_t shift) { |
Jim Stichnoth | b0051df | 2016-01-13 11:39:15 -0800 | [diff] [blame] | 114 | if (shift == 0) |
| 115 | return value; |
| 116 | return (value >> shift) | (value << (32 - shift)); |
| 117 | } |
John Porto | ccea793 | 2015-11-17 04:58:36 -0800 | [diff] [blame] | 118 | |
Jim Stichnoth | b0051df | 2016-01-13 11:39:15 -0800 | [diff] [blame] | 119 | /// Returns true if Val is +0.0. It requires T to be a floating point type. |
Jim Stichnoth | 2f00bf6 | 2016-03-11 14:59:43 -0800 | [diff] [blame] | 120 | template <typename T> bool isPositiveZero(T Val) { |
Jim Stichnoth | b0051df | 2016-01-13 11:39:15 -0800 | [diff] [blame] | 121 | static_assert(std::is_floating_point<T>::value, |
| 122 | "Input type must be floating point"); |
| 123 | return Val == 0 && !std::signbit(Val); |
| 124 | } |
Jan Voung | 8acded0 | 2014-09-22 18:02:25 -0700 | [diff] [blame] | 125 | |
Jim Stichnoth | 2f00bf6 | 2016-03-11 14:59:43 -0800 | [diff] [blame] | 126 | /// Resize a vector (or other suitable container) to a particular size, and also |
| 127 | /// reserve possibly a larger size to avoid repeatedly recopying as the |
| 128 | /// container grows. It uses a strategy of doubling capacity up to a certain |
| 129 | /// point, after which it bumps the capacity by a fixed amount. |
| 130 | template <typename Container> |
| 131 | inline void reserveAndResize(Container &V, uint32_t Size, |
| 132 | uint32_t ChunkSizeBits = 10) { |
| 133 | #if __has_builtin(__builtin_clz) |
| 134 | // Don't call reserve() if Size==0. |
| 135 | if (Size > 0) { |
| 136 | uint32_t Mask; |
| 137 | if (Size <= (1 << ChunkSizeBits)) { |
| 138 | // For smaller sizes, reserve the smallest power of 2 greater than or |
| 139 | // equal to Size. |
| 140 | Mask = |
| 141 | ((1 << (CHAR_BIT * sizeof(uint32_t) - __builtin_clz(Size))) - 1) - 1; |
| 142 | } else { |
| 143 | // For larger sizes, round up to the smallest multiple of 1<<ChunkSizeBits |
| 144 | // greater than or equal to Size. |
| 145 | Mask = (1 << ChunkSizeBits) - 1; |
| 146 | } |
| 147 | V.reserve((Size + Mask) & ~Mask); |
| 148 | } |
| 149 | #endif |
| 150 | V.resize(Size); |
| 151 | } |
| 152 | |
Eric Holk | d6cf6b3 | 2016-02-17 11:09:48 -0800 | [diff] [blame] | 153 | /// An RAII class to ensure that a boolean flag is restored to its previous |
| 154 | /// value upon function exit. |
| 155 | /// |
| 156 | /// Used in places like RandomizationPoolingPause and generating target helper |
| 157 | /// calls. |
| 158 | class BoolFlagSaver { |
| 159 | BoolFlagSaver() = delete; |
| 160 | BoolFlagSaver(const BoolFlagSaver &) = delete; |
| 161 | BoolFlagSaver &operator=(const BoolFlagSaver &) = delete; |
| 162 | |
| 163 | public: |
| 164 | BoolFlagSaver(bool &F, bool NewValue) : OldValue(F), Flag(F) { F = NewValue; } |
| 165 | ~BoolFlagSaver() { Flag = OldValue; } |
| 166 | |
| 167 | private: |
| 168 | const bool OldValue; |
| 169 | bool &Flag; |
| 170 | }; |
| 171 | |
Jim Stichnoth | b0051df | 2016-01-13 11:39:15 -0800 | [diff] [blame] | 172 | } // end of namespace Utils |
Jan Voung | 8acded0 | 2014-09-22 18:02:25 -0700 | [diff] [blame] | 173 | } // end of namespace Ice |
| 174 | |
| 175 | #endif // SUBZERO_SRC_ICEUTILS_H |