Re: Improving reload inheritance code generation and predictability

[Jeff Law <law at redhat dot com>]

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

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


jeff