2013-02-06

手続き呼び出しのまとめ

少し間があきましたが、こんばんは。

え、実はこの3日間くらいずっといボーッとしてたから更新なかったんだろって？
いやいや、まさかそんなことあるわけが・・・

まじめな話をしますと、ここ最近はずっとMIPSでの簡単なコードを書きながら、実際に高級言語(おもにC言語)で様々な分を書いた時の、実際の実行の様子がどうなっているかを勉強していました。
そんな訳で、ブログ書くにしても何載せようかちょっと迷っちゃってたんですよね・・・

今日載せるのは、手続き(関数)呼び出し時の一連の動作についてです。
MIPSにおいて、手続き呼び出し時の動作は以下の通り。

呼び出し側での処理(call時)

呼び出し側における一時レジスタ($a0-$a3, $t0-$t9)をスタックに退避
呼び出し先での引数を$a0-$a3にセット
(引数が5つ以上ある場合は、スタックへ積む)
jal命令でサブルーチンへ分岐

サブルーチン側での処理

$fp, $raレジスタをスタックへ退避
このときの$spを$fpに設定
(あれば)$spを下げて、手続き内でのローカル変数・$s0-$s7レジスタの退避領域を確保

(サブルーチンの主な手続き部分)

(あれば)$s0-$s7レジスタを復帰
$ra, $fpをスタックからレジスタへ復帰
jr $ra で戻り先へ分岐

呼び出し側での処理(return時)

call時と逆の手順でスタックから$a0-$a3, $t0-$t9を復帰

こんな感じですね。
コードでまとめると、例えば以下のような感じになります。

main:
	#part of execution...
	
	#part of call sub routine
	addi	$sp,	$sp,	-16	#shelter of $a0-$a3
	sw	$a0,	12($sp)
	sw	$a1,	8($sp)
	sw	$a2,	4($sp)
	sw	$a3,	0($sp)
	addi	$sp,	$sp,	-40	#shelter of $t0-$t9
	sw	$t0,	36($sp)
	sw	$t1,	32($sp)
	sw	$t2,	28($sp)
	sw	$t3,	24($sp)
	sw	$t4,	20($sp)
	sw	$t5,	16($sp)
	sw	$t6,	12($sp)
	sw	$t7,	8($sp)
	sw	$t8,	4($sp)
	sw	$t9,	0($sp)
	
	move	$a0,	$t0		#set of arguments
	move	$a1,	$t1
	move	$a2,	$t2
	move	$a3,	$t3
	addi	$sp,	$sp,	-16	#shelter of arguments
	sw	$t4,	12($sp)
	sw	$t5,	8($sp)
	sw	$t6,	4($sp)
	sw	$t7,	0($sp)
	
	jal	subr
	
	addi	$sp,	$sp,	16	#restore of $sp
	
	lw	$t9,	0($sp)		#restore of $t0-$t9
	lw	$t8,	4($sp)
	lw	$t7,	8($sp)
	lw	$t6,	12($sp)
	lw	$t5,	16($sp)
	lw	$t4,	20($sp)
	lw	$t3,	24($sp)
	lw	$t2,	28($sp)
	lw	$t1,	32($sp)
	lw	$t0,	36($sp)
	addi	$sp,	$sp,	40
	lw	$a3,	12($sp)		#restore of $a0-$a3
	lw	$a2,	8($sp)
	lw	$a1,	4($sp)
	lw	$a0,	0($sp)
	addi	$sp,	$sp,	16
	
	#continue main execution...
	
	jr $ra				#end of main
	
subr:
	addi	$sp,	$sp,	-8	#shelter of $fp and $ra
	sw	$fp,	4($sp)
	sw	$ra,	0($sp)
	move	$fp,	$sp		#$fp = $sp
	
	addi	$sp,	$sp,	-20	#secure area of local variale and $s0-$s7
#	sw	$s0,	0($sp)		#(shelter of save registers)
	#part of execution of subr...
	
#	lw	$s0,	0($sp)		#(restore of save registers)
	
	move	$sp,	$fp		#restore of $ra and $fp
	lw	$ra,	0($sp)
	sw	$fp,	4($sp)
	addi	$sp,	$sp,	8
	
	jr	$ra			#return of subr

では今日はこの辺で！

2013-02-02

sort on MIPS

今日やっていたことの報告。

今日は昨日に引き続き、MIPSさんと戯れていました。
例題に載ってはいるのですが、バブルソートをMIPSで実装してみました。

Cで書くと、コードはこんな感じ。

void swap(int v[], int k)
{
	int temp;
	temp = v[k];
	v[k] = v[k+1];
	v[k+1] = temp;
}

void sort(int v[], int n)
{
	int i, j

	for(i=0; i<n; i=i+1)
	{
		for(j=i-1, j>=0; j=j-1)
		{
			if(v[j] > v[j+1])
			{
				swap(v, j)
			}
		}
	}
}

これをもとにして、MIPSでは以下のようになりました。

Main:	jal	Sort
	j Exit
	
Sort:	addi	$s0,	$zero,	0	#For1 i=s0
For1:	slt	$t0,	$s0,	$a1	#if(i<n) t0 = 1
	beq	$t0,	$zero,	Exit1	#if(t0==0) goto Exit1
		
	addi	$s1,	$s0,	-1	#For2 j=s1
