ページ 11

何故か暴走するコード

Posted: 2017年7月12日(水) 03:23
by 元学生A
http://ideone.com/LUk4UV に示すコード(下に引用)で、何故、i = 50で実行がストップしないかが分かりません。

vにオーバーフローする値を足しこんでいるのは分かるのですが、
それが何故、ループ継続判定にまで影響を及ぼすのでしょうか?

コード:

#include <iostream>
using namespace std;
 
int main() {
	int v = 0;
	for(int i = 0; i < 50; i++) {
		v += 1000000000;
		std::cout << i + 1 << ", " << v << std::endl;
	}
	return 0;
}
※ かなりコンパイラ依存なようです。ideoneでは再現しましたが、wandbox(gcc HEAD 8.0.0 20170710 (experimental))では再現しません。

ご回答の程、よろしくお願いします。

Re: 何故か暴走するコード

Posted: 2017年7月12日(水) 10:46
by みけCAT
確かに符号付き整数のオーバーフローは未定義動作ですが…具体的にどうしてこうなるのかはgccのコードを読まないとわからないかもしれません。

以下、参考
Compiler Explorer

x86-64 gcc 6.3 -O2
► スポイラーを表示
確かに無限ループになっているようである。

x86-64 gcc 6.3
► スポイラーを表示
最適化をしない場合は、きちんとループ継続の判定をしている。

x86-64 clang 4.0.0 -O2
► スポイラーを表示
このclangでは、最適化を有効にしてもループの終了が判定されている。

Wandboxのgcc HEAD 8.0.0 20170711 (experimental)でも最適化を有効にすると再現しました。
https://wandbox.org/permlink/GsZUhKauJJi791YR

Re: 何故か暴走するコード

Posted: 2017年7月12日(水) 21:50
by 結城紬
とても面白い問題ですね。
みけCATさんの指摘通り、符号付き整数がオーバーフローした時の動作は未定義です。
最近のコンパイラは、未定義動作に対してとんでもない最適化をします。

i = 2 のとき、v はオーバーフローしますので、未定義動作になります。
するとコンパイラは、i = 2 になることは決して無いものとみなすことができます。
i = 2 になることが決して無いということは、i >= 50 になることも決してありません。
従って、最適化によってループ条件の i < 50 を削除することができます。その結果、無限ループになります。

未定義動作がいかにとんでもない結果を引き起こすかは、以下の記事が面白いです。
https://cpplover.blogspot.jp/2014/06/old-new-thing.html

Re: 何故か暴走するコード

Posted: 2017年7月16日(日) 23:02
by 元学生A
返信が遅れてしまい、申し訳ありません。

>> みけCATさん
ありがとうございます。
コンパイラと最適化オプションの組によって、動作が変化するということが、出力されたアセンブリによってよく分かりました。
符号付き整数のオーバーフローは動作未定義であるため、このような現象が起こるのですね。
Compiler Explorerというサイト、非常に便利ですね。これからも活用させていただきます。
オフトピック
ちなみに、int v = 0; となっている個所を unsigned int v = 0;とすると、(期待通り)ループが終了しました。
Compiler Explorerを使って、アセンブリを調べてみると、どうやらiの値ではなく、vの値でループを終了するかどうかを判定しているようです。
符号なし整数のオーバーフローは規格で定義されており、最終的なvの値を予め計算できる(かつ等値判定の方が処理が早い)ため、埋め込みを行っているのではないか、と考察しました。
>> 結城紬さん
ありがとうございます。
処理系が何を目的にこのような最適化を行っているのかがよく分かり、とてもスッキリしました。
紹介されたリンクも参考にしていろいろと考察した結果、C++のコンパイラの気持ちが多少分かるようになった気がします。
オフトピック
紹介されたリンク (https://cpplover.blogspot.jp/2014/06/old-new-thing.html) のコード:

コード:

int table[4];
bool exists_in_table(int v)
{
    for (int i = 0; i <= 4; i++) {
        if (table[i] == v) return true;
    }
    return false;
}
  • iが5の場合は、決して発生しない。なぜならば、iが5に到達するには、iはまず、4に到達しなければならない。吾輩は、すでにiが4には到達しないと看過しておるからだ。
  • 故に、すべての合法なコードパスはtrueを返すものである。
の間の説明が飛んでいるように思われたため、考察してみました。
  1. iが5には到達しない
  2. よって、最適化する場合、iに関する条件判定を消すことができる
  3. 条件判定を消した結果、for文は無限ループとなる
  4. よって、 return false; の行には到達せず、無限ループ中の return true; しか到達しえないため、関数全体を return true; と最適化する
他の例も興味深く、現在考察を進めているところです。
非常にためになっています。ありがとうございます。
以上をもって、このトピックは解決とさせていただきます。
みけCATさん、 結城紬さん、ありがとうございました。