詳細化としての最適化：コンパイラが変更してよいものを証明する

最適化問題には制約がある

コンパイラには、言語が保証する振る舞いを保存しながら実行コストを削減することが求められる。コストにはレイテンシ、コードサイズ、エネルギー、コンパイル時間などがあり、許容される振る舞いは型、算術規則、メモリ操作、例外、観測可能な相互作用に依存する。契約を変更することである目的を改善する変換は、単なる高速な実装ではなく、別のプログラムを生み出す。

たとえば、計算を定数に置き換えることは、数学的整数では正しく、剰余算術を行う符号なし整数では誤りであり、オーバーフローが未定義であるソース言語の符号付き算術では条件付きで正しい場合がある。表面的な構文だけでは答えは決まらない。したがって、有用な最適化の主張には、書き換え後の式とともに意味論上の事前条件を含める必要がある。これらの事前条件は、典型的な入力に関する非形式的な仮定にとどめず、実装または証明に表現すべきである。

信頼できる変換への三つのアプローチ

LeroyによるCompCertの研究は、形式的に検証されたコンパイラを示し、意味保存がコンパイル済みのクリティカルソフトウェアへの信頼をいかに支えるかを説明している。LLVMの原論文は、共通の低水準表現と、解析および変換のための枠組みを記述している。Alive2はLLVM IRに対する有界翻訳検証を提供し、資源使用量を制御しながら個々の変換を検査する。

これらのアプローチは異なる範囲を対象とする。コンパイラの証明は、検証済みパイプラインが対象とする変換について推論する。翻訳検証は、検証器がモデル化する意味論と限界の下で、特定の変換前後の組を検査する。中間表現は解析や変換を表現可能にするが、それらを自動的に正しくするわけではない。よく知られたIRの使用や検証器の実行によってツールチェーン全体を検証したとプロジェクトが主張する場合、これらの区別が重要となる。 [1], [2], [3]

等価性が適切な関係ではない場合

ソースプログラムは、未規定の選択や非決定性によって複数の振る舞いを許容することがある。コンパイラは、すべての内部的な選択を保存せずに、許容される振る舞いの一つを選んでもよい。したがって、詳細化の観点では、停止と未定義動作を適切に扱ったうえで、ターゲットがソースの禁止する振る舞いを導入するかどうかを問う。

詳細は言語ごとに異なる。ソースに未定義動作がある場合、言語はその実行に何の要件も課さないことがあるが、これは他の箇所で定義済みの実行を変更することを認めるものではない。検証器は、未定義動作を任意の通常値として扱うのではなく、この区別をモデル化しなければならない。同様に、IR内の内部的なpoison値は固定された整数と交換可能ではない。レビューでは実際の意味論的関係を明示し、オプティマイザのデータ構造中のすべての値が通常の機械値を表すと仮定しないようにすべきである。 [1], [2]

魅力的な書き換えに対する八ビットの反例

符号なしbビット変数xを取り、剰余算術を用いてxに一を加えた値とxを比較する。この比較は、最大値を除くすべてのxで真となる。最大値では、加算結果がゼロに折り返すため比較は偽となる。したがって、この式を真に置き換えることは符号なし算術では誤りである。

八ビットの場合、全数列挙により256個の入力の中から反例がちょうど一つ見つかる。それはxが255のときである。境界にめったに到達しないランダムテストでは、これを見逃す可能性がある。オーバーフローが未定義であるソース言語の符号付き型では、対応する最適化に、定義済みの実行に限定した別の論証が必要になる。要点は、定数畳み込みが一般に危険だということではない。証明義務が型とオーバーフローの契約によって決まり、テキスト上は同じに見える式でも異なる契約に属し得るということである。

剰余算術における陽性対照

符号なしbビット算術では、xを二倍して二のb乗を法とした結果は、簡略化したビットベクトルモデルにおいてxを一ビット左シフトし、下位bビットを保持した結果と一致する。この恒等式はすべてのビットパターンで成立し、テストハーネスに陽性対照を与える。付録では、妥当な書き換えと不正な書き換えの双方について、八ビットの全入力を列挙する。

ソース言語は、許容されるシフト量や型昇格後のオペランド型など、シフトに追加の条件を課す場合がある。本稿のモデルではシフト量を一に固定し、bビットベクトル上で操作を直接定義する。この結果をCまたはC++のソースコードに拡張するには、そうした言語の詳細を確認する必要がある。この制限を明示する方が、ビットベクトルの恒等式をソースレベルの普遍的な書き換えとして提示するよりも望ましい。

浮動小数点演算が保存する情報は異なる

