approaches to carry-flag modelling in RTL

approaches to carry-flag modelling in RTL

[Peter Bigot]

I'm rewriting a back-end originally based on AVR to eliminate insns for
multi-word operations (output templates like "add\;addc") and to use MODE_CC
instead of an unusual attribute-based approach.  The motivation is that I've
mostly found gcc does a better job than the existing back-end if it's shown
what's actually going on.

Part of this update requires correctly modelling the carry flag, for
plus/minus and for rotate through carry.  As noted in recent email here,
preserving the correct instruction order when expanding multi-word expressions
requires a set/use relation between the word-mode insns rather than a
simple clobber/use relation.

I've found several examples where back-ends model the carry in RTL.

Sparc does:

        (plus:SI
          (plus:SI
            (match_operand:SI 1 "arith_operand" "%r")
            (match_operand:SI 2 "arith_operand" "rI"))
          (ltu:SI (reg:CC_NOOV 100) (const_int 0))))]

RX does:

        (plus:SI
          (plus:SI
            (ltu:SI (reg:CC CC_REG) (const_int 0))
            (match_operand:SI 1 "register_operand"  "%0,0,0,0,0,0"))
          (match_operand:SI   2 "rx_source_operand"
"r,Sint08,Sint16,Sint24,i,Q")))

stormy16 does:

        (plus:HI
          (plus:HI
            (match_operand:HI 1 "register_operand" "%0,0,0")
            (zero_extend:HI (reg:BI CARRY_REG)))
          (match_operand:HI 2 "xs_hi_nonmemory_operand" "L,Ir,i")))

The variation points are:

(a) where the carry operand appears in the plus expressions;

(b) whether it's expressed as an ltu zero comparison or a zero_extend.

I'm inclined to follow sparc's lead, but is one or another of the choices
more likely to help combine/reload/etc do a better job?

Thanks.

Peter

Re: approaches to carry-flag modelling in RTL

[Richard Henderson]

On 10/28/2011 06:49 AM, Peter Bigot wrote:
> I'm inclined to follow sparc's lead, but is one or another of the choices
> more likely to help combine/reload/etc do a better job?

I don't know.

In the case of RX, we don't model CC_REG until after reload, so combine really
doesn't get a shot at it.

Be careful here.  If you explicitly model the carry flag before reload, you need
to have an ADD instruction that can avoid any flags modification.  Reload needs
to generate such instructions in some cases, and needs to be able to insert them
between any two arbitrary insns.

If you're like sparc (separate add, addcc insns), or i386 (separate add, lea insns),
then you're fine.  If you're like m68k or RX and have only an add that clobbers
the flags, then you'll have to delay splitting flags-using patterns until after
reload is complete.


r~

Re: approaches to carry-flag modelling in RTL

[Peter Bigot]

On Fri, Oct 28, 2011 at 11:59 AM, Richard Henderson <rth@redhat.com> wrote:
> On 10/28/2011 06:49 AM, Peter Bigot wrote:
>> I'm inclined to follow sparc's lead, but is one or another of the choices
>> more likely to help combine/reload/etc do a better job?
>
> I don't know.
>
> In the case of RX, we don't model CC_REG until after reload, so combine really
> doesn't get a shot at it.
>
> Be careful here.  If you explicitly model the carry flag before reload, you need
> to have an ADD instruction that can avoid any flags modification.  Reload needs
> to generate such instructions in some cases, and needs to be able to insert them
> between any two arbitrary insns.
>
> If you're like sparc (separate add, addcc insns), or i386 (separate add, lea insns),
> then you're fine.  If you're like m68k or RX and have only an add that clobbers
> the flags, then you'll have to delay splitting flags-using patterns until after
> reload is complete.

Interesting.  The MSP430 ISA has add and addc insns, but both affect the
flags.  Most instructions affect the flags.

Based on what I've encountered so far, between having to duplicate many
insns (one with CC_REG, one without), adding splits to convert between them,
and making a hash of the templates for the peepholes that enable efficient
access to volatile RMW peripheral memory, it looks like using CC_MODE is
going to create a maintenance nightmare.

