Procedures
여기서는 함수, 메서드 등을 프로시저(Procedure)라고 통칭하겠다. 프로시저 호출은 제어 전송, 데이터 전송, 지역 데이터 관리와 같이 3단계로 세분화할 수 있다. 각 단계는 필요한 경우에만 수행되어, 프로시저 호출의 오버헤드를 최소화한다.
Stack Structure
스택은 메모리의 한 영역으로, 호출된 프로시저가 정보를 저장하는 데 사용된다. 프로시저의 호출 순서에 따라 후입 선출(Last In First Out, LIFO) 방식으로 메모리 공간을 할당한다.
x86-64 Stack
- 스택 상단(top)의 주소를 저장하는 레지스터(
%rsp)를 가지고 있으며, 이를 스택 포인터(Stack pointer)라 한다. - 높은 주소에서 시작하여 주소가 낮아지는 방향으로 공간을 할당한다.
x86-64 Stack: Push
pushq Source 명령은 스택 포인터를 8만큼 감소시킨 뒤, 해당 주소에 Source의 값을 저장한다.
Source는 레지스터 또는 상수(immediate)이다.
x86-64 Stack: Pop
popq Dest 명령은 스택 포인터가 가리키는 주소에서 데이터를 읽어 Dest에 저장한 뒤, 스택 포인터를 8만큼 증가시킨다.
pop된 데이터는 여전히 메모리에 남아 있지만, 더이상 스택의 일부로 간주되지 않으므로 할당 해제(deallocate)된 것으로 본다.
Passing Control
1
2
3
4
5
6
7
8
9
| long mult2(long a, long b) {
long s = a * b;
return s;
}
void mulstore(long x, long y, long *dest) {
long t = mult2(x, y);
*dest = t;
}
|
1
2
3
4
5
6
7
8
9
10
| 0000000000001131 <mult2>:
1131: 48 89 f8 mov %rdi,%rax
⋮
1138: c3 ret
0000000000001139 <mulstore>:
⋮
113d: e8 e7 ff ff ff call 1131 <mult2>
1142: 48 89 03 mov %rax,(%rbx)
⋮
|
%rip | %rsp | stack |
|---|
0x113d | 0x120 | { ⋯ } |
0x1131 | 0x118 | { ⋯, 0x1142 } |
| | ⋮ | |
0x1138 | 0x118 | { ⋯, 0x1142 } |
0x1142 | 0x120 | { ⋯ } |
%rip는 다음에 실행될 명령어의 주소를 저장하는 레지스터로, 명령어 포인터(Instruction pointer)라 한다.
스택 상단의 주소가 0x120이라고 가정해 보자. 명령어 포인터는 0x113d를 가리키고 있으며, 이는 call 명령어이다. call 명령어는 다음 작업을 수행한다.
- 반환 주소
0x1142를 스택에 push한다. - 명령어 포인터는
call의 대상인 0x1131로 설정된다. mult2의 명령어들을 실행하다가 ret을 만나면, 스택에서 반환 주소 0x1142를 pop하여 명령어 포인터로 설정한다.
Passing Data
앞서 살펴본 어셈블리 코드 예시들에서 특정 레지스터들이 반복적으로 사용되는 것을 보았을 텐데, 이는 ABI(Application Binary Interface)에 따른 것이다.
- 함수 인자는 6개까지 순서대로
%rdi, %rsi, %rdx, %rcx, %r8, %r9에 저장된다. - 그 이후의 인자는 스택에 저장된다.
- 반환값은
%rax에 저장된다.
이는 모두 정수 및 포인터 값에 대한 규칙이며, 부동 소수점에 대해서는 별도의 레지스터 세트가 사용된다.
IA-32 시절에는 모든 인자가 스택에 저장되었으나, 지금은 대부분 레지스터에 저장된다. 레지스터 접근이 메모리 접근보다 훨씬 빠르기 때문이다.
Managing Local Data
Stack Frames
프로시저 호출 시 할당되는 각 영역을 스택 프레임(Stack frame)이라 한다. 스택은 호출된 뒤 아직 반환되지 않은 모든 프로시저에 대한 프레임을 유지한다.
프로시저 호출 전의 스택 포인터 값을 %rbp에 저장하며, 이를 프레임 포인터(Frame pointer)라 한다. 프로시저 반환 시 스택 포인터는 프레임 포인터의 값으로 복원된다.
프레임 포인터는 선택적으로 사용되며, %rbp는 프레임 포인터로 사용되지 않는 경우 일반 레지스터로 사용된다.
x86-64/Linux Stack Frame
| | Content |
|---|
| / | ⋮ |
| 호출자 프레임 | 7번째 이후의 인자 |
| \ | 반환 주소 |
프레임 포인터 %rbp → | 이전 %rbp |
| | 레지스터 + 지역 변수 |
스택 포인터 %rsp → | 6번째까지의 인자 |
스택 프레임은 스택 포인터(상단)와 프레임 포인터(하단)로 구분되며, 그 크기는 대부분 컴파일 타임에 결정된다. 동적 할당으로 인해 컴파일 타임에 결정되지 않는 경우에는 프레임 포인터를 통해 각 스택 프레임을 구분할 수 있다.
Example: incr()
1
2
3
4
5
6
| long incr(long *p, long val) {
long x = *p;
long y = x + val;
*p = y;
return x;
}
|
1
2
3
4
5
| incr:
movq (%rdi), %rax ; x = *p
addq %rax, %rsi ; val += x
movq %rsi, (%rdi) ; *p = val
ret
|
| Register | Use |
|---|
%rdi | p |
%rsi | val |
%rax | 반환값(x) |
Example: Calling incr()
1
2
3
4
5
| long call_incr() {
long v1 = 15213;
long v2 = incr(&v1, 3000);
return v1 + v2;
}
|
1
2
3
4
5
6
7
8
9
| call_incr:
subq $16, %rsp
movq $15213, 8(%rsp)
movl $3000, %esi
leaq 8(%rsp), %rdi
call incr
addq 8(%rsp), %rax
addq $16, %rsp
ret
|
| Register | Use |
|---|
%rdi | &v1 |
%rsi | 3000 |
| Line | Assembly | Stack |
|---|
| 1 | | { ⋯, return address } |
| 2 | subq $16, %rsp | { ⋯, return address, unused, unused } |
| 3 | movq $15213, 8(%rsp) | { ⋯, return address, 15213, unused } |
| 4 | movl $3000, %esi | { ⋯, return address, 15213, unused } |
| 5 | leaq 8(%rsp), %rdi | { ⋯, return address, 15213, unused } |
| 6 | call incr | { ⋯, return address, 18213, unused } |
| 7 | addq 8(%rsp), %rax | { ⋯, return address, 18213, unused } |
| 8 | addq $16, %rsp | { ⋯, return address } |
| 9 | ret | { ⋯ } |
call_incr()이 호출될 때 스택에 반환 주소가 push된다.- 스택에 16바이트의 공간을 할당한다. 필요한 것보다 많은 공간을 할당한 것은 주소를 특정한 방식으로 정렬하기 위함이다.
%rsp + 8이 가리키는 주소에 15213을 저장한다.Dest가 %eX 레지스터인 명령어는 해당 레지스터의 상위 32비트를 0으로 채운다. 따라서 movl은 3000을 %rsi에 복사하고 상위 바이트를 0으로 채운다. 컴파일러가 이러한 방식을 선호하는 이유는 movl을 인코딩하는 것이 movq보다 1바이트를 덜 사용하기 때문이다.%rsp + 8이 가리키는 주소를 %rdi에 복사한다.call이 호출한 incr()에서 %rax에 15213을, %rdi가 가리키는 주소에 18213을 저장한다.%rsp + 8이 가리키는 주소에 저장된 값을 %rax에 더한다. (18213 + 15213)- 스택에서 16바이트의 공간을 할당 해제한다.
- 스택에서 반환 주소를
pop한다.
Register Saving Conventions
| Convention | Description |
|---|
| Caller-saved | 호출자(caller)가 레지스터의 값을 저장해 두었다가,
피호출자(callee)로부터 제어가 반환될 때 값을 복원한다. |
| Callee-saved | 피호출자가 레지스터의 원래 값을 스택에 저장해 두었다가, 반환 전에 값을 복원한다. |
x86-64 Linux Register Usage
| Convention | Register | Special Use |
|---|
| Caller-saved | %rax | 반환값 |
| | %rdi | 인자 1 |
| | %rsi | 인자 2 |
| | %rdx | 인자 3 |
| | %rcx | 인자 4 |
| | %r8 | 인자 5 |
| | %r9 | 인자 6 |
| | %r10 | - |
| | %r11 | - |
| Callee-saved | %rbx | - |
| | %r12 | - |
| | %r13 | - |
| | %r14 | - |
| | %rbp | 프레임 포인터 (선택적) |
| | %rsp | 스택 포인터 |
Callee-Saved Example
1
2
3
4
5
| long call_incr2(long x) {
long v1 = 15213;
long v2 = incr(&v1, 3000);
return x + v2;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
| call_incr2:
pushq %rbx
subq $16, %rsp
movq %rdi, %rbx
movq $15213, 8(%rsp)
movl $3000, %esi
leaq 8(%rsp), %rdi
call incr
addq %rbx, %rax
addq $16, %rsp
popq %rbx
ret
|
| Line | Assembly | Stack |
|---|
| 1 | | { ⋯, return address } |
| 2 | pushq %rbx | { ⋯, return address, saved %rbx } |
| 3 | subq $16, %rsp | { ⋯, return address, saved %rbx, unused, unused } |
| 4 | movq %rdi, %rbx | { ⋯, return address, saved %rbx, unused, unused } |
| | ⋮ | |
| 9 | addq %rbx, %rax | { ⋯, return address, saved %rbx, 18213, unused } |
| 10 | addq $16, %rsp | { ⋯, return address, saved %rbx } |
| 11 | popq %rbx | { ⋯, return address } |
| 12 | ret | { ⋯ } |
Callee-saved 레지스터인 %rbx에 주목해 보자.
%rbx의 원래 값을 스택에 push한다.incr()에 인자를 전달하기 위해 %rdi에 새로운 값을 저장해야 하므로, %rdi의 원래 값(x)을 %rbx에 복사한다.%rbx의 값(x)을 %rax에 더한다.%rbx의 원래 값을 복원한다.
Illustration of Recursion
1
2
3
4
5
6
| long popcount_r(unsigned long x) {
if (x == 0)
return 0;
else
return (x & 1) + popcount_r(x >> 1);
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| popcount_r:
movl $0, %eax
testq %rdi, %rdi
je .L6
pushq %rbx
movq %rdi, %rbx
andl $1, %ebx
shrq %rdi
call popcount_r
addq %rbx, %rax
popq %rbx
.L6:
rep; ret
|
| Line | Assembly | %rdi | %rbx | stack |
|---|
| 1 | | x | b | { ⋯, ret1 } |
| 2 | movl $0, %eax | x | b | { ⋯, ret1 } |
| | ⋮ | | | |
| 5 | movq %rdi, %rbx | x | x | { ⋯, ret1, b } |
| 6 | andl $1, %ebx | x | x & 1 | { ⋯, ret1, b } |
| 7 | shrq %rdi | x >> 1 | x & 1 | { ⋯, ret1, b } |
| 8 | call popcount_r | x >> 1 | x & 1 | { ⋯, ret1, b, ret2 } |
| | ⋮ | | | |
| 8-5 | movq %rdi, %rbx | x >> 1 | x >> 1 | { ⋯, ret1, b, ret2, x & 1 } |
| 8-6 | andl $1, %ebx | x >> 1 | (x >> 1) & 1 | { ⋯, ret1, b, ret2, x & 1 } |
| 8-7 | shrq %rdi | x >> 2 | (x >> 1) & 1 | { ⋯, ret1, b, ret2, x & 1 } |
| | ⋮ | | | |
| 8-10 | popq %rbx | x >> w | x & 1 | { ⋯, ret1, b, ret2 } |
| 8-11 | rep; ret | x >> w | x & 1 | { ⋯, ret1, b} |
| 9 | addq %rbx, %rax | x >> w | x & 1 | { ⋯, ret1, b} |
| 10 | popq %rbx | x >> w | b | { ⋯, ret1} |
| 11 | rep; ret | x >> w | b | { ⋯ } |
References