Coverage Report

Created: 2018-09-19 08:35

/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
80.5M
  static std::size_t count(T Val, ZeroBehavior ZB) {
80
80.5M
    if (ZB != ZB_Undefined && 
Val == 080.5M
)
81
1
      return 32;
82
80.5M
83
80.5M
#if __has_builtin(__builtin_ctz) || LLVM_GNUC_PREREQ(4, 0, 0)
84
80.5M
    return __builtin_ctz(Val);
85
80.5M
#elif defined(_MSC_VER)
86
80.5M
    unsigned long Index;
87
80.5M
    _BitScanForward(&Index, Val);
88
80.5M
    return Index;
89
80.5M
#endif
90
80.5M
  }
91
};
92
93
#if !defined(_MSC_VER) || defined(_M_X64)
94
template <typename T> struct TrailingZerosCounter<T, 8> {
95
620M
  static std::size_t count(T Val, ZeroBehavior ZB) {
96
620M
    if (ZB != ZB_Undefined && 
Val == 0524M
)
97
40.5M
      return 64;
98
579M
99
579M
#if __has_builtin(__builtin_ctzll) || LLVM_GNUC_PREREQ(4, 0, 0)
100
579M
    return __builtin_ctzll(Val);
101
579M
#elif defined(_MSC_VER)
102
579M
    unsigned long Index;
103
579M
    _BitScanForward64(&Index, Val);
104
579M
    return Index;
105
579M
#endif
106
579M
  }
llvm::detail::TrailingZerosCounter<unsigned long long, 8ul>::count(unsigned long long, llvm::ZeroBehavior)
Line
Count
Source
95
409M
  static std::size_t count(T Val, ZeroBehavior ZB) {
96
409M
    if (ZB != ZB_Undefined && 
Val == 0313M
)
97
40.5M
      return 64;
98
369M
99
369M
#if __has_builtin(__builtin_ctzll) || LLVM_GNUC_PREREQ(4, 0, 0)
100
369M
    return __builtin_ctzll(Val);
101
369M
#elif defined(_MSC_VER)
102
369M
    unsigned long Index;
103
369M
    _BitScanForward64(&Index, Val);
104
369M
    return Index;
105
369M
#endif
106
369M
  }
llvm::detail::TrailingZerosCounter<unsigned long, 8ul>::count(unsigned long, llvm::ZeroBehavior)
Line
Count
Source
95
210M
  static std::size_t count(T Val, ZeroBehavior ZB) {
96
210M
    if (
ZB != ZB_Undefined210M
&& Val == 0)
97
0
      return 64;
98
210M
99
210M
#if __has_builtin(__builtin_ctzll) || LLVM_GNUC_PREREQ(4, 0, 0)
100
210M
    return __builtin_ctzll(Val);
101
210M
#elif defined(_MSC_VER)
102
210M
    unsigned long Index;
103
210M
    _BitScanForward64(&Index, Val);
104
210M
    return Index;
105
210M
#endif
106
210M
  }
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
701M
std::size_t countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
121
701M
  static_assert(std::numeric_limits<T>::is_integer &&
122
701M
                    !std::numeric_limits<T>::is_signed,
123
701M
                "Only unsigned integral types are allowed.");
124
701M
  return llvm::detail::TrailingZerosCounter<T, sizeof(T)>::count(Val, ZB);
125
701M
}
unsigned long llvm::countTrailingZeros<unsigned long long>(unsigned long long, llvm::ZeroBehavior)
Line
Count
Source
120
409M
std::size_t countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
121
409M
  static_assert(std::numeric_limits<T>::is_integer &&
122
409M
                    !std::numeric_limits<T>::is_signed,
123
409M
                "Only unsigned integral types are allowed.");
124
409M
  return llvm::detail::TrailingZerosCounter<T, sizeof(T)>::count(Val, ZB);
125
409M
}
unsigned long llvm::countTrailingZeros<unsigned long>(unsigned long, llvm::ZeroBehavior)
Line
Count
Source
120
210M
std::size_t countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
121
210M
  static_assert(std::numeric_limits<T>::is_integer &&
122
210M
                    !std::numeric_limits<T>::is_signed,
123
210M
                "Only unsigned integral types are allowed.");
124
210M
  return llvm::detail::TrailingZerosCounter<T, sizeof(T)>::count(Val, ZB);
125
210M
}
unsigned long llvm::countTrailingZeros<unsigned int>(unsigned int, llvm::ZeroBehavior)
Line
Count
Source
120
80.5M
std::size_t countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
121
80.5M
  static_assert(std::numeric_limits<T>::is_integer &&
122
80.5M
                    !std::numeric_limits<T>::is_signed,
123
80.5M
                "Only unsigned integral types are allowed.");
124
80.5M
  return llvm::detail::TrailingZerosCounter<T, sizeof(T)>::count(Val, ZB);
125
80.5M
}
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
108M
  static std::size_t count(T Val, ZeroBehavior ZB) {
149
108M
    if (
ZB != ZB_Undefined108M
&& Val == 0)
150
36.9M
      return 32;
151
71.6M
152
71.6M
#if __has_builtin(__builtin_clz) || LLVM_GNUC_PREREQ(4, 0, 0)
153
71.6M
    return __builtin_clz(Val);
154
71.6M
#elif defined(_MSC_VER)
155
71.6M
    unsigned long Index;
156
71.6M
    _BitScanReverse(&Index, Val);
157
71.6M
    return Index ^ 31;
158
71.6M
#endif
159
71.6M
  }
160
};
161
162
#if !defined(_MSC_VER) || defined(_M_X64)
163
template <typename T> struct LeadingZerosCounter<T, 8> {
164
615M
  static std::size_t count(T Val, ZeroBehavior ZB) {
165
615M
    if (ZB != ZB_Undefined && 
Val == 0609M
)
166
49.1M
      return 64;
167
566M
168
566M
#if __has_builtin(__builtin_clzll) || LLVM_GNUC_PREREQ(4, 0, 0)
169
566M
    return __builtin_clzll(Val);
170
566M
#elif defined(_MSC_VER)
171
566M
    unsigned long Index;
172
566M
    _BitScanReverse64(&Index, Val);
173
566M
    return Index ^ 63;
174
566M
#endif
175
566M
  }
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
724M
std::size_t countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
190
724M
  static_assert(std::numeric_limits<T>::is_integer &&
191
724M
                    !std::numeric_limits<T>::is_signed,
192
724M
                "Only unsigned integral types are allowed.");
193
724M
  return llvm::detail::LeadingZerosCounter<T, sizeof(T)>::count(Val, ZB);
194
724M
}
unsigned long llvm::countLeadingZeros<unsigned long long>(unsigned long long, llvm::ZeroBehavior)
Line
Count
Source
189
615M
std::size_t countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
190
615M
  static_assert(std::numeric_limits<T>::is_integer &&
191
615M
                    !std::numeric_limits<T>::is_signed,
192
615M
                "Only unsigned integral types are allowed.");
