레지스터 할당

컴파일러 최적화에서 레지스터 할당(Register allocation)은 지역 자동 변수와 식의 결과를 제한된 수의 프로세서 레지스터에 할당하는 과정이다.

레지스터 할당은 기본 블록(지역 레지스터 할당) 전체, 함수/프로시저 전체(전역 레지스터 할당), 또는 호출 그래프를 통해 트래버스되는 함수 경계(프로시저 간 레지스터 할당)를 넘어 발생할 수 있다. 함수/프로시저별로 수행될 때, 호출 규약은 각 호출 사이트 주변에 저장/복원 삽입을 요구할 수 있다.

 컴파일러 및 인터프리터 문서를 참고하십시오.

 기억 장치 및 메모리 계층 구조 문서를 참고하십시오.

많은 프로그래밍 언어에서 프로그래머는 원하는 만큼 변수를 사용할 수 있다. 컴퓨터는 CPU의 레지스터를 빠르게 읽고 쓸 수 있으므로, 더 많은 변수가 CPU 레지스터에 있을 때 컴퓨터 프로그램은 더 빠르게 실행된다.^[1] 또한, 레지스터에 접근하는 코드는 때로는 더 간결하여 코드가 더 작아지고, 메모리 대신 레지스터를 사용하면 더 빠르게 가져올 수 있다. 그러나 레지스터의 수는 제한적이다. 따라서 컴파일러가 코드를 기계어로 번역할 때, 제한된 수의 CPU 레지스터에 변수를 어떻게 할당할지 결정해야 한다.^[2][3]

모든 변수가 동시에 사용 중(또는 "활성")인 것은 아니므로, 프로그램의 수명 동안 특정 레지스터는 다른 변수를 저장하는 데 사용될 수 있다. 그러나 동시에 사용 중인 두 변수는 변수 중 하나를 손상시키지 않고 동일한 레지스터에 할당될 수 없다. 모든 변수를 담을 레지스터가 충분하지 않으면 일부 변수는 RAM으로 이동되거나 RAM에서 가져올 수 있다. 이 과정을 레지스터 "스필링"(spilling)이라고 한다.^[4] 프로그램의 수명 동안 변수는 스필링될 수도 있고 레지스터에 저장될 수도 있다. 이 변수는 "분할"(split)된 것으로 간주된다.^[5] RAM에 접근하는 것은 레지스터에 접근하는 것보다 훨씬 느리므로 ^[6] 컴파일된 프로그램은 더 느리게 실행된다. 따라서 최적화 컴파일러는 가능한 한 많은 변수를 레지스터에 할당하는 것을 목표로 한다. 높은 "레지스터 압력"은 더 많은 스필링 및 재로드가 필요하다는 기술 용어이며, 브라운(Braun) 등이 "명령어에서 동시에 활성 상태인 변수의 수"로 정의했다.^[7]

또한, 일부 컴퓨터 설계는 자주 접근하는 레지스터를 캐시한다. 따라서 가능한 한 `move` 명령어의 원본과 대상에 동일한 레지스터를 할당함으로써 프로그램을 더욱 최적화할 수 있다. 컴파일러가 정적 단일 대입 형식(SSA)과 같은 중간 표현을 사용하는 경우 특히 중요하다. 특히 SSA가 완전히 최적화되지 않은 경우 인위적으로 추가적인 `move` 명령어를 생성할 수 있다.

따라서 레지스터 할당은 런타임에 변수를 어디에 저장할지, 즉 레지스터 내부 또는 외부에 저장할지 선택하는 것으로 구성된다. 변수를 레지스터에 저장해야 하는 경우 할당자는 이 변수가 어떤 레지스터에 저장될지 결정해야 한다. 궁극적으로 또 다른 과제는 변수가 동일한 위치에 얼마나 오랫동안 머물러야 하는지 결정하는 것이다.

레지스터 할당자는 선택된 할당 전략에 관계없이 이러한 과제를 해결하기 위해 일련의 핵심 동작에 의존할 수 있다. 이러한 동작은 여러 범주로 분류할 수 있다.^[8]

이동 삽입

이 동작은 레지스터 간의 이동 명령어 수를 늘리는 것으로, 즉 하나의 레지스터 대신 변수가 수명 동안 다른 레지스터에서 활성화되도록 하는 것이다. 이는 분할 활성 범위 접근 방식에서 발생한다.

스필링

이 동작은 변수를 레지스터 대신 메모리에 저장하는 것이다.^[9]

할당

이 동작은 변수에 레지스터를 할당하는 것이다.^[10]

