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//===----------------------------------------------------------------------===//
9///
10/// \file
11/// \brief Defines some utility functions.
12///
13//===----------------------------------------------------------------------===//
14
15#ifndef SUBZERO_SRC_ICEUTILS_H
16#define SUBZERO_SRC_ICEUTILS_H
17
18#include <climits>
19#include <cmath> // std::signbit()
20
21namespace Ice {
22namespace Utils {
23
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.
28template <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;
33  // This use of memcpy is safe: source and destination cannot overlap.
34  memcpy(&Destination, reinterpret_cast<const void *>(&Source), sizeof(D));
35  return Destination;
36}
37
38/// Check whether an N-bit two's-complement representation can hold value.
39template <typename T> inline bool IsInt(int N, T value) {
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}
45
46template <typename T> inline bool IsUint(int N, T value) {
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}
52
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.
55template <typename T> inline bool IsAbsoluteUint(int N, T Value) {
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}
62
63/// Return true if the addition X + Y will cause integer overflow for integers
64/// of type T.
65template <typename T> inline bool WouldOverflowAdd(T X, T Y) {
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}
69
70/// Adds x to y and stores the result in sum. Returns true if the addition
71/// overflowed.
72inline bool add_overflow(uint32_t x, uint32_t y, uint32_t *sum) {
73  static_assert(std::is_same<uint32_t, unsigned>::value, "Must match type");
74#if __has_builtin(__builtin_uadd_overflow)
75  return __builtin_uadd_overflow(x, y, sum);
76#else
77  *sum = x + y;
78  return WouldOverflowAdd(x, y);
79#endif
80}
81
82/// Return true if X is already aligned by N, where N is a power of 2.
83template <typename T> inline bool IsAligned(T X, intptr_t N) {
84  assert(llvm::isPowerOf2_64(N));
85  return (X & (N - 1)) == 0;
86}
87
88/// Return Value adjusted to the next highest multiple of Alignment.
89inline uint32_t applyAlignment(uint32_t Value, uint32_t Alignment) {
90  assert(llvm::isPowerOf2_32(Alignment));
91  return (Value + Alignment - 1) & -Alignment;
92}
93
94/// Return amount which must be added to adjust Pos to the next highest
95/// multiple of Align.
96inline uint64_t OffsetToAlignment(uint64_t Pos, uint64_t Align) {
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}
103
104/// Rotate the value bit pattern to the left by shift bits.
105/// Precondition: 0 <= shift < 32
106inline uint32_t rotateLeft32(uint32_t value, uint32_t shift) {
107  if (shift == 0)
108    return value;
109  return (value << shift) | (value >> (32 - shift));
110}
111
112/// Rotate the value bit pattern to the right by shift bits.
113inline uint32_t rotateRight32(uint32_t value, uint32_t shift) {
114  if (shift == 0)
115    return value;
116  return (value >> shift) | (value << (32 - shift));
117}
118
119/// Returns true if Val is +0.0. It requires T to be a floating point type.
120template <typename T> bool isPositiveZero(T Val) {
121  static_assert(std::is_floating_point<T>::value,
122                "Input type must be floating point");
123  return Val == 0 && !std::signbit(Val);
124}
125
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.
130template <typename Container>
131inline 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
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.
158class BoolFlagSaver {
159  BoolFlagSaver() = delete;
160  BoolFlagSaver(const BoolFlagSaver &) = delete;
161  BoolFlagSaver &operator=(const BoolFlagSaver &) = delete;
162
163public:
164  BoolFlagSaver(bool &F, bool NewValue) : OldValue(F), Flag(F) { F = NewValue; }
165  ~BoolFlagSaver() { Flag = OldValue; }
166
167private:
168  const bool OldValue;
169  bool &Flag;
170};
171
172} // end of namespace Utils
173} // end of namespace Ice
174
175#endif // SUBZERO_SRC_ICEUTILS_H
176