splitting add instructions

splitting add instructions

[Paulo J. Matos]

Hello,

I am trying to size-optimise one of our instructions. That's addhi3. 
HImode is 32 bits and QImode is 16bits, which is what our processor 
instructions work with.

So generally an addhi3 looks like:
(define_insn "addhi3"
    [(set (match_operand:HI 0 "nonimmediate_operand" "=c")
          (plus:HI (match_operand:HI 1 "general_operand" "%0")
                   (match_operand:HI 2 "general_operand" "cwmi")))]
    ""
    "add  %b0,%b2\;addc %t0,%t2")

Where the format specifiers b and t choose the top and bottom 16 bits of 
each operand. add is a 16bit addition operand and addc takes carry flag 
into consideration. Now, there are a lot of simple manipulations that 
can be made if I release GCC from always outputting these two 
instructions together. However, the problem is expanding an addhi3 into 
two QImode add insn (which look the same), one of each outputs addc 
instead of add.

I thought about using attributes but I am very unsure that it works or 
even if it is the way to go.

The problem is, if addhi3 expands into two insn:
(define_insn "addqi3"
    [(set (match_operand:HI 0 "nonimmediate_operand" "=c")
          (plus:HI (match_operand:HI 1 "general_operand" "%0")
                   (match_operand:HI 2 "general_operand" "cwmi")))]
    "get_attr_CARRY(insn) == 0"
    "add  %b0,%b2")

(define_insn "addqi3_carry"
    [(set (match_operand:HI 0 "nonimmediate_operand" "=c")
          (plus:HI (match_operand:HI 1 "general_operand" "%0")
                   (match_operand:HI 2 "general_operand" "cwmi")))]
    "get_attr_CARRY(insn) == 1"
    "addc %t0,%t2")

_One_ of the problems with this is that if GCC sees that op2 is 0, it 
will remove the insn because it will see: R0 = R0 + 0. However, it can't 
do this in this specific case because the plus is actually also adding 
the carry flag.

Any suggestions on how to deal with this situation?

Cheers,
--

PMatos

Re: splitting add instructions

[Richard Henderson]

On 07/18/2011 08:01 AM, Paulo J. Matos wrote:
> The problem is, if addhi3 expands into two insn:
> (define_insn "addqi3"
>    [(set (match_operand:HI 0 "nonimmediate_operand" "=c")
>          (plus:HI (match_operand:HI 1 "general_operand" "%0")
>                   (match_operand:HI 2 "general_operand" "cwmi")))]
>    "get_attr_CARRY(insn) == 0"
>    "add  %b0,%b2")
> 
> (define_insn "addqi3_carry"
>    [(set (match_operand:HI 0 "nonimmediate_operand" "=c")
>          (plus:HI (match_operand:HI 1 "general_operand" "%0")
>                   (match_operand:HI 2 "general_operand" "cwmi")))]
>    "get_attr_CARRY(insn) == 1"
>    "addc %t0,%t2")
> 
> _One_ of the problems with this is that if GCC sees that op2 is 0, it will remove the insn because it will see: R0 = R0 + 0. However, it can't do this in this specific case because the plus is actually also adding the carry flag.
> 
> Any suggestions on how to deal with this situation?

You need to specifically represent the other output, i.e. the carry flag.

Depending on the constraints of your processor, you may or may not be able
to expose this before reload.  Reload requires the ability to issue move
instructions (all of loads, stores, reg-reg) and addition instructions.
It must be able to do this between any pair of instructions in order to
handle register spilling.  Therefore in order to expose the carry flag
before reload, you must have an add instruction that does not modify the
carry. Some processors have this in the form of a "load-effective-address"
instruction.

If you have an LEA-type insn, look at the way the i386 port splits its
double-word addition before reload.

Otherwise, have a look at the mn10300 and rx ports.  There, we split the
double-word register, but keep the double-word add as one insn until reload
is complete.  Those ports are also the only ones that use the brand new (4.6)
post-reload comparison optimization pass.


r~

Re: splitting add instructions

[Paul Koning]

On Jul 18, 2011, at 12:53 PM, Richard Henderson wrote:

