[WebAssembly] COMDAT: core LLVM support

[ncw]

Summary

This adds COMDAT support to the LLVM frontend and Wasm object-file support.

For spec, see https://github.com/WebAssembly/tool-conventions/pull/31

For corresponding LLD change, see https://bugs.llvm.org/show_bug.cgi?id=35533, and D40845

[sbc100]

Thanks for doing this. Looks like a good direction!

include/llvm/BinaryFormat/Wasm.h

79 ↗

(On Diff #125570)

Why a new struct here but not for Function and Segment?

If we decide a new struct is needed, we have tended to prefer composition over inheritance for this kind of thing.

218 ↗

(On Diff #125570)

Give that we already have symbol and segment info, and that functions and globals are both symbols, would it make sense to add the COMDAT to the existing segment / symbol info? I'm don't feel strongly about this, just wondering what you think?

lib/MC/WasmObjectWriter.cpp

148 ↗

(On Diff #125570)

Should this maybe go in BinaryFormat/Wasm.h since its part of the binary format. Then the reader could use it too?

And maybe another struct type which is a Name + a vector of WasmComdatEntry would be useful to represent a whole COMDAT declaration?

lib/Object/WasmObjectFile.cpp

413 ↗

(On Diff #125570)

Read into a WasmComdatEntry maybe?

[ncw]

include/llvm/BinaryFormat/Wasm.h

79 ↗

(On Diff #125570)

I knew this would come up! It's a hack/workaround. I would have preferred to add the member to WasmGlobal, but WasmGlobal is used inside a union (in WasmImport) and StringRef is non-POD so can't go in a union.

I'll fix it up one way or another, WasmGlobalDecl is a (small) bodge just to get it working. Possible solutions: use a Variant instead of a union in WasmImport; or, review the hierarchy of types and come up with a cleaner representation of the Wasm data. (I just need an hour to draw some diagrams and read the existing code to understand where the Comdat field belongs.)

218 ↗

(On Diff #125570)

I mainly did it this way for size. C++ function names can be hundreds of characters long, so you don't want to use the name very often in the object file.

ELF in fact does something very sneaky, and in the COMDAT group directly references the symbol name in the symbol table, for ultimate compactness.

If we put the long (string) COMDAT identifier next to each segment/symbol that would be quite a bit of bloat. We could have a list of COMDAT names separately, and then in the symbol data have an integer index into the COMDAT list, but I'm not sure that's any tidier than this approach.

lib/MC/WasmObjectWriter.cpp

148 ↗

(On Diff #125570)

Good idea.

[ncw]

OK, I've cleaned this up, and I think it's ready to go.

• Firstly, note that this can be merged before LLD gains COMDAT support (ie - this doesn't need corresponding changes in LLD to keep working)
• I've made a matching PR in the tool-conventions repo, https://github.com/WebAssembly/tool-conventions/pull/31
• Added test coverage for each bit

Now, the contentious bit - is it actually the right design to be using ELF-style COMDAT?

Well, I think it _maybe_ is, and it's better than nothing. I think we basically need to just keep on improving LLD, and as we go we'll add more flags and bits and pieces as needed. LLD linking is a bit different to x86 linking, certainly when we start doing more clever dead code removal, and I don't want to anticipate that too much.

I think there's value in merging a simple implementation soon, and improving it.

Anything more fancy than the COMDAT support I've done here, would require a correspondingly more fancy/complicated initial review on the LLD side.

[ncw]

Update - added "flags" field and removed explicit Comdat for globals, following Dan's comments on the GitHub PR.

[ncw]

lib/MC/WasmObjectWriter.cpp

148 ↗

(On Diff #125570)

I've decided to keep it this way, after having a fiddle to see what it would look like.

Firstly, I'm just storing the COMDAT information in the same way as existing linking data. We don't have a struct for the "names" custom section, and when we read them in, we attach the names directly to the objects.

I actually like the way it's represented. Conceptually, the COMDAT name *is* attached to the function/data-segment. The linking section is just a way to attach extra information to the standard Wasm sections, and I think it makes sense to model it that way.

[sbc100]

Based on the discussion in the bug (https://bugs.llvm.org/show_bug.cgi?id=35533) it sounds like we need to take a look at SHF_LINK_ORDER and how that works. It sounds like its different to the "group" concept. But if we do decide groups are the way to go this change lgtm.

[ncw]

Changes:

• Rebased
• Added yaml2obj support to match obj2yaml, tweaked the YAML display for neatness

[ncw]

In D40844#951754, @sbc100 wrote:

Based on the discussion in the bug (https://bugs.llvm.org/show_bug.cgi?id=35533) it sounds like we need to take a look at SHF_LINK_ORDER and how that works. It sounds like its different to the "group" concept. But if we do decide groups are the way to go this change lgtm.

I've added a looong comment to that bug. SHF_LINK_ORDER really is very very similar to "Comdat groups" - the only differences are 1) ELF historical encoding stuff, and 2) SHF_LINK_ORDER creates "anonymous" linker groupings rather than named Comdat groups.

I basically can't see what all the fuss is about! Comdat "groupings" are what we want, and all the alternatives we're discussing provide the same semantic. It's just arguing about the name and the details? Maybe if you've been working on this for a while though the details seem bigger.

I can't see a major functional difference between what I've implemented here, and what SHF_LINK_ORDER would provide. I might be missing something though....

[sbc100]

include/llvm/Object/Wasm.h

144 ↗

(On Diff #127341)

I'd rather expose an ArrayRef here (I think you can use a local function-local set() to detect duplicate entries while parsing). For consistency and so that comdats appear in order.

lib/Object/WasmObjectFile.cpp

438 ↗

(On Diff #127341)

while (ComdatCount--)?

449 ↗

(On Diff #127341)

while (EntryCount--)

468 ↗

(On Diff #127341)

We now have isValidFunctionIndex(Index) for this.

lib/ObjectYAML/WasmYAML.cpp

65 ↗

(On Diff #127341)

std::map funny to me here. This this its because I worry about iteration order being consistent. I'd want the comdats to be displayed in the order they appear in the input file, not alphabetically.

How about std::vector<Comdat> where Comdat is a struct with a name + entries?

[ncw]

Updated:

• Responded to Sam's comments
• Fixed a minor issue with the function indices
• Fixed a bug in my addition to yaml2wasm

include/llvm/Object/Wasm.h

144 ↗

(On Diff #127341)

Good point, done.

lib/ObjectYAML/WasmYAML.cpp

65 ↗

(On Diff #127341)

OK, for YAML it's using a vector now. That makes sense, thanks.

[sunfish]

I'm behind on some of the discussions on this topic at the moment, but overall, this looks like it's headed in a good direction, so I'm in favor of this patch.

[sbc100]

Would you mind re-basing this, and then I'll land it.

[ncw]

Thanks!

Rebased.

NB. I haven't yet re-run the tests, this is an optimistic update - it takes a looong time to compile everything, and after a rebase pretty much everything needs to recompile. Just building the tests now.

[ncw]

MC tests pass, but I've just noticed I missed one in CodeGen/WebAssembly/comdat.ll. I won't be able to fix it today, sorry..

[sbc100]

tools/obj2yaml/wasm2yaml.cpp

52 ↗

(On Diff #127684)

I ended up exposing the Index directly in the WasmFunction struct to avoid the need for this.

[sbc100]

When testing with lld I noticed that the comdat group names are appearing as undefined symbols in the final output.

See: https://reviews.llvm.org/D41959

I this case it results in unresolved symbol: sharedComdat

Can you think of a way to avoid including these?

llvm/trunk/docs/LangRef.rst

 ``largest``
     The linker will choose the section containing the largest COMDAT key.
 ``noduplicates``
     The linker requires that only section with this COMDAT key exist.
 ``samesize``
     The linker may choose any COMDAT key but the sections must contain the
     same amount of data.
 
-Note that the Mach-O platform doesn't support COMDATs and ELF only supports
-``any`` as a selection kind.
+Note that the Mach-O platform doesn't support COMDATs, and ELF and WebAssembly
+only support ``any`` as a selection kind.
 
 Here is an example of a COMDAT group where a function will only be selected if
 the COMDAT key's section is the largest:
 
 .. code-block:: text
 
    $foo = comdat largest
    @foo = global i32 2, comdat($foo)

llvm/trunk/include/llvm/ADT/Triple.h

bool isARM() const {
     return getArch() == Triple::arm || getArch() == Triple::armeb;
   }
 
   /// Tests whether the target is AArch64 (little and big endian).
   bool isAArch64() const {
     return getArch() == Triple::aarch64 || getArch() == Triple::aarch64_be;
   }
 
-  /// Tests wether the target supports comdat
+  /// Tests whether the target supports comdat
   bool supportsCOMDAT() const {
-    return !isOSBinFormatMachO() && !isOSBinFormatWasm();
+    return !isOSBinFormatMachO();
   }
 
   /// @}
   /// @name Mutators
   /// @{
 
   /// setArch - Set the architecture (first) component of the triple
   /// to a known type.

llvm/trunk/include/llvm/BinaryFormat/Wasm.h

 };
 
 struct WasmFunction {
   uint32_t Index;
   std::vector<WasmLocalDecl> Locals;
   ArrayRef<uint8_t> Body;
   uint32_t CodeSectionOffset;
   uint32_t Size;
+  StringRef Comdat;
 };
 
 struct WasmDataSegment {
   uint32_t MemoryIndex;
   WasmInitExpr Offset;
   ArrayRef<uint8_t> Content;
   StringRef Name;
   uint32_t Alignment;
   uint32_t Flags;
+  StringRef Comdat;
 };
 
 struct WasmElemSegment {
   uint32_t TableIndex;
   WasmInitExpr Offset;
   std::vector<uint32_t> Functions;
 };
 
enum : unsigned {
   WASM_OPCODE_GET_GLOBAL = 0x23,
   WASM_OPCODE_I32_CONST = 0x41,
   WASM_OPCODE_I64_CONST = 0x42,
   WASM_OPCODE_F32_CONST = 0x43,
   WASM_OPCODE_F64_CONST = 0x44,
 };
 
 enum : unsigned {
-  WASM_NAMES_FUNCTION = 0x1,
-  WASM_NAMES_LOCAL = 0x2,
-};
-
-enum : unsigned {
   WASM_LIMITS_FLAG_HAS_MAX = 0x1,
 };
 
 // Subset of types that a value can have
 enum class ValType {
   I32 = WASM_TYPE_I32,
   I64 = WASM_TYPE_I64,
   F32 = WASM_TYPE_F32,
   F64 = WASM_TYPE_F64,
 };
 
-// Linking metadata kinds.
+// Kind codes used in the custom "name" section
+enum : unsigned {
+  WASM_NAMES_FUNCTION = 0x1,
+  WASM_NAMES_LOCAL    = 0x2,
+};
+
+// Kind codes used in the custom "linking" section
 enum : unsigned {
   WASM_SYMBOL_INFO    = 0x2,
   WASM_DATA_SIZE      = 0x3,
   WASM_SEGMENT_INFO   = 0x5,
   WASM_INIT_FUNCS     = 0x6,
+  WASM_COMDAT_INFO    = 0x7,
+};
+
+// Kind codes used in the custom "linking" section in the WASM_COMDAT_INFO
+enum : unsigned {
+  WASM_COMDAT_DATA        = 0x0,
+  WASM_COMDAT_FUNCTION    = 0x1,
 };
 
 const unsigned WASM_SYMBOL_BINDING_MASK       = 0x3;
 const unsigned WASM_SYMBOL_VISIBILITY_MASK    = 0x4;
 
 const unsigned WASM_SYMBOL_BINDING_GLOBAL     = 0x0;
 const unsigned WASM_SYMBOL_BINDING_WEAK       = 0x1;
 const unsigned WASM_SYMBOL_BINDING_LOCAL      = 0x2;

llvm/trunk/include/llvm/Object/Wasm.h

public:
   ArrayRef<wasm::WasmLimits> memories() const { return Memories; }
   ArrayRef<wasm::WasmGlobal> globals() const { return Globals; }
   ArrayRef<wasm::WasmExport> exports() const { return Exports; }
   const wasm::WasmLinkingData& linkingData() const { return LinkingData; }
   uint32_t getNumberOfSymbols() const { return Symbols.size(); }
   ArrayRef<wasm::WasmElemSegment> elements() const { return ElemSegments; }
   ArrayRef<WasmSegment> dataSegments() const { return DataSegments; }
   ArrayRef<wasm::WasmFunction> functions() const { return Functions; }
+  ArrayRef<StringRef> comdats() const { return Comdats; }
   uint32_t startFunction() const { return StartFunction; }
 
   void moveSymbolNext(DataRefImpl &Symb) const override;
 
   uint32_t getSymbolFlags(DataRefImpl Symb) const override;
 
   basic_symbol_iterator symbol_begin() const override;
 
private:
   Error parseStartSection(const uint8_t *Ptr, const uint8_t *End);
   Error parseElemSection(const uint8_t *Ptr, const uint8_t *End);
   Error parseCodeSection(const uint8_t *Ptr, const uint8_t *End);
   Error parseDataSection(const uint8_t *Ptr, const uint8_t *End);
 
   // Custom section types
   Error parseNameSection(const uint8_t *Ptr, const uint8_t *End);
   Error parseLinkingSection(const uint8_t *Ptr, const uint8_t *End);
+  Error parseLinkingSectionComdat(const uint8_t *&Ptr, const uint8_t *End);
   Error parseRelocSection(StringRef Name, const uint8_t *Ptr,
                           const uint8_t *End);
 
   void populateSymbolTable();
 
   wasm::WasmObjectHeader Header;
   std::vector<WasmSection> Sections;
   std::vector<wasm::WasmSignature> Signatures;
   std::vector<uint32_t> FunctionTypes;
   std::vector<wasm::WasmTable> Tables;
   std::vector<wasm::WasmLimits> Memories;
   std::vector<wasm::WasmGlobal> Globals;
   std::vector<wasm::WasmImport> Imports;
   std::vector<wasm::WasmExport> Exports;
   std::vector<wasm::WasmElemSegment> ElemSegments;
   std::vector<WasmSegment> DataSegments;
   std::vector<wasm::WasmFunction> Functions;
   std::vector<WasmSymbol> Symbols;
+  std::vector<StringRef> Comdats;
   uint32_t StartFunction = -1;
   bool HasLinkingSection = false;
   wasm::WasmLinkingData LinkingData;
   uint32_t NumImportedGlobals = 0;
   uint32_t NumImportedFunctions = 0;
   uint32_t ImportSection = 0;
   uint32_t ExportSection = 0;
 

llvm/trunk/include/llvm/ObjectYAML/WasmYAML.h

 LLVM_YAML_STRONG_TYPEDEF(int32_t, TableType)
 LLVM_YAML_STRONG_TYPEDEF(int32_t, SignatureForm)
 LLVM_YAML_STRONG_TYPEDEF(uint32_t, ExportKind)
 LLVM_YAML_STRONG_TYPEDEF(uint32_t, Opcode)
 LLVM_YAML_STRONG_TYPEDEF(uint32_t, RelocType)
 LLVM_YAML_STRONG_TYPEDEF(uint32_t, SymbolFlags)
 LLVM_YAML_STRONG_TYPEDEF(uint32_t, SegmentFlags)
 LLVM_YAML_STRONG_TYPEDEF(uint32_t, LimitFlags)
+LLVM_YAML_STRONG_TYPEDEF(uint32_t, ComdatKind)
 
 struct FileHeader {
   yaml::Hex32 Version;
 };
 
 struct Limits {
   LimitFlags Flags;
   yaml::Hex32 Initial;
struct SymbolInfo {
   SymbolFlags Flags;
 };
 
 struct InitFunction {
   uint32_t Priority;
   uint32_t FunctionIndex;
 };
 
+struct ComdatEntry {
+  ComdatKind Kind;
+  uint32_t Index;
+};
+
+struct Comdat {
+  StringRef Name;
+  std::vector<ComdatEntry> Entries;
+};
+
 struct Section {
   explicit Section(SectionType SecType) : Type(SecType) {}
   virtual ~Section();
 
   SectionType Type;
   std::vector<Relocation> Relocations;
 };
 
static bool classof(const Section *S) {
     auto C = dyn_cast<CustomSection>(S);
     return C && C->Name == "linking";
   }
 
   uint32_t DataSize;
   std::vector<SymbolInfo> SymbolInfos;
   std::vector<SegmentInfo> SegmentInfos;
   std::vector<InitFunction> InitFunctions;
+  std::vector<Comdat> Comdats;
 };
 
 struct TypeSection : Section {
   TypeSection() : Section(wasm::WASM_SEC_TYPE) {}
 
   static bool classof(const Section *S) {
     return S->Type == wasm::WASM_SEC_TYPE;
   }

 LLVM_YAML_IS_SEQUENCE_VECTOR(llvm::WasmYAML::Global)
 LLVM_YAML_IS_SEQUENCE_VECTOR(llvm::WasmYAML::Function)
 LLVM_YAML_IS_SEQUENCE_VECTOR(llvm::WasmYAML::LocalDecl)
 LLVM_YAML_IS_SEQUENCE_VECTOR(llvm::WasmYAML::Relocation)
 LLVM_YAML_IS_SEQUENCE_VECTOR(llvm::WasmYAML::NameEntry)
 LLVM_YAML_IS_SEQUENCE_VECTOR(llvm::WasmYAML::SegmentInfo)
 LLVM_YAML_IS_SEQUENCE_VECTOR(llvm::WasmYAML::SymbolInfo)
 LLVM_YAML_IS_SEQUENCE_VECTOR(llvm::WasmYAML::InitFunction)
+LLVM_YAML_IS_SEQUENCE_VECTOR(llvm::WasmYAML::ComdatEntry)
+LLVM_YAML_IS_SEQUENCE_VECTOR(llvm::WasmYAML::Comdat)
 
 namespace llvm {
 namespace yaml {
 
 template <> struct MappingTraits<WasmYAML::FileHeader> {
   static void mapping(IO &IO, WasmYAML::FileHeader &FileHdr);
 };
 

 template <> struct MappingTraits<WasmYAML::SymbolInfo> {
   static void mapping(IO &IO, WasmYAML::SymbolInfo &Info);
 };
 
 template <> struct MappingTraits<WasmYAML::InitFunction> {
   static void mapping(IO &IO, WasmYAML::InitFunction &Init);
 };
 
+template <> struct ScalarEnumerationTraits<WasmYAML::ComdatKind> {
+  static void enumeration(IO &IO, WasmYAML::ComdatKind &Kind);
+};
+
+template <> struct MappingTraits<WasmYAML::ComdatEntry> {
+  static void mapping(IO &IO, WasmYAML::ComdatEntry &ComdatEntry);
+};
+
+template <> struct MappingTraits<WasmYAML::Comdat> {
+  static void mapping(IO &IO, WasmYAML::Comdat &Comdat);
+};
+
 template <> struct ScalarEnumerationTraits<WasmYAML::ValueType> {
   static void enumeration(IO &IO, WasmYAML::ValueType &Type);
 };
 
 template <> struct ScalarEnumerationTraits<WasmYAML::ExportKind> {
   static void enumeration(IO &IO, WasmYAML::ExportKind &Kind);
 };
 

llvm/trunk/lib/CodeGen/TargetLoweringObjectFileImpl.cpp

void TargetLoweringObjectFileCOFF::emitLinkerFlagsForGlobal(
     raw_ostream &OS, const GlobalValue *GV) const {
   emitLinkerFlagsForGlobalCOFF(OS, GV, getTargetTriple(), getMangler());
 }
 
 //===----------------------------------------------------------------------===//
 //                                  Wasm
 //===----------------------------------------------------------------------===//
 
-static void checkWasmComdat(const GlobalValue *GV) {
+static const Comdat *getWasmComdat(const GlobalValue *GV) {
   const Comdat *C = GV->getComdat();
   if (!C)
-    return;
+    return nullptr;
 
-  // TODO(sbc): At some point we may need COMDAT support but currently
-  // they are not supported.
-  report_fatal_error("WebAssembly doesn't support COMDATs, '" + C->getName() +
-                     "' cannot be lowered.");
+  if (C->getSelectionKind() != Comdat::Any)
+    report_fatal_error("WebAssembly COMDATs only support "
+                       "SelectionKind::Any, '" + C->getName() + "' cannot be "
+                       "lowered.");
+
+  return C;
 }
 
 static SectionKind getWasmKindForNamedSection(StringRef Name, SectionKind K) {
   // If we're told we have function data, then use that.
   if (K.isText())
     return SectionKind::getText();
 
   // Otherwise, ignore whatever section type the generic impl detected and use
   // a plain data section.
   return SectionKind::getData();
 }
 
 MCSection *TargetLoweringObjectFileWasm::getExplicitSectionGlobal(
     const GlobalObject *GO, SectionKind Kind, const TargetMachine &TM) const {
   StringRef Name = GO->getSection();
-  checkWasmComdat(GO);
+
   Kind = getWasmKindForNamedSection(Name, Kind);
-  return getContext().getWasmSection(Name, Kind);
+
+  StringRef Group = "";
+  if (const Comdat *C = getWasmComdat(GO)) {
+    Group = C->getName();
+  }
+
+  return getContext().getWasmSection(Name, Kind, Group,
+                                     MCContext::GenericSectionID);
 }
 
 static MCSectionWasm *selectWasmSectionForGlobal(
     MCContext &Ctx, const GlobalObject *GO, SectionKind Kind, Mangler &Mang,
     const TargetMachine &TM, bool EmitUniqueSection, unsigned *NextUniqueID) {
   StringRef Group = "";
-  checkWasmComdat(GO);
+  if (const Comdat *C = getWasmComdat(GO)) {
+    Group = C->getName();
+  }
 
   bool UniqueSectionNames = TM.getUniqueSectionNames();
   SmallString<128> Name = getSectionPrefixForGlobal(Kind);
 
   if (const auto *F = dyn_cast<Function>(GO)) {
     const auto &OptionalPrefix = F->getSectionPrefix();
     if (OptionalPrefix)
       Name += *OptionalPrefix;

llvm/trunk/lib/MC/WasmObjectWriter.cpp

 struct WasmGlobal {
   wasm::ValType Type;
   bool IsMutable;
   bool HasImport;
   uint64_t InitialValue;
   uint32_t ImportIndex;
 };
 
+// Information about a single item which is part of a COMDAT.  For each data
+// segment or function which is in the COMDAT, there is a corresponding
+// WasmComdatEntry.
+struct WasmComdatEntry {
+  unsigned Kind;
+  uint32_t Index;
+};
+
 // Information about a single relocation.
 struct WasmRelocationEntry {
   uint64_t Offset;                  // Where is the relocation.
   const MCSymbolWasm *Symbol;       // The symbol to relocate with.
   int64_t Addend;                   // A value to add to the symbol.
   unsigned Type;                    // The type of the relocation.
   const MCSectionWasm *FixupSection;// The section the relocation is targeting.
 
private:
   void writeDataSection(ArrayRef<WasmDataSegment> Segments);
   void writeNameSection(ArrayRef<WasmFunction> Functions,
                         ArrayRef<WasmImport> Imports,
                         uint32_t NumFuncImports);
   void writeCodeRelocSection();
   void writeDataRelocSection();
   void writeLinkingMetaDataSection(
       ArrayRef<WasmDataSegment> Segments, uint32_t DataSize,
-      const SmallVector<std::pair<StringRef, uint32_t>, 4> &SymbolFlags,
-      const SmallVector<std::pair<uint16_t, uint32_t>, 2> &InitFuncs);
+      ArrayRef<std::pair<StringRef, uint32_t>> SymbolFlags,
+      ArrayRef<std::pair<uint16_t, uint32_t>> InitFuncs,
+      const std::map<StringRef, std::vector<WasmComdatEntry>>& Comdats);
 
   uint32_t getProvisionalValue(const WasmRelocationEntry &RelEntry);
   void applyRelocations(ArrayRef<WasmRelocationEntry> Relocations,
                         uint64_t ContentsOffset);
 
   void writeRelocations(ArrayRef<WasmRelocationEntry> Relocations);
   uint32_t getRelocationIndexValue(const WasmRelocationEntry &RelEntry);
   uint32_t getFunctionType(const MCSymbolWasm& Symbol);
void WasmObjectWriter::writeDataRelocSection() {
 
   writeRelocations(DataRelocations);
 
   endSection(Section);
 }
 
 void WasmObjectWriter::writeLinkingMetaDataSection(
     ArrayRef<WasmDataSegment> Segments, uint32_t DataSize,
-    const SmallVector<std::pair<StringRef, uint32_t>, 4> &SymbolFlags,
-    const SmallVector<std::pair<uint16_t, uint32_t>, 2> &InitFuncs) {
+    ArrayRef<std::pair<StringRef, uint32_t>> SymbolFlags,
+    ArrayRef<std::pair<uint16_t, uint32_t>> InitFuncs,
+    const std::map<StringRef, std::vector<WasmComdatEntry>>& Comdats) {
   SectionBookkeeping Section;
   startSection(Section, wasm::WASM_SEC_CUSTOM, "linking");
   SectionBookkeeping SubSection;
 
   if (SymbolFlags.size() != 0) {
     startSection(SubSection, wasm::WASM_SYMBOL_INFO);
     encodeULEB128(SymbolFlags.size(), getStream());
     for (auto Pair: SymbolFlags) {
if (!InitFuncs.empty()) {
     encodeULEB128(InitFuncs.size(), getStream());
     for (auto &StartFunc : InitFuncs) {
       encodeULEB128(StartFunc.first, getStream()); // priority
       encodeULEB128(StartFunc.second, getStream()); // function index
     }
     endSection(SubSection);
   }
 
+  if (Comdats.size()) {
+    startSection(SubSection, wasm::WASM_COMDAT_INFO);
+    encodeULEB128(Comdats.size(), getStream());
+    for (const auto &C : Comdats) {
+      writeString(C.first);
+      encodeULEB128(0, getStream()); // flags for future use
+      encodeULEB128(C.second.size(), getStream());
+      for (const WasmComdatEntry &Entry : C.second) {
+        encodeULEB128(Entry.Kind, getStream());
+        encodeULEB128(Entry.Index, getStream());
+      }
+    }
+    endSection(SubSection);
+  }
+
   endSection(Section);
 }
 
 uint32_t WasmObjectWriter::getFunctionType(const MCSymbolWasm& Symbol) {
   assert(Symbol.isFunction());
   assert(TypeIndices.count(&Symbol));
   return TypeIndices[&Symbol];
 }
void WasmObjectWriter::writeObject(MCAssembler &Asm,
 
   // Collect information from the available symbols.
   SmallVector<WasmFunction, 4> Functions;
   SmallVector<uint32_t, 4> TableElems;
   SmallVector<WasmImport, 4> Imports;
   SmallVector<WasmExport, 4> Exports;
   SmallVector<std::pair<StringRef, uint32_t>, 4> SymbolFlags;
   SmallVector<std::pair<uint16_t, uint32_t>, 2> InitFuncs;
+  std::map<StringRef, std::vector<WasmComdatEntry>> Comdats;
   unsigned NumFuncImports = 0;
   SmallVector<WasmDataSegment, 4> DataSegments;
   uint32_t DataSize = 0;
 
   // In the special .global_variables section, we've encoded global
   // variables used by the function. Translate them into the Globals
   // list.
   MCSectionWasm *GlobalVars =
for (MCSection &Sec : Asm) {
     Segment.Name = Section.getSectionName();
     Segment.Offset = DataSize;
     Segment.Section = &Section;
     addData(Segment.Data, Section);
     Segment.Alignment = Section.getAlignment();
     Segment.Flags = 0;
     DataSize += Segment.Data.size();
     Section.setMemoryOffset(Segment.Offset);
+
+    if (const MCSymbolWasm *C = Section.getGroup()) {
+      Comdats[C->getName()].emplace_back(
+          WasmComdatEntry{wasm::WASM_COMDAT_DATA,
+                          static_cast<uint32_t>(DataSegments.size()) - 1});
+    }
   }
 
   // Handle regular defined and undefined symbols.
   for (const MCSymbol &S : Asm.symbols()) {
     // Ignore unnamed temporary symbols, which aren't ever exported, imported,
     // or used in relocations.
     if (S.isTemporary() && S.getName().empty())
       continue;
if (WS.isFunction()) {
       int64_t Size = 0;
       if (!WS.getSize()->evaluateAsAbsolute(Size, Layout))
         report_fatal_error(".size expression must be evaluatable");
 
       // For each global, prepare a corresponding wasm global holding its
       // address.  For externals these will also be named exports.
       Index = NumGlobalImports + Globals.size();
       auto &DataSection = static_cast<MCSectionWasm &>(WS.getSection());
+      assert(DataSection.isWasmData());
 
       WasmGlobal Global;
       Global.Type = PtrType;
       Global.IsMutable = false;
       Global.HasImport = false;
       Global.InitialValue = DataSection.getMemoryOffset() + Layout.getSymbolOffset(WS);
       Global.ImportIndex = 0;
       SymbolIndices[&WS] = Index;
       DEBUG(dbgs() << "  -> global index: " << Index << "\n");
       Globals.push_back(Global);
     }
 
     // If the symbol is visible outside this translation unit, export it.
     if (WS.isDefined(/*SetUsed=*/false)) {
       WasmExport Export;
       Export.FieldName = WS.getName();
       Export.Index = Index;
       if (WS.isFunction())
         Export.Kind = wasm::WASM_EXTERNAL_FUNCTION;
       else
         Export.Kind = wasm::WASM_EXTERNAL_GLOBAL;
       DEBUG(dbgs() << "  -> export " << Exports.size() << "\n");
       Exports.push_back(Export);
+
       if (!WS.isExternal())
         SymbolFlags.emplace_back(WS.getName(), wasm::WASM_SYMBOL_BINDING_LOCAL);
+
+      if (WS.isFunction()) {
+        auto &Section = static_cast<MCSectionWasm &>(WS.getSection(false));
+        if (const MCSymbolWasm *C = Section.getGroup())
+          Comdats[C->getName()].emplace_back(
+              WasmComdatEntry{wasm::WASM_COMDAT_FUNCTION, Index});
+      }
     }
   }
 
   // Handle weak aliases. We need to process these in a separate pass because
   // we need to have processed the target of the alias before the alias itself
   // and the symbols are not necessarily ordered in this way.
   for (const MCSymbol &S : Asm.symbols()) {
     if (!S.isVariable())
void WasmObjectWriter::writeObject(MCAssembler &Asm,
   writeExportSection(Exports);
   writeElemSection(TableElems);
   writeCodeSection(Asm, Layout, Functions);
   writeDataSection(DataSegments);
   writeNameSection(Functions, Imports, NumFuncImports);
   writeCodeRelocSection();
   writeDataRelocSection();
   writeLinkingMetaDataSection(DataSegments, DataSize, SymbolFlags,
-                              InitFuncs);
+                              InitFuncs, Comdats);
 
   // TODO: Translate the .comment section to the output.
   // TODO: Translate debug sections to the output.
 }
 
 std::unique_ptr<MCObjectWriter>
 llvm::createWasmObjectWriter(std::unique_ptr<MCWasmObjectTargetWriter> MOTW,
                              raw_pwrite_stream &OS) {
   // FIXME: Can't use make_unique<WasmObjectWriter>(...) as WasmObjectWriter's
   //        destructor is private. Is that necessary?
   return std::unique_ptr<MCObjectWriter>(
       new WasmObjectWriter(std::move(MOTW), OS));
 }

llvm/trunk/lib/Object/WasmObjectFile.cpp

 //===- WasmObjectFile.cpp - Wasm object file implementation ---------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/StringSet.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/BinaryFormat/Wasm.h"
 #include "llvm/MC/SubtargetFeature.h"
 #include "llvm/Object/Binary.h"
 #include "llvm/Object/Error.h"
 #include "llvm/Object/ObjectFile.h"
 #include "llvm/Object/SymbolicFile.h"
 #include "llvm/Object/Wasm.h"
case wasm::WASM_INIT_FUNCS: {
         if (!isValidFunctionIndex(Init.FunctionIndex))
           return make_error<GenericBinaryError>("Invalid function index: " +
                                                     Twine(Init.FunctionIndex),
                                                 object_error::parse_failed);
         LinkingData.InitFunctions.emplace_back(Init);
       }
       break;
     }
+    case wasm::WASM_COMDAT_INFO:
+      if (Error Err = parseLinkingSectionComdat(Ptr, SubSectionEnd))
+        return Err;
+      break;
     default:
       Ptr += Size;
       break;
     }
     if (Ptr != SubSectionEnd)
       return make_error<GenericBinaryError>(
           "Linking sub-section ended prematurely", object_error::parse_failed);
   }
   if (Ptr != End)
     return make_error<GenericBinaryError>("Linking section ended prematurely",
                                           object_error::parse_failed);
   return Error::success();
 }
 
+Error WasmObjectFile::parseLinkingSectionComdat(const uint8_t *&Ptr,
+                                                const uint8_t *End)
+{
+  uint32_t ComdatCount = readVaruint32(Ptr);
+  StringSet<> ComdatSet;
+  while (ComdatCount--) {
+    StringRef Name = readString(Ptr);
+    if (Name.empty() || !ComdatSet.insert(Name).second)
+      return make_error<GenericBinaryError>("Bad/duplicate COMDAT name " + Twine(Name),
+                                            object_error::parse_failed);
+    Comdats.emplace_back(Name);
+    uint32_t Flags = readVaruint32(Ptr);
+    if (Flags != 0)
+      return make_error<GenericBinaryError>("Unsupported COMDAT flags",
+                                            object_error::parse_failed);
+
+    uint32_t EntryCount = readVaruint32(Ptr);
+    while (EntryCount--) {
+      unsigned Kind = readVaruint32(Ptr);
+      unsigned Index = readVaruint32(Ptr);
+      switch (Kind) {
+      default:
+        return make_error<GenericBinaryError>("Invalid COMDAT entry type",
+                                              object_error::parse_failed);
+      case wasm::WASM_COMDAT_DATA:
+        if (Index >= DataSegments.size())
+          return make_error<GenericBinaryError>("COMDAT data index out of range",
+                                                object_error::parse_failed);
+        if (!DataSegments[Index].Data.Comdat.empty())
+          return make_error<GenericBinaryError>("Data segment in two COMDATs",
+                                                object_error::parse_failed);
+        DataSegments[Index].Data.Comdat = Name;
+        break;
+      case wasm::WASM_COMDAT_FUNCTION:
+        if (Index < NumImportedFunctions || !isValidFunctionIndex(Index))
+          return make_error<GenericBinaryError>("COMDAT function index out of range",
+                                                object_error::parse_failed);
+        Index -= NumImportedFunctions;
+        if (!Functions[Index].Comdat.empty())
+          return make_error<GenericBinaryError>("Function in two COMDATs",
+                                                object_error::parse_failed);
+        Functions[Index].Comdat = Name;
+        break;
+      }
+    }
+  }
+  return Error::success();
+}
+
 WasmSection* WasmObjectFile::findCustomSectionByName(StringRef Name) {
   for (WasmSection& Section : Sections) {
     if (Section.Type == wasm::WASM_SEC_CUSTOM && Section.Name == Name)
       return &Section;
   }
   return nullptr;
 }
 

llvm/trunk/lib/ObjectYAML/WasmYAML.cpp

 
 static void sectionMapping(IO &IO, WasmYAML::LinkingSection &Section) {
   commonSectionMapping(IO, Section);
   IO.mapRequired("Name", Section.Name);
   IO.mapRequired("DataSize", Section.DataSize);
   IO.mapOptional("SymbolInfo", Section.SymbolInfos);
   IO.mapOptional("SegmentInfo", Section.SegmentInfos);
   IO.mapOptional("InitFunctions", Section.InitFunctions);
+  IO.mapOptional("Comdats", Section.Comdats);
 }
 
 static void sectionMapping(IO &IO, WasmYAML::CustomSection &Section) {
   commonSectionMapping(IO, Section);
   IO.mapRequired("Name", Section.Name);
   IO.mapRequired("Payload", Section.Payload);
 }
 

 }
 
 void MappingTraits<WasmYAML::InitFunction>::mapping(
     IO &IO, WasmYAML::InitFunction &Init) {
   IO.mapRequired("Priority", Init.Priority);
   IO.mapRequired("FunctionIndex", Init.FunctionIndex);
 }
 
+void ScalarEnumerationTraits<WasmYAML::ComdatKind>::enumeration(
+    IO &IO, WasmYAML::ComdatKind &Kind) {
+#define ECase(X) IO.enumCase(Kind, #X, wasm::WASM_COMDAT_##X);
+  ECase(FUNCTION);
+  ECase(DATA);
+#undef ECase
+}
+
+void MappingTraits<WasmYAML::ComdatEntry>::mapping(
+    IO &IO, WasmYAML::ComdatEntry &ComdatEntry) {
+  IO.mapRequired("Kind", ComdatEntry.Kind);
+  IO.mapRequired("Index", ComdatEntry.Index);
+}
+
+void MappingTraits<WasmYAML::Comdat>::mapping(
+    IO &IO, WasmYAML::Comdat &Comdat) {
+  IO.mapRequired("Name", Comdat.Name);
+  IO.mapRequired("Entries", Comdat.Entries);
+}
+
 void MappingTraits<WasmYAML::SymbolInfo>::mapping(IO &IO,
                                                   WasmYAML::SymbolInfo &Info) {
   IO.mapRequired("Name", Info.Name);
   IO.mapRequired("Flags", Info.Flags);
 }
 
 void ScalarBitSetTraits<WasmYAML::LimitFlags>::bitset(
     IO &IO, WasmYAML::LimitFlags &Value) {

llvm/trunk/test/CodeGen/WebAssembly/comdat.ll

-; RUN: not llc < %s -mtriple wasm32-unknown-unknown-wasm 2>&1 | FileCheck %s
-
-$f = comdat any
-@f = global i32 0, comdat
-; CHECK: LLVM ERROR: WebAssembly doesn't support COMDATs, 'f' cannot be lowered.

llvm/trunk/test/MC/WebAssembly/comdat.ll

+; RUN: llc -mtriple wasm32-unknown-unknown-wasm -filetype=obj %s -o - | obj2yaml | FileCheck %s
+
+; Import a function just so we can check the index arithmetic for
+; WASM_COMDAT_FUNCTION entries is performed correctly
+declare i32 @funcImport()
+define i32 @callImport() {
+entry:
+  %call = call i32 @funcImport()
+  ret i32 %call
+}
+
+; Function in its own COMDAT
+$basicInlineFn = comdat any
+define linkonce_odr i32 @basicInlineFn() #1 comdat {
+  ret i32 0
+}
+
+; Global, data, and function in same COMDAT
+$sharedComdat = comdat any
+@constantData = weak_odr constant [3 x i8] c"abc", comdat($sharedComdat)
+define linkonce_odr i32 @sharedFn() #1 comdat($sharedComdat) {
+  ret i32 0
+}
+
+; CHECK:       - Type:            EXPORT
+; CHECK-NEXT:    Exports:
+; CHECK-NEXT:      - Name:            callImport
+; CHECK-NEXT:        Kind:            FUNCTION
+; CHECK-NEXT:        Index:           1
+; CHECK-NEXT:      - Name:            basicInlineFn
+; CHECK-NEXT:        Kind:            FUNCTION
+; CHECK-NEXT:        Index:           2
+; CHECK-NEXT:      - Name:            sharedFn
+; CHECK-NEXT:        Kind:            FUNCTION
+; CHECK-NEXT:        Index:           3
+; CHECK-NEXT:      - Name:            constantData
+; CHECK-NEXT:        Kind:            GLOBAL
+; CHECK-NEXT:        Index:           1
+; CHECK-NEXT:  - Type:            CODE
+; CHECK-NEXT:    Relocations:
+; CHECK-NEXT:      - Type:            R_WEBASSEMBLY_FUNCTION_INDEX_LEB
+; CHECK-NEXT:        Index:           0
+; CHECK-NEXT:        Offset:          0x00000004
+; CHECK-NEXT:    Functions:
+; CHECK-NEXT:      - Index:           1
+; CHECK-NEXT:        Locals:
+; CHECK-NEXT:        Body:            1080808080000B
+; CHECK-NEXT:      - Index:           2
+; CHECK-NEXT:        Locals:
+; CHECK-NEXT:        Body:            41000B
+; CHECK-NEXT:      - Index:           3
+; CHECK-NEXT:        Locals:
+; CHECK-NEXT:        Body:            41000B
+; CHECK-NEXT:  - Type:            DATA
+; CHECK-NEXT:    Segments:
+; CHECK-NEXT:      - SectionOffset:   6
+; CHECK-NEXT:        MemoryIndex:     0
+; CHECK-NEXT:        Offset:
+; CHECK-NEXT:          Opcode:          I32_CONST
+; CHECK-NEXT:          Value:           0
+; CHECK-NEXT:        Content:         '616263'
+; CHECK-NEXT:  - Type:            CUSTOM
+; CHECK-NEXT:    Name:            name
+; CHECK-NEXT:    FunctionNames:
+; CHECK-NEXT:      - Index:           0
+; CHECK-NEXT:        Name:            funcImport
+; CHECK-NEXT:      - Index:           1
+; CHECK-NEXT:        Name:            callImport
+; CHECK-NEXT:      - Index:           2
+; CHECK-NEXT:        Name:            basicInlineFn
+; CHECK-NEXT:      - Index:           3
+; CHECK-NEXT:        Name:            sharedFn
+; CHECK-NEXT:  - Type:            CUSTOM
+; CHECK-NEXT:    Name:            linking
+; CHECK-NEXT:    DataSize:        3
+; CHECK-NEXT:    SymbolInfo:
+; CHECK-NEXT:      - Name:            basicInlineFn
+; CHECK-NEXT:        Flags:           [ BINDING_WEAK ]
+; CHECK-NEXT:      - Name:            sharedFn
+; CHECK-NEXT:        Flags:           [ BINDING_WEAK ]
+; CHECK-NEXT:      - Name:            constantData
+; CHECK-NEXT:        Flags:           [ BINDING_WEAK ]
+; CHECK-NEXT:    SegmentInfo:
+; CHECK-NEXT:      - Index:           0
+; CHECK-NEXT:        Name:            .rodata.constantData
+; CHECK-NEXT:        Alignment:       1
+; CHECK-NEXT:        Flags:           [  ]
+; CHECK-NEXT:    Comdats:
+; CHECK-NEXT:      - Name:            basicInlineFn
+; CHECK-NEXT:        Entries:
+; CHECK-NEXT:          - Kind:            FUNCTION
+; CHECK-NEXT:            Index:           2
+; CHECK-NEXT:      - Name:            sharedComdat
+; CHECK-NEXT:        Entries:
+; CHECK-NEXT:          - Kind:            FUNCTION
+; CHECK-NEXT:            Index:           3
+; CHECK-NEXT:          - Kind:            DATA
+; CHECK-NEXT:            Index:           0
+; CHECK-NEXT: ...

llvm/trunk/tools/obj2yaml/wasm2yaml.cpp

for (const object::SymbolRef& Sym: Obj.symbols()) {
       WasmYAML::NameEntry NameEntry;
       NameEntry.Name = Symbol.Name;
       NameEntry.Index = Sym.getValue();
       NameSec->FunctionNames.push_back(NameEntry);
     }
     CustomSec = std::move(NameSec);
   } else if (WasmSec.Name == "linking") {
     std::unique_ptr<WasmYAML::LinkingSection> LinkingSec = make_unique<WasmYAML::LinkingSection>();
-    size_t Index = 0;
+    std::map<StringRef,size_t> ComdatIndexes;
+    for (StringRef ComdatName : Obj.comdats()) {
+      ComdatIndexes[ComdatName] = LinkingSec->Comdats.size();
+      LinkingSec->Comdats.emplace_back(WasmYAML::Comdat{ComdatName, {}});
+    }
+    for (auto &Func : Obj.functions()) {
+      if (!Func.Comdat.empty()) {
+        auto &Comdat = LinkingSec->Comdats[ComdatIndexes[Func.Comdat]];
+        Comdat.Entries.emplace_back(
+                WasmYAML::ComdatEntry{wasm::WASM_COMDAT_FUNCTION, Func.Index});
+      }
+    }
+    uint32_t SegmentIndex = 0;
     for (const object::WasmSegment &Segment : Obj.dataSegments()) {
       if (!Segment.Data.Name.empty()) {
         WasmYAML::SegmentInfo SegmentInfo;
         SegmentInfo.Name = Segment.Data.Name;
-        SegmentInfo.Index = Index;
+        SegmentInfo.Index = SegmentIndex;
         SegmentInfo.Alignment = Segment.Data.Alignment;
         SegmentInfo.Flags = Segment.Data.Flags;
         LinkingSec->SegmentInfos.push_back(SegmentInfo);
       }
-      Index++;
+      if (!Segment.Data.Comdat.empty()) {
+        auto &Comdat = LinkingSec->Comdats[ComdatIndexes[Segment.Data.Comdat]];
+        Comdat.Entries.emplace_back(
+            WasmYAML::ComdatEntry{wasm::WASM_COMDAT_DATA, SegmentIndex});
+      }
+      SegmentIndex++;
     }
     for (const object::SymbolRef& Sym: Obj.symbols()) {
       const object::WasmSymbol Symbol = Obj.getWasmSymbol(Sym);
       if (Symbol.Flags != 0) {
         WasmYAML::SymbolInfo Info{Symbol.Name, Symbol.Flags};
         LinkingSec->SymbolInfos.emplace_back(Info);
       }
     }

llvm/trunk/tools/yaml2obj/yaml2wasm.cpp

if (Section.InitFunctions.size()) {
     encodeULEB128(wasm::WASM_INIT_FUNCS, OS);
     encodeULEB128(Section.InitFunctions.size(), SubSection.GetStream());
     for (const WasmYAML::InitFunction &Func : Section.InitFunctions) {
       encodeULEB128(Func.Priority, SubSection.GetStream());
       encodeULEB128(Func.FunctionIndex, SubSection.GetStream());
     }
     SubSection.Done();
   }
+
+  // COMDAT_INFO subsection
+  if (Section.Comdats.size()) {
+    encodeULEB128(wasm::WASM_COMDAT_INFO, OS);
+    encodeULEB128(Section.Comdats.size(), SubSection.GetStream());
+    for (const auto &C : Section.Comdats) {
+      writeStringRef(C.Name, SubSection.GetStream());
+      encodeULEB128(0, SubSection.GetStream()); // flags for future use
+      encodeULEB128(C.Entries.size(), SubSection.GetStream());
+      for (const WasmYAML::ComdatEntry &Entry : C.Entries) {
+        encodeULEB128(Entry.Kind, SubSection.GetStream());
+        encodeULEB128(Entry.Index, SubSection.GetStream());
+      }
+    }
+    SubSection.Done();
+  }
+
   return 0;
 }
 
 int WasmWriter::writeSectionContent(raw_ostream &OS, WasmYAML::NameSection &Section) {
   writeStringRef(Section.Name, OS);
   if (Section.FunctionNames.size()) {
     encodeULEB128(wasm::WASM_NAMES_FUNCTION, OS);