명령어 : 컴퓨터 언어 8 ( feat. MIPS 어셈블리 코드 예시 )

한참을 열심히 달려왔네요.

저만 달려 왔나요? 이번 글에서는 C 코드를 보여드리고

해당하는 부분을 코딩해 보며 마무리 하겠습니다.

 

void swap( int v [], int k )
{
    int temp;
    tmep = 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+=1{
    	for (j = i -1; j>=0 && v[j] > v[j+1]; j -=1) {
        	swap(v,j);
        }
    }
}

프로시저 swap의 MIPS 어셈블리 코드

swap : sll $t1, $a1, 2 # reg $t1 = k*4

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

 

       lw $t0, 0($t1) # reg $t0 (temp) = v[k]

       lw $t2, 4($t1) # reg $t2 = v[k+1]

 

       sw $t2, 0($t1) # v[k] = $t2

       sw $t0, 4($t1) # v[k+1] = $t0

       

       jr $ra # 호출 주소로 복귀

 

음 설명을 안하고 넘어가려다가, 적고 넘어갑니다. 우선 인수가 v, k 임으로 $a0, $a1 을 사용 합니다. 그리고 몸체에서 temp를 사용하므로 $t0 가 사용됩니다.

 

그럼 이제 v[k]를 찾는 과정을 봅시다. 바이트 주소를 사용함으로 k*4를 해줘야합니다. 해당 값을 $t1에 저장합시다.

  sll $t1, $a1, 2 # reg $t1 = k*4

 

배열에서 이름은 주소를 나타냄으로 v[k]를 알기위해서는 v 주소에 k*4의 주소를 더해줘야 합니다.

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

이로써 $t1은 v[k]의 address를 가지게 되었습니다.

 

이제 값을 lw 하겠습니다. v[k]의 값을 temp에 로드합니다. 0($t1)이 v[k]의 메모리 주소임을 기억하세요

   lw $t0, 0($t1) # reg $t0 (temp) = v[k]

 

다음으로 $t2 임시 레지스터에 v[k+1]을 로드합니다. 물론 주소임으로 v[k]에 4를 더해줘야 겠죠.

   lw $t2, 4($t1) # reg $t2 = v[k+1]

 

이제 값을 가져왔으니 바꿔 봅시다. v[k]에 $t2의 값을, v[k+1]에 $t0의 값을 넣어보죠

  sw $t2, 0($t1) # v[k] = $t2

  sw $t0, 4($t1) # v[k+1] = $t0

이로써 swap이 완료되었고, 이제 다시 호출 프로세서로 복귀하면 됩니다. ( jr $ra ) 간단하죠? 여러분 꼭 기억하셔야 할점은 메모리 주소를 가지고 이동하여 그 속의 값을 임시 변수에 로드하고 그 값을 필요한 주소에 스토어 한다라는 것만 기억하시면 이 예제는 매우 쉽게 이해하실 수 있습니다.

반응형

프로시저 sort의 MIPS 어셈블리 코드

sort: addi $sp, $sp,-20 # $s0- $s3 , $ra를 위한 스텍생성

        sw $ra, 16($sp)

        sw $s3, 12($sp)

        sw $s2, 8($sp)

        sw $s1, 4($sp)

        sw $s0, 0($sp)

 

        move $s2, $a0 

        move $s3, $a1 

 

        move $s0, $zero

for1tst: slt $t0, $s0, $s3 

        beq $t0, $zero, exit1 

 

        addi $s1, $s0, -1

for2tst: slti $t0, $s1, 0

        bne $t0, $zero, exit2

        sll $t1, $s1, 2

        add $t2, $s2, $t1

        lw $t3, 0($t2)

        lw $t4, 4($t2)

        slt $t0, $t4, $t3

        beq $t0, $zero, exit2

 

        move $a0, $s2

        move $a1, $s1

        jal swap

 

        addi $s1, $s1, -1

        j for2tst

 

exit2: addi $s0, $s0, 1

        j for1tst

 

exit1: lw $s0, 0($sp)

        lw $s1, 4($sp)

        lw $s2, 8($sp)

        lw $s3, 12($sp)

        lw $ra, 16($sp)

        addi $sp, $sp, 20

 

        jr $ra

 

설명 시작하겠습니다. 우선 sort의 인수는 v와 n 임으로 $a0, $a1에 넣고 변수 i, j는 $s0, $s1을 할당합니다.

 

1. 첫 번째 ( 바깥쪽 ) 순환문 번역하기

for ( i = 0; i < n ; i += 1) 부분을 번역하겠습니다.

 

  move $s0, $zero # i = 0

 

이 부분은 가장 마지막 부분에 해당합니다.

 

  addi $s0, $s0, 1 # i += 1

 

