[Linker] Make repeated passes over archive members (#440)

An archive member can depend on any other archive member, so adding a
member to the link can introduce new undefined references that must be
satisfied. The linker must continue to iterate over the members until
nothing new is added to the link.

6 files changed, 53 insertions, 23 deletions

diff --git a/check.py b/check.py
index b02ce14ce..4a8a0c7a5 100755
--- a/check.py
+++ b/check.py
@@ -500,7 +500,7 @@ for dot_s_dir in ['dot_s', 'llvm_autogenerated']:
 print '\n[ running linker tests... ]\n'
 # The {main,foo,bar,baz}.s files were created by running clang over the respective
 # c files. The foobar.bar archive was created by running:
-# llvm-ar -format=gnu rc foobar.a foo.s bar.s baz.s
+# llvm-ar -format=gnu rc foobar.a quux.s foo.s bar.s baz.s
 s2wasm = os.path.join('bin', 's2wasm')
 cmd = [s2wasm, os.path.join('test', 'linker', 'main.s'), '-l', os.path.join('test', 'linker', 'archive', 'foobar.a')]
 output = run_command(cmd)
@@ -509,6 +509,8 @@ fail_if_not_contained(output, '(func $foo')
 fail_if_not_contained(output, '(i32.const 42)')
 # bar should be linked in from bar.s
 fail_if_not_contained(output, '(func $bar')
+# quux should be linked in from bar.s even though it comes before bar.s in the archive
+fail_if_not_contained(output, '(func $quux')
 # baz should not be linked in at all
 if 'baz' in output:
   raise Exception('output should not contain "baz": ' + output)
diff --git a/src/wasm-linker.cpp b/src/wasm-linker.cpp
index f4f516073..a4bd97e2f 100644
--- a/src/wasm-linker.cpp
+++ b/src/wasm-linker.cpp
@@ -217,23 +217,31 @@ bool Linker::linkObject(S2WasmBuilder& builder) {
 }
 
 bool Linker::linkArchive(Archive& archive) {
-  for (auto child = archive.child_begin(), end = archive.child_end();
-       child != end; ++child) {
-    Archive::SubBuffer memberBuf = child->getBuffer();
-    // S2WasmBuilder expects its input to be NUL-terminated. Archive members are
-    // not NUL-terminated. So we have to copy the contents out before parsing.
-    std::vector<char> memberString(memberBuf.len + 1);
-    memcpy(memberString.data(), memberBuf.data, memberBuf.len);
-    memberString[memberBuf.len] = '\0';
-    S2WasmBuilder memberBuilder(memberString.data(), false);
-    auto* memberSymbols = memberBuilder.getSymbolInfo();
-    for (const Name& symbol : memberSymbols->implementedFunctions) {
-      if (out.symbolInfo.undefinedFunctions.count(symbol)) {
-        if (!linkObject(memberBuilder)) return false;
-        break;
+  bool selected;
+  do {
+    selected = false;
+    for (auto child = archive.child_begin(), end = archive.child_end();
+         child != end; ++child) {
+      Archive::SubBuffer memberBuf = child->getBuffer();
+      // S2WasmBuilder expects its input to be NUL-terminated. Archive members
+      // are
+      // not NUL-terminated. So we have to copy the contents out before parsing.
+      std::vector<char> memberString(memberBuf.len + 1);
+      memcpy(memberString.data(), memberBuf.data, memberBuf.len);
+      memberString[memberBuf.len] = '\0';
+      S2WasmBuilder memberBuilder(memberString.data(), false);
+      auto* memberSymbols = memberBuilder.getSymbolInfo();
+      for (const Name& symbol : memberSymbols->implementedFunctions) {
+        if (out.symbolInfo.undefinedFunctions.count(symbol)) {
+          if (!linkObject(memberBuilder)) return false;
+          selected = true;
+          break;
+        }
       }
     }
-  }
+    // If we selected an archive member, it may depend on another archive member
+    // so continue to make passes over the members until no more are added.
+  } while (selected);
   return true;
 }
 
diff --git a/test/linker/archive/bar.s b/test/linker/archive/bar.s
index 7c39347e0..5012d4f14 100644
--- a/test/linker/archive/bar.s
+++ b/test/linker/archive/bar.s
@@ -1,15 +1,16 @@
 	.text
-	.file	"src/work/binaryen/test/linker/archive/bar.c"
+	.file	"test/linker/bar.c"
 	.section	.text.bar,"ax",@progbits
 	.hidden	bar
 	.globl	bar
 	.type	bar,@function
 bar:                                    # @bar
 # BB#0:                                 # %entry
+	call    	quux@FUNCTION
 	return
 	.endfunc
 .Lfunc_end0:
 	.size	bar, .Lfunc_end0-bar
 
 
-	.ident	"clang version 3.9.0 (trunk 267883) (llvm/trunk 267901)"
+	.ident	"clang version 3.9.0 (trunk 268553) (llvm/trunk 268561)"
diff --git a/test/linker/archive/foobar.a b/test/linker/archive/foobar.a
index 6028e8ce5..0da380708 100644
--- a/test/linker/archive/foobar.a
+++ b/test/linker/archive/foobar.a
@@ -1,4 +1,21 @@
 !<arch>
+quux.s/         0           0     0     644     345       `
+	.text
+	.file	"test/linker/quux.c"
+	.section	.text.quux,"ax",@progbits
+	.hidden	quux
+	.globl	quux
+	.type	quux,@function
+quux:                                   # @quux
+# BB#0:                                 # %entry
+	return
+	.endfunc
+.Lfunc_end0:
+	.size	quux, .Lfunc_end0-quux
+
+
+	.ident	"clang version 3.9.0 (trunk 268553) (llvm/trunk 268561)"
+
 foo.s/          0           0     0     644     407       `
 	.text
 	.file	"src/work/binaryen/test/linker/foo.c"
@@ -19,22 +36,23 @@ foo:                                    # @foo
 
 	.ident	"clang version 3.9.0 (trunk 267883) (llvm/trunk 267901)"
 
-bar.s/          0           0     0     644     363       `
+bar.s/          0           0     0     644     361       `
 	.text
-	.file	"src/work/binaryen/test/linker/archive/bar.c"
+	.file	"test/linker/bar.c"
 	.section	.text.bar,"ax",@progbits
 	.hidden	bar
 	.globl	bar
 	.type	bar,@function
 bar:                                    # @bar
 # BB#0:                                 # %entry
+	call    	quux@FUNCTION
 	return
 	.endfunc
 .Lfunc_end0:
 	.size	bar, .Lfunc_end0-bar
 
 
-	.ident	"clang version 3.9.0 (trunk 267883) (llvm/trunk 267901)"
+	.ident	"clang version 3.9.0 (trunk 268553) (llvm/trunk 268561)"
 
 baz.s/          0           0     0     644     355       `
 	.text
diff --git a/test/linker/bar.c b/test/linker/bar.c
index 0476ca2b0..8f32349da 100644
--- a/test/linker/bar.c
+++ b/test/linker/bar.c
@@ -1,2 +1,2 @@
-void bar() {
-}
+void quux();
+void bar() { quux(); }
diff --git a/test/linker/quux.c b/test/linker/quux.c
new file mode 100644
index 000000000..d9baa902a
--- /dev/null
+++ b/test/linker/quux.c
@@ -0,0 +1 @@
+void quux() {}