레지스터 할당

컴파일러 최적화에서 **레지스터 할당**(Register allocation)은 지역 자동 변수와 식의 결과를 제한된 수의 프로세서 레지스터에 할당하는 과정이다. 레지스터 할당은 기본 블록(지역 레지스터 할당) 전체, 함수/프로시저 전체(전역 레지스터 할당), 또는 호출 그래프를 통해 트래버스되는 함수 경계(프로시저 간 레지스터 할당)를 넘어 발생할 수 있다. 함수/프로시저별로 수행될 때, 호출 규약은 각 호출 사이트 주변에 저장/복원 삽입을 요구할 수 있다.
# 컨텍스트

## 원리
{| class="wikitable floatright" |+ 가장 일반적인 아키텍처의 다양한 범용 레지스터 수 |- ! 아키텍처 ! scope="col" | 32비트 ! scope="col" | 64비트 |- ! scope="row" | ARM | 15 | 31 |- ! scope="row" | 인텔 X86 | 8 | 16 |- ! scope="row" | MIPS | 32 | 32 |- ! scope="row" | POWER/파워PC | 32 | 32 |- ! scope="row" | RISC-V | 16/32 | 32 |- ! scope="row" | SPARC | 31 | 31 |- |} 많은 프로그래밍 언어에서 프로그래머는 원하는 만큼 변수를 사용할 수 있다. 컴퓨터는 CPU의 레지스터를 빠르게 읽고 쓸 수 있으므로, 더 많은 변수가 CPU 레지스터에 있을 때 컴퓨터 프로그램은 더 빠르게 실행된다.p=48 또한, 레지스터에 접근하는 코드는 때로는 더 간결하여 코드가 더 작아지고, 메모리 대신 레지스터를 사용하면 더 빠르게 가져올 수 있다. 그러나 레지스터의 수는 제한적이다. 따라서 컴파일러가 코드를 기계어로 번역할 때, 제한된 수의 CPU 레지스터에 변수를 어떻게 할당할지 결정해야 한다.p=242p=14:1 모든 변수가 동시에 사용 중(또는 "활성")인 것은 아니므로, 프로그램의 수명 동안 특정 레지스터는 다른 변수를 저장하는 데 사용될 수 있다. 그러나 동시에 사용 중인 두 변수는 변수 중 하나를 손상시키지 않고 동일한 레지스터에 할당될 수 없다. 모든 변수를 담을 레지스터가 충분하지 않으면 일부 변수는 RAM으로 이동되거나 RAM에서 가져올 수 있다. 이 과정을 레지스터 "스필링"(spilling)이라고 한다.p=47 프로그램의 수명 동안 변수는 스필링될 수도 있고 레지스터에 저장될 수도 있다. 이 변수는 "분할"(split)된 것으로 간주된다.p=1 RAM에 접근하는 것은 레지스터에 접근하는 것보다 훨씬 느리므로access-date=8 January 2019 컴파일된 프로그램은 더 느리게 실행된다. 따라서 최적화 컴파일러는 가능한 한 많은 변수를 레지스터에 할당하는 것을 목표로 한다. 높은 "레지스터 압력"은 더 많은 스필링 및 재로드가 필요하다는 기술 용어이며, 브라운(Braun) 등이 "명령어에서 동시에 활성 상태인 변수의 수"로 정의했다.p=174 또한, 일부 컴퓨터 설계는 자주 접근하는 레지스터를 캐시한다. 따라서 가능한 한 `move` 명령어의 원본과 대상에 동일한 레지스터를 할당함으로써 프로그램을 더욱 최적화할 수 있다. 컴파일러가 정적 단일 대입 형식(SSA)과 같은 중간 표현을 사용하는 경우 특히 중요하다. 특히 SSA가 완전히 최적화되지 않은 경우 인위적으로 추가적인 `move` 명령어를 생성할 수 있다.
## 레지스터 할당의 구성 요소
따라서 레지스터 할당은 런타임에 변수를 어디에 저장할지, 즉 레지스터 내부 또는 외부에 저장할지 선택하는 것으로 구성된다. 변수를 레지스터에 저장해야 하는 경우 할당자는 이 변수가 어떤 레지스터에 저장될지 결정해야 한다. 궁극적으로 또 다른 과제는 변수가 동일한 위치에 얼마나 오랫동안 머물러야 하는지 결정하는 것이다. 레지스터 할당자는 선택된 할당 전략에 관계없이 이러한 과제를 해결하기 위해 일련의 핵심 동작에 의존할 수 있다. 이러한 동작은 여러 범주로 분류할 수 있다.p=21 ; 이동 삽입: 이 동작은 레지스터 간의 이동 명령어 수를 늘리는 것으로, 즉 하나의 레지스터 대신 변수가 수명 동안 다른 레지스터에서 활성화되도록 하는 것이다. 이는 분할 활성 범위 접근 방식에서 발생한다. ; 스필링: 이 동작은 변수를 레지스터 대신 메모리에 저장하는 것이다.p=103 ; 할당: 이 동작은 변수에 레지스터를 할당하는 것이다.p=26 ; 통합과 집약: 이 동작은 레지스터 간의 이동 횟수를 제한하여 총 명령어 수를 제한하는 것이다. 예를 들어, 여러 메서드에서 활성화되는 변수를 식별하고 해당 수명 동안 하나의 레지스터에 저장하는 방식이다.p=103 많은 레지스터 할당 접근 방식은 하나 이상의 특정 동작 범주에 최적화되어 있다. 인텔 386 레지스터
## 레지스터 할당에서 발생하는 일반적인 문제
레지스터 할당은 다양한 레지스터 할당 접근 방식으로 해결(또는 피할 수 있는) 여러 문제를 제기한다. 가장 일반적인 세 가지 문제는 다음과 같다. ; 별칭(Aliasing): 일부 아키텍처에서는 한 레지스터에 값을 할당하면 다른 레지스터의 값에 영향을 줄 수 있다. 이를 별칭이라고 한다. 예를 들어, X86 아키텍처는 16비트 또는 8비트 레지스터로도 사용될 수 있는 4개의 범용 32비트 레지스터를 가지고 있다.archive-date=2019-05-25 이 경우 eax 레지스터에 32비트 값을 할당하면 al 레지스터의 값에 영향을 준다. ; 사전 색칠(Pre-coloring): 이 문제는 일부 변수를 특정 레지스터에 강제로 할당하는 행위이다. 예를 들어, PowerPC 호출 규약에서 매개변수는 일반적으로 R3-R10으로 전달되며 반환 값은 R3으로 전달된다.url=https://developer.apple.com/library/archive/documentation/DeveloperTools/Conceptual/LowLevelABI/100-32-bit_PowerPC_Function_Calling_Conventions/32bitPowerPC.html ; NP-문제: 채틴(Chaitin) 등이 레지스터 할당이 NP-완전 문제임을 보였다. 그들은 임의의 그래프에 대해, (레지스터를 노드로, 기계 레지스터를 사용 가능한 색상으로 나타내는) 프로그램에 대한 레지스터 할당이 원래 그래프에 대한 색칠이 되도록 프로그램을 구성할 수 있음을 보여줌으로써 그래프 색칠 문제를 레지스터 할당 문제로 환원시킨다. 그래프 색칠이 NP-난해 문제이고 레지스터 할당이 NP에 속하므로, 이는 문제의 NP-완전성을 증명한다.p=4
# 레지스터 할당 기술
레지스터 할당은 코드의 기본 블록에서 발생할 수 있다. 이를 "지역적"이라고 하며, 호르위츠(Horwitz) 등이 처음 언급했다.p=43 기본 블록에는 분기가 없으므로 할당 과정은 빠르다고 생각된다. 레지스터 할당에서 제어 흐름 그래프 병합 지점의 관리가 시간 소모적인 작업으로 드러나기 때문이다.p=566 그러나 이 접근 방식은 전체 컴파일 단위(예를 들어 메서드 또는 프로시저)에서 작동하는 "전역적" 접근 방식만큼 최적화된 코드를 생성하지 못한다고 생각된다.p=92
## 그래프 색칠 할당
그래프 색칠 할당은 레지스터 할당을 해결하는 지배적인 접근 방식이다.p=1p=316 이는 채틴(Chaitin) 등이 처음 제안했다.p=47 이 접근 방식에서 그래프의 노드는 레지스터 할당 후보인 활성 범위(변수, 임시 변수, 가상/심볼릭 레지스터)를 나타낸다. 간선은 충돌하는 활성 범위, 즉 적어도 하나의 프로그램 지점에서 동시에 활성 상태인 활성 범위를 연결한다. 레지스터 할당은 간선으로 연결된 두 노드가 같은 색을 받지 않도록 노드에 색상(레지스터)을 할당하는 그래프 색칠 문제로 축소된다.p=896 활성도 분석을 사용하여 간섭 그래프를 구축할 수 있다. 노드가 프로그램 변수인 간격 그래프인 간섭 그래프는 어떤 변수가 동일한 레지스터에 할당될 수 없는지를 모델링하는 데 사용된다.p=241
### 원리
채틴 스타일의 그래프 색칠 기반 레지스터 할당자의 주요 단계는 다음과 같다.p=316 채틴(Chaitin) 등의 반복적 그래프 색칠 기반 레지스터 할당기 # **재번호 매기기**: 소스 프로그램에서 활성 범위 정보를 찾는다. # **빌드**: 간섭 그래프를 빌드한다. # **통합**: 복사 명령어에 의해 관련되고 간섭하지 않는 변수들의 활성 범위를 병합한다. # **스필 비용**: 각 변수의 스필 비용을 계산한다. 이는 변수를 메모리에 매핑하는 것이 최종 프로그램의 속도에 미치는 영향을 평가한다. # **단순화**: 추론 그래프에서 노드의 순서를 구성한다. # **스필 코드**: 스필 명령어, 즉 레지스터와 메모리 사이에 값을 교환하기 위한 로드 및 저장 명령어를 삽입한다. # **선택**: 각 변수에 레지스터를 할당한다.
### 단점 및 추가 개선 사항
그래프 색칠 할당은 세 가지 주요 단점이 있다. 첫째, 어떤 변수가 스필링될지 결정하기 위해 NP-완전 문제인 그래프 색칠에 의존한다. 일반 그래프에 대한 최소 색칠을 찾는 것은 실제로 NP-완전 문제이지만,p=618–619 간격 그래프(간섭 그래프 포함)의 최소 색칠은 선형 시간에 수행될 수 있다(아래 선형 스캔 참조).at=15.1-4: interval-graph coloring problempages=219-220 따라서 이 기술은 문제의 가정을 완전히 활용하지 못한다. 둘째, 활성 범위 분할이 사용되지 않는 한, 제거된 변수는 모든 곳에서 스필링된다. 저장 명령어는 변수 정의 직후 가능한 한 빨리 삽입되고, 로드 명령어는 변수 사용 직전에 삽입된다. 셋째, 스필링되지 않은 변수는 전체 수명 동안 동일한 레지스터에 유지된다.p=1 반면에, 단일 레지스터 이름이 여러 레지스터 클래스에 나타날 수 있는데, 여기서 클래스는 특정 역할에서 상호 교환 가능한 레지스터 이름들의 집합이다. 그러면 여러 레지스터 이름이 단일 하드웨어 레지스터의 별칭일 수 있다.p=277 마지막으로, 그래프 색칠은 레지스터 할당에 강력한 기술이지만, 활성 범위 수에 대해 제곱에 해당하는 최악의 경우 크기를 가질 수 있는 간섭 그래프를 사용하기 때문에 계산 비용이 많이 든다.p=124 그래프 색칠 레지스터 할당의 전통적인 공식화는 암시적으로 단일 뱅크의 겹치지 않는 범용 레지스터를 가정하며, 겹치는 레지스터 쌍, 특수 목적 레지스터 및 여러 레지스터 뱅크와 같은 불규칙한 아키텍처 기능을 처리하지 않는다.p=240 채틴 스타일 그래프 색칠 접근 방식의 한 가지 나중 개선점은 브릭스(Briggs) 등이 발견한 것이다. 이는 보존적 통합(conservative coalescing)이라고 불린다. 이 개선점은 두 활성 범위가 병합될 수 있는 시점을 결정하기 위한 기준을 추가한다. 주로, 비간섭 요구 사항 외에도 두 변수는 병합이 추가적인 스필링을 유발하지 않는 경우에만 통합될 수 있다. 브릭스 등은 채틴의 작업에 두 번째 개선점인 편향 색칠(biased coloring)을 도입한다. 편향 색칠은 복사 관련 활성 범위에 그래프 색칠에서 동일한 색상을 할당하려고 시도한다.p=316
## 선형 스캔
선형 스캔은 또 다른 전역 레지스터 할당 접근 방식이다. 이는 1999년 포레토(Poletto) 등이 처음 제안했다.p=895 이 접근 방식에서는 코드가 그래프로 변환되지 않는다. 대신, 모든 변수를 선형적으로 스캔하여 간격으로 표현되는 활성 범위를 결정한다. 모든 변수의 활성 범위가 파악되면 간격을 시간 순서대로 순회한다. 이 순회가 활성 범위가 충돌하는 변수를 식별하는 데 도움이 될 수 있지만, 간섭 그래프는 구축되지 않으며 변수는 탐욕스러운 방식으로 할당된다.p=124 이 접근 방식의 동기는 속도이다. 생성된 코드의 실행 시간 측면이 아니라 코드 생성에 소요되는 시간 측면에서의 속도이다. 일반적으로 표준 그래프 색칠 접근 방식은 고품질 코드를 생성하지만, 상당한 오버헤드가 있으며,p=902p=132 사용된 그래프 색칠 알고리즘은 2차 비용을 가진다.p=102 이러한 특징 덕분에 선형 스캔은 현재 핫스팟 클라이언트 컴파일러, V8, Jikes RVM,p=1 그리고 안드로이드 런타임(ART)과 같은 여러 JIT 컴파일러에서 사용되는 접근 방식이다.work=Google 핫스팟 서버 컴파일러는 우수한 코드를 위해 그래프 색칠을 사용한다.p=1
### 의사 코드
이것은 폴레토(Poletto) 등이 처음 제안한 알고리즘을 설명한다.p=899 여기서: * **R**은 사용 가능한 레지스터의 수이다. * **active**는 현재 지점과 겹치고 레지스터에 배치된 활성 구간들의 목록으로, 끝점 기준으로 오름차순 정렬되어 있다. **LinearScanRegisterAllocation** active ← {} **각** 활성 구간 i에 대해, 시작점 기준으로 오름차순 **반복** ExpireOldIntervals(i) **만약** length(active) = R **이면** SpillAtInterval(i) **그렇지 않으면** register[i] ← 사용 가능한 레지스터 풀에서 제거된 레지스터 i를 active에 추가, 끝점 기준으로 오름차순 정렬 **ExpireOldIntervals(i)** **각** 구간 j **에 대해** active에서, 끝점 기준으로 오름차순 **반복** **만약** endpoint[j] ≥ startpoint[i] **이면** **반환** active에서 j 제거 register[j]를 사용 가능한 레지스터 풀에 추가 **SpillAtInterval(i)** spill ← active의 마지막 구간 **만약** endpoint[spill] > endpoint[i] **이면** register[i] ← register[spill] location[spill] ← 새로운 스택 위치 active에서 spill 제거 i를 active에 추가, 끝점 기준으로 오름차순 정렬 **그렇지 않으면** location[i] ← 새로운 스택 위치
### 단점 및 추가 개선 사항
그러나 선형 스캔은 두 가지 주요 단점을 보인다. 첫째, 탐욕적인 특성 때문에 수명 구멍(lifetime holes), 즉 "변수 값이 필요하지 않은 범위"를 고려하지 않는다.p=2p=143 게다가, 스필링된 변수는 전체 수명 동안 스필링된 상태로 남아 있다. SSA 접근 방식에서 더 짧은 활성 범위 많은 다른 연구들이 폴레토(Poletto)의 선형 스캔 알고리즘을 뒤따랐다. 예를 들어, 트라우브(Traub) 등이 더 나은 품질의 코드를 생성하기 위해 second-chance binpacking이라는 알고리즘을 제안했다.p=141p=897 이 접근 방식에서는 스필링된 변수들이 표준 선형 스캔 알고리즘에서 사용된 것과는 다른 휴리스틱을 사용하여 나중에 레지스터에 저장될 기회를 얻는다. 이 알고리즘은 활성 구간 대신 활성 범위에 의존하는데, 이는 범위가 스필링되어야 할 경우 이 변수에 해당하는 다른 모든 범위가 스필링될 필요는 없음을 의미한다. 선형 스캔 할당은 SSA 형식의 이점을 활용하도록 조정되기도 했다. 이 중간 표현의 속성은 할당 알고리즘을 단순화하고 수명 구멍을 직접 계산할 수 있도록 한다.p=170 우선, 활성 구간을 구축하기 위한 데이터 흐름 그래프 분석에 소요되는 시간이 줄어들었는데, 이는 변수가 고유하기 때문이다.p=234 결과적으로 각 새로운 할당이 새로운 활성 구간에 해당하므로 더 짧은 활성 구간을 생성한다.p=233p=229 구간 및 활성 구멍을 모델링하는 것을 피하기 위해 로저스(Rogers)는 명령어의 80%에 대해 구간을 성공적으로 제거한 future-active sets라는 단순화를 보여주었다.2020
## 재료화

