| //==- include/llvm/CodeGen/AccelTable.h - Accelerator Tables -----*- C++ -*-==// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| /// \file |
| /// This file contains support for writing accelerator tables. |
| /// |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef LLVM_CODEGEN_ACCELTABLE_H |
| #define LLVM_CODEGEN_ACCELTABLE_H |
| |
| #include "llvm/ADT/ArrayRef.h" |
| #include "llvm/ADT/MapVector.h" |
| #include "llvm/ADT/STLFunctionalExtras.h" |
| #include "llvm/ADT/StringRef.h" |
| #include "llvm/BinaryFormat/Dwarf.h" |
| #include "llvm/CodeGen/DIE.h" |
| #include "llvm/CodeGen/DwarfStringPoolEntry.h" |
| #include "llvm/Support/Allocator.h" |
| #include "llvm/Support/DJB.h" |
| #include "llvm/Support/Debug.h" |
| #include <cstdint> |
| #include <variant> |
| #include <vector> |
| |
| /// \file |
| /// 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 DWARF v5 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. |
| /// |
| /// |
| /// 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. |
| |
| namespace llvm { |
| |
| class AsmPrinter; |
| class DwarfDebug; |
| class DwarfTypeUnit; |
| class MCSymbol; |
| class raw_ostream; |
| |
| /// Interface which the different types of accelerator table data have to |
| /// conform. It serves as a base class for different values of the template |
| /// argument of the AccelTable class template. |
| class AccelTableData { |
| public: |
| virtual ~AccelTableData() = default; |
| |
| 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 |
| protected: |
| virtual uint64_t order() const = 0; |
| }; |
| |
| /// 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<AccelTableData *> Values; |
| MCSymbol *Sym; |
| |
| /// Get all AccelTableData cast as a `T`. |
| template <typename T = AccelTableData *> auto getValues() const { |
| static_assert(std::is_pointer<T>()); |
| static_assert( |
| std::is_base_of<AccelTableData, std::remove_pointer_t<T>>()); |
| return map_range( |
| Values, [](AccelTableData *Data) { return static_cast<T>(Data); }); |
| } |
| |
| #ifndef NDEBUG |
| void print(raw_ostream &OS) const; |
| void dump() const { print(dbgs()); } |
| #endif |
| }; |
| using HashList = std::vector<HashData *>; |
| using BucketList = std::vector<HashList>; |
| |
| protected: |
| /// Allocator for HashData and Values. |
| BumpPtrAllocator Allocator; |
| |
| using StringEntries = MapVector<StringRef, HashData>; |
| StringEntries Entries; |
| |
| HashFn *Hash; |
| uint32_t BucketCount = 0; |
| uint32_t UniqueHashCount = 0; |
| |
| HashList Hashes; |
| BucketList Buckets; |
| |
| void computeBucketCount(); |
| |
| AccelTableBase(HashFn *Hash) : Hash(Hash) {} |
| |
| public: |
| void finalize(AsmPrinter *Asm, StringRef Prefix); |
| ArrayRef<HashList> 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; |
| }; |
| |
| /// 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 <typename DataT> class AccelTable : public AccelTableBase { |
| public: |
| AccelTable() : AccelTableBase(DataT::hash) {} |
| |
| template <typename... Types> |
| void addName(DwarfStringPoolEntryRef Name, Types &&... Args); |
| void clear() { Entries.clear(); } |
| void addEntries(AccelTable<DataT> &Table); |
| const StringEntries getEntries() const { return Entries; } |
| }; |
| |
| template <typename AccelTableDataT> |
| template <typename... Types> |
| void AccelTable<AccelTableDataT>::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 &It = Entries[Name.getString()]; |
| if (It.Values.empty()) { |
| It.Name = Name; |
| It.HashValue = Hash(Name.getString()); |
| } |
| It.Values.push_back(new (Allocator) |
| AccelTableDataT(std::forward<Types>(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); } |
| }; |
| |
| /// Helper class to identify an entry in DWARF5AccelTable based on their DIE |
| /// offset and UnitID. |
| struct OffsetAndUnitID : std::pair<uint64_t, uint32_t> { |
| using Base = std::pair<uint64_t, uint32_t>; |
| OffsetAndUnitID(Base B) : Base(B) {} |
| |
| OffsetAndUnitID(uint64_t Offset, uint32_t UnitID) : Base(Offset, UnitID) {} |
| uint64_t offset() const { return first; }; |
| uint32_t unitID() const { return second; }; |
| }; |
| |
| template <> |
| struct DenseMapInfo<OffsetAndUnitID> : DenseMapInfo<OffsetAndUnitID::Base> {}; |
| |
| /// The Data class implementation for DWARF v5 accelerator table. Unlike the |
| /// Apple Data classes, this class is just a DIE wrapper, and does not know to |
| /// serialize itself. The complete serialization logic is in the |
| /// emitDWARF5AccelTable function. |
| class DWARF5AccelTableData : public AccelTableData { |
| public: |
| struct AttributeEncoding { |
| dwarf::Index Index; |
| dwarf::Form Form; |
| }; |
| |
| static uint32_t hash(StringRef Name) { return caseFoldingDjbHash(Name); } |
| |
| DWARF5AccelTableData(const DIE &Die, const uint32_t UnitID, |
| const bool IsTU = false); |
| DWARF5AccelTableData(const uint64_t DieOffset, |
| const std::optional<uint64_t> DefiningParentOffset, |
| const unsigned DieTag, const unsigned UnitID, |
| const bool IsTU = false) |
| : OffsetVal(DieOffset), ParentOffset(DefiningParentOffset), |
| DieTag(DieTag), UnitID(UnitID), IsTU(IsTU) {} |
| |
| #ifndef NDEBUG |
| void print(raw_ostream &OS) const override; |
| #endif |
| |
| uint64_t getDieOffset() const { |
| assert(isNormalized() && "Accessing DIE Offset before normalizing."); |
| return std::get<uint64_t>(OffsetVal); |
| } |
| |
| OffsetAndUnitID getDieOffsetAndUnitID() const { |
| return {getDieOffset(), UnitID}; |
| } |
| |
| unsigned getDieTag() const { return DieTag; } |
| unsigned getUnitID() const { return UnitID; } |
| bool isTU() const { return IsTU; } |
| void normalizeDIEToOffset() { |
| assert(!isNormalized() && "Accessing offset after normalizing."); |
| const DIE *Entry = std::get<const DIE *>(OffsetVal); |
| ParentOffset = getDefiningParentDieOffset(*Entry); |
| OffsetVal = Entry->getOffset(); |
| } |
| bool isNormalized() const { |
| return std::holds_alternative<uint64_t>(OffsetVal); |
| } |
| |
| std::optional<uint64_t> getParentDieOffset() const { |
| if (auto OffsetAndId = getParentDieOffsetAndUnitID()) |
| return OffsetAndId->offset(); |
| return {}; |
| } |
| |
| std::optional<OffsetAndUnitID> getParentDieOffsetAndUnitID() const { |
| assert(isNormalized() && "Accessing DIE Offset before normalizing."); |
| if (!ParentOffset) |
| return std::nullopt; |
| return OffsetAndUnitID(*ParentOffset, getUnitID()); |
| } |
| |
| /// If `Die` has a non-null parent and the parent is not a declaration, |
| /// return its offset. |
| static std::optional<uint64_t> getDefiningParentDieOffset(const DIE &Die); |
| |
| protected: |
| std::variant<const DIE *, uint64_t> OffsetVal; |
| std::optional<uint64_t> ParentOffset; |
| uint32_t DieTag : 16; |
| uint32_t UnitID : 15; |
| uint32_t IsTU : 1; |
| |
| uint64_t order() const override { return getDieOffset(); } |
| }; |
| |
| struct TypeUnitMetaInfo { |
| // Symbol for start of the TU section or signature if this is SplitDwarf. |
| std::variant<MCSymbol *, uint64_t> LabelOrSignature; |
| // Unique ID of Type Unit. |
| unsigned UniqueID; |
| }; |
| using TUVectorTy = SmallVector<TypeUnitMetaInfo, 1>; |
| class DWARF5AccelTable : public AccelTable<DWARF5AccelTableData> { |
| // Symbols to start of all the TU sections that were generated. |
| TUVectorTy TUSymbolsOrHashes; |
| |
| public: |
| struct UnitIndexAndEncoding { |
| unsigned Index; |
| DWARF5AccelTableData::AttributeEncoding Encoding; |
| }; |
| /// Returns type units that were constructed. |
| const TUVectorTy &getTypeUnitsSymbols() { return TUSymbolsOrHashes; } |
| /// Add a type unit start symbol. |
| void addTypeUnitSymbol(DwarfTypeUnit &U); |
| /// Add a type unit Signature. |
| void addTypeUnitSignature(DwarfTypeUnit &U); |
| /// Convert DIE entries to explicit offset. |
| /// Needs to be called after DIE offsets are computed. |
| void convertDieToOffset() { |
| for (auto &Entry : Entries) { |
| for (auto *Data : Entry.second.getValues<DWARF5AccelTableData *>()) { |
| // For TU we normalize as each Unit is emitted. |
| // So when this is invoked after CU construction we will be in mixed |
| // state. |
| if (!Data->isNormalized()) |
| Data->normalizeDIEToOffset(); |
| } |
| } |
| } |
| |
| void addTypeEntries(DWARF5AccelTable &Table) { |
| for (auto &Entry : Table.getEntries()) { |
| for (auto *Data : Entry.second.getValues<DWARF5AccelTableData *>()) { |
| addName(Entry.second.Name, Data->getDieOffset(), |
| Data->getParentDieOffset(), Data->getDieTag(), |
| Data->getUnitID(), true); |
| } |
| } |
| } |
| }; |
| |
| void emitAppleAccelTableImpl(AsmPrinter *Asm, AccelTableBase &Contents, |
| StringRef Prefix, const MCSymbol *SecBegin, |
| ArrayRef<AppleAccelTableData::Atom> Atoms); |
| |
| /// Emit an Apple Accelerator Table consisting of entries in the specified |
| /// AccelTable. The DataT template parameter should be derived from |
| /// AppleAccelTableData. |
| template <typename DataT> |
| void emitAppleAccelTable(AsmPrinter *Asm, AccelTable<DataT> &Contents, |
| StringRef Prefix, const MCSymbol *SecBegin) { |
| static_assert(std::is_convertible<DataT *, AppleAccelTableData *>::value); |
| emitAppleAccelTableImpl(Asm, Contents, Prefix, SecBegin, DataT::Atoms); |
| } |
| |
| void emitDWARF5AccelTable(AsmPrinter *Asm, DWARF5AccelTable &Contents, |
| const DwarfDebug &DD, |
| ArrayRef<std::unique_ptr<DwarfCompileUnit>> CUs); |
| |
| /// Emit a DWARFv5 Accelerator Table consisting of entries in the specified |
| /// AccelTable. The \p CUs contains either symbols keeping offsets to the |
| /// start of compilation unit, either offsets to the start of compilation |
| /// unit themselves. |
| void emitDWARF5AccelTable( |
| AsmPrinter *Asm, DWARF5AccelTable &Contents, |
| ArrayRef<std::variant<MCSymbol *, uint64_t>> CUs, |
| llvm::function_ref<std::optional<DWARF5AccelTable::UnitIndexAndEncoding>( |
| const DWARF5AccelTableData &)> |
| getIndexForEntry); |
| |
| /// 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) {} |
| |
| void emit(AsmPrinter *Asm) const override; |
| |
| static constexpr Atom Atoms[] = { |
| Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)}; |
| |
| #ifndef NDEBUG |
| void print(raw_ostream &OS) const override; |
| #endif |
| protected: |
| uint64_t order() const override { return Die.getOffset(); } |
| |
| const DIE &Die; |
| }; |
| |
| /// Accelerator table data implementation for Apple type accelerator tables. |
| class AppleAccelTableTypeData : public AppleAccelTableOffsetData { |
| public: |
| AppleAccelTableTypeData(const DIE &D) : AppleAccelTableOffsetData(D) {} |
| |
| void emit(AsmPrinter *Asm) const override; |
| |
| 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)}; |
| |
| #ifndef NDEBUG |
| void print(raw_ostream &OS) const override; |
| #endif |
| }; |
| |
| /// 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) {} |
| |
| void emit(AsmPrinter *Asm) const override; |
| |
| static constexpr Atom Atoms[] = { |
| Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)}; |
| |
| #ifndef NDEBUG |
| void print(raw_ostream &OS) const override; |
| #endif |
| protected: |
| uint64_t order() const override { return Offset; } |
| |
| uint32_t Offset; |
| }; |
| |
| /// Accelerator table data implementation for type accelerator tables with |
| /// a DIE offset but no actual DIE pointer. |
| class AppleAccelTableStaticTypeData : public AppleAccelTableStaticOffsetData { |
| public: |
| AppleAccelTableStaticTypeData(uint32_t Offset, uint16_t Tag, |
| bool ObjCClassIsImplementation, |
| uint32_t QualifiedNameHash) |
| : AppleAccelTableStaticOffsetData(Offset), |
| QualifiedNameHash(QualifiedNameHash), Tag(Tag), |
| ObjCClassIsImplementation(ObjCClassIsImplementation) {} |
| |
| void emit(AsmPrinter *Asm) const override; |
| |
| 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)}; |
| |
| #ifndef NDEBUG |
| void print(raw_ostream &OS) const override; |
| #endif |
| protected: |
| uint64_t order() const override { return Offset; } |
| |
| uint32_t QualifiedNameHash; |
| uint16_t Tag; |
| bool ObjCClassIsImplementation; |
| }; |
| |
| } // end namespace llvm |
| |
| #endif // LLVM_CODEGEN_ACCELTABLE_H |