2009-03-25
1.9 ヒープ確保 (2) ペア
- 1.9のテストでbeginが使われている。これまでどおりemit-exprに追加してってもいいんだけど、煩雑になっていくのでdefine-special-formみたいのを追加しよう。と思って作業し始めたが、他の一般の関数を定義するdefine-primitiveでも評価された引数が渡されるわけじゃなくて元の字面が渡ってくるので、beginでもそのまま使える。
- でそうすると末尾か末尾じゃないかで関数を2つ用意するのが煩雑になるので関数への引数として渡すように変更。
- あと、beginは任意長の引数を受け取りたいのだけど、define-syntaxでrestパラメータを受け取るマクロの定義の仕方がわからなかったので、define-macroで書き換え。
- letの本体に複文が使われているので、対応
- ペア関係の関数(cons, car, cdr, set-car!, set-cdr!, pair?)は実装、ベクターと文字列は今後
トラックバック - http://cadr.g.hatena.ne.jp/mokehehe/20090325
2009-03-22
1.9 ヒープ確保
- ペアやクロージャやシンボルや文字列はヒープに確保する
- タグビットで区別
- ペアの要素にアクセスする際に、pair-tag分引いた位置にアクセスすれば望みの要素が得られる
- 目から鱗。ヒープを指す値のタグビットは0じゃないと面倒なことになると思い込んでいた。
- テストでbeginを使ってる
1.8 末尾呼び出しの最適化による繰り返し
- 末尾かどうか
- プロシジャの本体は末尾
- let式が末尾にあるなら、letの本体は末尾
- 条件式(if test conseq altern)が末尾にあるなら、conseqとalternも末尾
- 他の式は末尾じゃない
- 末尾がプロシジャ呼び出しの場合、フレームを「シフト」させ、プロシジャをコールではなくジャンプにできる
- 3impのVMで同じことをしていたけど、アセンブラレベルでこれをやってしまうとは目から鱗
- この操作はC言語レベルではできないよな
- gccが自動的にやってくれればいいんだけど、メモリコピーのペナルティと引換だからな
- 後はテストを通せという、投げっぱなしジャーマン(先生ひどい…)
- 二重再帰による偶奇判定5000000できた!末尾呼び出し最適化すごい!
- Exercise 2 は、末尾呼び出し時にローカル変数領域の上の領域に引数を積んでいって後でシフトするんじゃなく、使われないローカル変数領域に直接書き込む、とかいうことかなぁ?難しいなぁ。
1.7 プロシジャ
- letrec で関数定義して、呼び出せるようにする
- testsがprocedureと関係ない、binary primitivesになっている
- tests-1.8の後半#!eofの後にあるproceduresのテストを試してみる
- 関数呼び出しが(app func args ...)の形じゃなくて(func args ...)
- でもdeeply nested proceduresのテストの方はappがついてる
- emit-lambda は、最後に"ret"を出力しないと関数呼び出しから戻れないんじゃ?
- emit-app中のemit-argumentsで、引数の計算結果をsiに格納してない
- emit-lambda中のsiが-wordsizeから始めているが、0からでいい?
- どうやらsiの値が、次に使うスペースを指してるぽい(- wordsizeスタート)
- $fxzero? -> fxzero?
- $fxsub1 -> fxsub1
- deeply nested procedures で Segmentation fault
- 1.5 Binary Primitives でスタックを導入したときにスタックサイズを16Kx4しか取ってなかったのに、10000回とか5000000回とか再帰させてる
- これは次の章の末尾呼び出しの最適化のチェック用か
関数が使えるようになったのでフィボナッチのテストができる:
[(letrec ((fib (lambda (n) (if (fx< n 2) n (fx+ (fib (fx- n 1)) (fib (fx- n 2))))))) (fib 35)) => "9227465\n"]
$ time ./stst.exe 9227465 real 0m0.426s user 0m0.424s sys 0m0.000s
速い!
出力されたアセンブリコード:
.text .global scheme_entry .type scheme_entry, @function scheme_entry: movl %esp, %ecx movl 4(%esp), %esp call L_scheme_entry movl %ecx, %esp ret .text .global fib .type fib, @function fib: movl -4(%esp), %eax cmpl $8, %eax jge L_0 movl -4(%esp), %eax jmp L_1 L_0: movl -4(%esp), %eax subl $4, %eax movl %eax, -12(%esp) subl $4, %esp call fib addl $4, %esp movl %eax, -8(%esp) movl -4(%esp), %eax subl $8, %eax movl %eax, -16(%esp) subl $8, %esp call fib addl $8, %esp addl -8(%esp), %eax L_1: ret L_scheme_entry: movl $140, %eax movl %eax, -8(%esp) call fib ret
Cで書いてgcc -O2 --omit-frame-pointerで出したものが 0.233s なので約1.8倍。
- Scheme Compiler の勉強(24) - 比較 - cranebirdの日記 cranebirdさんのllvmでのフィボナッチ出力結果
トラックバック - http://cadr.g.hatena.ne.jp/mokehehe/20090322
2009-03-20
1.5 二項演算子
- わざわざ自分でメモリ確保して、Cで使ってるスタックとは別領域を使うのか
- espをいじらずにオフセットを自分で管理
- fx+ の定義の中で、sc は si の間違い?
- emit-expr で渡ってくるsiはスタックの底だから、自分が使うテンポラリ領域は(- si wordsize)で、左右の値に渡すsiはそれぞれ(- si wordsize)、(- si (* 2 wordsize))じゃないか?
(define-primitive (fx+ si arg1 arg2) (emit-expr (- si wordsize) arg1) (emit " movl %eax, ~s(%esp)" (- si wordsize)) (emit-expr (- si (* 2 wordsize)) arg2) (emit " addl ~s(%esp), %eax" (- si wordsize)))
- 数値のタグビットが00なので、そのまま加減算できるのは楽でいい
- 以前$つきで出てきたfxlognotが、1.5のテストでは$なし…
- 書き換えなきゃいけない箇所多すぎ…
1.4 条件式
- ラベルを作って分岐
- Exercise 2: and, orを追加しろ
- Exercise 3: if の条件式に (fxzero? 0) とか使うといったん #t か #f を得た後にそれが #f か判定するのが無駄。なんとかしろ。
- primitive関数の登録を、値を返す関数と述語を返す関数で分ける。述語を返す関数は真の判定までして、条件式として使う場合はフラグで直接分岐、値として取り出す場合はseteで#tか#fに戻すようにする。
- 条件式にandやorを使った場合に対応できてない。値として使う場合と条件式として使う場合の2種類用意すればいけるけど、メンドイので後回し。
「Compilers: Backend to Frontend and Back to Front Again」を読んでみる
Compilers: Backend to Frontend and Back to Front Again
cranebirdさんのブログも参考にしつつ。cranebirdさんはllvm用に吐き出してるけど、オリジナルどおりx86で。
An Incremental Approach to Compiler Constructionも内容的にはほとんど同じ?どちらも入門用とかステップバイステップとかうたってるわりにはかなりハードな内容。Incremental~に比べるとこちらのほうがまだ読みやすい気がする。
tests-driver.scmを動かす
- テスト用パッケージのtests-driver.scmをGaucheで動かすのに躓く
- ここは Scheme Compiler の勉強(0) - cranebirdの日記を見れば解決
- それでも、tests-driver.scmには同じ関数の定義が2つあるもの(test-with-string-output, run-compile, execute, get-string)や、どこからも使われてない関数(runtime-file, input-filter, build-program, show-compiler-output)があって気持ち悪い
- Cygwinユーザなので、実行ファイル名に勝手に「.exe」がついてしまうのでそれ用の対応
1.1 整数
- 論文中のソースを写経
- とかいって本当にそのまま写してしまうと(error ---)とかあるので、そういうところは適宜いいように変更していかないとだめ
- アセンブラとの名前のルールが違うのか、「scheme_entry」だとC側から呼べないので、前にアンダーバーをつけて「_scheme_entry」に変更する
- 宣言が違うのか、.typeは「.def _scheme_entry; .scl 2; .type 32; .endef」にする
1.2 即値
- tests-driver.scm でランタイム用に使うCのソースファイル名がruntime.c決め打ちになっているが、それだと1.1のものとは共用できない。なのでtests-driver.scmを修正してtest-allにランタイムのCソースファイル名を与えるように変更
- immediate-repの中身がfixnum?しか書いてなくてあとは自分で補えという。かなりストイックだな。ランタイムのほうもprint_ptrがほとんど書いてない
1.3 単項プリミティブ
- Gaucheにputprop, getpropがない。ハッシュテーブルで代用
- define-primitive の define-syntax はそのままで動いた
- 論文中に出てくるのは「fxadd1」だけど、テストで使われてる関数名は「$fxadd1」とか、統一されてない
- ほとんどの関数が省略されていてヒントすら書かれてない。x86のアセンブラもよく知らないもんだから、かなり辛い。わからないものはCでテストコードを書いて、「gcc -S --omit-frame-pointer test.c」でアセンブリコードを吐き出して参考にすべし
- 実行時にエラーを出す方法がわかってないので、$fxlognot(整数のビット反転)で整数かどうか判定してない
成果物はhttp://svn.coderepos.org/share/lang/scheme/backend-to-frontendへ。かなりハードな内容だけど、x86アセンブラとかやったことなくてもこんなに簡単に生成できるんだー、というのが結構楽しい。
トラックバック - http://cadr.g.hatena.ne.jp/mokehehe/20090320
ネイティブコンパイラを少しずつ作るというアイディアはとても楽しいのに、細かいところが不足しているのが惜しいですよねぇ。
内容は非常にハードですが、テストコードがついていて正しいかどうかチェックがちゃんとできるのがよいですね!