basic VRP min/max range overflow question

basic VRP min/max range overflow question

[Paul Schlie]

Upon a potential integer overflow of either it's min or max range,
shouldn't the result be set to [min:type-min-value, max:type-max-value],
without the necessity of any further designations?

As this would seem to most accurately and simply represent the effective
bounds of an underflowed integer value constrained to an arbitrarily sized
integer type size for all targets I can think of, with the exception of
DSP's which tend to uniquely support saturating integer arithmetic, in
which case only the min or max range would be saturated correspondingly.

Re: basic VRP min/max range overflow question

[Paolo Bonzini]

Paul Schlie wrote:
> Upon a potential integer overflow of either it's min or max range,
> shouldn't the result be set to [min:type-min-value, max:type-max-value],
> without the necessity of any further designations?

No.

[10, INT_MAX] + [ 1, 1 ] == [ 11, INT_MAX ] because of the famous signed 
int overflow definition in the C standard.

[10U, UINT_MAX] + [ 1U, 1U ] == ~[ 1U, 10U ]

Paolo

Re: basic VRP min/max range overflow question

[Diego Novillo]

On Fri, Jun 17, 2005 at 12:27:55AM -0400, Paul Schlie wrote:

> Upon a potential integer overflow of either it's min or max range,
> shouldn't the result be set to [min:type-min-value, max:type-max-value],
> without the necessity of any further designations?
> 
If you want this behaviour, use -fwrapv.


Diego.

Re: basic VRP min/max range overflow question

[Paul Schlie]

> Paolo Bonsini wrote:
>> Upon a potential integer overflow of either it's min or max range,
>> shouldn't the result be set to [min:type-min-value, max:type-max-value],
>> without the necessity of any further designations?
>
> No.
> 
> [10, INT_MAX] + [ 1, 1 ] == [ 11, INT_MAX ] because of the famous signed
> int overflow definition in the C standard.
>
> [10U, UINT_MAX] + [ 1U, 1U ] == ~[ 1U, 10U ]

??? Do you mean:

