yeolyi.com성열의 컴퓨터공학

애착 변수에게 레지스터 주기

레지스터 할당

초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.

지금까지 컴파일러는 변수를 읽을 때마다 LOAD로 메모리에서 가져오고, 바꿀 때마다 STORE로 메모리에 썼습니다. 그래서 a를 여러 번 읽으면 이미 가져온 a를 매번 다시 LOAD로 가져옵니다. 변수를 아예 레지스터에 두면 이렇게 같은 칸을 오가지 않아도 되지 않을까요?

레지스터 나누기

변수를 레지스터에 두면, 읽을 때는 그 레지스터를 바로 쓰고 바꿀 때는 그 레지스터에서 바로 계산합니다. 메모리를 오가는 LOAD와 STORE가 사라집니다.

그런데 레지스터는 넷뿐이고, 식 글에서 보았듯 계산 중인 값도 R1:R0부터 레지스터를 차지합니다. 그래서 이 컴파일러는 R1:R0을 계산에 쓰려고 늘 비워 두고, R3:R2에 short 변수 하나를 둡니다.

C
어셈블리어
0–1LDI R0, 2
2–3LDI R1, 0
4–5STORE R0, a
6–7STORE R1, a+1
8–9LOAD R0, a
10–11LOAD R1, a+1
12–13ADDI R0, 1
14–15ADCI R1, 0
16–17STORE R0, b
18–19STORE R1, b+1
20–21LOAD R0, b
22–23LOAD R1, b+1
24–25LOAD R2, a
26–27SUB R0, R2
28–29LOAD R2, a+1
30–31SBC R1, R2
32–33STORE R0, c
34–35STORE R1, c+1
36–37LOAD R0, a
38–39LOAD R1, a+1
40–41LOAD R2, c
42–43ADD R0, R2
44–45LOAD R2, c+1
46–47ADC R1, R2
48–49STORE R0, a
50–51STORE R1, a+1
52–53HALT
54–55a: 0, 0
56–57b: 0, 0
58–59c: 0, 0
R0 0R1 0R2 0R3 0Z 0
a@54 0b@56 0c@58 0

메모리 쪽에서 a를 가져오는 LOAD 줄을 찾고, 레지스터 쪽과 비교해 봅시다.

많이 쓰는 변수부터

변수가 둘 이상이면 R3:R2에 다 들어가지 않습니다. 이 컴파일러는 코드에 가장 많이 나오는 변수 하나를 R3:R2에 두고, 나머지는 지금처럼 메모리 칸에 둡니다. 이렇게 어느 변수를 어느 레지스터에 둘지 정하는 일을 레지스터 할당(register allocation)이라 합니다.

C
1int main(void) {
2 short a = 2;
3 short b = a;
4 short c = 3;
5 short d = c;
6 a = 5;
7}
어셈블리어
0–1LDI R2, 2
2–3LDI R3, 0
4–5MOVE R0, R2
6–7MOVE R1, R3
8–9STORE R0, b
10–11STORE R1, b+1
12–13LDI R0, 3
14–15LDI R1, 0
16–17STORE R0, c
18–19STORE R1, c+1
20–21LOAD R0, c
22–23LOAD R1, c+1
24–25STORE R0, d
26–27STORE R1, d+1
28–29LDI R2, 5
30–31LDI R3, 0
32–33HALT
34–35b: 0, 0
36–37c: 0, 0
38–39d: 0, 0
R0 0R1 0R2 0R3 0Z 0
a@R3:R2 0b@34 0c@36 0d@38 0

데모 아래 a@R3:R2는 a가 R3:R2에 있다는 뜻입니다. 세 번 나오는 a가 R3:R2를 차지합니다.

a + b - (a - 1)처럼 괄호 안을 계산하는 데 R3:R2까지 써야 하는 식이 있으면 변수를 레지스터에 두지 않습니다. 실제 컴파일러는 변수가 언제까지 쓰이는지까지 따져, 다 쓴 변수의 레지스터를 다른 변수에 돌려 줍니다.

마무리

다음 글부터는 이 컴파일러를 씁니다. 다음 글에서는 값에 따라 실행할 줄을 고르고 되풀이하게 해 주는 조건과 반복을 살펴봅시다.

도전 문제

main 안에 short x0 = 1;, short x1 = 1;, short x2 = 1;, …처럼 새 변수에 1을 넣는 줄만 이어 적어 변수를 만듭니다. 쓰는 횟수가 모두 같으니 이 글의 컴파일러는 x0을 R3:R2에 두고, 나머지는 프로그램 뒤 메모리 칸에 둡니다. 끝에는 HALT를 붙입니다. 256칸 메모리에서 이렇게 만들 수 있는 변수는 최대 몇 개일까요? 숫자로 답하세요.