Reintroduce wasm-merge (#5709)

We used to have a wasm-merge tool but removed it for a lack of use cases. Recently
use cases have been showing up in the wasm GC space and elsewhere, as people are
using more diverse toolchains together, for example a project might build some C++
code alongside some wasm GC code. Merging those wasm files together can allow
for nice optimizations like inlining and better DCE etc., so it makes sense to have a
tool for merging.

Background:
* Removal: #1969
* Requests:
  * wasm-merge - why it has been deleted #2174
  * Compiling and linking wat files #2276
  * wasm-link? #2767

This PR is a compete rewrite of wasm-merge, not a restoration of the original
codebase. The original code was quite messy (my fault), and also, since then
we've added multi-memory and multi-table which makes things a lot simpler.

The linking semantics are as described in the "wasm-link" issue #2767 : all we do
is merge normal wasm files together and connect imports and export. That is, we
have a graph of modules and their names, and each import to a module name can
be resolved to that module. Basically, like a JS bundler would do for JS, or, in other
words, we do the same operations as JS code would do to glue wasm modules
together at runtime, but at compile time. See the README update in this PR for a
concrete example.

There are no plans to do more than that simple bundling, so this should not
really overlap with wasm-ld's use cases.

This should be fairly fast as it works in linear time on the total input code. However,
it won't be as fast as wasm-ld, of course, as it does build Binaryen IR for each
module. An advantage to working on Binaryen IR is that we can easily do some
global DCE after merging, and further optimizations are possible later.

22 files changed, 1173 insertions, 0 deletions

diff --git a/test/lit/merge/cycle.wat b/test/lit/merge/cycle.wat
new file mode 100644
index 000000000..9862b3355
--- /dev/null
+++ b/test/lit/merge/cycle.wat
@@ -0,0 +1,84 @@
+;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited.
+;; RUN: wasm-merge %s first %s.second second %s.third third --rename-export-conflicts -all -S -o - | filecheck %s
+
+;; Test a cycle of imports: the first module imports from the second, which
+;; imports from the third, and we have a reverse cycle as well.
+
+(module
+  (import "second" "forward" (func $second.forward))
+
+  (import "second" "reverse" (func $second.reverse))
+
+  (import "third" "forward" (func $third.forward))
+
+  (import "third" "reverse" (func $third.reverse))
+
+
+
+  ;; CHECK:      (type $none_=>_none (func))
+
+  ;; CHECK:      (export "forward" (func $forward))
+
+  ;; CHECK:      (export "reverse" (func $reverse))
+
+  ;; CHECK:      (export "forward_2" (func $forward_6))
+
+  ;; CHECK:      (export "reverse_3" (func $reverse_6))
+
+  ;; CHECK:      (export "forward_4" (func $forward_12))
+
+  ;; CHECK:      (export "reverse_5" (func $reverse_12))
+
+  ;; CHECK:      (func $forward (type $none_=>_none)
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (i32.const 1)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (call $forward_6)
+  ;; CHECK-NEXT: )
+  (func $forward (export "forward")
+    (drop
+      (i32.const 1)
+    )
+    (call $second.forward)
+  )
+
+  ;; CHECK:      (func $reverse (type $none_=>_none)
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (i32.const -1)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (call $reverse_12)
+  ;; CHECK-NEXT: )
+  (func $reverse (export "reverse")
+    (drop
+      (i32.const -1)
+    )
+    (call $third.reverse)
+  )
+)
+;; CHECK:      (func $forward_6 (type $none_=>_none)
+;; CHECK-NEXT:  (drop
+;; CHECK-NEXT:   (i32.const 2)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT:  (call $forward_12)
+;; CHECK-NEXT: )
+
+;; CHECK:      (func $reverse_6 (type $none_=>_none)
+;; CHECK-NEXT:  (drop
+;; CHECK-NEXT:   (i32.const -2)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT:  (call $reverse)
+;; CHECK-NEXT: )
+
+;; CHECK:      (func $forward_12 (type $none_=>_none)
+;; CHECK-NEXT:  (drop
+;; CHECK-NEXT:   (i32.const 3)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT:  (call $forward)
+;; CHECK-NEXT: )
+
+;; CHECK:      (func $reverse_12 (type $none_=>_none)
+;; CHECK-NEXT:  (drop
+;; CHECK-NEXT:   (i32.const -3)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT:  (call $reverse_6)
+;; CHECK-NEXT: )
diff --git a/test/lit/merge/cycle.wat.second b/test/lit/merge/cycle.wat.second
new file mode 100644
index 000000000..b110043b4
--- /dev/null
+++ b/test/lit/merge/cycle.wat.second
@@ -0,0 +1,24 @@
+(module
+  (import "first" "forward" (func $first.forward))
+
+  (import "first" "reverse" (func $first.reverse))
+
+  (import "third" "forward" (func $third.forward))
+
+  (import "third" "reverse" (func $third.reverse))
+
+  (func $forward (export "forward")
+    (drop
+      (i32.const 2)
+    )
+    (call $third.forward)
+  )
+
+  (func $reverse (export "reverse")
+    (drop
+      (i32.const -2)
+    )
+    (call $first.reverse)
+  )
+)
+
diff --git a/test/lit/merge/cycle.wat.third b/test/lit/merge/cycle.wat.third
new file mode 100644
index 000000000..03cc08f04
--- /dev/null
+++ b/test/lit/merge/cycle.wat.third
@@ -0,0 +1,24 @@
+(module
+  (import "first" "forward" (func $first.forward))
+
+  (import "first" "reverse" (func $first.reverse))
+
+  (import "second" "forward" (func $second.forward))
+
+  (import "second" "reverse" (func $second.reverse))
+
+  (func $forward (export "forward")
+    (drop
+      (i32.const 3)
+    )
+    (call $first.forward)
+  )
+
+  (func $reverse (export "reverse")
+    (drop
+      (i32.const -3)
+    )
+    (call $second.reverse)
+  )
+)
+
diff --git a/test/lit/merge/export_options.wat b/test/lit/merge/export_options.wat
new file mode 100644
index 000000000..26bc9d382
--- /dev/null
+++ b/test/lit/merge/export_options.wat
@@ -0,0 +1,59 @@
+;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited.
+
+;; If asked to, we rename the conflicts. The second "func" export will become
+;; "func_1".
+;; RUN: wasm-merge %s first %s.second second --rename-export-conflicts -S -o - | filecheck %s --check-prefix RENAME
+
+;; If asked to, we can skip conflicting exports from later modules. The second
+;; "func" export will not exist.
+;; RUN: wasm-merge %s first %s.second second --skip-export-conflicts -S -o - | filecheck %s --check-prefix SKIP_C
+
+(module
+  ;; RENAME:      (type $none_=>_none (func))
+
+  ;; RENAME:      (export "func" (func $func0))
+
+  ;; RENAME:      (export "func_1" (func $func1))
+
+  ;; RENAME:      (export "other" (func $func2))
+
+  ;; RENAME:      (func $func0
+  ;; RENAME-NEXT:  (drop
+  ;; RENAME-NEXT:   (i32.const 0)
+  ;; RENAME-NEXT:  )
+  ;; RENAME-NEXT: )
+  ;; SKIP_C:      (type $none_=>_none (func))
+
+  ;; SKIP_C:      (export "func" (func $func0))
+
+  ;; SKIP_C:      (export "other" (func $func2))
+
+  ;; SKIP_C:      (func $func0
+  ;; SKIP_C-NEXT:  (drop
+  ;; SKIP_C-NEXT:   (i32.const 0)
+  ;; SKIP_C-NEXT:  )
+  ;; SKIP_C-NEXT: )
+  (func $func0 (export "func")
+    ;; This export also appears in the second module.
+    (drop
+      (i32.const 0)
+    )
+  )
+)
+;; RENAME:      (func $func1
+;; RENAME-NEXT:  (drop
+;; RENAME-NEXT:   (i32.const 1)
+;; RENAME-NEXT:  )
+;; RENAME-NEXT: )
+
+;; RENAME:      (func $func2
+;; RENAME-NEXT:  (drop
+;; RENAME-NEXT:   (i32.const 2)
+;; RENAME-NEXT:  )
+;; RENAME-NEXT: )
+
+;; SKIP_C:      (func $func2
+;; SKIP_C-NEXT:  (drop
+;; SKIP_C-NEXT:   (i32.const 2)
+;; SKIP_C-NEXT:  )
+;; SKIP_C-NEXT: )
diff --git a/test/lit/merge/export_options.wat.second b/test/lit/merge/export_options.wat.second
new file mode 100644
index 000000000..adcc24bd2
--- /dev/null
+++ b/test/lit/merge/export_options.wat.second
@@ -0,0 +1,15 @@
+(module
+  (func $func1 (export "func")
+    ;; This export will conflict.
+    (drop
+      (i32.const 1)
+    )
+  )
+
+  (func $func2 (export "other")
+    ;; This export will not conflict.
+    (drop
+      (i32.const 2)
+    )
+  )
+)
diff --git a/test/lit/merge/export_options_default.wat b/test/lit/merge/export_options_default.wat
new file mode 100644
index 000000000..bb1dea30e
--- /dev/null
+++ b/test/lit/merge/export_options_default.wat
@@ -0,0 +1,15 @@
+;; By default we error on an export name conflict.
+;; (This is the same as export_options.wat, but a "not" test and a test with
+;; automatic updates cannot be in the same file.)
+
+;; RUN: not wasm-merge %s first %s.second second 2>&1 | filecheck %s
+;; CHECK: Fatal: Export name conflict: func (consider --rename-export-conflicts or --skip-export-conflicts)
+
+(module
+  (func $func0 (export "func")
+    ;; This export also appears in the second module.
+    (drop
+      (i32.const 0)
+    )
+  )
+)
diff --git a/test/lit/merge/export_options_default.wat.second b/test/lit/merge/export_options_default.wat.second
new file mode 100644
index 000000000..6e045c7dd
--- /dev/null
+++ b/test/lit/merge/export_options_default.wat.second
@@ -0,0 +1,7 @@
+(module
+  (func $func1 (export "func")
+    (drop
+      (i32.const 1)
+    )
+  )
+)
diff --git a/test/lit/merge/fusing.wat b/test/lit/merge/fusing.wat
new file mode 100644
index 000000000..645634b4d
--- /dev/null
+++ b/test/lit/merge/fusing.wat
@@ -0,0 +1,94 @@
+;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited.
+
+;; RUN: wasm-merge %s first %s.second second --rename-export-conflicts -all -S -o - | filecheck %s
+
+;; Test that we fuse imports to exports across modules.
+;;
+;; We test functions and memories here, and not every possible entity in a
+;; comprehensive way, since they all go through the same code path. (But we test
+;; two to at least verify we differentiate them.)
+
+(module
+  ;; The first two imports here will be resolved to direct calls into the
+  ;; second module's merged contents.
+  (import "second" "foo" (func $other.foo))
+
+  (import "second" "bar" (func $other.bar))
+
+  (import "second" "mem" (memory $other.mem 1))
+
+  ;; This import will remain unresolved.
+  ;; CHECK:      (type $none_=>_none (func))
+
+  ;; CHECK:      (type $none_=>_i32 (func (result i32)))
+
+  ;; CHECK:      (import "third" "missing" (func $other.missing))
+  (import "third" "missing" (func $other.missing))
+
+  ;; CHECK:      (memory $second.mem 2)
+
+  ;; CHECK:      (export "foo" (func $first.foo))
+
+  ;; CHECK:      (export "bar" (func $bar))
+
+  ;; CHECK:      (export "keepalive" (func $keepalive))
+
+  ;; CHECK:      (export "mem" (memory $second.mem))
+
+  ;; CHECK:      (export "foo_4" (func $second.foo))
+
+  ;; CHECK:      (export "bar_5" (func $bar_6))
+
+  ;; CHECK:      (func $first.foo (type $none_=>_none)
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (i32.const 1)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (call $second.foo)
+  ;; CHECK-NEXT: )
+  (func $first.foo (export "foo")
+    (drop
+      (i32.const 1)
+    )
+    (call $other.foo)
+  )
+
+  ;; CHECK:      (func $bar (type $none_=>_none)
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (i32.const 2)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (call $bar_6)
+  ;; CHECK-NEXT:  (call $other.missing)
+  ;; CHECK-NEXT: )
+  (func $bar (export "bar")
+    (drop
+      (i32.const 2)
+    )
+    (call $other.bar)
+    (call $other.missing)
+  )
+
+  ;; CHECK:      (func $keepalive (type $none_=>_i32) (result i32)
+  ;; CHECK-NEXT:  (i32.load
+  ;; CHECK-NEXT:   (i32.const 10)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $keepalive (export "keepalive") (result i32)
+    ;; Load from the memory imported from the second module.
+    (i32.load $other.mem
+      (i32.const 10)
+    )
+  )
+)
+;; CHECK:      (func $second.foo (type $none_=>_none)
+;; CHECK-NEXT:  (call $first.foo)
+;; CHECK-NEXT:  (drop
+;; CHECK-NEXT:   (i32.const 3)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT: )
+
+;; CHECK:      (func $bar_6 (type $none_=>_none)
+;; CHECK-NEXT:  (call $bar)
+;; CHECK-NEXT:  (drop
+;; CHECK-NEXT:   (i32.const 4)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT: )
diff --git a/test/lit/merge/fusing.wat.second b/test/lit/merge/fusing.wat.second
new file mode 100644
index 000000000..387e57bb4
--- /dev/null
+++ b/test/lit/merge/fusing.wat.second
@@ -0,0 +1,28 @@
+(module
+  ;; Use the same internal name as in first, so $other.foo will need to be
+  ;; deduplicated.
+  (import "first" "foo" (func $other.foo))
+
+  ;; Use a different prefix than in first ($main instead of $other).
+  (import "first" "bar" (func $main.bar))
+
+  (memory $second.mem 2)
+
+  (export "mem" (memory $second.mem))
+
+  (func $second.foo (export "foo")
+    (call $other.foo)
+    (drop
+      (i32.const 3)
+    )
+  )
+
+  ;; Use the same internal name as in first, so this will need to be
+  ;; deduplicated.
+  (func $bar (export "bar")
+    (call $main.bar)
+    (drop
+      (i32.const 4)
+    )
+  )
+)
diff --git a/test/lit/merge/memory_data.wat b/test/lit/merge/memory_data.wat
new file mode 100644
index 000000000..d796dc322
--- /dev/null
+++ b/test/lit/merge/memory_data.wat
@@ -0,0 +1,39 @@
+;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited.
+
+;; RUN: wasm-merge %s first %s.second second --rename-export-conflicts -all -S -o - | filecheck %s
+
+;; Test we rename memories and data segments properly at the module scope.
+;; Memory $bar has a name collision, and both of the element segments' names.
+;; This test verifies that data segments refer to the right tables even after
+;; such name changes.
+
+(module
+  ;; CHECK:      (memory $foo 1)
+  (memory $foo 1)
+
+  ;; CHECK:      (memory $bar 10)
+  (memory $bar 10)
+
+  ;; CHECK:      (memory $other 100)
+
+  ;; CHECK:      (memory $bar_2 1000)
+
+  ;; CHECK:      (data $a (i32.const 0) "a")
+  (data $a (memory $foo) (i32.const 0) "a")
+
+  ;; CHECK:      (data $b (memory $bar) (i32.const 0) "b")
+  (data $b (memory $bar) (i32.const 0) "b")
+
+  ;; CHECK:      (data $a_2 (memory $other) (i32.const 0) "a2")
+
+  ;; CHECK:      (data $b_2 (memory $bar_2) (i32.const 0) "b2")
+
+  ;; CHECK:      (export "keepalive" (memory $foo))
+  (export "keepalive" (memory $foo))
+
+  ;; CHECK:      (export "keepalive1" (memory $bar))
+  (export "keepalive1" (memory $bar))
+)
+;; CHECK:      (export "keepalive_2" (memory $other))
+
+;; CHECK:      (export "keepalive1_3" (memory $bar_2))
diff --git a/test/lit/merge/memory_data.wat.second b/test/lit/merge/memory_data.wat.second
new file mode 100644
index 000000000..0ea34dbcd
--- /dev/null
+++ b/test/lit/merge/memory_data.wat.second
@@ -0,0 +1,13 @@
+(module
+  (memory $other 100)
+
+  (memory $bar 1000)
+
+  (data $a (memory $other) (i32.const 0) "a2")
+
+  (data $b (memory $bar) (i32.const 0) "b2")
+
+  (export "keepalive" (memory $other))
+
+  (export "keepalive1" (memory $bar))
+)
diff --git a/test/lit/merge/renamings.wat b/test/lit/merge/renamings.wat
new file mode 100644
index 000000000..fd01803f2
--- /dev/null
+++ b/test/lit/merge/renamings.wat
@@ -0,0 +1,350 @@
+;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited.
+;; RUN: wasm-merge %s first %s.second second --rename-export-conflicts -all -S -o - | filecheck %s
+
+;; Test that we rename items in the second module to avoid name collisions.
+
+(module
+  ;; CHECK:      (type $array (array (mut funcref)))
+  (type $array (array (mut (ref null func))))
+
+  ;; This tag has a conflict in second.wat, and so second.wat's $foo
+  ;; will be renamed.
+  ;; CHECK:      (type $none_=>_none (func))
+
+  ;; CHECK:      (type $ref|$array|_=>_none (func (param (ref $array))))
+
+  ;; CHECK:      (type $i32_=>_none (func (param i32)))
+
+  ;; CHECK:      (type $i64_=>_none (func (param i64)))
+
+  ;; CHECK:      (type $f32_=>_none (func (param f32)))
+
+  ;; CHECK:      (type $f64_=>_none (func (param f64)))
+
+  ;; CHECK:      (global $foo i32 (i32.const 1))
+  (global $foo i32 (i32.const 1))
+
+  ;; This global has a conflict in second.wat, and so second.wat's $bar
+  ;; will be renamed.
+  ;; CHECK:      (global $bar i32 (i32.const 2))
+  (global $bar i32 (i32.const 2))
+
+  ;; This memory has a conflict in second.wat, and so second.wat's $foo
+  ;; will be renamed.
+  ;; CHECK:      (global $other i32 (i32.const 3))
+
+  ;; CHECK:      (global $bar_2 i32 (i32.const 4))
+
+  ;; CHECK:      (memory $foo 10 20)
+  (memory $foo 10 20)
+
+  ;; CHECK:      (memory $bar 30 40)
+  (memory $bar 30 40)
+
+  ;; CHECK:      (memory $foo_2 50 60)
+
+  ;; CHECK:      (memory $other 70 80)
+
+  ;; CHECK:      (data $foo (i32.const 1) "abc")
+  (data $foo (i32.const 1) "abc")
+
+  ;; This data segment has a conflict in second.wat, and so second.wat's $bar
+  ;; will be renamed.
+  ;; CHECK:      (data $bar (i32.const 2) "def")
+  (data $bar (i32.const 2) "def")
+
+  ;; This table has a conflict in second.wat, and so second.wat's $foo
+  ;; will be renamed.
+  ;; CHECK:      (data $other (memory $foo_2) (i32.const 3) "ghi")
+
+  ;; CHECK:      (data $bar_2 (memory $foo_2) (i32.const 4) "jkl")
+
+  ;; CHECK:      (table $foo 10 20 funcref)
+  (table $foo 10 20 funcref)
+
+  ;; CHECK:      (table $bar 30 40 funcref)
+  (table $bar 30 40 funcref)
+
+  ;; CHECK:      (table $foo_2 50 60 funcref)
+
+  ;; CHECK:      (table $other 70 80 funcref)
+
+  ;; CHECK:      (elem $foo func $foo $bar)
+  (elem $foo (ref null func) $foo $bar)
+
+  ;; This elem has a conflict in second.wat, and so second.wat's $bar
+  ;; will be renamed.
+  ;; CHECK:      (elem $bar func $bar $foo)
+  (elem $bar (ref null func) $bar $foo)
+
+  ;; CHECK:      (elem $other func $foo_3 $other)
+
+  ;; CHECK:      (elem $bar_2 func $other $foo_3)
+
+  ;; CHECK:      (tag $foo (param i32))
+  (tag $foo (param i32))
+
+  ;; CHECK:      (tag $bar (param i64))
+  (tag $bar (param i64))
+
+  ;; This export has a conflict in second.wat, and so second.wat's $foo
+  ;; will be renamed.
+  ;; CHECK:      (tag $foo_2 (param f32))
+
+  ;; CHECK:      (tag $other (param f64))
+
+  ;; CHECK:      (export "foo" (func $foo))
+  (export "foo" (func $foo))
+
+  ;; CHECK:      (export "bar" (func $bar))
+  (export "bar" (func $bar))
+
+  ;; CHECK:      (export "keepalive" (func $uses))
+  (export "keepalive" (func $uses))
+
+  ;; CHECK:      (export "foo_3" (func $foo_3))
+
+  ;; CHECK:      (export "other" (func $other))
+
+  ;; CHECK:      (export "keepalive_5" (func $uses.second))
+
+  ;; CHECK:      (export "other-b" (func $other))
+
+  ;; CHECK:      (func $foo (type $none_=>_none)
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (i32.const 1)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $foo
+    ;; This function has a conflict in second.wat, and so second.wat's $foo
+    ;; will be renamed.
+    (drop
+      (i32.const 1)
+    )
+  )
+
+  ;; CHECK:      (func $bar (type $none_=>_none)
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (i32.const 2)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $bar
+    (drop
+      (i32.const 2)
+    )
+  )
+
+  ;; CHECK:      (func $uses (type $ref|$array|_=>_none) (param $array (ref $array))
+  ;; CHECK-NEXT:  (try $try
+  ;; CHECK-NEXT:   (do
+  ;; CHECK-NEXT:    (nop)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:   (catch $foo
+  ;; CHECK-NEXT:    (drop
+  ;; CHECK-NEXT:     (pop i32)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (try $try0
+  ;; CHECK-NEXT:   (do
+  ;; CHECK-NEXT:    (nop)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:   (catch $bar
+  ;; CHECK-NEXT:    (drop
+  ;; CHECK-NEXT:     (pop i64)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (i32.load $foo
+  ;; CHECK-NEXT:    (i32.const 1)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (i32.load $bar
+  ;; CHECK-NEXT:    (i32.const 2)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (data.drop $foo)
+  ;; CHECK-NEXT:  (data.drop $bar)
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (table.get $foo
+  ;; CHECK-NEXT:    (i32.const 1)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (table.get $bar
+  ;; CHECK-NEXT:    (i32.const 2)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (array.init_elem $array $foo
+  ;; CHECK-NEXT:   (local.get $array)
+  ;; CHECK-NEXT:   (i32.const 1)
+  ;; CHECK-NEXT:   (i32.const 2)
+  ;; CHECK-NEXT:   (i32.const 3)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (array.init_elem $array $bar
+  ;; CHECK-NEXT:   (local.get $array)
+  ;; CHECK-NEXT:   (i32.const 4)
+  ;; CHECK-NEXT:   (i32.const 5)
+  ;; CHECK-NEXT:   (i32.const 6)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (global.get $foo)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (global.get $bar)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (call $foo)
+  ;; CHECK-NEXT:  (call $bar)
+  ;; CHECK-NEXT: )
+  (func $uses (param $array (ref $array))
+    ;; Tags.
+    (try
+      (do)
+      (catch $foo
+        (drop
+          (pop i32)
+        )
+      )
+    )
+    (try
+      (do)
+      (catch $bar
+        (drop
+          (pop i64)
+        )
+      )
+    )
+
+    ;; Memories
+    (drop
+      (i32.load $foo
+        (i32.const 1)
+      )
+    )
+    (drop
+      (i32.load $bar
+        (i32.const 2)
+      )
+    )
+
+    ;; Data segments
+    (data.drop $foo)
+    (data.drop $bar)
+
+    ;; Tables
+    (drop
+      (table.get $foo
+        (i32.const 1)
+      )
+    )
+    (drop
+      (table.get $bar
+        (i32.const 2)
+      )
+    )
+
+    ;; Element segments
+    (array.init_elem $array $foo
+      (local.get $array)
+      (i32.const 1)
+      (i32.const 2)
+      (i32.const 3)
+    )
+    (array.init_elem $array $bar
+      (local.get $array)
+      (i32.const 4)
+      (i32.const 5)
+      (i32.const 6)
+    )
+
+    ;; Globals
+    (drop
+      (global.get $foo)
+    )
+    (drop
+      (global.get $bar)
+    )
+
+    ;; Functions.
+    (call $foo)
+    (call $bar)
+  )
+)
+;; CHECK:      (func $foo_3 (type $none_=>_none)
+;; CHECK-NEXT:  (drop
+;; CHECK-NEXT:   (i32.const 3)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT: )
+
+;; CHECK:      (func $other (type $none_=>_none)
+;; CHECK-NEXT:  (drop
+;; CHECK-NEXT:   (i32.const 4)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT: )
+
+;; CHECK:      (func $uses.second (type $ref|$array|_=>_none) (param $array (ref $array))
+;; CHECK-NEXT:  (try $try
+;; CHECK-NEXT:   (do
+;; CHECK-NEXT:    (nop)
+;; CHECK-NEXT:   )
+;; CHECK-NEXT:   (catch $foo_2
+;; CHECK-NEXT:    (drop
+;; CHECK-NEXT:     (pop f32)
+;; CHECK-NEXT:    )
+;; CHECK-NEXT:   )
+;; CHECK-NEXT:  )
+;; CHECK-NEXT:  (try $try0
+;; CHECK-NEXT:   (do
+;; CHECK-NEXT:    (nop)
+;; CHECK-NEXT:   )
+;; CHECK-NEXT:   (catch $other
+;; CHECK-NEXT:    (drop
+;; CHECK-NEXT:     (pop f64)
+;; CHECK-NEXT:    )
+;; CHECK-NEXT:   )
+;; CHECK-NEXT:  )
+;; CHECK-NEXT:  (drop
+;; CHECK-NEXT:   (i32.load $foo_2
+;; CHECK-NEXT:    (i32.const 3)
+;; CHECK-NEXT:   )
+;; CHECK-NEXT:  )
+;; CHECK-NEXT:  (drop
+;; CHECK-NEXT:   (i32.load $other
+;; CHECK-NEXT:    (i32.const 4)
+;; CHECK-NEXT:   )
+;; CHECK-NEXT:  )
+;; CHECK-NEXT:  (data.drop $other)
+;; CHECK-NEXT:  (data.drop $bar_2)
+;; CHECK-NEXT:  (drop
+;; CHECK-NEXT:   (table.get $foo_2
+;; CHECK-NEXT:    (i32.const 3)
+;; CHECK-NEXT:   )
+;; CHECK-NEXT:  )
+;; CHECK-NEXT:  (drop
+;; CHECK-NEXT:   (table.get $other
+;; CHECK-NEXT:    (i32.const 4)
+;; CHECK-NEXT:   )
+;; CHECK-NEXT:  )
+;; CHECK-NEXT:  (array.init_elem $array $other
+;; CHECK-NEXT:   (local.get $array)
+;; CHECK-NEXT:   (i32.const 7)
+;; CHECK-NEXT:   (i32.const 8)
+;; CHECK-NEXT:   (i32.const 9)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT:  (array.init_elem $array $bar_2
+;; CHECK-NEXT:   (local.get $array)
+;; CHECK-NEXT:   (i32.const 10)
+;; CHECK-NEXT:   (i32.const 11)
+;; CHECK-NEXT:   (i32.const 12)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT:  (drop
+;; CHECK-NEXT:   (global.get $other)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT:  (drop
+;; CHECK-NEXT:   (global.get $bar_2)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT:  (call $foo_3)
+;; CHECK-NEXT:  (call $other)
+;; CHECK-NEXT: )
diff --git a/test/lit/merge/renamings.wat.second b/test/lit/merge/renamings.wat.second
new file mode 100644
index 000000000..da02e0438
--- /dev/null
+++ b/test/lit/merge/renamings.wat.second
@@ -0,0 +1,123 @@
+(module
+  (type $array (array (mut (ref null func))))
+
+  (tag $foo (param f32))
+
+  (tag $other (param f64))
+
+  (memory $foo 50 60)
+
+  (memory $other 70 80)
+
+  (data $other (i32.const 3) "ghi")
+
+  (data $bar (i32.const 4) "jkl")
+
+  (table $foo 50 60 funcref)
+
+  (table $other 70 80 funcref)
+
+  (elem $other (ref null func) $foo $other)
+
+  (elem $bar (ref null func) $other $foo)
+
+  (global $other i32 (i32.const 3))
+
+  (global $bar i32 (i32.const 4))
+
+  (export "foo" (func $foo))
+
+  (export "other" (func $other))
+
+  (export "keepalive" (func $uses.second))
+
+  ;; Also test having a different name for the export as for the internal
+  ;; thing it refers to, to test we don't assume they are identical.
+  (export "other-b" (func $other))
+
+  (func $foo
+    (drop
+      (i32.const 3)
+    )
+  )
+
+  (func $other
+    (drop
+      (i32.const 4)
+    )
+  )
+
+  (func $uses.second (param $array (ref $array))
+    ;; Tags.
+    (try
+      (do)
+      (catch $foo
+        (drop
+          (pop f32)
+        )
+      )
+    )
+    (try
+      (do)
+      (catch $other
+        (drop
+          (pop f64)
+        )
+      )
+    )
+
+    ;; Memories
+    (drop
+      (i32.load $foo
+        (i32.const 3)
+      )
+    )
+    (drop
+      (i32.load $other
+        (i32.const 4)
+      )
+    )
+
+    ;; Data segments
+    (data.drop $other)
+    (data.drop $bar)
+
+    ;; Tables
+    (drop
+      (table.get $foo
+        (i32.const 3)
+      )
+    )
+    (drop
+      (table.get $other
+        (i32.const 4)
+      )
+    )
+
+    ;; Element segments
+    (array.init_elem $array $other
+      (local.get $array)
+      (i32.const 7)
+      (i32.const 8)
+      (i32.const 9)
+    )
+    (array.init_elem $array $bar
+      (local.get $array)
+      (i32.const 10)
+      (i32.const 11)
+      (i32.const 12)
+    )
+
+    ;; Globals
+    (drop
+      (global.get $other)
+    )
+    (drop
+      (global.get $bar)
+    )
+
+    ;; Functions.
+    (call $foo)
+    (call $other)
+  )
+)
diff --git a/test/lit/merge/start.flip.wat b/test/lit/merge/start.flip.wat
new file mode 100644
index 000000000..cf7d93ca5
--- /dev/null
+++ b/test/lit/merge/start.flip.wat
@@ -0,0 +1,30 @@
+;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited.
+;; RUN: wasm-merge %s first %s.second second --rename-export-conflicts -all -S -o - | filecheck %s
+
+;; Like start, but flipped - now only the first module has a start.
+
+(module
+  ;; CHECK:      (type $none_=>_none (func))
+
+  ;; CHECK:      (export "start" (func $start_1))
+
+  ;; CHECK:      (start $start)
+  (start $start)
+
+  ;; CHECK:      (func $start (type $none_=>_none)
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (i32.const 0)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $start
+    (drop
+      (i32.const 0)
+    )
+  )
+)
+
+;; CHECK:      (func $start_1 (type $none_=>_none)
+;; CHECK-NEXT:  (drop
+;; CHECK-NEXT:   (i32.const 1)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT: )
diff --git a/test/lit/merge/start.flip.wat.second b/test/lit/merge/start.flip.wat.second
new file mode 100644
index 000000000..89dcf4f97
--- /dev/null
+++ b/test/lit/merge/start.flip.wat.second
@@ -0,0 +1,8 @@
+(module
+  (func $start (export "start")
+    ;; Not a start function, but the name overlaps so it will get deduplicated.
+    (drop
+      (i32.const 1)
+    )
+  )
+)
diff --git a/test/lit/merge/start.wat b/test/lit/merge/start.wat
new file mode 100644
index 000000000..19a9bcb91
--- /dev/null
+++ b/test/lit/merge/start.wat
@@ -0,0 +1,33 @@
+;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited.
+;; RUN: wasm-merge %s first %s.second second --rename-export-conflicts -all -S -o - | filecheck %s
+
+;; Test that we merge start functions. The first module here has none, but the
+;; second does, so we'll refer to its start function in the merged module.
+
+(module
+  (func $start
+    ;; This function has the name start, but is *not* the start function. The
+    ;; other module's start will need to get a new deduplicated name.
+    (drop
+      (i32.const 0)
+    )
+  )
+)
+;; CHECK:      (type $none_=>_none (func))
+
+;; CHECK:      (export "start" (func $start_1))
+
+;; CHECK:      (export "user" (func $user))
+
+;; CHECK:      (start $start_1)
+
+;; CHECK:      (func $start_1 (type $none_=>_none)
+;; CHECK-NEXT:  (drop
+;; CHECK-NEXT:   (i32.const 1)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT: )
+
+;; CHECK:      (func $user (type $none_=>_none)
+;; CHECK-NEXT:  (call $start_1)
+;; CHECK-NEXT:  (call $start_1)
+;; CHECK-NEXT: )
diff --git a/test/lit/merge/start.wat.second b/test/lit/merge/start.wat.second
new file mode 100644
index 000000000..0f00feb7a
--- /dev/null
+++ b/test/lit/merge/start.wat.second
@@ -0,0 +1,15 @@
+(module
+  (start $start)
+
+  (func $start (export "start")
+    (drop
+      (i32.const 1)
+    )
+  )
+
+  (func $user (export "user")
+    ;; These calls must go to the function $start here (with body "1").
+    (call $start)
+    (call $start)
+  )
+)
diff --git a/test/lit/merge/start3.wat b/test/lit/merge/start3.wat
new file mode 100644
index 000000000..ab4c555ab
--- /dev/null
+++ b/test/lit/merge/start3.wat
@@ -0,0 +1,36 @@
+;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited.
+;; RUN: wasm-merge %s first %s.second second %s.third third -all -S -o - | filecheck %s
+
+;; Test that we merge start functions. The first module here has none, but the
+;; second and third do, so we'll first copy in the second's and then merge in
+;; the third's.
+
+(module
+)
+;; CHECK:      (type $none_=>_none (func))
+
+;; CHECK:      (export "start" (func $start))
+
+;; CHECK:      (export "user" (func $user))
+
+;; CHECK:      (start $merged.start)
+
+;; CHECK:      (func $start (type $none_=>_none)
+;; CHECK-NEXT:  (drop
+;; CHECK-NEXT:   (i32.const 1)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT: )
+
+;; CHECK:      (func $user (type $none_=>_none)
+;; CHECK-NEXT:  (call $start)
+;; CHECK-NEXT:  (call $start)
+;; CHECK-NEXT: )
+
+;; CHECK:      (func $merged.start (type $none_=>_none)
+;; CHECK-NEXT:  (drop
+;; CHECK-NEXT:   (i32.const 1)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT:  (drop
+;; CHECK-NEXT:   (i32.const 2)
+;; CHECK-NEXT:  )
+;; CHECK-NEXT: )
diff --git a/test/lit/merge/start3.wat.second b/test/lit/merge/start3.wat.second
new file mode 100644
index 000000000..ec66c2f5b
--- /dev/null
+++ b/test/lit/merge/start3.wat.second
@@ -0,0 +1,16 @@
+(module
+  (start $start)
+
+  (func $start (export "start")
+    (drop
+      (i32.const 1)
+    )
+  )
+
+  (func $user (export "user")
+    ;; These calls must go to the function $start here (with body "1") and not
+    ;; to the modified start that has the third module's content merged in.
+    (call $start)
+    (call $start)
+  )
+)
diff --git a/test/lit/merge/start3.wat.third b/test/lit/merge/start3.wat.third
new file mode 100644
index 000000000..508ffdb2a
--- /dev/null
+++ b/test/lit/merge/start3.wat.third
@@ -0,0 +1,9 @@
+(module
+  (start $start)
+
+  (func $start
+    (drop
+      (i32.const 2)
+    )
+  )
+)
diff --git a/test/lit/merge/table_elem.wat b/test/lit/merge/table_elem.wat
new file mode 100644
index 000000000..3fec4d865
--- /dev/null
+++ b/test/lit/merge/table_elem.wat
@@ -0,0 +1,114 @@
+;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited.
+
+;; RUN: wasm-merge %s first %s.second second --rename-export-conflicts -all -S -o - | filecheck %s
+
+;; Test we rename tables and element segments properly at the module scope.
+;; Table $foo has a name collision, and both of the element segments' names do
+;; as well. This test verifies that element segments refer to the right tables
+;; even after such name changes.
+
+(module
+  ;; CHECK:      (type $vec (array funcref))
+  (type $vec (array funcref))
+
+  ;; CHECK:      (type $none_=>_none (func))
+
+  ;; CHECK:      (table $foo 1 funcref)
+  (table $foo 1 funcref)
+
+  ;; CHECK:      (table $bar 10 funcref)
+  (table $bar 10 funcref)
+
+  ;; CHECK:      (table $foo_2 100 funcref)
+
+  ;; CHECK:      (table $other 1000 funcref)
+
+  ;; CHECK:      (elem $a (table $foo) (i32.const 0) func)
+  (elem $a (table $foo) (i32.const 0) func)
+
+  ;; CHECK:      (elem $b (table $bar) (i32.const 0) func)
+  (elem $b (table $bar) (i32.const 0) func)
+
+  (func "keepalive2"
+    (drop
+      (table.get $foo
+        (i32.const 1)
+      )
+    )
+    (drop
+      (table.get $bar
+        (i32.const 1)
+      )
+    )
+    ;; GC operations are the only things that can keep alive an elem segment.
+    (drop
+      (array.new_elem $vec $a
+        (i32.const 1)
+        (i32.const 2)
+      )
+    )
+    (drop
+      (array.new_elem $vec $b
+        (i32.const 3)
+        (i32.const 4)
+      )
+    )
+  )
+)
+;; CHECK:      (elem $a_2 (table $foo_2) (i32.const 0) func)
+
+;; CHECK:      (elem $b_2 (table $other) (i32.const 0) func)
+
+;; CHECK:      (export "keepalive2" (func $0))
+
+;; CHECK:      (export "keepalive2_1" (func $0_1))
+
+;; CHECK:      (func $0 (type $none_=>_none)
+;; CHECK-NEXT:  (drop
+;; CHECK-NEXT:   (table.get $foo
+;; CHECK-NEXT:    (i32.const 1)
+;; CHECK-NEXT:   )
+;; CHECK-NEXT:  )
+;; CHECK-NEXT:  (drop
+;; CHECK-NEXT:   (table.get $bar
+;; CHECK-NEXT:    (i32.const 1)
+;; CHECK-NEXT:   )
+;; CHECK-NEXT:  )
+;; CHECK-NEXT:  (drop
+;; CHECK-NEXT:   (array.new_elem $vec $a
+;; CHECK-NEXT:    (i32.const 1)
+;; CHECK-NEXT:    (i32.const 2)
+;; CHECK-NEXT:   )
+;; CHECK-NEXT:  )
+;; CHECK-NEXT:  (drop
+;; CHECK-NEXT:   (array.new_elem $vec $b
+;; CHECK-NEXT:    (i32.const 3)
+;; CHECK-NEXT:    (i32.const 4)
+;; CHECK-NEXT:   )
+;; CHECK-NEXT:  )
+;; CHECK-NEXT: )
+
+;; CHECK:      (func $0_1 (type $none_=>_none)
+;; CHECK-NEXT:  (drop
+;; CHECK-NEXT:   (table.get $foo_2
+;; CHECK-NEXT:    (i32.const 1)
+;; CHECK-NEXT:   )
+;; CHECK-NEXT:  )
+;; CHECK-NEXT:  (drop
+;; CHECK-NEXT:   (table.get $other
+;; CHECK-NEXT:    (i32.const 1)
+;; CHECK-NEXT:   )
+;; CHECK-NEXT:  )
+;; CHECK-NEXT:  (drop
+;; CHECK-NEXT:   (array.new_elem $vec $a_2
+;; CHECK-NEXT:    (i32.const 5)
+;; CHECK-NEXT:    (i32.const 6)
+;; CHECK-NEXT:   )
+;; CHECK-NEXT:  )
+;; CHECK-NEXT:  (drop
+;; CHECK-NEXT:   (array.new_elem $vec $b_2
+;; CHECK-NEXT:    (i32.const 7)
+;; CHECK-NEXT:    (i32.const 8)
+;; CHECK-NEXT:   )
+;; CHECK-NEXT:  )
+;; CHECK-NEXT: )
diff --git a/test/lit/merge/table_elem.wat.second b/test/lit/merge/table_elem.wat.second
new file mode 100644
index 000000000..7aa960c7f
--- /dev/null
+++ b/test/lit/merge/table_elem.wat.second
@@ -0,0 +1,37 @@
+(module
+  (type $vec (array funcref))
+
+  (table $foo 100 funcref)
+
+  (table $other 1000 funcref)
+
+  (elem $a (table $foo) (i32.const 0) func)
+
+  (elem $b (table $other) (i32.const 0) func)
+
+  (func "keepalive2"
+    (drop
+      (table.get $foo
+        (i32.const 1)
+      )
+    )
+    (drop
+      (table.get $other
+        (i32.const 1)
+      )
+    )
+    ;; GC operations are the only things that can keep alive an elem segment.
+    (drop
+      (array.new_elem $vec $a
+        (i32.const 5)
+        (i32.const 6)
+      )
+    )
+    (drop
+      (array.new_elem $vec $b
+        (i32.const 7)
+        (i32.const 8)
+      )
+    )
+  )
+)