13장. 레지스터 할당

유한한 레지스터, 무한한 변수 — 그래프 색칠하기와 spill 비용의 미학.

원서 범위: pp. 679–724 키워드: register allocation, live range, interference graph, graph coloring, spilling, coalescing

13.1 들어가며: 자리는 부족하고 줄은 길다

레지스터(register)는 메모리 계층에서 가장 빠른 자리다. 대부분의 프로세서에서 연산이 직접 만질 수 있는 유일한 메모리이기도 하다. 연산 유닛 바로 옆에 붙어 있어서, 레지스터를 잘 쓰는 일은 곧 런타임 성능 그 자체다. 컴파일러에서 이 자원을 책임지는 사람이 레지스터 할당기(register allocator)다.

레지스터 할당기가 매 순간 답해야 할 질문은 두 개다. 어떤 값을 레지스터에 두는가? 그리고 그 값은 어느 레지스터에 들어가는가? 둘 다 답이 안 나오면 메모리에 보내야 한다. 보내는 이유는 두 가지인데, 하나는 살아 있는 값이 레지스터 개수보다 많아서, 다른 하나는 컴파일러가 그 값을 레지스터에 안전하게 둘 수 있다고 증명하지 못해서다.

   입력 프로그램   ┌────────────┐   출력 프로그램
   n 레지스터  ──▶│ Register   │──▶ m 레지스터
                  │ Allocator  │
                  └────────────┘

레지스터 할당기를 블랙박스로 보면 — 입력은 가상 레지스터를 마음대로 쓰는 코드, 출력은 타깃 머신의 유한한 레지스터에 끼워맞춘 코드.

할당기는 값을 메모리와 레지스터 사이로 옮기기 위해 load/store를 추가로 끼워넣어야 할 수도 있다. 이렇게 끼워넣은 코드를 spill 코드(spill code)라 부른다. 좋은 할당기는 (1) spill 코드의 실행 시간, (2) 차지하는 코드 공간, (3) 빠져나간 값이 잡아먹는 데이터 공간 — 이 셋을 모두 줄이려고 한다.

spill 코드 (spill code) — 레지스터 할당기가 추가로 삽입한 load와 store. 본질적으로는 "레지스터가 모자라서 메모리 다녀오는 비용"이다.

알고리즘적 본질

레지스터 할당의 일반형은 NP-완전(NP-complete)이다. 즉 최적해는 다항 시간으로 못 구한다. 그래서 좋은 할당기는 "어려운 문제에 대한 효과적인 근사 해를 빠르게" 계산한다. 이 책 전체에서 가장 노골적으로 NP-hard와 부딪히는 단원이기도 하다.

13.2 배경 이야기 — 메모리 모델, 할당과 배정, 레지스터 클래스

레지스터 할당기에 도착할 즈음의 코드는 거의 모든 단계를 거친 상태다. 스캔, 파스, 검사, 분석, 최적화, 타깃 코드 변환, 어쩌면 스케줄링까지 끝났다. 그래서 이전 단계들이 내린 결정이 할당기의 일거리를 좌우한다. 이 절에서는 그 환경을 만드는 세 가지 요인을 본다.

13.2.1 메모리 vs 레지스터 — 어떤 메모리 모델을 골랐나

컴파일러를 만들 때 메모리 모델(memory model) 선택은 IR의 모양과 할당기의 일거리를 동시에 결정한다.

레지스터-투-레지스터 모델(register-to-register model): 컴파일러의 앞단이 "이 값은 모호하지 않으니 레지스터에 둬도 된다"고 판단되는 값을 가상 레지스터(virtual register)에 넣어버린다. 메모리에 있는 값은 모호하다고 가정하고 그냥 거기 둔다. 이 경우 할당은 합법성 자체의 문제다 — 가상 레지스터 무한대를 물리 레지스터 유한 개에 끼워맞추지 않으면 코드가 굴러가지 않는다.
메모리-투-메모리 모델(memory-to-memory model): 모든 값이 메모리에 산다. 할당기는 "메모리에 있는 값 중 어느 것을 레지스터로 끌어올릴 수 있는가, 끌어올리는 게 이득인가"를 결정한다. 이 모델에서는 할당이 최적화다. 안 해도 코드는 합법, 하면 빨라질 뿐.

실무에서는 레지스터-투-레지스터 모델이 우세하다. 이유는 단순하다. 컴파일러 앞단(파서, 타입 분석)이 모호함과 유일성에 대한 지식을 IR의 모양에 직접 새겨 넣을 수 있기 때문이다. 메모리-투-메모리 모델은 그 지식을 분석으로 다시 발굴해야 한다.

13.2.2 할당 vs 배정 — 같은 동전의 양면

레지스터 할당기가 푸는 문제는 사실 두 개로 쪼개진다.

할당 (Allocation) (register allocation) — "어느 값을 레지스터에 둘까?"의 답. 무한한 이름 공간을 물리 레지스터 집합 + 메모리에 사상한다. 모든 명령어 시점에서 레지스터에 거주하는 값의 개수가 k개를 넘지 않도록 보장한다.

