Compiler Design & Implementation

1. Overview

컴파일러 설계 및 구현(Compiler Design & Implementation, CDI)은 인간이 작성한 고수준의 텍스트(소스 코드)를 기계가 인식할 수 있는 저수준의 바이너리(0과 1)로 변환하는 매우 길고 정교한 공정 라인(Pipeline)을 다룹니다.

컴파일러는 단순한 텍스트 번역기가 아니라, 우리가 작성한 코드를 수학적으로 분석하여 더 적은 메모리와 CPU 사이클로 실행되도록 바꾸는 최적화 시스템입니다. 학습자는 정규 표현식 기반의 어휘 분석(Lexing)과 스택 기반의 구문 분석(Parsing)을 통해 프론트엔드를 구축하고, 언어와 하드웨어 간의 중립 지대인 중간 표현(IR, LLVM-IR 등)을 생성하는 메커니즘을 배웁니다. 나아가 죽은 코드(Dead Code) 제거, 루프 언롤링(Unrolling), 레지스터 할당(Register Allocation) 같은 백엔드 최적화를 살펴보며 컴파일러 엔지니어링의 핵심 흐름을 이해합니다.

2. Scope & Boundaries

In-Scope

• 번역의 전초기지 (Frontend Pipeline): 스캐너(Scanner)의 토큰 추출, 파서(Parser)의 구문 트리(AST) 구축, 심볼 테이블(Symbol Table) 기반의 의미 분석(Semantic Analysis).
• 중립적 코드 표현 (Intermediate Representation): LLVM IR 매커니즘, 3-주소 코드(3-Address Code), 변수 재정의를 방지하는 SSA(Static Single Assignment) 폼.
• 수학적 코드 최적화 (Optimization Algorithms): 상수 폴딩(Constant Folding), 데드 코드 제거(DCE), 공통 부분식 제거(CSE), 루프 최적화(LICM, Unrolling), 제어 흐름 그래프(CFG) 기반 데이터 흐름 분석.
• 기계어 발행 (Backend Mechanics): 타겟 CPU 아키텍처(x86, ARM) 명령어 선택(Instruction Selection), 그래프 컬러링(Graph Coloring)을 활용한 레지스터 할당(Register Allocation).

Out-of-Scope

• 운영체제 로더/메모리 적재 상세 메커니즘: ELF 형식 해석이나 페이징 시스템 런타임 적재 → 03. Operating Systems 영역으로 위임.
• 가비지 컬렉터(GC) 등 동적 메모리 회수 엔진: 컴파일 이후에 동작하는 런타임 환경 상세(JVM, V8) → 05-03. Runtime Systems 영역으로 위임.

Boundaries

• CDI vs. Computer Architecture (02): CA(02)가 CPU 내부의 파이프라인이나 레지스터 하드웨어 그 자체를 다룬다면, CDI는 컴파일러가 그 하드웨어 특성을 고려해 빠르게 실행되는 어셈블리어를 생성하는 방법에 집중합니다.

3. Counterexample

• 컴파일러의 최적화 능력을 과신하는 태도: gcc -O3 옵션을 주면 코드가 무조건 최적화되어 10배 빨라질 것이라고 착각하는 행위입니다. 컴파일러 최적화기는 **'코드의 의미(Semantics)가 변하지 않음'**을 수학적으로 확신할 때만 코드를 수정합니다. 포인터 에일리어싱(Pointer Aliasing - 두 포인터가 같은 곳을 가리킬 가능성)이 존재하는 C 코드에서는 컴파일러가 최적화를 포기하고 보수적인 메모리 접근을 유지할 수 있다는 한계를 설명할 수 있어야 합니다.
• 프론트엔드와 백엔드의 직접 결합 (N x M 문제): 컴파일러를 만들 때 파싱한 결과를 바로 기계어로 변환하게 만들면, 언어가 5개이고 타겟 CPU가 5개일 때 $5 \times 5 = 25$개의 조합을 따로 구현해야 합니다. 이를 줄이기 위해 중간 표현(IR)을 두고 $5 + 5 = 10$번의 작업만으로 조합을 처리하는 **LLVM의 3단계 파이프라인 구조(Frontend $\rightarrow$ IR Optimizer $\rightarrow$ Backend)**를 이해해야 합니다.

4. Prerequisites

• 언어 설계 및 타입 시스템 기초 (Basic): 소스 코드가 어떻게 AST로 파싱되는지, 타입 체크가 어떻게 이뤄지는지에 대한 이론적 바탕이 필수입니다. (05-01. LDT)
• 컴퓨터 아키텍처 및 어셈블리 (Recommended): 백엔드에서 기계어를 생성하려면 타겟 하드웨어의 명령어 셋(ISA)과 레지스터 제약 사항을 파악하고 있어야 합니다. (02. Computer Architecture)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 전위 파이프라인 (Lexing & Parsing Frontend)

