2011年5月29日日曜日

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

[What Every C Programmer Should Know About Undefined Behavior #1/3 の翻訳です。]

LLVMでコンパイルしたコードは、最適化を有効にしているとたまにSIGTRAPシグナルを生成するのはなぜなのか、と聞かれることがある。いろいろ調べたあと、(X86での話だが) Clangは "ud2" インストラクションを生成していたことがわかった。"ud2" は__builtin_trap()が生成するインストラクションと同じものだ。[訳注: #UD例外を発生させる命令。ソフトウェアが#UD例外をハンドルできているかテストするために使われる。つまり、ソースコードが未定義な振る舞いを使っていたから、LLVMはud2インストラクションを生成したのであって、LLVMのバグではない、ということ] こういう問題は幾つかあって、すべて、Cの未定義な振る舞いとそれをLLVMがどう扱っているかとに関係している。


この記事 (3つの記事のうちの最初) では、トレードオフと問題の複雑さをより理解してもらうために、いくつかの問題を説明したい。それと、Cのダークサイドも少し話したい。経験のあるCプログラマ、特に低レイヤを扱っているプログラマは、Cを"高レベルなアセンブラ"だと考えるのが好きだが、Cは決して"高レベルなアセンブラ"などではなく、C++やObjective-Cは、その問題の多くを継承していることがわかるだろう。

未定義な振る舞いの紹介


LLVM IR [訳注: 中間言語実行系?] にもプログラミング言語Cにも"未定義な振る舞い”という概念がある。未定義な振る舞いとはいろいろな意味を含む幅広いトピックだ。John Regehrのブログの記事がもっともうまく説明していると思う。この素晴らしい記事を要約すると、パッと見た感じでは正しそうなCコードが実は未定義な振る舞いを含んでいて、これがバグの原因になっていることがよくある。さらに、Cの未定義な振る舞いがあると、実装 (コンパイラと実行系) は、ハードディスクをフォーマットしたり、全く予期できない挙動を示したり、もっと悪い事をしても良いことになっている。繰り返しになるが、Johnの記事を読むことを強く勧める。


CやCから派生した言語に未定義な振る舞いが存在するのは、Cの言語設計者がCをものすごく効率的な低レイヤプログラミング言語にしたかったからだ。対照的にJava(や他の「安全な」言語」)では、効率を犠牲にしてでも、安全で、実装によらずに同じ挙動を求めているので、未定義な振る舞いは避けられている。どちらも「追求すべき唯一の正しいゴール」ではないが、あなたがCプログラマなら、未定義な振る舞いが何であるのかを確実に理解すべきだ。


詳細に立ち入る前に、幅広いCアプリのパフォーマンスを引き出すためにコンパイラが何をやっているかを簡単に説明したい。というのも、魔法の弾丸などないからだ。ものすごく大雑把に説明すると、ハイパフォーマンスなアプリケーションを生成するために、コンパイラは次のことをする。a) レジスタアロケーションやスケジューリングなどの基本的なアルゴリズムを使って良い仕事をする。 b) 極めて大量の「トリック」(ピープホール最適化、ループ変換、など)を理解し、それが効きそうなら適用する。 c) 不要な抽象化をうまく取り除く (Cのマクロを使うことによる冗長性、関数のインライン化、C++のテンポラリオブジェクト)。 d) ソースコードを台無しにしない。以下の最適化は些細なものに見えるかもしれないが、たくさん実行されるループの中の、たった1サイクルでも削減出来れば、それによって、コーデックが10%速くなったり、消費電力が10%少なくなったりする。


Cの未定義な振る舞いのメリット。実例つきで。


未定義な振る舞いのダークサイドと、LLVMをCコンパイラとして使ったときのポリシーと振る舞いとを説明する前に、未定義な振る舞いのいくつかの実例を検討して、それらがJavaなどの安全な言語よりも良いパフォーマンスを実現するのが分かりやすいと思う。これらの実例は、未定義な振る舞いのクラスごとの"最適化を可能にする”とも言えるし、"未定義な振る舞い"を"定義された振る舞い"にするために必要な"オーバーヘッドを避ける"とも言える。コンパイラのオプティマイザは、このようなオーバーヘッドのいくつかは取り除けるのだが、全てのケースで一般的にオーバーヘッドを取り除くには、停止性問題やその他の"興味深い問題”を解決しなければならない。[訳注: 停止性問題は決定不能問題(解くことはできない)なので、つまり、コンパイラが一般的にオーバーヘッドを取り除くことはできない、と言っている。]


