오토마타와 컴파일러 12 - 코드 생성

IR에서 기계어로

최적화된 중간 표현은 아직 실행 가능한 프로그램이 아니다. 이를 특정 프로세서가 이해할 수 있는 기계어로 변환하는 마지막 단계가 코드 생성(Code Generation)이다. 코드 생성기는 세 가지 핵심 과제를 해결해야 한다. IR의 연산을 적절한 기계 명령어로 대응시키는 명령어 선택, 제한된 수의 레지스터에 변수를 배치하는 레지스터 할당, 그리고 파이프라인 효율을 극대화하기 위한 명령어 스케줄링이다.

이 세 과제는 서로 밀접하게 얽혀 있다. 명령어 선택이 달라지면 필요한 레지스터 수가 변하고, 레지스터 할당 결과에 따라 스케줄링의 자유도가 달라진다. 각각을 독립적으로 최적화하는 것만으로는 전체 최적해에 도달할 수 없으며, 이들 사이의 균형을 잡는 것이 코드 생성기 설계의 핵심이다.

명령어 선택

명령어 선택(Instruction Selection)은 IR의 각 연산을 대상 아키텍처의 기계 명령어로 매핑하는 과정이다. 하나의 IR 연산이 하나의 기계 명령어에 대응되는 경우도 있지만, 현실은 대부분 그렇게 단순하지 않다. 하나의 IR 연산이 여러 기계 명령어의 조합으로 구현되거나, 반대로 여러 IR 연산이 하나의 복합 명령어로 합쳐질 수 있다.

대표적인 명령어 선택 기법으로 트리 패턴 매칭(Tree Pattern Matching)이 있다. IR을 트리 형태로 표현한 후, 미리 정의된 명령어 패턴들을 트리에 매칭시킨다. 하나의 트리를 커버하는 방법이 여러 가지일 때, 비용이 가장 낮은 조합을 선택한다.

IR 트리:              패턴 매칭 결과 (x86):
    [+]
   /   \
 [Reg]  [*]           → lea rax, [rbx + rcx*4]
        / \            (덧셈과 곱셈을 하나의 LEA 명령어로 합침)
     [Reg] [4]

위 예시에서 Reg + Reg * 4라는 IR 패턴은 x86의 LEA(Load Effective Address) 명령어 하나로 구현할 수 있다. 이를 두 개의 명령어(곱셈 후 덧셈)로 나누어 생성하는 것보다 효율적이다.

매크로 확장(Macro Expansion)은 더 단순한 접근법이다. 각 IR 연산에 대해 미리 정해진 명령어 템플릿을 기계적으로 적용한다. 구현이 간단하지만 복합 명령어를 활용하지 못하므로 코드 품질이 낮을 수 있다. 실제 컴파일러에서는 매크로 확장으로 초기 코드를 생성한 후 핍홀 최적화(Peephole Optimization)로 인접한 명령어들을 더 효율적인 조합으로 교체하는 방식이 흔하다.

레지스터 할당

프로세서의 레지스터는 메모리보다 수십 배에서 수백 배 빠르지만, 그 수가 극히 제한되어 있다. x86-64에서 범용 레지스터는 16개, ARM에서는 31개이다. 최적화된 IR에는 수백, 수천 개의 가상 레지스터가 사용될 수 있으므로, 이를 물리 레지스터에 매핑하는 레지스터 할당(Register Allocation)은 코드 생성에서 가장 까다로운 문제이다.

레지스터 할당은 그래프 색칠(Graph Coloring) 문제로 모델링할 수 있다. 먼저 간섭 그래프(Interference Graph)를 구성한다. 각 가상 레지스터가 노드가 되고, 동시에 살아 있는(live) 두 레지스터 사이에 간선을 긋는다. 이 그래프를 물리 레지스터 수만큼의 색으로 색칠할 수 있으면 모든 변수를 레지스터에 배치할 수 있는 것이다.

간섭 그래프 예시:

