Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Steven Bosscher]

On 12/31/06, Paul Eggert <[EMAIL PROTECTED]> wrote:

Also, as I understand it this change shouldn't affect gcc's
SPEC benchmark scores, since they're typically done with -O3
or better.


It's not all about benchmark scores.  I think most users compile at
-O2 and they also won't understand why they get a performance drop on
their code.

You say you doubt it affects performance.  Based on what?  Facts
please, not guesses and hand-waiving...

Gr.
Steven

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Michael Veksler]

Robert Dewar wrote:

Andrew Pinski wrote:


-fwrapv-in-all-cases-except-loop-bounds



Again, please don't this the default for Fortran as integer
overflow has been undefined since at least 1977 so I don't think
it is a good idea for GCC in general anyways as evidence of Fortran.

-- Pinski


Well the question is whether the optimization buys anything
in practice for other than the loop bound case, I am guessing
it does not, and if that is the case there is an argument
for uniformity.


I don't understand why Fortran would make integer overflows undefined,
other than in a do loop (equivalent to for). C has the primal sin of no
proper for loops. In C "for" is simply syntactic sugar of a "while" loop.
When in Fortran you write

   do i = 0, 10

   ...

   end do

the compiler can know that "i" is the loop variable. It would have been
possible to mandate that "i" can't be modified in the body of the loop.
On the other hand, C does not have a way to tell the compiler:

   "this is my loop variable, it must not be modified inside the loop"

neither you can say:

   "this is the upper bound of the loop, it must not be modified"

either.

Any special treatment of "i" in

   for (i=0 ; i <= x ; ++i)

is problematic, because "i" might not be a real induction variable. Also
what about code like:

   for (i=0 ; i <= x ; ++i) {

   if (i<0) error();
   

   }

Should the call to error() be eliminated?
What about code like:

   for (i=0 ; i <= x ; ++i) {

   if (foo) {

   i++; // HERE
   
   return i;

   }
   

   }

Should gcc assume that since "i" is a loop induction variable, then it is
not wrapping? Not even at the line marked with "HERE" ? Or is gcc
is going to assume that no wrapping can happen in the "for (...;...;...)"
section, but wrapping can happen in the body?

I think that the best compromise between performance and reliability
would be to define (forget me for not using the terms defined in the
standard):

   Signed integer overflows are unspecified. The implementations
   may choose to treat overflows as trapping, wrapping or
   saturating.

   in the context of "for (A;B;C) D " , "while(B) D" or
   "do D while (B)":
   It is unspecified if B is evaluated to *false* some time after the
   execution of C or D results in signed integer overflow of
   variables that B uses. this is regardless of the behavior of
   overflows in other contexts.

This wording allows reasonable treating of

   for (i=0 ; i<=x && i>= 0 ; ++i) {.}

The compiler will not be allowed to eliminate the "i>=0" check since
i<=x   might return true when "i<=x && i>=0" would return false.

This wording also allows

   for (i=0 ; i<=x  ; ++i) {}

to be optimized to

   i=x+1

since is ok to assume that i<=x  returns *false* for i=MAX_INT+1.

--
Michael Veksler
http:///tx.technion.ac.il/~mveksler

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Gabriel Dos Reis]

Ian Lance Taylor <[EMAIL PROTECTED]> writes:

| Gabriel Dos Reis <[EMAIL PROTECTED]> writes:
| 
| > for this specific function (vrp_int_const_binop), I'm issuing a
| > warning inside the else-if  branch that tests for the overflowed
| > result.  I'm unclear why that is a false positive since the result is
| > known to overflow.  Could you elaborate? 
| 
| Within VRP, calculations are made on ranges.  The upper and lower
| limits of those ranges need not actually appear in the program.  If
| you warn whenever vrp_int_const_binop produces an overflow, you will
| get an enormous number of false positives.

Thanks for this explanation.

| I have a patch which issues warnings whenever gcc assumes that signed
| overflow is undefined, except in loop IV calculations.  I'm tweaking
| it to see whether it is possible to bootstrap gcc with this patch.  It
| currently builds libcpp with no warnings, but falls over on this code
| in decDivideOp in decNumber.c in libdecnumber:

OK, I see; since today is a bit special I may not be able to get back
to you as quickly as I would like.

-- Gaby

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Gabriel Dos Reis]

Paul Eggert <[EMAIL PROTECTED]> writes:

| [EMAIL PROTECTED] (Richard Kenner) writes:
| 
| > I found my copy of K&R (Second Edition)
| 
| Robert Dewar <[EMAIL PROTECTED]> writes:
| 
| > so in fact the new C standard has changed
| > nothing from a definitional point of view,
| 
| Wait, though: K&Rv2 is post-C89.  If memory serves, it was C89
| that established the rule that signed integer overflow has
| undefined behavior whereas unsigned overflow is well-defined.

My memory is that signed integer arithmetic overflow is undefined by
K&R C; unfortunately, my copy of the '77 edition of K&R is at office,
thousands of miles away from where I'm.

-- Gaby

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Gabriel Dos Reis]

Joe Buck <[EMAIL PROTECTED]> writes:

[...]

|  though I vaguely
| recall some complaints that you couldn't build v7 Unix if your compiler
| generated integer overflow traps.

this matches what I've told recently by some people who worked at bell
labs, in the unix room. 

-- Gaby

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Paul Eggert]

"Steven Bosscher" <[EMAIL PROTECTED]> writes:

> On 12/31/06, Paul Eggert <[EMAIL PROTECTED]> wrote:
>> Also, as I understand it this change shouldn't affect gcc's
>> SPEC benchmark scores, since they're typically done with -O3
>> or better.
>
> It's not all about benchmark scores.

But so far, benchmark scores are the only scores given by the people
who oppose having -O2 imply -fwrapv.  If the benchmarks use -O3 they
wouldn't be affected by such a change -- and if so, we have zero hard
evidence of any real harm being caused by having -O2 imply -fwrapv.

> I think most users compile at -O2

Yes, which is why there's so much argument about what -O2 should do

> You say you doubt it affects performance.  Based on what?  Facts
> please, not guesses and hand-waiving...

The burden of proof ought to be on the guys proposing -O2
optimizations that break longstanding code, not on the skeptics.

That being said, I just compiled GNU coreutils CVS on a Debian stable
x86 (2.4 GHz Pentium 4) using GCC 4.1.1.  With -O0, "sha512sum" on the
coreutils tar.gz file took 0.94 user CPU seconds (measured by "time
src/sha512sum coreutils-6.7-dirty.tar.gz").  With -O2 -fwrapv, 0.87
seconds.  With plain -O2, 0.86 seconds.

I also tried gzip 1.3.10, compressing its own tar file with a -9
compression option.  With -O0, 0.30 user CPU seconds.  With -O2
-fwrapv, 0.24 seconds.  With -O2, 0.24 seconds.

In all these cases I've averaged several results.  The difference
between -O2 and -O2 -fwrapv is pretty much in the noise here.

Admittedly it's only two small tests, and it's with 4.1.1.  But that's
two more tests than the -fwrapv naysayers have done, on
bread-and-butter applications like coreutils or gzip or Emacs (or GCC
itself, for that matter).

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Andreas Schwab]

Bernd Schmidt <[EMAIL PROTECTED]> writes:

> I must admit I don't know what an integer with padding bits would look
> like.  Can someone check what the C standard has to say about the bit-not
> operator?

All arithmethic operations operate only on the value bits and ignore the
padding bits.

Andreas.

-- 
Andreas Schwab, SuSE Labs, [EMAIL PROTECTED]
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: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Richard Guenther]

On 31 Dec 2006 00:40:39 +0100, Gabriel Dos Reis
<[EMAIL PROTECTED]> wrote:

"Richard Guenther" <[EMAIL PROTECTED]> writes:

| On 31 Dec 2006 00:10:23 +0100, Gabriel Dos Reis
| <[EMAIL PROTECTED]> wrote:
| > "Richard Guenther" <[EMAIL PROTECTED]> writes:
| >
| > | On 30 Dec 2006 23:55:46 +0100, Gabriel Dos Reis
| > | <[EMAIL PROTECTED]> wrote:
| > | >/* Wrapper around int_const_binop.  If the operation overflows and we
| > | >   are not using wrapping arithmetic, then adjust the result to be
| > | >   -INF or +INF depending on CODE, VAL1 and VAL2.  */
| > | >
| > | >static inline tree
| > | >vrp_int_const_binop (enum tree_code code, tree val1, tree val2)
| >
| > [...]
| >
| > | > What would you suggest this function to do, based on your comments?
| > |
| > | The function should be looked at in the context of the few callers - this
| > | is really one of the more ugly and tricky parts of VRP.
| >
| > I've done that; I do not see an obvious way to make everybody happy --
| > except issueing a warning (which I've done).  That is why I was asking
| > since you raised that particular point.  Maybe VRP experts may have
| > opinions...
| >
| > The heavy (and sole) user of vrp_int_const_binop() is
| > extract_range_from_binary_expr().
|
| Yes.  I don't see a way to issue a warning there without 99% false
| positives there.  The only thing we can really do is avoid false
| positives reliably if we have a + b and known ranges for a and b
| so we can see it will _not_ overflow.  But issuing a warning only
| if we are sure it _will_ overflow will likely cause in no warning at
| all - the interesting cases would be those that will have many
| false positives.

for this specific function (vrp_int_const_binop), I'm issuing a
warning inside the else-if  branch that tests for the overflowed
result.  I'm unclear why that is a false positive since the result is
known to overflow.  Could you elaborate?


Well, we use that function to do arithmetic on value ranges like
for example the ranges involving the expression a + b

[50, INT_MAX] + [50, 100]

now you will get a warning as we use vrp_int_const_binop to add
INT_MAX and 100 (to yield INT_MAX in the signed case).  Of
course adding a + b will not always overflow here (it might never
as the INT_MAX bound might be just due to VRP deficiencies),
for example 50 + 50 will not overflow.

So using vrp_int_const_binop to generate the warning will yield
very many false positives (also due to the fact that if we only know
the lower or upper bound we have lots of INT_MAX and INT_MIN
in value ranges).


| Note the interesting places in VRP where it assumes undefined
| signed overflow is in compare_values -- we use the undefinedness
| to fold comparisons.

I considered compare_values(), but I concluded that issueing a warning
from there will yield too many false positive, and probably many
duplicates.  Is that assumption correct?


That is correct - it's basically the same problem as if we were warning
from inside fold.


I have been looking into infer_loop_bounds_from_signedness() called
from infer_loop_bounds_from_undefined().
At some places, nowrap_type_p() is used but this function operates
only on types, so there will be too many false positive there; yet we
will miss warning through that case.


I don't know that area too well, but I think we are already issuing a
warning if we use -funsafe-loop-optimizations, so it might be possible
to do the same if we use signed wrapping undefinedness.  Zdenek
should know more.

Richard.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Richard Guenther]

On 12/31/06, Richard Kenner <[EMAIL PROTECTED]> wrote:

> What would you suggest this function to do, based on your comments?

I'm not familiar enough with VRP to answer at that level, but at a higher
level, what I'd advocate is that the *generator* of information would track
things both ways, assuming wrapping and non-wrapping semantics (of course, if
-fwrapv or -fno-wrapv was specified, it would only do that one).  Then the
*user* of the information would decide which one to use by applying
heuristics based both on the likelihood that the programmer would be relying
on wrapping and the importance from an optimization standpoint of not doing so.


For the VRP case I'd like to rework vrp_int_const_binop to behave like
int_const_binop (that wraps) and return if the operation overflowed.  It's
much more readable to have the handling (or not handling) of overflow
at the callers site extract_range_from_binary_expression.  Using
TREE_OVERFLOW as present is just wasting memory as an extra return
value will also do.

So in the end it's probably time to re-work the core implementation of
int_const_binop to be more like

tree int_const_binop (enum tree_code code, tree type, tree arg1, tree arg2,
int notrunc, bool *overflow);

as it has all the magic to detect overflow already.


So, for example, when making decisions involving loop optimizations, it would
assume that bivs and givs don't overflow.  But it if saw a comparison against
a result that might overflow, it would assume the more conservative choice on
the grounds that it's more likely that the test was intended to do something
than to always be true or false.

Here is where you also have a chance of issuing a warning.  In the former of
these cases, however, I don't think it would make sense to issue one since
it'd almost always be a false positive and in the latter there is nothing to
warn about since the conservative choice is being made. But in some "middle
of the road" cases, assuming undefined overflow and warning might be the most
appropriate: indeed, the ability to issue the warning could be a
justification towards making the less conservative choice.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Zdenek Dvorak]

Hello,

> >I have been looking into infer_loop_bounds_from_signedness() called
> >from infer_loop_bounds_from_undefined().
> >At some places, nowrap_type_p() is used but this function operates
> >only on types, so there will be too many false positive there; yet we
> >will miss warning through that case.
> 
> I don't know that area too well, but I think we are already issuing a
> warning if we use -funsafe-loop-optimizations, so it might be possible
> to do the same if we use signed wrapping undefinedness.

not quite; -funsafe-loop-optimizations is not used in scev analysis
itself, only in # of iterations analysis.  At some extra compile-time
cost, you can check whether we use undefinedness of signed overflow
throughout the scev analysis, but there is no way how to avoid duplicate
warnings, and even making the positioning and contents of the warnings
sensible would be nontrivial.

Zdenek

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Duncan Sands]

> > for this specific function (vrp_int_const_binop), I'm issuing a
> > warning inside the else-if  branch that tests for the overflowed
> > result.  I'm unclear why that is a false positive since the result is
> > known to overflow.  Could you elaborate?
> 
> Well, we use that function to do arithmetic on value ranges like
> for example the ranges involving the expression a + b
> 
>  [50, INT_MAX] + [50, 100]
> 
> now you will get a warning as we use vrp_int_const_binop to add
> INT_MAX and 100 (to yield INT_MAX in the signed case).  Of
> course adding a + b will not always overflow here (it might never
> as the INT_MAX bound might be just due to VRP deficiencies),
> for example 50 + 50 will not overflow.
> 
> So using vrp_int_const_binop to generate the warning will yield
> very many false positives (also due to the fact that if we only know
> the lower or upper bound we have lots of INT_MAX and INT_MIN
> in value ranges).

