From 0fa2f445eb7140214471074fc544adfd0f8a524f Mon Sep 17 00:00:00 2001 From: Mathias Magnusson Date: Thu, 24 Jul 2025 22:15:03 +0200 Subject: continue implementing procedure calls multiple procedures can now exist, but you cannot call them, the first one is the "main" procedure since it happens to be placed first in the binary, and all procedures end with an exit system call --- src/compile.zig | 222 +++++++++++++++++++++++++++++++++++--------------------- 1 file changed, 139 insertions(+), 83 deletions(-) (limited to 'src/compile.zig') diff --git a/src/compile.zig b/src/compile.zig index 583be50..d2226f1 100644 --- a/src/compile.zig +++ b/src/compile.zig @@ -30,6 +30,77 @@ fn IdCounter(Id: type) type { }; } +pub const Module = struct { + procedures: []Procedure, + + pub fn format(self: Module, comptime fmt: []const u8, options: std.fmt.FormatOptions, writer: anytype) !void { + _ = .{ fmt, options }; + for (self.procedures) |proc| { + try writer.print("{}", .{proc}); + } + } +}; + +pub const Procedure = struct { + name: []const u8, + blocks: []BasicBlock, + + fn init(allocator: Allocator, name: []const u8, blocks: []BasicBlock) !Procedure { + for (blocks) |*block| { + try block.finalize(allocator); + } + + return .{ .name = name, .blocks = blocks }; + } + + pub fn format(self: Procedure, comptime fmt: []const u8, options: std.fmt.FormatOptions, writer: anytype) !void { + _ = .{ fmt, options }; + try writer.print("{s}:\n", .{self.name}); + for (self.blocks, 0..) |block, i| { + try writer.print(" ${}{}", .{ i, block }); + } + try writer.writeAll("\n"); + } +}; + +pub const BasicBlock = struct { + ref: BlockRef, + instrs: std.ArrayListUnmanaged(Instr) = .empty, + + vreg_last_use: std.AutoHashMapUnmanaged(VReg, usize) = .empty, + + fn finalize(self: *BasicBlock, allocator: Allocator) !void { + std.debug.assert(self.instrs.items.len > 0); + std.debug.assert(switch (self.instrs.getLast().type) { + inline else => |ty| @hasDecl(@TypeOf(ty), "may_end_block"), + }); + + self.vreg_last_use = .empty; + for (0.., self.instrs.items) |i, instr| { + for (instr.sources().slice()) |src| + try self.vreg_last_use.put(allocator, src, i); + if (instr.dest()) |dest| + try self.vreg_last_use.put(allocator, dest, i); + } + } + + fn immediate_successors(self: *BasicBlock) std.BoundedArray(BlockRef, 2) { + return switch (self.instrs.getLast().type) { + .branch => |branch| std.BoundedArray(BlockRef, 2).fromSlice(&.{ branch.true.to, branch.false.to }) catch unreachable, + .jump => |jump| std.BoundedArray(BlockRef, 2).fromSlice(&.{jump.to}) catch unreachable, + else => .{}, + }; + } + + pub fn format(self: BasicBlock, comptime fmt: []const u8, options: std.fmt.FormatOptions, writer: anytype) !void { + _ = .{ fmt, options }; + try writer.print(":\n", .{}); + for (self.instrs.items) |instr| { + try writer.print(" {}\n", .{instr}); + } + } +}; + pub const Instr = struct { loc: Location, type: Type, @@ -199,95 +270,76 @@ pub const Instr = struct { } }; -pub const Procedure = struct { - blocks: []BasicBlock, - - fn init(allocator: Allocator, blocks: []BasicBlock) !Procedure { - for (blocks) |*block| { - try block.finalize(allocator); - } - - return .{ .blocks = blocks }; - } - - pub fn format(self: Procedure, comptime fmt: []const u8, options: std.fmt.FormatOptions, writer: anytype) !void { - _ = .{ fmt, options }; - for (self.blocks, 0..) |block, i| { - try writer.print("${}{}", .{ i, block }); - } - } +const Scope = struct { + locals: std.StringHashMapUnmanaged(LVar), + parent: ?*Scope, }; -pub const BasicBlock = struct { - instrs: std.ArrayListUnmanaged(Instr) = .empty, - - vreg_last_use: std.AutoHashMapUnmanaged(VReg, usize) = .empty, - - fn finalize(self: *BasicBlock, allocator: Allocator) !void { - std.debug.assert(self.instrs.items.len > 0); - std.debug.assert(switch (self.instrs.getLast().type) { - inline else => |ty| @hasDecl(@TypeOf(ty), "may_end_block"), - }); - - self.vreg_last_use = .empty; - for (0.., self.instrs.items) |i, instr| { - for (instr.sources().slice()) |src| - try self.vreg_last_use.put(allocator, src, i); - if (instr.dest()) |dest| - try self.vreg_last_use.put(allocator, dest, i); - } - } +const CompileError = error{ + OutOfMemory, + CanOnlyCallIdentifiers, + UnknownProcedure, + UnknownVariable, + CannotDefineProcedureHere, +}; - fn immediate_successors(self: *BasicBlock) std.BoundedArray(BlockRef, 2) { - return switch (self.instrs.getLast().type) { - .branch => |branch| std.BoundedArray(BlockRef, 2).fromSlice(&.{ branch.true.to, branch.false.to }) catch unreachable, - .jump => |jump| std.BoundedArray(BlockRef, 2).fromSlice(&.{jump.to}) catch unreachable, - else => .{}, - }; +pub fn compile(allocator: Allocator, source: []const u8, file: parse.File) !Module { + const procs = try allocator.alloc(Procedure, file.decls.len); + var ctx: Context = .{ + .allocator = allocator, + .block_ctx = .init, + }; + for (procs, file.decls) |*proc, decl| { + proc.* = try compileProcedure( + &ctx, + source, + decl.inner.ident, + decl.inner.value.type.proc, + ); } + return .{ + .procedures = procs, + }; +} - pub fn format(self: BasicBlock, comptime fmt: []const u8, options: std.fmt.FormatOptions, writer: anytype) !void { - _ = .{ fmt, options }; - try writer.print(":\n", .{}); - for (self.instrs.items) |instr| { - try writer.print(" {}\n", .{instr}); - } - } +const Context = struct { + allocator: Allocator, + block_ctx: IdCounter(BlockRef), }; -pub fn compile(allocator: Allocator, source: []const u8, block: parse.Block) !Procedure { - var ctx: CompileContext = .{ - .allocator = allocator, +fn compileProcedure( + ctx: *Context, + source: []const u8, + name: Location, + proc: parse.Expr.Type.Proc, +) !Procedure { + var pctx: ProcedureContext = .{ + .ctx = ctx, .source = source, .vreg_ctr = .init, .lvar_ctr = .init, .scope = .{ .locals = .empty, .parent = null }, .blocks = .empty, - .current_block = @enumFromInt(0), + .current_block = undefined, // immediately set by `switchToNewBlock` }; - _ = try ctx.switchToNewBlock(); - try ctx.compileBlock(block); - try ctx.addInstr(.{ + _ = try pctx.switchToNewBlock(); + try pctx.compileBlock(proc.body); + try pctx.addInstr(.{ .loc = .{ .start = 0, .end = 0 }, .type = .{ .exit = .{} }, }); - return try .init(allocator, try ctx.blocks.toOwnedSlice(allocator)); + var blocks = try ctx.allocator.alloc(BasicBlock, pctx.blocks.count()); + var it = pctx.blocks.iterator(); + var i: usize = 0; + while (it.next()) |kv| : (i += 1) { + std.debug.assert(kv.key_ptr.* == kv.value_ptr.ref); + blocks[i] = kv.value_ptr.*; + } + return try .init(ctx.allocator, name.getIdent(source), blocks); } -const Scope = struct { - locals: std.StringHashMapUnmanaged(LVar), - parent: ?*Scope, -}; - -const CompileError = error{ - OutOfMemory, - CanOnlyCallIdentifiers, - UnknownProcedure, - UnknownVariable, -}; - -const CompileContext = struct { - allocator: Allocator, +const ProcedureContext = struct { + ctx: *Context, source: []const u8, vreg_ctr: IdCounter(VReg), @@ -295,10 +347,10 @@ const CompileContext = struct { scope: Scope, - blocks: std.ArrayListUnmanaged(BasicBlock), + blocks: std.AutoArrayHashMapUnmanaged(BlockRef, BasicBlock), current_block: BlockRef, - fn compileBlock(self: *CompileContext, block: parse.Block) !void { + fn compileBlock(self: *ProcedureContext, block: parse.Block) !void { var parent = self.scope; self.scope = .{ .locals = .empty, @@ -309,11 +361,11 @@ const CompileContext = struct { try self.compileStmt(stmt); } - self.scope.locals.deinit(self.allocator); + self.scope.locals.deinit(self.ctx.allocator); self.scope = parent; } - fn compileStmt(self: *CompileContext, stmt: parse.Stmt) CompileError!void { + fn compileStmt(self: *ProcedureContext, stmt: parse.Stmt) CompileError!void { switch (stmt.type) { .expr => |expr| _ = try self.compileExpr(expr), .block => |block| { @@ -323,7 +375,7 @@ const CompileContext = struct { const local = if (assign_var.is_decl) blk: { const local = self.lvar_ctr.get(); const name = assign_var.ident.getIdent(self.source); - try self.scope.locals.put(self.allocator, name, local); + try self.scope.locals.put(self.ctx.allocator, name, local); break :blk local; } else blk: { var scope: ?*Scope = &self.scope; @@ -373,7 +425,7 @@ const CompileContext = struct { } } - fn compileExpr(self: *CompileContext, expr: *const parse.Expr) !VReg { + fn compileExpr(self: *ProcedureContext, 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.vreg_ctr.get(); switch (expr.type) { @@ -470,19 +522,23 @@ const CompileContext = struct { self.current_block = after; }, + .proc => |proc| { + _ = proc; + return error.CannotDefineProcedureHere; + }, } return dest; } - fn switchToNewBlock(self: *CompileContext) !BlockRef { - const ref: BlockRef = @enumFromInt(self.blocks.items.len); - try self.blocks.append(self.allocator, .{}); + fn switchToNewBlock(self: *ProcedureContext) !BlockRef { + const ref = self.ctx.block_ctx.get(); + try self.blocks.putNoClobber(self.ctx.allocator, ref, .{ .ref = ref }); 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 addInstr(self: *ProcedureContext, instr: Instr) !void { + try self.blocks.getPtr(self.current_block).? + .instrs.append(self.ctx.allocator, instr); } }; -- cgit v1.2.3