Coverage Report

Created: 2019-02-21 13:17

/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
172
  static std::size_t count(T Val, ZeroBehavior) {
55
172
    if (!Val)
56
1
      return std::numeric_limits<T>::digits;
57
171
    if (Val & 0x1)
58
35
      return 0;
59
136
60
136
    // Bisection method.
61
136
    std::size_t ZeroBits = 0;
62
136
    T Shift = std::numeric_limits<T>::digits >> 1;
63
136
    T Mask = std::numeric_limits<T>::max() >> Shift;
64
544
    while (Shift) {
65
408
      if ((Val & Mask) == 0) {
66
214
        Val >>= Shift;
67
214
        ZeroBits |= Shift;
68
214
      }
69
408
      Shift >>= 1;
70
408
      Mask >>= Shift;
71
408
    }
72
136
    return ZeroBits;
73
136
  }
74
};
75
76
#if __GNUC__ >= 4 || defined(_MSC_VER)
77
template <typename T> struct TrailingZerosCounter<T, 4> {
78
40.2M
  static std::size_t count(T Val, ZeroBehavior ZB) {
79
40.2M
    if (ZB != ZB_Undefined && 
Val == 040.2M
)
80
1
      return 32;
81
40.2M
82
40.2M
#if __has_builtin(__builtin_ctz) || LLVM_GNUC_PREREQ(4, 0, 0)
83
40.2M
    return __builtin_ctz(Val);
84
40.2M
#elif defined(_MSC_VER)
85
40.2M
    unsigned long Index;
86
40.2M
    _BitScanForward(&Index, Val);
87
40.2M
    return Index;
88
40.2M
#endif
89
40.2M
  }
90
};
91
92
#if !defined(_MSC_VER) || defined(_M_X64)
93
template <typename T> struct TrailingZerosCounter<T, 8> {
94
655M
  static std::size_t count(T Val, ZeroBehavior ZB) {
95
655M
    if (ZB != ZB_Undefined && 
Val == 0535M
)
96
40.5M
      return 64;
97
615M
98
615M
#if __has_builtin(__builtin_ctzll) || LLVM_GNUC_PREREQ(4, 0, 0)
99
615M
    return __builtin_ctzll(Val);
100
615M
#elif defined(_MSC_VER)
101
615M
    unsigned long Index;
102
615M
    _BitScanForward64(&Index, Val);
103
615M
    return Index;
104
615M
#endif
105
615M
  }
llvm::detail::TrailingZerosCounter<unsigned long long, 8ul>::count(unsigned long long, llvm::ZeroBehavior)
Line
Count
Source
94
427M
  static std::size_t count(T Val, ZeroBehavior ZB) {
95
427M
    if (ZB != ZB_Undefined && 
Val == 0306M
)
96
40.5M
      return 64;
97
386M
98
386M
#if __has_builtin(__builtin_ctzll) || LLVM_GNUC_PREREQ(4, 0, 0)
99
386M
    return __builtin_ctzll(Val);
100
386M
#elif defined(_MSC_VER)
101
386M
    unsigned long Index;
102
386M
    _BitScanForward64(&Index, Val);
103
386M
    return Index;
104
386M
#endif
105
386M
  }
llvm::detail::TrailingZerosCounter<unsigned long, 8ul>::count(unsigned long, llvm::ZeroBehavior)
Line
Count
Source
94
228M
  static std::size_t count(T Val, ZeroBehavior ZB) {
95
228M
    if (ZB != ZB_Undefined && 
Val == 0228M
)
96
0
      return 64;
97
228M
98
228M
#if __has_builtin(__builtin_ctzll) || LLVM_GNUC_PREREQ(4, 0, 0)
99
228M
    return __builtin_ctzll(Val);
100
228M
#elif defined(_MSC_VER)
101
228M
    unsigned long Index;
102
228M
    _BitScanForward64(&Index, Val);
103
228M
    return Index;
104
228M
#endif
105
228M
  }
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
695M
std::size_t countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
120
695M
  static_assert(std::numeric_limits<T>::is_integer &&
121
695M
                    !std::numeric_limits<T>::is_signed,
122
695M
                "Only unsigned integral types are allowed.");
123
695M
  return llvm::detail::TrailingZerosCounter<T, sizeof(T)>::count(Val, ZB);
124
695M
}
unsigned long llvm::countTrailingZeros<unsigned long long>(unsigned long long, llvm::ZeroBehavior)
Line
Count
Source
119
427M
std::size_t countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
120
427M
  static_assert(std::numeric_limits<T>::is_integer &&
121
427M
                    !std::numeric_limits<T>::is_signed,
122
427M
                "Only unsigned integral types are allowed.");
123
427M
  return llvm::detail::TrailingZerosCounter<T, sizeof(T)>::count(Val, ZB);
124
427M
}
unsigned long llvm::countTrailingZeros<unsigned long>(unsigned long, llvm::ZeroBehavior)
Line
Count
Source
119
228M
std::size_t countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
120
228M
  static_assert(std::numeric_limits<T>::is_integer &&
121
228M
                    !std::numeric_limits<T>::is_signed,
122
228M
                "Only unsigned integral types are allowed.");
123
228M
  return llvm::detail::TrailingZerosCounter<T, sizeof(T)>::count(Val, ZB);
124
228M
}
unsigned long llvm::countTrailingZeros<unsigned int>(unsigned int, llvm::ZeroBehavior)
Line
Count
Source
119
40.2M
std::size_t countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
120
40.2M
  static_assert(std::numeric_limits<T>::is_integer &&
121
40.2M
                    !std::numeric_limits<T>::is_signed,
122
40.2M
                "Only unsigned integral types are allowed.");
123
40.2M
  return llvm::detail::TrailingZerosCounter<T, sizeof(T)>::count(Val, ZB);
124
40.2M
}
unsigned long llvm::countTrailingZeros<unsigned char>(unsigned char, llvm::ZeroBehavior)
Line
Count
Source
119
172
std::size_t countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
120
172
  static_assert(std::numeric_limits<T>::is_integer &&
121
172
                    !std::numeric_limits<T>::is_signed,
122
172
                "Only unsigned integral types are allowed.");
123
172
  return llvm::detail::TrailingZerosCounter<T, sizeof(T)>::count(Val, ZB);
