PowerPC suboptimal "add with carry" optimization

PowerPC suboptimal "add with carry" optimization

[Joakim Tjernlund]

Noticed that gcc 4.3.4 doesn't optimize "add with carry" properly:

static u32
add32carry(u32 sum, u32 x)
{
  u32 z = sum + x;
  if (sum + x < x)
      z++;
  return z;
}
Becomes:
add32carry:
	add 3,3,4
	subfc 0,4,3
	subfe 0,0,0
	subfc 0,0,3
	mr 3,0
Instead of:
	addc 3,3,4
	addze 3,3

This slows down the the Internet checksum sigificantly

Also, doing this in a loop can be further optimized:

for(;len; --len)
   sum = add32carry(sum, *++buf);


	addic 3, 3, 0 /* clear carry */
.L31:
	lwzu 0,4(9)
	adde 3, 3, 0 /* add with carry */
	bdnz .L31

	addze 3, 3 /* add in final carry */

Re: PowerPC suboptimal "add with carry" optimization

[Ian Lance Taylor]

Joakim Tjernlund <joakim.tjernlund@transmode.se> writes:

> Noticed that gcc 4.3.4 doesn't optimize "add with carry" properly:

Please file a missed-optimization report according to
http://gcc.gnu.org/bugs/ .  Thanks.

Ian

Re: PowerPC suboptimal "add with carry" optimization

[Joakim Tjernlund]

Ian Lance Taylor <iant@google.com> wrote on 2010/04/25 20:07:03:
> Joakim Tjernlund <joakim.tjernlund@transmode.se> writes:
>
> > Noticed that gcc 4.3.4 doesn't optimize "add with carry" properly:
>
> Please file a missed-optimization report according to
> http://gcc.gnu.org/bugs/ .  Thanks.

I rather not, going through all that just for one odd report. I was hoping
an interested part would pick it up from my email.

 Jocke

Re: PowerPC suboptimal "add with carry" optimization

[Joakim Tjernlund]

Ian Lance Taylor <iant@google.com> wrote on 2010/04/25 20:07:03:
>
> Joakim Tjernlund <joakim.tjernlund@transmode.se> writes:
>
> > Noticed that gcc 4.3.4 doesn't optimize "add with carry" properly:

BTW, I can see in gcc src:
(define_insn ""
  [(set (match_operand:CC 0 "cc_reg_operand" "=x,?y")
	(compare:CC
	 (plus:SI (gt:SI (match_operand:SI 1 "gpc_reg_operand" "r,r")
			 (const_int 0))
		  (match_operand:SI 2 "gpc_reg_operand" "r,r"))
	 (const_int 0)))
   (clobber (match_scratch:SI 3 "=&r,&r"))]
  "TARGET_32BIT"
  "@
   {a|addc} %3,%1,%1\;{sfe|subfe} %3,%1,%3\;{aze.|addze.} %3,%2
   #"
  [(set_attr "type" "compare")
   (set_attr "length" "12,16")])
so there seems to be possible for gcc to emit them but how do
I make gcc do that?

       Jocke

Re: PowerPC suboptimal "add with carry" optimization

[Manuel López-Ibáñez]

On 26 April 2010 09:13, Joakim Tjernlund <joakim.tjernlund@transmode.se> wrote:
> Ian Lance Taylor <iant@google.com> wrote on 2010/04/25 20:07:03:
>> Joakim Tjernlund <joakim.tjernlund@transmode.se> writes:
>>
>> > Noticed that gcc 4.3.4 doesn't optimize "add with carry" properly:
>>
>> Please file a missed-optimization report according to
>> http://gcc.gnu.org/bugs/ .  Thanks.
>
> I rather not, going through all that just for one odd report. I was hoping
> an interested part would pick it up from my email.

What is to be done besides what you have done here but in a more
useful, structured manner? I am asking because we want to make things
simple but not simpler than they become more complex for us.

Aren't you interested in someone fixing the bug?

Manuel.

Re: PowerPC suboptimal "add with carry" optimization

[Joakim Tjernlund]

