演習の目的

• 命令レベルシミュレータに慣れること
• MIPSのアセンブラ命令の使い方を理解すること
• 今後の課題で使用するプログラムを作成すること

今回の演習ではMIPSプロセッサのアセンブラを用いて簡単なプログラミングを行います。 このプログラムを動作させるために、SPIMシミュレータを用いて、実際に正しく動作しているかどうかを確認します。 ここで作成したプログラムはあとで設計するMIPSプロセッサで実行させるテストプログラムになります。

シミュレータのドキュメント

演習を始める前に

以下のページの留意点をよく読んでから演習を始めてください：Ex01 演習の留意点2015

留意点 １

以下の表に示された以外の命令は使わないこと。

区分	命令	例	意味
算術演算	add	add $1,$2,$3	$1=$2+$3
	subtract	sub $1,$2,$3	$1=$2-$3
	add immediate	addi $1,$2,100	$1=$2+100
論理演算	and	and $1,$2,$3	$1=$2&$3
	or	or $1,$2,$3	$1=$2|$3
	and immediate	andi $1,$2,100	$1=$2&100
	or immediate	ori $1,$2,100	$1=$2|100
データ転送	load word	lw $1,100($2)	$1=メモリ[$2+100]
	store word	sw $1,100($2)	メモリ[$2+100]=$1
条件分岐	branch on equal	beq $1,$2,100	if($1==$2) go to PC+4+100
比較演算	set on less than	slt $1,$2,$3	if($2<$3) $1=1;else $1=0
	set less than imm.	slti $1,$2,100	if($2<100) $1=1;else $1=0
ジャンプ	jump	j 10000	go to 10000
	jump register	jr $rs	go to $rs
	jump and link	jal 10000	go to 10000; $31=PC+4
疑似命令	load address	la $1, A	$1 = Aのアドレス

これ以外の命令を使うと、後半の演習で設計するMIPSプロセッサでは動作しません。

レジスタの指定は、$0から$31でも、$zero, $v0, $v1,...でも構いません。 指定があるもの(スタックポインタ,リターンアドレスなど)は、指定通りに使ってください。 以下の課題において、一時的にレジスタを利用する場合は、$8から$15と$24, $25(これらは$t0 - $t9としてもアクセス可能)を使用します。

$1はアセンブラが使用するので、プログラムでは使用しないでください。

留意点 ２

シミュレーションはステップ実行で行うこと。方法については演習の時間に説明する。

留意点 ３

後半の演習で設計するMIPSプロセッサでは、システムコールを実装しないので、exit システムコールは利用できません。 プログラムの最後で停止させたいときは、自分自身にジャンプさせ無限ループさせるようなコードを挿入します。

例：

exit: j exit

留意点 ４

後の演習や課題、レポートで利用するため、作成するプログラムは全て保存しておくこと。

単純な代入文

定数の代入文はor immediate命令とstore word命令の組み合わせで実現できます。

例えばC言語のコード

A = 15;

は、擬似的なアセンブリプログラム

$8 = 15;
A = $8

に置き換えることができます。

各行を実行可能な命令に置き換えると：

ori $8, $0, 15
sw $8, A

というプログラムに置き換えることができます.

考察事項

• この２つのアセンブラ命令でA=15が正しく実現できているか考えなさい。
• なぜ$0が使われるのか？
• この方法で扱える代入文の右辺の定数の範囲を考えなさい。
• 符号付き32bitの範囲の定数の代入文を実装する方法を考えなさい。

メモリの初期化

代入文「A = 15;」は、Aへの代入としてプログラム開始から最初に実行され、一度しか実行されない場合

    .data
A: .word 15 

とすることで、アセンブリプログラムによるメモリ領域の初期化によっても実現できます。 しかし、この初期化を含んだプログラムをサブルーチンに用いる場合、一回目の実行でAの値が変更されてしまうと、 2回目以降の呼び出しにおいてAは15以外の値を持つ可能性があります。 この様な場合、上記のようにori命令とsw命令の組み合わせで代入文を実現します。

例題１：変数の代入

変数A, B, Cがある時に「C = A + B;」を実現するプログラムを考える。

変数A,B, Cは、メモリ上に以下のように配置されているとします。 それぞれは32ビットワードの変数であり、１変数につき4バイトのアドレス空間を占めます。

変数	アドレス(16進数)	初期値(10進数)	結果(10進数)
A	0x0	19	19
B	0x4	75	75
C	0x8	0	94

MIPSプロセッサでの演算はレジスタ間でのみ行うことができます。 したがって、メモリの中のデータを演算するためには一度レジスタの中にデータをロードし、 演算を行った後に演算結果をメモリにストアしなければなりません。 そのようなプログラムを下に示します。

         .data 
A:       .word 19 
B:       .word 75 
C:       .word 0 
         .text 
main:    lw   $8, A 
         lw   $9, B 
         add  $10, $8, $9 
         sw   $10, C 