124
172
}
125
126
namespace detail {
127
template <typename T, std::size_t SizeOfT> struct LeadingZerosCounter {
128
3
  static std::size_t count(T Val, ZeroBehavior) {
129
3
    if (!Val)
130
1
      return std::numeric_limits<T>::digits;
131
2
132
2
    // Bisection method.
133
2
    std::size_t 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
122M
  static std::size_t count(T Val, ZeroBehavior ZB) {
148
122M
    if (
ZB != ZB_Undefined122M
&& Val == 0)
149
43.1M
      return 32;
150
79.4M
151
79.4M
#if __has_builtin(__builtin_clz) || LLVM_GNUC_PREREQ(4, 0, 0)
152
79.4M
    return __builtin_clz(Val);
153
79.4M
#elif defined(_MSC_VER)
154
79.4M
    unsigned long Index;
155
79.4M
    _BitScanReverse(&Index, Val);
156
79.4M
    return Index ^ 31;
157
79.4M
#endif
158
79.4M
  }
159
};
160
161
#if !defined(_MSC_VER) || defined(_M_X64)
162
template <typename T> struct LeadingZerosCounter<T, 8> {
163
598M
  static std::size_t count(T Val, ZeroBehavior ZB) {
164
598M
    if (ZB != ZB_Undefined && 
Val == 0592M
)
165
47.6M
      return 64;
166
550M
167
550M
#if __has_builtin(__builtin_clzll) || LLVM_GNUC_PREREQ(4, 0, 0)
168
550M
    return __builtin_clzll(Val);
169
550M
#elif defined(_MSC_VER)
170
550M
    unsigned long Index;
171
550M
    _BitScanReverse64(&Index, Val);
172
550M
    return Index ^ 63;
173
550M
#endif
174
550M
  }
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
721M
std::size_t countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
189
721M
  static_assert(std::numeric_limits<T>::is_integer &&
190
721M
                    !std::numeric_limits<T>::is_signed,
191
721M
                "Only unsigned integral types are allowed.");
192
721M
  return llvm::detail::LeadingZerosCounter<T, sizeof(T)>::count(Val, ZB);
193
721M
}
unsigned long llvm::countLeadingZeros<unsigned int>(unsigned int, llvm::ZeroBehavior)
Line
Count
Source
188
122M
std::size_t countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
189
122M
  static_assert(std::numeric_limits<T>::is_integer &&
190
122M
                    !std::numeric_limits<T>::is_signed,
191
122M
                "Only unsigned integral types are allowed.");
192
122M
  return llvm::detail::LeadingZerosCounter<T, sizeof(T)>::count(Val, ZB);
193
122M
}
unsigned long llvm::countLeadingZeros<unsigned long long>(unsigned long long, llvm::ZeroBehavior)
Line
Count
Source
188
598M
std::size_t countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) {
189
598M
  static_assert(std::numeric_limits<T>::is_integer &&
190
598M
                    !std::numeric_limits<T>::is_signed,
191
598M
                "Only unsigned integral types are allowed.");
192
598M
  return llvm::detail::LeadingZerosCounter<T, sizeof(T)>::count(Val, ZB);
193
598M
}
unsigned long llvm::countLeadingZeros<unsigned short>(unsigned short, llvm::ZeroBehavior)
Line
Count
Source
188
3
std::size_t 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
120M
template <typename T> T findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) {
203
120M
  if (ZB == ZB_Max && Val == 0)
204
2
    return std::numeric_limits<T>::max();
205
120M
206
120M
  return countTrailingZeros(Val, ZB_Undefined);
207
120M
}
unsigned long long llvm::findFirstSet<unsigned long long>(unsigned long long, llvm::ZeroBehavior)
Line
Count
Source
202
120M
template <typename T> T findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) {
203
120M
  if (ZB == ZB_Max && Val == 0)
204
1
    return std::numeric_limits<T>::max();
205
120M
206
120M
  return countTrailingZeros(Val, ZB_Undefined);
207
120M
}
unsigned int llvm::findFirstSet<unsigned int>(unsigned int, llvm::ZeroBehavior)
Line
Count
Source
202
62
template <typename T> T findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) {
203
62
  if (ZB == ZB_Max && Val == 0)
204
1
    return std::numeric_limits<T>::max();
205
61
206
61
  return countTrailingZeros(Val, ZB_Undefined);
207
61
}
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
466M
template <typename T> T maskTrailingOnes(unsigned N) {
212
466M
  static_assert(std::is_unsigned<T>::value, "Invalid type!");
213
466M
  const unsigned Bits = CHAR_BIT * sizeof(T);
214
466M
  assert(N <= Bits && "Invalid bit index");
215
466M
  return N == 0 ? 
022.8M
:
(T(-1) >> (Bits - N))443M
;
216
466M
}
unsigned long llvm::maskTrailingOnes<unsigned long>(unsigned int)
Line
Count
Source
211
338M
template <typename T> T maskTrailingOnes(unsigned N) {
212
338M
  static_assert(std::is_unsigned<T>::value, "Invalid type!");
213
338M
  const unsigned Bits = CHAR_BIT * sizeof(T);
214
338M
  assert(N <= Bits && "Invalid bit index");
215
338M
  return N == 0 ? 
022.8M
:
(T(-1) >> (Bits - N))315M
;
216
338M
}
unsigned long long llvm::maskTrailingOnes<unsigned long long>(unsigned int)
Line
Count
Source
211
127M
template <typename T> T maskTrailingOnes(unsigned N) {
212
127M
  static_assert(std::is_unsigned<T>::value, "Invalid type!");
213
127M
  const unsigned Bits = CHAR_BIT * sizeof(T);
214
127M
  assert(N <= Bits && "Invalid bit index");
215
127M
  return N == 0 ? 
035.4k
:
(T(-1) >> (Bits - N))127M
;
216
127M
}
unsigned int llvm::maskTrailingOnes<unsigned int>(unsigned int)
Line
Count
Source
211
265
template <typename T> T maskTrailingOnes(unsigned N) {
212
265
  static_assert(std::is_unsigned<T>::value, "Invalid type!");
213
265
  const unsigned Bits = CHAR_BIT * sizeof(T);
214
265
  assert(N <= Bits && "Invalid bit index");
215
265
  return N == 0 ? 
02
:
(T(-1) >> (Bits - N))263
;
216
265
}
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
360M
template <typename T> T maskLeadingOnes(unsigned N) {
221
360M
  return ~maskTrailingOnes<T>(CHAR_BIT * sizeof(T) - N);
222
360M
}
unsigned long llvm::maskLeadingOnes<unsigned long>(unsigned int)
Line
Count
Source
220
233M
template <typename T> T maskLeadingOnes(unsigned N) {
221
233M
  return ~maskTrailingOnes<T>(CHAR_BIT * sizeof(T) - N);
222
233M
}
unsigned long long llvm::maskLeadingOnes<unsigned long long>(unsigned int)
Line
Count
Source
220
127M
template <typename T> T maskLeadingOnes(unsigned N) {
221
127M
  return ~maskTrailingOnes<T>(CHAR_BIT * sizeof(T) - N);
222
127M
}
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
233M
template <typename T> T maskTrailingZeros(unsigned N) {
227
233M
  return maskLeadingOnes<T>(CHAR_BIT * sizeof(T) - N);
228
233M
}
unsigned long llvm::maskTrailingZeros<unsigned long>(unsigned int)
Line
Count
Source
226
233M
template <typename T> T maskTrailingZeros(unsigned N) {
227
233M
  return maskLeadingOnes<T>(CHAR_BIT * sizeof(T) - N);
228
233M
}
unsigned long long llvm::maskTrailingZeros<unsigned long long>(unsigned int)
Line
Count
Source
226
930
template <typename T> T maskTrailingZeros(unsigned N) {
227
930
  return maskLeadingOnes<T>(CHAR_BIT * sizeof(T) - N);
228
930
}
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.39M
template <typename T> T findLastSet(T Val, ZeroBehavior ZB = ZB_Max) {
244
5.39M
  if (ZB == ZB_Max && 
Val == 05.39M
)
245
1
    return std::numeric_limits<T>::max();
246
5.39M
247
5.39M
  // Use ^ instead of - because both gcc and llvm can remove the associated ^
248
5.39M
  // in the __builtin_clz intrinsic on x86.
249
5.39M
  return countLeadingZeros(Val, ZB_Undefined) ^
250
5.39M
         (std::numeric_limits<T>::digits - 1);
251
5.39M
}
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
20.3k
T reverseBits(T Val) {
269
20.3k
  unsigned char in[sizeof(Val)];
270
20.3k
  unsigned char out[sizeof(Val)];
271
20.3k
  std::memcpy(in, &Val, sizeof(Val));
272
106k
  for (unsigned i = 0; i < sizeof(Val); 
++i86.2k
)
273
86.2k
    out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]];
274
20.3k
  std::memcpy(&Val, out, sizeof(Val));
275
20.3k
  return Val;
276
20.3k
}
int llvm::reverseBits<int>(int)
Line
Count
Source
268
14.3k
T reverseBits(T Val) {
269
14.3k
  unsigned char in[sizeof(Val)];
270
14.3k
  unsigned char out[sizeof(Val)];
271
14.3k
  std::memcpy(in, &Val, sizeof(Val));
272
71.6k
  for (unsigned i = 0; i < sizeof(Val); 
++i57.3k
)
273
57.3k
    out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]];
274
14.3k
  std::memcpy(&Val, out, sizeof(Val));
275
14.3k
  return Val;
276
14.3k
}
unsigned int llvm::reverseBits<unsigned int>(unsigned int)
Line
Count
Source
268
3.76k
T reverseBits(T Val) {
269
3.76k
  unsigned char in[sizeof(Val)];
270
3.76k
  unsigned char out[sizeof(Val)];
271
3.76k
  std::memcpy(in, &Val, sizeof(Val));
272
18.8k
  for (unsigned i = 0; i < sizeof(Val); 
++i15.0k
)
273
15.0k
    out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]];
274
3.76k
  std::memcpy(&Val, out, sizeof(Val));
275
3.76k
  return Val;
276
3.76k
}
unsigned long long llvm::reverseBits<unsigned long long>(unsigned long long)
Line
Count
Source
268
1.62k
T reverseBits(T Val) {
269
1.62k
  unsigned char in[sizeof(Val)];
270
1.62k
  unsigned char out[sizeof(Val)];
271
1.62k
  std::memcpy(in, &Val, sizeof(Val));
272
14.5k
  for (unsigned i = 0; i < sizeof(Val); 
++i12.9k
)
273
12.9k
    out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]];
274
1.62k
  std::memcpy(&Val, out, sizeof(Val));
275
1.62k
  return Val;
