This is the mail archive of the 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: Improving reload inheritance code generation and predictability

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.

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 round-robin fashion.

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 thoughts/comments early...

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.

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 of DF-infrastructure.

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.

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