LLVM  14.0.0git
ScopedHashTable.h
Go to the documentation of this file.
1 //===- ScopedHashTable.h - A simple scoped hash table -----------*- 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 implements an efficient scoped hash table, which is useful for
10 // things like dominator-based optimizations. This allows clients to do things
11 // like this:
12 //
13 // ScopedHashTable<int, int> HT;
14 // {
15 // ScopedHashTableScope<int, int> Scope1(HT);
16 // HT.insert(0, 0);
17 // HT.insert(1, 1);
18 // {
19 // ScopedHashTableScope<int, int> Scope2(HT);
20 // HT.insert(0, 42);
21 // }
22 // }
23 //
24 // Looking up the value for "0" in the Scope2 block will return 42. Looking
25 // up the value for 0 before 42 is inserted or after Scope2 is popped will
26 // return 0.
27 //
28 //===----------------------------------------------------------------------===//
29 
30 #ifndef LLVM_ADT_SCOPEDHASHTABLE_H
31 #define LLVM_ADT_SCOPEDHASHTABLE_H
32 
33 #include "llvm/ADT/DenseMap.h"
34 #include "llvm/ADT/DenseMapInfo.h"
36 #include <cassert>
37 #include <new>
38 
39 namespace llvm {
40 
41 template <typename K, typename V, typename KInfo = DenseMapInfo<K>,
42  typename AllocatorTy = MallocAllocator>
44 
45 template <typename K, typename V>
47  ScopedHashTableVal *NextInScope;
48  ScopedHashTableVal *NextForKey;
49  K Key;
50  V Val;
51 
52  ScopedHashTableVal(const K &key, const V &val) : Key(key), Val(val) {}
53 
54 public:
55  const K &getKey() const { return Key; }
56  const V &getValue() const { return Val; }
57  V &getValue() { return Val; }
58 
59  ScopedHashTableVal *getNextForKey() { return NextForKey; }
60  const ScopedHashTableVal *getNextForKey() const { return NextForKey; }
61  ScopedHashTableVal *getNextInScope() { return NextInScope; }
62 
63  template <typename AllocatorTy>
65  ScopedHashTableVal *nextForKey,
66  const K &key, const V &val,
67  AllocatorTy &Allocator) {
68  ScopedHashTableVal *New = Allocator.template Allocate<ScopedHashTableVal>();
69  // Set up the value.
70  new (New) ScopedHashTableVal(key, val);
71  New->NextInScope = nextInScope;
72  New->NextForKey = nextForKey;
73  return New;
74  }
75 
76  template <typename AllocatorTy> void Destroy(AllocatorTy &Allocator) {
77  // Free memory referenced by the item.
78  this->~ScopedHashTableVal();
79  Allocator.Deallocate(this);
80  }
81 };
82 
83 template <typename K, typename V, typename KInfo = DenseMapInfo<K>,
84  typename AllocatorTy = MallocAllocator>
86  /// HT - The hashtable that we are active for.
88 
89  /// PrevScope - This is the scope that we are shadowing in HT.
90  ScopedHashTableScope *PrevScope;
91 
92  /// LastValInScope - This is the last value that was inserted for this scope
93  /// or null if none have been inserted yet.
94  ScopedHashTableVal<K, V> *LastValInScope;
95 
96 public:
101 
102  ScopedHashTableScope *getParentScope() { return PrevScope; }
103  const ScopedHashTableScope *getParentScope() const { return PrevScope; }
104 
105 private:
106  friend class ScopedHashTable<K, V, KInfo, AllocatorTy>;
107 
108  ScopedHashTableVal<K, V> *getLastValInScope() {
109  return LastValInScope;
110  }
111 
112  void setLastValInScope(ScopedHashTableVal<K, V> *Val) {
113  LastValInScope = Val;
114  }
115 };
116 
117 template <typename K, typename V, typename KInfo = DenseMapInfo<K>>
120 
121 public:
123 
124  V &operator*() const {
125  assert(Node && "Dereference end()");
126  return Node->getValue();
127  }
128  V *operator->() const {
129  return &Node->getValue();
130  }
131 
132  bool operator==(const ScopedHashTableIterator &RHS) const {
133  return Node == RHS.Node;
134  }
135  bool operator!=(const ScopedHashTableIterator &RHS) const {
136  return Node != RHS.Node;
137  }
138 
139  inline ScopedHashTableIterator& operator++() { // Preincrement
140  assert(Node && "incrementing past end()");
141  Node = Node->getNextForKey();
142  return *this;
143  }
144  ScopedHashTableIterator operator++(int) { // Postincrement
145  ScopedHashTableIterator tmp = *this; ++*this; return tmp;
146  }
147 };
148 
149 template <typename K, typename V, typename KInfo, typename AllocatorTy>
150 class ScopedHashTable {
151 public:
152  /// ScopeTy - This is a helpful typedef that allows clients to get easy access
153  /// to the name of the scope for this hash table.
155  using size_type = unsigned;
156 
157 private:
158  friend class ScopedHashTableScope<K, V, KInfo, AllocatorTy>;
159 
161 
162  DenseMap<K, ValTy*, KInfo> TopLevelMap;
163  ScopeTy *CurScope = nullptr;
164 
165  AllocatorTy Allocator;
166 
167 public:
168  ScopedHashTable() = default;
169  ScopedHashTable(AllocatorTy A) : Allocator(A) {}
170  ScopedHashTable(const ScopedHashTable &) = delete;
171  ScopedHashTable &operator=(const ScopedHashTable &) = delete;
172 
174  assert(!CurScope && TopLevelMap.empty() && "Scope imbalance!");
175  }
176 
177  /// Access to the allocator.
178  AllocatorTy &getAllocator() { return Allocator; }
179  const AllocatorTy &getAllocator() const { return Allocator; }
180 
181  /// Return 1 if the specified key is in the table, 0 otherwise.
182  size_type count(const K &Key) const {
183  return TopLevelMap.count(Key);
184  }
185 
186  V lookup(const K &Key) const {
187  auto I = TopLevelMap.find(Key);
188  if (I != TopLevelMap.end())
189  return I->second->getValue();
190 
191  return V();
192  }
193 
194  void insert(const K &Key, const V &Val) {
195  insertIntoScope(CurScope, Key, Val);
196  }
197 
199 
200  iterator end() { return iterator(0); }
201 
202  iterator begin(const K &Key) {
204  TopLevelMap.find(Key);
205  if (I == TopLevelMap.end()) return end();
206  return iterator(I->second);
207  }
208 
209  ScopeTy *getCurScope() { return CurScope; }
210  const ScopeTy *getCurScope() const { return CurScope; }
211 
212  /// insertIntoScope - This inserts the specified key/value at the specified
213  /// (possibly not the current) scope. While it is ok to insert into a scope
214  /// that isn't the current one, it isn't ok to insert *underneath* an existing
215  /// value of the specified key.
216  void insertIntoScope(ScopeTy *S, const K &Key, const V &Val) {
217  assert(S && "No scope active!");
218  ScopedHashTableVal<K, V> *&KeyEntry = TopLevelMap[Key];
219  KeyEntry = ValTy::Create(S->getLastValInScope(), KeyEntry, Key, Val,
220  Allocator);
221  S->setLastValInScope(KeyEntry);
222  }
223 };
224 
225 /// ScopedHashTableScope ctor - Install this as the current scope for the hash
226 /// table.
227 template <typename K, typename V, typename KInfo, typename Allocator>
229  ScopedHashTableScope(ScopedHashTable<K, V, KInfo, Allocator> &ht) : HT(ht) {
230  PrevScope = HT.CurScope;
231  HT.CurScope = this;
232  LastValInScope = nullptr;
233 }
234 
235 template <typename K, typename V, typename KInfo, typename Allocator>
237  assert(HT.CurScope == this && "Scope imbalance!");
238  HT.CurScope = PrevScope;
239 
240  // Pop and delete all values corresponding to this scope.
241  while (ScopedHashTableVal<K, V> *ThisEntry = LastValInScope) {
242  // Pop this value out of the TopLevelMap.
243  if (!ThisEntry->getNextForKey()) {
244  assert(HT.TopLevelMap[ThisEntry->getKey()] == ThisEntry &&
245  "Scope imbalance!");
246  HT.TopLevelMap.erase(ThisEntry->getKey());
247  } else {
248  ScopedHashTableVal<K, V> *&KeyEntry = HT.TopLevelMap[ThisEntry->getKey()];
249  assert(KeyEntry == ThisEntry && "Scope imbalance!");
250  KeyEntry = ThisEntry->getNextForKey();
251  }
252 
253  // Pop this value out of the scope.
254  LastValInScope = ThisEntry->getNextInScope();
255 
256  // Delete this entry.
257  ThisEntry->Destroy(HT.getAllocator());
258  }
259 }
260 
261 } // end namespace llvm
262 
263 #endif // LLVM_ADT_SCOPEDHASHTABLE_H
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
llvm::ScopedHashTableVal::getValue
V & getValue()
Definition: ScopedHashTable.h:57
llvm::ScopedHashTableVal
Definition: ScopedHashTable.h:46
llvm::ScopedHashTableScope::getParentScope
ScopedHashTableScope * getParentScope()
Definition: ScopedHashTable.h:102
llvm::ScopedHashTable::begin
iterator begin(const K &Key)
Definition: ScopedHashTable.h:202
llvm::ScopedHashTableIterator::ScopedHashTableIterator
ScopedHashTableIterator(ScopedHashTableVal< K, V > *node)
Definition: ScopedHashTable.h:122
llvm::ScopedHashTableVal::getValue
const V & getValue() const
Definition: ScopedHashTable.h:56
llvm::ScopedHashTable::~ScopedHashTable
~ScopedHashTable()
Definition: ScopedHashTable.h:173
llvm::DenseMapIterator
Definition: DenseMap.h:56
DenseMap.h
llvm::ScopedHashTableIterator
Definition: ScopedHashTable.h:118
llvm::ScopedHashTableVal::getKey
const K & getKey() const
Definition: ScopedHashTable.h:55
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::count
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:145
llvm::ScopedHashTableScope::operator=
ScopedHashTableScope & operator=(ScopedHashTableScope &)=delete
llvm::ScopedHashTable::lookup
V lookup(const K &Key) const
Definition: ScopedHashTable.h:186
llvm::ScopedHashTableScope
Definition: ScopedHashTable.h:85
tmp
alloca< 16 x float >, align 16 %tmp2=alloca< 16 x float >, align 16 store< 16 x float > %A,< 16 x float > *%tmp %s=bitcast< 16 x float > *%tmp to i8 *%s2=bitcast< 16 x float > *%tmp2 to i8 *call void @llvm.memcpy.i64(i8 *%s, i8 *%s2, i64 64, i32 16) %R=load< 16 x float > *%tmp2 ret< 16 x float > %R } declare void @llvm.memcpy.i64(i8 *nocapture, i8 *nocapture, i64, i32) nounwind which compiles to:_foo:subl $140, %esp movaps %xmm3, 112(%esp) movaps %xmm2, 96(%esp) movaps %xmm1, 80(%esp) movaps %xmm0, 64(%esp) movl 60(%esp), %eax movl %eax, 124(%esp) movl 56(%esp), %eax movl %eax, 120(%esp) movl 52(%esp), %eax< many many more 32-bit copies > movaps(%esp), %xmm0 movaps 16(%esp), %xmm1 movaps 32(%esp), %xmm2 movaps 48(%esp), %xmm3 addl $140, %esp ret On Nehalem, it may even be cheaper to just use movups when unaligned than to fall back to lower-granularity chunks. Implement processor-specific optimizations for parity with GCC on these processors. GCC does two optimizations:1. ix86_pad_returns inserts a noop before ret instructions if immediately preceded by a conditional branch or is the target of a jump. 2. ix86_avoid_jump_misspredicts inserts noops in cases where a 16-byte block of code contains more than 3 branches. The first one is done for all AMDs, Core2, and "Generic" The second one is done for:Atom, Pentium Pro, all AMDs, Pentium 4, Nocona, Core 2, and "Generic" Testcase:int x(int a) { return(a &0xf0)> >4 tmp
Definition: README.txt:1347
llvm::ScopedHashTable::insert
void insert(const K &Key, const V &Val)
Definition: ScopedHashTable.h:194
llvm::ScopedHashTableScope::ScopedHashTableScope
ScopedHashTableScope(ScopedHashTable< K, V, KInfo, AllocatorTy > &HT)
llvm::AMDGPU::PALMD::Key
Key
PAL metadata keys.
Definition: AMDGPUMetadata.h:481
llvm::ScopedHashTable::getAllocator
AllocatorTy & getAllocator()
Access to the allocator.
Definition: ScopedHashTable.h:178
llvm::ScopedHashTable::getCurScope
const ScopeTy * getCurScope() const
Definition: ScopedHashTable.h:210
llvm::ScopedHashTableIterator::operator++
ScopedHashTableIterator & operator++()
Definition: ScopedHashTable.h:139
AllocatorBase.h
llvm::ScopedHashTable
Definition: ScopedHashTable.h:43
val
The initial backend is deliberately restricted to z10 We should add support for later architectures at some point If an asm ties an i32 r result to an i64 the input will be treated as an leaving the upper bits uninitialised For i64 store i32 val
Definition: README.txt:15
llvm::ScopedHashTableVal::getNextInScope
ScopedHashTableVal * getNextInScope()
Definition: ScopedHashTable.h:61
llvm::ScopedHashTable::iterator
ScopedHashTableIterator< K, V, KInfo > iterator
Definition: ScopedHashTable.h:198
llvm::ScopedHashTable::count
size_type count(const K &Key) const
Return 1 if the specified key is in the table, 0 otherwise.
Definition: ScopedHashTable.h:182
llvm::DenseMap
Definition: DenseMap.h:714
llvm::ScopedHashTableIterator::operator!=
bool operator!=(const ScopedHashTableIterator &RHS) const
Definition: ScopedHashTable.h:135
I
#define I(x, y, z)
Definition: MD5.cpp:59
node
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper node
Definition: README-SSE.txt:406
llvm::ScopedHashTable::operator=
ScopedHashTable & operator=(const ScopedHashTable &)=delete
llvm::ScopedHashTable::getCurScope
ScopeTy * getCurScope()
Definition: ScopedHashTable.h:209
llvm::ScopedHashTableIterator::operator->
V * operator->() const
Definition: ScopedHashTable.h:128
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
llvm::ScopedHashTable::insertIntoScope
void insertIntoScope(ScopeTy *S, const K &Key, const V &Val)
insertIntoScope - This inserts the specified key/value at the specified (possibly not the current) sc...
Definition: ScopedHashTable.h:216
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::ScopedHashTableVal::getNextForKey
ScopedHashTableVal * getNextForKey()
Definition: ScopedHashTable.h:59
llvm::ScopedHashTableVal::Destroy
void Destroy(AllocatorTy &Allocator)
Definition: ScopedHashTable.h:76
A
* A
Definition: README_ALTIVEC.txt:89
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
Node
Definition: ItaniumDemangle.h:235
llvm::ScopedHashTableScope::~ScopedHashTableScope
~ScopedHashTableScope()
Definition: ScopedHashTable.h:236
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::empty
LLVM_NODISCARD bool empty() const
Definition: DenseMap.h:97
llvm::ScopedHashTableScope::getParentScope
const ScopedHashTableScope * getParentScope() const
Definition: ScopedHashTable.h:103
llvm::ScopedHashTable::ScopedHashTable
ScopedHashTable(AllocatorTy A)
Definition: ScopedHashTable.h:169
llvm::ScopedHashTableIterator::operator==
bool operator==(const ScopedHashTableIterator &RHS) const
Definition: ScopedHashTable.h:132
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:83
llvm::ScopedHashTableVal::Create
static ScopedHashTableVal * Create(ScopedHashTableVal *nextInScope, ScopedHashTableVal *nextForKey, const K &key, const V &val, AllocatorTy &Allocator)
Definition: ScopedHashTable.h:64
llvm::ScopedHashTable::getAllocator
const AllocatorTy & getAllocator() const
Definition: ScopedHashTable.h:179
Allocator
Basic Register Allocator
Definition: RegAllocBasic.cpp:146
llvm::ScopedHashTableIterator::operator++
ScopedHashTableIterator operator++(int)
Definition: ScopedHashTable.h:144
llvm::ScopedHashTable::ScopedHashTable
ScopedHashTable()=default
DenseMapInfo.h
llvm::ScopedHashTable::end
iterator end()
Definition: ScopedHashTable.h:200
llvm::ScopedHashTableIterator::operator*
V & operator*() const
Definition: ScopedHashTable.h:124
llvm::ScopedHashTableVal::getNextForKey
const ScopedHashTableVal * getNextForKey() const
Definition: ScopedHashTable.h:60
llvm::ScopedHashTable< K, V, DenseMapInfo< K >, MallocAllocator >::size_type
unsigned size_type
Definition: ScopedHashTable.h:155