9. Liveness Analysis

Front-End Compilation

프로그램 코드를 직접 번역하는 것으로 무한개의 virtual register가 있다고 가정하고 진행을 한다.

하지만 실제로 physical register에 할당을 할 때는 갯수가 정해져 있기 때문에 이에 맞춰서 다시 진행해준다.

그리고 processor architecture에 맞추지 않아 불필요한 것이 들어갈 수 있다.

 

Back-End Compilation

virtual register를 실제 physical register로 mapping하는 부분이다.

불필요한 부분들을 다 제거하는 dead code elimination을 진행하여 아무 동작 안하고 선언만 되어있는 부분을 다 지운다.

 

Control Flow Graph (CFG)

graph의 노드는 instruction이고 edge는 다음에 실행될 수 있는 것들을 나타낸 것이다.

cfg의 예시

위의 예시를 보면 왼쪽의 코드를 기반으로 오른쪽의 CFG를 생성한 것이다.

CFG의 각각의 노드는 보면 코드의 한 줄씩 대응되고 조건에 따라 flow가 바뀌게 되면 변하는 노드로 edge를 이어서 그래프를 그린다.

이때 위처럼 명령어 한 줄씩 노드를 만드는 것이 아니라 basic block을 하나의 노드로 묶어서 CFG를 만들 수도 있다.

 

Dataflow Analysis

- Constant Propagation

아래의 예시와 같이 상수가 전달되는 경우 특별히 생길수 있는 예외사항이 없기 때문에 따로 변수를 선언하지 않고 합쳐서 사용할 수 있다.

예시1

다만 다음과 같이 오른쪽에서 미지의 값이 들어올 수 있는 경우 합치지 못하고 왼쪽과 같이 분리해서 써야한다.

예시2

- Register Allocation

무한개의 virtual register가 유한개의 real register에 할당되어야 하기 때문에 어떤 레지스터가 어떤 값을 가지고 있는지 알아야 한다.

이때 virtual register는 같은 real register에 동시에 매핑될 수 없다.

 

Terminology

- out-edges: 다음 노드로 나가는 edge

- in-edges: 이전 노드에서 들어오는 edge

- pred[n]: n노드의 모든 이전 노드

- succ[n]: n의 모든 다음 노드

- assignment: 변수나 임시에 대한 정의

- occurrence: 할당된 변수가 사용하는 변수 오른쪽의 값

- def[n]: 정의된 변수

- usd[n]: node n이 사용하는 변수의 집합

- def[v]: 변수를 정의한 노드들

- use[v]: 변수를 사용한 노드들

- live: def를 지나지 않으면서 edge를 통해 정의된 다음부터 사용하는데 까지 도달할 수 있는 경우

- live-in: in-edge 쪽에서 살아남는게 들어오는 것

- live-out: out-edge쪽으로 빠져나가는 것

 

Liveness Analysis

liveness정보는 use와 def를 사용해서 계산할 수 있다.

1. 만약 variable이 use[n]에 있으면 node n에서 live-in이다.

2. 노드n에서 live-in이면 pred[n]의 모든 노드m에서 live-out 되어서 나온다.

3. n에서 live-out되고 def[n]에 없고 n에서 live-in된다면 n노드가 필요가 없더라도 들어와야한다.

위내용을 수식으로 쓰면 아래와 같다.

 

$$\begin{matrix} in[n] &=& use[n] \cup (out[n] - def[n]) \\ out[n] &=& \cup_{s \in succ[n]} in[s] \end{matrix}$$

 

그리고 위의 알고리즘을 바탕으로 liveness analysis를 진행하면 다음과 같이 in과 out을 구할 수 있다.

이때 처음에는 각 노드의edge가 한 번에 파악이 되지 않으므로 변화가 없을 때 까지 반복을 하게되면 구할 수 있다.

 

Register Allocation

liveness analysis을 진행한 결과를 바탕으로 이제 register를 할당해줘야한다.

먼저 in, out, use, def와 같은 각 프로그램의 지점에서 사용될 변수들의 집합을 계산해준다.

그리고 interference graph를 그려서 변수가 동시에 live한다고 했을 때 같은 레이스터에 할당 될 수 없는 변수를 식별한다.

마지막으로 interference graph를 기반으로 실제 레지스터를 색칠하여 각 노드를 가능한 최소의 색으로 칠하고 두 인접한 노드는 다른 색을 가지게 한다.