[WebAssembly] Refactor order of creation for SyntheticFunction

[ncw]

Summary

Previously we created __wasm_call_ctors with null InputFunction, and added the InputFunction later. Now we create the SyntheticFunction with null body, and set the body later.

---

This will allow placing SyntheticFunctions at the start of the Wasm file. This is a useful refactor I think! You may think otherwise...

[ruiu]

I'd guess that the motivation of this change is to start processing global constructors as quickly as possible by putting them at beginning of a file when we execute a wasm binary with a streaming decoder & executor. Am I correct?

[ncw]

In D44206#1030099, @ruiu wrote:

I'd guess that the motivation of this change is to start processing global constructors as quickly as possible by putting them at beginning of a file when we execute a wasm binary with a streaming decoder & executor. Am I correct?

Yes, that's right :) There's a TODO to that effect in Writer::assignIndexes, I should probably add a short permanent comment just as well to note that it's desirable for __wasm_call_ctors to come early on.

Secondarily, it's also a very nice simplification to Writer::createCtorFunction, which previously did all sorts of stuff with indexes and the Live bit.. three or four lines of duplicated code from elsewhere in Writer, whereas creating the SyntheticFunction object up-front means that's all handled automatically at the same as those are set for all the other InputFunctions.

[ruiu]

If that's the case, I don't think just putting a .ctor at beginning of a file is not enough. You probably should sort functions by topological order so that the functions and data that a .ctor needs are available early.

[sbc100]

Nice. I like this increased abstraction and generalization this buys us.

LGTM, with comments.

wasm/SymbolTable.h

55

Newline between method bodies.

82

Maybe move these up to where ObjectFiles is defined (and make them public). They seem to fit the same category to me, and it would save adding accessors.

wasm/Writer.cpp

884

Should use cast<> here and define a classof() for syntheticfunction? Would that buy is anything?

[sbc100]

In D44206#1030142, @ruiu wrote:

If that's the case, I don't think just putting a .ctor at beginning of a file is not enough. You probably should sort functions by topological order so that the functions and data that a .ctor needs are available early.

I don't see that as the reason for this change. This seems like more of refactor to make the code cleaner and more re-usable. Nicolas has another change pending that will add synthetic functions to allow weak undefined functions to be called which builds on the generality in this change.

I fact, this change doesn't change the order of any functions, as can be seen by the fact that no unit tests changed.

@ncw, and you add NFC to the title and update the title and the description to more accurately describe what this change does. Its not really just about the __wasm_call_ctors, and it doesn't effect the ordering in the file, right?

[sbc100]

Also, it should be noted that it is too early to say if ordering of the functions withing the wasm file means anything to any of the engines, so any change that was aimed purely at that would be premature.

[ruiu]

I'm not sure if this is a good change as a refactoring...

wasm/Driver.cpp

302–303

I think you should directly pass make's return value instead because you are using it only once.

wasm/InputChunks.h

165–168

I don't actually know if this is a good thing. Currently a syntehtic function is immutable, but now with this change it is mutable. It is not a good thing in general.

[ncw]

Updated: nits, clang-format, and added classof for SyntheticFunction

[ncw]

wasm/InputChunks.h

165–168

There's an upside and a downside - previously we were mutating the DefinedFunction symbol object. So there's no extra mutation, it's just shifted from one object to another. It's "safer" I think to mutate the SyntheticFunction, since nothing looks at its body until the very end (when the CODE section is written out), whereas it's more dangerous to mutate the symbol, since various fields are retrieved from it earlier on.

[sbc100]

wasm/InputChunks.h

165–168

I agree with @ncw here. Previously we were mutating the symbol to point to an entirely new function, not we are only mutating the body of the function and leaving the symbol alone.

I can see more refinements here down the road but think this is step forward.

[ruiu]

wasm/InputChunks.h

165–168

I don't like the fact that this class has two ways to set body. But you can eliminate Body from the constructor , no?

[ncw]

wasm/InputChunks.h

165–168

Done, removed Body from the constructor

wasm/Driver.cpp

 //===- Driver.cpp ---------------------------------------------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "lld/Common/Driver.h"
 #include "Config.h"
+#include "InputChunks.h"
 #include "InputGlobal.h"
 #include "MarkLive.h"
 #include "SymbolTable.h"
 #include "Writer.h"
 #include "lld/Common/Args.h"
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Memory.h"
 #include "lld/Common/Threads.h"
