☰

'gcc -O2' で無限ループに最適化される関数 質問する

tag-icon • tag-icon c gcc optimization undefined-behavior
'gcc -O2' で無限ループに最適化される関数 質問する

コンテクスト
友人の一人から次のようなパズルを尋ねられました。

void fn(void)
{
  /* write something after this comment so that the program output is 10 */
  /* write something before this comment */
}

int main()
{
  int i = 5;
  fn();
  printf("%d\n", i);
  return 0;
}

解決策は複数あることはわかっています。その中にはマクロを使用するものや、実装について何かを前提として C に違反するものなどがあります。

私が興味を持った特定の解決策は、スタックについて特定の仮定を立てて、次のコードを書くことです: (これは未定義の動作だと理解していますが、多くの実装では期待どおりに動作するかもしれません)

void fn(void)
{
  /* write something after this comment so that the program output is 10 */
  int a[1] = {0};
  int j = 0;
  while(a[j] != 5) ++j;  /* Search stack until you find 5 */
  a[j] = 10;             /* Overwrite it with 10 */
  /* write something before this comment */
}

問題
このプログラムはMSVCとgccでは最適化なしでも問題なく動作しました。しかし、gcc -O2フラグを付けてコンパイルしたり、イデオネ関数内で無限ループが発生しますfn。

私の観察
gcc -Svsでファイルをコンパイルして比較すると、関数内で無限ループが続いていることがgcc -S -O2はっきりとわかります。gccfn

質問
コードが未定義の動作を呼び出すため、バグとは言えないことは理解しています。しかし、なぜ、そしてどのようにしてコンパイラは動作を分析し、無限ループを残すのでしょうかO2?

多くの人が、変数の一部を volatile に変更した場合の動作を知りたいとコメントしました。予想どおりの結果は次のとおりです。

  • iまたはjを に変更した場合volatile、プログラムの動作は同じままです。
  • 配列aを作成するとvolatile、プログラムは無限ループに陥りません。
  • さらに次のパッチを適用すると
-  int a[1] = {0};
+  int aa[1] = {0};
+  int *a = aa;

プログラムの動作は同じままです（無限ループ）

でコードをコンパイルするとgcc -O2 -fdump-tree-optimized、次の中間ファイルが生成されます。

;; Function fn (fn) (executed once)

Removing basic block 3
fn ()
{
<bb 2>:

<bb 3>:
  goto <bb 3>;

}



;; Function main (main) (executed once)

main ()
{
<bb 2>:
  fn ();

}
Invalid sum of incoming frequencies 0, should be 10000

これは、以下の回答の後に行われた主張を検証します。

ベストアンサー1

これは未定義の動作なので、コンパイラは実際には何でもできます。同様の例を次に示します。GCC 4.8 以前が壊れた SPEC 2006 ベンチマークを破るは、gcc未定義の動作を持つループを受け取り、次のように最適化します。

L2:
    jmp .L2

記事にはこう書かれている（強調地雷):

もちろんこれは無限ループです。SA​​TD()は無条件に未定義の動作を実行するため（タイプ3関数です）、いかなる翻訳（または翻訳なし）も、正しいCコンパイラにとっては完全に許容可能な動作である。未定義の動作は、ループを終了する直前にd[16]にアクセスすることです。C99では配列の末尾から1つ後の要素へのポインタを作成することは合法ですが、そのポインタは逆参照してはいけません。同様に、配列の末尾の 1 つの要素を超える配列セルにはアクセスしないでください。

あなたのプログラムを調べるとゴッドボルト私たちは見る：

fn:
.L2:
    jmp .L2

オプティマイザーが使用するロジックはおそらく次のようになります。

  • のすべての要素はaゼロに初期化されます
  • aループの前またはループ内で変更されることはありません
  • 常に真ですa[j] != 5-> 無限ループ
  • 無限であるため、 はa[j] = 10;到達不可能であり、 は最適化によって除去できます。またa、 とjも、ループ条件を決定するために必要なくなったため、除去できます。

これは、次のような記事の場合と似ています。

int d[16];

次のループを分析します。

for (dd=d[k=0]; k<16; dd=d[++k])

このような：

d[++k] を見ると、k の増分値が配列境界内にあると想定することが許可されます。そうでない場合、未定義の動作が発生するためです。ここのコードでは、GCC は k が 0..15 の範囲内にあると推測できます。少し後、GCC が k<16 を見ると、GCC は「ああ、この式は常に true なので、無限ループが発生します」と自分自身に判断します。

おそらく興味深い二次的な点は、無限ループが観測可能な動作と見なされるかどうかである（仮定ルールに関して）かどうかは、無限ループが最適化によって除去できるかどうかに影響します。C コンパイラがフェルマーの最終定理を反証11 世紀以前には少なくともいくらかの解釈の余地があった。

多くの知識のある人々 (私を含む) は、これをプログラムの終了動作を変更してはならないと言っていると解釈します。明らかに、一部のコンパイラ作成者はこれに同意せず、あるいはそれが重要だとは考えていません。分別のある人々が解釈に同意しないという事実は、C 標準に欠陥があることを示しているように思われます。

C11セクションに説明を追加6.8.5 反復文詳細については、この答え。

おすすめ記事