2.12 종합: C 정렬 프로그램

 이 절에서는 두 가지 C 프로시저의 MIPS 코드를 만들어 본다. 하나는 배열 원소 두 개를 맞바꾸는 것, 다른 하나는 배열 원소를 정렬하는 것이다. C 프로그램을 어셈블리 프로그램으로 바꿀 때는 다음 절차에 따라 번역한다.



1. 프로그램 변수에 레지스터를 할당한다.

2. 프로시저 본체에 해당하는 코드를 생성한다.

3. 프로시저 호출 후의 레지스터 내용을 호출 전과 같도록 만든다.











프로시저 swap


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

 

 

레지스터 할당

 

 인수 v, k를 각각 $a0와 $a1에 할당한다. 그 외의 변수는 temp 뿐인데 swap은 말단 프로시저이므로 레지스터 $t0에 할당된다. 
  

본체 프로그램 

sll $t1, $a1, 2       // $t1 = k * 4         ->  바이트 주소를 사용하지만 워드 단위로 주소를 받기 때문

add $t1, $a0, $t1  // $t1 = v + (k * 4)

                        // $t1 = v[k] address

 

lw $t0, 0($t1)       // temp = v[k];

lw $t2, 4($t1)       // $t2 = v[k+1] value

 

sw $t2, 0($t1)      // v[k] = v[k+1];

sw $t0, 4($t1)      // v[k+1] = temp;

 

 

프로시저 호출 전과 후의 레지스터 내용을 같게 유지하기

 

 swap 프로시저는 $s 레지스터들을 사용하지 않기 때문에 별도의 레지스터 복구 과정은 필요없다. 프로지서 레이블과 복귀를 위한 점프만 추가되면 전체 루틴이 완성된다.

 

jr $ra  // return to calling routine

 

 

 

 

 

 

 

 

 

 

 

프로시저 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와 n을 각각 $a0, $a1을 할당하고, 변수 i와 j는 $s0와 $s1을 할당한다.

 

 

 

본체 프로그램

 

           move  $s0, $zero         // i = 0  -> 어셈블러 의사명령어

for1tst:  slt       $t0, $s0, $a1     // if(i >= n) $t0 = 0

           beq     $t0, $zero, exit1 // if($t0 == 0) jump to exit1

                                          

                 ... (body) ...

 

           addi    $s0, $s0, 1        // i += 1;

           j         for1st              // jump to top of first loop

exit1:                                   // end of first loop

 

 여기까지 첫번째 for문 : for(i = 0; i < n; i += 1) 

 

 

 

           addi    $s1, $s0, -1       // j = i - 1;

for2tst:  slti      $t0, $s1, 0        // if(j < 0) $t0 = 1

           bne     $t0, $zero, exit2 // if($t0 == 1) jump to exit2

                                          // 여기까지 조건문 첫번째 조건

           sll       $t1, $s1, 2        // $t1 = j * 4

           add     $t2, $a0, $t1     // $t2 = v[j] address

 

           lw       $t3, 0($t2)        // $t3 = v[j] value

           lw       $t4, 4($t2)        // $t4 = v[j+1] value

 

           slt       $t0, $t4, $t3      // if(v[j+1] >= v[j]) $t0 = 0

           beq     $t0, $zero, exit2 // if($t0 == 0) jump to exit2

                                          // 여기까지 조건문 두번째 조건

 

                     ... (body) ...

 

           addi    $s1, $s1, -1       // j -= 1;

           j         for2tst             // jump to top of second loop

exit2:                                   // end of second loop

 

 여기까지 두번째 for문 : for(j = i - 1; j >= 0 && v[j] > v[j+1] ; j -= 1)

 

 

 

jal swap    // swap(v,j);

 

 여기까지가 마지막 본체 부분인 swap 프로시저 호출

 

 

 

 

 

프로시저 호출

 

 sort 프로시저도 레지스터 $a0와 $a1을 사용하고, swap 프로시저도 인수 전달을 위해 같은 레지스터를 사용해야 한다. 스택에 저장했다 복구하는 방법도 있지만, 프로시저 앞부분에서 sort의 인수를 다른 레지스터에 복사해서 swap을 호출할 때 레지스터 $a0와 $a1을 사용할 수 있게 하는게 더 빠르다.

 

move $s2, $a0  // copy parameter $a0 into $s2

move $s3, $a1  // copy parameter $a1 into $s3

 

move $a0, $s2  // first swap parameter is v

move $a1, $s1  // seconde swap parameter is j

                     // swap에 인수를 전달한다.

 

 

프로시저 호출 전과 후의 레지스터 내용을 같게 유지하기

 

 sort 자신도 프로시저로서 호출된 입장이므로 레지스터 $ra의 복귀 주소를 저장해야 한다. 그 외에 저장해야하는 레지스터는 $s0, $s1, $s2, $s3 등이다.

 

addi  $sp, $sp, -20

sw    $ra, 16($sp)

sw    $s3, 12($sp)

sw    $s2, 8($sp)

sw    $s1, 4($sp)

sw    $s0, 0($sp)

 

 레지스터를 다시 복구하는 코드 역시 필요하다.

 

lw    $s0, 0($sp)

lw    $s1, 4($sp)

lw    $s2, 8($sp)

lw    $s3, 12($sp)

lw    $ra, 16($sp)

addi $sp, $sp, 20

 

 마지막으로 Caller 루틴으로 점프하는 명령어다.

 

jr $ra  // return to calling routine