[WebAssembly] Avoid COMDAT hashmap lookup for each symbol. NFC

[ncw]

Summary

This reduces the number of lookups to one per COMDAT group, rather than one per symbol in a COMDAT group.

See D44343

[ncw]

I'm hoping this one can be approved too, since it goes along with D44343. Any objections?

[sbc100]

wasm/InputChunks.h

165

I feel like it would be good to have some kind of wasm::kInvalidIndex that we could use here and elsewhere. But thats a separate change.

[ncw]

Thanks!

[ruiu]

LGTM

wasm/InputChunks.h

public:
   uint32_t getSize() const { return data().size(); }
 
   void copyRelocations(const WasmSection &Section);
 
   void writeTo(uint8_t *SectionStart) const;
 
   ArrayRef<WasmRelocation> getRelocations() const { return Relocations; }
 
-  virtual StringRef getComdat() const = 0;
   virtual StringRef getName() const = 0;
+  virtual uint32_t getComdat() const = 0;
+  StringRef getComdatName() const;
 
   size_t NumRelocations() const { return Relocations.size(); }
   void writeRelocations(llvm::raw_ostream &OS) const;
 
   ObjFile *File;
   int32_t OutputOffset = 0;
 
   // Signals that the section is part of the output.  The garbage collector,

 public:
   InputSegment(const WasmSegment &Seg, ObjFile *F)
       : InputChunk(F, InputChunk::DataSegment), Segment(Seg) {}
 
   static bool classof(const InputChunk *C) { return C->kind() == DataSegment; }
 
   uint32_t getAlignment() const { return Segment.Data.Alignment; }
   StringRef getName() const override { return Segment.Data.Name; }
-  StringRef getComdat() const override { return Segment.Data.Comdat; }
+  uint32_t getComdat() const override { return Segment.Data.Comdat; }
 
   const OutputSegment *OutputSeg = nullptr;
   int32_t OutputSegmentOffset = 0;
 
 protected:
   ArrayRef<uint8_t> data() const override { return Segment.Data.Content; }
   uint32_t getInputSectionOffset() const override {
     return Segment.SectionOffset;
InputFunction(const WasmSignature &S, const WasmFunction *Func, ObjFile *F)
       : InputChunk(F, InputChunk::Function), Signature(S), Function(Func) {}
 
   static bool classof(const InputChunk *C) {
     return C->kind() == InputChunk::Function ||
            C->kind() == InputChunk::SyntheticFunction;
   }
 
   StringRef getName() const override { return Function->Name; }
-  StringRef getComdat() const override { return Function->Comdat; }
+  uint32_t getComdat() const override { return Function->Comdat; }
   uint32_t getOutputIndex() const { return OutputIndex.getValue(); }
   bool hasOutputIndex() const { return OutputIndex.hasValue(); }
   void setOutputIndex(uint32_t Index);
   uint32_t getTableIndex() const { return TableIndex.getValue(); }
   bool hasTableIndex() const { return TableIndex.hasValue(); }
   void setTableIndex(uint32_t Index);
 
   const WasmSignature &Signature;
SyntheticFunction(const WasmSignature &S, StringRef Name)
     SectionKind = InputChunk::SyntheticFunction;
   }
 
   static bool classof(const InputChunk *C) {
     return C->kind() == InputChunk::SyntheticFunction;
   }
 
   StringRef getName() const override { return Name; }
-  StringRef getComdat() const override { return StringRef(); }
+  uint32_t getComdat() const override { return UINT32_MAX; }
 
   void setBody(ArrayRef<uint8_t> Body_) { Body = Body_; }
 
 protected:
   ArrayRef<uint8_t> data() const override { return Body; }
 
   StringRef Name;
   ArrayRef<uint8_t> Body;
 };
 
 } // namespace wasm
 
 std::string toString(const wasm::InputChunk *);
 } // namespace lld
 
 #endif // LLD_WASM_INPUT_CHUNKS_H

wasm/InputChunks.cpp

 using namespace llvm::support::endian;
 using namespace lld;
 using namespace lld::wasm;
 
 std::string lld::toString(const InputChunk *C) {
   return (toString(C->File) + ":(" + C->getName() + ")").str();
 }
 
+StringRef InputChunk::getComdatName() const {
+  uint32_t Index = getComdat();
+  if (Index == UINT32_MAX)
+    return StringRef();
+  return File->getWasmObj()->linkingData().Comdats[Index];
+}
+
 void InputChunk::copyRelocations(const WasmSection &Section) {
   if (Section.Relocations.empty())
     return;
   size_t Start = getInputSectionOffset();
   size_t Size = getSize();
   for (const WasmRelocation &R : Section.Relocations)
     if (R.Offset >= Start && R.Offset < Start + Size)
       Relocations.push_back(R);

wasm/InputFiles.h

public:
   uint32_t calcNewIndex(const WasmRelocation &Reloc) const;
   uint32_t calcNewValue(const WasmRelocation &Reloc) const;
 
   const WasmSection *CodeSection = nullptr;
   const WasmSection *DataSection = nullptr;
 
   std::vector<uint32_t> TypeMap;
   std::vector<bool> TypeIsUsed;
+  std::vector<bool> UsedComdats;
   std::vector<InputSegment *> Segments;
   std::vector<InputFunction *> Functions;
   std::vector<InputGlobal *> Globals;
 
   ArrayRef<Symbol *> getSymbols() const { return Symbols; }
   Symbol *getSymbol(uint32_t Index) const { return Symbols[Index]; }
   FunctionSymbol *getFunctionSymbol(uint32_t Index) const;
   DataSymbol *getDataSymbol(uint32_t Index) const;

wasm/InputFiles.cpp

if (Section.Type == WASM_SEC_CODE)
       CodeSection = &Section;
     else if (Section.Type == WASM_SEC_DATA)
       DataSection = &Section;
   }
 
   TypeMap.resize(getWasmObj()->types().size());
   TypeIsUsed.resize(getWasmObj()->types().size(), false);
 
