[컴구] #03. Procedure

Procedure

프로시저는 특정 작업을 수행하는 프로그램의 묶음을 말합니다. 프로그램을 짜다 보면 특정 작업을 반복해서 수행해야 할 때가 있잖아요? 작업 A를 100번 해야 한다고 할 때 A를 해야 할 때마다 A의 코드를 작성하지 말고, A라는 작업을 하는 프로시저를 하나 만들고 A를 해야 할 때마다 프로시저를 그냥 호출해주기만 하면 됩니다.

프로그램은 프로시져가 필요할 때 프로지서에 값을 보내고 계산된 값을 받아오는데요, 이 일을 하는 것을 Parameter(인수)라 부릅니다.

프로그램이 프로시저를 실행할 때 아래와 같은 단계를 거칩니다.

1. 프로시저가 접근할 수 있는 곳에 인수를 넣어둔다.
2. 프로시저로 제어를 넘긴다.
3. 프로시저가 필요로 하는 메모리를 프로시저에게 제공한다.
4. 필요한 작업을 수행한다.
5. 프로시저를 호출한 프로그램이 접근할 수 있는 곳에 결괏값을 넣는다.
6. 프로시저가 나중에 다시 호출될 것에 대비하여, 원래 위치로 제어를 돌려준다.

이 과정에서 프로시저에 전달할 인수를 보통 a0부터 a3까지의 레지스터에 넣고, 프로시저로부터 반환되는 값을 v0, v1에 넣습니다. 그리고 프로시저가 종료되면 다시 원래 실행하던 부분, 즉 원래의 주소로 돌아와야 하기 때문에 프로시저를 호출한 곳의 주소를 저장할 레지스터가 필요한데, 이것이 $ra 레지스터입니다.

위 과정을 담당하는 것은 jal (Jump And Link) 명령어입니다. 이 명령어는 지정된 주소(프로시저가 있는 주소)로 점프함과 동시에, 다음 명령어가 있는 주소(프로시저가 종료되고 돌아올 주소 = Return Address, 복귀 주소)를 ra 레지스터에 저장합니다. 이 과정에서 a0에서 a3에 프로시저에 전달할 인수값을 넣고, jal 명령어를 이용하는 부분을 Caller (호출하는 프로그램), Caller가 호출한 프로시저를 Callee (호출당하는 프로그램) 라고 합니다.

프로시저가 종료된 이후 원래 프로그램이 실행되던 주소, 그러니까 복귀 주소로 돌아가야 한다고 말씀드렸는데요. 이런 과정이 가능하려면 현재 실행 중인 명령어의 주소를 기억하는 레지스터가 하나 필요합니다. 이 레지스터의 이름은 보통 프로그램 카운터, Program Counter라고 부르며 줄여서 PC라고도 합니다.

프로그램 하나는 32개의 비트, 4개의 Byte로 표현됩니다. 그래서 프로그램 한 줄을 실행할 때마다 PC의 값은 4씩 증가합니다. 또한, jal 명령어는 복귀 주소를 ra에 저장한다고 했었죠? 이때 ra에 저장하는 값이 바로 PC + 4가 됩니다.

 

Stack Pointer

프로시저는 인수 레지스터 4개, 결과값 레지스터 2개를 부여받는다고 했었는데요, 만약 프로시저를 실행하는 과정에서 이거보다 더 많은 레지스터가 필요한 경우 스택형태의 메모리에 필요한 값들을 저장하게 됩니다. 이 과정을 총괄하는 것이 바로 스택 포인터, Stack Pointer입니다. 예시를 통해 자세히 알아보도록 하겠습니다.

int leaf (int g, int h, int i, int j) {
	int f;
	f = (g + h) - (i + j);
	return f;
}

이러한 C++ 코드를 어셈블리어로 변환해보겠습니다. 변수 g, h, i, j는 각각 a0, a1, a2, a3에 해당하고, f는 s0에 해당한다고 생각하겠습니다. 먼저, 컴파일된 프로그램은 아래에서부터 시작합니다.

leaf:

이 아래로 작성되는 프로그램은 leaf라는 이름의 프로시저에 해당하며, leaf 프로시저가 호출되었을 때 실행되는 코드임을 의미합니다.

