이전 글에서도 몇 번 봤던 그림을 다시 보고 시작해보자.
이전 글까지 총 7개의 글에 걸쳐 lexical → Syntax → Semantic 분석을 알아봤었다.
이제는 Code Generation과정에 대해 알아보자.
컴파일러의 역할
컴파일러는 단순히 사람이 작성한 코드를 아무생각없이 기계어로 바꿔주는 것이 아니다.
데이터가 저장공간에 어떻게 저장되고 사용될지를 관리하기도 한다.
또 더 효율적인 코드가 되도록 코드를 바꿀 수도 있다.
데이터 저장 위치 결정
소프트웨어적인 관점에서 CPU는 연산장치, 레지스터, 메모리로 나눠서 이해해볼 수 있다.
여기서 우리는 데이터를 레지스터에 저장할지, 메모리에 저장할지 결정해야한다.
일반적으로 전역 변수나 static변수는 메모리에 저장한다.
로컬 변수들 중에서도 배열, 구조체 같은 복합 타입들은 크기가 커 레지스터에 저장할 수 없어 메모리에 저장한다.
남은 int, float같은 변수들은 레지스터에 저장한다.
프로그램 실행의 기본 단계
OS가 프로그램을 실행시키는 과정은 아래 세 단계로 요약할 수 있다.
1. 프로그램에 메모리 공간을 할당해준다.
2. 코드와 데이터가 그 공간에 load된다.
3. OS가 프로그램의 시작점으로 제어를 넘겨 실행을 시작한다.
일반적으로 낮은 주소에 코드가, 높은 주소에 데이터가 저장된다.
3번 과정에서 OS가 넘긴 제어는 프로그램의 코드를 따라 순차적으로 이동하면서 하나씩 실행을 한다.
이때 함수가 나온다면 함수를 실행 후 다시 해당 호출이 있었던 곳으로 되돌아간다.
Activation & Lifetime
이번글에서 중요하게 다뤄질 개념이다.
- 어떤 프로시저(함수)가 호출이 되었다면 activate되었다고 표현한다.
- activation은 함수가 실행 중일 동안 유효하다. 이때 내부에서 다른 함수가 호출되더라도 유지된다.
- 변수 x의 값이 선언되고 이후로 값이 유효할 동안 x는 live하다고 말한다.
Activation Tree
이때 프로시저 P가 자신의 하위 프로시저Q를 호출했다면 Q가 P보다 먼저 끝나야한다.
이런 관계는 activation tree라는 것을 사용해 나타낼 수 있다.
어려운 개념은 아니기 때문에 아래의 그림을 보면 이해할 수 있을 것이다.
나중에 활성화된 함수가 먼저 끝난다는 성질 때문에 stack을 사용해 이를 표현할 수 있다.
아래 그림은 같은 예시에서 시간 경과에 따른 stack의 모습을 나타낸 것이다.
따라서 이 stack의 상태를 보면 현재 activate되어있는 함수가 무엇인지 알 수 있다.
stack 관리
위의 그림에서 스택의 데이터를 저장하는 단위를 AR또는 frame이라고 한다.
AR은 activation record의 약자이고, 하나의 activation을 관리하기 위한 정보가 들어있다.
stack은 낮은 주소 → 높은 주소 방향으로 쌓인다.
아래는 조금 더 복잡한 예시이다.
가운데 그림은 스택의 전체 모습을 간략히 나타낸 것이고,
오른쪽 그림은 f(2)의 AR의 일부분까지의 상세 모습을 나타낸 것이다.
f(3)의 AR을 예시로 AR의 구성요소를 간단히 알아보자.
return for f(3) : 이 함수의 리턴값을 저장한다. 이 경우 f(2)의 값이 될 것이다.
Prev FP : FP는 frame pointer이다. 나를 호출한 상위 함수의 AR시작점 주소를 얘기한다.
local data : 이 함수 내부에서 사용되는 로컬변수이다.
return addr : 이 f(3)함수가 호출이 끝나고 다시 돌아갈 코드의 주소를 얘기한다.
Argument : f(3)안에서 f(3-1)을 호출하고 있다. 이때 인자인 2를 나타낸다.
AR의 값들에 접근하고 AR을 다루기 위해 포인터 두 개를 사용한다.
FP(frame pointer), SP(stack pointer)이다.
FP는 frame의 base부분의 주소를 나타내고, SP는 스택의 가장 위 주소 보다 하나 큰 값을 나타낸다.
두 개의 포인터를 사용하는 이유는 컴파일 할 때 AR의 크기를 항상 알 수 있는 것은 아니기 때문이다.
아래사진의 왼쪽 모습에서 g()함수가 실행이 끝났다고 하자.
그럼 g의 더이상 activate될 필요가 없으므로 AR은 필요없어진다.
SP에 FP(0x184)의 값을 대입하고, FP에는 g의 AR안에 있던 Prev FP값을 대입해서 오른쪽 그림과 같은 상태로 만들 수 있다.
f(0)에서 g()의 결과값을 가져오려면 SP에 있는 값을 읽기만 하면 된다.
AR내부의 다른 값(local date)등을 읽고 싶다면 FP의 주소에다가 해당하는 offset값을 더해서 해당 칸에 접근하면 된다.
위의 그림에서는 $fp + 0x1c 라고 생각할 수 있다.
변수 저장
전역변수를 AR에 저장하는 것은 비효율적이다.
따라서 아래처럼 static data 부분을 만들어 여기에 저장한다.
또 프로그램 실행 중 동적으로 할당되는 값들은 heap에 저장한다.
다음 글에서는 사람이 high level 언어로 작성한 코드를 어셈블리어로 바꾸는 법을 알아보자.
'CS > 컴파일러' 카테고리의 다른 글
| [컴파일러 이론] 10. Dataflow Analysis (1) | 2025.12.31 |
|---|---|
| [컴파일러 이론] 9. Code Generation - Stack Machine (1) | 2025.12.29 |
| [컴파일러 이론] 7. Semantic Analysis (0) | 2025.12.25 |
| [컴파일러 이론] 6. Bottom-up Parsing, LR grammars (0) | 2025.12.25 |
| [컴파일러 이론] 5. Parsing table 만들기 (0) | 2025.12.24 |