[AccelTable] Provide DWARF5AccelTableStaticData for dsymutil.

[JDevlieghere]

Summary

For dsymutil we want to store offsets in the accelerator table entries
rather than DIE pointers. In addition, we need a way to communicate
which CU a DIE belongs to. This patch provides support for both of these
issues. It supersedes r336529 which will be reverted in favor of this.

[JDevlieghere]

• Add comment motivating template type and callback.

[probinson]

Minor drive-by comment.

llvm/lib/CodeGen/AsmPrinter/AccelTable.cpp

573

I'm guessing this wants llvm:: on it, same as the other overload.

[JDevlieghere]

• Extend interface
• Address Paul's comment

[labath]

This looks good to me. There are some different tradeoffs we could make (speed/templates vs. code size/virtualization), but I don't have an opinion on that, so if noone else does either, I guess this is fine.

llvm/include/llvm/CodeGen/AccelTable.h

319

If we wanted to optimize things, this could be an llvm::function_ref.

[JDevlieghere]

In D49102#1163267, @labath wrote:

This looks good to me. There are some different tradeoffs we could make (speed/templates vs. code size/virtualization), but I don't have an opinion on that, so if noone else does either, I guess this is fine.

It seemed reasonable to pick the same trade-offs as we did for the Apple-style accel tables. The motivation then was that we didn't want to pay for a virtual call for every entry in the list.

llvm/include/llvm/CodeGen/AccelTable.h

 class AccelTableData {
 public:
   virtual ~AccelTableData() = default;
 
   bool operator<(const AccelTableData &Other) const {
     return order() < Other.order();
   }
 
     // Subclasses should implement:
     // static uint32_t hash(StringRef Name);
 
 #ifndef NDEBUG
   virtual void print(raw_ostream &OS) const = 0;
 #endif
 protected:
   virtual uint64_t order() const = 0;
 };
 
public:
 
   DWARF5AccelTableData(const DIE &Die) : Die(Die) {}
 
 #ifndef NDEBUG
   void print(raw_ostream &OS) const override;
 #endif
 
   const DIE &getDie() const { return Die; }
+  uint64_t getDieOffset() const { return Die.getOffset(); }
+  unsigned getDieTag() const { return Die.getTag(); }
 
 protected:
   const DIE &Die;
 
   uint64_t order() const override { return Die.getOffset(); }
 };
 
+class DWARF5AccelTableStaticData : public AccelTableData {
+public:
+  static uint32_t hash(StringRef Name) { return caseFoldingDjbHash(Name); }
+
+  DWARF5AccelTableStaticData(uint64_t DieOffset, unsigned DieTag,
+                             unsigned CUIndex)
+      : DieOffset(DieOffset), DieTag(DieTag), CUIndex(CUIndex) {}
+
+#ifndef NDEBUG
+  void print(raw_ostream &OS) const override;
+#endif
+
+  uint64_t getDieOffset() const { return DieOffset; }
+  unsigned getDieTag() const { return DieTag; }
+  unsigned getCUIndex() const { return CUIndex; }
+
+protected:
+  uint64_t DieOffset;
+  unsigned DieTag;
+  unsigned CUIndex;
+
+  uint64_t order() const override { return DieOffset; }
+};
+
 void emitAppleAccelTableImpl(AsmPrinter *Asm, AccelTableBase &Contents,
                              StringRef Prefix, const MCSymbol *SecBegin,
                              ArrayRef<AppleAccelTableData::Atom> Atoms);
 
 /// Emit an Apple Accelerator Table consisting of entries in the specified
 /// AccelTable. The DataT template parameter should be derived from
 /// AppleAccelTableData.
 template <typename DataT>
 void emitAppleAccelTable(AsmPrinter *Asm, AccelTable<DataT> &Contents,
                          StringRef Prefix, const MCSymbol *SecBegin) {
   static_assert(std::is_convertible<DataT *, AppleAccelTableData *>::value, "");
   emitAppleAccelTableImpl(Asm, Contents, Prefix, SecBegin, DataT::Atoms);
 }
 
 void emitDWARF5AccelTable(AsmPrinter *Asm,
                           AccelTable<DWARF5AccelTableData> &Contents,
                           const DwarfDebug &DD,
                           ArrayRef<std::unique_ptr<DwarfCompileUnit>> CUs);
 
