1//===- TypePool.h -----------------------------------------------*- 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#ifndef LLVM_DWARFLINKER_PARALLEL_TYPEPOOL_H
10#define LLVM_DWARFLINKER_PARALLEL_TYPEPOOL_H
11
12#include "ArrayList.h"
13#include "llvm/ADT/ConcurrentHashtable.h"
14#include "llvm/ADT/StringMap.h"
15#include "llvm/CodeGen/DIE.h"
16#include "llvm/Support/Allocator.h"
17#include <atomic>
18#include <limits>
19
20namespace llvm {
21namespace dwarf_linker {
22namespace parallel {
23
24class TypePool;
25class CompileUnit;
26class TypeEntryBody;
27
28using TypeEntry = StringMapEntry<std::atomic<TypeEntryBody *>>;
29
30/// Keeps cloned data for the type DIE.
31class TypeEntryBody {
32public:
33 /// Returns copy of type DIE which should be emitted into resulting file.
34 DIE &getFinalDie() const {
35 if (Die)
36 return *Die;
37
38 assert(DeclarationDie);
39 return *DeclarationDie;
40 }
41
42 /// Returns true if type die entry has only declaration die.
43 bool hasOnlyDeclaration() const { return Die == nullptr; }
44
45 /// Creates type DIE for the specified name.
46 static TypeEntryBody *
47 create(llvm::parallel::PerThreadBumpPtrAllocator &Allocator) {
48 TypeEntryBody *Result = Allocator.Allocate<TypeEntryBody>();
49 new (Result) TypeEntryBody(Allocator);
50 return Result;
51 }
52
53 /// TypeEntryBody keeps partially cloned DIEs corresponding to this type.
54 /// The two kinds of DIE can be kept: declaration and definition.
55 /// If definition DIE was met while parsing input DWARF then this DIE would
56 /// be used as a final DIE for this type. If definition DIE is not met then
57 /// declaration DIE would be used as a final DIE.
58
59 // Keeps definition die.
60 std::atomic<DIE *> Die = {nullptr};
61
62 // Keeps declaration die.
63 std::atomic<DIE *> DeclarationDie = {nullptr};
64
65 // True if the declaration winner's parent is itself a declaration.
66 bool DeclarationParentIsDeclaration = true;
67
68 // Priority of the CU that set Die (lower wins, for deterministic output).
69 // Atomic so it can be read outside the lock for a fast pre-check; the
70 // definitive comparison still happens under the spinlock.
71 std::atomic<uint64_t> DiePriority = {std::numeric_limits<uint64_t>::max()};
72
73 // Priority of the CU that set DeclarationDie (lower wins).
74 uint64_t DeclarationDiePriority = std::numeric_limits<uint64_t>::max();
75
76 // Spinlock for deterministic type DIE allocation.
77 std::atomic_flag Lock = {};
78
79 // Primary key for the comparator: ordinal of this child in its parent's
80 // child list, min-merged across CUs to keep record-like type members in
81 // source order. Sentinel UINT32_MAX sorts after any real observation.
82 // When set, overwrites the default getKey() in TypeComparator.
83 std::atomic<uint32_t> SortKey = {std::numeric_limits<uint32_t>::max()};
84
85 /// Children for current type.
86 ArrayList<TypeEntry *, 5> Children;
87
88protected:
89 TypeEntryBody() = delete;
90 TypeEntryBody(const TypeEntryBody &RHS) = delete;
91 TypeEntryBody(TypeEntryBody &&RHS) = delete;
92 TypeEntryBody &operator=(const TypeEntryBody &RHS) = delete;
93 TypeEntryBody &operator=(const TypeEntryBody &&RHS) = delete;
94
95 TypeEntryBody(llvm::parallel::PerThreadBumpPtrAllocator &Allocator)
96 : Children(&Allocator) {}
97};
98
99class TypeEntryInfo {
100public:
101 /// \returns Hash value for the specified \p Key.
102 static inline uint64_t getHashValue(const StringRef &Key) {
103 return xxh3_64bits(data: Key);
104 }
105
106 /// \returns true if both \p LHS and \p RHS are equal.
107 static inline bool isEqual(const StringRef &LHS, const StringRef &RHS) {
108 return LHS == RHS;
109 }
110
111 /// \returns key for the specified \p KeyData.
112 static inline StringRef getKey(const TypeEntry &KeyData) {
113 return KeyData.getKey();
114 }
115
116 /// \returns newly created object of KeyDataTy type.
117 static inline TypeEntry *
118 create(const StringRef &Key,
119 llvm::parallel::PerThreadBumpPtrAllocator &Allocator) {
120 return TypeEntry::create(key: Key, allocator&: Allocator);
121 }
122};
123
124/// TypePool keeps type descriptors which contain partially cloned DIE
125/// correspinding to each type. Types are identified by names.
126class TypePool
127 : ConcurrentHashTableByPtr<StringRef, TypeEntry,
128 llvm::parallel::PerThreadBumpPtrAllocator,
129 TypeEntryInfo> {
130public:
131 TypePool()
132 : ConcurrentHashTableByPtr<StringRef, TypeEntry,
133 llvm::parallel::PerThreadBumpPtrAllocator,
134 TypeEntryInfo>(Allocator) {
135 Root = TypeEntry::create(key: "", allocator&: Allocator);
136 Root->getValue().store(p: TypeEntryBody::create(Allocator));
137 }
138
139 TypeEntry *insert(StringRef Name) {
140 return ConcurrentHashTableByPtr<StringRef, TypeEntry,
141 llvm::parallel::PerThreadBumpPtrAllocator,
142 TypeEntryInfo>::insert(NewValue: Name)
143 .first;
144 }
145
146 /// Create or return existing type entry body for the specified \p Entry.
147 /// Link that entry as child for the specified \p ParentEntry.
148 /// The returned body's \c SortKey starts at the sentinel; callers that want
149 /// the entry to participate in source-order sorting must min-merge their
150 /// per-CU observation into it.
151 /// \returns The existing or created type entry body.
152 TypeEntryBody *getOrCreateTypeEntryBody(TypeEntry *Entry,
153 TypeEntry *ParentEntry) {
154 TypeEntryBody *DIE = Entry->getValue().load();
155 if (DIE)
156 return DIE;
157
158 TypeEntryBody *NewDIE = TypeEntryBody::create(Allocator);
159 if (Entry->getValue().compare_exchange_strong(p1&: DIE, p2: NewDIE)) {
160 ParentEntry->getValue().load()->Children.add(Item: Entry);
161 return NewDIE;
162 }
163
164 return DIE;
165 }
166
167 /// Sort children for each kept type entry.
168 void sortTypes() {
169 std::function<void(TypeEntry * Entry)> SortChildrenRec =
170 [&](TypeEntry *Entry) {
171 Entry->getValue().load()->Children.sort(Comparator: TypesComparator);
172 Entry->getValue().load()->Children.forEach(Handler: SortChildrenRec);
173 };
174
175 SortChildrenRec(getRoot());
176 }
177
178 /// Return root for all type entries.
179 TypeEntry *getRoot() const { return Root; }
180
181 /// Return thread local allocator used by pool.
182 BumpPtrAllocator &getThreadLocalAllocator() {
183 return Allocator.getThreadLocalAllocator();
184 }
185
186protected:
187 std::function<bool(const TypeEntry *LHS, const TypeEntry *RHS)>
188 TypesComparator = [](const TypeEntry *LHS, const TypeEntry *RHS) -> bool {
189 uint32_t LK =
190 LHS->getValue().load()->SortKey.load(m: std::memory_order_relaxed);
191 uint32_t RK =
192 RHS->getValue().load()->SortKey.load(m: std::memory_order_relaxed);
193 if (LK != RK)
194 return LK < RK;
195 return LHS->getKey() < RHS->getKey();
196 };
197
198 // Root of all type entries.
199 TypeEntry *Root = nullptr;
200
201private:
202 llvm::parallel::PerThreadBumpPtrAllocator Allocator;
203};
204
205} // end of namespace parallel
206} // end of namespace dwarf_linker
207} // end of namespace llvm
208
209#endif // LLVM_DWARFLINKER_PARALLEL_TYPEPOOL_H
210