【アセンブリ】再帰で10の階乗を求めるプログラムを通して手続き呼び出し規約を理解する学習ノート【MIPS】

まず、再帰的な構造を持つプログラムを作るにあたって、手続き呼び出し規約をしっかりと理解しなければいけないらしい。レジスタ使用規約って、言われた方が自分にとってはピンと来るけども。

Patteron&Hennesy本の日本語訳verでは手続き呼び出し規約って単語が使われているので、自分もそちらで進むことにする。

よっしゃ、ということで手続き呼び出し規約に従うことを意識しながらPatterson&Hennesy本に沿って再帰で階乗を求めるプログラムに自分の解釈（理解）を添えながら読み進めていってみる。

C言語のソースコード

C言語で以下のように実現できるプログラムを作っていく。

main()
{
  printf("The factorial of 10 is %d\n", fact(10));
}

int fact(int n)
{
    if (n < 1)
        return 1;
    else
        return n * fact(n-1);
}

main編

まず、呼び出し手続き規約に従って処理をする３つの局面をおさえておくことにする。

This convention comes into play at three pointes during a procedure call: immediately before the caller invokes the callee, just as the callee starts executing, and immediately before the callee returns to the caller.

(Location 14781)

とあるように

① 呼び出し側が手続きを呼び出す直前 ② 被呼び出し側がスタートした直後 ③ 被呼び出し側が呼び出し側に戻る直前

の３つで規約に従った処理を行わなければならない。

じゃあ順番に読んで、解釈していく。

スタックフレームの生成

被呼び出し側（今回はmainが呼ばれている）がスタックフレームを生成する過程で最初にすることは以下。これは最初に言及した局面の②にあたる。

Before a called routine starts running, it must take the following steps to set up its stack frame:

Allocate memory for the frame by subtracting the frame's size from the stack pointer.

Save callee-saved registers in the frame. A callee must save the values in these registers ($s0-$s7, $fp, and $ra) before altering them, since the caller expects to fnd these registers unchanged after the call. Register $fp is saved by every procedure that allocates a new stac frame. However, register $ra only needs to be saved if the callee itself makes a call. The other callee-saved registers that are used also must be saved.

Establish the frame pointer by adding the stack frame's size minus 4 to $sp and storing the sum in register $fp.

(Location 14787)

以下ソースコード。

  .text
  .globl main
main:
  subu  $sp, $sp, 32  # (1) Length of stack frame: 32 bytes
  sw    $ra, 20($sp)  # (2) Save return address (戻りアドレスを退避)
  sw    $fp, 16($sp)  # (2) Save old frame pointer (古いフレームポインタを退避)
  addiu $fp, $sp, 28  # (4) Set up frame pointer

まず最初のパートではmainルーチンで前処理的なこと（スタックフレームの生成）をやってる。

なぜスタックフレームを生成するときに$spから値を引くのかについては以下の記事で別に考察する。この記事で同時に、20($sp)とかでスタックにアクセスする方法についても触れる。

【アセンブリ】スタックフレームを生成するときにスタックポインタから値を引く理由【MIPS】 - 凸ろぐ

ヘネパタ本の

Register $fp is saved by every procedure that allocates a new stac frame. However, register $ra only needs to be saved if the callee itself makes a call.

という部分は大事な気がする。なんで$fpは必ず退避しないといけないんだろう。呼び出し側がさらに呼び出し側になる場合$raが対比される必要はあるのは納得できるしそれ以外の時は退避する必要がないのも納得出来るけど。。。

そしてここでの大きなポイントは、addiuで$fpに足すのは スタックフレームの長さ - 4バイト ってなってるところ。

上の記事の、前処理を済ませた段階のスタックフレームの状態を示した画像を見ればわかるが、長さ32バイトの場合は、最初のスタックは28バイト目が先頭になっている。だから下位の回想である$spに28を足すことで、スタックの先頭、一つ目を$fpが指すようにフレームポインタを設定できる。

メインの処理

mainからfact関数を呼び出すので、今度はmainが呼び出し側になる。

