[NFC] Generalize DwarfAccelTable

[JDevlieghere]

Summary

This patch is an effort to make the DwarfAccelTable more generic so they
can be reused by the dsymutil implementation, where we need to support
different atoms for LLDB:

eAtomTypeTypeFlags = 5u,    // Flags from enum TypeFlags
eAtomTypeQualNameHash = 6u  // A 32 bit hash of the full qualified name

Similar to some patches from Fred in the past, my goal was to make the
DwarfAccelTable generic and the emitted data is actually derived from
the list of atoms passed to its constructor. For this purpose I have
added a callback function to the interface. This callback function can
is used to generate a value for a combination of row (HashDataContents)
and column (Atom).

I believe this approach provides the best trade-off between making the
table more generic while still building on the current, proven
implementation.

As discussed on the mailing list
(http://lists.llvm.org/pipermail/llvm-dev/2018-January/120499.html) we
want to bring DWARFv5 accelerator tables to LLVM. The goal is to share
as much logic as possible between the two implementation. With that in
mind, I believe it's beneficial to have llvm-dsymutil use the current
implementation, as to ensure that the future design supports this use
case down the line.

From the emitted code point of view, the patch is actually NFC, we rely
on the existing tests to prove that the patch doesn't break anything.

[JDevlieghere]

As an alternative to having a callback function it should be trivial to implement this using the a separate DwarfAccelTableInfo class with virtual methods as is common in LLVM. However the current approach requires less code to be changed and follows the same principle.

[aprantl]

lib/CodeGen/AsmPrinter/DwarfAccelTable.cpp

35

Could this be merged with DIEInteger::SizeOf() ?

lib/CodeGen/AsmPrinter/DwarfAccelTable.h

169

Is this code not needed for dwarfdump?

188

  default: return 0;
  }
}

not sure if actually better :-)

242

Would be nice to doxygenify these comments in a separate NFC commit. (no need for a review)

[labath]

lib/CodeGen/AsmPrinter/DwarfAccelTable.h

163

Do we need the HashDataContents struct if it is just a DIE* wrapper? I am not sure if there is anything that we would want to emit that cannot extracted from a DIE pointer by a suitable DataForAtomFunction callback...

[JDevlieghere]

lib/CodeGen/AsmPrinter/DwarfAccelTable.cpp

35

I didn't know about this, sounds like a good idea.

lib/CodeGen/AsmPrinter/DwarfAccelTable.h

163

The struct will become useful when I implement the second part for dsymutil. There we don't have DIEs and want to track just the offsets.

169

What do you mean exactly?

188

From experience I know that gcc used to complain about this with -Wall. I kind of prefer this but I don't have a strong opinion.

242

Indeed. I actually have this commit ready :-)

[aprantl]

lib/CodeGen/AsmPrinter/DwarfAccelTable.h

169

The print function is asserts (!NDEBUG) only; I was wondering if we don't want to print this in llvm-dwarfdump ever.

[JDevlieghere]

lib/CodeGen/AsmPrinter/DwarfAccelTable.h

169

Right. This code doesn't actually read any data so I don't think it would benefit dwarfdump unless we manage to unify this with its counterpart in DebugInfo.

[labath]

lib/CodeGen/AsmPrinter/DwarfAccelTable.h

169

llvm-dwarfdump uses DWARFAcceleratorTable class (which is in no relation to DwarfAccelTable) :P.

[JDevlieghere]

Use DIEInteger::SizeOf()

[JDevlieghere]

Abandoning this in favor of D42334

lib/CodeGen/AsmPrinter/DwarfAccelTable.h

#endif
   // hash and the offsets to the DIEs themselves.
   // On disk each data section is ended with a 0 KeyType as the end of the
   // hash chain.
   // On output this looks like:
   // uint32_t str_offset
   // uint32_t hash_data_count
   // HashData[hash_data_count]
 public:
   struct HashDataContents {
     const DIE *Die;   // Offsets
-    char Flags; // Specific flags to output
 
-    HashDataContents(const DIE *D, char Flags) : Die(D), Flags(Flags) {}
+    HashDataContents(const DIE *D) : Die(D) {}
 
 #ifndef NDEBUG
     void print(raw_ostream &OS) const {
-      OS << "  Offset: " << Die->getOffset() << "\n"
-         << "  Tag: " << dwarf::TagString(Die->getTag()) << "\n"
-         << "  Flags: " << Flags << "\n";
+      OS << "  Offset: " << Die->getOffset() << "\n";
+      OS << "  Tag: " << dwarf::TagString(Die->getTag()) << "\n";
     }
 #endif
   };
 
