[컴개/CI] 3-address code: 예제 1

각각의 예를 분류하면 아래와 같다.

 

- 3-addr code: GCC GIMPLE, LLVM

- Stack machine code: JVM byte code, MSIL

- Tree code: GCC RTL

 

예1) GCC의 GIMPLE

 

GCC는 c 언어의 컴파일러로 최소 3개의 중간 코드가 존재한다.

중간 코드로는 GENERIC, GIMPLE, RTL이 있다.

 

이러한 GCC 컴파일러는 c언어 뿐만 아니라, c++, Objective C, Ada까지 입력으로 받을 수 있으며, target 코드의 종류도 여러 가지이다.

 

GCC는 사실 컴파일러라기 보다 Compiler Generation Framework이라고 부르는 것이 더 정확하며, GCC에서 c 컴파일러를 찾기 위해서는 폴더를 타고 들어가야 한다.

 

GENERIC

AST에서 거의 바로 나온 형태로 트리 형태의 HIR이다.

GENERIC은 여러 FOTRAN, c++과 같은 여러 가지 코드를 받아 언어 고유의 기능들은 다들 사용하는 언어처럼, 즉 언어 중립적으로 표현한 후 그에 따라 AST 모양으로 만들어주는 형태이다.

 

GIMPLE

대표적인 3-address code로 gimple을 열어보면 D.1954와 같은 변수를 발견할 수 있는데, 이 변수가 바로 임시변수이다.

 

또한 gimple_assign에서 4가지의 파라미터를 제공하는데, 이 형태를 미루어보아 gimple은 quardruple임을 확인할 수 있다.

 

RTL

RTL도 머신 코드를 생성해야 하므로 트리의 형태의 LIR이다.

결과적인 기계어 코드를 만들기 위해서 일련의 파라미터를 받아 파라미터에 따른 코드를 생성한다.

 

 

GIMPLE에 대해 자세히 살펴보자.

#include <stdio.h>
void main(){
	int x = 10;
    int y = 5;
    
    x = x * y + 3;
    printf("hello\n");
}

위와 같이 구성된 c 코드 파일이 있다. 해당 파일을

gcc -fdump-tree-all test.c

이 -fdump-tree-all 옵션은 컴파일하면서 쓰고 싶은 것을 다 보여주는 옵션이다.

 

명령어를 실행하면 사진의 왼쪽 아래처럼 .gimple 파일을 만들어 낼 수 있다.

해당 파일을 열어보면 D.1779라는 변수가 새롭게 선언되어 있는 것을 확인 할 수 있으며, 해당 변수는 x * y의 결과값을 임시로 담고 있는 용도로 사용하고 있음을 확인할 수 있다.

 

또한, 아래의 printf는 putstring로 바뀌었는데, 이는 printf 사용 시 format string을 사용하지 않는 경우 putstring과 동일한 취급을 하기 때문이다.

 

예 2) LLVM BIT 코드

c 코드는 GCC 대신 clang를 통해서 컴파일이 가능하다.

clang을 통해 컴파일을 진행하는 경우 실질적으로 속도가 빠르고, 다양한 기능이 플러그 인처럼 많이 제공되는데, 특히 최적화 기능이 잘 제공된다. 이러한 기능은 사용하기 쉽게도 제공해준다.

 

LLVM은 일리노이 대학교에서 만든 컴파일러로 자체 IR을 보유하고 있으며, 현재는 애플에서 관리하고 있다.

 

 

LLVM IR이라는 것이 있는데, 이것의 이름이 bit code이다. gcc의 경우 IR은 3개가 있지만, LLVM은 1개를 가지고 있다. 사실 중간 IR을 까보면 더 많은 종류의 IR이 존재하지만, 대부분 그림과 같이 1개라고 표현을 한다.

 

중간 언어가 1개 존재하고, 여러 가지 언어가 frontend로 붙는데, backend로 여러 가지가 붙을 수 있다. gcc도 여러 언어에 대한 컴파일을 지원하지만, LLVM은 목표 자체가 다양한 기능 제공하기 위함이다. LLVM은 bit code만으로 프론트와 백엔드만 잘 맞추고 디자인하여 넣으면 n*m의 조합으로 뭔가를 만들 수 있지 않을까?라는 철학으로 시작하였다.

 

따라서 인터페이스가 깔끔하며, 컴파일러에 대한 지식이 없어도 LLVM 백엔드를 쉽게 넣을 수 있다. c++ 코드로 작성되어 있으며, 코드가 깔끔하게 짜여 있기 때문에 연구하는 사람들이 진입 장벽이 있는 gcc보다 LLVM을 더 선호한다. 그러다보니 새롭게 등장하는 기법을 LLVM에 넣어 성능이 굉장히 높아졌다.

 

