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.