Where is the second overflow in this piece of code

Question

Here is the piece of code from GNU C reference manual Pg 74:

If your code uses a signed loop index, make sure that the index cannot overflow, along with all signed expressions derived from the index. Here is a contrived example of problematic code with two instances of overflow.

for( i = INT_MAX - 10 ; i <= INT_MAX; i++)
    if( i+1 < 0 ) //first overflow
    {
        report_overflow();
        break; 
    }

Because of the two overflows, a compiler might optimize away or transform the two comparisons in a way that is incompatible with the wraparound assumption.

I feel written as is only one overflow will occur. The second one from `i++` cannot occur because of the `break` statement. Agree? — Ankur Agarwal, Jul 22 '14 at 07:48
yes, but the compiler might see it as a potential overflow, that could cause problem with optimization. — sp2danny, Jul 22 '14 at 07:50
@sp2danny I see, so you mean to say that on using some compiler optimization options the loop can be turned into an infinite loop under the argument that behavior is undefined on overflow, and this will contradict with the author's intended behavior of the code. Right? — Ankur Agarwal, Jul 22 '14 at 07:56
the loop is infinite either way (sans the break). the compiler can deduct that UB will happen. this means that the code might not do what you expect. — sp2danny, Jul 22 '14 at 08:02
Once "first overflow" occurs, the behaviour of the program is undefined from that point onwards. The program can't get "more undefined" . — M.M, Jul 22 '14 at 22:20

score 4 · Accepted Answer · edited Jul 22 '14 at 21:21

4

What GNU C reference manual means is that you have two possible overflows. The first one is the i++ statement in

for( i = INT_MAX - 10 ; i <= INT_MAX; i++)

and the second one would be i+1 in

if( i+1 < 0 ) //first overflow

The example C code avoids an eternal loop with the

if( i+1 < 0 ) //first overflow
{
    report_overflow();
    break; 
}

piece of code, and to do that you're relying in signed wraparound behaviour.

However the A.3 apendix tells you that you shouldn't rely on signed wraparound behaviour because the optimizer exploits its undefined behaviour and could generate code that would behave differently from what you expect. This is the case with if( i+1 < 0 ) piece of code, which relies in that wraparound will happen when i is INT_MAX.

As a conclusion, above code could fail after being optimized by the compiler.

edited Jul 22 '14 at 21:21

Ankur Agarwal

23,692
41
137
208

answered Jul 22 '14 at 08:03

sharcashmo

795
1
7
16

2

+1 You correctly say "you shouldn't rely in wraparound behaviour", maybe it's important to state that this is the case because the variable is signed, while wraparound would be guaranteed if the variable was unsigned. – Antonio Jul 22 '14 at 08:19
@Antonio: on all known architectures wraparound will happen *regardless* of variable signedness – mvp Jul 22 '14 at 08:30
2

@mvp The point here is that the optimizer, more than the architecture, might produce `strange` behaviour when relying on wraparound while using a signed integer. It is better described in several threads, e.g. [1](http://stackoverflow.com/a/7682539/2436175) [2](http://stackoverflow.com/a/4240878/2436175) [3](http://stackoverflow.com/questions/19842215/wrap-around-explanation-for-signed-and-unsigned-variables-in-c) – Antonio Jul 22 '14 at 11:54
@mvp http://www.gnu.org/software/gnu-c-manual/gnu-c-manual.html#Integer-Overflow-Basics : "In languages like C, unsigned integer overflow reliably wraps around; e.g., UINT_MAX + 1 yields zero. This is guaranteed by the C standard and is portable in practice, unless you specify aggressive, nonstandard optimization options suitable only for special applications." – Ankur Agarwal Jul 22 '14 at 21:24

score 2 · Answer 2 · answered Jul 22 '14 at 07:41

2

Converting from comment:

i <= INT_MAX is always true, so loop can never quit. So this is a bug because i++ overflows.

Because it is always true, compiler may optimize this condition out, which is obviously not what expected.

answered Jul 22 '14 at 07:41

mvp

111,019
13
122
148

In the code written as is I do not see how the second overflow due to `i++` can affect the operation and turn this in an infinite loop. Can you please correct me? – Ankur Agarwal Jul 22 '14 at 07:47
You expect that increasing `i` will eventually break loop condition. But, when i==INT_MAX, increasing it once more makes it negative (overflows), so your expectation is never met, and loop continues forever – mvp Jul 22 '14 at 07:49
the loop condition is broken by the if clause. Isn't it? – Ankur Agarwal Jul 22 '14 at 07:50

score 2 · Answer 3 · answered Jul 22 '14 at 07:42

2

due to the break, there should be none
without the break this would be an eternal loop, and overflow on ++i
since i <= INT_MAX is true for all values of i (assuming i is an integer)

answered Jul 22 '14 at 07:42

sp2danny

7,488
3
31
53

Where is the second overflow in this piece of code

3 Answers3