这是 clang 优化器错误还是 C 语言中的未定义行为？
Is this a clang optimizer bug or an undefined behavior in C?
这段代码给出了 -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 循环是有效的，因为最大无符号整数值的增量被明确定义为导致零。
A computation involving unsigned operands can never overflow, because
a result that cannot be represented by the resulting unsigned integer
type is reduced modulo the number that is one greater than the largest
value that can be represented by the resulting type.
我有理由相信这是 clang 中的一个错误。我在程序中没有看到未定义的行为（假设它没有超过实现的容量限制）——除了我将在下面解决的 printf 调用中的一个小问题（现在已经在对问题的编辑）。可能我错过了什么，但我不这么认为。
如果我遗漏了什么，我希望很快就能指出来。如果几天后这个答案仍然没有矛盾，我就认为它确实是 clang 中的一个 bug。
更新： 原始发帖人 Mark Adler 已报告此问题并确认这是 3.6.0 之前的 clang 中的错误，已在更高版本中更正。我要不要脸偷this link to the bug report from .
正确的输出是：
47 bits set (4294967296 loops)
解决一些已经指出的问题（或者我自己注意到的）：
static uint64_t vec[1 << 26] = {0};
这是一个大对象（229 字节，或半千兆字节，假设 CHAR_BIT==8），但它显然没有超过实现的容量。如果这样做，它将被拒绝。我不是 100% 确定标准需要这个，但是由于程序在较低的优化级别下确实可以正常工作，我们可以假设对象不是太大。
vec[31415927] = 0xb9fe2f2fedf7ebbd
常量0xb9fe2f2fedf7ebbd不是问题。它的值在263和264之间，所以在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 是 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 得到正确的输出，但在 -O2 或 [= 得到错误的输出 (0 bits set) 38=]。时序表明循环在-O2和-O3处被消除。当我用 clang -m32 编译时，输出在所有优化级别都是正确的（并且没有消除循环）。
当我将 loops 的声明更改为
volatile uint64_t loops = 0;
我在所有优化级别都得到了正确的输出（并且没有消除循环）。
对程序的进一步调整（此处未显示）显示 vec[31415927] 确实设置为 0xb9fe2f2fedf7ebbd，即使优化产生了错误的位数。
它看起来确实像是 clang 中的一个错误。我可以在我的 64 位系统中重现这个 运行 clang3.4-1ubuntu3;正如另一个答案提到的那样，我总是使用 gcc 获得正确的输出（它永远不会优化循环），但是如果我们使用 -O2 和 -O3.
clang 似乎会优化循环
这个答案对 Keith 的彻底和出色的答案没有太大帮助，但为了将来参考，我想展示一个可能的解决方法（volatile 除外）。
确实，将 x、count 或 loops 中的任何一个设置为 volatile 都可以修复它，但经过一些试验后，我确定该错误似乎仅在 do { ... } while; 循环。
如果您更改代码以使用 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;
}
这是一个bug in pre-3.6.0 clang。 （“3.6.0svn”版本在 3.6.0 之前。）由于它已经在五个月前的 3.6.0 版本中得到修复，我已经向 Apple 报告了这个错误——这仍然是他们最新的编译器分发版工具。
这段代码给出了 -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 循环是有效的，因为最大无符号整数值的增量被明确定义为导致零。
A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type.
我有理由相信这是 clang 中的一个错误。我在程序中没有看到未定义的行为（假设它没有超过实现的容量限制）——除了我将在下面解决的 printf 调用中的一个小问题（现在已经在对问题的编辑）。可能我错过了什么，但我不这么认为。
如果我遗漏了什么，我希望很快就能指出来。如果几天后这个答案仍然没有矛盾，我就认为它确实是 clang 中的一个 bug。
更新： 原始发帖人 Mark Adler 已报告此问题并确认这是 3.6.0 之前的 clang 中的错误，已在更高版本中更正。我要不要脸偷this link to the bug report from
正确的输出是：
47 bits set (4294967296 loops)
解决一些已经指出的问题（或者我自己注意到的）：
static uint64_t vec[1 << 26] = {0};
这是一个大对象（229 字节，或半千兆字节，假设 CHAR_BIT==8），但它显然没有超过实现的容量。如果这样做，它将被拒绝。我不是 100% 确定标准需要这个，但是由于程序在较低的优化级别下确实可以正常工作，我们可以假设对象不是太大。
vec[31415927] = 0xb9fe2f2fedf7ebbd
常量0xb9fe2f2fedf7ebbd不是问题。它的值在263和264之间，所以在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 是 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 得到正确的输出，但在 -O2 或 [= 得到错误的输出 (0 bits set) 38=]。时序表明循环在-O2和-O3处被消除。当我用 clang -m32 编译时，输出在所有优化级别都是正确的（并且没有消除循环）。
当我将 loops 的声明更改为
volatile uint64_t loops = 0;
我在所有优化级别都得到了正确的输出（并且没有消除循环）。
对程序的进一步调整（此处未显示）显示 vec[31415927] 确实设置为 0xb9fe2f2fedf7ebbd，即使优化产生了错误的位数。
它看起来确实像是 clang 中的一个错误。我可以在我的 64 位系统中重现这个 运行 clang3.4-1ubuntu3;正如另一个答案提到的那样，我总是使用 gcc 获得正确的输出（它永远不会优化循环），但是如果我们使用 -O2 和 -O3.
这个答案对 Keith 的彻底和出色的答案没有太大帮助，但为了将来参考，我想展示一个可能的解决方法（volatile 除外）。
确实，将 x、count 或 loops 中的任何一个设置为 volatile 都可以修复它，但经过一些试验后，我确定该错误似乎仅在 do { ... } while; 循环。
如果您更改代码以使用 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;
}
这是一个bug in pre-3.6.0 clang。 （“3.6.0svn”版本在 3.6.0 之前。）由于它已经在五个月前的 3.6.0 版本中得到修复，我已经向 Apple 报告了这个错误——这仍然是他们最新的编译器分发版工具。