implement the prelink phase in the frontend

this strategy uses a "postponed" queue to handle codegen tasks that
spawn too early. there's probably a better way.

4 files changed, 110 insertions, 23 deletions

diff --git a/src/Compilation.zig b/src/Compilation.zig
index fd8fd357f4..33868ef195 100644
--- a/src/Compilation.zig
+++ b/src/Compilation.zig
@@ -113,6 +113,12 @@ link_diags: link.Diags,
 link_task_queue: ThreadSafeQueue(link.Task) = .empty,
 /// Ensure only 1 simultaneous call to `flushTaskQueue`.
 link_task_queue_safety: std.debug.SafetyLock = .{},
+/// If any tasks are queued up that depend on prelink being finished, they are moved
+/// here until prelink finishes.
+link_task_queue_postponed: std.ArrayListUnmanaged(link.Task) = .empty,
+/// Initialized with how many link input tasks are expected. After this reaches zero
+/// the linker will begin the prelink phase.
+remaining_prelink_tasks: u32,
 
 work_queues: [
     len: {
@@ -1515,6 +1521,7 @@ pub fn create(gpa: Allocator, arena: Allocator, options: CreateOptions) !*Compil
             .file_system_inputs = options.file_system_inputs,
             .parent_whole_cache = options.parent_whole_cache,
             .link_diags = .init(gpa),
+            .remaining_prelink_tasks = 0,
         };
 
         // Prevent some footguns by making the "any" fields of config reflect
@@ -1780,10 +1787,12 @@ pub fn create(gpa: Allocator, arena: Allocator, options: CreateOptions) !*Compil
                     inline for (fields) |field| {
                         if (@field(paths, field.name)) |path| {
                             comp.link_task_queue.shared.appendAssumeCapacity(.{ .load_object = path });
+                            comp.remaining_prelink_tasks += 1;
                         }
                     }
                     // Loads the libraries provided by `target_util.libcFullLinkFlags(target)`.
                     comp.link_task_queue.shared.appendAssumeCapacity(.load_host_libc);
+                    comp.remaining_prelink_tasks += 1;
                 } else if (target.isMusl() and !target.isWasm()) {
                     if (!std.zig.target.canBuildLibC(target)) return error.LibCUnavailable;
 
@@ -1792,14 +1801,17 @@ pub fn create(gpa: Allocator, arena: Allocator, options: CreateOptions) !*Compil
                             .{ .musl_crt_file = .crti_o },
                             .{ .musl_crt_file = .crtn_o },
                         });
+                        comp.remaining_prelink_tasks += 2;
                     }
                     if (musl.needsCrt0(comp.config.output_mode, comp.config.link_mode, comp.config.pie)) |f| {
                         try comp.queueJobs(&.{.{ .musl_crt_file = f }});
+                        comp.remaining_prelink_tasks += 1;
                     }
                     try comp.queueJobs(&.{.{ .musl_crt_file = switch (comp.config.link_mode) {
                         .static => .libc_a,
                         .dynamic => .libc_so,
                     } }});
+                    comp.remaining_prelink_tasks += 1;
                 } else if (target.isGnuLibC()) {
                     if (!std.zig.target.canBuildLibC(target)) return error.LibCUnavailable;
 
@@ -1808,14 +1820,18 @@ pub fn create(gpa: Allocator, arena: Allocator, options: CreateOptions) !*Compil
                             .{ .glibc_crt_file = .crti_o },
                             .{ .glibc_crt_file = .crtn_o },
                         });
+                        comp.remaining_prelink_tasks += 2;
                     }
                     if (glibc.needsCrt0(comp.config.output_mode)) |f| {
                         try comp.queueJobs(&.{.{ .glibc_crt_file = f }});
+                        comp.remaining_prelink_tasks += 1;
                     }
                     try comp.queueJobs(&[_]Job{
                         .{ .glibc_shared_objects = {} },
                         .{ .glibc_crt_file = .libc_nonshared_a },
                     });
