アセンブリ言語その2 - kivantium活動日記

この記事はkivantium Advent Calendarの19日目です。

前回は最初のCPUの設計に使う命令セットを紹介しました。
今回はこの命令を使っていろいろなプログラムを書いてみます。

SPIM

ここではMIPSのシミュレータとして有名なSPIM (MIPSを逆から読んだ名前) を使うことにします。
GUIがついたQtSPIMをダウンロード・インストールします。

QtSPIMはアセンブリで書いたテキストファイルを読み込んで実行します。
実行したいファイルを保存して、File > Reinitialize and Load Fileとすることでファイルが読み込まれます。
再生ボタンのようなRun/Continueを押すと実行されます。

最初のプログラム

まずはHello, World代わりに数字の1を表示することにします。

    .text                   # アセンブリ命令がここから始まることを示す
main:                       # main関数を表すラベル
    addiu $a0, $zero, 1     # $a0 に $zero+1 (=1) を入れる
    addiu $v0, $zero, 1     # $v0 に $zero+1 (=1) を入れる
    syscall                 # システムコール (print_int)
    addiu $v0, $zero, 10    # $v0 に $zero+10 (=10) を入れる
    syscall                 # システムコール (exit)

syscallは$v0に入っている値に応じて異なる処理を行います。
SPIMの場合は1で$a0に入っている整数を表示するprint_int、10でプログラムを終了するexitになります。
実装するCPUにはsyscall命令はありませんが、SPIMで結果を表示するためにしばらく使うことにします。

これを実行すると

となって、意図通り1が表示されます。

演算命令を使う例

演算命令はレジスタに演算を行った結果をレジスタに格納します。

    .text                   # アセンブリ命令がここから始まることを示す
main:                       # main関数を表すラベル
    addiu $s0, $zero, 1     # $s0 に $zero+1 (=1) を入れる
    addiu $s1, $s0, 2       # $s1 に $s0+2 (=3) を入れる
    addu  $s1, $s0, $s1     # $s1 に $s0+$s1 (=4) を入れる
    sll   $a0, $s1, 2       # $a0 に $s1 を2bit左にシフトした値 (=16) を入れる
    addiu $v0, $zero, 1     # $v0 に $zero+1 (=1) を入れる
    syscall                 # システムコール (print_int)
    addiu $v0, $zero, 10    # $v0 に $zero+10 (=10) を入れる
    syscall                 # システムコール (exit)

これを実行すると

となります。

ロード・ストア命令

ロード命令は指定したアドレスのメモリ値をレジスタに入れ、ストア命令はレジスタの値を指定したアドレスに入れます。

    .text                   # アセンブリ命令がここから始まることを示す
main:                       # main関数を表すラベル
    addiu $s0, $zero, 1     # $s0 に $zero+1 (=1) を入れる
    sw    $s0, -4($sp)      # $s0 の値をメモリアドレスが $sp-4 の領域に入れる
    lw    $a0, -4($sp)      # $a0 にメモリアドレスが $sp-4 の領域の値を入れる
    addiu $v0, $zero, 1     # $v0 に $zero+1 (=1) を入れる
    syscall                 # システムコール (print_int)
    addiu $v0, $zero, 10    # $v0 に $zero+10 (=10) を入れる
    syscall                 # システムコール (exit)

$spは後で説明するスタックポインタが入っているレジスタです。同じ場所にストアしてからロードしているので出力は

となります。

ジャンプ命令とラベル

ジャンプ命令は次の命令のアドレスを指定してプログラムカウンタを変更します。
命令のアドレスを数字で明示的に書くのは大変なので普通はラベルを使用します。

    .text                   # アセンブリ命令がここから始まることを示す
main:                       # main関数を表すラベル
    addiu $s0, $zero, 1     # $s0 に $zero+1 (=1) を入れる
    j     jumpto            # jumpto というラベルまでジャンプ
    addiu $s0, $zero, 2     # $s0 に $zero+2 (=2) を入れる
