SHPC 16 - Register Allocation

Register Allocation

어떤 register에 어떤 값을 할당할지 결정하는 것
Register allocation
- 프로그램의 각 포인트에 레지스터 내에 존재할 변수들의 집합을 고르는 것
Register assignment
- 어떤 변수 하나가 존재할 특정 레지스터를 고르는 것
레지스터의 optimal assignment를 찾는 것은 NP-complete 문제
- Computation 순서에 따라 레지스터가 적게 필요할 수도 있는데, 가장 적은 할당을 찾는 것은 어렵다 (Graph coloring problem으로 환원될 수 있음)
- 따라서 보통 Brute force로 구현하며, Chaitin’s Algorithm이 대표적

어떤 변수 $x$ 의 값이 flow graph에서 시작지점 $p$ 부터 시작하여 나오는 어떤 path에서 사용되면 변수 $x$ 가 특정 포인트 $p$ 에서 살아있다(live)라고 한다
Interference Graph를 만들기 위해서는 프로그램의 모든 포인트에서 살아있는 변수들을 찾는 것이 중요하다
- 두 개의 변수가 함께 살아있는 경우, 이 둘은 동일한 physical register에 allocation될 수 없음 (==interfere함)
Data flow analysis technique을 이용해 찾는다

Interference
- 변수 a와 b가 동일한 레지스터에 할당될 수 없는 상황
Interference graph 에 등장하는 노드들은 temporaries 혹은 symbolic registers 를 나타낸다
a와 b를 연결하는 edge가 존재 iff a와 b 사이의 interference가 존재한다
- 어떤 변수가 미래에 필요한 데이터를 그 시점에 가지고 있으면 해당 변수가 살아있다고 한다
- Non-move instruction(copy가 아닌 instruction)이 블록 n 내에서 a를 정의하는 경우(a:=…), 모든 $b \in o u t [n]$ 에 대해 (a, b) edge를 더한다
- Move instruction이 c를 a로 옮긴다면(a:=c), 모든 $b \in o u t [n] - {c}$ (a, b)를 더한다
- 살아있는 변수끼리 연결하되, move instruction에 대해서는 예외가 있다 정도로 생각할 수 있을 듯 하다
아래 예시

K-coloring problem을 아래와 같이 생각 가능
- Color의 갯수: 레지스터의 갯수 K
- Vertex: 변수
연결된(Interfere하는) 변수끼리는 같은 color(레지스터)를 할당받으면 안되는 문제이다
- 즉 graph coloring 문제로 환원 가능하며, 이것이 NP 문제이기 때문에 레지스터 할당 문제는 NP 문제이다
- 풀기 위해서는 linear approximation algorithm을 이용한다
K-coloring 문제 풀이에 실패할 경우, 일부 변수는 메모리에 저장해야 하는데 이를 spiling이라 한다

Build) interference graph G를 만든다
Simplify) K보다 더 적은 수의 이웃을 가진 노드를 삭제하고 스택에 넣는다
Spill) Degree가 K보다 큰 노드들만 남았다면, 몇개의 노드를 spilling 표시하고 스택에 넣은 뒤 다시 simplification을 진행한다. (아니면 계속 Simplify 하면 됨)
Select) 스택에서 하나씩 노드를 꺼내 그래프를 재구성하되, spilling 표시가 있는 경우 사용 가능한 color가 있는지 확인하고 없는 경우 실제로 spill 대상으로 표기한다
Start Over) 실제 spill 대상이 있으면 코드를 수정하고 다시 1번으로 간다