I'd been moving on this path based on the recommendation in the "Condition Code
Status" section of GCC Internals to use CC_MODE for new ports.  (Though the
MSP430 isn't a "new port", in 2003 the original cc0 solution using
NOTICE_UPDATE_CC was converted to something obscene that ends up instead
walking the insn chain calling get_attr_cc during output template generation
to identify the most recent change.  No idea why; the CVS comment just
says "cmp fixes and improvements".)

It seems cc0 should probably still be preferred for CISC-style
architectures like the
MSP430.  I'll give that approach a try.

Thanks.

Peter

Re: approaches to carry-flag modelling in RTL

[Richard Henderson]

On 10/29/2011 05:41 AM, Peter Bigot wrote:
> It seems cc0 should probably still be preferred for CISC-style
> architectures like the MSP430.  I'll give that approach a try.

I think that's somewhat unfair.  Take a close look at the RX and
mn10300 ports -- they're what I would call the most up-to-date
of the cisc-y ports.


r~

Re: approaches to carry-flag modelling in RTL

[Peter Bigot]

On Sat, Oct 29, 2011 at 10:58 AM, Richard Henderson <rth@redhat.com> wrote:
> On 10/29/2011 05:41 AM, Peter Bigot wrote:
>> It seems cc0 should probably still be preferred for CISC-style
>> architectures like the MSP430.  I'll give that approach a try.
>
> I think that's somewhat unfair.  Take a close look at the RX and
> mn10300 ports -- they're what I would call the most up-to-date
> of the cisc-y ports.

Both RX and mn10300 may be cleaner architectures than MSP430, in that the
machine descriptions only provide SI and DI versions of the insns.  I admit
I'm discouraged that it's necessary to have (1) an addsi3 insn, (2) an
*addsi3_flags insn that differs from it only by adding a CC_REG set in the
RTL template and a reload_completed condition, and (3) an addsi3_flags
expander that replicates the RTL template of *addsi3_flags.

For MSP430, the native operand sizes are QI, HI, and PSI, and I need all
three, plus expanders for the derived SI and DI variants where gcc's
ignorance of machine-dependent carry support causes the default expansions
to be poor.  The same sort of relationships between the instructions and the
flags register exist for add, sub, ior, and, xor, and left and right shift
operations.  Even using iterators, this makes for an ugly machine
description.

The last straw for me is that adding CC_REG-related patterns into the RTL
bleeds into the peephole definitions that I need to eliminate unnecessary
(arguably wrong) register moves that get generated for RMW operations on
memory-mapped peripherals.  Those are already pretty hard to understand.

Using CC_MODE in this case certainly appears much more complicated
than using cc0.  Do you believe the effort required to get it right would be
justified?  Where would the win come from?

Peter

Re: approaches to carry-flag modelling in RTL

[Hans-Peter Nilsson]

On Sat, 29 Oct 2011, Peter Bigot wrote:
> On Fri, Oct 28, 2011 at 11:59 AM, Richard Henderson <rth@redhat.com> wrote:
> Based on what I've encountered so far, between having to duplicate many
> insns (one with CC_REG, one without), adding splits to convert between them,
> and making a hash of the templates for the peepholes that enable efficient
> access to volatile RMW peripheral memory, it looks like using CC_MODE is
> going to create a maintenance nightmare.

