要約

  • Frances E. Allenは、最適化を高速化の小技の集積から、制御経路、定義、使用関係を扱う規律ある解析へ進めた。
  • 区間、到達定義、生存性が示すのは条件付きの静的事実であり、実行履歴でも、未定義動作やデータ競合、数値的不安定性がないという証明でもない。
  • Allenの仕事は、John Cocke、Reese T. Prosser、E. S. Lowry、C. W. Medlock、Kenneth Kennedy、Stretch・Harvest・ACS各チームの寄与と区別しながら記録すべきである。

ループの外へ一つの演算を移そうとする最適化器を考える。オペランドのどの定義がそこへ届くのか。途中で再定義されないか。後の経路で値が使われるか。例外や外部から見える処理の順序は変わらないか。見た目の重複だけでは判断できない。

モデルを作り、その上で関係を計算し、前提が満たされたときだけ変換する。Frances E. Allenは、この手続きをコンパイラー工学の中心へ据えた。

IBMの人物史によると、Allenは1957年、新しく入った科学者にFORTRANを教えるためIBMへ入社した。その後、Stretch–Harvestと実験的なAdvanced Computing Systemsに携わった。2006年、ACMのチューリング賞資料は、最適化コンパイラー技術の理論と実践への先駆的貢献を評価した。女性として初の受賞でもあった。

「Allenが最適化を発明した」という短い表現では、重要な点を取り逃がす。彼女の研究が与えたのは万能な正しさではなく、コンパイラーが何を、どの仮定の下で知ったのかを述べる形式だった。

制御フローグラフは可能性の地図である

1970年の Control Flow Analysis は、式やデータを大域的に調べるにはプログラムの制御経路が必要だ、という問題から始まる。基本ブロックをノード、起こり得る制御の移動を有向辺とする。論文のモデルで基本ブロックは、一つの入口と一つの出口を持つ直線的な命令列である。

辺は実行記録ではない。制御が移れることを表すだけで、ある実行がその辺を通ったとは言わない。ここに最初の証拠境界がある。

Allenは区間でグラフを整理した。ヘッダーhを持つ区間は、全ての閉路がhを含む最大の単一入口部分グラフである。入口から始め、全ての直前ノードが区間に入ったノードを追加する。縮約を繰り返すことで、経路を総当たりせずにループとフローの階層を扱える。

論文は先行研究を明記している。ブール行列・接続行列と支配概念の導入はReese T. Prosser、支配研究の大幅な展開はE. S. LowryとC. W. Medlock、区間構成はJohn Cockeに帰される。Allenの成果は、こうした基礎を隠すことではなく、解析可能な工学へまとめた点にある。

「到達し得る」は「実際に値を供給した」ではない

AllenとCockeの1976年論文 A Program Data Flow Analysis Procedure は、各ノードへ到達し得る定義と、各辺で生存している定義をコンパイル時に求める。

ある定義が後のブロックへ到達するのは、出発点で局所的に利用可能で、同じデータ項目の再定義がない経路が少なくとも一つ存在するときである。「少なくとも一つ」はmay解析を意味する。結果は可能性を保守的に覆うが、どの経路が実行されたか、ある実行の値がどの定義から来たかまでは示さない。

生存性も限定された問いに答える。到達する定義が、先の露出した使用で参照され得るかどうかである。レジスターに残す判断や無用な計算の除去には使えるが、値が全ての実行で存在することや、その使用が安全であることを保証しない。

手続きは区間順の辺とビットベクトルを用い、可約・非可約グラフを同じ枠組みで扱う。著者は、生存解析アルゴリズムをKenneth Kennedy、データ構造の着想をRichard Staskoに帰し、Ullman、Hecht、Kildall、Schaefer、Schwartzらの貢献も記録した。

変換一覧は「最適」の定義ではない

AllenとCockeの A Catalogue of Optimizing Transformations は、共通部分式の除去、コード移動、演算強度の軽減、冗長処理の削除などを体系化した。しかし著者自身、一覧は網羅的でなく、一般的な最適値を定義できない場面で「最適化」という語は不正確だと述べている。主眼は実行時間、次いで空間であり、運用全体の費用や保守性ではない。

指定された意味論の下で合法な変換も、全ての評価軸を改善するとは限らない。浮動小数点演算の並べ替えは丸めを変え得る。重複して見える読み込みも、volatileな場所、共有メモリー、装置から観測される場所、例外を起こす処理なら消せない。

必要なのはグラフの形だけではない。言語の評価規則、別名関係、例外、算術契約が要る。並行プログラムではメモリーモデルと同期順序も加わる。中間表現は条件を明示できるが、条件そのものを不要にはしない。

意味を保つ変換も、プログラム全体を保証しない

最適化器が自分の証明義務を完全に果たしても、ソースプログラムが特定入力で未定義動作を起こすことはある。スレッド間にデータ競合があるかもしれない。数値アルゴリズムが丸め誤差を拡大したり、そもそも要求を取り違えたりする場合もある。コンパイラーの証明は、これら上位の主張へ自動的に広がらない。

それは欠陥ではない。価値のある解析は「このグラフ、この定義と使用、この意味上の条件では、この関係が成り立つ」と検査可能な形で言える。危険なのは、組織がその文を単なる「正しい」という緑色表示へ縮めることである。

人物史も同じ精度を必要とする。IBMはAllenをStretch–Harvestの設計者・言語連絡役、ACSコンパイラー研究の中心人物として記す。IEEE Computer Societyの紹介は1966年のProgram Optimization、区間解析、変換一覧を結び付ける。ACMのJohn Cocke紹介はCocke自身の基礎的貢献を残す。ハードウェア、言語、コンパイラーの各チームが抽象を実働システムにした。

Allenがコンパイラーへ与えたのは、全てを知っていると主張する権利ではない。何を証明したかを、厳密に述べる能力だった。

出典