This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


On 12-10-11 5:53 PM, Peter Bergner wrote:
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. :)


Interesting. The max number passes is very dependent on the target. The biggest I saw was about 20 on a test on m68k
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.
Interesting approach to spill a spilled pseudo.

Although it is not wise to give a different color for spilled pseudos on targets without displacement issues. Small space for pseudos (by reusing slots) gives better data locality and smaller displacements which are important to reduce code size for targets having different size of insn displacement field for different displacements (e.g. x86). I know only one drawback of reusing stack slots. It is less freedom for insn-scheduling after RA. But still it is more important to reuse the stack than better 2nd insn scheduling at least for most widely used target x86/x86-64.

For targets with different displacement sizes, in my experience coloring is also not best algorithm for this. It usually results in smaller stack space but it has a tendency to evenly spread pseudos to different slots instead of putting important pseudos into slots with smaller displacements to generate smaller insns.

Just my observations, coloring is pretty good for register allocation. It works particularly well for unknown (or varying) execution profiles. But if you have exact execution profiles, there are heuristic approaches which could work better coloring.

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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]