①でみたように、関数を呼び出す直前に、手続き呼び出し規約に従って呼び出し側はスタックフレームを生成しなければならない。

することは以下の３つ。

Pass arguments. By convention, the first four arguments are passed in registers $a0-$a3. Any remaining arguments are pushed on the stack and appear at the beginning of the called procedure's stack frame.

Save caller-saved registers. The called procedure can use these registers($a0-$a3 and $t0-$t9) without first saving their value. If the caller expects to use one of these registers after a call, it must save its value before the call.

Execute a jal instruction (see Section 2.8 of Chapter 2), which jumps to the callee's first instruciton and saves the return address in register $ra.

ということで以下ソース

  li    $a0, 10       # (1) Put argument (10) in $a0
  jal   fact          # Call factorial function

  la    $a0, $LC      # Put format string in $a0
  move  $a1, $v0      # Move fact result to $a1
  jal   printf        # Call the print function

10を$a0に入れる。$a0は確か...引数だったな。fact関数で使う値を渡してるわけだ。(1)

ここでは呼び出し側で、被呼び出し側で使う値（$a0-$a3と$t0-$t9)を事前に保存（退避）しておく。これは $t系のレジスタが被呼び出し側で使われて、変更されたとしても呼び出し側に戻ってきたときにそれを復元してもとの値として使えるようにするためだ。要するに「$aと$t系レジスタは呼び出し間では保存されない」という規約を自分で作らないといけないわけだ。アセンブリ原子的（はーと）

1と2でしてることが混同していたけど、1は被呼び出し側に引数を渡すための処理で、2は呼び出し側に戻ってきたときも$a系と$t系をもとの値でキープするために退避させる処理なわけやな。　

$a0を退避させていないようだけど、これは引数としてしか使わないからいいのかな？

そしてfactのラベルをつけた場所、factルーチンに入る。(3)

factから抜けだしたらprintfを呼んで結果を表示してるわけだけど、$LCの意味がわからんで。コメントには「format stringを$a0に突っ込む」とある。なるほどこの後出てくるLCラベルでasciiで出力する文字のフォーマットを保存した。ここではそれを呼び出して$a0に格納しているんだろう(1)。こんな使い方もできるのね。

$v0は返り値を入れるとこだからfactルーチン内で計算された値がこれに入ってるはず。これをprintfルーチンで使うために$a1に移してる（実際の処理的には写してる？）(1)わけだ。

そしてjalでprintfを読み込む(3)

スタックフレームの事後処理

そしたらmainルーチンを抜ける。と、抜ける前にいくつか処理が必要らしい。

Finally, after pointing the factorial, main returns. But first, it must restore the registers it saved and pop its stack frame.

最後に被呼び出し側（今回はmainが呼ばれている）が呼び出し側に戻る前に踏む手順は以下

If the calle is a function that returns a value, place the returned value in register $v0.

Restore all callee-saved registers that were saved upon procedure entry.

Pop the stack frame by adding the frame size to $sp

Return by jumping to the address in register $ra

(Location 14804)

と書いてる。返り値ってひとつしか無理なのかな？あとはスタック使うとかして一応実現はできそうだけど。

  lw    $ra, 20($sp)  # (2) Restore return address
  lw    $fp, 16($sp)  # (2) Restore frame pointer
  addiu $sp, $sp, 32  # (3) Pop stack frame
  jr    $ra           # (4) Return to caller

  .rdata
$LC:
  .ascii  "The factorial of 10 is %d\n\000"

mainは返り値がないので1はなし。(1)

lwでさっきスタックに格納（退避）しておいた戻りアドレス$raとフレームポインタ$fpを元あるべき場所に戻す。(2)

そしたらスタックフレームを全部元どおり（サイズ０）にする。$spに32足したら前確保した分が詰まって元どおりに。(3)

そしたらjrでmainの値を返してプログラム終了。(4)

fact編

そしてfactルーチンへいよいよ。

スタックフレーム生成編

mainの最初でやったこと局面②と同じ。被呼び出し側がする最初の処理を行いスタックフレームを生成する。