## 통합과 집약
레지스터 할당의 맥락에서 통합과 집약은 변수-변수 이동 작업을 두 변수를 동일한 위치에 할당함으로써 병합하는 행위이다. 통합과 집약 작업은 간섭 그래프가 구축된 후에 발생한다. 두 노드가 통합되면 동일한 색상을 얻고 동일한 레지스터에 할당되어야 하며, 그 후에 복사 작업은 불필요해진다.p=90 통합과 집약은 간섭 그래프의 색칠 가능성에 긍정적 및 부정적 영향을 모두 미칠 수 있다.p=103 예를 들어, 통합과 집약이 그래프 추론 색칠 가능성에 미칠 수 있는 부정적인 영향 중 하나는 두 노드가 통합될 때 결과 노드가 통합되는 노드들의 간선들의 합집합을 가지게 되는 경우이다.p=103 간섭 그래프 색칠 가능성에 대한 통합과 집약의 긍정적인 영향은, 예를 들어, 노드가 통합되는 두 노드 모두와 간섭할 때, 노드의 차수가 하나 줄어들어 간섭 그래프의 전반적인 색칠 가능성을 향상시키는 경우이다.p=7 여러 통합과 집약 휴리스틱이 존재한다.p=736 ; 적극적 통합과 집약: 채틴의 원래 레지스터 할당자에서 처음 도입되었다. 이 휴리스틱은 비간섭적인, 복사 관련 노드를 통합하는 것을 목표로 한다.p=99 복사 제거 관점에서 이 휴리스틱은 최상의 결과를 낸다.p=738 반면에 적극적 통합과 집약은 추론 그래프의 색칠 가능성에 영향을 미칠 수 있다.p=7 ; 보존적 통합과 집약: 적극적 통합과 집약과 동일한 휴리스틱을 주로 사용하지만, 간섭 그래프의 색칠 가능성을 손상시키지 않는 경우에만 이동을 병합한다.p=433 ; 반복적 통합과 집약: 그래프의 색칠 가능성을 유지하면서 한 번에 하나의 특정 이동을 제거한다.p=212 ; 낙관적 통합과 집약: 적극적 통합과 집약에 기반하지만, 추론 그래프 색칠 가능성이 손상되는 경우 가능한 한 적은 이동을 포기한다.p=741
## 혼합 접근법

