DwarfAccelTable: Make Dwarf accelerator table generic.

[friss]

Summary

Today, the fields dumped in the accelerator tables are hardcoded to
the 2 variants that LLVM produces. llvm-dsymutil would like to reuse
that code, but needs to ouptut another variant.

This patch makes the DwarfAccelTable generic and the emitted data
is actually derived from the list of atoms passed to its constructor.
In order not to waste memory (this structure can grow very big on
huge programs), it allocates memory for the atom contents right
after the HashDataContents struct and uses memcpy to access them.

The only hardcoded thing is that the first atom must be a DIE offset.
has the table is always used as a map from name to DIEs, this makes
sense.

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

[echristo]

What other variant are you going to output? We did recently standardize a new (but closely related) variant as part of DWARF5.

-eric

[friss]

Hadn't seen your message, sorry for the delay in replying. It turns out lldb uses different atoms (as produced by dsymutil) than the one we currently hardcode. The only table having additional atoms is the types table. In addition to the DIE offset, LLVM emits:

• DW_ATOM_die_tag = 3u // A tag entry.
• DW_ATOM_type_flags = 4u // Set of flags for a type.

The type flags are always hardcoded to 0 (I plan to remove this field as it serves no purpose). LLDB on the other hand has these atoms definition:

• eAtomTypeTag = 3u, // DW_TAG_xxx value,
• eAtomTypeNameFlags = 4u, // Flags from enum NameFlags
• eAtomTypeTypeFlags = 5u, // Flags from enum TypeFlags
• eAtomTypeQualNameHash = 6u // A 32 bit hash of the full qualified name

And it actually doesn't use TypeNameFlags. but it uses the last 2.

I'm wondering if Adrian hasn't planed a new use of an accelerator table that would require yet another variant of atom combinations for his module debugging work.

[aprantl]

Ping?

[echristo]

Adding the atoms explicitly in DwarfDebug is a little weird rather than just setting the format when you create the tables. Any reason why you want to do it there?

-eric

[echristo]

(Honestly it's probably fine either way, but I'd like the question answered first if it's not too much of a problem. Thanks!)

-eric

lib/CodeGen/AsmPrinter/DwarfAccelTable.h

#endif
   // 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) {}
-#ifndef NDEBUG
-    void print(raw_ostream &O) const {
-      O << "  Offset: " << Die->getOffset() << "\n";
-      O << "  Tag: " << dwarf::TagString(Die->getTag()) << "\n";
-      O << "  Flags: " << Flags << "\n";
+    HashDataContents(const DIE *D) : Die(D) {}
+
+    /// \brief Get the start of the Atom storage.
+    /// Atoms are stored right after the HashDataContents object in memory.
+    char *getAtomData() const {
+      return (char *)(void *)(this + 1);
+    }
+
+    /// \brief Get the atom of type AtomT at \p Offset in the Atom data.
+    template<typename AtomT>
+    AtomT getAtom(unsigned int Offset) const {
+      AtomT Atom;
+      memcpy(&Atom, getAtomData() + Offset, sizeof(AtomT));
+      return Atom;
     }
+
+#ifndef NDEBUG
+    void print(raw_ostream &O,
+               const DwarfAccelTable::TableHeaderData &Header) const;
 #endif
   };
   
+  class HashDataContentsRef {
+    const HashDataContents &Contents; ///< The entry we are populating
+    const DwarfAccelTable &Table; ///< The table that owns us
+    uint16_t AtomBytePos; ///< Byte position of the next Atom
+    uint8_t AtomPos; ///< Index of the next Atom
+    
+  public:
+    HashDataContentsRef(HashDataContents &Contents, DwarfAccelTable &Table)
+      : Contents(Contents), Table(Table), AtomBytePos(0), AtomPos(1) {}
+    
+    template<typename AtomT>
+    HashDataContentsRef addAtom(AtomT Atom) {
+      assert(AtomBytePos + sizeof(AtomT) <= Table.getAtomsSize());
+      assert(Table.checkAtomSize(AtomPos, sizeof(AtomT)));
+      memcpy(Contents.getAtomData() + AtomBytePos, &Atom, sizeof(AtomT));
+      ++AtomPos;
+      AtomBytePos += sizeof(AtomT);
+      return *this;
+    }
+  };
+
 private:
   // String Data
   struct DataArray {
     MCSymbol *StrSym;
     std::vector<HashDataContents *> Values;
     DataArray() : StrSym(nullptr) {}
   };
   friend struct HashData;
   struct HashData {
     StringRef Str;
     uint32_t HashValue;
     MCSymbol *Sym;
     DwarfAccelTable::DataArray &Data; // offsets
     HashData(StringRef S, DwarfAccelTable::DataArray &Data)
         : Str(S), Data(Data) {
       HashValue = DwarfAccelTable::HashDJB(S);
     }
 #ifndef NDEBUG
-    void print(raw_ostream &O) {
+    void print(raw_ostream &O, TableHeaderData& Atoms) {
       O << "Name: " << Str << "\n";
       O << "  Hash Value: " << format("0x%x", HashValue) << "\n";
       O << "  Symbol: ";
       if (Sym)
         Sym->print(O);
       else
         O << "<none>";
       O << "\n";
-      for (HashDataContents *C : Data.Values) {
-        O << "  Offset: " << C->Die->getOffset() << "\n";
-        O << "  Tag: " << dwarf::TagString(C->Die->getTag()) << "\n";
-        O << "  Flags: " << C->Flags << "\n";
-      }
+      for (HashDataContents *C : Data.Values)
+        C->print(O, Atoms);
     }
-    void dump() { print(dbgs()); }
+    void dump(TableHeaderData& Atoms) { print(dbgs(), Atoms); }
 #endif
   };
 
   DwarfAccelTable(const DwarfAccelTable &) = delete;
   void operator=(const DwarfAccelTable &) = delete;
 
   // Internal Functions
   void EmitHeader(AsmPrinter *);
#endif
   typedef StringMap<DataArray, BumpPtrAllocator &> StringEntries;
   StringEntries Entries;
 
   // Buckets/Hashes/Offsets
   typedef std::vector<HashData *> HashList;
   typedef std::vector<HashList> BucketList;
   BucketList Buckets;
   HashList Hashes;
+  unsigned AtomsSize;
 
   // Public Implementation
 public:
   DwarfAccelTable(ArrayRef<DwarfAccelTable::Atom>);
-  void AddName(StringRef Name, MCSymbol *StrSym, const DIE *Die,
-               char Flags = 0);
+  HashDataContentsRef AddName(StringRef Name, MCSymbol *StrSym, const DIE *Die);
   void FinalizeTable(AsmPrinter *, StringRef);
   void Emit(AsmPrinter *, MCSymbol *, DwarfDebug *, MCSymbol *StrSym);
+  unsigned getAtomsSize() const { return AtomsSize; }
 #ifndef NDEBUG
+  bool checkAtomSize(unsigned Index, unsigned ByteSize) const;
   void print(raw_ostream &O);
   void dump() { print(dbgs()); }
 #endif
 };
 }
 #endif

