1//===- StorageUniquer.cpp - Common Storage Class Uniquer ------------------===//
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#include "mlir/Support/StorageUniquer.h"
10
11#include "mlir/Support/LLVM.h"
12#include "mlir/Support/ThreadLocalCache.h"
13#include "mlir/Support/TypeID.h"
14#include "llvm/Support/RWMutex.h"
15
16using namespace mlir;
17using namespace mlir::detail;
18
19namespace {
20/// This class represents a uniquer for storage instances of a specific type
21/// that has parametric storage. It contains all of the necessary data to unique
22/// storage instances in a thread safe way. This allows for the main uniquer to
23/// bucket each of the individual sub-types removing the need to lock the main
24/// uniquer itself.
25class ParametricStorageUniquer {
26public:
27 using BaseStorage = StorageUniquer::BaseStorage;
28 using StorageAllocator = StorageUniquer::StorageAllocator;
29
30 /// A lookup key for derived instances of storage objects.
31 struct LookupKey {
32 /// The known hash value of the key.
33 unsigned hashValue;
34
35 /// An equality function for comparing with an existing storage instance.
36 function_ref<bool(const BaseStorage *)> isEqual;
37 };
38
39private:
40 /// A utility wrapper object representing a hashed storage object. This class
41 /// contains a storage object and an existing computed hash value.
42 struct HashedStorage {
43 HashedStorage(unsigned hashValue = 0, BaseStorage *storage = nullptr)
44 : hashValue(hashValue), storage(storage) {}
45 unsigned hashValue;
46 BaseStorage *storage;
47 };
48
49 /// Storage info for derived TypeStorage objects.
50 struct StorageKeyInfo {
51 static inline unsigned getHashValue(const HashedStorage &key) {
52 return key.hashValue;
53 }
54 static inline unsigned getHashValue(const LookupKey &key) {
55 return key.hashValue;
56 }
57
58 static inline bool isEqual(const HashedStorage &lhs,
59 const HashedStorage &rhs) {
60 return lhs.storage == rhs.storage;
61 }
62 static inline bool isEqual(const LookupKey &lhs, const HashedStorage &rhs) {
63 // Invoke the equality function on the lookup key.
64 return lhs.isEqual(rhs.storage);
65 }
66 };
67 using StorageTypeSet = DenseSet<HashedStorage, StorageKeyInfo>;
68
69 /// This class represents a single shard of the uniquer. The uniquer uses a
70 /// set of shards to allow for multiple threads to create instances with less
71 /// lock contention.
72 struct Shard {
73 /// The set containing the allocated storage instances in the base layer.
74 StorageTypeSet instances;
75
76 /// The set containing the allocated storage instances in the transient
77 /// layer, lazily instantiated on the first transient allocation.
78 std::unique_ptr<StorageTypeSet> transientInstances;
79
80#if LLVM_ENABLE_THREADS != 0
81 /// A mutex to keep uniquing thread-safe.
82 llvm::sys::SmartRWMutex<true> mutex;
83#endif
84 };
85
86 /// Get or create an instance of a param derived type in an thread-unsafe
87 /// fashion.
88 BaseStorage *getOrCreateUnsafe(Shard &shard, LookupKey &key,
89 function_ref<BaseStorage *()> ctorFn) {
90 if (isInTransientScope()) {
91 // If we are in a transient scope, then it means we had a base context
92 // which was frozen at some point and are busy mutating in a transient
93 // overlay state. Check to see if the instance is in either of these
94 // first before creating. The expectation is that the base state is
95 // rather minimal and most of the entries are in the transient, so
96 // search in transient instances first before base, and if neither
97 // create a transient instance.
98 if (shard.transientInstances) {
99 auto transientIt = shard.transientInstances->find_as(Val: key);
100 if (transientIt != shard.transientInstances->end())
101 return transientIt->storage;
102 }
103 auto baseIt = shard.instances.find_as(Val: key);
104 if (baseIt != shard.instances.end())
105 return baseIt->storage;
106 if (!shard.transientInstances)
107 shard.transientInstances = std::make_unique<StorageTypeSet>();
108 auto existing = shard.transientInstances->insert_as(V: {key.hashValue}, LookupKey: key);
109 BaseStorage *&storage = existing.first->storage;
110 if (existing.second)
111 storage = ctorFn();
112 return storage;
113 }
114
115 auto existing = shard.instances.insert_as(V: {key.hashValue}, LookupKey: key);
116 BaseStorage *&storage = existing.first->storage;
117 if (existing.second)
118 storage = ctorFn();
119 return storage;
120 }
121
122 /// Destroy all of the storage instances within the given shard.
123 void destroyShardInstances(Shard &shard) {
124 if (!destructorFn)
125 return;
126 for (HashedStorage &instance : shard.instances)
127 destructorFn(instance.storage);
128 if (shard.transientInstances) {
129 for (HashedStorage &instance : *shard.transientInstances)
130 destructorFn(instance.storage);
131 }
132 }
133
134public:
135#if LLVM_ENABLE_THREADS != 0
136 /// Initialize the storage uniquer with a given number of storage shards to
137 /// use. The provided shard number is required to be a valid power of 2. The
138 /// destructor function is used to destroy any allocated storage instances.
139 ParametricStorageUniquer(function_ref<void(BaseStorage *)> destructorFn,
140 size_t numShards = 8)
141 : shards(new std::atomic<Shard *>[numShards]),
142 destructorFn(destructorFn) {
143 assert(llvm::isPowerOf2_64(numShards) &&
144 "the number of shards is required to be a power of 2");
145 this->numShards = numShards;
146 this->inTransientScope = false;
147 for (size_t i = 0; i < numShards; i++)
148 shards[i].store(p: nullptr, m: std::memory_order_relaxed);
149 }
150 ~ParametricStorageUniquer() {
151 // Free all of the allocated shards.
152 for (size_t i = 0; i != numShards; ++i) {
153 if (Shard *shard = shards[i].load()) {
154 destroyShardInstances(shard&: *shard);
155 delete shard;
156 }
157 }
158 }
159 /// Get or create an instance of a parametric type.
160 BaseStorage *getOrCreate(bool threadingIsEnabled, unsigned hashValue,
161 function_ref<bool(const BaseStorage *)> isEqual,
162 function_ref<BaseStorage *()> ctorFn) {
163 Shard &shard = getShard(hashValue);
164 ParametricStorageUniquer::LookupKey lookupKey{.hashValue: hashValue, .isEqual: isEqual};
165 if (!threadingIsEnabled)
166 return getOrCreateUnsafe(shard, key&: lookupKey, ctorFn);
167
168 // Check for a instance of this object in the local cache.
169 auto localIt = localCache->insert_as(V: {hashValue}, LookupKey: lookupKey);
170 BaseStorage *&localInst = localIt.first->storage;
171 if (localInst)
172 return localInst;
173
174 // Check for an existing instance in read-only mode.
175 {
176 llvm::sys::SmartScopedReader<true> typeLock(shard.mutex);
177 if (isInTransientScope() && shard.transientInstances) {
178 auto it = shard.transientInstances->find_as(Val: lookupKey);
179 if (it != shard.transientInstances->end())
180 return localInst = it->storage;
181 }
182 auto it = shard.instances.find_as(Val: lookupKey);
183 if (it != shard.instances.end())
184 return localInst = it->storage;
185 }
186
187 // Acquire a writer-lock so that we can safely create the new storage
188 // instance.
189 llvm::sys::SmartScopedWriter<true> typeLock(shard.mutex);
190 return localInst = getOrCreateUnsafe(shard, key&: lookupKey, ctorFn);
191 }
192
193 /// Run a mutation function on the provided storage object in a thread-safe
194 /// way.
195 LogicalResult mutate(bool threadingIsEnabled, BaseStorage *storage,
196 function_ref<LogicalResult()> mutationFn) {
197 if (!threadingIsEnabled)
198 return mutationFn();
199
200 // Get a shard to use for mutating this storage instance. It doesn't need to
201 // be the same shard as the original allocation, but does need to be
202 // deterministic.
203 Shard &shard = getShard(hashValue: llvm::hash_value(ptr: storage));
204 llvm::sys::SmartScopedWriter<true> lock(shard.mutex);
205 return mutationFn();
206 }
207
208 void beginTransientScope() {
209 assert(!isInTransientScope() &&
210 "parametric storage uniquer is already in a transient scope");
211 inTransientScope = true;
212 }
213
214 void endTransientScope() {
215 assert(isInTransientScope() &&
216 "parametric storage uniquer is not in a transient scope");
217 if (!isInTransientScope())
218 return;
219
220 for (size_t i = 0; i != numShards; ++i) {
221 if (Shard *shard = shards[i].load()) {
222 llvm::sys::SmartScopedWriter<true> typeLock(shard->mutex);
223 if (shard->transientInstances) {
224 if (destructorFn) {
225 for (HashedStorage &instance : *shard->transientInstances)
226 destructorFn(instance.storage);
227 }
228 shard->transientInstances.reset();
229 }
230 }
231 }
232 localCache.clear();
233 inTransientScope = false;
234 }
235
236 bool isInTransientScope() const { return inTransientScope; }
237
238 size_t getNumShards() const { return numShards; }
239
240private:
241 /// Return the shard used for the given hash value.
242 Shard &getShard(unsigned hashValue) {
243 // Get a shard number from the provided hashvalue.
244 unsigned shardNum = hashValue & (numShards - 1);
245
246 // Try to acquire an already initialized shard.
247 Shard *shard = shards[shardNum].load(m: std::memory_order_acquire);
248 if (shard)
249 return *shard;
250
251 // Otherwise, try to allocate a new shard.
252 Shard *newShard = new Shard();
253 if (shards[shardNum].compare_exchange_strong(p1&: shard, p2: newShard))
254 return *newShard;
255
256 // If one was allocated before we can initialize ours, delete ours.
257 delete newShard;
258 return *shard;
259 }
260
261 /// A thread local cache for storage objects. This helps to reduce the lock
262 /// contention when an object already existing in the cache.
263 ThreadLocalCache<StorageTypeSet> localCache;
264
265 /// A set of uniquer shards to allow for further bucketing accesses for
266 /// instances of this storage type. Each shard is lazily initialized to reduce
267 /// the overhead when only a small amount of shards are in use.
268 std::unique_ptr<std::atomic<Shard *>[]> shards;
269
270 /// The number of available shards.
271 unsigned numShards : 31;
272
273 /// Whether the uniquer is currently in a transient scope.
274 unsigned inTransientScope : 1;
275
276 /// Function to used to destruct any allocated storage instances.
277 function_ref<void(BaseStorage *)> destructorFn;
278
279#else
280 /// If multi-threading is disabled, ignore the shard parameter as we will
281 /// always use one shard. The destructor function is used to destroy any
282 /// allocated storage instances.
283 ParametricStorageUniquer(function_ref<void(BaseStorage *)> destructorFn,
284 size_t numShards = 0)
285 : destructorFn(destructorFn) {}
286 ~ParametricStorageUniquer() { destroyShardInstances(shard); }
287
288 /// Get or create an instance of a parametric type.
289 BaseStorage *
290 getOrCreate(bool threadingIsEnabled, unsigned hashValue,
291 function_ref<bool(const BaseStorage *)> isEqual,
292 function_ref<BaseStorage *()> ctorFn) {
293 ParametricStorageUniquer::LookupKey lookupKey{hashValue, isEqual};
294 return getOrCreateUnsafe(shard, lookupKey, ctorFn);
295 }
296 /// Run a mutation function on the provided storage object in a thread-safe
297 /// way.
298 LogicalResult
299 mutate(bool threadingIsEnabled, BaseStorage *storage,
300 function_ref<LogicalResult()> mutationFn) {
301 return mutationFn();
302 }
303
304 void beginTransientScope() {
305 assert(!inTransientScope &&
306 "parametric storage uniquer is already in a transient scope");
307 inTransientScope = true;
308 }
309
310 void endTransientScope() {
311 assert(inTransientScope &&
312 "parametric storage uniquer is not in a transient scope");
313 if (!inTransientScope)
314 return;
315 if (shard.transientInstances) {
316 if (destructorFn) {
317 for (HashedStorage &instance : *shard.transientInstances)
318 destructorFn(instance.storage);
319 }
320 shard.transientInstances.reset();
321 }
322 inTransientScope = false;
323 }
324
325 bool isInTransientScope() const { return inTransientScope; }
326
327private:
328 /// The main uniquer shard that is used for allocating storage instances.
329 Shard shard;
330
331 /// Function to used to destruct any allocated storage instances.
332 function_ref<void(BaseStorage *)> destructorFn;
333
334 /// Flag indicating if the uniquer is currently in a transient scope.
335 bool inTransientScope = false;
336#endif
337};
338} // namespace
339
340namespace mlir {
341namespace detail {
342/// This is the implementation of the StorageUniquer class.
343struct StorageUniquerImpl {
344 using BaseStorage = StorageUniquer::BaseStorage;
345 using StorageAllocator = StorageUniquer::StorageAllocator;
346
347 /// Bundled state dynamically allocated when entering a transient scope.
348 struct TransientState {
349#if LLVM_ENABLE_THREADS != 0
350 /// Transient thread local set of allocators used when in a transient scope.
351 ThreadLocalCache<StorageAllocator *> threadSafeAllocator;
352
353 /// Transient allocators created during transient scope.
354 std::vector<std::unique_ptr<StorageAllocator>> threadAllocators;
355
356 /// A mutex used for safely adding a new transient thread allocator.
357 llvm::sys::SmartMutex<true> threadAllocatorMutex;
358#endif
359
360 /// Single-threaded allocator used during transient scope.
361 std::unique_ptr<StorageAllocator> allocator;
362
363 /// Transient singleton instances registered during transient scope.
364 DenseMap<TypeID, BaseStorage *> singletonInstances;
365 };
366
367 //===--------------------------------------------------------------------===//
368 // Parametric Storage
369 //===--------------------------------------------------------------------===//
370
371 /// Check if an instance of a parametric storage class exists.
372 bool hasParametricStorage(TypeID id) { return parametricUniquers.count(Val: id); }
373
374 /// Get or create an instance of a parametric type.
375 BaseStorage *
376 getOrCreate(TypeID id, unsigned hashValue,
377 function_ref<bool(const BaseStorage *)> isEqual,
378 function_ref<BaseStorage *(StorageAllocator &)> ctorFn) {
379 assert(parametricUniquers.count(id) &&
380 "creating unregistered storage instance");
381 ParametricStorageUniquer &storageUniquer = *parametricUniquers[id];
382 return storageUniquer.getOrCreate(
383 threadingIsEnabled, hashValue, isEqual,
384 ctorFn: [&] { return ctorFn(getThreadSafeAllocator()); });
385 }
386
387 /// Run a mutation function on the provided storage object in a thread-safe
388 /// way.
389 LogicalResult
390 mutate(TypeID id, BaseStorage *storage,
391 function_ref<LogicalResult(StorageAllocator &)> mutationFn) {
392 assert(parametricUniquers.count(id) &&
393 "mutating unregistered storage instance");
394 ParametricStorageUniquer &storageUniquer = *parametricUniquers[id];
395 return storageUniquer.mutate(threadingIsEnabled, storage, mutationFn: [&] {
396 return mutationFn(getThreadSafeAllocator());
397 });
398 }
399
400 /// Return an allocator that can be used to safely allocate instances on the
401 /// current thread.
402 StorageAllocator &getThreadSafeAllocator() {
403#if LLVM_ENABLE_THREADS != 0
404 if (!threadingIsEnabled) {
405 if (transientState) {
406 if (!transientState->allocator)
407 transientState->allocator = std::make_unique<StorageAllocator>();
408 return *transientState->allocator;
409 }
410 return allocator;
411 }
412
413 if (transientState) {
414 StorageAllocator *&threadAllocator =
415 transientState->threadSafeAllocator.get();
416 if (!threadAllocator) {
417 threadAllocator = new StorageAllocator();
418 llvm::sys::SmartScopedLock<true> lock(
419 transientState->threadAllocatorMutex);
420 transientState->threadAllocators.push_back(
421 x: std::unique_ptr<StorageAllocator>(threadAllocator));
422 }
423 return *threadAllocator;
424 }
425
426 // If the allocator has not been initialized, create a new one.
427 StorageAllocator *&threadAllocator = threadSafeAllocator.get();
428 if (!threadAllocator) {
429 threadAllocator = new StorageAllocator();
430
431 // Record this allocator, given that we don't want it to be destroyed when
432 // the thread dies.
433 llvm::sys::SmartScopedLock<true> lock(threadAllocatorMutex);
434 threadAllocators.push_back(
435 x: std::unique_ptr<StorageAllocator>(threadAllocator));
436 }
437
438 return *threadAllocator;
439#else
440 if (transientState) {
441 if (!transientState->allocator)
442 transientState->allocator = std::make_unique<StorageAllocator>();
443 return *transientState->allocator;
444 }
445 return allocator;
446#endif
447 }
448
449 void beginTransientScope() {
450 assert(!transientState &&
451 "storage uniquer is already in a transient scope");
452 transientState = std::make_unique<TransientState>();
453 for (auto &entry : parametricUniquers)
454 entry.second->beginTransientScope();
455 }
456
457 void endTransientScope() {
458 assert(transientState && "storage uniquer is not in a transient scope");
459 if (!transientState)
460 return;
461 for (auto &entry : parametricUniquers)
462 entry.second->endTransientScope();
463 transientState.reset();
464 }
465
466 bool isInTransientScope() const { return transientState != nullptr; }
467
468 //===--------------------------------------------------------------------===//
469 // Singleton Storage
470 //===--------------------------------------------------------------------===//
471
472 /// Get or create an instance of a singleton storage class.
473 BaseStorage *getSingleton(TypeID id) {
474 if (transientState) {
475 auto it = transientState->singletonInstances.find(Val: id);
476 if (it != transientState->singletonInstances.end())
477 return it->second;
478 }
479 BaseStorage *singletonInstance = singletonInstances[id];
480 assert(singletonInstance && "expected singleton instance to exist");
481 return singletonInstance;
482 }
483
484 /// Check if an instance of a singleton storage class exists.
485 bool hasSingleton(TypeID id) const {
486 if (transientState && transientState->singletonInstances.count(Val: id))
487 return true;
488 return singletonInstances.count(Val: id);
489 }
490
491 //===--------------------------------------------------------------------===//
492 // Instance Storage
493 //===--------------------------------------------------------------------===//
494
495#if LLVM_ENABLE_THREADS != 0
496 /// A thread local set of allocators used for uniquing parametric instances,
497 /// or other data allocated in thread volatile situations.
498 ThreadLocalCache<StorageAllocator *> threadSafeAllocator;
499
500 /// All of the allocators that have been created for thread based allocation.
501 std::vector<std::unique_ptr<StorageAllocator>> threadAllocators;
502
503 /// A mutex used for safely adding a new thread allocator.
504 llvm::sys::SmartMutex<true> threadAllocatorMutex;
505#endif
506
507 /// Main allocator used for uniquing singleton instances, and other state when
508 /// thread safety is guaranteed.
509 StorageAllocator allocator;
510
511 /// Transient state bundled into a unique pointer (nullptr when inactive).
512 std::unique_ptr<TransientState> transientState;
513
514 /// Map of type ids to the storage uniquer to use for registered objects.
515 DenseMap<TypeID, std::unique_ptr<ParametricStorageUniquer>>
516 parametricUniquers;
517
518 /// Map of type ids to a singleton instance when the storage class is a
519 /// singleton.
520 DenseMap<TypeID, BaseStorage *> singletonInstances;
521
522 /// Flag specifying if multi-threading is enabled within the uniquer.
523 bool threadingIsEnabled = true;
524};
525} // namespace detail
526} // namespace mlir
527
528StorageUniquer::StorageUniquer() : impl(new StorageUniquerImpl()) {}
529StorageUniquer::~StorageUniquer() = default;
530
531/// Set whether thread-safe locking is enabled within the uniquer.
532void StorageUniquer::setThreadSafeLocking(bool enable) {
533 impl->threadingIsEnabled = enable;
534}
535
536void StorageUniquer::beginTransientScope() { impl->beginTransientScope(); }
537
538void StorageUniquer::endTransientScope() { impl->endTransientScope(); }
539
540bool StorageUniquer::isInTransientScope() const {
541 return impl->isInTransientScope();
542}
543
544/// Implementation for getting/creating an instance of a derived type with
545/// parametric storage.
546auto StorageUniquer::getParametricStorageTypeImpl(
547 TypeID id, unsigned hashValue,
548 function_ref<bool(const BaseStorage *)> isEqual,
549 function_ref<BaseStorage *(StorageAllocator &)> ctorFn) -> BaseStorage * {
550 return impl->getOrCreate(id, hashValue, isEqual, ctorFn);
551}
552
553/// Implementation for registering an instance of a derived type with
554/// parametric storage.
555void StorageUniquer::registerParametricStorageTypeImpl(
556 TypeID id, function_ref<void(BaseStorage *)> destructorFn) {
557 auto uniquer = std::make_unique<ParametricStorageUniquer>(args&: destructorFn);
558 if (impl->isInTransientScope())
559 uniquer->beginTransientScope();
560 impl->parametricUniquers.try_emplace(Key: id, Args: std::move(uniquer));
561}
562
563/// Implementation for getting an instance of a derived type with default
564/// storage.
565auto StorageUniquer::getSingletonImpl(TypeID id) -> BaseStorage * {
566 return impl->getSingleton(id);
567}
568
569/// Test is the storage singleton is initialized.
570bool StorageUniquer::isSingletonStorageInitialized(TypeID id) {
571 return impl->hasSingleton(id);
572}
573
574/// Test is the parametric storage is initialized.
575bool StorageUniquer::isParametricStorageInitialized(TypeID id) {
576 return impl->hasParametricStorage(id);
577}
578
579/// Implementation for registering an instance of a derived type with default
580/// storage.
581void StorageUniquer::registerSingletonImpl(
582 TypeID id, function_ref<BaseStorage *(StorageAllocator &)> ctorFn) {
583 if (impl->transientState) {
584 assert(!impl->transientState->singletonInstances.count(id) &&
585 !impl->singletonInstances.count(id) &&
586 "storage class already registered");
587 impl->transientState->singletonInstances.try_emplace(
588 Key: id, Args: ctorFn(impl->getThreadSafeAllocator()));
589 return;
590 }
591 assert(!impl->singletonInstances.count(id) &&
592 "storage class already registered");
593 impl->singletonInstances.try_emplace(Key: id, Args: ctorFn(impl->allocator));
594}
595
596/// Implementation for mutating an instance of a derived storage.
597LogicalResult StorageUniquer::mutateImpl(
598 TypeID id, BaseStorage *storage,
599 function_ref<LogicalResult(StorageAllocator &)> mutationFn) {
600 return impl->mutate(id, storage, mutationFn);
601}
602