コンパイラの方針

一般にコンパイルとは、ある高水準言語のプログラムを、より低水準な言語に変換することです。たとえば、二つの非負整数の最大公約数を求めるMinCaml関数

let rec gcd m n =
if m = 0 then n else
if m <= n then gcd m (n - m) else
gcd n (m - n)

は、以下のようなSPARCアセンブリにコンパイルされます。

gcd.7:
cmp %i2, 0
bne be_else.18
nop
mov %i3, %i2
retl
nop
be_else.18:
cmp %i2, %i3
bg ble_else.19
nop
sub %i3, %i2, %i3
b gcd.7
nop
ble_else.19:
sub %i2, %i3, %o5
mov %i3, %i2
mov %o5, %i3
b gcd.7
nop

これは一見すると、ものすごいギャップです。MinCamlコンパイラでは適切な中間言語を設定し、単純な変換を順番に適用していくことにより、このギャップを一つずつ埋めていきます。MinCamlとSPARCアセンブリの主なギャップは次の5つです。

1. 型。MinCamlには型があり、型チェックが行われますが、アセンブリにはそのような仕組みがありません。
2. ネストした式。たとえばMinCamlでは1+2-(3+(4-5))のように、いくらでも複雑な式を書くことができますが、アセンブリでは一つの命令につき一つの演算しかできません。
3. ネストした関数定義。MinCamlでは
   let rec make_adder x =
   let rec adder y = x + y in
   adder in
   (make_adder 3) 7
   のように関数の中で別の関数を定義できますが、アセンブリではトップレベルの「ラベル」しか使用できません。
4. MinCamlには組や配列などのデータ構造がありますが、アセンブリにはありません。
5. MinCamlではいくつでも変数を使用できますが、アセンブリには有限のレジスタしかありません。

これらのギャップを埋めるために、MinCamlでは

1. 型推論
2. K正規化
3. クロージャ変換
4. 仮想マシンコード生成
5. レジスタ割り当て

といった処理を順番に行います。以下では、そのような変換や各種最適化について説明していきます。

次へ進む