Register Spilling
레지스터 스필링
- 프로시저 A와 프로시저 B가 서로 같은 레지스터를 사용함에 따라 생기는 Register Corruption(레지스터 변형)을 방지하는 테크닉이다.
- MIPS의 레지스터의 개수가 유한하다는 점에서 오는 한계점에 대한 솔루션이다.
- Overwrite을 방지하기 위해 Callee측에서 자신이 사용할 Register들에 저장된 데이터을 Stack*에 저장한 후, Callee의 Task를 수행한다.
- Callee가 Task를 끝마치면, Stack에 저장해놓은 데이터들을 다시 원래 자리의 레지스터에 옮기고 난 다음 Caller에게 제어권을 넘긴다.
* Stack(스택)
- LIFO구조의 D램 기반 메인 메모리의 일부이다.
- \(\texttt{\$sp}\) 레지스터는 스택 포인터를 저장하는 레지스터이다.
- 스택의 주솟값 체계는 전통적으로 상위 주소에서 시작하여 Push된 데이터를 하위 주소로 쌓아가는 방식이다.
- 스택의 주솟의 주솟값은 데이터가 삽입될수록 4만큼 감소된다.
- Push 연산 : \(\texttt{\$sp - 4}\)
- Pop 연산 : \(\texttt{\$sp + 4}\)
Ex. 두 프로시저 간의 데이터 Overwrite를 방지하는 Register Spilling 기법 예시
- \(\texttt{main}\)프로시저와 \(\texttt{diffofsums}\)프로시저에서 \(\texttt{\$t0, \$t1}\)를 동시에 사용하고 있어 Register Corruption이 발생할 수 있다.
- \(\texttt{diffofsums}\) 프로시저에서 Task를 수행하기 전, 사용할 레지스터들의 데이터를 우선적으로 메인 메모리(스택)에 옮겨 놓는다. (Stack - Push)
- \(\texttt{diffofsums}\) 프로시저의 모든 Task가 완료된 후, 메인 메모리(스택)에 저장해놓았던 데이터들을 원래의 위치(레지스터)에 되돌려 놓고, Caller(\(\texttt{main}\)) 프로시저로 분기한다. (Stack - Pop)
- 스택에 대한 \(\texttt{sw, lw}\) 명령 수행 시, 스택이 LIFO구조임을 감안하여 Push 연산과 Pop 연산은 반대의 순서로 이루어져야 한다.
Preserved Register & Non-Preserved Register
| Preserved Register (Callee-Saved) |
Non-Preserved Register (Caller-Saved) |
| \(\texttt{\$s0 - \$s7}\) | \(\texttt{\$t0 - \$t9}\) |
| \(\texttt{\$ra}\) | \(\texttt{\$a0 - \$a3}\) |
| \(\texttt{\$sp}\) | \(\texttt{\$v0 - \$v1}\) |
| Stakc above the \(\texttt{\$sp}\) | Stack below the \(\texttt{\$sp}\) |
- 프로시저가 호출될 때마다 무조건적으로 Spilling을 수행한다면, 성능 측면에서 무시하지 못할 마이너스 요소로 작용하게 된다.
- 불필요한 Spilling 작업을 방지하기 위해 MIPS에서 레지스터를 두 카테고리로 나누어놓은 개념이다.
- Register Corruption에 대한 책임을 Caller가 지느냐, Callee가 지느냐에 대한 개념이다.
- Nested Procedure Call* 형태에서 Spilling 기법이 자주 사용되며, 대부분의 프로그램이 이 형태에 해당된다.
* Nested Procedure Call : Leaf Procedure*가 아닌 프로시저가 적어도 하나 이상은 존재하는 형태이다. Leaf Procedure는 어떤 프로시저도 호출하지 않는 프로시저를 의미한다.
1. Preserved Register (Callee-Saved)
- Caller가 사용하고 있을 확률이 높은 레지스터들이다.
- Callee측에서 Spilling을 진행해야할 책임이 있는 레지스터들이다.
- Callee측에서 Stack을 사용하고자 한다면, \(\texttt{\$sp}\)의 아래쪽 메모리를 사용해야 한다.
(즉, Callee 측에서 추가적으로 Stack 공간을 확보해서 사용해야 한다.)
2. Non-Preserved Register (Caller-Saved)
- Callee가 사용하고 있을 확률이 높은 레지스터들이다.
- Caller측에서 Spilling을 진행해야할 책임이 있는 레지스터들이다.
- Caller측에선, Callee와 달리, 기 확보된 Stack 공간을 사용하면 된다.
Ex. Recursive Procedure Call에서의 Spilling 예시
- Factorial을 재귀적으로 계산하는 프로그램이다.
- Argument와 Return Address를Stack에 저장하기 위해 2Words의 공간만큼을 확보한다.
- Factorial이 호출되는 횟수만큼, Stack에서는 2Words만큼의 공간이 계속해서 확보될 것이다.
- Factorial(3)을 계산할 때, 스택의 변화 과정이다.
- \(\texttt{0xBC}\)는 \(\texttt{jal}\) 명령 바로 다음에 수행될 명령어의 주소임을 명심하자.
이미지 출처 : 권건우 교수님 강의록
