Re: FW: How does GCC implement dynamic binding?

[Robert Dewar]

David Daney wrote:

Perhaps you are right, but it would not surprise me if there were 
commercial entities based around FOSS that would provide that type of 
support.


Certainly for instance AdaCore is able to provide this kind of
certification for its customers using its commercial version of
GNAT Pro (an Ada compiler based on GNAT Pro), and perhaps for
example Code Sourcery might be able to provide similar certification
for a product that they provide, but if you are looking for 
certification of some publicly available version, I think you

are out of luck.

It reminds me of a time in 1999, when someone demanded that we provide
Y2K compliance guarantees for the public version of GNAT. Of course I
declined (for one thing I had no way of knowing exactly what he was
using). He was outraged, and said "well in that case I will have to
stop using this version". I explained that this was indeed the case,
and offered the possibility of using the commerical version supported
by us, but that's not he wanted to hear, he wanted to use the freely
available public version (which is fine if it meets someones needs),
but wanted someone to guarantee compliance (which is not fine).

Re: compiling very large functions.

[Robert Dewar]

Kenneth Zadeck wrote:


I actually think that you small talk example is the exception and not
the rule.  I would guess that the vast majority of very large functions
are machine generated simulations where the optimizer most likely
provides little benefit.


Wouldn't it be best to base this discussion on data rather than guesses
as to what "most likely" happens. Seems to me that the first step here
is taking some of these large functions and compiling them with various
optimizations enabled or disabled.

Re: Canonical type nodes, or, comptypes considered harmful

[Robert Dewar]

Doug Gregor wrote:


These are different types. For instance, "int" and "long" are distinct
types in C++, even if both map onto 32-bit integers.


And in Ada, you can have any number of distinct integer types
with identical representations.

Re: comments on getting the most out of multi-core machines

[Robert Dewar]

Howard Chu wrote:

It also somewhat blurs the
distinction between a fully linked executable file and an intermediate 
relocatable object, since executables can also be incrementally 
relinked. It's a real timesaver when you just need to fix one file in a 
very large program.


a proper fix-and-continue functionality would be even more of a
timesaver, maybe that's where the energy should go ...

Re: Threading the compiler

[Robert Dewar]

Geert Bosch wrote:


Given that CPU usage is at 100% now for most jobs, such as
bootstrapping GCC, there is not much room for any improvement
through threading.


Geert, I find this a bit incomprehensible, the whole point
of threading is to increase CPU availability by using
multiple cores.


Even in the best case, large parts of the
compilation will still be serial.
In the non-optimizing case, which is so important for the
compile-debug-edit cycle, almost no parallelism will be possible.


Well that is a completely different issue

Re: strict aliasing benefit examples

[Robert Dewar]

Paolo Bonzini wrote:

for(i = 0;i<*t;i++)
  *f += 1.0;


This one is pretty realistic, especially if you consider C++ and inlining:


Don't you think that a convincing argument here has to be based
on actual timings with and without strict aliasing. It would
be interesting to see cases where that simple-to-understand
argument can be made!

Re: strict aliasing benefit examples

[Robert Dewar]

Richard Kenner wrote:

Since humans have to do a bit of alias analysis when maintaining
or writing code, the extra clarity of pulling things into temporary
variables isn't wasted.


Sorry, I don't follow.  Why should we want to do "a bit of alias analysis"
when maintaining or writing code?  It would seem a far better practice to
leave that to the optimizer and use local variables only when necessary
for clarify.


And while we are at it, write code in C, instead of some ill-defined
variant of it!

Re: Char shifts promoted to int. Why?

[Robert Dewar]

Chris Lattner wrote:

Sorry, but you're incorrect.  While it may be "logical" that shifting  
a value left more bits than its size will give you zero, this is not  
what C specifies. 


I am puzzled, what exactly *does* C specify in this case? I reread
the thread, but it's not clear what the requirement of the standard
here is (as opposed to what programmers might or might not expect,
or what hardware does or does not do).

Re: Char shifts promoted to int. Why?

[Robert Dewar]

Chris Lattner wrote:


C99 says:

The integer promotions are performed on each of the operands. The  
type of the result is
that of the promoted left operand. If the value of the right operand  
is negative or is
greater than or equal to the width of the promoted left operand, the  
behavior is undefined.


Thus, it is undefined.


So the suggested transformation is indeed valid, which is what I
thought, but some seem to be contesting this, though I don't see
on what grounds.

Re: Char shifts promoted to int. Why?

[Robert Dewar]

Chris Lattner wrote:

It only retains the proper semantics when targeting a machine that  
zeros the result of oversized left shifts.  The original question was  
about X86 codegen, which doesn't have this behavior, so it is not valid.


RIght, I see, though it can still be applied in some cases ...


-Chris

Re: Char shifts promoted to int. Why?

[Robert Dewar]

Chris Lattner wrote:

Thus, the transformation is safe in this specific case on i386.   
However, shifting a 32-bit value left by 33 bits would not be safe.


That's the case where the transformation IS safe, since shifting a
32-bit value left by 33 bits gives an undefined result as I understand
things.

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

Brooks Moses wrote:

Now, if your argument is that following the LIA-1 standard will prevent 
optimizations that could otherwise be made if one followed only the C 
standard, that's a reasonable argument, but it should not be couched as 
if it implies that preventing the optimizations would not be following 
the C standard.


I continue to suspect that the gains from this optimization are minimal
to non-existent in practice. Given the requirements in LIA-1, I would
think that taking advantage of overflow being undefined is only 
acceptable if there is very clear quantitative data showing that this

indeed is a significant optimization.

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

Andrew Haley wrote:

Robert Dewar writes:
 > Brooks Moses wrote:
 > 
 > > Now, if your argument is that following the LIA-1 standard will

 > > prevent optimizations that could otherwise be made if one
 > > followed only the C standard, that's a reasonable argument, but
 > > it should not be couched as if it implies that preventing the
 > > optimizations would not be following the C standard.
 > 
 > I continue to suspect that the gains from this optimization are minimal

 > to non-existent in practice. Given the requirements in LIA-1, I would
 > think that taking advantage of overflow being undefined is only 
 > acceptable


That's an interesting use of the passive voice.  Acceptable to whom?


acceptable from a technical perspective. Damaging useability on the
basis of providing better optimization without good data showing that
the optimization is worthwhile seems unjustifiable to me. Compiler
writers overestimate the value of optimizations all the time. To me
it is essential to have data to back up arguments that optimizations
that change behavior are worth while.

For example, putting variables in registers instead of memory most
definitely changes behavior (by making uninitialized variables have
a much more deleterious effect in practice), but is easily justified
since we can easily show that many programs are really substantially
helped by this optimization.


We've already defined `-fwrapv' for people who need nonstandard
arithmetic.


Nonstandard implies that the result does not conform with the standard,
which is not correct. -fwrapv provides semantics that exactly conform
with the C standard.

But how do we know that there is any point to this option? It would
not seem hard to run a set of benchmarks. I don't have access to
helpful examples, but for what I ran, -fwrapv had no detectable
effect on performance. It sure would be nice to get at least ONE
example that is at least semi-realistic where it makes a difference.

When I worked on SPITBOL, people all the time were suggesting
optimizations in letters to the SPITBOL newsletter. I imposed
a rule saying that no one could propose an optimization unless
they could show ONE example program where the optimization could
plausibly save 5% execution time. I never got another suggestion.


I don't see that this is any different from the
interminable strict-aliasing discussion.


Yes, and sadly missing from that discussion is sufficient
concrete data, though indeed there are some examples that
we know of there, so certainly my 5% rule would apply. Even
there I would make strict-aliasing the default (I have argued
stronly for that in the GNAT context, but the back end folks
are sure (without data) that no-strict-aliasing has a
noticeable effect, so it is still the default. In practice
we advise many of our large customers to routinely use
-fno-strict-aliasing, and we have introduced a pragma to
marke individual types to suppress strict aliasing.

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

Andrew Pinski wrote:


I don't have the number of times this shows up or how much it helps but
it does help out on being able to vectorize this loop.


Just to be clear, when I ask for quantitative data, it is precisely
data about "how much it helps". It is always easy enough to show
cases where the optimization does help the code.


All of these do show up in real code, and since loops are now more
important to optimize than anything else, well knowing the number of
iterations is very important.


Using "very" is usually a substitute for actual data, and that appears
to be the case here. What would make me confident that this optimization
is worth while is a message that says"

This test (hopefully one from a realistic example, or at least from a
real benchmark suite, and not just cooked up for demonstration) runs
in X seconds with the optimization and X+Y seconds without on bla
architecture.

That does not seem too much to ask :-)


