Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics?

Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics?

[Paul Schlie]

Given that the formal implication of GCC's choice not define signed integer
overflow semantics as being other than undefined will be to guaranteed that
all programs, with reachable signed integer arithmetic operations which can
not warrant that their respective operand expressions are recursively
constrained to each others corresponding additive, multiplicative inverse,
may produce unpredictably arbitrary results and/or behavior by default;
might it be a good idea to publish a formal rule/warning, as it's a good
thing to know and not particularly obvious:

- Signed integer types and/or arithmetic operations should not be utilized
  in GCC compiled programs (or any program desired to be strictly portable,
  even if it's values are known or desired to be constrained to signed
  integers) unless it is provably known that the corresponding operands to
  all signed arithmetic operation which may use their values directly and/or
  indirectly are correspondingly recursively constrained to their respective
  additive or multiplicative inverse. As GCC complied programs may produce
  arbitrary results and/or behavior in such instances by default, as enabled
  by the C/C++ standards.

Or more generally as C/C++'s default integer promotion rules may convert
unsigned integer types to signed operand types if it's other operand is
signed, should the general rule be broadened to discourage the use of all
integer variable types unless all signed integer operations which may
utilize their values directly or indirectly are provably known to have
their correspondingly operands constrained to their respective additive or
multiplicative inverse value ranges?

(or if by default it warrants otherwise, maybe that should be stated?)

Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics?

[Paul Schlie]

(sorry, meant additive/multiplicative inverse +/- MAX/MIN_<TYPE> value;
 but even that's wrong, which is why it seems that leaving signed overflow
 as being undefined is such a bad idea, as it becomes correspondingly very
 difficult to even try determine if a program is warranted to have a
 deterministic behavior, or potentially a completely arbitrary one.)

> Given that the formal implication of GCC's choice not define signed integer
> overflow semantics as being other than undefined will be to guaranteed that
> all programs, with reachable signed integer arithmetic operations which can
> not warrant that their respective operand expressions are recursively
> constrained to each others corresponding additive or multiplicative inverse,
> may produce unpredictably arbitrary results and/or behavior by default; might
> it be a good idea to publish a formal rule/warning, as it's a good thing to
> know and not particularly obvious:
> 
> - Signed integer types and/or arithmetic operations should not be utilized
>   in GCC compiled programs (or any program desired to be strictly portable,
>   even if it's values are known or desired to be constrained to signed
>   integers) unless it is provably known that the corresponding operands to
>   all signed arithmetic operation which may use their values directly and/or
>   indirectly are correspondingly recursively constrained to their respective
>   additive or multiplicative inverse. As GCC complied programs may produce
>   arbitrary results and/or behavior in such instances by default, as enabled
>   by the C/C++ standards.
> 
> Or more generally as C/C++'s default integer promotion rules may convert
> unsigned integer types to signed operand types if it's other operand is
> signed, should the general rule be broadened to discourage the use of all
> integer variable types unless all signed integer operations which may utilize
> their values directly or indirectly are provably known to have
> their correspondingly operands constrained to their respective additive or
> multiplicative inverse value ranges?
> 
> (or if by default it warrants otherwise, maybe that should be stated?)

Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics?

[Joe Buck]

On Thu, Jun 30, 2005 at 03:14:54PM -0400, Paul Schlie wrote:
> Given that the formal implication of GCC's choice not define signed integer
> overflow semantics as being other than undefined will be to guaranteed that
> all programs, with reachable signed integer arithmetic operations which can
> not warrant that their respective operand expressions are recursively
> constrained to each others corresponding additive, multiplicative inverse,
> may produce unpredictably arbitrary results and/or behavior by default;
> might it be a good idea to publish a formal rule/warning, as it's a good
> thing to know and not particularly obvious:

The formal rule is called the ISO C standard.  It's the only one you're
going to get.

> - Signed integer types and/or arithmetic operations should not be utilized
>   in GCC compiled programs (or any program desired to be strictly portable,
>   even if it's values are known or desired to be constrained to signed
>   integers) unless it is provably known that the corresponding operands to
>   all signed arithmetic operation which may use their values directly and/or
>   indirectly are correspondingly recursively constrained to their respective
>   additive or multiplicative inverse. As GCC complied programs may produce
>   arbitrary results and/or behavior in such instances by default, as enabled
>   by the C/C++ standards.

