컴파일러는 소스를 어떻게 바꾸는가: IR, 코드 생성, 최적화의 전체 흐름

이 글은 개인 학습 아카이브에 보관된 컴파일러 강의 PDF·슬라이드·코드 예제를 교차 검토해 새로 구성한 학습 노트입니다. 오래된 표기, 오탈자, 실행되지 않는 예시는 본문에서 별도로 바로잡았으며 원본 파일이나 내부 경로는 공개하지 않습니다.

IR은 front end와 back end 사이의 계약이다

compiler는 source를 곧바로 machine instruction으로 바꾸지 않는 경우가 많다. lexer와 parser가 구조를 만들고 semantic analysis가 이름과 type을 확인한 뒤, source syntax와 target ISA 사이에 하나 이상의 intermediate representation을 둔다.

source
  -> lexical analysis
  -> parsing
  -> semantic analysis
  -> high-level IR
  -> optimization and lowering
  -> low-level or machine IR
  -> instruction selection and register allocation
  -> target code

아카이브 강의는 front end를 source-language dependent, back end를 target-machine dependent라고 나누고 intermediate language가 둘을 잇는다고 설명한다. 이 구조는 modularity와 retargetability를 높이고, source와 machine의 semantic gap을 단계적으로 줄이며, machine-independent optimization을 가능하게 한다. 반면 IR을 만들고 여러 pass를 실행하는 compile-time cost도 생긴다.

현대적으로는 optimization을 별도 middle end로 부르는 편이 자연스럽고, parser output이 바로 code generator로 간다고 단정하기보다 typed AST나 semantic IR을 거친다고 설명하는 편이 정확하다.

Postfix: 괄호 없이 계산 순서를 적기

infix a+b*c는 postfix에서 a b c * +가 된다. operand가 operator보다 먼저 오므로 괄호 없이 evaluation order를 표현하고 value stack으로 실행할 수 있다.

아카이브에는 이름의 철자가 잘못 적혀 있고 Polish notation과 postfix가 섞여 있다. Polish notation은 prefix, postfix는 Reverse Polish notation으로 구분하는 것이 정확하다. infix를 postfix로 변환할 때는 operator stack을 사용하지만 postfix를 실행할 때 핵심은 operand/value stack이다.

postfix가 optimization에 부적합하다는 절대적 표현도 완화해야 한다. 최적화할 수 없는 것은 아니지만 explicit result name, def-use edge, control-flow structure가 있는 SSA나 graph IR보다 분석과 code motion이 불편하다.

Three-address code와 세 가지 record

a = b * (c + d)

t1 := c + d
t2 := b * t1
a  := t2

three-address code는 복잡한 expression을 작은 instruction으로 분해한다. 이름과 달리 모든 instruction이 항상 두 operand와 하나의 result를 갖는 것은 아니다. copy, unary operation, branch, call, return처럼 형태가 다른 instruction도 포함한다.

아카이브는 triple을 optimization에 부적합하다고 분류하지만 “불가능”하지는 않다. 표현을 이동할 때 위치 기반 reference를 유지하는 비용이 큰 것이 핵심 차이다.

한 compiler 안에도 여러 IR이 있다

낮은 수준 list IR의 archived 예는 다음과 같은 모양이다.

(set (reg:SI 69)
     (mem:SI (plus:SI (reg:SI 65) (const_int -4))))

(set (reg:SI 70)
     (mem:SI (plus:SI (reg:SI 65) (const_int -8))))

(set (reg:SI 68)
     (plus:SI (reg:SI 69) (reg:SI 70)))

(set (mem:SF (plus:SI (reg:SI 65) (const_int -12)))
     (float:SF (reg:SI 68)))

SI와 SF는 각각 integer와 single-float machine mode를 뜻한다. base register의 두 offset에서 값을 읽고 더한 다음 float으로 바꾸어 다른 offset에 저장한다.

이 예를 “현대 GNU compiler의 유일한 IR”로 소개하면 낡은 설명이 된다. 현대 compiler는 source에 가까운 tree, SSA 기반 middle-level IR, target에 가까운 register-transfer 또는 machine IR 등 여러 층을 사용한다. 낮은 수준 IR 하나는 그 pipeline의 한 단계다.

아카이브가 IL_S와 IL_T로 부른 구조도 같은 생각을 담는다.

source
  -> source-oriented high-level IR
  -> lowering
  -> target-oriented low-level IR
  -> target

IL_S와 IL_T 자체는 보편적인 표준 명칭이 아니므로 high-level, mid-level/SSA, low-level 또는 machine IR이라는 현대 용어와 함께 설명하는 편이 좋다.

Tree IR와 virtual-machine code

parse tree는 grammar production을 충실히 보존한다. AST는 문법의 terminal/nonterminal 구분을 그대로 나열하기보다 operation과 semantic entity를 중심으로 재구성한다. archived 설명 중 “AST가 terminal과 nonterminal node를 지정한다”는 부분은 parse tree와 AST의 책임을 뒤섞는다.

