Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/include/llvm/Support/MathExtras.h
Line
Count
Source (jump to first uncovered line)
1
//===-- llvm/Support/MathExtras.h - Useful math functions -------*- C++ -*-===//
2
//
3
//                     The LLVM Compiler Infrastructure
4
//
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
7
//
8
//===----------------------------------------------------------------------===//
9
//
10
// This file contains some functions that are useful for math stuff.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#ifndef LLVM_SUPPORT_MATHEXTRAS_H
15
#define LLVM_SUPPORT_MATHEXTRAS_H
16
17
#include "llvm/Support/Compiler.h"
18
#include "llvm/Support/SwapByteOrder.h"
19
#include <algorithm>
20
#include <cassert>
21
#include <climits>
22
#include <cstring>
23
#include <limits>
24
#include <type_traits>
25
26
#ifdef _MSC_VER
27
#include <intrin.h>
28
#endif
29
30
#ifdef __ANDROID_NDK__
31
#include <android/api-level.h>
32
#endif
33
34
namespace llvm {
35
/// \brief The behavior an operation has on an input of 0.
36
enum ZeroBehavior {
37
  /// \brief The returned value is undefined.
38
  ZB_Undefined,
39
  /// \brief The returned value is numeric_limits<T>::max()
40
  ZB_Max,
41
  /// \brief The returned value is numeric_limits<T>::digits
42
  ZB_Width
43
};
44
45
namespace detail {
46
template <typename T, std::size_t SizeOfT> struct TrailingZerosCounter {
47
159
  static std::size_t count(T Val, ZeroBehavior) {
48
159
    if (!Val)
49
1
      return std::numeric_limits<T>::digits;
50
158
    
if (158
Val & 0x1158
)
51
29
      return 0;
52
158
53
158
    // Bisection method.
54
129
    std::size_t ZeroBits = 0;
55
129
    T Shift = std::numeric_limits<T>::digits >> 1;
56
129
    T Mask = std::numeric_limits<T>::max() >> Shift;
57
516
    while (
Shift516
) {
58
387
      if (
(Val & Mask) == 0387
) {
59
206
        Val >>= Shift;
60
206
        ZeroBits |= Shift;
61
206
      }
62
387
      Shift >>= 1;
63
387
      Mask >>= Shift;
64
387
    }
65
129
    return ZeroBits;
66
159
  }
67
};
68
69
#if __GNUC__ >= 4 || defined(_MSC_VER)
70
template <typename T> struct TrailingZerosCounter<T, 4> {
71
77.8M
  static std::size_t count(T Val, ZeroBehavior ZB) {
72
77.8M
    if (
ZB != ZB_Undefined && 77.8M
Val == 077.8M
)
73
338
      return 32;
74
77.8M
75
77.8M
#if __has_builtin(__builtin_ctz) || LLVM_GNUC_PREREQ(4, 0, 0)
76
77.8M
    return __builtin_ctz(Val);
77
#elif defined(_MSC_VER)
78
    unsigned long Index;
79
    _BitScanForward(&Index, Val);
80
    return Index;
81
#endif
82
  }
83
};
84
85
#if !defined(_MSC_VER) || defined(_M_X64)
86
template <typename T> struct TrailingZerosCounter<T, 8> {
87
648M
  static std::size_t count(T Val, ZeroBehavior ZB) {
88
648M
    if (
ZB != ZB_Undefined && 648M
Val == 0585M
)
89
55.7M
      return 64;
90
648M
91
648M
#if __has_builtin(__builtin_ctzll) || LLVM_GNUC_PREREQ(4, 0, 0)
92
592M
    return __builtin_ctzll(Val);
93
#elif defined(_MSC_VER)
94
    unsigned long Index;
95
    _BitScanForward64(&Index, Val);
96
    return Index;
97
#endif
98
  }
llvm::detail::TrailingZerosCounter<unsigned long long, 8ul>::count(unsigned long long, llvm::ZeroBehavior)
Line
Count
Source
87
469M
  static std::size_t count(T Val, ZeroBehavior ZB) {
88
469M
    if (
ZB != ZB_Undefined && 469M
Val == 0406M
)
89
55.7M
      return 64;
90
469M
91
469M
#if __has_builtin(__builtin_ctzll) || LLVM_GNUC_PREREQ(4, 0, 0)
92
413M
    return __builtin_ctzll(Val);
93
#elif defined(_MSC_VER)
94
    unsigned long Index;
95
    _BitScanForward64(&Index, Val);
96
    return Index;
97
#endif
98
  }
llvm::detail::TrailingZerosCounter<unsigned long, 8ul>::count(unsigned long, llvm::ZeroBehavior)
Line
Count
Source
87
178M
  static std::size_t count(T Val, ZeroBehavior ZB) {
88
178M
    if (
ZB != ZB_Undefined && 178M
Val == 0178M
)
89
0
      return 64;
90
178M
91
178M
#if __has_builtin(__builtin_ctzll) || LLVM_GNUC_PREREQ(4, 0, 0)
92
178M
    return __builtin_ctzll(Val);
93
#elif defined(_MSC_VER)
94
    unsigned long Index;
95
    _BitScanForward64(&Index, Val);
96
    return Index;
97
#endif
98
  }
99
};
100
#endif
101
#endif
102
} // namespace detail
103
104
/// \brief Count number of 0's from the least significant bit to the most
105
///   stopping at the first 1.
106
///
107
/// Only unsigned integral types are allowed.
108
///
109
/// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are
110
///   valid arguments.
111
template <typename T>
112
726M
std::size_t countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
113
726M
  static_assert(std::numeric_limits<T>::is_integer &&
114
726M
                    !std::numeric_limits<T>::is_signed,
115
726M
                "Only unsigned integral types are allowed.");
116
726M
  return llvm::detail::TrailingZerosCounter<T, sizeof(T)>::count(Val, ZB);
117
726M
}
unsigned long llvm::countTrailingZeros<unsigned char>(unsigned char, llvm::ZeroBehavior)
Line
Count
Source
112
159
std::size_t countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
113
159
  static_assert(std::numeric_limits<T>::is_integer &&
114
159
                    !std::numeric_limits<T>::is_signed,
115
159
                "Only unsigned integral types are allowed.");
116
159
  return llvm::detail::TrailingZerosCounter<T, sizeof(T)>::count(Val, ZB);
117
159
}
unsigned long llvm::countTrailingZeros<unsigned long long>(unsigned long long, llvm::ZeroBehavior)
Line
Count
Source
112
469M
std::size_t countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
113
469M
  static_assert(std::numeric_limits<T>::is_integer &&
114
469M
                    !std::numeric_limits<T>::is_signed,
115
469M
                "Only unsigned integral types are allowed.");
116
469M
  return llvm::detail::TrailingZerosCounter<T, sizeof(T)>::count(Val, ZB);
117
469M
}
unsigned long llvm::countTrailingZeros<unsigned long>(unsigned long, llvm::ZeroBehavior)
Line
Count
Source
112
178M
std::size_t countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
113
178M
  static_assert(std::numeric_limits<T>::is_integer &&
114
178M
                    !std::numeric_limits<T>::is_signed,
115
178M
                "Only unsigned integral types are allowed.");
116
178M
  return llvm::detail::TrailingZerosCounter<T, sizeof(T)>::count(Val, ZB);
117
178M
}
unsigned long llvm::countTrailingZeros<unsigned int>(unsigned int, llvm::ZeroBehavior)
Line
Count
Source
112
77.8M
std::size_t countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
113
77.8M
  static_assert(std::numeric_limits<T>::is_integer &&
114
77.8M
                    !std::numeric_limits<T>::is_signed,
115
77.8M
                "Only unsigned integral types are allowed.");
116
77.8M
  return llvm::detail::TrailingZerosCounter<T, sizeof(T)>::count(Val, ZB);
117
77.8M
}
118
119
namespace detail {
120
template <typename T, std::size_t SizeOfT> struct LeadingZerosCounter {
121
  static std::size_t count(T Val, ZeroBehavior) {
122
    if (!Val)
123
      return std::numeric_limits<T>::digits;
124
125
    // Bisection method.
126
    std::size_t ZeroBits = 0;
127
    for (T Shift = std::numeric_limits<T>::digits >> 1; Shift; Shift >>= 1) {
128
      T Tmp = Val >> Shift;
129
      if (Tmp)
130
        Val = Tmp;
131
      else
132
        ZeroBits |= Shift;
133
    }
134
    return ZeroBits;
135
  }
136
};
137
138
#if __GNUC__ >= 4 || defined(_MSC_VER)
139
template <typename T> struct LeadingZerosCounter<T, 4> {
140
141M
  static std::size_t count(T Val, ZeroBehavior ZB) {
141
141M
    if (
ZB != ZB_Undefined && 141M
Val == 0141M
)
142
50.6M
      return 32;
143
141M
144
141M
#if __has_builtin(__builtin_clz) || LLVM_GNUC_PREREQ(4, 0, 0)
145
90.9M
    return __builtin_clz(Val);
146
#elif defined(_MSC_VER)
147
    unsigned long Index;
148
    _BitScanReverse(&Index, Val);
149
    return Index ^ 31;
150
#endif
151
  }
152
};
153
154
#if !defined(_MSC_VER) || defined(_M_X64)
155
template <typename T> struct LeadingZerosCounter<T, 8> {
156
818M
  static std::size_t count(T Val, ZeroBehavior ZB) {
157
818M
    if (
ZB != ZB_Undefined && 818M
Val == 0810M
)
158
60.8M
      return 64;
159
818M
160
818M
#if __has_builtin(__builtin_clzll) || LLVM_GNUC_PREREQ(4, 0, 0)
161
758M
    return __builtin_clzll(Val);
162
#elif defined(_MSC_VER)
163
    unsigned long Index;
164
    _BitScanReverse64(&Index, Val);
165
    return Index ^ 63;
166
#endif
167
  }
168
};
169
#endif
170
#endif
171
} // namespace detail
172
173
/// \brief Count number of 0's from the most significant bit to the least
174
///   stopping at the first 1.
175
///
176
/// Only unsigned integral types are allowed.
177
///
178
/// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are
179
///   valid arguments.
180
template <typename T>
181
960M
std::size_t countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
182
960M
  static_assert(std::numeric_limits<T>::is_integer &&
183
960M
                    !std::numeric_limits<T>::is_signed,
184
960M
                "Only unsigned integral types are allowed.");
185
960M
  return llvm::detail::LeadingZerosCounter<T, sizeof(T)>::count(Val, ZB);
186
960M
}
unsigned long llvm::countLeadingZeros<unsigned int>(unsigned int, llvm::ZeroBehavior)
Line
Count
Source
181
141M
std::size_t countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
182
141M
  static_assert(std::numeric_limits<T>::is_integer &&
183
141M
                    !std::numeric_limits<T>::is_signed,
184
141M
                "Only unsigned integral types are allowed.");
185
141M
  return llvm::detail::LeadingZerosCounter<T, sizeof(T)>::count(Val, ZB);
186
141M
}
unsigned long llvm::countLeadingZeros<unsigned long long>(unsigned long long, llvm::ZeroBehavior)
Line
Count
Source
181
818M
std::size_t countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
182
818M
  static_assert(std::numeric_limits<T>::is_integer &&
183
818M
                    !std::numeric_limits<T>::is_signed,
184
818M
                "Only unsigned integral types are allowed.");
185
818M
  return llvm::detail::LeadingZerosCounter<T, sizeof(T)>::count(Val, ZB);
