3.7 프로시저 (Procedures)
프로시저는 소프트웨어에서 핵심적인 추상화 개념입니다. 프로시저는 특정 기능을 구현하는 코드를 지정된 인수 집합과 선택적 반환값과 함께 패키징하는 방법을 제공합니다. 이 함수는 프로그램의 다양한 지점에서 호출할 수 있습니다.
프로시저의 주요 메커니즘
프로시저 P가 프로시저 Q를 호출하고, Q가 실행된 후 P로 돌아오는 작업에는 다음 메커니즘들이 포함됩니다:
1. 제어 전달 (Passing Control)
- 진입 시: 프로그램 카운터를 Q의 시작 주소로 설정
- 반환 시: P의 호출 다음 명령으로 설정
2. 데이터 전달 (Passing Data)
- P는 Q에게 하나 이상의 매개변수 제공
- Q는 P에게 값을 반환
3. 메모리 할당/해제 (Memory Management)
- Q는 시작 시 지역 변수를 위한 공간 할당
- 반환 전 해당 저장소 해제
x86-64 프로시저 구현 특징
- 특별한 명령어와 관례 조합: 기계 자원(레지스터, 프로그램 메모리) 사용 방식
- 최소주의 전략: 각 특정 프로시저에 필요한 메커니즘만 구현
- 오버헤드 최소화: 프로시저 호출 비용을 최소화하기 위한 노력
3.7.1 런타임 스택 (The Run-Time Stack)
스택의 기본 특성
C와 대부분의 다른 언어의 프로시저 호출 메커니즘의 핵심 특징은 후입선출(LIFO) 메모리 관리 원칙을 사용하는 스택 데이터 구조를 활용할 수 있다는 것입니다.
스택 동작 원리
- 프로시저 호출 시: P가 Q를 호출하면 Q가 실행되는 동안 P는 일시 중단
- 실행 중: Q만이 새로운 저장소 할당이나 다른 프로시저 호출 설정 능력 필요
- 반환 시: Q가 반환하면 할당된 모든 지역 저장소 해제 가능
x86-64 스택 구조
스택의 물리적 특성
- 성장 방향: 낮은 주소 방향으로 성장
- 스택 포인터:
%rsp가 스택 최상위 요소를 가리킴 - 데이터 조작:
pushq와popq명령어 사용
스택 프레임 구조
Figure 3.25: 일반적인 스택 프레임 구조
스택 프레임의 구성 요소
1. 현재 실행 프로시저 프레임
- 항상 스택의 최상위에 위치
- 가변 크기 가능 (3.10.5절에서 다룸)
2. 반환 주소 (Return Address)
- P의 스택 프레임의 일부로 간주
- P와 관련된 상태 정보 포함
3. 인수 전달 (Argument Passing)
- 최대 6개의 정수 값(포인터 및 정수)까지 레지스터로 전달
- 더 많은 인수가 필요한 경우 스택에 저장
4. 최적화
- 공간 및 시간 효율성: 필요한 스택 프레임 부분만 할당
- 리프 프로시저: 모든 지역 변수가 레지스터에 저장되고 다른 함수를 호출하지 않는 함수는 스택 프레임이 필요하지 않음
3.7.2 제어 전달 (Control Transfer)
기본 메커니즘
함수 P에서 함수 Q로 제어를 전달하는 것은 단순히 프로그램 카운터(PC)를 Q의 코드 시작 주소로 설정하는 것입니다. 그러나 Q가 나중에 반환할 때, 프로세서는 P의 실행을 재개해야 할 코드 위치에 대한 기록이 있어야 합니다.
call과 ret 명령어
call 명령어
| 명령어 | 설명 |
|---|---|
call Label | 프로시저 호출 (직접) |
call *Operand | 프로시저 호출 (간접) |
동작 과정:
1. 반환 주소 A를 스택에 푸시
2. PC를 Q의 시작 주소로 설정
3. 반환 주소 A = 호출 명령어 바로 다음 명령어의 주소
ret 명령어
| 명령어 | 설명 |
|---|---|
ret | 호출에서 반환 |
동작 과정:
1. 스택에서 주소 A를 팝
2. PC를 A로 설정
실행 예제
코드 구조
# multstore 함수 시작
0000000000400540 <multstore>:
400540: 53 push %rbx
400541: 48 89 d3 mov %rdx,%rbx
...
40054d: c3 retq
# main에서 multstore 호출
400563: e8 d8 ff ff ff callq 400540 <multstore>
400568: 48 8b 54 24 08 mov 0x8(%rsp),%rdx실행 단계
1. 호출 전 (Figure 3.26a)
%rip = 0x400563(call 명령어 위치)%rsp = 0x7fffffffe840
-
호출 후 (Figure 3.26b)
%rip = 0x400540(multstore 시작)%rsp = 0x7fffffffe838(스택에 반환 주소 푸시)- 스택 최상위:
0x400568(반환 주소)
-
반환 후 (Figure 3.26c)
%rip = 0x400568(main의 다음 명령어)%rsp = 0x7fffffffe840(원래 상태 복원)
상세 실행 추적 예제
함수 정의
long leaf(long y) { return y+2; }
long top(long x) { return 2 * leaf(x-5); }어셈블리 코드
# leaf 함수
L1: 400540: lea 0x2(%rdi),%rax # z+2
L2: 400544: retq # Return
# top 함수
T1: 400545: sub $0x5,%rdi # x-5
T2: 400549: callq 400540 <leaf> # Call leaf(x-5)
T3: 40054e: add %rax,%rax # Double result
T4: 400551: retq # Return
# main에서 호출
M1: 40055b: callq 400545 <top> # Call top(100)
M2: 400560: mov %rax,%rdx # Resume실행 추적 표
| 라벨 | PC | 명령어 | %rdi | %rax | %rsp | *%rsp | 설명 |
|---|---|---|---|---|---|---|---|
| M1 | 0x40055b | callq | 100 | — | 0x7fffffffe820 | — | Call top(100) |
| T1 | 0x400545 | sub | 100 | — | 0x7fffffffe818 | 0x400560 | Entry of top |
| T2 | 0x400549 | callq | 95 | — | 0x7fffffffe818 | 0x400560 | Call leaf(95) |
| L1 | 0x400540 | lea | 95 | — | 0x7fffffffe810 | 0x40054e | Entry of leaf |
| L2 | 0x400544 | retq | — | 97 | 0x7fffffffe810 | 0x40054e | Return 97 from leaf |
| T3 | 0x40054e | add | — | 97 | 0x7fffffffe818 | 0x400560 | Resume top |
| T4 | 0x400551 | retq | — | 194 | 0x7fffffffe818 | 0x400560 | Return 194 from top |
| M2 | 0x400560 | mov | — | 194 | 0x7fffffffe820 | — | Resume main |
Figure 3.27: 프로시저 호출 및 반환을 포함한 프로그램의 상세 실행
실행 과정 상세 분석
첫 번째 호출 (M1 → T1):
- main에서
callq실행으로 top(100) 호출 - 반환 주소 0x400560이 스택에 푸시됨
- 스택 포인터가 0x7fffffffe818로 감소
두 번째 호출 (T2 → L1):
- top에서
callq실행으로 leaf(95) 호출 - 반환 주소 0x40054e가 스택에 푸시됨
- 스택 포인터가 0x7fffffffe810으로 감소
첫 번째 반환 (L2 → T3):
- leaf의
retq실행으로 반환값 97과 함께 top으로 복귀 - 스택에서 0x40054e를 팝하여 PC에 설정
- 스택 포인터가 0x7fffffffe818로 복원
두 번째 반환 (T4 → M2):
- top의
retq실행으로 반환값 194와 함께 main으로 복귀 - 스택에서 0x400560을 팝하여 PC에 설정
- 스택 포인터가 0x7fffffffe820으로 완전 복원
스택 상태 변화 시각화
핵심 원리
반환 주소를 스택에 푸시하는 간단한 메커니즘으로 함수가 나중에 프로그램의 적절한 지점으로 반환할 수 있게 됩니다. C의 표준 call/return 메커니즘은 스택이 제공하는 후입선출 메모리 관리 원칙과 편리하게 일치합니다.
중요한 관찰사항
- 스택의 LIFO 특성: 가장 최근에 푸시된 반환 주소가 가장 먼저 팝됨
- 자동 상태 복원: 각 함수 반환 시 스택 포인터가 자동으로 이전 상태로 복원됨
- 중첩 호출 지원: 임의의 깊이로 함수 호출 중첩 가능
- 레지스터 보존: %rax는 반환값 전달에 사용됨
3.7.3 데이터 전달 (Data Transfer)
기본 개념
프로시저 호출 시 제어 전달 외에도 다음이 필요합니다:
- 인수로 데이터 전달: 호출 시
- 값 반환: 프로시저 반환 시
x86-64에서는 대부분의 데이터 전달이 레지스터를 통해 이루어집니다.
레지스터를 통한 인수 전달
인수 전달 레지스터 순서
| 피연산자 크기 (비트) | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 64 | %rdi | %rsi | %rdx | %rcx | %r8 | %r9 |
| 32 | %edi | %esi | %edx | %ecx | %r8d | %r9d |
| 16 | %di | %si | %dx | %cx | %r8w | %r9w |
| 8 | %dil | %sil | %dl | %cl | %r8b | %r9b |
Figure 3.28: 함수 인수 전달용 레지스터
인수 전달 규칙
- 최대 6개 정수 인수: 레지스터로 전달
- 인수 크기: 64비트 미만인 경우 적절한 레지스터 하위 부분 사용
- 인수 순서: 인수 목록의 순서에 따라 레지스터 할당
- 반환값: 함수는 레지스터
%rax로 값을 반환
스택을 통한 인수 전달
6개 초과 인수의 경우
프로시저 P가 n > 6개의 정수 인수로 프로시저 Q를 호출하는 경우:
- 인수 1-6: 적절한 레지스터에 복사
- 인수 7-n: 스택에 배치 (인수 7이 스택 최상위)
- 데이터 크기 정렬: 모든 데이터 크기를 8의 배수로 반올림
- 스택 프레임 할당: P는 인수 7-n을 위한 충분한 저장 공간 할당
인수 전달 예제
C 함수 정의 (Figure 3.29a)
void proc(long a1, long *a1p, int a2, int *a2p,
short a3, short *a3p, char a4, char *a4p)어셈블리 코드 (Figure 3.29b)
void proc(long a1, long *a1p, int a2, int *a2p,
short a3, short *a3p, char a4, char *a4p)
// a1 in %rdi (인수 1)
// a1p in %rsi (인수 2)
// a2 in %edx (인수 3)
// a2p in %rcx (인수 4)
// a3 in %r8w (인수 5)
// a3p in %r9 (인수 6)
// a4 at %rsp+8 (인수 7)
// a4p at %rsp+16 (인수 8)1 proc:
2 movq 16(%rsp), %rax # a4p에서 가져오기
3 addq %rdi, (%rsi) # *a1p += a1
4 addl %edx, (%rcx) # *a2p += a2
5 addw %r8w, (%r9) # *a3p += a3
6 movl 8(%rsp), %edx # a4 가져오기
7 addb %dl, (%rax) # *a4p += a4
8 ret스택 상태 다이어그램 (Figure 3.30)
명령어 크기별 처리
addq: a1 (long) - 8바이트addl: a2 (int) - 4바이트addw: a3 (short) - 2바이트addb: a4 (char) - 1바이트
주목할 점: movl 명령어(6번째 줄)는 메모리에서 4바이트를 읽지만, 다음 addb 명령어는 하위 바이트만 사용합니다.
3.7.4 스택의 지역 저장소 (Local Storage on the Stack)
지역 데이터가 메모리에 저장되는 경우
지금까지 본 대부분의 프로시저 예제는 레지스터에 저장할 수 있는 것 이상의 지역 저장소가 필요하지 않았습니다. 그러나 지역 데이터를 메모리에 저장해야 하는 경우가 있습니다:
1. 레지스터 부족
모든 지역 데이터를 담기에 레지스터가 충분하지 않은 경우
2. 주소 연산자 사용 ('&')
지역 변수에 주소 연산자가 적용되어 해당 주소를 생성해야 하는 경우
3. 배열이나 구조체
일부 지역 변수가 배열이나 구조체이므로 배열 또는 구조체 참조로 접근해야 하는 경우
스택 프레임 할당
일반적인 할당 방법: 스택 포인터를 감소시켜 스택 프레임에 공간 할당
주소 연산자 처리 예제 (Figure 3.31)
(a) C 코드
long swap_add(long *xp, long *yp)
{
long x = *xp;
long y = *yp;
*xp = y;
*yp = x;
return x + y;
}
long caller()
{
long arg1 = 534;
long arg2 = 1057;
long sum = swap_add(&arg1, &arg2);
long diff = arg1 - arg2;
return sum * diff;
}(b) caller 함수의 어셈블리 코드
long caller()1 caller:
2 subq $16, %rsp # 스택 프레임에 16바이트 할당
3 movq $534, (%rsp) # arg1에 534 저장
4 movq $1057, 8(%rsp) # arg2에 1057 저장
5 leaq 8(%rsp), %rsi # &arg2를 두 번째 인수로 계산
6 movq %rsp, %rdi # &arg1을 첫 번째 인수로 계산
7 call swap_add # swap_add(&arg1, &arg2) 호출
8 movq (%rsp), %rdx # arg1 가져오기
9 subq 8(%rsp), %rdx # diff = arg1 - arg2 계산
10 imulq %rdx, %rax # sum * diff 계산
11 addq $16, %rsp # 스택 프레임 해제
12 ret # 반환메모리 할당 분석
S = 스택 포인터 값이라고 하면:
- &arg2 = S + 8 (5번째 줄)
- &arg1 = S (6번째 줄)
따라서 지역 변수들의 스택 프레임 내 위치:
- arg1: 스택 포인터 기준 오프셋 0
- arg2: 스택 포인터 기준 오프셋 8
복잡한 스택 사용 예제 (Figure 3.32)
(a) call_proc 함수 C 코드
long call_proc()
{
long x1 = 1; int x2 = 2;
short x3 = 3; char x4 = 4;
proc(x1, &x1, x2, &x2, x3, &x3, x4, &x4);
return (x1+x2)*(x3-x4);
}(b) 생성된 어셈블리 코드
long call_proc()# proc에 대한 인수 설정
1 call_proc:
2 subq $32, %rsp # 32바이트 스택 프레임 할당
3 movq $1, 24(%rsp) # x1에 1 저장
4 movl $2, 20(%rsp) # x2에 2 저장
5 movw $3, 18(%rsp) # x3에 3 저장
6 movb $4, 17(%rsp) # x4에 4 저장
7 leaq 17(%rsp), %rax # &x4 생성
8 movq %rax, 8(%rsp) # &x4를 인수 8로 저장
9 movl $4, (%rsp) # 4를 인수 7로 저장
10 leaq 18(%rsp), %r9 # &x3를 인수 6으로 전달
11 movl $3, %r8d # 3을 인수 5로 전달
12 leaq 20(%rsp), %rcx # &x2를 인수 4로 전달
13 movl $2, %edx # 2를 인수 3으로 전달
14 leaq 24(%rsp), %rsi # &x1을 인수 2로 전달
15 movl $1, %edi # 1을 인수 1로 전달
# proc 호출
16 call proc
# 메모리 변경사항 검색
17 movslq 20(%rsp), %rdx # x2를 가져와서 long으로 변환
18 addq 24(%rsp), %rdx # x1+x2 계산
19 movswl 18(%rsp), %eax # x3를 가져와서 int로 변환
20 movsbl 17(%rsp), %ecx # x4를 가져와서 int로 변환
21 subl %ecx, %eax # x3-x4 계산
22 cltq # long으로 변환
23 imulq %rdx, %rax # (x1+x2) * (x3-x4) 계산
24 addq $32, %rsp # 스택 프레임 해제
25 ret # 반환call_proc 스택 프레임 구조 (Figure 3.33)
지역 변수 위치 (스택 포인터 기준 오프셋)
- x1: 바이트 24-31 (8바이트)
- x2: 바이트 20-23 (4바이트)
- x3: 바이트 18-19 (2바이트)
- x4: 바이트 17 (1바이트)
스택 인수 위치
- 인수 7 (값 4): 오프셋 0
- 인수 8 (&x4의 포인터): 오프셋 8
함수 실행 과정
- 설정 단계 (2-15번째 줄): 스택 프레임과 함수 매개변수 설정
- 호출 단계 (16번째 줄): proc 함수 호출
- 결과 처리 (17-23번째 줄): 4개 지역 변수 값 검색 후 최종 계산
- 정리 단계 (24-25번째 줄): 스택 프레임 해제 후 반환
3.7.5 레지스터의 지역 저장소 (Local Storage in Registers)
레지스터 사용 규칙의 필요성
프로그램 레지스터 세트는 모든 프로시저가 공유하는 단일 자원입니다. 한 번에 하나의 프로시저만 활성화되지만, 한 프로시저(호출자)가 다른 프로시저(피호출자)를 호출할 때 피호출자가 호출자가 나중에 사용할 예정인 레지스터 값을 덮어쓰지 않도록 해야 합니다.
레지스터 분류
1. Callee-Saved 레지스터 (피호출자 저장)
해당 레지스터: %rbx, %rbp, %r12–%r15
규칙:
- 프로시저 Q는 이러한 레지스터의 값을 보존해야 함
- Q가 P로 반환할 때 Q가 호출되었을 때와 동일한 값을 가져야 함
보존 방법:
1. 변경하지 않기: 전혀 변경하지 않음
2. 저장 후 복원: 원래 값을 스택에 푸시 → 변경 → 반환 전 이전 값을 팝
2. Caller-Saved 레지스터 (호출자 저장)
해당 레지스터: 스택 포인터 %rsp를 제외한 모든 다른 레지스터
규칙:
- 모든 함수에 의해 수정될 수 있음
- 호출자 P가 이런 레지스터에 지역 데이터를 가지고 있다면 Q를 호출하기 전에 먼저 데이터를 저장해야 함
Callee-Saved 레지스터 사용 예제 (Figure 3.34)
(a) 호출 함수
long P(long x, long y)
{
long u = Q(y);
long v = Q(x);
return u + v;
}(b) 호출 함수의 어셈블리 코드
long P(long x, long y)
// x in %rdi, y in %rsi1 P:
2 pushq %rbp # %rbp 저장
3 pushq %rbx # %rbx 저장
4 subq $8, %rsp # 스택 프레임 정렬
5 movq %rdi, %rbp # x 저장
6 movq %rsi, %rdi # y를 첫 번째 인수로 이동
7 call Q # Q(y) 호출
8 movq %rax, %rbx # 결과 저장
9 movq %rbp, %rdi # x를 첫 번째 인수로 이동
10 call Q # Q(x) 호출
11 addq %rbx, %rax # 저장된 Q(y)를 Q(x)에 더하기
12 addq $8, %rsp # 스택의 마지막 부분 해제
13 popq %rbx # %rbx 복원
14 popq %rbp # %rbp 복원
15 ret실행 과정 분석
-
레지스터 저장 (2-3번째 줄):
- 두 callee-saved 레지스터의 값을 스택에 저장
-
값 보존:
- %rbp: x 값 보존 (첫 번째 Q 호출 동안)
- %rbx: Q(y)의 계산 결과 보존 (두 번째 Q 호출 동안)
-
레지스터 복원 (13-14번째 줄):
- 스택에서 두 callee-saved 레지스터 복원
- 주의: 푸시한 순서의 역순으로 팝 (LIFO 원칙)
핵심 원리
- 안전한 저장: P는 callee-saved 레지스터에 값을 안전하게 저장할 수 있음 (스택에 이전 값을 저장한 후)
- 투명성: Q 호출 후에도 레지스터 값이 변경되지 않음을 보장
- 효율성: caller-saved 레지스터를 사용하는 것보다 호출자의 부담 감소
3.7.6 재귀 프로시저 (Recursive Procedures)
재귀 지원 메커니즘
레지스터와 스택 사용에 대해 설명한 규칙들은 x86-64 프로시저가 자기 자신을 재귀적으로 호출할 수 있게 합니다.
재귀 지원의 핵심 원리
- 프라이빗 공간: 각 프로시저 호출은 스택에서 자체 프라이빗 공간을 가짐
- 간섭 방지: 여러 미완료 호출의 지역 변수들이 서로 간섭하지 않음
- 자동 할당/해제: 스택 원칙이 프로시저 호출 시 지역 저장소 할당과 반환 전 해제를 자연스럽게 제공
재귀 팩토리얼 예제 (Figure 3.35)
(a) C 코드
long rfact(long n)
{
long result;
if (n <= 1)
result = 1;
else
result = n * rfact(n-1);
return result;
}(b) 생성된 어셈블리 코드
long rfact(long n)
// n in %rdi1 rfact:
2 pushq %rbx # %rbx 저장
3 movq %rdi, %rbx # n을 callee-saved 레지스터에 저장
4 movl $1, %eax # 반환값 = 1로 설정
5 cmpq $1, %rdi # n:1 비교
6 jle .L35 # <=이면 done으로 이동
7 leaq -1(%rdi), %rdi # n-1 계산
8 call rfact # rfact(n-1) 호출
9 imulq %rbx, %rax # 결과에 n을 곱하기
10 .L35: done:
11 popq %rbx # %rbx 복원
12 ret # 반환실행 과정 분석
- 레지스터 보존:
%rbx에 매개변수 n 저장 (기존 값은 스택에 저장) - 기저 조건: n ≤ 1이면 결과값 1 반환
- 재귀 호출: rfact(n-1) 호출
- 결과 계산: 재귀 호출 반환 후 결과와 n을 곱함
- 레지스터 복원: 반환 전 %rbx 복원
재귀 호출의 보장 사항
스택 원칙과 레지스터 저장 규칙으로 인해 재귀 호출 rfact(n-1)이 반환될 때(9번째 줄):
- 결과값: 호출 결과가 레지스터
%rax에 저장됨 - 인수값: 인수 n의 값이 레지스터
%rbx에 저장됨
재귀의 일반적 특성
함수 호출과의 동일성
재귀 함수 호출은 다른 함수 호출과 동일하게 진행됩니다.
복잡한 패턴 지원
- 상호 재귀: 프로시저 P가 Q를 호출하고, Q가 다시 P를 호출하는 경우도 지원
- 스택 원칙: 할당과 해제의 스택 원칙이 함수 호출-반환 순서와 자연스럽게 일치
메모리 관리
스택 원칙이 다음을 제공:
- 할당: 필요 시 지역 저장소 할당
- 해제: 함수 완료 시 자동 해제
- 상태 정보 저장: 각 호출의 프라이빗 저장소 (반환 위치 저장값, callee-saved 레지스터)
재귀 실행 스택 시각화
rfact(4) 호출 시 스택 상태:
┌─────────────────┐ ← 높은 주소
│ main의 데이터 │
├─────────────────┤
│ rfact(4) frame │ ← n=4, %rbx 저장됨
├─────────────────┤
│ rfact(3) frame │ ← n=3, %rbx 저장됨
├─────────────────┤
│ rfact(2) frame │ ← n=2, %rbx 저장됨
├─────────────────┤
│ rfact(1) frame │ ← n=1, %rbx 저장됨
└─────────────────┘ ← %rsp (낮은 주소)각 재귀 호출이 자체 스택 프레임을 가져 독립적인 n 값과 %rbx 저장값을 유지합니다.