Your alleged required condition is way too strict, to the point of being
offensive, and you are falsely implying that GCC is aggressively doing
what other compilers do not.

The writer of a C program (or C++) needs to ensure that integer overflow
does not occur when using signed types.  If she fails to do this, we can't
make any promise about the results, though in some cases the program might
do what the user expects.  Any promise we did make would inevitably harm
the code quality for those who do write correct C programs, by preventing
many common loops from being optimized.  However, because we don't
generate traps, in many cases programs that have overflows produce correct
results anyway.  It's just that we cannot promise that this will always be
so.

If the user does need the mathematical properties of arithmetic modulo
2**32 (8 or 16 or 64), he can readily obtain this by using unsigned types.
The only correct way to write a bignum package in C, for example, is to
use an unsigned type to store each word.

Given your biases, you might be happier with Java as a language (than C or
C++).  The Java language designers decided to strictly define many cases
that are not defined in C (example: the order side effects is always
strictly left to right, floating point is always IEEE, etc., integer
overflow wraps around).  There is a performance penalty for this, but
given the "write once, run everywhere" goal it was felt that it's worth
paying this price.

Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics?

[Gabriel Dos Reis]

Joe Buck <Joe.Buck@synopsys.COM> writes:

[...]

| Given your biases, you might be happier with Java as a language (than C or
| C++).  The Java language designers decided to strictly define many cases
| that are not defined in C (example: the order side effects is always
| strictly left to right, floating point is always IEEE, etc., integer
| overflow wraps around).  There is a performance penalty for this, but
| given the "write once, run everywhere" goal it was felt that it's worth
| paying this price.

Well, in the case of C++ I can say that the designer and original
implementor of C++ is quite amazed as to how people interpret
"undefined behaviour" in this thread.  I don't think he would suggest
that people go to use Java instead.

-- Gaby

Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics?

[Joe Buck]

On Fri, Jul 01, 2005 at 12:25:58AM +0200, Gabriel Dos Reis wrote:
> Joe Buck <Joe.Buck@synopsys.COM> writes:
> 
> [...]
> 
> | Given your biases, you might be happier with Java as a language (than C or
> | C++).  The Java language designers decided to strictly define many cases
> | that are not defined in C (example: the order side effects is always
> | strictly left to right, floating point is always IEEE, etc., integer
> | overflow wraps around).  There is a performance penalty for this, but
> | given the "write once, run everywhere" goal it was felt that it's worth
> | paying this price.
> 
> Well, in the case of C++ I can say that the designer and original
> implementor of C++ is quite amazed as to how people interpret
> "undefined behaviour" in this thread. 

Really?  You've talked to Stroustrup?  Can you be more specific?
(If you're talking about the regularly repeated claim that "undefined
behavior" means the compiler can delete all your files, hack your bank
account, and send all your money to the GCC team, well, that's just
hyperbole not to be taken seriously).

> I don't think he would suggest
> that people go to use Java instead.

Are you claiming that Stroustrup would want to sacrifice loop optimization
to make Paul happy?

Undefined behavior doesn't mean that we should attempt to arbitrarily
punish those who cross the line; that's why I don't think forcing integer
overflows to trap (at least by default) is a good idea.  In many cases,
"assume no overflow, but don't trap" can produce a better result than
"assume wrap" does, as in the example I gave before.

Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics?

[Gabriel Dos Reis]

Joe Buck <Joe.Buck@synopsys.COM> writes:

| On Fri, Jul 01, 2005 at 12:25:58AM +0200, Gabriel Dos Reis wrote:
| > Joe Buck <Joe.Buck@synopsys.COM> writes:
| > 
| > [...]
| > 
| > | Given your biases, you might be happier with Java as a language (than C or
| > | C++).  The Java language designers decided to strictly define many cases
| > | that are not defined in C (example: the order side effects is always
| > | strictly left to right, floating point is always IEEE, etc., integer
| > | overflow wraps around).  There is a performance penalty for this, but
| > | given the "write once, run everywhere" goal it was felt that it's worth
| > | paying this price.
| > 
| > Well, in the case of C++ I can say that the designer and original
| > implementor of C++ is quite amazed as to how people interpret
| > "undefined behaviour" in this thread. 
| 
| Really?  You've talked to Stroustrup?

