vm変換器作成中 - mas454の日記

いま、コンピュータシステムの理論と実装７章のVM変換器を作成しています。
VM自体はこの本の中では実装しませんが(この本のサイトからダウンロードできます。)、
VM用の言語から前の章で作成したアセンブラ言語に変換するプログラムを作成します。

この章の中で2段階に分けてVM変換器を作成していくのですが、
いま１段階目の変換する部分のみ完成しています。
　例えばaddという足し算をする命令は、

@SP //スタックポインタ
M=M-1
A=M
D=M
A=A-1
M=M+D

のようなプログラムに変換します。

足し算をするadd命令や引き算をするsub命令等は、そのまま対応する命令がアセンブラにも
あるのですが、==や>のような比較演算を直接行う命令がこのアセンブラにはありません。
なのでジャンプ命令を利用して実装しました。
例えば、等しいかどうか判定するeq命令は、

//戻ってくるアドレスを保存
@$1
D=A
@R13
M=D

@SP
M=M-1
A=M
D=M
A=A-1
D=M-D //x - y
@true
D;JEQ
@false
0;JMP
($1);ここまでがeq命令


(true)
@SP
A=M-1
M=-1
@R13
A=M
0;JMP

(false)
@SP
A=M-1
M=0
@R13
A=M
0;JMP

のように変換します。

@true
D;JEQ

このD;JEQはDの値が0ならジャンプするという命令で、
上の場合Dの値が0なら、(true)にジャンプします。
(true)から始まる部分でスタックにtrueを表す-1を積んでいます。(このVMはスタックマシンです。)
その後R13に保存されているアドレスに戻ります。
上のプログラムの場合($1)に戻ります。

以下がeqを変換するプログラムです。

(define (vm-eq)
  (let1 r (t-f-label)
	(string-append
	 ;戻ってくるアドレスをR13に保存
	 "@" r "\n"
	 "D=A\n"
	 "@R13\n"
	 "M=D\n"
	 
	 ;ここからメイン
	 "@SP\n"
	 "M=M-1\n"
	 "A=M\n"
	 "D=M\n"
	 "A=A-1\n"
	 "D=M-D\n" ;x - y
	 "@TRUE\n"
	 "D;JEQ\n"
	 "@FALSE\n"
	 "0;JMP\n"
	 "(" r ")\n" ;ここに戻る
	 )))

t-f-label関数は戻りアドレス用のラベルを返します。
上の例だと$1のことで、t-f-label呼び出すたびに$2、$3、$4、・・・と数字の部分が増えていきます。

以下がプログラムの全体です。

(define t-f-label-n 0)

(define (count)
  (set! t-f-label-n (+ t-f-label-n 1)))

(define (t-f-label)
  (let1 label (string-append "$" (number->string t-f-label-n))
	(count)
	label))

(define (push_constant n)
  (string-append "@" (number->string n)
		 "\nD=A"
		 "\n@SP"
		 "\nA=M"
		 "\nM=D"
		 "\n@SP"
		 "\nM=M+1\n"))

(define vm-neg
  (string-append "@SP\n"
		 "A=M-1\n"
		 "M=-M\n"))
(define vm-not
  (string-append "@SP\n"
		 "A=M-1\n"
		 "M=!M\n"))

(define vm-add
  (string-append "@SP\n"
		 "M=M-1\n"
		 "A=M\n"
		 "D=M\n"
		 "A=A-1\n"
		 "M=M+D\n"))
(define vm-sub
  (string-append "@SP\n"
		 "M=M-1\n"
		 "A=M\n"
		 "D=M\n"
		 "A=A-1\n"
		 "M=M-D\n"))
(define vm-and
  (string-append "@SP\n"
		 "M=M-1\n"
		 "A=M\n"
		 "D=M\n"
		 "A=A-1\n"
		 "M=M&D\n"))
(define vm-or
  (string-append "@SP\n"
		 "M=M-1\n"
		 "A=M\n"
		 "D=M\n"
		 "A=A-1\n"
		 "M=M|D\n"))


(define (vm-eq)
  (let1 r (t-f-label)
	(string-append
	 ;戻ってくるアドレスをR13に保存
	 "@" r "\n"
	 "D=A\n"
	 "@R13\n"
	 "M=D\n"
	 
	 ;ここからメイン
	 "@SP\n"
	 "M=M-1\n"
	 "A=M\n"
	 "D=M\n"
	 "A=A-1\n"
	 "D=M-D\n" ;x - y
	 "@TRUE\n"
	 "D;JEQ\n"
	 "@FALSE\n"
	 "0;JMP\n"
	 "(" r ")\n" ;ここに戻る
	 )))
(define (vm-gt)
  (let1 r (t-f-label)
	(string-append
	 ;戻ってくるアドレスをR13に保存
	 "@" r "\n"
	 "D=A\n"
	 "@R13\n"
	 "M=D\n"
	 
	 ;ここからメイン
	 "@SP\n"
	 "M=M-1\n"
	 "A=M\n"
	 "D=M\n"
	 "A=A-1\n"
	 "D=M-D\n" ;x - y
	 "@TRUE\n"
	 "D;JGT\n" ;Dが0より大きければジャンプ
	 "@FALSE\n"
	 "0;JMP\n"
	 "(" r ")\n" ;ここに戻る
	 )))

(define (vm-lt)
  (let1 r (t-f-label)
	(string-append
	 ;戻ってくるアドレスをR13に保存
	 "@" r "\n"
	 "D=A\n"
	 "@R13\n"
	 "M=D\n"
	 
	 ;ここからメイン
	 "@SP\n"
	 "M=M-1\n"
	 "A=M\n"
	 "D=M\n"
	 "A=A-1\n"
	 "D=M-D\n" ;x - y
	 "@TRUE\n"
	 "D;JLT\n" ;Dが0より小さければジャンプ
	 "@FALSE\n"
	 "0;JMP\n"
	 "(" r ")\n" ;ここに戻る
	 )))

;スタックにtrue(-1)を積む 	 
(define vm-true
  (string-append "(TRUE)\n"
                 "@SP\n"
		 "A=M-1\n"
		 "M=-1\n"
		 "@R13\n"
		 "A=M\n"
		 "0;JMP\n"))

;スタックにfalse(0)を積む
(define vm-false
  (string-append "(FALSE)\n"
                 "@SP\n"
		 "A=M-1\n"
		 "M=0\n"
		 "@R13\n"
		 "A=M\n"
		 "0;JMP\n"))

(define (test)
  (print (string-append
	  "@start\n"
	  "0;JMP\n"
	  vm-true
	  vm-false
	  "(start)\n"
	  (push_constant 20)
	  (push_constant 20)
	  (vm-eq))))