Intermediate Representation - 1

이전까지는 프론트엔드에 대해 공부했고, 이제는 백엔드를 공부할 차례이다.

 

* Intermediate Representation (IR)

쉽게는 컴파일러 안에 있는 어셈블리라고 생각하면 된다.

컴파일러가 프론트엔드에서 마지막에 결과로 나오는 AST 를 IR 로 저장할 때 코드의 형태를 나타내는 것이다. 컴파일러는 IR 형태로 input 프로그램을 저장한 후에 최적화하고 target 하드웨어에 맞도록 코드를 만든다. IR 은 target 언어와 target machine 에 independent 하다. 

 

+ target 하드웨어와 independent 하다? machine independent 하다? 는 무슨 의미일까? 저장소와 ALU 가 무한대로 있다는 것이고 이것을 virtual 환경이라고 한다. 그렇다면 모든 instruction 이 한 사이클에 끝날 수 있을까? core dependency 가 있기 때문에 어려운데 이걸 없애려면 프로그램을 새로 짜서 없애는 방법밖에 없다. 컴파일러는 virtual 환경과 비슷하게 만드는 게 목표다.

 

 

 

* IR 을 어떻게 만들어야 좋을까?

두 가지 level 로 IR 을 만들 수 있다.

> high-level language 와 비슷하게 저장할 수 있다. 루프가 키워드로 명시되어 있기 때문에 detection 이 쉽다. 

> low-level machine 의 특성(어셈블리와 비슷하게)과 저장할 수 있다. 머신코드를 만들기 쉽다.

> Narrow interface : instruction 의 개수를 조금만 가지고 있는 것이 좋다. (간결한 구조여야 최적화하기 쉽고, 타겟 하드웨어에 맞는 코드를 만들기도 쉽기 때문이다.)

 

 

 

* Multiple IRs

대부분의 컴파일러는 2개의 IR 을 사용한다.

하이레벨과 유사한 것(HIR)과 로우레벨과 유사한 것(LIR)인데, 프로그래밍 언어를 파싱하면 AST 로 저장이 되고, 이를 기반으로 HIR 를 만든 후에 최적화를 수행한다. (function inline 처럼 scope 가 큰 단위를 최적화) LIR 로 바꾸고 다시 최적화를 진행하여 타켓 하드웨어에 맞도록 어셈블리를 만든다.

 

 

+ LIR 이 virutal 하다고 했는데, 레지스터와 ALU 가 virtual 한 것이다. virtual 을 physical 로 바꾸면 register allocation 과 opcode mapping, scheduling 를 해야 한다. 

 

 

> HIR 은 AST 와 같다. 토큰들을 프로그램 구조에 맞게 트리 구조로 구성하고 저장한 자료구조이다. 프로그램이 동작할 때 flow 가 어떻게 변하는지 알 수 있다(if, switch 등 처럼) . HIR 구조로 짜여진 코드는 하이레벨 최적화를 할 수 있다. 앞에서 말한 것처럼, 어셈블리 형태에서 최적화를 하기 어려운 이유는 어셈블리는 루프를 찾는 게 쉽지 않기 때문이다. 하지만 하이레벨에서는 키워드를 통해 루프가 있는지 알 수 있어서 쉽다.

 

 

> LIR 은 Abstract machine 을 구동시키기 위한 instruction 의 모임이다. 다시 언급하자면, Abstract machine 은 communication unit 과 register 가 무한대인 것을 말한다.

 

 

LIR 의 종류를 보면,

1. Three-Address Code : operand 3개가 존재하고 하나의 opcode (연산자) 가 존재한다. (a = b OP c), quadruple 이라고도 하고 2,3번도 쓰이긴 하지만 이게 가장 많이 쓰인다.

2. 트리 형태 (머신 코드를 쉽게 만드는 장점)

3. 스택 머신 

 

 

* IR Instructions

> Assignment instructions

   - a = b OP C  : binary op (input operand 가 2개)

   - a = OP b : unary op (input 1개) 예) MOV(copy), CPL(not) 

                       + 만약 모든 instruction 이 binary 로 만들어져 있다면 MOV 와 CPL 는 어떻게 만들까? ADD r1, r2, 0

   - a = b : copy instruction (input 을 output 에 저장)

   - a = [b] : load instruction (메모리 주소에 있는 데이터 타겟에 저장)

   - [a] = b : store instruction (값을 다른 메모리 주소의 저장)

   - a = addr b : symbolic address

 

> Flow of control 

   - label, jump, cjump 와 같이 flow 를 바꾸는 것이다. 다른 곳에 있는 instruction 을 실행한다.

 

> Function call

   - call f()

 

 

 

* IR Operands

대부분 3-address code 로 되어 있는데, 프로그램 변수(실제 지정한 변수)이거나 상수나 임시 변수(하이레벨에서는 없었는데 작은 instruction 모임으로 바꿀 때, 중간값을 저장하는 데 사용한다.)이다.

 

 

* Translating High IR to Low IR

notation : [[e]]

예를 들어, binary operation: t = [[e1 OP e2]] 를 보면 

t1 = [[e1]]

t2 = [[e2]]

t = t1 OP t2 

로 표현할 수 있다.

 

Array access: t = [[v[e]]] 도 바꿔보자.

t1 = addr v

t2 = [[e]] -> index

t3 = t2 * S -> offset

t4 = t1 + t3 -> address of v[e]

t = [t4]

 

 

이 외에 if-else, while, switch 등 다양한 statement 들을 연습해보자.