[AppleTables] Implement iterator over all entries in table

[fdeazeve]

Summary

This commit adds functionality to the Apple Accelerator table allowing iteration
over all elements in the table.

Our iterators look like streaming iterators: when we increment the iterator we
check if there is still enough data in the "stream" (in our case, the blob of
data of the accelerator table) and extract the next entry. If any failures
occur, we immediately set the iterator to be the end iterator.

Since the ultimate user of this functionality is LLDB, there are roughly two
iteration methods we want support: one that also loads the name of each entry,
and one which does not. Loading names is measurably slower (one order the
magnitude) than only loading DIEs, so we used some template metaprograming to
implement both iteration methods.

[fdeazeve]

Add review dependency

[aprantl]

llvm/include/llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h

260

should this be default initialized?

[dblaikie]

llvm/include/llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h

256

Can you use any of the iterator helpers we have to ensure the whole iterator contract is implemented easily?

294–300

Rather than template metaprogramming - could this be done lazily? (store StrOffset as a member of some Entry type (either the current one, or some wrapper) and a member function of that entry could do the work on-request?

325–328

I don't think it's valid for forward iterators to return by value - I think yo uhave to create a pair as a member and return a reference to that. So that op-> can be implemented (since it needs to return a pointer).

[fdeazeve]

llvm/include/llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h

256

Oh I didn't know these exist, I'll have a look!

260

I'm not sure I follow the suggestion: the one and only constructor of the class ensures it is initialized properly. Is there some concern about initialization here?

294–300

That's an interesting one. Note that this *is* done lazily: we only do it if someone calls all_entries_with_names (instead of all_entries) which presumably means they are interested in the name.

That said we could add an extra member to the Entry class which would substantially simplify code and also enable me to address the other concern you had about operator ->! I'll give this a try.

325–328

Good point, let me give this a try

[fdeazeve]

Address review comments

[dblaikie]

llvm/include/llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h

248

Ah, sorry, I probably wouldn't complicate this by deriving, needing a virtual dtor, etc.

Maybe composition? EntryWithName could be closer to the std::pair (but, yeah, it needs to be a bit smarter) than this - contains an Entry, the offset and a function to get the name.

[fdeazeve]

Use composition instead of inheritance

llvm/include/llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h

248

It seems that composition leaks a lot of the implementation to users of this class. For example, they will need to do Entry.BaseEntry.getDIESectionOffset instead of just Entry.getDIESectionOffset. To avoid this, we would need to copy all public methods of Entry and implement them by calling the corresponding method on the Entry member... but that's just re-implementing inheritance manually.

Note that the base class Entry still derives from a pure virtual class, even if we remove this new inheritance; the only reason the compiler was not giving a dtor warning before is because Entry was marked as final.

IMO the more artificial part of this hierarchy is the pure virtual class, which AFAICT is not taken advantage of (I couldn't find any virtual uses of them). I believe the original goal was that Apple tables and the Dwarf 5 tables could share an interface, but maybe it doesn't have to be a virtual interface, instead some sort of CRTP.

All that said, for now I have moved to composition instead of inheritance. If we feel like this becomes too cumbersome, we can re-evaluate.

[dblaikie]

llvm/include/llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h

248

Fair enough - I still tend a bit towards composition, though perhaps if you want to cleanup the virtual base, if it turns out it hasn't been useful - then maybe derivation isn't so bad?

252

If StrOffset is going to be public, probably could skip the accessor and mutate it directly?

260

yeah, I'd second the suggestion - I'd tend towards a member initializer over an init list, seems to simplify things a bit - if another ctor is added, if it's a clear default state for the member, etc

[fdeazeve]

Remove accessor methods, use member initialization.

llvm/include/llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h

252

Good point!

260

Sounds good, I'll initialize this to the end marker.

I can see why that is appealing, but personally believe it gives the false security that things are initialized properly. To use your example of a new ctor, consider the case someone forgets to initialize the member: no tool will catch this when member initialization was used. But tools exist to catch use of uninitialized variables/members (e.g. -Wuninitialized)

[fdeazeve]

Hopefully I've addressed all the major concerns here, so I'll go ahead and merge this; happy to address any other suggestions afterwards!

[MaskRay]

llvm/tools/llvm-dwarfdump/llvm-dwarfdump.cpp

466

This relies on the iteration order of StringMap and SmallSet, which is not good. I'll fix this to use MapVector.

llvm/include/llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h

class AppleAcceleratorTable : public DWARFAcceleratorTable {
   uint64_t getHashBase() const { return getBucketBase() + getNumBuckets() * 4; }
 
   /// Return the offset into the section where the I-th hash is.
   uint64_t getIthHashBase(uint32_t I) const { return getHashBase() + I * 4; }
 
   /// Return the offset into the section where the offset list begins.
   uint64_t getOffsetBase() const { return getHashBase() + getNumHashes() * 4; }
 
+  /// Return the offset into the section where the table entries begin.
+  uint64_t getEntriesBase() const {
+    return getOffsetBase() + getNumHashes() * 4;
+  }
+
   /// Return the offset into the section where the I-th offset is.
   uint64_t getIthOffsetBase(uint32_t I) const {
     return getOffsetBase() + I * 4;
   }
 
   /// Returns the index of the bucket where a hypothetical Hash would be.
   uint32_t hashToBucketIdx(uint32_t Hash) const {
     return Hash % getNumBuckets();
SameNameIterator &operator++() {
       return *this;
     }
     friend bool operator==(const SameNameIterator &A,
                            const SameNameIterator &B) {
       return A.Offset == B.Offset;
     }
   };
 
+  struct EntryWithName {
+    EntryWithName(const AppleAcceleratorTable &Table)
+        : BaseEntry(Table), StrOffset(0) {}
+
+    std::optional<StringRef> readName() const {
+      return BaseEntry.Table.readStringFromStrSection(StrOffset);
+    }
+
+    Entry BaseEntry;
+    uint32_t StrOffset;
+  };
+
+  /// An iterator for all entries in the table.
+  class Iterator
+      : public iterator_facade_base<Iterator, std::forward_iterator_tag,
+                                    EntryWithName> {
+    constexpr static auto EndMarker = std::numeric_limits<uint64_t>::max();
+
+    EntryWithName Current;
+    uint64_t Offset = EndMarker;
+    uint32_t NumEntriesToCome = 0;
+
+    void setToEnd() { Offset = EndMarker; }
+    bool isEnd() const { return Offset == EndMarker; }
+    const AppleAcceleratorTable &getTable() const {
+      return Current.BaseEntry.Table;
+    }
+
+    /// Reads the next Entry in the table, populating `Current`.
+    /// If not possible (e.g. end of the section), becomes the end iterator.
+    void prepareNextEntryOrEnd();
+
+    /// Reads the next string pointer and the entry count for that string,
+    /// populating `NumEntriesToCome`.
+    /// If not possible (e.g. end of the section), becomes the end iterator.
+    /// Assumes `Offset` points to a string reference.
+    void prepareNextStringOrEnd();
+
+  public:
+    Iterator(const AppleAcceleratorTable &Table, bool SetEnd = false);
+
+    Iterator &operator++() {
+      prepareNextEntryOrEnd();
+      return *this;
+    }
+    bool operator==(const Iterator &It) const { return Offset == It.Offset; }
+    const EntryWithName &operator*() const {
+      assert(!isEnd() && "dereferencing end iterator");
+      return Current;
+    }
+  };
+
   AppleAcceleratorTable(const DWARFDataExtractor &AccelSection,
                         DataExtractor StringSection)
       : DWARFAcceleratorTable(AccelSection, StringSection) {}
 
   Error extract() override;
   uint32_t getNumBuckets() const;
   uint32_t getNumHashes() const;
   uint32_t getSizeHdr() const;
   uint32_t getHeaderDataLength() const;
 
   /// Returns the size of one HashData entry.
   uint32_t getHashDataEntryLength() const { return HashDataEntryLength; }
 
   /// 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>
   /// DieOffset is the offset into the .debug_info section for the DIE
   /// related to the input hash data offset.
   /// DieTag is the tag of the DIE
   std::pair<uint64_t, dwarf::Tag> readAtoms(uint64_t *HashDataOffset);
   void dump(raw_ostream &OS) const override;
 
   /// Look up all entries in the accelerator table matching \c Key.
   iterator_range<SameNameIterator> equal_range(StringRef Key) const;
+
+  /// Lookup all entries in the accelerator table.
+  auto entries() const {
+    return make_range(Iterator(*this), Iterator(*this, /*SetEnd*/ true));
+  }
 };
 
 /// .debug_names section consists of one or more units. Each unit starts with a
 /// header, which is followed by a list of compilation units, local and foreign
 /// type units.
 ///
 /// These may be followed by an (optional) hash lookup table, which consists of
 /// an array of buckets and hashes similar to the apple tables above. The only

llvm/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp

if (std::optional<uint64_t> Value = Tag->getAsUnsignedConstant())
     return dwarf::Tag(*Value);
   return std::nullopt;
 }
 
 AppleAcceleratorTable::SameNameIterator::SameNameIterator(
     const AppleAcceleratorTable &AccelTable, uint64_t DataOffset)
     : Current(AccelTable), Offset(DataOffset) {}
 
+void AppleAcceleratorTable::Iterator::prepareNextEntryOrEnd() {
+  if (NumEntriesToCome == 0)
+    prepareNextStringOrEnd();
+  if (isEnd())
+    return;
+  uint64_t OffsetCopy = Offset;
+  Current.BaseEntry.extract(&OffsetCopy);
+  NumEntriesToCome--;
+  Offset += getTable().getHashDataEntryLength();
+}
+
+void AppleAcceleratorTable::Iterator::prepareNextStringOrEnd() {
+  std::optional<uint32_t> StrOffset = getTable().readStringOffsetAt(Offset);
+  if (!StrOffset)
+    return setToEnd();
+
+  // A zero denotes the end of the collision list. Read the next string
+  // again.
+  if (*StrOffset == 0)
+    return prepareNextStringOrEnd();
+  Current.StrOffset = *StrOffset;
+
+  std::optional<uint32_t> MaybeNumEntries = getTable().readU32FromAccel(Offset);
+  if (!MaybeNumEntries || *MaybeNumEntries == 0)
+    return setToEnd();
+  NumEntriesToCome = *MaybeNumEntries;
+}
+
+AppleAcceleratorTable::Iterator::Iterator(const AppleAcceleratorTable &Table,
+                                          bool SetEnd)
+    : Current(Table), Offset(Table.getEntriesBase()), NumEntriesToCome(0) {
+  if (SetEnd)
+    setToEnd();
+  else
+    prepareNextEntryOrEnd();
+}
+
 iterator_range<AppleAcceleratorTable::SameNameIterator>
 AppleAcceleratorTable::equal_range(StringRef Key) const {
   const auto EmptyRange =
       make_range(SameNameIterator(*this, 0), SameNameIterator(*this, 0));
   if (!IsValid)
     return EmptyRange;
 
   // Find the bucket.

llvm/test/DebugInfo/Generic/apple-names-hash-collisions.ll

 ; XFAIL: target={{.*}}-aix{{.*}}
 ; RUN: %llc_dwarf -accel-tables=Apple -filetype=obj -o %t < %s
 ; RUN: llvm-dwarfdump -apple-names %t | FileCheck %s --check-prefix=NUM_HASHES
 ; RUN: llvm-dwarfdump  --find=bb --find=cA %t | FileCheck %s --check-prefix=FOUND_VARS
+; RUN: llvm-dwarfdump  --find-all-apple %t | FileCheck %s --check-prefix=ALL_ENTRIES
 
 
 ; The strings 'bb' and 'cA' hash to the same value under the Apple accelerator
 ; table hashing algorithm.
 ; We first test that there is exactly one bucket and one hash.
 ; Then we check that both values are found.
 
-; NUM_HASHES:      Bucket count: 1
-; NUM_HASHES-NEXT: Hashes count: 1
+; NUM_HASHES:      Bucket count: 2
+; NUM_HASHES-NEXT: Hashes count: 2
 ; FOUND_VARS: DW_AT_name        ("bb")
 ; FOUND_VARS: DW_AT_name        ("cA")
 
+; ALL_ENTRIES: Apple accelerator entries with name = "cA":
+; ALL_ENTRIES: DW_AT_name        ("cA")
+; ALL_ENTRIES: Apple accelerator entries with name = "some_other_hash":
+; ALL_ENTRIES: DW_AT_name        ("some_other_hash")
+; ALL_ENTRIES: Apple accelerator entries with name = "int":
+; ALL_ENTRIES: DW_AT_name        ("int")
+; ALL_ENTRIES: Apple accelerator entries with name = "bb":
+; ALL_ENTRIES: DW_AT_name        ("bb")
+
 @bb = global i32 200, align 4, !dbg !0
 @cA = global i32 10, align 4, !dbg !5
+@some_other_hash = global i32 10, !dbg !17
 
 !llvm.module.flags = !{!9, !10, !11, !12, !13}
 !llvm.dbg.cu = !{!2}
 !llvm.ident = !{!15}
 
 !0 = !DIGlobalVariableExpression(var: !1, expr: !DIExpression())
 !1 = distinct !DIGlobalVariable(name: "bb", scope: !2, file: !3, line: 1, type: !7, isDefinition: true)
 !2 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus_14, file: !3, producer: "", emissionKind: FullDebug, globals: !4)
 !3 = !DIFile(filename: "test.cpp", directory: "blah")
-!4 = !{!0, !5}
+!4 = !{!0, !5, !17}
 !5 = !DIGlobalVariableExpression(var: !6, expr: !DIExpression())
 !6 = distinct !DIGlobalVariable(name: "cA", scope: !2, file: !3, line: 2, type: !7, isLocal: false, isDefinition: true)
 !7 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
 !9 = !{i32 7, !"Dwarf Version", i32 4}
 !10 = !{i32 2, !"Debug Info Version", i32 3}
 !11 = !{i32 1, !"wchar_size", i32 4}
 !12 = !{i32 8, !"PIC Level", i32 2}
 !13 = !{i32 7, !"uwtable", i32 1}
 !15 = !{!"blah"}
+!16 = distinct !DIGlobalVariable(name: "some_other_hash", scope: !2, file: !3, line: 2, type: !7, isLocal: false, isDefinition: true)
+!17 = !DIGlobalVariableExpression(var: !16, expr: !DIExpression())

llvm/tools/llvm-dwarfdump/llvm-dwarfdump.cpp

 //===-- llvm-dwarfdump.cpp - Debug info dumping utility for llvm ----------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This program is a utility that works like "dwarfdump".
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm-dwarfdump.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/DebugInfo/DIContext.h"
 #include "llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h"
 #include "llvm/DebugInfo/DWARF/DWARFCompileUnit.h"
 #include "llvm/DebugInfo/DWARF/DWARFContext.h"
 #include "llvm/MC/MCRegisterInfo.h"
 #include "llvm/MC/TargetRegistry.h"
 #include "llvm/Object/Archive.h"
 #include "llvm/Object/MachOUniversal.h"
 #include "llvm/Object/ObjectFile.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Format.h"
+#include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/InitLLVM.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/Regex.h"
 #include "llvm/Support/TargetSelect.h"
 #include "llvm/Support/ToolOutputFile.h"
 #include "llvm/Support/WithColor.h"
 #include "llvm/Support/raw_ostream.h"
static list<std::string>
     Find("find",
          desc("Search for the exact match for <name> in the accelerator tables "
               "and print the matching debug information entries. When no "
               "accelerator tables are available, the slower but more complete "
               "-name option can be used instead."),
          value_desc("name"), cat(DwarfDumpCategory));
 static alias FindAlias("f", desc("Alias for --find."), aliasopt(Find),
                        cl::NotHidden);
+static opt<bool> FindAllApple(
+    "find-all-apple",
+    desc("Print every debug information entry in the accelerator tables."),
+    cat(DwarfDumpCategory));
 static opt<bool> IgnoreCase("ignore-case",
                             desc("Ignore case distinctions when using --name."),
                             value_desc("i"), cat(DwarfDumpCategory));
 static alias IgnoreCaseAlias("i", desc("Alias for --ignore-case."),
                              aliasopt(IgnoreCase), cl::NotHidden);
 static list<std::string> Name(
     "name",
     desc("Find and print all debug info entries whose name (DW_AT_name "
static void filterByAccelName(
   Dies.erase(std::unique(Dies.begin(), Dies.end()), Dies.end());
 
   DIDumpOptions DumpOpts = getDumpOpts(DICtx);
   DumpOpts.GetNameForDWARFReg = GetNameForDWARFReg;
   for (DWARFDie Die : Dies)
     Die.dump(OS, 0, DumpOpts);
 }
 
+/// Print all DIEs in apple accelerator tables
+static void findAllApple(
+    DWARFContext &DICtx, raw_ostream &OS,
+    std::function<StringRef(uint64_t RegNum, bool IsEH)> GetNameForDWARFReg) {
+  StringMap<llvm::SmallSet<DWARFDie, 2>> NameToDies;
+
+  auto PushDIEs = [&](const AppleAcceleratorTable &Accel) {
+    for (const auto &Entry : Accel.entries()) {
+      if (std::optional<uint64_t> Off = Entry.BaseEntry.getDIESectionOffset()) {
+        std::optional<StringRef> MaybeName = Entry.readName();
+        DWARFDie Die = DICtx.getDIEForOffset(*Off);
+        if (Die && MaybeName)
+          NameToDies[*MaybeName].insert(Die);
+      }
+    }
+  };
+
+  PushDIEs(DICtx.getAppleNames());
+  PushDIEs(DICtx.getAppleNamespaces());
+  PushDIEs(DICtx.getAppleTypes());
+
+  DIDumpOptions DumpOpts = getDumpOpts(DICtx);
+  DumpOpts.GetNameForDWARFReg = GetNameForDWARFReg;
+  for (const auto &[Name, Dies] : NameToDies) {
+    OS << llvm::formatv("\nApple accelerator entries with name = \"{0}\":\n",
+                        Name);
+    for (DWARFDie Die : Dies)
+      Die.dump(OS, 0, DumpOpts);
+  }
+}
+
 /// Handle the --lookup option and dump the DIEs and line info for the given
 /// address.
 /// TODO: specified Address for --lookup option could relate for several
 /// different sections(in case not-linked object file). llvm-dwarfdump
 /// need to do something with this: extend lookup option with section
 /// information or probably display all matched entries, or something else...
 static bool lookup(ObjectFile &Obj, DWARFContext &DICtx, uint64_t Address,
                    raw_ostream &OS) {
static bool dumpObjectFile(ObjectFile &Obj, DWARFContext &DICtx,
   }
 
   // Handle the --find option and lower it to --debug-info=<offset>.
   if (!Find.empty()) {
     filterByAccelName(Find, DICtx, OS, GetRegName);
     return true;
   }
 
+  // Handle the --find-all-apple option and lower it to --debug-info=<offset>.
+  if (FindAllApple) {
+    findAllApple(DICtx, OS, GetRegName);
+    return true;
+  }
+
   // Dump the complete DWARF structure.
   auto DumpOpts = getDumpOpts(DICtx);
   DumpOpts.GetNameForDWARFReg = GetRegName;
   DICtx.dump(OS, DumpOpts, DumpOffsets);
   return true;
 }
 
 static bool verifyObjectFile(ObjectFile &Obj, DWARFContext &DICtx,
if (DumpType == DIDT_Null) {
     if (Verbose)
       DumpType = DIDT_All;
     else
       DumpType = DIDT_DebugInfo;
   }
 
   // Unless dumping a specific DIE, default to --show-children.
   if (!ShowChildren && !Verify && !OffsetRequested && Name.empty() &&
-      Find.empty())
+      Find.empty() && !FindAllApple)
     ShowChildren = true;
 
   // Defaults to a.out if no filenames specified.
   if (InputFilenames.empty())
     InputFilenames.push_back("a.out");
 
   // Expand any .dSYM bundles to the individual object files contained therein.
   std::vector<std::string> Objects;