• Why to Learn: 무질서한 텍스트 덩어리를 컴퓨터가 트리(Tree) 구조로 탐색하고 조작할 수 있는 규격화된 데이터 포맷으로 바꾸기 위해서입니다.
• What to Learn:
  • Concepts: 렉서(Lexer/Scanner), 파서(Parser), 추상 구문 트리(AST), 심볼 테이블(Symbol Table).
  • Skills: 정규 표현식으로 소스 코드에서 키워드, 연산자, 식별자(Identifier)를 토큰 단위로 추출. 하향식 파싱(Recursive Descent)을 통한 함수콜 스택 기반 트리 빌드 방식.
  • Tools: 스캐너 생성기(Flex), 파서 생성기(Bison, Yacc, ANTLR).
  • Trade-offs: 손으로 직접 짠 재귀 하향 파서의 에러 메시지 직관성 및 커스텀 유연성 vs 파서 생성 툴이 만들어주는 $O(N)$ 속도의 Bottom-up 파서(LALR)가 주는 개발 생산성.
• How to Learn:
  • 1단계: int a = 5 + 3; 문장을 스캐너에 통과시켜 [TYPE:INT] [ID:a] [OP:EQ] [LIT:5] [OP:PLUS] [LIT:3] [SEMI]의 토큰 스트림 배열이 생성되는 과정을 도식화합니다.
  • 2단계: 이 토큰 스트림을 읽으며 Assignment 노드 산하에 Variable 노드와 Addition 노드를 매달아내는(트리 파싱) 과정을 스택 시뮬레이션으로 추적합니다.
• Implement: 특정 정규식 규칙을 파라미터로 받아 문자열을 훑으며 유효한 토큰들을 식별해 내는 수제(Hand-written) 상태 머신(FSM) 스캐너 모듈.

Recommended

Core Topic 02: 중간 표현과 SSA 폼 (Intermediate Representation)

• Why to Learn: 수십 가지 프로그래밍 언어와 수십 가지 하드웨어 아키텍처 사이에서 최적화 알고리즘을 단 한 번만 작성하여 재활용할 수 있는(M x N 문제 해결) 공용어를 마스터하기 위해서입니다.
• What to Learn:
  • Concepts: 중간 표현(IR), 3-주소 코드(Three-Address Code), 정적 단일 할당(Static Single Assignment, SSA) 폼.
  • Skills: 깊고 복잡한 AST를 선형적인 IR 명령어로 평탄화(Flattening)하는 변환 방식.
  • Tools: LLVM-IR 명령어 분석, Clang 옵션(-emit-llvm).
  • Trade-offs: 고수준 AST 구조에서 최적화(루프)하기 좋은 이점 vs 하드웨어에 가까운 레지스터 레벨 IR에서 메모리 레이아웃을 최적화하기 좋은 이점을 모두 취하기 위해 IR을 다층(Multi-level IR)으로 유지하는 최신 컴파일러의 비용.
• How to Learn:
  • 1단계: $x = (a + b) \times (c - d)$ 라는 트리를 순회하면서, t1 = a + b, t2 = c - d, x = t1 * t2 라는 3-주소 코드로 임시 변수를 만들어 평탄화하는 과정을 봅니다.
  • 2단계: x = 1; x = x + 1; 코드를 분석할 때 '현재 x가 무엇인가' 헷갈리는 문제를 막기 위해 변수를 한 번만 할당하는 SSA 폼(x1 = 1; x2 = x1 + 1;)으로 재작성하여 최적화 분석의 난이도를 낮추는 방식을 익힙니다.
• Implement: 입력된 간단한 수식 AST를 후위 순회(Post-order Traversal)하며 가상의 임시 레지스터 번호(%1, %2...)를 부여해 3-주소 코드 문자열로 출력하는 IR 변환기.

Practical

Core Topic 03: 코드 최적화 엔진 (Optimizer Mechanics)

• Why to Learn: 개발자가 가독성을 위해 남겨둔 중복 계산식과 불필요한 메모리 참조를 컴파일러가 안전하게 줄여, 프로그램의 실행 속도를 개선하기 위해서입니다.
• What to Learn:
  • Concepts: 제어 흐름 그래프(Control Flow Graph, CFG), 기본 블록(Basic Block).
  • Skills: 상수 폴딩(Constant Folding), 대수적 간소화($x \times 0 \rightarrow 0$), 공통 부분식 제거(CSE), 죽은 코드 제거(Dead Code Elimination), 루프 불변 코드 이동(LICM), 함수 인라이닝(Inlining).
  • Tools: 데이터 흐름 분석(Data Flow Analysis) 방정식.
  • Trade-offs: 루프 언롤링(Unrolling)이 주는 분기 조건 검사 횟수 감소(속도 증가) 이점 vs 코드 크기가 커져 CPU 명령어 캐시 용량을 초과하면 오히려 속도 저하를 낳는 명령어 캐시 미스(Cache Miss)의 딜레마.
