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/SmallString.h"
15#include "llvm/ADT/StringMap.h"
16#include "llvm/CodeGen/DIE.h"
17#include "llvm/Support/Allocator.h"
18#include "llvm/Support/Parallel.h"
19#include <atomic>
20#include <limits>
21#include <variant>
22
23namespace llvm {
24namespace dwarf_linker {
25namespace parallel {
26
27class TypePool;
28class CompileUnit;
29class TypeEntryBody;
30
31using TypeEntry = StringMapEntry<std::atomic<TypeEntryBody *>>;
32
33/// A type key is text interleaved with references to other type entries. A
34/// reference stands for the referenced entry's key without copying it. Keys
35/// are interned, so equal references mean equal keys.
36class TypeKey {
37public:
38 /// A maximal run of text, or a reference.
39 using Part = std::variant<StringRef, const TypeEntry *>;
40
41 /// Remove the first part of the non-empty key \p Key and return it.
42 static Part takePart(StringRef &Key);
43
44 /// Compare \p LHS and \p RHS as if every reference were replaced by the key
45 /// it refers to, so the result does not depend on pointer values.
46 static int compare(StringRef LHS, StringRef RHS);
47
48 /// \returns \p Key with every reference replaced by the key it refers to.
49 static std::string expand(StringRef Key);
50
51 TypeKey &operator+=(StringRef Text) {
52 assert(!Text.contains(RefMarker) && "text would read as a reference");
53 Bytes += Text;
54 return *this;
55 }
56 TypeKey &operator+=(char C) {
57 assert(C != RefMarker && "text would read as a reference");
58 Bytes += C;
59 return *this;
60 }
61 void appendRef(const TypeEntry *Entry);
62
63 size_t size() const { return Bytes.size(); }
64 void truncate(size_t Size) { Bytes.truncate(N: Size); }
65 StringRef str() const { return Bytes; }
66
67private:
68 /// DWARF strings cannot contain NUL, so the marker is unambiguous.
69 static constexpr char RefMarker = '\0';
70 static constexpr size_t RefSize = 1 + sizeof(const TypeEntry *);
71
72 SmallString<1000> Bytes;
73};
74
75/// Keeps cloned data for the type DIE.
76class TypeEntryBody {
77public:
78 /// Returns copy of type DIE which should be emitted into resulting file.
79 DIE &getFinalDie() const {
80 if (Die)
81 return *Die;
82
83 assert(DeclarationDie);
84 return *DeclarationDie;
85 }
86
87 /// Returns true if type die entry has only declaration die.
88 bool hasOnlyDeclaration() const { return Die == nullptr; }
89
90 /// Creates type DIE for the specified name.
91 static TypeEntryBody *
92 create(llvm::parallel::PerThreadBumpPtrAllocator &Allocator) {
93 TypeEntryBody *Result = Allocator.Allocate<TypeEntryBody>();
94 new (Result) TypeEntryBody(Allocator);
95 return Result;
96 }
97
98 /// TypeEntryBody keeps partially cloned DIEs corresponding to this type.
99 /// The two kinds of DIE can be kept: declaration and definition.
100 /// If definition DIE was met while parsing input DWARF then this DIE would
101 /// be used as a final DIE for this type. If definition DIE is not met then
102 /// declaration DIE would be used as a final DIE.
103
104 // Keeps definition die.
105 std::atomic<DIE *> Die = {nullptr};
106
107 // Keeps declaration die.
108 std::atomic<DIE *> DeclarationDie = {nullptr};
109
110 // True if the declaration winner's parent is itself a declaration.
111 bool DeclarationParentIsDeclaration = true;
112
113 // Priority of the CU that set Die (lower wins, for deterministic output).
114 // Atomic so it can be read outside the lock for a fast pre-check; the
115 // definitive comparison still happens under the spinlock.
116 std::atomic<uint64_t> DiePriority = {std::numeric_limits<uint64_t>::max()};
117
118 // Priority of the CU that set DeclarationDie (lower wins).
119 uint64_t DeclarationDiePriority = std::numeric_limits<uint64_t>::max();
120
121 // Spinlock for deterministic type DIE allocation.
122 std::atomic_flag Lock = {};
123
124 // Primary key for the comparator: ordinal of this child in its parent's
125 // child list, min-merged across CUs to keep record-like type members in
126 // source order. Sentinel UINT32_MAX sorts after any real observation.
127 // When set, overwrites the default getKey() in TypeComparator.
128 std::atomic<uint32_t> SortKey = {std::numeric_limits<uint32_t>::max()};
129
130 /// Children for current type.
131 ArrayList<TypeEntry *, 5> Children;
132
133protected:
134 TypeEntryBody() = delete;
135 TypeEntryBody(const TypeEntryBody &RHS) = delete;
136 TypeEntryBody(TypeEntryBody &&RHS) = delete;
137 TypeEntryBody &operator=(const TypeEntryBody &RHS) = delete;
138 TypeEntryBody &operator=(const TypeEntryBody &&RHS) = delete;
139
140 TypeEntryBody(llvm::parallel::PerThreadBumpPtrAllocator &Allocator)
141 : Children(&Allocator) {}
142};
143
144/// TypePool keeps type descriptors which contain partially cloned DIE
145/// correspinding to each type. Types are identified by names.
146class TypePool
147 : ConcurrentHashTableByPtr<StringRef, TypeEntry,
148 llvm::parallel::PerThreadBumpPtrAllocator> {
149public:
150 TypePool()
151 : ConcurrentHashTableByPtr<StringRef, TypeEntry,
152 llvm::parallel::PerThreadBumpPtrAllocator>(
153 Allocator) {
154 Root = TypeEntry::create(key: "", allocator&: Allocator);
155 Root->getValue().store(p: TypeEntryBody::create(Allocator));
156 }
157
158 TypeEntry *insert(StringRef Name) {
159 return ConcurrentHashTableByPtr<
160 StringRef, TypeEntry,
161 llvm::parallel::PerThreadBumpPtrAllocator>::insert(NewValue: Name)
162 .first;
163 }
164
165 /// Create or return existing type entry body for the specified \p Entry.
166 /// Link that entry as child for the specified \p ParentEntry.
167 /// The returned body's \c SortKey starts at the sentinel; callers that want
168 /// the entry to participate in source-order sorting must min-merge their
169 /// per-CU observation into it.
170 /// \returns The existing or created type entry body.
171 TypeEntryBody *getOrCreateTypeEntryBody(TypeEntry *Entry,
172 TypeEntry *ParentEntry) {
173 TypeEntryBody *DIE = Entry->getValue().load();
174 if (DIE)
175 return DIE;
176
177 TypeEntryBody *NewDIE = TypeEntryBody::create(Allocator);
178 if (Entry->getValue().compare_exchange_strong(p1&: DIE, p2: NewDIE)) {
179 ParentEntry->getValue().load()->Children.add(Item: Entry);
180 return NewDIE;
181 }
182
183 return DIE;
184 }
185
186 /// Sort children for each kept type entry.
187 void sortTypes() {
188 SmallVector<TypeEntry *> Entries;
189 SmallVector<TypeEntry *> Worklist = {getRoot()};
190 while (!Worklist.empty()) {
191 TypeEntry *Entry = Worklist.pop_back_val();
192 Entries.push_back(Elt: Entry);
193 Entry->getValue().load()->Children.forEach(
194 Handler: [&](TypeEntry *Child) { Worklist.push_back(Elt: Child); });
195 }
196
197 // The comparator is a total order, so the result does not depend on
198 // scheduling.
199 parallelForEach(R&: Entries, Fn: [&](TypeEntry *Entry) {
200 Entry->getValue().load()->Children.sort(Comparator: TypesComparator,
201 /*Parallel=*/Parallel: true);
202 });
203 }
204
205 /// Return root for all type entries.
206 TypeEntry *getRoot() const { return Root; }
207
208 /// Return thread local allocator used by pool.
209 BumpPtrAllocator &getThreadLocalAllocator() {
210 return Allocator.getThreadLocalAllocator();
211 }
212
213protected:
214 std::function<bool(const TypeEntry *LHS, const TypeEntry *RHS)>
215 TypesComparator = [](const TypeEntry *LHS, const TypeEntry *RHS) -> bool {
216 uint32_t LK =
217 LHS->getValue().load()->SortKey.load(m: std::memory_order_relaxed);
218 uint32_t RK =
219 RHS->getValue().load()->SortKey.load(m: std::memory_order_relaxed);
220 if (LK != RK)
221 return LK < RK;
222 return TypeKey::compare(LHS: LHS->getKey(), RHS: RHS->getKey()) < 0;
223 };
224
225 // Root of all type entries.
226 TypeEntry *Root = nullptr;
227
228private:
229 llvm::parallel::PerThreadBumpPtrAllocator Allocator;
230};
231
232} // end of namespace parallel
233} // end of namespace dwarf_linker
234} // end of namespace llvm
235
236#endif // LLVM_DWARFLINKER_PARALLEL_TYPEPOOL_H
237