backend

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

commit 8494f427c99de816ae32ecc6494bb24c00db86dd
parent bb9ac0fb9b7b5c3faa4074c2cc54dd8d70a88f47
Author: William Djupström <william@deepztream.com>
Date:   Sun, 27 Sep 2026 13:20:54 +0200

Add syscalls

Diffstat:
MMakefile | 12+++++++++---
Msrc/backend.h | 7+++++++
Msrc/ir_backend.c | 19++++++++++++++++++-
Msrc/lexer.c | 28+++++++++++++++-------------
Msrc/lexer.h | 1+
Msrc/parse.c | 50++++++++++++++++++++++++++++++++++++++++++++++++++
Msrc/x86_64-codegen.c | 815++++++++++++++++++++++++++++++++++++++++++++++++++++++++++---------------------
7 files changed, 699 insertions(+), 233 deletions(-)

diff --git a/Makefile b/Makefile @@ -1,16 +1,19 @@ BUILD_DIR = build -DEP_FILES = src/ir_backend.c \ +SRC_FILES = src/ir_backend.c \ src/phi.c \ src/x86_64-codegen.c \ dlib/dlib.h \ - src/backend.h + src/backend.h \ + src/parse.c \ + src/lexer.h \ + src/lexer.c CFLAGS=-ggdb -Og -Wall -Wextra -Wswitch-enum -I./dlib .PHONY: parse clean all: $(BUILD_DIR)/parse $(BUILD_DIR)/parse_output -$(BUILD_DIR)/parse: src/parse.c src/lexer.c src/lexer.h $(DEP_FILES) +$(BUILD_DIR)/parse: $(SRC_FILES) mkdir -p $(BUILD_DIR) gcc $(CFLAGS) -o $@ src/parse.c src/lexer.c @@ -28,3 +31,6 @@ $(BUILD_DIR)/parse_output.nasm: $(BUILD_DIR)/parse clean: rm -rf $(BUILD_DIR)/* + +tags: $(SRC_FILES) + ctags $(SRC_FILES) diff --git a/src/backend.h b/src/backend.h @@ -27,6 +27,7 @@ typedef enum Ir_kind { IR_ASSIGN, IR_BINOP, IR_CALL, + IR_SYSCALL, IR_RETURN, /* IR_LABEL, */ IR_JUMP, @@ -101,6 +102,11 @@ typedef struct { } Ir_call_args; typedef struct { + Ir_arg syscall; + Ir_arg_list args; +} Ir_syscall_args; + +typedef struct { enum Ir_kind kind; Ir_arg result; union { @@ -129,6 +135,7 @@ typedef struct { } branch; Ir_arg ret; Ir_call_args call; + Ir_syscall_args syscall; Phi_entry_list phi_list; }; } Ir; diff --git a/src/ir_backend.c b/src/ir_backend.c @@ -74,6 +74,7 @@ ir_compile_block(Ir_block block, Sb *sb) size_t i, j; Ir ir; Temp_allocator saved_allocator; + const char *str; for (i = 0; i < block.count; i++) { saved_allocator = temp_allocator; ir = block.items[i]; @@ -93,7 +94,12 @@ ir_compile_block(Ir_block block, Sb *sb) 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)); + str = ir_arg_to_cstr(ir.result); + sb_printf(sb, " %s", str); + str = ir_type_to_cstr(ir.result.type); + sb_printf(sb, " =%s", str); + str = ir_arg_to_cstr(ir.assign); + sb_printf(sb, " %s", str); break; case IR_BINOP: assert(ir.result.kind != ARG_NONE); @@ -115,6 +121,17 @@ ir_compile_block(Ir_block block, Sb *sb) } sb_append_char(sb, ')'); break; + case IR_SYSCALL: + assert(ir.result.kind != ARG_NONE); + sb_printf(sb, " %s = syscall %s (", ir_arg_to_cstr(ir.result), ir_arg_to_cstr(ir.syscall.syscall)); + for (j = 0; j < ir.syscall.args.count; j++) { + if (j) { + sb_append_cstr(sb, ", "); + } + sb_append_cstr(sb, ir_arg_to_cstr(ir.syscall.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)); diff --git a/src/lexer.c b/src/lexer.c @@ -4,21 +4,22 @@ #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"), + [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_SYSCALL - T_KEYWORDS_] = sv_literal("syscall"), + [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"); +static_assert(T_COUNT_ - T_KEYWORDS_ == 13, "keywords[] wrong length"); int keywords_count = (sizeof(keywords) / sizeof(keywords[0])); void @@ -49,6 +50,7 @@ sb_append_token_kind(Sb *sb, Token_kind kind) 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_SYSCALL) sb_append_cstr(sb, "syscall"); 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"); diff --git a/src/lexer.h b/src/lexer.h @@ -34,6 +34,7 @@ typedef enum { T_PTR, T_VOID, T_CALL, + T_SYSCALL, T_JUMP, T_BRANCH, T_PHI, diff --git a/src/parse.c b/src/parse.c @@ -1,3 +1,4 @@ +#define _GNU_SOURCE #define DLIB_IMPLEMENTATION #include "dlib.h" @@ -157,6 +158,43 @@ parse_ir_call(Ir_call_args *out_call_args, Lexer *lexer) } bool +parse_ir_syscall(Ir_syscall_args *out_syscall_args, Lexer *lexer) +{ + if (!parse_ir_value(&out_syscall_args->syscall, lexer)) { + return false; + } + 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_syscall_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, '[')) { @@ -219,6 +257,18 @@ parse_ir_assignment(Ir *out_ins, Lexer *lexer) .result = result, .call = call_args, }; + } else if (t.kind == T_SYSCALL) { + next_token(lexer); + skip_whitespace(lexer); + Ir_syscall_args syscall_args = {0}; + if (!parse_ir_syscall(&syscall_args, lexer)) { + return false; + } + *out_ins = (Ir) { + .kind = IR_SYSCALL, + .result = result, + .syscall = syscall_args, + }; } else if (t.kind == T_PHI) { next_token(lexer); skip_whitespace(lexer); diff --git a/src/x86_64-codegen.c b/src/x86_64-codegen.c @@ -1,5 +1,8 @@ +#define SIZE_T_INVALID 0xfffffffffffffffful + typedef enum { x86_64_MOV, + x86_64_XCHG, x86_64_PUSH, x86_64_JMP, x86_64_JZ, @@ -12,8 +15,11 @@ typedef enum { x86_64_XOR, x86_64_RET, x86_64_CALL, + x86_64_SYSCALL, + x86_64_PSEUDO_RET, x86_64_PSEUDO_CALL, + x86_64_PSEUDO_SYSCALL, x86_64_PSEUDO_PHI, } x86_64_Opcode; @@ -38,8 +44,8 @@ typedef enum { } x86_64_Operand_kind; typedef struct { - bool physical; - size_t number; + int8_t physical; + size_t temp_id; } x86_64_Register; typedef enum { @@ -142,10 +148,14 @@ const char *x86_64_registers_err[16] = { #define x86_64_REGISTERS_COUNT (sizeof(x86_64_registers_64) / sizeof(*x86_64_registers_64)) -int x86_64_registers_ccall[6] = { +int8_t x86_64_registers_ccall[6] = { 7, 6, 2, 1, 8, 9, }; +int8_t x86_64_registers_syscall[6] = { + 7, 6, 2, 10, 8, 9, +}; + int x86_64_bit_width_of_type(Ir_type type) { @@ -191,11 +201,11 @@ x86_64_operand_to_cstr(x86_64_Operand rand) } switch(rand.kind) { case x86_64_RAND_REGISTER: - if (rand.reg.physical) { - free(leak_buf); - return reg_names[rand.reg.number]; + if (rand.reg.physical == -1) { + snprintf(leak_buf, 32, "r_%zu", rand.reg.temp_id); } else { - snprintf(leak_buf, 32, "r_%zu", rand.reg.number); + free(leak_buf); + return reg_names[rand.reg.physical]; } break; case x86_64_RAND_MEMORY: @@ -207,12 +217,12 @@ x86_64_operand_to_cstr(x86_64_Operand rand) case x86_64_MEM_BS: todo_p("MEM_BS"); case x86_64_MEM_BD: - assert(rand.mem.base.physical); + assert(rand.mem.base.physical != -1); 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); + len = snprintf(leak_buf, 32, "[%s+%li]", x86_64_registers_64[rand.mem.base.physical], rand.mem.offset.i64); } else { - len = snprintf(leak_buf, 32, "[%s-%li]", x86_64_registers_64[rand.mem.base.number], -rand.mem.offset.i64); + len = snprintf(leak_buf, 32, "[%s-%li]", x86_64_registers_64[rand.mem.base.physical], -rand.mem.offset.i64); } assert(len < 32); break; @@ -259,8 +269,6 @@ typedef struct { size_t capacity; } x86_64_Instruction_list; -#define SIZE_T_INVALID 0xfffffffffffffffful - typedef enum { x86_64_LIVE_NOT_STARTED = 0, x86_64_LIVE_STARTED, @@ -415,6 +423,26 @@ x86_64_emit_instruction(x86_64_Instruction ins, Sb *sb) unreachable("encoding"); } break; + case x86_64_XCHG: + switch (ins.encoding) { + case x86_64_RR: + case x86_64_RM: + case x86_64_MR: + sb_printf(sb, " xchg %s, %s\n", x86_64_operand_to_cstr(ins.rand1), x86_64_operand_to_cstr(ins.rand2)); + break; + + case x86_64_MI: + case x86_64_RI: + 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: @@ -466,6 +494,12 @@ x86_64_emit_instruction(x86_64_Instruction ins, Sb *sb) case x86_64_CALL: sb_printf(sb, " call %.*s\n", (int) ins.rand1.symbol.count, ins.rand1.symbol.data); break; + case x86_64_SYSCALL: + sb_printf(sb, " syscall\n"); + break; + case x86_64_PSEUDO_RET: + sb_printf(sb, " ret %s\n", x86_64_operand_to_cstr(ins.ret)); + 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); @@ -477,6 +511,17 @@ x86_64_emit_instruction(x86_64_Instruction ins, Sb *sb) } sb_printf(sb, ") -> %s\n", x86_64_operand_to_cstr(ins.ret)); break; + case x86_64_PSEUDO_SYSCALL: + assert(ins.rand1.kind == x86_64_RAND_IMMEDIATE || ins.rand1.kind == x86_64_RAND_REGISTER); + sb_printf(sb, " syscall %s (", x86_64_operand_to_cstr(ins.rand1)); + 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"); @@ -508,8 +553,8 @@ x86_64_compile_instruction(Ir ir, x86_64_Instruction_list *list, x86_64_Data_lis .bit_width = 32, .kind = x86_64_RAND_REGISTER, .reg = { - .physical = false, - .number = ir.result.temp_id, + .physical = -1, + .temp_id = ir.result.temp_id, }, }, .rand2 = { @@ -530,8 +575,8 @@ x86_64_compile_instruction(Ir ir, x86_64_Instruction_list *list, x86_64_Data_lis .bit_width = 64, .kind = x86_64_RAND_REGISTER, .reg = { - .physical = false, - .number = ir.result.temp_id, + .physical = -1, + .temp_id = ir.result.temp_id, }, }, .rand2 = { @@ -552,16 +597,16 @@ x86_64_compile_instruction(Ir ir, x86_64_Instruction_list *list, x86_64_Data_lis .bit_width = 32, .kind = x86_64_RAND_REGISTER, .reg = { - .physical = false, - .number = ir.result.temp_id, + .physical = -1, + .temp_id = ir.result.temp_id, }, }, .rand2 = { .bit_width = 32, .kind = x86_64_RAND_REGISTER, .reg = { - .physical = false, - .number = ir.assign.temp_id, + .physical = -1, + .temp_id = ir.assign.temp_id, }, }, })); @@ -578,11 +623,12 @@ x86_64_compile_instruction(Ir ir, x86_64_Instruction_list *list, x86_64_Data_lis 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"); - } + /* 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); */ + if (ir.binop.left.kind == ARG_TEMP_STORAGE) { da_append(list, ((x86_64_Instruction) { .opcode = x86_64_MOV, .encoding = x86_64_RR, @@ -590,19 +636,44 @@ x86_64_compile_instruction(Ir ir, x86_64_Instruction_list *list, x86_64_Data_lis .bit_width = 32, .kind = x86_64_RAND_REGISTER, .reg = { - .physical = false, - .number = ir.result.temp_id, + .physical = -1, + .temp_id = ir.result.temp_id, }, }, .rand2 = { .bit_width = 32, .kind = x86_64_RAND_REGISTER, .reg = { - .physical = false, - .number = ir.binop.left.temp_id, + .physical = -1, + .temp_id = ir.binop.left.temp_id, }, }, })); + } else { + todo("+ left"); + } + if (ir.binop.right.kind == ARG_TEMP_STORAGE) { + da_append(list, ((x86_64_Instruction) { + .opcode = x86_64_ADD, + .encoding = x86_64_RR, + .rand1 = { + .bit_width = 32, + .kind = x86_64_RAND_REGISTER, + .reg = { + .physical = -1, + .temp_id = ir.result.temp_id, + }, + }, + .rand2 = { + .bit_width = 32, + .kind = x86_64_RAND_REGISTER, + .reg = { + .physical = -1, + .temp_id = ir.binop.right.temp_id, + }, + }, + })); + } else if (ir.binop.right.kind == ARG_INT_LITERAL) { da_append(list, ((x86_64_Instruction) { .opcode = x86_64_ADD, .encoding = x86_64_RI, @@ -610,8 +681,8 @@ x86_64_compile_instruction(Ir ir, x86_64_Instruction_list *list, x86_64_Data_lis .bit_width = 32, .kind = x86_64_RAND_REGISTER, .reg = { - .physical = false, - .number = ir.result.temp_id, + .physical = -1, + .temp_id = ir.result.temp_id, }, }, .rand2 = { @@ -646,8 +717,8 @@ x86_64_compile_instruction(Ir ir, x86_64_Instruction_list *list, x86_64_Data_lis .bit_width = 32, .kind = x86_64_RAND_REGISTER, .reg = { - .physical = false, - .number = ir.binop.left.temp_id, + .physical = -1, + .temp_id = ir.binop.left.temp_id, }, }, .rand2 = { @@ -670,8 +741,8 @@ x86_64_compile_instruction(Ir ir, x86_64_Instruction_list *list, x86_64_Data_lis .bit_width = 8, .kind = x86_64_RAND_REGISTER, .reg = { - .physical = false, - .number = ir.result.temp_id, + .physical = -1, + .temp_id = ir.result.temp_id, }, }, })); @@ -692,7 +763,22 @@ x86_64_compile_instruction(Ir ir, x86_64_Instruction_list *list, x86_64_Data_lis if (ir.call.args.count > 6) { todo("call > 6 args"); } - /* + 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 = -1, + .temp_id = 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) { @@ -705,16 +791,18 @@ x86_64_compile_instruction(Ir ir, x86_64_Instruction_list *list, x86_64_Data_lis 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(data_list, ir.call.args.items[i].cstr), + .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, + .physical = -1, + .temp_id = ir.call.args.items[i].temp_id, }; break; case ARG_ADDRESS: @@ -723,60 +811,85 @@ x86_64_compile_instruction(Ir ir, x86_64_Instruction_list *list, x86_64_Data_lis default: unreachable("args operand"); } - da_append(list, ((x86_64_Instruction) { - .opcode = x86_64_MOV, - .encoding = x86_64_RR, - .rand1 = { + da_append(&list->items[list->count - 1].call_args, arg); + } + break; + case IR_SYSCALL: + if (ir.syscall.args.count > 6) { + todo("syscall > 6 args"); + } + x86_64_Operand_encoding syscall_encoding; + x86_64_Operand syscall_rand; + switch (ir.syscall.syscall.kind) { + case ARG_INT_LITERAL: + syscall_encoding = x86_64_I; + syscall_rand = (x86_64_Operand) { + .kind = x86_64_RAND_IMMEDIATE, + .imm = { + .kind = x86_64_IMM_LITERAL, + .i64 = ir.syscall.syscall.i64, + }, + }; + break; + case ARG_TEMP_STORAGE: + syscall_encoding = x86_64_R; + syscall_rand = (x86_64_Operand) { .kind = x86_64_RAND_REGISTER, + .bit_width = 64, .reg = { - .physical = true, - .number = x86_64_registers_ccall[i], + .physical = -1, + .temp_id = ir.syscall.syscall.temp_id, }, - }, - .rand2 = arg, - })); + }; + break; + case ARG_CSTRING_LITERAL: + unreachable("syscall->cstring"); + case ARG_ADDRESS: + unreachable("syscall->address"); + case ARG_REGISTER: + unreachable("syscall->register"); + case ARG_NONE: + unreachable("syscall->none"); + default: + unreachable("syscall operand kind"); } - */ 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, - }, + .opcode = x86_64_PSEUDO_SYSCALL, + .encoding = syscall_encoding, + .rand1 = syscall_rand, .ret = { .kind = x86_64_RAND_REGISTER, - .bit_width = 32, + .bit_width = 64, .reg = { - .physical = false, - .number = ir.result.temp_id, + .physical = -1, + .temp_id = ir.result.temp_id, }, }, })); - for (size_t i = 0; i < ir.call.args.count; i++) { + for (size_t i = 0; i < ir.syscall.args.count; i++) { x86_64_Operand arg = {0}; - switch (ir.call.args.items[i].kind) { + switch (ir.syscall.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, + .i64 = ir.syscall.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.bit_width = x86_64_bit_width_of_type(ir.syscall.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), + .label_id = x86_64_add_cstr_from_sv(data_list, ir.syscall.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.bit_width = x86_64_bit_width_of_type(ir.syscall.args.items[i].type); arg.reg = (x86_64_Register) { - .physical = false, - .number = ir.call.args.items[i].temp_id, + .physical = -1, + .temp_id = ir.syscall.args.items[i].temp_id, }; break; case ARG_ADDRESS: @@ -790,6 +903,7 @@ x86_64_compile_instruction(Ir ir, x86_64_Instruction_list *list, x86_64_Data_lis 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, @@ -797,22 +911,31 @@ x86_64_compile_instruction(Ir ir, x86_64_Instruction_list *list, x86_64_Data_lis .bit_width = 32, .kind = x86_64_RAND_REGISTER, .reg = { - .physical = true, - .number = 0, + .physical = 0, + .temp_id = SIZE_T_INVALID, }, }, .rand2 = { .bit_width = 32, .kind = x86_64_RAND_REGISTER, .reg = { - .physical = false, - .number = ir.ret.temp_id, + .physical = -1, + .temp_id = ir.ret.temp_id, }, }, })); + */ da_append(list, ((x86_64_Instruction) { - .opcode = x86_64_RET, - .encoding = x86_64_NO_OPERAND, + .opcode = x86_64_PSEUDO_RET, + .encoding = x86_64_R, + .rand1 = { + .bit_width = 32, + .kind = x86_64_RAND_REGISTER, + .reg = { + .physical = -1, + .temp_id = ir.ret.temp_id, + }, + }, })); } else { todo("return"); @@ -845,16 +968,16 @@ x86_64_compile_instruction(Ir ir, x86_64_Instruction_list *list, x86_64_Data_lis .bit_width = 8, .kind = x86_64_RAND_REGISTER, .reg = { - .physical = false, - .number = ir.branch.cond.temp_id, + .physical = -1, + .temp_id = ir.branch.cond.temp_id, }, }, .rand2 = { .bit_width = 8, .kind = x86_64_RAND_REGISTER, .reg = { - .physical = false, - .number = ir.branch.cond.temp_id, + .physical = -1, + .temp_id = ir.branch.cond.temp_id, }, }, })); @@ -1055,21 +1178,24 @@ x86_64_calculate_internal_liveness(x86_64_Basic_block *block) switch (ins.opcode) { case x86_64_CALL: unreachable("live call"); + case x86_64_SYSCALL: + unreachable("live syscall"); case x86_64_PSEUDO_PHI: todo("live phi"); case x86_64_MOV: + case x86_64_XCHG: case x86_64_SETL: switch (ins.encoding) { case x86_64_R: case x86_64_RI: - if (ins.rand1.reg.physical) { + if (ins.rand1.reg.physical != -1) { /* 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) { + if ((entry_index = x86_64_get_liveness_entry(&block->live, ins.rand1.reg.temp_id)) == SIZE_T_INVALID) { da_append(&block->live, ((x86_64_Liveness_entry) { .start = i, .end = i, - .temp_id = ins.rand1.reg.number, + .temp_id = ins.rand1.reg.temp_id, })); } else { assert(block->live.items[entry_index].start == -1); @@ -1081,28 +1207,28 @@ x86_64_calculate_internal_liveness(x86_64_Basic_block *block) todo("modifying M"); case x86_64_RR: - if (ins.rand1.reg.physical) { + if (ins.rand1.reg.physical != -1) { /* 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) { + if ((entry_index = x86_64_get_liveness_entry(&block->live, ins.rand1.reg.temp_id)) == SIZE_T_INVALID) { da_append(&block->live, ((x86_64_Liveness_entry) { .start = i, .end = i, - .temp_id = ins.rand1.reg.number, + .temp_id = ins.rand1.reg.temp_id, })); } else { assert(block->live.items[entry_index].start == -1); block->live.items[entry_index].start = i; } } - if (ins.rand2.reg.physical) { + if (ins.rand2.reg.physical != -1) { /* 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) { + if ((entry_index = x86_64_get_liveness_entry(&block->live, ins.rand2.reg.temp_id)) == SIZE_T_INVALID) { da_append(&block->live, ((x86_64_Liveness_entry) { .start = -1, .end = i, - .temp_id = ins.rand2.reg.number, + .temp_id = ins.rand2.reg.temp_id, })); } else { entry = &block->live.items[entry_index]; @@ -1113,7 +1239,7 @@ x86_64_calculate_internal_liveness(x86_64_Basic_block *block) 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); */ + /* fprintf(stderr, "%%%zu already defined as (%i -> %i)\n", ins.rand2.reg.temp_id, block->live.items[entry_index].start, block->live.items[entry_index].end); */ } } break; @@ -1142,18 +1268,19 @@ x86_64_calculate_internal_liveness(x86_64_Basic_block *block) case x86_64_PUSH: case x86_64_TEST: case x86_64_CMP: + case x86_64_PSEUDO_RET: switch (ins.encoding) { case x86_64_RI: case x86_64_R: - if (ins.rand1.reg.physical) { + if (ins.rand1.reg.physical != -1) { /* 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) { + if ((entry_index = x86_64_get_liveness_entry(&block->live, ins.rand1.reg.temp_id)) == SIZE_T_INVALID) { da_append(&block->live, ((x86_64_Liveness_entry) { .start = -1, .end = i, - .temp_id = ins.rand1.reg.number, + .temp_id = ins.rand1.reg.temp_id, })); } else { /* DO NOTHING? */ @@ -1162,27 +1289,27 @@ x86_64_calculate_internal_liveness(x86_64_Basic_block *block) case x86_64_M: todo("non-modifying M"); case x86_64_RR: - if (ins.rand1.reg.physical) { + if (ins.rand1.reg.physical != -1) { /* 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) { + if ((entry_index = x86_64_get_liveness_entry(&block->live, ins.rand1.reg.temp_id)) == SIZE_T_INVALID) { da_append(&block->live, ((x86_64_Liveness_entry) { .start = -1, .end = i, - .temp_id = ins.rand1.reg.number, + .temp_id = ins.rand1.reg.temp_id, })); } else { /* DO NOTHING? */ } } - if (ins.rand2.reg.physical) { + if (ins.rand2.reg.physical != -1) { /* 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) { + if ((entry_index = x86_64_get_liveness_entry(&block->live, ins.rand2.reg.temp_id)) == SIZE_T_INVALID) { da_append(&block->live, ((x86_64_Liveness_entry) { .start = -1, .end = i, - .temp_id = ins.rand2.reg.number, + .temp_id = ins.rand2.reg.temp_id, })); } else { /* DO NOTHING? */ @@ -1210,11 +1337,11 @@ x86_64_calculate_internal_liveness(x86_64_Basic_block *block) 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) { + if ((entry_index = x86_64_get_liveness_entry(&block->live, ins.ret.reg.temp_id)) == SIZE_T_INVALID) { da_append(&block->live, ((x86_64_Liveness_entry) { .start = i, .end = i, - .temp_id = ins.ret.reg.number, + .temp_id = ins.ret.reg.temp_id, })); } else { assert(block->live.items[entry_index].start == -1); @@ -1226,15 +1353,58 @@ x86_64_calculate_internal_liveness(x86_64_Basic_block *block) if (arg.kind != x86_64_RAND_REGISTER) { continue; } - if (arg.reg.physical) { + if (arg.reg.physical != -1) { /* 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) { + if ((entry_index = x86_64_get_liveness_entry(&block->live, arg.reg.temp_id)) == SIZE_T_INVALID) { + da_append(&block->live, ((x86_64_Liveness_entry) { + .start = -1, + .end = i, + .temp_id = arg.reg.temp_id, + })); + } else { + /* DO NOTHING? */ + } + } + } + break; + case x86_64_PSEUDO_SYSCALL: + if (ins.encoding == x86_64_R && ins.rand1.reg.physical == -1) { + if ((entry_index = x86_64_get_liveness_entry(&block->live, ins.rand1.reg.temp_id)) == SIZE_T_INVALID) { + da_append(&block->live, ((x86_64_Liveness_entry) { + .start = -1, + .end = i, + .temp_id = ins.rand1.reg.temp_id, + })); + } else { + /* DO NOTHING? */ + } + } + if ((entry_index = x86_64_get_liveness_entry(&block->live, ins.ret.reg.temp_id)) == SIZE_T_INVALID) { + da_append(&block->live, ((x86_64_Liveness_entry) { + .start = i, + .end = i, + .temp_id = ins.ret.reg.temp_id, + })); + } 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 != -1) { + break; + } + if ((entry_index = x86_64_get_liveness_entry(&block->live, arg.reg.temp_id)) == SIZE_T_INVALID) { da_append(&block->live, ((x86_64_Liveness_entry) { .start = -1, .end = i, - .temp_id = arg.reg.number, + .temp_id = arg.reg.temp_id, })); } else { /* DO NOTHING? */ @@ -1326,7 +1496,7 @@ x86_64_calculate_liveness(x86_64_Function *fn) assert(max_temp != SIZE_T_INVALID); fn->temporary_count = max_temp + 1; - /* fprintf(stderr, "\n--- Total Lifetimes ---\n"); */ + 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)) { @@ -1334,11 +1504,11 @@ x86_64_calculate_liveness(x86_64_Function *fn) } 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"); */ + 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; } @@ -1353,7 +1523,7 @@ x86_64_calculate_call_graph(x86_64_Function *fn) block = &fn->blocks.items[i]; for (j = 0; j < block->instructions.count; j++) { ins = &block->instructions.items[j]; - if (ins->opcode == x86_64_RET) { + if (ins->opcode == x86_64_RET || ins->opcode == x86_64_PSEUDO_RET) { da_append(&block->children, fn->blocks.count); } else if (ins->opcode == x86_64_JMP || ins->opcode == x86_64_JZ || @@ -1396,6 +1566,36 @@ x86_64_emit_call_graph_dotfmt(x86_64_Function fn) } bool +x86_64_is_pseudo_opcode(x86_64_Opcode opcode) { + switch (opcode) { + case x86_64_MOV: + case x86_64_XCHG: + case x86_64_PUSH: + case x86_64_JMP: + case x86_64_JZ: + case x86_64_JNZ: + case x86_64_TEST: + case x86_64_CMP: + case x86_64_SETL: + case x86_64_INC: + case x86_64_ADD: + case x86_64_XOR: + case x86_64_RET: + case x86_64_CALL: + case x86_64_SYSCALL: + return false; + + case x86_64_PSEUDO_RET: + case x86_64_PSEUDO_CALL: + case x86_64_PSEUDO_SYSCALL: + case x86_64_PSEUDO_PHI: + return true; + default: + unreachable("opcode"); + } +} + +bool x86_64_expand_pseudo_instructions(x86_64_Function *fn) { size_t i, j, k, l; @@ -1408,18 +1608,60 @@ x86_64_expand_pseudo_instructions(x86_64_Function *fn) 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) { + /* if (ins->opcode != x86_64_PSEUDO_CALL) { */ + if (!x86_64_is_pseudo_opcode(ins->opcode)) { da_append(&new_instruction_list, *ins); continue; } + if (ins->opcode == x86_64_PSEUDO_PHI) { + todo("expand pseudo-phi"); + } + if (ins->opcode == x86_64_PSEUDO_RET) { + x86_64_Operand_encoding ret_encoding; + switch (ins->encoding) { + case x86_64_R: + ret_encoding = x86_64_RR; + break; + case x86_64_I: + todo("ret I"); + case x86_64_M: + todo("ret m"); + 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_RMI: + default: + unreachable("ret encoding"); + } + da_append(&new_instruction_list, ((x86_64_Instruction) { + .opcode = x86_64_MOV, + .encoding = ret_encoding, + .rand1 = { + .kind = x86_64_RAND_REGISTER, + .bit_width = ins->rand1.bit_width, + .reg = { + .physical = 0, + .temp_id = SIZE_T_INVALID, + }, + }, + .rand2 = ins->rand1, + })); + da_append(&new_instruction_list, ((x86_64_Instruction) { + .opcode = x86_64_RET, + .encoding = x86_64_NO_OPERAND, + })); + 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) { + if (block->live.items[l].temp_id == arg->reg.temp_id) { break; } } @@ -1436,8 +1678,8 @@ x86_64_expand_pseudo_instructions(x86_64_Function *fn) .mem = { .encoding = x86_64_MEM_BD, .base = { - .physical = true, - .number = 5, + .physical = 5, + .temp_id = SIZE_T_INVALID, }, .offset_bit_width = 8, .offset = { @@ -1458,73 +1700,187 @@ x86_64_expand_pseudo_instructions(x86_64_Function *fn) unreachable("operand kind"); } } + struct { + int8_t *items; + size_t count; + size_t capacity; + } current_reg = {0}; + da_expand(&current_reg, ins->call_args.count); + for (k = 0; k < ins->call_args.count; k++) { + if (ins->call_args.items[k].kind == x86_64_RAND_REGISTER) { + current_reg.items[k] = ins->call_args.items[k].reg.physical; + } else { + current_reg.items[k] = -1; + } + } + int8_t *reg_array; + if (ins->opcode == x86_64_PSEUDO_CALL) { + reg_array = x86_64_registers_ccall; + } else if (ins->opcode == x86_64_PSEUDO_SYSCALL) { + reg_array = x86_64_registers_syscall; + } else { + unreachable("opcode"); + } for (k = 0; k < ins->call_args.count; k++) { + int8_t swap = -1; 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], + for (l = k + 1; l < ins->call_args.count; l++) { + if (reg_array[k] == current_reg.items[l]) { + fprintf(stderr, "Error: Overwriting later operand %s\n", x86_64_registers_64[reg_array[k]]); + if (current_reg.items[k] != -1) { + swap = current_reg.items[k]; + /* current_reg.items[k] = current_reg.items[l]; */ + current_reg.items[l] = swap; + } else { + todo("handle non-register cases"); + } + } + } + if (swap == -1) { + switch (arg->kind) { + case x86_64_RAND_REGISTER: + assert(arg->reg.physical != -1); + 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 = reg_array[k], + .temp_id = SIZE_T_INVALID, + }, }, - }, - .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 = { + .kind = x86_64_RAND_REGISTER, + .bit_width = arg->bit_width, + .reg = { + .physical = current_reg.items[k], + .temp_id = arg->reg.temp_id, + }, }, - }, - .rand2 = *arg, - })); - break; - case x86_64_RAND_SYMBOL: - todo("symbol"); - default: - unreachable("operand kind"); + })); + 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 = reg_array[k], + .temp_id = SIZE_T_INVALID, + }, + }, + .rand2 = *arg, + })); + break; + case x86_64_RAND_SYMBOL: + todo("symbol"); + default: + unreachable("operand kind"); + } + } else { + switch (arg->kind) { + case x86_64_RAND_REGISTER: + assert(arg->reg.physical != -1); + 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 = swap, + .temp_id = SIZE_T_INVALID, + }, + }, + .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_XCHG, + .encoding = x86_64_RR, + .rand1 = { + .kind = x86_64_RAND_REGISTER, + .bit_width = 64, + .reg = { + .physical = reg_array[k], + .temp_id = SIZE_T_INVALID, + }, + }, + .rand2 = { + .kind = x86_64_RAND_REGISTER, + .bit_width = 64, + .reg = { + .physical = swap, + .temp_id = SIZE_T_INVALID, + }, + }, + })); } } - 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, + if (ins->opcode == x86_64_PSEUDO_CALL) { + 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 = 0, + .temp_id = SIZE_T_INVALID, + }, }, - }, - .rand2 = { - .kind = x86_64_RAND_IMMEDIATE, - .imm = { - .kind = x86_64_IMM_LITERAL, - .i64 = 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, - })); + })); + da_append(&new_instruction_list, ((x86_64_Instruction) { + .opcode = x86_64_CALL, + .encoding = x86_64_I, + .rand1 = ins->rand1, + })); + } else if (ins->opcode == x86_64_PSEUDO_SYSCALL) { + if (ins->encoding == x86_64_R) { + da_append(&new_instruction_list, ((x86_64_Instruction) { + .opcode = x86_64_MOV, + .encoding = x86_64_RR, + .rand1 = { + .kind = x86_64_RAND_REGISTER, + .bit_width = ins->rand1.bit_width, + .reg = { + .physical = 0, + .temp_id = SIZE_T_INVALID, + }, + }, + .rand2 = ins->rand1, + })); + } + da_append(&new_instruction_list, ((x86_64_Instruction) { + .opcode = x86_64_SYSCALL, + .encoding = x86_64_NO_OPERAND, + })); + } else { + unreachable("opcode"); + } assert(ins->ret.kind == x86_64_RAND_REGISTER); da_append(&new_instruction_list, ((x86_64_Instruction) { .opcode = x86_64_MOV, @@ -1534,8 +1890,8 @@ x86_64_expand_pseudo_instructions(x86_64_Function *fn) .kind = x86_64_RAND_REGISTER, .bit_width = ins->ret.bit_width, .reg = { - .physical = true, - .number = 0, + .physical = 0, + .temp_id = SIZE_T_INVALID, }, }, })); @@ -1550,8 +1906,8 @@ x86_64_expand_pseudo_instructions(x86_64_Function *fn) .mem = { .encoding = x86_64_MEM_BD, .base = { - .physical = true, - .number = 5, + .physical = 5, + .temp_id = SIZE_T_INVALID, }, .offset_bit_width = 8, .offset = { @@ -1632,6 +1988,16 @@ x86_64_emit_temp_colored_graph_dotfmt(x86_64_Interference_list *graph, int *colo fprintf(f, "}\n"); } +int +x86_64_neighbours_count_compare(const void *a, const void *b, void *graph) +{ + size_t ia = *(size_t *) a; + size_t ib = *(size_t *) b; + x86_64_Interference_list *ga = &((x86_64_Interference_list *) graph)[ia]; + x86_64_Interference_list *gb = &((x86_64_Interference_list *) graph)[ib]; + return gb->count - ga->count; +} + bool x86_64_assign_registers(x86_64_Function *fn) { @@ -1673,6 +2039,7 @@ x86_64_assign_registers(x86_64_Function *fn) } } if (l == graph[live->temp_id].count) { + /* fprintf(stderr, "Overlap in this basic block: {%i, %i} {%i, %i}\n", s1, e1, s2, e2); */ da_append(&graph[live->temp_id], live_cmp->temp_id); } } else { @@ -1681,20 +2048,26 @@ x86_64_assign_registers(x86_64_Function *fn) } } } + size_t *color_order = calloc(temp_count, sizeof(*color_order)); + for (i = 0; i < temp_count; i++) { + color_order[i] = i; + } + qsort_r(color_order, temp_count, sizeof(*color_order), x86_64_neighbours_count_compare, (void *)graph); bool possible[x86_64_REGISTERS_COUNT] = {0}; for (i = 0; i < temp_count; i++) { + k = color_order[i]; for (j = 0; j < x86_64_registers_usable_count; j++) { possible[x86_64_registers_usable[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 < graph[k].count; j++) { + if (mappings[graph[k].items[j]] != -1) { + possible[mappings[graph[k].items[j]]] = false; } } for (j = 0; j < x86_64_registers_usable_count; j++) { if (possible[x86_64_registers_usable[j]]) { - mappings[i] = x86_64_registers_usable[j]; + mappings[k] = x86_64_registers_usable[j]; break; } } @@ -1708,16 +2081,31 @@ x86_64_assign_registers(x86_64_Function *fn) 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]; + assert(ins->ret.reg.physical == -1); + ins->ret.reg.physical = mappings[ins->ret.reg.temp_id]; + if (ins->rand1.kind == x86_64_RAND_REGISTER) { + assert(ins->rand1.reg.physical == -1); + ins->rand1.reg.physical = mappings[ins->rand1.reg.temp_id]; } 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]; - } + assert(ins->call_args.items[k].reg.physical == -1); + ins->call_args.items[k].reg.physical = mappings[ins->call_args.items[k].reg.temp_id]; + } + } + continue; + } + if (ins->opcode == x86_64_PSEUDO_SYSCALL) { + assert(ins->ret.reg.physical == -1); + ins->ret.reg.physical = mappings[ins->ret.reg.temp_id]; + if (ins->rand1.kind == x86_64_RAND_REGISTER) { + assert(ins->rand1.reg.physical == -1); + ins->rand1.reg.physical = mappings[ins->rand1.reg.temp_id]; + } + for (k = 0; k < ins->call_args.count; k++) { + if (ins->call_args.items[k].kind == x86_64_RAND_REGISTER) { + assert(ins->call_args.items[k].reg.physical == -1); + ins->call_args.items[k].reg.physical = mappings[ins->call_args.items[k].reg.temp_id]; } } continue; @@ -1733,22 +2121,21 @@ x86_64_assign_registers(x86_64_Function *fn) 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]; - } + assert(ins->rand1.reg.physical == -1); + ins->rand1.reg.physical = mappings[ins->rand1.reg.temp_id]; 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->rand1.reg.physical != -1) { + Sb sb = {0}; + x86_64_emit_instruction(*ins, &sb); + sb_write(1, sb); + exit(1); } + ins->rand1.reg.physical = mappings[ins->rand1.reg.temp_id]; - if (!ins->rand2.reg.physical) { - ins->rand2.reg.physical = true; - ins->rand2.reg.number = mappings[ins->rand2.reg.number]; - } + assert(ins->rand2.reg.physical == -1); + ins->rand2.reg.physical = mappings[ins->rand2.reg.temp_id]; break; case x86_64_M: @@ -1761,10 +2148,8 @@ x86_64_assign_registers(x86_64_Function *fn) 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]; - } + assert(ins->rand2.mem.base.physical == -1); + ins->rand2.mem.base.physical = mappings[ins->rand2.mem.base.temp_id]; break; case x86_64_MEM_SD: todo("MEM_SD"); @@ -1773,10 +2158,8 @@ x86_64_assign_registers(x86_64_Function *fn) default: unreachable("memory encoding"); } - if (!ins->rand1.reg.physical) { - ins->rand1.reg.physical = true; - ins->rand1.reg.number = mappings[ins->rand1.reg.number]; - } + assert(ins->rand1.reg.physical == -1); + ins->rand1.reg.physical = mappings[ins->rand1.reg.temp_id]; break; case x86_64_MR: switch (ins->rand1.mem.encoding) { @@ -1786,10 +2169,8 @@ x86_64_assign_registers(x86_64_Function *fn) 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]; - } + assert(ins->rand1.mem.base.physical == -1); + ins->rand1.mem.base.physical = mappings[ins->rand1.mem.base.temp_id]; break; case x86_64_MEM_SD: todo("MEM_SD"); @@ -1798,10 +2179,8 @@ x86_64_assign_registers(x86_64_Function *fn) default: unreachable("memory encoding"); } - if (!ins->rand2.reg.physical) { - ins->rand2.reg.physical = true; - ins->rand2.reg.number = mappings[ins->rand2.reg.number]; - } + assert(ins->rand2.reg.physical == -1); + ins->rand2.reg.physical = mappings[ins->rand2.reg.temp_id]; break; case x86_64_MI: todo("assign MI"); @@ -1829,7 +2208,7 @@ x86_64_simplify_constant_operations(x86_64_Function *fn) 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) { @@ -1871,9 +2250,13 @@ x86_64_delete_nop(x86_64_Function *fn) 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) { + if (ins->rand1.reg.physical == ins->rand2.reg.physical) { + is_nop = true; + } + } else if (ins->opcode == x86_64_XCHG && ins->encoding == x86_64_RR) { + if (ins->rand1.reg.physical == ins->rand2.reg.physical) { is_nop = true; } } else if(ins->opcode == x86_64_JMP && ins->rand1.imm.label_id == i + 1) { @@ -1920,13 +2303,13 @@ x86_64_compile_program(Ir_program prog, x86_64_Program *out_prog) break; } - if (!x86_64_expand_pseudo_instructions(&func)) { + if (!x86_64_assign_registers(&func)) { da_append(&out_prog->functions, func); success = false; break; } - if (!x86_64_assign_registers(&func)) { + if (!x86_64_expand_pseudo_instructions(&func)) { da_append(&out_prog->functions, func); success = false; break;