这是一个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标准来看,do遍历所有uint32_t值的循环是有效的,因为最大无符号整数值的增量被很好地定义为零.

涉及无符号操作数的计算永远不会溢出,因为无法通过生成的无符号整数类型表示的结果将以比结果类型可以表示的最大值大1的数量为模.

Answer 1

我有理由相信这是一个铿锵的错误.我看到程序中没有未定义的行为(假设它没有超出实现的容量限制) - 除了printf我将在下面解决的调用中的一个小问题(现在已经在编辑问题时解决了) ).我可能错过了一些东西,但我不这么认为.

如果我错过了什么,我希望很快就能指出.如果这个答案在几天之后仍然没有受到影响,我会把它作为一个强有力的迹象表明它确实是一个铿锵的错误.

更新:原始海报Mark Adler报告了这一点并确认它是3.6.0之前版本中的一个错误,在更高版本中进行了更正.我将从他的回答中无耻地窃取这个错误报告的链接.

正确的输出是:

47 bits set (4294967296 loops)

解决一些已经指出的事情(或者我已经注意到自己):

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

这是一个大对象(假设为2 ²⁹个字节,或半个千兆字节CHAR_BIT==8),但它显然不超过实现的容量.如果确实如此,它将被拒绝.我不是100%确定标准需要这个,但由于程序在较低的优化级别下可以正常工作,我们可以假设对象不是太大.

vec[31415927] = 0xb9fe2f2fedf7ebbd

常数0xb9fe2f2fedf7ebbd不是问题.它的值介于2 ⁶³和2 ^64之间,所以它在...范围内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需要一个类型的参数unsigned long long; count并且loops是类型uint64_t.在这里,根据实现,我们可能有未定义的行为(在我的系统上uint64_t是一个typedef unsigned long,我得到一个警告).但它不太可能导致任何实际问题(unsigned long long并且uint64_t通常具有相同的表示,即使它们不是同一类型),并且当我添加强制转换以避免任何UB时:

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

我得到了同样的行为.以下结果适用于添加到printf调用中的强制转换的程序.

我的64位系统上使用GCC 5.2.0,我得到正确的输出,-O0,-O1,-O2,和-O3,有或无-m32.时间表明gcc不会消除任何优化级别的循环.

在同一系统上使用clang 3.4,我得到正确的输出,-O0或者输出-O1错误(0 bits set)at -O2或-O3.时序表示循环在-O2和时消除-O3.当我编译时clang -m32,所有优化级别的输出都是正确的(并且没有消除循环).

当我将声明更改loops为

volatile uint64_t loops = 0;

我在所有优化级别都得到了正确的输出(并且没有消除循环).

对程序的进一步调整(此处未显示)显示vec[31415927]实际设置为0xb9fe2f2fedf7ebbd,即使优化产生错误的位数.

Answer 2

这是3.6.0之前的一个错误.("3.6.0svn"版本在3.6.0之前.)因为它已经在五个月前的3.6.0版本中得到修复,所以我向Apple报告了这个错误 - 这仍然是他们最新的编译器版本工具.

Answer 3

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

这个答案并没有给Keith的全面和出色的答案增添太多,但为了将来的参考,我想展示一个可能的解决方法(除了volatile).

事实上,无论是制作的x,count或loops挥发性将修复它,但一些试验后,我确定这个bug似乎表现出来只在do { ... } while;循环.

如果您更改代码以使用a 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;
}