[Chapter 2.5 컴퓨터 구조 및 설계] 메모리 구조와 레지스터 스필링, 함수 및 재귀함수의 컴파일

본 정리는 CS422-컴퓨터 구조 및 설계 : 하드웨어/소프트웨어 인터페이스. David A. Patterson,존 헤네시 책을 바탕으로 하고 있음을 미리 알립니다.

 

프로시저 혹은 함수가 불리는 과정

---

프로시저 : 제공되는 인수에 따라서 특정 작업을 수행하는 서브루틴. 프로그래밍에서 함수와 같다고 보면 된다.

 

메인 루틴을 Caller(호출 프로그램)

 

프로시저를 Callee(피호출 프로그램)라고 정의하자.

 

프로그램이 프로시저를 실행할 때  다음과 같은 6가지 과정을 거친다.

1. Caller는 Callee가 접근할 수 있는 곳에 인수를 넣는다. 보통 $a0 - $a3 레지스터를 사용한다.(argument)
2. Caller는 Callee에 제어를 넘긴다.
3. Callee가 필요로 하는 메모리 자원을 얻는다.
4. Callee가 필요한 작업을 수행한다.
5. Callee가 Caller가 접근할 수 있는 장소에 결과 값을 넣는다. 보통 $v0 - $v1의 두 개의 레지스터 값을 이용해 결과 값을 저장한다.
6. Callee는 프로그램 내의 여러 곳에서 호출될 수 있으므로 원래 위치로 제어를 넘겨준다. 보통 $ra 에 return address가 담겨있다.

레지스터는 총 32개가 존재한다고 하였고, 각 레지스터에는 각각 역할이 있다고 하였다. 다음 그림은 32개의 역할을 나타낸 것이다.

레지스터의 역할

 

 

Jal 명령어와 jr 명령어

 

MIPS 어셈블리어에서 그렇다면 함수가 실행될 때 어떤 명령어가 실행될까?

바로 Jal (Jump and link) 명령어 이다.

 

지정된 주소로 점프하면서 동시에 다음 명령어의 주소를 $ra레지스터에 저장하는 명령이다.

즉, PC+4의 값(다음 명령어의 주소)을 $ra 레지스터에 저장하게 될 것이다.

 

이름에서 link는 프로시저 종료 후 올바른 주소로 되돌아올 수 있도록 호출한 곳과 프로시저 사이에 주소 또는 링크를 형성한다는 듯이다. $ra에 기억되는 이 링크를 복귀 주소(return address)라고 부른다.

jal ProcedureAddress #jump and link

 Jal 명령어는  J format을 따른다.

J format

 

 

 

함수가 종료되었을 때는 jr (jump register) 명령어가 쓰인다.

이 명령어는 레지스터에 저장된 주소로 무조건 점프하라는 뜻이다.

 

즉, jr $ra를 해주면 저장된 return address(PC+4)로 복귀하게 된다.

 

R format을 따른다.

R format

 

 

레지스터 스필링 (spilling)

---

만약 인수가 인수 레지스터의 개수 $a0 -$a3인 4개보다 많으면 어떻게 될까?

바로 레지스터 스필링 과정을 거치게 된다.

 

'작을수록 빠르다'는 원칙에 의하면 레지스터가 더 작으므로 메모리는 레지스터보다 느리고, 데이터가 레지스터에 있으면 더 빨리 접근할 수 있다.

 

그러므로 컴파일러는 자주 사용되는 변수를 가능한 한 많이 레지스터에 넣고 나머지 변수는 메모리에 저장했다가 필요할 때 꺼내서 레지스터에 넣는다. 자주 사용하지 않는 변수를 메모리에 넣는 일을 레지스터 스필링이라고 한다.

 

레지스터 스필링에 이상적인 자료구조는 바로 스택(stack)이다.

 

스택은 후입선출 (Last in First out) 으로 구성된 자료구조이다.

 

스택에는 다음 프로시저가 스필 할 레지스터를 저장할 장소나 레지스터의 옛날 값이 저장된 장소를 표시하기 위해 최근에 할당된 주소를 가리키는 포인터가 필요하다. 이 스택 포인터는 레지스터 값하나 가 스택에 저장되거나 스택에서 복구될 때마다 한 워드씩 조정된다. 

 

