5.2 중간 표현과 최적화 — 프로그램을 분석하고 바꾸기 좋은 형태

AST는 파서의 산출물로는 훌륭하지만 최적화의 좌표계로는 나쁘다 — 제어 흐름이 문법에 암묵적으로 숨어 있고, 같은 변수의 여러 대입이 값의 흐름을 가린다. 이 문서는 프로그램을 기본 블록·CFG·SSA로 낮춰서 분석과 변환이 단순해지는 구조를 세우고, 대표 최적화 패스를 "필요한 분석 → 변환 → 지켜야 할 의미"로 해부한 뒤, 최적화가 절대 넘을 수 없는 선 — 관찰 가능한 동작의 보존 — 이 어디에 그어지는지 확인한다.

학습 목표

• AST 수준에서 최적화 패스를 쌓기 어려운 이유를 제어 흐름과 값 정의의 암묵성으로 설명한다.
• 작은 함수를 기본 블록과 CFG로 나누고, SSA 형태의 단일 정의 불변식과 phi 함수의 역할을 판독한다.
• constant propagation, dead code elimination, CSE, inlining 각각에 필요한 분석과 지켜야 할 의미 조건을 짝지어 설명한다.
• 관찰 가능한 동작 보존이라는 계약을 근거로, 부동소수점·overflow·aliasing·부작용이 특정 최적화를 막는 상황을 판별한다.
• 코드 생성의 세 책임(instruction selection, register allocation, scheduling)을 개념적으로 구분한다.

배경: 왜 이것이 존재하는가

최적화 패스를 AST에 직접 붙인다고 상상해 보자. "이 변수는 여기서 항상 20이다"를 알아내려면 if/else, while, for, 삼항 연산자, &&의 단락 평가까지 — 문법 형태마다 값이 어느 경로로 흐르는지 다시 따져야 한다. 패스가 10개면 이 문법 처리 코드가 10벌이다. 게다가 소스 언어가 여럿이고 대상 CPU도 여럿이면, 언어 M개 × 대상 N개의 조합마다 최적화기를 만드는 M×N 문제가 된다.

중간 표현(IR, intermediate representation)은 이 두 문제를 동시에 푼다. 소스 문법의 다양성을 소거한 하나의 표현으로 낮추면(lowering) 모든 패스가 같은 계약 위에서 동작하고, 프런트엔드 M개와 백엔드 N개가 IR을 사이에 두고 M+N으로 줄어든다. LLVM이 정확히 이 구조다 — C·C++·Rust·Swift가 LLVM IR로 내려오고, x86·ARM·RISC-V 백엔드가 그 IR을 소비한다.

IR은 하나의 수준이 아니라 스펙트럼이다. 소스 구조를 많이 남긴 high-level IR(언어별 검사와 특화 최적화에 유리), 제어 흐름과 연산이 명시된 mid-level IR(대부분의 범용 최적화가 사는 곳), 기계 명령에 가까운 low-level IR(레지스터·주소 계산이 드러남)로 내려가며, 정보를 버리는 대신 대상 독립성과 분석 단순성을 산다. 이 문서의 중심은 mid-level이다.

핵심 개념

예제는 챕터 5 공통 Toy 언어의 작은 함수다. IR 표기는 특정 컴파일러의 문법이 아니라 이 문서의 축약 표기이며, 아래의 모든 변환은 변환 전후 코드를 같은 입력 범위로 실행해 결과가 일치함을 확인했다.

fn classify(n) {
  let scale = 2;
  let base = scale * 10;
  let r = 0;
  if (n < base) { r = n * scale; } else { r = n + base; }
  return r;
}

기본 블록과 CFG — 제어 흐름을 명시적 그래프로

기본 블록(basic block)은 "들어오는 입구가 하나, 나가는 출구가 하나"인 직선 명령열이다 — 중간으로 뛰어들 수도, 중간에서 빠져나갈 수도 없다. 프로그램을 기본 블록으로 자르고 분기를 간선으로 이으면 제어 흐름 그래프(CFG, control flow graph)가 된다. classify를 낮추면:

