Re: [PATCH] Document arithmetic overflow semantics

Re: [PATCH] Document arithmetic overflow semantics

[Richard Kenner]

    I completely disagree, and so do GCC's patch reviewers.  The behaviour
    of a program with optimization should always be the same as its behaviour
    without optimization.

Another example of where that's false:

We've said many times that a program that contains an expression of
the form

	i = i++;

need not produce the same results in different optimization levels.

You seem to be trying to divide the set of things that make a program
undefined into two sets: those that we must preserve over optimization
and those that we need not.  What criteria do you propose to use to choose,
for each example of undefined behavior, which of those cases we apply?

Re: [PATCH] Document arithmetic overflow semantics

[Roger Sayle]

Hi Richard,
> We've said many times that a program that contains an expression of
> the form
>
> 	i = i++;
>
> need not produce the same results in different optimization levels.
>
> You seem to be trying to divide the set of things that make a program
> undefined into two sets: those that we must preserve over optimization
> and those that we need not.  What criteria do you propose to use to choose,
> for each example of undefined behavior, which of those cases we apply?


What makes a program undefined is specified by the front-end's language
specification.  This I have absolutely no comment on.  In some languages
"i = i++" has precisely defined behaviour, in others it does not.

The issue is GCC's internal representations, which shouldn't suffer
from the same issue of poorly defined languages.  Hence, if CSE sees
"x = i++; i = x" it had better understand exactly what "i = i++" means
at the RTL-level.  One might hope that the interpretation of RTL and
TREEs are independent of the source language and target architecture.

Roger
--

Re: [PATCH] Document arithmetic overflow semantics

[Robert Dewar]

> Yes, but won't such a program always give a compile-time
> warning like "this branch will never be executed" or
> "unreachable code deleted"?  Can you give an example
> where the compiler will delete a branch but where it
> is not able to diagnose it did?


Actually it is often very difficult to track down actions in a complex
optimization circuit that is manipulating some intermediate form to give
clear diagnostics, because the sequence of logic that arrives at a decision
may be arbitrarily complex, and it may be difficult for instance o tell
if the code in question is a direct consequence of the original source
code, or some code generated by some other optimization. Certainly there
is no requirement for a compiler to give such warnings.

Re: [PATCH] Document arithmetic overflow semantics

[Segher Boessenkool]

Robert Dewar wrote:
>>Yes, but won't such a program always give a compile-time
>>warning like "this branch will never be executed" or
>>"unreachable code deleted"?  Can you give an example
>>where the compiler will delete a branch but where it
>>is not able to diagnose it did?
> 
> Actually it is often very difficult to track down actions in a complex
> optimization circuit that is manipulating some intermediate form to give
> clear diagnostics, because the sequence of logic that arrives at a decision
> may be arbitrarily complex, and it may be difficult for instance o tell
> if the code in question is a direct consequence of the original source
> code, or some code generated by some other optimization. Certainly there
> is no requirement for a compiler to give such warnings.

Of course, but I can't come up with an example where the
compiler can't easily warn "unreachable code deleted".
Can you?


Segher

Re: [PATCH] Document arithmetic overflow semantics

[Fergus Henderson]

On 18-Feb-2003, Segher Boessenkool <segher@koffie.nl> wrote:
> Of course, but I can't come up with an example where the
> compiler can't easily warn "unreachable code deleted".

The compiler could easily issue such warnings, but the problem is that
there would be too many false alarms.  Having unreachable code at the
tree or RTL level may be quite common, especially in conjunction with macros,
C++ templates, automatically generated source files (e.g. yacc), etc.

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.

Re: [PATCH] Document arithmetic overflow semantics

[Joe Buck]

> > Actually it is often very difficult to track down actions in a complex
> > optimization circuit that is manipulating some intermediate form to give
> > clear diagnostics, because the sequence of logic that arrives at a decision
> > may be arbitrarily complex, and it may be difficult for instance o tell
> > if the code in question is a direct consequence of the original source
> > code, or some code generated by some other optimization. Certainly there
> > is no requirement for a compiler to give such warnings.
 
On Tue, Feb 18, 2003 at 05:36:32AM +0100, Segher Boessenkool wrote:
> Of course, but I can't come up with an example where the
> compiler can't easily warn "unreachable code deleted".
> Can you?

I commonly write C++ templates that rely on constant folding for optimization.
The fact that unreachable code is deleted is a feature, not a bug, and any
compiler that insisted on warning me every time unreachable code is deleted
would be rejected as unusable.

Neverthess, redundant code is sometimes an indication that something is
wrong, but only when the code is redundant at source level when the values
of macros or the form of expanded templates is considered opaque.  There's
a discussion of this in some of Dawson Engler's metacompilation papers.

Re: [PATCH] Document arithmetic overflow semantics

[Robert Dewar]

> I guess the question is what exactly "back propagate" mean in practice. I
> think most people agree that doing so *explicitly* is a bad idea and doesn't
> produce any optimizations of correct programs in practice.

It is in fact almost impossible to precisely define, but in the realm of
optimizers, you have code that makes logical deductions from a set of 
assumptions. For example, if you see 

  if a > 3 then
	

You create an implicit assertion that a is greater than 3 at the point of the
then statements. Subsequent actions assume this and e.g. remove a division
by zero check.

There is really no distinction between "forward" and "backward" propagation
at this level of logical operation. Many important optimizations, for example
removing dead code and dead assignments result from what you might informally
regard as "back propagation":

   x := 3;
   ... (x not mentioned)
   x := 4;

The information from the second assignment back propagates to the x := 3
point and causes it to be deleted.

If you introduce as an assumption that the optimizer can take into account that
certain behavior is undefined, then what informally we regard as "improper
back propagation" is hard to avoid. The meaning of two statements:

   s1;
   s2;

is represted semantically as the composition of two functions on states,
and if s2(s) yields undefined for all s, then most certainly s2(s1(s)) yields
undefined, and there goes the back propagation.

So it is indeed important to keep this under control. I actually think the
idea of using the Ada bounded error semantics for uninitialized variables
is exactly the right one. The Ada definition was carefully crafted with two
ideas in mind:

1. Don't cause any significant degradation of the code
2. Avoid nasty "back propagation" of undefined

And also of course, at the programmer's semantic level, we have a definition
of uninitialized behavior that corresponds intuitively to what the programmer
who does not know about weird optimizers would expect.

Re: [PATCH] Document arithmetic overflow semantics

[Richard Kenner]

    However, once you allow an optimizer to back propagate the assumption
    that a program has a defined behavior, things may get surprising, and
    as you can see from my earlier message, there is a not too far fetched
    scenario in which a well meaning implementation could in fact end up
    deleting the system disk unintentionally as an indirect consequence of
    an uninitialized variable.

I guess the question is what exactly "back propagate" mean in practice. I
think most people agree that doing so *explicitly* is a bad idea and doesn't
produce any optimizations of correct programs in practice.

The issue is in something like my A * 2 / 2 example in C.  Technically
speaking, you can view optimizing this to A as doing that back-propagation,
but an alternate way to look at it is to redefine the arithmetic with
"undefined" as a value and allow the simplification to be valid if
certain well-defined behavior on that arithmetic is preserved.

Re: [PATCH] Document arithmetic overflow semantics

[Robert Dewar]

> 
>     This is indeed the reason that Ada 95 introduced bounded errors,
>     where the language allows the implementation to pick any value
>     in the base range of the type or raise an exception.
> 
> I think that's intuitively what most of us mean by "undefined" in this
> discussion but you are quite right that it's good to formalize it better.

Yes, and that intuition is dangerously misleading, because it gives a false
sense of comfort. If I tell you that an uninitialized variable could cause
the system disk to be deleted, you will tend to react "yeah, yeah, we know
this language lawyer stuff, but in practice, no implementor is going to
do something that silly". However, once you allow an optimizer to back
propagate the assumption that a program has a defined behavior, things
may get surprising, and as you can see from my earlier message, there is
a not too far fetched scenario in which a well meaning implementation could
in fact end up deleting the system disk unintentionally as an indirect
consequence of an uninitialized variable.

Re: [PATCH] Document arithmetic overflow semantics

[Segher Boessenkool]

Robert Dewar wrote:

> Yes, and that intuition is dangerously misleading, because it gives a false
> sense of comfort. If I tell you that an uninitialized variable could cause
> the system disk to be deleted, you will tend to react "yeah, yeah, we know
> this language lawyer stuff, but in practice, no implementor is going to
> do something that silly". However, once you allow an optimizer to back
> propagate the assumption that a program has a defined behavior, things
> may get surprising, and as you can see from my earlier message, there is
> a not too far fetched scenario in which a well meaning implementation could
> in fact end up deleting the system disk unintentionally as an indirect
> consequence of an uninitialized variable.

Yes, but won't such a program always give a compile-time
warning like "this branch will never be executed" or
"unreachable code deleted"?  Can you give an example
where the compiler will delete a branch but where it
is not able to diagnose it did?


Segher

Re: [PATCH] Document arithmetic overflow semantics

[Richard Kenner]

    This is indeed the reason that Ada 95 introduced bounded errors,
    where the language allows the implementation to pick any value
    in the base range of the type or raise an exception.

I think that's intuitively what most of us mean by "undefined" in this
discussion but you are quite right that it's good to formalize it better.

Re: [PATCH] Document arithmetic overflow semantics

[Robert Dewar]

> That's not really true... a straight-forward way to "fix" this problem is
> to simply initialize all variables to, for example, zero.  In almost all
> cases, optimization would DCE this initialization anyway, so there is
> really very little cost.  The only major cases I can think of that the
> initialization would not be killed would be something like this:

Hmm, I am quite dubious about the claim that this would have zero overhead
in practice, but if true, then I agree, it should be done.

Re: [PATCH] Document arithmetic overflow semantics

[Chris Lattner]

> > really very little cost.  The only major cases I can think of that the
> > initialization would not be killed would be something like this:
>
> Hmm, I am quite dubious about the claim that this would have zero overhead
> in practice, but if true, then I agree, it should be done.

Please don't get me wrong, I'm not claiming _zero_ overhead, just "very
little" overhead overhead.  C programmers everywhere would rebel against
such a thing, but it certainly would be a useful option to have.  If your
program doesn't work with optimization turned on, you could try this
switch, and it might help paper over the problem.  :)