Manuel López-Ibáñez <lopezibanez@gmail.com> wrote on 2010/04/26 13:59:04:
> On 26 April 2010 09:13, Joakim Tjernlund <joakim.tjernlund@transmode.se> wrote:
> > Ian Lance Taylor <iant@google.com> wrote on 2010/04/25 20:07:03:
> >> Joakim Tjernlund <joakim.tjernlund@transmode.se> writes:
> >>
> >> > Noticed that gcc 4.3.4 doesn't optimize "add with carry" properly:
> >>
> >> Please file a missed-optimization report according to
> >> http://gcc.gnu.org/bugs/ .  Thanks.
> >
> > I rather not, going through all that just for one odd report. I was hoping
> > an interested part would pick it up from my email.
>
> What is to be done besides what you have done here but in a more
> useful, structured manner? I am asking because we want to make things
> simple but not simpler than they become more complex for us.

Lots of stuff to read on that page, lots of info to supply,
registering an account, specify all that system info and so on.

>
> Aren't you interested in someone fixing the bug?

Sure or better yet, show me some way to restructure the C code so proper
asm code is generated.

Re: PowerPC suboptimal "add with carry" optimization

[Manuel López-Ibáñez]

On 26 April 2010 14:21, Joakim Tjernlund <joakim.tjernlund@transmode.se> wrote:
> Manuel López-Ibáñez <lopezibanez@gmail.com> wrote on 2010/04/26 13:59:04:
>> On 26 April 2010 09:13, Joakim Tjernlund <joakim.tjernlund@transmode.se> wrote:
>> > Ian Lance Taylor <iant@google.com> wrote on 2010/04/25 20:07:03:
>> >> Joakim Tjernlund <joakim.tjernlund@transmode.se> writes:
>> >>
>> >> > Noticed that gcc 4.3.4 doesn't optimize "add with carry" properly:
>> >>
>> >> Please file a missed-optimization report according to
>> >> http://gcc.gnu.org/bugs/ .  Thanks.
>> >
>> > I rather not, going through all that just for one odd report. I was hoping
>> > an interested part would pick it up from my email.
>>
>> What is to be done besides what you have done here but in a more
>> useful, structured manner? I am asking because we want to make things
>> simple but not simpler than they become more complex for us.
>
> Lots of stuff to read on that page, lots of info to supply,
> registering an account, specify all that system info and so on.
>

I don't think it will take you much more than 15 minutes.

>> Aren't you interested in someone fixing the bug?
>
> Sure or better yet, show me some way to restructure the C code so proper
> asm code is generated.

