LLVM  14.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 // This file defines DenseMapInfo traits for DenseMap.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_ADT_DENSEMAPINFO_H
14 #define LLVM_ADT_DENSEMAPINFO_H
15 
16 #include <cassert>
17 #include <cstddef>
18 #include <cstdint>
19 #include <tuple>
20 #include <utility>
21 
22 namespace llvm {
23 
24 namespace detail {
25 
26 /// Simplistic combination of 32-bit hash values into 32-bit hash values.
27 static inline unsigned combineHashValue(unsigned a, unsigned b) {
28  uint64_t key = (uint64_t)a << 32 | (uint64_t)b;
29  key += ~(key << 32);
30  key ^= (key >> 22);
31  key += ~(key << 13);
32  key ^= (key >> 8);
33  key += (key << 3);
34  key ^= (key >> 15);
35  key += ~(key << 27);
36  key ^= (key >> 31);
37  return (unsigned)key;
38 }
39 
40 } // end namespace detail
41 
42 /// An information struct used to provide DenseMap with the various necessary
43 /// components for a given value type `T`. `Enable` is an optional additional
44 /// parameter that is used to support SFINAE (generally using std::enable_if_t)
45 /// in derived DenseMapInfo specializations; in non-SFINAE use cases this should
46 /// just be `void`.
47 template<typename T, typename Enable = void>
48 struct DenseMapInfo {
49  //static inline T getEmptyKey();
50  //static inline T getTombstoneKey();
51  //static unsigned getHashValue(const T &Val);
52  //static bool isEqual(const T &LHS, const T &RHS);
53 };
54 
55 // Provide DenseMapInfo for all pointers. Come up with sentinel pointer values
56 // that are aligned to alignof(T) bytes, but try to avoid requiring T to be
57 // complete. This allows clients to instantiate DenseMap<T*, ...> with forward
58 // declared key types. Assume that no pointer key type requires more than 4096
59 // bytes of alignment.
60 template<typename T>
61 struct DenseMapInfo<T*> {
62  // The following should hold, but it would require T to be complete:
63  // static_assert(alignof(T) <= (1 << Log2MaxAlign),
64  // "DenseMap does not support pointer keys requiring more than "
65  // "Log2MaxAlign bits of alignment");
66  static constexpr uintptr_t Log2MaxAlign = 12;
67 
68  static inline T* getEmptyKey() {
69  uintptr_t Val = static_cast<uintptr_t>(-1);
70  Val <<= Log2MaxAlign;
71  return reinterpret_cast<T*>(Val);
72  }
73 
74  static inline T* getTombstoneKey() {
75  uintptr_t Val = static_cast<uintptr_t>(-2);
76  Val <<= Log2MaxAlign;
77  return reinterpret_cast<T*>(Val);
78  }
79 
80  static unsigned getHashValue(const T *PtrVal) {
81  return (unsigned((uintptr_t)PtrVal) >> 4) ^
82  (unsigned((uintptr_t)PtrVal) >> 9);
83  }
84 
85  static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; }
86 };
87 
88 // Provide DenseMapInfo for chars.
89 template<> struct DenseMapInfo<char> {
90  static inline char getEmptyKey() { return ~0; }
91  static inline char getTombstoneKey() { return ~0 - 1; }
92  static unsigned getHashValue(const char& Val) { return Val * 37U; }
93 
94  static bool isEqual(const char &LHS, const char &RHS) {
95  return LHS == RHS;
96  }
97 };
98 
99 // Provide DenseMapInfo for unsigned chars.
100 template <> struct DenseMapInfo<unsigned char> {
101  static inline unsigned char getEmptyKey() { return ~0; }
102  static inline unsigned char getTombstoneKey() { return ~0 - 1; }
103  static unsigned getHashValue(const unsigned char &Val) { return Val * 37U; }
104 
105  static bool isEqual(const unsigned char &LHS, const unsigned char &RHS) {
106  return LHS == RHS;
107  }
108 };
109 
110 // Provide DenseMapInfo for unsigned shorts.
111 template <> struct DenseMapInfo<unsigned short> {
112  static inline unsigned short getEmptyKey() { return 0xFFFF; }
113  static inline unsigned short getTombstoneKey() { return 0xFFFF - 1; }
114  static unsigned getHashValue(const unsigned short &Val) { return Val * 37U; }
115 
116  static bool isEqual(const unsigned short &LHS, const unsigned short &RHS) {
117  return LHS == RHS;
118  }
119 };
120 
121 // Provide DenseMapInfo for unsigned ints.
122 template<> struct DenseMapInfo<unsigned> {
123  static inline unsigned getEmptyKey() { return ~0U; }
124  static inline unsigned getTombstoneKey() { return ~0U - 1; }
125  static unsigned getHashValue(const unsigned& Val) { return Val * 37U; }
126 
127  static bool isEqual(const unsigned& LHS, const unsigned& RHS) {
128  return LHS == RHS;
129  }
130 };
131 
132 // Provide DenseMapInfo for unsigned longs.
133 template<> struct DenseMapInfo<unsigned long> {
134  static inline unsigned long getEmptyKey() { return ~0UL; }
135  static inline unsigned long getTombstoneKey() { return ~0UL - 1L; }
136 
137  static unsigned getHashValue(const unsigned long& Val) {
138  return (unsigned)(Val * 37UL);
139  }
140 
141  static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) {
142  return LHS == RHS;
143  }
144 };
145 
146 // Provide DenseMapInfo for unsigned long longs.
147 template<> struct DenseMapInfo<unsigned long long> {
148  static inline unsigned long long getEmptyKey() { return ~0ULL; }
149  static inline unsigned long long getTombstoneKey() { return ~0ULL - 1ULL; }
150 
151  static unsigned getHashValue(const unsigned long long& Val) {
152  return (unsigned)(Val * 37ULL);
153  }
154 
155  static bool isEqual(const unsigned long long& LHS,
156  const unsigned long long& RHS) {
157  return LHS == RHS;
158  }
159 };
160 
161 // Provide DenseMapInfo for shorts.
162 template <> struct DenseMapInfo<short> {
163  static inline short getEmptyKey() { return 0x7FFF; }
164  static inline short getTombstoneKey() { return -0x7FFF - 1; }
165  static unsigned getHashValue(const short &Val) { return Val * 37U; }
166  static bool isEqual(const short &LHS, const short &RHS) { return LHS == RHS; }
167 };
168 
169 // Provide DenseMapInfo for ints.
170 template<> struct DenseMapInfo<int> {
171  static inline int getEmptyKey() { return 0x7fffffff; }
172  static inline int getTombstoneKey() { return -0x7fffffff - 1; }
173  static unsigned getHashValue(const int& Val) { return (unsigned)(Val * 37U); }
174 
175  static bool isEqual(const int& LHS, const int& RHS) {
176  return LHS == RHS;
177  }
178 };
179 
180 // Provide DenseMapInfo for longs.
181 template<> struct DenseMapInfo<long> {
182  static inline long getEmptyKey() {
183  return (1UL << (sizeof(long) * 8 - 1)) - 1UL;
184  }
185 
186  static inline long getTombstoneKey() { return getEmptyKey() - 1L; }
187 
188  static unsigned getHashValue(const long& Val) {
189  return (unsigned)(Val * 37UL);
190  }
191 
192  static bool isEqual(const long& LHS, const long& RHS) {
193  return LHS == RHS;
194  }
195 };
196 
197 // Provide DenseMapInfo for long longs.
198 template<> struct DenseMapInfo<long long> {
199  static inline long long getEmptyKey() { return 0x7fffffffffffffffLL; }
200  static inline long long getTombstoneKey() { return -0x7fffffffffffffffLL-1; }
201 
202  static unsigned getHashValue(const long long& Val) {
203  return (unsigned)(Val * 37ULL);
204  }
205 
206  static bool isEqual(const long long& LHS,
207  const long long& RHS) {
208  return LHS == RHS;
209  }
210 };
211 
212 // Provide DenseMapInfo for all pairs whose members have info.
213 template<typename T, typename U>
214 struct DenseMapInfo<std::pair<T, U>> {
215  using Pair = std::pair<T, U>;
218 
219  static inline Pair getEmptyKey() {
220  return std::make_pair(FirstInfo::getEmptyKey(),
221  SecondInfo::getEmptyKey());
222  }
223 
224  static inline Pair getTombstoneKey() {
225  return std::make_pair(FirstInfo::getTombstoneKey(),
226  SecondInfo::getTombstoneKey());
227  }
228 
229  static unsigned getHashValue(const Pair& PairVal) {
230  return detail::combineHashValue(FirstInfo::getHashValue(PairVal.first),
231  SecondInfo::getHashValue(PairVal.second));
232  }
233 
234  static bool isEqual(const Pair &LHS, const Pair &RHS) {
235  return FirstInfo::isEqual(LHS.first, RHS.first) &&
236  SecondInfo::isEqual(LHS.second, RHS.second);
237  }
238 };
239 
240 // Provide DenseMapInfo for all tuples whose members have info.
241 template <typename... Ts> struct DenseMapInfo<std::tuple<Ts...>> {
242  using Tuple = std::tuple<Ts...>;
243 
244  static inline Tuple getEmptyKey() {
246  }
247 
248  static inline Tuple getTombstoneKey() {
250  }
251 
252  template <unsigned I>
253  static unsigned getHashValueImpl(const Tuple &values, std::false_type) {
254  using EltType = typename std::tuple_element<I, Tuple>::type;
255  std::integral_constant<bool, I + 1 == sizeof...(Ts)> atEnd;
258  getHashValueImpl<I + 1>(values, atEnd));
259  }
260 
261  template <unsigned I>
262  static unsigned getHashValueImpl(const Tuple &, std::true_type) {
263  return 0;
264  }
265 
266  static unsigned getHashValue(const std::tuple<Ts...> &values) {
267  std::integral_constant<bool, 0 == sizeof...(Ts)> atEnd;
268  return getHashValueImpl<0>(values, atEnd);
269  }
270 
271  template <unsigned I>
272  static bool isEqualImpl(const Tuple &lhs, const Tuple &rhs, std::false_type) {
273  using EltType = typename std::tuple_element<I, Tuple>::type;
274  std::integral_constant<bool, I + 1 == sizeof...(Ts)> atEnd;
275  return DenseMapInfo<EltType>::isEqual(std::get<I>(lhs), std::get<I>(rhs)) &&
276  isEqualImpl<I + 1>(lhs, rhs, atEnd);
277  }
278 
279  template <unsigned I>
280  static bool isEqualImpl(const Tuple &, const Tuple &, std::true_type) {
281  return true;
282  }
283 
284  static bool isEqual(const Tuple &lhs, const Tuple &rhs) {
285  std::integral_constant<bool, 0 == sizeof...(Ts)> atEnd;
286  return isEqualImpl<0>(lhs, rhs, atEnd);
287  }
288 };
289 
290 } // end namespace llvm
291 
292 #endif // LLVM_ADT_DENSEMAPINFO_H
llvm::DenseMapInfo< unsigned short >::getTombstoneKey
static unsigned short getTombstoneKey()
Definition: DenseMapInfo.h:113
llvm::DenseMapInfo< short >::getEmptyKey
static short getEmptyKey()
Definition: DenseMapInfo.h:163
llvm::DenseMapInfo< T * >::getTombstoneKey
static T * getTombstoneKey()
Definition: DenseMapInfo.h:74
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
llvm::DenseMapInfo< std::tuple< Ts... > >::isEqualImpl
static bool isEqualImpl(const Tuple &lhs, const Tuple &rhs, std::false_type)
Definition: DenseMapInfo.h:272
llvm::DenseMapInfo< long long >::getEmptyKey
static long long getEmptyKey()
Definition: DenseMapInfo.h:199
llvm::DenseMapInfo< long >::getEmptyKey
static long getEmptyKey()
Definition: DenseMapInfo.h:182
llvm::DenseMapInfo< char >::getEmptyKey
static char getEmptyKey()
Definition: DenseMapInfo.h:90
llvm::DenseMapInfo< unsigned long long >::getHashValue
static unsigned getHashValue(const unsigned long long &Val)
Definition: DenseMapInfo.h:151
llvm::DenseMapInfo< std::tuple< Ts... > >::getTombstoneKey
static Tuple getTombstoneKey()
Definition: DenseMapInfo.h:248
llvm::DenseMapInfo< unsigned long >::getTombstoneKey
static unsigned long getTombstoneKey()
Definition: DenseMapInfo.h:135
llvm::DenseMapInfo< T * >::getHashValue
static unsigned getHashValue(const T *PtrVal)
Definition: DenseMapInfo.h:80
llvm::DenseMapInfo< long >::getHashValue
static unsigned getHashValue(const long &Val)
Definition: DenseMapInfo.h:188
llvm::DenseMapInfo< char >::isEqual
static bool isEqual(const char &LHS, const char &RHS)
Definition: DenseMapInfo.h:94
T
#define T
Definition: Mips16ISelLowering.cpp:341
RHS
Value * RHS
Definition: X86PartialReduction.cpp:74
llvm::DenseMapInfo< unsigned short >::isEqual
static bool isEqual(const unsigned short &LHS, const unsigned short &RHS)
Definition: DenseMapInfo.h:116
llvm::DenseMapInfo< unsigned long long >::isEqual
static bool isEqual(const unsigned long long &LHS, const unsigned long long &RHS)
Definition: DenseMapInfo.h:155
llvm::DenseMapInfo< long long >::isEqual
static bool isEqual(const long long &LHS, const long long &RHS)
Definition: DenseMapInfo.h:206
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:91
LHS
Value * LHS
Definition: X86PartialReduction.cpp:73
llvm::DenseMapInfo
An information struct used to provide DenseMap with the various necessary components for a given valu...
Definition: APInt.h:34
llvm::DenseMapInfo< unsigned >::isEqual
static bool isEqual(const unsigned &LHS, const unsigned &RHS)
Definition: DenseMapInfo.h:127
llvm::DenseMapInfo< long long >::getHashValue
static unsigned getHashValue(const long long &Val)
Definition: DenseMapInfo.h:202
llvm::DenseMapInfo< unsigned char >::isEqual
static bool isEqual(const unsigned char &LHS, const unsigned char &RHS)
Definition: DenseMapInfo.h:105
llvm::DenseMapInfo< int >::getHashValue
static unsigned getHashValue(const int &Val)
Definition: DenseMapInfo.h:173
llvm::DenseMapInfo< std::tuple< Ts... > >::Tuple
std::tuple< Ts... > Tuple
Definition: DenseMapInfo.h:242
llvm::DenseMapInfo< unsigned long >::getHashValue
static unsigned getHashValue(const unsigned long &Val)
Definition: DenseMapInfo.h:137
llvm::DenseMapInfo< unsigned short >::getEmptyKey
static unsigned short getEmptyKey()
Definition: DenseMapInfo.h:112
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:148
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< unsigned short >::getHashValue
static unsigned getHashValue(const unsigned short &Val)
Definition: DenseMapInfo.h:114
llvm::DenseMapInfo< std::tuple< Ts... > >::isEqualImpl
static bool isEqualImpl(const Tuple &, const Tuple &, std::true_type)
Definition: DenseMapInfo.h:280
llvm::DenseMapInfo< int >::getTombstoneKey
static int getTombstoneKey()
Definition: DenseMapInfo.h:172
llvm::DenseMapInfo< T * >::getEmptyKey
static T * getEmptyKey()
Definition: DenseMapInfo.h:68
llvm::DenseMapInfo< std::pair< T, U > >::getHashValue
static unsigned getHashValue(const Pair &PairVal)
Definition: DenseMapInfo.h:229
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:27
llvm::DenseMapInfo< unsigned long >::getEmptyKey
static unsigned long getEmptyKey()
Definition: DenseMapInfo.h:134
llvm::DenseMapInfo< long >::getTombstoneKey
static long getTombstoneKey()
Definition: DenseMapInfo.h:186
llvm::DenseMapInfo< unsigned >::getHashValue
static unsigned getHashValue(const unsigned &Val)
Definition: DenseMapInfo.h:125
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:697
type
AMD64 Optimization Manual has some nice information about optimizing integer multiplication by a constant How much of it applies to Intel s X86 implementation There are definite trade offs to xmm0 cvttss2siq rdx jb L3 subss xmm0 rax cvttss2siq rdx xorq rdx rax ret instead of xmm1 cvttss2siq rcx movaps xmm2 subss xmm2 cvttss2siq rax rdx xorq rax ucomiss xmm0 cmovb rax ret Seems like the jb branch has high likelihood of being taken It would have saved a few instructions It s not possible to reference and DH registers in an instruction requiring REX prefix divb and mulb both produce results in AH If isel emits a CopyFromReg which gets turned into a movb and that can be allocated a r8b r15b To get around isel emits a CopyFromReg from AX and then right shift it down by and truncate it It s not pretty but it works We need some register allocation magic to make the hack go which would often require a callee saved register Callees usually need to keep this value live for most of their body so it doesn t add a significant burden on them We currently implement this in however this is suboptimal because it means that it would be quite awkward to implement the optimization for callers A better implementation would be to relax the LLVM IR rules for sret arguments to allow a function with an sret argument to have a non void return type
Definition: README-X86-64.txt:70
llvm::DenseMapInfo< std::tuple< Ts... > >::getHashValue
static unsigned getHashValue(const std::tuple< Ts... > &values)
Definition: DenseMapInfo.h:266
uint64_t
llvm::DenseMapInfo< T * >::isEqual
static bool isEqual(const T *LHS, const T *RHS)
Definition: DenseMapInfo.h:85
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:192
llvm::DenseMapInfo< unsigned >::getEmptyKey
static unsigned getEmptyKey()
Definition: DenseMapInfo.h:123
llvm::DenseMapInfo< short >::getTombstoneKey
static short getTombstoneKey()
Definition: DenseMapInfo.h:164
llvm::DenseMapInfo< std::tuple< Ts... > >::getEmptyKey
static Tuple getEmptyKey()
Definition: DenseMapInfo.h:244
llvm::DenseMapInfo< std::pair< T, U > >::isEqual
static bool isEqual(const Pair &LHS, const Pair &RHS)
Definition: DenseMapInfo.h:234
llvm::DenseMapInfo< std::pair< T, U > >::Pair
std::pair< T, U > Pair
Definition: DenseMapInfo.h:215
llvm::DenseMapInfo< int >::isEqual
static bool isEqual(const int &LHS, const int &RHS)
Definition: DenseMapInfo.h:175
llvm::DenseMapInfo< char >::getHashValue
static unsigned getHashValue(const char &Val)
Definition: DenseMapInfo.h:92
llvm::DenseMapInfo< unsigned char >::getEmptyKey
static unsigned char getEmptyKey()
Definition: DenseMapInfo.h:101
llvm::DenseMapInfo< unsigned char >::getTombstoneKey
static unsigned char getTombstoneKey()
Definition: DenseMapInfo.h:102
llvm::DenseMapInfo< int >::getEmptyKey
static int getEmptyKey()
Definition: DenseMapInfo.h:171
llvm::DenseMapInfo< unsigned char >::getHashValue
static unsigned getHashValue(const unsigned char &Val)
Definition: DenseMapInfo.h:103
std
Definition: BitVector.h:850
llvm::DenseMapInfo< unsigned long >::isEqual
static bool isEqual(const unsigned long &LHS, const unsigned long &RHS)
Definition: DenseMapInfo.h:141
llvm::DenseMapInfo< std::tuple< Ts... > >::getHashValueImpl
static unsigned getHashValueImpl(const Tuple &values, std::false_type)
Definition: DenseMapInfo.h:253
isEqual
static bool isEqual(const Function &Caller, const Function &Callee)
Definition: Attributes.cpp:1803
llvm::DenseMapInfo< std::tuple< Ts... > >::isEqual
static bool isEqual(const Tuple &lhs, const Tuple &rhs)
Definition: DenseMapInfo.h:284
llvm::DenseMapInfo< std::tuple< Ts... > >::getHashValueImpl
static unsigned getHashValueImpl(const Tuple &, std::true_type)
Definition: DenseMapInfo.h:262
llvm::DenseMapInfo< long long >::getTombstoneKey
static long long getTombstoneKey()
Definition: DenseMapInfo.h:200
llvm::DenseMapInfo< unsigned >::getTombstoneKey
static unsigned getTombstoneKey()
Definition: DenseMapInfo.h:124
llvm::DenseMapInfo< short >::getHashValue
static unsigned getHashValue(const short &Val)
Definition: DenseMapInfo.h:165
llvm::DenseMapInfo< unsigned long long >::getTombstoneKey
static unsigned long long getTombstoneKey()
Definition: DenseMapInfo.h:149
llvm::DenseMapInfo< short >::isEqual
static bool isEqual(const short &LHS, const short &RHS)
Definition: DenseMapInfo.h:166
llvm::DenseMapInfo< std::pair< T, U > >::getTombstoneKey
static Pair getTombstoneKey()
Definition: DenseMapInfo.h:224
llvm::DenseMapInfo< std::pair< T, U > >::getEmptyKey
static Pair getEmptyKey()
Definition: DenseMapInfo.h:219