컴파일러 구조와 최적화 단계

컴파일러 파이프라인 개요

소스 코드
    ↓ Lexer (어휘 분석)
  토큰 스트림
    ↓ Parser (구문 분석)
  AST (추상 구문 트리)
    ↓ Semantic Analysis (의미 분석)
  타입 검사된 AST
    ↓ IR 생성
  중간 표현 (IR)
    ↓ 최적화 패스
  최적화된 IR
    ↓ 코드 생성
  기계어 / 바이트코드

1. 어휘 분석 (Lexer)

소스 코드를 토큰 시퀀스로 분리합니다.

입력: int x = 42 + y;
토큰: [INT][IDENT:x][ASSIGN][NUMBER:42][PLUS][IDENT:y][SEMICOLON]

정규 표현식 기반 DFA(결정적 유한 오토마타)로 구현합니다.

2. 구문 분석 (Parser)

토큰을 **AST(Abstract Syntax Tree)**로 변환합니다.

x = 42 + y
      AST:
    Assign
    /     \
   x      Add
          /   \
         42    y

LL(k) 하향식, LR(k) 상향식 파서가 일반적입니다. C++은 문맥 의존 문법이라 일반 LR 파서만으로는 부족해 특수 처리가 필요합니다.

3. 의미 분석 (Semantic Analysis)

• 타입 검사: int + string → 오류
• 범위 분석: 변수 선언 위치, 스코프
• 심볼 테이블: 이름 → 타입/주소 매핑

4. 중간 표현 (IR)

아키텍처 독립적인 형태로 변환합니다. LLVM IR이 대표적입니다.

; x = a + b * c
%t1 = mul i32 %b, %c
%t2 = add i32 %a, %t1
store i32 %t2, ptr %x

SSA(Static Single Assignment) 형태: 각 변수가 정확히 한 번만 할당되어 최적화가 쉬워집니다.

5. 주요 최적화 패스

상수 폴딩

2 + 3 → 5   (컴파일 타임에 계산)

공통 부분식 제거 (CSE)

a = b * c + d
e = b * c + f
→ t = b * c; a = t + d; e = t + f

루프 최적화

• Loop Invariant Code Motion: 루프 불변 코드를 루프 밖으로 이동
• Loop Unrolling: 루프를 펼쳐 분기 예측 개선
• Vectorization: SIMD 명령어로 변환

인라이닝

함수 호출 오버헤드 제거. inline 키워드나 LTO(Link Time Optimization)로 제어.

데드 코드 제거

if (false) { doSomething(); }  // 제거됨

6. 코드 생성 백엔드

IR → 타겟 아키텍처 명령어 선택:

• 레지스터 할당: 변수를 레지스터에 배치 (NP-완전 문제, 그래프 컬러링)
• 명령어 스케줄링: 파이프라인 효율을 위한 순서 재배치
• Calling Convention: 함수 인자와 반환값 전달 규약

게임 개발자 관련 지식

// 1. __attribute__((noinline)) — 인라이닝 방지
__attribute__((noinline)) void HeavyFunction() {}

// 2. Profile-Guided Optimization (PGO)
// 실제 실행 프로파일로 핫 경로 우선 최적화

// 3. LTO (Link-Time Optimization)
// 모듈 간 인라이닝, 전역 최적화
// MSVC: /GL /LTCG
// GCC/Clang: -flto

// 4. Unity Build / LTCG
// 여러 .cpp를 하나로 합쳐 컴파일 — 빌드 시간 단축 + LTO 효과

정리

• 컴파일러는 Lexer → Parser → Semantic → IR → Optimize → Codegen 순서
• SSA IR이 대부분 현대 컴파일러(LLVM, GCC)의 핵심
• 상수 폴딩, CSE, 루프 최적화, 인라이닝이 핵심 최적화 패스
• PGO, LTO로 링크 단계에서 전역 최적화 가능
• C++ 미정의 동작(UB)은 컴파일러가 “이 경로는 없다”고 가정해 공격적 최적화 유발