가상 레지스터: v1, v2, v3, v4
물리 레지스터: R1, R2, R3 (3개)

  v1 ── v2
  |  ×  |          v1 → R1
  v3 ── v4          v2 → R2
                    v3 → R2 (v2와 v3은 동시에 살아있지 않음)
                    v4 → R3

그래프를 색칠할 수 없는 경우, 즉 물리 레지스터가 부족한 경우에는 일부 변수를 메모리에 저장했다 다시 불러오는 스필(Spill)이 필요하다. 어떤 변수를 스필할지에 따라 성능 영향이 크게 달라지므로, 사용 빈도와 루프 깊이를 고려하여 스필 비용이 가장 낮은 변수를 선택한다.

그래프 색칠 알고리즘은 최적해를 보장하지만 NP-완전 문제이므로 실행 시간이 길어질 수 있다. 이 때문에 JIT 컴파일러처럼 컴파일 속도가 중요한 환경에서는 선형 스캔(Linear Scan) 알고리즘이 대안으로 사용된다. 선형 스캔은 변수의 수명 구간(Live Range)을 정렬한 후 순서대로 레지스터를 배정하며, O(n log n)의 시간 복잡도로 합리적인 품질의 할당을 수행한다.

명령어 스케줄링

현대 프로세서는 파이프라인을 통해 여러 명령어를 동시에 처리한다. 그러나 명령어 사이에 데이터 의존성이 있으면 파이프라인이 멈추는 스톨(Stall)이 발생한다. 명령어 스케줄링(Instruction Scheduling)은 의존성을 위반하지 않는 범위 내에서 명령어 순서를 재배치하여 스톨을 최소화하는 최적화이다.

스케줄링 전:                      스케줄링 후:
load  r1, [addr1]    ← 메모리 접근   load  r1, [addr1]
add   r2, r1, 1      ← r1 대기 스톨   load  r3, [addr2]    ← 독립적 로드를 먼저
load  r3, [addr2]                     add   r2, r1, 1      ← r1 로드 완료 후 실행
mul   r4, r3, 2      ← r3 대기 스톨   mul   r4, r3, 2      ← r3 로드 완료 후 실행

위 예시에서 두 번째 load를 앞으로 이동시켜 첫 번째 load의 지연 시간 동안 유용한 작업을 수행하도록 한 것이다. 결과적으로 동일한 명령어 집합이지만 실행 시간이 줄어든다.

스택 프레임과 호출 규약

함수 호출은 코드 생성에서 별도의 관리가 필요한 영역이다. 함수가 호출될 때마다 스택 프레임(Stack Frame)이 생성되며, 여기에 지역 변수, 저장된 레지스터, 반환 주소, 함수 인자 등이 저장된다.

스택 프레임 구조 (일반적인 레이아웃):

높은 주소 ┌─────────────────┐
         │   함수 인자들    │  ← 호출자가 전달
         ├─────────────────┤
         │   반환 주소      │  ← call 명령어가 저장
         ├─────────────────┤
         │ 이전 프레임 포인터│  ← 스택 체인 유지
         ├─────────────────┤
         │   저장된 레지스터 │  ← callee-saved 레지스터
         ├─────────────────┤
         │   지역 변수      │
낮은 주소 └─────────────────┘  ← 스택 포인터 (SP)

호출 규약(Calling Convention)은 함수 호출 시 인자 전달 방법, 반환 값 위치, 레지스터 보존 책임 등을 정의하는 규칙이다. x86-64의 System V ABI에서는 처음 6개의 정수 인자를 RDI, RSI, RDX, RCX, R8, R9 레지스터로 전달하고, 반환 값은 RAX에 저장한다. Windows x64에서는 RCX, RDX, R8, R9를 사용한다. 코드 생성기는 대상 플랫폼의 호출 규약을 정확히 준수해야 하며, 그렇지 않으면 다른 컴파일러가 생성한 코드와 링크할 수 없게 되는 것이다.

다양한 아키텍처 대응

하나의 컴파일러가 여러 아키텍처를 지원하려면, 코드 생성기에서 아키텍처별 차이를 체계적으로 관리해야 한다. CISC 아키텍처(x86)는 복잡한 명령어와 다양한 주소 지정 모드를 제공하여 명령어 선택의 폭이 넓다. RISC 아키텍처(ARM, RISC-V)는 단순한 명령어를 빠르게 실행하는 것에 초점을 맞추므로, 하나의 IR 연산이 여러 명령어로 분해되는 경우가 많다.

