2011年6月3日金曜日

全てのCプログラマが未定義な振る舞いについて知っておくべきこと #3/3

[原文: What Every C Programmer Should Know About Undefined Behavior #3/3]

このシリーズのPart 1では、Cにおける未定義な振る舞いと、未定義な振る舞いによって"安全な"言語よりもCのパフォーマンスがよくなることがある事例を示した。Part 2では、未定義な振る舞いが引き起こす驚くようなバグと、多くのプログラマがCに対して持っている誤解を見てきた。この記事では、これらに対して警告を出すためにコンパイラが直面する困難と、いくつかの驚かされる問題を取り除きつつパフォーマンスの優位を保つために、LLVMとClangが提供する特長とツールについて説明したい。

未定義な振る舞いを使って最適化するときにどうして警告してくれないの?


「コンパイラが未定義な振る舞いを使って最適化するときに、どうしてコンパイラは警告を出さないのか? ユーザーコードのバグかもしれないのに。」とよく聞かれる。これが難しいのは次の理由による。1) 警告が多すぎて役に立たなくなってしまうと思われる。というのは、バグがない場合にもこの種の最適化は実行されるからだ。2) 人々が警告を欲しいと思う時だけ警告を出すのはとても手の込んだ作業になる。3) ある最適化を適用する機会が、どのような最適化の組み合わせによって生じたのかを (ユーザーに) 表現する良い方法がない。順番に見ていこう。

警告を役に立つようにするのは"本当に難しい"

例を見てみよう。型の不正なキャストのバグがtype based alias analysisによって見つかることが多いからといって、"zero_array" (シリーズのPart 1の例) を最適化するときに "オプティマイザはPとP[i]がaliasではないと仮定している"という警告を出すのは便利とは言えないだろう。

float *P;
 void zero_array() {
   int i;
   for (i = 0; i < 10000; ++i)
     P[i] = 0.0f;
}

"false positive"問題の他にも、論理学的な問題として、意味のある警告を生成するのに十分な情報をオプティマイザが持っていない、というものがある。そもそも、オプティマイザは、Cとは全く異なるコードの抽象表現(LLVM IR)を扱っているし、二点目としては、コンパイラは多層化されていて、"Pからのロードをループの前に出す"ことを考えているオプティマイザは、TBAAがポインタのエイリアス問題を解決するための解析だということを知らない。そのとおり。これは"コンパイラ野郎がめそめそ泣き言を言っている"だけだ。でも本当に難しい問題なんだ。

みんなが本当に欲しい時だけ警告を生成するのは難しい

Clangは、未定義な振る舞いのうち、単純で明確なものに対しては数多くの警告を出すよう実装している。例えば、"x << 421"のような大きすぎるシフトなど。これは単純で明確だと思うかもしれない。しかし、これは実は難しいことで、というのはみんなはデッドコード中の未定義な振る舞いに対しては警告を出してほしくないからだ。(それと 冗長も参照)

このデッドコードというのはいくつかの形式を取る。マクロに定数が渡されたときに変な形で展開されたものとか。caseに到達しないことを証明するにはコントロールフロー解析が必要になるのに、あるcaseに到達できないことを警告すべきだと文句を言われたことさえある。Cのswtich文は適切に構成される必要はない事を考えれば、これは不可能だ。[訳注: 適切に構成されたswitch文ならコントロールフロー解析でデッドコードを判定できるが、そうじゃないswitch文もあるので一般にはできない、という意味だと思われるが、自信はない。]

これに対するClangの解決策としては、"実行時の振る舞い"に関する警告を扱う基盤を拡張し、同時にそのブロックが実行されないとわかったときには、警告が表示されないように取り除くことだ。でもこれはプログラマ同士の腕相撲みたいなもので、私たちが予想しなかったようなイディオムが出てくるし、こういうことをフロントエンドでやると、みんなが捉えて欲しいというケースを捉えられなくなったりする。
[訳注: ほとんど理解できていませんが、ある種の警告に対しては、静的解析時には警告せず、実際にそのブロックが実行されるときに警告を出す、ということでしょうか・・・? そしてその「ある種」の定義にはどうしても漏れが出てくるし、その「ある種」の警告の中でも場合によっては静的に出してほしいケースを捉えられなくなる、という感じか・・・?]

新しい最適化の機会を作りだした最適化の組み合わせを表現する

