DwarfAccelTable: Enable use of static offsets instead of DIEs and string symbols.

[friss]

Summary

llvm-dsymutil doesn't keep DIE objects once it has handled an object,
but the accelerator tables are global and thus are emitted at the end
of the link. The current scheme of using pointers to DIEs can't work
for llvm-dsymutil. llvm-dsymutil however knows the offset a DIE will
be placed at right upon creation though.

Similarly for the string table, llvm-dsymutil doesn't generate MCSymbols
for it, becasue it doesn't need any relocation.

This patch adds 2 knobs to the DwarfAccelTable to be able to use raw
offsets for DIEs and strings, so that it can be used by producers
like llvm-dsymutil.

I separated the knobs for strings and DIEs, as I have another patch
in my backlog that would prevent the creation of MCSymbols for strings
in MachO files (the linker doesn't care about relocations in debug info,
thus there is no point in using a lot of memeory to generate those).
When/If this patch gets applied, it will use a mix of string offset
and DIE objects.

[echristo]

Not a huge fan, but I don't have any options that aren't some ridiculous amount of work here so go ahead.

Also, you have one occurrence of DIe in your patch. :)

-eric

[Eugene.Zelenko]

Looks like patch was not committed.

lib/CodeGen/AsmPrinter/DwarfAccelTable.h

#endif
   // 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
-
+    union {
+      const DIE *Die; ///< The DIE. 
+      uint32_t DieOffset; ///< Offset of the DIE in debug_info.
+    };
     HashDataContents(const DIE *D) : Die(D) {}
+    HashDataContents(uint32_t Offset) : DieOffset(Offset) {}
 
     /// \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;
+    void print(raw_ostream &O, const DwarfAccelTable &Table) 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
HashDataContentsRef addAtom(AtomT Atom) {
       AtomBytePos += sizeof(AtomT);
       return *this;
     }
   };
 
 private:
   // String Data
   struct DataArray {
-    MCSymbol *StrSym;
+    union {
+      MCSymbol *StrSym; ///< Symbol of the string in debug_str.
+      uint32_t StrOffset; ///<Offset of the string in debug_str.
+    };
     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, TableHeaderData& Atoms) {
+    void print(raw_ostream &O, DwarfAccelTable& Table) {
       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)
-        C->print(O, Atoms);
+        C->print(O, Table);
     }
-    void dump(TableHeaderData& Atoms) { print(dbgs(), Atoms); }
+    void dump(DwarfAccelTable& Table) { print(dbgs(), Table); }
 #endif
   };
 
   DwarfAccelTable(const DwarfAccelTable &) = delete;
   void operator=(const DwarfAccelTable &) = delete;
 
   // Internal Functions
   void EmitHeader(AsmPrinter *);
#endif
   StringEntries Entries;
 
   // Buckets/Hashes/Offsets
   typedef std::vector<HashData *> HashList;
   typedef std::vector<HashList> BucketList;
   BucketList Buckets;
   HashList Hashes;
   unsigned AtomsSize;
+  bool UseDieOffsets;
+  bool UseStringOffsets;
   
   // Public Implementation
 public:
-  DwarfAccelTable(ArrayRef<DwarfAccelTable::Atom>);
+  DwarfAccelTable(ArrayRef<DwarfAccelTable::Atom>, bool UseDieOffset = false,
+                  bool UseStringOffsets = false);
   HashDataContentsRef AddName(StringRef Name, MCSymbol *StrSym, const DIE *Die);
+  HashDataContentsRef AddName(StringRef Name, uint32_t StrOffset,
+                              uint32_t DIeOffset);
   void FinalizeTable(AsmPrinter *, StringRef);
   void Emit(AsmPrinter *, MCSymbol *, DwarfDebug *, MCSymbol *StrSym);
   unsigned getAtomsSize() const { return AtomsSize; }
+  bool useDieOffssets() const { return UseDieOffsets; }
+  bool useStringOffssets() const { return UseStringOffsets; }
+  const TableHeaderData &getHeaderData() const { return HeaderData; }
 #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

static unsigned getSizeForForm(uint16_t Form) {
   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)
+DwarfAccelTable::DwarfAccelTable(ArrayRef<DwarfAccelTable::Atom> atomList,
+                                 bool UseDieOffsets, bool UseStringOffsets)
     : Header(8 + (atomList.size() * 4)), HeaderData(atomList),
-      Entries(Allocator), AtomsSize(0) {
+      Entries(Allocator), AtomsSize(0), UseDieOffsets(UseDieOffsets),
+      UseStringOffsets(UseStringOffsets) {
   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);
 }
 
 #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!");
+  assert(!UseDieOffsets && "Mismatch between AddName and mode.");
+  assert(!UseStringOffsets && "Mismatch between AddName and mode.");
   // 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;
   void *HashDataMem = Allocator.Allocate(sizeof(HashDataContents) + AtomsSize,
                                          alignof(HashDataContents));
   auto *HD = new (HashDataMem) HashDataContents(die);
   DIEs.Values.push_back(HD);
   return HashDataContentsRef(*HD, *this);
 }
 