통합과 집약

이 동작은 레지스터 간의 이동 횟수를 제한하여 총 명령어 수를 제한하는 것이다. 예를 들어, 여러 메서드에서 활성화되는 변수를 식별하고 해당 수명 동안 하나의 레지스터에 저장하는 방식이다.^[9]

많은 레지스터 할당 접근 방식은 하나 이상의 특정 동작 범주에 최적화되어 있다.

레지스터 할당은 다양한 레지스터 할당 접근 방식으로 해결(또는 피할 수 있는) 여러 문제를 제기한다. 가장 일반적인 세 가지 문제는 다음과 같다.

별칭(Aliasing)

일부 아키텍처에서는 한 레지스터에 값을 할당하면 다른 레지스터의 값에 영향을 줄 수 있다. 이를 별칭이라고 한다. 예를 들어, X86 아키텍처는 16비트 또는 8비트 레지스터로도 사용될 수 있는 4개의 범용 32비트 레지스터를 가지고 있다.^[11] 이 경우 eax 레지스터에 32비트 값을 할당하면 al 레지스터의 값에 영향을 준다.

사전 색칠(Pre-coloring)

이 문제는 일부 변수를 특정 레지스터에 강제로 할당하는 행위이다. 예를 들어, PowerPC 호출 규약에서 매개변수는 일반적으로 R3-R10으로 전달되며 반환 값은 R3으로 전달된다.^[12]

NP-문제

채틴(Chaitin) 등이 레지스터 할당이 NP-완전 문제임을 보였다. 그들은 임의의 그래프에 대해, (레지스터를 노드로, 기계 레지스터를 사용 가능한 색상으로 나타내는) 프로그램에 대한 레지스터 할당이 원래 그래프에 대한 색칠이 되도록 프로그램을 구성할 수 있음을 보여줌으로써 그래프 색칠 문제를 레지스터 할당 문제로 환원시킨다. 그래프 색칠이 NP-난해 문제이고 레지스터 할당이 NP에 속하므로, 이는 문제의 NP-완전성을 증명한다.^[13]

레지스터 할당은 코드의 기본 블록에서 발생할 수 있다. 이를 "지역적"이라고 하며, 호르위츠(Horwitz) 등이 처음 언급했다.^[14] 기본 블록에는 분기가 없으므로 할당 과정은 빠르다고 생각된다. 레지스터 할당에서 제어 흐름 그래프 병합 지점의 관리가 시간 소모적인 작업으로 드러나기 때문이다.^[15] 그러나 이 접근 방식은 전체 컴파일 단위(예를 들어 메서드 또는 프로시저)에서 작동하는 "전역적" 접근 방식만큼 최적화된 코드를 생성하지 못한다고 생각된다.^[16]

 그래프 색칠 문서를 참고하십시오.

그래프 색칠 할당은 레지스터 할당을 해결하는 지배적인 접근 방식이다.^[17][18] 이는 채틴(Chaitin) 등이 처음 제안했다.^[4] 이 접근 방식에서 그래프의 노드는 레지스터 할당 후보인 활성 범위(변수, 임시 변수, 가상/심볼릭 레지스터)를 나타낸다. 간선은 충돌하는 활성 범위, 즉 적어도 하나의 프로그램 지점에서 동시에 활성 상태인 활성 범위를 연결한다. 레지스터 할당은 간선으로 연결된 두 노드가 같은 색을 받지 않도록 노드에 색상(레지스터)을 할당하는 그래프 색칠 문제로 축소된다.^[19]

활성도 분석을 사용하여 간섭 그래프를 구축할 수 있다. 노드가 프로그램 변수인 간격 그래프인 간섭 그래프는 어떤 변수가 동일한 레지스터에 할당될 수 없는지를 모델링하는 데 사용된다.^[20]

채틴 스타일의 그래프 색칠 기반 레지스터 할당자의 주요 단계는 다음과 같다.^[18]

1. 재번호 매기기: 소스 프로그램에서 활성 범위 정보를 찾는다.
2. 빌드: 간섭 그래프를 빌드한다.
3. 통합: 복사 명령어에 의해 관련되고 간섭하지 않는 변수들의 활성 범위를 병합한다.
4. 스필 비용: 각 변수의 스필 비용을 계산한다. 이는 변수를 메모리에 매핑하는 것이 최종 프로그램의 속도에 미치는 영향을 평가한다.
5. 단순화: 추론 그래프에서 노드의 순서를 구성한다.
6. 스필 코드: 스필 명령어, 즉 레지스터와 메모리 사이에 값을 교환하기 위한 로드 및 저장 명령어를 삽입한다.
7. 선택: 각 변수에 레지스터를 할당한다.

