lib/CodeGen/AsmPrinter/DwarfAccelTable.h

   1 //==-- llvm/CodeGen/DwarfAccelTable.h - Dwarf Accelerator Tables -*- C++ -*-==//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file contains support for writing dwarf accelerator tables.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef CODEGEN_ASMPRINTER_DWARFACCELTABLE_H__
  15 #define CODEGEN_ASMPRINTER_DWARFACCELTABLE_H__
  16
  17 #include "DIE.h"
  18 #include "llvm/ADT/ArrayRef.h"
  19 #include "llvm/ADT/StringMap.h"
  20 #include "llvm/MC/MCSymbol.h"
  21 #include "llvm/Support/DataTypes.h"
  22 #include "llvm/Support/Debug.h"
  23 #include "llvm/Support/Dwarf.h"
  24 #include "llvm/Support/ErrorHandling.h"
  25 #include "llvm/Support/Format.h"
  26 #include "llvm/Support/FormattedStream.h"
  27 #include <map>
  28 #include <vector>
  29
  30 // The dwarf accelerator tables are an indirect hash table optimized
  31 // for null lookup rather than access to known data. They are output into
  32 // an on-disk format that looks like this:
  33 //
  34 // .-------------.
  35 // |  HEADER     |
  36 // |-------------|
  37 // |  BUCKETS    |
  38 // |-------------|
  39 // |  HASHES     |
  40 // |-------------|
  41 // |  OFFSETS    |
  42 // |-------------|
  43 // |  DATA       |
  44 // `-------------'
  45 //
  46 // where the header contains a magic number, version, type of hash function,
  47 // the number of buckets, total number of hashes, and room for a special
  48 // struct of data and the length of that struct.
  49 //
  50 // The buckets contain an index (e.g. 6) into the hashes array. The hashes
  51 // section contains all of the 32-bit hash values in contiguous memory, and
  52 // the offsets contain the offset into the data area for the particular
  53 // hash.
  54 //
  55 // For a lookup example, we could hash a function name and take it modulo the
  56 // number of buckets giving us our bucket. From there we take the bucket value
  57 // as an index into the hashes table and look at each successive hash as long
  58 // as the hash value is still the same modulo result (bucket value) as earlier.
  59 // If we have a match we look at that same entry in the offsets table and
  60 // grab the offset in the data for our final match.
  61
  62 namespace llvm {
  63
  64 class AsmPrinter;
  65 class DIE;
  66 class DwarfUnits;
  67
  68 class DwarfAccelTable {
  69
  70   enum HashFunctionType {
  71     eHashFunctionDJB = 0u
  72   };
  73
  74   static uint32_t HashDJB(StringRef Str) {
  75     uint32_t h = 5381;
  76     for (unsigned i = 0, e = Str.size(); i != e; ++i)
  77       h = ((h << 5) + h) + Str[i];
  78     return h;
  79   }
  80
  81   // Helper function to compute the number of buckets needed based on
  82   // the number of unique hashes.
  83   void ComputeBucketCount(void);
  84
  85   struct TableHeader {
  86     uint32_t magic;           // 'HASH' magic value to allow endian detection
  87     uint16_t version;         // Version number.
  88     uint16_t hash_function;   // The hash function enumeration that was used.
  89     uint32_t bucket_count;    // The number of buckets in this hash table.
  90     uint32_t hashes_count;    // The total number of unique hash values
  91                               // and hash data offsets in this table.
  92     uint32_t header_data_len; // The bytes to skip to get to the hash
  93                               // indexes (buckets) for correct alignment.
  94     // Also written to disk is the implementation specific header data.
  95
  96     static const uint32_t MagicHash = 0x48415348;
  97
  98     TableHeader(uint32_t data_len)
  99         : magic(MagicHash), version(1), hash_function(eHashFunctionDJB),
 100           bucket_count(0), hashes_count(0), header_data_len(data_len) {}
 101
 102 #ifndef NDEBUG
 103     void print(raw_ostream &O) {
 104       O << "Magic: " << format("0x%x", magic) << "\n"
 105         << "Version: " << version << "\n"
 106         << "Hash Function: " << hash_function << "\n"
 107         << "Bucket Count: " << bucket_count << "\n"
 108         << "Header Data Length: " << header_data_len << "\n";
 109     }
 110     void dump() { print(dbgs()); }
 111 #endif
 112   };
 113
 114 public:
 115   // The HeaderData describes the form of each set of data. In general this
 116   // is as a list of atoms (atom_count) where each atom contains a type
 117   // (AtomType type) of data, and an encoding form (form). In the case of
 118   // data that is referenced via DW_FORM_ref_* the die_offset_base is
 119   // used to describe the offset for all forms in the list of atoms.
 120   // This also serves as a public interface of sorts.
 121   // When written to disk this will have the form:
 122   //
 123   // uint32_t die_offset_base
 124   // uint32_t atom_count
 125   // atom_count Atoms
 126   enum AtomType {
 127     eAtomTypeNULL = 0u,
 128     eAtomTypeDIEOffset = 1u, // DIE offset, check form for encoding
 129     eAtomTypeCUOffset = 2u,  // DIE offset of the compiler unit header that
 130                              // contains the item in question
 131     eAtomTypeTag = 3u,       // DW_TAG_xxx value, should be encoded as
 132                              // DW_FORM_data1 (if no tags exceed 255) or
 133                              // DW_FORM_data2.
 134     eAtomTypeNameFlags = 4u, // Flags from enum NameFlags
 135     eAtomTypeTypeFlags = 5u  // Flags from enum TypeFlags
 136   };
 137
 138   enum TypeFlags {
 139     eTypeFlagClassMask = 0x0000000fu,
 140
 141     // Always set for C++, only set for ObjC if this is the
 142     // @implementation for a class.
 143     eTypeFlagClassIsImplementation = (1u << 1)
 144   };
 145
 146   // Make these public so that they can be used as a general interface to
 147   // the class.
 148   struct Atom {
 149     AtomType type; // enum AtomType
 150     uint16_t form; // DWARF DW_FORM_ defines
 151
 152     Atom(AtomType type, uint16_t form) : type(type), form(form) {}
 153     static const char *AtomTypeString(enum AtomType);
 154 #ifndef NDEBUG
 155     void print(raw_ostream &O) {
 156       O << "Type: " << AtomTypeString(type) << "\n"
 157         << "Form: " << dwarf::FormEncodingString(form) << "\n";
 158     }
 159     void dump() { print(dbgs()); }
 160 #endif
 161   };
 162
 163 private:
 164   struct TableHeaderData {
 165     uint32_t die_offset_base;
 166     SmallVector<Atom, 1> Atoms;
 167
 168     TableHeaderData(ArrayRef<Atom> AtomList, uint32_t offset = 0)
 169         : die_offset_base(offset), Atoms(AtomList.begin(), AtomList.end()) {}
 170
 171 #ifndef NDEBUG
 172     void print(raw_ostream &O) {
 173       O << "die_offset_base: " << die_offset_base << "\n";
 174       for (size_t i = 0; i < Atoms.size(); i++)
 175         Atoms[i].print(O);
 176     }
 177     void dump() { print(dbgs()); }
 178 #endif
 179   };
 180
 181   // The data itself consists of a str_offset, a count of the DIEs in the
 182   // hash and the offsets to the DIEs themselves.
 183   // On disk each data section is ended with a 0 KeyType as the end of the
 184   // hash chain.
 185   // On output this looks like:
 186   // uint32_t str_offset
 187   // uint32_t hash_data_count
 188   // HashData[hash_data_count]
 189 public:
 190   struct HashDataContents {
 191     DIE *Die;   // Offsets
 192     char Flags; // Specific flags to output
 193
 194     HashDataContents(DIE *D, char Flags) : Die(D), Flags(Flags) {}
 195 #ifndef NDEBUG
 196     void print(raw_ostream &O) const {
 197       O << "  Offset: " << Die->getOffset() << "\n";
 198       O << "  Tag: " << dwarf::TagString(Die->getTag()) << "\n";
 199       O << "  Flags: " << Flags << "\n";
 200     }
 201 #endif
 202   };
 203
 204 private:
 205   struct HashData {
 206     StringRef Str;
 207     uint32_t HashValue;
 208     MCSymbol *Sym;
 209     ArrayRef<HashDataContents *> Data; // offsets
 210     HashData(StringRef S, ArrayRef<HashDataContents *> Data)
 211         : Str(S), Data(Data) {
 212       HashValue = DwarfAccelTable::HashDJB(S);
 213     }
 214 #ifndef NDEBUG
 215     void print(raw_ostream &O) {
 216       O << "Name: " << Str << "\n";
 217       O << "  Hash Value: " << format("0x%x", HashValue) << "\n";
 218       O << "  Symbol: ";
 219       if (Sym)
 220         Sym->print(O);
 221       else
 222         O << "<none>";
 223       O << "\n";
 224       for (size_t i = 0; i < Data.size(); i++) {
 225         O << "  Offset: " << Data[i]->Die->getOffset() << "\n";
 226         O << "  Tag: " << dwarf::TagString(Data[i]->Die->getTag()) << "\n";
 227         O << "  Flags: " << Data[i]->Flags << "\n";
 228       }
 229     }
 230     void dump() { print(dbgs()); }
 231 #endif
 232   };
 233
 234   DwarfAccelTable(const DwarfAccelTable &) LLVM_DELETED_FUNCTION;
 235   void operator=(const DwarfAccelTable &) LLVM_DELETED_FUNCTION;
 236
 237   // Internal Functions
 238   void EmitHeader(AsmPrinter *);
 239   void EmitBuckets(AsmPrinter *);
 240   void EmitHashes(AsmPrinter *);
 241   void EmitOffsets(AsmPrinter *, MCSymbol *);
 242   void EmitData(AsmPrinter *, DwarfUnits *D);
 243
 244   // Allocator for HashData and HashDataContents.
 245   BumpPtrAllocator Allocator;
 246
 247   // Output Variables
 248   TableHeader Header;
 249   TableHeaderData HeaderData;
 250   std::vector<HashData *> Data;
 251
 252   // String Data
 253   typedef std::vector<HashDataContents *> DataArray;
 254   typedef StringMap<DataArray, BumpPtrAllocator &> StringEntries;
 255   StringEntries Entries;
 256
 257   // Buckets/Hashes/Offsets
 258   typedef std::vector<HashData *> HashList;
 259   typedef std::vector<HashList> BucketList;
 260   BucketList Buckets;
 261   HashList Hashes;
 262
 263   // Public Implementation
 264 public:
 265   DwarfAccelTable(ArrayRef<DwarfAccelTable::Atom>);
 266   ~DwarfAccelTable();
 267   void AddName(StringRef, DIE *, char = 0);
 268   void FinalizeTable(AsmPrinter *, StringRef);
 269   void Emit(AsmPrinter *, MCSymbol *, DwarfUnits *);
 270 #ifndef NDEBUG
 271   void print(raw_ostream &O);
 272   void dump() { print(dbgs()); }
 273 #endif
 274 };
 275 }
 276 #endif