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.
There's definitely weighting, but when you get up to the point where size matters the split may still be worth it. My Evil Program here has:
P temps: 26951 S temps: 2099 I temps: 8878
Definitely skewed, but going from n^2 (27838^2) to i^2+p^2+s^2 looks like it'd make quite a difference.
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.
I applied this patch, though it didn't change the results on my nasty programs. The size reduction seems worth it, though.
--
Dan
--------------------------------------it's like this-------------------
Dan Sugalski even samurai
[EMAIL PROTECTED] have teddy bears and even
teddy bears get drunk
