This is the mail archive of the
mailing list for the GCC project.
Re: Improving reload inheritance code generation and predictability
- From: Vladimir Makarov <vmakarov at redhat dot com>
- To: Jeff Law <law at redhat dot com>
- Cc: gcc-patches <gcc-patches at gcc dot gnu dot org>
- Date: Thu, 18 Nov 2010 16:27:15 -0500
- Subject: Re: Improving reload inheritance code generation and predictability
- References: <4CE53C3D.firstname.lastname@example.org>
On 11/18/2010 09:46 AM, Jeff Law wrote:
I have been continually vexed by the "joys" of reload inheritance. In
particular its near randomness in identifying inheritance opportunities.I like this idea and also thought long ago to try it too. Because of
better inheritance I think it should show some code size improvement and
probably some performance improvement too besides better debugging.
The fundamental problem is how we select a spill register. Right now
we keep track of what hard regs are spill regs and we use them in a
round-robin fashion. The idea is by using them in a round-robin
fashion, a spill reg holds a useful value for a longer period of time,
which in turn means we're more likely to find a reload inheritance
optimization opportunity. Understandable, but it can be quite
annoying in practice.
The problem with this is subtle changes in what's presented to reload
changes the spills, which in turn changes which spill registers are
selected for a particular insn needing spills. That in turn can mask
or unmask reload inheritance opportunities, effectively at random
because of the round robin selection of spill regs.
The randomness makes it extremely difficult to track down regressions
in the range splitting code -- not to mention that it's totally silly
that eliminating a reload somewhere in the stream suddenly causes an
inheritance opportunity to be missed because last_reload_reg didn't
get bumped due to the elimination of an unrelated reload.
So while I hate the inheritance code and loathe to spend time making
it better, I just can't justify spending a days looking for these
kinds of regresions. So attached you'll find a revamping of how we
choose a register from the set of spill registers.
Basically we start searching forward in the stream from the current
insn needing a reload noting uses of spill regs as we go. The further
away from the insn needing reloads the spill reg is used the more
desirable that spill reg becomes. If we can't find all the spill regs
before reaching the end of the block, the remaining spill regs are
considered the most desirable and we allocate these stragglers in the
The net result is that a spill reg holds a useful value for an even
longer stretch of insns which in turn exposes more reload inheritance
opportunities. Furthermore, reload inheritance becomes more stable in
the opportunities it finds.
Obviously this has to be queued for stage1, but I wanted to get any
I am afraid only that it will take some compilation time too (which will
be probably compensated partially by less final insns processing) and
IMHO that is not because of insn traversing but mostly because of usage
Some time ago I analyzed how many memory is used by DF during an IRA
snapshot. It was about 25% vs 7% allocated by IRA for its IR (% of all
heap memory). Touching this huge footprint will worse code locality and
result in slow code.
Reload does not use DF and even automatic insn rescanning is switched
off. I believe that if reload were rewritten to use DF, it could result
in much slower code. This is just some my speculations which really
hard to confirm or reject.