Signed Overflow

The C and C++ language standards say that overflow of a signed value is undefined behaviour. In the C99 standard this is in section 6.5. In the C++98 standard it is in section 5 [expr], paragraph 5. This means that a correct C/C++ program must never generate signed overflow when computing an expression. It also means that a compiler may assume that a program will never generated signed overflow.

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 to 0x7ffffff0 < 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. In particular, consider code like this:

int f()
{
int i;
int j = 0;
for (i = 1; i > 0; i += i)
++j;
return j;
}

This code is assuming that if it keeps doubling a positive number, it will eventually get a negative number. That is, it expects signed overflow to behave in a certain way. Current mainline gcc will see that the signed overflow can not occur in a correct program, and will compile this code into an infinite loop.

Some gcc users were surprised by this optimization, and there was an outcry around the beginning of 2007. For a while there was a suggestion that gcc compilations should always use the -fwrapv option. -fwrapv tells the compiler to treat signed overflow as wrapping. That is how Java defines signed overflow. The option was introduced in 2003 for gcc 3.3.

The disadvantage of -fwrapv is that it inhibits optimizations. Most programs do not produce signed overflow, and, as we have seen, no correct programs do. The compiler can generate better code when it can assume that signed overflow can not occur. This particularly arises in loops. When a loop uses a signed integer index, the compiler can do much better when it doesn’t have to consider the possibility that the index will overflow.

Consider this trivial example:

int f(int i) { int j, k = 0; for (j = i; j < i + 10; ++j) ++k; return k; }

What does this function return? When the compiler can assume that signed overflow is undefined, this function is compiled into code which simply returns 10. With the -fwrapv option, the code is not so simple,, since i might happen to have a value like 0x7ffffff8 which will overflow during the loop. While this is a trivial example, it is clear that loops like this occur in real code all the time.

However, gcc does need to respond to the concerns of the user community. I introduced two new options in gcc 4.2. The first is -fno-strict-overflow. This tells the compiler that it may not assume that signed overflow is undefined. The second is -Wstrict-overflow. This tells the compiler to warn about cases where it is using the fact that signed overflow is undefined to implement an optimization. With these options it is possible to detect cases where signed overflow occurs in a program, and it is possible to disable optimizations which rely on signed overflow until the program is fixed. The -Wstrict-overflow warning even found one minor case where gcc itself relied on wrapping signed overflow, in the handling of division by the constant 0x80000000.

This naturally leads to the question: what is the difference between -fwrapv and -fno-strict-overflow? There is a clear difference on a processor which does not use ordinary twos-complement arithmetic: -fwrapv requires twos-complement overflow, and -fno-strict-overflow does not. However, no such processor is in common use today. In practice, I think that the code generated by the two options will always behave the same. However, they affect the optimizers differently. For example, this code

int f(int x) { return (x + 0x7fffffff) * 2; }

is compiled differently with -fwrapv and -fno-strict-overflow. The difference occurs because -fwrapv precisely specifies how the overflow should behave. -fno-strict-overflow merely says that the compiler should not optimize away the overflow. With the current compiler, with -fwrapv (and -O2 -fomit-frame-pointer), I see this:

movl $1, %eax
subl 4(%esp), %eax
addl %eax, %eax
negl %eax
ret

With -fno-strict-overflow I see this:

movl 4(%esp), %eax
leal -2(%eax,%eax), %eax
ret

Same result, different algorithm.


Posted

in

by

Tags:

Comments

15 responses to “Signed Overflow”

  1. ncm Avatar

    I see that -Wstrict-overflow is accepted by Debian’s gcc-4.2.3. However, it issues no warnings for the code examples presented.

    Is it included in -W or -Wall? (Debian has not packaged gcc-4.2 docs yet.)

  2. Ian Lance Taylor Avatar

    -Wstrict-overflow should issue a warning if you compile with -O2. -Wstrict-overflow warns about cases where an optimization relies on undefined overflow; it doesn’t have any way to detect possible overflow except when an optimization is applied. In some cases you will need to use -Wstrict-overflow=5.

    -Wall includes -Wstrict-overflow=1. Specifying -Wstrict-overflow with no number is equivalent to -Wstrict-overflow=2.

    The docs are available at http://gcc.gnu.org/onlinedocs/ .

  3. ncm Avatar

    I’m running

    $ gcc –version

    gcc (GCC) 4.2.3 20080102 (prerelease) (Debian 4.2.2-5)

    and putting all your code examples into t.c and compiling with

    $ gcc -O3 -Wstrict-overflow=5 -fstrict-overflow -Wall -W -c t.c

    I get no warnings at all. Should I be surprised at this?

  4. Ian Lance Taylor Avatar

    I think the full effects only come in on gcc mainline. At least, gcc 4.2 does not eliminate the loop, but gcc 4.3 will. All my examples were run with gcc mainline.

  5. ncm Avatar

    I see what happened:

    $ gcc -O3 -Wstrict-overflow=5 -Wall -c t.c

    is not the same as

    $ gcc -O3 -Wall -Wstrict-overflow=5 -c t.c

    Evidently the -Wall in the first example bumps the warning level back down to 1. I see that gcc-4.2 warns only about the first example, I suppose because it doesn’t perform that optimization on the next two. I can’t seem to get a warning about the last example from gcc-4.3. Shouldn’t I? It looks like bad code.

  6. Ian Lance Taylor Avatar

    There is no warning about the last example from gcc mainline because gcc doesn’t actually optimize it differently based on undefined signed overflow. It just goes ahead and generated the overflow code. I wasn’t clear: I didn’t intend that to be an example of using overflow to optimize, I intended to show a case where -fwrapv differed from -fno-strict-overflow.

  7. […] Ian Lance Taylor’s blog has an interesting post on signed overflow behavior in C. According to the C standard, integer overflow results in undefined behavior, and modern versions of GCC take advantage of this to generate more efficient code. This topic was raised on -hackers by Tom a few years ago — at the time, only the -fwrapv flag was implemented by GCC. Now that GCC 4.2 provides -Wstrict-overflow, this might be worth investigating further. […]

  8. egnor Avatar
    egnor

    At this point, several years later, would you say that -fno-strict-overflow is preferred to -fwrapv? The consensus on the Interwebs seems to prefer -fno-strict-overflow, because (1) it’s reported to generate better code (most of this probably because of your one anecdote above), (2) it avoids bugs in older gcc -fwrapv implementations.

    (I know, you would probably prefer people write code that doesn’t depend on overflow semantics at all, but that can be challenging in low level applications and legacy codebases.)

  9. […] Turns out this is a feature. For optimization purposes, by default GCC assumes there will be no overflow with integer arithmetic (see this). […]

  10. […] undefined because they use this undefinedness to help with optimization. See for instance this blog post by Ian Lance Taylor or this complaint by Agner Fog, and the answers to his bug […]

  11. […] on x86 CPUs, integers usually wrap the way you expect. This is one of those exceptions. The compiler assumes you won’t cause undefined behavior, and optimizes away the loop test. If […]

  12. […] Ian Lance Taylor ? ?? ?? ???? Agner […]

  13. […] ??????C90????????(undefined behavior)????????????????????????????K&R C???C90????????????????C90?????????????(implementation-defined behavior)?????????????????????????????????????????????????????????????????????C???????????????????????????????????????????????? […]

  14. […] ??????Signed Overflow?? […]

Leave a Reply