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
19namespace llvm {
20namespace dwarf_linker {
21namespace parallel {
22
23class TypePool;
24class CompileUnit;
25class TypeEntryBody;
26
27using TypeEntry = StringMapEntry<std::atomic<TypeEntryBody *>>;
28
29/// Keeps cloned data for the type DIE.
30class TypeEntryBody {
31public:
32 /// Returns copy of type DIE which should be emitted into resulting file.
33 DIE &getFinalDie() const {
34 if (Die)
35 return *Die;
36
37 assert(DeclarationDie);
38 return *DeclarationDie;
39 }
40
41 /// Returns true if type die entry has only declaration die.
42 bool hasOnlyDeclaration() const { return Die == nullptr; }
43
44 /// Creates type DIE for the specified name.
45 static TypeEntryBody *
46 create(llvm::parallel::PerThreadBumpPtrAllocator &Allocator) {
47 TypeEntryBody *Result = Allocator.Allocate<TypeEntryBody>();
48 new (Result) TypeEntryBody(Allocator);
49 return Result;
50 }
51
52 /// TypeEntryBody keeps partially cloned DIEs corresponding to this type.
53 /// The two kinds of DIE can be kept: declaration and definition.
54 /// If definition DIE was met while parsing input DWARF then this DIE would
55 /// be used as a final DIE for this type. If definition DIE is not met then
56 /// declaration DIE would be used as a final DIE.
57
58 // Keeps definition die.
59 std::atomic<DIE *> Die = {nullptr};
60
61 // Keeps declaration die.
62 std::atomic<DIE *> DeclarationDie = {nullptr};
63
64 // True if parent type die is declaration.
65 std::atomic<bool> ParentIsDeclaration = {true};
66
67 /// Children for current type.
68 ArrayList<TypeEntry *, 5> Children;
69
70protected:
71 TypeEntryBody() = delete;
72 TypeEntryBody(const TypeEntryBody &RHS) = delete;
73 TypeEntryBody(TypeEntryBody &&RHS) = delete;
74 TypeEntryBody &operator=(const TypeEntryBody &RHS) = delete;
75 TypeEntryBody &operator=(const TypeEntryBody &&RHS) = delete;
76
77 TypeEntryBody(llvm::parallel::PerThreadBumpPtrAllocator &Allocator)
78 : Children(&Allocator) {}
79};
80
81class TypeEntryInfo {
82public:
83 /// \returns Hash value for the specified \p Key.
84 static inline uint64_t getHashValue(const StringRef &Key) {
85 return xxh3_64bits(data: Key);
86 }
87
88 /// \returns true if both \p LHS and \p RHS are equal.
89 static inline bool isEqual(const StringRef &LHS, const StringRef &RHS) {
90 return LHS == RHS;
91 }
92
93 /// \returns key for the specified \p KeyData.
94 static inline StringRef getKey(const TypeEntry &KeyData) {
95 return KeyData.getKey();
96 }
97
98 /// \returns newly created object of KeyDataTy type.
99 static inline TypeEntry *
100 create(const StringRef &Key,
101 llvm::parallel::PerThreadBumpPtrAllocator &Allocator) {
102 return TypeEntry::create(key: Key, allocator&: Allocator);
103 }
104};
105
106/// TypePool keeps type descriptors which contain partially cloned DIE
107/// correspinding to each type. Types are identified by names.
108class TypePool
109 : ConcurrentHashTableByPtr<StringRef, TypeEntry,
110 llvm::parallel::PerThreadBumpPtrAllocator,
111 TypeEntryInfo> {
112public:
113 TypePool()
114 : ConcurrentHashTableByPtr<StringRef, TypeEntry,
115 llvm::parallel::PerThreadBumpPtrAllocator,
116 TypeEntryInfo>(Allocator) {
117 Root = TypeEntry::create(key: "", allocator&: Allocator);
118 Root->getValue().store(p: TypeEntryBody::create(Allocator));
119 }
120
121 TypeEntry *insert(StringRef Name) {
122 return ConcurrentHashTableByPtr<StringRef, TypeEntry,
123 llvm::parallel::PerThreadBumpPtrAllocator,
124 TypeEntryInfo>::insert(NewValue: Name)
125 .first;
126 }
127
128 /// Create or return existing type entry body for the specified \p Entry.
129 /// Link that entry as child for the specified \p ParentEntry.
130 /// \returns The existing or created type entry body.
131 TypeEntryBody *getOrCreateTypeEntryBody(TypeEntry *Entry,
132 TypeEntry *ParentEntry) {
133 TypeEntryBody *DIE = Entry->getValue().load();
134 if (DIE)
135 return DIE;
136
137 TypeEntryBody *NewDIE = TypeEntryBody::create(Allocator);
138 if (Entry->getValue().compare_exchange_strong(p1&: DIE, p2: NewDIE)) {
139 ParentEntry->getValue().load()->Children.add(Item: Entry);
140 return NewDIE;
141 }
142
143 return DIE;
144 }
145
146 /// Sort children for each kept type entry.
147 void sortTypes() {
148 std::function<void(TypeEntry * Entry)> SortChildrenRec =
149 [&](TypeEntry *Entry) {
150 Entry->getValue().load()->Children.sort(Comparator: TypesComparator);
151 Entry->getValue().load()->Children.forEach(Handler: SortChildrenRec);
152 };
153
154 SortChildrenRec(getRoot());
155 }
156
157 /// Return root for all type entries.
158 TypeEntry *getRoot() const { return Root; }
159
160 /// Return thread local allocator used by pool.
161 BumpPtrAllocator &getThreadLocalAllocator() {
162 return Allocator.getThreadLocalAllocator();
163 }
164
165protected:
166 std::function<bool(const TypeEntry *LHS, const TypeEntry *RHS)>
167 TypesComparator = [](const TypeEntry *LHS, const TypeEntry *RHS) -> bool {
168 return LHS->getKey() < RHS->getKey();
169 };
170
171 // Root of all type entries.
172 TypeEntry *Root = nullptr;
173
174private:
175 llvm::parallel::PerThreadBumpPtrAllocator Allocator;
176};
177
178} // end of namespace parallel
179} // end of namespace dwarf_linker
180} // end of namespace llvm
181
182#endif // LLVM_DWARFLINKER_PARALLEL_TYPEPOOL_H
183