Re: condition codes, haifa-sched and virtual-stack-vars

Re: condition codes, haifa-sched and virtual-stack-vars

[Ulrich Weigand]

Greg McGary wrote:

>Here's a summary of mutations, by optimizer phase.

[snip reload generating addsi insn clobbering CC]

>Things would have been OK if the stack var weren't the first one,
>so that it got an offset in 00.rtl, and the associated clobber.
>Maybe we shouldn't emit bare virtual-stack-vars, but rather emit as
>plus with 0 offset?

I've been fighting exactly this problem on s390 ever since
we changed from cc0 to an explicit CC register :-(

The problem is that reload simply calls gen_add2_insn whenever it
feels like it, without consideration that this might introduce
a CC clobber at an inappropriate point ...

The only way I've found around this is to use some insn that
performs an addition without clobbering CC; on many architectures
some sort of 'load-address' instruction can be used for this.
E.g. on i386, every addition reload wants to perform appears to
fit the 'lea' pattern, so they don't have the problem.

On s390, while we do have a load-address pattern, it is somewhat
restricted (e.g. it accepts only immediate offsets in the 0..4095
range).  I've tried to trick reload into using LA anyway, by 
providing a generic 'add' pattern and splitters to massage the
result into a form acceptable by LA afterward.

There might be other options, e.g. converting addsi3 into an
expander that generates different code when called while
reload_in_progress, or using a secondary input reload to 
handle PLUS reloads ...

If you don't have any sort of load-address instruction, I don't
know what to do either.

Bye,
Ulrich

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

Re: condition codes, haifa-sched and virtual-stack-vars

[Geoff Keating]

Ulrich Weigand <weigand@immd1.informatik.uni-erlangen.de> writes:

> Greg McGary wrote:
> 
> >Here's a summary of mutations, by optimizer phase.
> 
> [snip reload generating addsi insn clobbering CC]
> 
> >Things would have been OK if the stack var weren't the first one,
> >so that it got an offset in 00.rtl, and the associated clobber.
> >Maybe we shouldn't emit bare virtual-stack-vars, but rather emit as
> >plus with 0 offset?
> 
> I've been fighting exactly this problem on s390 ever since
> we changed from cc0 to an explicit CC register :-(
> 
> The problem is that reload simply calls gen_add2_insn whenever it
> feels like it, without consideration that this might introduce
> a CC clobber at an inappropriate point ...

On xstormy16, this problem existed with the carry register.  I believe
it was fixed by having a reload_inhi pattern and an appropriate
definition of SECONDARY_RELOAD_CLASS.  The result appears to work.

-- 
- Geoffrey Keating <geoffk@geoffk.org> <geoffk@redhat.com>

Re: condition codes, haifa-sched and virtual-stack-vars

[Ulrich Weigand]

Geoff Keating wrote:

> Ulrich Weigand <weigand@immd1.informatik.uni-erlangen.de> writes:
> 
> > The problem is that reload simply calls gen_add2_insn whenever it
> > feels like it, without consideration that this might introduce
> > a CC clobber at an inappropriate point ...
> 
> On xstormy16, this problem existed with the carry register.  I believe
> it was fixed by having a reload_inhi pattern and an appropriate
> definition of SECONDARY_RELOAD_CLASS.  The result appears to work.

This is interesting, but I'm not sure I understand *why* it works ;-)

The reload_inhi pattern tries to allocate the carry register as the
secondary reload scratch register.  Now, in the interesting case 
where the carry register is in fact live at the location where the
insn is inserted, this would mean that reload would need to spill
the carry register and later on restore its old value, right?
(Because there is only a single register in this class ...)

However, I'm not sure how the carry register can be spilled,
given that there is no mov* insn that touches it, unless I'm
missing something ...

Bye,
Ulrich

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

Re: condition codes, haifa-sched and virtual-stack-vars

[Geoff Keating]

> From: Ulrich Weigand <weigand@immd1.informatik.uni-erlangen.de>
> Date: Thu, 31 Jan 2002 00:16:59 +0100 (MET)
> Cc: weigand@immd1.informatik.uni-erlangen.de (Ulrich Weigand), gcc@gcc.gnu.org
> X-OriginalArrivalTime: 30 Jan 2002 23:24:42.0937 (UTC) FILETIME=[4BEAD290:01C1A9E5]
> 
> Geoff Keating wrote:
> 
> > Ulrich Weigand <weigand@immd1.informatik.uni-erlangen.de> writes:
> > 
> > > The problem is that reload simply calls gen_add2_insn whenever it
> > > feels like it, without consideration that this might introduce
> > > a CC clobber at an inappropriate point ...
> > 
> > On xstormy16, this problem existed with the carry register.  I believe
> > it was fixed by having a reload_inhi pattern and an appropriate
> > definition of SECONDARY_RELOAD_CLASS.  The result appears to work.
> 
> This is interesting, but I'm not sure I understand *why* it works ;-)
> 
> The reload_inhi pattern tries to allocate the carry register as the
> secondary reload scratch register.  Now, in the interesting case 
> where the carry register is in fact live at the location where the
> insn is inserted, this would mean that reload would need to spill
> the carry register and later on restore its old value, right?
> (Because there is only a single register in this class ...)

No, reload_inhi doesn't allocate anything; that's done by
SECONDARY_RELOAD_CLASS.  reload_inhi is just to explain to reload how
to put the carry register into the add instruction.

> However, I'm not sure how the carry register can be spilled,
> given that there is no mov* insn that touches it, unless I'm
> missing something ...

Yes, the case of spills is tricky, which is why we pretty much avoid
it on xstormy16 :-).  In the general case, you'd have to explain how
to spill and restore the carry register.  xstormy16 has the additional
problem that certain branches can clobber the carry register, which is
why it can't really be spilled (because reload is not smart enough to
restore it after a branch).