배정 (Assignment) (register assignment) — "그 값을 정확히 어느 레지스터에 둘까?"의 답. 할당 결과로 만들어진 이름 집합을 실제 물리 레지스터 번호로 바꾼다.

이 둘이 어떻게 다른가? 할당은 어렵고, 배정은 (보통은) 쉽다. 하나의 레지스터 종류만 있고 매 명령어 시점의 수요가 k 이하라면 — 즉 할당이 이미 잘 되어 있다면 — 배정은 구간 그래프 색칠(interval-graph coloring)로 다항 시간에 풀린다. 어려움은 거의 항상 할당에 몰려 있다.

구간 그래프 (interval graph) — 실수 직선 위 구간들의 겹침을 나타내는 그래프. 노드는 구간 하나, 간선 (i,j)는 두 구간이 겹친다는 표시. 일반 그래프와 달리 k-색칠을 다항 시간에 풀 수 있다.

13.2.3 레지스터 클래스 — 종류가 다르면 따로 논다

현실의 프로세서는 모든 레지스터를 균일한 풀(pool)로 주지 않는다. 거의 항상 종류가 갈린다. 가장 흔한 분리는 범용 레지스터(general-purpose register)(정수, 주소)와 부동소수점 레지스터(floating-point register)다. IBM 360의 16+4 구성 시절부터 있던 이야기다. 현대 ISA는 더 많은 클래스를 들고 있다 — PowerPC는 조건 코드용 레지스터를, Intel IA-64는 술어(predicate)와 분기 타깃용 레지스터를 따로 가진다.

두 클래스가 서로 닿지 않으면 컴파일러는 그것들을 독립적으로 할당할 수 있다. 작은 문제를 여러 개로 쪼개서 풀면 자료 구조 크기가 줄고 컴파일 시간도 빨라진다. 반대로 클래스가 겹치면 — 예: x86에서 32비트 레지스터를 1×32비트 / 2×16비트 / 4×8비트로 쓸 수 있는 경우, 또는 단정밀도 두 개와 배정밀도 하나가 같은 레지스터 쌍을 두고 다툴 때 — 한꺼번에 풀어야 한다.

13.3 지역 레지스터 할당과 배정 — 한 블록 안에서

전역 할당으로 가기 전에, 가장 단순한 경우부터 본다. 기본 블록(basic block) 하나만 있는 상황. 이 동네에서는 제어 흐름이 일직선이라 "이 값이 다음에 언제 쓰이는가"를 거리(distance)로 정확히 측정할 수 있다.

가정은 이렇다. 블록은 가상 레지스터 vr_i를 자유롭게 쓰고, 타깃 머신은 물리 레지스터 k개를 준다. 가상 레지스터 수가 k를 넘으면 일부를 메모리로 빼야 한다. 두 가지 접근이 있다.

13.3.1 톱다운 지역 할당 — "많이 쓰이는 놈이 임자"

아이디어는 단순하다. 가장 자주 등장하는 값일수록 레지스터에 살 자격이 있다. 알고리즘:

각 가상 레지스터의 등장 빈도를 센다 (블록을 한 번 훑으면 끝).
빈도순으로 정렬한다.
상위 k − F개 가상 레지스터에 물리 레지스터를 영구 배정한다. 여기서 F는 "spill 코드를 만드는 데 필요한 예약 레지스터 수" — RISC라면 보통 2~4개.
코드를 다시 훑으면서 가상 레지스터 이름을 물리 레지스터 이름으로 바꿔 쓰고, 배정받지 못한 가상 레지스터는 예약 레지스터로 잠깐 끌어와 쓰는 짧은 시퀀스로 대체한다.

이 방식의 약점은 명확하다. 한 가상 레지스터에 한 물리 레지스터를 블록 전체 동안 잡아둔다. 어떤 값이 블록 전반에서만 자주 쓰이고 후반에는 안 쓰여도, 그 레지스터는 후반 내내 놀게 된다. 자원의 시간적 낭비가 발생한다.

13.3.2 보텀업 지역 할당 — "다음에 쓰일 때까지 가장 먼 놈을 쫓아내자"

보텀업 할당은 결정의 단위가 다르다. 전체 블록을 한꺼번에 보지 않고, 연산 단위로 결정한다. 각 연산 op vr_i1, vr_i2 ⇒ vr_i3마다 (1) 두 피연산자가 레지스터에 있도록 보장하고, (2) 결과를 담을 레지스터를 확보한다.

/* 보텀업 지역 할당기 */
for each operation, i, in order from 1 to N
    where i has the form: op vr_{i1}, vr_{i2} => vr_{i3}

    r_x ← Ensure(vr_{i1}, class(vr_{i1}))   /* 첫 피연산자를 레지스터에 */
    r_y ← Ensure(vr_{i2}, class(vr_{i2}))   /* 둘째 피연산자를 레지스터에 */

    if vr_{i1} is not needed after i then Free(r_x, ...)
    if vr_{i2} is not needed after i then Free(r_y, ...)

    r_z ← Allocate(vr_{i3}, class(vr_{i3}))  /* 결과 자리 잡기 */
    rewrite i as: op r_x, r_y => r_z

    /* 다음 사용 거리 갱신 */
    if vr_{i1} is needed after i then class.Next[r_x] ← Dist(vr_{i1})
    if vr_{i2} is needed after i then class.Next[r_y] ← Dist(vr_{i2})
    class.Next[r_z] ← Dist(vr_{i3})