> On 07/18/2011 08:01 AM, Paulo J. Matos wrote:
>> The problem is, if addhi3 expands into two insn:
>> (define_insn "addqi3"
>>   [(set (match_operand:HI 0 "nonimmediate_operand" "=c")
>>         (plus:HI (match_operand:HI 1 "general_operand" "%0")
>>                  (match_operand:HI 2 "general_operand" "cwmi")))]
>>   "get_attr_CARRY(insn) == 0"
>>   "add  %b0,%b2")
>> 
>> (define_insn "addqi3_carry"
>>   [(set (match_operand:HI 0 "nonimmediate_operand" "=c")
>>         (plus:HI (match_operand:HI 1 "general_operand" "%0")
>>                  (match_operand:HI 2 "general_operand" "cwmi")))]
>>   "get_attr_CARRY(insn) == 1"
>>   "addc %t0,%t2")
>> 
>> _One_ of the problems with this is that if GCC sees that op2 is 0, it will remove the insn because it will see: R0 = R0 + 0. However, it can't do this in this specific case because the plus is actually also adding the carry flag.
>> 
>> Any suggestions on how to deal with this situation?
> 
> You need to specifically represent the other output, i.e. the carry flag.
> 
> Depending on the constraints of your processor, you may or may not be able
> to expose this before reload.  Reload requires the ability to issue move
> instructions (all of loads, stores, reg-reg) and addition instructions.
> It must be able to do this between any pair of instructions in order to
> handle register spilling.  Therefore in order to expose the carry flag
> before reload, you must have an add instruction that does not modify the
> carry. Some processors have this in the form of a "load-effective-address"
> instruction.

Why an add instruction?  Is that in the case where address arithmetic requires separate adds?  If the machine is CISC, then I would think that reload just needs to be able to generate loads and stores that don't modify the carry, which would be a different requirement.  For example, on a pdp11 load/store (move) has that property, while add doesn't (it always touches carry).

"Specifically represent... the carry flag" means using the CCmode style of condition code handling, right?

	paul

Re: splitting add instructions

[Richard Henderson]

On 07/18/2011 10:29 AM, Paul Koning wrote:
> Why an add instruction? Is that in the case where address arithmetic
> requires separate adds?

I don't recall.  Probably to do with some edge case of reloading addresses.
I know that this affects m68k, which is even CISC-y-er in its addressing 
modes than pdp11, so I do know that you can't ignore it.

You could fairly easily find the case that requires it by adding a temporary

  gcc_assert (!reload_in_progress);

inside your Pmode add expander.

> "Specifically represent... the carry flag" means using the CCmode
> style of condition code handling, right?

Yes.


r~

Re: splitting add instructions

[Paulo J. Matos]

On 18/07/11 19:00, Richard Henderson wrote:
>
>> "Specifically represent... the carry flag" means using the CCmode
>> style of condition code handling, right?
>
> Yes.
>
>

hummm, we are still using the old mode for condition code handling. From 
what you're saying we need to use the new CCmode. I was looking at the 
internal documents and even though it doesn't seem required to have a 
hard register to keep the condition codes, it is also hard to know how 
it is actually implemented. Is there any port which doesn't have a hard 
register representing a condition code, which used CCMode?

-- 
PMatos

Re: splitting add instructions

[Paulo J. Matos]

On 19/07/11 09:21, Paulo J. Matos wrote:
> hummm, we are still using the old mode for condition code handling. From
> what you're saying we need to use the new CCmode. I was looking at the
> internal documents and even though it doesn't seem required to have a
> hard register to keep the condition codes, it is also hard to know how
> it is actually implemented. Is there any port which doesn't have a hard
> register representing a condition code, which used CCMode?
>

I have been looking at the rx port. Seems to be very similar to mine in 
that it has an add and adc where both set the flags and no explicit hard 
register for cc. Mine is actually simpler in that there is only CCmode 
since we don't have floating point operations in the chip. Will use rx 
as a guide! :)

-- 
PMatos

Re: splitting add instructions

[Richard Henderson]

On 07/19/2011 01:48 AM, Paulo J. Matos wrote:
> I have been looking at the rx port. Seems to be very similar to mine
> in that it has an add and adc where both set the flags and no
> explicit hard register for cc. Mine is actually simpler in that there
> is only CCmode since we don't have floating point operations in the
> chip. Will use rx as a guide! :)

Note that while RX has one mode for floating-point, it has
two other modes to deal with instructions that fail to set
all of the flags (or fails to set the flags in a way that
is useful for the comparison).

Depending on how regular your instructions are, you may
find that CCmode is not enough to eliminate all comparisons.
It is, however, a good start.


r~

Re: splitting add instructions

[Paulo J. Matos]

