컴파일러 작동 원리

소개

컴파일러란 무엇일까? 프로그래밍을 해 본 사람이라면 여러 가지 언어로 코드를 작성한 후, run 버튼을 누르거나 혹은 직접 명령어를 입력하여 실행시켜본 경험이 있을 것이다. 텍스트 파일 형태의 소스 파일(source file)이 실행 파일 형태로 변화하는 과정이 궁금했던 사람 또한 많을 것이다(내가 그렇다). 그리하여 그 과정 中 컴파일러가 하는 일에 대해 알아볼 것이다.

그림1 ❘ 컴파일러가 소스 코드를 기계 명령어로 번역하는 과정

다시 본 질문으로 들어와서, 컴파일러란 무엇일까? 컴파일러는 단순히 번역기 이자 텍스트 처리 프로그램(text processor)라고 생각해도 무관하다. 앞서 스포했듯 텍스트 파일 형태의 소스 파일(source file)을 CPU가 직접 실행할 수 있는 실행 파일 형태로 번역해 주는 역할을 한다. 위 그림1 을 보면 이해가 쉬울 것이다.
단순하게 시작과 결과만을 보고선, 정확한 기능을 유추하기 어렵다. 지금부터 한 단계씩 차근차근 알아가 보도록 하자.
 

실행 과정

컴파일러는 프로그래밍 언어의 특성에 따라 일부 단계가 다를 수 있지만, 보통 아래와 같은 순서를 거쳐 실행된다.

• 구문 분석
• 최적화
• 코드 생성
• 링킹

또한, 본 세부 과정을 살펴 보기 전, 참고하여 살펴볼 코드는 아래와 같다.

int a=1;
int b=2;

while (a<b) {
  b = b - 1;
}

 

구문 분석(Syntax Analysis)

컴파일러는 먼저 각 항목을 잘게 쪼갠다(연산자, 괄호, 식별자 등). 이때 각 항목이 가지고 있는 추가 정보를 함께 묶어서 관리한다. 예시 코드에서 int를 보면, '키워드(keyword)라는 사실'과 '그중 int 키워드라는 사실'이라는 추가 정보가 포함되는 것이다. 이렇게 각 항목에 추가로 정보를 결합한 것을 전문용어로 토큰(token)이라고 한다.
이와 같이 컴파일러는 가장 먼저 소스 코드를 돌아다니면서 모든 토큰을 찾아낸다. 우리의 예시 코드를 처리하면 아래와 같은 결과가 나오게 될 것이다. 각 줄은 하나의 토큰을 의미한다.

T_Keyword     int
T_Identifier  a
T_Assign      =
T_Int         1
T_Semicolon   ;
T_Keyword     int
T_Identifier  b
T_Assign      =
T_Int         2
T_Semicolon   ;
T_While       while
T_LeftParen   (
T_Identifier  a
T_Less        <
T_Identifier  b
T_RightParen  )
T_OpenBrace   {
T_Identifier  b
T_Assign      =
T_Identifier  b
T_Minus       -
T_Int         1
T_Semicolon   ;
T_CloseBrace  }

 
이렇게 소스 코드에서 토큰을 추출하는 과정을 어휘 분석(lexical analysis)라고 한다. 하지만 코드는 구문에 따라 작성되어야 하고, 컴파일러는 구문에 따라 토큰을 처리해야 한다. while 구문을 예로 들어보자.

while (표현식) {
 반복 내용
 }

위 while 구문에서 컴파일러가 'while' 키워드의 토큰을 찾으면 다음 토큰이 '('라는 것을 알고 있는 상태로 기다리게 된다. 물론 while 키워드에 필요하지 않은 토큰이 오게 된다면 문법 오류(syntax error)를 낼 것이다. '(' 토큰을 정상적으로 받았다면, 다음 토큰은 불(bool) 표현식이어야 한다. 구문에 따라 꼼꼼하게 작업을 진행하면 최종적으로 추상 구문 트리(abstract syntax tree, AST) 형태로 빌드되게 된다. 이러한 과정은 해석(parsing)이라고 하며, 아래 그림2 는 구문 트리의 예시이다.

그림2 ❘ 생성된 추상 구문 트리

토큰 추출 부터 구문 트리 생성까지의 전체 과정을 구문 분석(syntax analysis)라고 한다.
 

최적화(Optimizing)

