レジスタマシンとスタックマシン
こちらで見かけた話題・・・
Lua の VM は 4.0 でのスタックマシンから 5.0 でレジスタマシンに変更されたらしく、その時の理由が Lua: papers の "The implementation of Lua 5.0" の 第 7 節 にいくつか書いてありました。そこで書いてあることには・・・、の前に Lua 5.0 の「レジスタ」の仕様を簡単にまとめるておくと、こんな風になってます。
富豪的です。その分、レジスタ割り当てを考える必要がないので、コンパイラのコード生成が大変／実装が難しい、ということはないです。なにせ構文木をそのまま深さ優先探索でたどるだけでコードが出てきます。引数の問題、状態の保存の処理は call と return 命令に全部集約されているので、直接スタックを操作する命令も不要です。とゆーか、ジャンプ時のスタック長の整合性とか考えなくていい分スタックマシンより実装楽かもという気もします。
話を戻して、"The implementation of Lua 5.0" に書いてあったレジスタマシン化の利点ですが、
レジスタマシンはコピーが少ない
"a = b + c" という式を考えると、'a','b','c' をそれぞれの変数のローカル変数番号としたとき、スタックマシンだと
getlocal 'b' # 'b'の値をスタックにpush getlocal 'c' # 'c'の値をスタックにpush add # スタックポインタ2つ減らして和を push setlocal 'a' # スタックトップの値をpopして'a'に書き込み
こう、都合 3 回か 4 回かのコピーが発生しますが、レジスタなら
add 'a' 'b' 'c'
1 回。そして、特に Lua の場合、変数の「値」は型を表すタグ(4Byte)とポインタかdoubleのunion(8Byte)で計12Byteもある構造体なので、あんまり何回もコピーしたくないという事情があるそうな。「ポインタの下位ビットを利用してタグを云々〜」みたいなトリッキーな技を避けたいと思うと動的な言語の VM は同じ問題を抱えがち。
レジスタマシンの命令は word align しやすい
要は命令を固定長にしやすい。スタックマシンだと、「コードサイズが小さい」利点を保つために命令が可変長になってしまいがち（add 命令は 1 Byte で済むけど、getlocal や jmp 命令、定数ロード命令等々は、ローカル変数インデックスやジャンプ距離のように余計な情報がいるので 1 Byte では足りない）