You could emit a warning if the entire range overflows (i.e. both lower
and upper bound calculations overflow), since that means that the calculation
of a+b necessarily overflows.

Best wishes,

Duncan.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Richard Guenther]

On 12/31/06, Duncan Sands <[EMAIL PROTECTED]> wrote:

> > for this specific function (vrp_int_const_binop), I'm issuing a
> > warning inside the else-if  branch that tests for the overflowed
> > result.  I'm unclear why that is a false positive since the result is
> > known to overflow.  Could you elaborate?
>
> Well, we use that function to do arithmetic on value ranges like
> for example the ranges involving the expression a + b
>
>  [50, INT_MAX] + [50, 100]
>
> now you will get a warning as we use vrp_int_const_binop to add
> INT_MAX and 100 (to yield INT_MAX in the signed case).  Of
> course adding a + b will not always overflow here (it might never
> as the INT_MAX bound might be just due to VRP deficiencies),
> for example 50 + 50 will not overflow.
>
> So using vrp_int_const_binop to generate the warning will yield
> very many false positives (also due to the fact that if we only know
> the lower or upper bound we have lots of INT_MAX and INT_MIN
> in value ranges).

You could emit a warning if the entire range overflows (i.e. both lower
and upper bound calculations overflow), since that means that the calculation
of a+b necessarily overflows.


Yes we can do that, but this won't detect the cases people care about.
In fact I doubt it will trigger on real code at all - you can just make
artificial testcases that excercise this warning.  Like

 if (a > INT_MAX/2 && b > INT_MAX/2)
   return a + b;

I doubt this will be very useful.

Richard.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Vincent Lefevre]

On 2006-12-30 19:29:58 -0500, Robert Dewar wrote:
> Richard Kenner wrote:
> >I can't speak for any other GCC developer, but I personally am
> >quite comfortable viewing any code that assumes wrapping semantics
> >as broken and needing fixing with the exception of these cases of
> >checking for overflow: there simply is no good way in C to do these
> >checks in a portable manner and, as I said, I think we should make
> >sure they continue to work and maybe even document that.
> 
> Now that I don't like, Richard is recommending we write in some
> undefined language where wraps sometimes work and sometimes
> don't. That seems the worst of all worlds to me.

I agree with you. And I doubt that GCC (or any compiler) could
reliably detect code that checks for overflow.

-- 
Vincent Lefèvre <[EMAIL PROTECTED]> - Web: 
100% accessible validated (X)HTML - Blog: 
Work: CR INRIA - computer arithmetic / Arenaire project (LIP, ENS-Lyon)

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Gabriel Dos Reis]

"Richard Guenther" <[EMAIL PROTECTED]> writes:

| On 12/31/06, Richard Kenner <[EMAIL PROTECTED]> wrote:
| > > What would you suggest this function to do, based on your comments?
| >
| > I'm not familiar enough with VRP to answer at that level, but at a higher
| > level, what I'd advocate is that the *generator* of information would track
| > things both ways, assuming wrapping and non-wrapping semantics (of course, 
if
| > -fwrapv or -fno-wrapv was specified, it would only do that one).  Then the
| > *user* of the information would decide which one to use by applying
| > heuristics based both on the likelihood that the programmer would be relying
| > on wrapping and the importance from an optimization standpoint of not doing 
so.
| 
| For the VRP case I'd like to rework vrp_int_const_binop to behave like
| int_const_binop (that wraps) and return if the operation overflowed.  It's
| much more readable to have the handling (or not handling) of overflow
| at the callers site extract_range_from_binary_expression.  Using
| TREE_OVERFLOW as present is just wasting memory as an extra return
| value will also do.
| 
| So in the end it's probably time to re-work the core implementation of
| int_const_binop to be more like
| 
| tree int_const_binop (enum tree_code code, tree type, tree arg1, tree arg2,
| int notrunc, bool *overflow);
| 
| as it has all the magic to detect overflow already.

Can I interpret that as you volunteering to do it, or at least help?

-- Gaby

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Richard Guenther]

On 31 Dec 2006 12:42:57 +0100, Gabriel Dos Reis
<[EMAIL PROTECTED]> wrote:

"Richard Guenther" <[EMAIL PROTECTED]> writes:

| On 12/31/06, Richard Kenner <[EMAIL PROTECTED]> wrote:
| > > What would you suggest this function to do, based on your comments?
| >
| > I'm not familiar enough with VRP to answer at that level, but at a higher
| > level, what I'd advocate is that the *generator* of information would track
| > things both ways, assuming wrapping and non-wrapping semantics (of course, 
if
| > -fwrapv or -fno-wrapv was specified, it would only do that one).  Then the
| > *user* of the information would decide which one to use by applying
| > heuristics based both on the likelihood that the programmer would be relying
| > on wrapping and the importance from an optimization standpoint of not doing 
so.
|
| For the VRP case I'd like to rework vrp_int_const_binop to behave like
| int_const_binop (that wraps) and return if the operation overflowed.  It's
| much more readable to have the handling (or not handling) of overflow
| at the callers site extract_range_from_binary_expression.  Using
| TREE_OVERFLOW as present is just wasting memory as an extra return
| value will also do.
|
| So in the end it's probably time to re-work the core implementation of
| int_const_binop to be more like
|
| tree int_const_binop (enum tree_code code, tree type, tree arg1, tree arg2,
| int notrunc, bool *overflow);
|
| as it has all the magic to detect overflow already.

Can I interpret that as you volunteering to do it, or at least help?


Yes, I have some patches in the queue to clean this up (and add some
more stuff to VRP).

Richard.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Gabriel Dos Reis]

"Richard Guenther" <[EMAIL PROTECTED]> writes:

[...]

| Yes, I have some patches in the queue to clean this up (and add some
| more stuff to VRP).

Great!

-- Gaby

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Vincent Lefevre]

On 2006-12-30 20:07:09 -0500, Robert Dewar wrote:
>  In my view, this comparison optimization should not have been put in
>  without justification given that it clearly does affect the semantics
>  of real code. Indeed if you really see code like
> 
>if (a - 10 < 20)
> 
>  in place of
> 
>if (a < 30)
> 
>  a very likely explanation is that you are deliberately doing something
>  strange with wrap around, and should leave it alone.

I disagree concerning your "very likely explanation". This code
may come from the use of macros, in which case this has nothing
to do with wrap around.

-- 
Vincent Lefèvre <[EMAIL PROTECTED]> - Web: 
100% accessible validated (X)HTML - Blog: 
Work: CR INRIA - computer arithmetic / Arenaire project (LIP, ENS-Lyon)

Re: RFC: SMS problem with emit_copy_of_insn_after copying REG_NOTEs

[Vladimir Yanovsky]

Hi,
Sorry for possibly causing confusion. I had tested the patch on my ICE
testcase and bootstrapped for -enable-languages=C, but didn't run the
full bootstrap. Bootstrapping the latest Andrew's patch on ppc-linux
and testing it on SPU.

Vladimir

On 12/30/06, Jan Hubicka <[EMAIL PROTECTED]> wrote:

Hi,
thanks for testing.  I've bootstrapped/regtested this variant of patch
and comitted it as obvious.

Honza

2006-12-30  Jan Hubicka  <[EMAIL PROTECTED]>
Vladimir Yanovsky <[EMAIL PROTECTED]>

* emit-rt.c (emit_copy_of_insn_after): Fix bug causing exponential
amount of copies of INSN_NOTEs list.

Index: emit-rtl.c
===
--- emit-rtl.c  (revision 120274)
+++ emit-rtl.c  (working copy)
@@ -5297,14 +5297,12 @@ emit_copy_of_insn_after (rtx insn, rtx a
   {
if (GET_CODE (link) == EXPR_LIST)
  REG_NOTES (new)
-   = copy_insn_1 (gen_rtx_EXPR_LIST (REG_NOTE_KIND (link),
- XEXP (link, 0),
- REG_NOTES (new)));
+   = gen_rtx_EXPR_LIST (REG_NOTE_KIND (link),
+ copy_insn_1 (XEXP (link, 0)),  REG_NOTES (new));
else
  REG_NOTES (new)
-   = copy_insn_1 (gen_rtx_INSN_LIST (REG_NOTE_KIND (link),
- XEXP (link, 0),
- REG_NOTES (new)));
+  = gen_rtx_INSN_LIST (REG_NOTE_KIND (link),
+copy_insn_1 (XEXP (link, 0)),  REG_NOTES (new));
   }

   /* Fix the libcall sequences.  */

Re: Link tests not allowed

[Andrew Haley]

Douglas B Rupp writes:
 > Andrew Haley wrote:
 > > Douglas B Rupp writes:
 > >  > DJ Delorie wrote:
 > >  > > Is your target a newlib target?  If so, are you including 
 > > --with-newlib?
 > >  > > 
 > >  > 
 > >  > Thanks, that was the problem.
 > >  > Why isn't --with-newlib the default for newlib targets?
 > > 
 > > AIX is a newlib target?  Really?
 > 
 > Don't really know one way or the other but it fixed the configure 
 > problem. How does one tell a newlib target other than by looking at 
 > configure.in and noconfigdirs?

Newlib targets are targets without their own native libc.  I find it
exceedingly hard to believe that AIX falls into this category.

Andrew.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Robert Dewar]

Vincent Lefevre wrote:

On 2006-12-30 20:07:09 -0500, Robert Dewar wrote:

 In my view, this comparison optimization should not have been put in
 without justification given that it clearly does affect the semantics
 of real code. Indeed if you really see code like

   if (a - 10 < 20)

 in place of

   if (a < 30)

 a very likely explanation is that you are deliberately doing something
 strange with wrap around, and should leave it alone.


I disagree concerning your "very likely explanation". This code
may come from the use of macros, in which case this has nothing
to do with wrap around.


Sorry, my "you" was unclear, I meant you as in a human not you as
in a compiler. Yes, if the code comes from macros, it might well
be in advertent, and of course inadvertent overflow, never mind
potential overflow can be hidden in macros this way.

My point was that if you see this in a source program, it is in
fact a possible candidiate for code that can be destroyed by
the optimization.

And that's the trouble, this is an optimization which does improve
performance, but may destroy existing code, and the very example
you gave to talk about improved performance is also a nice case
of showing why it may destroy performance. In fact the wrap
around range test is a standard idiom for "hand optimization"
of range tests.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Richard Kenner]

> Wait, though: K&Rv2 is post-C89.  

Not completely: it's published in 1988, but the cover says "based on
draft-proposed ANSI C".

> Naturally K&Rv2 documents this, but if you want to know about
> traditional practice the relevant wording should come from K&Rv1,
> not v2.
>
> I don't know what K&Rv1 says on the subject, 

I think it's silent on the subject, but that's really old memory on my part.
Remember that this was in an era before most people were used to thinking
seriously about language semantics and thing that we now call "implementation
defined" and "undefined" weren't thought about.  Certainly within that
community, practical issues were more important than any concept of
standardization.

> but from other evidence it's clear that common traditional practice assumes
> wrapv semantics.

"Common traditional C" was actually yet another language that was even more
ill-defined because it included such things as structure assignment that
weren't in K&Rv1.

> I just now looked at the implementation of atoi() in
> 7th Edition Unix, which is about as traditional as it gets.  It
> ends as follows:
> 
>   while(*p >= '0' && *p <= '9')
>   n = n*10 + *p++ - '0';
>   return(f? -n: n);
> 
> where p is char* and n is int.  This relies on wrapv semantics
> when atoi returns INT_MIN.  I'm sure many similar examples can be
> found in the V7 sources.

Maybe, but that one is a weak example because it's *much* more likely that
the author of that code didn't even *think* about the INT_MIN case rather
than made a conscious decision to depend on wrapping semantics in that case.
In that era, thinking about boundary conditions was also rare.  So, for all
we know, this might have been considered a bug even by the original author.

The counter-argument your arguments about common practice at the time is that
the *purpose* of the original ANSI C standard was to standardize common
practice in C precisely because people were already writing in a language
that went beyond K&R so there was need to precisely define that language.

I just found the Rationale document for ANSI C (C89).  In the section on
Additive Operators, it says "Overflow was considered not to break old code
since it was undefined by K&R".  The discussion of "elimination of the
regrouping rule" talks about "implementations with twos-complement arithmetic
and silent wraparound on overflow" and then in the next sentence "any
implementation".  This seems to imply that both types of implementations
existed in the mid-80's.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Richard Kenner]

> > > I suppose there is
> > > 
> > >   *hv = (HOST_WIDE_INT) -(unsigned HOST_WIDE_INT) h1;
> > > 
> > > to make it safe.
> > 
> > Can't that conversion overflow?
> 
> Not on a two's complement machine, 

Then I'm confused about C's arithmetic rules.  Suppose h1 is 1. It's cast
to unsigned, so stays as 1.  Now we do unary minus in unsigned.  That's ~0
because it's done mod 2**32, but interpreted as a POSITIVE number.  Now,
that positive number overflows when converted to signed (the intent is for
that overflow make it negative).  Am I missing something (quite likely!)?

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Richard Kenner]

> On the other hand, C does not have a way to tell the compiler:
> 
> "this is my loop variable, it must not be modified inside the loop"
> 
> neither you can say:
> 
> "this is the upper bound of the loop, it must not be modified"
> 
> either.

No, but the compiler can almost always trivially determine that nothing in
the loop can modify the variable, so I'm not sure I understand your point.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Robert Dewar]

Richard Kenner wrote:
Wait, though: K&Rv2 is post-C89.  


Not completely: it's published in 1988, but the cover says "based on
draft-proposed ANSI C".


Naturally K&Rv2 documents this, but if you want to know about
traditional practice the relevant wording should come from K&Rv1,
not v2.

