3.7 프로시저 ✅
프로시저는 소프트웨어에서 주요 추상화이다. 함수, 메서드, 서브루틴, 핸들러 등은 프로시저의 일반적인 특징을 따른다. 프로시저는 다음과 같은 메커니즘을 따른다.
- 제어 전달 : 프로그램 카운터는 프로시저의 시작점으로 주소를 설정한다. 이후 프로시저를 수행하고 호출자로 제어를 반환한다.
- 데이터 전달 : 호출자는 프로시저에 파라미터를 전달하고, 프로시저는 호출자에 리턴값을 반환한다.
- 메모리의 할당과 해제 : 프로시저 시작 시 지역 변수를 위한 공간 할당하고 리턴 이전에 공간을 해제한다.
예를 들어 프로시저 P가 프로시저 Q를 호출했다면, Q가 실행된 이후 P를 다시 반환된다.
- 제어 전달 : PC는 Q의 코드의 시작 주소로 설정되고 Q를 호출한 후에 P의 명령어로 설정한다.
- 데이터 전달 : P는 하나 이상의 파라미터를 Q에게 제공하고, Q는 P에게 값을 다시 반환한다.
- 메모리 할당과 해제 : Q는 지역 변수에 대한 공간을 할당할 필요가 있다.
3.7.1 런타임 스택
프로시저 호출 매커니즘의 핵심은 스택 자료구조를 활용한 후입선출(LIFO) 메모리 관리 원칙이다. 3.4.4에서 다뤘던 것처럼, x86-64의 스택은 작은 주소 방향으로 성장하며, 스택 포인터는 스택의 최상위 원소를 가리킨다.
일반적인 스택 프레임 구조: 스택을 프로시저의 인자를 전달하고, 리턴 정보를 저장하며, 레지스터를 저장하고, 지역 저장공간의 목적으로 사용된다. 필요하지 않은 경우 일부분은 생략될 수 있다.
위의 그림은 일반적인 스택 프레임 구조를 나타낸다. x86-64 프로시저가 레지스터에 저장할 수 있는 개수 이상의 저장공간을 필요로 할 때는 공간을 스택에 할당하는데, 이 스택 영역을 프로시저의 스택 프레임이라고 부른다.
주목할 점은 프로시저 P가 Q를 호출하면서 Return address를 스택에 push해서 Q가 리턴할 때 P에서 프로그램이 재시작해야 하는 위치를 가리켜 준다는 것. 프로시저 Q가 호출되면 스택 경계를 확장해서 자신을 위한 공간을 할당한다. 그리고 이 공간 내에서 레지스터 값들을 저장하고, 지역변수를 위한 공간을 할당하며, 자신이 호출하는 프로시저들을 위한 인자들을 설정할 수 있다.
3.7.2 제어의 이동
함수 P에서 Q로 제어 전송을 하는 것은 PC에 Q 코드에 대한 시작 주소로 설정하면 된다. 나중에 Q가 반환할 시간이 오면, 프로세서는 P의 실행을 다시 재개해야 하는 위치를 기록해야 한다. 이 정보는 Q를 호출하는 명령어와 함께 프로시저 Q를 부르면서 x86-64 기계에 저장된다.
이 명령어는 스택에 주소 A를 푸시하고, PC를 Q의 시작 주소로 설정한다. 푸시된 주소는 반환 주소로 부르며 call 명령어로 명령어의 주소로써 계산된다.
제어를 함수 P에서 Q로 넘긴다는 것은 단순히 프로그램 카운터를 Q를 위한 코드 시작주소로 설정하는 것이면 된다. 그렇지만, 나중에 Q가 동작을 마치고 리턴해야 할 때가 오면 프로세서는 P의 실행을 다시 실행해야 하는 코드 위치의 일부 기록을 가지고 있어야 한다. 이를 담당하는 것이 call 인스트럭션이다.
- call 인스트럭션은 호출된 프로시저가 시작하는 주소를 목적지로 갖는다. jump 인스트럭션과 비슷하게 직접 호출할수도, *를 붙여 간접 호출할 수도 있다.
- ret은 프로시저 호출이 끝날 때 사용되는 인스트럭션으로, 프로시저가 호출될 때 스택에 저장해 놓았던 복귀 주소를 읽어들여, 스택 프레임을 해제하고 해당 주소로 복귀한다.
call과 ret 기능의 예제: call 인스트럭션은 함수의 시작 부분으로 제어를 이동하는 반면, ret 인스트럭션은 call 다음에 오는 인스트럭션으로 제어를 되돌린다.
Practice 3.32
두 함수 first와 last의 역어셈블링 코드가 아래와 같이 main 함수에서 first를 호출하는 코드와 함께 주어졌다.
# Disassembly of last(long u, long v)
# u in %rdi, v in %rsi
0000000000400540 <last>:
400540: 48 89 f8 mov %rdi, %rax # L1: u
400543: 48 0f af c6 imul %rsi, %rax # L2: u*v
400547: c3 retq
# Disassembly of first(long x)
# x in %rdi
0000000000400548 <first>:
400548: 48 8d 77 01 lea 0x1(%rdi), %rsi # F1: x+1
40054c: 48 83 ef 01 sub $0x1, %rdi # F2: x-1
400550: e8 eb ff ff ff callq 400540 <last> # F3: Call last(x-1, x+1)
400500: f3 c3 repz retq # F4: Return
400560: e8 e3 ff ff ff callq 400548 <first> # M1: Call first(10)
400565: 48 89 c2 mov %rax,%rdx # M2: Resumemain에 의해 first(10)을 호출하는 것으로 시작해서 이 프로그램이 main으로 다시 리턴하는 위치까지 인스트럭션 실행을 추적하는 다음의 표를 채우시오. (드래그하면 정답이 보입니다.)
| Instruction | State values (at beginning) | Description |
||||||
| Label | PC | Instruction | %rdi | %rsi | %rax | %rsp | *%rsp | |
| M1 | 0x400560 | callq | 10 | -- | -- | 0x7fffffffe820 | -- | Call first(10) |
| F1 | 0x400548 | lea | 10 | -- | -- | 0x7fffffffe818 | 0x400565 | Entry of first |
| F2 | 0x40054c | sub | 10 | 11 | -- | 0x7fffffffe818 | 0x400565 | |
| F3 | 0x400550 | callq | 9 | 11 | -- | 0x7fffffffe818 | 0x400565 | Call last(9, 11) |
| L1 | 0x400540 | mov | 9 | 11 | -- | 0x7fffffffe810 | 0x400555 | Entry of last |
| L2 | 0x400543 | imul | 9 | 11 | 9 | 0x7fffffffe810 | 0x400555 | |
| L3 | 0x400547 | retq | 9 | 11 | 99 | 0x7fffffffe810 | 0x400555 | Return 99 from last |
| F4 | 0x400555 | repz retq | 9 | 11 | 99 | 0x7fffffffe818 | 0x400555 | Return 99 from first |
| M2 | 0x400565 | mov | 9 | 11 | 99 | 0x7fffffffe820 | -- | Resume main |
함수 정의 요약
- last(long u, long v)
- 인자 u는 %rdi, v는 %rsi에 들어옴.
- 내부 동작: rax = u * v, 그 후 retq로 리턴.
- first(long x)
- 인자 x는 %rdi에 들어옴.
- 내부 동작:
- %rsi = x + 1
- %rdi = x - 1
- last(x - 1, x + 1) 호출
- 결과를 그대로 리턴
- main()
- first(10) 호출 (callq)
- 결과를 %rax에 받아 %rdx로 복사
스택과 레지스터 추적 설명
| 라벨 | 설명 |
| M1 | main()이 first(10) 호출: 현재 리턴 주소인 0x400565가 스택에 저장되고, first의 주소로 점프 |
| F1 | lea 0x1(%rdi), %rsi는 rsi = 10 + 1 = 11로 설정 |
| F2 | sub $0x1, %rdi는 rdi = 10 - 1 = 9로 설정 (이제 last(9, 11) 호출 준비 완료) |
| F3 | callq last 실행: 현재 리턴 주소 0x400555 (first의 다음 인스트럭션)이 스택에 저장되고, last로 점프 |
| L1 | mov %rdi, %rax 실행: rax = 9 |
| L2 | imul %rsi, %rax 실행: rax = 9 * 11 = 99 |
| L3 | retq: 스택에서 0x400555를 꺼내 리턴 (first로 돌아감) |
| F4 | repz retq: 리턴 주소 0x400565로 돌아감 (main 복귀) |
| M2 | main의 다음 명령 실행: mov %rax, %rdx 즉, 99를 %rdx에 저장 |
주요 개념 정리
- 함수 호출 시 스택에 리턴 주소가 저장된다. 예: callq 명령은 다음 명령 주소를 스택에 푸시한 후, 점프.
- 함수 리턴 시 retq는 스택에서 주소를 팝하여 그 위치로 점프.
- 레지스터 전파 추적은 함수 간 값 전달을 이해하는 핵심이다.
- first(x)에서 x-1과 x+1을 각각 %rdi와 %rsi로 설정하여 last를 호출
- last(u, v)는 rax = u * v 연산만 수행
결과
first(10)은 내부에서 last(9, 11)을 호출하고, 이는 99를 계산하여 리턴한다. 따라서 main()은 결국 rdx = 99가 된다.
3.7.3 데이터 전송
대부분의 데이터 전달은 레지스터를 통해 구현된다. x86-64에서는 최대 여섯 개의 정수형(즉, 정수와 포인터) 인자가 레지스터로 전달될 수 있다. 이러한 레지스터들은 전달되는 데이터 형의 길이에 따라 레지스터 이름을 이용해서 정해진 순서로 이용된다.
함수 인자 전달을 위한 레지스터들: 레지스터들은 인자 크기에 따라 이름이 붙여지며, 특정 순서로 이용된다.
- 64비트보다 작은 인자들은 64비트 레지스터의 적절한 일부분을 이용해서 접근할 수 있다. 예를 들어, 만약 첫번째 인자가 32비트라면 %edi로 접근할 수 있다.
- 함수가 여섯 개 이상의 정수형 인자를 가질 때, 다른 인자들은 스택으로 전달된다. 인자 1~6은 적절한 레지스터에 복사하고, 인자 7에서 n까지는 인자 7을 스택 탑에 넣는 방법으로 저장한다.
Practice 3.33
어떤 C함수 procprb는 네 개의 인자 u, a, v, b를 가지고 있다. 각각은 부호형 숫자 또는 부호형 숫자의 포인터이며, 숫자들은 서로 다른 길이를 가진다. 이 함수는 다음과 같은 본체를 가진다.
*u += a;
*v += b;
return sizeof(a) + sizeof(b);네 개의 매개변수의 유효한 순서와 자료형을 결정하시오. 두 개의 답이 있을 수도 있다.
procprob:
movslq %edl, %rdi
addq %rdi, (%rdx)
addb %sil, (%rcx)
movl $6, %eax
ret(정답) int procprob (int b, shor a, long *v, char *u);
(해설) 만약 첫번째 덧셈(addq)이 *u = a를 구현하고, 두번째 덧셈(addb)이 v += b를 구현한 것이라면, a가 첫번째에 더하기 전에 변환된다는 것을 알 수 있다. 이것은 a가 int 타입이어야 한다는 것과 u는 long * 유형이어야 한다는 것을 의미한다. 또한, 인자 b의 하위 바이트가 %rcx가 가리키는 바이트에 더해진다는 것을 알 수 있다. 이것은 v가 char * 타입이어야 한다는 것을 의미하지만, b의 타입은 모호하다. 이것은 1, 2, 4, 8바이트의 길이를 가질 수 있다. 이런 모호성은 a와 b의 크기의 합으로 계산된 값 6을 리턴 값에 표시해서 해소할 수 있다. 우리는 a가 4바이트 길이라는 것을 알기 때문에 b는 2여야 한다는 것을 유추할 수 있다.
# int procprobl(int a, short b, long *u, char *v)
# a in %edi, b in %si, u in %rdx, v in %rcx
procprob:
movslq %edl, %rdi # Convert a to long
addq %rdi, (%rdx) # Add to *u (long)
addb %sil, (%rcx) # Add low-order byte of b to *v
movl $6, %eax # Return 4+2
ret3.7.4 스택에서의 지역저장공간
- 지역 데이터가 메모리에 저장되어야 하는 경우가 있다.
- 지역 데이터 모두를 저장하기에는 레지스터의 수가 부족하다.
- 지역변수에 연산자 &가 사용되었으며, 이 변수의 주소를 생성할 수 있어야 한다.
- 배열 또는 구조체여서 이들이 배열이나 구조체 참조로 접근되어야 한다.
- 위 세가지의 경우에 Local variables로 명명된 스택 프레임의 일부분이 생겨난다.
- 지역변수들은 여러가지 크기를 갖는데, 이들의 위치는 스택 포인터에 대한 상대 오프셋으로 나타낼 수 있다.
위의 예제를 통해 스택 운영방식의 여러 가지 측면을 엿볼 수 있다. 이 예제는 지역변수를 위해 스택에 알맞은 공간(32byte)를 할당하고, 각 자료형에 맞게 변수를 담고, proc() 함수를 부르기 위한 준비과정을 거치는 일련의 과정을 잘 보여준다.
프로시저 proc을 실행한 후 call_proc으로 리턴될 때, 이 코드는 네 개의 지역변수 값을 가져오고 최종 계산을 수행한다. 모든 작업이 끝난 후에는 스택 프레임을 반환하기 위해 스택 포인터를 32 감소시켜 마무리한다.
3.7.5 레지스터를 이용하는 지역저장소
프로그램 레지스터들은 모든 프로시저가 공유하는 단일 자원이므로 피호출자callee는 호출자caller가 나중에 쓰려고 저장한 레지스터를 덮어써서는 안된다. 때문에 x86-64는 레지스터 사용 규약을 채택하고 있다.
- 프로그램 레지스터들은 모든 프로시저들이 공유하는 단일 자원의 역할을 한다.
- 피호출자는 호출자가 나중에 사용할 계획인 일부 레지스터 값은 덮어쓰지 않는다.
- 레지스터 %rbx, %rbp, %r12-%r15는 피호출자-저장 레지스터로 구분한다.
- 리턴하기 전에 스택에서 이전 값을 pop해오는 방식으로 레지스터를 보존한다.
- 레지스터 값들을 푸시하는 것은 Saved registers로 이름 붙인 스택 프레임의 일부분을 생성하는 효과를 갖는다.
함수 call_proc에 대한 스택 프레임: 이 스택 프레임은 함수 proc으로 전달하기 위한 두 개의 인자와 지역변수를 포함한다.
Practice 3.34
지역변수 a0-a7을 생성하는 함수 P는 인자가 없는 함수 Q를 호출한다. GCC는 P의 전반부에 대해 다음의 코드를 생성한다.
# long P(long x)
# x in %rdi
P:
pushq %r15
pushq %r14
pushq %r13
pushq %r12
pushq %rbp
pushq %rbx
subq $24, %rsp
movq %rdi, %rbx
leaq 1(%rdi), %r15
leaq 2(%rdi), %r14
leaq 3(%rdi), %r13
leaq 4(%rdi), %r12
leaq 5(%rdi), %rbp
leaq 6(%rdi), %rax
movq %rax, (%rsp)
leaq 7(%rdi), %rdx
movq %rdx, 8(%rsp)
movl $0, %eax
call Q1. 어떤 지역 값들이 피호출자-저장 레지스터에 저장되는가?
(답) 9~14번째 줄은 지역 값 a0-a5를 피호출자-저장 레지스터 %rbx, %r15, %r14, %r13, %r12, %rbp에 각각 저장한다.
2. 어떤 지역 값들이 스택에 저장되는가?
(답) 지역 값 a6과 a7은 스택 포인터 대비 오프셋 0과 8 위치에 저장된다. (16, 18번째 코드)
3. 왜 이 프로그램이 모든 지역 값들을 피호출 레지스터에 저장할 수 없었는가?
(답) 6개의 지역변수들을 저장한 후에 프로그램은 피호출자-저장 레지스터들(%rbx, %rbp, %r12-%r15)을 모두 사용하였다. 프로그램은 남은 2개의 지역 값들을 스택에 저장한다.
3.7.6 재귀 프로시저
프로시저는 자기 자신을 재귀적으로 호출하는 것을 허용한다. 각 프로시저 호출은 고유한 공간을 가지므로 서로 간섭하지 않는다. 스택의 원칙상 자연스럽게 프로시저 공간을 할당하고 해제하는 정책을 제공한다.
- 레지스터와 스택을 사용하는 것에 대해 설명한 관습으로 프로시저들이 이들을 재귀적으로 호출하는 것을 설명할 수 있다.
- 각 프로시저 콜은 스택상에 자신만의 사적인 공간을 가지며, 따라서 다수의 별도의 호출들의 지역변수들은 서로 간섭하지 않는다.
- 스택 운영방식은 프로시저가 호출될 때 지역저장소를 할당하고, 리턴하기 전에 이것을 반환하는 적절한 정책을 자연스럽게 제공한다.
- 스택 기법을 사용해서 함수의 각 호출 시에 상태정보를 위한 자신만의 개별적 저장곤간을 제공한다.
- 필요한 경우에는 지역변수를 위한 저장공간도 제공할 수 있다.
- 스택의 할당과 반환 동작은 자연스럽게 함수의 호출-리턴 순서와 일치한다.
Practice 3.35
long rfun(unsigned long x) {
if (____________)
return ;
unsigned long nx = ____________;
long rv = rfun(nx);
return ____________;
}# long rfun(unsigned long x)
# x in %rdi
rfun:
pushq %rbx
movq %rdi, %rbx
movl $0, %eax
testq %rdi, %rdi
je .L2
shrq $2, %rdi
call rfun
addq %rbx, %rax
.L2:
popq %rbx
ret1. rfun은 피호출자-저장 레지스터 %rbx에 무슨 값을 저장하는가?
(답) 레지스터 %rbx는 매개변수 x의 값을 저장하고 있엉서 이것은 결과 수식을 계산하기 위해 사용될 수 있다.
2. 위 C코드에서 빠진 수식을 채우시오.
(정답)
long rfun(unsigned long x) {
if (x == 0)
return ;
unsigned long nx = x>>2;
long rv = rfun(nx);
return x + rv;
}(해설)
long rfun(unsigned long x) {
if (x == 0) // testq + je
return 0; // movl $0, %eax + ret
unsigned long nx = x >> 2; // shrq $2, %rdi
long rv = rfun(nx); // call rfun
return x + rv; // addq %rbx, %rax
}
- 이 함수는 재귀적으로 x를 4로 나누어가며 (x >> 2), 그 값을 더해나가는 함수다.
- 즉, x + (x >> 2) + (x >> 4) + ... 이런 식으로, x가 0이 될 때까지 계속 나눠서 더해가는 재귀 누적 합 함수이다.
- 종료 조건은 x == 0, 즉 기저 조건이며, 그 외에는 오른쪽 시프트(>> 2)로 재귀를 호출해 누적합을 구한다.
3.8 배열의 할당과 접근 ✅
C에서 배열은 스칼라 데이터를 보다 큰 자료형으로 연계시키는 수단이다. C의 특이한 점은 배열 원소들에 대한 포인터를 만들고 이들 포인터간에 연산을 할 수 있다는 점이다. 이것은 기계어에서 주소 계산으로 번역된다.
3.8.1 기본 원리
- 자료형 T와 정수형 상수 N에 대해서 다음과 같은 선언에 대해 생각해보자.
T A[N]; - 시작하는 위치를 Xa로 표시하자. 이 선언은 두가지 효과를 갖는다.
- 이것은 L*N 바이트의 연속적인 공간을 메모리에 할당하며, 여기서 L(바이트 단위)은 자료형 T의 크기를 나타낸다.
- 새로운 식별자 A를 통해서 배열이 시작하는 위치의 포인터로 사용한다.
- 배열의 각 원소는 0에서 N-1 사이의 정수형 인덱스를 사용해서 접근할 수 있다.
- 배열의 원소 i는 주소 Xa +L*i에 저장된다.
메모리는 연속적인 공간에 할당되며, 배열의 각 원소는 인덱스로 구분된다.
char A[12];
char *B[8];
int C[6];
double *D[5];| Array | Element size | Total size | Start address | Element i |
| A | 1 | 12 | Xa | Xa + i |
| B | 8 | 64 | Xb | Xb + 8i |
| C | 4 | 24 | Xc | Xc + 4i |
| D | 8 | 40 | Xd | Xd + 8i |
- 배열 A는 12개의 단일 바이트(char) 원소로 구성된다.
- 배열 C는 각각 4바이트씩 필요로 하는 6개의 정수(int)로 구성된다.
- 배열 B와 D는 모두 포인터의 배열로, 배열의 원소는 각각 8바이트의 크기를 가진다.포인터 크기
- 32비트 시스템에서는 메모리 주소를 32비트(4바이트)로 표현하므로 포인터도 4바이트
- 64비트 시스템에서는 메모리 주소를 64비트(8바이트)로 표현하므로 포인터 크기 8바이트
Practice 3.36
int P[5];
short Q[2];
int **R[9];
double *S[10];
short *T[2];다음 표의 내용을 채우시오.
| Array | Element size | Total size | Start address | Element i |
| P | 4 | 20 | Xp | Xp + 4i |
| Q | 2 | 4 | Xq | Xq + 2i |
| R | 8 | 72 | Xr | Xr + 8i |
| S | 8 | 80 | Xs | Xs + 8i |
| T | 8 | 16 | Xt | Xt + 8i |
(해설) 모든 종류의 포인터는 8바이트 길이를 가진다. short는 2바이트를 필요로 하지만, int는 4바이트를 필요로 한다.
3.8.2 포인터 연산
C는 포인터 간에 연산을 허용하며, 계산된 값은 포인터가 참조하게 되는 자료형의 크기에 따라 그 값이 확대된다.
- p가 데이터 타입 T에 대한 포인터이면, p의 값은 xp이고 p + i 은 xp + L * i 값을 가진다.
- 어떤 객체를 나타내는 식 Expr에 대해 &Expr는 그 객체의 주소를 주는 포인터이다.
- 주소를 나타내는 식 AExpr에 대해 *AExpr는 그 주소에 위치한 값을 준다.
| Expression | Type | Value | Assembly code |
| E | int* | Xe | movq %rdx, %rax |
| E[0] | int | M[Xe] | movl (%rdx), %eax |
| E[i] | int | M[Xe + 4i] | movl (%rdx, %rcx, 4), %eax |
| &E[2] | int* | Xe + 8 | leaq 8(%rdx), %rax |
| E + i - 1 | int* | Xe + 4i - 4 | leaq -4(%rdx, %rcx, 4), %rax |
| *(E + i - 3) | int | M[Xe + 4i - 12] | movl -12(%rdx, %rcx, 4), %eax |
| &E[i] - E | long | i | movq %rcx, %rax |
위 표에 대한 설명은 다음과 같다.
| Expression | Explanation |
| E | E는 포인터로 배열의 시작 주소를 가리키고 %rdx에 저장된 주소를 %rax에 복사 |
| E[0] | E[0]는 배열의 첫 번째 원소를 의미하며 주소 Xe에서 값을 읽어옴 |
| E[i] | E[i]는 i번째 원소의 값으로 배열 시작 주소에 4 * i만큼 더해 접근 |
| &E[2] | &E[2]는 배열의 세 번째 원소의 주소로 시작 주소에 8을 더한 값 |
| E + i - 1 | E + i - 1는 i-1번째 원소의 주소로 시작 주소에 4 * i - 4만큼 더한 값 |
| *(E + i - 3) | *(E + i - 3)는 i-3번째 원소의 값으로 시작 주소에서 4 * i - 12만큼 떨어진 위치에서 값을 읽어옴 |
| &E[i] - E | &E[i] - E는 배열의 i번째 원소와 배열의 시작 주소 사이의 오프셋을 의미하며 이는 i와 동일 |
Practice 3.37
short integer의 배열 P가 주소 Xp와 long integer 인덱스 i가 각각 레지스터 %rdx와 %rcx에 저장되어 있다. 다음 표에 비어진 칸을 채우시오. 결과값이 short인 경우에는 %ax에, 포인터인 경우에는 %rax에 저장되어야 한다.
| Expression | Type | Value | Assembly code |
| P[1] | short | M[Xp + 2] | movw 2(%rdx),%ax |
| P + 3 + i | short * | Xp + 6 + 2i | leaq 6(%rdx,%rcx,2),%rax |
| P[i * 6 - 5] | short | M[Xp + 12i - 10] | movw -10(%rdx,%rcx,12),%ax |
| P[2] | short | M[Xp + 4] | movw 4(%rdx),%ax |
| &P[i + 2] | short * | Xp + 2i + 4 | leaq 4P%rdx,%rcx,2),%rax |
(해설) 이 문제는 정수 배열 E에 대해 보여준 문제의 변형이다. 포인터와 포인터가 가리키는 객체 사이의 차이점을 이해하는 것이 중요하다. 자료형 short는 2바이트를 필요로 하기 때문에 모든 배열의 인덱스는 2씩 곱해진다. movl을 사용하는 것보다는 앞에서와 마찬가지로 movw를 사용한다.
3.8.3 다중 배열
- 배열 할당과 참조에 관한 일반적인 원칙들은 심지어 배열의 배열을 생성할 때도 적용된다.
- 배열의 원소들은 메모리에 행 우선row major 순서로 저장된다. 이는 A[0]으로 표시하는 모든 행 0의 원소들 다음에 행1(A[1])의 원소가 따라오는 방식이다.
일반적으로 다음과 같이 선언된 배열에 대해서
T D[R][C];배열 원소 D[i][j]는 메모리 주소
&D[i][j] = Xd + L(C*i+j)에 위치한다.
Practice 3.38
다음의 소스코드에서 M, N은 #define으로 정의된 상수들이다.
long P[M][N];
long Q[N][M];
long sum_element(long i, long j) {
return P[i][j] + Q[j][i];
}# long sum_element(long i, long j)
# i in %rdi, j in %rsi
sum_element:
leaq 0(,%rdi,8), %rdx
subq %rdi, %rdx
addq %rsi, %rdx
leaq (%rsi,%rsi,4), %rax
addq %rax, %rdi
movq Q(,%rdi,8), %rax
addq P(,%rdx,8), %rax
ret역엔지니어링 기술을 사용하여 이 어셈블리 코드에서 M과 N 값을 결정하시오.
(정답) M = 5, N = 7
(해설)
# long sum_element(long i, long j)
# i in %rdi, j in %rsi
sum_element:
leaq 0(,%rdi,8), %rdx # Compute 8i
subq %rdi, %rdx # Compute 7i
addq %rsi, %rdx # Compute 7i + j
leaq (%rsi,%rsi,4), %rax # Compute 5i
addq %rax, %rdi # Compute i + 5j
movq Q(,%rdi,8), %rax # Retrieve M[Xq + 8(5j+i)]
addq P(,%rdx,8), %rax # Add M[Xp + 8(7i+j)]
ret행렬 P를 바이트 오프셋 8*(7i+j)로 참조하는 것을 알 수 있으며, 행렬 Q로의 참조는 바이트 오프셋 8*(5j+i)로 이루어진다. 이로부터 P는 7개의 열을 가지며, Q는 5개 열을 가짐을 유추할 수 있다.
3.8.4 고정크기의 배열
- C 컴파일러는 고정크기의 다차원 배열을 위한 코드에 대해 다양한 최적화를 수행할 수 있다.
- 아래의 그림은 고정길이 배열에 대한 행렬 곱셈의 원소 i, k를 계산하는 최초의 코드와 최적화된 코드이다. 컴파일러는 이런 최적화를 자동으로 실행한다.
기존의 C 코드에서 정수 인덱스 j를 제거하고, 포인터 연산만을 이용하여 빠르게 연산을 할 수 있게 코드가 최적화된 모습을 확인할 수 있다. 컴파일러는 이런 최적화를 자동으로 실행한다.
Practice 3.39
위의 그림 중 (b)의 3~5번째 줄의 C코드에서 Aptr, Bptr, Bend에 대한 초기값들의 계산이 (a)의 3~5번째 줄에 대해 생성된 어셈블리 코드에서 이들의 계산을 어떻게 정확하게 표현하는지 다음 수식을 사용해서 설명하시오.
&D[i][j] = Xd + L(C*i+j)- L=4, C=16, j=0인 경우에 대해서, 포인터 Aptr은 Xa + 4*(16i+0) = Xa + 64i로 계산된다.
- L=4, C=16, i=0, j=k인 경우에 대해서, 포인터 Bptr은 Xb + 4*(16*0+k) = Xb + 4k로 계산된다.
- L=4, C=16, i=16, j=k인 경우에 대해서, 포인터 Bend은 Xb + 4*(16*16+k) = Xb + 1024 + 4k로 계산된다.
Practice 3.40
다음 C코드는 고정크기 배열의 대각선 원소들을 val 값으로 설정한다.
// Set all diagonal elements to val
void fix_set_diag(fix_matrix A, int val) {
long i;
for (i = 0; i < N; i++) {
A[i][i] = val;
}
}-01 최적화 수준으로 컴파일하면, GCC는 다음과 같은 어셈블리 코드를 생성한다.
fix_set_diag:
# void fix_set_diag(fix_matrix A, int val)
# A in %rdi, val in %rsi
movl $0, %eax
.L13:
movl %esi, (%rdi, %rax)
addq $68, %rax
cmpq $1088, %rax
jne .L13
rep; ret어셈블리 코드에서와 유사한 최적화 기법을 사용하는 C코드 프로그램 fix_set_diag_opt를 위 그림(b)의 코드와 동일한 형태로 작성하시오. 정수형 상수보다는 매개변수 N과 관련된 식을 사용해서 N이 재정의되는 경우에도 정확히 동작할 수 있도록 하시오.
(정답)
// Set all diagonal elements to val
void fix_set_diag_opt(fix_matrix A, int val) {
int *Abase = &A[0][0];
long i = 0;
long iend = N*(N+1);
do {
Abase[i] = val;
i += (N+1);
} while (i != iend);
}(해설)
fix_set_diag:
# void fix_set_diag(fix_matrix A, int val)
# A in %rdi, val in %rsi
movl $0, %eax # Set index4 = 0
.L13:
movl %esi, (%rdi, %rax) # Set Abase[index4/4] to val
addq $68, %rax # Increment index4 += 4(N+1)
cmpq $1088, %rax # Compare index: 4N(N+1)
jne .L13 # If !=, goto loop
rep; ret # Return
전제:
- fix_matrix는 int A[N][N]과 같은 2차원 배열이라고 가정하자.
- N = 17이라서 int (4바이트) 기준으로 (N+1)*N = 17*18 = 306개의 요소 중, 대각선 요소는 A[0][0], A[1][1], ..., A[16][16]으로 총 17개.
- 메모리상 대각선 요소의 위치는 (N+1) 간격으로 존재함. 즉, A[i][i] = A[0][0] + (N+1)*i
fix_set_diag의 단점:
- A[i][i] 접근 시, 컴파일러는 i * N + i를 계산해서 해당 오프셋을 찾음.
- 매 반복마다 곱셈 연산 i * N이 필요해. 이게 작은 루프에서는 꽤 부담스러울 수 있음.
- 따라서 이 코드는 간접 메모리 접근 + 곱셈 기반 인덱싱이 포함됨.
fix_set_diag_opt의 장점:
- 포인터 기반 접근을 통해 메모리 주소를 직접 조작.
- 인덱스를 (N+1)씩 증가시키며 정확히 대각선 요소만 건드림.
- 루프마다 단순한 덧셈 연산만 있으므로 곱셈 없이 빠르게 동작함.
결론
| 항목 | fix_set_diag | fix_set_diag_opt |
| 인덱싱 방식 | 2D 배열 (A[i][i]) | 1D 포인터 (Abase[i]) |
| 계산량 | 곱셈 포함 (i*N + i) | 단순 덧셈 (i += N+1) |
| 메모리 접근 | 간접 접근 | 연속적 직접 접근 |
| 어셈블리 효율 | 느림 (더 많은 연산) | 빠름 (덧셈 + 비교만) |
👉 그래서 fix_set_diag_opt가 CPU에 더 친화적이고, 특히 루프가 작고 반복적인 경우엔 확실히 빠름!
3.8.5 가변크기 배열
- 가변크기 배열을 원하는 프로그래머는 배열들을 위한 저장공간을 malloc이나 calloc 같은 함수를 사용해서 할당해야 한다.
- 아래의 그림은 가변크기 배열에 대한 행렬 곱셈의 원소 i,k를 계산하는 최초의 코드와 최적화된 코드이다. 컴파일러는 이런 최적화를 자동으로 실행한다.
'Krafton Jungle > 4. CSAPP' 카테고리의 다른 글
| [Computer System] ⑦ 링커 (0) | 2025.04.19 |
|---|---|
| [Computer System] ③ 프로그램의 기계수준 표현 (4) (0) | 2025.04.07 |
| [Computer System] ③ 프로그램의 기계수준 표현 (2) (0) | 2025.04.05 |
| [Computer System] ③ 프로그램의 기계수준 표현 (1) (0) | 2025.04.04 |
| [Computer System] ① 컴퓨터 시스템으로의 여행 (3) (0) | 2025.03.31 |