This would perhaps help you now but not a future you, not anyone else
in the world. (On the other hand, I don't have a workaround, sorry).

Cheers,

Manuel.

Re: PowerPC suboptimal "add with carry" optimization

[Pekka Enberg]

On Mon, Apr 26, 2010 at 3:36 PM, Manuel López-Ibáñez
<lopezibanez@gmail.com> wrote:
>>> What is to be done besides what you have done here but in a more
>>> useful, structured manner? I am asking because we want to make things
>>> simple but not simpler than they become more complex for us.
>>
>> Lots of stuff to read on that page, lots of info to supply,
>> registering an account, specify all that system info and so on.
>
> I don't think it will take you much more than 15 minutes.

There's been a long "why not contribute to GCC thread" so to point out
the obvious...

I guess that's the point, really. 15 minutes for what exactly? All the
information is right there in the email Joakim sent. You are trying to
make life easier for developers, not users or testers.

                        Pekka

Re: PowerPC suboptimal "add with carry" optimization

[David Edelsohn]

In Mon, Apr 26, 2010 at 8:42 AM, Pekka Enberg <penberg@cs.helsinki.fi> wrote:
> On Mon, Apr 26, 2010 at 3:36 PM, Manuel López-Ibáñez
> <lopezibanez@gmail.com> wrote:
>>>> What is to be done besides what you have done here but in a more
>>>> useful, structured manner? I am asking because we want to make things
>>>> simple but not simpler than they become more complex for us.
>>>
>>> Lots of stuff to read on that page, lots of info to supply,
>>> registering an account, specify all that system info and so on.
>>
>> I don't think it will take you much more than 15 minutes.
>
> There's been a long "why not contribute to GCC thread" so to point out
> the obvious...
>
> I guess that's the point, really. 15 minutes for what exactly? All the
> information is right there in the email Joakim sent. You are trying to
> make life easier for developers, not users or testers.

There are a large number of users and a small number of developers.
Why is it so large a burden to ask users to provide the information in
a standard format in a centralized, trackable location, like GCC
Bugzilla?

Thanks, David

Re: PowerPC suboptimal "add with carry" optimization

[Pekka Enberg]

Hi David,

On Mon, Apr 26, 2010 at 3:45 PM, David Edelsohn <dje.gcc@gmail.com> wrote:
> There are a large number of users and a small number of developers.
> Why is it so large a burden to ask users to provide the information in
> a standard format in a centralized, trackable location, like GCC
> Bugzilla?

I'm not sure I understand the question. If you're arguing that it's
_not_ a burden, we have Joakim's reaction as proof that it's a burden
for *some* people. And if you're arguing that people shouldn't
consider it as a burden, then well, all I can say that you're arguing
with reality. Whether or not that represents a significant portion of
your user and tester-base is unknown to me.

                        Pekka

Re: PowerPC suboptimal "add with carry" optimization

[David Edelsohn]

On Mon, Apr 26, 2010 at 8:21 AM, Joakim Tjernlund
<joakim.tjernlund@transmode.se> wrote:
> Manuel López-Ibáñez <lopezibanez@gmail.com> wrote on 2010/04/26 13:59:04:
>> On 26 April 2010 09:13, Joakim Tjernlund <joakim.tjernlund@transmode.se> wrote:
>> > Ian Lance Taylor <iant@google.com> wrote on 2010/04/25 20:07:03:
>> >> Joakim Tjernlund <joakim.tjernlund@transmode.se> writes:
>> >>
>> >> > Noticed that gcc 4.3.4 doesn't optimize "add with carry" properly:
>> >>
>> >> Please file a missed-optimization report according to
>> >> http://gcc.gnu.org/bugs/ .  Thanks.
>> >
>> > I rather not, going through all that just for one odd report. I was hoping
>> > an interested part would pick it up from my email.
>>
>> What is to be done besides what you have done here but in a more
>> useful, structured manner? I am asking because we want to make things
>> simple but not simpler than they become more complex for us.
>
> Lots of stuff to read on that page, lots of info to supply,
> registering an account, specify all that system info and so on.

You do not need to register an account to report a bug or request a
feature enhancement.  Some of the information can be left blank, but
if we do not have information about the system and an example, we may
not understand the request or may not be able to reproduce the problem
and fix it.

>> Aren't you interested in someone fixing the bug?
>
> Sure or better yet, show me some way to restructure the C code so proper
> asm code is generated.

You referred to PowerPC patterns in GCC that use the carry
instructions.  Those patterns are optimizations for materializing a
truthvalue in a GPR or performance a 64 bit arithmetic operation in 32
bit mode.  The PowerPC port of GCC does not recognize general carry
arithmetic operations yet and track the carry bit.

Thanks, David

Re: PowerPC suboptimal "add with carry" optimization

[Joakim Tjernlund]

David Edelsohn <dje.gcc@gmail.com> wrote on 2010/04/26 14:54:55:
>
> On Mon, Apr 26, 2010 at 8:21 AM, Joakim Tjernlund
> <joakim.tjernlund@transmode.se> wrote:
> > Manuel López-Ibáñez <lopezibanez@gmail.com> wrote on 2010/04/26 13:59:04:
> >> On 26 April 2010 09:13, Joakim Tjernlund <joakim.tjernlund@transmode.se> wrote:
> >> > Ian Lance Taylor <iant@google.com> wrote on 2010/04/25 20:07:03:
> >> >> Joakim Tjernlund <joakim.tjernlund@transmode.se> writes:
> >> >>
> >> >> > Noticed that gcc 4.3.4 doesn't optimize "add with carry" properly:
> >> >>
> >> >> Please file a missed-optimization report according to
> >> >> http://gcc.gnu.org/bugs/ .  Thanks.
> >> >
> >> > I rather not, going through all that just for one odd report. I was hoping
> >> > an interested part would pick it up from my email.
> >>
> >> What is to be done besides what you have done here but in a more
> >> useful, structured manner? I am asking because we want to make things
> >> simple but not simpler than they become more complex for us.
> >
> > Lots of stuff to read on that page, lots of info to supply,
> > registering an account, specify all that system info and so on.
>
> You do not need to register an account to report a bug or request a

Just tried that and don't see that.

> feature enhancement.  Some of the information can be left blank, but
> if we do not have information about the system and an example, we may
> not understand the request or may not be able to reproduce the problem
> and fix it.

Just go look at that page, it is so much info that if the bug isn't very importat
you quickly decide it is not worth it. How I am supposed to know what is need
or not without reading all that?

>
> >> Aren't you interested in someone fixing the bug?
> >
> > Sure or better yet, show me some way to restructure the C code so proper
> > asm code is generated.
>
> You referred to PowerPC patterns in GCC that use the carry
> instructions.  Those patterns are optimizations for materializing a
> truthvalue in a GPR or performance a 64 bit arithmetic operation in 32
> bit mode.  The PowerPC port of GCC does not recognize general carry
> arithmetic operations yet and track the carry bit.

OK, thanks. I know x86 do I had hope there was some way to do that i
PowerPC too.

Re: PowerPC suboptimal "add with carry" optimization

[Manuel López-Ibáñez]

On 26 April 2010 14:42, Pekka Enberg <penberg@cs.helsinki.fi> wrote:
> On Mon, Apr 26, 2010 at 3:36 PM, Manuel López-Ibáñez
> <lopezibanez@gmail.com> wrote:
>>>> What is to be done besides what you have done here but in a more
>>>> useful, structured manner? I am asking because we want to make things
>>>> simple but not simpler than they become more complex for us.
>>>
>>> Lots of stuff to read on that page, lots of info to supply,
>>> registering an account, specify all that system info and so on.
>>
>> I don't think it will take you much more than 15 minutes.
>
> There's been a long "why not contribute to GCC thread" so to point out
> the obvious...

I know. I started it. ;-)

