CHAPTER 8

Intermediate Representations — IR의 형태와 종류

Douglas Thain, Introduction to Compilers and Language Design (2nd ed., 2023) · pp.119–134

📌단원 개요

source language의 추상적 구조와 target assembly language의 구체적 구조 사이에 놓이는 intermediate representation (IR)을 다룬다. 다양한 IR 종류를 추상화 수준이 높은 것부터 낮은 것 순으로 살펴보고, 각각의 장단점을 비교한다.

💡 이 장의 큰 그림 — 추상화 수준 사다리

AST → source에 가장 가까운 IR (high abstraction)
DAG → AST에서 한 단계 단순화, 공통 부분식 공유 가능
Control Flow Graph (CFG) → basic block 단위로 제어 흐름 표현
SSA form → 변수마다 version number, 복잡한 optimization용
Linear IR → three-address code, assembly에 근접
Stack Machine IR → register 없이 stack만 사용, 가장 compact

⭐ 시험 포인트 — IR이 갖춰야 할 성질

구조가 simple & regular → optimization, analysis, code generation이 쉬움
modular compiler: 각 optimization/analysis 도구가 같은 IR을 소비·생산 → 순서 조합이 자유로움
external format(text)으로 파일에 쓸 수 있어 무관한 도구 간 교환 가능 (사람이 읽기 쉽진 않음)
메모리에 적재되면 data structure로 표현 → 구조를 순회하는 알고리즘 용이
일부 컴파일러는 여러 IR을 추상화가 점점 낮아지는 층(layer)으로 사용

8.1Introduction

대부분의 production compiler는 source language와 target assembly language 사이에 위치하는 IR을 사용한다.

💡 IR이 필요한 이유

IR은 simple하고 regular한 구조로 설계되어 optimization·analysis·efficient code generation을 돕는다.
modular compiler는 각 optimization/analysis tool을 같은 IR을 소비하고 생산하는 별도 module로 구현 → optimization들을 다른 순서로 쉽게 선택·조합(compose).
IR은 보통 text 형태의 external format을 가져 파일로 출력 가능 → 무관한 tool 사이에서 교환된다.
메모리에 적재되면 data structure로 표현된다.

IR의 종류는 다양하다. 어떤 것은 지금까지 쓴 AST에 매우 가깝고, 어떤 것은 target assembly language와 매우 가깝다. 일부 compiler는 추상화 수준이 점점 낮아지는 여러 IR을 동시에 쓰기도 한다.

8.2Abstract Syntax Tree

AST 자체도 IR로 쓸 수 있다 — 단, 큰 optimization 없이 그냥 assembly language를 emit하는 것이 목표일 때만.

💡 AST를 IR로 쓰는 방법

typechecking이 끝나면 strength reduction, constant folding 같은 단순 optimization을 AST 자체에 적용할 수 있다.
assembly language 생성: AST를 post-order traversal 하면서 각 node마다 몇 개의 assembly instruction을 emit한다.
(교재 각주) 한 학기 과정에서 project compiler를 구현할 때 시간이 제한적이므로 이 방식을 사용한다.

⚠️ 주의 — production compiler에서 AST는 좋은 IR이 아니다

구조가 너무 풍부(too rich)하다 → 각 node가 너무 많은 option과 substructure를 가짐.
예: 하나의 addition node가 값의 type에 따라 integer addition / floating point addition / boolean-or / string concatenation 중 무엇이든 될 수 있다.
이로 인해 robust transformation과 external representation 생성이 어렵다 → 더 low-level인 표현이 필요하다.

참고: DAG Data Structure 정의 (Figure 8.1)

이후 DAG 절에서 쓸 자료구조 정의. node 종류가 많고, 각각의 의미가 명시적이다.

Figure 8.1 — Sample DAG Data Structure Definition

typedef enum {
     DAG_ASSIGN,
     DAG_DEREF,
     DAG_IADD,
     DAG_IMUL,
     ...
     DAG_NAME,
     DAG_FLOAT_VALUE,
     DAG_INTEGER_VALUE
} dag_kind_t;