entry:                          ┌─────────┐
  scale ← 2                     │  entry  │
  base  ← scale * 10            └────┬────┘
  r     ← 0                    t0 참 ╱ ╲ 거짓
  t0    ← n < base                 ╱   ╲
  branch t0 ? then : else    ┌────▼─┐ ┌─▼────┐
then:                        │ then │ │ else │
  r ← n * scale              └────┬─┘ └─┬────┘
  jump merge                      ╲     ╱
else:                              ╲   ╱
  r ← n + base                  ┌───▼─▼───┐
  jump merge                    │  merge  │
merge:                          └─────────┘
  return r

문법은 사라졌다. if/else였는지 삼항 연산자였는지는 이제 중요하지 않고, 남은 것은 블록과 간선뿐이다. 분석이 물을 질문들 — 이 블록에 도달할 수 있는가, 이 블록을 반드시 거치는가(지배, dominance), 루프는 어디인가(back edge) — 이 전부 그래프 질문이 된다. CFG는 이 문서의 최적화만이 아니라 5.4의 데이터 흐름 분석과 5.3의 JIT 컴파일이 공유하는 좌표계다.

SSA — 값의 정의를 하나로 만든다

CFG 위에서도 남는 골칫거리가 재대입이다. 위 IR에서 r은 세 곳에서 대입된다. merge의 return r이 읽는 r이 어느 대입에서 왔는지 알려면 모든 경로를 역추적해야 하고, 이 use-def 추적이 사실상 모든 최적화의 전제 작업이라 패스마다 반복하면 낭비다.

SSA(static single assignment)는 이 추적을 표현 자체에 굽는다. 불변식은 하나 — 모든 값은 정확히 한 번만 정의된다. 재대입은 새 버전(r1, r2, …)이 되고, 분기가 합류하는 지점에서는 "어느 경로로 왔는지에 따라 값을 고르는" phi 함수(φ)가 버전들을 합친다.

entry:
  scale1 ← 2
  base1  ← scale1 * 10
  r1     ← 0
  t0     ← n < base1
  branch t0 ? then : else
then:
  r2 ← n * scale1
  jump merge
else:
  r3 ← n + base1
  jump merge
merge:
  r4 ← φ(then → r2, else → r3)
  return r4

φ는 실행되는 명령이 아니라 합류의 표기다(코드 생성 시점에 각 선행 블록 끝의 복사로 풀린다). 이 표기가 사는 이득은 즉시적이다 — r4의 정의는 φ 하나이고, φ의 피연산자는 r2와 r3이며, 각각의 정의도 한 곳이다. 어떤 값이 어디서 왔는지가 이름만으로 확정된다. "SSA는 변수에 번호를 붙인 표기법"이라는 통념이 놓치는 것이 이것이다 — 번호는 수단이고, 목적은 use-def 관계를 자료구조 없이 표현에 내장해 모든 패스의 분석을 단순화하는 것이다. r1 ← 0을 보라. SSA 이전에는 "이 대입이 죽었는지" 알려면 모든 경로를 검사해야 했지만, SSA에서는 r1을 읽는 곳이 없다는 사실만으로 즉시 죽은 코드다.

대표 패스 — 분석, 변환, 지켜야 할 의미

최적화 패스는 셋 다 같은 뼈대다: 어떤 사실을 증명하고(분석), 그 사실이 허용하는 변환을 하되, 관찰 가능한 의미를 보존한다.

패스	필요한 분석	변환	지켜야 할 의미 조건
constant folding	피연산자가 컴파일 시점 상수	2 * 10 → 20	대상 실행 환경과 같은 산술 의미(overflow·반올림)
constant propagation	이 사용 지점의 값이 항상 그 상수	사용처를 상수로 치환	정의와 사용 사이에서 값이 바뀔 경로가 없어야
dead code elimination	결과를 읽는 곳이 없음	명령 제거	제거 대상에 관찰 가능한 부작용이 없어야
common subexpression elimination	같은 계산이 이미 수행됨	재계산을 재사용으로 치환	두 지점 사이에서 피연산자 불변, 계산이 순수해야
inlining	호출 대상이 확정됨	호출을 본문 복사로 치환	호출 의미(재귀·스택 관찰 등) 보존, 비용 모델