193
615M
  return llvm::detail::LeadingZerosCounter<T, sizeof(T)>::count(Val, ZB);
194
615M
}
unsigned long llvm::countLeadingZeros<unsigned int>(unsigned int, llvm::ZeroBehavior)
Line
Count
Source
189
108M
std::size_t countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
190
108M
  static_assert(std::numeric_limits<T>::is_integer &&
191
108M
                    !std::numeric_limits<T>::is_signed,
192
108M
                "Only unsigned integral types are allowed.");
193
108M
  return llvm::detail::LeadingZerosCounter<T, sizeof(T)>::count(Val, ZB);
194
108M
}
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
96.2M
template <typename T> T findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) {
204
96.2M
  if (ZB == ZB_Max && Val == 0)
205
1
    return std::numeric_limits<T>::max();
206
96.2M
207
96.2M
  return countTrailingZeros(Val, ZB_Undefined);
208
96.2M
}
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
400M
template <typename T> T maskTrailingOnes(unsigned N) {
213
400M
  static_assert(std::is_unsigned<T>::value, "Invalid type!");
214
400M
  const unsigned Bits = CHAR_BIT * sizeof(T);
215
400M
  assert(N <= Bits && "Invalid bit index");
216
400M
  return N == 0 ? 
019.9M
:
(T(-1) >> (Bits - N))380M
;
217
400M
}
unsigned long llvm::maskTrailingOnes<unsigned long>(unsigned int)
Line
Count
Source
212
301M
template <typename T> T maskTrailingOnes(unsigned N) {
213
301M
  static_assert(std::is_unsigned<T>::value, "Invalid type!");
214
301M
  const unsigned Bits = CHAR_BIT * sizeof(T);
215
301M
  assert(N <= Bits && "Invalid bit index");
216
301M
  return N == 0 ? 
019.8M
:
(T(-1) >> (Bits - N))281M
;
217
301M
}
unsigned long long llvm::maskTrailingOnes<unsigned long long>(unsigned int)
Line
Count
Source
212
98.8M
template <typename T> T maskTrailingOnes(unsigned N) {
213
98.8M
  static_assert(std::is_unsigned<T>::value, "Invalid type!");
214
98.8M
  const unsigned Bits = CHAR_BIT * sizeof(T);
215
98.8M
  assert(N <= Bits && "Invalid bit index");
216
98.8M
  return N == 0 ? 
047.1k
:
(T(-1) >> (Bits - N))98.7M
;
217
98.8M
}
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
312M
template <typename T> T maskLeadingOnes(unsigned N) {
222
312M
  return ~maskTrailingOnes<T>(CHAR_BIT * sizeof(T) - N);
223
312M
}
unsigned long llvm::maskLeadingOnes<unsigned long>(unsigned int)
Line
Count
Source
221
213M
template <typename T> T maskLeadingOnes(unsigned N) {
222
213M
  return ~maskTrailingOnes<T>(CHAR_BIT * sizeof(T) - N);
223
213M
}
unsigned long long llvm::maskLeadingOnes<unsigned long long>(unsigned int)
Line
Count
Source
221
98.7M
template <typename T> T maskLeadingOnes(unsigned N) {
222
98.7M
  return ~maskTrailingOnes<T>(CHAR_BIT * sizeof(T) - N);
223
98.7M
}
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
213M
template <typename T> T maskTrailingZeros(unsigned N) {
228
213M
  return maskLeadingOnes<T>(CHAR_BIT * sizeof(T) - N);
229
213M
}
unsigned long llvm::maskTrailingZeros<unsigned long>(unsigned int)
Line
Count
Source
227
213M
template <typename T> T maskTrailingZeros(unsigned N) {
228
213M
  return maskLeadingOnes<T>(CHAR_BIT * sizeof(T) - N);
229
213M
}
unsigned long long llvm::maskTrailingZeros<unsigned long long>(unsigned int)
Line
Count
Source
227
887
template <typename T> T maskTrailingZeros(unsigned N) {
228
887
  return maskLeadingOnes<T>(CHAR_BIT * sizeof(T) - N);
229
887
}
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.41M
template <typename T> T findLastSet(T Val, ZeroBehavior ZB = ZB_Max) {
245
5.41M
  if (ZB == ZB_Max && 
Val == 05.41M
)
246
1
    return std::numeric_limits<T>::max();
247
5.41M
248
5.41M
  // Use ^ instead of - because both gcc and llvm can remove the associated ^
249
5.41M
  // in the __builtin_clz intrinsic on x86.
250
5.41M
  return countLeadingZeros(Val, ZB_Undefined) ^
251
5.41M
         (std::numeric_limits<T>::digits - 1);
252
5.41M
}
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.5k
T reverseBits(T Val) {
270
18.5k
  unsigned char in[sizeof(Val)];
271
18.5k
  unsigned char out[sizeof(Val)];
272
18.5k
  std::memcpy(in, &Val, sizeof(Val));
273
97.8k
  for (unsigned i = 0; i < sizeof(Val); 
++i79.2k
)
274
79.2k
    out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]];
275
18.5k
  std::memcpy(&Val, out, sizeof(Val));
276
18.5k
  return Val;
277
18.5k
}
int llvm::reverseBits<int>(int)
Line
Count
Source
269
13.0k
T reverseBits(T Val) {
270
13.0k
  unsigned char in[sizeof(Val)];
271
13.0k
  unsigned char out[sizeof(Val)];
272
13.0k
  std::memcpy(in, &Val, sizeof(Val));
273
65.3k
  for (unsigned i = 0; i < sizeof(Val); 
++i52.2k
)
274
52.2k
    out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]];
275
13.0k
  std::memcpy(&Val, out, sizeof(Val));
276
13.0k
  return Val;
277
13.0k
}
unsigned int llvm::reverseBits<unsigned int>(unsigned int)
Line
Count
Source
269
3.54k
T reverseBits(T Val) {
270
3.54k
  unsigned char in[sizeof(Val)];
271
3.54k
  unsigned char out[sizeof(Val)];
272
3.54k
  std::memcpy(in, &Val, sizeof(Val));
273
17.7k
  for (unsigned i = 0; i < sizeof(Val); 
++i14.1k
)
274
14.1k
    out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]];
275
3.54k
  std::memcpy(&Val, out, sizeof(Val));
276
3.54k
  return Val;