Thanks,
Andrew Pinski

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

Andrew Haley wrote:

Robert Dewar writes:
 > Andrew Haley wrote:
 > 
 > > We've already defined `-fwrapv' for people who need nonstandard

 > > arithmetic.
 > 
 > Nonstandard implies that the result does not conform with the standard,


I don't think it does; it merely implies that any program which
requires "-fwrapv" for correct execution is not a strictly conforming
program.


OK, well if you say to people

gcc is a nonstandard implementation of C99, most people will read that
to indicate that it is non-conforming, so I suggest avoiding this term.


Andrew.

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

Gabriel Dos Reis wrote:

Andrew Haley <[EMAIL PROTECTED]> writes:

| Robert Dewar writes:
|  > Andrew Haley wrote:
|  > 
|  > > We've already defined `-fwrapv' for people who need nonstandard

|  > > arithmetic.
|  > 
|  > Nonstandard implies that the result does not conform with the standard,
| 
| I don't think it does; it merely implies that any program which

| requires "-fwrapv" for correct execution is not a strictly conforming
| program.

How many useful C programs do you know that are strictly conforming?
Certainly, GCC isn't stritcly conforming.


The other danger in using nonstandard in this peculiar way is that
it is too easy to use or at least think in terms of the argument.

This feature is nonstandard
We want gcc to be standard
Therefore we don't want this feature

which is faulty reasoning in this particular case. The ONLY reason
for doing the optimization is to improve performance, it does not
somehow make gcc more standard to take implement undefined in an
unpredictable manner :-)

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

Andrew Haley wrote:


 > I suspect the actual argument must be somewhere else.

I'm sure it is.  The only purpose of my mail was to clarify what I
meant by "nonstandard", which in this case was "not strictly
conforming".  I didn't intend to imply anything else.


But a compiler that implements wrap around IS strictly conforming.
A program that takes advantage of it is depending on non-standard
semantics, but then so is any program that uses floating-point and
expects it to have IEEE semantics to any extent.

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

Florian Weimer wrote:

* Paolo Bonzini:


Interesting read.  I agree with the proposed fix; however, note that
GCC does not make the result of overflowing signed left-shifts
undefined, exactly because in this case the overflow is relied upon by
too many existing programs


Is this documented somewhere?  Without documentation, it could also be
an oversight (lack of optimization) from a programmer perspective.


It generally seems desirable for me to have a documentation section
which takes every undefined in the standard and says what is done
with it (sort of like Annex M in the documentation for an Ada compiler).

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

Zdenek Dvorak wrote:


IMHO, using loops relying on the behavior of overflow of an
induction variable (*) is an ugly hack and whoever writes such a code
does not deserve for his program to work.


I suspect everyone would agree on this, and in practice I would
guess that

a) there are no programs that rely on this

b) the value of the optimization if any, is probably almost all
from this treatment of induction variables in loops.

Perhaps the proper resolution here is to implement and document
that gcc will wrap except in the case of loop variables (needs
some more careful documentation of course).

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

Joseph S. Myers wrote:

On Tue, 19 Dec 2006, Florian Weimer wrote:


* Paolo Bonzini:


Interesting read.  I agree with the proposed fix; however, note that
GCC does not make the result of overflowing signed left-shifts
undefined, exactly because in this case the overflow is relied upon by
too many existing programs

Is this documented somewhere?  Without documentation, it could also be
an oversight (lack of optimization) from a programmer perspective.


Certainly, in implement-c.texi:

GCC does not use the latitude given in C99 only to treat certain
aspects of signed @samp{<<} as undefined, but this is subject to
change.


That hardly seems sufficient documentation, when documenting undefined,
you had better say what the semantics is. Saying it is not treated as
undefined, and then failing to define it is a bit of a contradiction
in terms :-)


This particular case has the special property that signed << was 
implementation-defined in C90 (DR#081) and became undefined in some cases 
in C99.


We've optimized expressions such as (a*2)/2 on the basis of overflow being 
undefined for a very long time, not just loops.


What is (a*2)/2 optimized to? certainly it has the value a if you wrap, 
so you are not necessarily depending on undefined here.

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

Florian Weimer wrote:


Something like:

GCC does not use the latitude given in C99 only to treat
certain aspects of signed @samp{<<} as undefined: If the right
operand @var{n} is non-negative and less than the width of the
left operand @var{val}, the resulting value @[EMAIL PROTECTED] <<
@var{n}} is guaranteed to be equal to @var{val} times 2 to the
@var{n}th power under 2-complement arithmetic.

would probably settle the issue, but it's unwieldy.


Seems fine to me and completely clear, but in my experience, a lot
of people prefer to infer from examples than to read perfectly
clear defining text, so I would add an example.

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

Paolo Bonzini wrote:

No, it has not.  For example, if a is 0x4000 in a 32 bit type and 
arithmetic wraps, a*2 = -0x8000 (overflow), and hence (a*2)/2 = 
-0x4000 = -1073741824.


Paolo


