1 //===- llvm/CodeGen/AsmPrinter/AccelTable.cpp - Accelerator Tables --------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file contains support for writing accelerator tables. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/CodeGen/AccelTable.h" 15 #include "llvm/ADT/STLExtras.h" 16 #include "llvm/ADT/StringMap.h" 17 #include "llvm/ADT/Twine.h" 18 #include "llvm/BinaryFormat/Dwarf.h" 19 #include "llvm/CodeGen/AsmPrinter.h" 20 #include "llvm/CodeGen/DIE.h" 21 #include "llvm/MC/MCExpr.h" 22 #include "llvm/MC/MCStreamer.h" 23 #include "llvm/Support/raw_ostream.h" 24 #include <algorithm> 25 #include <cstddef> 26 #include <cstdint> 27 #include <limits> 28 #include <vector> 29 30 using namespace llvm; 31 32 void AccelTableBase::computeBucketCount() { 33 // First get the number of unique hashes. 34 std::vector<uint32_t> Uniques; 35 Uniques.reserve(Entries.size()); 36 for (const auto &E : Entries) 37 Uniques.push_back(E.second.HashValue); 38 array_pod_sort(Uniques.begin(), Uniques.end()); 39 std::vector<uint32_t>::iterator P = 40 std::unique(Uniques.begin(), Uniques.end()); 41 42 UniqueHashCount = std::distance(Uniques.begin(), P); 43 44 if (UniqueHashCount > 1024) 45 BucketCount = UniqueHashCount / 4; 46 else if (UniqueHashCount > 16) 47 BucketCount = UniqueHashCount / 2; 48 else 49 BucketCount = std::max<uint32_t>(UniqueHashCount, 1); 50 } 51 52 void AccelTableBase::finalize(AsmPrinter *Asm, StringRef Prefix) { 53 // Create the individual hash data outputs. 54 for (auto &E : Entries) { 55 // Unique the entries. 56 std::stable_sort(E.second.Values.begin(), E.second.Values.end(), 57 [](const AccelTableData *A, const AccelTableData *B) { 58 return *A < *B; 59 }); 60 E.second.Values.erase( 61 std::unique(E.second.Values.begin(), E.second.Values.end()), 62 E.second.Values.end()); 63 } 64 65 // Figure out how many buckets we need, then compute the bucket contents and 66 // the final ordering. The hashes and offsets can be emitted by walking these 67 // data structures. We add temporary symbols to the data so they can be 68 // referenced when emitting the offsets. 69 computeBucketCount(); 70 71 // Compute bucket contents and final ordering. 72 Buckets.resize(BucketCount); 73 for (auto &E : Entries) { 74 uint32_t Bucket = E.second.HashValue % BucketCount; 75 Buckets[Bucket].push_back(&E.second); 76 E.second.Sym = Asm->createTempSymbol(Prefix); 77 } 78 79 // Sort the contents of the buckets by hash value so that hash collisions end 80 // up together. Stable sort makes testing easier and doesn't cost much more. 81 for (auto &Bucket : Buckets) 82 std::stable_sort(Bucket.begin(), Bucket.end(), 83 [](HashData *LHS, HashData *RHS) { 84 return LHS->HashValue < RHS->HashValue; 85 }); 86 } 87 88 namespace { 89 class AccelTableEmitter { 90 protected: 91 AsmPrinter *const Asm; ///< Destination. 92 const AccelTableBase &Contents; ///< Data to emit. 93 94 /// Controls whether to emit duplicate hash and offset table entries for names 95 /// with identical hashes. Apple tables don't emit duplicate entries, DWARF v5 96 /// tables do. 97 const bool SkipIdenticalHashes; 98 99 void emitHashes() const; 100 101 /// Emit offsets to lists of entries with identical names. The offsets are 102 /// relative to the Base argument. 103 void emitOffsets(const MCSymbol *Base) const; 104 105 public: 106 AccelTableEmitter(AsmPrinter *Asm, const AccelTableBase &Contents, 107 bool SkipIdenticalHashes) 108 : Asm(Asm), Contents(Contents), SkipIdenticalHashes(SkipIdenticalHashes) { 109 } 110 }; 111 112 class AppleAccelTableEmitter : public AccelTableEmitter { 113 using Atom = AppleAccelTableData::Atom; 114 115 /// The fixed header of an Apple Accelerator Table. 116 struct Header { 117 uint32_t Magic = MagicHash; 118 uint16_t Version = 1; 119 uint16_t HashFunction = dwarf::DW_hash_function_djb; 120 uint32_t BucketCount; 121 uint32_t HashCount; 122 uint32_t HeaderDataLength; 123 124 /// 'HASH' magic value to detect endianness. 125 static const uint32_t MagicHash = 0x48415348; 126 127 Header(uint32_t BucketCount, uint32_t UniqueHashCount, uint32_t DataLength) 128 : BucketCount(BucketCount), HashCount(UniqueHashCount), 129 HeaderDataLength(DataLength) {} 130 131 void emit(AsmPrinter *Asm) const; 132 #ifndef NDEBUG 133 void print(raw_ostream &OS) const; 134 void dump() const { print(dbgs()); } 135 #endif 136 }; 137 138 /// The HeaderData describes the structure of an Apple accelerator table 139 /// through a list of Atoms. 140 struct HeaderData { 141 /// In the case of data that is referenced via DW_FORM_ref_* the offset 142 /// base is used to describe the offset for all forms in the list of atoms. 143 uint32_t DieOffsetBase; 144 145 const SmallVector<Atom, 4> Atoms; 146 147 HeaderData(ArrayRef<Atom> AtomList, uint32_t Offset = 0) 148 : DieOffsetBase(Offset), Atoms(AtomList.begin(), AtomList.end()) {} 149 150 void emit(AsmPrinter *Asm) const; 151 #ifndef NDEBUG 152 void print(raw_ostream &OS) const; 153 void dump() const { print(dbgs()); } 154 #endif 155 }; 156 157 Header Header; 158 HeaderData HeaderData; 159 const MCSymbol *SecBegin; 160 161 void emitBuckets() const; 162 void emitData() const; 163 164 public: 165 AppleAccelTableEmitter(AsmPrinter *Asm, const AccelTableBase &Contents, 166 ArrayRef<Atom> Atoms, const MCSymbol *SecBegin) 167 : AccelTableEmitter(Asm, Contents, true), 168 Header(Contents.getBucketCount(), Contents.getUniqueHashCount(), 169 8 + (Atoms.size() * 4)), 170 HeaderData(Atoms), SecBegin(SecBegin) {} 171 172 void emit() const; 173 174 #ifndef NDEBUG 175 void print(raw_ostream &OS) const; 176 void dump() const { print(dbgs()); } 177 #endif 178 }; 179 } // namespace 180 181 void AccelTableEmitter::emitHashes() const { 182 uint64_t PrevHash = std::numeric_limits<uint64_t>::max(); 183 unsigned BucketIdx = 0; 184 for (auto &Bucket : Contents.getBuckets()) { 185 for (auto &Hash : Bucket) { 186 uint32_t HashValue = Hash->HashValue; 187 if (SkipIdenticalHashes && PrevHash == HashValue) 188 continue; 189 Asm->OutStreamer->AddComment("Hash in Bucket " + Twine(BucketIdx)); 190 Asm->emitInt32(HashValue); 191 PrevHash = HashValue; 192 } 193 BucketIdx++; 194 } 195 } 196 197 void AccelTableEmitter::emitOffsets(const MCSymbol *Base) const { 198 const auto &Buckets = Contents.getBuckets(); 199 uint64_t PrevHash = std::numeric_limits<uint64_t>::max(); 200 for (size_t i = 0, e = Buckets.size(); i < e; ++i) { 201 for (auto *Hash : Buckets[i]) { 202 uint32_t HashValue = Hash->HashValue; 203 if (SkipIdenticalHashes && PrevHash == HashValue) 204 continue; 205 PrevHash = HashValue; 206 Asm->OutStreamer->AddComment("Offset in Bucket " + Twine(i)); 207 Asm->EmitLabelDifference(Hash->Sym, Base, sizeof(uint32_t)); 208 } 209 } 210 } 211 212 void AppleAccelTableEmitter::Header::emit(AsmPrinter *Asm) const { 213 Asm->OutStreamer->AddComment("Header Magic"); 214 Asm->emitInt32(Magic); 215 Asm->OutStreamer->AddComment("Header Version"); 216 Asm->emitInt16(Version); 217 Asm->OutStreamer->AddComment("Header Hash Function"); 218 Asm->emitInt16(HashFunction); 219 Asm->OutStreamer->AddComment("Header Bucket Count"); 220 Asm->emitInt32(BucketCount); 221 Asm->OutStreamer->AddComment("Header Hash Count"); 222 Asm->emitInt32(HashCount); 223 Asm->OutStreamer->AddComment("Header Data Length"); 224 Asm->emitInt32(HeaderDataLength); 225 } 226 227 void AppleAccelTableEmitter::HeaderData::emit(AsmPrinter *Asm) const { 228 Asm->OutStreamer->AddComment("HeaderData Die Offset Base"); 229 Asm->emitInt32(DieOffsetBase); 230 Asm->OutStreamer->AddComment("HeaderData Atom Count"); 231 Asm->emitInt32(Atoms.size()); 232 233 for (const Atom &A : Atoms) { 234 Asm->OutStreamer->AddComment(dwarf::AtomTypeString(A.Type)); 235 Asm->emitInt16(A.Type); 236 Asm->OutStreamer->AddComment(dwarf::FormEncodingString(A.Form)); 237 Asm->emitInt16(A.Form); 238 } 239 } 240 241 void AppleAccelTableEmitter::emitBuckets() const { 242 const auto &Buckets = Contents.getBuckets(); 243 unsigned index = 0; 244 for (size_t i = 0, e = Buckets.size(); i < e; ++i) { 245 Asm->OutStreamer->AddComment("Bucket " + Twine(i)); 246 if (!Buckets[i].empty()) 247 Asm->emitInt32(index); 248 else 249 Asm->emitInt32(std::numeric_limits<uint32_t>::max()); 250 // Buckets point in the list of hashes, not to the data. Do not increment 251 // the index multiple times in case of hash collisions. 252 uint64_t PrevHash = std::numeric_limits<uint64_t>::max(); 253 for (auto *HD : Buckets[i]) { 254 uint32_t HashValue = HD->HashValue; 255 if (PrevHash != HashValue) 256 ++index; 257 PrevHash = HashValue; 258 } 259 } 260 } 261 262 void AppleAccelTableEmitter::emitData() const { 263 const auto &Buckets = Contents.getBuckets(); 264 for (size_t i = 0, e = Buckets.size(); i < e; ++i) { 265 uint64_t PrevHash = std::numeric_limits<uint64_t>::max(); 266 for (auto &Hash : Buckets[i]) { 267 // Terminate the previous entry if there is no hash collision with the 268 // current one. 269 if (PrevHash != std::numeric_limits<uint64_t>::max() && 270 PrevHash != Hash->HashValue) 271 Asm->emitInt32(0); 272 // Remember to emit the label for our offset. 273 Asm->OutStreamer->EmitLabel(Hash->Sym); 274 Asm->OutStreamer->AddComment(Hash->Name.getString()); 275 Asm->emitDwarfStringOffset(Hash->Name); 276 Asm->OutStreamer->AddComment("Num DIEs"); 277 Asm->emitInt32(Hash->Values.size()); 278 for (const auto *V : Hash->Values) 279 static_cast<const AppleAccelTableData *>(V)->emit(Asm); 280 PrevHash = Hash->HashValue; 281 } 282 // Emit the final end marker for the bucket. 283 if (!Buckets[i].empty()) 284 Asm->emitInt32(0); 285 } 286 } 287 288 void AppleAccelTableEmitter::emit() const { 289 Header.emit(Asm); 290 HeaderData.emit(Asm); 291 emitBuckets(); 292 emitHashes(); 293 emitOffsets(SecBegin); 294 emitData(); 295 } 296 297 void llvm::emitAppleAccelTableImpl(AsmPrinter *Asm, AccelTableBase &Contents, 298 StringRef Prefix, const MCSymbol *SecBegin, 299 ArrayRef<AppleAccelTableData::Atom> Atoms) { 300 Contents.finalize(Asm, Prefix); 301 AppleAccelTableEmitter(Asm, Contents, Atoms, SecBegin).emit(); 302 } 303 304 void AppleAccelTableOffsetData::emit(AsmPrinter *Asm) const { 305 Asm->emitInt32(Die->getDebugSectionOffset()); 306 } 307 308 void AppleAccelTableTypeData::emit(AsmPrinter *Asm) const { 309 Asm->emitInt32(Die->getDebugSectionOffset()); 310 Asm->emitInt16(Die->getTag()); 311 Asm->emitInt8(0); 312 } 313 314 void AppleAccelTableStaticOffsetData::emit(AsmPrinter *Asm) const { 315 Asm->emitInt32(Offset); 316 } 317 318 void AppleAccelTableStaticTypeData::emit(AsmPrinter *Asm) const { 319 Asm->emitInt32(Offset); 320 Asm->emitInt16(Tag); 321 Asm->emitInt8(ObjCClassIsImplementation ? dwarf::DW_FLAG_type_implementation 322 : 0); 323 Asm->emitInt32(QualifiedNameHash); 324 } 325 326 #ifndef _MSC_VER 327 // The lines below are rejected by older versions (TBD) of MSVC. 328 constexpr AppleAccelTableData::Atom AppleAccelTableTypeData::Atoms[]; 329 constexpr AppleAccelTableData::Atom AppleAccelTableOffsetData::Atoms[]; 330 constexpr AppleAccelTableData::Atom AppleAccelTableStaticOffsetData::Atoms[]; 331 constexpr AppleAccelTableData::Atom AppleAccelTableStaticTypeData::Atoms[]; 332 #else 333 // FIXME: Erase this path once the minimum MSCV version has been bumped. 334 const SmallVector<AppleAccelTableData::Atom, 4> 335 AppleAccelTableOffsetData::Atoms = { 336 Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)}; 337 const SmallVector<AppleAccelTableData::Atom, 4> AppleAccelTableTypeData::Atoms = 338 {Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4), 339 Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2), 340 Atom(dwarf::DW_ATOM_type_flags, dwarf::DW_FORM_data1)}; 341 const SmallVector<AppleAccelTableData::Atom, 4> 342 AppleAccelTableStaticOffsetData::Atoms = { 343 Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)}; 344 const SmallVector<AppleAccelTableData::Atom, 4> 345 AppleAccelTableStaticTypeData::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(5, dwarf::DW_FORM_data1), Atom(6, dwarf::DW_FORM_data4)}; 349 #endif 350 351 #ifndef NDEBUG 352 void AppleAccelTableEmitter::Header::print(raw_ostream &OS) const { 353 OS << "Magic: " << format("0x%x", Magic) << "\n" 354 << "Version: " << Version << "\n" 355 << "Hash Function: " << HashFunction << "\n" 356 << "Bucket Count: " << BucketCount << "\n" 357 << "Header Data Length: " << HeaderDataLength << "\n"; 358 } 359 360 void AppleAccelTableData::Atom::print(raw_ostream &OS) const { 361 OS << "Type: " << dwarf::AtomTypeString(Type) << "\n" 362 << "Form: " << dwarf::FormEncodingString(Form) << "\n"; 363 } 364 365 void AppleAccelTableEmitter::HeaderData::print(raw_ostream &OS) const { 366 OS << "DIE Offset Base: " << DieOffsetBase << "\n"; 367 for (auto Atom : Atoms) 368 Atom.print(OS); 369 } 370 371 void AppleAccelTableEmitter::print(raw_ostream &OS) const { 372 Header.print(OS); 373 HeaderData.print(OS); 374 Contents.print(OS); 375 SecBegin->print(OS, nullptr); 376 } 377 378 void AccelTableBase::HashData::print(raw_ostream &OS) const { 379 OS << "Name: " << Name.getString() << "\n"; 380 OS << " Hash Value: " << format("0x%x", HashValue) << "\n"; 381 OS << " Symbol: "; 382 if (Sym) 383 OS << *Sym; 384 else 385 OS << "<none>"; 386 OS << "\n"; 387 for (auto *Value : Values) 388 Value->print(OS); 389 } 390 391 void AccelTableBase::print(raw_ostream &OS) const { 392 // Print Content. 393 OS << "Entries: \n"; 394 for (const auto &Entry : Entries) { 395 OS << "Name: " << Entry.first() << "\n"; 396 for (auto *V : Entry.second.Values) 397 V->print(OS); 398 } 399 400 OS << "Buckets and Hashes: \n"; 401 for (auto &Bucket : Buckets) 402 for (auto &Hash : Bucket) 403 Hash->print(OS); 404 405 OS << "Data: \n"; 406 for (auto &E : Entries) 407 E.second.print(OS); 408 } 409 410 void AppleAccelTableOffsetData::print(raw_ostream &OS) const { 411 OS << " Offset: " << Die->getOffset() << "\n"; 412 } 413 414 void AppleAccelTableTypeData::print(raw_ostream &OS) const { 415 OS << " Offset: " << Die->getOffset() << "\n"; 416 OS << " Tag: " << dwarf::TagString(Die->getTag()) << "\n"; 417 } 418 419 void AppleAccelTableStaticOffsetData::print(raw_ostream &OS) const { 420 OS << " Static Offset: " << Offset << "\n"; 421 } 422 423 void AppleAccelTableStaticTypeData::print(raw_ostream &OS) const { 424 OS << " Static Offset: " << Offset << "\n"; 425 OS << " QualifiedNameHash: " << format("%x\n", QualifiedNameHash) << "\n"; 426 OS << " Tag: " << dwarf::TagString(Tag) << "\n"; 427 OS << " ObjCClassIsImplementation: " 428 << (ObjCClassIsImplementation ? "true" : "false"); 429 OS << "\n"; 430 } 431 #endif 432