> I guess that's the point, really. 15 minutes for what exactly? All the
> information is right there in the email Joakim sent. You are trying to
> make life easier for developers, not users or testers.

I think you misunderstood the thread then. More users and more testers
would be nice but we really need more developers (or people
contributing documentation, infrastructure support, etc). So making
life easier for developers is contributing. Making life harder for
developers is not.

You mention "reality" below. If you really want a particular bug
fixed, then you should try to help the developers to fix it. Reality
is that bugs that are not in bugzilla do not get fixed because
developers prefer to spend their time efficiently on well-structured
reports and on high impact bugs. So my comment is trying to help you
to increase the chances that your bug gets fixed. But if yourself
don't care, then why do you expect others do?

Cheers,

Manuel.

Re: PowerPC suboptimal "add with carry" optimization

[Manuel López-Ibáñez]

On 26 April 2010 15:22, Joakim Tjernlund <joakim.tjernlund@transmode.se> wrote:
>
>> feature enhancement.  Some of the information can be left blank, but
>> if we do not have information about the system and an example, we may
>> not understand the request or may not be able to reproduce the problem
>> and fix it.
>
> Just go look at that page, it is so much info that if the bug isn't very importat
> you quickly decide it is not worth it. How I am supposed to know what is need
> or not without reading all that?

You are totally right here. But this is not because we do not want to
improve that page. Again, it is a lack of people contributing to
improve that page. OK. I will stop fixing bugs and try to work on
improving that page. Do you want to help me? It would be great to have
some user-feedback when doing it.

Cheers,

Manuel.

Re: PowerPC suboptimal "add with carry" optimization

[Joakim Tjernlund]