-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/

Re: [PATCH] Document arithmetic overflow semantics

[Joe Buck]

On Thu, Feb 13, 2003 at 11:45:37PM -0500, Robert Dewar wrote:
> > That's not really true... a straight-forward way to "fix" this problem is
> > to simply initialize all variables to, for example, zero.  In almost all
> > cases, optimization would DCE this initialization anyway, so there is
> > really very little cost.  The only major cases I can think of that the
> > initialization would not be killed would be something like this:
> 
> Hmm, I am quite dubious about the claim that this would have zero overhead
> in practice, but if true, then I agree, it should be done.

The reason that it won't have zero overhead in practice is because gcc is
not yet as smart as it should be, even for scalars.  For arrays, if you
force all elements of arrays to be initialized to zero, I doubt that gcc
will figure out that those initializations are dead in most cases.

Re: [PATCH] Document arithmetic overflow semantics

[Robert Dewar]

> This thread is impossible two follow, what with not one but two
> arch-villains, Robert Dewar and Richard Kenner contributing to it.

Sorry I tried switching and something went wrong, and then other things
over took stuff. I will try again!

Re: [PATCH] Document arithmetic overflow semantics

[Robert Dewar]

> The issue is GCC's internal representations, which shouldn't suffer
> from the same issue of poorly defined languages.  Hence, if CSE sees
> "x = i++; i = x" it had better understand exactly what "i = i++" means
> at the RTL-level.  One might hope that the interpretation of RTL and
> TREEs are independent of the source language and target architecture.

Most certainly the meaning should be specified and exact, but also it can
most certainly be non-deterministic with several possbile outcomes.

Re: [PATCH] Document arithmetic overflow semantics

[Chris Lattner]

>> Are you really claiming that a program with an uninitialized variable
>> must be compiled in such a way that it produces the same result
>> independent of optimization?

> No one claims this, but it is useful to observe that the problem of
> uninitialized variables causing different results in unoptimized and
> optimized code is a severe one in practice that causes a lot of grief,
> especially in large systems where tracking down the difference can be a
> lot of work. However, in this case, the cure would be very expensive,
> and the gain from "optimizing" (which typically comes from putting stuff
> in registers) is so great as to be worth the pain.

That's not really true... a straight-forward way to "fix" this problem is
to simply initialize all variables to, for example, zero.  In almost all
cases, optimization would DCE this initialization anyway, so there is
really very little cost.  The only major cases I can think of that the
initialization would not be killed would be something like this:

int X;

if (predicate) {
...
  X = 6;
}

...

if (predicate) {
  = X;
}

In this case, X is always initialized before being used, but it's unlikely
an optimizer would know that, and thus it would have to insert an
initialization for X on the first !predicate path...

Despite the small cost, this could be a real help to some people...

-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/

Re: [PATCH] Document arithmetic overflow semantics

[Marcel Cox]

I think initializing automatic variables to 0 is the worst you could do as
you would start helping people write erronous code which relies on
uninitialized variables being 0.
If you really want to help people track down problems with uninitialzed
variables, initialize all variables with some "magic" value which is always
the same so that you get predictable behaviour, but a value which is useless
to 99.9% of all programs because it will automatically yield wrong results.


Marcel Cox

"Chris Lattner" <sabre@nondot.org> wrote in message
news:Pine.LNX.4.44.0302131450560.9271-100000@nondot.org...
>
> >> Are you really claiming that a program with an uninitialized variable
> >> must be compiled in such a way that it produces the same result
> >> independent of optimization?
>
> > No one claims this, but it is useful to observe that the problem of
> > uninitialized variables causing different results in unoptimized and
> > optimized code is a severe one in practice that causes a lot of grief,
> > especially in large systems where tracking down the difference can be a
> > lot of work. However, in this case, the cure would be very expensive,
> > and the gain from "optimizing" (which typically comes from putting stuff
> > in registers) is so great as to be worth the pain.
>
> That's not really true... a straight-forward way to "fix" this problem is
> to simply initialize all variables to, for example, zero.  In almost all
> cases, optimization would DCE this initialization anyway, so there is
> really very little cost.  The only major cases I can think of that the
> initialization would not be killed would be something like this:
>
> int X;
>
> if (predicate) {
> ...
>   X = 6;
> }
>
> ...
>
> if (predicate) {
>   = X;
> }
>
> In this case, X is always initialized before being used, but it's unlikely
> an optimizer would know that, and thus it would have to insert an
> initialization for X on the first !predicate path...
>
> Despite the small cost, this could be a real help to some people...
>
> -Chris
>
> -- 
> http://llvm.cs.uiuc.edu/
> http://www.nondot.org/~sabre/Projects/
>
>

Re: [PATCH] Document arithmetic overflow semantics

[Joe Buck]

On Fri, Feb 14, 2003 at 08:46:02AM +0100, Marcel Cox wrote:
> I think initializing automatic variables to 0 is the worst you could do as
> you would start helping people write erronous code which relies on
> uninitialized variables being 0.
> If you really want to help people track down problems with uninitialzed
> variables, initialize all variables with some "magic" value which is always
> the same so that you get predictable behaviour, but a value which is useless
> to 99.9% of all programs because it will automatically yield wrong results.

For floating point, a signaling NaN can be used.  For integers,
0xdeadbeef or some such.