LLVM과 같은 컴파일러 기반 구조에서는 타겟 디스크립션(Target Description) 파일을 통해 각 아키텍처의 레지스터 집합, 명령어 정의, 호출 규약 등을 선언적으로 기술한다. 코드 생성기의 핵심 알고리즘은 아키텍처와 무관하게 유지하면서, 아키텍처 고유의 세부 사항은 타겟 디스크립션에서 읽어오는 구조이다. 새로운 아키텍처를 추가할 때 코드 생성기 전체를 다시 작성할 필요 없이 타겟 디스크립션만 추가하면 된다는 점에서 IR 기반 설계의 확장성이 드러나는 셈이다.

JIT 컴파일

지금까지 다룬 것은 프로그램 실행 전에 기계어를 생성하는 AOT(Ahead-of-Time) 컴파일이었다. 이에 대응하는 개념이 JIT(Just-in-Time) 컴파일이다. JIT 컴파일러는 프로그램이 실행되는 도중에 바이트코드나 IR을 기계어로 변환한다. Java의 HotSpot, JavaScript의 V8, .NET의 RyuJIT이 대표적인 JIT 컴파일러이다.

JIT 컴파일의 핵심 장점은 실행 시점의 정보를 최적화에 활용할 수 있다는 것이다. AOT 컴파일러는 프로그램이 어떤 입력을 받을지, 어떤 분기를 자주 탈지를 알 수 없다. JIT 컴파일러는 프로파일링을 통해 자주 실행되는 경로(핫 패스)를 식별하고, 해당 경로에 공격적인 최적화를 적용할 수 있다. 과연 JIT이 AOT보다 항상 빠른 코드를 생성할까? 그렇지 않다. JIT 컴파일 자체에 소요되는 시간이 실행 시간에 포함되므로, 짧게 실행되는 프로그램에서는 오히려 불리하다. 오래 실행되는 서버 애플리케이션에서 JIT의 장점이 극대화되는 이유가 여기에 있다.

이론에서 실전까지

이 시리즈는 유한 오토마타라는 가장 단순한 계산 모델에서 출발했다. 유한 오토마타는 상태와 전이만으로 패턴을 인식하는 기계였으며, 이것이 컴파일러의 첫 단계인 렉서의 이론적 기반이 되었다. 정규 표현식이 유한 오토마타와 동치라는 사실, NFA를 DFA로 변환할 수 있다는 사실은 단순한 이론적 흥미를 넘어서 실제 렉서 구현의 토대가 되는 것이었다.

유한 오토마타의 한계를 인식하면서 우리는 스택을 가진 푸시다운 오토마타로 나아갔고, 이것이 파서의 이론적 기반이 되었다. 문맥 자유 문법으로 프로그래밍 언어의 구조를 기술하고, LL 파싱과 LR 파싱이라는 체계적인 구문 분석 방법을 공부했다. 이 파싱 이론이 Yacc나 ANTLR 같은 파서 생성기의 핵심 원리였다.

그 위에 의미 분석이 타입 안전성과 스코프 규칙을 보장했고, 중간 표현과 최적화가 프로그램의 의미를 보존하면서 성능을 개선했으며, 최종적으로 코드 생성이 추상적인 표현을 실제 하드웨어가 실행할 수 있는 명령어로 변환했다.

돌아보면, 컴파일러의 각 단계는 이론 위에 세워진 공학이다. 오토마타 이론이 없었다면 렉서와 파서를 체계적으로 설계할 근거가 없었을 것이고, 형식 언어 이론이 없었다면 프로그래밍 언어의 문법을 정확하게 기술할 방법이 없었을 것이다. 우리가 매일 사용하는 컴파일러가 수십 년간의 이론적 연구 위에 서 있다는 사실을 이 시리즈를 통해 조금이나마 전달할 수 있었기를 바란다.