최적화 단계는 효율성을 높이고, 산출되는 기계 코드의 질을 높이기 위한 과정이다. 이에 활용되는 다양한 종류의 알고리즘 방식이 있는데, 일반적으로 사용되는 대표적인 두 기법만 알아보도록 하자.

1. Common Subexpression Elimination (CSE)

Common Subexpression Elimination, 이하 CSE, 는 특정 표현식을 해당 결과를 가지는 하나의 변수로 치환하는 기법이다.

그림3 ❘ Common Subexpression Elimination

위 그림3을 예로 들면, b*c라는 포현식을 해당 결괏값을 가진 tmp로 치환하는 식이다. 곱셈 연산을 하는 비용과 tmp라는 변수를 저장하고 사용하는 비용을 계산하여 더욱 효율적인 방향으로 선택하게 되는 것이다.

2. Constant Folding/Propagation

상수라는 공통으로 두 기법을 묶어 보았다(실제로 함께 사용되는 경우가 많다).
우선, Constant Folding은 런타임 이전에 컴파일 과정에서 상수 표현에 대한 인식과 계산을 담당하는 기법이다.

a = 150 * 50 * 12
b = "hel" + "lo"

대부분의 컴파일러는 위 코드의 변수 a와 같이 두번의 곱연산을 저장하지 않는다. 대신 계산된 결과인 90000을 컴파일 과정에 치환하여 저장하게 된다. 또한, 변수 b와 같은 문자열 구문도 계산된 결과("hello")와 치환하게 된다.
이어서 Constant Propagation은 특정 상수로 선언된 변수를 표현식에서 값(선언된 상수)으로 치환하는 과정이다.
아래 예시 코드는 Constant Folding과 Constant Propagation을 사용하는 상황이다.

int x = 16;
int y = 10 - x / 4;
return y * (32 / x + 1);

x를 치환한다

int x = 16;
int y = 10 - 16 / 4;
return y * (32 / 16 + 1);

계산 후 이어서 y도 치환한다

int x = 16;
int y = 6;
return 6 * 3;

결과적으로 아래와 같이 나오게 된다

int x = 16;
int y = 6;
return 18;

Dead Code Elimination, Loop Invariant Code Motion과 같이 다양한 기법들도 소개하고 싶지만 글의 전체적인 길이를 위해 따로 정리하여 소개하도록 하겠다. 이렇게 두 번째 과정 최적화(Optimizing)를 마치고 다음 과정으로 넘어간다.
 

코드 생성

int a=1;
int b=2;

while (a<b) {
  b = b - 1;
}

위 코드를 기억하는가? 구문 분석이 끝나면 컴파일러는 구문 트리를 탐색한 결과를 바탕으로 최적화가 진행된 중간 코드(Intermediate Representation Code, IR Code)를 생성한다. 중간 코드는 어셈블리어 코드를 거쳐 기계 명령으로 변환되는데, 지금 까지 알 수 있듯 굉장히 복잡하고 지능적인 과정이기에 넘기고 결과만을 살펴보도록 하자.

그림4 ❘ 코드 생성 과정

이것으로 전체 컴파일 과정이 끝나진 않는다. 이렇게 생성된 기계 명령어 데이터는 .o 확장자를 가지는 파일에 저장되는데, 이러한 파일을 대상 파일(object file)이라고 한다. 이렇게 모든 소스 파일에 각각의 대상 파일이 만들어지게 되는 것이다.
 

링킹

컴파일러가 여러개의 대상 파일을 생성하였다면, 링커는 대상 파일을 한데 묶어 최종 실행 파일을 만드는 역할을 한다. 윈도의 EXE 나 리눅스의 ELF 파일과 같은 실행 파일이 그 최종 형식이 되는 것이다. 특정한 소스 파일이서 다른 모듈에 정의되어 있는 함수를 참조할 때, 컴파일러의 시점에서는 함수가 어느 메모리 주소에 위치할지 정확히 알 수가 없다. 그리하여 해당 함수를 N으로 표시해 두고 이후 링크 과정에서 실제 메모리 주소로 재배치하는 과정을 거친다.

그림5 ❘ 링크와 실행 파일 생성

간단하게 언급했듯이 링킹 또한 세부적인 과정이 존재한다. 다같이 세 가지 과정을 살펴보도록 하자

1. 심벌 해석

우선, 심벌 해석의 단계다. 여기서 심벌(symbol)이란 전역 변수와 함수의 이름을 포함하는 모든 변수 이름을 의미한다. 링커는 대상 파일에서 참조하고 있는 외부 심벌마다 해당하는 정의가 존재하는지 확인한다. 이러한 심벌 정보는 컴파일러가 대상 파일을 만들 때 포함시켜 링커로 전달된다. 

