RFC: LRA for x86/x86-64 [0/9]

[Vladimir Makarov]

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.
>