Manuel López-Ibáñez <lopezibanez@gmail.com> wrote on 2010/04/26 15:29:54:
>
> On 26 April 2010 15:22, Joakim Tjernlund <joakim.tjernlund@transmode.se> wrote:
> >
> >> feature enhancement.  Some of the information can be left blank, but
> >> if we do not have information about the system and an example, we may
> >> not understand the request or may not be able to reproduce the problem
> >> and fix it.
> >
> > Just go look at that page, it is so much info that if the bug isn't very importat
> > you quickly decide it is not worth it. How I am supposed to know what is need
> > or not without reading all that?
>
> You are totally right here. But this is not because we do not want to
> improve that page. Again, it is a lack of people contributing to
> improve that page. OK. I will stop fixing bugs and try to work on
> improving that page. Do you want to help me? It would be great to have
> some user-feedback when doing it.

You do what you want, it is not for me to say. And no I am not into fixing
that page either.

Anyway, I *looked* at the page and it said something about gccbug so I tried
that, not obvious either but I let me fire off a report an back came
bug ID 43892

      Jocke

Re: PowerPC suboptimal "add with carry" optimization

[David Edelsohn]

On Mon, Apr 26, 2010 at 9:22 AM, Joakim Tjernlund
<joakim.tjernlund@transmode.se> wrote:
>
> David Edelsohn <dje.gcc@gmail.com> wrote on 2010/04/26 14:54:55:
>>
>> On Mon, Apr 26, 2010 at 8:21 AM, Joakim Tjernlund
>> <joakim.tjernlund@transmode.se> wrote:
>> > Manuel López-Ibáñez <lopezibanez@gmail.com> wrote on 2010/04/26 13:59:04:
>> >> On 26 April 2010 09:13, Joakim Tjernlund <joakim.tjernlund@transmode.se> wrote:
>> >> > Ian Lance Taylor <iant@google.com> wrote on 2010/04/25 20:07:03:
>> >> >> Joakim Tjernlund <joakim.tjernlund@transmode.se> writes:
>> >> >>
>> >> >> > Noticed that gcc 4.3.4 doesn't optimize "add with carry" properly:
>> >> >>
>> >> >> Please file a missed-optimization report according to
>> >> >> http://gcc.gnu.org/bugs/ .  Thanks.
>> >> >
>> >> > I rather not, going through all that just for one odd report. I was hoping
>> >> > an interested part would pick it up from my email.
>> >>
>> >> What is to be done besides what you have done here but in a more
>> >> useful, structured manner? I am asking because we want to make things
>> >> simple but not simpler than they become more complex for us.
>> >
>> > Lots of stuff to read on that page, lots of info to supply,
>> > registering an account, specify all that system info and so on.
>>
>> You do not need to register an account to report a bug or request a
>
> Just tried that and don't see that.

Sorry, I was mistaken.  I thought that one could submit bug reports
without registering an account.

Thanks for opening a PR for the enhancement request.

Thanks, David

Re: PowerPC suboptimal "add with carry" optimization

[Ian Lance Taylor]

Joakim Tjernlund <joakim.tjernlund@transmode.se> writes:

> Anyway, I *looked* at the page and it said something about gccbug so I tried
> that, not obvious either but I let me fire off a report an back came
> bug ID 43892

Thanks for filing the report.

Ian

Re: PowerPC suboptimal "add with carry" optimization

[Ian Lance Taylor]

Joakim Tjernlund <joakim.tjernlund@transmode.se> writes:

> Ian Lance Taylor <iant@google.com> wrote on 2010/04/25 20:07:03:
>>
>> Joakim Tjernlund <joakim.tjernlund@transmode.se> writes:
>>
>> > Noticed that gcc 4.3.4 doesn't optimize "add with carry" properly:
>
> BTW, I can see in gcc src:
> (define_insn ""
>   [(set (match_operand:CC 0 "cc_reg_operand" "=x,?y")
> 	(compare:CC
> 	 (plus:SI (gt:SI (match_operand:SI 1 "gpc_reg_operand" "r,r")
> 			 (const_int 0))
> 		  (match_operand:SI 2 "gpc_reg_operand" "r,r"))
> 	 (const_int 0)))
>    (clobber (match_scratch:SI 3 "=&r,&r"))]
>   "TARGET_32BIT"
>   "@
>    {a|addc} %3,%1,%1\;{sfe|subfe} %3,%1,%3\;{aze.|addze.} %3,%2
>    #"
>   [(set_attr "type" "compare")
>    (set_attr "length" "12,16")])
> so there seems to be possible for gcc to emit them but how do
> I make gcc do that?

