diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/main.c | 2 | ||||
| -rw-r--r-- | src/nodes.c | 48 | ||||
| -rw-r--r-- | src/opt.c | 16 | ||||
| -rw-r--r-- | src/parser.y | 10 | ||||
| -rw-r--r-- | src/ssa.c | 231 | ||||
| -rw-r--r-- | src/unreachable.c | 34 |
6 files changed, 296 insertions, 45 deletions
@@ -57,10 +57,8 @@ 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); } diff --git a/src/nodes.c b/src/nodes.c index 294b531..a6ff0b8 100644 --- a/src/nodes.c +++ b/src/nodes.c @@ -48,8 +48,11 @@ struct blk *new_block(struct fn *f) { struct blk *b = calloc(1, sizeof(struct blk)); b->id = ++f->nblk; - b->reachable = false; + b->visited = 0; b->insns = vec_create(sizeof(struct insn)); + b->params = vec_create(sizeof(struct val)); + b->args1 = vec_create(sizeof(struct val)); + b->args2 = vec_create(sizeof(struct val)); vec_append(&f->blks, &b); return b; } @@ -102,6 +105,8 @@ void finish_function(struct fn *f, const char *name) } b->s2 = m.b; + if (b->btype == J) + b->s1 = b->s2; } } @@ -136,6 +141,7 @@ void destroy_function(struct fn *f) void destroy_block(struct blk *b) { vec_destroy(&b->insns); + vec_destroy(&b->params); free(b); } @@ -191,7 +197,16 @@ bool return_blk(struct blk *b) void dump_block(struct blk *b) { printf("//\t/*** block %lld ", (long long)b->id); - if (b->name) printf("(%s) ", b->name); + if (b->name) printf("\"%s\" ", b->name); + + printf("("); + foreach_blk_param(pi, b->params) { + struct val v = blk_param_at(b->params, pi); + dump_val(v); + printf(", "); + } + printf(") "); + printf("***/\n"); foreach_insn(i, b->insns) { @@ -204,20 +219,29 @@ void dump_block(struct blk *b) return; } - if (b->btype != J) { - assert(b->s2); - struct blk *s2 = b->s2; - 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); + assert(b->s2); + struct blk *s2 = b->s2; + printf("//\t%s ", op_str(b->btype)); + dump_val(b->cmp[0]); + printf(" "); + dump_val(b->cmp[1]); + printf(" -> %lli (", (long long)s2->id); + foreach_blk_param(pi, b->args2) { + struct val a = blk_param_at(b->args2, pi); + dump_val(a); + printf(", "); + } + printf("), else %lli (", (long long)b->s1->id); + foreach_blk_param(pi, b->args1) { + struct val a = blk_param_at(b->args1, pi); + dump_val(a); + printf(", "); } - printf("//\n"); + printf(")\n"); } void dump_function(struct fn *f) { - printf("/*** function %s ***/\n", f->name); + printf("//\t/*** function %s ***/\n", f->name); foreach_blk(i, f->blks) { struct blk *b = blk_at(f->blks, i); dump_block(b); @@ -1,14 +1,26 @@ +#include <stdio.h> + #include <qbt/opt.h> #include <qbt/regalloc.h> -#include <qbt/unreachable.h> #include <qbt/ssa.h> #include <qbt/abi.h> void optimize(struct fn *f) { + printf("\n// initial:\n"); + dump_function(f); + + /* unreachability is done in several steps I guess */ ssa(f); + printf("\n// after SSA:\n"); + dump_function(f); + abi0(f); + printf("\n// after abi0:\n"); + dump_function(f); + /* ... do more stuff ... */ - unreachable(f); regalloc(f); + printf("\n// after regalloc:\n"); + dump_function(f); } diff --git a/src/parser.y b/src/parser.y index 4edcdcf..ec133eb 100644 --- a/src/parser.y +++ b/src/parser.y @@ -157,7 +157,15 @@ static inline void do_new_block(struct parser *p, const char *label) { finish_block(p->b, type, a0, a1, label); - p->b = p->b->s1 = new_block(p->f); + struct blk *b = new_block(p->f); + + if (p->b->btype == RET) + p->b = b; + /* kind of a special case, a jump to the direct next block */ + else if (p->b->btype == J && label == NULL) + p->b = p->b->s1 = p->b->s2 = b; + else + p->b = p->b->s1 = b; } static inline void do_insadd(struct parser *p, @@ -1,8 +1,239 @@ +#include <assert.h> #include <qbt/ssa.h> +#include <qbt/unreachable.h> + +static void add_val(struct vec *map, struct val v) +{ + assert(v.class == TMP); + size_t i = v.r; + while (vec_len(map) <= i) { + struct val no = noclass(); + vec_append(map, &no); + } + + blk_param_at(*map, i) = v; +} + +static void remove_val(struct vec *map, struct val v) +{ + assert(v.class == TMP); + size_t i = v.r; + if (vec_len(map) <= i) + return; + + blk_param_at(*map, i) = noclass(); +} + +static bool has_val(struct vec *map, struct val v) +{ + assert(v.class == TMP); + size_t i = v.r; + if (vec_len(map) <= i) + return false; + + struct val p = blk_param_at(*map, i); + return p.class != NOCLASS; +} + +static void build_params(struct blk *b, int visited) +{ + if (b->visited > visited) + return; + + b->visited++; + + if (b->s1) + build_params(b->s1, visited); + + if (b->s2) + build_params(b->s2, visited); + + struct vec generated = vec_create(sizeof(struct val)); + struct vec forward = vec_create(sizeof(struct val)); + struct vec required = vec_create(sizeof(struct val)); + + /* first, collect all forwards */ + if (b->s1) { + foreach_blk_param(pi, b->s1->params) { + struct val p = blk_param_at(b->s1->params, pi); + add_val(&forward, p); + } + } + + if (b->s2) { + foreach_blk_param(pi, b->s2->params) { + struct val p = blk_param_at(b->s2->params, pi); + add_val(&forward, p); + } + } + + /* go through each instruction and add inputs to required and outputs to + * generated */ + foreach_insn(ii, b->insns) { + struct insn i = insn_at(b->insns, ii); + struct val in1 = i.in[0]; + if (in1.class == TMP && !has_val(&generated, in1)) + add_val(&required, in1); + + struct val in2 = i.in[1]; + if (in2.class == TMP && !has_val(&generated, in2)) + add_val(&required, in2); + + struct val out = i.out; + if (out.class == TMP) { + add_val(&generated, out); + /* we generate this value so no need to forward it */ + if (has_val(&forward, out)) + remove_val(&forward, out); + } + } + + if (b->cmp[0].class == TMP && !has_val(&generated, b->cmp[0])) + add_val(&required, b->cmp[0]); + + if (b->cmp[1].class == TMP && !has_val(&generated, b->cmp[1])) + add_val(&required, b->cmp[1]); + + /* add values that need forwarding to our required list */ + foreach_blk_param(pi, forward) { + /* if value already is in list, don't do anything */ + struct val p = blk_param_at(forward, pi); + + /* skip empty slots */ + if (p.class == NOCLASS) + continue; + + if (has_val(&forward, p)) + continue; + + add_val(&required, p); + } + + /* convert from the hashmap-like structure to regular vector */ + foreach_blk_param(pi, required) { + struct val p = blk_param_at(required, pi); + if (p.class == NOCLASS) + continue; + + vec_append(&b->params, &p); + } + + vec_destroy(&required); + vec_destroy(&forward); + vec_destroy(&generated); +} + +static void collect_params(struct blk *b, int visited) +{ + if (b->visited > visited) + return; + + b->visited++; + + if (b->s1) { + collect_params(b->s1, visited); + foreach_blk_param(pi, b->s1->params) { + struct val p = blk_param_at(b->s1->params, pi); + vec_append(&b->args1, &p); + } + } + + if (b->s2) { + collect_params(b->s2, visited); + foreach_blk_param(pi, b->s2->params) { + struct val p = blk_param_at(b->s2->params, pi); + vec_append(&b->args2, &p); + } + } +} + +#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); + assert(to.class == TMP); + + while ((int64_t)vec_len(rmap) <= from.r) { + struct val no = noclass(); + vec_append(rmap, &no); + } + + tmpval_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); + assert(v.class == TMP); + return v; +} + +static size_t rename_temps(struct blk *b, size_t i) +{ + struct vec rmap = vec_create(sizeof(struct val)); + + foreach_blk_param(pi, b->params) { + struct val p = blk_param_at(b->params, pi); + /* this is very similar to what's going on in regalloc.c, hmm */ + add_rewrite_rule(&rmap, p, tmp_val(i++)); + blk_param_at(b->params, pi) = rewrite_tmp(&rmap, p); + } + + foreach_insn(ii, b->insns) { + struct insn n = insn_at(b->insns, ii); + + 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, tmp_val(i++)); + n.out = rewrite_tmp(&rmap, n.out); + } + + insn_at(b->insns, ii) = n; + } + + 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]); + + foreach_blk_param(pi, b->args1) { + struct val p = blk_param_at(b->args1, pi); + blk_param_at(b->args1, pi) = rewrite_tmp(&rmap, p); + } + + foreach_blk_param(pi, b->args2) { + struct val p = blk_param_at(b->args2, pi); + blk_param_at(b->args2, pi) = rewrite_tmp(&rmap, p); + } + + vec_destroy(&rmap); + + return i; +} 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) */ + struct blk *b = blk_at(f->blks, 0); + build_params(b, b->visited); + remove_unvisited(f, b->visited); + collect_params(b, b->visited); + + size_t i = 0; + foreach_blk(bi, f->blks) { + struct blk *b = blk_at(f->blks, bi); + i = rename_temps(b, i); + } } diff --git a/src/unreachable.c b/src/unreachable.c index 90a65bd..aa04f46 100644 --- a/src/unreachable.c +++ b/src/unreachable.c @@ -1,38 +1,16 @@ #include <qbt/unreachable.h> -void build_reachable_vec(struct vec *reachable, struct blk *cur) +void remove_unvisited(struct fn *f, int visited) { - if (cur->reachable) - return; - - cur->reachable = true; - vec_append(reachable, &cur); - - if (cur->btype == RET) - return; - - if (cur->btype == J) - cur->s1 = cur->s2; - - if (cur->s1) - build_reachable_vec(reachable, cur->s1); - - if (cur->s2) - build_reachable_vec(reachable, cur->s2); -} - -void unreachable(struct fn *f) -{ - struct vec reachable = vec_create(sizeof(struct blk *)); - struct blk *b = blk_at(f->blks, 0); - build_reachable_vec(&reachable, b); + struct vec new = vec_create(sizeof(struct blk *)); foreach_blk(bi, f->blks) { struct blk *b = blk_at(f->blks, bi); - if (!b->reachable) + if (b->visited < visited) destroy_block(b); - + else + vec_append(&new, &b); } vec_destroy(&f->blks); - f->blks = reachable; + f->blks = new; } |