명령어 : 컴퓨터 언어 5

 

반응형

안녕하세요. 개발자 WH 입니다.

컴퓨터 구조론에 대해 정리하며 올리며, 저 역시 리뷰되는 좋은 시간인 것 같네요

이번 글은 프로시저에 대한 글입니다.

 

프로시저( procedure )

  - 프로시저는 소프트웨어에서 추상화를 구현하는 방법인데요. 즉 프로시저나 함수는 이해하기 쉽고 재사용이 가능하도록 프로그램을 구조화 하는 방법 중 하나입니다. 큰 덩어리를 부분 부분 나누어 프래그래머가 해당 부분에 집중할 수 있게 해주죠. 프로시저에 값을 보내고 결과를 받아오는 일을 하는 것이 바로 인자 ( parameter )인데요. 프로그램의 다른 부분 및 데이터와 프로시저 사이의 인터페이스 역할을 한답니다. 프로그램이 프로시저를 실행할 데 아래의 6가지 단계를 거칩니다.

 

1. 프로시저가 접근할 수 있는 곳에 인수를 넣음

2. 프로시저로 제어를 넘김

3. 프로시저가 필요로 하는 메모리 자원을 획득

4. 필요한 작업 수행

5. 호출한 프로그램이 접근할 수 있는 장소에 결과 값을 넣음

6. 프로시저는 프로그램 내의 여러 곳에서 호출될 수 있음으로 원래 위치로 제어를 돌려줌

 

레지스터는  데이터를 저장하는 가장 빠른 장소이므로 가능한 많이 활용하는 것이 좋은데요, MIPS 소프트웨어는 호출 관례에 따라 32개의 레지스터를 할당한답니다.

 

1. $a0-$a3 : 전달할 인수를 가지고 있는 인수 레지스터

2. $v0-$v1 : 반환되는 값을 갖게 되는 값

3. $ra : 호출한 곳으로 되돌아가기 위한 복귀 주소를 가지고 있는 레지스터

 

- > 정리 : 인수 레지스터 4, 반환 레지스터 2, 복귀를 위한 레지스터 1, 총 7개

 

MIPS 어셈블리 언어는 프로시저를 위한 명령어를 제공하는데요, 지정된 주소로 점프하면서 동시에 다음 명령의 주소를 $ra 레지스터에 저장하는 명령어가 바로 jal( jump-and-link instruction )입니다. 이름 속 link의 의미는 프로시저 종료 후 올바른 주소로 되돌아올 수 있도록 호출한 곳과 프로시저 사이에 링크를 형성한다는 의미랍니다. $ra 에 기억되는 링크를 복귀 주소( return registor )라 부른답니다. MIPS에서는 jr (jump register )를 이용하는 데

 

jr $ra

 

$ra에 저장되어 있는 주소로 점프하라는 의미를 가집니다. 즉 해당 글들을 정리해서 좀 보자면

 

프로시저 이름이 X라 가정함

 

1. 호출 프로그램에서 전달할 인수 -> $a0 - $a3에 넣음

2. jal X  -> 프로시저 X로 점프

3. 피호출 프로그램 계산 완료 -> $v0-$v1에 값 넣음

4. jr $ra -> 복귀

 

 이런 내장 프로그램 개념은 현재 수행 중인 명령어의 주소를 기억하는 레지스터를 필요로 하며, 프로그램 카운터 ( program counter ) 즉 PC 라고 부른답니다. jal 명령은 PC + 4를 레지스터 $ra 에 저장( 프로시저에서 복귀시 다음 명령어부터 실행하기 위함 )합니다.

 

더 많은 레지스터 사용하기

  - 컴파일러가 프로시저를 번역하는 데 더 많은 인수 레지스터 4개, 결과 레지스터 2개 만으로 부족하면 어떻게 해야할까요? 이 때 사용하는 것이 바로 레지스터 스필링이랍니다. 자주 사용하지 않는 것은 저장해두겠다는 거죠. 기억이 나지 않으시나요? 아래글을 참조해주세요.

2022.02.07 - [컴퓨터 구조론( MIPS )] - 명령어 : 컴퓨터 언어 1

명령어 : 컴퓨터 언어 1

레지스터 스펠링은 스텍이 사용된답니다. 스텍에는 다음 프로시저가 스필할 레지스터를 저장할 장소나 옛날 값이 저장된 장소를 표시해야겠죠? 즉 장소를 가리킬 포인터가 필요합니다. 이 포인터를 스텍 포인터라 부르며 레지스터 값 하나가 스텍에 저장되거나 스텍에서 복구될 때마다 한 워드씩 조정된답니다. MIPS 소프트웨어는 레지스터 29번에 스텍 포인터를 할당해 놓고 $sp( 레지스터 29 번 )라는 이름을 사용합니다. 자료를 넣을 때는 push, 뺄 때는 pop이라고 하며, 최상위부터 아래로 크기가 커집니다. 즉 스텍은 높은 주소에서 낮은 주소로 성장하기 때문에, push 시 sp를 감소시켜야하고, pop시 sp를 증가시켜야합니다.

예시를 보면서 이해해봅시다.

 

