Make DwarfAccelTable customizable. NFC.

[friss]

Summary

Make DwarfAccelTable customizable. NFC.

I sent a couple of patches out a couple of month ago to basically achieve
the same thing in a more convoluted way (by having one class trying to
handle all possible cases).

Instead of making the API of the class fully generic (which makes the
code a mess), allow customization of the accelerator table by:

• basing its behavior on a virtual class defining the type of the ATOMs it stores (the HashDataContents class).
• Making it a base class that needs to be derived to provide the right factory functions for the content.

This NFC patch only provide on derived type DIEDwarfAccelTable with 2
variants (one describing types that dumps the additinal field).
llvm-dsymutil can use this to create tables that contain raw DIE offsets
instead of DIE pointers, and Adrian has a use where he store strings
instead of DIEs.

The HashDataContents gains a virtual pointer, but stays the same size
as I dropped an unused field. We can move the virtual inheritance to
the DwarfAccelTable itself in a followup, but this would be more code
(and thus harder to review) as it requires that the generic code iterates
over a vector of opaque data rather than the handy HashDataContents *.

[friss]

Try to include only the relevant change in the Phad revision this time...

[friss]

Sorry about the mess with the diff/revision title. My topic branch had one more uncommitted change when I ran "arc diff" and I wasn't careful enough while reading the text...

[echristo]

I'd think there's something in the middle here. The code is a bit of a hack originally and this cleans up some, but makes some of it a bit worse. I'm not quite sure where you're going with it, ideally we should be able to base everything here off of the atoms in the stack that this uses. Could we do that? (Mostly throwing out ideas here...).

-eric

[friss]

I have this revision lying around where the code is driven by what's in the atom list:
http://reviews.llvm.org/D8215 (it's based on this other one http://reviews.llvm.org/D8216 that you ack'd but that I didn't commit as it doesn't make much sense without the former)

I find this approach clearer. Rather than adding a special case for storing DIE offsets instead of DIE pointers, I'll just derive a new table type.

As I mentioned, Adrian has a use that create a totally different table without even DIEs. He's still pondering if he wants to upstream that or do it differently, but this one would make the code even uglier with other special cases.

[echristo]

Sorry for the delay. The idea behind the current implementation is to be able to derive it from the atom list. I guess if we just want "variant" tables we could instead just instantiate the type of table we'd like for the output information and just store "things we'd like to put into the table" in the intermediate state as we're constructing DIEs?

-eric

[friss]

In D11805#238845, @echristo wrote:

Sorry for the delay. The idea behind the current implementation is to be able to derive it from the atom list. I guess if we just want "variant" tables we could instead just instantiate the type of table we'd like for the output information and just store "things we'd like to put into the table" in the intermediate state as we're constructing DIEs?

I was just going to ping you about this, it's really blocking me right now. Not sure I get what you mean exactly. Care to elaborate on a concrete example? The one I have to handle right now is that I can't store DIE pointers in the table because my DIE objects go away before we emit the table, thus I have to store raw DIE offsets instead. I can do that by adding a config boolean to the table and making the DIE* a union with the offset. Is that what you mean?

When doing this the data emission part of the code gets a bit ugly because it has to handle all the different cases. I had that implemented internally, but we had an additional change by Adrian that made it really too ugly to live. I think that last change is not necessary anymore, so I could definitely implement it this way if it's ok with you. (This is basically what was proposed in http://reviews.llvm.org/D8215 + http://reviews.llvm.org/D8216 if you wanna get a feel of what it looks like. I'd need to update these to current master)

[echristo]

In D11805#238925, @friss wrote:

In D11805#238845, @echristo wrote:

Sorry for the delay. The idea behind the current implementation is to be able to derive it from the atom list. I guess if we just want "variant" tables we could instead just instantiate the type of table we'd like for the output information and just store "things we'd like to put into the table" in the intermediate state as we're constructing DIEs?