On 19/07/11 16:41, Richard Henderson wrote:
> Note that while RX has one mode for floating-point, it has
> two other modes to deal with instructions that fail to set
> all of the flags (or fails to set the flags in a way that
> is useful for the comparison).
>
> Depending on how regular your instructions are, you may
> find that CCmode is not enough to eliminate all comparisons.
> It is, however, a good start.
>
>

Yes, you're right. I just added also some more modes to my port 
mimicking RX.

-- 
PMatos

Re: splitting add instructions

[Paulo J. Matos]

On 19/07/11 16:41, Richard Henderson wrote:
>(or fails to set the flags in a way that
> is useful for the comparison).

I am not sure I understand the above. Could you give an example where 
certain flags might be set but are not useful for comparison?

-- 
PMatos

Re: splitting add instructions

[Richard Henderson]

On 07/19/2011 08:57 AM, Paulo J. Matos wrote:
> On 19/07/11 16:41, Richard Henderson wrote:
>> (or fails to set the flags in a way that
>> is useful for the comparison).
> 
> I am not sure I understand the above. Could you give an example where
> certain flags might be set but are not useful for comparison?

You pasted one before -- the RX definition of ABS.

The instruction description of the O flag for ABS reads:

# The flag is set if src before the operation was 80000000h; otherwise it is cleared.

The upshot is that the entire flags register is set as if
the operation was "0 - src", i.e.

  (compare:CC (const_int 0) (reg:SI src))

However, the comparison that we're actually going to try
to generate is

  (compare:CC (abs:SI (reg:SI src)) (const_int 0))

Which is of course not the same thing.  However, if we can
ignore the O flag for a given comparison, then we can still
usefully make use of some of the flags.  E.g. the Z flag in
testing for (in)equality against zero.

The other very common case is subtract, where the flags are
set as if the comparison is

  (compare:CC input1 input2)

whereas the comparison that we generate is

  (compare:CC output 0)

Have a look at all the uses of rx_match_ccmode in rx.md.



r~

Re: splitting add instructions

[Paul Koning]

On Jul 19, 2011, at 4:21 AM, Paulo J. Matos wrote:

> On 18/07/11 19:00, Richard Henderson wrote:
>> 
>>> "Specifically represent... the carry flag" means using the CCmode
>>> style of condition code handling, right?
>> 
>> Yes.
> 
> hummm, we are still using the old mode for condition code handling. From what you're saying we need to use the new CCmode. I was looking at the internal documents and even though it doesn't seem required to have a hard register to keep the condition codes, it is also hard to know how it is actually implemented. Is there any port which doesn't have a hard register representing a condition code, which used CCMode?

"hard register" doesn't mean a general register with a number, explicitly mentioned in the processor manual.  It just is a way to describe some more pieces of state to GCC.  In that sense, every processor that has condition codes has a hard register of type CCmode -- they just don't describe it that way.

	paul

Re: splitting add instructions

[Paulo J. Matos]

On 18/07/11 17:53, Richard Henderson wrote:
>Therefore in order to expose the carry flag
> before reload, you must have an add instruction that does not modify the
> carry. Some processors have this in the form of a "load-effective-address"
> instruction.
>

An add instruction that doesn't modify carry. You mean an add 
instruction that doesn't take carry into consideration (like add) or an 
instruction that doesn't modify (by clearing or setting) the carry flag? 
If the latter, then we don't have since both add and addc set the carry. :(

Re: splitting add instructions

[Paulo J. Matos]

On 18/07/11 17:53, Richard Henderson wrote:
> Otherwise, have a look at the mn10300 and rx ports.

Looking at rx.c, flag_from_code:

