# 레지스터 스파일링

## 개요

**레스터 스파일링**(Registerilling)은 컴일러 최적화정에서 발생하는 중요한 현상 중로, 프로그램에서 사용하는 변수의 수 프로세서의 물리적 레지스터 수를 초과할 때 발생한다. 이 경우 컴파일러는 일부 변수를 **메모리**(스택)로 내려보내야 하며, 이를 통해 레지스터 자원을 효율적으로 관리한다. 이 과정은 성능에 직접적인 영향을 미치므로, 컴파일러의 최적화 전략에서 매우 중요한 요소로 다뤄진다.

레지스터 스파일링은 레지스터 할당(Register Allocation) 단계에서 결정되며, 특히 **그래프 기반 레지스터 할당**(Graph Coloring-based Register Allocation) 기법을 사용하는 컴파일러에서 자주 논의된다. 레지스터는 CPU 내에서 가장 빠른 접근 속도를 가진 저장 장치이므로, 변수가 레지스터에 유지되는 것이 이상적이다. 그러나 제한된 수의 레지스터로 인해 모든 변수를 레지스터에 저장할 수 없을 때, 스파일링이 불가피하게 발생한다.

## 레지스터 스파일링의 원리

### 레지스터 할당과 한계

현대 CPU는 일반적으로 제한된 수의 일반 목적 레지스터(예: x86-64 아키텍처의 경우 16개의 64비트 레지스터)를 제공한다. 그러나 고수준 프로그래밍 언어로 작성된 프로그램은 수십 개 이상의 변수를 동시에 사용할 수 있다. 컴파일러는 이들 변수를 가능한 한 레지스터에 할당하여 실행 속도를 극대화하려 한다.

레지스터 할당은 다음과 같은 단계로 이루어진다:

1. **라이브 변수 분석**(Live Variable Analysis): 각 변수가 언제 읽히고 쓰이는지 분석하여 라이브 범위를 결정.
2. **간섭 그래프 생성**(Interference Graph): 동시에 라이브인 변수들 간의 간섭 관계를 그래프로 표현.
3. **그래프 색칠**(Graph Coloring): 각 레지스터를 하나의 "색"으로 간주하고, 간섭 관계에 따라 변수에 색을 칠함.
4. **스파일링 결정**: 색칠이 불가능한 변수(레지스터 부족)는 메모리로 스파일링.

### 스파일링의 비용

레지스터에서 변수를 메모리로 옮기면 다음과 같은 성능 저하가 발생한다:

- **메모리 접근 지연**: 레지스터 접근은 1 사이클 이내인 반면, 캐시 미스 시 메모리 접근은 수십~수백 사이클이 소요될 수 있음.
- **스택 조작 오버헤드**: 스파일된 변수는 함수 스택 프레임에 저장되며, 로드/스토어 명령어가 추가됨.
- **지연 파이프라인 영향**: 메모리 접근은 파이프라인 지연을 유발할 수 있음.

따라서 컴파일러는 스파일링을 최소화하고, **가장 덜 자주 사용되는 변수**나 **라이브 범위가 짧지 않은 변수**를 우선적으로 스파일 대상으로 선정한다.

## 스파일링 최적화 전략

### 1. 비용 기반 스파일링 (Cost-based Spilling)

컴파일러는 각 변수에 대해 스파일링 비용을 추정하고, 이를 바탕으로 스파일 대상을 결정한다. 비용은 일반적으로 다음과 같은 요소로 계산된다:

- 변수의 사용 빈도 (로드/스토어 횟수)
- 라이브 범위의 길이
- 루프 내 사용 여부 (루프 내 변수는 스파일링 비용이 큼)

예를 들어, 자주 사용되지만 짧은 라이브 범위를 가진 변수는 임시 레지스터로 관리되기도 하며, 반복 루프 내에서 자주 접근되는 변수는 스파일링을 피하려는 전략이 적용된다.

### 2. 재스파일링 (Rematerialization)

일부 경우, 컴파일러는 변수 값을 메모리에 저장하는 대신, **다시 계산**(재생성)하는 것이 더 효율적일 수 있다. 예를 들어, 상수 값이나 간단한 연산 결과(예: `x = 5` 또는 `y = a + b`에서 `a`, `b`가 레지스터에 있음)는 필요 시 다시 계산하는 것이 메모리 접근보다 빠를 수 있다. 이를 **재스파일링**(Rematerialization)이라 한다.

이 전략은 읽기 전용 값이나 순수 함수의 결과에 효과적이다.

### 3. 라이브 범위 분할 (Live Range Splitting)

컴파일러는 하나의 변수를 여러 개의 논리적 변수로 분할하여, 레지스터 할당의 유연성을 높일 수 있다. 예를 들어, 변수 `i`가 두 개의 분리된 루프에서 사용될 경우, 각 루프 내에서 독립적인 변수로 취급하여 서로 다른 레지스터를 할당할 수 있다. 이로 인해 스파일링 필요성이 줄어들 수 있다.

## 예시: 레지스터 스파일링의 실제 코드

다음은 간단한 C 코드와 컴파일 시 발생할 수 있는 레지스터 스파일링의 예이다.

```c
int compute(int a, int b, int c, int d, int e, int f) {
    int t1 = a + b;
    int t2 = c * d;
    int t3 = e - f;
    int t4 =1 t2;
    int t5 = t4 + t3;
    return t5;
}
```

이 함수는 6개의 입력 인자와 5개의 지역 변수를 사용한다. x86-64의 경우 인자는 최대 6개까지 레지스터(RDI, RSI, RDX, RCX, R8, R9)로 전달되지만, 지역 변수가 많아질 경우 레지스터 부족이 발생할 수 있다.

최적화되지 않은 컴파일에서는 `t3`, `t4`, `t5` 등 일부 변수가 스택에 저장될 수 있으며, 이는 다음과 같은 어셈블리 코드로 나타날 수 있다:

```asm
mov eax, edi        ; a
add eax, esi        ; a + b → t1
imul eax, edx       ; t1 * c*d → t4 (가정)
; t3 계산 후 메모리에 저장 (스파일링)
mov [rbp-4], ecx    ; t3 = e - f (간단화)
```

최적화된 컴파일러는 라이브 범위 분석을 통해 불필요한 스파일링을 방지하고, 변수를 재사용하거나 제거할 수 있다.

## 관련 기법 및 최신 동향

- **SSA**(Static Single Assignment) 형식: 변수가 한 번만 할당되도록 변환하여 레지스터 할당을 용이하게 함.
- **리지스터 프레싱**(Register Pressure): 레지스터 사용 수요가 높은 코드 영역을 식별하고, 함수 인라인이나 루프 최적화로 완화.
- **GPU 컴파일러**: GPU는 수천 개의 스레드를 동시에 실행하므로 레지스터 스파일링이 성능에 더 큰 영향을 미치며, 이에 대한 정교한 정책이 필요.

## 참고 자료

- Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). *Compilers: Principles, Techniques, and Tools* (2nd ed.). Addison-Wesley.  
- Cooper, K. D., & Torczon, L. (2011). *Engineering a Compiler* (2nd ed.). Morgan Kaufmann.  
- LLVM 문서: [Register Allocation](https://llvm.org/docs/RegisterAllocation.html)  

레지스터 스파일링은 컴파일러 최적화의 핵심 과제 중 하나로, 성능과 자원 효율성 사이의 균형을 맞추는 데 중요한 역할을 한다.