I was just going to ping you about this, it's really blocking me right now. Not sure I get what you mean exactly. Care to elaborate on a concrete example? The one I have to handle right now is that I can't store DIE pointers in the table because my DIE objects go away before we emit the table, thus I have to store raw DIE offsets instead. I can do that by adding a config boolean to the table and making the DIE* a union with the offset. Is that what you mean?

I hadn't thought through that detail when I sent my response, but it seems reasonable. Maybe a union of "things we'll use in the table" sort of thing and then use that as the target for the vector?

union TableEntry {

DIE *Entry;
uint64_t offset;
...

}

and keep track via the atom list what things we think we've actually got and access that way?

Am I crazy in thinking this seems good?

-eric

When doing this the data emission part of the code gets a bit ugly because it has to handle all the different cases. I had that implemented internally, but we had an additional change by Adrian that made it really too ugly to live. I think that last change is not necessary anymore, so I could definitely implement it this way if it's ok with you. (This is basically what was proposed in http://reviews.llvm.org/D8215 + http://reviews.llvm.org/D8216 if you wanna get a feel of what it looks like. I'd need to update these to current master)

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
-    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";
-    }
-#endif
+    virtual void emit(AsmPrinter *Asm, DwarfDebug *D) const = 0;
+    virtual bool less(const HashDataContents *Other) const = 0;
+    virtual void print(raw_ostream &OS) const = 0;
+    virtual ~HashDataContents();
   };
 
-private:
+protected:
   // String Data
   struct DataArray {
     DwarfStringPoolEntryRef Name;
     std::vector<HashDataContents *> Values;
   };
   friend struct HashData;
   struct HashData {
     StringRef Str;
void print(raw_ostream &O) {
       O << "Name: " << Str << "\n";
       O << "  Hash Value: " << format("0x%x", HashValue) << "\n";
       O << "  Symbol: ";
       if (Sym)
         O << *Sym;
       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 (auto *C : Data.Values)
+        C->print(O);
     }
     void dump() { print(dbgs()); }
 #endif
   };
 
   DwarfAccelTable(const DwarfAccelTable &) = delete;
   void operator=(const DwarfAccelTable &) = delete;
 
   // Internal Functions
   void EmitHeader(AsmPrinter *);
   void EmitBuckets(AsmPrinter *);
   void EmitHashes(AsmPrinter *);
   void emitOffsets(AsmPrinter *, const MCSymbol *);
   void EmitData(AsmPrinter *, DwarfDebug *D);
 
+protected:
   // Allocator for HashData and HashDataContents.
   BumpPtrAllocator Allocator;
 
   // Output Variables
   TableHeader Header;
   TableHeaderData HeaderData;
   std::vector<HashData *> Data;
 
+  // This map needs to be filled by subclasses.
   typedef StringMap<DataArray, BumpPtrAllocator &> StringEntries;
   StringEntries Entries;
 
   // Buckets/Hashes/Offsets
   typedef std::vector<HashData *> HashList;
   typedef std::vector<HashList> BucketList;
   BucketList Buckets;
   HashList Hashes;
 
-  // Public Implementation
-public:
   DwarfAccelTable(ArrayRef<DwarfAccelTable::Atom>);
-  void AddName(DwarfStringPoolEntryRef Name, const DIE *Die, char Flags = 0);
+
+public:
   void FinalizeTable(AsmPrinter *, StringRef);
   void emit(AsmPrinter *, const MCSymbol *, DwarfDebug *);
 #ifndef NDEBUG
   void print(raw_ostream &O);
   void dump() { print(dbgs()); }
 #endif
 };
+
+class DIEDwarfAccelTable : public DwarfAccelTable {
+  bool IsType;
+
+public:
+  /// Construct a DIE accelerator table. \p IsType is true if it will
+  /// be emitted as a type accelerator table.
+  DIEDwarfAccelTable(bool IsType = false);
+
+  void AddName(DwarfStringPoolEntryRef Name, const DIE *Die);
+};
 }
 #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;
 