+                    comp.remaining_prelink_tasks += 1;
+                    comp.remaining_prelink_tasks += glibc.sharedObjectsCount(&target);
                 } else if (target.isWasm() and target.os.tag == .wasi) {
                     if (!std.zig.target.canBuildLibC(target)) return error.LibCUnavailable;
 
@@ -1823,11 +1839,13 @@ pub fn create(gpa: Allocator, arena: Allocator, options: CreateOptions) !*Compil
                         try comp.queueJob(.{
                             .wasi_libc_crt_file = crt_file,
                         });
+                        comp.remaining_prelink_tasks += 1;
                     }
                     try comp.queueJobs(&[_]Job{
                         .{ .wasi_libc_crt_file = wasi_libc.execModelCrtFile(comp.config.wasi_exec_model) },
                         .{ .wasi_libc_crt_file = .libc_a },
                     });
+                    comp.remaining_prelink_tasks += 2;
                 } else if (target.isMinGW()) {
                     if (!std.zig.target.canBuildLibC(target)) return error.LibCUnavailable;
 
@@ -1836,6 +1854,7 @@ pub fn create(gpa: Allocator, arena: Allocator, options: CreateOptions) !*Compil
                         .{ .mingw_crt_file = .mingw32_lib },
                         crt_job,
                     });
+                    comp.remaining_prelink_tasks += 2;
 
                     // When linking mingw-w64 there are some import libs we always need.
                     try comp.windows_libs.ensureUnusedCapacity(gpa, mingw.always_link_libs.len);
@@ -1847,6 +1866,7 @@ pub fn create(gpa: Allocator, arena: Allocator, options: CreateOptions) !*Compil
                     }
                 } else if (target.os.tag == .freestanding and capable_of_building_zig_libc) {
                     try comp.queueJob(.{ .zig_libc = {} });
+                    comp.remaining_prelink_tasks += 1;
                 } else {
                     return error.LibCUnavailable;
                 }
@@ -1858,16 +1878,20 @@ pub fn create(gpa: Allocator, arena: Allocator, options: CreateOptions) !*Compil
                 for (0..count) |i| {
                     try comp.queueJob(.{ .windows_import_lib = i });
                 }
+                comp.remaining_prelink_tasks += @intCast(count);
             }
             if (comp.wantBuildLibUnwindFromSource()) {
                 try comp.queueJob(.{ .libunwind = {} });
+                comp.remaining_prelink_tasks += 1;
             }
             if (build_options.have_llvm and is_exe_or_dyn_lib and comp.config.link_libcpp) {
                 try comp.queueJob(.libcxx);
                 try comp.queueJob(.libcxxabi);
+                comp.remaining_prelink_tasks += 2;
             }
             if (build_options.have_llvm and is_exe_or_dyn_lib and comp.config.any_sanitize_thread) {
                 try comp.queueJob(.libtsan);
+                comp.remaining_prelink_tasks += 1;
             }
 
             if (target.isMinGW() and comp.config.any_non_single_threaded) {
@@ -1886,21 +1910,25 @@ pub fn create(gpa: Allocator, arena: Allocator, options: CreateOptions) !*Compil
                 if (is_exe_or_dyn_lib) {
                     log.debug("queuing a job to build compiler_rt_lib", .{});
                     comp.job_queued_compiler_rt_lib = true;
+                    comp.remaining_prelink_tasks += 1;
                 } else if (output_mode != .Obj) {
                     log.debug("queuing a job to build compiler_rt_obj", .{});
                     // In this case we are making a static library, so we ask
                     // for a compiler-rt object to put in it.
                     comp.job_queued_compiler_rt_obj = true;
+                    comp.remaining_prelink_tasks += 1;
                 }
             }
 
             if (is_exe_or_dyn_lib and comp.config.any_fuzz and capable_of_building_compiler_rt) {
                 log.debug("queuing a job to build libfuzzer", .{});
                 comp.job_queued_fuzzer_lib = true;
+                comp.remaining_prelink_tasks += 1;
             }
         }
 
         try comp.link_task_queue.shared.append(gpa, .load_explicitly_provided);
