为什么优化会破坏这段 C 代码？

Question

有人知道为什么-O2会破坏这段代码吗？我怀疑这是gcc的一个bug，因为它可以在不同平台和不同版本的gcc上正常工作。然而，也有可能是代码包含一些我不知道的特殊情况。请有经验的人指点一下？

这里是代码，它是一个可变数量的嵌套循环的实现，产生所有可能的组合。期望的输出是：

100 1
010 2
001 4
110 3
101 5

以及损坏版本的报告

100 1
010 2
001 4
100 1
010 2

代码如下：

#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;
 }

- YSN

---

你使用的是哪个版本的gcc？在我的x86上，使用4.7.2和-O2选项可以正常工作。 - Yefim Dinitz

可能你的代码存在一些未定义行为。当我遇到这样的问题时，最后想到的是编译器错误。 - Kiril Kirov

啊啊啊！为什么这些 i，l，1 看起来这么相似！！我读这段代码片段时头都晕了 :) :) - TheCodeArtist

@KirilKirov 这是程序的验证：http://pastebin.com/XNdZLEYV。在这种情况下，这很容易，因为程序是确定性的且没有输入。如果您使用的是最近的Debian或Ubuntu，则可以通过“apt-get install frama-c”获得静态分析器。 - Pascal Cuoq

@MattMcNabb “软件预测困难”（我更喜欢将“不可决定性”保留给图灵机。认为所有C程序都是有限自动机太容易了）并不妨碍静态分析器的“准确性”（从未未能警告未定义行为）：一个简单的解决方法是在难以得出未定义行为不存在的结论时发出警告。具备准确性和可用性精度（没有太多误报）是根本困难的。 - Pascal Cuoq

Answer 1

你应该发布关于你正在使用哪个gcc版本，目标是什么以及你正在使用的确切命令行的详细信息。此外，发布GCC生成的汇编（例如，使用-S选项）将有所帮助。

我猜测编译器错误地提升了cnt[0]，使其超出了控制表达式的while循环范围。以下修改（模拟提升）会产生不正确的输出：

// ...

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

// ...

当然，这仅仅是一个猜测 - 获取请求的细节并检查生成的代码会更有趣。

- Michael Burr