이제 저 프로그램을 계산하기 위해서는 g + h의 값을 저장할 임시 레지스터 t0와 i + j의 값을 저장할 임시 레지스터 t1을 필요로 합니다. 또한, 함수 내부에서 저장된 f의 값을 저장할 레지스터 s0도 필요합니다.

그런데, 프로시저가 실행된다고 해서 s0나 t0, t1에 저장된 값이 바뀌면 안 되잖아요? 그래서 s0, t0, t1에 이미 저장되어 있던 값들을 메모리에 옮겨 놓은 뒤에, 레지스터들을 사용할 겁니다. 그리고 프로시저가 종료될 때 메모리에 저장해 둔 값을 다시 s0, t0, t1에 복구시켜 두면 되겠죠. 그래서, 저희는 스택에 이 3개의 변수를 위한 자리를 만들어줄겁니다. 

addi sp, sp, -12
sw t1, 8(sp)
sw t0, 4(sp)
sw s0, 0(sp)

먼저 첫번째 코드는 sp에 저장된 값에 12를 빼라는 것을 의미합니다. sp는 현재 스택 포인터의 위치를 의미하는 레지스터입니다. sp가 원래 있던 자리에서 12를 빼주었기 때문에, 무언가를 넣을 수 있는 12 Byte의 공간이 새로 생긴 것입니다.

그림으로 표현하면 위와 같습니다. 위 코드의 나머지 부분은 새로 생긴 공간에 s0, t0, t1의 값을 저장하는 부분입니다.

이제 실제로 코드를 실행하는 부분은 아래와 같습니다.

add t0, a0, a1
add t1, a2, a3
sub s0, t0, t1
add v0, s0, zero

v0는 프로시저가 반환할 값이 들어갈 레지스터입니다. 이제 연산이 완료되었으니, 스택에 저장해 둔 값들을 다시 레지스터 s0, t0, t1에 넣어주어야겠죠. 

lw s0, 0(sp)
lw t0, 4(sp)
lw t1, 8(sp)
addi sp, sp, 12

lw 명령어를 이용해 메모리에 저장되어 있던 값을 레지스터로 옮긴 후, sp의 값에도 다시 12를 더해줘 원래 상태로 복구시켜 주는 것입니다. 그림으로 나타내면 아래와 같습니다.

이제 마지막으로 ra에 저장된 복귀 주소로 돌아가는 코드만 작성해주면 마무리됩니다.

jr ra

 

jr 명령어는 j 명령어와 똑같이 작동합니다. 다만, j 명령어는 원하는 코드의 이름을 입력받아 그 코드로 이동하는 명령어였다면 jr 명령어는 레지스터를 받아 레지스터에 저장된 주소값으로 이동하는 명령어입니다.

이렇게 임시 레지스터를 사용하고, 사용한 레지스터를 다시 원상태로 복구시키는 과정을 알아보았습니다. 그런데, 사용하지도 않을 값을 쓸데없이 저장했다가 복구하는 일이 생길 수도 있습니다. 이를 예방하기 위해서 MIPS가 선택한 방법은 레지스터의 종류를 나누는 것이었습니다.

t0부터 t9까지의 레지스터는 프로시저가 호출되었을 때, Callee가 마음대로 사용하고 복구해주지 않습니다. s0부터 s7까지의 레지스터는 프로시저가 호출되어도 그 값이 바뀌지 않습니다. 즉, Callee가 이 레지스터를 사용하면 원래 값을 저장했다가 복구해 줍니다.

그래서, 위와 같은 약속이 있다면 바로 위의 프로그램에서 t0와 t1의 값을 복구하는 부분의 코드를 줄일 수 있습니다. 

 

재귀 프로시저

다른 프로시저를 호출하지 않는 프로시저를 말단 프로시저, Leaf Procedure라고 합니다. 모든 프로시저가 말단 프로시저면 좋겠지만 대부분의 경우 그렇지 않습니다. 심지어 자기 자신을 호출하는 프로시저도 존재합니다.