lib/CodeGen/AsmPrinter/DwarfAccelTable.cpp

 #include "llvm/CodeGen/DIE.h"
 #include "llvm/MC/MCExpr.h"
 #include "llvm/MC/MCStreamer.h"
 #include "llvm/MC/MCSymbol.h"
 #include "llvm/Support/Debug.h"
 
 using namespace llvm;
 
+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) {}
+      Entries(Allocator), AtomsSize(0) {
+  assert(atomList[0].type == dwarf::DW_ATOM_die_offset &&
+         atomList[0].form == dwarf::DW_FORM_data4);
+  for (const auto &Atom : atomList.slice(1))
+    AtomsSize += getSizeForForm(Atom.form);
+}
 
-void DwarfAccelTable::AddName(StringRef Name, MCSymbol *StrSym, const DIE *die,
-                              char Flags) {
+#ifndef NDEBUG
+bool DwarfAccelTable::checkAtomSize(unsigned Index, unsigned ByteSize) const {
+  if (Index >= HeaderData.Atoms.size())
+    return false;
+  return getSizeForForm(HeaderData.Atoms[Index].form) == ByteSize;
+}
+#endif
+
+DwarfAccelTable::HashDataContentsRef
+DwarfAccelTable::AddName(StringRef Name, MCSymbol *StrSym, 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];
   assert(!DIEs.StrSym || DIEs.StrSym == StrSym);
   DIEs.StrSym = StrSym;
-  DIEs.Values.push_back(new (Allocator) HashDataContents(die, Flags));
+  void *HashDataMem = Allocator.Allocate(sizeof(HashDataContents) + AtomsSize,
+                                         alignof(HashDataContents));
+  auto *HD = new (HashDataMem) HashDataContents(die);
+  DIEs.Values.push_back(HD);
+  return HashDataContentsRef(*HD, *this);
 }
 
 void DwarfAccelTable::ComputeBucketCount(void) {
   // 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());
for (HashList::const_iterator HI = Buckets[i].begin(),
       Asm->OutStreamer.AddComment("Num DIEs");
       Asm->EmitInt32((*HI)->Data.Values.size());
       for (HashDataContents *HD : (*HI)->Data.Values) {
         // Emit the DIE offset
         DwarfCompileUnit *CU = D->lookupUnit(HD->Die->getUnit());
         assert(CU && "Accelerated DIE should belong to a CU.");
         Asm->EmitInt32(HD->Die->getOffset() + CU->getDebugInfoOffset());
         // 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);
+        unsigned AtomOffset = 0;
+        for (const auto &Atom : makeArrayRef(HeaderData.Atoms.data() + 1,
+                                             HeaderData.Atoms.size() - 1)) {
+          switch (Atom.form) {
+          case dwarf::DW_FORM_data1:
+            Asm->EmitInt8(HD->getAtom<uint8_t>(AtomOffset));
+            AtomOffset += 1;
+            break;
+          case dwarf::DW_FORM_data2:
+            Asm->EmitInt16(HD->getAtom<uint16_t>(AtomOffset));
+            AtomOffset += 2;
+            break;
+          case dwarf::DW_FORM_data4:
+            Asm->EmitInt32(HD->getAtom<uint32_t>(AtomOffset));
+            AtomOffset += 4;
+            break;
+          case dwarf::DW_FORM_data8:
+            Asm->OutStreamer.EmitIntValue(HD->getAtom<uint64_t>(AtomOffset), 8);
+            AtomOffset += 8;
+            break;
+          }
         }
       }
       PrevHash = (*HI)->HashValue;
     }
     // Emit the final end marker for the bucket.
     if (!Buckets[i].empty())
       Asm->EmitInt32(0);
   }
