えびちゃんの日記

えびちゃん（競プロ）の日記です。

未定義動作は未定義動作だよという話

人々は未定義動作に多くを期待しがちではという気持ちがあるので書きます．

まず「これこれは未定義動作です」と言ったとき，目に見えるやばいこと*1が発生するとは限らないです．「なんかうまくいく」とか「必ず実行時エラーになる」とかは保証されていません．

「未定義動作が起きます」という文より，「こういうコードを書いた場合の動作は定義されていません」という文の方が実態に即している気がします．

気づきにくい要因として，コンパイラが以下のような動作をすることが仕様で許されているというのがあります．

  • 未定義動作は起こらないと仮定してよい
  • 起こらないのだから，無視して最適化してよい

無視して最適化された結果として「なんかいい感じに動く」ということはありますが，当然常にうまくいくわけではありません． 甘えるのはやめましょう．

ある環境でたまたま動いたコードが別の環境で動かなかったときに「環境依存のコード」と言うのもやめましょうね．そもそも「環境依存」は C++ 用語ではないです． ここでは説明しませんが「処理系定義」「未規定」「未定義」はそれぞれ意味が別です*2．

例

さて，わかりやすい例をいくつか挙げてみましょう．

ゼロ除算

「ゼロ除算は実行時エラーになる」と信じている人は多いでしょう．ですが，正しくは未定義動作であり，エラーとは限りません．

int f(int d) {
  d /= d;
  return d;
}

最適化の結果，次のようなコードをコンパイルした場合と同じ結果になりえます．

int f(int) { return 1; }

コンパイラは /= 0 のことを考える必要がないのでこのようにできます*3．実行時エラーが起きなくても知ったことではありません．

（追記 2021/05/05）

最近気づいたので書きます。

int f(int x, bool y) { return x / y; }

これは次のようにできます。

int f(int x, bool) { return x; }

これは、y == true のとき x / 1 と等しく、y == false のとき未定義であることから従います。追記おわり。

符号つき整数のオーバーフロー

「符号つき整数がオーバーフローしても 2 の補数表現でいい感じになって（ちゃんと定義された）負の値になる」とか信じている人は多いでしょう*4．

これも，正しくは未定義動作であり，「正の大きい足す正の大きいは負のなんか」みたいなことを期待してはいけません．

bool f(int x) {
  // x+1 がオーバーフローして負の値になるなら
  // x < x+1 は false になるはず？
  if (!(x < x+1)) return false;
  return true;
}

実際は，符号つき整数のオーバーフローが未定義であることから x < x+1 は常に真であると仮定できるため，以下のコードと等価になりえます．

bool f(int) { return true; }

bool f(int x, int y) {
  // 正の x, y について x*y がオーバーフローすると
  // x*y/y != x になるはず？
  if (!(x*y/y == x)) return false;
  return true;
}

こちらも，true だけ返すようになりそうです．ABC 169 B などで，これをしてこわれた例もあります．

符号つき整数のオーバーフローとしつこく言っていることから察せる通り，符号なし整数のオーバーフローは未定義ではありません．

追記：この事情について

えびちゃんの推測などを書きます．

符号つき整数のオーバーフローが未定義なのは，たぶん表現方法が一つに定まらない事情がありそう？ 負数の表現については，1 の補数表現，2 の補数表現，符号・絶対値表現が認められています．そのうち 2 の補数表現に統一されるらしいですが．

そのため，符号つき整数のオーバーフローの挙動を規定するのは難しかったんだろうと思っていました．

なんですが，C++20 からは負数の表現が 2 の補数表現に規定されるんですが，それでも符号つき整数のオーバーフローは未定義のままとのことらしくて，...？

\((2^{N-1}-1) + 1 = -2^{N-1}\) と定義するのは不自然ですし，そうするメリットが特にない（上で述べたような最適化ができなくなる）ので未定義としていそう？

この記事を公開した後の話ですが，n*2/2 はオーバーフローを無視できるなら n と最適化できると見てなるほどなぁとなりました．

一方，2n-bit 符号なし整数の演算は mod 2n で行われると規定されているんですが，こうすることのうれしさはよくわかってないです（ハードウェアとか関係してる？ わからない）．

足し算や掛け算を行った結果の下位ワードのみを得るみたいな操作ができるとうれしい？

この辺の事情に詳しい人がいたら教えてほしいです．

追記おわり．

（追記 2021/05/05：教えてもらいました）

シフト演算

シフト演算において，シフトの幅がビット幅以上の場合の動作は未定義です．0 になってくれるとうれしいと思っていた人も多いのでは？

int f(int x) {
  if (x == 1) x <<= 123;
  if (x == 2) x >>= 456;
  return x;
}

次のようなコードと等価になりそうです．

int f(int x) { return x; }

シフト幅が負の場合の動作も未定義です．

未初期化の変数

未初期化の変数を使った場合の動作は未定義です． グローバルや static で宣言した場合は 0 で初期化されているので別です．

コンパイル時に警告が出ると思うので，ちゃんと見てれば防げるミスだとは思います（警告をちゃんと見ようね）．

