From 0f8532d4e7315b86e160abf4ced461e7678b5587 Mon Sep 17 00:00:00 2001 From: Kimplul Date: Sun, 7 Apr 2024 01:29:12 +0300 Subject: add features that make machine generation easier --- src/abi.c | 4 ++ src/asm.c | 85 +++++++++++++++++++++++++++++++++-- src/correct.c | 138 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/nodes.c | 2 - src/opt.c | 7 ++- src/parser.y | 34 ++++++++------ src/regalloc.c | 26 ++++++----- src/ssa.c | 5 ++- src/vec.c | 2 +- 9 files changed, 269 insertions(+), 34 deletions(-) create mode 100644 src/correct.c (limited to 'src') diff --git a/src/abi.c b/src/abi.c index fede365..a16ef2d 100644 --- a/src/abi.c +++ b/src/abi.c @@ -102,6 +102,10 @@ void abi0(struct fn *f) struct insn a = rewrite_retarg(n); insn_at(b->insns, i) = a; } + else if (n.type == CALL) { + set_insn_flags(&n, CALL_SETUP | CALL_TEARDOWN); + insn_at(b->insns, i) = n; + } } } } diff --git a/src/asm.c b/src/asm.c index 7eac389..e4b65cc 100644 --- a/src/asm.c +++ b/src/asm.c @@ -152,12 +152,14 @@ static void restore_state(struct fn *f, FILE *o) if (f->has_calls) fprintf(o, "ld w ra, -%zi(fp)\n", ra_fploc()); - fprintf(o, "ld w fp, -%zi(fp)\n", fp_fploc()); fprintf(o, "mv sp, fp\n"); + fprintf(o, "ld w fp, -%zi(fp)\n", fp_fploc()); } static void output_move(struct insn n, FILE *o) { + /** @todo should this also handle casts or would it make more sense to + * add an insn specifically for that? */ if (!same_val(n.out, n.in[0])) fprintf(o, "mv %s, %s\n", rname(n.out), rname(n.in[0])); @@ -244,17 +246,69 @@ static void output_restore(struct insn n, FILE *o, struct fn *f) rname(r), call_save_fploc(f, i)); } +static void output_store(struct insn n, FILE *o) +{ + struct val offset = n.out; + struct val b = n.in[0]; + struct val t = n.in[1]; + + assert(offset.class == IMM); + assert(b.class == REG); + assert(t.class == REG); + + char width = 'w'; + if (n.vtype == I9) + width = 't'; + + int64_t off = offset.v; + fprintf(o, "st %c %s, %lli(%s)\n", + width, rname(t), (long long int)off, rname(b)); +} + +static void output_load(struct insn n, FILE *o) +{ + struct val t = n.out; + struct val b = n.in[0]; + struct val offset = n.in[1]; + + assert(offset.class == IMM); + assert(b.class == REG); + assert(t.class == REG); + + char width = 'w'; + if (n.vtype == I9) + width = 't'; + + int64_t off = offset.v; + fprintf(o, "ld %c %s, %lli(%s)\n", + width, rname(t), (long long int)off, rname(b)); +} + +static void output_lt(struct insn i, FILE *o) +{ + assert(i.type == LT); + if (i.in[1].class == IMM) + fprintf(o, "slti %s, %s, %lli\n", + rname(i.out), rname(i.in[0]), (long long)i.in[1].v); + else + fprintf(o, "slt %s, %s, %s\n", + rname(i.out), rname(i.in[0]), rname(i.in[1])); +} + static void output_insn(struct insn n, FILE *o, struct fn *f) { /* 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 LT: output_lt(n, o); break; 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; + case STORE: output_store(n, o); break; + case LOAD: output_load(n, o); break; case SAVE: output_save(n, o, f); break; case RESTORE: output_restore(n, o, f); break; default: fprintf(stderr, "unimplemented insn: %s\n", op_str(n.type)); @@ -275,7 +329,29 @@ 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); + f->name, (long long)b->s2->id); +} + +static void output_bne(struct blk *b, struct fn *f, FILE *o) +{ + assert(b->s2); + fprintf(o, "bne %s, %s, .%s.%lli\n", + rname(b->cmp[0]), rname(b->cmp[1]), + f->name, (long long)b->s2->id); +} + +static void output_bnz(struct blk *b, struct fn *f, FILE *o) +{ + assert(b->s2); + fprintf(o, "bne %s, x0, .%s.%lli\n", + rname(b->cmp[0]), f->name, (long long)b->s2->id); +} + +static void output_bez(struct blk *b, struct fn *f, FILE *o) +{ + assert(b->s2); + fprintf(o, "beq %s, x0, .%s.%lli\n", + rname(b->cmp[0]), f->name, (long long)b->s2->id); } static void output_ret(struct fn *f, FILE *o) @@ -290,7 +366,7 @@ static void output_j(struct blk *b, struct fn *f, FILE *o) if (!b->to || b->s1 == b->s2) return; - fprintf(o, "j .%s.%lli\n", f->name, (long long int)b->s2->id); + fprintf(o, "jal x0, .%s.%lli\n", f->name, (long long int)b->s2->id); } static void output_branch(struct blk *b, struct fn *f, FILE *o) @@ -300,6 +376,9 @@ static void output_branch(struct blk *b, struct fn *f, FILE *o) case J: output_j(b, f, o); break; case BLT: output_blt(b, f, o); break; case BLE: output_ble(b, f, o); break; + case BNE: output_bne(b, f, o); break; + case BNZ: output_bnz(b, f, o); break; + case BEZ: output_bez(b, f, o); break; default: fprintf(stderr, "unimplemented branch: %s\n", op_str(b->btype)); abort(); diff --git a/src/correct.c b/src/correct.c new file mode 100644 index 0000000..2654218 --- /dev/null +++ b/src/correct.c @@ -0,0 +1,138 @@ +#include + +static size_t spill_ref(struct blk *b, size_t ii, struct insn i, size_t idx, size_t ri) +{ + struct val tmp = tmp_val(ri++); + struct insn new = insn_create(ADDR, I27, tmp, i.in[idx], noclass()); + i.in[idx] = tmp; + insn_at(b->insns, ii) = i; + insn_insert(b, new, ii); + return ri; +} + +static size_t spill_imm(struct blk *b, size_t ii, struct insn i, size_t idx, size_t ri) +{ + struct val tmp = tmp_val(ri++); + struct insn new = insn_create(COPY, I27, tmp, i.in[idx], noclass()); + i.in[idx] = tmp; + insn_at(b->insns, ii) = i; + insn_insert(b, new, ii); + return ri; +} + +static size_t correct_arith(struct blk *b, size_t ii, struct insn i, size_t ri) +{ + if (i.in[0].class == IMM) { + /* swap so that immediates are 'outermost' */ + struct val tmp = i.in[0]; + i.in[0] = i.in[1]; + i.in[1] = tmp; + insn_at(b->insns, ii) = i; + return ri; + } + + if (i.in[0].class == IMM) + return spill_imm(b, ii, i, 0, ri); + + return ri; +} + +static size_t correct_positional_arith(struct blk *b, size_t ii, struct insn i, size_t ri) +{ + if (i.in[0].class == IMM) + return spill_imm(b, ii, i, 0, ri); + + return ri; +} + +static size_t correct_branch(struct blk *b, size_t ii, struct insn i, size_t ri) +{ + if (i.in[0].class == IMM) + return spill_imm(b, ii, i, 0, ri); + + if (i.in[1].class == IMM) + return spill_imm(b, ii, i, 1, ri); + + return ri; +} + +static size_t correct_relations(struct blk *b, size_t ii, struct insn i, size_t ri) +{ + if (i.in[0].class == IMM) + return spill_imm(b, ii, i, 0, ri); + + return ri; +} + +static size_t correct_insn(struct blk *b, size_t ii, struct insn i, size_t ri) +{ + /* replace references with instructions */ + if (i.type != CALL && i.in[0].class == REF) + return spill_ref(b, ii, i, 0, ri); + + if (i.in[1].class == REF) + return spill_ref(b, ii, i, 1, ri); + + switch (i.type) { + case ADD: + case MUL: + return correct_arith(b, ii, i, ri); + + case SUB: + case DIV: + case REM: + case LSHIFT: + case RSHIFT: + return correct_positional_arith(b, ii, i, ri); + + case BEQ: + case BNE: + case BLE: + case BGE: + case BLT: + case BGT: + case BNZ: + case BEZ: + /* oh wait, this never triggers because branches are at the end + * of blocks, duh */ + return correct_branch(b, ii, i, ri); + + case LT: + case LE: + case GT: + case GE: + case EQ: + case NE: + return correct_relations(b, ii, i, ri); + + default: + } + + return ri; +} + +void correct(struct fn *f, size_t ri) +{ + /* some simpler corrections to make sure all instructions follow a + * specific pattern. The textual version doesn't have these + * restrictions, but they make our lives easier in the future. */ + foreach_blk(bi, f->blks) { + struct blk *b = blk_at(f->blks, bi); + foreach_insn(ii, b->insns) { + struct insn i = insn_at(b->insns, ii); + ri = correct_insn(b, ii, i, ri); + } + + if (b->cmp[0].class == IMM) { + struct val t = tmp_val(ri++); + insadd(b, COPY, I27, t, b->cmp[0], noclass()); + b->cmp[0] = t; + } + + if (b->cmp[1].class == IMM) { + struct val t = tmp_val(ri++); + insadd(b, COPY, I27, t, b->cmp[0], noclass()); + b->cmp[1] = t; + } + } +} diff --git a/src/nodes.c b/src/nodes.c index d5a22da..22fc454 100644 --- a/src/nodes.c +++ b/src/nodes.c @@ -107,8 +107,6 @@ void finish_function(struct fn *f, const char *name) } b->s2 = m.b; - if (b->btype == J) - b->s1 = b->s2; } } diff --git a/src/opt.c b/src/opt.c index 882587d..dac19a6 100644 --- a/src/opt.c +++ b/src/opt.c @@ -2,7 +2,6 @@ #include #include -#include #include void optimize(struct fn *f) @@ -11,10 +10,14 @@ void optimize(struct fn *f) dump_function(f); /* unreachability is done in several steps I guess */ - ssa(f); + size_t ri = ssa(f); printf("\n// after SSA:\n"); dump_function(f); + correct(f, ri); + printf("\n// corrections:\n"); + dump_function(f); + abi0(f); printf("\n// after abi0:\n"); dump_function(f); diff --git a/src/parser.y b/src/parser.y index ec133eb..bda8f31 100644 --- a/src/parser.y +++ b/src/parser.y @@ -64,7 +64,6 @@ %token LEXI9 "i9" %token LEXI27 "i27" -%nterm mem_loc %nterm mem_base %nterm mem_off %nterm int @@ -262,8 +261,7 @@ type | "i27" { $$ = I27; } const - : "i9" int - | "i27" int + : int consts : const "," consts @@ -307,8 +305,8 @@ arg : id { $$ = IDTOVAL($[id]); } - | type int { - $$ = imm_val($[int], $[type]); + | int { + $$ = imm_val($[int], NOTYPE); } arith @@ -359,17 +357,19 @@ mem_base mem_off : int -mem_loc - : "(" mem_base mem_off ")" {$$ = mem_val(IDTOVAL($[mem_base]).r, $[mem_off]);} - mem - : type id "<<" mem_loc { - struct val t = IDALLOC($[id]); - INSADD(LOAD, $[type], t, $[mem_loc], noclass()); + : type id "<<" mem_base mem_off { + struct val t = IDTOVAL($[id]); + struct val b = IDTOVAL($[mem_base]); + struct val o = imm_val($[mem_off], I27); + INSADD(LOAD, $[type], t, b, o); } - | id ">>" type mem_loc { - struct val t = IDALLOC($[id]); - INSADD(STORE, $[type], noclass(), t, $[mem_loc]); + | id ">>" type mem_base mem_off { + struct val t = IDTOVAL($[id]); + struct val b = IDTOVAL($[mem_base]); + struct val o = imm_val($[mem_off], I27); + /* really not a huge fan or 'reusing' the output slot... */ + INSADD(STORE, $[type], o, b, t); } stack @@ -444,6 +444,12 @@ branch | arg ">" arg "->" local { NEW_BLOCK(BGT, $1, $3, $[local]); } + | arg "->" local { + NEW_BLOCK(BNZ, $[arg], noclass(), $[local]); + } + | "!" arg "->" local { + NEW_BLOCK(BEZ, $[arg], noclass(), $[local]); + } | "->" local { NEW_BLOCK(J, noclass(), noclass(), $[local]); } diff --git a/src/regalloc.c b/src/regalloc.c index ffefeb5..9c4d87e 100644 --- a/src/regalloc.c +++ b/src/regalloc.c @@ -387,35 +387,33 @@ static bool callee_save(struct val r) return false; } -static void insn_insert_before_call(struct blk *b, struct insn save, size_t pos) +static void insn_insert_before_call(struct blk *b, struct insn save, ssize_t pos) { assert((insn_at(b->insns, pos)).type == CALL); struct insn setup; do { - /* the first instruction in a block can be part of a call setup */ - if (pos == 0) + if (pos < 0) break; - pos--; setup = insn_at(b->insns, pos); + pos--; } while (has_insn_flag(setup, CALL_SETUP)); - /* the do-while loop technically went one too far, fix */ - insn_insert(b, save, pos == 0 ? 0 : pos + 1); + insn_insert(b, save, pos + 1); } static void insn_insert_after_call(struct blk *b, struct insn restore, size_t pos) { assert((insn_at(b->insns, pos)).type == CALL); - size_t max = vec_len(&b->insns) - 1; + size_t max = vec_len(&b->insns); struct insn setup; do { if (pos == max) break; - pos++; setup = insn_at(b->insns, pos); + pos++; } while (has_insn_flag(setup, CALL_TEARDOWN)); insn_insert(b, restore, pos); @@ -497,14 +495,22 @@ void regalloc(struct fn *f) struct blk *b = blk_at(f->blks, bi); vec_reset(&lifetimes); vec_reset(&calls); + /** @todo collect hints from args/params */ collect_lifetimes(b, &hints, &lifetimes, &rmap, &calls); - f->max_callee_save = build_rmap(&hints, &lifetimes, &rmap); + size_t max_callee_save = build_rmap(&hints, &lifetimes, &rmap); + do_rewrites(b, &rmap); - f->max_call_save = do_call_saves(b, &lifetimes, &rmap, &calls); + size_t max_call_save = do_call_saves(b, &lifetimes, &rmap, &calls); /** @todo forward_hints(b, &hints, &rmap) */ if (vec_len(&calls) != 0) f->has_calls = true; + + if (max_callee_save > f->max_callee_save) + f->max_callee_save = max_callee_save; + + if (max_call_save > f->max_call_save) + f->max_call_save = max_call_save; } vec_destroy(&calls); diff --git a/src/ssa.c b/src/ssa.c index 96d1eb1..997f078 100644 --- a/src/ssa.c +++ b/src/ssa.c @@ -1,5 +1,4 @@ #include -#include #include static void add_val(struct vec *map, struct val v) @@ -221,7 +220,7 @@ static size_t rename_temps(struct blk *b, size_t i) return i; } -void ssa(struct fn *f) +size_t 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 @@ -236,4 +235,6 @@ void ssa(struct fn *f) struct blk *b = blk_at(f->blks, bi); i = rename_temps(b, i); } + + return i; } diff --git a/src/vec.c b/src/vec.c index 7fb314e..344518b 100644 --- a/src/vec.c +++ b/src/vec.c @@ -58,7 +58,7 @@ void vec_insert(struct vec *v, void *n, size_t i) { assert(i <= vec_len(v)); if (i == vec_len(v)) - vec_append(v, n); + return vec_append(v, n); v->n++; if (v->n >= v->s) { -- cgit v1.3