やることは以下。

スタックフレームを生成 (1)
$raと$fpを退避 (2)
$fpを設定 (3)
$a0を退避 -> 再帰でつかうため

  .text
fact:
  subu  $sp, $sp, 32 # (1) Stack frame is 32 bytes long
  sw    $ra, 20($sp) # (2) Save return address
  sw    $fp, 16($sp) # (2) Save frame pointer
  addiu $fp, $sp, 28 # (3) Set up frame pointer
  sw    $a0, 0($fp)  # (2) Save argument (n)

戻りアドレスを退避するときに、最初の$ra上書きされるやん、って思ったけど、P.765にこんな記述が。

MIPSのレジスタ使用規約では、呼び出し側退避レジスタと被呼び出し側退避レジスタを設けている。(P. 765)

The MIPS register use convention provides callee- and caller-saved registers, because both types of registers are advantageous in different circumstances.

ってことでここでは呼び出し側であるmainで退避した$raは上書きされず、factルーチンで保存（退避）された戻りアドレスは被呼び出し側レジスタに格納されるってことなのかな。

便利ですな、どうなってんだろ。

そして最後に、再帰でつかうために$a0も退避してる。これは再帰特有かなー。

メインの処理

そしたらついについに計算と値を返すところ。

  lw    $v0, 0($fp)  # Load n
  bgtz  $v0, $L2     # Branch if n > 0
  li    $v0, 1       # Return 1
  jr    $L1          # Jump to code to return

まず、スタックに格納していた$a0つまり引数nを$v0に読み込む。で$v0が0より大きかったら$L2にジャンプする。

$L2:
  lw    $v1, 0($fp)   # Load n
  subu  $v0, $v1, 1   # Compute n - 1
  move  $a0, $v0      # Move value to $a0
  jal   fact          # Call factorial function

  lw    $v1, 0($fp)   # Load n
  mul   $v0, $v0, $v1 # Compute fact(n-1) * n

$L2は再帰の処理。

またnの値を呼び出して今度は$v1に格納。飛ぶ前にスタックから取り出した値$v0に、$v1-1を行いnの値を更新。

返す値とするため$v0の値を$a0に移動。

そしたらまたfactに飛ぶ。

スタックフレーム事後処理

nが1より小さくなったらついに最後の処理。

$L1:                  # Result is in $v0
  lw    $ra, 20($sp)  # Restore $ra
  lw    $fp, 16($sp)  # Restore $fp
  addiu $sp, $sp, 32  # Pop stack
  jr    $ra

被呼び出し側が値を返す直前にやる処理を行う。

printf編

printfルーチンがないのでこのままでは実行できないと思うので作っておこう。

引数はmain部分で$a0にformat stringを、$a1にfact resultを格納した。

前やったsyscallのノートを参考にしながら...

printf:
  li    $v0, 4        # syscall of print_string
  lw    $a0, 0($fp)   # Load format string
  syscall             # Print format string
  li    $v0, 1        # syscal of print_int
  lw    $a1, 4($fp)   # Load n
  syscall             # Print n

と思ったら、呼び出し手続き規約に従うのを忘れてた笑

factでやったことを参考にしながら（というかコピーしながら...笑）

  .text
printf:
  subu  $sp, $sp, 32 # Stack frame is 32 bytes long
  sw    $ra, 20($sp) # Save return address
  sw    $fp, 16($sp) # Save frame pointer
  addiu $fp, $sp, 28 # Set up frame pointer
  
  li    $v0, 4        # syscall of print_string
  syscall             # Print format string
  li    $v0, 1        # syscal of print_int
  move  $a0, $a1      # Move $a1 to $a0 for syscall
  syscall             # Print n

  lw    $ra, 20($sp)  # Restore $ra
  lw    $fp, 16($sp)  # Restore $fp
  addiu $sp, $sp, 32  # Pop stack
  jr    $ra

こんな感じかなー。テストしてみよう。

ちょっと$LCいじったけど、出力は以下。