-- 
- Geoffrey Keating <geoffk@geoffk.org> <geoffk@redhat.com>

Re: condition codes, haifa-sched and virtual-stack-vars

[Richard Henderson]

On Wed, Jan 30, 2002 at 10:41:43PM +0100, Ulrich Weigand wrote:
> On s390, while we do have a load-address pattern, it is somewhat
> restricted (e.g. it accepts only immediate offsets in the 0..4095
> range).  I've tried to trick reload into using LA anyway, by 
> providing a generic 'add' pattern and splitters to massage the
> result into a form acceptable by LA afterward.

On i386 we have a peephole2 that converts lea to add if the
flags register is dead.


r~

Re: condition codes, haifa-sched and virtual-stack-vars

[Ulrich Weigand]

Richard Henderson wrote:

> On Wed, Jan 30, 2002 at 10:41:43PM +0100, Ulrich Weigand wrote:
> > On s390, while we do have a load-address pattern, it is somewhat
> > restricted (e.g. it accepts only immediate offsets in the 0..4095
> > range).  I've tried to trick reload into using LA anyway, by 
> > providing a generic 'add' pattern and splitters to massage the
> > result into a form acceptable by LA afterward.
> 
> On i386 we have a peephole2 that converts lea to add if the
> flags register is dead.

Thanks for the tip, I'll look into that approach on s390.

Bye,
Ulrich

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

Re: condition codes, haifa-sched and virtual-stack-vars

[Ulrich Weigand]

Following up on myself:

> The reload_inhi pattern tries to allocate the carry register as the
> secondary reload scratch register.  Now, in the interesting case 
> where the carry register is in fact live at the location where the
> insn is inserted, this would mean that reload would need to spill
> the carry register and later on restore its old value, right?
> (Because there is only a single register in this class ...)
> 
> However, I'm not sure how the carry register can be spilled,
> given that there is no mov* insn that touches it, unless I'm
> missing something ...

Hmm, what I was missing was that apparently the carry register
can *never* be live during reload, as all insns that actually
use it (except for just a clobber) are *only* ever emitted from 
splitters after reload.

So what I called the 'interesting case' above never happens ...


Bye,
Ulrich

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

condition codes, haifa-sched and virtual-stack-vars

[Greg McGary]

