[WebAssembly] Add support for init functions linking metadata

[sbc100]

Summary

This change lays the groundwork lowering of @llvm.global_ctors
and @llvm.global_dtors for the wasm object format. Some parts
of this patch are subset of: https://reviews.llvm.org/D40759

See https://github.com/WebAssembly/tool-conventions/issues/25

[ncw]

Looks good.

At the back of my mind, I'm just wondering about how Comdat interacts with this. In the .init_array it's fairly simple, since the data section containing the function pointer is handled just like any other data section and is included/excluded as necessary. Is it ever possible for a global ctor to be registered in a COMDAT, maybe for static class members in template classes? In that case we'll need to remember to check that duplicate INIT_FUNCS are discarded (if indeed they can participate in Comdat discarding).

I think the right way to model that would be in the Comdat data. (This is all assuming we do Comdat groups...) Currently Comdat group data is a vector of typed function/data-segment indices. Now that INIT_FUNCS aren't in the .init_array data segment, we'll need to make the Comdat group to be a vector of type function/data-segment/INIT_FUNCS indices.

lib/Object/WasmObjectFile.cpp

675 ↗

(On Diff #126868)

You've changed the behaviour of parseStartSection, which used to take a function index excluding the imported functions.

Is that deliberate? These indexes are slippery... I would have thought that both parseStartSection and WASM_INIT_FUNCS should only be able to specify a defined function, ie the range should not include the imported functions.

[sunfish]

In D41208#955130, @ncw wrote:

Looks good.

At the back of my mind, I'm just wondering about how Comdat interacts with this. In the .init_array it's fairly simple, since the data section containing the function pointer is handled just like any other data section and is included/excluded as necessary. Is it ever possible for a global ctor to be registered in a COMDAT, maybe for static class members in template classes? In that case we'll need to remember to check that duplicate INIT_FUNCS are discarded (if indeed they can participate in Comdat discarding).

I think the right way to model that would be in the Comdat data. (This is all assuming we do Comdat groups...) Currently Comdat group data is a vector of typed function/data-segment indices. Now that INIT_FUNCS aren't in the .init_array data segment, we'll need to make the Comdat group to be a vector of type function/data-segment/INIT_FUNCS indices.

LLVM handles this in @llvm.global_ctors by making each entry consist of:

• the constructor function address
• a priority value
• an "associated" symbol, which when non-null refers to a comdat group

So, another approach would be to do something similar, and add a comdat symbol to the WASM_START_FUNCS entries (see also here), which would reflect LLVM's structure pretty closely. I don't have a strong opinion about whether this is better than doing it within the comdat metadata section though.

lib/Object/WasmObjectFile.cpp

675 ↗

(On Diff #126868)

The underlying wasm start function takes a plain function index, which includes the imports, so I think it does make sense for low-level tools like this to use the same index space.

If there are tools where it's complex to support this, I think it's fine to issue an error if the index is an import, but using the same index space everywhere is one way to keep a semblance of a foothold in this slippery terrain.

[ncw]

In D41208#955207, @sunfish wrote:

So, another approach would be to do something similar, and add a comdat symbol to the WASM_START_FUNCS entries (see also here), which would reflect LLVM's structure pretty closely. I don't have a strong opinion about whether this is better than doing it within the comdat metadata section though.

Either way works. My preference for putting things in the Comdat metadata section is simply to avoid having to write out the string name for the Comdat multiple times (which could be veeery long for STL templated methods!) - or alternatively avoids referring to Comdats by some "Comdat index" which is a bit more awkward because then you'd have to make the list of Comdats up-front and it's just (marginally) more work.

lib/Object/WasmObjectFile.cpp

675 ↗

(On Diff #126868)

That makes sense. I guess it should then have a branch added && Index >= NumImportedFunctions

[sbc100]

In D41208#955217, @ncw wrote:

In D41208#955207, @sunfish wrote:

So, another approach would be to do something similar, and add a comdat symbol to the WASM_START_FUNCS entries (see also here), which would reflect LLVM's structure pretty closely. I don't have a strong opinion about whether this is better than doing it within the comdat metadata section though.

Either way works. My preference for putting things in the Comdat metadata section is simply to avoid having to write out the string name for the Comdat multiple times (which could be veeery long for STL templated methods!) - or alternatively avoids referring to Comdats by some "Comdat index" which is a bit more awkward because then you'd have to make the list of Comdats up-front and it's just (marginally) more work.

My preference would be always refer to symbols, rather than including strings in either the COMDAT section or the init funcs. So one can refer to a COMDAT by symbol. I think this is how ELF does it. We don't have a great notion of symbol index right now (because some symbols and functions and some are globals), but I think we need one. Dan proposed doing this for the SYMBOL_INFO metadata already and I think we should do that.

lib/Object/WasmObjectFile.cpp

675 ↗

(On Diff #126868)

This is basically a bug fix from Dan's branch. I think the new code is correct. Start function was always meant to be in the function index space and the check was simply wrong before.

[ncw]

In D41208#955451, @sbc100 wrote:

My preference would be always refer to symbols, rather than including strings in either the COMDAT section or the init funcs. So one can refer to a COMDAT by symbol. I think this is how ELF does it. We don't have a great notion of symbol index right now (because some symbols and functions and some are globals), but I think we need one. Dan proposed doing this for the SYMBOL_INFO metadata already and I think we should do that.

I think the Comdat metadata will should include a string name for the Comdat - although as an optimisation I suppose we could point to an index in the "names" metadata. The LLVM IR fully supports the notion of named Comdats, and I don't think we'd want to impose too much on the different language frontends, ie we want to be compatible with any legal IR that a frontend might produce, with lowering passes for anything we don't want to support. A Comdat could contain multiple symbols or chunks of data, and could have its own name - otherwise Haskell or Rust or who knows what will complain.

In ELF, the Comdat is named independently from the symbol(s) it contains. It's just that the Comdat's name and the symbol names are both indexes into the same table of names, so the string data itself isn't duplicated in the ELF binary. They are still named independently though, even though it's overwhelmingly common for the Comdat's name to match the name of an existing symbol.

[sbc100]

In D41208#955465, @ncw wrote:

In D41208#955451, @sbc100 wrote:

My preference would be always refer to symbols, rather than including strings in either the COMDAT section or the init funcs. So one can refer to a COMDAT by symbol. I think this is how ELF does it. We don't have a great notion of symbol index right now (because some symbols and functions and some are globals), but I think we need one. Dan proposed doing this for the SYMBOL_INFO metadata already and I think we should do that.

I think the Comdat metadata will should include a string name for the Comdat - although as an optimisation I suppose we could point to an index in the "names" metadata. The LLVM IR fully supports the notion of named Comdats, and I don't think we'd want to impose too much on the different language frontends, ie we want to be compatible with any legal IR that a frontend might produce, with lowering passes for anything we don't want to support. A Comdat could contain multiple symbols or chunks of data, and could have its own name - otherwise Haskell or Rust or who knows what will complain.

In ELF, the Comdat is named independently from the symbol(s) it contains. It's just that the Comdat's name and the symbol names are both indexes into the same table of names, so the string data itself isn't duplicated in the ELF binary. They are still named independently though, even though it's overwhelmingly common for the Comdat's name to match the name of an existing symbol.

I think maybe you misunderstood or I wasn't clear. I wasn't suggesting dropping named COMDATs. Just that we should use the symbol tables to store the strings, like ELF does. So the name of the COMDAT and then name of a function can be stored in the same string/symbol table. Basically I want to make symbol a more first class thing.

[ncw]

Ah, that sounds good.

I wonder what will happen to Comdats anyway... I'm just waiting to see, as an outsider it's not really my place to prod any decisions! I'm still a bit bemused why there's so much resistance to Comdat groups - which are simple and model the C++ and LLVM IR semantics exactly. It just feels like what we're being asked to implement, with the SHF_LINK_ORDER thing, is a semi-untested idea, given that it's not actually how the ELF does things currently (it applies Comdat groups first). I'm also a bit uneasy about relying so heavily on GC, so that rather than just being a filesize optimisation it becomes a vital component to the linking model's semantics. Even if we did have GC, doing Comdat discarding first would be a reassuring way of getting the "right" semantics, so that GC can be tweaked without worrying so much about introducing bugs. Not up to me to decide though!

[sbc100]

In D41208#955548, @ncw wrote:

Ah, that sounds good.

I wonder what will happen to Comdats anyway... I'm just waiting to see, as an outsider it's not really my place to prod any decisions! I'm still a bit bemused why there's so much resistance to Comdat groups - which are simple and model the C++ and LLVM IR semantics exactly. It just feels like what we're being asked to implement, with the SHF_LINK_ORDER thing, is a semi-untested idea, given that it's not actually how the ELF does things currently (it applies Comdat groups first). I'm also a bit uneasy about relying so heavily on GC, so that rather than just being a filesize optimisation it becomes a vital component to the linking model's semantics. Even if we did have GC, doing Comdat discarding first would be a reassuring way of getting the "right" semantics, so that GC can be tweaked without worrying so much about introducing bugs. Not up to me to decide though!

You opinion (as someone who has been doing a lot of the work in this area) certainly does matter here. I think its worth a little more consideration but ultimately if COMDAT support you have implemented does the job of supporting C++ needs and the alternative is more complicated then we have a good argument for landing it.

I would suggest that we look bit more at the COFF associative COMDATs (which is apparently similar, but more obviously designed to implement COMDAT). My understanding is that that technique basically still results in named groups, but that the groups are defined by a chain (each section depends on at most one other one, and each group points to the top of a chain).

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

 
 struct WasmRelocation {
   uint32_t Type;   // The type of the relocation.
   uint32_t Index;  // Index into function to global index space.
   uint64_t Offset; // Offset from the start of the section.
   int64_t Addend;  // A value to add to the symbol.
 };
 
+struct WasmInitFunc {
+  uint32_t Priority;
+  uint32_t FunctionIndex;
+};
+
 struct WasmLinkingData {
   uint32_t DataSize;
+  std::vector<WasmInitFunc> InitFunctions;
 };
 
 enum : unsigned {
   WASM_SEC_CUSTOM = 0,   // Custom / User-defined section
   WASM_SEC_TYPE = 1,     // Function signature declarations
   WASM_SEC_IMPORT = 2,   // Import declarations
   WASM_SEC_FUNCTION = 3, // Function declarations
   WASM_SEC_TABLE = 4,    // Indirect function table and other tables
enum class ValType {
   F64 = WASM_TYPE_F64,
 };
 
 // Linking metadata kinds.
 enum : unsigned {
   WASM_SYMBOL_INFO    = 0x2,
   WASM_DATA_SIZE      = 0x3,
   WASM_SEGMENT_INFO   = 0x5,
+  WASM_INIT_FUNCS     = 0x6,
 };
 
 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:
   section_iterator section_end() const override;
   uint8_t getBytesInAddress() const override;
   StringRef getFileFormatName() const override;
   unsigned getArch() const override;
   SubtargetFeatures getFeatures() const override;
   bool isRelocatableObject() const override;
 
 private:
+  bool isValidFunctionIndex(uint32_t Index) const;
   const WasmSection &getWasmSection(DataRefImpl Ref) const;
   const wasm::WasmRelocation &getWasmRelocation(DataRefImpl Ref) const;
 
   WasmSection* findCustomSectionByName(StringRef Name);
   WasmSection* findSectionByType(uint32_t Type);
 
   const uint8_t *getPtr(size_t Offset) const;
   Error parseSection(WasmSection &Sec);

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

struct Signature {
   ValueType ReturnType;
 };
 
 struct SymbolInfo {
   StringRef Name;
   SymbolFlags Flags;
 };
 
+struct InitFunction {
+  uint32_t Priority;
+  uint32_t FunctionIndex;
+};
+
 struct Section {
   explicit Section(SectionType SecType) : Type(SecType) {}
   virtual ~Section();
 
   SectionType Type;
   std::vector<Relocation> Relocations;
 };
 
struct LinkingSection : CustomSection {
   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;
 };
 
 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::DataSegment)
 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)
 
 namespace llvm {
 namespace yaml {
 
 template <> struct MappingTraits<WasmYAML::FileHeader> {
   static void mapping(IO &IO, WasmYAML::FileHeader &FileHdr);
 };
 

 template <> struct MappingTraits<WasmYAML::ElemSegment> {
   static void mapping(IO &IO, WasmYAML::ElemSegment &Segment);
 };
 
 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::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/Object/WasmObjectFile.cpp

case wasm::WASM_SEGMENT_INFO: {
                                               object_error::parse_failed);
       for (uint32_t i = 0; i < Count; i++) {
         DataSegments[i].Data.Name = readString(Ptr);
         DataSegments[i].Data.Alignment = readVaruint32(Ptr);
         DataSegments[i].Data.Flags = readVaruint32(Ptr);
       }
       break;
     }
+    case wasm::WASM_INIT_FUNCS: {
+      uint32_t Count = readVaruint32(Ptr);
+      LinkingData.InitFunctions.reserve(Count);
+      for (uint32_t i = 0; i < Count; i++) {
+        wasm::WasmInitFunc Init;
+        Init.Priority = readVaruint32(Ptr);
+        Init.FunctionIndex = readVaruint32(Ptr);
+        if (!isValidFunctionIndex(Init.FunctionIndex))
+          return make_error<GenericBinaryError>("Invalid function index: " +
+                                                    Twine(Init.FunctionIndex),
+                                                object_error::parse_failed);
+        LinkingData.InitFunctions.emplace_back(Init);
+      }
+      break;
+    }
     default:
       Ptr += Size;
       break;
     }
     if (Ptr != SubSectionEnd)
       return make_error<GenericBinaryError>(
           "Linking sub-section ended prematurely", object_error::parse_failed);
   }
for (uint32_t i = 0; i < Count; i++) {
     Exports.push_back(Ex);
   }
   if (Ptr != End)
     return make_error<GenericBinaryError>("Export section ended prematurely",
                                           object_error::parse_failed);
   return Error::success();
 }
 
+bool WasmObjectFile::isValidFunctionIndex(uint32_t Index) const {
+  return Index < FunctionTypes.size() + NumImportedFunctions;
+}
+
 Error WasmObjectFile::parseStartSection(const uint8_t *Ptr, const uint8_t *End) {
   StartFunction = readVaruint32(Ptr);
-  if (StartFunction >= FunctionTypes.size())
+  if (!isValidFunctionIndex(StartFunction))
     return make_error<GenericBinaryError>("Invalid start function",
                                           object_error::parse_failed);
   return Error::success();
 }
 
 Error WasmObjectFile::parseCodeSection(const uint8_t *Ptr, const uint8_t *End) {
   uint32_t FunctionCount = readVaruint32(Ptr);
   if (FunctionCount != FunctionTypes.size()) {

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);
 }
 
 static void sectionMapping(IO &IO, WasmYAML::CustomSection &Section) {
   commonSectionMapping(IO, Section);
   IO.mapRequired("Name", Section.Name);
   IO.mapRequired("Payload", Section.Payload);
 }
 

 void MappingTraits<WasmYAML::DataSegment>::mapping(
     IO &IO, WasmYAML::DataSegment &Segment) {
   IO.mapOptional("SectionOffset", Segment.SectionOffset);
   IO.mapRequired("MemoryIndex", Segment.MemoryIndex);
   IO.mapRequired("Offset", Segment.Offset);
   IO.mapRequired("Content", Segment.Content);
 }
 
+void MappingTraits<WasmYAML::InitFunction>::mapping(
+    IO &IO, WasmYAML::InitFunction &Init) {
+  IO.mapRequired("Priority", Init.Priority);
+  IO.mapRequired("FunctionIndex", Init.FunctionIndex);
+}
+
 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/ObjectYAML/wasm/linking_section.yaml

SegmentInfo:
       - Index:       0
         Alignment:   4
         Flags:       [ ]
         Name:        mydata
       - Index:       1
         Alignment:   2
         Flags:       [ ]
         Name:        moredata
+    InitFunctions:
+      - Priority:      1
+        FunctionIndex: 0
 ...
 # CHECK:       - Type:            CUSTOM
 # CHECK-NEXT:    Name:            linking
 # CHECK-NEXT:    DataSize:        999
 # CHECK-NEXT:    SymbolInfo:
 # CHECK-NEXT:      - Name:            bar
 # CHECK-NEXT:        Flags:           [ BINDING_WEAK ]
 # CHECK-NEXT:    SegmentInfo:
 # CHECK-NEXT:      - Index:           0
 # CHECK-NEXT:        Name:            mydata
 # CHECK-NEXT:        Alignment:       4
 # CHECK-NEXT:        Flags:           [ ]
 # CHECK-NEXT:      - Index:           1
 # CHECK-NEXT:        Name:            moredata
 # CHECK-NEXT:        Alignment:       2
 # CHECK-NEXT:        Flags:           [ ]
+# CHECK-NEXT:    InitFunctions:
+# CHECK-NEXT:       - Priority:       1
+# CHECK-NEXT:         FunctionIndex:  0
 # CHECK-NEXT: ...

llvm/trunk/tools/obj2yaml/wasm2yaml.cpp

for (const object::WasmSegment &Segment : Obj.dataSegments()) {
         SegmentInfo.Flags = Segment.Data.Flags;
         LinkingSec->SegmentInfos.push_back(SegmentInfo);
       }
       Index++;
     }
     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.push_back(Info);
