[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

271 ↗

(On Diff #129267)

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

271 ↗

(On Diff #129267)

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

173 ↗

(On Diff #129598)

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

wasm/Writer.cpp

443 ↗

(On Diff #129598)

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.

lld/trunk/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)
+}

lld/trunk/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)
+}

lld/trunk/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:      - Index:           0
+; 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:      - Index:           0
+; CHECK-NEXT:        Locals:
+; CHECK-NEXT:        Body:            1081808080001A0B
+; CHECK-NEXT:      - Index:           1
+; CHECK-NEXT:        Locals:
+; CHECK-NEXT:        Body:            4180888080000B
+; CHECK-NEXT:      - Index:           2
+; CHECK-NEXT:        Locals:
+; CHECK-NEXT:        Body:            4181808080000B
+; CHECK-NEXT:      - Index:           3
+; CHECK-NEXT:        Locals:
+; CHECK-NEXT:        Body:            4181808080000B
+; CHECK-NEXT:      - Index:           4
+; CHECK-NEXT:        Locals:
+; CHECK-NEXT:        Body:            0B
+; 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'

lld/trunk/test/wasm/relocatable.ll

 
 declare i32 @foo_import() local_unnamed_addr
 @data_import = external global i64
 
 @func_addr1 = hidden global i32()* @my_func, align 4
 @func_addr2 = hidden global i32()* @foo_import, align 4
 @data_addr1 = hidden global i64* @data_import, align 8
 
+$func_comdat = comdat any
+@data_comdat = weak_odr constant [3 x i8] c"abc", comdat($func_comdat)
+define linkonce_odr i32 @func_comdat() comdat {
+entry:
+  ret i32 ptrtoint ([3 x i8]* @data_comdat to i32)
+}
+
 ; CHECK:      --- !WASM
 ; CHECK-NEXT: FileHeader:
 ; CHECK-NEXT:   Version:         0x00000001
 ; CHECK-NEXT: Sections:
 ; CHECK-NEXT:   - Type:            TYPE
 ; CHECK-NEXT:     Signatures:
 ; CHECK-NEXT:       - Index:           0
 ; CHECK-NEXT:         ReturnType:      NORESULT

 ; CHECK-NEXT:         Kind:            FUNCTION
 ; CHECK-NEXT:         SigIndex:        2
 ; CHECK-NEXT:       - Module:          env
 ; CHECK-NEXT:         Field:           data_import
 ; CHECK-NEXT:         Kind:            GLOBAL
 ; CHECK-NEXT:         GlobalType:      I32
 ; CHECK-NEXT:         GlobalMutable:   false
 ; CHECK-NEXT:   - Type:            FUNCTION
-; CHECK-NEXT:     FunctionTypes:   [ 0, 2 ]
+; CHECK-NEXT:     FunctionTypes:   [ 0, 2, 2 ]
 ; CHECK-NEXT:   - Type:            TABLE
 ; CHECK-NEXT:     Tables:
 ; CHECK-NEXT:       - ElemType:        ANYFUNC
 ; CHECK-NEXT:         Limits:
 ; CHECK-NEXT:           Flags:           [ HAS_MAX ]
 ; CHECK-NEXT:           Initial:         0x00000002
 ; CHECK-NEXT:           Maximum:         0x00000002
 ; CHECK-NEXT:   - Type:            MEMORY
 ; CHECK-NEXT:     Memories:
 ; CHECK-NEXT:       - Initial:         0x00000001
 ; CHECK-NEXT:   - Type:            GLOBAL
 ; CHECK-NEXT:     Globals:
 ; CHECK-NEXT:       - Index:           1
 ; CHECK-NEXT:         Type:            I32
 ; CHECK-NEXT:         Mutable:         false
 ; CHECK-NEXT:         InitExpr:
 ; CHECK-NEXT:           Opcode:          I32_CONST
 ; CHECK-NEXT:           Value:           0
 ; CHECK-NEXT:       - Index:           2
 ; CHECK-NEXT:         Type:            I32
 ; CHECK-NEXT:         Mutable:         false
 ; CHECK-NEXT:         InitExpr:
 ; CHECK-NEXT:           Opcode:          I32_CONST
-; CHECK-NEXT:           Value:           8
+; CHECK-NEXT:           Value:           20
 ; CHECK-NEXT:       - Index:           3
 ; CHECK-NEXT:         Type:            I32
 ; CHECK-NEXT:         Mutable:         false
 ; CHECK-NEXT:         InitExpr:
 ; CHECK-NEXT:           Opcode:          I32_CONST
-; CHECK-NEXT:           Value:           12
+; CHECK-NEXT:           Value:           8
 ; CHECK-NEXT:       - Index:           4
 ; CHECK-NEXT:         Type:            I32
 ; CHECK-NEXT:         Mutable:         false
 ; CHECK-NEXT:         InitExpr:
 ; CHECK-NEXT:           Opcode:          I32_CONST
+; CHECK-NEXT:           Value:           12
+; CHECK-NEXT:       - Index:           5
+; CHECK-NEXT:         Type:            I32
+; CHECK-NEXT:         Mutable:         false
+; CHECK-NEXT:         InitExpr:
+; CHECK-NEXT:           Opcode:          I32_CONST
 ; CHECK-NEXT:           Value:           16
 ; CHECK-NEXT:   - Type:            EXPORT
 ; CHECK-NEXT:     Exports:
 ; CHECK-NEXT:       - Name:            hello
 ; CHECK-NEXT:         Kind:            FUNCTION
 ; CHECK-NEXT:         Index:           2
 ; CHECK-NEXT:       - Name:            my_func
 ; CHECK-NEXT:         Kind:            FUNCTION
 ; CHECK-NEXT:         Index:           3
+; CHECK-NEXT:       - Name:            func_comdat
+; CHECK-NEXT:         Kind:            FUNCTION
+; CHECK-NEXT:         Index:           4
 ; CHECK-NEXT:       - Name:            hello_str
 ; CHECK-NEXT:         Kind:            GLOBAL
 ; CHECK-NEXT:         Index:           1
-; CHECK-NEXT:       - Name:            func_addr1
+; CHECK-NEXT:       - Name:            data_comdat
 ; CHECK-NEXT:         Kind:            GLOBAL
 ; CHECK-NEXT:         Index:           2
-; CHECK-NEXT:       - Name:            func_addr2
+; CHECK-NEXT:       - Name:            func_addr1
 ; CHECK-NEXT:         Kind:            GLOBAL
 ; CHECK-NEXT:         Index:           3
-; CHECK-NEXT:       - Name:            data_addr1
+; CHECK-NEXT:       - Name:            func_addr2
 ; CHECK-NEXT:         Kind:            GLOBAL
 ; CHECK-NEXT:         Index:           4
+; CHECK-NEXT:       - Name:            data_addr1
+; CHECK-NEXT:         Kind:            GLOBAL
+; CHECK-NEXT:         Index:           5
 ; CHECK-NEXT:   - Type:            ELEM
 ; CHECK-NEXT:     Segments:
 ; CHECK-NEXT:       - Offset:
 ; CHECK-NEXT:           Opcode:          I32_CONST
 ; CHECK-NEXT:           Value:           0
 ; CHECK-NEXT:         Functions:       [ 3, 1 ]
 ; CHECK-NEXT:   - Type:            CODE
 ; CHECK-NEXT:     Relocations:
 ; CHECK-NEXT:       - Type:            R_WEBASSEMBLY_MEMORY_ADDR_SLEB
 ; CHECK-NEXT:         Index:           1
 ; CHECK-NEXT:         Offset:          0x00000004
 ; CHECK-NEXT:       - Type:            R_WEBASSEMBLY_FUNCTION_INDEX_LEB
 ; CHECK-NEXT:         Index:           0
 ; CHECK-NEXT:         Offset:          0x0000000A
 ; CHECK-NEXT:       - Type:            R_WEBASSEMBLY_FUNCTION_INDEX_LEB
 ; CHECK-NEXT:         Index:           1
 ; CHECK-NEXT:         Offset:          0x00000013
+; CHECK-NEXT:       - Type:            R_WEBASSEMBLY_MEMORY_ADDR_SLEB
+; CHECK-NEXT:         Index:           2
+; CHECK-NEXT:         Offset:          0x0000001F
 ; CHECK-NEXT:     Functions:
 ; CHECK-NEXT:       - Index:         2
 ; CHECK-NEXT:         Locals:
 ; CHECK-NEXT:         Body:          4180808080001080808080000B
 ; CHECK-NEXT:       - Index:         3
 ; CHECK-NEXT:         Locals:
 ; CHECK-NEXT:         Body:          1081808080001A41010B
+; CHECK-NEXT:       - Index:           4
+; CHECK-NEXT:         Locals:
+; CHECK-NEXT:         Body:            4194808080000B
 ; CHECK-NEXT:   - Type:            DATA
 ; CHECK-NEXT:     Relocations:
 ; CHECK-NEXT:       - Type:            R_WEBASSEMBLY_TABLE_INDEX_I32
 ; CHECK-NEXT:         Index:           0
 ; CHECK-NEXT:         Offset:          0x00000012
 ; CHECK-NEXT:       - Type:            R_WEBASSEMBLY_TABLE_INDEX_I32
 ; CHECK-NEXT:         Index:           1
 ; CHECK-NEXT:         Offset:          0x0000001B

 ; CHECK-NEXT:           Value:           12
 ; CHECK-NEXT:         Content:         '01000000'
 ; CHECK-NEXT:       - SectionOffset:   36
 ; CHECK-NEXT:         MemoryIndex:     0
 ; CHECK-NEXT:         Offset:
 ; CHECK-NEXT:           Opcode:          I32_CONST
 ; CHECK-NEXT:           Value:           16
 ; CHECK-NEXT:         Content:         '00000000'
+; CHECK-NEXT:       - SectionOffset:   45
+; CHECK-NEXT:         MemoryIndex:     0
+; CHECK-NEXT:         Offset:
+; CHECK-NEXT:           Opcode:          I32_CONST
+; CHECK-NEXT:           Value:           20
+; CHECK-NEXT:         Content:         '616263'
 ; CHECK-NEXT:   - Type:            CUSTOM
 ; CHECK-NEXT:     Name:            linking
-; CHECK-NEXT:     DataSize:        20
+; CHECK-NEXT:     DataSize:        23
 ; CHECK-NEXT:     SegmentInfo:
 ; CHECK-NEXT:       - Index:           0
 ; CHECK-NEXT:         Name:            .rodata.hello_str
 ; CHECK-NEXT:         Alignment:       1
-; CHECK-NEXT:         Flags:           [ ]
+; CHECK-NEXT:         Flags:           [  ]
 ; CHECK-NEXT:       - Index:           1
 ; CHECK-NEXT:         Name:            .data.func_addr1
 ; CHECK-NEXT:         Alignment:       4
-; CHECK-NEXT:         Flags:           [ ]
+; CHECK-NEXT:         Flags:           [  ]
 ; CHECK-NEXT:       - Index:           2
 ; CHECK-NEXT:         Name:            .data.func_addr2
 ; CHECK-NEXT:         Alignment:       4
-; CHECK-NEXT:         Flags:           [ ]
+; CHECK-NEXT:         Flags:           [  ]
 ; CHECK-NEXT:       - Index:           3
 ; CHECK-NEXT:         Name:            .data.data_addr1
 ; CHECK-NEXT:         Alignment:       8
-; CHECK-NEXT:         Flags:           [ ]
+; CHECK-NEXT:         Flags:           [  ]
+; CHECK-NEXT:       - Index:           4
+; CHECK-NEXT:         Name:            .rodata.data_comdat
+; CHECK-NEXT:         Alignment:       1
+; CHECK-NEXT:         Flags:           [  ]
+; CHECK-NEXT:     Comdats:
+; CHECK-NEXT:       - Name:            func_comdat
+; CHECK-NEXT:         Entries:
+; CHECK-NEXT:           - Kind:            FUNCTION
+; CHECK-NEXT:             Index:           4
+; CHECK-NEXT:           - Kind:            DATA
+; CHECK-NEXT:             Index:           4
 ; CHECK-NEXT:   - Type:            CUSTOM
 ; CHECK-NEXT:     Name:            name
 ; CHECK-NEXT:     FunctionNames:
 ; CHECK-NEXT:       - Index:           0
 ; CHECK-NEXT:         Name:            puts
 ; CHECK-NEXT:       - Index:           1
 ; CHECK-NEXT:         Name:            foo_import
 ; CHECK-NEXT:       - Index:           2
 ; CHECK-NEXT:         Name:            hello
 ; CHECK-NEXT:       - Index:           3
 ; CHECK-NEXT:         Name:            my_func
 ; CHECK-NEXT: ...

lld/trunk/wasm/InputChunks.h

public:
 
   void setOutputOffset(uint32_t Offset) {
     OutputOffset = Offset;
     calcRelocations();
   }
 
   uint32_t getOutputOffset() const { return OutputOffset; }
 
+  virtual StringRef getComdat() const = 0;
+
+  bool Discarded = false;
   std::vector<OutputRelocation> OutRelocations;
 
 protected:
   InputChunk(const ObjFile *F) : File(F) {}
   virtual ~InputChunk() = default;
   void calcRelocations();
   virtual const uint8_t *getData() const = 0;
   virtual uint32_t getInputSectionOffset() const = 0;
public:
   const uint8_t *getData() const override {
     return Segment.Data.Content.data();
   }
   uint32_t getSize() const override { return Segment.Data.Content.size(); }
   uint32_t getAlignment() const { return Segment.Data.Alignment; }
   uint32_t startVA() const { return Segment.Data.Offset.Value.Int32; }
   uint32_t endVA() const { return startVA() + getSize(); }
   StringRef getName() const { return Segment.Data.Name; }
+  StringRef getComdat() const override { return Segment.Data.Comdat; }
 
   int32_t OutputSegmentOffset = 0;
 
 protected:
   uint32_t getInputSectionOffset() const override {
     return Segment.SectionOffset;
   }
+
   const WasmSegment &Segment;
   const OutputSegment *OutputSeg = nullptr;
 };
 
 // Represents a single wasm function within and input file.  These are
 // combined to create the final output CODE section.
 class InputFunction : public InputChunk {
 public:
   InputFunction(const WasmSignature &S, const WasmFunction *Func,
                 const ObjFile *F)
       : InputChunk(F), Signature(S), WrittenToNameSec(false), Function(Func) {}
 
   uint32_t getSize() const override { return Function->Size; }
   const uint8_t *getData() const override {
     return File->CodeSection->Content.data() + getInputSectionOffset();
   }
-
+  StringRef getComdat() const override { return Function->Comdat; }
   uint32_t getOutputIndex() const { return OutputIndex.getValue(); };
   bool hasOutputIndex() const { return OutputIndex.hasValue(); };
   void setOutputIndex(uint32_t Index);
 
   const WasmSignature &Signature;
 
   unsigned WrittenToNameSec : 1;
 

lld/trunk/wasm/InputFiles.h

 using llvm::object::WasmSymbol;
 using llvm::wasm::WasmImport;
 using llvm::wasm::WasmSignature;
 using llvm::wasm::WasmRelocation;
 
 namespace lld {
 namespace wasm {
 
+class InputChunk;
 class InputFunction;
 class InputSegment;
 
 class InputFile {
 public:
   enum Kind {
     ObjectKind,
     ArchiveKind,
Symbol *createDefined(const WasmSymbol &Sym, Symbol::Kind Kind,
                         uint32_t Address = UINT32_MAX);
   Symbol *createUndefined(const WasmSymbol &Sym, Symbol::Kind Kind,
                           const WasmSignature *Signature = nullptr);
   void initializeSymbols();
   InputSegment *getSegment(const WasmSymbol &WasmSym) const;
   const WasmSignature *getFunctionSig(const WasmSymbol &Sym) const;
   uint32_t getGlobalValue(const WasmSymbol &Sym) const;
   InputFunction *getFunction(const WasmSymbol &Sym) const;
+  bool isExcludedByComdat(InputChunk *Chunk) const;
 
   // List of all symbols referenced or defined by this file.
   std::vector<Symbol *> Symbols;
 
   // List of all function symbols indexed by the function index space
   std::vector<Symbol *> FunctionSymbols;
 
   // List of all global symbols indexed by the global index space

lld/trunk/wasm/InputFiles.cpp

const WasmSignature *ObjFile::getFunctionSig(const WasmSymbol &Sym) const {
   return &WasmObj->types()[Sym.FunctionType];
 }
 
 InputFunction *ObjFile::getFunction(const WasmSymbol &Sym) const {
   uint32_t FunctionIndex = Sym.ElementIndex - NumFunctionImports;
   return Functions[FunctionIndex];
 }
 
+bool ObjFile::isExcludedByComdat(InputChunk *Chunk) const {
+  StringRef Comdat = Chunk->getComdat();
+  return !Comdat.empty() && Symtab->findComdat(Comdat) != this;
+}
+
 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;
     }
   }
 
   FunctionSymbols.resize(NumFunctionImports + WasmObj->functions().size());
   GlobalSymbols.resize(NumGlobalImports + WasmObj->globals().size());
 
+  ArrayRef<WasmFunction> Funcs = WasmObj->functions();
+  ArrayRef<uint32_t> FuncTypes = WasmObj->functionTypes();
+  ArrayRef<WasmSignature> Types = WasmObj->types();
+  ArrayRef<WasmGlobal> Globals = WasmObj->globals();
+
+  for (const auto &C : WasmObj->comdats())
+    Symtab->addComdat(C, this);
+
+  FunctionSymbols.resize(NumFunctionImports + Funcs.size());
+  GlobalSymbols.resize(NumGlobalImports + Globals.size());
+
   for (const WasmSegment &S : WasmObj->dataSegments()) {
     InputSegment *Seg = make<InputSegment>(S, this);
     Seg->copyRelocations(*DataSection);
     Segments.emplace_back(Seg);
   }
 
-  ArrayRef<WasmFunction> Funcs = WasmObj->functions();
-  ArrayRef<uint32_t> FuncTypes = WasmObj->functionTypes();
-  ArrayRef<WasmSignature> Types = WasmObj->types();
   for (size_t I = 0; I < Funcs.size(); ++I) {
     const WasmFunction &Func = Funcs[I];
     const WasmSignature &Sig = Types[FuncTypes[I]];
     InputFunction *F = make<InputFunction>(Sig, &Func, this);
     F->copyRelocations(*CodeSection);
     Functions.emplace_back(F);
   }
 
   // Populate `FunctionSymbols` and `GlobalSymbols` based on the WasmSymbols
   // in the object
   for (const SymbolRef &Sym : WasmObj->symbols()) {
     const WasmSymbol &WasmSym = WasmObj->getWasmSymbol(Sym.getRawDataRefImpl());
     Symbol *S;
     switch (WasmSym.Type) {
+    case WasmSymbol::SymbolType::FUNCTION_EXPORT: {
+      InputFunction *Function = getFunction(WasmSym);
+      if (!isExcludedByComdat(Function)) {
+        S = createDefined(WasmSym, Symbol::Kind::DefinedFunctionKind, nullptr,
+                          Function);
+        break;
+      } else {
+        Function->Discarded = true;
+        LLVM_FALLTHROUGH; // Exclude function, and add the symbol as undefined
+      }
+    }
     case WasmSymbol::SymbolType::FUNCTION_IMPORT:
       S = createUndefined(WasmSym, Symbol::Kind::UndefinedFunctionKind,
                           getFunctionSig(WasmSym));
       break;
-    case WasmSymbol::SymbolType::GLOBAL_IMPORT:
-      S = createUndefined(WasmSym, Symbol::Kind::UndefinedGlobalKind);
-      break;
-    case WasmSymbol::SymbolType::GLOBAL_EXPORT:
+    case WasmSymbol::SymbolType::GLOBAL_EXPORT: {
+      InputSegment *Segment = getSegment(WasmSym);
+      if (!isExcludedByComdat(Segment)) {
         S = createDefined(WasmSym, Symbol::Kind::DefinedGlobalKind,
-                        getSegment(WasmSym), nullptr, getGlobalValue(WasmSym));
+                          Segment, nullptr, getGlobalValue(WasmSym));
         break;
-    case WasmSymbol::SymbolType::FUNCTION_EXPORT:
-      S = createDefined(WasmSym, Symbol::Kind::DefinedFunctionKind, nullptr,
-                        getFunction(WasmSym));
+      } else {
+        Segment->Discarded = true;
+        LLVM_FALLTHROUGH; // Exclude global, and add the symbol as undefined
+      }
+    }
+    case WasmSymbol::SymbolType::GLOBAL_IMPORT:
+      S = createUndefined(WasmSym, Symbol::Kind::UndefinedGlobalKind);
       break;
     case WasmSymbol::SymbolType::DEBUG_FUNCTION_NAME:
       // These are for debugging only, no need to create linker symbols for them
       continue;
     }
 
     Symbols.push_back(S);
     if (WasmSym.isFunction()) {

lld/trunk/wasm/SymbolTable.h

public:
 
   std::vector<ObjFile *> ObjectFiles;
 
   void reportDuplicate(Symbol *Existing, InputFile *NewFile);
   void reportRemainingUndefines();
 
   ArrayRef<Symbol *> getSymbols() const { return SymVector; }
   Symbol *find(StringRef Name);
+  ObjFile *findComdat(StringRef Name) const;
 
   Symbol *addDefined(StringRef Name, Symbol::Kind Kind, uint32_t Flags,
                      InputFile *F, const InputSegment *Segment = nullptr,
                      InputFunction *Function = nullptr, uint32_t Address = 0);
   Symbol *addUndefined(StringRef Name, Symbol::Kind Kind, uint32_t Flags,
                        InputFile *F, const WasmSignature *Signature = nullptr);
   Symbol *addUndefinedFunction(StringRef Name, const WasmSignature *Type);
   Symbol *addDefinedGlobal(StringRef Name);
   Symbol *addDefinedFunction(StringRef Name, const WasmSignature *Type,
                              uint32_t Flags);
   void addLazy(ArchiveFile *F, const Archive::Symbol *Sym);
+  bool addComdat(StringRef Name, ObjFile *);
 
 private:
   std::pair<Symbol *, bool> insert(StringRef Name);
 
+  llvm::DenseMap<llvm::CachedHashStringRef, ObjFile *> ComdatMap;
   llvm::DenseMap<llvm::CachedHashStringRef, Symbol *> SymMap;
   std::vector<Symbol *> SymVector;
 };
 
 extern SymbolTable *Symtab;
 
 } // namespace wasm
 } // namespace lld
 
 #endif

lld/trunk/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;
+}