jumpto:                     # ジャンプ先のラベル
    addiu $a0, $s0, 0       # $a0 に $s0+0 (=$s0) を入れる
    addiu $v0, $zero, 1     # $v0 に $zero+1 (=1) を入れる
    syscall                 # システムコール (print_int)
    addiu $v0, $zero, 10    # $v0 に $zero+10 (=10) を入れる
    syscall                 # システムコール (exit)

これを実行すると

が表示されます。jumpの次の行の$s0に2を入れる処理がジャンプで飛ばされていることが確認できます。

条件分岐命令

条件分岐命令は比較結果に応じて次のプログラムカウンタを変更する命令です。

    .text                    # アセンブリ命令がここから始まることを示す
main:                        # main関数を表すラベル
    addiu $s0, $zero, 1      # $s0 に $zero+1 (=1) を入れる
    addiu $s1, $zero, 2      # $s1 に $zero+2 (=2) を入れる
    beq   $s0, $s1, if_equal # $s0 と $s1 が等しければif_equalへ行く
    addiu $a0, $zero, 0      # $a0 に $zero+0 (=0) を入れる
    j     display            # display にジャンプ
if_equal:                    # ラベル
    addiu $a0, $zero, 1      # $a0 に $zero+1 (=1) を入れる
display:                     # ラベル
    addiu $v0, $zero, 1      # $v0 に $zero+1 (=1) を入れる
    syscall                  # システムコール (print_int)
    addiu $v0, $zero, 10     # $v0 に $zero+10 (=10) を入れる
    syscall                  # システムコール (exit)

これはC言語でいうと

s0 = 1; s1 = 2;
if(s0 == s1) a = 1;
else         a = 0:
printf("%d", a);

をアセンブリで書いたイメージです。実行結果は

となります。

関数呼び出し

アセンブリでの関数は「特定のレジスタに引数を入れた状態で関数の動作が書かれた部分にジャンプした後、特定のレジスタに戻り値を入れた状態で元の場所に戻る処理」として表現されます。
MIPSの場合、引数は$a0〜$a3に、戻り値は$v0〜$v1に入れることになっています。

簡単な例を見てみます。

    .text                    # アセンブリ命令がここから始まることを示す
main:                        # main関数を表すラベル
    addiu $a0, $zero, 1      # $a0 に $zero+1 (=1) を入れる
    jal   func               # funcを呼び出す
    addu  $a0, $v0, $zero    # a0 に $v0 (戻り値) を入れる
    addiu $v0, $zero, 1      # $v0 に $zero+1 (=1) を入れる
    syscall                  # システムコール (print_int)
    addiu $v0, $zero, 10     # $v0 に $zero+10 (=10) を入れる
    syscall                  # システムコール (exit)
func:
    sll   $v0, $a0, 1        # $v0 に $a0 を左に1bitシフトした値を入れる
    jr    $ra                # $ra (関数を呼び出した次のアドレスが入る)にジャンプ

これはC言語でいうと

int func (int a) {
    return a << 1;
}
int main(void) {
    printf("%d", func(1));
}

に対応するコードのイメージです。結果は

となります。

関数を呼び出した後に元の位置に戻ることができるのはjal命令で$raに関数呼び出しの次のアドレスを格納しているため、関数が終わるときにjr命令で$raの値にジャンプできるからです。関数呼び出しが1回であればこの方法でいいのですが、呼び出した関数の中でもう一度関数を書くと$raが上書きされてしまいリターンアドレスが分からなくなってしまいます。これを回避するためにコールスタックと呼ばれるデータ構造を使います。

最後に格納した情報が最初に出てくるデータ構造をスタックといいます。スタックを用いると、関数を呼び出す際にリターンアドレスをスタックに入れて、関数を終了するときにスタックからリターンアドレスを取り出せばいくつ関数を呼び出しても正しい順番で戻ることができます。スタックをメモリ上に作るためにスタックポインタとフレームポインタという2つの値を使います。

スタックポインタはスタックの最下端のアドレスを表していて、スタックにデータを積むたびに値が減らされ、スタックからデータを取り出すと値が増やされます。
一つの関数を呼び出すたびにスタックに積まれるデータのひとかたまりをスタックフレームと呼び、フレームポインタからスタックポインタの間のアドレスがスタックフレームとなるようにフレームポインタの間の値がセットされます。

