[Compiler Design] Intermediate Representation

 

 

 

중간언어(IR)는 컴파일러 내부적으로 사용하는 경우가 많고, 대부분 트리 형태나 Intruction List(기계어 코드) 형태를 가진다.

 

 

 

 

자바 코드는 AST로 변환된 후, 중간 언어를 거친 다음에 Low Level 코드로 변환된다.

중간 언어는 여러 종류가 있을 수 있다 - High Level, Low Level

 

AST와 가까이 있다면 소스코드 정보를 최대한 활용해서 최적화에 사용하고, Low Level과 가까이 있다면 실제로 Low Level 언어로 변환하는 작업을 수행한다.

 

High Level과 Low Level은 상대적인 개념이다. 당연히 3개 이상의 중간언어도 나올 수 있음.

 

High Level IR은 AST의 변형이라고 생각하면 됨. 

변수, 표현식, 문장, 함수 등 모든게 유지되니 변수 사용 분석, Loop Transform, 함수 Inlining 등 여러 작업을 수행할 수 있다.

 

 

 

 

 

좌측은 AST 우측은 TCOL (High Level IR) 그냥 바로 어떤 느낌인지 감이 온다.

 

컴파일러가 최적화 할 때는 3-Address Code 형식을 사용한다.

AST는 계산 순서가 트리 모양이라 컴퓨터가 순차적으로 처리하기에는 복잡함

그래서 3-Address Code를 사용함. x = y + z 처럼 한 줄로 나열되어 있어 다루기 편하다.

 

x = y OP z 형태의 N-tuple로 표현하고, 복잡한 식은 컴파일러가 생성한 임시 변수를 사용해서 쪼개진다. 

아래와 같이..

 

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

1. t1 = b + c
2. t2 = -e
3. a = t1 * t2

 

 

실제 컴파일러의 GCC가 어떻게 IR 을 활용하는지 보자. GCC는 여러 단계의 IR을 사용한다. 

 

C,C++ -> GENERIC -> GIMPLE -> RTL -> 어셈블리 

 

C,C++ - 그냥 소스코드임

GENERIC - 트리 형태의 High Level IR 

GIMPLE - 3 Address Code 형태. 여기서 최적화 최대한 깎아준다. 임시변수가 생기면서 쪼개짐.

RTL (Register Transfer Language) - 기계어와 유사한 Low Level IR 

 

현대 컴파일러는 LLVM IR을 사용함. 모듈화가 확실하게 되어있어 깔끔하다.

Frontend : 소스코드 -> LLVM IR 

Common Optimizer : LLVM IR -> 최적화된 LLVM IR 

Backend : LLVM IR -> 기계어 

 

지역변수 앞에 %를 붙이고 개수 제한이 없는 가상의 레지스터를 사용한다.

전역변수 앞에는 @를 붙이고.. 타입도 i32처럼 확실하게 선언해준다.

 

if (a == 0) {
    a++;
}

----

%0 = load i32* %a, align 4                  ; a 읽음
  %cmp = icmp eq i32 %0, 0                  ; 0 같은지 확인하고 cmp 에다가 저장
  br i1 %cmp, label %if.then, label %if.end ; if then 분기 태움

if.then:
  %1 = load i32* %a, align 4
  %inc = add i32 %1, 1            
  store i32 %inc, i32* %a, align 4
  br label %if.end

if.end:
  ...

 

 

load add store 명령어가 3 Address Code 방식을 따른다.

Clang이 LLVM 기반인데, 다른 컴파일러랑 비교할 때 컴파일 속도가 확실히 빠름.

 

 

Java나 C#은 한 번 작성하고 Linux Window 등 어떤 환경에서든 실행할 수 있어야 된다는 철학으로 개발됨.

이 철학을 지키기 위해 VIrtual Machine을 사용한다.

 

Frontend : Source -> IR(ByteCode)

IR : Virtual Machine이 이해하는 기계어로, 주로 스택 머신 형태로 구성된다.

Backend : IR -> Target Machine에 맞는 기계어

 

Java ByteCode는 스택 머신 구조로 구성됨.

 

Local Variables : 함수 내부의 지역변수 (배열 형태)

Operand Stack : 연산을 위해 값을 잠시 쌓아두는 곳.

Constant Pool : 상수 / 메서드 / 필드 참조 정보를 저장하는 곳.

 

스택 머신 IR 설계 시 데이터 타입도 고려해야 한다..

자바는 Integer Add는 있지만 Short Add 명령어는 없음. -> JVM이 int로 변환해서 계산한다.