LLVM 20.0.0git
Classes | Namespaces | Typedefs | Functions
AccelTable.h File Reference

This file contains support for writing accelerator tables. More...

#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>

Go to the source code of this file.

Classes

class  llvm::AccelTableData
 Interface which the different types of accelerator table data have to conform. More...
 
class  llvm::AccelTableBase
 A base class holding non-template-dependant functionality of the AccelTable class. More...
 
struct  llvm::AccelTableBase::HashData
 Represents a group of entries with identical name (and hence, hash value). More...
 
class  llvm::AccelTable< DataT >
 This class holds an abstract representation of an Accelerator Table, consisting of a sequence of buckets, each bucket containint a sequence of HashData entries. More...
 
class  llvm::AppleAccelTableData
 A base class for different implementations of Data classes for Apple Accelerator Tables. More...
 
struct  llvm::AppleAccelTableData::Atom
 An Atom defines the form of the data in an Apple accelerator table. More...
 
struct  llvm::OffsetAndUnitID
 Helper class to identify an entry in DWARF5AccelTable based on their DIE offset and UnitID. More...
 
struct  llvm::DenseMapInfo< OffsetAndUnitID >
 
class  llvm::DWARF5AccelTableData
 The Data class implementation for DWARF v5 accelerator table. More...
 
class  llvm::DebugNamesAbbrev
 
struct  llvm::DebugNamesAbbrev::AttributeEncoding
 
struct  llvm::TypeUnitMetaInfo
 
class  llvm::DWARF5AccelTable
 
struct  llvm::DWARF5AccelTable::UnitIndexAndEncoding
 
class  llvm::AppleAccelTableOffsetData
 Accelerator table data implementation for simple Apple accelerator tables with just a DIE reference. More...
 
class  llvm::AppleAccelTableTypeData
 Accelerator table data implementation for Apple type accelerator tables. More...
 
class  llvm::AppleAccelTableStaticOffsetData
 Accelerator table data implementation for simple Apple accelerator tables with a DIE offset but no actual DIE pointer. More...
 
class  llvm::AppleAccelTableStaticTypeData
 Accelerator table data implementation for type accelerator tables with a DIE offset but no actual DIE pointer. More...
 

Namespaces

namespace  llvm
 This is an optimization pass for GlobalISel generic memory operations.
 

Typedefs

using llvm::TUVectorTy = SmallVector< TypeUnitMetaInfo, 1 >
 

Functions

void llvm::emitAppleAccelTableImpl (AsmPrinter *Asm, AccelTableBase &Contents, StringRef Prefix, const MCSymbol *SecBegin, ArrayRef< AppleAccelTableData::Atom > Atoms)
 
template<typename DataT >
void llvm::emitAppleAccelTable (AsmPrinter *Asm, AccelTable< DataT > &Contents, StringRef Prefix, const MCSymbol *SecBegin)
 Emit an Apple Accelerator Table consisting of entries in the specified AccelTable.
 
void llvm::emitDWARF5AccelTable (AsmPrinter *Asm, DWARF5AccelTable &Contents, const DwarfDebug &DD, ArrayRef< std::unique_ptr< DwarfCompileUnit > > CUs)
 
void llvm::emitDWARF5AccelTable (AsmPrinter *Asm, DWARF5AccelTable &Contents, ArrayRef< std::variant< MCSymbol *, uint64_t > > CUs, llvm::function_ref< std::optional< DWARF5AccelTable::UnitIndexAndEncoding >(const DWARF5AccelTableData &)> getIndexForEntry)
 Emit a DWARFv5 Accelerator Table consisting of entries in the specified AccelTable.
 

Detailed Description

This file contains support for writing accelerator tables.

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.

Definition in file AccelTable.h.