if (!Config->Relocatable) {
     // "mutable global" proposal is accepted.
     StackPointerGlobal.Type = {WASM_TYPE_I32, true};
     StackPointerGlobal.InitExpr.Value.Int32 = 0;
     StackPointerGlobal.InitExpr.Opcode = WASM_OPCODE_I32_CONST;
     InputGlobal *StackPointer = make<InputGlobal>(StackPointerGlobal);
     StackPointer->Live = true;
 
     static WasmSignature NullSignature = {{}, WASM_TYPE_NORESULT};
+
     // Add synthetic symbols before any others
     WasmSym::CallCtors = Symtab->addSyntheticFunction(
-        "__wasm_call_ctors", &NullSignature, WASM_SYMBOL_VISIBILITY_HIDDEN);
+        "__wasm_call_ctors", WASM_SYMBOL_VISIBILITY_HIDDEN,
+        make<SyntheticFunction>(NullSignature, "__wasm_call_ctors"));
     WasmSym::StackPointer = Symtab->addSyntheticGlobal(
         "__stack_pointer", WASM_SYMBOL_VISIBILITY_HIDDEN, StackPointer);
     WasmSym::HeapBase = Symtab->addSyntheticDataSymbol("__heap_base", 0);
     WasmSym::DsoHandle = Symtab->addSyntheticDataSymbol(
         "__dso_handle", WASM_SYMBOL_VISIBILITY_HIDDEN);
     WasmSym::DataEnd = Symtab->addSyntheticDataSymbol("__data_end", 0);
 
     if (!Config->Entry.empty())

wasm/InputChunks.h

 namespace lld {
 namespace wasm {
 
 class ObjFile;
 class OutputSegment;
 
 class InputChunk {
 public:
-  enum Kind { DataSegment, Function };
+  enum Kind { DataSegment, Function, SyntheticFunction };
 
   Kind kind() const { return SectionKind; }
 
   uint32_t getSize() const { return data().size(); }
 
   void copyRelocations(const WasmSection &Section);
 
   void writeTo(uint8_t *SectionStart) const;

 // 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, ObjFile *F)
       : InputChunk(F, InputChunk::Function), Signature(S), Function(Func) {}
 
   static bool classof(const InputChunk *C) {
-    return C->kind() == InputChunk::Function;
+    return C->kind() == InputChunk::Function ||
+           C->kind() == InputChunk::SyntheticFunction;
   }
 
   StringRef getName() const override { return Function->Name; }
   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);
   uint32_t getTableIndex() const { return TableIndex.getValue(); }
protected:
 
   const WasmFunction *Function;
   llvm::Optional<uint32_t> OutputIndex;
   llvm::Optional<uint32_t> TableIndex;
 };
 
 class SyntheticFunction : public InputFunction {
 public:
-  SyntheticFunction(const WasmSignature &S, ArrayRef<uint8_t> Body,
-                    StringRef Name)
-      : InputFunction(S, nullptr, nullptr), Name(Name), Body(Body) {}
+  SyntheticFunction(const WasmSignature &S, StringRef Name)
+      : InputFunction(S, nullptr, nullptr), Name(Name) {
+    SectionKind = InputChunk::SyntheticFunction;
+  }
+
+  static bool classof(const InputChunk *C) {
+    return C->kind() == InputChunk::SyntheticFunction;
+  }
 
   StringRef getName() const override { return Name; }
   StringRef getComdat() const override { return StringRef(); }
 
+  void setBody(ArrayRef<uint8_t> Body_) { Body = Body_; }
+
 protected:
   ArrayRef<uint8_t> data() const override { return Body; }
 
   StringRef Name;
   ArrayRef<uint8_t> Body;
 };
 
 } // namespace wasm
 
 std::string toString(const wasm::InputChunk *);
 } // namespace lld
 
 #endif // LLD_WASM_INPUT_CHUNKS_H

