[NFC] Rename DwarfAccelTable and move header. NFC

[JDevlieghere]

Summary

This patch renames DwarfAccelTable.{h,cpp} to AccelTable.{h,cpp} and
moves the header to the include dir so it is accessible by the
dsymutil implementation.

[aprantl]

include/llvm/CodeGen/AccelTable.h

33 ↗

(On Diff #131418)

This should be a file-wide Doxygen comment.

[aprantl]

include/llvm/CodeGen/AccelTable.h

35 ↗

(On Diff #131418)

Replace this sentence with: The Apple accelerator tables are a precursor of the newer DWARF v5 accelerator tables. Both formats share common design ideas.

[aprantl]

More rewording.

[aprantl]

include/llvm/CodeGen/AccelTable.h

69 ↗

(On Diff #131418)

DWARF v5

llvm/trunk/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
+
+#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"
+#include "llvm/MC/MCSymbol.h"
+#include "llvm/Support/Allocator.h"
+#include "llvm/Support/DJB.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/Format.h"
+#include "llvm/Support/raw_ostream.h"
+#include <cstddef>
+#include <cstdint>
+#include <vector>
+
+/// The DWARF and Apple accelerator tables are an indirect hash table optimized
+/// for null lookup rather than access to known data. The Apple accelerator
+/// tables are a precursor of the newer DWARF v5 accelerator tables. Both
+/// formats share common design ideas.
+///
+/// The Apple accelerator table are output into an on-disk format that looks
+/// like this:
+///
+/// .------------------.
+/// |  HEADER          |
+/// |------------------|
+/// |  BUCKETS         |
+/// |------------------|
+/// |  HASHES          |
+/// |------------------|
+/// |  OFFSETS         |
+/// |------------------|
+/// |  DATA            |
+/// `------------------'
+///
+/// The header contains a magic number, version, type of hash function,
+/// the number of buckets, total number of hashes, and room for a special struct
+/// of data and the length of that struct.
+///
+/// The buckets contain an index (e.g. 6) into the hashes array. The hashes
+/// section contains all of the 32-bit hash values in contiguous memory, and the
+/// offsets contain the offset into the data area for the particular hash.
+///
+/// For a lookup example, we could hash a function name and take it modulo the
+/// number of buckets giving us our bucket. From there we take the bucket value
+/// as an index into the hashes table and look at each successive hash as long
+/// as the hash value is still the same modulo result (bucket value) as earlier.
+/// If we have a match we look at that same entry in the offsets table and grab
+/// the offset in the data for our final match.
+///
+/// The DWARFv5 accelerator table consists of zero or more name indices that
+/// are output into an on-disk format that looks like this:
+///
+/// .------------------.
+/// |  HEADER          |
+/// |------------------|
+/// |  CU LIST         |
+/// |------------------|
+/// |  LOCAL TU LIST   |
+/// |------------------|
+/// |  FOREIGN TU LIST |
+/// |------------------|
+/// |  HASH TABLE      |
+/// |------------------|
+/// |  NAME TABLE      |
+/// |------------------|
+/// |  ABBREV TABLE    |
+/// |------------------|
+/// |  ENTRY POOL      |
+/// `------------------'
+///
+/// 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 {
+      OS << "Magic: " << format("0x%x", Magic) << "\n"
+         << "Version: " << Version << "\n"
+         << "Hash Function: " << HashFunction << "\n"
+         << "Bucket Count: " << BucketCount << "\n"
+         << "Header Data Length: " << HeaderDataLength << "\n";
+    }
+
+    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 {
+      OS << "Type: " << dwarf::AtomTypeString(Type) << "\n"
+         << "Form: " << dwarf::FormEncodingString(Form) << "\n";
+    }
+
+    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;
+
+    SmallVector<Atom, 3> Atoms;
+
+    HeaderData(ArrayRef<Atom> AtomList, uint32_t Offset = 0)
+        : DieOffsetBase(Offset), Atoms(AtomList.begin(), AtomList.end()) {}
+
+#ifndef NDEBUG
+    void print(raw_ostream &OS) const {
+      OS << "DIE Offset Base: " << DieOffsetBase << "\n";
+      for (auto Atom : Atoms)
+        Atom.print(OS);
+    }
+
+    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.
+  AppleAccelTableHeader(ArrayRef<AppleAccelTableHeader::Atom> Atoms)
+      : Header(8 + (Atoms.size() * 4)), HeaderData(Atoms) {}
+
+  /// 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 {
+    Header.print(OS);
+    HeaderData.print(OS);
+  }
+
+  void dump() const { print(dbgs()); }
+#endif
+};
+
+/// Interface which the different types of accelerator table data have to
+/// conform.
+class AppleAccelTableData {
+public:
+  virtual ~AppleAccelTableData() = default;
+
+  virtual void emit(AsmPrinter *Asm) const = 0;
+
+  bool operator<(const AppleAccelTableData &Other) const {
+    return order() < Other.order();
+  }
+
+#ifndef NDEBUG
+  virtual void print(raw_ostream &OS) const = 0;
+#endif
+protected:
+  virtual uint64_t order() const;
+};
+
+/// Apple-style accelerator table base class.
+class AppleAccelTableBase {
+protected:
+  struct DataArray {
+    DwarfStringPoolEntryRef Name;
+    std::vector<AppleAccelTableData *> Values;
+  };
+
+  friend struct HashData;
+
+  struct HashData {
+    StringRef Str;
+    uint32_t HashValue;
+    MCSymbol *Sym;
+    DataArray &Data;
+
+    HashData(StringRef S, DataArray &Data) : Str(S), Data(Data) {
+      HashValue = djbHash(S);
+    }
+
+#ifndef NDEBUG
+    void print(raw_ostream &OS) {
+      OS << "Name: " << Str << "\n";
+      OS << "  Hash Value: " << format("0x%x", HashValue) << "\n";
+      OS << "  Symbol: ";
+      if (Sym)
+        OS << *Sym;
+      else
+        OS << "<none>";
+      OS << "\n";
+      for (auto *Value : Data.Values)
+        Value->print(OS);
+    }
+
+    void dump() { print(dbgs()); }
+#endif
+  };
+
+  /// Allocator for HashData and Values.
+  BumpPtrAllocator Allocator;
+
+  /// Header containing both the header and header data.
+  AppleAccelTableHeader Header;
+
+  std::vector<HashData *> Data;
+
+  using StringEntries = StringMap<DataArray, BumpPtrAllocator &>;
+  StringEntries Entries;
+
+  using HashList = std::vector<HashData *>;
+  HashList Hashes;
+
+  using BucketList = std::vector<HashList>;
+  BucketList Buckets;
+
+  AppleAccelTableBase(ArrayRef<AppleAccelTableHeader::Atom> Atoms)
+      : Header(Atoms), Entries(Allocator) {}
+
+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 *);
+
+public:
+  void finalizeTable(AsmPrinter *, StringRef);
+
+  void emit(AsmPrinter *Asm, const MCSymbol *SecBegin) {
+    emitHeader(Asm);
+    emitBuckets(Asm);
+    emitHashes(Asm);
+    emitOffsets(Asm, SecBegin);
+    emitData(Asm);
+  }
+
+#ifndef NDEBUG
+  void print(raw_ostream &OS) const {
+    // Print Header.
+    Header.print(OS);
+
+    // Print Content.
+    OS << "Entries: \n";
+    for (const auto &Entry : Entries) {
+      OS << "Name: " << Entry.first() << "\n";
+      for (auto *V : Entry.second.Values)
+        V->print(OS);
+    }
+
+    OS << "Buckets and Hashes: \n";
+    for (auto &Bucket : Buckets)
+      for (auto &Hash : Bucket)
+        Hash->print(OS);
+
+    OS << "Data: \n";
+    for (auto &D : Data)
+      D->print(OS);
+  }
+  void dump() const { print(dbgs()); }
+#endif
+};
+
+template <typename AppleAccelTableDataT>
+class AppleAccelTable : public AppleAccelTableBase {
+public:
+  AppleAccelTable() : AppleAccelTableBase(AppleAccelTableDataT::Atoms) {}
+  AppleAccelTable(const AppleAccelTable &) = delete;
+  AppleAccelTable &operator=(const AppleAccelTable &) = delete;
+
+  template <class... Types>
+  void addName(DwarfStringPoolEntryRef Name, Types... Args);
+};
+
+template <typename AppleAccelTableDataT>
+template <class... Types>
+void AppleAccelTable<AppleAccelTableDataT>::addName(
+    DwarfStringPoolEntryRef Name, Types... Args) {
+  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 &DA = Entries[Name.getString()];
+  assert(!DA.Name || DA.Name == Name);
+  DA.Name = Name;
+  DA.Values.push_back(new (Allocator) AppleAccelTableDataT(Args...));
+}
+
+/// Accelerator table data implementation for simple accelerator tables with
+/// just a DIE reference.
+class AppleAccelTableOffsetData : public AppleAccelTableData {
+public:
+  AppleAccelTableOffsetData(const DIE *D) : Die(D) {}
+
+  void emit(AsmPrinter *Asm) const override;
+
+  static constexpr AppleAccelTableHeader::Atom Atoms[] = {
+      AppleAccelTableHeader::Atom(dwarf::DW_ATOM_die_offset,
+                                  dwarf::DW_FORM_data4)};
+
+#ifndef NDEBUG
+  void print(raw_ostream &OS) const override {
+    OS << "  Offset: " << Die->getOffset() << "\n";
+  }
+
+#endif
+protected:
+  uint64_t order() const override { return Die->getOffset(); }
+
+  const DIE *Die;
+};
+
+/// Accelerator table data implementation for type accelerator tables.
+class AppleAccelTableTypeData : public AppleAccelTableOffsetData {
+public:
+  AppleAccelTableTypeData(const DIE *D) : AppleAccelTableOffsetData(D) {}
+
+  void emit(AsmPrinter *Asm) const override;
+
+  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)};
+
+#ifndef NDEBUG
+  void print(raw_ostream &OS) const override {
+    OS << "  Offset: " << Die->getOffset() << "\n";
+    OS << "  Tag: " << dwarf::TagString(Die->getTag()) << "\n";
+  }
+#endif
+};
+
+} // end namespace llvm
+
+#endif // LLVM_LIB_CODEGEN_ASMPRINTER_DWARFACCELTABLE_H

