LCOV - code coverage report
Current view: top level - include/llvm/CodeGen - AccelTable.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 20 24 83.3 %
Date: 2018-02-20 03:34:22 Functions: 9 17 52.9 %
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             : 
     112             : /// Interface which the different types of accelerator table data have to
     113             : /// conform. It serves as a base class for different values of the template
     114             : /// argument of the AccelTable class template.
     115             : class AccelTableData {
     116             : public:
     117             :   virtual ~AccelTableData() = default;
     118             : 
     119             :   bool operator<(const AccelTableData &Other) const {
     120         277 :     return order() < Other.order();
     121             :   }
     122             : 
     123             :   // Subclasses should implement:
     124             :   // static uint32_t hash(StringRef Name);
     125             : 
     126             : #ifndef NDEBUG
     127             :   virtual void print(raw_ostream &OS) const = 0;
     128             : #endif
     129             : protected:
     130             :   virtual uint64_t order() const = 0;
     131             : };
     132             : 
     133             : /// A base class holding non-template-dependant functionality of the AccelTable
     134             : /// class. Clients should not use this class directly but rather instantiate
     135             : /// AccelTable with a type derived from AccelTableData.
     136      162975 : class AccelTableBase {
     137             : public:
     138             :   using HashFn = uint32_t(StringRef);
     139             : 
     140             :   /// Represents a group of entries with identical name (and hence, hash value).
     141             :   struct HashData {
     142             :     DwarfStringPoolEntryRef Name;
     143             :     uint32_t HashValue;
     144             :     std::vector<AccelTableData *> Values;
     145             :     MCSymbol *Sym;
     146             : 
     147             :     HashData(DwarfStringPoolEntryRef Name, HashFn *Hash)
     148        2968 :         : Name(Name), HashValue(Hash(Name.getString())) {}
     149             : 
     150             : #ifndef NDEBUG
     151             :     void print(raw_ostream &OS) const;
     152             :     void dump() const { print(dbgs()); }
     153             : #endif
     154             :   };
     155             :   using HashList = std::vector<HashData *>;
     156             :   using BucketList = std::vector<HashList>;
     157             : 
     158             : protected:
     159             :   /// Allocator for HashData and Values.
     160             :   BumpPtrAllocator Allocator;
     161             : 
     162             :   using StringEntries = StringMap<HashData, BumpPtrAllocator &>;
     163             :   StringEntries Entries;
     164             : 
     165             :   HashFn *Hash;
     166             :   uint32_t BucketCount;
     167             :   uint32_t UniqueHashCount;
     168             : 
     169             :   HashList Hashes;
     170             :   BucketList Buckets;
     171             : 
     172             :   void computeBucketCount();
     173             : 
     174      163760 :   AccelTableBase(HashFn *Hash) : Entries(Allocator), Hash(Hash) {}
     175             : 
     176             : public:
     177             :   void finalize(AsmPrinter *Asm, StringRef Prefix);
     178             :   ArrayRef<HashList> getBuckets() const { return Buckets; }
     179             :   uint32_t getBucketCount() const { return BucketCount; }
     180             :   uint32_t getUniqueHashCount() const { return UniqueHashCount; }
     181             :   uint32_t getUniqueNameCount() const { return Entries.size(); }
     182             : 
     183             : #ifndef NDEBUG
     184             :   void print(raw_ostream &OS) const;
     185             :   void dump() const { print(dbgs()); }
     186             : #endif
     187             : 
     188             :   AccelTableBase(const AccelTableBase &) = delete;
     189             :   void operator=(const AccelTableBase &) = delete;
     190             : };
     191             : 
     192             : /// This class holds an abstract representation of an Accelerator Table,
     193             : /// consisting of a sequence of buckets, each bucket containint a sequence of
     194             : /// HashData entries. The class is parameterized by the type of entries it
     195             : /// holds. The type template parameter also defines the hash function to use for
     196             : /// hashing names.
     197       20372 : template <typename DataT> class AccelTable : public AccelTableBase {
     198             : public:
     199             :   AccelTable() : AccelTableBase(DataT::hash) {}
     200             : 
     201             :   template <typename... Types>
     202             :   void addName(DwarfStringPoolEntryRef Name, Types &&... Args);
     203             : };
     204             : 
     205             : template <typename AccelTableDataT>
     206             : template <typename... Types>
     207        1700 : void AccelTable<AccelTableDataT>::addName(DwarfStringPoolEntryRef Name,
     208             :                                           Types &&... Args) {
     209             :   assert(Buckets.empty() && "Already finalized!");
     210             :   // If the string is in the list already then add this die to the list
     211             :   // otherwise add a new one.
     212        3400 :   auto Iter = Entries.try_emplace(Name.getString(), Name, Hash).first;
     213             :   assert(Iter->second.Name == Name);
     214        5368 :   Iter->second.Values.push_back(
     215        1968 :       new (Allocator) AccelTableDataT(std::forward<Types>(Args)...));
     216        1700 : }
     217             : 
     218             : /// A base class for different implementations of Data classes for Apple
     219             : /// Accelerator Tables. The columns in the table are defined by the static Atoms
     220             : /// variable defined on the subclasses.
     221             : class AppleAccelTableData : public AccelTableData {
     222             : public:
     223             :   /// An Atom defines the form of the data in an Apple accelerator table.
     224             :   /// Conceptually it is a column in the accelerator consisting of a type and a
     225             :   /// specification of the form of its data.
     226             :   struct Atom {
     227             :     /// Atom Type.
     228             :     const uint16_t Type;
     229             :     /// DWARF Form.
     230             :     const uint16_t Form;
     231             : 
     232             :     constexpr Atom(uint16_t Type, uint16_t Form) : Type(Type), Form(Form) {}
     233             : 
     234             : #ifndef NDEBUG
     235             :     void print(raw_ostream &OS) const;
     236             :     void dump() const { print(dbgs()); }
     237             : #endif
     238             :   };
     239             :   // Subclasses should define:
     240             :   // static constexpr Atom Atoms[];
     241             : 
     242             :   virtual void emit(AsmPrinter *Asm) const = 0;
     243             : 
     244        1484 :   static uint32_t hash(StringRef Buffer) { return djbHash(Buffer); }
     245             : };
     246             : 
     247             : void emitAppleAccelTableImpl(AsmPrinter *Asm, AccelTableBase &Contents,
     248             :                              StringRef Prefix, const MCSymbol *SecBegin,
     249             :                              ArrayRef<AppleAccelTableData::Atom> Atoms);
     250             : 
     251             : /// Emit an Apple Accelerator Table consisting of entries in the specified
     252             : /// AccelTable. The DataT template parameter should be derived from
     253             : /// AppleAccelTableData.
     254             : template <typename DataT>
     255             : void emitAppleAccelTable(AsmPrinter *Asm, AccelTable<DataT> &Contents,
     256             :                          StringRef Prefix, const MCSymbol *SecBegin) {
     257             :   static_assert(std::is_convertible<DataT *, AppleAccelTableData *>::value, "");
     258        1132 :   emitAppleAccelTableImpl(Asm, Contents, Prefix, SecBegin, DataT::Atoms);
     259             : }
     260             : 
     261             : /// Accelerator table data implementation for simple Apple accelerator tables
     262             : /// with just a DIE reference.
     263           0 : class AppleAccelTableOffsetData : public AppleAccelTableData {
     264             : public:
     265        1008 :   AppleAccelTableOffsetData(const DIE *D) : Die(D) {}
     266             : 
     267             :   void emit(AsmPrinter *Asm) const override;
     268             : 
     269             : #ifndef _MSC_VER
     270             :   // The line below is rejected by older versions (TBD) of MSVC.
     271             :   static constexpr Atom Atoms[] = {
     272             :       Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
     273             : #else
     274             :   // FIXME: Erase this path once the minimum MSCV version has been bumped.
     275             :   static const SmallVector<Atom, 4> Atoms;
     276             : #endif
     277             : 
     278             : #ifndef NDEBUG
     279             :   void print(raw_ostream &OS) const override;
     280             : #endif
     281             : protected:
     282         124 :   uint64_t order() const override { return Die->getOffset(); }
     283             : 
     284             :   const DIE *Die;
     285             : };
     286             : 
     287             : /// Accelerator table data implementation for Apple type accelerator tables.
     288           0 : class AppleAccelTableTypeData : public AppleAccelTableOffsetData {
     289             : public:
     290         456 :   AppleAccelTableTypeData(const DIE *D) : AppleAccelTableOffsetData(D) {}
     291             : 
     292             :   void emit(AsmPrinter *Asm) const override;
     293             : 
     294             : #ifndef _MSC_VER
     295             :   // The line below is rejected by older versions (TBD) of MSVC.
     296             :   static constexpr Atom Atoms[] = {
     297             :       Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4),
     298             :       Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2),
     299             :       Atom(dwarf::DW_ATOM_type_flags, dwarf::DW_FORM_data1)};
     300             : #else
     301             :   // FIXME: Erase this path once the minimum MSCV version has been bumped.
     302             :   static const SmallVector<Atom, 4> Atoms;
     303             : #endif
     304             : 
     305             : #ifndef NDEBUG
     306             :   void print(raw_ostream &OS) const override;
     307             : #endif
     308             : };
     309             : 
     310             : /// Accelerator table data implementation for simple Apple accelerator tables
     311             : /// with a DIE offset but no actual DIE pointer.
     312           0 : class AppleAccelTableStaticOffsetData : public AppleAccelTableData {
     313             : public:
     314         692 :   AppleAccelTableStaticOffsetData(uint32_t Offset) : Offset(Offset) {}
     315             : 
     316             :   void emit(AsmPrinter *Asm) const override;
     317             : 
     318             : #ifndef _MSC_VER
     319             :   // The line below is rejected by older versions (TBD) of MSVC.
     320             :   static constexpr Atom Atoms[] = {
     321             :       Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
     322             : #else
     323             :   // FIXME: Erase this path once the minimum MSCV version has been bumped.
     324             :   static const SmallVector<Atom, 4> Atoms;
     325             : #endif
     326             : 
     327             : #ifndef NDEBUG
     328             :   void print(raw_ostream &OS) const override;
     329             : #endif
     330             : protected:
     331         138 :   uint64_t order() const override { return Offset; }
     332             : 
     333             :   uint32_t Offset;
     334             : };
     335             : 
     336             : /// Accelerator table data implementation for type accelerator tables with
     337             : /// a DIE offset but no actual DIE pointer.
     338           0 : class AppleAccelTableStaticTypeData : public AppleAccelTableStaticOffsetData {
     339             : public:
     340             :   AppleAccelTableStaticTypeData(uint32_t Offset, uint16_t Tag,
     341             :                                 bool ObjCClassIsImplementation,
     342             :                                 uint32_t QualifiedNameHash)
     343         268 :       : AppleAccelTableStaticOffsetData(Offset),
     344             :         QualifiedNameHash(QualifiedNameHash), Tag(Tag),
     345         268 :         ObjCClassIsImplementation(ObjCClassIsImplementation) {}
     346             : 
     347             :   void emit(AsmPrinter *Asm) const override;
     348             : 
     349             : #ifndef _MSC_VER
     350             :   // The line below is rejected by older versions (TBD) of MSVC.
     351             :   static constexpr Atom Atoms[] = {
     352             :       Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4),
     353             :       Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2),
     354             :       Atom(5, dwarf::DW_FORM_data1), Atom(6, dwarf::DW_FORM_data4)};
     355             : #else
     356             :   // FIXME: Erase this path once the minimum MSCV version has been bumped.
     357             :   static const SmallVector<Atom, 4> Atoms;
     358             : #endif
     359             : 
     360             : #ifndef NDEBUG
     361             :   void print(raw_ostream &OS) const override;
     362             : #endif
     363             : protected:
     364         292 :   uint64_t order() const override { return Offset; }
     365             : 
     366             :   uint32_t QualifiedNameHash;
     367             :   uint16_t Tag;
     368             :   bool ObjCClassIsImplementation;
     369             : };
     370             : 
     371             : } // end namespace llvm
     372             : 
     373             : #endif // LLVM_CODEGEN_DWARFACCELTABLE_H

Generated by: LCOV version 1.13