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;