From 67443867c2743eda27be650b58f5021004789a45 Mon Sep 17 00:00:00 2001 From: Kimplul Date: Thu, 27 Jun 2024 19:17:50 +0300 Subject: allow compiling some massive functions --- src/parser.y | 27 +++++++++++---- src/regalloc.c | 48 ++++++++++++++++++++++----- src/ssa.c | 101 +++++++++++++++++++++++++++++++++++++++++++++------------ 3 files changed, 142 insertions(+), 34 deletions(-) (limited to 'src') diff --git a/src/parser.y b/src/parser.y index dd744c0..f41948f 100644 --- a/src/parser.y +++ b/src/parser.y @@ -516,12 +516,18 @@ call INS_REPLACE($[placeholder], insn_create(CALL, NOTYPE, noclass(), imm_ref($[addr]), noclass(), 0)); + + /* make some optimization phases easier by splitting each call + * into a separate block */ + NEW_BLOCK(J, noclass(), noclass(), NULL); } | id reset_index "(" opt_call_args ")" "=>" placeholder reset_index "(" opt_call_rets ")" { INS_REPLACE($[placeholder], insn_create(CALL, NOTYPE, noclass(), IDTOVAL($[id]), noclass(), 0)); + + NEW_BLOCK(J, noclass(), noclass(), NULL); } proc_ret @@ -555,15 +561,24 @@ insn | call | return -body - : insn ";" body - | label body +labels + : labels label | label - | insn ";" + +body + : body ";" labels insn + | body ";" insn + | labels insn + | labels + | insn + +body_opt_term + : body + | body ";" /** @todo add in return type checking? */ function - : id reset_index "(" opt_params ")" "{" body "}" { + : id reset_index "(" opt_params ")" "{" body_opt_term "}" { NEW_FUNCTION($[id]); } @@ -572,7 +587,7 @@ top | function unit - : top unit + : unit top | top | error { parser->failed = true; diff --git a/src/regalloc.c b/src/regalloc.c index cd21f5e..6265c6d 100644 --- a/src/regalloc.c +++ b/src/regalloc.c @@ -175,10 +175,26 @@ static void collect_lifetimes(struct blk *b, struct vec *hints, } } -static void build_active_between(struct vec *active, struct vec *lifetimes, - size_t start, size_t end) +static void build_active_between(struct vec *active, struct vec *prev_active, struct vec *lifetimes, + size_t i, size_t start, size_t end) { - foreach_lifetime(li, *lifetimes) { + /* we really only need to look at previously active lifetimes and check + * which ones are still active, no need to iterate all the way from the + * start. Only works if prev_active is really the previous lifetime in + * the lifetimes vector */ + if (prev_active) + foreach_lifetime(li, *prev_active) { + struct lifetime l = lifetime_at(*lifetimes, li); + if (l.end <= start) + continue; + + if (l.start >= end) + break; + + vec_append(active, &l); + } + + for (size_t li = i; li < vec_len(lifetimes); ++li) { struct lifetime l = lifetime_at(*lifetimes, li); if (l.used == 0) continue; @@ -188,17 +204,20 @@ static void build_active_between(struct vec *active, struct vec *lifetimes, if (l.end <= start) continue; + /* since lifetimes must be strictly ascending by start value, we + * know that no other lifetimes can possibly be active after + * this point */ if (l.start >= end) - continue; + break; vec_append(active, &l); } } -static void build_active(struct vec *active, struct vec *lifetimes, size_t i) +static void build_active(struct vec *active, struct vec *prev_active, struct vec *lifetimes, size_t i) { struct lifetime ref = lifetime_at(*lifetimes, i); - build_active_between(active, lifetimes, ref.start, ref.end); + build_active_between(active, prev_active, lifetimes, i, ref.start, ref.end); } static void build_reserved(struct vec *reserved, struct vec *active, @@ -279,10 +298,18 @@ static size_t highest_sreg(struct val f) return 0; } +static void swap_lifetimes(struct vec *a, struct vec *b) +{ + struct vec tmp = *a; + *a = *b; + *b = tmp; +} + static size_t build_rmap(struct vec *hints, struct vec *lifetimes, struct vec *rmap) { size_t max_callee_save = 0; + struct vec prev_active = vec_create(sizeof(struct lifetime)); struct vec active = vec_create(sizeof(struct lifetime)); struct vec reserved = vec_create(sizeof(struct val)); @@ -296,7 +323,7 @@ static size_t build_rmap(struct vec *hints, struct vec *lifetimes, vec_reset(&active); vec_reset(&reserved); - build_active(&active, lifetimes, li); + build_active(&active, &prev_active, lifetimes, li); build_reserved(&reserved, &active, rmap); struct val h = get_hint(hints, l.v); @@ -315,10 +342,15 @@ static size_t build_rmap(struct vec *hints, struct vec *lifetimes, max_callee_save = highest_sreg(f); add_rewrite_rule(rmap, l.v, f); + + /* store currently active in prev_active */ + swap_lifetimes(&active, &prev_active); + vec_reset(&active); } vec_destroy(&active); vec_destroy(&reserved); + vec_destroy(&prev_active); return max_callee_save; } @@ -457,7 +489,7 @@ static size_t do_call_saves(struct blk *b, struct vec *lifetimes, vec_reset(&active); vec_reset(&reserved); - build_active_between(&active, lifetimes, call_pos, call_pos); + build_active_between(&active, NULL, lifetimes, 0, call_pos, call_pos); build_reserved(&reserved, &active, rmap); /* what follows is a slight bit of index counting, a bit diff --git a/src/ssa.c b/src/ssa.c index 186d6b5..87bf453 100644 --- a/src/ssa.c +++ b/src/ssa.c @@ -34,24 +34,65 @@ static bool has_val(struct vec *map, struct val v) return p.class != NOCLASS; } +static bool entered(struct blk *b, int visited) +{ + return b->visited >= visited + 1; +} + +static void enter(struct blk *b) +{ + b->visited++; +} + +static bool done(struct blk *b, int visited) +{ + return b->visited >= visited + 2; +} + +static void leave(struct blk *b) +{ + b->visited++; +} + static void build_params(struct blk *b, int visited) { - if (b->visited > visited) + if (done(b, visited)) return; - b->visited++; + /* recursive functionality made iterative by using an external + * stack, just think of pushing to the stack as doing a recursive call + * */ + struct vec stack = vec_create(sizeof(struct blk *)); + vec_append(&stack, &b); +top: + if (vec_len(&stack) == 0) { + vec_destroy(&stack); + return; + } + + b = vect_pop(struct blk *, stack); if (return_blk(b)) { b->s1 = NULL; b->s2 = NULL; } - if (b->s1) - build_params(b->s1, visited); + /* this is the first time here, queue up work for us */ + if (!entered(b, visited)) { + /* put ourselves back onto the stack */ + vec_append(&stack, &b); + + if (b->s1) + vec_append(&stack, &b->s1); + if (b->s2) + vec_append(&stack, &b->s2); - if (b->s2) - build_params(b->s2, visited); + enter(b); + goto top; + } + /* second time through, do actual work now that dependencies (should) be + * done */ struct vec generated = vec_create(sizeof(struct val)); struct vec forward = vec_create(sizeof(struct val)); struct vec required = vec_create(sizeof(struct val)); @@ -125,30 +166,50 @@ static void build_params(struct blk *b, int visited) vec_destroy(&required); vec_destroy(&forward); vec_destroy(&generated); + leave(b); // mark us ready + goto top; } static void collect_params(struct blk *b, int visited) { - if (b->visited > visited) + if (done(b, visited)) return; - b->visited++; + struct vec stack = vec_create(sizeof(struct blk *)); + vec_append(&stack, &b); - 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); - } +top: + if (vec_len(&stack) == 0) { + vec_destroy(&stack); + return; } - 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); - } + b = vect_pop(struct blk *, stack); + if (!entered(b, visited)) { + vec_append(&stack, &b); + + if (b->s1) + vec_append(&stack, &b->s1); + + if (b->s2) + vec_append(&stack, &b->s2); + + enter(b); + goto top; } + + foreach_blk_param(pi, b->s1->params) { + struct val p = blk_param_at(b->s1->params, pi); + vec_append(&b->args1, &p); + } + + foreach_blk_param(pi, b->s2->params) { + struct val p = blk_param_at(b->s2->params, pi); + vec_append(&b->args2, &p); + } + + leave(b); + goto top; } static void add_rewrite_rule(struct vec *rmap, struct val from, struct val to) -- cgit v1.3