I work with him on daily basis, and as a matter of fact we've discussed
the heart of this topic of this thread yesterday over lunch.  But, as
much as I hate argument by authority I could not let this discussion
goes on the slope it is taking without saying what I understood from
discussion with him on the topic.  It wasn't meant as a proof.  Just a
data point.  Of course, it is far preferable he speaks for himself but
it is hard to have him take part of a debate where extreme abstract
arguments are more dominant than balance between two apparant
conflicting goals. And that is, I guess, a wise thing to do just as
core developers like RTH may have a say on this very issue :-) 

| Can you be more specific?

yes, see below.

| (If you're talking about the regularly repeated claim that "undefined
| behavior" means the compiler can delete all your files, hack your bank
| account, and send all your money to the GCC team, well, that's just
| hyperbole not to be taken seriously).

as you may correctly guess he is familiar with those rethorical figures. 

| > I don't think he would suggest
| > that people go to use Java instead.
| 
| Are you claiming that Stroustrup would want to sacrifice loop optimization
| to make Paul happy?

No, I'm not claiming that.  But, on the other hand he does not believe
engineering decisions for useful compilers should be primarily based on
SPEC numbers for example, or primarily driven by the best
optimizations without some considerations on the impacts and
"practices" and expectations.  And he is not claiming it is easy :-)

What I'm claiming is that he thinks "undefined behaviour" in the
standard should not be taken as meaning "go to hell" (or punishment to
borrow words from you) or absolute liberty for compiler writers to do
just about everything that is imaginable, regardless of expectations.
In other words, it is a question of balance.  As, an example, he
illustrated the issue with the story -- quickly classified as "legend" by
Robert Dewar -- about the best C optimizing compilers that miscompiled
the Unix kernel that nobody wanted to use in practice (even if it
would blow up any other competing compiler) and the company
running out of business.  (Interestingly, it was also predictated that
Robert would react ;-))

| Undefined behavior doesn't mean that we should attempt to arbitrarily
| punish those who cross the line; that's why I don't think forcing integer
| overflows to trap (at least by default) is a good idea.  In many cases,
| "assume no overflow, but don't trap" can produce a better result than
| "assume wrap" does, as in the example I gave before.

Yes, I understand.

I just don't think the answer would be to tell Paul to go to Java,
even though that would have the side effect of closing the already
long discussion :-)  Correctness and efficiency is important to us.
GCC is of great interest to us too.

-- Gaby

Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics?

[Andrew Pinski]

On Jun 30, 2005, at 8:48 PM, Gabriel Dos Reis wrote:

> | Really?  You've talked to Stroustrup?
>
> I work with him on daily basis, and as a matter of fact we've discussed
> the heart of this topic of this thread yesterday over lunch.  But, as
> much as I hate argument by authority I could not let this discussion
> goes on the slope it is taking without saying what I understood from
> discussion with him on the topic.  It wasn't meant as a proof.  Just a
> data point.  Of course, it is far preferable he speaks for himself but
> it is hard to have him take part of a debate where extreme abstract
> arguments are more dominant than balance between two apparant
> conflicting goals. And that is, I guess, a wise thing to do just as
> core developers like RTH may have a say on this very issue :-)

But the reason question is why make it an undefined behavior instead of
an implementation defined?  This would have made it clearer instead of
allowing the compiler not document what happens.  Or is C++
just following C here?  In which case it might be better to ask the C
committee why it was done this way and real definition of undefined for
this case?

-- Pinski

Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics?

[Gabriel Dos Reis]

Andrew Pinski <pinskia@physics.uc.edu> writes:

| On Jun 30, 2005, at 8:48 PM, Gabriel Dos Reis wrote:
| 
| > | Really?  You've talked to Stroustrup?
| >
| > I work with him on daily basis, and as a matter of fact we've discussed
| > the heart of this topic of this thread yesterday over lunch.  But, as
| > much as I hate argument by authority I could not let this discussion
| > goes on the slope it is taking without saying what I understood from
| > discussion with him on the topic.  It wasn't meant as a proof.  Just a
| > data point.  Of course, it is far preferable he speaks for himself but
| > it is hard to have him take part of a debate where extreme abstract
| > arguments are more dominant than balance between two apparant
| > conflicting goals. And that is, I guess, a wise thing to do just as
| > core developers like RTH may have a say on this very issue :-)
| 
| But the reason question is why make it an undefined behavior instead of
| an implementation defined?

