Coverage Report

Created: 2019-07-24 05:18

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