프로시저... 맛있는 시저...

죄송합니다.

스택과 스택연산

• push로 데이터를 추가, pop으로 데이터를 제거
  • pop할 땐 제일 최근에 push한 데이터가 먼저 제거됨
• 배열로 구현하며, 원소들을 한쪽 끝에서만 추가하거나 제거
  • 이때 높은 주소 -> 낮은 주소 순으로 추가됨
  • 스택의 주소가 낮은 쪽 (푸시/팝되는 쪽)을 상단, 주소가 높은 쪽을 하단이라 칭함
  • 즉 제일 최근에 push한 원소는 최상단에 위치
• 스택 포인터: 탑 원소의 주소를 저장하는 레지스터로, %rsp로 나타냄

푸시 연산

• 스택 포인터의 주소를 데이터의 크기만큼 감소시키고, 새로운 값을 스택 포인터가 가리키는 메모리 주소에 저장
• e.g., 레지스터 %rbp에 저장된 8바이트 값을 푸시
  • subq $8, %rsp: 스택 포인터의 주소를 8 감소. 여기서는 8바이트 값이므로 8을 감소시킨 것
  • movq %rbp, (%rsp): 레지스터 %rbp에 저장된 값을, 스택포인터 (%rsp)가 가리키는 메모리 주소로 복사
• 위 두 명령어을 pushq %rbp로 한꺼번에 수행 가능

팝 연산

• 스택 포인터의 주소를 데이터의 크기만큼 증가시킴
• 실제로 원소가 제거되지는 않지만, 스택 포인터보다 낮은 주소에 위치하므로 접근이 불가능함.
  • 그리고 어차피 다시 푸시면 그 자리에 새롭게 푸시된 값이 덮어 씌워짐
• e.g., 8바이트 값을 팝해 레지스터 %rax에 저장
  • movq (%rsp), %rax: 스택포인터 (%rsp)가 가리키는 메모리 주소의 값을, 레지스터 %rax로 복사
  • addq $8, %rsp: 스택포인터의 주소를 8 증가. 여기선 8바이트 값이므로, 8을 증가시킨 것
• 위 두 명령어를 popq %rax로 한꺼번에 수행 가능

프로시저

• "여러 줄의 코드를 하나로 묶어둔 것"이라 생각하면 됨
• 프로그래밍 언어에서는 일반적으로 인수와 리턴 값으로 구성된 함수, 메서드로 구현됨
  • 어려우면 진짜 함수라고 생각하고 읽어도 됨

런타임 스택

• 함수 호출 시 정보를 저장하는 메모리 내 공간
• 프로시저가 호출될 때마다 필요한 정보를 스택에 저장하고, 함수가 끝나면 정보를 제거함
  • 후입선출 구조: 현재 실행 중인 프로시저의 스택 프레임은, 스택의 최상단 (가장 낮은 주소)에 위치
  • 현재 레지스터 값, 지역 변수, 함수 인수 등
• 스택 프레임: 각각의 프로시저가 사용하는 스택 내 저장공간
• 모든 정보가 무조건 스택에 정보가 저장되지는 않음
  • 레지스터 등 저장공간이 부족한 경우 사용됨

⚠️ 런타임 스택은 전에 배웠듯이 주소가 낮을수록 상단, 높을수록 하단입니다. 스택의 데이터가 입출력되는 쪽이 상단입니다. 헷갈리지 않으시길 바랍니다.

함수 호출

• 프로시저 P에서 프로시저 Q를 호출할 때
• 프로시저 Q를 호출: call Q:
  • P의 리턴주소를 스택에 푸시: P의 call 명령어 다음 명령어의 주소
  • 이후 프로시저 Q의 시작 주소로 점프해, 제어권 전달
• 프로시저 Q 반환 (종료): ret
  • 리턴주소를 스택에서 팝 -> 리턴 주소로 점프해, 프로시저 P로 복귀
• 점프 과정에서는 현재 실행 중인 명령어를 나타내는 프로그램 카운터 (%rip)에 저장된 주소가 변경됨

예시

• 주소 0x400563에서 callq 400540을 실행
  • 주소 0x400540에 다른 프로시저가 있다고 가정
  • 리턴 주소 0x400568를 스택에 푸시 (callq 다음 명령어의 주소)
  • 주소 0x400540으로 점프
• 이후 ret 실행
  • 스택에서 리턴 주소 0x400568를 팝
  • 팝한 리턴 주소로 점프해, 원래 프로시저가 호춛된 위치로 복귀
  • 반환값은 ret 명령어 이후 레지스터 %rax를 통해 전달됨

인수 전달

• 프로시저 호출 시 인자 전달은 레지스터를 통해 이루어짐
• x86-64에선 최대 6개의 정수형 (정수, 포인터) 인자를 레지스터로 전달함
  • 8바이트 인자는 %rdi -> %rsi-> %rdx -> %rcx -> %r8 -> %r9 순으로 레지스터로 전달됨
  • 4 / 2 / 1바이트 인자는 위 레지스터들의 하위 부분으로 전달됨
