Re: [patch] Fix behavior of TER on unrolled loops

[Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>]

Hello,

> > > > does anything like that exist? All the RA algorithms I have seen so far
> > > > were pretty simple greedy approaches.
> > > 
> > > Pretty simple greedy approaches?
> > > I've not seen an RA paper in the past 10 years that was a simple
> > > approach until a few weeks ago.
> > 
> > we obviously have different measure on what "a simple approach" is.
> > For example the paper you cite below (Park and Moon) is a simple
> > heuristic as far as I am concerned. 
> 
> By that measure, everything but ILP register allocation is a simple
> heuristic.

sorta kinda.  There are various other approaches to graph coloring
(which of course by itself is just a simplification to the problem) that
probably could be applied, but do not fit very well into the time
limits imposed by compilers.  For architectures with few registers,
dynamic programming approaches (which in some cases can be viewed as
reformulation of ILP) might be feasible.

> Google for optimal register allocation and you'll find a bunch of papers
> that try to take *everything* into account.
> You'll discover that except for coalescing, the "simple approaches"
> actually aren't more than ~3% off completely optimal approaches that
> take literally everything into account.

The only thing I ever said is that all of the "simple approaches" suffer
from the local minimum type problems, and that their behavior is too
unreliable and unpredictable to claim things like "this is only a
workaround that we will be able to remove once we improve RA".

Zdenek