[ cases where gcc can't figure out that a variable is uninitialized ]

> > Despite the small cost, this could be a real help to some people...

It should be possible to turn the feature off.

Re: [PATCH] Document arithmetic overflow semantics

[Nathan Sidwell]

Joe Buck wrote:

> For floating point, a signaling NaN can be used.  For integers,
> 0xdeadbeef or some such.
> 
> [ cases where gcc can't figure out that a variable is uninitialized ]
> 
> 
>>>Despite the small cost, this could be a real help to some people...
>>
> 
> It should be possible to turn the feature off.
turned on at -O0, off at other levels?

nathan

-- 
Nathan Sidwell    ::   http://www.codesourcery.com   ::     CodeSourcery LLC
          The voices in my head said this was stupid too
nathan@codesourcery.com : http://www.cs.bris.ac.uk/~nathan/ : nathan@acm.org

Re: [PATCH] Document arithmetic overflow semantics

[Robert Dewar]

> Are you really claiming that a program with an uninitialized variable
> must be compiled in such a way that it produces the same result independent
> of optimization?

No one claims this, but it is useful to observe that the problem of uninitialized
variables causing different results in unoptimized and optimized code is a severe
one in practice that causes a lot of grief, especially in large systems where
tracking down the difference can be a lot of work. However, in this case, the
cure would be very expensive, and the gain from "optimizing" (which typically
comes from putting stuff in registers) is so great as to be worth the pain.

But we really should note in this discussion that any case in which optimization
changes results is potentailly a degradation of the usability of the compiler.
You have to be careful, on a case-by-case basis, that the gains from the
corresponding optimization are worth the pain.

Re: [PATCH] Document arithmetic overflow semantics

[Robert Dewar]

> > Certainly for + and -, Java can get what it wants
> 
> Including gdb support?
> If Java maps signed types to unsigned, how is gdb going to know about it?

As someone pointed out you can certainly do conversions, and that is annoying
but will preserve gdb semantics.

Re: [PATCH] Document arithmetic overflow semantics

[Robert Dewar]

> Including gdb support?
> If Java maps signed types to unsigned, how is gdb going to know about it?

Indeed the debugging information should represent these as signed, and it is
indeed problematic that gdb debugging information in gcc is tied so closely
to the types used for code generation purposes (we have bumped our noses
on this in Ada many times). I think this just goes again to show that the
issue of operation semantics should not depend on the type alone, but rather
on the operation, as was previously suggested in this thread.

Re: [PATCH] Document arithmetic overflow semantics

[Robert Dewar]

>  One of the
> possibilities is to generate a two's complement addition.  Another
> is to generate a trapping addition.

OK, so you are using "two's complement addition" to imply wrapping. That's
potentially confusing terminology, I would suggest that we always say wrapping
when we mean it.

Re: [PATCH] Document arithmetic overflow semantics

[Robert Dewar]

> and clearly this is in incorrect in many cases, for example int->long
> conversion and indeed anything that involves integer operands of
> different sizes.

Sorry for confusing things, but yes, of course the interpretation of values
is as signed values where it matters, but for addition, subtraction and
multiplication it does not, and the proper way of representing these in the
tree to get tyhe right results is to use unsigned oeprations.

Re: [PATCH] Document arithmetic overflow semantics

[Robert Dewar]

> There are operations other than plus and minus.

Yes, in particular division needs special casing, but overflow is not an issue
there for single length division, or at least not so much of an issue.

Re: [PATCH] Document arithmetic overflow semantics

[Robert Dewar]

> But undefined overflow is a superset of two's complement semantics

I don't understand the terminology here. Are you using "two's comlement" to
imply unsigned wrap around, i.e. throw away carry and ignore overflow. If so,
that's a bit confusing, since it presupposes the conclusion. The issue with
twos complement signed arithmetic is preciesely what happens on overflow (that's
the only thing that distinguishes it from unsigned).

Re: [PATCH] Document arithmetic overflow semantics

[Joe Buck]

On Thu, Feb 13, 2003 at 02:10:10PM -0500, Robert Dewar wrote:
> > But undefined overflow is a superset of two's complement semantics
> 
> I don't understand the terminology here. Are you using "two's comlement" to
> imply unsigned wrap around, i.e. throw away carry and ignore overflow. If so,
> that's a bit confusing, since it presupposes the conclusion. The issue with
> twos complement signed arithmetic is preciesely what happens on overflow (that's
> the only thing that distinguishes it from unsigned).

To clarify: if we have code that might overflow, we can generate a
variety of different forms of assembler language, as long as the
cases that don't overflow compute the correct results.  One of the
possibilities is to generate a two's complement addition.  Another
is to generate a trapping addition.

If we use two's complement addition, which is associative, we can make
further transformations.

Re: [PATCH] Document arithmetic overflow semantics

[Robert Dewar]

> This is why we should have proper annotations on the tree nodes
> so that Java can get the results that they need.

Certainly for + and -, Java can get what it wants

Re: [PATCH] Document arithmetic overflow semantics

[Fergus Henderson]

On 13-Feb-2003, Robert Dewar <dewar@gnat.com> wrote:
> > This is why we should have proper annotations on the tree nodes
> > so that Java can get the results that they need.
> 
> Certainly for + and -, Java can get what it wants

Including gdb support?
If Java maps signed types to unsigned, how is gdb going to know about it?

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.

Re: [PATCH] Document arithmetic overflow semantics

[Robert Dewar]

> Suppose we denote the three variants of "+" as follows:
> 
>       +undef          undefined behaviour on overflow
>       +wrap           wraps on overflow
>       +trap           traps on overflow

I still don't see how +wrap differs from an unsigned addition, so it seems
simply confusing to have it around explicitly.

Re: [PATCH] Document arithmetic overflow semantics

[Fergus Henderson]

On 13-Feb-2003, Robert Dewar <dewar@gnat.com> wrote:
> > Suppose we denote the three variants of "+" as follows:
> > 
> >       +undef          undefined behaviour on overflow
> >       +wrap           wraps on overflow
> >       +trap           traps on overflow
> 
> I still don't see how +wrap differs from an unsigned addition, so it seems
> simply confusing to have it around explicitly.

You are right that +wrap has the same semantics as an unsigned addition.
But I don't think it would be confusing to have it around explicitly,
and I do think that doing this would make things a lot easier.

In GCC trees the signedness of additions is determined by the signedness
of the types of the operands.  Representing +wrap additions as unsigned
operations would require that the operations be converted to unsigned
types.  This will require more tree nodes, which may have a compilation
time impact, and the additional conversions would complicate the intermediate
representation in ways that may inhibit some optimizations.

I think it would be much better to adopt a consistent approach which will
work for all arithmetic operations, not just plus and minus.

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.

Re: [PATCH] Document arithmetic overflow semantics

[Fergus Henderson]

On 14-Feb-2003, Fergus Henderson <fjh@cs.mu.OZ.AU> wrote:
> In GCC trees the signedness of additions is determined by the signedness
> of the types of the operands.  Representing +wrap additions as unsigned
> operations would require that the operations be converted to unsigned
> types.

Sorry, I meant s/the operations/the operands/

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.

Re: [PATCH] Document arithmetic overflow semantics

[Michael S. Zick]

On Friday 14 February 2003 02:31 am, Fergus Henderson wrote:
> On 14-Feb-2003, Fergus Henderson <fjh@cs.mu.OZ.AU> wrote:
> > In GCC trees the signedness of additions is determined by the signedness
> > of the types of the operands.  Representing +wrap additions as unsigned
> > operations would require that the operations be converted to unsigned
> > types.
>
> Sorry, I meant s/the operations/the operands/

Actually, both.

My case for both is to generalize the internal abstraction to handle related
issues.
Since the discussion has lead to either "property bits" or "node types" to
handle overflow semantics; and somebody will be coding in this area...

I suggest adding a bit to both operator and operand to represent the
commutative property.

Multiplication ("*" operator), an operation of the second kind, would
have its commutative property bit set.

For Integer (and appropriate others) operands, they would have 
the commutative property bit set.

For Matrix operands, they would have the commutative property
bit clear.

The internal abstraction could then select its allowable optimizations
based on the commutative property bits of both operands and operators.

I.E: for;
int i1, i2 ;

i1 * i2 == i2 * i1 ;
In other words, that is allowable. (commutative == {true, true, true})

and for;
mat m1, m2 ;

m1 * m2 != m2 * m1 ;
In other words, that is NOT allowable. (commutative == {false, true, false})

With concurrent threads on this list about support for HPC and
vector types, first thing you know, somebody will want an array
of a vector type (a matrix).  Then they will expect to be able to do
basic numeric operations on them.

(Heck, perhaps bite the bullet now, add four property bits:
associative, commutative, distributive, monotonic [to support
unorder compares]).

Mike

Re: [PATCH] Document arithmetic overflow semantics

[Robert Dewar]

> What do you mean by this, exactly?  Java is defied as having signed
> two's complement arithmetic.

At the implementation level, the difference between signed and unsigned
arithmetic (for operations like plus and minus) is in whether overflow
is an issue or not (look for example at the MIPS). The issue of "2-s complement"
just has to do with how you interpret a bit pattern (i.e. whether all 1's is
a big number of minus one). If you have wrap around semantics, then, regardless
of how you choose to interpret the bit patterns, the appropriate run-time
representation of add/subtract operations is to do unsigned adds with no 
carry around (and no signed overflow detection).

Re: [PATCH] Document arithmetic overflow semantics

[Fergus Henderson]

On 13-Feb-2003, Robert Dewar <dewar@gnat.com> wrote:
> > What do you mean by this, exactly?  Java is defied as having signed
> > two's complement arithmetic.
> 
> At the implementation level, the difference between signed and unsigned
> arithmetic (for operations like plus and minus) is in whether overflow
> is an issue or not

There are operations other than plus and minus.

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.

Re: [PATCH] Document arithmetic overflow semantics

[Andrew Haley]

Robert Dewar writes:
 > > What do you mean by this, exactly?  Java is defied as having signed
 > > two's complement arithmetic.
 > 
 > At the implementation level, the difference between signed and unsigned
 > arithmetic (for operations like plus and minus) is in whether overflow
 > is an issue or not (look for example at the MIPS). The issue of "2-s complement"
 > just has to do with how you interpret a bit pattern (i.e. whether all 1's is
 > a big number of minus one). If you have wrap around semantics, then, regardless
 > of how you choose to interpret the bit patterns, the appropriate run-time
 > representation of add/subtract operations is to do unsigned adds with no 
 > carry around (and no signed overflow detection).

Obviously, but you said

 > it seems clear that Java should be using unsigned arithmetic for
 > all operations, since that is the way Java is defined.

and clearly this is in incorrect in many cases, for example int->long
conversion and indeed anything that involves integer operands of
different sizes.

Andrew.

Re: [PATCH] Document arithmetic overflow semantics

[Richard Kenner]

    There are more bugs in this area, than I can hope to address.

But you have pointed out correctly that it does need to be addressed
at some point.

Re: [PATCH] Document arithmetic overflow semantics

[Robert Dewar]

> Java requires strict 32-bit two's complement arithmetic for its ints,
> and PLUS_EXPR isn't guaranteed to do that.  We could, of course,
> generate something like
> 
>    uint((ulong)a + (ulong)b)
> 
> which would be well defined. 

it seems clear that Java should be using unsigned arithmetic for all operations,
since that is the way Java is defined.

Re: [PATCH] Document arithmetic overflow semantics

[Andrew Haley]

Robert Dewar writes:
 > > Java requires strict 32-bit two's complement arithmetic for its ints,
 > > and PLUS_EXPR isn't guaranteed to do that.  We could, of course,
 > > generate something like
 > > 
 > >    uint((ulong)a + (ulong)b)
 > > 
 > > which would be well defined. 
 > 
 > it seems clear that Java should be using unsigned arithmetic for all operations,
 > since that is the way Java is defined.

What do you mean by this, exactly?  Java is defied as having signed
two's complement arithmetic.

Andrew.

Re: [PATCH] Document arithmetic overflow semantics

[Neil Booth]

Robert Dewar wrote:-

> > Java requires strict 32-bit two's complement arithmetic for its ints,
> > and PLUS_EXPR isn't guaranteed to do that.  We could, of course,
> > generate something like
> > 
> >    uint((ulong)a + (ulong)b)
> > 
> > which would be well defined. 
> 
> it seems clear that Java should be using unsigned arithmetic for all operations,
> since that is the way Java is defined.

What happened about getting a 21-st century mailer that preserves
mail IDs?  Zack pointed you to a Berkeley-compatible mail program that
did it, but he was ignored.

This thread is impossible two follow, what with not one but two
arch-villains, Robert Dewar and Richard Kenner contributing to it.

Neil.

Re: [PATCH] Document arithmetic overflow semantics

[Gabriel Dos Reis]

Neil Booth <neil@daikokuya.co.uk> writes:

[...]

| This thread is impossible two follow,

I would like to second Neil here: Although I enjoy reading
contributions by Robert Dewar and Richard Kenner, I find the failure
of their mailers to insert appropriate references very discouraging to
the point that, most of the time, I just press the 'D' key and pass on
much readable threads.  

:-(

-- Gaby

Re: [PATCH] Document arithmetic overflow semantics

[Phil Edwards]

On Thu, Feb 13, 2003 at 10:04:46PM +0100, Gabriel Dos Reis wrote:
> Neil Booth <neil@daikokuya.co.uk> writes:
> 
> [...]
> 
> | This thread is impossible two follow,
> 
> I would like to second Neil here: Although I enjoy reading
> contributions by Robert Dewar and Richard Kenner, I find the failure
> of their mailers to insert appropriate references very discouraging to
> the point that, most of the time, I just press the 'D' key and pass on
> much readable threads.  
> 
> :-(

You both have much more patience than I do; this thread has been going
straight to the 'delete' bin ever since I logged in and saw that the
"thread tree" was one long line, straight down.

It's hard enough to decode and mentally reorganize the output of
-fdump-translation-unit.  There's no excuse for needing to do the same
thing to email.

Phil

-- 
I would therefore like to posit that computing's central challenge, viz. "How
not to make a mess of it," has /not/ been met.
                                                 - Edsger Dijkstra, 1930-2002

Re: [PATCH] Document arithmetic overflow semantics

[Diego Novillo]

On Thu, 2003-02-13 at 16:04, Gabriel Dos Reis wrote:
> Neil Booth <neil@daikokuya.co.uk> writes:
> 
> [...]
> 
> | This thread is impossible two follow,
> 
> I would like to second Neil here: Although I enjoy reading
> contributions by Robert Dewar and Richard Kenner, I find the failure
> of their mailers to insert appropriate references very discouraging to
> the point that, most of the time, I just press the 'D' key and pass on
> much readable threads.  
> 
> :-(
> 
I concur.  Richard, Robert, *please* get a sane MUA!


Diego.

Re: [PATCH] Document arithmetic overflow semantics

[Robert Dewar]

> The fact that the behaviour of overflow is undefined in C, C++ and Ada
> does not mean that "overflow cannot occur".  Quite clearly overflows do
> occur, and the optimizers are paralyzed by the semantics in this event.

Since this quote is being repeated many times, it is perhaps worth
emphasizing that overflow *is* defined in Ada, and indeed the most
important thing that Ada needs from gcc is efficient code for arithmetic
operations that trap on overflow :-)

Re: [PATCH] Document arithmetic overflow semantics

[Robert Dewar]

> So what?  There's no requirement that erroneous programs produce the
> same result in different versions of GCC.


There is also no requirement that the compile speed not be multiplied by
100 in the next version of GCC. The standard is not the only source of
criteria for a usable compiler, and a compiler that takes too much advantage
of undefined behavior may be a menace even if it is conforming.

Re: [PATCH] Document arithmetic overflow semantics

[Robert Dewar]

> The one I mentioned: (a*2)/2

Notice that in Ada this is handled at the language level without any notino
of undefinedness in the semantics (indeed in Ada, integer overflow is usually
very well defined to raise an exception).

However, the intermediate value a*2 will be computed in the base integer type,
and base integer types are unconstrained, which means that it is fine to have
out of range values temporarily if the result is "correct" mathematically.

Re: [PATCH] Document arithmetic overflow semantics

[Richard Kenner]

    How?  Any new optimization that we introduce that takes advantage
    of the undefinedness will both produce different results from the
    current versions of GCC, 

So what?  There's no requirement that erroneous programs produce the
same result in different versions of GCC.

    and will break the Java front-end.

No, because *those* nodes would be marked as *not* being undefined on
overflow.

Re: [PATCH] Document arithmetic overflow semantics

[Richard Kenner]

    > Nope.  Lots of places in the optimizer assume that overflow signed
    > integers are undefined.  

    I'm prepared to drop this entire argument if you can find me just one

The one I mentioned: (a*2)/2.

Re: [PATCH] Document arithmetic overflow semantics

[Roger Sayle]

> > I'm prepared to drop this entire argument if you can find me just one
>
> The one I mentioned: (a*2)/2.


That'll do.  You're right, GCC does optimize this assuming undefined
overflow.  Good to my word, I hereby withdraw my patch.  There are
more bugs in this area, than I can hope to address.

Interestingly, Microsoft's Visual C/C++ compilers don't optimize this
example.  I wonder how much of their 20% SPECint advantage over mainline
GCC is from their use of two's-complement semantics vs. undefined
overflow.  For example, they also optimize "z1 = (x+y)+z; z2 = x+(y+z)"
which GCC currently can't.


What can I say.  I tried.  I failed.
My apologies for any inconvenience.

Roger
--

Re: [PATCH] Document arithmetic overflow semantics

[Joe Buck]

On Thu, Feb 13, 2003 at 11:16:03AM -0700, Roger Sayle wrote:
> 
> > > I'm prepared to drop this entire argument if you can find me just one
> >
> > The one I mentioned: (a*2)/2.
> 
> 
> That'll do.  You're right, GCC does optimize this assuming undefined
> overflow.  Good to my word, I hereby withdraw my patch.  There are
> more bugs in this area, than I can hope to address.
> 
> Interestingly, Microsoft's Visual C/C++ compilers don't optimize this
> example.  I wonder how much of their 20% SPECint advantage over mainline
> GCC is from their use of two's-complement semantics vs. undefined
> overflow.  For example, they also optimize "z1 = (x+y)+z; z2 = x+(y+z)"
> which GCC currently can't.

But undefined overflow is a superset of two's complement semantics; if
overflow is undefined it can be implemented as two's complement if it is
useful.

Re: [PATCH] Document arithmetic overflow semantics

[Richard Kenner]

    I think there is major confusion here between "undefined" in the 
    language-lawyer concept and "ambiguous" about what our internal nodes mean.

    Yes, we want to take advantage of the former.  But we need to try and 
    avoid the latter.

Strongly agreed.

Re: [PATCH] Document arithmetic overflow semantics

[Robert Dewar]

I very much dislike the idea of the optimizer making assumptions based
on undefined semantics. It's a very dangerous path to tread. Consider
the following Ada 83 code (you can get equivalent Ada 95 programs, but
Ada 95 has restricted erroneous behavior as much as possible to minimize
this kind of concern). 

In Ada 83, referencing an undefined variable is erroneous

   put_line ("system disk reformat requested: enter pass word");
   declare
	Attempts : Natural; -- count of attempts at pass word entry

   begin
        loop
           Get (password);
           if password = masterpassword then
	 	erase_system_disk;
                exit;
	   else
	      Attempts := Attempts + 1;
              if Attempts > 4 then raise Hacker_Alert; end if;
	      put_line ("bad pass word, reenter");
	   end if;
	end loop;
   end;

Now the optimizer appears to be allowed to do the following.

If password /= masterpassword, then the program execution is errroneous.
That means the program can do anything it likes, e.g. call erase_system_disk.
Great, I can omit as useless the test password = masterpassword and still
provide a fully conformant as-if implementation.

It's really hard from a formal point of view to stop compilers doing this
sort of thing. 

In the case of overflow, sure, I know you can construct examples where the
optimizer is helped but:

a) I very much doubt that it helps significantly in real life
b) I am afraid of optimizers running amok as in the above example

A single program malfunctioning in an unboundedly curious manner which
is difficult to detect or fix balances against a lot of very minor speedups
and probably these days, the curious malfunction wins unless there is a
really big, demonstratable gain.

Re: [PATCH] Document arithmetic overflow semantics

[Florian Weimer]

dewar@gnat.com (Robert Dewar) writes:

> b) I am afraid of optimizers running amok as in the above example

Shameless plug:

<http://cert.uni-stuttgart.de/advisories/c-integer-overflow.php>

The apt_get_chunk_size bug referenced in the end was actually
exploited by a worm.

Typical C programmers do not understand the issue.  The rebel inside
still thinks that GCC should optimize aggressively in this area, just
to prove the point that C is unusable for any real work, but I doubt
that this is practical.

Re: [PATCH] Document arithmetic overflow semantics

[Joseph S. Myers]

On Thu, 13 Feb 2003, Florian Weimer wrote:

> <http://cert.uni-stuttgart.de/advisories/c-integer-overflow.php>
> 
> The apt_get_chunk_size bug referenced in the end was actually
> exploited by a worm.
> 
> Typical C programmers do not understand the issue.  The rebel inside
> still thinks that GCC should optimize aggressively in this area, just
> to prove the point that C is unusable for any real work, but I doubt
> that this is practical.

We should document options encouraged for compiling secure code.  This
would include both warning options (-Wall -Wformat-security
-Wmissing-format-attribute ...) and code-generation options, such as
-ftrapv (trap on signed overflow) and, when we eventually get it in
mainline, some bounded pointer options (-fmudflap?).

(With flag bits on operations that might overflow, we can easily also add
an option -fsigned-overflow-defined for the benefit of anyone who wants
that language dialect.)

-- 
Joseph S. Myers
jsm28@cam.ac.uk

Re: [PATCH] Document arithmetic overflow semantics

[Mark Hahn]

> > The apt_get_chunk_size bug referenced in the end was actually
> > exploited by a worm.
> > 
> > Typical C programmers do not understand the issue.  The rebel inside
> > still thinks that GCC should optimize aggressively in this area, just
> > to prove the point that C is unusable for any real work, but I doubt
> > that this is practical.
> 
> We should document options encouraged for compiling secure code.  This

yes!  I'm a lowly gcc end-user, but I'm apalled that gcc-gods would 
even consider compromising optimization in favor of some nebulous 
make-bugs-safer argument.

gcc is not a security-fix tool.  please permit users to select 
absolute-max-optimization somehow; this is orthogonal to gcc's 
extremely valuable diagnostics about undefined/questionable code.

thanks, mark hahn.

Re: [PATCH] Document arithmetic overflow semantics

[Neil Booth]

Mark Hahn wrote:-

> yes!  I'm a lowly gcc end-user, but I'm apalled that gcc-gods would 
> even consider compromising optimization in favor of some nebulous 
> make-bugs-safer argument.
> 
> gcc is not a security-fix tool.  please permit users to select 
> absolute-max-optimization somehow; this is orthogonal to gcc's 
> extremely valuable diagnostics about undefined/questionable code.

Indeed.

One day I'd like to see GCC capable of much of what the Linux "Checker"
does, though.

Neil.

Re: [PATCH] Document arithmetic overflow semantics

[Richard Kenner]

    I doubt it; the reason is that the particular assumption that addition
    and multiplication follow the natural two's complement rules gives us
    an algebraic ring, which makes many transformations possible.  Any other
    assumption would introduce an irregularity that has to be tested for in
    each transformation.

I'm thinking of (A * 2) / 2.  This is A only if you are allowed to
assume that an overflow of the multiplication is undefined.

There are numerous cases in loop optimizations too.

Re: [PATCH] Document arithmetic overflow semantics

[Richard Kenner]

    At the GCC internal level there should be no such thing as undefined
    behaviour, this is a front-end concept.  

I disagree.  As I said, it's quite valuable to be able to know that we
don't care, for optimization purposes, if an overflow has or has
not occurred.

    As for trap on overflow, that is currently supported and honored in
    the middle-end, by flag_trapv and flag_non_call_exceptions.

I'm talking about *per expression*.

    You may have noticed that my original patch, was a simple
    documentation patch that just described what GCC currently does, and
    what is assumed at several points in the code.

Nope.  Lots of places in the optimizer assume that overflow signed
integers are undefined.  Your proposed documentation doesn't mention that.

Re: [PATCH] Document arithmetic overflow semantics

[Roger Sayle]

On Thu, 13 Feb 2003, Richard Kenner wrote:
>     At the GCC internal level there should be no such thing as undefined
>     behaviour, this is a front-end concept.
>
> I disagree.  As I said, it's quite valuable to be able to know that we
> don't care, for optimization purposes, if an overflow has or has
> not occurred.

The problem is that this cuts both ways.  Yes, at the moment we may
legitimately replace an expression that overflows with one that doesn't
by invoking the "undefined behaviour" clause.  However, it prohibits
use from optimizing an expression that doesn't orginally overflow, with
an equivalent expression that may.

Currently, GCC's middle-end expands integral PLUS_EXPR using add?i3.
The same addsi3 pattern is used in the back-ends for unsigned arithmetic
as for signed arithmetic, and the behaviour of overflow with both is the
usual two's-complement semantics.  A front-end accepts that an expression
will be evaluated this way when it decides to pass a PLUS_EXPR to the
middle-end.

If a front-end wished to use saturating arithmetic overflow, they would
use the appropriate tree nodes that GCC's middle-end would expand using
ss_plus and us_plus RTL patterns.  Doing a grep in the GCC source code,
the only reference to SS_PLUS is in simplify-rtx.c, which is currently a
place holder as GCC currently performs no simplifications of SS_PLUS,
US_PLUS, SS_MINUS or US_MINUS.


> Nope.  Lots of places in the optimizer assume that overflow signed
> integers are undefined.  Your proposed documentation doesn't mention that.

I'm prepared to drop this entire argument if you can find me just one
(that doesn't already have a GNATS PR).


In return, I'll draw your attention to the following patch, that is
an optimization that we're currently unable to perform because of GCC's
poorly defined semantics.
http://gcc.gnu.org/ml/gcc-patches/2003-02/msg00028.html
Note that several rival C/C++ compilers do happily perform this
transformation, for example Microsoft's Visual C.  You might want
to check whether any of the commercial Ada compilers do too.


If you really believe PLUS_EXPR should have undefined overflow semantics
for signed overflow, then do something about it and document that thats
the intended behaviour.  In which case, the Java front-end will have to
introduce a new tree node with PLUS_EXPR's current semantics.


May I also remind you of the catastrophe of leaving the semantics of
paradoxical subregs undefined in GCC's RTL.  Fortunately, for 3.3 and
3.4 their interpretation was decided upon, but gcc 3.2.2 still has PRs
on Sparc, PA-Risc, IA-64 and PowerPC.  Let's document what we intend!

Roger
--

Re: [PATCH] Document arithmetic overflow semantics

[Richard Kenner]

    Ada for example, performs all its own real arithmetic because Ada
    specifies constraints on precision that aren't documented for GCC's
    tree-nodes.  

No, that's true only for constants.

Re: [PATCH] Document arithmetic overflow semantics

[Richard Kenner]

    In C, it is frequently the case that defining the overflow behavior of
    signed integer in this way makes more optimizations possible.  For one
    thing, it makes addition and multiplication associative.  Without such
    an assumption, you can't turn (a+b)+c into a+(b+c), because the overflows
    might be different.

True, but there are an equal number of simplification that can only be done
if you are allowed to assume that overflow is undefined.

Perhaps an approach might be to say that "we know what overflow
actually does for this operation, but if it occurs, it's undefined
semantics".  That's what we actually *implement* right now and would
give the best of both worlds.  Then there would be a bit that says that,
in this particular operation, the overflow is *not* undefined.

Re: [PATCH] Document arithmetic overflow semantics

[Joe Buck]

I wrote:

>     In C, it is frequently the case that defining the overflow behavior of
>     signed integer in this way makes more optimizations possible.  For one
>     thing, it makes addition and multiplication associative.  Without such
>     an assumption, you can't turn (a+b)+c into a+(b+c), because the overflows
>     might be different.

On Thu, Feb 13, 2003 at 11:06:39AM -0500, Richard Kenner wrote:
> True, but there are an equal number of simplification that can only be done
> if you are allowed to assume that overflow is undefined.

I doubt it; the reason is that the particular assumption that addition
and multiplication follow the natural two's complement rules gives us
an algebraic ring, which makes many transformations possible.  Any other
assumption would introduce an irregularity that has to be tested for in
each transformation.

> Perhaps an approach might be to say that "we know what overflow
> actually does for this operation, but if it occurs, it's undefined
> semantics".  That's what we actually *implement* right now and would
> give the best of both worlds.  Then there would be a bit that says that,
> in this particular operation, the overflow is *not* undefined.

This corresponds to the view that when the USER enters a + with int
arguments, there are no guarantees, but the COMPILER (in particular, tree
optimizations), has available a + node and a * node for ints that are
associative and distributive.  The fact that some ancient and obsolete
one's complement routine with an overflow trap that can't be turned off
might theoretically exist isn't a good reason for crippling the compiler.

If you want to use a mix, then you need to distinguish between overflows
that are a consequence of what the user entered, and overflows that only
exist because of transformations that the compiler did.

Re: [PATCH] Document arithmetic overflow semantics

[Richard Kenner]

    The issue is GCC's internal representations, which shouldn't suffer
    from the same issue of poorly defined languages.  Hence, if CSE sees
    "x = i++; i = x" it had better understand exactly what "i = i++" means
    at the RTL-level.  One might hope that the interpretation of RTL and
    TREEs are independent of the source language and target architecture.

I agree.  Which is why I'm in favor of adding flags to tree nodes that say
whether the operation:

(a) has undefined behavior
(b) has defined overflow behavior, documented for the tree node in question
(c) will trap on overflow.

Then each language sets the appropriate bit for each expression it
makes (possibly defaulting to those from the types) and we do our best
to honor them.

Re: [PATCH] Document arithmetic overflow semantics

[Roger Sayle]

> I agree.  Which is why I'm in favor of adding flags to tree nodes that say
> whether the operation:
>
> (a) has undefined behavior
> (b) has defined overflow behavior, documented for the tree node in question
> (c) will trap on overflow.

At the GCC internal level there should be no such thing as undefined
behaviour, this is a front-end concept.  There should be tree nodes for
overflow behaviour A, overflow behaviour B or overflow behaviour C.
A front-end that says behaviour is undefined, is then free to use
whichever tree node is sees fit.  The middle-end should never be left
to guess what the front-end intended.

As for trap on overflow, that is currently supported and honored in
the middle-end, by flag_trapv and flag_non_call_exceptions.


You may have noticed that my original patch, was a simple documentation
patch that just described what GCC currently does, and what is assumed
at several points in the code.  Naturally, it doesn't require any source
code changes and/or regression testing on multiple platforms.

Should we decide to change GCC's implementation at some point in the
future, naturally we'll have to amend the documentation to reflect that.


Feel free to submit patches to implement you proposed semantics.  It
should have no effect on whether the proposed documentation is accurate
and/or appropriate.

Roger
--

Re: [PATCH] Document arithmetic overflow semantics

[Joseph S. Myers]

On Thu, 13 Feb 2003, Roger Sayle wrote:

> At the GCC internal level there should be no such thing as undefined
> behaviour, this is a front-end concept.  There should be tree nodes for

Undefined behaviour needs to be explicitly modelled in any formal model of
C (see e.g. Norrish's thesis).  It is entirely reasonable to pass it down 
to the middle end.  A C program has a family of possible semantics, some 
of which involve undefined behaviour for some or all input; if we pass 
down information about the family of semantics (rather than unique 
semantics), as constrained by GCC's implementation-defined choices only, 
the middle end can make whichever choices are best for the given code on 
the given machine.  (For example, it can choose the order in which 
function arguments are computed to be what is best for a given function 
call, although what happens with undefined code changing the same object 
in multiple function arguments may vary on different machines.  Scheduling 
can move computations that are not separated by a sequence point past each 
other, when only in undefined code could they change the same variable.  
Having generated code for a+b, the compiler can use the condition codes 
left by that operation for a subsequent check on the value of a+b, even 
though they might be wrong for the check had overflow occurred (this has 
been mentioned as an underlying reason for signed integer arithmetic being 
undefined - the original C compilers having made such assumptions).)

In practice, it may be difficult for the middle-end representation to
encode all the information about the family of program semantics permitted
by the language standard and the implementation-defined behaviour, but
where it can be represented and used it is reasonable to do so.

-- 
Joseph S. Myers
jsm28@cam.ac.uk

Re: [PATCH] Document arithmetic overflow semantics

[Richard Henderson]

On Thu, Feb 13, 2003 at 08:31:33AM -0700, Roger Sayle wrote:
> At the GCC internal level there should be no such thing as undefined
> behaviour, this is a front-end concept.

I disagree.  It's the undefinedness we want to take advantage of.


r~

Re: [PATCH] Document arithmetic overflow semantics

[Richard Earnshaw]

> On Thu, Feb 13, 2003 at 08:31:33AM -0700, Roger Sayle wrote:
> > At the GCC internal level there should be no such thing as undefined
> > behaviour, this is a front-end concept.
> 
> I disagree.  It's the undefinedness we want to take advantage of.
> 

I think there is major confusion here between "undefined" in the 
language-lawyer concept and "ambiguous" about what our internal nodes mean.

Yes, we want to take advantage of the former.  But we need to try and 
avoid the latter.

R.

Re: [PATCH] Document arithmetic overflow semantics

[Richard Henderson]

On Thu, Feb 13, 2003 at 06:04:55PM +0000, Richard Earnshaw wrote:
> I think there is major confusion here between "undefined" in the 
> language-lawyer concept and "ambiguous" about what our internal nodes mean.
> 
> Yes, we want to take advantage of the former.  But we need to try and 
> avoid the latter.

Correct.  But if we don't have a way to represent the former
in the later, then we've lost out.


r~

Re: [PATCH] Document arithmetic overflow semantics

[Roger Sayle]

On Thu, 13 Feb 2003, Richard Henderson wrote:
> On Thu, Feb 13, 2003 at 08:31:33AM -0700, Roger Sayle wrote:
> > At the GCC internal level there should be no such thing as undefined
> > behaviour, this is a front-end concept.
>
> I disagree.  It's the undefinedness we want to take advantage of.

How?  Any new optimization that we introduce that takes advantage
of the undefinedness will both produce different results from the
current versions of GCC, and will break the Java front-end.

New SSA-level loop optimizations will have great difficulty being as
effective as loop.c's loop_iterations that can determine how many times
to a loop iterates at the RTL-level even in the presence of overflows.


Its a simple evolutionary step for GCC, whether the internal tree-level
representation reflects the C/C++ semantics reflecting its heritage,
or is truly an intermediate representation for the "GNU Compiler
Collection" that is consistent with C/C++.  For SSA, tree's need to
be a language independent high-level abstraction of the RTL.


Do you believe the Java front-end is currently incorrect to use
PLUS_EXPR to represent signed addition?

Roger
--

Re: [PATCH] Document arithmetic overflow semantics

[Andrew Haley]

Roger Sayle writes:
 > 
 > 
 > Do you believe the Java front-end is currently incorrect to use
 > PLUS_EXPR to represent signed addition?

It probably is.  

Java requires strict 32-bit two's complement arithmetic for its ints,
and PLUS_EXPR isn't guaranteed to do that.  We could, of course,
generate something like

   uint((ulong)a + (ulong)b)

which would be well defined. 

Andrew.

Re: [PATCH] Document arithmetic overflow semantics

[Richard Henderson]

On Thu, Feb 13, 2003 at 10:41:35AM -0700, Roger Sayle wrote:
> How?  Any new optimization that we introduce that takes advantage
> of the undefinedness will both produce different results from the
> current versions of GCC,

Of this I do not care.

> ... and will break the Java front-end.

The Java front end is already broken because of the overflow
assumptions we _already_ make.  See extract_muldiv.

This is why we should have proper annotations on the tree nodes
so that Java can get the results that they need.


r~

Re: [PATCH] Document arithmetic overflow semantics

[Richard Kenner]

    > Are you really claiming that a program with an uninitialized variable
    > must be compiled in such a way that it produces the same result
    > independent of optimization?

    You got me.  Naturally there are limits.  GCC can't claim that two runs
    of the same executable with an uninitialized variable produce the same
    result.

So then to rephrase the question I asked in my last question, what are those
limits, where do we document them, and how do we decide what they are?

I'm more familiar with the Ada standard than that for C99 and C++ and
there are dozens of places where they describe things that are undefined.
Are you proposing that we look at each of those, choose (by what criteria?)
whether we guarantee that a program that has that particular undefined 
behavior is preserved over optimization, and document our choice somewhere?
And that we do the same for C, C++, Fortran and Java?

If not, precisely *what* are you proposing: I don't understand.

Re: [PATCH] Document arithmetic overflow semantics

[Roger Sayle]

Hi Richard,
> I'm more familiar with the Ada standard than that for C99 and C++ and
> there are dozens of places where they describe things that are undefined.
> Are you proposing that we look at each of those, choose (by what criteria?)
> whether we guarantee that a program that has that particular undefined
> behavior is preserved over optimization, and document our choice somewhere?
> And that we do the same for C, C++, Fortran and Java?
>
> If not, precisely *what* are you proposing: I don't understand.

Again, my concern is not with the front-ends.  I'm proposing that the
GCC tighten up some of the semantics that it uses from its internal
TREE nodes, so that front-end maintainers can decide whether a GCC
node has semantics compatible with those required by the language.

Ada for example, performs all its own real arithmetic because Ada
specifies constraints on precision that aren't documented for GCC's
tree-nodes.  Perhaps, CONST_DOUBLE does what Ada needs, perhaps it
doesn't, but documenting the actual behaviour is a good start.

Similarly, java-tree.def provides its own CONDITIONAL_EXPR because
the semantics it requires may be different from those of C/C++'s
COND_EXPR.

Roger
--

Re: [PATCH] Document arithmetic overflow semantics

[Richard Kenner]

    I believe this generalization is drifting away from the initial
    specific topic.

Sure, but for what I consider a good reason: if we're going to treat
*certain* undefined behavior differently than others we need to:

(1) Be explicit that we are doing that; and
(2) Precisely characterize which behaviors are in each set.

Re: [PATCH] Document arithmetic overflow semantics

[Richard Kenner]

    I completely disagree, and so do GCC's patch reviewers.  The behaviour
    of a program with optimization should always be the same as its behaviour
    without optimization.

Only for correct programs.

Are you really claiming that a program with an uninitialized variable
must be compiled in such a way that it produces the same result independent
of optimization?

Re: [PATCH] Document arithmetic overflow semantics

[Gabriel Dos Reis]

kenner@vlsi1.ultra.nyu.edu (Richard Kenner) writes:

|     I completely disagree, and so do GCC's patch reviewers.  The behaviour
|     of a program with optimization should always be the same as its behaviour
|     without optimization.
| 
| Only for correct programs.
| 
| Are you really claiming that a program with an uninitialized variable
| must be compiled in such a way that it produces the same result independent
| of optimization?

I believe this generalization is drifting away from the initial
specific topic.

-- Gaby

Re: [PATCH] Document arithmetic overflow semantics

[Roger Sayle]

On Thu, 13 Feb 2003, Richard Kenner wrote:
>     I completely disagree, and so do GCC's patch reviewers.  The behaviour
>     of a program with optimization should always be the same as its behaviour
>     without optimization.
>
> Only for correct programs.
>
> Are you really claiming that a program with an uninitialized variable
> must be compiled in such a way that it produces the same result independent
> of optimization?

You got me.  Naturally there are limits.  GCC can't claim that two runs
of the same executable with an uninitialized variable produce the same
result.

Roger
--

Re: [PATCH] Document arithmetic overflow semantics

[Richard Kenner]

    This is a common misunderstanding.  The c-tree.texi not only documents
    the tree nodes that are specific to C and C++, but also those that are
    shared amongst all the front-ends.  

That suggests to me that the file has the wrong name.

Re: [PATCH] Document arithmetic overflow semantics

[Richard Kenner]

    The fact that the behaviour of overflow is undefined in C, C++ and Ada
    does not mean that "overflow cannot occur".  Quite clearly overflows do
    occur, and the optimizers are paralyzed by the semantics in this event.

I think that's backwards.  If program in C, C++, or Ada generates an
overflow, that program is undefined.  That means the optimizer can do
anything it wants to the program, which, in turn, means that the optimizer
can assume that overflow *does not* occur, and that allows a lot more
optimizations.

    Any optimization that concerns overflow will assume a behaviour upon
    overflow.  If the behaviour assumed is anything other than the
    two's-complement overflow, then the optimization is "unsafe" and will
    produce different results to not performing the optimization, as the
    RTL will use two's-complement overflow at run-time.  

Only for erroneous programs, where it's perfectly acceptable to do that.

    I'm not opposed to either adding a bit to the tree structure, or
    introducing a new tree node for trapping arithmetic.  However the
    existing infrastructure is currently sufficient for all of GCC's
    front-ends and back-ends without modification.  Being pragmatic I
    can't see how adding a bit would help, if we never set or never test
    for it.

Well, obviously we have to test for it!

Re: [PATCH] Document arithmetic overflow semantics

[Gabriel Dos Reis]

kenner@vlsi1.ultra.nyu.edu (Richard Kenner) writes:

|     The fact that the behaviour of overflow is undefined in C, C++ and Ada
|     does not mean that "overflow cannot occur".  Quite clearly overflows do
|     occur, and the optimizers are paralyzed by the semantics in this event.
| 
| I think that's backwards.  If program in C, C++, or Ada generates an
| overflow, that program is undefined.  That means the optimizer can do
| anything it wants to the program,

including honoring stringent standards like LIA.  
We ought to be careful about what we do to programs, given C99 requirements
(and C++)'s.

-- Gaby

Re: [PATCH] Document arithmetic overflow semantics

[Roger Sayle]

Hi Richard,
> I think that's backwards.  If program in C, C++, or Ada generates an
> overflow, that program is undefined.  That means the optimizer can do
> anything it wants to the program, which, in turn, means that the optimizer
> can assume that overflow *does not* occur, and that allows a lot more
> optimizations.

I completely disagree, and so do GCC's patch reviewers.  The behaviour
of a program with optimization should always be the same as its behaviour
without optimization.

Consider the case of x << y, where y is larger than the word size of
x.  Nobody would be prepared to constant "x << 98" as just zero.  Its
true that the behaviour is undefined by the language specification,
but that still doesn't mean we can do anything.

Indeed GCC refuses to constant fold  "100 << 98" at compile time, and
performs the shift at run-time to preserve these semantics.  This case
is actually more difficult than two's-complement overflow, as differnent
processors generate different results for the above even when they all
use 32-bit operands.

Hence

int shift(int x, int y) { return x << y; }

int main()
{
  if (shift (100, 98) != (100 << 98))
    abort ();
  return 0;
}


is a test-case that demonstrates that GCC strives to produce identical
behaviour between optimized and unoptimized code, even in the presence
of "undefined behaviour" in the language specification.

I can submit a patch to constant fold x << y to zero, for suitably
large y, if anyone disagrees.  It will of course break the above
test-case, which might no be what a programmer expects.

Roger
--

Re: [PATCH] Document arithmetic overflow semantics

[Joseph S. Myers]

On Thu, 13 Feb 2003, Roger Sayle wrote:

> I can submit a patch to constant fold x << y to zero, for suitably
> large y, if anyone disagrees.  It will of course break the above

I'd prefer a patch that codes it as an abort (or, better yet, records that
this code path cannot be executed - so that given "if (x) y << 200;", we
conclude that x == 0).  We already have precedent for generating an abort
for code that is known to be undefined if ever executed but is allowed in
a strictly conforming program if never executed - va_arg(ap, char).  I
think a patch to generate an abort for this code would be entirely
acceptable, as would one to treat the code as unreachable (but the latter
might be more difficult, since we don't have a tree node saying "this is
unreachable").

-- 
Joseph S. Myers
jsm28@cam.ac.uk

Re: [PATCH] Document arithmetic overflow semantics

[Richard Henderson]

On Thu, Feb 13, 2003 at 07:22:42AM -0700, Roger Sayle wrote:
> Hi Richard,
> > I think that's backwards.  If program in C, C++, or Ada generates an
> > overflow, that program is undefined.  That means the optimizer can do
> > anything it wants to the program, which, in turn, means that the optimizer
> > can assume that overflow *does not* occur, and that allows a lot more
> > optimizations.
> 
> I completely disagree, and so do GCC's patch reviewers.

Huh?  I for one agree with Kenner.  Using the undefinedness of
something to infer that it doesn't happen is well-established.

> The behaviour of a program with optimization should always be the
> same as its behaviour without optimization.

For conformant code, yes.  For undefined code, no.

For a very popular example of this *not* happening for
non-conformant code is type-based aliasing.  This regularly
catches folks by "mis-scheduling" their code.



r~

Re: [PATCH] Document arithmetic overflow semantics

[Roger Sayle]

On Thu, 13 Feb 2003, Richard Henderson wrote:
> > I completely disagree, and so do GCC's patch reviewers.
>
> Huh?  I for one agree with Kenner.  Using the undefinedness of
> something to infer that it doesn't happen is well-established.

I apologise.  I'm sure I've had constant folding optimizations rejected
in the past for assuming overflow semantics.  At the time I posted this
claim, the "-A - B" patch that I was thinking off not only removed
overflows that occured in the original, but also introduces overflows
that didn't occur in the original.  I now realize that this is not
quite the same thing.

I'd previously had several floating point transformations rejected,
until I finally resolved the issue by introducing the flag_signaling_nans
option, that separated out the issues.  And today GCC's optimizers are
much improved for it.  Not that anyone used GCC with sNANs then or now,
but it helped appease the paranoia.

Roger
--

Re: [PATCH] Document arithmetic overflow semantics

[Erik Trulsson]

On Thu, Feb 13, 2003 at 07:22:42AM -0700, Roger Sayle wrote:
> 
> Hi Richard,
> > I think that's backwards.  If program in C, C++, or Ada generates an
> > overflow, that program is undefined.  That means the optimizer can do
> > anything it wants to the program, which, in turn, means that the optimizer
> > can assume that overflow *does not* occur, and that allows a lot more
> > optimizations.
> 
> I completely disagree, and so do GCC's patch reviewers.  The behaviour
> of a program with optimization should always be the same as its behaviour
> without optimization.

Since the behaviour of a program includes things like the time it takes
to execute a program as well as the exact sequence of memory locations
that are read from/written to, and many other similar things this would
imply that optimization is essentially not allowed to do anything.

Optimization is certainly allowed to change the behaviour of a program,
anything else would be just plain silly since the very purpose of
optimization is to change the behaviour of a program (in particular the
execution time of the program.)

What optimization is not allowed to do is change the semantics of a
program, but in the case of undefined behaviour there is no semantics
to preserve and therefore the optimizer can do whatever it damn well
pleases in that case.


-- 
<Insert your favourite quote here.>
Erik Trulsson
ertr1013@student.uu.se

Re: [PATCH] Document arithmetic overflow semantics

[Richard Kenner]

    + For integral types, negation is the same as subtraction from zero.
    + Because the range of two's-complement values in not symmetric, the
    + negation of the maximum negative integer results in the same maximum
    + negative number.

I *really* don't like defining the tree operations as having this overflow
behavior.    I have three major problems with it:

(1) It removes the potential of optimizations that assume such overflow cannot
    occur in languages where it is undefined (C, C++, and Ada).
(2) It represents an implementation difficulty and perhaps cost on machines
    where this behavior is not present (for example, where it traps).
(3) It does not allow representing trapping arithmetic in the three.

My suggestion is to use a bit in either the type (my preference) or the
operation to say whether overflow is defined or not.  There can be a bit in
the operation to require that it trap if it overflow.

Re: [PATCH] Document arithmetic overflow semantics

[Roger Sayle]

Hi Richard,
> I *really* don't like defining the tree operations as having this overflow
> behavior.    I have three major problems with it:
>
> (1) It removes the potential of optimizations that assume such overflow
>     cannot occur in languages where it is undefined (C, C++, and Ada).

The fact that the behaviour of overflow is undefined in C, C++ and Ada
does not mean that "overflow cannot occur".  Quite clearly overflows do
occur, and the optimizers are paralyzed by the semantics in this event.

Leaving behaviour undefined actually limits more optimizations than it
helps.  Any optimization that concerns overflow will assume a behaviour
upon overflow.  If the behaviour assumed is anything other than the
two's-complement overflow, then the optimization is "unsafe" and will
produce different results to not performing the optimization, as the
RTL will use two's-complement overflow at run-time.  And as has been
demonstrated recently, even if the optimization assumes these overflow
semantics, people will argue that it relies on "undefined" behaviour.

I suggest people pay attention to what "undefined" and "implementation
defined" really mean in the ISO C/C++ standards.


> (2) It represents an implementation difficulty and perhaps cost on machines
>     where this behavior is not present (for example, where it traps).
> (3) It does not allow representing trapping arithmetic in the three.

I would suggest that the lines I've added say nothing of whether these
operations trap or not, via "-ftrapv" or "-fnon-call-exceptions".  If
someone else would like to document that behaviour, please feel free
to add a paragraph or two in these locations.

> My suggestion is to use a bit in either the type (my preference) or the
> operation to say whether overflow is defined or not.  There can be a bit
> in the operation to require that it trap if it overflow.

I'm not opposed to either adding a bit to the tree structure, or
introducing a new tree node for trapping arithmetic.  However the
existing infrastructure is currently sufficient for all of GCC's
front-ends and back-ends without modification.  Being pragmatic I
can't see how adding a bit would help, if we never set or never
test for it.

Roger
--

Re: [PATCH] Document arithmetic overflow semantics

[Fergus Henderson]

On 13-Feb-2003, Roger Sayle <roger@www.eyesopen.com> wrote:
> 
> Hi Richard,
> > I *really* don't like defining the tree operations as having this overflow
> > behavior.    I have three major problems with it:
> >
> > (1) It removes the potential of optimizations that assume such overflow
> >     cannot occur in languages where it is undefined (C, C++, and Ada).
> 
> The fact that the behaviour of overflow is undefined in C, C++ and Ada
> does not mean that "overflow cannot occur".  Quite clearly overflows do
> occur, and the optimizers are paralyzed by the semantics in this event.

Optimizers are only paralyzed by such semantics (undefined behaviour on
overflow) if it occurs in their *target* language, and can't be avoided.
If it occurs in their *source* language, then it is a boon for the optimizer.

Of course, many optimizations are done as tree->tree or RTL->RTL passes;
In that case, the target is the same as the source, and so such semantics
can both help (in some cases) and hinder (in others), if the

One way to get the best of both words is to provide bits on each
operation specifying the behaviour on overflow.  The optimizer
can then convert operations with undefined behaviour into
operations with defined behavior if this helps it optimize.

Let me give an example.
Suppose we denote the three variants of "+" as follows:

	+undef		undefined behaviour on overflow
	+wrap		wraps on overflow
	+trap		traps on overflow

`+wrap' is associative, so an optimizer can replace `x +wrap (y +wrap z)'.
with `(x +wrap y) +wrap z'.  But `+undef' is not, so an optimizer cannot
replace `x +undef (y +undef z)' with `(x +undef y) +undef z'.  
However, if the target language supports both kinds, the optimizer can
convert from +undef to +wrap when desired, so it can safely replace
`(x +undef y) +undef z' with `x +wrap (y +wrap z)'.

This is why I think it would be much better to specify the overflow behaviour
by using flag bits on the operations, rather than on the types.

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.

Re: [PATCH] Document arithmetic overflow semantics

[Joe Buck]

On Fri, Feb 14, 2003 at 05:27:46AM +1100, Fergus Henderson wrote:
> One way to get the best of both words is to provide bits on each
> operation specifying the behaviour on overflow.  The optimizer
> can then convert operations with undefined behaviour into
> operations with defined behavior if this helps it optimize.

Exactly: we need to be able to distinguish between operations provided
by the user (which have undefined overflow behavior), and operations
available for mapping to (which have defined overflow behavior that
we can exploit).

> Let me give an example.
> Suppose we denote the three variants of "+" as follows:
> 
> 	+undef		undefined behaviour on overflow
> 	+wrap		wraps on overflow
> 	+trap		traps on overflow
> 
> `+wrap' is associative, so an optimizer can replace `x +wrap (y +wrap z)'.
> with `(x +wrap y) +wrap z'.  But `+undef' is not, so an optimizer cannot
> replace `x +undef (y +undef z)' with `(x +undef y) +undef z'.  
> However, if the target language supports both kinds, the optimizer can
> convert from +undef to +wrap when desired, so it can safely replace
> `(x +undef y) +undef z' with `x +wrap (y +wrap z)'.
> 
> This is why I think it would be much better to specify the overflow behaviour
> by using flag bits on the operations, rather than on the types.

I find this argument convincing.

Re: [PATCH] Document arithmetic overflow semantics

[Richard Earnshaw]

> On Fri, Feb 14, 2003 at 05:27:46AM +1100, Fergus Henderson wrote:
> > One way to get the best of both words is to provide bits on each
> > operation specifying the behaviour on overflow.  The optimizer
> > can then convert operations with undefined behaviour into
> > operations with defined behavior if this helps it optimize.
> 
> Exactly: we need to be able to distinguish between operations provided
> by the user (which have undefined overflow behavior), and operations
> available for mapping to (which have defined overflow behavior that
> we can exploit).
> 
> > Let me give an example.
> > Suppose we denote the three variants of "+" as follows:
> > 
> > 	+undef		undefined behaviour on overflow
> > 	+wrap		wraps on overflow
> > 	+trap		traps on overflow
> > 
> > `+wrap' is associative, so an optimizer can replace `x +wrap (y +wrap z)'.
> > with `(x +wrap y) +wrap z'.  But `+undef' is not, so an optimizer cannot
> > replace `x +undef (y +undef z)' with `(x +undef y) +undef z'.  
> > However, if the target language supports both kinds, the optimizer can
> > convert from +undef to +wrap when desired, so it can safely replace
> > `(x +undef y) +undef z' with `x +wrap (y +wrap z)'.
> > 
> > This is why I think it would be much better to specify the overflow behaviour
> > by using flag bits on the operations, rather than on the types.
> 
> I find this argument convincing.

Rather than having lots of differnent plus nodes, why not have plus mean 
the mathematical operation (done in "infinite" precision and then define a 
series of "reduction" nodes that can be applied to it.

Examples would be

	wrap		Reduce to 2's complement
	trap		trap on overflow
	sat		Saturate
	
That way a C expression such as

x = a + b + c;

can be compiled as

	x = truncop (plus (plus (a, b), c))

And a language which applied specific semantics to the above could expand 
this to

	x = truncop (plus (truncop (plus (a, b)), c))

R.

Re: [PATCH] Document arithmetic overflow semantics

[Richard Henderson]

On Fri, Feb 14, 2003 at 05:27:46AM +1100, Fergus Henderson wrote:
> `+wrap' is associative ...  But `+undef' is not

Certainly it is.  It's undefined.  We can get whatever results
are most convenient.


r~

Re: [PATCH] Document arithmetic overflow semantics

[Roger Sayle]

On Thu, 13 Feb 2003, Richard Henderson wrote:
> On Fri, Feb 14, 2003 at 05:27:46AM +1100, Fergus Henderson wrote:
> > `+wrap' is associative ...  But `+undef' is not
>
> Certainly it is.  It's undefined.  We can get whatever results
> are most convenient.

Alas not.  a +undef (b +undef c) is not guaranteed to be the same
as (a +undef b) +undef c!  Consider a = 100, b = 30, c = -50 for
signed chars.  Notice that the first expression doesn't overflow,
but the second does, invoking the "we can get whatever results
are most convenient" instaed of being guaranteed to produce 80.


Undefined overflow is so non-intuitive, anyone can make a mistake.

Roger
--

Re: [PATCH] Document arithmetic overflow semantics

[David Carlton]

On Thu, 13 Feb 2003 14:24:14 -0800, Richard Henderson <rth@redhat.com> said:
> On Fri, Feb 14, 2003 at 05:27:46AM +1100, Fergus Henderson wrote:

>> `+wrap' is associative ...  But `+undef' is not

> Certainly it is.  It's undefined.

I don't think so.  The expressions

  INT_MAX +undef (1 +undef -1)

and

  (INT_MAX +undef 1) +undef -1

are different.  The former is required to be INT_MAX; the latter is
undefined behavior.  So if we might later apply optimizations that are
only valid when we hit undefined behavior, we can't transform the
former into the latter.  (Though there is a solution: we could
transform +undef into +wrap when associating.  That should be safe, I
think?)

I would be curious to see situations where +undef and -undef open up
interesting optimization possibilities.  It seems to me that making +
and - undefined is of a different nature than making * undefined; and
of course the earlier example of (A*2)/2 that profits from making *
undefined doesn't have a direct analog with + and -.  And I suspect
that there's a lot more code out there that depends on + and -
behaving the same for signed and unsigned than there is code that
depends on * behaving the same for signed and unsigned.

David Carlton
carlton@math.stanford.edu

Re: [PATCH] Document arithmetic overflow semantics

[Nathan Sidwell]

Fergus Henderson wrote:

> Optimizers are only paralyzed by such semantics (undefined behaviour on
> overflow) if it occurs in their *target* language, and can't be avoided.
> If it occurs in their *source* language, then it is a boon for the optimizer.
> 
> Of course, many optimizations are done as tree->tree or RTL->RTL passes;
> In that case, the target is the same as the source, and so such semantics
> can both help (in some cases) and hinder (in others), if the
thank you, I finally understand what this discussion is all about.

> One way to get the best of both words is to provide bits on each
> operation specifying the behaviour on overflow.  The optimizer
> can then convert operations with undefined behaviour into
> operations with defined behavior if this helps it optimize.
> 
> Let me give an example.
> Suppose we denote the three variants of "+" as follows:
> 
> 	+undef		undefined behaviour on overflow
> 	+wrap		wraps on overflow
> 	+trap		traps on overflow
This makes sense. I think you need
	op this_never_overflows
	op dont_care
	op modulo
	op trap
	op saturate (maybe).

optimizers are thus free to convert the first two into the final three. They
are also know that input values must be bounded such that the first one never
overflows.

> This is why I think it would be much better to specify the overflow behaviour
> by using flag bits on the operations, rather than on the types.
FWIW, I concur.

nathan
-- 
Nathan Sidwell    ::   http://www.codesourcery.com   ::     CodeSourcery LLC
          The voices in my head said this was stupid too
nathan@codesourcery.com : http://www.cs.bris.ac.uk/~nathan/ : nathan@acm.org

Re: [PATCH] Document arithmetic overflow semantics

[Fergus Henderson]

On 13-Feb-2003, Nathan Sidwell <nathan@codesourcery.com> wrote:
> Fergus Henderson wrote:
> >Suppose we denote the three variants of "+" as follows:
> >
> >	+undef		undefined behaviour on overflow
> >	+wrap		wraps on overflow
> >	+trap		traps on overflow
>
> This makes sense. I think you need
> 	op this_never_overflows
> 	op dont_care
> 	op modulo
> 	op trap
> 	op saturate (maybe).

Yes, your "op this_never_overflows" is the same as my "op undef", but
if you want to represent Ada 95 bounded errors, you need another
alternative -- your "op dont_care".

The difference between "op dont_care" and "op this_never_overflows"
is that for "op dont_care", if overflow occurs then you get either an
unspecified result or a trap, but for "op this_never_overflows", you
get undefined behaviour (the generated code is allowed to do anything).

Even for C, it might make sense to have a compilation option in which
C operations were mapped to "op dont_care" rather than "op undef".
This would be useful for compiling security-critical software.
Perhaps it should even be the default.

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.

Re: [PATCH] Document arithmetic overflow semantics

[Geert Bosch]

On Friday, Feb 14, 2003, at 02:12 America/New_York, Fergus Henderson 
wrote:

> Even for C, it might make sense to have a compilation option in which
> C operations were mapped to "op dont_care" rather than "op undef".
> This would be useful for compiling security-critical software.
> Perhaps it should even be the default.

Yes, it should be the default. Having the compiler reason from
undefined behavior really can be quite nasty, especially when
this information back-propagates (see Robert's password example).
This is indeed the reason that Ada 95 introduced bounded errors,
where the language allows the implementation to pick any value
in the base range of the type or raise an exception.

Essentially, this is what people expect when reading an
uninitialized variable. Even though a language standard
may not define a behavior at all, choosing a reasonable
set of possible outcomes becomes a quality of implementation
issue.

   -Geert

Re: [PATCH] Document arithmetic overflow semantics

[Joseph S. Myers]

On Fri, 14 Feb 2003, Geert Bosch wrote:

> This is indeed the reason that Ada 95 introduced bounded errors,
> where the language allows the implementation to pick any value
> in the base range of the type or raise an exception.

But in the A * 2 / 2 case, if there is overflow then the "value" selected 
for A * 2 is *not* a value of the signed type of A, and A * 2 / 2 gets a 
value that cannot be the value of dividing a signed integer by 2.  (Note 
that this optimization is a case that could actually be useful in the 
presence of macros.)  It would be reasonable enough to take code

int A, B;
/* ... */
B = A * 2 / 2;
if (B > 2000000000) { /* ... */ }
/* subsequent code using B */

and reason that B, the result of dividing an int by 2, cannot be > 
2000000000, so remove the if, but for the subsequent code compute B using 
the folding of A * 2 / 2, having a value > 2000000000.  Both optimizations 
are individually reasonable in the presence of macros or generated code, 
and the combined effect is that no single value is assumed for the result 
of the undefined code.

For the specific cases where we can *prove* that particular code, if
executed, must be undefined (use of a variable that cannot have been
initialized, shift by constant greater that width of type, A * 1000000 *
1000000, ...), the best option may be to generate a trap (as already done
for some such cases), and a mandatory warning if we can't also prove that
the code in question isn't executed (it may well be contained inside an if
(0)).

-- 
Joseph S. Myers
jsm28@cam.ac.uk

Re: [PATCH] Document arithmetic overflow semantics

[Joseph S. Myers]

On Fri, 14 Feb 2003, Fergus Henderson wrote:

> Even for C, it might make sense to have a compilation option in which
> C operations were mapped to "op dont_care" rather than "op undef".
> This would be useful for compiling security-critical software.
> Perhaps it should even be the default.

I think we should recommend using "op trap" for security-critical
software.  There is more runtime cost, but if an overflow does occur and
isn't trapped it is very likely to be an exploitable security hole.

-- 
Joseph S. Myers
jsm28@cam.ac.uk

Re: [PATCH] Document arithmetic overflow semantics

[Joe Buck]

On Thu, Feb 13, 2003 at 08:08:30AM -0500, Richard Kenner wrote:
>     + For integral types, negation is the same as subtraction from zero.
>     + Because the range of two's-complement values in not symmetric, the
>     + negation of the maximum negative integer results in the same maximum
>     + negative number.
> 
> I *really* don't like defining the tree operations as having this overflow
> behavior.    I have three major problems with it:
> 
> (1) It removes the potential of optimizations that assume such overflow cannot
>     occur in languages where it is undefined (C, C++, and Ada).

In C, it is frequently the case that defining the overflow behavior of
signed integer in this way makes more optimizations possible.  For one
thing, it makes addition and multiplication associative.  Without such
an assumption, you can't turn (a+b)+c into a+(b+c), because the overflows
might be different.

> (2) It represents an implementation difficulty and perhaps cost on machines
>     where this behavior is not present (for example, where it traps).

I'd hate to implement C on a machine that forces a trap on integer
overflows.

> (3) It does not allow representing trapping arithmetic in the three.
> 
> My suggestion is to use a bit in either the type (my preference) or the
> operation to say whether overflow is defined or not.  There can be a bit in
> the operation to require that it trap if it overflow.

If this were done, then it would be a very good idea to mark the C int
type as having defined overflow behavior, with the possibility of changing
this if someone wants to port to a strange machine.

Re: [PATCH] Document arithmetic overflow semantics

[Richard Earnshaw]

> In C, it is frequently the case that defining the overflow behavior of
> signed integer in this way makes more optimizations possible.  For one
> thing, it makes addition and multiplication associative.  Without such
> an assumption, you can't turn (a+b)+c into a+(b+c), because the overflows
> might be different.

The same is also true if the operation saturates.  I don't recall anything 
in the C89 standard that says that signed arithmetic can't be implemented 
on a saturating arithmetic machine.

R.

Re: [PATCH] Document arithmetic overflow semantics

[Florian Weimer]

kenner@vlsi1.ultra.nyu.edu (Richard Kenner) writes:

> behavior.    I have three major problems with it:
>
> (1) It removes the potential of optimizations that assume such overflow cannot
>     occur in languages where it is undefined (C, C++, and Ada).

The last time I asked, I was told that GCC already does not check in
some cases if arithmetic overflow can occur and still performs some
optimizations which assume that no overflow occurs.