这是clang优化器错误还是C中未定义的行为？

Question

此代码为-O1和-O2提供不同的结果：

/*
    Example of a clang optimization bug.
    Mark Adler, August 8, 2015.

    Using -O0 or -O1 takes a little while and gives the correct result:

        47 bits set (4294967296 loops)

    Using -O2 or -O3 optimizes out the loop, returning immediately with:

        0 bits set (4294967296 loops)

    Of course, there weren't really that many loops.  The number of loops was
    calculated, correctly, by the compiler when optimizing.  But it got the
    number of bits set wrong.

    This is with:

        Apple LLVM version 6.1.0 (clang-602.0.53) (based on LLVM 3.6.0svn)
        Target: x86_64-apple-darwin14.4.0

 */

#include <stdio.h>
#include <inttypes.h>

/* bit vector of 1<<32 bits, initialized to all zeros */
static uint64_t vec[1 << 26] = {0};

int main(void)
{
    /* set 47 of the bits. */
    vec[31415927] = UINT64_C(0xb9fe2f2fedf7ebbd);

    /* count the set bits */
    uint64_t count = 0;
    uint64_t loops = 0;
    uint32_t x = 0;
    do {
        if (vec[x >> 6] & ((uint64_t)1 << (x & 0x3f)))
            count++;
        x++;
        loops++;
    } while (x);
    printf("%" PRIu64 " bits set (%" PRIu64 " loops)\n", count, loops);
    return 0;
}

那么这是一个错误吗？或者其中是否存在某种未定义的行为，编译器有权为其提供不同的结果？

据我从C99标准中可以看出，遍历所有uint32_t值的do循环是有效的，因为最大无符号整数值的增量被很好地定义为导致零。

涉及无符号操作数的计算永远不会溢出，因为不能由结果无符号整数类型表示的结果将被减少为比结果类型可以表示的最大值大一的数的模。

Answer 1

它看起来确实像clang中的一个错误。我可以在运行clang3.4-1ubuntu3的64位系统中重现这一点；正如另一个答案所提到的，我总是使用gcc获得正确的输出（它永远不会优化掉循环），但是如果我们使用-O2和-O3，clang似乎会优化掉循环。

这个答案并没有给Keith彻底而出色的答案增添太多，但为了将来的参考，我想展示一个可能的解决方法（除了volatile）。

的确，让x、count或loops中的任何一个变得易变都可以解决这个问题，但是经过一些实验，我确定这个错误似乎只在do{…}上表现出来而 循环。

如果您将代码更改为使用while或for循环（并进行适当的更改以保持程序的行为），clang将始终生成正确的输出，并且循环不会被优化（但使用-O3，它仍然运行得更快）。

下面是一个例子：

#include <stdio.h>
#include <inttypes.h>

/* bit vector of 1<<32 bits, initialized to all zeros */
static uint64_t vec[1 << 26] = {0};

int main(void)
{
    /* set 47 of the bits. */
    vec[31415927] = UINT64_C(0xb9fe2f2fedf7ebbd);

    /* count the set bits */
    uint64_t count = vec[0] & (uint64_t)1;
    uint64_t loops = 1;
    uint32_t x = 1;

    while (x) {
        if (vec[x >> 6] & ((uint64_t)1 << (x & 0x3f)))
            count++;
        x++;
        loops++;
    }

    printf("%" PRIu64 " bits set (%" PRIu64 " loops)\n", count, loops);
    return 0;
}

Answer 2

这是3.6.0之前版本中的一个bug。（3.6.0svn版本先于3.6.0。）由于在5个月前3.6.0版本中已经修复了该漏洞，我已经向苹果公司报告了该漏洞——这仍然是他们最新发布的编译器工具。

Answer 3

我有理由相信这是一个叮当作响的错误。我在程序中看不到任何未定义的行为（假设它不超过实现的容量限制）——除了printf调用中的一个小问题之外，我将在下面讨论这个问题（这已经在问题的编辑中得到了解决）。我可能错过了什么，但我不这么认为。

如果我遗漏了什么，我希望很快就会被指出。如果几天后这个答案仍然没有争议，我会认为这是一个强有力的迹象，表明它确实是一个叮当作响的错误。

更新：原始发帖人Mark Adler已经报告了这一点，并确认这是3.6.0之前的clang中的一个错误，在以后的版本中得到了纠正。我会无耻地从他的回答中窃取这个错误报告的链接。

正确的输出是：

47 bits set (4294967296 loops)

要解决已经指出的一些事情（或我自己已经注意到的）：

static uint64_t vec[1 << 26] = {0};

这是一个大对象（2²⁹bytes，或半GB，假设CHAR_BIT==8），但它显然没有超过实现的容量。如果它这样做了，它会被拒绝。我不是100%确定标准要求这样做，但由于程序确实在较低的优化级别下正常工作，我们可以假设对象不是太大。

vec[31415927] = 0xb9fe2f2fedf7ebbd

常量0xb9fe2f2fedf7ebbd不是问题。它的值介于2⁶³和2⁶⁴之间，因此它在uint64_t的范围内。十六进制整数常量的类型足够宽，可以容纳它的值（除非它超过ULLONG_MAX，但这里不是这种情况）。

if (vec[x >> 6] & ((uint64_t)1 << (x & 0x3f)))

我曾一度认为左移位可能有问题，但事实并非如此。左操作数的类型为uint64\t，右操作数的范围为0<代码>63。64位的左移位会有未定义的行为，但这里的情况并非如此。

printf("%llu bits set (%llu loops)\n", count, loops);

以下是问题的最新进展。我尝试了代码的更新版本，得到了相同的结果。

%llu需要类型为的参数 无符号long-long； 计数和 循环属于 uint64\u t。在这里，根据实现的不同，我们可能有未定义的行为（在我的系统上） uint64_t是 unsigned long，我得到一个警告）。但这不太可能造成任何实际问题( 无符号长和 uint64_t通常具有相同的表示，即使它们不是相同的类型），当我添加强制转换以避免任何UB时：

printf("%llu bits set (%llu loops)\n",
       (unsigned long long)count,
       (unsigned long long)loops);

在我的64位系统上使用gcc 5.2.0，我通过 -O0、 -O1、 -O2和 -O3获得正确的输出，无论是否 -m32。定时表明gcc不会在任何优化级别消除循环。

在同一个系统上使用clang 3.4，我用 -O0或 -O1得到正确的输出，但在 -O2或 -O3处得到不正确的输出（ 0位设置）。定时表明循环在 -O2和 -O3被消除。当我使用 clang-m32编译时，输出在所有优化级别都是正确的（并且循环没有被消除）。

当我将 循环的声明更改为

 
  volatile uint64_t loops = 0;

 

我在所有优化级别都获得正确的输出（并且循环没有被消除）。

对程序的进一步调整（此处未显示）显示，vec[31415927]确实设置为0xb9fe2fedf7ebbd，即使优化产生了错误的位计数。