Add WASM code gen for call instruction with no args

16 files changed, 261 insertions, 54 deletions

diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/WasmCodeGen.java b/src/main/java/org/shedlang/compiler/backends/wasm/WasmCodeGen.java
index 6ab555a7..3d466648 100644
--- a/src/main/java/org/shedlang/compiler/backends/wasm/WasmCodeGen.java
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/WasmCodeGen.java
@@ -3,14 +3,23 @@ package org.shedlang.compiler.backends.wasm;
 import org.shedlang.compiler.backends.wasm.structure.ast.instructions.*;
 import org.shedlang.compiler.stackir.instructions.*;
 
+import java.util.List;
+import java.util.Map;
+
 public class WasmCodeGen {
     private WasmCodeGen() {
     }
 
     public static WasmCodeGenContext generateInstruction(Instruction instruction, WasmCodeGenContext context) {
         return switch (instruction) {
-            case CallInstruction callInstruction -> {
-                throw new UnsupportedOperationException("TODO");
+            case CallInstruction call -> {
+                var receiverResult = context.generateLocal(WasmCodeGenLocalSpace.RECEIVER);
+                var receiver = receiverResult.value();
+                context = receiverResult.context();
+
+                context = context.addInstruction(new WasmLocalSet(receiver));
+
+                yield WasmCodeGenClosures.call(receiver, List.of(), Map.of(), context);
             }
             case DefineFunctionInstruction defineFunctionInstruction -> {
                 throw new UnsupportedOperationException("TODO");
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/WasmCodeGenClosures.java b/src/main/java/org/shedlang/compiler/backends/wasm/WasmCodeGenClosures.java
new file mode 100644
index 00000000..86ae472d
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/WasmCodeGenClosures.java
@@ -0,0 +1,44 @@
+package org.shedlang.compiler.backends.wasm;
+
+import org.shedlang.compiler.backends.wasm.structure.ast.instructions.WasmCallIndirect;
+import org.shedlang.compiler.backends.wasm.structure.ast.instructions.WasmI32Load;
+import org.shedlang.compiler.backends.wasm.structure.ast.instructions.WasmLocalGet;
+import org.shedlang.compiler.backends.wasm.structure.ast.instructions.WasmMemoryArg;
+import org.shedlang.compiler.backends.wasm.structure.ast.modules.WasmAlignment;
+import org.shedlang.compiler.backends.wasm.structure.ast.modules.WasmLocalIndex;
+import org.shedlang.compiler.backends.wasm.structure.ast.types.WasmFuncType;
+import org.shedlang.compiler.backends.wasm.structure.ast.types.WasmValueType;
+
+import java.util.List;
+import java.util.Map;
+
+public class WasmCodeGenClosures {
+    private WasmCodeGenClosures() {
+    }
+
+    private static final WasmValueType CLOSURE_TYPE = WasmValueType.I32;
+
+    public static WasmCodeGenContext call(
+        WasmLocalIndex closure,
+        List<WasmLocalIndex> positionalArgs,
+        Map<String, WasmLocalIndex> namedArgsByName,
+        WasmCodeGenContext context
+    ) {
+        context = loadClosureFunctionTableIndex(closure, context);
+
+        var funcType = new WasmFuncType(List.of(CLOSURE_TYPE), List.of(WasmCodeGenTypes.VALUE_TYPE));
+        return context
+            .addInstruction(new WasmLocalGet(closure))
+            .addType(funcType)
+            .addInstruction(new WasmCallIndirect(context.indirectFunctionTableIndex(), funcType));
+    }
+
+    private static WasmCodeGenContext loadClosureFunctionTableIndex(
+        WasmLocalIndex closure,
+        WasmCodeGenContext context
+    ) {
+        return context
+            .addInstruction(new WasmLocalGet(closure))
+            .addInstruction(new WasmI32Load(new WasmMemoryArg(0, WasmAlignment.ALIGN_32_BIT)));
+    }
+}
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/WasmCodeGenContext.java b/src/main/java/org/shedlang/compiler/backends/wasm/WasmCodeGenContext.java
index 7dfb13c2..37396d2f 100644
--- a/src/main/java/org/shedlang/compiler/backends/wasm/WasmCodeGenContext.java
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/WasmCodeGenContext.java
@@ -1,19 +1,18 @@
 package org.shedlang.compiler.backends.wasm;
 
-import org.pcollections.Empty;
-import org.pcollections.OrderedPMap;
-import org.pcollections.PMap;
-import org.pcollections.PVector;
+import org.pcollections.*;
 import org.shedlang.compiler.backends.llvm.NameAllocator;
 import org.shedlang.compiler.backends.wasm.structure.ast.instructions.WasmExpression;
 import org.shedlang.compiler.backends.wasm.structure.ast.instructions.WasmInstruction;
 import org.shedlang.compiler.backends.wasm.structure.ast.linking.WasmMemoryAddress;
 import org.shedlang.compiler.backends.wasm.structure.ast.modules.*;
+import org.shedlang.compiler.backends.wasm.structure.ast.types.*;
 
 import java.util.List;
 import java.util.Optional;
 
 public record WasmCodeGenContext(
+    OrderedPSet<WasmFuncType> types,
     PVector<WasmFunction> functions,
     WasmMemoryBuilder memory,
     PVector<WasmInstruction> instructions,
@@ -21,6 +20,7 @@ public record WasmCodeGenContext(
     PMap<String, WasmLocalIndex> shedLocalNameToLocalIndex
 ) {
     public static final WasmCodeGenContext EMPTY = new WasmCodeGenContext(
+        OrderedPSet.empty(),
         Empty.vector(),
         WasmMemoryBuilder.EMPTY,
         Empty.vector(),
@@ -28,6 +28,17 @@ public record WasmCodeGenContext(
         Empty.map()
     );
 
+    public WasmCodeGenContext addType(WasmFuncType funcType) {
+        return new WasmCodeGenContext(
+            types.plus(funcType),
+            functions,
+            memory,
+            instructions,
+            locals,
+            shedLocalNameToLocalIndex
+        );
+    }
+
     public WasmCodeGenResult<WasmMemoryAddress> addData(
         WasmCodeGenGlobalSpace space,
         byte[] data,
@@ -36,6 +47,7 @@ public record WasmCodeGenContext(
         var result = memory.add(space, data, alignment);
 
         return new WasmCodeGenContext(
+            types,
             functions,
             result.memory(),
             instructions,
@@ -46,6 +58,7 @@ public record WasmCodeGenContext(
 
     public WasmCodeGenContext addInstruction(WasmInstruction instruction) {
         return new WasmCodeGenContext(
+            types,
             functions,
             memory,
             instructions.plus(instruction),
@@ -63,6 +76,7 @@ public record WasmCodeGenContext(
             new WasmExpression(instructions)
         );
         return new WasmCodeGenContext(
+            types.plus(function.type()),
             functions.plus(function),
             memory,
             Empty.vector(),
@@ -74,6 +88,20 @@ public record WasmCodeGenContext(
     public WasmModule toModule() {
         var module = WasmModule.EMPTY;
 
+        module = module.addImport(new WasmImport(
+            "env",
+            "__indirect_function_table",
+            new WasmImportDescriptor.Table(new WasmTableType(
+                WasmReferenceType.FUNC_REF,
+                // TODO: set size according to number of entries
+                WasmLimits.min(0)
+            ))
+        ));
+
+        for (var type : types) {
+            module = module.addType(type);
+        }
+
         for (var function : functions) {
             module = module.addFunction(function);
         }
@@ -87,6 +115,7 @@ public record WasmCodeGenContext(
         var context = localIndexResult.context();
 
         return new WasmCodeGenContext(
+            context.types,
             context.functions,
             context.memory,
             context.instructions,
@@ -105,14 +134,23 @@ public record WasmCodeGenContext(
         }
     }
 
+    public WasmCodeGenResult<WasmLocalIndex> generateLocal(WasmCodeGenLocalSpace space) {
+        return generateLocal(space, Optional.empty());
+    }
+
     public WasmCodeGenResult<WasmLocalIndex> generateLocal(WasmCodeGenLocalSpace space, String name) {
+        return generateLocal(space, Optional.of(name));
+    }
+
+    private WasmCodeGenResult<WasmLocalIndex> generateLocal(WasmCodeGenLocalSpace space, Optional<String> name) {
         var localIndex = new WasmLocalIndex(locals.size());
         var localName = NameAllocator.generateName(
             x -> locals.containsKey(x),
             space,
-            Optional.of(name)
+            name
         );
         return new WasmCodeGenContext(
+            types,
             functions,
             memory,
             instructions,
@@ -121,6 +159,10 @@ public record WasmCodeGenContext(
         ).toResult(localIndex);
     }
 
+    public WasmTableIndex indirectFunctionTableIndex() {
+        return new WasmTableIndex(0);
+    }
+
     public <T> WasmCodeGenResult<T> toResult(T value) {
         return new WasmCodeGenResult<>(value, this);
     }
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/WasmCodeGenLocalSpace.java b/src/main/java/org/shedlang/compiler/backends/wasm/WasmCodeGenLocalSpace.java
index 196a5304..80e89155 100644
--- a/src/main/java/org/shedlang/compiler/backends/wasm/WasmCodeGenLocalSpace.java
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/WasmCodeGenLocalSpace.java
@@ -1,7 +1,8 @@
 package org.shedlang.compiler.backends.wasm;
 
 public enum WasmCodeGenLocalSpace {
-    LOCAL("local");
+    LOCAL("local"),
+    RECEIVER("receiver");
 
     private final String name;
 
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/WasmMemoryBuilder.java b/src/main/java/org/shedlang/compiler/backends/wasm/WasmMemoryBuilder.java
index 76a234d7..21568dfc 100644
--- a/src/main/java/org/shedlang/compiler/backends/wasm/WasmMemoryBuilder.java
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/WasmMemoryBuilder.java
@@ -7,10 +7,7 @@ import org.shedlang.compiler.backends.wasm.structure.ast.instructions.WasmI32Con
 import org.shedlang.compiler.backends.wasm.structure.ast.linking.WasmDataSegmentIndex;
 import org.shedlang.compiler.backends.wasm.structure.ast.linking.WasmDataSymbol;
 import org.shedlang.compiler.backends.wasm.structure.ast.linking.WasmMemoryAddress;
-import org.shedlang.compiler.backends.wasm.structure.ast.modules.WasmAlignment;
-import org.shedlang.compiler.backends.wasm.structure.ast.modules.WasmDataSegment;
-import org.shedlang.compiler.backends.wasm.structure.ast.modules.WasmMemory;
-import org.shedlang.compiler.backends.wasm.structure.ast.modules.WasmModule;
+import org.shedlang.compiler.backends.wasm.structure.ast.modules.*;
 import org.shedlang.compiler.backends.wasm.structure.ast.types.WasmLimits;
 import org.shedlang.compiler.backends.wasm.structure.ast.types.WasmMemoryType;
 
@@ -32,6 +29,13 @@ public class WasmMemoryBuilder {
     }
 
     public WasmModule toModule(WasmModule module) {
+        module = module
+            .addImport(new WasmImport(
+                "env",
+                "__linear_memory",
+                new WasmImportDescriptor.Memory(new WasmMemoryType(WasmLimits.min(size)))
+            ));
+
         if (entities.size() > 0) {
             var data = ByteBuffer.allocate(size);
 
@@ -42,7 +46,6 @@ public class WasmMemoryBuilder {
             // TODO: we assume that we're in complete control of memory and data segments.
             // Either remove this assumption or document it properly.
             module = module
-                .addMemory(new WasmMemory(new WasmMemoryType(WasmLimits.min(size))))
                 .addDataSegment(new WasmDataSegment(
                     ".data",
                     data.array(),
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/structure/ast/instructions/WasmCallIndirect.java b/src/main/java/org/shedlang/compiler/backends/wasm/structure/ast/instructions/WasmCallIndirect.java
new file mode 100644
index 00000000..716aa04c
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/structure/ast/instructions/WasmCallIndirect.java
@@ -0,0 +1,10 @@
+package org.shedlang.compiler.backends.wasm.structure.ast.instructions;
+
+import org.shedlang.compiler.backends.wasm.structure.ast.modules.WasmTableIndex;
+import org.shedlang.compiler.backends.wasm.structure.ast.types.WasmFuncType;
+
+public record WasmCallIndirect(
+    WasmTableIndex tableIndex,
+    WasmFuncType funcType
+) implements WasmInstruction {
+}
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/structure/ast/instructions/WasmI32Load.java b/src/main/java/org/shedlang/compiler/backends/wasm/structure/ast/instructions/WasmI32Load.java
new file mode 100644
index 00000000..1cb70fd5
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/structure/ast/instructions/WasmI32Load.java
@@ -0,0 +1,4 @@
+package org.shedlang.compiler.backends.wasm.structure.ast.instructions;
+
+public record WasmI32Load(WasmMemoryArg memoryArg) implements WasmInstruction {
+}
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/structure/ast/instructions/WasmInstruction.java b/src/main/java/org/shedlang/compiler/backends/wasm/structure/ast/instructions/WasmInstruction.java
index bc70f9c2..65b4b672 100644
--- a/src/main/java/org/shedlang/compiler/backends/wasm/structure/ast/instructions/WasmInstruction.java
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/structure/ast/instructions/WasmInstruction.java
@@ -1,4 +1,4 @@
 package org.shedlang.compiler.backends.wasm.structure.ast.instructions;
 
-public sealed interface WasmInstruction permits WasmDrop, WasmI32Const, WasmI64Const, WasmLocalGet, WasmLocalSet, WasmMemoryAddressConst, WasmReturn {
+public sealed interface WasmInstruction permits WasmCallIndirect, WasmDrop, WasmI32Const, WasmI32Load, WasmI64Const, WasmLocalGet, WasmLocalSet, WasmMemoryAddressConst, WasmReturn {
 }
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/structure/ast/instructions/WasmMemoryArg.java b/src/main/java/org/shedlang/compiler/backends/wasm/structure/ast/instructions/WasmMemoryArg.java
new file mode 100644
index 00000000..752bbc35
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/structure/ast/instructions/WasmMemoryArg.java
@@ -0,0 +1,6 @@
+package org.shedlang.compiler.backends.wasm.structure.ast.instructions;
+
+import org.shedlang.compiler.backends.wasm.structure.ast.modules.WasmAlignment;
+
+public record WasmMemoryArg(int offset, WasmAlignment alignment) {
+}
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/structure/ast/linking/WasmRelocatableIndex.java b/src/main/java/org/shedlang/compiler/backends/wasm/structure/ast/linking/WasmRelocatableIndex.java
new file mode 100644
index 00000000..3801bf59
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/structure/ast/linking/WasmRelocatableIndex.java
@@ -0,0 +1,8 @@
+package org.shedlang.compiler.backends.wasm.structure.ast.linking;
+
+import org.shedlang.compiler.backends.wasm.structure.ast.types.WasmFuncType;
+
+public sealed interface WasmRelocatableIndex {
+    record MemoryAddress(WasmMemoryAddress address) implements WasmRelocatableIndex {}
+    record TypeIndex(WasmFuncType funcType) implements WasmRelocatableIndex {}
+}
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/structure/ast/modules/WasmTableIndex.java b/src/main/java/org/shedlang/compiler/backends/wasm/structure/ast/modules/WasmTableIndex.java
new file mode 100644
index 00000000..ac78b9eb
--- /dev/null
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/structure/ast/modules/WasmTableIndex.java
@@ -0,0 +1,4 @@
+package org.shedlang.compiler.backends.wasm.structure.ast.modules;
+
+public record WasmTableIndex(int value) {
+}
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatInstructions.java b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatInstructions.java
index af9f5db8..895be551 100644
--- a/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatInstructions.java
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatInstructions.java
@@ -1,6 +1,7 @@
 package org.shedlang.compiler.backends.wasm.structure.binary;
 
 import org.shedlang.compiler.backends.wasm.structure.ast.instructions.*;
+import org.shedlang.compiler.backends.wasm.structure.ast.modules.WasmAlignment;
 
 import java.io.IOException;
 
@@ -15,7 +16,7 @@ public class WasmBinaryFormatInstructions {
     private static void writeInstruction(
         WasmInstruction instruction,
         WasmBinaryWriter writer
-    ) {
+    ) throws IOException {
         switch (instruction) {
 
             // == Control Instructions ==
@@ -24,6 +25,14 @@ public class WasmBinaryFormatInstructions {
                 writer.writeByte(0x0f);
             }
 
+            case WasmCallIndirect callIndirect -> {
+                writer.writeByte(0x11);
+                writer.writeTypeIndex(callIndirect.funcType(), writer);
+                // TODO: the table index corresponds to the import in the context.
+                // Make this
+                writer.writeUnsignedInt32(0); // Table index
+            }
+
             // == Parametric Instructions ==
 
             case WasmDrop ignored -> {
@@ -42,6 +51,13 @@ public class WasmBinaryFormatInstructions {
                 writeLocalIndex(localSet.localIndex(), writer);
             }
 
+            // == Memory Instructions ==
+
+            case WasmI32Load i32Load -> {
+                writer.writeByte(0x28);
+                writeMemoryArg(i32Load.memoryArg(), writer);
+            }
+
             // == Numeric Instructions ==
 
             case WasmI32Const i32Const -> {
@@ -57,11 +73,22 @@ public class WasmBinaryFormatInstructions {
 
             case WasmMemoryAddressConst memoryAddressConst -> {
                 writer.writeByte(0x41);
-                writer.writeMemoryAddressSignedInt32(memoryAddressConst.address());
+                writer.writeMemoryAddressConst(memoryAddressConst.address());
             }
         }
     }
 
+    // == Memory Instructions ==
+
+    private static void writeMemoryArg(WasmMemoryArg memoryArg, WasmBinaryWriter writer) {
+        writeAlignment(memoryArg.alignment(), writer);
+        writer.writeUnsignedInt32(memoryArg.offset());
+    }
+
+    static void writeAlignment(WasmAlignment alignment, WasmBinaryWriter writer) {
+        writer.writeUnsignedInt32(alignment.alignment());
+    }
+
     // == Expressions ==
 
     static void writeExpression(
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatLinking.java b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatLinking.java
index 0f8aa696..fb5ea132 100644
--- a/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatLinking.java
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryFormatLinking.java
@@ -1,14 +1,18 @@
 package org.shedlang.compiler.backends.wasm.structure.binary;
 
 import org.shedlang.compiler.backends.wasm.structure.ast.linking.*;
-import org.shedlang.compiler.backends.wasm.structure.ast.modules.WasmAlignment;
 import org.shedlang.compiler.backends.wasm.structure.ast.modules.WasmFuncIndex;
 import org.shedlang.compiler.backends.wasm.structure.ast.modules.WasmGlobalIndex;
 import org.shedlang.compiler.backends.wasm.structure.ast.modules.WasmModule;
+import org.shedlang.compiler.backends.wasm.structure.ast.modules.WasmTypeIndex;
+import org.shedlang.compiler.backends.wasm.structure.ast.types.WasmFuncType;
 
 import java.io.IOException;
 import java.util.*;
+import java.util.stream.Collectors;
+import java.util.stream.IntStream;
 
+import static org.shedlang.compiler.backends.wasm.structure.binary.WasmBinaryFormatInstructions.writeAlignment;
 import static org.shedlang.compiler.backends.wasm.structure.binary.WasmBinaryFormatModules.*;
 
 public class WasmBinaryFormatLinking {
@@ -64,14 +68,21 @@ public class WasmBinaryFormatLinking {
         SymbolTable symbolTable,
         WasmBinaryWriter writer
     ) {
-        var symbolIndex = symbolTable.memoryAddressToSymbolIndex(relocationEntry.index());
+        var index = switch (relocationEntry.index()) {
+            case WasmRelocatableIndex.MemoryAddress memoryAddress ->
+                symbolTable.memoryAddressToSymbolIndex(memoryAddress.address()).value();
+
+            case WasmRelocatableIndex.TypeIndex typeIndex ->
+                symbolTable.funcTypeToTypeIndex(typeIndex.funcType()).value();
+        };
 
         writer.writeByte(relocationEntry.type().id());
         writer.writeUnsignedInt32(relocationEntry.sectionContentsOffset());
-        writer.writeUnsignedInt32(symbolIndex.value());
+        writer.writeUnsignedInt32(index);
 
-        // TODO: handle types without addends
-        writer.writeSignedInt32(0);
+        if (relocationEntry.type().hasAddend()) {
+            writer.writeSignedInt32(0);
+        }
     }
 
     // == Linking Metadata Section ==
@@ -217,15 +228,18 @@ public class WasmBinaryFormatLinking {
         private final List<SymbolInfo> symbolInfos;
         private final int functionSymbolIndexOffset;
         private final Map<WasmMemoryAddress, WasmSymbolIndex> memoryAddressToSymbolIndex;
+        private final Map<WasmFuncType, WasmTypeIndex> funcTypeToTypeIndex;
 
         public SymbolTable(
             List<SymbolInfo> symbolInfos,
             int functionSymbolIndexOffset,
-            Map<WasmMemoryAddress, WasmSymbolIndex> memoryAddressToSymbolIndex
+            Map<WasmMemoryAddress, WasmSymbolIndex> memoryAddressToSymbolIndex,
+            Map<WasmFuncType, WasmTypeIndex> funcTypeToTypeIndex
         ) {
             this.symbolInfos = symbolInfos;
             this.functionSymbolIndexOffset = functionSymbolIndexOffset;
             this.memoryAddressToSymbolIndex = memoryAddressToSymbolIndex;
+            this.funcTypeToTypeIndex = funcTypeToTypeIndex;
         }
 
         public WasmSymbolIndex funcIndexToSymbolIndex(WasmFuncIndex funcIndex) {
@@ -240,7 +254,16 @@ public class WasmBinaryFormatLinking {
             } else {
                 return symbolIndex;
             }
+        }
 
+        public WasmTypeIndex funcTypeToTypeIndex(WasmFuncType funcType) {
+            var typeIndex = funcTypeToTypeIndex.get(funcType);
+            if (typeIndex == null) {
+                // TODO: better error
+                throw new RuntimeException("could not find index for type: " + funcType);
+            } else {
+                return typeIndex;
+            }
         }
     }
     
@@ -292,10 +315,19 @@ public class WasmBinaryFormatLinking {
             symbolInfos.add(symbolInfo);
         }
 
+        var funcTypes = module.types().stream().toList();
+        var funcTypeToTypeIndex = IntStream.range(0, funcTypes.size())
+            .boxed()
+            .collect(Collectors.toMap(
+                typeIndex -> funcTypes.get(typeIndex),
+                typeIndex -> new WasmTypeIndex(typeIndex)
+            ));
+
         return new SymbolTable(
             symbolInfos,
             functionSymbolIndexOffset,
-            memoryAddressToSymbolIndex
+            memoryAddressToSymbolIndex,
+            funcTypeToTypeIndex
         );
     }
 
@@ -347,8 +379,4 @@ public class WasmBinaryFormatLinking {
     private static void writeSymbolIndex(WasmSymbolIndex symbolIndex, WasmBinaryWriter writer) {
         writer.writeUnsignedInt32(symbolIndex.value());
     }
-
-    private static void writeAlignment(WasmAlignment alignment, WasmBinaryWriter writer) {
-        writer.writeUnsignedInt32(alignment.alignment());
-    }
 }
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryWriter.java b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryWriter.java
index 8617976b..14b47e64 100644
--- a/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryWriter.java
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmBinaryWriter.java
@@ -2,6 +2,8 @@ package org.shedlang.compiler.backends.wasm.structure.binary;
 
 import org.shedlang.compiler.backends.wasm.structure.BinaryWriter;
 import org.shedlang.compiler.backends.wasm.structure.ast.linking.WasmMemoryAddress;
+import org.shedlang.compiler.backends.wasm.structure.ast.linking.WasmRelocatableIndex;
+import org.shedlang.compiler.backends.wasm.structure.ast.types.WasmFuncType;
 
 import java.io.IOException;
 import java.util.*;
@@ -44,18 +46,31 @@ public class WasmBinaryWriter {
         WasmBinaryFormatValues.writeString(value, writer);
     }
 
-    public void writeMemoryAddressSignedInt32(WasmMemoryAddress index) {
-        writeRelocatableSignedInt32(
+    public void writeMemoryAddressConst(WasmMemoryAddress index) throws IOException {
+        writeRelocatableIndex(
             WasmRelocationType.MEMORY_ADDR_SLEB,
-            index
+            () -> writePaddedSignedInt32(0),
+            new WasmRelocatableIndex.MemoryAddress(index)
         );
     }
 
-    private void writeRelocatableSignedInt32(WasmRelocationType relocationType, WasmMemoryAddress index) {
+    public void writeTypeIndex(WasmFuncType funcType, WasmBinaryWriter writer) throws IOException {
+        writeRelocatableIndex(
+            WasmRelocationType.TYPE_INDEX_LEB,
+            () -> writePaddedUnsignedInt32(0),
+            new WasmRelocatableIndex.TypeIndex(funcType)
+        );
+    }
+
+    private void writeRelocatableIndex(
+        WasmRelocationType relocationType,
+        WasmBinaryFormatModules.Write writePlaceholder,
+        WasmRelocatableIndex index
+    ) throws IOException {
         // TODO: handle relocatable values in non-CODE sections
 
         var sectionContentsOffset = writer.position() - sectionContentsStart;
-        writePaddedSignedInt32(0);
+        writePlaceholder.write();
 
         if (!relocationEntries.containsKey(sectionIndex)) {
             relocationEntries.put(sectionIndex, new ArrayList<>());
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmRelocationEntry.java b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmRelocationEntry.java
index 287907a3..7e02821b 100644
--- a/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmRelocationEntry.java
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmRelocationEntry.java
@@ -1,11 +1,11 @@
 package org.shedlang.compiler.backends.wasm.structure.binary;
 
-import org.shedlang.compiler.backends.wasm.structure.ast.linking.WasmMemoryAddress;
+import org.shedlang.compiler.backends.wasm.structure.ast.linking.WasmRelocatableIndex;
 
 public record WasmRelocationEntry(
     int sectionIndex,
     WasmRelocationType type,
     int sectionContentsOffset,
-    WasmMemoryAddress index
+    WasmRelocatableIndex index
 ) {
 }
diff --git a/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmRelocationType.java b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmRelocationType.java
index 1ae3b3dc..1b76028b 100644
--- a/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmRelocationType.java
+++ b/src/main/java/org/shedlang/compiler/backends/wasm/structure/binary/WasmRelocationType.java
@@ -1,32 +1,34 @@
 package org.shedlang.compiler.backends.wasm.structure.binary;
 
 public enum WasmRelocationType {
-    FUNCTION_INDEX_LEB(0, false),
-    TABLE_INDEX_SLEB(1, true),
-    TABLE_INDEX_I32(2, true),
-    MEMORY_ADDR_LEB(3, false),
-    MEMORY_ADDR_SLEB(4, true),
-    MEMORY_ADDR_I32(5, true),
-    TYPE_INDEX_LEB(6, false),
-    GLOBAL_INDEX_LEB(7, false),
-    FUNCTION_OFFSET_I32(8, true),
-    SECTION_OFFSET_I32(9, true),
-    TAG_INDEX_LEB(10, false),
-    GLOBAL_INDEX_I32(13, true),
-    MEMORY_ADDR_LEB64(14, false),
-    MEMORY_ADDR_SLEB64(15, true),
-    MEMORY_ADDR_I64(16, true),
-    MEMORY_ADDR_REL_SLEB64(17, true),
-    TABLE_INDEX_SLEB64(18, true),
-    TABLE_INDEX_I64(19, true),
-    TABLE_NUMBER_LEB(20, false);
+    FUNCTION_INDEX_LEB(0, false, false),
+    TABLE_INDEX_SLEB(1, true, false),
+    TABLE_INDEX_I32(2, true, false),
+    MEMORY_ADDR_LEB(3, false, true),
+    MEMORY_ADDR_SLEB(4, true, true),
+    MEMORY_ADDR_I32(5, true, true),
+    TYPE_INDEX_LEB(6, false, false),
+    GLOBAL_INDEX_LEB(7, false, false),
+    FUNCTION_OFFSET_I32(8, true, true),
+    SECTION_OFFSET_I32(9, true, true),
+    TAG_INDEX_LEB(10, false, false),
+    GLOBAL_INDEX_I32(13, true, false),
+    MEMORY_ADDR_LEB64(14, false, true),
+    MEMORY_ADDR_SLEB64(15, true, true),
+    MEMORY_ADDR_I64(16, true, true),
+    MEMORY_ADDR_REL_SLEB64(17, true, true),
+    TABLE_INDEX_SLEB64(18, true, false),
+    TABLE_INDEX_I64(19, true, false),
+    TABLE_NUMBER_LEB(20, false, false);
 
     private final byte id;
     private final boolean isSigned;
+    private final boolean hasAddend;
 
-    WasmRelocationType(int id, boolean isSigned) {
+    WasmRelocationType(int id, boolean isSigned, boolean hasAddend) {
         this.id = (byte) id;
         this.isSigned = isSigned;
+        this.hasAddend = hasAddend;
     }
 
     public byte id() {
@@ -36,4 +38,8 @@ public enum WasmRelocationType {
     public boolean isSigned() {
         return isSigned;
     }
+
+    public boolean hasAddend() {
+        return hasAddend;
+    }
 }