未定義動作により最適化レベルで結果が変わるコード

はじめに

「C++アドベントカレンダーが埋まらない〜」という悲鳴が聞こえてきたので、小ネタを投下します。

未定義動作

C++には「未定義動作」というものが存在します。いや、もちろん他の言語にもあるんですけど、C++の未定義動作はちょっと雰囲気が違っています。つまり、世の中には「C++未定義動作を愛する人」というのがいるんですね。愛するというか、未定義動作の匂いを嗅ぎつけるとどこからともなくやってきて「ハナカラアクマ！」と叫びます。「ハナカラアクマ！」というのが何か詳しくは知りませんが、未定義動作を浄化するためのおまじないのようなものだと思えば間違いないと思います。

そんなわけで、うっかり未定義動作を踏んだコードを書いて公開しようものなら、「シープラプラシヨウケイサツ」という秘密結社のメンバーがやってきて、コメント欄で「ハナカラアクマ！」と叫ばれてしまいます。

で、世の中様々な未定義動作の例が落ちているわけですが、単に「未定義動作なので何が起きても知りません」という文脈で語られることが多いです。ところで、最近のコンパイラは未定義動作を発見すると、それを積極的に最適化に利用する傾向にあります。なので、「未定義動作を含むコードは、最適化レベルによって結果が変わる」ということが起きます。

本稿ではそういう例を少しだけ紹介します。

NULLポインターがらみ

C++ではNULLポインタをデリファレンスすることはできません。逆に言えば、コンパイラは「もしポインタがデリファレンスされているのなら、そのポインタはNULLではない」と推定することができます。

こんなコードを書きます。

null.cpp

#include <cstdio>
#include <cstdlib>

int
func(int &v){
  if(&v == NULL){
    return 1;
  }else{
    return 0;
  }
}

int
main(void){
  int *p = NULL;
  printf("%d\n",func(*p));
}

まず、ポインタpがNULLに初期化されており、それをデリファレンスしたものが参照渡しで関数funcに渡されています。関数func内で渡された値のポインタを調べ、それがNULLかどうかで振る舞いを変えています。

まず、最適化レベル0の場合、コンパイラは素直に上記のコードをそのままコンパイルします。その結果、渡されたのはNULLだったため、結果として「1」を出力します。

$ g++ -O0 null.cpp
$ ./a.out
1

さて、最適化レベルを上げると、コンパイラは、上記のコードがNULLポインタのデリファレンスを含む可能性を認識します。関数func内で、もし&vがNULLとなるならば、vはNULLをデリファレンスしたものになります。それは許されないのであるから、&vはNULLではないと仮定して問題ないことになります。従って比較結果は常にfalseとなるため、コンパイラはfuncをこう書き換えることができます。

int
func(int &v){
  return 0;
}

以上から、最適化レベルを-O1以上にすると0が表示されます。

$ g++ -O1 null.cpp
$ ./a.out
0

ならべるとちょっと面白いです。

$ g++ -O0 null.cpp; ./a.out
1
$ g++ -O1 null.cpp; ./a.out 
0

アセンブリも見ておきましょう。funcを-O0でコンパイルすると、ちゃんとNULLと比較してます。

func(int&):
  pushq %rbp
  movq  %rsp, %rbp
  movq  %rdi, -8(%rbp)
  cmpq  $0, -8(%rbp)
  jne L2
  movl  $1, %eax
  jmp L3
L2:
  movl  $0, %eax
L3:
  popq  %rbp
  ret

-O2以上でコンパイルするとこうなります¹。

func(int&):
  xorl  %eax, %eax
  ret

問答無用でゼロを返してますね。

配列外参照

配列外参照は未定義動作を引き起こします。従って、賢いコンパイラは「配列外参照は起きない」ことを仮定して最適化を行うことができます。

こんなコードを書いてみましょう。

array.cpp

#include <cstdio>
#include <cstdlib>

int
func(int index){
  int b[10] = {1};
  int a[1000] = {};
  return a[index];
}

int
main(void){
  printf("%d\n",func(1000));
}

なんの変哲もない配列外参照のコードです。配列aは1000個しか値が無いのに、その1001番目を参照しに行きます。その前にわざとらしく使われない配列bが置いてあります。

さて、GCCの場合、最適化レベル0ではそのままコンパイルされ、実際に配列外参照を引き起こします。、

$ g++ -O0 array.cpp; ./a.out
1

1が表示されました。これはb[0]の値です。

さて、最適化レベルを上げると、コンパイラは「配列外参照は未定義だ」という事実を積極的に利用します。まず、配列外参照は未定義なのであるから、引数indexは必ず0から999までの間であると仮定できます。しかし、コンパイラは配列a[1000]がゼロクリアされていることを知っています。従って、配列aを参照する限り、どこを触っても0であるはずです。以上から関数funcをこう書き換えることができます。

int
func(int index){
  return 0;
}

随分スッキリしてしまいました。実際、-O1以上では結果として「0」を表示します。

$ g++ -O1 array.cpp; ./a.out
0

やっぱり並べるとちょっとおもしろくないですか？

$ g++ -O0 array.cpp; ./a.out
1
$ g++ -O1 array.cpp; ./a.out
0

さて、このコードは最適化レベルだけではなく、コンパイラ依存も引き起こします。例えば、同じコードをclang++でコンパイルするとこうなります。

$ clang++ -O0 array.cpp; ./a.out 
1
$ clang++ -O1 array.cpp; ./a.out 
-2090729263

これは、clang++が「配列aはどこを触っても0だ」という事実を使った最適化を行わないためです。clang++は「配列bは使われないから削除」という最適化のみを施して、こうします。

int
func(int index){
  int a[1000] = {};
  return a[index];
}

これにより、メモリ上ではa[1000] = b[0]だったわけですが、そのbがなくなってしまったため、値が不定になります。

さらに、インテルコンパイラ(16.0.4)は違う答えを表示します。

$ icpc -O0 array.cpp; ./a.out
1000

「1000」が表示されました。なぜ「1000」が表示されたかわかりますか？

実はこれは関数の引数が表示されています。なので、こんなことができます。

array2.cpp

#include <cstdio>
#include <cstdlib>

int
func(int index, int hoge){
  int b[10] = {1};
  int a[1000] = {};
  return a[index];
}

int
main(void){
  printf("%d\n",func(1002,12345));
}

$ icpc -O0 array2.cpp; ./a.out 
12345

これは、a[1002]の指す場所が、スタックに積まれた二つ目の引数12345を指しているからです。

もちろん、最適化レベルを上げると結果が変わります。

$ icpc -O1 array.cpp; ./a.out 
4196864
$ icpc -O1 array2.cpp; ./a.out 
4197141

インテルコンパイラも「配列aはどこを触っても0であるはず」という事実を使った最適化はしません。

まとめ

というわけで、未定義動作を利用してコンパイラの最適化レベルによって結果が変わるコードを作って見ました。こういうもの見たり聞いたりする時には気をつけなければいけません。ほら、もう貴方の背後に「シープラプラシヨウケイサツ」の足音が・・・

参考

• 本の虫：とても賢いコンパイラーの逆襲
• GCCの最適化がインテルコンパイラより賢くて驚いた話
• C言語分かってなかった (I Do Not Know C)
• What Every C Programmer Should Know About Undefined Behavior #1/3, #2/3, #3/3

1. なんか-O1だと変なことをしてたので-O2の結果を出します。 ↩