### 하이브리드 할당
일부 다른 레지스터 할당 접근 방식은 레지스터 사용을 최적화하기 위해 한 가지 기술에 국한되지 않는다. 예를 들어, 카바소스(Cavazos) 등은 선형 스캔과 그래프 색칠 알고리즘을 모두 사용할 수 있는 솔루션을 제안했다.p=11 이 접근 방식에서 두 솔루션 중 하나를 선택하는 것은 동적으로 결정된다. 먼저, 기계 학습 알고리즘이 "오프라인"으로, 즉 런타임이 아닌 시점에 사용되어 어떤 할당 알고리즘을 사용해야 할지 결정하는 휴리스틱 함수를 구축한다. 그런 다음 이 휴리스틱 함수는 런타임에 사용되며, 코드 동작에 따라 할당자는 사용 가능한 두 알고리즘 중 하나를 선택할 수 있다.p=124-127 트레이스 레지스터 할당은 아이슬(Eisl) 등이 개발한 최근 접근 방식이다.p=14:1p=1 이 기술은 할당을 지역적으로 처리한다. 이는 동적 프로파일링 데이터에 의존하여 주어진 제어 흐름 그래프에서 가장 자주 사용될 분기를 결정한다. 그런 다음 병합 지점을 가장 많이 사용된 분기 위주로 무시하는 "트레이스"(즉 코드 세그먼트) 세트를 추론한다. 각 트레이스는 할당자에 의해 독립적으로 처리된다. 이 접근 방식은 다른 트레이스 간에 다른 레지스터 할당 알고리즘을 사용할 수 있기 때문에 하이브리드로 간주될 수 있다.p=4
### 분할 할당
분할 할당은 서로 다른 접근 방식을 결합하는 또 다른 레지스터 할당 기술로, 일반적으로 상반되는 것으로 간주된다. 예를 들어, 하이브리드 할당 기술은 첫 번째 휴리스틱 구축 단계가 오프라인에서 수행되고 휴리스틱 사용이 온라인에서 수행되기 때문에 분할된 것으로 간주될 수 있다.p=124 같은 방식으로 B. 디우프(Diouf) 등이 오프라인 및 온라인 동작, 즉 정적 및 동적 컴파일에 모두 의존하는 할당 기술을 제안했다.p=66p=1 오프라인 단계에서는 먼저 정수 선형 계획법을 사용하여 최적의 스필 세트가 수집된다. 그런 다음 라이브 범위는 이전에 식별된 최적의 스필 세트에 의존하는 `compressAnnotation` 알고리즘을 사용하여 주석 처리된다. 레지스터 할당은 오프라인 단계에서 수집된 데이터를 기반으로 온라인 단계에서 수행된다.p=72 2007년에 부셰(Bouchez) 등이 레지스터 할당을 스필링 전용 단계와 색칠 및 통합과 집약 전용 단계로 나누는 것을 제안하기도 했다.p=1
# 다양한 기술 간 비교
여러 메트릭이 하나의 레지스터 할당 기술과 다른 기술의 성능을 평가하는 데 사용되었다. 레지스터 할당은 일반적으로 코드 품질, 즉 빠르게 실행되는 코드와 분석 오버헤드, 즉 최적화된 레지스터 할당으로 코드를 생성하기 위해 소스 코드를 분석하는 데 소요되는 시간 사이의 균형을 다루어야 한다. 이러한 관점에서 생성된 코드의 실행 시간과 활성 분석에 소요된 시간은 다양한 기술을 비교하는 데 적합한 메트릭이다.p=901-910 적합한 메트릭이 선택되면, 메트릭이 적용될 코드는 실제 응용 프로그램의 동작을 반영하거나 알고리즘이 해결하려는 특정 문제와 관련성이 있어야 한다. 레지스터 할당에 관한 최근 기사들은 특히 다카포(Dacapo) 벤치마크 스위트를 사용한다.p=169
# 참고 자료
35em * s2cid=14143277 * edition = second * s2cid=1380545 * citeseerx=10.1.1.75.6911 * s2cid=16952747 * s2cid=9255051 * jstor=2271828 * isbn=978-3-540-72520-6 * s2cid=7683867 * arxiv=0710.3642 * citeseerx=10.1.1.219.5318 * doi=10.1145/143103.143143 * s2cid=6571479 * isbn=978-3-540-33050-9 * doi=10.1016/0096-0551(81)90048-5 * s2cid=16872867 * s2cid=3367270 * s2cid=14314078 * s2cid=8296742 * citeseerx=10.1.1.229.3988 * s2cid=2812379 * url=http://epub.jku.at/doi/10.1145/2972206.2972211 * chapter-url=http://kar.kent.ac.uk/63807/1/manlang17-eisl-et-al-trace-register-allocation-policies.pdf * url=https://resolver.obvsg.at/urn:nbn:at:at-ubl:3-271 * publication-place = New York, NY, USA * publication-place = Philadelphia, PA, USA * * doi-access=free * doi-access=free * isbn=978-3-540-43092-6 * s2cid=17598675 * isbn=978-3-540-43369-9 * doi=10.1145/93548.93552 * citeseerx=10.1.1.106.1919 * s2cid=15969885 * s2cid=18180752 * eprint=2011.05608 * citeseerx=10.1.1.6.6186 * citeseerx=10.1.1.71.9532 * citeseerx=10.1.1.52.8730 * s2cid=494490 * s2cid=1820765 참고 자료 끝