# New Ticket Created by Bill Coffman
# Please include the string: [perl #32208]
# in the subject line of all future correspondence about this issue.
# <URL: http://rt.perl.org:80/rt3/Ticket/Display.html?id=32208 >
Patch does the following:
- Applied Matula/Chaitin/Briggs algorithm for register allocation.
- Color the graph all at once, and spill all symbols with high colors.
Spill all at once to speed things up.
- Remove several of the functions, which are incorporated into the new
algorithm.
- Shortcomming: doesn't use score anymore, but the algorithm is smart
enough that I hope it's okay to do that.
- Failed 2 tests for latest CVS. (See earlier posting.)
WANT TO DO:
- Apparently, there's a memory leak which prevents from coloring
graphs with more than a few hundred registers. I suspect this is in
the spill, or update_life routine. Not sure if it's mine or
pre-existing.
- Interference graph is using 8 times the memory it needs to use.
This is still trivial compared to lost data in above bug.
- Smarten up algorithm to use score again. A good way to do so is
commented in the code.
- Create spilling score, that prints out with a debug option. This
can be a metric to compare various algorithms.
- Improve spill to spill all registers at once, adding speed.
- Introduce proper analysis of flow graph, to create less conservative
interference graph.
- Color each of the four register types separately. Be sure to
compare gains with losses for this, as it is not entirely cear.
- Introduce register renaming. When variable is reassigned, it might
as well be considered a new symbol... well, much of the time, anyway.
- Introduce variable register size, in coordination with subroutine
calls, to reduce copy cost. Coordinate with Dan and Leo on this.
- Improve flow-graph, basic block calculation, etc. Make it all a
little easier to understand, and more efficient. Knuth style,
literate programming. Well, just good comments, and a couple of
decent pods.
Index: imcc/reg_alloc.c
===================================================================
RCS file: /cvs/public/parrot/imcc/reg_alloc.c,v
retrieving revision 1.22
diff -u -r1.22 reg_alloc.c
--- imcc/reg_alloc.c 30 Sep 2004 16:00:37 -0000 1.22
+++ imcc/reg_alloc.c 29 Oct 2004 04:39:07 -0000
@@ -41,15 +41,63 @@
static void compute_du_chain(IMC_Unit * unit);
static void compute_one_du_chain(SymReg * r, IMC_Unit * unit);
static int interferes(IMC_Unit *, SymReg * r0, SymReg * r1);
-static int map_colors(IMC_Unit *, int x, unsigned int * graph, int colors[], int typ);
-#ifdef DO_SIMPLIFY
-static int simplify (IMC_Unit *);
-#endif
static void compute_spilling_costs (Parrot_Interp, IMC_Unit *);
-static void order_spilling (IMC_Unit *);
static void spill (Interp *, IMC_Unit * unit, int);
-static int try_allocate(Parrot_Interp, IMC_Unit *);
-static void restore_interference_graph(IMC_Unit *);
+
+/***************** New graph algorithm stuff *********************/
+static void ig_color_graph(void);
+static void apply_coloring(IMC_Unit *);
+static void ig_precolor(IMC_Unit *);
+static int ig_init_graph(int num_nodes, unsigned* edge_bits);
+static void ig_clear_graph(void);
+static int spill_registers(Parrot_Interp interpreter, IMC_Unit * unit);
+
+typedef struct {
+ int deg; /* degree of node (# neighbors) */
+ int col; /* color assigned to this node */
+ int rank; /* position within the below D array */
+ char in; /* boolean, indicating if removed yet */
+} node;
+
+typedef struct {
+ int n; /* number of nodes */
+ node* V; /* array of nodes */
+ int* D; /* sorted nodes by degree */
+ unsigned* E; /* edge data, adjacency matrix */
+ int k; /* maximum color used in graph (0 means uncolored) */
+} graph;
+
+graph G; /* must have as global to use qsort,
+ but there's only one at a time -- FIXME minimize this global */
+
+#define Dbg_level 0 /* FIXME -- must be a better way to implement this */
+#include <stdarg.h>
+static void my_message(const char *pat, ...)
+{
+ va_list args;
+ va_start(args, pat);
+#if Dbg_level >= 1
+ vfprintf(stderr,pat,args);
+#endif
+ va_end(args);
+}
+static void my_message2(const char *pat, ...)
+{
+ va_list args;
+ va_start(args, pat);
+#if Dbg_level >= 2
+ vfprintf(stderr,pat,args);
+#endif
+ va_end(args);
+}
+/*#define Dbg printf*/
+#define Dbg my_message
+#define Dbg2 my_message2
+
+
+/******************************************************************/
+
+
#if 0
static int neighbours(int node);
#endif
@@ -57,7 +105,7 @@
extern int pasm_file;
/* XXX FIXME: Globals: */
-static IMCStack nodeStack;
+static IMCStack nodeStack; /* FIXME -- this is used in a silly way */
static unsigned int* ig_get_word(int i, int j, int N, unsigned int* graph,
int* bit_ofs)
@@ -74,12 +122,14 @@
*word |= (1 << bit_ofs);
}
+/* currently unused.
static void ig_clear(int i, int j, int N, unsigned int* graph)
{
int bit_ofs;
unsigned int* word = ig_get_word(i, j, N, graph, &bit_ofs);
*word &= ~(1 << bit_ofs);
}
+*/
int ig_test(int i, int j, int N, unsigned int* graph);
int ig_test(int i, int j, int N, unsigned int* graph)
@@ -105,9 +155,7 @@
void
imc_reg_alloc(Interp *interpreter, IMC_Unit * unit)
{
- int to_spill;
- int todo, first;
- int loop_counter;
+ int todo, first, loop_counter;
if (!unit)
return;
@@ -181,45 +229,36 @@
}
todo = 1;
loop_counter = 0;
-#if !DOIT_AGAIN_SAM
+
build_interference_graph(interpreter, unit);
-#endif
- while (todo) {
- loop_counter++;
-#if DOIT_AGAIN_SAM
+
+ if (optimizer_level & OPT_SUB)
+ allocate_wanted_regs(unit);
+
+ if (!ig_init_graph(unit->n_symbols, unit->interference_graph))
+ fatal(1,"imc_reg_alloc", "cannot allocate memory for coloring graph");
+ ig_precolor(unit);
+ ig_color_graph(); /* in G */
+
+ /*
+ * Use colors from G to allocate registers and spill the high colors.
+ */
+ while (G.k > MAX_COLOR) { /* inside this loop, we must spill */
+ compute_spilling_costs(interpreter, unit); /* will eventually use */
+ spill_registers(interpreter, unit); /* this changes things */
+
+ ig_clear_graph(); /* reclaim used memory for G */
+ free(unit->interference_graph);
build_interference_graph(interpreter, unit);
-#endif
- if (optimizer_level & OPT_SUB)
- allocate_wanted_regs(unit);
- compute_spilling_costs(interpreter, unit);
-#ifdef DO_SIMPLIFY
- /* simplify until no changes can be made */
- while (simplify(unit)) {}
-#endif
- order_spilling(unit); /* put the remaining items on stack */
+ if (!ig_init_graph(unit->n_symbols, unit->interference_graph))
+ fatal(1,"imc_reg_alloc", "cannot allocate memory for coloring graph");
+ ig_precolor(unit);
+ ig_color_graph(); /* in G */
+ }
+ apply_coloring(unit);
- to_spill = try_allocate(interpreter, unit);
- allocated = 1;
+ ig_clear_graph(); /* reclaim used memory */
- if ( to_spill >= 0 ) {
- allocated = 0;
- spill(interpreter, unit, to_spill);
- /*
- * build the new cfg/reglist on the fly in spill() and
- * do life analysis there for only the involved regs
- */
-#if DOIT_AGAIN_SAM
- find_basic_blocks(interpreter, unit, 0);
- build_cfg(interpreter, unit);
- build_reglist(interpreter, unit, 1);
- life_analysis(interpreter);
-#endif
- }
- else {
- /* the process is finished */
- todo = 0;
- }
- }
if (optimizer_level & OPT_SUB)
sub_optimize(interpreter, unit);
if (IMCC_INFO(interpreter)->debug & DEBUG_IMC)
@@ -227,6 +266,7 @@
if (IMCC_INFO(interpreter)->verbose ||
(IMCC_INFO(interpreter)->debug & DEBUG_IMC))
print_stat(interpreter, unit);
+ free(unit->interference_graph);
imcstack_free(nodeStack);
}
@@ -327,99 +367,6 @@
qsort(unit->reglist, unit->n_symbols, sizeof(SymReg*), reg_sort_f);
}
-/*
- * regs are sorted now according to their start line of usage
- * which means they are sorted by basic block numbers too
- *
- * run through them and allocate all that don't overlap
- * in one bunch
- *
- * registers 28-30 are reserved for short range temps, which
- * get allocate immediately
- */
-
-#define ALLOCATE_HACK
-
-#ifdef ALLOCATE_HACK
-
-static void
-allocate_non_interfering(Parrot_Interp interpreter, IMC_Unit *unit, int n)
-{
- int i, t;
- int first_color, last_line, b, first_reg;
- SymReg *r = NULL; /* uninit gcc warning */
- SymReg ** reglist = unit->reglist;
-
- for (t = 0; t < 4; t++) {
- int typ = "INSP"[t];
- i = 0;
- for (b = 0; b < unit->n_basic_blocks; b++) {
- first_color = 30;
- last_line = -1;
- first_reg = -1;
- while (first_color >= 28) { /* 28..30 for 3 temps */
- for (; i < n; ++i) {
- r = reglist[i];
- /*
- * if we didn't reach this basic block, continue
- */
- if (r->first_ins->bbindex < b)
- continue;
- /* remember first register in this block */
- if (first_reg == -1)
- first_reg = i;
- /*
- * register set must match and not already allocated
- */
- if (r->set != typ || (r->type & VT_REGP) ||
- r->want_regno >= 0 || r->color >= 0)
- continue;
- if (r->color == first_color) {
- warning(interpreter, "allocate_non_interfering",
- "color %d for register type %c in use",
- first_color, typ);
- goto next_color;
- }
- /* at end of block start over, try next color */
- if (r->first_ins->bbindex > b)
- goto next_color;
- /* if this register spans more then one block
- * try next one
- */
- if (r->last_ins->bbindex > b)
- continue;
- /*
- * if it interfers with the previous allocated reg
- * try next one
- */
- if (r->first_ins->index <= last_line)
- continue;
- assert(r->first_ins->bbindex == r->last_ins->bbindex);
- break;
- }
- if (i == n)
- goto next_block;
- last_line = r->last_ins->index;
- r->color = first_color;
- r->type = VTPASM;
- debug(interpreter, DEBUG_IMC, "block %d coloring '%s' %d\n",
- b, r->name, r->color);
- continue;
-next_color:
- if (first_reg >= 0)
- i = first_reg;
- else
- i = 0;
- /* reset, color is decremented, so no interfernce */
- last_line = -1;
- --first_color;
- }
-next_block:
- ;
- } /* for b */
- } /* for t */
-}
-#endif
/* make a linear list of IDENTs and VARs, set n_symbols
* TODO
@@ -442,10 +389,6 @@
for (; r; r = r->next) {
if (r->type & VT_REGP)
count++;
-#ifdef ALLOCATE_HACK
- if (r->color >= 28)
- continue;
-#endif
if (r->type & VTREGISTER)
count++;
}
@@ -468,10 +411,7 @@
if (r->type & VT_REGP)
unit->reglist[count++] = r->reg;
else
-#ifdef ALLOCATE_HACK
- if (r->color < 28)
-#endif
- unit->reglist[count++] = r;
+ unit->reglist[count++] = r;
/* rearange I/N registers
* XXX not here, do it, when reading the source
* .nciarg, ... !!!1 */
@@ -496,15 +436,6 @@
n_symbols -= unused;
unit->n_symbols = n_symbols;
sort_reglist(unit);
- if (first) {
-#ifdef ALLOCATE_HACK
- info(interpreter, 1, "build_reglist: %d symbols\n", n_symbols);
- allocate_non_interfering(interpreter, unit, n_symbols);
- build_reglist(interpreter, unit, 0);
- info(interpreter, 1, "allocate_non_interfering, now: %d symbols\n",
- unit->n_symbols);
-#endif
- }
}
/* creates the interference graph between the variables.
@@ -755,128 +686,9 @@
return 0;
}
-/*
- * Simplify deletes all the nodes from the interference graph
- * that have arity lower than MAX_COLOR
- *
- * Returns if it has been able to delete at least one node
- * and 0 otherwise.
- *
- * XXX: this doesn't look at score, so I think this is bogus
- * - currently disabled
- *
- */
-#ifdef DO_SIMPLIFY
-static int
-simplify (IMC_Unit * unit)
-{
- int changes = 0;
- int x;
- SymReg **g;
-
- g = unit->reglist;
-
- for (x = 0; x < n_symbols; x++) {
- if (g[x]->color >= 0) /* VTPASM */
- g[x]->simplified = 1;
- }
- for (x = 0; x < n_symbols; x++) {
- if (g[x]->simplified) {
- break;
- }
-
- if ( neighbours(x) < MAX_COLOR) {
- debug(interpreter, DEBUG_IMC, "#simplifying [%s]\n", g[x]->name);
-
- imcstack_push(nodeStack, x);
-
- g[x]->simplified = 1;
- changes = 1;
- break;
- }
- }
-
- return changes;
-}
-#endif
-
-/* Puts the remaining nodes on the stack, on the correct order.
- *
- * We count how many times does a symbol appear (weighted by the probability
- * that this particular point of code will be reached) and choose the symbol
- * with the lower score until all are in the stack.
- *
- */
-
-static void
-order_spilling (IMC_Unit * unit)
-{
- int min_score = 0, total_score;
- int min_node;
- int x;
-
- while (1) {
-
- min_node = -1;
-
- for (x = 0; x < unit->n_symbols; x++) {
- /* if its spilled skip it */
- if (unit->reglist[x]->usage & U_SPILL)
- continue;
-
- /* for now, our score function only
- takes in account how many times a symbols
- has appeared + the loop_depth */
-
- /* we have to combine somehow the rank of the node
- * with the cost of spilling it
- *
- * our current function to maximize is:
- * rank - spill_cost
- *
- * I have no clue of how good it is
- */
- if (!(unit->reglist[x]->simplified)) {
- total_score = unit->reglist[x]->score /* - neighbours(x) */;
-
- if ( (min_node == -1) || (min_score > total_score) ) {
- min_node = x;
- min_score = total_score;
- }
- }
- }
-
- if (min_node == -1)
- break; /* We are finished */
-
- imcstack_push(nodeStack, min_node);
- unit->reglist[min_node]->simplified = 1;
- }
- /*
- * now put all spilled regs on top of stack so that they
- * get their register first
- */
- for (x = 0; x < unit->n_symbols; x++) {
- if (unit->reglist[x]->usage & U_SPILL)
- imcstack_push(nodeStack, x);
- }
-}
-
-
-static void
-restore_interference_graph(IMC_Unit * unit)
-{
- int i;
- for (i=0; i < unit->n_symbols; i++) {
- if ((unit->reglist[i]->type & VTPASM) && !(optimizer_level & OPT_PASM))
- continue;
- unit->reglist[i]->color = -1;
- unit->reglist[i]->simplified = 0;
- }
-}
/*
- * try to allocate as much as possible
+ * try to allocate as much as possible, an optimization ...
*/
static void
allocate_wanted_regs(IMC_Unit * unit)
@@ -905,106 +717,7 @@
r->color = r->want_regno;
}
}
-/*
- * Color the graph assigning registers to each symbol:
- *
- * We just proceed poping items from the stack, and assigning
- * a free color to the them.
- *
- * If we run out of colors, then we need to spill the top node.
- */
-static int
-try_allocate(Parrot_Interp interpreter, IMC_Unit * unit)
-{
- int x = 0;
- int color, colors[MAX_COLOR];
- int free_colors, t;
- unsigned int *graph = unit->interference_graph;
- SymReg ** reglist = unit->reglist;
-
- while ((imcstack_depth(nodeStack) > 0) ) {
- x=imcstack_pop(nodeStack);
-
- for (t = 0; t < 4; t++) {
- int typ = "INSP"[t];
- memset(colors, 0, sizeof(colors));
- if (reglist[x]->set == typ && reglist[x]->color == -1) {
- free_colors = map_colors(unit, x, graph, colors, typ);
- if (free_colors > 0) {
- for (color = 0; color < MAX_COLOR; color++) {
- int c = (color + MAX_COLOR/2) % MAX_COLOR;
- if (!colors[c]) {
- reglist[x]->color = c;
-
- debug(interpreter, DEBUG_IMC,
- "#[%s] provisionally gets color [%d]"
- "(%d free colors, score %d)\n",
- reglist[x]->name, c,
- free_colors, reglist[x]->score);
- break;
- }
- }
- }
-
- if (reglist[x]->color == -1) {
- debug(interpreter, DEBUG_IMC,
- "# no more colors free = %d\n", free_colors);
-
- /* It has been impossible to assign a color
- * to this node, return it so it gets spilled
- */
-
- restore_interference_graph(unit);
- /* clean stack */
- while ((imcstack_depth(nodeStack) > 0) )
- imcstack_pop(nodeStack);
- return x;
- }
- }
- }
- }
-
- return -1; /* we are totally finished */
-}
-
-/*
- * map_colors: calculates what colors can be assigned to the x-th symbol.
- */
-static int
-map_colors(IMC_Unit* unit, int x, unsigned int *graph, int colors[], int typ)
-{
- int y = 0, n_symbols;
- SymReg * r;
- int color, free_colors;
-
- n_symbols = unit->n_symbols;
- memset(colors, 0, sizeof(colors[0]) * MAX_COLOR);
- /* reserved for spilling */
- if (typ == 'P')
- colors[31] = 1;
-#ifdef ALLOCATE_HACK
- colors[28] = 1; /* for immediate allocation */
- colors[29] = 1; /* for immediate allocation */
- colors[30] = 1; /* for immediate allocation */
-#endif
- for (y = 0; y < n_symbols; y++) {
- if (! ig_test(x, y, n_symbols, graph))
- continue;
- r = unit->reglist[y];
- if ( r
- && r->color != -1
- && r->set == typ) {
- colors[r->color] = 1;
- }
- }
- for (color = free_colors = 0; color < MAX_COLOR; color++)
- if (!colors[color])
- free_colors++;
- return free_colors;
-}
-
-#if ! DOIT_AGAIN_SAM
/* update bb and life_info after spilling
* this saves 4 costy routines
* NOTE {lhs_,}use_count are not set again, this is save, when no
@@ -1064,61 +777,10 @@
dump_symreg(unit);
}
}
-/*
- * update the interference_graph too and don't call
- * build_interference_graph again
- */
-
-static void
-update_interference(Parrot_Interp interpreter, IMC_Unit * unit,
- SymReg *old, SymReg *new)
-{
- int x, y, n_symbols;
- SymReg ** reglist = unit->reglist;
- unsigned int *interference_graph = unit->interference_graph;
-
- n_symbols = unit->n_symbols;
- if (old != new) {
- /* n_symbols is already increased */
- unsigned int *new_graph = ig_allocate(n_symbols);
- /* old symbols count of previous graph */
- int o = n_symbols - 1;
- for (x = 0; x < o; x++) {
- for (y = x + 1; y < o; y++) {
- if (ig_test(x, y, o, interference_graph)) {
- ig_set(x, y, n_symbols, new_graph);
- ig_set(y, x, n_symbols, new_graph);
- }
- }
- }
- free(interference_graph);
- unit->interference_graph = interference_graph = new_graph;
- }
- for (x = 0; x < n_symbols; x++) {
- for (y = x + 1; y < n_symbols; y++) {
- if (reglist[x] == old || reglist[x] == new ||
- reglist[y] == old || reglist[y] == new) {
- if (interferes(unit, reglist[x], reglist[y])) {
- ig_set(x, y, n_symbols, interference_graph);
- ig_set(y, x, n_symbols, interference_graph);
- }
- else {
- ig_clear(x, y, n_symbols, interference_graph);
- ig_clear(y, x, n_symbols, interference_graph);
- }
- }
- }
- }
- if (IMCC_INFO(interpreter)->debug & DEBUG_IMC) {
- fprintf(stderr, "old_sym %s\n", old->name);
- fprintf(stderr, "new_sym %s\n", new->name);
- dump_interference_graph(unit);
- }
-}
-#endif
/* Rewrites the unit instructions, inserting spill code in every ocurrence
- * of the symbol.
+ * of the symbol. XXX this has tremendous potential for optimization.
+ * Spilling multiple variables would help tremendously.
*/
static void
@@ -1128,15 +790,10 @@
int i, n, dl;
int needs_fetch, needs_store;
SymReg * old_sym, *p31, *new_sym;
- char * buf;
+ char buf[256];
SymReg *regs[IMCC_MAX_REGS];
SymReg **reglist = unit->reglist;
- buf = malloc(256 * sizeof(char));
- if (buf == NULL) {
- fatal(1, "spill","Out of mem\n");
- }
-
debug(interpreter, DEBUG_IMC, "#Spilling [%s]:\n", reglist[spilled]->name);
new_sym = old_sym = reglist[spilled];
@@ -1217,13 +874,9 @@
dl++;
}
if (needs_fetch || needs_store) {
-#if ! DOIT_AGAIN_SAM
/* update life info of prev sym */
update_life(interpreter, unit, ins, new_sym, needs_fetch, needs_store,
old_sym != new_sym);
- /* and interference of both */
- update_interference(interpreter, unit, old_sym, new_sym);
-#endif
/* if all symbols are in one basic_block, we need a new
* symbol, so that the life_ranges are minimal
* It would be nice, to detect, when changing the symbol
@@ -1236,18 +889,303 @@
ins = tmp;
}
}
+ if (IMCC_INFO(interpreter)->debug & DEBUG_IMC)
+ dump_instructions(unit);
+}
- free(buf);
-#if DOIT_AGAIN_SAM
- /* update index */
- for (i = 0, ins = unit; ins; ins = ins->next) {
- ins->index = i++;
+
+/*********************************************************/
+/**** The below is to test the new graph algorithms. ****/
+/*********************************************************/
+
+/*
+ * Use colors from G to allocate registers and spill the high colors.
+ */
+static int
+spill_registers(Parrot_Interp interpreter, IMC_Unit * unit)
+{
+ int spilled=0,x=0;
+ Dbg("spill_registers n=%d\n", G.n);
+
+ for (x = 0; x < G.n; x++) {
+ int maxcol = MAX_COLOR;
+ if (unit->reglist[x]->set == 'P') maxcol--; /* for spilling into P31 */
+ if (G.V[x].col > maxcol) {
+ Dbg("SPILL_REGISTERS node %d, spilling ... regcol=%d\n",
+ x, G.V[x].col);
+ spill(interpreter, unit, x);
+ /* new spill symbols are always added to end of list >n,
+ * so that's how we can get away with this little hack. */
+ Dbg("SPILL_REGISTERS spilled node %d\n", x);
+ spilled++;
+ }
}
+ return spilled;
+}
+
+/*
+ * Use colors from G to allocate registers and spill the high colors.
+ */
+static void
+apply_coloring(IMC_Unit * unit)
+{
+ int j,x=0;
+ SymReg ** reglist = unit->reglist;
+ int maxcol = MAX_COLOR;
+ Dbg("apply_coloring n=%d\n", G.n);
+
+ for (j = 0; j < G.n; j++) {
+ x = G.D[j];
+ Dbg2("pondering node %d\n", x);
+ if (unit->reglist[x]->usage & U_SPILL) /* already spilled, done below */
+ continue;
+ if (!(unit->reglist[x]->simplified)) /* probably not used */
+ continue;
+
+ imcstack_push(nodeStack, x); /* XXX don't really need this */
+ unit->reglist[x]->simplified = 1; /* not actually needed any more */
+ }
+ /*
+ * now put all spilled regs on top of stack so that they
+ * get their register first
+ */
+ for (x = 0; x < unit->n_symbols; x++) {
+ if (unit->reglist[x]->usage & U_SPILL)
+ imcstack_push(nodeStack, x);
+ }
+
+ while ((imcstack_depth(nodeStack) > 0) ) {
+ x=imcstack_pop(nodeStack);
+ Dbg2("APPLY popped node %d\n", x);
+
+ if (G.V[x].col <= maxcol) {
+ reglist[x]->color = G.V[x].col - 1;
+ Dbg2("APPLY node %d, reg=%ld\n", x, reglist[x]->color);
+ } else {
+ fatal(1,"apply_coloring", "wants to use too high reg num");
+ }
+ }
+#ifndef NDEBUG
+ for (x = 0; x < G.n; x++) {
+ int y;
+ assert(reglist[x]->color >= 0);
+ assert(reglist[x]->color < MAX_COLOR);
+ assert(reglist[x]->color == G.V[x].col-1);
+ Dbg("%d (reg==%ld):",x, reglist[x]->color);
+ for (y = 0; y < G.n; y++)
+ if (ig_test(x, y, G.n, G.E)) {
+ Dbg(" %d(%ld)",y, reglist[y]->color);
+ assert(reglist[x]->color != reglist[y]->color);
+ }
+ Dbg("\n");
+ }
+ Dbg("\ncoloring applied and verified, for %d node graph (Chi==%d).\n\n", G.n, G.k);
#endif
- if (IMCC_INFO(interpreter)->debug & DEBUG_IMC)
- dump_instructions(unit);
+}
+
+static int degree_comparator(const void * x, const void * y) {
+ return G.V[*(int*)x].deg < G.V[*(int*)y].deg ? -1 :
+ G.V[*(int*)x].deg == G.V[*(int*)y].deg ? 0 : 1;
+}
+
+static int ig_init_graph(int num_nodes, unsigned* edge_bits) {
+ int j,x,y;
+
+ G.n = num_nodes;
+ G.E = edge_bits;
+ G.k = 0;
+ G.V = (node*)calloc(G.n, sizeof(node));
+ G.D = (int*)calloc(G.n, sizeof(int)); /* to keep track of nodes by degee */
+
+ if (G.V ? G.D ? 0 : (free(G.V),1) : (1) )
+ return 0;
+
+ for (x = 0; x < num_nodes; x++) {
+ G.D[x] = x; /* put self into degree list */
+ for (y = 0; y < num_nodes; y++)
+ if (ig_test(x, y, num_nodes, edge_bits))
+ G.V[x].deg++; /* another neighbor of x is recorded */
+ assert(G.V[x].deg>=0 && G.V[x].deg<G.n);
+ }
+ qsort(G.D, G.n, sizeof(int), degree_comparator);
+ for (j = 0; j < num_nodes; j++) {
+ x = G.D[j];
+ G.V[x].col = 0; /* start uncolored */
+ G.V[x].rank = j;
+ G.V[x].in = 1;
+ }
+ return 1;
+}
+
+
+static void ig_clear_graph(void)
+{
+ free(G.V);
+ free(G.D);
+ G.n=0;
+ G.E=NULL;
+ G.k=0;
+ G.V=NULL;
+ G.D=NULL;
+}
+
+static void ig_remove_node(int x) { /* operates on global graph, G */
+ int j,y,v;
+ assert(G.V[x].deg>=0 && G.V[x].deg<G.n);
+ /*G.V[x].deg = 0; save for last assertion */
+ G.V[x].in = 0; /* set removal flag */
+ assert(G.V[x].rank==0 || !G.V[G.D[G.V[x].rank-1]].in);
+
+#ifdef NDEBUG
+ G.V[x].deg=0;
+#else
+ Dbg("del %d(%d)[rank=%d]:", x, G.V[x].deg, G.V[x].rank);
+ for (y = 0; y < G.n; y++) {
+ assert(G.D[G.V[y].rank]==y);
+ if (G.V[y].in && ig_test(x, y, G.n, G.E)) {
+ Dbg(" %d",y);
+ G.V[x].deg--; /*countdown degrees*/
+ }
+ }
+ Dbg("\n");
+ assert(G.V[x].deg==0);
+#endif
+ for (y = 0; y < G.n; y++)
+ if (G.V[y].in && ig_test(x, y, G.n, G.E)) { /* non-deleted neighbor */
+ int dy = G.V[y].deg--;
+ j = G.V[y].rank;
+ if (j==0 || G.V[G.D[j-1]].deg<dy) continue;
+ assert(G.D[j]==y);
+ while (j>0 && G.V[G.D[j-1]].in && G.V[G.D[j-1]].deg == dy) j--;
+ v = G.D[j]; /* these three lines exchange old & new j */
+ assert(G.V[v].rank==j);
+ G.V[v].rank = G.V[y].rank; /* old position of y saved in new */
+ G.V[y].rank = j;
+ G.D[G.V[y].rank]=y;
+ G.D[G.V[v].rank]=v;
+ assert(j>0 ? G.V[y].deg >= G.V[G.D[j-1]].deg : 1);
+ assert(j<G.n-1 ? G.V[y].deg <= G.V[G.D[j+1]].deg : 1);
+ }
+}
+
+static int ig_color_node(int x) /* select first available color */
+{
+ int c,y;
+ /*
+ * TODO for higher optimization level:
+ * Nodes that get colored too high (ie spill) should look at each
+ * neighboring colored node's score. If some neighboring color has a
+ * lower spill cost and can change their color or spill, then the more
+ * expensive node can have it's color. The cost of swapping out a color
+ * can be recorded in the below array, making it easier to find the switch
+ * color. This scheme should then reduce the cost of spilling overall.
+ *
+ * Actually, this might be a good idea anyway, since spilling is even
+ * expensive to do! Lot's of substitutions, and it looks like having
+ * to redo the whole graph?
+ */
+ char* avail = (char*)alloca(+G.k+41); /* lazily use bytes for avail colors */
+ memset(avail,1,G.k+41);
+ avail[32]=0; /*reserve spot for spill reg, p31: FIXME blocks S31,I31,N31*/
+ if (G.V[x].col)
+ Dbg2("ig_color_node color node %d, precolor col=%d\n", x, G.V[x].col);
+ for (y = 0; y < G.n; y++)
+ if (ig_test(x, y, G.n, G.E)) {
+ Dbg2("ig_color_node k=%d, rank %d, node %d, col=%d\n",
+ G.k, G.V[y].rank, y, G.V[y].col);
+ assert(0<=G.V[y].col && G.V[y].col<=G.k); /*uncolored is okay*/
+ avail[G.V[y].col] = 0;
+ }
+ if (G.V[x].col && avail[G.V[x].col]) {
+ c = G.V[x].col;
+ assert(avail[G.V[x].col]); /* verify no conflict */
+ } else {
+ if (G.V[x].col)
+ Dbg("WARNING - ig_color_node: cannot give requested color to "
+ "node %d, (%d)\n", x, G.V[x].col-1);
+ /* this looks stupid for a number of strange reasons... XXX pls clean */
+ for (c = 17; c < 31; c++) if (avail[c]) break;
+ if (!avail[c]) for (c = 31; c >= 1; c--) if (avail[c]) break;
+ if (!c)
+ for (c = 1; c <= G.k+2; c++) if (avail[c]) break;
+ G.V[x].col = c;
+ }
+ if (G.k<c) G.k = c;
+ Dbg2("ig_color_node color node %d, receives col=%d\n", x, G.V[x].col);
+ return c;
+}
+/*
+ * Set colors in G to pre-allocated values, from allocate_wanted_regs
+ */
+static void
+ig_precolor(IMC_Unit * unit)
+{
+ int j,x;
+ SymReg ** reglist = unit->reglist;
+ Dbg("COLORING GRAPH n=%d *****\n", G.n);
+ for (j = 0; j < G.n; j++) {
+ x = G.D[j];
+ G.V[x].col = 1 + reglist[x]->color;
+ if (!G.V[x].col && unit->reglist[x]->usage & U_SPILL) {
+ int c=1+MAX_COLOR/2, y=0; /* precolor spilled symbols */
+ while(y<G.n) {
+ for (y = 0; y < G.n; y++)
+ if (ig_test(x, y, G.n, G.E))
+ if (c == G.V[y].col) {c++; break;}
+ if (c>=MAX_COLOR)
+ fatal(1, "ig_precolor", "cannot precolor spilled symbol");
+ }
+ G.V[x].col=c;
+ Dbg("PRECOLORing spill-node %d as color %d\n",x,c);
+ }
+ assert(0<=G.V[x].col && G.V[x].col<=MAX_COLOR); /*uncolored is okay*/
+ if (G.V[x].col>G.k)
+ G.k = G.V[x].col;
+ reglist[x]->simplified = 1; /* not actually needed any more */
+ if(G.V[x].col)
+ Dbg("PRECOL rank %d, node %d, col=%d\n", G.V[x].rank, x, G.V[x].col);
+ }
+}
+
+/* The Matula Maximum Minimum Degree coloring algorithm (Degeneracy Coloring).
+ *
+ * Sort by degrees, remove lowest degree nodes, adjust other degrees, iterate.
+ * This algorithm for coloring, was adapted by Chaiten for register allocation.
+ * Briggs later made more modifications. The interesting part is spilling,
+ * which really has nothing to do with theoretical graph coloring. Stay tuned
+ * to this channel as the saga continues ...
+ */
+
+static void
+ig_color_graph(void) {
+ int j,x;
+
+ Dbg("ig_color_graph n=%d\n", G.n);
+ for (j=0; j<G.n; j++) {
+ x = G.D[j];
+ ig_remove_node(x);
+ }
+
+ for (j=G.n-1; j>=0; j--) {
+ x = G.D[j];
+ ig_color_node(x);
+ Dbg2("rank %d, node %d, col=%d\n", G.V[x].rank, x, G.V[x].col);
+#ifndef NDEBUG
+ {
+ int y;
+ for (y = 0; y < G.n; y++) {
+ assert(G.D[G.V[y].rank]==y);
+ if (ig_test(x, y, G.n, G.E)) {
+ assert(G.V[x].col != G.V[y].col);
+ }
+ }
+ assert(G.V[x].deg==0);
+ }
+#endif
+ }
+ Dbg("finished coloring, k=%d\n", G.k);
}
/*