The factorial of 10 is 3628800

最終的なコード

ということで最終的なコード貼っておきます

10の階乗を求めるプログラム for 手続き呼び出しの練習

学んだこと

なぜこんなめんどい規約が必要？

C言語の関数のような機能を実現するために手続き呼び出し規約はできた、と認識してもいいんじゃないかと思う。

他多くのプログラミング言語でも実装されているこのような機能を、レジスタがぶつかったりせずうまくコンパイルしてアセンブリとして実現するために、手続き呼び出し規約なるややこしいものが必要になった。ということ。

やること

コンピュータハードウェア内での手続きのサポートのために手続き間で以下の方法を定めておく必要がある

引数の渡し方，戻り値の受け取り方
呼出し元への戻り方
手続き内でのレジスタの保存

疑問点

- なぜ引く？

スタックポインタからフレームのサイズを引いて、フレーム用にメモリを割り当てる (p. 764)

スタックフレームは低位から高位のメモリアドレスにフーレムを生成する。$fpは最初初期値が$spと同じように設定されていて、$spから引いた数の分だけ$spと$fpの差は開き、そこがフーレムとして生成される、とか？

考察

【アセンブリ】スタックフレームを生成するときにスタックポインタから値を引く理由【MIPS】 - 凸ろぐ

- スタックフレームの大きさはなぜ24バイト以上？8バイト単位？

手続き呼び出し規約にスタックフレームの大きさは24バイト以上と定められている (P.766)

Patterson&Hennessy本によると

この最低限のフレームに４つの引数レジスタ ($a0 - $a3) と戻りアドレス$raを、倍長語の境界に整列化して持たせることができる。mainでは$fpも退避する必要があるので、スタックフレームを2語分大きくしなければならない。（スタックフレームは倍長語の境界に整列化されることに留意）(P.766)

The frame is larger than required for these two register because the calling convention requires the minimum size of a stack frame to be 24 bytes. This minimum frame can hold four argument registers ($a0-$a3) and the return address $ra, padded to a double-word boundary (24 bytes). Since main also needs to save $fp, its stack frame must be two words larger (remember: the stack pointer is kept doubleword aligned).

って書いてる。正直意味がわからん笑

考察

【アセンブラ】スタックフレームの大きさはなぜ24バイト以上？8バイト単位？【MIPS】[アセンブラ] - 凸ろぐ

- $LCってなに / ラベルのダラーマーク

  la    $a0, $LC      # Put format string in $a0

~~コメントから予想するに、レジスタをフォーマットするときに使うのかな？~~

とか思ったけどそのあとにラベルが出てきたのでなんとなくわかった。こんな使い方もできるのか。。

- 関数が返せる引数はひとつ？

スタックを使えば複数の値も返せるか

- なぜ$fpは必ず退避させなければならない？

なんで$fpは必ず退避しないといけないんだろう。呼び出し側がさらに呼び出し側になる場合$raが対比される必要はあるのは納得できるしそれ以外の時は退避する必要がないのも納得出来るけど。。。

- mainからfactを呼ぶとき$a0は退避しない？

$a0を退避させていないようだけど、これは引数としてしか使わないからいいのかな？

- $fpの使い方

上から順番に0($fp)、1($fp)ってなる？

珈琲駆動開発

CDD

【アセンブリ】再帰で10の階乗を求めるプログラムを通して手続き呼び出し規約を理解する学習ノート【MIPS】

C言語のソースコード

main編

スタックフレームの生成

メインの処理

スタックフレームの事後処理

fact編

スタックフレーム生成編

メインの処理

スタックフレーム事後処理

printf編

最終的なコード

学んだこと

なぜこんなめんどい規約が必要？

やること

疑問点

- なぜ引く？

考察

- スタックフレームの大きさはなぜ24バイト以上？8バイト単位？

考察

- $LCってなに / ラベルのダラーマーク

- 関数が返せる引数はひとつ？

- なぜ$fpは必ず退避させなければならない？

- mainからfactを呼ぶとき$a0は退避しない？

- $fpの使い方