classify의 SSA에 constant propagation과 folding을 적용하면 scale1 = 2, base1 = 2 * 10 = 20이 확정되어 사용처가 상수로 바뀌고, DCE가 이제 아무도 읽지 않는 scale1·base1·r1의 정의를 지운다.

entry:                               변환 전 대비:
  t0 ← n < 20                        - scale1, base1 정의 소멸 (전파 후 죽음)
  branch t0 ? then : else            - r1 ← 0 소멸 (읽는 곳 없음)
then:  r2 ← n * 2;  jump merge       - base1의 곱셈이 컴파일 시점에 접힘
else:  r3 ← n + 20; jump merge
merge: r4 ← φ(then → r2, else → r3)
  return r4

패스는 서로의 기회를 만든다. 이 예에서도 전파가 없었다면 DCE가 지울 것이 없었다. 실전에서 가장 극적인 조합은 inlining이다 — 호출을 본문으로 펼치는 순간, 인자로 들어온 상수가 본문에 전파되고, 상수 조건 분기가 접히고, 죽은 가지가 사라진다. 반대 방향의 상호작용도 있다: 한 패스가 다른 패스의 패턴을 깨뜨려 기회를 없앨 수 있고, 이 때문에 모든 프로그램에 최적인 고정된 패스 순서는 존재하지 않는다(phase-ordering problem). 실무 컴파일러의 -O2 같은 수준은 "대부분의 코드에서 좋았던" 경험적 파이프라인이지 최적해가 아니다.

코드 생성 — IR을 실제 기계에 착지시킨다

mid-level IR은 무한한 가상 레지스터와 추상 연산 위에 서 있다. 실제 CPU에 착지시키는 백엔드의 책임은 개념적으로 셋으로 나뉜다.

1. Instruction selection — IR 연산을 대상 ISA의 명령으로 바꾼다. 같은 n * 2도 곱셈 명령, 시프트, 주소 계산 명령(x86 lea) 중 무엇이 쌀지는 대상별 비용 모델이 정한다.
2. Register allocation — 무한한 가상 레지스터를 유한한 물리 레지스터에 배정한다. 동시에 살아 있는 값이 레지스터 수를 넘으면 일부를 스택에 내리는 spill이 발생하고, 이것이 최적화 빌드에서도 메모리 접근이 남는 흔한 이유다.
3. Instruction scheduling — 파이프라인과 실행 유닛을 놀리지 않도록 명령 순서를 재배치한다. 왜 순서가 성능을 바꾸는지는 7.1의 의존 체인과 ILP가 다루는 메커니즘 그대로다.

세 문제는 서로 얽혀 있고(선택이 레지스터 압력을 바꾸고, 배정이 스케줄을 제약한다) 각각이 NP-난해한 최적화 문제라, 실전은 휴리스틱이다. 이 챕터에서는 책임의 분해까지만 가져간다 — 특정 ISA의 인코딩은 범위 밖이다.

정확성 계약 — 관찰 가능한 동작만 보존하면 된다

지금까지 "의미를 보존한다"고 말했는데, 정확히는 관찰 가능한 동작(observable behavior)의 보존이다. C/C++의 as-if 규칙이 대표적 정식화다: 프로그램의 관찰 가능한 결과(출력, volatile 접근, 종료 상태 등 언어 명세가 정의한 것)가 같다면, 컴파일러는 내부적으로 무엇이든 할 수 있다. 최적화의 자유는 전부 이 계약에서 나오고, 최적화의 한계도 전부 여기서 나온다. 한계 쪽 사례가 실무 감각과 자주 충돌한다.

• 부동소수점: IEEE 754에서 덧셈은 결합법칙이 성립하지 않는다 — (a + b) + c와 a + (b + c)는 다른 값일 수 있다. 따라서 합산 순서를 바꾸는 재배치(벡터화의 전제이기도 하다)는 기본적으로 금지이고, -ffast-math 같은 플래그는 "그 차이를 관찰하지 않겠다"는 개발자의 계약 변경이다.
• overflow: C에서 부호 있는 정수 overflow는 undefined behavior다. 컴파일러는 "UB는 일어나지 않는다"를 전제로 x + 1 > x를 참으로 접을 수 있다. 반대로 overflow 의미가 정의된 언어(Java의 wrap-around 등)에서는 같은 접기가 불법이다 — 언어 명세가 최적화 가능 범위를 정한다.
• aliasing: 두 포인터·참조가 같은 메모리를 가리킬 수 있으면, 한쪽에 쓰는 순간 다른 쪽으로 읽은 값을 레지스터에 들고 있을 수 없다. "이 둘은 겹치지 않는다"를 증명(또는 restrict처럼 개발자가 약속)하지 못하면 재로드가 남는다.
• 부작용: 호출의 내부를 모르면(분리 컴파일, 동적 디스패치) 그 호출이 무엇이든 바꿀 수 있다고 가정해야 한다. 순수해 보이는 함수 호출이 CSE·DCE되지 않는 이유는 대부분 "순수함을 증명할 수 없어서"다.

