Register Allocation

Register Allocation은 virtual register를 physical register에 대응시키는 과정입니다.

이 과정에는 두가지 과정이 필요한데, 첫째는 interference graph, 둘째는 register coloring입니다.

어떤 두 register가 동시에 live하면 같은 physical register를 할당할 수 없습니다. 그리고 이런 상태를 두 register가 interfere한다고 표현하죠. 이렇게 register를 graph의 vertex로, interfere하는 두 register를 edge로 연결하여 표현하는 graph를 interference graph라고 합니다. 이것은 liveness analysis를 통해서 구해낼 수 있습니다.

register coloring은, 말 그대로 m개의 area(vertex, virtual register)에 k개의 color(physical register)를 대응시키는 과정입니다. 당연히 인접한(interfere하는) 두 area에는 같은 색을 칠해서는 안되겠죠. 만일 이것이 불가능하다면 spill을 해야만 하는데, 그렇게 되면 앞서 설명 드렸듯이 overhead가 발생해서 프로그램이 느려지게 되겠죠.

이 문제는 NP problem이므로 practical한 시간 안에 최선의 해를 구할 수가 없습니다. 다만, 근사한 해를 구하는 알고리즘을 이번에 설명드리려 합니다.

첫번째는 Chaitin's Algorithm입니다. 이 algorithm은 다음과 같은 순서로 진행됩니다.

1. Degree < k(the number of color)인 vertex를 찾아서 stack에 push한다. 그리고 이 vertex는 graph에서 삭제한다.

2. 만일 이것이 불가능하면, Degree가 최대인 vertex를 찾아서 graph에서 삭제하고 stack에 push한다. 이 때, 이 vertex는 spill 마커를 표시한다.

3. 1,2의 과정을 graph가 빌 때 까지 반복한다.

4. stack이 빌 때 까지 pop하며 색을 칠한다. 이 때, spill 마커가 표시된 vertex는 색을 칠하지 않는다.

하지만 이 algorithm은 항상 좋은 해를 내어놓지는 않습니다.
대표적인 예가 아래와 같은 경우가 있을 것입니다.

이 경우에는 chaitin's algorithm은 하나의 register를 spill하게 되겠죠. 하지만 실제로는 아래와 같은 해가 존재합니다.

이런 케이스를 위해 Chaitin's algorithm을 Briggs가 개선한 것이 바로 Chaitin-Briggs' algorithm입니다.

이 알고리즘은 간단한데, spill 마커를 가진 vertex 가 존재하더라도 색칠이 가능하다면 색칠을 해주는 것 뿐이니까요. 그렇게 함으로써 위와 같은 문제도 좀더 최선에 가까운 해를 구할 수 있게 됩니다.