Implement equal_range for the DWARF v5 accelerator table

[labath]

Summary

This patch implements the name lookup functionality of the .debug_names
accelerator table and hooks it up to "llvm-dwarfdump -find". To make the
interface of the two kinds of accelerator tables more consistent, I've
created an abstract "DWARFAcceleratorTable::Entry" class, which provides
a consistent interface to access the common functionality of the table
entries (such as getting the die offset, die tag, etc.). I've also
modified the apple table to vend entries conforming to this interface.

[labath]

tools/llvm-dwarfdump/llvm-dwarfdump.cpp

370

Technically, this changes behavior for apple tables as previously it would accept any section offset here, but I think the author was looking for the DIE offset here anyway.

[JDevlieghere]

This is very neat, thanks a lot Pavel!

A few insignificant nits inline.

include/llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h

280

Nit: Index is usually Idx

284

... returned Index is valid ...

303

Missing )

[labath]

Fix issues pointed out by Jonas + clang-format.

[dblaikie]

include/llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h

43

default

290–295

Could these be defaulted (maybe even implicitly defaulted)?

296

Perhaps this should/could be implicit?

[labath]

Resolve David's comments (apart from one, which I have a question on).

[labath]

include/llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h

290–295

These ones are a bit tricky. They could be made default, but then I'd have to un-delete the super class implementations (which I deleted as a standard precaution for polymorphic classes). Maybe I could make the super class functions protected to make sure they're not invoked accidentally ?

