LLVM  7.0.0svn
DWARFAcceleratorTable.h
Go to the documentation of this file.
1 //===- DWARFAcceleratorTable.h ----------------------------------*- 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 #ifndef LLVM_DEBUGINFO_DWARFACCELERATORTABLE_H
11 #define LLVM_DEBUGINFO_DWARFACCELERATORTABLE_H
12 
13 #include "llvm/ADT/DenseSet.h"
14 #include "llvm/ADT/SmallVector.h"
18 #include <cstdint>
19 #include <utility>
20 
21 namespace llvm {
22 
23 class raw_ostream;
24 class ScopedPrinter;
25 
26 /// The accelerator tables are designed to allow efficient random access
27 /// (using a symbol name as a key) into debug info by providing an index of the
28 /// debug info DIEs. This class implements the common functionality of Apple and
29 /// DWARF 5 accelerator tables.
30 /// TODO: Generalize the rest of the AppleAcceleratorTable interface and move it
31 /// to this class.
33 protected:
36 
37 public:
39  DataExtractor StringSection)
40  : AccelSection(AccelSection), StringSection(StringSection) {}
41  virtual ~DWARFAcceleratorTable();
42 
43  virtual llvm::Error extract() = 0;
44  virtual void dump(raw_ostream &OS) const = 0;
45 
47  void operator=(const DWARFAcceleratorTable &) = delete;
48 };
49 
50 /// This implements the Apple accelerator table format, a precursor of the
51 /// DWARF 5 accelerator table format.
53  struct Header {
55  uint16_t Version;
56  uint16_t HashFunction;
57  uint32_t BucketCount;
58  uint32_t HashCount;
59  uint32_t HeaderDataLength;
60 
61  void dump(ScopedPrinter &W) const;
62  };
63 
64  struct HeaderData {
65  using AtomType = uint16_t;
66  using Form = dwarf::Form;
67 
68  uint32_t DIEOffsetBase;
70  };
71 
72  struct Header Hdr;
73  struct HeaderData HdrData;
74  bool IsValid = false;
75 
76  /// Returns true if we should continue scanning for entries or false if we've
77  /// reached the last (sentinel) entry of encountered a parsing error.
78  bool dumpName(ScopedPrinter &W, SmallVectorImpl<DWARFFormValue> &AtomForms,
79  uint32_t *DataOffset) const;
80 
81 public:
82  /// An iterator for the entries associated with one key. Each entry can have
83  /// multiple DWARFFormValues.
84  class ValueIterator : public std::iterator<std::input_iterator_tag,
85  ArrayRef<DWARFFormValue>> {
86  const AppleAcceleratorTable *AccelTable = nullptr;
87  SmallVector<DWARFFormValue, 3> AtomForms; ///< The decoded data entry.
88 
89  unsigned DataOffset = 0; ///< Offset into the section.
90  unsigned Data = 0; ///< Current data entry.
91  unsigned NumData = 0; ///< Number of data entries.
92 
93  /// Advance the iterator.
94  void Next();
95  public:
96  /// Construct a new iterator for the entries at \p DataOffset.
97  ValueIterator(const AppleAcceleratorTable &AccelTable, unsigned DataOffset);
98  /// End marker.
99  ValueIterator() = default;
100 
102  return AtomForms;
103  }
104  ValueIterator &operator++() { Next(); return *this; }
106  ValueIterator I = *this;
107  Next();
108  return I;
109  }
110  friend bool operator==(const ValueIterator &A, const ValueIterator &B) {
111  return A.NumData == B.NumData && A.DataOffset == B.DataOffset;
112  }
113  friend bool operator!=(const ValueIterator &A, const ValueIterator &B) {
114  return !(A == B);
115  }
116  };
117 
120  : DWARFAcceleratorTable(AccelSection, StringSection) {}
121 
122  llvm::Error extract() override;
123  uint32_t getNumBuckets();
124  uint32_t getNumHashes();
125  uint32_t getSizeHdr();
126  uint32_t getHeaderDataLength();
128  bool validateForms();
129 
130  /// Return information related to the DWARF DIE we're looking for when
131  /// performing a lookup by name.
132  ///
133  /// \param HashDataOffset an offset into the hash data table
134  /// \returns <DieOffset, DieTag>
135  /// DieOffset is the offset into the .debug_info section for the DIE
136  /// related to the input hash data offset.
137  /// DieTag is the tag of the DIE
138  std::pair<uint32_t, dwarf::Tag> readAtoms(uint32_t &HashDataOffset);
139  void dump(raw_ostream &OS) const override;
140 
141  /// Look up all entries in the accelerator table matching \c Key.
142  iterator_range<ValueIterator> equal_range(StringRef Key) const;
143 };
144 
145 /// .debug_names section consists of one or more units. Each unit starts with a
146 /// header, which is followed by a list of compilation units, local and foreign
147 /// type units.
148 ///
149 /// These may be followed by an (optional) hash lookup table, which consists of
150 /// an array of buckets and hashes similar to the apple tables above. The only
151 /// difference is that the hashes array is 1-based, and consequently an empty
152 /// bucket is denoted by 0 and not UINT32_MAX.
153 ///
154 /// Next is the name table, which consists of an array of names and array of
155 /// entry offsets. This is different from the apple tables, which store names
156 /// next to the actual entries.
157 ///
158 /// The structure of the entries is described by an abbreviations table, which
159 /// comes after the name table. Unlike the apple tables, which have a uniform
160 /// entry structure described in the header, each .debug_names entry may have
161 /// different index attributes (DW_IDX_???) attached to it.
162 ///
163 /// The last segment consists of a list of entries, which is a 0-terminated list
164 /// referenced by the name table and interpreted with the help of the
165 /// abbreviation table.
167  /// The fixed-size part of a Dwarf 5 Name Index header
168  struct HeaderPOD {
169  uint32_t UnitLength;
170  uint16_t Version;
171  uint16_t Padding;
172  uint32_t CompUnitCount;
173  uint32_t LocalTypeUnitCount;
174  uint32_t ForeignTypeUnitCount;
175  uint32_t BucketCount;
176  uint32_t NameCount;
177  uint32_t AbbrevTableSize;
178  uint32_t AugmentationStringSize;
179  };
180 
181 public:
182  /// Dwarf 5 Name Index header.
183  struct Header : public HeaderPOD {
185 
187  void dump(ScopedPrinter &W) const;
188  };
189 
190  /// Index attribute and its encoding.
194 
196  : Index(Index), Form(Form) {}
197 
198  friend bool operator==(const AttributeEncoding &LHS,
199  const AttributeEncoding &RHS) {
200  return LHS.Index == RHS.Index && LHS.Form == RHS.Form;
201  }
202  };
203 
204  /// Abbreviation describing the encoding of Name Index entries.
205  struct Abbrev {
206  uint32_t Code; ///< Abbreviation code
207  dwarf::Tag Tag; ///< Dwarf Tag of the described entity.
208  std::vector<AttributeEncoding> Attributes; ///< List of index attributes.
209 
211  std::vector<AttributeEncoding> Attributes)
212  : Code(Code), Tag(Tag), Attributes(std::move(Attributes)) {}
213 
214  void dump(ScopedPrinter &W) const;
215  };
216 
217  /// A single entry in the Name Index.
218  struct Entry {
219  const Abbrev &Abbr;
220 
221  /// Values of the index attributes described by Abbr.
222  std::vector<DWARFFormValue> Values;
223 
224  Entry(const Abbrev &Abbr);
225 
226  void dump(ScopedPrinter &W) const;
227  };
228 
229 private:
230  /// Error returned by NameIndex::getEntry to report it has reached the end of
231  /// the entry list.
232  class SentinelError : public ErrorInfo<SentinelError> {
233  public:
234  static char ID;
235 
236  void log(raw_ostream &OS) const override { OS << "Sentinel"; }
237  std::error_code convertToErrorCode() const override;
238  };
239 
240  /// DenseMapInfo for struct Abbrev.
241  struct AbbrevMapInfo {
242  static Abbrev getEmptyKey();
243  static Abbrev getTombstoneKey();
244  static unsigned getHashValue(uint32_t Code) {
246  }
247  static unsigned getHashValue(const Abbrev &Abbr) {
248  return getHashValue(Abbr.Code);
249  }
250  static bool isEqual(uint32_t LHS, const Abbrev &RHS) {
251  return LHS == RHS.Code;
252  }
253  static bool isEqual(const Abbrev &LHS, const Abbrev &RHS) {
254  return LHS.Code == RHS.Code;
255  }
256  };
257 
258  /// A single entry in the Name Table (Dwarf 5 sect. 6.1.1.4.6) of the Name
259  /// Index.
260  struct NameTableEntry {
261  uint32_t StringOffset; ///< Offset of the name of the described entities.
262  uint32_t EntryOffset; ///< Offset of the first Entry in the list.
263  };
264 
265 public:
266  /// Represents a single accelerator table within the Dwarf 5 .debug_names
267  /// section.
268  class NameIndex {
270  struct Header Hdr;
271  const DWARFDebugNames &Section;
272 
273  // Base of the whole unit and of various important tables, as offsets from
274  // the start of the section.
275  uint32_t Base;
276  uint32_t CUsBase;
277  uint32_t BucketsBase;
278  uint32_t HashesBase;
279  uint32_t StringOffsetsBase;
280  uint32_t EntryOffsetsBase;
281  uint32_t EntriesBase;
282 
283  /// Reads offset of compilation unit CU. CU is 0-based.
284  uint32_t getCUOffset(uint32_t CU) const;
285 
286  /// Reads offset of local type unit TU, TU is 0-based.
287  uint32_t getLocalTUOffset(uint32_t TU) const;
288 
289  /// Reads signature of foreign type unit TU. TU is 0-based.
290  uint64_t getForeignTUOffset(uint32_t TU) const;
291 
292  /// Reads an entry in the Bucket Array for the given Bucket. The returned
293  /// value is a (1-based) index into the Names, StringOffsets and
294  /// EntryOffsets arrays. The input Bucket index is 0-based.
295  uint32_t getBucketArrayEntry(uint32_t Bucket) const;
296 
297  /// Reads an entry in the Hash Array for the given Index. The input Index
298  /// is 1-based.
299  uint32_t getHashArrayEntry(uint32_t Index) const;
300 
301  /// Reads an entry in the Name Table for the given Index. The Name Table
302  /// consists of two arrays -- String Offsets and Entry Offsets. The returned
303  /// offsets are relative to the starts of respective sections. Input Index
304  /// is 1-based.
305  NameTableEntry getNameTableEntry(uint32_t Index) const;
306 
307  Expected<Entry> getEntry(uint32_t *Offset) const;
308 
309  void dumpCUs(ScopedPrinter &W) const;
310  void dumpLocalTUs(ScopedPrinter &W) const;
311  void dumpForeignTUs(ScopedPrinter &W) const;
312  void dumpAbbreviations(ScopedPrinter &W) const;
313  bool dumpEntry(ScopedPrinter &W, uint32_t *Offset) const;
314  void dumpName(ScopedPrinter &W, uint32_t Index,
315  Optional<uint32_t> Hash) const;
316  void dumpBucket(ScopedPrinter &W, uint32_t Bucket) const;
317 
318  Expected<AttributeEncoding> extractAttributeEncoding(uint32_t *Offset);
319 
321  extractAttributeEncodings(uint32_t *Offset);
322 
323  Expected<Abbrev> extractAbbrev(uint32_t *Offset);
324 
325  public:
326  NameIndex(const DWARFDebugNames &Section, uint32_t Base)
327  : Section(Section), Base(Base) {}
328 
330  uint32_t getNextUnitOffset() const { return Base + 4 + Hdr.UnitLength; }
331  void dump(ScopedPrinter &W) const;
332  };
333 
334 private:
335  std::vector<NameIndex> NameIndices;
336 
337 public:
340  : DWARFAcceleratorTable(AccelSection, StringSection) {}
341 
342  llvm::Error extract() override;
343  void dump(raw_ostream &OS) const override;
344 };
345 
346 } // end namespace llvm
347 
348 #endif // LLVM_DEBUGINFO_DWARFACCELERATORTABLE_H
The accelerator tables are designed to allow efficient random access (using a symbol name as a key) i...
Abbrev(uint32_t Code, dwarf::Tag Tag, std::vector< AttributeEncoding > Attributes)
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
std::vector< DWARFFormValue > Values
Values of the index attributes described by Abbr.
An iterator for the entries associated with one key.
std::vector< AttributeEncoding > Attributes
List of index attributes.
Implements a dense probed hash-table based set.
Definition: DenseSet.h:221
This class holds an abstract representation of an Accelerator Table, consisting of a sequence of buck...
Definition: AccelTable.h:197
Abbreviation describing the encoding of Name Index entries.
Definition: BitVector.h:921
virtual void dump(raw_ostream &OS) const =0
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
friend bool operator==(const AttributeEncoding &LHS, const AttributeEncoding &RHS)
const ArrayRef< DWARFFormValue > operator*() const
Tagged union holding either a T or a Error.
Definition: CachePruning.h:23
Index attribute and its encoding.
dwarf::Tag Tag
Dwarf Tag of the described entity.
Key
PAL metadata keys.
static bool isEqual(const Function &Caller, const Function &Callee)
friend bool operator!=(const ValueIterator &A, const ValueIterator &B)
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
Represents a single accelerator table within the Dwarf 5 .debug_names section.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This implements the Apple accelerator table format, a precursor of the DWARF 5 accelerator table form...
DWARFDebugNames(const DWARFDataExtractor &AccelSection, DataExtractor StringSection)
virtual llvm::Error extract()=0
void operator=(const DWARFAcceleratorTable &)=delete
Dwarf 5 Name Index header.
DWARFAcceleratorTable(const DWARFDataExtractor &AccelSection, DataExtractor StringSection)
const AMDGPUAS & AS
static const char *const Magic
Definition: Archive.cpp:42
A DataExtractor (typically for an in-memory copy of an object-file section) plus a relocation map for...
A single entry in the Name Index.
.debug_names section consists of one or more units.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:862
constexpr AttributeEncoding(dwarf::Index Index, dwarf::Form Form)
friend bool operator==(const ValueIterator &A, const ValueIterator &B)
A range adaptor for a pair of iterators.
This file contains constants used for implementing Dwarf debug support.
Base class for user error types.
Definition: Error.h:331
NameIndex(const DWARFDebugNames &Section, uint32_t Base)
#define I(x, y, z)
Definition: MD5.cpp:58
AppleAcceleratorTable(const DWARFDataExtractor &AccelSection, DataExtractor StringSection)
uint32_t Code
Abbreviation code.
Lightweight error class with error context and mandatory checking.
Definition: Error.h:156
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
const uint64_t Version
Definition: InstrProf.h:867