[WebAssembly] LTO: Honor comdat groups when loading bitcode files

[sbc100]

Summary

But don't apply comdat groups when loading the LTO object files.
This is basically the same logic used by the ELF linker.

[sbc100]

• comment

[ruiu]

Even though what this code does is the same as what we do for the ELF linker, the code looks different. In ELF, we pass ComdatGroups (which is a set of comdat signature strings we've seen so far) around. I don't remember if there was a reason to do it differently for Wasm. Do you remmeber?

[sbc100]

In D61924#1502458, @ruiu wrote:

Even though what this code does is the same as what we do for the ELF linker, the code looks different. In ELF, we pass ComdatGroups (which is a set of comdat signature strings we've seen so far) around. I don't remember if there was a reason to do it differently for Wasm. Do you remmeber?

I found this version more explicit. ELF currently passes a new DummyGroups to each LTO object's parse function as way of implicitly disabling comdats, but I think explicitly disabling them improves clarity. Perhaps I should change the ELF linker to do the same thing either in this change or as a followup? Alternaitvely I would update this PR to match the ELF method and propose a separate PR to convert them both over as a followup?

[ruiu]

LGTM

Yeah, maybe we should change ELF to match this, but it will likely to conflict with my ongoing refactoring, I'll take a look later about that.

lld/test/wasm/lto/comdat.ll

+; Verify that comdat symbols can be defined in LTO objects.  We had a
+; regression where the comdat handling code was causing symbol in the lto object
+; to be ignored.
+; RUN: llvm-as %s -o %t.o
+; RUN: wasm-ld %t.o %t.o -o %t.wasm
+
+target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
+target triple = "wasm32-unknown-unknown"
+
+$foo = comdat any
+
+define linkonce_odr void @_start() comdat($foo) {
+entry:
+  ret void
+}

lld/wasm/InputFiles.h

public:
   };
 
   virtual ~InputFile() {}
 
   // Returns the filename.
   StringRef getName() const { return MB.getBufferIdentifier(); }
 
   // Reads a file (the constructor doesn't do that).
-  virtual void parse() = 0;
+  virtual void parse(bool IgnoreComdats = false) = 0;
 
   Kind kind() const { return FileKind; }
 
   // An archive file name if this file is created from an archive.
   StringRef ArchiveName;
 
   ArrayRef<Symbol *> getSymbols() const { return Symbols; }
 

 // .a file (ar archive)
 class ArchiveFile : public InputFile {
 public:
   explicit ArchiveFile(MemoryBufferRef M) : InputFile(ArchiveKind, M) {}
   static bool classof(const InputFile *F) { return F->kind() == ArchiveKind; }
 
   void addMember(const llvm::object::Archive::Symbol *Sym);
 
-  void parse() override;
+  void parse(bool IgnoreComdats) override;
 
 private:
   std::unique_ptr<llvm::object::Archive> File;
   llvm::DenseSet<uint64_t> Seen;
 };
 
 // .o file (wasm object file)
 class ObjFile : public InputFile {
 public:
   explicit ObjFile(MemoryBufferRef M, StringRef ArchiveName)
       : InputFile(ObjectKind, M) {
     this->ArchiveName = ArchiveName;
   }
   static bool classof(const InputFile *F) { return F->kind() == ObjectKind; }
 
-  void parse() override;
+  void parse(bool IgnoreComdats) override;
 
   // Returns the underlying wasm file.
   const WasmObjectFile *getWasmObj() const { return WasmObj.get(); }
 
   void dumpInfo() const;
 
   uint32_t calcNewIndex(const WasmRelocation &Reloc) const;
   uint32_t calcNewValue(const WasmRelocation &Reloc) const;
   uint32_t calcNewAddend(const WasmRelocation &Reloc) const;
   uint32_t calcExpectedValue(const WasmRelocation &Reloc) const;
   Symbol *getSymbol(const WasmRelocation &Reloc) const {
     return Symbols[Reloc.Index];
   };
 
   const WasmSection *CodeSection = nullptr;
   const WasmSection *DataSection = nullptr;
 
   // Maps input type indices to output type indices
   std::vector<uint32_t> TypeMap;
   std::vector<bool> TypeIsUsed;
   // Maps function indices to table indices
   std::vector<uint32_t> TableEntries;
-  std::vector<bool> UsedComdats;
+  std::vector<bool> KeptComdats;
   std::vector<InputSegment *> Segments;
   std::vector<InputFunction *> Functions;
   std::vector<InputGlobal *> Globals;
   std::vector<InputEvent *> Events;
   std::vector<InputSection *> CustomSections;
   llvm::DenseMap<uint32_t, InputSection *> CustomSectionsByIndex;
 
   Symbol *getSymbol(uint32_t Index) const { return Symbols[Index]; }

 };
 
 // .so file.
 class SharedFile : public InputFile {
 public:
   explicit SharedFile(MemoryBufferRef M) : InputFile(SharedKind, M) {}
   static bool classof(const InputFile *F) { return F->kind() == SharedKind; }
 
-  void parse() override {}
+  void parse(bool IgnoreComdats) override {}
 };
 
 // .bc file
 class BitcodeFile : public InputFile {
 public:
   explicit BitcodeFile(MemoryBufferRef M, StringRef ArchiveName)
       : InputFile(BitcodeKind, M) {
     this->ArchiveName = ArchiveName;
   }
   static bool classof(const InputFile *F) { return F->kind() == BitcodeKind; }
 
-  void parse() override;
+  void parse(bool IgnoreComdats) override;
   std::unique_ptr<llvm::lto::InputFile> Obj;
 };
 
 // Will report a fatal() error if the input buffer is not a valid bitcode
 // or wasm object file.
 InputFile *createObjectFile(MemoryBufferRef MB, StringRef ArchiveName = "");
 
 // Opens a given file.

lld/wasm/InputFiles.cpp

InputFile *lld::wasm::createObjectFile(MemoryBufferRef MB,
 
   if (Magic == file_magic::bitcode)
     return make<BitcodeFile>(MB, ArchiveName);
 
   fatal("unknown file type: " + MB.getBufferIdentifier());
 }
 
 void ObjFile::dumpInfo() const {
-  log("info for: " + getName() +
+  log("info for: " + toString(this) +
       "\n              Symbols : " + Twine(Symbols.size()) +
       "\n     Function Imports : " + Twine(WasmObj->getNumImportedFunctions()) +
       "\n       Global Imports : " + Twine(WasmObj->getNumImportedGlobals()) +
       "\n        Event Imports : " + Twine(WasmObj->getNumImportedEvents()));
 }
 
 // Relocations contain either symbol or type indices.  This function takes a
 // relocation and returns relocated index (i.e. translates from the input
auto RelocsStart = std::lower_bound(RelocsNext, RelocsEnd,
                                         C->getInputSectionOffset(), RelocLess);
     RelocsNext = std::lower_bound(
         RelocsStart, RelocsEnd, C->getInputSectionOffset() + C->getInputSize(),
         RelocLess);
     C->setRelocations(ArrayRef<WasmRelocation>(RelocsStart, RelocsNext));
   }
 }
 
