[컴파일러 이론] 9. Code Generation - Stack Machine

아래처럼 간단한 코드는 어셈블리 코드로 바꾸기 쉬울 것이다.

하지만 함수 호출등 코드가 복잡해지면 어려워진다.

---

Stack Machine

위의 어려움을 조금 해소해주기 위해 만들어진 방법이 stack machine이다.
일단 모든 데이터가 스택에 저장되어있다고 가정하고 진행해보자.
이 가정이 없는 경우에 대해서는 바로 이어서 다룰 것이다.
 
stack machine은 n개의 피연산자를 스택에서 pop하고 이 값들을 이용해 operation(명령어)를 계산한다.
그 이후 그 결과를 다시 스택에 push한다.
 
간단한 설명이지만 약간 추상적이므로 예시를 보고 확실히 이해를 해보자.
아래 예시는 7+5를 계산하는 예시이다.
2번의 load(pop), 1번의 store(push)로 계산할 수 있다.

그러나 덧셈 한번에 3번의 메모리 연산이 수행되었다. 비효율적이다.
 

Register 사용

이제는 가정을 벗어나 레지스터까지 사용해보자. 
레지스터는 메모리인 스택에 비해 훨씬 빠르기 때문에 효율적인 코드 실행이 가능하다.
스택의 top을 레지스터에 저장하는 것이다. 이 레지스터의 이름을 acc라고 하자.
 
위의 add연산이 이제 acc와 스택의 top을 더해 acc에 저장하는 것이 된다.
이 과정은 메모리 연산이 1번이면 된다.
 
이후 설명을 위해 네가지 표기법을 먼저 언급하면
1. acc <- i : i라는 정수값을 acc레지스터에 저장한다.
2. push acc : acc의 값을 스택에 넣는다.
3. pop : 스택의 가장 위 값을 꺼낸다.
4. add : 스택의 가장 위 값을 기존 acc값에 더해 acc에 저장한다.
 
아래는 7+5를 레지스터를 사용해서 계산하는 그림이다.

 
일반적으로 $op(e_1, e_2, ... e_n)$으로 표기한다.
각 $e_i$는 expression이다. 
n개의 인풋을 받아 op를 계산하지만, 하나는 acc에 저장되어있을 것이므로 pop은 n-1번 하면된다.
아래는 3+(7+5)를 계산하는 과정이다.

 
기계어 생성은 컴퓨터의 아키텍처에 따라 조금씩 다르다.
이 글에서는 컴퓨터 구조론에서 많이 사용하는 MIPS아키텍처를 기준으로 code generation을 알아보자.
어느 정도의 컴퓨터 구조론 지식이 있다고 가정한다.
 
acc레지스터라고 불렀던 것을 $a0 라고 표시한다.
스택은 주소가 낮아지는 방향으로 쌓인다고 가정하고, $sp는 아직 데이터가 없는 새로 쌓일 곳의 주소를 가리킨다고 하자.
주소가 커질수록 스택을 내려가는 것이므로 $sp+4 가 스택의 top 내용을 가리킨다.
아래 명령어들을 주로 사용해 설명할 것이다.

7+5를 stack machine코드를 MIPS명령어로 바꾸는 예시이다.

cgen함수는 상수에 대해서는 acc <- i 와 같지만, 인자로 expression이 올수도 있게 확장한 개념이다.

 
하나 의문이 드는 것은 레지스터를 지금 하나 사용하고 있어서 스택에 접근이 필요하긴 한 상황인데, 이것도 레지스터를 더 써서 더 빠르게 할 수 있지 않을까? 라는 것이다.
아래는 스택에 push하는 대신 $t1 레지스터를 추가로 사용한 것이다.
하지만 이렇게 하면 cgen(e2)에서 $t1을 덮어쓸 수도 있어 위험하다.

크게 다르지는 않지만 분기의 경우에 코드가 어떻게 생성되는지의 예시이다.

 더하기, 빼기, 분기(if) 같은 코드가 아닌 함수 호출에 대해서는 어떻게 code generation이 이루어지는지 알아보자.

아래는 f(x,y)를 호출했을 때 AR의 상태이다.

 

일반적인 함수 f(e1,e2,...,en){ local var}에 대해 위와 같은 AR을 만드는 코드를 살펴보자.

 

먼저 call하기전 caller에서 돌아가는 코드가 있다.

<caller side>

fp를 스택에 저장한다.(old $fp)

그 다음 함수의 파라미터들을 역순으로 스택에 저장한다. 즉 첫번째 인자가 스택의 가장 위에 놓여진다. (en,...,e2,e1)

이후 callee side로 넘어가는 jump문을 실행한다.

jal이 호출되며 호출된 함수가 끝나고 되돌아갈 주소가 자동으로 $ra에 저장되고 callee로 실행이 넘어간다.

<callee side>