aを大きな正の浮動小数点値とする。厳密な算術では、aに負のaを加えてから一を加える式と、負のaに一を加えた量をaに加える式は等しい。最近接丸めを用いるbinary64算術では、前者は一になる一方、後者は中間値である負のaと一の和の丸めで一が失われるとゼロになり得る。

数値例では十のべき乗を用い、両方の評価順序を記録する。aが十の十六乗のとき、明示したbinary64モデルで差が現れる。これは構成された算術上の証拠例であり、オプティマイザのベンチマークではない。この例は、緩和された浮動小数点オプションの下での再結合が、受け入れられる数値的契約を変更する理由を説明する。このようなトレードオフが適切な場合もあるが、誤差の許容範囲と後続の科学的利用に照らして評価しなければならない。

数値誤差はアプリケーションレベルの量である

小さな局所的差異は、あるアプリケーションでは無視できても、別のアプリケーションでは決定的になり得る。閾値判定、反復ソルバー、悪条件の式は、丸めの変化を増幅し得る。逆に、桁落ちを回避する変換によって速度と数値精度の双方が改善される場合もある。元の評価順序を保存すれば常に数学的問題に対する最良の近似が得られる、という一般則はない。

適切な評価では、変換後のプログラムを、明示された参照値および課題に適した誤差基準と比較する。ゼロ付近では、絶対誤差と相対誤差は異なる問いに答える。別の順序の方が高精度であっても、再現性のために決定的な順序が必要な場合がある。したがって、コンパイラの研究では、意味論上の許容、数値的品質、反復可能性を区別すべきである。緩和された言語オプションは特定の変更を許可するが、その変更が個別の科学的主張にとって許容可能であることを示すものではない。

翻訳検証には結果の状態を正直に示す必要がある

検証器は、モデル化された仮定の下で特定の変換を証明することも、反例を見つけることも、タイムアウトすることも、未対応の機能に遭遇することもある。これらの結果を、合格またはスキップの単一の集計にまとめるべきではない。タイムアウトは結果が得られていないことを意味し、変換が安全であるという証拠ではない。

有界な手法では、その限界も明示する必要がある。固定深さまで展開したループに関する結果は、それだけではすべての反復回数についての証明にはならない。逆に、他の構文要素には限界を設けるツールであっても、非有界の局所的な代数検査が有用な場合がある。レビューでは、どの証明義務が満たされ、どれが保留されたかを特定すべきである。Alive2を有界翻訳検証として位置付けることに価値があるのは、考え得るすべてのLLVMコンパイルの包括的証明を主張するのではなく、この範囲を明示しているからである。 [2]

性能比較は正しさを確認した後に始まる

書き換えが意味論上の事前条件を満たしても、そのコストは依然としてターゲットと周辺コードに依存する。ある命令を別の命令に置き換えると、依存関係の深さ、ベクトル化、レジスタ圧力、コード配置が変わる可能性がある。そのため、その命令を単独で測定するマイクロベンチマークは、アプリケーションのベンチマークと一致しない場合がある。

提案する研究では、各変種で同じ入力領域と正しさのオラクルを維持し、生成コードを調べ、想定用途を代表するワークロードを用いるべきである。コンパイラフラグと未定義動作に関する仮定は、一定に保つか、実験要因として明示的に扱わなければならない。一方の変種が制限された入力を仮定し、他方がすべての入力を扱う場合、比較にはその制限を強制するコストを含めるべきである。そうしなければ、報告される高速化の一部は、担う責任の変化を測定していることになる。

変換ごとにレビュー可能な成果物を残す

提案する最適化ごとに、ソース式とターゲット式、型とメモリのモデル、事前条件、詳細化関係、検証結果を保存する。少なくとも一つの境界テストと、不正であることが既知の類似した書き換えを一つ加え、ハーネスが検出感度を示せるようにする。数値的変換については、参照計算と誤差指標も保存する。

本稿の付録では、妥当な剰余算術の二倍化恒等式、不正な符号なし比較の書き換え、浮動小数点の再結合の証拠例に対して、このパターンを実装する。これらの例は、全体を精査できるよう意図的に小さくしてある。実際のIRの完全な意味論に代わるものではないが、性能に関する主張が意味を持つために必要な具体性の水準を示している。レビュー担当者は、どの仮定によって答えが変わるかを正確に確認できる。

結論：意味論は最適化の一部である

最適化の科学的価値は、保存された契約と、明示されたワークロードの下で測定された改善との組み合わせにある。報告から契約を取り除くと、意味の不確かな性能値だけが残る。ワークロードを取り除くと、正しいものの実用上の利点が不明な変換が残る。

