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

[Peter Bergner <bergner at vnet dot ibm dot com>]

On Tue, 2012-10-02 at 10:57 -0400, Vladimir Makarov wrote:
> 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.

IIRC, talking with the guys from Rice, they had a limit on the number of
color/spill iterations (20) before aborting, since anything more than
that would be due to a bug.  I believe the largest number of iterations
I ever saw in my allocator was about 6 iterations of color/spill.  I hit
a few cases that iterated forever, but those were always due to bugs in
my code or special hairy details I hadn't handled.  You're correct that
the hairy details are never discussed in papers. :)



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

To handle displacement constraints, instead of spilling to stack slots,
we spilled to spill pseudos which look like normal register pseudos.
We would then color them just like normal pseudos, but the colors
represent stack slots and not registers.  If "k" becomes too big, it
means you surpassed the maximum displacement, and you'll have to spill
the spill pseudo.  For small displacement cpus, coloring the spill pseudos
does a good job reusing stack slots which reduces the largest displacement
you'll see.  For cpus with no displacement issues, you could just give
each spill pseudo a different color which would mean you wouldn't have
to compute a interference graph of the spill pseudos and all the work
and space that goes into building that.

Note, with spill pseudos, you can perform dead code elimination, coalescing
and other optimizations on them just like normal pseudos to reduce the
amount of spill code generated.

Peter