Where does the C standard describe overflow of signed integers?

Where does the C standard describe overflow of signed integers?

[Nicholas Nethercote]

Hi,

There was recently a very long thread about the overflow behaviour of 
signed integers in C.  Apparently this is undefined according to the C 
standard.  I searched the standard on this matter, and while I did find 
some paragraphs that described how unsigned integers must wrap around upon 
overflow, I couldn't find anything explicit about signed integers.  Can 
someone point me to the relevant part(s) of the standard?

Also, does anyone know what the required behaviour for Fortran integers is 
on overflow?

(I realise this isn't exactly on-topic for this list, but I thought it 
reasonable to ask since this topic was discussed so enthusiastically 
recently :)

Thanks very much.

Nick

RE: Where does the C standard describe overflow of signed integers?

[Dave Korn]

----Original Message----
>From: Nicholas Nethercote
>Sent: 11 July 2005 15:59

> Hi,
> 
> There was recently a very long thread about the overflow behaviour of
> signed integers in C.  Apparently this is undefined according to the C
> standard.  I searched the standard on this matter, and while I did find
> some paragraphs that described how unsigned integers must wrap around upon
> overflow, I couldn't find anything explicit about signed integers.

  Anything not defined is undefined, by definition!

>  Can someone point me to the relevant part(s) of the standard?

  :) I can only point you at the whole thing, where it doesn't define it
anywhere.

  See also 3.4.3/3, and H.2.2.

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

RE: Where does the C standard describe overflow of signed integers?

[Nicholas Nethercote]

On Mon, 11 Jul 2005, Dave Korn wrote:

>> There was recently a very long thread about the overflow behaviour of
>> signed integers in C.  Apparently this is undefined according to the C
>> standard.  I searched the standard on this matter, and while I did find
>> some paragraphs that described how unsigned integers must wrap around upon
>> overflow, I couldn't find anything explicit about signed integers.

Dave, Nathan and Paul:  thanks for the quick replies.

The difference between signed and unsigned integer overflow is a little 
unclearly expressed, I think.

3.4.3/3 says:

   "EXAMPLE  An example of undefined behavior is the behavior on integer
    overflow"

6.5/5 says:

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

These two paragraphs would seem to indicate that overflow is undefined for 
both signed and unsigned integers.

But then 6.2.5 para 9, sentence 2 says:

   "A computation involving unsigned operands can never overflow, because a
    result that cannot be represented by the resulting unsigned integer
    type is reduced modulo the number that is one greater than the largest
    value that can be represented by the resulting type."

