Compiler 9 - Efficient Code generation

 이전의 코드 생성은 모두 가정(무한한 레지스터 등)에 의해 리소스를 낭비하였다. 따라서 이를 개선하는 방법이 필요하다.

따라서 memory access의 횟수를 줄여 실행속도를 증가시키고, 쓸모 없는 register의 사용을 줄여 리소스의 낭비 또한 방지한다. 이는 각 레지스터에 가능한 많은 변수를 가지고 있게 하는 방식으로 구현할 수 있다. 이를 위해서 서로 겹치지 않는 live variable을 하나의 레지스터가 공유하여 저장하도록 하면 된다. (덮어씌워도 더이상 사용되지 않는 변수라면 필요 없으므로)

이를 위해서 앞서 진행했던 live variable analysis를 global scope에서 모두 실행한다. 그리고 각 variable을 노드로 가지고, 동시에 존재하는 live variable 사이에 edge가 존재하도록 graph를 그린다. (Register Interference Graph - edge가 존재하는 노드 끼리는 서로 같은 레지스터를 공유하면 안된다)
이 RIG를 통해 연결되지 않은 노드는 같은 레지스터에 할당되어도 문제가 없다는 것을 알 수 있다. 따라서 전체 노드 수보다 적은 레지스터에 모든 변수를 저장할 수 있다. 그리고 TAC로 표현된 각 노드 변수에 서로 연결되지 않았다면 같은 레지스터를 할당하여 어셈브릴 코드를 완성할 수 있다.

- k colorable (transform into graph coloring problem)
서로 연결되지 않은 노드에 같은 색을 할당하여 색칠할 때 k개의 색이 필요하다면, k개의 레지스터에 모든 variable을 저장할 수 있다.
따라서 이를 그래프 색칠 문제로 확장하여 이해할 수 있다. 그러나 해당 문제는 NP-hard problem이므로 답은 존재하지만, 효율적으로 풀 수 있는 방법이 없다. (가장 간단한 것이 O(n*2^n))

따라서 이를 직접적으로 해결하기보다는 heuristic을 사용해야 한다.

- Heuristics for graph coloring (not optimal, but practical)
주어진 RIG에 대해 k보다 적은 neighbor(edge)를 가지는 노드를 제외한 RIG가 k-colorable하다면, 지우지 않은 오리지널 RIG도 K-colorable 하다는 것이다. (왜냐하면, k보다 작은 edge를 가지므로 연결되지 않은 노드의 색을 할당하면 되기 때문이다)

각 노드를 선택하여 제거하게 되면, 결국 연결된 edge가 줄어드므로 이런 과정을 반복하다보면 전체 노드를 k보다 작게 만들 수 있다. (k보다 작은 노드가 하나 이상 존재할 때)
따라서 순서대로 제거한 노드를 stack에 push하고, 모든 노드를 push했다면, 하나씩 pop하며 color를 할당할 수 있다. (이 때 서로 인접한 노드 사이에는 다른 색을 할당한다.) 만약 존재하는 노드와 연결되지 않은 색이 있다면, 해당 색을 할당하는 방식을 사용하면 최소 색을 사용하며 전체 그래프를 색칠할 수 있다.

-Spilling (if not k-colorable, we should access memory space)
만약 현재 가용가능한 레지스터의 개수 k가 RIG의 연결 수 보다 작아서 stack에 모든 노드를 push할 수 없다면, 할 수 있을 때까지 반복한 후에, 더 이상 들어가지 않는 노드에 대해 메모리 스왑을 진행해야 한다.
이를 spilling이라 하고, 레지스터의 수보다 live variable이 많으므로 어떤 variable은 메모리에 저장했다가 다시 불러와야 하는 과정이 필요하다는 것을 의미한다.

따라서 이 경우, 주어진 TAC에 대해서 spilling한 변수가 필요하고 사용될 때마다 해당 변수를 메모리에서 불러오고, 또 저장해야 하는 과정이 필요하다. (왜냐하면 해당 변수는 레지스터에서 계속 상주할 수 없기 때문) 따라서 lefthand side에서 사용된다면 store operation이, righthand side에서 사용된다면 load operation이 각각 이후와 이전에 삽입되어야 한다.

또한 각 사용되는 부분에 대해 서로 다른 이름을 부여 해야 한다. (load/store하여 사용될 때) 따라서 이들은 각 라인에서 사용되고 나면 더 이상 사용되지 않는 서로 다른 변수로 취급되게 된다. (spilled variable의 range를 한정하여 사용함으로써 live variable의 개수를 줄이는 것)
이를 통해 live variable analysis를 다시 진행하면 최대 k 개의 live variable을 동시에 가지게 바뀌게 된다.

만약 이렇게 한 후에도 레지스터의 수가 부족하다면 spilling을 더 진행할 수도 있다. 또, 어느 변수를 spilled로 설정할 것인지도 중요한 문제가 된다. (가장 많이 연결된 노드, 가장 적게 사용되는 변수, 루프 안에 들어가지 않는 변수 등... 정해진 정답은 없다)
또한 최대 변수 k는 동일하게 유지하면서 서로 다른 방식으로 색칠한 K-colored RIG가 존재할 수 있다.