On 10/02/2012 12:22 AM, Jeff Law wrote:
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.
Chaitin-Briggs literature does not discuss the termination, just saying
that live-ranges shortening will result to assigning hard regs to all
necessary pseudos which is not clearly guaranteed. There is the same
problem in LRA. So LRA checks that too many passes are done or to many
reloads for one insn are made and abort LRA. Porting LRA is mostly
fixing such aborts.
Another thing omitted by literature is inheritance which is very
important for performance. Although it could be considered as a special
case of live-range splitting. There are also a lot of small important
details (e.g. what to do in case of displacement constraints, or when
non-load/store insns permits memory and registers etc) not discussed
well or at all in the literature I read.
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.