Yes indeed, my mistake, I was thinking unsigned :-(
and of course signed is the whole point here!

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

Paolo Bonzini wrote:
We've optimized expressions such as (a*2)/2 on the basis of overflow 
being undefined for a very long time, not just loops.
What is (a*2)/2 optimized to? certainly it has the value a if you wrap, 
so you are not necessarily depending on undefined here.


it's interesting that in Ada, intermediate values are allowed to go out
of range, skipping the overflow check (i.e. if intermediate things go
out of range, you are allowed to raise Constraint_Error, but you can
give the right answer instead.

So Ada is allowed to return (a*2)/2 as a for the signed case without
appealing to any undefinedness, and in general (a*b)/c can always
be done with a double length intermediate result (which is probably
the right implementation in C as well).

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

Denis Vlasenko wrote:


I want sane compiler. One in which N-bit integer variables stay exactly N-bit.
Without "magic" N+1 bit which is there "somethimes". a*2/2:
If I say "multiply by 2 and _after that_ divide by 2,
I meant that. Compiler can optimize it any way it wants,
as long as result is the same as unoptimized one.


I am sure others will say this too, but the demand that optimization
not affect behavior is entirely unrealistic and unreasonable. The
whole point of making things undefined in C is to allow compilers
the freedom to optimize. Now that does not mean that one should
always take advantage (my position is that you want to be careful
in taking advantage of undefined and make sure the gain is worth
the surprise), but to say that you should NEVER take advantage
of this would have terrible effects on the code.


Above: v is a signed entity. I expect (v < 0) to be equal to
"most significant bit is set". It's not about standards.
It's about sanity.


Well for sure I don't think you want minus zero to be less than
plus zero on a 1's complement machine, that would not be sane.
Things are never simple!

--
vda

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

Paul Brook wrote:

Compiler can optimize it any way it wants,
as long as result is the same as unoptimized one.


We have an option for that. It's called -O0.

Pretty much all optimization will change the behavior of your program.


Now that's a bit TOO strong a statement, critical optimizations like
register allocation and instruction scheduling will generally not change
the behavior of the program (though the basic decision to put something
in a register will, and *surely* no one suggests avoiding this critical
optimization).

The 
important distinction is whether that difference is observable in valid 
programs. The whole point of langage standards is that they define what 
constitutes a valid program.


Valid programs is too narrow a set, you really do have to pay attention
to normal usage. I very well remember the Burroughs 5500 compiler, which
took advantage of the stack semantics allowed by the standard, but in
fact virtually all Fortran programs of the era assumed static allocation
since that's what every other compiler did. As a consequence the 5500
Fortran was completely useless, one factor that certainly caused
universities I was aassociated with to avoid this machine.

You can argue that signed overflow is an extension that it's worth supporting 
by default. Other people (eg. those interested in autovectorization) will 
argue that it provides useful optimization opportunities. I don't know which 
of these is better, but either what it's a lot different to saying "never 
change the behavior of any program.


Yes, absolutely, I agree with that!

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

Richard B. Kreckel wrote:


By the same token it would be wise to refrain from turning on any
optimization that breaks programs which depend on wrapping signed
integers. Silently breaking LIA-1 semantics is imprudent.


I am not so sure about that conclusion, which I why I would like to
see more data. It maybe that the loop induction optimization *is*
significant, and you must admit it is really really hard to imagine
real world code that depends on wrapping in this context.

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

Andrew Pinski wrote:


Actually they will with multi threaded program, since you can have a case
where it works and now it is broken because one thread has speed up so much it
writes to a variable which had a copy on another thread's stack.  So the 
argument
about it being too strong is wrong because timming matters now a days.  
Instruction
scheduling can cause the same issue as it forces a write too early for another 
thread
to act on.


But the behavior of such programs is typically fundamentally 
non-deterministic. I don't think it is useful to lump in this

kind of change with other functional changes. Remember that
the standard has NOTHING to say about instruction speeds and
even informally, any program depending on relative speeds of
two instruction streams is just TOO far out to consider.


Thanks,
Andrew Pinski

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

Dave Korn wrote:


  Why isn't that just a buggy program with wilful disregard for the use of
correct synchronisation techniques?


Right, I think most people would agree it is.

But for sure, if you consider that making the code go faster is itself
a change in behavior, then obviously all optimization changes the
behavior, but so does any improvement in the compiler in terms of
the unoptimized code generated.



cheers,
  DaveK

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

Paul Brook wrote:

As opposed to a buggy program with wilful disregard for signed overflow 
semantics? ;-)


I know there is a smiley there, but in fact I think it is useful to
distinguish these two cases.

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

Paul Schlie wrote:


As a compromise, I'd vote that no optimizations may alter program behavior
in any way not explicitly diagnosed in each instance of their application.


Sounds reasonable, but it is impossible and impractical! And I think
anyone familiar with compiler technology and optimization technology
understands why this is the case.

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

Andrew Haley wrote:


Is it simply that one error is likely to be more common than another?
Or is there some more fundamental reason?


I think it is more fundamental. Yes, of course any optimization
will change resource utilization (space, time). An optimization
may well make a program larger, which means it no longer fits
in memory, or it may in some unfortunate case slow down the
execution of some program, e.g. due to cache effects from too
much inlining, and the program misses deadlines.

But these effects are very different from optimizations which
change the results in a way permitted by the standard as a
direct result of using the optimization.

For example if we write

  a = b * c + d;

an optimizer may choose to use a fused multiply-add with
subtly different rounding effects

or on the x86, keeping intermediate floats in 80 bits,
certainly permissible from the standard without LIA,
can subtly change results.

I do think this is a useful distinction.

We can't say "don't do any optimization that changes
resource utilization", that would be absurd. We can't
even say, warn when this optimization might change
resource utilization, that would be equally absurd.

But when we have an optimization that changes the
operational semantics of the particular operation
being optimized, we can say:

This change in behavior may be unexpected, or
undesirable, even if allowed by the standard.
Let's be sure the optimization is worth it before
enabling it by default.

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

Zdenek Dvorak wrote:


actually, you do not even need (invalid) multithreaded programs to
realize that register allocation may change behavior of a program.
If the size of the stack is bounded, register allocation may
cause or prevent program from running out of stack, thus turning a
crashing program to non-crashing one or vice versa.


Again, I think it is useful to distinguish functional behavior changes
from changes that come from resource utilization. Yes, optimization
will always change resource utilization. That's the whole point, so
if you include resource utilization as a change in behavior, then
you lose the useful distinction between optimizations like

  a*2 => a+a

which could change the size of an executable

but which of itself is functionally neutral

from optimizations which are not functionally neutral for
programs with undefined or implementation defined semantics
(e.g. fast math).

Note that another possible effect of *any* optimization, is to
change the address of data and code throughout the program, and
of course this could wake up some implementation or buggy
behavior that depended on specific addresses of data or code.
Again, it is useful to exclude these indirect effects.

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

[EMAIL PROTECTED] wrote:

it should be fairly easy to indicate each and every 
undefined/unspecified value/semantic
assumption being applied to both explicitly declared variables and 
implicit intermediate
results of programmer specified expressions and their resulting 
hopefully logically equivalent
replacements; as otherwise arguably the "optimization" has no basis of 
application.


No, it's not fairly easy. If you really think it *is* easy, try it
in some case like the example below and propose a patch.
 
For example:
 
warning: line 12,  int x = a << b ; statement ignored as (int)b expected 
value range is greater
; than the sizeof(a) 
thereby the resulting value is undefined,
; and thereby there's no 
reason to compute the expression
; as (int)x may have any 
value.

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

Gabriel Dos Reis wrote:


I don't believe this particular issue of optimization based on
"undefined behaviour" can be resolved by just telling people "hey
look, the C standard says it is undefined, therefore we can optimize.
And if you're not happy, just tell the compiler not to optimize".
For not all undefined behaviour are equal, and undefined behaviour is
also a latitude given to implementors to better serve their base
users.


Right, and better service is a combination of doing what is expected
and generating fast code, and sometimes the two do conflict, and then
we have to do the best we can to balance the conlicting goals.

My concern is that in achieving this balance, we really need to have
data to show that we are indeed generating significantly faster code.
Compiler writers tend to want to optimize the last instruction out
in any situation, without necessarily showing it is significant to
do so.

Re: -fwrapv enables some optimizations

[Robert Dewar]

Geert Bosch wrote:


This is completely wrong. Making operations undefined is a two-edged
sword. At the one hand, you can make more assumptions, but there's
also the issue that when you want to rewrite expressions, you have
to be more careful to not introduce undefined behavior when there
was none before.


No, I think you miss the point


The canonical example is addition of signed integers. This operation
is associative with -wrapv, but not without.

So
   a = b + C1 + c + C2;
could be written as
   a = b + c + (C1 + C2);
where the constant addition is performed at compile time.
With signed addition overflowing, you can't do any reassociation,
because this might introduce overflows where none existed before.


Yes, but the overflows are harmless given that we know the
code we can generate will actuallly wrap, so it is just fine
to reassociate freely without -fwrapv, since the result will
be the same. Overflow is not an issue. If the final result
has overflowed, then the original program is for sure undefined.
If the final result has not overflowed, then intermediate values
may or may not have overflowed. There are two cases, either the
original canonical order caused overflow, in which case giving
the right result for the overall calculation is fine (though
not required), or it did not, in which case giving the right
result is also fine (and required)


Sometimes I think it is far better to have a default of -fwrapv for
at -O1 and possibly -Os. Sure, this would disable some powerful
optimizations, especially those involving loops, but it would in
practise be very useful to get reasonably good optimization for programs
with minimizing the number of programs with undefined behavior.
Also, it would allow some new optimizations, so total loss of
performance may be quite acceptable.


This is not right, on a machine where in fact addition wraps,
-fwrapv can never enable optimizations that would otherwise not
be possible. I must say when I first read this claim, I had
exactly the same initial reaction as Geert, but then I thought
about it more and realized the claim is indeed correct.


Also, for safety-critical program and certification, it is essential
to be able to reason about program behavior. Limiting the set of
programs with erroneous or undefined execution is essential.


I don't see this at all, you have to prove that you don't have overflows
in any case if the semantics of your program does not expect overflows.
This is what you have to do in any Ada program. I don't see that
enabling -fwrapv makes such proofs easier or harder.


If you want to prove that a program doesn't cause undefined behavior,
it is very helpful signed integer overflow to be defined, even if
it's just implementation defined. That would be a huge selling-point
for GCC.


I don't see this


   -Geert

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

 On 2006-12-21, at 22:19, David Nicol wrote:


It has always seemed to me that floating point comparison could
be standardized to regularize the exponent and ignore the least  
significant

few bits and doing so would save a lot of headaches.


This would be a real nuisance. This myth that you should
never compare fpt numbers for absolute equality is nonsense.
There are lots of algorithms where it is legitimate to
compare for absolute equality (various kinds of iterations
that converge reliably to a single bit pattern for example).

It *is* a problem to have the 80-bit stuff intefering (in fact
Kahan pronounced this a bug in a Fortran compiler. Ada gets
around this by providing the 'Machine attribute that forces
a fpt number to a canonical machine representation in its type,
but it's a bit cumbersome. Note that the use of SSE on the x86
eliminates this problem.

> Marcin Dalecki:


Well actually it wouldn't "save the world". However adding an
op-code implementing: x eqeps y <=> |x - y| < epsilion, would be  
indeed helpful.
Maybe some m-f has already patented it, and that's the reason we  
don't see it

already done. But that's of course only me speculating.


There would be nothing wrong in having such an operation, but
it is not equality!

> David Nicol wrote:


I have argued for "precision" to be included in numeric types in  
other forae
and have been stunned that all except people with a background in  
Chemistry
find the suggestion bizarre and unnecessary; 


if you are stunned by this, you need to study more about
computer arithmetic (btw I have a PhD in chemistry :-))

I realize that GCC is  
not really

a good place to try to shift norms;


especially if the attempt is misguided. Floating-point semantics
in languages have been studied by a lot of experts, they are not
accidental!


Marcin Dalecki:

No that's not sufficient. And a few bit's of precision are really not  
the
center-point of numerical stability of the overall calculation.  
Please look up
as an example a numerical phenomenon which is usually called  
"cancelation" to see

immediately why.


indeed!

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

Marcin Dalecki wrote:

On 2006-12-21, at 23:17, Robert Dewar wrote:


Marcin Dalecki:
Well actually it wouldn't "save the world". However adding an
op-code implementing: x eqeps y <=> |x - y| < epsilion, would be   
indeed helpful.
Maybe some m-f has already patented it, and that's the reason we   
don't see it

already done. But that's of course only me speculating.

There would be nothing wrong in having such an operation, but
it is not equality!


Of course I didn't think about a substitute for ==. Not! However I think
that checks for |x-y| < epsilion, could be really given a significant  
speed edge

if done in a single go in hardware.


I don't see this as viable, the choice of epsilon is too application
dependent.

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

Marcin Dalecki wrote:


Of course I didn't think about a substitute for ==. Not! However I think
that checks for |x-y| < epsilion, could be really given a significant  
speed edge

if done in a single go in hardware.


One thing to ponder here is that "thinks" like this are what lead
to CISC instruction messes. It just seems obvious to people that
it will help efficiency to have highly specialized instructions,
but in practice they gum up the architecture with junk, and a
careful analysis shows that the actual gain is small at best.
How many applications spend a significant amount of time doing
such an epsilon test -- best guess: none.

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

Paul Brook wrote:

On Friday 22 December 2006 00:58, Denis Vlasenko wrote:

On Tuesday 19 December 2006 23:39, Denis Vlasenko wrote:

There are a lot of 100.00% safe optimizations which gcc
can do. Value range propagation for bitwise operations, for one

Or this, absolutely typical C code. i386 arch can compare
16 bits at a time here (luckily, no alighment worries on this arch):

int f(char *p)
{
if (p[0] == 1 && p[1] == 2) return 1;
return 0;
}


Definitely not 100% safe. p may point to memory that is sensitive to the 
access width and/or number of accesses. (ie. memory mapped IO).


A program that depends on this is plain wrong. There is no guarantee
that memory references are as they appear in the program. For a
non-volatile variable, any such optimization is valid. For instance
if the flow can be used to prove that p[0] is already 1, then there
is no need to repeat the read.


Paul

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

Paul Brook wrote:


Who says the optimisation is valid? The language standard?

The example was given as something that's 100% safe to optimize. I'm 
disagreeing with that assertion. The use I describe isn't that unlikely if 
the code was written by someone with poor knowledge of C.


My point is that it's not that hard to invent plausible code that "breaks" 
when pretty much any transformation is applied. We have to decide how close 
to the standard we want to fly.


I did not find that plausible at all, for someone to depend on memory
mapped references without using volatile is indeed such junk code that
we don't need to care about it.

"Optimization should never change the behavior of a valid program" is useful 
definition because it forces you to define what constitutes a valid program.


No, no, let's not start calling these programs that violate the standard
valid. That's going much too far. Also, sometimes code is inherently
non-deterministic, so you have to be careful talking about change of
behavior.

"Optimization should never result in violating the required semantics of
a valid (standard) C program"

is of course criterion 1

Criterion 2 is something like "Optimization should not cause non-valid
non-standard programs to fail as a result of using a common idiom, which
though non-standard is generally expected to "work", unless the 
optimization can be demonstrated to be valuable enough to be worth

generating the effective incompatibility with expected practice"

is a half baked statement of criterion 2 (and it is not so easy to
bake this one!)

There's actually a much better reason why the transformation is not safe. 
Consider a data structure where a byte of 1 indicates the end of the object. 
Under normal circumstances short-circuiting of the && operator prevents 
anything bad happening. If you merge the two accesses you've just read past 
the end of the object and all kinds of bad things may happen (eg. a 
segfault).


You may well know that it is safe to go one past the last object 
(generally this will be the case, because of the strange semantics

of being allowed to address past the last byte). You do indeed have
to be careful of this

P.S. I think I'm repeating myself now, so this is the last time I intend to 
comment on this thread.


OK!

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

Dave Korn wrote:

On 22 December 2006 00:59, Denis Vlasenko wrote:



Or this, absolutely typical C code. i386 arch can compare
16 bits at a time here (luckily, no alighment worries on this arch):


  Whaddaya mean, no alignment worries?  Misaligned accesses *kill* your
performance!


is it really worse to do one unaligned 16-bit read, than two separate
8-bit reads? I am surprised ... and of course you have the gain from
shorter code, reducing i-cache pressure.


  I know this doesn't affect correctness, but the coder might well have known
that the pointer is unaligned and written two separate byte-sized accesses on
purpose; volatile isn't the answer because it's too extreme, there's nothing
wrong with caching these values in registers and they don't spontaneously
change on us.

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

Andrew Pinski wrote:

On Fri, 2006-12-22 at 17:08 +, Dave Korn wrote:
Misaligned accesses *kill* your performance! 


Maybe on x86, but on PPC, at least for the (current) Cell's PPU
misaligned accesses for most cases unaligned are optimal.


is that true across cache boundaries?


Thanks,
Andrew Pinski

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

[Robert Dewar]

Daniel Berlin wrote:


I'm sure no matter what argument i come up with, you'll just explain it away.
The reality is the majority of our users seem to care more about
whether they have to write "typename" in front of certain declarations
than they do about signed integer overflow.


I have no idea how you know this, to me ten reports seems a lot for
something like this.

Re: Compiler loop optimizations

[Robert Dewar]

Ian Lance Taylor wrote:

Christian Sturn <[EMAIL PROTECTED]> writes:


Thank you for your answer. Is there any chance to have gcc dump out
an optimized code in the form the source level language, e.g. can I run
gcc with some optimizations and see how the compiler modified my C
source code? 


You can get an approximation using -fdump-tree-*.  See the
documentation.  That is usually enough to see how the optimizations
affected your code.

There is no support for dumping actual valid source code, though, and
it is unlikely that there ever will be.


And indeed it is not in general possible, there are many optimizations
that cannot be expressed in valid C.


Ian

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

[Robert Dewar]

Paul Eggert wrote:


In practice, I expect that most C programmers probably
assume wrapv semantics, if only unconsciously.  The minimal
C Standard may not entitle them to that assumption, but they
assume it anyway.  Part of this is the Java influence no
doubt.  Sorry, but that is just the way the world goes.


That's an interesting point, I suspect it is indeed the
case that more C programmers will assume that C matches Java
semantics (indeed in a sense Java derived its semantics
from C practice).

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

[Robert Dewar]

Marc Espie wrote:


Specifically, because we value reliability over speed and strict
standard conformance...


Still as a long term goal, it would be good to try to have your
C programs written in C, and not some ill-defined dialect thereof!

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

[Robert Dewar]

Richard Kenner wrote:

Specifically, because we value reliability over speed and strict
standard conformance...


Seems to me that programs that strictly meet the standard of the language
they are written in would be more reliable than programs that are written
in some ill-defined language.


In the long run, sure, but during the transition, which can be
very long, this is only an academic observation. After all in
the Ada world, we advise many of our big customers to use
-fno-strict-aliasing as a matter of course to avoid similar
aliasing problems in Ada.

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

[Robert Dewar]

Richard Kenner wrote:

which clearly says LIA-1 isn't a requirement - notice "if" in the
second setence.
H.1 makes it clear that the entire Annex H doesn't add any extra rule
to the language but merely describes what C is in regard to LIA-1.
H.2 doubly makes it clear that C as it defined isn't LIA-1
- again, notice "if" in H.2p1.


That's the way I read it too.  Indeed, perhaps -fwrapv really ought to
be called -flia-1?


Is a smiley missing here?

If not, this is seriously confused, lia-1 is MUCH more than just
wrapping integer types.

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

[Robert Dewar]

Paul Eggert wrote:

Nor would I relish the prospect of keeping wrapv assumptions out of
GCC as other developers make further contributions, as the wrapv
assumption is so natural and pervasive.

It's neither natural not pervasive to me!  I would never write code
that way


That's great, but GCC has had many other hands stirring the pot.
I daresay a careful scan would come up with many other examples of
undefined behavior due to signed integer overflow.  (No doubt
you'll be appalled by them as well, but there they are.)


Not so appalling really, given that relying on wrapping is as
has been pointed out in this thread, the most natural and
convenient way of testing for overflow. It is really *quite*
difficult to test for overflow while avoiding overflow, and
this is something that is probably not in the lexicon of
many C programmers.

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

[Robert Dewar]

Richard Kenner wrote:

Not so appalling really, given that relying on wrapping is as has
been pointed out in this thread, the most natural and convenient way
of testing for overflow. It is really *quite* difficult to test for
overflow while avoiding overflow, and this is something that is
probably not in the lexicon of many C programmers.


I guess that's true even in GCC.  I looked at the OVERFLOW_SUM_SIGN macro in
fold-const.c.  But on the positive side, the test is isolated in one place
and so is easy to fix.


It would make sense as was suggested earlier to define standard library
routines or macros for overflow detection, and indeed this would be a
useful and appropriate addition to the standard


Moreover, as was said earlier in this thread, although it's hard to formally
define the subset, it's hard to see how any of the optimizations proposed
that take advantage of undefined overflow would, in pratice, actually break
this idiom.

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

[Robert Dewar]

Gabriel Dos Reis wrote:


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.


My inclination is to skip the warning for the loop
induction variable case. I think this will generate
lots of false positives, and almost no useful
warnings (I still think this is the one and only
case where the undefined optimization should be done,
in fact I think it would be useful to have a switch
that says

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

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

[Robert Dewar]

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.

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

[Robert Dewar]

Richard Kenner wrote:

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


Unfortunately, comparisons are the trickiest case because you have to
be careful to avoid deleting a comparison that exists to see if overflow
occured: this is perhaps the most common place where wrapping is assumed.


Note incidentally regarding Fortran that testing for overflow is
at least as difficult in Fortran as in C (unless new stuff has been
added to Fortran since my Fortran days, which is certainly possible).

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

[Robert Dewar]

Paul Eggert wrote:


For writing new code, it's easy: the C standard is all
that should be assumed.  Old code should be modified, as
time allows, to be consistent with that standard.


This may be the policy of the GCC developers for the code
they maintain, but it's not a realistic policy for
everybody, and GCC shouldn't insist on it, or even recommend
it, for everybody.  I certainly can't assume it for the code
I help maintain, as the minimal GCC standard is far too
restrictive.


Now that's extreme, it's one thing to say that existing
code may have bad assumptions, it is quite another to
disagree with a policy that all code should be in C,
and that when we find code that strays into undefined
territory it should be fixed. If nothing else it is
important for maintenance that everyone know what
language they are writing in.

Of course there is a way out that satisfies both
sides here, and that is to declare that gcc code
should adhere to the standard *including* LIA
and then make sure the default mode of gcc is
LIA compliant.

Then we

a) have a well defined language
b) have a language that is standardized
c) stay clear of undefinedness