실무 관점

"이 분기는 사라질 텐데"가 남아 있는 이유

소스만 보면 접힐 것 같은 검사가 최종 코드에 남아 있다면, 대부분 컴파일러가 필요한 사실을 증명하지 못한 것이다 — 값이 외부 호출 뒤에도 불변임을(aliasing·부작용), 이 경로로만 도달함을(흐름 정보), 호출 대상이 하나임을(디스패치). 최적화는 증명 게임이고, 증명의 재료는 표현이 담은 정보다. 언어 차원에서 불변성·비겹침·가시성을 표현할수록(const, 불변 자료구조, 클로저 범위 축소) 컴파일러의 증명이 쉬워진다는 일반 원칙이 여기서 나온다.

인라이닝은 공짜가 아니다

인라이닝은 호출 오버헤드 제거보다 후속 최적화의 문을 여는 것이 본질 가치다. 그러나 본문 복사는 코드 크기를 늘리고, 늘어난 코드는 명령어 캐시와 파이프라인 프론트엔드를 압박한다 — 7.1의 프론트엔드 병목이 정확히 이 지점이다. aggressive inlining이 마이크로벤치마크에서 이기고 실서비스에서 지는 전형적 구도: 벤치마크는 코드 풋프린트가 작아 i-cache 압력이 드러나지 않는다. 인라이닝 휴리스틱이 크기 예산과 호출 빈도를 함께 보는 이유이고, JIT이 프로파일로 인라이닝을 정하는 것이 유리한 이유다(5.3).

최적화 빌드의 스택 트레이스는 소스와 어긋난다

인라이닝된 함수는 스택 프레임이 없고, 재배치된 명령은 소스 줄 순서와 다르게 실행되며, 죽은 변수는 디버거에서 optimized out으로 보인다. 디버그 정보는 "기계 상태 → 소스 위치"의 근사 사상일 뿐이다. 크래시 리포트의 줄 번호가 이상할 때 의심할 것은 미신이 아니라 이 사상의 손실이고, 릴리스 빌드에 디버그 정보를 함께 생성해 보관하는(strip 후 심볼 서버 보관) 운영 관행이 그 대응이다.

통념: "최적화는 의미를 바꾸지 않으니 항상 켜도 안전하다"

계약을 정확히 읽으면: 최적화는 언어 명세가 관찰 가능하다고 정의한 것만 보존한다. 실행 시간, 메모리 배치, UB에 기댄 코드의 동작, 부동소수점의 비트 단위 재현성(재배치 허용 플래그를 켰다면)은 계약 밖이다. "-O0에서는 되는데 -O2에서 깨진다"의 대부분은 최적화기의 버그가 아니라, 코드가 계약 밖 동작(초기화 안 된 읽기, overflow, aliasing 위반)에 기대고 있었음이 드러난 것이다. 물론 진짜 컴파일러 버그도 존재한다 — 구분하는 방법은 명세를 기준으로 코드의 가정을 검증하는 것이지, 최적화 수준을 낮춰 덮는 것이 아니다.

더 깊이

UB 기반 최적화가 직관과 충돌하는 지점