I cannot tell you exactly why it was made undefined behaviour.  But,
I can tell you from experience working in the C++ committee that there
may be various reasons why something is left undefined (including
oversight), not just because the committee thought it would be fun.
In this specific case, I think (but I'm not 100% sure) it is a carry
over from C90 (like many other "curious" cases). 

-- Gaby

Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics?

[Joe Buck]

On Thu, Jun 30, 2005 at 09:02:48PM -0400, Andrew Pinski wrote:
> But the reason question is why make it an undefined behavior instead of
> an implementation defined?  This would have made it clearer instead of
> allowing the compiler not document what happens.  Or is C++
> just following C here?  In which case it might be better to ask the C
> committee why it was done this way and real definition of undefined for
> this case?

I already showed you the answer: loop optimization works better if you
can ignore overflow.

How much do you want to pay for "implementation defined"?  If you specify
the behavior of overflow precisely, then every optimizer in GCC must
preserve this behavior.  That has a high cost.

Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics?

[Gabriel Dos Reis]

Joe Buck <Joe.Buck@synopsys.COM> writes:

| On Thu, Jun 30, 2005 at 09:02:48PM -0400, Andrew Pinski wrote:
| > But the reason question is why make it an undefined behavior instead of
| > an implementation defined?  This would have made it clearer instead of
| > allowing the compiler not document what happens.  Or is C++
| > just following C here?  In which case it might be better to ask the C
| > committee why it was done this way and real definition of undefined for
| > this case?
| 
| I already showed you the answer: loop optimization works better if you
| can ignore overflow.

There are various ways to work within "loop optimization" assumptions.
Assuming undefined behaviour is not the only one.  In fact, given the
fact that the natural integer type for indices is "int" and not
"unsigned" and the known dislike of the original implementer of
C++ for "unsigned", it is legitimate to question whether that is "the
answer".  I think that can be an "a posteriori" justification, but I'm
not sure that is "the answer".

-- Gaby

Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics?

[Daniel Berlin]

On Fri, 2005-07-01 at 03:39 +0200, Gabriel Dos Reis wrote:
> Joe Buck <Joe.Buck@synopsys.COM> writes:
> 
> | On Thu, Jun 30, 2005 at 09:02:48PM -0400, Andrew Pinski wrote:
> | > But the reason question is why make it an undefined behavior instead of
> | > an implementation defined?  This would have made it clearer instead of
> | > allowing the compiler not document what happens.  Or is C++
> | > just following C here?  In which case it might be better to ask the C
> | > committee why it was done this way and real definition of undefined for
> | > this case?
> | 
> | I already showed you the answer: loop optimization works better if you
> | can ignore overflow.
> 
> There are various ways to work within "loop optimization" assumptions.

Gaby, if you have plans to do what nobody else has had any real luck
doing for 10 years in compilers in any practical way, which is proving
the iteration count of loops in the presence of overflow, please share.

It's possible, but all methods i'm aware that even attempt it are
incredibly expensive (exponential) in every case.

This isn't about SPEC numbers, it's about every single piece of
Numerical C, Fortran, and C++ i've ever seen.


--Dan

Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics?

[Gabriel Dos Reis]

Daniel Berlin <dberlin@dberlin.org> writes:

| On Fri, 2005-07-01 at 03:39 +0200, Gabriel Dos Reis wrote:
| > Joe Buck <Joe.Buck@synopsys.COM> writes:
| > 
| > | On Thu, Jun 30, 2005 at 09:02:48PM -0400, Andrew Pinski wrote:
| > | > But the reason question is why make it an undefined behavior instead of
| > | > an implementation defined?  This would have made it clearer instead of
| > | > allowing the compiler not document what happens.  Or is C++
| > | > just following C here?  In which case it might be better to ask the C
| > | > committee why it was done this way and real definition of undefined for
| > | > this case?
| > | 
| > | I already showed you the answer: loop optimization works better if you
| > | can ignore overflow.
| > 
| > There are various ways to work within "loop optimization" assumptions.
| 
| Gaby, if you have plans to do what nobody else has had any real luck
| doing for 10 years in compilers in any practical way, which is proving
| the iteration count of loops in the presence of overflow, please share.

As we have briefly discussed in mails, the most critical part of the
issue seems to be what can be assumed for loop variables.  I countend
that for many if not most practical loops, the variable can be assumed
not to overflow and apply the transformation.  But we need not apply
"undefined behaviour" to all other cases; only for those
"well-written" loop and loop variables. In summary, if user's loop is
well-written then he will benefit from the transformation. 
That will cover already a good set of common loops.

There are of course coner and pathological cases, but I don't think we
should worry too much about missing them.  Let's first cover the
structured loops, and address the contorsed ones later if they become
really important. 

This is why I suggested earlier whether you'd be happy with letting
user specify through a switch that his loops behave well.  Some
counter-examples were produced, but after some thoughts I think that
if user specifies through switch that his loops behave well but write
such deceiving codes then, well, he looses.


-- Gaby

Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics?

[Andrew Pinski]

On Jul 1, 2005, at 12:06 AM, Gabriel Dos Reis wrote:
>
> There are of course coner and pathological cases, but I don't think we
> should worry too much about missing them.  Let's first cover the
> structured loops, and address the contorsed ones later if they become
> really important.

And I just submitted a patch for one of those corner/pathological cases
and it actually does improve code, how much I don't know because I don't
have access to any benchmark to test on.  If someone wants to test it,
they will most likely find it, it does in fact improve code.

Also knowing in let say fold if the variable is a loop index or not is
actually not trivial.

Another testcase where we will fail out at if we take the view you want
to take is:

int f(int i)
{
   return (i - 1) > i;
}

Which is always false if overflow is undefined and not considered
wrapping and this shows up in fortran code even though the person did 
not
write it out explicitly:
SUBROUTINE d ( a, b,n)
   IMPLICIT NONE
   INTEGER :: n
   REAL,DIMENSION(n) :: a
   REAL,DIMENSION(n) :: b
   b(n-2:n) = sqrt(a(n-2:n))
END SUBROUTINE d

And this is now done in two different places, fold and simplify-rtx
(even though fold does not catch the fortran one as we need a tree
combiner for that).
And yes I actually reduced that testcase from real fortran code (I
forgot which one right now).

-- Pinski

Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics?

[Gabriel Dos Reis]

Andrew Pinski <pinskia@physics.uc.edu> writes:

| On Jul 1, 2005, at 12:06 AM, Gabriel Dos Reis wrote:
| >
| > There are of course coner and pathological cases, but I don't think we
| > should worry too much about missing them.  Let's first cover the
| > structured loops, and address the contorsed ones later if they become
| > really important.
| 
| And I just submitted a patch for one of those corner/pathological cases
| and it actually does improve code, how much I don't know because I don't
| have access to any benchmark to test on.  If someone wants to test it,
| they will most likely find it, it does in fact improve code.
| 
| Also knowing in let say fold if the variable is a loop index or not is
| actually not trivial.
| 
| Another testcase where we will fail out at if we take the view you want
| to take is:

As I said, if you let user tell you that his loop behaves well, i.e.
bounds do not rely on wrapping semantics, and yet he writes his loop to
deceive the compiler, then he loses.  Let him choose his own poinson,
don't think you have to choose it for him.

-- Gaby

Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics?

[Andrew Pinski]

On Jul 1, 2005, at 12:49 AM, Gabriel Dos Reis wrote:

>
> As I said, if you let user tell you that his loop behaves well, i.e.
> bounds do not rely on wrapping semantics, and yet he writes his loop to
> deceive the compiler, then he loses.  Let him choose his own poinson,
> don't think you have to choose it for him.

They already can, that is what -fwrapv is for.  If you ignore that 
there is
already a flag for this, then fine but there is already a flag for 
this, just
like there is already a flag for disabling C/C++ aliasing rules.

-- Pinski

Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics?

[Gabriel Dos Reis]

Andrew Pinski <pinskia@physics.uc.edu> writes:

| On Jul 1, 2005, at 12:49 AM, Gabriel Dos Reis wrote:
| 
| >
| > As I said, if you let user tell you that his loop behaves well, i.e.
| > bounds do not rely on wrapping semantics, and yet he writes his loop to
| > deceive the compiler, then he loses.  Let him choose his own poinson,
| > don't think you have to choose it for him.
| 
| They already can, that is what -fwrapv is for.

No, you completely missed the point and it would help if you read
through carefully.  The choice was about letting user tell you what he
knows/assumes about his loop bounds.  Not applying uniformly the
wrapping semantics.  

(Not counting the fact that it was pointed out -fwrapv is useful as is).

-- Gaby

Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics?

[Robert Dewar]

Gabriel Dos Reis wrote:

> As we have briefly discussed in mails, the most critical part of the
> issue seems to be what can be assumed for loop variables.  I countend
> that for many if not most practical loops, the variable can be assumed
> not to overflow and apply the transformation.  But we need not apply
> "undefined behaviour" to all other cases; only for those
> "well-written" loop and loop variables. In summary, if user's loop is
> well-written then he will benefit from the transformation. 
> That will cover already a good set of common loops.

Note that the lack of a FOR loop in C adds to the problems here. In
languages with FOR loops, this issue comes up very explicitly, but
at the code generation level, you have to be careful to generate
code that deals with the boundary cases correctly.

Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics?

[Gabriel Dos Reis]

Robert Dewar <dewar@adacore.com> writes:

| Gabriel Dos Reis wrote:
| 
| > As we have briefly discussed in mails, the most critical part of the
| > issue seems to be what can be assumed for loop variables.  I countend
| > that for many if not most practical loops, the variable can be assumed
| > not to overflow and apply the transformation.  But we need not apply
| > "undefined behaviour" to all other cases; only for those
| > "well-written" loop and loop variables. In summary, if user's loop is
| > well-written then he will benefit from the transformation. That will
| > cover already a good set of common loops.
| 
| Note that the lack of a FOR loop in C adds to the problems here. In

This is why I think a switch is useful here.  The programmer may know
more about his/her loops than the current GCC infrastructure may prove.

Furthermore, the blanket statement of lack of a "FOR loop" does not
preclude existence of properly writeen FOR loop.   We should be able
to do conservative analysis and catch those.  If, User writes

   for (int i = min; i < max; ++i)
       ....

and i, min and max don't change in the body, no matter what you think
of C's general "for" not being a FOR loop, the above is a FOR loop.

-- Gaby

Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics?

[Robert Dewar]

Gabriel Dos Reis wrote:
> 
>    for (int i = min; i < max; ++i)
>        ....
> 
> and i, min and max don't change in the body, no matter what you think
> of C's general "for" not being a FOR loop, the above is a FOR loop.

But this normal paradigm for representing a FOR loop does not work for
all possible ranges, that's precisely the trouble!

Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics?

[Joe Buck]

On Sat, Jul 02, 2005 at 07:15:17PM -0400, Robert Dewar wrote:
> Gabriel Dos Reis wrote:
> >
> >   for (int i = min; i < max; ++i)
> >       ....
> >
> >and i, min and max don't change in the body, no matter what you think
> >of C's general "for" not being a FOR loop, the above is a FOR loop.
> 
> But this normal paradigm for representing a FOR loop does not work for
> all possible ranges, that's precisely the trouble!

Yes, there's a problem if the maximum value of i is intended to be
INT_MAX.  There's a more common problem with

	for (unsigned i = array_size-1; i >= 0; --i)
	    ...

which, of course, doesn't work because unsigned values are always
greater than zero.

Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics?

[Gabriel Dos Reis]

Joe Buck <Joe.Buck@synopsys.COM> writes:

| On Sat, Jul 02, 2005 at 07:15:17PM -0400, Robert Dewar wrote:
| > Gabriel Dos Reis wrote:
| > >
| > >   for (int i = min; i < max; ++i)
| > >       ....
| > >
| > >and i, min and max don't change in the body, no matter what you think
| > >of C's general "for" not being a FOR loop, the above is a FOR loop.
| > 
| > But this normal paradigm for representing a FOR loop does not work for
| > all possible ranges, that's precisely the trouble!
| 
| Yes, there's a problem if the maximum value of i is intended to be
| INT_MAX.

I don't think the cases of INT_MAX represents the majority of such FOR
loop.  The semi-open interval is a widespread idiom and has become a
standard idiom, at least if you move to STL :-)

