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/10 12:43, Richard Henderson wrote:
On 11/18/2010 11:34 AM, Bernd Schmidt wrote:
On 11/18/2010 03:46 PM, Jeff Law wrote:
Basically we start searching forward in the stream from the current insn
needing a reload noting uses of spill regs as we go.
Isn't this quadratic in the number of insns?
It depends on how soon we find all of the spills.

If we fail to find them all, for every insn, then yes quadratic
on the size of the block.  If there's 1 spill per insn and we
always find it at the next insn, then it's linear.

Perhaps Jeff has some data on how much scanning we do in practice?
Not exactly.

We're looking for uses/sets of registers that we already know are used as spill registers somewhere in the current function. So the number of spills per insn isn't particularly relevant. What is relevant is the distance (in insns) from the current insn to the point where we're able to find a use/set of each spill register in use somewhere in the current function.

Per my recent message, with a couple minor improvements we're scanning 7.5 insns per call to allocate_reload_reg while bootstrapping GCC (without java). However, it's easy to argue that some kind of PARAM is needed here to avoid particularly bad behaviour -- within libgcc itself (bid_round) we average 60 insns scanned per call to allocate_reload_reg. And something like fpppp would be even worse, on the order of hundreds or thousands of insns scanned per call.

Alternatively we just table the whole thing and I keep this private on the branch merely to make evaluation of range splitting & new reload code easier. But given this does improve code, I wanted to put it out to the community and get some opinions.


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