[パタヘネ:読書メモ]2章　命令：コンピュータの言葉 その3

2012年6月11日

2.8　コンピュータ・ハードウエア内での手続きのサポート


関数の呼び出し


まずは用語の確認

caller             関数の呼び元(親側)
callee             関数の呼び出され側(子供側)
プログラムカウンタ 現在実行中の命令がある場所(address)



関数呼び出しの手続きは以下の流れで行われる。

パラメータのセット  ($a0-$a3レジスタを使用)
手続きに処理を移す
手続きに必要なメモリを確保
手続きの実行
結果のセット        ($v0-$v1レジスタを使用)
制御を元に戻す      ($raにreturn addressが保存されてる)



関数呼び出しは、アセンブラ的にはjal(jamp and link)命令を使用する
この命令で$raにリターンアドレス(プログラムカウンタに4[byte]を加えた値)をセットしてくれる

呼び出された側で呼び元にreturnする時は、”jr $ra”命令を実行する
$a0-$a3に値をセットするのは、もちろんcallerの仕事



スタックの利用


引数として必要な情報が5つ以上ある場合や、戻りの情報が3つ以上ある時は、は$a0-$a3/$v0-$v1に収まらないので、スタック領域を使用してやり取りする。
スタックポインタは$spレジスタで管理しており、大きな番地のアドレスから小さい方に伸びていく。


例題:
以下の関数をアセンブルせよ(g,h,i,jはそれぞれ$a0-$a3とする)

int func( int g, int h, int i, int j ) {
    int f;
    f = ( g + h ) - ( i + j );
    return f;
}



回答例

func: addi $sp, $sp, -12   # 3つ分のスタックエリアを確保(低い番地に伸びるので負数になる)
      sw   $t1, 8($sp)     # 各レジスタ値をスタック領域にpushする
      sw   $t2, 4($sp)
      sw   $s0, 0($sp)
      add  $t0, $a0, $a1   # t0 = g + h;
      add  $t1, $a2, $a3   # t1 = i + j;
      add  $s0, $t0, $t1   # f  = t0 - t1;
      add  $v0, $s0, $zero # v0 = s0;
      lw   $t1, 8($sp)     # 退避したレジスタ値をpopする
      lw   $t2, 4($sp)     #
      lw   $s0, 0($sp)     #
      jr   $ra             # 呼び元にreturnする



自分が使うレジスタの退避と、スタックポインタのずらし作業はcalleeの仕事となる。
関数呼び出しを行うと、上記例のようにレジスタの退避(spilling)が手間になる。MIPSでは、以下のレジスタ以外は関数呼び出しによって破壊しても良い。
ワークで使う$t?レジスタとかまでは、毎回復元しない。

$s0-$s7
$gp
$sp
$fp
$ra
自分および、自分より親側の関数が保存したスタック情報



上記のレジスタを元に戻すのはハードの仕事ではなく、呼び出された関数の仕事


2段以上の関数呼び出し


上記の説明には一部うそがある。関数の最後に”jr $ra”で呼び元に戻っているが、関数呼び出しが3段にネストすると子関数->孫関数の呼び出し時に親関数のリターンアドレスが失われてしまう。
なので、本当は$raもスタックに逃がしておく必要がある。($a0-$a3レジスタも同様)


例題:
以下のコードをアセンブルせよ(階乗の再帰処理)
nは$a0とする

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



回答例

fact: addi $sp, $sp,   -8       # まずは raとa0レジスタを退避(t0は退避する必要なし)
      sw   $ra, 4($sp)          # a0レジスタを退避するのは、自分が後で使うから
      sw   $a0, 0($sp)
 
      slti $t0, $a0,   1        # 引数が1未満?
      beq  $t0, $zero, L1       # false(1以上)だったらL1にジャンプ
 
                                # n < 1の処理
      addi $v0, $zero, 1        # v0 = 1;
      addi $sp, $sp,   8        # スタックの破棄(ra,a0を書き換えてないのでlwは不要)
      jr   $ra
 
 
                                # n >= 1の処理
L1    addi $a0, $a0, -1         # n -= 1
      jal  fact                 # fact( n ); ※戻り値は$v0に入る
 
      lw   $ra, 4($sp)          # レジスタの復元
      lw   $a0, 0($sp)
      addi $sp, $sp,   8        # スタックの破棄
 
      mul  $v0, $v0, $a0        # n * fact( n-1)
 
      jr   $ra                  # 呼び元に戻る



レジスタに定数をセットするには、以下の命令を使用する
$zeroの使いどころをまた1つ見つけた。

addi  $v0, $zero, 1



L1の処理で、a0レジスタを書き換えているので、掛け算しても (n-1) * fact(n-1) になるのでは???
と思ったけど、掛け算する前にlwで元に戻すからOKという仕組みだった。