+  using DataForAtomFunction =
+      std::function<uint64_t(const HashDataContents &, unsigned)>;
+  static uint64_t DefaultGetDataForAtom(const HashDataContents &HDC,
+                                        unsigned AtomIdx) {
+    switch (AtomIdx) {
+    // First atom is a DIE offset.
+    case 0:
+      return HDC.Die->getDebugSectionOffset();
+    // Second atom is a DIE offset.
+    case 1:
+      return HDC.Die->getTag();
+    // Third atom is a flag field that's always zero.
+    case 2:
+      return 0;
+    default:
+      break;
+    }
+    return 0;
+  }
+
 private:
   // String Data
   struct DataArray {
     DwarfStringPoolEntryRef Name;
     std::vector<HashDataContents *> Values;
   };
 
   friend struct HashData;
void print(raw_ostream &OS) {
       OS << "  Hash Value: " << format("0x%x", HashValue) << "\n";
       OS << "  Symbol: ";
       if (Sym)
         OS << *Sym;
       else
         OS << "<none>";
       OS << "\n";
       for (HashDataContents *C : Data.Values) {
-        OS << "  Offset: " << C->Die->getOffset() << "\n";
-        OS << "  Tag: " << dwarf::TagString(C->Die->getTag()) << "\n";
-        OS << "  Flags: " << C->Flags << "\n";
+        C->print(OS);
       }
     }
 
     void dump() { print(dbgs()); }
 #endif
   };
 
   // Internal Functions
   void EmitHeader(AsmPrinter *);
   void EmitBuckets(AsmPrinter *);
   void EmitHashes(AsmPrinter *);
   void emitOffsets(AsmPrinter *, const MCSymbol *);
   void EmitData(AsmPrinter *, DwarfDebug *D);
 
   // Allocator for HashData and HashDataContents.
   BumpPtrAllocator Allocator;
 
   // Output Variables
   TableHeader Header;
   TableHeaderData HeaderData;
   std::vector<HashData *> Data;
 
-  using StringEntries = StringMap<DataArray, BumpPtrAllocator &>;
+  DataForAtomFunction DataForAtom;
 
+  using StringEntries = StringMap<DataArray, BumpPtrAllocator &>;
   StringEntries Entries;
 
-  // Buckets/Hashes/Offsets
   using HashList = std::vector<HashData *>;
+  HashList Hashes;
+
   using BucketList = std::vector<HashList>;
   BucketList Buckets;
-  HashList Hashes;
 
   // Public Implementation
 public:
-  DwarfAccelTable(ArrayRef<DwarfAccelTable::Atom>);
+  DwarfAccelTable(ArrayRef<DwarfAccelTable::Atom>,
+                  DataForAtomFunction DataForAtom = DefaultGetDataForAtom);
   DwarfAccelTable(const DwarfAccelTable &) = delete;
   DwarfAccelTable &operator=(const DwarfAccelTable &) = delete;
 
-  void AddName(DwarfStringPoolEntryRef Name, const DIE *Die, char Flags = 0);
+  void AddName(DwarfStringPoolEntryRef Name, const DIE *Die);
   void FinalizeTable(AsmPrinter *, StringRef);
   void emit(AsmPrinter *, const MCSymbol *, DwarfDebug *);
+
 #ifndef NDEBUG
   void print(raw_ostream &OS);
   void dump() { print(dbgs()); }
 #endif
 };
 
 } // end namespace llvm
 
 #endif // LLVM_LIB_CODEGEN_ASMPRINTER_DWARFACCELTABLE_H

lib/CodeGen/AsmPrinter/DwarfAccelTable.cpp

 #include <cstddef>
 #include <cstdint>
 #include <iterator>
 #include <limits>
 #include <vector>
 
 using namespace llvm;
 
+/// Return the size (in bytes) for the given Form.
+static unsigned GetSizeForForm(uint16_t Form) {
+  switch (Form) {
+  case dwarf::DW_FORM_data1:
+    return 1;
+  case dwarf::DW_FORM_data2:
+    return 2;
+  case dwarf::DW_FORM_data4:
+    return 4;
+  case dwarf::DW_FORM_data8:
+    return 8;
+  default:
+    llvm_unreachable("Unsupported atom type");
+  }
+}
+
 // The length of the header data is always going to be 4 + 4 + 4*NumAtoms.