보텀업 지역 할당기의 골격. Ensure는 "필요한 값을 레지스터에 올려놓기", Allocate는 "빈 레지스터 잡기 또는 누군가 spill"이다.

핵심 휴리스틱은 Allocate가 빈 레지스터를 못 찾았을 때다. 이 알고리즘은 "다음에 쓰일 때까지 가장 먼" 값을 쫓아낸다. 직관적으로 말하면, 가장 오래 쓰이지 않을 값을 메모리로 보내서 그 시간 동안 레지스터를 다른 일에 쓰자는 것이다. 잘 알려진 캐시 교체 정책 — Belady의 OPT — 와 같은 아이디어다.

clean과 dirty — 모든 spill이 같지 않다

어떤 값을 메모리로 보낼 때, 그 값이 이미 메모리에 있는 형태와 같다면 store는 필요 없다. 상수로 만들어진 값이나 load로 가져온 값이 그 예다. 이런 값을 clean, store가 필요한 값을 dirty라 부른다. 최적 할당은 clean과 dirty의 비용 차이를 고려해야 한다 — 어떤 참조 시퀀스에서는 clean을 spill하는 게 이득이고, 다른 시퀀스에서는 dirty를 spill하는 게 이득이다. 단순한 "가장 먼 사용" 규칙은 이 차이를 잡지 못한다. 그래서 최적 지역 할당은 NP-hard다. 그래도 보텀업은 실무에서 매우 좋은 결과를 낸다.

13.3.3 단일 블록 너머로 — 왜 지역만으로는 안 되나

지역 할당기는 단일 블록 안에서는 잘 작동한다. 그런데 진짜 프로그램에서 값은 블록 사이를 흐른다. 어떤 값을 한 블록에서 만들고 다른 블록에서 쓰는 일은 일상이다. 지역 할당기를 그대로 여러 블록에 적용하려고 하면 곳곳에서 무너진다.

지역 할당기를 여러 블록에 그대로 쓰려 할 때 생기는 문제

변수 x가 네 블록 B₁, B₂, B₃, B₄에서 각각 r₁, r₂, r₃, r₄에 할당되었다고 하자. B₁→B₂로 흐르는 길에서 r₁의 값을 r₂로 옮겨야 한다. 안전한 일반 해법은 B₁ 끝에서 메모리에 store하고 B₂ 시작에서 load하는 것뿐이다. 컨트롤 흐름 그래프를 자유롭게 수정할 수 없다면 register-to-register copy도 모든 경우에 들어맞게 끼워넣을 수 없다 (이른바 critical edge 문제). 결국 메모리 트래픽이 늘어난다.

또 보텀업의 핵심 수치인 "다음 사용 거리"가 다중 블록에서는 다중 값이 되어 정의가 모호해진다. 어떤 후행 경로를 따라 가는지에 따라 거리가 달라지기 때문이다.

이 문제들은 본질적으로 지역 할당기의 시야 밖에 있다. 그래서 다중 블록 할당은 지역 할당의 단순 확장이 아니라 완전히 다른 알고리즘으로 풀어야 한다. 그게 다음 절의 주제다.

13.4 전역 레지스터 할당과 배정 — 그래프 색칠의 등장

전역 할당기는 spill 코드의 충격을 줄이려고 한다. 충격은 (1) 실행 시간, (2) 코드 공간, (3) 데이터 공간 세 갈래다. 보통 첫 번째에 집중한다. 전역이 지역과 본질적으로 다른 이유는 두 가지.

전역 라이브 레인지의 구조가 더 복잡하다. 지역에서는 라이브 레인지가 직선 코드의 구간이지만, 전역에서는 정의와 사용이 얽힌 거미줄(web)이다. 한 사용에 도달하는 모든 정의, 한 정의가 닿는 모든 사용 — 이들이 한 라이브 레인지로 묶여야 한다.
spill 비용이 위치에 따라 다르다. 지역 블록 안에서는 모든 참조가 같은 횟수로 실행되니 비용이 균일하다. 전역에서는 어떤 참조가 깊은 루프 안에 있느냐, 가끔 가는 if-branch에 있느냐에 따라 비용이 천차만별이다.

그래프 색칠 (Graph Coloring) 잠깐 정리

임의 그래프 G의 색칠이란 인접한 두 노드가 같은 색을 받지 않도록 각 노드에 색을 부여하는 것. k가지 색으로 색칠 가능하면 k-색칠 가능하다고 부른다. 가장 작은 그런 k를 채색수(chromatic number)라 한다.

임의 그래프의 채색수 결정은 NP-완전이다. 고정된 k에 대해 k-색칠 가능한지 묻는 것도 NP-완전(k≥3). 그래서 그래프 색칠을 자원 할당에 쓰는 알고리즘은 모두 근사적이다.