struct dag_node {
     dag_kind_t kind;
     struct dag_node *left;
     struct dag_node *right;
     union {
          const char *name;
          double float_value;
          int integer_value;
     } u;
};

8.3Directed Acyclic Graph

DAG는 AST에서 한 단계 단순화된 표현이다. 임의의 graph 구조를 가질 수 있고, 개별 node는 크게 단순화되어 있다.

💡 DAG vs AST

DAG는 AST와 비슷하지만 arbitrary graph structure를 가질 수 있다(공유 가능).
개별 node는 크게 단순화 → 각 node의 type과 value 외에는 보조 정보가 거의 없다.
대신 node type 수가 많아진다 — 각 type이 목적에 대해 explicit해야 하기 때문.

예: `x=(a+10)*(a+10)` 의 AST

AST는 syntactic structure를 그대로 담는다.

ASSIGN / \ x MUL / \ ADD ADD / \ / \ a 10 a 10

typechecking 후의 DAG

a가 floating point 값임을 알게 되면 10은 floating point 연산 전에 float로 변환되어야 한다. 또한 a+10은 한 번만 계산되고 그 결과 값이 두 번 재사용된다. 새 node로 integer-to-float 변환을 하는 ITOF, floating point 연산을 하는 FADD·FMUL이 도입된다.

ASSIGN / \ x FMUL | FADD / \ a ITOF | 10

⭐ 시험 포인트 — DAG의 핵심 두 가지

type-specific node: AST의 모호한 ADD 대신, type이 결정된 FADD/IADD/FMUL/IMUL/ITOF 등 명시적 node를 쓴다.
공통 부분식 공유(sharing): a+10처럼 동일한 부분식은 한 번만 계산되고 결과가 여러 부모에서 공유된다(그래서 acyclic graph).

주소 계산(address computation)의 표현 — `x=a[i]`

array lookup의 AST는 단순하다.

ASSIGN / \ x LOOKUP / \ a i

그러나 실제 array lookup은 array a의 시작 주소에, index i에 객체 크기(symbol table을 참조해 결정, 여기선 4)를 곱한 값을 더해 이루어진다. DAG로는 다음처럼 더 자세히 표현한다.

ASSIGN / \ x DEREF | IADD / \ a IMUL / \ i 4

code generation 직전 — local variable 주소까지 확장

code generation 마지막 단계에서, local variable의 주소 계산까지 DAG에 포함시킬 수 있다. 예: a와 i가 frame pointer FP로부터 각각 16, 20 byte 떨어진 stack에 저장된다면 다음처럼 확장된다.

ASSIGN / \ x DEREF | IADD / \ DEREF IMUL | / \ IADD DEREF 4 / \ | FP 16 IADD / \ FP 20

value-number method — AST로부터 DAG 만들기

💡 value-number method

각 entry가 DAG node type과 child node들의 array index로 구성된 array를 만든다.
새 node를 추가하려 할 때마다 array에서 matching node를 검색 → 있으면 재사용(re-use)해 중복을 피한다.
DAG는 AST를 post-order traversal 하면서 각 element를 array에 추가해 구성한다.

위 DAG (x=(a+10)*(a+10), float 버전)를 value-number array로 나타내면 다음과 같다.

#	Type	Left	Right	Value
0	NAME			x
1	NAME			a
2	INT			10
3	ITOF	2
4	FADD	1	3
5	FMUL	4	4
6	ASSIGN	0	5

⚠️ 주의 — 복잡도

새 node를 추가할 때마다 equivalent node를 찾기 위해 table을 검색하므로 polynomial complexity를 가진다. 다만 각 expression이 자신만의 DAG를 가지는 한, 절대 크기는 비교적 작게 유지된다. FMUL의 left·right가 모두 4를 가리켜(공유) a+10이 한 번만 계산됨에 주목하라.

External Representation

모든 정보가 node type에 encoding되도록 DAG를 설계하면 portable external representation 작성이 쉽다. 각 node를 symbol 뒤에 자식들을 괄호로 붙여 표현할 수 있다.

ASSIGN(x,DEREF(IADD(DEREF(IADD(FP,16)),
                    IMUL(DEREF(IADD(FP,20)),4))))