static unsigned int
flags_from_code (enum rtx_code code)
{
   switch (code)
     {
     case LT:
     case GE:
       return CC_FLAG_S;
...


For GE, shouldn't you also need CC_FLAG_Z ?

-- 
PMatos

Re: splitting add instructions

[Paulo J. Matos]

On 19/07/11 11:20, Paulo J. Matos wrote:
>
> For GE, shouldn't you also need CC_FLAG_Z ?
>

I just got it! :) No need for CC_FLAG_Z!

-- 
PMatos

Re: splitting add instructions

[Paulo J. Matos]

On 18/07/11 17:53, Richard Henderson wrote:
>
> Otherwise, have a look at the mn10300 and rx ports.

What's the idea behind the rx port *_flags alternative define_insn?
For example:
(define_insn "abssi2"
   [(set (match_operand:SI         0 "register_operand" "=r,r")
         (abs:SI (match_operand:SI 1 "register_operand"  "0,r")))
    (clobber (reg:CC CC_REG))]
   ""
   "@
   abs\t%0
   abs\t%1, %0"
   [(set_attr "length" "2,3")]
)

(define_insn "*abssi2_flags"
   [(set (match_operand:SI         0 "register_operand" "=r,r")
         (abs:SI (match_operand:SI 1 "register_operand"  "0,r")))
    (set (reg CC_REG)
         (compare (abs:SI (match_dup 1))
                  (const_int 0)))]
   ;; Note - although the ABS instruction does set the O bit in the 
processor
   ;; status word, it does not do so in a way that is comparable with 
the CMP
   ;; instruction.  Hence we use CC_ZSmode rather than CC_ZSOmode.
   "reload_completed && rx_match_ccmode (insn, CC_ZSmode)"
   "@
   abs\t%0
   abs\t%1, %0"
   [(set_attr "length" "2,3")]
)

What's the point of the second define insn? The first insn seems to take 
us from expansion to asm generation so I can't see where the second one 
will come into play except in an expansion after reload but that doesn't 
happen, right?

-- 

PMatos

Re: splitting add instructions

[DJ Delorie]

> What's the point of the second define insn? The first insn seems to
> take us from expansion to asm generation so I can't see where the
> second one will come into play except in an expansion after reload
> but that doesn't happen, right?

IIRC it has to do with optimizing away compare instructions.  Which
pattern you need depends on whether the flags will get used by a
conditional branch or not.

Re: splitting add instructions

[Paulo J. Matos]

On 19/07/11 16:06, DJ Delorie wrote:
>> What's the point of the second define insn? The first insn seems to
>> take us from expansion to asm generation so I can't see where the
>> second one will come into play except in an expansion after reload
>> but that doesn't happen, right?
>
> IIRC it has to do with optimizing away compare instructions.  Which
> pattern you need depends on whether the flags will get used by a
> conditional branch or not.
>

So, this seems to have to do with the post-reload comparison 
optimization pass Richard mentioned. But I am still confused as to how 
GCC matches them. Is *_flags any special name GCC loops for (doubtful)?

-- 
PMatos

Re: splitting add instructions

[Richard Henderson]

On 07/19/2011 08:08 AM, Paulo J. Matos wrote:
> So, this seems to have to do with the post-reload comparison optimization pass Richard mentioned.

Exactly.

> But I am still confused as to how GCC matches them. Is *_flags any
> special name GCC loops for (doubtful)?

No, and as you can see from the leading "*" in the name, the
name is not actually visible as a pattern.

As an experiment, please read the comment at the start of the
compare-elim.c file.  If you still do not understand how the
patch works, that suggests the documentation needs improvement.


r~

Re: splitting add instructions

[Paulo J. Matos]

On 19/07/11 16:36, Richard Henderson wrote:
>> But I am still confused as to how GCC matches them. Is *_flags any
>> special name GCC loops for (doubtful)?
>
> No, and as you can see from the leading "*" in the name, the
> name is not actually visible as a pattern.
>

Thought so... :)

> As an experiment, please read the comment at the start of the
> compare-elim.c file.  If you still do not understand how the
> patch works, that suggests the documentation needs improvement.
>
>
I did try to find the file that implements the pass but unsuccessfully. 
That's the one.

Great explanation in the comment header. Thank you, everything is 
clearer now.

Cheers,

-- 
PMatos

Re: splitting add instructions

[Ian Lance Taylor]

"Paulo J. Matos" <pocmatos@gmail.com> writes:

> Where the format specifiers b and t choose the top and bottom 16 bits
> of each operand. add is a 16bit addition operand and addc takes carry
> flag into consideration. Now, there are a lot of simple manipulations
> that can be made if I release GCC from always outputting these two
> instructions together. However, the problem is expanding an addhi3
> into two QImode add insn (which look the same), one of each outputs
> addc instead of add.

Look at add<mode>3_cc in gcc/config/i386/i386.md.  Look at how
add<dwi>3_doubleword splits to use it.

Ian

Re: splitting add instructions

[Paulo J. Matos]

On 18/07/11 17:58, Ian Lance Taylor wrote:
>
> Look at add<mode>3_cc in gcc/config/i386/i386.md.  Look at how
> add<dwi>3_doubleword splits to use it.
>

Thanks Ian, from what Richard said I need an add that doesn't modify 
carry in order to follow the approach there. Since I don't I guess I 
have to look for how it is done in mn10300 and rx ports.

cheers,

-- 
PMatos