Optimization & Code Generation (LLVM-IR)

1. Overview

최적화와 코드 생성 - LLVM IR(Optimization & Code Generation: LLVM IR)은 AST로 표현된 프로그램을 **플랫폼 독립적 중간 표현(IR, Intermediate Representation)**으로 변환하고, 수십 가지 최적화 패스(Optimization Pass)를 통해 성능을 극대화한 뒤, 목표 아키텍처(x86-64, ARM)의 기계어로 최종 변환하는 컴파일러 백엔드의 공학입니다.

학습자는 LLVM IR의 SSA(Static Single Assignment) 형태와 load, store, alloca, br 같은 LLVM IR 명령어의 의미를 살펴봅니다. 이어서 상수 전파(Constant Folding), 죽은 코드 제거(Dead Code Elimination), 인라이닝(Inlining), **루프 최적화(Loop Optimization, LICM/Loop Unrolling)**의 핵심 최적화 패스를 비교합니다. 마지막으로 레지스터 할당(Register Allocation, Graph Coloring), 명령어 선택(Instruction Selection), **링킹(Linking)**까지 컴파일러 백엔드 파이프라인의 전체 흐름을 정리합니다.

2. Scope & Boundaries

In-Scope

• LLVM IR & SSA (Intermediate Representation): SSA(Static Single Assignment), PHI 노드, LLVM IR 명령어(alloca, load, store, br, call, ret), 기본 블록(Basic Block), CFG.
• 최적화 패스 (Optimization Passes): 상수 폴딩(Constant Folding), 죽은 코드 제거(DCE), 공통 부분식 제거(CSE), 루프 불변 코드 이동(LICM), 함수 인라이닝(Inlining).
• 레지스터 할당 (Register Allocation): 간섭 그래프(Interference Graph), 그래프 컬러링(Graph Coloring), 스필링(Spilling).
• 코드 생성 (Code Generation): 명령어 선택(Instruction Selection, Tree Tiling), 링킹(Linking, ELF, DWARF), 어셈블리 출력.

Out-of-Scope

• JIT 컴파일: 런타임 코드 생성과 최적화 → 05-02-03 Virtual Machines & JIT 영역.
• 병렬화 최적화(Auto-vectorization 심화): SIMD 자동 벡터화 → 05-04 High-Performance Optimization 영역.

Boundaries

• IR 최적화 vs 기계어 최적화: IR 수준 최적화(LLVM opt 패스)는 플랫폼 독립적으로 적용되어 이식성이 높습니다. 기계어 수준 최적화(코드 생성기, 어셈블러)는 특정 CPU 아키텍처(x86 파이프라인, ARM NEON)에 종속적이지만 CPU 고유 기능(SIMD 명령어, 분기 힌트)을 최대한 활용합니다.

3. Counterexample

• SSA 위반과 PHI 노드 필요성 (Non-SSA IR Ambiguity): x = 1; if cond: x = 2; use(x). SSA 없는 IR에서 use(x) 시점의 x가 1인지 2인지 컴파일러가 간단히 결정하기 어렵습니다. SSA에서는 x1 = 1; if cond: x2 = 2; x3 = PHI(x1 if !cond, x2 if cond); use(x3)로 변수를 단 한 번만 정의(Single Assignment)하여 데이터 흐름 분석이 단순해집니다. PHI 노드가 없으면 최적화 분석이 지수적으로 복잡해집니다.
• 함수 인라이닝의 코드 크기 증가 (Inlining Code Bloat): 재귀 함수 fib(n)을 인라이닝하면 fib(5) 호출이 fib(4)+fib(3)으로 확장되고, 다시 각각 인라이닝되어 코드 크기가 지수적으로 커집니다. 인라이닝 휴리스틱(함수 크기 threshold, 호출 빈도)을 무시하고 모든 함수를 무조건 인라이닝하면 바이너리 크기가 100MB+까지 늘어나 I-Cache 미스로 오히려 성능이 저하됩니다.

4. Prerequisites

• 어셈블리 기초 (Basic): 레지스터, 메모리 주소 지정, 기본 어셈블리 명령어 개념이 필요합니다. (01. Computer Architecture)
• AST (Recommended): 코드 생성의 입력이 AST이므로 파서 프론트엔드의 출력을 이해해야 합니다. (05-02-01 Frontend Compilers)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 단 한 번만 정의되는 변수, LLVM IR과 SSA (LLVM IR & SSA)