사람이 손으로 읽고 쓰기는 쉽지 않지만, print하기도 parse하기도 trivial하므로 analysis·optimization을 위해 compiler stage 사이에서 주고받기 좋다.

Optimization 예: Constant Folding

💡 Constant Folding

오직 constant들로만 이루어진 expression을 단일 값으로 축약하는 과정.
장점: programmer는 가독성·유지보수를 위해 expression을 명시적 형태로 남겨두면서도, 실행 코드에서는 single constant의 성능 이점을 얻는다.
(각주) constant folding은 더 일반적인 partial execution(일부를 compile time에 실행하고 나머지는 runtime에 남김)의 좁은 예이다.

DAG Constant Folding Algorithm — DAG를 재귀적으로 살펴 두 constant에 대한 모든 operator를 single constant로 collapse

ConstantFold( DagNode n ):

If n is a leaf:
     return;
Else:
     n.left  = ConstantFold(n.left);
     n.right = ConstantFold(n.right);

     If n.left and n.right are constants:
          n.value = n.operator(n.left, n.right);
          n.kind  = constant;
          delete n.left and n.right;

예: secs=days*24*60*60 (Figure 8.2). algorithm이 tree를 내려가며 IMUL(60,60)을 3600으로, 다시 IMUL(3600,24)를 86400으로 결합한다. 최종적으로 secs = days * 86400 형태가 된다.

days*24*60*60→ IMUL(60,60)=3600→ IMUL(3600,24)=86400→ days*86400

8.4Control Flow Graph

DAG는 expression encoding에는 적합하지만 control flow나 순서가 있는 program 구조에는 효과적이지 않다. 더 high-level 구조를 표현하기 위해 control flow graph를 쓴다.

⚠️ 왜 DAG만으로는 부족한가

DAG에서 common sub-expression은 임의 순서로 평가해도 되고(operator precedence 한도 내), DAG 안의 값이 변하지 않는다는 가정 하에 결합된다. 그러나 값을 수정하는 여러 statement나, statement를 반복/생략하는 control flow 구조에서는 이 가정이 성립하지 않는다.

💡 Control Flow Graph (CFG) 정의

CFG는 directed graph이다 (cyclic할 수도 있음).
각 node = basic block: 순차적 statement들의 묶음.
각 edge = basic block 사이의 가능한 control 흐름.
conditional 구조(if, switch) → graph에 branch 발생.
loop 구조(for, while) → reverse edge(되돌아가는 간선) 발생.

예제 코드 → CFG (Figure 8.3)

for(i=0;i<10;i++) {
    if(i%2==0) {
        print "even";
    } else {
        print "odd";
    }
    print "\n";
}
return;

i=0; | v if(i<10) ──false──> return; | true v if(i%2==0) / \ true false v v print "even" print "odd" \ / v v print "\n"; | v i++; ──(back edge)──> if(i<10)

⭐ 시험 포인트 — CFG는 AST와 구조가 다르다

for-loop의 AST는 각 control expression을 loop node의 immediate child로 둔다.
반면 CFG는 각 expression을 실제로 실행되는 순서대로 배치한다.
if statement는 각 branch에서 다음 node로 향하는 edge를 가져, 실행 흐름을 component 사이로 쉽게 추적할 수 있다.

8.5Static Single Assignment Form

SSA form은 복잡한 optimization에 흔히 쓰이는 표현이다. control flow 정보를 활용하면서, 각 basic block에 "변수는 값을 바꿀 수 없다"는 새 제약을 추가한다.

💡 SSA의 핵심 규칙

변수가 새 값을 assign받을 때마다, 그 변수에 새 version number를 부여한다.
즉 한 변수의 각 version은 정확히 한 번만 assign된다 (static single assignment).

원본 코드

int x = 1;
int a = x;
int b = a + 10;
x = 20 * b;
x = x + 30;

SSA form

int x_1 = 1;
int a_1 = x_1;
int b_1 = a_1 + 10;
x_2 = 20 * b_1;
x_3 = x_2 + 30;