MIPS 레지스터에도 위 사진에 29번 레지스터에 $sp(stack pointer) 레지스터가 있는 것을 알 수 있다.

레지스터 스필링의 과정

스택에 데이터를 넣는 과정을 push 한다고 하는데, 관례적으로 sp의 값을 감소시키고 (메모리 기준 위에서 아래로 스택 포인터를 이동시킨다.) 메모리에서 감소시킨 자리에 데이터를 넣어준다. 즉, 한 word를 스택에 넣는다고 생각하면, $sp = $sp – 4 가 되고 이후 sw $s0, 0($sp) 등을 통해 그 자리에 데이터를 저장해주면 되는 것이다.

 

그렇다면 데이터를 빼는 작업도 있을 것이다. 이를 pop 한다고 한다. 반대로 sp의 값을 증가시키고 (메모리 기준 아래에서 위로 스택 포인터를 이동시킨다.) 메모리에서 증가시킨 자리에 데이터를 불러온다. 즉, 한 word를 스택에서 뺀다고 생각하면, $sp = $sp + 4 가 되고 이후 lw $s0, 0($sp) 등을 통해 그 자리에 데이터를 load 해주면 되는 것이다.

C 함수 컴파일 예시

---

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

Arguments g, …, j in $a0, …, $a3

f in $s0

 

컴파일된 프로시저는 다음과 같은 프로시저 레이블로부터 시작된다.

leaf_example:

 

다음 단계는 프로시저가 사용할 레지스터 값을 저장하는 것이다. 위 예시에서는 $s0,$t0,$t1의 3개의 레지스터가 함수 내부 변수를 위해 필요하고, 이를 위해 레지스터 스필링 즉, 스택(메모리)에 세 워드를 저장할 자리를 만든 후 저장해준다.

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

이로 인해 이제 $s0,$t0,$t1 이 레지스터들을 Callee 즉, 함수 내부에서 사용할 수 있게 되는 것이다.

 

이제 내 함수 내부 산술 연산을 컴파일해주면,

add $t0, $a0, $a1
add $t1, $a2, $a3
sub $s0, $t0, $t1

다음과 같이 될 것이고,

계산 결과가 결과 값 레지스터 즉, $v0에 저장될 것이다.

add $v0, $s0, $zero

이제 함수 내부에서 더 이상 레지스터를 사용할 일이 없으므로, 호출 프로그램(Caller)으로 되돌아가기 전에 저장해 두었던 값을 스택에서 꺼내 레지스터를 원상 복구한다. 즉, 이 과정을 함수 내부에서 일어나는 일들이 외부 Caller에게 영향을 미치지 않도록 하는 것이다.

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

이제 복귀 주소를 사용하는 jr명령어로 종료시킨다.

jr $ra

 

이렇게 프로시저 내에서 다른 프로시저를 호출하지 않는 프로시저를 Leaf 프로시저라고 한다.

 

함수 실행 과정을 스택 구조로 살펴보자.

함수 시작 전

함수 시작 전 다음과 같은 모습에서 스택에 local 데이터를 저장하여 다음과 같은 모습이 될 것이다.

함수 실행 중

함수가 끝나면 스택에 쌓여있는 데이터들을 다시 복구해줄 것이다.

함수 종료 후

$fp는 스택을 함수 별로 나눌 수 있게 함수의 스택 시작 주소를 나타낸다.

 

 

우리는 자기 자신을 호출하는 재귀 프로시저를 알고 있다.

 

다음 예시를 통해 재귀 프로시저는 어떻게 컴파일되는지 알아보자.

 

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

Argument n in $a0

Result in $v0

 

컴파일된 프로그램은 프로시저 레이블로 시작하며, 뒤이어 복귀 주소와 $a0를 스택에 저장하는 명령어가 나온다.

이를 저장하는 이유가 뭘까?

이 함수는 재귀로 다시 한번 불릴 수도 있는 함수다. 즉, 재귀 함수의 return address와 인자 값이 보존되어야 내가 부른 fact 함수가 끝나 다시 내가 불렸을 때, 나의 return address와 인자 값을 사용할 수 있을 것이기 때문이다.

 

즉, fact를 호출한 프로그램(Caller)의 주소를 저장하는 것이다.

