Fix for GCC Bugzilla Bug 36133

Fix for GCC Bugzilla Bug 36133

[Gunnar Von Boehn]

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

Hi,

I'm hereby emailing you again, the test case and patch that are
included to the GCC bugtracker of Bug 36133.


Problem desciption:
---------------------------
GCC 68k/Coldfire backends creates unnecessary TST instructions.
On the 68k/Coldfire many instructions do set the Condition Codes automaticly.
GCC is not aware of this and GCC creates unneeded TST instructions to
create these conditions code again.


Fix:
----
Add instrutcition definitions to machine description to inform GCC
about the instructions setting the conditions codes.


How to reproduce:
-------------------------
Compile this example function withand look at the produces ASM code.
m68k-linux-gnu-gcc -mcpu=54455 -o example -Os -fomit-frame-pointer example.c
void * copy_32x4a(void *destparam, const void *srcparam, size_t size)
{
       int *dest = destparam;
       const int *src = srcparam;
       int size32;
       size32 = size / 16;
       for (; size32; size32--) {
               *dest++ = *src++;
               *dest++ = *src++;
               *dest++ = *src++;
               *dest++ = *src++;
       }
}

Look at the code and see that GCC is not aware that LSRL and the SUBQL
do both set the condition codes already, there is no need for using an
extra TST instruction at all.

Please apply the patch and recompile.
GCC is now aware that the LSR instruction does set the CC already and
will not create the unneeded TST.

Please mind that the attached patch will fix only the SHIFT instruction.
Can you use this example for the other 68K instructions, or shall I
help with this?


Kind regards

Gunnar von Boehn

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: GCC36133.patch --]
[-- Type: text/x-patch; name=GCC36133.patch, Size: 894 bytes --]

Index: gcc/config/m68k/m68k.md
===================================================================
*** gcc/config/m68k/m68k.md.orig        2008-05-30 10:00:55.000000000 +0200
--- gcc/config/m68k/m68k.md     2008-06-04 17:01:11.000000000 +0200
***************
*** 5198,5203 ****
--- 5198,5215 ----
    [(set_attr "type" "shift")
     (set_attr "opy" "2")])

