それわかるぅ〜

日々「それわかるぅ〜」と思ったこと、忘れたくないことを徒然なるままに。Inputした情報を定着させるためのOutputの場として使用しています。誤字脱字等はたぶん仕様です。

コンパイラ作成のメモ書き

実験でコンパイラを作成した過程で必要になった事項を適当にまとめておく。
関数フレームとは実験で使う仕様に変更して書いてあるので一般的なものとすこし仕様が違うからちょっと注意。あと最後に例が少なくて本当に苦労したので実際のプログラムをアセンブリに変換するとどうなるかも一応挙げておく。

アセンブリ基本編

jal (手続きのラベル)

手続きのアドレスにジャンプ 。同時に次の命令のアドレスを$raに退避

jr $ra

$raに記録されているアドレスにジャンプ。ちなみに$raは関数呼び出しを行った場所の次の命令のアドレスが入っているレジスタ。また、$spはスタックポインタの値が入っているレジスタレジスタ29)レジスタの値が退避、復元される度に一語文増減される。

関数フレームの構造(低アドレス側から)

  • $spはフレームの先頭、$fpは引数の先頭
  • $fpの退避場所は4($sp)
  • $raの退避スペース
  • 局所変数のアクセスは0($fp)、-4($fp)等、引数のアクセスは4($fp)、8($fp)等 であることに注意して関数本体のアセンブリを書くと、
subu $sp,$sp,(フレームサイズ)
sw $ra,4($sp)
sw $fp,0($sp) 
addiu $fp,$sp,(局所変数の数-1)*4)
~~~~~~~~~~~~~~~~~~~~

この間に関す本体のコードを書いて

~~~~~~~~~~~~~~~~~~~~
lw $fp,0($sp)  ;;退避しておいた $ra を復帰
lw $ra,4($sp)  ;;$sp の値を戻す
'addiu $sp,$sp,(フレームサイズ)
jr $ra

という感じのコードになる.
ただし、フレームサイズは$fpと$raをそれぞれ退避させておくスペース数のための8バイト、局所変数の数と引数の数のバイト数(すなわちそれらの数に4掛ける)だけ必要。

関数呼び出しの手順

引数は退避させておかなければならないので、引数の数がn個でa1, a2,,, であるとすると

lw $t0 (a1のアドレス)
sw $t0 -4n($sp)
lw $t0 (a2のアドレス)
sw $t0 -4(n-1)($sp) ;;以下同様に引数の数だけ退避を行う。
jal (関数ラベル名)
sw $v0 (destアドレス)

という感じになる。

プログラム変換例

以下のSmall Cプログラム

int w(int x) {
  int r;
  r = 0;

  while (x > 0) {
    r = r + x;
    x = x - 1;
  }

  return r;
}

int main() {
  print(w(10) == 55);
}

は、次のようなアセンブリに変換できる。(あくまでこの実験仕様。あとちょっとインデントずれてるけど。。。)

        .data    
        .text   
w:
    subu    $sp,$sp,28
    sw  $ra,4($sp)
    sw  $fp,0($sp)
    addiu   $fp,$sp,20
    li  $t0,0
    sw  $t0,0($fp)
    li  $t0,0
    sw  $t0,-4($fp)
    lw  $t0,4($fp)
    lw  $t1,-4($fp)
    sgt $t0,$t0,$t1
    sw  $t0,-8($fp)
    lw  $t0,-8($fp)
L78:
    beqz    $t0,L79
    lw  $t0,0($fp)
    lw  $t1,4($fp)
    add $t0,$t0,$t1
    sw  $t0,-4($fp)
    lw  $t0,-4($fp)
    sw  $t0,0($fp)
    li  $t0,1
    sw  $t0,-8($fp)
    lw  $t0,4($fp)
    lw  $t1,-8($fp)
    sub $t0,$t0,$t1
    sw  $t0,-12($fp)
    lw  $t0,-12($fp)
    sw  $t0,4($fp)
    j   L78
L79:
    lw  $t0,0($fp)
    move    $v0,$t0
    lw  $fp,0($sp)
    lw  $ra,4($sp)
    addiu   $sp,$sp,28
    jr  $ra
    lw  $fp,0($sp)
    lw  $ra,4($sp)
    addiu   $sp,$sp,28
    jr  $ra
main:
    subu    $sp,$sp,28
    sw  $ra,4($sp)
    sw  $fp,0($sp)
    addiu   $fp,$sp,24
    li  $t0,10
    sw  $t0,-4($fp)
    lw  $t0,-4($fp)
    sw  $t0,-8($fp)
    lw  $t0,-8($fp)
    sw  $t0,-4($sp)
    jal w
    sw  $v0,0($fp)
    li  $t0,55
    sw  $t0,-12($fp)
    lw  $t0,0($fp)
    lw  $t1,-12($fp)
    seq $t0,$t0,$t1
    sw  $t0,-16($fp)
    li  $v0,1
    lw  $t0,-16($fp)
    move    $a0,$t0
    syscall 
    li  $v0,11
    li  $a0,10
    syscall 
    lw  $fp,0($sp)
    lw  $ra,4($sp)
    addiu   $sp,$sp,28
    jr  $ra

というようにできる。

ちょっと注意すべき命令変換例

空文
nop
メモリ書き込み

destはポインタ型でメモリにはアドレスが入っている。 *(dest) = srcの形。

lw $t0 src
lw $t1 dest
sw $t0 0($t1)
メモリ参照

srcはポインタ型でメモリにはアドレスが入っている。 dest = *(src)の形。

lw $t0 src
lw $t0 0($t0)
sw $t0 dest
if文
if(var){
    code1
}
else{
    code2
}

の形のif文は以下のように変換される。

lw $t0 var
beqz $t0 label1 ;;$t0が0のときはlabel1までジャンプ
code1 ;;if節
j label2
label1
code2 ;;else節
label2
組込み関数print(改行込み)

システムコールはSPIMのものを使用します。

li $v0 1
lw $t0 src
move $a0 $t0
syscall ;;これでint型のデータが出力される。
li $v0 11
li $a0 10
syscall ;;これで改行コードが出力される。

システムコールは$v0にシステムコールコードを入力することでサービスを提供しする。また、システムコールコード1はprint_intを意味し、$a0に入ったint型データが出力され、$v0に11が入るとprint_charを意味し$a0に入ったchar型データが出力される。なお$a0に入る10は改行コードを意味する。このあたりのシステムコールコードについてはWikipediaのSPIMの項を参照。

だいたいこんな感じだけど、ちょっとwhile文の変換部分がほんとにこれでいいのか臭が凄い(というか間違ってる汗)。