First pass at LLD support for Emscripten (#1346)

* Skeleton of a beginning of o2wasm, WIP and probably not going to be used

* Get building post-cherry-pick

* ast->ir, remove commented out code, include a debug module print because linking

* Read linking section, print emscripten metadata json

* WasmBinaryWriter emits user sections on Module

* Remove debugging prints, everything that isn't needed to build metadata

* Rename o2wasm to lld-metadata

* lld-metadata support for outputting to file

* Use tables index instead of function index for initializer functions

* Add lld-emscripten tool to add emscripten-runtime functions to wasm modules (built with lld)

* Handle EM_ASM in lld-emscripten

* Add a list of functions to forcibly export (for initializer functions)

* Disable incorrect initializer function reading

* Add error printing when parsing .o files in lld-metadata

* Remove ';; METADATA: ' prefix from lld-metadata, output is now standalone json

* Support em_asm consts that aren't at the start of a segment

* Initial test framework for lld-metadata tool

* Add em_asm test

* Add support for WASM_INIT_FUNCS in the linking section

* Remove reloc section parsing because it's unused

* lld-emscripten can read and write text

* Add test harness for lld-emscripten

* Export all functions for now

* Add missing lld test output

* Add support for reading object files differently

Only difference so far is in importing mutable globals being an object
file representation for symbols, but invalid wasm.

* Update help strings

* Update linking tests for stackAlloc fix

* Rename lld-emscripten,lld-metadata to wasm-emscripten-finalize,wasm-link-metadata

* Add help text to header comments

* auto& instead of auto &

* Extract LinkType to abi/wasm-object.h

* Remove special handling for wasm object file reading, allow mutable globals

* Add braces around default switch case

* Fix flake8 errors

* Handle generating dyncall thunks for imports as well

* Use explicit bool for stackPointerGlobal

* Use glob patterns for lld file iteration

* Use __wasm_call_ctors for all initializer functions

20 files changed, 564 insertions, 0 deletions

diff --git a/test/lld/em_asm.cpp b/test/lld/em_asm.cpp
new file mode 100644
index 000000000..ed89783f8
--- /dev/null
+++ b/test/lld/em_asm.cpp
@@ -0,0 +1,8 @@
+#include <emscripten/em_asm.h>
+
+int main() {
+  EM_ASM({ Module.print("Hello world"); });
+  int x = EM_ASM_INT({ return $0 + $1; }, 13, 27);
+  EM_ASM_({ Module.print("Got " + $0); }, x);
+  return 0;
+}
diff --git a/test/lld/em_asm.json b/test/lld/em_asm.json
new file mode 100644
index 000000000..f5027845d
--- /dev/null
+++ b/test/lld/em_asm.json
@@ -0,0 +1 @@
+{ "asmConsts": {"2": ["{ Module.print(\"Got \" + $0); }", ["ii"]],"0": ["{ Module.print(\"Hello world\"); }", ["i"]],"1": ["{ return $0 + $1; }", ["iii"]]},"staticBump": 84, "initializers": ["__wasm_call_ctors"] }
diff --git a/test/lld/em_asm.o b/test/lld/em_asm.o
new file mode 100644
index 000000000..f95befdee
--- /dev/null
+++ b/test/lld/em_asm.o
diff --git a/test/lld/em_asm.wast b/test/lld/em_asm.wast
new file mode 100644
index 000000000..da1d8c3b6
--- /dev/null
+++ b/test/lld/em_asm.wast
@@ -0,0 +1,41 @@
+(module
+ (type $0 (func (result i32)))
+ (type $1 (func (param i32) (result i32)))
+ (type $2 (func (param i32 i32 i32) (result i32)))
+ (type $3 (func (param i32 i32) (result i32)))
+ (type $4 (func))
+ (import "env" "_Z24emscripten_asm_const_intIJEEiPKcDpT_" (func $_Z24emscripten_asm_const_intIJEEiPKcDpT_ (param i32) (result i32)))
+ (import "env" "_Z24emscripten_asm_const_intIJiiEEiPKcDpT_" (func $_Z24emscripten_asm_const_intIJiiEEiPKcDpT_ (param i32 i32 i32) (result i32)))
+ (import "env" "_Z24emscripten_asm_const_intIJiEEiPKcDpT_" (func $_Z24emscripten_asm_const_intIJiEEiPKcDpT_ (param i32 i32) (result i32)))
+ (global $global$0 (mut i32) (i32.const 66656))
+ (global $global$1 i32 (i32.const 66656))
+ (table 1 1 anyfunc)
+ (memory $0 2)
+ (data (i32.const 1024) "{ Module.print(\"Hello world\"); }\00{ return $0 + $1; }\00{ Module.print(\"Got \" + $0); }\00")
+ (export "memory" (memory $0))
+ (export "main" (func $main))
+ (export "__wasm_call_ctors" (func $__wasm_call_ctors))
+ (export "__heap_base" (global $global$1))
+ (func $main (; 3 ;) (type $0) (result i32)
+  (drop
+   (call $_Z24emscripten_asm_const_intIJEEiPKcDpT_
+    (i32.const 1024)
+   )
+  )
+  (drop
+   (call $_Z24emscripten_asm_const_intIJiEEiPKcDpT_
+    (i32.const 1077)
+    (call $_Z24emscripten_asm_const_intIJiiEEiPKcDpT_
+     (i32.const 1057)
+     (i32.const 13)
+     (i32.const 27)
+    )
+   )
+  )
+  (i32.const 0)
+ )
+ (func $__wasm_call_ctors (; 4 ;) (type $4)
+ )
+ ;; custom section "linking", size 3
+)
+
diff --git a/test/lld/em_asm.wast.out b/test/lld/em_asm.wast.out
new file mode 100644
index 000000000..921cd9782
--- /dev/null
+++ b/test/lld/em_asm.wast.out
@@ -0,0 +1,75 @@
+(module
+ (type $0 (func (result i32)))
+ (type $1 (func (param i32) (result i32)))
+ (type $2 (func (param i32 i32 i32) (result i32)))
+ (type $3 (func (param i32 i32) (result i32)))
+ (type $4 (func))
+ (type $FUNCSIG$ii (func (param i32) (result i32)))
+ (type $FUNCSIG$iiii (func (param i32 i32 i32) (result i32)))
+ (type $FUNCSIG$iii (func (param i32 i32) (result i32)))
+ (import "env" "emscripten_asm_const_i" (func $emscripten_asm_const_i (param i32) (result i32)))
+ (import "env" "emscripten_asm_const_iii" (func $emscripten_asm_const_iii (param i32 i32 i32) (result i32)))
+ (import "env" "emscripten_asm_const_ii" (func $emscripten_asm_const_ii (param i32 i32) (result i32)))
+ (global $global$0 (mut i32) (i32.const 66656))
+ (global $global$1 i32 (i32.const 66656))
+ (table 1 1 anyfunc)
+ (memory $0 2)
+ (data (i32.const 1024) "{ Module.print(\"Hello world\"); }\00{ return $0 + $1; }\00{ Module.print(\"Got \" + $0); }\00")
+ (export "memory" (memory $0))
+ (export "main" (func $main))
+ (export "__wasm_call_ctors" (func $__wasm_call_ctors))
+ (export "__heap_base" (global $global$1))
+ (export "stackSave" (func $stackSave))
+ (export "stackAlloc" (func $stackAlloc))
+ (export "stackRestore" (func $stackRestore))
+ (export "__growWasmMemory" (func $__growWasmMemory))
+ (func $main (; 3 ;) (type $0) (result i32)
+  (drop
+   (call $emscripten_asm_const_i
+    (i32.const 0)
+   )
+  )
+  (drop
+   (call $emscripten_asm_const_ii
+    (i32.const 2)
+    (call $emscripten_asm_const_iii
+     (i32.const 1)
+     (i32.const 13)
+     (i32.const 27)
+    )
+   )
+  )
+  (i32.const 0)
+ )
+ (func $__wasm_call_ctors (; 4 ;) (type $4)
+  (nop)
+ )
+ (func $stackSave (; 5 ;) (result i32)
+  (get_global $global$0)
+ )
+ (func $stackAlloc (; 6 ;) (param $0 i32) (result i32)
+  (local $1 i32)
+  (set_global $global$0
+   (tee_local $1
+    (i32.and
+     (i32.sub
+      (get_global $global$0)
+      (get_local $0)
+     )
+     (i32.const -16)
+    )
+   )
+  )
+  (get_local $1)
+ )
+ (func $stackRestore (; 7 ;) (param $0 i32)
+  (set_global $global$0
+   (get_local $0)
+  )
+ )
+ (func $__growWasmMemory (; 8 ;) (param $newSize i32) (result i32)
+  (grow_memory
+   (get_local $newSize)
+  )
+ )
+)
diff --git a/test/lld/hello_world.c b/test/lld/hello_world.c
new file mode 100644
index 000000000..babd8d43c
--- /dev/null
+++ b/test/lld/hello_world.c
@@ -0,0 +1,6 @@
+int puts(const char* str);
+
+int main() {
+  puts("Hello, world");
+  return 0;
+}
diff --git a/test/lld/hello_world.json b/test/lld/hello_world.json
new file mode 100644
index 000000000..c0a391b6e
--- /dev/null
+++ b/test/lld/hello_world.json
@@ -0,0 +1 @@
+{ "asmConsts": {},"staticBump": 13, "initializers": ["__wasm_call_ctors"] }
diff --git a/test/lld/hello_world.o b/test/lld/hello_world.o
new file mode 100644
index 000000000..a14f95993
--- /dev/null
+++ b/test/lld/hello_world.o
diff --git a/test/lld/hello_world.wast b/test/lld/hello_world.wast
new file mode 100644
index 000000000..d1610cece
--- /dev/null
+++ b/test/lld/hello_world.wast
@@ -0,0 +1,27 @@
+(module
+ (type $0 (func (result i32)))
+ (type $1 (func (param i32) (result i32)))
+ (type $2 (func))
+ (import "env" "puts" (func $puts (param i32) (result i32)))
+ (global $global$0 (mut i32) (i32.const 66576))
+ (global $global$1 i32 (i32.const 66576))
+ (table 1 1 anyfunc)
+ (memory $0 2)
+ (data (i32.const 1024) "Hello, world\00")
+ (export "memory" (memory $0))
+ (export "main" (func $main))
+ (export "__wasm_call_ctors" (func $__wasm_call_ctors))
+ (export "__heap_base" (global $global$1))
+ (func $main (; 1 ;) (type $0) (result i32)
+  (drop
+   (call $puts
+    (i32.const 1024)
+   )
+  )
+  (i32.const 0)
+ )
+ (func $__wasm_call_ctors (; 2 ;) (type $2)
+ )
+ ;; custom section "linking", size 3
+)
+
diff --git a/test/lld/hello_world.wast.out b/test/lld/hello_world.wast.out
new file mode 100644
index 000000000..ab861cc94
--- /dev/null
+++ b/test/lld/hello_world.wast.out
@@ -0,0 +1,59 @@
+(module
+ (type $0 (func (result i32)))
+ (type $1 (func (param i32) (result i32)))
+ (type $2 (func))
+ (type $FUNCSIG$ii (func (param i32) (result i32)))
+ (import "env" "puts" (func $puts (param i32) (result i32)))
+ (global $global$0 (mut i32) (i32.const 66576))
+ (global $global$1 i32 (i32.const 66576))
+ (table 1 1 anyfunc)
+ (memory $0 2)
+ (data (i32.const 1024) "Hello, world\00")
+ (export "memory" (memory $0))
+ (export "main" (func $main))
+ (export "__wasm_call_ctors" (func $__wasm_call_ctors))
+ (export "__heap_base" (global $global$1))
+ (export "stackSave" (func $stackSave))
+ (export "stackAlloc" (func $stackAlloc))
+ (export "stackRestore" (func $stackRestore))
+ (export "__growWasmMemory" (func $__growWasmMemory))
+ (func $main (; 1 ;) (type $0) (result i32)
+  (drop
+   (call $puts
+    (i32.const 1024)
+   )
+  )
+  (i32.const 0)
+ )
+ (func $__wasm_call_ctors (; 2 ;) (type $2)
+  (nop)
+ )
+ (func $stackSave (; 3 ;) (result i32)
+  (get_global $global$0)
+ )
+ (func $stackAlloc (; 4 ;) (param $0 i32) (result i32)
+  (local $1 i32)
+  (set_global $global$0
+   (tee_local $1
+    (i32.and
+     (i32.sub
+      (get_global $global$0)
+      (get_local $0)
+     )
+     (i32.const -16)
+    )
+   )
+  )
+  (get_local $1)
+ )
+ (func $stackRestore (; 5 ;) (param $0 i32)
+  (set_global $global$0
+   (get_local $0)
+  )
+ )
+ (func $__growWasmMemory (; 6 ;) (param $newSize i32) (result i32)
+  (grow_memory
+   (get_local $newSize)
+  )
+ )
+)
diff --git a/test/lld/init.c b/test/lld/init.c
new file mode 100644
index 000000000..3a9311e3c
--- /dev/null
+++ b/test/lld/init.c
@@ -0,0 +1,15 @@
+volatile int x, y;
+
+__attribute__((constructor))
+void init_x() {
+    x = 14;
+}
+
+__attribute__((constructor))
+void init_y() {
+    y = 144;
+}
+
+int main() {
+    return x + y;
+}
diff --git a/test/lld/init.json b/test/lld/init.json
new file mode 100644
index 000000000..f4d13ada1
--- /dev/null
+++ b/test/lld/init.json
@@ -0,0 +1 @@
+{ "asmConsts": {},"staticBump": 8, "initializers": ["__wasm_call_ctors"] }
diff --git a/test/lld/init.o b/test/lld/init.o
new file mode 100644
index 000000000..e86c68092
--- /dev/null
+++ b/test/lld/init.o
diff --git a/test/lld/init.wast b/test/lld/init.wast
new file mode 100644
index 000000000..be25ed464
--- /dev/null
+++ b/test/lld/init.wast
@@ -0,0 +1,41 @@
+(module
+ (type $0 (func))
+ (type $1 (func (result i32)))
+ (global $global$0 (mut i32) (i32.const 66576))
+ (global $global$1 i32 (i32.const 66576))
+ (table 1 1 anyfunc)
+ (memory $0 2)
+ (data (i32.const 1024) "\00\00\00\00\00\00\00\00")
+ (export "memory" (memory $0))
+ (export "main" (func $main))
+ (export "__wasm_call_ctors" (func $__wasm_call_ctors))
+ (export "__heap_base" (global $global$1))
+ (func $init_x (; 0 ;) (type $0)
+  (i32.store offset=1024
+   (i32.const 0)
+   (i32.const 14)
+  )
+ )
+ (func $init_y (; 1 ;) (type $0)
+  (i32.store offset=1028
+   (i32.const 0)
+   (i32.const 144)
+  )
+ )
+ (func $main (; 2 ;) (type $1) (result i32)
+  (i32.add
+   (i32.load offset=1024
+    (i32.const 0)
+   )
+   (i32.load offset=1028
+    (i32.const 0)
+   )
+  )
+ )
+ (func $__wasm_call_ctors (; 3 ;) (type $0)
+  (call $init_x)
+  (call $init_y)
+ )
+ ;; custom section "linking", size 3
+)
+
diff --git a/test/lld/init.wast.out b/test/lld/init.wast.out
new file mode 100644
index 000000000..3b46d26d4
--- /dev/null
+++ b/test/lld/init.wast.out
@@ -0,0 +1,71 @@
+(module
+ (type $0 (func))
+ (type $1 (func (result i32)))
+ (global $global$0 (mut i32) (i32.const 66576))
+ (global $global$1 i32 (i32.const 66576))
+ (table 1 1 anyfunc)
+ (memory $0 2)
+ (data (i32.const 1024) "\00\00\00\00\00\00\00\00")
+ (export "memory" (memory $0))
+ (export "main" (func $main))
+ (export "__wasm_call_ctors" (func $__wasm_call_ctors))
+ (export "__heap_base" (global $global$1))
+ (export "stackSave" (func $stackSave))
+ (export "stackAlloc" (func $stackAlloc))
+ (export "stackRestore" (func $stackRestore))
+ (export "__growWasmMemory" (func $__growWasmMemory))
+ (func $init_x (; 0 ;) (type $0)
+  (i32.store offset=1024
+   (i32.const 0)
+   (i32.const 14)
+  )
+ )
+ (func $init_y (; 1 ;) (type $0)
+  (i32.store offset=1028
+   (i32.const 0)
+   (i32.const 144)
+  )
+ )
+ (func $main (; 2 ;) (type $1) (result i32)
+  (i32.add
+   (i32.load offset=1024
+    (i32.const 0)
+   )
+   (i32.load offset=1028
+    (i32.const 0)
+   )
+  )
+ )
+ (func $__wasm_call_ctors (; 3 ;) (type $0)
+  (call $init_x)
+  (call $init_y)
+ )
+ (func $stackSave (; 4 ;) (result i32)
+  (get_global $global$0)
+ )
+ (func $stackAlloc (; 5 ;) (param $0 i32) (result i32)
+  (local $1 i32)
+  (set_global $global$0
+   (tee_local $1
+    (i32.and
+     (i32.sub
+      (get_global $global$0)
+      (get_local $0)
+     )
+     (i32.const -16)
+    )
+   )
+  )
+  (get_local $1)
+ )
+ (func $stackRestore (; 6 ;) (param $0 i32)
+  (set_global $global$0
+   (get_local $0)
+  )
+ )
+ (func $__growWasmMemory (; 7 ;) (param $newSize i32) (result i32)
+  (grow_memory
+   (get_local $newSize)
+  )
+ )
+)
diff --git a/test/lld/recursive.c b/test/lld/recursive.c
new file mode 100644
index 000000000..c0cdaa425
--- /dev/null
+++ b/test/lld/recursive.c
@@ -0,0 +1,15 @@
+// This test emits a stack pointer, which tests global importing in object files
+// (which are mutable and not normally allowed).
+
+int printf(const char* fmt, ...);
+
+__attribute__((noinline))
+int foo(int a, int b) {
+    printf("%d:%d\n", a, b);
+    return a + b;
+}
+
+int main() {
+  printf("Result: %d\n", foo(1, 2));
+  return 0;
+}
diff --git a/test/lld/recursive.json b/test/lld/recursive.json
new file mode 100644
index 000000000..a976be232
--- /dev/null
+++ b/test/lld/recursive.json
@@ -0,0 +1 @@
+{ "asmConsts": {},"staticBump": 19, "initializers": ["__wasm_call_ctors"] }
diff --git a/test/lld/recursive.o b/test/lld/recursive.o
new file mode 100644
index 000000000..409257fd4
--- /dev/null
+++ b/test/lld/recursive.o
diff --git a/test/lld/recursive.wast b/test/lld/recursive.wast
new file mode 100644
index 000000000..21b46a31f
--- /dev/null
+++ b/test/lld/recursive.wast
@@ -0,0 +1,85 @@
+(module
+ (type $0 (func (param i32 i32) (result i32)))
+ (type $1 (func (result i32)))
+ (type $2 (func))
+ (import "env" "printf" (func $printf (param i32 i32) (result i32)))
+ (global $global$0 (mut i32) (i32.const 66592))
+ (global $global$1 i32 (i32.const 66592))
+ (table 1 1 anyfunc)
+ (memory $0 2)
+ (data (i32.const 1024) "%d:%d\n\00Result: %d\n\00")
+ (export "memory" (memory $0))
+ (export "main" (func $main))
+ (export "__wasm_call_ctors" (func $__wasm_call_ctors))
+ (export "__heap_base" (global $global$1))
+ (func $foo (; 1 ;) (type $0) (param $var$0 i32) (param $var$1 i32) (result i32)
+  (local $var$2 i32)
+  (set_global $global$0
+   (tee_local $var$2
+    (i32.sub
+     (get_global $global$0)
+     (i32.const 16)
+    )
+   )
+  )
+  (i32.store offset=4
+   (get_local $var$2)
+   (get_local $var$1)
+  )
+  (i32.store
+   (get_local $var$2)
+   (get_local $var$0)
+  )
+  (drop
+   (call $printf
+    (i32.const 1024)
+    (get_local $var$2)
+   )
+  )
+  (set_global $global$0
+   (i32.add
+    (get_local $var$2)
+    (i32.const 16)
+   )
+  )
+  (i32.add
+   (get_local $var$1)
+   (get_local $var$0)
+  )
+ )
+ (func $main (; 2 ;) (type $1) (result i32)
+  (local $var$0 i32)
+  (set_global $global$0
+   (tee_local $var$0
+    (i32.sub
+     (get_global $global$0)
+     (i32.const 16)
+    )
+   )
+  )
+  (i32.store
+   (get_local $var$0)
+   (call $foo
+    (i32.const 1)
+    (i32.const 2)
+   )
+  )
+  (drop
+   (call $printf
+    (i32.const 1031)
+    (get_local $var$0)
+   )
+  )
+  (set_global $global$0
+   (i32.add
+    (get_local $var$0)
+    (i32.const 16)
+   )
+  )
+  (i32.const 0)
+ )
+ (func $__wasm_call_ctors (; 3 ;) (type $2)
+ )
+ ;; custom section "linking", size 3
+)
+
diff --git a/test/lld/recursive.wast.out b/test/lld/recursive.wast.out
new file mode 100644
index 000000000..4920a7622
--- /dev/null
+++ b/test/lld/recursive.wast.out
@@ -0,0 +1,117 @@
+(module
+ (type $0 (func (param i32 i32) (result i32)))
+ (type $1 (func (result i32)))
+ (type $2 (func))
+ (type $FUNCSIG$iii (func (param i32 i32) (result i32)))
+ (import "env" "printf" (func $printf (param i32 i32) (result i32)))
+ (global $global$0 (mut i32) (i32.const 66592))
+ (global $global$1 i32 (i32.const 66592))
+ (table 1 1 anyfunc)
+ (memory $0 2)
+ (data (i32.const 1024) "%d:%d\n\00Result: %d\n\00")
+ (export "memory" (memory $0))
+ (export "main" (func $main))
+ (export "__wasm_call_ctors" (func $__wasm_call_ctors))
+ (export "__heap_base" (global $global$1))
+ (export "stackSave" (func $stackSave))
+ (export "stackAlloc" (func $stackAlloc))
+ (export "stackRestore" (func $stackRestore))
+ (export "__growWasmMemory" (func $__growWasmMemory))
+ (func $foo (; 1 ;) (type $0) (param $var$0 i32) (param $var$1 i32) (result i32)
+  (local $var$2 i32)
+  (set_global $global$0
+   (tee_local $var$2
+    (i32.sub
+     (get_global $global$0)
+     (i32.const 16)
+    )
+   )
+  )
+  (i32.store offset=4
+   (get_local $var$2)
+   (get_local $var$1)
+  )
+  (i32.store
+   (get_local $var$2)
+   (get_local $var$0)
+  )
+  (drop
+   (call $printf
+    (i32.const 1024)
+    (get_local $var$2)
+   )
+  )
+  (set_global $global$0
+   (i32.add
+    (get_local $var$2)
+    (i32.const 16)
+   )
+  )
+  (i32.add
+   (get_local $var$1)
+   (get_local $var$0)
+  )
+ )
+ (func $main (; 2 ;) (type $1) (result i32)
+  (local $var$0 i32)
+  (set_global $global$0
+   (tee_local $var$0
+    (i32.sub
+     (get_global $global$0)
+     (i32.const 16)
+    )
+   )
+  )
+  (i32.store
+   (get_local $var$0)
+   (call $foo
+    (i32.const 1)
+    (i32.const 2)
+   )
+  )
+  (drop
+   (call $printf
+    (i32.const 1031)
+    (get_local $var$0)
+   )
+  )
+  (set_global $global$0
+   (i32.add
+    (get_local $var$0)
+    (i32.const 16)
+   )
+  )
+  (i32.const 0)
+ )
+ (func $__wasm_call_ctors (; 3 ;) (type $2)
+  (nop)
+ )
+ (func $stackSave (; 4 ;) (result i32)
+  (get_global $global$0)
+ )
+ (func $stackAlloc (; 5 ;) (param $0 i32) (result i32)
+  (local $1 i32)
+  (set_global $global$0
+   (tee_local $1
+    (i32.and
+     (i32.sub
+      (get_global $global$0)
+      (get_local $0)
+     )
+     (i32.const -16)
+    )
+   )
+  )
+  (get_local $1)
+ )
+ (func $stackRestore (; 6 ;) (param $0 i32)
+  (set_global $global$0
+   (get_local $0)
+  )
+ )
+ (func $__growWasmMemory (; 7 ;) (param $newSize i32) (result i32)
+  (grow_memory
+   (get_local $newSize)
+  )
+ )
+)