For gcc tools themselves, I suspect the possible
loss in performance is unmeasurable, and it
resolves entirely (at least for the wrapping
issue) the tension between lets-write-standard-stuff
and lets-write-traditional-stuff.

By the way, does traditional C really assume this? Is
it the case that the original K&R document guarantees
wrapping, or is what you meant here "traditional C
compilers". There is quite a difference!

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

[Robert Dewar]

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.


But also note that my position also is that we, as much as possible, should
allow these "broken" legacy codes to continue to work properly despite that
feeling, unless we have a specific case (such as the loop cases) where the
benefits of losing the optimization are quite high and the likelihood that
we'll break code is very low.


Yes, I agree with this

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

[Robert Dewar]

Andrew Pinski wrote:

It does buy you something for code like:

if (a - 10 < 20)

Well that particular example is far fetched in code that people
expect to run efficiently, but with a bit of effort you could
come up with a more realistic example.

Compilers are always full of such optimizations which are simple to do
and get put in without any sound basis for determining that they actually
help. 

Now if they don't change semantics, then unhelpful optimizations (by this
I mean optimizations which don't in practice help real applications), are
only slightly damaging (they damage maintainability and reliability by
creating additional unnecessary special cases).

But if they are NOT semantically neutral in terms of expected usage, then
the burden should be much higher.

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.