(The reason I need these constructors in the first place is so I can return the object as a value from the parsing function without resorting to unique_ptrs and such. I did feel it a bit weird while doing it as this isn't standard practice for polymorphic classes, but it seemed like a nice optimization.)

[labath]

Make the base class copy/move operations protected and remote the hand-coded implementations from the derived class.

[dblaikie]

Also, if possible - the Entry dtor could be made non-virtual and protected in the base class, if these objects are never owned polymorphically, which it /looks/ like they aren't, but not entirely sure.

[labath]

Make base Entry destructor protected and nonvirtual (the class is not owned polymorphically right now).

Will commit once issues with the djb hash function are resolved.

include/llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h

 /// TODO: Generalize the rest of the AppleAcceleratorTable interface and move it
 /// to this class.
 class DWARFAcceleratorTable {
 protected:
   DWARFDataExtractor AccelSection;
   DataExtractor StringSection;
 
 public:
+  /// An abstract class representing a single entry in the accelerator tables.
+  struct Entry {
+  protected:
+    SmallVector<DWARFFormValue, 3> Values;
+
+    Entry() {}
+
+  public:
+    virtual ~Entry();
+
+    /// Returns the Offset of the Compilation Unit associated with this
+    /// Accelerator Entry or None if the Compilation Unit offset is not recorded
+    /// in this Accelerator Entry.
+    virtual Optional<uint64_t> getCUOffset() const = 0;
+
+    /// Returns the Offset of the Debug Info Entry associated with this
+    /// Accelerator Entry or None if the DIE offset is not recorded in this
+    /// Accelerator Entry.
+    virtual Optional<uint64_t> getDIEOffset() const = 0;
+
+    /// Returns the Tag of the Debug Info Entry associated with this
+    /// Accelerator Entry or None if the Tag is not recorded in this
+    /// Accelerator Entry.
+    virtual Optional<dwarf::Tag> getTag() const = 0;
+
+    /// Returns the raw values of fields in the Accelerator Entry. In general,
+    /// these can only be interpreted with the help of the metadata in the
+    /// owning Accelerator Table.
+    ArrayRef<DWARFFormValue> getValues() const { return Values; }
+
+    Entry(const Entry &) = delete;
+    void operator=(const Entry &) = delete;
+  };
+
   DWARFAcceleratorTable(const DWARFDataExtractor &AccelSection,
                         DataExtractor StringSection)
       : AccelSection(AccelSection), StringSection(StringSection) {}
   virtual ~DWARFAcceleratorTable();
 
   virtual llvm::Error extract() = 0;
   virtual void dump(raw_ostream &OS) const = 0;
 
class AppleAcceleratorTable : public DWARFAcceleratorTable {
   bool IsValid = false;
 
   /// Returns true if we should continue scanning for entries or false if we've
   /// reached the last (sentinel) entry of encountered a parsing error.
   bool dumpName(ScopedPrinter &W, SmallVectorImpl<DWARFFormValue> &AtomForms,
                 uint32_t *DataOffset) const;
 
 public:
-  /// An iterator for the entries associated with one key. Each entry can have
-  /// multiple DWARFFormValues.
-  class ValueIterator : public std::iterator<std::input_iterator_tag,
-                                            ArrayRef<DWARFFormValue>> {
-    const AppleAcceleratorTable *AccelTable = nullptr;
-    SmallVector<DWARFFormValue, 3> AtomForms; ///< The decoded data entry.
+  /// Apple-specific implementation of an Accelerator Entry.
+  class Entry final : public DWARFAcceleratorTable::Entry {
+    const HeaderData *HdrData = nullptr;
+
+    Entry(const HeaderData &Data);
+    Entry() = default;
+
+    void extract(const AppleAcceleratorTable &AccelTable, uint32_t *Offset);
+
+  public:
+    Entry(const Entry &RHS) : HdrData(RHS.HdrData) { Values = RHS.Values; }
+    ~Entry() override;
+    Optional<uint64_t> getCUOffset() const override;
+    Optional<uint64_t> getDIEOffset() const override;
+    Optional<dwarf::Tag> getTag() const override;
 
+    /// Returns the value of the Atom in this Accelerator Entry, if the Entry
+    /// contains such Atom.
+    Optional<DWARFFormValue> lookup(HeaderData::AtomType Atom) const;
+
+    friend class AppleAcceleratorTable;
+    friend class ValueIterator;
+  };
+
+  class ValueIterator : public std::iterator<std::input_iterator_tag, Entry> {
+    const AppleAcceleratorTable *AccelTable = nullptr;
+    Entry Current;           ///< The current entry.
     unsigned DataOffset = 0; ///< Offset into the section.
     unsigned Data = 0; ///< Current data entry.
     unsigned NumData = 0; ///< Number of data entries.
 
     /// Advance the iterator.
     void Next();
   public:
     /// Construct a new iterator for the entries at \p DataOffset.
     ValueIterator(const AppleAcceleratorTable &AccelTable, unsigned DataOffset);
     /// End marker.
     ValueIterator() = default;
 
-    const ArrayRef<DWARFFormValue> operator*() const {
-      return AtomForms;
-    }
+    const Entry &operator*() const { return Current; }
     ValueIterator &operator++() { Next(); return *this; }
     ValueIterator operator++(int) {
       ValueIterator I = *this;
       Next();
       return I;
     }
     friend bool operator==(const ValueIterator &A, const ValueIterator &B) {
       return A.NumData == B.NumData && A.DataOffset == B.DataOffset;
     }
     friend bool operator!=(const ValueIterator &A, const ValueIterator &B) {
       return !(A == B);
     }
   };
 
   AppleAcceleratorTable(const DWARFDataExtractor &AccelSection,
                         DataExtractor StringSection)
       : DWARFAcceleratorTable(AccelSection, StringSection) {}
 
   llvm::Error extract() override;
   uint32_t getNumBuckets();
   uint32_t getNumHashes();
   uint32_t getSizeHdr();
   uint32_t getHeaderDataLength();
+
+  /// Return the Atom description, which can be used to interpret the raw values
+  /// of the Accelerator Entries in this table.
   ArrayRef<std::pair<HeaderData::AtomType, HeaderData::Form>> getAtomsDesc();
   bool validateForms();
 
   /// Return information related to the DWARF DIE we're looking for when
   /// performing a lookup by name.
   ///
   /// \param HashDataOffset an offset into the hash data table
   /// \returns <DieOffset, DieTag>
struct HeaderPOD {
     uint32_t ForeignTypeUnitCount;
     uint32_t BucketCount;
     uint32_t NameCount;
     uint32_t AbbrevTableSize;
     uint32_t AugmentationStringSize;
   };
 
 public:
+  class NameIndex;
+  class ValueIterator;
+
   /// Dwarf 5 Name Index header.
   struct Header : public HeaderPOD {
     SmallString<8> AugmentationString;
 
     Error extract(const DWARFDataExtractor &AS, uint32_t *Offset);
     void dump(ScopedPrinter &W) const;
   };
 
struct Abbrev {
 
     Abbrev(uint32_t Code, dwarf::Tag Tag,
            std::vector<AttributeEncoding> Attributes)
         : Code(Code), Tag(Tag), Attributes(std::move(Attributes)) {}
 
     void dump(ScopedPrinter &W) const;
   };
 
-  /// A single entry in the Name Index.
-  struct Entry {
-    const Abbrev &Abbr;
+  /// DWARF v5-specific implementation of an Accelerator Entry.
+  class Entry final : public DWARFAcceleratorTable::Entry {
+    const NameIndex *NameIdx;
+    const Abbrev *Abbr;
+
+    Entry(const NameIndex &NameIdx, const Abbrev &Abbr);
+
+    /// Returns the Index into the Compilation Unit list of the owning Name
+    /// Index or None if this Accelerator Entry does not have an associated
+    /// Compilation Unit. It is up to the user to verify that the returned Index
+    /// is valid in the owning NameIndex (or use getCUOffset(), which will
+    /// handle that check itself).
+    Optional<uint64_t> getCUIndex() const;
 
-    /// Values of the index attributes described by Abbr.
-    std::vector<DWARFFormValue> Values;
+  public:
+    Entry(const Entry &RHS) : NameIdx(RHS.NameIdx), Abbr(RHS.Abbr) {
+      Values = RHS.Values;
+    }
+    Entry(Entry &&RHS) : NameIdx(RHS.NameIdx), Abbr(RHS.Abbr) {
+      Values = std::move(RHS.Values);
+    }
+    ~Entry() override;
 
-    Entry(const Abbrev &Abbr);
+    Optional<uint64_t> getCUOffset() const override;
+    Optional<uint64_t> getDIEOffset() const override;
+    Optional<dwarf::Tag> getTag() const override { return tag(); }
+
+    /// .debug_names-specific getter, which always succeeds (DWARF v5 index
+    /// entries always have a tag).
+    dwarf::Tag tag() const { return Abbr->Tag; }
+
+    /// Return the Abbreviation that can be used to interpret the raw values of
+    /// this Accelerator Entry.
+    const Abbrev &getAbbrev() const { return *Abbr; }
+
+    /// Returns the value of the Index Attribute in this Accelerator Entry, if
+    /// the Entry contains such Attribute.
+    Optional<DWARFFormValue> lookup(dwarf::Index Index) const;
 
     void dump(ScopedPrinter &W) const;
+
+    Entry &operator=(Entry &&RHS) {
+      Values = std::move(RHS.Values);
+      NameIdx = RHS.NameIdx;
+      Abbr = RHS.Abbr;
+      return *this;
+    }
+
+    friend class NameIndex;
+    friend class ValueIterator;
   };
 
 private:
   /// Error returned by NameIndex::getEntry to report it has reached the end of
   /// the entry list.
   class SentinelError : public ErrorInfo<SentinelError> {
   public:
     static char ID;
class NameIndex {
     uint32_t Base;
     uint32_t CUsBase;
     uint32_t BucketsBase;
     uint32_t HashesBase;
     uint32_t StringOffsetsBase;
     uint32_t EntryOffsetsBase;
     uint32_t EntriesBase;
 
-    /// Reads offset of compilation unit CU. CU is 0-based.
-    uint32_t getCUOffset(uint32_t CU) const;
-
-    /// Reads offset of local type unit TU, TU is 0-based.
-    uint32_t getLocalTUOffset(uint32_t TU) const;
-
-    /// Reads signature of foreign type unit TU. TU is 0-based.
-    uint64_t getForeignTUOffset(uint32_t TU) const;
-
     /// Reads an entry in the Bucket Array for the given Bucket. The returned
     /// value is a (1-based) index into the Names, StringOffsets and
     /// EntryOffsets arrays. The input Bucket index is 0-based.
     uint32_t getBucketArrayEntry(uint32_t Bucket) const;
 
     /// Reads an entry in the Hash Array for the given Index. The input Index
     /// is 1-based.
     uint32_t getHashArrayEntry(uint32_t Index) const;
class NameIndex {
     extractAttributeEncodings(uint32_t *Offset);
 
     Expected<Abbrev> extractAbbrev(uint32_t *Offset);
 
   public:
     NameIndex(const DWARFDebugNames &Section, uint32_t Base)
         : Section(Section), Base(Base) {}
 
+    /// Reads offset of compilation unit CU. CU is 0-based.
+    uint32_t getCUOffset(uint32_t CU) const;
+    uint32_t getCUCount() const { return Hdr.CompUnitCount; }
+
+    /// Reads offset of local type unit TU, TU is 0-based.
+    uint32_t getLocalTUOffset(uint32_t TU) const;
+    uint32_t getLocalTUCount() const { return Hdr.LocalTypeUnitCount; }
+
+    /// Reads signature of foreign type unit TU. TU is 0-based.
+    uint64_t getForeignTUSignature(uint32_t TU) const;
+    uint32_t getForeignTUCount() const { return Hdr.ForeignTypeUnitCount; }
+
     llvm::Error extract();
     uint32_t getNextUnitOffset() const { return Base + 4 + Hdr.UnitLength; }
     void dump(ScopedPrinter &W) const;
+
+    friend class DWARFDebugNames;
+  };
+
+  class ValueIterator : public std::iterator<std::input_iterator_tag, Entry> {
+
+    /// The Name Index we are currently iterating through. The implementation
+    /// relies on the fact that this can also be used as an iterator into the
+    /// "NameIndices" vector in the Accelerator section.
+    const NameIndex *CurrentIndex = nullptr;
+
+    Optional<Entry> CurrentEntry;
+    unsigned DataOffset = 0; ///< Offset into the section.
+    std::string Key;         ///< The Key we are searching for.
+    Optional<uint32_t> Hash; ///< Hash of Key, if it has been computed.
+
+    bool getEntryAtCurrentOffset();
+    Optional<uint32_t> findEntryOffsetInCurrentIndex();
+    bool findInCurrentIndex();
+    void searchFromStartOfCurrentIndex();
+    void next();
+
+    /// Set the iterator to the "end" state.
+    void setEnd() { *this = ValueIterator(); }
+
+  public:
+    /// Create a "begin" iterator for looping over all entries in the
+    /// accelerator table matching Key. The iterator will run through all Name
+    /// Indexes in the section in sequence.
+    ValueIterator(const DWARFDebugNames &AccelTable, StringRef Key);
+
+    /// End marker.
+    ValueIterator() = default;
+
+    const Entry &operator*() const { return *CurrentEntry; }
+    ValueIterator &operator++() {
+      next();
+      return *this;
+    }
+    ValueIterator operator++(int) {
+      ValueIterator I = *this;
+      next();
+      return I;
+    }
+
+    friend bool operator==(const ValueIterator &A, const ValueIterator &B) {
+      return A.CurrentIndex == B.CurrentIndex && A.DataOffset == B.DataOffset;
+    }
+    friend bool operator!=(const ValueIterator &A, const ValueIterator &B) {
+      return !(A == B);
+    }
   };
 
 private:
-  std::vector<NameIndex> NameIndices;
+  llvm::SmallVector<NameIndex, 0> NameIndices;
 
 public:
   DWARFDebugNames(const DWARFDataExtractor &AccelSection,
                   DataExtractor StringSection)
       : DWARFAcceleratorTable(AccelSection, StringSection) {}
 
   llvm::Error extract() override;
   void dump(raw_ostream &OS) const override;
+
+  /// Look up all entries in the accelerator table matching \c Key.
+  iterator_range<ValueIterator> equal_range(StringRef Key) const;
 };
 
 } // end namespace llvm
 
 #endif // LLVM_DEBUGINFO_DWARFACCELERATORTABLE_H

lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp

static DwarfConstant formatIndex(unsigned Idx) {
   return {dwarf::IndexString, "IDX", Idx};
 }
 
 static DwarfConstant formatAtom(unsigned Atom) {
   return {dwarf::AtomTypeString, "ATOM", Atom};
 }
 
 DWARFAcceleratorTable::~DWARFAcceleratorTable() = default;
+DWARFAcceleratorTable::Entry::~Entry() = default;
 
 llvm::Error AppleAcceleratorTable::extract() {
   uint32_t Offset = 0;
 
   // Check that we can at least read the header.
   if (!AccelSection.isValidOffset(offsetof(Header, HeaderDataLength)+4))
     return make_error<StringError>("Section too small: cannot read header.",
                                    inconvertibleErrorCode());
for (unsigned HashIdx = Index; HashIdx < Hdr.HashCount; ++HashIdx) {
         continue;
       }
       while (dumpName(W, AtomForms, &DataOffset))
         /*empty*/;
     }
   }
 }
 
+AppleAcceleratorTable::Entry::Entry(
+    const AppleAcceleratorTable::HeaderData &HdrData)
+    : HdrData(&HdrData) {
+  Values.reserve(HdrData.Atoms.size());
+  for (const auto &Atom : HdrData.Atoms)
+    Values.push_back(DWARFFormValue(Atom.second));
+}
+
+void AppleAcceleratorTable::Entry::extract(
+    const AppleAcceleratorTable &AccelTable, uint32_t *Offset) {
+
+  DWARFFormParams FormParams = {AccelTable.Hdr.Version, 0,
+                                dwarf::DwarfFormat::DWARF32};
+  for (auto &Atom : Values)
+    Atom.extractValue(AccelTable.AccelSection, Offset, FormParams);
+}
+
+AppleAcceleratorTable::Entry::~Entry() = default;
+
+Optional<DWARFFormValue>
+AppleAcceleratorTable::Entry::lookup(HeaderData::AtomType Atom) const {
+  assert(HdrData && "Dereferencing end iterator?");
+  assert(HdrData->Atoms.size() == Values.size());
+  for (const auto &Tuple : zip_first(HdrData->Atoms, Values)) {
+    if (std::get<0>(Tuple).first == Atom)
+      return std::get<1>(Tuple);
+  }
+  return None;
+}
+
+Optional<uint64_t> AppleAcceleratorTable::Entry::getDIEOffset() const {
+  if (Optional<DWARFFormValue> Off = lookup(dwarf::DW_ATOM_die_offset))
+    return Off->getAsSectionOffset();
+  return None;
+}
+
+Optional<uint64_t> AppleAcceleratorTable::Entry::getCUOffset() const {
+  if (Optional<DWARFFormValue> Off = lookup(dwarf::DW_ATOM_cu_offset))
+    return Off->getAsSectionOffset();
+  return None;
+}
+
+Optional<dwarf::Tag> AppleAcceleratorTable::Entry::getTag() const {
+  Optional<DWARFFormValue> Tag = lookup(dwarf::DW_ATOM_die_tag);
+  if (!Tag)
+    return None;
+  if (Optional<uint64_t> Value = Tag->getAsUnsignedConstant())
+    return dwarf::Tag(*Value);
+  return None;
+}
+
 AppleAcceleratorTable::ValueIterator::ValueIterator(
     const AppleAcceleratorTable &AccelTable, unsigned Offset)
-    : AccelTable(&AccelTable), DataOffset(Offset) {
+    : AccelTable(&AccelTable), Current(AccelTable.HdrData), DataOffset(Offset) {
   if (!AccelTable.AccelSection.isValidOffsetForDataOfSize(DataOffset, 4))
     return;
 
-  for (const auto &Atom : AccelTable.HdrData.Atoms)
-    AtomForms.push_back(DWARFFormValue(Atom.second));
-
   // Read the first entry.
   NumData = AccelTable.AccelSection.getU32(&DataOffset);
   Next();
 }
 
 void AppleAcceleratorTable::ValueIterator::Next() {
   assert(NumData > 0 && "attempted to increment iterator past the end");
   auto &AccelSection = AccelTable->AccelSection;
   if (Data >= NumData ||
       !AccelSection.isValidOffsetForDataOfSize(DataOffset, 4)) {
     NumData = 0;
     return;
   }
-  DWARFFormParams FormParams = {AccelTable->Hdr.Version, 0,
-                                dwarf::DwarfFormat::DWARF32};
-  for (auto &Atom : AtomForms)
-    Atom.extractValue(AccelSection, &DataOffset, FormParams);
+  Current.extract(*AccelTable, &DataOffset);
   ++Data;
 }
 
 iterator_range<AppleAcceleratorTable::ValueIterator>
 AppleAcceleratorTable::equal_range(StringRef Key) const {
   if (!IsValid)
     return make_range(ValueIterator(), ValueIterator());
 
if (isSentinel(*AbbrevOr))
       return Error::success();
 
     if (!Abbrevs.insert(std::move(*AbbrevOr)).second) {
       return make_error<StringError>("Duplicate abbreviation code.",
                                      inconvertibleErrorCode());
     }
   }
 }
-
-DWARFDebugNames::Entry::Entry(const Abbrev &Abbr) : Abbr(Abbr) {
+DWARFDebugNames::Entry::Entry(const NameIndex &NameIdx, const Abbrev &Abbr)
+    : NameIdx(&NameIdx), Abbr(&Abbr) {
   // This merely creates form values. It is up to the caller
   // (NameIndex::getEntry) to populate them.
   Values.reserve(Abbr.Attributes.size());
   for (const auto &Attr : Abbr.Attributes)
     Values.emplace_back(Attr.Form);
 }
+DWARFDebugNames::Entry::~Entry() = default;
+
+Optional<DWARFFormValue>
+DWARFDebugNames::Entry::lookup(dwarf::Index Index) const {
+  assert(Abbr->Attributes.size() == Values.size());
+  for (const auto &Tuple : zip_first(Abbr->Attributes, Values)) {
+    if (std::get<0>(Tuple).Index == Index)
+      return std::get<1>(Tuple);
+  }
+  return None;
+}
+
+Optional<uint64_t> DWARFDebugNames::Entry::getDIEOffset() const {
+  if (Optional<DWARFFormValue> Off = lookup(dwarf::DW_IDX_die_offset))
+    return Off->getAsSectionOffset();
+  return None;
+}
+
+Optional<uint64_t> DWARFDebugNames::Entry::getCUIndex() const {
+  if (Optional<DWARFFormValue> Off = lookup(dwarf::DW_IDX_compile_unit))
+    return Off->getAsUnsignedConstant();
+  return None;
+}
+
+Optional<uint64_t> DWARFDebugNames::Entry::getCUOffset() const {
+  Optional<uint64_t> Index = getCUIndex();
+  if (!Index || *Index >= NameIdx->getCUCount())
+    return None;
+  return NameIdx->getCUOffset(*Index);
+}
 
 void DWARFDebugNames::Entry::dump(ScopedPrinter &W) const {
-  W.printHex("Abbrev", Abbr.Code);
-  W.startLine() << "Tag: " << formatTag(Abbr.Tag) << "\n";
+  W.printHex("Abbrev", Abbr->Code);
+  W.startLine() << "Tag: " << formatTag(Abbr->Tag) << "\n";
 
-  assert(Abbr.Attributes.size() == Values.size());
-  for (uint32_t I = 0, E = Values.size(); I < E; ++I) {
-    W.startLine() << formatIndex(Abbr.Attributes[I].Index) << ": ";
-    Values[I].dump(W.getOStream());
+  assert(Abbr->Attributes.size() == Values.size());
+  for (const auto &Tuple : zip_first(Abbr->Attributes, Values)) {
+    W.startLine() << formatIndex(std::get<0>(Tuple).Index) << ": ";
+    std::get<1>(Tuple).dump(W.getOStream());
     W.getOStream() << '\n';
   }
 }
 
 char DWARFDebugNames::SentinelError::ID;
 std::error_code DWARFDebugNames::SentinelError::convertToErrorCode() const {
   return inconvertibleErrorCode();
 }
 
 uint32_t DWARFDebugNames::NameIndex::getCUOffset(uint32_t CU) const {
   assert(CU < Hdr.CompUnitCount);
   uint32_t Offset = CUsBase + 4 * CU;
   return Section.AccelSection.getRelocatedValue(4, &Offset);
 }
 
 uint32_t DWARFDebugNames::NameIndex::getLocalTUOffset(uint32_t TU) const {
   assert(TU < Hdr.LocalTypeUnitCount);
   uint32_t Offset = CUsBase + Hdr.CompUnitCount * 4;
   return Section.AccelSection.getRelocatedValue(4, &Offset);
 }
 
-uint64_t DWARFDebugNames::NameIndex::getForeignTUOffset(uint32_t TU) const {
+uint64_t DWARFDebugNames::NameIndex::getForeignTUSignature(uint32_t TU) const {
   assert(TU < Hdr.ForeignTypeUnitCount);
   uint32_t Offset = CUsBase + (Hdr.CompUnitCount + Hdr.LocalTypeUnitCount) * 4;
   return Section.AccelSection.getU64(&Offset);
 }
 
 Expected<DWARFDebugNames::Entry>
 DWARFDebugNames::NameIndex::getEntry(uint32_t *Offset) const {
   const DWARFDataExtractor &AS = Section.AccelSection;
   if (!AS.isValidOffset(*Offset))
     return make_error<StringError>("Incorrectly terminated entry list",
                                    inconvertibleErrorCode());
 
   uint32_t AbbrevCode = AS.getULEB128(Offset);
   if (AbbrevCode == 0)
     return make_error<SentinelError>();
 
   const auto AbbrevIt = Abbrevs.find_as(AbbrevCode);
   if (AbbrevIt == Abbrevs.end())
     return make_error<StringError>("Invalid abbreviation",
                                    inconvertibleErrorCode());
 
-  Entry E(*AbbrevIt);
+  Entry E(*this, *AbbrevIt);
 
   DWARFFormParams FormParams = {Hdr.Version, 0, dwarf::DwarfFormat::DWARF32};
   for (auto &Value : E.Values) {
     if (!Value.extractValue(AS, Offset, FormParams))
       return make_error<StringError>("Error extracting index attribute values",
                                      inconvertibleErrorCode());
   }
   return std::move(E);

 
 void DWARFDebugNames::NameIndex::dumpForeignTUs(ScopedPrinter &W) const {
   if (Hdr.ForeignTypeUnitCount == 0)
     return;
 
   ListScope TUScope(W, "Foreign Type Unit signatures");
   for (uint32_t TU = 0; TU < Hdr.ForeignTypeUnitCount; ++TU) {
     W.startLine() << format("ForeignTU[%u]: 0x%016" PRIx64 "\n", TU,
-                            getForeignTUOffset(TU));
+                            getForeignTUSignature(TU));
   }
 }
 
 void DWARFDebugNames::NameIndex::dumpAbbreviations(ScopedPrinter &W) const {
   ListScope AbbrevsScope(W, "Abbreviations");
   for (const auto &Abbr : Abbrevs)
     Abbr.dump(W);
 }
llvm::Error DWARFDebugNames::extract() {
   return Error::success();
 }
 
 LLVM_DUMP_METHOD void DWARFDebugNames::dump(raw_ostream &OS) const {
   ScopedPrinter W(OS);
   for (const NameIndex &NI : NameIndices)
     NI.dump(W);
 }
+
+Optional<uint32_t>
+DWARFDebugNames::ValueIterator::findEntryOffsetInCurrentIndex() {
+  const Header &Hdr = CurrentIndex->Hdr;
+  if (Hdr.BucketCount == 0) {
+    // No Hash Table, We need to search through all names in the Name Index.
+    for (uint32_t Index = 1; Index <= Hdr.NameCount; ++Index) {
+      NameTableEntry NTE = CurrentIndex->getNameTableEntry(Index);
+      if (CurrentIndex->Section.StringSection.getCStr(&NTE.StringOffset) == Key)
+        return NTE.EntryOffset;
+    }
+    return None;
+  }
+
+  // The Name Index has a Hash Table, so use that to speed up the search.
+  // Compute the Key Hash, if it has not been done already.
+  if (!Hash)
+    Hash = caseFoldingDjbHash(Key);
+  uint32_t Bucket = *Hash % Hdr.BucketCount;
+  uint32_t Index = CurrentIndex->getBucketArrayEntry(Bucket);
+  if (Index == 0)
+    return None; // Empty bucket
+
+  for (; Index <= Hdr.NameCount; ++Index) {
+    uint32_t Hash = CurrentIndex->getHashArrayEntry(Index);
+    if (Hash % Hdr.BucketCount != Bucket)
+      return None; // End of bucket
+
+    NameTableEntry NTE = CurrentIndex->getNameTableEntry(Index);
+    if (CurrentIndex->Section.StringSection.getCStr(&NTE.StringOffset) == Key)
+      return NTE.EntryOffset;
+  }
+  return None;
+}
+
+bool DWARFDebugNames::ValueIterator::getEntryAtCurrentOffset() {
+  auto EntryOr = CurrentIndex->getEntry(&DataOffset);
+  if (!EntryOr) {
+    consumeError(EntryOr.takeError());
+    return false;
+  }
+  CurrentEntry = std::move(*EntryOr);
+  return true;
+}
+
+bool DWARFDebugNames::ValueIterator::findInCurrentIndex() {
+  Optional<uint32_t> Offset = findEntryOffsetInCurrentIndex();
+  if (!Offset)
+    return false;
+  DataOffset = *Offset;
+  return getEntryAtCurrentOffset();
+}
+
+void DWARFDebugNames::ValueIterator::searchFromStartOfCurrentIndex() {
+  for (const NameIndex *End = CurrentIndex->Section.NameIndices.end();
+       CurrentIndex != End; ++CurrentIndex) {
+    if (findInCurrentIndex())
+      return;
+  }
+  setEnd();
+}
+
+void DWARFDebugNames::ValueIterator::next() {
+  assert(CurrentIndex && "Incrementing an end() iterator?");
+
+  // First try the next entry in the current Index.
+  if (getEntryAtCurrentOffset())
+    return;
+
+  // Try the next Name Index.
+  ++CurrentIndex;
+  searchFromStartOfCurrentIndex();
+}
+
+DWARFDebugNames::ValueIterator::ValueIterator(const DWARFDebugNames &AccelTable,
+                                              StringRef Key)
+    : CurrentIndex(AccelTable.NameIndices.begin()), Key(Key) {
+  searchFromStartOfCurrentIndex();
+}
+
+iterator_range<DWARFDebugNames::ValueIterator>
+DWARFDebugNames::equal_range(StringRef Key) const {
+  if (NameIndices.empty())
+    return make_range(ValueIterator(), ValueIterator());
+  return make_range(ValueIterator(*this, Key), ValueIterator());
+}

test/tools/llvm-dwarfdump/X86/debug-names-find.s

+# RUN: llvm-mc -triple x86_64-pc-linux %s -filetype=obj -o %t
+# RUN: llvm-dwarfdump -find=foo %t | FileCheck --check-prefix=FOO %s
+# RUN: llvm-dwarfdump -find=baz %t | FileCheck --check-prefix=BAZ %s
+# RUN: llvm-dwarfdump -find=missing %t | FileCheck --check-prefix=MISSING %s
+
+# FOO: DW_TAG_subprogram
+# FOO-NEXT: DW_AT_name ("foo")
+# FOO-NEXT: DW_AT_external
+
+# BAZ: DW_TAG_subprogram
+# BAZ-NEXT: DW_AT_name ("baz")
+# BAZ-NEXT: DW_AT_external
+
+# MISSING-NOT: foo
+# MISSING-NOT: bar
+# MISSING-NOT: baz
+# MISSING-NOT: bazz
+
+  .section  .debug_str,"MS",@progbits,1
+.Lstring_foo:
+  .asciz  "foo"
+.Lstring_foo_mangled:
+  .asciz  "_Z3foov"
+.Lstring_bar:
+  .asciz  "bar"
+.Lstring_baz:
+  .asciz  "baz"
+.Lstring_bazz:
+  .asciz  "bazz"
+.Lstring_producer:
+  .asciz  "Hand-written dwarf"
+
+  .section  .debug_abbrev,"",@progbits
+.Lsection_abbrev:
+  .byte 1                       # Abbreviation Code
+  .byte 17                      # DW_TAG_compile_unit
+  .byte 1                       # DW_CHILDREN_yes
+  .byte 37                      # DW_AT_producer
+  .byte 14                      # DW_FORM_strp
+  .byte 19                      # DW_AT_language
+  .byte 5                       # DW_FORM_data2
+  .byte 0                       # EOM(1)
+  .byte 0                       # EOM(2)
+  .byte 2                       # Abbreviation Code
+  .byte 46                      # DW_TAG_subprogram
+  .byte 0                       # DW_CHILDREN_no
+  .byte 3                       # DW_AT_name
+  .byte 14                      # DW_FORM_strp
+  .byte 63                      # DW_AT_external
+  .byte 25                      # DW_FORM_flag_present
+  .byte 0                       # EOM(1)
+  .byte 0                       # EOM(2)
+  .byte 0                       # EOM(3)
+
+  .section  .debug_info,"",@progbits
+.Lcu_begin0:
+  .long .Lcu_end0-.Lcu_start0   # Length of Unit
+.Lcu_start0:
+  .short  4                       # DWARF version number
+  .long .Lsection_abbrev        # Offset Into Abbrev. Section
+  .byte 8                       # Address Size (in bytes)
+  .byte 1                       # Abbrev [1] DW_TAG_compile_unit
+  .long .Lstring_producer       # DW_AT_producer
+  .short  12                      # DW_AT_language
+.Ldie_foo:
+  .byte 2                       # Abbrev [2] DW_TAG_subprogram
+  .long .Lstring_foo            # DW_AT_name
+                                        # DW_AT_external
+.Ldie_bar:
+  .byte 2                       # Abbrev [2] DW_TAG_subprogram
+  .long .Lstring_bar            # DW_AT_name
+                                        # DW_AT_external
+  .byte 0                       # End Of Children Mark
+.Lcu_end0:
+
+.Lcu_begin1:
+  .long .Lcu_end1-.Lcu_start1   # Length of Unit
+.Lcu_start1:
+  .short  4                       # DWARF version number
+  .long .Lsection_abbrev        # Offset Into Abbrev. Section
+  .byte 8                       # Address Size (in bytes)
+  .byte 1                       # Abbrev [1] DW_TAG_compile_unit
+  .long .Lstring_producer       # DW_AT_producer
+  .short  12                      # DW_AT_language
+.Ldie_baz:
+  .byte 2                       # Abbrev [2] DW_TAG_subprogram
+  .long .Lstring_baz            # DW_AT_name
+                                        # DW_AT_external
+.Ldie_bazz:
+  .byte 2                       # Abbrev [2] DW_TAG_subprogram
+  .long .Lstring_bazz           # DW_AT_name
+                                        # DW_AT_external
+  .byte 0                       # End Of Children Mark
+.Lcu_end1:
+
+  .section  .debug_names,"",@progbits
+  .long .Lnames_end0-.Lnames_start0 # Header: contribution length
+.Lnames_start0:
+  .short  5                       # Header: version
+  .short  0                       # Header: padding
+  .long 1                       # Header: compilation unit count
+  .long 0                       # Header: local type unit count
+  .long 0                       # Header: foreign type unit count
+  .long 2                       # Header: bucket count
+  .long 3                       # Header: name count
+  .long .Lnames_abbrev_end0-.Lnames_abbrev_start0 # Header: abbreviation table size
+  .long 0                       # Header: augmentation length
+  .long .Lcu_begin0             # Compilation unit 0
+  .long 1                       # Bucket 0
+  .long 2                       # Bucket 1
+        .long   193487034               # Hash in Bucket 0
+  .long 193491849               # Hash in Bucket 1
+  .long -1257882357             # Hash in Bucket 1
+  .long .Lstring_bar            # String in Bucket 1: bar
+  .long .Lstring_foo            # String in Bucket 1: foo
+  .long .Lstring_foo_mangled    # String in Bucket 1: _Z3foov
+  .long .Lnames0-.Lnames_entries0 # Offset in Bucket 1
+  .long .Lnames1-.Lnames_entries0 # Offset in Bucket 1
+  .long .Lnames2-.Lnames_entries0 # Offset in Bucket 1
+.Lnames_abbrev_start0:
+  .byte 46                      # Abbrev code
+  .byte 46                      # DW_TAG_subprogram
+  .byte 3                       # DW_IDX_die_offset
+  .byte 6                       # DW_FORM_data4
+  .byte 0                       # End of abbrev
+  .byte 0                       # End of abbrev
+  .byte 0                       # End of abbrev list
+.Lnames_abbrev_end0:
+.Lnames_entries0:
+.Lnames0:
+  .byte 46                      # Abbrev code
+  .long .Ldie_bar               # DW_IDX_die_offset
+  .long 0                       # End of list: bar
+.Lnames1:
+  .byte 46                      # Abbrev code
+  .long .Ldie_foo               # DW_IDX_die_offset
+  .long 0                       # End of list: foo
+.Lnames2:
+  .byte 46                      # Abbrev code
+  .long .Ldie_foo               # DW_IDX_die_offset
+  .long 0                       # End of list: _Z3foov
+  .p2align  2
+.Lnames_end0:
+
+# Index of compilation unit 1. This one has no hash table.
+  .long .Lnames_end1-.Lnames_start1 # Header: contribution length
+.Lnames_start1:
+  .short  5                       # Header: version
+  .short  0                       # Header: padding
+  .long 1                       # Header: compilation unit count
+  .long 0                       # Header: local type unit count
+  .long 0                       # Header: foreign type unit count
+  .long 0                       # Header: bucket count
+  .long 2                       # Header: name count
+  .long .Lnames_abbrev_end1-.Lnames_abbrev_start1 # Header: abbreviation table size
+  .long 0                       # Header: augmentation length
+  .long .Lcu_begin1             # Compilation unit 0
+  .long .Lstring_baz            # String in Bucket 1: baz
+  .long .Lstring_bazz           # String in Bucket 1: bazz
+  .long .Lnames3-.Lnames_entries1 # Offset in Bucket 1
+  .long .Lnames4-.Lnames_entries1 # Offset in Bucket 1
+.Lnames_abbrev_start1:
+  .byte 46                      # Abbrev code
+  .byte 46                      # DW_TAG_subprogram
+  .byte 3                       # DW_IDX_die_offset
+  .byte 6                       # DW_FORM_data4
+  .byte 0                       # End of abbrev
+  .byte 0                       # End of abbrev
+  .byte 0                       # End of abbrev list
+.Lnames_abbrev_end1:
+.Lnames_entries1:
+.Lnames3:
+  .byte 46                      # Abbrev code
+  .long .Ldie_baz               # DW_IDX_die_offset
+  .long 0                       # End of list: baz
+  .p2align  2
+.Lnames4:
+  .byte 46                      # Abbrev code
+  .long .Ldie_bazz              # DW_IDX_die_offset
+  .long 0                       # End of list: baz
+  .p2align  2
+.Lnames_end1:

tools/llvm-dwarfdump/llvm-dwarfdump.cpp

if (DILineInfo LineInfo = DICtx.getLineInfoForAddress(Lookup))
     LineInfo.dump(OS);
 
   return true;
 }
 
 bool collectStatsForObjectFile(ObjectFile &Obj, DWARFContext &DICtx,
                                Twine Filename, raw_ostream &OS);
 
+template <typename AccelTable>
+static Optional<uint64_t> getDIEOffset(const AccelTable &Accel,
+                                       StringRef Name) {
+  for (const auto &Entry : Accel.equal_range(Name))
+    if (Optional<uint64_t> Off = Entry.getDIEOffset())
+      return *Off;
+  return None;
+}
+
 static bool dumpObjectFile(ObjectFile &Obj, DWARFContext &DICtx, Twine Filename,
                            raw_ostream &OS) {
   logAllUnhandledErrors(DICtx.loadRegisterInfo(Obj), errs(),
                         Filename.str() + ": ");
   // The UUID dump already contains all the same information.
   if (!(DumpType & DIDT_UUID) || DumpType == DIDT_All)
     OS << Filename << ":\tfile format " << Obj.getFileFormatName() << '\n';
 
if (!Name.empty()) {
     filterByName(Names, DICtx.dwo_compile_units(), OS);
     return true;
   }
 
   // Handle the --find option and lower it to --debug-info=<offset>.
   if (!Find.empty()) {
     DumpOffsets[DIDT_ID_DebugInfo] = [&]() -> llvm::Optional<uint64_t> {
       for (auto Name : Find) {
-        auto find = [&](const AppleAcceleratorTable &Accel)
-            -> llvm::Optional<uint64_t> {
-          for (auto Entry : Accel.equal_range(Name))
-            for (auto Atom : Entry)
-              if (auto Offset = Atom.getAsSectionOffset())
-                return Offset;
-          return None;
-        };
-        if (auto Offset = find(DICtx.getAppleNames()))
+        if (auto Offset = getDIEOffset(DICtx.getAppleNames(), Name))
+          return DumpOffsets[DIDT_ID_DebugInfo] = *Offset;
+        if (auto Offset = getDIEOffset(DICtx.getAppleTypes(), Name))
           return DumpOffsets[DIDT_ID_DebugInfo] = *Offset;
-        if (auto Offset = find(DICtx.getAppleTypes()))
+        if (auto Offset = getDIEOffset(DICtx.getAppleNamespaces(), Name))
           return DumpOffsets[DIDT_ID_DebugInfo] = *Offset;
-        if (auto Offset = find(DICtx.getAppleNamespaces()))
+        if (auto Offset = getDIEOffset(DICtx.getDebugNames(), Name))
           return DumpOffsets[DIDT_ID_DebugInfo] = *Offset;
-        // TODO: Add .debug_names support
       }
       return None;
     }();
     // Early exit if --find was specified but the current file doesn't have it.
     if (!DumpOffsets[DIDT_ID_DebugInfo])
       return true;
   }