• 6개를 초과하는 경우, 나머지 인자는 스택으로 푸시됨
  • 크기가 8바이트보다 작아도 스택에는 8바이트 단위로 공간이 할당됨에 유의
  • 스택 내 인수는 스택 포인터 %rsp의 주소에 8의 단위를 더해 접근 (e.g., %rsp + 8)
• 인자들은 call 명령어 실행 전에 레지스터로 전달되고 스택에 푸시됨
  • 이후 call 명령어 실행 시, 리턴 주소가 푸시됨

예시

void proc(long a1, long *a1p, int a2, int *a2p, short a3, short *a3p, char a4, char *a4p){
  // 내부 코드는 생략
}

• long: 8바이트, int: 4바이트, short: 2바이트, char: 1바이트
• 포인터 (* 붙은 변수들): 모두 8바이트
• 1~6번째 인수는 레지스터에 저장
• 7번째 인수 a4, 8번째 인수 *a4p는 스택에 저장
• 이후 인자가 모두 전송되면, 리턴 주소를 푸시

⚠️ 위 그림은 8바이트 데이터를 한 줄로, 8바이트 내 더 작은 데이터는 각 줄 안의 칸으로 표시했음에 유의하세요.

지역변수 저장

• 프로시저의 지역변수는 일반적으로 레지스터에 저장됨
• 하지만 데이터를 레지스터에 저장할 수 없는 경우, 스택 프레임에 공간을 할당
  • 레지스터의 수가 부족하거나
  • 주소 연산자(&)를 사용해 메모리 주소가 필요하거나
  • 지역변수가 배열 또는 구조체일 때
• 크기가 8바이트보다 작으면, 해당 크기만큼만 할당됨

🤔 주소... 연산자요? 그게 뭔 소리에요?

• 주소 연산자를 &변수와 같이 사용하면 해당 변수의 주소를 반환합니다.
• 이때 변수의 주소가 존재하기 위해선, 변수는 레지스터가 아닌 메모리에 저장되어 있어야 합니다.
  • 레지스터에는 주소 값이 없습니다!!
• 따라서 &변수 사용 전 변수를 선언할 때, 레지스터가 아닌 메모리에 저장시켜 놓아야 합니다.

예시

long call_proc(){
  long x1 = 1;  // 8바이트
  int x2 = 2;   // 4바이트
  short x3 = 3; // 2바이트
  char x4 = 4;  // 1바이트
  proc(x1, &x1, x2, &x2, x3, &x3, x4, &x4)
  // 주소 (&x1, &x2, &x3, &x4)는 모두 8바이트

  return (x1 * x2 + x3 * x4)
}

• x1, x2, x3, x4를 스택에 푸시
• proc 호출 직전, 인수 중 1~6번째 인수는 레지스터로 전달, 7번째 인수인 x4와 8번째 인수인 &x4는 스택에 푸시
  • 이 시점에선 proc이 호출되지 않아 리턴 주소는 아직 푸시되지 않았음에 유의할 것
• 함수가 종료되면 스택 프레임에 저장된 인수, 지역 변수를 팝한 후, 리턴 주소를 팝해 점프

피호출자 저장 레지스터

• 프로시저 A가 프로시저 B를 호출할 때, B는 A가 나중에 사용할 수 있는 레지스터 값을 덮어쓰지 않아야 함
  • 이러한 값은 피호출자 저장 레지스터에 저장
• 피호출자 저장 레지스터
  • %rbx, %rbp, %r12-%r15 6개의 범용 레지스터
  • 프로시저 B가 해당 레지스터의 값을 필요로 하는 경우, 스택에 기존 값을 푸시한 뒤, 함수 종료 전에 팝해서 복원해야 함
• 호출자 저장 레지스터
  • 피호출자 저장 레지스터 + %rsp(스택 포인터)를 제외한 범용 레지스터
  • 이후 호출된 프로시저에 의해 값들이 변경될 수 있음

예시

long P(long x, long y){
  long u = Q(y);
  long v = Q(x);
  return u + v
}

• Q(y)가 호출되는 동안 P의 매개변수 x의 값을 유지시켜야 함

• Q(x)가 호출되는 동안 Q(y)의 반환값 u의 값을 유지시켜야 함

• 따라서 두 값은 비호출자 저장 레지스터에 저장

• 실제 과정

  • P 시작 시 피호출자 저장 레지스터 %rbp, %rbx의 이전 값을 pushq %rbp, pushq %rbx로 푸시
  • Q(y) 호출 전 x를 %rbp에 복사
  • Q(x) 호출 전 u를 %rbx에 복사
  • P 종료 시 %rbp, %rbx의 이전 값을 popq %rbx, popq %rbp로 팝해 원상태로 복귀

스택에 푸시되는 순서

