| 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 | |
| 23 | namespace llvm { |
| 24 | namespace dwarf_linker { |
| 25 | namespace parallel { |
| 26 | |
| 27 | class TypePool; |
| 28 | class CompileUnit; |
| 29 | class TypeEntryBody; |
| 30 | |
| 31 | using 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. |
| 36 | class TypeKey { |
| 37 | public: |
| 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 | |
| 67 | private: |
| 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. |
| 76 | class TypeEntryBody { |
| 77 | public: |
| 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 | |
| 133 | protected: |
| 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. |
| 146 | class TypePool |
| 147 | : ConcurrentHashTableByPtr<StringRef, TypeEntry, |
| 148 | llvm::parallel::PerThreadBumpPtrAllocator> { |
| 149 | public: |
| 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 | |
| 213 | protected: |
| 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 | |
| 228 | private: |
| 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 | |