그래프 색칠 할당은 세 가지 주요 단점이 있다. 첫째, 어떤 변수가 스필링될지 결정하기 위해 NP-완전 문제인 그래프 색칠에 의존한다. 일반 그래프에 대한 최소 색칠을 찾는 것은 실제로 NP-완전 문제이지만,^[21] 간격 그래프(간섭 그래프 포함)의 최소 색칠은 선형 시간에 수행될 수 있다(아래 선형 스캔 참조).^[22][23] 따라서 이 기술은 문제의 가정을 완전히 활용하지 못한다. 둘째, 활성 범위 분할이 사용되지 않는 한, 제거된 변수는 모든 곳에서 스필링된다. 저장 명령어는 변수 정의 직후 가능한 한 빨리 삽입되고, 로드 명령어는 변수 사용 직전에 삽입된다. 셋째, 스필링되지 않은 변수는 전체 수명 동안 동일한 레지스터에 유지된다.^[24]

반면에, 단일 레지스터 이름이 여러 레지스터 클래스에 나타날 수 있는데, 여기서 클래스는 특정 역할에서 상호 교환 가능한 레지스터 이름들의 집합이다. 그러면 여러 레지스터 이름이 단일 하드웨어 레지스터의 별칭일 수 있다.^[25] 마지막으로, 그래프 색칠은 레지스터 할당에 강력한 기술이지만, 활성 범위 수에 대해 제곱에 해당하는 최악의 경우 크기를 가질 수 있는 간섭 그래프를 사용하기 때문에 계산 비용이 많이 든다.^[26] 그래프 색칠 레지스터 할당의 전통적인 공식화는 암시적으로 단일 뱅크의 겹치지 않는 범용 레지스터를 가정하며, 겹치는 레지스터 쌍, 특수 목적 레지스터 및 여러 레지스터 뱅크와 같은 불규칙한 아키텍처 기능을 처리하지 않는다.^[27]

채틴 스타일 그래프 색칠 접근 방식의 한 가지 나중 개선점은 브릭스(Briggs) 등이 발견한 것이다. 이는 보존적 통합(conservative coalescing)이라고 불린다. 이 개선점은 두 활성 범위가 병합될 수 있는 시점을 결정하기 위한 기준을 추가한다. 주로, 비간섭 요구 사항 외에도 두 변수는 병합이 추가적인 스필링을 유발하지 않는 경우에만 통합될 수 있다. 브릭스 등은 채틴의 작업에 두 번째 개선점인 편향 색칠(biased coloring)을 도입한다. 편향 색칠은 복사 관련 활성 범위에 그래프 색칠에서 동일한 색상을 할당하려고 시도한다.^[18]

선형 스캔은 또 다른 전역 레지스터 할당 접근 방식이다. 이는 1999년 포레토(Poletto) 등이 처음 제안했다.^[28] 이 접근 방식에서는 코드가 그래프로 변환되지 않는다. 대신, 모든 변수를 선형적으로 스캔하여 간격으로 표현되는 활성 범위를 결정한다. 모든 변수의 활성 범위가 파악되면 간격을 시간 순서대로 순회한다. 이 순회가 활성 범위가 충돌하는 변수를 식별하는 데 도움이 될 수 있지만, 간섭 그래프는 구축되지 않으며 변수는 탐욕스러운 방식으로 할당된다.^[26]

이 접근 방식의 동기는 속도이다. 생성된 코드의 실행 시간 측면이 아니라 코드 생성에 소요되는 시간 측면에서의 속도이다. 일반적으로 표준 그래프 색칠 접근 방식은 고품질 코드를 생성하지만, 상당한 오버헤드가 있으며,^[29][30] 사용된 그래프 색칠 알고리즘은 2차 비용을 가진다.^[31] 이러한 특징 덕분에 선형 스캔은 현재 핫스팟 클라이언트 컴파일러, V8, Jikes RVM,^[5] 그리고 안드로이드 런타임(ART)과 같은 여러 JIT 컴파일러에서 사용되는 접근 방식이다.^[32] 핫스팟 서버 컴파일러는 우수한 코드를 위해 그래프 색칠을 사용한다.^[33]

이것은 폴레토(Poletto) 등이 처음 제안한 알고리즘을 설명한다.^[34] 여기서:

• 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), 즉 "변수 값이 필요하지 않은 범위"를 고려하지 않는다.^[35][36] 게다가, 스필링된 변수는 전체 수명 동안 스필링된 상태로 남아 있다.