関数を呼び出すたびにリターンアドレス・フレームポインタ・スタックポインタをスタックに保管しておけば関数を呼び出しても復帰先が分からなくなることはありません。
スタックはリターンアドレスの他にもレジスタに入りきらない引数や退避したい変数を格納するのにも使います。
SPIMではmain関数が始まった時点で$spと$fpにその時のスタックポインタ・フレームポインタが入っています。

その他、ヒープ領域などのアドレス空間なども説明した方がいいかもしれませんが、今後の話に関係ないので省略します。

ではこれを使って再帰を使ったフィボナッチ数を計算する例を紹介します。
C言語のイメージコードは

int fib(int n) {
    if(n < 2) return 1;
    else return fin(n-1)+fib(n-2);
}
int main(void) {
    for(int i=0; i<15; i++) {
        printf("%d\n", fib(i));
    }
}

です。

アセンブリは

    .text
    .globl main
main:
    # スタックフレームの作成
    addiu   $sp, $sp, -32   # スタック領域を下に32 byte伸ばす
    sw      $ra, 20($sp)    # リターン・アドレスを退避
    sw      $fp, 16($sp)    # フレーム・ポインタを退避
    addiu   $fp, $sp, 28    # 新しいフレーム・ポインタを設定
    addiu   $s0, $zero, 0
    addiu   $s1, $zero, 10
    addiu   $s2, $zero, 2
loop:
    beq     $s0, $s1, end
    addu    $a0, $s0, $zero # fibの引数に$s0を設定
    jal     fib             # fibを呼び出す
    addu    $a0, $v0, $zero # fibの結果をa0に移動
    addiu   $v0, $zero, 1   # syscallでprint_intを呼び出す設定
    syscall                 # print_intでa0(fibの結果が入る)を出力
    addiu   $a0, $zero, 10 
    addiu   $v0, $zero, 11
    syscall
    addiu   $s0, $s0, 1
    j       loop
end:
    lw      $ra, 20($sp)    # 退避したリターン・アドレスを復元
    lw      $fp, 16($sp)    # 退避したフレーム・ポインタを復元
    addiu   $sp, $sp, 32    # スタック領域を32 byte短くする
    jr      $ra             # 呼び出し元に戻る
# fib関数
fib:
    addiu   $sp, $sp, -32   # スタック領域を下に32 byte伸ばす
    sw      $ra, 20($sp)    # リターン・アドレスを退避
    sw      $fp, 16($sp)    # フレーム・ポインタを退避
    addiu   $fp, $sp, 28    # 新しいフレームポインタを設定
    sw      $a0, 0($fp)     # a0 (引数)を退避
    slt     $t0, $a0, $s2   # (次の行と合わせて) a0<2ならば$L2にジャンプ
    beq     $t0, $zero, L2      
    addiu   $v0, $zero, 1   # (ここはa0==0のとき実行される) v0(戻り値)に0を入れる
    j       L1              # $L1にジャンプ
# fibの再帰部分
L2:
    lw      $a0, 0($fp)     # 退避しておいたnを$a0に入れる
    addiu   $a0, $a0, -1    # $a0 <- $a0 - 1
    jal     fib             # fib(n-1)の再帰呼出し
    sw      $v0, 4($fp)     # fib(n-1)の戻り値を退避
    lw      $a0, 0($fp)     # 退避しておいたnを$a0に入れる
    addiu   $a0, $a0, -2    # $a0-2を求める
    jal     fib             # fib(n-2)の再帰呼出し
    lw      $v1, 4($fp)     # v1に退避しておいたfib(n-1)の値を入れる
    addu    $v0, $v0, $v1   # v0(fib(n-2)の戻り値)にfib(n-1)の値を足す
# fib関数の終了処理
L1:
    lw      $ra, 20($sp)    # 退避したリターン・アドレスを復元
    lw      $fp, 16($sp)    # 退避したフレーム・ポインタを復元
    addiu   $sp, $sp, 32    # スタック領域を32 byte短くする
    jr      $ra             # 呼び出し元に戻る

結果は