Newsgroups: perl.perl6.internals Path: g2news1.google.com!news1.google.com!newsfeed.stanford.edu!nntp.perl.org Return-Path: Mailing-List: contact perl6-internals-h...@perl.org; run by ezmlm Delivered-To: mailing list perl6-intern...@perl.org Received: (qmail 80463 invoked from network); 7 Aug 2004 16:21:39 -0000 Received: from x1.develooper.com (63.251.223.170) by onion.develooper.com with SMTP; 7 Aug 2004 16:21:39 -0000 Received: (qmail 22264 invoked by uid 225); 7 Aug 2004 16:21:39 -0000 Delivered-To: perl6-intern...@perl.org Received: (qmail 22260 invoked by alias); 7 Aug 2004 16:21:38 -0000 X-Spam-Status: No, hits=-4.9 required=8.0 tests=BAYES_00 X-Spam-Check-By: la.mx.develooper.com Received: from adsl-67-121-188-224.dsl.sntc01.pacbell.net (HELO dnsalias.org) (67.121.188.224) by la.mx.develooper.com (qpsmtpd/0.27.1) with ESMTP; Sat, 07 Aug 2004 09:21:36 -0700 Received: from localhost.localdomain (IDENT:0abpevQ2LgqiQA5tnyIbBy6FKZXTu...@localhost.localdomain [127.0.0.1]) by dnsalias.org (8.12.8/8.11.6) with ESMTP id i77GLuQH025541; Sat, 7 Aug 2004 09:21:57 -0700 Received: (from sfink@localhost) by localhost.localdomain (8.12.8/8.12.3/Submit) id i77GLt6k025539; Sat, 7 Aug 2004 09:21:55 -0700 Date: Sat, 7 Aug 2004 09:21:55 -0700 To: Leopold Toetsch Cc: perl6-intern...@perl.org Subject: [PATCH] Re: register allocation Message-ID: <20040807162155.GA25516@foxglove> Mail-Followup-To: Steve Fink , Leopold Toetsch , perl6-intern...@perl.org References: <41133881.5050009@toetsch.at> <200408071045.i77Aj9X26102@thu8.leo.home> Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="6c2NcOVqGQ03X4Wi" Content-Disposition: inline In-Reply-To: <200408071045.i77Aj9X26102@thu8.leo.home> User-Agent: Mutt/1.4.1i X-Virus-Checked: Checked X-Spam-Rating: onion.develooper.com 1.6.2 0/1000/N Approved: n...@nntp.perl.org From: st...@fink.com (Steve Fink) --6c2NcOVqGQ03X4Wi Content-Type: text/plain; charset=us-ascii Content-Disposition: inline On Aug-07, Leopold Toetsch wrote: > Sean O'Rourke wrote: > > l...@toetsch.at (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. --6c2NcOVqGQ03X4Wi Content-Type: text/plain; charset=us-ascii Content-Disposition: attachment; filename="bitmapped-ig.patch" 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; --6c2NcOVqGQ03X4Wi--