From 59148d666a78d671198d56caabe7fe4d7fb3fee1 Mon Sep 17 00:00:00 2001 From: Kimplul Date: Sun, 31 Mar 2024 23:09:14 +0300 Subject: produce some very limited assembly output + Several subsystems missing critical features, but enough to do some basic things like calling procedures, printing to screen and doing loops --- src/abi.c | 96 ++++++++++++++++++++ src/asm.c | 277 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/main.c | 7 ++ src/nodes.c | 21 ++--- src/opt.c | 12 +++ src/parser.y | 130 +++++++++++++++------------ src/regalloc.c | 90 +++++++++++++++++++ src/ssa.c | 8 ++ 8 files changed, 568 insertions(+), 73 deletions(-) create mode 100644 src/abi.c create mode 100644 src/asm.c create mode 100644 src/opt.c create mode 100644 src/regalloc.c create mode 100644 src/ssa.c (limited to 'src') diff --git a/src/abi.c b/src/abi.c new file mode 100644 index 0000000..cb92190 --- /dev/null +++ b/src/abi.c @@ -0,0 +1,96 @@ +#include +#include +#include + +static const int64_t ar_map[] = { + RA0, RA1, RA2, RA3, RA4, RA5, RA6, RA7, RA8, RA9, + RA10, RA11, RA12, RA13, RA14, RA15, RA16, RA17, RA18, RA19, + RA20, RA21, RA22, RA23, RA24 +}; + +static struct val nth_ar(int64_t nth) +{ + return reg_val(ar_map[nth]); +} + +static struct insn rewrite_param(struct insn n) +{ + assert(n.type == PARAM); + assert(n.in[1].class == IMM); + int64_t nth_param = n.in[1].v; + assert(nth_param >= 0 && nth_param < 25 + && "stack argument passing not yet supported"); + + return insn_create(MOVE, I27, n.out, nth_ar(nth_param), noclass()); +} + +static struct insn rewrite_retval(struct insn n) +{ + assert(n.type == RETVAL); + assert(n.in[1].class == IMM); + int64_t nth_retval = n.in[1].v; + assert(nth_retval >= 0 && nth_retval < 25); + return insn_create(MOVE, I27, n.out, nth_ar(nth_retval), noclass()); +} + +static struct insn rewrite_arg(struct insn n) +{ + assert(n.type == ARG); + assert(n.in[1].class == IMM); + int64_t nth_arg = n.in[1].v; + assert(nth_arg >= 0 && nth_arg < 25); + + if (n.in[0].class == TMP || n.in[0].class == REG) + return insn_create(MOVE, I27, nth_ar(nth_arg), n.in[0], noclass()); + else if (n.in[0].class == IMM || n.in[0].class == REF) + return insn_create(COPY, I27, nth_ar(nth_arg), n.in[0], noclass()); + + assert("illegal arg type"); + abort(); +} + +static struct insn rewrite_retarg(struct insn n) +{ + assert(n.type == RETARG); + assert(n.in[1].class == IMM); + int64_t nth_arg = n.in[1].v; + assert(nth_arg >= 0 && nth_arg < 25); + + if (n.in[0].class == TMP || n.in[0].class == REG) + return insn_create(MOVE, I27, nth_ar(nth_arg), n.in[0], noclass()); + else if (n.in[0].class == IMM || n.in[0].class == REF) + return insn_create(COPY, I27, nth_ar(nth_arg), n.in[0], noclass()); + + assert("illegal retval type"); + abort(); +} + +void abi0(struct fn *f) +{ + foreach_blk(bi, f->blks) { + struct blk *b = blk_at(f->blks, bi); + foreach_insn(i, b->insns) { + struct insn n = insn_at(b->insns, i); + if (n.type == PARAM) { + struct insn p = rewrite_param(n); + insn_at(b->insns, i) = p; + } + + else if (n.type == RETVAL) { + struct insn r = rewrite_retval(n); + insn_at(b->insns, i) = r; + } + + else if (n.type == ARG) { + struct insn a = rewrite_arg(n); + insn_at(b->insns, i) = a; + } + + else if (n.type == RETARG) { + struct insn a = rewrite_retarg(n); + insn_at(b->insns, i) = a; + } + } + } +} + diff --git a/src/asm.c b/src/asm.c new file mode 100644 index 0000000..eb0bead --- /dev/null +++ b/src/asm.c @@ -0,0 +1,277 @@ +#include +#include +#include +#include + +static const char *rname(struct val v) +{ + assert(v.class == REG); + /** @todo use ABI names? */ + switch (v.r) { + case RX0: return "x0"; + case RX1: return "x1"; + case RX2: return "x2"; + case RX3: return "x3"; + case RX4: return "x4"; + case RX5: return "x5"; + case RX6: return "x6"; + case RX7: return "x7"; + case RX8: return "x8"; + case RX9: return "x9"; + case RX10: return "x10"; + case RX11: return "x11"; + case RX12: return "x12"; + case RX13: return "x13"; + case RX14: return "x14"; + case RX15: return "x15"; + case RX16: return "x16"; + case RX17: return "x17"; + case RX18: return "x18"; + case RX19: return "x19"; + case RX20: return "x20"; + case RX21: return "x21"; + case RX22: return "x22"; + case RX23: return "x23"; + case RX24: return "x24"; + case RX25: return "x25"; + case RX26: return "x26"; + case RX27: return "x27"; + case RX28: return "x28"; + case RX29: return "x29"; + case RX30: return "x30"; + case RX31: return "x31"; + case RX32: return "x32"; + case RX33: return "x33"; + case RX34: return "x34"; + case RX35: return "x35"; + case RX36: return "x36"; + case RX37: return "x37"; + case RX38: return "x38"; + case RX39: return "x39"; + case RX40: return "x40"; + case RX41: return "x41"; + case RX42: return "x42"; + case RX43: return "x43"; + case RX44: return "x44"; + case RX45: return "x45"; + case RX46: return "x46"; + case RX47: return "x47"; + case RX48: return "x48"; + case RX49: return "x49"; + case RX50: return "x50"; + case RX51: return "x51"; + case RX52: return "x52"; + case RX53: return "x53"; + case RX54: return "x54"; + case RX55: return "x55"; + case RX56: return "x56"; + case RX57: return "x57"; + case RX58: return "x58"; + case RX59: return "x59"; + case RX60: return "x60"; + case RX61: return "x61"; + case RX62: return "x62"; + case RX63: return "x63"; + case RX64: return "x64"; + case RX65: return "x65"; + case RX66: return "x66"; + case RX67: return "x67"; + case RX68: return "x68"; + case RX69: return "x69"; + case RX70: return "x70"; + case RX71: return "x71"; + case RX72: return "x72"; + case RX73: return "x73"; + case RX74: return "x74"; + case RX75: return "x75"; + case RX76: return "x76"; + case RX77: return "x77"; + case RX78: return "x78"; + case RX79: return "x79"; + case RX80: return "x80"; + } + + assert(0 && "illegal register"); + abort(); +} + +static void save_state(struct fn *f, FILE *o) +{ + /* stack frame: + * last frame + * ra + * s0 + * ... + * local variables + * <- sp + */ + fprintf(o, "st w fp, -3(sp)\n"); + if (f->has_calls) + fprintf(o, "st w ra, -6(fp)\n"); + + fprintf(o, "mv fp, sp\n"); + fprintf(o, "addi sp, sp, -%zi\n", f->max_callee_save * 3 + 6); + + for (size_t i = 0; i < f->max_callee_save; ++i) { + fprintf(o, "st w s%zi, -%zi(fp)\n", + i, 3 * i + 9); + } +} + +static void restore_state(struct fn *f, FILE *o) +{ + for (size_t i = 0; i < f->max_callee_save; ++i) { + fprintf(o, "ld w s%zi, -%zi(fp)\n", + i, 3 * i + 9); + } + + if (f->has_calls) + fprintf(o, "ld w ra, -6(fp)\n"); + + fprintf(o, "ld w fp, -3(fp)\n"); + fprintf(o, "mv sp, fp\n"); +} + +static void output_move(struct insn n, FILE *o) +{ + fprintf(o, "mv %s, %s\n", + rname(n.out), rname(n.in[0])); +} + +static void output_add(struct insn n, FILE *o) +{ + if (n.in[1].class == REG) { + fprintf(o, "add %s, %s, %s\n", + rname(n.out), rname(n.in[0]), rname(n.in[1])); + return; + } + else if (n.in[1].class == IMM) { + /** @todo fix for values larger than what addi allows, mark one + * temporary register reserved for the compiler? */ + fprintf(o, "addi %s, %s, %lli\n", + rname(n.out), rname(n.in[0]), (long long int)n.in[1].v); + return; + } + + assert(0 && "illegal value type for add"); + abort(); +} + +static void output_sub(struct insn n, FILE *o) +{ + if (n.in[1].class == REG) { + fprintf(o, "sub %s, %s, %s\n", + rname(n.out), rname(n.in[0]), rname(n.in[1])); + return; + } + else if (n.in[1].class == IMM) { + if (n.in[1].v >= 0) + fprintf(o, "addi %s, %s, -%lli\n", + rname(n.out), rname(n.in[0]), (long long int)n.in[1].v); + else /* double negative */ + fprintf(o, "addi %s, %s, %lli\n", + rname(n.out), rname(n.in[0]), (long long int)n.in[1].v); + return; + } + + assert(0 && "illegal value type for sub"); + abort(); +} + +static void output_copy(struct insn n, FILE *o) +{ + fprintf(o, "li %s, %lli\n", + rname(n.out), (long long int)n.in[0].v); +} + +static void output_call(struct insn n, FILE *o) +{ + if (n.in[0].class == REF) { + fprintf(o, "call ra, %s\n", n.in[0].s); + return; + } + else if (n.in[0].class == REG) { + fprintf(o, "jalr ra, 0(%s)\n", rname(n.in[0])); + return; + } + + assert(0 && "illegal value type for call"); + abort(); +} + +static void output_insn(struct insn n, FILE *o) +{ + /* one insn directly matches one or more assembly instructions, + * we may be missing out on certain optimizations by not using some kind + * of matching here but good enough for now */ + switch (n.type) { + case MOVE: output_move(n, o); break; + case ADD: output_add(n, o); break; + case SUB: output_sub(n, o); break; + case COPY: output_copy(n, o); break; + case CALL: output_call(n, o); break; + default: fprintf(stderr, "unimplemented insn: %s\n", op_str(n.type)); + abort(); + } +} + +static void output_blt(struct blk *b, struct fn *f, FILE *o) +{ + assert(b->s2); + fprintf(o, "blt %s, %s, .%s.%lli\n", + rname(b->cmp[0]), rname(b->cmp[1]), + f->name, (long long int)b->s2->id); +} + +static void output_ble(struct blk *b, struct fn *f, FILE *o) +{ + assert(b->s2); + fprintf(o, "ble %s, %s, .%s.%lli\n", + rname(b->cmp[0]), rname(b->cmp[1]), + f->name, (long long int)b->s2->id); +} + +static void output_ret(struct fn *f, FILE *o) +{ + restore_state(f, o); + fprintf(o, "ret ra\n"); +} + +static void output_j(struct blk *b, struct fn *f, FILE *o) +{ + /* the jump is directly to a following block, no need to do anything */ + if (!b->to) + return; + + fprintf(o, "j .%s.%lli\n", f->name, (long long int)b->s1->id); +} + +static void output_branch(struct blk *b, struct fn *f, FILE *o) +{ + switch (b->btype) { + case RET: output_ret(f, o); break; + case J: output_j(b, f, o); break; + case BLT: output_blt(b, f, o); break; + case BLE: output_ble(b, f, o); break; + default: fprintf(stderr, "unimplemented branch: %s\n", op_str(b->btype)); + abort(); + } +} + +void output(struct fn *f, FILE *o) +{ + fprintf(o, "%s:\n", f->name); + save_state(f, o); + foreach_blk(bi, f->blks) { + struct blk *b = blk_at(f->blks, bi); + fprintf(o, ".%s.%lli:\n", + f->name, (long long int)b->id); + + foreach_insn(i, b->insns) { + struct insn n = insn_at(b->insns, i); + output_insn(n, o); + } + + output_branch(b, f, o); + } +} diff --git a/src/main.c b/src/main.c index a0eeb42..d6abb2d 100644 --- a/src/main.c +++ b/src/main.c @@ -4,6 +4,8 @@ #include #include +#include +#include #include static char *read_file(const char *file, FILE *f) @@ -56,6 +58,11 @@ int main(int argc, char *argv[]) foreach_fn(i, p->fns) { struct fn_map m = fn_at(p->fns, i); dump_function(m.fn); + // also handles things like register mapping etc. + optimize(m.fn); + dump_function(m.fn); + // for now + output(m.fn, stdout); } destroy_parser(p); diff --git a/src/nodes.c b/src/nodes.c index 9eb0113..4c5e97a 100644 --- a/src/nodes.c +++ b/src/nodes.c @@ -104,6 +104,8 @@ struct fn *new_function() f->blks = vec_create(sizeof(struct blk *)); f->tmps = vec_create(sizeof(struct tmp_map)); f->labels = vec_create(sizeof(struct label_map)); + f->has_calls = false; + f->max_callee_save = 0; /* empty block */ new_block(f); return f; @@ -134,15 +136,6 @@ void new_label(struct fn *f, struct blk *b, const char *name) vec_append(&f->labels, &(struct label_map){.id = name, .b = b}); } -static const char *op_str(enum insn_type n) { -#define CASE(I) case I: return #I; - switch (n) { - FOREACH_INSN_TYPE(CASE); - } -#undef CASE - return "unknown"; -} - void dump_val(struct val val) { long long r = val.r; long long v = val.v; @@ -160,7 +153,7 @@ void dump_val(struct val val) { void dump_insn(struct insn i) { - printf("\t"); + printf("//\t"); if (hasclass(i.out)) { dump_val(i.out); @@ -189,7 +182,7 @@ bool return_blk(struct blk *b) void dump_block(struct blk *b) { - printf("\t/*** block %lld ", (long long)b->id); + printf("//\t/*** block %lld ", (long long)b->id); if (b->name) printf("(%s) ", b->name); printf("***/\n"); @@ -199,20 +192,20 @@ void dump_block(struct blk *b) } if (return_blk(b)) { - printf("\n"); + printf("//\tRETURN\n"); return; } if (b->btype != J) { assert(b->s2); struct blk *s2 = b->s2; - printf("\t%s ", op_str(b->btype)); + printf("//\t%s ", op_str(b->btype)); dump_val(b->cmp[0]); printf(" "); dump_val(b->cmp[1]); printf(" -> %lli\n", (long long)s2->id); } - printf("\n"); + printf("//\n"); } void dump_function(struct fn *f) { diff --git a/src/opt.c b/src/opt.c new file mode 100644 index 0000000..3036950 --- /dev/null +++ b/src/opt.c @@ -0,0 +1,12 @@ +#include +#include +#include +#include + +void optimize(struct fn *f) +{ + ssa(f); + abi0(f); + /* ... do more stuff ... */ + regalloc(f); +} diff --git a/src/parser.y b/src/parser.y index 4a70341..4edcdcf 100644 --- a/src/parser.y +++ b/src/parser.y @@ -12,11 +12,6 @@ #include #include -struct ret_helper { - const char *r; - enum val_type t; -}; - %} %locations @@ -31,7 +26,6 @@ struct ret_helper { %union { struct val val; - struct ret_helper ret; enum val_type type; int64_t integer; char *str; @@ -77,8 +71,10 @@ struct ret_helper { %nterm type %nterm id addr local label -%nterm arg opt_arg -%nterm call_ret opt_call_ret +%nterm arg +%nterm ret + +%nterm placeholder %{ @@ -201,6 +197,22 @@ static inline void do_new_label(struct parser *p, const char *s) new_label(p->f, p->b, s); } +static inline size_t do_cur_insn(struct parser *p) +{ + return vec_len(&p->b->insns); +} + +static inline void do_ins_replace(struct parser *p, size_t i, struct insn n) +{ + insn_at(p->b->insns, i) = n; +} + +#define INS_REPLACE(i, n)\ + do_ins_replace(parser, i, n) + +#define CUR_INSN()\ + do_cur_insn(parser) + #define INSADD(o, t, r, a0, a1)\ do_insadd(parser, o, t, r, a0, a1) @@ -260,7 +272,7 @@ data param : type id { struct val t = IDALLOC($[id]); - INSADD(PARAM, $[type], t, imm_val(parser->idx++, I27), noclass()); + INSADD(PARAM, $[type], t, noclass(), imm_val(parser->idx++, I27)); } params @@ -272,17 +284,6 @@ opt_params : params | {} -ret - : type - -opt_ret - : ret - | {} - -/* only three return args permitted (keep things simple for now) */ -rets - : opt_ret "," opt_ret "," opt_ret - label : id ":" { if (empty_block(parser->b)) { @@ -299,7 +300,7 @@ arg $$ = IDTOVAL($[id]); } | type int { - $$ = imm_val($[type], $[int]); + $$ = imm_val($[int], $[type]); } arith @@ -439,14 +440,24 @@ branch NEW_BLOCK(J, noclass(), noclass(), $[local]); } +ret + : id { + $$ = IDALLOC($[id]); + } + call_ret - : type id { - $$ = (struct ret_helper){.r = $[id], .t = $[type]}; + : ret { + INSADD(RETVAL, NOTYPE, $[ret], noclass(), imm_val(parser->idx++, I27)); } -opt_call_ret - : call_ret - | { $$ = (struct ret_helper){.r = NULL, .t = NOTYPE}; } +call_rets + : call_ret "," call_rets + | call_ret "," + | call_ret + +opt_call_rets + : call_rets + | {} call_arg : arg { @@ -466,43 +477,43 @@ opt_call_args reset_index : {parser->idx = 0;} -call - : "(" opt_call_ret "," opt_call_ret "," opt_call_ret ")" - "=" addr reset_index "(" opt_call_args ")" { - /* call args should have inserted their own nodes */ - INSADD(CALL, NOTYPE, noclass(), imm_ref($[addr]), noclass()); - - if ($2.r) { - struct val t = IDALLOC($2.r); - INSADD(RETVAL, $2.t, t, noclass(), imm_val(0, I27)); - } - - if ($4.r) { - struct val t = IDALLOC($4.r); - INSADD(RETVAL, $4.t, t, noclass(), imm_val(1, I27)); - } - - if ($6.r) { - struct val t = IDALLOC($6.r); - INSADD(RETVAL, $6.t, t, noclass(), imm_val(2, I27)); - } +placeholder + : { + $$ = CUR_INSN(); + INSADD(CALL, NOTYPE, noclass(), noclass(), noclass()); } -opt_arg - : arg - | { $$ = noclass(); } - -return - : "=>" "(" opt_arg "," opt_arg "," opt_arg ")" { - if (!hasnoclass($3)) - INSADD(RET, NOTYPE, noclass(), $3, imm_val(0, I27)); +call + : addr reset_index "(" opt_call_args ")" + "=>" placeholder reset_index "(" opt_call_rets ")" { + /* kind of hacky but works */ + INS_REPLACE($[placeholder], + insn_create(CALL, NOTYPE, + noclass(), imm_ref($[addr]), noclass())); + } + | id reset_index "(" opt_call_args ")" + "=>" placeholder reset_index "(" opt_call_rets ")" { + INS_REPLACE($[placeholder], + insn_create(CALL, NOTYPE, + noclass(), IDTOVAL($[id]), noclass())); + } + +proc_ret + : id { + INSADD(RETARG, NOTYPE, noclass(), IDTOVAL($[id]), imm_val(parser->idx++, I27)); + } - if (!hasnoclass($5)) - INSADD(RET, NOTYPE, noclass(), $5, imm_val(1, I27)); +proc_rets + : proc_ret "," proc_rets + | proc_ret "," + | proc_ret - if (!hasnoclass($7)) - INSADD(RET, NOTYPE, noclass(), $7, imm_val(2, I27)); +opt_proc_rets + : proc_rets + | {} +return + : "=>" reset_index "(" opt_proc_rets ")" { NEW_BLOCK(RET, noclass(), noclass(), NULL); } @@ -524,8 +535,9 @@ body | label | insn ";" +/** @todo add in return type checking? */ function - : id reset_index "(" opt_params "=>" rets ")" "{" body "}" { + : id reset_index "(" opt_params ")" "{" body "}" { NEW_FUNCTION($[id]); } diff --git a/src/regalloc.c b/src/regalloc.c new file mode 100644 index 0000000..474e5a4 --- /dev/null +++ b/src/regalloc.c @@ -0,0 +1,90 @@ +#include + +#include +#include +#include + +static const int64_t tr_map[] = { + RS0, RS1, RS2, RS3, RS4, RS5, RS6, RS7, RS8, RS9, + RS10, RS11, RS12, RS13, RS14, RS15, RS16, RS17, RS18, RS19, + RS20, RS21, RS22, RS23, RS24 +}; + +#define reg_at(v, i)\ + vect_at(int64_t, v, i) + +static struct val rewrite_tmp(struct vec rmap, struct val t) +{ + assert(t.class == TMP); + assert(t.r < (int64_t)vec_len(&rmap)); + int64_t r = reg_at(rmap, t.r); + assert(r); + return reg_val(r); +} + +static size_t cur_reg = 0; +static void add_rewrite_rule(struct vec *rmap, struct val t) +{ + assert(t.class == TMP); + assert(cur_reg < 25 + && "ran out of temp registers, time to implement proper regalloc!"); + /* note <=, we go one 'beyond' just to make sure that 0 fits */ + while ((int64_t)vec_len(rmap) <= t.r) { + int64_t zero = 0; + vec_append(rmap, &zero); + } + + if (reg_at(*rmap, t.r) == 0) + reg_at(*rmap, t.r) = tr_map[cur_reg++]; +} + +void regalloc(struct fn *f) +{ + /* very ugly, fix once we get the proper regalloc implemented */ + cur_reg = 0; + struct vec rmap = vec_create(sizeof(int64_t)); + + /* here we would ideally do some kind of lifetime checking, to start + * with we only assign to different temporary registers, we have enough + * of them to work for some smaller test functions */ + /* lifetime info would probably also be useful for saving callee-save + * registers during calls, so that should probably also be done during + * register allocation? maybe? */ + foreach_blk(bi, f->blks) { + struct blk *b = blk_at(f->blks, bi); + foreach_insn(i, b->insns) { + struct insn n = insn_at(b->insns, i); + if (n.in[0].class == TMP) { + n.in[0] = rewrite_tmp(rmap, n.in[0]); + } + + if (n.in[1].class == TMP) { + n.in[1] = rewrite_tmp(rmap, n.in[1]); + } + + if (n.out.class == TMP) { + add_rewrite_rule(&rmap, n.out); + n.out = rewrite_tmp(rmap, n.out); + } + + /* write back changes */ + insn_at(b->insns, i) = n; + + /* do this here since the register allocation is the + * last stage before actually lowering to assembly, so + * no possibility of dead code elimination or stuff like + * that */ + if (n.type == CALL) + f->has_calls = true; + } + + if (b->cmp[0].class == TMP) + b->cmp[0] = rewrite_tmp(rmap, b->cmp[0]); + + if (b->cmp[1].class == TMP) + b->cmp[1] = rewrite_tmp(rmap, b->cmp[1]); + } + + f->max_callee_save = cur_reg; + vec_destroy(&rmap); +} diff --git a/src/ssa.c b/src/ssa.c new file mode 100644 index 0000000..a9d6e6c --- /dev/null +++ b/src/ssa.c @@ -0,0 +1,8 @@ +#include + +void ssa(struct fn *f) +{ + /* do a depth-first traversal of blocks, mark locations within as either + * generated (i.e. we assign something to the register) or required + * (i.e. it must be taken as a block parameter) */ +} -- cgit v1.3