llvm/lib/DWARFLinker/Parallel/TypePool.h

   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