//==- 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/STLFunctionalExtras.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/Support/Allocator.h"
#include "llvm/Support/DJB.h"
#include "llvm/Support/Debug.h"
#include <cstdint>
#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 DwarfCompileUnit;
class DwarfDebug;
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;
HashData(DwarfStringPoolEntryRef Name, HashFn *Hash)
: Name(Name), HashValue(Hash(Name.getString())) {}
#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 = StringMap<HashData, BumpPtrAllocator &>;
StringEntries Entries;
HashFn *Hash;
uint32_t BucketCount;
uint32_t UniqueHashCount;
HashList Hashes;
BucketList Buckets;
void computeBucketCount();
AccelTableBase(HashFn *Hash) : Entries(Allocator), 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);
};
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 Iter = Entries.try_emplace(Name.getString(), Name, Hash).first;
assert(Iter->second.Name == Name);
Iter->second.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); }
};
/// 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:
static uint32_t hash(StringRef Name) { return caseFoldingDjbHash(Name); }
DWARF5AccelTableData(const DIE &Die) : Die(Die) {}
#ifndef NDEBUG
void print(raw_ostream &OS) const override;
#endif
const DIE &getDie() const { return Die; }
uint64_t getDieOffset() const { return Die.getOffset(); }
unsigned getDieTag() const { return Die.getTag(); }
protected:
const DIE &Die;
uint64_t order() const override { return Die.getOffset(); }
};
class DWARF5AccelTableStaticData : public AccelTableData {
public:
static uint32_t hash(StringRef Name) { return caseFoldingDjbHash(Name); }
DWARF5AccelTableStaticData(uint64_t DieOffset, unsigned DieTag,
unsigned CUIndex)
: DieOffset(DieOffset), DieTag(DieTag), CUIndex(CUIndex) {}
#ifndef NDEBUG
void print(raw_ostream &OS) const override;
#endif
uint64_t getDieOffset() const { return DieOffset; }
unsigned getDieTag() const { return DieTag; }
unsigned getCUIndex() const { return CUIndex; }
protected:
uint64_t DieOffset;
unsigned DieTag;
unsigned CUIndex;
uint64_t order() const override { return DieOffset; }
};
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,
AccelTable<DWARF5AccelTableData> &Contents,
const DwarfDebug &DD,
ArrayRef<std::unique_ptr<DwarfCompileUnit>> CUs);
void emitDWARF5AccelTable(
AsmPrinter *Asm, AccelTable<DWARF5AccelTableStaticData> &Contents,
ArrayRef<MCSymbol *> CUs,
llvm::function_ref<unsigned(const DWARF5AccelTableStaticData &)>
getCUIndexForEntry);
/// 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