이 사실이 전역 할당의 메타포가 된다. 컴파일러는 인터퍼런스 그래프(interference graph) I를 만든다. 노드는 라이브 레인지, 간선은 "두 라이브 레인지가 동시에 살아 있어 같은 레지스터를 쓸 수 없다"는 충돌 표시다. 이 그래프의 k-색칠을 찾으면 그게 곧 합법 할당이다 — 색이 곧 물리 레지스터다. 못 찾으면? 코드를 수정해서(=spill) 그래프를 더 색칠하기 쉬운 모양으로 바꾼 뒤 다시 시도한다.

인터퍼런스 그래프 (interference graph) — 노드는 라이브 레인지(live range), 간선 (i,j)는 LR_i와 LR_j가 같은 레지스터를 공유할 수 없음을 뜻함.

간섭 (Interference) — 두 라이브 레인지 LR_i와 LR_j는, 한쪽이 정의되는 시점에 다른 쪽이 살아 있고 두 값이 다르다면 간섭한다.

13.4.1 전역 라이브 레인지 찾기 — SSA가 길을 잡아준다

전역 라이브 레인지를 만들려면 정의와 사용 사이의 도달 관계를 풀어야 한다. 한 정의가 어떤 사용에 도달하는가? 한 사용에 어떤 정의들이 도달하는가? 같은 라이브 레인지에 묶일 정의-사용은 한 그룹이다.

SSA 형식(static single-assignment form)이 이 작업의 자연스러운 출발점이다. SSA에서는 각 이름이 정확히 한 번 정의되고, 각 사용은 단일 정의를 참조한다. 컨트롤 흐름이 합쳐지는 지점에서 φ-함수가 여러 정의를 하나의 이름으로 합쳐주는데, 이 φ-함수가 "어떤 정의들이 한 바구니에 들어가야 하는가"를 그대로 알려준다.

알고리즘: φ-함수에 대해 union-find

1. 각 SSA 이름(정의)을 자기 자신만 들어 있는 집합으로 시작한다.
2. 각 φ-함수마다, 그 결과의 집합과 모든 인자의 집합을 union으로 합친다.
3. 모든 φ-함수를 처리하면, 남은 집합들이 곧 라이브 레인지다.

예를 들어 코드에 SSA 이름 a₀, b₀, c₀, d₀, d₁, d₂가 있고 φ-함수 d₂ ← φ(d₀, d₁)이 있다면, {d₀, d₁, d₂}가 합쳐져 LR_d가 된다. 나머지는 각각 자기만의 LR을 갖는다 — LR_a, LR_b, LR_c.

13.4.2 전역 spill 비용 추정

그래프가 k-색칠 안 될 때 어떤 라이브 레인지를 spill할지 결정하려면, 각 LR을 spill하는 데 드는 비용을 알아야 한다. 비용의 구성:

주소 계산: 보통 활성 레코드(activation record, AR) 안 register-save area에 두면 ARP 기준 상대 주소로 끝나서 거의 공짜다.
메모리 연산: 정의 후 store, 사용 전 load. 메모리 지연 시간이 클수록 무겁다.
실행 빈도: 어디 위치한 참조냐에 따라 가중치가 곱해진다.

실행 빈도 추정의 관행

컴파일러는 각 블록에 실행 횟수 추정값을 매긴다. 프로파일 데이터가 있으면 그걸 쓰고, 없으면 휴리스틱이 동원된다. 흔한 가정: 한 루프는 10회 실행. 따라서 한 겹 루프 안의 참조는 ×10, 두 겹 루프 안은 ×100. if-then-else는 빈도를 절반으로 나눈다. 정밀하지는 않지만, "안쪽 루프보다 바깥 루프에서 spill하라"는 편향을 만들어주는 데는 충분하다.

음수 spill 비용

같은 주소를 가리키는 load와 store만 있고 다른 사용이 없는 라이브 레인지는 음수 비용을 가져야 한다. spill하는 게 오히려 코드를 줄여주기 때문이다. 그런 LR이 발견되면 무조건 spill해야 한다. 레지스터 수요도 줄고 명령어도 사라진다 — 일석이조.

무한 spill 비용

너무 짧은 라이브 레인지(정의 직후 사용)는 spill해봐야 store + load 두 명령어가 새 LR로 추가될 뿐, 원래 LR보다 짧지 않다. 이런 LR은 spill로 얻을 게 없으니 비용을 ∞로 매겨 절대 spill 후보에서 빠지게 한다. 일반화하면, 정의와 사용 사이에 다른 LR이 끝나지 않는 LR은 모두 무한 비용이다.

13.4.3 인터퍼런스 그래프 만들기

라이브 레인지가 정해지고 각 블록의 LiveOut 집합이 계산되었다면, 그래프는 블록 단위로 한 번씩 훑으면 만들어진다. 알고리즘은 LiveNow를 LiveOut으로 초기화한 뒤 블록을 거꾸로 따라가며 매 연산마다 간선을 추가한다.

for each LR_i: create a node n_i ∈ N