+        comp.remaining_prelink_tasks += 1;
     }
 
     return comp;
@@ -1977,6 +2005,7 @@ pub fn destroy(comp: *Compilation) void {
 
     comp.link_diags.deinit();
     comp.link_task_queue.deinit(gpa);
+    comp.link_task_queue_postponed.deinit(gpa);
 
     comp.clearMiscFailures();
 
@@ -3528,9 +3557,9 @@ pub fn performAllTheWork(
 
     defer if (comp.zcu) |zcu| {
         zcu.sema_prog_node.end();
-        zcu.sema_prog_node = std.Progress.Node.none;
+        zcu.sema_prog_node = .none;
         zcu.codegen_prog_node.end();
-        zcu.codegen_prog_node = std.Progress.Node.none;
+        zcu.codegen_prog_node = .none;
 
         zcu.generation += 1;
     };
@@ -3663,7 +3692,7 @@ fn performAllTheWorkInner(
         try zcu.flushRetryableFailures();
 
         zcu.sema_prog_node = main_progress_node.start("Semantic Analysis", 0);
-        zcu.codegen_prog_node = main_progress_node.start("Code Generation", 0);
+        zcu.codegen_prog_node = if (comp.bin_file != null) main_progress_node.start("Code Generation", 0) else .none;
     }
 
     if (!comp.separateCodegenThreadOk()) {
@@ -3693,6 +3722,8 @@ fn performAllTheWorkInner(
                 });
                 continue;
             }
+            zcu.sema_prog_node.end();
+            zcu.sema_prog_node = .none;
         }
         break;
     }
diff --git a/src/glibc.zig b/src/glibc.zig
index 5bad947e5d..744e4d1766 100644
--- a/src/glibc.zig
+++ b/src/glibc.zig
@@ -1217,6 +1217,18 @@ pub fn buildSharedObjects(comp: *Compilation, prog_node: std.Progress.Node) !voi
     });
 }
 