That unfortunately does not do what you want.  That instruction
sequence uses a scratch register to set a condition register to
whether (a + b) > 0.

Ian

Re: PowerPC suboptimal "add with carry" optimization

[Pekka Enberg]

Hi Manuel,

On Mon, Apr 26, 2010 at 4:27 PM, Manuel López-Ibáñez
<lopezibanez@gmail.com> wrote:
>> I guess that's the point, really. 15 minutes for what exactly? All the
>> information is right there in the email Joakim sent. You are trying to
>> make life easier for developers, not users or testers.
>
> I think you misunderstood the thread then. More users and more testers
> would be nice but we really need more developers (or people
> contributing documentation, infrastructure support, etc). So making
> life easier for developers is contributing. Making life harder for
> developers is not.

I guess the conventional wisdom says that the way to attract new
developers is to first attract users and testers and then turn them
into contributors.

I can understand what you're trying to achieve with your bug tracking
system but I'm questioning if it's working for you. I am looking at
this from Linux kernel development point of view and the lessons
learned there is that the lower you can make the barrier for entry
(bug reports, patches, etc.), the more likely you're going to keep old
people around and attract new ones.

But anyway, I'm not trying to argue with you or force my views on you.
I'm just stating my observation which is extremely biased towards what
I see as a working model (the Linux kernel).

On Mon, Apr 26, 2010 at 4:27 PM, Manuel López-Ibáñez
<lopezibanez@gmail.com> wrote:
> You mention "reality" below. If you really want a particular bug
> fixed, then you should try to help the developers to fix it. Reality
> is that bugs that are not in bugzilla do not get fixed because
> developers prefer to spend their time efficiently on well-structured
> reports and on high impact bugs. So my comment is trying to help you
> to increase the chances that your bug gets fixed. But if yourself
> don't care, then why do you expect others do?

That's something you can change. But trying to convince people that
your bug tracking system is not a pain in the ass isn't going to
change things.

                        Pekka

Re: PowerPC suboptimal "add with carry" optimization

[Manuel López-Ibáñez]

On 26 April 2010 16:33, Pekka Enberg <penberg@cs.helsinki.fi> wrote:
>
> I guess the conventional wisdom says that the way to attract new
> developers is to first attract users and testers and then turn them
> into contributors.

Unfortunately, this is not the case. We have probably hundreds of
thousands of users, people that can certainly program in the language
that GCC is written. We do not have many contributors. I don't have
numbers but I have the intuition that the ratio between users that are
developers and contributors to the project is much higher in GCC than
for the Linux kernel.

> I can understand what you're trying to achieve with your bug tracking
> system but I'm questioning if it's working for you. I am looking at

That depends what you mean by working. It works for me because
bugzilla does not get in my way when fixing bugs and most of the time
is very useful. It also works for people that spend time reporting
good bugs. Perhaps it doesn't work for people that don't have the time
to follow up on bugs. But then, we have already a lot of open reports
and features to work on, so perhaps missing those reports is actually
saving us time. On the other hand, if people are willing to spent time
reporting good bugs and perhaps providing a patch, and they don't have
the tools or the infrastructure to help them, *that* is really bad.
That is the people that we want to help.

> this from Linux kernel development point of view and the lessons
> learned there is that the lower you can make the barrier for entry
> (bug reports, patches, etc.), the more likely you're going to keep old
> people around and attract new ones.

Thanks for your comments, even if we disagree. I am spending a lot of
time thinking about these issues lately and I certainly appreciate
your input.

Cheers,

Manuel.