I don't know what K&Rv1 says on the subject, 


I think it's silent on the subject, but that's really old memory on my part.
Remember that this was in an era before most people were used to thinking
seriously about language semantics and thing that we now call "implementation
defined" and "undefined" weren't thought about.


That's unfair to K&Rv1 which is in many places quite careful about the
concept of undefined/implementation-defined stuff, e.g. for pointer
conversions.

And the idea that people were not used to thinking seriously about
language semantics is very odd, this book was published in 1978,
ten years after the algol-68 report, a year after the fortran
77 standard, long after the COBOL 74 standard, and a year before the 
PL/1 standard. It's not that old!

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Richard Kenner]

> |  though I vaguely
> | recall some complaints that you couldn't build v7 Unix if your compiler
> | generated integer overflow traps.
> 
> this matches what I've told recently by some people who worked at bell
> labs, in the unix room. 

I have recollections of that being the case as well.  Moreover, I
think it's also clearly established that PCC always implemented wrapping
semantics.  What's less clear (at least to me) is what other existing
practice that the ANSI C committee took into account was at the time.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Richard Kenner]

> The burden of proof ought to be on the guys proposing -O2
> optimizations that break longstanding code, not on the skeptics.

There's also a burden of proof that proposed optimizations will actually
"break longstanding code".  So far, all of the examples of code shown
that assumes wrapv semantics are such that it's nearly impossible to see
any useful optimization that would break it!

Let's look at the example from GCC's fold-const.c:neg_double:

  *hv = - h1;
  return (*hv & h1) < 0;

What could we do that could break that?  We could conceivably argue after
seeing the first statement that either the sign bits of *hv and -h1 are
now different or an overflow occured, then argue that since an overflow
can't occur, they must be different. Hence the AND of the sign bits in
the second statement must always be zero and hence the RETURN always
returns zero.

I don't think GCC does that now, though it's certainly something it COULD
do.  But that falls within what's been discussed earlier in this thread,
which is not using an assumption about overflow to deduce that a test is
always false or true because that might be testing for overflow.

In the atoi example, there's nothing to optimize, so that certainly wouldn't
be affected.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Richard Kenner]

> You could emit a warning if the entire range overflows (i.e. both lower
> and upper bound calculations overflow), since that means that the calculation
> of a+b necessarily overflows.

True, but the interesting question is not whether a computation NECESSARILY
overflows, but whether it MIGHT overflow in some case that's actually
executed by the program.

The case of a computation necessarily overflowing is quite rare (and is
almost always a bug in the code anyway since that would be a bizarre way to
code something).  The problem is that most computations that look like the
MIGHT overflow don't.  After all, if I just write:

int sum (int a, int b) { return a + b;}

There's absolutely no way a compiler could EVER tell if that's relying on
wrapping semantics and issuing a warning that a+b might overflow would be
completely useless.  Luckily, that's not a question we need to answer.  The
question we care about is if we're making some TRANSFORMATION to the
program that would change the behavior of the program if it required
wrapping semantics. That can't be determined when we GENERATE a range, only
when we USE that range for something.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Robert Dewar]

Richard Kenner wrote:

The burden of proof ought to be on the guys proposing -O2
optimizations that break longstanding code, not on the skeptics.


There's also a burden of proof that proposed optimizations will actually
"break longstanding code".  So far, all of the examples of code shown
that assumes wrapv semantics are such that it's nearly impossible to see
any useful optimization that would break it!


That's far too ad hoc to me. We can't have a rule for writing
gcc that says

  Be careful about overflow, since it is undefined, and the gcc
  optimizer takes advantage of this assumption, but it's OK to
  assume wrap around semantics in code where it is "nearly
  impossible to see any useful optimization that would break it".

I would think that it would be a common consensus position that
whatever the outcome of this debate, the result must be that
the language we are supposed to write in is well defined.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Michael Veksler]

Richard Kenner wrote:

On the other hand, C does not have a way to tell the compiler:

"this is my loop variable, it must not be modified inside the loop"

neither you can say:

"this is the upper bound of the loop, it must not be modified"

either.



No, but the compiler can almost always trivially determine that nothing in
the loop can modify the variable, so I'm not sure I understand your point.

  

My point in the quoted section is that:

  1. A programmer can accidentally modify the loop variable, or bound.
 It is more
 difficult for a programmer to catch such bugs, if the language
 does not help.
 Having a true "for" syntax will help to catch such bug.
  2. If there were a real "for" construct, there would be no question
 of termination
 in that common case. There would be no need to do the "overflow is
 undefined"
 hack.
 Among other things, complex termination conditions make it
 impossible  to
 figure out if the loop terminates. If a true "for" would have been
 defined by C,
 then the termination condition would be calculated and known in
 advance:

   FOR i:=0 TO foo()+1
   BEGIN
   
   END

   We don't care if foo()+1 wraps to MIN_INT. It would be undefined to
   have the
   upper bound smaller than the lower bound. Wrapping semantics can be
   used
   everywhere.
   Anyway, in most cases one knows the upper limit of the loop upfront.


Anyway, the main point of the complete mail was to propose  semantics 
that is

strong enough for the "speed is all" camp, and predictable enough for the
"real world code assumes wrapping" camp.
--

Michael Veksler
http:///tx.technion.ac.il/~mveksler

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Robert Dewar]

Richard Kenner wrote:

The burden of proof ought to be on the guys proposing -O2
optimizations that break longstanding code, not on the skeptics.


There's also a burden of proof that proposed optimizations will actually
"break longstanding code".  So far, all of the examples of code shown
that assumes wrapv semantics are such that it's nearly impossible to see
any useful optimization that would break it!


Also, there are bug reports filed, so we certainly DO have examples
of code breaking, and quite a few reports have discussed the need
to enable -fwrapv for specific code bases.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Richard Kenner]

> And I doubt that GCC (or any compiler) could reliably detect code
> that checks for overflow.

It doesn't need to "detect" all such code: all it needs to do is
ensure that it doesn't BREAK such code.  And that's a far easier
condition: you just have to avoid folding a condition into TRUE or FALSE
based on assumptions about overflow.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Richard Kenner]

> In fact the wrap around range test is a standard idiom for "hand
> optimization" of range tests.

It's also one that GCC uses internally, but you do it in *unsigned* to
avoid the undefined overflow.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Vincent Lefevre]

On 2006-12-31 08:06:56 -0500, Robert Dewar wrote:
> Vincent Lefevre wrote:
> >On 2006-12-30 20:07:09 -0500, Robert Dewar wrote:
> >> In my view, this comparison optimization should not have been put in
> >> without justification given that it clearly does affect the semantics
> >> of real code. Indeed if you really see code like
> >>
> >>   if (a - 10 < 20)
> >>
> >> in place of
> >>
> >>   if (a < 30)
> >>
> >> a very likely explanation is that you are deliberately doing something
> >> strange with wrap around, and should leave it alone.
> >
> >I disagree concerning your "very likely explanation". This code
> >may come from the use of macros, in which case this has nothing
> >to do with wrap around.
> 
> Sorry, my "you" was unclear, I meant you as in a human not you as
> in a compiler. Yes, if the code comes from macros, it might well
> be in advertent, and of course inadvertent overflow, never mind
> potential overflow can be hidden in macros this way.

This is still not clear. If I write a - 10 < 20 (where a is signed),
this implicitly assumes that a - 10 cannot overflow; in particular,
when writing macros, I take care of that. So, from this point of
view, the optimization is safe as long as -ftrav is not used.

> My point was that if you see this in a source program, it is in
> fact a possible candidiate for code that can be destroyed by
> the optimization.

Well, only for non-portable code (i.e. code based on wrap). I also
suppose that this kind of code is used only to check for overflows.

> And that's the trouble, this is an optimization which does improve
> performance, but may destroy existing code, and the very example
> you gave to talk about improved performance is also a nice case
> of showing why it may destroy performance. In fact the wrap
> around range test is a standard idiom for "hand optimization"
> of range tests.

Yes, and the lack of optimization would be even worse.

-- 
Vincent Lefèvre <[EMAIL PROTECTED]> - Web: 
100% accessible validated (X)HTML - Blog: 
Work: CR INRIA - computer arithmetic / Arenaire project (LIP, ENS-Lyon)

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Richard Kenner]

> And the idea that people were not used to thinking seriously about
> language semantics is very odd, this book was published in 1978,
> ten years after the algol-68 report, a year after the fortran
> 77 standard, long after the COBOL 74 standard, and a year before the 
> PL/1 standard. It's not that old!

I knew you were going to say something like that, which is why I edited
my message to say "most people": yes, there were certainly groups (I 
specifically had Algol 68 in mind) who were thinking of programming
languages in very formal terms, but those represented an even smaller
minority of the community than now and certainly the Unix/C community's
view at that point was much more pragmatic than formal: that's the point
that a lot of people in this thread are making.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Vincent Lefevre]

On 2006-12-31 08:25:23 -0500, Richard Kenner wrote:
> > > > I suppose there is
> > > > 
> > > >   *hv = (HOST_WIDE_INT) -(unsigned HOST_WIDE_INT) h1;
> > > > 
> > > > to make it safe.
> > > 
> > > Can't that conversion overflow?
> > 
> > Not on a two's complement machine, 
> 
> Then I'm confused about C's arithmetic rules. Suppose h1 is 1. It's
> cast to unsigned, so stays as 1. Now we do unary minus in unsigned.
> That's ~0 because it's done mod 2**32, but interpreted as a POSITIVE
> number. Now, that positive number overflows when converted to signed
> (the intent is for that overflow make it negative). Am I missing
> something (quite likely!)?

No, this is not portable. On the same kind of code, even the wrap
may hide a bug, e.g. when one has:

  *hv = -(unsigned HOST_WIDE_INT) h1;

where *hv is signed, but not the same type as the original one.
For instance, such a code will work on a 32-bit machine, but not
necessarily on a 64-bit machine. Now, will GCC do anything to
make such code work on such machines? I doubt that.

-- 
Vincent Lefèvre <[EMAIL PROTECTED]> - Web: 
100% accessible validated (X)HTML - Blog: 
Work: CR INRIA - computer arithmetic / Arenaire project (LIP, ENS-Lyon)

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Robert Dewar]

Vincent Lefevre wrote:


My point was that if you see this in a source program, it is in
fact a possible candidiate for code that can be destroyed by
the optimization.


Well, only for non-portable code (i.e. code based on wrap). I also
suppose that this kind of code is used only to check for overflows.


No, you suppose wrong, this is an idiom for a normal range test. If
you have

   if (a > x && a < y)

you can often replace this by a single test with a wrapping subtraction.
As Richard said, you should do this unsigned, but I can easily imagine
those who are accustomed to signed arithmetic wrapping not bothering



And that's the trouble, this is an optimization which does improve
performance, but may destroy existing code, and the very example
you gave to talk about improved performance is also a nice case
of showing why it may destroy performance. In fact the wrap
around range test is a standard idiom for "hand optimization"
of range tests.


Yes, and the lack of optimization would be even worse.


Well that's a claim without substantiation. No one has any data that
I know of that shows that the optimization of copmarisons like this
is important. Sure you can concoct an example, but that says nothing
about real world code.

This is a long thread, but it is on an important subject. I find
that compiler writers (and hardware manufacturers too) tend to
be far too focused on performance, when what is important to the
majority of users is reliability.

Yes, there may be some people who look at gcc and try their code
and are concerned with performance and come away disappointed that
gcc is x% slower.

But just as likely, perhaps more likely, is people with a big body
of code who try it out on gcc and are disappointed to find out that
it doesn't work. Sure, it's their fault in a language lawyer sense,
but they will still vote with their actions and avoid using a
compiler that from their point of view does not work.

Getting wrong results fast is of dubious value, where by wrong
I mean wrong from the users point of view.

I mentioned hardware manufacturers, and a similar phenomenon
happens with fudging IEEE fpt semantics (e.g. the R10K not
handling denormals right) to get a bit more performance at
the expense of correctness. After all, gcc could enable
fast math by default, and still be a completely conforming
C compiler, but we recognize that as a bad idea. Not so
clear that this is such a different case.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Robert Dewar]

Richard Kenner wrote:

And the idea that people were not used to thinking seriously about
language semantics is very odd, this book was published in 1978,
ten years after the algol-68 report, a year after the fortran
77 standard, long after the COBOL 74 standard, and a year before the 
PL/1 standard. It's not that old!


I knew you were going to say something like that, which is why I edited
my message to say "most people": yes, there were certainly groups (I 
specifically had Algol 68 in mind) who were thinking of programming

languages in very formal terms, but those represented an even smaller
minority of the community than now and certainly the Unix/C community's
view at that point was much more pragmatic than formal: that's the point
that a lot of people in this thread are making.


It was a MUCH bigger set than you think, remember that Algol-60 was
widely used in Europe. ABsolutely every Algol-60 programmer read the
A60 report, there is not one book on A60 that did not reprint the
report as part of the book.

Indeed it is the case that the eventual dominance of Fortran and
C set things back, but not back as much as you think in terms of
language definition.

In fact K&R is much stronger than you think in terms of providing
a precise definition of the language. Too bad people did not read it.

As I said earlier in this thread, people seem to think that the
standards committee invented something new here in making overflow
undefined, but I don't think that's the case. I personally would
have thought it more judicious to make it implementation defined,
since I don't like undefined semantics anywhere in programming
languages unless a hugely strong case can be made that providing
or requiring a definition damages code (e.g. uninitialized variables
have always been generally agreed to be in that class for C/Ada/Fortran
level languages, but even there Ada 95 greatly reduced the damage
that uninitialized variables can do, and introduced the notion of
bounded error to replace many undefined (called erroneous) cases
in Ada).

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Richard Kenner]

> I would think that it would be a common consensus position that whatever
> the outcome of this debate, the result must be that the language we are
> supposed to write in is well defined.

Right.  But "supposed to write in" is not the same as "what we do to avoid
breaking legacy code"!