You say "I don't want to see this optimization removed", why not?
The answer should hopefully be something like

because test # 5 in benchmark suite xxx takes a 3% hit

or even better

awk processing expressions like bla bla takes an n% hit

However, I suspect the real answer is

"it's a neat optimization, I did it, and it can only help, so why not
leave it in"

And that's to me not good enough for optimziations that break existing
programs.

Note that if (a - 10 < 20)

in the presence of wrap around semantics means something like

   if (a < 30 && a > minint + 9) ...

and perhaps that was exactly what was meant!

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

[Robert Dewar]

Gaby said

K&R C leaves arithmetic overflow undefined (except for unsigned
types), in the sense that you get whatever the underlying hardware
gives you.  If it traps, you get trapped.  If it wraps, you get wrapped.

Is that really what the K&R book says, or just what compilers typically
did? My memory is that the K&R book leaves it undefined period, but it's
a long time since I read it!

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

[Robert Dewar]

(first, sorry for breaking the thread, pilot error on my part)
Here is the message again properly threaded. The other broken
thread by dewar's evil twin can be discarded.

Andrew Pinski wrote:


It does buy you something for code like:

if (a - 10 < 20)


 Well that particular example is far fetched in code that people
 expect to run efficiently, but with a bit of effort you could
 come up with a more realistic example.

 Compilers are always full of such optimizations which are simple to do
 and get put in without any sound basis for determining that they actually
 help.

 Now if they don't change semantics, then unhelpful optimizations (by this
 I mean optimizations which don't in practice help real applications), are
 only slightly damaging (they damage maintainability and reliability by
 creating additional unnecessary special cases).

 But if they are NOT semantically neutral in terms of expected usage, then
 the burden should be much higher.

 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.

 You say "I don't want to see this optimization removed", why not?
 The answer should hopefully be something like

   because test # 5 in benchmark suite xxx takes a 3% hit

 or even better

   awk processing expressions like bla bla takes an n% hit

 However, I suspect the real answer is

 "it's a neat optimization, I did it, and it can only help. I don't know
 if it really helps, but I can concoct an example where it would help,
 so why not leave it in, every little bit helps when it comes to high
 performance.

 And that's to me not good enough for optimziations that break existing
 programs.

 Note that

   if (a - 10 < 20)

 in the presence of wrap around semantics means something like

if (a < 30 && a > minint + 9) ...

 and perhaps that was exactly what was meant!

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

[Robert Dewar]

(again I apologize for breaking the thread),
Here is the reply I sent properly threaded

Gaby said

> K&R C leaves arithmetic overflow undefined (except for unsigned
> types), in the sense that you get whatever the underlying hardware
> gives you.  If it traps, you get trapped.  If it wraps, you get > 
wrapped.


Is that really what the K&R book says, or just what compilers typically
did? My memory is that the K&R book leaves it undefined period, but it's
a long time since I read it!

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

[Robert Dewar]

Richard Kenner wrote:


I found my copy of K&R (Second Edition).  Page 200: "The handling of overflow,
divide check, and other exceptions in expression evaluation is not defined
by the language.  Most existing implementations of C ignore overflow in
evaluation of signed integral expressions and assignments, but this behavior
is not guaranteed."


