Support true example in llvm-patio backend

3 files changed, 661 insertions, 39 deletions

diff --git a/src/main/java/org/shedlang/compiler/backends/llvm/LlvmCodeGenLocalVariableSpace.java b/src/main/java/org/shedlang/compiler/backends/llvm/LlvmCodeGenLocalVariableSpace.java
index 1d893ff0..a8149228 100644
--- a/src/main/java/org/shedlang/compiler/backends/llvm/LlvmCodeGenLocalVariableSpace.java
+++ b/src/main/java/org/shedlang/compiler/backends/llvm/LlvmCodeGenLocalVariableSpace.java
@@ -14,6 +14,7 @@ public enum LlvmCodeGenLocalVariableSpace {
     IF_END("ifEnd"),
     IF_FALSE("ifFalse"),
     IF_TRUE("ifTrue"),
+    LOCAL("local"),
     NAMESPACE("namespace"),
     NAMESPACE_STRUCT_POINTER("namespaceStructPointer"),
     PARAM("param"),
diff --git a/src/main/java/org/shedlang/compiler/backends/llvm/LlvmPatioCodeGen.java b/src/main/java/org/shedlang/compiler/backends/llvm/LlvmPatioCodeGen.java
index cc1dfeff..bbf7bb41 100644
--- a/src/main/java/org/shedlang/compiler/backends/llvm/LlvmPatioCodeGen.java
+++ b/src/main/java/org/shedlang/compiler/backends/llvm/LlvmPatioCodeGen.java
@@ -1,11 +1,16 @@
 package org.shedlang.compiler.backends.llvm;
 
+import org.pcollections.PMap;
 import org.pcollections.PVector;
+import org.pcollections.TreePVector;
 import org.shedlang.compiler.backends.llvm.ir.ast.*;
+import org.shedlang.compiler.backends.llvm.ir.ast.instructions.*;
 import org.shedlang.compiler.backends.llvm.ir.ast.operands.*;
 import org.shedlang.compiler.backends.llvm.ir.ast.types.LlvmType;
 import org.shedlang.compiler.backends.llvm.ir.ast.types.LlvmTypes;
 import org.shedlang.compiler.patio.ast.*;
+import org.shedlang.compiler.patio.ast.instructions.*;
+import org.shedlang.compiler.patio.ast.operands.*;
 import org.shedlang.compiler.patio.ast.types.*;
 import org.shedlang.compiler.util.Lists;
 import org.shedlang.compiler.util.P;
@@ -15,18 +20,45 @@ import java.util.Optional;
 
 public class LlvmPatioCodeGen {
     public static LlvmModule generateCompilationUnit(PatioCompilationUnit patioCompilationUnit) {
-        var context = Context.EMPTY;
+        var context = ModuleContext.EMPTY;
+
+        for (var patioCompilationUnitElement : patioCompilationUnit.elements()) {
+            switch (patioCompilationUnitElement) {
+                case PatioDataElementImmutable patioDataElementImmutable -> {
+                }
+                case PatioDataElementMutable patioDataElementMutable -> {
+                }
+                case PatioFunctionDeclaration patioFunctionDeclaration -> {
+                    context = context.addFunctionNameToReturnType(
+                        patioFunctionDeclaration.name(),
+                        patioTypeToLlvmType(patioFunctionDeclaration.returnType())
+                    );
+                }
+                case PatioFunctionDefinition patioFunctionDefinition -> {
+                    context = context.addFunctionNameToReturnType(
+                        patioFunctionDefinition.name(),
+                        patioTypeToLlvmType(patioFunctionDefinition.returnType())
+                    );
+                }
+            }
+        }
 
         for (var patioCompilationUnitElement : patioCompilationUnit.elements()) {
             context = generateCompilationUnitElement(patioCompilationUnitElement, context);
         }
 
+        context = context.addTopLevelEntity(new LlvmFunctionDeclaration(
+            "shed__runtime__alloc",
+            LlvmTypes.pointer(LlvmTypes.INT_8),
+            List.of(new LlvmParam(LlvmTypes.INT_64, "size"))
+        ));
+
         return context.toModule();
     }
 
-    private static Context generateCompilationUnitElement(
+    private static ModuleContext generateCompilationUnitElement(
         PatioCompilationUnitElement patioCompilationUnitElement,
-        Context context
+        ModuleContext context
     ) {
         return switch (patioCompilationUnitElement) {
             case PatioDataElementImmutable patioDataElementImmutable ->
@@ -43,62 +75,80 @@ public class LlvmPatioCodeGen {
         };
     }
 
-    private static Context generateDataElementImmutable(
+    private static ModuleContext generateDataElementImmutable(
         PatioDataElementImmutable patioDataElementImmutable,
-        Context context
+        ModuleContext context
     ) {
         return context.addTopLevelEntity(new LlvmGlobalDefinition(
             patioDataElementImmutable.name(),
-            patioDataLayoutToType(patioDataElementImmutable.value().layout()),
-            Optional.of(patioDataValueToOperand(patioDataElementImmutable.value())),
+            patioDataLayoutToLlvmType(patioDataElementImmutable.value().layout()),
+            Optional.of(patioDataValueToLlvmOperand(patioDataElementImmutable.value())),
             true,
             true,
             true
         ));
     }
 
-    private static Context generateDataElementMutable(
+    private static ModuleContext generateDataElementMutable(
         PatioDataElementMutable patioDataElementMutable,
-        Context context
+        ModuleContext context
     ) {
         return context.addTopLevelEntity(new LlvmGlobalDefinition(
             patioDataElementMutable.name(),
-            patioDataLayoutToType(patioDataElementMutable.layout()),
-            Optional.of(patioDataLayoutToZeroedOperand(patioDataElementMutable.layout())),
+            patioDataLayoutToLlvmType(patioDataElementMutable.layout()),
+            Optional.of(patioDataLayoutToZeroedLlvmOperand(patioDataElementMutable.layout())),
             false,
             true,
             true
         ));
     }
 
-    private static Context generateFunctionDeclaration(
+    private static ModuleContext generateFunctionDeclaration(
         PatioFunctionDeclaration patioFunctionDeclaration,
-        Context context
+        ModuleContext context
     ) {
         return context.addTopLevelEntity(new LlvmFunctionDeclaration(
             patioFunctionDeclaration.name(),
-            patioTypeToType(patioFunctionDeclaration.returnType()),
+            patioTypeToLlvmType(patioFunctionDeclaration.returnType()),
             patioFunctionDeclaration.params().stream()
                 .map(patioParam -> new LlvmParam(
-                    patioTypeToType(patioParam.type()),
+                    patioTypeToLlvmType(patioParam.type()),
                     patioParam.name()
                 ))
                 .toList()
         ));
     }
 
-    private static Context generateFunctionDefinition(
+    private static ModuleContext generateFunctionDefinition(
         PatioFunctionDefinition patioFunctionDefinition,
-        Context context
+        ModuleContext context
     ) {
-        var llvmBody = List.<LlvmBasicBlock>of();
+        var functionContext = context.enterFunction();
+
+        var patioLocals = Lists.concat(
+            patioFunctionDefinition.params(),
+            patioFunctionDefinition.locals()
+        );
+        for (var patioLocal : patioLocals) {
+            functionContext = functionContext.addPatioLocalToType(
+                patioLocal.ref(),
+                patioTypeToLlvmType(patioLocal.type())
+            );
+        }
+
+        functionContext = generateInstructions(patioFunctionDefinition.body(), functionContext);
+        // TODO: push into Patio?
+        if (!functionContext.instructions.isEmpty()) {
+            functionContext = functionContext.addTerminatorInstruction(new LlvmReturnVoid());
+        }
+        var llvmBody = functionContext.basicBlocks;
 
         return context.addTopLevelEntity(new LlvmFunctionDefinition(
             patioFunctionDefinition.name(),
-            patioTypeToType(patioFunctionDefinition.returnType()),
+            patioTypeToLlvmType(patioFunctionDefinition.returnType()),
             patioFunctionDefinition.params().stream()
                 .map(patioParam -> new LlvmParam(
-                    patioTypeToType(patioParam.type()),
+                    patioTypeToLlvmType(patioParam.type()),
                     patioParam.name()
                 ))
                 .toList(),
@@ -106,8 +156,365 @@ public class LlvmPatioCodeGen {
         ));
     }
 
+    private static FunctionContext generateInstructions(
+        List<PatioInstruction> patioInstructions,
+        FunctionContext context
+    ) {
+        for (var patioInstruction : patioInstructions) {
+            context = generateInstruction(patioInstruction, context);
+        }
+        
+        return context;
+    }
+
+    private static FunctionContext generateInstruction(
+        PatioInstruction patioInstruction,
+        FunctionContext context
+    ) {
+        return switch (patioInstruction) {
+            case PatioAlloc patioAlloc -> {
+                var sizeResult = sizeOf(patioDataLayoutToLlvmType(patioAlloc.layout()), context);
+                var size = sizeResult.value;
+                context = sizeResult.context;
+
+                var targetResult = context.addPatioLocalToLlvmLocal(patioAlloc.target());
+                var target = targetResult.value;
+                context = targetResult.context;
+
+                yield context.addInstruction(new LlvmCall(
+                    target,
+                    LlvmTypes.pointer(LlvmTypes.VOID),
+                    new LlvmVariableGlobal("shed__runtime__alloc"),
+                    List.of(
+                        new LlvmTypedOperand(LlvmTypes.INT_64, size)
+                    )
+                ));
+            }
+
+            case PatioCall patioCall -> {
+                var target = Optional.<LlvmVariable>empty();
+                if (patioCall.target().isPresent()) {
+                    var targetResult = context.addPatioLocalToLlvmLocal(patioCall.target().get());
+                    target = Optional.of(targetResult.value);
+                    context = targetResult.context;
+                }
+
+                var c = context;
+
+                yield context.addInstruction(new LlvmCall(
+                    target,
+                    context.functionNameToReturnType(patioCall.functionName()),
+                    new LlvmVariableGlobal(patioCall.functionName()),
+                    patioCall.args().stream()
+                        .map(arg -> patioOperandToLlvmTypedOperand(arg, c))
+                        .toList()
+                ));
+            }
+
+            case PatioCallPointer patioCallPointer -> {
+                var targetResult = context.addPatioLocalToLlvmLocal(patioCallPointer.target());
+                var target = targetResult.value;
+                context = targetResult.context;
+
+                var c = context;
+
+                yield context.addInstruction(new LlvmCall(
+                    target,
+                    context.patioLocalToType(patioCallPointer.target()),
+                    patioOperandToLlvmOperand(patioCallPointer.functionPointer(), context),
+                    patioCallPointer.args().stream()
+                        .map(arg -> patioOperandToLlvmTypedOperand(arg, c))
+                        .toList()
+                ));
+            }
+
+            case PatioDataPtrToInt patioDataPtrToInt -> {
+                var targetResult = context.addPatioLocalToLlvmLocal(patioDataPtrToInt.target());
+                var target = targetResult.value;
+                context = targetResult.context;
+
+                yield context.addInstruction(new LlvmPtrToInt(
+                    target,
+                    patioOperandToLlvmOperand(patioDataPtrToInt.value(), context),
+                    LlvmTypes.INT_64
+                ));
+            }
+
+            case PatioIf patioIf -> {
+                var ifTrueLabelResult = context.allocateLocalName(
+                    LlvmCodeGenLocalVariableSpace.IF_TRUE
+                );
+                var ifTrueLabel = ifTrueLabelResult.value();
+                context = ifTrueLabelResult.context();
+
+                var ifFalseLabelResult = context.allocateLocalName(
+                    LlvmCodeGenLocalVariableSpace.IF_FALSE
+                );
+                var ifFalseLabel = ifFalseLabelResult.value();
+                context = ifFalseLabelResult.context();
+
+                var endLabelResult = context.allocateLocalName(
+                    LlvmCodeGenLocalVariableSpace.IF_END
+                );
+                var endLabel = endLabelResult.value();
+                context = endLabelResult.context();
+
+                context = context.addTerminatorInstruction(new LlvmBr(
+                    patioOperandToLlvmOperand(patioIf.condition(), context),
+                    ifTrueLabel.name(),
+                    ifFalseLabel.name()
+                ));
+
+                context = context.setBasicBlockLabel(ifTrueLabel.name());
+                context = generateInstructions(patioIf.trueBody(), context);
+                // TODO: remove this hack!
+                var ifTrueEndLabel = context.basicBlockLabel.orElseThrow();
+                context = context.addTerminatorInstruction(new LlvmBrUnconditional(endLabel.name()));
+
+                context = context.setBasicBlockLabel(ifFalseLabel.name());
+                context = generateInstructions(patioIf.falseBody(), context);
+                // TODO: remove this hack!
+                var ifFalseEndLabel = context.basicBlockLabel.orElseThrow();
+                context = context.addTerminatorInstruction(new LlvmBrUnconditional(endLabel.name()));
+
+                context = context.setBasicBlockLabel(endLabel.name());
+
+                // TODO: phi
+
+                yield context;
+            }
+
+
+            case PatioIntAdd patioIntAdd -> {
+                var targetResult = context.addPatioLocalToLlvmLocal(patioIntAdd.target());
+                var target = targetResult.value;
+                context = targetResult.context;
+
+                yield context.addInstruction(new LlvmAdd(
+                    target,
+                    LlvmTypes.INT_64,
+                    patioOperandToLlvmOperand(patioIntAdd.left(), context),
+                    patioOperandToLlvmOperand(patioIntAdd.right(), context)
+                ));
+            }
+
+            case PatioIntToDataPtr patioIntToDataPtr -> {
+                var targetResult = context.addPatioLocalToLlvmLocal(patioIntToDataPtr.target());
+                var target = targetResult.value;
+                context = targetResult.context;
+
+                yield context.addInstruction(new LlvmIntToPtr(
+                    target,
+                    LlvmTypes.INT_64,
+                    patioOperandToLlvmOperand(patioIntToDataPtr.value(), context)
+                ));
+            }
+
+            case PatioLocalStore patioLocalStore ->
+                context.addPatioLocal(
+                    patioLocalStore.target(),
+                    patioOperandToLlvmOperand(patioLocalStore.value(), context)
+                );
+
+            case PatioMemoryLoad patioMemoryLoad -> {
+                var targetResult = context.addPatioLocalToLlvmLocal(patioMemoryLoad.target());
+                var target = targetResult.value;
+                context = targetResult.context;
+
+                var pointerResult = context.allocateLocalName(LlvmCodeGenLocalVariableSpace.TEMPORARY);
+                var pointer = pointerResult.value;
+                context = pointerResult.context;
+
+                context = context.addInstruction(new LlvmGetElementPtr(
+                    pointer,
+                    LlvmTypes.pointer(patioDataLayoutToLlvmType(patioMemoryLoad.layout())),
+                    patioOperandToLlvmOperand(patioMemoryLoad.pointer(), context),
+                    patioDataOffsetsToLlvmOffsets(patioMemoryLoad.layout(), patioMemoryLoad.offset())
+                ));
+
+                context = context.addInstruction(new LlvmLoad(
+                    target,
+                    patioDataOffsetToLlvmType(patioMemoryLoad.layout(), patioMemoryLoad.offset()),
+                    pointer
+                ));
+
+                yield context;
+            }
+
+            case PatioMemoryStore patioMemoryStore -> {
+                var pointerResult = context.allocateLocalName(LlvmCodeGenLocalVariableSpace.TEMPORARY);
+                var pointer = pointerResult.value;
+                context = pointerResult.context;
+
+                context = context.addInstruction(new LlvmGetElementPtr(
+                    pointer,
+                    LlvmTypes.pointer(patioDataLayoutToLlvmType(patioMemoryStore.layout())),
+                    patioOperandToLlvmOperand(patioMemoryStore.pointer(), context),
+                    patioDataOffsetsToLlvmOffsets(patioMemoryStore.layout(), patioMemoryStore.offset())
+                ));
+
+                context = context.addInstruction(new LlvmStore(
+                    patioDataOffsetToLlvmType(patioMemoryStore.layout(), patioMemoryStore.offset()),
+                    patioOperandToLlvmOperand(patioMemoryStore.value(), context),
+                    pointer
+                ));
+
+                yield context;
+            }
+            
+            case PatioReturn patioReturn ->
+                context.addTerminatorInstruction(new LlvmReturn(
+                    context.patioLocalToType(patioReturn.value()),
+                    context.patioLocalToOperand(patioReturn.value())
+                ));
+        };
+    }
+
+    private static PVector<LlvmTypedOperand> patioDataOffsetsToLlvmOffsets(
+        PatioDataLayout patioDataLayout,
+        List<Integer> patioOffsets
+    ) {
+        return patioDataOffsetsToLlvmOffsets(
+            patioDataLayout,
+            TreePVector.from(patioOffsets),
+            P.vector()
+        ).plus(0, LlvmTypedOperand.arrayIndex(0));
+    }
+
+    private static PVector<LlvmTypedOperand> patioDataOffsetsToLlvmOffsets(
+        PatioDataLayout patioDataLayout,
+        PVector<Integer> patioOffsets,
+        PVector<LlvmTypedOperand> llvmOffsets
+    ) {
+        if (patioOffsets.isEmpty()) {
+            return llvmOffsets;
+        } else {
+            var patioOffset = patioOffsets.get(0);
+
+            return switch (patioDataLayout) {
+                case PatioDataLayoutArray patioDataLayoutArray ->
+                    patioDataOffsetsToLlvmOffsets(
+                        patioDataLayoutArray.element(),
+                        patioOffsets.minus(0),
+                        llvmOffsets.plus(LlvmTypedOperand.arrayIndex(patioOffset))
+                    );
+
+                case PatioDataLayoutBool patioDataLayoutBool ->
+                    throw new RuntimeException("offset not allowed for bools");
+
+                case PatioDataLayoutByte patioDataLayoutByte ->
+                    throw new RuntimeException("offset not allowed for bytes");
+
+                case PatioDataLayoutFunctionPointer patioDataLayoutFunctionPointer ->
+                    throw new RuntimeException("offset not allowed for function ptrs");
+
+                case PatioDataLayoutInt patioDataLayoutInt ->
+                    throw new RuntimeException("offset not allowed for ints");
+
+                case PatioDataLayoutStruct patioDataLayoutStruct ->
+                    patioDataOffsetsToLlvmOffsets(
+                        patioDataLayoutStruct.elements().get(patioOffset),
+                        patioOffsets.minus(0),
+                        llvmOffsets.plus(LlvmTypedOperand.structureIndex(patioOffset))
+                    );
+            };
+        }
+    }
+
+    private static LlvmType patioDataOffsetToLlvmType(
+        PatioDataLayout patioDataLayout,
+        List<Integer> patioOffsets
+    ) {
+        return patioDataOffsetToLlvmType(patioDataLayout, TreePVector.from(patioOffsets));
+    }
+
+    private static LlvmType patioDataOffsetToLlvmType(
+        PatioDataLayout patioDataLayout,
+        PVector<Integer> patioOffsets
+    ) {
+        return switch (patioDataLayout) {
+            case PatioDataLayoutArray patioDataLayoutArray ->
+                patioDataOffsetToLlvmType(
+                    patioDataLayoutArray.element(),
+                    patioOffsets.minus(0)
+                );
 
-    private static LlvmType patioTypeToType(PatioType patioType) {
+            case PatioDataLayoutBool patioDataLayoutBool ->
+                LlvmTypes.INT_1;
+
+            case PatioDataLayoutByte patioDataLayoutByte ->
+                LlvmTypes.INT_8;
+
+            case PatioDataLayoutFunctionPointer patioDataLayoutFunctionPointer ->
+                LlvmTypes.pointer(LlvmTypes.VOID);
+
+            case PatioDataLayoutInt patioDataLayoutInt ->
+                LlvmTypes.INT_64;
+
+            case PatioDataLayoutStruct patioDataLayoutStruct ->
+                patioDataOffsetToLlvmType(
+                    patioDataLayoutStruct.elements().get(patioOffsets.get(0)),
+                    patioOffsets.minus(0)
+                );
+        };
+    }
+
+    private static LlvmTypedOperand patioOperandToLlvmTypedOperand(
+        PatioOperand patioOperand,
+        FunctionContext context
+    ) {
+        return new LlvmTypedOperand(
+            patioOperandToLlvmType(patioOperand, context),
+            patioOperandToLlvmOperand(patioOperand, context)
+        );
+    }
+
+    private static LlvmType patioOperandToLlvmType(
+        PatioOperand patioOperand,
+        FunctionContext context
+    ) {
+        return switch (patioOperand) {
+            case PatioBool patioBool ->
+                LlvmTypes.INT_1;
+
+            case PatioDataPtr patioDataPtr ->
+                LlvmTypes.pointer(LlvmTypes.VOID);
+
+            case PatioFunctionPtr patioFunctionPtr ->
+                LlvmTypes.pointer(LlvmTypes.VOID);
+
+            case PatioInt patioInt ->
+                LlvmTypes.INT_64;
+
+            case PatioLocalRef patioLocalRef ->
+                context.patioLocalToType(patioLocalRef);
+        };
+    }
+
+    private static LlvmOperand patioOperandToLlvmOperand(
+        PatioOperand patioOperand,
+        FunctionContext context
+    ) {
+        return switch (patioOperand) {
+            case PatioBool patioBool ->
+                new LlvmOperandInt(patioBool.value() ? 1 : 0);
+
+            case PatioDataPtr patioDataPtr ->
+                new LlvmVariableGlobal(patioDataPtr.name());
+
+            case PatioFunctionPtr patioFunctionPtr ->
+                new LlvmVariableGlobal(patioFunctionPtr.name());
+
+            case PatioInt patioInt ->
+                new LlvmOperandInt(patioInt.value());
+
+            case PatioLocalRef patioLocalRef ->
+                context.patioLocalToOperand(patioLocalRef);
+        };
+    }
+
+
+    private static LlvmType patioTypeToLlvmType(PatioType patioType) {
         return switch (patioType) {
             case PatioBoolType patioBoolType ->
                 LlvmTypes.INT_1;
@@ -129,12 +536,12 @@ public class LlvmPatioCodeGen {
         };
     }
 
-    private static LlvmType patioDataLayoutToType(PatioDataLayout layout) {
+    private static LlvmType patioDataLayoutToLlvmType(PatioDataLayout layout) {
         return switch (layout) {
             case PatioDataLayoutArray patioDataLayoutArray ->
                 LlvmTypes.array(
                     patioDataLayoutArray.size(),
-                    patioDataLayoutToType(patioDataLayoutArray.element())
+                    patioDataLayoutToLlvmType(patioDataLayoutArray.element())
                 );
 
             case PatioDataLayoutBool patioDataLayoutBool ->
@@ -152,19 +559,19 @@ public class LlvmPatioCodeGen {
             case PatioDataLayoutStruct patioDataLayoutStruct ->
                 LlvmTypes.structure(
                     patioDataLayoutStruct.elements().stream()
-                        .map(element -> patioDataLayoutToType(element))
+                        .map(element -> patioDataLayoutToLlvmType(element))
                         .toList()
                 );
         };
     }
 
-    private static LlvmOperand patioDataLayoutToZeroedOperand(PatioDataLayout layout) {
+    private static LlvmOperand patioDataLayoutToZeroedLlvmOperand(PatioDataLayout layout) {
         return switch (layout) {
             case PatioDataLayoutArray patioDataLayoutArray ->
                 new LlvmOperandArray(
-                    patioDataLayoutToType(patioDataLayoutArray.element()),
+                    patioDataLayoutToLlvmType(patioDataLayoutArray.element()),
                     Lists.repeat(
-                        patioDataLayoutToZeroedOperand(patioDataLayoutArray.element()),
+                        patioDataLayoutToZeroedLlvmOperand(patioDataLayoutArray.element()),
                         patioDataLayoutArray.size()
                     )
                 );
@@ -185,22 +592,22 @@ public class LlvmPatioCodeGen {
                 new LlvmOperandStructure(
                     patioDataLayoutStruct.elements().stream()
                         .map(element -> new LlvmTypedOperand(
-                            patioDataLayoutToType(element),
-                            patioDataLayoutToZeroedOperand(element)
+                            patioDataLayoutToLlvmType(element),
+                            patioDataLayoutToZeroedLlvmOperand(element)
                         ))
                         .toList()
                 );
         };
     }
 
-    private static LlvmOperand patioDataValueToOperand(PatioDataValue value) {
+    private static LlvmOperand patioDataValueToLlvmOperand(PatioDataValue value) {
         return switch (value) {
             case PatioDataValueArray patioDataValueArray -> {
                 var patioElement = patioDataValueArray.elements().get(0);
-                var llvmType = patioDataLayoutToType(patioElement.layout());
+                var llvmType = patioDataLayoutToLlvmType(patioElement.layout());
 
                 var llvmElements = patioDataValueArray.elements().stream()
-                    .map(element -> patioDataValueToOperand(element))
+                    .map(element -> patioDataValueToLlvmOperand(element))
                     .toList();
 
                 yield new LlvmOperandArray(llvmType, llvmElements);
@@ -216,33 +623,243 @@ public class LlvmPatioCodeGen {
                 new LlvmOperandStructure(
                     patioDataValueStruct.elements().stream()
                         .map(element -> new LlvmTypedOperand(
-                            patioDataLayoutToType(element.layout()),
-                            patioDataValueToOperand(element)
+                            patioDataLayoutToLlvmType(element.layout()),
+                            patioDataValueToLlvmOperand(element)
                         ))
                         .toList()
                 );
         };
     }
 
-    private static class Context {
-        private static final Context EMPTY = new Context(P.vector());
+    public static FunctionContext.Result<LlvmOperand> sizeOf(
+        LlvmType type,
+        FunctionContext context
+    ) {
+        var sizePtrResult = context.allocateLocalName(LlvmCodeGenLocalVariableSpace.SIZE_PTR);
+        var sizePtr = sizePtrResult.value();
+        context = sizePtrResult.context();
+
+        var sizeResult = context.allocateLocalName(LlvmCodeGenLocalVariableSpace.SIZE);
+        var size = sizeResult.value();
+        context = sizeResult.context();
+
+        return context
+            .addInstruction(
+                new LlvmGetElementPtr(
+                    sizePtr,
+                    LlvmTypes.pointer(type),
+                    new LlvmOperandNull(),
+                    List.of(LlvmTypedOperand.arrayIndex(0))
+                )
+            )
+            .addInstruction(
+                new LlvmPtrToInt(
+                    size,
+                    sizePtr,
+                    LlvmTypes.INT_64
+                )
+            )
+            .toResult(size);
+    }
 
+    private static class ModuleContext {
+        private static final ModuleContext EMPTY = new ModuleContext(
+            P.map(),
+            P.vector()
+        );
+
+        private final PMap<String, LlvmType> functionNameToReturnType;
         private final PVector<LlvmTopLevelEntity> topLevelEntities;
 
-        private Context(
+        private ModuleContext(
+            PMap<String, LlvmType> functionNameToReturnType,
             PVector<LlvmTopLevelEntity> topLevelEntities
         ) {
+            this.functionNameToReturnType = functionNameToReturnType;
             this.topLevelEntities = topLevelEntities;
         }
 
+        private ModuleContext addFunctionNameToReturnType(String functionName, LlvmType returnType) {
+            return new ModuleContext(
+                this.functionNameToReturnType.plus(functionName, returnType),
+                this.topLevelEntities
+            );
+        }
+
         private LlvmModule toModule() {
             return new LlvmModule(topLevelEntities);
         }
 
-        public Context addTopLevelEntity(LlvmTopLevelEntity topLevelEntity) {
-            return new Context(
+        public ModuleContext addTopLevelEntity(LlvmTopLevelEntity topLevelEntity) {
+            return new ModuleContext(
+                this.functionNameToReturnType,
                 this.topLevelEntities.plus(topLevelEntity)
             );
         }
+
+        public FunctionContext enterFunction() {
+            return FunctionContext.of(functionNameToReturnType);
+        }
+    }
+
+    private static class FunctionContext {
+        private static FunctionContext of(PMap<String, LlvmType> functionNameToType) {
+            return new FunctionContext(
+                functionNameToType,
+                P.vector(),
+                Optional.empty(),
+                P.vector(),
+                P.map(),
+                P.map(),
+                NameAllocator.empty()
+            );
+        }
+
+        private final PMap<String, LlvmType> functionNameToReturnType;
+        private final PVector<LlvmBasicBlock> basicBlocks;
+        private final Optional<String> basicBlockLabel;
+        private final PVector<LlvmInstruction> instructions;
+        private final PMap<PatioLocalRef, LlvmType> patioLocalToType;
+        private final PMap<PatioLocalRef, LlvmOperand> patioLocalToOperand;
+        private final NameAllocator<LlvmCodeGenLocalVariableSpace> localNameAllocator;
+
+        private FunctionContext(
+            PMap<String, LlvmType> functionNameToReturnType,
+            PVector<LlvmBasicBlock> basicBlocks,
+            Optional<String> basicBlockLabel,
+            PVector<LlvmInstruction> instructions,
+            PMap<PatioLocalRef, LlvmType> patioLocalToType,
+            PMap<PatioLocalRef, LlvmOperand> patioLocalToOperand,
+            NameAllocator<LlvmCodeGenLocalVariableSpace> localNameAllocator
+        ) {
+            this.functionNameToReturnType = functionNameToReturnType;
+            this.basicBlocks = basicBlocks;
+            this.basicBlockLabel = basicBlockLabel;
+            this.instructions = instructions;
+            this.patioLocalToType = patioLocalToType;
+            this.patioLocalToOperand = patioLocalToOperand;
+            this.localNameAllocator = localNameAllocator;
+        }
+
+        private LlvmType functionNameToReturnType(String functionName) {
+            return this.functionNameToReturnType.get(functionName);
+        }
+
+        private FunctionContext addTerminatorInstruction(LlvmTerminatorInstruction terminatorInstruction) {
+            return new FunctionContext(
+                this.functionNameToReturnType,
+                this.basicBlocks.plus(new LlvmBasicBlock(
+                    this.basicBlockLabel,
+                    this.instructions,
+                    terminatorInstruction
+                )),
+                Optional.empty(),
+                P.vector(),
+                this.patioLocalToType,
+                this.patioLocalToOperand,
+                this.localNameAllocator
+            );
+        }
+
+        public FunctionContext setBasicBlockLabel(String basicBlockLabel) {
+            if (this.basicBlockLabel.isEmpty()) {
+                return new FunctionContext(
+                    this.functionNameToReturnType,
+                    this.basicBlocks,
+                    Optional.of(basicBlockLabel),
+                    this.instructions,
+                    this.patioLocalToType,
+                    this.patioLocalToOperand,
+                    this.localNameAllocator
+                );
+            } else {
+                throw new RuntimeException("basic block label is already set");
+            }
+        }
+
+        public LlvmType patioLocalToType(PatioLocalRef value) {
+            return this.patioLocalToType.get(value);
+        }
+
+        public LlvmOperand patioLocalToOperand(PatioLocalRef value) {
+            return this.patioLocalToOperand.get(value);
+        }
+
+        public FunctionContext addPatioLocalToType(PatioLocalRef patioLocal, LlvmType llvmType) {
+            return new FunctionContext(
+                this.functionNameToReturnType,
+                this.basicBlocks,
+                this.basicBlockLabel,
+                this.instructions,
+                this.patioLocalToType.plus(patioLocal, llvmType),
+                this.patioLocalToOperand,
+                this.localNameAllocator
+            );
+        }
+
+        public FunctionContext addInstruction(LlvmInstruction instruction) {
+            return new FunctionContext(
+                this.functionNameToReturnType,
+                this.basicBlocks,
+                this.basicBlockLabel,
+                this.instructions.plus(instruction),
+                this.patioLocalToType,
+                this.patioLocalToOperand,
+                this.localNameAllocator
+            );
+        }
+
+        public Result<LlvmVariableLocal> allocateLocalName(LlvmCodeGenLocalVariableSpace space) {
+            var result = localNameAllocator.allocateName(space, Optional.empty());
+
+            return new FunctionContext(
+                this.functionNameToReturnType,
+                this.basicBlocks,
+                this.basicBlockLabel,
+                this.instructions,
+                this.patioLocalToType,
+                this.patioLocalToOperand,
+                result.allocator()
+            ).toResult(new LlvmVariableLocal(result.name()));
+        }
+
+        public Result<LlvmVariableLocal> allocateLocalName(LlvmCodeGenLocalVariableSpace space, String name) {
+            var result = localNameAllocator.allocateName(space, Optional.of(name));
+
+            return new FunctionContext(
+                this.functionNameToReturnType,
+                this.basicBlocks,
+                this.basicBlockLabel,
+                this.instructions,
+                this.patioLocalToType,
+                this.patioLocalToOperand,
+                result.allocator()
+            ).toResult(new LlvmVariableLocal(result.name()));
+        }
+
+        public Result<LlvmVariableLocal> addPatioLocalToLlvmLocal(PatioLocalRef patioLocal) {
+            var result = allocateLocalName(LlvmCodeGenLocalVariableSpace.LOCAL, patioLocal.name());
+
+            return result.context.addPatioLocal(patioLocal, result.value).toResult(result.value);
+        }
+
+        public FunctionContext addPatioLocal(PatioLocalRef patioLocal, LlvmOperand llvmOperand) {
+            return new FunctionContext(
+                this.functionNameToReturnType,
+                this.basicBlocks,
+                this.basicBlockLabel,
+                this.instructions,
+                this.patioLocalToType,
+                this.patioLocalToOperand.plus(patioLocal, llvmOperand),
+                this.localNameAllocator
+            );
+        }
+
+        private <T> Result<T> toResult(T value) {
+            return new Result<>(value, this);
+        }
+
+        public record Result<T>(T value, FunctionContext context) {
+        }
     }
 }
diff --git a/src/main/java/org/shedlang/compiler/patio/ast/PatioLocal.java b/src/main/java/org/shedlang/compiler/patio/ast/PatioLocal.java
index 1cb7433b..eda09d2c 100644
--- a/src/main/java/org/shedlang/compiler/patio/ast/PatioLocal.java
+++ b/src/main/java/org/shedlang/compiler/patio/ast/PatioLocal.java
@@ -1,6 +1,10 @@
 package org.shedlang.compiler.patio.ast;
 
+import org.shedlang.compiler.patio.ast.operands.PatioLocalRef;
 import org.shedlang.compiler.patio.ast.types.PatioType;
 
 public record PatioLocal(String name, PatioType type) {
+    public PatioLocalRef ref() {
+        return new PatioLocalRef(name);
+    }
 }