그런데 이런 프로시저는 다루기 되게 까다롭습니다. 어떤 프로시저 A가 인수값 3을 가지고 호출되었다고 가정합시다. 그러면 프로그램은 레지스터 a0에 3을 넣고, jal A 명령어를 실행하겠죠. 그리고 프로시저 A가 인수값 7을 가지고 프로시저 B를 호출한다고 생각해 봅시다. 그러면 프로시저 A는 또 레지스터 a0에 7을 넣고, jal B 명령어를 실행할 겁니다.

벌써 2가지 문제점이 생겼습니다. 프로시저 A가 종료된 것이 아니기 때문에 a0에 저장된 3이라는 값이 아직 필요한데, 이 값이 7로 업데이트되어버렸습니다. 또한, jal A 명령어가 실행되었을 때 ra 레지스터에는 A의 복귀 주소가 들어가는데 jal B 명령어가 실행되면 ra 레지스터의 값이 B의 복귀 주소로 업데이트되기 때문에 충돌이 또 발생합니다.

이러한 문제를 해결하기 위해 보존되어야 할 모든 값을 전부 스택에 집어넣어 주어야 합니다. 

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

위와 같이 n 팩토리얼을 계산하는 함수에 해당하는 MIPS 어셈블리 코드를 한번 보겠습니다. 이 프로시저는 자기 자신을 다시 호출할 수 있기 때문에, 인수가 저장되는 레지스터 a0와 복귀 주소가 저장되는 레지스터 r0를 스택에 저장해주어야 합니다.

fact:
addi sp, sp, -8
sw ra, 4(sp)
sw a0, 0(sp)

그리고 이 프로시저는 n이 1보다 작은 지를 검사해서 그렇지 않으면 L1으로 가도록 하게 합니다.

slti t0, a0, 1
beq t0, zero, L1

이렇게 n이 저장된 a0를 왼쪽으로 1만큼 Shift 시킨 뒤 이 값을 0과 비교하게 되면 n이 1 이상인지 아닌지를 비교할 수 있습니다. L1은 재귀 명령어를 작성해 줄 것이고, 그 아래에는 n이 1 미만일 경우에 대한 코드를 작성해 주면 됩니다.

addi v0, zero, 1

1을 리턴하는 부분입니다. 1을 리턴한 후 프로시저가 종료되어야 하므로, ra와 a0에 저장된 값을 원래대로 돌려줘야 하는데요. 그런데 n이 1일 경우에는 새로운 프로시저가 호출되지 않기 때문에 a0와 ra 값이 변할 일이 없습니다. 그래서, 그냥 stack에 저장된 2개의 값은 버려도 됩니다.

addi sp, sp, 8
jr ra

이제 n이 1 이상일 경우를 보겠습니다. 먼저 n을 1만큼 감소시킨 뒤 이 감소된 값으로 새로운 프러시저를 호출해야겠죠.

L1: 
addi a0, a0, -1
jal fact

다음은 호출한 프로그램으로 되돌아가는 부분입니다. a0, ra에 있던 값들을 원상 복구시켜 줍니다.

lw a0, 0(sp)
lw ra, 4(sp)
addi sp, sp, 8

마지막으로 인수인 a0와 결괏값 레지스터인 v0의 값을 곱해서 출력해 줍니다. 두 수를 곱하는 명령어는 mul입니다.

mul v0, a0, v0
jr ra

이렇게 팩토리얼을 계산하는 MIPS 어셈블리 코드를 작성할 수 있었습니다.

10! 을 계산하는 과정에서 스택의 구조를 간단하게 나타낸 표입니다.

 

MIPS 메모리 할당과 레지스터 관례

위는 메모리의 구조를 간단하게 나타낸 것입니다. 이 구조는 MIPS에 한정된 것이 아니라 소프트웨어적인 관례로서 사용되는 것입니다. 최하위 주소 부분은 사용되지 않으며, 그 위로는 MIPS 기계어가 들어가는 부분입니다. 이 부분을 Text Segment라고 합니다. 그 위에는 Static Data Segment가 있습니다. 여기에는 상수나, 기타 정적인 변수가 들어갑니다.