아래 코드를 어셈블리어로 바꿔보자구요. a, b, c, d 는 각각 $a0-$a3에 해당하고 e는 $s0 에 해당한다고 가정하겠습니다.

int example(int a, int b, int c, int d)
{
    int e;
    e = ( a + b ) - ( c + d );
    return e;
}

한글로 먼저 정리해 볼까요?

 

1. 프로시저 이름이 example임으로 프로시저 레이블은 example입니다.

example:

 

2. 사용될 레지스터의 개수를 세보면 e 하나 저장해야 겠고, ( a + b ), ( c + d )를 저장해야겠네요. 스텍 포인터로 3개의 공간을 만든 뒤에 값을 할당해 줍시다.

 

addi $sp, $sp, -12

sw $t0, 8($sp)

sw $t1, 4($sp)

sw $s0, 0($sp)

 

3. 프로시저 본문의 내용은 다음과 같이 바뀌겠죠?

 

add $t0, $a0, $a1

add $t1, $a2, $a3

sub $s0, $t0, $t1

add $v0, $s0, 0

 

4. 이제 호출 프로그램으로 가야되는데, 레지스터를 원상 복구 시켜야 겠네요.

 

lw $s0, 0($sp)

lw $t0, 4($sp)

lw $t1, 8($sp)

 

5. 마지막으로 복귀 주소를 이용해 복귀 해야겠죠?

 

jr $ra

 

정리해볼까요?

example:

addi $sp, $sp, -12

    sw $t0, 8($sp)

    sw $t1, 4($sp)

    sw $s0, 0($sp)

    add $t0, $a0, $a1 # ( a + b )

    add $t1, $a2, $a3 # ( c + d )

    sub $s0, $t0, $t1 # e = ( a + b ) - ( c + d )

    add $v0, $s0, 0 # return e;

    lw $s0, 0($sp)

    lw $t0, 4($sp)

    lw $t1, 8($sp)

    jr $ra

 

이해하기 어려우면 안되요 여러분. 여러분은 더 어려운 분기도 이해하고 오신분들이라구요. 어려웠다면, 그 전 글들을 꼼꼼히 읽고 오시길 바랄게요. 여튼 이번 예제에서 임시 레지스터( $t0, $t1 )와 변수 레지스터( $s0 )를 사용했어요. MIPS 소프트웨어는 레지스터 18개를 두 종류로 나눈답니다.

 

1. $t0- $t9 프로시저 호출 시, 피호출 프로그램이 값을 보존해 주지 않는 임시 레지스터

2. $s0-$s7 프로시저 호출 전과 후의 값이 같게 유지되어야 하는 변수 레지스터

 

사실 위의 코드는 $t0, $t1 값이 호출 전 후에 같은 값을 유지할 필요없기 때문에 lw와 sw 명령 2개씩 없앨 수 있어요. 그러나 $s0의 경우는 반드시 lw와 sw가 필요하답니다. 

 

중첩 프로시저 

 

이번에는 조금은 까다로운 예제를 하나 볼게요. 팩토리얼 재귀 함수인데요. 재귀 함수가 까다로워서 가져왔다기 보다는 함수안에서 함수를 콜할 때 흘러가는 플로우를 보여드리고자 가져왔습니다. 인수 n이 $a0에 해당한다고 가정할게요.

int fact( int n )
{
    if( n < 1) return 1;
    	else return (n * fact( n-1 ));
}

 

우선 명령어를 쭉 보여드리겠습니다.

fact:

    addi $sp, $sp, -8

    sw $ra, 4($sp)

    sw $a0, 0($sp)

    slti $t0, $a0,1

    beq $t0, $zero, L1

    addi $v0, $zero, 1

    jr $ra

 

L1:

    addi $a0, $a0, -1

    jal fact

    lw $a0, 0($sp)

    lw $ra, 4($sp)

    addi $sp, $sp, 8

    mul $v0, $a0, $v0

    ja $ra

 

뭔가 보기만 해도 복잡하네요. 한글로 정리해보겠습니다.

 

1. fact: 라는 레이블로 시작하고 인수 n과 복귀 주소를 저장해야겠네요. 그럼 스텍 공간 2개를 확보하고 해당 값을 저쟁해줍시다.

fact:

    addi $sp, $sp, -8

    sw $ra, 4($sp)

    sw $a0, 0($sp)

 

 

2. 그 다음으로는 if문을 코딩해야겠네요? 그럼 조건을 먼저 코딩하고 beq 문을 써야겠네요.

slti $t0, $a0, 1 # n <1 test

beq $t0, $zero, L1 # n >=1 이면 L1으로 가라

 

3. 작으면 1을 return해라 라는 문장을 코딩해야겠죠? 해당 return 문은 총 함수의 종결을 나타내니까 할당해줬던 메모리도 찾아와야 하고 복귀 주소로 돌아가야겠네요.

addi $v0, $zero, 1

addi $sp, $sp, 8

jp $ra

 

4. 이번에는 n >=1 일때 코딩을 L1에서 한다고 했으니 L1에 대해 코딩해 봅시다. 먼저 인수를 하나 줄이고 함수를 재호출하는 부분입니다.

