From 5fea247f139ade8183b1ba19eafb2512139ce37d Mon Sep 17 00:00:00 2001 From: David Given Date: Thu, 26 Jan 2017 23:52:41 +0100 Subject: [PATCH] Vreg usage is now stored separately to value usage, because we may want the same vreg to be used in multiple ways (usually when copying vreg X->Y and X->Z in the same move operation). --- mach/proto/mcg/hop.c | 148 +++++++++++++++++------- mach/proto/mcg/hop.h | 8 +- mach/proto/mcg/pass_assignvregs.c | 40 +++++-- mach/proto/mcg/pass_copiestomoves.c | 23 ++-- mach/proto/mcg/pass_registerallocator.c | 53 +++++---- mach/proto/mcg/pass_spillibility.c | 23 ++-- 6 files changed, 194 insertions(+), 101 deletions(-) diff --git a/mach/proto/mcg/hop.c b/mach/proto/mcg/hop.c index d4884f7a7..b14e09345 100644 --- a/mach/proto/mcg/hop.c +++ b/mach/proto/mcg/hop.c @@ -46,6 +46,69 @@ struct valueusage* hop_get_value_usage(struct hop* hop, struct value* value) return usage; } +void hop_add_input_vreg(struct hop* hop, struct vreg* vreg) +{ + if (!pmap_findleft(&hop->vregusage, vreg)) + pmap_add(&hop->vregusage, vreg, NULL); +} + +void hop_add_output_vreg(struct hop* hop, struct vreg* vreg) +{ + assert(!pmap_findright(&hop->vregusage, vreg)); + pmap_add(&hop->vregusage, NULL, vreg); +} + +void hop_add_through_vreg(struct hop* hop, struct vreg* src, struct vreg* dest) +{ + int i; + + for (i=0; ivregusage.count; i++) + { + struct vreg* candidatesrc = hop->vregusage.item[i].left; + struct vreg* candidatedest = hop->vregusage.item[i].right; + if ((candidatesrc == src) && !candidatedest) + { + hop->vregusage.item[i].right = dest; + return; + } + if (!candidatesrc && (candidatedest == dest)) + { + hop->vregusage.item[i].left = src; + return; + } + } + + pmap_add(&hop->vregusage, src, dest); +} + +struct vreg* hop_find_input_vreg(struct hop* hop, struct value* value) +{ + int i; + + for (i=0; ivregusage.count; i++) + { + struct vreg* vreg = hop->vregusage.item[i].left; + if (vreg && value_comparison_function(vreg->value, value)) + return vreg; + } + + return NULL; +} + +struct vreg* hop_find_output_vreg(struct hop* hop, struct value* value) +{ + int i; + + for (i=0; ivregusage.count; i++) + { + struct vreg* vreg = hop->vregusage.item[i].right; + if (vreg && value_comparison_function(vreg->value, value)) + return vreg; + } + + return NULL; +} + void hop_add_move(struct hop* hop, struct value* src, struct value* dest) { struct valueusage* usage; @@ -255,38 +318,12 @@ static struct vreg* actual(struct vreg* vreg) void appendvreg(struct vreg* vreg) { - appendf("%%%d", vreg->id); + appendf("($%d:%d=%%%d", vreg->value->ir->id, vreg->value->subid, vreg->id); if (vreg->hreg != -1) - appendf("=%d", vreg->hreg); + appendf("=R%d", vreg->hreg); if (vreg->is_spilt) appendf("S"); -} - -void appendvalue(struct hop* hop, struct value* value) -{ - struct valueusage* usage = hop_get_value_usage(hop, value); - struct vreg* vreg = NULL; - - if (usage->input && usage->output && usage->invreg && usage->outvreg) - { - appendf("%%%d->%%%d", usage->invreg->id, usage->outvreg->id); - return; - } - - if (usage->input) - vreg = usage->invreg; - if (usage->output) - vreg = usage->outvreg; - if (usage->through) - { - assert(usage->invreg == usage->outvreg); - vreg = usage->invreg; - } - - if (vreg) - appendvreg(actual(vreg)); - else - appendf("$%d:%d", value->ir->id, value->subid); + appendf(")"); } static void appendheader(struct hop* hop) @@ -300,6 +337,7 @@ static void appendheader(struct hop* hop) appendf(" from $%d", hop->ir->id); appendf(":"); + appendf(" VALUES:"); { struct hashtable_iterator hit = {}; while (hashtable_next(hop->valueusage, &hit)) @@ -318,12 +356,26 @@ static void appendheader(struct hop* hop) appendf("="); if (usage->corrupted) appendf("!"); - appendvalue(hop, value); + appendf("$%d:%d", value->ir->id, value->subid); } } } - appendf(" "); + appendf(" VREGS:"); + for (i=0; ivregusage.count; i++) + { + struct vreg* src = hop->vregusage.item[i].left; + struct vreg* dest = hop->vregusage.item[i].right; + + appendf(" "); + if (src) + appendvreg(src); + appendf("->"); + if (dest) + appendvreg(dest); + } + + appendf(" INSN: "); } char* hop_render(struct hop* hop) @@ -336,21 +388,20 @@ char* hop_render(struct hop* hop) if (hop->is_move) { - struct hashtable_iterator hit = {}; appendf("@move:"); - while (hashtable_next(hop->valueusage, &hit)) + + for (i=0; ivregusage.count; i++) { - struct valueusage* usage = hit.value; - struct vreg* invreg = actual(usage->invreg); - struct vreg* outvreg = actual(usage->outvreg); - if (usage->input && usage->output && (invreg == outvreg)) + struct vreg* invreg = actual(hop->vregusage.item[i].left); + struct vreg* outvreg = actual(hop->vregusage.item[i].right); + if ((invreg == outvreg) || !invreg || !outvreg) continue; appendf(" "); - if (usage->input && invreg) + if (invreg) appendvreg(invreg); appendf("->"); - if (usage->output && outvreg) + if (outvreg) appendvreg(outvreg); } appendf("\n"); @@ -379,9 +430,22 @@ char* hop_render(struct hop* hop) case INSEL_VREG: { - appendvalue(hop, insel->u.value); - if (insel->index) - appendf(".%d", insel->index); + struct value* value = insel->u.value; + struct valueusage* usage = hop_get_value_usage(hop, value); + struct vreg* vreg = NULL; + if (usage->input) + vreg = hop_find_input_vreg(hop, value); + else if (usage->output) + vreg = hop_find_output_vreg(hop, value); + + if (vreg) + appendvreg(actual(vreg)); + else + { + appendf("$%d:%d", value->ir->id, value->subid); + if (insel->index) + appendf(".%d", insel->index); + } break; } diff --git a/mach/proto/mcg/hop.h b/mach/proto/mcg/hop.h index cff607165..15ca8f45b 100644 --- a/mach/proto/mcg/hop.h +++ b/mach/proto/mcg/hop.h @@ -30,8 +30,6 @@ struct insel struct valueusage { - struct vreg* invreg; - struct vreg* outvreg; bool input : 1; bool output : 1; bool through : 1; @@ -50,12 +48,18 @@ struct hop PMAPOF(struct value, struct value) equals_constraint; struct hashtable* valueusage; + PMAPOF(struct vreg, struct vreg) vregusage; }; extern struct hop* new_hop(struct basicblock* bb, struct ir* ir); extern struct hop* new_move_hop(struct basicblock* bb); extern struct valueusage* hop_get_value_usage(struct hop* hop, struct value* value); +extern void hop_add_input_vreg(struct hop* hop, struct vreg* vreg); +extern void hop_add_output_vreg(struct hop* hop, struct vreg* vreg); +extern void hop_add_through_vreg(struct hop* hop, struct vreg* src, struct vreg* dest); +extern struct vreg* hop_find_input_vreg(struct hop* hop, struct value* value); +extern struct vreg* hop_find_output_vreg(struct hop* hop, struct value* value); extern void hop_add_move(struct hop* hop, struct value* src, struct value* dest); extern void hop_add_string_insel(struct hop* hop, const char* string); diff --git a/mach/proto/mcg/pass_assignvregs.c b/mach/proto/mcg/pass_assignvregs.c index 4238cf293..2aa80f263 100644 --- a/mach/proto/mcg/pass_assignvregs.c +++ b/mach/proto/mcg/pass_assignvregs.c @@ -36,10 +36,8 @@ static struct hop* clone_vregs(void) struct valueusage* usage = hop_get_value_usage(hop, value); hashtable_put(&mapping, value, newvreg); - usage->input = true; - usage->invreg = oldvreg; - usage->output = true; - usage->outvreg = newvreg; + usage->input = usage->output = true; + hop_add_through_vreg(hop, oldvreg, newvreg); } return hop; @@ -83,11 +81,27 @@ static void assign_vregs(void) for (i=0; ihops.count; i++) { + /* Remove completely unused vregs from the mapping. */ + + hop = current_bb->hops.item[i]; + { + struct hashtable_iterator hit = {}; + while (hashtable_next(&mapping, &hit)) + { + struct value* value = hit.key; + struct valueusage* usage = hop_get_value_usage(hop, value); + if (!usage->input && !usage->output && !usage->through) + hashtable_delete_current(&mapping, &hit); + } + } + /* Insert a parallel-move hop to copy all the vregs. */ - struct hop* move = clone_vregs(); - array_insert(¤t_bb->hops, move, i); - i++; + { + struct hop* move = clone_vregs(); + array_insert(¤t_bb->hops, move, i); + i++; + } /* Copy the previous mapping to this hop. */ @@ -98,7 +112,7 @@ static void assign_vregs(void) { struct value* value = hit.key; struct vreg* vreg = hit.value; - hop_get_value_usage(hop, value)->invreg = vreg; + hop_add_input_vreg(hop, vreg); } } @@ -126,9 +140,15 @@ static void assign_vregs(void) assert(!(usage->through && usage->output)); if (usage->through) - usage->outvreg = usage->invreg; + { + struct vreg* invreg = hop_find_input_vreg(hop, value); + hop_add_through_vreg(hop, invreg, invreg); + } if (usage->output) - usage->outvreg = create_and_map_vreg(value); + { + struct vreg* outvreg = create_and_map_vreg(value); + hop_add_output_vreg(hop, outvreg); + } } } } diff --git a/mach/proto/mcg/pass_copiestomoves.c b/mach/proto/mcg/pass_copiestomoves.c index 177821987..4a0150eb5 100644 --- a/mach/proto/mcg/pass_copiestomoves.c +++ b/mach/proto/mcg/pass_copiestomoves.c @@ -2,7 +2,7 @@ void pass_convert_copies_to_moves(void) { - int i, j; + int i, j, k; for (i=0; ihops.item[j]; if (hop->is_move) { - struct valueusage* usage; - struct hashtable_iterator hit = {}; struct vreg* invreg = NULL; struct vreg* outvreg = NULL; - while (hashtable_next(hop->valueusage, &hit)) + + for (k=0; kvregusage.count; k++) { - usage = hit.value; - if (usage->input && !usage->output) + struct vreg* in = hop->vregusage.item[k].left; + struct vreg* out = hop->vregusage.item[k].right; + + if (in && !out) { assert(!invreg); - invreg = usage->invreg; + invreg = in; } - if (!usage->input && usage->output) + if (!in && out) { assert(!outvreg); - outvreg = usage->outvreg; + outvreg = out; } } if (invreg && outvreg) { - usage = hop_get_value_usage(hop, outvreg->value); + struct valueusage* usage = hop_get_value_usage(hop, outvreg->value); assert(!usage->input); usage->input = true; - usage->invreg = invreg; + hop_add_through_vreg(hop, invreg, outvreg); } } } diff --git a/mach/proto/mcg/pass_registerallocator.c b/mach/proto/mcg/pass_registerallocator.c index 60a4d2bcb..b2ffa7912 100644 --- a/mach/proto/mcg/pass_registerallocator.c +++ b/mach/proto/mcg/pass_registerallocator.c @@ -17,6 +17,8 @@ static ARRAYOF(struct vreg) simplified; static struct vreg* actual(struct vreg* vreg) { + if (!vreg) + return NULL; while (vreg->coalesced_with) vreg = vreg->coalesced_with; return vreg; @@ -52,7 +54,7 @@ static void wire_together_bbs(void) static void generate_graph(void) { - int i, j, k; + int i, j, k, m; for (i=0; ihops.count; j++) { struct hop* hop = bb->hops.item[j]; - struct hashtable_iterator hit1 = {}; - while (hashtable_next(hop->valueusage, &hit1)) + for (k=0; kvregusage.count; k++) { - struct valueusage* usage1 = hit1.value; - struct hashtable_iterator hit2 = {}; - while (hashtable_next(hop->valueusage, &hit2)) + struct vreg* invreg1 = actual(hop->vregusage.item[k].left); + struct vreg* outvreg1 = actual(hop->vregusage.item[k].right); + + for (m=k; mvregusage.count; m++) { - struct valueusage* usage2 = hit2.value; - - if (usage1->invreg) - graph_add_vertex(&interference, actual(usage1->invreg)); - if (usage2->invreg) - graph_add_vertex(&interference, actual(usage2->invreg)); - if (usage1->invreg && usage2->invreg) - graph_add_edge(&interference, actual(usage1->invreg), actual(usage2->invreg)); - if (usage1->outvreg && usage2->outvreg) - graph_add_edge(&interference, actual(usage1->outvreg), actual(usage2->outvreg)); - - if (usage1->corrupted && usage1->invreg && usage2->outvreg) - graph_add_edge(&interference, actual(usage1->invreg), actual(usage2->outvreg)); + struct vreg* invreg2 = actual(hop->vregusage.item[m].left); + struct vreg* outvreg2 = actual(hop->vregusage.item[m].right); + + if (invreg1) + graph_add_vertex(&interference, invreg1); + if (invreg2) + graph_add_vertex(&interference, invreg2); + if (outvreg1) + graph_add_vertex(&interference, outvreg1); + if (outvreg2) + graph_add_vertex(&interference, outvreg2); + + if (invreg1 && invreg2) + graph_add_edge(&interference, invreg1, invreg2); + if (outvreg1 && outvreg2) + graph_add_edge(&interference, outvreg1, outvreg2); } - if (hop->is_move && usage1->invreg && usage1->outvreg) - graph_add_edge(&affinity, actual(usage1->invreg), actual(usage1->outvreg)); + if (hop->is_move && invreg1 && outvreg1) + graph_add_edge(&affinity, invreg1, outvreg1); } } } @@ -352,17 +357,17 @@ static void assign_hard_registers(void) { struct vreg* vreg = array_pop(&simplified); int neighbours = vreg->neighbours; - unsigned int bitmap = 0; + burm_register_bitmap_t bitmap = {}; while (neighbours > 0) { struct vreg* neighbour = actual(array_pop(&simplified)); if (neighbour->hreg != -1) - bitmap_set(&bitmap, 32, neighbour->hreg); + bitmap_set(bitmap, burm_register_count, neighbour->hreg); neighbours--; } - vreg->hreg = bitmap_find_unset_bit(&bitmap, 32); + vreg->hreg = bitmap_find_unset_bit(bitmap, burm_register_count); } } diff --git a/mach/proto/mcg/pass_spillibility.c b/mach/proto/mcg/pass_spillibility.c index f434dc099..923d2b74f 100644 --- a/mach/proto/mcg/pass_spillibility.c +++ b/mach/proto/mcg/pass_spillibility.c @@ -4,26 +4,25 @@ static struct basicblock* current_bb; static void calculate_spillibility(void) { - int i; + int i, j; 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)) + for (j=0; jvregusage.count; j++) { - struct value* value = hit.key; - struct valueusage* usage = hit.value; + struct vreg* invreg = hop->vregusage.item[j].left; + struct vreg* outvreg = hop->vregusage.item[j].right; + struct valueusage* usage = invreg ? hop_get_value_usage(hop, invreg->value) : NULL; - if (!usage->through) - { - if (usage->invreg) - usage->invreg->needs_register = true; - if (usage->outvreg) - usage->outvreg->needs_register = true; - } + if (invreg && !outvreg) + invreg->needs_register = true; + if (!invreg && outvreg) + outvreg->needs_register = true; + if (invreg && outvreg && !usage->through) + invreg->needs_register = outvreg->needs_register = true; } } } -- 2.34.1