for each basic block b:
    LiveNow ← LiveOut(b)

    for each operation op_n, op_{n-1}, op_{n-2}, ..., op_1 in b:
        with form op_i: LR_a, LR_b => LR_c

        for each LR_j ∈ LiveNow:
            add (LR_c, LR_j) to E

        remove LR_c from LiveNow
        add LR_a and LR_b to LiveNow

인터퍼런스 그래프 만들기. 거꾸로 훑으면서 "정의 시점에 살아 있는 모든 LR"과 정의 대상 사이에 간선을 긋는다.

copy 연산은 특별 대우

copy LR_i ⇒ LR_j는 두 LR이 같은 값을 갖게 만든다. 따라서 같은 레지스터에 둬도 안전하다 — 이 연산만으로는 (LR_i, LR_j) 간선을 만들지 않는다. 이후 다른 맥락에서 진짜 충돌이 생기면 그때 간선이 추가된다. 같은 이유로 φ-함수도 인자와 결과 사이에 간선을 만들지 않는다. 이 처리는 뒤에 나올 coalescing에 결정적이다.

실용 팁: 그래프 자료구조는 하삼각 비트 행렬(lower-diagonal bit matrix)과 인접 리스트(adjacency lists)를 같이 들고 다닌다. 비트 행렬은 (i,j) 간선이 있는지 상수 시간에 체크하고, 인접 리스트는 한 노드의 이웃을 빠르게 순회한다. 공간을 두 배 쓰지만 할당 시간이 크게 줄어든다.

13.4.4 톱다운 색칠 — 우선순위가 골라준다

색칠 단계에서도 톱다운과 보텀업이 갈린다. 톱다운은 외부에서 매겨준 우선순위(priority) — 보통 라이브 레인지 보존 시 절약되는 런타임 예상치 — 에 따라 LR을 정렬한다. 우선순위가 높은 LR부터 색을 시도한다.

핵심 분류는 제약 LR(constrained)과 비제약 LR(unconstrained)이다. 차수(degree)가 k 이상이면 제약, 미만이면 비제약. 비제약 LR은 이웃들이 모든 색을 다 써도 항상 빈 색이 하나는 남는다 — 그래서 항상 색칠 가능. 톱다운 알고리즘은 제약 LR부터 우선순위 순으로 색칠하고, 비제약 LR은 마지막에 임의 순서로 처리한다.

우선순위 순서로 그냥 가면 어떤 일이 생길까? 비제약이지만 우선순위가 높은 이웃이 모든 색을 잡아먹어서, 이론상 색칠 가능한 제약 LR이 색칠을 못 받는 일이 생긴다. 그래서 제약 LR을 먼저 처리하는 것이다.

spill 처리

색칠을 못 받은 LR은 spill하거나 split해야 한다. spill은 정의 뒤마다 store, 사용 앞마다 load를 끼워넣어 LR을 잘게 부수는 것이다. split은 LR을 더 큰 조각 몇 개로 나눠서 그 조각들이 더 적은 LR과 충돌하기를 기대하는 것이다.

톱다운에서 spill 코드 자체가 레지스터를 필요로 한다는 모순이 있다 — 그래서 보통 약간의 레지스터를 spill 전용으로 예약한다. 예약은 k를 사실상 줄이는 효과가 있어, 그 자체로 spill을 더 일으킬 수 있다는 역설이 따라온다.

13.4.5 보텀업 색칠 — 그래프 구조가 순서를 정한다

보텀업은 그래프 구조로 색칠 순서를 결정한다. 외부 우선순위가 아니다. 핵심 통찰: 모든 노드를 자기보다 적은 수의 이미 색칠된 이웃을 갖는 시점에 색칠하면, 그 노드는 항상 색을 받는다.

/* 색칠 순서 결정 (reduction) */
initialize stack to empty
while (N ≠ ∅):
    if ∃ n ∈ N with n° < k:        /* 비제약 노드 우선 */
        node ← n
    else:
        node ← n picked from N      /* spill metric으로 고름 */
    remove node and its edges from I
    push node onto stack

/* 색칠 (reverse order) */
while (stack ≠ ∅):
    node ← pop(stack)
    insert node and its edges back into I
    color node                      /* 이웃의 색을 보고 빈 색 하나 고름 */

보텀업 그래프 색칠. 비제약 노드부터 차례로 빼서 스택에 쌓고, 빼낸 역순으로 다시 끼워넣으며 색칠한다.

알고리즘은 두 단계다. 축소(reduction): 비제약 노드(차수 < k)를 찾아 그래프에서 제거하고 스택에 푸시. 비제약 노드가 없으면 spill metric으로 한 노드를 골라 제거(이건 색을 못 받을 수 있다). 색칠(coloring): 스택에서 팝하며 노드와 간선을 다시 끼워넣고, 이웃의 색을 보고 빈 색을 부여.

왜 작동하는가

한 노드를 그래프에서 제거할 때 비제약이었다면, 다시 끼워넣는 시점에도 비제약이다 — 그동안 다른 노드들이 더 들어왔지만, 이 노드의 이웃은 변하지 않는다. 따라서 색을 받지 못할 위험은 오직 spill metric으로 강제 제거된 노드에만 존재한다. 그것마저도 운이 좋으면 색을 받을 수 있는데, k개 이웃이 우연히 같은 색을 공유했을 경우다.