186
818M
}
187
188
/// \brief Get the index of the first set bit starting from the least
189
///   significant bit.
190
///
191
/// Only unsigned integral types are allowed.
192
///
193
/// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
194
///   valid arguments.
195
62.9M
template <typename T> T findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) {
196
62.9M
  if (
ZB == ZB_Max && 62.9M
Val == 062.9M
)
197
1
    return std::numeric_limits<T>::max();
198
62.9M
199
62.9M
  return countTrailingZeros(Val, ZB_Undefined);
200
62.9M
}
201
202
/// \brief Create a bitmask with the N right-most bits set to 1, and all other
203
/// bits set to 0.  Only unsigned types are allowed.
204
342M
template <typename T> T maskTrailingOnes(unsigned N) {
205
342M
  static_assert(std::is_unsigned<T>::value, "Invalid type!");
206
342M
  const unsigned Bits = CHAR_BIT * sizeof(T);
207
342M
  assert(N <= Bits && "Invalid bit index");
208
342M
  return N == 0 ? 
021.5M
:
(T(-1) >> (Bits - N))320M
;
209
342M
}
unsigned int llvm::maskTrailingOnes<unsigned int>(unsigned int)
Line
Count
Source
204
258
template <typename T> T maskTrailingOnes(unsigned N) {
205
258
  static_assert(std::is_unsigned<T>::value, "Invalid type!");
206
258
  const unsigned Bits = CHAR_BIT * sizeof(T);
207
258
  assert(N <= Bits && "Invalid bit index");
208
258
  return N == 0 ? 
02
:
(T(-1) >> (Bits - N))256
;
209
258
}
unsigned long llvm::maskTrailingOnes<unsigned long>(unsigned int)
Line
Count
Source
204
283M
template <typename T> T maskTrailingOnes(unsigned N) {
205
283M
  static_assert(std::is_unsigned<T>::value, "Invalid type!");
206
283M
  const unsigned Bits = CHAR_BIT * sizeof(T);
207
283M
  assert(N <= Bits && "Invalid bit index");
208
283M
  return N == 0 ? 
021.5M
:
(T(-1) >> (Bits - N))262M
;
209
283M
}
unsigned long long llvm::maskTrailingOnes<unsigned long long>(unsigned int)
Line
Count
Source
204
58.2M
template <typename T> T maskTrailingOnes(unsigned N) {
205
58.2M
  static_assert(std::is_unsigned<T>::value, "Invalid type!");
206
58.2M
  const unsigned Bits = CHAR_BIT * sizeof(T);
207
58.2M
  assert(N <= Bits && "Invalid bit index");
208
58.2M
  return N == 0 ? 
04
:
(T(-1) >> (Bits - N))58.2M
;
209
58.2M
}
210
211
/// \brief Create a bitmask with the N left-most bits set to 1, and all other
212
/// bits set to 0.  Only unsigned types are allowed.
213
233M
template <typename T> T maskLeadingOnes(unsigned N) {
214
233M
  return ~maskTrailingOnes<T>(CHAR_BIT * sizeof(T) - N);
215
233M
}
unsigned long long llvm::maskLeadingOnes<unsigned long long>(unsigned int)
Line
Count
Source
213
58.2M
template <typename T> T maskLeadingOnes(unsigned N) {
214
58.2M
  return ~maskTrailingOnes<T>(CHAR_BIT * sizeof(T) - N);
215
58.2M
}
unsigned long llvm::maskLeadingOnes<unsigned long>(unsigned int)
Line
Count
Source
213
174M
template <typename T> T maskLeadingOnes(unsigned N) {
214
174M
  return ~maskTrailingOnes<T>(CHAR_BIT * sizeof(T) - N);
215
174M
}
216
217
/// \brief Create a bitmask with the N right-most bits set to 0, and all other
218
/// bits set to 1.  Only unsigned types are allowed.
219
174M
template <typename T> T maskTrailingZeros(unsigned N) {
220
174M
  return maskLeadingOnes<T>(CHAR_BIT * sizeof(T) - N);
221
174M
}
unsigned long long llvm::maskTrailingZeros<unsigned long long>(unsigned int)
Line
Count
Source
219
462
template <typename T> T maskTrailingZeros(unsigned N) {
220
462
  return maskLeadingOnes<T>(CHAR_BIT * sizeof(T) - N);
221
462
}
unsigned long llvm::maskTrailingZeros<unsigned long>(unsigned int)
Line
Count
Source
219
174M
template <typename T> T maskTrailingZeros(unsigned N) {
220
174M
  return maskLeadingOnes<T>(CHAR_BIT * sizeof(T) - N);
221
174M
}
222
223
/// \brief Create a bitmask with the N left-most bits set to 0, and all other
224
/// bits set to 1.  Only unsigned types are allowed.
225
template <typename T> T maskLeadingZeros(unsigned N) {
226
  return maskTrailingOnes<T>(CHAR_BIT * sizeof(T) - N);
227
}
228
229
/// \brief Get the index of the last set bit starting from the least
230
///   significant bit.
231
///
232
/// Only unsigned integral types are allowed.
233
///
234
/// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are
235
///   valid arguments.
236
6.38M
template <typename T> T findLastSet(T Val, ZeroBehavior ZB = ZB_Max) {
237
6.38M
  if (
ZB == ZB_Max && 6.38M
Val == 06.38M
)
238
1
    return std::numeric_limits<T>::max();
239
6.38M
240
6.38M
  // Use ^ instead of - because both gcc and llvm can remove the associated ^
241
6.38M
  // in the __builtin_clz intrinsic on x86.
242
6.38M
  return countLeadingZeros(Val, ZB_Undefined) ^
243
6.38M
         (std::numeric_limits<T>::digits - 1);
244
6.38M
}
245
246
/// \brief Macro compressed bit reversal table for 256 bits.
247
///
248
/// http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
249
static const unsigned char BitReverseTable256[256] = {
250
#define R2(n) n, n + 2 * 64, n + 1 * 64, n + 3 * 64
251
#define R4(n) R2(n), R2(n + 2 * 16), R2(n + 1 * 16), R2(n + 3 * 16)
252
#define R6(n) R4(n), R4(n + 2 * 4), R4(n + 1 * 4), R4(n + 3 * 4)
253
  R6(0), R6(2), R6(1), R6(3)
254
#undef R2
255
#undef R4
256
#undef R6
257
};
258
259
/// \brief Reverse the bits in \p Val.
260
template <typename T>
261
15.1k
T reverseBits(T Val) {
262
15.1k
  unsigned char in[sizeof(Val)];
263
15.1k
  unsigned char out[sizeof(Val)];
264
15.1k
  std::memcpy(in, &Val, sizeof(Val));
265
76.3k
  for (unsigned i = 0; 
i < sizeof(Val)76.3k
;
++i61.1k
)
266
61.1k
    out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]];
267
15.1k
  std::memcpy(&Val, out, sizeof(Val));
268
15.1k
  return Val;
269
15.1k
}
unsigned long long llvm::reverseBits<unsigned long long>(unsigned long long)
Line
Count
Source
261
391
T reverseBits(T Val) {
262
391
  unsigned char in[sizeof(Val)];
263
391
  unsigned char out[sizeof(Val)];
264
391
  std::memcpy(in, &Val, sizeof(Val));
265
3.51k
  for (unsigned i = 0; 
i < sizeof(Val)3.51k
;
++i3.12k
)
266
3.12k
    out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]];
267
391
  std::memcpy(&Val, out, sizeof(Val));
268
391
  return Val;
269
391
}
unsigned short llvm::reverseBits<unsigned short>(unsigned short)
Line
Count
Source
261
191
T reverseBits(T Val) {
262
191
  unsigned char in[sizeof(Val)];
263
191
  unsigned char out[sizeof(Val)];
264
191
  std::memcpy(in, &Val, sizeof(Val));
265
573
  for (unsigned i = 0; 
i < sizeof(Val)573
;
++i382
)
266
382
    out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]];
267
191
  std::memcpy(&Val, out, sizeof(Val));
268
191
  return Val;
269
191
}
unsigned char llvm::reverseBits<unsigned char>(unsigned char)
Line
Count
Source
261
189
T reverseBits(T Val) {
262
189
  unsigned char in[sizeof(Val)];
263
189
  unsigned char out[sizeof(Val)];
264
189
  std::memcpy(in, &Val, sizeof(Val));
265
378
  for (unsigned i = 0; 
i < sizeof(Val)378
;
++i189
)
266
189
    out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]];
267
189
  std::memcpy(&Val, out, sizeof(Val));
268
189
  return Val;
269
189
}
int llvm::reverseBits<int>(int)
Line
Count
Source
261
12.3k
T reverseBits(T Val) {
262
12.3k
  unsigned char in[sizeof(Val)];
263
12.3k
  unsigned char out[sizeof(Val)];
264
12.3k
  std::memcpy(in, &Val, sizeof(Val));
265
61.9k
  for (unsigned i = 0; 
i < sizeof(Val)61.9k
;
++i49.5k
)
266
49.5k
    out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]];
267
12.3k
  std::memcpy(&Val, out, sizeof(Val));
268
12.3k
  return Val;
269
12.3k
}
unsigned int llvm::reverseBits<unsigned int>(unsigned int)
Line
Count
Source
261
1.98k
T reverseBits(T Val) {
262
1.98k
  unsigned char in[sizeof(Val)];
263
1.98k
  unsigned char out[sizeof(Val)];
264
1.98k
  std::memcpy(in, &Val, sizeof(Val));
265
9.94k
  for (unsigned i = 0; 
i < sizeof(Val)9.94k
;
++i7.95k
)
266
7.95k
    out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]];
267
1.98k
  std::memcpy(&Val, out, sizeof(Val));
268
1.98k
  return Val;
