Split Registers with Linear Scan, Then Mark and Sweep

목표

가상 레지스터를 쓰는 중간 코드에서 값이 살아 있는 구간을 구해 선형 스캔으로 실제 레지스터 k 개에 나누고, 반복문이 있는 CFG 의 활성 분석까지 합니다. 이어서 힙 그래프에서 뿌리에 닿는 객체만 남기는 mark-sweep 수거기를 만들고, 참조 수 방식이 무엇을 놓치는지 셉니다.

왜 중요한가

-O0 과 -O2 의 가장 큰 차이는 값을 레지스터에 두느냐이고, 그 결정은 '두 값이 동시에 살아 있는가' 에 달려 있습니다. 가비지 컬렉션은 그 반대편 — 실행 중에 만든 객체를 언제 버려도 되는가 — 을 같은 도구(그래프를 따라 닿는 것 찾기)로 풉니다. 둘 다 규칙 한 글자(< 와 <=, 재귀와 반복)에서 틀리기 쉽습니다.

규칙

중간 코드   명령 {"op", "def"(없을 수 있음), "use": [..]} 의 목록. 가상 레지스터마다 def 는 한 번(param 도 def)
liveness    명령마다 그 명령 **바로 뒤** 에 살아 있는 값(이름순 목록). 마지막 명령 뒤는 빈 목록
intervals   {값: [정의한 명령, 마지막으로 쓰는 명령]} (쓰지 않으면 [정의, 정의])
max_pressure 한 명령에서 쓰는 값 ∪ 정의하는 값 ∪ 그 뒤에 살아 있는 값 의 크기 가운데 최댓값
linear_scan(구간, k)  → {값: "r0".."r{k-1}" 또는 "spill"}
            시작 순(같으면 이름순)으로 훑는다. 새 구간 앞에서 끝 < 새 시작 인 활성 구간만 풀어 준다.
            빈 레지스터가 있으면 번호가 가장 작은 것. 없으면 활성 구간과 새 구간 가운데 끝이 가장 먼 것
            (끝이 같으면 이름이 큰 쪽)을 넘기고, 넘긴 것이 활성 구간이면 그 레지스터를 새 구간이 물려받는다
conflicts   같은 레지스터를 받은 두 구간이 겹치면(s1 ≤ e2 이고 s2 ≤ e1) [a, b](이름순), 목록도 정렬
block_liveness(blocks, succ)  → (live_in, live_out) 블록마다 이름순 목록. 고정점까지 되풀이
mark(heap, roots)   heap = {번호: [가리키는 번호…]}. 뿌리에서 닿는 번호(오름차순). 힙에 없는 뿌리는 무시.
                    재귀하지 않는다(10만 개짜리 연결 리스트도 받는다)
sweep(heap, marked) → (살아남은 힙, 치운 번호 오름차순)
refcount_leaks(heap, roots)  뿌리도 참조 하나로 센다. 0 인 것을 치우며 가리키던 것의 수를 줄이고 되풀이.
                    그래도 남았는데 뿌리에서 닿지 않는 번호(오름차순)
simulate(trace, capacity)  기록: ["alloc", n] · ["link", a, b] · ["unlink", a, b] · ["root", n] · ["unroot", n]
                    alloc 하려는데 힙이 capacity 개면 먼저 mark-sweep. 그래도 꽉 차면 "out of memory" 로 멈춘다.
                    → {"collections", "freed", "peak", "live"(끝의 번호 오름차순), "error"}

단계

1. /root/mini/regalloc.py 의 liveness(code) 를 채웁니다.
2. intervals(code) 와 max_pressure(code) 를 채웁니다.
3. linear_scan(ivs, k) 를 채웁니다 — 채점기가 레지스터 1·2·3·4·6개로 대조합니다.
4. conflicts(ivs, alloc) 를 채웁니다 — 올바른 할당에서 거짓 경보가 없어야 합니다.
5. block_liveness(blocks, succ) 를 채웁니다 — /opt/fixtures/mini/regalloc/loop.json 에 반복문 예가 있습니다.
6. /root/mini/heap.py 의 mark(heap, roots) 를 채웁니다.
7. sweep(heap, marked) 와 refcount_leaks(heap, roots) 를 채웁니다.
8. simulate(trace, capacity) 를 채웁니다 — /opt/fixtures/mini/regalloc/trace.json 이 손으로 따라가 볼 수 있는 예입니다.