+void emitDWARF5AccelTable(
+    AsmPrinter *Asm, AccelTable<DWARF5AccelTableStaticData> &Contents,
+    ArrayRef<MCSymbol *> CUs,
+    std::function<unsigned(const DWARF5AccelTableStaticData &)>
+        getCUIndexForEntry);
+
 /// Accelerator table data implementation for simple Apple accelerator tables
 /// with just a DIE reference.
 class AppleAccelTableOffsetData : public AppleAccelTableData {
 public:
   AppleAccelTableOffsetData(const DIE *D) : Die(D) {}
 
   void emit(AsmPrinter *Asm) const override;
 

llvm/lib/CodeGen/AsmPrinter/AccelTable.cpp

 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/BinaryFormat/Dwarf.h"
 #include "llvm/CodeGen/AsmPrinter.h"
 #include "llvm/CodeGen/DIE.h"
 #include "llvm/MC/MCExpr.h"
 #include "llvm/MC/MCStreamer.h"
+#include "llvm/MC/MCSymbol.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cstddef>
 #include <cstdint>
 #include <limits>
 #include <vector>
 
 using namespace llvm;
public:
   void emit() const;
 
 #ifndef NDEBUG
   void print(raw_ostream &OS) const;
   void dump() const { print(dbgs()); }
 #endif
 };
 