+ (define_insn "*lshrsi3_cc"
+   [(set (cc0)
+       (lshiftrt:SI (match_operand:SI 1 "register_operand" "0")
+                    (match_operand:SI 2 "general_operand" "dI")))
+    (set (match_operand:SI 0 "register_operand" "=d")
+       (lshiftrt:SI (match_dup 1)
+                    (match_dup 2)))]
+   ""
+   "lsr%.l %2,%0"
+   [(set_attr "type" "shift")
+    (set_attr "opy" "2")])
+
  (define_insn "lshrhi3"
    [(set (match_operand:HI 0 "register_operand" "=d")
        (lshiftrt:HI (match_operand:HI 1 "register_operand" "0")

Re: Fix for GCC Bugzilla Bug 36133

[Andreas Schwab]

"Gunnar Von Boehn" <gunnar@genesi-usa.com> writes:

> Please apply the patch and recompile.
> GCC is now aware that the LSR instruction does set the CC already and
> will not create the unneeded TST.

That does not look correct, see the comment in notice_update_cc:

      case ASHIFT: case ASHIFTRT: case LSHIFTRT:
      case ROTATE: case ROTATERT:
	/* These instructions always clear the overflow bit, and set
	   the carry to the bit shifted out.  */
	/* ??? We don't currently have a way to signal carry not valid,
	   nor do we check for it in the branch insns.  */
	CC_STATUS_INIT;
	break;

Andreas.

-- 
Andreas Schwab, SuSE Labs, schwab@suse.de
SuSE Linux Products GmbH, Maxfeldstraße 5, 90409 Nürnberg, Germany
PGP key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: Fix for GCC Bugzilla Bug 36133

[Gunnar Von Boehn]

Hi Andreas,

Please have a look at the MOTOROLA 68k Programming model (M68000PRM)
for a definition of how the flags are set by the shift instructions.

ie. Page 218 for the LSL, LSR instructions:

Bit
X — Set according to the last bit shifted out of the operand;
unaffected for a shift
    count of zero.
N — Set if the result is negative; cleared otherwise.
Z — Set if the result is zero; cleared otherwise.
V — Always cleared.
C — Set according to the last bit shifted out of the operand; cleared
for a shift count
    of zero.


Lets compare how the flags are set to how the flags would be set by
the otherwise used TST instruction:

p 296 TST

X — Not affected.
N — Set if the operand is negative; cleared otherwise.
Z — Set if the operand is zero; cleared otherwise.
V — Always cleared.
C — Always cleared.

As you can see the flags N Z V are set 100% the same way by LSX and TST.


Do you agree with me that the flags N,Z,V are those that will be used by BCC?
Isn't it true that GCC does not allow the user to generate BCC
instructions which use the carry flag?


Kind regards
Gunnar von Boehn


On Tue, Jun 17, 2008 at 1:53 PM, Andreas Schwab <schwab@suse.de> wrote:
> "Gunnar Von Boehn" <gunnar@genesi-usa.com> writes:
>
>> Please apply the patch and recompile.
>> GCC is now aware that the LSR instruction does set the CC already and
>> will not create the unneeded TST.
>
> That does not look correct, see the comment in notice_update_cc:
>
>      case ASHIFT: case ASHIFTRT: case LSHIFTRT:
>      case ROTATE: case ROTATERT:
>        /* These instructions always clear the overflow bit, and set
>           the carry to the bit shifted out.  */
>        /* ??? We don't currently have a way to signal carry not valid,
>           nor do we check for it in the branch insns.  */
>        CC_STATUS_INIT;
>        break;
>
> Andreas.
>
> --
> Andreas Schwab, SuSE Labs, schwab@suse.de
> SuSE Linux Products GmbH, Maxfeldstraße 5, 90409 Nürnberg, Germany
> PGP key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
> "And now for something completely different."
>

Re: Fix for GCC Bugzilla Bug 36133

[Andreas Schwab]

"Gunnar Von Boehn" <gunnar@genesi-usa.com> writes:

> Do you agree with me that the flags N,Z,V are those that will be used by BCC?
> Isn't it true that GCC does not allow the user to generate BCC
> instructions which use the carry flag?

The carry flag is used by bhi/bls, which are generated by the gtu/ltu
patterns.

Andreas.

-- 
Andreas Schwab, SuSE Labs, schwab@suse.de
SuSE Linux Products GmbH, Maxfeldstraße 5, 90409 Nürnberg, Germany
PGP key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: Fix for GCC Bugzilla Bug 36133

[Gunnar Von Boehn]

Hallo Andreas,

> The carry flag is used by bhi/bls, which are generated by the gtu/ltu
> patterns.

Can GCC create a BHI instructions that follows a LSR ?
Honestly, I fail to see the possibility for this in GCC.

Doesn't the BCC created by GCC behave like a BCC after a TST against ZERO?
Isn't it true that such a BCC would never be a BHI but always a BNE or BEQ ?

If you think its somehow possible to get GCC to create a BHI then
please be so kind
and help me to understand this and please give a C-example.

Kind regards
Gunnar

Re: Fix for GCC Bugzilla Bug 36133

[Gunnar Von Boehn]

Hi Andreas,

What is your opinion to this topic now?


Maybe I can summarize the question again.
When I understood your question correctly then it was:
"Does it make sense to mark the CC as invalid after a shift instruction."
Your point was that a shift will "trash" the carry flag.
If the CC is marked as valid GCC will but BCC instructions after the shift.
If the CC is marked as invalid then GCC will put a TST before the BCC
instruction to regenerate the conditions codes.

As a matter of fact TST will always clear the carry flag.
This means, that there can never be an BCC that depends on the carry
flag after the TST instruction.
There can of course only be BCC instructions after the TST that use
condition flags that are actually set by TST (these are N and Z)
The flags (N and Z ) are both correctly set ba the shift instruction as well.
Ergo: The TST instruction is redundant and should not by generated by GCC.
Ergo: The CC should be marked as valid after a shift or rotate instruction.

Do you agree with me here?

It would be good if we finally can fix this again.
AFAIK GCC 2.9  did behave correctly in this matter.

Cheers
Gunnar

The question basicly is does it make sense to makr the CC as invaklid
  "CC_STATUS_INIT"

On Thu, Jun 19, 2008 at 2:43 PM, Gunnar Von Boehn <gunnar@genesi-usa.com> wrote:
> Hallo Andreas,
>
>> The carry flag is used by bhi/bls, which are generated by the gtu/ltu
>> patterns.
>
> Can GCC create a BHI instructions that follows a LSR ?
> Honestly, I fail to see the possibility for this in GCC.
>
> Doesn't the BCC created by GCC behave like a BCC after a TST against ZERO?
> Isn't it true that such a BCC would never be a BHI but always a BNE or BEQ ?
>
> If you think its somehow possible to get GCC to create a BHI then
> please be so kind
> and help me to understand this and please give a C-example.
>
> Kind regards
> Gunnar
>

Re: Fix for GCC Bugzilla Bug 36133

[Andreas Schwab]

"Gunnar Von Boehn" <gunnar@genesi-usa.com> writes:

> Maybe I can summarize the question again.
> When I understood your question correctly then it was:
> "Does it make sense to mark the CC as invalid after a shift instruction."
> Your point was that a shift will "trash" the carry flag.
> If the CC is marked as valid GCC will but BCC instructions after the shift.
> If the CC is marked as invalid then GCC will put a TST before the BCC
> instruction to regenerate the conditions codes.

You need to argue on the RTL insns that can be generated.  I cannot
prove that there will never be a bgtu/bltu insn following the lshiftr
insn.  If that can happen your change would introduce a wrong-code bug.

In any case, the right place to change that is in notice_update_cc
anyway.

> AFAIK GCC 2.9  did behave correctly in this matter.

I don't know what gcc 2.9 refers to, but the handling of lshiftr in
notice_update_cc was changed 5 years ago, presumably because of a
wrong-code bug (I cannot find any reference in the gcc-patches archive).

Andreas.

-- 
Andreas Schwab, SuSE Labs, schwab@suse.de
SuSE Linux Products GmbH, Maxfeldstraße 5, 90409 Nürnberg, Germany
PGP key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: Fix for GCC Bugzilla Bug 36133

[Gunther Nikl]

Andreas Schwab wrote:
> "Gunnar Von Boehn" <gunnar@genesi-usa.com> writes:
> 
>> AFAIK GCC 2.9  did behave correctly in this matter.
> 
> I don't know what gcc 2.9 refers to, but the handling of lshiftr in

That quite likely refers to GCC 2.95.x

> notice_update_cc was changed 5 years ago, presumably because of a
> wrong-code bug (I cannot find any reference in the gcc-patches archive).

The following link should be the thread about that change you were
looking for: http://gcc.gnu.org/ml/gcc/2003-10/msg01236.html

Gunther

Re: Fix for GCC Bugzilla Bug 36133

[Andreas Schwab]

Gunther Nikl <gni@gecko.de> writes:

> Andreas Schwab wrote:
>> "Gunnar Von Boehn" <gunnar@genesi-usa.com> writes:
>> 
>>> AFAIK GCC 2.9  did behave correctly in this matter.
>> 
>> I don't know what gcc 2.9 refers to, but the handling of lshiftr in
>
> That quite likely refers to GCC 2.95.x
>
>> notice_update_cc was changed 5 years ago, presumably because of a
>> wrong-code bug (I cannot find any reference in the gcc-patches archive).
>
> The following link should be the thread about that change you were
> looking for: http://gcc.gnu.org/ml/gcc/2003-10/msg01236.html

Thanks.  That's exactly the test case I was look for.

Andreas.

-- 
Andreas Schwab, SuSE Labs, schwab@suse.de
SuSE Linux Products GmbH, Maxfeldstraße 5, 90409 Nürnberg, Germany
PGP key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Fwd: Fix for GCC Bugzilla Bug 36133

[Gunnar Von Boehn]

Hallo Gunther,


So you are basically saying is that this code was produced by GCC

>  void foo (unsigned long j)
>  {
>    unsigned int i;
>    for (i = 0; i < (j>>5); ++i)
>      ;
>  }
>
>(Similiar code is in GCC which is broken for me since your change)
>
>Compiled with -O before your change:
>
> foo:  clr.l %d1
>       move.l 4(%sp),%d0
>       lsr.l #5,%d0
>       move.l %d0,%a0
>       cmp.l %d1,%d0    <- good
>       jbls .L7
>  .L5: addq.l #1,%d1
>       cmp.l %d1,%a0
>       jbhi .L5
>  .L7: rts
>
>After your change
>
> foo:  clr.l %d1
>       move.l 4(%sp),%d0
>       lsr.l #5,%d0
>       move.l %d0,%a0
>       jbls .L7
>  .L5: addq.l #1,%d1
>       cmp.l %a0,%d1
>       jbcs .L5
>  .L7: rts


Basicly it boils down to:
       clr.l %d1
       lsr.l #5,%d0
       cmp.l %d1,%d0   # CMP with 0 !!
       jbls .L7               # Branch on Carry-flag | Zero-Flag

Do I see this correctly that GCC sees that D1 is zero,
So GCC realizes that a CMP with Zero is not needed.
- A CMP of "CMP %d1,%d0" set the conditions codes according to (D0 - D1)
- As D1 is known to be zero this is equally to the CC set the instructions.

I think the root cause of the issue is that this old GCC version DID
shorten the instruction
but it DID not shorten the JUMP to not contain any "impossible" condition-flags.

Condition "LS" is Lower or same (Carry | Zero )
There can never be a Carry-condition be created by a CMP with source of zero !

The correctly shortened Condition is a sole "Z".
If GCC would not only drop the CMP with Zero but correctly shorten the
Branch condition then there would be no problem.
The correct Branch condition is  Z =>  BEQ


Does GCC still not shorten the conditions correctly, or is this fixed
in newer GCC version?

Would it be possible to have GCC correctly shorten impossible branch
conditions away?


Cheers
Gunnar


On Fri, Jun 27, 2008 at 2:59 PM, Gunther Nikl <gni@gecko.de> wrote:
> Andreas Schwab wrote:
>> "Gunnar Von Boehn" <gunnar@genesi-usa.com> writes:
>>
>>> AFAIK GCC 2.9  did behave correctly in this matter.
>>
>> I don't know what gcc 2.9 refers to, but the handling of lshiftr in
>
> That quite likely refers to GCC 2.95.x
>
>> notice_update_cc was changed 5 years ago, presumably because of a
>> wrong-code bug (I cannot find any reference in the gcc-patches archive).
>
> The following link should be the thread about that change you were
> looking for: http://gcc.gnu.org/ml/gcc/2003-10/msg01236.html
>
> Gunther
>

Re: Fix for GCC Bugzilla Bug 36133

[Andreas Krebbel]

Hi Gunnar, Hi Andreas,

although your thoughts are correct if you think assembly-wise.  I
think GCC could indeed create lsr;tst;jhi combinations.  As you say
the branch would then never be taken due to the carry flag but it is
still correct code which would break if the tst gets optimized away.

Maybe Andreas was thinking about an example like this:

int
foo (unsigned int a, unsigned int b, unsigned int c)
{
  unsigned int t = a << b;

  if (t > c)
    return 31;
  return 42;
}

int
bar (unsigned int a, unsigned int b)
{ return foo (a, b, 0); }

The code for foo would contain something like this:
...
       lsl.l %d1,%d0
       cmp.l 16(%fp),%d0
       jhi .L2

But after inlining GCC is able to see that the second operand is
always 0 and replaces the cmp instruction with the simpler tst.
Although that would render the carry flag check in jhi pointless it is
correct to do so. The cmp instruction would in that case never have
set the carry flag anyway - very much the same way the tst instruction
never does.

Unfortunately the example is not really a good one since the inlining
is already takes place at tree level so that the RTL expansion already
picks the NE comparison operator for bar which result in a jne
instruction. But I think you can imagine that a more intricate example
could make GCC to recognize the possibility to replace cmp with tst
later in the RTL optimization which might lead to the lsl; tst; jhi
combination.

I've pointed you to the solution you have posted since that's the way
we do it on S/390 - sorry for sending you in a somewhat wrong
direction.  It would be correct for 68k if the current semantics of CC
could be taken into account when matching instructions.  That's why
several back ends do not use cc0 for condition code handling. By using
a normal register as CC it is possible to do the matching over the
attached mode.  The mode of CC then makes sure that the compare and
the conditional branch fit together.  Using cc0 it is only possible to
state that the current CC is invalid to use what is done for the shift
instructions as Andreas pointed out.

Making the m68k back end to not use cc0 anymore would require a major
rework.  But I think it would be worth the effort since there are
probably a lot of situation were you could get rid of superfluous
tests. Andreas what do you think?

Another solution (although quite an ugly one) would be to do a check
for redundant tests in the machine dependent reorg pass but that's
certainly not preferable.

Bye,

-Andreas-

Re: Fix for GCC Bugzilla Bug 36133

[Andreas Schwab]

"Andreas Krebbel" <Andreas.Krebbel@de.ibm.com> writes:

> Making the m68k back end to not use cc0 anymore would require a major
> rework.  But I think it would be worth the effort since there are
> probably a lot of situation were you could get rid of superfluous
> tests. Andreas what do you think?

There has already been some discussions in the past about that.  IIRC
the major problem is that on m68k almost all insns touch the CC.

Andreas.

-- 
Andreas Schwab, SuSE Labs, schwab@suse.de
SuSE Linux Products GmbH, Maxfeldstraße 5, 90409 Nürnberg, Germany
PGP key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."