컴퓨터/컴파일러

6. Translation to Intermediate Code

sidedoor 2024. 7. 19. 15:00

Intermediate Representation(IR)

기계어 연산을 표현할 수 있는 추상적 언어로 소스 언어와 무관하고 컴파일러마다 IR이 다를 수 있다.

IR은 필수는 아니지만 호환성을 위해서 있으면 좋다.

왜냐하면 IR을 사용하면 언어간에 바꾸기 편하고, 이해하기 쉽고, CPU의 차이를 잘 반영할 수 있기 때문이다.

 

CISC: 1개의 복잡한 일을 다루는 것으로 더 복잡한 코드를 1개의 명령어로 표현 가능하다

RISC: 명령어가 단순한 작업일 때 사용하는 것으로 더 많은 명령어가 사용 가능하다.

 

Assembly Language

word는 프로세서가 다룰 수 있는 단위로 일반적으로 레지스터의 크기를 의미한다.

여기서 %eax, %ecx, %edx, %ebx, %esi, %edi는 32-bit register를 의미하고 여기에 e가 빠지면 아래족 16비트에 해당한다.

그리고 여기서도 %ah, %al과 같이 각각 8비트로 앞쪽과 뒤쪽에 접근할 수 있다.

 

▪ Operations

cpu가 한 번에 실행하는 명령어로 레지스터 또는 메모리 데이터의 연산 기능을 수행한다.

메모리와 레지스터간의 데이터 전송은 메모리에서 레지스터로 데이터를 load하고 레지스터에서 메모리로 데이터를 저장한다.

그리고 비교하는 연산이나 점프를 하는등의 transfer control을 통해서 pc값을 바꾼다.

 

▪ Label

코드의 위치를 가리키는 것으로 symbolic label은 함수의 시작에 ":" 기호를 사용해서 시작을 한다.

one: 
/* ... assembler code ... */ 
jmp one

위처럼 사용해서 jmp를 통해서 pc가 one으로 바뀐다.

 

▪ movl

데이터 값을 옮기는 것으로 상수 값을 바로 레지스터나 메모리에 값을 줄 수 있고, 레지스터 값이나 메모리 값도 각각 옮길 수 있다.

movl $3 (%eax)

이때 이와 같이 괄호를 통해서 레지스터를 나타내면 이는 레지스터를 의미하는 것이 아니라 레지스터가 가지고 있는 주소를 의미하는 것으로 해당하는 메모리에 값을 옮겨준다.

movl의 사용법

IR Representation

IR은 tree나 list와 같이 다양한 형태로 표현이 가능한데 IR tree에서는 expression(exp)로 값을 계산 하거나 메모리 접근 혹은 출력과 같은 side effect이 발생할 수 있는 것들을 표현하고, statements(stm)으로 side effect를 수행하고 control flow를 바꾸는 작업을 표현한다.

 

Expression

CONST of int : 정수 1개를 대표한다

NAME of Temp.label : label이름을 나타낸다

TEMP of Temp.temp : temporary register로 가상의 레지스터를 대표한다.

BINOP of binop * exp * exp :두개의 expresion을 계산한다.

MEM of exp :읽거나 쓰는 메모리의 주소를 받는다

CALL of exp of exp list :호출한 함수와 argument를 받는다.

ESEQ of stm * exp : statement와 expression을 받아 statement를 실행한 후 expression을 실행한다

 

Statement

MOVE of exp * exp : 뒤의 exp를 계산한 뒤에 앞에 넣어준다

EXP of exp : exp를 계산만 한다

JUMP of exp * Temp.label list : 주어진 주소로 jump한다

CJUMP of relop * exp * exp * Temp.label * Temp.label : 조건에 맞춰서 해당 위치로 jump한다

SEQ of stm * stm : statement 2개를 연결한다

LABEL of Temp.label : 해당 label을 정의한다

Translation to Intermediate Code 예시

 

Array Variable

array를 생성할 때 alloca를 통해서 메모리를 초기화 하고 할당을 해준다.

CALL(NAME(alloca), [CONST(n), CONST(w)])

 

여기서 n은 할당될 원소의 수이고 w는 element의 크기이다.

이를 통해서 a[i]에 접근하기 위해서  &(a[i]) = &(a[0]) + i * w 과 같이 하면 된다.

 

Record Variable

a.f과 같은 것에 접근을 하기 위해서는 tree에서 a의 위치를 찾고 그 후 해당 위치에서 f까지의 위치를 찾아서 구해주면 된다.

MEM(BINOP(PLUS, e, BINOP(MUL, CONST(offset), CONST(w))))

따라서 이와같이 하면 되고 여기서 e는 IR tree에서 a의 위치이고, offset은 f의 위치이다.

 

Conditional Statement

if e1 then e2 else e3와 같은 조건문을 표현할 때는 다음과 같이 하면 된다.

ESEQ(SEQ(e1(t,f),
    SEQ(LABEL(t),
    SEQ(MOVE(TEMP(r), e2)),
    SEQ(JUMP(NAME(join)),
    SEQ(LABEL(f),
    SEQ(MOVE(TEMP(r), e3)),
    LABEL(join))))))),
    TEMP(r))

여기서 조건인 e1이 t로 나온다면 label name이 t에 해당하는 부분으로 jump해서 해당 내용을 다루고 만약 f가 나온다면 name이 f인 부분으로 jump 해서 해당 내용을 다룬다.

 

Loop

while loop와 같은 경우는 조건문과 비슷하게 반복되는 부분의 label로 jump하는 것을 통해서 구현 할 수 있다.

while a > 1 in print(a)  {Variable Environment: a → TEMP("t")}

SEQ(LABEL("test"),
    SEQ(CJUMP(GT, TEMP("t"), CONST(1), NAME("body"), NAME("done")),
    SEQ(LABEL("body"),
    SEQ(EXP(CALL(NAME("print"), [TEMP("t")])),
    SEQ(JUMP(NAME("test"), []),
    LABEL("done"))

 

Function Call

f(a1, a2, ..., an)과 같은 함수의 경우 다음과 같이 구현한 다.

CALL(NAME(function_label), [sl, e1, e2, ..., en])

여기서 sl은 f의 static link를 의미한다