[perl #32208] [PATCH] Register allocation patch - scales better to more symbols

# 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);
 }
 
 /*