[lld][WebAssembly] Fix bitcode LTO order in archive parsing (#73095)

When doing LTO on multiple archives, the order with which bitcodes are
linked to the LTO module is hard to control, given that processing
undefined symbols can lead to parsing of an object file, which in turn
lead to parsing of another object file before finishing parsing of the
previous file. This can result in encountering a non-prevailing comdat
first when linking, which can make the the symbol undefined, and the
real definition is added later with an additional prefix to avoid
duplication (e.g. `__cxx_global_var_init` and `__cxx_global_var_init.2`)

So this one-line fix ensures we compile bitcodes in the order that we
process comdats, so that when multiple archived bitcode files have the
same variable with the same comdat, we make sure that the prevailing
comdat will be linked first in the LTO.

Fixes #62243.

4 files changed, 103 insertions, 1 deletions

diff --git a/lld/test/wasm/lto/Inputs/comdat_ordering1.ll b/lld/test/wasm/lto/Inputs/comdat_ordering1.ll
new file mode 100644
index 0000000..b866c6e
--- /dev/null
+++ b/lld/test/wasm/lto/Inputs/comdat_ordering1.ll
@@ -0,0 +1,42 @@
+target datalayout = "e-m:e-p:32:32-p10:8:8-p20:8:8-i64:64-n32:64-S128"
+target triple = "wasm32-unknown-unknown"
+
+; Generated from this C++ code and simplified manually:
+;
+; int foo();
+; inline int unused = foo();
+;
+; int main() {
+;   return foo();
+; }
+
+$unused = comdat any
+
+@unused = linkonce_odr global i32 0, comdat, align 4
+@_ZGV6unused = linkonce_odr global i32 0, comdat($unused), align 4
+@llvm.global_ctors = appending global [1 x { i32, ptr, ptr }] [{ i32, ptr, ptr } { i32 65535, ptr @__cxx_global_var_init, ptr @unused }]
+
+define internal void @__cxx_global_var_init() comdat($unused) {
+entry:
+  %0 = load i8, ptr @_ZGV6unused, align 4
+  %1 = and i8 %0, 1
+  %guard.uninitialized = icmp eq i8 %1, 0
+  br i1 %guard.uninitialized, label %init.check, label %init.end
+
+init.check:                                       ; preds = %entry
+  store i8 1, ptr @_ZGV6unused, align 4
+  %call = call i32 @foo()
+  store i32 %call, ptr @unused, align 4
+  br label %init.end
+
+init.end:                                         ; preds = %init.check, %entry
+  ret void
+}
+
+declare i32 @foo()
+
+define i32 @main() {
+entry:
+  %call = call i32 @foo()
+  ret i32 %call
+}
diff --git a/lld/test/wasm/lto/Inputs/comdat_ordering2.ll b/lld/test/wasm/lto/Inputs/comdat_ordering2.ll
new file mode 100644
index 0000000..58ab512
--- /dev/null
+++ b/lld/test/wasm/lto/Inputs/comdat_ordering2.ll
@@ -0,0 +1,39 @@
+target datalayout = "e-m:e-p:32:32-p10:8:8-p20:8:8-i64:64-n32:64-S128"
+target triple = "wasm32-unknown-unknown"
+
+; Generated from this C++ code and simplified manually:
+;
+; int foo();
+; inline int unused = foo();
+;
+; int foo() {
+;   return 42;
+; }
+
+$unused = comdat any
+
+@unused = linkonce_odr global i32 0, comdat, align 4
+@_ZGV6unused = linkonce_odr global i32 0, comdat($unused), align 4
+@llvm.global_ctors = appending global [1 x { i32, ptr, ptr }] [{ i32, ptr, ptr } { i32 65535, ptr @__cxx_global_var_init, ptr @unused }]
+
+define internal void @__cxx_global_var_init() comdat($unused) {
+entry:
+  %0 = load i8, ptr @_ZGV6unused, align 4
+  %1 = and i8 %0, 1
+  %guard.uninitialized = icmp eq i8 %1, 0
+  br i1 %guard.uninitialized, label %init.check, label %init.end
+
+init.check:                                       ; preds = %entry
+  store i8 1, ptr @_ZGV6unused, align 4
+  %call = call i32 @foo()
+  store i32 %call, ptr @unused, align 4
+  br label %init.end
+
+init.end:                                         ; preds = %init.check, %entry
+  ret void
+}
+
+define i32 @foo() {
+entry:
+  ret i32 42
+}
diff --git a/lld/test/wasm/lto/comdat_ordering.test b/lld/test/wasm/lto/comdat_ordering.test
new file mode 100644
index 0000000..12a0efc
--- /dev/null
+++ b/lld/test/wasm/lto/comdat_ordering.test
@@ -0,0 +1,19 @@
+; Check if we handle a variable (here __cxx_global_var_init) in different LTO
+; bitcode modules sharing a comdat.
+
+; RUN: llvm-as %S/Inputs/comdat_ordering1.ll -o %t1.o
+; RUN: llvm-as %S/Inputs/comdat_ordering2.ll -o %t2.o
+; RUN: llvm-ar rcs %t1.a %t1.o
+; RUN: llvm-ar rcs %t2.a %t2.o
+; RUN: wasm-ld %t1.a %t2.a -o %t.wasm --no-entry --export=main --export=__wasm_call_ctors
+; RUN: obj2yaml %t.wasm | FileCheck %s
+
+; CHECK:       - Type:            CUSTOM
+; CHECK-NEXT:    Name:            name
+; CHECK-NEXT:    FunctionNames:
+; CHECK-NEXT:      - Index:           0
+; CHECK-NEXT:        Name:            __wasm_call_ctors
+; CHECK-NEXT:      - Index:           1
+; CHECK-NEXT:        Name:            __cxx_global_var_init
+
+; CHECK-NOT:         Name:            __cxx_global_var_init.2
diff --git a/lld/wasm/SymbolTable.cpp b/lld/wasm/SymbolTable.cpp
index a00e336..7637052 100644
--- a/lld/wasm/SymbolTable.cpp
+++ b/lld/wasm/SymbolTable.cpp
@@ -50,8 +50,10 @@ void SymbolTable::addFile(InputFile *file, StringRef symName) {
 
   // LLVM bitcode file
   if (auto *f = dyn_cast<BitcodeFile>(file)) {
-    f->parse(symName);
+    // This order, first adding to `bitcodeFiles` and then parsing is necessary.
+    // See https://github.com/llvm/llvm-project/pull/73095
     bitcodeFiles.push_back(f);
+    f->parse(symName);
     return;
   }