diff options
| -rw-r--r-- | include/qbt/nodes.h | 2 | ||||
| -rw-r--r-- | include/qbt/opt.h | 2 | ||||
| -rw-r--r-- | src/correct.c | 97 | ||||
| -rw-r--r-- | src/opt.c | 10 | ||||
| -rw-r--r-- | src/parser.y | 6 | ||||
| -rw-r--r-- | src/ssa.c | 7 | ||||
| -rw-r--r-- | tests/4.qbt | 18 | ||||
| -rw-r--r-- | tests/5.qbt | 5 | ||||
| -rw-r--r-- | tests/addr.qbt | 7 | ||||
| -rw-r--r-- | tests/empty.qbt (renamed from tests/2.qbt) | 0 | ||||
| -rw-r--r-- | tests/hello_world.qbt | 18 | ||||
| -rw-r--r-- | tests/simple_args.qbt (renamed from tests/1.qbt) | 2 | ||||
| -rw-r--r-- | tests/simple_external_putchar.qbt | 5 | ||||
| -rw-r--r-- | tests/simple_loop.qbt (renamed from tests/3.qbt) | 4 |
14 files changed, 141 insertions, 42 deletions
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 <qbt/nodes.h> 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 <assert.h> #include <qbt/opt.h> 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; } @@ -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]); } @@ -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/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/2.qbt b/tests/empty.qbt index 9c63342..9c63342 100644 --- a/tests/2.qbt +++ b/tests/empty.qbt 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/1.qbt b/tests/simple_args.qbt index e87fddc..5dcb3d8 100644 --- a/tests/1.qbt +++ b/tests/simple_args.qbt @@ -10,7 +10,7 @@ main (i27 a0, i27 a1) { i27 r0 = a0 + a1; /* r0 is reassigned */ - &do_stuff (r0, i9 29) => (r0, r1); + &do_stuff (r0, 29) => (r0, r1); r0 < r1 -> somewhere_else; => (r1); 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/3.qbt b/tests/simple_loop.qbt index 7c54e0f..32e544f 100644 --- a/tests/3.qbt +++ b/tests/simple_loop.qbt @@ -1,13 +1,13 @@ main() { i27 i = 0; - i27 max = 1000000000; + i27 max = 1000; i27 sum = 0; top: i27 sum = sum + i; i27 i = i + 1; i < max -> top; - &_putchar(i9 sum) => (); + &_putchar(sum) => (); => (); } |