CommonLispアセンブラ上にスタック型言語(っぽいもの)
前回のCommonLispアセンブラを使って、アセンブラ上に簡単なスタック型言語(っぽいもの)を組み立てて、それを使ってフィボナッチ数を計算するプログラムを書くと、どのような感じになるかを試してみた。
cl-asmはバージョンを更新して0.0.2を使用*1。
0.0.1(前回)からの大きな変更点としては、ニモニック列をプログラムから操作しやすいように以下のような二つの機能を追加した。
;; 例示用のプログラム (cl-asm:execute '((:push %rbp) (:mov %rbp %rsp) (:push %rdi) (:push %rsi) (:push %rbx) ; 関数呼び出し時の定形処理 ;; 10 + 15 (:mov %eax 10) (:mov %ebx 15) (:add %eax %ebx) (:pop %rbx) (:pop %rsi) (:pop %rdi) (:pop %rbp) ; 関数から返る時の定形処理 :ret) (function int)) --> 25 ;;======================================================================= ;; 追加機能１: (:progn ...) ;; - 複数のニモニックを一つにまとめることが可能 ;; => 追加機能２(eval)と合わせることでニモニック内に任意の関数・変数を埋め込むことが可能 (cl-asm:execute '((:progn (:push %rbp) (:mov %rbp %rsp) (:push %rdi) (:push %rsi) (:push %rbx)) ; 関数呼び出し時の定形処理 ;; 10 + 15 (:progn (:mov %eax 10) (:mov %ebx 15) (:add %eax %ebx)) (:progn (:pop %rbx) (:pop %rsi) (:pop %rdi) (:pop %rbp)) ; 関数から返る時の定形処理 :ret) (function int)) --> 25 ;;======================================================================= ;; 追加機能２: eval ;; - 以下の二つ以外がニモニック列に表れた場合はevalを適用 ;; a: 組み込みの命令(car部がキーワードのリスト) ;; b: ラベル('&'で始まるシンボル) ;; 定形処理を関数にまとめる (defun save-registers () '(:progn (:push %rbp) (:mov %rbp %rsp) (:push %rdi) (:push %rsi) (:push %rbx))) (defun restore-registers () '(:progn (:pop %rbx) (:pop %rsi) (:pop %rdi) (:pop %rbp))) ;; 実行 (cl-asm:execute '((save-registers) ; レジスタ退避 ;; 10 + 15 (:mov %eax 10) (:mov %ebx 15) (:add %eax %ebx) (restore-registers) ; レジスタ復元 :ret) (function int)) --> 25
一応これで少しは、普通のlispプログラムっぽくアセンブリプログラムが書けるようになった。
スタック型言語
以下では、機能的に前々回とほぼ同等のスタック型言語(っぽいもの)をアセンブラ上に作っていく。
まずはデータスタック周りの補助関数を用意。(リターンスタックにはx86の通常のスタックを使用)
;; データスタック用の領域をヒープに確保 & 解放 ;; - スタックサイズは決め打ち ;; - スタックの先頭アドレスの保持にはRCXレジスタを使用 ;; (ちなみにRAX/RBXレジスタは、一時データ保持用に使用) ;; 確保 (defun ready-data-stack () '(:progn (:push %rax) (:push %rdi) ; レジスタ退避 (:mov %edi 102400) ; スタックサイズ (:mov %rax (:extern "malloc")) (:call %rax) ; malloc(102400) (:mov %rcx %rax) ; アドレスをRCXレジスタに保存 (:pop %rdi) (:pop %rax))) ; レジスタ復元 ;; 解放 (defun destroy-data-stack () '(:progn (:push %rax) (:push %rdi) ; レジスタ退避 (:mov %rdi %rcx) (:mov %rax (:extern "free")) (:call %rax) ; free(RCX) (:pop %rdi) (:pop %rax))) ; レジスタ復元 ;; アセンブラ用関数(マクロ)定義マクロ ;; これを使えば引数のシンボルのクォートが不要となり、使用時に(xxx '%eax)ではなく(xxx %eax)のように書ける (defmacro defop (name args &body body) `(defmacro ,name ,args (list 'quote (locally ,@body)))) ;; データスタック用のアクセサ定義 (defop @ds-get (dst index) `(:mov ,dst (:refd %rcx ,(* index -4)))) ; getter (defop @ds-set (index src) `(:mov (:refd %rcx ,(* index -4)) ,src)) ; setter (defop @ds-inc (&optional (n 1)) `(:add %rcx ,(* 4 n))) ; 先頭を進める (defop @ds-dec (&optional (n 1)) `(:sub %rcx ,(* 4 n))) ; 先頭を戻す ;; ついでに全ての定期処理をまとめて生成してくれるマクロを用意 (defmacro body (&rest mnemonics) `'(,(save-registers) ; レジスタ退避 ,(ready-data-stack) ; データスタック用意 ,@mnemonics ; 本体処理 ,(destroy-data-stack) ; データスタック破棄 ,(restore-registers) ; レジスタ復元 :ret)) (cl-asm:execute (body (:mov %eax 10)) (function int)) --> 10
残りはひたすらスタック型言語用の命令(関数)を定義。
;; srcをスタックの先頭に追加 (defop @push (src) `(:progn (@ds-inc) (@ds-set 0 ,src))) ;; スタックの先頭を取り出しdstに格納 (defop @pop (dst) `(:progn (@ds-get ,dst 0) (@ds-dec))) ;; スタックの先頭から二つを要素を取り出し、dst1とdst2に格納 (defop @pop2 (dst1 dst2) `(:progn (@ds-get ,dst1 0) (@ds-get ,dst2 1) (@ds-dec 2))) ;; スタック[index1]とスタック[index2]の要素を交換 (defop @swap-impl (index1 index2) `(:progn (@ds-get %eax ,index1) (@ds-get %ebx ,index2) (@ds-set ,index1 %ebx) (@ds-set ,index2 %eax))) ;; スタックの先頭二つの要素を交換 (defop @swap () '(@swap-impl 0 1)) ;; スタックの先頭要素を複製 (defop @dup () `(:progn (@ds-get %eax 0) (@push %eax))) ;; スタックの先頭要素の破棄 (defop @drop () '(@ds-dec)) ;; スタックの二番目の要素を先頭に複製 (defop @over () `(:progn (@ds-get %eax 1) (@push %eax))) ;; スタックの先頭三つの要素をローテーション (defop @rot () `(:progn (@swap-impl 2 0) (@swap-impl 1 2))) ;; スタックの先頭二つを使った加算 (defop @add () `(:progn (@pop2 %ebx %eax) (:add %eax %ebx) (@push %eax))) ;; スタックの先頭二つを使った減算 (defop @sub () `(:progn (@pop2 %ebx %eax) (:sub %eax %ebx) (@push %eax))) ;; スタックの先頭二つの要素が等しいか (真なら非ゼロがスタックトップに格納) (defop @eql () `(:progn (@pop2 %ebx %eax) (:cmp %eax %ebx) (:mov %eax 0) (:sete %al) (@push %eax))) ;; スタックの先頭要素が二番目の要素よりも小さいか (真なら非ゼロがスタックトップに格納) (defop @less () `(:progn (@pop2 %ebx %eax) (:cmp %eax %ebx) (:mov %eax 0) (:setl %al) (@push %eax))) ;; スタックの先頭が真(非ゼロ)なら、指定位置に遷移 (defop @jump-if (pos) `(:progn (@pop %eax) (:cmp %eax 0) (:jne ,pos))) ;; 指定位置に遷移 (defop @jump (pos) `(:jmp ,pos)) ;; 関数呼び出し (defop @call (pos) `(:call ,pos)) ;; 関数からの復帰 (defop @return () :ret) ;; int値を生成してスタックトップに積む (defop @int (n) `(@push ,n))
実行例。
(cl-asm:execute (body (@push 10) (@push 15) (@add) (@pop %eax)) ; 結果取り出し (function int)) --> 25
フィボナッチ数
フィボナッチ数計算プログラム。
薄いラップの割にはスタック型言語っぽい見た目になっているように思う。
(cl-asm:execute (body (@push %edi) ; 引数取得 (@call &fib-beg) ; (fib 10) (@jump &finish) &fib-beg (@dup) (@int 2) (@less) (@jump-if &fib-end) ; (if (< arg 2) ... ....) (@dup) (@int 2) (@sub) (@call &fib-beg) ; a = (fib (- arg 2)) (@swap) (@int 1) (@sub) (@call &fib-beg) ; b = (fib (- arg 1)) (@add) ; (+ a b) &fib-end (@return) &finish (@pop %eax)) (function int int) 10) --> 55
*1:いずれにせよ、まだまだ実用に堪えるものにはかなりほど遠いけど
