[WebAssembly] COMDAT: LLD support

[ncw]

Summary

See https://bugs.llvm.org/show_bug.cgi?id=35533, and D40844

Things covered:

• Removing duplicate data segments (as determined by COMDATs emitted by the frontend)
• Removing duplicate globals and functions in COMDATs
• Checking that each time a COMDAT is seen it has the same symbols as at other times (ie it's a stronger check than simply giving all the symbols in the COMDAT weak linkage)

[ruiu]

I just skimmed through the code, but it looks like what this code does is different from ELF. Is there a reason to be different?

[sbc100]

I create a patch based partially on this one that just does the compression of the function table. https://reviews.llvm.org/D40989.
Hopefully that means this can be rebased into a smaller change.

[ncw]

Updates:

• Added test
• Rebased on top of Sam's table deduplication
• Added name-to-segment map to avoid N^2 lookup when deduplicating N inline/Comdat data segments

I think it's an OK start on the problem.

Having looked more at what LDD does with ELF, it's hard to copy what it's doing. I think in spirit the basic process is identical, it's just that relocations and code/data segments are rather different in Wasm.

I agree it would be nice to move towards the ELF linker, by adding section GC etc, but that's maybe out-of-scope for what I'm trying to achieve here.

[ncw]

Rebased and simplified using Sam's latest tweaks to InputSegment handling.

[ncw]

I've now split some of this out into D41390.

The remaining changes here are now very short! It's pretty good value for its line count, hopefully short and inoffensive.

I'm not doing anything to it right now, apart from waiting.

I think it's now much closer to the way the ELF linker does it, which should alleviate concerns.

[ncw]

Rebased on top of Sam's refactoring work...

APPLY AFTER:

• D41315 (Sam's commit "Output functions individually")
• D41419 (Sam's commit "Add InputChunk base class")
• D41390 (My commit, "Don't write out discarded symbols")

Also added support for "relocatable" output from LLD, which should also include the Comdats merged from all the input files.

[sbc100]

Could you rebase this? Does this really depend D41390

[ncw]

Rebased as requested.

Does this depend on D41390?

I did it this way round, because I thought D41390 was the less controversial, and hence would be applied first. I wanted to add the Discarded flag and behaviour, without having to wait for discussion of the COMDAT to grind on.

The COMDAT support here does depend on the Discarded flag added in D41390, so I think the order does make sense.

[sbc100]

If feels like there should be a better way implement D41390 . Do you think we could detagle the two CLs such that this one can land sooner?

[sbc100]

wasm/InputFiles.cpp

267

Can we check the comdats when the segment or function is first created to avoid two loops?

Maybe we could then avoid even adding the to the Functions or Segments list at all and just discard them?

[ncw]

Changes:

• Disentangled from D41390
• Changed to assume that all Functions/InputSegments are covered by Symbols. The "discardable" entities are the function and segment definitions, not the Symbols referring to them, so previously I was iterating over the Functions/Segments to make sure they were discarded. We know though that the MCWasmWriter will never output a COMDAT Function/Segment without an accompanying Symbol, so the change is safe.

One thing I did like a bit about the previous implementation was that it made Comdat behave pretty much just like (non-Comdat) weak symbols; now the Comdat symbols are discarded earlier, which I guess makes sense.

wasm/InputFiles.cpp

267

It was harder before, but in the last fortnight of refactoring, the signatures all match up nicely now, making that easier :)

You're right that's now the best place for it.

I've moved the check above, to where we add the symbols to the SymbolTable.

[ncw]

Simple rebase, to fix conflict with master after latest commits

[sbc100]

Looks like we need one more rebase then this is good to go.

wasm/InputChunks.h

37 ↗

(On Diff #129598)

no need to move this I think?

wasm/InputFiles.cpp

176

I guess this could be a local lambda function since its just used in one function?

wasm/Writer.cpp

420

I think you can just use F->getOutputIndex() here and avoid NumFunctionImports and use a foreach loop instread

[ncw]

Thank you for reviewing and landing! And also for the "setComdat/isComdat" fix in the Clang WasmObjectWriter, I missed a trick there.

I'm glad the community's able to accept patches so easily.

wasm/InputChunks.h

37 ↗

(On Diff #129598)

Oh, I just did it while I was at it...

I really don't like it when method don't match up! I like them to be in the same order in parent and child classes, and I like them to be in the same order in the header and code files, so I can navigate quickly. Just a habit.

It's public in both derived classes, and implemented right next to getSize(), so I felt it belongs here.

I don't mind.

test/wasm/Inputs/comdat1.ll

+$inlineFn = comdat any
+@constantData = weak_odr constant [3 x i8] c"abc", comdat($inlineFn)
+define linkonce_odr i32 @inlineFn() comdat {
+entry:
+  ret i32 ptrtoint ([3 x i8]* @constantData to i32)
+}
+
+define i32 @callInline1() {
+entry:
+    ret i32 ptrtoint (i32 ()* @inlineFn to i32)
+}

test/wasm/Inputs/comdat2.ll

+$inlineFn = comdat any
+@constantData = weak_odr constant [3 x i8] c"abc", comdat($inlineFn)
+define linkonce_odr i32 @inlineFn() comdat {
+entry:
+  ret i32 ptrtoint ([3 x i8]* @constantData to i32)
+}
+
+define i32 @callInline2() {
+entry:
+    ret i32 ptrtoint (i32 ()* @inlineFn to i32)
+}

test/wasm/comdats.ll

+; RUN: llc -filetype=obj -mtriple=wasm32-unknown-uknown-wasm %p/Inputs/comdat1.ll -o %t1.o
+; RUN: llc -filetype=obj -mtriple=wasm32-unknown-uknown-wasm %p/Inputs/comdat2.ll -o %t2.o
+; RUN: llc -filetype=obj -mtriple=wasm32-unknown-uknown-wasm %s -o %t.o
+; RUN: lld -flavor wasm -o %t.wasm %t.o %t1.o %t2.o
+; RUN: obj2yaml %t.wasm | FileCheck %s
+
+declare i32 @inlineFn()
+
+define void @_start() local_unnamed_addr {
+entry:
+  %call = call i32 @inlineFn()
+  ret void
+}
+
+; CHECK:       - Type:            GLOBAL
+; CHECK-NEXT:    Globals:
+; CHECK-NEXT:      - Type:            I32
+; CHECK-NEXT:        Mutable:         true
+; CHECK-NEXT:        InitExpr:
+; CHECK-NEXT:          Opcode:          I32_CONST
+; CHECK-NEXT:          Value:           66576
+; CHECK-NEXT:  - Type:            EXPORT
+; CHECK-NEXT:    Exports:
+; CHECK-NEXT:      - Name:            memory
+; CHECK-NEXT:        Kind:            MEMORY
+; CHECK-NEXT:        Index:           0
+; CHECK-NEXT:      - Name:            _start
+; CHECK-NEXT:        Kind:            FUNCTION
+; CHECK-NEXT:        Index:           0
+; CHECK-NEXT:      - Name:            inlineFn
+; CHECK-NEXT:        Kind:            FUNCTION
+; CHECK-NEXT:        Index:           1
+; CHECK-NEXT:      - Name:            callInline1
+; CHECK-NEXT:        Kind:            FUNCTION
+; CHECK-NEXT:        Index:           2
+; CHECK-NEXT:      - Name:            callInline2
+; CHECK-NEXT:        Kind:            FUNCTION
+; CHECK-NEXT:        Index:           3
+; CHECK-NEXT:  - Type:            ELEM
+; CHECK-NEXT:    Segments:
+; CHECK-NEXT:      - Offset:
+; CHECK-NEXT:          Opcode:          I32_CONST
+; CHECK-NEXT:          Value:           1
+; CHECK-NEXT:        Functions:       [ 1 ]
+; CHECK-NEXT:  - Type:            CODE
+; CHECK-NEXT:    Functions:
+; CHECK-NEXT:      - Locals:
+; CHECK-NEXT:        Body:            1081808080001A0B
+; CHECK-NEXT:      - Locals:
+; CHECK-NEXT:        Body:            4180888080000B
+; CHECK-NEXT:      - Locals:
+; CHECK-NEXT:        Body:            4181808080000B
+; CHECK-NEXT:      - Locals:
+; CHECK-NEXT:        Body:            4181808080000B
+; CHECK-NEXT:  - Type:            DATA
+; CHECK-NEXT:    Segments:
+; CHECK-NEXT:      - SectionOffset:   7
+; CHECK-NEXT:        MemoryIndex:     0
+; CHECK-NEXT:        Offset:
+; CHECK-NEXT:          Opcode:          I32_CONST
+; CHECK-NEXT:          Value:           1024
+; CHECK-NEXT:        Content:         '616263'

wasm/InputFiles.cpp

InputSegment *ObjFile::getSegment(const WasmSymbol &WasmSym) const {
   for (InputSegment *Segment : Segments) {
     if (Address >= Segment->startVA() && Address < Segment->endVA()) {
       DEBUG(dbgs() << "Found symbol in segment: " << WasmSym.Name << " -> "
                    << Segment->getName() << "\n");
 
       return Segment;
     }
   }
-  error("symbol not found in any segment: " + WasmSym.Name);
-  return nullptr;
+  fatal("symbol not found in any segment: " + WasmSym.Name);
 }
 
 static void copyRelocationsRange(std::vector<WasmRelocation> &To,
                                  ArrayRef<WasmRelocation> From, size_t Start,
                                  size_t Size) {
   for (const WasmRelocation &R : From)
     if (R.Offset >= Start && R.Offset < Start + Size)
       To.push_back(R);
const WasmSignature *ObjFile::getFunctionSig(const WasmSymbol &Sym) const {
   return &WasmObj->types()[FunctionType];
 }
 
 InputFunction *ObjFile::getFunction(const WasmSymbol &Sym) const {
   uint32_t FunctionIndex = Sym.ElementIndex - NumFunctionImports;
   return Functions[FunctionIndex];
 }
 
 void ObjFile::initializeSymbols() {
   Symbols.reserve(WasmObj->getNumberOfSymbols());
 
   for (const WasmImport &Import : WasmObj->imports()) {
     switch (Import.Kind) {
     case WASM_EXTERNAL_FUNCTION:
       ++NumFunctionImports;
       break;
     case WASM_EXTERNAL_GLOBAL:
       ++NumGlobalImports;
       break;
     }
   }
 
+  for (const auto &C : WasmObj->comdats())
+    Symtab->addComdat(C.first(), this);
+
   FunctionSymbols.resize(NumFunctionImports + WasmObj->functions().size());
   GlobalSymbols.resize(NumGlobalImports + WasmObj->globals().size());
 
   for (const WasmSegment &S : WasmObj->dataSegments()) {
     InputSegment *Seg = make<InputSegment>(&S, this);
     copyRelocationsRange(Seg->Relocations, DataSection->Relocations,
                          Seg->getInputSectionOffset(), Seg->getSize());
     Segments.emplace_back(Seg);
void ObjFile::initializeSymbols() {
   }
 
   // This is a crude precursor to garbage collection, but it works really nicely
   // for discarding multiple copies of inline (=Comdat/weak) symbols.  If the
   // function isn't reachable by any Symbol (because another file has defined
   // the weak symbol), then it's discardable.  We aren't considering here
   // whether the Symbol is actually ever called.
   for (uint32_t I = 0; I < Funcs.size(); ++I) {
-    if (!ReachedFunctions[I])
+    StringRef Comdat = Functions[I]->Function->Comdat;
+    ObjFile *ComdatFile = Comdat.empty() ? this : Symtab->findComdat(Comdat);
+    if (!ReachedFunctions[I] || ComdatFile != this)
       Functions[I] = &InputFunction::Discarded;
   }
 
+  for (InputSegment *&Seg : Segments) {
+    StringRef Comdat = Seg->Segment->Data.Comdat;
+    if (!Comdat.empty() && Symtab->findComdat(Comdat) != this) {
+      DEBUG(dbgs() << "discarding segment: " << Seg->getName() << "\n");
+      Seg = &InputSegment::Discarded;
+    }
+  }
+
   // Populate `TableSymbols` with all symbols that are called indirectly
   uint32_t SegmentCount = WasmObj->elements().size();
   if (SegmentCount) {
     if (SegmentCount > 1)
       fatal(getName() + ": contains more than one element segment");
     const WasmElemSegment &Segment = WasmObj->elements()[0];
     if (Segment.Offset.Opcode != WASM_OPCODE_I32_CONST)
       fatal(getName() + ": unsupported element segment");

wasm/SymbolTable.h

Symbol *addDefined(InputFile *F, const WasmSymbol *Sym,
                      const InputSegment *Segment = nullptr,
                      InputFunction *Function = nullptr);
   Symbol *addUndefined(InputFile *F, const WasmSymbol *Sym,
                        const WasmSignature *Signature = nullptr);
   Symbol *addUndefinedFunction(StringRef Name, const WasmSignature *Type);
   Symbol *addDefinedGlobal(StringRef Name);
   void addLazy(ArchiveFile *F, const Archive::Symbol *Sym);
 
+  bool addComdat(StringRef Name, ObjFile *);
+  ObjFile *findComdat(StringRef Name) const;
+
 private:
   std::pair<Symbol *, bool> insert(StringRef Name);
 
   llvm::DenseMap<llvm::CachedHashStringRef, Symbol *> SymMap;
   std::vector<Symbol *> SymVector;
+  llvm::DenseMap<llvm::CachedHashStringRef, ObjFile *> ComdatMap;
 };
 
 extern SymbolTable *Symtab;
 
 } // namespace wasm
 } // namespace lld
 
 #endif

wasm/SymbolTable.cpp

if (WasInserted) {
     S->setArchiveSymbol(*Sym);
   } else if (S->isUndefined()) {
     // There is an existing undefined symbol.  The can load from the
     // archive.
     DEBUG(dbgs() << "replacing existing undefined\n");
     F->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;
+}

wasm/Writer.cpp

if (Segments.size() && Config->Relocatable) {
     for (const OutputSegment *S : Segments) {
       writeStr(SubSection.getStream(), S->Name, "segment name");
       writeUleb128(SubSection.getStream(), S->Alignment, "alignment");
       writeUleb128(SubSection.getStream(), 0, "flags");
     }
     SubSection.finalizeContents();
     SubSection.writeToStream(OS);
   }
+
+  // TODO How important is relocatable output - do we need to output the Comdats?
+  // In that case we may need to fiddling with how we merge InputSegments into
+  // OutputSegments so that we can write out the Comdats here.
 }
 
 // Create the custom "name" section containing debug symbol names.
 void Writer::createNameSection() {
   // Create an array of all function sorted by function index space
   std::vector<const Symbol *> Names;
 
   for (ObjFile *File : Symtab->ObjectFiles) {
     Names.reserve(Names.size() + File->getSymbols().size());
     for (Symbol *S : File->getSymbols()) {
       if (!S->isFunction() || S->isWeak() || S->WrittenToNameSec)
         continue;
       S->WrittenToNameSec = true;
       Names.emplace_back(S);