+pub fn sharedObjectsCount(target: *const std.Target) u8 {
+    const target_version = target.os.versionRange().gnuLibCVersion() orelse return 0;
+    var count: u8 = 0;
+    for (libs) |lib| {
+        if (lib.removed_in) |rem_in| {
+            if (target_version.order(rem_in) != .lt) continue;
+        }
+        count += 1;
+    }
+    return count;
+}
+
 fn queueSharedObjects(comp: *Compilation, so_files: BuiltSharedObjects) void {
     const target_version = comp.getTarget().os.versionRange().gnuLibCVersion().?;
 
diff --git a/src/link.zig b/src/link.zig
index 5a9cd5a7e4..e828e24b99 100644
--- a/src/link.zig
+++ b/src/link.zig
@@ -364,6 +364,7 @@ pub const File = struct {
     build_id: std.zig.BuildId,
     allow_shlib_undefined: bool,
     stack_size: u64,
+    post_prelink: bool = false,
 
     /// Prevents other processes from clobbering files in the output directory
     /// of this linking operation.
@@ -780,6 +781,8 @@ pub const File = struct {
             return;
         }
 
+        assert(base.post_prelink);
+
         const use_lld = build_options.have_llvm and comp.config.use_lld;
         const output_mode = comp.config.output_mode;
         const link_mode = comp.config.link_mode;
@@ -1007,7 +1010,8 @@ pub const File = struct {
 
     /// Called when all linker inputs have been sent via `loadInput`. After
     /// this, `loadInput` will not be called anymore.
-    pub fn prelink(base: *File) FlushError!void {
+    pub fn prelink(base: *File, prog_node: std.Progress.Node) FlushError!void {
+        assert(!base.post_prelink);
         const use_lld = build_options.have_llvm and base.comp.config.use_lld;
         if (use_lld) return;
 
@@ -1019,7 +1023,7 @@ pub const File = struct {
         switch (base.tag) {
             inline .wasm => |tag| {
                 dev.check(tag.devFeature());
-                return @as(*tag.Type(), @fieldParentPtr("base", base)).prelink();
+                return @as(*tag.Type(), @fieldParentPtr("base", base)).prelink(prog_node);
             },
             else => {},
         }
@@ -1326,12 +1330,32 @@ pub const File = struct {
 /// from the rest of compilation. All tasks performed here are
 /// single-threaded with respect to one another.
 pub fn flushTaskQueue(tid: usize, comp: *Compilation) void {
+    const diags = &comp.link_diags;
     // As soon as check() is called, another `flushTaskQueue` call could occur,
     // so the safety lock must go after the check.
     while (comp.link_task_queue.check()) |tasks| {
         comp.link_task_queue_safety.lock();
         defer comp.link_task_queue_safety.unlock();
+
+        if (comp.remaining_prelink_tasks > 0) {
+            comp.link_task_queue_postponed.ensureUnusedCapacity(comp.gpa, tasks.len) catch |err| switch (err) {
+                error.OutOfMemory => return diags.setAllocFailure(),
+            };
+        }
+
         for (tasks) |task| doTask(comp, tid, task);
+
+        if (comp.remaining_prelink_tasks == 0) {
+            if (comp.bin_file) |base| if (!base.post_prelink) {
+                base.prelink(comp.work_queue_progress_node) catch |err| switch (err) {
+                    error.OutOfMemory => diags.setAllocFailure(),
+                    error.LinkFailure => continue,
+                };
+                base.post_prelink = true;
+                for (comp.link_task_queue_postponed.items) |task| doTask(comp, tid, task);
+                comp.link_task_queue_postponed.clearRetainingCapacity();
+            };
+        }
     }
 }
 
@@ -1375,6 +1399,7 @@ pub fn doTask(comp: *Compilation, tid: usize, task: Task) void {
     const diags = &comp.link_diags;
     switch (task) {
         .load_explicitly_provided => if (comp.bin_file) |base| {
+            comp.remaining_prelink_tasks -= 1;
             const prog_node = comp.work_queue_progress_node.start("Parse Linker Inputs", comp.link_inputs.len);
             defer prog_node.end();
             for (comp.link_inputs) |input| {
@@ -1392,6 +1417,7 @@ pub fn doTask(comp: *Compilation, tid: usize, task: Task) void {
             }
         },
         .load_host_libc => if (comp.bin_file) |base| {
+            comp.remaining_prelink_tasks -= 1;
             const prog_node = comp.work_queue_progress_node.start("Linker Parse Host libc", 0);
             defer prog_node.end();
 
@@ -1451,6 +1477,7 @@ pub fn doTask(comp: *Compilation, tid: usize, task: Task) void {
             }
         },
         .load_object => |path| if (comp.bin_file) |base| {
+            comp.remaining_prelink_tasks -= 1;
             const prog_node = comp.work_queue_progress_node.start("Linker Parse Object", 0);
             defer prog_node.end();
             base.openLoadObject(path) catch |err| switch (err) {
@@ -1459,6 +1486,7 @@ pub fn doTask(comp: *Compilation, tid: usize, task: Task) void {
             };
         },
         .load_archive => |path| if (comp.bin_file) |base| {
+            comp.remaining_prelink_tasks -= 1;
             const prog_node = comp.work_queue_progress_node.start("Linker Parse Archive", 0);
             defer prog_node.end();
             base.openLoadArchive(path, null) catch |err| switch (err) {
@@ -1467,6 +1495,7 @@ pub fn doTask(comp: *Compilation, tid: usize, task: Task) void {
             };
         },
         .load_dso => |path| if (comp.bin_file) |base| {
+            comp.remaining_prelink_tasks -= 1;
             const prog_node = comp.work_queue_progress_node.start("Linker Parse Shared Library", 0);
             defer prog_node.end();
             base.openLoadDso(path, .{
@@ -1478,6 +1507,7 @@ pub fn doTask(comp: *Compilation, tid: usize, task: Task) void {
             };
         },
         .load_input => |input| if (comp.bin_file) |base| {
+            comp.remaining_prelink_tasks -= 1;
             const prog_node = comp.work_queue_progress_node.start("Linker Parse Input", 0);
             defer prog_node.end();
             base.loadInput(input) catch |err| switch (err) {
@@ -1492,26 +1522,38 @@ pub fn doTask(comp: *Compilation, tid: usize, task: Task) void {
             };
         },
         .codegen_nav => |nav_index| {
-            const pt: Zcu.PerThread = .activate(comp.zcu.?, @enumFromInt(tid));
-            defer pt.deactivate();
-            pt.linkerUpdateNav(nav_index) catch |err| switch (err) {
-                error.OutOfMemory => diags.setAllocFailure(),
-            };
+            if (comp.remaining_prelink_tasks == 0) {
+                const pt: Zcu.PerThread = .activate(comp.zcu.?, @enumFromInt(tid));
+                defer pt.deactivate();
+                pt.linkerUpdateNav(nav_index) catch |err| switch (err) {
+                    error.OutOfMemory => diags.setAllocFailure(),
+                };
+            } else {
+                comp.link_task_queue_postponed.appendAssumeCapacity(task);
+            }
         },
         .codegen_func => |func| {
-            const pt: Zcu.PerThread = .activate(comp.zcu.?, @enumFromInt(tid));
-            defer pt.deactivate();
-            // This call takes ownership of `func.air`.
-            pt.linkerUpdateFunc(func.func, func.air) catch |err| switch (err) {
-                error.OutOfMemory => diags.setAllocFailure(),
-            };
+            if (comp.remaining_prelink_tasks == 0) {
+                const pt: Zcu.PerThread = .activate(comp.zcu.?, @enumFromInt(tid));
+                defer pt.deactivate();
+                // This call takes ownership of `func.air`.
+                pt.linkerUpdateFunc(func.func, func.air) catch |err| switch (err) {
+                    error.OutOfMemory => diags.setAllocFailure(),
+                };
+            } else {
+                comp.link_task_queue_postponed.appendAssumeCapacity(task);
+            }
         },
         .codegen_type => |ty| {
-            const pt: Zcu.PerThread = .activate(comp.zcu.?, @enumFromInt(tid));
-            defer pt.deactivate();
-            pt.linkerUpdateContainerType(ty) catch |err| switch (err) {
-                error.OutOfMemory => diags.setAllocFailure(),
-            };
+            if (comp.remaining_prelink_tasks == 0) {
+                const pt: Zcu.PerThread = .activate(comp.zcu.?, @enumFromInt(tid));
+                defer pt.deactivate();
+                pt.linkerUpdateContainerType(ty) catch |err| switch (err) {
+                    error.OutOfMemory => diags.setAllocFailure(),
+                };
+            } else {
+                comp.link_task_queue_postponed.appendAssumeCapacity(task);
+            }
         },
         .update_line_number => |ti| {
             const pt: Zcu.PerThread = .activate(comp.zcu.?, @enumFromInt(tid));
diff --git a/src/link/Wasm/Flush.zig b/src/link/Wasm/Flush.zig
index 5cfa8d268a..4a9e21d7be 100644
--- a/src/link/Wasm/Flush.zig
+++ b/src/link/Wasm/Flush.zig
@@ -571,8 +571,10 @@ pub fn finish(f: *Flush, wasm: *Wasm) !void {
                 .__tls_size => @panic("TODO"),
                 .object_global => |i| {
                     const global = i.ptr(wasm);
-                    try binary_writer.writeByte(@intFromEnum(@as(std.wasm.Valtype, global.flags.global_type.valtype.to())));
-                    try binary_writer.writeByte(@intFromBool(global.flags.global_type.mutable));
+                    try binary_bytes.appendSlice(gpa, &.{
+                        @intFromEnum(@as(std.wasm.Valtype, global.flags.global_type.valtype.to())),
+                        @intFromBool(global.flags.global_type.mutable),
+                    });
                     try emitExpr(wasm, binary_bytes, global.expr);
                 },
                 .nav_exe => @panic("TODO"),