Very odd code under certain conditions including optimizations

Question

I have this snippet of code:

#include <stdio.h>     

void optimization_headache()    
{    
    int t = 11;    
    int l[1047] = {0};    
    int u_lu[23] = {0};    

    int u = 0;    

    l[0] = 0;    
    l[1] = 0;    

    do {    
        u++;    
        //printf("Incrementing u, now u is %d\n", u);     
        u_lu[u + 1] = u - l[u + 1];    
    } while ((u < t * 2) && (l[u + 1] <= t));    

    printf("u = %d, l[u] = %d, t = %d, u_lu[u] = %d\n", u, l[u], t, u_lu[u]);    
}    

int main()    
{    
    optimization_headache();    

    return 0;    
}

Upon compiling with optimizations off ($ gcc -Wall -Wextra -O0 main.c), the code compiles, and I get the following output:

u = 22, l[u] = 0, t = 11, u_lu[u] = 21

When I compile with full optimizations ($ gcc -Wall -Wextra -O3 main.c), the program hangs, and top indicates it's using 100% of my CPU. It must be running forever in the do while loop.

I can get the code to compile with full optimizations and run correctly by changing one or all of the following:

1) If I comment out l[0] = 0; l[1] = 0;.

2) If I make u a volatile int instead.

3) If I uncomment the printf inside the do while loop.

So obviously, I don't understand what the optimizations are doing, and why it changes the behavior of my program. I could just choose one of the above solutions to get it to run, but I really really want to know what's going on here. It's so weird to me.

(The C++ tag might not be appropriate, but I see the same behavior using g++ as well)

The behavior goes away with `-fno-aggressive-loop-optimizations` which means you likely have undefined behavior see [C++ compilation bug?](http://stackoverflow.com/q/32506643/1708801) for a detailed explanation of what gcc is doing. Most likely an out of bounds access is happening. — Shafik Yaghmour, Dec 18 '15 at 19:40
Your code can write to `u_lu[23]`. (you loop while `u < 22` but `u` is incremented twice). — wimh, Dec 18 '15 at 19:40
What version of gcc and what platform are you on? Both compiled versions run just fine on my Mac. — i_am_jorf, Dec 18 '15 at 19:43
it's a damned shame that no compilers have a -fflag-undefined-behaviour option... — Richard Hodges, Dec 18 '15 at 19:44
Aside: `l[0] = 0; l[1] = 0;` is unnecessary since you already defined `int l[1047] = {0};` — Weather Vane, Dec 18 '15 at 19:45
@Wimmel OH MY GOODNESS. I spent so much time widdling this small example from a huge error correction library just to post it here, I didn't have brain cells left to look at the code well enough. It was also the fact that commenting certain things out and in, and making u volatile threw me for a loop. Post your comment as the answer, and I'll accept it. — justynnuff, Dec 18 '15 at 19:48
If minor changes affect the behaviour, you are probably indexing out of range. — Weather Vane, Dec 18 '15 at 19:48
By changing small things that didn't make sense should have been a red flag for undefined behavior in the first place :( — justynnuff, Dec 18 '15 at 19:48
@WeatherVane I know! That's why this code snippet was twisting my brain. It made no sense that by redefining the elements the code would work. But like the comments already suggested, changing stuff that doesn't make sense should have pointed to undefined behavior, not optimization weirdness. — justynnuff, Dec 18 '15 at 19:52
Behavior that changes with optimization level is a strong indication of undefined behavior. — Shafik Yaghmour, Dec 18 '15 at 19:55
@justynnuff that's why I ticked up your previous comment and the question too, you have morenuff between your ears! — Weather Vane, Dec 18 '15 at 19:56
@RichardHodges GCC and Clang do have such a flag. This particular bug will be caught by `-fsanitize=address`. For other (not memory access related) UBs there is `-fsanitize=undefined`. — Ilya Popov, Dec 19 '15 at 00:27
@RichardHodges, No, because they involve quite significant runtime overhead (like 2x memory and 3x time). — Ilya Popov, Dec 19 '15 at 13:53
@RichardHodges See more detail in this CppCon 2014 talk https://www.youtube.com/watch?v=V2_80g0eOMc — Ilya Popov, Dec 19 '15 at 13:56

score 7 · Accepted Answer · edited May 23 '17 at 11:52

As pointed out in the comments, this could happen if you invokes undefined behavior.

In your case, this is the relevant part:

int t = 11;    
int u_lu[23] = {0};    

do {    
    u++;    
    u_lu[u + 1] = u - l[u + 1];    
} while ((u < t * 2) /*...*/);

The loop runs while u is smaller then 22, so it can become 21. But inside the loop, you increment u twice and writing to u_lu[23]. This is one more then allocated.

Very odd code under certain conditions including optimizations

1 Answers1