フロントエンドで適切な警告を生成するのが難しいんだとしたら、もしかしたら代わりにオプティマイザから警告を生成できるんじゃないだろうか! 役に立つメッセージをオプティマイザで生成するときの最大の問題は、データ追跡の一種だ。コンパイラのオプティマイザは、たくさんの最適化パスをふくんでいて、それぞれがコードを正規化したり、(願わくば) 速く動くように変更していく。もしインライン化モジュールがある関数をインライン化すると決定すると、これが他の最適化の機会、例えば"X*2/2"の最適化、を作り出す。

こういう最適化を例示するために、比較的単純で自己完結している例を出したが、多くのケースは、コンパイラが行うマクロ展開や、関数のインライン化、その他の抽象表現の削除によってこういう最適化が有効になる。現実には、人間はこういう馬鹿馬鹿しいコードを直接書いたりはしない。つまり、問題をユーザーコードに送り返すために、コンパイラがどのように中間コードを得たのかを、警告は再構築しなくてはならない。このようなことをいう能力が必要になるだろう。

警告: 3レベルの関数のインライン化 (リンク時最適化のためファイルを跨っている可能性がある) の後、いくつかの共通部分式が取り除かれ、これをループの前に移動して、13個のポインタがエイリアスになっていないことを証明した後、何か未定義な処理が見つかりました。コードにバグがある場合か、マクロやインライン化によって動的に到達不可能なコードが生成され、そればデッドコードだと証明できない場合のどちらかの可能性があります。

残念ながら、このような警告を生成するのに必要な内部のデータ追跡の仕組みがないし、もしあったとしても、コンパイラはこれをプログラマに伝えるのに十分なインターフェイスを持っていない。

究極的には、未定義な振る舞いは、"この操作は不正です - これは発生しないと仮定することができます"と言っていることになるので、オプティマイザにとって価値があるのだ。"*P"のような場合は、PがNULLではないとオプティマイザが演繹することを可能にしている。"*NULL"のような場合 (例えば、定数伝搬と関数のインライン化の後のコード) には、オプティマイザは、このコードが到達可能に成り得ないことを知ることができる。ここでの重要な教えは、停止性問題を解くことはできないので、コードが実際に死んでいるのか (Cの規格によれば死んでいなければならない)、それとも(長くなる可能性のある) 一連の最適化の末に発覚したバグなのかどうかを、コンパイラが知ることはできない。この2つを区別する一般的な良い方法がないので、生成されるほぼすべての警告はfalse positive (ノイズ) となるだろう。

未定義な振る舞いを扱うClangのやり方


未定義な振る舞いに関する残念な状態を考えると、ClangとLLVMが状況を改善するために何をしようとしているのか不思議に思うかもしれない。そのいくつかはすでに述べてきたが、Clang Static AnalyzerKlee project、そして-fcatch-undefined-behavior フラグは、これらのバグを見付け出すための便利なツールとなる。問題は、これらのツールはコンパイラほどに広く使われていないため、これらのツールを改良するよりは、コンパイラを直接改良したほうがずっと良いということだ。ただし、コンパイラは動的な情報を持っていないということと、コンパイル時間を大量に消費せずに出来ることに限られるという限界があることを覚えておいて欲しい。

世の中のコードの改善するためのClangの第一ステップは、他のコンパイラよりも多くの警告をデフォルトで生成することだ。開発者の中には、よく規律を守り、"-Wall -Wextra" (例えば) をつけてビルドする人たちもいるが、多くの人達は、こういうフラグを知らないか、手間を惜しんで指定しない。多くの警告をデフォルトで有効にすれば、より多くの場合により多くのバグを捉えることができる。

第二ステップは、よくある間違いを捉えるために、コード中で明らかな未定義な振る舞いの多くの種類 (NULLポインタのデリファレンス、大きすぎるシフト、など) に対して警告をだす事だ。前述のとおり、いくつかの注意点はあるが、現実にはこれらはうまく働く。

