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
