[CodeGen] Refactor AppleAccelTable

[labath]

Summary

This commit separates the abstract accelerator table data structure
from the code for writing out an on-disk representation of a specific
accelerator table format. The idea is that former (now called
AccelTable<T>) can be reused for the DWARF v5 accelerator tables
as-is, without any further customizations.

Some bits of the emission code (now living in the EmissionContext class)
can be reused for DWARF v5 as well, but the subtle differences in the
layout of various subtables mean the sharing is not always possible.
(Also, the individual emit*** functions are fairly simple so there's a
tradeoff between making a bigger general-purpose function, and two
smaller targeted functions.)

Another advantage of this setup is that more of the serialization logic
can be hidden in the .cpp file -- I have moved declarations of the
header and all the emission functions there.

[labath]

I've also put up D43286 (which is still WIP, but nearing completion...) so you can see the context of this change.

[labath]

delete copy constructors of AccelTableBase and move one comment a bit.

[JDevlieghere]

Looks good, with a few minor comments inline.

I think it would be great if we can add a small diagram or textual explanation to the top of the header file with the way the classes are structure, similar to your summary here. The comments on the individual classes are clear enough imho, but I can imagine that the big picture is a little harder to get when you don't know why we have all these different classes.

include/llvm/CodeGen/AccelTable.h

117–125

What was your motivation for wrapping this into a separate namespace? When I saw detail I assumed this is where the differences between the Apple and DWARF tables would live. Maybe I'm missing something but otherwise I think we'd be better of without it.

132–133

Is there any advantage over passing in the hash value directly?

150–152

std::function<uint32_t(StringRef)>?

lib/CodeGen/AsmPrinter/AccelTable.cpp

91

[opinion] I think AccelTableEmitter or something like that would better convey the purpose of this class.

[labath]

include/llvm/CodeGen/AccelTable.h

117–125

It's customary (at least in some parts of the llvm codebase) to place the things which have to be declared in the header, but that are not really considered to be a public interface into the detail namespace. I've put it here because I don't think anyone on the outside should ever refer to this non-templated class directly as doing so (particularly in combination with the non-templated version of emitAppleAccelTable) would allow you to circumvent some of the type safety checks (and probably crash).

But it seems that's not how things are done here (this is the only instance of the detail namespace in CodeGen), so I've removed it.

132–133

We delay computing the hash in the try_emplace function (in AddName) until we know that we really need to construct a new HashData object (i.e., that this is a new name).

150–152

I think we should avoid that as std::function is fairly heavy (it uses virtual dispatch and what-not). Besides, in the current model, we obtain the hash function as &DataT::hash, so this cannot really be anything other than a simple function pointer.

lib/CodeGen/AsmPrinter/AccelTable.cpp

91

