LCOV - code coverage report
Current view: top level - include/llvm/CodeGen - AccelTable.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 24 29 82.8 %
Date: 2018-07-13 00:08:38 Functions: 12 22 54.5 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //==- include/llvm/CodeGen/AccelTable.h - 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 accelerator tables.
      11             : //
      12             : //===----------------------------------------------------------------------===//
      13             : 
      14             : #ifndef LLVM_CODEGEN_DWARFACCELTABLE_H
      15             : #define LLVM_CODEGEN_DWARFACCELTABLE_H
      16             : 
      17             : #include "llvm/ADT/ArrayRef.h"
      18             : #include "llvm/ADT/SmallVector.h"
      19             : #include "llvm/ADT/StringMap.h"
      20             : #include "llvm/ADT/StringRef.h"
      21             : #include "llvm/BinaryFormat/Dwarf.h"
      22             : #include "llvm/CodeGen/DIE.h"
      23             : #include "llvm/CodeGen/DwarfStringPoolEntry.h"
      24             : #include "llvm/MC/MCSymbol.h"
      25             : #include "llvm/Support/Allocator.h"
      26             : #include "llvm/Support/DJB.h"
      27             : #include "llvm/Support/Debug.h"
      28             : #include "llvm/Support/Format.h"
      29             : #include "llvm/Support/raw_ostream.h"
      30             : #include <cstddef>
      31             : #include <cstdint>
      32             : #include <vector>
      33             : 
      34             : /// The DWARF and Apple accelerator tables are an indirect hash table optimized
      35             : /// for null lookup rather than access to known data. The Apple accelerator
      36             : /// tables are a precursor of the newer DWARF v5 accelerator tables. Both
      37             : /// formats share common design ideas.
      38             : ///
      39             : /// The Apple accelerator table are output into an on-disk format that looks
      40             : /// like this:
      41             : ///
      42             : /// .------------------.
      43             : /// |  HEADER          |
      44             : /// |------------------|
      45             : /// |  BUCKETS         |
      46             : /// |------------------|
      47             : /// |  HASHES          |
      48             : /// |------------------|
      49             : /// |  OFFSETS         |
      50             : /// |------------------|
      51             : /// |  DATA            |
      52             : /// `------------------'
      53             : ///
      54             : /// The header contains a magic number, version, type of hash function,
      55             : /// the number of buckets, total number of hashes, and room for a special struct
      56             : /// of data and the length of that struct.
      57             : ///
      58             : /// The buckets contain an index (e.g. 6) into the hashes array. The hashes
      59             : /// section contains all of the 32-bit hash values in contiguous memory, and the
      60             : /// offsets contain the offset into the data area for the particular hash.
      61             : ///
      62             : /// For a lookup example, we could hash a function name and take it modulo the
      63             : /// number of buckets giving us our bucket. From there we take the bucket value
      64             : /// as an index into the hashes table and look at each successive hash as long
      65             : /// as the hash value is still the same modulo result (bucket value) as earlier.
      66             : /// If we have a match we look at that same entry in the offsets table and grab
      67             : /// the offset in the data for our final match.
      68             : ///
      69             : /// The DWARF v5 accelerator table consists of zero or more name indices that
      70             : /// are output into an on-disk format that looks like this:
      71             : ///
      72             : /// .------------------.
      73             : /// |  HEADER          |
      74             : /// |------------------|
      75             : /// |  CU LIST         |
      76             : /// |------------------|
      77             : /// |  LOCAL TU LIST   |
      78             : /// |------------------|
      79             : /// |  FOREIGN TU LIST |
      80             : /// |------------------|
      81             : /// |  HASH TABLE      |
      82             : /// |------------------|
      83             : /// |  NAME TABLE      |
      84             : /// |------------------|
      85             : /// |  ABBREV TABLE    |
      86             : /// |------------------|
      87             : /// |  ENTRY POOL      |
      88             : /// `------------------'
      89             : ///
      90             : /// For the full documentation please refer to the DWARF 5 standard.
      91             : ///
      92             : ///
      93             : /// This file defines the class template AccelTable, which is represents an
      94             : /// abstract view of an Accelerator table, without any notion of an on-disk
      95             : /// layout. This class is parameterized by an entry type, which should derive
      96             : /// from AccelTableData. This is the type of individual entries in the table,
      97             : /// and it should store the data necessary to emit them. AppleAccelTableData is
      98             : /// the base class for Apple Accelerator Table entries, which have a uniform
      99             : /// structure based on a sequence of Atoms. There are different sub-classes
     100             : /// derived from AppleAccelTable, which differ in the set of Atoms and how they
     101             : /// obtain their values.
     102             : ///
     103             : /// An Apple Accelerator Table can be serialized by calling emitAppleAccelTable
     104             : /// function.
     105             : ///
     106             : /// TODO: Add DWARF v5 emission code.
     107             : 
     108             : namespace llvm {
     109             : 
     110             : class AsmPrinter;
     111             : class DwarfCompileUnit;
     112             : class DwarfDebug;
     113             : 
     114             : /// Interface which the different types of accelerator table data have to
     115             : /// conform. It serves as a base class for different values of the template
     116             : /// argument of the AccelTable class template.
     117             : class AccelTableData {
     118             : public:
     119             :   virtual ~AccelTableData() = default;
     120             : 
     121             :   bool operator<(const AccelTableData &Other) const {
     122         364 :     return order() < Other.order();
     123             :   }
     124             : 
     125             :   // Subclasses should implement:
     126             :   // static uint32_t hash(StringRef Name);
     127             : 
     128             : #ifndef NDEBUG
     129             :   virtual void print(raw_ostream &OS) const = 0;
     130             : #endif
     131             : protected:
     132             :   virtual uint64_t order() const = 0;
     133             : };
     134             : 
     135             : /// A base class holding non-template-dependant functionality of the AccelTable
     136             : /// class. Clients should not use this class directly but rather instantiate
     137             : /// AccelTable with a type derived from AccelTableData.
     138      217674 : class AccelTableBase {
     139             : public:
     140             :   using HashFn = uint32_t(StringRef);
     141             : 
     142             :   /// Represents a group of entries with identical name (and hence, hash value).
     143             :   struct HashData {
     144             :     DwarfStringPoolEntryRef Name;
     145             :     uint32_t HashValue;
     146             :     std::vector<AccelTableData *> Values;
     147             :     MCSymbol *Sym;
     148             : 
     149             :     HashData(DwarfStringPoolEntryRef Name, HashFn *Hash)
     150        4010 :         : Name(Name), HashValue(Hash(Name.getString())) {}
     151             : 
     152             : #ifndef NDEBUG
     153             :     void print(raw_ostream &OS) const;
     154             :     void dump() const { print(dbgs()); }
     155             : #endif
     156             :   };
     157             :   using HashList = std::vector<HashData *>;
     158             :   using BucketList = std::vector<HashList>;
     159             : 
     160             : protected:
     161             :   /// Allocator for HashData and Values.
     162             :   BumpPtrAllocator Allocator;
     163             : 
     164             :   using StringEntries = StringMap<HashData, BumpPtrAllocator &>;
     165             :   StringEntries Entries;
     166             : 
     167             :   HashFn *Hash;
     168             :   uint32_t BucketCount;
     169             :   uint32_t UniqueHashCount;
     170             : 
     171             :   HashList Hashes;
     172             :   BucketList Buckets;
     173             : 
     174             :   void computeBucketCount();
     175             : 
     176      218714 :   AccelTableBase(HashFn *Hash) : Entries(Allocator), Hash(Hash) {}
     177             : 
     178             : public:
     179             :   void finalize(AsmPrinter *Asm, StringRef Prefix);
     180             :   ArrayRef<HashList> getBuckets() const { return Buckets; }
     181             :   uint32_t getBucketCount() const { return BucketCount; }
     182             :   uint32_t getUniqueHashCount() const { return UniqueHashCount; }
     183          25 :   uint32_t getUniqueNameCount() const { return Entries.size(); }
     184             : 
     185             : #ifndef NDEBUG
     186             :   void print(raw_ostream &OS) const;
     187             :   void dump() const { print(dbgs()); }
     188             : #endif
     189             : 
     190             :   AccelTableBase(const AccelTableBase &) = delete;
     191             :   void operator=(const AccelTableBase &) = delete;
     192             : };
     193             : 
     194             : /// This class holds an abstract representation of an Accelerator Table,
     195             : /// consisting of a sequence of buckets, each bucket containint a sequence of
     196             : /// HashData entries. The class is parameterized by the type of entries it
     197             : /// holds. The type template parameter also defines the hash function to use for
     198             : /// hashing names.
     199       21788 : template <typename DataT> class AccelTable : public AccelTableBase {
     200             : public:
     201             :   AccelTable() : AccelTableBase(DataT::hash) {}
     202             : 
     203             :   template <typename... Types>
     204             :   void addName(DwarfStringPoolEntryRef Name, Types &&... Args);
     205             : };
     206             : 
     207             : template <typename AccelTableDataT>
     208             : template <typename... Types>
     209        2268 : void AccelTable<AccelTableDataT>::addName(DwarfStringPoolEntryRef Name,
     210             :                                           Types &&... Args) {
     211             :   assert(Buckets.empty() && "Already finalized!");
     212             :   // If the string is in the list already then add this die to the list
     213             :   // otherwise add a new one.
     214        4536 :   auto Iter = Entries.try_emplace(Name.getString(), Name, Hash).first;
     215             :   assert(Iter->second.Name == Name);
     216        7078 :   Iter->second.Values.push_back(
     217        2542 :       new (Allocator) AccelTableDataT(std::forward<Types>(Args)...));
     218        2268 : }
     219             : 
     220             : /// A base class for different implementations of Data classes for Apple
     221             : /// Accelerator Tables. The columns in the table are defined by the static Atoms
     222             : /// variable defined on the subclasses.
     223             : class AppleAccelTableData : public AccelTableData {
     224             : public:
     225             :   /// An Atom defines the form of the data in an Apple accelerator table.
     226             :   /// Conceptually it is a column in the accelerator consisting of a type and a
     227             :   /// specification of the form of its data.
     228             :   struct Atom {
     229             :     /// Atom Type.
     230             :     const uint16_t Type;
     231             :     /// DWARF Form.
     232             :     const uint16_t Form;
     233             : 
     234             :     constexpr Atom(uint16_t Type, uint16_t Form) : Type(Type), Form(Form) {}
     235             : 
     236             : #ifndef NDEBUG
     237             :     void print(raw_ostream &OS) const;
     238             :     void dump() const { print(dbgs()); }
     239             : #endif
     240             :   };
     241             :   // Subclasses should define:
     242             :   // static constexpr Atom Atoms[];
     243             : 
     244             :   virtual void emit(AsmPrinter *Asm) const = 0;
     245             : 
     246        3210 :   static uint32_t hash(StringRef Buffer) { return djbHash(Buffer); }
     247             : };
     248             : 
     249             : /// The Data class implementation for DWARF v5 accelerator table. Unlike the
     250             : /// Apple Data classes, this class is just a DIE wrapper, and does not know to
     251             : /// serialize itself. The complete serialization logic is in the
     252             : /// emitDWARF5AccelTable function.
     253           0 : class DWARF5AccelTableData : public AccelTableData {
     254             : public:
     255         400 :   static uint32_t hash(StringRef Name) { return caseFoldingDjbHash(Name); }
     256             : 
     257         423 :   DWARF5AccelTableData(const DIE &Die) : Die(Die) {}
     258             : 
     259             : #ifndef NDEBUG
     260             :   void print(raw_ostream &OS) const override;
     261             : #endif
     262             : 
     263             :   const DIE &getDie() const { return Die; }
     264             : 
     265             : protected:
     266             :   const DIE &Die;
     267             : 
     268          92 :   uint64_t order() const override { return Die.getOffset(); }
     269             : };
     270             : 
     271             : void emitAppleAccelTableImpl(AsmPrinter *Asm, AccelTableBase &Contents,
     272             :                              StringRef Prefix, const MCSymbol *SecBegin,
     273             :                              ArrayRef<AppleAccelTableData::Atom> Atoms);
     274             : 
     275             : /// Emit an Apple Accelerator Table consisting of entries in the specified
     276             : /// AccelTable. The DataT template parameter should be derived from
     277             : /// AppleAccelTableData.
     278             : template <typename DataT>
     279             : void emitAppleAccelTable(AsmPrinter *Asm, AccelTable<DataT> &Contents,
     280             :                          StringRef Prefix, const MCSymbol *SecBegin) {
     281             :   static_assert(std::is_convertible<DataT *, AppleAccelTableData *>::value, "");
     282        1188 :   emitAppleAccelTableImpl(Asm, Contents, Prefix, SecBegin, DataT::Atoms);
     283             : }
     284             : 
     285             : void emitDWARF5AccelTable(AsmPrinter *Asm,
     286             :                           AccelTable<DWARF5AccelTableData> &Contents,
     287             :                           const DwarfDebug &DD,
     288             :                           ArrayRef<std::unique_ptr<DwarfCompileUnit>> CUs);
     289             : 
     290             : /// Accelerator table data implementation for simple Apple accelerator tables
     291             : /// with just a DIE reference.
     292           0 : class AppleAccelTableOffsetData : public AppleAccelTableData {
     293             : public:
     294        1136 :   AppleAccelTableOffsetData(const DIE *D) : Die(D) {}
     295             : 
     296             :   void emit(AsmPrinter *Asm) const override;
     297             : 
     298             : #ifndef _MSC_VER
     299             :   // The line below is rejected by older versions (TBD) of MSVC.
     300             :   static constexpr Atom Atoms[] = {
     301             :       Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
     302             : #else
     303             :   // FIXME: Erase this path once the minimum MSCV version has been bumped.
     304             :   static const SmallVector<Atom, 4> Atoms;
     305             : #endif
     306             : 
     307             : #ifndef NDEBUG
     308             :   void print(raw_ostream &OS) const override;
     309             : #endif
     310             : protected:
     311         198 :   uint64_t order() const override { return Die->getOffset(); }
     312             : 
     313             :   const DIE *Die;
     314             : };
     315             : 
     316             : /// Accelerator table data implementation for Apple type accelerator tables.
     317           0 : class AppleAccelTableTypeData : public AppleAccelTableOffsetData {
     318             : public:
     319         504 :   AppleAccelTableTypeData(const DIE *D) : AppleAccelTableOffsetData(D) {}
     320             : 
     321             :   void emit(AsmPrinter *Asm) const override;
     322             : 
     323             : #ifndef _MSC_VER
     324             :   // The line below is rejected by older versions (TBD) of MSVC.
     325             :   static constexpr Atom Atoms[] = {
     326             :       Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4),
     327             :       Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2),
     328             :       Atom(dwarf::DW_ATOM_type_flags, dwarf::DW_FORM_data1)};
     329             : #else
     330             :   // FIXME: Erase this path once the minimum MSCV version has been bumped.
     331             :   static const SmallVector<Atom, 4> Atoms;
     332             : #endif
     333             : 
     334             : #ifndef NDEBUG
     335             :   void print(raw_ostream &OS) const override;
     336             : #endif
     337             : };
     338             : 
     339             : /// Accelerator table data implementation for simple Apple accelerator tables
     340             : /// with a DIE offset but no actual DIE pointer.
     341           0 : class AppleAccelTableStaticOffsetData : public AppleAccelTableData {
     342             : public:
     343         709 :   AppleAccelTableStaticOffsetData(uint32_t Offset) : Offset(Offset) {}
     344             : 
     345             :   void emit(AsmPrinter *Asm) const override;
     346             : 
     347             : #ifndef _MSC_VER
     348             :   // The line below is rejected by older versions (TBD) of MSVC.
     349             :   static constexpr Atom Atoms[] = {
     350             :       Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
     351             : #else
     352             :   // FIXME: Erase this path once the minimum MSCV version has been bumped.
     353             :   static const SmallVector<Atom, 4> Atoms;
     354             : #endif
     355             : 
     356             : #ifndef NDEBUG
     357             :   void print(raw_ostream &OS) const override;
     358             : #endif
     359             : protected:
     360         140 :   uint64_t order() const override { return Offset; }
     361             : 
     362             :   uint32_t Offset;
     363             : };
     364             : 
     365             : /// Accelerator table data implementation for type accelerator tables with
     366             : /// a DIE offset but no actual DIE pointer.
     367           0 : class AppleAccelTableStaticTypeData : public AppleAccelTableStaticOffsetData {
     368             : public:
     369             :   AppleAccelTableStaticTypeData(uint32_t Offset, uint16_t Tag,
     370             :                                 bool ObjCClassIsImplementation,
     371             :                                 uint32_t QualifiedNameHash)
     372         274 :       : AppleAccelTableStaticOffsetData(Offset),
     373             :         QualifiedNameHash(QualifiedNameHash), Tag(Tag),
     374         274 :         ObjCClassIsImplementation(ObjCClassIsImplementation) {}
     375             : 
     376             :   void emit(AsmPrinter *Asm) const override;
     377             : 
     378             : #ifndef _MSC_VER
     379             :   // The line below is rejected by older versions (TBD) of MSVC.
     380             :   static constexpr Atom Atoms[] = {
     381             :       Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4),
     382             :       Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2),
     383             :       Atom(5, dwarf::DW_FORM_data1), Atom(6, dwarf::DW_FORM_data4)};
     384             : #else
     385             :   // FIXME: Erase this path once the minimum MSCV version has been bumped.
     386             :   static const SmallVector<Atom, 4> Atoms;
     387             : #endif
     388             : 
     389             : #ifndef NDEBUG
     390             :   void print(raw_ostream &OS) const override;
     391             : #endif
     392             : protected:
     393         298 :   uint64_t order() const override { return Offset; }
     394             : 
     395             :   uint32_t QualifiedNameHash;
     396             :   uint16_t Tag;
     397             :   bool ObjCClassIsImplementation;
     398             : };
     399             : 
     400             : } // end namespace llvm
     401             : 
     402             : #endif // LLVM_CODEGEN_DWARFACCELTABLE_H

Generated by: LCOV version 1.13