레지스터 할당(Register Allocation)은 컴파일러 최적화의 한 단계로, 프로그램에서 사용되는 지역 자동 변수와 식(expression)의 결과값을 제한된 수의 프로세서 레지스터에 효율적으로 배치하는 과정이다. CPU의 레지스터는 메모리(RAM)에 비해 접근 속도가 매우 빠르므로, 가능한 많은 변수를 레지스터에 할당할수록 프로그램의 실행 속도가 향상된다. 그러나 CPU가 제공하는 레지스터의 개수는 한정적이므로(예: x86 32비트 8개, 64비트 16개, ARM 64비트 31개 등), 컴파일러는 어떤 변수를 레지스터에 저장하고 어떤 변수를 메모리로 내보낼지(spilling) 결정해야 한다.
레지스터 할당은 적용 범위에 따라 세 가지로 구분된다. 기본 블록(basic block) 단위로 수행되는 지역 레지스터 할당(local register allocation), 함수나 프로시저 전체를 대상으로 하는 전역 레지스터 할당(global register allocation), 그리고 호출 그래프(call graph)를 통해 함수 경계를 넘나드는 프로시저 간 레지스터 할당(interprocedural register allocation)이 있다.
레지스터 할당의 주요 기술로는 그래프 색칠 할당(graph coloring allocation)과 선형 스캔(linear scan)이 대표적이다. 그래프 색칠 할당은 채틴(Chaitin) 등이 1981년에 처음 제안한 방식으로, 변수들의 활성 범위(live range) 간 충돌 관계를 간섭 그래프(interference graph)로 모델링한 후, 인접한 노드가 서로 다른 색(레지스터)을 갖도록 색칠하는 그래프 색칠 문제로 환원하여 해결한다. 채틴은 레지스터 할당 문제가 NP-완전(NP-complete) 문제임을 증명하였다. 선형 스캔은 1999년 포레토(Poletto) 등이 제안한 방식으로, 간섭 그래프를 구축하지 않고 변수의 활성 구간(interval)을 선형적으로 순회하며 탐욕적(greedy)으로 레지스터를 할당한다. 속도가 빠르다는 장점이 있어 Java HotSpot 클라이언트 컴파일러, V8, Android Runtime(ART) 등의 JIT 컴파일러에서 사용된다.
레지스터 할당 과정에서 모든 변수를 레지스터에 담을 수 없을 경우 일부 변수를 메모리로 내보내는 것을 스필링(spilling)이라고 하며, 이때 추가적인 로드(load) 및 저장(store) 명령어가 삽입된다. 또한 두 변수 간의 불필요한 복사(move) 명령어를 제거하기 위해 통합(coalescing) 기법이 사용되며, 이는 적극적 통합, 보존적 통합, 반복적 통합, 낙관적 통합 등의 다양한 휴리스틱이 존재한다. 그 외에도 재료화(rematerialization), 분할 할당(split allocation), 하이브리드 할당, 트레이스 레지스터 할당(trace register allocation) 등의 다양한 접근 방식이 연구되어 왔다.