LLVM IR은 언어와 기계에 독립적이며, 현재 gcc 기반의 C/C++ frontend (“Clang”)와 X86계열, ARM, SPARC 등의 backend 및 JIT compiler 포함한다.

 

 

bit code의 생김새를 직접 확인해보자.

사진의 소스코드를 gcc나 clang로 컴파일하면 사진의 아래 부분과 같은 IR이 나오게 된다.

 

위 코드는 .ll의 파일 형식으로 .bc는 인코딩된 형태라 사람의 눈으로는 읽히지 않는다.

 

LLVM은 일반적으로 @, %와 같은 특수 문자들이 많이 등장한다.

@는 전역변수를 의미하는데, 함수 이름과 같은 변수는 어디서나 접근이 가능하기 때문이다. %는 지역변수를 의미한다.

 

i32는 항상 결과가 몇 바이트인지를 알려주는 역할을 한다. 즉 type와 크기에 대한 정보를 나타낸다. 이처럼 결과값에 대한 정보를 Low-level하게 명시해주어 기계어나 어셈블리 코드로 적절하게 변환할 수 있게 한다.

 

위 코드는 entry: 로 시작하여 return으로 끝난다.

각 변수 앞에는 i32라는 키워드가 존재하는데, 해당 키워드는 integer 타입이고, 32비트의 크기를 가지고 있다는 의미이다.

 

alloca라는 키워드를 통해 c 변수를 선언하는데, 선언할 때 변수의 크기와 align 키워드를 통해 4의 배수로 시작하는 주소를 달라고 요청한다.

 

또, 원 코드에서는 a + b를 return하는데, .ll 파일에서는 a + b의 값을 tmp1에 담아주고, tmp1을 리턴한다. 이때 add 명령어와 결과값의 크기인 i32, 더하는 피연산자가 차례로 등장한다.

 

또 다른 예시를 보자.

 

위 표에서 마찬가지로 전역, 지역 변수의 의미로 @와 %를 확인할 수 있다.

이때, @var에서 'global' 키워드를 확인할 수 있는데, 이는 글로벌 변수이며, alloca를 사용하지 않으며, 초기값으로 14를 설정해주고 있다.

 

main함수는 int를 리턴하기 때문에 int의 크기인 i32를 표현하고 있으며, nounwind는 exception이 없다는 의미이다.

main함수에서 var를 리턴하는데, 해당 변수를 바로 리턴하지 않고, 임시변수 %1을 생성하여 load를 통해 옮겨 담은 후 %1을 리턴한다.

 

 

위 예제는 Foo라는 struct에 대한 예제이다.

LLVM의 bit code가 구조체와 같은 복잡한 코드를 표현할 때 가독성이 좋아진다.

Foo 구조체 내부에 _len이라는 필드가 존재한다. 이러한 내용을 .ll에서 그대로 작성하고,

%Foo = type {i32} 명령어를 통해 Foo라는 변수에 32의 크기를 가지는 필드가 존재함을 나타낸다.

 

 

위 예제는 long 타입의 2차원 배열을 나타내는 예제이다.

i64는 long 타입의 크기를 나타내며, @z를 정의할 때 전역 변수를 의미하는 global 키워드와 i64크기의 변수가 3 * 3개가 있음을 나타내고 있다.(배열의 크기)

 

또한 zeroinitializer 키워드를 통해 배열의 모든 값을 0으로 초기화하고 있으며, i64는 8바이트이므로 8의 배수로 시작하는 주소를 요청하고 있다.

 

 

위 예제는 a를 할당하는 부분이 빠졌으므로 if에 대한 LLVM IR이다.

 로컬 변수인 a를 로드하여 임시변수 %0에 a의 값을 넣어준다.

이후 eq 키워드를 이용하여 0과 %0의 값이 같은지 비교하고 결과값을 %cmp에 넣는다.

 

%cmp가 true라면 %if.then 라벨로, false라면 %if.end 라벨로 jump한다.

이때, %1이라는 임시변수에 마찬가지로 %a의 값을 넣어주고

%1과 1을 더하여 %inc 변수에 넣어준 후, store 명령어를 통해 %inc 값을 %a에 저장한다.

이후 뒤의 코드가 더 실행되지 않게 하기 위해 %if.end 라벨로 브랜치 시켜준다.

 

⭐️정리

GCC GIMPLE은 c코드와 유사하고, LLVM IR에서는 변수를 나타내기 위해 @와 %를 사용한다. load, store와 같은 키워드로 인해 가독성이 나빠지지만, Low-level 관점으로 보면, 명시적으로 메모리 연산을 알려주기 때문에 기계 언어로 번역하기에 더 용이하다.

 

GCC는 RTL이라는 기계어로 번역할 수 있는 IR이 존재하므로, GIMPLE이가 더 high-level IR이다.

 

LLVM과 GCC는 상호 보완 관계를 가진다.