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

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

Hello,

> > > > > I took a quick look, any decent rematerialization scheme would fix that
> > > > > up quite nicely.  There is nothing killing the loads, so nothing
> > > > > preventing them from being moved down to their uses.
> > > > 
> > > > depending on how the address of the loads is computed, moving a single
> > > > one of them may actually increase the number of registers needed, so
> > > > a straightforward greedy approach won't work.  I don't know about
> > > > approach that would not suffer from this type of local optimum problem
> > > > and in the same time would be fast enough to be usable for a compiler.
> > > 
> > > I will not go into a long detailed description, I did say decent
> > > rematerialization, not simple or greedy.
> > 
> > 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.  Of course it had to take some time
to come up with exact implementation details that produces the best results,
but the idea itself is just a simple greedy approach.

Zdenek

> >   Could you please provide some
> > reference so that I may check what you mean?
> 
> For regular approaches, see the optimistic register coalescing by park
> and moon.  It greedily coalesces but uncoalesces when necessary to get a
> register.  If you want to make it handle irregular architectures, see
> http://www.eecs.harvard.edu/~nr/pubs/gcra-abstract.html
> 
> 
> However, at least on SSA, you can do optimal coloring and optimal
> prespilling in linear time in ~96% of cases, and get linear time but not
> optimal in the rest:
> 
> (You can get 100% of the cases optimal if you had hardware that handled
> phi statements :P)
> 
> http://compilers.cs.ucla.edu/fernando/
> 
> Note that the prespilling is optimal because on a chordal graph, max
> clique size = number of colors required to color the graph.
> 
> Thus, if you split the graph into maximal cliques, in linear time, you
> now know what exactly is going to end up being spilled.
> 
> I pointed this paper out to some people mainly because it's simple and
> faster, and if you wanted a tree-on-ssa -> machine code path for O1/O2,
> I'd probably use it.
>