Index: include/llvm/CodeGen/AccelTable.h =================================================================== --- include/llvm/CodeGen/AccelTable.h +++ include/llvm/CodeGen/AccelTable.h @@ -11,8 +11,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_LIB_CODEGEN_ASMPRINTER_DWARFACCELTABLE_H -#define LLVM_LIB_CODEGEN_ASMPRINTER_DWARFACCELTABLE_H +#ifndef LLVM_CODEGEN_DWARFACCELTABLE_H +#define LLVM_CODEGEN_DWARFACCELTABLE_H #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/SmallVector.h" @@ -88,122 +88,41 @@ /// `------------------' /// /// For the full documentation please refer to the DWARF 5 standard. +/// +/// +/// This file defines the class template AccelTable, which is represents an +/// abstract view of an Accelerator table, without any notion of an on-disk +/// layout. This class is parameterized by an entry type, which should derive +/// from AccelTableData. This is the type of individual entries in the table, +/// and it should store the data necessary to emit them. AppleAccelTableData is +/// the base class for Apple Accelerator Table entries, which have a uniform +/// structure based on a sequence of Atoms. There are different sub-classes +/// derived from AppleAccelTable, which differ in the set of Atoms and how they +/// obtain their values. +/// +/// An Apple Accelerator Table can be serialized by calling emitAppleAccelTable +/// function. +/// +/// TODO: Add DWARF v5 emission code. namespace llvm { class AsmPrinter; -/// Representation of the header of an Apple accelerator table. This consists -/// of the fixed header and the header data. The latter contains the atoms -/// which define the columns of the table. -class AppleAccelTableHeader { - struct Header { - uint32_t Magic = MagicHash; - uint16_t Version = 1; - uint16_t HashFunction = dwarf::DW_hash_function_djb; - uint32_t BucketCount = 0; - uint32_t HashCount = 0; - uint32_t HeaderDataLength; - - /// 'HASH' magic value to detect endianness. - static const uint32_t MagicHash = 0x48415348; - - Header(uint32_t DataLength) : HeaderDataLength(DataLength) {} - -#ifndef NDEBUG - void print(raw_ostream &OS) const; - void dump() const { print(dbgs()); } -#endif - }; - -public: - /// An Atom defines the form of the data in the accelerator table. - /// Conceptually it is a column in the accelerator consisting of a type and a - /// specification of the form of its data. - struct Atom { - /// Atom Type. - const uint16_t Type; - /// DWARF Form. - const uint16_t Form; - - constexpr Atom(uint16_t Type, uint16_t Form) : Type(Type), Form(Form) {} - -#ifndef NDEBUG - void print(raw_ostream &OS) const; - void dump() const { print(dbgs()); } -#endif - }; - -private: - /// The HeaderData describes the structure of the 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 Atoms; - -#ifndef _MSC_VER - // See the `static constexpr` below why we need an alternative - // implementation for MSVC. - HeaderData(ArrayRef AtomList, uint32_t Offset = 0) - : DieOffsetBase(Offset), Atoms(AtomList.begin(), AtomList.end()) {} -#else - // FIXME: Erase this path once the minimum MSCV version has been bumped. - HeaderData(const SmallVectorImpl &Atoms, uint32_t Offset = 0) - : DieOffsetBase(Offset), Atoms(Atoms.begin(), Atoms.end()) {} -#endif - -#ifndef NDEBUG - void print(raw_ostream &OS) const; - void dump() const { print(dbgs()); } -#endif - }; - - Header Header; - HeaderData HeaderData; - -public: - /// The length of the header data is always going to be 4 + 4 + 4*NumAtoms. -#ifndef _MSC_VER - // See the `static constexpr` below why we need an alternative implementation - // for MSVC. - AppleAccelTableHeader(ArrayRef Atoms) - : Header(8 + (Atoms.size() * 4)), HeaderData(Atoms) {} -#else - // FIXME: Erase this path once the minimum MSCV version has been bumped. - AppleAccelTableHeader(const SmallVectorImpl &Atoms) - : Header(8 + (Atoms.size() * 4)), HeaderData(Atoms) {} -#endif - - /// Update header with hash and bucket count. - void setBucketAndHashCount(uint32_t HashCount); - - uint32_t getHashCount() const { return Header.HashCount; } - uint32_t getBucketCount() const { return Header.BucketCount; } - - /// Emits the header via the AsmPrinter. - void emit(AsmPrinter *); - -#ifndef NDEBUG - void print(raw_ostream &OS) const; - void dump() const { print(dbgs()); } -#endif -}; - /// Interface which the different types of accelerator table data have to -/// conform. -class AppleAccelTableData { +/// conform. It serves as a base class for different values of the template +/// argument of the AccelTable class template. +class AccelTableData { public: - virtual ~AppleAccelTableData() = default; + virtual ~AccelTableData() = default; - virtual void emit(AsmPrinter *Asm) const = 0; - - bool operator<(const AppleAccelTableData &Other) const { + bool operator<(const AccelTableData &Other) const { return order() < Other.order(); } + // Subclasses should implement: + // static uint32_t hash(StringRef Name); + #ifndef NDEBUG virtual void print(raw_ostream &OS) const = 0; #endif @@ -211,119 +130,136 @@ virtual uint64_t order() const = 0; }; -/// Apple-style accelerator table base class. -class AppleAccelTableBase { -protected: +/// A base class holding non-template-dependant functionality of the AccelTable +/// class. Clients should not use this class directly but rather instantiate +/// AccelTable with a type derived from AccelTableData. +class AccelTableBase { +public: + using HashFn = uint32_t(StringRef); + + /// Represents a group of entries with identical name (and hence, hash value). struct HashData { DwarfStringPoolEntryRef Name; uint32_t HashValue; - std::vector Values; + std::vector Values; MCSymbol *Sym; - HashData(DwarfStringPoolEntryRef Name) : Name(Name) { - HashValue = djbHash(Name.getString()); - } + HashData(DwarfStringPoolEntryRef Name, HashFn *Hash) + : Name(Name), HashValue(Hash(Name.getString())) {} #ifndef NDEBUG void print(raw_ostream &OS) const; void dump() const { print(dbgs()); } #endif }; + using HashList = std::vector; + using BucketList = std::vector; +protected: /// Allocator for HashData and Values. BumpPtrAllocator Allocator; - /// Header containing both the header and header data. - AppleAccelTableHeader Header; - using StringEntries = StringMap; StringEntries Entries; - using HashList = std::vector; - HashList Hashes; + HashFn *Hash; + uint32_t BucketCount; + uint32_t UniqueHashCount; - using BucketList = std::vector; + HashList Hashes; BucketList Buckets; -#ifndef _MSC_VER - // See the `static constexpr` below why we need an alternative implementation - // for MSVC. - AppleAccelTableBase(ArrayRef Atoms) - : Header(Atoms), Entries(Allocator) {} -#else - // FIXME: Erase this path once the minimum MSCV version has been bumped. - AppleAccelTableBase(const SmallVectorImpl &Atoms) - : Header(Atoms), Entries(Allocator) {} -#endif - -private: - /// Emits the header for the table via the AsmPrinter. - void emitHeader(AsmPrinter *Asm); - - /// Helper function to compute the number of buckets needed based on the - /// number of unique hashes. void computeBucketCount(); - /// Walk through and emit the buckets for the table. Each index is an offset - /// into the list of hashes. - void emitBuckets(AsmPrinter *); - - /// Walk through the buckets and emit the individual hashes for each bucket. - void emitHashes(AsmPrinter *); - - /// Walk through the buckets and emit the individual offsets for each element - /// in each bucket. This is done via a symbol subtraction from the beginning - /// of the section. The non-section symbol will be output later when we emit - /// the actual data. - void emitOffsets(AsmPrinter *, const MCSymbol *); - - /// Walk through the buckets and emit the full data for each element in the - /// bucket. For the string case emit the dies and the various offsets. - /// Terminate each HashData bucket with 0. - void emitData(AsmPrinter *); + AccelTableBase(HashFn *Hash) : Entries(Allocator), Hash(Hash) {} public: - void finalizeTable(AsmPrinter *, StringRef); - - void emit(AsmPrinter *Asm, const MCSymbol *SecBegin) { - emitHeader(Asm); - emitBuckets(Asm); - emitHashes(Asm); - emitOffsets(Asm, SecBegin); - emitData(Asm); - } + void finalize(AsmPrinter *Asm, StringRef Prefix); + ArrayRef getBuckets() const { return Buckets; } + uint32_t getBucketCount() const { return BucketCount; } + uint32_t getUniqueHashCount() const { return UniqueHashCount; } + uint32_t getUniqueNameCount() const { return Entries.size(); } #ifndef NDEBUG void print(raw_ostream &OS) const; void dump() const { print(dbgs()); } #endif + + AccelTableBase(const AccelTableBase &) = delete; + void operator=(const AccelTableBase &) = delete; }; -template -class AppleAccelTable : public AppleAccelTableBase { +/// This class holds an abstract representation of an Accelerator Table, +/// consisting of a sequence of buckets, each bucket containint a sequence of +/// HashData entries. The class is parameterized by the type of entries it +/// holds. The type template parameter also defines the hash function to use for +/// hashing names. +template class AccelTable : public AccelTableBase { public: - AppleAccelTable() : AppleAccelTableBase(AppleAccelTableDataT::Atoms) {} - AppleAccelTable(const AppleAccelTable &) = delete; - AppleAccelTable &operator=(const AppleAccelTable &) = delete; + AccelTable() : AccelTableBase(DataT::hash) {} - template - void addName(DwarfStringPoolEntryRef Name, Types... Args); + template + void addName(DwarfStringPoolEntryRef Name, Types &&... Args); }; -template -template -void AppleAccelTable::addName( - DwarfStringPoolEntryRef Name, Types... Args) { +template +template +void AccelTable::addName(DwarfStringPoolEntryRef Name, + Types &&... Args) { assert(Buckets.empty() && "Already finalized!"); // If the string is in the list already then add this die to the list // otherwise add a new one. - auto Iter = Entries.try_emplace(Name.getString(), Name).first; + auto Iter = Entries.try_emplace(Name.getString(), Name, Hash).first; assert(Iter->second.Name == Name); - Iter->second.Values.push_back(new (Allocator) AppleAccelTableDataT(Args...)); + Iter->second.Values.push_back( + new (Allocator) AccelTableDataT(std::forward(Args)...)); +} + +/// A base class for different implementations of Data classes for Apple +/// Accelerator Tables. The columns in the table are defined by the static Atoms +/// variable defined on the subclasses. +class AppleAccelTableData : public AccelTableData { +public: + /// An Atom defines the form of the data in an Apple accelerator table. + /// Conceptually it is a column in the accelerator consisting of a type and a + /// specification of the form of its data. + struct Atom { + /// Atom Type. + const uint16_t Type; + /// DWARF Form. + const uint16_t Form; + + constexpr Atom(uint16_t Type, uint16_t Form) : Type(Type), Form(Form) {} + +#ifndef NDEBUG + void print(raw_ostream &OS) const; + void dump() const { print(dbgs()); } +#endif + }; + // Subclasses should define: + // static constexpr Atom Atoms[]; + + virtual void emit(AsmPrinter *Asm) const = 0; + + static uint32_t hash(StringRef Buffer) { return djbHash(Buffer); } +}; + +void emitAppleAccelTableImpl(AsmPrinter *Asm, AccelTableBase &Contents, + StringRef Prefix, const MCSymbol *SecBegin, + ArrayRef Atoms); + +/// Emit an Apple Accelerator Table consisting of entries in the specified +/// AccelTable. The DataT template parameter should be derived from +/// AppleAccelTableData. +template +void emitAppleAccelTable(AsmPrinter *Asm, AccelTable &Contents, + StringRef Prefix, const MCSymbol *SecBegin) { + static_assert(std::is_convertible::value, ""); + emitAppleAccelTableImpl(Asm, Contents, Prefix, SecBegin, DataT::Atoms); } -/// Accelerator table data implementation for simple accelerator tables with -/// just a DIE reference. +/// Accelerator table data implementation for simple Apple accelerator tables +/// with just a DIE reference. class AppleAccelTableOffsetData : public AppleAccelTableData { public: AppleAccelTableOffsetData(const DIE *D) : Die(D) {} @@ -332,12 +268,11 @@ #ifndef _MSC_VER // The line below is rejected by older versions (TBD) of MSVC. - static constexpr AppleAccelTableHeader::Atom Atoms[] = { - AppleAccelTableHeader::Atom(dwarf::DW_ATOM_die_offset, - dwarf::DW_FORM_data4)}; + static constexpr Atom Atoms[] = { + Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)}; #else // FIXME: Erase this path once the minimum MSCV version has been bumped. - static const SmallVector Atoms; + static const SmallVector Atoms; #endif #ifndef NDEBUG @@ -349,7 +284,7 @@ const DIE *Die; }; -/// Accelerator table data implementation for type accelerator tables. +/// Accelerator table data implementation for Apple type accelerator tables. class AppleAccelTableTypeData : public AppleAccelTableOffsetData { public: AppleAccelTableTypeData(const DIE *D) : AppleAccelTableOffsetData(D) {} @@ -358,15 +293,13 @@ #ifndef _MSC_VER // The line below is rejected by older versions (TBD) of MSVC. - static constexpr AppleAccelTableHeader::Atom 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)}; + static constexpr Atom 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)}; #else // FIXME: Erase this path once the minimum MSCV version has been bumped. - static const SmallVector Atoms; + static const SmallVector Atoms; #endif #ifndef NDEBUG @@ -374,8 +307,8 @@ #endif }; -/// Accelerator table data implementation for simple accelerator tables with -/// a DIE offset but no actual DIE pointer. +/// Accelerator table data implementation for simple Apple accelerator tables +/// with a DIE offset but no actual DIE pointer. class AppleAccelTableStaticOffsetData : public AppleAccelTableData { public: AppleAccelTableStaticOffsetData(uint32_t Offset) : Offset(Offset) {} @@ -384,12 +317,11 @@ #ifndef _MSC_VER // The line below is rejected by older versions (TBD) of MSVC. - static constexpr AppleAccelTableHeader::Atom Atoms[] = { - AppleAccelTableHeader::Atom(dwarf::DW_ATOM_die_offset, - dwarf::DW_FORM_data4)}; + static constexpr Atom Atoms[] = { + Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)}; #else // FIXME: Erase this path once the minimum MSCV version has been bumped. - static const SmallVector Atoms; + static const SmallVector Atoms; #endif #ifndef NDEBUG @@ -416,15 +348,13 @@ #ifndef _MSC_VER // The line below is rejected by older versions (TBD) of MSVC. - static constexpr AppleAccelTableHeader::Atom 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)}; + static constexpr Atom Atoms[] = { + 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)}; #else // FIXME: Erase this path once the minimum MSCV version has been bumped. - static const SmallVector Atoms; + static const SmallVector Atoms; #endif #ifndef NDEBUG @@ -440,4 +370,4 @@ } // end namespace llvm -#endif // LLVM_LIB_CODEGEN_ASMPRINTER_DWARFACCELTABLE_H +#endif // LLVM_CODEGEN_DWARFACCELTABLE_H Index: lib/CodeGen/AsmPrinter/AccelTable.cpp =================================================================== --- lib/CodeGen/AsmPrinter/AccelTable.cpp +++ 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 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::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(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 Atoms; + + HeaderData(ArrayRef 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 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::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::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::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::emitHashes(AsmPrinter *Asm) { - uint64_t PrevHash = std::numeric_limits::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::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::max(); for (auto &Hash : Buckets[i]) { @@ -142,9 +275,8 @@ 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(V)->emit(Asm); PrevHash = Hash->HashValue; } // Emit the final end marker for the bucket. @@ -153,55 +285,20 @@ } } -void AppleAccelTableBase::computeBucketCount() { - // First get the number of unique hashes. - std::vector 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::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 Atoms) { + Contents.finalize(Asm, Prefix); + AppleAccelTableEmitter(Asm, Contents, Atoms, SecBegin).emit(); } void AppleAccelTableOffsetData::emit(AsmPrinter *Asm) const { @@ -228,38 +325,31 @@ #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 - AppleAccelTableOffsetData::Atoms = {AppleAccelTableHeader::Atom( - dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)}; -const SmallVector - 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 - AppleAccelTableStaticOffsetData::Atoms = {AppleAccelTableHeader::Atom( - dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)}; -const SmallVector +const SmallVector + AppleAccelTableOffsetData::Atoms = { + Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)}; +const SmallVector 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 + AppleAccelTableStaticOffsetData::Atoms = { + Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)}; +const SmallVector 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 @@ << "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 @@ 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) { Index: lib/CodeGen/AsmPrinter/DwarfDebug.h =================================================================== --- lib/CodeGen/AsmPrinter/DwarfDebug.h +++ lib/CodeGen/AsmPrinter/DwarfDebug.h @@ -290,10 +290,10 @@ AddressPool AddrPool; /// Apple accelerator tables. - AppleAccelTable AccelNames; - AppleAccelTable AccelObjC; - AppleAccelTable AccelNamespace; - AppleAccelTable AccelTypes; + AccelTable AccelNames; + AccelTable AccelObjC; + AccelTable AccelNamespace; + AccelTable AccelTypes; // Identify a debugger for "tuning" the debug info. DebuggerKind DebuggerTuning = DebuggerKind::Default; Index: lib/CodeGen/AsmPrinter/DwarfDebug.cpp =================================================================== --- lib/CodeGen/AsmPrinter/DwarfDebug.cpp +++ lib/CodeGen/AsmPrinter/DwarfDebug.cpp @@ -262,8 +262,7 @@ : 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 @@ -1416,11 +1415,10 @@ template 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. Index: tools/dsymutil/DwarfLinker.cpp =================================================================== --- tools/dsymutil/DwarfLinker.cpp +++ tools/dsymutil/DwarfLinker.cpp @@ -741,17 +741,16 @@ StringRef Bytes); /// Emit Apple namespaces accelerator table. - void - emitAppleNamespaces(AppleAccelTable &Table); + void emitAppleNamespaces(AccelTable &Table); /// Emit Apple names accelerator table. - void emitAppleNames(AppleAccelTable &Table); + void emitAppleNames(AccelTable &Table); /// Emit Apple Objective-C accelerator table. - void emitAppleObjc(AppleAccelTable &Table); + void emitAppleObjc(AccelTable &Table); /// Emit Apple type accelerator table. - void emitAppleTypes(AppleAccelTable &Table); + void emitAppleTypes(AccelTable &Table); uint32_t getFrameSectionSize() const { return FrameSectionSize; } }; @@ -898,39 +897,35 @@ } void DwarfStreamer::emitAppleNamespaces( - AppleAccelTable &Table) { + AccelTable &Table) { Asm->OutStreamer->SwitchSection(MOFI->getDwarfAccelNamespaceSection()); - Table.finalizeTable(Asm.get(), "namespac"); auto *SectionBegin = Asm->createTempSymbol("namespac_begin"); Asm->OutStreamer->EmitLabel(SectionBegin); - Table.emit(Asm.get(), SectionBegin); + emitAppleAccelTable(Asm.get(), Table, "namespac", SectionBegin); } void DwarfStreamer::emitAppleNames( - AppleAccelTable &Table) { + AccelTable &Table) { Asm->OutStreamer->SwitchSection(MOFI->getDwarfAccelNamesSection()); - Table.finalizeTable(Asm.get(), "names"); auto *SectionBegin = Asm->createTempSymbol("names_begin"); Asm->OutStreamer->EmitLabel(SectionBegin); - Table.emit(Asm.get(), SectionBegin); + emitAppleAccelTable(Asm.get(), Table, "names", SectionBegin); } void DwarfStreamer::emitAppleObjc( - AppleAccelTable &Table) { + AccelTable &Table) { Asm->OutStreamer->SwitchSection(MOFI->getDwarfAccelObjCSection()); - Table.finalizeTable(Asm.get(), "objc"); auto *SectionBegin = Asm->createTempSymbol("objc_begin"); Asm->OutStreamer->EmitLabel(SectionBegin); - Table.emit(Asm.get(), SectionBegin); + emitAppleAccelTable(Asm.get(), Table, "objc", SectionBegin); } void DwarfStreamer::emitAppleTypes( - AppleAccelTable &Table) { + AccelTable &Table) { Asm->OutStreamer->SwitchSection(MOFI->getDwarfAccelTypesSection()); - Table.finalizeTable(Asm.get(), "types"); auto *SectionBegin = Asm->createTempSymbol("types_begin"); Asm->OutStreamer->EmitLabel(SectionBegin); - Table.emit(Asm.get(), SectionBegin); + emitAppleAccelTable(Asm.get(), Table, "types", SectionBegin); } /// Emit the swift_ast section stored in \p Buffers. @@ -1758,10 +1753,10 @@ uint32_t LastCIEOffset = 0; /// Apple accelerator tables. - AppleAccelTable AppleNames; - AppleAccelTable AppleNamespaces; - AppleAccelTable AppleObjc; - AppleAccelTable AppleTypes; + AccelTable AppleNames; + AccelTable AppleNamespaces; + AccelTable AppleObjc; + AccelTable AppleTypes; /// Mapping the PCM filename to the DwoId. StringMap ClangModules;