• Why to Learn: Clang(C/C++), Rust 컴파일러, Swift 컴파일러, Kotlin Native가 모두 LLVM IR을 백엔드로 사용합니다. LLVM IR의 SSA 구조를 이해하면 최적화 패스의 동작 원리와 clang -O2가 왜 코드를 더 빠르게 만드는지를 설명할 수 있습니다.
• What to Learn:
  • Concepts: SSA(Static Single Assignment, 각 변수는 정확히 1번 정의), 기본 블록(Basic Block, 순차 명령어 집합), 제어 흐름 그래프(CFG), PHI 노드(분기 합류점에서 값 선택), LLVM IR 명령어.
  • Skills: clang -S -emit-llvm -O0 hello.c로 IR 출력 분석.
  • Tools: clang, opt, LLVM IR 플레이그라운드.
• How to Learn:
  • 1단계: C 코드 int add(int a, int b) { return a + b; } → LLVM IR: define i32 @add(i32 %a, i32 %b) { %sum = add i32 %a, %b; ret i32 %sum }. 각 변수(%a, %b, %sum)가 SSA로 단 1번 정의됨을 확인합니다.
  • 2단계: PHI 노드: if (cond) x=1; else x=2; return x; → IR: br cond, label_true, label_false; label_true: br merge; label_false: br merge; merge: %x = phi i32 [1, label_true], [2, label_false]; ret i32 %x. PHI 노드가 두 경로를 합치는 역할을 살펴봅니다.
• Implement: 간단 컴파일러의 IR 방출기. 파이썬 AST → 의사 LLVM IR 출력. BinOp('+', Var('a'), Num(5)) → %t1 = load i32 @a; %t2 = add i32 %t1, 5; ret i32 %t2. 여러 산술식의 IR 방출 테스트.

Recommended

Core Topic 02: 컴파일러가 코드를 개선하는 방법, 핵심 최적화 패스 (Core Optimization Passes)

• Why to Learn: clang -O0(최적화 없음)과 clang -O3(최대 최적화)의 같은 코드 성능 차이가 2~10배에 달하는 이유가 상수 전파, 루프 최적화 등 수십 개의 최적화 패스 때문임을 이해하기 위함입니다.
• What to Learn:
  • Concepts: 상수 전파(Constant Propagation, x=1+2 → x=3), 죽은 코드 제거(DCE, 사용되지 않는 변수/코드 삭제), CSE(공통 부분식 제거, a*b + a*b → t=a*b; t+t), LICM(루프 불변 코드 이동, 루프 밖으로 이동).
  • Skills: opt -passes="constant-folding,dce" 적용 전후 IR 비교.
• How to Learn:
  • 1단계: 상수 전파: int a=2; int b=3; int c=a+b; return c*2; → return 10; (상수 폴딩+전파로 전체 계산이 컴파일 타임에 완료). 컴파일러가 런타임 계산을 컴파일 타임으로 옮기는 과정을 살펴봅니다.
  • 2단계: LICM(루프 불변 코드 이동): for(i=0; i<n; i++) x = arr[i] + strlen(s). strlen(s)가 루프 내 불변이므로 int len=strlen(s); for(i=0; i<n; i++) x=arr[i]+len;로 이동하여 호출 횟수를 O(n)에서 O(1)로 줄이는 방식을 살펴봅니다.
• Implement: 파이썬 미니 IR 최적화 파이프라인. ConstantFolding: IR 명령어 add i32 2, 3 → i32 5로 치환. DeadCodeElimination: 사용되지 않는 임시 변수 %dead = add i32 1, 2(결과 미사용) 제거. TestIR에서 최적화 전/후 IR 명령어 수 비교 로그.

Practical

Core Topic 03: 무한 레지스터를 유한 레지스터에, 레지스터 할당 (Register Allocation)

• Why to Learn: CPU에는 x86-64 기준 15개의 범용 레지스터(rax~r15)만 있지만, IR에는 수백 개의 가상 레지스터가 있습니다. 이를 최소 스필링(Spilling, 레지스터 → 스택 메모리)으로 15개에 배정하는 레지스터 할당이 코드 성능의 핵심임을 이해하기 위함입니다.
• What to Learn:
  • Concepts: 수명(Live Range), 간섭 그래프(Interference Graph, 동시에 살아있는 변수들 간 간선), 그래프 컬러링(k-색, k=레지스터 수), 스필링(메모리로 내보내기), 코어스닝(Coalescing, 복사 명령 제거).
  • Skills: 라이브니스 분석(Liveness Analysis), Chaitin's Algorithm.
• How to Learn:
  • 1단계: IR %a = ...; %b = ...; %c = add %a, %b; %d = mul %a, %c;. 각 변수의 수명: a: [1,4], b: [2,3], c: [3,4], d: [4,4]. a와 b는 동시에 살아있으므로 간섭. a와 c도 간섭. 이 관계로 간섭 그래프를 구축합니다.
  • 2단계: 간섭 그래프를 3색(3개 레지스터 r1, r2, r3)으로 컬러링. 차수가 적은 노드부터 제거하여 스택에 push, 다시 꺼내면서 이웃이 사용하지 않는 색 배정. 불가능하면 스필링을 결정하는 Chaitin's Algorithm을 살펴봅니다.