I came to the somewhat the same conclusion for CRIS where all
insns set condition codes except move to memory and a "add
reg1,reg2" (no immediate operand) and to/from special registers:
there'll one clobbering and one CC_REG-setting pattern plus a
load of others (peephole2's mostly) to get an exact match.

What would help is a kind of iterator that (also) affects the
form of the insn, so you could match the clobbering and the
cc0-setting insn in the same (iterator-using) pattern.  BTW, I
don't think it helps that someone decided the canonical form of
a parallel that includes a CC-setter must have the CC-setting
*first* (contrasting with the position of clobbers)...

To answer your later question: The main win from moving *from*
cc0 is easier maintenance for the *rest* of gcc: no need to
special-case cc0; its implicit setting is a complicating factor
when working at the RTL level.  Albeit some minor optimizations
are disabled when cc0 is encountered (IIRC), last I checked a
trivial transformation from cc0 to explicit CC_REG loses
performance; additional work (peephole2's and the equivalence of
avr_reorg) is needed to get it back.

brgds, H-P

Re: approaches to carry-flag modelling in RTL

[Paulo J. Matos]

On 28/10/11 17:59, Richard Henderson wrote:
> On 10/28/2011 06:49 AM, Peter Bigot wrote:
>> I'm inclined to follow sparc's lead, but is one or another of the choices
>> more likely to help combine/reload/etc do a better job?
>
> I don't know.
>
> In the case of RX, we don't model CC_REG until after reload, so combine really
> doesn't get a shot at it.
>
> Be careful here.  If you explicitly model the carry flag before reload, you need
> to have an ADD instruction that can avoid any flags modification.  Reload needs
> to generate such instructions in some cases, and needs to be able to insert them
> between any two arbitrary insns.
>

I followed rx model but instead RCC before clobber in some cases.
To solve this problem

I have the following insn_and_split:
(define_insn_and_split "addqi3_noclobber"
   [(set (match_operand:QI 0 "register_operand" "=c")
         (plus:QI (match_operand:QI 1 "register_operand")
                  (match_operand:QI 2 "immediate_operand")))]
   "reload_in_progress"
   "#"
   "reload_completed"
   [(parallel [(set (match_dup 0) (match_dup 1))
               (clobber (reg:CC RCC))])
    (parallel [(set (match_dup 0) (plus:QI (match_dup 0) (match_dup 2)))
               (clobber (reg:CC RCC))])])

Cheers,
-- 
PMatos

Re: approaches to carry-flag modelling in RTL

[Paulo J. Matos]

On 29/10/11 18:33, Peter Bigot wrote:
> On Sat, Oct 29, 2011 at 10:58 AM, Richard Henderson<rth@redhat.com>  wrote:
>> On 10/29/2011 05:41 AM, Peter Bigot wrote:
>>> It seems cc0 should probably still be preferred for CISC-style
>>> architectures like the MSP430.  I'll give that approach a try.
>>
>> I think that's somewhat unfair.  Take a close look at the RX and
>> mn10300 ports -- they're what I would call the most up-to-date
>> of the cisc-y ports.
>
>
> Using CC_MODE in this case certainly appears much more complicated
> than using cc0.  Do you believe the effort required to get it right would be
> justified?  Where would the win come from?
>

I can provide you with some insight here. We have a somewhat cisc-y 
port. I converted from cc0 to REG_CC based on the technique used in RX 
and MN10300.

Cons:
* Conversion took 2 weeks and increased the size of the backend due to 
the duplication of <rule> and <rule_flags>;
* My somewhat wierd backend has strange sizes so I ended up having to 
modify core GCC in some parts: to set CC_MODE size and to enable moves 
clobbering flags;
* Some rules are not much harder to read;
* compare-elim.c doesn't work 100% since pass assumes rules have 
register as destination. If yours have a memory operand, elimination 
won't succeed;

Pros:
* 0.7% code size reduction;
* Hoping that future GCC versions will ease the use of a pseudo 
FLAGS_REG, improve compare-elim and boost code size reduction further.

Some colleagues said the change probably didn't make sense. I am still 
slightly hopeful in the longer term to show them otherwise.

Cheers,

-- 
PMatos

Re: approaches to carry-flag modelling in RTL

[Paulo J. Matos]

On 31/10/11 05:36, Hans-Peter Nilsson wrote:
> BTW, I
> don't think it helps that someone decided the canonical form of
> a parallel that includes a CC-setter must have the CC-setting
> *first* (contrasting with the position of clobbers)...
>

How did you reach this conclusion?


-- 
PMatos

Re: approaches to carry-flag modelling in RTL

[Joern Rennecke]

Quoting Hans-Peter Nilsson <hp@bitrange.com>:

> I came to the somewhat the same conclusion for CRIS where all
> insns set condition codes except move to memory and a "add
> reg1,reg2" (no immediate operand) and to/from special registers:
> there'll one clobbering and one CC_REG-setting pattern plus a
> load of others (peephole2's mostly) to get an exact match.
>
> What would help is a kind of iterator that (also) affects the
> form of the insn, so you could match the clobbering and the
> cc0-setting insn in the same (iterator-using) pattern.

match_parallel is useful for recognizing insns with varying clobbers.
Unfortunately, it is absolutely useless when you want a reasonable expander,
so then you end up having a separate expander pattern, even if all you want to
do is have structure of the patch_parallel without extra clobbers.
Repeat for a dozen similar instructions, and it gets really annoying.

Re: approaches to carry-flag modelling in RTL

[Hans-Peter Nilsson]

On Mon, 31 Oct 2011, Paulo J. Matos wrote:
> On 31/10/11 05:36, Hans-Peter Nilsson wrote:
> > BTW, I
> > don't think it helps that someone decided the canonical form of
> > a parallel that includes a CC-setter must have the CC-setting
> > *first* (contrasting with the position of clobbers)...
>
> How did you reach this conclusion?

Not obvious or maybe I was unclear as to what I alluded?
In the below insn-bodies, "sub" is the insn that sets cc0 as a
side-effect.

Supposed canonical form :

(parallel
 [(set cc_reg) (compare ...))
  (set destreg) (sub ...))])