276
1.62k
}
unsigned short llvm::reverseBits<unsigned short>(unsigned short)
Line
Count
Source
268
281
T reverseBits(T Val) {
269
281
  unsigned char in[sizeof(Val)];
270
281
  unsigned char out[sizeof(Val)];
271
281
  std::memcpy(in, &Val, sizeof(Val));
272
843
  for (unsigned i = 0; i < sizeof(Val); 
++i562
)
273
562
    out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]];
274
281
  std::memcpy(&Val, out, sizeof(Val));
275
281
  return Val;
276
281
}
unsigned char llvm::reverseBits<unsigned char>(unsigned char)
Line
Count
Source
268
311
T reverseBits(T Val) {
269
311
  unsigned char in[sizeof(Val)];
270
311
  unsigned char out[sizeof(Val)];
271
311
  std::memcpy(in, &Val, sizeof(Val));
272
622
  for (unsigned i = 0; i < sizeof(Val); 
++i311
)
273
311
    out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]];
274
311
  std::memcpy(&Val, out, sizeof(Val));
275
311
  return Val;
276
311
}
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
27.1M
constexpr inline uint32_t Hi_32(uint64_t Value) {
284
27.1M
  return static_cast<uint32_t>(Value >> 32);
285
27.1M
}
286
287
/// Return the low 32 bits of a 64 bit value.
288
46.1M
constexpr inline uint32_t Lo_32(uint64_t Value) {
289
46.1M
  return static_cast<uint32_t>(Value);
290
46.1M
}
291
292
/// Make a 64-bit integer from a high / low pair of 32-bit integers.
293
19.5M
constexpr inline uint64_t Make_64(uint32_t High, uint32_t Low) {
294
19.5M
  return ((uint64_t)High << 32) | (uint64_t)Low;
295
19.5M
}
296
297
/// Checks if an integer fits into the given bit width.
298
25.3M
template <unsigned N> constexpr inline bool isInt(int64_t x) {
299
25.3M
  return N >= 64 || 
(25.3M
-(INT64_C(1)<<(N-1)) <= x25.3M
&&
x < (INT64_C(1)<<(N-1))24.7M
);
300
25.3M
}
bool llvm::isInt<9u>(long long)
Line
Count
Source
298
25.0M
template <unsigned N> constexpr inline bool isInt(int64_t x) {
299
25.0M
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && 
x < (INT64_C(1)<<(N-1))24.4M
);
300
25.0M
}
bool llvm::isInt<21u>(long long)
Line
Count
Source
298
7.84k
template <unsigned N> constexpr inline bool isInt(int64_t x) {
299
7.84k
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && 
x < (INT64_C(1)<<(N-1))7.81k
);
300
7.84k
}
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<13u>(long long)
Line
Count
Source
298
32.5k
template <unsigned N> constexpr inline bool isInt(int64_t x) {
299
32.5k
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && 
x < (INT64_C(1)<<(N-1))32.4k
);
300
32.5k
}
bool llvm::isInt<25u>(long long)
Line
Count
Source
298
57.4k
template <unsigned N> constexpr inline bool isInt(int64_t x) {
299
57.4k
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && 
x < (INT64_C(1)<<(N-1))57.4k
);
300
57.4k
}
bool llvm::isInt<23u>(long long)
Line
Count
Source
298
379
template <unsigned N> constexpr inline bool isInt(int64_t x) {
299
379
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && 
x < (INT64_C(1)<<(N-1))377
);
300
379
}
bool llvm::isInt<12u>(long long)
Line
Count
Source
298
53
template <unsigned N> constexpr inline bool isInt(int64_t x) {
299
53
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && 
x < (INT64_C(1)<<(N-1))35
);
300
53
}
bool llvm::isInt<10u>(long long)
Line
Count
Source
298
449
template <unsigned N> constexpr inline bool isInt(int64_t x) {
299
449
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && 
x < (INT64_C(1)<<(N-1))423
);
300
449
}
bool llvm::isInt<6u>(long long)
Line
Count
Source
298
82
template <unsigned N> constexpr inline bool isInt(int64_t x) {
299
82
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && 
x < (INT64_C(1)<<(N-1))76
);
300
82
}
bool llvm::isInt<11u>(long long)
Line
Count
Source
298
39.9k
template <unsigned N> constexpr inline bool isInt(int64_t x) {
299
39.9k
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && 
x < (INT64_C(1)<<(N-1))39.6k
);
300
39.9k
}
bool llvm::isInt<24u>(long long)
Line
Count
Source
298
161
template <unsigned N> constexpr inline bool isInt(int64_t x) {
299
161
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1)));
300
161
}
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.49k
template <unsigned N> constexpr inline bool isInt(int64_t x) {
299
1.49k
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && 
x < (INT64_C(1)<<(N-1))1.49k
);
300
1.49k
}
bool llvm::isInt<3u>(long long)
Line
Count
Source
298
314
template <unsigned N> constexpr inline bool isInt(int64_t x) {
299
314
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1)));
300
314
}
bool llvm::isInt<7u>(long long)
Line
Count
Source
298
188
template <unsigned N> constexpr inline bool isInt(int64_t x) {
299
188
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && 
x < (INT64_C(1)<<(N-1))185
);
300
188
}
bool llvm::isInt<5u>(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))172
);
300
192
}
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.43k
template <unsigned N> constexpr inline bool isInt(int64_t x) {
299
1.43k
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1)));
300
1.43k
}
bool llvm::isInt<28u>(long long)
Line
Count
Source
298
107
template <unsigned N> constexpr inline bool isInt(int64_t x) {
299
107
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1)));
300
107
}
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.28k
template <unsigned N> constexpr inline bool isInt(int64_t x) {
299
1.28k
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && 
x < (INT64_C(1)<<(N-1))1.26k
);
300
1.28k
}
bool llvm::isInt<19u>(long long)
Line
Count
Source
298
20
template <unsigned N> constexpr inline bool isInt(int64_t x) {
299
20
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1)));
300
20
}
bool llvm::isInt<26u>(long long)
Line
Count
Source
298
259
template <unsigned N> constexpr inline bool isInt(int64_t x) {
299
259
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && 
x < (INT64_C(1)<<(N-1))250
);
300
259
}
bool llvm::isInt<20u>(long long)
Line
Count
Source
298
30.2k
template <unsigned N> constexpr inline bool isInt(int64_t x) {
299
30.2k
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && 
x < (INT64_C(1)<<(N-1))29.4k
);
300
30.2k
}
bool llvm::isInt<31u>(long long)
Line
Count
Source
298
129k
template <unsigned N> constexpr inline bool isInt(int64_t x) {
299
129k
  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && 
x < (INT64_C(1)<<(N-1))129k
);
300
129k
}
301
// Template specializations to get better code for common cases.
302
414k
template <> constexpr inline bool isInt<8>(int64_t x) {
303
414k
  return static_cast<int8_t>(x) == x;
304
414k
}
305
431k
template <> constexpr inline bool isInt<16>(int64_t x) {
306
431k
  return static_cast<int16_t>(x) == x;
307
431k
}
308
6.74M
template <> constexpr inline bool isInt<32>(int64_t x) {
309
6.74M
  return static_cast<int32_t>(x) == x;
310
6.74M
}
311
312
/// Checks if a signed integer is an N bit number shifted left by S.
313
template <unsigned N, unsigned S>
314
5.72k
constexpr inline bool isShiftedInt(int64_t x) {
315
5.72k
  static_assert(
316
5.72k
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
317
5.72k
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
318
5.72k
  return isInt<N + S>(x) && 
(x % (UINT64_C(1) << S) == 0)4.15k
;
319
5.72k
}
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.10k
;
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.40k
constexpr inline bool isShiftedInt(int64_t x) {
315
1.40k
  static_assert(
316
1.40k
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
317
1.40k
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
318
1.40k
  return isInt<N + S>(x) && 
(x % (UINT64_C(1) << S) == 0)1.40k
;
319
1.40k
}
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<7u, 0u>(long long)
Line
Count
Source
314
183
constexpr inline bool isShiftedInt(int64_t x) {
315
183
  static_assert(
316
183
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
317
183
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
318
183
  return isInt<N + S>(x) && 
(x % (UINT64_C(1) << S) == 0)149
;
319
183
}
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
940
constexpr inline bool isShiftedInt(int64_t x) {
315
940
  static_assert(
316
940
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
317
940
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
318
940
  return isInt<N + S>(x) && 
(x % (UINT64_C(1) << S) == 0)502
;
319
940
}
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
136
constexpr inline bool isShiftedInt(int64_t x) {
315
136
  static_assert(
316
136
      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
317
136
  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
318
136
  return isInt<N + S>(x) && 
(x % (UINT64_C(1) << S) == 0)80
;
319
136
}
Unexecuted instantiation: bool llvm::isShiftedInt<7u, 2u>(long long)
Unexecuted instantiation: bool llvm::isShiftedInt<16u, 16u>(long long)
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.18M
isUInt(uint64_t X) {
332
3.18M
  static_assert(N > 0, "isUInt<0> doesn't make sense");
333
3.18M
  return X < (UINT64_C(1) << (N));
334
3.18M
}
std::__1::enable_if<(5u) < (64), bool>::type llvm::isUInt<5u>(unsigned long long)
Line
Count
Source
331
19.4k
isUInt(uint64_t X) {
332
19.4k
  static_assert(N > 0, "isUInt<0> doesn't make sense");
333
19.4k
  return X < (UINT64_C(1) << (N));
334
19.4k
}
std::__1::enable_if<(12u) < (64), bool>::type llvm::isUInt<12u>(unsigned long long)
Line
Count
Source
331
116k
isUInt(uint64_t X) {
332
116k
  static_assert(N > 0, "isUInt<0> doesn't make sense");
333
116k
  return X < (UINT64_C(1) << (N));
334
116k
}
std::__1::enable_if<(24u) < (64), bool>::type llvm::isUInt<24u>(unsigned long long)
Line
Count
Source
331
2.81M
isUInt(uint64_t X) {
332
2.81M
  static_assert(N > 0, "isUInt<0> doesn't make sense");
333
2.81M
  return X < (UINT64_C(1) << (N));
334
2.81M
}
std::__1::enable_if<(20u) < (64), bool>::type llvm::isUInt<20u>(unsigned long long)
Line
Count
Source
331
55.3k
isUInt(uint64_t X) {
332
55.3k
  static_assert(N > 0, "isUInt<0> doesn't make sense");
333
55.3k
  return X < (UINT64_C(1) << (N));
334
55.3k
}
std::__1::enable_if<(6u) < (64), bool>::type llvm::isUInt<6u>(unsigned long long)
Line
Count
Source
331
136k
isUInt(uint64_t X) {
332
136k
  static_assert(N > 0, "isUInt<0> doesn't make sense");
333
136k
  return X < (UINT64_C(1) << (N));
334
136k
}
std::__1::enable_if<(1u) < (64), bool>::type llvm::isUInt<1u>(unsigned long long)
Line
Count
Source
331
913
isUInt(uint64_t X) {
332
913
  static_assert(N > 0, "isUInt<0> doesn't make sense");
333
913
  return X < (UINT64_C(1) << (N));
334
913
}
std::__1::enable_if<(2u) < (64), bool>::type llvm::isUInt<2u>(unsigned long long)
Line
Count
Source
331
3.23k
isUInt(uint64_t X) {
332
3.23k
  static_assert(N > 0, "isUInt<0> doesn't make sense");
333
3.23k
  return X < (UINT64_C(1) << (N));
334
3.23k
}
std::__1::enable_if<(4u) < (64), bool>::type llvm::isUInt<4u>(unsigned long long)
Line
Count
Source
331
6.93k
isUInt(uint64_t X) {
332
6.93k
  static_assert(N > 0, "isUInt<0> doesn't make sense");
333
6.93k
  return X < (UINT64_C(1) << (N));
334
6.93k
}
std::__1::enable_if<(9u) < (64), bool>::type llvm::isUInt<9u>(unsigned long long)
Line
Count
Source
331
14.7k
isUInt(uint64_t X) {
332
14.7k
  static_assert(N > 0, "isUInt<0> doesn't make sense");
333
14.7k
  return X < (UINT64_C(1) << (N));
334
14.7k
}
std::__1::enable_if<(10u) < (64), bool>::type llvm::isUInt<10u>(unsigned long long)
Line
Count
Source
331
528
isUInt(uint64_t X) {
332
528
  static_assert(N > 0, "isUInt<0> doesn't make sense");
333
528
  return X < (UINT64_C(1) << (N));
334
528
}
std::__1::enable_if<(7u) < (64), bool>::type llvm::isUInt<7u>(unsigned long long)
Line
Count
Source
331
3.31k
isUInt(uint64_t X) {
332
3.31k
  static_assert(N > 0, "isUInt<0> doesn't make sense");
333
3.31k
  return X < (UINT64_C(1) << (N));
334
3.31k
}
std::__1::enable_if<(3u) < (64), bool>::type llvm::isUInt<3u>(unsigned long long)
Line
Count
Source
331
3.33k
isUInt(uint64_t X) {
332
3.33k
  static_assert(N > 0, "isUInt<0> doesn't make sense");
333
3.33k
  return X < (UINT64_C(1) << (N));
334
3.33k
}
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
}
std::__1::enable_if<(11u) < (64), bool>::type llvm::isUInt<11u>(unsigned long long)
Line
Count
Source
331
492
isUInt(uint64_t X) {
332
492
  static_assert(N > 0, "isUInt<0> doesn't make sense");
333
492
  return X < (UINT64_C(1) << (N));
334
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
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
141k
template <> constexpr inline bool isUInt<8>(uint64_t x) {
343
141k
  return static_cast<uint8_t>(x) == x;
344
141k
}
345
5.61M
template <> constexpr inline bool isUInt<16>(uint64_t x) {
346
5.61M
  return static_cast<uint16_t>(x) == x;
347
5.61M
}
348
167k
template <> constexpr inline bool isUInt<32>(uint64_t x) {
349
167k
  return static_cast<uint32_t>(x) == x;
350
167k
}
351
352
/// Checks if a unsigned integer is an N bit number shifted left by S.
353
template <unsigned N, unsigned S>
354
13.8k
constexpr inline bool isShiftedUInt(uint64_t x) {
355
13.8k
  static_assert(
356
13.8k
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
357
13.8k
  static_assert(N + S <= 64,
358
13.8k
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
359
13.8k
  // Per the two static_asserts above, S must be strictly less than 64.  So
360
13.8k
  // 1 << S is not undefined behavior.
361
13.8k
  return isUInt<N + S>(x) && 
(x % (UINT64_C(1) << S) == 0)11.7k
;
362
13.8k
}
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<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
1.97k
constexpr inline bool isShiftedUInt(uint64_t x) {
355
1.97k
  static_assert(
356
1.97k
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
357
1.97k
  static_assert(N + S <= 64,
358
1.97k
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
359
1.97k
  // Per the two static_asserts above, S must be strictly less than 64.  So
360
1.97k
  // 1 << S is not undefined behavior.
361
1.97k
  return isUInt<N + S>(x) && 
(x % (UINT64_C(1) << S) == 0)1.57k
;
362
1.97k
}
Unexecuted instantiation: bool llvm::isShiftedUInt<6u, 3u>(unsigned long long)
bool llvm::isShiftedUInt<5u, 2u>(unsigned long long)
Line
Count
Source
354
1.10k
constexpr inline bool isShiftedUInt(uint64_t x) {
355
1.10k
  static_assert(
356
1.10k
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
357
1.10k
  static_assert(N + S <= 64,
358
1.10k
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
359
1.10k
  // Per the two static_asserts above, S must be strictly less than 64.  So
360
1.10k
  // 1 << S is not undefined behavior.
361
1.10k
  return isUInt<N + S>(x) && 
(x % (UINT64_C(1) << S) == 0)870
;
362
1.10k
}
bool llvm::isShiftedUInt<4u, 2u>(unsigned long long)
Line
Count
Source
354
1.41k
constexpr inline bool isShiftedUInt(uint64_t x) {
355
1.41k
  static_assert(
356
1.41k
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
357
1.41k
  static_assert(N + S <= 64,
358
1.41k
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
359
1.41k
  // Per the two static_asserts above, S must be strictly less than 64.  So
360
1.41k
  // 1 << S is not undefined behavior.
361
1.41k
  return isUInt<N + S>(x) && 
(x % (UINT64_C(1) << S) == 0)1.28k
;
362
1.41k
}
bool llvm::isShiftedUInt<3u, 1u>(unsigned long long)
Line
Count
Source
354
387
constexpr inline bool isShiftedUInt(uint64_t x) {
355
387
  static_assert(
356
387
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
357
387
  static_assert(N + S <= 64,
358
387
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
359
387
  // Per the two static_asserts above, S must be strictly less than 64.  So
360
387
  // 1 << S is not undefined behavior.
361
387
  return isUInt<N + S>(x) && 
(x % (UINT64_C(1) << S) == 0)313
;
362
387
}
bool llvm::isShiftedUInt<5u, 3u>(unsigned long long)
Line
Count
Source
354
2.15k
constexpr inline bool isShiftedUInt(uint64_t x) {
355
2.15k
  static_assert(
356
2.15k
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
357
2.15k
  static_assert(N + S <= 64,
358
2.15k
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
359
2.15k
  // Per the two static_asserts above, S must be strictly less than 64.  So
360
2.15k
  // 1 << S is not undefined behavior.
361
2.15k
  return isUInt<N + S>(x) && 
(x % (UINT64_C(1) << S) == 0)2.03k
;
362
2.15k
}
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.33k
constexpr inline bool isShiftedUInt(uint64_t x) {
355
1.33k
  static_assert(
356
1.33k
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
357
1.33k
  static_assert(N + S <= 64,
358
1.33k
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
359
1.33k
  // Per the two static_asserts above, S must be strictly less than 64.  So
360
1.33k
  // 1 << S is not undefined behavior.
361
1.33k
  return isUInt<N + S>(x) && 
(x % (UINT64_C(1) << S) == 0)1.16k
;
362
1.33k
}
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
239
constexpr inline bool isShiftedUInt(uint64_t x) {
355
239
  static_assert(
356
239
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
357
239
  static_assert(N + S <= 64,
358
239
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
359
239
  // Per the two static_asserts above, S must be strictly less than 64.  So
360
239
  // 1 << S is not undefined behavior.
361
239
  return isUInt<N + S>(x) && 
(x % (UINT64_C(1) << S) == 0)225
;
362
239
}
bool llvm::isShiftedUInt<32u, 0u>(unsigned long long)
Line
Count
Source
354
313
constexpr inline bool isShiftedUInt(uint64_t x) {
355
313
  static_assert(
356
313
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
357
313
  static_assert(N + S <= 64,
358
313
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
359
313
  // Per the two static_asserts above, S must be strictly less than 64.  So
360
313
  // 1 << S is not undefined behavior.
361
313
  return isUInt<N + S>(x) && 
(x % (UINT64_C(1) << S) == 0)307
;
362
313
}
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
51
constexpr inline bool isShiftedUInt(uint64_t x) {
355
51
  static_assert(
356
51
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
357
51
  static_assert(N + S <= 64,
358
51
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
359
51
  // Per the two static_asserts above, S must be strictly less than 64.  So
360
51
  // 1 << S is not undefined behavior.
361
51
  return isUInt<N + S>(x) && 
(x % (UINT64_C(1) << S) == 0)45
;
362
51
}
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
358
constexpr inline bool isShiftedUInt(uint64_t x) {
355
358
  static_assert(
356
358
      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
357
358
  static_assert(N + S <= 64,
358
358
                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
359
358
  // Per the two static_asserts above, S must be strictly less than 64.  So
360
358
  // 1 << S is not undefined behavior.
361
358
  return isUInt<N + S>(x) && 
(x % (UINT64_C(1) << S) == 0)314
;
362
358
}
363
364
/// Gets the maximum value for a N-bit unsigned integer.
365
221k
inline uint64_t maxUIntN(uint64_t N) {
366
221k
  assert(N > 0 && N <= 64 && "integer width out of range");
367
221k
368
221k
  // uint64_t(1) << 64 is undefined behavior, so we can't do
369
221k
  //   (uint64_t(1) << N) - 1
370
221k
  // without checking first that N != 64.  But this works and doesn't have a
371
221k
  // branch.
372
221k
  return UINT64_MAX >> (64 - N);
373
221k
}
374
375
/// Gets the minimum value for a N-bit signed integer.
376
1.23M
inline int64_t minIntN(int64_t N) {
377
1.23M
  assert(N > 0 && N <= 64 && "integer width out of range");
378
1.23M
379
1.23M
  return -(UINT64_C(1)<<(N-1));
380
1.23M
}
381
382
/// Gets the maximum value for a N-bit signed integer.
383
1.23M
inline int64_t maxIntN(int64_t N) {
384
1.23M
  assert(N > 0 && N <= 64 && "integer width out of range");
385
1.23M
386
1.23M
  // This relies on two's complement wraparound when N == 64, so we convert to
387
1.23M
  // int64_t only at the very end to avoid UB.
388
1.23M
  return (UINT64_C(1) << (N - 1)) - 1;
389
1.23M
}
390
391
/// Checks if an unsigned integer fits into the given (dynamic) bit width.
392
223k
inline bool isUIntN(unsigned N, uint64_t x) {
393
223k
  return N >= 64 || 
x <= maxUIntN(N)221k
;
394
223k
}
395
396
/// Checks if an signed integer fits into the given (dynamic) bit width.
397
2.32M
inline bool isIntN(unsigned N, int64_t x) {
398
2.32M
  return N >= 64 || 
(1.23M
minIntN(N) <= x1.23M
&&
x <= maxIntN(N)1.23M
);
399
2.32M
}
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.2k
constexpr inline bool isMask_32(uint32_t Value) {
405
13.2k
  return Value && 
((Value + 1) & Value) == 013.2k
;
406
13.2k
}
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
5.40M
constexpr inline bool isMask_64(uint64_t Value) {
411
5.40M
  return Value && 
((Value + 1) & Value) == 05.19M
;
412
5.40M
}
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.26k
constexpr inline bool isShiftedMask_32(uint32_t Value) {
417
7.26k
  return Value && isMask_32((Value - 1) | Value);
418
7.26k
}
419
420
/// Return true if the argument contains a non-empty sequence of ones with the
421
/// remainder zero (64 bit version.)
422
3.46M
constexpr inline bool isShiftedMask_64(uint64_t Value) {
423
3.46M
  return Value && 
isMask_64((Value - 1) | Value)3.46M
;
424
3.46M
}
425
426
/// Return true if the argument is a power of two > 0.
427
/// Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.)
428
17.2M
constexpr inline bool isPowerOf2_32(uint32_t Value) {
429
17.2M
  return Value && 
!(Value & (Value - 1))17.0M
;
430
17.2M
}
431
432
/// Return true if the argument is a power of two > 0 (64 bit edition.)
433
66.8M
constexpr inline bool isPowerOf2_64(uint64_t Value) {
434
66.8M
  return Value && 
!(Value & (Value - 1))66.7M
;
435
66.8M
}
436
437
/// Return a byte-swapped representation of the 16-bit argument.
438
8.05k
inline uint16_t ByteSwap_16(uint16_t Value) {
439
8.05k
  return sys::SwapByteOrder_16(Value);
440
8.05k
}
441
442
/// Return a byte-swapped representation of the 32-bit argument.
443
39.9k
inline uint32_t ByteSwap_32(uint32_t Value) {
444
39.9k
  return sys::SwapByteOrder_32(Value);
445
39.9k
}
446
447
/// Return a byte-swapped representation of the 64-bit argument.
448
5.70k
inline uint64_t ByteSwap_64(uint64_t Value) {
449
5.70k
  return sys::SwapByteOrder_64(Value);
450
5.70k
}
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
55.3M
std::size_t countLeadingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
462
55.3M
  static_assert(std::numeric_limits<T>::is_integer &&
463
55.3M
                    !std::numeric_limits<T>::is_signed,
464
55.3M
                "Only unsigned integral types are allowed.");
465
55.3M
  return countLeadingZeros<T>(~Value, ZB);
466
55.3M
}
unsigned long llvm::countLeadingOnes<unsigned long long>(unsigned long long, llvm::ZeroBehavior)
Line
Count
Source
461
55.3M
std::size_t countLeadingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
462
55.3M
  static_assert(std::numeric_limits<T>::is_integer &&
463
55.3M
                    !std::numeric_limits<T>::is_signed,
464
55.3M
                "Only unsigned integral types are allowed.");
465
55.3M
  return countLeadingZeros<T>(~Value, ZB);
466
55.3M
}
unsigned long llvm::countLeadingOnes<unsigned int>(unsigned int, llvm::ZeroBehavior)
Line
Count
Source
461
73
std::size_t 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
229M
std::size_t countTrailingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
478
229M
  static_assert(std::numeric_limits<T>::is_integer &&
479
229M
                    !std::numeric_limits<T>::is_signed,
480
229M
                "Only unsigned integral types are allowed.");
481
229M
  return countTrailingZeros<T>(~Value, ZB);
482
229M
}
unsigned long llvm::countTrailingOnes<unsigned long long>(unsigned long long, llvm::ZeroBehavior)
Line
Count
Source
477
229M
std::size_t countTrailingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
478
229M
  static_assert(std::numeric_limits<T>::is_integer &&
479
229M
                    !std::numeric_limits<T>::is_signed,
480
229M
                "Only unsigned integral types are allowed.");
481
229M
  return countTrailingZeros<T>(~Value, ZB);
482
229M
}
unsigned long llvm::countTrailingOnes<unsigned int>(unsigned int, llvm::ZeroBehavior)
Line
Count
Source
477
4.83k
std::size_t countTrailingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
478
4.83k
  static_assert(std::numeric_limits<T>::is_integer &&
479
4.83k
                    !std::numeric_limits<T>::is_signed,
480
4.83k
                "Only unsigned integral types are allowed.");
481
4.83k
  return countTrailingZeros<T>(~Value, ZB);
482
4.83k
}
483
484
namespace detail {
485
template <typename T, std::size_t SizeOfT> struct PopulationCounter {
486
1.70M
  static unsigned count(T Value) {
487
1.70M
    // Generic version, forward to 32 bits.
488
1.70M
    static_assert(SizeOfT <= 4, "Not implemented!");
489
1.70M
#if __GNUC__ >= 4
490
1.70M
    return __builtin_popcount(Value);
491
1.70M
#else
492
1.70M
    uint32_t v = Value;
493
1.70M
    v = v - ((v >> 1) & 0x55555555);
494
1.70M
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
495
1.70M
    return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
496
1.70M
#endif
497
1.70M
  }
llvm::detail::PopulationCounter<unsigned int, 4ul>::count(unsigned int)
Line
Count
Source
486
1.70M
  static unsigned count(T Value) {
487
1.70M
    // Generic version, forward to 32 bits.
488
1.70M
    static_assert(SizeOfT <= 4, "Not implemented!");
489
1.70M
#if __GNUC__ >= 4
490
1.70M
    return __builtin_popcount(Value);
491
1.70M
#else
492
1.70M
    uint32_t v = Value;
493
1.70M
    v = v - ((v >> 1) & 0x55555555);
494
1.70M
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
495
1.70M
    return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
496
1.70M
#endif
497
1.70M
  }
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
79
#else
492
79
    uint32_t v = Value;
493
79
    v = v - ((v >> 1) & 0x55555555);
494
79
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
495
79
    return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
496
79
#endif
497
79
  }
498
};
499
500
template <typename T> struct PopulationCounter<T, 8> {
501
215M
  static unsigned count(T Value) {
502
215M
#if __GNUC__ >= 4
503
215M
    return __builtin_popcountll(Value);
504
215M
#else
505
215M
    uint64_t v = Value;
506
215M
    v = v - ((v >> 1) & 0x5555555555555555ULL);
507
215M
    v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
508
215M
    v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
509
215M
    return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56);
510
215M
#endif
511
215M
  }
llvm::detail::PopulationCounter<unsigned long, 8ul>::count(unsigned long)
Line
Count
Source
501
11.3M
  static unsigned count(T Value) {
502
11.3M
#if __GNUC__ >= 4
503
11.3M
    return __builtin_popcountll(Value);
504
11.3M
#else
505
11.3M
    uint64_t v = Value;
506
11.3M
    v = v - ((v >> 1) & 0x5555555555555555ULL);
507
11.3M
    v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
508
11.3M
    v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
509
11.3M
    return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56);
510
11.3M
#endif
511
11.3M
  }
llvm::detail::PopulationCounter<unsigned long long, 8ul>::count(unsigned long long)
Line
Count
Source
501
204M
  static unsigned count(T Value) {
502
204M
#if __GNUC__ >= 4
503
204M
    return __builtin_popcountll(Value);
504
204M
#else
505
204M
    uint64_t v = Value;
506
204M
    v = v - ((v >> 1) & 0x5555555555555555ULL);
507
204M
    v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
508
204M
    v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
509
204M
    return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56);
510
204M
#endif
511
204M
  }
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
217M
inline unsigned countPopulation(T Value) {
520
217M
  static_assert(std::numeric_limits<T>::is_integer &&
521
217M
                    !std::numeric_limits<T>::is_signed,
522
217M
                "Only unsigned integral types are allowed.");
523
217M
  return detail::PopulationCounter<T, sizeof(T)>::count(Value);
524
217M
}
unsigned int llvm::countPopulation<unsigned long>(unsigned long)
Line
Count
Source
519
11.3M
inline unsigned countPopulation(T Value) {
520
11.3M
  static_assert(std::numeric_limits<T>::is_integer &&
521
11.3M
                    !std::numeric_limits<T>::is_signed,
522
11.3M
                "Only unsigned integral types are allowed.");
523
11.3M
  return detail::PopulationCounter<T, sizeof(T)>::count(Value);
524
11.3M
}
unsigned int llvm::countPopulation<unsigned long long>(unsigned long long)
Line
Count
Source
519
204M
inline unsigned countPopulation(T Value) {
520
204M
  static_assert(std::numeric_limits<T>::is_integer &&
521
204M
                    !std::numeric_limits<T>::is_signed,
522
204M
                "Only unsigned integral types are allowed.");
523
204M
  return detail::PopulationCounter<T, sizeof(T)>::count(Value);
524
204M
}
unsigned int llvm::countPopulation<unsigned int>(unsigned int)
Line
Count
Source
519
1.70M
inline unsigned countPopulation(T Value) {
520
1.70M
  static_assert(std::numeric_limits<T>::is_integer &&
521
1.70M
                    !std::numeric_limits<T>::is_signed,
522
1.70M
                "Only unsigned integral types are allowed.");
523
1.70M
  return detail::PopulationCounter<T, sizeof(T)>::count(Value);
524
1.70M
}
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
0
#if defined(__ANDROID_API__) && __ANDROID_API__ < 18
529
0
  return __builtin_log(Value) / __builtin_log(2.0);
530
0
#else
531
0
  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.0M
inline unsigned Log2_32(uint32_t Value) {
539
55.0M
  return 31 - countLeadingZeros(Value);
540
55.0M
}
541
542
/// Return the floor log base 2 of the specified value, -1 if the value is zero.
543
/// (64 bit edition.)
544
6.78M
inline unsigned Log2_64(uint64_t Value) {
545
6.78M
  return 63 - countLeadingZeros(Value);
546
6.78M
}
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
65.4M
inline unsigned Log2_32_Ceil(uint32_t Value) {
552
65.4M
  return 32 - countLeadingZeros(Value - 1);
553
65.4M
}
554
555
/// Return the ceil log base 2 of the specified value, 64 if the value is zero.
556
/// (64 bit edition.)
557
141M
inline unsigned Log2_64_Ceil(uint64_t Value) {
558
141M
  return 64 - countLeadingZeros(Value - 1);
559
141M
}
560
561
/// Return the greatest common divisor of the values using Euclid's algorithm.
562
261k
inline uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B) {
563
723k
  while (B) {
564
461k
    uint64_t T = B;
565
461k
    B = A % B;
566
461k
    A = T;
567
461k
  }
568
261k
  return A;
569
261k
}
570
571
/// This function takes a 64-bit integer and returns the bit equivalent double.
572
40.9k
inline double BitsToDouble(uint64_t Bits) {
573
40.9k
  double D;
574
40.9k
  static_assert(sizeof(uint64_t) == sizeof(double), "Unexpected type sizes");
575
40.9k
  memcpy(&D, &Bits, sizeof(Bits));
576
40.9k
  return D;
577
40.9k
}
578
579
/// This function takes a 32-bit integer and returns the bit equivalent float.
580
40.6k
inline float BitsToFloat(uint32_t Bits) {
581
40.6k
  float F;
582
40.6k
  static_assert(sizeof(uint32_t) == sizeof(float), "Unexpected type sizes");
583
40.6k
  memcpy(&F, &Bits, sizeof(Bits));
584
40.6k
  return F;
585
40.6k
}
586
587
/// This function takes a double and returns the bit equivalent 64-bit integer.
588
/// Note that copying doubles around changes the bits of NaNs on some hosts,
589
/// notably x86, so this routine cannot be used if these bits are needed.
590
6.34M
inline uint64_t DoubleToBits(double Double) {
591
6.34M
  uint64_t Bits;
592
6.34M
  static_assert(sizeof(uint64_t) == sizeof(double), "Unexpected type sizes");
593
6.34M
  memcpy(&Bits, &Double, sizeof(Double));
594
6.34M
  return Bits;
595
6.34M
}
596
597
/// This function takes a float and returns the bit equivalent 32-bit integer.
598
/// Note that copying floats around changes the bits of NaNs on some hosts,
599
/// notably x86, so this routine cannot be used if these bits are needed.
600
3.97M
inline uint32_t FloatToBits(float Float) {
601
3.97M
  uint32_t Bits;
602
3.97M
  static_assert(sizeof(uint32_t) == sizeof(float), "Unexpected type sizes");
603
3.97M
  memcpy(&Bits, &Float, sizeof(Float));
604
3.97M
  return Bits;
605
3.97M
}
606
607
/// A and B are either alignments or offsets. Return the minimum alignment that
608
/// may be assumed after adding the two together.
609
25.4M
constexpr inline uint64_t MinAlign(uint64_t A, uint64_t B) {
610
25.4M
  // The largest power of 2 that divides both A and B.
611
25.4M
  //
612
25.4M
  // Replace "-Value" by "1+~Value" in the following commented code to avoid
613
25.4M
  // MSVC warning C4146
614
25.4M
  //    return (A | B) & -(A | B);
615
25.4M
  return (A | B) & (1 + ~(A | B));
616
25.4M
}
617
618
/// Aligns \c Addr to \c Alignment bytes, rounding up.
619
///
620
/// Alignment should be a power of two.  This method rounds up, so
621
/// alignAddr(7, 4) == 8 and alignAddr(8, 4) == 8.
622
1.12G
inline uintptr_t alignAddr(const void *Addr, size_t Alignment) {
623
1.12G
  assert(Alignment && isPowerOf2_64((uint64_t)Alignment) &&
624
1.12G
         "Alignment is not a power of two!");
625
1.12G
626
1.12G
  assert((uintptr_t)Addr + Alignment - 1 >= (uintptr_t)Addr);
627
1.12G
628
1.12G
  return (((uintptr_t)Addr + Alignment - 1) & ~(uintptr_t)(Alignment - 1));
629
1.12G
}
630
631
/// Returns the necessary adjustment for aligning \c Ptr to \c Alignment
632
/// bytes, rounding up.
633
1.10G
inline size_t alignmentAdjustment(const void *Ptr, size_t Alignment) {
634
1.10G
  return alignAddr(Ptr, Alignment) - (uintptr_t)Ptr;
635
1.10G
}
636
637
/// Returns the next power of two (in 64-bits) that is strictly greater than A.
638
/// Returns zero on overflow.
639
407M
inline uint64_t NextPowerOf2(uint64_t A) {
640
407M
  A |= (A >> 1);
641
407M
  A |= (A >> 2);
642
407M
  A |= (A >> 4);
643
407M
  A |= (A >> 8);
644
407M
  A |= (A >> 16);
645
407M
  A |= (A >> 32);
646
407M
  return A + 1;
647
407M
}
648
649
/// Returns the power of two which is less than or equal to the given value.
650
/// Essentially, it is a floor operation across the domain of powers of two.
651
679k
inline uint64_t PowerOf2Floor(uint64_t A) {
652
679k
  if (!A) 
return 0617
;
653
679k
  return 1ull << (63 - countLeadingZeros(A, ZB_Undefined));
654
679k
}
655
656
/// Returns the power of two which is greater than or equal to the given value.
657
/// Essentially, it is a ceil operation across the domain of powers of two.
658
1.52M
inline uint64_t PowerOf2Ceil(uint64_t A) {
659
1.52M
  if (!A)
660
192
    return 0;
661
1.52M
  return NextPowerOf2(A - 1);
662
1.52M
}
663
664
/// Returns the next integer (mod 2**64) that is greater than or equal to
665
/// \p Value and is a multiple of \p Align. \p Align must be non-zero.
666
///
667
/// If non-zero \p Skew is specified, the return value will be a minimal
668
/// integer that is greater than or equal to \p Value and equal to
669
/// \p Align * N + \p Skew for some integer N. If \p Skew is larger than
670
/// \p Align, its value is adjusted to '\p Skew mod \p Align'.
671
///
672
/// Examples:
673
/// \code
674
///   alignTo(5, 8) = 8
675
///   alignTo(17, 8) = 24
676
///   alignTo(~0LL, 8) = 0
677
///   alignTo(321, 255) = 510
678
///
679
///   alignTo(5, 8, 7) = 7
680
///   alignTo(17, 8, 1) = 17
681
///   alignTo(~0LL, 8, 3) = 3
682
///   alignTo(321, 255, 42) = 552
683
/// \endcode
684
702M
inline uint64_t alignTo(uint64_t Value, uint64_t Align, uint64_t Skew = 0) {
685
702M
  assert(Align != 0u && "Align can't be 0.");
686
702M
  Skew %= Align;
687
702M
  return (Value + Align - 1 - Skew) / Align * Align + Skew;
688
702M
}
689
690
/// Returns the next integer (mod 2**64) that is greater than or equal to
691
/// \p Value and is a multiple of \c Align. \c Align must be non-zero.
692
7.65M
template <uint64_t Align> constexpr inline uint64_t alignTo(uint64_t Value) {
693
7.65M
  static_assert(Align != 0u, "Align must be non-zero");
694
7.65M
  return (Value + Align - 1) / Align * Align;
695
7.65M
}
unsigned long long llvm::alignTo<8ull>(unsigned long long)
Line
Count
Source
692
20.9k
template <uint64_t Align> constexpr inline uint64_t alignTo(uint64_t Value) {
693
20.9k
  static_assert(Align != 0u, "Align must be non-zero");
694
20.9k
  return (Value + Align - 1) / Align * Align;
695
20.9k
}
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
692
7.63M
template <uint64_t Align> constexpr inline uint64_t alignTo(uint64_t Value) {
693
7.63M
  static_assert(Align != 0u, "Align must be non-zero");
694
7.63M
  return (Value + Align - 1) / Align * Align;
695
7.63M
}
696
697
/// Returns the integer ceil(Numerator / Denominator).
698
219k
inline uint64_t divideCeil(uint64_t Numerator, uint64_t Denominator) {
699
219k
  return alignTo(Numerator, Denominator) / Denominator;
700
219k
}
701
702
/// \c alignTo for contexts where a constant expression is required.
703
/// \sa alignTo
704
///
705
/// \todo FIXME: remove when \c constexpr becomes really \c constexpr
706
template <uint64_t Align>
707
struct AlignTo {
708
  static_assert(Align != 0u, "Align must be non-zero");
709
  template <uint64_t Value>
710
  struct from_value {
711
    static const uint64_t value = (Value + Align - 1) / Align * Align;
712
  };
713
};
714
715
/// Returns the largest uint64_t less than or equal to \p Value and is
716
/// \p Skew mod \p Align. \p Align must be non-zero
717
688k
inline uint64_t alignDown(uint64_t Value, uint64_t Align, uint64_t Skew = 0) {
718
688k
  assert(Align != 0u && "Align can't be 0.");
719
688k
  Skew %= Align;
720
688k
  return (Value - Skew) / Align * Align + Skew;
721
688k
}
722
723
/// Returns the offset to the next integer (mod 2**64) that is greater than
724
/// or equal to \p Value and is a multiple of \p Align. \p Align must be
725
/// non-zero.
726
2.22M
inline uint64_t OffsetToAlignment(uint64_t Value, uint64_t Align) {
727
2.22M
  return alignTo(Value, Align) - Value;
728
2.22M
}
729
730
/// Sign-extend the number in the bottom B bits of X to a 32-bit integer.
731
/// Requires 0 < B <= 32.
732
3.17k
template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
733
3.17k
  static_assert(B > 0, "Bit width can't be 0.");
734
3.17k
  static_assert(B <= 32, "Bit width out of range.");
735
3.17k
  return int32_t(X << (32 - B)) >> (32 - B);
736
3.17k
}
int llvm::SignExtend32<13u>(unsigned int)
Line
Count
Source
732
1.79k
template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
733
1.79k
  static_assert(B > 0, "Bit width can't be 0.");
734
1.79k
  static_assert(B <= 32, "Bit width out of range.");
735
1.79k
  return int32_t(X << (32 - B)) >> (32 - B);
736
1.79k
}
int llvm::SignExtend32<5u>(unsigned int)
Line
Count
Source
732
335
template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
733
335
  static_assert(B > 0, "Bit width can't be 0.");
734
335
  static_assert(B <= 32, "Bit width out of range.");
735
335
  return int32_t(X << (32 - B)) >> (32 - B);
736
335
}
int llvm::SignExtend32<26u>(unsigned int)
Line
Count
Source
732
659
template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
733
659
  static_assert(B > 0, "Bit width can't be 0.");
734
659
  static_assert(B <= 32, "Bit width out of range.");
735
659
  return int32_t(X << (32 - B)) >> (32 - B);
736
659
}
int llvm::SignExtend32<32u>(unsigned int)
Line
Count
Source
732
383
template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
733
383
  static_assert(B > 0, "Bit width can't be 0.");
734
383
  static_assert(B <= 32, "Bit width out of range.");
735
383
  return int32_t(X << (32 - B)) >> (32 - B);
736
383
}
737
738
/// Sign-extend the number in the bottom B bits of X to a 32-bit integer.
739
/// Requires 0 < B < 32.
740
6.19k
inline int32_t SignExtend32(uint32_t X, unsigned B) {
741
6.19k
  assert(B > 0 && "Bit width can't be 0.");
742
6.19k
  assert(B <= 32 && "Bit width out of range.");
743
6.19k
  return int32_t(X << (32 - B)) >> (32 - B);
744
6.19k
}
745
746
/// Sign-extend the number in the bottom B bits of X to a 64-bit integer.
747
/// Requires 0 < B < 64.
748
9.90k
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
749
9.90k
  static_assert(B > 0, "Bit width can't be 0.");
750
9.90k
  static_assert(B <= 64, "Bit width out of range.");
751
9.90k
  return int64_t(x << (64 - B)) >> (64 - B);
752
9.90k
}
long long llvm::SignExtend64<16u>(unsigned long long)
Line
Count
Source
748
4.82k
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
749
4.82k
  static_assert(B > 0, "Bit width can't be 0.");
750
4.82k
  static_assert(B <= 64, "Bit width out of range.");
751
4.82k
  return int64_t(x << (64 - B)) >> (64 - B);
752
4.82k
}
long long llvm::SignExtend64<32u>(unsigned long long)
Line
Count
Source
748
4.79k
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
749
4.79k
  static_assert(B > 0, "Bit width can't be 0.");
750
4.79k
  static_assert(B <= 64, "Bit width out of range.");
751
4.79k
  return int64_t(x << (64 - B)) >> (64 - B);
752
4.79k
}
long long llvm::SignExtend64<4u>(unsigned long long)
Line
Count
Source
748
115
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
749
115
  static_assert(B > 0, "Bit width can't be 0.");
750
115
  static_assert(B <= 64, "Bit width out of range.");
751
115
  return int64_t(x << (64 - B)) >> (64 - B);
752
115
}
long long llvm::SignExtend64<5u>(unsigned long long)
Line
Count
Source
748
95
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
749
95
  static_assert(B > 0, "Bit width can't be 0.");
750
95
  static_assert(B <= 64, "Bit width out of range.");
751
95
  return int64_t(x << (64 - B)) >> (64 - B);
752
95
}
long long llvm::SignExtend64<10u>(unsigned long long)
Line
Count
Source
748
12
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
749
12
  static_assert(B > 0, "Bit width can't be 0.");
750
12
  static_assert(B <= 64, "Bit width out of range.");
751
12
  return int64_t(x << (64 - B)) >> (64 - B);
752
12
}
long long llvm::SignExtend64<6u>(unsigned long long)
Line
Count
Source
748
69
template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
749
69
  static_assert(B > 0, "Bit width can't be 0.");
750
69
  static_assert(B <= 64, "Bit width out of range.");
751
69
  return int64_t(x << (64 - B)) >> (64 - B);
752
69
}
753
754
/// Sign-extend the number in the bottom B bits of X to a 64-bit integer.
755
/// Requires 0 < B < 64.
756
701M
inline int64_t SignExtend64(uint64_t X, unsigned B) {
757
701M
  assert(B > 0 && "Bit width can't be 0.");
758
701M
  assert(B <= 64 && "Bit width out of range.");
759
701M
  return int64_t(X << (64 - B)) >> (64 - B);
760
701M
}
761
762
/// Subtract two unsigned integers, X and Y, of type T and return the absolute
763
/// value of the result.
764
template <typename T>
765
typename std::enable_if<std::is_unsigned<T>::value, T>::type
766
259
AbsoluteDifference(T X, T Y) {
767
259
  return std::max(X, Y) - std::min(X, Y);
768
259
}
769
770
/// Add two unsigned integers, X and Y, of type T.  Clamp the result to the
771
/// maximum representable value of T on overflow.  ResultOverflowed indicates if
772
/// the result is larger than the maximum representable value of type T.
773
template <typename T>
774
typename std::enable_if<std::is_unsigned<T>::value, T>::type
775
645k
SaturatingAdd(T X, T Y, bool *ResultOverflowed = nullptr) {
776
645k
  bool Dummy;
777
645k
  bool &Overflowed = ResultOverflowed ? 
*ResultOverflowed2.85k
:
Dummy642k
;
778
645k
  // Hacker's Delight, p. 29
779
645k
  T Z = X + Y;
780
645k
  Overflowed = (Z < X || 
Z < Y645k
);
781
645k
  if (Overflowed)
782
25
    return std::numeric_limits<T>::max();
783
645k
  else
784
645k
    return Z;
785
645k
}
786
787
/// Multiply two unsigned integers, X and Y, of type T.  Clamp the result to the
788
/// maximum representable value of T on overflow.  ResultOverflowed indicates if
789
/// the result is larger than the maximum representable value of type T.
790
template <typename T>
791
typename std::enable_if<std::is_unsigned<T>::value, T>::type
792
3.21k
SaturatingMultiply(T X, T Y, bool *ResultOverflowed = nullptr) {
793
3.21k
  bool Dummy;
794
3.21k
  bool &Overflowed = ResultOverflowed ? 
*ResultOverflowed3.01k
:
Dummy199
;
795
3.21k
796
3.21k
  // Hacker's Delight, p. 30 has a different algorithm, but we don't use that
797
3.21k
  // because it fails for uint16_t (where multiplication can have undefined
798
3.21k
  // behavior due to promotion to int), and requires a division in addition
799
3.21k
  // to the multiplication.
800
3.21k
801
3.21k
  Overflowed = false;
802
3.21k
803
3.21k
  // Log2(Z) would be either Log2Z or Log2Z + 1.
804
3.21k
  // Special case: if X or Y is 0, Log2_64 gives -1, and Log2Z
805
3.21k
  // will necessarily be less than Log2Max as desired.
806
3.21k
  int Log2Z = Log2_64(X) + Log2_64(Y);
807
3.21k
  const T Max = std::numeric_limits<T>::max();
808
3.21k
  int Log2Max = Log2_64(Max);
809
3.21k
  if (Log2Z < Log2Max) {
810
2.88k
    return X * Y;
811
2.88k
  }
812
326
  if (Log2Z > Log2Max) {
813
12
    Overflowed = true;
814
12
    return Max;
815
12
  }
816
314
817
314
  // We're going to use the top bit, and maybe overflow one
818
314
  // bit past it. Multiply all but the bottom bit then add
819
314
  // that on at the end.
820
314
  T Z = (X >> 1) * Y;
821
314
  if (Z & ~(Max >> 1)) {
822
62
    Overflowed = true;
823
62
    return Max;
824
62
  }
825
252
  Z <<= 1;
826
252
  if (X & 1)
827
250
    return SaturatingAdd(Z, Y, ResultOverflowed);
828
2
829
2
  return Z;
830
2
}
831
832
/// Multiply two unsigned integers, X and Y, and add the unsigned integer, A to
833
/// the product. Clamp the result to the maximum representable value of T on
834
/// overflow. ResultOverflowed indicates if the result is larger than the
835
/// maximum representable value of type T.
836
template <typename T>
837
typename std::enable_if<std::is_unsigned<T>::value, T>::type
838
2.70k
SaturatingMultiplyAdd(T X, T Y, T A, bool *ResultOverflowed = nullptr) {
839
2.70k
  bool Dummy;
840
2.70k
  bool &Overflowed = ResultOverflowed ? 
*ResultOverflowed2.68k
:
Dummy21
;
841
2.70k
842
2.70k
  T Product = SaturatingMultiply(X, Y, &Overflowed);
843
2.70k
  if (Overflowed)
844
6
    return Product;
845
2.69k
846
2.69k
  return SaturatingAdd(A, Product, &Overflowed);
847
2.69k
}
848
849
/// Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
850
extern const float huge_valf;
851
} // End llvm namespace
852
853
#endif