[CP] 3-Addr Code

2023학년도 2학기 충남대학교 조은선 교수님의 컴파일러개론 수업 정리자료입니다.

 

 

 

 

📁 N-tuple, 3-주소 코드(Quadruple)

N-tuple은 보통 quadruple(4-tuple)을 많이 사용하는데, quadruple은 피연산자 두개와 결과값을 위해 memory address가 3개 필요하다. 때문에 이를 3-address code(3-주소 코드)라고도 부른다.

 

3-addr코드는 OP에 단 하나의 연산자가 와야한다는 점과, 기계어가 가지는 피연산자 및 주소의 개수가 3개 미만이라는 점에서 C코드와 비슷하다.

 

때문에 -e나 b+c와 같은 코드도 3-addr code로 표현이 가능하다.

 

하지만 C언어와 같은 하이레벨 코드는  a = (b+c) * (-e)처럼 한번에 연산자가 많이 나올 수 있어서, 이를 3-addr 코드로 변환하기 위해서는 중간에 임시로 결과를 담아놓을 메모리공간이 필요하다. 이런 문제를 해결하기 위해, 컴파일러는 기존에 없는 a, b, c, e가 아닌 새 임시 변수를 생성한다. 위 예시에서는 가시적으로 t1 t2이라고 표현하였다. 

 

 

 

3-주소 코드의 instruction 종류는 아래와 같다.

 

1. Assignment instructions

load, store, symbolic address와 같이 메모리 공간에서 주소를 주고 값을 가져온다던지, 메모리 공간의 주소에 store한다던지, 변수의 주소값을 가져오는 등의 로우레벨 연산을 할 수 있다.

 

 

2. Flow of control

 

 

3. Function call

 

 

즉 일종의 가상 기계의 instruction들이라고 가정할 수 있다.

 

 

 

3-주소 코드의 피연산자는 개발자가 준 일반적인 프로그램 변수, 상수, literals, 임시변수 중 하나이다.

 

이때 임시변수에는 location을 새로 할당하며, 고급 프로그래밍언어만큼 3-주소 코드가 expressive하지 못하기 때문에 중간 값 저장을 위해 사용한다.

 

 

 

 

 

📁 3-addr code의 예시

 

3-addr code의 예시에는 GCC gimple과 LLVM IR이 있다.

 

*

 

Gcc의 gimple. gcc는 c 컴파일러. 중간코드가 최소 세개 존재. generic, gimple, rtl. input으로 C 뿐만 아니라 C++, Objective C, Ada 등 받을 수 있음. 타겟 머신 코드도 여러가지 있음. gcc가 컴파일러라고 부르기 보단 compiler generation framework라고 부르는게 더 정확함. gcc에서 c 컴파일러를 찾기 위해서는 폴더를 타고 들어가야함.

 

generic은 HIR. 소스코드 ast에서 거의 바로 나오는 형태라 트리형태.

rtl도 머신코드를 생성해야해서 트리형태의 ir.

generic에서 하는 일은, 여러 포트와 c++들을 받아서 결과적으로 그 언어 자체적인 고유 기능들을 언어중립적으로 표현하고, 그에 맞는 AST를 적절하게 만들어줌.

RTL은 결과적인 기계어 코드를 만들어주기 위해 일련의 파라미터를 받아 그 파라미터에 따라 코드 제너레이션을 하는데 특화됨.

 

gimple은 3-addr 코드의 대명사. gimple을 열어보면 D.1954처럼 이상한 변수를 볼 수 있는데, 이게 임시변수. gimple_assign이라는 표현 형태를 보면, 네가지의 파라미터를 주는걸로 quadraple인 것을 알 수 있음. 

*

 

 

1. GCC GIMPLE

GCC는 compiler generation framework로, C언어의 컴파일러 역할을 하며 generic, gimple, RTL과 같이 최소 3개의 중간코드를 갖고있다.

 

위 중간코드는 C 뿐만 아니라 C++, Objective C, Ada 등 다른 하이레벨 언어 코드를 input으로 받을 수 있으며, 타겟 머신 코드도 여러 종류가 있다.

 

 

Generic은 소스코드 AST에서 거의 바로 나오는 트리형태의 HIR이다. 여러 포트와 c++들을 받아서 결과적으로 그 언어 자체적인 고유 기능들을 언어중립적으로 표현하고, 그에 맞는 AST를 적절하게 만들어준다.

 

GIMPLE은 대표적인 3-addr 코드이다. 내부를 살펴보면 D.1954와 같은 변수를 확인할 수 있는데, 이들이 임시변수이다.

gimple_assign 표현을 살펴보면, 파라미터를 4개 전달하고 있으므로 quadraple임을 알 수 있다.

 