I see it as similar to the old CS engineering principle of "be conservative
in what you generate but liberal in what you accept".  We certainly should
encourage people to write correct code (and change GCC to only use correct
code), but that doesn't mean it's not worth spending some effort to avoid
penalizing old code that doesn't follow those rules.

I am being very careful to explicitly not propose that we document exactly
what exceptions we make, but we just use engineering judgement to make them
in such a way to have a reasonable compromise between code quality and not
breaking old code.  If we DO document exceptions then we are indeed encouraging
people to write in some ad-hoc language and I agree with you that doing so
is a very bad idea.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Vincent Lefevre]

On 2006-12-31 09:03:17 -0500, Richard Kenner wrote:
> > And I doubt that GCC (or any compiler) could reliably detect code
> > that checks for overflow.
> 
> It doesn't need to "detect" all such code: all it needs to do is
> ensure that it doesn't BREAK such code. And that's a far easier
> condition: you just have to avoid folding a condition into TRUE or
> FALSE based on assumptions about overflow.

Well, that's not equivalent. For instance, MPFR has many conditions
that evaluate to TRUE or FALSE on some/many implementations (mainly
because the type sizes depend on the implementation), even without
the assumption that an overflow cannot occur.

-- 
Vincent Lefèvre <[EMAIL PROTECTED]> - Web: 
100% accessible validated (X)HTML - Blog: 
Work: CR INRIA - computer arithmetic / Arenaire project (LIP, ENS-Lyon)

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Daniel Berlin]

On 12/31/06, Paul Eggert <[EMAIL PROTECTED]> wrote:

"Steven Bosscher" <[EMAIL PROTECTED]> writes:

> On 12/31/06, Paul Eggert <[EMAIL PROTECTED]> wrote:
>> Also, as I understand it this change shouldn't affect gcc's
>> SPEC benchmark scores, since they're typically done with -O3
>> or better.
>
> It's not all about benchmark scores.

But so far, benchmark scores are the only scores given by the people
who oppose having -O2 imply -fwrapv.  If the benchmarks use -O3 they
wouldn't be affected by such a change -- and if so, we have zero hard
evidence of any real harm being caused by having -O2 imply -fwrapv.

> I think most users compile at -O2

Yes, which is why there's so much argument about what -O2 should do

> You say you doubt it affects performance.  Based on what?  Facts
> please, not guesses and hand-waiving...

The burden of proof ought to be on the guys proposing -O2
optimizations that break longstanding code, not on the skeptics.


The burden ought to be (and IMHO is) on those who propose we change
optimizer behavior in order to support something non-standard.

Why do you believe otherwise?


That being said, I just compiled GNU coreutils CVS on a Debian stable
x86 (2.4 GHz Pentium 4) using GCC 4.1.1.  With -O0, "sha512sum" on the
coreutils tar.gz file took 0.94 user CPU seconds (measured by "time
src/sha512sum coreutils-6.7-dirty.tar.gz").  With -O2 -fwrapv, 0.87
seconds.  With plain -O2, 0.86 seconds.

I also tried gzip 1.3.10, compressing its own tar file with a -9
compression option.  With -O0, 0.30 user CPU seconds.  With -O2
-fwrapv, 0.24 seconds.  With -O2, 0.24 seconds.

In all these cases I've averaged several results.  The difference
between -O2 and -O2 -fwrapv is pretty much in the noise here.

Admittedly it's only two small tests, and it's with 4.1.1.  But that's
two more tests than the -fwrapv naysayers have done, on
bread-and-butter applications like coreutils or gzip or Emacs (or GCC
itself, for that matter).


These are not performance needing applications.
I'll happily grant you that  adding -fwrapv will make no difference at
all on any application that does not demand performance in integer or
floating point calculations.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Richard Guenther]

On 12/31/06, Daniel Berlin <[EMAIL PROTECTED]> wrote:

On 12/31/06, Paul Eggert <[EMAIL PROTECTED]> wrote:
> "Steven Bosscher" <[EMAIL PROTECTED]> writes:
>
> > On 12/31/06, Paul Eggert <[EMAIL PROTECTED]> wrote:
> >> Also, as I understand it this change shouldn't affect gcc's
> >> SPEC benchmark scores, since they're typically done with -O3
> >> or better.
> >
> > It's not all about benchmark scores.
>
> But so far, benchmark scores are the only scores given by the people
> who oppose having -O2 imply -fwrapv.  If the benchmarks use -O3 they
> wouldn't be affected by such a change -- and if so, we have zero hard
> evidence of any real harm being caused by having -O2 imply -fwrapv.
>
> > I think most users compile at -O2
>
> Yes, which is why there's so much argument about what -O2 should do
>
> > You say you doubt it affects performance.  Based on what?  Facts
> > please, not guesses and hand-waiving...
>
> The burden of proof ought to be on the guys proposing -O2
> optimizations that break longstanding code, not on the skeptics.

The burden ought to be (and IMHO is) on those who propose we change
optimizer behavior in order to support something non-standard.

Why do you believe otherwise?
>
> That being said, I just compiled GNU coreutils CVS on a Debian stable
> x86 (2.4 GHz Pentium 4) using GCC 4.1.1.  With -O0, "sha512sum" on the
> coreutils tar.gz file took 0.94 user CPU seconds (measured by "time
> src/sha512sum coreutils-6.7-dirty.tar.gz").  With -O2 -fwrapv, 0.87
> seconds.  With plain -O2, 0.86 seconds.
>
> I also tried gzip 1.3.10, compressing its own tar file with a -9
> compression option.  With -O0, 0.30 user CPU seconds.  With -O2
> -fwrapv, 0.24 seconds.  With -O2, 0.24 seconds.
>
> In all these cases I've averaged several results.  The difference
> between -O2 and -O2 -fwrapv is pretty much in the noise here.
>
> Admittedly it's only two small tests, and it's with 4.1.1.  But that's
> two more tests than the -fwrapv naysayers have done, on
> bread-and-butter applications like coreutils or gzip or Emacs (or GCC
> itself, for that matter).

These are not performance needing applications.
I'll happily grant you that  adding -fwrapv will make no difference at
all on any application that does not demand performance in integer or
floating point calculations.


I added -fwrapv to the Dec30 run of SPEC at
http://www.suse.de/~gcctest/SPEC/CFP/sb-vangelis-head-64/recent.html
and
http://www.suse.de/~gcctest/SPEC/CINT/sb-vangelis-head-64/recent.html

Richard.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Vincent Lefevre]

On 2006-12-31 09:08:21 -0500, Richard Kenner wrote:
> > In fact the wrap around range test is a standard idiom for "hand
> > optimization" of range tests.
> 
> It's also one that GCC uses internally, but you do it in *unsigned*
> to avoid the undefined overflow.

If done in unsigned, this won't lead to any optimization, as unsigned
arithmetic doesn't have overflows. So, if you write "a - 10" where a
is unsigned, the compiler can't assume anything, whereas is a is
signed, the compiler can assume that a >= INT_MIN + 10, reducing
the range for a, and possibly allowing some optimizations.

-- 
Vincent Lefèvre <[EMAIL PROTECTED]> - Web: 
100% accessible validated (X)HTML - Blog: 
Work: CR INRIA - computer arithmetic / Arenaire project (LIP, ENS-Lyon)

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Robert Dewar]

Vincent Lefevre wrote:


If done in unsigned, this won't lead to any optimization, as unsigned
arithmetic doesn't have overflows. So, if you write "a - 10" where a
is unsigned, the compiler can't assume anything, whereas is a is
signed, the compiler can assume that a >= INT_MIN + 10, reducing
the range for a, and possibly allowing some optimizations.


Vincent, you missed the point, if we do this in unsigned, it works
fine, and we don't WANT any optimization to intefere. That's what
Richard was saying, if you want to do this kind of hand optimization
of range checking, you do it in unsigned, and everything is fine.

If you do it in signed expecting wrapping, then the optimization
destroys your code. Yes, it is technically your fault, but this
business of telling users

"sorry, your code is non-standard, gcc won't handle it as you
expect, go fix your code"

is not very convincing to users who find other compilers that
handle their code just fine.

I remember that in Realia COBOL days, it was not just a matter
of dealing with undefined situations, there were actually a
couple of cases where the IBM compiler had semantics that were
definitely non-conforming to the COBOL standard. Users depended
on these bugs, so we carefully copied them in Realia COBOL.

Sure, we could have explained to users that their code was
junk, and the IBM compiler was wrong, but that would not have
convinced them to move to using Realia COBOL!

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Vincent Lefevre]

On 2006-12-31 09:22:22 -0500, Robert Dewar wrote:
> Vincent Lefevre wrote:
> >>My point was that if you see this in a source program, it is in
> >>fact a possible candidiate for code that can be destroyed by
> >>the optimization.
> >
> >Well, only for non-portable code (i.e. code based on wrap). I also
> >suppose that this kind of code is used only to check for overflows.
> 
> No, you suppose wrong, this is an idiom for a normal range test. If
> you have
> 
>if (a > x && a < y)
> 
> you can often replace this by a single test with a wrapping subtraction.
> As Richard said, you should do this unsigned, but I can easily imagine
> those who are accustomed to signed arithmetic wrapping not bothering

Doing that in unsigned arithmetic is much more readable anyway. So,
I doubt that programmers would do that in signed arithmetic. Or do
you have any real example?

> >>And that's the trouble, this is an optimization which does improve
> >>performance, but may destroy existing code, and the very example
> >>you gave to talk about improved performance is also a nice case
> >>of showing why it may destroy performance. In fact the wrap
> >>around range test is a standard idiom for "hand optimization"
> >>of range tests.
> >
> >Yes, and the lack of optimization would be even worse.
> 
> Well that's a claim without substantiation. No one has any data that
> I know of that shows that the optimization of copmarisons like this
> is important. Sure you can concoct an example, but that says nothing
> about real world code.

I meant that the lack of optimization would be even worse in the above
case only. The point is that one can write "a - 10" in order to say
that a >= INT_MIN + 10 and allow some optimizations. But if, instead
of doing an optimization, the compiler really generates a - 10 because
of wrap, then in this case, writing "a - 10" is worse than writing
code without trying to reduce the range, i.e. instead of having a
faster code, one has a slower code.

I'm not saying that this kind of code is common, but it is quite bad
to penalize a code based on the standard (that tries to give
information to the compiler in order to run faster), just because of
existing non-conforming code.

> This is a long thread, but it is on an important subject. I find
> that compiler writers (and hardware manufacturers too) tend to
> be far too focused on performance, when what is important to the
> majority of users is reliability.

IMHO, GCC should first focus on reliability of code based on the
standard. If reliability is important, why not assuming -ffloat-store
by default when need be? Without it on some platforms, it cannot be a
conforming compiler (even with it, it isn't, but that's much better
with it).

-- 
Vincent Lefèvre <[EMAIL PROTECTED]> - Web: 
100% accessible validated (X)HTML - Blog: 
Work: CR INRIA - computer arithmetic / Arenaire project (LIP, ENS-Lyon)

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Richard Kenner]

> If done in unsigned, this won't lead to any optimization, as unsigned
> arithmetic doesn't have overflows. So, if you write "a - 10" where a
> is unsigned, the compiler can't assume anything, whereas is a is
> signed, the compiler can assume that a >= INT_MIN + 10, reducing
> the range for a, and possibly allowing some optimizations.

I don't follow.  The purpose of this hand-optimization (whch is also done
by GCC) is to replace two comparisons with one subtraction and one
comparison, which is faster on most machines.  It's not CORRECT to do this
transformation in signed unless you know there won't be overflow. 

In general, for modern compilers it's best not to do this transformation
AT ALL and let the compiler figure out the best way to do the range tst.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Vincent Lefevre]

On 2006-12-31 09:27:21 -0500, Robert Dewar wrote:
> As I said earlier in this thread, people seem to think that the
> standards committee invented something new here in making overflow
> undefined, but I don't think that's the case. I personally would
> have thought it more judicious to make it implementation defined,
> since I don't like undefined semantics anywhere in programming
> languages unless a hugely strong case can be made that providing
> or requiring a definition damages code (e.g. uninitialized variables
> have always been generally agreed to be in that class for C/Ada/Fortran
> level languages, but even there Ada 95 greatly reduced the damage
> that uninitialized variables can do, and introduced the notion of
> bounded error to replace many undefined (called erroneous) cases
> in Ada).

The compiler could have an optional mode where everything is defined.
So, this is more a problem with the compiler than with the language.
But this won't prevent from having bugs, possibly difficult to detect,
in particular if behavior is implementation-defined instead of being
fixed for every implementation.

-- 
Vincent Lefèvre <[EMAIL PROTECTED]> - Web: 
100% accessible validated (X)HTML - Blog: 
Work: CR INRIA - computer arithmetic / Arenaire project (LIP, ENS-Lyon)

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Richard Kenner]

> Doing that in unsigned arithmetic is much more readable anyway. 

If you're concerned about readability, you leave it as the two tests and
let the compiler worry about the optimal way to implement it.

> So I doubt that programmers would do that in signed arithmetic. 

I kind of doubt that as well, but for a different reason: this is a trick
that isn't that widely known and I'd guess (again with no data) that the
people who know about it know to do it correctly.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Richard Kenner]

> As I said earlier in this thread, people seem to think that the
> standards committee invented something new here in making overflow
> undefined, but I don't think that's the case. 

I agree with that too.

However, it is also the case that between K&Rv1 and the ANSI C standard,
there was a language that was a superset of K&Rv1 C and that could be called
"Unix C" or "Bell Labs C" where people sort of "understood" what it was, but
it was never formally specified anywhere.  Most people would view PCC as an
operational specification of that language and hence would say that wrapping
semantics was part it.  That's where a lot of these problems started.

> I personally would have thought it more judicious to make it
> implementation defined, since I don't like undefined semantics
> anywhere in programming languages unless a hugely strong case can be
> made that providing or requiring a definition damages code