그 위로는 Stack과 Heap이 존재하게 됩니다. Stack은 방금까지 알아보았던 부분이고, Heap에는 여러 Dynamic Data, C++을 예로 들면 new 명령어를 통해 만들어지는 변수들이 저장되는 공간입니다. Stack과 Heap은 서로를 마주 보고 자라기 때문에, 메모리를 보다 효율적으로 사용할 수 있습니다.

위는 MIPS 어셈블리어에서 레지스터가 어떻게 사용되는지를 정리해 나타낸 표입니다. 

 

문자와 문자열

lb (Load Byte)는 메모리에서 하나의 바이트를 읽어 레지스터의 오른쪽 8비트에 채우는 명령어이고, sb (Store Byte)는 레지스터의 오른쪽 8비트를 메모리로 보내는 명령어입니다. 

그래서 메모리에서 하나의 바이트를 복사할 때는, 아래와 같이 할 수 있습니다. (sp에 있는 바이트를 gp로 복사하는 코드)

lb t0, 0(sp)
sb t0, 0(gp)

조금 더 복잡한 예시로, 문자열 y를 문자열 x에 복사하는 strcpy 프로시저를 한번 보겠습니다.

void strcpy (char x[], char y[]) {
	int i = 0;
	while ((x[i] = y[i]) != '\0')
	i += 1;
}

(\0은 null Byte로 문자열이 끝났음을 의미합니다.)

이 프로시저의 MIPS 코드는 아래와 같습니다. a0와 a1은 배열 x, y의 시작 주소를 저장하며 변수 i는 s0에 대응됩니다.

strcpy:
addi sp, sp, -4
sw s0, 4(sp)
add s0, zero, zero　　　# i를 0으로 초기화

L1:
add t1, s0, a1　　　# i에 y의 시작 주소를 더해 y[i]의 주소를 구하기
lbu t2, 0(t1)　　　# 임시 레지스터 t2에 y[i]의 값 넣기
add t3, s0, a0　　　# 임시 레지스터 t3에 x[i]의 주소 넣기
sb t2, 0(t3)　　　# t2에 저장된 값을 x[i]에 넣기
beq t2, zero, L2　　　# 복사한 값이 0인 경우 L2로 이동
addi s0, s0, 1
j L1

L2:
lw s0, 0(sp)
addi sp, sp, 4
jr ra

lbu 명령어는 lb와 같게 작동하지만, 차이점은 lb는 바이트를 부호확장하여 레지스터에 넣지만 lbu 명령어는 바이트를 0 확장하여 레지스터에 넣습니다.

또한, MIPS 명령어에는 하프워드(Halfword), 16비트 데이터에 대한 명령어도 포함되어 있습니다. lh와 lhu, sh가 그것입니다. lb, lbu, sb와 같게 작동하지만 8비트가 아닌 16비트에 대해서작동하는 명령어라고 생각하시면 됩니다.

 

32비트 주소 표현법

MIPS 명령어의 길이는 32비트이고, 하드웨어에서 사용되는 주소값 역시 32비트입니다. 따라서, 명령어 내에서 32비트 주소를 일반적으로 표시할 방법이 없습니다. 32비트 상수도 마찬가지고요. 이번 섹션에서는 이 문제들을 어떻게 해결할지 알아보도록 하겠습니다.

먼저 32비트 상수 같은 경우는 간단한 해결 방법이 있습니다. 레지스터의 상위 16비트에는 lui 명령어, 하위 16비트에는 ori 명령어를 사용해 상수를 채우는 것입니다. 예를 들어, s0에 0000 0000 0011 1101 0000 1001 0000 0000을 채우고 싶다고 가정합시다.

그러면 lui 명령어를 이용해 상위 16비트 0000 0000 0011 1101 (= 61)을 채우고, ori 명령어를 이용해 0000 1001 0000 0000 (=2304)을 채우는 겁니다.

lui s0, 61
ori s0, s0, 2304

다음으로는 주소값에 대해 설명해 보겠습니다. 가장 대표적으로 주소값을 사용하는 명령어에는 bne가 있습니다. bne 명령어는 2개의 연산자와 주소값을 받기 때문에, 주소가 들어갈 공간은 16비트에 불과합니다. 만약 프로그램에서 사용 가능한 주소가 $2^{16}$보다 더 커질 수 없다면, 아주 작은 프로그램만 실행할 수 있을 겁니다. 그래서 그 대안으로, 점프할 명령어의 주소값을 그대로 입력하는 것이 아닌 현재 주소와 얼마나 떨어져 있는지를 입력하는 것입니다.