• 프로시저 호출 시 (call) 다음 순서대로 값이 푸시됨
  • (1) 보존되어야 하는 피호출자 저장 레지스터의 값
  • (2) 프로시저의 지역 변수
  • 이후엔 내부에서 다른 프로시저가 호출될 시만 푸시
  • (3) 전달할 인수 (7번째 인수부터)
  • (4) 리턴 주소
• 프로시저 반환 시 (ret)
  • 역순으로 위의 값을 팝
  • 저장했던 지역 변수 및 피호출자 저장 레지스터의 값을 복원하고,
  • 이전 프로시저의 리턴 주소를 팝하여 점프

배열의 할당과 접근

배열의 선언

• 자료형 $T$, 정수형 상수 $N$에 대해, T A[N]와 같이 배열을 선언할 때
  • 자료형 $T$의 크기가 $L$일 때, $L \times N$ 바이트 의 연속 공간이 메모리에 할당됨
  • 식별자 $A$를 배열이 시작되는 위치의 포인터 $x_A$로 사용
  • 배열의 i번째 원소는 주소 $x_a + i$에 저장됨

예시

• int A[6]의 시작 위치가 $x_A$일 대
  • int는 4바이트이므로 총 24바이트가 할당됨
  • i번째 원소의 주소는 $x_A + 4i$
• A의 시작 주소가 %rdx, i가 %rcx에 저장되어 있을 때
  • A[i]의 주소는 (%rdx, %rcx, 4)로 계산 -> rdx + 4 * %rcx와 동일
  • e.g., movl (%rdx, %rcx, 4), %eax: A[i]의 값을 레지스터 %eax로 복사

포인터 연산

• C언어는 포인터 간 연산을 허용
• p가 $L$ 크기의 자료형 $T$ 데이터에 대한 포인터이고, 값이 $x_p$일 때
  • p + i는 $x_p + L \times i$로 계산됨
• &Expr: 객체 Expr의 주소를 갖는 포인터 생성
• *AExpr: 주소 AExpr에 대해 주소에 위치한 값을 줌
• 배열 참조 A[i]는 *(A + i)와 동일
  • 배열명 A는 주소처럼 동작해, 포인터 연산 가능
  • A + i는 (A의 시작 주소) + (자료형 크기) * i로 연산됨

다중 배열

• int A[5][3]과 같이 이차원 배열을 생성했을 때
  • A는 5개의 배열을 원소로 가짐
  • 각 배열은 3개의 int를 저장하기 위해 12바이트를 필요로 함
  • 총 $5 \times 3 \times 4 = 60$바이트가 할당됨
• 다중 배열의 원소는 행 우선으로 전달됨
  • 행 0의 원소 (A[0]) 이후 행 1(A[1]), 행 2(A[2]).... 순으로 저장됨
• 배열 D[R][C]의 원소 D[i][j]의 주소
  • D의 시작 주소를 $x_D$로 둘 때
  • $(x_D + L \times (C \times i + j))$
  • i행 j열의 원소는 C \times i + j번째 (0으로 시작)로 저장된다는 점에 유의

• 어셈블리어 예시 (int A[3][4]로 선언했을 때, A[i][j]에 접근)

leaq (%rsi, %rsi, 2), %rax       
; %rsi * 3 → 3i 계산 (즉, %rax = 3 × i)

leaq (%rdi, %rax, 4), %rax       
; A + 4 × (3i) → %rax = A + 12 × i

movl (%rax, %rdx, 4), %eax       
; %rax + 4 × j → A + 12i + 4j 위치의 값 → %eax에 저장

• $x_A + 4 \times (3 \times i + j)$는 $x_A + 12 \times i + 4 \times j$이므로 동일 연산

🤔 왜 첫 두 명령어는 leaq, 마지막은 movl이 사용되었나요?

• 첫 두 명령은 유효주소 계산만 하면 되니, 해당 주소값만 읽고 메모리에 접근하지는 않는 leaq가 사용되었습니다.
• 다만 마지막에 데이터를 복사하려면, 계산된 주소의 메모리에 접근해 값을 읽어야 하니 movl를 사용해야겠죠.

포인터를 이용한 배열 접근 최적화

// 최적화 전
int A[5] = {1, 2, 3, 4, 5};
for (int i = 0; i < 5; i++) {
  printf("%d", A[i]);
}

• GCC의 최적화 과정에선, 정수 인덱스 i 대신 포인터로 배열에 접근하게끔 연산이 변경됨

int A[5] = {1, 2, 3, 4, 5};
int* p;
for (p = A; p < A + 5; p++) {
  printf("%d", *p);
}

• 포인터 p의 초깃값은 배열의 시작 주소 (첫 원소의 주소, &A[0])
• *p로 현재 포인터에 저장된 주소의 값에 접근한 뒤, p++로 포인터 연산 수행
  • int형은 4바이트이므로, p++로 포인터는 4바이트 증가
  • 이를 통해 배열의 다음 원소 주소로 이동