This is the final chapter of Part 1 of Writing a C Compiler. Something about static variables?
Lexer
The Book spends 15 pages talking about linkage and static variabeles and tentative declarations, etc, before it gets to the lexer. Only two new keywrods are needed: static and extern. This is the current keyword static map:
pub const keywords = std.StaticStringMap(Tag).initComptime(.{
.{ "int", .type_int },
.{ "return", .keyword_return },
.{ "void", .keyword_void },
.{ "if", .keyword_if },
.{ "else", .keyword_else },
.{ "do", .keyword_do },
.{ "while", .keyword_while },
.{ "for", .keyword_for },
.{ "break", .keyword_break },
.{ "continue", .keyword_continue },
.{ "static", .keyword_static },
.{ "extern", .keyword_extern },
});
As a small update to the lexer's API, I added a next_force function that returns an error union rather than an option, as it is easier to deal with at the call site.
pub inline fn next_force(self: *Tokenizer) !Token {
return self.next() orelse
return error.NotEnoughJunk;
}
// usage
var token = try tokens.next_force();
// rather than
var token = tokens.next() orlse return error.NotEnoughJunk;
AST and Parser
The parser requires deeper changes. First of all, as Prgm changed from a single function to multiple functions last chapter, now it is a list of declarations. Also, static and extern belong, by themselves, to a new semi-node for "storage class specifiers", that is an optional parameter for function and variable declarations. Since a declaration cannot be both static and extern, this makes it a simple enum.
pub const Prgm = struct {
funcs: std.SegmentedList(Decl, 0),
};
pub const StorageClass = enum { static, @"extern" };
pub const FuncDecl = struct {
sc: ?StorageClass, // <--
name: []const u8,
params: std.SegmentedList(Identifier, 0),
block: ?Block,
};
pub const VarDecl = struct {
sc: ?StorageClass, // <--
name: Identifier,
init: ?*Expr,
}
Changes to parse_prgm are simple enough. There already is a parse_decl so I will just use that one when iterating. Parsing specifiers is interesting and annoying, as I relied before on looking for the int token, now it can be anything! Consider these tqo equally valid variable declarations.
static int example1 = 1;
int static example2 = 2;
There is no set order. Whose genius idea was this? Thankfully I do not have to think of this on my own, as the book privdes a nice pseudocode functon to parse them. When I was doing my Rust implementation, where I was using nom for parsing, I could not actually figure out to make it nicer than what the Book already provided. Here is the function translated from pseudo code to Zig.1
fn parse_storage_class(
tokens: *lexer.Tokenizer,
) Error!?ast.StorageClass {
var type_seen = false;
var sc: ?ast.StorageClass = null;
while (tokens.next()) |nt| switch (nt.tag) {
.type_int => type_seen = true,
.keyword_static => sc = if (sc == null)
.static
else
return error.InvalidStorageClass,
.keyword_extern => sc = if (sc == null)
.@"extern"
else
return error.InvalidStorageClass,
else => {
tokens.put_back(nt);
break;
},
} else return error.NotEnoughJunk;
if (!type_seen) return error.InvalidTypeSpecifier;
return sc;
}
Then use this new function in both parse_func_decl and parse_variable_decl. In fact, it is probably easier right now to just simply unify the two into a horrendous giant amalgamation.
fn parse_decl(
arena: std.mem.Allocator,
tokens: *lexer.Tokenizer,
ty: union(enum) { @"var": ?ast.StorageClass, either },
) Error!ast.Decl {
const sc = if (ty == .@"var") ty.@"var" else try parse_storage_class(tokens);
const name = try expect(.identifier, tokens);
const new_token = try tokens.next_force();
switch (new_token.tag) {
.semicolon => return .{ .V = .{
.sc = sc,
.name = .{ .name = name },
.init = null,
} },
.equals => {
const expr = try parse_expr(arena, tokens, 0);
const expr_ptr = try utils.create(arena, expr);
try expect(.semicolon, tokens);
return .{ .V = .{
.sc = sc,
.name = .{ .name = name },
.init = expr_ptr,
} };
},
.l_paren => {
if (ty == .@"var") return error.SyntaxError;
var params: std.SegmentedList(ast.Identifier, 0) = .{};
const param_peek = try tokens.next_force();
params: switch (param_peek.tag) {
.keyword_void => try expect(.r_paren, tokens),
.type_int => {
const ident = try expect(.identifier, tokens);
try params.append(arena, .{ .name = ident });
const inner_param_peek = try tokens.next_force();
switch (inner_param_peek.tag) {
.comma => {
try expect(.type_int, tokens);
continue :params .type_int;
},
.r_paren => {},
else => continue :params .invalid,
}
},
else => return error.SyntaxError,
}
const block_peek = try tokens.next_force();
const block = block: {
switch (block_peek.tag) {
.semicolon => break :block null,
.l_brace => {
tokens.put_back(block_peek);
break :block try parse_block(arena, tokens);
},
else => return error.SyntaxError,
}
};
return .{ .F = .{
.sc = sc,
.name = name,
.params = params,
.block = block,
} };
},
else => return error.SyntaxError,
}
}
The ty parameter is because there is one place in the AST that requires a variable declaration specifically, which is the initial part of a for loop. (It is not comptime because I use to sneak in an already parsed sc value, as you will see.) Everywhere else can really take either declaration type.
This is the part in for loop parsing that deals with the new parsing functions.
const init: ast.Stmt.For.Init = init: {
const peeked = try tokens.next_force();
if (peeked.tag == .semicolon) break :init .none else {
tokens.put_back(peeked);
if (parse_storage_class(tokens)) |sc| {
const decl = try parse_decl(
arena,
tokens,
.{ .@"var" = sc }, // <-- snuck in
);
const decl_ptr = try utils.create(arena, decl.V); // <-- unwrapped
break :init .{ .decl = decl_ptr };
} else |_| { // <-- parse_sc already puts back any other token
const expr = try parse_expr(arena, tokens, 0);
const expr_ptr = try utils.create(arena, expr);
try expect(.semicolon, tokens);
break :init .{ .expr = expr_ptr };
}
}
};
Running the eye test I quickly ran into a bug. *Sigh.
Debugging the Parser
It failed on the first test, so obviously this is a bug in the general algorithm. With all the new changes all at once it is ahrder to pinpoint which one it is. I did not make a separate commit for every refactor, I am afraid. This is the C file it failed on (after removing comments).
int putchar (int ch);
int print_letters(void) {
static int i = 65;
putchar(i);
{
i = i + 1;
static int i = 97;
putchar(i);
i = i + 1;
}
putchar(10);
return 0;
}
int main(void) {
for (int i = 0; i < 26; i = i + 1)
print_letters();
}
Adding debugging printers to next() and put_back(), as done previously, will let me see where it failed in the file. I could also print the failed token's span, but that would require better architecture and more dedication. I get this stream of consciusness back. I added comments to each line, manually, to be honest, to track which function does which.
NEXT type_int 0-3 # parse_prgm
REWIND type_int 0-3 # parse_prgm
NEXT type_int 0-3 # parse_decl -> parse_storage_class
NEXT identifier 4-11 # parse_storage_class
REWIND identifier 4-11 # parse_storage_class
NEXT identifier 4-11 # parse_decl
NEXT l_paren 12-13 # parse_decl
NEXT type_int 13-16 # parse_decl # params
NEXT identifier 17-19 # parse_decl # params
NEXT r_paren 19-20 # parse_decl # params
NEXT semicolon 20-21 # parse_decl # block
NEXT type_int 22-25 # parse_prgm
REWIND type_int 22-25 # parse_prgm
NEXT type_int 22-25 # parse_decl -> parse_storage_class
NEXT identifier 26-39 # parse_storage_class
REWIND identifier 26-39 # parse_storage_class
NEXT identifier 26-39 # parse_decl
NEXT l_paren 39-40 # parse_decl
NEXT keyword_void 40-44 # parse_decl # params
NEXT r_paren 44-45 # parse_decl # params
NEXT l_brace 46-47 # parse_decl # block
REWIND l_brace 46-47 # parse_decl # block
NEXT l_brace 46-47 # parse_block
NEXT keyword_static 52-58 # parse_block
REWIND keyword_static 52-58 # parse_block
NEXT keyword_static 52-58 # parse_block_item
REWIND keyword_static 52-58 # parse_block_item
NEXT keyword_static 52-58 # .. oh
REWIND keyword_static 52-58
NEXT keyword_static 52-58
error: SyntaxError
Oh yeah here it is. I forgot to update it and parse_block_item still checks for whether something is a declaration or a statement using the int keyword. I could use a similar trick to what I did for the for loop where I can pass the parsed value in instead of peeking and parsing it again. This would require changes to parse_decls signature, so I will start with that. This is the current signature.
fn parse_decl(
arena: std.mem.Allocator,
tokens: *lexer.Tokenizer,
ty: union(enum) { @"var": ?ast.StorageClass, either },
) Error!ast.Decl {
const sc = if (ty == .@"var") ty.@"var" else try parse_storage_class(tokens);
// etc
Instead of smuggling the parsed value through ty, I could change ty to my earlier iteration of an enum, and pass whether it is parsed or not in another variable, like so.
fn parse_decl(
comptime ty: enum { @"var", either },
arena: std.mem.Allocator,
tokens: *lexer.Tokenizer,
parsed: union(enum) { yes:?ast.StorageClass, no },
) Error!ast.Decl {
const sc = if (parsed == .yes) parsed.yes else try parse_storage_class(tokens);
// etc
And changing the call sites, again, but no matter. Here is the new and improved parse_block_item, relying on parse_storage_class putting back any unrecognized tokens.
fn parse_block_item(
arena: std.mem.Allocator,
tokens: *lexer.Tokenizer,
) Error!ast.BlockItem {
if (parse_storage_class(tokens)) |sc|
return .decl(try parse_decl(.either, arena, tokens, .{ .yes = sc }))
else |_|
return .stmt(try parse_stmt(arena, tokens));
}
And voila! Running the parser on the same C file above renders the following AST (with some updated printing for variable declarations).
PROGRAM
FUNCTION putchar ch
FUNCTION print_letters
static VARIABLE i <- 65
(putchar i);
DO
(i <- (+ i 1));
static VARIABLE i <- 97
(putchar i);
(i <- (+ i 1));
(putchar 10);
RETURN 0
FUNCTION main
FOR VARIABLE i <- 0; (< i 26); (i <- (+ i 1))
(print_letters);
The eye test passes. The actual test suite passes. All is done and all is happy with the tiny world of this project.
Semantic Analysis
The main difference in here from the previous chapters is that the symbol table needs to survive beyond this phase, as it is used in assembly. So far, in my compiler, the info is not kept in ir_gen. This would probably have to change. Here my idea of doing type checking in the same pass as identifier resolution is put to the test for the first, and probably last, time.
One thing to note, is that variables that do have linkage (whether internal or external) do not get their name mangled, because their name is how the linker tracks them.
The first thing I will do is resolving file scope variables. Instead of mucking around in resolve_var_decl, it is much smaller code that I will inline in resolve_prgm immediately.
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.decls.iterator(0);
while (iter.next()) |item| switch (item.*) {
.F => |*f| try resolve_func_decl(bp, f),
// right here, never mind the `.name.name`.
// no type checking yet
.V => |*v| try variable_map.put(gpa, v.name.name, .{
.name = try strings.get_or_put(gpa, v.name.name),
.linkage = .has_linkage,
}),
};
}
Much of the complexity here is deferred in the Book to the type checking stage, so I presume I am heavily editing this part before the section is over. NExt comes resolve_var_decl. Unfortunately, some of the clever shenaningans I did to unify resolution for paramaters and variables are making this a bit more complex, but I persevere.
fn resolve_local_var_decl(
comptime T: enum { param, @"var" },
bp: Boilerplate,
item: switch (T) {
.@"var" => *ast.VarDecl,
.param => *ast.Identifier,
},
) Error!void {
const identifier, const sc: ?ast.StorageClass = switch (T) {
.@"var" => .{ &item.name, item.sc }, // <-- getting sc here
.param => .{ item, null },
};
if (bp.variable_map.get(identifier.name)) |prev|
if (prev.scope == .local)
if (!(prev.linkage == .has_linkage and sc == .@"extern")) // <--
return error.DuplicateDecl;
if (sc == .@"extern") { // <--
try bp.variable_map.put(bp.gpa, identifier.name, .{
.name = try bp.strings.get_or_put(bp.gpa, identifier.name),
.linkage = .has_linkage,
});
// no type checking yet
return;
}
// snip --
Regarding function declarations, the compiler should throw an error if a local function declaration is static. I am unsure where to put this check. I currently check if a block scope function declaration has a body (which it should not) in resolve_block, so maybe that is where I will stuff that check.
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 if (f.sc == .static) // <-- here
return error.TypeError
else
try resolve_func_decl(bp, f),
.V => |*v| try resolve_local_var_decl(.@"var", bp, v),
},
};
}
Next up is type checking. Instead of tracking each identifier's type in a type_map, the compiler would track the attributes.2 So this the previous entry in TypeMap:
const Type = union(enum) {
int,
func: struct {
arity: usize,
defined: bool,
},
};
This becomes the folloiwng. This is not identical to the Book's design as it has its entry as a tuple of type and attributes. I will cross that bridge if I come to it.
const Arrtibutes = union(enum) {
func: struct {
arity: usize,
defined: bool,
global: bool,
},
static: struct {
ubut: Init,
global: bool,
},
local,
const Init = union(enum) {
tentative,
initial: u64,
none,
};
};
Simply updating the existing TypeMap to have the new type as its value is enough for now. Now, back to writing code. Function declarations need to make some checks about their globality: whether they are static or not. Tracking defined functions is improved from last run as well.
{ // func_decl type checking
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 if (gop.value_ptr.func.global and // <-- new check
func_decl.sc == .static)
{
return error.ConflictingFuncDecls;
}
gop.value_ptr.func.defined |= func_decl.block != null; // <-- update
} else gop.value_ptr.* = .{ .func = .{
.arity = func_decl.params.count(),
.defined = func_decl.block != null,
.global = func_decl.sc != .static, // <-- new field
} };
}
File scope variable declarations, which I have stubbed in resolve_prgm above, also need to by type checked. This is significantly longer, and is a bit more complex than I can process at the moment of writing so I copied it from the book without trying to refactor. I am sure I made a mistake anyway.
.V => |*v| { // file scope variables
const nname = try strings.get_or_put(gpa, v.name.name);
try variable_map.put(gpa, v.name.name, .{
.name = nname,
.linkage = .has_linkage,
});
// TYPE CHECKING
var init_value: Arrtibutes.Init = if (v.init) |e| switch (e.*) {
.constant => |i| .{ .initial = i },
else => return error.NonConstantInit,
} else if (v.sc == .@"extern") .none else .tentative;
var global = v.sc != .static;
const gop = try type_map.getOrPut(gpa, nname.real_idx);
if (gop.found_existing) {
if (gop.value_ptr.* != .static)
return error.TypeError;
if (v.sc == .@"extern")
global = gop.value_ptr.static.global
else if (gop.value_ptr.static.global != global)
return error.ConflictingLinkage;
if (gop.value_ptr.static.init == .initial) {
if (init_value == .initial)
return error.ConflictingDefinitions;
init_value = gop.value_ptr.static.init;
} else if (init_value != .initial and
gop.value_ptr.static.init == .tentative)
{
init_value = .tentative;
}
}
gop.value_ptr.* = .{ .static = .{
.init = init_value,
.global = global,
} };
},
There is a strong argument to be made that this should live in its own function. Resolving local scope variables is equally annoying. You can probably tell I am bored with this already.
fn resolve_local_var_decl(
comptime T: enum { param, @"var" },
bp: Boilerplate,
item: switch (T) {
.@"var" => *ast.VarDecl,
.param => *ast.Identifier,
},
) Error!void {
const identifier, const sc: ?ast.StorageClass = switch (T) {
.@"var" => .{ &item.name, item.sc },
.param => .{ item, null },
};
if (bp.variable_map.get(identifier.name)) |prev|
if (prev.scope == .local)
if (!(prev.linkage != .none and sc == .@"extern"))
return error.DuplicateDecl;
if (sc == .@"extern") {
const nname = try bp.strings.get_or_put(bp.gpa, identifier.name);
try bp.variable_map.put(bp.gpa, identifier.name, .{
.name = nname,
.linkage = .has_linkage,
});
{ // TYPE CHECKING
if (item.init != null) {
return error.TypeError;
}
const gop = try bp.type_map.getOrPut(bp.gpa, nname.real_idx);
if (gop.found_existing) {
if (gop.value_ptr.* == .func)
return error.TypeError;
} else gop.value_ptr.* = .{ .static = .{
.init = .none,
.global = true,
} };
}
return;
}
const unique_name = try bp.make_temporary(identifier.name);
try bp.variable_map.put(bp.gpa, identifier.name, .{ .name = unique_name });
{ // TYPE CHECKING
const attr: Arrtibutes = if (sc == .static) ret: {
const init_value: Arrtibutes.Init = if (item.init) |e| switch (e.*) {
.constant => |i| .{ .initial = i },
else => return error.TypeError,
} else .{ .initial = 0 };
break :ret .{ .static = .{
.init = init_value,
.global = false,
} };
} else .local;
const gop = try bp.type_map.getOrPut(bp.gpa, unique_name.real_idx);
if (gop.found_existing) {
if (gop.value_ptr.* == .func)
return error.TypeError;
}
gop.value_ptr.* = attr;
}
identifier.* = .{ .idx = unique_name };
if (T == .@"var")
if (item.init) |expr|
try resolve_expr(bp, expr);
}
I do not like how this chapters is all these weird intermingling ifs. It is very confusing logic and horrible to debug. Running the test suite, I got one failure, which is not catching the error in this C code.
int main(void) {
int x = 0;
/* a variable declared in a for loop header cannot have a storage class. */
for (static int i = 0; i < 10; i = i + 1) {
x = x + 1;
}
return x;
}
Well, then. I do not think I will add another if statement in that monster function just for for loops. I will go back and reject that at the parsing stage instead. Boom: tests pass.
Internal Representation
It makes sense in a weird twisted manner to have the String Interner itself hold the type info that the semantic analsys phase has been collecting. It makes perfect sense if you ask me, and it keeps me from carrying yet another type around. Changing the value of the internal map to ?sema.Attributes, where the strings that do not have related values would simple be null. This, however, requires more work than I am currently willing ti put in, so I will have the semantic analysis function just return the collected type map.
pub fn resolve_prgm(
gpa: std.mem.Allocator,
strings: *utils.StringInterner,
prgm: *ast.Prgm,
) Error!TypeMap {
// yada yada
return type_map;
}
The IR syntax tree changes in a similar fashion too. Programs are now a list of TopLevels, which are either a function or a StaticVar. Functions also track whether they are global.
pub const Prgm = struct {
items: std.ArrayListUnmanaged(TopLevel),
};
pub const TopLevel = union(enum) {
F: FuncDef,
V: StaticVar,
};
pub const FuncDef = struct {
name: Identifier,
global: bool,
params: std.ArrayListUnmanaged(Identifier),
instrs: std.ArrayListUnmanaged(Instr),
};
pub const StaticVar = struct {
name: Identifier,
global: bool,
init: u64,
};
Now, to generate these new items, the type_map returned from semantic analysis is now an input parameter. This is used to determine which function declarations are global. This is the new prgm_emit_ir.
pub fn prgm_emit_ir(
alloc: std.mem.Allocator,
strings: *utils.StringInterner,
type_map: *sema.TypeMap, // might make sense to move this to `utils`
prgm: *const ast.Prgm,
) Error!ir.Prgm {
var top_level: std.ArrayListUnmanaged(ir.TopLevel) = try .initCapacity(
alloc,
prgm.decls.len,
);
var iter = prgm.decls.constIterator(0);
while (iter.next()) |d| if (d.* == .F) if (d.F.block) |_| {
var f_ir = try func_def_emit_ir(alloc, strings, &d.F);
// assertions galore. so much hidden control flow
f_ir.global = type_map.get(f_ir.name.real_idx).?.func.global;
try top_level.append(alloc, .{ .F = f_ir });
};
return .{ .items = top_level };
}
Secondly, all variable declarations with static or extern specifiers should not be generated. Because they have linkage and therefore belong to the Prgm scope.
fn var_decl_emit_ir(
bp: Boilerplate,
decl: *const ast.VarDecl,
) Error!void {
if (decl.sc == null) if (decl.init) |e| {
const src = try expr_emit_ir(bp, e);
try bp.append(.{ .copy = .init(src, .{ .variable = decl.name.idx }) });
};
}
Now, back in prgm_emit_ir, the type_map is traversed for every static variable. Here is hoping the semantic analysis phase tracked these correctly.
{ // STATIC VARS
var iter = type_map.iterator();
while (iter.next()) |entry| if (entry.value_ptr.* == .static) {
const name: utils.StringInterner.Idx = .{ // hacks on hacks
.real_idx = entry.key_ptr.*,
.strings = strings,
};
const global = entry.value_ptr.static.global;
const init = switch (entry.value_ptr.static.init) {
.initial => |i| i,
.tentative => 0,
.none => continue,
};
try top_level.append(alloc, .{ .V = .{
.name = name,
.global = global,
.init = init,
} });
};
}
And .. that's fairly it. Doing the eye test on IR generation seems to work fine. Here is one sample. Running the test suite works fine as well.
static int my_fun(void);
int call_static_my_fun(void) {
return my_fun();
}
int call_static_my_fun_2(void) {
int my_fun(void);
return my_fun();
}
extern int my_fun(void);
static int my_fun(void);
int my_fun(void) {
static int i = 0;
i = i + 1;
return i;
}
//PROGRAM
// global FUNCTION call_static_my_fun
// fn.1 <- my_fun()
// ret fn.1
// ret 0
// global FUNCTION call_static_my_fun_2
// fn.2 <- my_fun()
// ret fn.2
// ret 0
// FUNCTION my_fun
// add.3 <- i.0 + 1
// i.0 <- add.3
// ret i.0
// ret 0
// VARIABLE i.0 = 0
Onwards to codegen and exposing the actual bugs in previous stages.
Assembly Generation
Changes to the assembly syntax tree mirror those in the IR's. Also, a new Operand type for rodata. The Operand change is tiny.
pub const Operand = union(enum) {
imm: u64,
reg: Register,
pseudo: Identifier,
stack: Offset,
data: Identifier, // <--
};
The changes to Prgm are similar enough to the changes in IR that repeating them here would be a chore. Changes to asm_gen.zig are equally straightforward, for the most part. The new prgm_to_asm almost contains all of it, with functions getting their global in their own function.
pub fn prgm_to_asm(
alloc: std.mem.Allocator,
prgm: ir.Prgm,
) !assembly.Prgm {
var items: std.ArrayListUnmanaged(assembly.TopLevel) = try .initCapacity(
alloc,
prgm.items.items.len,
);
for (prgm.items.items) |item| switch (item) {
.F => |f| try items.append(alloc, .{
.F = try func_def_to_asm(alloc, f),
}),
.V => |v| try items.append(alloc, .{ .V = assembly.StaticVar{
.name = v.name,
.init = v.init,
.global = v.global,
} }),
};
return .{ .items = items };
}
Replacing Pseudos
Previously, pseudoregisters were replaced by stack items. Now, the static ones, as indicated by the type_map (I am never getting rid of this am I), are going to be replaced by data operands. To facilitate this, I am just going to add a type_map field to ir.Prgm and assembly.Prgm. The map passes through all the way to pseudo_to_stack (which might warrant a change of name now), to end up with this. I also changed PseudoMap's value type to void because I realized I am not using it.3
fn pseudo_to_stack(
op: assembly.Operand,
type_map: *const sema.TypeMap,
map: *PseudoMap,
) !assembly.Operand {
switch (op) {
.reg, .imm, .stack, .data => return op,
.pseudo => |name| {
const offset: assembly.Operand.Offset =
if (map.getIndex(name)) |idx|
// already seen
@intCast(idx + 1)
else if (cond: {
const cond = type_map.get(name.real_idx);
if (cond == null) break :cond false;
break :cond cond.? == .static;
})
return .{ .data = name }
else ret: {
try map.put(name, {});
break :ret @intCast(map.count()); // index of last item + 1
};
return .{ .stack = offset * -4 };
},
}
}
Fixing Up Instructions
A lot of the old, already implemented rules for moving between different stack positions already apply here for moving between different memory positions, whether they are data or stack. Otherwise, it is the same annoying state machine.
To help make things simpler, I created a helper function to tell me if an Operand is a memory location or not. This is the function defined under Operand.
pub inline fn is_mem(
self: @This(),
) bool {
return switch (self) {
.stack, .data => true,
else => false,
};
}
And this is the new state machine in all its glory. the only changes is using .is_mem() and changing the states' names from stack to mem.
const State = enum {
start,
mov_mem_mem,
cmp_mem_mem,
cmp_to_imm,
add_mem_mem,
sub_mem_mem,
mul_to_mem,
idiv_const,
legal,
};
for (func_def.instrs.items) |instr| {
state: switch (State.start) {
.start => switch (instr) {
.mov => |m| if (m.src.is_mem() and m.dst.is_mem())
continue :state .mov_mem_mem
else
continue :state .legal,
.cmp => |m| if (m.src.is_mem() and m.dst.is_mem())
continue :state .cmp_mem_mem
else if (m.dst == .imm)
continue :state .cmp_to_imm
else
continue :state .legal,
.add => |m| if (m.src.is_mem() and m.dst.is_mem())
continue :state .add_mem_mem
else
continue :state .legal,
.sub => |m| if (m.src.is_mem() and m.dst.is_mem())
continue :state .sub_mem_mem
else
continue :state .legal,
.mul => |m| if (m.dst.is_mem())
continue :state .mul_to_mem
else
continue :state .legal,
.idiv => |o| if (o == .imm)
continue :state .idiv_const
else
continue :state .legal,
else => continue :state .legal,
},
.mov_mem_mem => try out.appendSlice(alloc, &.{
.{ .mov = .init(instr.mov.src, .{ .reg = .R10 }) },
.{ .mov = .init(.{ .reg = .R10 }, instr.mov.dst) },
}),
.cmp_mem_mem => try out.appendSlice(alloc, &.{
.{ .mov = .init(instr.cmp.src, .{ .reg = .R10 }) },
.{ .cmp = .init(.{ .reg = .R10 }, instr.cmp.dst) },
}),
.cmp_to_imm => try out.appendSlice(alloc, &.{
.{ .mov = .init(instr.cmp.dst, .{ .reg = .R11 }) },
.{ .cmp = .init(instr.cmp.src, .{ .reg = .R11 }) },
}),
.add_mem_mem => try out.appendSlice(alloc, &.{
.{ .mov = .init(instr.add.src, .{ .reg = .R10 }) },
.{ .add = .init(.{ .reg = .R10 }, instr.add.dst) },
}),
.sub_mem_mem => try out.appendSlice(alloc, &.{
.{ .mov = .init(instr.sub.src, .{ .reg = .R10 }) },
.{ .sub = .init(.{ .reg = .R10 }, instr.sub.dst) },
}),
.mul_to_mem => try out.appendSlice(alloc, &.{
.{ .mov = .init(instr.mul.dst, .{ .reg = .R11 }) },
.{ .mul = .init(instr.mul.src, .{ .reg = .R11 }) },
.{ .mov = .init(.{ .reg = .R11 }, instr.mul.dst) },
}),
.idiv_const => try out.appendSlice(alloc, &.{
.{ .mov = .init(instr.idiv, .{ .reg = .R11 }) },
.{ .idiv = .{ .reg = .R11 } },
}),
.legal => try out.append(alloc, instr),
}
}
And here, I was done. The eye tests pass, with small hiccups regarding lifetimes and formatting. All is left now is the actual assembly generation. This is fairly mechanical, I think, despite hiding a nasty bug last chapter.
Thankfully, all tests pass. I am done with Part 1.
Next Thing to Do
I am undecided yet. Either go for Part 3, which is about optimizations, or do Part 1 again in another language, like Swift or .. I dunno .. TypeScript? Maybe I will start working on my own language, or working on a compiler for Hare. Or maybe just go find a job.
All in all, this was a fun process. I learned a lot about Zig and reinforced knowledge about writing a C compiler. I recommend buying the Book. It is great.
Until later.