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 19 namespace llvm { 20 namespace dwarf_linker { 21 namespace parallel { 22 23 class TypePool; 24 class CompileUnit; 25 class TypeEntryBody; 26 27 using TypeEntry = StringMapEntry<std::atomic<TypeEntryBody *>>; 28 29 /// Keeps cloned data for the type DIE. 30 class TypeEntryBody { 31 public: 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 70 protected: 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 81 class TypeEntryInfo { 82 public: 83 /// \returns Hash value for the specified \p Key. 84 static inline uint64_t getHashValue(const StringRef &Key) { 85 return xxh3_64bits(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, Allocator); 103 } 104 }; 105 106 /// TypePool keeps type descriptors which contain partially cloned DIE 107 /// correspinding to each type. Types are identified by names. 108 class TypePool 109 : ConcurrentHashTableByPtr<StringRef, TypeEntry, 110 llvm::parallel::PerThreadBumpPtrAllocator, 111 TypeEntryInfo> { 112 public: 113 TypePool() 114 : ConcurrentHashTableByPtr<StringRef, TypeEntry, 115 llvm::parallel::PerThreadBumpPtrAllocator, 116 TypeEntryInfo>(Allocator) { 117 Root = TypeEntry::create("", Allocator); 118 Root->getValue().store(TypeEntryBody::create(Allocator)); 119 } 120 121 TypeEntry *insert(StringRef Name) { 122 return ConcurrentHashTableByPtr<StringRef, TypeEntry, 123 llvm::parallel::PerThreadBumpPtrAllocator, 124 TypeEntryInfo>::insert(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_weak(DIE, NewDIE)) { 139 ParentEntry->getValue().load()->Children.add(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(TypesComparator); 151 Entry->getValue().load()->Children.forEach(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 165 protected: 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 174 private: 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