LLVM  15.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 <utility>
22 
23 namespace llvm {
24 
25 namespace detail {
26 
27 /// Simplistic combination of 32-bit hash values into 32-bit hash values.
28 static inline unsigned combineHashValue(unsigned a, unsigned b) {
29  uint64_t key = (uint64_t)a << 32 | (uint64_t)b;
30  key += ~(key << 32);
31  key ^= (key >> 22);
32  key += ~(key << 13);
33  key ^= (key >> 8);
34  key += (key << 3);
35  key ^= (key >> 15);
36  key += ~(key << 27);
37  key ^= (key >> 31);
38  return (unsigned)key;
39 }
40 
41 } // end namespace detail
42 
43 /// An information struct used to provide DenseMap with the various necessary
44 /// components for a given value type `T`. `Enable` is an optional additional
45 /// parameter that is used to support SFINAE (generally using std::enable_if_t)
46 /// in derived DenseMapInfo specializations; in non-SFINAE use cases this should
47 /// just be `void`.
48 template<typename T, typename Enable = void>
49 struct DenseMapInfo {
50  //static inline T getEmptyKey();
51  //static inline T getTombstoneKey();
52  //static unsigned getHashValue(const T &Val);
53  //static bool isEqual(const T &LHS, const T &RHS);
54 };
55 
56 // Provide DenseMapInfo for all pointers. Come up with sentinel pointer values
57 // that are aligned to alignof(T) bytes, but try to avoid requiring T to be
58 // complete. This allows clients to instantiate DenseMap<T*, ...> with forward
59 // declared key types. Assume that no pointer key type requires more than 4096
60 // bytes of alignment.
61 template<typename T>
62 struct DenseMapInfo<T*> {
63  // The following should hold, but it would require T to be complete:
64  // static_assert(alignof(T) <= (1 << Log2MaxAlign),
65  // "DenseMap does not support pointer keys requiring more than "
66  // "Log2MaxAlign bits of alignment");
67  static constexpr uintptr_t Log2MaxAlign = 12;
68 
69  static inline T* getEmptyKey() {
70  uintptr_t Val = static_cast<uintptr_t>(-1);
71  Val <<= Log2MaxAlign;
72  return reinterpret_cast<T*>(Val);
73  }
74 
75  static inline T* getTombstoneKey() {
76  uintptr_t Val = static_cast<uintptr_t>(-2);
77  Val <<= Log2MaxAlign;
78  return reinterpret_cast<T*>(Val);
79  }
80 
81  static unsigned getHashValue(const T *PtrVal) {
82  return (unsigned((uintptr_t)PtrVal) >> 4) ^
83  (unsigned((uintptr_t)PtrVal) >> 9);
84  }
85 
86  static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; }
87 };
88 
89 // Provide DenseMapInfo for chars.
90 template<> struct DenseMapInfo<char> {
91  static inline char getEmptyKey() { return ~0; }
92  static inline char getTombstoneKey() { return ~0 - 1; }
93  static unsigned getHashValue(const char& Val) { return Val * 37U; }
94 
95  static bool isEqual(const char &LHS, const char &RHS) {
96  return LHS == RHS;
97  }
98 };
99 
100 // Provide DenseMapInfo for unsigned chars.
101 template <> struct DenseMapInfo<unsigned char> {
102  static inline unsigned char getEmptyKey() { return ~0; }
103  static inline unsigned char getTombstoneKey() { return ~0 - 1; }
104  static unsigned getHashValue(const unsigned char &Val) { return Val * 37U; }
105 
106  static bool isEqual(const unsigned char &LHS, const unsigned char &RHS) {
107  return LHS == RHS;
108  }
109 };
110 
111 // Provide DenseMapInfo for unsigned shorts.
112 template <> struct DenseMapInfo<unsigned short> {
113  static inline unsigned short getEmptyKey() { return 0xFFFF; }
114  static inline unsigned short getTombstoneKey() { return 0xFFFF - 1; }
115  static unsigned getHashValue(const unsigned short &Val) { return Val * 37U; }
116 
117  static bool isEqual(const unsigned short &LHS, const unsigned short &RHS) {
118  return LHS == RHS;
119  }
120 };
121 
122 // Provide DenseMapInfo for unsigned ints.
123 template<> struct DenseMapInfo<unsigned> {
124  static inline unsigned getEmptyKey() { return ~0U; }
125  static inline unsigned getTombstoneKey() { return ~0U - 1; }
126  static unsigned getHashValue(const unsigned& Val) { return Val * 37U; }
127 
128  static bool isEqual(const unsigned& LHS, const unsigned& RHS) {
129  return LHS == RHS;
130  }
131 };
132 
133 // Provide DenseMapInfo for unsigned longs.
134 template<> struct DenseMapInfo<unsigned long> {
135  static inline unsigned long getEmptyKey() { return ~0UL; }
136  static inline unsigned long getTombstoneKey() { return ~0UL - 1L; }
137 
138  static unsigned getHashValue(const unsigned long& Val) {
139  return (unsigned)(Val * 37UL);
140  }
141 
142  static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) {
143  return LHS == RHS;
144  }
145 };
146 
147 // Provide DenseMapInfo for unsigned long longs.
148 template<> struct DenseMapInfo<unsigned long long> {
149  static inline unsigned long long getEmptyKey() { return ~0ULL; }
150  static inline unsigned long long getTombstoneKey() { return ~0ULL - 1ULL; }
151 
152  static unsigned getHashValue(const unsigned long long& Val) {
153  return (unsigned)(Val * 37ULL);
154  }
155 
156  static bool isEqual(const unsigned long long& LHS,
157  const unsigned long long& RHS) {
158  return LHS == RHS;
159  }
160 };
161 
162 // Provide DenseMapInfo for shorts.
163 template <> struct DenseMapInfo<short> {
164  static inline short getEmptyKey() { return 0x7FFF; }
165  static inline short getTombstoneKey() { return -0x7FFF - 1; }
166  static unsigned getHashValue(const short &Val) { return Val * 37U; }
167  static bool isEqual(const short &LHS, const short &RHS) { return LHS == RHS; }
168 };
169 
170 // Provide DenseMapInfo for ints.
171 template<> struct DenseMapInfo<int> {
172  static inline int getEmptyKey() { return 0x7fffffff; }
173  static inline int getTombstoneKey() { return -0x7fffffff - 1; }
174  static unsigned getHashValue(const int& Val) { return (unsigned)(Val * 37U); }
175 
176  static bool isEqual(const int& LHS, const int& RHS) {
177  return LHS == RHS;
178  }
179 };
180 
181 // Provide DenseMapInfo for longs.
182 template<> struct DenseMapInfo<long> {
183  static inline long getEmptyKey() {
184  return (1UL << (sizeof(long) * 8 - 1)) - 1UL;
185  }
186 
187  static inline long getTombstoneKey() { return getEmptyKey() - 1L; }
188 
189  static unsigned getHashValue(const long& Val) {
190  return (unsigned)(Val * 37UL);
191  }
192 
193  static bool isEqual(const long& LHS, const long& RHS) {
194  return LHS == RHS;
195  }
196 };
197 
198 // Provide DenseMapInfo for long longs.
199 template<> struct DenseMapInfo<long long> {
200  static inline long long getEmptyKey() { return 0x7fffffffffffffffLL; }
201  static inline long long getTombstoneKey() { return -0x7fffffffffffffffLL-1; }
202 
203  static unsigned getHashValue(const long long& Val) {
204  return (unsigned)(Val * 37ULL);
205  }
206 
207  static bool isEqual(const long long& LHS,
208  const long long& RHS) {
209  return LHS == RHS;
210  }
211 };
212 
213 // Provide DenseMapInfo for all pairs whose members have info.
214 template<typename T, typename U>
215 struct DenseMapInfo<std::pair<T, U>> {
216  using Pair = std::pair<T, U>;
219 
220  static inline Pair getEmptyKey() {
221  return std::make_pair(FirstInfo::getEmptyKey(),
222  SecondInfo::getEmptyKey());
223  }
224 
225  static inline Pair getTombstoneKey() {
226  return std::make_pair(FirstInfo::getTombstoneKey(),
227  SecondInfo::getTombstoneKey());
228  }
229 
230  static unsigned getHashValue(const Pair& PairVal) {
231  return detail::combineHashValue(FirstInfo::getHashValue(PairVal.first),
232  SecondInfo::getHashValue(PairVal.second));
233  }
234 
235  static bool isEqual(const Pair &LHS, const Pair &RHS) {
236  return FirstInfo::isEqual(LHS.first, RHS.first) &&
237  SecondInfo::isEqual(LHS.second, RHS.second);
238  }
239 };
240 
241 // Provide DenseMapInfo for all tuples whose members have info.
242 template <typename... Ts> struct DenseMapInfo<std::tuple<Ts...>> {
243  using Tuple = std::tuple<Ts...>;
244 
245  static inline Tuple getEmptyKey() {
247  }
248 
249  static inline Tuple getTombstoneKey() {
251  }
252 
253  template <unsigned I>
254  static unsigned getHashValueImpl(const Tuple &values, std::false_type) {
255  using EltType = typename std::tuple_element<I, Tuple>::type;
256  std::integral_constant<bool, I + 1 == sizeof...(Ts)> atEnd;
259  getHashValueImpl<I + 1>(values, atEnd));
260  }
261 
262  template <unsigned I>
263  static unsigned getHashValueImpl(const Tuple &, std::true_type) {
264  return 0;
265  }
266 
267  static unsigned getHashValue(const std::tuple<Ts...> &values) {
268  std::integral_constant<bool, 0 == sizeof...(Ts)> atEnd;
269  return getHashValueImpl<0>(values, atEnd);
270  }
271 
272  template <unsigned I>
273  static bool isEqualImpl(const Tuple &lhs, const Tuple &rhs, std::false_type) {
274  using EltType = typename std::tuple_element<I, Tuple>::type;
275  std::integral_constant<bool, I + 1 == sizeof...(Ts)> atEnd;
276  return DenseMapInfo<EltType>::isEqual(std::get<I>(lhs), std::get<I>(rhs)) &&
277  isEqualImpl<I + 1>(lhs, rhs, atEnd);
278  }
279 
280  template <unsigned I>
281  static bool isEqualImpl(const Tuple &, const Tuple &, std::true_type) {
282  return true;
283  }
284 
285  static bool isEqual(const Tuple &lhs, const Tuple &rhs) {
286  std::integral_constant<bool, 0 == sizeof...(Ts)> atEnd;
287  return isEqualImpl<0>(lhs, rhs, atEnd);
288  }
289 };
290 
291 } // end namespace llvm
292 
293 #endif // LLVM_ADT_DENSEMAPINFO_H
llvm::DenseMapInfo< unsigned short >::getTombstoneKey
static unsigned short getTombstoneKey()
Definition: DenseMapInfo.h:114
llvm::DenseMapInfo< short >::getEmptyKey
static short getEmptyKey()
Definition: DenseMapInfo.h:164
llvm::DenseMapInfo< T * >::getTombstoneKey
static T * getTombstoneKey()
Definition: DenseMapInfo.h:75
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::DenseMapInfo< std::tuple< Ts... > >::isEqualImpl
static bool isEqualImpl(const Tuple &lhs, const Tuple &rhs, std::false_type)
Definition: DenseMapInfo.h:273
llvm::DenseMapInfo< long long >::getEmptyKey
static long long getEmptyKey()
Definition: DenseMapInfo.h:200
llvm::DenseMapInfo< long >::getEmptyKey
static long getEmptyKey()
Definition: DenseMapInfo.h:183
llvm::DenseMapInfo< char >::getEmptyKey
static char getEmptyKey()
Definition: DenseMapInfo.h:91
llvm::DenseMapInfo< unsigned long long >::getHashValue
static unsigned getHashValue(const unsigned long long &Val)
Definition: DenseMapInfo.h:152
llvm::DenseMapInfo< std::tuple< Ts... > >::getTombstoneKey
static Tuple getTombstoneKey()
Definition: DenseMapInfo.h:249
llvm::DenseMapInfo< unsigned long >::getTombstoneKey
static unsigned long getTombstoneKey()
Definition: DenseMapInfo.h:136
llvm::DenseMapInfo< T * >::getHashValue
static unsigned getHashValue(const T *PtrVal)
Definition: DenseMapInfo.h:81
llvm::DenseMapInfo< long >::getHashValue
static unsigned getHashValue(const long &Val)
Definition: DenseMapInfo.h:189
llvm::DenseMapInfo< char >::isEqual
static bool isEqual(const char &LHS, const char &RHS)
Definition: DenseMapInfo.h:95
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:117
llvm::DenseMapInfo< unsigned long long >::isEqual
static bool isEqual(const unsigned long long &LHS, const unsigned long long &RHS)
Definition: DenseMapInfo.h:156
llvm::DenseMapInfo< long long >::isEqual
static bool isEqual(const long long &LHS, const long long &RHS)
Definition: DenseMapInfo.h:207
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:92
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< unsigned >::isEqual
static bool isEqual(const unsigned &LHS, const unsigned &RHS)
Definition: DenseMapInfo.h:128
llvm::DenseMapInfo< long long >::getHashValue
static unsigned getHashValue(const long long &Val)
Definition: DenseMapInfo.h:203
llvm::DenseMapInfo< unsigned char >::isEqual
static bool isEqual(const unsigned char &LHS, const unsigned char &RHS)
Definition: DenseMapInfo.h:106
llvm::DenseMapInfo< int >::getHashValue
static unsigned getHashValue(const int &Val)
Definition: DenseMapInfo.h:174
llvm::DenseMapInfo< std::tuple< Ts... > >::Tuple
std::tuple< Ts... > Tuple
Definition: DenseMapInfo.h:243
llvm::DenseMapInfo< unsigned long >::getHashValue
static unsigned getHashValue(const unsigned long &Val)
Definition: DenseMapInfo.h:138
llvm::DenseMapInfo< unsigned short >::getEmptyKey
static unsigned short getEmptyKey()
Definition: DenseMapInfo.h:113
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:149
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:115
llvm::DenseMapInfo< std::tuple< Ts... > >::isEqualImpl
static bool isEqualImpl(const Tuple &, const Tuple &, std::true_type)
Definition: DenseMapInfo.h:281
llvm::DenseMapInfo< int >::getTombstoneKey
static int getTombstoneKey()
Definition: DenseMapInfo.h:173
llvm::DenseMapInfo< T * >::getEmptyKey
static T * getEmptyKey()
Definition: DenseMapInfo.h:69
llvm::DenseMapInfo< std::pair< T, U > >::getHashValue
static unsigned getHashValue(const Pair &PairVal)
Definition: DenseMapInfo.h:230
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:28
llvm::DenseMapInfo< unsigned long >::getEmptyKey
static unsigned long getEmptyKey()
Definition: DenseMapInfo.h:135
llvm::DenseMapInfo< long >::getTombstoneKey
static long getTombstoneKey()
Definition: DenseMapInfo.h:187
llvm::DenseMapInfo< unsigned >::getHashValue
static unsigned getHashValue(const unsigned &Val)
Definition: DenseMapInfo.h:126
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:685
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:267
uint64_t
llvm::DenseMapInfo< T * >::isEqual
static bool isEqual(const T *LHS, const T *RHS)
Definition: DenseMapInfo.h:86
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:193
llvm::DenseMapInfo< unsigned >::getEmptyKey
static unsigned getEmptyKey()
Definition: DenseMapInfo.h:124
llvm::DenseMapInfo< short >::getTombstoneKey
static short getTombstoneKey()
Definition: DenseMapInfo.h:165
llvm::DenseMapInfo< std::tuple< Ts... > >::getEmptyKey
static Tuple getEmptyKey()
Definition: DenseMapInfo.h:245
llvm::DenseMapInfo< std::pair< T, U > >::isEqual
static bool isEqual(const Pair &LHS, const Pair &RHS)
Definition: DenseMapInfo.h:235
llvm::DenseMapInfo< std::pair< T, U > >::Pair
std::pair< T, U > Pair
Definition: DenseMapInfo.h:216
llvm::DenseMapInfo< int >::isEqual
static bool isEqual(const int &LHS, const int &RHS)
Definition: DenseMapInfo.h:176
llvm::DenseMapInfo< char >::getHashValue
static unsigned getHashValue(const char &Val)
Definition: DenseMapInfo.h:93
llvm::DenseMapInfo< unsigned char >::getEmptyKey
static unsigned char getEmptyKey()
Definition: DenseMapInfo.h:102
llvm::DenseMapInfo< unsigned char >::getTombstoneKey
static unsigned char getTombstoneKey()
Definition: DenseMapInfo.h:103
llvm::DenseMapInfo< int >::getEmptyKey
static int getEmptyKey()
Definition: DenseMapInfo.h:172
llvm::DenseMapInfo< unsigned char >::getHashValue
static unsigned getHashValue(const unsigned char &Val)
Definition: DenseMapInfo.h:104
std
Definition: BitVector.h:851
llvm::DenseMapInfo< unsigned long >::isEqual
static bool isEqual(const unsigned long &LHS, const unsigned long &RHS)
Definition: DenseMapInfo.h:142
llvm::DenseMapInfo< std::tuple< Ts... > >::getHashValueImpl
static unsigned getHashValueImpl(const Tuple &values, std::false_type)
Definition: DenseMapInfo.h:254
isEqual
static bool isEqual(const Function &Caller, const Function &Callee)
Definition: Attributes.cpp:1834
llvm::DenseMapInfo< std::tuple< Ts... > >::isEqual
static bool isEqual(const Tuple &lhs, const Tuple &rhs)
Definition: DenseMapInfo.h:285
llvm::DenseMapInfo< std::tuple< Ts... > >::getHashValueImpl
static unsigned getHashValueImpl(const Tuple &, std::true_type)
Definition: DenseMapInfo.h:263
llvm::DenseMapInfo< long long >::getTombstoneKey
static long long getTombstoneKey()
Definition: DenseMapInfo.h:201
llvm::DenseMapInfo< unsigned >::getTombstoneKey
static unsigned getTombstoneKey()
Definition: DenseMapInfo.h:125
llvm::DenseMapInfo< short >::getHashValue
static unsigned getHashValue(const short &Val)
Definition: DenseMapInfo.h:166
llvm::DenseMapInfo< unsigned long long >::getTombstoneKey
static unsigned long long getTombstoneKey()
Definition: DenseMapInfo.h:150
llvm::DenseMapInfo< short >::isEqual
static bool isEqual(const short &LHS, const short &RHS)
Definition: DenseMapInfo.h:167
llvm::DenseMapInfo< std::pair< T, U > >::getTombstoneKey
static Pair getTombstoneKey()
Definition: DenseMapInfo.h:225
llvm::DenseMapInfo< std::pair< T, U > >::getEmptyKey
static Pair getEmptyKey()
Definition: DenseMapInfo.h:220