UB의 원래 취지는 "명세가 정의하지 않는 입력에 대해 구현이 비용을 지불하지 않게 한다"이지만, 현대 컴파일러는 이를 적극적 추론 전제로 쓴다. 유명한 패턴: 포인터를 역참조한 뒤의 null 검사는 "역참조가 UB 없이 지나갔으니 null이 아니다"로 접혀 제거될 수 있다. 검사가 사라진 것을 발견한 개발자에게 이것은 배신처럼 보이지만, 계약상 컴파일러는 일관적이다. LLVM이 poison/freeze 같은 개념으로 UB 값의 전파를 IR 수준에서 정밀하게 규정하려는 것도, 이 추론이 어디까지 허용되는지를 명확히 하려는 노력이다. 실무 방어선은 계약을 검사하는 도구다 — UBSan·ASan 계열 sanitizer를 테스트 빌드에 상시 켜는 것이 "최적화가 이상하다"는 디버깅보다 앞선다.

JIT의 IR — 같은 원리, 다른 예산

이 문서의 원리는 사전(ahead-of-time) 컴파일 기준으로 서술했지만, JIT 컴파일러도 같은 구조(IR·CFG·SSA 기반 최적화)를 쓴다. 다른 것은 예산과 정보다 — JIT은 컴파일 시간이 실행 시간에 청구되므로 싼 패스를 골라야 하고, 대신 실행 중 관찰한 프로파일(실제 타입, 실제 분기 방향)이라는 정적 컴파일러가 갖지 못한 정보로 추측 기반 최적화를 한다. 이 교환의 구조가 5.3의 주제다.

lowering은 계단이다

실전 컴파일러는 IR을 한 번이 아니라 여러 번 낮춘다. Rust는 HIR→MIR→LLVM IR을 거치고(borrow check는 MIR에서), V8의 TurboFan도 여러 층의 표현을 거쳐 기계어에 도달한다. 각 층은 "이 검사·이 최적화는 이 정보가 아직 살아 있는 층에서"라는 배치 문제의 답이다. 언어 특화 검사는 소스 구조가 남은 높은 층에서, 범용 최적화는 중간층에서, 대상 특화는 낮은 층에서 — 산출물이 단계별 인터페이스라는 5.0의 관점이 컴파일러 내부에서도 반복된다.

정리

• IR은 소스 문법과 대상 기계를 분리하는 공유 계약이다. M×N 문제를 M+N으로 줄이고, 모든 패스가 같은 표현 위에서 동작하게 한다.
• CFG는 제어 흐름을, SSA는 값의 흐름을 명시적으로 만든다. SSA의 단일 정의 불변식과 phi 함수는 use-def 추적을 표현 자체에 내장해 분석을 단순화한다.
• 최적화 패스는 "분석이 증명한 사실 → 허용되는 변환 → 보존해야 할 의미"의 삼각형이고, 패스들은 서로의 기회를 만들거나 없애므로 고정된 최적 순서가 없다.
• 최적화의 자유와 한계는 모두 "관찰 가능한 동작 보존" 계약에서 나온다. 부동소수점 재배치, overflow, aliasing, 부작용이 그 경계의 대표 사례다.
• 코드 생성은 instruction selection, register allocation, scheduling으로 분해되고, 각각 대상별 비용 모델 위의 휴리스틱이다.

확인 문제

1. 다음 SSA 조각에서 적용 가능한 최적화를 순서대로 적용하고, 각 단계에서 어떤 분석 사실이 변환을 정당화하는지 밝혀라.

entry:
  a1 ← 4
  b1 ← a1 * 2
  c1 ← x + b1
  d1 ← x + b1
  branch (b1 < 0) ? neg : merge
neg:
  e1 ← c1 * 2
  jump merge
merge:
  f1 ← φ(entry → c1, neg → e1)
  return f1 + d1

정답과 해설

(1) constant propagation·folding: a1 = 4가 상수이므로 b1 = 4 * 2 = 8. 근거는 SSA에서 a1의 정의가 유일하고 상수라는 사실. (2) b1 = 8이 전파되면 분기 조건 8 < 0은 거짓으로 접히고, neg 블록은 도달 불가능해져 제거된다(분기 접기 + 도달성 분석). φ는 남은 유입이 entry 하나뿐이므로 f1 = c1으로 단순화된다. (3) CSE: c1과 d1은 같은 피연산자(x, b1)의 같은 순수 연산이고 사이에 x를 바꾸는 정의가 없으므로 d1을 c1 재사용으로 치환. (4) DCE: 이제 d1, a1 정의는 읽는 곳이 없으면 제거. 최종적으로 c1 ← x + 8; return c1 + c1 수준까지 줄어든다. 각 변환이 "SSA가 공짜로 주는 use-def 사실"에 기대고 있음을 보는 것이 핵심이다.