Was the distinction between "undefined" and "implementation defined" well
understood in that era?  K&Rv2 says that "the behavior is not defined by the
language" and then goes on to talk about what "most implementations" do. To
me, saying that the "behavior" rather than the "result" is undefined sounds
more like what today is called "implementation defined" than "undefined".
But the standard indeed didn't copy that language.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Richard Kenner]

> Well, that's not equivalent. For instance, MPFR has many conditions
> that evaluate to TRUE or FALSE on some/many implementations (mainly
> because the type sizes depend on the implementation), even without
> the assumption that an overflow cannot occur.

Can you give an example of such a condition and show how an optimization that
assumed overflows were undefined could break that code?

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Vincent Lefevre]

On 2006-12-31 10:07:44 -0500, Robert Dewar wrote:
> Vincent Lefevre wrote:
> >If done in unsigned, this won't lead to any optimization, as unsigned
> >arithmetic doesn't have overflows. So, if you write "a - 10" where a
> >is unsigned, the compiler can't assume anything, whereas is a is
> >signed, the compiler can assume that a >= INT_MIN + 10, reducing
> >the range for a, and possibly allowing some optimizations.
> 
> Vincent, you missed the point, if we do this in unsigned, it works
> fine, and we don't WANT any optimization to intefere. That's what
> Richard was saying, if you want to do this kind of hand optimization
> of range checking, you do it in unsigned, and everything is fine.
> 
> If you do it in signed expecting wrapping, then the optimization
> destroys your code. Yes, it is technically your fault, but this
> business of telling users

No, this isn't what I meant. The C standard doesn't assume wrapping,
so I don't either. If the compiler doesn't either, then it can do
some optimizations. Let's take a very simple example:

int not (int k)
{
  k + INT_MIN;
  (k - 1) + INT_MAX;
  /* Now the compiler can assume that k is either 0 or 1. Because
 otherwise there is an overflow and any result is correct. */
  return !k;
}

Is that clear? Note that if k were unsigned, the compiler could not
optimized.

Of course, unless traps on overflows are enabled, the compiler won't
generate any code on the first two lines. But if combined with other
operations (with more complex code) and if the compiler assumes wrap
on overflow, then the compiler will not be able to optimize the k!.

Note: of course, this depends on the processor, one could also write
k & 1 here, and so on, but this is not my point here.

-- 
Vincent Lefèvre <[EMAIL PROTECTED]> - Web: 
100% accessible validated (X)HTML - Blog: 
Work: CR INRIA - computer arithmetic / Arenaire project (LIP, ENS-Lyon)

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Gerald Pfeifer]

On Sun, 31 Dec 2006, Robert Dewar wrote:
> If you do it in signed expecting wrapping, then the optimization
> destroys your code. Yes, it is technically your fault, but this
> business of telling users
> 
> "sorry, your code is non-standard, gcc won't handle it as you
> expect, go fix your code"

My understanding of previous messages in this thread was that other
compilers (like ICC) do enable the optimization we are talking about
here by default.

Did I misunderstand?

Gerald

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Vincent Lefevre]

On 2006-12-31 10:08:32 -0500, Richard Kenner wrote:
> > Well, that's not equivalent. For instance, MPFR has many conditions
> > that evaluate to TRUE or FALSE on some/many implementations (mainly
> > because the type sizes depend on the implementation), even without
> > the assumption that an overflow cannot occur.
> 
> Can you give an example of such a condition and show how an
> optimization that assumed overflows were undefined could break that
> code?

This won't break the code. But I'm saying that if the compiler assumes
wrapping, even in some particular cases (e.g. code that *looks like*
"overflow check"), it could miss some potential optimizations. That
is, it is not possible to avoid breaking overflow checks *and*
optimizing everything else.

-- 
Vincent Lefèvre <[EMAIL PROTECTED]> - Web: 
100% accessible validated (X)HTML - Blog: 
Work: CR INRIA - computer arithmetic / Arenaire project (LIP, ENS-Lyon)

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Robert Dewar]

Vincent Lefevre wrote:


No, this isn't what I meant. The C standard doesn't assume wrapping,
so I don't either. If the compiler doesn't either, then it can do
some optimizations. Let's take a very simple example:


We perfectly understand that if the compiler does not assume
wrapping, but instead assumes that integer overflow is undefined,
then some possible optimization opportunities open up (how could
anyone reading this thread not understand this, far better examples
have been given than the one you give here). No one is contesting
that, or failing to understand that this is of course true. So we
don't need another simple-minded tutorial on that issue!

The issues are

a) are these optimizations valuable? (and if so, in all cases,
   or only in practice for loop invariants?).

b) are these optimiztions judicious? they are allowed by the
   standard, but then a lot of things are allowed by the
   standard that we do not take advantage of (such as fast
   math), but do they cause too many surprises given actual
   C coding practices.

And it is on these two points that people (rather strenuously)
disagree.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Vincent Lefevre]

On 2006-12-31 10:19:59 -0500, Richard Kenner wrote:
> > If done in unsigned, this won't lead to any optimization, as unsigned
> > arithmetic doesn't have overflows. So, if you write "a - 10" where a
> > is unsigned, the compiler can't assume anything, whereas is a is
> > signed, the compiler can assume that a >= INT_MIN + 10, reducing
> > the range for a, and possibly allowing some optimizations.
> 
> I don't follow.  The purpose of this hand-optimization (whch is also done
> by GCC) is to replace two comparisons with one subtraction and one
> comparison, which is faster on most machines.  It's not CORRECT to do this
> transformation in signed unless you know there won't be overflow. 

OK, I was assuming that the code were correct in signed arithmetic
(meaning no overflow) and that the "a - 10" were done for another
purpose (see my example in another message).

-- 
Vincent Lefèvre <[EMAIL PROTECTED]> - Web: 
100% accessible validated (X)HTML - Blog: 
Work: CR INRIA - computer arithmetic / Arenaire project (LIP, ENS-Lyon)

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Robert Dewar]

Gerald Pfeifer wrote:

On Sun, 31 Dec 2006, Robert Dewar wrote:

If you do it in signed expecting wrapping, then the optimization
destroys your code. Yes, it is technically your fault, but this
business of telling users

"sorry, your code is non-standard, gcc won't handle it as you
expect, go fix your code"


My understanding of previous messages in this thread was that other
compilers (like ICC) do enable the optimization we are talking about
here by default.


Well that's not such a clear criterion. "the optimization" here is
misleading, what we really have is a whole class of optimizations
enabled by taking advantage of signed overflow being undefined.

How energetic compilers are in taking advantage of this will vary
a lot, and is neither easy to determine nor document. What you have
is another assertion that the compiler can propagate to determine
optimization conditions. Whether this assertion is propagated
forwards and/or backwards, and how far-reaching the effect of the
assertion is will depend on the structure of the compiler and how
good it is at theorem proving internally.

So all we can say is that other compilers (including ICC) take
advantage of this assertion, but that does not mean that the
performance or behavior of the generated code will be equivalent
or even similar with respect to this particular condition.




Did I misunderstand?

Gerald

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Robert Dewar]

Vincent Lefevre wrote:

On 2006-12-31 10:08:32 -0500, Richard Kenner wrote:

Well, that's not equivalent. For instance, MPFR has many conditions
that evaluate to TRUE or FALSE on some/many implementations (mainly
because the type sizes depend on the implementation), even without
the assumption that an overflow cannot occur.

Can you give an example of such a condition and show how an
optimization that assumed overflows were undefined could break that
code?


This won't break the code.


OK, so your answer to Richard is simply no, helping to confirm
his pragmatic assertion that the code in GCC that assumes wrapping
is in practice (if not in theory) safe from the optimization efforts
in this area.


But I'm saying that if the compiler assumes
wrapping, even in some particular cases (e.g. code that *looks like*
"overflow check"), it could miss some potential optimizations. That
is, it is not possible to avoid breaking overflow checks *and*
optimizing everything else.


Of course, but this has nothing to do with Richard's point

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Vincent Lefevre]

On 2006-12-31 11:01:45 -0500, Robert Dewar wrote:
> The issues are
> 
> a) are these optimizations valuable? (and if so, in all cases,
>or only in practice for loop invariants?).

Even if they aren't valuable today, you don't know what will happen
in future code. So, there's another issue: is it OK to encourage bad
practice (possibly as a side effect by making a difference between
loop invariants and other cases)?

-- 
Vincent Lefèvre <[EMAIL PROTECTED]> - Web: 
100% accessible validated (X)HTML - Blog: 
Work: CR INRIA - computer arithmetic / Arenaire project (LIP, ENS-Lyon)

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Richard Kenner]

> This won't break the code. But I'm saying that if the compiler assumes
> wrapping, even in some particular cases (e.g. code that *looks like*
> "overflow check"), it could miss some potential optimizations. That
> is, it is not possible to avoid breaking overflow checks *and*
> optimizing everything else.

Certainly.  Indeed I think that's the whole point of this thread: that if
you want to catch ALL potential optimizations opportunities given to you
by the standard, you must assume that signed overflows are undefined.

However, what's being discussed is an engineering tradeoff where you give
up SOME optimization opportunities to avoid breaking code.

Essentially, there are three choices: with -fwrapv, you must preseve wrapping
semantics and do NONE of those optimizations; with -fno-wrapv, you can do ALL
of them; in the default cause, a heuristic can be used that attempts to
balance optimization quality against breakage of old code.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Robert Dewar]

Richard Kenner wrote:
]

Essentially, there are three choices: with -fwrapv, you must preseve wrapping
semantics and do NONE of those optimizations; with -fno-wrapv, you can do ALL
of them; in the default cause, a heuristic can be used that attempts to
balance optimization quality against breakage of old code.


Right, and such heuristics are certainly appropriate when you have
conflicting requirements, especially when both requirements

a) do all the optimizations possible
b) don't break existing code

are both ill defined

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Duncan Sands]

On Sunday 31 December 2006 16:19, Richard Kenner wrote:
> > If done in unsigned, this won't lead to any optimization, as unsigned
> > arithmetic doesn't have overflows. So, if you write "a - 10" where a
> > is unsigned, the compiler can't assume anything, whereas is a is
> > signed, the compiler can assume that a >= INT_MIN + 10, reducing
> > the range for a, and possibly allowing some optimizations.
> 
> I don't follow.  The purpose of this hand-optimization (whch is also done
> by GCC) is to replace two comparisons with one subtraction and one
> comparison, which is faster on most machines.  It's not CORRECT to do this
> transformation in signed unless you know there won't be overflow. 
> 
> In general, for modern compilers it's best not to do this transformation
> AT ALL and let the compiler figure out the best way to do the range tst.

Funny you should say that, because the Ada front-end likes to do this
transformation, rather than leaving it to the back-end.  For example:

procedure P (X : Natural) is
   subtype Y is Natural range 10 .. 20;
begin
   if X in Y then
  raise Program_Error;
   end if;
end;

turns into

P (x)
{
  typedef p__y___XDLU_10__20 p__y___XDLU_10__20;

typedef p__y___XDLU_10__20 p__y___XDLU_10__20;
  if ((unsigned int) ((integer) x - 10) <= 10)
{
  __gnat_rcheck_17 ("p.adb", 5);
}
  else
{

}
  return;
}

The C front-end performs this transformation too.  I'm not claiming that the
back-end optimizers would actually do something sensible if the front-end
didn't transform this code (in fact they don't seem too), but since the
optimal way of doing the check presumably depends on the target, wouldn't
it make sense if the backend took care of it?

Best wishes,

Duncan.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Robert Dewar]

Duncan Sands wrote:


The C front-end performs this transformation too.  I'm not claiming that the
back-end optimizers would actually do something sensible if the front-end
didn't transform this code (in fact they don't seem too), but since the
optimal way of doing the check presumably depends on the target, wouldn't
it make sense if the backend took care of it?


Remember that not all GNAT backends use GCC, so sometimes we do
optimizations in the front end rather than duplicate the code in
each of our back ends (JGNAT, Dotgnat (the .Net version), AAMP,
and maybe more in the future, who knows?)

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Paul Schlie]

Upon attempted careful reading of the standard's excerpts quoted by
Gabriel Dos Reis per ,
it's not clear that GCC's current presumption of LIA-1 overflow semantics
in absents of their true support is actually advocated by the standard.

As by my read, it seems fairly clear that "If an implementation adds
support for the LIA-1 exception values ... then those types are LIA-1
conformant types"; implies to me an intent that LIA-1 semantics may be
legitimately presumed "if" the semantics are "supported" by a target
implementation (just as null pointer optimizations should not be
considered legitimate if not correspondingly literally supported by
a given target).

Which makes sense, as if a target factually supports LIA-1 overflow
trapping, then a compiler may "safely" presume the behavior, and
thereby leverage it knowing that the target's runtime semantics are
preserved; just as a compiler may "safely" presume that wrapping or
other overflow semantics for the purpose of optimization for targets
which factually "support" those semantics; all of which are legitimate,
as the standard defines signed integer overflow semantics as being
undefined, and thereby provides implementation's the liberty to augment
the language by defining that otherwise being undefined by the standard.

However GCC's current predisposition to presume semantics which are known
to differ from a target's factual behavior in the name of optimization
is likely beyond that intended to be productively enabled by the standard
(although arguably perversely legitimate); and should be reconsidered as
any optimization which risks altering a program's expressed behavior is
most often never desirable (although the diagnosis of behaviors which
can't be strictly portably relied upon is most often always desirable).

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Robert Dewar]

Paul Schlie wrote:

Upon attempted careful reading of the standard's excerpts quoted by
Gabriel Dos Reis per ,
it's not clear that GCC's current presumption of LIA-1 overflow semantics
in absents of their true support is actually advocated by the standard.

As by my read, it seems fairly clear that "If an implementation adds
support for the LIA-1 exception values ... then those types are LIA-1
conformant types"; 