L1:

    addi $a0, $a0, -1

    jal fact

 

( 여기 부분을 먼저 시행하는 이유는 프로시저가 시행되면서 n<1이 호출되지 않으면 조건을 만족할 때 가지 함수를 호출하는데, 인자를 날리지 않고 쌓아주기 위함입니다. 즉 $a0의 내용을 계속해서 쌓아주기 위함입니다. 음 한가지 헷갈릴 수 있는게, 스텍 포인터는 초기화 되는 것이 아니라, 그 위치에서 시작한다고 생각하시면 됩니다. 예를 들면 a = 1 + 2, 다음 시행에 a = a + 1 하면 최종 a = 4가 되는 것과 같다고 생각하시면 되요 )

 

5. 이번에는 호출프로그램으로 돌아가는 부분에 대해서 짜볼까요? 이전의 복귀 주소와 인수 값을 복구하겠습니다.

lw $a0, 0($sp)

lw $ra, 4($sp)

addi $sp, $sp, 8

 

6. 마지막으로 인수 $a0 와 결과 값 레지스터의 현재 값을 곱해서 $v0 에 넣어주고 복귀 주소로 돌아가겠습니다

 

mul $v0, $a0, $v0

jr $ra

 

이렇게 설명해도 조금은 어렵다면, 음 어셈블리어가 어려운것이 아니라, 재귀함수에 대한 이해가 부족한 것 같아요. 만약 재귀 함수를 완벽하게 이해했는데도, 해당 설명이 이해가가지 않으시면,,, 스텍을 그려놓고 해당 과정을 따라가면서 쌓아보시면 이해가 잘 가실 겁니다. 

 

참고 프로그래밍에서의 전역 변수와 지역 변수가 MIPS 에서는

전역 변수와 static 변수는 지역변수와는 다르게 해당 프로시저가 끝나더라도 남아있게 되죠? 이런 변수를 정적 변수라고 하는데 MIPS 에서는 $gp ( global pointer , 레지스터 28 번 )라 불리는 레지스터 지정해 놓고 접근한답니다. 이 부분은 나중에 기회를 봐서 다시 한번 설명드리겠습니다.

 

새 데이터를 위한 스택 공간 할당

  앞 선 글에서, 레지스터에 들어가지 못할 만큼 큰 배열이나 구조체 같은 지역 변수는 스택에 저장한다고 했었죠? 와 그래서 머리가 아파졌어요. 스택에는 지금 프로시저 호출 시 지역변수도 저장되거든요? 이걸 어쩔까나요.. 자 천천히 따라와보세요. 우선 프로시저의 저장된 레지스터와 지역 변수를 가지고 있는 스텍 영영을 프로시저 프레임 ( procedure frame ) 또는 엑티베이션 레코드 ( activation record )라 합니다. MIPS 소프트웨어 중에는 프레임 포인터 ( frame pointer, $fp ,레지스터 30 번) 가 존재하는데 이는 프로시저 프레임의 첫 번째 워드를 가리키도록 한답니다. $sp 값이 프로시저 내에서 변경될 수 있음을 중첩 프로시저 예제에서 보았죠? 즉 $fp 가 베이스 레지스터 역할을 하기 때문에 해당 문제는 해결이 간단해 집니다. $fp 로 가리키고 $sp를 움직이면 되니까요!

MIPS register 사용 관례

                   이          름                                  레지스터 번호                                   용        도

$zero	0	상수 0
$v0 - $v1	2-3	결과 값 저장
$a0 - $a3	4-7	전달 인자
$t0 - $t7	8-5	임시 변수
$s0 - $s7	16-23	saved 변수
$t8 - $t9	24-25	임시 변수
$gp	28	global pointer
$sp	29	stack pointer
$fp	30	frame pointer
$ra	31	복귀 주소

 

여기까지 읽으신 분들 수고하셨습니다. 아래 글은 읽지 않아도 되지만, 내가 실력 향상을 꿈꾼다 하시는 분만 읽어주세요.

 

마지막으로 조금은 더 복잡한 예제를 말씀드리며 마무리하려고 합니다. 꼬리 재귀 인데요. 꼬리 재귀가 무엇인지는,,, 언젠가 설명할 기회가 있기를 바라며 어셈 보여드리고 마무리할게요. ( $s0 = n, $a1 = acc라 가정 )

int sum ( int n, int acc ){
    if ( n > 0 )
        return sum ( n-1, acc + n );
    else
        return acc;
}

sum:

    slti $t0, $a0, 1

    bne $t0, $zero, sum_exit

    add $a1, $a1, $a0

    addi $a0, $a0, -1

sum_exit:

    add $v0, $a1, $zero

    jr $ra

 

간단한 해설 sum (3,0 ) 을 호출한다면 sum ( 2, 3 ) , sum( 1, 5 ) , sum ( 0, 6 )의 재귀적 호출이 일어나게 6이 네번 반환될 겁니다. 코드는 조금만 생각해 보시길 바랄게요.

 

이상 WH 였습니다. 감사합니다. 오늘도 즐거운 하루되세요!