-- Gaby

Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics?

[Gabriel Dos Reis]

Robert Dewar <dewar@adacore.com> writes:

| Gabriel Dos Reis wrote:
| >    for (int i = min; i < max; ++i)
| >        ....
| > and i, min and max don't change in the body, no matter what you think
| > of C's general "for" not being a FOR loop, the above is a FOR loop.
| 
| But this normal paradigm for representing a FOR loop does not work for
| all possible ranges,

Yes, but it needs not cover all possible ranges.  For practical
purposes, if it covers the vast majority of such loops I'll take it
and leave you complaining about not covering all possible ranges.

-- Gaby

Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics?

[Robert Dewar]

Andrew Pinski wrote:

> But the reason question is why make it an undefined behavior instead of
> an implementation defined?  This would have made it clearer instead of
> allowing the compiler not document what happens.  Or is C++
> just following C here?  In which case it might be better to ask the C
> committee why it was done this way and real definition of undefined for
> this case?

Note that implementation defined in practice is a fairly severe
constraint. That's because you don't want to have a super complicated
definition that takes a book to describe all the horrible things
that might happen, so in practice you are pushed into some simple
decision (always traps, always saturates, always wraps etc for the
case of overflow).

Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics?

[Robert Dewar]

Gabriel Dos Reis wrote:

> What I'm claiming is that he thinks "undefined behaviour" in the
> standard should not be taken as meaning "go to hell" (or punishment to
> borrow words from you) or absolute liberty for compiler writers to do
> just about everything that is imaginable, regardless of expectations.
> In other words, it is a question of balance. 

The trouble is that the standard does not formalize the balance, and
that is why we use the rhetoric. The real issue is whether the compiler
optimizer circuits should be allowed to assume that there is no overflow.
At first glance, it seems reasonable to say yes, that is after all what
the undefined semantics is about. The trouble, is, as I have pointed out
before, and tried to illustrate with my password example, that this
assumption, propagated by clever global flow algorithms, can have very
unexpected results.

So what to do?

We could try to formalize the notion that although overflow is undefined,
this information cannot be propagated, or perhaps more specifically cannot
be propagated backwards. But in practice this is very difficult to formalize,
and it is very hard to put bounds on what propagation means in this case.
We have a sort of informal notion that says the kind of thing that occurred
in my password example is a bad thing and should not happen, but we have a
lot of trouble formalizing it (I know of lots of attempts to do this, no
successes, anyone know a success story here?) Note that a similar issue
arises with assertions (is the compiler allowed to assume that assertions
are true and propagate this information?)

We could try to avoid the use of the general undefined. After all if
Stroustrup doesn't like the consequence of unbounded undefinedness,
then presumably he doesn't like the language of the standard. It is
the standard that introduces this notion of unbounded undefinedness
not me :-)