x가 세 번 assign되므로 x_1, x_2, x_3로 version이 나뉜다.

⭐ 시험 포인트 — φ (phi) function

한 변수가 conditional의 두 branch에서 서로 다른 값을 받으면, conditional 이후엔 어느 값인지 알 수 없다.
이를 표현하기 위해 φ(x, y) 함수를 도입 → runtime에 x 또는 y 중 하나가 선택됨을 나타낸다.
φ function은 반드시 assembly instruction으로 번역되는 것은 아니다. 새 값을 가능한 옛 값들과 연결(link)해 control flow graph를 반영하는 역할을 한다.

원본 코드

if(y<10) {
   x=a;
} else {
   x=b;
}

SSA form (φ 사용)

if(y_1<10) {
   x_2=a;
} else {
   x_3=b;
}
x_4 = phi(x_2,x_3);

8.6Linear IR

linear IR은 final goal인 assembly language에 더 가까운, 순서가 있는 instruction의 sequence이다. DAG의 유연함(특정 순서를 확정하지 않음)은 잃지만, expression·statement·control flow를 하나의 자료구조에 담을 수 있다.

💡 Linear IR의 형태

universal standard는 없다. 보통 register 수가 매우 많은(혹은 무한한) 이상적 assembly language처럼 생겼다.
LOAD·STOR로 memory와 register 사이 값을 이동.
three-address arithmetic operation: 두 register를 읽고 세 번째에 쓴다 (왼쪽→오른쪽).

예제 expression(x=(a+10)*(a+10), float)을 linear IR로 표현하면 다음과 같다.

1. LOAD a        -> %r1
2. LOAD $10      -> %r2
3. ITOF %r2      -> %r3
4. FADD %r1, %r3 -> %r4
5. FMUL %r4, %r4 -> %r5
6. STOR %r5      -> x

⭐ 시험 포인트 — 저장 효율 & virtual register

각 instruction은 고정 크기 4-tuple(operation + 최대 3개 argument)로 표현 가능 → 효율적 저장, external representation도 단순.
무한한 virtual register가 있다고 가정하는 것이 편리하다 → 새로 계산되는 값마다 새 register에 쓴다.
lifetime: register가 처음 쓰여진(written) 지점부터 마지막으로 사용된(used) 지점까지. 그 사이에는 값이 보존되어야 한다. 예: %r1의 lifetime은 instruction 1 ~ 4.

live register set

각 instruction 시점에서 live 상태인 virtual register 집합을 관찰할 수 있다.

1. LOAD a        -> %r1                 live: %r1
2. LOAD $10      -> %r2                 live: %r1 %r2
3. ITOF %r2      -> %r3                 live: %r1 %r2 %r3
4. FADD %r1, %r3 -> %r4                 live: %r1 %r3 %r4
5. FMUL %r4, %r4 -> %r5                 live: %r4 %r5
6. STOR %r5      -> x                   live: %r5

💡 Instruction 재정렬(reordering)

어떤 instruction이든 (한 basic block 안에서) 앞으로 옮길 수 있다 — 단, 읽는 값들이 그 정의(definition) 위로 올라가지 않는 한.
마찬가지로 뒤로도 옮길 수 있다 — 쓰는 값이 그 use 아래로 내려가지 않는 한.
instruction 이동은 code generation에서 필요한 physical register 수를 줄이고, pipelined architecture에서 실행 시간을 줄일 수 있다.

8.7Stack Machine IR

더욱 compact한 IR로 stack machine IR이 있다. 전통적 register가 없고 중간 값을 담는 stack만 있는 virtual stack machine에서 실행되도록 설계된다.

💡 Stack Machine IR의 instruction

PUSH: 변수나 literal 값을 stack에 push.
POP: stack에서 항목을 꺼내 memory에 저장.
binary arithmetic operator(FADD, FMUL): stack에서 두 값을 pop하고 결과를 push.
unary operator(ITOF): 한 값을 pop하고 한 값을 push.
COPY: stack 맨 위 값을 복제(duplicate)해 push (stack 조작용 utility).

⭐ 시험 포인트 — DAG → Stack Machine IR 변환