exit: j  exit

このプログラムを「sum1.s」としてファイルに保存し、xspimでシミュレーションを行ってください。 ソースファイルの読み込みには "load" ボタン、プログラムの実行には "step" ボタンをクリックする。

「.data」で定義される部分をデータセグメントと呼ぶ。各行は「32ビット数値で内容は「19」の変数を定義しそのアドレスを「A」で参照できるようにする」のような意味を持つ。

「.text」で定義される部分をコードセグメントと呼び、これがプログラムの本体になる。各命令の概要を以下に説明する。 まず、このプログラムでは、レジスタ$8, $9, $10を利用している。各行が実行される毎に、その内容は変化する場合がある。

命令	動作	$8の内容	$9の内容	$10の内容
lw $8, A	アドレスAのデータをレジスタ$8にロード	19	不定	不定
lw $9, B	アドレスBのデータをレジスタ$9にロード	19	75	不定
add $10, $8, $9	レジスタ$8と$9を加算して、結果を$10に格納	19	75	94
sw $10, C	レジスタ$10の内容をアドレスCにストア	19	75	94
j exit	ラベルexitにジャンプ	19	75	94

補足：「lw $8, A」 は 「lw $8, A($0)」 の省略形である。レジスタ$0は常にゼロである。

複雑な式の評価

代入文の右辺が複雑な場合は式を変換して考えます。

A= B * C - 5

という演算をする場合、右辺は一時的な変数Tempを用いて、

Temp = B * C
A = Temp - 5

と変換できます。 より複雑な式も、このように一時的な変数を導入して分解して、右辺の演算が実装する命令で実行できるようにします。 if文の条件判定の式が複雑な場合も同様に分解します。

アセンブラプログラムでは、一時的な変数の役割はレジスタが行います。 しかし、すべての一時的なレジスタを使いきるような場合、一時変数を保持するのにメモリを利用する必要があります。 メモリを利用する場合、swおよびlw命令が必要となり、 実行命令数が増えるので、可能な限りレジスタを効率的に使用するようにします。

課題１

3つの変数と定数を含んだ式「S = (A + B - C) | 3」の計算を行うプログラムを作成し、SPIM上でシミュレーションを行ってください。 "|" はビットごとの論理和演算です。

各変数の初期値は以下のように設定してください。

アドレス	データ(10進数)
A	19
B	75
C	10
S	結果の格納

例題２ レジスタによるメモリの参照

この例題ではメモリを間接的に参照するためにレジスタ相対アドレスを用いる方法を示します。 以下のような配列変数の和を計算することを考えます。

S=A[0]+A[1]+A[2]+A[3]

配列のように、連続するデータのアドレスが規則的に並んでいる場合、 レジスタを使ってアドレスを加減算しながらメモリにアクセスするとプログラムが簡単に記述できます。 たとえば次のようにデータが並んでいるとします。　

アドレス	データ(10進数)
A	19
A+4	75
A+8	10
A+12	15 |
S	結果の格納

このような場合、最初のアドレスAがわかれば、次のアドレスはAに４を足すことによって求めることができます。 したがって、４つの要素の和を求める場合、次のようなプログラムを記述すればよいことになります。

        .data 
A:      .word 19 
        .word 75 
        .word 10 
        .word 15 
S:      .word 0
        .text 
main:   or   $8, $0, $0   # 和を 0 に初期化 
        la   $9, A        # Aのアドレスを $9 に入れる。実際は ori 命令に置き換わる。

        lw   $10, 0($9) 
        add  $8, $8, $10 

        lw   $10, 4($9) 
        add  $8, $8, $10

        lw   $10, 8($9) 
        add  $8, $8, $10

        lw   $10, 12($9) 
        add  $8, $8, $10

        sw   $8, S 
exit:   j exit

また、上のプログラムは下のように書き直すこともできます。 この形は各データに対する処理が全く同じ命令列になるため、 後で述べるループを用いて和を求める場合に適しています。

        .data 
A:      .word 19 
        .word 75 
        .word 10 
        .word 15 
S:      .word 0
        .text 
main:   or   $8, $0, $0   # 和を 0 に初期化 
        la   $9, A        # Aのアドレスを $9 に入れる。実際は ori 命令に置き換わる。

        lw   $10, 0($9) 
        add  $8, $8, $10  
        addi $9, $9, 4    # アドレスを次へすすめる

        lw   $10, 0($9) 
        add  $8, $8, $10 
        addi $9, $9, 4

        lw   $10, 0($9) 
        add  $8, $8, $10 
        addi $9, $9, 4

        lw   $10, 0($9) 
        add  $8, $8, $10

        sw   $8, S 
exit:   j exit

上の２番目のアセンブラソースファイルをエディタにカット＆ペーストして、SPIM上で動作を確認してみてください。 レジスタをインクリメントしながらメモリにアクセスする方法を理解してください。