それと、Cの規格が未定義としている振る舞いのうちいくつかは、ClangでもGCCでも定義されていることを指摘しておきたい。これから説明するケースは、Cの規格で未定義とされていて、かつ、ClangとGCCの標準モードで未定義として扱われるものである。


未初期化変数の使用: これは、Cプログラムの問題の原因としてよく知られている。そのため、コンパイラの警告や動的アナライザといった、多くのツールでこの問題を発見できる。スコープに入ったときに変数を0で初期化する必要がない(Javaは0初期化する)ため、パフォーマンスの向上につながる。スカラー変数は、0初期化するとしてもオーバーヘッドは殆ど無いが、スタックに配置された配列やmallocで確保されたメモリを初期化しようとすると、ストレージに対してmemsetを呼ぶこともあり、それは非常にコストが高い。とくにストレージはたいてい完全に上書きされるので。[訳注: 「とくに」以降がよくわからない]


符号付き整数のオーバーフロー: 例えばint型に対する演算がオーバーフローすると、結果は未定義となる。例えば"INT_MAX+1"がINT_MINになることは保証されていない。この振る舞いにより、ある種のコードにとって重要な最適化を行うことが可能となる。例えば、INT_MAX + 1 が未定義であることを利用して、"X+1 > X" を "true" に最適化することができる。乗算がオーバーフローしない(オーバーフローした結果は未定義なので)ことを活かせば、"X*2/2" を "X" に最適化することができる。これらは些細な最適化に見えるかもしれないが、関数のインライン化やマクロ展開によってこのような最適化の機会がたくさん出てくる。より重要な最適化としては、"<=" を使ったループが考えられる。

for (i = 0; i <= N; ++i) { ... }

コンパイラは、iがオーバーフローすると結果が未定義になることを利用して、このループがちょうどN+1回ループすることを仮定できるし、それによって各種のループ最適化を使用できる。一方、もし変数がオーバーフローするとラップする[訳注: 最小値に戻る]と定義されていたとしたら、コンパイラはこれが無限ループになるかもしれない(NがINT_MAXだと無限ループする)ことを仮定しなければならない。intはループ変数によく使われているので、64-bitプラットフォームでは特に問題になる。[訳注: 64bitプラットフォームではNがINT_MAX以上になることが多いが、intは32bitなので、問題が表面化しやすい、という意味だと思われる。]

符合なし整数型のオーバーフローは、2の補数になる(wrapする)ことが保証されていて、これは常に活用できることを指摘しておく。符号つき整数のオーバーフローの振る舞いを定義するコストとしては、これらの最適化が全く使えなくなることがある。(たとえば、よくある症状としては64bitプラットフォームでのループ内で大量に符号拡張をしなくてはならなくなる。) ClangもGCCも "-fwrapv" フラッグをサポートしており、これをつけると、符号付き整数のオーバーフローを定義済みの挙動とするようにコンパイラに強制できる。(ただし、INT_MINを-1で割った場合のみ、依然として未定義となる)


大きすぎるシフト: uint32_t型の変数に対する32bit以上のシフトは未定義である。様々なCPUがこの種のシフトに対して異なる動作をすることから、この仕様が作られたと私は思っている。例えば X86 アーキテクチャでは 32bit 変数のシフト量は 5 bit に切り捨てられる (そのため32bitシフトするのは0bitシフトするのと同じである) が、PowerPC は 6bit に切り捨てる (なので32bitシフトすると0が生成される)。この未定義な振る舞いを取り除くためには、コンパイラが変数のシフトに対して、余分なオペレーション (例えば 'and') を発行しなくはならない。多くのCPUでは、これはコストを2倍にするだろう。[訳注: 例えば「シフト量は5bitに切り捨てられる」と定義すると、5bitに切り捨てるためにandインストラクションが必要になる。大抵のCPUではshiftもandも1サイクルで実行できるので、andを追加することはコストを2倍にすることになる。]



