第24回 入れ子の式 で泣く泣く見送ったアレをやっつけます！
枝葉の修正（1） ステップ実行の切り替え
先に枝葉っぽい部分を片付けます。
前回 ダンプ表示を間引きしてライフゲームの実行を高速化しましたが、 今回また、
- 確認用の小さなプログラムをステップ実行して命令レベルでの動作を確認
- 問題なければライフゲームを実行して壊れていないことを確認
という作業を繰り返すことになります。
そのたびに vgvm.rb を書き直すのはさすがに面倒だったため、
環境変数で切り替えられるようにしました。
--- a/vgvm.rb +++ b/vgvm.rb @@ -235,8 +235,14 @@ class Vm raise "Unknown operator (#{op})" end - dump_v2() if @step % 10 == 0 - # $stdin.gets if @step >= 600 + if ENV.key?("STEP") + dump_v2() + $stdin.gets + # $stdin.gets if @step >= 600 + else + dump_v2() if @step % 10 == 0 + end + # sleep 0.01 end end
- ダンプ表示の間引きのステップ数
- ステップ実行する場合にスキップするステップ数
あたりもついでに指定できるようにしたくなりますが、
とりあえず今必要なものだけということで
環境変数 STEP の有無によって切り替えるだけにしました。
ライフゲームを実行する場合は今までどおり
./run.sh gol.vgt.json
で、ステップ実行したい場合は
STEP= ./run.sh 39_nested_exp.vgt.json
のように頭に STEP= を付けて実行します。
枝葉の修正（2） push, pop の修正
今回、次の3つの操作が必要になるので先に片付けておきます。
push reg_a ... reg_a の値をスタックに push pop reg_a ... pop した値を reg_a にセット pop reg_b ... pop した値を reg_b にセット
--- a/vgvm.rb +++ b/vgvm.rb @@ -381,6 +381,8 @@ class Vm arg when String case arg + when "reg_a" + @reg_a when "bp" @bp when /^\[bp\-(\d+)\]$/ @@ -404,6 +406,10 @@ class Vm arg = @mem.main[@pc + 1] case arg + when "reg_a" + @reg_a = @mem.stack[@sp] + when "reg_b" + @reg_b = @mem.stack[@sp] when "bp" @bp = @mem.stack[@sp] else
本題
さて、枝葉が片付いたところでここからが本題です。
第24回 で
低レイヤを知りたい人のためのCコンパイラ作成入門＞スタックマシン
https://www.sigbus.info/compilerbook#%E3%82%B9%E3%82%BF%E3%83%83%E3%82%AF%E3%83%9E%E3%82%B7%E3%83%B3v1 を作った後で読みました。 「スタックマシン」の節に答えが載ってますね。
と書いた通り、必要なことは 「低レイヤを知りたい人のためのCコンパイラ作成入門」 で解説されてますので、 考え方についてはそちらを参照してください。 自分が改めて付け加えることはありませんね。ありがたや……。
まず、入れ子になっていない式の処理が壊れないことを確認しながら、 リファクタリングします。
確認用のコードを用意。
// 39_nested_exp.vgt.json ["stmts" , ["func", "main", [] , [ ["var", "a"] , ["set", "a", ["+", 1, 2]] ] ] ]
左項、右項をそれぞれ reg_a、 reg_b に直接セットしていた箇所を、
一度スタックを経由するように修正します。
まず他に影響を与えないように + だけ。
--- a/vgcg.rb +++ b/vgcg.rb @@ -141,8 +141,11 @@ def codegen_exp(fn_arg_names, lvar_names, exp) case operator when "+" - alines << " set_reg_a #{left}" - alines << " set_reg_b #{right}" + alines << " push #{left}" + alines << " push #{right}" + alines << " pop reg_b" + alines << " pop reg_a" + alines << " add_ab" when "*" alines << " set_reg_a #{left}"
関数呼び出しのときと同じように、 push と pop を同じ回数行っているのがポイントです。 ここに気をつけておけば、 スタックポインタがおかしくなることはないでしょう。 この後の工程でも この収支が狂わないように気をつけてやっていきます。
結果の渡し方については、
これまで
「何かしら処理したら結果を reg_a にセットする」
というルールで作ってきましたので、
そこから外れないようにします。
スタックマシンのエミュレーションとしては
結果がスタックトップに置かれてほしいところですが、
ひとまず「入れ子の式が書けるようにする」をゴールとして
先に進みます。
（あれこれやっていると記事が書き終わらないのです……あと前回からの差分も見にくくなるし……と言い訳しつつ）
10: reg_a(3) reg_b(2) reg_c(0) zf(0)
---- memory (main) ----
00 ["call", 5]
02 ["exit"]
03 ["label", "main"]
05 ["push", "bp"]
07 ["cp", "sp", "bp"]
10 ["sub_sp", 1]
12 ["push", 1]
14 ["push", 2]
16 ["pop", "reg_b"]
18 ["pop", "reg_a"]
20 ["add_ab"]
21 ["cp", "reg_a", "[bp-1]"]
pc => 24 ["cp", "bp", "sp"]
27 ["pop", "bp"]
29 ["ret"]
---- memory (stack) ----
38 0
39 0
40 0
41 0
42 0
43 0
44 2
45 1
sp => 46 3
bp => 47 49
48 2
49 0
1 + 2 の結果がローカル変数 a にセットされました。
よしよし、足し算は壊れていないですね。
特に不安はありませんが、 手間はかからないですし 念のためライフゲームも動かして壊れていないことを確認します。
codegen_exp() には他に 掛け算 * と
eq、neq があります。
これらも足し算と同じように、動作を確認しながら push + pop に書き換えていきます。
--- a/39_nested_exp.vgt.json +++ b/39_nested_exp.vgt.json @@ -4,7 +4,22 @@ , [ ["var", "a"] - , ["set", "a", ["+", 1, 2]] + // , ["set", "a", ["+", 1, 2]] + + // , ["set", "a", ["*", 2, 3]] + + // , ["set", "a", ["eq", 1, 1]] + // , ["_cmt", "等しい場合: 1 になること"] + + // , ["set", "a", ["eq", 1, 2]] + // , ["_cmt", "等しくない場合: 0 になること"] + + , ["set", "a", ["neq", 1, 1]] + , ["_cmt", "等しい場合: 0 になること"] + + , ["set", "a", ["neq", 1, 2]] + , ["_cmt", "等しくない場合: 1 になること"] + ] ]
--- a/vgcg.rb +++ b/vgcg.rb @@ -148,15 +148,21 @@ def codegen_exp(fn_arg_names, lvar_names, exp) alines << " add_ab" when "*" - alines << " set_reg_a #{left}" - alines << " set_reg_b #{right}" + alines << " push #{left}" + alines << " push #{right}" + alines << " pop reg_b" + alines << " pop reg_a" + alines << " mult_ab" when "eq" $label_id += 1 label_id = $label_id - alines << " set_reg_a #{left}" - alines << " set_reg_b #{right}" + alines << " push #{left}" + alines << " push #{right}" + alines << " pop reg_b" + alines << " pop reg_a" + alines << " compare" alines << " jump_eq then_#{label_id}" @@ -173,8 +179,11 @@ def codegen_exp(fn_arg_names, lvar_names, exp) $label_id += 1 label_id = $label_id - alines << " set_reg_a #{left}" - alines << " set_reg_b #{right}" + alines << " push #{left}" + alines << " push #{right}" + alines << " pop reg_b" + alines << " pop reg_a" + alines << " compare" alines << " jump_eq then_#{label_id}"
問題なさそうなので、 push left 、 push right を case の外に出して、 それぞれ 「左項の評価（のコード生成）が終わった直後」 「右項の評価（のコード生成）が終わった直後」 の位置に移動させます。
--- a/vgcg.rb +++ b/vgcg.rb @@ -122,6 +122,8 @@ def codegen_exp(fn_arg_names, lvar_names, exp) raise not_yet_impl("left", args[0]) end + alines << " push #{left}" + right = case args[1] when Integer @@ -139,17 +141,15 @@ def codegen_exp(fn_arg_names, lvar_names, exp) raise not_yet_impl("right", args[1]) end + alines << " push #{right}" + case operator when "+" - alines << " push #{left}" - alines << " push #{right}" alines << " pop reg_b" alines << " pop reg_a" alines << " add_ab" when "*" - alines << " push #{left}" - alines << " push #{right}" alines << " pop reg_b" alines << " pop reg_a" @@ -158,8 +158,6 @@ def codegen_exp(fn_arg_names, lvar_names, exp) $label_id += 1 label_id = $label_id - alines << " push #{left}" - alines << " push #{right}" alines << " pop reg_b" alines << " pop reg_a" @@ -179,8 +177,6 @@ def codegen_exp(fn_arg_names, lvar_names, exp) $label_id += 1 label_id = $label_id - alines << " push #{left}" - alines << " push #{right}" alines << " pop reg_b" alines << " pop reg_a"
というわけで、 「入れ子の式に対応させる修正のための準備」 が済みました。 ここからがほんとの本題。
まずは左項が入れ子の場合をやってみます。
--- a/39_nested_exp.vgt.json +++ b/39_nested_exp.vgt.json @@ -14,11 +14,19 @@ // , ["set", "a", ["eq", 1, 2]] // , ["_cmt", "等しくない場合: 0 になること"] - , ["set", "a", ["neq", 1, 1]] - , ["_cmt", "等しい場合: 0 になること"] - - , ["set", "a", ["neq", 1, 2]] - , ["_cmt", "等しくない場合: 1 になること"] + // , ["set", "a", ["neq", 1, 1]] + // , ["_cmt", "等しい場合: 0 になること"] + + // , ["set", "a", ["neq", 1, 2]] + // , ["_cmt", "等しくない場合: 1 になること"] + + // 左項が入れ子になっているパターン + , ["set", "a" + , ["*" + , ["+", 2, 3] + , 4 + ] + ] ] ]
(2 + 3) * 4 ですね。結果が 20 になれば OK。
左項の評価部分は今はこうなってますので、
left =
case args[0]
when Integer
args[0]
when String
case
when lvar_names.include?(args[0])
to_lvar_addr(lvar_names, args[0])
when fn_arg_names.include?(args[0])
to_fn_arg_addr(fn_arg_names, args[0])
else
raise not_yet_impl("left", args[0])
end
else
raise not_yet_impl("left", args[0])
end
ここに入れ子の子として式が来た場合の分岐を追加してやればよいでしょう。
--- a/vgcg.rb +++ b/vgcg.rb @@ -118,6 +118,9 @@ def codegen_exp(fn_arg_names, lvar_names, exp) else raise not_yet_impl("left", args[0]) end + when Array + alines += codegen_exp(fn_arg_names, lvar_names, args[0]) + "reg_a" else raise not_yet_impl("left", args[0]) end
はい、これだけ。
codegen_exp() が再帰的に呼び出されるようになりました。
15: reg_a(20) reg_b(4) reg_c(0) zf(0)
---- memory (main) ----
03 ["label", "main"]
05 ["push", "bp"]
07 ["cp", "sp", "bp"]
10 ["sub_sp", 1]
12 ["push", 2]
14 ["push", 3]
16 ["pop", "reg_b"]
18 ["pop", "reg_a"]
20 ["add_ab"]
21 ["push", "reg_a"]
23 ["push", 4]
25 ["pop", "reg_b"]
27 ["pop", "reg_a"]
29 ["mult_ab"]
30 ["cp", "reg_a", "[bp-1]"]
pc => 33 ["cp", "bp", "sp"]
36 ["pop", "bp"]
38 ["ret"]
---- memory (stack) ----
38 0
39 0
40 0
41 0
42 0
43 0
44 4
45 5
sp => 46 20
bp => 47 49
48 2
49 0
正しい結果になっています！ おー！
右項も同様に。
--- a/39_nested_exp.vgt.json +++ b/39_nested_exp.vgt.json @@ -20,11 +20,20 @@ // , ["set", "a", ["neq", 1, 2]] // , ["_cmt", "等しくない場合: 1 になること"] - // 左項が入れ子になっているパターン + // // 左項が入れ子になっているパターン + // , ["set", "a" + // , ["*" + // , ["+", 2, 3] + // , 4 + // ] + // ] + // ] + + // 右項が入れ子になっているパターン , ["set", "a" , ["*" - , ["+", 2, 3] , 4 + , ["+", 2, 3] ] ]
--- a/vgcg.rb +++ b/vgcg.rb @@ -140,6 +140,9 @@ def codegen_exp(fn_arg_names, lvar_names, exp) else raise not_yet_impl("right", args[1]) end + when Array + alines += codegen_exp(fn_arg_names, lvar_names, args[1]) + "reg_a" else raise not_yet_impl("right", args[1]) end
これもヨシ！
さらに、左右の項が両方とも入れ子になっているパターン、 2段以上の入れ子になっているパターンなどを確認しました。 問題なさそうです。
問題なさそうなので、gol.vgt.json を
入れ子の式に書き直しましょう！
--- a/gol.vgt.json +++ b/gol.vgt.json @@ -2,12 +2,16 @@ , ["func", "to_vi", ["w", "x", "y", "offset"] , [ - ["var", "yw"] - , ["set", "yw", ["*", "y", "w"]] - - , ["var", "vi"] // vram index - , ["set", "vi", ["+", "yw", "x"]] - , ["set", "vi", ["+", "vi", "offset"]] + ["var", "vi"] // vram index + , ["set", "vi" + , ["+" + , ["+" + , ["*", "y", "w"] + , "x" + ] + , "offset" + ] + ] , ["return", "vi"] ]
ローカル変数 yw が不要になり、
vi への再代入もなくすことができました。
ライフゲームを実行すると……問題ないですね！ よしよし。
次の箇所も入れ子の式にできます。
set文の 2番目の引数が配列だった場合は
codegen_exp() を呼び出すようになっているため、
vgcg.rb は修正不要です。
--- a/gol.vgt.json +++ b/gol.vgt.json @@ -44,13 +44,11 @@ , ["func", "adjust_index", ["width", "i"] , [ ["var", "adjusted"] - , ["var", "max_i"] - , ["set", "max_i", ["+", "width", -1]] , ["case" , [["eq", "i", -1] , ["_cmt", "下限を超えた場合"] - , ["set", "adjusted", "max_i"]] + , ["set", "adjusted", ["+", "width", -1]]] , [["eq", "i", "width"] , ["_cmt", "上限を超えた場合"] , ["set", "adjusted", 0]]
いいですね。不要な一時変数がなくなって ちょっとすっきりしました。
えーとあとは…… あとは無理して入れ子の式に書き直さなくてもいいかな……。
あれだけ悩んだのに、結局ライフゲームのために必要だったのは この 2箇所くらいなので、 やっぱり余計な先回りをせずに 一時変数にセットするように手で書く選択で正解でしたね。
というわけで、入れ子の式が使えるようになりました！
codegen_exp() のリファクタリングもやっておきたいですが、
長くなってきましたし、
ともかく入れ子の式を書けるようにするという目標は達成できましたので、
今回はここで切り上げます。
いやー、これでまた一段落ですね。年内に片付いてよかったよかった。
