☰

これは clang オプティマイザのバグですか、それとも C の未定義の動作ですか? 質問する

tag-icon • tag-icon c optimization clang c99
これは clang オプティマイザのバグですか、それとも 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 標準から判断する限り、最大の符号なし整数値の増分はゼロになるように明確に定義されているため、doすべての値を処理するループは有効です。uint32_t

符号なしオペランドを含む計算では、結果の符号なし整数型で表すことができない結果は、結果の型で表すことができる最大値より 1 大きい数値を法として減算されるため、オーバーフローが発生することはありません。

ベストアンサー1

これは clang のバグだと確信しています。プログラムに未定義の動作は見当たりません (実装の容量制限を超えていないと仮定した場合)。ただし、printf以下で説明する呼び出しの小さな問題 (質問の編集で対処済み) は除きます。何か見落としている可能性もありますが、そうではないと思います。

何か見落としがあった場合は、すぐに指摘されると思います。この回答が数日後に矛盾しない場合は、それが確かに clang のバグであるという強い兆候であると見なします。

アップデート ：元の投稿者であるマーク・アドラーはこれを報告し、これは3.6.0以前のclangのバグであり、それ以降のバージョンで修正されたことを確認しました。私は恥ずかしげもなく盗用します。バグレポートへのリンクから彼の答え。

正しい出力は次のとおりです。

47 bits set (4294967296 loops)

指摘されたこと（または私自身が気づいたこと）のいくつかについて説明します。

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

これは大きなオブジェクト (2 29バイト、つまり と仮定すると 0.5 ギガバイトCHAR_BIT==8) ですが、実装の容量を超えていないようです。超えていた場合は拒否されます。標準でこれが要求されているかどうかは 100% 確信はありませんが、プログラムは低い最適化レベルでは正しく動作するため、オブジェクトは大きすぎないと想定できます。

vec[31415927] = 0xb9fe2f2fedf7ebbd

定数は0xb9fe2f2fedf7ebbd問題ではありません。その値は 2 63から 2 64の間なので、 の範囲内ですuint64_t。16 進整数定数の型は、その値を保持するのに十分な広さです ( を超えない限りですULLONG_MAXが、この場合はそうではありません)。

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

左シフトが問題になるかもしれないと一瞬思いましたが、そうではありません。左オペランドは 型でuint64_t、右オペランドは の範囲にあります0。6463ビットの左シフトでは未定義の動作が発生しますが、ここではそうではありません。

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、gcc がどの最適化レベルでもループを削除しないことを示しています。-O2-O3-m32

同じシステムで clang 3.4 を使用すると、または では正しい出力が得られます-O0が、または-O1では間違った出力 ( 0 bits set)が得られます。タイミングは、ループが および で削除されることを示しています。を使用してコンパイルすると、すべての最適化レベルで出力は正しくなります (ループは削除されません)。-O2-O3-O2-O3clang -m32

の宣言をloops次のように変更すると

volatile uint64_t loops = 0;

すべての最適化レベルで正しい出力が得られます (ループは削除されません)。

プログラムをさらに調整すると（ここでは示していません）、最適化によって間違ったビット数が生成された場合でも、vec[31415927]実際には が に設定されることがわかります。0xb9fe2f2fedf7ebbd

おすすめ記事