[CodeGen] Optimize AccelTable

[labath]

Summary

The class contained arrays of two structures (DataArray and HashData).
These structures were in 1:1 correspondence, and one of them contained
pointers to the other (and *both* contained a "Name" field). By merging
these two structures into one, we can save a bit of space without
negatively impacting much of anything.

[JDevlieghere]

Thanks! I had noticed this too when doing the refactoring earlier, but hadn't gotten around to looking into it yet.

[labath]

llvm/trunk/include/llvm/CodeGen/AccelTable.h

239 ↗

(On Diff #133572)

I see one more (and possibly bigger) improvement that we can make here:
This string map will store a copy of the string from the HashData structure (along with it's hash, which it will need to recompute). However, HashData already contains a hash *and* the string, which has even been uniqued by the dwarf string pool.

So, we could store the HashData in a DenseMap (with a custom DenseMapInfo) and save both space (no string copies) and time (efficient equality comparison).

The only additional requirement here would be that all the DwarfStringPoolEntryRefs come from a single string pool. As far as I can tell, this is already the case (and I can't imagine why one would do it differently), but I don't see a way to enforce that in code.

WDYT?

include/llvm/CodeGen/AccelTable.h

 #endif
 protected:
   virtual uint64_t order() const = 0;
 };
 
 /// Apple-style accelerator table base class.
 class AppleAccelTableBase {
 protected:
-  struct DataArray {
-    DwarfStringPoolEntryRef Name;
-    std::vector<AppleAccelTableData *> Values;
-  };
-
-  friend struct HashData;
-
   struct HashData {
-    StringRef Str;
+    DwarfStringPoolEntryRef Name;
     uint32_t HashValue;
+    std::vector<AppleAccelTableData *> Values;
     MCSymbol *Sym;
-    DataArray &Data;
 
-    HashData(StringRef S, DataArray &Data) : Str(S), Data(Data) {
-      HashValue = djbHash(S);
+    HashData(DwarfStringPoolEntryRef Name) : Name(Name) {
+      HashValue = djbHash(Name.getString());
     }
 
 #ifndef NDEBUG
-    void print(raw_ostream &OS);
-    void dump() { print(dbgs()); }
+    void print(raw_ostream &OS) const;
+    void dump() const { 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 &>;
+  using StringEntries = StringMap<HashData, BumpPtrAllocator &>;
   StringEntries Entries;
 
   using HashList = std::vector<HashData *>;
   HashList Hashes;
 
   using BucketList = std::vector<HashList>;
   BucketList Buckets;
 
public:
   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!");
+  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.
-  DataArray &DA = Entries[Name.getString()];
-  assert(!DA.Name || DA.Name == Name);
-  DA.Name = Name;
-  DA.Values.push_back(new (Allocator) AppleAccelTableDataT(Args...));
+  auto Iter = Entries.try_emplace(Name.getString(), Name).first;
+  assert(Iter->second.Name == Name);
+  Iter->second.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) {}
 

lib/CodeGen/AsmPrinter/AccelTable.cpp

for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
     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(Hash->Name.getString());
+      Asm->emitDwarfStringOffset(Hash->Name);
       Asm->OutStreamer->AddComment("Num DIEs");
-      Asm->EmitInt32(Hash->Data.Values.size());
-      for (const auto *V : Hash->Data.Values) {
+      Asm->EmitInt32(Hash->Values.size());
+      for (const auto *V : Hash->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;
+  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.
-  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);
+  for (auto &E : Entries) {
+    uint32_t bucket = E.second.HashValue % Header.getBucketCount();
+    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;
for (auto Atom : Atoms)
     Atom.print(OS);
 }
 
 void AppleAccelTableHeader::print(raw_ostream &OS) const {
   Header.print(OS);
   HeaderData.print(OS);
 }
 
-void AppleAccelTableBase::HashData::print(raw_ostream &OS) {
-  OS << "Name: " << Str << "\n";
+void AppleAccelTableBase::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 : Data.Values)
+  for (auto *Value : Values)
     Value->print(OS);
 }
 
 void AppleAccelTableBase::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);
+  for (auto &E : Entries)
+    E.second.print(OS);
 }
 
 void AppleAccelTableOffsetData::print(raw_ostream &OS) const {
   OS << "  Offset: " << Die->getOffset() << "\n";
 }
 
 void AppleAccelTableTypeData::print(raw_ostream &OS) const {
   OS << "  Offset: " << Die->getOffset() << "\n";