277
3.54k
}
unsigned long long llvm::reverseBits<unsigned long long>(unsigned long long)
Line
Count
Source
269
1.51k
T reverseBits(T Val) {
270
1.51k
  unsigned char in[sizeof(Val)];
271
1.51k
  unsigned char out[sizeof(Val)];
272
1.51k
  std::memcpy(in, &Val, sizeof(Val));
273
13.6k
  for (unsigned i = 0; i < sizeof(Val); 
++i12.1k
)
274
12.1k
    out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]];
275
1.51k
  std::memcpy(&Val, out, sizeof(Val));
276
1.51k
  return Val;
277
1.51k
}
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
27.4M
constexpr inline uint32_t Hi_32(uint64_t Value) {
285
27.4M
  return static_cast<uint32_t>(Value >> 32);
286
27.4M
}
287
288
/// Return the low 32 bits of a 64 bit value.
289
46.3M
constexpr inline uint32_t Lo_32(uint64_t Value) {
290
46.3M
  return static_cast<uint32_t>(Value);
291
46.3M
}
292
293
/// Make a 64-bit integer from a high / low pair of 32-bit integers.
294
19.4M
constexpr inline uint64_t Make_64(uint32_t High, uint32_t Low) {
295
19.4M
  return ((uint64_t)High << 32) | (uint64_t)Low;
296
19.4M
}
297
298
/// Checks if an integer fits into the given bit width.
299
25.0M
template <unsigned N> constexpr inline bool isInt(int64_t x) {
300
25.0M
  return N >= 64 || 
(25.0M
-(INT64_C(1)<<(N-1)) <= x25.0M
&&
x < (INT64_C(1)<<(N-1))24.4M
);
301
25.0M
}
bool llvm::isInt<9u>(long long)
Line
Count
Source
299
24.7M
template <unsigned N> constexpr inline bool isInt(int64_t x) {
300
24.7M
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && 
x < (INT64_C(1)<<(N-1))24.1M
);
301
24.7M
}
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.5k
template <unsigned N> constexpr inline bool isInt(int64_t x) {
300
24.5k
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && 
x < (INT64_C(1)<<(N-1))24.5k
);
301
24.5k
}
bool llvm::isInt<25u>(long long)
Line
Count
Source
299
54.5k
template <unsigned N> constexpr inline bool isInt(int64_t x) {
300
54.5k
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && 
x < (INT64_C(1)<<(N-1))54.5k
);
301
54.5k
}
bool llvm::isInt<21u>(long long)
Line
Count
Source
299
5.61k
template <unsigned N> constexpr inline bool isInt(int64_t x) {
300
5.61k
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && 
x < (INT64_C(1)<<(N-1))5.59k
);
301
5.61k
}
bool llvm::isInt<23u>(long long)
Line
Count
Source
299
378
template <unsigned N> constexpr inline bool isInt(int64_t x) {
300
378
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && 
x < (INT64_C(1)<<(N-1))376
);
301
378
}
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
84
template <unsigned N> constexpr inline bool isInt(int64_t x) {
300
84
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && 
x < (INT64_C(1)<<(N-1))78
);
301
84
}
bool llvm::isInt<11u>(long long)
Line
Count
Source
299
38.4k
template <unsigned N> constexpr inline bool isInt(int64_t x) {
300
38.4k
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && 
x < (INT64_C(1)<<(N-1))38.1k
);
301
38.4k
}
bool llvm::isInt<24u>(long long)
Line
Count
Source
299
162
template <unsigned N> constexpr inline bool isInt(int64_t x) {
300
162
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1)));
301
162
}
bool llvm::isInt<17u>(long long)
Line
Count
Source
299
2.32k
template <unsigned N> constexpr inline bool isInt(int64_t x) {
300
2.32k
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && 
x < (INT64_C(1)<<(N-1))2.31k
);
301
2.32k
}
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.46k
);
301
1.47k
}
bool llvm::isInt<3u>(long long)
Line
Count
Source
299
309
template <unsigned N> constexpr inline bool isInt(int64_t x) {
300
309
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1)));
301
309
}
bool llvm::isInt<7u>(long long)
Line
Count
Source
299
186
template <unsigned N> constexpr inline bool isInt(int64_t x) {
300
186
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && 
x < (INT64_C(1)<<(N-1))183
);
301
186
}
bool llvm::isInt<5u>(long long)
Line
Count
Source
299
172
template <unsigned N> constexpr inline bool isInt(int64_t x) {
300
172
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && 
x < (INT64_C(1)<<(N-1))152
);
301
172
}
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.42k
template <unsigned N> constexpr inline bool isInt(int64_t x) {
300
1.42k
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1)));
301
1.42k
}
bool llvm::isInt<28u>(long long)
Line
Count
Source
299
99
template <unsigned N> constexpr inline bool isInt(int64_t x) {
300
99
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1)));
301
99
}
bool llvm::isInt<27u>(long long)
Line
Count
Source
299
16
template <unsigned N> constexpr inline bool isInt(int64_t x) {
300
16
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1)));
301
16
}
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
44
template <unsigned N> constexpr inline bool isInt(int64_t x) {
300
44
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && 
x < (INT64_C(1)<<(N-1))43
);
301
44
}
bool llvm::isInt<20u>(long long)
Line
Count
Source
299
24.4k
template <unsigned N> constexpr inline bool isInt(int64_t x) {
300
24.4k
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && 
x < (INT64_C(1)<<(N-1))23.7k
);
301
24.4k
}
bool llvm::isInt<31u>(long long)
Line
Count
Source
299
121k
template <unsigned N> constexpr inline bool isInt(int64_t x) {
300
121k
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && 
x < (INT64_C(1)<<(N-1))121k
);
301
121k
}
302
// Template specializations to get better code for common cases.
303
484k
template <> constexpr inline bool isInt<8>(int64_t x) {
304
484k
  return static_cast<int8_t>(x) == x;
305
484k
}
306
375k
template <> constexpr inline bool isInt<16>(int64_t x) {
307
375k
  return static_cast<int16_t>(x) == x;
308
375k
}
309
7.24M
template <> constexpr inline bool isInt<32>(int64_t x) {
310
7.24M
  return static_cast<int32_t>(x) == x;
311
7.24M
}
312
313
/// Checks if a signed integer is an N bit number shifted left by S.
314
template <unsigned N, unsigned S>
315
5.61k
constexpr inline bool isShiftedInt(int64_t x) {
316
5.61k
  static_assert(
317
5.61k
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
318
5.61k
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
319
5.61k
  return isInt<N + S>(x) && 
(x % (UINT64_C(1) << S) == 0)4.04k
;
320
5.61k
}
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
66
constexpr inline bool isShiftedInt(int64_t x) {
316
66
  static_assert(
317
66
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
318
66
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
319
66
  return isInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
320
66
}
bool llvm::isShiftedInt<29u, 3u>(long long)
Line
Count
Source
315
46
constexpr inline bool isShiftedInt(int64_t x) {
316
46
  static_assert(
317
46
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
318
46
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
319
46
  return isInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
320
46
}
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.36k
constexpr inline bool isShiftedInt(int64_t x) {
316
1.36k
  static_assert(
317
1.36k
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
318
1.36k
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
319
1.36k
  return isInt<N + S>(x) && 
(x % (UINT64_C(1) << S) == 0)1.36k
;
320
1.36k
}
bool llvm::isShiftedInt<8u, 0u>(long long)
Line
Count
Source
315
99
constexpr inline bool isShiftedInt(int64_t x) {
316
99
  static_assert(
317
99
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
318
99
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
319
99
  return isInt<N + S>(x) && 
(x % (UINT64_C(1) << S) == 0)91
;
320
99
}
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
181
constexpr inline bool isShiftedInt(int64_t x) {
316
181
  static_assert(
317
181
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
318
181
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
319
181
  return isInt<N + S>(x) && 
(x % (UINT64_C(1) << S) == 0)149
;
320
181
}
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
3.00M
isUInt(uint64_t X) {
333
3.00M
  static_assert(N > 0, "isUInt<0> doesn't make sense");
334
3.00M
  return X < (UINT64_C(1) << (N));
335
3.00M
}
std::__1::enable_if<(5u) < (64), bool>::type llvm::isUInt<5u>(unsigned long long)
Line
Count
Source
332
21.6k
isUInt(uint64_t X) {
333
21.6k
  static_assert(N > 0, "isUInt<0> doesn't make sense");
334
21.6k
  return X < (UINT64_C(1) << (N));
335
21.6k
}
std::__1::enable_if<(12u) < (64), bool>::type llvm::isUInt<12u>(unsigned long long)
Line
Count
Source
332
111k
isUInt(uint64_t X) {
333
111k
  static_assert(N > 0, "isUInt<0> doesn't make sense");
334
111k
  return X < (UINT64_C(1) << (N));
335
111k
}
std::__1::enable_if<(24u) < (64), bool>::type llvm::isUInt<24u>(unsigned long long)
Line
Count
Source
332
2.65M
isUInt(uint64_t X) {
333
2.65M
  static_assert(N > 0, "isUInt<0> doesn't make sense");
334
2.65M
  return X < (UINT64_C(1) << (N));
335
2.65M
}
std::__1::enable_if<(20u) < (64), bool>::type llvm::isUInt<20u>(unsigned long long)
Line
Count
Source
332
51.6k
isUInt(uint64_t X) {
333
51.6k
  static_assert(N > 0, "isUInt<0> doesn't make sense");
334
51.6k
  return X < (UINT64_C(1) << (N));
335
51.6k
}
std::__1::enable_if<(6u) < (64), bool>::type llvm::isUInt<6u>(unsigned long long)
Line
Count
Source
332
127k
isUInt(uint64_t X) {
333
127k
  static_assert(N > 0, "isUInt<0> doesn't make sense");
334
127k
  return X < (UINT64_C(1) << (N));
335
127k
}
std::__1::enable_if<(1u) < (64), bool>::type llvm::isUInt<1u>(unsigned long long)
Line
Count
Source
332
827
isUInt(uint64_t X) {
333
827
  static_assert(N > 0, "isUInt<0> doesn't make sense");
334
827
  return X < (UINT64_C(1) << (N));
335
827
}
std::__1::enable_if<(2u) < (64), bool>::type llvm::isUInt<2u>(unsigned long long)
Line
Count
Source
332
3.16k
isUInt(uint64_t X) {
333
3.16k
  static_assert(N > 0, "isUInt<0> doesn't make sense");
334
3.16k
  return X < (UINT64_C(1) << (N));
335
3.16k
}
std::__1::enable_if<(4u) < (64), bool>::type llvm::isUInt<4u>(unsigned long long)
Line
Count
Source
332
6.72k
isUInt(uint64_t X) {
333
6.72k
  static_assert(N > 0, "isUInt<0> doesn't make sense");
334
6.72k
  return X < (UINT64_C(1) << (N));
335
6.72k
}
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
523
isUInt(uint64_t X) {
333
523
  static_assert(N > 0, "isUInt<0> doesn't make sense");
334
523
  return X < (UINT64_C(1) << (N));
335
523
}
std::__1::enable_if<(7u) < (64), bool>::type llvm::isUInt<7u>(unsigned long long)
Line
Count
Source
332
3.31k
isUInt(uint64_t X) {
333
3.31k
  static_assert(N > 0, "isUInt<0> doesn't make sense");
334
3.31k
  return X < (UINT64_C(1) << (N));
335
3.31k
}
std::__1::enable_if<(3u) < (64), bool>::type llvm::isUInt<3u>(unsigned long long)
Line
Count
Source
332
3.07k
isUInt(uint64_t X) {
333
3.07k
  static_assert(N > 0, "isUInt<0> doesn't make sense");
334
3.07k
  return X < (UINT64_C(1) << (N));
335
3.07k
}
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
55
isUInt(uint64_t X) {
333
55
  static_assert(N > 0, "isUInt<0> doesn't make sense");
334
55
  return X < (UINT64_C(1) << (N));
335
55
}
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.28M
template <> constexpr inline bool isUInt<16>(uint64_t x) {
347
5.28M
  return static_cast<uint16_t>(x) == x;
348
5.28M
}
349
162k
template <> constexpr inline bool isUInt<32>(uint64_t x) {
350
162k
  return static_cast<uint32_t>(x) == x;
351
162k
}
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)11.0k
;
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.34k
constexpr inline bool isShiftedUInt(uint64_t x) {
356
1.34k
  static_assert(
357
1.34k
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
358
1.34k
  static_assert(N + S <= 64,
359
1.34k
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
360
1.34k
  // Per the two static_asserts above, S must be strictly less than 64.  So
361
1.34k
  // 1 << S is not undefined behavior.
362
1.34k
  return isUInt<N + S>(x) && 
(x % (UINT64_C(1) << S) == 0)1.01k
;
363
1.34k
}
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.11k
constexpr inline bool isShiftedUInt(uint64_t x) {
356
1.11k
  static_assert(
357
1.11k
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
358
1.11k
  static_assert(N + S <= 64,
359
1.11k
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
360
1.11k
  // Per the two static_asserts above, S must be strictly less than 64.  So
361
1.11k
  // 1 << S is not undefined behavior.
362
1.11k
  return isUInt<N + S>(x) && 
(x % (UINT64_C(1) << S) == 0)872
;
363
1.11k
}
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
395
constexpr inline bool isShiftedUInt(uint64_t x) {
356
395
  static_assert(
357
395
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
358
395
  static_assert(N + S <= 64,
359
395
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
360
395
  // Per the two static_asserts above, S must be strictly less than 64.  So
361
395
  // 1 << S is not undefined behavior.
362
395
  return isUInt<N + S>(x) && 
(x % (UINT64_C(1) << S) == 0)321
;
363
395
}
bool llvm::isShiftedUInt<5u, 3u>(unsigned long long)
Line
Count
Source
355
2.15k
constexpr inline bool isShiftedUInt(uint64_t x) {
356
2.15k
  static_assert(
357
2.15k
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
358
2.15k
  static_assert(N + S <= 64,
359
2.15k
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
360
2.15k
  // Per the two static_asserts above, S must be strictly less than 64.  So
361
2.15k
  // 1 << S is not undefined behavior.
362
2.15k
  return isUInt<N + S>(x) && 
(x % (UINT64_C(1) << S) == 0)2.03k
;
363
2.15k
}
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.81k
;
363
2.41k
}
bool llvm::isShiftedUInt<5u, 0u>(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)956
;
363
1.12k
}
bool llvm::isShiftedUInt<2u, 0u>(unsigned long long)
Line
Count
Source
355
369
constexpr inline bool isShiftedUInt(uint64_t x) {
356
369
  static_assert(
357
369
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
358
369
  static_assert(N + S <= 64,
359
369
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
360
369
  // Per the two static_asserts above, S must be strictly less than 64.  So
361
369
  // 1 << S is not undefined behavior.
362
369
  return isUInt<N + S>(x) && 
(x % (UINT64_C(1) << S) == 0)345
;
363
369
}
bool llvm::isShiftedUInt<3u, 0u>(unsigned long long)
Line
Count
Source
355
135
constexpr inline bool isShiftedUInt(uint64_t x) {
356
135
  static_assert(
357
135
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
358
135
  static_assert(N + S <= 64,
359
135
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
360
135
  // Per the two static_asserts above, S must be strictly less than 64.  So
361
135
  // 1 << S is not undefined behavior.
362
135
  return isUInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
363
135
}
bool llvm::isShiftedUInt<32u, 0u>(unsigned long long)
Line
Count
Source
355
281
constexpr inline bool isShiftedUInt(uint64_t x) {
356
281
  static_assert(
357
281
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
358
281
  static_assert(N + S <= 64,
359
281
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
360
281
  // Per the two static_asserts above, S must be strictly less than 64.  So
361
281
  // 1 << S is not undefined behavior.
362
281
  return isUInt<N + S>(x) && 
(x % (UINT64_C(1) << S) == 0)275
;
363
281
}
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
362
constexpr inline bool isShiftedUInt(uint64_t x) {
356
362
  static_assert(
357
362
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
358
362
  static_assert(N + S <= 64,
359
362
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
360
362
  // Per the two static_asserts above, S must be strictly less than 64.  So
361
362
  // 1 << S is not undefined behavior.
362
362
  return isUInt<N + S>(x) && 
(x % (UINT64_C(1) << S) == 0)318
;
363
362
}
364
365
/// Gets the maximum value for a N-bit unsigned integer.
366
235k
inline uint64_t maxUIntN(uint64_t N) {
367
235k
  assert(N > 0 && N <= 64 && "integer width out of range");
368
235k
369
235k
  // uint64_t(1) << 64 is undefined behavior, so we can't do
370
235k
  //   (uint64_t(1) << N) - 1
371
235k
  // without checking first that N != 64.  But this works and doesn't have a
372
235k
  // branch.
373
235k
  return UINT64_MAX >> (64 - N);
374
235k
}
375
376
/// Gets the minimum value for a N-bit signed integer.
377
1.25M
inline int64_t minIntN(int64_t N) {
378
1.25M
  assert(N > 0 && N <= 64 && "integer width out of range");
379
1.25M
380
1.25M
  return -(UINT64_C(1)<<(N-1));
381
1.25M
}
382
383
/// Gets the maximum value for a N-bit signed integer.
384
1.25M
inline int64_t maxIntN(int64_t N) {
385
1.25M
  assert(N > 0 && N <= 64 && "integer width out of range");
386
1.25M
387
1.25M
  // This relies on two's complement wraparound when N == 64, so we convert to
388
1.25M
  // int64_t only at the very end to avoid UB.
389
1.25M
  return (UINT64_C(1) << (N - 1)) - 1;
390
1.25M
}
391
392
/// Checks if an unsigned integer fits into the given (dynamic) bit width.
393
237k
inline bool isUIntN(unsigned N, uint64_t x) {
394
237k
  return N >= 64 || 
x <= maxUIntN(N)235k
;
395
237k
}
396
397
/// Checks if an signed integer fits into the given (dynamic) bit width.
398
2.32M
inline bool isIntN(unsigned N, int64_t x) {
399
2.32M
  return N >= 64 || 
(1.24M
minIntN(N) <= x1.24M
&&
x <= maxIntN(N)1.24M
);
400
2.32M
}
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.1k
constexpr inline bool isMask_32(uint32_t Value) {
406
13.1k
  return Value && 
((Value + 1) & Value) == 013.1k
;
407
13.1k
}
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.15M
constexpr inline bool isMask_64(uint64_t Value) {
412
5.15M
  return Value && 
((Value + 1) & Value) == 04.95M
;
413
5.15M
}
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.32k
constexpr inline bool isShiftedMask_32(uint32_t Value) {
418
7.32k
  return Value && isMask_32((Value - 1) | Value);
419
7.32k
}
420
421
/// Return true if the argument contains a non-empty sequence of ones with the
422
/// remainder zero (64 bit version.)
423
3.23M
constexpr inline bool isShiftedMask_64(uint64_t Value) {
424
3.23M
  return Value && 
isMask_64((Value - 1) | Value)3.23M
;
425
3.23M
}
426
427
/// Return true if the argument is a power of two > 0.
428
/// Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.)
429
15.9M
constexpr inline bool isPowerOf2_32(uint32_t Value) {
430
15.9M
  return Value && 
!(Value & (Value - 1))15.9M
;
431
15.9M
}
432
433
/// Return true if the argument is a power of two > 0 (64 bit edition.)
434
64.6M
constexpr inline bool isPowerOf2_64(uint64_t Value) {
435
64.6M
  return Value && 
!(Value & (Value - 1))64.6M
;
436
64.6M
}
437
438
/// Return a byte-swapped representation of the 16-bit argument.
439
7.80k
inline uint16_t ByteSwap_16(uint16_t Value) {
440
7.80k
  return sys::SwapByteOrder_16(Value);
441
7.80k
}
442
443
/// Return a byte-swapped representation of the 32-bit argument.
444
35.5k
inline uint32_t ByteSwap_32(uint32_t Value) {
445
35.5k
  return sys::SwapByteOrder_32(Value);
446
35.5k
}
447
448
/// Return a byte-swapped representation of the 64-bit argument.
449
4.77k
inline uint64_t ByteSwap_64(uint64_t Value) {
450
4.77k
  return sys::SwapByteOrder_64(Value);
451
4.77k
}
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
58.3M
std::size_t countLeadingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
463
58.3M
  static_assert(std::numeric_limits<T>::is_integer &&
464
58.3M
                    !std::numeric_limits<T>::is_signed,
465
58.3M
                "Only unsigned integral types are allowed.");
466
58.3M
  return countLeadingZeros<T>(~Value, ZB);
467
58.3M
}
unsigned long llvm::countLeadingOnes<unsigned long long>(unsigned long long, llvm::ZeroBehavior)
Line
Count
Source
462
58.3M
std::size_t countLeadingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
463
58.3M
  static_assert(std::numeric_limits<T>::is_integer &&
464
58.3M
                    !std::numeric_limits<T>::is_signed,
465
58.3M
                "Only unsigned integral types are allowed.");
466
58.3M
  return countLeadingZeros<T>(~Value, ZB);
467
58.3M
}
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
235M
std::size_t countTrailingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
479
235M
  static_assert(std::numeric_limits<T>::is_integer &&
480
235M
                    !std::numeric_limits<T>::is_signed,
481
235M
                "Only unsigned integral types are allowed.");
482
235M
  return countTrailingZeros<T>(~Value, ZB);
483
235M
}
unsigned long llvm::countTrailingOnes<unsigned long long>(unsigned long long, llvm::ZeroBehavior)
Line
Count
Source
478
235M
std::size_t countTrailingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
479
235M
  static_assert(std::numeric_limits<T>::is_integer &&
480
235M
                    !std::numeric_limits<T>::is_signed,
481
235M
                "Only unsigned integral types are allowed.");
482
235M
  return countTrailingZeros<T>(~Value, ZB);
483
235M
}
unsigned long llvm::countTrailingOnes<unsigned int>(unsigned int, llvm::ZeroBehavior)
Line
Count
Source
478
5.42k
std::size_t countTrailingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
479
5.42k
  static_assert(std::numeric_limits<T>::is_integer &&
480
5.42k
                    !std::numeric_limits<T>::is_signed,
481
5.42k
                "Only unsigned integral types are allowed.");
482
5.42k
  return countTrailingZeros<T>(~Value, ZB);
483
5.42k
}
484
485
namespace detail {
486
template <typename T, std::size_t SizeOfT> struct PopulationCounter {
487
1.49M
  static unsigned count(T Value) {
488
1.49M
    // Generic version, forward to 32 bits.
489
1.49M
    static_assert(SizeOfT <= 4, "Not implemented!");
490
1.49M
#if __GNUC__ >= 4
491
1.49M
    return __builtin_popcount(Value);
492
1.49M
#else
493
1.49M
    uint32_t v = Value;
494
1.49M
    v = v - ((v >> 1) & 0x55555555);
495
1.49M
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
496
1.49M
    return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
497
1.49M
#endif
498
1.49M
  }
llvm::detail::PopulationCounter<unsigned int, 4ul>::count(unsigned int)
Line
Count
Source
487
1.49M
  static unsigned count(T Value) {
488
1.49M
    // Generic version, forward to 32 bits.
489
1.49M
    static_assert(SizeOfT <= 4, "Not implemented!");
490
1.49M
#if __GNUC__ >= 4
491
1.49M
    return __builtin_popcount(Value);
492
1.49M
#else
493
1.49M
    uint32_t v = Value;
494
1.49M
    v = v - ((v >> 1) & 0x55555555);
495
1.49M
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
496
1.49M
    return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
497
1.49M
#endif
498
1.49M
  }
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
218M
  static unsigned count(T Value) {
503
218M
#if __GNUC__ >= 4
504
218M
    return __builtin_popcountll(Value);
505
218M
#else
506
218M
    uint64_t v = Value;
507
218M
    v = v - ((v >> 1) & 0x5555555555555555ULL);
508
218M
    v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
509
218M
    v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
510
218M
    return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56);
511
218M
#endif
512
218M
  }
llvm::detail::PopulationCounter<unsigned long, 8ul>::count(unsigned long)
Line
Count
Source
502
13.0M
  static unsigned count(T Value) {
503
13.0M
#if __GNUC__ >= 4
504
13.0M
    return __builtin_popcountll(Value);
505
13.0M
#else
506
13.0M
    uint64_t v = Value;
507
13.0M
    v = v - ((v >> 1) & 0x5555555555555555ULL);
508
13.0M
    v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
509
13.0M
    v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
510
13.0M
    return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56);
511
13.0M
#endif
512
13.0M
  }
llvm::detail::PopulationCounter<unsigned long long, 8ul>::count(unsigned long long)
Line
Count
Source
502
205M
  static unsigned count(T Value) {
503
205M
#if __GNUC__ >= 4
504
205M
    return __builtin_popcountll(Value);
505
205M
#else
506
205M
    uint64_t v = Value;
507
205M
    v = v - ((v >> 1) & 0x5555555555555555ULL);
508
205M
    v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
509
205M
    v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
510
205M
    return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56);
511
205M
#endif
512
205M
  }
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
220M
inline unsigned countPopulation(T Value) {
521
220M
  static_assert(std::numeric_limits<T>::is_integer &&
522
220M
                    !std::numeric_limits<T>::is_signed,
523
220M
                "Only unsigned integral types are allowed.");
524
220M
  return detail::PopulationCounter<T, sizeof(T)>::count(Value);
525
220M
}
unsigned int llvm::countPopulation<unsigned long>(unsigned long)
Line
Count
Source
520
13.0M
inline unsigned countPopulation(T Value) {
521
13.0M
  static_assert(std::numeric_limits<T>::is_integer &&
522
13.0M
                    !std::numeric_limits<T>::is_signed,
523
13.0M
                "Only unsigned integral types are allowed.");
524
13.0M
  return detail::PopulationCounter<T, sizeof(T)>::count(Value);
525
13.0M
}
unsigned int llvm::countPopulation<unsigned long long>(unsigned long long)
Line
Count
Source
520
205M
inline unsigned countPopulation(T Value) {
521
205M
  static_assert(std::numeric_limits<T>::is_integer &&
522
205M
                    !std::numeric_limits<T>::is_signed,
523
205M
                "Only unsigned integral types are allowed.");
524
205M
  return detail::PopulationCounter<T, sizeof(T)>::count(Value);
525
205M
}
unsigned int llvm::countPopulation<unsigned int>(unsigned int)
Line
Count
Source
520
1.49M
inline unsigned countPopulation(T Value) {
521
1.49M
  static_assert(std::numeric_limits<T>::is_integer &&
522
1.49M
                    !std::numeric_limits<T>::is_signed,
523
1.49M
                "Only unsigned integral types are allowed.");
524
1.49M
  return detail::PopulationCounter<T, sizeof(T)>::count(Value);
525
1.49M
}
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
56.7M
inline unsigned Log2_32(uint32_t Value) {
540
56.7M
  return 31 - countLeadingZeros(Value);
541
56.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.54M
inline unsigned Log2_64(uint64_t Value) {
546
6.54M
  return 63 - countLeadingZeros(Value);
547
6.54M
}
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
49.8M
inline unsigned Log2_32_Ceil(uint32_t Value) {
553
49.8M
  return 32 - countLeadingZeros(Value - 1);
554
49.8M
}
555
556
/// Return the ceil log base 2 of the specified value, 64 if the value is zero.
557
/// (64 bit edition.)
558
162M
inline unsigned Log2_64_Ceil(uint64_t Value) {
559
162M
  return 64 - countLeadingZeros(Value - 1);
560
162M
}
561
562
/// Return the greatest common divisor of the values using Euclid's algorithm.
563
237k
inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) {
564
655k
  while (B) {
565
417k
    uint64_t T = B;
566
417k
    B = A % B;
567
417k
    A = T;
568
417k
  }
569
237k
  return A;
570
237k
}
571
572
/// This function takes a 64-bit integer and returns the bit equivalent double.
573
38.1k
inline double BitsToDouble(uint64_t Bits) {
574
38.1k
  double D;
575
38.1k
  static_assert(sizeof(uint64_t) == sizeof(double), "Unexpected type sizes");
576
38.1k
  memcpy(&D, &Bits, sizeof(Bits));
577
38.1k
  return D;
578
38.1k
}
579
580
/// This function takes a 32-bit integer and returns the bit equivalent float.
581
39.6k
inline float BitsToFloat(uint32_t Bits) {
582
39.6k
  float F;
583
39.6k
  static_assert(sizeof(uint32_t) == sizeof(float), "Unexpected type sizes");
584
39.6k
  memcpy(&F, &Bits, sizeof(Bits));
585
39.6k
  return F;
586
39.6k
}
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.89M
inline uint64_t DoubleToBits(double Double) {
592
5.89M
  uint64_t Bits;
593
5.89M
  static_assert(sizeof(uint64_t) == sizeof(double), "Unexpected type sizes");
594
5.89M
  memcpy(&Bits, &Double, sizeof(Double));
595
5.89M
  return Bits;
596
5.89M
}
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.34M
inline uint32_t FloatToBits(float Float) {
602
3.34M
  uint32_t Bits;
603
3.34M
  static_assert(sizeof(uint32_t) == sizeof(float), "Unexpected type sizes");
604
3.34M
  memcpy(&Bits, &Float, sizeof(Float));
605
3.34M
  return Bits;
606
3.34M
}
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
27.6M
constexpr inline uint64_t MinAlign(uint64_t A, uint64_t B) {
611
27.6M
  // The largest power of 2 that divides both A and B.
612
27.6M
  //
613
27.6M
  // Replace "-Value" by "1+~Value" in the following commented code to avoid
614
27.6M
  // MSVC warning C4146
615
27.6M
  //    return (A | B) & -(A | B);
616
27.6M
  return (A | B) & (1 + ~(A | B));
617
27.6M
}
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.11G
inline uintptr_t alignAddr(const void *Addr, size_t Alignment) {
624
1.11G
  assert(Alignment && isPowerOf2_64((uint64_t)Alignment) &&
625
1.11G
         "Alignment is not a power of two!");
626
1.11G
627
1.11G
  assert((uintptr_t)Addr + Alignment - 1 >= (uintptr_t)Addr);
628
1.11G
629
1.11G
  return (((uintptr_t)Addr + Alignment - 1) & ~(uintptr_t)(Alignment - 1));
630
1.11G
}
631
632
/// Returns the necessary adjustment for aligning \c Ptr to \c Alignment
633
/// bytes, rounding up.
634
1.09G
inline size_t alignmentAdjustment(const void *Ptr, size_t Alignment) {
635
1.09G
  return alignAddr(Ptr, Alignment) - (uintptr_t)Ptr;
636
1.09G
}
637
638
/// Returns the next power of two (in 64-bits) that is strictly greater than A.
639
/// Returns zero on overflow.
640
380M
inline uint64_t NextPowerOf2(uint64_t A) {
641
380M
  A |= (A >> 1);
642
380M
  A |= (A >> 2);
643
380M
  A |= (A >> 4);
644
380M
  A |= (A >> 8);
645
380M
  A |= (A >> 16);
646
380M
  A |= (A >> 32);
647
380M
  return A + 1;
648
380M
}
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
634k
inline uint64_t PowerOf2Floor(uint64_t A) {
653
634k
  if (!A) 
return 0602
;
654
633k
  return 1ull << (63 - countLeadingZeros(A, ZB_Undefined));
655
633k
}
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.57M
inline uint64_t PowerOf2Ceil(uint64_t A) {
660
1.57M
  if (!A)
661
200
    return 0;
662
1.57M
  return NextPowerOf2(A - 1);
663
1.57M
}
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
691M
inline uint64_t alignTo(uint64_t Value, uint64_t Align, uint64_t Skew = 0) {
686
691M
  assert(Align != 0u && "Align can't be 0.");
687
691M
  Skew %= Align;
688
691M
  return (Value + Align - 1 - Skew) / Align * Align + Skew;
689
691M
}
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
21.8M
template <uint64_t Align> constexpr inline uint64_t alignTo(uint64_t Value) {
694
21.8M
  static_assert(Align != 0u, "Align must be non-zero");
695
21.8M
  return (Value + Align - 1) / Align * Align;
696
21.8M
}
unsigned long long llvm::alignTo<8ull>(unsigned long long)
Line
Count
Source
693
21.8M
template <uint64_t Align> constexpr inline uint64_t alignTo(uint64_t Value) {
694
21.8M
  static_assert(Align != 0u, "Align must be non-zero");
695
21.8M
  return (Value + Align - 1) / Align * Align;
696
21.8M
}
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
230k
inline uint64_t divideCeil(uint64_t Numerator, uint64_t Denominator) {
700
230k
  return alignTo(Numerator, Denominator) / Denominator;
701
230k
}
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
627k
inline uint64_t alignDown(uint64_t Value, uint64_t Align, uint64_t Skew = 0) {
719
627k
  assert(Align != 0u && "Align can't be 0.");
720
627k
  Skew %= Align;
721
627k
  return (Value - Skew) / Align * Align + Skew;
722
627k
}
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.24M
inline uint64_t OffsetToAlignment(uint64_t Value, uint64_t Align) {
728
2.24M
  return alignTo(Value, Align) - Value;
729
2.24M
}
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.87k
template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
734
2.87k
  static_assert(B > 0, "Bit width can't be 0.");
735
2.87k
  static_assert(B <= 32, "Bit width out of range.");
736
2.87k
  return int32_t(X << (32 - B)) >> (32 - B);
737
2.87k
}
int llvm::SignExtend32<13u>(unsigned int)
Line
Count
Source
733
1.71k
template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
734
1.71k
  static_assert(B > 0, "Bit width can't be 0.");
735
1.71k
  static_assert(B <= 32, "Bit width out of range.");
736
1.71k
  return int32_t(X << (32 - B)) >> (32 - B);
737
1.71k
}
int llvm::SignExtend32<5u>(unsigned int)
Line
Count
Source
733
272
template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
734
272
  static_assert(B > 0, "Bit width can't be 0.");
735
272
  static_assert(B <= 32, "Bit width out of range.");
736
272
  return int32_t(X << (32 - B)) >> (32 - B);
737
272
}
int llvm::SignExtend32<26u>(unsigned int)
Line
Count
Source
733
653
template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
734
653
  static_assert(B > 0, "Bit width can't be 0.");
735
653
  static_assert(B <= 32, "Bit width out of range.");
736
653
  return int32_t(X << (32 - B)) >> (32 - B);
737
653
}
int llvm::SignExtend32<32u>(unsigned int)
Line
Count
Source
733
226
template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
734
226
  static_assert(B > 0, "Bit width can't be 0.");
735
226
  static_assert(B <= 32, "Bit width out of range.");
736
226
  return int32_t(X << (32 - B)) >> (32 - B);
737
226
}
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.08k
inline int32_t SignExtend32(uint32_t X, unsigned B) {
742
6.08k
  assert(B > 0 && "Bit width can't be 0.");
743
6.08k
  assert(B <= 32 && "Bit width out of range.");
744
6.08k
  return int32_t(X << (32 - B)) >> (32 - B);
745
6.08k
}
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.17k
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
750
9.17k
  static_assert(B > 0, "Bit width can't be 0.");
751
9.17k
  static_assert(B <= 64, "Bit width out of range.");
752
9.17k
  return int64_t(x << (64 - B)) >> (64 - B);
753
9.17k
}
long long llvm::SignExtend64<16u>(unsigned long long)
Line
Count
Source
749
4.14k
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
750
4.14k
  static_assert(B > 0, "Bit width can't be 0.");
751
4.14k
  static_assert(B <= 64, "Bit width out of range.");
752
4.14k
  return int64_t(x << (64 - B)) >> (64 - B);
753
4.14k
}
long long llvm::SignExtend64<32u>(unsigned long long)
Line
Count
Source
749
4.73k
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
750
4.73k
  static_assert(B > 0, "Bit width can't be 0.");
751
4.73k
  static_assert(B <= 64, "Bit width out of range.");
752
4.73k
  return int64_t(x << (64 - B)) >> (64 - B);
753
4.73k
}
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
95
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
750
95
  static_assert(B > 0, "Bit width can't be 0.");
751
95
  static_assert(B <= 64, "Bit width out of range.");
752
95
  return int64_t(x << (64 - B)) >> (64 - B);
753
95
}
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
637M
inline int64_t SignExtend64(uint64_t X, unsigned B) {
758
637M
  assert(B > 0 && "Bit width can't be 0.");
759
637M
  assert(B <= 64 && "Bit width out of range.");
760
637M
  return int64_t(X << (64 - B)) >> (64 - B);
761
637M
}
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
1.13M
SaturatingAdd(T X, T Y, bool *ResultOverflowed = nullptr) {
777
1.13M
  bool Dummy;
778
1.13M
  bool &Overflowed = ResultOverflowed ? 
*ResultOverflowed2.66k
:
Dummy1.12M
;
779
1.13M
  // Hacker's Delight, p. 29
780
1.13M
  T Z = X + Y;
781
1.13M
  Overflowed = (Z < X || 
Z < Y1.13M
);
782
1.13M
  if (Overflowed)
783
25
    return std::numeric_limits<T>::max();
784
1.13M
  else
785
1.13M
    return Z;
786
1.13M
}
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
3.02k
SaturatingMultiply(T X, T Y, bool *ResultOverflowed = nullptr) {
794
3.02k
  bool Dummy;
795
3.02k
  bool &Overflowed = ResultOverflowed ? 
*ResultOverflowed2.82k
:
Dummy199
;
796
3.02k
797
3.02k
  // Hacker's Delight, p. 30 has a different algorithm, but we don't use that
798
3.02k
  // because it fails for uint16_t (where multiplication can have undefined
799
3.02k
  // behavior due to promotion to int), and requires a division in addition
800
3.02k
  // to the multiplication.
801
3.02k
802
3.02k
  Overflowed = false;
803
3.02k
804
3.02k
  // Log2(Z) would be either Log2Z or Log2Z + 1.
805
3.02k
  // Special case: if X or Y is 0, Log2_64 gives -1, and Log2Z
806
3.02k
  // will necessarily be less than Log2Max as desired.
807
3.02k
  int Log2Z = Log2_64(X) + Log2_64(Y);
808
3.02k
  const T Max = std::numeric_limits<T>::max();
809
3.02k
  int Log2Max = Log2_64(Max);
810
3.02k
  if (Log2Z < Log2Max) {
811
2.70k
    return X * Y;
812
2.70k
  }
813
324
  if (Log2Z > Log2Max) {
814
12
    Overflowed = true;
815
12
    return Max;
816
12
  }
817
312
818
312
  // We're going to use the top bit, and maybe overflow one
819
312
  // bit past it. Multiply all but the bottom bit then add
820
312
  // that on at the end.
821
312
  T Z = (X >> 1) * Y;
822
312
  if (Z & ~(Max >> 1)) {
823
62
    Overflowed = true;
824
62
    return Max;
825
62
  }
826
250
  Z <<= 1;
827
250
  if (X & 1)
828
248
    return SaturatingAdd(Z, Y, ResultOverflowed);
829
2
830
2
  return Z;
831
2
}
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.51k
SaturatingMultiplyAdd(T X, T Y, T A, bool *ResultOverflowed = nullptr) {
840
2.51k
  bool Dummy;
841
2.51k
  bool &Overflowed = ResultOverflowed ? 
*ResultOverflowed2.49k
:
Dummy21
;
842
2.51k
843
2.51k
  T Product = SaturatingMultiply(X, Y, &Overflowed);
844
2.51k
  if (Overflowed)
845
6
    return Product;
846
2.51k
847
2.51k
  return SaturatingAdd(A, Product, &Overflowed);
848
2.51k
}
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