Coverage Report

Created: 2018-07-12 09:57

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