RTL은 머신코드를 생성하는 트리형태의 LIR이다. 결과적인 기계어 코드를 만들어주기 위해 일련의 파라미터를 받아 그 파라미터에 따라 코드 제너레이션을 하는데 특화되었다.

 

 

 

위와 같이 main() 코드가 있다고 하자. gcc -fdump-tree-all test.c와 같은 명령어를 사용하여 오른쪽 아래와 같은 파일을 만들 수 있다. 해당 파일에서 D.1779라는 변수를 확인할 수 있는데, 해당 임시변수는 x*y 과정에서 x와 y를 곱한 결과값을 보관하는 용도로 사용되고 있음을 알 수 있다.

 

 

 

 

2. LLVM BIT 코드

 

C언어 컴파일러에는 gcc 외에도 clang이라는 도구가 있다. clang은 실질적으로 속도가 빠르고, 최적화와 같은 다양한 기능이 들어있으며 사용하기도 쉽다는 장점이 있다.

LLVM의 IR을 BIT 코드라고 부른다. GCC와 달리 중간코드가 Common Optimizer 단 하나 존재한다. 언어와 기계에 독립적이며 여러가지 언어가 input 및 output 대상이 될 수 있다는 장점이 있다.

 

 

 

LLVM IR인 BIT 코드의 예시를 살펴보자.

아래 예시에서, 상단의 소스코드를 GCC나 Clang으로 컴파일하면 하단과 같은 중간코드가 나온다. 이때 하단의 코드는 .ll의 확장자를 가지고 있으며, .bc 확장자로 인코딩 할 경우 사람이 읽을 수 없다.

 

• @ : 전역적으로 쓰이는 변수 혹은 함수명을 의미한다.
• % : 로컬하게 사용되는 변수를 의미한다.
• i32 : 변수의 타입과 크기에 대한 정보를 알 수 있따. i32는 결과값, 즉 allocation한 변수의 타입이 integer이고 크기가 32bit임을 알려준다.

 

위 비트코드를 살펴보면 entry 부분에서 시작해서 return(ret)로 끝난다.

변수 선언 시에는 alloca 키워드와 변수의 타입 및 크기를 함께 적고, align 키워드와 시작 주소 정보를 적어 표현한다. alloca i32, align 4의 의미는 integer 타입 및 32bit 크기의 변수를 시작주소가 4의 배수인 위치에 할당하라는 뜻이다.

a + b를 반환할때는 직접 바로 반환하지 않고 tmp1이라는 임시변수에 담은 후 반환한다.

 

 

더 복잡한 예시를 살펴보자.

 

• 글로벌 변수의 경우에는 alloca하지 않고 global이라는 키워드를 사용한다. global i32 14의 뜻은 integer 32bit 글로벌변수의 초기값이 14라는 의미이다.
• main()은 integer타입을 리턴하기 때문에 리턴타입 부분에 i32라고 작성한다.
• nounwind란 exception이 없는 함수라는 뜻이다.
• struct Foo { size_t _len; }은 struct 자료구조를 나타낸다. 내부에 _len이라는 필드가 있다는 뜻이며, %Foo = type {i32}는 Foo 내부에 32bit만큼의 크기를 가지는 integer 필드 하나가 존재한다는 뜻이다.
• long 타입의 셀을 가지는 2차원배열 z는 long 타입 변수를 나타내는 i64를 사용하여 나타낸다.
• zeroinitializer는 0으로 초기화하라는 뜻이다.
• align 8은 셀 하나의 크기가 8byte이므로 8의 배수에 맞춰 시작주소를 정하라는 의미이다.
• icmp는 boolean값을 반환한다.
• eq i32 %0 0은 %0과 0을 비교하라는 의미이다.
• br i1 %cmp, label %if.then, label %if.end은 만약 cmp가 true라면 %if.then label로 jump하고, false면 if.end로 jump하라는 의미이다.
• br label %if.end은 if.end 라벨로 점프하라는 의미이다.

 

 

 

gcc gimple은 c코드와 매우 유사하고, LLVM IR은 %,@ 등이 나타남. load, store 등등 때문에 가독성이 더 안좋음. 하지만 로우레벨하게 보면 명시적으로 메모리 연산을 알려주므로 기계언어로 번역하기 더 용이함. gcc에는 RTL이라는 기계어로 번역할 수 있는 중간언어가 존재하므로 gimple이 좀 더 하이레벨. LLVM과 gcc는 서로 보완하는 관계.

 

 

 

 

 

📝 문제 풀어보기

n = 0;
while (n < 10) {
	n = n+1;
}
n = n*2

 

위 코드를 if, goto와 새로운 label을 써서 변환해보시오. 단 {} 와 같은 블럭구조는 사용하지 마시오.