+DwarfAccelTable::HashDataContentsRef
+DwarfAccelTable::AddName(StringRef Name, uint32_t StrOffset, uint32_t Offset) {
+  assert(Data.empty() && "Already finalized!");
+  assert(UseDieOffsets && "Mismatch between AddName and mode.");
+  assert(UseStringOffsets && "Mismatch between AddName and mode.");
+  // 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.Values.empty() || DIEs.StrOffset == StrOffset);
+  DIEs.StrOffset = StrOffset;
+  void *HashDataMem = Allocator.Allocate(sizeof(HashDataContents) + AtomsSize,
+                                         alignof(HashDataContents));
+  auto *HD = new (HashDataMem) HashDataContents(Offset);
+  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());
   std::vector<uint32_t>::iterator p =
       std::unique(uniques.begin(), uniques.end());

 }
 
 // compareDIEs - 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();
 }
 
+// \brief Compare DIE offsets. Table must be in useDieOffsets mode.
+static bool compareOffsets(const DwarfAccelTable::HashDataContents *A,
+                           const DwarfAccelTable::HashDataContents *B) {
+  return A->DieOffset < B->DieOffset;
+}
+
 void DwarfAccelTable::FinalizeTable(AsmPrinter *Asm, StringRef Prefix) {
   // Create the individual hash data outputs.
   Data.reserve(Entries.size());
   for (StringMap<DataArray>::iterator EI = Entries.begin(), EE = Entries.end();
        EI != EE; ++EI) {
 
     // Unique the entries.
-    std::stable_sort(EI->second.Values.begin(), EI->second.Values.end(), compareDIEs);
+    auto *Comparator = UseDieOffsets ? compareOffsets : compareDIEs;
+    std::stable_sort(EI->second.Values.begin(), EI->second.Values.end(), Comparator);
     EI->second.Values.erase(
         std::unique(EI->second.Values.begin(), EI->second.Values.end()),
         EI->second.Values.end());
 
     HashData *Entry = new (Allocator) HashData(EI->getKey(), EI->second);
     Data.push_back(Entry);
   }
 
void DwarfAccelTable::EmitOffsets(AsmPrinter *Asm, MCSymbol *SecBegin) {
   }
 }
 
 // Walk through the buckets and emit the full data for each element in
 // the bucket. For the string case emit the dies and the various offsets.
 // Terminate each HashData bucket with 0.
 void DwarfAccelTable::EmitData(AsmPrinter *Asm, DwarfDebug *D,
                                MCSymbol *StrSym) {
+  assert(!(UseStringOffsets && StrSym));
+  assert(!(UseDieOffsets && D));
   for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
     uint64_t PrevHash = UINT64_MAX;
     for (HashList::const_iterator HI = Buckets[i].begin(),
                                   HE = Buckets[i].end();
          HI != HE; ++HI) {
       // Terminate the previous entry if there is no hash collision
       // with the current one.
       if (PrevHash != UINT64_MAX && PrevHash != (*HI)->HashValue)
         Asm->EmitInt32(0);
       // Remember to emit the label for our offset.
       Asm->OutStreamer.EmitLabel((*HI)->Sym);
       Asm->OutStreamer.AddComment((*HI)->Str);
+      if (UseStringOffsets)
+        Asm->EmitInt32((*HI)->Data.StrOffset);
+      else
         Asm->EmitSectionOffset((*HI)->Data.StrSym, StrSym);
       Asm->OutStreamer.AddComment("Num DIEs");
       Asm->EmitInt32((*HI)->Data.Values.size());
       for (HashDataContents *HD : (*HI)->Data.Values) {
         // Emit the DIE offset
+        uint32_t Offset;
+        if (UseDieOffsets) {
+          Offset = HD->DieOffset;
+        } else {
           DwarfCompileUnit *CU = D->lookupUnit(HD->Die->getUnit());
           assert(CU && "Accelerated DIE should belong to a CU.");
-        Asm->EmitInt32(HD->Die->getOffset() + CU->getDebugInfoOffset());
+          Offset = HD->Die->getOffset() + CU->getDebugInfoOffset();
+        }
+        Asm->EmitInt32(Offset);
         // If we have multiple Atoms emit that info too.
         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;
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, HeaderData);
+      HD->print(O, *this);
   }
 
   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, HeaderData);
+      (*HI)->print(O, *this);
 
   O << "Data: \n";
   for (std::vector<HashData *>::const_iterator DI = Data.begin(),
                                                DE = Data.end();
        DI != DE; ++DI)
-    (*DI)->print(O, HeaderData);
+    (*DI)->print(O, *this);
 }
 
 void DwarfAccelTable::HashDataContents::print(
-    raw_ostream &O, const DwarfAccelTable::TableHeaderData &Header) const {
+    raw_ostream &O, const DwarfAccelTable &Table) 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())) {
+  assert(!Table.getHeaderData().Atoms.empty());
+  for (const auto &Atom : make_range(Table.getHeaderData().Atoms.begin()+1,
+                                     Table.getHeaderData().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));