何故か暴走するコード

#4

返信が遅れてしまい、申し訳ありません。

>> みけ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さん、結城紬さん、ありがとうございました。

#3

とても面白い問題ですね。
みけCATさんの指摘通り、符号付き整数がオーバーフローした時の動作は未定義です。
最近のコンパイラは、未定義動作に対してとんでもない最適化をします。

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

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

#2

確かに符号付き整数のオーバーフローは未定義動作ですが…具体的にどうしてこうなるのかは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

#1

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))では再現しません。

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

		4月 2024
日	月	火	水	木	金	土
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30