backend

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

commit a00348a5a71f64b1c607ea3526c7ee056aec44e2
parent 372ae52525e47ba31d84ece3f558b8ead2cb1000
Author: William Djupström <william@deepztream.com>
Date:   Mon, 21 Sep 2026 18:08:41 +0200

Added a parser for .ir files

Diffstat:
M.gitignore | 8++++++++
A.gitmodules | 3+++
MMakefile | 38++++++++++++++++++++++++++++++++------
Dbackend.c | 207-------------------------------------------------------------------------------
Adlib | 1+
Ddlib.h | 324-------------------------------------------------------------------------------
Dir_backend.c | 195-------------------------------------------------------------------------------
Asrc/backend.h | 225+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Asrc/ir_backend.c | 207+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Asrc/lexer.c | 651+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Asrc/lexer.h | 88+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Asrc/parse.c | 546+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Asrc/phi.c | 28++++++++++++++++++++++++++++
Asrc/test.c | 104+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Asrc/x86_64-codegen.c | 1962+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
15 files changed, 3855 insertions(+), 732 deletions(-)

diff --git a/.gitignore b/.gitignore @@ -1,2 +1,10 @@ tags backend +*.o +*.gv +*.svg +parse +*.nasm +*.ir +build/ +test/ diff --git a/.gitmodules b/.gitmodules @@ -0,0 +1,3 @@ +[submodule "dlib"] + path = dlib + url = https://git.deepztream.com/dlib diff --git a/Makefile b/Makefile @@ -1,6 +1,32 @@ -INPUT_FILES = backend.c \ - ir_backend.c \ - dlib.h -CFLAGS=-ggdb -Og -Wall -Wextra -backend: $(INPUT_FILES) - gcc $(CFLAGS) -o $@ backend.c +BUILD_DIR = build +DEP_FILES = src/ir_backend.c \ + src/phi.c \ + src/x86_64-codegen.c \ + dlib/dlib.h \ + src/backend.h + +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) + gcc $(CFLAGS) -o $@ src/test.c + +$(BUILD_DIR)/parse: src/parse.c src/lexer.c src/lexer.h $(DEP_FILES) $(BUILD_DIR) + gcc $(CFLAGS) -o $@ src/parse.c src/lexer.c + +$(BUILD_DIR)/parse_output: $(BUILD_DIR)/parse_output.o $(BUILD_DIR) + gcc $(CFLAGS) -no-pie -o $@ $(BUILD_DIR)/parse_output.o + +$(BUILD_DIR)/parse_output.o: $(BUILD_DIR)/parse_output.nasm $(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): + mkdir -p $(BUILD_DIR) + +clean: + rm -rf $(BUILD_DIR)/* diff --git a/backend.c b/backend.c @@ -1,207 +0,0 @@ -#include <stdbool.h> - -#define DLIB_IMPLEMENTATION -#include "dlib.h" - -typedef struct Ir_program Ir_program; -typedef bool (*Compile_fn)(Ir_program, string_builder *); - -typedef struct { - const char *name; - Compile_fn compile; -} Backend; - -enum Ir_type { - TYPE_VOID, - TYPE_I8, - TYPE_U8, - TYPE_I16, - TYPE_U16, - TYPE_I32, - TYPE_U32, - TYPE_I64, - TYPE_U64, - TYPE_PTR, - TYPE_F32, - TYPE_F64, -}; - -enum Ir_kind { - IR_LOAD, - IR_STORE, - IR_ASSIGN, - IR_BINOP, - IR_CALL, - IR_RETURN, - IR_LABEL, - IR_JUMP, - IR_JUMP_IF_NOT, -}; - -enum Ir_arg_kind { - ARG_NONE, - ARG_INT_LITERAL, - /*ARG_FLOAT_LITERAL,*/ - ARG_CSTRING_LITERAL, - ARG_TEMP_STORAGE, - ARG_ADDRESS, -}; - -enum Ir_binop { - OP_ADD, - OP_SUB, - OP_MUL, - OP_DIV, - OP_LT, - OP_GT, - OP_EQ, - OP_LEQ, - OP_GEQ, -}; - -typedef struct { - enum Ir_arg_kind type; - union { - int64_t i64; - /* double f64; */ - ssize_t temp_id; - void *addr; - char *cstr; - }; -} Ir_arg; - -typedef struct { - Ir_arg *items; - size_t count; - size_t capacity; -} Ir_arg_list; - -typedef struct { - enum Ir_kind type; - Ir_arg result; - union { - struct { - enum Ir_binop op; - Ir_arg left; - Ir_arg right; - } binop; - struct { - Ir_arg loc; - } load; - struct { - Ir_arg loc; - Ir_arg data; - } store; - Ir_arg assign; - string_view label; - struct { - Ir_arg cond; - string_view label; - } jump; - Ir_arg ret; - struct { - Ir_arg indirect; - string_view name; - Ir_arg_list args; - } call; - }; -} Ir; - -typedef struct { - Ir *items; - size_t count; - size_t capacity; -} Ir_list; - -typedef struct { - enum Ir_type *items; - size_t count; - size_t capacity; -} Ir_type_list; - -typedef struct { - enum Ir_type type; - union { - int8_t i8; - uint8_t u8; - int16_t i16; - uint16_t u16; - int32_t i32; - uint32_t u32; - int64_t i64; - uint64_t u64; - /* double f64; - float f32; */ - string_view str; - char *cstr; - }; -} Ir_data; - -typedef struct { - string_view name; - Ir_data default_value; -} Ir_static_data; - -typedef struct { - Ir_static_data *items; - size_t count; - size_t capacity; -} Ir_static_data_list; - -typedef struct { - string_view name; - enum Ir_type return_type; - Ir_type_list argument_types; - Ir_list body; -} Ir_function; - -typedef struct { - Ir_function *items; - size_t count; - size_t capacity; -} Ir_function_list; - -struct Ir_program { - Ir_function_list functions; - Ir_static_data_list data; -}; - -bool ir_compile(Ir_program, string_builder *); - -Backend ir_backend = { - "IR Dump", - ir_compile, -}; - -int -main(int argc, char **argv) -{ - (void) argc; - (void) argv; - string_builder sb = {0}; - Ir_list ir_list = {0}; - da_append(&ir_list, ((Ir) { .type = IR_LABEL, .label = {.data = "start", .count = 5}})); - da_append(&ir_list, ((Ir) { .type = IR_ASSIGN, .result = { .type = ARG_TEMP_STORAGE, .temp_id = 0}, .assign = {.type = ARG_INT_LITERAL, .i64 = 0}})); - da_append(&ir_list, ((Ir) { .type = IR_LABEL, .label = {.data = "loop", .count = 4}})); - da_append(&ir_list, ((Ir) { .type = IR_BINOP, .result = { .type = ARG_TEMP_STORAGE, .temp_id = 1}, .binop = {.op = OP_LT, .left = {.type = ARG_TEMP_STORAGE, .temp_id = 0}, .right = {.type = ARG_INT_LITERAL, .i64 = 10}}})); - da_append(&ir_list, ((Ir) { .type = IR_JUMP_IF_NOT, .jump = {.cond = {.type = ARG_TEMP_STORAGE, .temp_id = 1}, .label = {.data = "loop_end", .count = 8}}})); - da_append(&ir_list, ((Ir) { .type = IR_CALL, .result = {.type = ARG_TEMP_STORAGE, .temp_id = 2}, .call = { .name = {.data = "printf", .count = 6}, .args = {0}}})); - da_append(&ir_list.items[ir_list.count - 1].call.args, ((Ir_arg) {.type = ARG_CSTRING_LITERAL, .cstr = "%i\\n"})); - da_append(&ir_list.items[ir_list.count - 1].call.args, ((Ir_arg) {.type = ARG_TEMP_STORAGE, .temp_id = 0})); - da_append(&ir_list, ((Ir) { .type = IR_BINOP, .result = { .type = ARG_TEMP_STORAGE, .temp_id = 0}, .binop = {.op = OP_ADD, .left = {.type = ARG_TEMP_STORAGE, .temp_id = 0}, .right = {.type = ARG_INT_LITERAL, .i64 = 1}}})); - da_append(&ir_list, ((Ir) { .type = IR_JUMP, .jump = {.label = {.data = "loop", .count = 4}}})); - da_append(&ir_list, ((Ir) { .type = IR_LABEL, .label = {.data = "loop_end", .count = 8}})); - da_append(&ir_list, ((Ir) { .type = IR_RETURN, .ret = {.type = ARG_INT_LITERAL, .i64 = 69}})); - Ir_program prog = {0}; - da_append(&prog.functions, ((Ir_function) {.name = {.data = "main", .count = 4}, .return_type = TYPE_I32, .body = ir_list})); - da_append(&prog.functions.items[0].argument_types, TYPE_I32); - da_append(&prog.functions.items[0].argument_types, TYPE_PTR); - - if (!ir_backend.compile(prog, &sb)) { - return 1; - } - sb_write(1, sb); - return 0; -} - -#include "ir_backend.c" diff --git a/dlib b/dlib @@ -0,0 +1 @@ +Subproject commit 17ea5a41be7a78531e1919b84399d09fe36bdfcf diff --git a/dlib.h b/dlib.h @@ -1,324 +0,0 @@ -#ifndef DLIB_H -#define DLIB_H 1 - -#include <assert.h> -#include <ctype.h> -#include <stdarg.h> -#include <stdio.h> -#include <stdbool.h> -#include <stdint.h> -#include <stdlib.h> -#include <errno.h> -#include <string.h> -#include <unistd.h> - -#define da_append(da, new)\ - do {\ - if ((da)->capacity <= (da)->count) {\ - (da)->capacity = (da)->capacity ? (da)->capacity * 2 : 16;\ - (da)->items = realloc((da)->items, sizeof(*(da)->items) * (da)->capacity);\ - }\ - (da)->items[(da)->count++] = (new);\ - } while(0) - -#define da_prepend(da, new)\ - do {\ - if ((da)->capacity <= (da)->count) {\ - (da)->capacity = (da)->capacity ? (da)->capacity * 2 : 16;\ - (da)->items = realloc((da)->items, sizeof(*(da)->items) * (da)->capacity);\ - }\ - memmove((da)->items + 1, (da)->items, sizeof(*(da)->items) * ((da)->count++));\ - (da)->items[0] = (new);\ - } while(0) - -#define da_reserve(da, len)\ - do {\ - if ((da)->capacity >= (len)) break;\ - (da)->capacity = (len);\ - (da)->items = realloc((da)->items, sizeof(*(da)->items) * (len));\ - } while(0) - -#define da_delete(da, index)\ - do {\ - assert(index >= 0 && index < (da)->count);\ - (da)->items[index] = (da)->items[--(da)->count];\ - } while (0) - -typedef struct { - union { - char *items; - const char *data; - }; - union { - ssize_t count; - ssize_t length; - }; - ssize_t capacity; -} string_builder; - -typedef struct { - union { - const char *items; - const char *data; - }; - union { - ssize_t count; - ssize_t length; - }; -} string_view; - -#define sb_append_char da_append -void sb_printf(string_builder *sb, const char *fmt, ...); -void sb_append_cstr(string_builder *sb, const char *cstr); -void sb_append_sv(string_builder *sb, string_view sv); - -void sb_read(string_builder *sb, int fd); -void sb_read_file(string_builder *sb, int fd); -void sb_write(int fd, string_builder sb); - -void sv_write(int fd, string_view sv); - -#define sv_literal(str) ((string_view){.data = (str), .count = (sizeof (str) - 1)}) - -string_view sv_from_sb(string_builder sb); -ssize_t sv_find_char(string_view sv, char c); - -string_view sv_chop(string_view sv, ssize_t count, string_view *rest); -string_view sv_chop_delim(string_view sv, char c, string_view *rest); - -string_view sv_getline(string_view *sv); - -string_view sv_trim_left(string_view sv); -string_view sv_trim_right(string_view sv); -string_view sv_trim(string_view sv); - -string_view sv_substring(string_view sv, ssize_t start, ssize_t req_count); - -int sv_compare(string_view sv1, string_view sv2); -bool sv_equal(string_view sv1, string_view sv2); - - -#ifdef DLIB_IMPLEMENTATION - -void -sb_printf(string_builder *sb, const char *fmt, ...) { - va_list args, args_copy; - va_start(args, fmt); - va_copy(args_copy, args); - int len = vsnprintf(NULL, 0, fmt, args_copy) + 1; - ssize_t new_size = sb->count + len; - da_reserve(sb, new_size); - va_end(args_copy); - vsnprintf(sb->items + sb->count, len, fmt, args); - va_end(args); - sb->count = new_size - 1; -} - -void -sb_append_cstr(string_builder *sb, const char *cstr) -{ - ssize_t len = strlen(cstr); - da_reserve(sb, sb->count + len); - strcpy(sb->items + sb->count, cstr); - sb->count += len; -} - -void -sb_append_sv(string_builder *sb, string_view sv) -{ - da_reserve(sb, sb->count + sv.count); - memcpy(sb->items + sb->count, sv.data, sv.count); - sb->count += sv.count; -} - -void -sb_read(string_builder *sb, int fd) -{ - ssize_t read_count; - ssize_t buf_size = 4096; - char *buf = malloc(buf_size); - do { - read_count = read(fd, buf, buf_size); - if (read_count < 0) { - if (errno == EINTR) { - continue; - } - perror(NULL); - exit(1); - } - if (read_count == 0) { - break; - } - sb_append_sv(sb, ((string_view) {.data = buf, .length = read_count})); - if (read_count < buf_size) { - break; - } - } while (1); - free(buf); -} - -void -sb_read_file(string_builder *sb, int fd) -{ - ssize_t read_count; - ssize_t buf_size = 4096; - char *buf = malloc(buf_size); - do { - read_count = read(fd, buf, buf_size); - if (read_count < 0) { - if (errno == EINTR) { - continue; - } - perror(NULL); - exit(1); - } - if (read_count == 0) { - break; - } - sb_append_sv(sb, ((string_view) {.data = buf, .length = read_count})); - } while (1); - free(buf); -} - -void -sb_write(int fd, string_builder sb) -{ - write(fd, sb.data, sb.length); -} - -/* String view functions */ - -void -sv_write(int fd, string_view sv) -{ - write(fd, sv.data, sv.count); -} - -string_view -sv_from_sb(string_builder sb) -{ - return (string_view) {.data = sb.items, .count = sb.count}; -} - -ssize_t -sv_find_char(string_view sv, char c) -{ - ssize_t pos = 0; - while (sv.count > pos && sv.data[pos] != c) - pos++; - for (pos = 0; pos < sv.count && sv.data[pos] != c; pos++); - return pos < sv.count ? pos : -1; -} - -string_view -sv_chop_delim(string_view sv, char c, string_view *rest) -{ - ssize_t pos = sv_find_char(sv, c); - string_view res = sv; - if (pos > 0) { - res.count = pos; - - rest->count -= pos + 1; - rest->data += pos + 1; - } - return res; -} - -string_view -sv_chop(string_view sv, ssize_t count, string_view *rest) -{ - string_view left = {0}; - ssize_t lcount, rcount; - if (count > sv.count) { - lcount = sv.count; - rcount = 0; - } else if (-count > sv.count) { - lcount = 0; - rcount = sv.count; - } else if (count < 0) { - lcount = sv.count + count; - rcount = -count; - } else { - lcount = count; - rcount = sv.count - count; - } - left.data = sv.data; - left.count = lcount; - if (rest) { - rest->data = sv.data + lcount; - rest->count = rcount; - } - return left; -} - -string_view -sv_trim_left(string_view sv) -{ - while (sv.count && isspace(sv.data[0])) { - sv.count--; - sv.data++; - } - return sv; -} - -string_view -sv_trim_right(string_view sv) -{ - while (sv.count && isspace(sv.data[sv.count - 1])) { - sv.count--; - } - return sv; -} - -string_view -sv_trim(string_view sv) -{ - return sv_trim_right(sv_trim_left(sv)); -} - -string_view -sv_substring(string_view sv, ssize_t start, ssize_t req_count) -{ - string_view ss = {0}; - if (start >= sv.count) return ss; - ss.count = (req_count < sv.count - start) ? req_count : sv.count - start; - ss.data = sv.data + start; - return ss; -} - -int -sv_compare(string_view sv1, string_view sv2) -{ - if (sv1.data == sv2.data && sv1.count == sv2.count) return 0; - signed char diff; - ssize_t pos; - for (pos = 0; pos < sv1.count; pos++) { - if (pos == sv2.count) return 1; - if ((diff = sv1.data[pos] - sv2.data[pos])) return diff; - } - return pos < sv2.count ? -1 : 0; -} - -bool -sv_equal(string_view sv1, string_view sv2) -{ - if (sv1.count != sv2.count) return false; - if (sv1.data == sv2.data) return true; - ssize_t pos; - for (pos = 0; pos < sv1.count && sv1.data[pos] == sv2.data[pos]; pos++); - return pos == sv1.count; -} - -string_view -sv_getline(string_view *sv) -{ - string_view line = sv_chop_delim(*sv, '\n', sv); - if (line.count && line.data[line.count - 1] == '\r') { - line.count--; - } - return line; -} - -#endif // DLIB_IMPLEMENTATION - -#endif // DLIB_H diff --git a/ir_backend.c b/ir_backend.c @@ -1,195 +0,0 @@ -typedef struct { - void *loc; - void *end; -} Temp_allocator; - -Temp_allocator temp_allocator = {0}; - -void * -temp_alloc(size_t size) -{ - if (!temp_allocator.loc) { - size_t allocator_size = 1024*1024; - temp_allocator.loc = malloc(allocator_size); - temp_allocator.end = temp_allocator.loc + allocator_size; - temp_allocator.loc = (void *)((intptr_t)(temp_allocator.loc + 0xF) & ~0xFul); - } - void *result = temp_allocator.loc; - temp_allocator.loc += (size + 0xF) & ~0xFul; - if (temp_allocator.loc >= temp_allocator.end) { - fprintf(stderr, "Error: Temp allocator out of memory\n"); - exit(1); - } - return result; -} - -const char * -ir_arg_to_cstr(Ir_arg arg) -{ - int len; - char *str; - if (arg.type == ARG_INT_LITERAL) { - len = snprintf(NULL, 0, "%li", arg.i64) + 1; - str = temp_alloc(len); - snprintf(str, len, "%li", arg.i64); - } else if (arg.type == ARG_TEMP_STORAGE) { - len = snprintf(NULL, 0, "%%%li", arg.temp_id) + 1; - str = temp_alloc(len); - snprintf(str, len, "%%%li", arg.temp_id); - } else if (arg.type == ARG_ADDRESS) { - len = snprintf(NULL, 0, "0x%p", arg.addr) + 1; - str = temp_alloc(len); - snprintf(str, len, "0x%p", arg.addr); - } else if (arg.type == ARG_CSTRING_LITERAL) { - len = strlen(arg.cstr); - str = temp_alloc(len + 3); - memcpy(str + 1, arg.cstr, len); - str[0] = '"'; - str[len + 1] = '"'; - str[len + 2] = '\0'; - } else { - assert(0 && "Invalid arg"); - } - return str; -} - -const char * -ir_binop_to_cstr(enum Ir_binop binop) -{ - const char *str; - switch (binop) { - case OP_ADD: str = "+"; break; - case OP_SUB: str = "-"; break; - case OP_MUL: str = "*"; break; - case OP_DIV: str = "/"; break; - case OP_LT: str = "<"; break; - case OP_GT: str = ">"; break; - case OP_EQ: str = "=="; break; - case OP_LEQ: str = "<="; break; - case OP_GEQ: str = "=>"; break; - default: assert(0 && "Unknown binop"); - } - return str; -} - -const char * -ir_type_to_cstr(enum Ir_type type) -{ - const char *str; - switch (type) { - case TYPE_VOID: str = "void"; break; - case TYPE_I8: str = "i8"; break; - case TYPE_U8: str = "u8"; break; - case TYPE_I16: str = "i16"; break; - case TYPE_U16: str = "u16"; break; - case TYPE_I32: str = "i32"; break; - case TYPE_U32: str = "u32"; break; - case TYPE_I64: str = "i64"; break; - case TYPE_U64: str = "u64"; break; - case TYPE_PTR: str = "ptr"; break; - case TYPE_F32: str = "f32"; break; - case TYPE_F64: str = "f64"; break; - default: assert(0 && "Unknown type"); - } - return str; -} - -bool -ir_compile_body(Ir_list irs, string_builder *sb) -{ - size_t i, j; - Ir ir; - Temp_allocator saved_allocator; - for (i = 0; i < irs.count; i++) { - saved_allocator = temp_allocator; - ir = irs.items[i]; - assert(ir.result.type == ARG_TEMP_STORAGE || ir.result.type == ARG_NONE); - sb_append_cstr(sb, " "); - switch (ir.type) { - case IR_LOAD: - assert(ir.result.type != ARG_NONE); - sb_printf(sb, " %s = load(%s)", ir_arg_to_cstr(ir.result), ir_arg_to_cstr(ir.load.loc)); - break; - case IR_STORE: - assert(ir.result.type == ARG_NONE); - sb_printf(sb, " store(%s, %s)", ir_arg_to_cstr(ir.store.loc), ir_arg_to_cstr(ir.store.data)); - break; - case IR_ASSIGN: - assert(ir.result.type != ARG_NONE); - sb_printf(sb, " %s = %s", ir_arg_to_cstr(ir.result), ir_arg_to_cstr(ir.assign)); - break; - case IR_BINOP: - assert(ir.result.type != ARG_NONE); - sb_printf(sb, " %s = %s %s %s", ir_arg_to_cstr(ir.result), ir_arg_to_cstr(ir.binop.left), ir_binop_to_cstr(ir.binop.op), ir_arg_to_cstr(ir.binop.right)); - break; - case IR_CALL: - assert(ir.result.type != ARG_NONE); - if (ir.call.indirect.type != ARG_NONE) { - sb_printf(sb, " %s = call %s (", ir_arg_to_cstr(ir.result), ir_arg_to_cstr(ir.call.indirect)); - } else { - sb_printf(sb, " %s = call %.*s (", ir_arg_to_cstr(ir.result), ir.call.name.count, ir.call.name.data); - } - for (j = 0; j < ir.call.args.count; j++) { - if (j) { - sb_append_cstr(sb, ", "); - } - sb_append_cstr(sb, ir_arg_to_cstr(ir.call.args.items[j])); - } - sb_append_char(sb, ')'); - break; - case IR_RETURN: - assert(ir.result.type == ARG_NONE); - sb_printf(sb, " return %s", ir_arg_to_cstr(ir.ret)); - break; - case IR_LABEL: - assert(ir.result.type == ARG_NONE); - sb_printf(sb, "#%.*s:", ir.label.count, ir.label.data); - break; - case IR_JUMP: - assert(ir.result.type == ARG_NONE); - sb_printf(sb, " jump #%.*s", ir.jump.label.count, ir.jump.label.data); - break; - case IR_JUMP_IF_NOT: - assert(ir.result.type == ARG_NONE); - sb_printf(sb, " jump_if_not %s #%.*s", ir_arg_to_cstr(ir.jump.cond), ir.jump.label.count, ir.jump.label.data); - break; - default: - fprintf(stderr, "Error: Unknown IR %lu\n", i); - temp_allocator = saved_allocator; - return false; - } - sb_append_char(sb, '\n'); - temp_allocator = saved_allocator; - } - return true; -} - -bool -ir_compile(Ir_program prog, string_builder *sb) -{ - size_t i, j; - Ir_function function; - Temp_allocator saved_allocator; - for (i = 0; i < prog.functions.count; i++) { - saved_allocator = temp_allocator; - if (i) { - sb_append_char(sb, '\n'); - } - function = prog.functions.items[i]; - sb_printf(sb, "$%.*s(", function.name.count, function.name.data); - for (j = 0; j < function.argument_types.count; j++) { - if (j) { - sb_append_cstr(sb, ", "); - } - sb_append_cstr(sb, ir_type_to_cstr(function.argument_types.items[j])); - } - sb_printf(sb, ") -> %s {\n", ir_type_to_cstr(function.return_type)); - if (!ir_compile_body(function.body, sb)) { - temp_allocator = saved_allocator; - return false; - } - sb_append_cstr(sb, "}\n"); - temp_allocator = saved_allocator; - } - return true; -} diff --git a/src/backend.h b/src/backend.h @@ -0,0 +1,225 @@ +#ifndef BACKEND_H +#define BACKEND_H + +typedef struct Ir_program Ir_program; +typedef bool (*Compile_fn)(Ir_program, Sb*); + +typedef struct { + const char *name; + Compile_fn compile; +} Backend; + +typedef enum { + TYPE_UNKNOWN, + TYPE_VOID, + TYPE_I8, + TYPE_I16, + TYPE_I32, + TYPE_I64, + TYPE_PTR, + TYPE_F32, + TYPE_F64, +} Ir_type; + +typedef enum Ir_kind { + IR_LOAD, + IR_STORE, + IR_ASSIGN, + IR_BINOP, + IR_CALL, + IR_RETURN, + /* IR_LABEL, */ + IR_JUMP, + IR_BRANCH, + IR_PHI, + } Ir_kind; + +typedef enum Ir_arg_kind { + ARG_NONE, + ARG_INT_LITERAL, + /*ARG_FLOAT_LITERAL,*/ + ARG_CSTRING_LITERAL, + ARG_TEMP_STORAGE, + ARG_ADDRESS, + ARG_REGISTER, +} Ir_arg_kind; + +typedef enum Ir_binop { + OP_ADD, + OP_SUB, + OP_MUL, + OP_DIV, + OP_LT, + OP_GT, + OP_EQ, + OP_LEQ, + 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 { + enum Ir_arg_kind kind; + Ir_type type; + union { + int64_t i64; + /* double f64; */ + ssize_t temp_id; + void *addr; + /* char *cstr; */ + Sv sv; + enum x86_64_register reg; + }; +} Ir_arg; + +typedef struct { + Ir_arg *items; + size_t count; + size_t capacity; +} Ir_arg_list; + +typedef struct { + ssize_t label_id; + ssize_t temp_id; +} Phi_entry; + +typedef struct { + Phi_entry *items; + unsigned int count; + unsigned int capacity; +} Phi_entry_list; + +typedef struct { + Ir_arg indirect; + Sv name; + Ir_arg_list args; +} Ir_call_args; + +typedef struct { + enum Ir_kind kind; + Ir_arg result; + union { + struct { + Ir_binop op; + Ir_type op_type; + Ir_arg left; + Ir_arg right; + } binop; + struct { + Ir_arg loc; + } load; + struct { + Ir_arg loc; + Ir_arg data; + } store; + Ir_arg assign; + ssize_t label_id; + struct { + ssize_t label_id; + } jump; + struct { + Ir_arg cond; + ssize_t true_label_id; + ssize_t false_label_id; + } branch; + Ir_arg ret; + Ir_call_args call; + Phi_entry_list phi_list; + }; +} Ir; + +typedef struct { + Ir *items; + size_t count; + size_t capacity; +} Ir_block; + +typedef struct { + Ir_type *items; + size_t count; + size_t capacity; +} Ir_type_list; + +typedef struct { + Ir_type type; + union { + int8_t i8; + uint8_t u8; + int16_t i16; + uint16_t u16; + int32_t i32; + uint32_t u32; + int64_t i64; + uint64_t u64; + /* double f64; + float f32; */ + Sv str; + char *cstr; + }; +} Ir_data; + +typedef struct { + Sv name; + Ir_data default_value; +} Ir_static_data; + +typedef struct { + Ir_static_data *items; + size_t count; + size_t capacity; +} Ir_static_data_list; + +typedef struct { + Ir_block *items; + size_t count; + size_t capacity; +} Ir_block_list; + +typedef struct { + Sv name; + Ir_type return_type; + Ir_type_list argument_types; + Ir_block_list body; +} Ir_function; + +typedef struct { + Ir_function *items; + size_t count; + size_t capacity; +} Ir_function_list; + +typedef struct { + Sv symbol; +} Ir_extern; + +typedef struct { + Ir_extern *items; + size_t count; + size_t capacity; +} Ir_extern_list; + +struct Ir_program { + Ir_function_list functions; + Ir_static_data_list data; + Ir_extern_list externs; +}; + +#endif // BACKEND_H diff --git a/src/ir_backend.c b/src/ir_backend.c @@ -0,0 +1,207 @@ +Temp_allocator temp_allocator = {0}; + +const char * +ir_arg_to_cstr(Ir_arg arg) +{ + int len; + char *str; + if (arg.kind == ARG_INT_LITERAL) { + len = snprintf(NULL, 0, "%li", arg.i64) + 1; + str = ta_alloc(&temp_allocator, len); + snprintf(str, len, "%li", arg.i64); + } else if (arg.kind == ARG_TEMP_STORAGE) { + len = snprintf(NULL, 0, "%%%li", arg.temp_id) + 1; + str = ta_alloc(&temp_allocator, len); + snprintf(str, len, "%%%li", arg.temp_id); + } else if (arg.kind == ARG_ADDRESS) { + len = snprintf(NULL, 0, "0x%p", arg.addr) + 1; + str = ta_alloc(&temp_allocator, len); + snprintf(str, len, "0x%p", arg.addr); + } else if (arg.kind == ARG_CSTRING_LITERAL) { + str = ta_alloc(&temp_allocator, arg.sv.count + 3); + memcpy(str + 1, arg.sv.items, arg.sv.count); + str[0] = '"'; + str[arg.sv.count + 1] = '"'; + str[arg.sv.count + 2] = '\0'; + } else { + fprintf(stderr, "Invalid arg %i\n", arg.kind); + abort(); + } + return str; +} + +const char * +ir_binop_to_cstr(enum Ir_binop binop) +{ + const char *str; + switch (binop) { + case OP_ADD: str = "+"; break; + case OP_SUB: str = "-"; break; + case OP_MUL: str = "*"; break; + case OP_DIV: str = "/"; break; + case OP_LT: str = "<"; break; + case OP_GT: str = ">"; break; + case OP_EQ: str = "=="; break; + case OP_LEQ: str = "<="; break; + case OP_GEQ: str = "=>"; break; + default: assert(0 && "Unknown binop"); + } + return str; +} + +const char * +ir_type_to_cstr(Ir_type type) +{ + const char *str; + switch (type) { + case TYPE_VOID: str = "void"; break; + case TYPE_I8: str = "i8"; break; + case TYPE_I16: str = "i16"; break; + case TYPE_I32: str = "i32"; break; + case TYPE_I64: str = "i64"; break; + case TYPE_PTR: str = "ptr"; break; + case TYPE_F32: str = "f32"; break; + case TYPE_F64: str = "f64"; break; + case TYPE_UNKNOWN: str = "??"; break; + default: assert(0 && "Unknown type"); + } + return str; +} + +bool +ir_compile_block(Ir_block block, Sb *sb) +{ + size_t i, j; + Ir ir; + Temp_allocator saved_allocator; + for (i = 0; i < block.count; i++) { + saved_allocator = temp_allocator; + ir = block.items[i]; + assert(ir.result.kind == ARG_TEMP_STORAGE || ir.result.kind == ARG_NONE); + sb_append_cstr(sb, " "); + switch (ir.kind) { + case IR_LOAD: + assert(ir.result.kind != ARG_NONE); + assert(ir.result.type != TYPE_VOID); + sb_printf(sb, " %s =%s load(%s)", ir_arg_to_cstr(ir.result), ir_type_to_cstr(ir.result.type), ir_arg_to_cstr(ir.load.loc)); + break; + case IR_STORE: + assert(ir.result.kind == ARG_NONE); + assert(ir.store.data.type != TYPE_VOID); + sb_printf(sb, " store(%s, %s %s)", ir_arg_to_cstr(ir.store.loc), ir_type_to_cstr(ir.store.data.type), ir_arg_to_cstr(ir.store.data)); + break; + case IR_ASSIGN: + assert(ir.result.kind != ARG_NONE); + assert(ir.result.type != TYPE_VOID); + sb_printf(sb, " %s =%s %s", ir_arg_to_cstr(ir.result), ir_type_to_cstr(ir.result.type), ir_arg_to_cstr(ir.assign)); + break; + case IR_BINOP: + assert(ir.result.kind != ARG_NONE); + assert(ir.result.type != TYPE_VOID); + sb_printf(sb, " %s = %s %s %s", ir_arg_to_cstr(ir.result), ir_arg_to_cstr(ir.binop.left), ir_binop_to_cstr(ir.binop.op), ir_arg_to_cstr(ir.binop.right)); + break; + case IR_CALL: + assert(ir.result.kind != ARG_NONE); + if (ir.call.indirect.kind != ARG_NONE) { + sb_printf(sb, " %s = call %s (", ir_arg_to_cstr(ir.result), ir_arg_to_cstr(ir.call.indirect)); + } else { + sb_printf(sb, " %s = call $%.*s (", ir_arg_to_cstr(ir.result), ir.call.name.count, ir.call.name.data); + } + for (j = 0; j < ir.call.args.count; j++) { + if (j) { + sb_append_cstr(sb, ", "); + } + sb_append_cstr(sb, ir_arg_to_cstr(ir.call.args.items[j])); + } + sb_append_char(sb, ')'); + break; + case IR_RETURN: + assert(ir.result.kind == ARG_NONE); + sb_printf(sb, " return %s", ir_arg_to_cstr(ir.ret)); + break; + /* case IR_LABEL: */ + /* assert(ir.result.kind == ARG_NONE); */ + /* sb_printf(sb, "#%li:", ir.label_id); */ + /* break; */ + case IR_JUMP: + assert(ir.result.kind == ARG_NONE); + sb_printf(sb, " jump #%li", ir.jump.label_id); + 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); + break; + case IR_PHI: + assert(ir.result.kind == ARG_TEMP_STORAGE); + sb_printf(sb, " phi %s [", ir_arg_to_cstr(ir.result)); + for (j = 0; j < ir.phi_list.count; j++) { + if (j) { + da_append(sb, ' '); + } + sb_printf(sb, "(#%li %%%li)", ir.phi_list.items[j].label_id, ir.phi_list.items[j].temp_id); + } + sb_printf(sb, "]"); + break; + default: + fprintf(stderr, "Error: Unknown IR %lu\n", i); + temp_allocator = saved_allocator; + return false; + } + sb_append_char(sb, '\n'); + temp_allocator = saved_allocator; + } + return true; +} + +bool +ir_dump_extern(Ir_extern ext, Sb *sb) +{ + sb_printf(sb, "extern $%.*s\n", (int) ext.symbol.count, ext.symbol.data); + return true; +} + +bool +ir_dump(Ir_program prog, Sb *sb) +{ + size_t i, j; + Ir_function function; + Temp_allocator saved_allocator; + for (i = 0; i < prog.externs.count; i++) { + if (!ir_dump_extern(prog.externs.items[i], sb)) { + return false; + } + } + if (i) { + sb_append_char(sb, '\n'); + } + for (i = 0; i < prog.functions.count; i++) { + saved_allocator = temp_allocator; + if (i) { + sb_append_char(sb, '\n'); + } + function = prog.functions.items[i]; + sb_printf(sb, "$%.*s(", function.name.count, function.name.data); + for (j = 0; j < function.argument_types.count; j++) { + if (j) { + sb_append_cstr(sb, ", "); + } + sb_append_cstr(sb, ir_type_to_cstr(function.argument_types.items[j])); + } + 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 (!ir_compile_block(function.body.items[j], sb)) { + temp_allocator = saved_allocator; + return false; + } + } + sb_append_cstr(sb, "}\n"); + temp_allocator = saved_allocator; + } + return true; +} + +Backend ir_backend = { + "IR Dump", + ir_dump, +}; diff --git a/src/lexer.c b/src/lexer.c @@ -0,0 +1,651 @@ +#include <fcntl.h> + +#include "dlib.h" +#include "lexer.h" + +Sv keywords[] = { + [T_RETURN - T_KEYWORDS_] = sv_literal("return"), + [T_EXTERN - T_KEYWORDS_] = sv_literal("extern"), + [T_I8 - T_KEYWORDS_] = sv_literal("i8"), + [T_I16 - T_KEYWORDS_] = sv_literal("i16"), + [T_I32 - T_KEYWORDS_] = sv_literal("i32"), + [T_I64 - T_KEYWORDS_] = sv_literal("i64"), + [T_PTR - T_KEYWORDS_] = sv_literal("ptr"), + [T_VOID - T_KEYWORDS_] = sv_literal("void"), + [T_CALL - T_KEYWORDS_] = sv_literal("call"), + [T_JUMP - T_KEYWORDS_] = sv_literal("jump"), + [T_BRANCH - T_KEYWORDS_] = sv_literal("branch"), + [T_PHI - T_KEYWORDS_] = sv_literal("phi"), +}; + +static_assert(T_COUNT_ - T_KEYWORDS_ == 12, "keywords[] wrong length"); +int keywords_count = (sizeof(keywords) / sizeof(keywords[0])); + +void +sb_append_loc(Sb *sb, Loc loc) +{ + sb_printf(sb, "%.*s:%li:%li: ", (int) loc.filename.count, loc.filename.items, loc.line, loc.column); +} + +void +sb_append_token_kind(Sb *sb, Token_kind kind) +{ + if (kind >= 32 && kind <= 127) sb_append_char(sb, kind); + else if (kind == T_ERROR_) sb_append_cstr(sb, "T_ERROR_"); + else if (kind == T_EOF) sb_append_cstr(sb, "T_EOF"); + else if (kind == T_INVALID) sb_append_cstr(sb, "T_INVALID"); + else if (kind == T_WHITESPACE) sb_append_cstr(sb, "T_WHITESPACE"); + else if (kind == T_WHITESPACE_NL) sb_append_cstr(sb, "T_WHITESPACE_NL"); + else if (kind == T_FUNCTION_SYMBOL) sb_append_cstr(sb, "T_FUNCTION_SYMBOL"); + else if (kind == T_LABEL) sb_append_cstr(sb, "T_LABEL"); + else if (kind == T_TEMP) sb_append_cstr(sb, "T_TEMP"); + else if (kind == T_ARROW) sb_append_cstr(sb, "->"); + else if (kind == T_RETURN) sb_append_cstr(sb, "return"); + else if (kind == T_EXTERN) sb_append_cstr(sb, "extern"); + else if (kind == T_I8) sb_append_cstr(sb, "i8"); + else if (kind == T_I16) sb_append_cstr(sb, "i16"); + else if (kind == T_I32) sb_append_cstr(sb, "i32"); + else if (kind == T_I64) sb_append_cstr(sb, "i64"); + else if (kind == T_PTR) sb_append_cstr(sb, "ptr"); + else if (kind == T_VOID) sb_append_cstr(sb, "void"); + else if (kind == T_CALL) sb_append_cstr(sb, "call"); + else if (kind == T_JUMP) sb_append_cstr(sb, "jump"); + else if (kind == T_BRANCH) sb_append_cstr(sb, "branch"); + else if (kind == T_PHI) sb_append_cstr(sb, "phi"); + else sb_append_cstr(sb, "(unknown token)"); +} + +void +print_loc(Loc loc) +{ + fprintf(stderr, "%.*s:%li:%li: ", (int) loc.filename.count, loc.filename.items, loc.line, loc.column); +} + +void +print_loc_pad(Loc loc, int min_width) +{ + int len = fprintf(stderr, "%.*s:%li:%li: ", (int) loc.filename.count, loc.filename.items, loc.line, loc.column); + if (len < min_width) { + fprintf(stderr, "%*s", min_width - len, ""); + } +} + +void +debug_print_token(Token t) +{ + print_loc(t.loc); + if (t.kind == T_ERROR_) { + fprintf(stderr, "ERROR"); + } else if (t.kind >= 32 && t.kind < 127) { + fprintf(stderr, "'%c'", t.kind); + } else if (t.kind == T_EOF) { + fprintf(stderr, "EOF"); + } else if (t.kind == T_WHITESPACE || t.kind == T_WHITESPACE_NL) { + if (t.kind == T_WHITESPACE) { + fprintf(stderr, "WHITESPACE("); + } else { + fprintf(stderr, "WHITESPACE_NL("); + } + char last_char = '?'; + int last_char_count = 0; + for (int i = 0; i < t.sv.count; i++) { + char c = '?'; + switch (t.sv.items[i]) { + case ' ' : c = 's'; break; + case '\t': c = 't'; break; + case '\n': c = 'n'; break; + case '\r': c = 'r'; break; + case '\v': c = 'v'; break; + case '\f': c = 'f'; break; + } + if (last_char != c) { + if (last_char_count > 1) { + fprintf(stderr, "(%i)", last_char_count); + } + last_char_count = 0; + fputc(c, stderr); + } else if (!last_char_count) { + fputc(c, stderr); + } + last_char = c; + last_char_count++; + } + if (last_char_count > 1) { + fprintf(stderr, "(%i)", last_char_count); + } + fputc(')', stderr); + } else if (t.kind == T_IDENT) { + fprintf(stderr, "IDENT(%.*s)", (int) t.sv.count, t.sv.items); + } else if (t.kind == T_NUMBER) { + fprintf(stderr, "NUMBER(%.*s)", (int) t.sv.count, t.sv.items); + } else if (t.kind == T_SQ_STRING || t.kind == T_DQ_STRING) { + fprintf(stderr, "STRING(%.*s)", (int) t.sv.count, t.sv.items); + } else if (t.kind >= T_KEYWORDS_ && t.kind < T_COUNT_) { + Sv keyword = keywords[t.kind - T_KEYWORDS_]; + fprintf(stderr, "%.*s", (int) keyword.count, keyword.data); + } else { + fprintf(stderr, "unknown token 0x%02x", t.kind); + } + fprintf(stderr, "\n"); +} + +int +next_utf8_continuation(Lexer *lexer) +{ + if (!lexer->source.count) { + fprintf(stderr, "Error: expected utf-8 continuation byte\n"); + return CHAR_INVALID; + } + unsigned int c = *lexer->source.items++; + lexer->source.count--; + if ((c & 0b11000000) != 0b10000000) { + print_loc(lexer->current_loc); + fprintf(stderr, "Error: expected utf-8 continuation byte\n"); + return CHAR_INVALID; + } + return c & 0b00111111; +} + +int +next_char(Lexer *lexer) +{ + int result; + if (!lexer->source.count) return EOF; + unsigned int c0 = *lexer->source.items++; + int c1; + lexer->source.count--; + result = c0; + if (c0 == '\n') { + lexer->current_loc.column = 1; + lexer->current_loc.line++; + } else { + if (c0 > 127) { + if ((c0 & 0b11000000) != 0b11000000) { + print_loc(lexer->current_loc); + fprintf(stderr, "Error: invalid utf-8 character\n"); + return CHAR_INVALID; + } + c1 = next_utf8_continuation(lexer); + if (c1 == CHAR_INVALID) return CHAR_INVALID; + result = (c0 & 0b00011111) << 6 | c1; + + if ((c0 & 0b11100000) == 0b11100000) { + c1 = next_utf8_continuation(lexer); + if (c1 == CHAR_INVALID) return CHAR_INVALID; + result = result << 6 | c1; + } + if ((c0 & 0b11110000) == 0b11110000) { + c1 = next_utf8_continuation(lexer); + if (c1 == CHAR_INVALID) return CHAR_INVALID; + result = result << 6 | c1; + } + if ((c0 & 0b11111000) == 0b11111000) { + c1 = next_utf8_continuation(lexer); + if (c1 == CHAR_INVALID) return CHAR_INVALID; + result = result << 6 | c1; + } + if ((c0 & 0b11111110) == 0b11111100) { + c1 = next_utf8_continuation(lexer); + if (c1 == CHAR_INVALID) return CHAR_INVALID; + result = result << 6 | c1; + } + } + lexer->current_loc.column++; + } + return result; +} + +int +peek_char(Lexer *lexer) +{ + if (!lexer->source.count || lexer->source.count == 1) return EOF; + return *lexer->source.items; +} + +int +next_char_if(Lexer *lexer, int (*pred)(int)) +{ + if (!lexer->source.count) return EOF; + if (pred(*lexer->source.items)) { + return next_char(lexer); + } + return CHAR_INVALID; +} + +int +isbdigit_or_sep(int c) +{ + if (c == '_') return true; + return isbdigit(c); +} + +int +isodigit_or_sep(int c) +{ + if (c == '_') return true; + return isodigit(c); +} + +int +isddigit_or_sep(int c) +{ + if (c == '_') return true; + return isddigit(c); +} + +int +isxdigit_or_sep(int c) +{ + if (c == '_') return true; + return isxdigit(c); +} + +int +is_ident_char(int c) +{ + return c == '_' || + (c >= '0' && c <= '9') || + (c >= 'A' && c <= 'Z') || + (c >= 'a' && c <= 'z'); +} + +int +is_symbol_char(int c) +{ + return c == '+' || + c == '-' || + c == '*' || + c == '/' || + c == '%' || + c == '(' || + c == ')' || + c == '[' || + c == ']' || + c == '<' || + c == '>' || + c == '{' || + c == '}' || + c == '=' || + c == '&' || + c == '|' || + c == '^' || + c == '~' || + c == '?' || + c == '!' || + c == '.' || + c == ',' || + c == ':' || + c == ';' || + c == '`' || + c == '#' || + c == '@' || + c == '$' || + 0; +} + +bool +is_operator_token(Token_kind kind) { + return kind == '+' || + kind == '-' || + kind == '*' || + kind == '/' || + kind == '%' || + /* kind == '(' || */ + /* kind == ')' || */ + /* kind == '[' || */ + /* kind == ']' || */ + kind == '<' || + kind == '>' || + /* kind == '{' || */ + /* kind == '}' || */ + kind == '=' || + kind == '&' || + kind == '|' || + kind == '^' || + kind == '~' || + kind == '?' || + kind == '!' || + /* kind == '.' || */ + /* kind == ',' || */ + kind == T_IDENT || + 0; +} + +int +skip_comment(Lexer *lexer) +{ + Loc start_loc = lexer->current_loc; + int len = 0; + if (sv_starts_with_cstr(lexer->source, "/*")) { + len = 2; + next_char(lexer); + next_char(lexer); + while (lexer->source.count && !sv_starts_with_cstr(lexer->source, "*/")) { + if (sv_starts_with_cstr(lexer->source, "/*")) { + len += skip_comment(lexer); + } else { + len++; + next_char(lexer); + } + } + if (!lexer->source.count) { + print_loc(start_loc); + fprintf(stderr, "Error: unterminated comment\n"); + return -1; + } + next_char(lexer); + next_char(lexer); + len += 2; + } else if (sv_starts_with_cstr(lexer->source, "//")) { + char next; + while ((next = next_char(lexer)) != '\n' && next != EOF) len++; + } + return len; +} + +Token +next_token(Lexer *lexer) +{ + Loc start_loc = lexer->current_loc; + Token result = { .loc = start_loc, .sv = { .items = lexer->source.items, .count = 0 } }; + + if (lexer->last_tok.kind != T_WHITESPACE) { + lexer->last_valid_loc = start_loc; + } + + if (!lexer->source.count) { + result.kind = T_EOF; + lexer->last_tok = result; + return result; + } + + int c = next_char_if(lexer, isspace); + size_t len = 0; + + { + bool whitespace = false; + int comment_len = 0; + while (isspace(c) || (comment_len = skip_comment(lexer))) { + if (comment_len < 0) { + return (Token) { + .kind = T_ERROR_, + .loc = start_loc, + }; + } else if (comment_len > 0) { + len += comment_len; + } else { + len++; + } + whitespace = true; + while ((c = next_char_if(lexer, isspace)) >= 0) { + len++; + } + } + if (whitespace) { + if (start_loc.line < lexer->current_loc.line) { + result.kind = T_WHITESPACE_NL; + } else { + result.kind = T_WHITESPACE; + } + result.sv.count = len; + lexer->last_tok = result; + return result; + } + } + + len = 1; + + c = next_char(lexer); + + if (c == '$' && is_ident_char(peek_char(lexer))) { + result.sv.data++; + len = 0; + while (next_char_if(lexer, is_ident_char) >= 0) len++; + assert(len > 0); + result.sv.count = len; + result.kind = T_FUNCTION_SYMBOL; + lexer->last_tok = result; + return result; + } + + if (c == '#' && isdigit(peek_char(lexer))) { + result.sv.data++; + len = 0; + while (next_char_if(lexer, isdigit) >= 0) len++; + result.kind = T_LABEL; + result.sv.count = len; + result.i64 = sv_to_number(result.sv, 10); + lexer->last_tok = result; + return result; + } + + if (c == '%' && isdigit(peek_char(lexer))) { + result.sv.data++; + len = 0; + while (next_char_if(lexer, isdigit) >= 0) len++; + result.kind = T_TEMP; + result.sv.count = len; + result.i64 = sv_to_number(result.sv, 10); + lexer->last_tok = result; + return result; + } + + if (c == '-' && peek_char(lexer) == '>') { + len++; + next_char(lexer); + result.sv.count = len; + result.kind = T_ARROW; + lexer->last_tok = result; + return result; + } + + if (c == '-' && isdigit(peek_char(lexer))) { + c = next_char(lexer); + len++; + } + if (isdigit(c)) { + int peek; + int base = 10; + int (*digit_fn)(int) = isddigit_or_sep; + if (c == '0') { + peek = peek_char(lexer); + len++; + if (peek == 'b') { + next_char(lexer); + base = 2; + digit_fn = isbdigit_or_sep; + } else if (peek == 'o') { + next_char(lexer); + base = 8; + digit_fn = isodigit_or_sep; + } else if (peek == 'x') { + next_char(lexer); + base = 16; + digit_fn = isxdigit_or_sep; + } else { + len--; + base = 8; + digit_fn = isodigit_or_sep; + } + } + + while (next_char_if(lexer, digit_fn) >= 0) len++; + + result.kind = T_NUMBER; + result.sv.count = len; + result.i64 = sv_to_number(result.sv, base); + lexer->last_tok = result; + return result; + } + + if (is_ident_char(c)) { + while (next_char_if(lexer, is_ident_char) >= 0) len++; + result.sv.count = len; + result.kind = get_keyword_kind(result.sv); + lexer->last_tok = result; + return result; + } + + if (is_symbol_char(c)) { + result.kind = c; + result.sv.count = len; + lexer->last_tok = result; + return result; + } + + if (c == '\'' || c == '"') { + char next; + while ((next = next_char(lexer)) != EOF && next != c) { + len++; + if (next == '\\') { + next_char(lexer); + len++; + } + } + if (next != c) { + print_loc(start_loc); + fprintf(stderr, "Error: unterminated %s quoted string\n", c == '"' ? "double" : "single"); + + return (Token) { + .kind = T_ERROR_, + .loc = start_loc, + }; + } + result.kind = c == '"' ? T_DQ_STRING : T_SQ_STRING; + result.sv.count = --len; + result.sv.data++; + lexer->last_tok = result; + return result; + } + + print_loc(start_loc); + fprintf(stderr, "Error: unknown character '%c'\n", c); + + return (Token) { + .kind = T_ERROR_, + .loc = start_loc, + }; +} + +Token +peek_token(Lexer *lexer) +{ + Lexer peek = *lexer; + return next_token(&peek); +} + +Token_kind +get_keyword_kind(Sv sv) +{ + int i = 0; + for (;i < keywords_count; i++) { + if (sv_equal(sv, keywords[i])) { + return i + T_KEYWORDS_; + } + } + return T_IDENT; +} + +Token +next_token_if_kind(Lexer *lexer, Token_kind kind) +{ + Lexer peek = *lexer; + Token t = next_token(&peek); + if (t.kind == kind) { + *lexer = peek; + return t; + } + return (Token) { + .kind = T_INVALID, + .loc = lexer->current_loc, + }; +} + +Token +next_token_if(Lexer *lexer, int (*pred)(Token)) +{ + Lexer peek = *lexer; + Token t = next_token(&peek); + if (pred(t)) { + *lexer = peek; + return t; + } + return (Token) { + .kind = T_INVALID, + .loc = lexer->current_loc, + }; +} + +void +skip_whitespace(Lexer *lexer) +{ + Lexer peek = *lexer; + Token t = next_token(&peek); + if (t.kind == T_WHITESPACE || t.kind == T_WHITESPACE_NL) { + *lexer = peek; + } +} + +bool +expect_token_kind(Lexer *lexer, Token_kind kind) +{ + Token t = next_token(lexer); + if (t.kind != kind) { + Sb error = {0}; + + /* sb_append_loc(&error, t.loc); */ + sb_append_loc(&error, lexer->last_valid_loc); + sb_append_cstr(&error, "Error: expected token "); + sb_append_token_kind(&error, kind); + sb_append_cstr(&error, ", but got "); + sb_append_token_kind(&error, t.kind); + + fprintf(stderr, "%.*s\n", (int) error.count, error.items); + + sb_release(&error); + return false; + /* return (Token) { */ + /* .kind = T_ERROR_, */ + /* .loc = t.loc, */ + /* }; */ + } + return true; +} + +bool +expect_end_statement_impl(Lexer *lexer, const char *file, int line) +{ + if (lexer->last_tok.kind == T_WHITESPACE_NL) { + fprintf(stderr, "%s:%i: expect_end_statement hack\n", file, line); + return true; + /* return lexer->last_tok; */ + } + Token t = next_token(lexer); + if (t.kind == ';' || t.kind == T_WHITESPACE_NL) { + /* return t; */ + skip_whitespace(lexer); + return true; + } + if (t.kind == T_WHITESPACE) { + if (peek_token(lexer).kind == ';') { + next_token(lexer); + skip_whitespace(lexer); + return true; + } + } + Sb error = {0}; + + /* sb_append_loc(&error, t.loc); */ + sb_append_loc(&error, lexer->last_valid_loc); + sb_append_cstr(&error, "Error: expected ; or newline, but got "); + sb_append_token_kind(&error, t.kind); + + fprintf(stderr, "%.*s\n", (int) error.count, error.items); + + sb_release(&error); + return false; + /* return (Token) { */ + /* .kind = T_ERROR_, */ + /* .loc = t.loc, */ + /* }; */ +} diff --git a/src/lexer.h b/src/lexer.h @@ -0,0 +1,88 @@ +#ifndef DC_LEXER_H +#define DC_LEXER_H + +#include "dlib.h" + +typedef struct { + Sv filename; + size_t line, column; +} Loc; + +typedef enum { + T_ERROR_ = 0, + T_EOF = 256, + T_INVALID, + T_WHITESPACE, + T_WHITESPACE_NL, + T_IDENT, + T_NUMBER, + T_SQ_STRING, + T_DQ_STRING, + T_ARROW, + T_FUNCTION_SYMBOL, + T_LABEL, + T_TEMP, + + T_KEYWORDS_, + + T_RETURN = T_KEYWORDS_, + T_EXTERN, + T_I8, + T_I16, + T_I32, + T_I64, + T_PTR, + T_VOID, + T_CALL, + T_JUMP, + T_BRANCH, + T_PHI, + + T_COUNT_ +} Token_kind; + +typedef struct { + Token_kind kind; + Loc loc; + Sv sv; + long int i64; +} Token; + +typedef struct { + Sv source; + Loc current_loc; + Token last_tok; + Loc last_valid_loc; +} Lexer; + +#define CHAR_INVALID (-2) +int next_char(Lexer *lexer); +int next_char_if(Lexer *lexer, int (*pred)(int)); + +int is_ident_char(int c); +int is_symbol_char(int c); +bool is_operator_token(Token_kind kind); + +int skip_comment(Lexer *lexer); +Token next_token(Lexer *lexer); +Token peek_token(Lexer *lexer); + +Token_kind get_keyword_kind(Sv sv); + +Token next_token_if(Lexer *lexer, int (*pred)(Token)); +Token next_token_if_kind(Lexer *lexer, Token_kind kind); +bool expect_token_kind(Lexer *lexer, Token_kind kind); + +bool expect_end_statement_impl(Lexer *lexer, const char *file, int line); +#define expect_end_statement(l) expect_end_statement_impl(l, __FILE__, __LINE__) + +void skip_whitespace(Lexer *lexer); + +void sb_append_token_kind(Sb *sb, Token_kind kind); +void sb_append_loc(Sb *sb, Loc loc); + +void print_loc(Loc loc); +void print_loc_pad(Loc loc, int min_width); +void debug_print_token(Token t); + +#endif /* DC_LEXER_H */ diff --git a/src/parse.c b/src/parse.c @@ -0,0 +1,546 @@ +#define DLIB_IMPLEMENTATION +#include "dlib.h" + +#include "lexer.h" + +#include "backend.h" +#include "phi.c" +#include "ir_backend.c" +#include "x86_64-codegen.c" + +char *input_source_2 = +/* "extern $printf(ptr, i32) -> i32\n" */ +"extern $printf\n" +"$foo() -> i32 {\n" +"#0:\n" +" %0 =i32 0\n" +" jump #1\n" +"#1:\n" +" %1 =i32 phi [(#0 %0) (#2 %5)]\n" +" %2 =i32 phi [(#0 %0) (#2 %4)]\n" +" %3 =i8 %1 <i32 11\n" +" branch %3 #2 #3\n" +"#2:\n" +" %4 =i32 call $printf (ptr \"%i\\n\", i32 %1)\n" +" %5 =i32 %1 +i32 1\n" +" jump #1\n" +"#3:\n" +" return i32 %2\n" +"}" + +/* char *input_source = */ +"$main() -> i32 {\n" +"#0:\n" +" %0 =i32 call $foo()\n" +" return i32 %0\n" +"}"; + +bool +is_binary_operator(Token t) +{ + Token_kind k = t.kind; + return k == '+' || + k == '<'; +} + +Ir_binop +ir_binop_from_token(Token t) +{ + if (t.kind == '+') return OP_ADD; + else if (t.kind == '<') return OP_LT; + unreachable("binop token"); +} + +bool +parse_ir_extern(Ir_program *out_prog, Lexer *lexer) +{ + skip_whitespace(lexer); + if (!expect_token_kind(lexer, T_FUNCTION_SYMBOL)) { + return false; + } + da_append(&out_prog->externs, ((Ir_extern) { .symbol = lexer->last_tok.sv })); + expect_end_statement(lexer); + return true; +} + +bool +parse_ir_type(Ir_type *out_type, Lexer *lexer) +{ + Token t = next_token(lexer); + if (t.kind == T_I8) { + *out_type = TYPE_I8; + } else if (t.kind == T_I16) { + *out_type = TYPE_I16; + } else if (t.kind == T_I32) { + *out_type = TYPE_I32; + } else if (t.kind == T_I64) { + *out_type = TYPE_I64; + } else if (t.kind == T_PTR) { + *out_type = TYPE_PTR; + } else if (t.kind == T_VOID) { + *out_type = TYPE_VOID; + } else { + print_loc(t.loc); + fprintf(stderr, "Error: expected type\n"); + return false; + } + return true; +} + +bool +parse_ir_value(Ir_arg *out_arg, Lexer *lexer) +{ + Token t = next_token(lexer); + if (t.kind == T_TEMP) { + *out_arg = (Ir_arg) { + .kind = ARG_TEMP_STORAGE, + .type = TYPE_UNKNOWN, + .temp_id = t.i64, + }; + } else if (t.kind == T_NUMBER) { + *out_arg = (Ir_arg) { + .kind = ARG_INT_LITERAL, + .type = TYPE_UNKNOWN, + .temp_id = t.i64, + }; + } else if (t.kind == T_DQ_STRING) { + *out_arg = (Ir_arg) { + .kind = ARG_CSTRING_LITERAL, + .type = TYPE_PTR, + .sv = t.sv, + }; + } else { + print_loc(t.loc); + fprintf(stderr, "Error: expected value\n"); + debug_print_token(t); + return false; + } + return true; +} + +bool +parse_ir_call(Ir_call_args *out_call_args, Lexer *lexer) +{ + if (!expect_token_kind(lexer, T_FUNCTION_SYMBOL)) { + return false; + } + out_call_args->name = lexer->last_tok.sv; + skip_whitespace(lexer); + if (!expect_token_kind(lexer, '(')) { + return false; + } + skip_whitespace(lexer); + while (peek_token(lexer).kind != ')') { + Ir_type type = {0}; + Ir_arg arg = {0}; + if (!parse_ir_type(&type, lexer)) { + return false; + } + skip_whitespace(lexer); + if (!parse_ir_value(&arg, lexer)) { + return false; + } + skip_whitespace(lexer); + arg.type = type; + da_append(&out_call_args->args, arg); + skip_whitespace(lexer); + if (peek_token(lexer).kind != ',') { + break; + } + next_token(lexer); + skip_whitespace(lexer); + } + if (!expect_token_kind(lexer, ')')) { + return false; + } + return true; +} + +bool +parse_ir_phi_list(Phi_entry_list *out_phi_list, Lexer *lexer) +{ + if (!expect_token_kind(lexer, '[')) { + return false; + } + skip_whitespace(lexer); + do { + Phi_entry phi = {0}; + if (!expect_token_kind(lexer, '(')) { + return false; + } + skip_whitespace(lexer); + if (!expect_token_kind(lexer, T_LABEL)) { + return false; + } + phi.label_id = lexer->last_tok.i64; + skip_whitespace(lexer); + if (!expect_token_kind(lexer, T_TEMP)) { + return false; + } + phi.temp_id = lexer->last_tok.i64; + skip_whitespace(lexer); + if (!expect_token_kind(lexer, ')')) { + return false; + } + da_append(out_phi_list, phi); + skip_whitespace(lexer); + } while (peek_token(lexer).kind != ']'); + next_token(lexer); + return true; +} + +bool +parse_ir_assignment(Ir *out_ins, Lexer *lexer) +{ + Ir_arg result = { .kind = ARG_TEMP_STORAGE, .temp_id = lexer->last_tok.i64 }; + Ir_type type = {0}; + Ir_arg arg1 = {0}; + Ir_arg arg2 = {0}; + skip_whitespace(lexer); + if (!expect_token_kind(lexer, '=')) { + return false; + } + skip_whitespace(lexer); + if (!parse_ir_type(&result.type, lexer)) { + return false; + } + skip_whitespace(lexer); + + Token t = peek_token(lexer); + if (t.kind == T_CALL) { + next_token(lexer); + skip_whitespace(lexer); + Ir_call_args call_args = {0}; + if (!parse_ir_call(&call_args, lexer)) { + return false; + } + *out_ins = (Ir) { + .kind = IR_CALL, + .result = result, + .call = call_args, + }; + } else if (t.kind == T_PHI) { + next_token(lexer); + skip_whitespace(lexer); + Phi_entry_list phi_list = {0}; + if (!parse_ir_phi_list(&phi_list, lexer)) { + return false; + } + *out_ins = (Ir) { + .kind = IR_PHI, + .result = result, + .phi_list = phi_list, + }; + } else { + if (!parse_ir_value(&arg1, lexer)) { + return false; + } + next_token_if_kind(lexer, T_WHITESPACE); + t = peek_token(lexer); + if (is_binary_operator(t)) { + next_token(lexer); + skip_whitespace(lexer); + if (!parse_ir_type(&type, lexer)) { + return false; + } + skip_whitespace(lexer); + if (!parse_ir_value(&arg2, lexer)) { + return false; + } + arg1.type = type; + arg2.type = type; + *out_ins = (Ir) { + .kind = IR_BINOP, + .result = result, + .binop = { + .op = ir_binop_from_token(t), + .op_type = type, + .left = arg1, + .right = arg2, + }, + }; + } else { + arg1.type = type; + *out_ins = (Ir) { + .kind = IR_ASSIGN, + .result = result, + .assign = arg1, + }; + } + } + return true; +} + +bool +parse_ir_return(Ir *out_ins, Lexer *lexer) +{ + Ir_arg value = {0}; + + Ir_type type = {0}; + skip_whitespace(lexer); + if (!parse_ir_type(&type, lexer)) { + return false; + } + + skip_whitespace(lexer); + if (!parse_ir_value(&value, lexer)) { + return false; + } + + value.type = type; + *out_ins = (Ir) { + .kind = IR_RETURN, + .ret = value, + }; + return true; +} + +bool +parse_ir_jump(Ir *out_ins, Lexer *lexer) +{ + skip_whitespace(lexer); + if (!expect_token_kind(lexer, T_LABEL)) { + return false; + } + + *out_ins = (Ir) { + .kind = IR_JUMP, + .jump = { .label_id = lexer->last_tok.i64 }, + }; + return true; +} + +bool +parse_ir_branch(Ir *out_ins, Lexer *lexer) +{ + Ir_arg cond = {0}; + skip_whitespace(lexer); + if (!parse_ir_value(&cond, lexer)) { + return false; + } + skip_whitespace(lexer); + if (!expect_token_kind(lexer, T_LABEL)) { + return false; + } + size_t true_label = lexer->last_tok.i64; + skip_whitespace(lexer); + if (!expect_token_kind(lexer, T_LABEL)) { + return false; + } + size_t false_label = lexer->last_tok.i64; + *out_ins = (Ir) { + .kind = IR_BRANCH, + .branch = { + .cond = cond, + .true_label_id = true_label, + .false_label_id = false_label, + }, + }; + return true; +} + +bool +parse_ir_basic_block(Ir_block *out_block, Lexer *lexer) +{ + bool found_end_statement = false; + Ir ins = {0}; + while (!found_end_statement) { + Token t = next_token(lexer); + if (t.kind == T_TEMP) { + if (!parse_ir_assignment(&ins, lexer)) { + return false; + } + } else if (t.kind == T_RETURN) { + if (!parse_ir_return(&ins, lexer)) { + return false; + } + found_end_statement = true; + } else if (t.kind == T_JUMP) { + if (!parse_ir_jump(&ins, lexer)) { + return false; + } + found_end_statement = true; + } else if (t.kind == T_BRANCH) { + if (!parse_ir_branch(&ins, lexer)) { + return false; + } + found_end_statement = true; + } else { + Sb error = {0}; + sb_append_loc(&error, t.loc); + sb_printf(&error, "Error: invalid token "); + sb_append_token_kind(&error, t.kind); + da_append(&error, '\n'); + sb_write(2, error); + unreachable("statement"); + } + da_append(out_block, ins); + ins = (Ir) {0}; + if (!expect_end_statement(lexer)) { + return false; + } + } + return true; +} + +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++; + skip_whitespace(lexer); + if (!expect_token_kind(lexer, ':')) { + return false; + } + if (!expect_end_statement(lexer)) { + return false; + } + if (!parse_ir_basic_block(&block, lexer)) { + return false; + } + da_append(&out_func->body, block); + } + if (!expect_token_kind(lexer, '}')) { + return false; + } + return true; +} + +bool +parse_ir_function(Ir_program *out_prog, Lexer *lexer) +{ + Ir_function func = {.name = lexer->last_tok.sv}; + + skip_whitespace(lexer); + if (!expect_token_kind(lexer, '(')) { + return false; + } + skip_whitespace(lexer); + if (!expect_token_kind(lexer, ')')) { + return false; + } + skip_whitespace(lexer); + if (!expect_token_kind(lexer, T_ARROW)) { + return false; + } + skip_whitespace(lexer); + if (!parse_ir_type(&func.return_type, lexer)) { + return false; + } + skip_whitespace(lexer); + if (!parse_ir_function_body(&func, lexer)) { + return false; + } + da_append(&out_prog->functions, func); + + return true; +} + +bool +parse_ir_top(Ir_program *out_prog, Lexer *lexer) +{ + while (peek_token(lexer).kind != T_EOF) { + Token t = next_token(lexer); + if (t.kind == T_EXTERN) { + if (!parse_ir_extern(out_prog, lexer)) { + return false; + } + } else if (t.kind == T_FUNCTION_SYMBOL) { + if (!parse_ir_function(out_prog, lexer)) { + return false; + } + } else { + Sb error = {0}; + sb_append_loc(&error, t.loc); + sb_printf(&error, "Error: Invalid top level token "); + sb_append_token_kind(&error, t.kind); + da_append(&error, '\n'); + sb_write(2, error); + return false; + } + skip_whitespace(lexer); + } + return true; +} + +bool +parse_ir_cstr(const char *in_cstr, Ir_program *out_prog) +{ + Sv input = sv_from_cstr(in_cstr); + Lexer lexer = {.source = input, .current_loc = {.filename = sv_literal("(cstr)"), .line = 1, .column = 1}}; + skip_whitespace(&lexer); + return parse_ir_top(out_prog, &lexer); +} + +bool +parse_ir_from_file(const char *file_name, Ir_program *out_prog) +{ + Sb input_source = {0}; + if (!sb_read_file(&input_source, file_name)) { + return false; + } + Lexer lexer = {.source = sv_from_sb(input_source), .current_loc = {.filename = sv_from_cstr(file_name), .line = 1, .column = 1}}; + return parse_ir_top(out_prog, &lexer); +} + +void +usage(FILE *output, const char *program_name) +{ + fprintf(output, "Usage: %s <input file>\n", program_name); +} + +int +main(int argc, const char * const *argv) +{ + if (!argc) { + usage(stderr, "parse"); + return 2; + } + const char *prog_name = pop_arg(argc, argv); + if (!argc) { + usage(stderr, prog_name); + return 1; + } + const char *input_file_name = pop_arg(argc, argv); + bool success = true; + size_t i; + Ir_program prog = {0}; + Sb sb = {0}; + if (!parse_ir_from_file(input_file_name, &prog)) { + return 1; + } + for (i = 0; i < prog.functions.count; i++) { + remove_phi_nodes(prog.functions.items[i]); + } + + ir_dump(prog, &sb); + sb_write(1, sb); + sb.count = 0; + success = x86_64_compile_and_emit(prog, &sb); + sb_write(1, sb); + + int out_fd = open("build/parse_output.nasm", O_WRONLY | O_CREAT | O_TRUNC, 0644); + if (out_fd < 0) { + return 1; + } + sb_write(out_fd, sb); + sb.count = 0; + + return success ? 0 : 1; +} diff --git a/src/phi.c b/src/phi.c @@ -0,0 +1,28 @@ +void +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; + for (i = 0; i < fn.body.count; i++) { + block = &fn.body.items[i]; + for (j = 0; j < block->count; j++) { + if (block->items[j].kind != IR_PHI) { + continue; + } + phi = block->items[j]; + for (k = 0; k < phi.phi_list.count; k++) { + 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 }})); + tmp_ir = fn.body.items[label_id].items[last]; + fn.body.items[label_id].items[last] = fn.body.items[label_id].items[last - 1]; + fn.body.items[label_id].items[last - 1] = tmp_ir; + } + memmove(&block->items[j], &block->items[j + 1], sizeof(*block->items) * (block->count - j - 1)); + block->count--; + j--; + } + } +} diff --git a/src/test.c b/src/test.c @@ -0,0 +1,104 @@ +#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 @@ -0,0 +1,1962 @@ +typedef enum { + x86_64_MOV, + x86_64_PUSH, + x86_64_JMP, + x86_64_JZ, + x86_64_JNZ, + x86_64_TEST, + x86_64_CMP, + x86_64_SETL, + x86_64_INC, + x86_64_ADD, + x86_64_XOR, + x86_64_RET, + x86_64_CALL, + + x86_64_PSEUDO_CALL, + x86_64_PSEUDO_PHI, +} x86_64_Opcode; + +typedef enum { + x86_64_NO_OPERAND, + x86_64_I, + x86_64_R, + x86_64_M, + x86_64_RI, + x86_64_RR, + x86_64_RM, + x86_64_MR, + x86_64_MI, + x86_64_RMI, +} x86_64_Operand_encoding; + +typedef enum { + x86_64_RAND_REGISTER, + x86_64_RAND_MEMORY, + x86_64_RAND_IMMEDIATE, + x86_64_RAND_SYMBOL, +} x86_64_Operand_kind; + +typedef struct { + bool physical; + size_t number; +} x86_64_Register; + +typedef enum { + x86_64_IMM_LITERAL, + x86_64_IMM_CODE_LABEL, + x86_64_IMM_DATA_LABEL, +} x86_64_Immediate_kind; + +typedef struct { + x86_64_Immediate_kind kind; + union { + long int i64; + size_t label_id; + }; +} x86_64_Immediate; + +typedef enum { + x86_64_MEM_D, + x86_64_MEM_B, + x86_64_MEM_BS, + x86_64_MEM_BD, + x86_64_MEM_SD, + x86_64_MEM_BSD, +} x86_64_Memory_encoding; + +typedef struct { + x86_64_Memory_encoding encoding; + char reg2_scale; + char offset_bit_width; + x86_64_Immediate offset; + x86_64_Register base, index; +} x86_64_Memory; + +char * +x86_64_immediate_to_cstr(x86_64_Immediate imm) +{ + char *leak_buf = malloc(32); + if (imm.kind == x86_64_IMM_CODE_LABEL) { + snprintf(leak_buf, 32, ".%zu", imm.label_id); + } else if (imm.kind == x86_64_IMM_DATA_LABEL) { + snprintf(leak_buf, 32, "@%zu", imm.label_id); + } else if (imm.kind == x86_64_IMM_LITERAL) { + snprintf(leak_buf, 32, "%li", imm.i64); + } else { + unreachable("immediate kind"); + } + return leak_buf; +} + +typedef struct { + char bit_width; + x86_64_Operand_kind kind; + union { + x86_64_Register reg; + x86_64_Memory mem; + x86_64_Immediate imm; + Sv symbol; + }; +} x86_64_Operand; + +typedef struct { + x86_64_Operand *items; + size_t count; + size_t capacity; +} x86_64_Operand_list; + +typedef struct { + struct { + size_t temp_id; + size_t label_id; + } *items; + size_t count; + size_t capacity; +} x86_64_Phi_list; + +const char *x86_64_registers_8[16] = { + "al", "cl", "dl", "bl", "spl", "bpl", "sil", "dil", + "r8b", "r9b", "r10b", "r11b", "r12b", "r13b", "r14b", "r15b", +}; + +const char *x86_64_registers_16[16] = { + "ax", "cx", "dx", "bx", "sp", "bp", "si", "di", + "r8w", "r9w", "r10w", "r11w", "r12w", "r13w", "r14w", "r15w", +}; + +const char *x86_64_registers_32[16] = { + "eax", "ecx", "edx", "ebx", "esp", "ebp", "esi", "edi", + "r8d", "r9d", "r10d", "r11d", "r12d", "r13d", "r14d", "r15d", +}; + +const char *x86_64_registers_64[16] = { + "rax", "rcx", "rdx", "rbx", "rsp", "rbp", "rsi", "rdi", + "r8", "r9", "r10", "r11", "r12", "r13", "r14", "r15", +}; + +const char *x86_64_registers_err[16] = { + "err_ax", "err_cx", "err_dx", "err_bx", "err_sp", "err_bp", "err_si", "err_di", + "err_8", "err_9", "err_10", "err_11", "err_12", "err_13", "err_14", "err_15", +}; + +int x86_64_registers_ccall[6] = { + 7, 6, 2, 1, 8, 9, +}; + +int +x86_64_bit_width_of_type(Ir_type type) +{ + switch (type) { + case TYPE_I8: + return 8; + case TYPE_I16: + return 16; + case TYPE_I32: + return 32; + case TYPE_PTR: + case TYPE_I64: + return 64; + case TYPE_F32: + case TYPE_F64: + todo("float"); + case TYPE_VOID: + unreachable("type void width"); + case TYPE_UNKNOWN: + return 0; + unreachable("type unknown width"); + default: + unreachable("type"); + } +} + +const char * +x86_64_operand_to_cstr(x86_64_Operand rand) +{ + int len; + char *leak_buf = malloc(32); + const char **reg_names; + if (rand.bit_width == 8) { + reg_names = x86_64_registers_8; + } else if (rand.bit_width == 16) { + reg_names = x86_64_registers_16; + } else if (rand.bit_width == 32) { + reg_names = x86_64_registers_32; + } else if (rand.bit_width == 64) { + reg_names = x86_64_registers_64; + } else { + reg_names = x86_64_registers_err; + } + switch(rand.kind) { + case x86_64_RAND_REGISTER: + if (rand.reg.physical) { + free(leak_buf); + return reg_names[rand.reg.number]; + } else { + snprintf(leak_buf, 32, "r_%zu", rand.reg.number); + } + break; + case x86_64_RAND_MEMORY: + switch (rand.mem.encoding) { + case x86_64_MEM_D: + todo_p("MEM_D"); + case x86_64_MEM_B: + todo_p("MEM_B"); + case x86_64_MEM_BS: + todo_p("MEM_BS"); + case x86_64_MEM_BD: + assert(rand.mem.base.physical); + assert(rand.mem.offset.kind == x86_64_IMM_LITERAL); + if (rand.mem.offset.i64 >= 0) { + len = snprintf(leak_buf, 32, "[%s+%li]", x86_64_registers_64[rand.mem.base.number], rand.mem.offset.i64); + } else { + len = snprintf(leak_buf, 32, "[%s-%li]", x86_64_registers_64[rand.mem.base.number], -rand.mem.offset.i64); + } + assert(len < 32); + break; + case x86_64_MEM_SD: + todo_p("MEM_SD"); + case x86_64_MEM_BSD: + todo_p("MEM_BSD"); + default: + unreachable("memory encoding"); + } + break; + case x86_64_RAND_IMMEDIATE: + free(leak_buf); + return x86_64_immediate_to_cstr(rand.imm); + case x86_64_RAND_SYMBOL: + free(leak_buf); + return sv_to_cstr(rand.symbol); + default: + unreachable("operand kind"); + } + return leak_buf; +} + +typedef struct { + x86_64_Opcode opcode; + x86_64_Operand_encoding encoding; + x86_64_Operand rand1; + union { + struct { + x86_64_Operand rand2; + x86_64_Operand rand3; + }; + struct { + x86_64_Operand ret; + x86_64_Operand_list call_args; + }; + x86_64_Phi_list phi_list; + }; +} x86_64_Instruction; + +typedef struct { + x86_64_Instruction *items; + size_t count; + size_t capacity; +} x86_64_Instruction_list; + +#define SIZE_T_INVALID 0xfffffffffffffffful + +typedef enum { + x86_64_LIVE_NOT_STARTED = 0, + x86_64_LIVE_STARTED, + x86_64_LIVE_COMPLETED, +} x86_64_Liveness_status; + +typedef struct { + int start; + int end; + size_t temp_id; + /* size_t physical; */ + /* size_t spill_offset; */ +} x86_64_Liveness_entry; + +typedef struct { + x86_64_Liveness_entry *items; + size_t count; + size_t capacity; +} x86_64_Liveness_list; + +size_t +x86_64_get_liveness_entry(x86_64_Liveness_list *list, size_t temp_id) +{ + for (size_t i = 0; i < list->count; i++) { + if (list->items[i].temp_id == temp_id) { + return i; + } + } + return SIZE_T_INVALID; +} + +typedef struct { + x86_64_Instruction_list instructions; + x86_64_Liveness_list live; + x86_64_Liveness_status live_status; + struct { + size_t *items; + size_t count; + size_t capacity; + } parents; + struct { + size_t *items; + size_t count; + size_t capacity; + } children; +} x86_64_Basic_block; + +typedef struct { + x86_64_Basic_block *items; + size_t count; + size_t capacity; +} x86_64_Basic_block_list; + +typedef struct { + Sv name; + size_t temporary_count; + x86_64_Basic_block_list blocks; +} x86_64_Function; + +typedef struct { + x86_64_Function *items; + size_t count; + size_t capacity; +} x86_64_Function_list; + +typedef struct { + bool null_terminate; + bool read_only; + void *ptr; + size_t length; + size_t alignment; +} x86_64_Data; + +typedef struct { + x86_64_Data *items; + size_t count; + size_t capacity; +} x86_64_Data_list; + +size_t +x86_64_add_cstr_from_sv(x86_64_Data_list *data_list, Sv sv) +{ + Sb sb = {0}; + sb_append_and_unescape_sv(&sb, sv); + da_append(&sb, '\0'); + da_append(data_list, ((x86_64_Data) { + .read_only = true, + .ptr = (void *) sb.data, + .alignment = 1, + .length = sb.count, + })); + return data_list->count - 1; +} + +typedef struct { + x86_64_Function_list functions; + x86_64_Data_list static_data; + Ir_extern_list externs; +} x86_64_Program; + +void +x86_64_emit_program_header(x86_64_Program prog, Sb *sb) +{ + (void) prog; + sb_printf(sb, "BITS 64\n"); + sb_printf(sb, "SECTION .text\n"); +} + +void +x86_64_emit_program_footer(x86_64_Program prog, Sb *sb) +{ + (void) prog; + (void) sb; +} + +void +x86_64_emit_data_header(x86_64_Program prog, Sb *sb) +{ + (void) prog; + sb_printf(sb, "\n; Static data ;\n"); +} + +void +x86_64_emit_data_footer(x86_64_Program prog, Sb *sb) +{ + (void) prog; + (void) sb; +} + +bool +x86_64_emit_instruction(x86_64_Instruction ins, Sb *sb) +{ + size_t i; + switch (ins.opcode) { + case x86_64_MOV: + switch (ins.encoding) { + case x86_64_RI: + case x86_64_RR: + case x86_64_RM: + case x86_64_MR: + case x86_64_MI: + sb_printf(sb, " mov %s, %s\n", x86_64_operand_to_cstr(ins.rand1), x86_64_operand_to_cstr(ins.rand2)); + break; + + case x86_64_NO_OPERAND: + case x86_64_R: + case x86_64_M: + case x86_64_I: + case x86_64_RMI: + unreachable("invalid encoding"); + default: + unreachable("encoding"); + } + break; + case x86_64_PUSH: + todo("push"); + case x86_64_JMP: + switch (ins.encoding) { + case x86_64_I: + sb_printf(sb, " jmp %s\n", x86_64_operand_to_cstr(ins.rand1)); + break; + case x86_64_NO_OPERAND: + case x86_64_RI: + case x86_64_RR: + case x86_64_RM: + case x86_64_MR: + case x86_64_MI: + case x86_64_R: + case x86_64_M: + case x86_64_RMI: + unreachable("invalid encoding"); + default: + unreachable("encoding"); + } + break; + case x86_64_JZ: + sb_printf(sb, " jz %s\n", x86_64_operand_to_cstr(ins.rand1)); + break; + case x86_64_JNZ: + sb_printf(sb, " jnz %s\n", x86_64_operand_to_cstr(ins.rand1)); + break; + case x86_64_TEST: + sb_printf(sb, " test %s, %s\n", x86_64_operand_to_cstr(ins.rand1), x86_64_operand_to_cstr(ins.rand2)); + break; + case x86_64_CMP: + sb_printf(sb, " cmp %s, %s\n", x86_64_operand_to_cstr(ins.rand1), x86_64_operand_to_cstr(ins.rand2)); + break; + case x86_64_SETL: + sb_printf(sb, " setl %s\n", x86_64_operand_to_cstr(ins.rand1)); + break; + case x86_64_INC: + sb_printf(sb, " inc %s\n", x86_64_operand_to_cstr(ins.rand1)); + break; + case x86_64_ADD: + sb_printf(sb, " add %s, %s\n", x86_64_operand_to_cstr(ins.rand1), x86_64_operand_to_cstr(ins.rand2)); + break; + case x86_64_XOR: + sb_printf(sb, " xor %s, %s\n", x86_64_operand_to_cstr(ins.rand1), x86_64_operand_to_cstr(ins.rand2)); + break; + case x86_64_RET: + sb_printf(sb, " jmp .ret\n"); + break; + case x86_64_CALL: + sb_printf(sb, " call %.*s\n", (int) ins.rand1.symbol.count, ins.rand1.symbol.data); + break; + case x86_64_PSEUDO_CALL: + assert(ins.rand1.kind == x86_64_RAND_SYMBOL); + sb_printf(sb, " call %.*s (", (int) ins.rand1.symbol.count, ins.rand1.symbol.data); + for (i = 0; i < ins.call_args.count; i++) { + if (i) { + sb_printf(sb, ", "); + } + sb_printf(sb, "%s", x86_64_operand_to_cstr(ins.call_args.items[i])); + } + sb_printf(sb, ") -> %s\n", x86_64_operand_to_cstr(ins.ret)); + break; + + case x86_64_PSEUDO_PHI: + todo("emit phi"); + default: + unreachable("x86_64_opcode"); + } + return true; +} +bool +x86_64_compile_instruction(Ir ir, x86_64_Instruction_list *list, x86_64_Data_list *data_list) +{ + switch (ir.kind) { + case IR_LOAD: + todo("load"); + break; + case IR_STORE: + todo("store"); + break; + case IR_ASSIGN: + switch (ir.assign.kind) { + case ARG_NONE: + unreachable("assign-none"); + case ARG_INT_LITERAL: + /* 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, + .rand1 = { + .bit_width = 32, + .kind = x86_64_RAND_REGISTER, + .reg = { + .physical = false, + .number = ir.result.temp_id, + }, + }, + .rand2 = { + .bit_width = 32, + .kind = x86_64_RAND_IMMEDIATE, + .imm = { + .kind = x86_64_IMM_LITERAL, + .i64 = (unsigned int) ir.assign.i64, + }, + }, + })); + break; + case ARG_CSTRING_LITERAL: + da_append(list, ((x86_64_Instruction) { + .opcode = x86_64_MOV, + .encoding = x86_64_RI, + .rand1 = { + .bit_width = 64, + .kind = x86_64_RAND_REGISTER, + .reg = { + .physical = false, + .number = ir.result.temp_id, + }, + }, + .rand2 = { + .bit_width = 64, + .kind = x86_64_RAND_IMMEDIATE, + .imm = { + .kind = x86_64_IMM_DATA_LABEL, + .label_id = x86_64_add_cstr_from_sv(data_list, ir.assign.sv), + }, + }, + })); + break; + case ARG_TEMP_STORAGE: + da_append(list, ((x86_64_Instruction) { + .opcode = x86_64_MOV, + .encoding = x86_64_RR, + .rand1 = { + .bit_width = 32, + .kind = x86_64_RAND_REGISTER, + .reg = { + .physical = false, + .number = ir.result.temp_id, + }, + }, + .rand2 = { + .bit_width = 32, + .kind = x86_64_RAND_REGISTER, + .reg = { + .physical = false, + .number = ir.assign.temp_id, + }, + }, + })); + break; + case ARG_ADDRESS: + todo("assign-address"); + case ARG_REGISTER: + unreachable("assign-register"); + default: + unreachable("assign"); + } + /* return false; */ + break; + case IR_BINOP: + switch (ir.binop.op) { + case OP_ADD: + if (ir.binop.left.kind == ARG_TEMP_STORAGE && ir.binop.right.kind == ARG_INT_LITERAL) { + if (ir.binop.op_type != TYPE_I32) { + todo("add types"); + } + /* sb_printf(sb, " cmp tmp_%zu, %li\n", ir.binop.left.temp_id, ir.binop.right.i64); */ + da_append(list, ((x86_64_Instruction) { + .opcode = x86_64_MOV, + .encoding = x86_64_RR, + .rand1 = { + .bit_width = 32, + .kind = x86_64_RAND_REGISTER, + .reg = { + .physical = false, + .number = ir.result.temp_id, + }, + }, + .rand2 = { + .bit_width = 32, + .kind = x86_64_RAND_REGISTER, + .reg = { + .physical = false, + .number = ir.binop.left.temp_id, + }, + }, + })); + da_append(list, ((x86_64_Instruction) { + .opcode = x86_64_ADD, + .encoding = x86_64_RI, + .rand1 = { + .bit_width = 32, + .kind = x86_64_RAND_REGISTER, + .reg = { + .physical = false, + .number = ir.result.temp_id, + }, + }, + .rand2 = { + .bit_width = 32, + .kind = x86_64_RAND_IMMEDIATE, + .imm = { + .kind = x86_64_IMM_LITERAL, + .i64 = ir.binop.right.i64, + }, + }, + })); + } else { + todo("binop +"); + } + break; + case OP_SUB: + todo("binop -"); + case OP_MUL: + todo("binop *"); + case OP_DIV: + todo("binop /"); + case OP_LT: + if (ir.binop.left.kind == ARG_TEMP_STORAGE && ir.binop.right.kind == ARG_INT_LITERAL) { + if (ir.binop.op_type != TYPE_I32) { + todo("lt types"); + } + /* sb_printf(sb, " cmp tmp_%zu, %li\n", ir.binop.left.temp_id, ir.binop.right.i64); */ + da_append(list, ((x86_64_Instruction) { + .opcode = x86_64_CMP, + .encoding = x86_64_RI, + .rand1 = { + .bit_width = 32, + .kind = x86_64_RAND_REGISTER, + .reg = { + .physical = false, + .number = ir.binop.left.temp_id, + }, + }, + .rand2 = { + .bit_width = 32, + .kind = x86_64_RAND_IMMEDIATE, + .imm = { + .kind = x86_64_IMM_LITERAL, + .i64 = ir.binop.right.i64, + }, + }, + })); + } else { + todo("binop <"); + } + /* sb_printf(sb, " setl tmp_%zu\n", ir.result.temp_id); */ + da_append(list, ((x86_64_Instruction) { + .opcode = x86_64_SETL, + .encoding = x86_64_R, + .rand1 = { + .bit_width = 8, + .kind = x86_64_RAND_REGISTER, + .reg = { + .physical = false, + .number = ir.result.temp_id, + }, + }, + })); + break; + case OP_GT: + todo("binop >"); + case OP_EQ: + todo("binop =="); + case OP_LEQ: + todo("binop <="); + case OP_GEQ: + todo("binop >="); + default: + unreachable("binop"); + } + break; + case IR_CALL: + if (ir.call.args.count > 6) { + todo("call > 6 args"); + } + /* + for (size_t i = 0; i < ir.call.args.count; i++) { + x86_64_Operand arg = {0}; + switch (ir.call.args.items[i].kind) { + case ARG_INT_LITERAL: + arg.kind = x86_64_RAND_IMMEDIATE; + arg.imm = (x86_64_Immediate) { + .kind = x86_64_IMM_LITERAL, + .i64 = ir.call.args.items[i].i64, + }; + break; + case ARG_CSTRING_LITERAL: + arg.kind = x86_64_RAND_IMMEDIATE; + arg.imm = (x86_64_Immediate) { + .kind = x86_64_IMM_DATA_LABEL, + .label_id = x86_64_add_cstr(data_list, ir.call.args.items[i].cstr), + }; + break; + case ARG_TEMP_STORAGE: + arg.kind = x86_64_RAND_REGISTER; + arg.reg = (x86_64_Register) { + .physical = false, + .number = ir.call.args.items[i].temp_id, + }; + break; + case ARG_ADDRESS: + case ARG_REGISTER: + case ARG_NONE: + default: + unreachable("args operand"); + } + da_append(list, ((x86_64_Instruction) { + .opcode = x86_64_MOV, + .encoding = x86_64_RR, + .rand1 = { + .kind = x86_64_RAND_REGISTER, + .reg = { + .physical = true, + .number = x86_64_registers_ccall[i], + }, + }, + .rand2 = arg, + })); + } + */ + da_append(list, ((x86_64_Instruction) { + .opcode = x86_64_PSEUDO_CALL, + .encoding = x86_64_I, + .rand1 = { + .kind = x86_64_RAND_SYMBOL, + .symbol = ir.call.name, + }, + .ret = { + .kind = x86_64_RAND_REGISTER, + .bit_width = 32, + .reg = { + .physical = false, + .number = ir.result.temp_id, + }, + }, + })); + for (size_t i = 0; i < ir.call.args.count; i++) { + x86_64_Operand arg = {0}; + switch (ir.call.args.items[i].kind) { + case ARG_INT_LITERAL: + arg.kind = x86_64_RAND_IMMEDIATE; + arg.imm = (x86_64_Immediate) { + .kind = x86_64_IMM_LITERAL, + .i64 = ir.call.args.items[i].i64, + }; + break; + case ARG_CSTRING_LITERAL: + arg.kind = x86_64_RAND_IMMEDIATE; + arg.bit_width = x86_64_bit_width_of_type(ir.call.args.items[i].type); + arg.imm = (x86_64_Immediate) { + .kind = x86_64_IMM_DATA_LABEL, + .label_id = x86_64_add_cstr_from_sv(data_list, ir.call.args.items[i].sv), + }; + break; + case ARG_TEMP_STORAGE: + arg.kind = x86_64_RAND_REGISTER; + arg.bit_width = x86_64_bit_width_of_type(ir.call.args.items[i].type); + arg.reg = (x86_64_Register) { + .physical = false, + .number = ir.call.args.items[i].temp_id, + }; + break; + case ARG_ADDRESS: + case ARG_REGISTER: + case ARG_NONE: + default: + unreachable("args operand"); + } + da_append(&list->items[list->count - 1].call_args, arg); + } + break; + case IR_RETURN: + if (ir.ret.kind == ARG_TEMP_STORAGE) { + da_append(list, ((x86_64_Instruction) { + .opcode = x86_64_MOV, + .encoding = x86_64_RR, + .rand1 = { + .bit_width = 32, + .kind = x86_64_RAND_REGISTER, + .reg = { + .physical = true, + .number = 0, + }, + }, + .rand2 = { + .bit_width = 32, + .kind = x86_64_RAND_REGISTER, + .reg = { + .physical = false, + .number = ir.ret.temp_id, + }, + }, + })); + da_append(list, ((x86_64_Instruction) { + .opcode = x86_64_RET, + .encoding = x86_64_NO_OPERAND, + })); + } else { + todo("return"); + } + break; + /* case IR_LABEL: */ + case IR_JUMP: + da_append(list, ((x86_64_Instruction) { + .opcode = x86_64_JMP, + .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, + }, + }, + })); + break; + case IR_BRANCH: + if (ir.branch.cond.kind == ARG_TEMP_STORAGE) { + da_append(list, ((x86_64_Instruction) { + .opcode = x86_64_TEST, + .encoding = x86_64_RR, + .rand1 = { + .bit_width = 8, + .kind = x86_64_RAND_REGISTER, + .reg = { + .physical = false, + .number = ir.branch.cond.temp_id, + }, + }, + .rand2 = { + .bit_width = 8, + .kind = x86_64_RAND_REGISTER, + .reg = { + .physical = false, + .number = ir.branch.cond.temp_id, + }, + }, + })); + da_append(list, ((x86_64_Instruction) { + .opcode = x86_64_JZ, + .encoding = x86_64_I, + .rand1 = { + .bit_width = 64, + .kind = x86_64_RAND_IMMEDIATE, + .imm = { + .kind = x86_64_IMM_CODE_LABEL, + .label_id = ir.branch.false_label_id, + }, + }, + })); + da_append(list, ((x86_64_Instruction) { + .opcode = x86_64_JMP, + .encoding = x86_64_I, + .rand1 = { + .bit_width = 64, + .kind = x86_64_RAND_IMMEDIATE, + .imm = { + .kind = x86_64_IMM_CODE_LABEL, + .label_id = ir.branch.true_label_id, + }, + }, + })); + /* sb_printf(sb, " mov rax, tmp_%zu\n", ir.branch.cond.temp_id); */ + /* sb_printf(sb, " test rax, rax\n"); */ + /* sb_printf(sb, " jz .%zu\n", ir.branch.true_label_id); */ + /* sb_printf(sb, " jmp .%zu\n", ir.branch.false_label_id); */ + } else { + todo("branch"); + } + break; + case IR_PHI: + unreachable("phi nodes should've been purged"); + default: + unreachable("ir_kind"); + } + return true; +} + +bool +x86_64_compile_basic_block(Ir_block block, x86_64_Basic_block *out_block, x86_64_Data_list *data_list) +{ + bool success = true; + size_t i; + for (i = 0; i < block.count; i++) { + if (!x86_64_compile_instruction(block.items[i], &out_block->instructions, data_list)) { + success = false; + break; + } + } + return success; +} + +bool +x86_64_emit_basic_block(x86_64_Basic_block block, Sb *sb) +{ + bool success = true; + size_t i; + for (i = 0; i < block.instructions.count; i++) { + if (!x86_64_emit_instruction(block.instructions.items[i], sb)) { + success = false; + break; + } + } + return success; +} + +bool +x86_64_compile_function(Ir_function func, x86_64_Function *out_func, x86_64_Data_list *data_list) +{ + bool success = true; + size_t i; + x86_64_Basic_block block; + for (i = 0; i < func.body.count; i++) { + block = (x86_64_Basic_block) {0}; + if (!x86_64_compile_basic_block(func.body.items[i], &block, data_list)) { + da_append(&out_func->blocks, block); + success = false; + break; + } + da_append(&out_func->blocks, block); + } + return success; +} + +bool +x86_64_emit_function(x86_64_Function fn, Sb *sb) +{ + bool success = true; + size_t i; + sb_printf(sb, "\nGLOBAL %.*s\n", (int) fn.name.count, fn.name.items); + sb_printf(sb, "%.*s:\n", (int) fn.name.count, fn.name.items); + sb_printf(sb, " push rbp\n"); + sb_printf(sb, " mov rbp, rsp\n"); + sb_printf(sb, " sub rsp, %zu\n", ((fn.temporary_count * 8) + 0xF) & ~0xF); + + Sb body = {0}; + for (i = 0; i < fn.blocks.count; i++) { + sb_printf(&body, " .%zu:\n", i); + if (!x86_64_emit_basic_block(fn.blocks.items[i], &body)) { + success = false; + break; + } + } + sb_append_sv(sb, sv_from_sb(body)); + sb_printf(sb, " .ret:\n"); + sb_printf(sb, " mov rsp, rbp\n"); + sb_printf(sb, " pop rbp\n"); + sb_printf(sb, " ret\n"); + + free(body.items); + + return success; +} + +bool +x86_64_emit_data(x86_64_Data data, Sb *sb, size_t label_id) +{ + size_t i; + int prefix_len; + if (data.alignment > 1) { + sb_printf(sb, "ALIGN %zu\n", data.alignment); + } + if (data.ptr) { + sb_printf(sb, "SECTION .rodata\n"); + prefix_len = sb_printf(sb, "@%zu: db ", label_id); + for (i = 0; i < data.length; i++) { + if (i) { + da_append(sb, ','); + if (!(i & 0x0f)) { + sb_printf(sb, "\n%*s", prefix_len, ""); + } + } + sb_printf(sb, "0x%02x", ((char *) data.ptr)[i]); + } + if (data.null_terminate) { + sb_printf(sb, ",0x00"); + } + da_append(sb, '\n'); + } else { + sb_printf(sb, "SECTION .bss\n"); + sb_printf(sb, "@%zu: resb %zu", label_id, data.length); + } + return true; +} + +bool +x86_64_emit_extern(Ir_extern ext, Sb *sb) +{ + sb_printf(sb, "EXTERN %.*s\n", (int) ext.symbol.count, ext.symbol.data); + return true; +} + +bool +x86_64_emit_program(x86_64_Program prog, Sb *sb) +{ + bool success = true; + size_t i; + x86_64_emit_program_header(prog, sb); + for (i = 0; i < prog.externs.count; i++) { + if (!x86_64_emit_extern(prog.externs.items[i], sb)) { + success = false; + break; + } + } + for (i = 0; i < prog.functions.count; i++) { + if (!x86_64_emit_function(prog.functions.items[i], sb)) { + success = false; + break; + } + } + x86_64_emit_program_footer(prog, sb); + x86_64_emit_data_header(prog, sb); + for (i = 0; i < prog.static_data.count; i++) { + if (!x86_64_emit_data(prog.static_data.items[i], sb, i)) { + success = false; + break; + } + } + x86_64_emit_data_footer(prog, sb); + return success; +} + +bool +x86_64_calculate_internal_liveness(x86_64_Basic_block *block) +{ + size_t i, j, entry_index; + x86_64_Instruction ins; + x86_64_Liveness_entry *entry; + + size_t block_icount = block->instructions.count; + for (i = block_icount - 1; i != SIZE_T_INVALID; i--) { + ins = block->instructions.items[i]; + switch (ins.opcode) { + case x86_64_CALL: + unreachable("live call"); + case x86_64_PSEUDO_PHI: + todo("live phi"); + case x86_64_MOV: + case x86_64_SETL: + switch (ins.encoding) { + case x86_64_R: + case x86_64_RI: + if (ins.rand1.reg.physical) { + /* fprintf(stderr, "INFO: Ignoring physical register in liveness check\n"); */ + } else { + if ((entry_index = x86_64_get_liveness_entry(&block->live, ins.rand1.reg.number)) == SIZE_T_INVALID) { + da_append(&block->live, ((x86_64_Liveness_entry) { + .start = i, + .end = i, + .temp_id = ins.rand1.reg.number, + })); + } else { + assert(block->live.items[entry_index].start == -1); + block->live.items[entry_index].start = i; + } + } + break; + case x86_64_M: + todo("modifying M"); + + case x86_64_RR: + if (ins.rand1.reg.physical) { + /* fprintf(stderr, "INFO: Ignoring physical register in liveness check\n"); */ + } else { + if ((entry_index = x86_64_get_liveness_entry(&block->live, ins.rand1.reg.number)) == SIZE_T_INVALID) { + da_append(&block->live, ((x86_64_Liveness_entry) { + .start = i, + .end = i, + .temp_id = ins.rand1.reg.number, + })); + } else { + assert(block->live.items[entry_index].start == -1); + block->live.items[entry_index].start = i; + } + } + if (ins.rand2.reg.physical) { + /* fprintf(stderr, "INFO: Ignoring physical register in liveness check\n"); */ + } else { + if ((entry_index = x86_64_get_liveness_entry(&block->live, ins.rand2.reg.number)) == SIZE_T_INVALID) { + da_append(&block->live, ((x86_64_Liveness_entry) { + .start = -1, + .end = i, + .temp_id = ins.rand2.reg.number, + })); + } else { + entry = &block->live.items[entry_index]; + if (entry->start == entry->end) { + entry->end = i; + } + if (entry->start >= 0) { + entry->start = -(entry->start + 2); + } + /* DO NOTHING? */ + /* fprintf(stderr, "%%%zu already defined as (%i -> %i)\n", ins.rand2.reg.number, block->live.items[entry_index].start, block->live.items[entry_index].end); */ + } + } + break; + case x86_64_RM: + todo("modifying RM"); + case x86_64_MR: + todo("modifying MR"); + case x86_64_MI: + todo("modifying RMI"); + case x86_64_RMI: + todo("modifying RMI"); + + case x86_64_I: + break; + case x86_64_NO_OPERAND: + default: + unreachable("encoding"); + } + break; + + /* Modifies their first operand, but not a valid start, since it also reads from it. Must be preceeded by mov or similar */ + case x86_64_INC: + case x86_64_ADD: + case x86_64_XOR: + /* Doesn't modify their operands */ + case x86_64_PUSH: + case x86_64_TEST: + case x86_64_CMP: + switch (ins.encoding) { + case x86_64_RI: + case x86_64_R: + if (ins.rand1.reg.physical) { + /* fprintf(stderr, "INFO: Ignoring physical register in liveness check\n"); */ + break; + } + if ((entry_index = x86_64_get_liveness_entry(&block->live, ins.rand1.reg.number)) == SIZE_T_INVALID) { + da_append(&block->live, ((x86_64_Liveness_entry) { + .start = -1, + .end = i, + .temp_id = ins.rand1.reg.number, + })); + } else { + /* DO NOTHING? */ + } + break; + case x86_64_M: + todo("non-modifying M"); + case x86_64_RR: + if (ins.rand1.reg.physical) { + /* fprintf(stderr, "INFO: Ignoring physical register in liveness check\n"); */ + } else { + if ((entry_index = x86_64_get_liveness_entry(&block->live, ins.rand1.reg.number)) == SIZE_T_INVALID) { + da_append(&block->live, ((x86_64_Liveness_entry) { + .start = -1, + .end = i, + .temp_id = ins.rand1.reg.number, + })); + } else { + /* DO NOTHING? */ + } + } + if (ins.rand2.reg.physical) { + /* fprintf(stderr, "INFO: Ignoring physical register in liveness check\n"); */ + } else { + if ((entry_index = x86_64_get_liveness_entry(&block->live, ins.rand2.reg.number)) == SIZE_T_INVALID) { + da_append(&block->live, ((x86_64_Liveness_entry) { + .start = -1, + .end = i, + .temp_id = ins.rand2.reg.number, + })); + } else { + /* DO NOTHING? */ + } + } + break; + case x86_64_RM: + todo("non-modifying RM"); + case x86_64_MR: + todo("non-modifying MR"); + case x86_64_MI: + todo("non-modifying MI"); + case x86_64_RMI: + todo("non-modifying RMM"); + + case x86_64_I: + break; + case x86_64_NO_OPERAND: + default: + unreachable("encoding"); + } + break; + + case x86_64_PSEUDO_CALL: + if (ins.encoding == x86_64_R) { + todo("indirect call"); + } + if ((entry_index = x86_64_get_liveness_entry(&block->live, ins.ret.reg.number)) == SIZE_T_INVALID) { + da_append(&block->live, ((x86_64_Liveness_entry) { + .start = i, + .end = i, + .temp_id = ins.ret.reg.number, + })); + } else { + assert(block->live.items[entry_index].start == -1); + block->live.items[entry_index].start = i; + } + if (ins.call_args.count) { + for (j = 0; j < ins.call_args.count; j++) { + x86_64_Operand arg = ins.call_args.items[j]; + if (arg.kind != x86_64_RAND_REGISTER) { + continue; + } + if (arg.reg.physical) { + /* fprintf(stderr, "INFO: Ignoring physical register in liveness check\n"); */ + break; + } + if ((entry_index = x86_64_get_liveness_entry(&block->live, arg.reg.number)) == SIZE_T_INVALID) { + da_append(&block->live, ((x86_64_Liveness_entry) { + .start = -1, + .end = i, + .temp_id = arg.reg.number, + })); + } else { + /* DO NOTHING? */ + } + } + } + break; + + /* Can only use static labels */ + case x86_64_JZ: + case x86_64_JNZ: + case x86_64_JMP: + assert(ins.encoding == x86_64_I); + break; + + /* No operands */ + case x86_64_RET: + assert(ins.encoding == x86_64_NO_OPERAND); + break; + default: + unreachable("instruction"); + } + } + return true; +} + +bool +x86_64_calculate_external_liveness(x86_64_Basic_block *block, x86_64_Basic_block_list *block_list) +{ + if (block->live_status == x86_64_LIVE_COMPLETED) { + return true; + } + block->live_status = x86_64_LIVE_STARTED; + size_t i, j, entry_index; + x86_64_Basic_block *child_block; + x86_64_Liveness_entry *entry, *child_entry; + for (i = 0; i < block->children.count; i++) { + if (block->children.items[i] == block_list->count) { + continue; + } + child_block = &block_list->items[block->children.items[i]]; + if (child_block->live_status == x86_64_LIVE_NOT_STARTED) { + if (!x86_64_calculate_external_liveness(child_block, block_list)) { + return false; + } + } + for (j = 0; j < child_block->live.count; j++) { + child_entry = &child_block->live.items[j]; + if (child_entry->start >= 0) { + continue; + } + if ((entry_index = x86_64_get_liveness_entry(&block->live, child_entry->temp_id)) == SIZE_T_INVALID) { + da_append(&block->live, ((x86_64_Liveness_entry) { + .start = -1, + .end = -1, + .temp_id = child_entry->temp_id, + })); + } else { + entry = &block->live.items[entry_index]; + if (entry->end >= 0) { + entry->end = -(entry->end + 2); + } + } + } + } + return true; +} + +bool +x86_64_calculate_liveness(x86_64_Function *fn) +{ + size_t i, j, max_temp = SIZE_T_INVALID; + x86_64_Basic_block *block; + /* fprintf(stderr, "--- Internal Lifetimes ---\n"); */ + for (i = 0; i < fn->blocks.count; i++) { + block = &fn->blocks.items[i]; + if (!x86_64_calculate_internal_liveness(block)) { + return false; + } + /* fprintf(stderr, ".%zu {\n", i); */ + for (j = 0; j < block->live.count; j++) { + /* fprintf(stderr, " %%%zu: %i -> %i\n", block->live.items[j].temp_id, block->live.items[j].start, block->live.items[j].end); */ + if (max_temp < block->live.items[j].temp_id || max_temp == SIZE_T_INVALID) { + max_temp = block->live.items[j].temp_id; + } + } + /* fprintf(stderr, "}\n"); */ + } + assert(max_temp != SIZE_T_INVALID); + fn->temporary_count = max_temp + 1; + + /* fprintf(stderr, "\n--- Total Lifetimes ---\n"); */ + for (i = 0; i < fn->blocks.count; i++) { + block = &fn->blocks.items[i]; + if (!x86_64_calculate_external_liveness(block, &fn->blocks)) { + return false; + } + block->live_status = x86_64_LIVE_COMPLETED; + + /* fprintf(stderr, ".%zu {\n", i); */ + /* for (j = 0; j < block->live.count; j++) { */ + /* fprintf(stderr, " %%%zu: %i -> %i\n", block->live.items[j].temp_id, block->live.items[j].start, block->live.items[j].end); */ + /* } */ + /* fprintf(stderr, "}\n"); */ + } + return true; +} + +bool +x86_64_calculate_call_graph(x86_64_Function *fn) +{ + size_t i, j, k, child; + x86_64_Basic_block *block; + x86_64_Instruction *ins; + for (i = 0; i < fn->blocks.count; i++) { + block = &fn->blocks.items[i]; + for (j = 0; j < block->instructions.count; j++) { + ins = &block->instructions.items[j]; + if (ins->opcode == x86_64_RET) { + da_append(&block->children, fn->blocks.count); + } else if (ins->opcode == x86_64_JMP || + ins->opcode == x86_64_JZ || + ins->opcode == x86_64_JNZ) { + assert(ins->encoding == x86_64_I); + assert(ins->rand1.imm.kind == x86_64_IMM_CODE_LABEL); + child = ins->rand1.imm.label_id; + for (k = 0; k < block->children.count; k++) { + if (block->children.items[k] == child) { + break; + } + } + if (k == block->children.count) { + da_append(&block->children, child); + da_append(&fn->blocks.items[child].parents, i); + } + } + } + } + return true; +} + +void +x86_64_emit_call_graph_dotfmt(x86_64_Function fn) +{ + size_t i, j; + FILE *f = fopen("build/callgraph.gv", "w"); + if (!f) { + perror("x86_64_emit_call_graph_dotfmt"); + return; + } + fprintf(f, "digraph {\n"); + fprintf(f, " .%zu [name=ret]\n", fn.blocks.count); + for (i = 0; i < fn.blocks.count; i++) { + for (j = 0; j < fn.blocks.items[i].children.count; j++) { + fprintf(f, " .%zu -> .%zu\n", i, fn.blocks.items[i].children.items[j]); + } + } + fprintf(f, "}\n"); +} + +bool +x86_64_expand_pseudo_instructions(x86_64_Function *fn) +{ + size_t i, j, k, l; + x86_64_Basic_block *block; + x86_64_Instruction_list new_instruction_list = {0}; + x86_64_Instruction *ins; + x86_64_Operand *arg; + x86_64_Operand_list saved = {0}; + for (i = 0; i < fn->blocks.count; i++) { + block = &fn->blocks.items[i]; + for (j = 0; j< block->instructions.count; j++) { + ins = &block->instructions.items[j]; + if (ins->opcode != x86_64_PSEUDO_CALL) { + da_append(&new_instruction_list, *ins); + continue; + } + saved.count = 0; + for (k = 0; k < ins->call_args.count; k++) { + arg = &ins->call_args.items[k]; + switch (arg->kind) { + case x86_64_RAND_REGISTER: + assert(!arg->reg.physical); + for (l = 0; l < block->live.count; l++) { + if (block->live.items[l].temp_id == arg->reg.number) { + break; + } + } + assert(l < block->live.count); + if (block->live.items[l].end == (long) j || (-block->live.items[l].end - 2) == (long) j) { + continue; + } + da_append(&saved, *arg); + da_append(&new_instruction_list, ((x86_64_Instruction) { + .opcode = x86_64_MOV, + .encoding = x86_64_MR, + .rand1 = { + .kind = x86_64_RAND_MEMORY, + .mem = { + .encoding = x86_64_MEM_BD, + .base = { + .physical = true, + .number = 5, + }, + .offset_bit_width = 8, + .offset = { + .kind = x86_64_IMM_LITERAL, + .i64 = -(saved.count << 3), + }, + }, + }, + .rand2 = *arg, + })); + break; + case x86_64_RAND_MEMORY: + todo("memory"); + case x86_64_RAND_IMMEDIATE: + case x86_64_RAND_SYMBOL: + continue; + default: + unreachable("operand kind"); + } + } + for (k = 0; k < ins->call_args.count; k++) { + arg = &ins->call_args.items[k]; + switch (arg->kind) { + case x86_64_RAND_REGISTER: + assert(!arg->reg.physical); + da_append(&new_instruction_list, ((x86_64_Instruction) { + .opcode = x86_64_MOV, + .encoding = x86_64_RR, + .rand1 = { + .kind = x86_64_RAND_REGISTER, + .bit_width = arg->bit_width, + .reg = { + .physical = true, + .number = x86_64_registers_ccall[k], + }, + }, + .rand2 = *arg, + })); + break; + case x86_64_RAND_MEMORY: + todo("memory"); + case x86_64_RAND_IMMEDIATE: + da_append(&new_instruction_list, ((x86_64_Instruction) { + .opcode = x86_64_MOV, + .encoding = x86_64_RI, + .rand1 = { + .kind = x86_64_RAND_REGISTER, + .bit_width = arg->bit_width, + .reg = { + .physical = true, + .number = x86_64_registers_ccall[k], + }, + }, + .rand2 = *arg, + })); + break; + case x86_64_RAND_SYMBOL: + todo("symbol"); + default: + unreachable("operand kind"); + + } + } + da_append(&new_instruction_list, ((x86_64_Instruction) { + .opcode = x86_64_MOV, + .encoding = x86_64_RI, + .rand1 = { + .kind = x86_64_RAND_REGISTER, + .bit_width = 64, + .reg = { + .physical = true, + .number = 0, + }, + }, + .rand2 = { + .kind = x86_64_RAND_IMMEDIATE, + .imm = { + .kind = x86_64_IMM_LITERAL, + .i64 = 0, + }, + }, + })); + da_append(&new_instruction_list, ((x86_64_Instruction) { + .opcode = x86_64_CALL, + .encoding = x86_64_I, + .rand1 = ins->rand1, + })); + assert(ins->ret.kind == x86_64_RAND_REGISTER); + da_append(&new_instruction_list, ((x86_64_Instruction) { + .opcode = x86_64_MOV, + .encoding = x86_64_RR, + .rand1 = ins->ret, + .rand2 = { + .kind = x86_64_RAND_REGISTER, + .bit_width = ins->ret.bit_width, + .reg = { + .physical = true, + .number = 0, + }, + }, + })); + while (saved.count) { + saved.count--; + da_append(&new_instruction_list, ((x86_64_Instruction) { + .opcode = x86_64_MOV, + .encoding = x86_64_RM, + .rand1 = saved.items[saved.count], + .rand2 = { + .kind = x86_64_RAND_MEMORY, + .mem = { + .encoding = x86_64_MEM_BD, + .base = { + .physical = true, + .number = 5, + }, + .offset_bit_width = 8, + .offset = { + .kind = x86_64_IMM_LITERAL, + .i64 = -((saved.count+1) << 3), + }, + }, + }, + })); + } + } + free(block->instructions.items); + block->instructions = new_instruction_list; + memset(&new_instruction_list, 0, sizeof(new_instruction_list)); + } + free(saved.items); + return true; +} + +typedef struct { + size_t *items; + size_t count; + size_t capacity; +} x86_64_Interference_list; + +void +x86_64_emit_temp_interference_graph_dotfmt(x86_64_Interference_list *graph, size_t entries) +{ + size_t i, j; + FILE *f = fopen("build/interferencegraph.gv", "w"); + if (!f) { + perror("x86_64_emit_temp_interference_graph_dotfmt"); + return; + } + fprintf(f, "digraph {\n"); + for (i = 0; i < entries; i++) { + for (j = 0; j < graph[i].count; j++) { + fprintf(f, " r_%zu -> r_%zu\n", i, graph[i].items[j]); + } + } + fprintf(f, "}\n"); +} + +/* + "rax", "rcx", "rdx", "rbx", "rsp", "rbp", "rsi", "rdi", + "r8", "r9", "r10", "r11", "r12", "r13", "r14", "r15", +*/ + +int x86_64_registers_usable[] = { + 0, 1, 2, 6, 7, 8, 9, 3, 10, 11, 12, 13, 14, 15, +}; + +int x86_64_registers_usable_rgb[] = { + 0xff0000, 0xffff00, 0xff00ff, 0x00ffff, 0x336600, 0x993300, 0xcccc99, + 0x66cc00, 0x669999, 0x33cc99, 0x0066cc, 0x9966cc, 0x330066, 0x990066, +}; + +size_t x86_64_registers_usable_count = sizeof(x86_64_registers_usable) / sizeof(*x86_64_registers_usable); + +void +x86_64_emit_temp_colored_graph_dotfmt(x86_64_Interference_list *graph, int *colors, size_t entries) +{ + size_t i, j; + FILE *f = fopen("build/colorgraph.gv", "w"); + if (!f) { + perror("x86_64_emit_temp_colored_graph_dotfmt"); + return; + } + fprintf(f, "graph {\n"); + for (i = 0; i < entries; i++) { + fprintf(f, " r_%zu [fillcolor=\"#%06x\", style=filled];\n", i, x86_64_registers_usable_rgb[colors[i]]); + for (j = 0; j < graph[i].count; j++) { + if (i < graph[i].items[j]) { + fprintf(f, " r_%zu -- r_%zu;\n", i, graph[i].items[j]); + } + } + } + fprintf(f, "}\n"); +} + +bool +x86_64_assign_registers(x86_64_Function *fn) +{ + size_t i, j, k, l; + int s1, s2, e1, e2; + x86_64_Basic_block *block; + x86_64_Liveness_entry *live, *live_cmp; + size_t temp_count = fn->temporary_count; + x86_64_Interference_list *graph = calloc(temp_count, sizeof(*graph)); + int *mappings = malloc(sizeof(*mappings) * temp_count); + for (i = 0; i < temp_count; i++) { + mappings[i] = -1; + } + for (i = 0; i < fn->blocks.count; i++) { + block = &fn->blocks.items[i]; + for (j = 0; j < block->live.count; j++) { + live = &block->live.items[j]; + s1 = live->start; + e1 = live->end; + for (k = 0; k < block->live.count; k++) { + if (j == k) { + continue; + } + live_cmp = &block->live.items[k]; + s2 = live_cmp->start; + e2 = live_cmp->end; + if ( + (s2 < 0 && e2 < 0) || + (s1 < 0 && e1 < 0) || + (s1 < 0 && s2 < 0) || + (e1 < 0 && e2 < 0) || + (s1 >= 0 && s2 >= 0 && e1 >= 0 && e1 > s2 && s1 < s2) || + (s1 >= 0 && s2 >= 0 && e2 >= 0 && e2 > s1 && s2 < s1) || + (s1 >= 0 && e1 >= 0 && e2 >= 0 && e1 > s2 && s1 < e2) + ) { + for (l = 0; l < graph[live->temp_id].count; l++) { + if (graph[live->temp_id].items[l] == live_cmp->temp_id) { + break; + } + } + if (l == graph[live->temp_id].count) { + da_append(&graph[live->temp_id], live_cmp->temp_id); + } + } else { + /* fprintf(stderr, "No overlap in this basic block: {%i, %i} {%i, %i}\n", s1, e1, s2, e2); */ + } + } + } + } + + bool possible[x86_64_registers_usable_count]; + for (i = 0; i < temp_count; i++) { + for (j = 0; j < x86_64_registers_usable_count; j++) { + possible[j] = true; + } + for (j = 0; j < graph[i].count; j++) { + if (mappings[graph[i].items[j]] != -1) { + possible[mappings[graph[i].items[j]]] = false; + } + } + for (j = 0; j < x86_64_registers_usable_count; j++) { + if (possible[j]) { + mappings[i] = x86_64_registers_usable[j]; + break; + } + } + if (j == x86_64_registers_usable_count) { + todo("spill"); + } + } + + for (i = 0; i < fn->blocks.count; i++) { + block = &fn->blocks.items[i]; + for (j = 0; j < block->instructions.count; j++) { + x86_64_Instruction *ins = &block->instructions.items[j]; + if (ins->opcode == x86_64_PSEUDO_CALL) { + if (!ins->ret.reg.physical) { + ins->ret.reg.physical = true; + ins->ret.reg.number = mappings[ins->ret.reg.number]; + } + for (k = 0; k < ins->call_args.count; k++) { + if (ins->call_args.items[k].kind == x86_64_RAND_REGISTER) { + if (!ins->call_args.items[k].reg.physical) { + ins->call_args.items[k].reg.physical = true; + ins->call_args.items[k].reg.number = mappings[ins->call_args.items[k].reg.number]; + } + } + } + continue; + } + if (ins->opcode == x86_64_PSEUDO_PHI) { + todo("reg phi"); + continue; + } + switch (ins->encoding) { + case x86_64_NO_OPERAND: + case x86_64_I: + break; + + case x86_64_R: + case x86_64_RI: + if (!ins->rand1.reg.physical) { + ins->rand1.reg.physical = true; + ins->rand1.reg.number = mappings[ins->rand1.reg.number]; + } + break; + + case x86_64_RR: + if (!ins->rand1.reg.physical) { + ins->rand1.reg.physical = true; + ins->rand1.reg.number = mappings[ins->rand1.reg.number]; + } + + if (!ins->rand2.reg.physical) { + ins->rand2.reg.physical = true; + ins->rand2.reg.number = mappings[ins->rand2.reg.number]; + } + break; + + case x86_64_M: + todo("assign M"); + case x86_64_RM: + switch (ins->rand2.mem.encoding) { + case x86_64_MEM_D: + break; + case x86_64_MEM_BS: + todo("MEM_BS"); + case x86_64_MEM_B: + case x86_64_MEM_BD: + if (!ins->rand2.mem.base.physical) { + ins->rand2.mem.base.physical = true; + ins->rand2.mem.base.number = mappings[ins->rand2.mem.base.number]; + } + break; + case x86_64_MEM_SD: + todo("MEM_SD"); + case x86_64_MEM_BSD: + todo("MEM_BSD"); + default: + unreachable("memory encoding"); + } + if (!ins->rand1.reg.physical) { + ins->rand1.reg.physical = true; + ins->rand1.reg.number = mappings[ins->rand1.reg.number]; + } + break; + case x86_64_MR: + switch (ins->rand1.mem.encoding) { + case x86_64_MEM_D: + break; + case x86_64_MEM_BS: + todo("MEM_BS"); + case x86_64_MEM_B: + case x86_64_MEM_BD: + if (!ins->rand1.mem.base.physical) { + ins->rand1.mem.base.physical = true; + ins->rand1.mem.base.number = mappings[ins->rand1.mem.base.number]; + } + break; + case x86_64_MEM_SD: + todo("MEM_SD"); + case x86_64_MEM_BSD: + todo("MEM_BSD"); + default: + unreachable("memory encoding"); + } + if (!ins->rand2.reg.physical) { + ins->rand2.reg.physical = true; + ins->rand2.reg.number = mappings[ins->rand2.reg.number]; + } + break; + case x86_64_MI: + todo("assign MI"); + case x86_64_RMI: + todo("assign RMI"); + default: + unreachable("ins->encoding"); + } + } + } + x86_64_emit_temp_interference_graph_dotfmt(graph, temp_count); + x86_64_emit_temp_colored_graph_dotfmt(graph, mappings, temp_count); + free(graph); + free(mappings); + return true; +} + +bool +x86_64_simplify_constant_operations(x86_64_Function *fn) +{ + size_t i, j; + x86_64_Basic_block *block; + x86_64_Instruction *ins; + for (i = 0; i < fn->blocks.count; i++) { + block = &fn->blocks.items[i]; + for (j = 0; j < block->instructions.count; j++) { + ins = &block->instructions.items[j]; + + if (ins->opcode == x86_64_MOV) { + if (ins->encoding == x86_64_RI && ins->rand2.imm.kind == x86_64_IMM_LITERAL) { + if (ins->rand2.imm.i64 == 0) { + ins->opcode = x86_64_XOR; + ins->encoding = x86_64_RR; + ins->rand1.bit_width = 32; + ins->rand2 = ins->rand1; + } else if (ins->rand2.imm.i64 > 0 && ins->rand2.imm.i64 <= UINT32_MAX && ins->rand1.bit_width == 64) { + ins->rand1.bit_width = 32; + } + } + } else if (ins->opcode == x86_64_ADD) { + if (ins->encoding == x86_64_RI && ins->rand2.imm.kind == x86_64_IMM_LITERAL) { + if (ins->rand2.imm.i64 == 1) { + ins->opcode = x86_64_INC; + ins->encoding = x86_64_R; + if (ins->rand1.bit_width != 64) { + ins->rand1.bit_width = 32; + } + } else if (ins->rand2.imm.i64 > 0 && ins->rand2.imm.i64 <= UINT32_MAX && ins->rand1.bit_width == 64) { + ins->rand1.bit_width = 32; + } + } + } + } + } + return true; +} + +bool +x86_64_delete_nop(x86_64_Function *fn) +{ + bool is_nop; + size_t i, j; + x86_64_Basic_block *block; + x86_64_Instruction *ins; + for (i = 0; i < fn->blocks.count; i++) { + block = &fn->blocks.items[i]; + for (j = 0; j < block->instructions.count; j++) { + is_nop = false; + ins = &block->instructions.items[j]; + + if (ins->opcode == x86_64_MOV && ins->encoding == x86_64_RR) { + if (ins->rand1.reg.number == ins->rand2.reg.number) { + is_nop = true; + } + } else if(ins->opcode == x86_64_JMP && ins->rand1.imm.label_id == i + 1) { + assert(j == block->instructions.count - 1); + is_nop = true; + } else if(ins->opcode == x86_64_RET && i == fn->blocks.count - 1) { + assert(j == block->instructions.count - 1); + is_nop = true; + } + + if (is_nop) { + da_delete_ordered(&block->instructions, j); + j--; + } + } + } + return true; +} + +bool +x86_64_compile_program(Ir_program prog, x86_64_Program *out_prog) +{ + bool success = true; + size_t i; + x86_64_Function func = {0}; + for (i = 0; i < prog.functions.count; i++) { + func = (x86_64_Function) { .name = prog.functions.items[i].name }; + if (!x86_64_compile_function(prog.functions.items[i], &func, &out_prog->static_data)) { + da_append(&out_prog->functions, func); + success = false; + break; + } + if (!x86_64_calculate_call_graph(&func)) { + da_append(&out_prog->functions, func); + success = false; + break; + } + + x86_64_emit_call_graph_dotfmt(func); + + if (!x86_64_calculate_liveness(&func)) { + da_append(&out_prog->functions, func); + success = false; + break; + } + + if (!x86_64_expand_pseudo_instructions(&func)) { + da_append(&out_prog->functions, func); + success = false; + break; + } + + if (!x86_64_assign_registers(&func)) { + da_append(&out_prog->functions, func); + success = false; + break; + } + + if (!x86_64_simplify_constant_operations(&func)) { + da_append(&out_prog->functions, func); + success = false; + break; + } + + if (!x86_64_delete_nop(&func)) { + da_append(&out_prog->functions, func); + success = false; + break; + } + + da_append(&out_prog->functions, func); + } + return success; +} + +bool +x86_64_compile_and_emit(Ir_program prog, Sb *sb) +{ + x86_64_Program x86_64_prog = {0}; + x86_64_prog.externs = prog.externs; + if (!x86_64_compile_program(prog, &x86_64_prog)) { + x86_64_emit_program(x86_64_prog, sb); + return false; + } + return x86_64_emit_program(x86_64_prog, sb); +} + +Backend x86_64_backend = { + "x86_64 assembly", + x86_64_compile_and_emit, +};