and:
(parallel
 [(set destreg) (sub ...))
  (clobber cc_reg)])

But IMHO it'd be easier (for most values of "easier") to combine
both patterns with that non-existing mechanism (and no, I don't
count match_parallel) if we instead canonicalized on the CC_REG
set being the same as the clobber position:

(parallel
 [(set destreg) (sub ...))
  (set cc_reg) (compare ...))])
with:
(parallel
 [(set destreg) (sub ...))
  (clobber cc_reg)])

brgds, H-P

Re: approaches to carry-flag modelling in RTL

[Paulo J. Matos]

On 01/11/11 02:43, Hans-Peter Nilsson wrote:
>
> Not obvious or maybe I was unclear as to what I alluded?
> In the below insn-bodies, "sub" is the insn that sets cc0 as a
> side-effect.
>
> Supposed canonical form :
>
> (parallel
>   [(set cc_reg) (compare ...))
>    (set destreg) (sub ...))])
> and:
> (parallel
>   [(set destreg) (sub ...))
>    (clobber cc_reg)])
>
> But IMHO it'd be easier (for most values of "easier") to combine
> both patterns with that non-existing mechanism (and no, I don't
> count match_parallel) if we instead canonicalized on the CC_REG
> set being the same as the clobber position:
>
> (parallel
>   [(set destreg) (sub ...))
>    (set cc_reg) (compare ...))])
> with:
> (parallel
>   [(set destreg) (sub ...))
>    (clobber cc_reg)])
>
> brgds, H-P
>

That is very strange because if you look into RX or MN10300, they all 
have the set REG_CC as the last in the parallel. I wonder if it has 
anything to do with the fact that in these backends the set of the 
REG_CC only shows up after reload.


-- 
PMatos

Re: approaches to carry-flag modelling in RTL

[Hans-Peter Nilsson]

Please, when replying, also send to me, not just the list.

On Tue, 1 Nov 2011, Paulo J. Matos wrote:
> On 01/11/11 02:43, Hans-Peter Nilsson wrote:
> >
> > Not obvious or maybe I was unclear as to what I alluded?
> > In the below insn-bodies, "sub" is the insn that sets cc0 as a
> > side-effect.
> >
> > Supposed canonical form :
> >
> > (parallel
> >   [(set cc_reg) (compare ...))
> >    (set destreg) (sub ...))])
> > and:
> > (parallel
> >   [(set destreg) (sub ...))
> >    (clobber cc_reg)])

> That is very strange because if you look into RX or MN10300, they all have the
> set REG_CC as the last in the parallel.

That'd be a good reason to flip the default...except that the
i386 has it the other way round i.e. as shown above.  I think
the main reason is that it just seemed right to those port
authors.

> I wonder if it has anything to do with
> the fact that in these backends the set of the REG_CC only shows up after
> reload.

Right, it'd only matter where (also) GCC cooks up combinations
(which IIRC it doesn't if the register is only exposed
post-reload), not where only the port emits them.  N.B., it
*could* very well be that I misremember about the canonical
form, but it seems neither of us bother to search the archives,
so never mind. ;)
...oh wait, see the comments at combine.c:2824 and 3030 r180744.
I can't find anything in the docs, but that might just be my
grep-fu failing.

