contrib/llvm-project/llvm/include/llvm/CodeGen/AccelTable.h

   1 //==- include/llvm/CodeGen/AccelTable.h - Accelerator Tables -----*- 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 // This file contains support for writing accelerator tables.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #ifndef LLVM_CODEGEN_DWARFACCELTABLE_H
  14 #define LLVM_CODEGEN_DWARFACCELTABLE_H
  15
  16 #include "llvm/ADT/ArrayRef.h"
  17 #include "llvm/ADT/SmallVector.h"
  18 #include "llvm/ADT/StringMap.h"
  19 #include "llvm/ADT/StringRef.h"
  20 #include "llvm/BinaryFormat/Dwarf.h"
  21 #include "llvm/CodeGen/DIE.h"
  22 #include "llvm/CodeGen/DwarfStringPoolEntry.h"
  23 #include "llvm/MC/MCSymbol.h"
  24 #include "llvm/Support/Allocator.h"
  25 #include "llvm/Support/DJB.h"
  26 #include "llvm/Support/Debug.h"
  27 #include "llvm/Support/Format.h"
  28 #include "llvm/Support/raw_ostream.h"
  29 #include <cstddef>
  30 #include <cstdint>
  31 #include <vector>
  32
  33 /// The DWARF and Apple accelerator tables are an indirect hash table optimized
  34 /// for null lookup rather than access to known data. The Apple accelerator
  35 /// tables are a precursor of the newer DWARF v5 accelerator tables. Both
  36 /// formats share common design ideas.
  37 ///
  38 /// The Apple accelerator table are output into an on-disk format that looks
  39 /// like this:
  40 ///
  41 /// .------------------.
  42 /// |  HEADER          |
  43 /// |------------------|
  44 /// |  BUCKETS         |
  45 /// |------------------|
  46 /// |  HASHES          |
  47 /// |------------------|
  48 /// |  OFFSETS         |
  49 /// |------------------|
  50 /// |  DATA            |
  51 /// `------------------'
  52 ///
  53 /// The header contains a magic number, version, type of hash function,
  54 /// the number of buckets, total number of hashes, and room for a special struct
  55 /// of data and the length of that struct.
  56 ///
  57 /// The buckets contain an index (e.g. 6) into the hashes array. The hashes
  58 /// section contains all of the 32-bit hash values in contiguous memory, and the
  59 /// offsets contain the offset into the data area for the particular hash.
  60 ///
  61 /// For a lookup example, we could hash a function name and take it modulo the
  62 /// number of buckets giving us our bucket. From there we take the bucket value
  63 /// as an index into the hashes table and look at each successive hash as long
  64 /// as the hash value is still the same modulo result (bucket value) as earlier.
  65 /// If we have a match we look at that same entry in the offsets table and grab
  66 /// the offset in the data for our final match.
  67 ///
  68 /// The DWARF v5 accelerator table consists of zero or more name indices that
  69 /// are output into an on-disk format that looks like this:
  70 ///
  71 /// .------------------.
  72 /// |  HEADER          |
  73 /// |------------------|
  74 /// |  CU LIST         |
  75 /// |------------------|
  76 /// |  LOCAL TU LIST   |
  77 /// |------------------|
  78 /// |  FOREIGN TU LIST |
  79 /// |------------------|
  80 /// |  HASH TABLE      |
  81 /// |------------------|
  82 /// |  NAME TABLE      |
  83 /// |------------------|
  84 /// |  ABBREV TABLE    |
  85 /// |------------------|
  86 /// |  ENTRY POOL      |
  87 /// `------------------'
  88 ///
  89 /// For the full documentation please refer to the DWARF 5 standard.
  90 ///
  91 ///
  92 /// This file defines the class template AccelTable, which is represents an
  93 /// abstract view of an Accelerator table, without any notion of an on-disk
  94 /// layout. This class is parameterized by an entry type, which should derive
  95 /// from AccelTableData. This is the type of individual entries in the table,
  96 /// and it should store the data necessary to emit them. AppleAccelTableData is
  97 /// the base class for Apple Accelerator Table entries, which have a uniform
  98 /// structure based on a sequence of Atoms. There are different sub-classes
  99 /// derived from AppleAccelTable, which differ in the set of Atoms and how they
 100 /// obtain their values.
 101 ///
 102 /// An Apple Accelerator Table can be serialized by calling emitAppleAccelTable
 103 /// function.
 104 ///
 105 /// TODO: Add DWARF v5 emission code.
 106
 107 namespace llvm {
 108
 109 class AsmPrinter;
 110 class DwarfCompileUnit;
 111 class DwarfDebug;
 112
 113 /// Interface which the different types of accelerator table data have to
 114 /// conform. It serves as a base class for different values of the template
 115 /// argument of the AccelTable class template.
 116 class AccelTableData {
 117 public:
 118   virtual ~AccelTableData() = default;
 119
 120   bool operator<(const AccelTableData &Other) const {
 121     return order() < Other.order();
 122   }
 123
 124     // Subclasses should implement:
 125     // static uint32_t hash(StringRef Name);
 126
 127 #ifndef NDEBUG
 128   virtual void print(raw_ostream &OS) const = 0;
 129 #endif
 130 protected:
 131   virtual uint64_t order() const = 0;
 132 };
 133
 134 /// A base class holding non-template-dependant functionality of the AccelTable
 135 /// class. Clients should not use this class directly but rather instantiate
 136 /// AccelTable with a type derived from AccelTableData.
 137 class AccelTableBase {
 138 public:
 139   using HashFn = uint32_t(StringRef);
 140
 141   /// Represents a group of entries with identical name (and hence, hash value).
 142   struct HashData {
 143     DwarfStringPoolEntryRef Name;
 144     uint32_t HashValue;
 145     std::vector<AccelTableData *> Values;
 146     MCSymbol *Sym;
 147
 148     HashData(DwarfStringPoolEntryRef Name, HashFn *Hash)
 149         : Name(Name), HashValue(Hash(Name.getString())) {}
 150
 151 #ifndef NDEBUG
 152     void print(raw_ostream &OS) const;
 153     void dump() const { print(dbgs()); }
 154 #endif
 155   };
 156   using HashList = std::vector<HashData *>;
 157   using BucketList = std::vector<HashList>;
 158
 159 protected:
 160   /// Allocator for HashData and Values.
 161   BumpPtrAllocator Allocator;
 162
 163   using StringEntries = StringMap<HashData, BumpPtrAllocator &>;
 164   StringEntries Entries;
 165
 166   HashFn *Hash;
 167   uint32_t BucketCount;
 168   uint32_t UniqueHashCount;
 169
 170   HashList Hashes;
 171   BucketList Buckets;
 172
 173   void computeBucketCount();
 174
 175   AccelTableBase(HashFn *Hash) : Entries(Allocator), Hash(Hash) {}
 176
 177 public:
 178   void finalize(AsmPrinter *Asm, StringRef Prefix);
 179   ArrayRef<HashList> getBuckets() const { return Buckets; }
 180   uint32_t getBucketCount() const { return BucketCount; }
 181   uint32_t getUniqueHashCount() const { return UniqueHashCount; }
 182   uint32_t getUniqueNameCount() const { return Entries.size(); }
 183
 184 #ifndef NDEBUG
 185   void print(raw_ostream &OS) const;
 186   void dump() const { print(dbgs()); }
 187 #endif
 188
 189   AccelTableBase(const AccelTableBase &) = delete;
 190   void operator=(const AccelTableBase &) = delete;
 191 };
 192
 193 /// This class holds an abstract representation of an Accelerator Table,
 194 /// consisting of a sequence of buckets, each bucket containint a sequence of
 195 /// HashData entries. The class is parameterized by the type of entries it
 196 /// holds. The type template parameter also defines the hash function to use for
 197 /// hashing names.
 198 template <typename DataT> class AccelTable : public AccelTableBase {
 199 public:
 200   AccelTable() : AccelTableBase(DataT::hash) {}
 201
 202   template <typename... Types>
 203   void addName(DwarfStringPoolEntryRef Name, Types &&... Args);
 204 };
 205
 206 template <typename AccelTableDataT>
 207 template <typename... Types>
 208 void AccelTable<AccelTableDataT>::addName(DwarfStringPoolEntryRef Name,
 209                                           Types &&... Args) {
 210   assert(Buckets.empty() && "Already finalized!");
 211   // If the string is in the list already then add this die to the list
 212   // otherwise add a new one.
 213   auto Iter = Entries.try_emplace(Name.getString(), Name, Hash).first;
 214   assert(Iter->second.Name == Name);
 215   Iter->second.Values.push_back(
 216       new (Allocator) AccelTableDataT(std::forward<Types>(Args)...));
 217 }
 218
 219 /// A base class for different implementations of Data classes for Apple
 220 /// Accelerator Tables. The columns in the table are defined by the static Atoms
 221 /// variable defined on the subclasses.
 222 class AppleAccelTableData : public AccelTableData {
 223 public:
 224   /// An Atom defines the form of the data in an Apple accelerator table.
 225   /// Conceptually it is a column in the accelerator consisting of a type and a
 226   /// specification of the form of its data.
 227   struct Atom {
 228     /// Atom Type.
 229     const uint16_t Type;
 230     /// DWARF Form.
 231     const uint16_t Form;
 232
 233     constexpr Atom(uint16_t Type, uint16_t Form) : Type(Type), Form(Form) {}
 234
 235 #ifndef NDEBUG
 236     void print(raw_ostream &OS) const;
 237     void dump() const { print(dbgs()); }
 238 #endif
 239   };
 240   // Subclasses should define:
 241   // static constexpr Atom Atoms[];
 242
 243   virtual void emit(AsmPrinter *Asm) const = 0;
 244
 245   static uint32_t hash(StringRef Buffer) { return djbHash(Buffer); }
 246 };
 247
 248 /// The Data class implementation for DWARF v5 accelerator table. Unlike the
 249 /// Apple Data classes, this class is just a DIE wrapper, and does not know to
 250 /// serialize itself. The complete serialization logic is in the
 251 /// emitDWARF5AccelTable function.
 252 class DWARF5AccelTableData : public AccelTableData {
 253 public:
 254   static uint32_t hash(StringRef Name) { return caseFoldingDjbHash(Name); }
 255
 256   DWARF5AccelTableData(const DIE &Die) : Die(Die) {}
 257
 258 #ifndef NDEBUG
 259   void print(raw_ostream &OS) const override;
 260 #endif
 261
 262   const DIE &getDie() const { return Die; }
 263   uint64_t getDieOffset() const { return Die.getOffset(); }
 264   unsigned getDieTag() const { return Die.getTag(); }
 265
 266 protected:
 267   const DIE &Die;
 268
 269   uint64_t order() const override { return Die.getOffset(); }
 270 };
 271
 272 class DWARF5AccelTableStaticData : public AccelTableData {
 273 public:
 274   static uint32_t hash(StringRef Name) { return caseFoldingDjbHash(Name); }
 275
 276   DWARF5AccelTableStaticData(uint64_t DieOffset, unsigned DieTag,
 277                              unsigned CUIndex)
 278       : DieOffset(DieOffset), DieTag(DieTag), CUIndex(CUIndex) {}
 279
 280 #ifndef NDEBUG
 281   void print(raw_ostream &OS) const override;
 282 #endif
 283
 284   uint64_t getDieOffset() const { return DieOffset; }
 285   unsigned getDieTag() const { return DieTag; }
 286   unsigned getCUIndex() const { return CUIndex; }
 287
 288 protected:
 289   uint64_t DieOffset;
 290   unsigned DieTag;
 291   unsigned CUIndex;
 292
 293   uint64_t order() const override { return DieOffset; }
 294 };
 295
 296 void emitAppleAccelTableImpl(AsmPrinter *Asm, AccelTableBase &Contents,
 297                              StringRef Prefix, const MCSymbol *SecBegin,
 298                              ArrayRef<AppleAccelTableData::Atom> Atoms);
 299
 300 /// Emit an Apple Accelerator Table consisting of entries in the specified
 301 /// AccelTable. The DataT template parameter should be derived from
 302 /// AppleAccelTableData.
 303 template <typename DataT>
 304 void emitAppleAccelTable(AsmPrinter *Asm, AccelTable<DataT> &Contents,
 305                          StringRef Prefix, const MCSymbol *SecBegin) {
 306   static_assert(std::is_convertible<DataT *, AppleAccelTableData *>::value, "");
 307   emitAppleAccelTableImpl(Asm, Contents, Prefix, SecBegin, DataT::Atoms);
 308 }
 309
 310 void emitDWARF5AccelTable(AsmPrinter *Asm,
 311                           AccelTable<DWARF5AccelTableData> &Contents,
 312                           const DwarfDebug &DD,
 313                           ArrayRef<std::unique_ptr<DwarfCompileUnit>> CUs);
 314
 315 void emitDWARF5AccelTable(
 316     AsmPrinter *Asm, AccelTable<DWARF5AccelTableStaticData> &Contents,
 317     ArrayRef<MCSymbol *> CUs,
 318     llvm::function_ref<unsigned(const DWARF5AccelTableStaticData &)>
 319         getCUIndexForEntry);
 320
 321 /// Accelerator table data implementation for simple Apple accelerator tables
 322 /// with just a DIE reference.
 323 class AppleAccelTableOffsetData : public AppleAccelTableData {
 324 public:
 325   AppleAccelTableOffsetData(const DIE &D) : Die(D) {}
 326
 327   void emit(AsmPrinter *Asm) const override;
 328
 329   static constexpr Atom Atoms[] = {
 330       Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
 331
 332 #ifndef NDEBUG
 333   void print(raw_ostream &OS) const override;
 334 #endif
 335 protected:
 336   uint64_t order() const override { return Die.getOffset(); }
 337
 338   const DIE &Die;
 339 };
 340
 341 /// Accelerator table data implementation for Apple type accelerator tables.
 342 class AppleAccelTableTypeData : public AppleAccelTableOffsetData {
 343 public:
 344   AppleAccelTableTypeData(const DIE &D) : AppleAccelTableOffsetData(D) {}
 345
 346   void emit(AsmPrinter *Asm) const override;
 347
 348   static constexpr Atom Atoms[] = {
 349       Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4),
 350       Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2),
 351       Atom(dwarf::DW_ATOM_type_flags, dwarf::DW_FORM_data1)};
 352
 353 #ifndef NDEBUG
 354   void print(raw_ostream &OS) const override;
 355 #endif
 356 };
 357
 358 /// Accelerator table data implementation for simple Apple accelerator tables
 359 /// with a DIE offset but no actual DIE pointer.
 360 class AppleAccelTableStaticOffsetData : public AppleAccelTableData {
 361 public:
 362   AppleAccelTableStaticOffsetData(uint32_t Offset) : Offset(Offset) {}
 363
 364   void emit(AsmPrinter *Asm) const override;
 365
 366   static constexpr Atom Atoms[] = {
 367       Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
 368
 369 #ifndef NDEBUG
 370   void print(raw_ostream &OS) const override;
 371 #endif
 372 protected:
 373   uint64_t order() const override { return Offset; }
 374
 375   uint32_t Offset;
 376 };
 377
 378 /// Accelerator table data implementation for type accelerator tables with
 379 /// a DIE offset but no actual DIE pointer.
 380 class AppleAccelTableStaticTypeData : public AppleAccelTableStaticOffsetData {
 381 public:
 382   AppleAccelTableStaticTypeData(uint32_t Offset, uint16_t Tag,
 383                                 bool ObjCClassIsImplementation,
 384                                 uint32_t QualifiedNameHash)
 385       : AppleAccelTableStaticOffsetData(Offset),
 386         QualifiedNameHash(QualifiedNameHash), Tag(Tag),
 387         ObjCClassIsImplementation(ObjCClassIsImplementation) {}
 388
 389   void emit(AsmPrinter *Asm) const override;
 390
 391   static constexpr Atom Atoms[] = {
 392       Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4),
 393       Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2),
 394       Atom(5, dwarf::DW_FORM_data1), Atom(6, dwarf::DW_FORM_data4)};
 395
 396 #ifndef NDEBUG
 397   void print(raw_ostream &OS) const override;
 398 #endif
 399 protected:
 400   uint64_t order() const override { return Offset; }
 401
 402   uint32_t QualifiedNameHash;
 403   uint16_t Tag;
 404   bool ObjCClassIsImplementation;
 405 };
 406
 407 } // end namespace llvm
 408
 409 #endif // LLVM_CODEGEN_DWARFACCELTABLE_H