Question about constraints and reload

Question about constraints and reload

[Steven Bosscher]

Hi,

In recog.c there are a few places in constrain_operands() where we have
code like this,

            /* Before reload, accept what reload can turn into mem.  */
            else if (strict < 0 && CONSTANT_P (op))
              win = 1;

See cases 'm', 'o', and the default case.

What is this necessary for, is there any reason to rely on reload to
turn a constant into a MEM?

Gr.
Steven

Re: Question about constraints and reload

[Geoffrey Keating]

Steven Bosscher <stevenb@suse.de> writes:
> is there any reason to rely on reload to turn a constant into a MEM?

Yes, there is.

Consider rs6000, where there's no instruction to load a constant into
a FP register, but it's pretty easy to get a constant into a GPR.
Suppose reload is seeing a pattern like

(mov:SF (reg:SF 1234) (const_double:SF 0))

if it decides that register 1234 should be allocated to a GPR (for
instance, because it's going to be a parameter to a varargs function),
this can be coded as a 'li' instruction, an immediate load.  If it
decides to allocate it to a FPR (for instance, because it's about to
be compared with another FP value), it must be coded as a 'lfs'
instruction, a floating-point load, of a value in the constant pool.
If the zero's just being stored out to somewhere else, either choice
is acceptable and which should be picked would depend on what
registers are available.

Re: Question about constraints and reload

[Andrew Pinski]

On Sep 26, 2004, at 5:30 PM, Geoffrey Keating wrote:

> Steven Bosscher <stevenb@suse.de> writes:
>> is there any reason to rely on reload to turn a constant into a MEM?
>
> Yes, there is.
>
> Consider rs6000, where there's no instruction to load a constant into
> a FP register, but it's pretty easy to get a constant into a GPR.
> Suppose reload is seeing a pattern like
>
> (mov:SF (reg:SF 1234) (const_double:SF 0))
>
> if it decides that register 1234 should be allocated to a GPR (for
> instance, because it's going to be a parameter to a varargs function),
> this can be coded as a 'li' instruction, an immediate load.  If it
> decides to allocate it to a FPR (for instance, because it's about to
> be compared with another FP value), it must be coded as a 'lfs'
> instruction, a floating-point load, of a value in the constant pool.
> If the zero's just being stored out to somewhere else, either choice
> is acceptable and which should be picked would depend on what
> registers are available.

But this breaks some testcases, see PR 17606 for an example where this
causes some problems.

-- Pinski

Re: Question about constraints and reload

[Geoff Keating]

[-- Attachment #1: Type: text/plain, Size: 1581 bytes --]


On 26/09/2004, at 2:35 PM, Andrew Pinski wrote:

>
> On Sep 26, 2004, at 5:30 PM, Geoffrey Keating wrote:
>
>> Steven Bosscher <stevenb@suse.de> writes:
>>> is there any reason to rely on reload to turn a constant into a MEM?
>>
>> Yes, there is.
>>
>> Consider rs6000, where there's no instruction to load a constant into
>> a FP register, but it's pretty easy to get a constant into a GPR.
>> Suppose reload is seeing a pattern like
>>
>> (mov:SF (reg:SF 1234) (const_double:SF 0))
>>
>> if it decides that register 1234 should be allocated to a GPR (for
>> instance, because it's going to be a parameter to a varargs function),
>> this can be coded as a 'li' instruction, an immediate load.  If it
>> decides to allocate it to a FPR (for instance, because it's about to
>> be compared with another FP value), it must be coded as a 'lfs'
>> instruction, a floating-point load, of a value in the constant pool.
>> If the zero's just being stored out to somewhere else, either choice
>> is acceptable and which should be picked would depend on what
>> registers are available.
>
> But this breaks some testcases, see PR 17606 for an example where this
> causes some problems.

The fact that the chip is like this doesn't 'break' anything; it is 
perfectly possible to create a compiler that can generate good code for 
such a chip, and in fact the infrastructure in GCC is designed to be 
able to cope with the kinds of situation I described.  The problem is 
that there are reload and/or backend bugs that cause this to go wrong.  
The solution is to find the bugs and fix them.

[-- Attachment #2: smime.p7s --]
[-- Type: application/pkcs7-signature, Size: 2410 bytes --]

Re: Question about constraints and reload

[Geoff Keating]

[-- Attachment #1: Type: text/plain, Size: 1581 bytes --]


On 26/09/2004, at 2:35 PM, Andrew Pinski wrote:

>
> On Sep 26, 2004, at 5:30 PM, Geoffrey Keating wrote:
>
>> Steven Bosscher <stevenb@suse.de> writes:
>>> is there any reason to rely on reload to turn a constant into a MEM?
>>
>> Yes, there is.
>>
>> Consider rs6000, where there's no instruction to load a constant into
>> a FP register, but it's pretty easy to get a constant into a GPR.
>> Suppose reload is seeing a pattern like
>>
>> (mov:SF (reg:SF 1234) (const_double:SF 0))
>>
>> if it decides that register 1234 should be allocated to a GPR (for
>> instance, because it's going to be a parameter to a varargs function),
>> this can be coded as a 'li' instruction, an immediate load.  If it
>> decides to allocate it to a FPR (for instance, because it's about to
>> be compared with another FP value), it must be coded as a 'lfs'
>> instruction, a floating-point load, of a value in the constant pool.
>> If the zero's just being stored out to somewhere else, either choice
>> is acceptable and which should be picked would depend on what
>> registers are available.
>
> But this breaks some testcases, see PR 17606 for an example where this
> causes some problems.

The fact that the chip is like this doesn't 'break' anything; it is 
perfectly possible to create a compiler that can generate good code for 
such a chip, and in fact the infrastructure in GCC is designed to be 
able to cope with the kinds of situation I described.  The problem is 
that there are reload and/or backend bugs that cause this to go wrong.  
The solution is to find the bugs and fix them.

[-- Attachment #2: smime.p7s --]
[-- Type: application/pkcs7-signature, Size: 2410 bytes --]

Re: Question about constraints and reload

[Ulrich Weigand]

Steven Bosscher wrote:

>What is this necessary for, is there any reason to rely on reload to
>turn a constant into a MEM?

Certainly!  Reload will, as one of its options, force a constant to
the literal pool, thereby turning the operand into a MEM.  The s390
port relies extensively on that feature, because we can only use a
limited set of immediate operands, and these differ widely between
different instructions.  Thus the best way to handle constants is
to allow them more or less freely before reload, and have reload
choose to use either an actual immediate operand where available,
reload the constant into a register, or else push it into the
literal pool.

Bye,
Ulrich

-- 
  Dr. Ulrich Weigand
  weigand@informatik.uni-erlangen.de

Re: Question about constraints and reload

[Steven Bosscher]

On Saturday 25 September 2004 16:56, Ulrich Weigand wrote:
> Steven Bosscher wrote:
> >What is this necessary for, is there any reason to rely on reload to
> >turn a constant into a MEM?
>
> Certainly!  Reload will, as one of its options, force a constant to
> the literal pool, thereby turning the operand into a MEM.  The s390
> port relies extensively on that feature, because we can only use a
> limited set of immediate operands, and these differ widely between
> different instructions.  Thus the best way to handle constants is
> to allow them more or less freely before reload, and have reload
> choose to use either an actual immediate operand where available,
> reload the constant into a register, or else push it into the
> literal pool.

Maybe it's the *easiest* way for your port and other ports to handle
constants this way, but it may not be the "best way" ;-)  I suppose
you would want to keep constants around mostly for optimization, but
do we still need that, if the tree optimizers do most of the work?

These loose constraints looks like the kind of thing that make it so
hard to write a decent register allocator.
In some discussions about that recently on IRC (I plan to turn the log
of that into a Wiki page), one of the things the new-ra people mentioned,
was that the constraints on register classes and strict constraints on
insn operands were notsatisfied during register allocation.  This would
cause reload to sort of redo the whole register allocation even after
new-ra was done.

With reload turning a constant into a MEM and (probably) a load to a
register, I would guess you introduce new register uses in reload, and
suddenly it's not that surprising that reload has to redo new-ra's work.

So I thought perhaps we should be more strict about satisfying operand
constraints before reload.  Hence my question.

Perhaps we can experiment with putting non-legitimate constants into the
constant pool and turn them into MEMs somewhere *before* greg and reload.
Perhaps even already somewhere late in the tree optimizers (turn them 
into CONST_DECLs), or otherwise in some pre-regalloc pass.

Gr.
Steven

Re: Question about constraints and reload

[Ulrich Weigand]

Steven Bosscher wrote:

> With reload turning a constant into a MEM and (probably) a load to a
> register, I would guess you introduce new register uses in reload, and
> suddenly it's not that surprising that reload has to redo new-ra's work.

Eh?  Reload introduces new register uses all the time, for many different
purposes (e.g. address reloads).  The force-const-to-mem is actually one
of the few operations reload does that typically does *not* need a new
register.

> So I thought perhaps we should be more strict about satisfying operand
> constraints before reload.  Hence my question.

This is kind of contradictory -- the primary purpose of the reload pass
is to satisfy operand constraints.  If they were always satisfied before
reload we wouldn't need it ...

> Perhaps we can experiment with putting non-legitimate constants into the
> constant pool and turn them into MEMs somewhere *before* greg and reload.
> Perhaps even already somewhere late in the tree optimizers (turn them 
> into CONST_DECLs), or otherwise in some pre-regalloc pass.

The problem is that there isn't a single set of non-legitimate constants
vs. legitimate constants.  What's legitimate depends very much on the
particular assembler instruction -- in some cases it's impossible to
tell on the tree level which constants are legitimate; even on the *rtl*
level it may not be possible to decide before reload has actually 
chosen an insn alternative.

Bye,
Ulrich

-- 
  Dr. Ulrich Weigand
  weigand@informatik.uni-erlangen.de

Re: Question about constraints and reload

[Steven Bosscher]

On Saturday 25 September 2004 18:39, Ulrich Weigand wrote:
> > So I thought perhaps we should be more strict about satisfying operand
> > constraints before reload.  Hence my question.
>
> This is kind of contradictory -- the primary purpose of the reload pass
> is to satisfy operand constraints.  If they were always satisfied before
> reload we wouldn't need it ...

That's not a contradiction, it's the whole point ;-)
You conveniently ignored my remark about reload redoing almost complete
register allocations after the register allocator.  Apparently you do not
think that is odd.

We'll probably always need reload of some form.  But one way or another
we will have to provide an instruction stream to the register allocator on
which it can do its job properly, without getting overruled by reload.
Of course, "force-const-to-mem" is only one problem.  And if you're right
about it typically not needing a new reg, not even a serious one compared
to some others.

> The problem is that there isn't a single set of non-legitimate constants
> vs. legitimate constants.  

:-(

Gr.
Steven

Re: Question about constraints and reload

[Ulrich Weigand]

Steven Bosscher wrote:

> You conveniently ignored my remark about reload redoing almost complete
> register allocations after the register allocator.  Apparently you do not
> think that is odd.

I don't see reload as redoing register allocation.  As I said, I my view
the primary purpose of reload is to choose operands in a way to best fit
the available machine instructions.

I agree that the way this task is currently intertwined with generating
spill code required to satisfy register pressure is not optimal.  Handling
spill code as just one variant of reloads generates very inefficient code;
and while reload avoids that extreme by measures like reload inheritance
and post-reload CSE, all this is not only quite fragile, but not as
efficient as it probably could be ...

> We'll probably always need reload of some form.  But one way or another
> we will have to provide an instruction stream to the register allocator on
> which it can do its job properly, without getting overruled by reload.

My feeling is that this order may not work well; the final decision on
which instruction forms to choose should IMO stay with reload or something
like it, but it should be integrated with a proper register allocator
to implement all the spill code.  (Maybe similar to how the reload
currently calls back into the register allocator for re-evaluation
after reload itself has generated additional register pressure; only
that the (old) register allocator doesn't do any spilling.)

Anyway, I haven't really looked into this issue in detail, so feel
free to ignore me. ;-)  I just don't think that you can handle the
intricate machine-specific details all up-front, and then run a 
generic algorithm; it usually needs to be the other way round
(or completly integrated with each other in the first place).

Bye,
Ulrich

-- 
  Dr. Ulrich Weigand
  weigand@informatik.uni-erlangen.de

Re: Question about constraints and reload

[tm_gccmail]

On Sat, 25 Sep 2004, Steven Bosscher wrote:

> On Saturday 25 September 2004 16:56, Ulrich Weigand wrote:
> > Steven Bosscher wrote:
> > >What is this necessary for, is there any reason to rely on reload to
> > >turn a constant into a MEM?
> >
> > Certainly!  Reload will, as one of its options, force a constant to
> > the literal pool, thereby turning the operand into a MEM.  The s390
> > port relies extensively on that feature, because we can only use a
> > limited set of immediate operands, and these differ widely between
> > different instructions.  Thus the best way to handle constants is
> > to allow them more or less freely before reload, and have reload
> > choose to use either an actual immediate operand where available,
> > reload the constant into a register, or else push it into the
> > literal pool.
> 
> Maybe it's the *easiest* way for your port and other ports to handle
> constants this way, but it may not be the "best way" ;-)  I suppose
> you would want to keep constants around mostly for optimization, but
> do we still need that, if the tree optimizers do most of the work?
>
> (bits removed for brevity)
>
> Perhaps we can experiment with putting non-legitimate constants into the
> constant pool and turn them into MEMs somewhere *before* greg and reload.
> Perhaps even already somewhere late in the tree optimizers (turn them 
> into CONST_DECLs), or otherwise in some pre-regalloc pass.

This fits nicely into the midRTL/targetRTL paradigm.

The register allocator will still need to generate literal pool entries
for accessing deep stacks on machines with limited displacements on
indirect addressing modes, however.

> Gr.
> Steven

Toshi

Re: Question about constraints and reload

[tm_gccmail]

On Sat, 25 Sep 2004, Steven Bosscher wrote:

> <snip>
>
> Perhaps we can experiment with putting non-legitimate constants into the
> constant pool and turn them into MEMs somewhere *before* greg and reload.
> Perhaps even already somewhere late in the tree optimizers (turn them 
> into CONST_DECLs), or otherwise in some pre-regalloc pass.
> 
> Gr.
> Steven

Steven just prodded me into posting a more verbose reply, so here are my
recent thoughts on this subject - my apologies if I ramble somewhat, since
it's so early in the morning.

Regarding reload:

Some other functionality of reload which seem obvious to move
into a separate pass (besides literal pool generation) are:

o 3AC to 2AC conversion
o reload_cse (which IMHO should be handled in the regalloc - see below)

Regarding register allocation:

When we do a new register allocator:

We really need to defer assignment of stack locations for automatics until
the register allocation pass. This would be nice for multiple reasons,
such as more efficient code generation on short displacement targets and
the ability to pack HImode/QImode stack slots, ability to merge stack
slots with non-overlapping lifetimes, etc.

We really needs a target-dependent hook to allow reordering of the stack
slots before any code is generated. We did this as a Renesas project, and
saw a significant performance improvement on the SH; it should also help
MIPS16/Thumb signification, and even Alpha/PPC/MIPS targets if somebody
allocates a 32k array at the bottom of the stack.

We really need to make it easily extensible to handle different methods of
reducing register pressure, like live-range splitting, complex
rematerialization (like Mukta did), etc. We encountered a lot of problems
modifying new-ra to handle complex remat; it would be nice if the next ra
was more easily extensible.

Toshi

Re: Question about constraints and reload

[Peter Barada]

>We really needs a target-dependent hook to allow reordering of the stack
>slots before any code is generated. We did this as a Renesas project, and
>saw a significant performance improvement on the SH; it should also help
>MIPS16/Thumb signification, and even Alpha/PPC/MIPS targets if somebody
>allocates a 32k array at the bottom of the stack.

M68000/Coldfire gets a benifit from this as well since they can only
do signed 16 bit offset addressing from the frame/stack pointer.

-- 
Peter Barada
peter@the-baradas.com

Re: Question about constraints and reload

[Ulrich Weigand]

Peter Barada wrote:
> >We really needs a target-dependent hook to allow reordering of the stack
> >slots before any code is generated. We did this as a Renesas project, and
> >saw a significant performance improvement on the SH; it should also help
> >MIPS16/Thumb signification, and even Alpha/PPC/MIPS targets if somebody
> >allocates a 32k array at the bottom of the stack.
> 
> M68000/Coldfire gets a benifit from this as well since they can only
> do signed 16 bit offset addressing from the frame/stack pointer.

S/390 would benefit as well.

Bye,
Ulrich

-- 
  Dr. Ulrich Weigand
  weigand@informatik.uni-erlangen.de

Re: Question about constraints and reload

[Richard Kenner]

    I don't see reload as redoing register allocation.  

Nor do I, but I see where the sentiment is coming from.  If you have a machine
with a very small number of registers, what reload will essentially do is
evict almost everything from hard regs and load everything itself.  But I'm
not sure I'd call that "allocation".