レジスタの復元は常にjrの直前にしたほうが分かりやすいように感じるんだけど,なぜそうしないんだろう??
使用レジスタを節約したいからぐらいしか思いつかない。
十分な理由にはなるけど、復元処理を途中に挟み込むとコンパイラの実装が大変そう…



Cの変数をCPUで管理する時、型と記憶クラスの解釈が重要になる。
型はその変数が占めるメモリサイズに関係する。

また、記憶クラスはstatic変数とauto変数(=ローカル変数)がある。
staticはプログラムの実行中、ずっと生きてる必要があるけど、その辺の管理を楽にする為に$gp(grobal pointer)が存在している。



再度まとめると、関数呼び出しが行われた後、保持されるレジスタは以下の通り

$s0-$s7
$gp
$sp
$fp
$ra
自分および、自分より親側の関数が保存したスタック情報


$a0-$a3は、保存されない事に注意(呼び出し先側で破壊してもかまわない)

ここで”保持される”というのは、CPUが自動的に保持してくれるという意味ではなく、”呼び出された関数側(callee)で同じ状態に戻しておく義務がある。”という意味なので注意。




配列や構造体の受け渡し


配列や構造体を引数として渡す場合は、レジスタに入りきらないので、これらもスタックに積む必要がある。これらの情報の事をスタックフレーム(stack frame)と呼ぶ(またはactivation record, activation frame,procedure frameとも呼ばれる)。

関数のコールスタックは複数の手続きフレームで構成されていて、退避した$a0-$a3,$raレジスタなどの上に積まれる。そうすると、ある関数をコールした時に、追加されるスタックの大きさは可変になる。スタックの高さは記録されていないので、スタックの底の情報を取りたいときに$spの情報だけだとアクセスできない(offsetが分からないので)。

なので、そのような場合に備えて、スタックの底のアドレスを$fp(frame pointer)レジスタに保存する”ものがある”。 ここで、”ものがある”というのは、前述までの例のように、関数自身で使用するスタックが固定なら、$fpを使わなくても定数値でspの加減算すればやり繰りすることも出来る。

※たしか,javaのバイトコードはメソッド呼び出しの際に、使用するスタックの高さは固定だったはず。
※MIPS向けCコンパイラでも、実装によって$fpの使用有無は異なる。
また、関数の引数が5つ以上ある時は$a0-$a3に収まらないので、この場合はスタックフレームを積む前にスタックに載せ,$fp側からアクセスする。



メモリ空間のセグメント分け


メモリ空間は、その使用目的ごとにセグメント分けされている

text segment        プログラムのコードが入っている領域
 
static data segment static変数(プログラムの実行中、ずっと有効なグローバル情報)
                    定数
                    ヒープ情報
                    スタック情報




2.9　人との情報交換

文字を表現するにはascii,unicodeなどのコード体系を使う。

ascii文字を処理するときはword(32bit)単位ではなく、byte(8bit)単位で処理した方が都合が良い。また、unicodeの場合はhalf word(16bit)単位にアクセスできると便利。

なので、この為のロード命令がある.

lb  (load byte)
lbu (load byte unsigned)
sb  (store byte)
lh  (load half)
lhu (load half unsigned)
sh  (store half)


使い方はlw,swと同様。


例題:
strcpy関数を自作せよ
strcpy関数は、以下の実装とする。
(dest=$a0, src=$a1, i=$s0)

void strcpy( char *dest, char *src ) {
    int i = 0;
    while ( ( dest[i] = src[i] ) != 0x00 ) {
        i++;
    }
}




回答例:

strcpy:
    addi    $sp, $sp, -4    # s0を退避
    sw      $s0, 0($sp)
 
    addi    $s0, $zero, 0   # i = 0;
 
L1:
    addi    $t1, $a1, $s0   # t2 = src[i];
    lbu     $t2, 0($t1)
 
    addi    $t3, $a0, $s0   # t3 = &dest[i];
 
    sb      $t2, 0($t3)     # *t3 = t2;
 
    beq     $t2, 0, L2:     # if ( t2 == 0x00 ) goto L2;
 
    addi    $s0, $s0, 1     # i++;
    j       L1:             # goto L1;
 
L2:
    lw      $s0, 0($sp)     # s0を復元
    addi    $sp, $sp, -4
 
    jr      $ra             # return



strcpyは1byteづつ処理を行う。

strcpyは、ここからコールされる子関数がないので、リーフ処理になる。
この場合レジスタの退避･復元の省略が出来る。


また、MIPSではスタックの値は4byte境界でアライメントが整えられる。
なので1byteのcharをパラメータとして渡す場合でも4byte消費する。

4822284786
コンピュータの構成と設計（上）

関連記事
同じカテゴリの記事はこちらから!! → 読書メモ タグ:

コメントを残す

メールアドレスが公開されることはありません。