Which requires that unsigned ints must wrap on overflow.  (Actually, I 
guess it defines "overflow" such that unsigned ints never "overflow", so 
3.4.3/3 and 6.5/5 don't apply!)

But I think the paragraphs together are good enough to communicate that: 
unsigned ints must wrap on overflow, signed ints need not.  Thanks again 
for your help.

N

RE: Where does the C standard describe overflow of signed integers?

[Dave Korn]

----Original Message----
>From: Nicholas Nethercote
>Sent: 11 July 2005 17:08

> On Mon, 11 Jul 2005, Dave Korn wrote:
> 
>>> There was recently a very long thread about the overflow behaviour of
>>> signed integers in C.  Apparently this is undefined according to the C
>>> standard.  I searched the standard on this matter, and while I did find
>>> some paragraphs that described how unsigned integers must wrap around
>>> upon overflow, I couldn't find anything explicit about signed integers.

  Mangled attribution there, I didn't say that, you did!  There's no reason
to leave in the "So-and-so wrote" line if you haven't quoted a single word
of what so-and-so actually wrote....

> The difference between signed and unsigned integer overflow is a little
> unclearly expressed, I think.
> 
> 3.4.3/3 says:
> 
>    "EXAMPLE  An example of undefined behavior is the behavior on integer
>     overflow"
> 
> 6.5/5 says:
> 
>    "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."
> 
> These two paragraphs would seem to indicate that overflow is undefined for
> both signed and unsigned integers.

  Not quite; you have to read all the implications at once.  3.4.3/3 says
that the behaviour "on integer overflow" is undefined, but because it
elsewhere says that unsigned ints don't overflow, that para only applies to
signed ints.  Likewise, because unsigned ints are defined to use modulo
arithmetic, no "exception condition" occurs, because the result _is_ defined
and the modulo rule keeps it within the "range of representable values for
its type".

> But then 6.2.5 para 9, sentence 2 says:
> 
>    "A computation involving unsigned operands can never overflow, because
>     a result that cannot be represented by the resulting unsigned integer
>     type is reduced modulo the number that is one greater than the largest
>     value that can be represented by the resulting type."
> 
> Which requires that unsigned ints must wrap on overflow.  (Actually, I
> guess it defines "overflow" such that unsigned ints never "overflow", so
> 3.4.3/3 and 6.5/5 don't apply!)
> 
> But I think the paragraphs together are good enough to communicate that:
> unsigned ints must wrap on overflow, signed ints need not.  Thanks again
> for your help.

  Ah, I see you've already worked out for yourself what I wrote above.  Yes,
the language in these standards is very hard to read, because you can't
consider any individual point by itself; they don't all explicitly itemise
the other points that might interact with or modify them, as you've seen, so
it requires a good familiarity with the standard to know if some other part
of it might make a difference to the interpretation of the bit you're
examining on any given occasion.


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

Re: Where does the C standard describe overflow of signed integers?

[Nathan Sidwell]

Nicholas Nethercote wrote:
> Hi,
> 
> There was recently a very long thread about the overflow behaviour of 
> signed integers in C.  Apparently this is undefined according to the C 
> standard.  I searched the standard on this matter, and while I did find 
> some paragraphs that described how unsigned integers must wrap around 
> upon overflow, I couldn't find anything explicit about signed integers.  
> Can someone point me to the relevant part(s) of the standard?

c99 6.5 para 5 (overflow is undefined) & 6.3.1.3 (conversions to unsigned type 
obey modulo laws)

c++ 5 para 5 (overflow is undefined, unless otherwise stated) & 3.9.1 para 4 
(unsigned types obey modulo laws)

I cannot find, in c99, a statement that all unsigned arithmetic obeys modulo 
laws -- only that integral conversions to them do.

nathan

-- 
Nathan Sidwell    ::   http://www.codesourcery.com   ::     CodeSourcery LLC
nathan@codesourcery.com    ::     http://www.planetfall.pwp.blueyonder.co.uk

RE: Where does the C standard describe overflow of signed integers?

[Dave Korn]

----Original Message----
>From: Nathan Sidwell
>Sent: 11 July 2005 16:15

> c99 6.5 para 5 (overflow is undefined) 

  Have I got an old draft or something, or is that the paragraph that begins
"If an _exceptional_ _condition_ occurs ..." ?

> I cannot find, in c99, a statement that all unsigned arithmetic obeys
> modulo laws -- only that integral conversions to them do.

  Like I say, I'm not sure exactly what draft/version/spec I have here in
front of me, except that it says "ISO/IEC 9899:1999 (E)" at the top of each
page, but I've got a para 9 in 6.2.5 that says 

" ... A computation involving unsigned operands can never overflow, because
a  result that cannot be represented by the resulting unsigned integer type
is reduced modulo the number that is one greater than the largest value that
can be
represented by the resulting type."

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

Re: Overflow in Fortran (was: Where does the C standard describe overflow of signed integers?)

[Paul Brook]

On Monday 11 July 2005 15:58, Nicholas Nethercote wrote:
> Also, does anyone know what the required behaviour for Fortran integers is
> on overflow?

Section 7.1.7 "Evaluation of operation"

"The evaluation of any numeric operation whose result is not defined by the 
arithmetic used by the processor[1] is prohibited"

Section 13.7.1 "Models for integer and real data"

The model set for integer i is defined by:
[sign + magnitude]


ie. overflow is not defined, and we can do whatever the hell we want.

Paul

[1] In this context "processor" means language processor, ie. a combination 
the compiler, OS and target hardware.

Re: Where does the C standard describe overflow of signed integers?

[Michael Meissner]

On Mon, Jul 11, 2005 at 09:58:36AM -0500, Nicholas Nethercote wrote:
> Hi,
> 
> There was recently a very long thread about the overflow behaviour of 
> signed integers in C.  Apparently this is undefined according to the C 
> standard.  I searched the standard on this matter, and while I did find 
> some paragraphs that described how unsigned integers must wrap around upon 
> overflow, I couldn't find anything explicit about signed integers.  Can 
> someone point me to the relevant part(s) of the standard?

I don't have time to dig out all of the relevant sections, but I was on the
ANSI X3J11 committee that defined the C standard from its beginning through the
release of the C90 international standard (and some of the C99 work, though I
left the committee before a lot of the changes were made).  It did come up for
discussion, but the committee did decide to leave it undefined, since there
were C compilers for some different machines that did not just silently
truncate.

From memory, there was one vendor with a machine that had signed magnitude
integers.

There was a vendor with a machine that had one's complement integers.

I suspect at least one vendor used instructions that caused an overflow trap
for signed arithmetic.

-- 
Michael Meissner
email: gnu@the-meissners.org
http://www.the-meissners.org

RE: Where does the C standard describe overflow of signed integers?

[Paul Schlie]

> " ... A computation involving unsigned operands can never overflow, because
> a  result that cannot be represented by the resulting unsigned integer type
> is reduced modulo the number that is one greater than the largest value that
> can be represented by the resulting type."

Although I don't intend to extend the debate; doesn't anyone find it curious
that given this hard requirement, combined with the fact that all current
machine architectures rely on 2's complement signed integer representation
to eliminate the otherwise necessity for distinct signed integer arithmetic
operations; that by extension unsigned and signed integer arithmetic
operations are behaviorally equivalent all current machine implementations
(as well as likely future implementations for the same reasons); therefore
seemingly irrational and counter productive to presume otherwise, regardless
of the standard's presently relatively ambiguous position on the subject for
apparently largely historical reasons.

As optimization seems to be a non-argument, as by analogy all optimizations
which are available for unsigned arithmetic are correspondingly available
for signed integer operations; as any signed value may then be thought of
as being unsigned for the purposes of computation and/or comparison. i.e.:

  signed: 0 .. INT_MAX  INT_MIN ..    -1    0 ...
unsigned: 0 ..    UINT_MAX/2    .. UINT_MAX 0 ...

Re: Where does the C standard describe overflow of signed integers?

[Robert Dewar]

Paul Schlie wrote:

> Although I don't intend to extend the debate; doesn't anyone find it curious
> that given this hard requirement, combined with the fact that all current
> machine architectures rely on 2's complement signed integer representation
> to eliminate the otherwise necessity for distinct signed integer arithmetic
> operations; that by extension unsigned and signed integer arithmetic
> operations are behaviorally equivalent all current machine implementations
> (as well as likely future implementations for the same reasons);

nonsense!  -1/1 = 0 signed, -1 unsigned
-1 < 1 signed, -1>1 unsigned

Re: Where does the C standard describe overflow of signed integers?

[Paul Schlie]

> From: Robert Dewar <dewar@adacore.com>
>> Paul Schlie wrote:
>> Although I don't intend to extend the debate; doesn't anyone find it curious
>> that given this hard requirement, combined with the fact that all current
>> machine architectures rely on 2's complement signed integer representation
>> to eliminate the otherwise necessity for distinct signed integer arithmetic
>> operations; that by extension unsigned and signed integer arithmetic
>> operations are behaviorally equivalent all current machine implementations
>> (as well as likely future implementations for the same reasons);
> 
> nonsense!  -1/1 = 0 signed, -1 unsigned

Actually as -1(signed) == UINT_MAX(unsigned) there's no problem, as
1..1/0..1 == 1..1.  Although suspect you meant something like 1/-1. However
as 2's complement division typically presumes the effective conversion of
signed values to their absolute unsigned values (which is the form in which
the division typically takes place, which is itself often further decomposed
to conditional modulo unsigned subtractions, and then sign corrected
afterward), I don't view this as a discrepancy; but do agree signed division
is typically a distinct operation, which wraps sign correction around a
fundamentally unsigned division operation; which itself tends to rely on
modulo unsigned subtraction at it's core.

> -1 < 1 signed, -1>1 unsigned

Agreed, however as above, comparison operations are essentially composed of
an unsigned modulo subtraction, who's result's high order virtual sign bit
determines the logical result of the operation as a function of the xor of
it's operand's virtual sign bits. So essentially again just an wrapper over
an unsigned modulo subtraction operation.

1..1 - 0..1 == 1..0 => true (signed), false (unsigned)

So overall, it seems pretty clear that even these two arguable exceptions
actually themselves tend to rely on modulo unsigned arithmetic at their core
in all typical implementations of these signed operations.

Re: Where does the C standard describe overflow of signed integers?

[Matthew Woodcraft]

Paul Schlie wrote:
>As optimization seems to be a non-argument, as by analogy all
>optimizations which are available for unsigned arithmetic are
>correspondingly available for signed integer operations; as any signed
>value may then be thought of as being unsigned for the purposes of
>computation and/or comparison.

What about optimising x*2/2 to x?

-M-

Re: Where does the C standard describe overflow of signed integers?

[Paul Koning]

>>>>> "Matthew" == Matthew Woodcraft <mattheww@chiark.greenend.org.uk> writes:

 Matthew> Paul Schlie wrote:
 >> As optimization seems to be a non-argument, as by analogy all
 >> optimizations which are available for unsigned arithmetic are
 >> correspondingly available for signed integer operations; as any
 >> signed value may then be thought of as being unsigned for the
 >> purposes of computation and/or comparison.

 Matthew> What about optimising x*2/2 to x?

If that doesn't overflow then it's valid, and if overflow is undefined
it's valid in that case, too.  :-)

Of course this would be an example where overflow isn't treated as 2s
complement wrap...

     paul

Re: Where does the C standard describe overflow of signed integers?

[Paul Schlie]

> Matthew Woodcraft writes:
>> Paul Schlie wrote:
>>As optimization seems to be a non-argument, as by analogy all
>>optimizations which are available for unsigned arithmetic are
>>correspondingly available for signed integer operations; as any signed
>>value may then be thought of as being unsigned for the purposes of
>>computation and/or comparison.
>
> What about optimising x*2/2 to x?

Given that "C" requires the above be evaluated as (x*2)/2, as the language
specifies that the syntax defines the precedence of the operations, and that
no optimization should alter the behavior as specified by the program; I'd
say that unless it was known that the value range of x was between 0
and INT_MAX, the optimization is simply invalid.

As programmers should know and often rely on the finite range of integers to
intentionally specify algebraically inconsistent transforms; which is why
various precision integers, and in the infinite precision libraries are
available for use when such overflow ambiguities are not acceptable or
desired; the complier should simply do what is asked, not pretend it knows
better, because it doesn't.

However it seems quite reasonable and desirable for the compiler to provide
feedback to the programmer, indicating that the expression specified may be
portably algebraically simplified to "x", if the negative value overflow
behavior was not intentionally desired; thereby enabling the programmer to
improve both the portability and performance of their specified program,
rather than assuming that a value altering optimization is desirable (which
in general it never is, and typically only leads to difficult to diagnose
problems, as the program isn't actually doing an equivalent of what was
specified).

Re: Where does the C standard describe overflow of signed integers?

[Robert Dewar]

Paul Schlie wrote:

>>What about optimising x*2/2 to x?
> 
> 
> Given that "C" requires the above be evaluated as (x*2)/2, as the language
> specifies that the syntax defines the precedence of the operations, and that
> no optimization should alter the behavior as specified by the program; I'd
> say that unless it was known that the value range of x was between 0
> and INT_MAX, the optimization is simply invalid.

the optimization is indeed valid

optimizations may most certainly alter behavior of undefined
code. think about uninitialized local variables.

Re: Where does the C standard describe overflow of signed integers?

[Paul Schlie]

> From: Robert Dewar <dewar@adacore.com>
>> Paul Schlie wrote:
>>> What about optimising x*2/2 to x?
>> 
>> Given that "C" requires the above be evaluated as (x*2)/2, as the language
>> specifies that the syntax defines the precedence of the operations, and that
>> no optimization should alter the behavior as specified by the program; I'd
>> say that unless it was known that the value range of x was between 0
>> and INT_MAX, the optimization is simply invalid.
> 
> the optimization is indeed valid
> 
> optimizations may most certainly alter behavior of undefined
> code. think about uninitialized local variables.

I don't contest that it may, I simply don't believe it should.

Re: Where does the C standard describe overflow of signed integers?

[Robert Dewar]

Paul Schlie wrote:

> I don't contest that it may, I simply don't believe it should.

you can't seriously mean that with respect to uninitialized
variables. this would mean you could not put local variables in registers.
the effect on code quality woul be awful!

Re: Where does the C standard describe overflow of signed integers?

[Paul Schlie]

> From: Robert Dewar <dewar@adacore.com>
>> Paul Schlie wrote:
> 
>> I don't contest that it may, I simply don't believe it should.
> 
> you can't seriously mean that with respect to uninitialized
> variables. this would mean you could not put local variables in
> registers. the effect on code quality woul be awful!

Why would anyone care about the performance of an access to an
un-initialized variable?  Rather than attempting to insure their
diagnosis, and hopeful subsequent removal the specified code?

Personally, see no value in producing faster garbage; although do
see substantial value in producing compiled code which is strictly
consistent with the specified program and native target behavior,
regardless of its portability.

Re: Where does the C standard describe overflow of signed integers?

[Georg Bauhaus]

Paul Schlie wrote:
>>From: Robert Dewar <dewar@adacore.com>
>>
>>>Paul Schlie wrote:
>>
>>>I don't contest that it may, I simply don't believe it should.
>>
>>you can't seriously mean that with respect to uninitialized
>>variables. this would mean you could not put local variables in
>>registers. the effect on code quality woul be awful!
> 
> 
> Why would anyone care about the performance of an access to an
> un-initialized variable? [..] although do
> see substantial value in producing compiled code which is strictly
> consistent with the specified program and native target behavior,
> regardless of its portability.

You can have both, correctness and uninitialised local
variables. For an impression of the difference in performance,
and for a way to ensure correctness, I tried this
(switch register/volatile in the declaration lines in comp
and r to see the effects).

#include <stddef.h>
#include <assert.h>


#define BUFFER_SIZE 1000  // must be > 0
#define ITERATIONS 100000  // must be > 0

static inline int comp(const short, const short, const short);

/* pre: a has elements, that is hi > 0. Frequently called */
int r(short a[], size_t hi)
{
  //register int x, y, z;
  volatile int x=1, y=2, z=3;

  assert(hi > 0);

  for (size_t c=0; c < hi + 2; ++c) {
    if (a[c]) {
    jfssoae:
      x = c + 3, y = z = a[c];
      if (comp(x, y, z)) z = x - y;
    }
  }
  return x + y + z;
}

static inline int comp(const short x, const short y, const short z)
{
  //register int result = (x + y) == (x +  z);
  volatile int result = (x + y) == (x +  z);
  return result;
}

int main()
{
  short buffer[BUFFER_SIZE];
  int result;

  assert(ITERATIONS > 0);

  for (int runs = 0; runs < ITERATIONS; ++runs) {
    result = r(buffer, BUFFER_SIZE);
  }
  return result;
}

Re: Where does the C standard describe overflow of signed integers?

[Georg Bauhaus]

Georg Bauhaus wrote:

(There are at least two bugs in this :-/ but corrections
won't change the picture. Neither will initialisation.)

> #define BUFFER_SIZE 1000  // must be > 0
> #define ITERATIONS 100000  // must be > 0

>  assert(hi > 0);
> 
>  for (size_t c=0; c < hi + 2; ++c) {
>    if (a[c]) {

RE: Where does the C standard describe overflow of signed integers?

[Dave Korn]

----Original Message----
>From: Georg Bauhaus
>Sent: 15 July 2005 14:21

> You can have both, correctness and uninitialised local
> variables. For an impression of the difference in performance,
> and for a way to ensure correctness, I tried this
> (switch register/volatile in the declaration lines in comp
> and r to see the effects).

  I didn't get that far.  Before the first call to comp the program has
already accessed uninitialised memory:

> int main()
> {
>   short buffer[BUFFER_SIZE];
>   int result;
> 
>   assert(ITERATIONS > 0);

  So far, so good.  Declare some uninitialised storage.

> 
>   for (int runs = 0; runs < ITERATIONS; ++runs) {

  First time round, runs = 0;

>     result = r(buffer, BUFFER_SIZE);

  Call function 'r'.

> /* pre: a has elements, that is hi > 0. Frequently called */
> int r(short a[], size_t hi)
> {
>   //register int x, y, z;
>   volatile int x=1, y=2, z=3;

  x=1, y=2 and =3.  hi = BUFFER_SIZE and a[] is uninitialised.

> 
>   assert(hi > 0);

  Still good...
 
>   for (size_t c=0; c < hi + 2; ++c) {
>     if (a[c]) {

  Uninitialised variable access.  Boom.  *NOT* correct.

  In what sense of the word 'correct' do you claim this example is correct?


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

Re: Where does the C standard describe overflow of signed integers?

[Georg Bauhaus]

Dave Korn wrote:

>>You can have both, correctness and uninitialised local
>>variables. For an impression of the difference in performance,
>>and for a way to ensure correctness, I tried this
>>(switch register/volatile in the declaration lines in comp
>>and r to see the effects).
>>    
>>
>
>  I didn't get that far.  Before the first call to comp the program has
>already accessed uninitialised memory:
>  
>
[...]

>>  for (size_t c=0; c < hi + 2; ++c) {
>>    if (a[c]) {
>>    
>>
>
>  Uninitialised variable access.  Boom.  *NOT* correct.
>  
>

Right, but not so much Boom because `a` is full of don't care
shorts. Rather because if x, y, and z are register variables
they might never be assigned; if a[c] happens to always yield 0,
then the function r adds uninitialised local variables in
   return x + y + z;
GCC tells us, anyway.

And then there is + 2 in the loop condition which
might move c off the end of a before a[c]. Another bug,
unrelated to uninitiliased variables.

If you remove the if (a[c]) entirely here and also the + 2
(left over when quickly scribbling a program),
then x, y, and z will be computed. I think the assert
statement has a lot more to say about correctness
than when the register variables get some (which?) initial
values that are not used ever.

>  In what sense of the word 'correct' do you claim this example is correct?
>  
>

The example was intended to demonstrate two things:

1) initialising variables doesn't necessarily make programs any
  more correct.
  Initialisation might be redundant, distracting, and inviting
  asymmetric expressions, see below.  A good initial value
  for some algorithm might depend on other values, hence it is
  known only after a conditional. Pseudo code:

  f(a, b):
     x <- some initial value
      # expr doesn't show init really depends on cond(a, b)
     ...
     if cond(a, b):
        x <- a different initial value  # asymmetry here
        compute(x, ...)
     else:
        compute(x, ...)

2) if putting local variables in registers becomes impossible
  there will be a significant cost. I wanted to get an impression
  of the cost. That's the reason for writing volatile in the
  declaration lines. Just for demo.)


-- Georg

Re: Where does the C standard describe overflow of signed integers?

[Paul Schlie]

> From: Georg Bauhaus <bauhaus@futureapps.de>
> 2) if putting local variables in registers becomes impossible
>   there will be a significant cost. I wanted to get an impression
>   of the cost. That's the reason for writing volatile in the
>   declaration lines. Just for demo.)

I believe that was just a miss-statement, as I don't believe there's any
relationship between the two.

Re: Where does the C standard describe overflow of signed integers?

[Paul Schlie]

> From: Georg Bauhaus <bauhaus@futureapps.de>
>> Paul Schlie wrote:
>>> From: Robert Dewar <dewar@adacore.com>
>>>> Paul Schlie wrote:
>>>> I don't contest that it may, I simply don't believe it should.
>>> you can't seriously mean that with respect to uninitialized
>>> variables. this would mean you could not put local variables in
>>> registers. the effect on code quality woul be awful!
>> Why would anyone care about the performance of an access to an
>> un-initialized variable? [..] although do
>> see substantial value in producing compiled code which is strictly
>> consistent with the specified program and native target behavior,
>> regardless of its portability.
> 
> You can have both, correctness and uninitialised local
> variables. For an impression of the difference in performance,
> and for a way to ensure correctness, I tried this
> (switch register/volatile in the declaration lines in comp
> and r to see the effects).

- which predominantly illustrates the effect of volatile semantics?

  int x, y, z;
  (vs.)
  int x=1, y=2, z=3;

  would illustrate the effect of potentially uninitialised local variables,
  along with the accesses specified to the uninitialised elements of buffer.

  in that circumstance, what optimizations would you advocate as beneficial?

> #include <stddef.h>
> #include <assert.h>
> 
> #define BUFFER_SIZE 1000  // must be > 0
> #define ITERATIONS 100000  // must be > 0
> 
> static inline int comp(const short, const short, const short);
> 
> /* pre: a has elements, that is hi > 0. Frequently called */
> int r(short a[], size_t hi)
> {
>   //register int x, y, z;
>   volatile int x=1, y=2, z=3;
> 
>   assert(hi > 0);
> 
>   for (size_t c=0; c < hi + 2; ++c) {
>     if (a[c]) {
>     jfssoae:
>       x = c + 3, y = z = a[c];
>       if (comp(x, y, z)) z = x - y;
>     }
>   }
>   return x + y + z;
> }
> 
> static inline int comp(const short x, const short y, const short z)
> {
>   //register int result = (x + y) == (x +  z);
>   volatile int result = (x + y) == (x +  z);
>   return result;
> }
> 
> int main()
> {
>   short buffer[BUFFER_SIZE];
>   int result;
> 
>   assert(ITERATIONS > 0);
> 
>   for (int runs = 0; runs < ITERATIONS; ++runs) {
>     result = r(buffer, BUFFER_SIZE);
>   }
>   return result;
> }
> 

Re: Where does the C standard describe overflow of signed integers?

[Georg Bauhaus]

Paul Schlie wrote:

>>From: Georg Bauhaus <bauhaus@futureapps.de>
>>    
>>
>>>Paul Schlie wrote:
>>>      
>>>
>>>>From: Robert Dewar <dewar@adacore.com>
>>>>        
>>>>
>>>> this would mean you could not put local variables in
>>>>registers. the effect on code quality woul be awful!
>>>>        
>>>>
>>>Why would anyone care about the performance of an access to an
>>>un-initialized variable? 
>>>      
>>>
>>You can have both, correctness and uninitialised local
>>variables. For an impression of the difference in performance,
>>    
>>

>- which predominantly illustrates the effect of volatile semantics?
>  
>
I was looking for a way to stop GCC from using registers,
as I wanted to see one of the above mentioned effects
on code quality. Hence volatile.


-- Georg

Re: Where does the C standard describe overflow of signed integers?

[Paul Koning]

>>>>> "Paul" == Paul Schlie <schlie@comcast.net> writes:

 >> From: Robert Dewar <dewar@adacore.com>
 >>> Paul Schlie wrote:
 >>>> What about optimising x*2/2 to x?
 >>> Given that "C" requires the above be evaluated as (x*2)/2, as the
 >>> language specifies that the syntax defines the precedence of the
 >>> operations, and that no optimization should alter the behavior as
 >>> specified by the program; I'd say that unless it was known that
 >>> the value range of x was between 0 and INT_MAX, the optimization
 >>> is simply invalid.
 >> the optimization is indeed valid
 >> 
 >> optimizations may most certainly alter behavior of undefined
 >> code. think about uninitialized local variables.

 Paul> I don't contest that it may, I simply don't believe it should.

In that case you may want to stick with -O0.  There are *lots* of
things GCC does that alter undefined cases.  How about the undefined
behavior when aliasing rules are violated?  Would you want to make
-fno-strict-aliasing be the only supported setting?

     paul

Re: Where does the C standard describe overflow of signed integers?

[Paul Schlie]

> From: Paul Koning <pkoning@equallogic.com>
>>>>>> "Paul" == Paul Schlie <schlie@comcast.net> writes:
>>> From: Robert Dewar <dewar@adacore.com>
>>>> Paul Schlie wrote:
>>>>> What about optimising x*2/2 to x?
>>>> Given that "C" requires the above be evaluated as (x*2)/2, as the
>>>> language specifies that the syntax defines the precedence of the
>>>> operations, and that no optimization should alter the behavior as
>>>> specified by the program; I'd say that unless it was known that
>>>> the value range of x was between 0 and INT_MAX, the optimization
>>>> is simply invalid.
>>> the optimization is indeed valid
>>> 
>>> optimizations may most certainly alter behavior of undefined
>>> code. think about uninitialized local variables.
> 
>  Paul> I don't contest that it may, I simply don't believe it should.
> 
> In that case you may want to stick with -O0.  There are *lots* of
> things GCC does that alter undefined cases.  How about the undefined
> behavior when aliasing rules are violated?  Would you want to make
> -fno-strict-aliasing be the only supported setting?

- Isn't the purpose of "restrict" to explicitly enable the compiler to
  more aggressively optimize references which it may be not have been
  able to identify it as being strictly safe?  (As opposed to it feeling
  compelled presume potentially disastrously otherwise, without explicit
  permission to do so?)

Re: Where does the C standard describe overflow of signed integers?

[Avi Kivity]

Paul Schlie wrote:

>>In that case you may want to stick with -O0.  There are *lots* of
>>things GCC does that alter undefined cases.  How about the undefined
>>behavior when aliasing rules are violated?  Would you want to make
>>-fno-strict-aliasing be the only supported setting?
>>    
>>
>
>- Isn't the purpose of "restrict" to explicitly enable the compiler to
>  more aggressively optimize references which it may be not have been
>  able to identify it as being strictly safe?  (As opposed to it feeling
>  compelled presume potentially disastrously otherwise, without explicit
>  permission to do so?)
>  
>
"restrict" allows the compiler to make further assumptions than 
-fstrict-aliasing. with strict aliasing, the compiler assumes that an 
int pointer and a long pointer cannot refer to the same object, whereas 
"restrict" allows you to specify that two int pointers do not refer to 
the same object.

-- 
Do not meddle in the internals of kernels, for they are subtle and quick to panic.