Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2026-05-10 08:43:26 

0001 //==- include/llvm/CodeGen/AccelTable.h - Accelerator Tables -----*- C++ -*-==//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 /// \file
0009 /// This file contains support for writing accelerator tables.
0010 ///
0011 //===----------------------------------------------------------------------===//
0012 
0013 #ifndef LLVM_CODEGEN_ACCELTABLE_H
0014 #define LLVM_CODEGEN_ACCELTABLE_H
0015 
0016 #include "llvm/ADT/ArrayRef.h"
0017 #include "llvm/ADT/MapVector.h"
0018 #include "llvm/ADT/STLFunctionalExtras.h"
0019 #include "llvm/ADT/StringRef.h"
0020 #include "llvm/BinaryFormat/Dwarf.h"
0021 #include "llvm/CodeGen/DIE.h"
0022 #include "llvm/CodeGen/DwarfStringPoolEntry.h"
0023 #include "llvm/Support/Allocator.h"
0024 #include "llvm/Support/DJB.h"
0025 #include "llvm/Support/Debug.h"
0026 #include <cstdint>
0027 #include <variant>
0028 #include <vector>
0029 
0030 /// \file
0031 /// The DWARF and Apple accelerator tables are an indirect hash table optimized
0032 /// for null lookup rather than access to known data. The Apple accelerator
0033 /// tables are a precursor of the newer DWARF v5 accelerator tables. Both
0034 /// formats share common design ideas.
0035 ///
0036 /// The Apple accelerator table are output into an on-disk format that looks
0037 /// like this:
0038 ///
0039 /// .------------------.
0040 /// |  HEADER          |
0041 /// |------------------|
0042 /// |  BUCKETS         |
0043 /// |------------------|
0044 /// |  HASHES          |
0045 /// |------------------|
0046 /// |  OFFSETS         |
0047 /// |------------------|
0048 /// |  DATA            |
0049 /// `------------------'
0050 ///
0051 /// The header contains a magic number, version, type of hash function,
0052 /// the number of buckets, total number of hashes, and room for a special struct
0053 /// of data and the length of that struct.
0054 ///
0055 /// The buckets contain an index (e.g. 6) into the hashes array. The hashes
0056 /// section contains all of the 32-bit hash values in contiguous memory, and the
0057 /// offsets contain the offset into the data area for the particular hash.
0058 ///
0059 /// For a lookup example, we could hash a function name and take it modulo the
0060 /// number of buckets giving us our bucket. From there we take the bucket value
0061 /// as an index into the hashes table and look at each successive hash as long
0062 /// as the hash value is still the same modulo result (bucket value) as earlier.
0063 /// If we have a match we look at that same entry in the offsets table and grab
0064 /// the offset in the data for our final match.
0065 ///
0066 /// The DWARF v5 accelerator table consists of zero or more name indices that
0067 /// are output into an on-disk format that looks like this:
0068 ///
0069 /// .------------------.
0070 /// |  HEADER          |
0071 /// |------------------|
0072 /// |  CU LIST         |
0073 /// |------------------|
0074 /// |  LOCAL TU LIST   |
0075 /// |------------------|
0076 /// |  FOREIGN TU LIST |
0077 /// |------------------|
0078 /// |  HASH TABLE      |
0079 /// |------------------|
0080 /// |  NAME TABLE      |
0081 /// |------------------|
0082 /// |  ABBREV TABLE    |
0083 /// |------------------|
0084 /// |  ENTRY POOL      |
0085 /// `------------------'
0086 ///
0087 /// For the full documentation please refer to the DWARF 5 standard.
0088 ///
0089 ///
0090 /// This file defines the class template AccelTable, which is represents an
0091 /// abstract view of an Accelerator table, without any notion of an on-disk
0092 /// layout. This class is parameterized by an entry type, which should derive
0093 /// from AccelTableData. This is the type of individual entries in the table,
0094 /// and it should store the data necessary to emit them. AppleAccelTableData is
0095 /// the base class for Apple Accelerator Table entries, which have a uniform
0096 /// structure based on a sequence of Atoms. There are different sub-classes
0097 /// derived from AppleAccelTable, which differ in the set of Atoms and how they
0098 /// obtain their values.
0099 ///
0100 /// An Apple Accelerator Table can be serialized by calling emitAppleAccelTable
0101 /// function.
0102 
0103 namespace llvm {
0104 
0105 class AsmPrinter;
0106 class DwarfDebug;
0107 class DwarfTypeUnit;
0108 class MCSymbol;
0109 class raw_ostream;
0110 
0111 /// Interface which the different types of accelerator table data have to
0112 /// conform. It serves as a base class for different values of the template
0113 /// argument of the AccelTable class template.
0114 class AccelTableData {
0115 public:
0116   virtual ~AccelTableData() = default;
0117 
0118   bool operator<(const AccelTableData &Other) const {
0119     return order() < Other.order();
0120   }
0121 
0122     // Subclasses should implement:
0123     // static uint32_t hash(StringRef Name);
0124 
0125 #ifndef NDEBUG
0126   virtual void print(raw_ostream &OS) const = 0;
0127 #endif
0128 protected:
0129   virtual uint64_t order() const = 0;
0130 };
0131 
0132 /// A base class holding non-template-dependant functionality of the AccelTable
0133 /// class. Clients should not use this class directly but rather instantiate
0134 /// AccelTable with a type derived from AccelTableData.
0135 class AccelTableBase {
0136 public:
0137   using HashFn = uint32_t(StringRef);
0138 
0139   /// Represents a group of entries with identical name (and hence, hash value).
0140   struct HashData {
0141     DwarfStringPoolEntryRef Name;
0142     uint32_t HashValue;
0143     std::vector<AccelTableData *> Values;
0144     MCSymbol *Sym;
0145 
0146     /// Get all AccelTableData cast as a `T`.
0147     template <typename T = AccelTableData *> auto getValues() const {
0148       static_assert(std::is_pointer<T>());
0149       static_assert(
0150           std::is_base_of<AccelTableData, std::remove_pointer_t<T>>());
0151       return map_range(
0152           Values, [](AccelTableData *Data) { return static_cast<T>(Data); });
0153     }
0154 
0155 #ifndef NDEBUG
0156     void print(raw_ostream &OS) const;
0157     void dump() const { print(dbgs()); }
0158 #endif
0159   };
0160   using HashList = std::vector<HashData *>;
0161   using BucketList = std::vector<HashList>;
0162 
0163 protected:
0164   /// Allocator for HashData and Values.
0165   BumpPtrAllocator Allocator;
0166 
0167   using StringEntries = MapVector<StringRef, HashData>;
0168   StringEntries Entries;
0169 
0170   HashFn *Hash;
0171   uint32_t BucketCount = 0;
0172   uint32_t UniqueHashCount = 0;
0173 
0174   HashList Hashes;
0175   BucketList Buckets;
0176 
0177   void computeBucketCount();
0178 
0179   AccelTableBase(HashFn *Hash) : Hash(Hash) {}
0180 
0181 public:
0182   void finalize(AsmPrinter *Asm, StringRef Prefix);
0183   ArrayRef<HashList> getBuckets() const { return Buckets; }
0184   uint32_t getBucketCount() const { return BucketCount; }
0185   uint32_t getUniqueHashCount() const { return UniqueHashCount; }
0186   uint32_t getUniqueNameCount() const { return Entries.size(); }
0187 
0188 #ifndef NDEBUG
0189   void print(raw_ostream &OS) const;
0190   void dump() const { print(dbgs()); }
0191 #endif
0192 
0193   AccelTableBase(const AccelTableBase &) = delete;
0194   void operator=(const AccelTableBase &) = delete;
0195 };
0196 
0197 /// This class holds an abstract representation of an Accelerator Table,
0198 /// consisting of a sequence of buckets, each bucket containint a sequence of
0199 /// HashData entries. The class is parameterized by the type of entries it
0200 /// holds. The type template parameter also defines the hash function to use for
0201 /// hashing names.
0202 template <typename DataT> class AccelTable : public AccelTableBase {
0203 public:
0204   AccelTable() : AccelTableBase(DataT::hash) {}
0205 
0206   template <typename... Types>
0207   void addName(DwarfStringPoolEntryRef Name, Types &&... Args);
0208   void clear() { Entries.clear(); }
0209   void addEntries(AccelTable<DataT> &Table);
0210   const StringEntries getEntries() const { return Entries; }
0211 };
0212 
0213 template <typename AccelTableDataT>
0214 template <typename... Types>
0215 void AccelTable<AccelTableDataT>::addName(DwarfStringPoolEntryRef Name,
0216                                           Types &&... Args) {
0217   assert(Buckets.empty() && "Already finalized!");
0218   // If the string is in the list already then add this die to the list
0219   // otherwise add a new one.
0220   auto &It = Entries[Name.getString()];
0221   if (It.Values.empty()) {
0222     It.Name = Name;
0223     It.HashValue = Hash(Name.getString());
0224   }
0225   It.Values.push_back(new (Allocator)
0226                           AccelTableDataT(std::forward<Types>(Args)...));
0227 }
0228 
0229 /// A base class for different implementations of Data classes for Apple
0230 /// Accelerator Tables. The columns in the table are defined by the static Atoms
0231 /// variable defined on the subclasses.
0232 class AppleAccelTableData : public AccelTableData {
0233 public:
0234   /// An Atom defines the form of the data in an Apple accelerator table.
0235   /// Conceptually it is a column in the accelerator consisting of a type and a
0236   /// specification of the form of its data.
0237   struct Atom {
0238     /// Atom Type.
0239     const uint16_t Type;
0240     /// DWARF Form.
0241     const uint16_t Form;
0242 
0243     constexpr Atom(uint16_t Type, uint16_t Form) : Type(Type), Form(Form) {}
0244 
0245 #ifndef NDEBUG
0246     void print(raw_ostream &OS) const;
0247     void dump() const { print(dbgs()); }
0248 #endif
0249   };
0250   // Subclasses should define:
0251   // static constexpr Atom Atoms[];
0252 
0253   virtual void emit(AsmPrinter *Asm) const = 0;
0254 
0255   static uint32_t hash(StringRef Buffer) { return djbHash(Buffer); }
0256 };
0257 
0258 /// Helper class to identify an entry in DWARF5AccelTable based on their DIE
0259 /// offset and UnitID.
0260 struct OffsetAndUnitID {
0261   uint64_t Offset = 0;
0262   uint32_t UnitID = 0;
0263   bool IsTU = false;
0264   OffsetAndUnitID() = delete;
0265   OffsetAndUnitID(uint64_t Offset, uint32_t UnitID, bool IsTU)
0266       : Offset(Offset), UnitID(UnitID), IsTU(IsTU) {}
0267   uint64_t offset() const { return Offset; };
0268   uint32_t unitID() const { return UnitID; };
0269   bool isTU() const { return IsTU; }
0270 };
0271 
0272 template <> struct DenseMapInfo<OffsetAndUnitID> {
0273   static inline OffsetAndUnitID getEmptyKey() {
0274     return OffsetAndUnitID(-1, -1, false);
0275   }
0276   static inline OffsetAndUnitID getTombstoneKey() {
0277     return OffsetAndUnitID(-2, -2, false);
0278   }
0279   static unsigned getHashValue(const OffsetAndUnitID &Val) {
0280     return (unsigned)llvm::hash_combine(Val.offset(), Val.unitID(), Val.IsTU);
0281   }
0282   static bool isEqual(const OffsetAndUnitID &LHS, const OffsetAndUnitID &RHS) {
0283     return LHS.offset() == RHS.offset() && LHS.unitID() == RHS.unitID() &&
0284            LHS.IsTU == RHS.isTU();
0285   }
0286 };
0287 
0288 /// The Data class implementation for DWARF v5 accelerator table. Unlike the
0289 /// Apple Data classes, this class is just a DIE wrapper, and does not know to
0290 /// serialize itself. The complete serialization logic is in the
0291 /// emitDWARF5AccelTable function.
0292 class DWARF5AccelTableData : public AccelTableData {
0293 public:
0294   static uint32_t hash(StringRef Name) { return caseFoldingDjbHash(Name); }
0295 
0296   DWARF5AccelTableData(const DIE &Die, const uint32_t UnitID, const bool IsTU);
0297   DWARF5AccelTableData(const uint64_t DieOffset,
0298                        const std::optional<uint64_t> DefiningParentOffset,
0299                        const unsigned DieTag, const unsigned UnitID,
0300                        const bool IsTU)
0301       : OffsetVal(DieOffset), ParentOffset(DefiningParentOffset),
0302         DieTag(DieTag), AbbrevNumber(0), IsTU(IsTU), UnitID(UnitID) {}
0303 
0304 #ifndef NDEBUG
0305   void print(raw_ostream &OS) const override;
0306 #endif
0307 
0308   uint64_t getDieOffset() const {
0309     assert(isNormalized() && "Accessing DIE Offset before normalizing.");
0310     return std::get<uint64_t>(OffsetVal);
0311   }
0312 
0313   OffsetAndUnitID getDieOffsetAndUnitID() const {
0314     return {getDieOffset(), getUnitID(), isTU()};
0315   }
0316 
0317   unsigned getDieTag() const { return DieTag; }
0318   unsigned getUnitID() const { return UnitID; }
0319   bool isTU() const { return IsTU; }
0320   void normalizeDIEToOffset() {
0321     assert(!isNormalized() && "Accessing offset after normalizing.");
0322     const DIE *Entry = std::get<const DIE *>(OffsetVal);
0323     ParentOffset = getDefiningParentDieOffset(*Entry);
0324     OffsetVal = Entry->getOffset();
0325   }
0326   bool isNormalized() const {
0327     return std::holds_alternative<uint64_t>(OffsetVal);
0328   }
0329 
0330   std::optional<uint64_t> getParentDieOffset() const {
0331     if (auto OffsetAndId = getParentDieOffsetAndUnitID())
0332       return OffsetAndId->offset();
0333     return {};
0334   }
0335 
0336   std::optional<OffsetAndUnitID> getParentDieOffsetAndUnitID() const {
0337     assert(isNormalized() && "Accessing DIE Offset before normalizing.");
0338     if (!ParentOffset)
0339       return std::nullopt;
0340     return OffsetAndUnitID(*ParentOffset, getUnitID(), isTU());
0341   }
0342 
0343   /// Sets AbbrevIndex for an Entry.
0344   void setAbbrevNumber(uint16_t AbbrevNum) { AbbrevNumber = AbbrevNum; }
0345 
0346   /// Returns AbbrevIndex for an Entry.
0347   uint16_t getAbbrevNumber() const { return AbbrevNumber; }
0348 
0349   /// If `Die` has a non-null parent and the parent is not a declaration,
0350   /// return its offset.
0351   static std::optional<uint64_t> getDefiningParentDieOffset(const DIE &Die);
0352 
0353 protected:
0354   std::variant<const DIE *, uint64_t> OffsetVal;
0355   std::optional<uint64_t> ParentOffset;
0356   uint32_t DieTag : 16;
0357   uint32_t AbbrevNumber : 15;
0358   uint32_t IsTU : 1;
0359   uint32_t UnitID;
0360   uint64_t order() const override { return getDieOffset(); }
0361 };
0362 
0363 class DebugNamesAbbrev : public FoldingSetNode {
0364 public:
0365   uint32_t DieTag;
0366   uint32_t Number;
0367   struct AttributeEncoding {
0368     dwarf::Index Index;
0369     dwarf::Form Form;
0370   };
0371   DebugNamesAbbrev(uint32_t DieTag) : DieTag(DieTag), Number(0) {}
0372   /// Add attribute encoding to an abbreviation.
0373   void addAttribute(const DebugNamesAbbrev::AttributeEncoding &Attr) {
0374     AttrVect.push_back(Attr);
0375   }
0376   /// Set abbreviation tag index.
0377   void setNumber(uint32_t AbbrevNumber) { Number = AbbrevNumber; }
0378   /// Get abbreviation tag index.
0379   uint32_t getNumber() const { return Number; }
0380   /// Get DIE Tag.
0381   uint32_t getDieTag() const { return DieTag; }
0382   /// Used to gather unique data for the abbreviation folding set.
0383   void Profile(FoldingSetNodeID &ID) const;
0384   /// Returns attributes for an abbreviation.
0385   const SmallVector<AttributeEncoding, 1> &getAttributes() const {
0386     return AttrVect;
0387   }
0388 
0389 private:
0390   SmallVector<AttributeEncoding, 1> AttrVect;
0391 };
0392 
0393 struct TypeUnitMetaInfo {
0394   // Symbol for start of the TU section or signature if this is SplitDwarf.
0395   std::variant<MCSymbol *, uint64_t> LabelOrSignature;
0396   // Unique ID of Type Unit.
0397   unsigned UniqueID;
0398 };
0399 using TUVectorTy = SmallVector<TypeUnitMetaInfo, 1>;
0400 class DWARF5AccelTable : public AccelTable<DWARF5AccelTableData> {
0401   // Symbols to start of all the TU sections that were generated.
0402   TUVectorTy TUSymbolsOrHashes;
0403 
0404 public:
0405   struct UnitIndexAndEncoding {
0406     unsigned Index;
0407     DebugNamesAbbrev::AttributeEncoding Encoding;
0408   };
0409   /// Returns type units that were constructed.
0410   const TUVectorTy &getTypeUnitsSymbols() { return TUSymbolsOrHashes; }
0411   /// Add a type unit start symbol.
0412   void addTypeUnitSymbol(DwarfTypeUnit &U);
0413   /// Add a type unit Signature.
0414   void addTypeUnitSignature(DwarfTypeUnit &U);
0415   /// Convert DIE entries to explicit offset.
0416   /// Needs to be called after DIE offsets are computed.
0417   void convertDieToOffset() {
0418     for (auto &Entry : Entries) {
0419       for (auto *Data : Entry.second.getValues<DWARF5AccelTableData *>()) {
0420         // For TU we normalize as each Unit is emitted.
0421         // So when this is invoked after CU construction we will be in mixed
0422         // state.
0423         if (!Data->isNormalized())
0424           Data->normalizeDIEToOffset();
0425       }
0426     }
0427   }
0428 
0429   void addTypeEntries(DWARF5AccelTable &Table) {
0430     for (auto &Entry : Table.getEntries()) {
0431       for (auto *Data : Entry.second.getValues<DWARF5AccelTableData *>()) {
0432         addName(Entry.second.Name, Data->getDieOffset(),
0433                 Data->getParentDieOffset(), Data->getDieTag(),
0434                 Data->getUnitID(), Data->isTU());
0435       }
0436     }
0437   }
0438 };
0439 
0440 void emitAppleAccelTableImpl(AsmPrinter *Asm, AccelTableBase &Contents,
0441                              StringRef Prefix, const MCSymbol *SecBegin,
0442                              ArrayRef<AppleAccelTableData::Atom> Atoms);
0443 
0444 /// Emit an Apple Accelerator Table consisting of entries in the specified
0445 /// AccelTable. The DataT template parameter should be derived from
0446 /// AppleAccelTableData.
0447 template <typename DataT>
0448 void emitAppleAccelTable(AsmPrinter *Asm, AccelTable<DataT> &Contents,
0449                          StringRef Prefix, const MCSymbol *SecBegin) {
0450   static_assert(std::is_convertible<DataT *, AppleAccelTableData *>::value);
0451   emitAppleAccelTableImpl(Asm, Contents, Prefix, SecBegin, DataT::Atoms);
0452 }
0453 
0454 void emitDWARF5AccelTable(AsmPrinter *Asm, DWARF5AccelTable &Contents,
0455                           const DwarfDebug &DD,
0456                           ArrayRef<std::unique_ptr<DwarfCompileUnit>> CUs);
0457 
0458 /// Emit a DWARFv5 Accelerator Table consisting of entries in the specified
0459 /// AccelTable. The \p CUs contains either symbols keeping offsets to the
0460 /// start of compilation unit, either offsets to the start of compilation
0461 /// unit themselves.
0462 void emitDWARF5AccelTable(
0463     AsmPrinter *Asm, DWARF5AccelTable &Contents,
0464     ArrayRef<std::variant<MCSymbol *, uint64_t>> CUs,
0465     llvm::function_ref<std::optional<DWARF5AccelTable::UnitIndexAndEncoding>(
0466         const DWARF5AccelTableData &)>
0467         getIndexForEntry);
0468 
0469 /// Accelerator table data implementation for simple Apple accelerator tables
0470 /// with just a DIE reference.
0471 class AppleAccelTableOffsetData : public AppleAccelTableData {
0472 public:
0473   AppleAccelTableOffsetData(const DIE &D) : Die(D) {}
0474 
0475   void emit(AsmPrinter *Asm) const override;
0476 
0477   static constexpr Atom Atoms[] = {
0478       Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
0479 
0480 #ifndef NDEBUG
0481   void print(raw_ostream &OS) const override;
0482 #endif
0483 protected:
0484   uint64_t order() const override { return Die.getOffset(); }
0485 
0486   const DIE &Die;
0487 };
0488 
0489 /// Accelerator table data implementation for Apple type accelerator tables.
0490 class AppleAccelTableTypeData : public AppleAccelTableOffsetData {
0491 public:
0492   AppleAccelTableTypeData(const DIE &D) : AppleAccelTableOffsetData(D) {}
0493 
0494   void emit(AsmPrinter *Asm) const override;
0495 
0496   static constexpr Atom Atoms[] = {
0497       Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4),
0498       Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2),
0499       Atom(dwarf::DW_ATOM_type_flags, dwarf::DW_FORM_data1)};
0500 
0501 #ifndef NDEBUG
0502   void print(raw_ostream &OS) const override;
0503 #endif
0504 };
0505 
0506 /// Accelerator table data implementation for simple Apple accelerator tables
0507 /// with a DIE offset but no actual DIE pointer.
0508 class AppleAccelTableStaticOffsetData : public AppleAccelTableData {
0509 public:
0510   AppleAccelTableStaticOffsetData(uint32_t Offset) : Offset(Offset) {}
0511 
0512   void emit(AsmPrinter *Asm) const override;
0513 
0514   static constexpr Atom Atoms[] = {
0515       Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
0516 
0517 #ifndef NDEBUG
0518   void print(raw_ostream &OS) const override;
0519 #endif
0520 protected:
0521   uint64_t order() const override { return Offset; }
0522 
0523   uint32_t Offset;
0524 };
0525 
0526 /// Accelerator table data implementation for type accelerator tables with
0527 /// a DIE offset but no actual DIE pointer.
0528 class AppleAccelTableStaticTypeData : public AppleAccelTableStaticOffsetData {
0529 public:
0530   AppleAccelTableStaticTypeData(uint32_t Offset, uint16_t Tag,
0531                                 bool ObjCClassIsImplementation,
0532                                 uint32_t QualifiedNameHash)
0533       : AppleAccelTableStaticOffsetData(Offset),
0534         QualifiedNameHash(QualifiedNameHash), Tag(Tag),
0535         ObjCClassIsImplementation(ObjCClassIsImplementation) {}
0536 
0537   void emit(AsmPrinter *Asm) const override;
0538 
0539   static constexpr Atom Atoms[] = {
0540       Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4),
0541       Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2),
0542       Atom(5, dwarf::DW_FORM_data1), Atom(6, dwarf::DW_FORM_data4)};
0543 
0544 #ifndef NDEBUG
0545   void print(raw_ostream &OS) const override;
0546 #endif
0547 protected:
0548   uint64_t order() const override { return Offset; }
0549 
0550   uint32_t QualifiedNameHash;
0551   uint16_t Tag;
0552   bool ObjCClassIsImplementation;
0553 };
0554 
0555 } // end namespace llvm
0556 
0557 #endif // LLVM_CODEGEN_ACCELTABLE_H
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!