I'm still thinking of a generic md iterator mechanism (one that
doesn't restrict the form of the expansion in ways getting in
the way with expanding to both a clobber and a set, and in
swapped locations as above), to make the troubles go away...
But maybe expanding them by a pass through e.g. m4 would be
better than cooking up something new there.

brgds, H-P

Re: approaches to carry-flag modelling in RTL

[Richard Henderson]

On 11/01/2011 02:59 PM, Hans-Peter Nilsson wrote:
> Please, when replying, also send to me, not just the list.
> 
> On Tue, 1 Nov 2011, Paulo J. Matos wrote:
>> On 01/11/11 02:43, Hans-Peter Nilsson wrote:
>>>
>>> Not obvious or maybe I was unclear as to what I alluded?
>>> In the below insn-bodies, "sub" is the insn that sets cc0 as a
>>> side-effect.
>>>
>>> Supposed canonical form :
>>>
>>> (parallel
>>>   [(set cc_reg) (compare ...))
>>>    (set destreg) (sub ...))])
>>> and:
>>> (parallel
>>>   [(set destreg) (sub ...))
>>>    (clobber cc_reg)])
> 
>> That is very strange because if you look into RX or MN10300, they all have the
>> set REG_CC as the last in the parallel.

Yes.  The cc_reg last there is a consequence of the post-reload compare-elim pass.
Which wants to splat the CC set on top of the clobber.  Thus it must be last.

> That'd be a good reason to flip the default...except that the
> i386 has it the other way round i.e. as shown above.  I think
> the main reason is that it just seemed right to those port
> authors.

Frankly, I'd prefer to flip the default.  It does seem to make the most sense.
We shan't do that until we tackle...

> I'm still thinking of a generic md iterator mechanism (one that
> doesn't restrict the form of the expansion in ways getting in
> the way with expanding to both a clobber and a set, and in
> swapped locations as above), to make the troubles go away...
> But maybe expanding them by a pass through e.g. m4 would be
> better than cooking up something new there.

... this, so that it can all be done automatically.

I think some sort of iterator mechanism is best, much like we
automate cond_exec and other sorts of macro-izations.

I can imagine a sort of

(define_insn_with_flags "name"
  [(set ...)
   (set (reg:cc) (...)]
  ""
  ...)

where we automatically expand to

(define_insn "name"
  [(set ...)
   (clobber (reg:cc))]
  ...)

(define_insn "name_flags"
  [(set ...)
   (set (reg:cc) (...)]
  ...)

or something like that.


r~

Re: approaches to carry-flag modelling in RTL

[Hans-Peter Nilsson]

Since this came up the other day in the "post-reload compare
optimization pass" discussion, I thought better comment on
this old post in case someone is tempted to do something...

On Wed, 2 Nov 2011, Richard Henderson wrote:
> Frankly, I'd prefer to flip the default.  It does seem to make the most sense.
> We shan't do that until we tackle...
>
> On 11/01/2011 02:59 PM, Hans-Peter Nilsson wrote:
> > I'm still thinking of a generic md iterator mechanism (one that
> > doesn't restrict the form of the expansion in ways getting in
> > the way with expanding to both a clobber and a set, and in
> > swapped locations as above), to make the troubles go away...
> > But maybe expanding them by a pass through e.g. m4 would be
> > better than cooking up something new there.
>
> ... this, so that it can all be done automatically.
>
> I think some sort of iterator mechanism is best, much like we
> automate cond_exec and other sorts of macro-izations.
>
> I can imagine a sort of
>
> (define_insn_with_flags "name"
>   [(set ...)
>    (set (reg:cc) (...)]
>   ""
>   ...)
>
> where we automatically expand to
>
> (define_insn "name"
>   [(set ...)
>    (clobber (reg:cc))]
>   ...)
>
> (define_insn "name_flags"
>   [(set ...)
>    (set (reg:cc) (...)]
>   ...)
>
> or something like that.

Of equal value would be an optional third expansion for that
define_insn_with_flags thing with just the plain "main" set, for
the cases where (for some alternatives) the plain set can be
emitted without CC side effects.

brgds, H-P