why optimization breaks this C code?

Question

Does anyone see why -O2 breaks this code? I suspect it is a bug in gcc, as it works fine with on different platforms and with different versions of gcc. However, it is also possible that the code contains some peculiarity which I am not aware of. Could anyone enlighten me?

Here is the code, it is an implementation of a variable number of nested loops producing all possible combinations. The expected output is

100 1
010 2
001 4
110 3
101 5

and the broken version reports

100 1
010 2
001 4
100 1
010 2

The code is:

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
int main()
{
    int nmax = 5; // finish after 5 combinations
    int n = 3;    // three elements
    int *out = (int*) calloc(nmax, sizeof(int)); 
    int *cnt = (int*) calloc(n, sizeof(int)); // declaring volatile solves the problem. But why ?
    int il, nl, i = 0;
    for (nl=1; nl<=n; nl++)
    {
        for (il=0; il<nl; il++) cnt[il] = 0;
        cnt[nl-1] = -1;
        while ( cnt[0]<n-nl )
        {
            for (il=nl-1; il>=0; il--)
            {
                if ( ++cnt[il] < n-nl+il+1 ) break;
                cnt[il] = 0;
            }
            for (il=1; il<nl; il++)
            {
                if ( cnt[il] <= cnt[il-1] ) cnt[il] = cnt[il-1]+1;
            }
            for (il=0; il<nl; il++) out[i] |= 1<<cnt[il];
            if ( ++i >= nmax ) break;
        }
        if ( i >= nmax ) break;
    }
    for (i=0; i<nmax; i++)
    {
       for (il=0; il<n; il++) printf("%d", out[i]&(1<<il) ? 1 : 0);
       printf("\t%d\n", out[i]);
    }
    free(cnt);
    free(out);
    return 0;
 }

Answer 1

You should post details of exactly which gcc version you're using, the target, and the exact command line you're using. Additionally, posting the assembly generated by GCC (for example, by using the -S option) would be helpful.

I'm guessing that the compiler is incorrectly hoisting cnt[0] out of the while loop controlling expression. The following modification (which would simulate the hoist) produces your incorrect output:

// ...

for (nl=1; nl<=n; nl++)
{
    int tmp;                            // <== new line
    for (il=0; il<nl; il++) cnt[il] = 0;
    cnt[nl-1] = -1;
    tmp = cnt[0];                       // <== new line
    while ( /*cnt[0] */ tmp <n-nl )     // modified
    {
        for (il=nl-1; il>=0; il--)

// ...

Of course, this is just a guess - it would be more interesting to get the requested details so the generated code could be examined.