From 9d07527b8b21d17bcd787ea962b650a56eac6b32 Mon Sep 17 00:00:00 2001 From: David Given Date: Fri, 20 Jan 2017 21:28:32 +0100 Subject: [PATCH] Keep track of which vregs need to be in real registers (i.e. are being used to do work) and which ones aren't (and so can be spilt). Do some long-needed cleanup and removal of dead code. --- mach/proto/mcg/mcg.h | 3 +- mach/proto/mcg/pass_prologueepilogue.c | 52 +++++----- mach/proto/mcg/pass_registerallocator.c | 17 +++- mach/proto/mcg/pass_spillibility.c | 43 ++++++++ mach/proto/mcg/pass_splitliveranges.c | 125 ------------------------ mach/proto/mcg/pass_vregusage.c | 66 ------------- mach/proto/mcg/procedure.c | 4 +- mach/proto/mcg/reg.h | 1 + 8 files changed, 84 insertions(+), 227 deletions(-) create mode 100644 mach/proto/mcg/pass_spillibility.c delete mode 100644 mach/proto/mcg/pass_splitliveranges.c delete mode 100644 mach/proto/mcg/pass_vregusage.c diff --git a/mach/proto/mcg/mcg.h b/mach/proto/mcg/mcg.h index 19f259018..692127e6d 100644 --- a/mach/proto/mcg/mcg.h +++ b/mach/proto/mcg/mcg.h @@ -108,11 +108,11 @@ extern void tb_procedure(void); extern void tb_regvar(struct procedure* proc, arith offset, int size, int type, int priority); extern void pass_assign_vregs(void); +extern void pass_calculate_vreg_spillibility(void); extern void pass_convert_inputs_to_phis(void); extern void pass_convert_locals_to_ssa(void); extern void pass_convert_nonlocal_phis(void); extern void pass_convert_stack_ops(void); -extern void pass_determine_vreg_usage(void); extern void pass_eliminate_trivial_blocks(void); extern void pass_find_phi_congruence_groups(void); extern void pass_group_irs(void); @@ -125,7 +125,6 @@ extern void pass_register_allocator(void); extern void pass_remove_dead_blocks(void); extern void pass_remove_dead_phis(void); extern void pass_split_critical_edges(void); -extern void pass_split_live_ranges(void); extern void pass_wire_up_return_values(void); extern void platform_calculate_offsets(void); diff --git a/mach/proto/mcg/pass_prologueepilogue.c b/mach/proto/mcg/pass_prologueepilogue.c index 3b0c517cb..30e452d01 100644 --- a/mach/proto/mcg/pass_prologueepilogue.c +++ b/mach/proto/mcg/pass_prologueepilogue.c @@ -4,32 +4,32 @@ void pass_add_prologue_epilogue(void) { int i, j, k; - current_proc->usedregs.count = 0; - for (i=0; ihops.count; j++) - { - struct hop* hop = bb->hops.item[j]; - - for (k=0; kregsin.count; k++) - { - struct hreg* hreg = hop->regsin.item[k].left; - if (!hreg->is_stacked) - array_appendu(¤t_proc->usedregs, hreg); - } - - for (k=0; kregsout.count; k++) - { - struct hreg* hreg = hop->regsout.item[k].left; - if (!hreg->is_stacked) - array_appendu(¤t_proc->usedregs, hreg); - } - } - } - - platform_calculate_offsets(); + // current_proc->usedregs.count = 0; + // for (i=0; ihops.count; j++) + // { + // struct hop* hop = bb->hops.item[j]; + + // for (k=0; kregsin.count; k++) + // { + // struct hreg* hreg = hop->regsin.item[k].left; + // if (!hreg->is_stacked) + // array_appendu(¤t_proc->usedregs, hreg); + // } + + // for (k=0; kregsout.count; k++) + // { + // struct hreg* hreg = hop->regsout.item[k].left; + // if (!hreg->is_stacked) + // array_appendu(¤t_proc->usedregs, hreg); + // } + // } + // } + + // platform_calculate_offsets(); array_insert(¤t_proc->entry->hops, platform_prologue(), 0); diff --git a/mach/proto/mcg/pass_registerallocator.c b/mach/proto/mcg/pass_registerallocator.c index 1c435e9e5..05f48e303 100644 --- a/mach/proto/mcg/pass_registerallocator.c +++ b/mach/proto/mcg/pass_registerallocator.c @@ -8,7 +8,7 @@ * http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.5924 */ -static const int DEGREE = 10; +static const int DEGREE = 5; static struct graph interference; static struct graph affinity; @@ -89,6 +89,8 @@ static void generate_graph(void) static void dump_vreg(struct vreg* vreg) { fprintf(regalloc_dot_file, "[%%%d]", vreg->id); + if (!vreg->needs_register) + fprintf(regalloc_dot_file, "S"); } static void dump_interference_graph(void) @@ -176,7 +178,7 @@ static bool attempt_to_coalesce(void) if (degree > DEGREE) return false; - tracef('R', "R: lowest degree affinity edge: %%%d->%%%d, degree %d\n", + tracef('R', "R: coalescing affinity edge: %%%d->%%%d, degree %d\n", v1->id, v2->id, degree); coalesce(v1, v2); @@ -189,6 +191,11 @@ static bool attempt_to_coalesce(void) return true; } +static bool attempt_to_simplify(void) +{ + return false; +} + static void iterate(void) { struct anode* spill; @@ -201,8 +208,8 @@ static void iterate(void) if (attempt_to_coalesce()) continue; - // if (attempt_to_simplify()) - // continue; + if (attempt_to_simplify()) + continue; // if (attempt_to_spill_or_simplify()) // continue; @@ -216,7 +223,7 @@ void pass_register_allocator(void) wire_together_bbs(); generate_graph(); - iterate(); + //iterate(); dump_interference_graph(); diff --git a/mach/proto/mcg/pass_spillibility.c b/mach/proto/mcg/pass_spillibility.c new file mode 100644 index 000000000..f434dc099 --- /dev/null +++ b/mach/proto/mcg/pass_spillibility.c @@ -0,0 +1,43 @@ +#include "mcg.h" + +static struct basicblock* current_bb; + +static void calculate_spillibility(void) +{ + int i; + + for (i=0; ihops.count; i++) + { + struct hop* hop = current_bb->hops.item[i]; + if (!hop->is_move) + { + struct hashtable_iterator hit = {}; + while (hashtable_next(hop->valueusage, &hit)) + { + struct value* value = hit.key; + struct valueusage* usage = hit.value; + + if (!usage->through) + { + if (usage->invreg) + usage->invreg->needs_register = true; + if (usage->outvreg) + usage->outvreg->needs_register = true; + } + } + } + } +} + +void pass_calculate_vreg_spillibility(void) +{ + int i; + + for (i=0; ihops.count) - { - struct hop* hop = bb->hops.item[pos]; - - array_replace(&hop->ins, src, dest); - array_replace(&hop->throughs, src, dest); - array_replace(&hop->outs, src, dest); - - for (i=0; iinsels.count; i++) - { - struct insel* insel = hop->insels.item[i]; - if ((insel->type == INSEL_VREG) && (insel->u.vreg == src)) - insel->u.vreg = dest; - } - - for (i=0; iconstraints.count; i++) - { - struct constraint* c = hop->constraints.item[i].right; - - if (hop->constraints.item[i].left == src) - hop->constraints.item[i].left = dest; - - if (c->equals_to == src) - c->equals_to = dest; - } - - pos++; - } - - for (i=0; inexts.count; i++) - { - struct basicblock* nextbb = bb->nexts.item[i]; - - for (j=0; jphis.count; j++) - { - struct phi* phi = nextbb->phis.item[j].right; - if (phi->ir->result == src) - phi->ir->result = dest; - } - } -} - -static void rewrite_blocks(struct basicblock* startbb, int startindex, - struct vreg* src, struct vreg* dest) -{ - int i; - - for (i=0; itype = src->type; - copy = new_copy_hop(current_bb, src, dest); - - array_insert(¤t_bb->hops, copy, index+1); - - rewrite_blocks(current_bb, index+2, src, dest); - return 1; -} - -void pass_split_live_ranges(void) -{ - int i, j, k; - - for (i=0; ihops.count; j++) - { - struct hop* hop = current_bb->hops.item[j]; - - if (!hop->is_move) - { - for (k=0; kins.count; k++) - { - struct vreg* vreg = hop->ins.item[k]; - j += insert_move_after(j-1, vreg); - } - - for (k=0; kouts.count; k++) - { - struct vreg* vreg = hop->outs.item[k]; - insert_move_after(j, vreg); - } - - for (k=0; kins.count; k++) - { - struct vreg* vreg = hop->ins.item[k]; - j += insert_move_after(j, vreg); - } - } - } - } -} - -/* vim: set sw=4 ts=4 expandtab : */ \ No newline at end of file diff --git a/mach/proto/mcg/pass_vregusage.c b/mach/proto/mcg/pass_vregusage.c deleted file mode 100644 index e8d400f13..000000000 --- a/mach/proto/mcg/pass_vregusage.c +++ /dev/null @@ -1,66 +0,0 @@ -#include "mcg.h" - -static struct set vregs; - -static void assign_uses_cb(struct hop* hop, void* user) -{ - int i; - - for (i=0; iins.count; i++) - array_appendu(&hop->ins.item[i]->usedhops, hop); - - for (i=0; iouts.count; i++) - { - struct vreg* vreg = hop->outs.item[i]; - assert(vreg->defined == NULL); - vreg->defined = hop; - set_add(&vregs, vreg); - } -} - -static bool is_spillable_vreg(struct vreg* vreg) -{ - int i; - - if (vreg->defined && !vreg->defined->is_move) - return false; - - for (i=0; iusedhops.count; i++) - if (!vreg->usedhops.item[i]->is_move) - return false; - - return true; -} - -void pass_determine_vreg_usage(void) -{ - int i, j; - - set_empty(&vregs); - hop_walk(assign_uses_cb, NULL); - - for (i=0; iphis.count; j++) - { - struct vreg* dest = bb->phis.item[j].left; - struct phi* phi = bb->phis.item[j].right; - struct vreg* src = phi->ir->result; - array_appendu(&src->usedphis, bb); - set_add(&vregs, src); - set_add(&vregs, dest); - } - } - - { - struct set_iterator sit = {}; - while (set_next(&vregs, &sit)) - { - struct vreg* vreg = sit.item; - vreg->is_spillable = is_spillable_vreg(vreg); - } - } -} - -/* vim: set sw=4 ts=4 expandtab : */ diff --git a/mach/proto/mcg/procedure.c b/mach/proto/mcg/procedure.c index cb9ba62b9..82160727d 100644 --- a/mach/proto/mcg/procedure.c +++ b/mach/proto/mcg/procedure.c @@ -222,12 +222,10 @@ void procedure_compile(struct procedure* proc) pass_live_value_analysis(); print_hops('8'); pass_assign_vregs(); + pass_calculate_vreg_spillibility(); print_hops('9'); pass_register_allocator(); #if 0 - pass_split_live_ranges(); - pass_determine_vreg_usage(); - pass_add_prologue_epilogue(); print_hops('9'); diff --git a/mach/proto/mcg/reg.h b/mach/proto/mcg/reg.h index 63c23b307..d8e4053e1 100644 --- a/mach/proto/mcg/reg.h +++ b/mach/proto/mcg/reg.h @@ -18,6 +18,7 @@ struct vreg int id; struct value* value; struct vreg* coalesced_with; + bool needs_register; }; extern struct hreg* new_hreg(const struct burm_register_data* brd); -- 2.34.1