条件分岐

本演習で利用可能な命令の中で、条件分岐に利用できるのはbranch on equal命令だけです。 例えば、C言語での以下の条件分岐は

if( i == j) goto label
:
label:

以下のbeq命令と同等です。

beq $i,$j,label

大小比較

大小比較をするには、set on less than命令、あるいはset less than imm命令と、beq命令を組み合わせて実現します。

C言語

if(a > b) {サブプログラム１｝else {サブプログラム２}

MIPSアセンブリ

lw $8, a // $8 = a
lw $9, b // $9 = b
slt $8,$9,$8 // $8 = if ($9<$8) $8=1;else $8=0
beq $8,$0,label1 // if $8=0 then goto label1
{サブプログラム１に対応するアセンブラプログラム}
goto label2
label1:
{サブプログラム２に対応するアセンブラプログラム｝
label2:

「 <=」による条件分岐をどのように実現するか、また、「if (条件１ ｜｜ 条件２)」や「if (条件１＆＆ 条件２)」をどのように実現するかは各自検討してください。

while文

C言語

while（条件）{ サブプログラム}

MIPSアセンブリ

label1:
$a ← if (条件) 1 else 0
beq $a,$0,label2
(サブプログラムに対応するアセンブラプログラム）
goto label1

なお、条件が等式の場合は$aを用いず、直接beq命令で等式判定をします。

for文

for( i = init_value; i < terminate_value ;更新式){サブプログラム}

のようなfor文は、while文を使って

i = init_value;
while(i < terminate_value){
サブプログラム;
更新式}

と置き換えることができるので、while文のアセンブリプログラムを応用することで変換可能です。 このとき、iの値をレジスタに保持しておくと、iへのswやlw命令を省略でき、 高速化が行えますが、繰り返しの中で自由に使えるレジスタが減ってしまいます。 多重ループの場合は、内部の繰り返しに優先してfor文の制御変数(今の場合i)をレジスタに割り付けるといいでしょう。 この場合繰り返しの最後に、レジスタの値をメモリに書き戻さないと、正しい最適化とはなりません.

例題３ アセンブラでのループ S=Σi=1..ni

この例題では、１からｎまでを単純に加算するプログラムを扱います。

Ｃ言語

main() 
{ 
  int i = 0; 
  int n = 15; 
  int s = 0;
  while( i != n ) { 
     i++; 
     s += i; 
  } 
}

総和演算のような処理は処理はwhile文を用いることによって記述できます。

MIPSアセンブリ

アセンブラでは、分岐命令と比較命令を用いてループを実現します。メモリの初期状態を以下のように仮定しましょう。

アドレス	データ
n	15
s	結果の格納

このコードをアセンブラに変換します。 ループ変数 i を$8、n の値が入っているレジスタを$9とすると、ループの部分は次のように書けます。

         or  $8, $0, $0    　      # i = 0 
loop: beq  $8, $9, loopend  # i == n なら loopend へ飛ぶ 
         addi $8, $8, 1             # i++ 
　 
   　    ・・・・ループの中身・・・・・ 
　 
         j loop 
loopend:

例題のソースファイル全体は次のようになります。

         .data 
n:       .word 15 
s:       .word 0
         .text 
main:    or   $8, $0, $0       # i = 0 
         lw   $9, n            # nの値をロード 
         or   $10, $0, $0      # s = 0

loop:    beq  $8, $9, loopend  # i == n なら loopend へ 
         addi $8, $8, 1        # i++ 
         add  $10, $10, $8     # s += i 
         j    loop

loopend: sw   $10, s           # sの値をストア

exit:    j    exit

課題２ 配列の総和計算

メモリ上に並んだN要素からなる配列の総和を求めるプログラムを作成し、SPIMシミュレータで動作確認を行ってください。 プログラムの先頭部分(配列データ)には下のコードを使用してください。

        .data 
N:     .word 10    # The length of Array 
A:     .word 8     # A[0] = 8 
        .word 4     # A[1] = 4 
        .word 7 
        .word 12 
        .word 13 
        .word 19 
        .word 23 
        .word 43 
        .word 56    # A[8] = 56 
        .word 32    # A[9] = 32 
S:      .word 0
        .text 
main: 

課題３ 配列のコピー

メモリ上に並んだＮ要素からなる配列Aの内容を別の配列Bにコピーするプログラムを作成し、シミュレータで動作確認を行ってください。 プログラムの先頭部分には、下のコードを使用して下さい。

       .data 
N:    .word 10    # The length of Array 
A:    .word 8      # A[0] = 8 
        .word 4     # A[1] = 4 
        .word 7 
        .word 12 
        .word 13 
        .word 19 
        .word 23 
        .word 43 
        .word 56    # A[8] = 56 
        .word 32    # A[9] = 32 
B:      .space 40   # 配列B の格納先　大きさは40バイト
        .text 
main: