An Incremental Approach to Compiler Construction (2006)
October 23, 2023An Incremental Approach to Compiler Constructionは、コンパイラの学習を目的としたSchemeのコンパイラの実装方法の解説である。 コンパイラの実装に使用する言語もSchemeであり、コンパイラは、Intel-x86のアセンブリコードを出力する。 プログラマが普段使用しているコンパイラは、教育用の教材としてのコンパイラと比べて複雑であり、学習には向かない。 この商用と学習用のコンパイラの溝を埋めるために、Schemeの仕様の大部分を満たす規模のコンパイラの実装例が示されている。 実装手順は24ステップからなり、最後のステップまで実装しなくても、各ステップにある実装を完了すれば、コンパイラが正常に動作するように実装することができる。
実装するコンパイラは、引数xで渡されたSchemeのコードのアセブリ言語のステップを関数emitで出力する関数compile-programである。
アセンブリコードは、Cから関数として呼びだせる。
C言語の呼出元が返り値の型を判定できるように、アセンブリコードは、下位ビットに型情報をふくめた値を返す。
最下位2ビットが00であれば、fixnum, 00001111であれば文字, 0011111であれば真偽値, 00101111は空のリストであること意味する。
以下のコードは、xが整数であれば、整数を2ビット左シフトした値をEAXレジスタに格納する。
(define (compile-program x)
(define (immediate-rep x)
(cond
((integer? x) (shift x fixnum-shift))
...))
(emit "movl $~a, %eax" (immediate-rep x))
(emit "ret"))
また、以下は、返り値の型ごとに処理を分岐するCの実装である。
#include <stdio.h>
#define fixnum_mask 3
#define fixnum_tag 0
#define fixnum_shift 2
...
int main(int argc, char** argv){
int val = scheme_entry();
if((val & fixnum_mask) == fixnum_tag){
printf("%d\n", val >> fixnum_shift);
} else if(val == empty_list){
printf("()\n");
} ...
return 0;
}
let式の束縛変数はスタックのインデックスにコンパイルされ、インデックスの示すスタックの位置に変数の値が格納される。
以下の関数は、siがスタックのインデックス、rhsとlhsがそれぞれ値と変数をとりだす関数として、let式をコンパイルする。
(define (emit-expr x si env)
(cond
((immediate? x) ...)
((variable? x)
(emit "movl ~a(%esp), %eax" (lookup x env)))
((let? x)
(emit-let (bindings x) (body x) si env))
...))
(define (emit-let bindings body si env)
(let f ((b* bindings) (new-env env) (si si))
(cond
((null? b*) (emit-expr body si new-env))
(else
(let ((b (car b*)))
(emit-expr (rhs b) si env)
(emit "movl %eax, ~a(%esp)" si)
(f (cdr b*)
(extend-env (lhs b) si new-env)
(- si wordsize)))))))
ペア、ベクタ、文字列などの1つのマシンワードで保存できないデータは、ヒープに保存される。
fixnumと同様に、下位3ビットでデータの型を保存し、下位3ビットが0になる8の倍数から始まるヒープ上の空間にデータを保存する。
以下は、ペアを001ビットで表現し、ヒープのアドレスをESIレジスタで指定する(cons 10 20)を保存するアセンブリコードである。
movl $40, 0(%esi)
movl $80, 4(%esi)
movl %esi, %eax
orl $1, %eax
addl $8, %esi
compile-programが受理できる関数の構文を導入する。
以下のlvarは関数名、codeは関数の本体に対応する。
<Prog> ::= (labels ((lvar <LExpr>) ...) <Expr>)
<LExpr> ::= (code (var ...) <Expr>)
<Expr> ::= immediate
| var
| (let ((var <Expr>) ...) <Expr>)
コンパイラは、まず、lvarごとにユーニークなラベルを出力し、let式のコンパイルの実装にあるenvのような環境をラベルごとに用意する。
次に以下の図のようにリターンアドレス、ローカルアドレス、実引数をスタック上に配置する。
論文中より図を引用しました。