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ループの比較・分岐部分ですね。

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

では今回はこの辺で！