On Aug-07, Leopold Toetsch wrote:
> Sean O'Rourke <[EMAIL PROTECTED]> wrote:
> > [EMAIL PROTECTED] (Leopold Toetsch) writes:
> >> The interference_graph size is n_symbols * n_symbols *
> >> sizeof(a_pointer). This might already be too much.
> >>
> >> 2) There is a note in the source code that the interference graph could
> >> be done without the N x N graph array. Any hints welcome (Angel Faus!).
>
> > It looks like the way things are used in the code, you can use an
> > adjacency list instead of the current adjacency matrix for the graph.
>
> Yeah. Or a bitmap.
An adjacency list would definitely be much smaller, but I'd be
concerned that it would slow down searches too much. I think the
bitmap might be worth a try just to see how much the size matters.
Since this is an n^2 issue, splitting out the four different register
types could help -- except that I'd guess that most code with
excessive register usage probably uses one type of register much more
than the rest.
Anyway, I've attached a patch that uses bitmaps instead of SymReg*'s,
which should give a factor of 32 size reduction. I've only tested it
by doing a 'make test' and verifying that the several dozen test
failures are the same before and after (I don't think things are
actually that broken; I think the make system is), but for all I know
it's not even calling the code. That's what you get when I only have a
two hour hacking window and I've never looked at the code before.
> Or still better, create the interference graph per basic block.
> Should be much smaller then.
Huh? Is register allocation done wholly within basic blocks? I thought
the point of the graph was to compute interference across basic
blocks. I guess I should go and actually read the code.
Index: imcc/reg_alloc.c
===================================================================
RCS file: /cvs/public/parrot/imcc/reg_alloc.c,v
retrieving revision 1.14
diff -u -r1.14 reg_alloc.c
--- imcc/reg_alloc.c 23 Apr 2004 14:09:33 -0000 1.14
+++ imcc/reg_alloc.c 7 Aug 2004 07:11:08 -0000
@@ -41,7 +41,7 @@
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(int x, SymReg ** graph, int colors[], int typ);
+static int map_colors(IMC_Unit *, int x, int * graph, int colors[], int typ);
#ifdef DO_SIMPLIFY
static int simplify (IMC_Unit *);
#endif
@@ -58,12 +58,46 @@
/* XXX FIXME: Globals: */
static IMCStack nodeStack;
-static SymReg** interference_graph;
-/*
-static SymReg** reglist;
-*/
+static int* interference_graph;
static int n_symbols;
+static int* ig_get_word(int i, int j, int N, int* graph, int* bit_ofs)
+{
+ int bit = i * N + j;
+ *bit_ofs = bit % sizeof(*graph);
+ return &graph[bit / sizeof(*graph)];
+}
+
+static void ig_set(int i, int j, int N, int* graph)
+{
+ int bit_ofs;
+ int* word = ig_get_word(i, j, N, graph, &bit_ofs);
+ *word |= (1 << bit_ofs);
+}
+
+static void ig_clear(int i, int j, int N, int* graph)
+{
+ int bit_ofs;
+ int* word = ig_get_word(i, j, N, graph, &bit_ofs);
+ *word &= ~(1 << bit_ofs);
+}
+
+static int ig_test(int i, int j, int N, int* graph)
+{
+ int bit_ofs;
+ int* word = ig_get_word(i, j, N, graph, &bit_ofs);
+ return *word & (1 << bit_ofs);
+}
+
+static int* ig_allocate(int N)
+{
+ // size is N*N bits, but we want don't want to allocate a partial
+ // word, so round up to the nearest multiple of sizeof(int).
+ int need_bits = N * N;
+ int num_words = (need_bits + sizeof(int) - 1) / sizeof(int);
+ return (int*) calloc(num_words, sizeof(int));
+}
+
/* imc_reg_alloc is the main loop of the allocation algorithm. It operates
* on a single compilation unit at a time.
*/
@@ -446,6 +480,12 @@
/* creates the interference graph between the variables.
*
+ * data structure is a 2-d array 'interference_graph' where row/column
+ * indices represent the same index in the list of all symbols
+ * (unit->reglist) in the current compilation unit. The value in the
+ * 2-d array interference_graph[i][j] is the symbol unit->reglist[j]
+ * itself.
+ *
* two variables interfere when they are alive at the
* same time
*/
@@ -461,7 +501,7 @@
/* Construct a graph N x N where N = number of symbolics.
* This piece can be rewritten without the N x N array
*/
- interference_graph = calloc(n_symbols * n_symbols, sizeof(SymReg*));
+ interference_graph = ig_allocate(n_symbols);
if (interference_graph == NULL)
fatal(1, "build_interference_graph","Out of mem\n");
unit->interference_graph = interference_graph;
@@ -475,8 +515,8 @@
if (!unit->reglist[y]->first_ins)
continue;
if (interferes(unit, unit->reglist[x], unit->reglist[y])) {
- interference_graph[x*n_symbols+y] = unit->reglist[y];
- interference_graph[y*n_symbols+x] = unit->reglist[x];
+ ig_set(x, y, n_symbols, interference_graph);
+ ig_set(y, x, n_symbols, interference_graph);
}
}
}
@@ -801,8 +841,7 @@
allocate_wanted_regs(IMC_Unit * unit)
{
int i, y, interf;
- SymReg *r, *s;
- SymReg ** graph = interference_graph;
+ SymReg *r;
for (i = 0; i < n_symbols; i++) {
r = unit->reglist[i];
@@ -810,9 +849,13 @@
continue;
interf = 0;
for (y = 0; y < n_symbols; y++) {
- if ((s = graph[i*n_symbols+y])
- && s->color == r->want_regno
- && s->set == r->set) {
+ SymReg *s;
+ if (! ig_test(i, y, n_symbols, interference_graph))
+ continue;
+ s = unit->reglist[y];
+ if ( s
+ && s->color == r->want_regno
+ && s->set == r->set) {
interf = 1;
}
}
@@ -835,7 +878,7 @@
int x = 0;
int color, colors[MAX_COLOR];
int free_colors, t;
- SymReg ** graph = interference_graph;
+ int *graph = interference_graph;
SymReg ** reglist = unit->reglist;
while ((imcstack_depth(nodeStack) > 0) ) {
@@ -845,7 +888,7 @@
int typ = "INSP"[t];
memset(colors, 0, sizeof(colors));
if (reglist[x]->set == typ && reglist[x]->color == -1) {
- free_colors = map_colors(x, graph, colors, typ);
+ free_colors = map_colors(unit, x, graph, colors, typ);
if (free_colors > 0) {
for (color = 0; color < MAX_COLOR; color++) {
int c = (color + 16) % 32;
@@ -886,7 +929,7 @@
* map_colors: calculates what colors can be assigned to the x-th symbol.
*/
static int
-map_colors(int x, SymReg ** graph, int colors[], int typ)
+map_colors(IMC_Unit* unit, int x, int *graph, int colors[], int typ)
{
int y = 0;
SymReg * r;
@@ -901,7 +944,10 @@
colors[30] = 1; /* for immediate allocation */
#endif
for (y = 0; y < n_symbols; y++) {
- if ((r = graph[x*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;
@@ -985,13 +1031,15 @@
SymReg ** reglist = unit->reglist;
if (old != new) {
/* n_symbols is already increased */
- SymReg ** new_graph = calloc(n_symbols * n_symbols, sizeof(SymReg*));
+ 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++) {
- new_graph[x*n_symbols+y] = interference_graph[x*o+y];
- new_graph[y*n_symbols+x] = interference_graph[y*o+x];
+ 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);
@@ -1002,12 +1050,12 @@
if (reglist[x] == old || reglist[x] == new ||
reglist[y] == old || reglist[y] == new) {
if (interferes(unit, reglist[x], reglist[y])) {
- interference_graph[x*n_symbols+y] = reglist[y];
- interference_graph[y*n_symbols+x] = reglist[x];
+ ig_set(x, y, n_symbols, interference_graph);
+ ig_set(y, x, n_symbols, interference_graph);
}
else {
- interference_graph[x*n_symbols+y] = NULL;
- interference_graph[y*n_symbols+x] = NULL;
+ ig_clear(x, y, n_symbols, interference_graph);
+ ig_clear(y, x, n_symbols, interference_graph);
}
}
}
@@ -1151,27 +1199,6 @@
}
-#if 0
-static int
-neighbours(int node)
-{
- int y, cnt;
- SymReg *r;
-
- cnt = 0;
- for (y = 0; y < n_symbols; y++) {
-
- if ( (r = interference_graph[node*n_symbols + y] ) &&
- (!r->simplified) ) {
- cnt++;
- }
- }
-
- return cnt;
-}
-#endif
-
-
/*
* Local variables:
* c-indentation-style: bsd
Index: imcc/unit.h
===================================================================
RCS file: /cvs/public/parrot/imcc/unit.h,v
retrieving revision 1.6
diff -u -r1.6 unit.h
--- imcc/unit.h 22 Apr 2004 08:55:01 -0000 1.6
+++ imcc/unit.h 7 Aug 2004 07:11:08 -0000
@@ -31,7 +31,7 @@
/* register allocation */
int n_spilled;
SymReg * p31;
- SymReg** interference_graph;
+ int* interference_graph;
SymReg** reglist;
int n_symbols;
struct _IMC_Unit * prev;