H.2.2  Integer types

       [#1] The signed C integer types int,  long,  long  long  and  the
       corresponding  unsigned  types  are compatible with LIA-1.  If an
       implementation adds support  for  the  LIA-1  exceptional  values
       integer_overflow  and  undefined,  then  those  types  are  LIA-1
       conformant types.  C's unsigned integer types are "modulo" in the
       LIA-1  sense  in that overflows or out-of-bounds results silently
       wrap. An implementation that defines signed integer types as also
       being  modulo  need  not  detect integer overflow, in which case,
       only integer divide-by-zero need be detected.

Where in combination with:

5.1.2.3  Program execution

Examples 2.  In executing the fragment

                     char c1, c2;
                     /* ... */
                     c1 = c1 + c2;

             the ``integer promotions'' require that  the  abstract
             machine promote the value of each variable to int size
             and then add  the  two  ints  and  truncate  the  sum.
             Provided the addition of two chars can be done without
             overflow,  or  with  overflow  wrapping  silently   to
             produce  the correct result, the actual execution need
             only produce the same result,  possibly  omitting  the
             promotions.

It seems pretty clear given that for all practical purposes all typical
machines do silently wrap integer overflow, they all correspondingly yield:

  [10, INT_MAX] + [ 1, 1 ] == [INT_MIN, INT_MAX ]

  [10U, UINT_MAX] + [ 1U, 1U ] == [UINT_MIN, UINT_MAX]

or more generally: [<INTEGER-TYPE>_MIN, <INTEGER-TYPE>_MAX] upon overflow.

Re: basic VRP min/max range overflow question

[Paolo Bonzini]

>       [#1] The signed C integer types int,  long,  long  long  and  the
>       corresponding  unsigned  types  are compatible with LIA-1.  If an
>       implementation adds support  for  the  LIA-1  exceptional  values
>       integer_overflow  and  undefined,  then  those  types  are  LIA-1
>       conformant types.
>  
>
They need not wrap around.  People that are actually on the C standards 
committee have told you this multiple times.

>       C's unsigned integer types are "modulo" in the
>       LIA-1  sense  in that overflows or out-of-bounds results silently
>       wrap. An implementation that defines signed integer types as also
>       being  modulo  need  not  detect integer overflow, in which case,
>       only integer divide-by-zero need be detected.
>  
>
This is different from signed types.  Actually I was wrong,

   [10U, UINT_MAX] + [ 1U, 1U ] == ~[ UINT_MIN + 1, 10U ]

Paolo

Re: basic VRP min/max range overflow question

[Paul Schlie]

> They need not wrap around.  People that are actually on the C standards
> committee have told you this multiple times.

Yes, and may clearly produce erroneous results if the value ranges
are not consistent with the factual behavior of an implementation, i.e.:

 int x;
 volatile int v;

 x = (v ? 0 : INT_MAX) + 1;  // [1, INT_MAX] (without -fwrapv)

 if (x <= 0)                 // Which may be erroneously
  printf("%i is <= 0.", x);  // optimized away, with this.
 else
  printf("%i is > 0.", x);   // Leaving only this in error.

As regardless of the value of x produced by an implementation, it's wrong
to presume a result which is not consistent with the factual behavior of
that implementation.  Therefore -fwrapv must be presumed for all targets
which effectively wrap signed integer overflows, as otherwise non-
conformant behaviors may result. (i.e. effectively all present targets)

As I doubt "-2147483648 > 0" or "0 > 0" (as may otherwise result from
typical 2's or 1's complement implementations which silently wrap
overflows), can be justified as being a valid conforming result in any
circumstance. (and confess that I have nothing more to add if not obvious).

Re: basic VRP min/max range overflow question

[Paolo Bonzini]

Paul Schlie wrote:

>>They need not wrap around.  People that are actually on the C standards
>>committee have told you this multiple times.
>>    
>>
>
>Yes, and may clearly produce erroneous results if the value ranges
>are not consistent with the factual behavior of an implementation, i.e.:
>  
>
Are you listening or not??? This is *not* meant to be inconsistent with 
"the factual behavior of an implementation".  It is simply not 
specified.  It is not portable.  It should not be done.  Period.

On many embedded machines, dereferencing a NULL pointer is perfectly 
ok.  To avoid problems with C optimizations where dereferencing a NULL 
pointer is consider to have unspecified behavior, code is usually put 
there.  Does this make it "non-conformant" to optimize away this if?

   char *a, b;
   a = NULL;
   b = *a;
   if (a == NULL)
     abort ();

Well, according to zillions of embedded C developers, it is not.

A similar case of unspecified behavior that "just works" is this.  On 
the i386, passing variadic arguments to a function without a prototype 
usually just works.  On other machines it may not because the ellipsis 
has a different calling conventions.  It is not specified.  It is not 
portable.  It should not be done.  Period.

Read the standard, *understand* what it says, then come back.  Or anyway 
do not complain here, propose a DR on the C standard committee and wait 
for it to be rejected.

I *know* I'm being rude, but I'm also fed up by this utter waste of time 
and bandwidth, and am not going to spend more time on this.

Paolo

Re: basic VRP min/max range overflow question

[Diego Novillo]

On Fri, Jun 17, 2005 at 02:28:58PM -0400, Paul Schlie wrote:

>  int x;
>  volatile int v;
> 
>  x = (v ? 0 : INT_MAX) + 1;  // [1, INT_MAX] (without -fwrapv)
> 
>  if (x <= 0)                 // Which may be erroneously
>   printf("%i is <= 0.", x);  // optimized away, with this.
>  else
>   printf("%i is > 0.", x);   // Leaving only this in error.
> 
You want to file a DR with the language standards.  This is now
wasting everybody's time.

The compiler is perfectly free to fold that if() away.  The fact
that it doesn't do it now is actually a missed optimization
opportunity (a PHI node with all arguments > 0 could produce the
range [1, +INF]).


Diego.

Re: basic VRP min/max range overflow question

[Paul Schlie]

> From: Diego Novillo <dnovillo@redhat.com>
> On Fri, Jun 17, 2005 at 02:28:58PM -0400, Paul Schlie wrote:
> 
>>  int x;
>>  volatile int v;
>> 
>>  x = (v ? 0 : INT_MAX) + 1;  // [1, INT_MAX] (without -fwrapv)
>> 
>>  if (x <= 0)                 // Which may be erroneously
>>   printf("%i is <= 0.", x);  // optimized away, with this.
>>  else
>>   printf("%i is > 0.", x);   // Leaving only this in error.
>> 
> You want to file a DR with the language standards.

- There's nothing wrong with the standard, just it's implementation.

  (As there's nothing in the standard which enables an implementation
  to subsequently disregard the resulting value of an implementation
  specific operation from the best I can tell; although would welcome
  someone pointing out where specifically it's allowed.  As unless
  it is, an undefined result is specific to the just that operation.
  It does not magically alter the semantics well defined operations
  which may utilize that result, regardless of it's value.)

  ["undefined" only provides liberties within the constrains of what
  is specifically specified as being undefined, but none beyond that.]

Re: basic VRP min/max range overflow question

[Andrew Pinski]

On Jun 17, 2005, at 8:20 PM, Paul Schlie wrote:

>   ["undefined" only provides liberties within the constrains of what
>   is specifically specified as being undefined, but none beyond that.]

That is not true.  Undefined means it can run "rm /" if you ever invoke
the undefined code.

Thanks,
Andrew Pinski

Re: basic VRP min/max range overflow question

[Paul Schlie]

> From: Andrew Pinski <pinskia@physics.uc.edu>
> On Jun 17, 2005, at 8:20 PM, Paul Schlie wrote:
> 
>>   ["undefined" only provides liberties within the constrains of what
>>   is specifically specified as being undefined, but none beyond that.]
> 
> That is not true.  Undefined means it can run "rm /" if you ever invoke
> the undefined code.

- If the semantics of an operation are "undefined", I'd agree; but if
  control is returned to the program, the program's remaining specified
  semantics must be correspondingly obeyed, including the those which
  may utilize the resulting value of the "undefined" operation.

- If the result value is "undefined", just the value is undefined.

(Unless one advocates that any undefined result implies undefined semantics,
which enables anything to occur, including the arbitrary corruption of
the remaining program's otherwise well defined semantics; in which case any
invocation of implementation specific behavior may then validly result in
arbitrary remaining program behavior.)

Which I'd hope isn't advocated.

Re: basic VRP min/max range overflow question

[Dale Johannesen]

On Jun 17, 2005, at 5:59 PM, Paul Schlie wrote:

>> From: Andrew Pinski <pinskia@physics.uc.edu>
>> On Jun 17, 2005, at 8:20 PM, Paul Schlie wrote:
>>
>>>   ["undefined" only provides liberties within the constrains of what
>>>   is specifically specified as being undefined, but none beyond 
>>> that.]
>>
>> That is not true.  Undefined means it can run "rm /" if you ever 
>> invoke
>> the undefined code.
>
> - If the semantics of an operation are "undefined", I'd agree; but if
>   control is returned to the program, the program's remaining specified
>   semantics must be correspondingly obeyed, including the those which
>   may utilize the resulting value of the "undefined" operation.
>
> - If the result value is "undefined", just the value is undefined.
>
> (Unless one advocates that any undefined result implies undefined 
> semantics,
> which enables anything to occur, including the arbitrary corruption of
> the remaining program's otherwise well defined semantics; in which 
> case any
> invocation of implementation specific behavior may then validly result 
> in
> arbitrary remaining program behavior.)
>
> Which I'd hope isn't advocated.

You are wrong, and this really isn't a matter of opinion.  The standard 
defines exactly
what it means by "undefined behavior":

3.4.3 1 undefined behavior
behavior, upon use of a nonportable or erroneous program construct or 
of erroneous data,
  for which this International Standard imposes no requirements
2 NOTE  Possible undefined behavior ranges from ignoring the situation 
completely with
unpredictable results, to behaving during translation or program 
execution in a documented
manner characteristic of the environment (with or without the issuance 
of a diagnostic message),
to terminating a translation or execution (with the issuance of a 
diagnostic message).

Re: basic VRP min/max range overflow question

[Mike Stump]

On Friday, June 17, 2005, at 05:59  PM, Paul Schlie wrote:
> - If the semantics of an operation are "undefined", I'd agree; but if
>   control is returned to the program, the program's remaining specified
>   semantics must be correspondingly obeyed, including the those which
>   may utilize the resulting value of the "undefined" operation.

I am sorry the standard disagrees with you:

        [#3] A  program  that  is  correct  in  all  other  aspects,
        operating  on  correct data, containing unspecified behavior
        shall be a  correct  program  and  act  in  accordance  with
        5.1.2.3.

:-(  Maybe you just mean that you'd like it if the compiler should 
follow the remaining semantics as best it can, on that point, I'd agree.

Re: basic VRP min/max range overflow question

[Toon Moene]

Dale Johannesen wrote:

> 2 NOTE  Possible undefined behavior ranges from ignoring the situation 
> completely with
> unpredictable results, to behaving during translation or program 
> execution in a documented
> manner characteristic of the environment (with or without the issuance 
> of a diagnostic message),
> to terminating a translation or execution (with the issuance of a 
> diagnostic message).

Hmmm, I see your standard doesn't include the possibility to start WW 
III (if the right, optional, hardware is connected) ?

[ Sorry, couldn't resist :-) ]

-- 
Toon Moene - e-mail: toon@moene.indiv.nluug.nl - phone: +31 346 214290
Saturnushof 14, 3738 XG  Maartensdijk, The Netherlands
A maintainer of GNU Fortran 95: http://gcc.gnu.org/fortran/
Looking for a job: Work from home or at a customer site; HPC, (GNU) 
Fortran & C

Re: basic VRP min/max range overflow question

[Robert Dewar]

Paul Schlie wrote:

>   (As there's nothing in the standard which enables an implementation
>   to subsequently disregard the resulting value of an implementation
>   specific operation from the best I can tell; although would welcome
>   someone pointing out where specifically it's allowed.  As unless
>   it is, an undefined result is specific to the just that operation.
>   It does not magically alter the semantics well defined operations
>   which may utilize that result, regardless of it's value.)
> 
>   ["undefined" only provides liberties within the constrains of what
>   is specifically specified as being undefined, but none beyond that.]

You are forgetting the "as if" semantics that is always inherent in
the standard. So after an operation with an undefined result, we can
do anything we like with the value, since it is "as if" the operation
had produced that value. So for example, if we skip an operation because
we know it will overflow, and end up using uninitialized junk in a register,
it is "as if" that undefined operation produced the particular uninitialized
junk value that we ended up with.

So the above is inventive but wrong.

Re: basic VRP min/max range overflow question

[Paul Schlie]

> Mike Stump wrote:
>> Paul Schlie wrote:
>> - If the semantics of an operation are "undefined", I'd agree; but if
>>   control is returned to the program, the program's remaining specified
>>   semantics must be correspondingly obeyed, including the those which
>>   may utilize the resulting value of the "undefined" operation.
>
> I am sorry the standard disagrees with you:
>
>        [#3] A  program  that  is  correct  in  all  other  aspects,
>        operating  on  correct data, containing unspecified behavior
>        shall be a  correct  program  and  act  in  accordance  with
>        5.1.2.3.
>
> :-(  Maybe you just mean that you'd like it if the compiler should
> follow the remaining semantics as best it can, on that point, I'd agree.

Maybe I didn't phrase my statement well; I fully agree with the cited
paragraph above which specifically says a program containing unspecified
behavior "shall be a  correct  program  and  act  in  accordance  with
5.1.2.3". Which specifies program execution, in terms of an abstract machine
model, which correspondingly requires:

       [#2] ... At  certain  specified
       points in the execution sequence called sequence points, all
       side effects of previous evaluations shall be  complete  and
       no  side  effects of subsequent evaluations shall have taken
       place.

       [#3] In the abstract machine, all expressions are  evaluated
       as  specified  by  the  semantics.  An actual implementation
       need not evaluate part of an expression  if  it  can  deduce
       that  its  value is not used and that no needed side effects
       are produced ...

Therefore regardless of the result of an "undefined" result/operation at
it's enclosing sequence point, the remaining program must continue to abide
by the specified semantics of the language.

> Robert Dewar writes:
> You are forgetting the "as if" semantics that is always inherent in
> the standard. So after an operation with an undefined result, we can
> do anything we like with the value, since it is "as if" the operation
> had produced that value. So for example, if we skip an operation because
> we know it will overflow, and end up using uninitialized junk in a register,
> it is "as if" that undefined operation produced the particular uninitialized
> junk value that we ended up with.
> 
> So the above is inventive but wrong.

No, as above, the standard clearly requires that the side-effects of an
undefined operation be effectively bounded at it's enclosing sequence
points. Therefore any optimizations performed beyond these bounds must be
"as if" consistent with any resulting stored value/state side effects which
may have resulted from an operation's undefined behavior.

Therefore clearly, subsequent evaluations/optimizations must comply with
whatever logical state is defined to exist subsequent to an implementation's
choice of an undefined behavior past it's delineated sequence point if
logical execution is allowed to proceed past them.

Therefore clearly:

- an optimization which presume a value which differs from the effective
stored value past a sequence point may result in erroneous behavior; which
as would be the case in the example I provided.

- an optimization which presumes the execution state of a program does not
proceed past a sequence point. but in fact does, may result in erroneous
behavior; which would be the case if NULL pointer comparisons were optimized
away presuming an earlier pointer dereference would have prevented execution
from proceeding past it's enclosing sequence point if in fact it does not.

> Dale Johannesen writes:
> You are wrong, and this really isn't a matter of opinion.  The standard
> defines exactly what it means by "undefined behavior":
> 
> 3.4.3 1 undefined behavior
> behavior, upon use of a nonportable or erroneous program construct or
> of erroneous data, for which this International Standard imposes no
> requirements
>
> 2 NOTE  Possible undefined behavior ranges from ignoring the situation
> completely with unpredictable results, to behaving during translation or
> program execution in a documented manner characteristic of the environment
> (with or without the issuance of a diagnostic message), to terminating a
> translation or execution (with the issuance of a diagnostic message).

- as above, the logical side effects of an undefined behavior (what ever
  it's defined to be by an implementation) are clearly logically constrained
  to within the bounds of the it's enclosing sequence points.

Re: basic VRP min/max range overflow question

[Joseph S. Myers]

On Sat, 18 Jun 2005, Paul Schlie wrote:

> Maybe I didn't phrase my statement well; I fully agree with the cited
> paragraph above which specifically says a program containing unspecified
> behavior "shall be a  correct  program  and  act  in  accordance  with
> 5.1.2.3". Which specifies program execution, in terms of an abstract machine
> model, which correspondingly requires:

You appear to have confused unspecified behavior (where the possibilities 
are bounded) and undefined behavior (where the possibilities are 
unbounded).  On *undefined* behavior (such as signed integer overflow), 
*this International Standard imposes no requirements*.  If a program 
execution involved undefined behavior, *there are no requirements on its 
execution, even before the undefined behavior occurs in the abstract 
machine*.  Therefore the compiler assumes that you only ever pass it 
programs which do not execute undefined behavior.  If a possible execution 
might involve undefined behavior, the compiler presumes that the 
programmer knows more than it can prove and knows that the relevant 
circumstances cannot arise at execution.  For example, a correct program 
never involves overflow of a signed loop variable, so the compiler 
presumes that the programmer proved that the loop variable can never 
overflow at execution and uses this information to optimize the loop: it 
cannot prove it by itself but using the presumption that the program is 
correct it can optimize the program better.

The traditional form of undefined behavior is for demons to fly out of 
your nose.  We just haven't yet got -fnasal-demons working reliably but it 
would be conforming for it to be on by default.  If you are lucky, it will 
happen anyway without that option.

http://groups.google.com/groups?hl=en&selm=10195%40ksr.com

-- 
Joseph S. Myers               http://www.srcf.ucam.org/~jsm28/gcc/
    jsm@polyomino.org.uk (personal mail)
    joseph@codesourcery.com (CodeSourcery mail)
    jsm28@gcc.gnu.org (Bugzilla assignments and CCs)

Re: basic VRP min/max range overflow question

[Paul Schlie]

> From: "Joseph S. Myers" <joseph@codesourcery.com>
> On Sat, 18 Jun 2005, Paul Schlie wrote:
> 
>> Maybe I didn't phrase my statement well; I fully agree with the cited
>> paragraph above which specifically says a program containing unspecified
>> behavior "shall be a  correct  program  and  act  in  accordance  with
>> 5.1.2.3". Which specifies program execution, in terms of an abstract machine
>> model, which correspondingly requires:
> 
> You appear to have confused unspecified behavior (where the possibilities
> are bounded) and undefined behavior (where the possibilities are
> unbounded).  On *undefined* behavior (such as signed integer overflow),
> *this International Standard imposes no requirements*.  If a program
> execution involved undefined behavior, *there are no requirements on its
> execution, even before the undefined behavior occurs in the abstract
> machine*.

No, the standard clearly states that it imposes no requirements on the
behavior which an implementation may choose to implement for (and limited
to) that specific undefined behavior; as regardless of that behavior, it's
resulting side effects clearly remains constrained by the rules as specified
in 5.1.2.3.

       [#1] Behavior where this International Standard provides two
       or  more  possibilities and imposes no requirements on which
       is chosen in any instance.  A program that is correct in all
       other   aspects,   operating  on  correct  data,  containing
       unspecified behavior shall be a correct program and  act  in
       accordance with subclause 5.1.2.3.

>              Therefore the compiler assumes that you only ever pass it
> programs which do not execute undefined behavior.  If a possible execution
> might involve undefined behavior, the compiler presumes that the
> programmer knows more than it can prove and knows that the relevant
> circumstances cannot arise at execution.

The compiler is free to presume whatever it desires as long as the
evaluation of the resulting code it produces conforms to the requirements of
the language.  Therefore any compiler which does not consistently treat the
side effects (if any) resulting from the evaluation of an undefined behavior
past the sequence points logically bounding that behavior is non-conformant.

>                                           For example, a correct program
> never involves overflow of a signed loop variable, so the compiler
> presumes that the programmer proved that the loop variable can never
> overflow at execution and uses this information to optimize the loop: it
> cannot prove it by itself but using the presumption that the program is
> correct it can optimize the program better.

As program which may specify/invoke an undefined behavior remains a correct,
albeit non-portable and even possibly indeterminate, program; its arguably
incorrect for a compiler to presume otherwise, however is free to choose
an arbitrary behavior for any specified undefined behaviors specified in the
code, but remains bound to consistently treat the resulting side-effects of
whatever behavior it choose to implement in the evaluation of the program
past the sequence point those side-effects remain bound by.

Therefore, given your example; regardless of what value an implementation
chooses to logically assign to an overflowed loop iteration variable, the
compiler can't assume it's X for the purposes of optimization when in fact
it was assigned the value Y past the sequence point that operation remains
bounded by, as this would violate the sequence rule semantics imposed on all
expression evaluations, regardless of their individual semantics, and
possibly result in non-conformant erroneous behavior.

> The traditional form of undefined behavior is for demons to fly out of
> your nose.  We just haven't yet got -fnasal-demons working reliably but it
> would be conforming for it to be on by default.  If you are lucky, it will
> happen anyway without that option.

As long as all side-effects are logically expressed at it's sequence point
bounds, I've got no problem with this :)

Re: basic VRP min/max range overflow question

[Paul Schlie]

Sorry, yes the quote below defines unspecified, not undefined behavior.

Now more correctly:

       [#1] Behavior,  upon  use  of  a  nonportable  or  erroneous
       program  construct, of erroneous data, or of indeterminately
       valued  objects,  for  which  this  International   Standard
       imposes  no  requirements.   Permissible  undefined behavior
       ranges  from  ignoring   the   situation   completely   with
       unpredictable  results,  to  behaving  during translation or
       program execution in a documented manner  characteristic  of
       the   environment   (with  or  without  the  issuance  of  a
       diagnostic  message),  to  terminating  a   translation   or
       execution (with the issuance of a diagnostic message).

       [#3] The implementation must successfully translate a  given
       program  unless  a syntax error is detected, a constraint is
       violated, or it can determine that every possible  execution
       of that program would result in undefined behavior.

Which again is specific to that which is defined, as it requires the
successful (and presumably conformant) translation of the program unless
the implementation can prove the whole program is itself would have an
undefined behavior (reinforcing the notion that the language's semantics
remain in force even in the presence of a expression with undefined
semantics).


> From: Paul Schlie <schlie@comcast.net>
>> From: "Joseph S. Myers" <joseph@codesourcery.com>
>> On Sat, 18 Jun 2005, Paul Schlie wrote:
>> 
>>> Maybe I didn't phrase my statement well; I fully agree with the cited
>>> paragraph above which specifically says a program containing unspecified
>>> behavior "shall be a  correct  program  and  act  in  accordance  with
>>> 5.1.2.3". Which specifies program execution, in terms of an abstract machine
>>> model, which correspondingly requires:
>> 
>> You appear to have confused unspecified behavior (where the possibilities
>> are bounded) and undefined behavior (where the possibilities are
>> unbounded).  On *undefined* behavior (such as signed integer overflow),
>> *this International Standard imposes no requirements*.  If a program
>> execution involved undefined behavior, *there are no requirements on its
>> execution, even before the undefined behavior occurs in the abstract
>> machine*.
> 
> No, the standard clearly states that it imposes no requirements on the
> behavior which an implementation may choose to implement for (and limited to)
> that specific undefined behavior; as regardless of that behavior, it's
> resulting side effects clearly remains constrained by the rules as specified
> in 5.1.2.3.
> 
>        [#1] Behavior where this International Standard provides two
>        or  more  possibilities and imposes no requirements on which
>        is chosen in any instance.  A program that is correct in all
>        other   aspects,   operating  on  correct  data,  containing
>        unspecified behavior shall be a correct program and  act  in
>        accordance with subclause 5.1.2.3.
> 
>>              Therefore the compiler assumes that you only ever pass it
>> programs which do not execute undefined behavior.  If a possible execution
>> might involve undefined behavior, the compiler presumes that the
>> programmer knows more than it can prove and knows that the relevant
>> circumstances cannot arise at execution.
> 
> The compiler is free to presume whatever it desires as long as the evaluation
> of the resulting code it produces conforms to the requirements of the
> language.  Therefore any compiler which does not consistently treat the side
> effects (if any) resulting from the evaluation of an undefined behavior past
> the sequence points logically bounding that behavior is non-conformant.
> 
>>                                           For example, a correct program
>> never involves overflow of a signed loop variable, so the compiler
>> presumes that the programmer proved that the loop variable can never
>> overflow at execution and uses this information to optimize the loop: it
>> cannot prove it by itself but using the presumption that the program is
>> correct it can optimize the program better.
> 
> As program which may specify/invoke an undefined behavior remains a correct,
> albeit non-portable and even possibly indeterminate, program; its arguably
> incorrect for a compiler to presume otherwise, however is free to choose
> an arbitrary behavior for any specified undefined behaviors specified in the
> code, but remains bound to consistently treat the resulting side-effects of
> whatever behavior it choose to implement in the evaluation of the program past
> the sequence point those side-effects remain bound by.
> 
> Therefore, given your example; regardless of what value an implementation
> chooses to logically assign to an overflowed loop iteration variable, the
> compiler can't assume it's X for the purposes of optimization when in fact it
> was assigned the value Y past the sequence point that operation remains
> bounded by, as this would violate the sequence rule semantics imposed on all
> expression evaluations, regardless of their individual semantics, and possibly
> result in non-conformant erroneous behavior.
> 
>> The traditional form of undefined behavior is for demons to fly out of
>> your nose.  We just haven't yet got -fnasal-demons working reliably but it
>> would be conforming for it to be on by default.  If you are lucky, it will
>> happen anyway without that option.
> 
> As long as all side-effects are logically expressed at it's sequence point
> bounds, I've got no problem with this :)

Re: basic VRP min/max range overflow question

[Joseph S. Myers]

On Sat, 18 Jun 2005, Paul Schlie wrote:

>        [#1] Behavior,  upon  use  of  a  nonportable  or  erroneous
>        program  construct, of erroneous data, or of indeterminately
>        valued  objects,  for  which  this  International   Standard
>        imposes  no  requirements.   Permissible  undefined behavior
>        ranges  from  ignoring   the   situation   completely   with
>        unpredictable  results,  to  behaving  during translation or
>        program execution in a documented manner  characteristic  of
>        the   environment   (with  or  without  the  issuance  of  a
>        diagnostic  message),  to  terminating  a   translation   or
>        execution (with the issuance of a diagnostic message).

You appear to have chosen to misquote again.  In this case, you've taken 
the C90 version of the wording but with a paragraph number from C99 (C90 
did not have paragraph numbers).  Perhaps you cannot grasp the generality 
of "no requirements"?  A few examples are given, but "no requirements" 
means that the program can behave completely inconsistently if it involves 
undefined behavior.

>        [#3] The implementation must successfully translate a  given
>        program  unless  a syntax error is detected, a constraint is
>        violated, or it can determine that every possible  execution
>        of that program would result in undefined behavior.

This looks like a completely fabricated quote to me.  If it comes from 
C99, state the subclause and paragraph numbers (in C99 as amended by TC1 
and TC2).  It certainly doesn't seem to be in the plain text version of 
C99+TC1.  In general, state where you are quoting rather than just 
claiming particular text you've just written is relevant.

> Which again is specific to that which is defined, as it requires the
> successful (and presumably conformant) translation of the program unless
> the implementation can prove the whole program is itself would have an
> undefined behavior (reinforcing the notion that the language's semantics
> remain in force even in the presence of a expression with undefined
> semantics).

"no requirements" means that *any* translation conforms in the case of 
undefined behavior.  Only those executions not involving undefined 
behavior have any requirements.

-- 
Joseph S. Myers               http://www.srcf.ucam.org/~jsm28/gcc/
    jsm@polyomino.org.uk (personal mail)
    joseph@codesourcery.com (CodeSourcery mail)
    jsm28@gcc.gnu.org (Bugzilla assignments and CCs)

Re: basic VRP min/max range overflow question

[Paul Schlie]

So in effect the standard committee have chosen to allow any program which
invokes any undefined behavior to behave arbitrarily without diagnosis?

This is a good thing?

[ curiously can't find any actual reference stating that integer overflow
  is specifically results in undefined behavior, although it's obviously ill
  defined?

  although can find reference that a dereference of an overflowed pointer
  is undefined? ]


> From: "Joseph S. Myers" <joseph@codesourcery.com>
> On Sat, 18 Jun 2005, Paul Schlie wrote:
> 
>>        [#1] Behavior,  upon  use  of  a  nonportable  or  erroneous
>>        program  construct, of erroneous data, or of indeterminately
>>        valued  objects,  for  which  this  International   Standard
>>        imposes  no  requirements.   Permissible  undefined behavior
>>        ranges  from  ignoring   the   situation   completely   with
>>        unpredictable  results,  to  behaving  during translation or
>>        program execution in a documented manner  characteristic  of
>>        the   environment   (with  or  without  the  issuance  of  a
>>        diagnostic  message),  to  terminating  a   translation   or
>>        execution (with the issuance of a diagnostic message).
> 
> You appear to have chosen to misquote again.  In this case, you've taken
> the C90 version of the wording but with a paragraph number from C99 (C90
> did not have paragraph numbers).  Perhaps you cannot grasp the generality
> of "no requirements"?  A few examples are given, but "no requirements"
> means that the program can behave completely inconsistently if it involves
> undefined behavior.
> 
>>        [#3] The implementation must successfully translate a  given
>>        program  unless  a syntax error is detected, a constraint is
>>        violated, or it can determine that every possible  execution
>>        of that program would result in undefined behavior.
> 
> This looks like a completely fabricated quote to me.  If it comes from
> C99, state the subclause and paragraph numbers (in C99 as amended by TC1
> and TC2).  It certainly doesn't seem to be in the plain text version of
> C99+TC1.  In general, state where you are quoting rather than just
> claiming particular text you've just written is relevant.
> 
>> Which again is specific to that which is defined, as it requires the
>> successful (and presumably conformant) translation of the program unless
>> the implementation can prove the whole program is itself would have an
>> undefined behavior (reinforcing the notion that the language's semantics
>> remain in force even in the presence of a expression with undefined
>> semantics).
> 
> "no requirements" means that *any* translation conforms in the case of
> undefined behavior.  Only those executions not involving undefined
> behavior have any requirements.
> 
> -- 
> Joseph S. Myers               http://www.srcf.ucam.org/~jsm28/gcc/
>     jsm@polyomino.org.uk (personal mail)
>     joseph@codesourcery.com (CodeSourcery mail)
>     jsm28@gcc.gnu.org (Bugzilla assignments and CCs)

Re: basic VRP min/max range overflow question

[Joseph S. Myers]

On Sat, 18 Jun 2005, Paul Schlie wrote:

> So in effect the standard committee have chosen to allow any program which
> invokes any undefined behavior to behave arbitrarily without diagnosis?

That is the *whole point* of undefined behavior.  Unless the program also 
violates a compile-time syntax rule or constraint, no diagnosis is 
required.

> This is a good thing?

Yes, C is designed to allow more efficient optimization of correct 
programs at the expense of complete unpredictability for incorrect 
programs.  If you want different tradeoffs, use another language such as 
Java instead of complaining about the design principles of C.

The important cases of optimization are where the programmer knows that 
the undefined behavior cannot occur in any execution of the program but 
the compiler can only know this by presuming that the programmer knew what 
they were doing and that undefined behavior won't occur.  For example, a 
competent programmer will not write programs where a signed loop variable 
overflows, and loops can be optimized better if you can ignore the 
possibility of loops overflowing.  Undefined behavior on overflow allows 
this optimization for loops with signed induction variables, on the 
presumption of a competent programmer.  If the induction variable is 
unsigned, the compiler needs to allow for overflow in case of perverse but 
correct programmers writing what would nevertheless be valid code, and the 
loops cannot be optimized so well.  Similarly, a competent programmer will 
not write programs which modify the same object twice between sequence 
points, but in general the compiler can't know whether two pointer 
dereferences in an expression refer to the same object; undefined behavior 
allows the compiler to reorder and schedule the expression for more 
efficient execution anyway on the presumption that no prohibited aliasing 
occurs.

> [ curiously can't find any actual reference stating that integer overflow
>   is specifically results in undefined behavior, although it's obviously ill
>   defined?

In general you don't need any specific reference; the mere lack of 
definition suffices; see 4#2:

       [#2] If  a  ``shall''  or  ``shall  not''  requirement  that
       appears outside of a constraint is violated, the behavior is
       undefined.  Undefined behavior  is  otherwise  indicated  in
       this   International   Standard  by  the  words  ``undefined
       behavior'' or by the omission of any explicit definition  of
       behavior.   There  is  no difference in emphasis among these
       three; they all describe ``behavior that is undefined''.

But the specific reference you want is 6.5#5:

       [#5]  If  an  exceptional  condition   occurs   during   the
       evaluation  of  an expression (that is, if the result is not
       mathematically defined or not in the range of  representable
       values for its type), the behavior is undefined.

Again, if you don't like the definition of C, there are other programming 
languages available which may be more to your taste.

-- 
Joseph S. Myers               http://www.srcf.ucam.org/~jsm28/gcc/
    jsm@polyomino.org.uk (personal mail)
    joseph@codesourcery.com (CodeSourcery mail)
    jsm28@gcc.gnu.org (Bugzilla assignments and CCs)

Re: basic VRP min/max range overflow question

[Florian Weimer]

* Paul Schlie:

> So in effect the standard committee have chosen to allow any program which
> invokes any undefined behavior to behave arbitrarily without diagnosis?
>
> This is a good thing?

It's the way things are.  There isn't a real market for
bounds-checking C compilers, for example, which offer well-defined
semantics even for completely botched pointer arithmetic and pointer
dereference.

C isn't a programming language which protects its own abstractions
(unlike Java, or certain Ada or Common Lisp subsets), and C never was
intended to work this way.  Consequently, the committee was right to
deal with undefined behavior in the way it did.  Otherwise, the
industry would have adopted C as we know it, and the ISO C standard
would have had the same relevance as, say, the ISO Pascal on the
evolution of Pascal.

Keep in mind that the interest in "safe" langauges (which protect
their abstractions) for commercial production code is a very, very
recent development, and I'm not sure if this is just an accident.

Re: basic VRP min/max range overflow question

[Kai Henningsen]

fw@deneb.enyo.de (Florian Weimer)  wrote on 18.06.05 in <87oea3gz29.fsf@deneb.enyo.de>:

> * Paul Schlie:
>
> > So in effect the standard committee have chosen to allow any program which
> > invokes any undefined behavior to behave arbitrarily without diagnosis?
> >
> > This is a good thing?
>
> It's the way things are.  There isn't a real market for
> bounds-checking C compilers, for example, which offer well-defined
> semantics even for completely botched pointer arithmetic and pointer
> dereference.
>
> C isn't a programming language which protects its own abstractions
> (unlike Java, or certain Ada or Common Lisp subsets), and C never was
> intended to work this way.  Consequently, the committee was right to
> deal with undefined behavior in the way it did.  Otherwise, the
> industry would have adopted C as we know it, and the ISO C standard
> would have had the same relevance as, say, the ISO Pascal on the
> evolution of Pascal.

And yet, languages like ISO Pascal *still* define undefined behaviour  
pretty much the same way C does. They just choose a different set of  
situations (well, there *is* overlap) to apply it to.

Pretty much all languages which allow access to "the bare metal" need this  
escape clause, because making a program safe in that context pretty much  
requires the compiler to solve the halting problem or equivalent - and we  
can't do that. The alternative is putting enough padding between the  
program and the metal to enable the compiler and runtime system  
significantly more control - and, of course, giving the programmer  
significantly *less* control. For example, there won't be any type-punning  
in such a language. It's a very different trade-off.

MfG Kai

Re: basic VRP min/max range overflow question

[Mike Stump]

On Jun 18, 2005, at 11:50 AM, Paul Schlie wrote:
> [ curiously can't find any actual reference stating that integer  
> overflow
>   is specifically results in undefined behavior, although it's  
> obviously ill defined?

Every operation that isn't defined is undefined.  Only the operations  
that are defined, are defined.  Think about the implications of this.

Re: basic VRP min/max range overflow question

[Paul Schlie]

> From: "Joseph S. Myers" <joseph@codesourcery.com>
> "no requirements" means that *any* translation conforms in the case of
> undefined behavior.  Only those executions not involving undefined
> behavior have any requirements.

What delineates the bounds between undefined and non-undefined behaviors?

(As in the extreme if an undefined behavior may arbitrarily corrupt the
entire specified program state, and/or modify the languages otherwise
required semantics governing the translation/execution of a program, it
would seem that rather than attempting to utilize undefined behaviors as
a basis of optimizations, the compiler should more properly simply abort
compilation upon their detection, as the resulting program would be
otherwise be arguably useless for any likely purpose if the effect of an
undefined behavior within a program is not bounded?)

Re: basic VRP min/max range overflow question

[Robert Dewar]

Paul Schlie wrote:
>>From: "Joseph S. Myers" <joseph@codesourcery.com>
>>"no requirements" means that *any* translation conforms in the case of
>>undefined behavior.  Only those executions not involving undefined
>>behavior have any requirements.
> 
> 
> What delineates the bounds between undefined and non-undefined behaviors?
> 
> (As in the extreme if an undefined behavior may arbitrarily corrupt the
> entire specified program state, and/or modify the languages otherwise
> required semantics governing the translation/execution of a program, it
> would seem that rather than attempting to utilize undefined behaviors as
> a basis of optimizations, the compiler should more properly simply abort
> compilation upon their detection, as the resulting program would be
> otherwise be arguably useless for any likely purpose if the effect of an
> undefined behavior within a program is not bounded?)

But of COURSE you can't detect these situations at compile time. Even
if you had all the input in advance, this would be trivially equivalent
to solving the halting problem. Programming language definitions reserve
this use of undefined PRECISELY for those cases where it cannot be
determined statically whether some rule in the dynamic semantic
definition is or is not met.

When a compiler can determine that a given construct is sure to result
in undefined behavior, e.g. it can prove at compile time that overflow
will always occur, then indeed the best approach is to abort, or raise
some kind of exception (depending on the language), and to generate a
warning at compile time that this is going on. It CAN NOT "abort
compilation", since this is not an error condition, it would be improper
to refuse to compile the program. Besides which it would in practice
be wrong, since the compiler may very well be able to tell that a given
statement IF EXECUTED will cause trouble, but be unable to tell if in
fact it will be executed (my password program is like this, a friendly
compiler would warn that the reference to npasswords_entered (or whatever
I called it) results in undefined behavior, and an attentive programmer
who does not ignore warnings will deal with this warning before the
program causes chaotic results.
> 

Re: basic VRP min/max range overflow question

[Paul Schlie]

> From: Robert Dewar <dewar@adacore.com>
>> Paul Schlie wrote:
>>> From: "Joseph S. Myers" <joseph@codesourcery.com>
>>> "no requirements" means that *any* translation conforms in the case of
>>> undefined behavior.  Only those executions not involving undefined
>>> behavior have any requirements.
>> 
>> What delineates the bounds between undefined and non-undefined behaviors?
>> 
>> (As in the extreme if an undefined behavior may arbitrarily corrupt the
>> entire specified program state, and/or modify the languages otherwise
>> required semantics governing the translation/execution of a program, it
>> would seem that rather than attempting to utilize undefined behaviors as
>> a basis of optimizations, the compiler should more properly simply abort
>> compilation upon their detection, as the resulting program would be
>> otherwise be arguably useless for any likely purpose if the effect of an
>> undefined behavior within a program is not bounded?)
> 
> But of COURSE you can't detect these situations at compile time. Even
> if you had all the input in advance, this would be trivially equivalent
> to solving the halting problem. Programming language definitions reserve
> this use of undefined PRECISELY for those cases where it cannot be
> determined statically whether some rule in the dynamic semantic
> definition is or is not met.
> 
> When a compiler can determine that a given construct is sure to result
> in undefined behavior, e.g. it can prove at compile time that overflow
> will always occur, then indeed the best approach is to abort, or raise
> some kind of exception (depending on the language), and to generate a
> warning at compile time that this is going on. It CAN NOT "abort
> compilation", since this is not an error condition, it would be improper
> to refuse to compile the program. Besides which it would in practice
> be wrong, since the compiler may very well be able to tell that a given
> statement IF EXECUTED will cause trouble, but be unable to tell if in
> fact it will be executed (my password program is like this, a friendly
> compiler would warn that the reference to npasswords_entered (or whatever
> I called it) results in undefined behavior, and an attentive programmer
> who does not ignore warnings will deal with this warning before the
> program causes chaotic results.

The root of the concern being expressed is with respect to the compilers use
of statically identified undefined behaviors as opportunities to invoke
alternative semantics which are easily identified as being inconsistent with
the target's native semantics, thus altering the logical behavior of the
program than would otherwise have resulted. (without any halting solutions
required)

As candidly, regardless of this being technically allowed, it should obvious
that any optimization which may likely alter the behavior of a program
should never be invoked without explicit request and ideally diagnosis of
the resulting alternative possibly undesired and/or fatal behavior.

To be more clear, specifically as examples:

- As VRP relies on the static analysis of value ranges, primarily based
on embedded implicit and/or explicit constant values which enables the
detection of both bound ranges and potential value range overflows, this
information may be used to both identify both known safe optimizations,
as well as those known to be potentially unsafe based upon the easily
identifiable true overflow behavior of the target. Therefore is seems
clear that the most desirable default behavior for VRP based optimizations
would be to only enable those which are known to be safe (i.e. not alter
the behavior of the resulting program, nor requires a halting problem be
solved), by default; and enable through an explicit command line switch
the presumption that no integer overflows will occur, with optionally the
warning diagnosis of all locations were potential overflow was identified
and may result in differing program behavior. (Again no halting problems
need to solved)

- Correspondingly, as pointer null comparison optimizations are known to be
unsafe for targets which are known to not trap null-pointer dereferences,
this optimization should only be enabled by default for targets which are
known to do so (regardless of if it's perceived to be "technically allowed",
as it should be obvious that any optimization which will identifiably alter
program behavior should never be invoked by default at any optimization
level without explicit request and optional corresponding diagnosis).

As just my opinion, and possibly the opinion of many who've ever cursed
the result of an optimization's altering a program's logical behavior
(which I can't imagine as ever being desirable in any circumstance, as
optimizations should ideally eliminate logical redundancies, not alter
logical semantics, without explicit request).

Re: basic VRP min/max range overflow question

[Robert Dewar]

Paul Schlie wrote:

> The root of the concern being expressed is with respect to the compilers use
> of statically identified undefined behaviors as opportunities to invoke
> alternative semantics which are easily identified as being inconsistent with
> the target's native semantics, thus altering the logical behavior of the
> program than would otherwise have resulted. (without any halting solutions
> required)

You are still not understanding, these are NOT cases of "statically
identified undefined behavior". Those are the trivial cases that are
uninterestig.
> 
> As candidly, regardless of this being technically allowed, it should obvious
> that any optimization which may likely alter the behavior of a program
> should never be invoked without explicit request and ideally diagnosis of
> the resulting alternative possibly undesired and/or fatal behavior.

If the behavior is undefined, then it is undefined, and you cannot
talk about a change in behavior. This is what non-deterministic semantics
is about.
> 
> To be more clear, specifically as examples:
> 
> - As VRP relies on the static analysis of value ranges, primarily based
> on embedded implicit and/or explicit constant values which enables the

It most certainly is NOT possible to statically identify situations that
cause overflow. I cannot believe this is not clear to you.

Re: basic VRP min/max range overflow question

[Paul Schlie]

> From: Robert Dewar <dewar@adacore.com>
>> Paul Schlie wrote:
>> The root of the concern being expressed is with respect to the compilers use
>> of statically identified undefined behaviors as opportunities to invoke
>> alternative semantics which are easily identified as being inconsistent with
>> the target's native semantics, thus altering the logical behavior of the
>> program than would otherwise have resulted. (without any halting solutions
>> required)
> 
> You are still not understanding, these are NOT cases of "statically
> identified undefined behavior". Those are the trivial cases that are
> uninterestig.

OK, assuming I may misunderstand, the following is my understanding:

- presently if GCC STATICALLY identifies a pointer dereference which
  precedes a pointer null comparison, it presumes that the comparison may
  be optimized away under the rationalization that preceding dereference
  would be trapped, and if not, rationalizes that an undefined behavior
  grants it permission do what it wants regardless of the fact that it
  is only safe (logically equivalent) to do so for targets which are known
  to trap null dereferences.

- given the following code fragment:

  int x, y;
  volatile z;

  x = z ? 1 : 2;    // x == [1, 2]
  y = z ? z + x;    // y == [INT_MIN+1, INT_MAX+2]

  if (x < 0)        // which may be safely optimized away as
    somthing();     // [1, 2] is STATICALLY known to be never < 0.

  if (y == INT_MIN) // which may not be safely optimized away unless
    something();    // it is known that the target does not wrap overflow.

My position is simply that an optimization should never remove a specified
operation unless it is known to yield logically equivalent behavior, as
producing a program which does not behave as specified is not a good idea,
to be polite, unless specifically requested to do so; as if the programmer
didn't intend the code to be evaluated, it wouldn't have been specified;
regardless of the compilers presumed license to do what ever it pleases
when encountering a STATICALLY identified/potential undefined behavior.


>> As candidly, regardless of this being technically allowed, it should obvious
>> that any optimization which may likely alter the behavior of a program
>> should never be invoked without explicit request and ideally diagnosis of
>> the resulting alternative possibly undesired and/or fatal behavior.
> 
> If the behavior is undefined, then it is undefined, and you cannot
> talk about a change in behavior. This is what non-deterministic semantics
> is about.

I guess I simply believe that optimizations should never alter the logical
behavior of a specified program relative to it's un-optimized form unless
explicitly granted permission to do so, therefore such optimizations should
never be considered enabled at any level of optimization by default.

As I personally I believe the unbounded liberty to arbitrary alter the
logical evaluation of program statements/expressions distinct from those
which are considered undefined without explicit permission is misguided.

As it's likely more useful/important that optimizations preserve the
behavior of even non-portable programs, than it likely useful/important
to produce a faster program which may have an arbitrary different behavior.

>> To be more clear, specifically as examples:
>> 
>> - As VRP relies on the static analysis of value ranges, primarily based
>> on embedded implicit and/or explicit constant values which enables the
> 
> It most certainly is NOT possible to statically identify situations that
> cause overflow. I cannot believe this is not clear to you.

Actually it is (or we may be talking about different things, see below).

But regardless, what's important is identifying those with predicable value
ranges, as they are the only ones which may be safely used for optimizations
i.e.:

Known no overflow:
 [1, 4] = [0, 1] + [1, 3];   // safe to use as a basis of VRP optimization.

Possible overflow:
 [?, ?] = [0, 1] + [0, INT_MAX]; // unsafe without OverFlow knowledge.

~[INT_MIN+1, -1] = [0, 1] + [0, INT_MAX] // safe with 2's comp OvF.

Known overflow:
 [?, ?] = [INT_MAX-1 INT_MAX] + INT_MAX; // unsafe without OvF knowledge.

 [-3, -2] = [INT_MAX-1, INT_MAX] + INT_MAX; // known safe with 2's comp OvF

(What undefined overflow semantics should really be utilized to provide is
target specific overflow optimization based on a targets native overflow
semantics, which would be a whole lot more useful than pretending otherwise
and risk altering the programs otherwise un-optimized behavior.)

Again, just my opinion (as after all, undefined semantics enable the
compiler to do anything, so might as well do something more useful than not
:)

Re: basic VRP min/max range overflow question

[Michael Veksler]

Paul Schlie wrote on 20/06/2005 08:55:20:
>   y = z ? z + x;    // y == [INT_MIN+1, INT_MAX+2]

Invalid syntax, what did you mean?

> I guess I simply believe that optimizations should never alter the
logical
> behavior of a specified program relative to it's un-optimized form unless
> explicitly granted permission to do so, therefore such optimizations
should
> never be considered enabled at any level of optimization by default.

As a user I sympathize with this wish. As someone who spent a whole
day wading through assembly to analyze a bug (undefined
behavior), I can tell you that I don't like it either.

Yet, as a developer of another system with strict semantics I can
say that, in general, your requirements are impossible to follow,
unless very carefully worded.

This requirement for "never alter the logical behavior" implicitly
forbids all optimizations in a language like C.
For example consider:

1: void foo()
2: {
3:     int a;
4:     printf("%d\n", a); /* undefined behavior */
5: }
6: void bar()
7: {
8:     do something;
9: }
10:int main()
11:{
12:    bar();
13:    foo();
14:    return 0;
15:}

Almost any optimization over line 8 will change the
behavior of line 4. I believe that you did not intend to
cover this case in your requirement. Maybe you would
like to narrow the requirement such that it enumerates
all the cases you consider to "alter the logical behavior".
And even if you do, you'll have to be very careful to
define a consistent semantics for each case.



   Michael

Re: basic VRP min/max range overflow question

[Paul Schlie]

> From: Michael Veksler <VEKSLER@il.ibm.com>
> Paul Schlie wrote on 20/06/2005 08:55:20:
>>   y = z ? z + x;    // y == [INT_MIN+1, INT_MAX+2]
> Invalid syntax, what did you mean?

Sorry, meant:
  y = z + x; // y == [INT_MIN, INT_MAX] + [1, 2] == [INT_MIN+1, INT_MAX+2]

>> I guess I simply believe that optimizations should never alter the
>> logical behavior of a specified program relative to it's un-optimized
>> form unless explicitly granted permission to do so, therefore such
>> optimizations should never be considered enabled at any level of
>> optimization by default.
> 
> As a user I sympathize with this wish. As someone who spent a whole
> day wading through assembly to analyze a bug (undefined
> behavior), I can tell you that I don't like it either.
> 
> Yet, as a developer of another system with strict semantics I can
> say that, in general, your requirements are impossible to follow,
> unless very carefully worded.
> 
> This requirement for "never alter the logical behavior" implicitly
> forbids all optimizations in a language like C.
> For example consider:
> 
> 1: void foo()
> 2: {
> 3:     int a;
> 4:     printf("%d\n", a); /* undefined behavior */
> 5: }
> 6: void bar()
> 7: {
> 8:     do something;
> 9: }
> 10:int main()
> 11:{
> 12:    bar();
> 13:    foo();
> 14:    return 0;
> 15:}
> 
> Almost any optimization over line 8 will change the
> behavior of line 4. I believe that you did not intend to
> cover this case in your requirement. Maybe you would
> like to narrow the requirement such that it enumerates
> all the cases you consider to "alter the logical behavior".
> And even if you do, you'll have to be very careful to
> define a consistent semantics for each case.

Understood, but tried to be careful with my wording, as I didn't say alter
the resulting value, but rather alter the logical behavior (i.e. semantics).

As in my mind, the semantics of foo() dictate that it print the value of
the storage location which was allocated to the variable "a", where unless
"a" is initialized with an explicit value, may be arbitrary. So I've got no
problem with arbitrary results or behavior, I just simply believe they are
implicitly constrained to the remaining rules of the language, i.e. all
side-effects must be expressed upon reaching a sequence point which
logically bounds the effects of the evaluation of any expression.

(where if an undefined behavior it did delete the program being executed it
wouldn't resume execution beyond the next sequence point, but if it does, it
must continue to abide by the languages rules regardless of the resulting
side effects from the preceding behaviors)

Re: basic VRP min/max range overflow question

[Robert Dewar]

Paul Schlie wrote:

> As in my mind, the semantics of foo() dictate that it print the value of
> the storage location which was allocated to the variable "a", where unless
> "a" is initialized with an explicit value, may be arbitrary. So I've got no
> problem with arbitrary results or behavior, I just simply believe they are
> implicitly constrained to the remaining rules of the language, i.e. all
> side-effects must be expressed upon reaching a sequence point which
> logically bounds the effects of the evaluation of any expression.

This cannot be formalized, and is not what the standard says. The fact that
you believe it is interesting (though I don't think you can write a formal
description of what you believe in C standard terms), but we operate by what
the standard formally says, not by what one person informally believes.
> 
> (where if an undefined behavior it did delete the program being executed it
> wouldn't resume execution beyond the next sequence point, but if it does, it
> must continue to abide by the languages rules regardless of the resulting
> side effects from the preceding behaviors)

Sequence points simply do not have this semantics. If they did, then nearly
all useful optimizations would be prohibited. You are essentially positing
a model in which the state at every sequence point is not only defined by
the standard, but must be reflected in the implementation with no use of
as-if semantics. I don't see this as meaningful, and I don't think this can
be formalized. I am quite *sure* that it is undesirable.

Re: basic VRP min/max range overflow question

[Paul Schlie]

> From: Robert Dewar <dewar@adacore.com>
> Paul Schlie wrote:
> 
>> As in my mind, the semantics of foo() dictate that it print the value of
>> the storage location which was allocated to the variable "a", where unless
>> "a" is initialized with an explicit value, may be arbitrary. So I've got no
>> problem with arbitrary results or behavior, I just simply believe they are
>> implicitly constrained to the remaining rules of the language, i.e. all
>> side-effects must be expressed upon reaching a sequence point which
>> logically bounds the effects of the evaluation of any expression.
> 
> This cannot be formalized, and is not what the standard says. The fact that
> you believe it is interesting (though I don't think you can write a formal
> description of what you believe in C standard terms), but we operate by what
> the standard formally says, not by what one person informally believes.
>
>> (where if an undefined behavior it did delete the program being executed it
>> wouldn't resume execution beyond the next sequence point, but if it does, it
>> must continue to abide by the languages rules regardless of the resulting
>> side effects from the preceding behaviors)
> 
> Sequence points simply do not have this semantics. If they did, then nearly
> all useful optimizations would be prohibited. You are essentially positing
> a model in which the state at every sequence point is not only defined by
> the standard, but must be reflected in the implementation with no use of
> as-if semantics. I don't see this as meaningful, and I don't think this can
> be formalized. I am quite *sure* that it is undesirable.

- You may be correct, although it's not obviously the case? (As requiring
  all undefined behavior be encapsulated between sequence points already
  seems implied to me, as I don't see any explicit counter examples
  requiring otherwise. Nor do any optimizations which are obviously more
  useful than potentially counterproductive seem to require the violation of
  C's sequence point semantics?)

Re: basic VRP min/max range overflow question

[Robert Dewar]

Paul Schlie wrote:

> - You may be correct, although it's not obviously the case? (As requiring
>   all undefined behavior be encapsulated between sequence points already
>   seems implied to me, as I don't see any explicit counter examples
>   requiring otherwise. 

There don't need to be examples. The as-if rule always applies, if you cannot
write a legitimate C program that shows the difference between two possible
implementations, then both are correct. Note that the requirement of a legitimate
C program exlude ANY program which has undefined behavior anywhere.

 >   Nor do any optimizations which are obviously more
 >   useful than potentially counterproductive seem to require the violation of
 >   C's sequence point semantics?)

Ordinary code motion optimizations like hoisting out of a loop are an obvious
example, there are lots of others. If you read the dragon book (are you familiar
with this book?) then almost all optimizations discussed there in the global
optimization chapters would be affected.

Re: basic VRP min/max range overflow question

[Paul Schlie]

> From: Robert Dewar <dewar@adacore.com>
>> Paul Schlie wrote:
> 
>> - You may be correct, although it's not obviously the case? (As requiring
>>   all undefined behavior be encapsulated between sequence points already
>>   seems implied to me, as I don't see any explicit counter examples
>>   requiring otherwise.
> 
> There don't need to be examples. The as-if rule always applies, if you cannot
> write a legitimate C program that shows the difference between two possible
> implementations, then both are correct.

??? as-if means they're logically equivalent (i.e. there is no logical
difference between the two alternative representations, and strongly support
that this should be the guideline for all optimizations).

>                                                Note that the requirement of a
> legitimate C program exlude ANY program which has undefined behavior anywhere.

Then it is illegitimate for a compiler to generate a program which contains
a known undefined behavior, (i.e. any known overflow, any unsigned to signed
cast which is known to not be representable, any pointer dereference of a
known null value, etc.; rather than generate any code.)

>>   Nor do any optimizations which are obviously more
>>   useful than potentially counterproductive seem to require the violation of
>>   C's sequence point semantics?)
> 
> Ordinary code motion optimizations like hoisting out of a loop are an obvious
> example, there are lots of others. If you read the dragon book (are you
> familiar with this book?) then almost all optimizations discussed there in the
> global optimization chapters would be affected.

Expression reordering does not necessitate the violation of sequence point
semantics as long as at the last point of reordering, the resulting
semantics are logically equivalent (as-if); which is why it's a safe
optimization if the logical behavior is preserved.

Re: basic VRP min/max range overflow question

[Robert Dewar]

Paul Schlie wrote:

>>There don't need to be examples. The as-if rule always applies, if you cannot
>>write a legitimate C program that shows the difference between two possible
>>implementations, then both are correct.
> 
> 
> ??? as-if means they're logically equivalent (i.e. there is no logical
> difference between the two alternative representations, and strongly support
> that this should be the guideline for all optimizations).

as if means what I said in the above quoted paragraph. I do not know what
"no logical difference" means if it is different from the above criterion.
> 
> 
>>                                               Note that the requirement of a
>>legitimate C program exlude ANY program which has undefined behavior anywhere.
> 
> 
> Then it is illegitimate for a compiler to generate a program which contains
> a known undefined behavior, (i.e. any known overflow, any unsigned to signed
> cast which is known to not be representable, any pointer dereference of a
> known null value, etc.; rather than generate any code.)

No, that's plain untrue, I don't know how you got that idea.

> Expression reordering does not necessitate the violation of sequence point
> semantics as long as at the last point of reordering, the resulting
> semantics are logically equivalent (as-if); which is why it's a safe
> optimization if the logical behavior is preserved.

Again, as-if behavior means that it is not possible to write a correct
C program that distinguishes the cases. No program containing an overflow
can be used for such a test.
> 

Re: basic VRP min/max range overflow question

[Michael Veksler]

Paul Schlie <schlie@comcast.net> wrote on 20/06/2005 14:03:53:
> > From: Michael Veksler <VEKSLER@il.ibm.com>
...
> > Almost any optimization over line 8 will change the
> > behavior of line 4. I believe that you did not intend to
> > cover this case in your requirement. Maybe you would
> > like to narrow the requirement such that it enumerates
> > all the cases you consider to "alter the logical behavior".
> > And even if you do, you'll have to be very careful to
> > define a consistent semantics for each case.
>
> Understood, but tried to be careful with my wording, as I didn't say
alter
> the resulting value, but rather alter the logical behavior (i.e.
semantics).
>
> As in my mind, the semantics of foo() dictate that it print the value of
> the storage location which was allocated to the variable "a", where
unless
> "a" is initialized with an explicit value, may be arbitrary. So I've got
no
> problem with arbitrary results or behavior, I just simply believe they
are
> implicitly constrained to the remaining rules of the language, i.e. all
> side-effects must be expressed upon reaching a sequence point which
> logically bounds the effects of the evaluation of any expression.
>
> (where if an undefined behavior it did delete the program being executed
it
> wouldn't resume execution beyond the next sequence point, but if it does,
it
> must continue to abide by the languages rules regardless of the resulting
> side effects from the preceding behaviors)
>


This definition is not rigorous enough. What is a side-effect?
Can the side-effect modify the executed code itself? In that
case all bets are off, again.

Consider:
1: int *p;
2: *p=0x12345678;
3: printf("rm -rf /");

Isn't it possible that executing line 2 will mutate line 3 to:
3: system("rm -rf /");

As in my previous example, optimization level can change the initial
junk in 'p', and as a result the behavior will range from the benign
"p = (int*)0x12345678" to the destructive 'system("rm -rf /")'.

Do you consider the side-effect to be "bounded" in this
example? How can you tell this case from other cases of
undefined behavior? Do you have a formal definition?
Can you validate its consistency?

Getting a consistent definition of "bounded side-effects"
is a nontrivial task. Simply hacking and patching the
definition does not work. Trust me, I've been there done
that, got burnt and are still paying for my sins.


  Michael

Re: basic VRP min/max range overflow question

[Robert Dewar]

Michael Veksler wrote:

> Getting a consistent definition of "bounded side-effects"
> is a nontrivial task. Simply hacking and patching the
> definition does not work. Trust me, I've been there done
> that, got burnt and are still paying for my sins.

Indeed! I think anyone who has been involved in the arduous
work of formal language definition is very aware of this. At
one point people designing Ada wanted to make functions side
effect free, we quickly discovered this was not useful since
a useful definition could not be formalized (e.g. is a pure
function that works by using a memo table side effect free?)

Re: basic VRP min/max range overflow question

[Robert Dewar]

Paul Schlie wrote:

> My position is simply that an optimization should never remove a specified
> operation unless it is known to yield logically equivalent behavior, as
> producing a program which does not behave as specified is not a good idea

That may be your position, but it is not the position of the standard, and
indeed it is not a well-formed position. Why, because the whole point is that
when the behavior is undefined, then the change DOES yield a logically
equivalent behavior, because undefined means undefined, and all possible
behaviors are logicaly equivalent to undefined.

Note that in the cases where something is statically optimized away (these
are the easy cases), it is nice if the compiler warns that this is happening
(that would certainly be the case in Ada in the corresponding situation, not
sure about C++). But of course no such warning is required.

Re: basic VRP min/max range overflow question

[Robert Dewar]

Robert Dewar wrote:

> That may be your position, but it is not the position of the standard, and
> indeed it is not a well-formed position. Why, because the whole point is 
> that
> when the behavior is undefined, then the change DOES yield a logically
> equivalent behavior, because undefined means undefined, and all possible
> behaviors are logicaly equivalent to undefined.

To add to this, I can see how you might feel that even if the standard
allows this behavior it is non-desirable, but I don't even agree with that.
The trouble is if the compiler makes this "work", then C programmers who
don't really know the language end up depending on it, and writing what
is essentially junk non-portable code. It is a GOOD THING if C programmers
are burned by this and learn the language. It is perfectly possible to
write portable programs in C, but you have to know the language to do it,
and knowing the language means knowing what the actual rules are, not just
being familiar with the behavior of a particular compiler.

Re: basic VRP min/max range overflow question

[Paul Schlie]

> From: Robert Dewar <dewar@adacore.com>
> Robert Dewar wrote:
> 
>> That may be your position, but it is not the position of the standard, and
>> indeed it is not a well-formed position. Why, because the whole point is
>> that
>> when the behavior is undefined, then the change DOES yield a logically
>> equivalent behavior, because undefined means undefined, and all possible
>> behaviors are logicaly equivalent to undefined.
> 
> To add to this, I can see how you might feel that even if the standard
> allows this behavior it is non-desirable, but I don't even agree with that.
> The trouble is if the compiler makes this "work", then C programmers who
> don't really know the language end up depending on it, and writing what
> is essentially junk non-portable code. It is a GOOD THING if C programmers
> are burned by this and learn the language. It is perfectly possible to
> write portable programs in C, but you have to know the language to do it,
> and knowing the language means knowing what the actual rules are, not just
> being familiar with the behavior of a particular compiler.

I too believe I understand your position, however don't believe it's the
compiler's job to make life for the programmer harder than it need be when
a program may contain an undefined behavior; but agree it would likely
always be helpful to for it to point them out when identifiable.

Re: basic VRP min/max range overflow question

[Robert Dewar]

Paul Schlie wrote:

> I too believe I understand your position, however don't believe it's the
> compiler's job to make life for the programmer harder than it need be when
> a program may contain an undefined behavior; but agree it would likely
> always be helpful to for it to point them out when identifiable.

I really don't care too much about making life harder for the programmer
who originally writes code if it makes it easier for people maintaining
and porting the code down the line. I think it is a good idea if people
writing C know C (substitute any other language you like for C here :-)

Re: basic VRP min/max range overflow question

[Paul Schlie]

> From: Robert Dewar <dewar@adacore.com>
> Paul Schlie wrote:
> 
>> I too believe I understand your position, however don't believe it's the
>> compiler's job to make life for the programmer harder than it need be when
>> a program may contain an undefined behavior; but agree it would likely
>> always be helpful to for it to point them out when identifiable.
> 
> I really don't care too much about making life harder for the programmer
> who originally writes code if it makes it easier for people maintaining
> and porting the code down the line. I think it is a good idea if people
> writing C know C (substitute any other language you like for C here :-)

It's not clear to me that intentionally altering the semantics of a program
as a result of an undefined behavior in any single way is very productive
towards that goal, as unless the alternative behavior happens to be caught,
it may only likely result in a latent bug which the programmer thought
wouldn't occur based on the code specified, and/or the confirmed behavior of
the program prior to optimization. However having the compiler point out
potentially undefined non-portable expressions seems very useful, especially
if it attempts to maintain their semantics through optimization, albeit
non-portably.

Re: basic VRP min/max range overflow question

[Paul Schlie]

> From: Robert Dewar <dewar@adacore.com>
> Paul Schlie wrote:
> 
>> My position is simply that an optimization should never remove a specified
>> operation unless it is known to yield logically equivalent behavior, as
>> producing a program which does not behave as specified is not a good idea
> 
> That may be your position, but it is not the position of the standard, and
> indeed it is not a well-formed position. Why, because the whole point is that
> when the behavior is undefined, then the change DOES yield a logically
> equivalent behavior, because undefined means undefined, and all possible
> behaviors are logicaly equivalent to undefined.
> 
> Note that in the cases where something is statically optimized away (these
> are the easy cases), it is nice if the compiler warns that this is happening
> (that would certainly be the case in Ada in the corresponding situation, not
> sure about C++). But of course no such warning is required.

Agreed. And given that the standard enables an implementation to do anything
upon encountering an undefined behavior, it just seems just as correct to
simply presume that the behavior will be consistent with the targets native
behavior; as just because it may enable the compiler to do anything, it
doesn't imply that it should, or that it would be a good idea to do so.

Re: basic VRP min/max range overflow question

[Michael Veksler]

Paul Schlie wrote on 20/06/2005 14:13:33:
> > From: Robert Dewar <dewar@adacore.com>
...
> > Note that in the cases where something is statically optimized away
(these
> > are the easy cases), it is nice if the compiler warns that this is
happening
> > (that would certainly be the case in Ada in the corresponding
situation, not
> > sure about C++). But of course no such warning is required.
>
> Agreed. And given that the standard enables an implementation to do
anything
> upon encountering an undefined behavior, it just seems just as correct to
> simply presume that the behavior will be consistent with the targets
native
> behavior; as just because it may enable the compiler to do anything, it
> doesn't imply that it should, or that it would be a good idea to do so.
>

Agreed in theory. Can you define "to do anything" ? What aspects
of the language can be defined as "native behavior"? What aspects
are always undefined? (e.g. uninitialized pointer dereference?).

As for overflow, you can say that you want instead of "undefined"
to treat is "unspecified". Where each architecture / opsys / compiler
must consistently define what happens on overflow:
 - saturation
 - wrap 2's (or 1's) complement
 - exception.
You can argue (and maybe show benchmarks) that the above
"unspecified" does not inhibit too many real world optimizations,
as compared with "undefined". If that were the case, you would
have a chance convincing the std and gcc of your views.

However, generalizing things for all "undefined behavior" is
doomed to failure. Not all "undefined behaviors" were born equal,
and you can't treat them as equal, unless they
"enable the compiler to do anything".

You can be pragmatic, and try hard to minimize the cases where
the compiler happens "to do anything", but you cannot formally
guarantee that it will never happen. If you are not careful you may
end up with a spaghetti compiler full of special code geared
at the avoiding many of the "to do anything" cases.


  Michael

Re: basic VRP min/max range overflow question

[Robert Dewar]

Michael Veksler wrote:

> As for overflow, you can say that you want instead of "undefined"
> to treat is "unspecified". 

In Ada 95 we introduced a new category of behavior, called a bounded
error. We tried to recategorize as many erroneous (= C undefined)
cases as possible to bounded error.

A bounded error is still considered incorrect programming, but the
standard specifies the range of possible results allowed.

Re: basic VRP min/max range overflow question

[Paul Schlie]

> From: Michael Veksler <VEKSLER@il.ibm.com>>
>> Paul Schlie wrote on 20/06/2005 14:13:33:
>>> From: Robert Dewar <dewar@adacore.com>
> ...
>>> Note that in the cases where something is statically optimized away
>>> (these are the easy cases), it is nice if the compiler warns that this
>>> is happening that would certainly be the case in Ada in the corresponding
>>> situation, not sure about C++). But of course no such warning is required.
>> 
>> Agreed. And given that the standard enables an implementation to do
>> anything
>> upon encountering an undefined behavior, it just seems just as correct to
>> simply presume that the behavior will be consistent with the targets
>> native
>> behavior; as just because it may enable the compiler to do anything, it
>> doesn't imply that it should, or that it would be a good idea to do so.
>> 
> 
> Agreed in theory. Can you define "to do anything" ? What aspects
> of the language can be defined as "native behavior"? What aspects
> are always undefined? (e.g. uninitialized pointer dereference?).
> 
> As for overflow, you can say that you want instead of "undefined"
> to treat is "unspecified". Where each architecture / opsys / compiler
> must consistently define what happens on overflow:
>  - saturation
>  - wrap 2's (or 1's) complement
>  - exception.

- yes, effectively I don't perceive any necessity for undefined, vs
unspecified; as I don't perceive any necessity to give the compiler
the freedom to treat generate an arbitrary program which may contain
a potentially ambiguous specific and isolatable behavior. Again, is
seems real simple to abide by C's sequence point and as-if rules to contain
any ambiguity to the bounds between it's logical sequence points, and any
resulting side-effects specific to that ambiguity must be expressed and
logically bounded there.

> You can argue (and maybe show benchmarks) that the above
> "unspecified" does not inhibit too many real world optimizations,
> as compared with "undefined". If that were the case, you would
> have a chance convincing the std and gcc of your views.

- can one show that it is unreasonable?

> However, generalizing things for all "undefined behavior" is
> doomed to failure. Not all "undefined behaviors" were born equal,
> and you can't treat them as equal, unless they
> "enable the compiler to do anything".

- example?

> You can be pragmatic, and try hard to minimize the cases where
> the compiler happens "to do anything", but you cannot formally
> guarantee that it will never happen. If you are not careful you may
> end up with a spaghetti compiler full of special code geared
> at the avoiding many of the "to do anything" cases.
> 
> 
>   Michael
> 

Re: basic VRP min/max range overflow question

[Robert Dewar]

Paul Schlie wrote:

> - yes, effectively I don't perceive any necessity for undefined, vs
> unspecified; as I don't perceive any necessity to give the compiler
> the freedom to treat generate an arbitrary program which may contain
> a potentially ambiguous specific and isolatable behavior.

OK, then you are definitely on a different planet when it comes to
designing languages of this class (C, Ada, PL/1, Pascal, ALgol etc).
Everyone of these language definitions sees a critical need for this
differentiation. It is indeed somewhat fundamental.

Re: basic VRP min/max range overflow question

[Michael Veksler]

Paul Schlie <schlie@comcast.net> wrote on 20/06/2005 16:09:16:
> > From: Michael Veksler <VEKSLER@il.ibm.com>>
> > As for overflow, you can say that you want instead of "undefined"
> > to treat is "unspecified". Where each architecture / opsys / compiler
> > must consistently define what happens on overflow:
> >  - saturation
> >  - wrap 2's (or 1's) complement
> >  - exception.
>
> - yes, effectively I don't perceive any necessity for undefined, vs
> unspecified; as I don't perceive any necessity to give the compiler
> the freedom to treat generate an arbitrary program which may contain
> a potentially ambiguous specific and isolatable behavior. Again, is
> seems real simple to abide by C's sequence point and as-if rules to
contain
> any ambiguity to the bounds between it's logical sequence points, and any
> resulting side-effects specific to that ambiguity must be expressed and
> logically bounded there.

Look again at my dangling pointer example. In this example, the most
benign optimizations may "generate an arbitrary program" in this case.
As I said, and as Robert Dewar concurred, you can carefully define
something less strict than "undefined" on a case by case basis.
On the other hand, it is impossible to make all "undefined" cases
demonstrate an "isolatable behavior". Such a broad requirement is
impossible to fulfill, as my dangling pointer example shows.

>
> > You can argue (and maybe show benchmarks) that the above
> > "unspecified" does not inhibit too many real world optimizations,
> > as compared with "undefined". If that were the case, you would
> > have a chance convincing the std and gcc of your views.
>
> - can one show that it is unreasonable?
Someone will have to prove it first. Just waving hands will
convince nobody. Maybe if you are lucky, you may convince
somebody to make an experiment, that in the end may or may
not lead to changes in gcc or the std.
>
> > However, generalizing things for all "undefined behavior" is
> > doomed to failure. Not all "undefined behaviors" were born equal,
> > and you can't treat them as equal, unless they
> > "enable the compiler to do anything".
>
> - example?

Again, the dangling pointer example. Dangling pointer may or
may not lead to the corruption of the code itself (self modifying
code). When that inadvertently happens, all bets are off.
It is possible that by pure luck the code is "safe" without
optimization, and after optimizing unrelated stuff the
code becomes self destructive.


This is one of the cases of "undefined" behavior that cannot be
reasonably bounded. Would you like to sub-categorize
"undefined" to get rid of cases like the dangling pointer?
Are you willing to make sure that they are OK?
Again, this is a nontrivial task to get right. You can't get
it simply by disabling optimization X or fixing optimization Y.

This is out of the scope of this list. This list is not intended
to discuss and define new language semantics. You will have
to either come up with a reasonable definition yourself, or
get help from experts in the field. And only then go to the
std or gcc.
I have been burnt by these issues too many times exactly
because I am not an expert in the field, I am still learning.
You too should try to be more cautious in the treacherous
realm of language specification. Are you sure you want
to go there?

   Michael

Re: basic VRP min/max range overflow question

[Paul Schlie]

> From: Michael Veksler <VEKSLER@il.ibm.com>
>> Paul Schlie <schlie@comcast.net> wrote on 20/06/2005 16:09:16:
>>> From: Michael Veksler <VEKSLER@il.ibm.com>>
>>> As for overflow, you can say that you want instead of "undefined"
>>> to treat is "unspecified". Where each architecture / opsys / compiler
>>> must consistently define what happens on overflow:
>>>  - saturation
>>>  - wrap 2's (or 1's) complement
>>>  - exception.
>> 
>> - yes, effectively I don't perceive any necessity for undefined, vs
>> unspecified; as I don't perceive any necessity to give the compiler
>> the freedom to treat generate an arbitrary program which may contain
>> a potentially ambiguous specific and isolatable behavior. Again, is
>> seems real simple to abide by C's sequence point and as-if rules to
>> contain any ambiguity to the bounds between it's logical sequence points,
>> and any resulting side-effects specific to that ambiguity must be expressed
>> and logically bounded there.
> 
> Look again at my dangling pointer example. In this example, the most
> benign optimizations may "generate an arbitrary program" in this case.
> As I said, and as Robert Dewar concurred, you can carefully define
> something less strict than "undefined" on a case by case basis.
> On the other hand, it is impossible to make all "undefined" cases
> demonstrate an "isolatable behavior". Such a broad requirement is
> impossible to fulfill, as my dangling pointer example shows.
>
> ... Dangling pointer may or may not lead to the corruption of the code
> itself (self modifying code). When that inadvertently happens, all bets
> are off. It is possible that by pure luck the code is "safe" without
> optimization, and after optimizing unrelated stuff the code becomes self
> destructive.

For what its worth, I don't consider this a problem, as long as the
semantics (including the relative sequencing) of any dangling pointer are
preserved in the process, regardless of the potentially unpredictable and/or
dire consequences they may have.

As it is just this uncertainty which I view as the basis of compiler's
constraint; as unlike the apparently popular view that something which is
un/ill-defined provides license to modify specified code in any way desired;
I view the uncertainty as a constraint which forbids the compiler from
presuming it's reference will store or return any predictable value,
therefore can not be used as a basis of any optimization, therefore must
preserve whatever unpredictable behavior may result upon it's execution
within some potentially arbitrary environment, while continuing to presume
that the remaining program semantics and state are preserved, therefore may
continue to be optimized based upon any predictable side-effects which are
not logically dependant on dangling pointer references.

Thereby strictly preserving the program's semantics as authored, as
potentially unpredictable and possibly unrepeatable as the resulting
behavior may be; as I perceive to do otherwise as being inconsistent with
the program as authored, although would expect a suitable warning alerting
the programmer of it's likely unintended potential consequences if a
dangling pointer references are identifiable; where if not, then all things
remain the same, i.e. only known safe optimizations are enabled to be
performed which by definition precludes any dependant on unpredictable value
ranges and/or behaviors.

Re: basic VRP min/max range overflow question

[Joseph S. Myers]

On Sat, 18 Jun 2005, Paul Schlie wrote:

> > You appear to have confused unspecified behavior (where the possibilities
> > are bounded) and undefined behavior (where the possibilities are
> > unbounded).  On *undefined* behavior (such as signed integer overflow),
> > *this International Standard imposes no requirements*.  If a program
> > execution involved undefined behavior, *there are no requirements on its
> > execution, even before the undefined behavior occurs in the abstract
> > machine*.
> 
> No, the standard clearly states that it imposes no requirements on the
> behavior which an implementation may choose to implement for (and limited
> to) that specific undefined behavior; as regardless of that behavior, it's
> resulting side effects clearly remains constrained by the rules as specified
> in 5.1.2.3.
> 
>        [#1] Behavior where this International Standard provides two
>        or  more  possibilities and imposes no requirements on which
>        is chosen in any instance.  A program that is correct in all
>        other   aspects,   operating  on  correct  data,  containing
>        unspecified behavior shall be a correct program and  act  in
>        accordance with subclause 5.1.2.3.

1. This section describes unspecified behavior, not undefined behavior.  
This discussion is about undefined behavior, not unspecified behavior.  
You appear to be trying deliberately to confuse the matter by misleading 
quotation of a section about something other than the topic (undefined 
behavior) under discussion.  You also appear to have removed the heading 
"unspecified behavior" of this section which would show that your 
quotation is irrelevant, in order to confuse readers who don't check 
quotations claiming to be from the standard to see whether they are 
genuine and relevant.

2. No section with the wording you quote appears in the standard; you 
appear to be conflating two different sections, 3.4.4#1 and 4#3.

3. 3.4.4#1 had "use of an unspecified value, or other " prepended in TC2, 
so you are *misquoting* an *obsolete* standard version.

"undefined" and "unspecified" have completely different meanings in C 
standard context.  Until you understand this and are willing to refer only 
to relevant parts of the correct standard version without silently 
concatenating different sections and removing the section headings where 
they would contradict your claims, there is no point in your posting to 
this list or anywhere else C standards are discussed, and readers must 
presume that what you post claiming to be a quotation from the standard is 
not such a quotation or is placed in misleading context until they check 
the standard themselves.

-- 
Joseph S. Myers               http://www.srcf.ucam.org/~jsm28/gcc/
    jsm@polyomino.org.uk (personal mail)
    joseph@codesourcery.com (CodeSourcery mail)
    jsm28@gcc.gnu.org (Bugzilla assignments and CCs)

Re: basic VRP min/max range overflow question

[Robert Dewar]

Joseph S. Myers wrote:

> The traditional form of undefined behavior is for demons to fly out of 
> your nose.  We just haven't yet got -fnasal-demons working reliably but it 
> would be conforming for it to be on by default.  If you are lucky, it will 
> happen anyway without that option.

A nice piece of history. During the discussions of the Algol 68 revised
standard, there was a discussion of what undefined meant. Charles Lindsay
(I think, not 100% sure it was him) said "it could mean anything,
including unimaginable chaos", Gerhardt Goos replied "but how can I
implement unimaginable chaos in my compiler".

Here is an interesting example I have used sometimes to indicate just
how this kind of information can propagate in a manner that would result
in unexpected chaos. (Ada but obvious analogies in other languages)


       -- process command to delete system disk, check password first

       loop
          read (password)
          if password = expected_password then
            delete_system_disk;
          else
            complain_about_bad_password;
            npassword_attempts := npassword_attempts + 1;
            if npassword_attempts = 4 then
               abort_execution;
            end if;
          end if;
       end loop;

Now suppose that npassword_attempt is not initialized, and we are in a
language where doing an operation on an uninitialized value is undefined,
erroneous or whatever other term is used for undefined disaster.

Now the compiler can assume that npassword_attempts is not referenced,
therefore it can assume that the if check on password is true, therefore
it can omit the password check AARGH!

This kind of backward propagation of undefinedness is indeed worrisome,
but it is quite difficult to create a formal definition of undefined
that prevents it.
> 
> http://groups.google.com/groups?hl=en&selm=10195%40ksr.com
> 

Re: basic VRP min/max range overflow question

[Kai Henningsen]

dewar@adacore.com (Robert Dewar)  wrote on 18.06.05 in <42B48D43.2070100@adacore.com>:

> Here is an interesting example I have used sometimes to indicate just
> how this kind of information can propagate in a manner that would result
> in unexpected chaos. (Ada but obvious analogies in other languages)
>
>
>        -- process command to delete system disk, check password first
>
>        loop
>           read (password)
>           if password = expected_password then
>             delete_system_disk;
>           else
>             complain_about_bad_password;
>             npassword_attempts := npassword_attempts + 1;
>             if npassword_attempts = 4 then
>                abort_execution;
>             end if;
>           end if;
>        end loop;
>
> Now suppose that npassword_attempt is not initialized, and we are in a
> language where doing an operation on an uninitialized value is undefined,
> erroneous or whatever other term is used for undefined disaster.
>
> Now the compiler can assume that npassword_attempts is not referenced,
> therefore it can assume that the if check on password is true, therefore
> it can omit the password check AARGH!
>
> This kind of backward propagation of undefinedness is indeed worrisome,
> but it is quite difficult to create a formal definition of undefined
> that prevents it.

But at least, in that case, the compiler could easily issue the  
(presumably not required by the standard) warning that the else branch is  
"unreachable code".

1/2 :-)

MfG Kai

Re: basic VRP min/max range overflow question

[Robert Dewar]

Kai Henningsen wrote:

> But at least, in that case, the compiler could easily issue the  
> (presumably not required by the standard) warning that the else branch is  
> "unreachable code".

Yes, absolutely, a compiler should generate warnings as much as possible when
it is making these kind of assujmptions. Sometimes this is difficult though,
because the unexpected actions emerge from the depths of complex optimization
algorithms that don't easily link back what they are doing to the source code.

Actually an easier warning here is that npassword_attempts is uninitialized.
That should be easy enough to generate (certainly GNAT would generate that
warning in this situation).

Working hard to generate good warnings is an important part of the compiler
writers job, even if it is quite outside the scope of the formal standard.
Being careful to look at warnings and not ignore them is an important part
of the programmers job :-)

Re: basic VRP min/max range overflow question

[Sebastian Pop]

Robert Dewar wrote:
> Yes, absolutely, a compiler should generate warnings as much as possible when
> it is making these kind of assujmptions.

Then, you will like the following kind of patches:

Index: tree-data-ref.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-data-ref.c,v
retrieving revision 2.32
diff -d -u -p -r2.32 tree-data-ref.c
--- tree-data-ref.c	8 Jun 2005 08:47:01 -0000	2.32
+++ tree-data-ref.c	20 Jun 2005 12:57:21 -0000
@@ -499,6 +499,8 @@ estimate_niter_from_size_of_data (struct
 				 fold (build2 (MINUS_EXPR, integer_type_node, 
 					       data_size, init)), step));
 
+      warning (0, "%H undefined behavior if loop runs for more than %qE iterations",
+	       find_loop_location (loop), estimation);
       record_estimate (loop, estimation, boolean_true_node, stmt);
     }
 }

This is the best the compiler can do: it has warned the user of a
possible undefined behavior in the code, and that it will use this
assumption for transforming the code.

The other opportunity raised in this thread for inferring loop bounds
from undefined behavior of overflowing signed induction variables is
still not implemented.  I will propose a patch with the corresponding
warning messages.

Sebastian

Re: basic VRP min/max range overflow question

[DJ Delorie]

> Then, you will like the following kind of patches:
> 
> +      warning (0, "%H undefined behavior if loop runs for more than %qE iterations",
> +	       find_loop_location (loop), estimation);

I think we would like them better if you could choose to silence them,
especially when people use -Werror.  Please avoid passing 0 to
warning() for new warnings; especially if there's no other way to
control them.

Re: basic VRP min/max range overflow question

[Sebastian Pop]

DJ Delorie wrote:
> 
> > Then, you will like the following kind of patches:
> > 
> > +      warning (0, "%H undefined behavior if loop runs for more than %qE iterations",
> > +	       find_loop_location (loop), estimation);
> 
> I think we would like them better if you could choose to silence them,
> especially when people use -Werror. 

How can I do this?

> Please avoid passing 0 to
> warning() for new warnings; especially if there's no other way to
> control them.

I have just mimicked one of the other uses of warning without paying
much attention to the parameters (that are by the way not documented).

/* A warning.  Use this for code which is correct according to the
   relevant language specification but is likely to be buggy anyway.  */
void
warning (int opt, const char *gmsgid, ...)

Re: basic VRP min/max range overflow question

[DJ Delorie]

> > I think we would like them better if you could choose to silence them,
> > especially when people use -Werror. 
> 
> How can I do this?

Create a -W* command line option for it.  Pass the corresponding OPT_*
to warning().  Theen the -W option controls that warning.

> I have just mimicked one of the other uses of warning without paying
> much attention to the parameters (that are by the way not documented).

Yeah, that's why I had my procmail flag these for me.  I've just been
mentioning it when I thought it made sense to.

Re: basic VRP min/max range overflow question

[Robert Dewar]

Sebastian Pop wrote:

> This is the best the compiler can do: it has warned the user of a
> possible undefined behavior in the code, and that it will use this
> assumption for transforming the code.

As with all warnings, you have to run this over a large test suite
of real applications to find out whether there are too many false
positives.

Re: basic VRP min/max range overflow question

[Sebastian Pop]

Robert Dewar wrote:
> 
> As with all warnings, you have to run this over a large test suite
> of real applications to find out whether there are too many false
> positives.

I don't really see what a false positive could be in this case.  In
the patch that I have proposed, the warning is triggered every time
the flag -Wloop-bound-estimated is used and the loop optimizer
triggers the estimation of loop bounds for a parametric loop, as in
the following:

void foo (int N)
{
  int i;
  int A[123];

  for (i = 0; i < N; i++)
    A[i] = ...
}

The warning would say something like "<file>:<line> undefined behavior
if loop runs more than 122 iterations: access over allocated data
bounds".

Sebastian

Re: basic VRP min/max range overflow question

[Robert Dewar]

Sebastian Pop wrote:

> I don't really see what a false positive could be in this case.  In
> the patch that I have proposed, the warning is triggered every time
> the flag -Wloop-bound-estimated is used and the loop optimizer
> triggers the estimation of loop bounds for a parametric loop, as in
> the following:
> 
> void foo (int N)
> {
>   int i;
>   int A[123];
> 
>   for (i = 0; i < N; i++)
>     A[i] = ...
> }
> 
> The warning would say something like "<file>:<line> undefined behavior
> if loop runs more than 122 iterations: access over allocated data
> bounds".

and that is called a false positive if in fact the loop does
not overrun. this sounds very dubious to me

Re: basic VRP min/max range overflow question

[Sebastian Pop]

Robert Dewar wrote:
> 
> and that is called a false positive if in fact the loop does
> not overrun. this sounds very dubious to me

The problem is that the compiler has no other information about the
number of iterations in the loop, otherwise it wouldn't spend cycles
on computing such estimations.  Because the compiler will use the
estimation for transforming the code, it should warn the user.

If I understand correctly, you would like a warning that says: "your
code is wrong: you access the array outside the allocated size".
Well, this is feasible, but then, the warning will be effective only
on loops that have statically determinable number of iterations.

In my opinion both these warnings are useful.

Sebastian

Re: basic VRP min/max range overflow question

[Michael Veksler]

Sebastian Pop wrote on 19/07/2005 09:49:11:

> Robert Dewar wrote:
> >
> > and that is called a false positive if in fact the loop does
> > not overrun. this sounds very dubious to me

I concur.

>
> The problem is that the compiler has no other information about the
> number of iterations in the loop, otherwise it wouldn't spend cycles
> on computing such estimations.  Because the compiler will use the
> estimation for transforming the code, it should warn the user.

But isn't it only an estimation? In other words, does it affect anything
but performance (in case of a wrong estimation)?

>
> If I understand correctly, you would like a warning that says: "your
> code is wrong: you access the array outside the allocated size".
> Well, this is feasible, but then, the warning will be effective only
> on loops that have statically determinable number of iterations.
>
> In my opinion both these warnings are useful.
>
I am not sure about it. If you have false positives that you have
no reasonable way to turn off (other than -Wno-xxxxx), then
the warning is useless. The only alternative for -Wno-xxxxx
in your example would be:

void foo (int N)
{
  int i;
  int A[123];

  if (N > 123) // Turn the warning off.
     abort();
  for (i = 0; i < N; i++)
    A[i] = ...
}

This is problematic:
1. I am not sure it will turn the warning off.
2. Even if it does, this defeats the whole idea of the original
    optimization (gcc could have put the abort - it is allowed
    to do so because N>123 triggers undefined behavior).
3. If the line with A[i]=....  contains a function call then it is
   possible that the function calls exit, abort, longjmp or throw.
   In that case, N>123 is perfectly legal (and my if..abort
   is not viable - so again there is no way to shut the warning
   off).
   I guess that VRP is not allowed to propagate N <= 123 in
   this case.


    Michael

Re: basic VRP min/max range overflow question

[Sebastian Pop]

Michael Veksler wrote:
> This is problematic:
> 1. I am not sure it will turn the warning off.

So you don't want a warning that cannot be turned off simply by
modifying the code.  Then, I withdraw the patch that I have proposed
to implement the warning.

Re: basic VRP min/max range overflow question

[Michael Veksler]

Sebastian Pop <sebastian.pop@cri.ensmp.fr> wrote on 19/07/2005 12:58:23:
| Michael Veksler wrote:
| > This is problematic:
| > 1. I am not sure it will turn the warning off.
|
| So you don't want a warning that cannot be turned off simply by
| modifying the code.

Most of gcc warnings are like that: you can avoid a warning by
writing your code in a certain way. In most of the cases the
resulting code is clearer than what it would be without
warning avoiding maneuvers.

| Then, I withdraw the patch that I have proposed
| to implement the warning.

Wait not so fast.
1. I am no authority to block other people's enhancements.
   This was not my intention.
2. Can't it be refined? Can't delay the warning to a
   place where code depends on the VRP?
   Example:

   void foo (int N)
   {
     int i;
     int A[123];

     if (N > 123)
        // Will it be eliminated by VRP ?
        printf("N is too big, hope for the best\n");
     for (i = 0; i < N; i++)
       A[i] = ...
   }

  If VRP results in printf being eliminated, only then
  should a warning be emitted.


    Michael

Re: basic VRP min/max range overflow question

[Kai Henningsen]

dewar@adacore.com (Robert Dewar)  wrote on 19.06.05 in <42B54D96.2050006@adacore.com>:

> Kai Henningsen wrote:
>
> > But at least, in that case, the compiler could easily issue the
> > (presumably not required by the standard) warning that the else branch is
> > "unreachable code".
>
> Yes, absolutely, a compiler should generate warnings as much as possible
> when it is making these kind of assujmptions. Sometimes this is difficult
> though, because the unexpected actions emerge from the depths of complex
> optimization algorithms that don't easily link back what they are doing to
> the source code.

Actually, the reason I named an unrechable code warning was on the  
presumption that the compiler would not necessarily realize the problem,  
but a part of the compilers reasoning would necessarily make that into  
unreachable code and thus could trigger the generic unreachable code  
warning completely independent of why that code is determined to be  
unreachable.

And of course, that's only applicable to that specific case.

> Actually an easier warning here is that npassword_attempts is uninitialized.
> That should be easy enough to generate (certainly GNAT would generate that
> warning in this situation).
>
> Working hard to generate good warnings is an important part of the compiler
> writers job, even if it is quite outside the scope of the formal standard.
> Being careful to look at warnings and not ignore them is an important part
> of the programmers job :-)

In this context, also see the warning controls project. I'm very, very  
happy that things are finally moving on that front.

MfG Kai

Re: basic VRP min/max range overflow question

[Robert Dewar]

Paul Schlie wrote:

> - an optimization which presumes the execution state of a program does not
> proceed past a sequence point. but in fact does, may result in erroneous
> behavior; which would be the case if NULL pointer comparisons were optimized
> away presuming an earlier pointer dereference would have prevented execution
> from proceeding past it's enclosing sequence point if in fact it does not.

This is just plain wrong I am afraid, you are making things up, the undefined
state, plus as-if semantics, allows the optimizer to assume that the value is
anything it likes and propagate this information forward. Perhaps nothing can
convince you otherwise, but I can assure you that the people writing the
standard do not have in mind the odd reading you are pushing.

Re: basic VRP min/max range overflow question

[Tristan Wibberley]

Paul Schlie wrote:

[Justification snipped]

> Therefore regardless of the result of an "undefined" result/operation at
> it's enclosing sequence point, the remaining program must continue to abide
> by the specified semantics of the language.

Tell that to Mister my_array[sizeof(my_array) / sizeof(*my_array)] = 0;

I believe this is theoretically impossible in general.

-- 
Tristan Wibberley

Opinions expressed are my own and certainly *not* those of my employer, etc.

Re: basic VRP min/max range overflow question

[Mike Stump]

General note, please, this list is for developers of gcc to develop  
gcc.  Using it as a way to teach yourself how to read the C standard,  
isn't ok, please stop.


On Saturday, June 18, 2005, at 07:15  AM, Paul Schlie wrote:
> Maybe I didn't phrase my statement well;

I think you did, you are just wrong.  Please quote the sentence that  
says the the program behaves in accordance with 5.1.2.3, if you can  
find none, then, trivially, there is no such requirement.  If you can  
find it, you can quote it.  Failure to find it, means either, you  
didn't look hard enough, or there is none.

Here, let me try again, in a slightly different way:

   --If a program contains no violations of the rules  in  this   
Interna-
     tional  Standard,  a  conforming  implementation  shall,  within  
its
     resource limits, accept and correctly execute2) that program.

   --If  a program contains a violation of a rule for which no  
diagnostic
     is required, this International Standard places  no   
requirement  on
     implementations with respect to that program.

   1.4.12  undefined behavior                            
[defns.undefined]
   behavior, such as might arise upon use of an  erroneous  program   
con-
   struct  or  of  erroneous  data,  for  which  the  Standard  
imposes no
   requirements.  Undefined behavior may also be expected when the   
stan-
   dard  omits  the  description  of any explicit definition of  
behavior.

Read it slowly, carefully, then instead of replying, go ask 100  
programmers not on this list what they think the words mean, listen  
to them.  Come back here and summarize, if the result is different  
from what we represent.

> I fully agree with the cited paragraph above which specifically  
> says a program containing unspecified behavior "shall be a   
> correct  program  and  act  in  accordance  with 5.1.2.3". Which  
> specifies program execution, in terms of an abstract machine model,  
> which correspondingly requires:

I love it, you quote 5.1.2.3, but that section has no relevance to  
the program, if you can't find something that gives it relevance.  Go  
back and try again.

> Therefore regardless of the result of an "undefined" result/ 
> operation at
> it's enclosing sequence point, the remaining program must continue  
> to abide
> by the specified semantics of the language.

Nope.  You have failed to grasp that `can do anything' actually means  
can do anything.  If the standard mean to say that all preceding  
semantics must be observable, the standard would say that, if you can  
find where it says that all observable semantics are required in all  
sequence points before the one containing the undefined behavior,  
then, maybe that standard doesn't say that.