+        WasmYAML::SymbolInfo Info{Symbol.Name, Symbol.Flags};
+        LinkingSec->SymbolInfos.emplace_back(Info);
       }
     }
     LinkingSec->DataSize = Obj.linkingData().DataSize;
+    for (const wasm::WasmInitFunc &Func : Obj.linkingData().InitFunctions) {
+      WasmYAML::InitFunction F{Func.Priority, Func.FunctionIndex};
+      LinkingSec->InitFunctions.emplace_back(F);
+    }
     CustomSec = std::move(LinkingSec);
   } else {
     CustomSec = make_unique<WasmYAML::CustomSection>(WasmSec.Name);
   }
   CustomSec->Payload = yaml::BinaryRef(WasmSec.Content);
   return CustomSec;
 }
 

llvm/trunk/tools/yaml2obj/yaml2wasm.cpp

if (Section.SegmentInfos.size()) {
     encodeULEB128(Section.SegmentInfos.size(), SubSection.GetStream());
     for (const WasmYAML::SegmentInfo &SegmentInfo : Section.SegmentInfos) {
       writeStringRef(SegmentInfo.Name, SubSection.GetStream());
       encodeULEB128(SegmentInfo.Alignment, SubSection.GetStream());
       encodeULEB128(SegmentInfo.Flags, SubSection.GetStream());
     }
     SubSection.Done();
   }
+
+  // INIT_FUNCS subsection
+  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();
+  }
   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);