backend

Unnamed repository; edit this file 'description' to name the repository.
git clone https://git.deepztream.com/backend
Log | Files | Refs | Submodules

commit 3a356cedeb2e859aee1f99096b13edce85c41768
parent a00348a5a71f64b1c607ea3526c7ee056aec44e2
Author: William Djupström <william@deepztream.com>
Date:   Tue, 22 Sep 2026 19:40:00 +0200

Allow naming labels to simplify ir generation

Diffstat:
MMakefile | 18++++++++++--------
Msrc/backend.h | 45++++++++++++++++++++-------------------------
Msrc/ir_backend.c | 26++++++++++++++++++++++----
Msrc/lexer.c | 6+++---
Msrc/parse.c | 96++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-------------
Msrc/phi.c | 11+++++++++--
Dsrc/test.c | 104-------------------------------------------------------------------------------
Msrc/x86_64-codegen.c | 21++++++++++++---------
8 files changed, 157 insertions(+), 170 deletions(-)

diff --git a/Makefile b/Makefile @@ -10,23 +10,25 @@ CFLAGS=-ggdb -Og -Wall -Wextra -Wswitch-enum -I./dlib .PHONY: parse clean all: $(BUILD_DIR)/parse $(BUILD_DIR)/test $(BUILD_DIR)/parse_output -$(BUILD_DIR)/test: src/test.c $(DEP_FILES) $(BUILD_DIR) +$(BUILD_DIR)/test: src/test.c $(DEP_FILES) + mkdir -p $(BUILD_DIR) gcc $(CFLAGS) -o $@ src/test.c -$(BUILD_DIR)/parse: src/parse.c src/lexer.c src/lexer.h $(DEP_FILES) $(BUILD_DIR) +$(BUILD_DIR)/parse: src/parse.c src/lexer.c src/lexer.h $(DEP_FILES) + mkdir -p $(BUILD_DIR) gcc $(CFLAGS) -o $@ src/parse.c src/lexer.c -$(BUILD_DIR)/parse_output: $(BUILD_DIR)/parse_output.o $(BUILD_DIR) +$(BUILD_DIR)/parse_output: $(BUILD_DIR)/parse_output.o + mkdir -p $(BUILD_DIR) gcc $(CFLAGS) -no-pie -o $@ $(BUILD_DIR)/parse_output.o -$(BUILD_DIR)/parse_output.o: $(BUILD_DIR)/parse_output.nasm $(BUILD_DIR) +$(BUILD_DIR)/parse_output.o: $(BUILD_DIR)/parse_output.nasm + mkdir -p $(BUILD_DIR) nasm -felf64 -o $@ $(BUILD_DIR)/parse_output.nasm -$(BUILD_DIR)/parse_output.nasm: $(BUILD_DIR)/parse $(BUILD_DIR) - ./$(BUILD_DIR)/parse test/test.ir - -$(BUILD_DIR): +$(BUILD_DIR)/parse_output.nasm: $(BUILD_DIR)/parse mkdir -p $(BUILD_DIR) + ./$(BUILD_DIR)/parse test/test.ir clean: rm -rf $(BUILD_DIR)/* diff --git a/src/backend.h b/src/backend.h @@ -56,25 +56,13 @@ typedef enum Ir_binop { OP_GEQ, } Ir_binop; -enum x86_64_register { - REG_INVALID = 0, - REG_A, - REG_B, - REG_C, - REG_D, - REG_DI, - REG_SI, - REG_SP, - REG_BP, - REG_8, - REG_9, - REG_10, - REG_11, - REG_12, - REG_13, - REG_14, - REG_15, -}; +typedef struct { + bool resolved; + union { + Sv sv; + size_t id; + }; +} Label; typedef struct { enum Ir_arg_kind kind; @@ -86,7 +74,6 @@ typedef struct { void *addr; /* char *cstr; */ Sv sv; - enum x86_64_register reg; }; } Ir_arg; @@ -97,7 +84,7 @@ typedef struct { } Ir_arg_list; typedef struct { - ssize_t label_id; + Label label; ssize_t temp_id; } Phi_entry; @@ -131,14 +118,14 @@ typedef struct { Ir_arg data; } store; Ir_arg assign; - ssize_t label_id; + Label label; struct { - ssize_t label_id; + Label label; } jump; struct { Ir_arg cond; - ssize_t true_label_id; - ssize_t false_label_id; + Label true_label; + Label false_label; } branch; Ir_arg ret; Ir_call_args call; @@ -194,10 +181,18 @@ typedef struct { } Ir_block_list; typedef struct { + Sv *items; + size_t count; + size_t capacity; +} Sv_list; + +typedef struct { + bool resolved_labels; Sv name; Ir_type return_type; Ir_type_list argument_types; Ir_block_list body; + Sv_list labels; } Ir_function; typedef struct { diff --git a/src/ir_backend.c b/src/ir_backend.c @@ -125,11 +125,21 @@ ir_compile_block(Ir_block block, Sb *sb) /* break; */ case IR_JUMP: assert(ir.result.kind == ARG_NONE); - sb_printf(sb, " jump #%li", ir.jump.label_id); + if (ir.jump.label.resolved) { + sb_printf(sb, " jump #%li", ir.jump.label.id); + } else { + sb_printf(sb, " jump #%.*s", (int) ir.jump.label.sv.count, ir.jump.label.sv.items); + } break; case IR_BRANCH: assert(ir.result.kind == ARG_NONE); - sb_printf(sb, " branch %s #%li #%li", ir_arg_to_cstr(ir.branch.cond), ir.branch.true_label_id, ir.branch.false_label_id); + if (ir.branch.true_label.resolved && ir.branch.false_label.resolved) { + sb_printf(sb, " branch %s #%li #%li", ir_arg_to_cstr(ir.branch.cond), ir.branch.true_label.id, ir.branch.false_label.id); + } else if (!ir.branch.true_label.resolved && !ir.branch.false_label.resolved) { + sb_printf(sb, " branch %s #%.*s #%.*s", ir_arg_to_cstr(ir.branch.cond), (int) ir.branch.true_label.sv.count, ir.branch.true_label.sv.items, (int) ir.branch.false_label.sv.count, ir.branch.false_label.sv.items); + } else { + unreachable("out-of-sync labels"); + } break; case IR_PHI: assert(ir.result.kind == ARG_TEMP_STORAGE); @@ -138,7 +148,11 @@ ir_compile_block(Ir_block block, Sb *sb) if (j) { da_append(sb, ' '); } - sb_printf(sb, "(#%li %%%li)", ir.phi_list.items[j].label_id, ir.phi_list.items[j].temp_id); + if (ir.phi_list.items[j].label.resolved) { + sb_printf(sb, "(#%li %%%li)", ir.phi_list.items[j].label.id, ir.phi_list.items[j].temp_id); + } else { + sb_printf(sb, "(#%.*s %%%li)", (int) ir.phi_list.items[j].label.sv.count, ir.phi_list.items[j].label.sv.items, ir.phi_list.items[j].temp_id); + } } sb_printf(sb, "]"); break; @@ -189,7 +203,11 @@ ir_dump(Ir_program prog, Sb *sb) } sb_printf(sb, ") -> %s {\n", ir_type_to_cstr(function.return_type)); for (j = 0; j < function.body.count; j++) { - sb_printf(sb, "#%lu:\n", j); + if (function.resolved_labels) { + sb_printf(sb, "#%lu:\n", j); + } else { + sb_printf(sb, "#%.*s:\n", (int) function.labels.items[j].count, function.labels.items[j].data); + } if (!ir_compile_block(function.body.items[j], sb)) { temp_allocator = saved_allocator; return false; diff --git a/src/lexer.c b/src/lexer.c @@ -408,13 +408,13 @@ next_token(Lexer *lexer) return result; } - if (c == '#' && isdigit(peek_char(lexer))) { + if (c == '#' && is_ident_char(peek_char(lexer))) { result.sv.data++; len = 0; - while (next_char_if(lexer, isdigit) >= 0) len++; + while (next_char_if(lexer, is_ident_char) >= 0) len++; result.kind = T_LABEL; result.sv.count = len; - result.i64 = sv_to_number(result.sv, 10); + /* result.i64 = sv_to_number(result.sv, 10); */ lexer->last_tok = result; return result; } diff --git a/src/parse.c b/src/parse.c @@ -172,7 +172,7 @@ parse_ir_phi_list(Phi_entry_list *out_phi_list, Lexer *lexer) if (!expect_token_kind(lexer, T_LABEL)) { return false; } - phi.label_id = lexer->last_tok.i64; + phi.label.sv = lexer->last_tok.sv; skip_whitespace(lexer); if (!expect_token_kind(lexer, T_TEMP)) { return false; @@ -305,7 +305,7 @@ parse_ir_jump(Ir *out_ins, Lexer *lexer) *out_ins = (Ir) { .kind = IR_JUMP, - .jump = { .label_id = lexer->last_tok.i64 }, + .jump = { .label = { .sv = lexer->last_tok.sv }}, }; return true; } @@ -322,18 +322,22 @@ parse_ir_branch(Ir *out_ins, Lexer *lexer) if (!expect_token_kind(lexer, T_LABEL)) { return false; } - size_t true_label = lexer->last_tok.i64; + Sv true_label = lexer->last_tok.sv; skip_whitespace(lexer); if (!expect_token_kind(lexer, T_LABEL)) { return false; } - size_t false_label = lexer->last_tok.i64; + Sv false_label = lexer->last_tok.sv; *out_ins = (Ir) { .kind = IR_BRANCH, .branch = { .cond = cond, - .true_label_id = true_label, - .false_label_id = false_label, + .true_label = { + .sv = true_label, + }, + .false_label = { + .sv = false_label, + }, }, }; return true; @@ -386,24 +390,18 @@ parse_ir_basic_block(Ir_block *out_block, Lexer *lexer) bool parse_ir_function_body(Ir_function *out_func, Lexer *lexer) { - int next_label = 0, label; Ir_block block; if (!expect_token_kind(lexer, '{')) { return false; } skip_whitespace(lexer); + while (peek_token(lexer).kind != '}') { block = (Ir_block) {0}; if (!expect_token_kind(lexer, T_LABEL)) { return false; } - label = lexer->last_tok.i64; - if (label != next_label) { - print_loc(lexer->last_valid_loc); - fprintf(stderr, "Error: Exptected label %i, but got %i\n", next_label, label); - return false; - } - next_label++; + da_append(&out_func->labels, lexer->last_tok.sv); skip_whitespace(lexer); if (!expect_token_kind(lexer, ':')) { return false; @@ -499,6 +497,64 @@ parse_ir_from_file(const char *file_name, Ir_program *out_prog) return parse_ir_top(out_prog, &lexer); } +bool +resolve_labels(Ir_function *fn) +{ + bool looping; + size_t i, j, k, l; + Label *target; + Ir *ir; + if (fn->resolved_labels) { + return true; + } + if (fn->labels.count != fn->body.count) { + fprintf(stderr, "Error: Label count (%zu) doesn't match Basic block count (%zu)\n", fn->labels.count, fn->body.count); + return false; + } + for (j = 0; j < fn->body.count; j++) { + for (k = 0; k < fn->body.items[j].count; k++) { + ir = &fn->body.items[j].items[k]; + looping = true; + for (l = 0; looping; l++) { + if (ir->kind == IR_JUMP) { + looping = false; + target = &ir->jump.label; + } else if (ir->kind == IR_BRANCH) { + fprintf(stderr, "Found branch\n"); + if (l) { + looping = false; + target = &ir->branch.false_label; + } else { + target = &ir->branch.true_label; + } + } else if (ir->kind == IR_PHI) { + if (l < ir->phi_list.count) { + target = &ir->phi_list.items[l].label; + } else { + break; + } + } else { + break; + } + assert(!target->resolved); + for (i = 0; i < fn->labels.count; i++) { + if (sv_equal(fn->labels.items[i], target->sv)) { + target->id = i; + target->resolved = true; + break; + } + } + if (i == fn->labels.count) { + fprintf(stderr, "Error: Non-existant label: %.*s\n", (int) target->sv.count, target->sv.items); + return false; + } + } + } + } + fn->resolved_labels = true; + return true; +} + void usage(FILE *output, const char *program_name) { @@ -525,8 +581,18 @@ main(int argc, const char * const *argv) if (!parse_ir_from_file(input_file_name, &prog)) { return 1; } + + ir_dump(prog, &sb); + sb_write(1, sb); + sb.count = 0; + for (i = 0; i < prog.functions.count; i++) { - remove_phi_nodes(prog.functions.items[i]); + if (!resolve_labels(&prog.functions.items[i])) { + return 1; + } + if (!remove_phi_nodes(prog.functions.items[i])) { + return 1; + } } ir_dump(prog, &sb); diff --git a/src/phi.c b/src/phi.c @@ -1,9 +1,13 @@ -void +bool remove_phi_nodes(Ir_function fn) { size_t i, j, k, last; ssize_t label_id, temp_id; Ir phi, tmp_ir; Ir_block *block; + if (!fn.resolved_labels) { + fprintf(stderr, "Error: Running remove_phi_nodes() before resolving block labels\n"); + return false; + } for (i = 0; i < fn.body.count; i++) { block = &fn.body.items[i]; for (j = 0; j < block->count; j++) { @@ -12,7 +16,9 @@ remove_phi_nodes(Ir_function fn) { } phi = block->items[j]; for (k = 0; k < phi.phi_list.count; k++) { - label_id = phi.phi_list.items[k].label_id; + assert(phi.phi_list.items[k].label.resolved); + + label_id = phi.phi_list.items[k].label.id; last = fn.body.items[label_id].count; temp_id = phi.phi_list.items[k].temp_id; da_append(&fn.body.items[label_id], ((Ir) { .kind = IR_ASSIGN, .result = phi.result, .assign = { .kind = ARG_TEMP_STORAGE, .temp_id = temp_id }})); @@ -25,4 +31,5 @@ remove_phi_nodes(Ir_function fn) { j--; } } + return true; } diff --git a/src/test.c b/src/test.c @@ -1,104 +0,0 @@ -#include <stdbool.h> - -#define DLIB_IMPLEMENTATION -#include "dlib.h" - -#include "backend.h" - -#include "phi.c" - -#include "ir_backend.c" -#include "x86_64-codegen.c" - -int -main(int argc, char **argv) -{ - (void) argc; - (void) argv; - size_t i; - Sb sb = {0}; - Ir_block_list func_body = {0}; - Ir_block ir_block = {0}; - /* da_append(&ir_block, ((Ir) { .kind = IR_LABEL, .label_id = 0})); */ - da_append(&ir_block, ((Ir) { .kind = IR_ASSIGN, .result = { .kind = ARG_TEMP_STORAGE, .type = TYPE_I32, .temp_id = 0}, .assign = {.kind = ARG_INT_LITERAL, .i64 = 0}})); - da_append(&ir_block, ((Ir) { .kind = IR_JUMP, .jump = {.label_id = 1}})); - - da_append(&func_body, ir_block); - ir_block = (Ir_block) {0}; - - /* da_append(&ir_block, ((Ir) { .kind = IR_LABEL, .label_id = 1})); */ - da_append(&ir_block, ((Ir) { .kind = IR_PHI, .result = { .kind = ARG_TEMP_STORAGE, .type = TYPE_I32, .temp_id = 3 }, .phi_list = {0}})); - da_append(&ir_block.items[ir_block.count - 1].phi_list, ((Phi_entry) { .label_id = 0, .temp_id = 0 })); - da_append(&ir_block.items[ir_block.count - 1].phi_list, ((Phi_entry) { .label_id = 2, .temp_id = 4 })); - da_append(&ir_block, ((Ir) { .kind = IR_PHI, .result = { .kind = ARG_TEMP_STORAGE, .type = TYPE_I32, .temp_id = 5 }, .phi_list = {0}})); - da_append(&ir_block.items[ir_block.count - 1].phi_list, ((Phi_entry) { .label_id = 0, .temp_id = 0 })); - da_append(&ir_block.items[ir_block.count - 1].phi_list, ((Phi_entry) { .label_id = 2, .temp_id = 2 })); - da_append(&ir_block, ((Ir) { .kind = IR_BINOP, .result = { .kind = ARG_TEMP_STORAGE, .type = TYPE_I8, .temp_id = 1}, .binop = {.op = OP_LT, .op_type = TYPE_I32, .left = {.kind = ARG_TEMP_STORAGE, .temp_id = 3}, .right = { .kind = ARG_INT_LITERAL, .i64 = 11}}})); - da_append(&ir_block, ((Ir) { .kind = IR_BRANCH, .branch = {.cond = {.kind = ARG_TEMP_STORAGE, .temp_id = 1}, .true_label_id = 2, .false_label_id = 3}})); - - da_append(&func_body, ir_block); - ir_block = (Ir_block) {0}; - - /* da_append(&ir_block, ((Ir) { .kind = IR_LABEL, .label_id = 2})); */ - da_append(&ir_block, ((Ir) { .kind = IR_CALL, .result = {.kind = ARG_TEMP_STORAGE, .type = TYPE_I32, .temp_id = 2}, .call = { .name = {.data = "printf", .count = 6}, .args = {0}}})); - da_append(&ir_block.items[ir_block.count - 1].call.args, ((Ir_arg) {.kind = ARG_CSTRING_LITERAL, .type = TYPE_PTR, .sv = sv_literal("%i\n")})); - da_append(&ir_block.items[ir_block.count - 1].call.args, ((Ir_arg) {.kind = ARG_TEMP_STORAGE, .type = TYPE_I32, .temp_id = 3})); - da_append(&ir_block, ((Ir) { .kind = IR_BINOP, .result = { .kind = ARG_TEMP_STORAGE, .type = TYPE_I32, .temp_id = 4}, .binop = {.op = OP_ADD, .op_type = TYPE_I32, .left = {.kind = ARG_TEMP_STORAGE, .temp_id = 3}, .right = {.kind = ARG_INT_LITERAL, .i64 = 1}}})); - da_append(&ir_block, ((Ir) { .kind = IR_JUMP, .jump = {.label_id = 1}})); - - da_append(&func_body, ir_block); - ir_block = (Ir_block) {0}; - - /* da_append(&ir_block, ((Ir) { .kind = IR_LABEL, .label_id = 3})); */ - da_append(&ir_block, ((Ir) { .kind = IR_RETURN, .ret = {.kind = ARG_TEMP_STORAGE, .type = TYPE_I32, .temp_id = 5}})); - - da_append(&func_body, ir_block); - ir_block = (Ir_block) {0}; - - Ir_program prog = {0}; - da_append(&prog.functions, ((Ir_function) {.name = {.data = "main", .count = 4}, .return_type = TYPE_I32, .body = func_body})); - da_append(&prog.functions.items[0].argument_types, TYPE_I32); - da_append(&prog.functions.items[0].argument_types, TYPE_PTR); - - da_append(&prog.externs, ((Ir_extern) { .symbol = { .data = "printf", .count = 6 }})); - - if (!ir_backend.compile(prog, &sb)) { - return 1; - } - - fprintf(stdout, "[[[ IR Representation ]]]\n"); - sb_write(1, sb); - sb.count = 0; - - for (i = 0; i < prog.functions.count; i++) { - remove_phi_nodes(prog.functions.items[i]); - } - - if (!x86_64_backend.compile(prog, &sb)) { - fprintf(stdout, "\n[[[ x86_64-nasm Representation ]]]\n"); - sb_write(1, sb); - return 1; - } - - fprintf(stdout, "\n[[[ x86_64-nasm Representation ]]]\n"); - sb_write(1, sb); - - int out_fd = open("output.nasm", O_WRONLY | O_CREAT | O_TRUNC, 0644); - if (out_fd < 0) { - return 1; - } - sb_write(out_fd, sb); - sb.count = 0; - - /* print_temp_count(prog); */ - - /* remove_phi_nodes(prog.functions.items[0]); */ - /* fprintf(stderr, "--------Removed Phi nodes---------\n"); */ - /* if (!ir_backend.compile(prog, &sb)) { */ - /* return 1; */ - /* } */ - /* sb_write(1, sb); */ - - return 0; -} - diff --git a/src/x86_64-codegen.c b/src/x86_64-codegen.c @@ -501,7 +501,7 @@ x86_64_compile_instruction(Ir ir, x86_64_Instruction_list *list, x86_64_Data_lis /* sb_printf(sb, " mov tmp_%zu, %li\n", ir.assign.i64); */ da_append(list, ((x86_64_Instruction) { .opcode = x86_64_MOV, - .encoding = x86_64_RI, + .encoding = x86_64_RI, .rand1 = { .bit_width = 32, .kind = x86_64_RAND_REGISTER, @@ -523,7 +523,7 @@ x86_64_compile_instruction(Ir ir, x86_64_Instruction_list *list, x86_64_Data_lis case ARG_CSTRING_LITERAL: da_append(list, ((x86_64_Instruction) { .opcode = x86_64_MOV, - .encoding = x86_64_RI, + .encoding = x86_64_RI, .rand1 = { .bit_width = 64, .kind = x86_64_RAND_REGISTER, @@ -545,7 +545,7 @@ x86_64_compile_instruction(Ir ir, x86_64_Instruction_list *list, x86_64_Data_lis case ARG_TEMP_STORAGE: da_append(list, ((x86_64_Instruction) { .opcode = x86_64_MOV, - .encoding = x86_64_RR, + .encoding = x86_64_RR, .rand1 = { .bit_width = 32, .kind = x86_64_RAND_REGISTER, @@ -790,7 +790,7 @@ x86_64_compile_instruction(Ir ir, x86_64_Instruction_list *list, x86_64_Data_lis if (ir.ret.kind == ARG_TEMP_STORAGE) { da_append(list, ((x86_64_Instruction) { .opcode = x86_64_MOV, - .encoding = x86_64_RR, + .encoding = x86_64_RR, .rand1 = { .bit_width = 32, .kind = x86_64_RAND_REGISTER, @@ -810,7 +810,7 @@ x86_64_compile_instruction(Ir ir, x86_64_Instruction_list *list, x86_64_Data_lis })); da_append(list, ((x86_64_Instruction) { .opcode = x86_64_RET, - .encoding = x86_64_NO_OPERAND, + .encoding = x86_64_NO_OPERAND, })); } else { todo("return"); @@ -818,20 +818,23 @@ x86_64_compile_instruction(Ir ir, x86_64_Instruction_list *list, x86_64_Data_lis break; /* case IR_LABEL: */ case IR_JUMP: + assert(ir.jump.label.resolved); da_append(list, ((x86_64_Instruction) { .opcode = x86_64_JMP, - .encoding = x86_64_I, + .encoding = x86_64_I, .rand1 = { .bit_width = 64, .kind = x86_64_RAND_IMMEDIATE, .imm = { .kind = x86_64_IMM_CODE_LABEL, - .label_id = ir.jump.label_id, + .label_id = ir.jump.label.id, }, }, })); break; case IR_BRANCH: + assert(ir.branch.true_label.resolved); + assert(ir.branch.false_label.resolved); if (ir.branch.cond.kind == ARG_TEMP_STORAGE) { da_append(list, ((x86_64_Instruction) { .opcode = x86_64_TEST, @@ -861,7 +864,7 @@ x86_64_compile_instruction(Ir ir, x86_64_Instruction_list *list, x86_64_Data_lis .kind = x86_64_RAND_IMMEDIATE, .imm = { .kind = x86_64_IMM_CODE_LABEL, - .label_id = ir.branch.false_label_id, + .label_id = ir.branch.false_label.id, }, }, })); @@ -873,7 +876,7 @@ x86_64_compile_instruction(Ir ir, x86_64_Instruction_list *list, x86_64_Data_lis .kind = x86_64_RAND_IMMEDIATE, .imm = { .kind = x86_64_IMM_CODE_LABEL, - .label_id = ir.branch.true_label_id, + .label_id = ir.branch.true_label.id, }, }, }));