콘텐츠로 바로가기
HY_TECH_BASE

Compiler Design & Implementation

고수준 소스 코드를 기계어로 변환하는 멀티 스테이지 파이프라인과 코드 최적화 알고리즘을 다루는 학습 노드입니다.

sys.entry
M

Me

hyunyoun's Blog

posts6 min read

1. Overview

컴파일러 설계 및 구현(Compiler Design & Implementation, CDI)은 추상적인 알고리즘 기술을 물리적인 CPU 명령어로 변환하는 정교한 공정 과정을 다룹니다.

컴파일러는 프로그래밍 언어의 '번역기'이자 '최적화 도구'입니다. 학습자는 어휘 분석(Frontend)부터 중간 표현(IR) 생성을 거쳐 타겟 하드웨어에 최적화된 기계어 생성(Backend)에 이르는 전체 파이프라인을 이해합니다. 특히 LLVM과 같은 현대적 컴파일러 인프라를 통해 코드의 성능을 물리적으로 개선하는 핵심 기법들을 실습합니다.

2. Scope & Boundaries

In-Scope

  • Frontend Pipeline: Lexical analysis(토큰화), Parsing(구문 분석), Semantic analysis
  • Intermediate Representation: LLVM-IR, 3-Address Code, SSA(Static Single Assignment) form
  • Optimization Algorithms: Dead code elimination, Loop optimization, Register allocation
  • Backend Mechanics: Instruction selection, Code emission, Linker & Loader 기초

Out-of-Scope

  • 운영체제의 로더/링커 상세 동작 (03. Operating Systems 영역으로 위임)
  • 순수 인터프리터 언어의 런타임 최적화 (05-03 Runtime Systems 영역으로 위임)

Boundaries

  • CDI vs. LDT: LDT는 '언어의 명세'에 집중한다면, CDI는 '그 명세를 기계로 옮기는 하드웨어 지향적 변환 로직'에 집중합니다.

3. Counterexample

  • 단순히 gcc 명령어를 사용하여 실행 파일을 만드는 것은 CDI 학습이 아닙니다. gcc -O3 옵션이 적용될 때 **인라인 함수 확장(Inlining)**이나 **공통 부분식 제거(CSE)**가 중간 코드 수준에서 어떻게 이루어지는지 내부 알고리즘을 설명할 수 있어야 합니다.

4. Prerequisites

  • 언어 설계 및 타입 시스템 기초 (Basic): AST 구조와 문법(CFG) 이해가 선행되어야 합니다. (05. LDT)
  • 컴퓨터 아키텍처 및 임베디드 매카니즘 (Recommended): CPU 명령어 셋(ISA)과 레지스터 구조 이해가 필수적입니다. (02. Computer Architecture)

5. Learning Map

  1. The Translation Pipeline: 소스 코드가 토큰과 트리를 거쳐 기계어로 분해되는 단계를 익힙니다.
  2. Intermediate Logic: 특정 하드웨어에 종속되지 않은 효율적인 중간 언어(IR)를 이해합니다.
  3. The Optimizer: 수학적 모델을 통해 코드의 실행 속도와 크기를 물리적으로 개선합니다.
  4. Machine Code Emission: 레지스터 할당과 타겟 명령어 매핑의 최적화 과정을 배웁니다.

6. Learning Topics

Basic

Core: 어휘 및 구문 분석 (Lexing & Parsing)

  • Why to Learn: 텍스트 형태의 소스 코드를 컴퓨터가 조작 가능한 데이터 구조로 정형화하기 위함입니다.
  • What to Learn:
    • 정규 문법(Regular Grammar) 기반의 스캐너 제작 원리
    • Top-down 파싱(Recursive Descent) vs Bottom-up 파싱(LALR) 물리 로직
    • 파서 생성 도구(Lex/Yacc, ANTLR)의 작동 메커니즘
  • How to Learn:
    • 간단한 수식 계산기를 위한 정규 표현식 토큰 셋 설계 실습
    • 스택을 이용한 시프트-리듀스(Shift-Reduce) 파싱 과정 수기 추적
  • Implement: 주어진 문법(CFG)에 따라 토큰 스트림을 AST로 변환하는 기초 파서

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

  • Why to Learn: 하드웨어 가속 최적화를 효율적으로 수행하기 위한 중립적인 형식을 유지하기 위해서입니다.
  • What to Learn:
    • LLVM IR 및 3-주소 코드(3AC)의 구조와 장점
    • SSA(Static Single Assignment) 폼: 변수 버전 관리를 통한 데이터 흐름 분석 용이성
    • 심볼 테이블(Symbol Table)의 계층적 관리 물리
  • How to Learn:
    • 간단한 C 코드를 LLVM IR로 컴파일하여 사람이 읽을 수 있는 형태로 분석
    • 일반적인 코드를 SSA 폼으로 수기 변환해보며 중복 정의 해결 실습
  • Implement: AST를 순회하며 3-주소 코드를 생성하는 코드 제너레이터(Generator)

