[컴파일러] Storage & Stack Management

👑 Storage Management

컴파일러는 고수준의 프로그래밍 언어를 기계어와 같은 저수준의 언어로 변환해주는 프로그램이다.

컴파일러 설계시에 Storage allocation 방식은 소프트웨어의 성능에 직접적인 영향을 끼치기

때문에 매우 중요하다.

성능 최적화에서 변수를 저장하는 방식은 매우 중요하다. 메모리는 레지스터에 비해 접근 속도가

느리며, 따라서 변수를 가능한 한 가상 레지스터에 저장하려고 해야할 것이다. 만약 루프 내에서

자주 사용되는 변수가 캐시나 레지스터가 아닌 메모리에 저장된다면, 성능 저하를 유발할 것이다.

변수의 저장 위치를 결정하는 것은 주로 HIR → LIR 단계에서 이루어지는데, 이 과정에서 컴파일러는

변수의 타입과 기타 요소들을 분석한다.

💡 Memory

우선 메모리가 어떻게 이루어져 있는지를 짚고 넘어가야 한다. 메모리는 다음과 같은 4개의 영역으로

구성되어 있으며, Stack과 Heap 영역은 런타임 시에 크기가 변하는 특징을 가지고 있다.

• Code 영역

  • 프로그램 명령어가 저장되며, 일반적으로 read-only

• Static Data 영역

  • 전역 변수처럼 프로그램의 전체 수명 동안 유지되는 데이터가 저장되는 영역

• Stack 영역

  • 함수 호출 시 생성되는 지역 변수와 매개변수를 저장

• Heap 영역

  • 동적으로 할당된 메모리를 저장, malloc, new와 같은 system call로 메모리를 요청

💡 Storage Allocation Strategies

일반적으로 다음 3가지의 할당 방식이 존재한다.

1. Static Allocation
2. Heap Allocation
3. Stack Allocation

📌 Static Allocation

정적 할당은 모든 데이터 객체의 저장 공간을 컴파일 시점에 할당하는 방식이다. 정적 할당에서는

변수가 저장 공간에 바인딩되며, 이 식별자들의 주소는 프로그램 실행 동안 변하지 않고 동일하다.

전역 변수, static 변수 등의 할당에 이용된다.

📌 Heap Allocation

힙 할당은 스택 할당의 한계를 보완하기 위해 사용된다. 만약 함수의 활성 레코드(Activation Record)

가 종료된 후에도 지역 변수의 값을 유지하고 싶다면, 스택 할당으로는 해결할 수 없다. 힙은 가장 유연한 할당

방식으로 실행 시간 동안 사용자의 요구에 따라 동적으로 지역 변수를 할당하고 해제할 수 있다. 즉, 프로그램

수행 중에 요청과 반환이 이루어지며, garbage collection을 지원하는 언어의 경우 반환이 자동으로

이루어진다.

📌 Stack Allocation

스택은 일반적으로 동적 할당(Dynamic Allocation)으로 알려져 있다. 동적 할당이란 실행 시간(run-

time)에 메모리를 할당하는 것을 의미한다. 스택은 LIFO(Last In, First Out) 원칙을 따르는

자료 구조로, 다수의 활성 레코드(Activation Record)가 생성될 경우, 활성화가 시작되거나 종료될

때마다 스택에 push 또는 pop된다.

활성 레코드(Activation Record)

스택 프레임(Stack Frame)이라고도 불리며, 함수(또는 프로시저)가 호출될 때 해당 함수 실행을

지원하기 위해 스택에 저장되는 데이터 구조를 의미한다. 함수 실행에 필요한 정보를 담고 있으며,

함수가 끝날 때 스택에서 제거된다. 지역 변수, 인자, 리턴값 등의 정보를 담고 있다.

함수가 호출될 때마다 활성 레코드가 시작되며, 지역 변수는 새로운 저장 공간에 바인딩된다. 이 저장 공간은

런타임에 할당된다. 활성 레코드가 스택에서 팝되면, 지역 변수의 값은 사라지게 되며, 활성 레코드에 할당된

저장 공간도 제거된다.

👑 Stack Management

Stack은 함수 호출과 지역 변수 관리를 위한 핵심 구조이다. Stack은 활성 레코드(또는 프레임)라는

단위로 구성되며, 다음과 같은 정보를 포함한다.

• 매개변수(parameter)

• 지역 변수(local variable)

• 리턴 주소(return address)

• 임시 저장 공간(temporary storage)

스택은 일반적으로 아래 방향으로 증가하며 힙은 반대로 위 방향으로 증가한다. 하지만 이 방향은

시스템 구현에 따라 달라질 수 있다.

💡 Stack 연산

스택 연산은 주로 함수 호출과 반환 시 이루어진다.

• 함수 호출 시 : 새로운 스택 프레임이 생성되어 스택에 push 된다.

• 함수 반환 시 : 현재 프레임이 pop되어 메모리에서 제거된다.

💡 Stack Pointer & Frame Pointer

컴파일러는 스택 기반의 함수 호출과 활성 레코드 관리를 효율적으로 지원하기 위해 다음의 두 가지 포인터를

