vm2gol v2 製作メモ(20) 値を返却してローカル変数に代入 / return, call_set文



関数呼び出しができて、 ローカル変数が使えるようになって、 引数も渡せるようになりました。

あと関数まわりは返り値をどうにかすれば一通り必要なものが揃います。


今回は次の2つのステップに分けます。

  • 値を返すだけ
  • 返された値を(呼び出し元の)ローカル変数にセットする。

ではやっていきましょう。

値を返すだけ

まずはこれをコンパイルします。

// 20_return.vgt.json

["stmts"

, ["func", "main"
  , []
  , [
      ["call", "fn_sub"]
    ]
  ]

, ["func", "fn_sub"
  , []
  , [
      ["return", 12]
    ]
  ]

]

値を返すのは「reg_a に値をセットして ret」すればよいので、 これは簡単ですね。

※参考: (14) 複数の引数を渡す / スタックオーバーフロー対策 / 返り値

["return", {返却する値}]

という構文を追加して、修正します。

--- a/vgcg.rb
+++ b/vgcg.rb
@@ -52,6 +52,9 @@ def codegen_func_def(rest)
 
       lvar_pos = lvar_names.index(lvar_name) + 1
       alines << "  cp #{val} [bp-#{lvar_pos}]"
+    when "return"
+      val = stmt_rest[0]
+      alines << "  set_reg_a #{val}"
     else
       raise not_yet_impl("stmt_head", stmt_head)
     end

簡単ですね。

結果はこうなります。 fn_sub() から戻った直後の状態。

$ ./run.sh 20_return.vgt.json 

(略)

================================
reg_a(12) reg_b(0) reg_c(0) zf(0)
---- memory (main) ----
      00   ["call", 5]
      02   ["exit"]
      03 ["label", "main"]
      05   ["push", "bp"]
      07   ["cp", "sp", "bp"]
      10   ["call", 22]
pc => 12   ["add_sp", 0]
      14   ["cp", "bp", "sp"]
      17   ["pop", "bp"]
      19   ["ret"]
      20 ["label", "fn_sub"]
      22   ["push", "bp"]
      24   ["cp", "sp", "bp"]
      27   ["set_reg_a", 12]
      29   ["cp", "bp", "sp"]
      32   ["pop", "bp"]
      34   ["ret"]
---- memory (stack) ----
         39 0
         40 0
         41 0
         42 0
         43 0
         44 0
         45 47
         46 12
sp bp => 47 49
         48 2
         49 0

reg_a に返り値がセットされています。

というわけで、単純な返却はこれで OK。

返り値をローカル変数に代入

次に、返り値をローカル変数に代入します。

["set", "{ローカル変数名}", ["call", "fn_sub"]]

set 構文を改造してこんな感じでローカル変数にセットするとかっこいいかな? というのをまずは考えたのですが、 set の2番めの引数が即値か関数呼び出しかで分岐して……とやっていくと 複雑になりそうな気がして(そうでもない?)、 call_set という専用の構文を新たに追加することにしました。

こうです:

[
  "call_set"
, "{ローカル変数名}"
, [
    "{呼び出す関数名}"
  , {引数1}
  , {引数2}
  , ...
  ]
]

今見ると、内側の括弧をなくして

[
  "call_set"
, "{ローカル変数名}"
, "{呼び出す関数名}"
, {引数1}
, {引数2}
, ...
]

とした方が call の構文に近くて良かったかも…… という気もしますが、うーんまあいいか (適当)。

vgtコードを用意して

// 20_call_set.vgt.json

["stmts"

, ["func", "main"
  , []
  , [
      ["var", "a"]
    , ["call_set", "a", ["fn_sub"]]
    ]
  ]

, ["func", "fn_sub"
  , []
  , [
      ["return", 12]
    ]
  ]

]

call_set 文の処理を追加します。

--- a/vgcg.rb
+++ b/vgcg.rb
@@ -33,6 +33,17 @@ def codegen_func_def(rest)
       }
       alines << "  call #{fn_name}"
       alines << "  add_sp #{fn_args.size}"
+    when "call_set"
+      lvar_name, fn_temp = stmt_rest
+      fn_name, *fn_args = fn_temp
+      fn_args.reverse.each {|fn_arg|
+        alines << "  push #{fn_arg}"
+      }
+      alines << "  call #{fn_name}"
+      alines << "  add_sp #{fn_args.size}"
+
+      lvar_pos = lvar_names.index(lvar_name) + 1
+      alines << "  cp reg_a [bp-#{lvar_pos}]"
     when "var"
       lvar_names << stmt_rest[0]
       alines << "  sub_sp 1"

call の処理をコピペしてちょこっと直して、 最後に cp reg_a [bp-N] を追加した形ですね。 関数の返り値は reg_a にセットすることにしているので、コピー元は reg_a 固定です。

動かしてみます。

================================
reg_a(12) reg_b(0) 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   ["call", 27]
      14   ["add_sp", 0]
      16   ["cp", "reg_a", "[bp-1]"] ... 返り値をローカル変数 a に代入
pc => 19   ["cp", "bp", "sp"]
      22   ["pop", "bp"]
      24   ["ret"]
      25 ["label", "fn_sub"]
      27   ["push", "bp"]
      29   ["cp", "sp", "bp"]
      32   ["set_reg_a", 12]
      34   ["cp", "bp", "sp"]
      37   ["pop", "bp"]
      39   ["ret"]
---- memory (stack) ----
         38 0
         39 0
         40 0
         41 0
         42 0
         43 0
         44 47
         45 14
sp    => 46 12 ... ローカル変数 a に代入された
   bp => 47 49
         48 2
         49 0

fn_sub() から main() に戻ってローカル変数 a に返り値を代入した直後です。 いいですね!

これで、関数まわりで必要そうなものがひととおり (といってもほんとに必要最低限ですが)整備できました!



vm2gol v2 製作メモ(19) 関数に引数を渡す



今回は関数の引数をやります。こんな感じで進めましょう。

  • 引数を1個渡す
  • 渡した引数をローカル変数に代入
  • 引数を2個渡してローカル変数に代入

引数を1個渡す

これを動かします。

// 19_func_arg.vgt.json

["stmts"

, ["func", "main"
  , []
  , [
      ["call", "fn_sub", 34]  // 引数 34 を渡す
    ]
  ]

, ["func", "fn_sub"
  , ["arg1"]  // 引数を arg1 として受け取る
  , [
    ]
  ]

]

call文を変更して、3個目以降の要素として引数を渡すようにしてみます。

["call", "{関数名}", 引数1, 引数2, ...]

アセンブリではサブルーチンに引数を渡すときどうやってたか、 ちょっとおさらい。

こんな感じでしたね。

  • call の前に引数を逆順で push して、
  • 呼び出し先のサブルーチンでは bp+N で参照する
  • サブルーチンから戻ったときに add_sp でスタックポインタを戻す

ということは、引数が1個のときは次のようなアセンブリコードに変換されてほしい。

# 略

label main
  push 34 # 引数を push
  call fn_sub
  add_sp 1 # sp を調整

label fn_sub
  # bp+N で参照

call の前の push と call の後の add_sp を 追加で出力すればよさそうです。

まずはハードコーディングで。

--- a/vgcg.rb
+++ b/vgcg.rb
@@ -27,7 +27,9 @@ def codegen_func_def(rest)
     case stmt_head
     when "call"
       fn_name = stmt_rest[0]
+      alines << "  push 34"
       alines << "  call #{fn_name}"
+      alines << "  add_sp 1"
     when "var"
       lvar_names << stmt_rest[0]
       alines << "  sub_sp 1"

コンパイルすると期待するアセンブリコードが出力され、問題なさそうです。 単に2行追加されるだけですからね。


ではハードコーディングした部分を書き換えていきましょう。

push に渡すのは引数の内容なので、どうすればいいかというと……

["call", "fn_sub", 34] // 引数 34 を渡す

「3個目以降を引数とする」としたので、 call文の配列の 3つ目の要素を使えばいいですね。

add_sp に渡す 1 は単に引数の個数を与えてやればいいので、 特に難しくなさそうです。

修正します。

--- a/vgcg.rb
+++ b/vgcg.rb
@@ -26,10 +26,10 @@ def codegen_func_def(rest)
     stmt_head, *stmt_rest = stmt
     case stmt_head
     when "call"
-      fn_name = stmt_rest[0]
-      alines << "  push 34"
+      fn_name, *fn_args = stmt_rest
+      alines << "  push #{fn_args[0]}"
       alines << "  call #{fn_name}"
-      alines << "  add_sp 1"
+      alines << "  add_sp #{fn_args.size}"
     when "var"
       lvar_names << stmt_rest[0]
       alines << "  sub_sp 1"

run.sh で実行して確認。

================================
reg_a(0) reg_b(0) reg_c(0) zf(0)
---- memory (main) ----
      00   ["call", 5]
      02   ["exit"]
      03 ["label", "main"]
      05   ["push", "bp"]
      07   ["cp", "sp", "bp"]
      10   ["push", 34]
      12   ["call", 24]
      14   ["add_sp", 1]
      16   ["cp", "bp", "sp"]
      19   ["pop", "bp"]
      21   ["ret"]
      22 ["label", "fn_sub"]
      24   ["push", "bp"]
      26   ["cp", "sp", "bp"]
pc => 29   ["cp", "bp", "sp"]
      32   ["pop", "bp"]
      34   ["ret"]
---- memory (stack) ----
         36 0
         37 0
         38 0
         39 0
         40 0
         41 0
         42 0
         43 0
sp bp => 44 47
         45 14
         46 34 ... bp+2 の位置に arg1 の値がセットされている
         47 49
         48 2
         49 0

よしよし。

渡した引数をローカル変数に代入

渡した引数は使わないと意味がありません。 次は引数を参照してローカル変数に値をセットしてみましょう。

--- a/19_func_arg.vgt.json
+++ b/19_func_arg.vgt.json
@@ -10,6 +10,8 @@
 , ["func", "fn_sub"
   , ["arg1"]  // 引数を arg1 として受け取る
   , [
+      ["var", "a"]
+    , ["set", "a", "arg1"]
     ]
   ]

とりあえず実行してみると……

$ ./run.sh 19_func_arg.vgt.json 

(略)

