Index: llvm/trunk/lib/CodeGen/AsmPrinter/DwarfAccelTable.h =================================================================== --- llvm/trunk/lib/CodeGen/AsmPrinter/DwarfAccelTable.h +++ llvm/trunk/lib/CodeGen/AsmPrinter/DwarfAccelTable.h @@ -66,121 +66,135 @@ namespace llvm { class AsmPrinter; -class DwarfDebug; -class DwarfAccelTable { - // Helper function to compute the number of buckets needed based on - // the number of unique hashes. - void ComputeBucketCount(); - - struct TableHeader { - uint32_t magic = MagicHash; // 'HASH' magic value to allow endian detection - uint16_t version = 1; // Version number. - uint16_t hash_function = dwarf::DW_hash_function_djb; - // The hash function enumeration that was used. - uint32_t bucket_count = 0; // The number of buckets in this hash table. - uint32_t hashes_count = 0; // The total number of unique hash values - // and hash data offsets in this table. - uint32_t header_data_len; // The bytes to skip to get to the hash - // indexes (buckets) for correct alignment. - // Also written to disk is the implementation specific header data. +/// 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; - TableHeader(uint32_t data_len) : header_data_len(data_len) {} + Header(uint32_t DataLength) : HeaderDataLength(DataLength) {} #ifndef NDEBUG - void print(raw_ostream &OS) { - OS << "Magic: " << format("0x%x", magic) << "\n" - << "Version: " << version << "\n" - << "Hash Function: " << hash_function << "\n" - << "Bucket Count: " << bucket_count << "\n" - << "Header Data Length: " << header_data_len << "\n"; + void print(raw_ostream &OS) const { + OS << "Magic: " << format("0x%x", Magic) << "\n" + << "Version: " << Version << "\n" + << "Hash Function: " << HashFunction << "\n" + << "Bucket Count: " << BucketCount << "\n" + << "Header Data Length: " << HeaderDataLength << "\n"; } - void dump() { print(dbgs()); } + void dump() const { print(dbgs()); } #endif }; public: - // The HeaderData describes the form of each set of data. In general this - // is as a list of atoms (atom_count) where each atom contains a type - // (AtomType type) of data, and an encoding form (form). In the case of - // data that is referenced via DW_FORM_ref_* the die_offset_base is - // used to describe the offset for all forms in the list of atoms. - // This also serves as a public interface of sorts. - // When written to disk this will have the form: - // - // uint32_t die_offset_base - // uint32_t atom_count - // atom_count Atoms - - // Make these public so that they can be used as a general interface to - // the class. + /// 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 { - uint16_t type; // enum AtomType - uint16_t form; // DWARF DW_FORM_ defines + /// Atom Type. + const uint16_t Type; + /// DWARF Form. + const uint16_t Form; - constexpr Atom(uint16_t type, uint16_t form) : type(type), form(form) {} + constexpr Atom(uint16_t Type, uint16_t Form) : Type(Type), Form(Form) {} #ifndef NDEBUG - void print(raw_ostream &OS) { - OS << "Type: " << dwarf::AtomTypeString(type) << "\n" - << "Form: " << dwarf::FormEncodingString(form) << "\n"; + void print(raw_ostream &OS) const { + OS << "Type: " << dwarf::AtomTypeString(Type) << "\n" + << "Form: " << dwarf::FormEncodingString(Form) << "\n"; } - void dump() { print(dbgs()); } + void dump() const { print(dbgs()); } #endif }; private: - struct TableHeaderData { - uint32_t die_offset_base; + /// 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; + SmallVector Atoms; - TableHeaderData(ArrayRef AtomList, uint32_t offset = 0) - : die_offset_base(offset), Atoms(AtomList.begin(), AtomList.end()) {} + HeaderData(ArrayRef AtomList, uint32_t Offset = 0) + : DieOffsetBase(Offset), Atoms(AtomList.begin(), AtomList.end()) {} #ifndef NDEBUG - void print(raw_ostream &OS) { - OS << "die_offset_base: " << die_offset_base << "\n"; - for (size_t i = 0; i < Atoms.size(); i++) - Atoms[i].print(OS); + void print(raw_ostream &OS) const { + OS << "DIE Offset Base: " << DieOffsetBase << "\n"; + for (auto Atom : Atoms) + Atom.print(OS); } - void dump() { print(dbgs()); } + void dump() const { print(dbgs()); } #endif }; - // The data itself consists of a str_offset, a count of the DIEs in the - // hash and the offsets to the DIEs themselves. - // On disk each data section is ended with a 0 KeyType as the end of the - // hash chain. - // On output this looks like: - // uint32_t str_offset - // uint32_t hash_data_count - // HashData[hash_data_count] + Header Header; + HeaderData HeaderData; + public: - struct HashDataContents { - const DIE *Die; // Offsets - char Flags; // Specific flags to output + /// The length of the header data is always going to be 4 + 4 + 4*NumAtoms. + AppleAccelTableHeader(ArrayRef Atoms) + : Header(8 + (Atoms.size() * 4)), HeaderData(Atoms) {} + + /// Update header with hash and bucket count. + void setBucketAndHashCount(uint32_t HashCount); - HashDataContents(const DIE *D, char Flags) : Die(D), Flags(Flags) {} + 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 { - OS << " Offset: " << Die->getOffset() << "\n" - << " Tag: " << dwarf::TagString(Die->getTag()) << "\n" - << " Flags: " << Flags << "\n"; - } + void print(raw_ostream &OS) const { + Header.print(OS); + HeaderData.print(OS); + } + + void dump() const { print(dbgs()); } #endif - }; +}; -private: - // String Data +/// Interface which the different types of accelerator table data have to +/// conform. +class AppleAccelTableData { +public: + virtual ~AppleAccelTableData() = default; + + virtual void emit(AsmPrinter *Asm) const = 0; + + bool operator<(const AppleAccelTableData &Other) const { + return order() < Other.order(); + } + +#ifndef NDEBUG + virtual void print(raw_ostream &OS) const = 0; +#endif +protected: + virtual uint64_t order() const; +}; + +/// Apple-style accelerator table base class. +class AppleAccelTableBase { +protected: struct DataArray { DwarfStringPoolEntryRef Name; - std::vector Values; + std::vector Values; }; friend struct HashData; @@ -189,10 +203,9 @@ StringRef Str; uint32_t HashValue; MCSymbol *Sym; - DwarfAccelTable::DataArray &Data; // offsets + DataArray &Data; - HashData(StringRef S, DwarfAccelTable::DataArray &Data) - : Str(S), Data(Data) { + HashData(StringRef S, DataArray &Data) : Str(S), Data(Data) { HashValue = djbHash(S); } @@ -206,54 +219,164 @@ else OS << ""; OS << "\n"; - for (HashDataContents *C : Data.Values) { - OS << " Offset: " << C->Die->getOffset() << "\n"; - OS << " Tag: " << dwarf::TagString(C->Die->getTag()) << "\n"; - OS << " Flags: " << C->Flags << "\n"; - } + for (auto *Value : Data.Values) + Value->print(OS); } void dump() { print(dbgs()); } #endif }; - // Internal Functions - void EmitHeader(AsmPrinter *); - void EmitBuckets(AsmPrinter *); - void EmitHashes(AsmPrinter *); - void emitOffsets(AsmPrinter *, const MCSymbol *); - void EmitData(AsmPrinter *, DwarfDebug *D); - - // Allocator for HashData and HashDataContents. + /// Allocator for HashData and Values. BumpPtrAllocator Allocator; - // Output Variables - TableHeader Header; - TableHeaderData HeaderData; + /// Header containing both the header and header data. + AppleAccelTableHeader Header; + std::vector Data; using StringEntries = StringMap; - StringEntries Entries; - // Buckets/Hashes/Offsets using HashList = std::vector; + HashList Hashes; + using BucketList = std::vector; BucketList Buckets; - HashList Hashes; - // Public Implementation + AppleAccelTableBase(ArrayRef Atoms) + : Header(Atoms), Entries(Allocator) {} + +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 *); + public: - DwarfAccelTable(ArrayRef); - DwarfAccelTable(const DwarfAccelTable &) = delete; - DwarfAccelTable &operator=(const DwarfAccelTable &) = delete; - - void AddName(DwarfStringPoolEntryRef Name, const DIE *Die, char Flags = 0); - void FinalizeTable(AsmPrinter *, StringRef); - void emit(AsmPrinter *, const MCSymbol *, DwarfDebug *); + void finalizeTable(AsmPrinter *, StringRef); + + void emit(AsmPrinter *Asm, const MCSymbol *SecBegin) { + emitHeader(Asm); + emitBuckets(Asm); + emitHashes(Asm); + emitOffsets(Asm, SecBegin); + emitData(Asm); + } + +#ifndef NDEBUG + void print(raw_ostream &OS) const { + // Print Header. + Header.print(OS); + + // Print Content. + OS << "Entries: \n"; + for (const auto &Entry : Entries) { + OS << "Name: " << Entry.first() << "\n"; + for (auto *V : Entry.second.Values) + V->print(OS); + } + + OS << "Buckets and Hashes: \n"; + for (auto &Bucket : Buckets) + for (auto &Hash : Bucket) + Hash->print(OS); + + OS << "Data: \n"; + for (auto &D : Data) + D->print(OS); + } + void dump() const { print(dbgs()); } +#endif +}; + +template +class AppleAccelTable : public AppleAccelTableBase { +public: + AppleAccelTable() : AppleAccelTableBase(AppleAccelTableDataT::Atoms) {} + AppleAccelTable(const AppleAccelTable &) = delete; + AppleAccelTable &operator=(const AppleAccelTable &) = delete; + + template + void addName(DwarfStringPoolEntryRef Name, Types... Args); +}; + +template +template +void AppleAccelTable::addName( + DwarfStringPoolEntryRef Name, Types... Args) { + assert(Data.empty() && "Already finalized!"); + // If the string is in the list already then add this die to the list + // otherwise add a new one. + DataArray &DA = Entries[Name.getString()]; + assert(!DA.Name || DA.Name == Name); + DA.Name = Name; + DA.Values.push_back(new (Allocator) AppleAccelTableDataT(Args...)); +} + +/// Accelerator table data implementation for simple accelerator tables with +/// just a DIE reference. +class AppleAccelTableOffsetData : public AppleAccelTableData { +public: + AppleAccelTableOffsetData(const DIE *D) : Die(D) {} + + void emit(AsmPrinter *Asm) const override; + + static constexpr AppleAccelTableHeader::Atom Atoms[] = { + AppleAccelTableHeader::Atom(dwarf::DW_ATOM_die_offset, + dwarf::DW_FORM_data4)}; + +#ifndef NDEBUG + void print(raw_ostream &OS) const override { + OS << " Offset: " << Die->getOffset() << "\n"; + } + +#endif +protected: + uint64_t order() const override { return Die->getOffset(); } + + const DIE *Die; +}; + +/// Accelerator table data implementation for type accelerator tables. +class AppleAccelTableTypeData : public AppleAccelTableOffsetData { +public: + AppleAccelTableTypeData(const DIE *D) : AppleAccelTableOffsetData(D) {} + + void emit(AsmPrinter *Asm) const override; + + 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)}; + #ifndef NDEBUG - void print(raw_ostream &OS); - void dump() { print(dbgs()); } + void print(raw_ostream &OS) const override { + OS << " Offset: " << Die->getOffset() << "\n"; + OS << " Tag: " << dwarf::TagString(Die->getTag()) << "\n"; + } #endif }; Index: llvm/trunk/lib/CodeGen/AsmPrinter/DwarfAccelTable.cpp =================================================================== --- llvm/trunk/lib/CodeGen/AsmPrinter/DwarfAccelTable.cpp +++ llvm/trunk/lib/CodeGen/AsmPrinter/DwarfAccelTable.cpp @@ -22,129 +22,60 @@ #include "llvm/MC/MCStreamer.h" #include "llvm/Support/raw_ostream.h" #include -#include #include #include -#include #include #include using namespace llvm; -// The length of the header data is always going to be 4 + 4 + 4*NumAtoms. -DwarfAccelTable::DwarfAccelTable(ArrayRef atomList) - : Header(8 + (atomList.size() * 4)), HeaderData(atomList), - Entries(Allocator) {} - -void DwarfAccelTable::AddName(DwarfStringPoolEntryRef Name, const DIE *die, - char Flags) { - assert(Data.empty() && "Already finalized!"); - // If the string is in the list already then add this die to the list - // otherwise add a new one. - DataArray &DIEs = Entries[Name.getString()]; - assert(!DIEs.Name || DIEs.Name == Name); - DIEs.Name = Name; - DIEs.Values.push_back(new (Allocator) HashDataContents(die, Flags)); -} - -void DwarfAccelTable::ComputeBucketCount() { - // First get the number of unique hashes. - std::vector uniques(Data.size()); - for (size_t i = 0, e = Data.size(); i < e; ++i) - uniques[i] = Data[i]->HashValue; - array_pod_sort(uniques.begin(), uniques.end()); - std::vector::iterator p = - std::unique(uniques.begin(), uniques.end()); - uint32_t num = std::distance(uniques.begin(), p); - - // Then compute the bucket size, minimum of 1 bucket. - if (num > 1024) - Header.bucket_count = num / 4; - else if (num > 16) - Header.bucket_count = num / 2; - else - Header.bucket_count = num > 0 ? num : 1; - - Header.hashes_count = num; -} - -// compareDIEs - comparison predicate that sorts DIEs by their offset. -static bool compareDIEs(const DwarfAccelTable::HashDataContents *A, - const DwarfAccelTable::HashDataContents *B) { - return A->Die->getOffset() < B->Die->getOffset(); -} - -void DwarfAccelTable::FinalizeTable(AsmPrinter *Asm, StringRef Prefix) { - // Create the individual hash data outputs. - Data.reserve(Entries.size()); - for (StringMap::iterator EI = Entries.begin(), EE = Entries.end(); - EI != EE; ++EI) { - - // Unique the entries. - std::stable_sort(EI->second.Values.begin(), EI->second.Values.end(), compareDIEs); - EI->second.Values.erase( - std::unique(EI->second.Values.begin(), EI->second.Values.end()), - EI->second.Values.end()); - - HashData *Entry = new (Allocator) HashData(EI->getKey(), EI->second); - Data.push_back(Entry); - } - - // 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.bucket_count); - for (size_t i = 0, e = Data.size(); i < e; ++i) { - uint32_t bucket = Data[i]->HashValue % Header.bucket_count; - Buckets[bucket].push_back(Data[i]); - Data[i]->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 (size_t i = 0; i < Buckets.size(); ++i) - std::stable_sort(Buckets[i].begin(), Buckets[i].end(), - [] (HashData *LHS, HashData *RHS) { - return LHS->HashValue < RHS->HashValue; - }); -} - -// Emits the header for the table via the AsmPrinter. -void DwarfAccelTable::EmitHeader(AsmPrinter *Asm) { +void AppleAccelTableHeader::emit(AsmPrinter *Asm) { + // Emit Header. Asm->OutStreamer->AddComment("Header Magic"); - Asm->EmitInt32(Header.magic); + Asm->EmitInt32(Header.Magic); Asm->OutStreamer->AddComment("Header Version"); - Asm->EmitInt16(Header.version); + Asm->EmitInt16(Header.Version); Asm->OutStreamer->AddComment("Header Hash Function"); - Asm->EmitInt16(Header.hash_function); + Asm->EmitInt16(Header.HashFunction); Asm->OutStreamer->AddComment("Header Bucket Count"); - Asm->EmitInt32(Header.bucket_count); + Asm->EmitInt32(Header.BucketCount); Asm->OutStreamer->AddComment("Header Hash Count"); - Asm->EmitInt32(Header.hashes_count); + Asm->EmitInt32(Header.HashCount); Asm->OutStreamer->AddComment("Header Data Length"); - Asm->EmitInt32(Header.header_data_len); + Asm->EmitInt32(Header.HeaderDataLength); + + // Emit Header Data Asm->OutStreamer->AddComment("HeaderData Die Offset Base"); - Asm->EmitInt32(HeaderData.die_offset_base); + Asm->EmitInt32(HeaderData.DieOffsetBase); Asm->OutStreamer->AddComment("HeaderData Atom Count"); Asm->EmitInt32(HeaderData.Atoms.size()); + for (size_t i = 0; i < HeaderData.Atoms.size(); i++) { Atom A = HeaderData.Atoms[i]; - Asm->OutStreamer->AddComment(dwarf::AtomTypeString(A.type)); - Asm->EmitInt16(A.type); - Asm->OutStreamer->AddComment(dwarf::FormEncodingString(A.form)); - Asm->EmitInt16(A.form); + Asm->OutStreamer->AddComment(dwarf::AtomTypeString(A.Type)); + Asm->EmitInt16(A.Type); + Asm->OutStreamer->AddComment(dwarf::FormEncodingString(A.Form)); + Asm->EmitInt16(A.Form); } } -// Walk through and emit the buckets for the table. Each index is -// an offset into the list of hashes. -void DwarfAccelTable::EmitBuckets(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; +} + +constexpr AppleAccelTableHeader::Atom AppleAccelTableTypeData::Atoms[]; +constexpr AppleAccelTableHeader::Atom AppleAccelTableOffsetData::Atoms[]; + +void AppleAccelTableBase::emitHeader(AsmPrinter *Asm) { Header.emit(Asm); } + +void AppleAccelTableBase::emitBuckets(AsmPrinter *Asm) { unsigned index = 0; for (size_t i = 0, e = Buckets.size(); i < e; ++i) { Asm->OutStreamer->AddComment("Bucket " + Twine(i)); @@ -152,8 +83,8 @@ Asm->EmitInt32(index); else Asm->EmitInt32(std::numeric_limits::max()); - // Buckets point in the list of hashes, not to the data. Do not - // increment the index multiple times in case of hash collisions. + // Buckets point in the list of hashes, not to the data. Do not increment + // the index multiple times in case of hash collisions. uint64_t PrevHash = std::numeric_limits::max(); for (auto *HD : Buckets[i]) { uint32_t HashValue = HD->HashValue; @@ -164,34 +95,27 @@ } } -// Walk through the buckets and emit the individual hashes for each -// bucket. -void DwarfAccelTable::EmitHashes(AsmPrinter *Asm) { +void AppleAccelTableBase::emitHashes(AsmPrinter *Asm) { uint64_t PrevHash = std::numeric_limits::max(); - for (size_t i = 0, e = Buckets.size(); i < e; ++i) { - for (HashList::const_iterator HI = Buckets[i].begin(), - HE = Buckets[i].end(); - HI != HE; ++HI) { - uint32_t HashValue = (*HI)->HashValue; + 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(i)); + Asm->OutStreamer->AddComment("Hash in Bucket " + Twine(BucketIdx)); Asm->EmitInt32(HashValue); PrevHash = HashValue; } + BucketIdx++; } } -// 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 DwarfAccelTable::emitOffsets(AsmPrinter *Asm, const MCSymbol *SecBegin) { +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 (HashList::const_iterator HI = Buckets[i].begin(), - HE = Buckets[i].end(); - HI != HE; ++HI) { + for (auto HI = Buckets[i].begin(), HE = Buckets[i].end(); HI != HE; ++HI) { uint32_t HashValue = (*HI)->HashValue; if (PrevHash == HashValue) continue; @@ -206,37 +130,25 @@ } } -// 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 DwarfAccelTable::EmitData(AsmPrinter *Asm, DwarfDebug *D) { +void AppleAccelTableBase::emitData(AsmPrinter *Asm) { for (size_t i = 0, e = Buckets.size(); i < e; ++i) { uint64_t PrevHash = std::numeric_limits::max(); - for (HashList::const_iterator HI = Buckets[i].begin(), - HE = Buckets[i].end(); - HI != HE; ++HI) { - // Terminate the previous entry if there is no hash collision - // with the current one. + for (auto &Hash : Buckets[i]) { + // Terminate the previous entry if there is no hash collision with the + // current one. if (PrevHash != std::numeric_limits::max() && - PrevHash != (*HI)->HashValue) + PrevHash != Hash->HashValue) Asm->EmitInt32(0); // Remember to emit the label for our offset. - Asm->OutStreamer->EmitLabel((*HI)->Sym); - Asm->OutStreamer->AddComment((*HI)->Str); - Asm->emitDwarfStringOffset((*HI)->Data.Name); + Asm->OutStreamer->EmitLabel(Hash->Sym); + Asm->OutStreamer->AddComment(Hash->Str); + Asm->emitDwarfStringOffset(Hash->Data.Name); Asm->OutStreamer->AddComment("Num DIEs"); - Asm->EmitInt32((*HI)->Data.Values.size()); - for (HashDataContents *HD : (*HI)->Data.Values) { - // Emit the DIE offset - Asm->EmitInt32(HD->Die->getDebugSectionOffset()); - // If we have multiple Atoms emit that info too. - // FIXME: A bit of a hack, we either emit only one atom or all info. - if (HeaderData.Atoms.size() > 1) { - Asm->EmitInt16(HD->Die->getTag()); - Asm->EmitInt8(HD->Flags); - } + Asm->EmitInt32(Hash->Data.Values.size()); + for (const auto *V : Hash->Data.Values) { + V->emit(Asm); } - PrevHash = (*HI)->HashValue; + PrevHash = Hash->HashValue; } // Emit the final end marker for the bucket. if (!Buckets[i].empty()) @@ -244,50 +156,66 @@ } } -// Emit the entire data structure to the output file. -void DwarfAccelTable::emit(AsmPrinter *Asm, const MCSymbol *SecBegin, - DwarfDebug *D) { - // Emit the header. - EmitHeader(Asm); - - // Emit the buckets. - EmitBuckets(Asm); +void AppleAccelTableBase::computeBucketCount() { + // First get the number of unique hashes. + std::vector uniques(Data.size()); + for (size_t i = 0, e = Data.size(); i < e; ++i) + uniques[i] = Data[i]->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 AppleAccelTableBase::finalizeTable(AsmPrinter *Asm, StringRef Prefix) { + // Create the individual hash data outputs. + Data.reserve(Entries.size()); + 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()); + + HashData *Entry = new (Allocator) HashData(E.first(), E.second); + Data.push_back(Entry); + } - // Emit the hashes. - EmitHashes(Asm); + // 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(); - // Emit the offsets. - emitOffsets(Asm, SecBegin); + // Compute bucket contents and final ordering. + Buckets.resize(Header.getBucketCount()); + for (auto &D : Data) { + uint32_t bucket = D->HashValue % Header.getBucketCount(); + Buckets[bucket].push_back(D); + D->Sym = Asm->createTempSymbol(Prefix); + } - // Emit the hash data. - EmitData(Asm, D); + // 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; + }); } -#ifndef NDEBUG -void DwarfAccelTable::print(raw_ostream &OS) { - Header.print(OS); - HeaderData.print(OS); - - OS << "Entries: \n"; - for (StringMap::const_iterator EI = Entries.begin(), - EE = Entries.end(); - EI != EE; ++EI) { - OS << "Name: " << EI->getKeyData() << "\n"; - for (HashDataContents *HD : EI->second.Values) - HD->print(OS); - } +void AppleAccelTableOffsetData::emit(AsmPrinter *Asm) const { + Asm->EmitInt32(Die->getDebugSectionOffset()); +} - OS << "Buckets and Hashes: \n"; - for (size_t i = 0, e = Buckets.size(); i < e; ++i) - for (HashList::const_iterator HI = Buckets[i].begin(), - HE = Buckets[i].end(); - HI != HE; ++HI) - (*HI)->print(OS); - - OS << "Data: \n"; - for (std::vector::const_iterator DI = Data.begin(), - DE = Data.end(); - DI != DE; ++DI) - (*DI)->print(OS); +void AppleAccelTableTypeData::emit(AsmPrinter *Asm) const { + Asm->EmitInt32(Die->getDebugSectionOffset()); + Asm->EmitInt16(Die->getTag()); + Asm->EmitInt8(0); } -#endif Index: llvm/trunk/lib/CodeGen/AsmPrinter/DwarfDebug.h =================================================================== --- llvm/trunk/lib/CodeGen/AsmPrinter/DwarfDebug.h +++ llvm/trunk/lib/CodeGen/AsmPrinter/DwarfDebug.h @@ -289,10 +289,11 @@ AddressPool AddrPool; - DwarfAccelTable AccelNames; - DwarfAccelTable AccelObjC; - DwarfAccelTable AccelNamespace; - DwarfAccelTable AccelTypes; + /// Apple accelerator tables. + AppleAccelTable AccelNames; + AppleAccelTable AccelObjC; + AppleAccelTable AccelNamespace; + AppleAccelTable AccelTypes; // Identify a debugger for "tuning" the debug info. DebuggerKind DebuggerTuning = DebuggerKind::Default; @@ -334,8 +335,8 @@ void emitStringOffsetsTableHeader(); /// Emit a specified accelerator table. - void emitAccel(DwarfAccelTable &Accel, MCSection *Section, - StringRef TableName); + template + void emitAccel(AccelTableT &Accel, MCSection *Section, StringRef TableName); /// Emit visible names into a hashed accelerator table section. void emitAccelNames(); Index: llvm/trunk/lib/CodeGen/AsmPrinter/DwarfDebug.cpp =================================================================== --- llvm/trunk/lib/CodeGen/AsmPrinter/DwarfDebug.cpp +++ llvm/trunk/lib/CodeGen/AsmPrinter/DwarfDebug.cpp @@ -258,23 +258,12 @@ "conflicting locations for variable"); } -static const DwarfAccelTable::Atom TypeAtoms[] = { - DwarfAccelTable::Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4), - DwarfAccelTable::Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2), - DwarfAccelTable::Atom(dwarf::DW_ATOM_type_flags, dwarf::DW_FORM_data1)}; - 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(DwarfAccelTable::Atom(dwarf::DW_ATOM_die_offset, - dwarf::DW_FORM_data4)), - AccelObjC(DwarfAccelTable::Atom(dwarf::DW_ATOM_die_offset, - dwarf::DW_FORM_data4)), - AccelNamespace(DwarfAccelTable::Atom(dwarf::DW_ATOM_die_offset, - dwarf::DW_FORM_data4)), - AccelTypes(TypeAtoms) { + IsDarwin(A->TM.getTargetTriple().isOSDarwin()), AccelNames(), AccelObjC(), + AccelNamespace(), AccelTypes() { const Triple &TT = Asm->TM.getTargetTriple(); // Make sure we know our "debugger tuning." The target option takes @@ -1424,13 +1413,14 @@ Asm->getObjFileLowering().getDwarfStrOffSection()); } -void DwarfDebug::emitAccel(DwarfAccelTable &Accel, MCSection *Section, +template +void DwarfDebug::emitAccel(AccelTableT &Accel, MCSection *Section, StringRef TableName) { - Accel.FinalizeTable(Asm, TableName); + Accel.finalizeTable(Asm, TableName); Asm->OutStreamer->SwitchSection(Section); // Emit the full data. - Accel.emit(Asm, Section->getBeginSymbol(), this); + Accel.emit(Asm, Section->getBeginSymbol()); } // Emit visible names into a hashed accelerator table section. @@ -2206,25 +2196,25 @@ void DwarfDebug::addAccelName(StringRef Name, const DIE &Die) { if (!useDwarfAccelTables()) return; - AccelNames.AddName(InfoHolder.getStringPool().getEntry(*Asm, Name), &Die); + AccelNames.addName(InfoHolder.getStringPool().getEntry(*Asm, Name), &Die); } void DwarfDebug::addAccelObjC(StringRef Name, const DIE &Die) { if (!useDwarfAccelTables()) return; - AccelObjC.AddName(InfoHolder.getStringPool().getEntry(*Asm, Name), &Die); + AccelObjC.addName(InfoHolder.getStringPool().getEntry(*Asm, Name), &Die); } void DwarfDebug::addAccelNamespace(StringRef Name, const DIE &Die) { if (!useDwarfAccelTables()) return; - AccelNamespace.AddName(InfoHolder.getStringPool().getEntry(*Asm, Name), &Die); + AccelNamespace.addName(InfoHolder.getStringPool().getEntry(*Asm, Name), &Die); } void DwarfDebug::addAccelType(StringRef Name, const DIE &Die, char Flags) { if (!useDwarfAccelTables()) return; - AccelTypes.AddName(InfoHolder.getStringPool().getEntry(*Asm, Name), &Die); + AccelTypes.addName(InfoHolder.getStringPool().getEntry(*Asm, Name), &Die); } uint16_t DwarfDebug::getDwarfVersion() const {