현재 fp는 이전 caller AR의 fp이므로 callee에 맞게 fp를 옮겨준다. ( mv $fp $sp)

$ra의 값을 스택에 넣어놓는데, 이 함수 내부에서 다른 함수가 또 호출되면 $ra레지스터의 값이 덮어써질 수 있기 때문이다.

이제 로컬 변수 및 함수에 대한 cgen()을 호출해 처리한다.

처리했으면 위에서 스택에 저장했던 return address를 다시 $ra에 불러온다.

이후 sp를 변경해 이 함수를 실행하며 스택에 쌓았던 로컬 변수들의 공간을 다시 되돌린다.

fp도 old fp로 다시 바꿔준다.

 

---

Temporary Variables

컴파일러는 어떤 함수가 실행되면서 임시변수가 몇개나 필요할지 미리 알 수 있다.

아래 사진의 왼쪽 피보나치 함수를 보면, x-1,x-2,fib(x-1),fib(x-2)등을 저장할 변수가 각각 하나씩 있어야 할 것 같다.

하지만 오른쪽에서 보듯이 변수 2개로 해결할 수 있다.

몇개가 필요할지 그 개수를 계산하는 방법을 알아보자.

 

e라는 표현식을 다룰 때 필요한 임시변수의 개수를 NT(e) 라고 하자.

NT(e1 + e2) = max(NT(e1), NT(e2) + 1) 이다.

e1과 e2의 내용이 동시에 계산되는 것이 아니기 때문에

예시로 e1에서 만약 5개의 변수를 썼고, e2에서 4개의 변수가 필요하다면 e1이 썼던 변수를 재사용하면 되므로 총 필요한 변수 개수는 max(5,4)이다. 

하지만 +1 이 붙어있는 것을 볼 수 있는데, 전체 식 e1+e2를 계산할 때 e1의 계산 값을 저장할 변수는 하나 더 있어야하기 때문이다.

따라서 위 예시에서 e1이 계산될 때 5개의 변수가 사용되고, 이 e1의 값을 저장하는데 1개의 변수가 사용되는 중에, e2가 계산 되는 동안 4개의 변수가 필요하다. 

따라서 max(5,4+1) = 5 가 총 필요한 변수의 개수가 된다.

 

몇가지 계산 식이 있다.

1. NT(e1+e2) = max(NT(e1), NT(e2)+1)

2. NT(e1-e2) = max(NT(e1), NT(e2)+1)

3. NT( if (e1==e2) {e3} else {e4} ) = max(NT(e1), NT(e2)+1, NT(e3), NT(e4))

4. NT( func(e1,...,en) ) = max(NT(e1), ..., NT(en))

5. NT(NUM) = 0

6. NT(id) = 0

 

1,2번은 방금 위에서 설명한 내용으로 이해가 될 것이다.

3번은 e1==e2를 계산할 때 e1의 값을 기억하고 있어야 비교를 하기 때문에 +1이 되었다.

하지만 비교가 끝나면 비교 값이 true/false 중에 어떤 것인지는 기억할 필요 없이 그냥 계산 직후 필요한 코드(e3 또는 e4)로 이동하고 까먹어도 된다. 따라서 뒤에는 +1이 붙지 않았다.

4번은 각 e1~en의 결과가 이 ar에 저장되는 것이 아니고 다음 ar에 저장되기 때문에 +1 이 없다.

 

아래는 피보나치 함수에서 NT값을 써놓은 예시이다.

---

Code Generation using NT

이제 cgen(e)함수를 cgen(e, nt)로 확장시키자.

e는 기존대로 표현식이고 nt는 이용가능한 임시변수의 위치이다.

그러면 왼쪽처럼 썼던 코드를 오른쪽처럼 간단하게 바꿀 수 있다.

이 새로 바뀐 간단한 코드의 작동을 알아보자.

위에서 얘기했듯 NT를 구하는 것은 미리할 수 있다.

이 예시에서 NT(e1+e2)는 5인것을 이미 알기때문에 미리 5칸의 공간을 확보해놓고 코드가 실행된다.

 

1번과정에서 e1을 계산하는데 임시변수 3개가 필요했다.

결과를 얻은 후에는 이 결과를 저장할 변수 1개를 남기고 나머지는 필요없어진다.

3번과정에서 nt+4의 위치에서부터 e2가 계산된다.

e2는 4개의 변수가 필요하다.

---

IR (Intermediate Representation)

IR은 코드와 기계어 사이에 위치하는 표현방식이다.

이건 cpu나 프로그래밍 언어에 독립적인 방식이다.

프론트엔드에서 c언어등의 언어를 받아서 AST를 만들고,이를 IR이 기반으로 만들어진다.

앞으로 high level assembly를 IR로 사용할 것이다.

기본적으로 어셈블리이지만 push 등 여러개의 어셈블리 명령어가 필요한 명령어라도 그냥 push라는 하나의 명령어로 사용하는 방식이다.