behavior of signed overflow is undefined in ANSI C

[Jay Carlson <nop@...>]

OK, this goes into the "I Did Not Know That" (but should have) file. I'll credit http://www.pixelbeat.org/programming/gcc/integer_overflow.html for some good pointers.

In ANSI C, behavior on signed overflow is undefined.

In C89, this is called out explicitly in A.6.2:

>  * An arithmetic operation is invalid (such as division or modulus by 0)
>    or produces a result that cannot be represented in the space
>    provided (such as overflow or underflow) ($3.3).

In C99, section 6.5 declares:

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

In fact section 3.4.3, the definition of undefined behavior itself, gives as an its example:

> EXAMPLE   An example of undefined behavior is the behavior on integer overflow.

Ian Lance Taylor posts about how some gcc optimizations depend on the fact that correct programs do not produce signed overflow.

http://www.airs.com/blog/archives/120

> gcc has taken advantage of this fact for a long time when optimizing. For example, consider this function:
> 
> int f(int x) { return 0x7ffffff0 < x && x + 32 < 0x7fffffff; }
> 
> If signed arithmetic simply wraps on overflow, then this is equivalent to0x7ffffff0 < x, since adding 32 to such a value will yield a negative number. However, even gcc 2.95.3, released in 2001, will optimize this function into code which simply returns 0. This is valid because the compiler may assume that signed overflow does not occur in a correct program, and getting a negative number from x + 32 can only happen from signed overflow.
> 
> Recently gcc has started using undefined signed overflow to implement better bounds tests. [...]

The autoconf manual describes things that usually work even though not-conformant; here's one:

http://www.gnu.org/savannah-checkouts/gnu/autoconf/manual/autoconf-2.69/html_node/Signed-Overflow-Examples.html

>      static long int randx = 1;
>      ...
>      randx = randx * 1103515245 + 12345;
>      return (randx >> 16) & 077777;

The next section gives examples of things that don't work:

http://www.gnu.org/savannah-checkouts/gnu/autoconf/manual/autoconf-2.69/html_node/Optimization-and-Wraparound.html

> Compilers sometimes generate code that is incompatible with wraparound integer arithmetic. A simple example is an algebraic simplification: a compiler might translate (i * 2000) / 1000 to i * 2 because it assumes that i * 2000 does not overflow. The translation is not equivalent to the original when overflow occurs: e.g., in the typical case of 32-bit signed two's complement wraparound int, if i has type int and value 1073742, the original expression returns −2147483 but the optimized version returns the mathematically correct value 2147484.
> 
> More subtly, loop induction optimizations often exploit the undefined behavior of signed overflow. Consider the following contrived function [...]


Given how Lua's bytecode works, it seems unlikely an optimizer would be able to mess up the implementation of the proposed integer arithmetic. So this is probably not a deadly problem.

Jay