Compiler 개요3

Code Generation

Code Generation은 Instruction Selection, Register Allocation 그리고 Instruction Scheduling 단계로 나뉜다.

Instruction Selection
: Instruction Set을 정의하고 있는 System Architecture Spec.이 필요할 것이다. Architecture Spec.에서는 IR 기반의 각 연산 구문을 어떻게 하드웨어 어셈블리어로 매핑할 수 있을지에 대한 정보를 제공한다.

 

Register Allocation
: 제한된 레지스터를 효과적으로 배분할 수 있어야한다. 왜일까? 우선 레지스터를 불필요하게 많이 사용하여 레지스터간 의존관계가 생기게 되면 이것을 관리하는데 CPU cycle을 소요하게 된다. 예를 들어 R1과 R2가 항시 같아야 한다면 굳이 두 개의 레지스터를 계속해서 사용할 필요가 없다. 사용할 경우에는 항시 같은지를 체크해야하기에 비용이 들어가는 것이다. 그렇다면 레지스터는 최소한의 개수로 사용하는 것이 좋을까? 꼭 그러한 것도 아닐 듯 하다. 아는바와 같이 RISC기반의 CPU는 Fetch, Decode, Execution 그리고 Write의 연산을 한 사이클에 수행한다. 그런데 레지스터가 단 하나 뿐이라면 이러한 Pipe line 기반의 연산이 어려울 것이다. 즉, 가능한 레지스터를 많이 사용하되 그로인해 연산의 수가 증가하지 않는 방향으로 사용해야할 것이다. 바로 이것이 Register Allocation이다. 그렇다면 어떻게 이러한 작업을 수행하게 될까? 먼저 앞장에서 설명한 Web을 활용한다. Web에서는 각 연산에서 사용되는 변수들에 대해서 일단 무한정한 레지스터를 사용할 수 있다는 가정으로 표현한다. 물론 연산의 수를 늘려가면서까지 레지스터의 사용을 고려하지는 않는다. 이 Web을 기반으로 각 연산라인간의 Interference 관계를 그려낸다. 이를 Interference Graph라고 한다. Interference Graph에서 각 노드들이 edge로 연결되어 있다면 이것은 동일한 레지스터를 사용할 수 없다는 것을 가리킨다. 예를 들어서

 

a:=c;         // (1)
x:= a + 2;   // (2)
y:= a + z;   // (3)

 

(1)에서는 a가 define되었고 (2)에서는 x가 define되었다. 이 때 a와 x를 동일한 레지스터로 가져갈 수는 없을 것이다. 왜냐하면 (3)을 수행할 때 a와 x는 서로 다른 값을 가지게 될 수 있기 때문이다. 이와 같을 경우 a와 x는 interference 관계를 가지게 되고 edge로 연결되게 된다. 그리고 interference graph에서는 edge관계가 없을 경우에는 동일한 register를 가질 수 있으며 그렇지 않을 경우에는 각각 다른 register를 가지게 된다.

 

Instruction Secheduling

a:=b+c; (1)
b:=d*z; (2)

위의 코드에서 때로는 (1)과 (2)의 구문이 바뀔 경우 cpu cycle이 줄어들 수도 있다. 가장 대표적인 경우는 loop안의 연산을 loop밖으로 빼는 것이다. 그리고 항시 한 cycle동안 fetch, decode, execution 그리고 write가 모두 수행되는 것이 아니기에 가능한 이것을 유도하기 위해서 각 연산 라인을 이동할 필요도 있게 된다.