llvm/trunk/lib/CodeGen/AsmPrinter/AccelTable.cpp

+//===- llvm/CodeGen/AsmPrinter/AccelTable.cpp - Accelerator Tables --------===//
+//
+//                     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.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/AccelTable.h"
+#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/Support/raw_ostream.h"
+#include <algorithm>
+#include <cstddef>
+#include <cstdint>
+#include <limits>
+#include <vector>
+
+using namespace llvm;
+
+void AppleAccelTableHeader::emit(AsmPrinter *Asm) {
+  // Emit Header.
+  Asm->OutStreamer->AddComment("Header Magic");
+  Asm->EmitInt32(Header.Magic);
+  Asm->OutStreamer->AddComment("Header Version");
+  Asm->EmitInt16(Header.Version);
+  Asm->OutStreamer->AddComment("Header Hash Function");
+  Asm->EmitInt16(Header.HashFunction);
+  Asm->OutStreamer->AddComment("Header Bucket Count");
+  Asm->EmitInt32(Header.BucketCount);
+  Asm->OutStreamer->AddComment("Header Hash Count");
+  Asm->EmitInt32(Header.HashCount);
+  Asm->OutStreamer->AddComment("Header Data Length");
+  Asm->EmitInt32(Header.HeaderDataLength);
+
+  //  Emit Header Data
+  Asm->OutStreamer->AddComment("HeaderData Die Offset Base");
+  Asm->EmitInt32(HeaderData.DieOffsetBase);
+  Asm->OutStreamer->AddComment("HeaderData Atom Count");
+  Asm->EmitInt32(HeaderData.Atoms.size());
+
+  for (size_t i = 0; i < HeaderData.Atoms.size(); i++) {
+    Atom A = HeaderData.Atoms[i];
+    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;
+}
+
+constexpr AppleAccelTableHeader::Atom AppleAccelTableTypeData::Atoms[];
+constexpr AppleAccelTableHeader::Atom AppleAccelTableOffsetData::Atoms[];
+
+void AppleAccelTableBase::emitHeader(AsmPrinter *Asm) { Header.emit(Asm); }
+
+void AppleAccelTableBase::emitBuckets(AsmPrinter *Asm) {
+  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) {
+  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->Str);
+      Asm->emitDwarfStringOffset(Hash->Data.Name);
+      Asm->OutStreamer->AddComment("Num DIEs");
+      Asm->EmitInt32(Hash->Data.Values.size());
+      for (const auto *V : Hash->Data.Values) {
+        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(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());
+
+  // 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.
+  Data.reserve(Entries.size());
+  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());
+
+    HashData *Entry = new (Allocator) HashData(E.first(), E.second);
+    Data.push_back(Entry);
+  }
+
+  // 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 &D : Data) {
+    uint32_t bucket = D->HashValue % Header.getBucketCount();
+    Buckets[bucket].push_back(D);
+    D->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;
+                     });
+}
+
+void AppleAccelTableOffsetData::emit(AsmPrinter *Asm) const {
+  Asm->EmitInt32(Die->getDebugSectionOffset());
+}
+
+void AppleAccelTableTypeData::emit(AsmPrinter *Asm) const {
+  Asm->EmitInt32(Die->getDebugSectionOffset());
+  Asm->EmitInt16(Die->getTag());
+  Asm->EmitInt8(0);
+}

