[컴개/CI] Intermediate Representation(IR)

Intermediate Representation(IR)

 

IR은 위 사진에서의 단계 중 중간 코드를 의미한다.

전체적인 컴파일 과정은 High-level 언어에서 Low-level 언어로 만들어주는 과정인데, 이 과정에서 High-level 언어보다는 low하고, Low-level 언어보다 high한 언어로 만들어주는 단계를 거치게 된다.

 

이러한 IR은 언어와 기계에 독립적이며 컴파일러 내부적으로 사용하는 경우가 가장 많다.

IR은 instruction list의 형태와 같은데, 기계어 코드와 같은 list 형태가 가장 많다. 또한 tree 형태로도 존재한다. 이러한 instruction(node)의 종류가 적을 수록 최적화나 번역에 좋다.

 

 

Java, C, C++과 같은 High-level 언어를 받아서 AST로 만든 후, 중간 언어 IR을 거치고 Low-level 언어로 향한다.

 

이러한 IR은 여러 개가 존재할 수 있는데, 얼마나 높냐, 얼마나 낮냐에 따라 HIR, LIR이라고 구분 지을 수 있으며, 여러 개를 사용하는 경우 multiple IR's라고도 한다.

 

가장 낮은 LIR은 직접 target 언어 또는 기계 언어에 대한 코드를 생성하고,

높은 HIR은 소스코드의 정보를 활용하여 소스 코드를 최적화시켜준다.

 

위 그림에서 출력물 중 java bytecode의 경우 가상 기계 위에서 동작한다. 따라서 가상 기계를 target으로 하는 컴파일러도 존재한다. 이때, 가상 기계 자체를 IR로 보기도 하기 때문에, java bytecode 자체를 LIR 또는 target 언어로 볼 수 있다.

 

High Level IR(HIR)

이때, HIR, LIR을 구분하는 기준은 따로 없으며 상대적인 개념이다.

GCC의 경우 3개의 IR을 사용하고, 어떤 건 1개만 사용한다.

 

HIR은 AST와 비슷하다. AST의 표현력을 유지하고, 해당 표현에서 비롯된 정보를 활용하여 최적화 또는 코드를 생성할 때 필요한 정보를 빼낸다. 

 

변수, 변수 타입, while, for, 함수 등의 구조가 유지되기 때문에, 변수 사용 분석, loop 변환, 함수를 복사붙여넣기하는 inlining과 같은 최적화 시에 용이하다.

 

 

위 사진을 통해 AST와 HIR을 비교해보자. 위 사진은 TCOL이라는 HIR이다.

코드에서 a는 int 타입, b는 float타입이다. 이때, a + 1이라는 값이 float 변수에 할당되기 때문에, assingment가 일어나기 직전에 int가 float로 변환되는 과정이 필요하다.

 

AST에서 sementic적인 분석이 덧붙여져 float 의미 분석 후 float라는 정보가 들어가면서 전체적인 AST의 구조가 구제적으로 a+1이 int의 합으로 계산되고, 이후 float로 변환이 되는 절차적 성격의 새로운 node가 추가된다.

 

즉, TCOL 언어는 AST와 비슷하지만, 타입 검사에서 얻은 것으로 명령어가 바뀐다.

 

Low Level IR(LIR)

LIR은 주로 단순한 instruction으로 구성되어 있다.

RICS 머신은 명령어 사이즈, op 코드 길이, 종류가 한정적이지만, 대신 프로그램 길이가 길어진다는 특징이 있다. CISC 머신은 for문 표현과 같은 가능한 복잡한 명령 지원하지만 명령 길이 길어지는 특징을 가지고 있는데, RISC 머신이 번역과 최적화에 더 용이하다고 판명되어 더욱 각광받고 있다.

 

LIR은 어셈표현된 RISC 머신과 닮아있다.

 

머신 구조를 표현하기 위해, memory locations, registers, unstructured jump(goto) 등을 가지고 있어야 한다.

 

instruction의 예시로는 사칙연산, 메모리연산, 함수 call/return과 같은 것들이 추상화되어 들어가 있어 보기 좋게 표현이 가능하다.

 

Low level IR의 종류

N-tuple 표기법

가장 많이 쓰이는 LIR은 N-tuple 표기법이다.

연산자, 피연산자1, 피연산자2, 결과 총 4개의 튜플이 있는 경우 quadruple라고 하며 High-level로 표현하면 a = b OP c가 된다.

 

어떤 피연산자 2개에 op를 취했을 때의 값이 결과값이 되는데,

결과값과 instruction이 따로 표현된다.

 

예전에는 3-tuple 표기법이 유행하였는데, 3-tuple은 b + c의 결과값을 저장하지 않는다.

quardruple의 경우 a에 결과값을 저장하지만 3-tuple에서 나중에 결과값을 참조하고 싶은 경우

명령마다 공간이 있고, 해당 공간에 결과값을 저장하며 참조하는 곳에서 해당 명령어를 불러온다.

 

위 사진이 3-tuple의 예시이다. b+c의 명령어가 100번째 주소에 저장되어 있고,

해당 연산의 결과값에 1을 더하는 명령어가 108번째 주소에 저장되어 있다.

