GCCのバグ？未定義動作？g++とclang++で違う結果になるコード
こないだAtCoderの過去問を解いてて
ローカルでは正解が出ているのにサーバ上でREが出まくってはまったのでメモ。
再現できる形で変形＆単純化を繰り返した結果がこんな感じ
#include <vector>
#include <cstdio>
std::vector<int> a, b;
int f() {
a.push_back(-1);
b.push_back(-1);
return (int)a.size();
}
int main() {
int first = f();
printf("a[0]=%d, b[0]=%d\n", a[0], b[0]);
a[0] = f();
printf("a[0]=%d, b[0]=%d\n", a[0], b[0]);
return 0;
}・グローバルに vector<int> a, b がある。それぞれの中身は最初は空（だと思う）。
・まず f() が呼ばれる。a, b は末尾に -1 を挿入され、それぞれ長さ1になる。int数値 1 が返され、first に代入される。（このコード片ではその後 first は使われないので最適化で代入されなくなっても構わない）
・この時点で a[0], b[0] はどちらも -1 のはず
・もう一度 f() が呼ばれる。a, bは末尾に -1 を代入され、それぞれ長さ2になる。int数値 2 が返され、a[0] に代入される。
・この時点で a[0], b[0] は 2, -1 のはず。
・おしまい
というわけで、想定される出力は
a[0]=-1, b[0]=-1 a[0]=2, b[0]=-1
だし clang++ ではそうなるのだけれど、これをGCC (G++) でコンパイルして実行すると
a[0]=-1, b[0]=-1 a[0]=-1, b[0]=2
になる。-O0, -O1, -O2, -O3 試してみたけど変化なし。-std=c++11とか付けても変化なし。
GCCのバージョンはローカル（macOS Sierra）では 4.8.5 と 7.2.0 を試したが同じ。（さくらVPSに置いてるUbuntu 14.04 LTSの4.8.4でも同様の結果だった）
この a[0] = f() を、int tmp = f(); a[0] = f() とすると問題は起こらなくなる。
グローバル変数じゃなければいいのか？と思って
#include <vector>
#include <cstdio>
int f(std::vector<int>& a, std::vector<int>& b) {
a.push_back(-1);
b.push_back(-1);
return (int)a.size();
}
int main() {
std::vector<int> a, b;
int first = f(a, b);
printf("a[0]=%d, b[0]=%d\n", a[0], b[0]);
a[0] = f(a, b);
printf("a[0]=%d, b[0]=%d\n", a[0], b[0]);
return 0;
}こんなのも試してみたけど結果は同じだった。
(int)a.size() の代わりに何らかの定数（42なり666なり114514なり）を返すようにしてもa[0]側ではなくb[0]側に収まってしまう現象に変化はなかった。
アセンブラ出力 (-S) を眺めてみたのだけれど、_main の箇所を抜粋するとこんな感じ：
（-O2 オプション有。コメントはnaoya_t手書き）
LFE831:
.cstring
lC0:
.ascii "a[0]=%d, b[0]=%d\12\0"
.section __TEXT,__text_startup,regular,pure_instructions
.align 4
.globl _main
_main:
LFB832:
pushq %rbx
LCFI19:
call __Z1fv ; eax = f(); first がその後使われないのがバレてるので -O2 ではeaxの値は捨てられる
movq _b(%rip), %rax ; rax = b.begin()
leaq lC0(%rip), %rdi ; rdi = "a[0]=%d, b[0]=%d\n"
movl (%rax), %edx ; edx = *b.begin()
movq _a(%rip), %rax ; rax = a.begin()
movl (%rax), %esi ; esi = *a.begin()
xorl %eax, %eax ; eax = 0
call _printf ; printf()
movq _a(%rip), %rbx ; rbx = a.begin()
call __Z1fv ; eax = f()
leaq lC0(%rip), %rdi ; rdi = "a[0]=%d, b[0]=%d\n"
movl %eax, (%rbx) ; *a.begin() = eax
movq _b(%rip), %rax ; rax = b.begin()
movl (%rax), %edx ; edx = *b.begin()
movq _a(%rip), %rax ; rax = a.begin()
movl (%rax), %esi ; esi = *a.begin()
xorl %eax, %eax ; eax = 0
call _printf ; printf()
xorl %eax, %eax ; eax = 0（これが main() の返り値になる）
popq %rbx
LCFI20:
ret２回目の f() の結果の代入先のアドレス（a）は f() 呼び出し前に組み立てられていて rbx に保持されていて、
これが f() を呼び出している間に改変され b の方に行ってしまっているようだ。
（それなら tmp に一時保存してから a[0] に代入した場合に問題が起こらないのも納得がいく。）
例えば２回目の call __Z1fv をコメントアウトして代わりに movl $777, %eax などとすると
a[0]=-1, b[0]=-1 a[0]=777, b[0]=-1
のように（想定された）結果になる。
// ちなみに clang++ が吐くコードでは、f() の内容が main() 内にインライン展開されていた。
とりあえず、GCC Bugzilla に報告を出してみようかなと。
追記：
いわゆる i=i++; と同じで未定義動作じゃないでしょうか
— kinaba (@kinaba) 2017年10月21日
f() 内の push_back で a[0] の参照が無効化されるから未定義動作だねぇ
— 残念なC++使い、銀天すばる (@SubaruG) 2017年10月21日
なるほど。未定義動作。
（だとしたらBugzilla報告はしなくても良いかな）
C++17で直るというか直感通りになるよなぁとおもって GCC 7.2で確認しみてたら-std=c++14と-std=c++1zでちゃんと(？)結果が違うという https://t.co/rMWkfD6f2b https://t.co/hukPismU4W
— yoh (@yohhoy) 2017年10月21日
折角GCC7でもやったのに c++1z は試してなかった…本当だc++1zだと意図した結果になりました
C++17なら https://t.co/qUcTPqf7Jo 確か期待する結果が保証されるケースだったと思います(要確認)
— kinaba (@kinaba) 2017年10月21日
評価順。
今回見たGCCのコンパイル結果では、a[0] = f() の代入先の a[0] のアドレスが関数 f() の呼び出しに先立って評価され、f() の結果がそのアドレスに書き込まれるのだけれど、f() の中で行っている a.push_back() は a[0] のアドレスを変更する可能性があるから、前もって評価された a[0] のアドレスは必ずしも有効ではない。
（実際vector<>を普段使ってる時にはそういうつもりで使ってるわけですけど）
そして今回の現象は、a[0] のアドレスと f() の値のどちらを先に評価するかに依存していて、評価順保証が入ったC++17では意図したとおりの結果になっている。（評価順ってSICP
clang++で意図通りの結果になったのは、f() の実行がインライン展開された結果 "たまたま" a[0] のアドレスの評価が後回しになったから、であって、これは［そうあるべきだから］というわけではなく［未定義動作］なのだろう。
a[0], b[0] のアドレスを表示してみる
#include <vector>
#include <cstdio>
std::vector<int> a, b;
int f() {
a.push_back(-1);
b.push_back(-1);
return (int)a.size();
}
int main() {
int first = f();
printf("a[0]=%d, b[0]=%d\n", a[0], b[0]);
printf("&a[0]=%p, &b[0]=%p\n", &a[0], &b[0]);
a[0] = f();
printf("a[0]=%d, b[0]=%d\n", a[0], b[0]);
printf("&a[0]=%p, &b[0]=%p\n", &a[0], &b[0]);
return 0;
}結果
$ g++ foo.cc $ ./a.out a[0]=-1, b[0]=-1 &a[0]=0x7fcc53d000e0, &b[0]=0x7fcc53d000f0 a[0]=-1, b[0]=2 &a[0]=0x7fcc53d00100, &b[0]=0x7fcc53d000e0 $ clang++ foo.cc $ ./a.out a[0]=-1, b[0]=-1 &a[0]=0x7fe390502750, &b[0]=0x7fe390502760 a[0]=2, b[0]=-1 &a[0]=0x7fe390502770, &b[0]=0x7fe390502750
g++版とclang++版に共通して、b[0] が過去の a[0] と同じアドレスになっている。使い回されてる。
というか
rbx の値が変わったのではなく、かつて a[0] だった場所は b[0] が使うことになったから、という話だったのか。
理解
今回、コンパイラにアセンブラコードを吐かせて（それに手を加えたりしつつ）調べていたお陰で、（C++の闇への）理解が深まった。
vectorって最初に24バイト確保されてて、これはポインタ3つ分の領域なわけだけど、実際に3つのポインタ（begin, end, 確保されているメモリの終端？）でやりくりしていた。（そしてコンパイラはvectorに関して、コードで使われてるpush_backと中身の参照・代入が出来る最低限のコードしか埋め込まない。）
おまけ
push_back() で領域再確保が起こるタイミングを調べる
#include <vector>
#include <cstdio>
int main() {
std::vector<int> a;
int *last = NULL;
for (int i=0; i<=100000; ++i) {
a.push_back(i);
int *curr = &a[0];
if (curr != last) {
printf("a.size()=%d &a[0]=%p\n", (int)a.size(), curr);
last = curr;
}
}
return 0;
}結果。サイズが2^kのとき(1,2,4,8,...)にpush_back()すると再確保される。
a.size()=1 &a[0]=0x7fb801c034e0 a.size()=2 &a[0]=0x7fb801c034f0 a.size()=3 &a[0]=0x7fb801c034e0 a.size()=5 &a[0]=0x7fb801c03500 a.size()=9 &a[0]=0x7fb801c03520 a.size()=17 &a[0]=0x7fb801c03560 a.size()=33 &a[0]=0x7fb801c035e0 a.size()=65 &a[0]=0x7fb801c036e0 a.size()=129 &a[0]=0x7fb802000600 a.size()=257 &a[0]=0x7fb802003600 a.size()=513 &a[0]=0x7fb802003e00 a.size()=1025 &a[0]=0x7fb802004e00 a.size()=2049 &a[0]=0x7fb802800000 a.size()=4097 &a[0]=0x7fb803000000 a.size()=8193 &a[0]=0x7fb803008000 a.size()=16385 &a[0]=0x1046df000 a.size()=32769 &a[0]=0x104700000 a.size()=65537 &a[0]=0x104740000
メモリのアロケーションを倍々に取っていくことでならし計算量をlog(N)のオーダーにする、ってのは知識としては持ってたんだけど、こうやって確認してみたことはなかったし、そうか1から2に伸びる時にすらそれは起こるんだ、という実感を伴っていなかった。