llvm/trunk/lib/CodeGen/AsmPrinter/CMakeLists.txt

 add_llvm_library(LLVMAsmPrinter
+  AccelTable.cpp
   AddressPool.cpp
   ARMException.cpp
   AsmPrinter.cpp
   AsmPrinterDwarf.cpp
   AsmPrinterInlineAsm.cpp
   DbgValueHistoryCalculator.cpp
   DebugHandlerBase.cpp
   DebugLocStream.cpp
   DIE.cpp
   DIEHash.cpp
-  DwarfAccelTable.cpp
   DwarfCFIException.cpp
   DwarfCompileUnit.cpp
   DwarfDebug.cpp
   DwarfExpression.cpp
   DwarfFile.cpp
   DwarfStringPool.cpp
   DwarfUnit.cpp
   EHStreamer.cpp

llvm/trunk/lib/CodeGen/AsmPrinter/DwarfAccelTable.h

-//==- llvm/CodeGen/DwarfAccelTable.h - Dwarf 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 dwarf accelerator tables.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_LIB_CODEGEN_ASMPRINTER_DWARFACCELTABLE_H
-#define LLVM_LIB_CODEGEN_ASMPRINTER_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"
-#include "llvm/MC/MCSymbol.h"
-#include "llvm/Support/Allocator.h"
-#include "llvm/Support/DJB.h"
-#include "llvm/Support/Debug.h"
-#include "llvm/Support/Format.h"
-#include "llvm/Support/raw_ostream.h"
-#include <cstddef>
-#include <cstdint>
-#include <vector>
-
-// The dwarf accelerator tables are an indirect hash table optimized
-// for null lookup rather than access to known data. They are output into
-// an on-disk format that looks like this:
-//
-// .-------------.
-// |  HEADER     |
-// |-------------|
-// |  BUCKETS    |
-// |-------------|
-// |  HASHES     |
-// |-------------|
-// |  OFFSETS    |
-// |-------------|
-// |  DATA       |
-// `-------------'
-//
-// where the header contains a magic number, version, type of hash function,
-// the number of buckets, total number of hashes, and room for a special
-// struct of data and the length of that struct.
-//
-// The buckets contain an index (e.g. 6) into the hashes array. The hashes
-// section contains all of the 32-bit hash values in contiguous memory, and
-// the offsets contain the offset into the data area for the particular
-// hash.
-//
-// For a lookup example, we could hash a function name and take it modulo the
-// number of buckets giving us our bucket. From there we take the bucket value
-// as an index into the hashes table and look at each successive hash as long
-// as the hash value is still the same modulo result (bucket value) as earlier.
-// If we have a match we look at that same entry in the offsets table and
-// grab the offset in the data for our final match.
-
-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 {
-      OS << "Magic: " << format("0x%x", Magic) << "\n"
-         << "Version: " << Version << "\n"
-         << "Hash Function: " << HashFunction << "\n"
-         << "Bucket Count: " << BucketCount << "\n"
-         << "Header Data Length: " << HeaderDataLength << "\n";
-    }
-
-    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 {
-      OS << "Type: " << dwarf::AtomTypeString(Type) << "\n"
-         << "Form: " << dwarf::FormEncodingString(Form) << "\n";
-    }
-
-    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;
-
-    SmallVector<Atom, 3> Atoms;
-
-    HeaderData(ArrayRef<Atom> AtomList, uint32_t Offset = 0)
-        : DieOffsetBase(Offset), Atoms(AtomList.begin(), AtomList.end()) {}
-
-#ifndef NDEBUG
-    void print(raw_ostream &OS) const {
-      OS << "DIE Offset Base: " << DieOffsetBase << "\n";
-      for (auto Atom : Atoms)
-        Atom.print(OS);
-    }
-
-    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.
-  AppleAccelTableHeader(ArrayRef<AppleAccelTableHeader::Atom> Atoms)
-      : Header(8 + (Atoms.size() * 4)), HeaderData(Atoms) {}
-
-  /// 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 {
-    Header.print(OS);
-    HeaderData.print(OS);
-  }
-
-  void dump() const { print(dbgs()); }
-#endif
-};
-
-/// Interface which the different types of accelerator table data have to
-/// conform.
-class AppleAccelTableData {
-public:
-  virtual ~AppleAccelTableData() = default;
-
-  virtual void emit(AsmPrinter *Asm) const = 0;
-
-  bool operator<(const AppleAccelTableData &Other) const {
-    return order() < Other.order();
-  }
-
-#ifndef NDEBUG
-  virtual void print(raw_ostream &OS) const = 0;
-#endif
-protected:
-  virtual uint64_t order() const;
-};
-
-/// Apple-style accelerator table base class.
-class AppleAccelTableBase {
-protected:
-  struct DataArray {
-    DwarfStringPoolEntryRef Name;
-    std::vector<AppleAccelTableData *> Values;
-  };
-
-  friend struct HashData;
-
-  struct HashData {
-    StringRef Str;
-    uint32_t HashValue;
-    MCSymbol *Sym;
-    DataArray &Data;
-
-    HashData(StringRef S, DataArray &Data) : Str(S), Data(Data) {
-      HashValue = djbHash(S);
-    }
-
-#ifndef NDEBUG
-    void print(raw_ostream &OS) {
-      OS << "Name: " << Str << "\n";
-      OS << "  Hash Value: " << format("0x%x", HashValue) << "\n";
-      OS << "  Symbol: ";
-      if (Sym)
-        OS << *Sym;
-      else
-        OS << "<none>";
-      OS << "\n";
-      for (auto *Value : Data.Values)
-        Value->print(OS);
-    }
-
-    void dump() { print(dbgs()); }
-#endif
-  };
-
-  /// Allocator for HashData and Values.
-  BumpPtrAllocator Allocator;
-
-  /// Header containing both the header and header data.
-  AppleAccelTableHeader Header;
-
-  std::vector<HashData *> Data;
-
-  using StringEntries = StringMap<DataArray, BumpPtrAllocator &>;
-  StringEntries Entries;
-
-  using HashList = std::vector<HashData *>;
-  HashList Hashes;
-
-  using BucketList = std::vector<HashList>;
-  BucketList Buckets;
-
-  AppleAccelTableBase(ArrayRef<AppleAccelTableHeader::Atom> Atoms)
-      : Header(Atoms), Entries(Allocator) {}
-
-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 *);
-
-public:
-  void finalizeTable(AsmPrinter *, StringRef);
-
-  void emit(AsmPrinter *Asm, const MCSymbol *SecBegin) {
-    emitHeader(Asm);
-    emitBuckets(Asm);
-    emitHashes(Asm);
-    emitOffsets(Asm, SecBegin);
-    emitData(Asm);
-  }
-
-#ifndef NDEBUG
-  void print(raw_ostream &OS) const {
-    // Print Header.
-    Header.print(OS);
-
-    // Print Content.
-    OS << "Entries: \n";
-    for (const auto &Entry : Entries) {
-      OS << "Name: " << Entry.first() << "\n";
-      for (auto *V : Entry.second.Values)
-        V->print(OS);
-    }
-
-    OS << "Buckets and Hashes: \n";
-    for (auto &Bucket : Buckets)
-      for (auto &Hash : Bucket)
-        Hash->print(OS);
-
-    OS << "Data: \n";
-    for (auto &D : Data)
-      D->print(OS);
-  }
-  void dump() const { print(dbgs()); }
-#endif
-};
-
-template <typename AppleAccelTableDataT>
-class AppleAccelTable : public AppleAccelTableBase {
-public:
-  AppleAccelTable() : AppleAccelTableBase(AppleAccelTableDataT::Atoms) {}
-  AppleAccelTable(const AppleAccelTable &) = delete;
-  AppleAccelTable &operator=(const AppleAccelTable &) = delete;
-
-  template <class... Types>
-  void addName(DwarfStringPoolEntryRef Name, Types... Args);
-};
-
-template <typename AppleAccelTableDataT>
-template <class... Types>
-void AppleAccelTable<AppleAccelTableDataT>::addName(
-    DwarfStringPoolEntryRef Name, Types... Args) {
-  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 &DA = Entries[Name.getString()];
-  assert(!DA.Name || DA.Name == Name);
-  DA.Name = Name;
-  DA.Values.push_back(new (Allocator) AppleAccelTableDataT(Args...));
-}
-
-/// Accelerator table data implementation for simple accelerator tables with
-/// just a DIE reference.
-class AppleAccelTableOffsetData : public AppleAccelTableData {
-public:
-  AppleAccelTableOffsetData(const DIE *D) : Die(D) {}
-
-  void emit(AsmPrinter *Asm) const override;
-
-  static constexpr AppleAccelTableHeader::Atom Atoms[] = {
-      AppleAccelTableHeader::Atom(dwarf::DW_ATOM_die_offset,
-                                  dwarf::DW_FORM_data4)};
-
-#ifndef NDEBUG
-  void print(raw_ostream &OS) const override {
-    OS << "  Offset: " << Die->getOffset() << "\n";
-  }
-
-#endif
-protected:
-  uint64_t order() const override { return Die->getOffset(); }
-
-  const DIE *Die;
-};
-
-/// Accelerator table data implementation for type accelerator tables.
-class AppleAccelTableTypeData : public AppleAccelTableOffsetData {
-public:
-  AppleAccelTableTypeData(const DIE *D) : AppleAccelTableOffsetData(D) {}
-
-  void emit(AsmPrinter *Asm) const override;
-
-  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)};
-
-#ifndef NDEBUG
-  void print(raw_ostream &OS) const override {
-    OS << "  Offset: " << Die->getOffset() << "\n";
-    OS << "  Tag: " << dwarf::TagString(Die->getTag()) << "\n";
-  }
-#endif
-};
-
-} // end namespace llvm
-
-#endif // LLVM_LIB_CODEGEN_ASMPRINTER_DWARFACCELTABLE_H