DAG(또는 AST)를 post-order traversal 하며: 각 leaf 값마다 PUSH, 각 interior node마다 arithmetic instruction, 변수에 값을 assign할 때 POP을 emit한다.

예제 expression의 stack machine IR (공통 부분식 a+10을 COPY로 복제해 두 번 사용).

PUSH a
PUSH 10
ITOF
FADD
COPY
FMUL
POP x

직접 실행 추적 (`a = 5.0` 일 때)

IR Op	PUSH a	PUSH 10	ITOF	FADD	COPY	FMUL	POP x
Stack	5.0	10	10.0	15.0	15.0	225.0	-
State	-	5.0	5.0	-	15.0	-	-

💡 장점

3-tuple/4-tuple linear 표현보다 훨씬 compact — register 정보를 기록할 필요가 없음.
단순 interpreter로 구현하기 straightforward.

⚠️ 단점

explicit register name이 사라져, conventional register-based assembly로 번역하기 다소 어렵다.
추가 transformation/optimization을 하려면, stack-based IR의 implicit한 dependency를 다시 DAG나 explicit register name을 가진 linear IR 같은 explicit 형태로 변환해야 한다.

8.8Examples

거의 모든 compiler/language는 고유한 IR을 가진다. 2017년 기준 세 가지 실제 IR을, 같은 산술 expression을 compile한 결과로 비교한다.

공통 입력 함수

float f( int a, int b, float x ) {
    float y = a*x*x + b*x + 100;
    return y;
}

8.8.1 GIMPLE — GNU Simple Representation

💡 GIMPLE

GNU C compiler의 가장 이른 단계에서 쓰는 internal IR.
모든 expression이 값에 대한 개별 operator로 분해된, SSA form의 극도로 단순화된 C로 볼 수 있다.
basic conditional 허용, loop는 goto로 구현.
각 SSA 값은 (긴 이름의) local variable로 선언되고, 각 operator의 type은 local type 선언으로부터 추론된다.

f (int a, int b, float x)
{
  float D.1597D.1597;
  float D.1598D.1598;
  float D.1599D.1599;
  float D.1600D.1600;
  float D.1601D.1601;
  float D.1602D.1602;
  float D.1603D.1603;
  float y;

    D.1597D.1597 = (float) a;
    D.1598D.1598 = D.1597D.1597 * x;
    D.1599D.1599 = D.1598D.1598 * x;
    D.1600D.1600 = (float) b;
    D.1601D.1601 = D.1600D.1600 * x;
    D.1602D.1602 = D.1599D.1599 + D.1601D.1601;
    y = D.1602D.1602 + 1.0e+2;
    D.1603D.1603 = y;
    return D.1603D.1603;
}

8.8.2 LLVM — Low-Level Virtual Machine

💡 LLVM

optimizing compiler/interpreter를 만들기 위한 language이자 tool suite.
여러 front-end가 LLVM intermediate code를 생성 → 독립적 tool들이 optimize → native machine code나 JVM/CLR 같은 virtual machine용 bytecode로 다시 번역.
먼저 alloca로 local variable 공간을 할당하고, store로 parameter를 local로 옮긴다. 이후 각 단계를 SSA form으로 계산해 결과를 y에 store.
각 단계에서 type(32-bit integer 또는 float)과 alignment를 explicit하게 명시한다.

define float @f(i32 %a, i32 %b, float %x) #0 {
  %1 = alloca i32, align 4
  %2 = alloca i32, align 4
  %3 = alloca float, align 4
  %y = alloca float, align 4
  store i32 %a, i32* %1, align 4
  store i32 %b, i32* %2, align 4
  store float %x, float* %3, align 4
  %4 = load i32* %1, align 4
  %5 = sitofp i32 %4 to float
  %6 = load float* %3, align 4
  %7 = fmul float %5, %6
  %8 = load float* %3, align 4
  %9 = fmul float %7, %8
  %10 = load i32* %2, align 4
  %11 = sitofp i32 %10 to float
  %12 = load float* %3, align 4
  %13 = fmul float %11, %12
  %14 = fadd float %9, %13
  %15 = fadd float %14, 1.000000e+02
  store float %15, float* %y, align 4
  %16 = load float* %y, align 4
  ret float %16
}

