begin implementing if expressions

registers are used over block boundaries though, which doesn't work very
well so i turned off register freeing to make it look like it works
(unless you create more than 12 values total)

1 files changed, 176 insertions, 34 deletions

diff --git a/src/compile.zig b/src/compile.zig
index 5d57e71..0918d30 100644
--- a/src/compile.zig
+++ b/src/compile.zig
@@ -6,6 +6,7 @@ const parse = root.parse;
 const Location = root.Lexer.Location;
 
 pub const VReg = enum(u32) { _ };
+pub const BlockRef = enum(u32) { _ };
 
 pub const Instr = struct {
     loc: Location,
@@ -15,6 +16,9 @@ pub const Instr = struct {
         constant: Constant,
         bin_op: BinOp,
         proc_call: ProcCall,
+        branch: Branch,
+        jump: Jump,
+        exit: Exit,
     };
 
     pub const Constant = struct {
@@ -57,6 +61,30 @@ pub const Instr = struct {
         }
     };
 
+    pub const Branch = struct {
+        cond: VReg,
+        true: BlockRef,
+        false: BlockRef,
+
+        pub fn sources(self: Branch) Sources {
+            return Sources.fromSlice(&.{self.cond}) catch unreachable;
+        }
+    };
+
+    pub const Jump = struct {
+        to: BlockRef,
+
+        pub fn sources(_: Jump) Sources {
+            return Sources.init(0) catch unreachable;
+        }
+    };
+
+    pub const Exit = struct {
+        pub fn sources(_: Exit) Sources {
+            return Sources.init(0) catch unreachable;
+        }
+    };
+
     pub fn sources(self: Instr) Sources {
         return switch (self.type) {
             inline else => |instr| instr.sources(),
@@ -66,43 +94,94 @@ pub const Instr = struct {
     pub fn dest(self: *const Instr) ?VReg {
         return switch (self.type) {
             inline .constant, .bin_op, .proc_call => |s| s.dest,
+            .branch, .jump, .exit => null,
         };
     }
 
     pub const Sources = std.BoundedArray(VReg, 2);
+
+    pub fn format(self: Instr, comptime fmt: []const u8, options: std.fmt.FormatOptions, writer: anytype) !void {
+        _ = .{ fmt, options };
+
+        switch (self.type) {
+            .constant => |constant| try writer.print(
+                "%{} = {}",
+                .{ @intFromEnum(constant.dest), constant.value },
+            ),
+            .bin_op => |bin_op| try writer.print(
+                "%{} = %{} {s} %{}",
+                .{
+                    @intFromEnum(bin_op.dest),
+                    @intFromEnum(bin_op.lhs),
+                    @tagName(bin_op.op),
+                    @intFromEnum(bin_op.rhs),
+                },
+            ),
+            .proc_call => |proc_call| try writer.print(
+                "%{} = {s} %{}",
+                .{
+                    @intFromEnum(proc_call.dest),
+                    @tagName(proc_call.proc),
+                    @intFromEnum(proc_call.arg),
+                },
+            ),
+            .branch => |branch| try writer.print(
+                "branch %{} ? ${} : ${}",
+                .{
+                    @intFromEnum(branch.cond),
+                    @intFromEnum(branch.true),
+                    @intFromEnum(branch.false),
+                },
+            ),
+            .jump => |jump| try writer.print("jump ${}", .{@intFromEnum(jump.to)}),
+            .exit => |_| try writer.print("exit", .{}),
+        }
+    }
+};
+
+pub const Procedure = struct {
+    blocks: []BasicBlock,
+
+    fn init(allocator: Allocator, blocks: []BasicBlock) !Procedure {
+        for (blocks) |*block| {
+            try block.finalize(allocator);
+        }
+        return .{ .blocks = blocks };
+    }
 };
 
 pub const BasicBlock = struct {
     // arguments: []Reg,
-    instrs: []Instr,
-    vreg_last_use: std.AutoHashMap(VReg, usize),
+    instrs: std.ArrayListUnmanaged(Instr) = .empty,
 
-    fn init(allocator: Allocator, instrs: []Instr) !BasicBlock {
-        var vreg_last_use: std.AutoHashMap(VReg, usize) = .init(allocator);
-        for (0.., instrs) |i, instr| {
+    vreg_last_use: std.AutoHashMapUnmanaged(VReg, usize) = .empty,
+
+    fn finalize(self: *BasicBlock, allocator: Allocator) !void {
+        self.vreg_last_use = .empty;
+        for (0.., self.instrs.items) |i, instr| {
             for (instr.sources().slice()) |src|
-                try vreg_last_use.put(src, i);
+                try self.vreg_last_use.put(allocator, src, i);
             if (instr.dest()) |dest|
-                try vreg_last_use.put(dest, i);
+                try self.vreg_last_use.put(allocator, dest, i);
         }
-        return .{
-            .instrs = instrs,
-            .vreg_last_use = vreg_last_use,
-        };
     }
 };
 
-pub fn compile(allocator: Allocator, source: []const u8, block: parse.Block) !BasicBlock {
-    const instrs: std.ArrayListUnmanaged(Instr) = try .initCapacity(allocator, 0);
+pub fn compile(allocator: Allocator, source: []const u8, block: parse.Block) !Procedure {
     var ctx: CompileContext = .{
         .allocator = allocator,
         .source = source,
         .register_counter = 0,
         .scope = .{ .locals = .empty, .parent = null },
-        .instrs = instrs,
+        .blocks = .empty,
+        .current_block = @enumFromInt(0),
     };
     try ctx.compileBlock(block);
-    return .init(allocator, ctx.instrs.items);
+    try ctx.addInstr(.{
+        .loc = .{ .start = 0, .end = 0 },
+        .type = .{ .exit = .{} },
+    });
+    return try .init(allocator, try ctx.blocks.toOwnedSlice(allocator));
 }
 
 const CompileError = error{
@@ -117,38 +196,51 @@ const CompileContext = struct {
     source: []const u8,
     register_counter: u32,
     scope: Scope,
-    instrs: std.ArrayListUnmanaged(Instr),
+    blocks: std.ArrayListUnmanaged(BasicBlock),
+    current_block: BlockRef,
+    // instrs: std.ArrayListUnmanaged(Instr),
 
     const Scope = struct {
         locals: std.StringHashMapUnmanaged(VReg),
         parent: ?*Scope,
     };
 
-    const Self = @This();
-
-    fn addInstr(self: *Self, instr: Instr) !void {
-        try self.instrs.append(self.allocator, instr);
-    }
+    fn compileBlock(self: *CompileContext, block: parse.Block) !void {
+        _ = try self.switchToNewBlock();
 
-    fn compileBlock(self: *Self, block: parse.Block) !void {
-        const parent = try self.allocator.create(Scope);
-        defer self.allocator.destroy(parent);
-        parent.* = self.scope;
+        var parent = self.scope;
         self.scope = .{
             .locals = .empty,
-            .parent = parent,
+            .parent = &parent,
         };
+
         for (block.stmts) |stmt| {
             try self.compileStmt(stmt);
         }
+
         self.scope.locals.deinit(self.allocator);
-        self.scope = parent.*;
+        self.scope = parent;
     }
 
-    fn compileStmt(self: *Self, stmt: parse.Stmt) CompileError!void {
+    fn compileStmt(self: *CompileContext, stmt: parse.Stmt) CompileError!void {
         switch (stmt.type) {
             .expr => |expr| _ = try self.compileExpr(expr),
-            .block => |block| try self.compileBlock(block),
+            .block => |block| {
+                const curr = self.current_block;
+                const after = try self.switchToNewBlock();
+                try self.compileBlock(block);
+                const b = self.current_block;
+                try self.addInstr(.{
+                    .loc = stmt.loc,
+                    .type = .{ .jump = .{ .to = after } },
+                });
+                self.current_block = curr;
+                try self.addInstr(.{
+                    .loc = stmt.loc,
+                    .type = .{ .jump = .{ .to = b } },
+                });
+                self.current_block = after;
+            },
             .declare_var => |declare_var| {
                 const val = try self.compileExpr(declare_var.value);
                 const name = declare_var.ident.getIdent(self.source);
@@ -157,18 +249,18 @@ const CompileContext = struct {
         }
     }
 
-    fn compileExpr(self: *Self, expr: *const parse.Expr) !VReg {
+    fn compileExpr(self: *CompileContext, expr: *const parse.Expr) !VReg {
         // This is not used by all expression types, but creating an unused virtual register is not a problem.
         const dest = self.register();
         switch (expr.type) {
-            .integer_literal => try addInstr(self, .{
+            .integer_literal => try self.addInstr(.{
                 .loc = expr.loc,
                 .type = .{ .constant = .{ .dest = dest, .value = expr.loc.getInt(self.source) } },
             }),
             .bin_op => |binop| {
                 const lhs = try self.compileExpr(binop.lhs);
                 const rhs = try self.compileExpr(binop.rhs);
-                try addInstr(self, .{
+                try self.addInstr(.{
                     .loc = expr.loc,
                     .type = .{
                         .bin_op = .{
@@ -190,7 +282,11 @@ const CompileContext = struct {
                 const arg = try self.compileExpr(call.arg);
                 try self.addInstr(.{
                     .loc = expr.loc,
-                    .type = .{ .proc_call = .{ .dest = dest, .arg = arg, .proc = proc } },
+                    .type = .{ .proc_call = .{
+                        .dest = dest,
+                        .arg = arg,
+                        .proc = proc,
+                    } },
                 });
             },
             .identifier => {
@@ -202,11 +298,57 @@ const CompileContext = struct {
                 }
                 return error.UnknownVariable;
             },
+            .@"if" => |@"if"| {
+                const cond = try self.compileExpr(@"if".cond);
+                const curr = self.current_block;
+
+                const after = try self.switchToNewBlock();
+
+                try self.compileBlock(@"if".then);
+                try self.addInstr(.{
+                    .loc = expr.loc,
+                    .type = .{ .jump = .{ .to = after } },
+                });
+                const t = self.current_block;
+
+                const f = if (@"if".@"else") |@"else"| blk: {
+                    try self.compileBlock(@"else");
+                    try self.addInstr(.{
+                        .loc = expr.loc,
+                        .type = .{ .jump = .{ .to = after } },
+                    });
+                    break :blk self.current_block;
+                } else after;
+
+                self.current_block = curr;
+                try self.addInstr(.{
+                    .loc = expr.loc,
+                    .type = .{ .branch = .{
+                        .cond = cond,
+                        .true = t,
+                        .false = f,
+                    } },
+                });
+
+                self.current_block = after;
+            },
         }
         return dest;
     }
 
-    fn register(self: *Self) VReg {
+    fn switchToNewBlock(self: *CompileContext) !BlockRef {
+        const ref: BlockRef = @enumFromInt(self.blocks.items.len);
+        try self.blocks.append(self.allocator, .{});
+        self.current_block = ref;
+        return ref;
+    }
+
+    fn addInstr(self: *CompileContext, instr: Instr) !void {
+        try self.blocks.items[@intFromEnum(self.current_block)]
+            .instrs.append(self.allocator, instr);
+    }
+
+    fn register(self: *CompileContext) VReg {
         const reg: VReg = @enumFromInt(self.register_counter);
         self.register_counter += 1;
         return reg;