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

At 12:30 PM +0200 10/29/04, Leopold Toetsch wrote:
> Bill Coffman (via RT) wrote:
>
> > 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.
>
> Good. Hopefully Dan can provide some compile number compares.

I'll give it a shot as soon as I can.

> > 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.
>
> There probably were already some leaks. But we really have to get 
> rid of memory leaks alltogether.
>
> > - Interference graph is using 8 times the memory it needs to use. 
> > This is still trivial compared to lost data in above bug.
>
> That might kill Dan's 6000-liner.

I should point out, for the folks following along at home, that it's 
6K lines of source in the original language (DecisionPlus). The 
actual PIR code generated runs to 84k lines in the biggest sub.

> Some more notes WRT the patch:
>
> * the Dbg and Dbg2 debug macros aren't needed. Just use the existing 
> debug(interp, level, ...) function in src/debug.c. If you need some 
> extra levels, you can use some more bits in imcc/debug.h
>
> * The global G is a no no, and I don't think you need it for qsort 
> (If you need it you should just use the global around the qsort). We 
> finally have to have a reentrant compiler. Yes I know, there are 
> still some other globals around, they are being reduced ...

I'd like to get us down to a single global for all of Parrot. I don't 
think it's possible to safely go any lower than that, though I 
suppose we could if we really, really tried, and didn't mind things 
crashing and burning in some really odd fringe edge cases.

> * all functions should have an Interp* and a IMC_Unit* argument to 
> allow reentrancy. I.e. all state should be in the unit structure.

Definitely.

> * Variable names should be a bit more verbose, G.V is to terse.

Yeah. This stuff is abstruse enough as it is -- take pity on those uf 
us with Very Little Brain. :)

> * alloca() isn't portable and not available everywhere

Yep. This is a gcc-ism. Use Parrot's memory allocation functions instead.

> I'm waiting for Dan's comments on usability.

I'd like the code issues cleaned up before it gets committed. I'll 
let you know the timing as soon as I can, though it'll probably take 
a few hours.
--
                                Dan

--------------------------------------it's like this-------------------
Dan Sugalski                          even samurai
dan@xxxxxxxxx                         have teddy bears and even
                                      teddy bears get drunk