조건 부분입니다. i <n 이 아니면 순환에서 빠져나옵니다. 즉 i >= n 이면 종료됩니다.

 

  for1tst:slt $t0, $s0, $a1

          beq $t0, $zero, $exit1

 

순환문의 맨끝은 처음의 반복조건 검사로 되돌아가는 명령인데요

 

           j for1tst

  exit1:

 

이 문장들을 정리하면 첫 번째 순환문은 다음과 같은 형태가 됩니다.

 

        move $s0, $zero # i = 0

for1tst:slt $t0, $s0, $a1

        beq $t0, $zero, $exit1

 

            ( 본문 내용 )

 

        addi $s0, $s0, 1 # i += 1

         j for1tst

exit1:

 

2. 두 번째 ( 안쪽 ) 순환문 번역하기

for ( j = i -1; j>=0 && v[j] > v[j+1]; j -= 1 ) 이 부분입니다.

 

초기화 부분은 addi 를 사용하면 간단히 해결됩니다.

 

  addi $s1, $s0, -1 # j = i -1

 

j 값을 감소시키는 것 역시 addi를 사용합니다.

 

  addi $s1, $s1, -1 # j -= 1

 

반복 조건 검사는 두 부분으로 구성됩니다. 둘중 하나라도 거짓 시 순환문에서 나갑니다.

 

  for2tst:slti $t0, $s1, 0 # $s1 < 0 ( j < 0 ) 참이면 1 거짓이면 0

          bne $t0, $zero, exit2

이 명령을 통과하였다면 두 번째 조건에 대해 검사합니다. 즉 v[j]<=v[j+1] 이면 순환문을 빠져나오면 됩니다. 먼저 jdp 4를 곱해서 v의 시작 주소에 더해야겠죠?

 

  sll $t1, $s1, 2

  add $t2, $a0, $t1

 

이 주소를 활용하여 v[j] 주소를 읽습니다.

 

  lw $t3, 0($t2)

 

다음 원소의 주소는 4만큼 더 크므로, 레지스터 $t2에 4를 더해서 v[j+1]을 읽습니다.

 

  lw $t2, 4($t2)

 

v[j] <= v[j+1] 의 검사는 v[j+1] >= v[j] 검사와 같으므로 다음 명령어로 수행할 수 있습니다.

 

  slt $t0, $t4, $t3 # reg = 0 if $t4 >= $t3

  beq $t0, $zero, exit2

 

마지막 명령어는 내부 순환문의 조건 검사로 점프하는 것이겠죠?

 

  j for2tst 

 

여기 까지 종합하면 2번 째 순환문은 아래와 같은 구성이 됩니다.

 

          addi $s1, $s0, -1 # j = i -1  

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

          bne $t0, $zero, exit2 # go to exit 2 if $s1 < 0

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

          add $t2, $a0, $t1 # $t2 = v + j*4

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

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

          slt $t0, $t4, $t3 #$t0 = 0 if $t4 >= $t3

          beq $t0 $zero, exit2

               . . .

            ( body loop )

               . . .

          addi $s1, $s1, -1 # j-= 1

          j for2tst # jump to test of inner loop

  exit2:

 

잘 따라오셨나요?? 쉽지가 않아요. 그렇지만 이런 예제를 잘해놓고 나면 다음에 만났을 때, 쉽게 넘어갈 수 있게 되겠죠?

 

3. 프로시저 sort 호출

  안 쪽 for문 본체 부분인 swap ( v, j ); 은 간단하게 바뀐답니다

 

jal swap

 

4. 인수 전달 sort

  sort 프로시저도 레지스터 $a0, $a1을 사용하고, swap 프로시저도 인수 전달을 위해서 똑같은 레지스터를 사용해야 하므로 인수 전달 방법이 문제가 되는데요, 프로시저 앞부분 sort의 인수를 다른 레지스터에 복사해서 swap을 호출할 때 레지스터 $a0, $a1을 사용할수 있게 하는 겁니다. 물론 스택에 저장했다가 복구할 수 있지만 레지스터를 활용하면 더 빠르답니다. 

 

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

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

 

다음은 swap에 인수를 전달하는 일입니다.

 

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

  move $a1, $s1 #second swap parameter is j 

 

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

  거의 다왔어요. 이제 남은 것은 레지스터 내용을 저장했다가 복구하는 프로그램이에요. sort 자신도 프로시저로서 호출된 입장이므로 레지스터 $ra의 복귀 주소를 저장해야 한답니다. 그 외에 저장해야하는 레지스터는 $s0-$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)

 

와 고생하셨습니다. 다시 한번 위로 올라가서 전체 코드를 보시길 바랍니다. 어려운 내용은 없습니다. 다만 하나하나 빠트리지 않고 해셔야 한다는게 조금은 까다로울 뿐이지요. 이번 글은 여기까지 하겠습니다. 이상 WH 였습니다.