8.8.3 JVM — Java Virtual Machine

💡 JVM

JVM은 stack-based machine의 추상적 정의.
Java 코드는 .class 파일(JVM bytecode의 binary 표현)로 compile된다.
초기 구현은 bytecode를 그대로 실행하는 interpreter, 이후 구현은 bytecode를 native assembly로 바꾸는 JIT(just-in-time) compiling.
iload/fload는 local variable을 참조(parameter가 첫 몇 개 local). iload 1 = 첫 local(int a) push, fload 3 = 셋째 local(float x) push.
고정 constant는 class 파일의 array에 저장되어 위치로 참조 → ldc #2는 위치 2(100)의 constant를 push.

 0: iload   1
 1: i2f
 2: fload   3
 4: fmul
 5: fload   3
 7: fmul
 8: iload   2
 9: i2f
10: fload   3
12: fmul
13: fadd
14: ldc     #2
16: fadd
17: fstore 4
19: fload   4
21: freturn

⭐ 시험 포인트 — 세 IR의 분류

IR	유형	특징
GIMPLE	SSA 기반 단순화된 C	GNU C compiler 초기 단계, loop는 goto
LLVM	SSA, register-based linear IR	type·alignment를 explicit하게, alloca/load/store
JVM	stack machine bytecode	iload/fload/fmul/ldc, JIT 가능

8.9Exercises (연습문제)

compiler에 AST → DAG 변환 단계를 추가하라 (post-order traversal로, 각 AST node에 하나 이상의 DAG node를 생성).
이 장에서 보인 단순 external representation으로 DAG를 export하는 코드를 작성하라. control flow 구조와 function definition을 표현하도록 DAG를 적절히 확장하라.
DAG external representation을 읽어 data structure로 재구성하는 scanner와 parser를 작성하라. IR의 grammar class를 신중히 고려하고, 동작하는 가장 단순한 구현을 택하라.
(2,3 기반) DAG format을 읽어 constant folding 같은 단순 optimization을 수행하고 같은 format으로 다시 쓰는 standalone optimization tool을 작성하라.

8.10Further Reading

논문	주제
Cytron, Ferrante, Rosen, Wegman, Zadeck (1991), TOPLAS	SSA form과 control dependence graph를 효율적으로 계산
J. Merrill (2003), GCC Developers Summit	GENERIC and GIMPLE: 전체 함수를 위한 새 tree representation
C. Lattner & V. Adve (2004), CGO	LLVM: lifelong program analysis & transformation을 위한 compilation framework

⭐핵심 정리 / 시험 포인트

🎯 반드시 외울 핵심 명제

IR은 source language와 target assembly language 사이에 위치하며, simple·regular 구조로 optimization·analysis·code generation을 돕는다.
modular compiler: 각 도구가 같은 IR을 소비·생산 → optimization 조합 자유. IR은 text external format으로 교환 가능.
AST는 too rich해서 production IR로 부적합 (하나의 ADD가 integer/float/bool-or/string concat이 될 수 있음). 단, 단순 컴파일에선 post-order traversal로 assembly emit 가능.
DAG = AST 한 단계 단순화 + 공통 부분식 공유 + type-specific node(FADD/IADD/ITOF). value-number method로 AST를 post-order 순회하며 구성(중복 시 재사용, polynomial complexity).
DAG external representation: SYMBOL(child, child) 형식 — print·parse가 trivial.
constant folding = constant만의 expression을 single 값으로 collapse (partial execution의 한 예).
CFG: node=basic block, edge=control 흐름. conditional→branch, loop→reverse edge. DAG는 ordered/control flow엔 부적합.
SSA: 변수는 값을 바꾸지 못함 → assign마다 새 version number. 두 branch가 충돌하면 φ(phi) function으로 link(반드시 instruction으로 번역되진 않음).
Linear IR: three-address code(2 register 읽고 1개 쓰기), 무한 virtual register, 고정 4-tuple. lifetime=처음 write~마지막 use. 정의/use 제약을 지키면 instruction 재정렬 가능.
Stack Machine IR: register 없이 stack만. PUSH/POP/COPY, binary op는 2 pop 1 push, unary는 1 pop 1 push. 가장 compact하지만 register name이 사라져 번역이 어려움. DAG post-order로 emit.
실제 예: GIMPLE(SSA-C, goto loop), LLVM(SSA register-based, alloca/load/store, type·align explicit), JVM(stack machine bytecode, iload/fmul/ldc, JIT).