현재 주소를 저장하는 레지스터를 PC라고 불렀잖아요? 이렇게 되면 PC로부터 $\pm 2^{15}$ 워드만큼 떨어진 곳으로는 어디든 점프할 수 있게 됩니다. 이런 방식을 PC-relative Addressing이라고 합니다.

여기서 주의점은, 실제 MIPS에서는 현재 명령어의 주소를 기준으로 하는 것이 아닌 PC + 4를 기준으로 한다는 것입니다. 그 이유는 명령어를 실행하기 전에 프로그램이 미리 PC의 값을 4 늘려놓기 때문입니다.

Loop: sll ~~
addi ~~
addi ~~
bne ~ ~ Loop

Exit:

위와 같은 코드가 있다고 생각하고, Loop의 주소가 80,000이라고 하겠습니다. 그러면 bne가 있는 곳의 주소는 80,012가 됩니다. 따라서, bne가 실행될 때의 PC 값은 80,012겠지만 프로그램이 미리 4를 더해둔다고 했으므로 80,016일 것입니다. 저희가 점프해야 할 곳의 주소값은 80,000이므로, PC + 4를 기준으로 -16만큼 떨어져 있습니다. 따라서 bne 명령어 부분을 기계어로 번역하면 주소값 부분에 -16이 들어가게 됩니다.

 

또 다른 주소값을 사용하는 명령어는 바로 j 명령어입니다. 이 명령어는 J 타입의 형식을 사용합니다.

J 타입 명령어는 위와 같이 6비트의 Opcode 필드와 26비트의 주소 필드로 나뉩니다. j, jal과 같은 명령어는 bne와 같은 명령어에 비해 아주 멀리 떨어진 곳으로 점프해야 할 상황이 많습니다. 호출해야 할 프로시저가 현재 PC와 가까울 것이라는 보장이 없기 때문이죠.

그래서 이 명령어들은 PC-relative Addressing을 사용하지 않고 주소값을 그래도 입력하는 방식을 사용합니다. 그런데 주소값을 넣을 필드는 26비트이고, 주소값은 32비트이잖아요? 6개의 비트가 부족합니다. 이를 채우는 전략은 2가지입니다.

첫 번째로, MIPS 명령어의 길이는 항상 4바이트이기 때문에, 주소값은 항상 4의 배수입니다. 그래서 주소값을 바이트 단위가 아니라 비트 단위로 표시하게 되면 총 2개의 비트를 아낄 수 있습니다. 남은 4개의 비트를 채우기 위해, MIPS는 PC의 상위 4개의 비트를 그대로 가져오고, 하위 28비트만 바꾸는 방법을 사용합니다. 

Loop: sll ~~
addi ~~
addi ~~
j Loop

Exit:

위의 예시에서 bne를 j로만 바꿔준 코드입니다. 점프해야 할 주소값 80000을 2진수로 바꾸면 0000 0000 0000 0001 0011 1000 1000 0000입니다. 여기에서 기계어를 작성할 때 가장 상위 4개의 비트 0000을 지우고, 가장 하위 2개의 비트 00을 지워 "0000 0000 0001 0011 1000 1000 00" 이렇게 26개의 비트를 작성합니다.

프로그램이 이를 계산할 때, 자동으로 가장 하위에 2개의 비트 00을 추가합니다. 그리고, 해당 명령어를 실행할 때의 PC 값 80,016 (2진수로 0000 0000 0000 0001 0011 1000 1001 0000)에서 상위 4개의 비트 0000을 가져와 32개의 비트로 이루어진 주소값을 완성합니다.

 

감사합니다.

---

이 글은 컴퓨터공학과 학부생이 개인 공부 목적으로 작성한 글이므로, 부정확하거나 틀린 내용이 있을 수 있으니 참고용으로만 봐주시면 좋겠습니다. 레퍼런스 및 글에 대한 기본적인 정보는 이 글을 참고해 주세요.