コンパイラ

コンパイラ

執筆済 コンピュータ言語処理系

ソースコードを別の言語（多くは機械語）に翻訳する。

構成#

[フロントエンド]  [字句解析] → [構文解析] → [意味解析]
        ↓ 中間表現 (IR)
[ミドルエンド]    最適化
        ↓
[バックエンド]    命令選択 → レジスタ割り当て → コード生成

フロントエンドとバックエンドの分離#

中間表現を挟むことで、 M 言語 × N アーキテクチャの組み合わせが M+N の実装で済む。

LLVM が広く使われるのは この分離を徹底しているため。

主な最適化#

最適化 内容
定数畳み込み 2 * 3 → 6
共通部分式除去 同じ計算を 1 回に
デッドコード除去 使われない計算を消す
インライン展開 関数呼び出しを本体で置き換える
ループ不変式の移動 ループ外に出す
ループ展開 分岐回数を減らす
自動ベクトル化 SIMD 命令にまとめる

インライン展開は他の最適化を可能にする点で特に重要。 関数の境界が消えると、定数伝播や不要コード除去が働くようになる。

SSA 形式#

各変数がただ 1 回だけ代入される中間表現。

x = 1      →   x1 = 1
x = x + 2  →   x2 = x1 + 2

「この変数の値はどこで決まったか」が一意になるので、 データフロー解析が大幅に単純になる。 現代のコンパイラのほとんどが採用している。

最適化の限界#

  • 観測できる振る舞いは変えられないことが制約になる
  • 浮動小数点は結合則が成り立たないため、順序を変えられない （-ffast-math はこの保証を捨てる）
  • エイリアス解析（2 つのポインタが同じ場所を指すか）が 一般に不可能なため、多くの最適化が保守的になる

C の restrict、Rust の所有権は、 このエイリアス情報をコンパイラに伝える仕組みでもある。

参考文献#

  • Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools, 2nd ed. Pearson, 2006.
  • Chris Lattner, Vikram Adve. LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation. CGO, 2004. https://doi.org/10.1109/CGO.2004.1281665
  • Ron Cytron et al. Efficiently computing static single assignment form and the control dependence graph. ACM TOPLAS 13(4), 1991. https://doi.org/10.1145/115372.115320