From 55f45123f21e63e883d0afe16d97dcb5dafdd296 Mon Sep 17 00:00:00 2001 From: Mathias Magnusson Date: Wed, 4 Jun 2025 01:12:01 +0200 Subject: 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) --- src/compile.zig | 210 +++++++++++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 176 insertions(+), 34 deletions(-) (limited to 'src/compile.zig') 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; -- cgit v1.2.3