wasm-link: Implement indirect function table

The function table contains all function pointers that are called
by using call_indirect. During codegen, we create a relocation
where the linker will resolve the correct index into the table and stores
this value within the data section at the location of the pointer.

2 files changed, 66 insertions, 16 deletions

diff --git a/src/link/Wasm.zig b/src/link/Wasm.zig
index 9490634dc1..8933bdef9f 100644
--- a/src/link/Wasm.zig
+++ b/src/link/Wasm.zig
@@ -79,7 +79,9 @@ memories: wasm.Memory = .{ .limits = .{ .min = 0, .max = null } },
 /// Indirect function table, used to call function pointers
 /// When this is non-zero, we must emit a table entry,
 /// as well as an 'elements' section.
-function_table: std.ArrayListUnmanaged(Symbol) = .{},
+///
+/// Note: Key is symbol index, value represents the index into the table
+function_table: std.AutoHashMapUnmanaged(u32, u32) = .{},
 
 pub const Segment = struct {
     alignment: u32,
@@ -276,7 +278,7 @@ pub fn updateDecl(self: *Wasm, module: *Module, decl: *Module.Decl) !void {
     defer codegen.deinit();
 
     // generate the 'code' section for the function declaration
-    const result = codegen.gen(decl.ty, decl.val) catch |err| switch (err) {
+    const result = codegen.genDecl(decl.ty, decl.val) catch |err| switch (err) {
         error.CodegenFail => {
             decl.analysis = .codegen_failure;
             try module.failed_decls.put(module.gpa, decl, codegen.err_msg);
@@ -334,6 +336,25 @@ pub fn freeDecl(self: *Wasm, decl: *Module.Decl) void {
             else => unreachable,
         }
     }
+
+    // maybe remove from function table if needed
+    if (decl.ty.zigTypeTag() == .Fn) {
+        _ = self.function_table.remove(atom.sym_index);
+    }
+}
+
+/// Appends a new entry to the indirect function table
+pub fn addTableFunction(self: *Wasm, symbol_index: u32) !void {
+    const index = @intCast(u32, self.function_table.count());
+    try self.function_table.put(self.base.allocator, symbol_index, index);
+}
+
+fn mapFunctionTable(self: *Wasm) void {
+    var it = self.function_table.valueIterator();
+    var index: u32 = 0;
+    while (it.next()) |value_ptr| : (index += 1) {
+        value_ptr.* = index;
+    }
 }
 
 fn addOrUpdateImport(self: *Wasm, decl: *Module.Decl) !void {
@@ -583,6 +604,7 @@ pub fn flushModule(self: *Wasm, comp: *Compilation) !void {
 
     try self.setupMemory();
     try self.allocateAtoms();
+    self.mapFunctionTable();
 
     const file = self.base.file.?;
     const header_size = 5 + 1;
@@ -662,6 +684,22 @@ pub fn flushModule(self: *Wasm, comp: *Compilation) !void {
         );
     }
 
+    if (self.function_table.count() > 0) {
+        const header_offset = try reserveVecSectionHeader(file);
+        const writer = file.writer();
+
+        try leb.writeULEB128(writer, wasm.reftype(.funcref));
+        try emitLimits(writer, .{ .min = 1, .max = null });
+
+        try writeVecSectionHeader(
+            file,
+            header_offset,
+            .table,
+            @intCast(u32, (try file.getPos()) - header_offset - header_size),
+            @as(u32, 1),
+        );
+    }
+
     // Memory section
     if (!self.base.options.import_memory) {
         const header_offset = try reserveVecSectionHeader(file);
@@ -743,6 +781,31 @@ pub fn flushModule(self: *Wasm, comp: *Compilation) !void {
         );
     }
 
+    // element section (function table)
+    if (self.function_table.count() > 0) {
+        const header_offset = try reserveVecSectionHeader(file);
+        const writer = file.writer();
+
+        var flags: u32 = 0x2; // Yes we have a table
+        try leb.writeULEB128(writer, flags);
+        try leb.writeULEB128(writer, @as(u32, 0)); // index of that table. TODO: Store synthetic symbols
+        try emitInit(writer, .{ .i32_const = 0 });
+        try leb.writeULEB128(writer, @as(u8, 0));
+        try leb.writeULEB128(writer, @intCast(u32, self.function_table.count()));
+        var symbol_it = self.function_table.keyIterator();
+        while (symbol_it.next()) |symbol_index_ptr| {
+            try leb.writeULEB128(writer, self.symbols.items[symbol_index_ptr.*].index);
+        }
+
+        try writeVecSectionHeader(
+            file,
+            header_offset,
+            .element,
+            @intCast(u32, (try file.getPos()) - header_offset - header_size),
+            @as(u32, 1),
+        );
+    }
+
     // Code section
     if (self.code_section_index) |code_index| {
         const header_offset = try reserveVecSectionHeader(file);
@@ -1233,16 +1296,3 @@ pub fn putOrGetFuncType(self: *Wasm, func_type: wasm.Type) !u32 {
     });
     return index;
 }
-
-/// From a given index and an `ExternalKind`, finds the corresponding Import.
-/// This is due to indexes for imports being unique per type, rather than across all imports.
-fn findImport(self: Wasm, index: u32, external_type: wasm.ExternalKind) ?*wasm.Import {
-    var current_index: u32 = 0;
-    for (self.imports.items) |*import| {
-        if (import.kind == external_type) {
-            if (current_index == index) return import;
-            current_index += 1;
-        }
-    }
-    return null;
-}
diff --git a/src/link/Wasm/Atom.zig b/src/link/Wasm/Atom.zig
index ec336718cc..7f49e069b1 100644
--- a/src/link/Wasm/Atom.zig
+++ b/src/link/Wasm/Atom.zig
@@ -129,7 +129,7 @@ fn relocationValue(relocation: types.Relocation, wasm_bin: *const Wasm) !u64 {
         .R_WASM_TABLE_INDEX_I64,
         .R_WASM_TABLE_INDEX_SLEB,
         .R_WASM_TABLE_INDEX_SLEB64,
-        => return error.TodoImplementTableIndex, // find table index from a function symbol
+        => return wasm_bin.function_table.get(relocation.index) orelse 0,
         .R_WASM_TYPE_INDEX_LEB => wasm_bin.functions.items[symbol.index].type_index,
         .R_WASM_GLOBAL_INDEX_I32,
         .R_WASM_GLOBAL_INDEX_LEB,