コンパイラの方針

 

一般にコンパイルとは、ある高水準言語のプログラムを、より低水準な言語に変換することです。たとえば、二つの非負整数の最大公約数を求める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コンパイラでは適切な中間言語を設定し、単純な変換を順番に適用していくことにより、このギャップを一つずつ埋めていきます。MinCamlSPARCアセンブリの主なギャップは次の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. レジスタ割り当て

 

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

 

次へ進む