💡 추상화 수준 순서 (high → low)

AST
DAG
Control Flow Graph
SSA form
Linear IR (three-address)
Stack Machine IR

💡 stack machine 실행 규칙

PUSH 변수/literal → stack
POP → memory에 저장
binary op: 2 pop → 1 push
unary op(ITOF): 1 pop → 1 push
COPY: top 값 복제 push

❓ 예상 서술형/단답

Q. AST를 production IR로 쓰기 어려운 이유? → 구조가 too rich: 한 node(예 ADD)가 integer/float/bool-or/string concat 등 너무 많은 의미를 가져 robust transformation·external representation이 어렵다.
Q. DAG와 AST의 차이? → DAG는 arbitrary graph(공통 부분식 공유), node가 단순·type explicit(FADD 등), node type 수가 많다.
Q. value-number method란? → array에 (type, child index)를 저장하고, 새 node 추가 시 matching node를 검색·재사용. AST를 post-order로 순회해 구성.
Q. φ function이 필요한 상황? → 변수가 conditional의 두 branch에서 다른 값을 받아, 이후 어느 값인지 모를 때. φ(x,y)로 runtime 선택을 표현.
Q. three-address code란? → 두 register를 읽고 세 번째 register에 쓰는 arithmetic operation 형식의 linear IR.
Q. %r1의 lifetime을 구하라 → 처음 write된 instruction부터 마지막 use까지 (예제에선 instruction 1~4).
Q. stack machine IR의 장단점? → 장점: 매우 compact, interpreter 구현 쉬움. 단점: register name 소실로 register-based assembly 번역·추가 optimization이 어려움.

📋한눈에 보기 — Cheat Sheet

용어 / 키워드	의미
Intermediate Representation (IR)	source와 target assembly 사이의 표현. simple·regular, external format 가능
AST	가장 high-level IR. too rich → 큰 optimization 없이 post-order로 assembly emit할 때만 적합
DAG	AST 한 단계 단순화. arbitrary graph, 공통 부분식 공유, type-specific node
FADD / IADD / FMUL / IMUL / ITOF	type이 결정된 DAG node (float/int add·mul, int→float 변환)
value-number method	(type, child index) array로 DAG 구성, 중복 node 재사용 (post-order)
constant folding	constant만의 expression을 single 값으로 collapse (partial execution 예)
Control Flow Graph (CFG)	node=basic block, edge=control 흐름. conditional→branch, loop→reverse edge
basic block	순차적 statement들의 묶음(CFG의 node)
SSA form	변수는 값 불변 → assign마다 version number
φ / phi(x,y)	두 branch 값을 link. runtime에 선택. 항상 instruction으로 번역되진 않음
Linear IR	ordered instruction sequence. assembly에 근접
three-address code	2 register 읽고 1 register에 쓰기. 고정 4-tuple
LOAD / STOR	memory↔register 값 이동
virtual register	무한 가정. 새 값마다 새 register
lifetime / live	register의 첫 write~마지막 use 구간 / 그 시점 live한 register 집합
Stack Machine IR	register 없이 stack만. 가장 compact
PUSH / POP / COPY	stack에 push / memory에 저장 / top 값 복제
binary op (FADD,FMUL)	2 pop → 1 push
unary op (ITOF)	1 pop → 1 push
GIMPLE	GNU C 초기 IR. SSA 기반 단순화 C, loop는 goto
LLVM	SSA register-based IR. alloca/load/store, sitofp/fmul/fadd, type·align explicit
JVM	stack machine bytecode. iload/fload/fmul/i2f/ldc/freturn, JIT