[scheme]Scheme Compiler の勉強(18)

Scheme で Scheme を書く場合、簡単にテストデータが作れるのが嬉しい。
※現在作成中の勉強用 scheme コンパイラ（というのもおこがましいが）は、直接 LLVM IR を吐き出すプリミティブしかなく、そしてまだ任意の足し算すらできない。またプリミティブな手続きは全て引数１つ。

たとえば「0 に１を足してその結果についてまた１を足して、、、を１０回繰り返して結果が１０になること」などというテストは、以下のように fold と make-list を使うと手が楽だ。

gosh> (fold list 0 (make-list 10 '$fxadd1))
($fxadd1 ($fxadd1 ($fxadd1 ($fxadd1 ($fxadd1 ($fxadd1 ($fxadd1 ($fxadd1 ($fxadd1 ($fxadd1 0))))))))))
gosh> (run-compile (fold list 0 (make-list 10 '$fxadd1)))
#<undef>

で、いまの LLVM 用自作「コンパイラ」は、上の S式を「コンパイル」するときはひたすらに１を足す LLVM IR のコードを積み重ねていく。そのままだと冗長だけど、いったん llvm-as コマンドで中間コードのバイナリを生成し、opt コマンドで最適化して新しい中間コードのバイナリを作成し、さらに llc コマンドで最終的なアセンブラを出力すると下のように簡潔なものになっている。（※以下は make-list に 1000 を与えている。"4000" になっているのは、32bit の 2bit をタグに使っているためその分ずれているから）

	.globl	_scheme_entry
	.align	4
_scheme_entry:
	li r3, 4000
	blr

上は最終のアセンブラだけど、その一歩手前の、最適化された中間コードのバイナリも llvm-dis コマンドで参照できる。わたしの「コンパイラ」は3000行位の LLVM IR を出力しているので、それに比べれば随分コンパクト。

define i32 @scheme_entry() nounwind  {
entry:
	ret i32 4000
}

手続きが定義できるようになるまでには、この最適化された LLVM IR も最終のアセンブラも同時に簡単に参照できるように整備しておこう。gosh 環境から対話的にコンパイルしチェックを繰り返すようなイメージ。

定数畳み込み（constant folding）と定数伝播（constant propagation）
定数からなる式（例えば、"3 + 5"）をコンパイル時に計算結果（"8"）と置き換えてしまう。最近の言語処理系ではほとんど必ず行われる。
http://ja.wikipedia.org/wiki/コンパイラ最適化

『「最近の処理系ではほとんど必ず」だって？そんなのは「未来」のコンパイラには関係ないッ！他の誰か(LLVMとか)にお願いすればいいんだッ！！』と言いたいところだけども、残念ながらそんなに単純では無いはず。それでも、LLVM みたいな中間層には未来を感じるのは確か。コンピューターの歴史は中間層の歴史、と昔上司にならったなぁ。

Compilers: Backend to Frontend and Back to Front Again: 1.4 Conditional Expressions

if の実装、といっても、そもそも LLVM IR にはそんなに命令の種類が無いので、'br' を使えばいいと分かる。if だと条件を満たさないときのコードは実行してはいけないので、今までのように順番に命令を実行するだけでは駄目。そのために 'br' とラベルを使う。

http://llvm.org/docs/LangRef.html#identifiers を読む。ラベルも参照するときは % がつくのか。おっと、 unnamed variable なんて便利そうなものがあるよ。そのうち使えると奇麗かもしれない。

if のメイン部分はこんな感じ。

(define (emit-if expr)
  (let ((%if-test (unique-var))
	(%tmp (unique-var))
	(L_if-true (unique-label))
	(L_if-else (unique-label))
	(L_if-cont (unique-label)))
    (emit-expr (if-test expr))
    (emit "    ~a = load i32* %ret" %if-test) 
    ;; compare to #f 
    (emit "    ~a = icmp eq i32 ~a, ~a" %tmp %if-test bool_f)
    (emit "    br i1 ~a, label %~a, label %~a" %tmp L_if-else L_if-true)
    (emit "~a:" L_if-true)
    (emit-expr (if-then expr))
    (emit "    br label %~a" L_if-cont)
    (emit "~a:" L_if-else)
    (emit-expr (if-else expr))
    (emit "    br label %~a" L_if-cont)
    (emit "~a:" L_if-cont)))

gosh> (compile-program '(if #f 12 9))
define i32 @scheme_entry() nounwind {
entry:
    %ret = alloca i32
    store i32 47, i32* %ret
    %var128 = load i32* %ret
    %var129 = icmp eq i32 %var128, 47
    br i1 %var129, label %Label_80, label %Label_79
Label_79:
    store i32 48, i32* %ret
    br label %Label_81
Label_80:
    store i32 36, i32* %ret
    br label %Label_81
Label_81:
    %retval = load i32* %ret
    ret i32 %retval
}
#<undef>

gauche の disasm を使ってみると自作のコンパイラもどきの冗長さが際立つ。

gosh> (compile-program '(if #t (if 12 13 4) 17))
define i32 @scheme_entry() nounwind {
entry:
    %ret = alloca i32
    store i32 111, i32* %ret
    %var130 = load i32* %ret
    %var131 = icmp eq i32 %var130, 47
    br i1 %var131, label %Label_83, label %Label_82
Label_82:
    store i32 48, i32* %ret
    %var132 = load i32* %ret
    %var133 = icmp eq i32 %var132, 47
    br i1 %var133, label %Label_86, label %Label_85
Label_85:
    store i32 52, i32* %ret
    br label %Label_87
Label_86:
    store i32 16, i32* %ret
    br label %Label_87
Label_87:
    br label %Label_84
Label_83:
    store i32 68, i32* %ret
    br label %Label_84
Label_84:
    %retval = load i32* %ret
    ret i32 %retval
}
#<undef>
gosh> (disasm (lambda () (if #t (if 12 13 4) 17)))
main_code (name=#f, code=0xb5d58, size=13, const=0, stack=0):
args: #f
     0 CONST #t
     2 BF 11                    ; (if #t (if 12 13 4) 17)
     4 CONSTI(12) 
     5 BF 9                     ; (if 12 13 4)
     7 CONSTI(13) 
     8 RET 
     9 CONSTI(4) 
    10 RET 
    11 CONSTI(17) 
    12 RET 
#<undef>

でもともかくも tests-1.4-req.scm まで全テストが通っている。
p. 17 に and , or 、それから現在のコンパイラの非効率さについて。後でやるか飛ばすか。
次の 1.5 Binary Primitives はちょっと LLVM のことを調べないと進めない印象。

続く。

小まとめ

※"Compilers: Backend to Frontend and Back to Front Again" ばっかり見てたけど、"An Incremental Approach to Compiler Construction" の方が今の知識で読むと読みやすい。

	paper	わたしの勉強	メモ
Source Language	Scheme サブセット	Scheme サブセット	コンパイルする対象となる言語。
Implementation Language	Scheme (ChezScheme 7)	Scheme (gauche 0.8.8)	コンパイラを実装する言語。
Taget Architecture	Intel-X86	PowerPC(LLVM 2.3)(PowerBook G4)	コンパイラのターゲットとなるプラットフォーム。
	CISC	RISC-like	命令セット。
Help	gcc	llvm-gcc	困った時に助けを求める別のコンパイラ。

※元文書は、コンパイラーの学習者が具体的なマシン上で学習が進められるように、意図して Intel-X86 を設定。わたしは手元に Intel-X86 マシンが無いことと、 LLVM が楽しそう、という理由でいまのところ LLVM を設定、 LLVM のバックエンド（というらしい）として PowerPC。これにはメリットもデメリットもある。低レベル（マシンに近い）仮想マシンとはいえ、ほんもののマシンより使いやすい部分もあれば、逆に勉強を複雑にして具体的なマシンから遠くなっている、とも言える。

Compilers: Backend to Frontend and Back to Front Again: 1.5 Binary Primitives

ここからどうもターゲットマシンの影響を受けて教材通りに行かない気がしてきている。TODO