25 const bool IsSubtrie =
false;
27 TrieNode(
bool IsSubtrie) : IsSubtrie(IsSubtrie) {}
29 static void *
operator new(
size_t Size) { return ::operator
new(
Size); }
30 void operator delete(
void *
Ptr) { ::operator
delete(
Ptr); }
33struct TrieContent final :
public TrieNode {
38 void *getValuePointer()
const {
39 auto *
Content =
reinterpret_cast<const uint8_t *
>(
this) + ContentOffset;
44 auto *Begin =
reinterpret_cast<const uint8_t *
>(
this) + HashOffset;
45 return ArrayRef(Begin, Begin + HashSize);
48 TrieContent(
size_t ContentOffset,
size_t HashSize,
size_t HashOffset)
49 : TrieNode(
false), ContentOffset(ContentOffset),
50 HashSize(HashSize), HashOffset(HashOffset) {}
52 static bool classof(
const TrieNode *TN) {
return !TN->IsSubtrie; }
55static_assert(
sizeof(TrieContent) ==
57 "Check header assumption!");
59class TrieSubtrie final
66 TrieNode *
load(
size_t I) {
return get(
I).load(); }
68 unsigned size()
const {
return Size; }
71 sink(
size_t I, TrieContent &
Content,
size_t NumSubtrieBits,
size_t NewI,
72 function_ref<TrieSubtrie *(std::unique_ptr<TrieSubtrie>)> Saver);
74 static std::unique_ptr<TrieSubtrie> create(
size_t StartBit,
size_t NumBits);
76 explicit TrieSubtrie(
size_t StartBit,
size_t NumBits);
78 static bool classof(
const TrieNode *TN) {
return TN->IsSubtrie; }
80 static constexpr size_t sizeToAlloc(
unsigned NumBits) {
81 assert(NumBits < 20 &&
"Tries should have fewer than ~1M slots");
82 unsigned Count = 1u << NumBits;
83 return totalSizeToAlloc<LazyAtomicPointer<TrieNode>>(Count);
107 unsigned StartBit = 0;
108 unsigned NumBits = 0;
115 std::atomic<TrieSubtrie *> Next;
119std::unique_ptr<TrieSubtrie> TrieSubtrie::create(
size_t StartBit,
121 void *
Memory = ::operator
new(sizeToAlloc(NumBits));
122 TrieSubtrie *S = ::new (
Memory) TrieSubtrie(StartBit, NumBits);
123 return std::unique_ptr<TrieSubtrie>(S);
126TrieSubtrie::TrieSubtrie(
size_t StartBit,
size_t NumBits)
127 : TrieNode(
true), StartBit(StartBit), NumBits(NumBits),
Size(1u << NumBits),
129 for (
unsigned I = 0;
I <
Size; ++
I)
133 std::is_trivially_destructible<LazyAtomicPointer<TrieNode>>
::value,
134 "Expected no work in destructor for TrieNode");
140TrieSubtrie *TrieSubtrie::sink(
141 size_t I, TrieContent &
Content,
size_t NumSubtrieBits,
size_t NewI,
142 function_ref<TrieSubtrie *(std::unique_ptr<TrieSubtrie>)> Saver) {
145 assert(NumSubtrieBits > 0);
146 std::unique_ptr<TrieSubtrie> S = create(StartBit + NumBits, NumSubtrieBits);
153 TrieNode *ExistingNode = &
Content;
155 if (
get(
I).compare_exchange_strong(ExistingNode, S.get()))
156 return Saver(std::move(S));
160 return cast<TrieSubtrie>(ExistingNode);
167 static std::unique_ptr<ImplType>
create(
size_t StartBit,
size_t NumBits) {
168 size_t Size =
sizeof(
ImplType) + TrieSubtrie::sizeToAlloc(NumBits);
171 return std::unique_ptr<ImplType>(Impl);
177 TrieSubtrie *
save(std::unique_ptr<TrieSubtrie> S) {
178 assert(!S->Next &&
"Expected S to a freshly-constructed leaf");
180 TrieSubtrie *CurrentHead =
nullptr;
185 while (!
getRoot()->Next.compare_exchange_weak(CurrentHead, S.get()))
186 S->Next.exchange(CurrentHead);
195 static void *
operator new(
size_t Size) { return ::operator
new(
Size); }
196 void operator delete(
void *
Ptr) { ::operator
delete(
Ptr); }
206 ImplType(
size_t StartBit,
size_t NumBits) {
207 ::new (
getRoot()) TrieSubtrie(StartBit, NumBits);
213 if (
ImplType *Impl = ImplPtr.load())
223 if (ImplPtr.compare_exchange_strong(ExistingImpl, Impl.get()))
224 return *Impl.release();
227 return *ExistingImpl;
238 TrieSubtrie *S = Impl->
getRoot();
240 size_t Index = IndexGen.next();
241 while (
Index != IndexGen.end()) {
243 TrieNode *Existing = S->get(
Index);
248 if (
auto *ExistingContent = dyn_cast<TrieContent>(Existing))
249 return ExistingContent->getHash() == Hash
253 Index = IndexGen.next();
254 S = cast<TrieSubtrie>(Existing);
256 llvm_unreachable(
"failed to locate the node after consuming all hash bytes");
266 TrieSubtrie *S = Impl.
getRoot();
270 S =
static_cast<TrieSubtrie *
>(Hint.P);
271 Index = IndexGen.hint(Hint.I, Hint.B);
273 Index = IndexGen.next();
276 while (
Index != IndexGen.end()) {
279 bool Generated =
false;
280 TrieNode &Existing = S->get(
Index).loadOrGenerate([&]() {
285 Impl.
ContentAlloc.Allocate(ContentAllocSize, ContentAllocAlign));
286 const uint8_t *HashStorage = Constructor(
Memory + ContentOffset, Hash);
290 TrieContent(ContentOffset, Hash.
size(), HashStorage -
Memory);
291 assert(Hash ==
Content->getHash() &&
"Hash not properly initialized");
296 return PointerBase(cast<TrieContent>(Existing).getValuePointer());
298 if (
auto *ST = dyn_cast<TrieSubtrie>(&Existing)) {
300 Index = IndexGen.next();
305 auto &ExistingContent = cast<TrieContent>(Existing);
306 if (ExistingContent.getHash() == Hash)
307 return PointerBase(ExistingContent.getValuePointer());
310 size_t NextIndex = IndexGen.next();
311 while (NextIndex != IndexGen.end()) {
312 size_t NewIndexForExistingContent =
313 IndexGen.getCollidingBits(ExistingContent.getHash());
314 S = S->sink(
Index, ExistingContent, IndexGen.getNumBits(),
315 NewIndexForExistingContent,
316 [&Impl](std::unique_ptr<TrieSubtrie> S) {
317 return Impl.save(std::move(S));
322 if (NextIndex != NewIndexForExistingContent)
325 NextIndex = IndexGen.next();
328 llvm_unreachable(
"failed to insert the node after consuming all hash bytes");
332 size_t ContentAllocSize,
size_t ContentAllocAlign,
size_t ContentOffset,
333 std::optional<size_t> NumRootBits, std::optional<size_t> NumSubtrieBits)
334 : ContentAllocSize(ContentAllocSize), ContentAllocAlign(ContentAllocAlign),
335 ContentOffset(ContentOffset),
342 assert((!NumRootBits || *NumRootBits < 20) &&
343 "Root should have fewer than ~1M slots");
344 assert((!NumSubtrieBits || *NumSubtrieBits < 10) &&
345 "Subtries should have fewer than ~1K slots");
350 : ContentAllocSize(
RHS.ContentAllocSize),
351 ContentAllocAlign(
RHS.ContentAllocAlign),
352 ContentOffset(
RHS.ContentOffset), NumRootBits(
RHS.NumRootBits),
353 NumSubtrieBits(
RHS.NumSubtrieBits) {
355 ImplPtr =
RHS.ImplPtr.exchange(
nullptr);
359 assert(!ImplPtr.load() &&
"Expected subclass to call destroyImpl()");
364 std::unique_ptr<ImplType> Impl(ImplPtr.exchange(
nullptr));
374 for (TrieSubtrie *Trie = Impl->getRoot(); Trie; Trie = Trie->Next.load())
375 for (
unsigned I = 0;
I < Trie->size(); ++
I)
376 if (
auto *
Content = dyn_cast_or_null<TrieContent>(Trie->load(
I)))
377 Destructor(
Content->getValuePointer());
381 TrieSubtrie *Trie = Impl->getRoot()->Next;
383 TrieSubtrie *Next = Trie->Next.exchange(
nullptr);
399 assert(!
P.isHint() &&
"Not a valid trie");
402 if (
auto *S = dyn_cast<TrieSubtrie>((TrieNode *)
P.P))
409 assert(!
P.isHint() &&
"Not a valid trie");
412 if (
auto *S = dyn_cast<TrieSubtrie>((TrieNode *)
P.P))
419 assert(!
P.isHint() &&
"Not a valid trie");
422 auto *S = dyn_cast<TrieSubtrie>((TrieNode *)
P.P);
426 for (
unsigned I = 0,
E = S->size();
I <
E; ++
I)
434 assert(!
P.isHint() &&
"Not a valid trie");
438 auto *S = dyn_cast<TrieSubtrie>((TrieNode *)
P.P);
439 if (!S || !S->IsSubtrie)
444 TrieSubtrie *Current = S;
445 TrieContent *Node =
nullptr;
447 TrieSubtrie *Next =
nullptr;
449 for (
unsigned I = 0,
E = Current->size();
I <
E; ++
I) {
450 auto *S = Current->load(
I);
454 if (
auto *
Content = dyn_cast<TrieContent>(S))
456 else if (
auto *
Sub = dyn_cast<TrieSubtrie>(S))
469 assert(Node &&
"malformed trie, cannot find TrieContent on leaf node");
475 unsigned StartFullBytes = (S->StartBit + 1) / 8 - 1;
476 SS << toHex(toStringRef(Node->getHash()).
take_front(StartFullBytes),
481 for (
unsigned I = StartFullBytes * 8,
E = S->StartBit;
I <
E; ++
I) {
484 Bits.push_back(
'0' + ((Node->getHash()[
Index] >>
Offset) & 1));
488 SS <<
"[" << Bits <<
"]";
498 for (TrieSubtrie *Trie = Impl->
getRoot(); Trie; Trie = Trie->Next.load())
506 assert(!
P.isHint() &&
"Not a valid trie");
509 auto *S = dyn_cast<TrieSubtrie>((TrieNode *)
P.P);
512 if (
auto *
E = S->Next.load())
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
AMDGPU Mark last scratch load
This file defines the BumpPtrAllocator interface.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Given that RA is a live value
static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT, const Loop *CurLoop, ICFLoopSafetyInfo *SafetyInfo, MemorySSAUpdater &MSSAU, OptimizationRemarkEmitter *ORE)
When an instruction is found to only be used outside of the loop, this function moves it to the exit ...
This header defines support for implementing classes that have some trailing object (or arrays of obj...
TrieSubtrie * save(std::unique_ptr< TrieSubtrie > S)
static std::unique_ptr< ImplType > create(size_t StartBit, size_t NumBits)
ThreadSafeAllocator< BumpPtrAllocator > ContentAlloc
FIXME: This should take a function that allocates and constructs the content lazily (taking the hash ...
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
size_t size() const
size - Get the array size.
bool empty() const
empty - Check if the array is empty.
Atomic pointer that's lock-free, but that can coordinate concurrent writes from a lazy generator.
StringRef take_front(size_t N=1) const
Return a StringRef equal to 'this' but with only the first N elements remaining.
Thread-safe allocator adaptor.
TrieRawHashMap - is a lock-free thread-safe trie that is can be used to store/index data based on a h...
LLVM_ABI PointerBase getNextTrie(PointerBase P) const
LLVM_ABI unsigned getNumTries() const
LLVM_ABI unsigned getNumBits(PointerBase P) const
LLVM_ABI unsigned getNumSlotUsed(PointerBase P) const
LLVM_ABI ~ThreadSafeTrieRawHashMapBase()
Destructor, which asserts if there's anything to do.
LLVM_ABI void destroyImpl(function_ref< void(void *ValueMem)> Destructor)
static constexpr size_t DefaultNumSubtrieBits
ThreadSafeTrieRawHashMapBase()=delete
LLVM_ABI PointerBase find(ArrayRef< uint8_t > Hash) const
Find the stored content with hash.
LLVM_ABI PointerBase getRoot() const
LLVM_ABI PointerBase insert(PointerBase Hint, ArrayRef< uint8_t > Hash, function_ref< const uint8_t *(void *Mem, ArrayRef< uint8_t > Hash)> Constructor)
Insert and return the stored content.
LLVM_ABI unsigned getStartBit(PointerBase P) const
LLVM_ABI std::string getTriePrefixAsString(PointerBase P) const
static constexpr size_t TrieContentBaseSize
static constexpr size_t DefaultNumRootBits
See the file comment for details on the usage of the TrailingObjects type.
const T * getTrailingObjects() const
Returns a pointer to the trailing object array of the given type (which must be one of those specifie...
An efficient, type-erasing, non-owning reference to a callable.
A raw_ostream that writes to an std::string.
This class provides various memory handling functions that manipulate MemoryBlock instances.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
This is an optimization pass for GlobalISel generic memory operations.
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
decltype(auto) get(const PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info > &Pair)
@ Sub
Subtraction of integers.
The utility class that helps computing the index of the object inside trie from its hash.