未定義の振る舞いとフェルマーの定理

CおよびC ++標準に従って、プログラムの実行が符号付き整数変数のオーバーフロー、または他の何百もの「未定義の動作」(未定義の動作、UB)につながる場合、プログラム実行の結果は任意です。Twitterにわいせつを投稿できます。ディスクをフォーマットできます...
悲しいかな、実際には、UBの場合にプログラムに通常とは異なる何かを強制する「イースターエッグ」は、GCC 1.17以降見られていません。プログラムコードで未知の#pragmaに遭遇したときにnethackを起動しました。 通常、UBの結果はより退屈です:コンパイラは、UBの場合にこのコードが何をするかをわずかに重要にせずに、UBが発生しない場合にコードを単純に最適化します-標準ではこの場合は何でもできるからです!
標準のUBの豊富さによりコンパイラが非自明な最適化を実行する方法を説明するために、Raymond Chen 次のコード例を示します。

 int table[4]; bool exists_in_table(int v) { for (int i = 0; i <= 4; i++) { if (table[i] == v) return true; } return false; } 

ループ状態では、 <=ではなく<=を入れて、1つ間違えました。 その結果、 exists_in_table()は最初の4回の反復のいずれかでtrueを返すか、 table[4] (UB)を読み取る必要がありtable[4]この場合、 exists_in_table()trueを返すなど、何でもできtrue ! 規格に完全に準拠して、コンパイラはexists_in_table()コードを最適化して
 int table[4]; bool exists_in_table(int v) { return true; } 

このような最適化は、プログラマーを驚かせることがあります。 John Reger は、 UBが重大な結果をもたらしたいくつかの例を挙げています。

2012年、Regerは「最も奇妙なUBの結果」の競争を発表しました。 勝者の1人は、ポインターをrealloc()パラメーターとして渡した後にUBを使用するという事実を利用しました。 彼のプログラムは、同じポインターに異なる値を表示します。
 #include <stdio.h> #include <stdlib.h> int main() { int *p = (int*)malloc(sizeof(int)); int *q = (int*)realloc(p, sizeof(int)); *p = 1; *q = 2; if (p == q) printf("%d %d\n", *p, *q); } 

 $ clang -O realloc.c;  ./a.out 
 1 2


私の意見では、コンテストの他の受賞者のプログラムはより退屈で、以前に引用した例と部分的に重複しています。
しかし、レガー自身の例に匹敵するものはありません。 フェルマーの定理の編集者による「反論」です。

彼は、一部の組み込みアプリケーションでは、最適化コンパイラがプログラムからループに続くすべてのコードを削除できないように、C ++で無限ループを作成する必要があると説明しました。 最新のコンパイラーは、 while (1) { }またはfor (;;) { }ような「イディオム」を認識するのに十分スマートです。このようなループに続くコードは実行されないため、コンパイルする必要はありません。 たとえば、関数
  void foo (void) { for (;;) { } open_pod_bay_doors(); } 

-ほとんどのコンパイラは、単一の命令に「短縮」します。
  foo: L2: jmp L2 

Clangはさらに賢く、このような偽装された無限ループも認識(および削除)できます。
  unsigned int i = 0; do { i+=2; } while (0==(i&1)); 

ここで、前の例のように、コンパイラーループからの出口が不可能であることを証明できます。つまり、単一のjmp命令で置き換えることができます。

Regerが決定しました:Fermatの定理コンパイラはコンパイル時に証明できないでしょうか?

 int fermat (void) { const int MAX = 1000; int a=1,b=1,c=1; while (1) { if (((a*a*a) == ((b*b*b)+(c*c*c)))) return 1; a++; if (a>MAX) { a=1; b++; } if (b>MAX) { b=1; c++; } if (c>MAX) { c=1; } } return 0; } #include <stdio.h> int main (void) { if (fermat()) { printf ("Fermat's Last Theorem has been disproved.\n"); } else { printf ("Fermat's Last Theorem has not been disproved.\n"); } return 0; } 

 regehr @ john-home:〜$ icc fermat2.c -o fermat2
 regehr @ john-home:〜$ ./fermat2
フェルマーの最後の定理は反証されました。
 regehr @ john-home:〜$ suncc -O fermat2.c -o fermat2
 「fermat2.c」、20行目:警告:ステートメントに到達していません
 regehr @ john-home:〜$ ./fermat2
フェルマーの最後の定理は反証されました。


どうして? ループはreturn 1;終了しreturn 1; -コンパイラは、フェルマーの定理が間違っていることを証明できましたか?!

a,b,cのどの値が「見つかった」のだろうか。

Regerは、 return 1;前に「見つかった値」の出力を追加しましたreturn 1; -その後、コンパイラはインポテンツを認識し、正直に無限ループをコンパイルしました。 (もちろん、何も印刷されませんでした。)

このプログラムには算術オーバーフローが含まれていないにもかかわらず(乗数は1..1000以内で変化し、キューブの合計は2 31を超えません)、C ++標準は外部状態を変更せずに「無限アクション」を無限ループとして宣言します。したがって、C ++コンパイラは、そのようなサイクルは有限です。
コンパイラーは、 while(1)から抜ける唯一の方法はreturn 1;演算子を使用するreturn 1;あると簡単にわかりreturn 1; 、および演算子はreturn 0; fermat()の終わりにfermat()到達不能です。 したがって、この関数を最適化して
 int fermat (void) { return 1; } 


つまり、コンパイラが削除できなかったC ++で無限ループを記述する唯一の方法は、ループ内の外部状態の変更を追加することです。 これを行う最も簡単な(そして標準的な!)方法は、 volatileとして宣言された変数を変更することです。

Source: https://habr.com/ru/post/J229963/


All Articles