================================
reg_a(0) reg_b(0) reg_c(0) zf(0)
---- memory (main) ----
      00   ["call", 5]
      02   ["exit"]
      03 ["label", "main"]
      05   ["push", "bp"]
      07   ["cp", "sp", "bp"]
      10   ["push", 34]
      12   ["call", 24]
      14   ["add_sp", 1]
      16   ["cp", "bp", "sp"]
      19   ["pop", "bp"]
      21   ["ret"]
      22 ["label", "fn_sub"]
      24   ["push", "bp"]
      26   ["cp", "sp", "bp"]
      29   ["sub_sp", 1]
pc => 31   ["cp", "arg1", "[bp-1]"]
      34   ["cp", "bp", "sp"]
      37   ["pop", "bp"]
      39   ["ret"]
---- memory (stack) ----
         35 0
         36 0
         37 0
         38 0
         39 0
         40 0
         41 0
         42 0
sp    => 43 0
   bp => 44 47
         45 14
         46 34
         47 49
         48 2
         49 0

vgvm.rb:235:in `copy': Not yet implemented ("copy src") ("arg1") (RuntimeError)
        from vgvm.rb:149:in `block in start'
        from vgvm.rb:126:in `loop'
        from vgvm.rb:126:in `start'
        from vgvm.rb:330:in `<main>'

ふむ……。


現時点ではこのようなアセンブリコードが出力されています。

# 略

label fn_sub
  push bp
  cp sp bp

  # 関数の処理本体
  sub_sp 1
  cp arg1 [bp-1] … 問題の箇所

  cp bp sp
  pop bp
  ret

VM(CPU)がこれを見て、 「コピー元が arg1 となってるけど arg1 ってなんやねん」 となってるわけですね。 ごもっとも。 VMちゃんにも分かる形にしてあげないと。

arg1 というのは関数呼び出しで渡された引数の名前なので、 これが [bp+2] となるように変換できればよさそうです。

ローカル変数のときは

lvar_pos = lvar_names.index(lvar_name) + 1
alines << "  cp #{src_val} [bp-#{lvar_pos}]"

のようにして [bp-N] の形にしていましたが、 同じようなやり方でいけるんじゃないでしょうか。

--- a/vgcg.rb
+++ b/vgcg.rb
@@ -10,6 +10,7 @@ def codegen_func_def(rest)
   alines = []
 
   fn_name = rest[0]
+  fn_arg_names = rest[1]
   body = rest[2]
 
   alines << ""
@@ -35,7 +36,18 @@ def codegen_func_def(rest)
       alines << "  sub_sp 1"
     when "set"
       lvar_name = stmt_rest[0]
-      val = stmt_rest[1]
+
+      val =
+        case
+        when stmt_rest[1].is_a?(Integer)
+          stmt_rest[1]
+        when fn_arg_names.include?(stmt_rest[1])
+          fn_arg_pos = fn_arg_names.index(stmt_rest[1]) + 2
+          "[bp+#{fn_arg_pos}]"
+        else
+          raise not_yet_impl("set val", stmt_rest)
+        end
+
       lvar_pos = lvar_names.index(lvar_name) + 1
       alines << "  cp #{val} [bp-#{lvar_pos}]"
     else

動かしてみます。

================================
reg_a(0) reg_b(0) reg_c(0) zf(0)
---- memory (main) ----
      00   ["call", 5]
      02   ["exit"]
      03 ["label", "main"]
      05   ["push", "bp"]
      07   ["cp", "sp", "bp"]
      10   ["push", 34]
      12   ["call", 24]
      14   ["add_sp", 1]
      16   ["cp", "bp", "sp"]
      19   ["pop", "bp"]
      21   ["ret"]
      22 ["label", "fn_sub"]
      24   ["push", "bp"]
      26   ["cp", "sp", "bp"]
      29   ["sub_sp", 1]
      31   ["cp", "[bp+2]", "[bp-1]"]
pc => 34   ["cp", "bp", "sp"]
      37   ["pop", "bp"]
      39   ["ret"]
---- memory (stack) ----
         35 0
         36 0
         37 0
         38 0
         39 0
         40 0
         41 0
         42 0
sp    => 43 34 ... [bp-1] ローカル変数 a
   bp => 44 47
         45 14
         46 34 ... [bp+2] 引数 arg1
         47 49
         48 2
         49 0

["set", "a", "arg1"] を実行した直後の状態です。 うまく動いてますね。


「実際のコンピュータでもメモリからメモリへのコピーってできるんだっけ?」 というとこが気になりますが、 ここはいったんできるということにして進めます。 あとで確認するかも。

なんとなれば、レジスタを経由させて

cp arg1 reg_a
cp reg_a a

とすれば回避できそうなどと考えつつ、とにかく進めます。

引数を2個渡す

さて、引数の参照部分もクリアできたので、 2個以上の引数でも動くようにしましょう。

vgtコードはこう。

// 19_func_args.vgt.json

["stmts"

, ["func", "main"
  , []
  , [
      ["call", "fn_sub", 34, 56] // 引数 34, 56 を渡す
    ]
  ]

, ["func", "fn_sub"
  , ["arg1", "arg2"] // 引数を arg1, arg2 として受け取る
  , [
      ["var", "a"]
    , ["set", "a", "arg1"]
    , ["var", "b"]
    , ["set", "b", "arg2"]
    ]
  ]

]

call文を変換している部分が今どうなっているかというと、

    when "call"
      fn_name, *fn_args = stmt_rest
      alines << "  push #{fn_args[0]}"
      alines << "  call #{fn_name}"
      alines << "  add_sp #{fn_args.size}"

こうなっていて、 fn_args[0] だけを push しています。 ここを複数にしてやればよくて、ただし逆順に push する点に気をつける、と。

修正します。

--- a/vgcg.rb
+++ b/vgcg.rb
@@ -28,7 +28,9 @@ def codegen_func_def(rest)
     case stmt_head
     when "call"
       fn_name, *fn_args = stmt_rest
-      alines << "  push #{fn_args[0]}"
+      fn_args.reverse.each {|fn_arg|
+        alines << "  push #{fn_arg}"
+      }
       alines << "  call #{fn_name}"
       alines << "  add_sp #{fn_args.size}"
     when "var"

これだけですね。動かします。

================================
reg_a(0) reg_b(0) reg_c(0) zf(0)
---- memory (main) ----
      00   ["call", 5]
      02   ["exit"]
      03 ["label", "main"]
      05   ["push", "bp"]
      07   ["cp", "sp", "bp"]
      10   ["push", 56]
      12   ["push", 34]
      14   ["call", 26]
      16   ["add_sp", 2]
      18   ["cp", "bp", "sp"]
      21   ["pop", "bp"]
      23   ["ret"]
      24 ["label", "fn_sub"]
      26   ["push", "bp"]
      28   ["cp", "sp", "bp"]
      31   ["sub_sp", 1]
      33   ["cp", "[bp+2]", "[bp-1]"]
      36   ["sub_sp", 1]
      38   ["cp", "[bp+3]", "[bp-2]"]
pc => 41   ["cp", "bp", "sp"]
      44   ["pop", "bp"]
      46   ["ret"]
---- memory (stack) ----
         33 0
         34 0
         35 0
         36 0
         37 0
         38 0
         39 0
         40 0
sp    => 41 56 ... b
         42 34 ... a
   bp => 43 47
         44 16
         45 34 ... arg1
         46 56 ... arg2
         47 49
         48 2
         49 0

["set", "b", "arg2"] を実行した直後。 いいですね!

というわけで今回は引数渡しと、呼び出し先での参照ができるようになりました!!



vm2gol v2 製作メモ(18) ローカル変数の宣言と代入 / var, set文



どうすれば「本棚の左端から36番目の本を取って」と言う代わりに「広辞苑を取って」と言えるようになるでしょうか? コンピュータが名前とモノの対応表を持てばよいのです。

コーディングを支える技術――成り立ちから学ぶプログラミング作法』 p85


今回はローカル変数の宣言と代入をやります。

アセンブリをやっていたときはループ、条件分岐、 それからサブルーチン〜という順番でやっていました。 それとは違う順番になっていますが、 特に意図したものではなく、次にやることを気分で適当に決めていたためです。 )

vgtコード:

// 18_local_var.vgt.json

["stmts"
, ["func", "main"
  , []
  , [
      ["var", "a"] // ← これ!
    ]
  ]
]

ローカル変数の宣言のために、

["var", "{ローカル変数名}"]

という構文を追加します (func に var と来るとちょっと GO言語っぽいですね)。

期待するアセンブリコード出力:

  call main
  exit

label main
  push bp
  cp sp bp

  # 関数の処理本体
  sub_sp 1 # ← これが加わる

  cp bp sp
  pop bp
  ret

これだけなら楽勝ですね。 codegen_func_def()case の分岐を1つ増やすだけ。

--- a/vgcg.rb
+++ b/vgcg.rb
@@ -25,6 +25,8 @@ def codegen_func_def(rest)
     when "call"
       fn_name = stmt_rest[0]
       alines << "  call #{fn_name}"
+    when "var"
+      alines << "  sub_sp 1"
     else
       raise not_yet_impl("stmt_head", stmt_head)
     end

宣言するだけでは意味がないので、変数に値をセットしてみましょう。

またまた文法を拡張して、こんどは変数に値を代入する

["set", "{ローカル変数名}", {セットしたい値}]

という構文を追加します。

vgtコードの方にも追加。

--- a/18_local_var.vgt.json
+++ b/18_local_var.vgt.json
@@ -3,6 +3,7 @@
   , []
   , [
       ["var", "a"]
+    , ["set", "a", 12]
     ]
   ]
 ]

ちなみに、var a = 12; のように、 宣言と同時に値を代入する構文は用意しませんでした。 varset を使うことで同等のことがすでにできているので、 さっさと次に進もうと考えたためです。

( ただ、ちょっとだけとはいえ煩雑ではあったので、 利便性のために追加しておいても良かったかなという気もします。 そんなに難しくなさそうですし。 )


で、(1個目の)ローカル変数への値のセットは、アセンブリでは cp 12 [bp-1] のように変換されてほしいので、そのように修正します。

参考: (15) ローカル変数 / sub_sp

var と同じように codegen_func_def() の分岐に追加します (ひとまず [bp-1] はハードコーディングで……)。

--- a/vgcg.rb
+++ b/vgcg.rb
@@ -27,6 +27,10 @@ def codegen_func_def(rest)
       alines << "  call #{fn_name}"
     when "var"
       alines << "  sub_sp 1"
+    when "set"
+      lvar_name = stmt_rest[0]
+      val = stmt_rest[1]
+      alines << "  cp #{val} [bp-1]"
     else
       raise not_yet_impl("stmt_head", stmt_head)
     end

アセンブリコードに変換してみましょう。

$ ruby vgcg.rb 18_local_var.vgt.json 
  call main
  exit

label main
  push bp
  cp sp bp

  # 関数の処理本体
  sub_sp 1      # ローカル変数を宣言(格納場所を確保)
  cp 12 [bp-1]  # ローカル変数に値を代入(確保した場所に cp)

  cp bp sp
  pop bp
  ret

よさそうですね。 run.sh で実行すると……

vgvm.rb:233:in `copy': Not yet implemented ("copy src") (12) (RuntimeError)
        from vgvm.rb:149:in `block in start'
        from vgvm.rb:126:in `loop'
        from vgvm.rb:126:in `start'
        from vgvm.rb:328:in `<main>'

