From fd5bdaff40f93546009e1ec854fd26df01e78f22 Mon Sep 17 00:00:00 2001 From: Kimplul Date: Tue, 30 Apr 2024 15:25:17 +0300 Subject: correct addr + Doesn't quite implement stack handling fully as of yet, but slowly getting there --- include/qbt/nodes.h | 2 +- include/qbt/opt.h | 2 +- src/correct.c | 97 +++++++++++++++++++++++++++++++++++++-- src/opt.c | 10 ++-- src/parser.y | 6 ++- src/ssa.c | 7 +-- tests/1.qbt | 19 -------- tests/2.qbt | 4 -- tests/3.qbt | 13 ------ tests/4.qbt | 18 -------- tests/5.qbt | 5 -- tests/addr.qbt | 7 +++ tests/empty.qbt | 4 ++ tests/hello_world.qbt | 18 ++++++++ tests/simple_args.qbt | 19 ++++++++ tests/simple_external_putchar.qbt | 5 ++ tests/simple_loop.qbt | 13 ++++++ 17 files changed, 174 insertions(+), 75 deletions(-) delete mode 100644 tests/1.qbt delete mode 100644 tests/2.qbt delete mode 100644 tests/3.qbt delete mode 100644 tests/4.qbt delete mode 100644 tests/5.qbt create mode 100644 tests/addr.qbt create mode 100644 tests/empty.qbt create mode 100644 tests/hello_world.qbt create mode 100644 tests/simple_args.qbt create mode 100644 tests/simple_external_putchar.qbt create mode 100644 tests/simple_loop.qbt diff --git a/include/qbt/nodes.h b/include/qbt/nodes.h index f51a32f..a81f397 100644 --- a/include/qbt/nodes.h +++ b/include/qbt/nodes.h @@ -45,11 +45,11 @@ enum insn_type { RETARG, PARAM, RETVAL, + ADDR, /* internal */ SAVE, RESTORE, - ADDR, }; enum insn_flags { diff --git a/include/qbt/opt.h b/include/qbt/opt.h index 60d29b3..87c8ac6 100644 --- a/include/qbt/opt.h +++ b/include/qbt/opt.h @@ -4,6 +4,6 @@ #include void optimize(struct fn *fn); size_t ssa(struct fn *f); -void correct(struct fn *f, size_t ri); +size_t correct(struct fn *f, size_t ri); #endif /* OPT_H */ diff --git a/src/correct.c b/src/correct.c index 8c0b249..6e99e3f 100644 --- a/src/correct.c +++ b/src/correct.c @@ -1,3 +1,4 @@ +#include #include static size_t spill_ref(struct blk *b, size_t ii, struct insn i, size_t idx, @@ -76,8 +77,89 @@ static size_t correct_store(struct blk *b, size_t ii, struct insn i, size_t ri) return ri; } -static size_t correct_insn(struct blk *b, size_t ii, struct insn i, size_t ri) +static void add_rewrite_rule(struct vec *rmap, struct val from, struct val to) { + assert(from.class == TMP); + assert(to.class == TMP); + + while ((int64_t)vec_len(rmap) <= from.r) { + struct val no = noclass(); + vec_append(rmap, &no); + } + + val_at(*rmap, from.r) = to; +} + +static bool has_rewrite_rule(struct vec *rmap, struct val t) +{ + if (t.r >= (int64_t)vec_len(rmap)) + return false; + + struct val r = val_at(*rmap, t.r); + return r.class != NOCLASS; +} + +static struct val rewrite_tmp(struct vec *rmap, struct val t) +{ + assert(t.class == TMP); + assert(t.r < (int64_t)vec_len(rmap)); + struct val r = val_at(*rmap, t.r); + assert(r.class != NOCLASS); + return r; +} + +static size_t correct_addr(struct blk *b, struct vec *rewrite_addrs, size_t ii, struct insn i, size_t ri) +{ + if (i.in[0].class == TMP) { + /** @todo this messes with the rest of the corrections, as the + * store with the tmp is rewritten to load t1 first, overwriting + * t0 */ + /* addr could potentially be defined to move the register into + * the location it's specifying? Not a particularly clean + * solution but I guess it could work? */ + add_rewrite_rule(rewrite_addrs, i.in[0], i.out); + return ri; + } + + return ri; +} + +static size_t load_rewrite(struct blk *b, struct vec *rewrite_addrs, size_t ii, struct insn i, size_t ri, size_t idx) +{ + struct val addr = rewrite_tmp(rewrite_addrs, i.in[idx]); + struct val tmp = tmp_val(ri++); + struct insn new = insn_create(LOAD, I27, tmp, addr, noclass(), 0); + i.in[idx] = tmp; + insn_at(b->insns, ii) = i; + insn_insert(b, new, ii); + return ri; +} + +static size_t store_rewrite(struct blk *b, struct vec *rewrite_addrs, size_t ii, struct insn i, size_t ri) +{ + struct val addr = rewrite_tmp(rewrite_addrs, i.out); + struct val tmp = tmp_val(ri++); + struct insn new = insn_create(STORE, I27, tmp, addr, noclass(), 0); + i.out = tmp; + insn_at(b->insns, ii) = i; + insn_insert(b, new, ii + 1); + return ri; +} + +static size_t correct_insn(struct blk *b, struct vec *rewrite_addrs, size_t ii, struct insn i, size_t ri) +{ + /* replace registers referencing rewritten addr */ + if (i.in[0].class == TMP && has_rewrite_rule(rewrite_addrs, i.in[0])) + return load_rewrite(b, rewrite_addrs, ii, i, ri, 0); + + if (i.in[1].class == TMP && has_rewrite_rule(rewrite_addrs, i.in[1])) + return load_rewrite(b, rewrite_addrs, ii, i, ri, 1); + + if (i.out.class == TMP && has_rewrite_rule(rewrite_addrs, i.out)) { + /* note no return */ + store_rewrite(b, rewrite_addrs, ii, i, ri); + } + /* replace references with instructions */ if (i.type != CALL && i.in[0].class == REF) return spill_ref(b, ii, i, 0, ri); @@ -120,22 +202,28 @@ static size_t correct_insn(struct blk *b, size_t ii, struct insn i, size_t ri) case STORE: return correct_store(b, ii, i, ri); + case ADDR: + return correct_addr(b, rewrite_addrs, ii, i, ri); + default: } return ri; } -void correct(struct fn *f, size_t ri) +size_t 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. */ + + struct vec rewrite_addrs = vec_create(sizeof(struct val)); + 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); + ri = correct_insn(b, &rewrite_addrs, ii, i, ri); } if (b->cmp[0].class == IMM) { @@ -150,4 +238,7 @@ void correct(struct fn *f, size_t ri) b->cmp[1] = t; } } + + vec_destroy(&rewrite_addrs); + return ri; } diff --git a/src/opt.c b/src/opt.c index dac19a6..426663a 100644 --- a/src/opt.c +++ b/src/opt.c @@ -9,13 +9,13 @@ void optimize(struct fn *f) printf("\n// initial:\n"); dump_function(f); - /* unreachability is done in several steps I guess */ - size_t ri = ssa(f); - printf("\n// after SSA:\n"); + f->ntmp = correct(f, f->ntmp); + printf("\n// corrections:\n"); dump_function(f); - correct(f, ri); - printf("\n// corrections:\n"); + /* unreachability is done in several steps I guess */ + ssa(f); + printf("\n// after SSA:\n"); dump_function(f); abi0(f); diff --git a/src/parser.y b/src/parser.y index b4c0035..dd744c0 100644 --- a/src/parser.y +++ b/src/parser.y @@ -381,7 +381,11 @@ stack struct val t = IDALLOC($[id]); INSADD(ALLOC, $[type], t, noclass(), noclass(), $[int]); } - + | type id "=" "^" id { + struct val t = IDALLOC($2); + struct val f = IDTOVAL($5); + INSADD(ADDR, $[type], t, f, noclass(), 0); + } | "^" "^" int { INSADD(DEALLOC, NOTYPE, noclass(), noclass(), noclass(), $[int]); } diff --git a/src/ssa.c b/src/ssa.c index 4283dae..186d6b5 100644 --- a/src/ssa.c +++ b/src/ssa.c @@ -151,9 +151,6 @@ static void collect_params(struct blk *b, int visited) } } -#define tmpval_at(rmap, i) \ - vect_at(struct val, rmap, i) - static void add_rewrite_rule(struct vec *rmap, struct val from, struct val to) { assert(from.class == TMP); @@ -164,14 +161,14 @@ static void add_rewrite_rule(struct vec *rmap, struct val from, struct val to) vec_append(rmap, &no); } - tmpval_at(*rmap, from.r) = to; + val_at(*rmap, from.r) = to; } static struct val rewrite_tmp(struct vec *rmap, struct val from) { assert(from.class == TMP); assert(from.r <= (int64_t)vec_len(rmap)); - struct val v = tmpval_at(*rmap, from.r); + struct val v = val_at(*rmap, from.r); assert(v.class == TMP); return v; } diff --git a/tests/1.qbt b/tests/1.qbt deleted file mode 100644 index e87fddc..0000000 --- a/tests/1.qbt +++ /dev/null @@ -1,19 +0,0 @@ -do_stuff (i27 a0, i27 a1) -{ - i27 r0 = a0 + a1; - i27 r1 = a0 - a1; - => (r0, r1); -} - -/* this is a function of some kind */ -main (i27 a0, i27 a1) -{ - i27 r0 = a0 + a1; - /* r0 is reassigned */ - &do_stuff (r0, i9 29) => (r0, r1); - r0 < r1 -> somewhere_else; - => (r1); - - somewhere_else: - => (r0); -} diff --git a/tests/2.qbt b/tests/2.qbt deleted file mode 100644 index 9c63342..0000000 --- a/tests/2.qbt +++ /dev/null @@ -1,4 +0,0 @@ -main() -{ - => (); -} diff --git a/tests/3.qbt b/tests/3.qbt deleted file mode 100644 index 7c54e0f..0000000 --- a/tests/3.qbt +++ /dev/null @@ -1,13 +0,0 @@ -main() -{ - i27 i = 0; - i27 max = 1000000000; - i27 sum = 0; - -top: - i27 sum = sum + i; - i27 i = i + 1; - i < max -> top; - &_putchar(i9 sum) => (); - => (); -} diff --git a/tests/4.qbt b/tests/4.qbt deleted file mode 100644 index 0a5734a..0000000 --- a/tests/4.qbt +++ /dev/null @@ -1,18 +0,0 @@ -main() -{ - &_putchar (i9 'H') => (); - &_putchar (i9 'e') => (); - &_putchar (i9 'l') => (); - &_putchar (i9 'l') => (); - &_putchar (i9 'o') => (); - &_putchar (i9 ',') => (); - &_putchar (i9 ' ') => (); - &_putchar (i9 'W') => (); - &_putchar (i9 'o') => (); - &_putchar (i9 'r') => (); - &_putchar (i9 'l') => (); - &_putchar (i9 'd') => (); - &_putchar (i9 '!') => (); - &_putchar (i9 '\n') => (); - => (); -} diff --git a/tests/5.qbt b/tests/5.qbt deleted file mode 100644 index 213592e..0000000 --- a/tests/5.qbt +++ /dev/null @@ -1,5 +0,0 @@ -main() -{ - &_putchar(i9 'H') => (); - => (); -} diff --git a/tests/addr.qbt b/tests/addr.qbt new file mode 100644 index 0000000..efe149c --- /dev/null +++ b/tests/addr.qbt @@ -0,0 +1,7 @@ +main () +{ + i27 r0 = 1; + i27 r1 = ^r0; + i27 r0 = r0 + r0; + => (r0); +} diff --git a/tests/empty.qbt b/tests/empty.qbt new file mode 100644 index 0000000..9c63342 --- /dev/null +++ b/tests/empty.qbt @@ -0,0 +1,4 @@ +main() +{ + => (); +} diff --git a/tests/hello_world.qbt b/tests/hello_world.qbt new file mode 100644 index 0000000..8419208 --- /dev/null +++ b/tests/hello_world.qbt @@ -0,0 +1,18 @@ +main() +{ + &_putchar ('H') => (); + &_putchar ('e') => (); + &_putchar ('l') => (); + &_putchar ('l') => (); + &_putchar ('o') => (); + &_putchar (',') => (); + &_putchar (' ') => (); + &_putchar ('W') => (); + &_putchar ('o') => (); + &_putchar ('r') => (); + &_putchar ('l') => (); + &_putchar ('d') => (); + &_putchar ('!') => (); + &_putchar ('\n') => (); + => (); +} diff --git a/tests/simple_args.qbt b/tests/simple_args.qbt new file mode 100644 index 0000000..5dcb3d8 --- /dev/null +++ b/tests/simple_args.qbt @@ -0,0 +1,19 @@ +do_stuff (i27 a0, i27 a1) +{ + i27 r0 = a0 + a1; + i27 r1 = a0 - a1; + => (r0, r1); +} + +/* this is a function of some kind */ +main (i27 a0, i27 a1) +{ + i27 r0 = a0 + a1; + /* r0 is reassigned */ + &do_stuff (r0, 29) => (r0, r1); + r0 < r1 -> somewhere_else; + => (r1); + + somewhere_else: + => (r0); +} diff --git a/tests/simple_external_putchar.qbt b/tests/simple_external_putchar.qbt new file mode 100644 index 0000000..b76844c --- /dev/null +++ b/tests/simple_external_putchar.qbt @@ -0,0 +1,5 @@ +main() +{ + &_putchar('H') => (); + => (); +} diff --git a/tests/simple_loop.qbt b/tests/simple_loop.qbt new file mode 100644 index 0000000..32e544f --- /dev/null +++ b/tests/simple_loop.qbt @@ -0,0 +1,13 @@ +main() +{ + i27 i = 0; + i27 max = 1000; + i27 sum = 0; + +top: + i27 sum = sum + i; + i27 i = i + 1; + i < max -> top; + &_putchar(sum) => (); + => (); +} -- cgit v1.3