LCOV - code coverage report
Current view: top level - include/llvm/CodeGen - AccelTable.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 42 54 77.8 %
Date: 2018-10-20 13:21:21 Functions: 14 24 58.3 %
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           0 :   virtual ~AccelTableData() = default;
     120             : 
     121             :   bool operator<(const AccelTableData &Other) const {
     122           0 :     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             : 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        4016 :         : 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      270890 :   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           0 :   uint32_t getBucketCount() const { return BucketCount; }
     182           0 :   uint32_t getUniqueHashCount() const { return UniqueHashCount; }
     183          50 :   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       26844 : 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        2258 : 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        4516 :   auto Iter = Entries.try_emplace(Name.getString(), Name, Hash).first;
     215             :   assert(Iter->second.Name == Name);
     216        7063 :   Iter->second.Values.push_back(
     217        2258 :       new (Allocator) AccelTableDataT(std::forward<Types>(Args)...));
     218        2258 : }
     219         503 : 
     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        1006 : public:
     225             :   /// An Atom defines the form of the data in an Apple accelerator table.
     226        1509 :   /// Conceptually it is a column in the accelerator consisting of a type and a
     227         503 :   /// specification of the form of its data.
     228         503 :   struct Atom {
     229         721 :     /// Atom Type.
     230             :     const uint16_t Type;
     231             :     /// DWARF Form.
     232             :     const uint16_t Form;
     233             : 
     234        1442 :     constexpr Atom(uint16_t Type, uint16_t Form) : Type(Type), Form(Form) {}
     235             : 
     236        2452 : #ifndef NDEBUG
     237         721 :     void print(raw_ostream &OS) const;
     238         721 :     void dump() const { print(dbgs()); }
     239        1034 : #endif
     240             :   };
     241             :   // Subclasses should define:
     242             :   // static constexpr Atom Atoms[];
     243             : 
     244        2068 :   virtual void emit(AsmPrinter *Asm) const = 0;
     245             : 
     246        3102 :   static uint32_t hash(StringRef Buffer) { return djbHash(Buffer); }
     247        1034 : };
     248        1034 : 
     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             : class DWARF5AccelTableData : public AccelTableData {
     254             : public:
     255             :   static uint32_t hash(StringRef Name) { return caseFoldingDjbHash(Name); }
     256             : 
     257             :   DWARF5AccelTableData(const DIE &Die) : Die(Die) {}
     258             : 
     259             : #ifndef NDEBUG
     260             :   void print(raw_ostream &OS) const override;
     261             : #endif
     262             : 
     263           0 :   const DIE &getDie() const { return Die; }
     264         432 :   uint64_t getDieOffset() const { return Die.getOffset(); }
     265         432 :   unsigned getDieTag() const { return Die.getTag(); }
     266             : 
     267             : protected:
     268             :   const DIE &Die;
     269             : 
     270           0 :   uint64_t order() const override { return Die.getOffset(); }
     271             : };
     272             : 
     273             : class DWARF5AccelTableStaticData : public AccelTableData {
     274             : public:
     275             :   static uint32_t hash(StringRef Name) { return caseFoldingDjbHash(Name); }
     276        1566 : 
     277             :   DWARF5AccelTableStaticData(uint64_t DieOffset, unsigned DieTag,
     278             :                              unsigned CUIndex)
     279             :       : DieOffset(DieOffset), DieTag(DieTag), CUIndex(CUIndex) {}
     280             : 
     281             : #ifndef NDEBUG
     282             :   void print(raw_ostream &OS) const override;
     283             : #endif
     284             : 
     285         424 :   uint64_t getDieOffset() const { return DieOffset; }
     286           0 :   unsigned getDieTag() const { return DieTag; }
     287         432 :   unsigned getCUIndex() const { return CUIndex; }
     288             : 
     289             : protected:
     290             :   uint64_t DieOffset;
     291             :   unsigned DieTag;
     292             :   unsigned CUIndex;
     293             : 
     294           0 :   uint64_t order() const override { return DieOffset; }
     295             : };
     296             : 
     297             : void emitAppleAccelTableImpl(AsmPrinter *Asm, AccelTableBase &Contents,
     298             :                              StringRef Prefix, const MCSymbol *SecBegin,
     299             :                              ArrayRef<AppleAccelTableData::Atom> Atoms);
     300          30 : 
     301             : /// Emit an Apple Accelerator Table consisting of entries in the specified
     302             : /// AccelTable. The DataT template parameter should be derived from
     303             : /// AppleAccelTableData.
     304             : template <typename DataT>
     305          18 : void emitAppleAccelTable(AsmPrinter *Asm, AccelTable<DataT> &Contents,
     306             :                          StringRef Prefix, const MCSymbol *SecBegin) {
     307             :   static_assert(std::is_convertible<DataT *, AppleAccelTableData *>::value, "");
     308         348 :   emitAppleAccelTableImpl(Asm, Contents, Prefix, SecBegin, DataT::Atoms);
     309          24 : }
     310             : 
     311             : void emitDWARF5AccelTable(AsmPrinter *Asm,
     312             :                           AccelTable<DWARF5AccelTableData> &Contents,
     313             :                           const DwarfDebug &DD,
     314             :                           ArrayRef<std::unique_ptr<DwarfCompileUnit>> CUs);
     315             : 
     316             : void emitDWARF5AccelTable(
     317             :     AsmPrinter *Asm, AccelTable<DWARF5AccelTableStaticData> &Contents,
     318             :     ArrayRef<MCSymbol *> CUs,
     319             :     llvm::function_ref<unsigned(const DWARF5AccelTableStaticData &)>
     320             :         getCUIndexForEntry);
     321             : 
     322             : /// Accelerator table data implementation for simple Apple accelerator tables
     323             : /// with just a DIE reference.
     324          16 : class AppleAccelTableOffsetData : public AppleAccelTableData {
     325             : public:
     326             :   AppleAccelTableOffsetData(const DIE &D) : Die(D) {}
     327             : 
     328             :   void emit(AsmPrinter *Asm) const override;
     329             : 
     330             : #ifndef _MSC_VER
     331             :   // The line below is rejected by older versions (TBD) of MSVC.
     332             :   static constexpr Atom Atoms[] = {
     333             :       Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
     334             : #else
     335             :   // FIXME: Erase this path once the minimum MSCV version has been bumped.
     336             :   static const SmallVector<Atom, 4> Atoms;
     337             : #endif
     338           0 : 
     339             : #ifndef NDEBUG
     340             :   void print(raw_ostream &OS) const override;
     341             : #endif
     342             : protected:
     343         136 :   uint64_t order() const override { return Die.getOffset(); }
     344             : 
     345             :   const DIE &Die;
     346             : };
     347             : 
     348             : /// Accelerator table data implementation for Apple type accelerator tables.
     349             : class AppleAccelTableTypeData : public AppleAccelTableOffsetData {
     350             : public:
     351             :   AppleAccelTableTypeData(const DIE &D) : AppleAccelTableOffsetData(D) {}
     352             : 
     353             :   void emit(AsmPrinter *Asm) const override;
     354             : 
     355             : #ifndef _MSC_VER
     356         573 :   // The line below is rejected by older versions (TBD) of MSVC.
     357             :   static constexpr Atom Atoms[] = {
     358             :       Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4),
     359             :       Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2),
     360             :       Atom(dwarf::DW_ATOM_type_flags, dwarf::DW_FORM_data1)};
     361             : #else
     362             :   // FIXME: Erase this path once the minimum MSCV version has been bumped.
     363             :   static const SmallVector<Atom, 4> Atoms;
     364             : #endif
     365             : 
     366             : #ifndef NDEBUG
     367             :   void print(raw_ostream &OS) const override;
     368             : #endif
     369             : };
     370             : 
     371             : /// Accelerator table data implementation for simple Apple accelerator tables
     372             : /// with a DIE offset but no actual DIE pointer.
     373           0 : class AppleAccelTableStaticOffsetData : public AppleAccelTableData {
     374             : public:
     375             :   AppleAccelTableStaticOffsetData(uint32_t Offset) : Offset(Offset) {}
     376             : 
     377             :   void emit(AsmPrinter *Asm) const override;
     378             : 
     379             : #ifndef _MSC_VER
     380             :   // The line below is rejected by older versions (TBD) of MSVC.
     381         479 :   static constexpr Atom Atoms[] = {
     382             :       Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
     383             : #else
     384             :   // FIXME: Erase this path once the minimum MSCV version has been bumped.
     385             :   static const SmallVector<Atom, 4> Atoms;
     386             : #endif
     387             : 
     388             : #ifndef NDEBUG
     389             :   void print(raw_ostream &OS) const override;
     390             : #endif
     391             : protected:
     392         148 :   uint64_t order() const override { return Offset; }
     393             : 
     394             :   uint32_t Offset;
     395             : };
     396             : 
     397             : /// Accelerator table data implementation for type accelerator tables with
     398             : /// a DIE offset but no actual DIE pointer.
     399             : class AppleAccelTableStaticTypeData : public AppleAccelTableStaticOffsetData {
     400             : public:
     401             :   AppleAccelTableStaticTypeData(uint32_t Offset, uint16_t Tag,
     402             :                                 bool ObjCClassIsImplementation,
     403             :                                 uint32_t QualifiedNameHash)
     404             :       : AppleAccelTableStaticOffsetData(Offset),
     405         461 :         QualifiedNameHash(QualifiedNameHash), Tag(Tag),
     406             :         ObjCClassIsImplementation(ObjCClassIsImplementation) {}
     407             : 
     408             :   void emit(AsmPrinter *Asm) const override;
     409             : 
     410             : #ifndef _MSC_VER
     411             :   // The line below is rejected by older versions (TBD) of MSVC.
     412             :   static constexpr Atom Atoms[] = {
     413             :       Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4),
     414             :       Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2),
     415             :       Atom(5, dwarf::DW_FORM_data1), Atom(6, dwarf::DW_FORM_data4)};
     416             : #else
     417             :   // FIXME: Erase this path once the minimum MSCV version has been bumped.
     418             :   static const SmallVector<Atom, 4> Atoms;
     419             : #endif
     420             : 
     421             : #ifndef NDEBUG
     422           0 :   void print(raw_ostream &OS) const override;
     423             : #endif
     424             : protected:
     425         318 :   uint64_t order() const override { return Offset; }
     426             : 
     427             :   uint32_t QualifiedNameHash;
     428             :   uint16_t Tag;
     429             :   bool ObjCClassIsImplementation;
     430             : };
     431             : 
     432             : } // end namespace llvm
     433             : 
     434         289 : #endif // LLVM_CODEGEN_DWARFACCELTABLE_H

Generated by: LCOV version 1.13