Reading · Abdul Rahman Sibahi

This page cannot be shown here. You can still read it on the original site — the toolbar below keeps your place in the directory.

After eight grueling (not really) chapters of Writing a C Compiler , time to implement more assembly instructions. Functions! Linkage! Commas! Lexer, AST, and Parser Lexer just has a comma now. I thought about adding the comma operator but that didn't seem worth the trouble. The AST has two new additions. Function call expressions and function declarations (which are rebranded and improved…

After eight</a> grueling (not really) chapters of Writing a C Compiler</a>, time to implement more assembly instructions. Functions! Linkage! Commas!

Lexer, AST, and Parser</h2>
Lexer just has a comma now. I thought about adding the comma operator but that didn't seem worth the trouble.
The AST has two new additions. Function call expressions and function declarations (which are rebranded and improved function definitions)! Other changes include how the structures themselves are defined. A program is now a list of function declarations, instead of just one. How about that?
These are the new AST nodes. I am not sure these compile or not yet, which I will find out when I am done with the parser. The use of `SegmentedList</code> is discussed a couple of chapters ago as a more Arena-friendly collection type.`
pub const Prgm = struct { funcs: std.SegmentedList(FuncDecl, 0), }; pub const Block = struct { body: std.SegmentedList(BlockItem, 0), }; pub const BlockItem = union(enum) { D: Decl, S: Stmt, }; pub const Decl = union(enum) { F: FuncDecl, V: VarDecl, }; pub const FuncDecl = struct { name: []const u8, params: std.SegmentedList(Identifier, 0), block: ?Block, }; pub const VarDecl = struct { name: Identifier, init: ?Expr, }; pub const Expr = union(enum) { // snip -- func_call: struct { Identifier, std.SegmentedList(Expr, 0) }, }; // This was implemented last chapter fixing the Segmentation Fault! pub const Identifier = union(enum) { name: []const u8, idx: utils.StringInterner.Idx, };</code></pre> It is going to be annoying fixing all the type errors throughout. Nonetheless, the parsing grammar for these new node types are going to change significantly. Here is. This is the new, tentative, parse_prgm</code>. I am not sure this is entirely correct yet.
pub fn parse_prgm( arena: std.mem.Allocator, tokens: lexer.Tokenizer, ) Error!ast.Prgm { var funcs: std.SegmentedList(ast.FuncDecl, 0) = .{}; while (tokens.next()) |next_token| { tokens.put_back(next_token); const func_decl = try parse_func_decl(arena, tokens); try funcs.append(arena, func_decl); } return .{ .funcs = funcs }; }</code></pre> parse_func_decl</code> is the same as the old parse_func_def</code>, but with optional parameters and an optional body. Ok maybe not the same, it is a behemoth. And all this is going to get significantly more complex when adding different types than int</code>.
fn parse_func_decl( arena: std.mem.Allocator, tokens: lexer.Tokenizer, ) Error!ast.FuncDecl { // same old try expect(.type_int, tokens); const name = try expect(.identifier, tokens); // new stuff !! var params: std.SegmentedList(ast.Identifier, 0) = .{}; { // params try expect(.l_paren, tokens); const next_token = tokens.next() orelse return error.SyntaxError; // labelled switch to loop over multiple parameters. params: switch (next_token.tag) { // old bahaviour is this: .keyword_void => try expect(.r_paren, tokens), // new optional parameters .type_int => { const ident = try expect(.identifier, tokens); try params.append(arena, .{ .name = ident }); const next_next = tokens.next() orelse return error.SyntaxError; // loops back here. this would be significantly more annoying // to write without labeled switch switch (next_next.tag) { .comma => { try expect(.type_int, tokens); continue :params .type_int; }, .r_paren => {}, // could just return here but where is the fun then? else => continue :params .invalid, } }, else => return error.SyntaxError, } } const block = block: { const peeked = tokens.next() orelse return error.SyntaxError; switch (peeked.tag) { .semicolon => break :block null, .l_brace => { tokens.put_back(peeked); break :block try parse_block(arena, tokens); }, else => return error.SyntaxError, } }; return .{ .name = name, .params = params, .block = block }; }</code></pre> There is one big item left, which is BlockItem</code>, which can be a function declaration as well as a variable declaration, and it is not possible to know which is which from the token type_int</code> as done before. The most straightforward way to implement it in the current code base is as follows: look for an type_int</code> token, verify there is an identifier token afterwards, without recording it, then see what the third token is. If it is a semicolon</code> or an equals</code>, it is a variable; if it is a parenthesis, it is a function; otherwise it is illegal. Then the parser is rewinded to the int</code> and the correct function is called. In later chapters, with global variables, it will be apparent that the only place which only accepts one type of declarations is the for</code> loop statement, but I will cross that bridge when I get to it.
fn parse_decl( arena: std.mem.Allocator, tokens: lexer.Tokenizer, ) Error!ast.Decl { const int_token = tokens.next() orelse return error.NotEnoughJunk; if (int_token.tag != .type_int) return error.SyntaxError; _ = try expect(.identifier, tokens); const new_token = tokens.next() orelse return error.NotEnoughJunk; tokens.put_back(int_token); switch (new_token.tag) { .semicolon, .equals => return .{ .V = try parse_var_decl(arena, tokens) }, .l_paren => return .{ .F = try parse_func_decl(arena, tokens) }, else => return error.SyntaxError, } }</code></pre> Parsing function calls is a new challenge. Previously, any identifier is immediately assumed to be a variable. But now, if the identifier is followed by parenthesis, it could be a function call with an arbitrary number of parameters. The new identifier</code> case exhibits a serious case of rightward drift.
.identifier => { const next_token = tokens.next() orelse return error.NotEnoughJunk; const name = tokens.buffer[current.loc.start..current.loc.end]; switch (next_token.tag) { .l_paren => return .{ .func_call = .{ .{ .name = name }, try parse_args(arena, tokens), } }, else => { tokens.put_back(next_token); return .{ .@"var" = .{ .name = name } }; }, } }, // elsewhere: fn parse_args( arena: std.mem.Allocator, tokens: lexer.Tokenizer, ) Error!std.SegmentedList(ast.Expr, 0) { // assumes l_paren already consumed var ret: std.SegmentedList(ast.Expr, 0) = .{}; const current = tokens.next() orelse return error.NotEnoughJunk; args: switch (current.tag) { .r_paren => return ret, .comma => { const expr = try parse_expr(arena, tokens, 0); try ret.append(arena, expr); const n_token = tokens.next() orelse return error.NotEnoughJunk; continue :args n_token.tag; }, else => { // only actually relevant for the first argument. tokens.put_back(current); continue :args .comma; }, } }</code></pre>
Semantic Analysis</h2>
This is a bit more involved than usual this chapter. In addition to variable resolution, the compiler needs to do type checking! Do all declarations of functions (which can repeat), have the same number of parameters?*
Starting with the easier stuff, the identifier resolution pass should handle the new function syntax. Start with function calls. Here is the added part in `resolve_expr</code>.`
.func_call => |f| { if (bp.variable_map.get(f.@"0".name)) |entry| { f.@"0" = .{ .idx = entry.name }; var iter = f.@"1".iterator(0); while (iter.next()) |item| try resolve_expr(bp, item); } else return error.Undeclaredfunction; },</code></pre> Resolving function declarations had me move the creation of the main variable map back into resolve_prgm</code> instead, and create a new inner map for every function. Also, I need to update the Entry</code> type of the variable map. This is the new Entry</code>.
const Entry = struct { name: utils.StringInterner.Idx, scope: enum { local, parent } = .local, linkage: enum { none, external } = .none, // <-- new };</code></pre> Then this is resolve_func_decl</code>, and the inner parameters resolution, which is really just a cheap copy of resolve_var_decl</code> itself rebranded resolve_decl</code>.
fn resolve_func_decl( bp: Boilerplate, func_decl: ast.FuncDecl, ) Error!void { if (bp.variable_map.get(func_decl.name)) |prev| if (prev.scope == .local and prev.linkage != .external) return error.DuplicateFunctionDecl; try bp.variable_map.put(bp.gpa, func_decl.name, .{ .name = try bp.strings.get_or_put(bp.gpa, func_decl.name), .scope = .local, .linkage = .external, }); var variable_map = try bp.variable_map.clone(bp.gpa); defer variable_map.deinit(bp.gpa); var iter = variable_map.valueIterator(); while (iter.next()) |value| value.* = .{ .name = value.name, .scope = .parent, .linkage = value.linkage, }; const inner_bp = bp.into_ineer(&variable_map); var iter = func_decl.params.iterator(0); while (iter.next()) |param| { // a cheap imitation of `resolve_var_decl` // should pribably be in its own function. if (inner_bp.variable_map.get(param.name)) |entry| if (entry.scope == .local) return error.DuplicateVariableDecl; const unique_name = try inner_bp.make_temporary(param.name); try inner_bp.variable_map.put(inner_bp.gpa, param.name, .{ .name = unique_name }); param.* = .{ .idx = unique_name }; } if (func_decl.block) |block| try resolve_block(inner_bp, null, block); }</code></pre> One more thing, there is need to check that block level function declarations have no body. I am going to do that in resolve_block</code>.
fn resolve_block( bp: Boilerplate, current_label: ?utils.StringInterner.Idx, block: ast.Block, ) Error!void { var iter = block.body.iterator(0); while (iter.next()) |item| switch (item.) { .S => |s| try resolve_stmt(bp, current_label, s), .D => |d| switch (d.) { .F => |f| if (f.block) |_| return error.IllegalFuncDefinition else try resolve_func_decl(bp, f), .V => |v| try resolve_var_decl(bp, v), }, }; }</code></pre> Before delving into type checking, the book suggests to run the test suite, but expect a number of failures. Thankfully, I can check the individual folders separately using the eye test, without running the test suite in the official manner, I can tell that the compiler is passing all the right files it should at this stage, even the ones in invalid_types</code>.
Type checking</h2> The Book has the type checking done in its own pass. At first, I tried just stuffing the type checking logic right into the same identifier resolution pass. But the actual problem was that I needed a separate data structure anyway, since function declarations have to match even when they are in different scopes. So I am still doing it in the same run, but with a separate data structure. The type checking consists mostly of the following: not using the same identifier for both int</code>s and functions, making sure functions always have the same number of parameters in all declarations, and make sure a function is not defined (with a body) twice. A new data structure would be needed to stuff this info, global throughout the whole file.^{1</a> A hashmap taking the unique identifiers as keys and their types as values. The type is either an integer or a function with defined arity (number of parameters). I also need to track whether a function has been defined or not.}
const TypeMap = std.AutoHashMapUnmanaged( u32, Type, ); const Type = union(enum) { int, func: struct { arity: usize, defined: bool, }, };</code></pre> Then adding a pointer to it to Boilerplate</code>, and adjusting resolve_prgm</code> as follows.
pub fn resolve_prgm( gpa: std.mem.Allocator, strings: utils.StringInterner, prgm: ast.Prgm, ) Error!void { var variable_map: VariableMap = .empty; defer variable_map.deinit(gpa); var type_map: TypeMap = .empty; defer type_map.deinit(gpa); const bp: Boilerplate = .{ .gpa = gpa, .strings = strings, .variable_map = &variable_map, .type_map = &type_map, }; var iter = prgm.funcs.iterator(0); while (iter.next()) |item| try resolve_func_decl(bp, item); }</code></pre> What follows next is lots of annoying boilerplate. I must make sure every time I add something to a variable_map</code>, I am adding its new name (if any) to type_map</code>. Hairier than usual logic, but should try to straighten it out before stuffing it in a Boilerplate</code> method. For example, in resolve_finc_decl</code>, adding a name to variable_map</code> and type_map</code> is done as follows:
{ const nname = try bp.strings.get_or_put(bp.gpa, func_decl.name); try bp.variable_map.put(bp.gpa, func_decl.name, .{ .name = nname, .scope = .local, .linkage = .external, }); const gop = try bp.type_map.getOrPut(bp.gpa, nname.real_idx); if (gop.found_existing) { if (gop.value_ptr.* != .func or gop.value_ptr.func.arity != func_decl.params.count()) { return error.TypeError; } else if (gop.value_ptr.func.defined and func_decl.block != null) { return error.DuplicateFunctionDef; } } else gop.value_ptr.* = .{ .func = .{ .arity = func_decl.params.count(), .defined = func_decl.block != null, } }; }</code></pre> A similar thing to do in resolve_var_decl</code>, and inside the small tidbit in resolve_func_decl</code> that resolves parameters. This is how it looks like.
{ const gop = try bp.type_map.getOrPut(bp.gpa, unique_name.real_idx); if (gop.found_existing) { if (gop.value_ptr.* != .int) { return error.TypeError; } } else gop.value_ptr.* = .int; }</code></pre> There does not seem enough shared logic right now to try and DRY these. Maybe later. What is left is checking these things in function calls and variable declarations. They are both very funny looking.
.@"var" => |name| { if (bp.variable_map.get(name.name)) |un| { if (bp.type_map.get(un.name.real_idx).? == .int) // unwrap optional expr.* = .{ .@"var" = .{ .idx = un.name } } else return error.TypeError; } else return error.UndeclaredVariable; }, .func_call => |f| { if (bp.variable_map.get(f.@"0".name)) |entry| { const t = bp.type_map.get(entry.name.real_idx).?; if (t == .func and t.func.arity == f.@"1".count()) { f.@"0" = .{ .idx = entry.name }; var iter = f.@"1".iterator(0); while (iter.next()) |item| try resolve_expr(bp, item); } else return error.TypeError; } else return error.UndeclaredFunction; },</code></pre> I think this should be it. I checked for functions being defined twice/ I checked that functions should be functions and types should be types. I checked all functions with the same name should have the same arity. zig build</code> returns no errors. What is left? The proof of the pudding is in the test suite. Time to run the test suite. (which now applies --latest-only</code> by default as not to take too long.)
`% paella ❱ zig build submit -- --chapter 9 --stage validate ---------------------------------------------------------------------- Ran 61 tests in 157.089s OK</code></pre> Phew. Mind you this does not mean the logic is correct. It just means it is failing the ones it should fail and passing the ones it should pass. The full test suite passes as well, which is cool.`
I took the time to refactor out the common logic between function parameters and variable declarations. Zig's `comptime</code> allows some tricks that Rust would torture me for,``2</a> forcing me to use a trait or some weird amalgamation of const generics. It turned out most of the logic is for identifiers, except for initializers in variable declarations. The new function follows.`
fn resolve_var_decl( comptime T: enum { param, @"var" }, // anonymous types yay bp: Boilerplate, item: switch (T) { // can simply be `if` but this is more readable i think .@"var" => ast.VarDecl, .param => ast.Identifier, }, ) Error!void { const identifier = switch (T) { // pulling out the common logic .@"var" => &item.name, .param => item, }; if (bp.variable_map.get(identifier.name)) |entry| if (entry.scope == .local) return error.DuplicateDecl; const unique_name = try bp.make_temporary(identifier.name); try bp.variable_map.put(bp.gpa, identifier.name, .{ .name = unique_name }); { // TYPE CHECKING const gop = try bp.type_map.getOrPut(bp.gpa, unique_name.real_idx); if (gop.found_existing) { if (gop.value_ptr. != .int) return error.TypeError; } else gop.value_ptr.* = .int; } identifier.* = .{ .idx = unique_name }; if (T == .@"var") // logic unique to declarations if (item.init) |expr| try resolve_expr(bp, expr); } // called like this, inside `resolve_func_decl` while (params.next()) |param| try resolve_var_decl(.param, inner_bp, param);</code></pre> I ran the test suite again (and the eye tests) after this and everything seems to work out. Internal Representation</h2> After a long drought, finally time to update the IR syntax tree and generation. Which means new assembly stuff later. Couldn't the Book stick to adding more control flow constructs for ever? Maybe function calls can be implemented by just jumping around. Is that a thing? The syntax tree updates mirror the AST's. const Identifier = utils.StringInterner.Idx; // type alias pub const Prgm = struct { funcs: std.ArrayListUnmanaged(FuncDef), // <-- }; pub const FuncDef = struct { name: Identifier, params: std.ArrayListUnmanaged(Identifier), // <-- instrs: std.ArrayListUnmanaged(Instr), }; pub const Instr = union(enum) { func_call: struct { name: Identifier, args: std.ArrayListUnmanaged(Value), dst: Value, }, // rest of the owl };</code></pre> And the rest is pretty much the same, sans a few updates to the pretty printers and deinitializers. Note that there are no function declarations, as they are discarded in this stage after being done with the type checking. prgm_emit_ir</code> is simply a small update from the one-function version to the many-functions version, skipping over declarations without bodies pub fn prgm_emit_ir( alloc: std.mem.Allocator, strings: utils.StringInterner, prgm: const ast.Prgm, ) Error!ir.Prgm { var funcs: std.ArrayListUnmanaged(ir.FuncDef) = try .initCapacity( alloc, prgm.funcs.len, ); var iter = prgm.funcs.constIterator(0); while (iter.next()) |f| if (f.block) |_| { // skip empty declarations const fir = try func_def_emit_ir(alloc, strings, f); try funcs.append(alloc, fir); }; return .{ .funcs = funcs }; }</code></pre> func_def_emit_ir</code> is also almost exactly the same, except that the identifiers are moved over. fn func_def_emit_ir( alloc: std.mem.Allocator, strings: utils.StringInterner, func_def: const ast.FuncDecl, ) Error!ir.FuncDef { const name = try strings.get_or_put(alloc, func_def.name); var params: std.ArrayListUnmanaged(utils.StringInterner.Idx) = try .initCapacity( alloc, func_def.params.count(), ); var iter = func_def.params.constIterator(0); while (iter.next()) |param| try params.append(alloc, param.idx); var instrs: std.ArrayListUnmanaged(ir.Instr) = .empty; const bp: Boilerplate = .{ .alloc = alloc, .strings = strings, .instrs = &instrs, }; try block_emit_ir(bp, &func_def.block.?); try instrs.append(alloc, .{ .ret = .{ .constant = 0 } }); return .{ .name = name, .params = params, .instrs = instrs }; }</code></pre> Function call expressions are new, even though they follow the same pattern as all other expressions. .func_call => |f| { var args: std.ArrayListUnmanaged(ir.Value) = try .initCapacity( bp.alloc, f.@"1".count(), ); const dst = .{ .variable = try bp.make_temporary("fn") }; var iter = f.@"1".constIterator(0); while (iter.next()) |e| { const v = try expr_emit_ir(bp, e); try args.append(bp.alloc, v); } try bp.append(.{ .func_call = .{ .name = f.@"0".idx, .args = args, .dst = dst, } }); return dst; },</code></pre> The last thing left to do here is to make sure that function declaration as block items are skipped as well. fn block_emit_ir( bp: Boilerplate, block: const ast.Block, ) Error!void { var iter = block.body.constIterator(0); while (iter.next()) |item| switch (item.) { .S => |s| try stmt_emit_ir(bp, s), .D => |d| if (d == .V) try var_decl_emit_ir(bp, &d.V), // <- }; }</code></pre>Small Detour Back to Type Checking</h3> I am honestly not quite sure about some decisions up to now. For example, if function declarations are discarded, why are their parameters given unique identities at all? Maybe I should go back and simply check the count (and ideally the types, but there are no types in here). This would change the end of resolve_func_decl</code> to the following, instead of the if statement only encasing the last line. Since the count is checked earlier if (func_decl.block) |block| { var params = func_decl.params.iterator(0); while (params.next()) |param| try resolve_var_decl(.param, inner_bp, param); try resolve_block(inner_bp, null, block); }</code></pre> This passes all validations tests, except one. /* Duplicate parameter names are illegal in function declarations as well as definitions / int foo(int a, int a); int main(void) { return foo(1, 2); } int foo(int a, int b) { return a + b; }</code></pre> Ah well. Amusingly, at least according to the LLM I asked, int foo(int, int)</code> is a legal declaration. Anyway, this was a failed detour. Assembly Generation</h2> This is the first serious brush in the Book with the System V ABI, the most common binary interface for Unixes. As there are currently no types more complex than int</code>, all the compiler needs to worry about is stuffing parameters in the right registers. (And for function bodies, retrieving them from the right registers). The IR has not concerned itself with this, relying on the surrounding passes to make sense out of it. In my Rust implementation, I used clever iterator combinators to write the logic for this section. I am kind of curious to see how it will turn out in Zig. The first step, as usual, is to update the assembly syntax tree. A program needs to be redefined as a list of functions, and there are new instructions and new registers. Some necessary refactorings should be timed now as well. This is assembly.Prgm</code>. pub const Prgm = struct { funcs: std.ArrayListUnmanaged(FuncDef), pub fn fixup( self: @This(), alloc: std.mem.Allocator, ) !void { for (self.funcs.items) |func| { // functions called here changed from taking Prgm to FuncDef // ideally this should live under FuncDef, but this is fine for now const depth = try pass_pseudo.replace_pseudos(alloc, func); try func.instrs.insert(alloc, 0, .{ .allocate_stack = @abs(depth), }); try pass_fixup.fixup_instrs(alloc, func); } }</code></pre> The new instructions are simple additions. However, I am using two type aliases here: Depth</code> for an unsigned version of stack depth, and Identifier</code> for utils.StringInterner.Idx</code>. allocate_stack: Depth, // old dealloc_stack: Depth, push: Operand, call: Identifier,</code></pre> And aside from the new Registers, which I will not bore you with, this is pretty much it.^{3</a> Implementing the codegen is the next step. parameters in function definitions need to be taken from their correct register and stack positions; and function calls need to stuff them there. prgm_to_asm</code>, the main entry point, is straightforward.}pub fn prgm_to_asm( alloc: std.mem.Allocator, prgm: ir.Prgm, ) !assembly.Prgm { var funcs: std.ArrayListUnmanaged(assembly.FuncDef) = try .initCapacity( alloc, prgm.funcs.items.len, ); for (prgm.funcs.items) |func| try funcs.append( alloc, try func_def_to_asm(alloc, func), ); return .{ .funcs = funcs }; }</code></pre> For functions, it is slightly different. The first six parameters should be passed in these registers in this specific order: DI</code>, SI</code>, DX</code>, CX</code>, R8</code>, and R9</code>. Remaining arguments are pushed into the stack in reverse order. So normally, I will just assign a constant for them registers. const REGISTERS: [6]assembly.Operand.Register = .{ .DI, .SI, .DX, .CX, .R8, .R9 };</code></pre> In func_def_to_asm</code> itself, a zipped for</code> loop is perhaps the most straightforward way of doing this. The first section is simple enough. And since the remaining parameters are pushed into the stack at function call in reverse order, they are in the correct order here. Starting from a 16 stack</code> offset, they are moved one by one. Luckily, this same loop can be used! for (func_def.params.items, 0..) |param, idx| if (idx < REGISTERS.len) try instrs.append(alloc, .{ .mov = .init( .{ .reg = REGISTERS[idx] }, .{ .pseudo = param }, ) }) else { const offset = (idx - REGISTERS.len + 2) 8; // 16, 24, etc try instrs.append(alloc, .{ .mov = .init( .{ .stack = @intCast(offset) }, .{ .pseudo = param }, ) }); };</code></pre> Implementing function calls is a lot more involved. First, the stack needs to be aligned properly at 16, as per the System V ABI. Copying the passed in expressions to the input registers is easy, but reversing the rest of them requires some shenanigans. First is to have a stack allocated array with the maximum possible size because it is unknown at the outset what the size of the returned slice could be. // the return is of unknown size. // maximum possible size is parameter count * 2 + 4 var ret: std.ArrayListUnmanaged(assembly.Instr) = try .initCapacity(alloc, c.args.items.len 2 + 4);</code></pre> Then calculate the amount of arguments in the stack and the needed padding to 16. Zig has a saturating subtraction operator -|</code> that is perfect for this. const depth = c.args.items.len -| REGISTERS.len; const padding: assembly.Instr.Depth = if (depth % 2 == 0) 8 else 0; if (padding > 0) try ret.append(alloc, .{ .allocate_stack = padding }); // 1</code></pre> The numbering in the comments is me keeping track of instructions that do not depend on parameters count. After that comes putting the values in their respective registers, and the stack.4</a> for (c.args.items, 0..) |arg, idx| { if (idx >= REGISTERS.len) break; try ret.append(alloc, .{ .mov = .init( .{ .reg = REGISTERS[idx] }, value_to_asm(arg), ) }); } for (0..depth) |idx| { const v_ir = c.args.items[c.args.items.len - 1 - idx]; const v_asm = value_to_asm(v_ir); switch (v_asm) { .imm, .reg => try ret.append(alloc, .{ .push = v_asm }), else => try ret.appendSlice(alloc, &.{ .{ .mov = .init(v_asm, .{ .reg = .AX }) }, .{ .push = .{ .reg = .AX } }, }), } }</code></pre> I think this should work. 0..depth</code> will be .. nothing, and the loop will not run. If it is larger, it starts from the last item (at index len - , 1</code>), then subtracts the current index of the loop. And finally, dealing with the return value, and returning the slice. // emit call instruction try ret.append(alloc, .{ .call = c.name }); // 2 const bytes_to_remove = 8 depth + padding; if (bytes_to_remove != 0) try ret.append(alloc, .{ .dealloc_stack = bytes_to_remove }); // 3 try ret.append(alloc, .{ .mov = .init( .{ .reg = .AX }, value_to_asm(c.dst), ) }); // 4 return ret.items;</code></pre> Doing the eye test for codegen, I quickly noticed something stupid. I am moving the register's value to an immutable. Oops. int add(int x, int y); int main(void) { return add(1, 2); } // PROGRAM // FUNCTION main // allocate 4 // allocate 8 // mov DI -> imm 1 // mov SI -> imm 2 // call .Ladd // deallocate 8 // mov AX -> stack -4 // mov stack -4 -> AX // ret // mov imm 0 -> AX // ret</code></pre> Fixing that by switching two lines, the eye test passes fine. The test suite does not hit any errors (and, as a reminder, does not test beyond success and failure). After that comes the annoying fixup pass adjustments. The depth returned by replace_pseudos</code> is adjusted to save the depth of each function in a field in the function definition. And also, when allocating, rounding that up to the nearest multiple of 16. There is a neat trick to round up a number, n</code>, to the nearest multiple of 16. Basically (n + 15) & ~15</code>. Unfortunately, Zig makes this a pain to write because the integer type inference is not clever enough to understand ~15</code>. There in the standard library is a helpful function to do that math: std.mem.alignForward</code>. Kindly pointed to me by the Zig Discord. So I added this bit at the end of replace_pseudos</code>. func_def.depth = @intCast(pseudo_map.count() 4); const aligned = std.mem.alignForward(assembly.Instr.Depth, func_def.depth, 16); try func_def.instrs.insert(alloc, 0, .{ .allocate_stack = aligned });</code></pre> So, time to actually emit the assembly. Code Emission</h2> The changes here are pretty small. The new instructions are one thing, but there are new registers and new register sizes for push</code>, which takes 8-width registers. The logic for printing registers got pretty large so I put it in its own function. fn emit_register( reg: Operand.Register, width: usize, writer: anytype, ) !void { p: switch (width) { 1 => switch (reg) { .AX => try writer.print("%al", .{}), .DX => try writer.print("%dl", .{}), .CX => try writer.print("%cl", .{}), .DI => try writer.print("%dil", .{}), .SI => try writer.print("%sil", .{}), .R8 => try writer.print("%r8b", .{}), .R9 => try writer.print("%r9b", .{}), .R10 => try writer.print("%r10b", .{}), .R11 => try writer.print("%r11b", .{}), }, 4 => switch (reg) { .AX => try writer.print("%eax", .{}), .DX => try writer.print("%edx", .{}), .CX => try writer.print("%ecx", .{}), .DI => try writer.print("%edi", .{}), .SI => try writer.print("%esi", .{}), .R8 => try writer.print("%r8d", .{}), .R9 => try writer.print("%r9d", .{}), .R10 => try writer.print("%r10d", .{}), .R11 => try writer.print("%r11d", .{}), }, 8 => switch (reg) { .AX => try writer.print("%rax", .{}), .DX => try writer.print("%rdx", .{}), .CX => try writer.print("%rcx", .{}), .DI => try writer.print("%rdi", .{}), .SI => try writer.print("%rsi", .{}), .R8 => try writer.print("%r8", .{}), .R9 => try writer.print("%r9", .{}), .R10 => try writer.print("%r10", .{}), .R11 => try writer.print("%r11", .{}), }, else => continue :p 4, // default case } }</code></pre> And then in the format function just do the following. There is a bit of redundancy regarding the 4 as a default case. You are not paranoid if they are out to get you! .reg => |r| try emit_register(r, options.width orelse 4, writer),</code></pre> Running the test suite, I get into 16 failures. Oh come on. Most of them seem to be UnrecognizedFlag</code>, which is the error I have in the compiler driver for flags that are unrecognized. That is what I get for not reading the text and jumping straight to the tables. There is a tidbit there about recognizing a -c</code> flag, which is the gcc</code> flag for creating object files instead of executables. This is a small change to the argument parser. That is the new one: pub fn parse_args() !Args { var args = std.process.args(); _ = args.skip(); var path: ?[:0]const u8 = null; var mode: Mode = .compile; var c_flag = false; // new while (args.next()) |arg| { if (arg[0] == '-') { if (arg[1] == 'c') // new c_flag = true else mode = std.meta.stringToEnum(Mode, arg[2..]) orelse return error.UnrecognizedFlag; } else if (path == null) path = arg else return error.PathDuplicated; } return .{ .path = path orelse return error.PathNotFound, .mode = mode, .c_flag = c_flag, // new }; }</code></pre> And much below that, when calling the assembler, the -c</code> flag is passed if c_flag</code> is true. And changing the extension to .o</code>. So it becomes the following (changing the extension itself is done elsewhere in a bit of rather annoying code). This is probably the nicest way of doing it. { // assembler var child = std.process.Child.init( if (args.c_flag) &.{ "gcc", "-c", asm_out, "-o", obj } else &.{ "gcc", asm_out, "-o", exe }, gpa, ); const term = try child.spawnAndWait(); if (!std.meta.eql(term, .{ .Exited = 0 })) return error.AssemblerFail; try std.fs.cwd().deleteFile(asm_out); // cleanup }</code></pre> Now running the test suite for real. Debugging</h2> On the plus side, all the programs are compiling and running. On the negative side, I got a lot of bad return codes. There are logic mistakes. Also 3 errors relating to unicode and timeouts? I do not get it. The test suite's output is generally jumbled up and I find it hard to process. Having said that, the easiest way to attack the problem is to look at the individual files and compiles them myself. UnicodeDecodeError</h3> This is one of the weird errors, Nora Sandler's comments and all. The program should call the system's putchar</code>, which prints a character to standard out. #ifdef SUPPRESS_WARNINGS #pragma GCC diagnostic ignored "-Wunused-parameter" #endif int putchar(int c); / Make sure we can correctly manage calling conventions from the callee side * (by accessing parameters, including parameters on the stack) and the caller side * (by calling a standard library function) in the same function / int foo(int a, int b, int c, int d, int e, int f, int g, int h) { putchar(h); return a + g; } int main(void) { return foo(1, 2, 3, 4, 5, 6, 7, 65); }</code></pre> This is the output for each stage. PARSING FUNCTION putchar c FUNCTION foo a b c d e f g h (putchar h); RETURN (+ a g) FUNCTION main RETURN (foo 1 2 3 4 5 6 7 65) ================================ VALIDATION FUNCTION putchar c.0 FUNCTION foo a.1 b.2 c.3 d.4 e.5 f.6 g.7 h.8 (putchar h.8); RETURN (+ a.1 g.7) FUNCTION main RETURN (foo 1 2 3 4 5 6 7 65) ================================ IR FUNCTION foo fn.9 <- putchar(h.8) add.10 <- a.1 + g.7 ret add.10 ret 0 FUNCTION main fn.11 <- foo(1, 2, 3, 4, 5, 6, 7, 65) ret fn.11 ret 0 ================================ CODEGEN FUNCTION foo allocate 48 mov DI -> stack -4 mov SI -> stack -8 mov DX -> stack -12 mov CX -> stack -16 mov R8 -> stack -20 mov R9 -> stack -24 mov stack 16 -> R10 mov R10 -> stack -28 mov stack 24 -> R10 mov R10 -> stack -32 allocate 8 mov stack -32 -> DI call .Lputchar deallocate 8 mov AX -> stack -36 mov stack -4 -> R10 mov R10 -> stack -40 mov stack -28 -> R10 add R10 -> stack -40 mov stack -40 -> AX ret mov imm 0 -> AX ret FUNCTION main allocate 16 allocate 8 mov imm 1 -> DI mov imm 2 -> SI mov imm 3 -> DX mov imm 4 -> CX mov imm 5 -> R8 mov imm 6 -> R9 push imm 65 push imm 7 call .Lfoo deallocate 24 mov AX -> stack -4 mov stack -4 -> AX ret mov imm 0 -> AX ret</code></pre> Hold on, before going into assembly, I spot a weird thing here. Why is the call to foo</code> is preceded by .L</code>. This is probably a formatting error which does not matter. But more importantly, the numbers for deallocations seem weird. Why is it deallocating 24? Let's review the logic in instr_to_asm</code> in .func_call</code>. const bytes_to_remove = 8 depth + padding; if (bytes_to_remove != 0) try ret.append(alloc, .{ .dealloc_stack = bytes_to_remove }); // 3</code></pre> Eh, this makes sense. Counting the arguments passed on the stack there, there are 2. So why is there padding? const padding: assembly.Instr.Depth = if (depth % 2 == 0) 8 else 0; // <--- here if (padding != 0) try ret.append(alloc, .{ .allocate_stack = padding }); // 1</code></pre> Oh I am assigning the padding in reverse. If the number of arguments is even, there should be no padding. Silly me. This does not actually deal with the error I got for this file, which is this: UnicodeDecodeError: 'utf-8' codec can't decode byte 0x90 in position 0: invalid start byte</code></pre> This might be the valued printed by putchar</code> failing to read. However, only way to know is to run the test suit again. % paella ❱ zig build submit --release=safe -- --chapter 9 # many moths later ---------------------------------------------------------------------- Ran 61 tests in 60.822s FAILED (failures=12)</code></pre> Hey at least no weird UTF-8 errors. That's 7 less failures than last time (which was 16 failures and 3 errors). AssertionError</h3> Note: Please do not rad this section. It is embarrassing. </blockquote> This is a more readable error than the last one. AssertionError: Incorrect behavior in chapter_9/valid/stack_arguments/test_for_memory_leaks Bad return code: expected 1 and got 0</code></pre> I can work with this. This is the C file in question. These are a lot of arguments. / Make sure stack arguments are deallocated correctly after returning from a function call; also test passing variables as stack arguments / #ifdef SUPPRESS_WARNINGS #pragma GCC diagnostic ignored "-Wunused-parameter" #endif int lots_of_args(int a, int b, int c, int d, int e, int f, int g, int h, int i, int j, int k, int l, int m, int n, int o) { return l + o; } int main(void) { int ret = 0; for (int i = 0; i < 10000000; i = i + 1) { ret = lots_of_args(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ret, 13, 14, 15); } return ret == 150000000; }</code></pre> I will skip the whole parsing to IR thing and simply give you here the last codegen, with added comments. It is huge. PROGRAM FUNCTION lots_of_args allocate 64 mov DI -> stack -4 ; a mov SI -> stack -8 ; b mov DX -> stack -12 ; c mov CX -> stack -16 ; d mov R8 -> stack -20 ; e mov R9 -> stack -24 ; f mov stack 16 -> R10 mov R10 -> stack -28 ; g mov stack 24 -> R10 mov R10 -> stack -32 ; h mov stack 32 -> R10 mov R10 -> stack -36 ; i mov stack 40 -> R10 mov R10 -> stack -40 ; j mov stack 48 -> R10 mov R10 -> stack -44 ; k mov stack 56 -> R10 mov R10 -> stack -48 ; l mov stack 64 -> R10 mov R10 -> stack -52 ; m mov stack 72 -> R10 mov R10 -> stack -56 ; n mov stack 80 -> R10 mov R10 -> stack -60 ; o mov stack -48 -> R10 mov R10 -> stack -64 ; l mov stack -60 -> R10 ; o add R10 -> stack -64 ; l + o mov stack -64 -> AX ret mov imm 0 -> AX ret FUNCTION main allocate 32 mov imm 0 -> stack -4 ; ret mov imm 0 -> stack -8 ; i => .Lst_for.16 cmp imm 10000000 -> stack -8 mov imm 0 -> stack -12 setl stack -12 cmp imm 0 -> stack -12 jmpe .Lbr_for.16 allocate 8 ; odd number of arguments ; register arguments mov imm 1 -> DI ; a mov imm 2 -> SI ; b mov imm 3 -> DX ; c mov imm 4 -> CX ; d mov imm 5 -> R8 ; e mov imm 6 -> R9 ; f ; stack arguments push imm 15 ; o push imm 14 ; n push imm 13 ; m mov stack -4 -> AX ; ret into l push AX ; l push imm 11 ; k push imm 10 ; j push imm 9 ; i push imm 8 ; h push imm 7 ; g call lots_of_args deallocate 80 ; why is this 80? 9 pushes + padding mov AX -> stack -16 ; l + o here mov stack -16 -> R10 mov R10 -> stack -4 ; assign to ret => .Lcn_for.16 mov stack -8 -> R10 mov R10 -> stack -20 add imm 1 -> stack -20 mov stack -20 -> R10 mov R10 -> stack -8 jmp .Lst_for.16 => .Lbr_for.16 cmp imm 150000000 -> stack -4 mov imm 0 -> stack -24 sete stack -24 mov stack -24 -> AX ret mov imm 0 -> AX ret</code></pre> I am actually at a loss. All this seems to make sense. The generated assembly is more of the same. Let us see another failure: AssertionError: Incorrect behavior in chapter_9/valid/arguments_in_registers/fibonacci Bad return code: expected 8 and got -11</code></pre> How would you even get -11? int fib(int n) { if (n == 0 || n == 1) { return n; } else { return fib(n - 1) + fib(n - 2); } } int main(void) { int n = 6; return fib(n); }</code></pre> This is the assembly this time. .globl _fib _fib: pushq %rbp ;; function prologue movq %rsp, %rbp subq $48, %rsp ;; allocate 48 movl %edi, -4(%rsp) ;; n cmpl $0, -4(%rsp) ;; does n equal 0? movl $0, -8(%rsp) sete -8(%rsp) cmpl $0, -8(%rsp) ;; is n == 0 true ? jne .Ltrue_or.2 cmpl $1, -4(%rsp) ;; does n equal 1? movl $0, -12(%rsp) sete -12(%rsp) cmpl $0, -12(%rsp) ;; is n == 1 true? jne .Ltrue_or.2 movl $0, -16(%rsp) jmp .Lend_or.3 .Ltrue_or.2: movl $1, -16(%rsp) .Lend_or.3: cmpl $0, -16(%rsp) ;; is the previous expression false? je .Lelse.7 movl -4(%rsp), %eax ;; if so just return n movq %rbp, %rsp popq %rbp ret jmp .Lend.8 .Lelse.7: movl -4(%rsp), %r10d ;; if not .. movl %r10d, -20(%rsp) ;; move n here subl $1, -20(%rsp) ;; n - 1 movl -20(%rsp), %edi ;; move n-1 to edi call _fib ;; call fib movl %eax, -24(%rsp) ;; stash result of fib(n-1) movl -4(%rsp), %r10d movl %r10d, -28(%rsp) ;; move n here subl $2, -28(%rsp) ;; n - 2 movl -28(%rsp), %edi ;; move n-1 to edi call _fib ;; call fib movl %eax, -32(%rsp) ;; stash result of fib(n-2) movl -24(%rsp), %r10d ;; stashed result of fib(n-1) movl %r10d, -36(%rsp) movl -32(%rsp), %r10d ;; stashed result of fib(n-2) addl %r10d, -36(%rsp) ;; add two results together movl -36(%rsp), %eax ;; move result to proper place movq %rbp, %rsp popq %rbp ret ;; the end .Lend.8: movl $0, %eax ;; this bit here is the useless return 0 movq %rbp, %rsp ;; added at the end of every function popq %rbp ret .globl _main _main: pushq %rbp movq %rsp, %rbp subq $16, %rsp movl $6, -4(%rsp) movl -4(%rsp), %edi call _fib movl %eax, -8(%rsp) movl -8(%rsp), %eax movq %rbp, %rsp popq %rbp ret movl $0, %eax movq %rbp, %rsp popq %rbp ret</code></pre> The logic seems fine. I am not debugging the logic for if</code>s and for</code>s as those test cases pass fine already. This sample here has no stack arguments yet it is still failing. This definitely means there is a memory corruption somewhere, but where? I am sure the smart ones of you spotted it. I am not that smart.^{5</a>} I figured maybe the mistake is from using the subshell. So I tried doing the test suite the manual way I did it previously. But nope, same result. The good news is that my subshell spell works perfectly. On a whim, which is most likely wrong, I thought of changing the sign of the stack offset for function bodies. (So they start from -16 downwards rather than 16 upwards). And that would not affect the failure in the fibonacci</code> example anyway. Surprisingly, that actually affected absolutely nothing: same number of failing cases. I am starting to think this is a parking_lot</code> bug. I moved to compare the codegen stage with my previous rust program, and it is identical. I moved on to comparing the assembly generated. Even using diff</code> with colors to compare the two assemblies. Then there I saw it. The logic is fine, but there is a typo: something I wrote many chapters ago. Behold: stack offsets: -8(%rsp)</code>. It should be from %rbp</code>. Now all the tests pass. Wonder how any of them did in the first place. Lessons Learned</h2> Spell checking is important.</li> diff --color</code> is a useful tool.</li> Unrelated to paella</code> itself, but I made some improvements to the build script, and learned more about jj</code> and git</code>. I think I will add git</code> tags to commits that finish each chapter, which would make browsing them easier.</li> This week I installed llm</code></a>, and had it set up to talk to the free version of Github Copilot. Really convenient and useful, and I used to spell check the articles. I will try some local models next but I do not expect they will do much with my Macbook Air M2.</li> Can I have typed integer literals or slightly greedier type inference in Zig please? It is absurd that ~15</code> just does not work.</li> </ol> One chapter left for Part 1. Unsure what to do next. Type errors between different files is very pointedly a not-my-problem. It is a linker error, while this is a compiler. ↩</a> </li> When will Rust have enums as proper const generics? Please, Rust. ↩</a> </li> To be honest, and for all chapters, I am skipping most of the reading and jumping through to the tables at the end of the section to implement the functions. I assume that is what the tables are for. ↩</a> </li> The Book's pseudocode gives different instructions to add if the IR value is converted to an immediate value, register, or a pseudo value. The weird part here is that, well until chapter 15 (where I stopped last time), the IR value is never converted to a register at this stage. This could be something in preparation for the optimizations in Part 3. ↩</a> </li> Gemini LLM told me this is fine. Though to be honest, Github Copilot pointed it out, but I missed it among the five useless things it also mentioned. ↩</a> </li> </ol> </section>

Chapter 9: Functions

Comments

Chapter 9: Functions

Code Emission</h2> The changes here are pretty small. The new instructions are one thing, but there are new registers and new register sizes for push</code>, which takes 8-width registers. The logic for printing registers got pretty large so I put it in its own function.</p>

UnicodeDecodeError</h3> This is one of the weird errors, Nora Sandler's comments and all. The program should call the system's putchar</code>, which prints a character to standard out.</p>

AssertionError</h3> Note: Please do not rad this section. It is embarrassing.</p> </blockquote> This is a more readable error than the last one.</p>

Comments