This is the mail archive of the gcc@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: Register Allocation


Andrew MacLeod <amacleod@redhat.com> writes:

> > The current reload pass includes general heuristics to handle
> > reloading memory addresses.  This code knows things like "if stack
> > pointer plus displacement is not a valid memory address, try loading
> > the displacement into a register."  Many targets currently rely on
> > those heuristics to generate valid code.  I haven't been able to quite
> > pin down where this happens in your proposal.  For example, it's easy
> > for an address to use the frame pointer and be valid before reload,
> > and then for reload to eliminate the frame pointer (in fact, in your
> > scheme, what does frame pointer elimination?) and produce an offset
> > from the stack pointer which is invalid.  That is, spill code or frame
> > pointer elimination can generate invalid address, and something needs
> > to fix them up.  Where does that happen, and how?
> > 
> 
> 
> To be fair, I haven't given register elimination a lot of thought yet. I
> was presuming it could be inserted as a pass or as a separate component
> of the spiller.  Let me get back to you, I must investigate the
> issues :-). A couple of prime examples would be helpful :-)  I'll write
> up a new section for it.

The way gcc currently works, register elimination can not always be a
separate pass (naturally that might be different in your proposal).
The MIPS16, for example, requires a frame pointer if the frame size
does not fit in a signed 16-bit offset.  But the frame size can change
during the spilling process.  So you when you start spilling you might
think that you can use the stack pointer for all references to the
stack frame, and you might use the frame pointer as a general
register.  But then spilling might cause the stack frame to be 32768
bytes or larger.  So then you need to do the spilling (or, really,
global register allocation) all over again, but this time you can't
use the frame pointer.

However, in fairness, for most targets register elimination is based
on factors that don't change during the register allocation process,
like whether the function is a leaf or not.  In those cases you can
decide at the start of the spilling process exactly which registers
you can eliminate, and you could eliminate them in a separate pass.

Either way, register elimination can cause addresses which were valid
to become invalid, typically because valid offsets from the frame
pointer become invalid offsets from the stack pointer.  So that needs
to be cleaned up somewhere.  In current gcc, it's handled inside
reload, because it is a special case of the general case of pushing
constants into memory due to register constraints, or rematerializing
values from the stack or from global variables.

Waving my hands wildly, it seems to me that it's not quite enough to
have descriptions of how to spill every register class.  It seems to
me that you also need descriptions of how to handle each addressing
mode, and in particular how to convert invalid addresses generated
during the register elimination or spilling process into valid
addresses.  This is straightforward for most CPUs, but can get
moderately ugly for something like 68020 (where you have a lot of
choices) or SH (where practically everything needs to use r0).


> Scheduling should be able to use heuristics and perhaps some of the
> tools of the allocator (such as register pressure and number of register
> available) to prevent itself from being too stupid if so desired.

The way gcc currently works, it's really hard for the scheduler to
have decent, portable, register pressure heuristics, because we
haven't done instruction selection and we haven't generated spill
code.  I spent a lot of time optimizing for XScale, and having reload
insert an unexpected register spill can be a 10% performance hit.

I think that what I would like to see out of the scheduler would be
some way to say things like "if you find you have to spill at
instruction X, try moving instruction Y from before instruction X to
after instruction X and see if that gives you better register
allocation."

But this is pie in the sky stuff anyhow.

Thanks for your reply.

Ian


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