2. 동료가 "이 함수는 같은 computeTax(order)를 두 번 호출하니 컴파일러가 알아서 한 번으로 합칠 것"이라고 말한다. 컴파일러가 이 CSE를 수행하기 위해 증명해야 하는 것들을 나열하고, 증명이 실패하는 현실적 시나리오를 두 가지 제시하라.

정답과 해설

증명할 것: 두 호출이 같은 값을 반환하고(호출이 순수 — 전역 상태·I/O에 의존하지 않고 변경도 하지 않음), 두 호출 사이에서 인자 order가 가리키는 데이터가 변하지 않으며(aliasing — 사이의 어떤 쓰기도 order와 겹치지 않음), 호출 대상이 확정된다(동적 디스패치·함수 포인터가 아님). 실패 시나리오: (1) computeTax가 다른 컴파일 단위에 있거나 인터페이스 뒤에 있어 본문을 볼 수 없다 — 부작용이 없음을 증명할 수 없으므로 두 호출 모두 보존해야 한다. (2) 두 호출 사이에 다른 객체를 수정하는 코드가 있는데 그 객체가 order와 겹치지 않음을 컴파일러가 증명하지 못한다. 실무 함의: 합쳐지길 원하면 호출 결과를 지역 변수에 직접 담는 것이 컴파일러 증명에 기대는 것보다 확실하다.

3. 수치 시뮬레이션 팀이 빌드에 -ffast-math를 켠 뒤 "결과가 이전 빌드와 마지막 자릿수에서 다르고, 실행마다는 동일하다"고 보고했다. 이 현상을 이 문서의 계약 관점에서 설명하고, 이 플래그를 켜도 되는지 판단하는 기준을 제시하라.

정답과 해설

-ffast-math는 IEEE 754의 엄격한 의미(비결합성, NaN·무한대 처리 등)를 관찰 대상에서 제외하겠다는 계약 변경이다. 컴파일러는 이제 합산 재배치·벡터화·역수 곱 치환 같은 대수적 변환을 할 수 있고, 반올림이 누적되는 순서가 달라져 결과의 마지막 자릿수가 이전 빌드와 달라진다. 같은 바이너리는 같은 순서로 계산하므로 실행 간에는 결정적이다. 판단 기준: 결과의 요구 정밀도가 반올림 오차 재배치에 둔감한가(오차 분석 또는 기준 결과 대비 허용 오차 검증), NaN·무한대가 정상 데이터 흐름에 등장하는가(등장하면 위험 — fast-math는 이들의 의미도 바꾼다), 그리고 비트 단위 재현성이 요구사항인가(회귀 테스트·감사 요건이 있으면 불가). "빨라지니 켠다"가 아니라 "무엇을 관찰하지 않기로 했는지"를 명시적으로 결정하는 문제다.

참고 자료

• Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, F. Kenneth Zadeck, Efficiently Computing Static Single Assignment Form and the Control Dependence Graph (TOPLAS 1991) — SSA 구성의 원전. phi 배치가 지배 경계(dominance frontier)로 결정되는 구조를 확인한다.
• Keith D. Cooper, Linda Torczon, Engineering a Compiler 3rd ed. (2022), Ch. 8–13 — 최적화 패스와 코드 생성 3책임의 구현 관점 표준 서술.
• LLVM Project, LLVM Language Reference Manual — 산업용 mid-level IR의 실제 계약. undefined behavior, poison 값의 정밀한 규정을 원문으로 확인한다.
• Chris Lattner, What Every C Programmer Should Know About Undefined Behavior (LLVM Blog, 2011) — UB가 최적화의 전제로 쓰이는 방식과 그 귀결을 컴파일러 구현자 관점에서 설명한 1차 자료.
• LLVM Project, Kaleidoscope Tutorial — 작은 언어를 LLVM IR로 낮추고 최적화 패스를 붙여 보는 공식 튜토리얼. 이 문서의 축약 IR을 실제 IR로 확장해 볼 때 사용한다.