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 namespace llvm { 106 107 class AsmPrinter; 108 class DwarfCompileUnit; 109 class DwarfDebug; 110 111 /// Interface which the different types of accelerator table data have to 112 /// conform. It serves as a base class for different values of the template 113 /// argument of the AccelTable class template. 114 class AccelTableData { 115 public: 116 virtual ~AccelTableData() = default; 117 118 bool operator<(const AccelTableData &Other) const { 119 return order() < Other.order(); 120 } 121 122 // Subclasses should implement: 123 // static uint32_t hash(StringRef Name); 124 125 #ifndef NDEBUG 126 virtual void print(raw_ostream &OS) const = 0; 127 #endif 128 protected: 129 virtual uint64_t order() const = 0; 130 }; 131 132 /// A base class holding non-template-dependant functionality of the AccelTable 133 /// class. Clients should not use this class directly but rather instantiate 134 /// AccelTable with a type derived from AccelTableData. 135 class AccelTableBase { 136 public: 137 using HashFn = uint32_t(StringRef); 138 139 /// Represents a group of entries with identical name (and hence, hash value). 140 struct HashData { 141 DwarfStringPoolEntryRef Name; 142 uint32_t HashValue; 143 std::vector<AccelTableData *> Values; 144 MCSymbol *Sym; 145 146 HashData(DwarfStringPoolEntryRef Name, HashFn *Hash) 147 : Name(Name), HashValue(Hash(Name.getString())) {} 148 149 #ifndef NDEBUG 150 void print(raw_ostream &OS) const; 151 void dump() const { print(dbgs()); } 152 #endif 153 }; 154 using HashList = std::vector<HashData *>; 155 using BucketList = std::vector<HashList>; 156 157 protected: 158 /// Allocator for HashData and Values. 159 BumpPtrAllocator Allocator; 160 161 using StringEntries = StringMap<HashData, BumpPtrAllocator &>; 162 StringEntries Entries; 163 164 HashFn *Hash; 165 uint32_t BucketCount; 166 uint32_t UniqueHashCount; 167 168 HashList Hashes; 169 BucketList Buckets; 170 171 void computeBucketCount(); 172 173 AccelTableBase(HashFn *Hash) : Entries(Allocator), Hash(Hash) {} 174 175 public: 176 void finalize(AsmPrinter *Asm, StringRef Prefix); 177 ArrayRef<HashList> getBuckets() const { return Buckets; } 178 uint32_t getBucketCount() const { return BucketCount; } 179 uint32_t getUniqueHashCount() const { return UniqueHashCount; } 180 uint32_t getUniqueNameCount() const { return Entries.size(); } 181 182 #ifndef NDEBUG 183 void print(raw_ostream &OS) const; 184 void dump() const { print(dbgs()); } 185 #endif 186 187 AccelTableBase(const AccelTableBase &) = delete; 188 void operator=(const AccelTableBase &) = delete; 189 }; 190 191 /// This class holds an abstract representation of an Accelerator Table, 192 /// consisting of a sequence of buckets, each bucket containint a sequence of 193 /// HashData entries. The class is parameterized by the type of entries it 194 /// holds. The type template parameter also defines the hash function to use for 195 /// hashing names. 196 template <typename DataT> class AccelTable : public AccelTableBase { 197 public: 198 AccelTable() : AccelTableBase(DataT::hash) {} 199 200 template <typename... Types> 201 void addName(DwarfStringPoolEntryRef Name, Types &&... Args); 202 }; 203 204 template <typename AccelTableDataT> 205 template <typename... Types> 206 void AccelTable<AccelTableDataT>::addName(DwarfStringPoolEntryRef Name, 207 Types &&... Args) { 208 assert(Buckets.empty() && "Already finalized!"); 209 // If the string is in the list already then add this die to the list 210 // otherwise add a new one. 211 auto Iter = Entries.try_emplace(Name.getString(), Name, Hash).first; 212 assert(Iter->second.Name == Name); 213 Iter->second.Values.push_back( 214 new (Allocator) AccelTableDataT(std::forward<Types>(Args)...)); 215 } 216 217 /// A base class for different implementations of Data classes for Apple 218 /// Accelerator Tables. The columns in the table are defined by the static Atoms 219 /// variable defined on the subclasses. 220 class AppleAccelTableData : public AccelTableData { 221 public: 222 /// An Atom defines the form of the data in an Apple accelerator table. 223 /// Conceptually it is a column in the accelerator consisting of a type and a 224 /// specification of the form of its data. 225 struct Atom { 226 /// Atom Type. 227 const uint16_t Type; 228 /// DWARF Form. 229 const uint16_t Form; 230 231 constexpr Atom(uint16_t Type, uint16_t Form) : Type(Type), Form(Form) {} 232 233 #ifndef NDEBUG 234 void print(raw_ostream &OS) const; 235 void dump() const { print(dbgs()); } 236 #endif 237 }; 238 // Subclasses should define: 239 // static constexpr Atom Atoms[]; 240 241 virtual void emit(AsmPrinter *Asm) const = 0; 242 243 static uint32_t hash(StringRef Buffer) { return djbHash(Buffer); } 244 }; 245 246 /// The Data class implementation for DWARF v5 accelerator table. Unlike the 247 /// Apple Data classes, this class is just a DIE wrapper, and does not know to 248 /// serialize itself. The complete serialization logic is in the 249 /// emitDWARF5AccelTable function. 250 class DWARF5AccelTableData : public AccelTableData { 251 public: 252 static uint32_t hash(StringRef Name) { return caseFoldingDjbHash(Name); } 253 254 DWARF5AccelTableData(const DIE &Die) : Die(Die) {} 255 256 #ifndef NDEBUG 257 void print(raw_ostream &OS) const override; 258 #endif 259 260 const DIE &getDie() const { return Die; } 261 uint64_t getDieOffset() const { return Die.getOffset(); } 262 unsigned getDieTag() const { return Die.getTag(); } 263 264 protected: 265 const DIE &Die; 266 267 uint64_t order() const override { return Die.getOffset(); } 268 }; 269 270 class DWARF5AccelTableStaticData : public AccelTableData { 271 public: 272 static uint32_t hash(StringRef Name) { return caseFoldingDjbHash(Name); } 273 274 DWARF5AccelTableStaticData(uint64_t DieOffset, unsigned DieTag, 275 unsigned CUIndex) 276 : DieOffset(DieOffset), DieTag(DieTag), CUIndex(CUIndex) {} 277 278 #ifndef NDEBUG 279 void print(raw_ostream &OS) const override; 280 #endif 281 282 uint64_t getDieOffset() const { return DieOffset; } 283 unsigned getDieTag() const { return DieTag; } 284 unsigned getCUIndex() const { return CUIndex; } 285 286 protected: 287 uint64_t DieOffset; 288 unsigned DieTag; 289 unsigned CUIndex; 290 291 uint64_t order() const override { return DieOffset; } 292 }; 293 294 void emitAppleAccelTableImpl(AsmPrinter *Asm, AccelTableBase &Contents, 295 StringRef Prefix, const MCSymbol *SecBegin, 296 ArrayRef<AppleAccelTableData::Atom> Atoms); 297 298 /// Emit an Apple Accelerator Table consisting of entries in the specified 299 /// AccelTable. The DataT template parameter should be derived from 300 /// AppleAccelTableData. 301 template <typename DataT> 302 void emitAppleAccelTable(AsmPrinter *Asm, AccelTable<DataT> &Contents, 303 StringRef Prefix, const MCSymbol *SecBegin) { 304 static_assert(std::is_convertible<DataT *, AppleAccelTableData *>::value, ""); 305 emitAppleAccelTableImpl(Asm, Contents, Prefix, SecBegin, DataT::Atoms); 306 } 307 308 void emitDWARF5AccelTable(AsmPrinter *Asm, 309 AccelTable<DWARF5AccelTableData> &Contents, 310 const DwarfDebug &DD, 311 ArrayRef<std::unique_ptr<DwarfCompileUnit>> CUs); 312 313 void emitDWARF5AccelTable( 314 AsmPrinter *Asm, AccelTable<DWARF5AccelTableStaticData> &Contents, 315 ArrayRef<MCSymbol *> CUs, 316 llvm::function_ref<unsigned(const DWARF5AccelTableStaticData &)> 317 getCUIndexForEntry); 318 319 /// Accelerator table data implementation for simple Apple accelerator tables 320 /// with just a DIE reference. 321 class AppleAccelTableOffsetData : public AppleAccelTableData { 322 public: 323 AppleAccelTableOffsetData(const DIE &D) : Die(D) {} 324 325 void emit(AsmPrinter *Asm) const override; 326 327 static constexpr Atom Atoms[] = { 328 Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)}; 329 330 #ifndef NDEBUG 331 void print(raw_ostream &OS) const override; 332 #endif 333 protected: 334 uint64_t order() const override { return Die.getOffset(); } 335 336 const DIE &Die; 337 }; 338 339 /// Accelerator table data implementation for Apple type accelerator tables. 340 class AppleAccelTableTypeData : public AppleAccelTableOffsetData { 341 public: 342 AppleAccelTableTypeData(const DIE &D) : AppleAccelTableOffsetData(D) {} 343 344 void emit(AsmPrinter *Asm) const override; 345 346 static constexpr Atom Atoms[] = { 347 Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4), 348 Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2), 349 Atom(dwarf::DW_ATOM_type_flags, dwarf::DW_FORM_data1)}; 350 351 #ifndef NDEBUG 352 void print(raw_ostream &OS) const override; 353 #endif 354 }; 355 356 /// Accelerator table data implementation for simple Apple accelerator tables 357 /// with a DIE offset but no actual DIE pointer. 358 class AppleAccelTableStaticOffsetData : public AppleAccelTableData { 359 public: 360 AppleAccelTableStaticOffsetData(uint32_t Offset) : Offset(Offset) {} 361 362 void emit(AsmPrinter *Asm) const override; 363 364 static constexpr Atom Atoms[] = { 365 Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)}; 366 367 #ifndef NDEBUG 368 void print(raw_ostream &OS) const override; 369 #endif 370 protected: 371 uint64_t order() const override { return Offset; } 372 373 uint32_t Offset; 374 }; 375 376 /// Accelerator table data implementation for type accelerator tables with 377 /// a DIE offset but no actual DIE pointer. 378 class AppleAccelTableStaticTypeData : public AppleAccelTableStaticOffsetData { 379 public: 380 AppleAccelTableStaticTypeData(uint32_t Offset, uint16_t Tag, 381 bool ObjCClassIsImplementation, 382 uint32_t QualifiedNameHash) 383 : AppleAccelTableStaticOffsetData(Offset), 384 QualifiedNameHash(QualifiedNameHash), Tag(Tag), 385 ObjCClassIsImplementation(ObjCClassIsImplementation) {} 386 387 void emit(AsmPrinter *Asm) const override; 388 389 static constexpr Atom Atoms[] = { 390 Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4), 391 Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2), 392 Atom(5, dwarf::DW_FORM_data1), Atom(6, dwarf::DW_FORM_data4)}; 393 394 #ifndef NDEBUG 395 void print(raw_ostream &OS) const override; 396 #endif 397 protected: 398 uint64_t order() const override { return Offset; } 399 400 uint32_t QualifiedNameHash; 401 uint16_t Tag; 402 bool ObjCClassIsImplementation; 403 }; 404 405 } // end namespace llvm 406 407 #endif // LLVM_CODEGEN_DWARFACCELTABLE_H 408