종합: C 정렬 프로그램

#1 프로시저 swap

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

[레지스터 할당] v=$a0, k=$a1, temp=$t0 

[프로그램 변수에 레지스터 할당]
인수: v=$a0, k=$a1  //  변수: temp=$t0
[프로시저 본체]
swap:	sll  $t1, $a1, 2	#reg $t1 = a1(k)*4
	add  $t1, $a0, $t1	#reg $t1 = k*4 + v(base address)
	lw  $t0, 0($t1)	#$t0=v[k]
	lw  $t2, 4($t1)	#$t2=v[k+1]
		#refers to next element of v
	sw  $t2, 0($t1)	v[k] = reg $t2
	sw  $t0, 4($t1)	v[k+1] = reg $t0(temp)
[Procedure return]
	jr  $ra	#return to calling routine

 

 

#2 프로시저 sort

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

[레지스터 할당] v=$a0 n=$a1 i=$s0 j=$s1

 

[saving registers]
sort:	addi $sp, $sp, -20	#make room on stack for 5 registers
	sw    $ra, 16($sp)	#save $ra on stack
	sw    $s3, 12($sp)	#save $s3 on stack
	sw    $s2,  8($sp)	#save $s2 on stack
	sw    $s1,  4($sp)	#save $s1 on stack
	sw    $s0,  0($sp)	#save $s0 on stack
[Procedue Body]
//move parameters
	move  $s2, $a0	#copy parameter $a0 into $s2(save $a0) [$s2<-v]
	move  $s3, $a1	#copy parameter $a0 into $s2(save $a1) [$s3<-j]
//outer loop(첫 번째 for문)
	move  $s0, $zero	#i=0
for1tst:	slt  &t0, &s0, &a1	#reg$t0=1 if $s0<$a1 #i<n이면 $t0=1
	beq  $t0, $zero, exit1	#go to exit if i>=n
//inner loop(두 번째 for문)
	addi  $s1, $s0, -1	#j=i-1
for2tst:	slti  $t0, $s1, 0	#j<0이면 $t0=1
	bne  $t0, $zero, exit2	#j>=0이면 go to exit2
	sll  $t1, $s1, 2	#v[j]공간만들기 $t1=j*4
	add  $t2, $s2, $t1	#base address v($s2)+j*4($t1)= v[j]
	lw  $t3, 0($t2)	#$t3=v[j]
	lw  $t4, 4($t2)	#$t4=v[j+1]
	slt  $t0, $t4, $t3	#v[j+1]<v[j]이면 $t0=1
	beq $t0, $zero, exit2	#v[j+1]>v[j]면 go to exit2
//pass parameters and call
	move  $a0, $s2	#1st parameter of swap() is v
	move  $a1, $s3	#2nd parameter of swap() is j
	jal  swap	#swap code
//inner loop
	addi  $s1, $s1, -1	#j-=1
	j  for2tst	#jump to test of the inner loop
//outer loop
exit2:	addi  $s0, $s0, 1	#i+=1
	j  for1tst	#jump to test of the outer loop
[Restoring Registers]
exit1:	sw  $s0, 0($sp)	#restore $s0 from stack
	sw  $s0, 4($sp)	#restore $s1 from stack
	sw  $s0, 8($sp)	#restore $s2 from stack
	sw  $s0, 12($sp)	#restore $s3 from stack
	sw  $s0, 16($sp)	#restore $ra from stack
	addi  $sp, $sp, 20	#restore stack pointer
[Procedure return]
	jr  $ra	#return to calling routine