wasm-linker: Resolve relocations

We now resolve relocations for globals, memory addresses and function indexes.
Besides above, we now also emit imported functions correctly and create a
corresponding undefined symbol for it, where as we create a defined symbol
for all other cases.

TODO: Make incrememental compilation work again with new linker infrastructure

5 files changed, 115 insertions, 86 deletions

diff --git a/src/arch/wasm/CodeGen.zig b/src/arch/wasm/CodeGen.zig
index 5bf58cd34f..9c82f84b2c 100644
--- a/src/arch/wasm/CodeGen.zig
+++ b/src/arch/wasm/CodeGen.zig
@@ -1363,16 +1363,7 @@ fn emitConstant(self: *Self, val: Value, ty: Type) InnerError!void {
             if (val.castTag(.decl_ref)) |payload| {
                 const decl = payload.data;
                 decl.alive = true;
-
-                // offset into the offset table within the 'data' section
-                // const ptr_width = self.target.cpu.arch.ptrBitWidth() / 8;
-                // try self.addImm32(@bitCast(i32, decl.link.wasm.offset_index * ptr_width));
-
-                // memory instruction followed by their memarg immediate
-                // memarg ::== x:u32, y:u32 => {align x, offset y}
-                const extra_index = try self.addExtra(Mir.MemArg{ .offset = 0, .alignment = 4 });
-                try self.addInst(.{ .tag = .i32_load, .data = .{ .payload = extra_index } });
-                @panic("REDO!\n");
+                try self.addLabel(.memory_address, decl.link.wasm.sym_index);
             } else return self.fail("Wasm TODO: emitConstant for other const pointer tag {s}", .{val.tag()});
         },
         .Void => {},
diff --git a/src/arch/wasm/Emit.zig b/src/arch/wasm/Emit.zig
index 5186896185..d01f319b91 100644
--- a/src/arch/wasm/Emit.zig
+++ b/src/arch/wasm/Emit.zig
@@ -49,6 +49,7 @@ pub fn emitMir(emit: *Emit) InnerError!void {
             .call => try emit.emitCall(inst),
             .global_get => try emit.emitGlobal(tag, inst),
             .global_set => try emit.emitGlobal(tag, inst),
+            .memory_address => try emit.emitMemAddress(inst),
 
             // immediates
             .f32_const => try emit.emitFloat32(inst),
@@ -157,6 +158,10 @@ pub fn emitMir(emit: *Emit) InnerError!void {
     }
 }
 
