중간언어는 원시언어와 목적코드 사이에 두는 표현으로, 컴파일러를 앞단과 뒷단으로 나누는 경계다. 앞단은 소스를 중간언어로 바꾸고 뒷단은 중간언어를 기계어로 바꾼다.
왜 한 단계를 더 두는지는 언어 m개를 기계 n종에 올리는 상황을 생각하면 분명하다. 직접 번역하면 번역기가 m × n개 필요하지만, 중간언어를 거치면 앞단 m개와 뒷단 n개, 합쳐서 m + n개로 끝난다. 이것 말고도 얻는 것이 있다.
- 컴파일러를 기능적으로 독립적인 모듈로 나눌 수 있다
- 원시 프로그램의 이식성이 올라간다
- 고급언어와 저급 목적코드 사이의 의미적 간극을 이어 준다
- 기계와 독립적인 최적화를 할 수 있다. 기계코드로 바뀐 뒤에 하는 것보다 훨씬 효율적이다
- 중간코드를 인터프리터로 직접 실행할 수 있다
대가도 있다. 목적코드로 곧장 번역하는 것보다 비효율적인 코드가 나온다. 중간 단계마다 정보가 손실되기 때문이고, 단일 패스 컴파일러가 중간코드를 두지 않는 이유이기도 하다.
형태는 여러 가지가 있지만 대표적인 것은 둘이다. 후위표현과 3-주소 코드이고, 둘의 차이는 최적화를 할 수 있느냐에서 갈린다.
후위표현은 구문트리를 선형화한 것이다. 부모 노드가 자식 노드들 바로 뒤에 오도록 나열한다.
일반형: e₁ e₂ … eₖ Q (Q는 k항 연산자)
b * c - d → b c * d -괄호가 필요 없고 스택 하나로 계산할 수 있다. 피연산자를 만나면 push하고 연산자를 만나면 필요한 만큼 pop해서 결과를 push한다. 원시 프로그램에서 변환하기도 쉽고 빠르다. FORTRAN 컴파일러가 산술식 중간코드로 썼고, BASIC 같은 인터프리터가 널리 사용했다.
스택 기반 가상머신의 바이트코드가 곧 후위표현이다. 교재의 예제 A := -B * (C + D)를 CPython으로 컴파일해 보면 그대로 드러난다.
후위표현 CPython 바이트코드 ───────── ────────────────── B LOAD_NAME B uminus UNARY_NEGATIVE C LOAD_NAME C D LOAD_NAME D + BINARY_OP 0 (+) * BINARY_OP 5 (*) A := STORE_NAME A토큰 하나하나가 일대일로 대응한다. 후위표현을 배운다는 것은 스택 머신 바이트코드를 배우는 것과 같다.
대신 코드를 옮길 수 없다. 하나의 후위표현이 다른 후위표현을 선형으로 내포하고 있어서, 중간의 일부를 떼어 다른 곳으로 옮기면 스택 균형이 깨진다. 위 예에서 C D +만 루프 밖으로 빼내려 해도 그 결과를 어디에 둘지 이름이 없다. 모든 중간 결과가 스택 위 익명의 자리에 있기 때문이다. 그래서 최적화에는 부적합하다.
3-주소 코드
Section titled “3-주소 코드”3-주소 코드는 중간 결과에 이름을 준다. 일반형은 이렇다.
A := B op C세 주소 중 둘은 피연산자, 하나는 결과를 담는다. 문 하나에 연산자 하나만 허용하므로, 복합식은 컴파일러가 만든 임시변수로 쪼개진다.
A := -B * (C + D)
T1 := -BT2 := C + DT3 := T1 * T2A := T3이제 T2 := C + D는 독립된 한 줄이고 결과에 T2라는 이름이 있다. 루프 불변식이면 루프 밖으로 빼내면 되고, 같은 식이 두 번 나오면 하나를 지우고 T2를 재사용하면 된다. 코드를 광범위하게 최적화하는 컴파일러가 3-주소 코드를 쓰는 이유다.
| 후위표현 | 3-주소 코드 | |
|---|---|---|
| 중간 결과 | 스택 위 익명 | 이름 붙은 임시변수 |
| 문당 연산자 | 제한 없음 | 하나 |
| 코드 이동 | 불가능 | 가능 |
| 최적화 | 부적합 | 적합 |
| 생성 비용 | 싸다 | 임시변수 관리 필요 |
| 크기 | 작다 | 크다 |
| 실행 | 스택 머신에서 직접 | 레지스터 할당 필요 |
| 실제 사례 | CPython·JVM 바이트코드 | LLVM IR, GCC GIMPLE |
문의 종류는 대략 이 정도다.
A := B op C 이항 연산A := op B 단항 연산A := B 복사goto L 무조건 분기if A relop B goto L 조건 분기param A₁ … param Aₙ / call P, n 프로시저 호출A := B[i] / A[i] := B 첨자 접근A := &B / A := *B / *A := B 주소·포인터분기가 goto와 레이블로 표현되므로 if나 while 같은 구조가 사라지고 제어 흐름이 평평해진다. 이 형태라야 제어 흐름 그래프를 만들 수 있고, 그 위에서 데이터 흐름 분석을 할 수 있다.
구현 형태 셋
Section titled “구현 형태 셋”추상적인 3-주소 코드를 실제 자료구조로 만드는 방법이 세 가지다. A := -B * (C + D)로 비교하면 이렇다.
triple은 <op> <피연산자1> <피연산자2> 세 필드를 갖고, 결과는 그 triple의 번호로 지칭한다.
번호 op 피연산자1 피연산자2(0) uminus B(1) + C D(2) * (0) (1)(3) := A (2)임시변수가 기호표에 들어가지 않아 공간을 아낀다. 하지만 코드를 옮기면 번호가 바뀌고, 그 번호를 참조하던 다른 triple도 전부 고쳐야 한다. 최적화에 불편하다.
간접 triple은 triple을 그대로 두고 수행 순서를 별도의 표로 뺀다.
수행순서 번호 op 피연산자1 피연산자21. (0) (0) uminus B2. (1) (1) + C D3. (2) (2) * (0) (1)4. (3) (3) := A (2)코드를 옮길 때 순서표만 바꾸면 되고 triple 자체는 건드리지 않는다. triple의 단점을 보완한 형태다.
quadruple은 <op> <피연산자1> <피연산자2> <결과> 네 필드를 갖는다.
번호 op 피연산자1 피연산자2 결과(0) uminus B T1(1) + C D T2(2) * T1 T2 T3(3) := T3 A결과 주소를 명시적으로 갖고 있어 코드 이동이 자유롭다. 최적화에 가장 알맞다. 대신 임시변수를 관리해야 한다.
LLVM IR이 이것이다
Section titled “LLVM IR이 이것이다”A = -B * (C + D)를 C로 쓰고 LLVM IR로 뽑으면 quadruple 형태가 그대로 나온다.
define i32 @f(i32 %0, i32 %1, i32 %2) { %4 = add nsw i32 %2, %1 ; T1 := D + C %5 = mul i32 %0, %4 ; T2 := B * T1 %6 = sub i32 0, %5 ; T3 := 0 - T2 ret i32 %6}%4, %5, %6이 교재의 T1, T2, T3이다. 명령마다 연산자 하나, 피연산자 둘, 결과 하나다. 각 임시 이름에 대입이 정확히 한 번만 일어나는 형태를 SSA(정적 단일 대입)라고 하고, 현대 컴파일러의 IR은 대부분 이 형태다. 임시변수가 재대입되지 않으면 “이 값이 어디서 왔는가”를 추적하기 쉬워 최적화가 간단해진다.
덧붙여 위 출력은 -B * (C+D)를 -(B * (C+D))로 바꿔 놓았다. IR 위에서 대수적 재결합이 이미 일어난 것이고, 이것이 “기계와 독립적인 최적화”의 실례다.
IR을 어느 수준에 둘지는 절충의 문제다. 너무 고급이면 뒷단이 할 일이 많아지고, 너무 저급이면 기계 독립성을 잃는다. LLVM IR이 타입을 갖고 있으면서도 레지스터 개수는 무한하다고 가정하는 것이 그 절충이다. 3-주소 코드는 식 하나마다 임시를 만들고 SSA는 대입마다 새 이름을 만들기 때문에, 이 임시들을 실제 레지스터로 접어 넣는 레지스터 할당이 뒷단에서 가장 무거운 작업 중 하나가 된다.
구문지시적 변환
Section titled “구문지시적 변환”중간코드를 생성하는 방법이 구문지시적 변환이다. 문법의 각 생성규칙에 의미수행 규칙(semantic action)을 붙여 두고, 파서가 그 규칙을 사용할 때 함께 실행한다.
E → E⁽¹⁾ + E⁽²⁾ { E.VAL := E⁽¹⁾.VAL + E⁽²⁾.VAL }{ } 안이 의미수행 규칙이고, X.VAL처럼 문법기호에 붙은 값을 그 기호의 속성이라고 한다. 실행 시점은 파싱 방향에 따라 다르다. 상향식에서는 ABC가 X로 reduce될 때, 하향식에서는 X가 확장될 때다.
속성은 값이 흐르는 방향에 따라 둘로 나뉜다.
- 합성 속성(synthesized): 오른쪽 자식들의 값으로 왼쪽 부모의 값을 정한다. 위 예가 그렇다. 값이 트리 위로 올라간다
- 상속 속성(inherited):
A → XYZ { Y.VAL := 2 * A.VAL }처럼 부모나 형제의 값으로 자식의 값을 정한다. 값이 아래로 내려간다
대부분의 언어 구조는 합성 속성으로 충분하다. 상향식 파서와 궁합이 맞기 때문이다.
구현은 LR 파서의 스택을 활용한다. 상태 스택과 나란히 값 스택 VAL을 두면 된다.
STATE VAL ───── ─────[TOP] Z Z.VAL[TOP-1] Y Y.VAL[TOP-2] X X.VAL
A → XYZ 로 reduce 후
STATE VAL ───── ─────[TOP] A A.VALXYZ가 A로 reduce될 때 Z.VAL은 VAL[TOP], Y.VAL은 VAL[TOP-1], X.VAL은 VAL[TOP-2]에 있다. 이걸로 A.VAL을 계산해 VAL[TOP]에 남긴다. yacc/bison의 $$, $1, $2가 이 스택 슬롯이고, CPython PEG 문법의 { _PyAST_BinOp(a, Add, b, EXTRA) } 액션도 같은 것이다.
실제 컴파일러의 IR 단계
Section titled “실제 컴파일러의 IR 단계”현대 컴파일러는 IR을 하나만 두지 않는다. CPython은 AST에서 바이트코드까지 가는 사이에 두 형태를 더 거친다.
AST │ codegen_visit_*() ▼의사 명령어 시퀀스 ← 바이트코드와 비슷하지만 더 추상적 │ _PyCfg_FromInstructionSequence() ▼제어 흐름 그래프(CFG) ← 최적화는 여기서 (flowgraph.c 4,261줄) │ _PyCfg_OptimizedCfgToInstructionSequence() ▼명령어 시퀀스 │ assemble.c ▼바이트코드 (PyCodeObject)의사 명령어를 따로 두는 이유는 점프 대상을 아직 정하지 못하기 때문이다. 앞으로 뛰는 분기는 목적지가 아직 생성되지 않았으므로, 레이블로 남겨 두고 나중에 실제 오프셋으로 채운다. 3-주소 코드에서 goto L을 쓰던 것과 같은 이유다.
CFG로 바꾸는 이유는 최적화 때문이다. 명령어를 기본 블록으로 묶고 블록 간 흐름을 간선으로 만들면 도달 불가능한 코드 제거, 점프 단순화 같은 변환을 할 수 있다. 선형 코드로는 못 하고 그래프로는 되는 일이 최적화이고, 후위표현이 최적화에 부적합했던 이유와 같은 맥락이다.
참고