You are reaching here, based on your peculiar notion of the relevance
of behavior of some target instructions to language semantics. But
there is no such relation. The C standard creates a semantic model
that is entirely independent of the target architecture with respect
to the overflow issue. The behavior of instructions on the machine
has nothing to do with what a compiler must implement.

> implies to me an intent that LIA-1 semantics may be
> legitimately presumed "if" the semantics are "supported" by a target
> implementation

It may (and apparently does) imply this to you, but there is
absolutely no implication of this in the standard. if the standard
wanted to say this, it would (although it would be VERY difficult
to state this in meaningful normative form).

> (just as null pointer optimizations should not be
> considered legitimate if not correspondingly literally supported by
> a given target).

There is no such implication in the standard. either

You persist in this strange notion of "factual support" of the
"target", but there is nothing to support this notion in either
the standard

There is reasonable grounds for arguing for limiting the
effects of this particular undefined optimization, but you
can not find any support for this in the standard itself
at all.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Gabriel Dos Reis]

Robert Dewar <[EMAIL PROTECTED]> writes:

| Gerald Pfeifer wrote:
| > On Sun, 31 Dec 2006, Robert Dewar wrote:
| >> If you do it in signed expecting wrapping, then the optimization
| >> destroys your code. Yes, it is technically your fault, but this
| >> business of telling users
| >>
| >> "sorry, your code is non-standard, gcc won't handle it as you
| >> expect, go fix your code"
| > My understanding of previous messages in this thread was that other
| > compilers (like ICC) do enable the optimization we are talking about
| > here by default.
| 
| Well that's not such a clear criterion. "the optimization" here is
| misleading, what we really have is a whole class of optimizations
| enabled by taking advantage of signed overflow being undefined.

We need more precise collection of data than "I've heard xxx does the
same optimization", because it is not clear when xxx does it and under
what conditions.  For example, Sun (which has been cited in this
thread) spends lot of resources on ensuring backward compability,
whether anachronistic or downright illegal codes[1] or existing
pratice even if not blessed by the standards, that I would like
to see more precise reports than hear-say. 

[1] at recent C++ committee meetings, Sun representative objected to the
new meaning of C++ keyword auto on the ground that they still supports
implicit "int", which has been banned from mode than a decade ago.

-- Gaby

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Gabriel Dos Reis]

[EMAIL PROTECTED] (Richard Kenner) writes:

[...]

| > but from other evidence it's clear that common traditional practice assumes
| > wrapv semantics.
| 
| "Common traditional C" was actually yet another language that was even more
| ill-defined because it included such things as structure assignment that
| weren't in K&Rv1.

Indeed.  Dennis Ritchie is said to have a sticker on this terminal
where "Classic C" refers to "K&R C + structure assigments,
enumerations and void"[1].

[1] http://www.research.att.com/~bs/siblings_short.pdf

-- Gaby

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Richard Kenner]

> Funny you should say that, because the Ada front-end likes to do this
> transformation, rather than leaving it to the back-end.  For example:
> 
> turns into
> 
>   if ((unsigned int) ((integer) x - 10) <= 10)

The front end isn't doing this: the routine "fold" in fold-const.c is.
True, it's being *called* by the front-end, but it's very definitely
common code.

See -gnatdg if you want to know what transformations the Ada front end
if making.

> The C front-end performs this transformation too.  

See above. ;-)

> I'm not claiming that the back-end optimizers would actually do
> something sensible if the front-end didn't transform this code

I consider the optimizer that does this part of the middle-end (which
is really what you mean, not "back end").

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Gabriel Dos Reis]

[EMAIL PROTECTED] (Richard Kenner) writes:

| > And the idea that people were not used to thinking seriously about
| > language semantics is very odd, this book was published in 1978,
| > ten years after the algol-68 report, a year after the fortran
| > 77 standard, long after the COBOL 74 standard, and a year before the 
| > PL/1 standard. It's not that old!
| 
| I knew you were going to say something like that, which is why I edited
| my message to say "most people": yes, there were certainly groups (I 
| specifically had Algol 68 in mind) who were thinking of programming
| languages in very formal terms, but those represented an even smaller
| minority of the community than now and certainly the Unix/C community's
| view at that point was much more pragmatic than formal: that's the point
| that a lot of people in this thread are making.

No doubt most people in the unix room were very pragmatic; after all,
Dennis Ritchie is credited for having stated "some languages are
designed to prove a point, others are meant to solve a problem", at
the second HOPL conference.