void DwarfAccelTable::print(raw_ostream &O) {
   HeaderData.print(O);
 
   O << "Entries: \n";
   for (StringMap<DataArray>::const_iterator EI = Entries.begin(),
                                             EE = Entries.end();
        EI != EE; ++EI) {
     O << "Name: " << EI->getKeyData() << "\n";
     for (HashDataContents *HD : EI->second.Values)
-      HD->print(O);
+      HD->print(O, HeaderData);
   }
 
   O << "Buckets and Hashes: \n";
   for (size_t i = 0, e = Buckets.size(); i < e; ++i)
     for (HashList::const_iterator HI = Buckets[i].begin(),
                                   HE = Buckets[i].end();
          HI != HE; ++HI)
-      (*HI)->print(O);
+      (*HI)->print(O, HeaderData);
 
   O << "Data: \n";
   for (std::vector<HashData *>::const_iterator DI = Data.begin(),
                                                DE = Data.end();
        DI != DE; ++DI)
-    (*DI)->print(O);
+    (*DI)->print(O, HeaderData);
+}
+
+void DwarfAccelTable::HashDataContents::print(
+    raw_ostream &O, const DwarfAccelTable::TableHeaderData &Header) const {
+  O << "  Offset: " << Die->getOffset() << "\n";
+  O << "  Tag: " << dwarf::TagString(Die->getTag()) << "\n";
+  unsigned Offset = 0;
+  unsigned Idx = 0;
+  assert(!Header.Atoms.empty());
+  for (const auto &Atom : make_range(Header.Atoms.begin()+1,
+                                     Header.Atoms.end())) {
+    O << "  Atom[" << Idx++ << "]: type " << Atom.type << " value: ";
+    switch (getSizeForForm(Atom.form)) {
+    case 1:
+      format("0x%02x\n", (int)getAtom<uint8_t>(Offset));
+      Offset += 1;
+      break;
+    case 2:
+      format("0x%04x\n", getAtom<uint16_t>(Offset));
+      Offset += 2;
+      break;
+    case 4:
+      format("0x%08x\n", getAtom<uint32_t>(Offset));
+      Offset += 4;
+      break;
+    case 8:
+      format("0x%016" PRIx64 "\n", getAtom<uint64_t>(Offset));
+      Offset += 2;
+      break;
+    }
+  }    
 }
 #endif

lib/CodeGen/AsmPrinter/DwarfDebug.cpp

void DwarfDebug::addAccelNamespace(StringRef Name, const DIE &Die) {
   AccelNamespace.AddName(Name, InfoHolder.getStringPool().getSymbol(*Asm, Name),
                          &Die);
 }
 
 void DwarfDebug::addAccelType(StringRef Name, const DIE &Die, char Flags) {
   if (!useDwarfAccelTables())
     return;
   AccelTypes.AddName(Name, InfoHolder.getStringPool().getSymbol(*Asm, Name),
-                     &Die);
+                     &Die).addAtom<uint16_t>(Die.getTag()).addAtom<uint8_t>(0);
 }