spill metric — 어떤 노드를 강제 제거할까

모든 남은 노드가 제약일 때 골라야 하는 한 명. Chaitin et al.의 원조 보텀업 할당기는 비용/차수(cost/degree) 비율을 최소화하는 노드를 골랐다. 직관: 비용은 작고 (싸게 spill되고) 차수는 크다 (제거 시 다른 노드의 차수를 많이 줄여준다)면 좋다.

변형도 많다 — cost/degree²는 이웃에 미치는 영향을 더 강조, straight cost는 런타임 속도만 본다, spill 연산 수만 세는 metric은 코드 크기를 줄인다. 정답은 없고, 실무에서는 여러 metric으로 색칠을 시도해 가장 좋은 결과를 고르기도 한다 — 색칠 자체가 빠르니까 가능한 전략이다.

13.4.6 Coalescing — 복사 명령어 없애기

인터퍼런스 그래프는 또 다른 용도로 쓰인다. 두 LR이 copy 연산 i2i LR_i ⇒ LR_j로 연결되어 있고 둘 사이에 간선이 없다면, 두 LR을 합쳐서 한 LR로 만들 수 있다. 이걸 coalescing이라 한다.

합치면 다음 효과가 한꺼번에 발생한다.

copy 연산이 사라진다 (코드 단축, 빨라짐).
합쳐진 LR은 양쪽의 이웃을 합집합으로 가지므로, 양쪽 모두와 충돌하던 다른 LR의 차수가 줄어든다.
전체 LR 개수가 줄어들어 I를 비롯한 자료 구조가 작아진다.

차수가 줄어드는 효과가 핵심이다. 합치기는 다른 노드의 차수를 절대 늘리지 않는다 — 줄이거나 그대로 두거나 둘 중 하나다. 그래서 보통 색칠 전에 coalescing을 한다. Briggs의 논문은 코드에 따라 라이브 레인지의 1/3까지 합쳐 없앤다는 예를 보여준다.

전체 흐름은 build-coalesce 루프

실무 보텀업 할당기의 흐름:
1. 라이브 레인지 찾기 → 인터퍼런스 그래프 빌드.
2. coalescing 한 라운드 — 합칠 수 있는 모든 copy를 합친다.
3. 합쳐졌으니 그래프가 달라졌다 → 다시 빌드해서 더 합칠 게 있나 확인.
4. 더 합칠 게 없으면 spill 비용 계산 → 색칠 시도 → spill 코드 삽입(필요 시) → 다시 처음부터.

보통 두어 라운드면 끝난다. 첫 빌드가 가장 비싸고, 이후 라운드는 더 작은 그래프라 빠르다.

13.4.7 톱다운 vs 보텀업 — 어디가 다른가

두 알고리즘은 큰 골격은 같다. 라이브 레인지 찾기 → 인터퍼런스 그래프 만들기 → coalescing → spill 비용 계산 → 색칠 → 색칠 안 된 LR 처리.

차이는 색칠 순서를 결정하는 정보 종류다.

	톱다운	보텀업
순서 결정	외부 우선순위 (예상 절약 시간)	그래프 구조 (차수 < k 우선)
spill 처리	예약 레지스터 사용	spill-and-iterate (전체 다시)
비제약 노드 처리	제약 처리 후 임의 순서	처음부터 우선 제거
"진짜 어려운 노드"	우선순위 순으로 색칠 시도	spill metric으로 후보 선정
예약 vs 반복	예약 = 빠름, 더 많은 spill 가능	반복 = 느림, 더 적은 spill

두 알고리즘의 성능을 결정짓는 부분은 "보텀업이 spill metric으로 강제 제거하는 노드들"이다. 이 노드들이야말로 그래프에서 가장 색칠하기 어려운, 강하게 연결된 부분 그래프를 이루는 노드들이다. 톱다운은 이 노드들을 우선순위 순으로 처리하고, 보텀업은 spill metric (비용 + 차수의 균형)으로 처리한다.

선형 스캔 할당 — JIT 컴파일러의 단골

linear scan allocation은 전역 LR을 단순 구간 [i,j]로 표현해 색칠 단순화를 시도한다. 구간 그래프는 k-색칠을 다항 시간으로 풀 수 있어서 정확한 인터퍼런스 그래프를 만들지 않아도 된다. 정밀도는 떨어지지만 컴파일 시간이 압도적으로 짧아서 JIT(just-in-time) 컴파일러에서 자주 쓰인다. "할당 속도" vs "spill 코드 양"의 trade-off가 분명한 사례다.

13.4.8 머신 제약을 그래프에 인코딩하기

실제 ISA는 일반적인 그래프 색칠 모델에 잘 안 맞는 제약을 잔뜩 가진다. 두 가지 흔한 사례.

다중 레지스터 값

