レジスタは少なく値は多い — 寿命で分け、片付ける

한 줄 요약

컴파일러는 값마다 이름(가상 레지스터)을 끝없이 만들어 쓰지만 CPU 의 레지스터는 열여섯 개뿐입니다. 활성 분석으로 값이 언제부터 언제까지 살아 있는지 구하고, 선형 스캔으로 겹치지 않는 값끼리 같은 레지스터를 나눠 쓰게 하며, 모자라면 일부를 메모리로 넘깁니다(spill). 프로그램이 실행 중에 만든 객체는 반대로, 아무도 가리키지 않게 되면 가비지 컬렉터가 뿌리에서 닿는 것만 남기고 치웁니다.

왜 이게 필요했나

8모듈의 코드 생성기는 모든 지역 변수를 스택 슬롯에 두고, 쓸 때마다 메모리에서 읽고 씁니다. 틀리지는 않지만, 레지스터는 한 사이클에 읽히고 메모리는 캐시에 있어도 몇 사이클이 걸립니다. gcc -O0 과 -O2 의 출력 차이 가운데 가장 큰 몫이 이것 — 값을 레지스터에 두느냐 — 입니다.

그런데 값은 많고 레지스터는 적습니다. 두 값이 동시에 살아 있지 않다면 같은 레지스터를 써도 됩니다. '살아 있다' 는 것은 "이 값을 나중에 다시 읽을 일이 있다" 는 뜻이고, 그것을 코드만 보고 계산하는 것이 활성 분석입니다.

메모리 반대편에도 같은 질문이 있습니다. 5모듈의 클로저는 호출이 끝난 환경을 붙잡아 살려 두었습니다. 그렇다면 언제 버려도 되는가? 아무도 닿을 수 없게 된 때입니다. 가비지 컬렉터는 그것을 사람 대신 계산합니다.

어떻게 동작하나

활성 분석은 뒤에서 앞으로. 명령 i 바로 뒤에 살아 있는 값(live-out)을 알면, 그 앞(live-in)은 use ∪ (live_out − def) 입니다 — 이 명령이 쓰는 값은 앞에서도 살아 있어야 하고, 이 명령이 정의하는 값은 앞에서는 아직 없었습니다. 마지막 명령부터 거꾸로 걸으면 한 번에 끝납니다. 반복문이 있는 CFG 에서는 뒤로 가는 간선 때문에 한 번으로 끝나지 않습니다 — 블록 단위로 live_out = 다음 블록들의 live_in 합집합 을 더는 바뀌지 않을 때까지 되풀이합니다(7모듈의 지배자와 같은 고정점 계산).

선형 스캔. 값마다 [정의한 명령, 마지막으로 쓰는 명령] 구간을 만들고, 시작 순으로 훑으며 레지스터를 나눠 줍니다.

구간(명령 번호)          k = 2 개의 레지스터로
t1 [0 ──────── 4]        t1 → r0
t2   [1 ───────────── 6] t2 → r1
t3     [2 ──── 4]        t3: 빈 레지스터가 없다. 활성인 t1(끝 4)·t2(끝 6)와 t3(끝 4) 가운데
                             끝이 가장 먼 t2 를 넘기고, t3 가 t2 의 r1 을 물려받는다
t4        [3 ── 5]       t4: 여전히 꽉 참. t1·t3(끝 4)·t4(끝 5) 가운데 끝이 가장 먼 것은 t4 자신 → t4 를 넘긴다
t5          [4 ─ 5]      t5: 시작 4 — 끝이 4 인 t1·t3 는 아직 쓰는 중(같으면 풀지 않는다) → 넘긴다

끝이 가장 먼 것을 넘기는 이유는, 그 값이 레지스터를 가장 오래 붙잡을 것이기 때문입니다. 넘긴 값은 쓸 때마다 메모리에서 읽고 씁니다(8모듈의 슬롯이 바로 그 자리입니다). 새 구간 앞에서는 끝이 새 시작보다 작은 구간만 풀어 줍니다 — 같은 명령에서 끝나는 값은 그 명령이 아직 읽는 중이기 때문입니다. 이 한 글자(< 와 <=)가 가장 흔한 실수입니다.

mark-sweep. 힙을 '객체 → 가리키는 객체들' 의 그래프로 보면, 뿌리(스택과 전역에 있는 값)에서 따라가 닿는 객체만 살아 있습니다. 표시(mark) 단계는 뿌리에서 그래프를 훑어 닿는 것에 표시하고, 쓸기(sweep) 단계는 표시가 없는 것을 모두 치웁니다. 순환(A ↔ B)이 있어도 이미 표시한 것은 다시 보지 않으므로 끝나고, 뿌리에서 떨어져 나간 순환은 통째로 치워집니다. 표시를 재귀로 짜면 10만 개짜리 연결 리스트에서 재귀 한도를 넘으니, 명시적인 스택으로 훑습니다.

참조 수가 놓치는 것. 객체마다 "몇 곳이 나를 가리키나" 를 세어 0 이 되면 바로 치우는 방식(참조 수)은 표시 단계 없이 즉시 치워서 정지가 없습니다. 그러나 A 와 B 가 서로를 가리키면 뿌리에서 떨어져도 수가 1 에서 내려가지 않아 영원히 남습니다. CPython 이 참조 수를 기본으로 쓰면서도 순환을 찾는 수거기(gc 모듈)를 따로 두는 까닭입니다.

현장에서 만나는 모습

• JIT 는 선형 스캔을 좋아한다. 그래프 색칠(graph coloring) 방식은 레지스터를 더 잘 쓰지만 느립니다. 실행 중에 컴파일해야 하는 JIT(HotSpot 의 C1, V8 의 초기 단계)는 빠른 선형 스캔 계열을 씁니다 — 컴파일 시간이 곧 사용자가 기다리는 시간이기 때문입니다.
• GC 정지. mark-sweep 은 표시하는 동안 프로그램을 멈춰야 합니다(그 사이에 포인터가 바뀌면 표시가 틀립니다). 힙이 크면 이 정지가 수백 밀리초가 됩니다. 실제 JVM 이 이 정지를 어떻게 로그로 남기고 무엇으로 줄이는지는 힙은 남았는데 서비스가 멈췄다 코스의 GC 로그 모듈이 다룹니다.
• GC 없이 치우기. Rust 는 수거기 없이 '이 값의 주인이 사라지는 곳' 을 컴파일할 때 정해 그 자리에 해제 코드를 넣습니다. 4모듈의 스코프 분석을 값의 수명까지 넓힌 것이라 할 수 있고, Rust — 컴파일러가 막는 것들 코스가 그 규칙을 오류 메시지로 읽습니다.

다음 실습에서 할 것

regalloc.py 에 직선 코드의 활성 분석, 활성 구간과 최대 동시 활성 수, 선형 스캔, 할당 검증기, 반복문이 있는 CFG 의 블록별 활성 분석을 만들고, heap.py 에 표시·쓸기, 참조 수가 놓치는 쓰레기 계산, 할당 기록을 따라 도는 수거기를 만듭니다. 채점기는 무작위 코드·그래프·힙·기록 수백 개로 기준과 대조합니다.