LLVM  16.0.0git
DenseMapInfo.h
Go to the documentation of this file.
1 //===- llvm/ADT/DenseMapInfo.h - Type traits for DenseMap -------*- 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 /// \file
10 /// This file defines DenseMapInfo traits for DenseMap.
11 ///
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_ADT_DENSEMAPINFO_H
15 #define LLVM_ADT_DENSEMAPINFO_H
16 
17 #include <cassert>
18 #include <cstddef>
19 #include <cstdint>
20 #include <tuple>
21 #include <type_traits>
22 #include <utility>
23 #include <variant>
24 
25 namespace llvm {
26 
27 namespace detail {
28 
29 /// Simplistic combination of 32-bit hash values into 32-bit hash values.
30 static inline unsigned combineHashValue(unsigned a, unsigned b) {
31  uint64_t key = (uint64_t)a << 32 | (uint64_t)b;
32  key += ~(key << 32);
33  key ^= (key >> 22);
34  key += ~(key << 13);
35  key ^= (key >> 8);
36  key += (key << 3);
37  key ^= (key >> 15);
38  key += ~(key << 27);
39  key ^= (key >> 31);
40  return (unsigned)key;
41 }
42 
43 } // end namespace detail
44 
45 /// An information struct used to provide DenseMap with the various necessary
46 /// components for a given value type `T`. `Enable` is an optional additional
47 /// parameter that is used to support SFINAE (generally using std::enable_if_t)
48 /// in derived DenseMapInfo specializations; in non-SFINAE use cases this should
49 /// just be `void`.
50 template<typename T, typename Enable = void>
51 struct DenseMapInfo {
52  //static inline T getEmptyKey();
53  //static inline T getTombstoneKey();
54  //static unsigned getHashValue(const T &Val);
55  //static bool isEqual(const T &LHS, const T &RHS);
56 };
57 
58 // Provide DenseMapInfo for all pointers. Come up with sentinel pointer values
59 // that are aligned to alignof(T) bytes, but try to avoid requiring T to be
60 // complete. This allows clients to instantiate DenseMap<T*, ...> with forward
61 // declared key types. Assume that no pointer key type requires more than 4096
62 // bytes of alignment.
63 template<typename T>
64 struct DenseMapInfo<T*> {
65  // The following should hold, but it would require T to be complete:
66  // static_assert(alignof(T) <= (1 << Log2MaxAlign),
67  // "DenseMap does not support pointer keys requiring more than "
68  // "Log2MaxAlign bits of alignment");
69  static constexpr uintptr_t Log2MaxAlign = 12;
70 
71  static inline T* getEmptyKey() {
72  uintptr_t Val = static_cast<uintptr_t>(-1);
73  Val <<= Log2MaxAlign;
74  return reinterpret_cast<T*>(Val);
75  }
76 
77  static inline T* getTombstoneKey() {
78  uintptr_t Val = static_cast<uintptr_t>(-2);
79  Val <<= Log2MaxAlign;
80  return reinterpret_cast<T*>(Val);
81  }
82 
83  static unsigned getHashValue(const T *PtrVal) {
84  return (unsigned((uintptr_t)PtrVal) >> 4) ^
85  (unsigned((uintptr_t)PtrVal) >> 9);
86  }
87 
88  static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; }
89 };
90 
91 // Provide DenseMapInfo for chars.
92 template<> struct DenseMapInfo<char> {
93  static inline char getEmptyKey() { return ~0; }
94  static inline char getTombstoneKey() { return ~0 - 1; }
95  static unsigned getHashValue(const char& Val) { return Val * 37U; }
96 
97  static bool isEqual(const char &LHS, const char &RHS) {
98  return LHS == RHS;
99  }
100 };
101 
102 // Provide DenseMapInfo for unsigned chars.
103 template <> struct DenseMapInfo<unsigned char> {
104  static inline unsigned char getEmptyKey() { return ~0; }
105  static inline unsigned char getTombstoneKey() { return ~0 - 1; }
106  static unsigned getHashValue(const unsigned char &Val) { return Val * 37U; }
107 
108  static bool isEqual(const unsigned char &LHS, const unsigned char &RHS) {
109  return LHS == RHS;
110  }
111 };
112 
113 // Provide DenseMapInfo for unsigned shorts.
114 template <> struct DenseMapInfo<unsigned short> {
115  static inline unsigned short getEmptyKey() { return 0xFFFF; }
116  static inline unsigned short getTombstoneKey() { return 0xFFFF - 1; }
117  static unsigned getHashValue(const unsigned short &Val) { return Val * 37U; }
118 
119  static bool isEqual(const unsigned short &LHS, const unsigned short &RHS) {
120  return LHS == RHS;
121  }
122 };
123 
124 // Provide DenseMapInfo for unsigned ints.
125 template<> struct DenseMapInfo<unsigned> {
126  static inline unsigned getEmptyKey() { return ~0U; }
127  static inline unsigned getTombstoneKey() { return ~0U - 1; }
128  static unsigned getHashValue(const unsigned& Val) { return Val * 37U; }
129 
130  static bool isEqual(const unsigned& LHS, const unsigned& RHS) {
131  return LHS == RHS;
132  }
133 };
134 
135 // Provide DenseMapInfo for unsigned longs.
136 template<> struct DenseMapInfo<unsigned long> {
137  static inline unsigned long getEmptyKey() { return ~0UL; }
138  static inline unsigned long getTombstoneKey() { return ~0UL - 1L; }
139 
140  static unsigned getHashValue(const unsigned long& Val) {
141  return (unsigned)(Val * 37UL);
142  }
143 
144  static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) {
145  return LHS == RHS;
146  }
147 };
148 
149 // Provide DenseMapInfo for unsigned long longs.
150 template<> struct DenseMapInfo<unsigned long long> {
151  static inline unsigned long long getEmptyKey() { return ~0ULL; }
152  static inline unsigned long long getTombstoneKey() { return ~0ULL - 1ULL; }
153 
154  static unsigned getHashValue(const unsigned long long& Val) {
155  return (unsigned)(Val * 37ULL);
156  }
157 
158  static bool isEqual(const unsigned long long& LHS,
159  const unsigned long long& RHS) {
160  return LHS == RHS;
161  }
162 };
163 
164 // Provide DenseMapInfo for shorts.
165 template <> struct DenseMapInfo<short> {
166  static inline short getEmptyKey() { return 0x7FFF; }
167  static inline short getTombstoneKey() { return -0x7FFF - 1; }
168  static unsigned getHashValue(const short &Val) { return Val * 37U; }
169  static bool isEqual(const short &LHS, const short &RHS) { return LHS == RHS; }
170 };
171 
172 // Provide DenseMapInfo for ints.
173 template<> struct DenseMapInfo<int> {
174  static inline int getEmptyKey() { return 0x7fffffff; }
175  static inline int getTombstoneKey() { return -0x7fffffff - 1; }
176  static unsigned getHashValue(const int& Val) { return (unsigned)(Val * 37U); }
177 
178  static bool isEqual(const int& LHS, const int& RHS) {
179  return LHS == RHS;
180  }
181 };
182 
183 // Provide DenseMapInfo for longs.
184 template<> struct DenseMapInfo<long> {
185  static inline long getEmptyKey() {
186  return (1UL << (sizeof(long) * 8 - 1)) - 1UL;
187  }
188 
189  static inline long getTombstoneKey() { return getEmptyKey() - 1L; }
190 
191  static unsigned getHashValue(const long& Val) {
192  return (unsigned)(Val * 37UL);
193  }
194 
195  static bool isEqual(const long& LHS, const long& RHS) {
196  return LHS == RHS;
197  }
198 };
199 
200 // Provide DenseMapInfo for long longs.
201 template<> struct DenseMapInfo<long long> {
202  static inline long long getEmptyKey() { return 0x7fffffffffffffffLL; }
203  static inline long long getTombstoneKey() { return -0x7fffffffffffffffLL-1; }
204 
205  static unsigned getHashValue(const long long& Val) {
206  return (unsigned)(Val * 37ULL);
207  }
208 
209  static bool isEqual(const long long& LHS,
210  const long long& RHS) {
211  return LHS == RHS;
212  }
213 };
214 
215 // Provide DenseMapInfo for all pairs whose members have info.
216 template<typename T, typename U>
217 struct DenseMapInfo<std::pair<T, U>> {
218  using Pair = std::pair<T, U>;
221 
222  static inline Pair getEmptyKey() {
223  return std::make_pair(FirstInfo::getEmptyKey(),
224  SecondInfo::getEmptyKey());
225  }
226 
227  static inline Pair getTombstoneKey() {
228  return std::make_pair(FirstInfo::getTombstoneKey(),
229  SecondInfo::getTombstoneKey());
230  }
231 
232  static unsigned getHashValue(const Pair& PairVal) {
233  return detail::combineHashValue(FirstInfo::getHashValue(PairVal.first),
234  SecondInfo::getHashValue(PairVal.second));
235  }
236 
237  static bool isEqual(const Pair &LHS, const Pair &RHS) {
238  return FirstInfo::isEqual(LHS.first, RHS.first) &&
239  SecondInfo::isEqual(LHS.second, RHS.second);
240  }
241 };
242 
243 // Provide DenseMapInfo for all tuples whose members have info.
244 template <typename... Ts> struct DenseMapInfo<std::tuple<Ts...>> {
245  using Tuple = std::tuple<Ts...>;
246 
247  static inline Tuple getEmptyKey() {
249  }
250 
251  static inline Tuple getTombstoneKey() {
253  }
254 
255  template <unsigned I>
256  static unsigned getHashValueImpl(const Tuple &values, std::false_type) {
257  using EltType = std::tuple_element_t<I, Tuple>;
258  std::integral_constant<bool, I + 1 == sizeof...(Ts)> atEnd;
261  getHashValueImpl<I + 1>(values, atEnd));
262  }
263 
264  template <unsigned I>
265  static unsigned getHashValueImpl(const Tuple &, std::true_type) {
266  return 0;
267  }
268 
269  static unsigned getHashValue(const std::tuple<Ts...> &values) {
270  std::integral_constant<bool, 0 == sizeof...(Ts)> atEnd;
271  return getHashValueImpl<0>(values, atEnd);
272  }
273 
274  template <unsigned I>
275  static bool isEqualImpl(const Tuple &lhs, const Tuple &rhs, std::false_type) {
276  using EltType = std::tuple_element_t<I, Tuple>;
277  std::integral_constant<bool, I + 1 == sizeof...(Ts)> atEnd;
278  return DenseMapInfo<EltType>::isEqual(std::get<I>(lhs), std::get<I>(rhs)) &&
279  isEqualImpl<I + 1>(lhs, rhs, atEnd);
280  }
281 
282  template <unsigned I>
283  static bool isEqualImpl(const Tuple &, const Tuple &, std::true_type) {
284  return true;
285  }
286 
287  static bool isEqual(const Tuple &lhs, const Tuple &rhs) {
288  std::integral_constant<bool, 0 == sizeof...(Ts)> atEnd;
289  return isEqualImpl<0>(lhs, rhs, atEnd);
290  }
291 };
292 
293 // Provide DenseMapInfo for variants whose all alternatives have DenseMapInfo.
294 template <typename... Ts> struct DenseMapInfo<std::variant<Ts...>> {
295  using Variant = std::variant<Ts...>;
296  using FirstT = std::variant_alternative_t<0, Variant>;
297 
298  static inline Variant getEmptyKey() {
299  return Variant(std::in_place_index<0>, DenseMapInfo<FirstT>::getEmptyKey());
300  }
301 
302  static inline Variant getTombstoneKey() {
303  return Variant(std::in_place_index<0>,
305  }
306 
307  static unsigned getHashValue(const Variant &Val) {
308  return std::visit(
309  [&Val](auto &&Alternative) {
310  using T = std::decay_t<decltype(Alternative)>;
311  // Include index in hash to make sure same value as different
312  // alternatives don't collide.
315  DenseMapInfo<T>::getHashValue(Alternative));
316  },
317  Val);
318  }
319 
320  static bool isEqual(const Variant &LHS, const Variant &RHS) {
321  return LHS == RHS;
322  }
323 };
324 } // end namespace llvm
325 
326 #endif // LLVM_ADT_DENSEMAPINFO_H
llvm::DenseMapInfo< unsigned short >::getTombstoneKey
static unsigned short getTombstoneKey()
Definition: DenseMapInfo.h:116
llvm::DenseMapInfo< short >::getEmptyKey
static short getEmptyKey()
Definition: DenseMapInfo.h:166
llvm::DenseMapInfo< T * >::getTombstoneKey
static T * getTombstoneKey()
Definition: DenseMapInfo.h:77
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::DenseMapInfo< std::tuple< Ts... > >::isEqualImpl
static bool isEqualImpl(const Tuple &lhs, const Tuple &rhs, std::false_type)
Definition: DenseMapInfo.h:275
llvm::DenseMapInfo< long long >::getEmptyKey
static long long getEmptyKey()
Definition: DenseMapInfo.h:202
llvm::DenseMapInfo< long >::getEmptyKey
static long getEmptyKey()
Definition: DenseMapInfo.h:185
llvm::DenseMapInfo< char >::getEmptyKey
static char getEmptyKey()
Definition: DenseMapInfo.h:93
llvm::DenseMapInfo< unsigned long long >::getHashValue
static unsigned getHashValue(const unsigned long long &Val)
Definition: DenseMapInfo.h:154
llvm::DenseMapInfo< std::tuple< Ts... > >::getTombstoneKey
static Tuple getTombstoneKey()
Definition: DenseMapInfo.h:251
llvm::DenseMapInfo< unsigned long >::getTombstoneKey
static unsigned long getTombstoneKey()
Definition: DenseMapInfo.h:138
llvm::DenseMapInfo< T * >::getHashValue
static unsigned getHashValue(const T *PtrVal)
Definition: DenseMapInfo.h:83
llvm::DenseMapInfo< long >::getHashValue
static unsigned getHashValue(const long &Val)
Definition: DenseMapInfo.h:191
llvm::DenseMapInfo< char >::isEqual
static bool isEqual(const char &LHS, const char &RHS)
Definition: DenseMapInfo.h:97
T
#define T
Definition: Mips16ISelLowering.cpp:341
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::DenseMapInfo< unsigned short >::isEqual
static bool isEqual(const unsigned short &LHS, const unsigned short &RHS)
Definition: DenseMapInfo.h:119
llvm::DenseMapInfo< std::variant< Ts... > >::isEqual
static bool isEqual(const Variant &LHS, const Variant &RHS)
Definition: DenseMapInfo.h:320
llvm::DenseMapInfo< unsigned long long >::isEqual
static bool isEqual(const unsigned long long &LHS, const unsigned long long &RHS)
Definition: DenseMapInfo.h:158
llvm::DenseMapInfo< long long >::isEqual
static bool isEqual(const long long &LHS, const long long &RHS)
Definition: DenseMapInfo.h:209
a
=0.0 ? 0.0 :(a > 0.0 ? 1.0 :-1.0) a
Definition: README.txt:489
llvm::DenseMapInfo< char >::getTombstoneKey
static char getTombstoneKey()
Definition: DenseMapInfo.h:94
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
llvm::DenseMapInfo
An information struct used to provide DenseMap with the various necessary components for a given valu...
Definition: APInt.h:34
llvm::DenseMapInfo< std::variant< Ts... > >::getEmptyKey
static Variant getEmptyKey()
Definition: DenseMapInfo.h:298
llvm::DenseMapInfo< unsigned >::isEqual
static bool isEqual(const unsigned &LHS, const unsigned &RHS)
Definition: DenseMapInfo.h:130
llvm::DenseMapInfo< long long >::getHashValue
static unsigned getHashValue(const long long &Val)
Definition: DenseMapInfo.h:205
llvm::DenseMapInfo< std::variant< Ts... > >::FirstT
std::variant_alternative_t< 0, Variant > FirstT
Definition: DenseMapInfo.h:296
llvm::DenseMapInfo< unsigned char >::isEqual
static bool isEqual(const unsigned char &LHS, const unsigned char &RHS)
Definition: DenseMapInfo.h:108
llvm::DenseMapInfo< int >::getHashValue
static unsigned getHashValue(const int &Val)
Definition: DenseMapInfo.h:176
llvm::DenseMapInfo< std::tuple< Ts... > >::Tuple
std::tuple< Ts... > Tuple
Definition: DenseMapInfo.h:245
llvm::DenseMapInfo< unsigned long >::getHashValue
static unsigned getHashValue(const unsigned long &Val)
Definition: DenseMapInfo.h:140
llvm::DenseMapInfo< unsigned short >::getEmptyKey
static unsigned short getEmptyKey()
Definition: DenseMapInfo.h:115
int
Clang compiles this i1 i64 store i64 i64 store i64 i64 store i64 i64 store i64 align Which gets codegen d xmm0 movaps rbp movaps rbp movaps rbp movaps rbp rbp rbp rbp rbp It would be better to have movq s of instead of the movaps s LLVM produces ret int
Definition: README.txt:536
llvm::DenseMapInfo< unsigned long long >::getEmptyKey
static unsigned long long getEmptyKey()
Definition: DenseMapInfo.h:151
b
the resulting code requires compare and branches when and if the revised code is with conditional branches instead of More there is a byte word extend before each where there should be only and the condition codes are not remembered when the same two values are compared twice More LSR enhancements i8 and i32 load store addressing modes are identical int b
Definition: README.txt:418
llvm::DenseMapInfo< std::variant< Ts... > >::getTombstoneKey
static Variant getTombstoneKey()
Definition: DenseMapInfo.h:302
llvm::DenseMapInfo< unsigned short >::getHashValue
static unsigned getHashValue(const unsigned short &Val)
Definition: DenseMapInfo.h:117
llvm::DenseMapInfo< std::tuple< Ts... > >::isEqualImpl
static bool isEqualImpl(const Tuple &, const Tuple &, std::true_type)
Definition: DenseMapInfo.h:283
llvm::DenseMapInfo< int >::getTombstoneKey
static int getTombstoneKey()
Definition: DenseMapInfo.h:175
llvm::DenseMapInfo< T * >::getEmptyKey
static T * getEmptyKey()
Definition: DenseMapInfo.h:71
llvm::DenseMapInfo< std::pair< T, U > >::getHashValue
static unsigned getHashValue(const Pair &PairVal)
Definition: DenseMapInfo.h:232
llvm::detail::combineHashValue
static unsigned combineHashValue(unsigned a, unsigned b)
Simplistic combination of 32-bit hash values into 32-bit hash values.
Definition: DenseMapInfo.h:30
llvm::DenseMapInfo< unsigned long >::getEmptyKey
static unsigned long getEmptyKey()
Definition: DenseMapInfo.h:137
llvm::DenseMapInfo< long >::getTombstoneKey
static long getTombstoneKey()
Definition: DenseMapInfo.h:189
llvm::DenseMapInfo< unsigned >::getHashValue
static unsigned getHashValue(const unsigned &Val)
Definition: DenseMapInfo.h:128
llvm::cl::values
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
Definition: CommandLine.h:705
llvm::DenseMapInfo< std::tuple< Ts... > >::getHashValue
static unsigned getHashValue(const std::tuple< Ts... > &values)
Definition: DenseMapInfo.h:269
uint64_t
llvm::DenseMapInfo< T * >::isEqual
static bool isEqual(const T *LHS, const T *RHS)
Definition: DenseMapInfo.h:88
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::DenseMapInfo< long >::isEqual
static bool isEqual(const long &LHS, const long &RHS)
Definition: DenseMapInfo.h:195
llvm::DenseMapInfo< unsigned >::getEmptyKey
static unsigned getEmptyKey()
Definition: DenseMapInfo.h:126
llvm::DenseMapInfo< short >::getTombstoneKey
static short getTombstoneKey()
Definition: DenseMapInfo.h:167
llvm::DenseMapInfo< std::tuple< Ts... > >::getEmptyKey
static Tuple getEmptyKey()
Definition: DenseMapInfo.h:247
llvm::DenseMapInfo< std::pair< T, U > >::isEqual
static bool isEqual(const Pair &LHS, const Pair &RHS)
Definition: DenseMapInfo.h:237
llvm::DenseMapInfo< std::pair< T, U > >::Pair
std::pair< T, U > Pair
Definition: DenseMapInfo.h:218
llvm::DenseMapInfo< int >::isEqual
static bool isEqual(const int &LHS, const int &RHS)
Definition: DenseMapInfo.h:178
llvm::DenseMapInfo< std::variant< Ts... > >::Variant
std::variant< Ts... > Variant
Definition: DenseMapInfo.h:295
llvm::DenseMapInfo< char >::getHashValue
static unsigned getHashValue(const char &Val)
Definition: DenseMapInfo.h:95
llvm::DenseMapInfo< unsigned char >::getEmptyKey
static unsigned char getEmptyKey()
Definition: DenseMapInfo.h:104
llvm::DenseMapInfo< unsigned char >::getTombstoneKey
static unsigned char getTombstoneKey()
Definition: DenseMapInfo.h:105
llvm::DenseMapInfo< int >::getEmptyKey
static int getEmptyKey()
Definition: DenseMapInfo.h:174
llvm::DenseMapInfo< unsigned char >::getHashValue
static unsigned getHashValue(const unsigned char &Val)
Definition: DenseMapInfo.h:106
std
Definition: BitVector.h:851
llvm::DenseMapInfo< unsigned long >::isEqual
static bool isEqual(const unsigned long &LHS, const unsigned long &RHS)
Definition: DenseMapInfo.h:144
llvm::DenseMapInfo< std::tuple< Ts... > >::getHashValueImpl
static unsigned getHashValueImpl(const Tuple &values, std::false_type)
Definition: DenseMapInfo.h:256
isEqual
static bool isEqual(const Function &Caller, const Function &Callee)
Definition: Attributes.cpp:1954
llvm::DenseMapInfo< std::variant< Ts... > >::getHashValue
static unsigned getHashValue(const Variant &Val)
Definition: DenseMapInfo.h:307
llvm::DenseMapInfo< std::tuple< Ts... > >::isEqual
static bool isEqual(const Tuple &lhs, const Tuple &rhs)
Definition: DenseMapInfo.h:287
llvm::DenseMapInfo< std::tuple< Ts... > >::getHashValueImpl
static unsigned getHashValueImpl(const Tuple &, std::true_type)
Definition: DenseMapInfo.h:265
llvm::DenseMapInfo< long long >::getTombstoneKey
static long long getTombstoneKey()
Definition: DenseMapInfo.h:203
llvm::DenseMapInfo< unsigned >::getTombstoneKey
static unsigned getTombstoneKey()
Definition: DenseMapInfo.h:127
llvm::DenseMapInfo< short >::getHashValue
static unsigned getHashValue(const short &Val)
Definition: DenseMapInfo.h:168
llvm::DenseMapInfo< unsigned long long >::getTombstoneKey
static unsigned long long getTombstoneKey()
Definition: DenseMapInfo.h:152
llvm::DenseMapInfo< short >::isEqual
static bool isEqual(const short &LHS, const short &RHS)
Definition: DenseMapInfo.h:169
llvm::DenseMapInfo< std::pair< T, U > >::getTombstoneKey
static Pair getTombstoneKey()
Definition: DenseMapInfo.h:227
llvm::DenseMapInfo< std::pair< T, U > >::getEmptyKey
static Pair getEmptyKey()
Definition: DenseMapInfo.h:222