연산의 결과값을 가져오기 위해 108번 명령어는 100번의 명령어를 가져오고 있다.

 

이때, 연산 결과를 명령어에 저장하는데, 코드를 최적화 할 때, 명령어들의 주소가 바뀌는 경우가 발생했다. 위 예시에서 100번째 명령어의 주소가 바뀌면, 해당 명령어의 결과값을 참조하는 모든 명령어를 수정해주어야 했기 때문에 quardruple 방법을 채택하게 되었다.

 

하지만, quardruple도 단점이 존재하는데,

이 단점은 바로 임시 변수를 다뤄야 한다는 것이다.

b + c 연산을 수행하고 항상 어딘가에 저장을 해야 하는데,

프로그램에서 저장하는 곳을 a라고 명시하지 않아도 메모리의 어딘가에 저장을 해야 하는 경우가 꽤 많이 존재하였다.

 

하지만 이러한 단점은 컴파일러의 일반적인 최적화 방법으로 해결이 가능하다.

 

Tree 표현

기계어를 생성할 때에 파싱 후 트리를 만들었듯이,

트리 형태로 표현하는 것이 용이하다는 여론이 생성되어 트리로 표현하는 것이 선호된다.

 

Stack machine code

Java byte code, U-code의 경우 Low-level한 코드라고 불리지만 사실 가상머신 위에서 실행되는 경우들이다.

 

즉, Stack machine code로 표현이 가능하다. (가상머신코드 == Stack machine code)

 

N-Tuple, 3-주소 코드 (Quadruple)

우리는 N-tuple 코드를 주로 채택하는데, 그 중에서도 quardruple을 자주 사용한다.

이때, quardruple은 op를 제외하고 피연산자 두 개와 결과값을 저장하기 위한 메모리 공간이 3개가 필요하다고 해서 3-address code라고도 이야기한다.

 

이때, 일반적으로 필요한 주소의 개수는 항상 3개는 아니며, 3개 이하인 경우도 포함이다.

 

3-address code는 c코드와 비슷하다.

다른 점은 명령어에 올 수 있는 연산자가 1개라는 점으로 피연산자 2개와 결과값까지 3개 또는 3개 이하로 가져야한다.

 

a = (b+c) * (-e)

 

위 코드는 High-level 언어로 표현된 명령어다. High-level 언어로 표현하는 경우 하나의 명령어에서 여러 개의 연산자가 등장할 수 있다.

 

이를 3-address code로 표현하기 할 때 보이지 않는 임시변수를 담아 둘 메모리 공간을 필요로 하는데, 3-address code에서는 이러한 임시 메모리 공간을 보이게 만들어 준다.

 

t1 = b + c
t2 = -e
a = t1 * t2

 

위 코드는 High-level 언어로 표현된 명령어를 3-address code로 표현한 모습이다.

위 코드에서 t1과 t2는 기존에 없던 변수로, 새롭게 만들어 준 변수이다.

 

3-address code: Intstruction

Assignment instructions

- a = b OP C (binary op)
arithmetic: ADD, SUB, MUL, DIV, MOD
logic: AND, OR, XOR
comparisons: EQ, NEQ, LT, GT, LEQ, GEQ

- a = OP b (unary op)
arithmetic MINUS, logical NEG

- a = b : copy instruction

- a = [b] : load instruction

메모리의 주소를 주면 값을 반환

- [a] = b : store instruction

메모리의 주소를 주고 값을 저장

- a = addr b: symbolic address

변수의 주소값을 가져옴

 

3-address code는 기본적으로 바이너리와 유나리 연산을 모두 포함한다.

아래에서 세 번째까지의 연산은 c와 비슷한 연산인데, 이를 미루어 보아 c언어는 굉장히 low한 레벨의 언어임을 깨달을 수 있다. 이러한 c언어는 사실 기계어와 가까운 언어로, c언어를 통해 운영체제도 개발할 수 있는 정도이다.

 

Flow of control

- label L

label instruction

- jump L

unconditional jump

 

- cjump a L

conditional jump

 

Flow of control은 goto만 가지고 있고, while/for/swith/if문 모두 없다.

보통 jump라 불리는 goto로 시뮬레이션을 한다.

 

Function call

- call f(a1, ..., an)

- a = call f(a1, ..., an)

 

함수 호출은 상위 언어처럼 표현이 가능하다.

인자를 주면, call을 통해 호출하고, 결과를 리턴하여 받을 수도 있다.

이러한 명령어들 모두 3-address code의 범주로 포함하고 있다.

 

즉, 3-address code 전체를 보면 가상 기계가 존재하고, 가상 기계에는 위와 같은 instruction이 있다고 생각하자.

 

3-주소 코드 : 피연산자

개발자가 준 일반적인 변주, 상수, 리터럴 들을 피연산자로 받을 수 있다.

추가로 받는 피연산자는 완전히 새 location이어야 하고, 중간값을 저장하기 위해 사용한다.

 

op가 여러 개가 들어가는 하나의 c 코드를 op 별로 끊어서 중간중간 저장하면서 값을 사용해야 하는 이유로 임시변수가 도입되었다.