In fact I think the attempt to avoid unbounded undefinedness (what Ada
calls erroneous execution), is something that is very worth while. One
of the major steps forward in the Ada 95 standard over the Ada 83 standard
was that we eliminated many of the common cases of erroneousness and replaced
it with bounded errors.

FOr example, consider the case of uninitialized variables. In Ada 83, a
reference to an uninitialized scalar variable caused the program to be
erroneous. Now in Ada 95, such a value may have an invalid representation.
To reference an uninitialized variable is now not-erroneous, but rather
a bounded error. The possible effects are defined as follows in the RM:

9   If the representation of a scalar object does not represent a value of
the object's subtype (perhaps because the object was not initialized), the
object is said to have an invalid representation.  It is a bounded error to
evaluate the value of such an object.  If the error is detected, either
Constraint_Error or Program_Error is raised.  Otherwise, execution continues
using the invalid representation.  The rules of the language outside this
subclause assume that all objects have valid representations.  The semantics
of operations on invalid representations are as follows:

    10  If the representation of the object represents a value of the
        object's type, the value of the type is used.

    11  If the representation of the object does not represent a value of
        the object's type, the semantics of operations on such
        representations is implementation-defined, but does not by itself
        lead to erroneous or unpredictable execution, or to other objects
        becoming abnormal.

> As, an example, he
> illustrated the issue with the story -- quickly classified as "legend" by
> Robert Dewar -- about the best C optimizing compilers that miscompiled
> the Unix kernel that nobody wanted to use in practice (even if it
> would blow up any other competing compiler) and the company
> running out of business. 

Actually I asked for documentation of this claim, and as far as I remember
no one provided it, which is a pity. It is really useful to have examples
of real life situations where sticking to the standard and ignoring real
world practice resulted in useless compilers. I gave one such example,
the Burroughs Fortran Compiler.

