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 template<typename T>
43 struct DenseMapInfo {
44  //static inline T getEmptyKey();
45  //static inline T getTombstoneKey();
46  //static unsigned getHashValue(const T &Val);
47  //static bool isEqual(const T &LHS, const T &RHS);
48 };
49 
50 // Provide DenseMapInfo for all pointers. Come up with sentinel pointer values
51 // that are aligned to alignof(T) bytes, but try to avoid requiring T to be
52 // complete. This allows clients to instantiate DenseMap<T*, ...> with forward
53 // declared key types. Assume that no pointer key type requires more than 4096
54 // bytes of alignment.
55 template<typename T>
56 struct DenseMapInfo<T*> {
57  // The following should hold, but it would require T to be complete:
58  // static_assert(alignof(T) <= (1 << Log2MaxAlign),
59  // "DenseMap does not support pointer keys requiring more than "
60  // "Log2MaxAlign bits of alignment");
61  static constexpr uintptr_t Log2MaxAlign = 12;
62 
63  static inline T* getEmptyKey() {
64  uintptr_t Val = static_cast<uintptr_t>(-1);
65  Val <<= Log2MaxAlign;
66  return reinterpret_cast<T*>(Val);
67  }
68 
69  static inline T* getTombstoneKey() {
70  uintptr_t Val = static_cast<uintptr_t>(-2);
71  Val <<= Log2MaxAlign;
72  return reinterpret_cast<T*>(Val);
73  }
74 
75  static unsigned getHashValue(const T *PtrVal) {
76  return (unsigned((uintptr_t)PtrVal) >> 4) ^
77  (unsigned((uintptr_t)PtrVal) >> 9);
78  }
79 
80  static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; }
81 };
82 
83 // Provide DenseMapInfo for chars.
84 template<> struct DenseMapInfo<char> {
85  static inline char getEmptyKey() { return ~0; }
86  static inline char getTombstoneKey() { return ~0 - 1; }
87  static unsigned getHashValue(const char& Val) { return Val * 37U; }
88 
89  static bool isEqual(const char &LHS, const char &RHS) {
90  return LHS == RHS;
91  }
92 };
93 
94 // Provide DenseMapInfo for unsigned chars.
95 template <> struct DenseMapInfo<unsigned char> {
96  static inline unsigned char getEmptyKey() { return ~0; }
97  static inline unsigned char getTombstoneKey() { return ~0 - 1; }
98  static unsigned getHashValue(const unsigned char &Val) { return Val * 37U; }
99 
100  static bool isEqual(const unsigned char &LHS, const unsigned char &RHS) {
101  return LHS == RHS;
102  }
103 };
104 
105 // Provide DenseMapInfo for unsigned shorts.
106 template <> struct DenseMapInfo<unsigned short> {
107  static inline unsigned short getEmptyKey() { return 0xFFFF; }
108  static inline unsigned short getTombstoneKey() { return 0xFFFF - 1; }
109  static unsigned getHashValue(const unsigned short &Val) { return Val * 37U; }
110 
111  static bool isEqual(const unsigned short &LHS, const unsigned short &RHS) {
112  return LHS == RHS;
113  }
114 };
115 
116 // Provide DenseMapInfo for unsigned ints.
117 template<> struct DenseMapInfo<unsigned> {
118  static inline unsigned getEmptyKey() { return ~0U; }
119  static inline unsigned getTombstoneKey() { return ~0U - 1; }
120  static unsigned getHashValue(const unsigned& Val) { return Val * 37U; }
121 
122  static bool isEqual(const unsigned& LHS, const unsigned& RHS) {
123  return LHS == RHS;
124  }
125 };
126 
127 // Provide DenseMapInfo for unsigned longs.
128 template<> struct DenseMapInfo<unsigned long> {
129  static inline unsigned long getEmptyKey() { return ~0UL; }
130  static inline unsigned long getTombstoneKey() { return ~0UL - 1L; }
131 
132  static unsigned getHashValue(const unsigned long& Val) {
133  return (unsigned)(Val * 37UL);
134  }
135 
136  static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) {
137  return LHS == RHS;
138  }
139 };
140 
141 // Provide DenseMapInfo for unsigned long longs.
142 template<> struct DenseMapInfo<unsigned long long> {
143  static inline unsigned long long getEmptyKey() { return ~0ULL; }
144  static inline unsigned long long getTombstoneKey() { return ~0ULL - 1ULL; }
145 
146  static unsigned getHashValue(const unsigned long long& Val) {
147  return (unsigned)(Val * 37ULL);
148  }
149 
150  static bool isEqual(const unsigned long long& LHS,
151  const unsigned long long& RHS) {
152  return LHS == RHS;
153  }
154 };
155 
156 // Provide DenseMapInfo for shorts.
157 template <> struct DenseMapInfo<short> {
158  static inline short getEmptyKey() { return 0x7FFF; }
159  static inline short getTombstoneKey() { return -0x7FFF - 1; }
160  static unsigned getHashValue(const short &Val) { return Val * 37U; }
161  static bool isEqual(const short &LHS, const short &RHS) { return LHS == RHS; }
162 };
163 
164 // Provide DenseMapInfo for ints.
165 template<> struct DenseMapInfo<int> {
166  static inline int getEmptyKey() { return 0x7fffffff; }
167  static inline int getTombstoneKey() { return -0x7fffffff - 1; }
168  static unsigned getHashValue(const int& Val) { return (unsigned)(Val * 37U); }
169 
170  static bool isEqual(const int& LHS, const int& RHS) {
171  return LHS == RHS;
172  }
173 };
174 
175 // Provide DenseMapInfo for longs.
176 template<> struct DenseMapInfo<long> {
177  static inline long getEmptyKey() {
178  return (1UL << (sizeof(long) * 8 - 1)) - 1UL;
179  }
180 
181  static inline long getTombstoneKey() { return getEmptyKey() - 1L; }
182 
183  static unsigned getHashValue(const long& Val) {
184  return (unsigned)(Val * 37UL);
185  }
186 
187  static bool isEqual(const long& LHS, const long& RHS) {
188  return LHS == RHS;
189  }
190 };
191 
192 // Provide DenseMapInfo for long longs.
193 template<> struct DenseMapInfo<long long> {
194  static inline long long getEmptyKey() { return 0x7fffffffffffffffLL; }
195  static inline long long getTombstoneKey() { return -0x7fffffffffffffffLL-1; }
196 
197  static unsigned getHashValue(const long long& Val) {
198  return (unsigned)(Val * 37ULL);
199  }
200 
201  static bool isEqual(const long long& LHS,
202  const long long& RHS) {
203  return LHS == RHS;
204  }
205 };
206 
207 // Provide DenseMapInfo for all pairs whose members have info.
208 template<typename T, typename U>
209 struct DenseMapInfo<std::pair<T, U>> {
210  using Pair = std::pair<T, U>;
213 
214  static inline Pair getEmptyKey() {
215  return std::make_pair(FirstInfo::getEmptyKey(),
216  SecondInfo::getEmptyKey());
217  }
218 
219  static inline Pair getTombstoneKey() {
220  return std::make_pair(FirstInfo::getTombstoneKey(),
221  SecondInfo::getTombstoneKey());
222  }
223 
224  static unsigned getHashValue(const Pair& PairVal) {
225  return detail::combineHashValue(FirstInfo::getHashValue(PairVal.first),
226  SecondInfo::getHashValue(PairVal.second));
227  }
228 
229  static bool isEqual(const Pair &LHS, const Pair &RHS) {
230  return FirstInfo::isEqual(LHS.first, RHS.first) &&
231  SecondInfo::isEqual(LHS.second, RHS.second);
232  }
233 };
234 
235 // Provide DenseMapInfo for all tuples whose members have info.
236 template <typename... Ts> struct DenseMapInfo<std::tuple<Ts...>> {
237  using Tuple = std::tuple<Ts...>;
238 
239  static inline Tuple getEmptyKey() {
241  }
242 
243  static inline Tuple getTombstoneKey() {
245  }
246 
247  template <unsigned I>
248  static unsigned getHashValueImpl(const Tuple &values, std::false_type) {
249  using EltType = typename std::tuple_element<I, Tuple>::type;
250  std::integral_constant<bool, I + 1 == sizeof...(Ts)> atEnd;
253  getHashValueImpl<I + 1>(values, atEnd));
254  }
255 
256  template <unsigned I>
257  static unsigned getHashValueImpl(const Tuple &, std::true_type) {
258  return 0;
259  }
260 
261  static unsigned getHashValue(const std::tuple<Ts...> &values) {
262  std::integral_constant<bool, 0 == sizeof...(Ts)> atEnd;
263  return getHashValueImpl<0>(values, atEnd);
264  }
265 
266  template <unsigned I>
267  static bool isEqualImpl(const Tuple &lhs, const Tuple &rhs, std::false_type) {
268  using EltType = typename std::tuple_element<I, Tuple>::type;
269  std::integral_constant<bool, I + 1 == sizeof...(Ts)> atEnd;
270  return DenseMapInfo<EltType>::isEqual(std::get<I>(lhs), std::get<I>(rhs)) &&
271  isEqualImpl<I + 1>(lhs, rhs, atEnd);
272  }
273 
274  template <unsigned I>
275  static bool isEqualImpl(const Tuple &, const Tuple &, std::true_type) {
276  return true;
277  }
278 
279  static bool isEqual(const Tuple &lhs, const Tuple &rhs) {
280  std::integral_constant<bool, 0 == sizeof...(Ts)> atEnd;
281  return isEqualImpl<0>(lhs, rhs, atEnd);
282  }
283 };
284 
285 } // end namespace llvm
286 
287 #endif // LLVM_ADT_DENSEMAPINFO_H
llvm::DenseMapInfo< unsigned short >::getTombstoneKey
static unsigned short getTombstoneKey()
Definition: DenseMapInfo.h:108
llvm::DenseMapInfo< short >::getEmptyKey
static short getEmptyKey()
Definition: DenseMapInfo.h:158
llvm::DenseMapInfo< T * >::getTombstoneKey
static T * getTombstoneKey()
Definition: DenseMapInfo.h:69
llvm
This file implements support for optimizing divisions by a constant.
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:267
llvm::DenseMapInfo< long long >::getEmptyKey
static long long getEmptyKey()
Definition: DenseMapInfo.h:194
llvm::DenseMapInfo< long >::getEmptyKey
static long getEmptyKey()
Definition: DenseMapInfo.h:177
llvm::DenseMapInfo< char >::getEmptyKey
static char getEmptyKey()
Definition: DenseMapInfo.h:85
llvm::DenseMapInfo< unsigned long long >::getHashValue
static unsigned getHashValue(const unsigned long long &Val)
Definition: DenseMapInfo.h:146
llvm::DenseMapInfo< std::tuple< Ts... > >::getTombstoneKey
static Tuple getTombstoneKey()
Definition: DenseMapInfo.h:243
llvm::DenseMapInfo< unsigned long >::getTombstoneKey
static unsigned long getTombstoneKey()
Definition: DenseMapInfo.h:130
llvm::DenseMapInfo< T * >::getHashValue
static unsigned getHashValue(const T *PtrVal)
Definition: DenseMapInfo.h:75
llvm::DenseMapInfo< long >::getHashValue
static unsigned getHashValue(const long &Val)
Definition: DenseMapInfo.h:183
llvm::DenseMapInfo< char >::isEqual
static bool isEqual(const char &LHS, const char &RHS)
Definition: DenseMapInfo.h:89
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::DenseMapInfo< unsigned short >::isEqual
static bool isEqual(const unsigned short &LHS, const unsigned short &RHS)
Definition: DenseMapInfo.h:111
llvm::DenseMapInfo< unsigned long long >::isEqual
static bool isEqual(const unsigned long long &LHS, const unsigned long long &RHS)
Definition: DenseMapInfo.h:150
llvm::DenseMapInfo< long long >::isEqual
static bool isEqual(const long long &LHS, const long long &RHS)
Definition: DenseMapInfo.h:201
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:86
llvm::DenseMapInfo
Definition: APInt.h:34
llvm::DenseMapInfo< unsigned >::isEqual
static bool isEqual(const unsigned &LHS, const unsigned &RHS)
Definition: DenseMapInfo.h:122
llvm::DenseMapInfo< long long >::getHashValue
static unsigned getHashValue(const long long &Val)
Definition: DenseMapInfo.h:197
llvm::DenseMapInfo< unsigned char >::isEqual
static bool isEqual(const unsigned char &LHS, const unsigned char &RHS)
Definition: DenseMapInfo.h:100
llvm::DenseMapInfo< int >::getHashValue
static unsigned getHashValue(const int &Val)
Definition: DenseMapInfo.h:168
llvm::DenseMapInfo< std::tuple< Ts... > >::Tuple
std::tuple< Ts... > Tuple
Definition: DenseMapInfo.h:237
llvm::DenseMapInfo< unsigned long >::getHashValue
static unsigned getHashValue(const unsigned long &Val)
Definition: DenseMapInfo.h:132
llvm::DenseMapInfo< unsigned short >::getEmptyKey
static unsigned short getEmptyKey()
Definition: DenseMapInfo.h:107
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:143
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:109
llvm::DenseMapInfo< std::tuple< Ts... > >::isEqualImpl
static bool isEqualImpl(const Tuple &, const Tuple &, std::true_type)
Definition: DenseMapInfo.h:275
llvm::DenseMapInfo< int >::getTombstoneKey
static int getTombstoneKey()
Definition: DenseMapInfo.h:167
llvm::DenseMapInfo< T * >::getEmptyKey
static T * getEmptyKey()
Definition: DenseMapInfo.h:63
llvm::DenseMapInfo< std::pair< T, U > >::getHashValue
static unsigned getHashValue(const Pair &PairVal)
Definition: DenseMapInfo.h:224
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:129
llvm::DenseMapInfo< long >::getTombstoneKey
static long getTombstoneKey()
Definition: DenseMapInfo.h:181
llvm::DenseMapInfo< unsigned >::getHashValue
static unsigned getHashValue(const unsigned &Val)
Definition: DenseMapInfo.h:120
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:261
uint64_t
llvm::DenseMapInfo< T * >::isEqual
static bool isEqual(const T *LHS, const T *RHS)
Definition: DenseMapInfo.h:80
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::DenseMapInfo< long >::isEqual
static bool isEqual(const long &LHS, const long &RHS)
Definition: DenseMapInfo.h:187
llvm::DenseMapInfo< unsigned >::getEmptyKey
static unsigned getEmptyKey()
Definition: DenseMapInfo.h:118
llvm::DenseMapInfo< short >::getTombstoneKey
static short getTombstoneKey()
Definition: DenseMapInfo.h:159
llvm::DenseMapInfo< std::tuple< Ts... > >::getEmptyKey
static Tuple getEmptyKey()
Definition: DenseMapInfo.h:239
llvm::DenseMapInfo< std::pair< T, U > >::isEqual
static bool isEqual(const Pair &LHS, const Pair &RHS)
Definition: DenseMapInfo.h:229
llvm::DenseMapInfo< std::pair< T, U > >::Pair
std::pair< T, U > Pair
Definition: DenseMapInfo.h:210
llvm::DenseMapInfo< int >::isEqual
static bool isEqual(const int &LHS, const int &RHS)
Definition: DenseMapInfo.h:170
llvm::DenseMapInfo< char >::getHashValue
static unsigned getHashValue(const char &Val)
Definition: DenseMapInfo.h:87
llvm::DenseMapInfo< unsigned char >::getEmptyKey
static unsigned char getEmptyKey()
Definition: DenseMapInfo.h:96
llvm::DenseMapInfo< unsigned char >::getTombstoneKey
static unsigned char getTombstoneKey()
Definition: DenseMapInfo.h:97
llvm::DenseMapInfo< int >::getEmptyKey
static int getEmptyKey()
Definition: DenseMapInfo.h:166
llvm::DenseMapInfo< unsigned char >::getHashValue
static unsigned getHashValue(const unsigned char &Val)
Definition: DenseMapInfo.h:98
std
Definition: BitVector.h:838
llvm::DenseMapInfo< unsigned long >::isEqual
static bool isEqual(const unsigned long &LHS, const unsigned long &RHS)
Definition: DenseMapInfo.h:136
llvm::DenseMapInfo< std::tuple< Ts... > >::getHashValueImpl
static unsigned getHashValueImpl(const Tuple &values, std::false_type)
Definition: DenseMapInfo.h:248
isEqual
static bool isEqual(const Function &Caller, const Function &Callee)
Definition: Attributes.cpp:1856
llvm::DenseMapInfo< std::tuple< Ts... > >::isEqual
static bool isEqual(const Tuple &lhs, const Tuple &rhs)
Definition: DenseMapInfo.h:279
llvm::DenseMapInfo< std::tuple< Ts... > >::getHashValueImpl
static unsigned getHashValueImpl(const Tuple &, std::true_type)
Definition: DenseMapInfo.h:257
llvm::DenseMapInfo< long long >::getTombstoneKey
static long long getTombstoneKey()
Definition: DenseMapInfo.h:195
llvm::DenseMapInfo< unsigned >::getTombstoneKey
static unsigned getTombstoneKey()
Definition: DenseMapInfo.h:119
llvm::DenseMapInfo< short >::getHashValue
static unsigned getHashValue(const short &Val)
Definition: DenseMapInfo.h:160
llvm::DenseMapInfo< unsigned long long >::getTombstoneKey
static unsigned long long getTombstoneKey()
Definition: DenseMapInfo.h:144
llvm::DenseMapInfo< short >::isEqual
static bool isEqual(const short &LHS, const short &RHS)
Definition: DenseMapInfo.h:161
llvm::DenseMapInfo< std::pair< T, U > >::getTombstoneKey
static Pair getTombstoneKey()
Definition: DenseMapInfo.h:219
llvm::DenseMapInfo< std::pair< T, U > >::getEmptyKey
static Pair getEmptyKey()
Definition: DenseMapInfo.h:214