llvm/trunk/lib/CodeGen/AsmPrinter/DwarfAccelTable.cpp

-//===- llvm/CodeGen/DwarfAccelTable.cpp - Dwarf Accelerator Tables --------===//
-//
-//                     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 dwarf accelerator tables.
-//
-//===----------------------------------------------------------------------===//
-
-#include "DwarfAccelTable.h"
-#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/Support/raw_ostream.h"
-#include <algorithm>
-#include <cstddef>
-#include <cstdint>
-#include <limits>
-#include <vector>
-
-using namespace llvm;
-
-void AppleAccelTableHeader::emit(AsmPrinter *Asm) {
-  // Emit Header.
-  Asm->OutStreamer->AddComment("Header Magic");
-  Asm->EmitInt32(Header.Magic);
-  Asm->OutStreamer->AddComment("Header Version");
-  Asm->EmitInt16(Header.Version);
-  Asm->OutStreamer->AddComment("Header Hash Function");
-  Asm->EmitInt16(Header.HashFunction);
-  Asm->OutStreamer->AddComment("Header Bucket Count");
-  Asm->EmitInt32(Header.BucketCount);
-  Asm->OutStreamer->AddComment("Header Hash Count");
-  Asm->EmitInt32(Header.HashCount);
-  Asm->OutStreamer->AddComment("Header Data Length");
-  Asm->EmitInt32(Header.HeaderDataLength);
-
-  //  Emit Header Data
-  Asm->OutStreamer->AddComment("HeaderData Die Offset Base");
-  Asm->EmitInt32(HeaderData.DieOffsetBase);
-  Asm->OutStreamer->AddComment("HeaderData Atom Count");
-  Asm->EmitInt32(HeaderData.Atoms.size());
-
-  for (size_t i = 0; i < HeaderData.Atoms.size(); i++) {
-    Atom A = HeaderData.Atoms[i];
-    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;
-}
-
-constexpr AppleAccelTableHeader::Atom AppleAccelTableTypeData::Atoms[];
-constexpr AppleAccelTableHeader::Atom AppleAccelTableOffsetData::Atoms[];
-
-void AppleAccelTableBase::emitHeader(AsmPrinter *Asm) { Header.emit(Asm); }
-
-void AppleAccelTableBase::emitBuckets(AsmPrinter *Asm) {
-  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) {
-  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->Str);
-      Asm->emitDwarfStringOffset(Hash->Data.Name);
-      Asm->OutStreamer->AddComment("Num DIEs");
-      Asm->EmitInt32(Hash->Data.Values.size());
-      for (const auto *V : Hash->Data.Values) {
-        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(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());
-
-  // 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.
-  Data.reserve(Entries.size());
-  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());
-
-    HashData *Entry = new (Allocator) HashData(E.first(), E.second);
-    Data.push_back(Entry);
-  }
-
-  // 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 &D : Data) {
-    uint32_t bucket = D->HashValue % Header.getBucketCount();
-    Buckets[bucket].push_back(D);
-    D->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;
-                     });
-}
-
-void AppleAccelTableOffsetData::emit(AsmPrinter *Asm) const {
-  Asm->EmitInt32(Die->getDebugSectionOffset());
-}
-
-void AppleAccelTableTypeData::emit(AsmPrinter *Asm) const {
-  Asm->EmitInt32(Die->getDebugSectionOffset());
-  Asm->EmitInt16(Die->getTag());
-  Asm->EmitInt8(0);
-}