I agree. (It's called this way because this started out just as a plain holder for the various bits needed for serialization).

[labath]

Remove the detail namespace, and rename the EmissionContext class.

[JDevlieghere]

LGTM. Thanks for working on this Pavel, I'm very happy with the direction this is going.

include/llvm/CodeGen/AccelTable.h

117–125

Alright, thanks for explaining. I didn't know about the detail namespace.

132–133

Makes sense!

150–152

Fair enough.

include/llvm/CodeGen/AccelTable.h

 //==- include/llvm/CodeGen/AccelTable.h - Accelerator Tables -----*- C++ -*-==//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file contains support for writing accelerator tables.
 //
 //===----------------------------------------------------------------------===//
 
-#ifndef LLVM_LIB_CODEGEN_ASMPRINTER_DWARFACCELTABLE_H
-#define LLVM_LIB_CODEGEN_ASMPRINTER_DWARFACCELTABLE_H
+#ifndef LLVM_CODEGEN_DWARFACCELTABLE_H
+#define LLVM_CODEGEN_DWARFACCELTABLE_H
 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/BinaryFormat/Dwarf.h"
 #include "llvm/CodeGen/DIE.h"
 #include "llvm/CodeGen/DwarfStringPoolEntry.h"

 /// `------------------'
 ///
 /// For the full documentation please refer to the DWARF 5 standard.
 
 namespace llvm {
 
 class AsmPrinter;
 
-/// Representation of the header of an Apple accelerator table. This consists
-/// of the fixed header and the header data. The latter contains the atoms
-/// which define the columns of the table.
-class AppleAccelTableHeader {
-  struct Header {
-    uint32_t Magic = MagicHash;
-    uint16_t Version = 1;
-    uint16_t HashFunction = dwarf::DW_hash_function_djb;
-    uint32_t BucketCount = 0;
-    uint32_t HashCount = 0;
-    uint32_t HeaderDataLength;
-
-    /// 'HASH' magic value to detect endianness.
-    static const uint32_t MagicHash = 0x48415348;
-
-    Header(uint32_t DataLength) : HeaderDataLength(DataLength) {}
-
-#ifndef NDEBUG
-    void print(raw_ostream &OS) const;
-    void dump() const { print(dbgs()); }
-#endif
-  };
-
-public:
-  /// An Atom defines the form of the data in the accelerator table.
-  /// Conceptually it is a column in the accelerator consisting of a type and a
-  /// specification of the form of its data.
-  struct Atom {
-    /// Atom Type.
-    const uint16_t Type;
-    /// DWARF Form.
-    const uint16_t Form;
-
-    constexpr Atom(uint16_t Type, uint16_t Form) : Type(Type), Form(Form) {}
-
-#ifndef NDEBUG
-    void print(raw_ostream &OS) const;
-    void dump() const { print(dbgs()); }
-#endif
-  };
-
-private:
-  /// The HeaderData describes the structure of the accelerator table through a
-  /// list of Atoms.
-  struct HeaderData {
-    /// In the case of data that is referenced via DW_FORM_ref_* the offset
-    /// base is used to describe the offset for all forms in the list of atoms.
-    uint32_t DieOffsetBase;
-
-    const SmallVector<Atom, 4> Atoms;
-
-#ifndef _MSC_VER
-    // See the `static constexpr` below why we need an alternative
-    // implementation for MSVC.
-    HeaderData(ArrayRef<Atom> AtomList, uint32_t Offset = 0)
-        : DieOffsetBase(Offset), Atoms(AtomList.begin(), AtomList.end()) {}
-#else
-    // FIXME: Erase this path once the minimum MSCV version has been bumped.
-    HeaderData(const SmallVectorImpl<Atom> &Atoms, uint32_t Offset = 0)
-        : DieOffsetBase(Offset), Atoms(Atoms.begin(), Atoms.end()) {}
-#endif
-
-#ifndef NDEBUG
-    void print(raw_ostream &OS) const;
-    void dump() const { print(dbgs()); }
-#endif
-  };
-
-  Header Header;
-  HeaderData HeaderData;
-
-public:
-  /// The length of the header data is always going to be 4 + 4 + 4*NumAtoms.
-#ifndef _MSC_VER
-  // See the `static constexpr` below why we need an alternative implementation
-  // for MSVC.
-  AppleAccelTableHeader(ArrayRef<AppleAccelTableHeader::Atom> Atoms)
-      : Header(8 + (Atoms.size() * 4)), HeaderData(Atoms) {}
-#else
-  // FIXME: Erase this path once the minimum MSCV version has been bumped.
-  AppleAccelTableHeader(const SmallVectorImpl<Atom> &Atoms)
-      : Header(8 + (Atoms.size() * 4)), HeaderData(Atoms) {}
-#endif
-
-  /// Update header with hash and bucket count.
-  void setBucketAndHashCount(uint32_t HashCount);
-
-  uint32_t getHashCount() const { return Header.HashCount; }
-  uint32_t getBucketCount() const { return Header.BucketCount; }
-
-  /// Emits the header via the AsmPrinter.
-  void emit(AsmPrinter *);
-
-#ifndef NDEBUG
-  void print(raw_ostream &OS) const;
-  void dump() const { print(dbgs()); }
-#endif
-};
-
 /// Interface which the different types of accelerator table data have to
-/// conform.
-class AppleAccelTableData {
+/// conform. It serves as a base class for different values of the template
+/// argument of the AccelTable class template.
+class AccelTableData {
 public:
-  virtual ~AppleAccelTableData() = default;
+  virtual ~AccelTableData() = default;
 
-  virtual void emit(AsmPrinter *Asm) const = 0;
-
-  bool operator<(const AppleAccelTableData &Other) const {
+  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;
 };
 
-/// Apple-style accelerator table base class.
-class AppleAccelTableBase {
-protected:
+namespace detail {
+/// A base class holding non-template-dependant functionality of the AccelTable
+/// class. Clients should not use this class directly but rather instantiate
+/// AccelTable with a type derived from AccelTableData.
+class AccelTableBase {
+public:
+  using HashFn = uint32_t(StringRef);
+
+  /// Represents a group of entries with identical name (and hence, hash value).
   struct HashData {
     DwarfStringPoolEntryRef Name;
     uint32_t HashValue;
-    std::vector<AppleAccelTableData *> Values;
+    std::vector<AccelTableData *> Values;
     MCSymbol *Sym;
 
-    HashData(DwarfStringPoolEntryRef Name) : Name(Name) {
-      HashValue = djbHash(Name.getString());
-    }
+    HashData(DwarfStringPoolEntryRef Name, HashFn *Hash)
+        : Name(Name), HashValue(Hash(Name.getString())) {}
 
 #ifndef NDEBUG
     void print(raw_ostream &OS) const;
     void dump() const { print(dbgs()); }
 #endif
   };
+  using HashList = std::vector<HashData *>;
+  using BucketList = std::vector<HashList>;
 
+protected:
   /// Allocator for HashData and Values.
   BumpPtrAllocator Allocator;
 
-  /// Header containing both the header and header data.
-  AppleAccelTableHeader Header;
-
   using StringEntries = StringMap<HashData, BumpPtrAllocator &>;
   StringEntries Entries;
 
-  using HashList = std::vector<HashData *>;
-  HashList Hashes;
+  HashFn *Hash;
+  uint32_t BucketCount;
+  uint32_t UniqueHashCount;
 
-  using BucketList = std::vector<HashList>;
+  HashList Hashes;
   BucketList Buckets;
 
-#ifndef _MSC_VER
-  // See the `static constexpr` below why we need an alternative implementation
-  // for MSVC.
-  AppleAccelTableBase(ArrayRef<AppleAccelTableHeader::Atom> Atoms)
-      : Header(Atoms), Entries(Allocator) {}
-#else
-  // FIXME: Erase this path once the minimum MSCV version has been bumped.
-  AppleAccelTableBase(const SmallVectorImpl<AppleAccelTableHeader::Atom> &Atoms)
-      : Header(Atoms), Entries(Allocator) {}
-#endif
-
-private:
-  /// Emits the header for the table via the AsmPrinter.
-  void emitHeader(AsmPrinter *Asm);
-
-  /// Helper function to compute the number of buckets needed based on the
-  /// number of unique hashes.
   void computeBucketCount();
 
-  /// Walk through and emit the buckets for the table. Each index is an offset
-  /// into the list of hashes.
-  void emitBuckets(AsmPrinter *);
-
-  /// Walk through the buckets and emit the individual hashes for each bucket.
-  void emitHashes(AsmPrinter *);
-
-  /// Walk through the buckets and emit the individual offsets for each element
-  /// in each bucket. This is done via a symbol subtraction from the beginning
-  /// of the section. The non-section symbol will be output later when we emit
-  /// the actual data.
-  void emitOffsets(AsmPrinter *, const MCSymbol *);
-
-  /// 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 emitData(AsmPrinter *);
+  AccelTableBase(HashFn *Hash) : Entries(Allocator), Hash(Hash) {}
 
 public:
-  void finalizeTable(AsmPrinter *, StringRef);
-
-  void emit(AsmPrinter *Asm, const MCSymbol *SecBegin) {
-    emitHeader(Asm);
-    emitBuckets(Asm);
-    emitHashes(Asm);
-    emitOffsets(Asm, SecBegin);
-    emitData(Asm);
-  }
+  void finalize(AsmPrinter *Asm, StringRef Prefix);
+  ArrayRef<HashList> getBuckets() const { return Buckets; }
+  uint32_t getBucketCount() const { return BucketCount; }
+  uint32_t getUniqueHashCount() const { return UniqueHashCount; }
+  uint32_t getUniqueNameCount() const { return Entries.size(); }
 
 #ifndef NDEBUG
   void print(raw_ostream &OS) const;
   void dump() const { print(dbgs()); }
 #endif
 };
+} // namespace detail
 
-template <typename AppleAccelTableDataT>
-class AppleAccelTable : public AppleAccelTableBase {
+/// This class holds an abstract representation of an Accelerator Table,
+/// consisting of a sequence of buckets, each bucket containint a sequence of
+/// HashData entries. The class is parameterized by the type of entries it
+/// holds. The type template parameter also defines the hash function to use for
+/// hashing names.
+template <typename DataT> class AccelTable : public detail::AccelTableBase {
 public:
-  AppleAccelTable() : AppleAccelTableBase(AppleAccelTableDataT::Atoms) {}
-  AppleAccelTable(const AppleAccelTable &) = delete;
-  AppleAccelTable &operator=(const AppleAccelTable &) = delete;
+  AccelTable() : AccelTableBase(DataT::hash) {}
 
-  template <class... Types>
-  void addName(DwarfStringPoolEntryRef Name, Types... Args);
+  template <typename... Types>
+  void addName(DwarfStringPoolEntryRef Name, Types &&... Args);
 };
 
-template <typename AppleAccelTableDataT>
-template <class... Types>
-void AppleAccelTable<AppleAccelTableDataT>::addName(
-    DwarfStringPoolEntryRef Name, Types... Args) {
+template <typename AccelTableDataT>
+template <typename... Types>
+void AccelTable<AccelTableDataT>::addName(DwarfStringPoolEntryRef Name,
+                                          Types &&... Args) {
   assert(Buckets.empty() && "Already finalized!");
   // If the string is in the list already then add this die to the list
   // otherwise add a new one.
-  auto Iter = Entries.try_emplace(Name.getString(), Name).first;
+  auto Iter = Entries.try_emplace(Name.getString(), Name, Hash).first;
   assert(Iter->second.Name == Name);
-  Iter->second.Values.push_back(new (Allocator) AppleAccelTableDataT(Args...));
+  Iter->second.Values.push_back(
+      new (Allocator) AccelTableDataT(std::forward<Types>(Args)...));
 }
 
-/// Accelerator table data implementation for simple accelerator tables with
-/// just a DIE reference.
+/// A base class for different implementations of Data classes for Apple
+/// Accelerator Tables. The columns in the table are defined by the static Atoms
+/// variable defined on the subclasses.
+class AppleAccelTableData : public AccelTableData {
+public:
+  /// An Atom defines the form of the data in an Apple accelerator table.
+  /// Conceptually it is a column in the accelerator consisting of a type and a
+  /// specification of the form of its data.
+  struct Atom {
+    /// Atom Type.
+    const uint16_t Type;
+    /// DWARF Form.
+    const uint16_t Form;
+
+    constexpr Atom(uint16_t Type, uint16_t Form) : Type(Type), Form(Form) {}
+
+#ifndef NDEBUG
+    void print(raw_ostream &OS) const;
+    void dump() const { print(dbgs()); }
+#endif
+  };
+  // Subclasses should define:
+  // static constexpr Atom Atoms[];
+
+  virtual void emit(AsmPrinter *Asm) const = 0;
+
+  static uint32_t hash(StringRef Buffer) { return djbHash(Buffer); }
+};
+
+namespace detail {
+void emitAppleAccelTable(AsmPrinter *Asm, AccelTableBase &Contents,
+                         StringRef Prefix, const MCSymbol *SecBegin,
+                         ArrayRef<AppleAccelTableData::Atom> Atoms);
+}
+
+template <typename DataT>
+/// Emit an Apple Accelerator Table consisting of entries in the specified
+/// AccelTable. The DataT template parameter should be derived from
+/// AppleAccelTableData.
+void emitAppleAccelTable(AsmPrinter *Asm, AccelTable<DataT> &Contents,
+                         StringRef Prefix, const MCSymbol *SecBegin) {
+  static_assert(std::is_convertible<DataT *, AppleAccelTableData *>::value, "");
+  detail::emitAppleAccelTable(Asm, Contents, Prefix, SecBegin, DataT::Atoms);
+}
+
+/// 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;
 
 #ifndef _MSC_VER
   // The line below is rejected by older versions (TBD) of MSVC.
-  static constexpr AppleAccelTableHeader::Atom Atoms[] = {
-      AppleAccelTableHeader::Atom(dwarf::DW_ATOM_die_offset,
-                                  dwarf::DW_FORM_data4)};
+  static constexpr Atom Atoms[] = {
+      Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
 #else
   // FIXME: Erase this path once the minimum MSCV version has been bumped.
-  static const SmallVector<AppleAccelTableHeader::Atom, 4> Atoms;
+  static const SmallVector<Atom, 4> Atoms;
 #endif
 
 #ifndef NDEBUG
   void print(raw_ostream &OS) const override;
 #endif
 protected:
   uint64_t order() const override { return Die->getOffset(); }
 
   const DIE *Die;
 };
 
-/// Accelerator table data implementation for type accelerator tables.
+/// Accelerator table data implementation for Apple type accelerator tables.
 class AppleAccelTableTypeData : public AppleAccelTableOffsetData {
 public:
   AppleAccelTableTypeData(const DIE *D) : AppleAccelTableOffsetData(D) {}
 
   void emit(AsmPrinter *Asm) const override;
 
 #ifndef _MSC_VER
   // The line below is rejected by older versions (TBD) of MSVC.
-  static constexpr AppleAccelTableHeader::Atom Atoms[] = {
-      AppleAccelTableHeader::Atom(dwarf::DW_ATOM_die_offset,
-                                  dwarf::DW_FORM_data4),
-      AppleAccelTableHeader::Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2),
-      AppleAccelTableHeader::Atom(dwarf::DW_ATOM_type_flags,
-                                  dwarf::DW_FORM_data1)};
+  static constexpr Atom Atoms[] = {
+      Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4),
+      Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2),
+      Atom(dwarf::DW_ATOM_type_flags, dwarf::DW_FORM_data1)};
 #else
   // FIXME: Erase this path once the minimum MSCV version has been bumped.
-  static const SmallVector<AppleAccelTableHeader::Atom, 4> Atoms;
+  static const SmallVector<Atom, 4> Atoms;
 #endif
 
 #ifndef NDEBUG
   void print(raw_ostream &OS) const override;
 #endif
 };
 
-/// Accelerator table data implementation for simple accelerator tables with
-/// a DIE offset but no actual DIE pointer.
+/// Accelerator table data implementation for simple Apple accelerator tables
+/// with a DIE offset but no actual DIE pointer.
 class AppleAccelTableStaticOffsetData : public AppleAccelTableData {
 public:
   AppleAccelTableStaticOffsetData(uint32_t Offset) : Offset(Offset) {}
 
   void emit(AsmPrinter *Asm) const override;
 
 #ifndef _MSC_VER
   // The line below is rejected by older versions (TBD) of MSVC.
-  static constexpr AppleAccelTableHeader::Atom Atoms[] = {
-      AppleAccelTableHeader::Atom(dwarf::DW_ATOM_die_offset,
-                                  dwarf::DW_FORM_data4)};
+  static constexpr Atom Atoms[] = {
+      Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
 #else
   // FIXME: Erase this path once the minimum MSCV version has been bumped.
-  static const SmallVector<AppleAccelTableHeader::Atom, 4> Atoms;
+  static const SmallVector<Atom, 4> Atoms;
 #endif
 
 #ifndef NDEBUG
   void print(raw_ostream &OS) const override;
 #endif
 protected:
   uint64_t order() const override { return Offset; }
 
AppleAccelTableStaticTypeData(uint32_t Offset, uint16_t Tag,
       : AppleAccelTableStaticOffsetData(Offset),
         QualifiedNameHash(QualifiedNameHash), Tag(Tag),
         ObjCClassIsImplementation(ObjCClassIsImplementation) {}
 
   void emit(AsmPrinter *Asm) const override;
 
 #ifndef _MSC_VER
   // The line below is rejected by older versions (TBD) of MSVC.
-  static constexpr AppleAccelTableHeader::Atom Atoms[] = {
-      AppleAccelTableHeader::Atom(dwarf::DW_ATOM_die_offset,
-                                  dwarf::DW_FORM_data4),
-      AppleAccelTableHeader::Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2),
-      AppleAccelTableHeader::Atom(5, dwarf::DW_FORM_data1),
-      AppleAccelTableHeader::Atom(6, dwarf::DW_FORM_data4)};
+  static constexpr Atom Atoms[] = {
+      Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4),
+      Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2),
+      Atom(5, dwarf::DW_FORM_data1), Atom(6, dwarf::DW_FORM_data4)};
 #else
   // FIXME: Erase this path once the minimum MSCV version has been bumped.
-  static const SmallVector<AppleAccelTableHeader::Atom, 4> Atoms;
+  static const SmallVector<Atom, 4> Atoms;
 #endif
 
 #ifndef NDEBUG
   void print(raw_ostream &OS) const override;
 #endif
 protected:
   uint64_t order() const override { return Offset; }
 
   uint32_t QualifiedNameHash;
   uint16_t Tag;
   bool ObjCClassIsImplementation;
 };
 
 } // end namespace llvm
 
-#endif // LLVM_LIB_CODEGEN_ASMPRINTER_DWARFACCELTABLE_H
+#endif // LLVM_CODEGEN_DWARFACCELTABLE_H

lib/CodeGen/AsmPrinter/AccelTable.cpp

 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cstddef>
 #include <cstdint>
 #include <limits>
 #include <vector>
 
 using namespace llvm;
+using namespace llvm::detail;
 
-void AppleAccelTableHeader::emit(AsmPrinter *Asm) {
-  // Emit Header.
+void AccelTableBase::computeBucketCount() {
+  // First get the number of unique hashes.
+  std::vector<uint32_t> Uniques;
+  Uniques.reserve(Entries.size());
+  for (const auto &E : Entries)
+    Uniques.push_back(E.second.HashValue);
+  array_pod_sort(Uniques.begin(), Uniques.end());
+  std::vector<uint32_t>::iterator P =
+      std::unique(Uniques.begin(), Uniques.end());
+
+  UniqueHashCount = std::distance(Uniques.begin(), P);
+
+  if (UniqueHashCount > 1024)
+    BucketCount = UniqueHashCount / 4;
+  else if (UniqueHashCount > 16)
+    BucketCount = UniqueHashCount / 2;
+  else
+    BucketCount = std::max<uint32_t>(UniqueHashCount, 1);
+}
+
+void AccelTableBase::finalize(AsmPrinter *Asm, StringRef Prefix) {
+  // Create the individual hash data outputs.
+  for (auto &E : Entries) {
+    // Unique the entries.
+    std::stable_sort(E.second.Values.begin(), E.second.Values.end(),
+                     [](const AccelTableData *A, const AccelTableData *B) {
+                       return *A < *B;
+                     });
+    E.second.Values.erase(
+        std::unique(E.second.Values.begin(), E.second.Values.end()),
+        E.second.Values.end());
+  }
+
+  // Figure out how many buckets we need, then compute the bucket contents and
+  // the final ordering. The hashes and offsets can be emitted by walking these
+  // data structures. We add temporary symbols to the data so they can be
+  // referenced when emitting the offsets.
+  computeBucketCount();
+
+  // Compute bucket contents and final ordering.
+  Buckets.resize(BucketCount);
+  for (auto &E : Entries) {
+    uint32_t Bucket = E.second.HashValue % BucketCount;
+    Buckets[Bucket].push_back(&E.second);
+    E.second.Sym = Asm->createTempSymbol(Prefix);
+  }
+
+  // Sort the contents of the buckets by hash value so that hash collisions end
+  // up together. Stable sort makes testing easier and doesn't cost much more.
+  for (auto &Bucket : Buckets)
+    std::stable_sort(Bucket.begin(), Bucket.end(),
+                     [](HashData *LHS, HashData *RHS) {
+                       return LHS->HashValue < RHS->HashValue;
+                     });
+}
+
+namespace {
+/// Represents the emission state of a single accelerator table.
+class EmissionContext {
+protected:
+  AsmPrinter *const Asm;          ///< Destination.
+  const AccelTableBase &Contents; ///< Data to emit.
+
+  /// Controls whether to emit duplicate hash and offset table entries for names
+  /// with identical hashes. Apple tables don't emit duplicate entries, DWARF v5
+  /// tables do.
+  const bool SkipIdenticalHashes;
+
+  void emitHashes() const;
+
+  /// Emit offsets to lists of entries with identical names. The offsets are
+  /// relative to the Base argument.
+  void emitOffsets(const MCSymbol *Base) const;
+
+public:
+  EmissionContext(AsmPrinter *Asm, const AccelTableBase &Contents,
+                  bool SkipIdenticalHashes)
+      : Asm(Asm), Contents(Contents), SkipIdenticalHashes(SkipIdenticalHashes) {
+  }
+};
+
+class AppleEmissionContext : public EmissionContext {
+  using Atom = AppleAccelTableData::Atom;
+
+  /// The fixed header of an Apple Accelerator Table.
+  struct Header {
+    uint32_t Magic = MagicHash;
+    uint16_t Version = 1;
+    uint16_t HashFunction = dwarf::DW_hash_function_djb;
+    uint32_t BucketCount;
+    uint32_t HashCount;
+    uint32_t HeaderDataLength;
+
+    /// 'HASH' magic value to detect endianness.
+    static const uint32_t MagicHash = 0x48415348;
+
+    Header(uint32_t BucketCount, uint32_t UniqueHashCount, uint32_t DataLength)
+        : BucketCount(BucketCount), HashCount(UniqueHashCount),
+          HeaderDataLength(DataLength) {}
+
+    void emit(AsmPrinter *Asm) const;
+#ifndef NDEBUG
+    void print(raw_ostream &OS) const;
+    void dump() const { print(dbgs()); }
+#endif
+  };
+
+  /// The HeaderData describes the structure of an Apple accelerator table
+  /// through a list of Atoms.
+  struct HeaderData {
+    /// In the case of data that is referenced via DW_FORM_ref_* the offset
+    /// base is used to describe the offset for all forms in the list of atoms.
+    uint32_t DieOffsetBase;
+
+    const SmallVector<Atom, 4> Atoms;
+
+    HeaderData(ArrayRef<Atom> AtomList, uint32_t Offset = 0)
+        : DieOffsetBase(Offset), Atoms(AtomList.begin(), AtomList.end()) {}
+
+    void emit(AsmPrinter *Asm) const;
+#ifndef NDEBUG
+    void print(raw_ostream &OS) const;
+    void dump() const { print(dbgs()); }
+#endif
+  };
+
+  Header Header;
+  HeaderData HeaderData;
+  const MCSymbol *SecBegin;
+
+  void emitBuckets() const;
+  void emitData() const;
+
+public:
+  AppleEmissionContext(AsmPrinter *Asm, const AccelTableBase &Contents,
+                       ArrayRef<Atom> Atoms, const MCSymbol *SecBegin)
+      : EmissionContext(Asm, Contents, true),
+        Header(Contents.getBucketCount(), Contents.getUniqueHashCount(),
+               8 + (Atoms.size() * 4)),
+        HeaderData(Atoms), SecBegin(SecBegin) {}
+
+  void emit() const;
+
+#ifndef NDEBUG
+  void print(raw_ostream &OS) const;
+  void dump() const { print(dbgs()); }
+#endif
+};
+} // namespace
+
+void EmissionContext::emitHashes() const {
+  uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
+  unsigned BucketIdx = 0;
+  for (auto &Bucket : Contents.getBuckets()) {
+    for (auto &Hash : Bucket) {
+      uint32_t HashValue = Hash->HashValue;
+      if (SkipIdenticalHashes && PrevHash == HashValue)
+        continue;
+      Asm->OutStreamer->AddComment("Hash in Bucket " + Twine(BucketIdx));
+      Asm->EmitInt32(HashValue);
+      PrevHash = HashValue;
+    }
+    BucketIdx++;
+  }
+}
+
+void EmissionContext::emitOffsets(const MCSymbol *Base) const {
+  const auto &Buckets = Contents.getBuckets();
+  uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
+  for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
+    for (auto *Hash : Buckets[i]) {
+      uint32_t HashValue = Hash->HashValue;
+      if (SkipIdenticalHashes && PrevHash == HashValue)
+        continue;
+      PrevHash = HashValue;
+      Asm->OutStreamer->AddComment("Offset in Bucket " + Twine(i));
+      Asm->EmitLabelDifference(Hash->Sym, Base, sizeof(uint32_t));
+    }
+  }
+}
+
+void AppleEmissionContext::Header::emit(AsmPrinter *Asm) const {
   Asm->OutStreamer->AddComment("Header Magic");
-  Asm->EmitInt32(Header.Magic);
+  Asm->EmitInt32(Magic);
   Asm->OutStreamer->AddComment("Header Version");
-  Asm->EmitInt16(Header.Version);
+  Asm->EmitInt16(Version);
   Asm->OutStreamer->AddComment("Header Hash Function");
-  Asm->EmitInt16(Header.HashFunction);
+  Asm->EmitInt16(HashFunction);
   Asm->OutStreamer->AddComment("Header Bucket Count");
-  Asm->EmitInt32(Header.BucketCount);
+  Asm->EmitInt32(BucketCount);
   Asm->OutStreamer->AddComment("Header Hash Count");
-  Asm->EmitInt32(Header.HashCount);
+  Asm->EmitInt32(HashCount);
   Asm->OutStreamer->AddComment("Header Data Length");
-  Asm->EmitInt32(Header.HeaderDataLength);
+  Asm->EmitInt32(HeaderDataLength);
+}
 
-  //  Emit Header Data
+void AppleEmissionContext::HeaderData::emit(AsmPrinter *Asm) const {
   Asm->OutStreamer->AddComment("HeaderData Die Offset Base");
-  Asm->EmitInt32(HeaderData.DieOffsetBase);
+  Asm->EmitInt32(DieOffsetBase);
   Asm->OutStreamer->AddComment("HeaderData Atom Count");
-  Asm->EmitInt32(HeaderData.Atoms.size());
+  Asm->EmitInt32(Atoms.size());
 
-  for (size_t i = 0; i < HeaderData.Atoms.size(); i++) {
-    Atom A = HeaderData.Atoms[i];
+  for (const Atom &A : Atoms) {
     Asm->OutStreamer->AddComment(dwarf::AtomTypeString(A.Type));
     Asm->EmitInt16(A.Type);
     Asm->OutStreamer->AddComment(dwarf::FormEncodingString(A.Form));
     Asm->EmitInt16(A.Form);
   }
 }
 
-void AppleAccelTableHeader::setBucketAndHashCount(uint32_t HashCount) {
-  if (HashCount > 1024)
-    Header.BucketCount = HashCount / 4;
-  else if (HashCount > 16)
-    Header.BucketCount = HashCount / 2;
-  else
-    Header.BucketCount = HashCount > 0 ? HashCount : 1;
-
-  Header.HashCount = HashCount;
-}
-
-void AppleAccelTableBase::emitHeader(AsmPrinter *Asm) { Header.emit(Asm); }
-
-void AppleAccelTableBase::emitBuckets(AsmPrinter *Asm) {
+void AppleEmissionContext::emitBuckets() const {
+  const auto &Buckets = Contents.getBuckets();
   unsigned index = 0;
   for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
     Asm->OutStreamer->AddComment("Bucket " + Twine(i));
     if (!Buckets[i].empty())
       Asm->EmitInt32(index);
     else
       Asm->EmitInt32(std::numeric_limits<uint32_t>::max());
     // Buckets point in the list of hashes, not to the data. Do not increment
     // the index multiple times in case of hash collisions.
     uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
     for (auto *HD : Buckets[i]) {
       uint32_t HashValue = HD->HashValue;
       if (PrevHash != HashValue)
         ++index;
       PrevHash = HashValue;
     }
   }
 }
 
-void AppleAccelTableBase::emitHashes(AsmPrinter *Asm) {
-  uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
-  unsigned BucketIdx = 0;
-  for (auto &Bucket : Buckets) {
-    for (auto &Hash : Bucket) {
-      uint32_t HashValue = Hash->HashValue;
-      if (PrevHash == HashValue)
-        continue;
-      Asm->OutStreamer->AddComment("Hash in Bucket " + Twine(BucketIdx));
-      Asm->EmitInt32(HashValue);
-      PrevHash = HashValue;
-    }
-    BucketIdx++;
-  }
-}
-
-void AppleAccelTableBase::emitOffsets(AsmPrinter *Asm,
-                                      const MCSymbol *SecBegin) {
-  uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
-  for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
-    for (auto HI = Buckets[i].begin(), HE = Buckets[i].end(); HI != HE; ++HI) {
-      uint32_t HashValue = (*HI)->HashValue;
-      if (PrevHash == HashValue)
-        continue;
-      PrevHash = HashValue;
-      Asm->OutStreamer->AddComment("Offset in Bucket " + Twine(i));
-      MCContext &Context = Asm->OutStreamer->getContext();
-      const MCExpr *Sub = MCBinaryExpr::createSub(
-          MCSymbolRefExpr::create((*HI)->Sym, Context),
-          MCSymbolRefExpr::create(SecBegin, Context), Context);
-      Asm->OutStreamer->EmitValue(Sub, sizeof(uint32_t));
-    }
-  }
-}
-
-void AppleAccelTableBase::emitData(AsmPrinter *Asm) {
+void AppleEmissionContext::emitData() const {
+  const auto &Buckets = Contents.getBuckets();
   for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
     uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
     for (auto &Hash : Buckets[i]) {
       // Terminate the previous entry if there is no hash collision with the
       // current one.
       if (PrevHash != std::numeric_limits<uint64_t>::max() &&
           PrevHash != Hash->HashValue)
         Asm->EmitInt32(0);
       // Remember to emit the label for our offset.
       Asm->OutStreamer->EmitLabel(Hash->Sym);
       Asm->OutStreamer->AddComment(Hash->Name.getString());
       Asm->emitDwarfStringOffset(Hash->Name);
       Asm->OutStreamer->AddComment("Num DIEs");
       Asm->EmitInt32(Hash->Values.size());
-      for (const auto *V : Hash->Values) {
-        V->emit(Asm);
-      }
+      for (const auto *V : Hash->Values)
+        static_cast<const AppleAccelTableData *>(V)->emit(Asm);
       PrevHash = Hash->HashValue;
     }
     // Emit the final end marker for the bucket.
     if (!Buckets[i].empty())
       Asm->EmitInt32(0);
   }
 }
 
-void AppleAccelTableBase::computeBucketCount() {
-  // First get the number of unique hashes.
-  std::vector<uint32_t> uniques;
-  uniques.reserve(Entries.size());
-  for (const auto &E : Entries)
-    uniques.push_back(E.second.HashValue);
-  array_pod_sort(uniques.begin(), uniques.end());
-  std::vector<uint32_t>::iterator p =
-      std::unique(uniques.begin(), uniques.end());
-
-  // Compute the hashes count and use it to set that together with the bucket
-  // count in the header.
-  Header.setBucketAndHashCount(std::distance(uniques.begin(), p));
-}
-
-void AppleAccelTableBase::finalizeTable(AsmPrinter *Asm, StringRef Prefix) {
-  // Create the individual hash data outputs.
-  for (auto &E : Entries) {
-    // Unique the entries.
-    std::stable_sort(E.second.Values.begin(), E.second.Values.end(),
-                     [](const AppleAccelTableData *A,
-                        const AppleAccelTableData *B) { return *A < *B; });
-    E.second.Values.erase(
-        std::unique(E.second.Values.begin(), E.second.Values.end()),
-        E.second.Values.end());
-  }
-
-  // Figure out how many buckets we need, then compute the bucket contents and
-  // the final ordering. We'll emit the hashes and offsets by doing a walk
-  // during the emission phase. We add temporary symbols to the data so that we
-  // can reference them during the offset later, we'll emit them when we emit
-  // the data.
-  computeBucketCount();
-
-  // Compute bucket contents and final ordering.
-  Buckets.resize(Header.getBucketCount());
-  for (auto &E : Entries) {
-    uint32_t bucket = E.second.HashValue % Header.getBucketCount();
-    Buckets[bucket].push_back(&E.second);
-    E.second.Sym = Asm->createTempSymbol(Prefix);
-  }
+void AppleEmissionContext::emit() const {
+  Header.emit(Asm);
+  HeaderData.emit(Asm);
+  emitBuckets();
+  emitHashes();
+  emitOffsets(SecBegin);
+  emitData();
 
-  // Sort the contents of the buckets by hash value so that hash collisions end
-  // up together. Stable sort makes testing easier and doesn't cost much more.
-  for (auto &Bucket : Buckets)
-    std::stable_sort(Bucket.begin(), Bucket.end(),
-                     [](HashData *LHS, HashData *RHS) {
-                       return LHS->HashValue < RHS->HashValue;
-                     });
+void detail::emitAppleAccelTable(AsmPrinter *Asm, AccelTableBase &Contents,
+                                 StringRef Prefix, const MCSymbol *SecBegin,
+                                 ArrayRef<AppleAccelTableData::Atom> Atoms) {
+  Contents.finalize(Asm, Prefix);
+  AppleEmissionContext(Asm, Contents, Atoms, SecBegin).emit();
 }
 
 void AppleAccelTableOffsetData::emit(AsmPrinter *Asm) const {
   Asm->EmitInt32(Die->getDebugSectionOffset());
 }
 
 void AppleAccelTableTypeData::emit(AsmPrinter *Asm) const {
   Asm->EmitInt32(Die->getDebugSectionOffset());
void AppleAccelTableStaticTypeData::emit(AsmPrinter *Asm) const {
   Asm->EmitInt16(Tag);
   Asm->EmitInt8(ObjCClassIsImplementation ? dwarf::DW_FLAG_type_implementation
                                           : 0);
   Asm->EmitInt32(QualifiedNameHash);
 }
 
 #ifndef _MSC_VER
 // The lines below are rejected by older versions (TBD) of MSVC.
-constexpr AppleAccelTableHeader::Atom AppleAccelTableTypeData::Atoms[];
-constexpr AppleAccelTableHeader::Atom AppleAccelTableOffsetData::Atoms[];
-constexpr AppleAccelTableHeader::Atom AppleAccelTableStaticOffsetData::Atoms[];
-constexpr AppleAccelTableHeader::Atom AppleAccelTableStaticTypeData::Atoms[];
+constexpr AppleAccelTableData::Atom AppleAccelTableTypeData::Atoms[];
+constexpr AppleAccelTableData::Atom AppleAccelTableOffsetData::Atoms[];
+constexpr AppleAccelTableData::Atom AppleAccelTableStaticOffsetData::Atoms[];
+constexpr AppleAccelTableData::Atom AppleAccelTableStaticTypeData::Atoms[];
 #else
 // FIXME: Erase this path once the minimum MSCV version has been bumped.
-const SmallVector<AppleAccelTableHeader::Atom, 4>
-    AppleAccelTableOffsetData::Atoms = {AppleAccelTableHeader::Atom(
-        dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
-const SmallVector<AppleAccelTableHeader::Atom, 4>
-    AppleAccelTableTypeData::Atoms = {
-        AppleAccelTableHeader::Atom(dwarf::DW_ATOM_die_offset,
-                                    dwarf::DW_FORM_data4),
-        AppleAccelTableHeader::Atom(dwarf::DW_ATOM_die_tag,
-                                    dwarf::DW_FORM_data2),
-        AppleAccelTableHeader::Atom(dwarf::DW_ATOM_type_flags,
-                                    dwarf::DW_FORM_data1)};
-const SmallVector<AppleAccelTableHeader::Atom, 4>
-    AppleAccelTableStaticOffsetData::Atoms = {AppleAccelTableHeader::Atom(
-        dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
-const SmallVector<AppleAccelTableHeader::Atom, 4>
+const SmallVector<AppleAccelTableData::Atom, 4>
+    AppleAccelTableOffsetData::Atoms = {
+        Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
+const SmallVector<AppleAccelTableData::Atom, 4> AppleAccelTableTypeData::Atoms =
+    {Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4),
+     Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2),
+     Atom(dwarf::DW_ATOM_type_flags, dwarf::DW_FORM_data1)};
+const SmallVector<AppleAccelTableData::Atom, 4>
+    AppleAccelTableStaticOffsetData::Atoms = {
+        Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
+const SmallVector<AppleAccelTableData::Atom, 4>
     AppleAccelTableStaticTypeData::Atoms = {
-        AppleAccelTableHeader::Atom(dwarf::DW_ATOM_die_offset,
-                                    dwarf::DW_FORM_data4),
-        AppleAccelTableHeader::Atom(dwarf::DW_ATOM_die_tag,
-                                    dwarf::DW_FORM_data2),
-        AppleAccelTableHeader::Atom(5, dwarf::DW_FORM_data1),
-        AppleAccelTableHeader::Atom(6, dwarf::DW_FORM_data4)};
+        Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4),
+        Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2),
+        Atom(5, dwarf::DW_FORM_data1), Atom(6, dwarf::DW_FORM_data4)};
 #endif
 
 #ifndef NDEBUG
-void AppleAccelTableHeader::Header::print(raw_ostream &OS) const {
+void AppleEmissionContext::Header::print(raw_ostream &OS) const {
   OS << "Magic: " << format("0x%x", Magic) << "\n"
      << "Version: " << Version << "\n"
      << "Hash Function: " << HashFunction << "\n"
      << "Bucket Count: " << BucketCount << "\n"
      << "Header Data Length: " << HeaderDataLength << "\n";
 }
 
-void AppleAccelTableHeader::Atom::print(raw_ostream &OS) const {
+void AppleAccelTableData::Atom::print(raw_ostream &OS) const {
   OS << "Type: " << dwarf::AtomTypeString(Type) << "\n"
      << "Form: " << dwarf::FormEncodingString(Form) << "\n";
 }
 
-void AppleAccelTableHeader::HeaderData::print(raw_ostream &OS) const {
+void AppleEmissionContext::HeaderData::print(raw_ostream &OS) const {
   OS << "DIE Offset Base: " << DieOffsetBase << "\n";
   for (auto Atom : Atoms)
     Atom.print(OS);
 }
 
-void AppleAccelTableHeader::print(raw_ostream &OS) const {
+void AppleEmissionContext::print(raw_ostream &OS) const {
   Header.print(OS);
   HeaderData.print(OS);
+  Contents.print(OS);
+  SecBegin->print(OS, nullptr);
 }
 
-void AppleAccelTableBase::HashData::print(raw_ostream &OS) const {
+void detail::AccelTableBase::HashData::print(raw_ostream &OS) const {
   OS << "Name: " << Name.getString() << "\n";
   OS << "  Hash Value: " << format("0x%x", HashValue) << "\n";
   OS << "  Symbol: ";
   if (Sym)
     OS << *Sym;
   else
     OS << "<none>";
   OS << "\n";
   for (auto *Value : Values)
     Value->print(OS);
 }
 
-void AppleAccelTableBase::print(raw_ostream &OS) const {
-  // Print Header.
-  Header.print(OS);
-
+void detail::AccelTableBase::print(raw_ostream &OS) const {
   // Print Content.
   OS << "Entries: \n";
   for (const auto &Entry : Entries) {
     OS << "Name: " << Entry.first() << "\n";
     for (auto *V : Entry.second.Values)
       V->print(OS);
   }
 

lib/CodeGen/AsmPrinter/DwarfDebug.h

class DwarfDebug : public DebugHandlerBase {
 
   /// True iff there are multiple CUs in this module.
   bool SingleCU;
   bool IsDarwin;
 
   AddressPool AddrPool;
 
   /// Apple accelerator tables.
-  AppleAccelTable<AppleAccelTableOffsetData> AccelNames;
-  AppleAccelTable<AppleAccelTableOffsetData> AccelObjC;
-  AppleAccelTable<AppleAccelTableOffsetData> AccelNamespace;
-  AppleAccelTable<AppleAccelTableTypeData> AccelTypes;
+  AccelTable<AppleAccelTableOffsetData> AccelNames;
+  AccelTable<AppleAccelTableOffsetData> AccelObjC;
+  AccelTable<AppleAccelTableOffsetData> AccelNamespace;
+  AccelTable<AppleAccelTableTypeData> AccelTypes;
 
   // Identify a debugger for "tuning" the debug info.
   DebuggerKind DebuggerTuning = DebuggerKind::Default;
 
   MCDwarfDwoLineTable *getDwoLineTable(const DwarfCompileUnit &);
 
   const SmallVectorImpl<std::unique_ptr<DwarfCompileUnit>> &getUnits() {
     return InfoHolder.getUnits();

lib/CodeGen/AsmPrinter/DwarfDebug.cpp

assert((FrameIndexExprs.size() == 1 ||
                        })) &&
          "conflicting locations for variable");
 }
 
 DwarfDebug::DwarfDebug(AsmPrinter *A, Module *M)
     : DebugHandlerBase(A), DebugLocs(A->OutStreamer->isVerboseAsm()),
       InfoHolder(A, "info_string", DIEValueAllocator),
       SkeletonHolder(A, "skel_string", DIEValueAllocator),
-      IsDarwin(A->TM.getTargetTriple().isOSDarwin()), AccelNames(), AccelObjC(),
-      AccelNamespace(), AccelTypes() {
+      IsDarwin(A->TM.getTargetTriple().isOSDarwin()) {
   const Triple &TT = Asm->TM.getTargetTriple();
 
   // Make sure we know our "debugger tuning."  The target option takes
   // precedence; fall back to triple-based defaults.
   if (Asm->TM.Options.DebuggerTuning != DebuggerKind::Default)
     DebuggerTuning = Asm->TM.Options.DebuggerTuning;
   else if (IsDarwin)
     DebuggerTuning = DebuggerKind::LLDB;
void DwarfDebug::emitStringOffsetsTableHeader() {
   DwarfFile &Holder = useSplitDwarf() ? SkeletonHolder : InfoHolder;
   Holder.emitStringOffsetsTableHeader(
       Asm->getObjFileLowering().getDwarfStrOffSection());
 }
 
 template <typename AccelTableT>
 void DwarfDebug::emitAccel(AccelTableT &Accel, MCSection *Section,
                            StringRef TableName) {
-  Accel.finalizeTable(Asm, TableName);
   Asm->OutStreamer->SwitchSection(Section);
 
   // Emit the full data.
-  Accel.emit(Asm, Section->getBeginSymbol());
+  emitAppleAccelTable(Asm, Accel, TableName, Section->getBeginSymbol());
 }
 
 // Emit visible names into a hashed accelerator table section.
 void DwarfDebug::emitAccelNames() {
   emitAccel(AccelNames, Asm->getObjFileLowering().getDwarfAccelNamesSection(),
             "Names");
 }
 

tools/dsymutil/DwarfLinker.cpp

public:
   /// Emit a CIE.
   void emitCIE(StringRef CIEBytes);
 
   /// Emit an FDE with data \p Bytes.
   void emitFDE(uint32_t CIEOffset, uint32_t AddreSize, uint32_t Address,
                StringRef Bytes);
 
   /// Emit Apple namespaces accelerator table.
-  void
-  emitAppleNamespaces(AppleAccelTable<AppleAccelTableStaticOffsetData> &Table);
+  void emitAppleNamespaces(AccelTable<AppleAccelTableStaticOffsetData> &Table);
 
   /// Emit Apple names accelerator table.
-  void emitAppleNames(AppleAccelTable<AppleAccelTableStaticOffsetData> &Table);
+  void emitAppleNames(AccelTable<AppleAccelTableStaticOffsetData> &Table);
 
   /// Emit Apple Objective-C accelerator table.
-  void emitAppleObjc(AppleAccelTable<AppleAccelTableStaticOffsetData> &Table);
+  void emitAppleObjc(AccelTable<AppleAccelTableStaticOffsetData> &Table);
 
   /// Emit Apple type accelerator table.
-  void emitAppleTypes(AppleAccelTable<AppleAccelTableStaticTypeData> &Table);
+  void emitAppleTypes(AccelTable<AppleAccelTableStaticTypeData> &Table);
 
   uint32_t getFrameSectionSize() const { return FrameSectionSize; }
 };
 
 } // end anonymous namespace
 
 bool DwarfStreamer::init(Triple TheTriple) {
   std::string ErrorStr;
for (auto Entry : Entries) {
     // Emit the string itself.
     Asm->OutStreamer->EmitBytes(Entry.getString());
     // Emit a null terminator.
     Asm->EmitInt8(0);
   }
 }
 
 void DwarfStreamer::emitAppleNamespaces(
-    AppleAccelTable<AppleAccelTableStaticOffsetData> &Table) {
+    AccelTable<AppleAccelTableStaticOffsetData> &Table) {
   Asm->OutStreamer->SwitchSection(MOFI->getDwarfAccelNamespaceSection());
-  Table.finalizeTable(Asm.get(), "namespac");
   auto *SectionBegin = Asm->createTempSymbol("namespac_begin");
   Asm->OutStreamer->EmitLabel(SectionBegin);
-  Table.emit(Asm.get(), SectionBegin);
+  emitAppleAccelTable(Asm.get(), Table, "namespac", SectionBegin);
 }
 
 void DwarfStreamer::emitAppleNames(
-    AppleAccelTable<AppleAccelTableStaticOffsetData> &Table) {
+    AccelTable<AppleAccelTableStaticOffsetData> &Table) {
   Asm->OutStreamer->SwitchSection(MOFI->getDwarfAccelNamesSection());
-  Table.finalizeTable(Asm.get(), "names");
   auto *SectionBegin = Asm->createTempSymbol("names_begin");
   Asm->OutStreamer->EmitLabel(SectionBegin);
-  Table.emit(Asm.get(), SectionBegin);
+  emitAppleAccelTable(Asm.get(), Table, "names", SectionBegin);
 }
 
 void DwarfStreamer::emitAppleObjc(
-    AppleAccelTable<AppleAccelTableStaticOffsetData> &Table) {
+    AccelTable<AppleAccelTableStaticOffsetData> &Table) {
   Asm->OutStreamer->SwitchSection(MOFI->getDwarfAccelObjCSection());
-  Table.finalizeTable(Asm.get(), "objc");
   auto *SectionBegin = Asm->createTempSymbol("objc_begin");
   Asm->OutStreamer->EmitLabel(SectionBegin);
-  Table.emit(Asm.get(), SectionBegin);
+  emitAppleAccelTable(Asm.get(), Table, "objc", SectionBegin);
 }
 
 void DwarfStreamer::emitAppleTypes(
-    AppleAccelTable<AppleAccelTableStaticTypeData> &Table) {
+    AccelTable<AppleAccelTableStaticTypeData> &Table) {
   Asm->OutStreamer->SwitchSection(MOFI->getDwarfAccelTypesSection());
-  Table.finalizeTable(Asm.get(), "types");
   auto *SectionBegin = Asm->createTempSymbol("types_begin");
   Asm->OutStreamer->EmitLabel(SectionBegin);
-  Table.emit(Asm.get(), SectionBegin);
+  emitAppleAccelTable(Asm.get(), Table, "types", SectionBegin);
 }
 
 /// Emit the swift_ast section stored in \p Buffers.
 void DwarfStreamer::emitSwiftAST(StringRef Buffer) {
   MCSection *SwiftASTSection = MOFI->getDwarfSwiftASTSection();
   SwiftASTSection->setAlignment(1 << 5);
   MS->SwitchSection(SwiftASTSection);
   MS->EmitBytes(Buffer);
private:
   /// different object files.
   StringMap<uint32_t> EmittedCIEs;
 
   /// Offset of the last CIE that has been emitted in the output
   /// debug_frame section.
   uint32_t LastCIEOffset = 0;
 
   /// Apple accelerator tables.
-  AppleAccelTable<AppleAccelTableStaticOffsetData> AppleNames;
-  AppleAccelTable<AppleAccelTableStaticOffsetData> AppleNamespaces;
-  AppleAccelTable<AppleAccelTableStaticOffsetData> AppleObjc;
-  AppleAccelTable<AppleAccelTableStaticTypeData> AppleTypes;
+  AccelTable<AppleAccelTableStaticOffsetData> AppleNames;
+  AccelTable<AppleAccelTableStaticOffsetData> AppleNamespaces;
+  AccelTable<AppleAccelTableStaticOffsetData> AppleObjc;
+  AccelTable<AppleAccelTableStaticTypeData> AppleTypes;
 
   /// Mapping the PCM filename to the DwoId.
   StringMap<uint64_t> ClangModules;
 
   bool ModuleCacheHintDisplayed = false;
   bool ArchiveHintDisplayed = false;
 };