-// 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::HashDataContents::~HashDataContents() {}
+
+template <bool IsType>
+class DIEHashDataContents : public DwarfAccelTable::HashDataContents {
+  const DIE *Die;
+
+public:
+  DIEHashDataContents(const DIE *Die) : Die(Die) {}
+
+  void emit(AsmPrinter *Asm, DwarfDebug *D) const override {
+    // Emit the DIE offset
+    DwarfCompileUnit *CU = D->lookupUnit(Die->getUnit());
+    assert(CU && "Accelerated DIE should belong to a CU.");
+    Asm->EmitInt32(Die->getOffset() + CU->getDebugInfoOffset());
+    if (IsType) {
+      Asm->EmitInt16(Die->getTag());
+      Asm->EmitInt8(0); // Flags
+    }
+  }
+
+  bool less(const HashDataContents *Other) const override {
+    return Die->getOffset() < HD->Die->getOffset();
+  }
+
+  void print(raw_ostream &OS) const override {
+    OS << "  Offset: " << Die->getOffset() << "\n";
+    if (IsType) {
+      OS << "  Tag: " << dwarf::TagString(Die->getTag()) << "\n";
+      OS << "  Flags: 0\n";
+    }
+  }
+};
 
-void DwarfAccelTable::AddName(DwarfStringPoolEntryRef Name, const DIE *die,
-                              char Flags) {
+static LLVM_CONSTEXPR DwarfAccelTable::Atom DieAtoms[] = {
+    DwarfAccelTable::Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
+
+static LLVM_CONSTEXPR DwarfAccelTable::Atom TypeAtoms[] = {
+    DwarfAccelTable::Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4),
+    DwarfAccelTable::Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2),
+    DwarfAccelTable::Atom(dwarf::DW_ATOM_type_flags, dwarf::DW_FORM_data1)};
+
+DIEDwarfAccelTable::DIEDwarfAccelTable(bool IsType)
+    : DwarfAccelTable(IsType ? makeArrayRef(TypeAtoms)
+                             : makeArrayRef(DieAtoms)),
+      IsType(IsType) {}
+
+void DIEDwarfAccelTable::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));
+  HashDataContents *HD;
+  if (IsType)
+    HD = new (Allocator) DIEHashDataContents<true>(Die);
+  else
+    HD = new (Allocator) DIEHashDataContents<false>(Die);
+  DIEs.Values.push_back(HD);
 }
 
+// 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) {}
+
 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());
   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.
-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 (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);
+    std::stable_sort(
+        EI->second.Values.begin(), EI->second.Values.end(),
+        [](const DwarfAccelTable::HashDataContents *A,
+           const DwarfAccelTable::HashDataContents *B) { return A->less(B); });
     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);
   }
 
for (HashList::const_iterator HI = Buckets[i].begin(),
       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);
       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
-        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);
-        }
-      }
+      for (HashDataContents *HD : (*HI)->Data.Values)
+        HD->emit(Asm, D);
       PrevHash = (*HI)->HashValue;
     }
     // Emit the final end marker for the bucket.
     if (!Buckets[i].empty())
       Asm->EmitInt32(0);
   }
 }
 

lib/CodeGen/AsmPrinter/DwarfDebug.h

class DwarfDebug : public AsmPrinterHandler {
   /// @}
   
   /// True iff there are multiple CUs in this module.
   bool SingleCU;
   bool IsDarwin;
 
   AddressPool AddrPool;
 
-  DwarfAccelTable AccelNames;
-  DwarfAccelTable AccelObjC;
-  DwarfAccelTable AccelNamespace;
-  DwarfAccelTable AccelTypes;
+  DIEDwarfAccelTable AccelNames;
+  DIEDwarfAccelTable AccelObjC;
+  DIEDwarfAccelTable AccelNamespace;
+  DIEDwarfAccelTable AccelTypes;
 
   DenseMap<const Function *, DISubprogram *> FunctionDIs;
 