배정밀도(double-precision) 부동소수점 값이 인접한 정렬된 레지스터 쌍을 요구한다고 하자. 이걸 표준 인터퍼런스 그래프로만 모델하면, 주위 단정밀도 LR이 두 번째 레지스터 자리를 차지해서 쌍을 못 잡게 만들 수 있다.

해결: 그런 LR 노드의 차수를 인위적으로 부풀린다. 모든 이웃에 간선을 두 개씩 — 즉 다중 간선을 사용한다. 이렇게 하면 그래프 축소 알고리즘이 그 노드를 제약으로 정확히 인식하고, 두 레지스터를 모두 잡아주는 시점에야 색칠을 시도하게 된다.

특정 레지스터 배치

호출 규약(linkage convention)은 인자나 반환 값을 특정 레지스터에 두라고 강요한다. PowerPC에서는 함수 반환값이 r3에 떨어진다. x86의 imul은 결과를 ax에 쓴다. 이런 LR을 다른 LR과 합치면 충돌이 생긴다.

해결책 두 가지가 있다.

가상 레지스터 vr_i를 r3 외 모든 물리 레지스터에 인터퍼런스 간선을 추가해서 r3로만 색칠 가능하게 강제. 깔끔하지만 그래프를 과도하게 제약할 수 있다.
코드 모양으로 풀기 — 호출 직전에 짧은 LR vr₁(=r3에만 매핑되는)을 만들고 copy vr₁ ⇒ vr_i로 분리. 그 짧은 LR만 r3에 묶이고 본 LR은 자유롭게 다닌다. 단, coalescing이 이 짧은 LR을 다른 LR과 합치지 않도록 막아야 한다 — 안 그러면 충돌이 다시 끼어들 수 있다.

13.5 고급 주제 — 그래프 색칠의 변형들

13.5.1 그래프 색칠 할당의 변종들

부정확한 인터퍼런스 그래프

Chow의 톱다운 우선순위 기반 할당기는 간섭 정의를 단순화했다. 두 LR이 같은 블록에서 둘 다 살아 있으면 간섭한다고 본다. 더 빠르게 그래프를 만들 수 있지만, copy로 연결된 두 LR도 같은 블록에 살아 있으면 충돌로 처리되어 coalescing이 막힌다. 이 손실을 보충하려고 같은 알고리즘은 단일 블록에만 사는 값에 대해 사전 지역 할당을 따로 돌렸다.

그래프를 작은 조각으로 쪼개기

인터퍼런스 그래프가 비연결 컴포넌트(connected component)로 분리될 수 있다면 컴포넌트별로 독립 색칠하면 된다. O(N²) 비트 행렬 크기를 절약한다. 가장 단순한 분리는 분리된 레지스터 클래스(부동소수점 vs 정수)다. 더 정교하게는 clique separator를 찾아 그래프를 잘게 나눈다.

보수적 coalescing

Coalescing은 차수를 절대 늘리지 않지만 — 노드 수준에서는 사실이지만 — 합쳐진 LR_ij의 차수가 LR_i나 LR_j 어느 쪽보다도 높을 수 있다. 둘 다 비제약(차수 < k)이었는데 합쳐서 제약(차수 ≥ k)이 되면 색칠이 어려워질 수 있다.

해결: conservative coalescing. 합쳤을 때 결과 LR이 "유의미한 차수(즉 차수 ≥ k)의 이웃"을 k개 미만으로 갖는 경우에만 합친다. 이 조건은 합쳐도 색칠 가능성을 해치지 않음을 보장한다.

이걸 더 발전시키면 iterated coalescing이 된다. 모든 LR이 제약이 되어 spill 후보를 골라야 할 때, 그 시점에 다시 한 번 coalescing을 시도한다. 그래프가 줄어든 만큼 이전엔 안전하지 않던 합치기가 안전해질 수 있다.

biased coloring

copy로 연결된 두 LR에 같은 색을 주려고 노력하는 색 선택 정책. 색 선택 시점에 이미 색칠된 copy 상대들이 받은 색을 우선 시도한다. 같은 색이 가능하면 copy가 자연스럽게 무의미해진다 — 사실상 사후 coalescing이다. 그래프를 어렵게 만들지 않으면서 copy를 줄인다.

부분 라이브 레인지 spill

전체 LR을 spill하는 건 종종 과잉이다. LR 대부분은 레지스터 수요가 낮은 구간에 있고, 작은 영역에서만 충돌한다면 그 영역만 spill하면 된다. 이걸 interference-region spilling이라고도 한다.

라이브 레인지 분할 (Live-Range Splitting)

spill의 대안. LR을 더 작은 조각으로 쪼개고, 그 조각들을 copy나 store/load로 이어준다. 작은 조각은 차수가 더 낮을 수 있어서 색을 받을 가능성이 높아진다. 분할 지점을 잘 고르면 spill 코드를 루프 바깥으로 밀어낼 수 있다 — 안에서 도는 것보다 훨씬 싸다. zero-cost splitting은 스케줄에서 nop으로 비어 있는 슬롯을 활용해 분할 비용을 0으로 만든다.

재구체화 (Rematerialization)