For2:	sge	$t0,	$s1,	$zero	#if(j>=0) t0 = 1
	beq	$t0,	$zero,	Exit2	#if(t0==0) goto Exit2
	
	sll	$t1,	$s1,	2	#t0 = quadruple j
	add	$t1,	$t1,	$a0	#t0 += base of v
	lw	$t2,	0($t1)		#t2 = v[j]
	lw	$t3,	4($t1)		#t3 = v[j+1]
	
	sgt	$t0,	$t3,	$t4	#if(v[j]>v[j+1]) then t0 = 1
	beq	$t0,	$zero,	Exit3	#if(t0==0) goto Exit3
	
	addi	$sp,	$sp,	-12	#shelter of registers
	sw	$a0,	8($sp)
	sw	$a1,	4($sp)
	sw	$ra,	0($sp)
	move	$a1,	$s1		#a1 = j
	jal	Swap			#swap(v, j)
	
	lw	$ra,	0($sp)		#restore of registers
	lw	$a1,	4($sp)
	lw	$a0,	8($sp)
	addi	$sp,	$sp,	12
	
Exit3:	addi	$s1,	$s1,	-1	#j -= 1
	j	For2			#goto For2
	
Exit2:	addi	$s0,	$s0,	1	#i += 1
	j	For1			#goto For1
			
Exit1:	jr	$ra			#end of sort
	
Swap:	sll	$t1,	$a1,	2	#quadruple k 
	add	$t1,	$a0,	$t1	#add base and 4*k
	
	lw	$t0,	0($t1)		#temp = v[k]
	lw	$t2,	4($t1)		#t2 = v[k+1]
		
	sw	$t2,	0($t1)		#v[k] = t2 (= v[k+1])
	sw	$t0,	4($t1)		#v[k+1] = temp
	
	jr	$ra			#end of swap
Exit:

sort内でswapの手続きを呼び出す際に、保持されないレジスタ群をスタックに退避するのは、
この前のfibonacciと同じですね。
$tレジスタ群はswap関数以降はまた新たに初期化されるので今回は退避する必要はありませんでしたが、本来であれば退避する必要があります。

あと重要そうなのははforループの比較・分岐部分ですね。

書いて思ったのが、バブルソートなんて普段割と普通で楽に書いてるコードなのに、
アセンブリだとやっぱり時間がかかるなーってことです。
レジスタの割り当てやら退避やら考える必要がありますからね。
高級言語とコンパイラのありがたさが身にしみてわかります。

では今回はこの辺で！

2013-02-02

fibonacci on MIPS

早速ですが、昨日やっていたことの報告。

最近パタヘネ本を読み進めながら、MIPS(アセンブリ言語の一種)の勉強をしています。

コンピュータの構成と設計　第4版（上）ハードウエアとソフトウエアのインタフェース (Computer Organization and Design: The Hardware/Software Interface, Fourth Edition)

作者: デイビッド・A・パターソン,ジョン・L・ヘネシー,成田光彰
出版社/メーカー: 日経BP社
発売日: 2011/11/17
メディア: 単行本
購入: 6人クリック: 17回
この商品を含むブログ (5件) を見る

アセンブリ言語を少しやっていると、僕らが日常使っている高級言語が
実際にどのようにCPUで処理されているのかがわかるようになってくると思います。

昨日は、フィボナッチ関数をMIPSで書いてました。

フィボナッチ関数は、C言語では以下のように書けると思います。

int fibonacci(int n)
{
	if(n <= 1)
	{
		return n;
	}
	else
	{
		return fibonacci(n-1) + fibonacci(n-2);
	}
}

これを、以下のようにMIPSで書いてみました。

Main:		jal	Fibonacci
		j	Exit
		
Fibonacci:	addi	$sp,	$sp,	-8	#shelter of registers
		sw	$a0,	4($sp)
		sw	$ra,	0($sp)

		addi	$t0,	$zero,	1
		bgt	$a0,	$t0,	True	#if(n>1)
		
		move	$v0,	$a0		#n<=1
		j	Return
		
True:		addi	$a0,	$a0,	-1	#n>1
		jal	Fibonacci		#fibonacci(n-1)
		addi	$sp,	$sp,	-4	#shelter of return value
		sw	$v0,	0($sp)		
		addi	$a0,	$a0,	-1
		jal	Fibonacci		#fibonacci(n-2)
		lw	$s0,	0($sp)		#restore of return value
		addi	$sp,	$sp,	4
		add	$v0,	$v0,	$s0	#fibonacci(n-1) + fibonacci(n-2)
		j	Return
		
Return:		lw	$ra,	0($sp)		#shelter of registers
		lw	$a0,	4($sp)
		addi	$sp,	$sp,	8
		jr	$ra
		
Exit:

重要なのは、再帰呼び出し時のレジスタの退避ですね。
$raレジスタと$a0レジスタは関数呼び出し時に保持されないので、スタックに退避してあげる必要があります。
procedure処理の重要部の1つが、fibonacci関数で学べるわけです。

では、今回はこの辺で！

2013-02-02

はじめてみました

どうもみなさんはじめまして。

つい最近春休みに入ったとある情報系大学二年生です。

「春休み中、何か専門分野を少しずつでいいから勉強・演習していきたいな～」

と思い、今も少しずつですが取り組んでいます。

せっかくなので、その取り組んだ結果をみんなとシェアできればなと思い、

今回このブログを作成するに至りました。

特に僕の周りにはハードウェア系を専門としようという人が少ない気がする(?)

ので、ハードウェアの面白みも伝えていければなと思います。

(といっても、僕自身もまだまだ勉強中の未熟な身ではありますが...)

春休み中は1日1回は更新できるように頑張りたいなーと思っているので、

もしよかったら見てやってください。