wasm/SymbolTable.h

 // to replace the lazy symbol. The logic is implemented in the
 // add*() functions, which are called by input files as they are parsed.
 // There is one add* function per symbol type.
 class SymbolTable {
 public:
   void addFile(InputFile *File);
 
   std::vector<ObjFile *> ObjectFiles;
+  std::vector<InputFunction *> SyntheticFunctions;
+  std::vector<InputGlobal *> SyntheticGlobals;
 
   void reportRemainingUndefines();
 
   ArrayRef<Symbol *> getSymbols() const { return SymVector; }
   Symbol *find(StringRef Name);
 
   Symbol *addDefinedFunction(StringRef Name, uint32_t Flags, InputFile *File,
                              InputFunction *Function);
   Symbol *addDefinedData(StringRef Name, uint32_t Flags, InputFile *File,
                          InputSegment *Segment, uint32_t Address,
                          uint32_t Size);
   Symbol *addDefinedGlobal(StringRef Name, uint32_t Flags, InputFile *File,
                            InputGlobal *G);
 
   Symbol *addUndefinedFunction(StringRef Name, uint32_t Flags, InputFile *File,
                                const WasmSignature *Signature);
   Symbol *addUndefinedData(StringRef Name, uint32_t Flags, InputFile *File);
   Symbol *addUndefinedGlobal(StringRef Name, uint32_t Flags, InputFile *File,
                              const WasmGlobalType *Type);
 
   void addLazy(ArchiveFile *F, const Archive::Symbol *Sym);
 
   bool addComdat(StringRef Name, const ObjFile *File);
 
   DefinedData *addSyntheticDataSymbol(StringRef Name, uint32_t Flags);
   DefinedGlobal *addSyntheticGlobal(StringRef Name, uint32_t Flags,
                                     InputGlobal *Global);
-  DefinedFunction *addSyntheticFunction(StringRef Name,
-                                        const WasmSignature *Type,
-                                        uint32_t Flags);
+  DefinedFunction *addSyntheticFunction(StringRef Name, uint32_t Flags,
+                                        InputFunction *Function);
 
 private:
   std::pair<Symbol *, bool> insert(StringRef Name);
 
   llvm::DenseMap<llvm::CachedHashStringRef, Symbol *> SymMap;
   std::vector<Symbol *> SymVector;
 
   llvm::DenseMap<StringRef, const ObjFile *> Comdats;
 };
 
 extern SymbolTable *Symtab;
 
 } // namespace wasm
 } // namespace lld
 
 #endif

wasm/SymbolTable.cpp

 }
 
 static void checkDataType(const Symbol *Existing, const InputFile *File) {
   if (!isa<DataSymbol>(Existing))
     reportTypeError(Existing, File, "Data");
 }
 
 DefinedFunction *SymbolTable::addSyntheticFunction(StringRef Name,
-                                                   const WasmSignature *Type,
-                                                   uint32_t Flags) {
+                                                   uint32_t Flags,
+                                                   InputFunction *Function) {
   DEBUG(dbgs() << "addSyntheticFunction: " << Name << "\n");
   assert(!find(Name));
-  return replaceSymbol<DefinedFunction>(insert(Name).first, Name, Flags, Type);
+  SyntheticFunctions.emplace_back(Function);
+  return replaceSymbol<DefinedFunction>(insert(Name).first, Name, Flags,
+                                        nullptr, Function);
 }
 
 DefinedData *SymbolTable::addSyntheticDataSymbol(StringRef Name,
                                                  uint32_t Flags) {
   DEBUG(dbgs() << "addSyntheticDataSymbol: " << Name << "\n");
   assert(!find(Name));
   return replaceSymbol<DefinedData>(insert(Name).first, Name, Flags);
 }
 
 DefinedGlobal *SymbolTable::addSyntheticGlobal(StringRef Name, uint32_t Flags,
                                                InputGlobal *Global) {
   DEBUG(dbgs() << "addSyntheticGlobal: " << Name << " -> " << Global << "\n");
   assert(!find(Name));
+  SyntheticGlobals.emplace_back(Global);
   return replaceSymbol<DefinedGlobal>(insert(Name).first, Name, Flags, nullptr,
                                       Global);
 }
 
 static bool shouldReplace(const Symbol *Existing, InputFile *NewFile,
                           uint32_t NewFlags) {
   // If existing symbol is undefined, replace it.
   if (!Existing->isDefined()) {

wasm/Symbols.h

protected:
 
   uint32_t TableIndex = INVALID_INDEX;
 
   const WasmSignature *FunctionType;
 };
 
 class DefinedFunction : public FunctionSymbol {
 public:
-  // Primary constructor for file-defined functions.
   DefinedFunction(StringRef Name, uint32_t Flags, InputFile *F,
                   InputFunction *Function);
 
-  // Second constructor used when creating synthetic functions.
-  DefinedFunction(StringRef Name, uint32_t Flags, const WasmSignature *Type)
-      : FunctionSymbol(Name, DefinedFunctionKind, Flags, nullptr, Type) {}
-
   static bool classof(const Symbol *S) {
     return S->kind() == DefinedFunctionKind;
   }
 
   InputFunction *Function;
 };
 
 class UndefinedFunction : public FunctionSymbol {

wasm/Writer.cpp

if (auto *F = dyn_cast<FunctionSymbol>(Sym))
       registerType(*F->getFunctionType());
 
   for (const InputFunction *F : InputFunctions)
     registerType(F->Signature);
 }
 
 void Writer::assignIndexes() {
   uint32_t FunctionIndex = NumImportedFunctions + InputFunctions.size();
-  for (ObjFile *File : Symtab->ObjectFiles) {
-    DEBUG(dbgs() << "Functions: " << File->getName() << "\n");
-    for (InputFunction *Func : File->Functions) {
-      if (!Func->Live)
-        continue;
-      InputFunctions.emplace_back(Func);
-      Func->setOutputIndex(FunctionIndex++);
-    }
-  }
+  auto AddDefinedFunction = [&](InputFunction *Func) {
+      return;
+  };
+
+  for (ObjFile *File : Symtab->ObjectFiles) {
+    DEBUG(dbgs() << "Functions: " << File->getName() << "\n");
+    for (InputFunction *Func : File->Functions)
+      AddDefinedFunction(Func);
+
+  // TODO Move synthetic functions to come before (so __wasm_call_ctors can be
+  // compiled immediately by the browser).  Will reorder tests.
+  for (InputFunction *Func : Symtab->SyntheticFunctions)
+    AddDefinedFunction(Func);
 
   uint32_t TableIndex = kInitialTableOffset;
   auto HandleRelocs = [&](InputChunk *Chunk) {
     if (!Chunk->Live)
       return;
     ObjFile *File = Chunk->File;
     ArrayRef<WasmSignature> Types = File->getWasmObj()->types();
     for (const WasmRelocation &Reloc : Chunk->getRelocations()) {
void Writer::assignIndexes() {
   auto AddDefinedGlobal = [&](InputGlobal *Global) {
     if (Global->Live) {
       DEBUG(dbgs() << "AddDefinedGlobal: " << GlobalIndex << "\n");
       Global->setOutputIndex(GlobalIndex++);
       InputGlobals.push_back(Global);
     }
   };
 
-  if (WasmSym::StackPointer)
-    AddDefinedGlobal(WasmSym::StackPointer->Global);
+  for (InputGlobal *Global : Symtab->SyntheticGlobals)
+    AddDefinedGlobal(Global);
 
   for (ObjFile *File : Symtab->ObjectFiles) {
     DEBUG(dbgs() << "Globals: " << File->getName() << "\n");
     for (InputGlobal *Global : File->Globals)
       AddDefinedGlobal(Global);
   }
 }
 

 }
 
 static const int OPCODE_CALL = 0x10;
 static const int OPCODE_END = 0xb;
 
 // Create synthetic "__wasm_call_ctors" function based on ctor functions
 // in input object.
 void Writer::createCtorFunction() {
-  uint32_t FunctionIndex = NumImportedFunctions + InputFunctions.size();
-
   // First write the body's contents to a string.
   std::string BodyContent;
   {
     raw_string_ostream OS(BodyContent);
     writeUleb128(OS, 0, "num locals");
     for (const WasmInitEntry &F : InitFunctions) {
       writeU8(OS, OPCODE_CALL, "CALL");
       writeUleb128(OS, F.Sym->getOutputIndex(), "function index");
     }
     writeU8(OS, OPCODE_END, "END");
   }
 
   // Once we know the size of the body we can create the final function body
   std::string FunctionBody;
   {
     raw_string_ostream OS(FunctionBody);
     writeUleb128(OS, BodyContent.size(), "function size");
     OS << BodyContent;
   }
 
-  const WasmSignature *Sig = WasmSym::CallCtors->getFunctionType();
-  SyntheticFunction *F =
-      make<SyntheticFunction>(*Sig, toArrayRef(Saver.save(FunctionBody)),
-                              WasmSym::CallCtors->getName());
-
-  F->setOutputIndex(FunctionIndex);
-  F->Live = true;
-  WasmSym::CallCtors->Function = F;
-  InputFunctions.emplace_back(F);
+  ArrayRef<uint8_t> Body = toArrayRef(Saver.save(FunctionBody));
+  cast<SyntheticFunction>(WasmSym::CallCtors->Function)->setBody(Body);
 }
 
 // Populate InitFunctions vector with init functions from all input objects.
 // This is then used either when creating the output linking section or to
 // synthesize the "__wasm_call_ctors" function.
 void Writer::calculateInitFunctions() {
   for (ObjFile *File : Symtab->ObjectFiles) {
     const WasmLinkingData &L = File->getWasmObj()->linkingData();