어떤 값은 메모리에서 다시 가져오는 것보다 다시 계산하는 게 싸다. 작은 정수 상수를 예로 들면, store + load 대신 load-immediate 한 명령어면 끝난다. 보텀업 할당기에 작은 변경을 더하면 SSA 이름에 "재구체화 가능" 태그를 붙이고 spill 시점에 재계산 코드로 대체할 수 있다.

모호한 값 (Ambiguous Values)

포인터, 배열 원소, 객체 참조처럼 같은 메모리 위치를 가리키는지 컴파일 타임에 못 가리는 값들. 이런 값을 레지스터에 못 두는 건 큰 성능 손실이다. scalar replacement는 배열-첨자 분석으로 재사용을 찾아내 임시 스칼라에 옮기고, register promotion은 데이터 흐름 분석으로 포인터 값을 루프 동안 레지스터에 안전하게 둘 수 있는지 판단해 코드를 바꿔준다. 둘 다 결국 "할당기에게 뜻을 명확히 알려주는" 코드 변환이다.

13.5.2 SSA 형식 위에서의 전역 레지스터 할당

최근 흥미로운 방향. SSA 이름을 직접 라이브 레인지로 쓰면 인터퍼런스 그래프가 chordal graph가 된다.

chordal graph — 길이 4 이상의 모든 사이클이 chord(사이클에 인접하지 않은 두 노드를 잇는 간선)를 갖는 그래프. 이 클래스의 k-색칠은 O(|V| + |E|) 다항 시간에 풀린다.

이 사실이 매력적인 이유는 최적 색칠을 (휴리스틱 없이) 다항 시간에 구할 수 있다는 점이다. 다만 SSA 형식은 — φ-함수가 살아 있는 동안만 — 코드를 그 모양으로 유지해야 하므로 SSA 해체(out-of-SSA translation)가 별도로 필요하다. 해체는 copy를 삽입하므로 일부 copy를 다시 처리해야 한다 (chordal 성질을 깨므로 인터퍼런스 그래프 기반 coalescing을 못 쓴다 — 다른 coalescing 알고리즘이 필요).

SSA 기반 할당기는 색칠 자체는 더 좋을 수 있지만 spill 선택과 배치 문제는 여전히 풀어야 한다. 이게 실제 성능을 더 크게 좌우하기 때문에, SSA 기반 할당기가 전통 할당기보다 항상 우위라고 단언하기는 어렵다.

13.6 요약 — 유한과 무한이 만나는 자리

레지스터 할당은 결국 유한한 자원에 무한한 수요를 끼워맞추는 문제다. 매 명령어 시점에서 살아 있는 값들이 물리 레지스터 개수를 넘어서면 누군가는 메모리에 다녀와야 한다. 그 다녀오기를 최소화하는 것이 할당기의 사명이다.

이 단원의 핵심 줄거리는 다음과 같다.

지역 할당은 단일 블록 안에서만 본다. 톱다운(빈도 기반)과 보텀업(다음 사용 거리 기반)이 양대 산맥이고, 보텀업이 보통 더 좋다.
전역 할당은 다중 블록 흐름을 처리하기 위해 완전히 다른 패러다임 — 그래프 색칠 — 을 채택한다.
인터퍼런스 그래프는 라이브 레인지 사이의 충돌을 노드와 간선으로 모델한다. k-색칠이 곧 합법 할당이다.
그래프 색칠은 NP-완전이다. 그래서 모든 실용 할당기는 휴리스틱 — 톱다운(우선순위)이나 보텀업(차수 기반 축소 + spill metric) — 을 쓴다.
spill 비용 추정은 실행 빈도 추정에 크게 의존한다. 안쪽 루프보다 바깥 루프에서 spill하라는 편향을 만든다.
Coalescing은 copy 연산을 없애 코드를 줄이고 그래프를 단순화한다. 보수적 coalescing은 색칠 가능성을 깨지 않으면서 합친다.
실용적인 개선은 모두 색칠 패러다임이 실제 문제를 부정확하게 모델하는 지점을 공격한다 — 비용 모델 정교화, 부분 LR spill, 라이브 레인지 분할, 재구체화. 이 개선들은 패러다임을 실제 문제에 더 가깝게 만든다.

한 줄 요약

컴파일러 백엔드의 마지막 진짜 어려운 문제. k개의 자리에 무한히 많은 손님을 앉히는 결혼식 좌석 배치 — 누가 누구 옆에 앉으면 안 되는지(인터퍼런스), 어떤 손님이 빠지면 가장 덜 아쉬운지(spill 비용), 같은 사람을 두 번 부르지 않을 방법(coalescing), 안쪽 테이블 대신 바깥 테이블에서 빼는 요령(루프 바깥 spill) — 이 모든 결정을 NP-완전이라는 어둠 속에서, 휴리스틱이라는 손전등 하나만 들고 빠르게 해내야 한다. 그래도 우리가 매일 쓰는 컴파일된 코드가 빠르게 도는 건, 이 한 손전등이 그동안 충분히 정교해졌기 때문이다.

← 이전12장. 명령어 스케줄링 다음 →부록 A. ILOC