Index: llvm/trunk/include/llvm/CodeGen/AccelTable.h =================================================================== --- llvm/trunk/include/llvm/CodeGen/AccelTable.h +++ llvm/trunk/include/llvm/CodeGen/AccelTable.h @@ -0,0 +1,411 @@ +//==- include/llvm/CodeGen/AccelTable.h - Accelerator Tables -----*- C++ -*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file contains support for writing accelerator tables. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_LIB_CODEGEN_ASMPRINTER_DWARFACCELTABLE_H +#define LLVM_LIB_CODEGEN_ASMPRINTER_DWARFACCELTABLE_H + +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StringMap.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/BinaryFormat/Dwarf.h" +#include "llvm/CodeGen/DIE.h" +#include "llvm/CodeGen/DwarfStringPoolEntry.h" +#include "llvm/MC/MCSymbol.h" +#include "llvm/Support/Allocator.h" +#include "llvm/Support/DJB.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/Format.h" +#include "llvm/Support/raw_ostream.h" +#include +#include +#include + +/// The DWARF and Apple accelerator tables are an indirect hash table optimized +/// for null lookup rather than access to known data. The Apple accelerator +/// tables are a precursor of the newer DWARF v5 accelerator tables. Both +/// formats share common design ideas. +/// +/// The Apple accelerator table are output into an on-disk format that looks +/// like this: +/// +/// .------------------. +/// | HEADER | +/// |------------------| +/// | BUCKETS | +/// |------------------| +/// | HASHES | +/// |------------------| +/// | OFFSETS | +/// |------------------| +/// | DATA | +/// `------------------' +/// +/// The header contains a magic number, version, type of hash function, +/// the number of buckets, total number of hashes, and room for a special struct +/// of data and the length of that struct. +/// +/// The buckets contain an index (e.g. 6) into the hashes array. The hashes +/// section contains all of the 32-bit hash values in contiguous memory, and the +/// offsets contain the offset into the data area for the particular hash. +/// +/// For a lookup example, we could hash a function name and take it modulo the +/// number of buckets giving us our bucket. From there we take the bucket value +/// as an index into the hashes table and look at each successive hash as long +/// as the hash value is still the same modulo result (bucket value) as earlier. +/// If we have a match we look at that same entry in the offsets table and grab +/// the offset in the data for our final match. +/// +/// The DWARFv5 accelerator table consists of zero or more name indices that +/// are output into an on-disk format that looks like this: +/// +/// .------------------. +/// | HEADER | +/// |------------------| +/// | CU LIST | +/// |------------------| +/// | LOCAL TU LIST | +/// |------------------| +/// | FOREIGN TU LIST | +/// |------------------| +/// | HASH TABLE | +/// |------------------| +/// | NAME TABLE | +/// |------------------| +/// | ABBREV TABLE | +/// |------------------| +/// | ENTRY POOL | +/// `------------------' +/// +/// For the full documentation please refer to the DWARF 5 standard. + +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 { + 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() 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 { + OS << "Type: " << dwarf::AtomTypeString(Type) << "\n" + << "Form: " << dwarf::FormEncodingString(Form) << "\n"; + } + + 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; + + SmallVector Atoms; + + HeaderData(ArrayRef AtomList, uint32_t Offset = 0) + : DieOffsetBase(Offset), Atoms(AtomList.begin(), AtomList.end()) {} + +#ifndef NDEBUG + void print(raw_ostream &OS) const { + OS << "DIE Offset Base: " << DieOffsetBase << "\n"; + for (auto Atom : Atoms) + Atom.print(OS); + } + + 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. + AppleAccelTableHeader(ArrayRef Atoms) + : Header(8 + (Atoms.size() * 4)), HeaderData(Atoms) {} + + /// 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 { + Header.print(OS); + HeaderData.print(OS); + } + + void dump() const { print(dbgs()); } +#endif +}; + +/// 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; + }; + + friend struct HashData; + + struct HashData { + StringRef Str; + uint32_t HashValue; + MCSymbol *Sym; + DataArray &Data; + + HashData(StringRef S, DataArray &Data) : Str(S), Data(Data) { + HashValue = djbHash(S); + } + +#ifndef NDEBUG + void print(raw_ostream &OS) { + OS << "Name: " << Str << "\n"; + OS << " Hash Value: " << format("0x%x", HashValue) << "\n"; + OS << " Symbol: "; + if (Sym) + OS << *Sym; + else + OS << ""; + OS << "\n"; + for (auto *Value : Data.Values) + Value->print(OS); + } + + void dump() { print(dbgs()); } +#endif + }; + + /// Allocator for HashData and Values. + BumpPtrAllocator Allocator; + + /// Header containing both the header and header data. + AppleAccelTableHeader Header; + + std::vector Data; + + using StringEntries = StringMap; + StringEntries Entries; + + using HashList = std::vector; + HashList Hashes; + + using BucketList = std::vector; + BucketList Buckets; + + 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: + 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) const override { + OS << " Offset: " << Die->getOffset() << "\n"; + OS << " Tag: " << dwarf::TagString(Die->getTag()) << "\n"; + } +#endif +}; + +} // end namespace llvm + +#endif // LLVM_LIB_CODEGEN_ASMPRINTER_DWARFACCELTABLE_H Index: llvm/trunk/lib/CodeGen/AsmPrinter/AccelTable.cpp =================================================================== --- llvm/trunk/lib/CodeGen/AsmPrinter/AccelTable.cpp +++ llvm/trunk/lib/CodeGen/AsmPrinter/AccelTable.cpp @@ -0,0 +1,221 @@ +//===- llvm/CodeGen/AsmPrinter/AccelTable.cpp - Accelerator Tables --------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file contains support for writing accelerator tables. +// +//===----------------------------------------------------------------------===// + +#include "llvm/CodeGen/AccelTable.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/StringMap.h" +#include "llvm/ADT/Twine.h" +#include "llvm/BinaryFormat/Dwarf.h" +#include "llvm/CodeGen/AsmPrinter.h" +#include "llvm/CodeGen/DIE.h" +#include "llvm/MC/MCExpr.h" +#include "llvm/MC/MCStreamer.h" +#include "llvm/Support/raw_ostream.h" +#include +#include +#include +#include +#include + +using namespace llvm; + +void AppleAccelTableHeader::emit(AsmPrinter *Asm) { + // Emit Header. + Asm->OutStreamer->AddComment("Header Magic"); + Asm->EmitInt32(Header.Magic); + Asm->OutStreamer->AddComment("Header Version"); + Asm->EmitInt16(Header.Version); + Asm->OutStreamer->AddComment("Header Hash Function"); + Asm->EmitInt16(Header.HashFunction); + Asm->OutStreamer->AddComment("Header Bucket Count"); + Asm->EmitInt32(Header.BucketCount); + Asm->OutStreamer->AddComment("Header Hash Count"); + Asm->EmitInt32(Header.HashCount); + Asm->OutStreamer->AddComment("Header Data Length"); + Asm->EmitInt32(Header.HeaderDataLength); + + // Emit Header Data + Asm->OutStreamer->AddComment("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); + } +} + +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)); + if (!Buckets[i].empty()) + 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. + uint64_t PrevHash = std::numeric_limits::max(); + for (auto *HD : Buckets[i]) { + uint32_t HashValue = HD->HashValue; + if (PrevHash != HashValue) + ++index; + PrevHash = HashValue; + } + } +} + +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) { + for (size_t i = 0, e = Buckets.size(); i < e; ++i) { + uint64_t PrevHash = std::numeric_limits::max(); + 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 != Hash->HashValue) + Asm->EmitInt32(0); + // Remember to emit the label for our offset. + Asm->OutStreamer->EmitLabel(Hash->Sym); + Asm->OutStreamer->AddComment(Hash->Str); + Asm->emitDwarfStringOffset(Hash->Data.Name); + Asm->OutStreamer->AddComment("Num DIEs"); + Asm->EmitInt32(Hash->Data.Values.size()); + for (const auto *V : Hash->Data.Values) { + V->emit(Asm); + } + PrevHash = Hash->HashValue; + } + // Emit the final end marker for the bucket. + if (!Buckets[i].empty()) + Asm->EmitInt32(0); + } +} + +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); + } + + // 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 &D : Data) { + uint32_t bucket = D->HashValue % Header.getBucketCount(); + Buckets[bucket].push_back(D); + D->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 AppleAccelTableOffsetData::emit(AsmPrinter *Asm) const { + Asm->EmitInt32(Die->getDebugSectionOffset()); +} + +void AppleAccelTableTypeData::emit(AsmPrinter *Asm) const { + Asm->EmitInt32(Die->getDebugSectionOffset()); + Asm->EmitInt16(Die->getTag()); + Asm->EmitInt8(0); +} Index: llvm/trunk/lib/CodeGen/AsmPrinter/CMakeLists.txt =================================================================== --- llvm/trunk/lib/CodeGen/AsmPrinter/CMakeLists.txt +++ llvm/trunk/lib/CodeGen/AsmPrinter/CMakeLists.txt @@ -1,4 +1,5 @@ add_llvm_library(LLVMAsmPrinter + AccelTable.cpp AddressPool.cpp ARMException.cpp AsmPrinter.cpp @@ -9,7 +10,6 @@ DebugLocStream.cpp DIE.cpp DIEHash.cpp - DwarfAccelTable.cpp DwarfCFIException.cpp DwarfCompileUnit.cpp DwarfDebug.cpp Index: llvm/trunk/lib/CodeGen/AsmPrinter/DwarfAccelTable.h =================================================================== --- llvm/trunk/lib/CodeGen/AsmPrinter/DwarfAccelTable.h +++ llvm/trunk/lib/CodeGen/AsmPrinter/DwarfAccelTable.h @@ -1,385 +0,0 @@ -//==- llvm/CodeGen/DwarfAccelTable.h - Dwarf Accelerator Tables --*- C++ -*-==// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file contains support for writing dwarf accelerator tables. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_LIB_CODEGEN_ASMPRINTER_DWARFACCELTABLE_H -#define LLVM_LIB_CODEGEN_ASMPRINTER_DWARFACCELTABLE_H - -#include "llvm/ADT/ArrayRef.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/StringMap.h" -#include "llvm/ADT/StringRef.h" -#include "llvm/BinaryFormat/Dwarf.h" -#include "llvm/CodeGen/DIE.h" -#include "llvm/CodeGen/DwarfStringPoolEntry.h" -#include "llvm/MC/MCSymbol.h" -#include "llvm/Support/Allocator.h" -#include "llvm/Support/DJB.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/Format.h" -#include "llvm/Support/raw_ostream.h" -#include -#include -#include - -// The dwarf accelerator tables are an indirect hash table optimized -// for null lookup rather than access to known data. They are output into -// an on-disk format that looks like this: -// -// .-------------. -// | HEADER | -// |-------------| -// | BUCKETS | -// |-------------| -// | HASHES | -// |-------------| -// | OFFSETS | -// |-------------| -// | DATA | -// `-------------' -// -// where the header contains a magic number, version, type of hash function, -// the number of buckets, total number of hashes, and room for a special -// struct of data and the length of that struct. -// -// The buckets contain an index (e.g. 6) into the hashes array. The hashes -// section contains all of the 32-bit hash values in contiguous memory, and -// the offsets contain the offset into the data area for the particular -// hash. -// -// For a lookup example, we could hash a function name and take it modulo the -// number of buckets giving us our bucket. From there we take the bucket value -// as an index into the hashes table and look at each successive hash as long -// as the hash value is still the same modulo result (bucket value) as earlier. -// If we have a match we look at that same entry in the offsets table and -// grab the offset in the data for our final match. - -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 { - 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() 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 { - OS << "Type: " << dwarf::AtomTypeString(Type) << "\n" - << "Form: " << dwarf::FormEncodingString(Form) << "\n"; - } - - 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; - - SmallVector Atoms; - - HeaderData(ArrayRef AtomList, uint32_t Offset = 0) - : DieOffsetBase(Offset), Atoms(AtomList.begin(), AtomList.end()) {} - -#ifndef NDEBUG - void print(raw_ostream &OS) const { - OS << "DIE Offset Base: " << DieOffsetBase << "\n"; - for (auto Atom : Atoms) - Atom.print(OS); - } - - 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. - AppleAccelTableHeader(ArrayRef Atoms) - : Header(8 + (Atoms.size() * 4)), HeaderData(Atoms) {} - - /// 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 { - Header.print(OS); - HeaderData.print(OS); - } - - void dump() const { print(dbgs()); } -#endif -}; - -/// 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; - }; - - friend struct HashData; - - struct HashData { - StringRef Str; - uint32_t HashValue; - MCSymbol *Sym; - DataArray &Data; - - HashData(StringRef S, DataArray &Data) : Str(S), Data(Data) { - HashValue = djbHash(S); - } - -#ifndef NDEBUG - void print(raw_ostream &OS) { - OS << "Name: " << Str << "\n"; - OS << " Hash Value: " << format("0x%x", HashValue) << "\n"; - OS << " Symbol: "; - if (Sym) - OS << *Sym; - else - OS << ""; - OS << "\n"; - for (auto *Value : Data.Values) - Value->print(OS); - } - - void dump() { print(dbgs()); } -#endif - }; - - /// Allocator for HashData and Values. - BumpPtrAllocator Allocator; - - /// Header containing both the header and header data. - AppleAccelTableHeader Header; - - std::vector Data; - - using StringEntries = StringMap; - StringEntries Entries; - - using HashList = std::vector; - HashList Hashes; - - using BucketList = std::vector; - BucketList Buckets; - - 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: - 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) const override { - OS << " Offset: " << Die->getOffset() << "\n"; - OS << " Tag: " << dwarf::TagString(Die->getTag()) << "\n"; - } -#endif -}; - -} // end namespace llvm - -#endif // LLVM_LIB_CODEGEN_ASMPRINTER_DWARFACCELTABLE_H Index: llvm/trunk/lib/CodeGen/AsmPrinter/DwarfAccelTable.cpp =================================================================== --- llvm/trunk/lib/CodeGen/AsmPrinter/DwarfAccelTable.cpp +++ llvm/trunk/lib/CodeGen/AsmPrinter/DwarfAccelTable.cpp @@ -1,221 +0,0 @@ -//===- llvm/CodeGen/DwarfAccelTable.cpp - Dwarf Accelerator Tables --------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file contains support for writing dwarf accelerator tables. -// -//===----------------------------------------------------------------------===// - -#include "DwarfAccelTable.h" -#include "llvm/ADT/STLExtras.h" -#include "llvm/ADT/StringMap.h" -#include "llvm/ADT/Twine.h" -#include "llvm/BinaryFormat/Dwarf.h" -#include "llvm/CodeGen/AsmPrinter.h" -#include "llvm/CodeGen/DIE.h" -#include "llvm/MC/MCExpr.h" -#include "llvm/MC/MCStreamer.h" -#include "llvm/Support/raw_ostream.h" -#include -#include -#include -#include -#include - -using namespace llvm; - -void AppleAccelTableHeader::emit(AsmPrinter *Asm) { - // Emit Header. - Asm->OutStreamer->AddComment("Header Magic"); - Asm->EmitInt32(Header.Magic); - Asm->OutStreamer->AddComment("Header Version"); - Asm->EmitInt16(Header.Version); - Asm->OutStreamer->AddComment("Header Hash Function"); - Asm->EmitInt16(Header.HashFunction); - Asm->OutStreamer->AddComment("Header Bucket Count"); - Asm->EmitInt32(Header.BucketCount); - Asm->OutStreamer->AddComment("Header Hash Count"); - Asm->EmitInt32(Header.HashCount); - Asm->OutStreamer->AddComment("Header Data Length"); - Asm->EmitInt32(Header.HeaderDataLength); - - // Emit Header Data - Asm->OutStreamer->AddComment("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); - } -} - -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)); - if (!Buckets[i].empty()) - 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. - uint64_t PrevHash = std::numeric_limits::max(); - for (auto *HD : Buckets[i]) { - uint32_t HashValue = HD->HashValue; - if (PrevHash != HashValue) - ++index; - PrevHash = HashValue; - } - } -} - -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) { - for (size_t i = 0, e = Buckets.size(); i < e; ++i) { - uint64_t PrevHash = std::numeric_limits::max(); - 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 != Hash->HashValue) - Asm->EmitInt32(0); - // Remember to emit the label for our offset. - Asm->OutStreamer->EmitLabel(Hash->Sym); - Asm->OutStreamer->AddComment(Hash->Str); - Asm->emitDwarfStringOffset(Hash->Data.Name); - Asm->OutStreamer->AddComment("Num DIEs"); - Asm->EmitInt32(Hash->Data.Values.size()); - for (const auto *V : Hash->Data.Values) { - V->emit(Asm); - } - PrevHash = Hash->HashValue; - } - // Emit the final end marker for the bucket. - if (!Buckets[i].empty()) - Asm->EmitInt32(0); - } -} - -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); - } - - // 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 &D : Data) { - uint32_t bucket = D->HashValue % Header.getBucketCount(); - Buckets[bucket].push_back(D); - D->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 AppleAccelTableOffsetData::emit(AsmPrinter *Asm) const { - Asm->EmitInt32(Die->getDebugSectionOffset()); -} - -void AppleAccelTableTypeData::emit(AsmPrinter *Asm) const { - Asm->EmitInt32(Die->getDebugSectionOffset()); - Asm->EmitInt16(Die->getTag()); - Asm->EmitInt8(0); -} Index: llvm/trunk/lib/CodeGen/AsmPrinter/DwarfDebug.h =================================================================== --- llvm/trunk/lib/CodeGen/AsmPrinter/DwarfDebug.h +++ llvm/trunk/lib/CodeGen/AsmPrinter/DwarfDebug.h @@ -18,7 +18,6 @@ #include "DbgValueHistoryCalculator.h" #include "DebugHandlerBase.h" #include "DebugLocStream.h" -#include "DwarfAccelTable.h" #include "DwarfFile.h" #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/DenseMap.h" @@ -31,6 +30,7 @@ #include "llvm/ADT/StringMap.h" #include "llvm/ADT/StringRef.h" #include "llvm/BinaryFormat/Dwarf.h" +#include "llvm/CodeGen/AccelTable.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/IR/DebugInfoMetadata.h" #include "llvm/IR/DebugLoc.h" Index: llvm/trunk/lib/CodeGen/AsmPrinter/DwarfDebug.cpp =================================================================== --- llvm/trunk/lib/CodeGen/AsmPrinter/DwarfDebug.cpp +++ llvm/trunk/lib/CodeGen/AsmPrinter/DwarfDebug.cpp @@ -16,7 +16,6 @@ #include "DIEHash.h" #include "DebugLocEntry.h" #include "DebugLocStream.h" -#include "DwarfAccelTable.h" #include "DwarfCompileUnit.h" #include "DwarfExpression.h" #include "DwarfFile.h" @@ -31,6 +30,7 @@ #include "llvm/ADT/Triple.h" #include "llvm/ADT/Twine.h" #include "llvm/BinaryFormat/Dwarf.h" +#include "llvm/CodeGen/AccelTable.h" #include "llvm/CodeGen/AsmPrinter.h" #include "llvm/CodeGen/DIE.h" #include "llvm/CodeGen/LexicalScopes.h"