fact:
addi $sp, $sp, -8 # adjust stack for 2 items
sw $ra, 4($sp) # save return address
sw $a0, 0($sp) # save argument

 

 다음은 n이 1보다 작은지 검사해서 n>=1이면 L1으로 가게 하는 명령어들이다.

slti $t0, $a0, 1 # test for n < 1
beq $t0, $zero, L1

 

n이 1보다 작으면 1을 결과 값 레지스터에 넣는다. 복귀하기 저네 스택에 저장된 값 두 개를 버리고(pop) 복귀 주소로 점프한다. 스택에 있는 값을 꺼내어 $a0나 $ra로 넣을 수도 있겠지만 n이 1보다 작을 때는 $a0와 $ra값이 바뀌지 않기 때문에 그럴 필요가 없다.

addi $v0, $zero, 1 # if so, result is 1
addi $sp, $sp, 8 # pop 2 items from stack
jr $ra # and return

 

n이 1보다 작지 않으면, 인수 n을 감소시키고 이 감소된 값으로 다시 fact를 호출한다.

L1: addi $a0, $a0, -1 # else decrement n 
jal fact # recursive call

이제 호출 프로그램으로 되돌아가는 부분이다. 먼저 스택 포인터를 사용해서 Caller의 복귀 주소와 인수 값을 복귀한다.

lw $a0, 0($sp) # restore original n
lw $ra, 4($sp) # and return address
addi $sp, $sp, 8 # pop 2 items from stack

다음으로 인수 $a0와 결과 값 레지스터의 현재 값을 곱해서 $v0에 넣는다.

mul $v0, $a0, $v0 # return n*fact(n-1)

마지막으로 복귀 주소를 이용해 되돌아간다.

jr $ra # and return

 

이해하기 쉽지 않겠지만, 천천히 스택 구조를 그려보면 이해가 갈 것이다.

 

 

프로시저 프레임

---

레지스터에 들어가지 못할 만큼 큰 배열이나 구조체 같은 지역 변수를 저장하는 데도 스택이 사용되기 때문에 스택의 지역 문제가 복잡해진다. 프로시저의 저장된 레지스터와 지역변수를 가지고 있는 스택 영역을 프로시저 프레임 또는 액티베이션 레코드라고 부른다. MIPS 소프트웨어 중에는 프레임 포인터(frame pointer $fp)가 프로시저 프레임의 첫 번째 워드를 가리키도록 하는 것이 있다. 즉, 베이스 레지스터의 역할을 하는 것이다. 즉, 지역변수의 참조가 간단해진다.

 

 

메모리 할당 방식

---

메모리 구조

스택에 사용되는 자동 변수 외에도 정적 변수와 동적 자료구조(malloc)를 위한 메모리 공간이 필요하다.

이에 따라 스택을 포함한 나머지 메모리 구조는 어떻게 사용되나 설명해보고자 한다.

• 스택 : 자동 변수, 지역 변수가 저장되는 공간으로 최상위 주소에서부터 시작해서 아래쪽으로 자란다.
• Reserved : 최하위 주소 부분은 사용이 유보되어 있다.
• Text : 우리가 각종 format을 사용하여 바꾼 MIPS 기계어 코드가 들어가는 공간이다. 전통적으로 텍스트 세그먼트라고 부른다.
• static data : 상수와 기타 정적 변수들이 여기에 들어간다. c에서의 정적 배열은 그 크기가 고정되어 있어서 정적 데이터 세그먼트에 잘 맞는다.
• heap : malloc으로 할당한 배열이나 길이가 들쭉 날쭉한 자료구조는 heap에 들어간다. heap은 stack과 마찬가지로 동적인 길이를 갖고 있고 아래에서 위로 자란다.

C에서는 이러한 메모리 할당을 프로그램이 (프로그래머가) 통제하는데, 이 부분이 흔하고도 까다로운 여러 버그의 근원이다. malloc후 free 하는 것을 잊어 메모리 누출이 발생하여 메모리 부족으로 운영체제가 붕괴될 수도 있고, 반면에 너무 일찍 반납하면 프로그램 의도와 상관없이 엉뚱한 곳을 가리키는 매달린 포인터(dangling pointer)가 발생한다. 자바에서는 이러한 것을 피하기 위해 자동 메모리 할당과 가비지 컬렉션을 사용한다.