   // Identify a debugger for "tuning" the debug info.
   DebuggerKind DebuggerTuning;
 
   MCDwarfDwoLineTable *getDwoLineTable(const DwarfCompileUnit &);
 
class DwarfDebug : public AsmPrinterHandler {
 
   /// Emit the debug info section.
   void emitDebugInfo();
 
   /// Emit the abbreviation section.
   void emitAbbreviations();
 
   /// Emit a specified accelerator table.
-  void emitAccel(DwarfAccelTable &Accel, MCSection *Section,
+  void emitAccel(DIEDwarfAccelTable &Accel, MCSection *Section,
                  StringRef TableName);
 
   /// Emit visible names into a hashed accelerator table section.
   void emitAccelNames();
 
   /// Emit objective C classes and categories into a hashed
   /// accelerator table section.
   void emitAccelObjC();

lib/CodeGen/AsmPrinter/DwarfDebug.cpp

for (unsigned i = 0, N = Elements.size(); i < N; ++i) {
       auto *DT = cast<DIDerivedType>(Elements[i]);
       if (getName() == DT->getName())
         return resolve(DT->getBaseType());
     }
   }
   return Ty;
 }
 
-static LLVM_CONSTEXPR DwarfAccelTable::Atom TypeAtoms[] = {
-    DwarfAccelTable::Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4),
-    DwarfAccelTable::Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2),
-    DwarfAccelTable::Atom(dwarf::DW_ATOM_type_flags, dwarf::DW_FORM_data1)};
-
 DwarfDebug::DwarfDebug(AsmPrinter *A, Module *M)
     : Asm(A), MMI(Asm->MMI), DebugLocs(A->OutStreamer->isVerboseAsm()),
       PrevLabel(nullptr), InfoHolder(A, "info_string", DIEValueAllocator),
       UsedNonDefaultText(false),
       SkeletonHolder(A, "skel_string", DIEValueAllocator),
-      IsDarwin(Triple(A->getTargetTriple()).isOSDarwin()),
-      AccelNames(DwarfAccelTable::Atom(dwarf::DW_ATOM_die_offset,
-                                       dwarf::DW_FORM_data4)),
-      AccelObjC(DwarfAccelTable::Atom(dwarf::DW_ATOM_die_offset,
-                                      dwarf::DW_FORM_data4)),
-      AccelNamespace(DwarfAccelTable::Atom(dwarf::DW_ATOM_die_offset,
-                                           dwarf::DW_FORM_data4)),
-      AccelTypes(TypeAtoms), DebuggerTuning(DebuggerKind::Default) {
+      IsDarwin(Triple(A->getTargetTriple()).isOSDarwin()), AccelNames(),
+      AccelObjC(), AccelNamespace(), AccelTypes(/* IsType =*/true),
+      DebuggerTuning(DebuggerKind::Default) {
 
   CurFn = nullptr;
   CurMI = nullptr;
   Triple TT(Asm->getTargetTriple());
 
   // Make sure we know our "debugger tuning."  The command-line option takes
   // precedence; fall back to triple-based defaults.
   if (DebuggerTuningOpt != DebuggerKind::Default)

 
 // Emit the abbreviation section.
 void DwarfDebug::emitAbbreviations() {
   DwarfFile &Holder = useSplitDwarf() ? SkeletonHolder : InfoHolder;
 
   Holder.emitAbbrevs(Asm->getObjFileLowering().getDwarfAbbrevSection());
 }
 
-void DwarfDebug::emitAccel(DwarfAccelTable &Accel, MCSection *Section,
+void DwarfDebug::emitAccel(DIEDwarfAccelTable &Accel, MCSection *Section,
                            StringRef TableName) {
   Accel.FinalizeTable(Asm, TableName);
   Asm->OutStreamer->SwitchSection(Section);
 
   // Emit the full data.
   Accel.emit(Asm, Section->getBeginSymbol(), this);
 }