피호출자는 R0~R3을 마음대로 쓰니, 호출자가 레지스터에 두었던 변수를 덮어쓸 수
있습니다. 돌아온 뒤에도 변수가 제 값을 지키려면 어떻게 해야 할까요?
레지스터 맡겨 두기
호출자는 피호출자가 어느 레지스터를 쓰는지 모릅니다. 그래서 돌아와서도 쓸
레지스터를 CALL 앞에서 스택에 PUSH해 두고, 돌아온 뒤 POP으로 되찾습니다. 다시
쓰지 않을 레지스터는 맡기지 않습니다.
C
1short f(short x) {
2 return x + (x + (x + 1));
3}
4
5int main(void) {
6 short a = 5;
7 short b = f(1) + a;
8}
어셈블리어
0–1LDI R2, 5
2–3LDI R3, 0
4–5PUSH R2
6–7PUSH R3
8–9LDI R0, 1
10–11LDI R1, 0
12–13PUSH R1
14–15PUSH R0
16–17CALL f
18–19ADDI SP, 2
20–21POP R3
22–23POP R2
24–25ADD R0, R2
26–27ADC R1, R3
28–29STORE R0, b
30–31STORE R1, b+1
32–33HALT
34–35f: MOVE R3, SP
36–37ADDI R3, 1
38–39LOAD R2, [R3]
40–41ADDI R3, 1
42–43LOAD R3, [R3]
44–45MOVE R0, R2
46–47MOVE R1, R3
48–49ADDI R0, 1
50–51ADCI R1, 0
52–53ADD R0, R2
54–55ADC R1, R3
56–57ADD R0, R2
58–59ADC R1, R3
60–61RET
62–63b: 0, 0
R0 0R1 0R2 0R3 0SP 0Z 0C 0
a@R3:R2 0b@62 0
스택
비어 있음
함수 글 끝의 프로그램입니다. 다음을 누르며 a가 든 R3:R2가 스택에
들어갔다가 돌아오는 것을 봅시다. 이제 b는 9가 됩니다.
이렇게 호출 한 번이 스택에 쌓는 묶음, 곧 돌아올 주소와 맡긴 레지스터를 스택
프레임(stack frame)이라 합니다. 레지스터가 모자라 메모리에 둘 지역 변수와
포인터로 주소를 가져가는 지역 변수도 프레임 안에 자리를 잡습니다.
함수에 들어오면 SUBI SP, 4처럼 SP에서 지역 변수의 칸 수를 빼 자리를 만들고,
돌아가기 전에 같은 수를 ADDI로 더해 치웁니다.
인자와 결과를 어디로 주고받고, 어느 레지스터를 누가 맡겨 둘지 정한 약속을 호출
규약(calling convention)이라 합니다. 실제 컴퓨터는 호출자가 맡길 레지스터와
피호출자가 맡길 레지스터를 나눠 정해 둡니다.
재귀
함수가 자기 자신을 부르는 것을 재귀(recursion)라 합니다. 재귀에서는 같은
함수의 호출 여러 개가 겹쳐 있고, 호출마다 n이 다릅니다. 각 호출은 다음 호출 전에
자기 n을 스택 프레임에 맡겨 두니, 돌아와서 제 n을 되찾습니다.
C
1short sum(short n) {
2 if (n == 0)
3 return 0;
4 return n + sum(n - 1);
5}
6
7int main(void) {
8 short s = sum(3);
9}
어셈블리어
0–1LDI R0, 3
2–3LDI R1, 0
4–5PUSH R1
6–7PUSH R0
8–9CALL sum
10–11ADDI SP, 2
12–13MOVE R2, R0
14–15MOVE R3, R1
16–17HALT
18–19sum: MOVE R3, SP
20–21ADDI R3, 1
22–23LOAD R2, [R3]
24–25ADDI R3, 1
26–27LOAD R3, [R3]
28–29MOVE R0, R2
30–31OR R0, R3
32–33JNZ end1
34–35LDI R0, 0
36–37LDI R1, 0
38–39RET
40–41end1: PUSH R2
42–43PUSH R3
44–45MOVE R0, R2
46–47MOVE R1, R3
48–49SUBI R0, 1
50–51SBCI R1, 0
52–53PUSH R1
54–55PUSH R0
56–57CALL sum
58–59ADDI SP, 2
60–61POP R3
62–63POP R2
64–65ADD R0, R2
66–67ADC R1, R3
68–69RET
R0 0R1 0R2 0R3 0SP 0Z 0C 0
s@R3:R2 0
스택
비어 있음
재생하며 스택을 봅시다. 가장 깊이 들어가면 sum(3), sum(2), sum(1)이 각각 맡긴
n의 값 3, 2, 1이 다음 호출의 인자, 돌아올 주소와 번갈아 쌓이고, n이 0에 닿은
뒤부터는 가장 나중에 쌓인 것부터 하나씩 꺼내며 더합니다.
이렇게 프레임이 쌓인 스택 전체를 호출 스택(call stack)이라 합니다.
스택 오버플로
자기 자신을 멈출 조건 없이 부르면 어떻게 될까요?
C
어셈블리어
0–1LDI R0, 0
2–3LDI R1, 0
4–5PUSH R1
6–7PUSH R0
8–9CALL f
10–11ADDI SP, 2
12–13HALT
14–15f: MOVE R3, SP
16–17ADDI R3, 1
18–19LOAD R2, [R3]
20–21ADDI R3, 1
22–23LOAD R3, [R3]
24–25MOVE R0, R2
26–27MOVE R1, R3
28–29ADDI R0, 1
30–31ADCI R1, 0
32–33PUSH R1
34–35PUSH R0
36–37CALL f
38–39ADDI SP, 2
40–41RET
R0 0R1 0R2 0R3 0SP 0Z 0C 0
스택
비어 있음
프레임이 끝없이 쌓여 스택이 프로그램 칸까지 내려옵니다. 이를 스택
오버플로(stack overflow)라 합니다. 실제 컴퓨터는 스택 구역 끝을 넘는 순간
프로그램을 멈춰, 다른 데이터를 덮어쓰지 않게 합니다.
마무리
함수를 부르면 맡길 레지스터와 돌아올 주소를 스택 프레임으로 쌓고, 끝나면 치우고
돌아갑니다. 이제 함수는 어디서 불러도 제대로 돌아오는 부품이 되었습니다. 잘 만든
함수는 다른 프로그램에서도 쓰고 싶어지는데, 그러려면 함수를 따로 파일에 두고
가져다 써야 합니다. 다음 글에서는 다른 파일에 있는 함수를 부를 수
있게 해 주는 링커를 살펴봅시다.
도전 문제
스택으로 쓸 수 있는 칸이 60칸입니다. 이 글의 컴파일 규칙대로 하면, 바깥에서 sum(n)을 부를 때 스택이 60칸을 넘지 않는 가장 큰 n은 얼마일까요? 숫자로 답하세요.
short sum(short n) {
if (n == 0)
return 0;
return n + sum(n - 1);
}