In class, I have always suggested as another example that a C compiler
that generated code for a flat address space would be a menace if it
gave random results for comparing addresses between different allocated
objects. I assume no C compiler does this in practice.

So the Unix kernel example would be really nice to pin down. What compiler
was this? And what was the "legitimate" freedom that it took that it should
not have.

By the way, I generally agree that C is a language where the expected behavior
is quite a bit larger than the formally defined behavior (I consider this a bad
characteristic of a language by the way).

At another extreme, in the case of COBOL, when we wrote Realia COBOL, there
were a number of places where we deliberately deviated from the COBOL standard.
Why? Because there were bugs in the IBM mainframe implementations, and it was
more important to maintain compatibility with these bugs than to do what the
standard demanded :-)

Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics?

[Paul Schlie]

> Joe Buck <Joe.Buck@synopsys.COM>
> Undefined behavior doesn't mean that we should attempt to arbitrarily
> punish those who cross the line; that's why I don't think forcing integer
> overflows to trap (at least by default) is a good idea.  In many cases,
> "assume no overflow, but don't trap" can produce a better result than
> "assume wrap" does, as in the example I gave before.

My primary concern is about predictability, and could live with undefined
integer overflow if it were likely reasonably possible to verify that in
the general case an overflow would not occur, as otherwise an undefined
behavior may result. (which I can't believe is acceptable to anyone).

Although I recognize and accept that most trivial uses of signed arithmetic
can likely be verified as being constrained or not; it seems pretty clear
to me that it's very difficult and often strictly impossible in the general
case to do so; implying that signed integer arithmetic needs to be avoided
in the general case by either specifying signed integers as being unsigned
and convert them as required post-fact (which may also be undefined), and/or
utilize floats if one wants to produce a program which has a reasonable
chance of predictable behavior.

(My question was an honest one, although candidly somewhat pointed; as prior
to recent discussions it wasn't clear to me how potentially serious an issue
this was; so thought being forewarned was better than being surprised by
unexpected behaviors which may only express themselves in subtle non-obvious
circumstances.)

Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics?

[Robert Dewar]

Paul Schlie wrote:

> My primary concern is about predictability, and could live with undefined
> integer overflow if it were likely reasonably possible to verify that in
> the general case an overflow would not occur, as otherwise an undefined
> behavior may result. (which I can't believe is acceptable to anyone).

Well bugs in programs in general are not acceptable. This is just one
example of a bug.
> 
> Although I recognize and accept that most trivial uses of signed arithmetic
> can likely be verified as being constrained or not; it seems pretty clear
> to me that it's very difficult and often strictly impossible in the general
> case to do so; implying that signed integer arithmetic needs to be avoided
> in the general case by either specifying signed integers as being unsigned
> and convert them as required post-fact (which may also be undefined), and/or
> utilize floats if one wants to produce a program which has a reasonable
> chance of predictable behavior.

Actually in the safety critical world, people all the time go through
procedures to verify that their program is free of bugs, including
unexpected overflow.

Re: Should GCC publish a general rule/warning due to it's default presumption of undefined signed integer overflow semantics?

[Paul Schlie]

> Joe Buck <Joe.Buck@synopsys.COM>
> Undefined behavior doesn't mean that we should attempt to arbitrarily
> punish those who cross the line; that's why I don't think forcing integer
> overflows to trap (at least by default) is a good idea.  In many cases,
> "assume no overflow, but don't trap" can produce a better result than
> "assume wrap" does, as in the example I gave before.

My primary concern is about predictability, and could live with undefined
integer overflow if it were likely reasonably possible to verify that in
the general case an overflow would not occur, as otherwise an undefined
behavior may result. (which I can't believe is acceptable to anyone).

Although I recognize and accept that most trivial uses of signed arithmetic
can likely be verified as being constrained or not; it seems pretty clear
to me that it's very difficult and often strictly impossible in the general
case to do so; implying that signed integer arithmetic needs to be avoided
in the general case by either specifying signed integers as being unsigned
and convert them as required post-fact (which may also be undefined), and/or
utilize floats if one wants to produce a program which has a reasonable
chance of predictable behavior.

(My question was an honest one, although candidly somewhat pointed; as prior
to recent discussions it wasn't clear to me how potentially serious an issue
this was; so thought being forewarned was better than being surprised by
unexpected behaviors which may only express themselves in subtle non-obvious
circumstances.)