From 9ba0e1d3d369827b41eed257b5528acf4bbf6a41 Mon Sep 17 00:00:00 2001 From: David Given Date: Mon, 28 Nov 2016 23:38:38 +0100 Subject: [PATCH] Basic building and initial coalescing of the interference graph now works. --- mach/proto/mcg/hop.c | 16 ++ mach/proto/mcg/hop.h | 3 + mach/proto/mcg/main.c | 60 +++--- mach/proto/mcg/mcg.h | 1 + mach/proto/mcg/pass_registerallocator.c | 235 ++++++++++++++++++++++++ mach/proto/mcg/reg.h | 1 + 6 files changed, 294 insertions(+), 22 deletions(-) diff --git a/mach/proto/mcg/hop.c b/mach/proto/mcg/hop.c index 72464a82a..c928b8fd0 100644 --- a/mach/proto/mcg/hop.c +++ b/mach/proto/mcg/hop.c @@ -162,6 +162,22 @@ void hop_add_insel(struct hop* hop, const char* fmt, ...) va_end(ap); } +void hop_walk(hop_walker_t* callback, void* user) +{ + int i, j, k; + + for (i=0; ihops.count; j++) + { + struct hop* hop = bb->hops.item[j]; + callback(hop, user); + } + } +} + static void print_header(char k, struct hop* hop) { int i; diff --git a/mach/proto/mcg/hop.h b/mach/proto/mcg/hop.h index 21c7e9293..d7b8f34b4 100644 --- a/mach/proto/mcg/hop.h +++ b/mach/proto/mcg/hop.h @@ -66,6 +66,9 @@ extern void hop_add_eoi_insel(struct hop* hop); extern void hop_add_insel(struct hop* hop, const char* fmt, ...); +typedef void hop_walker_t(struct hop* hop, void* user); +extern void hop_walk(hop_walker_t* callback, void* user); + extern char* hop_render(struct hop* hop); extern void hop_print(char k, struct hop* hop); diff --git a/mach/proto/mcg/main.c b/mach/proto/mcg/main.c index cf8a4435f..bc776b5fa 100644 --- a/mach/proto/mcg/main.c +++ b/mach/proto/mcg/main.c @@ -7,6 +7,7 @@ static const char* tracechars = NULL; FILE* outputfile = NULL; FILE* dominance_dot_file = NULL; FILE* cfg_dot_file = NULL; +FILE* regalloc_dot_file = NULL; bool tracing(char k) { @@ -37,6 +38,35 @@ static bool find_procedures_cb(struct symbol* symbol, void* user) return false; } +static FILE* open_dot_file(const char* filename) +{ + FILE* fp = fopen(filename, "w"); + if (!fp) + fatal("couldn't open output file '%s': %s", + filename, strerror(errno)); + fprintf(fp, "digraph {\n"); + return fp; +} + +static void close_dot_files(void) +{ + if (cfg_dot_file) + { + fprintf(cfg_dot_file, "}\n"); + fclose(cfg_dot_file); + } + if (dominance_dot_file) + { + fprintf(dominance_dot_file, "}\n"); + fclose(dominance_dot_file); + } + if (regalloc_dot_file) + { + fprintf(regalloc_dot_file, "}\n"); + fclose(regalloc_dot_file); + } +} + int main(int argc, char* const argv[]) { const char* inputfilename = NULL; @@ -48,26 +78,22 @@ int main(int argc, char* const argv[]) opterr = 1; for (;;) { - int c = getopt(argc, argv, "-d:D:C:o:"); + int c = getopt(argc, argv, "-d:D:C:R:o:"); if (c == -1) break; switch (c) { case 'C': - cfg_dot_file = fopen(optarg, "w"); - if (!cfg_dot_file) - fatal("couldn't open output file '%s': %s", - optarg, strerror(errno)); - fprintf(cfg_dot_file, "digraph {\n"); + cfg_dot_file = open_dot_file(optarg); break; case 'D': - dominance_dot_file = fopen(optarg, "w"); - if (!dominance_dot_file) - fatal("couldn't open output file '%s': %s", - optarg, strerror(errno)); - fprintf(dominance_dot_file, "digraph {\n"); + dominance_dot_file = open_dot_file(optarg); + break; + + case 'R': + regalloc_dot_file = open_dot_file(optarg); break; case 'd': @@ -86,6 +112,7 @@ int main(int argc, char* const argv[]) inputfilename = optarg; } } + atexit(close_dot_files); symbol_init(); @@ -120,17 +147,6 @@ int main(int argc, char* const argv[]) fclose(outputfile); EM_close(); - if (cfg_dot_file) - { - fprintf(cfg_dot_file, "}\n"); - fclose(cfg_dot_file); - } - if (dominance_dot_file) - { - fprintf(dominance_dot_file, "}\n"); - fclose(dominance_dot_file); - } - return 0; } diff --git a/mach/proto/mcg/mcg.h b/mach/proto/mcg/mcg.h index 860704285..6ea7c6157 100644 --- a/mach/proto/mcg/mcg.h +++ b/mach/proto/mcg/mcg.h @@ -131,6 +131,7 @@ extern const char* platform_label(const char* label); extern FILE* outputfile; extern FILE* dominance_dot_file; extern FILE* cfg_dot_file; +extern FILE* regalloc_dot_file; #endif diff --git a/mach/proto/mcg/pass_registerallocator.c b/mach/proto/mcg/pass_registerallocator.c index a5436bc73..f5187e2b6 100644 --- a/mach/proto/mcg/pass_registerallocator.c +++ b/mach/proto/mcg/pass_registerallocator.c @@ -1,5 +1,28 @@ #include "mcg.h" +/* This is based around the elegant graph colouring algorithm here: + * + * http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.5924 + * +struct anode +{ + int id; + int degree; + struct vref* vref; +}; + +struct vref +{ + struct vref* next; + struct vreg* vreg; +}; + +static struct heap anode_heap; +static bool interference_graph_valid; +static PMAPOF(struct anode, struct anode) interference; +static ARRAYOF(struct anode) vertices; +static ARRAYOF(struct anode) simplified; +#if 0 struct assignment { struct vreg* in; @@ -756,15 +779,227 @@ static void layout_stack_frame(void) stacksize = pack_stackframe(stacksize, EM_wordsize*1, burm_int_ATTR); current_proc->spills_size = stacksize; } +#endif + +static void walk_vregs(void (*callback)(struct vreg* vreg)) +{ + int i, j, k; + + interference.count = 0; + for (i=0; ihops.count; j++) + { + struct hop* hop = bb->hops.item[j]; + + for (k=0; kins.count; k++) + callback(hop->ins.item[k]); + for (k=0; kouts.count; k++) + callback(hop->outs.item[k]); + for (k=0; kthroughs.count; k++) + callback(hop->throughs.item[k]); + } + } +} + +static void clear_anode_cb(struct vreg* vreg) +{ + vreg->anode = NULL; +} + +static void assign_anode_cb(struct vreg* vreg) +{ + static int id = 1; + struct anode* anode = heap_alloc(&anode_heap, 1, sizeof(*anode)); + struct vref* vref = heap_alloc(&anode_heap, 1, sizeof(*vref)); + anode->id = id++; + anode->vref = vref; + vref->vreg = vreg; + vreg->anode = anode; +} + +/* Calling this makes the interference graph invalid */ +static void coalesce_anodes(struct anode* left, struct anode* right) +{ + struct vref* vref; + int i; + + if (left == right) + return; + + vref = left->vref; + if (vref) + { + while (vref->next) + vref = vref->next; + vref = vref->next = right->vref; + } + else + vref = left->vref = right->vref; + + while (vref) + { + vref->vreg->anode = left; + vref = vref->next; + } + + interference_graph_valid = false; +} + +static void coalesce_phis(void) +{ + int i, j; + + interference.count = 0; + 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; + + coalesce_anodes(src->anode, dest->anode); + } + } +} + +static void interferes_with(struct vreg** regs1, int count1, struct vreg** regs2, int count2) +{ + int i, j; + + for (i=0; ianode; + + for (j=0; janode; + + if (left != right) + pmap_add_bi(&interference, left, right); + } + } +} + +static void dump_anode(struct anode* anode) +{ + struct vref* vref; + + fprintf(regalloc_dot_file, "%s.%d deg %d\n", + current_proc->name, anode->id, anode->degree); + vref = anode->vref; + while (vref) + { + fprintf(regalloc_dot_file, "%%%d ", vref->vreg->id); + vref = vref->next; + } +} + +static void dump_interference_graph(void) +{ + int i; + + fprintf(regalloc_dot_file, "subgraph \"%s\" {\n", current_proc->name); + + for (i=0; i \""); + dump_anode(interference.item[i].right); + fprintf(regalloc_dot_file, "\";\n"); + } + + fprintf(regalloc_dot_file, "}\n"); +} + +static void build_interference_graph_cb(struct hop* hop, void* user) +{ + int i; + + interferes_with(hop->ins.item, hop->ins.count, hop->ins.item, hop->ins.count); + interferes_with(hop->outs.item, hop->outs.count, hop->outs.item, hop->outs.count); + interferes_with(hop->throughs.item, hop->throughs.count, hop->throughs.item, hop->throughs.count); + interferes_with(hop->throughs.item, hop->throughs.count, hop->ins.item, hop->ins.count); + interferes_with(hop->throughs.item, hop->throughs.count, hop->outs.item, hop->outs.count); + + for (i=0; iconstraints.count; i++) + { + struct vreg* vreg = hop->constraints.item[i].left; + struct constraint* c = hop->constraints.item[i].right; + + if (c->preserved) + interferes_with(&vreg, 1, hop->outs.item, hop->outs.count); + if (c->equals_to) + coalesce_anodes(vreg->anode, c->equals_to->anode); + } +} + +void collect_vertices(void) +{ + int i; + + vertices.count = 0; + for (i=0; idegree = 0; + for (j=0; jdegree++; + if (interference.item[j].right == candidate) + candidate->degree++; + } + } +} void pass_register_allocator(void) { + simplified.count = 0; + walk_vregs(clear_anode_cb); + walk_vregs(assign_anode_cb); + coalesce_phis(); + + do + { + interference_graph_valid = true; + hop_walk(build_interference_graph_cb, NULL); + } + while (!interference_graph_valid); + + collect_vertices(); + update_degrees(); + + dump_interference_graph(); + heap_free(&anode_heap); + + exit(1); + #if 0 populate_hregs(); wire_up_blocks_ins_outs(); assign_hregs_to_vregs(); insert_phi_copies(); layout_stack_frame(); + #endif } /* vim: set sw=4 ts=4 expandtab : */ diff --git a/mach/proto/mcg/reg.h b/mach/proto/mcg/reg.h index 00c8220b5..d1c4cbcb5 100644 --- a/mach/proto/mcg/reg.h +++ b/mach/proto/mcg/reg.h @@ -27,6 +27,7 @@ struct vreg uint32_t type; struct phicongruence* congruence; struct hop* defined; + struct anode* anode; ARRAYOF(struct hop) used; }; -- 2.34.1