-void ObjFile::parse() {
+void ObjFile::parse(bool IgnoreComdats) {
   // Parse a memory buffer as a wasm file.
   LLVM_DEBUG(dbgs() << "Parsing object: " << toString(this) << "\n");
   std::unique_ptr<Binary> Bin = CHECK(createBinary(MB), toString(this));
 
   auto *Obj = dyn_cast<WasmObjectFile>(Bin.get());
   if (!Obj)
     fatal(toString(this) + ": not a wasm file");
   if (!Obj->isRelocatableObject())
for (const SectionRef &Sec : WasmObj->sections()) {
     }
     SectionIndex++;
   }
 
   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]);
+    if (IgnoreComdats)
+      KeptComdats.push_back(true);
+    else
+      KeptComdats.push_back(Symtab->addComdat(Comdats[I]));
 
   // Populate `Segments`.
   for (const WasmSegment &S : WasmObj->dataSegments())
     Segments.emplace_back(make<InputSegment>(S, this));
   setRelocs(Segments, DataSection);
 
   // Populate `Functions`.
   ArrayRef<WasmFunction> Funcs = WasmObj->functions();
else
       Symbols.push_back(createUndefined(WasmSym));
   }
 }
 
 bool ObjFile::isExcludedByComdat(InputChunk *Chunk) const {
   uint32_t C = Chunk->getComdat();
   if (C == UINT32_MAX)
     return false;
-  return !UsedComdats[C];
+  return !KeptComdats[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]);
return Symtab->addUndefinedGlobal(Name, Sym.Info.ImportName,
                                       Sym.Info.ImportModule, Flags, this,
                                       Sym.GlobalType);
   case WASM_SYMBOL_TYPE_SECTION:
     llvm_unreachable("section symbols cannot be undefined");
   }
   llvm_unreachable("unknown symbol kind");
 }
 