符号なし算術と浮動小数点の証拠例は、機械表現をまたぐときに馴染み深い代数だけでは不十分な理由を示す。陽性対照は、表現レベルの精密な推論によって有用な変換を正当化できることを示す。コンパイラ全体の証明と翻訳検証は異なる種類の保証を与える。厳密な記述では、生成されたコードとともに、それらの範囲、未対応の事例、成果物との関係を提示する。

ローカルで実行済み · 限定された範囲

8ビット書き換えの全数検査とbinary64の反例

明示された算術式を対象とし、コンパイラのバイナリやソース言語の未定義動作モデルは含まない。

258件のアサーションが成功した。 これらの検査が妥当性を確認するのは、提示した例であり、引用したシステムではない。

{
  "bad_inputs": [
    255
  ],
  "float_results": [
    1.0,
    0.0
  ]
}

実行可能な全20例をダウンロード検査結果の全文を読む

明示された解析モデル

四つの式と明示的な仮定

構成された例 · 再現可能なデータ

定量的な論証を精査する

これらの曲線は、明示されたモデルから計算したものである。引用した研究の観測結果ではない。各図には数値データとベクター版が付属する。

CSVをダウンロードSVGソースをダウンロードPythonで再現する

CSVをダウンロードSVGソースをダウンロードPythonで再現する

どの証拠がどの問いに答えるのか

提案する検証プロトコル

これは提案段階の評価設計である。本番システムやハードウェアのベンチマークは行っていない。別途実行した有限モデルは、実行可能な検査の項に記録している。

1. 算術型、オーバーフローの振る舞い、観測可能な効果を記録する。
2. 同じ有限領域で、妥当な書き換えと意図的に不正な書き換えを検査する。
3. 反例を回帰テスト用の固定データとして保存する。
4. 検証器のタイムアウトと未対応の事例を未解決の結果として扱う。
5. 再結合を受け入れる前に、明示した参照値に対する数値誤差を測定する。
6. コンパイラのバージョン、フラグ、生成コード、ワークロードを記録し、等価な契約の下でベンチマークを行う。

一次資料が示すこと

本分析の限界

• ビットベクトル検査の対象は、インストールされたコンパイラではなく、八ビットの簡略化した式である。
• 浮動小数点の図はbinary64の振る舞いを仮定しており、コンパイラの実証的比較ではない。
• 本レビューは、現在のLLVMの意味論や、CompCertおよびAlive2のすべての機能を網羅しているわけではない。
• 有限テストがすべての型、言語、ビット幅に対して変換を証明するとは主張しない。

選定した三つの基礎的一次資料に焦点を絞った分析的レビューであり、独自の計算例を含む。2026までの文献を網羅するレビューや系統的レビューではない。資料へのアクセスと版に関する注記は参考文献とともに記録している。

結論を変え得る問い

1. どの事前条件が最適化を妥当なものにし、その条件はどこで強制されているか。
2. 緩和された数値的契約は、アプリケーションレベルの科学的結論を保存するか。
3. コンパイルとリンクの経路のうち、どの部分が検証結果の範囲外に残っているか。

参考文献

1. Xavier Leroy. Formal verification of a realistic compiler. Communications of the ACM (2009). 10.1145/1538788.1538814.
2. Nuno P. Lopes, Juneyoung Lee, Chung-Kil Hur et al.. Alive2: bounded translation validation for LLVM. Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation (2021). 10.1145/3453483.3454030.
3. C. Lattner, V. Adve. LLVM: a compilation framework for lifelong program analysis & transformation. International Symposium on Code Generation and Optimization, 2004. CGO 2004. (2004). 10.1109/cgo.2004.1281665.

資料[1]へのアクセス。 一次記録、要旨、アクセス可能な本文の一部を対象とし、全文や補足資料の網羅的監査ではない。

資料[2]へのアクセス。 一次記録、要旨、アクセス可能な本文の一部を対象とし、全文や補足資料の網羅的監査ではない。

資料[3]へのアクセス。 一次記録、要旨、アクセス可能な本文の一部を対象とし、全文や補足資料の網羅的監査ではない。

書誌情報はCrossrefと、出版社、著者、または機関の一次記録と照合した。以下の資料アクセスおよび版に関する注記にその範囲を示す。これは全文の網羅的監査ではない。

著者と来歴

Codex（AI）が執筆し、技術的な自己レビューを行った。参考文献は原研究の研究者を示し、分析的な構成と提案された評価設計は本稿に帰属する。

表紙はImageGenによる概念的イラストである。技術図は明示されたモデルまたは有限の例から計算されており、PythonとCSVを提供している。これらは、導入済み製品の測定や性能ベンチマークの再現ではない。

このローカル草稿には、独立した査読や学術誌への採択の記録はない。有界な実行可能例は明示された小規模モデルを検査するものであり、引用したシステムの形式的検証ではない。