• Implement: 파이썬 RegisterAllocator. build_interference_graph(live_ranges): 수명 겹침으로 간섭 그래프 구축. graph_color(graph, k): 탐욕적 컬러링 + 스필링 목록 반환. 5개 변수 예시에서 3개 레지스터 배정 결과 출력, 스필링 필요 변수 표시.

Advanced

Core Topic 04: IR을 기계어로, 명령어 선택과 링킹 (Code Generation & Linking)

• Why to Learn: LLVM IR add i32 %a, %b 같은 추상 명령어를 실제 CPU가 실행하는 ADD RAX, RBX x86-64 명령어로 변환하는 명령어 선택(Instruction Selection)과, 여러 오브젝트 파일을 하나의 실행 파일로 합치는 링킹(Linking)의 내부를 이해하기 위해서입니다.
• What to Learn:
  • Concepts: 명령어 선택(Instruction Selection, Tree Tiling, BURS), 명령어 스케줄링(Instruction Scheduling, 파이프라인 위험 회피), 어셈블리 코드 방출, ELF 오브젝트 파일 구조, 정적/동적 링킹(Static/Dynamic Linking, .a/.so).
  • Skills: readelf -a, objdump -d, nm, ldd 명령어 사용.
  • Tools: gcc -S, objdump, readelf, ldd, ld.
• How to Learn:
  • 1단계: Tree Tiling: IR의 연산 트리 Add(Load(Addr('a')), Mul(Const(3), Load(Addr('b')))) 를 x86 명령어 집합의 패턴(Tile)으로 덮기. MOV rax, [a]; IMUL rbx, [b], 3; ADD rax, rbx로 최소 명령어 수를 선택하는 과정을 살펴봅니다.
  • 2단계: ELF 링킹: main.o가 printf를 CALL printf@PLT로 참조하면, 링커가 libc.so의 printf 심볼 주소를 해결(Resolve)하여 PLT(Procedure Linkage Table)/GOT(Global Offset Table) 항목을 채우는 동적 링킹 과정을 살펴봅니다.
• Implement: C 파일 hello.c → gcc -S hello.c → hello.s 어셈블리 분석. gcc -c hello.c → hello.o ELF 파일. readelf -s hello.o 심볼 테이블 출력. gcc hello.o -o hello 링킹. ldd hello 동적 라이브러리 의존성 출력. objdump -d hello 역어셈블로 최적화 효과 비교.

7. Terminology

8. References

Primary

• [P1] CS2023 - Architecture and Organization (AR) - Code Optimization
• [P5] SFIA - Software Design (SWDN) - Compiler Backend

Secondary

• [Engineering a Compiler] Keith Cooper, Linda Torczon - Optimization and Data-flow Analysis
• [LLVM Compiler Infrastructure] LLVM Project - LLVM IR and Optimization Passes

Industry

• [Clang/LLVM Documentation] - LLVM Language Reference Manual (SSA)
• [Rust Compiler Documentation] - MIR (Mid-level IR) and LLVM Backend

9. Final Checklist

Primary

• 프론트엔드(C/Rust)와 백엔드(x86/ARM) 사이를 분리하는 중간 언어(IR)의 아키텍처적 이점을 다대다(N) 맵핑 관점에서 설명할 수 있는가?
• 컴파일러가 죽은 코드 제거(Dead Code Elimination)나 상수 접기(Constant Folding)를 통해 코드를 어떻게 기계적으로 줄이는지 증명할 수 있는가?

Secondary

• SSA(Static Single Assignment) 폼이 변수 재할당을 금지하여 데이터 의존성 그래프(Data Dependency Graph)를 어떻게 단순화시키는지 설명할 수 있는가?
• 루프 전개(Loop Unrolling) 최적화가 분기 예측(Branch Prediction) 실패를 줄이고 명령어 파이프라인(Instruction Pipeline) 스톨을 방지하는 원리를 논증할 수 있는가?

Industry

• 인라인(Inlining) 함수 최적화가 함수 호출 오버헤드를 없애는 반면, 바이너리 크기를 비대하게 만드는 물리적 트레이드오프를 설계할 수 있는가?
• LLVM 인프라를 활용해 새로운 프로그래밍 언어를 만들 때, LLVM IR만 생성해 주면 x86/ARM 최적화 기계어 번역이 무료로 따라오는 메커니즘을 묘사할 수 있는가?