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