정의
레지스터 할당(Register allocation)은 컴파일러가 기계어 코드를 생성할 때, 프로그램이 사용하는 변수와 임시값을 물리적 레지스터에 효율적으로 매핑하는 과정이다. 이 과정은 제한된 수의 레지스터 자원을 최적 활용하여 실행 속도를 향상하고 메모리 접근을 최소화하는 것을 목표로 한다.
개요
컴파일 과정에서 고수준 언어의 변수는 중간 표현(IR) 단계에서 무한히 많은 가상 레지스터에 할당된다. 최종 코드 생성을 위해서는 이러한 가상 레지스터를 실제 하드웨어가 제공하는 제한된 수의 물리 레지스터에 매핑해야 한다. 레지스터 할당은 일반적으로 다음과 같은 단계로 이루어진다.
- 라이브 변수 분석(Liveness analysis) – 각 명령어 시점에서 어떤 변수(또는 가상 레지스터)가 아직 사용될 가능성이 있는지 파악한다.
- 간섭 그래프(Interference graph) 구축 – 라이브 변수 간에 동시에 살아있는 경우를 간선으로 연결한 무방향 그래프를 만든다.
- 그래프 색칠(Graph coloring) – 간섭 그래프의 정점을 물리 레지스터 색으로 색칠한다. 서로 인접한 정점은 같은 색을 가질 수 없으며, 색이 부족하면 스필(Spill)이라 하여 메모리(스택)로 옮긴다.
- 코드 삽입 – 스필이 발생한 경우, 메모리 로드·스토어 삽입을 통해 레지스터와 메모리 간 데이터를 이동한다.
대표적인 레지스터 할당 알고리즘으로는 Chaitin’s algorithm, Iterated register coalescing, Linear scan allocation 등이 있다. 각각은 구현 복잡도와 할당 효율 사이에 트레이드오프가 존재한다.
어원/유래
‘레지스터’(register)는 라틴어 regesta(목록, 기록)에서 유래한 영단어 register를 한글 표기한 것이다. ‘할당’은 한국어 동사 할당하다에서 온 명사형으로, ‘배정한다’는 의미를 갖는다. 따라서 ‘레지스터 할당’은 “레지스터에 배정한다”는 뜻을 직역한 용어이며, 컴퓨터 과학 분야에서 1970년대 초반부터 사용되어 왔다.
특징
| 구분 | 내용 |
|---|---|
| 목표 | 실행 성능 향상, 메모리 접근 감소 |
| 제약 | 물리 레지스터 수 제한, 변수 간 간섭 관계 |
| 주요 기법 | 라이브 변수 분석, 간섭 그래프, 그래프 색칠, 스필 처리 |
| 알고리즘 종류 | Chaitin’s, Iterated coalescing, Linear scan 등 |
| 성능 영향 | 할당 효율에 따라 코드 크기·속도·전력 소비가 크게 달라짐 |
| 실제 적용 | GCC, LLVM, Microsoft Visual C++ 등 주요 컴파일러에 구현 |
관련 항목
- 컴파일러 – 고수준 언어를 기계어로 변환하는 소프트웨어 시스템. 레지스터 할당은 컴파일러 백엔드의 핵심 단계 중 하나이다.
- 라이브 변수 분석(Liveness analysis) – 변수의 생존 구간을 파악하는 데이터 흐름 분석 기법.
- 간섭 그래프(Interference graph) – 레지스터 할당을 위한 그래프 모델.
- 그래프 색칠(Graph coloring) – 간섭 그래프를 물리 레지스터에 매핑하는 알고리즘 이론.
- 스필(Spill) – 레지스터 부족 시 메모리(스택)로 변수 값을 옮기는 과정.
- Linear scan allocation – 빠른 할당을 위해 순차적으로 레지스터를 배정하는 간단한 기법.
- LLVM – 현대적인 컴파일러 프레임워크로, 다양한 레지스터 할당 패스를 제공한다.
본 항목은 기존 학술 자료와 주요 컴파일러 구현 문서를 기반으로 작성되었으며, 최신 연구 동향에 따라 내용이 추가·수정될 수 있다.