Re: register allocation vs. scheduling and other stuff

[Daniel Berlin <dberlin at dberlin dot org>]

On Monday, January 6, 2003, at 10:35  PM, tm wrote:

> On Mon, 6 Jan 2003, Robert Dewar wrote:
>
> > > The point I was trying to make that got lost in all the verbiage is
> > > that one might want to try to teach the register allocator a bit
> > > about scheduling rather than trying to teach the scheduler a bit 
> > > about
> > > register allocation.
> > At this point there are very good combined algorithms that are neither
> > of the above, but instead treat the allocation/scheduling problem as
> > a single problem with a unified solution.
> Will these combined algorithms handle register rematerialization,
> reload_cse, and other things cleanly? It sounds like it would become a
> huge, monolithic block of code.
I agree.
They also aren't necessarily doing better than a good scheduler and 
good allocator, in terms of runtime performance or compile time 
performance.

For the most part, the part you'd most want to combine the two for 
would be loops, which is what modulo scheduling (in some forms) would 
do for us.

If register usage is the main problem, then we could use a form of 
minimum register instruction sequencing (generating an instruction 
sequence S that is optimal in terms of the number of registers used) 
before register allocation, then after regalloc, let it go wild.

Their are relatively simple heuristics to give near-optimal results.
See http://citeseer.nj.nec.com/427865.html.

This might be interesting to implement, even if one doesn't want 
minimum register need all the time, just to see how good we *could* do 
(IE even if it was only used as a comparison point to see whether we 
even *could* do better on some test cases, assuming we do get some 
register pressure heuristics in the scheduler that are used instead)
> Toshi