+  ArrayRef<StringRef> Comdats = WasmObj->linkingData().Comdats;
+  UsedComdats.resize(Comdats.size());
+  for (unsigned I = 0; I < Comdats.size(); ++I)
+    UsedComdats[I] = Symtab->addComdat(Comdats[I]);
+
   // Populate `Segments`.
   for (const WasmSegment &S : WasmObj->dataSegments()) {
     InputSegment *Seg = make<InputSegment>(S, this);
     Seg->copyRelocations(*DataSection);
     Segments.emplace_back(Seg);
   }
 
   // Populate `Functions`.
for (const SymbolRef &Sym : WasmObj->symbols()) {
     if (Symbol *Sym = createDefined(WasmSym))
       Symbols.push_back(Sym);
     else
       Symbols.push_back(createUndefined(WasmSym));
   }
 }
 
 bool ObjFile::isExcludedByComdat(InputChunk *Chunk) const {
-  StringRef S = Chunk->getComdat();
-  if (S.empty())
+  uint32_t C = Chunk->getComdat();
+  if (C == UINT32_MAX)
     return false;
-  return !Symtab->addComdat(S, this);
+  return !UsedComdats[C];
 }
 
 FunctionSymbol *ObjFile::getFunctionSymbol(uint32_t Index) const {
   return cast<FunctionSymbol>(Symbols[Index]);
 }
 
 GlobalSymbol *ObjFile::getGlobalSymbol(uint32_t Index) const {
   return cast<GlobalSymbol>(Symbols[Index]);

wasm/SymbolTable.h

 //===- SymbolTable.h --------------------------------------------*- C++ -*-===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_WASM_SYMBOL_TABLE_H
 #define LLD_WASM_SYMBOL_TABLE_H
 
 #include "InputFiles.h"
 #include "Symbols.h"
 #include "llvm/ADT/CachedHashString.h"
-#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/Support/raw_ostream.h"
 
 using llvm::wasm::WasmGlobalType;
 using llvm::wasm::WasmSignature;
 
 namespace lld {
 namespace wasm {
 
public:
   Symbol *addUndefinedFunction(StringRef Name, uint32_t Flags, InputFile *File,
                                const WasmSignature *Signature);
   Symbol *addUndefinedData(StringRef Name, uint32_t Flags, InputFile *File);
   Symbol *addUndefinedGlobal(StringRef Name, uint32_t Flags, InputFile *File,
                              const WasmGlobalType *Type);
 
   void addLazy(ArchiveFile *F, const Archive::Symbol *Sym);
 
-  bool addComdat(StringRef Name, const ObjFile *File);
+  bool addComdat(StringRef Name);
 
   DefinedData *addSyntheticDataSymbol(StringRef Name, uint32_t Flags);
   DefinedGlobal *addSyntheticGlobal(StringRef Name, uint32_t Flags,
                                     InputGlobal *Global);
   DefinedFunction *addSyntheticFunction(StringRef Name, uint32_t Flags,
                                         InputFunction *Function);
 
 private:
   std::pair<Symbol *, bool> insert(StringRef Name);
 
   llvm::DenseMap<llvm::CachedHashStringRef, Symbol *> SymMap;
   std::vector<Symbol *> SymVector;
 
-  llvm::DenseMap<StringRef, const ObjFile *> Comdats;
+  llvm::DenseSet<llvm::CachedHashStringRef> Comdats;
 };
 
 extern SymbolTable *Symtab;
 
 } // namespace wasm
 } // namespace lld
 
 #endif

wasm/SymbolTable.cpp

void SymbolTable::addLazy(ArchiveFile *File, const Archive::Symbol *Sym) {
 
   // If there is an existing undefined symbol, load a new one from the archive.
   if (S->isUndefined()) {
     DEBUG(dbgs() << "replacing existing undefined\n");
     File->addMember(Sym);
   }
 }
 
-bool SymbolTable::addComdat(StringRef Name, const ObjFile *File) {
-  return Comdats.insert({Name, File}).first->second == File;
+bool SymbolTable::addComdat(StringRef Name) {
+  return Comdats.insert(CachedHashStringRef(Name)).second;
 }

wasm/Writer.cpp

void Writer::createLinkingSection() {
 
   struct ComdatEntry {
     unsigned Kind;
     uint32_t Index;
   };
   std::map<StringRef, std::vector<ComdatEntry>> Comdats;
 
   for (const InputFunction *F : InputFunctions) {
-    StringRef Comdat = F->getComdat();
+    StringRef Comdat = F->getComdatName();
     if (!Comdat.empty())
       Comdats[Comdat].emplace_back(
           ComdatEntry{WASM_COMDAT_FUNCTION, F->getOutputIndex()});
   }
   for (uint32_t I = 0; I < Segments.size(); ++I) {
     const auto &InputSegments = Segments[I]->InputSegments;
     if (InputSegments.empty())
       continue;
-    StringRef Comdat = InputSegments[0]->getComdat();
+    StringRef Comdat = InputSegments[0]->getComdatName();
 #ifndef NDEBUG
     for (const InputSegment *IS : InputSegments)
-      assert(IS->getComdat() == Comdat);
+      assert(IS->getComdatName() == Comdat);
 #endif
     if (!Comdat.empty())
       Comdats[Comdat].emplace_back(ComdatEntry{WASM_COMDAT_DATA, I});
   }
 
   if (!Comdats.empty()) {
     SubSection Sub(WASM_COMDAT_INFO);
     writeUleb128(Sub.OS, Comdats.size(), "num comdats");