OK, that's what I remembered, so in fact the new C standard has changed
nothing from a definitional point of view, it is just that people got
in the habit of ignoring the definition and going with what the 
compiler(s) happened to do.

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 ..."

[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 ..."

[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 ..."

[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 ..."

[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 ..."

[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 ..."

[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 ..."

[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 ..."

[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 ..."

[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 ..."

[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 ..."

[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: 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 ..."

[Robert Dewar]

Richard Kenner wrote:

the seemingly prevalent attitude "but it is undefined; but it is not
C" is the opinion of the majority of middle-end maintainers.


Does anybody DISAGREE with that "attitude"?  It isn't valid C to assume that
signed overflow wraps.  I've heard nobody argue that it is.  The question
is how far we go in supporting existing code that's broken in this way.


Well we all understand that the official language definition of C,
starting with K&R first edition, and continuing into the successive
C standards, says that overflow is undefined or machine dependent.

That's not in doubt

However, I am not willing to agree with the notion that code that
does not follow this rule is "broken". It is that attitude which
can lead to inappropriate decisions, instead we should simply say,
in a less judgmental mode, that the code is not strictly standard.
We should also recognize that many (most? nearly all?) large C
programs are in practice in this non-standard category.

In practice, ANY compiler has to go beyond what the standard says
to produce a usable product. The objective of a C compiler is not
simply to conform to the standard, but rather to be a useful tool
for use by C programmers.

With C (and in fact with any language, even a language perceived
to be fiercely standardized like Ada), it is the case that these
two things are not quite the same. For instance in Ada, the set
of representation clauses that must be accepted according to the
standard is fairly small. Tight packing of 3-bit element arrays
for example is not required. But in practice many Ada programs
require support beyond this minimal subset (and indeed we have
users who depend on 3-bit tight packing). Sure we can lecture
them on standard requirements, but GNAT is more useful to them
if we support this optional feature, even if it results in far
less efficient code for some cases (the standard would allow
such components to use 4-bits resulting in much more efficien
code).

When it comes to erroneous and bounded error cases, a compiler
could be maximally unfriendly. For example, in the GNAT binder
there is an option -p (for pessimistic), that says "choose the
worst possible elaboration order, consistent with the standard
requirements". It is a useful option for checking portability
of your code. It would be 100% standards conforming to make
the -p switch the default and only setting, but it would make
GNAT much less useful, since many large programs end up making
assumptions about elaboration order (basically they set things
up to work with some particular compiler).

Again in the Ada context, there are cases where efficiency and
usability conflict. For example, suppose you use an address
clause to position a variable at a specified address, and this
address is misaligned. That's erroneous (undefined in C-speak).
We are allowed to do anything, e.g. delete the system disk,
and the user cannot officially complain. Unofficially that
user is going to be hopping mad. In practice we find that only
a very small number of our users are maximum efficiency oriented
(some of them are happy to consider moving to Java even if it
costs them a factor of 10 in efficiency as an extreme case).
So in the address clause case, we by default generate checking
code that raises Program_Error if the address is misaligned.
That's inefficient, and unnecessary. It can be turned off, but
by default it's on even at the highest optimization level.

By using the word "broken", you are implicitly criticizing
the code, and contributing to an environment where compiler
writers are a little too ready in my view to write off the
programmers of such "broken" code as incompetent, and not
worth worrying about. That can lead to the wrong balance
of decisions in tricky trade off cases.

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

[Robert Dewar]

Geert Bosch wrote:


As undefined execution can result in arbitrary badness,
this is really at odds with the increasing need for many
programs to be secure. Since it is almost impossible to
prove that programs do not have signed integer overflow,


That seems a bit pessimistic, given the work Praxis
has done in the area of proving SPARK programs exception
free. Potentially these same techniques could work with
programs written in a suitable subset of C (and for
highly secure programs, you would want to use such a
subset in any case).

Still, in practical terms, it is true that overflow
being undefined is unpleasant. In Ada terms, it would
have seemed better in the C standard to reign in the
effect of overflow, for instance, merely saying that
the result is an implementation defined value of the
type, or the program is terminated. Any other outcome
seems unreasonable, and in practice unlikely.

The important thing is to stop the optimizer from
reasoning arbitrary deeply from lack of overflow.

For example if we have

   if (Password == Expected_Password)
   delete_system_disk;
   else
   xxx

and the optimizer figures out that xxx will unconditionally
cause signed integer overflow (presumably due to some bug),
we don't want the optimizer saying

"hmm, if that check is false, the result is undefined, so
I can do anything I like, for anything I will choose to
call delete_system_disk, so I can legitimately remove
the check on the password being correct."

This kind of back propagation, while strictly allowed
by the standard, seems totally unaccpetable to me. The
trouble is (we have been through this in some detail in
the Ada standardization world), it is hard to define
exactly and formally what you mean by "this kind of
back propagation".

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

[Robert Dewar]

Andrew Pinski wrote:


Look at Fortran argument aliasing, we get almost no bugs about that
undefinedness.  We have an option to change the way argument aliasing
works, in the same way we have an option for signed overflow.  I don't
see why overflow will be any different from argument aliasing.


Well you should see :-)

The point is that in practice many C compilers have implemented wrapping
in the past, and large bodies of C code and the C knowledge base have
developed assuming (correctly in practice) that wrapping could be relied
on. I don't think you can begin to make the same statement for Fortran
argument aliasing (and I speak as someone who developed hundreds of
thousands of lines of Fortran in the early days -- late 60's and early
70's).


Maybe the problem is that C (and C++) developers don't know the language
they writing in and expect anything to work they wrote. 


That's not right, and I worry that this attitud stands in the way of
getting the right compromise approach. In fact a lot of competent C
programmers know the language pretty well, but they know the language
that is used and works (quite portably even) in practice, not the
language of the standard (which in this case, if you take undefined
at its worse literally) is a difficult language to write in, when
it comes to checking for overflow, as has been clear from the discussion 
in this thread.



I think this is
a problem with the teaching of C (and C++) today and it is hard for us
to fix that issue.  We can try educate people by adding we treat signed
overflow as undefined in the documentation in more obvious place but
this is not going to help in general as developers don't read the docs.


Education won't help deal with large bodies of legacy C that are written
with wrapping assumed (including as we have seen, gcc itself, and other
components of the gnu system). Over time such code can be "fixed", but
it is more likely that people will just resort to fwrapv in practice,
which seems non-optimal to me (I am pretty sure that a moderated
intermediate position between overflow-always-undefined and
overflow-always-wraps can be devised which will in practice
work out fine on the efficiency and portability sides).

In terms of reading the documents, warning messages (and error messages
where possible) are probably more help in teaching the fine details of
the language, and I think everyone agrees that where possible, it would
be a good thing if gcc could warn that it was taking advantage of
"knowing" that signed overflow cannot occur (i.e. should not occur) in
a given situation.


The problem with the current signed overflow undefined optimizations is
that conflict in some are wrapping, others are saturation (most of the
VRP and a-'0'>9) and then more are extending (a*10/5).


Yes, and you can't paint them all with a broadbrush. If you look at the
last one for instance (a*10/5) it's a perfectly reasonable optimization
to optimize this to a*2, and indeed Ada introduces a special rule for
intermediate results which allow them to be "correct" instead of
overflowing precisely to allow this optimization (and to allow the more
general use of double precision intermediate result for computing 
a*b/c). Interestingly, this special Ada rule does introduce some

degree of non-portability, but there is often a trade-off between
portability and efficiency.


Thanks,
Andrew Pinski

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

[Robert Dewar]

Ian Lance Taylor wrote:


I don't think -frisky is a good name for that option.  A better name
would be -fstrict.


or perhaps -fstandard

which says "my program is 100% compliant ISO C. please mr. compiler
make any assumptions you like based on knowing this is the case. If
my claim that I am 100% compliant is wrong, you may punish me by
doing arbitrary horrible things to my code".

P.S. I won't mind if you warn me about these horrible things, but
I won't insist you do so, or blame you if you cannot.

Then all those who know ISO C, and of course would never dream of
writing anything that is non-conforming can use this switch and
know that the compiler will not be fettered by worrying about other
ignorant programmers junk code.

Furthermore, once this switch is on, the compiler writers will know
that the compiler need not worry, and can really go to town with all
sorts of amazing optimizations based on this assumption.

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

[Robert Dewar]

Richard Guenther wrote:

On 1/1/07, Geert Bosch <[EMAIL PROTECTED]> wrote:

 specfp.


I would support the proposal to enable -fwrapv for -O[01], but
not for -O2 as that is supposed to be "optimize for speed" and
as -O3 is not widely used to optimize for speed (in fact it may
make code slower).  I'm undecided for -Os but care less about it.


I think it is a bad idea for the optimization levels to deal with
anything other than optimization. -fwrapv is not about optimization,
it is about changing the language semantics.

So this proposal would be tantamount to implementing a different
language at -O1 and -O2, and having -O2 change the formal
semantic interpretation of the program. That seems a very
bad idea to me.

It is one thing to have different optimization levels do different
amounts of optimization that in practice may have more or less
effect on non-standard programs. It is quite another to guarantee
at a formal semantic level wrapping at -O1 and not -O2.

If we decide to avoid some optimizations at -O1 in this area,
that's fine, but it should not be done by enabling -fwrapv as
one of the (presumably documented) flags included in -O1.

Instead I would just do this silently without the guarantee.

And I continue to favor the compromise approach where loop
optimization can use undefinedness of overflow in dealing
with loop invariants, but we don't by default take advantage
of undefinedess elsewhere.

Then we have two switches:

-fstandard

which allows all optimizations (name can be changed, I
don't care about the name)

-fwrapv

which changes the semantics to require wrapping in
all cases (including loops)

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

[Robert Dewar]

Richard Kenner wrote:

Then we have two switches:

-fstandard

which allows all optimizations (name can be changed, I
don't care about the name)

-fwrapv

which changes the semantics to require wrapping in
all cases (including loops)


What about -fno-wrapv for the first?


Possible .. my view was that it is probably not necessary
to distinguish the various subcases which arise now or in
the future of aggressive optimization opportunities based
on assumption of strict standard semantics.

For example, for me in -fstandard, I would tolerate the
"dewar password check example" being optimized to remove
the password check.

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

[Robert Dewar]

Richard Kenner wrote:


What about -fno-wrapv for the first?


Actually I don't like this.

Why? Because it seems weird to have a flag that you
can turn on and off, but the default is neither on
nor off.

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

[Robert Dewar]

Paul Schlie wrote:


So this proposal would be tantamount to implementing a different
language at -O1 and -O2, and having -O2 change the formal
semantic interpretation of the program. That seems a very
bad idea to me.
...


Yes, it would be laudable for GCC to adopt the principle that whatever
language semantics are chosen in absents of optimization should be
preserved through -O2 by default; although may be explicitly overridden
as may be desired by the user.


Note Paul that I think you may be confusing what I say, when I talk
about language semantics, I am talking about the formal semantics of
the language, which may well have non-deterministic, undefined, or
implementation defined elements. I am NOT talking about preserving
observed behavior. You have rather consistently confused the two.


Further as this may be target specific, for target machine implementations
which inherently support trapping on overflow (or null pointer dereference);
GCC may correspondingly then enable through -O2 optimizations presuming the
same; but by principle not otherwise for targets for which GCC does not
factually support these semantics.


No, that's completely wrong, overflow is undefined in the semantics, so
preserving undefined semantics has nothing whatever with preserving
observed behavior for these programs with undefined semantics. Here
is exactly where you are confusing behavior with semantics.

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

[Robert Dewar]

Richard Guenther wrote:


We do that with -fstrict-aliasing, which also changes language semantics.
-fstrict-aliasing is disabled for -O0 and -O1 and enabled for -O[23s].


Yes, and as others have said, this is a bad precedent, and should
not be followed further. Inclusion of -fwrapv would be much worse,
since this has clearly and precisely defined semantics. In the
case of -fno-strict-aliasing, it is more like disabling an
optimization, since as far as I know there is no clear semantic
meaning for this flag (i.e. a meaning that could be expressed
formally at the level of the standard easily).


How do these switches implement your proposal?  "All optimiations" sounds
like the -fno-wrapv case we have now.


In a couple of ways:

First it can include semantics other than wrapping
Second, it allows completely unfettered optimization (see
password example), which I think no one would want to do
by default.


Richard.

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

[Robert Dewar]

Richard Guenther wrote:

On 1/2/07, Richard Kenner <[EMAIL PROTECTED]> wrote:

We do that with -fstrict-aliasing, which also changes language semantics.

Well, yes, but not quite in the same way.  Indeed it's rather hard to
describe in what way it changes the language semantics but easier to
describe the effect it has on optimization.  I think -fwrapv is the other
way around.


Well, while the effect of -fstrict-aliasing is hard to describe (TBAA
_is_ a complex
part of the standard), -fno-strict-aliasing rules are simple.  All
loads and stores
alias each other if they cannot be proven not to alias by points-to analysis.


That's an implementation oriented analysis, and indeed it is easy
to say at the implementation level what this means. What is not
easy is to describe the formal semantics of the resulting language
at the level of the standard.


Richard.

Re: Autoconf manual's coverage of signed integer overflow & portability

[Robert Dewar]

Richard Kenner wrote:

A few comments:


Many portable C programs assume that signed integer overflow wraps around
reliably using two's complement arithmetic.


I'd replace "portable C programs" with "widely-used C programs".  The normal
use of "portable" means that it conforms to the standard.


Actually the use of portable here is quite appropriate, it emphasizes
that such programs in general are pretty portable *despite* the fact
that they do not conform to the standard.

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

[Robert Dewar]

Laurent GUERBY wrote:

On Sun, 2006-12-31 at 12:04 -0500, Robert Dewar wrote:

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?)


Is the AAMP backend available somewhere?


Only as a GNAT Pro distribution (it requires a special proprietary
version of the AAMP operating system to run).


Laurent

Re: compile time enforcement of exception specification

[Robert Dewar]

James Dennett wrote:


There has been much debate, and a large fraction of those
involved feel that static checking of exceptions in C++ is
*not* an improvement from the current situation.  There
has also been much written on the weaknesses of the Java
approach.

Note: I'm not expressing my personal opinion above on
static vs. dynamic checking.  Just noting that what you
feel is "obviously an improvement" is controversial.


It is interesting to note that Ada, a language that
implemented exception handling back in the early 80's,
debated this issue and also decided that it was
undesirable to introduce this feature.

Probably it could make good sense in a small subset
of one of these languages, but in the full language
context it is dubious.



Wouldn't an option to g++ be only helpful here?


I think it would be inadvisable, g++ should not be in
the business of second guessing well discussed language
design decisions and generating variants by introducing
features unlikely to ever be accepted by the standard.

Re: Miscompilation of remainder expressions

[Robert Dewar]

It's interesting that the same issue arose with GNAT, but
we had no option to ignore the special case, since one of
the official Ada validation test programs tested this case,
and indeed as you see below there is a special test:


function q (a, b : integer) return integer is
begin
   return a rem b;
end;


generates

Source recreated from tree for q (body)
---


function q (a : integer; b : integer) return integer is
begin
   [constraint_error when
 b = 0
 "divide by zero"]
   return integer((if b = -1 then 0 else a rem b));
end q;

And indeed this is a nasty hit in efficiency, though in
practice the wide spread use of integer types with
restricted ranges means that most of the time you
know for example that the divisor cannot be negative.

Re: Miscompilation of remainder expressions

[Robert Dewar]

Roberto Bagnara wrote:

Reading the thread "Autoconf manual's coverage of signed integer
overflow & portability" I was horrified to discover about GCC's
miscompilation of the remainder expression that causes INT_MIN % -1
to cause a SIGFPE on CPUs of the i386 family.  Are there plans to
fix this bug (which, to me, looks quite serious)?
All the best,

Roberto

P.S. I checked whether this bug affects my code and it does.
  Before yesterday I was completely unsuspecting of such
  a fundamental flaw... I wonder how many know about it.


It's truly amazing for real code to be computing remainders
in this domain ... seems a bad idea to me, since very few
people are comfortably aware of what remainder means for
such cases.

Re: Miscompilation of remainder expressions

[Robert Dewar]

Roberto Bagnara wrote:

Reading the thread "Autoconf manual's coverage of signed integer
overflow & portability" I was horrified to discover about GCC's
miscompilation of the remainder expression that causes INT_MIN % -1
to cause a SIGFPE on CPUs of the i386 family.  Are there plans to
fix this bug (which, to me, looks quite serious)?


Seems ultra-non-serious to me, hard to believe this case appears
in real code, despite surprising claim by Roberto.

Re: Miscompilation of remainder expressions

[Robert Dewar]

Roberto Bagnara wrote:

Andrew Haley wrote:

Roberto Bagnara writes:
 > 
 > Reading the thread "Autoconf manual's coverage of signed integer

 > overflow & portability" I was horrified to discover about GCC's
 > miscompilation of the remainder expression that causes INT_MIN % -1
 > to cause a SIGFPE on CPUs of the i386 family.  Are there plans to
 > fix this bug (which, to me, looks quite serious)?

No, there aren't.  It would make more sense for you to wrap % in some
code that checks for this, rather than for us to slow down every division
for this one special case.


With all due respect, I must say I am shocked.  I always thought
(and taught) that we, Free Software people, value standard conformance
and getting things right.  Now we have a bug that can shut down
airplanes 


Please do not indulge in excessive rhetoric, planes do not get
shut down by compiler bugs. If you really think that the integrity
of avionics software depends on bug free compilers you have no
idea what you are talking about (I would guess you are for
example unfamiliar with DO-178B certification).

Yes, it's a bug, is it a serious bug, no? Will real software
be affected? no. Indeed I find any program that actually
does this remainder operation in practice to be highly
suspect.


A final remark: I think that today the problem is safety, not speed.
I don't think doing the right thing for remainder expression will
have such a high cost with the help of the optimizer and, maybe,
assistance from the kernel.  But even if the cost turns out to be high,
the actual state of things is unacceptable: mentioning the bug prominently
in the documentation, trying to change the standard, ..., whatever;
but not leaving things as they are.


Yes, it should probably be fixed, but making a major fuss about
it seems peculiar at best. I think it is perfectly reasonable
for you to propose a patch to fix this if you are specially
concerned, but don't expect the community to rush to fix this
particular bug at high priority in response to this complaint.

There are lots of known bugs far more important than this one.

Re: Miscompilation of remainder expressions

[Robert Dewar]

Roberto Bagnara wrote:


To the point that, when a/b is not representable, raising SIGFPE
for a%b is standard conformant behavior?


possibly so ..


Note however that I am not saying that the standard is not defective.
Who knows how to write and submit C/C++ standard defect reports?
Let us do that, assuming that such a report has not been submitted
already.


not clear that this is a defect, I would find it quite reasonable
for the C standard to recognize this anticipatable case, and decide
that a%b is undefined if a/b is undefined.

Re: Miscompilation of remainder expressions

[Robert Dewar]

Gabriel Paubert wrote:
\

No, because the instruction has actually two result values:

- the remainder, which you could safely set to zero (not 1!)

- the quotient, which is affected by the overflow and there may be
  compiler and languages that rely on the exception being generated.


But the division is undefined, programs have no right to
rely on an exception being generated.

Re: Miscompilation of remainder expressions

[Robert Dewar]

David Daney wrote:

Roberto Bagnara wrote:


Everyone knows that dividing a number by -1 or 1 gives
a 0 remainder.  To the contrary, no one expects a%b to
raise SIFPE when b != 0.



On the contrary, since the beginning of time SIGFPE has been generated 
on GCC/x86/linux under these conditions.  This is wildly known.


Just because you just found out about it does not mean that 'no one' 
expects it.


Indeed, I would never write this expression expecting the result to
be reliably zero, since x86 chips have treated this as a divide by
zero since the beginning of time (well 1981 :-)), a SIGFPE is quite
expected! So I guess Roberto's "no one" does not include me :-)


David Daney

Re: Miscompilation of remainder expressions

[Robert Dewar]

Dave Korn wrote:

On 16 January 2007 18:23, Robert Dewar wrote:


Gabriel Paubert wrote:
\

No, because the instruction has actually two result values:

- the remainder, which you could safely set to zero (not 1!)

- the quotient, which is affected by the overflow and there may be
  compiler and languages that rely on the exception being generated.

But the division is undefined, programs have no right to
rely on an exception being generated.


  It really depends whether you think of the % operator as being an atomic
mathematical operation, or a compound function involving real division and
multiplication and subtraction.  I think the wording of the standard says only
that the inequality "(a/b)*b + a%b == a" does not hold when (a/b) cannot be
represented, but does not deny the modulo operator the option of just
returning the correct result, which is representable.


I think you missed my point

For sure a/b is undefined, so the trap routine does not have to worry
about the case where the trap comes from a/b, it only has to worry
about the case where the remainder is wanted, so setting the remainder
is indeed safe.


cheers,
  DaveK

Re: Miscompilation of remainder expressions

[Robert Dewar]

Roberto Bagnara wrote:


I am sorry if I brought you to think that I am asking something
for me.  There is no longer a problem for me personally: I will
simply stop using % in my projects (which, by the way are in C++)
and will use custom functions instead.  I have almost finished
an Autoconf test to check for this bug.  Most importantly, I am
now perfectly aware of the problem.  I have filed a couple
of bug reports, one for GCC and the other for the Intel C/C++
compiler.  I have been told that a C Standard Defect Report
already exists on this subject.  So, it is the end of the
story, as far as I am personally concerned.
Concerning the community (to which I belong, by the way)
I propose that, to start with, the documentation is modified
to mention this problem in a prominent way.  The text can
be borrowed from the new Autoconf's documentation that has
been recently discussed on this list.


OK, so sounds like this bug definitely is in the status of
being of extremly low priority, since the only user who has
ever cared about it so far doesn't care any more



There are lots of known bugs far more important than this one.


Wow!


Are you *really* surprised by that statement above, if so
it's pretty amazing.


I hope they are all in Bugzilla: the one we are talking
about was apparently not there until a couple of hours ago.


Maybe they are may be not, it's not that critical, since
there are lots of serious bugs that are not known. So you
can never write programs that critically depend on compiler
correctness.

Re: Miscompilation of remainder expressions

[Robert Dewar]

Roberto Bagnara wrote:


You are right: I am not familiar with DO-178B certification.


Fair enough, but it means you should never use avionics code
as an example in such discussions. No life has ever been lost
due to a software bug in the realm of commercial aviation, and
that was not achieved by trusting compilers to be bug free.



Yes, it's a bug, is it a serious bug, no? Will real software
be affected? no. Indeed I find any program that actually
does this remainder operation in practice to be highly
suspect.


But I am not wrong if I say that a bug is a bug and must be fixed.


must be fixed

never means more than "may be fixed if someone either gets
enthusiastic enough to do it themselves, or is paid to fix it."
Of course serious bugs usually fall into one of these categories
in a reasonable time period.

Re: Miscompilation of remainder expressions

[Robert Dewar]

Andrew Haley wrote:

Roberto Bagnara writes:
 > Robert Dewar wrote:
 > 
 > > Yes, it's a bug, is it a serious bug, no? Will real software

 > > be affected? no. Indeed I find any program that actually
 > > does this remainder operation in practice to be highly
 > > suspect.
 > 
 > But I am not wrong if I say that a bug is a bug and must be fixed.

 > I was answering to a message saying (basically) "we won't fix
 > it since there is a performance penalty to be paid."

It wasn't saying that.

My opinion at the time was (and still is) that it probably isn't a
bug, and there is a performance penalty to be paid for changing the
behaviour, so we shouldn't fix it.

If I had believed that it surely was a bug, then I wouldn't have made
the performance argument: correctness first, then performance.


Yes, of course, I think we all agree with that. Roberto was just
misreading here


Andrew.

Re: Miscompilation of remainder expressions

[Robert Dewar]

H .. I wish some of the more important bugs in gcc received
the attention that this very unimportant issue is receiving :-)

I guess the difference is that lots of people can understand
this issue.

Reminds me of the hullabaloo over the Pentium division problem.
The fact of the matter was that the Pentium had many more serious
problems, but they were not well known, and often much more
complex to understand!