lld/trunk/wasm/Writer.cpp

 #include "lld/Common/Memory.h"
 #include "lld/Common/Threads.h"
 #include "llvm/Support/FileOutputBuffer.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/LEB128.h"
 
 #include <cstdarg>
+#include <map>
 
 #define DEBUG_TYPE "lld"
 
 using namespace llvm;
 using namespace llvm::wasm;
 using namespace lld;
 using namespace lld::wasm;
 
writeUleb128(SubSection.getStream(), InitFunctions.size(),
                  "num init functionsw");
     for (const WasmInitFunc &F : InitFunctions) {
       writeUleb128(SubSection.getStream(), F.Priority, "priority");
       writeUleb128(SubSection.getStream(), F.FunctionIndex, "function index");
     }
     SubSection.finalizeContents();
     SubSection.writeToStream(OS);
   }
+
+  struct ComdatEntry { unsigned Kind; uint32_t Index; };
+  std::map<StringRef,std::vector<ComdatEntry>> Comdats;
+
+  for (const InputFunction *F : DefinedFunctions) {
+    StringRef Comdat = F->getComdat();
+    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();
+    for (const InputSegment *IS : InputSegments)
+      assert(IS->getComdat() == Comdat);
+    if (!Comdat.empty())
+      Comdats[Comdat].emplace_back(ComdatEntry{WASM_COMDAT_DATA, I});
+  }
+
+  if (!Comdats.empty()) {
+    SubSection SubSection(WASM_COMDAT_INFO);
+    writeUleb128(SubSection.getStream(), Comdats.size(), "num comdats");
+    for (const auto &C : Comdats) {
+      writeStr(SubSection.getStream(), C.first, "comdat name");
+      writeUleb128(SubSection.getStream(), 0, "comdat flags"); // flags for future use
+      writeUleb128(SubSection.getStream(), C.second.size(), "num entries");
+      for (const ComdatEntry &Entry : C.second) {
+        writeUleb128(SubSection.getStream(), Entry.Kind, "entry kind");
+        writeUleb128(SubSection.getStream(), Entry.Index, "entry index");
+      }
+    }
+    SubSection.finalizeContents();
+    SubSection.writeToStream(OS);
+  }
 }
 
 // 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;
 
   auto AddToNames = [&](Symbol* S) {
if (Config->EmitRelocs) {
         Sym->setOutputIndex(GlobalIndex++);
       }
     }
   }
 
   for (ObjFile *File : Symtab->ObjectFiles) {
     DEBUG(dbgs() << "Functions: " << File->getName() << "\n");
     for (InputFunction *Func : File->Functions) {
+      if (Func->Discarded)
+        continue;
       DefinedFunctions.emplace_back(Func);
       Func->setOutputIndex(FunctionIndex++);
     }
   }
 
   for (ObjFile *File : Symtab->ObjectFiles) {
     DEBUG(dbgs() << "Table Indexes: " << File->getName() << "\n");
     for (Symbol *Sym : File->getTableSymbols()) {
static StringRef getOutputDataSegmentName(StringRef Name) {
   }
 
   return Name;
 }
 
 void Writer::createOutputSegments() {
   for (ObjFile *File : Symtab->ObjectFiles) {
     for (InputSegment *Segment : File->Segments) {
+      if (Segment->Discarded)
+        continue;
       StringRef Name = getOutputDataSegmentName(Segment->getName());
       OutputSegment *&S = SegmentMap[Name];
       if (S == nullptr) {
         DEBUG(dbgs() << "new segment: " << Name << "\n");
         S = make<OutputSegment>(Name);
         Segments.push_back(S);
       }
       S->addInputSegment(Segment);