一般にコンパイルとは、ある高水準言語のプログラムを、より低水準な言語に変換することです。たとえば、二つの非負整数の最大公約数を求める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つです。
これらのギャップを埋めるために、MinCamlでは
といった処理を順番に行います。以下では、そのような変換や各種最適化について説明していきます。