ページ 1 ／ 1
何故か暴走するコード
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
► スポイラーを表示
コード:
std::ctype<char>::do_widen(char) const:
mov eax, esi
ret
.LC0:
.string ", "
main:
push r13
push r12
xor r13d, r13d
push rbp
push rbx
xor r12d, r12d
sub rsp, 8
jmp .L6
.L12:
movsx esi, BYTE PTR [rbx+67]
.L5:
mov rdi, rbp
call std::basic_ostream<char, std::char_traits<char> >::put(char)
mov rdi, rax
call std::basic_ostream<char, std::char_traits<char> >::flush()
.L6:
add r13d, 1
mov edi, OFFSET FLAT:std::cout
add r12d, 1000000000
mov esi, r13d
call std::basic_ostream<char, std::char_traits<char> >::operator<<(int)
mov edx, 2
mov rbx, rax
mov esi, OFFSET FLAT:.LC0
mov rdi, rax
call std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
mov rdi, rbx
mov esi, r12d
call std::basic_ostream<char, std::char_traits<char> >::operator<<(int)
mov rbp, rax
mov rax, QWORD PTR [rax]
mov rax, QWORD PTR [rax-24]
mov rbx, QWORD PTR [rbp+240+rax]
test rbx, rbx
je .L11
cmp BYTE PTR [rbx+56], 0
jne .L12
mov rdi, rbx
call std::ctype<char>::_M_widen_init() const
mov rax, QWORD PTR [rbx]
mov esi, 10
mov rax, QWORD PTR [rax+48]
cmp rax, OFFSET FLAT:std::ctype<char>::do_widen(char) const
je .L5
mov rdi, rbx
call rax
movsx esi, al
jmp .L5
.L11:
call std::__throw_bad_cast()
_GLOBAL__sub_I_main:
sub rsp, 8
mov edi, OFFSET FLAT:std::__ioinit
call std::ios_base::Init::Init()
mov edx, OFFSET FLAT:__dso_handle
mov esi, OFFSET FLAT:std::__ioinit
mov edi, OFFSET FLAT:std::ios_base::Init::~Init()
add rsp, 8
jmp __cxa_atexit
確かに無限ループになっているようである。
x86-64 gcc 6.3
► スポイラーを表示
コード:
.LC0:
.string ", "
main:
push rbp
mov rbp, rsp
sub rsp, 16
mov DWORD PTR [rbp-4], 0
mov DWORD PTR [rbp-8], 0
.L3:
cmp DWORD PTR [rbp-8], 49
jg .L2
add DWORD PTR [rbp-4], 1000000000
mov eax, DWORD PTR [rbp-8]
add eax, 1
mov esi, eax
mov edi, OFFSET FLAT:std::cout
call std::basic_ostream<char, std::char_traits<char> >::operator<<(int)
mov esi, OFFSET FLAT:.LC0
mov rdi, rax
call std::basic_ostream<char, std::char_traits<char> >& std::operator<< <std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*)
mov rdx, rax
mov eax, DWORD PTR [rbp-4]
mov esi, eax
mov rdi, rdx
call std::basic_ostream<char, std::char_traits<char> >::operator<<(int)
mov esi, OFFSET FLAT:std::basic_ostream<char, std::char_traits<char> >& std::endl<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&)
mov rdi, rax
call std::basic_ostream<char, std::char_traits<char> >::operator<<(std::basic_ostream<char, std::char_traits<char> >& (*)(std::basic_ostream<char, std::char_traits<char> >&))
add DWORD PTR [rbp-8], 1
jmp .L3
.L2:
mov eax, 0
leave
ret
__static_initialization_and_destruction_0(int, int):
push rbp
mov rbp, rsp
sub rsp, 16
mov DWORD PTR [rbp-4], edi
mov DWORD PTR [rbp-8], esi
cmp DWORD PTR [rbp-4], 1
jne .L7
cmp DWORD PTR [rbp-8], 65535
jne .L7
mov edi, OFFSET FLAT:std::__ioinit
call std::ios_base::Init::Init()
mov edx, OFFSET FLAT:__dso_handle
mov esi, OFFSET FLAT:std::__ioinit
mov edi, OFFSET FLAT:std::ios_base::Init::~Init()
call __cxa_atexit
.L7:
nop
leave
ret
_GLOBAL__sub_I_main:
push rbp
mov rbp, rsp
mov esi, 65535
mov edi, 1
call __static_initialization_and_destruction_0(int, int)
pop rbp
ret
最適化をしない場合は、きちんとループ継続の判定をしている。
x86-64 clang 4.0.0 -O2
► スポイラーを表示
コード:
main: # @main
push rbp
push r15
push r14
push rbx
push rax
xor r15d, r15d
mov r14d, 1000000000
.LBB0_1: # =>This Inner Loop Header: Depth=1
inc r15d
mov edi, std::cout
mov esi, r15d
call std::basic_ostream<char, std::char_traits<char> >::operator<<(int)
mov rbx, rax
mov esi, .L.str
mov edx, 2
mov rdi, rbx
call std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
mov rdi, rbx
mov esi, r14d
call std::basic_ostream<char, std::char_traits<char> >::operator<<(int)
mov rbp, rax
mov rax, qword ptr [rbp]
mov rax, qword ptr [rax - 24]
mov rbx, qword ptr [rbp + rax + 240]
test rbx, rbx
je .LBB0_7
cmp byte ptr [rbx + 56], 0
je .LBB0_4
movzx eax, byte ptr [rbx + 67]
jmp .LBB0_5
.LBB0_4: # in Loop: Header=BB0_1 Depth=1
mov rdi, rbx
call std::ctype<char>::_M_widen_init() const
mov rax, qword ptr [rbx]
mov esi, 10
mov rdi, rbx
call qword ptr [rax + 48]
.LBB0_5: # in Loop: Header=BB0_1 Depth=1
movsx esi, al
mov rdi, rbp
call std::basic_ostream<char, std::char_traits<char> >::put(char)
mov rdi, rax
call std::basic_ostream<char, std::char_traits<char> >::flush()
add r14d, 1000000000
cmp r15d, 50
jl .LBB0_1
xor eax, eax
add rsp, 8
pop rbx
pop r14
pop r15
pop rbp
ret
.LBB0_7:
call std::__throw_bad_cast()
_GLOBAL__sub_I_example.cpp: # @_GLOBAL__sub_I_example.cpp
push rax
mov edi, std::__ioinit
call std::ios_base::Init::Init()
mov edi, std::ios_base::Init::~Init()
mov esi, std::__ioinit
mov edx, __dso_handle
pop rax
jmp __cxa_atexit # TAILCALL
.L.str:
.asciz ", "
この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を返すものである。
の間の説明が飛んでいるように思われたため、考察してみました。
- iが5には到達しない
- よって、最適化する場合、iに関する条件判定を消すことができる
- 条件判定を消した結果、for文は無限ループとなる
- よって、 return false; の行には到達せず、無限ループ中の return true; しか到達しえないため、関数全体を return true; と最適化する
他の例も興味深く、現在考察を進めているところです。
非常にためになっています。ありがとうございます。
以上をもって、このトピックは解決とさせていただきます。
みけCATさん、 結城紬さん、ありがとうございました。