llvm/trunk/lib/CodeGen/AsmPrinter/DwarfDebug.h

 
 #ifndef LLVM_LIB_CODEGEN_ASMPRINTER_DWARFDEBUG_H
 #define LLVM_LIB_CODEGEN_ASMPRINTER_DWARFDEBUG_H
 
 #include "AddressPool.h"
 #include "DbgValueHistoryCalculator.h"
 #include "DebugHandlerBase.h"
 #include "DebugLocStream.h"
-#include "DwarfAccelTable.h"
 #include "DwarfFile.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/BinaryFormat/Dwarf.h"
+#include "llvm/CodeGen/AccelTable.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/DebugLoc.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/MC/MCDwarf.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Target/TargetOptions.h"
 #include <cassert>

llvm/trunk/lib/CodeGen/AsmPrinter/DwarfDebug.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "DwarfDebug.h"
 #include "ByteStreamer.h"
 #include "DIEHash.h"
 #include "DebugLocEntry.h"
 #include "DebugLocStream.h"
-#include "DwarfAccelTable.h"
 #include "DwarfCompileUnit.h"
 #include "DwarfExpression.h"
 #include "DwarfFile.h"
 #include "DwarfUnit.h"
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/BinaryFormat/Dwarf.h"
+#include "llvm/CodeGen/AccelTable.h"
 #include "llvm/CodeGen/AsmPrinter.h"
 #include "llvm/CodeGen/DIE.h"
 #include "llvm/CodeGen/LexicalScopes.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/MachineOperand.h"