I have a GCC port to a custom RISC that uses condition codes in an
explicit register (doesn't use cc0).  GCC generates bogus code when
expanding an inline.  One of the inline's args is the address of an
automatic, so it is passed to the inline as a move from
virtual-stack-vars to a pseudo.  Later, there's a conditional branch
on bitfield test that expands as bitfield-extract (shift + and),
comparison wtih zero, and branch.  All harmless so far.

Haifa-sched schedules the move from virtual-stack-vars between the
bitfield test sequence and the branch.  Later, global-reg alloc
instantiates virtual-stack-vars as an offset from FP, so the move
mutates into an add of fp+offset, clobbering the condition codes
computed earlier in the bitfield test.

One idea for a localized bandaid is to make the machine-description
wrap moves from virtual-stack-vars in a parallel that has a clobber
CC_REGNUM.  Another idea is to manipulate scheduling parameters so
that haifa doesn't schedule anything between CC set and CC use.
(I haven't yet looked at if/how this can be done.)

What's a better way to fix it?

Thanks,
Greg

Re: condition codes, haifa-sched and virtual-stack-vars

[law]

In message <200201301859.g0UIxx606426@kayak.mcgary.org>, Greg McGary writes:
 > I have a GCC port to a custom RISC that uses condition codes in an
 > explicit register (doesn't use cc0).  GCC generates bogus code when
 > expanding an inline.  One of the inline's args is the address of an
 > automatic, so it is passed to the inline as a move from
 > virtual-stack-vars to a pseudo.  Later, there's a conditional branch
 > on bitfield test that expands as bitfield-extract (shift + and),
 > comparison wtih zero, and branch.  All harmless so far.
 > 
 > Haifa-sched schedules the move from virtual-stack-vars between the
 > bitfield test sequence and the branch.  Later, global-reg alloc
 > instantiates virtual-stack-vars as an offset from FP, so the move
 > mutates into an add of fp+offset, clobbering the condition codes
 > computed earlier in the bitfield test.
 > 
 > One idea for a localized bandaid is to make the machine-description
 > wrap moves from virtual-stack-vars in a parallel that has a clobber
 > CC_REGNUM.  Another idea is to manipulate scheduling parameters so
 > that haifa doesn't schedule anything between CC set and CC use.
 > (I haven't yet looked at if/how this can be done.)
 > 
 > What's a better way to fix it?
If arithmetic clobbers the register, then that needs to be reflected in
the RTL for arithmetic.  Otherwise you're going to run into all kinds of
problems due to missing critical data dependency information in the
scheduler.

jeff






 > 
 > Thanks,
 > Greg

Re: condition codes, haifa-sched and virtual-stack-vars

[Greg McGary]

law@redhat.com writes:

> If arithmetic clobbers the register, then that needs to be reflected in
> the RTL for arithmetic.

It is.  FYI, here's the addsi3 pattern:

        (define_insn_and_split "addsi3"
          [(set (match_operand:SI 0 "register_operand"          "=r,r,r,r,r,r,r")
        	(plus:SI (match_operand:SI 1 "register_operand" "%0,0,0,0,0,0,0")
        		 (match_operand:SI 2 "uimm32r_operand"   "rM,U,I,S,K,T,P")))
           (clobber (reg:CC CC_REGNUM))]

All other arithmetic patterns are similar.

Here's a summary of mutations, by optimizer phase.

00.rtl:
    We pass the address of stack var, which hapens to be the first one
    allocated, so it's a zero-offset form virtual-stack-vars

        (insn 1299 1297 1301 (set (reg/v:SI 397)
                (reg/f:SI 46 virtual-stack-vars)) -1 (nil)
            (nil))

03.jump:
    Nothing interesting here

	(insn 1299 1297 1301 (set (reg/v:SI 397)
	        (reg/f:SI 32 TempFP)) 8 {*movsi} (nil)
	    (nil))

18.sched:
    Haifa relocates this insn to sit between setting CC and cond branch:

        (insn 1299 3891 1301 (set (reg/v:SI 397)
                (reg/f:SI 32 TempFP)) 8 {*movsi} (nil)
            (nil))

20.greg:
    TempFP is eliminated in favor of real fp+offset, and now the set is no longer innocent.

        (insn 4102 3891 4103 (set (reg:SI 2 r2)
                (const_int 56 [0x38])) 8 {*movsi} (nil)
            (nil))

        (insn 4103 4102 1299 (parallel[ 
                    (set (reg:SI 2 r2)
                        (plus:SI (reg:SI 2 r2)
                            (reg/f:SI 28 r28)))
                    (clobber (reg:CC 34 CC))
                ] ) 19 {addsi3} (nil)
            (expr_list:REG_EQUIV (plus:SI (reg/f:SI 28 r28)
                    (const_int 56 [0x38]))
                (nil)))

        (insn 1299 4103 1301 (set (reg/v:SI 12 r12 [397])
                (reg:SI 2 r2)) 8 {*movsi} (nil)
            (expr_list:REG_EQUIV (plus:SI (reg/f:SI 28 r28)
                    (const_int 56 [0x38]))
                (nil)))

22.flow2:
    Flow notices that the legitimate set of CC has its result clobbered, so 
    removes all of the legitimate bitfield code.

Things would have been OK if the stack var weren't the first one,
so that it got an offset in 00.rtl, and the associated clobber.
Maybe we shouldn't emit bare virtual-stack-vars, but rather emit as
plus with 0 offset?

Something else entirely?

Thanks,
Greg

Re: condition codes, haifa-sched and virtual-stack-vars

[law]

In message <ms7kpzd371.fsf@mcgary.org>, Greg McGary writes:
 > law@redhat.com writes:
 > 
 > > If arithmetic clobbers the register, then that needs to be reflected in
 > > the RTL for arithmetic.
 > 
 > It is.  FYI, here's the addsi3 pattern:
[ ... ]

 > All other arithmetic patterns are similar.
Got it.


 > Here's a summary of mutations, by optimizer phase.
Thanks.  It was helpful.

I think you're hosed :(


 > Things would have been OK if the stack var weren't the first one,
 > so that it got an offset in 00.rtl, and the associated clobber.
 > Maybe we shouldn't emit bare virtual-stack-vars, but rather emit as
 > plus with 0 offset?
That would be non-canonical RTL.

Fundamentally what we have is a data dependency that isn't exposed until
register allocation -- by which time we've already lost.

What you might consider doing is keeping cc0 setters and cc0 users as a
single insn until after reload.  Once reload is completed, split them
into their component insns.  By the time sched2 runs all the dependencies
are exposed and you shouldn't see any problems.

jeff

Re: condition codes, haifa-sched and virtual-stack-vars

[Richard Earnshaw]

If most insns clobber the condition code register, then trying to 
represent it at all to the compiler isn't very helpful.  GCC relies on 
being able to generate some types of insn without going through the 
expanders (simple moves for instance), so you might end up with spurious 
aborts if your normal move/addition/subtraction patterns require a clobber.

You don't have to use the CC0 approach however, it is possible to create a 
description of a machine that has no condition code register at all, and 
conditional branches (about the only time that conditions are really 
needed within the compiler) can be represented as compare-and-branch 
instructions.  See the TARGET_THUMB instructions of the ARM machine 
description for an example.

R.

Re: condition codes, haifa-sched and virtual-stack-vars

[Alexandre Oliva]

On Jan 30, 2002, Greg McGary <greg@mcgary.org> wrote:

> Haifa-sched schedules the move from virtual-stack-vars between the
> bitfield test sequence and the branch.  Later, global-reg alloc
> instantiates virtual-stack-vars as an offset from FP, so the move
> mutates into an add of fp+offset, clobbering the condition codes
> computed earlier in the bitfield test.

How about having a pre-reload move pattern that clobbers CC, split
after reload into one that does not, so that sched2 could put the move
between compare and branch should it indeed not affect CC?

-- 
Alexandre Oliva   Enjoy Guarana', see http://www.ic.unicamp.br/~oliva/
Red Hat GCC Developer                  aoliva@{cygnus.com, redhat.com}
CS PhD student at IC-Unicamp        oliva@{lsd.ic.unicamp.br, gnu.org}
Free Software Evangelist    *Please* write to mailing lists, not to me

Re: condition codes, haifa-sched and virtual-stack-vars

[Greg McGary]

Alexandre Oliva <aoliva@redhat.com> writes:

> How about having a pre-reload move pattern that clobbers CC, split
> after reload into one that does not, so that sched2 could put the move
> between compare and branch should it indeed not affect CC?

Alexandre,

I liked your idea best (less invasive than Jeff's idea of
reworking conditional branch patterns), and it works!

In the "movsi" expander, I added this bit:

        if (REG_P (src)
            && REGNO (src) >= FIRST_PSEUDO_REGISTER
            && REGNO (src) <= LAST_VIRTUAL_REGISTER)
          {
            emit_insn (gen_movsi_virtual_reg (dest, src));
            return 1;
          }

In the md file, *after* the normal movsi insn (so the normal takes
precedence), I added this pattern:

        (define_insn_and_split "movsi_virtual_reg"
          [(parallel [(set (match_operand:SI 0 "register_operand" "=r")
        		   (match_operand:SI 1 "register_operand"  "r"))
        	      (clobber (reg:CC CC_REGNUM))])]
          ""
          "#"
          "reload_completed"
          [(set (match_dup 0)
        	(match_dup 1))]
          "")

Thanks very much Alexandre & Jeff!

Greg

Re: condition codes, haifa-sched and virtual-stack-vars

[Alexandre Oliva]

On Jan 30, 2002, Greg McGary <greg@mcgary.org> wrote:

> In the "movsi" expander, I added this bit:

>         if (REG_P (src)
>             && REGNO (src) >= FIRST_PSEUDO_REGISTER
>             && REGNO (src) <= LAST_VIRTUAL_REGISTER)

I'd take the last condition out.  Consider, for example, that you have
a very large stack frame, such that a pseudo ends up having to be
replaced with (plus (reg SP) (const_int VERY_LARGE_NUMBER))?  Reload
may end up using a scratch register to construct this address, and it
will need an add to do that.  Better be safe and consider any pseudo
reloading risky.


Other than that, I'm very happy it worked.

-- 
Alexandre Oliva   Enjoy Guarana', see http://www.ic.unicamp.br/~oliva/
Red Hat GCC Developer                  aoliva@{cygnus.com, redhat.com}
CS PhD student at IC-Unicamp        oliva@{lsd.ic.unicamp.br, gnu.org}
Free Software Evangelist                Professional serial bug killer

Re: condition codes, haifa-sched and virtual-stack-vars

[law]

In message <orpu3r1km3.fsf@free.redhat.lsd.ic.unicamp.br>, Alexandre Oliva writ
es:
 > On Jan 30, 2002, Greg McGary <greg@mcgary.org> wrote:
 > 
 > > In the "movsi" expander, I added this bit:
 > 
 > >         if (REG_P (src)
 > >             && REGNO (src) >= FIRST_PSEUDO_REGISTER
 > >             && REGNO (src) <= LAST_VIRTUAL_REGISTER)
 > 
 > I'd take the last condition out.  Consider, for example, that you have
 > a very large stack frame, such that a pseudo ends up having to be
 > replaced with (plus (reg SP) (const_int VERY_LARGE_NUMBER))?  Reload
 > may end up using a scratch register to construct this address, and it
 > will need an add to do that.  Better be safe and consider any pseudo
 > reloading risky.
 > 
 > 
 > Other than that, I'm very happy it worked.
Likewise.  

I had pondered similar solutions, but rejected them as imparing 
optimization in too many ways.  Some optimizers are more effective
when moves are "simple".

jeff

Re: condition codes, haifa-sched and virtual-stack-vars

[Greg McGary]

law@redhat.com writes:

>  > >         if (REG_P (src)
>  > >             && REGNO (src) >= FIRST_PSEUDO_REGISTER

Oops.  I meant FIRST_VIRTUAL_REGISTER here (it's the same constant though).

>  > >             && REGNO (src) <= LAST_VIRTUAL_REGISTER)
>  > 
>  > I'd take the last condition out.  Consider, for example, that you have
>  > a very large stack frame, such that a pseudo ends up having to be
>  > replaced with (plus (reg SP) (const_int VERY_LARGE_NUMBER))?  Reload
>  > may end up using a scratch register to construct this address, and it
>  > will need an add to do that.  Better be safe and consider any pseudo
>  > reloading risky.
> 
> I had pondered similar solutions, but rejected them as imparing 
> optimization in too many ways.  Some optimizers are more effective
> when moves are "simple".

I also wanted to keep them simple.  I am choosing to live dangerously
and confine this hack to bare virtual regs only.  The target is an
embedded processor without MMU whose entire stack buffers are nowhere
near the 64 Kbyte range of immediate offsets.  Now that I think about
it, your idea about reworking conditional branches to keep the test
and branch together then splitting after reload feels like the cleaner
solution.

Greg

Re: condition codes, haifa-sched and virtual-stack-vars

[Alexandre Oliva]

On Jan 30, 2002, Greg McGary <greg@mcgary.org> wrote:

> Now that I think about it, your idea about reworking conditional
> branches to keep the test and branch together then splitting after
> reload feels like the cleaner solution.

Of course.  I couldn't possibly have come up with a solution better
than that thought up by my master :-D

-- 
Alexandre Oliva   Enjoy Guarana', see http://www.ic.unicamp.br/~oliva/
Red Hat GCC Developer                  aoliva@{cygnus.com, redhat.com}
CS PhD student at IC-Unicamp        oliva@{lsd.ic.unicamp.br, gnu.org}
Free Software Evangelist                Professional serial bug killer

Re: condition codes, haifa-sched and virtual-stack-vars

[Richard Henderson]

On Wed, Jan 30, 2002 at 11:59:59AM -0700, Greg McGary wrote:
> Later, global-reg alloc instantiates virtual-stack-vars as an
> offset from FP, so the move mutates into an add of fp+offset,
> clobbering the condition codes computed earlier in the bitfield test.

If you don't have a form of add that doesn't clobber condition
codes, you are screwed.  Reload absolutely relies on the existance
of such an instruction.

Your only hope is to represent compare+branch as a single insn
until after reload.


r~