fibonacci on MIPS

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

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

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

アセンブリ言語を少しやっていると、僕らが日常使っている高級言語が
実際にどのように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関数で学べるわけです。

では、今回はこの辺で！