未定義なので，bool の変数が「true でも false でもない何か」であるかのように振る舞うことがあります．

int main()  {
  bool x;
  if (x || !x) puts("true");
  else puts("false");
}

こうなることもありえます．

int main() {
  puts("false");
}

配列境界外参照

「配列外参照してるけどなんか AC したわ」「配列外参照してるんだったら RE になってくれ」というのを無限回聞きましたが，これも未定義動作なので，そういうのは保証されません．もうわかりますね．

bool f(int x) {
  int a[] = {31, 41, 59, 26};
  for (int i = 0; i <= 4; ++i)
    // x が a に入っていれば true
    if (x == a[i]) return true;
  return false;
}

a[4] にアクセスするのは未定義であるため，そうしたことは起こらないと仮定できます．

ところで，それが起こらないということは i < 4 のうちに return true; が起きるということでしょう．ふふん，コンパイラちゃんはかしこいので見破っちゃいます．次のように最適化しちゃいますよ．

bool f(int) { return true; }

えぇ...

また，ポインタを操作している場合，境界外をポインタが指しても * をしなければ問題ないと思っている人が大半だと思っているんですが，嘘です．

int a[n]; のような配列に対して，&a[0] から &a[n] の範囲（&a[n] 含む）に乗っていない場合は未定義です．

int a[9] = {};
for (int* p = a; p < a+9; p += 2) ...

と書いた場合，最後に p == a+10 となって未定義になるので，大変なコードと等価になるかもしれません．

比較関数

STL の関数たちも，定められた条件が満たされていない場合は未定義動作になります．

たとえば，std::sort に渡す比較関数*5comp は以下が成り立つ必要があります．

  • comp(a, a) は false
  • comp(a, b) が true ならば comp(b, a) は false
  • comp(a, b) && comp(b, c) が true ならば comp(a, c) は true

数学っぽい記号で書いた方が分かりやすければ，以下のような感じです．

  • \(\neg(a < a)\)
  • \(a < b \implies \neg(b < a)\)
  • \(a < b, b < c \implies a < c\)

さらに、equiv(a, b) を !comp(a, b) && !comp(b, a) で定義して、equiv(a, b) && equiv(b, c) が true ならば equiv(a, c) が true になる必要があります。

これらを満たさない関数を渡した場合，動作は未定義です．わかりやすい例として，常に true を返す関数を考えてみましょう．

std::sort(a.begin() a.end(), [](auto, auto) { return true; });

等価なコードを示すのは難しいですが，実際に起こりうる例として，Segmentation fault が起きたり無限ループになったりします．最適化オプションによって変わったりします．

意図せずに要件を満たさない関数を渡していないか気をつけたりしましょうね．

ん，たとえば，[](auto x, auto y) { return x < y; } は問題ないですが [](auto x, auto y) { return x <= y; } は満たしていませんね．

除算

ゼロ除算に気をつければ問題ないと思っていましたか？

負数が 2 の補数表現かつ x == INT_MIN のとき，x / (-1) は未定義です．

剰余算

/ だけ気をつければいいと思っていませんか？

上と同様の仮定の元，x % (-1) は未定義です．

x % y について，x / y が対象の型で表せないなら x % y も未定義という仕様があります．

int f(int x) {
  x %= -1;
  return x;
}

% (-1) は大抵 0 になりますから，次のように書き換えられるかもしれません．

int f(int) { return 0; }

かもしれませんが，それを期待するのはいけません．

さらなる罠

as-if rule というのがあります（唐突）．

観測できる挙動については，（最適化されても）コードに書かれたままであるかのように行われなければいけない，という規則です．

よくある「printf するだけで別の挙動になった」にはこういう背景があります． 先ほどの配列境界外参照の例に手を加えたものです．

bool f(int x) {
  int a[] = {31, 41, 59, 26};
  for (int i = 0; i <= 4; ++i) {
    printf("%d == %d ???\n", x, a[i]);
    if (x == a[i]) return true;
  }
  return false;
}

このとき，x の値に応じて出力が行われる必要があるため，先ほどのようには最適化できなくなってしまいます．

まとめ

コード例とともにいくつかの未定義動作を紹介しました． 人々の期待に反しそうな動作をするものを集めたつもりです．

最適化された結果，等価になりうるコードの例を挙げましたが，これらは一例にすぎません． もっと大きいコードを書いたとき，コンパイラの気持ち次第では思いもよらないコードと等価になることもありえます．

「このコードは未定義だけど，あのとき期待通りに動いたから大丈夫なはず」などとは思わないことです．

*1:鼻から悪魔が出る，異世界に転生する，PC が爆発する，など

*2:「未定義」以外のふたつは書いても許されるけど，どうなるかは処理系によるもので，「未定義」は書くと何が起こるかわからない・許されない，くらいは覚えておくとよさそう？

*3:引数を使わない場合，名前を省略できます．

*4:そういう人が多いとえびちゃんは思っています．

*5:知らない人は調べてね．第三引数に関数を渡すことができます．