역사적 tree IR 이름들은 당시 compiler 설계를 보여 주지만 오늘의 핵심은 typed AST에서 data-flow-friendly IR로 내려가는 과정이다.

virtual-machine code는 다른 축의 IR이다. stack-based P-code machine은 code area, stack, heap, constant area와 PC, SP, frame/base pointer 같은 abstract register를 둔다. 다른 archived VM instruction은 다음 범주를 보여 준다.

• unary: not, neg
• binary: add, sub
• stack/data: load, store, load constant
• control: unconditional, true, false jump
• checks: upper/lower bound
• address: indexed address, indirect store
• procedure: call, return

JVM bytecode는 typed operation iadd, fadd, stack operation pop2와 class, array, exception 관련 instruction을 갖고 interpreter 또는 JIT compiler가 실행한다. “abstract machine은 general register가 없다”거나 “network로 보내기 위해 반드시 작아야 한다”는 문장은 모든 VM의 정의가 아니라 early stack VM과 초기 Java 배포 맥락의 단순화다.

Syntax-directed translation과 attribute

syntax-directed translation은 production에 semantic action을 붙여 parse와 함께 value, AST, symbol information, IR을 만든다.

L -> E $       { print(E.val) }
E -> E1 + T    { E.val = E1.val + T.val }
E -> T         { E.val = T.val }
T -> T1 * F    { T.val = T1.val * F.val }
T -> F         { T.val = F.val }
F -> ( E )     { F.val = E.val }
F -> digit     { F.val = digit.lexval }

synthesized attribute는 child의 정보에서 parent 값을 만든다.

A.attr = f(X.attr, Y.attr, Z.attr)

inherited attribute는 parent나 sibling에서 child로 context를 전달한다.

Y.attr = f(A.attr, X.attr, Z.attr)

archived inherited example의 A,attr는 A.attr 오탈자다. 또한 syntax-directed definition과 semantic action을 production 사이에 배치하는 translation scheme 용어가 섞여 있다. 위 계산기처럼 synthesized attribute만 쓰는 경우 bottom-up reduction에서 자연스럽게 평가할 수 있다.

Basic block과 control-flow graph

basic block은 중간 진입이나 중간 이탈 없이 처음부터 끝까지 순서대로 실행되는 instruction sequence다. leader를 찾고 leader부터 다음 leader 직전까지 묶는다.

leader는 보통:

1. 첫 instruction
2. branch target
3. conditional뿐 아니라 모든 jump 다음 instruction

이다. archived 목록은 unconditional jump 뒤 instruction을 빠뜨렸다. 실행상 도달 불가능하더라도 block boundary와 CFG construction에는 leader가 될 수 있다.

다음 loop를 낮춰 보자.

for (i = 0; i < N; i++)
    statement1;
statement2;

B1: i = 0; goto L2
B2: L1: statement1; i++
B3: L2: if (i < N) goto L1
B4: statement2

CFG edge는 entry -> B1 -> B3, B3의 true edge는 B2, false/fallthrough는 B4, B2는 다시 B3로 간다. explicit branch target뿐 아니라 unconditional jump로 끝나지 않은 block의 lexical successor에도 fallthrough edge를 추가한다.

Local optimization은 legality가 먼저다

common subexpression elimination:

x = a + b + c;
y = b + c + d;
z = (b + c) * e;

b+c가 세 번 나타나는 위 코드는 다음처럼 바꿀 수 있다.

t = b + c;
x = a + t;
y = t + d;
z = t * e;

이제 b+c를 한 번만 계산한다. 단, 사이에 b나 c가 재정의되지 않고 aliasing, exception, integer overflow, floating-point reassociation 규칙이 변환을 허용해야 한다.

constant propagation과 folding:

i = 2
t1 = 4 * i

=> t1 = 4 * 2
=> t1 = 8

algebraic simplification의 x=y+0, x=1*y도 integer에서는 단순해 보이지만 floating point의 signed zero, NaN, exception과 언어의 overflow/undefined behavior를 고려해야 한다.

strength reduction의 archived 예는 특히 조건을 밝혀야 한다.

• b ** 2 -> b * b: operand evaluation count와 side effect가 같아야 한다.
• 3 * a -> a + a + a: 현대 CPU에서 반드시 더 빠르지 않다.
• a / 5 -> a * 0.2: integer semantics가 달라지고 floating-point rounding도 다를 수 있다.
• signed a / 4 -> a >> 2: 음수 rounding 규칙과 arithmetic shift가 일치해야 한다.

t1=4*j+1 뒤의 t7=t1-4*j를 1로 바꾸는 substitution도 중간에 j와 t1이 바뀌지 않는다는 data-flow proof가 필요하다.

Loop optimization의 네 가지 함정