えーっとこれは…… 即値は cp 命令のコピー元として使えないようになってますね。 VM を修正します。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -219,6 +219,8 @@ class Vm
   def copy(arg1, arg2)
     src_val =
       case arg1
+      when Integer
+        arg1
       when "reg_a"
         @reg_a
       when "sp"

あらためて実行すると……こんどは大丈夫。

================================
reg_a(0) reg_b(0) 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   ["cp", 12, "[bp-1]"]
pc => 15   ["cp", "bp", "sp"]
      18   ["pop", "bp"]
      20   ["ret"]
---- memory (stack) ----
         38 0
         39 0
         40 0
         41 0
         42 0
         43 0
         44 0
         45 0
sp    => 46 12 ... ローカル変数にセットした値
   bp => 47 49
         48 2
         49 0

set文が動きました!! めでたしめでたし。


めでたく動いたので、ハードコーディングした部分をいい感じにしましょう。 ここをいい感じにすると 2個目以降のローカル変数も使えるようになるはず。

vgtコード:

// 18_local_vars.vgt.json

["stmts"
, ["func", "main"
  , []
  , [
      ["var", "a"]
    , ["set", "a", 12]  // [bp-1] にセットされてほしい

    , ["var", "b"]
    , ["set", "b", 34]  // [bp-2] にセットされてほしい
    ]
  ]
]

上のコメントに書いているように、 1個目の引数 a[bp-1] 、 2個目の引数 b[bp-2] に値がセットされるように変換したい。

変数名から「その変数が何番目に宣言されたか」が分かればよいので、 何かしらのマッピング情報を用意すればいいでしょう。

マッピングってことはハッシュかな、と一瞬考えましたが、 何番目かが分かればいいだけなので、 ハッシュじゃなくて配列を用意して、 変数が出現した(宣言された)順番に追加しとけばいいんじゃないでしょうか。

それでやってみましょう。

--- a/vgcg.rb
+++ b/vgcg.rb
@@ -19,6 +19,9 @@ def codegen_func_def(rest)
 
   alines << ""
   alines << "  # 関数の処理本体"