많은 다른 연구들이 폴레토(Poletto)의 선형 스캔 알고리즘을 뒤따랐다. 예를 들어, 트라우브(Traub) 등이 더 나은 품질의 코드를 생성하기 위해 second-chance binpacking이라는 알고리즘을 제안했다.^[37][38] 이 접근 방식에서는 스필링된 변수들이 표준 선형 스캔 알고리즘에서 사용된 것과는 다른 휴리스틱을 사용하여 나중에 레지스터에 저장될 기회를 얻는다. 이 알고리즘은 활성 구간 대신 활성 범위에 의존하는데, 이는 범위가 스필링되어야 할 경우 이 변수에 해당하는 다른 모든 범위가 스필링될 필요는 없음을 의미한다.

선형 스캔 할당은 SSA 형식의 이점을 활용하도록 조정되기도 했다. 이 중간 표현의 속성은 할당 알고리즘을 단순화하고 수명 구멍을 직접 계산할 수 있도록 한다.^[39] 우선, 활성 구간을 구축하기 위한 데이터 흐름 그래프 분석에 소요되는 시간이 줄어들었는데, 이는 변수가 고유하기 때문이다.^[40] 결과적으로 각 새로운 할당이 새로운 활성 구간에 해당하므로 더 짧은 활성 구간을 생성한다.^[41][42] 구간 및 활성 구멍을 모델링하는 것을 피하기 위해 로저스(Rogers)는 명령어의 80%에 대해 구간을 성공적으로 제거한 future-active sets라는 단순화를 보여주었다.^[43]

 재료화 문서를 참고하십시오.

 통합과 집약 (컴퓨터 과학) 문서를 참고하십시오.

레지스터 할당의 맥락에서 통합과 집약은 변수-변수 이동 작업을 두 변수를 동일한 위치에 할당함으로써 병합하는 행위이다. 통합과 집약 작업은 간섭 그래프가 구축된 후에 발생한다. 두 노드가 통합되면 동일한 색상을 얻고 동일한 레지스터에 할당되어야 하며, 그 후에 복사 작업은 불필요해진다.^[44]

통합과 집약은 간섭 그래프의 색칠 가능성에 긍정적 및 부정적 영향을 모두 미칠 수 있다.^[9] 예를 들어, 통합과 집약이 그래프 추론 색칠 가능성에 미칠 수 있는 부정적인 영향 중 하나는 두 노드가 통합될 때 결과 노드가 통합되는 노드들의 간선들의 합집합을 가지게 되는 경우이다.^[9] 간섭 그래프 색칠 가능성에 대한 통합과 집약의 긍정적인 영향은, 예를 들어, 노드가 통합되는 두 노드 모두와 간섭할 때, 노드의 차수가 하나 줄어들어 간섭 그래프의 전반적인 색칠 가능성을 향상시키는 경우이다.^[45]

여러 통합과 집약 휴리스틱이 존재한다.^[46]

적극적 통합과 집약

채틴의 원래 레지스터 할당자에서 처음 도입되었다. 이 휴리스틱은 비간섭적인, 복사 관련 노드를 통합하는 것을 목표로 한다.^[47] 복사 제거 관점에서 이 휴리스틱은 최상의 결과를 낸다.^[48] 반면에 적극적 통합과 집약은 추론 그래프의 색칠 가능성에 영향을 미칠 수 있다.^[45]

보존적 통합과 집약

적극적 통합과 집약과 동일한 휴리스틱을 주로 사용하지만, 간섭 그래프의 색칠 가능성을 손상시키지 않는 경우에만 이동을 병합한다.^[49]

반복적 통합과 집약

그래프의 색칠 가능성을 유지하면서 한 번에 하나의 특정 이동을 제거한다.^[50]

낙관적 통합과 집약

적극적 통합과 집약에 기반하지만, 추론 그래프 색칠 가능성이 손상되는 경우 가능한 한 적은 이동을 포기한다.^[51]

일부 다른 레지스터 할당 접근 방식은 레지스터 사용을 최적화하기 위해 한 가지 기술에 국한되지 않는다. 예를 들어, 카바소스(Cavazos) 등은 선형 스캔과 그래프 색칠 알고리즘을 모두 사용할 수 있는 솔루션을 제안했다.^[52] 이 접근 방식에서 두 솔루션 중 하나를 선택하는 것은 동적으로 결정된다. 먼저, 기계 학습 알고리즘이 "오프라인"으로, 즉 런타임이 아닌 시점에 사용되어 어떤 할당 알고리즘을 사용해야 할지 결정하는 휴리스틱 함수를 구축한다. 그런 다음 이 휴리스틱 함수는 런타임에 사용되며, 코드 동작에 따라 할당자는 사용 가능한 두 알고리즘 중 하나를 선택할 수 있다.^[53]