사용한다.

• Stack Pointer(SP)

  • 스택의 현재 최상단 위치를 가리키는 포인터이다.

  • 함수 호출 시 SP는 새 프레임을 위한 스택 공간을 확보하고, 그 주소를 새 활성 레코드의 최상단으로
    이동시킨다.

  • 함수 반환 시 SP는 호출 이전 상태로 돌아가며, 호출자의 활성 레코드에 다시 접근할 수 있도록 한다.

• Frame Pointer(FP = Base Pointer, BP)

  • 현재 활성 레코드의 시작 위치를 가리키는 포인터이다.

  • 활성 레코드 내부에서 상대적 메모리 접근을 위한 참조를 제공한다.

  • 즉, 해당 활성 레코드 안에서 매개변수, 지역 변수에 대한 빠른 접근을 가능하게 한다.

💡 Run-time Stack

일반적인 Run-time Stack의 구성은 다음과 같다.

다음의 코드가 동작할 때, Run-time Stack이 어떻게 구성되는지를 나타내면 다음과 같다.

void foo(int a) {
    int x = 0;
    if (a <= 1) return;
    foo(a-1);
}

main() {
    int y = 2;
    foo(y);
}

💡 함수 프롤로그 & 에필로그

Prologue와 Epilogue는 함수 호출에서 스택 프레임을 설정하고 해제하는 중요한 코드이다.

함수 호출이 시작될 때 Prologue가 실행되어 함수 실행 환경을 준비하고, 함수가 종료될 때 Epilogue가

실행되어 스택을 정리한다. 이를 통해 함수 간의 호출 체계와 메모리 관리가 원활히 이루어진다.

📌 Prologue

Prologue는 함수가 호출될 때, 함수 실행을 위한 스택 프레임을 설정하는 작업을 수행한다.

함수가 호출될 때 스택 포인터(SP)와 프레임 포인터(FP)를 조정하고, 함수의 지역 변수와

매개변수에 접근할 수 있도록 환경을 준비한다.

• 이전 FP 저장

  • caller의 FP를 현재 스택에 푸시하며, 이를 통해 함수 종료 시 호출자 환경으로 복귀 가능

• FP 업데이트

  • 현재 SP를 FP로 설정

• 스택 공간 확보

  • 함수의 지역 변수와 임시 데이터를 저장하기 위해 SP를 조정하여 공간을 확보한다.

// prologue

push ebp        ; 이전 FP를 스택에 push
move ebp, esp   ; 현재 SP를 FP로 설정
sub esp, 16     ; 지역 변수를 위한 공간 확보 (16바이트)

📌 Epilogue

Epilogue는 함수가 반환될 때, 함수 호출 시 생성했던 스택 프레임을 정리하는 작업을 수행한다.

이는 함수가 종료된 후 호출자의 환경으로 돌아가기 위해 필요한 작업이다.

• FP 복원

  • 이전에 저장했던 호출자의 FP를 복원하여 호출자의 스택 프레임으로 복귀한다.

• SP 복구

  • 함수가 호출될 때 확보했던 지역 변수와 임시 데이터 공간을 해제한다.

  • 스택 포인터를 호출 시점의 상태로 되돌린다.

• 리턴 주소 복원

  • 리턴 주소를 복원하고, 함수가 끝난 후 호출자의 실행 흐름으로 복귀한다.

// epilogue

move esp, ebp    ; SP를 FP로 복원
pop ebp          ; 호출자의 FP 복구
ret              ; 리턴 주소로 복귀

👑 문제

1. 다음의 코드에서 각 변수가 memory, register 중 어디에 저장되는지와 만약 memory에
저장된다면 어떤 영역에 저장되는지를 작성하시오.

int a;
void foo(int b, double c) {
    int d;
    struct { int e; char f; } g;
    int h[10];
    char i = 5;
}

각 변수는 컴파일러의 최적화 전략과 변수 사용 패턴에 따라 저장 위치가 달라질 수 있다.

• int a (전역변수)

  • 메모리의 Static Data 영역에 저장

  • 전역 변수는 프로그램 전체 실행 동안 유지되므로 Static Data 영역에 저장된다.

• int b, double c (매개변수)

  • 대부분 레지스터에 저장

  • 레지스터가 부족하거나 함수 호출 규약에 따라 메모리의 스택 영역에 저장될 수 있다.

• int d (지역변수)

  • 주로 레지스터에 저장

  • 레지스터가 부족하거나 함수 호출 규약에 따라 메모리의 스택 영역에 저장될 수 있다.

• struct, h[10] (지역변수)

  • 구조체나 배열은 크기가 크고, 포인터 또는 인덱싱으로 접근해야 하므로, 메모리의 스택에 저장된다.

• char i = 5 (지역변수)

  • 초기화된 변수는 컴파일러가 상수로 최적화하여 코드에 삽입할 수 있다.

  • 그렇지 않은 경우 주로 레지스터에 저장되며, 메모리 영역에서는 스택 영역에 저장될 수 있다.