-/// Class responsible for emitting a DWARF v5 Accelerator Table. The only public
-/// function is emit(), which performs the actual emission.
+/// Class responsible for emitting a DWARF v5 Accelerator Table. The only
+/// public function is emit(), which performs the actual emission.
+///
+/// The class is templated in its data type. This allows us to emit both dyamic
+/// and static data entries. A callback abstract the logic to provide a CU
+/// index for a given entry, which is different per data type, but identical
+/// for every entry in the same table.
+template <typename DataT>
 class Dwarf5AccelTableWriter : public AccelTableWriter {
   struct Header {
     uint32_t UnitLength = 0;
     uint16_t Version = 5;
     uint16_t Padding = 0;
     uint32_t CompUnitCount;
     uint32_t LocalTypeUnitCount = 0;
     uint32_t ForeignTypeUnitCount = 0;
class Dwarf5AccelTableWriter : public AccelTableWriter {
   };
   struct AttributeEncoding {
     dwarf::Index Index;
     dwarf::Form Form;
   };
 
   Header Header;
   DenseMap<uint32_t, SmallVector<AttributeEncoding, 2>> Abbreviations;
-  const DwarfDebug &DD;
-  ArrayRef<std::unique_ptr<DwarfCompileUnit>> CompUnits;
+  ArrayRef<MCSymbol *> CompUnits;
+  std::function<unsigned(const DataT &)> getCUIndexForEntry;
   MCSymbol *ContributionStart = Asm->createTempSymbol("names_start");
   MCSymbol *ContributionEnd = Asm->createTempSymbol("names_end");
   MCSymbol *AbbrevStart = Asm->createTempSymbol("names_abbrev_start");
   MCSymbol *AbbrevEnd = Asm->createTempSymbol("names_abbrev_end");
   MCSymbol *EntryPool = Asm->createTempSymbol("names_entries");
 
   DenseSet<uint32_t> getUniqueTags() const;
 
   // Right now, we emit uniform attributes for all tags.
   SmallVector<AttributeEncoding, 2> getUniformAttributes() const;
 
   void emitCUList() const;
   void emitBuckets() const;
   void emitStringOffsets() const;
   void emitAbbrevs() const;
-  void emitEntry(const DWARF5AccelTableData &Data) const;
+  void emitEntry(const DataT &Data) const;
   void emitData() const;
 
 public:
-  Dwarf5AccelTableWriter(AsmPrinter *Asm, const AccelTableBase &Contents,
-                         const DwarfDebug &DD,
-                         ArrayRef<std::unique_ptr<DwarfCompileUnit>> CompUnits);
+  Dwarf5AccelTableWriter(
+      AsmPrinter *Asm, const AccelTableBase &Contents,
+      ArrayRef<MCSymbol *> CompUnits,
+      std::function<unsigned(const DataT &)> GetCUIndexForEntry);
 
   void emit() const;
 };
 } // namespace
 
 void AccelTableWriter::emitHashes() const {
   uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
   unsigned BucketIdx = 0;
void AppleAccelTableWriter::emit() const {
   Header.emit(Asm);
   HeaderData.emit(Asm);
   emitBuckets();
   emitHashes();
   emitOffsets(SecBegin);
   emitData();
 }
 
-void Dwarf5AccelTableWriter::Header::emit(
+template <typename DataT>
+void Dwarf5AccelTableWriter<DataT>::Header::emit(
     const Dwarf5AccelTableWriter &Ctx) const {
   assert(CompUnitCount > 0 && "Index must have at least one CU.");
 
   AsmPrinter *Asm = Ctx.Asm;
   Asm->OutStreamer->AddComment("Header: unit length");
   Asm->EmitLabelDifference(Ctx.ContributionEnd, Ctx.ContributionStart,
                            sizeof(uint32_t));
   Asm->OutStreamer->EmitLabel(Ctx.ContributionStart);
void Dwarf5AccelTableWriter<DataT>::Header::emit(
   Asm->EmitLabelDifference(Ctx.AbbrevEnd, Ctx.AbbrevStart, sizeof(uint32_t));
   Asm->OutStreamer->AddComment("Header: augmentation string size");
   assert(AugmentationStringSize % 4 == 0);
   Asm->emitInt32(AugmentationStringSize);
   Asm->OutStreamer->AddComment("Header: augmentation string");
   Asm->OutStreamer->EmitBytes({AugmentationString, AugmentationStringSize});
 }
 
-DenseSet<uint32_t> Dwarf5AccelTableWriter::getUniqueTags() const {
+template <typename DataT>
+DenseSet<uint32_t> Dwarf5AccelTableWriter<DataT>::getUniqueTags() const {
   DenseSet<uint32_t> UniqueTags;
   for (auto &Bucket : Contents.getBuckets()) {
     for (auto *Hash : Bucket) {
       for (auto *Value : Hash->Values) {
-        const DIE &Die =
-            static_cast<const DWARF5AccelTableData *>(Value)->getDie();
-        UniqueTags.insert(Die.getTag());
+        unsigned Tag = static_cast<const DataT *>(Value)->getDieTag();
+        UniqueTags.insert(Tag);
       }
     }
   }
   return UniqueTags;
 }
 
-SmallVector<Dwarf5AccelTableWriter::AttributeEncoding, 2>
-Dwarf5AccelTableWriter::getUniformAttributes() const {
+template <typename DataT>
+SmallVector<typename Dwarf5AccelTableWriter<DataT>::AttributeEncoding, 2>
+Dwarf5AccelTableWriter<DataT>::getUniformAttributes() const {
   SmallVector<AttributeEncoding, 2> UA;
   if (CompUnits.size() > 1) {
     size_t LargestCUIndex = CompUnits.size() - 1;
     dwarf::Form Form = DIEInteger::BestForm(/*IsSigned*/ false, LargestCUIndex);
     UA.push_back({dwarf::DW_IDX_compile_unit, Form});
   }
   UA.push_back({dwarf::DW_IDX_die_offset, dwarf::DW_FORM_ref4});
   return UA;
 }
 
-void Dwarf5AccelTableWriter::emitCUList() const {
+template <typename DataT>
+void Dwarf5AccelTableWriter<DataT>::emitCUList() const {
   for (const auto &CU : enumerate(CompUnits)) {
-    assert(CU.index() == CU.value()->getUniqueID());
     Asm->OutStreamer->AddComment("Compilation unit " + Twine(CU.index()));
-    const DwarfCompileUnit *MainCU =
-        DD.useSplitDwarf() ? CU.value()->getSkeleton() : CU.value().get();
-    Asm->emitDwarfSymbolReference(MainCU->getLabelBegin());
+    Asm->emitDwarfSymbolReference(CU.value());
   }
 }
 
-void Dwarf5AccelTableWriter::emitBuckets() const {
+template <typename DataT>
+void Dwarf5AccelTableWriter<DataT>::emitBuckets() const {
   uint32_t Index = 1;
   for (const auto &Bucket : enumerate(Contents.getBuckets())) {
     Asm->OutStreamer->AddComment("Bucket " + Twine(Bucket.index()));
     Asm->emitInt32(Bucket.value().empty() ? 0 : Index);
     Index += Bucket.value().size();
   }
 }
 
-void Dwarf5AccelTableWriter::emitStringOffsets() const {
+template <typename DataT>
+void Dwarf5AccelTableWriter<DataT>::emitStringOffsets() const {
   for (const auto &Bucket : enumerate(Contents.getBuckets())) {
     for (auto *Hash : Bucket.value()) {
       DwarfStringPoolEntryRef String = Hash->Name;
       Asm->OutStreamer->AddComment("String in Bucket " + Twine(Bucket.index()) +
                                    ": " + String.getString());
       Asm->emitDwarfStringOffset(String);
     }
   }
 }
 
-void Dwarf5AccelTableWriter::emitAbbrevs() const {
+template <typename DataT>
+void Dwarf5AccelTableWriter<DataT>::emitAbbrevs() const {
   Asm->OutStreamer->EmitLabel(AbbrevStart);
   for (const auto &Abbrev : Abbreviations) {
     Asm->OutStreamer->AddComment("Abbrev code");
     assert(Abbrev.first != 0);
     Asm->EmitULEB128(Abbrev.first);
     Asm->OutStreamer->AddComment(dwarf::TagString(Abbrev.first));
     Asm->EmitULEB128(Abbrev.first);
     for (const auto &AttrEnc : Abbrev.second) {
       Asm->EmitULEB128(AttrEnc.Index, dwarf::IndexString(AttrEnc.Index).data());
       Asm->EmitULEB128(AttrEnc.Form,
                        dwarf::FormEncodingString(AttrEnc.Form).data());
     }
     Asm->EmitULEB128(0, "End of abbrev");
     Asm->EmitULEB128(0, "End of abbrev");
   }
   Asm->EmitULEB128(0, "End of abbrev list");
   Asm->OutStreamer->EmitLabel(AbbrevEnd);
 }
 
-void Dwarf5AccelTableWriter::emitEntry(
-    const DWARF5AccelTableData &Entry) const {
-  auto AbbrevIt = Abbreviations.find(Entry.getDie().getTag());
+template <typename DataT>
+void Dwarf5AccelTableWriter<DataT>::emitEntry(const DataT &Entry) const {
+  auto AbbrevIt = Abbreviations.find(Entry.getDieTag());
   assert(AbbrevIt != Abbreviations.end() &&
          "Why wasn't this abbrev generated?");
 
   Asm->EmitULEB128(AbbrevIt->first, "Abbreviation code");
   for (const auto &AttrEnc : AbbrevIt->second) {
     Asm->OutStreamer->AddComment(dwarf::IndexString(AttrEnc.Index));
     switch (AttrEnc.Index) {
     case dwarf::DW_IDX_compile_unit: {
-      const DIE *CUDie = Entry.getDie().getUnitDie();
-      DIEInteger ID(DD.lookupCU(CUDie)->getUniqueID());
+      DIEInteger ID(getCUIndexForEntry(Entry));
       ID.EmitValue(Asm, AttrEnc.Form);
       break;
     }
     case dwarf::DW_IDX_die_offset:
       assert(AttrEnc.Form == dwarf::DW_FORM_ref4);
-      Asm->emitInt32(Entry.getDie().getOffset());
+      Asm->emitInt32(Entry.getDieOffset());
       break;
     default:
       llvm_unreachable("Unexpected index attribute!");
     }
   }
 }
 
-void Dwarf5AccelTableWriter::emitData() const {
+template <typename DataT> void Dwarf5AccelTableWriter<DataT>::emitData() const {
   Asm->OutStreamer->EmitLabel(EntryPool);
   for (auto &Bucket : Contents.getBuckets()) {
     for (auto *Hash : Bucket) {
       // Remember to emit the label for our offset.
       Asm->OutStreamer->EmitLabel(Hash->Sym);
       for (const auto *Value : Hash->Values)
-        emitEntry(*static_cast<const DWARF5AccelTableData *>(Value));
+        emitEntry(*static_cast<const DataT *>(Value));
       Asm->OutStreamer->AddComment("End of list: " + Hash->Name.getString());
       Asm->emitInt32(0);
     }
   }
 }
 
-Dwarf5AccelTableWriter::Dwarf5AccelTableWriter(
-    AsmPrinter *Asm, const AccelTableBase &Contents, const DwarfDebug &DD,
-    ArrayRef<std::unique_ptr<DwarfCompileUnit>> CompUnits)
+template <typename DataT>
+Dwarf5AccelTableWriter<DataT>::Dwarf5AccelTableWriter(
+    AsmPrinter *Asm, const AccelTableBase &Contents,
+    ArrayRef<MCSymbol *> CompUnits,
+    std::function<unsigned(const DataT &)> getCUIndexForEntry)
     : AccelTableWriter(Asm, Contents, false),
       Header(CompUnits.size(), Contents.getBucketCount(),
              Contents.getUniqueNameCount()),
-      DD(DD), CompUnits(CompUnits) {
+      CompUnits(CompUnits), getCUIndexForEntry(std::move(getCUIndexForEntry)) {
   DenseSet<uint32_t> UniqueTags = getUniqueTags();
   SmallVector<AttributeEncoding, 2> UniformAttributes = getUniformAttributes();
 
   Abbreviations.reserve(UniqueTags.size());
   for (uint32_t Tag : UniqueTags)
     Abbreviations.try_emplace(Tag, UniformAttributes);
 }
 
-void Dwarf5AccelTableWriter::emit() const {
+template <typename DataT> void Dwarf5AccelTableWriter<DataT>::emit() const {
   Header.emit(*this);
   emitCUList();
   emitBuckets();
   emitHashes();
   emitStringOffsets();
   emitOffsets(EntryPool);
   emitAbbrevs();
   emitData();
   Asm->OutStreamer->EmitValueToAlignment(4, 0);
   Asm->OutStreamer->EmitLabel(ContributionEnd);
 }
 
 void llvm::emitAppleAccelTableImpl(AsmPrinter *Asm, AccelTableBase &Contents,
                                    StringRef Prefix, const MCSymbol *SecBegin,
                                    ArrayRef<AppleAccelTableData::Atom> Atoms) {
   Contents.finalize(Asm, Prefix);
   AppleAccelTableWriter(Asm, Contents, Atoms, SecBegin).emit();
 }
 
 void llvm::emitDWARF5AccelTable(
     AsmPrinter *Asm, AccelTable<DWARF5AccelTableData> &Contents,
     const DwarfDebug &DD, ArrayRef<std::unique_ptr<DwarfCompileUnit>> CUs) {
+  std::vector<MCSymbol *> CompUnits;
+  for (const auto &CU : enumerate(CUs)) {
+    assert(CU.index() == CU.value()->getUniqueID());
+    const DwarfCompileUnit *MainCU =
+        DD.useSplitDwarf() ? CU.value()->getSkeleton() : CU.value().get();
+    CompUnits.push_back(MainCU->getLabelBegin());
+  }
+
+  Contents.finalize(Asm, "names");
+  Dwarf5AccelTableWriter<DWARF5AccelTableData>(
+      Asm, Contents, CompUnits,
+      [&DD](const DWARF5AccelTableData &Entry) {
+        const DIE *CUDie = Entry.getDie().getUnitDie();
+        return DD.lookupCU(CUDie)->getUniqueID();
+      })
+      .emit();
+}
+
+void llvm::emitDWARF5AccelTable(
+    AsmPrinter *Asm, AccelTable<DWARF5AccelTableStaticData> &Contents,
+    ArrayRef<MCSymbol *> CUs,
+    std::function<unsigned(const DWARF5AccelTableStaticData &)>
+        getCUIndexForEntry) {
   Contents.finalize(Asm, "names");
-  Dwarf5AccelTableWriter(Asm, Contents, DD, CUs).emit();
+  Dwarf5AccelTableWriter<DWARF5AccelTableStaticData>(Asm, Contents, CUs,
+                                                     getCUIndexForEntry)
+      .emit();
 }
 
 void AppleAccelTableOffsetData::emit(AsmPrinter *Asm) const {
   Asm->emitInt32(Die->getDebugSectionOffset());
 }
 
 void AppleAccelTableTypeData::emit(AsmPrinter *Asm) const {
   Asm->emitInt32(Die->getDebugSectionOffset());
for (auto &Hash : Bucket)
       Hash->print(OS);
 
   OS << "Data: \n";
   for (auto &E : Entries)
     E.second.print(OS);
 }
 
 void DWARF5AccelTableData::print(raw_ostream &OS) const {
-  OS << "  Offset: " << Die.getOffset() << "\n";
-  OS << "  Tag: " << dwarf::TagString(Die.getTag()) << "\n";
+  OS << "  Offset: " << getDieOffset() << "\n";
+  OS << "  Tag: " << dwarf::TagString(getDieTag()) << "\n";
+}
+
+void DWARF5AccelTableStaticData::print(raw_ostream &OS) const {
+  OS << "  Offset: " << getDieOffset() << "\n";
+  OS << "  Tag: " << dwarf::TagString(getDieTag()) << "\n";
 }
 
 void AppleAccelTableOffsetData::print(raw_ostream &OS) const {
   OS << "  Offset: " << Die->getOffset() << "\n";
 }
 
 void AppleAccelTableTypeData::print(raw_ostream &OS) const {
   OS << "  Offset: " << Die->getOffset() << "\n";