그림6 ❘ 대상 파일의 구조

위 그림6은 대상파일의 중요한 부분들이다. 소스 파일 내 정의된 함수에서 변환된 기계 명령어가 저장되는 Code Segment. 소스 파일의 전역 변수가 저장되는 부분인 Data Segment. 그리고 Symbol Table에는 소스 파일마다 외부에서 참조 가능한 심벌과 어떤 외부 심벌을 참조하고 있는지에 대한 정보가 기록된다. 심벌 해석 단계는 링커가 각 대상 파일 내 사용할 외부 심벌이 Symbol Table내에 정의되어 있는지 확인하는 과정인 것이다.

2. 실행 파일 생성

실행 파일의 구조 속에도 대상 파일과 같은 Code Segment와 Data Segment가 존재한다. 물론 세부적인 작동 방식에는 많은 차이가 있지만, 링커가 대상파일과 라이브러리를 조합하여 실행 파일을 만든다는 것은 변함 없다. 링커가 실행 파일을 생성하는 방법에는 정적 라이브러리를 이용한 Static Linking과 동적 라이브러리를 이용한 Dynamic Linking이 존재한다. 

그림7 ❘ 정적 링킹과 동적 링킹

대상 파일과 라이브러리 내용을 모두 복사하는 Static Linking. 동적 라이브러리의 이름, 심벌 테이블, 재배치 정보 등 필수정보만을 포함시키고 실행 파일의 실제 실행 시점 시 불러오는 Dynamic Linking. 이 둘 간의 장단점과 Dynamic Linking의 세부 작동 과정은 따로 알아보도록 하고, 우선은 위 그림7과 같은 형식으로 실행 파일을 만들어 간다고 이해하자.

3. 재배치

지금까지 외부 참조할 변수나 함수가 있는지 검증을 하고(심벌 해석), 어떠한 방식으로 실행파일을 조립할지(실행 파일 생성) 알아보았다. 이제 남은 것은 그림6에서 볼 수 있는 대상 파일의 정보를 해석하여 링커가 외부 참조 부분을 실제 주소로 재배치시키는 과정이다. 이때 사용하는 실제 주소란, 프로그램이 실행된 후의 물리 메모리(Physical Memory) 주소가 아닌, 가상 메모리(Virtual Memory)를 의미한다. 더 자세한 가상 메모리에 대한 설명은 스킵하겠다.

call func1

링커가 위 코드와 같은 func1 함수의 위치를 어떻게 알 수 있을까? 이는 컴파일러가 대상 파일을 만들때의 과정을 자세히 살펴보면 알 수 있다. 그림6의 대상 파일 구조를 보면 Relocation Information이라는 부분이 있다. 컴파일러는 메모리 주소를 확정할 수 없는 변수를 발견할 때 마다 .relo.text에는 해당 명령어를 저장하고 .relo.data.에는 해당 명령어와 관련된 데이터를 저장한다. 링커는 이러한 정보를 토대로 재배치를 진행하는 것이다.

그림8 ❘ 링커의 재배치 과정

실행 파일을 만드는 과정이 되면 모든 기계 명령어와 전역 변수가 프로그램 실행 시간에 위치할 메모리 주소를 결정할 수 있게 된다. 위 그림8속 재배치 과정의 1번에 해당하는 부분을 보자. func1의 주소가 확정된 상태에서 링커는 이러한 주소를 2번과 같이 Code Segment에 재배치시키게 되는 것이다.
 

마무리

이제 우리는 컴퓨터와 대화할 수 있게된 비밀들을 간단하게나마 알게 되었다. 현대에 계속해서 발전되고 있는 알고리즘이나 과정 그 자체에 대해 정확히는 아니더라도 흐름정도는 알아둘 필요가 있다고 생각한다. 만일 당신이 이러한 컴파일러를 만든다면 어떠한 과정을 어떻게 거치는 것이 효율지 생각해 보자.
 

참고 자료

https://pages.cs.wisc.edu/~fischer/cs701.f05/lectures/Lecture02.4up.pdf
https://en.wikipedia.org/wiki/Copy_propagation#cite_note-dragonbook-1
https://en.wikipedia.org/wiki/Object_file
https://stackoverflow.com/questions/16749522/symbol-table-and-relocation-table-in-object-file