On 10/01/2012 07:14 PM, Vladimir Makarov wrote:
Analogous live ranges are used in IRA as intermidiate step to build a
conflict graph. Actually, the first approach was to use IRA code to
assign hard registers to pseudos (e.g. Jeff Law tried this approach)
but it was rejected as requiring much more compilation time. In some
way, one can look at the assignment in LRA is a compromise between
quality (which could achieved through repeated buidling conflict graphs
and using graph coloring) and compilation speed.
Not only was it slow (iterating IRA), guaranteeing termination was a
major problem. There's some algorithmic games that have to be played
(they're at least discussed in literature, but not under the heading of
termination) and there's some issues specific to the IRA implementation
which make ensuring termination difficult.
I got nearly as good of results by conservative updates of the conflicts
after splitting ranges and (ab)using ira's reload hooks to give the new
pseudos for the split range a chance to be allocated again.
The biggest problem with that approach was getting the costing right for
the new pseudos. That requires running a fair amount of IRA a second
time. I'd still like to return to some of the ideas from that work as I
think some of the bits are still relevant in the IRA+LRA world.
My experience shows that these lists are usually 1-2 elements.
That's been my experience as well. The vast majority of the time the
range lists are very small.
Jeff