第三ステップは、LLVMのオプティマイザは、未定義な振る舞いに対して、全般的にあまり勝手なことをしないようにしていることだ。規格では、未定義な振る舞いのいかなる例も、プログラムに完全に勝手な効果を与えて良いことになっているが、これは特に便利なわけでも開発者に優しい振る舞いでもない。その代わりに、LLVMのオプティマイザは、いくつかの異なる方法で最適化している。(以下のリンクは、CではなくてLLVM IRのルールの説明だ。ごめん。)


  1. 未定義な振る舞いのうちのいくつかは、可能ならば、暗黙的にトラップする操作に黙って書き換えられる。例えば、Clangは次のC++関数を

    int *foo(long x) {
      return new int[x];
    }
    
    次のX86-64マシンコードにコンパイルする。

    __Z3fool:
            movl $4, %ecx
            movq %rdi, %rax
            mulq %rcx
            movq $-1, %rdi        # オーバーフローのときは -1 をセットする
            cmovnoq %rax, %rdi    # そうすると、'new' は std::bad_alloc を投げる。
            jmp __Znam
    
    GCCは次のコードを生成する。
    __Z3fool:
            salq $2, %rdi
            jmp __Znam             # オーバーフローの時にセキュリティバグとなる!
    
    この違いは、私たちは、バッファオーバーフローとセキュリティ上のバグに繋がる、潜在的に重大な整数オーバーフローのバグ防ぐために、数サイクルを費やすことを決断したという点にある。(operator newは一般的にとてもコストが高いので、このオーバーヘッドはほとんど目立たない。) GCC の人たちも少なくとも2005年からこの問題に気がついていたが、この記事を書いている時点ではまだ修正されていない。

  2. 未定義な値に対する操作は、未定義な振る舞いになるのではなく、未定義な値を生成するように考えられている。この違いは、未定義な値は、ハードディスクをフォーマットしないし、その他の好ましくない効果を生み出したりもしないことだ。便利な工夫としては、未定義な値の部分がどんな値をとったとしても、演算は同じbitを生成するようになっていることだ。例えば、オプティマイザは、"undef & 1"の上位ビットは0になることを仮定し、最下位ビットのみ未定義として扱う。つまり、((undef & 1) >> 1) はLLVMでは0と定義される。未定義にはならない。[訳注: 32bitで考えると (undef & 1) は 0000000000000000000000000000000? というように最下位ビットのみ未定義になるため、これを1ビット右シフトすると0になる。]

  3. 実行時に未定義な操作を実行する演算 (例えば、符号付き整数のオーバーフロー) は、論理的トラップ値を生成する。これはその後の全ての計算を汚染するが、全プログラムを破壊したりはしない。つまり、未定義な操作に依存している論理式は影響をうけるかもしれないが、プログラム全体を破壊することはないということだ。例えば、未初期化変数を操作しているコードをオプティマイザが削除するのはこういう理由だ。

  4. NULLポインタへのストアや、NULLポインタの呼び出しは __builtin_trap() コール変換される (そしてこれは x86における "ud2"のようにトラップ命令に変換される)。これらは最適化されたコード (関数のインライン化や定数伝搬などの変換の結果) でいつも起こっているが、以前は、これらを含むブロックを削除していた。というのは"明らかに到達不可能”だったからだ。

    (杓子定規な言語法学者という視点から言うと) この動作は厳密に正しいが、みんなはときどきNULLポインタをデリファレンスするし、本来呼ばれるべき関数の次の関数の頭でコードの実行が失敗すると、問題を理解するのがとても難しい、ということを我々は学んだ。[訳注: 以前は未定義な振る舞いを含む関数を削除することもあったので、そうすると、その関数のcallerは実際には、その次に配置されるべき関数を呼ぶことになり、(引数の数や型が当然異なるので) その関数の先頭付近で実行時エラーになっていた、という意味] パフォーマンスの観点では、これらを残すことは、下位のコードを押しつぶすことになる。[訳注: この文の意味がとれない] このため、Clangはこれらを実行時のトラップに変換する: もし実行時にどれか一つに到達したら、プログラムはすぐに停止し、デバッグできるようになる。この方法の欠点は、これらの操作や条件を残すことで、コードが少し膨らむということだ。

  5. プログラマが何をしたいかが明らかである (Pがfloatへのポインタであるときに"*(int*)P"を評価する、など) 場合は、オプティマイザが"正しいことをする”ように努力している。多くの場合これは役に立つが、これに頼りたくはないだろうし、あなたが”明らかだ”と思うことでも、コードが何度も変換された後では明らかでなくなる例もたくさんある。

  6. 以上のどれにも該当しない最適化、例えばPart 1における zero_array やset/callの例は、Part 1で説明したとおりに最適化され、ユーザーへの通知は何も無い。こうしている理由は、ユーザーに有用なことは何も通知できないし、これらの最適化によって現実の(バグのある)アプリケーションが壊れることはめったにないからだ。

