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