834 lines · cpp
1//===- llvm/CodeGen/AsmPrinter/AccelTable.cpp - Accelerator Tables --------===//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-exception6//7//===----------------------------------------------------------------------===//8//9// This file contains support for writing accelerator tables.10//11//===----------------------------------------------------------------------===//12 13#include "llvm/CodeGen/AccelTable.h"14#include "DwarfCompileUnit.h"15#include "DwarfUnit.h"16#include "llvm/ADT/DenseSet.h"17#include "llvm/ADT/STLExtras.h"18#include "llvm/ADT/Twine.h"19#include "llvm/BinaryFormat/Dwarf.h"20#include "llvm/CodeGen/AsmPrinter.h"21#include "llvm/CodeGen/DIE.h"22#include "llvm/MC/MCStreamer.h"23#include "llvm/MC/MCSymbol.h"24#include "llvm/Support/raw_ostream.h"25#include "llvm/Target/TargetLoweringObjectFile.h"26#include <cstddef>27#include <cstdint>28#include <limits>29#include <vector>30 31using namespace llvm;32 33void AccelTableBase::computeBucketCount() {34 SmallVector<uint32_t, 0> Uniques;35 Uniques.reserve(Entries.size());36 for (const auto &E : Entries)37 Uniques.push_back(E.second.HashValue);38 llvm::sort(Uniques);39 UniqueHashCount = llvm::unique(Uniques) - Uniques.begin();40 BucketCount = dwarf::getDebugNamesBucketCount(UniqueHashCount);41}42 43void AccelTableBase::finalize(AsmPrinter *Asm, StringRef Prefix) {44 // Create the individual hash data outputs.45 for (auto &E : Entries) {46 // Unique the entries.47 llvm::stable_sort(E.second.Values,48 [](const AccelTableData *A, const AccelTableData *B) {49 return *A < *B;50 });51 E.second.Values.erase(llvm::unique(E.second.Values), E.second.Values.end());52 }53 54 // Figure out how many buckets we need, then compute the bucket contents and55 // the final ordering. The hashes and offsets can be emitted by walking these56 // data structures. We add temporary symbols to the data so they can be57 // referenced when emitting the offsets.58 computeBucketCount();59 60 // Compute bucket contents and final ordering.61 Buckets.resize(BucketCount);62 for (auto &E : Entries) {63 uint32_t Bucket = E.second.HashValue % BucketCount;64 Buckets[Bucket].push_back(&E.second);65 E.second.Sym = Asm->createTempSymbol(Prefix);66 }67 68 // Sort the contents of the buckets by hash value so that hash collisions end69 // up together. Stable sort makes testing easier and doesn't cost much more.70 for (auto &Bucket : Buckets)71 llvm::stable_sort(Bucket, [](HashData *LHS, HashData *RHS) {72 return LHS->HashValue < RHS->HashValue;73 });74}75 76namespace {77/// Base class for writing out Accelerator tables. It holds the common78/// functionality for the two Accelerator table types.79class AccelTableWriter {80protected:81 AsmPrinter *const Asm; ///< Destination.82 const AccelTableBase &Contents; ///< Data to emit.83 84 /// Controls whether to emit duplicate hash and offset table entries for names85 /// with identical hashes. Apple tables don't emit duplicate entries, DWARF v586 /// tables do.87 const bool SkipIdenticalHashes;88 89 void emitHashes() const;90 91 /// Emit offsets to lists of entries with identical names. The offsets are92 /// relative to the Base argument.93 void emitOffsets(const MCSymbol *Base) const;94 95public:96 AccelTableWriter(AsmPrinter *Asm, const AccelTableBase &Contents,97 bool SkipIdenticalHashes)98 : Asm(Asm), Contents(Contents), SkipIdenticalHashes(SkipIdenticalHashes) {99 }100};101 102class AppleAccelTableWriter : public AccelTableWriter {103 using Atom = AppleAccelTableData::Atom;104 105 /// The fixed header of an Apple Accelerator Table.106 struct Header {107 uint32_t Magic = MagicHash;108 uint16_t Version = 1;109 uint16_t HashFunction = dwarf::DW_hash_function_djb;110 uint32_t BucketCount;111 uint32_t HashCount;112 uint32_t HeaderDataLength;113 114 /// 'HASH' magic value to detect endianness.115 static const uint32_t MagicHash = 0x48415348;116 117 Header(uint32_t BucketCount, uint32_t UniqueHashCount, uint32_t DataLength)118 : BucketCount(BucketCount), HashCount(UniqueHashCount),119 HeaderDataLength(DataLength) {}120 121 void emit(AsmPrinter *Asm) const;122#ifndef NDEBUG123 void print(raw_ostream &OS) const;124 void dump() const { print(dbgs()); }125#endif126 };127 128 /// The HeaderData describes the structure of an Apple accelerator table129 /// through a list of Atoms.130 struct HeaderData {131 /// In the case of data that is referenced via DW_FORM_ref_* the offset132 /// base is used to describe the offset for all forms in the list of atoms.133 uint32_t DieOffsetBase;134 135 const SmallVector<Atom, 4> Atoms;136 137 HeaderData(ArrayRef<Atom> AtomList, uint32_t Offset = 0)138 : DieOffsetBase(Offset), Atoms(AtomList) {}139 140 void emit(AsmPrinter *Asm) const;141#ifndef NDEBUG142 void print(raw_ostream &OS) const;143 void dump() const { print(dbgs()); }144#endif145 };146 147 Header Header;148 HeaderData HeaderData;149 const MCSymbol *SecBegin;150 151 void emitBuckets() const;152 void emitData() const;153 154public:155 AppleAccelTableWriter(AsmPrinter *Asm, const AccelTableBase &Contents,156 ArrayRef<Atom> Atoms, const MCSymbol *SecBegin)157 : AccelTableWriter(Asm, Contents, true),158 Header(Contents.getBucketCount(), Contents.getUniqueHashCount(),159 8 + (Atoms.size() * 4)),160 HeaderData(Atoms), SecBegin(SecBegin) {}161 162 void emit() const;163 164#ifndef NDEBUG165 void print(raw_ostream &OS) const;166 void dump() const { print(dbgs()); }167#endif168};169 170/// Class responsible for emitting a DWARF v5 Accelerator Table. The only171/// public function is emit(), which performs the actual emission.172///173/// A callback abstracts the logic to provide a CU index for a given entry.174class Dwarf5AccelTableWriter : public AccelTableWriter {175 struct Header {176 uint16_t Version = 5;177 uint16_t Padding = 0;178 uint32_t CompUnitCount;179 uint32_t LocalTypeUnitCount = 0;180 uint32_t ForeignTypeUnitCount = 0;181 uint32_t BucketCount = 0;182 uint32_t NameCount = 0;183 uint32_t AbbrevTableSize = 0;184 uint32_t AugmentationStringSize = sizeof(AugmentationString);185 char AugmentationString[8] = {'L', 'L', 'V', 'M', '0', '7', '0', '0'};186 187 Header(uint32_t CompUnitCount, uint32_t LocalTypeUnitCount,188 uint32_t ForeignTypeUnitCount, uint32_t BucketCount,189 uint32_t NameCount)190 : CompUnitCount(CompUnitCount), LocalTypeUnitCount(LocalTypeUnitCount),191 ForeignTypeUnitCount(ForeignTypeUnitCount), BucketCount(BucketCount),192 NameCount(NameCount) {}193 194 void emit(Dwarf5AccelTableWriter &Ctx);195 };196 197 Header Header;198 /// FoldingSet that uniques the abbreviations.199 FoldingSet<DebugNamesAbbrev> AbbreviationsSet;200 /// Vector containing DebugNames abbreviations for iteration in order.201 SmallVector<DebugNamesAbbrev *, 5> AbbreviationsVector;202 /// The bump allocator to use when creating DIEAbbrev objects in the uniqued203 /// storage container.204 BumpPtrAllocator Alloc;205 ArrayRef<std::variant<MCSymbol *, uint64_t>> CompUnits;206 ArrayRef<std::variant<MCSymbol *, uint64_t>> TypeUnits;207 llvm::function_ref<std::optional<DWARF5AccelTable::UnitIndexAndEncoding>(208 const DWARF5AccelTableData &)>209 getIndexForEntry;210 MCSymbol *ContributionEnd = nullptr;211 MCSymbol *AbbrevStart = Asm->createTempSymbol("names_abbrev_start");212 MCSymbol *AbbrevEnd = Asm->createTempSymbol("names_abbrev_end");213 MCSymbol *EntryPool = Asm->createTempSymbol("names_entries");214 // Indicates if this module is built with Split Dwarf enabled.215 bool IsSplitDwarf = false;216 /// Stores the DIE offsets which are indexed by this table.217 DenseSet<OffsetAndUnitID> IndexedOffsets;218 219 void populateAbbrevsMap();220 221 void emitCUList() const;222 void emitTUList() const;223 void emitBuckets() const;224 void emitStringOffsets() const;225 void emitAbbrevs() const;226 void emitEntry(227 const DWARF5AccelTableData &Entry,228 const DenseMap<OffsetAndUnitID, MCSymbol *> &DIEOffsetToAccelEntryLabel,229 DenseSet<MCSymbol *> &EmittedAccelEntrySymbols);230 void emitData();231 232public:233 Dwarf5AccelTableWriter(234 AsmPrinter *Asm, const AccelTableBase &Contents,235 ArrayRef<std::variant<MCSymbol *, uint64_t>> CompUnits,236 ArrayRef<std::variant<MCSymbol *, uint64_t>> TypeUnits,237 llvm::function_ref<std::optional<DWARF5AccelTable::UnitIndexAndEncoding>(238 const DWARF5AccelTableData &)>239 getIndexForEntry,240 bool IsSplitDwarf);241 ~Dwarf5AccelTableWriter() {242 for (DebugNamesAbbrev *Abbrev : AbbreviationsVector)243 Abbrev->~DebugNamesAbbrev();244 }245 void emit();246};247} // namespace248 249void AccelTableWriter::emitHashes() const {250 uint64_t PrevHash = std::numeric_limits<uint64_t>::max();251 unsigned BucketIdx = 0;252 for (const auto &Bucket : Contents.getBuckets()) {253 for (const auto &Hash : Bucket) {254 uint32_t HashValue = Hash->HashValue;255 if (SkipIdenticalHashes && PrevHash == HashValue)256 continue;257 Asm->OutStreamer->AddComment("Hash in Bucket " + Twine(BucketIdx));258 Asm->emitInt32(HashValue);259 PrevHash = HashValue;260 }261 BucketIdx++;262 }263}264 265void AccelTableWriter::emitOffsets(const MCSymbol *Base) const {266 const auto &Buckets = Contents.getBuckets();267 uint64_t PrevHash = std::numeric_limits<uint64_t>::max();268 for (size_t i = 0, e = Buckets.size(); i < e; ++i) {269 for (auto *Hash : Buckets[i]) {270 uint32_t HashValue = Hash->HashValue;271 if (SkipIdenticalHashes && PrevHash == HashValue)272 continue;273 PrevHash = HashValue;274 Asm->OutStreamer->AddComment("Offset in Bucket " + Twine(i));275 Asm->emitLabelDifference(Hash->Sym, Base, Asm->getDwarfOffsetByteSize());276 }277 }278}279 280void AppleAccelTableWriter::Header::emit(AsmPrinter *Asm) const {281 Asm->OutStreamer->AddComment("Header Magic");282 Asm->emitInt32(Magic);283 Asm->OutStreamer->AddComment("Header Version");284 Asm->emitInt16(Version);285 Asm->OutStreamer->AddComment("Header Hash Function");286 Asm->emitInt16(HashFunction);287 Asm->OutStreamer->AddComment("Header Bucket Count");288 Asm->emitInt32(BucketCount);289 Asm->OutStreamer->AddComment("Header Hash Count");290 Asm->emitInt32(HashCount);291 Asm->OutStreamer->AddComment("Header Data Length");292 Asm->emitInt32(HeaderDataLength);293}294 295void AppleAccelTableWriter::HeaderData::emit(AsmPrinter *Asm) const {296 Asm->OutStreamer->AddComment("HeaderData Die Offset Base");297 Asm->emitInt32(DieOffsetBase);298 Asm->OutStreamer->AddComment("HeaderData Atom Count");299 Asm->emitInt32(Atoms.size());300 301 for (const Atom &A : Atoms) {302 Asm->OutStreamer->AddComment(dwarf::AtomTypeString(A.Type));303 Asm->emitInt16(A.Type);304 Asm->OutStreamer->AddComment(dwarf::FormEncodingString(A.Form));305 Asm->emitInt16(A.Form);306 }307}308 309void AppleAccelTableWriter::emitBuckets() const {310 const auto &Buckets = Contents.getBuckets();311 unsigned index = 0;312 for (size_t i = 0, e = Buckets.size(); i < e; ++i) {313 Asm->OutStreamer->AddComment("Bucket " + Twine(i));314 if (!Buckets[i].empty())315 Asm->emitInt32(index);316 else317 Asm->emitInt32(std::numeric_limits<uint32_t>::max());318 // Buckets point in the list of hashes, not to the data. Do not increment319 // the index multiple times in case of hash collisions.320 uint64_t PrevHash = std::numeric_limits<uint64_t>::max();321 for (auto *HD : Buckets[i]) {322 uint32_t HashValue = HD->HashValue;323 if (PrevHash != HashValue)324 ++index;325 PrevHash = HashValue;326 }327 }328}329 330void AppleAccelTableWriter::emitData() const {331 const auto &Buckets = Contents.getBuckets();332 for (const AccelTableBase::HashList &Bucket : Buckets) {333 uint64_t PrevHash = std::numeric_limits<uint64_t>::max();334 for (const auto &Hash : Bucket) {335 // Terminate the previous entry if there is no hash collision with the336 // current one.337 if (PrevHash != std::numeric_limits<uint64_t>::max() &&338 PrevHash != Hash->HashValue)339 Asm->emitInt32(0);340 // Remember to emit the label for our offset.341 Asm->OutStreamer->emitLabel(Hash->Sym);342 Asm->OutStreamer->AddComment(Hash->Name.getString());343 Asm->emitDwarfStringOffset(Hash->Name);344 Asm->OutStreamer->AddComment("Num DIEs");345 Asm->emitInt32(Hash->Values.size());346 for (const auto *V : Hash->getValues<const AppleAccelTableData *>())347 V->emit(Asm);348 PrevHash = Hash->HashValue;349 }350 // Emit the final end marker for the bucket.351 if (!Bucket.empty())352 Asm->emitInt32(0);353 }354}355 356void AppleAccelTableWriter::emit() const {357 Header.emit(Asm);358 HeaderData.emit(Asm);359 emitBuckets();360 emitHashes();361 emitOffsets(SecBegin);362 emitData();363}364 365DWARF5AccelTableData::DWARF5AccelTableData(const DIE &Die,366 const uint32_t UnitID,367 const bool IsTU)368 : OffsetVal(&Die), DieTag(Die.getTag()), AbbrevNumber(0), IsTU(IsTU),369 UnitID(UnitID) {}370 371void Dwarf5AccelTableWriter::Header::emit(Dwarf5AccelTableWriter &Ctx) {372 assert(CompUnitCount > 0 && "Index must have at least one CU.");373 374 AsmPrinter *Asm = Ctx.Asm;375 Ctx.ContributionEnd =376 Asm->emitDwarfUnitLength("names", "Header: unit length");377 Asm->OutStreamer->AddComment("Header: version");378 Asm->emitInt16(Version);379 Asm->OutStreamer->AddComment("Header: padding");380 Asm->emitInt16(Padding);381 Asm->OutStreamer->AddComment("Header: compilation unit count");382 Asm->emitInt32(CompUnitCount);383 Asm->OutStreamer->AddComment("Header: local type unit count");384 Asm->emitInt32(LocalTypeUnitCount);385 Asm->OutStreamer->AddComment("Header: foreign type unit count");386 Asm->emitInt32(ForeignTypeUnitCount);387 Asm->OutStreamer->AddComment("Header: bucket count");388 Asm->emitInt32(BucketCount);389 Asm->OutStreamer->AddComment("Header: name count");390 Asm->emitInt32(NameCount);391 Asm->OutStreamer->AddComment("Header: abbreviation table size");392 Asm->emitLabelDifference(Ctx.AbbrevEnd, Ctx.AbbrevStart, sizeof(uint32_t));393 Asm->OutStreamer->AddComment("Header: augmentation string size");394 assert(AugmentationStringSize % 4 == 0);395 Asm->emitInt32(AugmentationStringSize);396 Asm->OutStreamer->AddComment("Header: augmentation string");397 Asm->OutStreamer->emitBytes({AugmentationString, AugmentationStringSize});398}399 400std::optional<uint64_t>401DWARF5AccelTableData::getDefiningParentDieOffset(const DIE &Die) {402 if (auto *Parent = Die.getParent();403 Parent && !Parent->findAttribute(dwarf::Attribute::DW_AT_declaration))404 return Parent->getOffset();405 return {};406}407 408static std::optional<dwarf::Form>409getFormForIdxParent(const DenseSet<OffsetAndUnitID> &IndexedOffsets,410 std::optional<OffsetAndUnitID> ParentOffset) {411 // No parent information412 if (!ParentOffset)413 return std::nullopt;414 // Parent is indexed by this table.415 if (IndexedOffsets.contains(*ParentOffset))416 return dwarf::Form::DW_FORM_ref4;417 // Parent is not indexed by this table.418 return dwarf::Form::DW_FORM_flag_present;419}420 421void DebugNamesAbbrev::Profile(FoldingSetNodeID &ID) const {422 ID.AddInteger(DieTag);423 for (const DebugNamesAbbrev::AttributeEncoding &Enc : AttrVect) {424 ID.AddInteger(Enc.Index);425 ID.AddInteger(Enc.Form);426 }427}428 429void Dwarf5AccelTableWriter::populateAbbrevsMap() {430 for (auto &Bucket : Contents.getBuckets()) {431 for (auto *Hash : Bucket) {432 for (auto *Value : Hash->getValues<DWARF5AccelTableData *>()) {433 std::optional<DWARF5AccelTable::UnitIndexAndEncoding> EntryRet =434 getIndexForEntry(*Value);435 std::optional<dwarf::Form> MaybeParentForm = getFormForIdxParent(436 IndexedOffsets, Value->getParentDieOffsetAndUnitID());437 DebugNamesAbbrev Abbrev(Value->getDieTag());438 if (EntryRet)439 Abbrev.addAttribute(EntryRet->Encoding);440 Abbrev.addAttribute({dwarf::DW_IDX_die_offset, dwarf::DW_FORM_ref4});441 if (MaybeParentForm)442 Abbrev.addAttribute({dwarf::DW_IDX_parent, *MaybeParentForm});443 FoldingSetNodeID ID;444 Abbrev.Profile(ID);445 void *InsertPos;446 if (DebugNamesAbbrev *Existing =447 AbbreviationsSet.FindNodeOrInsertPos(ID, InsertPos)) {448 Value->setAbbrevNumber(Existing->getNumber());449 continue;450 }451 DebugNamesAbbrev *NewAbbrev =452 new (Alloc) DebugNamesAbbrev(std::move(Abbrev));453 AbbreviationsVector.push_back(NewAbbrev);454 NewAbbrev->setNumber(AbbreviationsVector.size());455 AbbreviationsSet.InsertNode(NewAbbrev, InsertPos);456 Value->setAbbrevNumber(NewAbbrev->getNumber());457 }458 }459 }460}461 462void Dwarf5AccelTableWriter::emitCUList() const {463 for (const auto &CU : enumerate(CompUnits)) {464 Asm->OutStreamer->AddComment("Compilation unit " + Twine(CU.index()));465 if (std::holds_alternative<MCSymbol *>(CU.value()))466 Asm->emitDwarfSymbolReference(std::get<MCSymbol *>(CU.value()));467 else468 Asm->emitDwarfLengthOrOffset(std::get<uint64_t>(CU.value()));469 }470}471 472void Dwarf5AccelTableWriter::emitTUList() const {473 for (const auto &TU : enumerate(TypeUnits)) {474 Asm->OutStreamer->AddComment("Type unit " + Twine(TU.index()));475 if (std::holds_alternative<MCSymbol *>(TU.value()))476 Asm->emitDwarfSymbolReference(std::get<MCSymbol *>(TU.value()));477 else if (IsSplitDwarf)478 Asm->emitInt64(std::get<uint64_t>(TU.value()));479 else480 Asm->emitDwarfLengthOrOffset(std::get<uint64_t>(TU.value()));481 }482}483 484void Dwarf5AccelTableWriter::emitBuckets() const {485 uint32_t Index = 1;486 for (const auto &Bucket : enumerate(Contents.getBuckets())) {487 Asm->OutStreamer->AddComment("Bucket " + Twine(Bucket.index()));488 Asm->emitInt32(Bucket.value().empty() ? 0 : Index);489 Index += Bucket.value().size();490 }491}492 493void Dwarf5AccelTableWriter::emitStringOffsets() const {494 for (const auto &Bucket : enumerate(Contents.getBuckets())) {495 for (auto *Hash : Bucket.value()) {496 DwarfStringPoolEntryRef String = Hash->Name;497 Asm->OutStreamer->AddComment("String in Bucket " + Twine(Bucket.index()) +498 ": " + String.getString());499 Asm->emitDwarfStringOffset(String);500 }501 }502}503 504void Dwarf5AccelTableWriter::emitAbbrevs() const {505 Asm->OutStreamer->emitLabel(AbbrevStart);506 for (const DebugNamesAbbrev *Abbrev : AbbreviationsVector) {507 Asm->OutStreamer->AddComment("Abbrev code");508 Asm->emitULEB128(Abbrev->getNumber());509 Asm->OutStreamer->AddComment(dwarf::TagString(Abbrev->getDieTag()));510 Asm->emitULEB128(Abbrev->getDieTag());511 for (const DebugNamesAbbrev::AttributeEncoding &AttrEnc :512 Abbrev->getAttributes()) {513 Asm->emitULEB128(AttrEnc.Index, dwarf::IndexString(AttrEnc.Index).data());514 Asm->emitULEB128(AttrEnc.Form,515 dwarf::FormEncodingString(AttrEnc.Form).data());516 }517 Asm->emitULEB128(0, "End of abbrev");518 Asm->emitULEB128(0, "End of abbrev");519 }520 Asm->emitULEB128(0, "End of abbrev list");521 Asm->OutStreamer->emitLabel(AbbrevEnd);522}523 524void Dwarf5AccelTableWriter::emitEntry(525 const DWARF5AccelTableData &Entry,526 const DenseMap<OffsetAndUnitID, MCSymbol *> &DIEOffsetToAccelEntryLabel,527 DenseSet<MCSymbol *> &EmittedAccelEntrySymbols) {528 unsigned AbbrevIndex = Entry.getAbbrevNumber() - 1;529 assert(AbbrevIndex < AbbreviationsVector.size() &&530 "Entry abbrev index is outside of abbreviations vector range.");531 DebugNamesAbbrev *Abbrev = AbbreviationsVector[AbbrevIndex];532 std::optional<DWARF5AccelTable::UnitIndexAndEncoding> EntryRet =533 getIndexForEntry(Entry);534 std::optional<OffsetAndUnitID> MaybeParentOffset =535 Entry.getParentDieOffsetAndUnitID();536 auto EntrySymbolIt =537 DIEOffsetToAccelEntryLabel.find(Entry.getDieOffsetAndUnitID());538 assert(EntrySymbolIt != DIEOffsetToAccelEntryLabel.end());539 MCSymbol *EntrySymbol = EntrySymbolIt->getSecond();540 541 // Emit the label for this Entry, so that IDX_parents may refer to it.542 // Note: a DIE may have multiple accelerator Entries; this check avoids543 // creating/emitting multiple labels for the same DIE.544 if (EmittedAccelEntrySymbols.insert(EntrySymbol).second)545 Asm->OutStreamer->emitLabel(EntrySymbol);546 547 Asm->emitULEB128(Entry.getAbbrevNumber(), "Abbreviation code");548 549 for (const DebugNamesAbbrev::AttributeEncoding &AttrEnc :550 Abbrev->getAttributes()) {551 Asm->OutStreamer->AddComment(dwarf::IndexString(AttrEnc.Index));552 switch (AttrEnc.Index) {553 case dwarf::DW_IDX_compile_unit:554 case dwarf::DW_IDX_type_unit: {555 DIEInteger ID(EntryRet->Index);556 ID.emitValue(Asm, AttrEnc.Form);557 break;558 }559 case dwarf::DW_IDX_die_offset:560 assert(AttrEnc.Form == dwarf::DW_FORM_ref4);561 Asm->emitInt32(Entry.getDieOffset());562 break;563 case dwarf::DW_IDX_parent: {564 if (AttrEnc.Form == dwarf::Form::DW_FORM_flag_present)565 break;566 auto ParentSymbolIt = DIEOffsetToAccelEntryLabel.find(*MaybeParentOffset);567 assert(ParentSymbolIt != DIEOffsetToAccelEntryLabel.end());568 Asm->emitLabelDifference(ParentSymbolIt->getSecond(), EntryPool, 4);569 break;570 }571 default:572 llvm_unreachable("Unexpected index attribute!");573 }574 }575}576 577void Dwarf5AccelTableWriter::emitData() {578 DenseMap<OffsetAndUnitID, MCSymbol *> DIEOffsetToAccelEntryLabel;579 580 for (OffsetAndUnitID Offset : IndexedOffsets)581 DIEOffsetToAccelEntryLabel.insert({Offset, Asm->createTempSymbol("")});582 583 Asm->OutStreamer->emitLabel(EntryPool);584 DenseSet<MCSymbol *> EmittedAccelEntrySymbols;585 for (auto &Bucket : Contents.getBuckets()) {586 for (auto *Hash : Bucket) {587 // Remember to emit the label for our offset.588 Asm->OutStreamer->emitLabel(Hash->Sym);589 for (const auto *Value : Hash->getValues<DWARF5AccelTableData *>())590 emitEntry(*Value, DIEOffsetToAccelEntryLabel, EmittedAccelEntrySymbols);591 Asm->OutStreamer->AddComment("End of list: " + Hash->Name.getString());592 Asm->emitInt8(0);593 }594 }595}596 597Dwarf5AccelTableWriter::Dwarf5AccelTableWriter(598 AsmPrinter *Asm, const AccelTableBase &Contents,599 ArrayRef<std::variant<MCSymbol *, uint64_t>> CompUnits,600 ArrayRef<std::variant<MCSymbol *, uint64_t>> TypeUnits,601 llvm::function_ref<std::optional<DWARF5AccelTable::UnitIndexAndEncoding>(602 const DWARF5AccelTableData &)>603 getIndexForEntry,604 bool IsSplitDwarf)605 : AccelTableWriter(Asm, Contents, false),606 Header(CompUnits.size(), IsSplitDwarf ? 0 : TypeUnits.size(),607 IsSplitDwarf ? TypeUnits.size() : 0, Contents.getBucketCount(),608 Contents.getUniqueNameCount()),609 CompUnits(CompUnits), TypeUnits(TypeUnits),610 getIndexForEntry(std::move(getIndexForEntry)),611 IsSplitDwarf(IsSplitDwarf) {612 613 for (auto &Bucket : Contents.getBuckets())614 for (auto *Hash : Bucket)615 for (auto *Value : Hash->getValues<DWARF5AccelTableData *>())616 IndexedOffsets.insert(Value->getDieOffsetAndUnitID());617 618 populateAbbrevsMap();619}620 621void Dwarf5AccelTableWriter::emit() {622 Header.emit(*this);623 emitCUList();624 emitTUList();625 emitBuckets();626 emitHashes();627 emitStringOffsets();628 emitOffsets(EntryPool);629 emitAbbrevs();630 emitData();631 Asm->OutStreamer->emitValueToAlignment(Align(4), 0);632 Asm->OutStreamer->emitLabel(ContributionEnd);633}634 635void llvm::emitAppleAccelTableImpl(AsmPrinter *Asm, AccelTableBase &Contents,636 StringRef Prefix, const MCSymbol *SecBegin,637 ArrayRef<AppleAccelTableData::Atom> Atoms) {638 Contents.finalize(Asm, Prefix);639 AppleAccelTableWriter(Asm, Contents, Atoms, SecBegin).emit();640}641 642void llvm::emitDWARF5AccelTable(643 AsmPrinter *Asm, DWARF5AccelTable &Contents, const DwarfDebug &DD,644 ArrayRef<std::unique_ptr<DwarfCompileUnit>> CUs) {645 TUVectorTy TUSymbols = Contents.getTypeUnitsSymbols();646 std::vector<std::variant<MCSymbol *, uint64_t>> CompUnits;647 std::vector<std::variant<MCSymbol *, uint64_t>> TypeUnits;648 SmallVector<unsigned, 1> CUIndex(CUs.size());649 DenseMap<unsigned, unsigned> TUIndex(TUSymbols.size());650 int CUCount = 0;651 int TUCount = 0;652 for (const auto &CU : enumerate(CUs)) {653 switch (CU.value()->getCUNode()->getNameTableKind()) {654 case DICompileUnit::DebugNameTableKind::Default:655 case DICompileUnit::DebugNameTableKind::Apple:656 break;657 default:658 continue;659 }660 CUIndex[CU.index()] = CUCount++;661 assert(CU.index() == CU.value()->getUniqueID());662 const DwarfCompileUnit *MainCU =663 DD.useSplitDwarf() ? CU.value()->getSkeleton() : CU.value().get();664 CompUnits.push_back(MainCU->getLabelBegin());665 }666 667 for (const auto &TU : TUSymbols) {668 TUIndex[TU.UniqueID] = TUCount++;669 if (DD.useSplitDwarf())670 TypeUnits.push_back(std::get<uint64_t>(TU.LabelOrSignature));671 else672 TypeUnits.push_back(std::get<MCSymbol *>(TU.LabelOrSignature));673 }674 675 if (CompUnits.empty())676 return;677 678 Asm->OutStreamer->switchSection(679 Asm->getObjFileLowering().getDwarfDebugNamesSection());680 681 Contents.finalize(Asm, "names");682 dwarf::Form CUIndexForm =683 DIEInteger::BestForm(/*IsSigned*/ false, CompUnits.size() - 1);684 dwarf::Form TUIndexForm =685 DIEInteger::BestForm(/*IsSigned*/ false, TypeUnits.size() - 1);686 Dwarf5AccelTableWriter(687 Asm, Contents, CompUnits, TypeUnits,688 [&](const DWARF5AccelTableData &Entry)689 -> std::optional<DWARF5AccelTable::UnitIndexAndEncoding> {690 if (Entry.isTU())691 return {{TUIndex[Entry.getUnitID()],692 {dwarf::DW_IDX_type_unit, TUIndexForm}}};693 if (CUIndex.size() > 1)694 return {{CUIndex[Entry.getUnitID()],695 {dwarf::DW_IDX_compile_unit, CUIndexForm}}};696 return std::nullopt;697 },698 DD.useSplitDwarf())699 .emit();700}701 702void DWARF5AccelTable::addTypeUnitSymbol(DwarfTypeUnit &U) {703 TUSymbolsOrHashes.push_back({U.getLabelBegin(), U.getUniqueID()});704}705 706void DWARF5AccelTable::addTypeUnitSignature(DwarfTypeUnit &U) {707 TUSymbolsOrHashes.push_back({U.getTypeSignature(), U.getUniqueID()});708}709 710void llvm::emitDWARF5AccelTable(711 AsmPrinter *Asm, DWARF5AccelTable &Contents,712 ArrayRef<std::variant<MCSymbol *, uint64_t>> CUs,713 llvm::function_ref<std::optional<DWARF5AccelTable::UnitIndexAndEncoding>(714 const DWARF5AccelTableData &)>715 getIndexForEntry) {716 std::vector<std::variant<MCSymbol *, uint64_t>> TypeUnits;717 Contents.finalize(Asm, "names");718 Dwarf5AccelTableWriter(Asm, Contents, CUs, TypeUnits, getIndexForEntry, false)719 .emit();720}721 722void AppleAccelTableOffsetData::emit(AsmPrinter *Asm) const {723 assert(Die.getDebugSectionOffset() <= UINT32_MAX &&724 "The section offset exceeds the limit.");725 Asm->emitInt32(Die.getDebugSectionOffset());726}727 728void AppleAccelTableTypeData::emit(AsmPrinter *Asm) const {729 assert(Die.getDebugSectionOffset() <= UINT32_MAX &&730 "The section offset exceeds the limit.");731 Asm->emitInt32(Die.getDebugSectionOffset());732 Asm->emitInt16(Die.getTag());733 Asm->emitInt8(0);734}735 736void AppleAccelTableStaticOffsetData::emit(AsmPrinter *Asm) const {737 Asm->emitInt32(Offset);738}739 740void AppleAccelTableStaticTypeData::emit(AsmPrinter *Asm) const {741 Asm->emitInt32(Offset);742 Asm->emitInt16(Tag);743 Asm->emitInt8(ObjCClassIsImplementation ? dwarf::DW_FLAG_type_implementation744 : 0);745 Asm->emitInt32(QualifiedNameHash);746}747 748#ifndef NDEBUG749void AppleAccelTableWriter::Header::print(raw_ostream &OS) const {750 OS << "Magic: " << format("0x%x", Magic) << "\n"751 << "Version: " << Version << "\n"752 << "Hash Function: " << HashFunction << "\n"753 << "Bucket Count: " << BucketCount << "\n"754 << "Header Data Length: " << HeaderDataLength << "\n";755}756 757void AppleAccelTableData::Atom::print(raw_ostream &OS) const {758 OS << "Type: " << dwarf::AtomTypeString(Type) << "\n"759 << "Form: " << dwarf::FormEncodingString(Form) << "\n";760}761 762void AppleAccelTableWriter::HeaderData::print(raw_ostream &OS) const {763 OS << "DIE Offset Base: " << DieOffsetBase << "\n";764 for (auto Atom : Atoms)765 Atom.print(OS);766}767 768void AppleAccelTableWriter::print(raw_ostream &OS) const {769 Header.print(OS);770 HeaderData.print(OS);771 Contents.print(OS);772 SecBegin->print(OS, nullptr);773}774 775void AccelTableBase::HashData::print(raw_ostream &OS) const {776 OS << "Name: " << Name.getString() << "\n";777 OS << " Hash Value: " << format("0x%x", HashValue) << "\n";778 OS << " Symbol: ";779 if (Sym)780 OS << *Sym;781 else782 OS << "<none>";783 OS << "\n";784 for (auto *Value : Values)785 Value->print(OS);786}787 788void AccelTableBase::print(raw_ostream &OS) const {789 // Print Content.790 OS << "Entries: \n";791 for (const auto &[Name, Data] : Entries) {792 OS << "Name: " << Name << "\n";793 for (auto *V : Data.Values)794 V->print(OS);795 }796 797 OS << "Buckets and Hashes: \n";798 for (const auto &Bucket : Buckets)799 for (const auto &Hash : Bucket)800 Hash->print(OS);801 802 OS << "Data: \n";803 for (const auto &E : Entries)804 E.second.print(OS);805}806 807void DWARF5AccelTableData::print(raw_ostream &OS) const {808 OS << " Offset: " << getDieOffset() << "\n";809 OS << " Tag: " << dwarf::TagString(getDieTag()) << "\n";810}811 812void AppleAccelTableOffsetData::print(raw_ostream &OS) const {813 OS << " Offset: " << Die.getOffset() << "\n";814}815 816void AppleAccelTableTypeData::print(raw_ostream &OS) const {817 OS << " Offset: " << Die.getOffset() << "\n";818 OS << " Tag: " << dwarf::TagString(Die.getTag()) << "\n";819}820 821void AppleAccelTableStaticOffsetData::print(raw_ostream &OS) const {822 OS << " Static Offset: " << Offset << "\n";823}824 825void AppleAccelTableStaticTypeData::print(raw_ostream &OS) const {826 OS << " Static Offset: " << Offset << "\n";827 OS << " QualifiedNameHash: " << format("%x\n", QualifiedNameHash) << "\n";828 OS << " Tag: " << dwarf::TagString(Tag) << "\n";829 OS << " ObjCClassIsImplementation: "830 << (ObjCClassIsImplementation ? "true" : "false");831 OS << "\n";832}833#endif834