私たちが取り組んでいる大きな改善点として、トラップの挿入が挙げられる。これによって、(デフォルトでは無効の) 警告フラグがコードに挿入され、オプティマイザがトラップ命令を生成するときに警告を発するようになるだろうと思っている。ある種のコードベースに対しては極めてノイズが多くなるだろうが、その他に対しては便利に使えるだろう。最初の課題として、オプティマイザが警告を生成できるようにするための、インフラストラクチャの開発が挙げられる。例えば、デバッグ情報の生成を有効にしない限り、オプティマイザはソースコードの行番号という有用な除法すら持っていないのだ。(でもこれは修正可能だ)

もうひとつのより重要な課題は、警告は"追跡”情報を一切持っていないので、「この操作は、ループアンロールを3回行って、関数呼び出しを4段階インライン化した結果です」というような説明ができないことだ。せいぜい、オリジナルの操作のファイル名、行番号、カラム数を指摘することしかできない。これは、非常に単純なケースでは役に立つだろうが、そうじゃなければ、大きな混乱を生むだけになると思われる。いずれにせよ、この機能が優先的に実装されてこなかったのは、a) ユーザーによいエクスペリエンスを提供できなさそうだから b) デフォルトでオンにすることはできないだろうだから c) 実装はとても手間がかかるからだ。

Cより安全な方言を使う (またはその他のオプション)


"究極のパフォーマンス"を求めているのでなければ、最後のオプションは、様々なコンパイラオプションを使ってCの方言を有効にし、未定義な振る舞いを取り除くことだ。例えば、-fwrapvフラグを使えば、符号付き整数のオーバーフローを取り除ける (ただし、全ての整数オーバーフローからくるセキュリティ脆弱性を取り除くわけではない)。-fno-strict-aliasingフラグはType Based Alias Analysisを無効にするので、この種の型のルールを気にする必要はなくなる。もし要望があれば、全ての局所変数をゼロに初期化するフラグや、シフト量が変数の場合のシフトの前に"and"を挿入するフラグなどを Clang に追加することは可能だ。残念ながら、ABIを壊したり、パフォーマンスを極限まで落としたりせずに、Cから未定義な振る舞いを完全に取り除く現実的な方法はない。他のオプションとしては、もうCでコードを書くのはやめて、移植不可能なCの方言でコードを書くということだ。 [訳注: 原文では "The other problem with this"となっているが、文脈上おかしいので、「他のオプション」と訳した。]

移植不可能なCの方言でコードを書くことが嫌なら、-ftrapvフラグと-fcatch-undefined-behaviorフラグ (そして以前に述べたその他のツール) が、この種のバグを追い詰めるための武器になるだろう。デバッグビルドでこれらを有効にすれば、関連するバグを早期に発見するのにとても役に立つだろう。もしセキュリティが重要なアプリケーションを作っているのなら、このフラグはプロダクションコードでも有効だろう。全てのバグを見つけることはできないが、バグの有益なサブセットは見つけるだろう。

究極的には、この問題の本質は、Cが"安全な”言語ではないこと、(Cは成功しているし人気もあるが) 多くの人達は、この言語がどのように動くか正しく理解していないことだ。1989年に標準化されるまでの10年間の進化の中で、Cは"PDPアセンブリの上の薄いレイヤである、低レイヤのシステムプログラミング言語"から"多くの人々の予測を裏切って素晴らしいパフォーマンスを提供しようとしている、低レイヤのシステムプログラミング言語"に変わった。これらのCの"ズル"は、ほとんどすべての場合に動作し、そして多くの場合よりよいパフォーマンスを (時には、極めてよいパフォーマンスを) だす一方で、Cのズルは時には人々を驚かせ、最悪のタイミングで襲ってくる。

Cは移植性のあるアセンブラなどではないし、時には驚くほど違う。この考察が、未定義な振る舞いの背後に潜むいくつかの問題を、少なくともコンパイラ実装者の観点から、うまく説明出来ていることを願う。

原著: Chris Lattner
翻訳: Ken Kawamoto

0 件のコメント:

コメントを投稿