강의는 “코드 10%가 실행 시간 90%를 차지한다”는 경험칙으로 loop를 강조한다. 이는 측정 대신 쓸 법칙이 아니라 hot path를 우선 보라는 heuristic이다.

Loop-invariant code motion

원래 loop:

for (i = 0; i < N; i++)
    c[i] = 2 * (p - q) * (n - i + 1) / (sqr(n) + n);

hoisting 후보의 형태:

t1 = 2 * (p - q);
t2 = n + 1;
t3 = sqr(n) + n;
for (i = 0; i < N; i++)
    c[i] = t1 * (t2 - i) / t3;

archived 변환은 loop 시작을 i=1로 바꾸어 c[0] 계산을 잃는다. 이것은 성능 문제가 아니라 semantic bug다. p, q, n이 loop에서 변하지 않고 sqr가 pure하며 hoisting이 exception timing을 부당하게 바꾸지 않는다는 조건도 필요하다.

이 후보도 자동으로 동치인 것은 아니다. 원래의 n - i + 1을 (n + 1) - i로 재결합하면 bounded signed integer에서는 원래 계산이 범위 안이어도 n + 1이 overflow할 수 있고, floating point에서는 rounding이 달라질 수 있다. 따라서 정수 범위가 증명되고 언어가 해당 floating-point 재결합을 허용할 때만 이 형태를 사용할 수 있다.

Loop unrolling

for (i = 0; i + 1 < N; i += 2) {
    a[i] = 0;
    a[i + 1] = 0;
}
for (; i < N; i++)
    a[i] = 0;

archived 두 배 unroll은 N이 홀수일 때 a[i+1]가 범위를 벗어난다. cleanup iteration이나 masked/vector tail이 필요하다.

Loop fusion

같은 bounds의 두 loop를 합치면 traversal overhead와 cache traffic을 줄일 수 있다. 하지만 두 loop 사이의 true, anti, output dependency와 alias를 검사해야 한다. 모양이 같다는 이유만으로 합칠 수 없다.

Count toward zero

i=N-1에서 0으로 세면 특정 ISA에서 compare가 간단할 수 있다. 현대 CPU에서 항상 빠르지 않으며 unsigned index로 i>=0을 쓰면 underflow 뒤 무한 loop가 된다.

Global optimization과 join의 조건

global pass는 여러 basic block을 가로질러 data-flow fact를 계산한다.

• cross-block common subexpression elimination
• global constant propagation and folding
• unreachable-code elimination
• branch simplification
• jump threading과 consecutive jump shortening

여러 predecessor가 b*i를 계산한다고 해서 join에서 임시 변수 하나를 바로 읽을 수 있는 것은 아니다. join으로 들어오는 모든 경로가 compatible value를 정의해야 한다. SSA에서는 dominance와 phi node, value numbering으로 이 조건을 명시한다.

a = 1
b = 2
t = a * b
if (t == 2) ...

는 constant propagation으로 true branch만 남길 수 있다. archived pseudo-code의 if (t = 2)를 C로 읽으면 comparison이 아니라 assignment이므로 ==로 고쳐야 한다.

if (true) A else B -> A, empty true branch를 condition inversion으로 단순화, goto A 뒤 A가 곧 goto B이면 B로 직접 연결하는 변환도 CFG와 observable behavior가 허용할 때 적용한다.

Machine-dependent optimization

load r1, b
store r1, a
load r1, a    // removable only if r1 and memory meaning are unchanged
add r1, 1
store r1, c

redundant load 제거는 register clobber, alias, volatile/atomic memory를 확인해야 한다. load; add 1; store를 inc로 바꾸는 것도 target ISA에 해당 instruction이 있고 condition flags, width, atomicity가 원래 sequence와 같을 때만 합법이다.

register allocation은 어느 program value를 어느 시점에 register에 둘지 고르는 문제이고, register assignment는 선택된 value를 실제 physical register에 배치하는 문제다. evaluation order는 live temporary 수와 spill을 줄이도록 바꿀 수 있다.

peephole optimizer는 작은 target-code window를 움직이며 redundant instruction, unreachable sequence, algebraic pattern, machine idiom을 더 나은 sequence로 바꾼다. pattern이 닮았다는 사실보다 target semantics와 cost model이 우선한다.

최적화의 정의는 “더 빠르게”보다 엄격하다

optimization은 관찰 가능한 의미를 보존하는 rewrite다. speed 외에도 code size, memory traffic, energy, startup latency, compile time이 목표가 될 수 있고 서로 trade-off를 만든다.

아카이브 예제는 transformation의 모양을 배우기에 좋지만 그대로 외우면 i=1 bug, odd-length out-of-bounds, integer/float 의미 변경, 잘못된 comparison, flag 변화 같은 실제 오류를 만든다. 현대 compiler가 legality analysis와 profitability model을 분리하는 이유다. 먼저 변환해도 되는지 증명하고, 그 다음 목표 machine에서 이득인지 판단한다.