中間表現
一般に、あるプログラミング言語で書かれたソースコードと、コンパイラが成果物として出力する目的コードには抽象度に大きな隔たりがあります。
例を挙げると、1 + 2 - 3のような単純な数式も、push 1; add 2; sub 3;のような形式に変換する必要があります。
このギャップを一気に埋めるのはとてもつらいため、多くのコンパイラでは中間表現というアイディアを採用しています。
例えば、HaskellのコンパイラGHCは、抽象構文木以外に、大きく分けてCore,Std,C--の3つの中間表現を使っています。
CのコンパイラGCCも、GIMPLE、RTLといった中間表現を用いています。
中間表現を用いるもう一つのメリットは、コンパイラの内部構造のモジュール化です。
中間表現を採用することで、ソースコードをASTに変換し意味検査を行うフロントエンド、中間表現に変換し最適化を行うミドルエンド、中間表現から目的コードへの変換を行うバックエンドに分割できます。
中間表現の種類と性質
この記事では、数ある中間表現を大きく「命令型」「関数型」の2つに分けて紹介します。
この区分は何らかの合意にもとづくものでも厳密なものでもなく、「ALGOLっぽい雰囲気」「MLっぽい雰囲気」程度の主観的なものです。
中間表現には、異なる歴史的経緯を辿って似たような形式にたどり着いたものがいくつか存在します。
これらの対比、あるいは歴史的に連続したものの比較をわかりやすくする目的でこの区分を採用しました。
ここで紹介する中間表現は、実際にはソース言語に由来する拡張を追加したり、複数の手法を合わせて利用されるものも含まれます。
命令型
3番地コード
典型的な3番地コードの命令はx := y op zの形式で表現されます。
例えば、
a = 2 + b * 2 / c
は、一時変数を追加して
t1 = b * 2
t2 = t1 / c
a = 2 + t2
のように変換されます。
制御構文を含むプログラムは、無条件ジャンプと条件付きジャンプを使用してより機械語に近い形に変換されます。
例えば、
a = 0
for (i = 0; i < 10; i++) {
a += i;
}
は
a = 0
i = 0
L1: if i < 10 goto L2
a = a + i
i = i + 1
L2:
のように変換されます。
最も単純な中間表現の一つで、他の多くの中間表現でもベースに3番地コードを採用しています。
CFG 制御フローグラフ
TODO: 書く
基本ブロック
TODO: 書く
SSA 静的単一代入形式
SSAは、すべての変数が唯一の定義をもつ中間表現です。
例えば、
a = 1
a = 2
b = a + 2
のようなコードがあったとき、一行目のa = 1が消去できることは明らかです。
しかし、手続きとしてこの処理を行うためには、変数がどこで再代入され、どこで使用されているのかを解析する必要があります。
SSAに変換すると、
a_1 = 1
a_2 = 2
b_1 = a_2 + 2
のようなコードになるため、a_1が使用されていないことがより簡単に分かります。
TODO: より複雑な例、φ関数について書く
データフロー、制御フローの解析や最適化アルゴリズムをより単純にできるため、
多くのコンパイラで採用されています。
また、最近のコンパイラではLLVMが広く使われていますが、これもSSAを採用しています。
RTL
TODO: 書く
関数型
この節で紹介する中間表現の多くはλ計算がベースとなっています。
この記事で使用するλ計算は、以下のような構文で定義される、let式をもつものです。
TERM := <identifier>
| TERM TERM
| "λ" <identifier>+ "." TERM
| "let" <identifier> "=" TERM "in" TERM
また、いつもどおり関数適用は左結合、λ抽象はカリー化されているものとします。
CPS 継続渡しスタイル
Schemerにはおなじみのアレです。
関数を評価するとき、結果を変数に代入するのではなく、次の処理を表す関数を引数として与える形式を、継続渡しスタイルと呼びます。
fib (+ 4 (- 10 2))
==>
(- 10 2 (λx.
(+ 4 x (λy.
(fib y k)))))
制御構造が陽に示される、すべての変数が一度だけ宣言されるなど、SSAと似た性質をもつため、関数型言語のコンパイラが中間表現として採用している事があります。(SML/NJなど)
K正規形
TODO: 書く
A正規形
TODO: 書く
関連する話題
- LLVM
- 制御フロー解析、データフロー解析
参考文献
- 最新コンパイラ構成技法
- Compiling with Continuations
TODO: 参考文献の追加
折を見て追記していきます。