LLVM  16.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 
133  return Node == RHS.Node;
134  }
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 : detail::AllocatorHolder<AllocatorTy> {
151  using AllocTy = detail::AllocatorHolder<AllocatorTy>;
152 
153 public:
154  /// ScopeTy - This is a helpful typedef that allows clients to get easy access
155  /// to the name of the scope for this hash table.
157  using size_type = unsigned;
158 
159 private:
160  friend class ScopedHashTableScope<K, V, KInfo, AllocatorTy>;
161 
163 
164  DenseMap<K, ValTy*, KInfo> TopLevelMap;
165  ScopeTy *CurScope = nullptr;
166 
167 public:
168  ScopedHashTable() = default;
169  ScopedHashTable(AllocatorTy A) : AllocTy(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  using AllocTy::getAllocator;
179 
180  /// Return 1 if the specified key is in the table, 0 otherwise.
181  size_type count(const K &Key) const {
182  return TopLevelMap.count(Key);
183  }
184 
185  V lookup(const K &Key) const {
186  auto I = TopLevelMap.find(Key);
187  if (I != TopLevelMap.end())
188  return I->second->getValue();
189 
190  return V();
191  }
192 
193  void insert(const K &Key, const V &Val) {
194  insertIntoScope(CurScope, Key, Val);
195  }
196 
198 
199  iterator end() { return iterator(nullptr); }
200 
201  iterator begin(const K &Key) {
203  TopLevelMap.find(Key);
204  if (I == TopLevelMap.end()) return end();
205  return iterator(I->second);
206  }
207 
208  ScopeTy *getCurScope() { return CurScope; }
209  const ScopeTy *getCurScope() const { return CurScope; }
210 
211  /// insertIntoScope - This inserts the specified key/value at the specified
212  /// (possibly not the current) scope. While it is ok to insert into a scope
213  /// that isn't the current one, it isn't ok to insert *underneath* an existing
214  /// value of the specified key.
215  void insertIntoScope(ScopeTy *S, const K &Key, const V &Val) {
216  assert(S && "No scope active!");
217  ScopedHashTableVal<K, V> *&KeyEntry = TopLevelMap[Key];
218  KeyEntry = ValTy::Create(S->getLastValInScope(), KeyEntry, Key, Val,
219  getAllocator());
220  S->setLastValInScope(KeyEntry);
221  }
222 };
223 
224 /// ScopedHashTableScope ctor - Install this as the current scope for the hash
225 /// table.
226 template <typename K, typename V, typename KInfo, typename Allocator>
228  ScopedHashTableScope(ScopedHashTable<K, V, KInfo, Allocator> &ht) : HT(ht) {
229  PrevScope = HT.CurScope;
230  HT.CurScope = this;
231  LastValInScope = nullptr;
232 }
233 
234 template <typename K, typename V, typename KInfo, typename Allocator>
236  assert(HT.CurScope == this && "Scope imbalance!");
237  HT.CurScope = PrevScope;
238 
239  // Pop and delete all values corresponding to this scope.
240  while (ScopedHashTableVal<K, V> *ThisEntry = LastValInScope) {
241  // Pop this value out of the TopLevelMap.
242  if (!ThisEntry->getNextForKey()) {
243  assert(HT.TopLevelMap[ThisEntry->getKey()] == ThisEntry &&
244  "Scope imbalance!");
245  HT.TopLevelMap.erase(ThisEntry->getKey());
246  } else {
247  ScopedHashTableVal<K, V> *&KeyEntry = HT.TopLevelMap[ThisEntry->getKey()];
248  assert(KeyEntry == ThisEntry && "Scope imbalance!");
249  KeyEntry = ThisEntry->getNextForKey();
250  }
251 
252  // Pop this value out of the scope.
253  LastValInScope = ThisEntry->getNextInScope();
254 
255  // Delete this entry.
256  ThisEntry->Destroy(HT.getAllocator());
257  }
258 }
259 
260 } // end namespace llvm
261 
262 #endif // LLVM_ADT_SCOPEDHASHTABLE_H
llvm::detail::AllocatorHolder< MallocAllocator >
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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:201
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::detail::AllocatorHolder::getAllocator
Alloc & getAllocator()
Definition: AllocatorBase.h:109
llvm::DenseMapIterator
Definition: DenseMap.h:57
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:185
llvm::ScopedHashTableScope
Definition: ScopedHashTable.h:85
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
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:193
llvm::ScopedHashTableScope::ScopedHashTableScope
ScopedHashTableScope(ScopedHashTable< K, V, KInfo, AllocatorTy > &HT)
llvm::AMDGPU::PALMD::Key
Key
PAL metadata keys.
Definition: AMDGPUMetadata.h:486
llvm::ScopedHashTable::getCurScope
const ScopeTy * getCurScope() const
Definition: ScopedHashTable.h:209
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:197
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:181
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:58
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:208
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:215
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::ScopedHashTableVal::getNextForKey
ScopedHashTableVal * getNextForKey()
Definition: ScopedHashTable.h:59
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::empty
bool empty() const
Definition: DenseMap.h:98
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:156
llvm::ScopedHashTableScope::~ScopedHashTableScope
~ScopedHashTableScope()
Definition: ScopedHashTable.h:235
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:84
llvm::ScopedHashTableVal::Create
static ScopedHashTableVal * Create(ScopedHashTableVal *nextInScope, ScopedHashTableVal *nextForKey, const K &key, const V &val, AllocatorTy &Allocator)
Definition: ScopedHashTable.h:64
Allocator
Basic Register Allocator
Definition: RegAllocBasic.cpp:143
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:199
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:157