diff options
Diffstat (limited to 'llvm/lib')
| -rw-r--r-- | llvm/lib/CodeGen/AsmPrinter/AccelTable.cpp | 383 | ||||
| -rw-r--r-- | llvm/lib/CodeGen/AsmPrinter/DwarfDebug.cpp | 6 | ||||
| -rw-r--r-- | llvm/lib/CodeGen/AsmPrinter/DwarfDebug.h | 8 |
3 files changed, 242 insertions, 155 deletions
diff --git a/llvm/lib/CodeGen/AsmPrinter/AccelTable.cpp b/llvm/lib/CodeGen/AsmPrinter/AccelTable.cpp index 3ecef5d8a19..ff70beb1613 100644 --- a/llvm/lib/CodeGen/AsmPrinter/AccelTable.cpp +++ b/llvm/lib/CodeGen/AsmPrinter/AccelTable.cpp @@ -29,29 +29,208 @@ using namespace llvm; -void AppleAccelTableHeader::emit(AsmPrinter *Asm) { - // Emit Header. +void AccelTableBase::computeBucketCount() { + // First get the number of unique hashes. + std::vector<uint32_t> Uniques; + Uniques.reserve(Entries.size()); + for (const auto &E : Entries) + Uniques.push_back(E.second.HashValue); + array_pod_sort(Uniques.begin(), Uniques.end()); + std::vector<uint32_t>::iterator P = + std::unique(Uniques.begin(), Uniques.end()); + + UniqueHashCount = std::distance(Uniques.begin(), P); + + if (UniqueHashCount > 1024) + BucketCount = UniqueHashCount / 4; + else if (UniqueHashCount > 16) + BucketCount = UniqueHashCount / 2; + else + BucketCount = std::max<uint32_t>(UniqueHashCount, 1); +} + +void AccelTableBase::finalize(AsmPrinter *Asm, StringRef Prefix) { + // Create the individual hash data outputs. + for (auto &E : Entries) { + // Unique the entries. + std::stable_sort(E.second.Values.begin(), E.second.Values.end(), + [](const AccelTableData *A, const AccelTableData *B) { + return *A < *B; + }); + E.second.Values.erase( + std::unique(E.second.Values.begin(), E.second.Values.end()), + E.second.Values.end()); + } + + // Figure out how many buckets we need, then compute the bucket contents and + // the final ordering. The hashes and offsets can be emitted by walking these + // data structures. We add temporary symbols to the data so they can be + // referenced when emitting the offsets. + computeBucketCount(); + + // Compute bucket contents and final ordering. + Buckets.resize(BucketCount); + for (auto &E : Entries) { + uint32_t Bucket = E.second.HashValue % BucketCount; + Buckets[Bucket].push_back(&E.second); + E.second.Sym = Asm->createTempSymbol(Prefix); + } + + // Sort the contents of the buckets by hash value so that hash collisions end + // up together. Stable sort makes testing easier and doesn't cost much more. + for (auto &Bucket : Buckets) + std::stable_sort(Bucket.begin(), Bucket.end(), + [](HashData *LHS, HashData *RHS) { + return LHS->HashValue < RHS->HashValue; + }); +} + +namespace { +class AccelTableEmitter { +protected: + AsmPrinter *const Asm; ///< Destination. + const AccelTableBase &Contents; ///< Data to emit. + + /// Controls whether to emit duplicate hash and offset table entries for names + /// with identical hashes. Apple tables don't emit duplicate entries, DWARF v5 + /// tables do. + const bool SkipIdenticalHashes; + + void emitHashes() const; + + /// Emit offsets to lists of entries with identical names. The offsets are + /// relative to the Base argument. + void emitOffsets(const MCSymbol *Base) const; + +public: + AccelTableEmitter(AsmPrinter *Asm, const AccelTableBase &Contents, + bool SkipIdenticalHashes) + : Asm(Asm), Contents(Contents), SkipIdenticalHashes(SkipIdenticalHashes) { + } +}; + +class AppleAccelTableEmitter : public AccelTableEmitter { + using Atom = AppleAccelTableData::Atom; + + /// The fixed header of an Apple Accelerator Table. + struct Header { + uint32_t Magic = MagicHash; + uint16_t Version = 1; + uint16_t HashFunction = dwarf::DW_hash_function_djb; + uint32_t BucketCount; + uint32_t HashCount; + uint32_t HeaderDataLength; + + /// 'HASH' magic value to detect endianness. + static const uint32_t MagicHash = 0x48415348; + + Header(uint32_t BucketCount, uint32_t UniqueHashCount, uint32_t DataLength) + : BucketCount(BucketCount), HashCount(UniqueHashCount), + HeaderDataLength(DataLength) {} + + void emit(AsmPrinter *Asm) const; +#ifndef NDEBUG + void print(raw_ostream &OS) const; + void dump() const { print(dbgs()); } +#endif + }; + + /// The HeaderData describes the structure of an Apple accelerator table + /// through a list of Atoms. + struct HeaderData { + /// In the case of data that is referenced via DW_FORM_ref_* the offset + /// base is used to describe the offset for all forms in the list of atoms. + uint32_t DieOffsetBase; + + const SmallVector<Atom, 4> Atoms; + + HeaderData(ArrayRef<Atom> AtomList, uint32_t Offset = 0) + : DieOffsetBase(Offset), Atoms(AtomList.begin(), AtomList.end()) {} + + void emit(AsmPrinter *Asm) const; +#ifndef NDEBUG + void print(raw_ostream &OS) const; + void dump() const { print(dbgs()); } +#endif + }; + + Header Header; + HeaderData HeaderData; + const MCSymbol *SecBegin; + + void emitBuckets() const; + void emitData() const; + +public: + AppleAccelTableEmitter(AsmPrinter *Asm, const AccelTableBase &Contents, + ArrayRef<Atom> Atoms, const MCSymbol *SecBegin) + : AccelTableEmitter(Asm, Contents, true), + Header(Contents.getBucketCount(), Contents.getUniqueHashCount(), + 8 + (Atoms.size() * 4)), + HeaderData(Atoms), SecBegin(SecBegin) {} + + void emit() const; + +#ifndef NDEBUG + void print(raw_ostream &OS) const; + void dump() const { print(dbgs()); } +#endif +}; +} // namespace + +void AccelTableEmitter::emitHashes() const { + uint64_t PrevHash = std::numeric_limits<uint64_t>::max(); + unsigned BucketIdx = 0; + for (auto &Bucket : Contents.getBuckets()) { + for (auto &Hash : Bucket) { + uint32_t HashValue = Hash->HashValue; + if (SkipIdenticalHashes && PrevHash == HashValue) + continue; + Asm->OutStreamer->AddComment("Hash in Bucket " + Twine(BucketIdx)); + Asm->EmitInt32(HashValue); + PrevHash = HashValue; + } + BucketIdx++; + } +} + +void AccelTableEmitter::emitOffsets(const MCSymbol *Base) const { + const auto &Buckets = Contents.getBuckets(); + uint64_t PrevHash = std::numeric_limits<uint64_t>::max(); + for (size_t i = 0, e = Buckets.size(); i < e; ++i) { + for (auto *Hash : Buckets[i]) { + uint32_t HashValue = Hash->HashValue; + if (SkipIdenticalHashes && PrevHash == HashValue) + continue; + PrevHash = HashValue; + Asm->OutStreamer->AddComment("Offset in Bucket " + Twine(i)); + Asm->EmitLabelDifference(Hash->Sym, Base, sizeof(uint32_t)); + } + } +} + +void AppleAccelTableEmitter::Header::emit(AsmPrinter *Asm) const { Asm->OutStreamer->AddComment("Header Magic"); - Asm->EmitInt32(Header.Magic); + Asm->EmitInt32(Magic); Asm->OutStreamer->AddComment("Header Version"); - Asm->EmitInt16(Header.Version); + Asm->EmitInt16(Version); Asm->OutStreamer->AddComment("Header Hash Function"); - Asm->EmitInt16(Header.HashFunction); + Asm->EmitInt16(HashFunction); Asm->OutStreamer->AddComment("Header Bucket Count"); - Asm->EmitInt32(Header.BucketCount); + Asm->EmitInt32(BucketCount); Asm->OutStreamer->AddComment("Header Hash Count"); - Asm->EmitInt32(Header.HashCount); + Asm->EmitInt32(HashCount); Asm->OutStreamer->AddComment("Header Data Length"); - Asm->EmitInt32(Header.HeaderDataLength); + Asm->EmitInt32(HeaderDataLength); +} - // Emit Header Data +void AppleAccelTableEmitter::HeaderData::emit(AsmPrinter *Asm) const { Asm->OutStreamer->AddComment("HeaderData Die Offset Base"); - Asm->EmitInt32(HeaderData.DieOffsetBase); + Asm->EmitInt32(DieOffsetBase); Asm->OutStreamer->AddComment("HeaderData Atom Count"); - Asm->EmitInt32(HeaderData.Atoms.size()); + Asm->EmitInt32(Atoms.size()); - for (size_t i = 0; i < HeaderData.Atoms.size(); i++) { - Atom A = HeaderData.Atoms[i]; + for (const Atom &A : Atoms) { Asm->OutStreamer->AddComment(dwarf::AtomTypeString(A.Type)); Asm->EmitInt16(A.Type); Asm->OutStreamer->AddComment(dwarf::FormEncodingString(A.Form)); @@ -59,20 +238,8 @@ void AppleAccelTableHeader::emit(AsmPrinter *Asm) { } } -void AppleAccelTableHeader::setBucketAndHashCount(uint32_t HashCount) { - if (HashCount > 1024) - Header.BucketCount = HashCount / 4; - else if (HashCount > 16) - Header.BucketCount = HashCount / 2; - else - Header.BucketCount = HashCount > 0 ? HashCount : 1; - - Header.HashCount = HashCount; -} - -void AppleAccelTableBase::emitHeader(AsmPrinter *Asm) { Header.emit(Asm); } - -void AppleAccelTableBase::emitBuckets(AsmPrinter *Asm) { +void AppleAccelTableEmitter::emitBuckets() const { + const auto &Buckets = Contents.getBuckets(); unsigned index = 0; for (size_t i = 0, e = Buckets.size(); i < e; ++i) { Asm->OutStreamer->AddComment("Bucket " + Twine(i)); @@ -92,42 +259,8 @@ void AppleAccelTableBase::emitBuckets(AsmPrinter *Asm) { } } -void AppleAccelTableBase::emitHashes(AsmPrinter *Asm) { - uint64_t PrevHash = std::numeric_limits<uint64_t>::max(); - unsigned BucketIdx = 0; - for (auto &Bucket : Buckets) { - for (auto &Hash : Bucket) { - uint32_t HashValue = Hash->HashValue; - if (PrevHash == HashValue) - continue; - Asm->OutStreamer->AddComment("Hash in Bucket " + Twine(BucketIdx)); - Asm->EmitInt32(HashValue); - PrevHash = HashValue; - } - BucketIdx++; - } -} - -void AppleAccelTableBase::emitOffsets(AsmPrinter *Asm, - const MCSymbol *SecBegin) { - uint64_t PrevHash = std::numeric_limits<uint64_t>::max(); - for (size_t i = 0, e = Buckets.size(); i < e; ++i) { - for (auto HI = Buckets[i].begin(), HE = Buckets[i].end(); HI != HE; ++HI) { - uint32_t HashValue = (*HI)->HashValue; - if (PrevHash == HashValue) - continue; - PrevHash = HashValue; - Asm->OutStreamer->AddComment("Offset in Bucket " + Twine(i)); - MCContext &Context = Asm->OutStreamer->getContext(); - const MCExpr *Sub = MCBinaryExpr::createSub( - MCSymbolRefExpr::create((*HI)->Sym, Context), - MCSymbolRefExpr::create(SecBegin, Context), Context); - Asm->OutStreamer->EmitValue(Sub, sizeof(uint32_t)); - } - } -} - -void AppleAccelTableBase::emitData(AsmPrinter *Asm) { +void AppleAccelTableEmitter::emitData() const { + const auto &Buckets = Contents.getBuckets(); for (size_t i = 0, e = Buckets.size(); i < e; ++i) { uint64_t PrevHash = std::numeric_limits<uint64_t>::max(); for (auto &Hash : Buckets[i]) { @@ -142,9 +275,8 @@ void AppleAccelTableBase::emitData(AsmPrinter *Asm) { Asm->emitDwarfStringOffset(Hash->Name); Asm->OutStreamer->AddComment("Num DIEs"); Asm->EmitInt32(Hash->Values.size()); - for (const auto *V : Hash->Values) { - V->emit(Asm); - } + for (const auto *V : Hash->Values) + static_cast<const AppleAccelTableData *>(V)->emit(Asm); PrevHash = Hash->HashValue; } // Emit the final end marker for the bucket. @@ -153,55 +285,20 @@ void AppleAccelTableBase::emitData(AsmPrinter *Asm) { } } -void AppleAccelTableBase::computeBucketCount() { - // First get the number of unique hashes. - std::vector<uint32_t> uniques; - uniques.reserve(Entries.size()); - for (const auto &E : Entries) - uniques.push_back(E.second.HashValue); - array_pod_sort(uniques.begin(), uniques.end()); - std::vector<uint32_t>::iterator p = - std::unique(uniques.begin(), uniques.end()); - - // Compute the hashes count and use it to set that together with the bucket - // count in the header. - Header.setBucketAndHashCount(std::distance(uniques.begin(), p)); +void AppleAccelTableEmitter::emit() const { + Header.emit(Asm); + HeaderData.emit(Asm); + emitBuckets(); + emitHashes(); + emitOffsets(SecBegin); + emitData(); } -void AppleAccelTableBase::finalizeTable(AsmPrinter *Asm, StringRef Prefix) { - // Create the individual hash data outputs. - for (auto &E : Entries) { - // Unique the entries. - std::stable_sort(E.second.Values.begin(), E.second.Values.end(), - [](const AppleAccelTableData *A, - const AppleAccelTableData *B) { return *A < *B; }); - E.second.Values.erase( - std::unique(E.second.Values.begin(), E.second.Values.end()), - E.second.Values.end()); - } - - // Figure out how many buckets we need, then compute the bucket contents and - // the final ordering. We'll emit the hashes and offsets by doing a walk - // during the emission phase. We add temporary symbols to the data so that we - // can reference them during the offset later, we'll emit them when we emit - // the data. - computeBucketCount(); - - // Compute bucket contents and final ordering. - Buckets.resize(Header.getBucketCount()); - for (auto &E : Entries) { - uint32_t bucket = E.second.HashValue % Header.getBucketCount(); - Buckets[bucket].push_back(&E.second); - E.second.Sym = Asm->createTempSymbol(Prefix); - } - - // Sort the contents of the buckets by hash value so that hash collisions end - // up together. Stable sort makes testing easier and doesn't cost much more. - for (auto &Bucket : Buckets) - std::stable_sort(Bucket.begin(), Bucket.end(), - [](HashData *LHS, HashData *RHS) { - return LHS->HashValue < RHS->HashValue; - }); +void llvm::emitAppleAccelTableImpl(AsmPrinter *Asm, AccelTableBase &Contents, + StringRef Prefix, const MCSymbol *SecBegin, + ArrayRef<AppleAccelTableData::Atom> Atoms) { + Contents.finalize(Asm, Prefix); + AppleAccelTableEmitter(Asm, Contents, Atoms, SecBegin).emit(); } void AppleAccelTableOffsetData::emit(AsmPrinter *Asm) const { @@ -228,38 +325,31 @@ void AppleAccelTableStaticTypeData::emit(AsmPrinter *Asm) const { #ifndef _MSC_VER // The lines below are rejected by older versions (TBD) of MSVC. -constexpr AppleAccelTableHeader::Atom AppleAccelTableTypeData::Atoms[]; -constexpr AppleAccelTableHeader::Atom AppleAccelTableOffsetData::Atoms[]; -constexpr AppleAccelTableHeader::Atom AppleAccelTableStaticOffsetData::Atoms[]; -constexpr AppleAccelTableHeader::Atom AppleAccelTableStaticTypeData::Atoms[]; +constexpr AppleAccelTableData::Atom AppleAccelTableTypeData::Atoms[]; +constexpr AppleAccelTableData::Atom AppleAccelTableOffsetData::Atoms[]; +constexpr AppleAccelTableData::Atom AppleAccelTableStaticOffsetData::Atoms[]; +constexpr AppleAccelTableData::Atom AppleAccelTableStaticTypeData::Atoms[]; #else // FIXME: Erase this path once the minimum MSCV version has been bumped. -const SmallVector<AppleAccelTableHeader::Atom, 4> - AppleAccelTableOffsetData::Atoms = {AppleAccelTableHeader::Atom( - dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)}; -const SmallVector<AppleAccelTableHeader::Atom, 4> - AppleAccelTableTypeData::Atoms = { - AppleAccelTableHeader::Atom(dwarf::DW_ATOM_die_offset, - dwarf::DW_FORM_data4), - AppleAccelTableHeader::Atom(dwarf::DW_ATOM_die_tag, - dwarf::DW_FORM_data2), - AppleAccelTableHeader::Atom(dwarf::DW_ATOM_type_flags, - dwarf::DW_FORM_data1)}; -const SmallVector<AppleAccelTableHeader::Atom, 4> - AppleAccelTableStaticOffsetData::Atoms = {AppleAccelTableHeader::Atom( - dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)}; -const SmallVector<AppleAccelTableHeader::Atom, 4> +const SmallVector<AppleAccelTableData::Atom, 4> + AppleAccelTableOffsetData::Atoms = { + Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)}; +const SmallVector<AppleAccelTableData::Atom, 4> AppleAccelTableTypeData::Atoms = + {Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4), + Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2), + Atom(dwarf::DW_ATOM_type_flags, dwarf::DW_FORM_data1)}; +const SmallVector<AppleAccelTableData::Atom, 4> + AppleAccelTableStaticOffsetData::Atoms = { + Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)}; +const SmallVector<AppleAccelTableData::Atom, 4> AppleAccelTableStaticTypeData::Atoms = { - AppleAccelTableHeader::Atom(dwarf::DW_ATOM_die_offset, - dwarf::DW_FORM_data4), - AppleAccelTableHeader::Atom(dwarf::DW_ATOM_die_tag, - dwarf::DW_FORM_data2), - AppleAccelTableHeader::Atom(5, dwarf::DW_FORM_data1), - AppleAccelTableHeader::Atom(6, dwarf::DW_FORM_data4)}; + Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4), + Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2), + Atom(5, dwarf::DW_FORM_data1), Atom(6, dwarf::DW_FORM_data4)}; #endif #ifndef NDEBUG -void AppleAccelTableHeader::Header::print(raw_ostream &OS) const { +void AppleAccelTableEmitter::Header::print(raw_ostream &OS) const { OS << "Magic: " << format("0x%x", Magic) << "\n" << "Version: " << Version << "\n" << "Hash Function: " << HashFunction << "\n" @@ -267,23 +357,25 @@ void AppleAccelTableHeader::Header::print(raw_ostream &OS) const { << "Header Data Length: " << HeaderDataLength << "\n"; } -void AppleAccelTableHeader::Atom::print(raw_ostream &OS) const { +void AppleAccelTableData::Atom::print(raw_ostream &OS) const { OS << "Type: " << dwarf::AtomTypeString(Type) << "\n" << "Form: " << dwarf::FormEncodingString(Form) << "\n"; } -void AppleAccelTableHeader::HeaderData::print(raw_ostream &OS) const { +void AppleAccelTableEmitter::HeaderData::print(raw_ostream &OS) const { OS << "DIE Offset Base: " << DieOffsetBase << "\n"; for (auto Atom : Atoms) Atom.print(OS); } -void AppleAccelTableHeader::print(raw_ostream &OS) const { +void AppleAccelTableEmitter::print(raw_ostream &OS) const { Header.print(OS); HeaderData.print(OS); + Contents.print(OS); + SecBegin->print(OS, nullptr); } -void AppleAccelTableBase::HashData::print(raw_ostream &OS) const { +void AccelTableBase::HashData::print(raw_ostream &OS) const { OS << "Name: " << Name.getString() << "\n"; OS << " Hash Value: " << format("0x%x", HashValue) << "\n"; OS << " Symbol: "; @@ -296,10 +388,7 @@ void AppleAccelTableBase::HashData::print(raw_ostream &OS) const { Value->print(OS); } -void AppleAccelTableBase::print(raw_ostream &OS) const { - // Print Header. - Header.print(OS); - +void AccelTableBase::print(raw_ostream &OS) const { // Print Content. OS << "Entries: \n"; for (const auto &Entry : Entries) { diff --git a/llvm/lib/CodeGen/AsmPrinter/DwarfDebug.cpp b/llvm/lib/CodeGen/AsmPrinter/DwarfDebug.cpp index c436950dc10..3681254ae08 100644 --- a/llvm/lib/CodeGen/AsmPrinter/DwarfDebug.cpp +++ b/llvm/lib/CodeGen/AsmPrinter/DwarfDebug.cpp @@ -262,8 +262,7 @@ DwarfDebug::DwarfDebug(AsmPrinter *A, Module *M) : DebugHandlerBase(A), DebugLocs(A->OutStreamer->isVerboseAsm()), InfoHolder(A, "info_string", DIEValueAllocator), SkeletonHolder(A, "skel_string", DIEValueAllocator), - IsDarwin(A->TM.getTargetTriple().isOSDarwin()), AccelNames(), AccelObjC(), - AccelNamespace(), AccelTypes() { + IsDarwin(A->TM.getTargetTriple().isOSDarwin()) { const Triple &TT = Asm->TM.getTargetTriple(); // Make sure we know our "debugger tuning." The target option takes @@ -1418,11 +1417,10 @@ void DwarfDebug::emitStringOffsetsTableHeader() { template <typename AccelTableT> void DwarfDebug::emitAccel(AccelTableT &Accel, MCSection *Section, StringRef TableName) { - Accel.finalizeTable(Asm, TableName); Asm->OutStreamer->SwitchSection(Section); // Emit the full data. - Accel.emit(Asm, Section->getBeginSymbol()); + emitAppleAccelTable(Asm, Accel, TableName, Section->getBeginSymbol()); } // Emit visible names into a hashed accelerator table section. diff --git a/llvm/lib/CodeGen/AsmPrinter/DwarfDebug.h b/llvm/lib/CodeGen/AsmPrinter/DwarfDebug.h index fa9b8edb6f3..380c868076b 100644 --- a/llvm/lib/CodeGen/AsmPrinter/DwarfDebug.h +++ b/llvm/lib/CodeGen/AsmPrinter/DwarfDebug.h @@ -290,10 +290,10 @@ class DwarfDebug : public DebugHandlerBase { AddressPool AddrPool; /// Apple accelerator tables. - AppleAccelTable<AppleAccelTableOffsetData> AccelNames; - AppleAccelTable<AppleAccelTableOffsetData> AccelObjC; - AppleAccelTable<AppleAccelTableOffsetData> AccelNamespace; - AppleAccelTable<AppleAccelTableTypeData> AccelTypes; + AccelTable<AppleAccelTableOffsetData> AccelNames; + AccelTable<AppleAccelTableOffsetData> AccelObjC; + AccelTable<AppleAccelTableOffsetData> AccelNamespace; + AccelTable<AppleAccelTableTypeData> AccelTypes; // Identify a debugger for "tuning" the debug info. DebuggerKind DebuggerTuning = DebuggerKind::Default; |