참고

• 재료: /opt/fixtures/mini/regalloc/ 의 straight.json(손으로 셈해 볼 직선 코드)·pressure.json(레지스터가 모자라는 코드)·loop.json·trace.json.
• 흔한 실수: live-out 대신 live-in 을 돌려주는 것, 끝이 새 시작과 같은 구간을 풀어 주는 것, 넘길 때 늘 새 구간을 넘기는 것, CFG 를 한 번만 훑는 것, 표시를 재귀로 짜는 것, 순환에서 이미 본 객체를 다시 보는 것.
• 세션은 60분에 시작해 ＋시간으로 늘릴 수 있고, 끝나면 /root/mini 가 사라집니다.

뒤에서 앞으로 — 활성 분석

live 집합을 비워 두고 마지막 명령부터 거꾸로 걷습니다. 명령마다 먼저 지금 live 를 그 명령의 live-out 으로 적고, 그다음 def 를 빼고 use 를 더합니다(그것이 앞 명령의 live-out 이 됩니다).

활성 구간과 동시에 살아 있는 수

def 를 만나면 [i, i] 로 시작하고, use 를 만날 때마다 끝을 max(끝, i) 로 늘립니다. 최대 동시 활성 수는 명령마다 use·def·live-out 을 합친 집합의 크기 가운데 가장 큰 값입니다.

선형 스캔

시작 순으로 훑으며 활성 목록을 들고 다닙니다. 새 구간마다 먼저 끝 < 새 시작 인 것만 풀어 레지스터를 돌려받습니다(같으면 아직 쓰는 중). 빈 레지스터는 번호가 작은 것부터. 없으면 (끝, 이름) 이 가장 큰 것을 넘기고, 그것이 새 구간이 아니면 그 레지스터를 새 구간에 줍니다.

할당을 검증한다

spill 이 아닌 값들을 이름순으로 두고 모든 쌍을 봅니다. 같은 레지스터이고 구간이 겹치면(한쪽 시작 ≤ 다른 쪽 끝, 그리고 반대도) 충돌입니다. 끝과 시작이 맞닿은 것도 겹침입니다 — 그 명령이 둘 다 쓰기 때문입니다.

반복문이 있는 활성 분석

블록마다 use(블록 안에서 정의하기 전에 쓰인 것)와 def 를 먼저 구합니다. 그다음 live_out = 다음 블록들의 live_in 합집합, live_in = use ∪ (live_out − def) 을 모든 블록에 적용하기를, 한 바퀴 동안 아무것도 바뀌지 않을 때까지 되풀이합니다.

뿌리에서 닿는 것에 표시한다

재귀 대신 목록을 스택으로 씁니다. 힙에 있는 뿌리로 시작해, 꺼낸 객체가 이미 본 것이면 넘어가고, 아니면 표시한 뒤 그것이 가리키는 객체들을 쌓습니다. 이미 본 것을 건너뛰어야 순환에서도 끝납니다.

쓸기, 그리고 참조 수가 놓치는 것

sweep 은 표시된 것만 새 사전에 옮깁니다. refcount_leaks 는 모든 객체의 들어오는 참조 수(뿌리 포함)를 세고, 0 인 것을 치우며 그것이 가리키던 것의 수를 줄이기를 되풀이합니다. 끝까지 남았는데 mark 로 닿지 않는 것이 새는 몫입니다.

할당 기록을 따라 도는 수거기

alloc 을 만났는데 이미 capacity 개면 mark → sweep 한 뒤 수거 횟수와 치운 수를 더합니다. 그래도 capacity 개면 error 를 적고 멈춥니다. peak 는 alloc 직후의 객체 수 가운데 최댓값입니다. trace.json 을 손으로 따라가 보면 규칙이 보입니다.