Practical

Core: 코드 최적화 기법 (Optimization)

  • Why to Learn: 동일한 로직을 더 적은 CPU 사이클과 메모리 접근으로 수행하기 위함입니다.
  • What to Learn:
    • 지역 최적화: 상수 폴딩(Constant Folding), 대수적 간소화
    • 전역 최적화: 데이터 흐름 분석(Data Flow Analysis), 도달 가능성 분석
    • 루프 최적화: 루프 언롤링(Unrolling), 불변 코드 이동(LICM)
  • How to Learn:
    • 최적화 전후의 어셈블리 코드를 비교하여 명령어 개수와 분기문 감소 확인
    • 제어 흐름 그래프(CFG) 상에서 살아있는 변수(Live Variables) 분석 실습
  • Implement: 단순 3AC 코드 셋에서 사용되지 않는 할당(Dead Code)을 제거하는 최적화 패스

Advanced

Core: 백엔드 및 타겟 코드 생성 (Target Code Generation)

  • Why to Learn: 실제 물리 하드웨어의 성능을 100% 끌어내는 코드를 생성하기 위해서입니다.
  • What to Learn:
    • 레지스터 할당(Register Allocation): 그래프 컬러링(Graph Coloring) 알고리즘 적용
    • 명령어 선택(Instruction Selection) 및 스케줄링 물리
    • 가상 머신(VM) 및 JIT(Just-In-Time) 컴파일 아키텍처 개요
  • How to Learn:
    • 부족한 레지스터 환경에서 스필(Spill) 코드가 생성되는 과정 물리적 분석
    • x86 vs ARM 타겟별 최적 명령어 매핑 차이 연구
  • Implement: 단순화된 CPU 명령어 셋에 맞춰 레지스터를 강제 할당하는 기초 백엔드 시뮬레이터

7. Terminology

Term (EN / ko, abbr) 1문장 정의 단계(기본/권장/실무/심화) 역할/맥락 관련 개념 유사/대비/함께 사용 오해 포인트 Evidence(Primary/Secondary/Industry) Flags(core/misused/legacy)
SSA Form 각 변수가 딱 한 번만 정의되도록 코드를 재구성하여 분석을 용이하게 하는 중간 표현 방식입니다. 추천 최적화 토대 LLVM IR 3-Address Code 런타임 제한으로 오해 P1:CS2023/Compilers core
Parsing (구문 분석) 토큰 스트림이 언어의 문법 규칙(CFG)을 따르는지 확인하고 구조를 생성하는 과정입니다. 기본 프론트엔드 Lexing / AST CFG 의미 분석과 동일시함 P1:CS2023/Compilers core
LLVM 현대 컴파일러 제작을 위한 모듈형 재사용 가능 라이브러리 및 툴체인의 집합체입니다. 실무 인프라 Clang / Backend GCC 단순한 '언어'로 오해 Industry Project core
Dead Code Elimination 프로그램의 출력이 변하지 않는 범위 내에서 실행되지 않거나 결과가 쓰이지 않는 코드를 제거하는 기법입니다. 실무 최적화 Data Flow Pruning 주석 제거와 동일시함 P1:CS2023/Compilers core

8. References

Primary References

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 지원)에 맞는 명령어를 생성하기 위한 백엔드 요구사항을 식별할 수 있는가?

Concepts & Tags

#compiler-frontend#code-optimization#llvm-ir#lexer-parser