It seems theoretical discussions were given importance to the extent
which they helped solve real problems.  For example,

 http://cm.bell-labs.com/cm/cs/who/dmr/chist.html

   [...]
   For all these reasons, it seemed that a typing scheme was necessary
   to cope with characters and byte addressing, and to prepare for the
   coming floating-point hardware. Other issues, particularly type
   safety and interface checking, did not seem as important then as
   they became later.

   [...]
   The language changes during this period, especially around 1977,
   were largely focused on considerations of portability and type
   safety, in an effort to cope with the problems we foresaw and
   observed in moving a considerable body of code to the new Interdata
   platform. C at that time still manifested strong signs of its
   typeless origins. Pointers, for example, were barely distinguished
   from integral memory indices in early language manuals or extant
   code; the similarity of the arithmetic properties of character
   pointers and unsigned integers made it hard to resist the
   temptation to identify them. The unsigned types were added to make
   unsigned arithmetic available without confusing it with pointer
   manipulation. Similarly, the early language condoned assignments
   between integers and pointers, but this practice began to be
   discouraged; a notation for type conversions (called `casts' from
   the example of Algol 68) was invented to specify type conversions
   more explicitly. Beguiled by the example of PL/I, early C did not
   tie structure pointers firmly to the structures they pointed to,
   and permitted programmers to write pointer->member almost without
   regard to the type of pointer; such an expression was taken
   uncritically as a reference to a region of memory designated by the
   pointer, while the member name specified only an offset and a type.


However, the community wasn't immune to formal terms.
Ravi Sethi published the first attempt to formalize C semantics in POPL'80 

   "A case study in specifying the semantics of a programming language",
 

http://portal.acm.org/citation.cfm?id=567458&coll=Portal&dl=GUIDE&CFID=10235106&CFTOKEN=61874737



-- Gaby

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Gabriel Dos Reis]

Robert Dewar <[EMAIL PROTECTED]> writes:

[...]

| In fact K&R is much stronger than you think in terms of providing
| a precise definition of the language. Too bad people did not read it.
| 
| As I said earlier in this thread, people seem to think that the
| standards committee invented something new here in making overflow
| undefined, but I don't think that's the case. I personally would
| have thought it more judicious to make it implementation defined,

I'm not sure the original C specification made that fine distinction
between "implementation defined" and "undefined behaviour".  I'll have
opportunity to check a manual from '77 nnot before two weeks from now.

You're right that the unix room people were quite well accointed with
formal techniques, type safety and soundness.  However, they valued
solving practical problems, over theoretical specification.  Most of C
language "reshaping" came from trying to port programs to new
machines, etc.

-- Gaby

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Paul Eggert]

"Daniel Berlin" <[EMAIL PROTECTED]> writes:

> These are not performance needing applications.

No, I chose gzip -9 and sha512sum precisely because they are
CPU-bound (integer arithmetic only).  On my platform, if the
input file is cached sha512sum is approximately 300 times
slower than 'cat', and gzip -9 is approximately 1000 times
slower.

> The burden ought to be (and IMHO is) on those who propose we change
> optimizer behavior in order to support something non-standard.

Please, let's move beyond this "non-standard" rhetoric.
There's nothing weird or unusual about assuming wrapv
semantics.  As we've seen it is common practice dating back
to Unix source code in the 1970s, and (if you want to be
pedantic) C99 Annex H with LIA-1 wrapping semantics gives a
standard for it.

The question is not whether GCC should support wrapv
semantics; it already does, if you specify -fwrapv.
The question is merely whether wrapv should be the default
with optimization levels -O0 through -O2.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Gabriel Dos Reis]

Paul Schlie <[EMAIL PROTECTED]> writes:

| Upon attempted careful reading of the standard's excerpts quoted by
| Gabriel Dos Reis per ,
| it's not clear that GCC's current presumption of LIA-1 overflow semantics
| in absents of their true support is actually advocated by the standard.
| 
| As by my read, it seems fairly clear that "If an implementation adds
| support for the LIA-1 exception values ... then those types are LIA-1
| conformant types"; implies to me an intent that LIA-1 semantics may be
| legitimately presumed "if" the semantics are "supported" by a target
| implementation (just as null pointer optimizations should not be
| considered legitimate if not correspondingly literally supported by
| a given target).

Note, however, that LIA-1 conformance -- just like IEEE-754
conformance -- is more than just wrapping semantics.

Interestingly, GCC/g++ advertises wrapping semantics for the following
types 

   * char
   * signed char
   * unsigned char
   * wchar_t
   * short
   * unsigned short
   * int
   * unsigned int
   * long
   * unsigned long
   * long long
   * unsigned long long

this ad is brought to you by std::numeric_limits::is_modulo.

-- Gaby

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Paul Schlie]

> Robert wrote:
>> Paul Schlie wrote:
>> Upon attempted careful reading of the standard's excerpts quoted by
>> Gabriel Dos Reis per ,
>> it's not clear that GCC's current presumption of LIA-1 overflow semantics
>> in absents of their true support is actually advocated by the standard.
>> 
>> As by my read, it seems fairly clear that "If an implementation adds
>> support for the LIA-1 exception values ... then those types are LIA-1
>> conformant types";
> 
> You are reaching here, based on your peculiar notion of the relevance
> of behavior of some target instructions to language semantics. But
> there is no such relation. The C standard creates a semantic model
> that is entirely independent of the target architecture with respect
> to the overflow issue. The behavior of instructions on the machine
> has nothing to do with what a compiler must implement.

- Yes it's a stretch, however although it's agreed there's no intrinsic
  relationship between a language's semantics and a particular target
  machine's instruction set; the compiler in effect defines one, which
  arguably should ideally be consistently preserved, as attempting to
  leverage behaviors factually not present in the compiler's originally
  chosen mappings, may worst case silently alter the originally expressed
  behavior of the resulting program to likely no one's benefit, presuming
  the original behavior as defined by the compiler was in fact desired,
  although both considered legitimate.

>> implies to me an intent that LIA-1 semantics may be
>> legitimately presumed "if" the semantics are "supported" by a target
>> implementation
> 
> It may (and apparently does) imply this to you, but there is
> absolutely no implication of this in the standard. if the standard
> wanted to say this, it would (although it would be VERY difficult
> to state this in meaningful normative form).

- Correspondingly, if the standard didn't intend to clarify LIA-1
  conforming support within the scope of undefined signed overflow
  semantics, it need not have "said" anything; thereby seemingly
  considered an implementation's optional "support" of LIA-1 to be
  worth noting, and predicated on its "support" (which most targets
  simply inherently don't).

>> (just as null pointer optimizations should not be
>> considered legitimate if not correspondingly literally supported by
>> a given target).
> 
> There is no such implication in the standard. either

- Only by analogy to above.

> You persist in this strange notion of "factual support" of the
> "target", but there is nothing to support this notion in either
> the standard
> 
> There is reasonable grounds for arguing for limiting the
> effects of this particular undefined optimization, but you
> can not find any support for this in the standard itself
> at all.

- Agreed.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Bruce Korb]

Daniel Berlin wrote:
>> Admittedly it's only two small tests, and it's with 4.1.1.  But that's
>> two more tests than the -fwrapv naysayers have done, on
>> bread-and-butter applications like coreutils or gzip or Emacs (or GCC
>> itself, for that matter).
> 
> These are not performance needing applications.
> I'll happily grant you that  adding -fwrapv will make no difference at
> all on any application that does not demand performance in integer or
> floating point calculations.

It seems then that this pretty-much ought to settle it:
If the only folks that would really care are those that do performance
critical work, then 99.9% of folks not doing that kind of work should
not bear the risk of having their code break.  The long standing
presumption, standardized or not, is that of wrapv semantics.
Changing that presumption without multiple years of -Wall warnings
is a Really, Really, Really Bad Idea.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Gabriel Dos Reis]

Paul Eggert <[EMAIL PROTECTED]> writes:

| > In that case, we should make the Autoconf change optional.
| > I'll propose a further patch along those lines.
| 
| OK, here's that proposed patch to Autoconf.  Also, this patch attempts
| to discuss the matter better in the documentation.  The documentation
| was by far the hardest part of the patch to write, and I'd appreciate
| any comments/reviews for it.

To the attention of the Steering Committee.

Additional data: the the C++ runtime support assumes and publishes
wrapping semantics for signed integer arithmetic overflow.  This can
be seen from numeric_limits::is_modulo. 
This has been so for about half a decade now (sorry I don't have the exact
dates). 

-- Gaby

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Bernd Schmidt]

Paul Eggert wrote:

But so far, benchmark scores are the only scores given by the people
who oppose having -O2 imply -fwrapv.


And you expect real-world results will be different because...?


You say you doubt it affects performance.  Based on what?  Facts
please, not guesses and hand-waiving...


The burden of proof ought to be on the guys proposing -O2
optimizations that break longstanding code, not on the skeptics.


IMHO the burden of proof should be on the people who are surprised that 
interesting things happen when they write in a language that isn't C and 
then try to pass it through a C compiler.


Has an example of code that actually breaks with a new gcc but not an 
old one been posted in this thread yet?  With -fstrict-aliasing we at 
least had examples of code that really broke with a new optimization 
before we disabled it (in the compiler, not in autoconf, mind you). 
Code got fixed, -fstrict-aliasing got enabled a release later, everyone 
moved on.



Bernd

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Robert Dewar]

Paul Eggert wrote:


The question is not whether GCC should support wrapv
semantics; it already does, if you specify -fwrapv.
The question is merely whether wrapv should be the default
with optimization levels -O0 through -O2.


That over simplifies, because it presents things as though
there are only two possibilities

1. Allow "undefined" optimizations without restriction

2. Forbid all such optimizations by specifying fwrapv

Quite a few of us (including certainly me, and I think
Richard) argue for a mid ground where

We don't insist on full fwrapv semantics (because we
think it will hurt code equality, particularly in the
loop invariant case).

We are judcious in applying the optimization in other
cases in a pragmatic attempt to keep "traditional"
C code working in practice.

Re: Link tests not allowed

[DJ Delorie]

> Newlib targets are targets without their own native libc.  I find it
> exceedingly hard to believe that AIX falls into this category.

Newlib supports some platforms that have their own native libc.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Robert Dewar]

Bruce Korb wrote:


Changing that presumption without multiple years of -Wall warnings
is a Really, Really, Really Bad Idea.


I am still not ready to agree that this is a RRRBI for the case
of loop invariants. We have not seen ONE imaginary example, let
alone a real example, where the optimziation of loop invariants
(by far the most important optimization in the class we are
discussing) would break existing code.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Richard Guenther]

On 12/31/06, Robert Dewar <[EMAIL PROTECTED]> wrote:

Paul Eggert wrote:

> The question is not whether GCC should support wrapv
> semantics; it already does, if you specify -fwrapv.
> The question is merely whether wrapv should be the default
> with optimization levels -O0 through -O2.

That over simplifies, because it presents things as though
there are only two possibilities

1. Allow "undefined" optimizations without restriction

2. Forbid all such optimizations by specifying fwrapv

Quite a few of us (including certainly me, and I think
Richard) argue for a mid ground where

We don't insist on full fwrapv semantics (because we
think it will hurt code equality, particularly in the
loop invariant case).

We are judcious in applying the optimization in other
cases in a pragmatic attempt to keep "traditional"
C code working in practice.


I think this is a fragile and not very practical approach.  How
do you define these "traditional" cases?  I guess you would
keep the other two as well, so have the mid ground default,
-fno-wrapv do what we have now and -fwrapv disable all
the optimizations.

I'd rather enable -fwrapv at -O1 and keep -O2 as is.  This is
what we also do for strict-aliasing, it's enabled at -O2 and beyond
only (for C, that is).  Of course with -O1 the VRP pass is not run, so
it might be that the reported problems do not show up with -O1 - and
as they are reportedly not for performance critical code they should
maybe just use -O1 as autoconf default.

Richard.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Karl Berry]

>The question is merely whether wrapv should be the default
>with optimization levels -O0 through -O2.

Perhaps the question of where wrapv gets enabled, together with the
"middle ground" approach mentioned by Robert Dewar, could be put to the
GCC Steering Committee.  (As was already proposed many messages ago, but
seems to have been lost.)

karl

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Paul Eggert]

[EMAIL PROTECTED] (Richard Kenner) writes:

> that one is a weak example because it's *much* more likely that
> the author of that code didn't even *think* about the INT_MIN case

I think this seriously underestimates the programming abilities of the
original Unix developers.  But if that example doesn't convince you,
how about this one, taken from the Unix v7 /usr/src/libc/gen/rand.c:

static  longrandx = 1;
...
rand()
{
return(((randx = randx*1103515245 + 12345)>>16) & 07);
}

Surely here the programmer knew and expected wrapv semantics.

Almost exactly same 'rand' code lives on in Solaris.  OpenSolaris
/usr/src/ucblib/libucb/port/gen/rand.c (2006-11-21) has this:

static  int randx = 1;
...
int
rand(void)
{
return ((randx = randx * 1103515245 + 12345) & 0x7fff);
}

Again, the wrapv assumption is clearly there.

GCC won't break this code now, but GCC is entitled to break it because
the code violates the strict C99 standard.  A simple and plausible
optimization that would break the Solaris code, for example, would be
to omit the "& 0x7fff" because randx must always be positive when
behavior is well-defined.

I am sure I can come up with many other examples.  The wrapv
assumption was and is pervasive in real-world Unix code.

>> Wait, though: K&Rv2 is post-C89.  
>
> Not completely: it's published in 1988, but the cover says "based on
> draft-proposed ANSI C".

Yes, I should have been more precise and written "intended to be
post-C89".  Whichever way it's said, though, K&Rv2 is not the best
source for documenting traditional C semantics.

> the *purpose* of the original ANSI C standard was to standardize common
> practice in C precisely because people were already writing in a language
> that went beyond K&R so there was need to precisely define that language.

Sure, but as with any standard, there were multiple cross-currents of
purpose.  One strong influence on the C89 standard was that of
compiler writers, who wanted to place enough constraints on the
standard that they could do Fortran-style optimizations on C code.

I don't think the _users_ of C had much to say about the treatment of
integer overflow in C89.  As is usual in standardization battles like
this, users generally are poorly represented in the relevant
committees and their concerns are reflected only indirectly in the
standard.  Typically, the most that users can do is vote with their
feet afterwards.

> I just found the Rationale document for ANSI C (C89).  In the section on
> Additive Operators, it says "Overflow was considered not to break old code
> since it was undefined by K&R".

If memory serves K&Rv1 didn't talk about overflow, yes.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Richard Kenner]

> I think this is a fragile and not very practical approach.  How do
> you define these "traditional" cases?  

You don't need to define the "cases" in advance.  Rather, you look at
each place where you'd be making an optimization based on the non-existance
of overflow and use knowlege of the importance of that optimization and the
types of code likely to trigger it to choose the default for whether to make
it or not.  It seems quite practical to me.

It also doesn't seem fragile: if you guess wrong on one particular default,
it's easy to change it.

> I guess you would keep the other two as well, so have the mid ground
> default, -fno-wrapv do what we have now and -fwrapv disable all the
> optimizations.

Right.  That's certainly my proposal.

> I'd rather enable -fwrapv at -O1 and keep -O2 as is.  This is what
> we also do for strict-aliasing, it's enabled at -O2 and beyond only
> (for C, that is).  Of course with -O1 the VRP pass is not run, so it
> might be that the reported problems do not show up with -O1 - and as
> they are reportedly not for performance critical code they should
> maybe just use -O1 as autoconf default.

My concern here would be the loop stuff.  That's such an important optimization
and has so low chance of causing problems that I think non-wrapping should
be assumed for it at each level that it applies.  I agree that it might
be reasonable to change some of the defaults so they change as a function
of the optimization level.

RE: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Dave Korn]

On 31 December 2006 18:47, Paul Eggert wrote:

> "Daniel Berlin" <[EMAIL PROTECTED]> writes:

> The question is not whether GCC should support wrapv
> semantics; it already does, if you specify -fwrapv.
> The question is merely whether wrapv should be the default
> with optimization levels -O0 through -O2.

  Maybe we need to make it a trinary, like -Wstrict-aliasing.  Then we would
turn on -fwrapv=1 at -O2, and we would only need to argue about which
wrap-assuming optimisations were suitable for level 1 and which weren't.


cheers,
  DaveK
-- 
Can't think of a witty .sigline today

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Gabriel Dos Reis]

Bernd Schmidt <[EMAIL PROTECTED]> writes:

[...]

| >> You say you doubt it affects performance.  Based on what?  Facts
| >> please, not guesses and hand-waiving...
| > The burden of proof ought to be on the guys proposing -O2
| > optimizations that break longstanding code, not on the skeptics.
| 
| IMHO the burden of proof should be on the people who are surprised
| that interesting things happen when they write in a language that
| isn't C and then try to pass it through a C compiler.

I don't believe that statement is accurate.  You will be hard pressed
to state precisely what "a language that isn't C" means.

The ISO C standard defines an unbounded family of languages.  And
certainly the wrapping semantics is part of that family.

-- Gaby

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[David Daney]

Paul Eggert wrote:

If memory serves K&Rv1 didn't talk about overflow, yes.
  

My K&R V1 says in Appendix A (C Reference Manual) Section 7:
.
.
.
The handling of overflow and divide check in expression evaluation is 
machine-dependent.  All existing implementations of C ignore integer 
overflows;  treatment of division by 0, and all floating-point 
exceptions, varies between machines, and is usually adjustable by a 
library function.


In chapter 2, section 2.5 it basically says the same thing.

Those are the only two places the index indicates that 'overflow' is 
described.




David Daney

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Richard Guenther]

On 12/31/06, Richard Kenner <[EMAIL PROTECTED]> wrote:

> I think this is a fragile and not very practical approach.  How do
> you define these "traditional" cases?

You don't need to define the "cases" in advance.  Rather, you look at
each place where you'd be making an optimization based on the non-existance
of overflow and use knowlege of the importance of that optimization and the
types of code likely to trigger it to choose the default for whether to make
it or not.  It seems quite practical to me.

It also doesn't seem fragile: if you guess wrong on one particular default,
it's easy to change it.


Are you volunteering to audit the present cases and argue whether they
fall in the "traditional" cases?  Note that -fwrapv also _enables_ some
transformations on signed integers that are disabled otherwise.  We for
example constant fold -CST for -fwrapv while we do not if signed overflow
is undefined.  Would you change those?

Richard.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Richard Kenner]

> Are you volunteering to audit the present cases and argue whether they
> fall in the "traditional" cases?

I'm certainly willing to *help*, but I'm sure there will be some cases
that will require discussion to get a consensus.

> Note that -fwrapv also _enables_ some transformations on signed
> integers that are disabled otherwise.  We for example constant fold
> -CST for -fwrapv while we do not if signed overflow is undefined.
> Would you change those?

I don't understand the rationale for not wrapping constant folding when
signed overflow is undefined: what's the harm in "defining" it as wrapping
for that purpose?  If it's undefined, then why does it matter what we
fold it to?  So we might as well fold it to what traditional code expects.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Daniel Berlin]

On 12/31/06, Richard Guenther <[EMAIL PROTECTED]> wrote:

On 12/31/06, Daniel Berlin <[EMAIL PROTECTED]> wrote:
> On 12/31/06, Paul Eggert <[EMAIL PROTECTED]> wrote:
> > "Steven Bosscher" <[EMAIL PROTECTED]> writes:
> >
> > > On 12/31/06, Paul Eggert <[EMAIL PROTECTED]> wrote:
> > >> Also, as I understand it this change shouldn't affect gcc's
> > >> SPEC benchmark scores, since they're typically done with -O3
> > >> or better.
> > >
> > > It's not all about benchmark scores.
> >
> > But so far, benchmark scores are the only scores given by the people
> > who oppose having -O2 imply -fwrapv.  If the benchmarks use -O3 they
> > wouldn't be affected by such a change -- and if so, we have zero hard
> > evidence of any real harm being caused by having -O2 imply -fwrapv.
> >
> > > I think most users compile at -O2
> >
> > Yes, which is why there's so much argument about what -O2 should do
> >
> > > You say you doubt it affects performance.  Based on what?  Facts
> > > please, not guesses and hand-waiving...
> >
> > The burden of proof ought to be on the guys proposing -O2
> > optimizations that break longstanding code, not on the skeptics.
>
> The burden ought to be (and IMHO is) on those who propose we change
> optimizer behavior in order to support something non-standard.
>
> Why do you believe otherwise?
> >
> > That being said, I just compiled GNU coreutils CVS on a Debian stable
> > x86 (2.4 GHz Pentium 4) using GCC 4.1.1.  With -O0, "sha512sum" on the
> > coreutils tar.gz file took 0.94 user CPU seconds (measured by "time
> > src/sha512sum coreutils-6.7-dirty.tar.gz").  With -O2 -fwrapv, 0.87
> > seconds.  With plain -O2, 0.86 seconds.
> >
> > I also tried gzip 1.3.10, compressing its own tar file with a -9
> > compression option.  With -O0, 0.30 user CPU seconds.  With -O2
> > -fwrapv, 0.24 seconds.  With -O2, 0.24 seconds.
> >
> > In all these cases I've averaged several results.  The difference
> > between -O2 and -O2 -fwrapv is pretty much in the noise here.
> >
> > Admittedly it's only two small tests, and it's with 4.1.1.  But that's
> > two more tests than the -fwrapv naysayers have done, on
> > bread-and-butter applications like coreutils or gzip or Emacs (or GCC
> > itself, for that matter).
>
> These are not performance needing applications.
> I'll happily grant you that  adding -fwrapv will make no difference at
> all on any application that does not demand performance in integer or
> floating point calculations.

I added -fwrapv to the Dec30 run of SPEC at
http://www.suse.de/~gcctest/SPEC/CFP/sb-vangelis-head-64/recent.html
and
http://www.suse.de/~gcctest/SPEC/CINT/sb-vangelis-head-64/recent.html



Note the distinct drop in performance across almost all the benchmarks
on Dec 30, including popular programs like bzip2 and gzip.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Daniel Berlin]

On 12/31/06, Bruce Korb <[EMAIL PROTECTED]> wrote:

Daniel Berlin wrote:
>> Admittedly it's only two small tests, and it's with 4.1.1.  But that's
>> two more tests than the -fwrapv naysayers have done, on
>> bread-and-butter applications like coreutils or gzip or Emacs (or GCC
>> itself, for that matter).
>
> These are not performance needing applications.
> I'll happily grant you that  adding -fwrapv will make no difference at
> all on any application that does not demand performance in integer or
> floating point calculations.

It seems then that this pretty-much ought to settle it:
If the only folks that would really care are those that do performance
critical work, then 99.9% of folks not doing that kind of work should
not bear the risk of having their code break.  The long standing
presumption, standardized or not, is that of wrapv semantics.
Changing that presumption without multiple years of -Wall warnings
is a Really, Really, Really Bad Idea.



I generally have no problem with turning on -fwrapv at O2, but i'm
curious where this ends.
After all, strict aliasing makes it hard to write a bunch of styles of
code people really want to write, and breaks real world programs and
GNU software.

Yet we decided to keep it on at O2, and off at O1.

We assume array accesses outside the defined length of an array are
invalid, but hey, maybe you really know something we don't there too.

Nothing but apps that actually do real work (and not just large
amounts of I/O) will notice these things.

Anyway, if you include "gzip" and "bzip2" in the applications that
demand performance in integer calculations, then you don't want it off
at O2. The spec scores show it makes both about 10% slower (at least).

You can distinguish the above cases all you want, but the idea that we
should trade performance for doing things we've told people for
*years* not to do, and finally made good on it, doesn't sit well with
me at all.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Vincent Lefevre]

On 2006-12-31 11:37:21 -0500, Richard Kenner wrote:
> Certainly.  Indeed I think that's the whole point of this thread: that if
> you want to catch ALL potential optimizations opportunities given to you
> by the standard, you must assume that signed overflows are undefined.
> 
> However, what's being discussed is an engineering tradeoff where you give
> up SOME optimization opportunities to avoid breaking code.

I was responding to a particular point. You said a few messages ago:

| I can't speak for any other GCC developer, but I personally am quite
| comfortable viewing any code that assumes wrapping semantics as broken
| and needing fixing with the exception of these cases of checking for
| overflow: there simply is no good way in C to do these checks in a portable
| manner and, as I said, I think we should make sure they continue to work
| and maybe even document that.

Now:

> Essentially, there are three choices: with -fwrapv, you must preseve
> wrapping semantics and do NONE of those optimizations; with
> -fno-wrapv, you can do ALL of them; in the default cause, a
> heuristic can be used that attempts to balance optimization quality
> against breakage of old code.

This isn't just about old code. If you're saying that old code with
overflow checking can't be fixed (in a portable manner...), then new
code will probably use the same tricks. Then hoping that such code
will continue to work is not sufficient. You need to really make sure
that it will still work. This means that either "overflow checking"
must be clearly defined, or -fwrapv should be used in any case (thus
disabling all the possible optimizations based on overflows). Well,
there's another way: a GCC extension so that the programmer can say
when wrapping is assumed.

-- 
Vincent Lefèvre <[EMAIL PROTECTED]> - Web: 
100% accessible validated (X)HTML - Blog: 
Work: CR INRIA - computer arithmetic / Arenaire project (LIP, ENS-Lyon)

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Paul Eggert]

"Daniel Berlin" <[EMAIL PROTECTED]> writes:

>> http://www.suse.de/~gcctest/SPEC/CFP/sb-vangelis-head-64/recent.html
>> and
>> http://www.suse.de/~gcctest/SPEC/CINT/sb-vangelis-head-64/recent.html
>>
> Note the distinct drop in performance across almost all the benchmarks
> on Dec 30, including popular programs like bzip2 and gzip.

That benchmark isn't that relevant, as it's using -O3, as is typical
for SPEC benchmarks.

This discussion is talking about -O2, not -O3.  The proposed change
(i.e., having -O2 imply -fwrapv) would not affect -O3 benchmark
scores.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Paul Eggert]

Robert Dewar <[EMAIL PROTECTED]> writes:

> We have not seen ONE imaginary example, let
> alone a real example, where the optimziation of loop invariants
> (by far the most important optimization in the class we are
> discussing) would break existing code.

But didn't this thread get started by a real program that was broken
by an optimization of loop invariants?  Certainly I got a real bug
report of a real problem, which you can see here:

http://lists.gnu.org/archive/html/bug-gnulib/2006-12/msg00084.html

Here is a bit more discussion:

http://gcc.gnu.org/ml/gcc/2006-12/msg00607.html

If this doesn't count as "optimization of loop invariants"
then what would count?

This particular example was just a test program run by "configure", so
the penalty for getting it wrong wasn't that severe -- the application
compiled its own version of mktime rather than using the system
mktime.  But I daresay I can find an example of real-world production
code that does something similar.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Ian Lance Taylor]

[EMAIL PROTECTED] (Richard Kenner) writes:

> > Note that -fwrapv also _enables_ some transformations on signed
> > integers that are disabled otherwise.  We for example constant fold
> > -CST for -fwrapv while we do not if signed overflow is undefined.
> > Would you change those?
> 
> I don't understand the rationale for not wrapping constant folding when
> signed overflow is undefined: what's the harm in "defining" it as wrapping
> for that purpose?  If it's undefined, then why does it matter what we
> fold it to?  So we might as well fold it to what traditional code expects.

If flag_wrapv is false, we can't do any optimization which may
introduce signed overflow when it did not already exist.  If we do,
future optimization passes may take advantage of the undefined signed
overflow to break the code unjustifiably.  The problem is that we
don't have a way to annotate particular tree or RTL nodes as using
wrapping arithmetic.  (This is something we will have to change for
LTO.)

Ian

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Richard Kenner]

> This isn't just about old code. If you're saying that old code with
> overflow checking can't be fixed (in a portable manner...), then new
> code will probably use the same tricks. 

I said there's no "good" way, meaning as compact as the current tests.  But
it's certainly easy to test for overflow in a correct and portable manner
that's not TOO inefficient.  I haven't tested it, but this ought to do it and
is only 9 instructions on x86-64:

/* Return 1 IFF a + b will overflow as signed numbers.  Assumes two's
   complement.  */

bool
overflow (int a, int b)
{
  unsigned int pos_a, pos_b;

  /* If they have different signs, their sum can't overflow.  */
  if ((a ^ b) < 0)
return false;

  /* Otherwise, sum the non-sign bits as unsigned (this is close to abs,
 but avoids overflow for INT_MIN) and see if that, interpreted as a
 signed number, would be negative.  If so, the sum will overflow.  */
  pos_a = (a & ((1u << (sizeof (int) * HOST_BITS_PER_CHAR - 1)) - 1));
  pos_b = (b & ((1u << (sizeof (int) * HOST_BITS_PER_CHAR - 1)) - 1));
  return (pos_a + pos_b) >> (sizeof (int) * HOST_BITS_PER_CHAR - 1);
}

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Seongbae Park]

On 12/31/06, Daniel Berlin <[EMAIL PROTECTED]> wrote:
...

> I added -fwrapv to the Dec30 run of SPEC at
> http://www.suse.de/~gcctest/SPEC/CFP/sb-vangelis-head-64/recent.html
> and
> http://www.suse.de/~gcctest/SPEC/CINT/sb-vangelis-head-64/recent.html

Note the distinct drop in performance across almost all the benchmarks
on Dec 30, including popular programs like bzip2 and gzip.


Also, this is only on x86 -
other targets that benefit more from software pipelinine/modulo scheduling
may suffer even more than x86, especially on the FP side.
--
#pragma ident "Seongbae Park, compiler, http://seongbae.blogspot.com";

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Richard Kenner]

> http://gcc.gnu.org/ml/gcc/2006-12/msg00607.html
> 
> If this doesn't count as "optimization of loop invariants"
> then what would count?

One where the induction variable was updated additively, not
multiplicatively.  When we talk about normal loop optimizations,
that's what we mean.  I agree that the optimization in this case is of
questionable value.

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Richard Kenner]

> > > Note that -fwrapv also _enables_ some transformations on signed
> > > integers that are disabled otherwise.  We for example constant fold
> > > -CST for -fwrapv while we do not if signed overflow is undefined.
> > > Would you change those?
> > 
> > I don't understand the rationale for not wrapping constant folding when
> > signed overflow is undefined: what's the harm in "defining" it as wrapping
> > for that purpose?  If it's undefined, then why does it matter what we
> > fold it to?  So we might as well fold it to what traditional code expects.
> 
> If flag_wrapv is false, we can't do any optimization which may
> introduce signed overflow when it did not already exist.  

But how would that happen here?  If we constant-fold something that would
have overflowed by wrapping, we are ELIMINATING a signed overflow, not
INTRODUCING one.  Or do I misunderstand what folding we're talking about here?

Re: Link tests not allowed

[Jim Wilson]

Douglas B Rupp wrote:

checking for library containing strerror... configure: error: Link tests
are not allowed after GCC_NO_EXECUTABLES.


You get this error if a link command fails while trying to configure the 
target libiberty.  So the question is why did the link fail?  You need 
to look at the target libiberty config.log file to find out why.  The 
interesting part will be immediately after the -V test.  There are many 
different ways that the link may have failed, and there are many 
different ways to fix this, depending on what exactly the problem is.


One way to solve this is to use newlib at the target library, in which 
case libiberty uses a built-in list of functions instead of doing link 
tests.  This however is clearly the wrong solution in your case, as AIX 
of course uses the AIX C library, not newlib.


I tried to reproduce this, and found the problem is that aix4.3 and up 
require additional nm/ar options.  NM_FOR_TARGET in the toplevel 
Makefile includes the -B and -X32_64 options.  Inside the gcc configure, 
we do "test -x $NM_FOR_TARGET" and this fails because NM_FOR_TARGET 
expands to more than a program name, and the shell test -x command does 
not handle this case.  We need to extract out the program name for this 
test.  This should be easy enough to do.  There is an example showing 
how to do this a few lines below.  Want to try writing a patch?  Or 
alternatively submitting a bug report so we can track this?


Admittedly, the configure error printed is a bit misleading.  It used to 
make sense when it was first written, but a lot of stuff has changed 
since then, and the error message never got updated.

--
Jim Wilson, GNU Tools Support, http://www.specifix.com

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Ian Lance Taylor]

[EMAIL PROTECTED] (Richard Kenner) writes:

> > > > Note that -fwrapv also _enables_ some transformations on signed
> > > > integers that are disabled otherwise.  We for example constant fold
> > > > -CST for -fwrapv while we do not if signed overflow is undefined.
> > > > Would you change those?
> > > 
> > > I don't understand the rationale for not wrapping constant folding when
> > > signed overflow is undefined: what's the harm in "defining" it as wrapping
> > > for that purpose?  If it's undefined, then why does it matter what we
> > > fold it to?  So we might as well fold it to what traditional code expects.
> > 
> > If flag_wrapv is false, we can't do any optimization which may
> > introduce signed overflow when it did not already exist.  
> 
> But how would that happen here?  If we constant-fold something that would
> have overflowed by wrapping, we are ELIMINATING a signed overflow, not
> INTRODUCING one.  Or do I misunderstand what folding we're talking about here?

http://gcc.gnu.org/PR27116 is what led to the patch.

Ian

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Ian Lance Taylor]

Paul Eggert <[EMAIL PROTECTED]> writes:

> "Daniel Berlin" <[EMAIL PROTECTED]> writes:
> 
> >> http://www.suse.de/~gcctest/SPEC/CFP/sb-vangelis-head-64/recent.html
> >> and
> >> http://www.suse.de/~gcctest/SPEC/CINT/sb-vangelis-head-64/recent.html
> >>
> > Note the distinct drop in performance across almost all the benchmarks
> > on Dec 30, including popular programs like bzip2 and gzip.
> 
> That benchmark isn't that relevant, as it's using -O3, as is typical
> for SPEC benchmarks.
> 
> This discussion is talking about -O2, not -O3.  The proposed change
> (i.e., having -O2 imply -fwrapv) would not affect -O3 benchmark
> scores.

I don't entirely understand where this particular proposal is coming
from.  Historically in gcc we've used -O2 to mean turn on all
optimizations even if means taking longer to compile code.  We've used
-O3 to turn on optimizations that make riskier tradeoffs for compiled
code.  Code compiled with -O3 may be slower than code compiled with
-O2.

We've never said that -O3 causes the compiler to adhere more closely
to the language standard or that it should introduce riskier
optimizations.  We could say that.  But then we should discuss it in
those terms: a change in the meaning of -O3.

The obvious analogy to this discussion about whether signed overflow
should be defined is strict aliasing.  Historically we've turned on
-fstrict-aliasing at -O2.  I think it would take a very strong
argument to handle signed overflow differently from strict aliasing.


I also have to note that at least some people appear to be approaching
this discussion as though the only options are to use require -fwrapv
or to assume that signed overflow should be treated as undefined in
all cases.  Those are not the only options on the table, and in fact I
believe that neither option is best.  I believe the best option is
going to be to take an case by case approach to selecting which
optimizations should be enabled by default, and which optimizations
should not be done except via a special extra option (by which I mean
not a -O option, but a -f option).

I appreciate your need to move this discussion along, but I'm not
entirely happy with what I take to be stampeding it by introducing
what I believe would be a completely inappropriate patch to autoconf,
rather than, say, opening a gcc bugzilla problem report for the cases
you feel gcc should handle differently.

You are asserting that most programmers assume -fwrapv, but, except
for your initial example, you are presenting examples which gcc
already does not change.  You are not considering the examples for
which most programmers do not assume -fwrapv, examples like

#define MULT(X) ((X) * 10)
int
foo (int x)
{
  return MULT (x) / 5;
}

With -fwrapv, we must multiply by 10 and then divide by 5.  Without
-fwrapv, we can simply multiply by 2.  A comparison of the generated
assembly for this trivial example may be instructive.


I already took the time to go through all the cases for which gcc
relies on signed overflow being undefined.  I also sent a very
preliminary patch providing warnings for those cases.  I believe that
we will get the best results along those lines, not by introducing an
autoconf patch.

Do you disagree?

Ian

Re: changing "configure" to default to "gcc -g -O2 -fwrapv ..."

[Richard Kenner]

> > But how would that happen here?  If we constant-fold something that would
> > have overflowed by wrapping, we are ELIMINATING a signed overflow, not
> > INTRODUCING one.  Or do I misunderstand what folding we're talking about
> > here?
> 
> http://gcc.gnu.org/PR27116 is what led to the patch.

I think the patch is wrong.  This is not a case where the source contains
"- INT_MIN".  If it did, I think it would be perfectly safe to always fold
it in a wrapping way.

As I understand the issue here, the problem is that we're generating a
negation of a constant present in the source as part of ANOTHER
transformation.  But I'd argue that such should not be generated if the
constant overflows REGARDLESS of the state of -fwrapv: it requires far too
much analysis of whether such a transformation is valid in such case to
bother doing it.

So I think it's correct for nearly all of the places that call negate_expr in
fold to protect that call with a call to negate_expr_p (I note a few seem
missing), but I'd argue that folding the expression "-CST" should
unconditionally do so and that negate_expr_p should return FALSE if an
overflow would occur independently of flag_wrapv and flag_trapv.