• How to Learn:
  • 1단계: 분기문(if-else)이 없는 연속된 명령어 묶음을 '기본 블록'으로 만들고, 이 블록들을 선으로 이은 CFG 그래프를 그려 프로그램 구조를 드러냅니다.
  • 2단계: 루프 안에서 매번 똑같은 값을 계산하는 y = a + b를 찾고, 이 코드가 루프 밖에서 한 번만 실행되도록 블록 위로 옮기는(LICM) 과정을 IR 명령어 이동으로 시연합니다.
• Implement: CFG 그래프를 순회하며 어떤 변수가 이후에 사용되지 않는지(Liveness 분석) 파악한 뒤, 해당 변수의 연산식을 제거하는 초소형 죽은 코드 제거(DCE) 패스.

Advanced

Core Topic 04: 백엔드와 기계어 발행 (Target Code Emission)

• Why to Learn: 무한한 임시 변수를 쓰던 가상의 IR 코드를, 16개 혹은 32개 정도로 제한된 실제 CPU 레지스터에 배치하고 최종 바이너리를 만들어내기 위해서입니다.
• What to Learn:
  • Concepts: 명령어 선택(Instruction Selection), 명령어 스케줄링(Instruction Scheduling), 레지스터 할당(Register Allocation).
  • Skills: 그래프 컬러링(Graph Coloring) 알고리즘을 이용한 레지스터 간섭 그래프(Interference Graph) 해결 방식, 메모리 스필링(Spilling).
  • Tools: 대상 기계의 아키텍처 매뉴얼(ABI).
  • Trade-offs: 복잡한 컴파일 최적화를 오래 돌려 빠른 바이너리를 만드는 AOT(Ahead-of-Time) 방식 vs 실행 도중에 자주 쓰이는 핫스팟(Hotspot) 코드만 컴파일하여 즉시 실행하는 JIT(Just-in-Time) 방식의 컴파일 타임/런타임 줄다리기.
• How to Learn:
  • 1단계: 변수 A와 B가 동시에 살아있는 구간(Live Range)이 겹친다면 둘을 선으로 잇고(간섭 그래프), 이 그래프에 주어진 K개의 색깔(물리 레지스터)을 칠해 인접 노드끼리 색이 겹치지 않게 하는 그래프 컬러링 문제를 풉니다.
  • 2단계: 만약 색칠에 실패(물리 레지스터 개수 부족)하면 어쩔 수 없이 변수 하나를 느린 RAM 메모리로 쫓아내는 '스필 코드(Spill Code: Store & Load)'가 어셈블리어 사이사이에 삽입되는 속도 병목 구간을 관측합니다.
• Implement: 최소한의 x86 어셈블리 명령어 구조에 맞춰, 3-주소 코드 목록을 MOV, ADD, MUL 같은 기계어 니모닉(Mnemonic)으로 변환해 출력하는 최종 코드 제너레이터 뼈대 작성.

7. Terminology

8. References

Primary References

• [P1] CS2023 - PL/Compilers & Runtimes — Compiler engineering sections.
• [P2] SWEBOK - Software Construction — Code generation and compilation processes.

Secondary References

• [Compilers: Principles, Techniques, and Tools (Dragon Book)] Aho et al. — The industry standard textbook.
• [Engineering a Compiler] Keith Cooper & Linda Torczon — Practical optimization focus.

Industry References

• [LLVM Language Reference Manual] — Real-world IR and optimization standard.
• [The Architecture of Open Source Applications - LLVM] — Deep dive into modern design.

9. Final Checklist

Primary Checklist

• 컴파일러의 5단계 파이프라인(Lex-Parse-Semantic-IR-Backend)의 흐름과 각 단계의 출력을 명확히 기술할 수 있는가? (P1)
• SSA 폼이 데이터 흐름 분석(Data Flow Analysis)의 복잡도를 높이는지 낮추는지 근거를 들어 설명 가능한가? (P1)

Secondary Checklist

• LLVM-IR이 다중 언어-다중 하드웨어 간 'M x N' 문제를 어떻게 효율적으로 해결하는지 인지하는가?
• 레지스터가 부족한 상황에서 '그래프 컬러링' 알고리즘이 레지스터 낭비를 줄이는 원리를 이해하는가?

Industry Checklist

• GCC나 Clang의 최적화 플래그(-O level)에 따라 애플리케이션의 성능 변화를 측정하고 병목을 추적 가능한가? (SFIA)
• 특정 하드웨어 아키텍처(예: SIMD 지원)에 맞는 명령어를 생성하기 위한 백엔드 요구사항을 식별할 수 있는가?