전통적인 컴파일러의 흐름

소스 코드
  ↓
AST (Abstract Syntax Tree)
  ↓
IR (중간 표현)
  ↓
저수준 IR / 기계 독립 최적화
  ↓
타겟 종속 코드 생성
  ↓
어셈블리 / 머신 코드
  ↓
실행 파일

 

AST 는 의미 구조만 담고 있음

a = b + c * d;

//////////////////

     =
   /   \
  a     +
       / \
      b   *
         / \
        c   d

의미는 명확하지만

• 레지스터 없음
• 메모리 주소 없음
• 실행 순서가 추상적
• CPU 가 이해 못 함

IR 로 내려가야 함

 

AST - IR (중간 표현 생성)

• 트리 - 선형적 명령 시퀀스
• 최적화하기 쉬운 형태
• 하드웨어 독립적

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

or

t1 = mul c, d
t2 = add b, t1
a  = t2

• 표현식 평탄화
• 제어 흐름 그래프 생ㅇ성
• 심볼 - 값으로 변환
• 타입 확정

 

IR 단계에서 진짜 컴파일러의 역할이 시작됨

주요 작업들

• 제어 흐름 구성
  • if / loop - basic block
  • CFG (context free grammer) 생성
• 데이터 흐름 분석
  • def-use chain
  • liveness
  • dominance
• 최적화
  • constant folding
  • dead code dlimination
  • common subexpressino elimination
  • loop invariant code motion
  • inlining

AST 에선 불가능한, IR 에서 가능한 작업들

 

IR - 저수준 IR ( Lowering)

t1 = mul c, d

>

LOAD r1, [c]
LOAD r2, [d]
MUL  r3, r1, r2

 

가상 레지스터

 

레지스터 할당 & 타겟 코드 생성

• 레지스터 할당
• 스택 프레임 생성
• calling convention 적용
• ABI 맞춤

mov eax, [c]
imul eax, [d]
add eax, [b]
mov [a], eax

 

어셈블 - 링크 - 실행 파일

 

• assembler → object file
• linker → executable
• runtime loader → 메모리 적재
• 실행

 

AST 는 무엇을 계산할지 표현, IR 은 어떻게 계산할지 결정

코드 생성은 어디서 어떻게 실행할지 확정