+fn offset(self: Emit) u32 {
+    return @intCast(u32, self.code.items.len);
+}
+
 fn fail(emit: *Emit, comptime format: []const u8, args: anytype) InnerError {
     @setCold(true);
     std.debug.assert(emit.error_msg == null);
@@ -209,9 +214,14 @@ fn emitGlobal(emit: *Emit, tag: Mir.Inst.Tag, inst: Mir.Inst.Index) !void {
     try emit.code.append(@enumToInt(tag));
     var buf: [5]u8 = undefined;
     leb128.writeUnsignedFixed(5, &buf, label);
+    const global_offset = emit.offset();
     try emit.code.appendSlice(&buf);
 
-    // TODO: Append label to the relocation list of this function
+    try emit.decl.link.wasm.relocs.append(emit.bin_file.allocator, .{
+        .index = label,
+        .offset = global_offset,
+        .relocation_type = .R_WASM_GLOBAL_INDEX_LEB,
+    });
 }
 
 fn emitImm32(emit: *Emit, inst: Mir.Inst.Index) !void {
@@ -254,17 +264,29 @@ fn emitMemArg(emit: *Emit, tag: Mir.Inst.Tag, inst: Mir.Inst.Index) !void {
 fn emitCall(emit: *Emit, inst: Mir.Inst.Index) !void {
     const label = emit.mir.instructions.items(.data)[inst].label;
     try emit.code.append(std.wasm.opcode(.call));
-    const offset = @intCast(u32, emit.code.items.len);
+    const call_offset = emit.offset();
     var buf: [5]u8 = undefined;
     leb128.writeUnsignedFixed(5, &buf, label);
     try emit.code.appendSlice(&buf);
 
-    // The function index immediate argument will be filled in using this data
-    // in link.Wasm.flush().
-    // TODO: Replace this with proper relocations saved in the Atom.
     try emit.decl.link.wasm.relocs.append(emit.bin_file.allocator, .{
-        .offset = offset,
+        .offset = call_offset,
         .index = label,
         .relocation_type = .R_WASM_FUNCTION_INDEX_LEB,
     });
 }
+
+fn emitMemAddress(emit: *Emit, inst: Mir.Inst.Index) !void {
+    const symbol_index = emit.mir.instructions.items(.data)[inst].label;
+    try emit.code.append(std.wasm.opcode(.i32_const));
+    const mem_offset = emit.offset();
+    var buf: [5]u8 = undefined;
+    leb128.writeUnsignedFixed(5, &buf, symbol_index);
+    try emit.code.appendSlice(&buf);
+
+    try emit.decl.link.wasm.relocs.append(emit.bin_file.allocator, .{
+        .offset = mem_offset,
+        .index = symbol_index,
+        .relocation_type = .R_WASM_MEMORY_ADDR_LEB,
+    });
+}
diff --git a/src/arch/wasm/Mir.zig b/src/arch/wasm/Mir.zig
index dbe894f212..97d8875984 100644
--- a/src/arch/wasm/Mir.zig
+++ b/src/arch/wasm/Mir.zig
@@ -358,6 +358,12 @@ pub const Inst = struct {
         i64_extend16_s = 0xC3,
         /// Uses `tag`
         i64_extend32_s = 0xC4,
+        /// Contains a symbol to a memory address
+        /// Uses `label`
+        ///
+        /// Note: This uses `0xFF` as value as it is unused and not-reserved
+        /// by the wasm specification, making it safe to use
+        memory_address = 0xFF,
 
         /// From a given wasm opcode, returns a MIR tag.
         pub fn fromOpcode(opcode: std.wasm.Opcode) Tag {
diff --git a/src/link/Wasm.zig b/src/link/Wasm.zig
index c23cdc696c..c08de60694 100644
--- a/src/link/Wasm.zig
+++ b/src/link/Wasm.zig
@@ -301,10 +301,66 @@ fn finishUpdateDecl(self: *Wasm, decl: *Module.Decl, result: CodeGen.Result, cod
     // to avoid infinite loops due to earlier links
     atom.unplug();
 
-    const symbol: *Symbol = &self.symbols.items[atom.sym_index];
     if (decl.isExtern()) {
-        symbol.setUndefined(true);
+        try self.createUndefinedSymbol(decl, atom.sym_index);
+    } else {
+        try self.createDefinedSymbol(decl, atom.sym_index, atom);
+    }
+}
+
+pub fn updateDeclExports(
+    self: *Wasm,
+    module: *Module,
+    decl: *const Module.Decl,
+    exports: []const *Module.Export,
+) !void {
+    if (build_options.skip_non_native and builtin.object_format != .wasm) {
+        @panic("Attempted to compile for object format that was disabled by build configuration");
+    }
+    if (build_options.have_llvm) {
+        if (self.llvm_object) |llvm_object| return llvm_object.updateDeclExports(module, decl, exports);
+    }
+}
+
+pub fn freeDecl(self: *Wasm, decl: *Module.Decl) void {
+    if (build_options.have_llvm) {
+        if (self.llvm_object) |llvm_object| return llvm_object.freeDecl(decl);
+    }
+
+    const atom = &decl.link.wasm;
+
+    if (self.last_atom == atom) {
+        self.last_atom = atom.prev;
     }
+
+    atom.unplug();
+    self.symbols_free_list.append(self.base.allocator, atom.sym_index) catch {};
+    atom.deinit(self.base.allocator);
+    _ = self.decls.remove(decl);
+}
+
+fn createUndefinedSymbol(self: *Wasm, decl: *Module.Decl, symbol_index: u32) !void {
+    var symbol: *Symbol = &self.symbols.items[symbol_index];
+    symbol.name = decl.name;
+    symbol.setUndefined(true);
+    switch (decl.ty.zigTypeTag()) {
+        .Fn => {
+            symbol.index = self.imported_functions_count;
+            self.imported_functions_count += 1;
+            try self.import_symbols.append(self.base.allocator, symbol_index);
+            try self.imports.append(self.base.allocator, .{
+                .module_name = self.host_name,
+                .name = std.mem.span(decl.name),
+                .kind = .{ .function = decl.fn_link.wasm.type_index },
+            });
+        },
+        else => @panic("TODO: Implement undefined symbols for non-function declarations"),
+    }
+}
+
+/// Creates a defined symbol, as well as inserts the given `atom` into the chain
+fn createDefinedSymbol(self: *Wasm, decl: *Module.Decl, symbol_index: u32, atom: *Atom) !void {
+    const symbol: *Symbol = &self.symbols.items[symbol_index];
     symbol.name = decl.name;
     const final_index = switch (decl.ty.zigTypeTag()) {
         .Fn => result: {
@@ -371,49 +427,6 @@ fn finishUpdateDecl(self: *Wasm, decl: *Module.Decl, result: CodeGen.Result, cod
     }
 }
 
-pub fn updateDeclExports(
-    self: *Wasm,
-    module: *Module,
-    decl: *const Module.Decl,
-    exports: []const *Module.Export,
-) !void {
-    if (build_options.skip_non_native and builtin.object_format != .wasm) {
-        @panic("Attempted to compile for object format that was disabled by build configuration");
-    }
-    if (build_options.have_llvm) {
-        if (self.llvm_object) |llvm_object| return llvm_object.updateDeclExports(module, decl, exports);
-    }
-}
-
-pub fn freeDecl(self: *Wasm, decl: *Module.Decl) void {
-    if (build_options.have_llvm) {
-        if (self.llvm_object) |llvm_object| return llvm_object.freeDecl(decl);
-    }
-
-    const atom = &decl.link.wasm;
-
-    if (self.last_atom == atom) {
-        self.last_atom = atom.prev;
-    }
-
-    atom.unplug();
-    self.symbols_free_list.append(self.base.allocator, atom.sym_index) catch {};
-    atom.deinit(self.base.allocator);
-    _ = self.decls.remove(decl);
-}
-
-fn createUndefinedSymbol(self: *Wasm, decl: *Module.Decl, symbol_index: u32) !void {
-    var symbol: *Symbol = &self.symbols.items[symbol_index];
-    symbol.setUndefined(true);
-    switch (decl.ty.zigTypeTag()) {
-        .Fn => {
-            symbol.setIndex(self.imported_functions_count);
-            self.imported_functions_count += 1;
-        },
-        else => @panic("TODO: Wasm implement extern non-function types"),
-    }
-}
-
 pub fn flush(self: *Wasm, comp: *Compilation) !void {
     if (build_options.have_llvm and self.base.options.use_lld) {
         return self.linkWithLLD(comp);
@@ -442,7 +455,7 @@ pub fn flushModule(self: *Wasm, comp: *Compilation) !void {
     }
 
     // set the stack size on the global
-    self.globals.items[0].init = .{ .i32_const = @bitCast(i32, data_size + stack_size) };
+    self.globals.items[0].init.i32_const = @bitCast(i32, data_size + stack_size);
 
     // No need to rewrite the magic/version header
     try file.setEndPos(@sizeOf(@TypeOf(wasm.magic ++ wasm.version)));
@@ -515,10 +528,7 @@ pub fn flushModule(self: *Wasm, comp: *Compilation) !void {
         const header_offset = try reserveVecSectionHeader(file);
         const writer = file.writer();
         for (self.functions.items) |function| {
-            try leb.writeULEB128(
-                writer,
-                @intCast(u32, function.type_index),
-            );
+            try leb.writeULEB128(writer, function.type_index);
         }
 
         try writeVecSectionHeader(
@@ -580,7 +590,7 @@ pub fn flushModule(self: *Wasm, comp: *Compilation) !void {
         const header_offset = try reserveVecSectionHeader(file);
         const writer = file.writer();
         var count: u32 = 0;
-        var func_index: u32 = 0;
+        var func_index: u32 = self.imported_functions_count;
         for (module.decl_exports.values()) |exports| {
             for (exports) |exprt| {
                 // Export name length + name
@@ -624,8 +634,9 @@ pub fn flushModule(self: *Wasm, comp: *Compilation) !void {
     if (self.code_section_index) |code_index| {
         const header_offset = try reserveVecSectionHeader(file);
         const writer = file.writer();
-        var atom = self.atoms.get(code_index).?.getFirst();
+        var atom: *Atom = self.atoms.get(code_index).?.getFirst();
         while (true) {
+            try atom.resolveRelocs(self);
             try leb.writeULEB128(writer, atom.size);
             try writer.writeAll(atom.code.items);
 
@@ -667,6 +678,7 @@ pub fn flushModule(self: *Wasm, comp: *Compilation) !void {
             // fill in the offset table and the data segments
             var current_offset: u32 = 0;
             while (true) {
+                try atom.resolveRelocs(self);
                 std.debug.assert(current_offset == atom.offset);
                 std.debug.assert(atom.code.items.len == atom.size);
 
diff --git a/src/link/Wasm/Atom.zig b/src/link/Wasm/Atom.zig
index 948a6308e7..cc02af9239 100644
--- a/src/link/Wasm/Atom.zig
+++ b/src/link/Wasm/Atom.zig
@@ -72,6 +72,7 @@ pub fn getLast(self: *Atom) *Atom {
     while (tmp.next) |next| tmp = next;
     return tmp;
 }
+
 /// Unplugs the `Atom` from the chain
 pub fn unplug(self: *Atom) void {
     if (self.prev) |prev| {
@@ -88,18 +89,16 @@ pub fn unplug(self: *Atom) void {
 /// Resolves the relocations within the atom, writing the new value
 /// at the calculated offset.
 pub fn resolveRelocs(self: *Atom, wasm_bin: *const Wasm) !void {
-    const object = wasm_bin.objects.items[self.file];
-    const symbol: Symbol = object.symtable[self.sym_index];
-
+    const symbol: Symbol = wasm_bin.symbols.items[self.sym_index];
     log.debug("Resolving relocs in atom '{s}' count({d})", .{
         symbol.name,
         self.relocs.items.len,
     });
 
     for (self.relocs.items) |reloc| {
-        const value = self.relocationValue(reloc, wasm_bin);
-        log.debug("Relocating '{s}' referenced in '{s}' offset=0x{x:0>8} value={d}", .{
-            object.symtable[reloc.index].name,
+        const value = try relocationValue(reloc, wasm_bin);
+        log.debug("Relocating '{s}' referenced in '{s}' offset=0x{x:0>8} value={d}\n", .{
+            wasm_bin.symbols.items[reloc.index].name,
             symbol.name,
             reloc.offset,
             value,
@@ -135,21 +134,20 @@ pub fn resolveRelocs(self: *Atom, wasm_bin: *const Wasm) !void {
 /// From a given `relocation` will return the new value to be written.
 /// All values will be represented as a `u64` as all values can fit within it.
 /// The final value must be casted to the correct size.
-fn relocationValue(self: *Atom, relocation: types.Relocation, wasm_bin: *const Wasm) u64 {
-    const object = wasm_bin.objects.items[self.file];
-    const symbol: Symbol = object.symtable[relocation.index];
+fn relocationValue(relocation: types.Relocation, wasm_bin: *const Wasm) !u64 {
+    const symbol: Symbol = wasm_bin.symbols.items[relocation.index];
     return switch (relocation.relocation_type) {
-        .R_WASM_FUNCTION_INDEX_LEB => symbol.kind.function.functionIndex(),
-        .R_WASM_TABLE_NUMBER_LEB => symbol.kind.table.table.table_idx,
+        .R_WASM_FUNCTION_INDEX_LEB => symbol.index,
+        .R_WASM_TABLE_NUMBER_LEB => symbol.index,
         .R_WASM_TABLE_INDEX_I32,
         .R_WASM_TABLE_INDEX_I64,
         .R_WASM_TABLE_INDEX_SLEB,
         .R_WASM_TABLE_INDEX_SLEB64,
-        => symbol.getTableIndex() orelse 0,
-        .R_WASM_TYPE_INDEX_LEB => symbol.kind.function.func.type_idx,
+        => return error.TodoImplementTableIndex, // find table index from a function symbol
+        .R_WASM_TYPE_INDEX_LEB => wasm_bin.functions.items[symbol.index].type_index,
         .R_WASM_GLOBAL_INDEX_I32,
         .R_WASM_GLOBAL_INDEX_LEB,
-        => symbol.kind.global.global.global_idx,
+        => symbol.index,
         .R_WASM_MEMORY_ADDR_I32,
         .R_WASM_MEMORY_ADDR_I64,
         .R_WASM_MEMORY_ADDR_LEB,
@@ -157,10 +155,10 @@ fn relocationValue(self: *Atom, relocation: types.Relocation, wasm_bin: *const W
         .R_WASM_MEMORY_ADDR_SLEB,
         .R_WASM_MEMORY_ADDR_SLEB64,
         => blk: {
-            if (symbol.isUndefined() and (symbol.kind == .data or symbol.isWeak())) {
+            if (symbol.isUndefined() and (symbol.tag == .data or symbol.isWeak())) {
                 return 0;
             }
-            const segment_name = object.segment_info[symbol.index().?].outputName();
+            const segment_name = wasm_bin.segment_info.items[symbol.index].outputName();
             const atom_index = wasm_bin.data_segments.get(segment_name).?;
             var target_atom = wasm_bin.atoms.getPtr(atom_index).?.*.getFirst();
             while (true) {
@@ -170,11 +168,11 @@ fn relocationValue(self: *Atom, relocation: types.Relocation, wasm_bin: *const W
                 } else break;
             }
             const segment = wasm_bin.segments.items[atom_index];
-            const base = wasm_bin.options.global_base orelse 1024;
+            const base = wasm_bin.base.options.global_base orelse 0;
             const offset = target_atom.offset + segment.offset;
             break :blk offset + base + (relocation.addend orelse 0);
         },
-        .R_WASM_EVENT_INDEX_LEB => symbol.kind.event.index,
+        .R_WASM_EVENT_INDEX_LEB => symbol.index,
         .R_WASM_SECTION_OFFSET_I32,
         .R_WASM_FUNCTION_OFFSET_I32,
         => relocation.offset,