vm2gol v2 製作メモ(9) 2段以上のサブルーチン呼び出し / スタック領域とスタックポインタ


前回簡単なサブルーチンをやりましたが、 今回はサブルーチンからまた別のサブルーチンを呼ぶ、 というのをやってみたいです。 これも普通にできてほしい。

今の状態ではこれはできません。 なぜかというと、 ret で戻るときの戻り先アドレスを reg_c に入れているからです。 このまま2段目のサブルーチン呼び出しをやってしまうと、 call のときに reg_c が上書きされてしまい、2段目からは戻れても そこから1段目に正しく戻れません。

そこで、スタック領域というものを用意します。

メインメモリの末尾の方をスタック領域として使うのが一般的っぽいのですが、 ここではメインメモリとは別にスタック領域を用意します。 なぜならその方が簡単そうだから(どっちでもあんまり変わらない?)。 我々(?)は初心者なので難しそうなことをやってはいけません。

まあ、いったんこれで作っておいて後から変えることもできなくはなさそうです。


はい。ではやります。

まずスタック領域を用意します。 メインメモリと同じくただの配列です。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -16,6 +16,8 @@ class Vm
     @zf = 0
 
     @mem = []
+    # スタック領域
+    @stack = Array.new(4, 0)
   end
 
   def load_program(path)

スタック領域のサイズはとりあえず 4 としました。かわいいスタックです。

それから、スタック領域の先頭がどこなのかを記憶しておく必要があるので、 その位置を保存しておくレジスタ、スタックポインタを追加します。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -18,6 +18,8 @@ class Vm
     @mem = []
     # スタック領域
     @stack = Array.new(4, 0)
+    # スタックポインタ
+    @sp = 3
   end
 
   def load_program(path)

スタック領域のサイズを 4 としたので、 スタックポインタの初期値は、スタックの「底」である 3 を指すようにしておきます。 次の図のようなイメージです。

f:id:sonota88:20190519121326p:plain
図 9-1 スタック領域の初期状態


それから、 callret を書き換えて reg_c ではなくスタック領域を使うようにします。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -66,11 +66,14 @@ class Vm
         addr = @mem[@pc + 1]
         jump_eq(addr)
       when "call"
-        @reg_c = @pc + 2 # 戻り先を記憶(call ではなく、その次の命令になるように)
+        @sp -= 1 # スタックポインタを1減らす
+        @stack[@sp] = @pc + 2 # 戻り先を記憶
         next_addr = @mem[@pc + 1] # ジャンプ先
         @pc = next_addr
       when "ret"
-        @pc = @reg_c
+        ret_addr = @stack[@sp] # 戻り先アドレスを取得
+        @pc = ret_addr # 戻る
+        @sp += 1 # スタックポインタを戻す
       else
         raise "Unknown operator (#{op})"
       end
  • sp から 1 を引いて戻り先アドレスをセット
  • 戻り先アドレスを取り出して sp に 1 を足す

が対になっているのがミソですね。


あわせてダンプ表示をいじります。 追加で @mem[@pc], @sp, @stack[@sp] も表示します。

--- a/vgvm.rb
+++ b/vgvm.rb
@@ -85,10 +85,12 @@ class Vm
   end
 
   def dump
-    puts "pc(%2d) | reg_a(%d) b(%d) c(%d) | zf(%d)" % [
+    puts "%- 10s | pc(%2d) | reg_a(%d) b(%d) c(%d) | zf(%d) | sp(%d,%d)" % [
+      @mem[@pc],
       @pc,
       @reg_a, @reg_b, @reg_c,
-      @zf
+      @zf,
+      @sp, @stack[@sp]
     ]
   end
 

機械語コードを書いて……

# 09_nested_call.vge.yaml

[
  "set_reg_a", 1,
  "call", 9, # sub1
  # 4 sub1 からここに戻って来るはず
  "set_reg_a", 5,
  "exit",

  # 7
  "label", "sub1",
  # 9
  "set_reg_a", 2,
  "call", 18, # sub2
  # 13 sub2 からここに戻って来るはず
  "set_reg_a", 4,
  "ret",

  # 16
  "label", "sub2",
  # 18
  "set_reg_a", 3,
  "ret"
]

動かしてみます。

$ ruby vgvm.rb 09_nested_call.vge.yaml
set_reg_a  | pc( 0) | reg_a(0) b(0) c(0) | zf(0) | sp(3,0)
call       | pc( 2) | reg_a(1) b(0) c(0) | zf(0) | sp(3,0)
set_reg_a  | pc( 9) | reg_a(1) b(0) c(0) | zf(0) | sp(2,4)  … call されて @pc が変更され、
                                                               スタック領域に sub1 からの戻り先アドレスがセットされた
call       | pc(11) | reg_a(2) b(0) c(0) | zf(0) | sp(2,4)
set_reg_a  | pc(18) | reg_a(2) b(0) c(0) | zf(0) | sp(1,13) … call されて @pc が変更され、
                                                               スタック領域に sub2 からの戻りアドレスがセットされた
ret        | pc(20) | reg_a(3) b(0) c(0) | zf(0) | sp(1,13)
set_reg_a  | pc(13) | reg_a(3) b(0) c(0) | zf(0) | sp(2,4)  … ret により sub2 から戻った
ret        | pc(15) | reg_a(4) b(0) c(0) | zf(0) | sp(2,4)
set_reg_a  | pc( 4) | reg_a(4) b(0) c(0) | zf(0) | sp(3,0)  … ret により sub1 から戻った
exit       | pc( 6) | reg_a(5) b(0) c(0) | zf(0) | sp(3,0)
exit

いいですねー。 reg_a の値も 1, 2, 3, 4, 5 と予想どおりに変わっています。

ではアセンブリコードからやってみましょう。 今回はジャンプまわりの変更がないのでアセンブラの修正は不要でそのまま動くはず。

# 09_nested_call.vga.txt

  set_reg_a 1
  call sub1   # sub1 を呼び出し
  set_reg_a 5 # sub1 からここに戻って来るはず
  exit

label sub1
  set_reg_a 2
  call sub2   # sub2 を呼び出し
  set_reg_a 4 # sub2 からここに戻って来るはず
  ret

label sub2
  set_reg_a 3
  ret
$ ./run.sh 09_nested_call.vga.txt
set_reg_a  | pc( 0) | reg_a(0) b(0) c(0) | zf(0) | sp(3,0)
call       | pc( 2) | reg_a(1) b(0) c(0) | zf(0) | sp(3,0)
set_reg_a  | pc( 9) | reg_a(1) b(0) c(0) | zf(0) | sp(2,4)
call       | pc(11) | reg_a(2) b(0) c(0) | zf(0) | sp(2,4)
set_reg_a  | pc(18) | reg_a(2) b(0) c(0) | zf(0) | sp(1,13)
ret        | pc(20) | reg_a(3) b(0) c(0) | zf(0) | sp(1,13)
set_reg_a  | pc(13) | reg_a(3) b(0) c(0) | zf(0) | sp(2,4)
ret        | pc(15) | reg_a(4) b(0) c(0) | zf(0) | sp(2,4)
set_reg_a  | pc( 4) | reg_a(4) b(0) c(0) | zf(0) | sp(3,0)
exit       | pc( 6) | reg_a(5) b(0) c(0) | zf(0) | sp(3,0)
exit

さっきと同じ結果になっています。OK!

いやー、スタック領域を導入するだけで入れ子の呼び出しができてしまいました。 意外と簡単ですね?