-DwarfAccelTable::DwarfAccelTable(ArrayRef<DwarfAccelTable::Atom> atomList)
-    : Header(8 + (atomList.size() * 4)), HeaderData(atomList),
-      Entries(Allocator) {}
+DwarfAccelTable::DwarfAccelTable(ArrayRef<DwarfAccelTable::Atom> AtomList,
+                                 DataForAtomFunction DataForAtom)
+    : Header(8 + (AtomList.size() * 4)), HeaderData(AtomList),
+      DataForAtom(std::move(DataForAtom)), Entries(Allocator) {}
 
-void DwarfAccelTable::AddName(DwarfStringPoolEntryRef Name, const DIE *die,
-                              char Flags) {
+void DwarfAccelTable::AddName(DwarfStringPoolEntryRef Name, const DIE *die) {
   assert(Data.empty() && "Already finalized!");
   // If the string is in the list already then add this die to the list
   // otherwise add a new one.
   DataArray &DIEs = Entries[Name.getString()];
   assert(!DIEs.Name || DIEs.Name == Name);
   DIEs.Name = Name;
-  DIEs.Values.push_back(new (Allocator) HashDataContents(die, Flags));
+  DIEs.Values.push_back(new (Allocator) HashDataContents(die));
 }
 
 void DwarfAccelTable::ComputeBucketCount() {
   // First get the number of unique hashes.
   std::vector<uint32_t> uniques(Data.size());
   for (size_t i = 0, e = Data.size(); i < e; ++i)
     uniques[i] = Data[i]->HashValue;
   array_pod_sort(uniques.begin(), uniques.end());
   std::vector<uint32_t>::iterator p =
       std::unique(uniques.begin(), uniques.end());
   uint32_t num = std::distance(uniques.begin(), p);
 
   // Then compute the bucket size, minimum of 1 bucket.
   if (num > 1024)
     Header.bucket_count = num / 4;
   else if (num > 16)
     Header.bucket_count = num / 2;
   else
     Header.bucket_count = num > 0 ? num : 1;
 
   Header.hashes_count = num;
 }
 
-// compareDIEs - comparison predicate that sorts DIEs by their offset.
+/// Comparison predicate that sorts DIEs by their offset.
 static bool compareDIEs(const DwarfAccelTable::HashDataContents *A,
                         const DwarfAccelTable::HashDataContents *B) {
   return A->Die->getOffset() < B->Die->getOffset();
 }
 
 void DwarfAccelTable::FinalizeTable(AsmPrinter *Asm, StringRef Prefix) {
   // Create the individual hash data outputs.
   Data.reserve(Entries.size());
for (HashList::const_iterator HI = Buckets[i].begin(),
         Asm->EmitInt32(0);
       // Remember to emit the label for our offset.
       Asm->OutStreamer->EmitLabel((*HI)->Sym);
       Asm->OutStreamer->AddComment((*HI)->Str);
       Asm->emitDwarfStringOffset((*HI)->Data.Name);
       Asm->OutStreamer->AddComment("Num DIEs");
       Asm->EmitInt32((*HI)->Data.Values.size());
       for (HashDataContents *HD : (*HI)->Data.Values) {
-        // Emit the DIE offset
-        Asm->EmitInt32(HD->Die->getDebugSectionOffset());
-        // If we have multiple Atoms emit that info too.
-        // FIXME: A bit of a hack, we either emit only one atom or all info.
-        if (HeaderData.Atoms.size() > 1) {
-          Asm->EmitInt16(HD->Die->getTag());
-          Asm->EmitInt8(HD->Flags);
+        // Emit data for Atoms.
+        unsigned AtomIdx = 0;
+        for (auto Atom : HeaderData.Atoms) {
+          Asm->OutStreamer->EmitIntValue(DataForAtom(*HD, AtomIdx),
+                                         GetSizeForForm(Atom.form));
+          AtomIdx++;
         }
       }
       PrevHash = (*HI)->HashValue;
     }
     // Emit the final end marker for the bucket.
     if (!Buckets[i].empty())
       Asm->EmitInt32(0);
   }