트레이스 레지스터 할당은 아이슬(Eisl) 등이 개발한 최근 접근 방식이다.^[3][5] 이 기술은 할당을 지역적으로 처리한다. 이는 동적 프로파일링 데이터에 의존하여 주어진 제어 흐름 그래프에서 가장 자주 사용될 분기를 결정한다. 그런 다음 병합 지점을 가장 많이 사용된 분기 위주로 무시하는 "트레이스"(즉 코드 세그먼트) 세트를 추론한다. 각 트레이스는 할당자에 의해 독립적으로 처리된다. 이 접근 방식은 다른 트레이스 간에 다른 레지스터 할당 알고리즘을 사용할 수 있기 때문에 하이브리드로 간주될 수 있다.^[54]

분할 할당은 서로 다른 접근 방식을 결합하는 또 다른 레지스터 할당 기술로, 일반적으로 상반되는 것으로 간주된다. 예를 들어, 하이브리드 할당 기술은 첫 번째 휴리스틱 구축 단계가 오프라인에서 수행되고 휴리스틱 사용이 온라인에서 수행되기 때문에 분할된 것으로 간주될 수 있다.^[26] 같은 방식으로 B. 디우프(Diouf) 등이 오프라인 및 온라인 동작, 즉 정적 및 동적 컴파일에 모두 의존하는 할당 기술을 제안했다.^[55][56] 오프라인 단계에서는 먼저 정수 선형 계획법을 사용하여 최적의 스필 세트가 수집된다. 그런 다음 라이브 범위는 이전에 식별된 최적의 스필 세트에 의존하는 `compressAnnotation` 알고리즘을 사용하여 주석 처리된다. 레지스터 할당은 오프라인 단계에서 수집된 데이터를 기반으로 온라인 단계에서 수행된다.^[57]

2007년에 부셰(Bouchez) 등이 레지스터 할당을 스필링 전용 단계와 색칠 및 통합과 집약 전용 단계로 나누는 것을 제안하기도 했다.^[58]

여러 메트릭이 하나의 레지스터 할당 기술과 다른 기술의 성능을 평가하는 데 사용되었다. 레지스터 할당은 일반적으로 코드 품질, 즉 빠르게 실행되는 코드와 분석 오버헤드, 즉 최적화된 레지스터 할당으로 코드를 생성하기 위해 소스 코드를 분석하는 데 소요되는 시간 사이의 균형을 다루어야 한다. 이러한 관점에서 생성된 코드의 실행 시간과 활성 분석에 소요된 시간은 다양한 기술을 비교하는 데 적합한 메트릭이다.^[59]

적합한 메트릭이 선택되면, 메트릭이 적용될 코드는 실제 응용 프로그램의 동작을 반영하거나 알고리즘이 해결하려는 특정 문제와 관련성이 있어야 한다. 레지스터 할당에 관한 최근 기사들은 특히 다카포(Dacapo) 벤치마크 스위트를 사용한다.^[60]

• 슈트랄러 수, 식 트리를 평가하는 데 필요한 최소 레지스터 수.^[61]
• Register (keyword), C 및 C++에서 변수를 레지스터에 배치하도록 하는 힌트.
• 세티–울만 알고리즘, 식을 평가하는 데 필요한 레지스터 수가 사용 가능한 레지스터 수를 초과할 때 단일 식을 평가하기 위한 가장 효율적인 레지스터 할당을 생성하는 알고리즘.

• 정수 계획법 튜토리얼
• 컨퍼런스 정수 계획법 및 조합 최적화, IPCO
• 오수아 조합 최적화 워크숍
• 보스처(Bosscher), 스티븐; 노빌로(Novillo), 디에고. GCC에 새로운 최적화 프레임워크 추가. GCC의 SSA 사용과 기존 IR보다 어떻게 개선되었는지에 대한 기사.
• SSA 참고문헌. SSA 연구 논문 광범위 카탈로그.
• 자덱(Zadeck), F. 케네스. "정적 단일 할당 형식의 개발", 2007년 12월 SSA의 기원에 대한 강연.
• VV.AA. "SSA 기반 컴파일러 설계" (2014)
• CiteSeer 인용
• 애그너 포그의 최적화 매뉴얼 - x86 프로세서 아키텍처 및 저수준 코드 최적화에 대한 문서