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