-void ArchiveFile::parse() {
+void ArchiveFile::parse(bool IgnoreComdats) {
   // Parse a MemoryBufferRef as an archive file.
   LLVM_DEBUG(dbgs() << "Parsing library: " << toString(this) << "\n");
   File = CHECK(Archive::create(MB), toString(this));
 
   // Read the symbol table to construct Lazy symbols.
   int Count = 0;
   for (const Archive::Symbol &Sym : File->symbols()) {
     Symtab->addLazy(this, &Sym);
case GlobalValue::DefaultVisibility:
     return WASM_SYMBOL_VISIBILITY_DEFAULT;
   case GlobalValue::HiddenVisibility:
   case GlobalValue::ProtectedVisibility:
     return WASM_SYMBOL_VISIBILITY_HIDDEN;
   }
   llvm_unreachable("unknown visibility");
 }
 
-static Symbol *createBitcodeSymbol(const lto::InputFile::Symbol &ObjSym,
+static Symbol *createBitcodeSymbol(const std::vector<bool> &KeptComdats,
+                                   const lto::InputFile::Symbol &ObjSym,
                                    BitcodeFile &F) {
   StringRef Name = Saver.save(ObjSym.getName());
 
   uint32_t Flags = ObjSym.isWeak() ? WASM_SYMBOL_BINDING_WEAK : 0;
   Flags |= mapVisibility(ObjSym.getVisibility());
 
-  if (ObjSym.isUndefined()) {
+  int C = ObjSym.getComdatIndex();
+  bool ExcludedByComdat = C != -1 && !KeptComdats[C];
+
+  if (ObjSym.isUndefined() || ExcludedByComdat) {
     if (ObjSym.isExecutable())
       return Symtab->addUndefinedFunction(Name, Name, DefaultModule, Flags, &F,
                                           nullptr);
     return Symtab->addUndefinedData(Name, Flags, &F);
   }
 
   if (ObjSym.isExecutable())
     return Symtab->addDefinedFunction(Name, Flags, &F, nullptr);
   return Symtab->addDefinedData(Name, Flags, &F, nullptr, 0, 0);
 }
 
-void BitcodeFile::parse() {
+void BitcodeFile::parse(bool IgnoreComdats) {
   Obj = check(lto::InputFile::create(MemoryBufferRef(
       MB.getBuffer(), Saver.save(ArchiveName + MB.getBufferIdentifier()))));
   Triple T(Obj->getTargetTriple());
   if (T.getArch() != Triple::wasm32) {
     error(toString(MB.getBufferIdentifier()) + ": machine type must be wasm32");
     return;
   }
+  std::vector<bool> KeptComdats;
+  for (StringRef S : Obj->getComdatTable())
+    if (IgnoreComdats)
+      KeptComdats.push_back(true);
+    else
+      KeptComdats.push_back(Symtab->addComdat(S));
 
   for (const lto::InputFile::Symbol &ObjSym : Obj->symbols())
-    Symbols.push_back(createBitcodeSymbol(ObjSym, *this));
+    Symbols.push_back(createBitcodeSymbol(KeptComdats, ObjSym, *this));
 }
 
 // Returns a string in the format of "foo.o" or "foo.a(bar.o)".
 std::string lld::toString(const wasm::InputFile *File) {
   if (!File)
     return "<internal>";
 
   if (File->ArchiveName.empty())
     return File->getName();
 
   return (File->ArchiveName + "(" + File->getName() + ")").str();
 }

lld/wasm/SymbolTable.h

private:
   // ever added.
   llvm::DenseMap<llvm::CachedHashStringRef, int> SymMap;
   std::vector<Symbol *> SymVector;
 
   // For certain symbols types, e.g. function symbols, we allow for muliple
   // variants of the same symbol with different signatures.
   llvm::DenseMap<llvm::CachedHashStringRef, std::vector<Symbol *>> SymVariants;
 
-  llvm::DenseSet<llvm::CachedHashStringRef> Comdats;
+  // Comdat groups define "link once" sections. If two comdat groups have the
+  // same name, only one of them is linked, and the other is ignored. This set
+  // is used to uniquify them.
+  llvm::DenseSet<llvm::CachedHashStringRef> ComdatGroups;
 
   // For LTO.
   std::unique_ptr<BitcodeCompiler> LTO;
 };
 
 extern SymbolTable *Symtab;
 
 } // namespace wasm
 } // namespace lld
 
 #endif

lld/wasm/SymbolTable.cpp

void SymbolTable::addCombinedLTOObject() {
 
   // Compile bitcode files and replace bitcode symbols.
   LTO.reset(new BitcodeCompiler);
   for (BitcodeFile *F : BitcodeFiles)
     LTO->add(*F);
 
   for (StringRef Filename : LTO->compile()) {
     auto *Obj = make<ObjFile>(MemoryBufferRef(Filename, "lto.tmp"), "");
-    Obj->parse();
+    Obj->parse(true);
     ObjectFiles.push_back(Obj);
   }
 }
 
 void SymbolTable::reportRemainingUndefines() {
   for (Symbol *Sym : SymVector) {
     if (!Sym->isUndefined() || Sym->isWeak())
       continue;
if (S->isWeak()) {
     return;
   }
 
   LLVM_DEBUG(dbgs() << "replacing existing undefined\n");
   File->addMember(Sym);
 }
 
 bool SymbolTable::addComdat(StringRef Name) {
-  return Comdats.insert(CachedHashStringRef(Name)).second;
+  return ComdatGroups.insert(CachedHashStringRef(Name)).second;
 }
 
 // The new signature doesn't match.  Create a variant to the symbol with the
 // signature encoded in the name and return that instead.  These symbols are
 // then unified later in handleSymbolVariants.
 bool SymbolTable::getFunctionVariant(Symbol* Sym, const WasmSignature *Sig,
                                      const InputFile *File, Symbol **Out) {
   LLVM_DEBUG(dbgs() << "getFunctionVariant: " << Sym->getName() << " -> "