[WebAssembly] Simplify COMDAT handling.

[ruiu]

Summary

[WebAssembly] Simplify COMDAT handling.

[ruiu]

• simplify addComdat's return type

[sbc100]

Interesting.. I guess it works. Adding @ncw who wrote this code.

[ruiu]

If I understand the existing code correctly, the new code should do exactly the same as before, with less number of hash table lookups.

[ncw]

In my queue of about ~20 patches still to submit, I have got one similar to this! In fact it was discussed a while back in some comments on another issue; I've just built up a big backlog while the symbol table stuff was being worked on.

It's actually possible to optimise it even more; my patch involves editing the BinaryFormat/Wasm.h structures to go from struct Function { ... StringRef Comdat } to struct Function { int Comdat; }.

Then change the loop to for (Comdat : File->Comdats()) { if (add(Comdat)) markComdatIndex(Comdat); }. Then, you only do a hashtable lookup once per Comdat, rather than (in your case) once per symbol, which should be a bit of a saving for a typical inline function comdat that might have some strings or other data in the comdat as well.

I'm happy for this to go in, it's in the right direction I think.

[ruiu]

I think that's a right direction, though that should be done as a separate patch after this.

Your change needs to change llvm/lib/Object/WasmObjectFile.cpp right? One thing I noticed there is that WasmObjectFile::parseLinkingSectionComdat does an expensive test using a set. I don't think that's we want check for name uniqueness in WasmObjectFile.cpp, as it should be a lightweight wrapper to read object files as quickly as possible.

[ncw]

In D43966#1024468, @ruiu wrote:

I think that's a right direction, though that should be done as a separate patch after this.

Your change needs to change llvm/lib/Object/WasmObjectFile.cpp right? One thing I noticed there is that WasmObjectFile::parseLinkingSectionComdat does an expensive test using a set. I don't think that's we want check for name uniqueness in WasmObjectFile.cpp, as it should be a lightweight wrapper to read object files as quickly as possible.

Good point, I can look into getting rid of that at the same time, when I get to submitting that patch.

By the way, I didn't mean to be rude, my last comment might have sounded like "I've done this already and my way's better". I just meant to say what I was working on, for comparison. I think it's great by the way you're working on Wasm-LLD; when Wasm came along was it maybe someone else's idea/initiative? It's good of you to make time in your schedule to work on the Wasm toolchain if you're not using it yourself!

lld/trunk/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);
 
-  for (StringRef Name : WasmObj->comdats())
-    Symtab->addComdat(Name, this);
-
   // 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 Comdat = Chunk->getComdat();
-  return !Comdat.empty() && Symtab->findComdat(Comdat) != this;
+  StringRef S = Chunk->getComdat();
+  if (S.empty())
+    return false;
+  return !Symtab->addComdat(S, this);
 }
 
 FunctionSymbol *ObjFile::getFunctionSymbol(uint32_t Index) const {
   return cast<FunctionSymbol>(Symbols[Index]);
 }
 
 GlobalSymbol *ObjFile::getGlobalSymbol(uint32_t Index) const {
   return cast<GlobalSymbol>(Symbols[Index]);

lld/trunk/wasm/SymbolTable.h

public:
   void addFile(InputFile *File);
 
   std::vector<ObjFile *> ObjectFiles;
 
   void reportRemainingUndefines();
 
   ArrayRef<Symbol *> getSymbols() const { return SymVector; }
   Symbol *find(StringRef Name);
-  ObjFile *findComdat(StringRef Name) const;
 
   Symbol *addDefinedFunction(StringRef Name, uint32_t Flags, InputFile *File,
                              InputFunction *Function);
   Symbol *addDefinedData(StringRef Name, uint32_t Flags, InputFile *File,
                          InputSegment *Segment, uint32_t Address,
                          uint32_t Size);
   Symbol *addDefinedGlobal(StringRef Name, uint32_t Flags, InputFile *File,
                            InputGlobal *G);
 
   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, ObjFile *);
+
+  bool addComdat(StringRef Name, const ObjFile *File);
 
   DefinedData *addSyntheticDataSymbol(StringRef Name, uint32_t Flags);
   DefinedGlobal *addSyntheticGlobal(StringRef Name, uint32_t Flags,
                                     InputGlobal *Global);
   DefinedFunction *addSyntheticFunction(StringRef Name,
                                         const WasmSignature *Type,
                                         uint32_t Flags);
 
 private:
   std::pair<Symbol *, bool> insert(StringRef Name);
 
-  llvm::DenseMap<llvm::CachedHashStringRef, ObjFile *> ComdatMap;
   llvm::DenseMap<llvm::CachedHashStringRef, Symbol *> SymMap;
   std::vector<Symbol *> SymVector;
+
+  llvm::DenseMap<StringRef, const ObjFile *> Comdats;
 };
 
 extern SymbolTable *Symtab;
 
 } // namespace wasm
 } // namespace lld
 
 #endif

lld/trunk/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, ObjFile *F) {
-  DEBUG(dbgs() << "addComdat: " << Name << "\n");
-  ObjFile *&File = ComdatMap[CachedHashStringRef(Name)];
-  if (File) {
-    DEBUG(dbgs() << "COMDAT already defined\n");
-    return false;
-  }
-  File = F;
-  return true;
-}
-
-ObjFile *SymbolTable::findComdat(StringRef Name) const {
-  auto It = ComdatMap.find(CachedHashStringRef(Name));
-  return It == ComdatMap.end() ? nullptr : It->second;
+bool SymbolTable::addComdat(StringRef Name, const ObjFile *File) {
+  return Comdats.insert({Name, File}).first->second == File;
 }