269
1.98k
}
270
271
// NOTE: The following support functions use the _32/_64 extensions instead of
272
// type overloading so that signed and unsigned integers can be used without
273
// ambiguity.
274
275
/// Return the high 32 bits of a 64 bit value.
276
1.63M
constexpr inline uint32_t Hi_32(uint64_t Value) {
277
1.63M
  return static_cast<uint32_t>(Value >> 32);
278
1.63M
}
279
280
/// Return the low 32 bits of a 64 bit value.
281
3.40M
constexpr inline uint32_t Lo_32(uint64_t Value) {
282
3.40M
  return static_cast<uint32_t>(Value);
283
3.40M
}
284
285
/// Make a 64-bit integer from a high / low pair of 32-bit integers.
286
1.46M
constexpr inline uint64_t Make_64(uint32_t High, uint32_t Low) {
287
1.46M
  return ((uint64_t)High << 32) | (uint64_t)Low;
288
1.46M
}
289
290
/// Checks if an integer fits into the given bit width.
291
38.6M
template <unsigned N> constexpr inline bool isInt(int64_t x) {
292
38.6M
  return N >= 64 || 
(-(INT64_C(1)<<(N-1)) <= x && 38.6M
x < (INT64_C(1)<<(N-1))37.8M
);
293
38.6M
}
bool llvm::isInt<7u>(long long)
Line
Count
Source
291
86
template <unsigned N> constexpr inline bool isInt(int64_t x) {
292
86
  return N >= 64 || 
(-(INT64_C(1)<<(N-1)) <= x && 86
x < (INT64_C(1)<<(N-1))86
);
293
86
}
bool llvm::isInt<34u>(long long)
Line
Count
Source
291
1.16k
template <unsigned N> constexpr inline bool isInt(int64_t x) {
292
1.16k
  return N >= 64 || 
(-(INT64_C(1)<<(N-1)) <= x && 1.16k
x < (INT64_C(1)<<(N-1))1.16k
);
293
1.16k
}
bool llvm::isInt<35u>(long long)
Line
Count
Source
291
953
template <unsigned N> constexpr inline bool isInt(int64_t x) {
292
953
  return N >= 64 || 
(-(INT64_C(1)<<(N-1)) <= x && 953
x < (INT64_C(1)<<(N-1))953
);
293
953
}
bool llvm::isInt<33u>(long long)
Line
Count
Source
291
2.23k
template <unsigned N> constexpr inline bool isInt(int64_t x) {
292
2.23k
  return N >= 64 || 
(-(INT64_C(1)<<(N-1)) <= x && 2.23k
x < (INT64_C(1)<<(N-1))2.20k
);
293
2.23k
}
bool llvm::isInt<9u>(long long)
Line
Count
Source
291
38.4M
template <unsigned N> constexpr inline bool isInt(int64_t x) {
292
38.4M
  return N >= 64 || 
(-(INT64_C(1)<<(N-1)) <= x && 38.4M
x < (INT64_C(1)<<(N-1))37.7M
);
293
38.4M
}
bool llvm::isInt<3u>(long long)
Line
Count
Source
291
80
template <unsigned N> constexpr inline bool isInt(int64_t x) {
292
80
  return N >= 64 || 
(-(INT64_C(1)<<(N-1)) <= x && 80
x < (INT64_C(1)<<(N-1))80
);
293
80
}
bool llvm::isInt<5u>(long long)
Line
Count
Source
291
163
template <unsigned N> constexpr inline bool isInt(int64_t x) {
292
163
  return N >= 64 || 
(-(INT64_C(1)<<(N-1)) <= x && 163
x < (INT64_C(1)<<(N-1))143
);
293
163
}
bool llvm::isInt<21u>(long long)
Line
Count
Source
291
218
template <unsigned N> constexpr inline bool isInt(int64_t x) {
292
218
  return N >= 64 || 
(-(INT64_C(1)<<(N-1)) <= x && 218
x < (INT64_C(1)<<(N-1))190
);
293
218
}
bool llvm::isInt<64u>(long long)
Line
Count
Source
291
115
template <unsigned N> constexpr inline bool isInt(int64_t x) {
292
0
  return N >= 64 || 
(-(INT64_C(1)<<(N-1)) <= x && 0
x < (INT64_C(1)<<(N-1))0
);
293
115
}
bool llvm::isInt<25u>(long long)
Line
Count
Source
291
72
template <unsigned N> constexpr inline bool isInt(int64_t x) {
292
72
  return N >= 64 || 
(-(INT64_C(1)<<(N-1)) <= x && 72
x < (INT64_C(1)<<(N-1))71
);
293
72
}
bool llvm::isInt<19u>(long long)
Line
Count
Source
291
21
template <unsigned N> constexpr inline bool isInt(int64_t x) {
292
21
  return N >= 64 || 
(-(INT64_C(1)<<(N-1)) <= x && 21
x < (INT64_C(1)<<(N-1))21
);
293
21
}
bool llvm::isInt<18u>(long long)
Line
Count
Source
291
8
template <unsigned N> constexpr inline bool isInt(int64_t x) {
292
8
  return N >= 64 || 
(-(INT64_C(1)<<(N-1)) <= x && 8
x < (INT64_C(1)<<(N-1))8
);
293
8
}
bool llvm::isInt<20u>(long long)
Line
Count
Source
291
21.7k
template <unsigned N> constexpr inline bool isInt(int64_t x) {
292
21.7k
  return N >= 64 || 
(-(INT64_C(1)<<(N-1)) <= x && 21.7k
x < (INT64_C(1)<<(N-1))21.1k
);
293
21.7k
}
bool llvm::isInt<31u>(long long)
Line
Count
Source
291
20.0k
template <unsigned N> constexpr inline bool isInt(int64_t x) {
292
20.0k
  return N >= 64 || 
(-(INT64_C(1)<<(N-1)) <= x && 20.0k
x < (INT64_C(1)<<(N-1))20.0k
);
293
20.0k
}
bool llvm::isInt<28u>(long long)
Line
Count
Source
291
27
template <unsigned N> constexpr inline bool isInt(int64_t x) {
292
27
  return N >= 64 || 
(-(INT64_C(1)<<(N-1)) <= x && 27
x < (INT64_C(1)<<(N-1))27
);
293
27
}
bool llvm::isInt<23u>(long long)
Line
Count
Source
291
1
template <unsigned N> constexpr inline bool isInt(int64_t x) {
292
1
  return N >= 64 || 
(-(INT64_C(1)<<(N-1)) <= x && 1
x < (INT64_C(1)<<(N-1))1
);
293
1
}
bool llvm::isInt<27u>(long long)
Line
Count
Source
291
4
template <unsigned N> constexpr inline bool isInt(int64_t x) {
292
4
  return N >= 64 || 
(-(INT64_C(1)<<(N-1)) <= x && 4
x < (INT64_C(1)<<(N-1))4
);
293
4
}
Unexecuted instantiation: bool llvm::isInt<22u>(long long)
bool llvm::isInt<4u>(long long)
Line
Count
Source
291
8.52k
template <unsigned N> constexpr inline bool isInt(int64_t x) {
292
8.52k
  return N >= 64 || 
(-(INT64_C(1)<<(N-1)) <= x && 8.52k
x < (INT64_C(1)<<(N-1))8.52k
);
293
8.52k
}
bool llvm::isInt<17u>(long long)
Line
Count
Source
291
1.30k
template <unsigned N> constexpr inline bool isInt(int64_t x) {
292
1.30k
  return N >= 64 || 
(-(INT64_C(1)<<(N-1)) <= x && 1.30k
x < (INT64_C(1)<<(N-1))1.30k
);
293
1.30k
}
bool llvm::isInt<24u>(long long)
Line
Count
Source
291
68
template <unsigned N> constexpr inline bool isInt(int64_t x) {
292
68
  return N >= 64 || 
(-(INT64_C(1)<<(N-1)) <= x && 68
x < (INT64_C(1)<<(N-1))68
);
293
68
}
bool llvm::isInt<11u>(long long)
Line
Count
Source
291
26.4k
template <unsigned N> constexpr inline bool isInt(int64_t x) {
292
26.4k
  return N >= 64 || 
(-(INT64_C(1)<<(N-1)) <= x && 26.4k
x < (INT64_C(1)<<(N-1))26.1k
);
293
26.4k
}
bool llvm::isInt<6u>(long long)
Line
Count
Source
291
64
template <unsigned N> constexpr inline bool isInt(int64_t x) {
292
64
  return N >= 64 || 
(-(INT64_C(1)<<(N-1)) <= x && 64
x < (INT64_C(1)<<(N-1))58
);
293
64
}
bool llvm::isInt<10u>(long long)
Line
Count
Source
291
920
template <unsigned N> constexpr inline bool isInt(int64_t x) {
292
920
  return N >= 64 || 
(-(INT64_C(1)<<(N-1)) <= x && 920
x < (INT64_C(1)<<(N-1))893
);
293
920
}
bool llvm::isInt<12u>(long long)
Line
Count
Source
291
135
template <unsigned N> constexpr inline bool isInt(int64_t x) {
292
135
  return N >= 64 || 
(-(INT64_C(1)<<(N-1)) <= x && 135
x < (INT64_C(1)<<(N-1))81
);
293
135
}
bool llvm::isInt<26u>(long long)
Line
Count
Source
291
14.1k
template <unsigned N> constexpr inline bool isInt(int64_t x) {
292
14.1k
  return N >= 64 || 
(-(INT64_C(1)<<(N-1)) <= x && 14.1k
x < (INT64_C(1)<<(N-1))14.1k
);
293
14.1k
}
bool llvm::isInt<13u>(long long)
Line
Count
Source
291
12.1k
template <unsigned N> constexpr inline bool isInt(int64_t x) {
292
12.1k
  return N >= 64 || 
(-(INT64_C(1)<<(N-1)) <= x && 12.1k
x < (INT64_C(1)<<(N-1))12.1k
);
293
12.1k
}
bool llvm::isInt<15u>(long long)
Line
Count
Source
291
4.20k
template <unsigned N> constexpr inline bool isInt(int64_t x) {
292
4.20k
  return N >= 64 || 
(-(INT64_C(1)<<(N-1)) <= x && 4.20k
x < (INT64_C(1)<<(N-1))4.20k
);
293
4.20k
}
294
// Template specializations to get better code for common cases.
295
146k
template <> constexpr inline bool isInt<8>(int64_t x) {
296
146k
  return static_cast<int8_t>(x) == x;
297
146k
}
298
289k
template <> constexpr inline bool isInt<16>(int64_t x) {
299
289k
  return static_cast<int16_t>(x) == x;
300
289k
}
301
3.00M
template <> constexpr inline bool isInt<32>(int64_t x) {
302
3.00M
  return static_cast<int32_t>(x) == x;
303
3.00M
}
304
305
/// Checks if a signed integer is an N bit number shifted left by S.
306
template <unsigned N, unsigned S>
307
12.2k
constexpr inline bool isShiftedInt(int64_t x) {
308
12.2k
  static_assert(
309
12.2k
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
310
12.2k
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
311
10.2k
  return isInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
312
12.2k
}
Unexecuted instantiation: bool llvm::isShiftedInt<7u, 2u>(long long)
bool llvm::isShiftedInt<10u, 2u>(long long)
Line
Count
Source
307
14
constexpr inline bool isShiftedInt(int64_t x) {
308
14
  static_assert(
309
14
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
310
14
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
311
6
  return isInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
312
14
}
bool llvm::isShiftedInt<10u, 1u>(long long)
Line
Count
Source
307
13
constexpr inline bool isShiftedInt(int64_t x) {
308
13
  static_assert(
309
13
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
310
13
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
311
5
  return isInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
312
13
}
bool llvm::isShiftedInt<7u, 0u>(long long)
Line
Count
Source
307
81
constexpr inline bool isShiftedInt(int64_t x) {
308
81
  static_assert(
309
81
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
310
81
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
311
71
  return isInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
312
81
}
bool llvm::isShiftedInt<6u, 0u>(long long)
Line
Count
Source
307
23
constexpr inline bool isShiftedInt(int64_t x) {
308
23
  static_assert(
309
23
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
310
23
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
311
23
  return isInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
312
23
}
bool llvm::isShiftedInt<10u, 0u>(long long)
Line
Count
Source
307
547
constexpr inline bool isShiftedInt(int64_t x) {
308
547
  static_assert(
309
547
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
310
547
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
311
453
  return isInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
312
547
}
bool llvm::isShiftedInt<8u, 0u>(long long)
Line
Count
Source
307
305
constexpr inline bool isShiftedInt(int64_t x) {
308
305
  static_assert(
309
305
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
310
305
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
311
228
  return isInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
312
305
}
bool llvm::isShiftedInt<4u, 3u>(long long)
Line
Count
Source
307
1
constexpr inline bool isShiftedInt(int64_t x) {
308
1
  static_assert(
309
1
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
310
1
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
311
1
  return isInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
312
1
}
bool llvm::isShiftedInt<29u, 3u>(long long)
Line
Count
Source
307
26
constexpr inline bool isShiftedInt(int64_t x) {
308
26
  static_assert(
309
26
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
310
26
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
311
26
  return isInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
312
26
}
bool llvm::isShiftedInt<30u, 2u>(long long)
Line
Count
Source
307
34
constexpr inline bool isShiftedInt(int64_t x) {
308
34
  static_assert(
309
34
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
310
34
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
311
34
  return isInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
312
34
}
bool llvm::isShiftedInt<4u, 2u>(long long)
Line
Count
Source
307
1
constexpr inline bool isShiftedInt(int64_t x) {
308
1
  static_assert(
309
1
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
310
1
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
311
1
  return isInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
312
1
}
bool llvm::isShiftedInt<4u, 1u>(long long)
Line
Count
Source
307
2
constexpr inline bool isShiftedInt(int64_t x) {
308
2
  static_assert(
309
2
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
310
2
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
311
2
  return isInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
312
2
}
bool llvm::isShiftedInt<4u, 0u>(long long)
Line
Count
Source
307
1
constexpr inline bool isShiftedInt(int64_t x) {
308
1
  static_assert(
309
1
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
310
1
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
311
1
  return isInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
312
1
}
bool llvm::isShiftedInt<32u, 1u>(long long)
Line
Count
Source
307
1.28k
constexpr inline bool isShiftedInt(int64_t x) {
308
1.28k
  static_assert(
309
1.28k
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
310
1.28k
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
311
1.28k
  return isInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
312
1.28k
}
bool llvm::isShiftedInt<9u, 0u>(long long)
Line
Count
Source
307
1.17k
constexpr inline bool isShiftedInt(int64_t x) {
308
1.17k
  static_assert(
309
1.17k
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
310
1.17k
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
311
615
  return isInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
312
1.17k
}
bool llvm::isShiftedInt<16u, 0u>(long long)
Line
Count
Source
307
1.35k
constexpr inline bool isShiftedInt(int64_t x) {
308
1.35k
  static_assert(
309
1.35k
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
310
1.35k
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
311
690
  return isInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
312
1.35k
}
bool llvm::isShiftedInt<32u, 3u>(long long)
Line
Count
Source
307
953
constexpr inline bool isShiftedInt(int64_t x) {
308
953
  static_assert(
309
953
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
310
953
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
311
953
  return isInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
312
953
}
bool llvm::isShiftedInt<32u, 2u>(long long)
Line
Count
Source
307
1.16k
constexpr inline bool isShiftedInt(int64_t x) {
308
1.16k
  static_assert(
309
1.16k
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
310
1.16k
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
311
1.16k
  return isInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
312
1.16k
}
bool llvm::isShiftedInt<32u, 0u>(long long)
Line
Count
Source
307
3.95k
constexpr inline bool isShiftedInt(int64_t x) {
308
3.95k
  static_assert(
309
3.95k
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
310
3.95k
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
311
3.94k
  return isInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
312
3.95k
}
bool llvm::isShiftedInt<6u, 3u>(long long)
Line
Count
Source
307
525
constexpr inline bool isShiftedInt(int64_t x) {
308
525
  static_assert(
309
525
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
310
525
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
311
507
  return isInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
312
525
}
bool llvm::isShiftedInt<10u, 3u>(long long)
Line
Count
Source
307
17
constexpr inline bool isShiftedInt(int64_t x) {
308
17
  static_assert(
309
17
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
310
17
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
311
9
  return isInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
312
17
}
bool llvm::isShiftedInt<11u, 0u>(long long)
Line
Count
Source
307
542
constexpr inline bool isShiftedInt(int64_t x) {
308
542
  static_assert(
309
542
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
310
542
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
311
66
  return isInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
312
542
}
bool llvm::isShiftedInt<12u, 0u>(long long)
Line
Count
Source
307
117
constexpr inline bool isShiftedInt(int64_t x) {
308
117
  static_assert(
309
117
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
310
117
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
311
29
  return isInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
312
117
}
bool llvm::isShiftedInt<19u, 2u>(long long)
Line
Count
Source
307
160
constexpr inline bool isShiftedInt(int64_t x) {
308
160
  static_assert(
309
160
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
310
160
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
311
104
  return isInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
312
160
}
Unexecuted instantiation: bool llvm::isShiftedInt<16u, 16u>(long long)
313
314
/// Checks if an unsigned integer fits into the given bit width.
315
///
316
/// This is written as two functions rather than as simply
317
///
318
///   return N >= 64 || X < (UINT64_C(1) << N);
319
///
320
/// to keep MSVC from (incorrectly) warning on isUInt<64> that we're shifting
321
/// left too many places.
322
template <unsigned N>
323
constexpr inline typename std::enable_if<(N < 64), bool>::type
324
2.70M
isUInt(uint64_t X) {
325
2.70M
  static_assert(N > 0, "isUInt<0> doesn't make sense");
326
2.70M
  return X < (UINT64_C(1) << (N));
327
2.70M
}
std::__1::enable_if<(2u) < (64), bool>::type llvm::isUInt<2u>(unsigned long long)
Line
Count
Source
324
2.42k
isUInt(uint64_t X) {
325
2.42k
  static_assert(N > 0, "isUInt<0> doesn't make sense");
326
2.42k
  return X < (UINT64_C(1) << (N));
327
2.42k
}
Unexecuted instantiation: std::__1::enable_if<(22u) < (64), bool>::type llvm::isUInt<22u>(unsigned long long)
Unexecuted instantiation: std::__1::enable_if<(29u) < (64), bool>::type llvm::isUInt<29u>(unsigned long long)
std::__1::enable_if<(15u) < (64), bool>::type llvm::isUInt<15u>(unsigned long long)
Line
Count
Source
324
7
isUInt(uint64_t X) {
325
7
  static_assert(N > 0, "isUInt<0> doesn't make sense");
326
7
  return X < (UINT64_C(1) << (N));
327
7
}
std::__1::enable_if<(33u) < (64), bool>::type llvm::isUInt<33u>(unsigned long long)
Line
Count
Source
324
44
isUInt(uint64_t X) {
325
44
  static_assert(N > 0, "isUInt<0> doesn't make sense");
326
44
  return X < (UINT64_C(1) << (N));
327
44
}
Unexecuted instantiation: std::__1::enable_if<(26u) < (64), bool>::type llvm::isUInt<26u>(unsigned long long)
std::__1::enable_if<(11u) < (64), bool>::type llvm::isUInt<11u>(unsigned long long)
Line
Count
Source
324
490
isUInt(uint64_t X) {
325
490
  static_assert(N > 0, "isUInt<0> doesn't make sense");
326
490
  return X < (UINT64_C(1) << (N));
327
490
}
std::__1::enable_if<(21u) < (64), bool>::type llvm::isUInt<21u>(unsigned long long)
Line
Count
Source
324
1
isUInt(uint64_t X) {
325
1
  static_assert(N > 0, "isUInt<0> doesn't make sense");
326
1
  return X < (UINT64_C(1) << (N));
327
1
}
std::__1::enable_if<(25u) < (64), bool>::type llvm::isUInt<25u>(unsigned long long)
Line
Count
Source
324
22
isUInt(uint64_t X) {
325
22
  static_assert(N > 0, "isUInt<0> doesn't make sense");
326
22
  return X < (UINT64_C(1) << (N));
327
22
}
std::__1::enable_if<(14u) < (64), bool>::type llvm::isUInt<14u>(unsigned long long)
Line
Count
Source
324
8
isUInt(uint64_t X) {
325
8
  static_assert(N > 0, "isUInt<0> doesn't make sense");
326
8
  return X < (UINT64_C(1) << (N));
327
8
}
std::__1::enable_if<(5u) < (64), bool>::type llvm::isUInt<5u>(unsigned long long)
Line
Count
Source
324
33.7k
isUInt(uint64_t X) {
325
33.7k
  static_assert(N > 0, "isUInt<0> doesn't make sense");
326
33.7k
  return X < (UINT64_C(1) << (N));
327
33.7k
}
std::__1::enable_if<(1u) < (64), bool>::type llvm::isUInt<1u>(unsigned long long)
Line
Count
Source
324
540
isUInt(uint64_t X) {
325
540
  static_assert(N > 0, "isUInt<0> doesn't make sense");
326
540
  return X < (UINT64_C(1) << (N));
327
540
}
std::__1::enable_if<(3u) < (64), bool>::type llvm::isUInt<3u>(unsigned long long)
Line
Count
Source
324
1.96k
isUInt(uint64_t X) {
325
1.96k
  static_assert(N > 0, "isUInt<0> doesn't make sense");
326
1.96k
  return X < (UINT64_C(1) << (N));
327
1.96k
}
std::__1::enable_if<(7u) < (64), bool>::type llvm::isUInt<7u>(unsigned long long)
Line
Count
Source
324
1.67k
isUInt(uint64_t X) {
325
1.67k
  static_assert(N > 0, "isUInt<0> doesn't make sense");
326
1.67k
  return X < (UINT64_C(1) << (N));
327
1.67k
}
std::__1::enable_if<(10u) < (64), bool>::type llvm::isUInt<10u>(unsigned long long)
Line
Count
Source
324
436
isUInt(uint64_t X) {
325
436
  static_assert(N > 0, "isUInt<0> doesn't make sense");
326
436
  return X < (UINT64_C(1) << (N));
327
436
}
std::__1::enable_if<(9u) < (64), bool>::type llvm::isUInt<9u>(unsigned long long)
Line
Count
Source
324
9.75k
isUInt(uint64_t X) {
325
9.75k
  static_assert(N > 0, "isUInt<0> doesn't make sense");
326
9.75k
  return X < (UINT64_C(1) << (N));
327
9.75k
}
std::__1::enable_if<(4u) < (64), bool>::type llvm::isUInt<4u>(unsigned long long)
Line
Count
Source
324
5.90k
isUInt(uint64_t X) {
325
5.90k
  static_assert(N > 0, "isUInt<0> doesn't make sense");
326
5.90k
  return X < (UINT64_C(1) << (N));
327
5.90k
}
std::__1::enable_if<(6u) < (64), bool>::type llvm::isUInt<6u>(unsigned long long)
Line
Count
Source
324
108k
isUInt(uint64_t X) {
325
108k
  static_assert(N > 0, "isUInt<0> doesn't make sense");
326
108k
  return X < (UINT64_C(1) << (N));
327
108k
}
std::__1::enable_if<(20u) < (64), bool>::type llvm::isUInt<20u>(unsigned long long)
Line
Count
Source
324
14.8k
isUInt(uint64_t X) {
325
14.8k
  static_assert(N > 0, "isUInt<0> doesn't make sense");
326
14.8k
  return X < (UINT64_C(1) << (N));
327
14.8k
}
std::__1::enable_if<(24u) < (64), bool>::type llvm::isUInt<24u>(unsigned long long)
Line
Count
Source
324
2.42M
isUInt(uint64_t X) {
325
2.42M
  static_assert(N > 0, "isUInt<0> doesn't make sense");
326
2.42M
  return X < (UINT64_C(1) << (N));
327
2.42M
}
std::__1::enable_if<(12u) < (64), bool>::type llvm::isUInt<12u>(unsigned long long)
Line
Count
Source
324
92.4k
isUInt(uint64_t X) {
325
92.4k
  static_assert(N > 0, "isUInt<0> doesn't make sense");
326
92.4k
  return X < (UINT64_C(1) << (N));
327
92.4k
}
328
template <unsigned N>
329
constexpr inline typename std::enable_if<N >= 64, bool>::type
330
isUInt(uint64_t X) {
331
  return true;
332
}
333
334
// Template specializations to get better code for common cases.
335
45.4k
template <> constexpr inline bool isUInt<8>(uint64_t x) {
336
45.4k
  return static_cast<uint8_t>(x) == x;
337
45.4k
}
338
4.82M
template <> constexpr inline bool isUInt<16>(uint64_t x) {
339
4.82M
  return static_cast<uint16_t>(x) == x;
340
4.82M
}
341
35.1k
template <> constexpr inline bool isUInt<32>(uint64_t x) {
342
35.1k
  return static_cast<uint32_t>(x) == x;
343
35.1k
}
344
345
/// Checks if a unsigned integer is an N bit number shifted left by S.
346
template <unsigned N, unsigned S>
347
5.61k
constexpr inline bool isShiftedUInt(uint64_t x) {
348
5.61k
  static_assert(
349
5.61k
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
350
5.61k
  static_assert(N + S <= 64,
351
5.61k
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
352
5.61k
  // Per the two static_asserts above, S must be strictly less than 64.  So
353
5.61k
  // 1 << S is not undefined behavior.
354
4.98k
  return isUInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
355
5.61k
}
bool llvm::isShiftedUInt<6u, 1u>(unsigned long long)
Line
Count
Source
347
217
constexpr inline bool isShiftedUInt(uint64_t x) {
348
217
  static_assert(
349
217
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
350
217
  static_assert(N + S <= 64,
351
217
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
352
217
  // Per the two static_asserts above, S must be strictly less than 64.  So
353
217
  // 1 << S is not undefined behavior.
354
217
  return isUInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
355
217
}
bool llvm::isShiftedUInt<12u, 12u>(unsigned long long)
Line
Count
Source
347
6
constexpr inline bool isShiftedUInt(uint64_t x) {
348
6
  static_assert(
349
6
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
350
6
  static_assert(N + S <= 64,
351
6
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
352
6
  // Per the two static_asserts above, S must be strictly less than 64.  So
353
6
  // 1 << S is not undefined behavior.
354
5
  return isUInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
355
6
}
bool llvm::isShiftedUInt<6u, 2u>(unsigned long long)
Line
Count
Source
347
1.16k
constexpr inline bool isShiftedUInt(uint64_t x) {
348
1.16k
  static_assert(
349
1.16k
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
350
1.16k
  static_assert(N + S <= 64,
351
1.16k
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
352
1.16k
  // Per the two static_asserts above, S must be strictly less than 64.  So
353
1.16k
  // 1 << S is not undefined behavior.
354
1.10k
  return isUInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
355
1.16k
}
Unexecuted instantiation: bool llvm::isShiftedUInt<6u, 3u>(unsigned long long)
bool llvm::isShiftedUInt<5u, 2u>(unsigned long long)
Line
Count
Source
347
653
constexpr inline bool isShiftedUInt(uint64_t x) {
348
653
  static_assert(
349
653
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
350
653
  static_assert(N + S <= 64,
351
653
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
352
653
  // Per the two static_asserts above, S must be strictly less than 64.  So
353
653
  // 1 << S is not undefined behavior.
354
506
  return isUInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
355
653
}
bool llvm::isShiftedUInt<4u, 2u>(unsigned long long)
Line
Count
Source
347
527
constexpr inline bool isShiftedUInt(uint64_t x) {
348
527
  static_assert(
349
527
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
350
527
  static_assert(N + S <= 64,
351
527
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
352
527
  // Per the two static_asserts above, S must be strictly less than 64.  So
353
527
  // 1 << S is not undefined behavior.
354
468
  return isUInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
355
527
}
bool llvm::isShiftedUInt<3u, 1u>(unsigned long long)
Line
Count
Source
347
167
constexpr inline bool isShiftedUInt(uint64_t x) {
348
167
  static_assert(
349
167
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
350
167
  static_assert(N + S <= 64,
351
167
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
352
167
  // Per the two static_asserts above, S must be strictly less than 64.  So
353
167
  // 1 << S is not undefined behavior.
354
165
  return isUInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
355
167
}
bool llvm::isShiftedUInt<5u, 3u>(unsigned long long)
Line
Count
Source
347
703
constexpr inline bool isShiftedUInt(uint64_t x) {
348
703
  static_assert(
349
703
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
350
703
  static_assert(N + S <= 64,
351
703
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
352
703
  // Per the two static_asserts above, S must be strictly less than 64.  So
353
703
  // 1 << S is not undefined behavior.
354
678
  return isUInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
355
703
}
bool llvm::isShiftedUInt<6u, 0u>(unsigned long long)
Line
Count
Source
347
640
constexpr inline bool isShiftedUInt(uint64_t x) {
348
640
  static_assert(
349
640
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
350
640
  static_assert(N + S <= 64,
351
640
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
352
640
  // Per the two static_asserts above, S must be strictly less than 64.  So
353
640
  // 1 << S is not undefined behavior.
354
535
  return isUInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
355
640
}
bool llvm::isShiftedUInt<5u, 0u>(unsigned long long)
Line
Count
Source
347
633
constexpr inline bool isShiftedUInt(uint64_t x) {
348
633
  static_assert(
349
633
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
350
633
  static_assert(N + S <= 64,
351
633
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
352
633
  // Per the two static_asserts above, S must be strictly less than 64.  So
353
633
  // 1 << S is not undefined behavior.
354
580
  return isUInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
355
633
}
bool llvm::isShiftedUInt<16u, 16u>(unsigned long long)
Line
Count
Source
347
29
constexpr inline bool isShiftedUInt(uint64_t x) {
348
29
  static_assert(
349
29
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
350
29
  static_assert(N + S <= 64,
351
29
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
352
29
  // Per the two static_asserts above, S must be strictly less than 64.  So
353
29
  // 1 << S is not undefined behavior.
354
29
  return isUInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
355
29
}
bool llvm::isShiftedUInt<22u, 10u>(unsigned long long)
Line
Count
Source
347
392
constexpr inline bool isShiftedUInt(uint64_t x) {
348
392
  static_assert(
349
392
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
350
392
  static_assert(N + S <= 64,
351
392
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
352
392
  // Per the two static_asserts above, S must be strictly less than 64.  So
353
392
  // 1 << S is not undefined behavior.
354
348
  return isUInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
355
392
}
bool llvm::isShiftedUInt<2u, 0u>(unsigned long long)
Line
Count
Source
347
76
constexpr inline bool isShiftedUInt(uint64_t x) {
348
76
  static_assert(
349
76
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
350
76
  static_assert(N + S <= 64,
351
76
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
352
76
  // Per the two static_asserts above, S must be strictly less than 64.  So
353
76
  // 1 << S is not undefined behavior.
354
76
  return isUInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
355
76
}
bool llvm::isShiftedUInt<8u, 8u>(unsigned long long)
Line
Count
Source
347
141
constexpr inline bool isShiftedUInt(uint64_t x) {
348
141
  static_assert(
349
141
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
350
141
  static_assert(N + S <= 64,
351
141
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
352
141
  // Per the two static_asserts above, S must be strictly less than 64.  So
353
141
  // 1 << S is not undefined behavior.
354
25
  return isUInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
355
141
}
bool llvm::isShiftedUInt<32u, 0u>(unsigned long long)
Line
Count
Source
347
134
constexpr inline bool isShiftedUInt(uint64_t x) {
348
134
  static_assert(
349
134
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
350
134
  static_assert(N + S <= 64,
351
134
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
352
134
  // Per the two static_asserts above, S must be strictly less than 64.  So
353
134
  // 1 << S is not undefined behavior.
354
123
  return isUInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
355
134
}
bool llvm::isShiftedUInt<3u, 0u>(unsigned long long)
Line
Count
Source
347
89
constexpr inline bool isShiftedUInt(uint64_t x) {
348
89
  static_assert(
349
89
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
350
89
  static_assert(N + S <= 64,
351
89
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
352
89
  // Per the two static_asserts above, S must be strictly less than 64.  So
353
89
  // 1 << S is not undefined behavior.
354
89
  return isUInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
355
89
}
Unexecuted instantiation: bool llvm::isShiftedUInt<8u, 0u>(unsigned long long)
bool llvm::isShiftedUInt<4u, 0u>(unsigned long long)
Line
Count
Source
347
10
constexpr inline bool isShiftedUInt(uint64_t x) {
348
10
  static_assert(
349
10
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
350
10
  static_assert(N + S <= 64,
351
10
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
352
10
  // Per the two static_asserts above, S must be strictly less than 64.  So
353
10
  // 1 << S is not undefined behavior.
354
10
  return isUInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
355
10
}
bool llvm::isShiftedUInt<16u, 0u>(unsigned long long)
Line
Count
Source
347
4
constexpr inline bool isShiftedUInt(uint64_t x) {
348
4
  static_assert(
349
4
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
350
4
  static_assert(N + S <= 64,
351
4
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
352
4
  // Per the two static_asserts above, S must be strictly less than 64.  So
353
4
  // 1 << S is not undefined behavior.
354
4
  return isUInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
355
4
}
bool llvm::isShiftedUInt<11u, 3u>(unsigned long long)
Line
Count
Source
347
8
constexpr inline bool isShiftedUInt(uint64_t x) {
348
8
  static_assert(
349
8
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
350
8
  static_assert(N + S <= 64,
351
8
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
352
8
  // Per the two static_asserts above, S must be strictly less than 64.  So
353
8
  // 1 << S is not undefined behavior.
354
8
  return isUInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
355
8
}
bool llvm::isShiftedUInt<23u, 2u>(unsigned long long)
Line
Count
Source
347
22
constexpr inline bool isShiftedUInt(uint64_t x) {
348
22
  static_assert(
349
22
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
350
22
  static_assert(N + S <= 64,
351
22
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
352
22
  // Per the two static_asserts above, S must be strictly less than 64.  So
353
22
  // 1 << S is not undefined behavior.
354
22
  return isUInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
355
22
}
356
357
/// Gets the maximum value for a N-bit unsigned integer.
358
86.4k
inline uint64_t maxUIntN(uint64_t N) {
359
86.4k
  assert(N > 0 && N <= 64 && "integer width out of range");
360
86.4k
361
86.4k
  // uint64_t(1) << 64 is undefined behavior, so we can't do
362
86.4k
  //   (uint64_t(1) << N) - 1
363
86.4k
  // without checking first that N != 64.  But this works and doesn't have a
364
86.4k
  // branch.
365
86.4k
  return UINT64_MAX >> (64 - N);
366
86.4k
}
367
368
/// Gets the minimum value for a N-bit signed integer.
369
2.16M
inline int64_t minIntN(int64_t N) {
370
2.16M
  assert(N > 0 && N <= 64 && "integer width out of range");
371
2.16M
372
2.16M
  return -(UINT64_C(1)<<(N-1));
373
2.16M
}
374
375
/// Gets the maximum value for a N-bit signed integer.
376
2.16M
inline int64_t maxIntN(int64_t N) {
377
2.16M
  assert(N > 0 && N <= 64 && "integer width out of range");
378
2.16M
379
2.16M
  // This relies on two's complement wraparound when N == 64, so we convert to
380
2.16M
  // int64_t only at the very end to avoid UB.
381
2.16M
  return (UINT64_C(1) << (N - 1)) - 1;
382
2.16M
}
383
384
/// Checks if an unsigned integer fits into the given (dynamic) bit width.
385
93.3k
inline bool isUIntN(unsigned N, uint64_t x) {
386
86.4k
  return N >= 64 || x <= maxUIntN(N);
387
93.3k
}
388
389
/// Checks if an signed integer fits into the given (dynamic) bit width.
390
3.60M
inline bool isIntN(unsigned N, int64_t x) {
391
2.16M
  return N >= 64 || 
(minIntN(N) <= x && 2.16M
x <= maxIntN(N)2.16M
);
392
3.60M
}
393
394
/// Return true if the argument is a non-empty sequence of ones starting at the
395
/// least significant bit with the remainder zero (32 bit version).
396
/// Ex. isMask_32(0x0000FFFFU) == true.
397
12.8k
constexpr inline bool isMask_32(uint32_t Value) {
398
12.8k
  return Value && ((Value + 1) & Value) == 0;
399
12.8k
}
400
401
/// Return true if the argument is a non-empty sequence of ones starting at the
402
/// least significant bit with the remainder zero (64 bit version).
403
5.57M
constexpr inline bool isMask_64(uint64_t Value) {
404
5.28M
  return Value && ((Value + 1) & Value) == 0;
405
5.57M
}
406
407
/// Return true if the argument contains a non-empty sequence of ones with the
408
/// remainder zero (32 bit version.) Ex. isShiftedMask_32(0x0000FF00U) == true.
409
6.75k
constexpr inline bool isShiftedMask_32(uint32_t Value) {
410
6.75k
  return Value && isMask_32((Value - 1) | Value);
411
6.75k
}
412
413
/// Return true if the argument contains a non-empty sequence of ones with the
414
/// remainder zero (64 bit version.)
415
4.41M
constexpr inline bool isShiftedMask_64(uint64_t Value) {
416
4.41M
  return Value && isMask_64((Value - 1) | Value);
417
4.41M
}
418
419
/// Return true if the argument is a power of two > 0.
420
/// Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.)
421
19.5M
constexpr inline bool isPowerOf2_32(uint32_t Value) {
422
19.5M
  return Value && !(Value & (Value - 1));
423
19.5M
}
424
425
/// Return true if the argument is a power of two > 0 (64 bit edition.)
426
106M
constexpr inline bool isPowerOf2_64(uint64_t Value) {
427
106M
  return Value && !(Value & (Value - 1));
428
106M
}
429
430
/// Return a byte-swapped representation of the 16-bit argument.
431
10.3k
inline uint16_t ByteSwap_16(uint16_t Value) {
432
10.3k
  return sys::SwapByteOrder_16(Value);
433
10.3k
}
434
435
/// Return a byte-swapped representation of the 32-bit argument.
436
56.1k
inline uint32_t ByteSwap_32(uint32_t Value) {
437
56.1k
  return sys::SwapByteOrder_32(Value);
438
56.1k
}
439
440
/// Return a byte-swapped representation of the 64-bit argument.
441
3.14k
inline uint64_t ByteSwap_64(uint64_t Value) {
442
3.14k
  return sys::SwapByteOrder_64(Value);
443
3.14k
}
444
445
/// \brief Count the number of ones from the most significant bit to the first
446
/// zero bit.
447
///
448
/// Ex. countLeadingOnes(0xFF0FFF00) == 8.
449
/// Only unsigned integral types are allowed.
450
///
451
/// \param ZB the behavior on an input of all ones. Only ZB_Width and
452
/// ZB_Undefined are valid arguments.
453
template <typename T>
454
89.9M
std::size_t countLeadingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
455
89.9M
  static_assert(std::numeric_limits<T>::is_integer &&
456
89.9M
                    !std::numeric_limits<T>::is_signed,
457
89.9M
                "Only unsigned integral types are allowed.");
458
89.9M
  return countLeadingZeros(~Value, ZB);
459
89.9M
}
unsigned long llvm::countLeadingOnes<unsigned long long>(unsigned long long, llvm::ZeroBehavior)
Line
Count
Source
454
89.9M
std::size_t countLeadingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
455
89.9M
  static_assert(std::numeric_limits<T>::is_integer &&
456
89.9M
                    !std::numeric_limits<T>::is_signed,
457
89.9M
                "Only unsigned integral types are allowed.");
458
89.9M
  return countLeadingZeros(~Value, ZB);
459
89.9M
}
unsigned long llvm::countLeadingOnes<unsigned int>(unsigned int, llvm::ZeroBehavior)
Line
Count
Source
454
73
std::size_t countLeadingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
455
73
  static_assert(std::numeric_limits<T>::is_integer &&
456
73
                    !std::numeric_limits<T>::is_signed,
457
73
                "Only unsigned integral types are allowed.");
458
73
  return countLeadingZeros(~Value, ZB);
459
73
}
460
461
/// \brief Count the number of ones from the least significant bit to the first
462
/// zero bit.
463
///
464
/// Ex. countTrailingOnes(0x00FF00FF) == 8.
465
/// Only unsigned integral types are allowed.
466
///
467
/// \param ZB the behavior on an input of all ones. Only ZB_Width and
468
/// ZB_Undefined are valid arguments.
469
template <typename T>
470
304M
std::size_t countTrailingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
471
304M
  static_assert(std::numeric_limits<T>::is_integer &&
472
304M
                    !std::numeric_limits<T>::is_signed,
473
304M
                "Only unsigned integral types are allowed.");
474
304M
  return countTrailingZeros(~Value, ZB);
475
304M
}
unsigned long llvm::countTrailingOnes<unsigned int>(unsigned int, llvm::ZeroBehavior)
Line
Count
Source
470
8.23k
std::size_t countTrailingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
471
8.23k
  static_assert(std::numeric_limits<T>::is_integer &&
472
8.23k
                    !std::numeric_limits<T>::is_signed,
473
8.23k
                "Only unsigned integral types are allowed.");
474
8.23k
  return countTrailingZeros(~Value, ZB);
475
8.23k
}
unsigned long llvm::countTrailingOnes<unsigned long long>(unsigned long long, llvm::ZeroBehavior)
Line
Count
Source
470
304M
std::size_t countTrailingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
471
304M
  static_assert(std::numeric_limits<T>::is_integer &&
472
304M
                    !std::numeric_limits<T>::is_signed,
473
304M
                "Only unsigned integral types are allowed.");
474
304M
  return countTrailingZeros(~Value, ZB);
475
304M
}
476
477
namespace detail {
478
template <typename T, std::size_t SizeOfT> struct PopulationCounter {
479
871k
  static unsigned count(T Value) {
480
871k
    // Generic version, forward to 32 bits.
481
871k
    static_assert(SizeOfT <= 4, "Not implemented!");
482
871k
#if __GNUC__ >= 4
483
871k
    return __builtin_popcount(Value);
484
#else
485
    uint32_t v = Value;
486
    v = v - ((v >> 1) & 0x55555555);
487
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
488
    return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
489
#endif
490
  }
llvm::detail::PopulationCounter<unsigned short, 2ul>::count(unsigned short)
Line
Count
Source
479
77
  static unsigned count(T Value) {
480
77
    // Generic version, forward to 32 bits.
481
77
    static_assert(SizeOfT <= 4, "Not implemented!");
482
77
#if __GNUC__ >= 4
483
77
    return __builtin_popcount(Value);
484
#else
485
    uint32_t v = Value;
486
    v = v - ((v >> 1) & 0x55555555);
487
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
488
    return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
489
#endif
490
  }
llvm::detail::PopulationCounter<unsigned int, 4ul>::count(unsigned int)
Line
Count
Source
479
864k
  static unsigned count(T Value) {
480
864k
    // Generic version, forward to 32 bits.
481
864k
    static_assert(SizeOfT <= 4, "Not implemented!");
482
864k
#if __GNUC__ >= 4
483
864k
    return __builtin_popcount(Value);
484
#else
485
    uint32_t v = Value;
486
    v = v - ((v >> 1) & 0x55555555);
487
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
488
    return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
489
#endif
490
  }
llvm::detail::PopulationCounter<unsigned char, 1ul>::count(unsigned char)
Line
Count
Source
479
6.70k
  static unsigned count(T Value) {
480
6.70k
    // Generic version, forward to 32 bits.
481
6.70k
    static_assert(SizeOfT <= 4, "Not implemented!");
482
6.70k
#if __GNUC__ >= 4
483
6.70k
    return __builtin_popcount(Value);
484
#else
485
    uint32_t v = Value;
486
    v = v - ((v >> 1) & 0x55555555);
487
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
488
    return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
489
#endif
490
  }
491
};
492
493
template <typename T> struct PopulationCounter<T, 8> {
494
285M
  static unsigned count(T Value) {
495
285M
#if __GNUC__ >= 4
496
285M
    return __builtin_popcountll(Value);
497
#else
498
    uint64_t v = Value;
499
    v = v - ((v >> 1) & 0x5555555555555555ULL);
500
    v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
501
    v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
502
    return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56);
503
#endif
504
  }
llvm::detail::PopulationCounter<unsigned long long, 8ul>::count(unsigned long long)
Line
Count
Source
494
277M
  static unsigned count(T Value) {
495
277M
#if __GNUC__ >= 4
496
277M
    return __builtin_popcountll(Value);
497
#else
498
    uint64_t v = Value;
499
    v = v - ((v >> 1) & 0x5555555555555555ULL);
500
    v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
501
    v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
502
    return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56);
503
#endif
504
  }
llvm::detail::PopulationCounter<unsigned long, 8ul>::count(unsigned long)
Line
Count
Source
494
8.51M
  static unsigned count(T Value) {
495
8.51M
#if __GNUC__ >= 4
496
8.51M
    return __builtin_popcountll(Value);
497
#else
498
    uint64_t v = Value;
499
    v = v - ((v >> 1) & 0x5555555555555555ULL);
500
    v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
501
    v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
502
    return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56);
503
#endif
504
  }
505
};
506
} // namespace detail
507
508
/// \brief Count the number of set bits in a value.
509
/// Ex. countPopulation(0xF000F000) = 8
510
/// Returns 0 if the word is zero.
511
template <typename T>
512
286M
inline unsigned countPopulation(T Value) {
513
286M
  static_assert(std::numeric_limits<T>::is_integer &&
514
286M
                    !std::numeric_limits<T>::is_signed,
515
286M
                "Only unsigned integral types are allowed.");
516
286M
  return detail::PopulationCounter<T, sizeof(T)>::count(Value);
517
286M
}
unsigned int llvm::countPopulation<unsigned char>(unsigned char)
Line
Count
Source
512
6.70k
inline unsigned countPopulation(T Value) {
513
6.70k
  static_assert(std::numeric_limits<T>::is_integer &&
514
6.70k
                    !std::numeric_limits<T>::is_signed,
515
6.70k
                "Only unsigned integral types are allowed.");
516
6.70k
  return detail::PopulationCounter<T, sizeof(T)>::count(Value);
517
6.70k
}
unsigned int llvm::countPopulation<unsigned short>(unsigned short)
Line
Count
Source
512
77
inline unsigned countPopulation(T Value) {
513
77
  static_assert(std::numeric_limits<T>::is_integer &&
514
77
                    !std::numeric_limits<T>::is_signed,
515
77
                "Only unsigned integral types are allowed.");
516
77
  return detail::PopulationCounter<T, sizeof(T)>::count(Value);
517
77
}
unsigned int llvm::countPopulation<unsigned int>(unsigned int)
Line
Count
Source
512
864k
inline unsigned countPopulation(T Value) {
513
864k
  static_assert(std::numeric_limits<T>::is_integer &&
514
864k
                    !std::numeric_limits<T>::is_signed,
515
864k
                "Only unsigned integral types are allowed.");
516
864k
  return detail::PopulationCounter<T, sizeof(T)>::count(Value);
517
864k
}
unsigned int llvm::countPopulation<unsigned long>(unsigned long)
Line
Count
Source
512
8.51M
inline unsigned countPopulation(T Value) {
513
8.51M
  static_assert(std::numeric_limits<T>::is_integer &&
514
8.51M
                    !std::numeric_limits<T>::is_signed,
515
8.51M
                "Only unsigned integral types are allowed.");
516
8.51M
  return detail::PopulationCounter<T, sizeof(T)>::count(Value);
517
8.51M
}
unsigned int llvm::countPopulation<unsigned long long>(unsigned long long)
Line
Count
Source
512
277M
inline unsigned countPopulation(T Value) {
513
277M
  static_assert(std::numeric_limits<T>::is_integer &&
514
277M
                    !std::numeric_limits<T>::is_signed,
515
277M
                "Only unsigned integral types are allowed.");
516
277M
  return detail::PopulationCounter<T, sizeof(T)>::count(Value);
517
277M
}
518
519
/// Return the log base 2 of the specified value.
520
0
inline double Log2(double Value) {
521
#if defined(__ANDROID_API__) && __ANDROID_API__ < 18
522
  return __builtin_log(Value) / __builtin_log(2.0);
523
#else
524
  return log2(Value);
525
0
#endif
526
0
}
527
528
/// Return the floor log base 2 of the specified value, -1 if the value is zero.
529
/// (32 bit edition.)
530
/// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2
531
65.3M
inline unsigned Log2_32(uint32_t Value) {
532
65.3M
  return 31 - countLeadingZeros(Value);
533
65.3M
}
534
535
/// Return the floor log base 2 of the specified value, -1 if the value is zero.
536
/// (64 bit edition.)
537
7.70M
inline unsigned Log2_64(uint64_t Value) {
538
7.70M
  return 63 - countLeadingZeros(Value);
539
7.70M
}
540
541
/// Return the ceil log base 2 of the specified value, 32 if the value is zero.
542
/// (32 bit edition).
543
/// Ex. Log2_32_Ceil(32) == 5, Log2_32_Ceil(1) == 0, Log2_32_Ceil(6) == 3
544
75.6M
inline unsigned Log2_32_Ceil(uint32_t Value) {
545
75.6M
  return 32 - countLeadingZeros(Value - 1);
546
75.6M
}
547
548
/// Return the ceil log base 2 of the specified value, 64 if the value is zero.
549
/// (64 bit edition.)
550
254M
inline unsigned Log2_64_Ceil(uint64_t Value) {
551
254M
  return 64 - countLeadingZeros(Value - 1);
552
254M
}
553
554
/// Return the greatest common divisor of the values using Euclid's algorithm.
555
159k
inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) {
556
452k
  while (
B452k
) {
557
293k
    uint64_t T = B;
558
293k
    B = A % B;
559
293k
    A = T;
560
293k
  }
561
159k
  return A;
562
159k
}
563
564
/// This function takes a 64-bit integer and returns the bit equivalent double.
565
26.4k
inline double BitsToDouble(uint64_t Bits) {
566
26.4k
  double D;
567
26.4k
  static_assert(sizeof(uint64_t) == sizeof(double), "Unexpected type sizes");
568
26.4k
  memcpy(&D, &Bits, sizeof(Bits));
569
26.4k
  return D;
570
26.4k
}
571
572
/// This function takes a 32-bit integer and returns the bit equivalent float.
573
33.5k
inline float BitsToFloat(uint32_t Bits) {
574
33.5k
  float F;
575
33.5k
  static_assert(sizeof(uint32_t) == sizeof(float), "Unexpected type sizes");
576
33.5k
  memcpy(&F, &Bits, sizeof(Bits));
577
33.5k
  return F;
578
33.5k
}
579
580
/// This function takes a double and returns the bit equivalent 64-bit integer.
581
/// Note that copying doubles around changes the bits of NaNs on some hosts,
582
/// notably x86, so this routine cannot be used if these bits are needed.
583
4.99M
inline uint64_t DoubleToBits(double Double) {
584
4.99M
  uint64_t Bits;
585
4.99M
  static_assert(sizeof(uint64_t) == sizeof(double), "Unexpected type sizes");
586
4.99M
  memcpy(&Bits, &Double, sizeof(Double));
587
4.99M
  return Bits;
588
4.99M
}
589
590
/// This function takes a float and returns the bit equivalent 32-bit integer.
591
/// Note that copying floats around changes the bits of NaNs on some hosts,
592
/// notably x86, so this routine cannot be used if these bits are needed.
593
2.74M
inline uint32_t FloatToBits(float Float) {
594
2.74M
  uint32_t Bits;
595
2.74M
  static_assert(sizeof(uint32_t) == sizeof(float), "Unexpected type sizes");
596
2.74M
  memcpy(&Bits, &Float, sizeof(Float));
597
2.74M
  return Bits;
598
2.74M
}
599
600
/// A and B are either alignments or offsets. Return the minimum alignment that
601
/// may be assumed after adding the two together.
602
46.2M
constexpr inline uint64_t MinAlign(uint64_t A, uint64_t B) {
603
46.2M
  // The largest power of 2 that divides both A and B.
604
46.2M
  //
605
46.2M
  // Replace "-Value" by "1+~Value" in the following commented code to avoid
606
46.2M
  // MSVC warning C4146
607
46.2M
  //    return (A | B) & -(A | B);
608
46.2M
  return (A | B) & (1 + ~(A | B));
609
46.2M
}
610
611
/// \brief Aligns \c Addr to \c Alignment bytes, rounding up.
612
///
613
/// Alignment should be a power of two.  This method rounds up, so
614
/// alignAddr(7, 4) == 8 and alignAddr(8, 4) == 8.
615
984M
inline uintptr_t alignAddr(const void *Addr, size_t Alignment) {
616
984M
  assert(Alignment && isPowerOf2_64((uint64_t)Alignment) &&
617
984M
         "Alignment is not a power of two!");
618
984M
619
984M
  assert((uintptr_t)Addr + Alignment - 1 >= (uintptr_t)Addr);
620
984M
621
984M
  return (((uintptr_t)Addr + Alignment - 1) & ~(uintptr_t)(Alignment - 1));
622
984M
}
623
624
/// \brief Returns the necessary adjustment for aligning \c Ptr to \c Alignment
625
/// bytes, rounding up.
626
967M
inline size_t alignmentAdjustment(const void *Ptr, size_t Alignment) {
627
967M
  return alignAddr(Ptr, Alignment) - (uintptr_t)Ptr;
628
967M
}
629
630
/// Returns the next power of two (in 64-bits) that is strictly greater than A.
631
/// Returns zero on overflow.
632
418M
inline uint64_t NextPowerOf2(uint64_t A) {
633
418M
  A |= (A >> 1);
634
418M
  A |= (A >> 2);
635
418M
  A |= (A >> 4);
636
418M
  A |= (A >> 8);
637
418M
  A |= (A >> 16);
638
418M
  A |= (A >> 32);
639
418M
  return A + 1;
640
418M
}
641
642
/// Returns the power of two which is less than or equal to the given value.
643
/// Essentially, it is a floor operation across the domain of powers of two.
644
2.38M
inline uint64_t PowerOf2Floor(uint64_t A) {
645
2.38M
  if (
!A2.38M
)
return 0435
;
646
2.38M
  return 1ull << (63 - countLeadingZeros(A, ZB_Undefined));
647
2.38M
}
648
649
/// Returns the power of two which is greater than or equal to the given value.
650
/// Essentially, it is a ceil operation across the domain of powers of two.
651
993k
inline uint64_t PowerOf2Ceil(uint64_t A) {
652
993k
  if (!A)
653
128
    return 0;
654
993k
  return NextPowerOf2(A - 1);
655
993k
}
656
657
/// Returns the next integer (mod 2**64) that is greater than or equal to
658
/// \p Value and is a multiple of \p Align. \p Align must be non-zero.
659
///
660
/// If non-zero \p Skew is specified, the return value will be a minimal
661
/// integer that is greater than or equal to \p Value and equal to
662
/// \p Align * N + \p Skew for some integer N. If \p Skew is larger than
663
/// \p Align, its value is adjusted to '\p Skew mod \p Align'.
664
///
665
/// Examples:
666
/// \code
667
///   alignTo(5, 8) = 8
668
///   alignTo(17, 8) = 24
669
///   alignTo(~0LL, 8) = 0
670
///   alignTo(321, 255) = 510
671
///
672
///   alignTo(5, 8, 7) = 7
673
///   alignTo(17, 8, 1) = 17
674
///   alignTo(~0LL, 8, 3) = 3
675
///   alignTo(321, 255, 42) = 552
676
/// \endcode
677
635M
inline uint64_t alignTo(uint64_t Value, uint64_t Align, uint64_t Skew = 0) {
678
635M
  assert(Align != 0u && "Align can't be 0.");
679
635M
  Skew %= Align;
680
635M
  return (Value + Align - 1 - Skew) / Align * Align + Skew;
681
635M
}
682
683
/// Returns the next integer (mod 2**64) that is greater than or equal to
684
/// \p Value and is a multiple of \c Align. \c Align must be non-zero.
685
8.37k
template <uint64_t Align> constexpr inline uint64_t alignTo(uint64_t Value) {
686
8.37k
  static_assert(Align != 0u, "Align must be non-zero");
687
8.37k
  return (Value + Align - 1) / Align * Align;
688
8.37k
}
Unexecuted instantiation: unsigned long long llvm::alignTo<4ull>(unsigned long long)
Unexecuted instantiation: unsigned long long llvm::alignTo<1ull>(unsigned long long)
unsigned long long llvm::alignTo<8ull>(unsigned long long)
Line
Count
Source
685
8.37k
template <uint64_t Align> constexpr inline uint64_t alignTo(uint64_t Value) {
686
8.37k
  static_assert(Align != 0u, "Align must be non-zero");
687
8.37k
  return (Value + Align - 1) / Align * Align;
688
8.37k
}
689
690
/// Returns the integer ceil(Numerator / Denominator).
691
0
inline uint64_t divideCeil(uint64_t Numerator, uint64_t Denominator) {
692
0
  return alignTo(Numerator, Denominator) / Denominator;
693
0
}
694
695
/// \c alignTo for contexts where a constant expression is required.
696
/// \sa alignTo
697
///
698
/// \todo FIXME: remove when \c constexpr becomes really \c constexpr
699
template <uint64_t Align>
700
struct AlignTo {
701
  static_assert(Align != 0u, "Align must be non-zero");
702
  template <uint64_t Value>
703
  struct from_value {
704
    static const uint64_t value = (Value + Align - 1) / Align * Align;
705
  };
706
};
707
708
/// Returns the largest uint64_t less than or equal to \p Value and is
709
/// \p Skew mod \p Align. \p Align must be non-zero
710
470k
inline uint64_t alignDown(uint64_t Value, uint64_t Align, uint64_t Skew = 0) {
711
470k
  assert(Align != 0u && "Align can't be 0.");
712
470k
  Skew %= Align;
713
470k
  return (Value - Skew) / Align * Align + Skew;
714
470k
}
715
716
/// Returns the offset to the next integer (mod 2**64) that is greater than
717
/// or equal to \p Value and is a multiple of \p Align. \p Align must be
718
/// non-zero.
719
2.49M
inline uint64_t OffsetToAlignment(uint64_t Value, uint64_t Align) {
720
2.49M
  return alignTo(Value, Align) - Value;
721
2.49M
}
722
723
/// Sign-extend the number in the bottom B bits of X to a 32-bit integer.
724
/// Requires 0 < B <= 32.
725
5.27k
template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
726
5.27k
  static_assert(B > 0, "Bit width can't be 0.");
727
5.27k
  static_assert(B <= 32, "Bit width out of range.");
728
5.27k
  return int32_t(X << (32 - B)) >> (32 - B);
729
5.27k
}
int llvm::SignExtend32<16u>(unsigned int)
Line
Count
Source
725
2.95k
template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
726
2.95k
  static_assert(B > 0, "Bit width can't be 0.");
727
2.95k
  static_assert(B <= 32, "Bit width out of range.");
728
2.95k
  return int32_t(X << (32 - B)) >> (32 - B);
729
2.95k
}
int llvm::SignExtend32<21u>(unsigned int)
Line
Count
Source
725
66
template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
726
66
  static_assert(B > 0, "Bit width can't be 0.");
727
66
  static_assert(B <= 32, "Bit width out of range.");
728
66
  return int32_t(X << (32 - B)) >> (32 - B);
729
66
}
int llvm::SignExtend32<13u>(unsigned int)
Line
Count
Source
725
63
template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
726
63
  static_assert(B > 0, "Bit width can't be 0.");
727
63
  static_assert(B <= 32, "Bit width out of range.");
728
63
  return int32_t(X << (32 - B)) >> (32 - B);
729
63
}
int llvm::SignExtend32<25u>(unsigned int)
Line
Count
Source
725
297
template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
726
297
  static_assert(B > 0, "Bit width can't be 0.");
727
297
  static_assert(B <= 32, "Bit width out of range.");
728
297
  return int32_t(X << (32 - B)) >> (32 - B);
729
297
}
int llvm::SignExtend32<12u>(unsigned int)
Line
Count
Source
725
193
template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
726
193
  static_assert(B > 0, "Bit width can't be 0.");
727
193
  static_assert(B <= 32, "Bit width out of range.");
728
193
  return int32_t(X << (32 - B)) >> (32 - B);
729
193
}
int llvm::SignExtend32<9u>(unsigned int)
Line
Count
Source
725
599
template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
726
599
  static_assert(B > 0, "Bit width can't be 0.");
727
599
  static_assert(B <= 32, "Bit width out of range.");
728
599
  return int32_t(X << (32 - B)) >> (32 - B);
729
599
}
int llvm::SignExtend32<32u>(unsigned int)
Line
Count
Source
725
61
template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
726
61
  static_assert(B > 0, "Bit width can't be 0.");
727
61
  static_assert(B <= 32, "Bit width out of range.");
728
61
  return int32_t(X << (32 - B)) >> (32 - B);
729
61
}
int llvm::SignExtend32<26u>(unsigned int)
Line
Count
Source
725
586
template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
726
586
  static_assert(B > 0, "Bit width can't be 0.");
727
586
  static_assert(B <= 32, "Bit width out of range.");
728
586
  return int32_t(X << (32 - B)) >> (32 - B);
729
586
}
int llvm::SignExtend32<5u>(unsigned int)
Line
Count
Source
725
246
template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
726
246
  static_assert(B > 0, "Bit width can't be 0.");
727
246
  static_assert(B <= 32, "Bit width out of range.");
728
246
  return int32_t(X << (32 - B)) >> (32 - B);
729
246
}
int llvm::SignExtend32<18u>(unsigned int)
Line
Count
Source
725
7
template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
726
7
  static_assert(B > 0, "Bit width can't be 0.");
727
7
  static_assert(B <= 32, "Bit width out of range.");
728
7
  return int32_t(X << (32 - B)) >> (32 - B);
729
7
}
int llvm::SignExtend32<19u>(unsigned int)
Line
Count
Source
725
26
template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
726
26
  static_assert(B > 0, "Bit width can't be 0.");
727
26
  static_assert(B <= 32, "Bit width out of range.");
728
26
  return int32_t(X << (32 - B)) >> (32 - B);
729
26
}
int llvm::SignExtend32<6u>(unsigned int)
Line
Count
Source
725
5
template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
726
5
  static_assert(B > 0, "Bit width can't be 0.");
727
5
  static_assert(B <= 32, "Bit width out of range.");
728
5
  return int32_t(X << (32 - B)) >> (32 - B);
729
5
}
int llvm::SignExtend32<11u>(unsigned int)
Line
Count
Source
725
31
template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
726
31
  static_assert(B > 0, "Bit width can't be 0.");
727
31
  static_assert(B <= 32, "Bit width out of range.");
728
31
  return int32_t(X << (32 - B)) >> (32 - B);
729
31
}
int llvm::SignExtend32<8u>(unsigned int)
Line
Count
Source
725
11
template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
726
11
  static_assert(B > 0, "Bit width can't be 0.");
727
11
  static_assert(B <= 32, "Bit width out of range.");
728
11
  return int32_t(X << (32 - B)) >> (32 - B);
729
11
}
int llvm::SignExtend32<27u>(unsigned int)
Line
Count
Source
725
3
template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
726
3
  static_assert(B > 0, "Bit width can't be 0.");
727
3
  static_assert(B <= 32, "Bit width out of range.");
728
3
  return int32_t(X << (32 - B)) >> (32 - B);
729
3
}
int llvm::SignExtend32<10u>(unsigned int)
Line
Count
Source
725
122
template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
726
122
  static_assert(B > 0, "Bit width can't be 0.");
727
122
  static_assert(B <= 32, "Bit width out of range.");
728
122
  return int32_t(X << (32 - B)) >> (32 - B);
729
122
}
int llvm::SignExtend32<4u>(unsigned int)
Line
Count
Source
725
8
template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
726
8
  static_assert(B > 0, "Bit width can't be 0.");
727
8
  static_assert(B <= 32, "Bit width out of range.");
728
8
  return int32_t(X << (32 - B)) >> (32 - B);
729
8
}
730
731
/// Sign-extend the number in the bottom B bits of X to a 32-bit integer.
732
/// Requires 0 < B < 32.
733
136
inline int32_t SignExtend32(uint32_t X, unsigned B) {
734
136
  assert(B > 0 && "Bit width can't be 0.");
735
136
  assert(B <= 32 && "Bit width out of range.");
736
136
  return int32_t(X << (32 - B)) >> (32 - B);
737
136
}
738
739
/// Sign-extend the number in the bottom B bits of X to a 64-bit integer.
740
/// Requires 0 < B < 64.
741
9.99k
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
742
9.99k
  static_assert(B > 0, "Bit width can't be 0.");
743
9.99k
  static_assert(B <= 64, "Bit width out of range.");
744
9.99k
  return int64_t(x << (64 - B)) >> (64 - B);
745
9.99k
}
long long llvm::SignExtend64<11u>(unsigned long long)
Line
Count
Source
741
2
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
742
2
  static_assert(B > 0, "Bit width can't be 0.");
743
2
  static_assert(B <= 64, "Bit width out of range.");
744
2
  return int64_t(x << (64 - B)) >> (64 - B);
745
2
}
long long llvm::SignExtend64<17u>(unsigned long long)
Line
Count
Source
741
2
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
742
2
  static_assert(B > 0, "Bit width can't be 0.");
743
2
  static_assert(B <= 64, "Bit width out of range.");
744
2
  return int64_t(x << (64 - B)) >> (64 - B);
745
2
}
long long llvm::SignExtend64<27u>(unsigned long long)
Line
Count
Source
741
4
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
742
4
  static_assert(B > 0, "Bit width can't be 0.");
743
4
  static_assert(B <= 64, "Bit width out of range.");
744
4
  return int64_t(x << (64 - B)) >> (64 - B);
745
4
}
long long llvm::SignExtend64<23u>(unsigned long long)
Line
Count
Source
741
3
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
742
3
  static_assert(B > 0, "Bit width can't be 0.");
743
3
  static_assert(B <= 64, "Bit width out of range.");
744
3
  return int64_t(x << (64 - B)) >> (64 - B);
745
3
}
long long llvm::SignExtend64<21u>(unsigned long long)
Line
Count
Source
741
1
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
742
1
  static_assert(B > 0, "Bit width can't be 0.");
743
1
  static_assert(B <= 64, "Bit width out of range.");
744
1
  return int64_t(x << (64 - B)) >> (64 - B);
745
1
}
long long llvm::SignExtend64<18u>(unsigned long long)
Line
Count
Source
741
2
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
742
2
  static_assert(B > 0, "Bit width can't be 0.");
743
2
  static_assert(B <= 64, "Bit width out of range.");
744
2
  return int64_t(x << (64 - B)) >> (64 - B);
745
2
}
long long llvm::SignExtend64<9u>(unsigned long long)
Line
Count
Source
741
14
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
742
14
  static_assert(B > 0, "Bit width can't be 0.");
743
14
  static_assert(B <= 64, "Bit width out of range.");
744
14
  return int64_t(x << (64 - B)) >> (64 - B);
745
14
}
long long llvm::SignExtend64<28u>(unsigned long long)
Line
Count
Source
741
49
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
742
49
  static_assert(B > 0, "Bit width can't be 0.");
743
49
  static_assert(B <= 64, "Bit width out of range.");
744
49
  return int64_t(x << (64 - B)) >> (64 - B);
745
49
}
Unexecuted instantiation: long long llvm::SignExtend64<22u>(unsigned long long)
Unexecuted instantiation: long long llvm::SignExtend64<25u>(unsigned long long)
long long llvm::SignExtend64<64u>(unsigned long long)
Line
Count
Source
741
70
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
742
70
  static_assert(B > 0, "Bit width can't be 0.");
743
70
  static_assert(B <= 64, "Bit width out of range.");
744
70
  return int64_t(x << (64 - B)) >> (64 - B);
745
70
}
long long llvm::SignExtend64<24u>(unsigned long long)
Line
Count
Source
741
61
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
742
61
  static_assert(B > 0, "Bit width can't be 0.");
743
61
  static_assert(B <= 64, "Bit width out of range.");
744
61
  return int64_t(x << (64 - B)) >> (64 - B);
745
61
}
long long llvm::SignExtend64<20u>(unsigned long long)
Line
Count
Source
741
1.97k
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
742
1.97k
  static_assert(B > 0, "Bit width can't be 0.");
743
1.97k
  static_assert(B <= 64, "Bit width out of range.");
744
1.97k
  return int64_t(x << (64 - B)) >> (64 - B);
745
1.97k
}
long long llvm::SignExtend64<12u>(unsigned long long)
Line
Count
Source
741
39
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
742
39
  static_assert(B > 0, "Bit width can't be 0.");
743
39
  static_assert(B <= 64, "Bit width out of range.");
744
39
  return int64_t(x << (64 - B)) >> (64 - B);
745
39
}
long long llvm::SignExtend64<26u>(unsigned long long)
Line
Count
Source
741
91
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
742
91
  static_assert(B > 0, "Bit width can't be 0.");
743
91
  static_assert(B <= 64, "Bit width out of range.");
744
91
  return int64_t(x << (64 - B)) >> (64 - B);
745
91
}
long long llvm::SignExtend64<31u>(unsigned long long)
Line
Count
Source
741
71
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
742
71
  static_assert(B > 0, "Bit width can't be 0.");
743
71
  static_assert(B <= 64, "Bit width out of range.");
744
71
  return int64_t(x << (64 - B)) >> (64 - B);
745
71
}
long long llvm::SignExtend64<6u>(unsigned long long)
Line
Count
Source
741
69
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
742
69
  static_assert(B > 0, "Bit width can't be 0.");
743
69
  static_assert(B <= 64, "Bit width out of range.");
744
69
  return int64_t(x << (64 - B)) >> (64 - B);
745
69
}
long long llvm::SignExtend64<10u>(unsigned long long)
Line
Count
Source
741
12
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
742
12
  static_assert(B > 0, "Bit width can't be 0.");
743
12
  static_assert(B <= 64, "Bit width out of range.");
744
12
  return int64_t(x << (64 - B)) >> (64 - B);
745
12
}
long long llvm::SignExtend64<5u>(unsigned long long)
Line
Count
Source
741
93
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
742
93
  static_assert(B > 0, "Bit width can't be 0.");
743
93
  static_assert(B <= 64, "Bit width out of range.");
744
93
  return int64_t(x << (64 - B)) >> (64 - B);
745
93
}
long long llvm::SignExtend64<4u>(unsigned long long)
Line
Count
Source
741
112
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
742
112
  static_assert(B > 0, "Bit width can't be 0.");
743
112
  static_assert(B <= 64, "Bit width out of range.");
744
112
  return int64_t(x << (64 - B)) >> (64 - B);
745
112
}
long long llvm::SignExtend64<32u>(unsigned long long)
Line
Count
Source
741
3.94k
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
742
3.94k
  static_assert(B > 0, "Bit width can't be 0.");
743
3.94k
  static_assert(B <= 64, "Bit width out of range.");
744
3.94k
  return int64_t(x << (64 - B)) >> (64 - B);
745
3.94k
}
long long llvm::SignExtend64<16u>(unsigned long long)
Line
Count
Source
741
3.10k
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
742
3.10k
  static_assert(B > 0, "Bit width can't be 0.");
743
3.10k
  static_assert(B <= 64, "Bit width out of range.");
744
3.10k
  return int64_t(x << (64 - B)) >> (64 - B);
745
3.10k
}
long long llvm::SignExtend64<13u>(unsigned long long)
Line
Count
Source
741
30
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
742
30
  static_assert(B > 0, "Bit width can't be 0.");
743
30
  static_assert(B <= 64, "Bit width out of range.");
744
30
  return int64_t(x << (64 - B)) >> (64 - B);
745
30
}
long long llvm::SignExtend64<14u>(unsigned long long)
Line
Count
Source
741
6
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
742
6
  static_assert(B > 0, "Bit width can't be 0.");
743
6
  static_assert(B <= 64, "Bit width out of range.");
744
6
  return int64_t(x << (64 - B)) >> (64 - B);
745
6
}
long long llvm::SignExtend64<7u>(unsigned long long)
Line
Count
Source
741
24
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
742
24
  static_assert(B > 0, "Bit width can't be 0.");
743
24
  static_assert(B <= 64, "Bit width out of range.");
744
24
  return int64_t(x << (64 - B)) >> (64 - B);
745
24
}
long long llvm::SignExtend64<3u>(unsigned long long)
Line
Count
Source
741
38
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
742
38
  static_assert(B > 0, "Bit width can't be 0.");
743
38
  static_assert(B <= 64, "Bit width out of range.");
744
38
  return int64_t(x << (64 - B)) >> (64 - B);
745
38
}
long long llvm::SignExtend64<8u>(unsigned long long)
Line
Count
Source
741
178
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
742
178
  static_assert(B > 0, "Bit width can't be 0.");
743
178
  static_assert(B <= 64, "Bit width out of range.");
744
178
  return int64_t(x << (64 - B)) >> (64 - B);
745
178
}
746
747
/// Sign-extend the number in the bottom B bits of X to a 64-bit integer.
748
/// Requires 0 < B < 64.
749
854M
inline int64_t SignExtend64(uint64_t X, unsigned B) {
750
854M
  assert(B > 0 && "Bit width can't be 0.");
751
854M
  assert(B <= 64 && "Bit width out of range.");
752
854M
  return int64_t(X << (64 - B)) >> (64 - B);
753
854M
}
754
755
/// Subtract two unsigned integers, X and Y, of type T and return the absolute
756
/// value of the result.
757
template <typename T>
758
typename std::enable_if<std::is_unsigned<T>::value, T>::type
759
33
AbsoluteDifference(T X, T Y) {
760
33
  return std::max(X, Y) - std::min(X, Y);
761
33
}
762
763
/// Add two unsigned integers, X and Y, of type T.  Clamp the result to the
764
/// maximum representable value of T on overflow.  ResultOverflowed indicates if
765
/// the result is larger than the maximum representable value of type T.
766
template <typename T>
767
typename std::enable_if<std::is_unsigned<T>::value, T>::type
768
417k
SaturatingAdd(T X, T Y, bool *ResultOverflowed = nullptr) {
769
417k
  bool Dummy;
770
417k
  bool &Overflowed = ResultOverflowed ? 
*ResultOverflowed2.32k
:
Dummy415k
;
771
417k
  // Hacker's Delight, p. 29
772
417k
  T Z = X + Y;
773
417k
  Overflowed = (Z < X || Z < Y);
774
417k
  if (Overflowed)
775
25
    return std::numeric_limits<T>::max();
776
417k
  else
777
417k
    return Z;
778
417k
}
779
780
/// Multiply two unsigned integers, X and Y, of type T.  Clamp the result to the
781
/// maximum representable value of T on overflow.  ResultOverflowed indicates if
782
/// the result is larger than the maximum representable value of type T.
783
template <typename T>
784
typename std::enable_if<std::is_unsigned<T>::value, T>::type
785
2.68k
SaturatingMultiply(T X, T Y, bool *ResultOverflowed = nullptr) {
786
2.68k
  bool Dummy;
787
2.68k
  bool &Overflowed = ResultOverflowed ? 
*ResultOverflowed2.48k
:
Dummy199
;
788
2.68k
789
2.68k
  // Hacker's Delight, p. 30 has a different algorithm, but we don't use that
790
2.68k
  // because it fails for uint16_t (where multiplication can have undefined
791
2.68k
  // behavior due to promotion to int), and requires a division in addition
792
2.68k
  // to the multiplication.
793
2.68k
794
2.68k
  Overflowed = false;
795
2.68k
796
2.68k
  // Log2(Z) would be either Log2Z or Log2Z + 1.
797
2.68k
  // Special case: if X or Y is 0, Log2_64 gives -1, and Log2Z
798
2.68k
  // will necessarily be less than Log2Max as desired.
799
2.68k
  int Log2Z = Log2_64(X) + Log2_64(Y);
800
2.68k
  const T Max = std::numeric_limits<T>::max();
801
2.68k
  int Log2Max = Log2_64(Max);
802
2.68k
  if (
Log2Z < Log2Max2.68k
) {
803
2.36k
    return X * Y;
804
2.36k
  }
805
323
  
if (323
Log2Z > Log2Max323
) {
806
12
    Overflowed = true;
807
12
    return Max;
808
12
  }
809
323
810
323
  // We're going to use the top bit, and maybe overflow one
811
323
  // bit past it. Multiply all but the bottom bit then add
812
323
  // that on at the end.
813
311
  T Z = (X >> 1) * Y;
814
311
  if (
Z & ~(Max >> 1)311
) {
815
62
    Overflowed = true;
816
62
    return Max;
817
62
  }
818
249
  Z <<= 1;
819
249
  if (X & 1)
820
248
    return SaturatingAdd(Z, Y, ResultOverflowed);
821
249
822
1
  return Z;
823
2.68k
}
824
825
/// Multiply two unsigned integers, X and Y, and add the unsigned integer, A to
826
/// the product. Clamp the result to the maximum representable value of T on
827
/// overflow. ResultOverflowed indicates if the result is larger than the
828
/// maximum representable value of type T.
829
template <typename T>
830
typename std::enable_if<std::is_unsigned<T>::value, T>::type
831
2.17k
SaturatingMultiplyAdd(T X, T Y, T A, bool *ResultOverflowed = nullptr) {
832
2.17k
  bool Dummy;
833
2.17k
  bool &Overflowed = ResultOverflowed ? 
*ResultOverflowed2.15k
:
Dummy25
;
834
2.17k
835
2.17k
  T Product = SaturatingMultiply(X, Y, &Overflowed);
836
2.17k
  if (Overflowed)
837
6
    return Product;
838
2.17k
839
2.17k
  return SaturatingAdd(A, Product, &Overflowed);
840
2.17k
}
841
842
/// Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
843
extern const float huge_valf;
844
} // End llvm namespace
845
846
#endif