+
+  lvar_names = []
+
   body.each {|stmt|
     stmt_head, *stmt_rest = stmt
     case stmt_head
@@ -26,11 +29,13 @@ def codegen_func_def(rest)
       fn_name = stmt_rest[0]
       alines << "  call #{fn_name}"
     when "var"
+      lvar_names << stmt_rest[0]
       alines << "  sub_sp 1"
     when "set"
       lvar_name = stmt_rest[0]
       val = stmt_rest[1]
-      alines << "  cp #{val} [bp-1]"
+      lvar_pos = lvar_names.index(lvar_name) + 1
+      alines << "  cp #{val} [bp-#{lvar_pos}]"
     else
       raise not_yet_impl("stmt_head", stmt_head)
     end
$ ruby vgcg.rb 18_local_vars.vgt.json 
  call main
  exit

label main
  push bp
  cp sp bp

  # 関数の処理本体
  sub_sp 1
  cp 12 [bp-1]
  sub_sp 1
  cp 34 [bp-2]

  cp bp sp
  pop bp
  ret

うまくいったようです!

================================
reg_a(0) reg_b(0) 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   ["cp", 12, "[bp-1]"]
      15   ["sub_sp", 1]
      17   ["cp", 34, "[bp-2]"]
pc => 20   ["cp", "bp", "sp"]
      23   ["pop", "bp"]
      25   ["ret"]
---- memory (stack) ----
         37 0
         38 0
         39 0
         40 0
         41 0
         42 0
         43 0
         44 0
sp    => 45 34 ... 2個目のローカル変数
         46 12 ... 1個目のローカル変数
   bp => 47 49
         48 2
         49 0

2個目のローカル変数 b に値をセットした直後の様子。 いい感じです!


これができたら、main から呼び出した先の関数でも 同じようにローカル変数が使えるようになってるんじゃないでしょうか。

調子に乗って試してみましょう。

vgtコード:

// 18_local_vars_call.vgt.json

["stmts"

, ["func", "main"
  , []
  , [
      ["var", "a"]
    , ["set", "a", 12]
    , ["var", "b"]
    , ["set", "b", 34]
    , ["call", "fn_sub"]
    ]
  ]

, ["func", "fn_sub"
  , []
  , [
      ["var", "a"]
    , ["set", "a", 56]
    , ["var", "b"]
    , ["set", "b", 78]
    ]
  ]

]

fn_sub() でローカル変数 b に値がセットされた直後の状態:

================================
reg_a(0) reg_b(0) 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   ["cp", 12, "[bp-1]"]
      15   ["sub_sp", 1]
      17   ["cp", 34, "[bp-2]"]
      20   ["call", 30]
      22   ["cp", "bp", "sp"]
      25   ["pop", "bp"]
      27   ["ret"]
      28 ["label", "fn_sub"]
      30   ["push", "bp"]
      32   ["cp", "sp", "bp"]
      35   ["sub_sp", 1]
      37   ["cp", 56, "[bp-1]"]
      40   ["sub_sp", 1]
      42   ["cp", 78, "[bp-2]"]
pc => 45   ["cp", "bp", "sp"]
      48   ["pop", "bp"]
      50   ["ret"]
---- memory (stack) ----
         33 0
         34 0
         35 0
         36 0
         37 0
         38 0
         39 0
         40 0
sp    => 41 78 ... fn_sub のローカル変数2
         42 56 ... fn_sub のローカル変数1
   bp => 43 47
         44 22
         45 34 ... main のローカル変数2
         46 12 ... main のローカル変数1
         47 49
         48 2
         49 0

おお〜いいですね〜。すんなり〜。 main と同じ変数名( a, b )を使っても ちゃんと別のものとして扱われています。



vm2gol v2 製作メモ(17) main から別の関数を呼ぶ / call文



空の main 関数の実行の次は、 main から 別の関数の呼び出しをやってみましょう。

簡単そうですが、これも一歩ずつということで 2段階に分けます。

  • 関数定義を並べるだけ(main からの呼び出しはしない)
  • main から呼び出す

やっていきましょう。

関数定義を並べるだけ

まずは関数定義を並べるだけ。 vgt のコードはこんな感じにしました。

// 17_empty_main_sub.vgt.json

["stmts"

, ["func", "main"
  , []
  , []
  ]

, ["func", "fn_sub"
  , []
  , []
  ]

]

トップレベルというかルート要素的なものは1つにした方がいいかな? となんとなく考えて、

[
  "stmts"
, {文1}
, {文2}
, ...
, {文n}
]

という構文を考えてみました。 stmts は statements の略です。 この構文になっていたら、文1, 文2, ... 文n と順番に文を実行していく、というものです。 Lisp だと progn でしょうか。

( 関数の定義は文なのか? というのはちょっと気になるところですが、 とりあえず文であるということにしておきます。 )

これをコンパイルしたらこんなアセンブリコードができてほしい。

  call main
  exit

label main
  ...

label fn_sub
  ...

では、コンパイラというかコード生成部分を修正していきます。 stmts の 文1, 文2, ..., 文n を順番に見ていって label 〜 の形で並べればいいだけなので これは全然むずかしくなさそう。


修正の前にまずはリファクタリングします。 codegen() に直接書いていた、 「関数定義に対応するアセンブリコードに変換する処理」の部分(ややこしいですね……) をメソッド抽出しておきます。

diff が分かりやすくならないので リファクタリング後のコードを貼ります。

def codegen_func_def(rest)
  alines = []

  fn_name = rest[0]
  body = rest[2]

  alines << ""
  alines << "label #{fn_name}"
  alines << "  push bp"
  alines << "  cp sp bp"

  alines << ""
  alines << "  # 関数の処理本体"
  body.each {|stmt|
    alines << "  # TODO"
  }

  alines << ""
  alines << "  cp bp sp"
  alines << "  pop bp"
  alines << "  ret"

  alines
end

def codegen(tree)
  alines = []

  alines << "  call main"
  alines << "  exit"

  head, *rest = tree
  alines += codegen_func_def(rest)

  alines
end

head, *rest = tree はこの先何度も出てくるイディオムで、 tree (配列)の先頭の要素を head に、 2番目以降の要素を rest に代入するという操作です。

こんな感じの動作になります。

irb(main):001:0> tree = [1, 2, 3, 4]
=> [1, 2, 3, 4]
irb(main):002:0> head, *rest = tree
=> [1, 2, 3, 4]
irb(main):003:0> head
=> 1
irb(main):004:0> rest
=> [2, 3, 4]

それから、

alines += codegen_func_def(rest)

alines = alines + codegen_func_def(rest)

と同じで、 alinescodegen_func_def(rest) の返り値を繋げたもので alines を上書きする、という動作ですね。

irb(main):023:0> xs = [1, 2]
=> [1, 2]
irb(main):024:0> xs += [3, 4]
=> [1, 2, 3, 4]
irb(main):025:0> xs
=> [1, 2, 3, 4]

要するに codegen_func_def(rest) の結果を alines の末尾に追加しているだけです。 これもこの先何度も使います。


はい、では先に進みましょう。

ルートは stmts にすると決めたので、それに対応します。 今回の vgtコードは

- stmts
  - main() の定義
  - fn_sub() の定義

のように、stmts の直下に関数定義が2つぶら下がる形になっているので、

  • codegen_stmts() というメソッドにルートの stmts を渡して呼び出し、
  • その中で codegen_func_def() を呼び出す

ようにしてみます。

--- a/vgcg.rb
+++ b/vgcg.rb
@@ -4,6 +4,8 @@
 
 require 'json'
 
+require './common'
+
 def codegen_func_def(rest)
   alines = []
 
@@ -29,6 +31,22 @@ def codegen_func_def(rest)
   alines
 end
 
+def codegen_stmts(rest)
+  alines = []
+
+  rest.each do |stmt|
+    stmt_head, *stmt_rest = stmt
+    case stmt_head
+    when "func"
+      alines += codegen_func_def(stmt_rest)
+    else
+      raise not_yet_impl("stmt_head", stmt_head)
+    end
+  end
+
+  alines
+end
+
 def codegen(tree)
   alines = []
 
@@ -36,7 +54,8 @@ def codegen(tree)
   alines << "  exit"
 
   head, *rest = tree
-  alines += codegen_func_def(rest)
+  # assert head == "stmts"
+  alines += codegen_stmts(rest)
 
   alines
 end

期待するアセンブリコードに変換されるか試しましょう。

$ ruby vgcg.rb 17_empty_main_sub.vgt.json 
  call main
  exit

label main
  push bp
  cp sp bp

  # 関数の処理本体

  cp bp sp
  pop bp
  ret

label fn_sub
  push bp
  cp sp bp

  # 関数の処理本体

  cp bp sp
  pop bp
  ret

いいですね!

ちなみにこの状態で ./run.sh 17_empty_main_sub.vgt.json を実行すると、 main だけ実行されて fn_sub の部分は実行されずに exit します。 fn_sub を呼び出していないので当然そうなりますね、という動作です。 これはこれで OK です(今の段階では)。

main から 別の関数を呼び出す

次は main から fn_sub を呼び出すようにします。

関数を呼び出すための

["call", "{呼び出したい関数名}"]

という構文を新たにでっちあげて main の「関数の処理本体」のところに追加します。

--- a/17_empty_main_sub.vgt.json
+++ b/17_empty_main_sub.vgt.json
@@ -2,7 +2,10 @@
 
 , ["func", "main"
   , []
-  , []
+  , [
+      // 関数の処理本体
+      ["call", "fn_sub"]
+    ]
   ]
 
 , ["func", "fn_sub"

これを変換してこういうアセンブリコードを出力してほしい。

  call main
  exit

label main
  push bp
  cp sp bp

  # 関数の処理本体
  call fn_sub # ← これが追加されるだけ

  cp bp sp
  pop bp
  ret

label fn_sub
  push bp
  cp sp bp
  # 関数の処理本体
  cp bp sp
  pop bp
  ret

おや? これは楽勝なのでは?

やってみましょうか。

--- a/vgcg.rb
+++ b/vgcg.rb
@@ -20,7 +20,14 @@ def codegen_func_def(rest)
   alines << ""
   alines << "  # 関数の処理本体"
   body.each {|stmt|
-    alines << "  # TODO"
+    stmt_head, *stmt_rest = stmt
+    case stmt_head
+    when "call"
+      fn_name = stmt_rest[0]
+      alines << "  call #{fn_name}"
+    else
+      raise not_yet_impl("stmt_head", stmt_head)
+    end
   }
 
   alines << ""

run.sh で実行してみると……問題なさそうです。 楽勝すぎてちょっと拍子抜けしてしまいましたが ともかく、vgtコードで関数呼び出しが書けるようになりました!

以下は終了時の状態です。

================================
reg_a(0) reg_b(0) reg_c(0) zf(0)
---- memory (main) ----
      00   ["call", 5]
pc => 02   ["exit"]
      03 ["label", "main"]
      05   ["push", "bp"]
      07   ["cp", "sp", "bp"]
      10   ["call", 20]
      12   ["cp", "bp", "sp"]
      15   ["pop", "bp"]
      17   ["ret"]
      18 ["label", "fn_sub"]
      20   ["push", "bp"]
      22   ["cp", "sp", "bp"]
      25   ["cp", "bp", "sp"]
      28   ["pop", "bp"]
      30   ["ret"]
---- memory (stack) ----
         41 0
         42 0
         43 0
         44 0
         45 47
         46 12
         47 49
         48 2
sp bp => 49 0

exit


vm2gol v2 製作メモ(16) 簡単なコード生成



条件分岐とループができて、 サブルーチンの呼び出しができて、引数が渡せて、 結果を返せて、ローカル変数が使えるようになった!!!  ので、これくらい揃えばもうなんでもできるんじゃね!?!?  みたいな気分になりました。

というわけでここからコード生成に突入しようと思います。

つまり!  コンパイラ(の一部)!  です!!

( ただし、ここまでで VM は完成という訳ではないので、 VM も必要に応じて修正していきます。 )


まずは空の main 関数呼び出しから始めましょうか。

C言語で書くとこんな感じ(雰囲気で適当に書いてます)。

void main(){
  // 何もしない
}

まじめにパースすると面倒なので、 またまたこんなオレオレフォーマットを使うことにしました。 これをコード生成の入力とします。 JSON なので、 JSON.parse すれば構文木がゲットできます。

// 16_empty_main.vgt.json

["func"
  ,"main" // 関数名
  ,[] // 引数
  ,[] // 関数本体
]

これがアセンブリコードになったときどうなってほしいか?

こうなってほしい!

  call main
  exit

label main
  push bp
  cp sp bp

  # 関数の処理本体

  cp bp sp
  pop bp
  ret

このようなアセンブリコードに変換するプログラム(=コード生成器) を作っていきましょう。

入力ファイルの拡張子は、 元のプログラムが C言語相当なつもりなので 最初は .vgc.json としていましたが、 構文木をそのまま書いているようなものなので、 Tree の "t" を取って .vgt.json としました。

この形式のコードのことを「vgtコード」と呼ぶことにします。

コード生成器は vgcg.rb というファイル名にしました。 "cg" は code generator の略。

次のようなコマンドでコード生成を行って アセンブリコードのファイルに出力する想定です。

ruby vgcg.rb foo.vgt.json > foo.vga.txt

さて、まず大枠を作ってみました。 出力するアセンブリコードをハードコーディングしておいて、 最初はこんなとこから始めるといいんじゃないでしょうか?

# vgcg.rb

# aline: assembly line

require 'json'

def codegen(tree)
  alines = []

  alines << "  call main"
  alines << "  exit"

  alines << ""
  alines << "label main"
  alines << "  push bp"
  alines << "  cp sp bp"

  alines << ""
  alines << "  # 関数の処理本体"

  alines << ""
  alines << "  cp bp sp"
  alines << "  pop bp"
  alines << "  ret"

  alines
end

# vgtコード読み込み
src = File.read(ARGV[0])

# 構文木に変換
tree = JSON.parse(src)

# コード生成(アセンブリコードに変換)
alines = codegen(tree)

# アセンブリコードを出力
alines.each {|aline|
  puts aline
}

大枠としてはこうで、あとは codegen() をそれっぽくしていけばよさそうです。

aline は assembly line の略。 アセンブリコードの1行に対応する文字列ということにします。

(2021-05-28 追記) 簡素化のため ステップ 53 で 配列 alines に貯めていくのやめてその都度 print する方式に変更しました。


codegen() に渡されている tree はこんな内容です (見た目は元の JSON と同じですが、こっちは Ruby の配列です)。

[
  "func",
  "main",
  [],
  []
]

入力の内容そのままですね。

ただの配列なので、関数名が欲しければ tree[1] 、 関数の本体部分が欲しければ tree[3] で取り出せます。

こうやって取り出したものでハードコーディングしたところを置き換えていきます。 関数本体はまだ空なので出力としては変化なしですね。

--- a/vgcg.rb
+++ b/vgcg.rb
@@ -7,16 +7,22 @@ require 'json'
 def codegen(tree)
   alines = []
 
+  fn_name = tree[1]
+  body = tree[3]
+
   alines << "  call main"
   alines << "  exit"
 
   alines << ""
-  alines << "label main"
+  alines << "label #{fn_name}"
   alines << "  push bp"
   alines << "  cp sp bp"
 
   alines << ""
   alines << "  # 関数の処理本体"
+  body.each {|stmt|
+    alines << "  # TODO"
+  }
 
   alines << ""
   alines << "  cp bp sp"

「関数 main をエントリポイントにする」 と決めたので、一番最初の call main の部分は 置き換えずに決め打ちのままにしています。

動かしてみます。

$ ruby vgcg.rb 16_empty_main.vgt.json 
  call main
  exit

label main
  push bp
  cp sp bp

  # 関数の処理本体

  cp bp sp
  pop bp
  ret

特に問題なし。


run.sh を修正しましょう。 アセンブルの前にコード生成のステップを追加します。

--- a/run.sh
+++ b/run.sh
@@ -3,8 +3,10 @@
 set -o errexit
 
 file="$1"
-bname=$(basename $file .vga.txt)
+bname=$(basename $file .vgt.json)
+asmfile=tmp/${bname}.vga.txt
 exefile=tmp/${bname}.vge.yaml
 
-ruby vgasm.rb $file > $exefile
+ruby vgcg.rb $file > $asmfile
+ruby vgasm.rb $asmfile > $exefile
 ruby vgvm.rb $exefile

動かします!

$ ./run.sh 16_empty_main.vgt.json 

(略)

================================
reg_a(0) reg_b(0) reg_c(0) zf(0)
---- memory (main) ----
      00   ["call", 5]
pc => 02   ["exit"]
      03 ["label", "main"]
      05   ["push", "bp"]
      07   ["cp", "sp", "bp"]
      10   ["cp", "bp", "sp"]
      13   ["pop", "bp"]
      15   ["ret"]
---- memory (stack) ----
         41 0
         42 0
         43 0
         44 0
         45 0
         46 0
         47 49
         48 2
sp bp => 49 0

exit

動きました!

今回はここまで。 コード生成の初回なのでまあこんなものでしょう。



vm2gol v2 製作メモ(15) ローカル変数 / sub_sp



今回はローカル変数をやります!


これまでスタックをこんな風に使っていました。

ベースポインタ
戻り先アドレス
引数1
引数2

入れ子の呼び出しがある場合はこう:

ベースポインタ
戻り先アドレス
引数1
引数2
旧ベースポインタ
戻り先アドレス
引数1
引数2

ローカル変数もなんとここに突っ込むそうです。 どう突っ込むかというと、こう:

ローカル変数2
ローカル変数1
ベースポインタ
戻り先アドレス
引数1
引数2
ローカル変数2
ローカル変数1
旧ベースポインタ
戻り先アドレス
引数1
引数2

入れ子なしで見てみます。

      ローカル変数2 (bp-2)
      ローカル変数1 (bp-1)
bp => ベースポインタ
      戻り先アドレス
      引数1 (bp+2)
      引数2 (bp+3)

呼びだされた先のサブルーチンで ローカル変数1を宣言するとスタックポインタが -1 され、 その次に ローカル変数2を宣言するとスタックポインタがさらに -1 されます。

引数1, 2 を使うときは bp+2, bp+3 を見ていましたが、 ローカル変数はベースポインタの上の方を見て、 ローカル変数1, 2 はそれぞれ bp-1, bp-2 の位置を使って読み書きすればよいと。

こういう仕組みになっているそうです!   すごいですね!   すごいですね!   今「すごいですね!」って2回言いました。 私はすごいなー巧みな仕組みだなーっていうかこんなんでいいんだ!?   と関心して目から鱗でした。 サブルーチン呼び出し、引数渡し、ローカル変数を使うのに スタック1つで用が足りてしまうんですね!   この歳になるまで知りませんでしたよ!!!!

ローカル変数1個だけ

関心したところで実際に書いてみます。 一度に少しずつということで、引数と値の返却はなしで、 まずはローカル変数1個だけ。

# 15_local_var.vga.txt

  call sub
  exit

label sub
  push bp
  cp sp bp

  # サブルーチンの処理本体
  set_reg_a 11
  sub_sp 1         # ローカル変数1の宣言(領域確保)
  cp reg_a [bp-1]  # ローカル変数1に値をセット
  cp [bp-1] reg_b  # ローカル変数1の値を参照して reg_b にコピー

  cp bp sp
  pop bp
  ret

まだ sub_sp を実装していないので、動かすとこうなります。

$ ./run.sh 15_local_var.vga.txt 
vgvm.rb:252:in `num_args_for': Invalid operator (sub_sp) (RuntimeError)

sub_sp を追加します。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -160,6 +160,9 @@ class Vm
       when "add_sp"
         set_sp(@sp + @mem.main[@pc + 1])
         @pc += pc_delta
+      when "sub_sp"
+        set_sp(@sp - @mem.main[@pc + 1])
+        @pc += pc_delta
       when "compare"
         compare()
         @pc += pc_delta
@@ -244,7 +247,7 @@ class Vm
     case operator
     when "cp"
       2
-    when "set_reg_a", "set_reg_b", "label", "call", "push", "pop", "add_sp"
+    when "set_reg_a", "set_reg_b", "label", "call", "push", "pop", "add_sp", "sub_sp"
       1
     when "ret", "exit", "add_ab"
       0

次はこうなります。

vgvm.rb:229:in `copy': Not yet implemented ("copy src") ("reg_a") (RuntimeError)

copy() を修正。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -219,6 +219,8 @@ class Vm
   def copy(arg1, arg2)
     src_val =
       case arg1
+      when "reg_a"
+        @reg_a
       when "sp"
         @sp
       when "bp"
vgvm.rb:244:in `copy': Not yet implemented ("copy dest") ("[bp-1]") (RuntimeError)

修正します!(ローカル変数へのコピー)

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -240,6 +240,8 @@ class Vm
       @bp = src_val
     when "sp"
       set_sp(src_val)
+    when /^\[bp-(\d+)\]$/
+      @mem.stack[@bp - $1.to_i] = src_val
     else
       raise not_yet_impl("copy dest", arg2)
     end
vgvm.rb:231:in `copy': Not yet implemented ("copy src") ("[bp-1]") (RuntimeError)

修正!!(ローカル変数からのコピー)

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -227,6 +227,8 @@ class Vm
         @bp
       when /^\[bp\+(\d+)\]$/
         @mem.stack[@bp + $1.to_i]
+      when /^\[bp-(\d+)\]$/
+        @mem.stack[@bp - $1.to_i]
       else
         raise not_yet_impl("copy src", arg1)
       end

最後まで動きました!!!

================================
reg_a(11) reg_b(11) reg_c(0) zf(0)
---- memory (main) ----
      00   ["call", 5]
pc => 02   ["exit"]
      03 ["label", "sub"]
      05   ["push", "bp"]
      07   ["cp", "sp", "bp"]
      10   ["set_reg_a", 11]
      12   ["sub_sp", 1]
      14   ["cp", "reg_a", "[bp-1]"]
      17   ["cp", "[bp-1]", "reg_b"]
      20   ["cp", "bp", "sp"]
      23   ["pop", "bp"]
      25   ["ret"]
---- memory (stack) ----
         41 0
         42 0
         43 0
         44 0
         45 0
         46 11 ... ローカル変数1
         47 49
         48 2
sp bp => 49 0

exit

reg_a → ローカル変数1( [bp-1] ) → reg_b の順番で値がコピーされています。

ローカル変数2個

ローカル変数2個もやってみます。

# 15_local_vars.vga.txt

  call sub
  exit

label sub
  push bp
  cp sp bp

  # サブルーチンの処理本体
  set_reg_a 11
  sub_sp 1         # ローカル変数1の宣言(領域確保)
  cp reg_a [bp-1]  # ローカル変数1に値をセット
  cp [bp-1] reg_b  # ローカル変数1の値を参照して reg_b にコピー

  set_reg_a 12
  sub_sp 1         # ローカル変数2の宣言(領域確保)
  cp reg_a [bp-2]  # ローカル変数2に値をセット
  cp [bp-2] reg_b  # ローカル変数2の値を参照して reg_b にコピー

  cp bp sp
  pop bp
  ret

2個でも大丈夫でした!

================================
reg_a(12) reg_b(12) reg_c(0) zf(0)
---- memory (main) ----
      00   ["call", 5]
pc => 02   ["exit"]
      03 ["label", "sub"]
      05   ["push", "bp"]
      07   ["cp", "sp", "bp"]
      10   ["set_reg_a", 11]
      12   ["sub_sp", 1]
      14   ["cp", "reg_a", "[bp-1]"]
      17   ["cp", "[bp-1]", "reg_b"]
      20   ["set_reg_a", 12]
      22   ["sub_sp", 1]
      24   ["cp", "reg_a", "[bp-2]"]
      27   ["cp", "[bp-2]", "reg_b"]
      30   ["cp", "bp", "sp"]
      33   ["pop", "bp"]
      35   ["ret"]
---- memory (stack) ----
         41 0
         42 0
         43 0
         44 0
         45 12 ... ローカル変数2
         46 11 ... ローカル変数1
         47 49
         48 2
sp bp => 49 0

exit

3個以上の場合も同じ要領でできそうですね。



vm2gol v2 製作メモ(14) 複数の引数を渡す / スタックオーバーフロー対策 / 返り値



前回は引数を 1個だけ渡すサブルーチン呼び出しができるようになりましたが、 今回はそれを 2個にしてみます。

それから、返り値の渡し方を調べたところ、 とりあえずは reg_a にセットすればよさそうでした。 それなら簡単にできそうです。ついでにやってしまいましょうか。

これらを組み合わせると、 たとえば「引数1 と引数2 を受け取って足した結果を返すサブルーチン」 なんてものが作れそうです。 今回はこれを目標にしましょう。

引数を2つ渡す

一度にやると大変なので、まずは引数を2個渡して 無事戻ってくるとこまでやります。

CDECL によると、引数は後ろのものから先にスタックに積むそうなので、 前回のをちょっと修正してこうします。

# 14_two_args_return.vga.txt

  push 34   # 引数2 を先に push
  push 12   # その次に引数1 を push
  call sub
  add_sp 2  # 引数の数だけスタックポインタを戻す
  exit

label sub
  push bp
  cp sp bp

  # サブルーチンの処理本体
  cp [bp+2] reg_a

  cp bp sp
  pop bp
  ret

引数を渡す順番と、サブルーチンから戻った後の後片付けで スタックポインタを引数の数だけ戻すところがポイントです。

これを動かすと……無事 exit までたどり着いて終了するのですが、 途中で spbp が負の値になり、スタックの天井を突き抜けてしまいます (Ruby では負の添字は配列の末尾側へのアクセスになるので、 スタックの底の方に戻って不正に書き込みが行われます)。 これはまずい。

スタックオーバーフロー対策

スタックのサイズは Memory のコンストラクタで渡していたので、 そこを増やしてやればいいのですが、 その前にせっかくなのでスタックオーバーフロー(stack overflow)対策をやりましょう! スタックオーバーフロー対策チャンスです!


Vm#sp に 0 より小さい数をセットしようとしたら例外を出すようにします。

スタックオーバーフローが発生したことに気づければいいだけなので、 こんなので十分でしょう。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -110,6 +110,11 @@ class Vm
     @bp = 3
   end
 
+  def set_sp(addr)
+    raise "Stack overflow" if addr < 0
+    @sp = addr
+  end
+
   def load_program(path)
     @mem.main = YAML.load_file(path)
   end

Vm#sp に値をセットしている箇所を set_sp() の呼び出しに書き換え。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -158,7 +158,7 @@ class Vm
         add_ac()
         @pc += pc_delta
       when "add_sp"
-        @sp += @mem.main[@pc + 1]
+        set_sp(@sp + @mem.main[@pc + 1])
         @pc += pc_delta
       when "compare"
         compare()
@@ -172,14 +172,14 @@ class Vm
         addr = @mem.main[@pc + 1]
         jump_eq(addr)
       when "call"
-        @sp -= 1 # スタックポインタを1減らす
+        set_sp(@sp - 1) # スタックポインタを1減らす
         @mem.stack[@sp] = @pc + 2 # 戻り先を記憶
         next_addr = @mem.main[@pc + 1] # ジャンプ先
         @pc = next_addr
       when "ret"
         ret_addr = @mem.stack[@sp] # 戻り先アドレスを取得
         @pc = ret_addr # 戻る
-        @sp += 1 # スタックポインタを戻す
+        set_sp(@sp + 1) # スタックポインタを戻す
       when "push"
         arg = @mem.main[@pc + 1]
         val_to_push =
@@ -191,7 +191,7 @@ class Vm
           else
             raise not_yet_impl("push", arg)
           end
-        @sp -= 1
+        set_sp(@sp - 1)
         @mem.stack[@sp] = val_to_push
         @pc += pc_delta
       when "pop"
@@ -202,7 +202,7 @@ class Vm
         else
           raise not_yet_impl("pop", arg)
         end
-        @sp += 1
+        set_sp(@sp + 1)
         @pc += pc_delta
       else
         raise "Unknown operator (#{op})"
@@ -232,7 +232,7 @@ class Vm
     when "bp"
       @bp = src_val
     when "sp"
-      @sp = src_val
+      set_sp(src_val)
     else
       raise not_yet_impl("copy dest", arg2)
     end

サイズ4 のかわいいスタックのまま動かすと、 スタックオーバーフローを検出して例外が発生するはず!

$ ./run.sh 14_two_args_return.vga.txt 

(略)

================================
reg_a(0) reg_b(0) reg_c(0) zf(0)
---- memory (main) ----
      00   ["push", 34]
      02   ["push", 12]
      04   ["call", 11]
      06   ["add_sp", 2]
      08   ["exit"]
      09 ["label", "sub"]
pc => 11   ["push", "bp"]
      13   ["cp", "sp", "bp"]
      16   ["cp", "[bp+2]", "reg_a"]
      19   ["cp", "bp", "sp"]
      22   ["pop", "bp"]
      24   ["ret"]
---- memory (stack) ----
sp    => 0 6
         1 12
         2 34
   bp => 3 0

vgvm.rb:114:in `set_sp': Stack overflow (RuntimeError)
        from vgvm.rb:194:in `block in start'
        from vgvm.rb:126:in `loop'
        from vgvm.rb:126:in `start'
        from vgvm.rb:316:in `<main>'

発生しました! いいですねー。 sp がすでに 0 の位置にあるのに、そこでさらに push しようとしたため 期待どおりに エラーになってくれました。


確認できて気が済んだので、 スタック領域のサイズを増やします。

vm2gol-v1 を作っていたときは足りなくなるたびにその都度伸ばしていましたが、 煩雑なのでここで一気に 50 まで引き上げておきます。 かわいいスタックはここで卒業です。

@@ -90,7 +90,7 @@ class Memory
 end

 class Vm
-  def initialize(mem)
+  def initialize(mem, stack_size)
     # program counter
     @pc = 0

@@ -104,9 +104,9 @@ class Vm

     @mem = mem
     # スタックポインタ
-    @sp = 3
+    @sp = stack_size - 1
     # ベースポインタ
-    @bp = 3
+    @bp = stack_size - 1
     end

     def set_sp(addr)
@@ -320,8 +320,9 @@ end

 bin_file = ARGV[0]

-mem = Memory.new(4)
-vm = Vm.new(mem)
+stack_size = 50
+mem = Memory.new(stack_size)
+vm = Vm.new(mem, stack_size)
 vm.load_program(bin_file)

 vm.start

スタック領域のサイズを十分に大きくしたので、 せっかく実装したスタックオーバーフロー検知の処理は この先出番がなくなってしまうのでした……。

まあ、残しておいても邪魔にはならないですし、 試行錯誤しているときにまた発生しないとも限らない、ということにして、 このまま残しておきます。

ケチケチせずにサイズを 100 とか 500 とかにしてしまってもいいのですが。


ちなみに、v1 のときはその都度必要な分だけスタック領域を大きくする、 というやり方で進めていたので、実際必要だったんですよ…… そこらへんも手探りでした。

「最初からスタック領域のサイズを十分大きくしておけばよい」 という発想は、 後から振り返るとそりゃそうだって感じがしますが、 「あ、これも削れるじゃん」と気づいたのは v1 を完成させた後でした。


( ところで、この検知の処理って CPU でやるべきことなの? という点は謎ですね。普通はどこでやるんでしょうね? (まだ調べてない) )


脱線しましたが、えーと……あ、そうそう、引数 2個渡して戻る、 というのをやっていたのでした。

動かしてみると……。

================================
reg_a(12) reg_b(0) reg_c(0) zf(0)
---- memory (main) ----
      00   ["push", 34]
      02   ["push", 12]
      04   ["call", 11]
      06   ["add_sp", 2]
pc => 08   ["exit"]
      09 ["label", "sub"]
      11   ["push", "bp"]
      13   ["cp", "sp", "bp"]
      16   ["cp", "[bp+2]", "reg_a"]
      19   ["cp", "bp", "sp"]
      22   ["pop", "bp"]
      24   ["ret"]
---- memory (stack) ----
         41 0
         42 0
         43 0
         44 0
         45 49
         46 6
         47 12
         48 34
sp bp => 49 0

exit

うん、いいですね。

返り値

残りの「引数2つを足して返す」をやっつけましょう。 「サブルーチンの処理本体」の部分をこんな感じに書けば良さそうです。

cp [bp+2] reg_a # 引数1 を reg_a にセット
cp [bp+3] reg_b # 引数2 を reg_b にセット
add_ab          # reg_a と reg_b を足して結果を reg_a にセット

add_ab 命令はたしか前に作ってたはず…… ありますね。これ使えばいいですね。

結果を返すのはどこにいったのかというと、 結果は reg_a に入れて返す(これも CDECL に合わせています) ということにしているので、 add_ab の場合は 特別に何かやる必要はないのです。

はい、ではアセンブリのコードを修正します!

--- a/14_two_args_return.vga.txt
+++ b/14_two_args_return.vga.txt
@@ -9,7 +9,9 @@ label sub
   cp sp bp
 
   # サブルーチンの処理本体
-  cp [bp+2] reg_a
+  cp [bp+2] reg_a # 引数1
+  cp [bp+3] reg_b # 引数2
+  add_ab
 
   cp bp sp
   pop bp

実行。

vgvm.rb:250:in `num_args_for': Invalid operator (add_ab) (RuntimeError)

抜けてました。追加します。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -244,7 +244,7 @@ class Vm
       2
     when "set_reg_a", "set_reg_b", "label", "call", "push", "pop", "add_sp"
       1
-    when "ret", "exit"
+    when "ret", "exit", "add_ab"
       0
     else
       raise "Invalid operator (#{operator})"

まあこうやってその都度必要な分を修正していけばいいんです(そういう方針です)。

vgvm.rb:237:in `copy': Not yet implemented ("copy dest") ("reg_b") (RuntimeError)

reg_b へのコピーもまだでしたね。 Vm#copy() に追加します。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -229,6 +229,8 @@ class Vm
     case arg2
     when "reg_a"
       @reg_a = src_val
+    when "reg_b"
+      @reg_b = src_val
     when "bp"
       @bp = src_val
     when "sp"

どうでしょう。

================================
reg_a(46) reg_b(34) reg_c(0) zf(0)
---- memory (main) ----
      00   ["push", 34]
      02   ["push", 12]
      04   ["call", 11]
      06   ["add_sp", 2]
pc => 08   ["exit"]
      09 ["label", "sub"]
      11   ["push", "bp"]
      13   ["cp", "sp", "bp"]
      16   ["cp", "[bp+2]", "reg_a"]
      19   ["cp", "[bp+3]", "reg_b"]
      22   ["add_ab"]
      23   ["cp", "bp", "sp"]
      26   ["pop", "bp"]
      28   ["ret"]
---- memory (stack) ----
         41 0
         42 0
         43 0
         44 0
         45 49
         46 6
         47 12
         48 34
sp bp => 49 0

exit

できました! 足し算の結果の 12 + 34 = 46 が reg_a にセットされ、 sp, bp がスタックの底に戻っています!

2個でできたので、3個以上の場合も

  • 後ろの引数から順に push
  • 引数の数だけスタックポインタを戻す

という点を押さえておけば同じ要領でできるでしょう。



vm2gol v2 製作メモ(13) サブルーチンに引数を1個渡す / add_sp



前々回と前回でいろいろ片付いたので引数やります!

引数はスタックに置いて渡すそうです!

まず引数を1個だけ使うのをやってみます。 次のようにサブルーチン呼び出し(call)の直前でスタックに push します。

(※間違いがあります。後述)

サブルーチン呼び出し前:

sp bp 2
      3

引数を1個 push: push {引数}

sp    1 {引数}
   bp 2
      3

サブルーチン呼び出し: push bp

sp    0 2
      1 {引数}
   bp 2
      3

サブルーチン呼び出し: cp sp bp

sp bp 0 2
      1 {引数}
      2
      3

で、サブルーチン内でこの引数にアクセスする場合は bp + 1 の位置を見ればよい(※間違いがあります。後述)と。

ふむふむ。やってみましょう。 例として、サブルーチンの中で引数1 を reg_a にセットするだけ、 というのをやってみます。

# 13_one_arg.vga.txt

  push 11 # 引数1
  call sub
  exit

label sub
  push bp
  cp sp bp

  # サブルーチンの処理本体
  cp [bp+1] reg_a

  cp bp sp
  pop bp
  ret

いろいろ片付いたはずでしたが実際動かすとまだ足りないところがあります。 まず最初の push ができない。

vgvm.rb:182:in `block in start': Not yet implemented ("push") (11) (RuntimeError)

オペランドとして即値を受け取れていませんでした。対応させます。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -176,6 +176,8 @@ class Vm
         arg = @mem.main[@pc + 1]
         val_to_push =
           case arg
+          when Integer
+            arg
           when "bp"
             @bp
           else

次は……

vgvm.rb:216:in `copy': Not yet implemented ("copy src") ("[bp+1]") (RuntimeError)

うん、そんな気はしました。 cp のコピー元のとこを修正します。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -212,6 +212,8 @@ class Vm
         @sp
       when "bp"
         @bp
+      when /^\[bp\+(\d+)\]$/
+        @mem.stack[@bp + $1.to_i]
       else
         raise not_yet_impl("copy src", arg1)
       end

@bp + $1.to_i を返すのではなく、 「スタックの @bp + $1.to_i の位置にある値」を返したいので @mem.stack[@bp + $1.to_i] となります。

正規表現が若干ハードコーディング気味ですが動いたので気にせず進みます。 YAGNI です。

お次はこう:

vgvm.rb:227:in `copy': Not yet implemented ("copy dest") ("reg_a") (RuntimeError)

cp のコピー先を修正!

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -219,6 +219,8 @@ class Vm
       end
 
     case arg2
+    when "reg_a"
+      @reg_a = src_val
     when "bp"
       @bp = src_val
     when "sp"

エラーが出なくなりましたが、動きがおかしいですね。

(終了時の状態)

================================
reg_a(4) reg_b(0) reg_c(0) zf(0)
---- memory (main) ----
      00   ["push", 11]
      02   ["call", 7]
pc => 04   ["exit"]
      05 ["label", "sub"]
      07   ["push", "bp"]
      09   ["cp", "sp", "bp"]
      12   ["cp", "[bp+1]", "reg_a"]
      15   ["cp", "bp", "sp"]
      18   ["pop", "bp"]
      20   ["ret"]
---- memory (stack) ----
         0 3
         1 4
sp    => 2 11
   bp => 3 0

exit

引数として指定した 11 が reg_a にセットされてほしいのに、 4 がセットされています。

(しばし調べる)

分かりました。 サブルーチン呼び出しの際には引数だけじゃなくて 戻り先アドレスもスタックに積んでいたのでした。

0 3
1 4  ← 戻り先アドレス
2 11 ← 引数
3 0

なので、[bp+1] じゃなくて [bp+2] としないといけないのでした。

--- a/13_one_arg.vga.txt
+++ b/13_one_arg.vga.txt
@@ -7,7 +7,7 @@ label sub
   cp sp bp
 
   # サブルーチンの処理本体
-  cp [bp+1] reg_a
+  cp [bp+2] reg_a
 
   cp bp sp
   pop bp

アセンブリコードを修正して動かすと、終了時の状態がこうなります。

================================
reg_a(11) reg_b(0) reg_c(0) zf(0)
---- memory (main) ----
      00   ["push", 11]
      02   ["call", 7]
pc => 04   ["exit"]
      05 ["label", "sub"]
      07   ["push", "bp"]
      09   ["cp", "sp", "bp"]
      12   ["cp", "[bp+2]", "reg_a"]
      15   ["cp", "bp", "sp"]
      18   ["pop", "bp"]
      20   ["ret"]
---- memory (stack) ----
         0 3
         1 4
sp    => 2 11
   bp => 3 0

exit

こんどは reg_a にちゃんと 11 がセットされました! されましたが!!

spbp の位置がずれてますね……。 これはずれていてはいけない (サブルーチン呼び出し前と同じ状態になっていないといけない)はずです。

呼び出し規約は CDECL を参考にすることにしたので、ちょっと調べてみると、 CDECL では ret で呼び出し元に戻った後に sp の位置を戻すようで、 sp に 1 を足すためにまた専用命令である add_sp をシュッと追加します。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -152,6 +152,9 @@ class Vm
       when "add_ac"
         add_ac()
         @pc += pc_delta
+      when "add_sp"
+        @sp += @mem.main[@pc + 1]
+        @pc += pc_delta
       when "compare"
         compare()
         @pc += pc_delta
@@ -234,7 +237,7 @@ class Vm
     case operator
     when "cp"
       2
-    when "set_reg_a", "set_reg_b", "label", "call", "push", "pop"
+    when "set_reg_a", "set_reg_b", "label", "call", "push", "pop", "add_sp"
       1
     when "ret", "exit"
       0

アセンブリコードの方にも add_sp を追加。

--- a/13_one_arg.vga.txt
+++ b/13_one_arg.vga.txt
@@ -1,5 +1,6 @@
   push 11 # 引数1
   call sub
+  add_sp 1
   exit
 
 label sub

またまた動かすとこんどは……

================================
reg_a(11) reg_b(0) reg_c(0) zf(0)
---- memory (main) ----
      00   ["push", 11]
      02   ["call", 9]
      04   ["add_sp", 1]
pc => 06   ["exit"]
      07 ["label", "sub"]
      09   ["push", "bp"]
      11   ["cp", "sp", "bp"]
      14   ["cp", "[bp+2]", "reg_a"]
      17   ["cp", "bp", "sp"]
      20   ["pop", "bp"]
      22   ["ret"]
---- memory (stack) ----
         0 3
         1 4
         2 11
sp bp => 3 0

exit

sp が元の位置に戻りました! めでたしめでたし!!

修正後のアセンブリコードも改めて貼っておきます。

# 13_one_arg.vga.txt

  push 11 # 引数1
  call sub
  add_sp 1
  exit

label sub
  push bp
  cp sp bp

  # サブルーチンの処理本体
  cp [bp+2] reg_a

  cp bp sp
  pop bp
  ret


vm2gol v2 製作メモ(12) リファクタリング / cp



道具が用意できたので引数渡しをやりたい! のですが、今回はリファクタリング回にします。

前回やっつけで追加した copy_sp_to_bpcopy_bp_to_sp を整理して、 せっかくのリファクタリング回なので他の部分もあわせて整理しておきます。


まず、

case arg
when "bp"
  @bp
else
  raise "push: not yet implemented (#{arg})"
end

のように、 case 式で分岐させ、 else で「その値に関する処理はまだ実装してないよ」と例外を投げている箇所が ありますが、以後も出てくるので共通化しておきます。

これは別ファイル common.rb に抽出します。

# common.rb

def p_e(*args)
  args.each{ |arg| $stderr.puts arg.inspect }
end

def pp_e(*args)
  args.each{ |arg| $stderr.puts arg.pretty_inspect }
end

def not_yet_impl(*args)
  "Not yet implemented" +
    args
    .map{ |arg| " (#{ arg.inspect })" }
    .join("")
end

ついでにデバッグ用の p_e, pp_e というべんりメソッドも足しておきました。

not_yet_impl() の中で例外を投げるとこまでやってしまおうかとも 考えましたが、 なるべく単機能(例外用のメッセージを組み立てるだけ)になっている方がよいかな? とか、 呼び出し元を読んだときにraise していることが分かった方が明示的でよいかな? などと考えて控えめにしておきました。


呼び出し元を修正します。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -2,6 +2,8 @@
 require 'pp'
 require 'yaml'
 
+require './common'
+
 module TermColor
   RESET  = "\e[m"
   RED    = "\e[0;31m"
@@ -174,7 +176,7 @@ class Vm
           when "bp"
             @bp
           else
-            raise "push: not yet implemented (#{arg})"
+            raise not_yet_impl("push", arg)
           end
         @sp -= 1
         @mem.stack[@sp] = val_to_push
@@ -185,7 +187,7 @@ class Vm
         when "bp"
           @bp = @mem.stack[@sp]
         else
-          raise "pop: not yet implemented (#{arg})"
+          raise not_yet_impl("pop", arg)
         end
         @sp += 1
         @pc += 2

次に、値のコピーまわりを整理します。

前回はとにかく早く動かしたかったので bp, sp 間のコピー用に専用の命令を追加してしまいましたが、 コピー用の命令は今後もいろいろ使うので、 この段階で汎用化しておきます。


一般的な(?)アセンブリ言語では こういうとき mov(move)という命令を使うようです。 ただし、自分が見聞きした範囲でも

  • move(移動)じゃなくてコピーでは?
  • オペランドの順番(コピー元、先)が Intel 記法と AT&T 記法で違っていて混乱する

という意見がちらほらあるようで(どのくらいポピュラーかは分かりませんが……)、個人的にも微妙に感じたので、 それならいっそのこと cp (copy) にしてはどうか、となりました。

MOV命令の元になった英語は「move」で、移動という意味なのですが、 代入って移動とは似ているけどちょっと違いますよね。

(中略)

すなおにコピー命令とかだったら説明が簡単だったのになあ。 どうしてMOV命令ということになったのかは、筆者にも分かりません。

30日でできる! OS自作入門 p32)

オペランドの順番問題については、 これは UNIX の cp コマンドと同じインターフェイスにしてみます。 つまり、コピー元、コピー先、の順番です。 分かりやすいですね? 自分にとって分かりやすいのでこれでいいということにします。 よく知られた既存のインターフェイスに合わせることで覚える手間をなくそう、余分な負荷を削ろうという工夫のつもりでもあります。

どうせ自分向けに作っているオレオレのものなので、 こういうのは「自分が覚えやすいかどうか」を基準にして決めてしまえばよい、と割り切っています(jump_eq のような他の命令の名前なんかもそういう基準で適当に決めています)。


適当に決めたので適当に修正しましょう。

まず cp 命令を追加。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -143,6 +143,12 @@ class Vm
       when "copy_sp_to_bp"
         @bp = @sp
         @pc += 1
+      when "cp"
+        copy(
+          @mem.main[@pc + 1],
+          @mem.main[@pc + 2]
+        )
+        @pc += 3
       when "add_ab"
         add_ab()
         @pc += 1
@@ -200,8 +206,31 @@ class Vm
     end
   end
 
+  def copy(arg1, arg2)
+    src_val =
+      case arg1
+      when "sp"
+        @sp
+      when "bp"
+        @bp
+      else
+        raise not_yet_impl("copy src", arg1)
+      end
+
+    case arg2
+    when "bp"
+      @bp = src_val
+    when "sp"
+      @sp = src_val
+    else
+      raise not_yet_impl("copy dest", arg2)
+    end
+  end
+
   def self.num_args_for(operator)
     case operator
+    when "cp"
+      2
     when "set_reg_a", "set_reg_b", "label", "call", "push", "pop"
       1
     when "ret", "exit", "copy_bp_to_sp", "copy_sp_to_bp"

copy_bp_to_spcopy_sp_to_bp はもう使わないので消しておきます。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -137,12 +137,6 @@ class Vm
         n = @mem.main[@pc + 1]
         @reg_c = n
         @pc += 2
-      when "copy_bp_to_sp"
-        @sp = @bp
-        @pc += 1
-      when "copy_sp_to_bp"
-        @bp = @sp
-        @pc += 1
       when "cp"
         copy(
           @mem.main[@pc + 1],
@@ -233,7 +227,7 @@ class Vm
       2
     when "set_reg_a", "set_reg_b", "label", "call", "push", "pop"
       1
-    when "ret", "exit", "copy_bp_to_sp", "copy_sp_to_bp"
+    when "ret", "exit"
       0
     else
       raise "Invalid operator (#{operator})"

前回のアセンブリコードを修正。

--- a/11_bp_push_pop.vga.txt
+++ b/11_bp_push_pop.vga.txt
@@ -6,13 +6,13 @@
 label sub
   # 前処理
   push bp
-  copy_sp_to_bp
+  cp sp bp
 
   # サブルーチン本体の処理
   set_reg_a 2
 
   # 後片付け
-  copy_bp_to_sp
+  cp bp sp
   pop bp
 
   ret

修正後のアセンブリコードが

cp bp sp

となって、アセンブリのコードなんだかシェルスクリプトなんだか よく分からない感じになって楽しくなりましたね(?)。


そういえば特に何も言わずにやってますが、 VM の命令名とアセンブリニーモニックが一致しているので こういう場合もアセンブラは修正なしです。

つくづく影の薄いアセンブラ……。


あと気になっていたのが、命令ごとのオペランド(引数)の数に関する知識が vgvm.rb のコード中に散らばっていることです。

せっかく Vm.num_args_for がすでにあるので、これを使いまわしましょう。

(今のうちに対処しておかないとこの先辛いってわけではなく、 とりあえず DRY にしときましょうか、という程度のノリです。)

@@ -118,6 +118,9 @@ class Vm
     loop do
       # operator
       op = @mem.main[@pc]
+
+      pc_delta = 1 + Vm.num_args_for(op)
+
       case op
       when "exit"
         $stderr.puts "exit"
@@ -125,32 +128,32 @@ class Vm
       when "set_reg_a"
         n = @mem.main[@pc + 1]
         set_reg_a(n)
-        @pc += 2
+        @pc += pc_delta
       when "set_reg_b"
         n = @mem.main[@pc + 1]
         set_reg_b(n)
-        @pc += 2
+        @pc += pc_delta
       when "set_reg_c"
         n = @mem.main[@pc + 1]
         set_reg_c(n)

以下同様

修正した 11_bp_push_pop.vga.txt を実行してみます。

$ ./run.sh 11_bp_push_pop.vga.txt 
(略)
================================
reg_a(2) reg_b(3) reg_c(0) zf(0)
---- memory (main) ----
      00   ["set_reg_a", 1]
      02   ["call", 9]
      04   ["set_reg_b", 3]
pc => 06   ["exit"]
      07 ["label", "sub"]
      09   ["push", "bp"]
      11   ["cp", "sp", "bp"]
      14   ["set_reg_a", 2]
      16   ["cp", "bp", "sp"]
      19   ["pop", "bp"]
      21   ["ret"]
---- memory (stack) ----
         0 0
         1 3
         2 4
sp bp => 3 0

exit
$

問題ないですね! 次回は引数渡しに戻ります!!!!



vm2gol v2 製作メモ(11) 引数渡しの準備 / bp, push, pop



さて、ダンプ表示が改善されたところで次に進みます。

call, ret で(多段の)サブルーチン呼び出しができたところまでやったので…… 次はサブルーチンに引数で値を渡せるようにします (ここらへんから「C言語のあれをやるには何が必要なんだっけ?」 みたいな感じで進んでいきます)。

(先に言っておくと、今回含め準備があるので実際に引数を渡せるようになるのは次の次の回です)

どうやるかというと、引数はスタックに置いて渡します。 スタックに引数を置いて、呼びだされたサブルーチン側ではそれを見ます。

ここらへんからだんだん難しくなって……というか知らない部分だったので調べました。


第六話:EBPとESP、スタック領域の使われ方|トリコロールな猫|note
https://note.mu/nekotricolor/n/n2a247c808275

x86アセンブリ言語での関数コール
https://vanya.jp.net/os/x86call/


詳しくはリンク先に書いてますので説明は略(ひどい!)!! こんな感じでやっていきましょう!

この、ベースポインタとスタックポインタを使って あれこれやっていく仕組みを知らなかったので、 今回知って、「うおーこんな風になってたのかー」 「スタックと spbp だけでこういうことができるのかー」 と結構感動しました。 今まで(高級言語で)数えきれないほど関数呼び出しやってきたわけですが、 ブラックボックスだった部分が明らかになってうおーってなりました。

呼び出し規約は CDECL っぽくします (適当なので細かい部分は違ってるかもしれません)。


今回動かしたいアセンブリコードはこう。 ★ の箇所が今回の新しい要素です。

# 11_bp_push_pop.vga.txt

  set_reg_a 1
  call sub
  set_reg_b 3
  exit

label sub
  # 前処理
  push bp       # ★
  copy_sp_to_bp # ★

  # サブルーチン本体の処理
  set_reg_a 2

  # 後片付け
  copy_bp_to_sp # ★
  pop bp        # ★

  ret

あれこれ一度にやると大変なので一歩ずつやります。

やることは

  • (1) レジスタを追加: ベースポインタ
  • (2) 命令を追加: copy_sp_to_bp, copy_bp_to_sp
  • (3) 命令を追加: push, pop

ですね。

(1) レジスタを追加: ベースポインタ

まずは bp を追加。

一緒にダンプ表示を修正して bp も表示されるようにします。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -98,6 +98,8 @@ class Vm
     @mem = mem
     # スタックポインタ
     @sp = 3
+    # ベースポインタ
+    @bp = 3
   end
 
   def load_program(path)
--- a/vgvm.rb
+++ b/vgvm.rb
@@ -64,7 +64,7 @@ class Memory
     }.join("\n")
   end
 
-  def dump_stack(sp)
+  def dump_stack(sp, bp)
     lines = []
     @stack.each_with_index do |x, i|
       addr = i
@@ -72,7 +72,13 @@ class Memory
       head =
         case addr
         when sp
-          "sp    => "
+          if sp == bp
+            "sp bp => "
+          else
+            "sp    => "
+          end
+        when bp
+          "   bp => "
         else
           "         "
         end
@@ -190,7 +196,7 @@ class Vm
 ---- memory (main) ----
 #{ @mem.dump_main(@pc) }
 ---- memory (stack) ----
-#{ @mem.dump_stack(@sp) }
+#{ @mem.dump_stack(@sp, @bp) }
     EOB
   end
 

この修正により、こんな感じで bp の位置が表示されるようになります。

---- memory (stack) ----
         0 0
sp    => 1 2
   bp => 2 3
         3 0

(2) 命令を追加: copy_sp_to_bp, copy_bp_to_sp

pushpop の前に簡単な方からやっつけます。

copy_sp_to_bp, copy_bp_to_sp は、名前の通り、 sp の値を bp にコピーするのと、その逆です。 ここは後で整理するのですが、とりあえず素早く曳光弾を通して動かしたい(せっかちなので……)ので 軽率に専用の命令を追加しました。

これらは何も難しいことはないですね。 命令を追加するときは Vm.num_args_for も忘れずに修正します。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -135,6 +135,12 @@ class Vm
         n = @mem.main[@pc + 1]
         @reg_c = n
         @pc += 2
+      when "copy_bp_to_sp"
+        @sp = @bp
+        @pc += 1
+      when "copy_sp_to_bp"
+        @bp = @sp
+        @pc += 1
       when "add_ab"
         add_ab()
         @pc += 1
@@ -174,7 +180,7 @@ class Vm
     case operator
     when "set_reg_a", "label", "call"
       1
-    when "ret", "exit"
+    when "ret", "exit", "copy_bp_to_sp", "copy_sp_to_bp"
       0
     else
       raise "Invalid operator (#{operator})"

(3) 命令を追加: push, pop

次は push

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -167,6 +167,18 @@ class Vm
         ret_addr = @mem.stack[@sp] # 戻り先アドレスを取得
         @pc = ret_addr # 戻る
         @sp += 1 # スタックポインタを戻す
+      when "push"
+        arg = @mem.main[@pc + 1]
+        val_to_push =
+          case arg
+          when "bp"
+            @bp
+          else
+            raise "push: not yet implemented (#{arg})"
+          end
+        @sp -= 1
+        @mem.stack[@sp] = val_to_push
+        @pc += 2
       else
         raise "Unknown operator (#{op})"
       end
@@ -178,7 +190,7 @@ class Vm
 
   def self.num_args_for(operator)
     case operator
-    when "set_reg_a", "label", "call"
+    when "set_reg_a", "label", "call", "push"
       1
     when "ret", "exit", "copy_bp_to_sp", "copy_sp_to_bp"
       0

いきなり pop まで作って動かすのが不安なので、 ここまでの分だけで動作確認してみます。

# 11_test_pop.vga.txt

  push bp
  copy_sp_to_bp
  push bp
  copy_bp_to_sp
  exit

良さそうなので pop に進みます。


--- a/vgvm.rb
+++ b/vgvm.rb
@@ -179,6 +179,16 @@ class Vm
         @sp -= 1
         @mem.stack[@sp] = val_to_push
         @pc += 2
+      when "pop"
+        arg = @mem.main[@pc + 1]
+        case arg
+        when "bp"
+          @bp = @mem.stack[@sp]
+        else
+          raise "pop: not yet implemented (#{arg})"
+        end
+        @sp += 1
+        @pc += 2
       else
         raise "Unknown operator (#{op})"
       end
@@ -190,7 +200,7 @@ class Vm
 
   def self.num_args_for(operator)
     case operator
-    when "set_reg_a", "label", "call", "push"
+    when "set_reg_a", "label", "call", "push", "pop"
       1
     when "ret", "exit", "copy_bp_to_sp", "copy_sp_to_bp"
       0

はい、これで冒頭のコード( 11_bp_push_pop.vga.txt )を動かしてみると……

$ ./run.sh 11_bp_push_pop.vga.txt 
vgvm.rb:208:in `num_args_for': Invalid operator (set_reg_b) (RuntimeError)
        from vgvm.rb:25:in `dump_main'
        from vgvm.rb:225:in `dump_v2'
        from vgvm.rb:116:in `start'
        from vgvm.rb:274:in `<main>'

あ、、、num_args_forset_reg_b を追加しそこねてましたね。 追加します。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -200,7 +200,7 @@ class Vm
 
   def self.num_args_for(operator)
     case operator
-    when "set_reg_a", "label", "call", "push", "pop"
+    when "set_reg_a", "set_reg_b", "label", "call", "push", "pop"
       1
     when "ret", "exit", "copy_bp_to_sp", "copy_sp_to_bp"
       0

これで動くようになりました。 以下は終了時の状態です。

================================
reg_a(2) reg_b(3) reg_c(0) zf(0)
---- memory (main) ----
      00   ["set_reg_a", 1]
      02   ["call", 9]
      04   ["set_reg_b", 3]
pc => 06   ["exit"]
      07 ["label", "sub"]
      09   ["push", "bp"]
      11   ["copy_sp_to_bp"]
      12   ["set_reg_a", 2]
      14   ["copy_bp_to_sp"]
      15   ["pop", "bp"]
      17   ["ret"]
---- memory (stack) ----
         0 0
         1 3
         2 4
sp bp => 3 0

exit

メモ

ふつうのコンパイラをつくろう』 p324

なお、他のアーキテクチャではベースポインタと同様の役割を フレームポインタ(frame pointer)と呼ぶほうが一般的です。 そのため、 gcc のマニュアルやオプションにもフレームポインタという名前がよく登場します。