不正なポインタのデリファレンスと配列の範囲外アクセス: 不正なポインタ (NULLポインタや解放済みのメモリを参照するポインタ) のデリファレンスや配列の範囲外アクセスは、Cアプリケーションによく見られるバグなので、説明は不要だと思いたい。これを取り除くには、配列にアクセスするたびに範囲チェックが必要になるし、ABIを変更してポインタが範囲情報を持つようにしなくてはならない。この範囲情報は、ポインタ演算で使用/更新することになるだろう。これは、数値計算アプリケーションにとってもその他のアプリケーションにとっても極めてコストが高くつくし、既存のCライブラリとの互換性を壊してしまう。



NULLポインタのデリファレンス: 誤解されることが多いが、CにおけるNULLポインタのデリファレンスは未定義である。例外になるとは定義されていないし、アドレス0にmmapしたらそのページにアクセスできるとも定義されていない。これは、不正なポインタのデリファレンスを禁止するルールややNULLを番兵(sentinel)として使うこととは別の話だ。NULLポインタのデリファンレンスを未定義とすることで、様々な最適化が可能になる。対照的にJavaでは、コンパイラが、ポインタのデリファレンスをまたがるように、副作用のある操作を移動することを禁止している。ポインタがNULLではないことを証明できないからだ。これはスケジューリングやその他の最適化にとって大きな制約となる。Cを基盤とする言語においては、NULLのデリファレンスが未定義であることで、マクロ展開や関数のインライン化によって生じる多くの単純なスカラー最適化が可能になる。

LLVMから派生したコンパイラを使っているなら、"volatitle"なNULLポインタをデリファレンスすることで、プログラムを(もしそうしたいなら)クラッシュさせることができる。オプティマイザはvolatileなロード・ストアに普通は関与しないからだ。今のところ、NULLポインタを使ってのロードを有効なアクセスにしたり、ロードするときにポインタがNULLであるかもしれないことを明示するフラグは存在しない。


型に関するルール違反: int*をfloat*にキャストして、それをデリファレンスすること(intをfloatとしてアクセスすること)は未定義である。Cは、このような型変換をmemcpyを使って実現することを要求している。ポインタのキャストを使う方法は、正しい方法でなく、未定義な振る舞いとなる。このルールはとても微妙なので、ここでは詳細 (char*に対する例外、ベクタ型は特別な性質がある、共用体 (union) では事情が異なる、など) には触れない。この振る舞いは、メモリアクセス最適化で使われる "Type-Based Alias Analysis" (TBAA) という解析を可能にする。例えば、このルールのおかげで、Clangはこの関数

float *P;
 void zero_array() {
   int i;
   for (i = 0; i < 10000; ++i)
     P[i] = 0.0f;
 }
を、"memset(P, 0, 40000)"に最適化できる。また、多くのメモリロードをループの前に移動させる、共通部分式を削除する、という最適化も可能になる。この種の未定義な振る舞いは、-fno-strict-aliasing フラグを指定することで無効にすることができ、この解析も無効になる。このフラグが渡されると、Clangは、このループを 10000個の 4byte ストアにコンパイルしなくてはならない (数倍遅くなる)。というのは、次の例のように、ストアによってPの値が変わる可能性を考慮しなくてはいけないからだ。

int main() {
   P = (float*)&P;  // このキャストによって zero_array の中で TBAA 違反となる
   zero_array();
 }
この種の型の乱用はあまり一般的ではないので、標準委員会は、"妥当な" 型のキャストによる予期しない結果と引き換えに、大幅なパフォーマンス向上を選んだ。Javaは、このような欠点なしに、型を利用した最適化を恩恵を受けていることを指摘したい。Javaではそもそも危険なポインタのキャストはできないからだ。

とにかく、Cにおける未定義な振る舞いによって、いくつかの最適化が可能になっていることを少しでも分かってもらえれば嬉しいと思う。もちろん、"foo(i, ++i)" のような sequence point violation [訳注: 日本語訳を知らないので原文のまま]、マルチスレッドプログラムにおける競合状態、"restrict" 違反、ゼロによる除算、など他にもいろいろある。


次の記事 では、パフォーマンスが唯一の目的でないとしたら、Cの未定義な振る舞いが極めて恐ろしいことを説明する。この連載の最後の記事では、LLVMとClangがどのように対処しているかについて話したい。


原著: Chris Lattner
翻訳: Ken Kawamoto

0 件のコメント:

コメントを投稿