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

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.

> - Shortcomming: doesn't use score anymore, but the algorithm is smart
> enough that  I hope it's okay to do that.
> - Failed 2 tests for latest CVS.  (See earlier posting.)

I've fixed dumper.t in CVS. Only streams_11 is currently failing here.

> 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.

> - Color each of the four register types separately.  Be sure to
> compare gains with losses for this, as it is not entirely cear.

That would reduce memory, wouldn't it?

> - Introduce register renaming.  When variable is reassigned, it might
> as well be considered a new symbol... well, much of the time, anyway.

Number 1 in my priority list.

> - Introduce variable register size, in coordination with subroutine
> calls, to reduce copy cost.  Coordinate with Dan and Leo on this.

Not needed. We don't copy registers anymore.

> - Improve flow-graph, basic block calculation, etc.

Yeah. And create some means to test it.

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 ...

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

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

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

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

Thanks for the patch,
leo