SSA 형태의 IR을 대상으로 선형 스캔 레지스터 할당을 구현·해설한다. 라이브니스 분석, 스케줄링(명령 번호 매기기), 라이브 구간/인터벌 구성, 고전 선형 스캔(스필/만료), SSA 해소(병렬 이동 순차화·크리티컬 엣지 분할), 호출 처리(호출자-저장 레지스터, 인자/반환 레지스터), 추상 해석 기반 검증까지 단계별로 코드와 함께 설명한다. 역사적 문헌도 간략히 정리한다.
SSA에서의 선형 스캔 레지스터 할당
Aaron Patterson과 함께한 작업과 배움이 이 글의 바탕이 되었습니다.
레지스터 할당의 근본 문제는, 가상 레지스터(필요한 만큼 무한히 쓸 수 있음)를 사용하는 IR을 유한한 개수의 물리 레지스터와 스택 공간으로 다시 쓰는 것입니다1.
다음은 가상 레지스터를 사용하는 코드 조각의 예시입니다:
add R1, R2 -> R3
add R1, R3 -> R4
ret R4
그리고 아래는 레지스터 할당기를 거친 뒤의 동일 예시입니다(R가 P로 바뀐 점에 주의):
add Stack[0], P0 -> P1
add Stack[0], P1 -> P0
ret
각 가상 레지스터는 물리적 위치에 배정되었습니다: R1은 스택, R2는 P0, R3는 P1, 그리고 R4는(이제 R2를 더 이상 쓰지 않으므로) P0에도 배정되었습니다.
사람들은 레지스터 할당기를 쓰는 방식을 가비지 컬렉터를 쓰는 방식에 비유하곤 합니다. 비용이 좀 들 수는 있어도, 자원 관리를 대신해주는 추상화죠. 컴파일러 백엔드를 구현할 때, 다양한 타깃 아키텍처를 고려하며 수명 관리를 수작업으로 하는 것보다, 상자 속의 레지스터 할당기를 갖춰두는 편이 대개 훨씬 쉽습니다.
JIT 컴파일러는 레지스터 할당을 어떻게 할까요? “모두가 아는” 바에 따르면 “모든 JIT는 선형 스캔의 변종을 쓴다”고 합니다2. 저는 몇 개의 JIT에 참여했음에도 백엔드 부분을 끝내 잘 이해하지 못한 채로 이 통념이 오래도록 마음에 걸렸습니다.
레지스터 할당에는 몇 가지 접근법이 있지만, 이 글에서는 SSA 위에서의 선형 스캔에 초점을 맞춥니다.
제가 SSA를 만드는 여러 가지 방법을 쓴 뒤 Wimmer와 Franz의 Linear Scan Register Allocation on SSA Form (PDF, 2010)을 읽기 시작했습니다. 그런데 읽기만 해서는 잘 이해가 되지 않더군요—여백에 좌절의 흔적만 잔뜩 남았습니다. 그래서 논문과 나란히 구현을 해보기 시작했습니다. 알고 보니 이 분야에는 그 논문이 크게 의존하는 풍부한 역사가 있었고, 참조 사슬을 따라갈 필요가 있었습니다.
예를 들어, Christian Wimmer의 석사 학위 논문 (PDF, 2004)에는 시작부터 끝까지 전 과정을 아름답게 설명한 부분이 있습니다.
LINEAR_SCAN // 블록과 연산 순서 정하기(루프 탐지 포함) COMPUTE_BLOCK_ORDER NUMBER_OPERATIONS // 라이브 구간을 갖는 인터벌 생성 COMPUTE_LOCAL_LIVE_SETS COMPUTE_GLOBAL_LIVE_SETS BUILD_INTERVALS // 레지스터 할당 WALK_INTERVALS RESOLVE_DATA_FLOW // 가상 레지스터를 물리 레지스터로 대체 ASSIGN_REG_NUM // Intel FPU 스택에 대한 특수 처리 ALLOCATE_FPU_STACK한눈에 다 펼쳐져 있으니 아주 상쾌합니다. 빽빽한 연구 논문들과 비교하면 더더욱요.
저는 선형 스캔에 관한 논문이 한두 편만 있는 줄 알았습니다. 그래서 이 글은 결과적으로—제가 이해한 범위 내에서—선형 스캔의 간단한 역사/서베이 역할도 하게 될 것입니다. 그 시기에 가까운 곳에 계셨던 분이라면 기꺼이 지적과 교정을 부탁드립니다.
이 글 전체에서, Wimmer2010의 SSA 코드 조각을 예제로 사용할 것입니다. 원래 논문의 phi-SSA를 블록 인자 SSA로 약간 바꾸고, 논문에서 암시된 채로 빠진 부분을 채우기 위한 약간의 코드도 덧붙였습니다. 논문 속 코드는 화살표 사이의 부분이며, 나머지는 보충입니다:
label B1(R10, R11):
jmp B2($1, R11)
# vvvvvvvvvv #
label B2(R12, R13)
cmp R13, $1
branch lessThan B4()
label B3()
mul R12, R13 -> R14
sub R13, $1 -> R15
jump B2(R14, R15)
label B4()
# ^^^^^^^^^^ #
add R10, R12 -> R16
ret R16
가상 레지스터는 R로 시작하며, 화살표로 정의되거나 블록 파라미터로 정의됩니다.
익숙하지 않은 문법을 풀고 제어 흐름 그래프를 손으로 그리려면 시간이 조금 걸리므로, 같은 코드를 그래프 형태로도 제공했습니다. 블록 이름(과 블록 파라미터)은 회색 음영으로 표시됩니다.
하나의 진입 블록 B1이 있습니다(Wimmer2010에서는 암시됨). 이 블록의 유일한 역할은 CFG의 나머지 부분에서 사용할 R10과 R11을 정의하는 것입니다.
그 다음 B2와 B3 사이에 루프가 있고 암시적인 폴스루가 있습니다. 우리는 블록 재배치를 자유롭게 하고자 폴스루 대신 명시적인 점프로 이루어진 조건 분기를 생성합니다.
B4의 내용도 Wimmer2010에서 비어있는 부분을 메우고 변수 사용을 늘려주기 위한 채움입니다.
이 글의 목표는 이 CFG를 분석하고, 각 가상 레지스터에 물리적 위치(레지스터 또는 스택 슬롯)를 할당한 뒤, 적절하게 코드를 다시 쓰는 것입니다.
잠시 시간을 되감아 선형 스캔이 어떻게 시작되었는지 살펴봅시다.
선형 스캔 레지스터 할당(LSRA)은 꽤 오래되었습니다. 멋진 점은 레지스터 할당의 “실제 배정” 단계를 저수준 IR에 대해 한 번의 패스로 수행한다는 것입니다. (이게 무슨 의미인지는 곧 더 이야기하겠습니다.)
최초 등장은 Poletto, Engler, Kaashoek의 tcc: A System for Fast, Flexible, and High-level Dynamic Code Generation (PDF, 1997)입니다. 이 논문은 주로 ‘C(틱C)’라는 단계적(스테이징) C 변형을 다루며, 이를 위해 빠른 레지스터 할당기가 유용합니다. (이 글을 쓰기 전까지 저는 이 논문을 본 적이 없었습니다. 1999년 논문을 다시 읽다가 눈에 띄었습니다.)
이후 Traub, Holloway, Smith의 Quality and Speed in Linear-scan Register Allocation (PDF, 1998)이 나왔습니다. 1997년 알고리즘에 라이프타임 홀(lifetime holes), 빈패킹(binpacking) 등 일부 최적화를 더합니다.
그 다음에 제가 처음 읽었고, 사람들이 선형 스캔을 말할 때 주로 가리키는 논문인 Poletto, Sarkar의 Linear Scan Register Allocation (PDF, 1999)이 등장합니다. 이 논문은 특히 JIT 컴파일러를 동기로, 그래프 채색 기반 레지스터 할당에 대한 빠른 대안을 제시합니다. 돌이켜보면 앞선 두 논문의 재탕 같은 느낌도 있습니다.
선형 스캔(1997, 1999)은 가상 레지스터 대신 라이브 구간(live ranges)에 대해 동작합니다. 라이브 구간은 [start, end) 형태(끝은 배타)의 정수 쌍입니다. 정의 시점에서 시작해, 마지막 사용 시점에서 끝납니다. 이는 프로그램의 명령 순서가 이미 단일한 선형 시퀀스로 고정되어 있다는 가정을 의미합니다! 또한 각 명령이 그 순서에서의 위치를 나타내는 번호를 갖고 있어야 합니다.
이 요구 사항이 놀라울 수도 아닐 수도 있습니다. 저는 종종 블록에 순서가 없고 명령이 떠다니기도 하는 CFG 판타지랜드에서 살기 때문에 놀랐습니다. 하지만 이미 역후위순(reverse post order)의 기본 블록 세계에서 산다면 덜 놀랄 수 있겠죠.
비-SSA 세계에서는, 라이브 구간은 가상 레지스터 그 자체와는 다릅니다. 가상 레지스터의 각 “버전”의 수명을 나타내죠. 예를 들어 다음 코드 조각을 봅시다:
... -> a
add 1, a -> b
add 1, b -> c
add 1, c -> a
add 1, a -> d
a에는 정의가 두 번 있고 각각 다른 시간만큼 살아있습니다:
a b c a d
... -> a | <- 첫 번째 a
add 1, a -> b v |
add 1, b -> c v |
add 1, c -> a v | <- 두 번째 a
add 1, a -> d v |
실제로 이 구간들은 완전히 분리되어 있습니다. 할당기가 변수 단위로 생각하는 것은 말이 되지 않습니다. 두 a가 반드시 같은 물리 레지스터에 있어야 할 이유가 없거든요.
SSA 세계에서는 조금 다릅니다. 각 가상 레지스터는 정의가 정확히 한 번이기 때문에(정의상), 라이브 구간과 가상 레지스터가 1:1로 대응합니다. 우리는 지금 SSA에 관심이 있으므로, 이 글의 나머지 부분은 SSA에 집중합니다. 연구계는 SSA에서 직접 할당하는 편이 레지스터 할당기에 더 많은 정보를 준다고 보는 듯합니다3.
선형 스캔은 이미 이러한 라이브 구간을 알고 있는 시점에서 시작합니다—즉, 어떤 분석을 수행해 매핑을 만들어둔 상태죠.
이 글에서는 SSA 저수준 IR을 막 만든 시점으로 돌아가 아무 것도 하지 않은 상태에서 모든 분석을 처음부터 진행합니다.
이 분석의 일부를 라이브니스 분석이라고 합니다.
라이브니스 분석의 결과는 다음과 같은 매핑입니다:
BasicBlock ->
Set[Instruction]
즉, 각 기본 블록의 시작 시점에 “살아 있는”(이후 사용될) 가상 레지스터(SSA에서는 명령==vreg)를 알려줍니다. 이를 라이브-인(live-in) 집합이라고 부릅니다. 예를 들면:
B0:
... -> R12
... -> R13
jmp B1
B1:
mul R12, R13 -> R14
sub R13, 1 -> R15
jmp B2
B2:
add R14, R15 -> R16
ret R16
라이브니스는 뒤에서부터 계산합니다. 어떤 변수가 뒤에서부터 처음 사용되는 순간부터 정의까지를 라이브라고 봅니다.
이 경우, B2의 끝에서는 아무 것도 라이브가 아닙니다. 한 단계 뒤로 가서 ret을 보면 사용이 있으므로 R16이 라이브가 됩니다. 한 단계 더 뒤로 가면 R16의 정의가 보입니다—R16은 더 이상 라이브가 아니지만, 이제 R14와 R15의 사용이 보이므로 이들이 라이브가 됩니다. 결과적으로 R14와 R15가 B2의 라이브-인이 됩니다.
이 라이브-인 집합은 B1의 라이브-아웃(live-out)이 됩니다. B1이 B2의 선행자이기 때문이죠. 계속 B1에서 진행합니다. 선형으로 거꾸로 진행해도 됩니다. 실제로 직접 연습해보길 권합니다. 기본 블록마다(비어있을 수 있는) 레지스터의 집합 하나씩을 얻게 될 겁니다.
분기가 있으면 더 흥미로워집니다. 두 블록의 라이브-인이 공통 선행자에서 어떻게 합쳐질까요? C 블록의 두 후속 블록이 A와 B라면, 라이브-인은 합집합으로 합쳐집니다.
즉, R0가 B의 라이브-인이고 R1이 A의 라이브-인이라면, C의 라이브-아웃에는 R0와 R1이 모두 포함됩니다. 또한 C의 라이브-인일 수도 있지만, 그것은 전적으로 C의 내용에 달려 있습니다.
가상 레지스터의 총 개수는 음이 아닌 유한 수이므로, 이는 추상 해석의 좋은 격자 구조처럼 보입니다. 그렇습니다, 우리는 AI(abstract interpretation)를 하고 있습니다.
이번 라이브니스 분석에서는 다음을 수행합니다:
우리는 gen, kill, live-in 집합을 비트셋으로 저장하고, Ruby의 Integer 클래스가 제공하는 API를 활용합니다.
대부분의 추상 해석과 마찬가지로, 기본 블록을 어떤 순서로 순회하든 정합성에는 문제가 없지만 성능은 달라집니다. 이 경우 역순(포스트 오더, post_order)으로 순회하는 것이 정순(리버스 포스트 오더, reverse_post_order)보다 훨씬 빨리 수렴합니다:
class Function
def compute_initial_liveness_sets order
# Map of Block -> what variables it alone needs to be live-in
gen = Hash.new 0
# Map of Block -> what variables it alone defines
kill = Hash.new 0
order.each do |block|
block.instructions.reverse_each do |insn|
out = insn.out&.as_vreg
if out
kill[block] |= (1 << out.num)
end
insn.vreg_ins.each do |vreg|
gen[block] |= (1 << vreg.num)
end
end
block.parameters.each do |param|
kill[block] |= (1 << param.num)
end
end
[gen, kill]
end
def analyze_liveness
order = post_order
gen, kill = compute_initial_liveness_sets(order)
# Map from Block -> what variables are live-in
live_in = Hash.new 0
changed = true
while changed
changed = false
for block in order
# Union-ing all the successors' live-in sets gives us this block's
# live-out, which is a good starting point for computing the live-in
block_live = block.successors.map { |succ| live_in[succ] }.reduce(0, :|)
block_live |= gen[block]
block_live &= ~kill[block]
if live_in[block] != block_live
changed = true
live_in[block] = block_live
end
end
end
live_in
end
end
워크리스트를 사용해도 되고 더 빠르지만, 지금은 전체 블록을 반복적으로 훑는 것으로 충분합니다.
Wimmer2010은 CFG에 대한 일부 정보를 전제함으로써 라이브니스 분석을 완전히 생략합니다: 루프의 시작과 끝, 루프 블록들의 연속성 요구 등입니다. 그리고 루프 전에 정의되고 루프 내부 어느 지점에서든 사용되는 변수는 루프 전체에서 라이브라고 가정합니다. 이 정보를 바탕으로, 그들은 라이브니스 분석을 라이브 구간(인터벌) 구성 단계에 접어 넣습니다. 우리는 이걸 별도로 하겠습니다.
Wimmer 방식은 복잡하고 까다로워 보였습니다. 실제로 그런지 아닌지는 모르겠습니다. 그래서 저는 데이터플로우 기반 라이브니스 분석을 택했습니다. 이 부분이 느려서 문제가 된다면 그때 가서 루프 태깅 기법을 배워도 늦지 않겠지요.
이제 CFG에 대한 스케줄(순서)을 정합시다.
라이브 구간을 만들려면, 명령에 어떤 번호 체계가 있어야 합니다. 그래야 라이브 구간의 시작과 끝이 의미를 갖습니다. 특정 블록 순서를 고정(여기서는 역후위순)하고, 각 블록과 명령에 선형 시퀀스 상의 번호를 배정하는 함수를 작성할 수 있습니다. 그래프를 납작하게 펴는 느낌이라고 생각하면 됩니다:
class Function
def number_instructions!
@block_order = rpo
number = 16 # just so we match the Wimmer2010 paper
@block_order.each do |blk|
blk.number = number
number += 2
blk.instructions.each do |insn|
insn.number = number
number += 2
end
blk.to = number
end
end
end
흥미로운 점 몇 가지:
여분의 명령이 있긴 하지만, 결과는 Wimmer2010의 예시와 매우 유사해 보입니다.
16: label B1(R10, R11):
18: jmp B2($1, R11)
# vvvvvvvvvv #
20: label B2(R12, R13)
22: cmp R13, $1
24: branch lessThan B4() else B3()
26: label B3()
28: mul R12, R13 -> R14
30: sub R13, $1 -> R15
32: jump B2(R14, R15)
34: label B4()
# ^^^^^^^^^^ #
36: add R10, R12 -> R16
38: ret R16
이제부터는 블록 내 명령의 순서를 건드리지 않을 것이므로, 앞으로 해야 할 일은 @block_order 순서대로 블록을 순회하는 것뿐입니다.
마침내 라이브 구간을 계산할 모든 준비가 끝났습니다.
우리는 대체로 Wimmer2010의 알고리즘을 따라 라이브 구간을 계산할 것입니다. 다만 두 가지 주요 차이가 있습니다:
라이브 구간을 계산한다고 해놓고 왜 함수 이름이 build_intervals냐고요? 선형 스캔의 초기에(Traub1998!) 하나의 가상 레지스터에 하나의 구간만 두는 대신, 서로 분리된 여러 구간을 허용하는 방향으로 발전이 있었기 때문입니다. 이 여러 구간의 모음을 인터벌(interval)이라고 부르며, 분기 상황에서 레지스터를 더 잘 풀어주기 위해 존재합니다.
예를 들어 위 IR 조각에서 R12는 B2(블록 파라미터)에서 정의되고 B3에서 사용된 다음, B4의 어떤 시점까지 다시 사용되지 않습니다. (예제에서는 길이를 줄이려고 바로 다음 명령에서 쓰지만, 더 멀리 있다고 상상합시다.)
Wimmer2010은 28과 34 사이에 라이프타임 홀을 만들어, R12의 인터벌(i12)을 [[20, 28), [34, ...)]로 둡니다. 인터벌의 구멍은 반드시 필요한 것은 아니며, 더 나은 코드를 생성하기 위한 것입니다. 그래서 이 글에서는 단순하게 1 인터벌 == 1 구간으로 가정합니다. 나중에 추가 구간을 도입하고 싶을 수 있지만, 그러려면 이후 구현의 일부를 손봐야 합니다. 어디를 고쳐야 할지 글에서 표시해두겠습니다.
BUILDINTERVALS
for each block b in reverse order do
live = union of successor.liveIn for each successor of b
for each phi function phi of successors of b do
live.add(phi.inputOf(b))
for each opd in live do
intervals[opd].addRange(b.from, b.to)
for each operation op of b in reverse order do
for each output operand opd of op do
intervals[opd].setFrom(op.id)
live.remove(opd)
for each input operand opd of op do
intervals[opd].addRange(b.from, op.id)
live.add(opd)
for each phi function phi of b do
live.remove(phi.output)
if b is loop header then
loopEnd = last block of the loop starting at b
for each opd in live do
intervals[opd].addRange(b.from, loopEnd.to)
b.liveIn = live
어쨌든, 아래는 Wimmer2010의 BuildIntervals를 대부분 그대로 옮기고 주석을 더한 구현입니다:
class Function
def build_intervals live_in
intervals = Hash.new { |hash, key| hash[key] = Interval.new }
@block_order.reverse_each do |block|
# live = union of successor.liveIn for each successor of b
# this is the *live out* of the current block since we're going to be
# iterating backwards over instructions
live = block.successors.map { |succ| live_in[succ] }.reduce(0, :|)
# for each phi function phi of successors of b do
# live.add(phi.inputOf(b))
live |= block.out_vregs.map { |vreg| 1 << vreg.num }.reduce(0, :|)
each_bit(live) do |idx|
opd = vreg idx
intervals[opd].add_range(block.from, block.to)
end
block.instructions.reverse.each do |insn|
out = insn.out&.as_vreg
if out
# for each output operand opd of op do
# intervals[opd].setFrom(op.id)
intervals[out].set_from(insn.number)
end
# for each input operand opd of op do
# intervals[opd].addRange(b.from, op.id)
insn.vreg_ins.each do |opd|
intervals[opd].add_range(block.from, insn.number)
end
end
end
intervals.default_proc = nil
intervals.freeze
end
end
우리는 블록 파라미터를 쓰므로, 논문 속 phi.inputOf 같은 것이 따로 필요 없습니다. 그게 곧 블록 인자입니다.
또한 우리는 루프 라이브니스 트릭을 생략했기 때문에, 명령을 순회하면서 블록의 live 집합을 수정하지 않습니다.
라이브 구간을 만든다고 했으니, Interval 클래스는 구간 하나만 가집니다. Ruby의 내장 Range를 쓰지만, 여기서는 사실상 정수 쌍으로만 사용합니다.
class Interval
attr_reader :range
def add_range(from, to)
if to <= from
raise ArgumentError, "Invalid range: #{from} to #{to}"
end
if !@range
@range = Range.new(from, to)
return
end
@range = Range.new([@range.begin, from].min, [@range.end, to].max)
end
def set_from(from)
@range = if @range
if @range.end <= from
raise ArgumentError, "Invalid range: #{from} to #{@range.end}"
end
Range.new(from, @range.end)
else
# This happens when we don't have a use of the vreg
# If we don't have a use, the live range is very short
Range.new(from, from)
end
end
def ==(other)
other.is_a?(Interval) && @range == other.range
end
end
여기에는 몇 가지 암묵적 동작이 있습니다:
add_range는 기존 구간과 겹치도록 가장 작은 구간을 만듭니다.set_from은 시작을 줄일 수 있습니다.예를 들어, [1, 5)가 있을 때 add_range(7, 10)을 호출하면 결과는 [1, 10)입니다. 중간에 빈 구멍이 생기지 않습니다.
그리고 [1, 7)에 set_from(3)을 호출하면 결과는
[3,
7)
이 됩니다.
이 인터벌/구간 API가 무엇을 하고 무엇을 하지 않아야 하는지 바닥부터 가정과 기대를 정리하던 중, Aaron과 저는 보다 이른 논문에 add_range에 대한 실제 코드가 있었음을 알게 되었습니다. Mössenböck과 Pfeiffer의 Linear Scan Register Allocation in the Context of SSA Form and Register Constraints (PDF, 2002)입니다.
ADDRANGE(i: Instruction; b: Block; end: integer)
if b.first.n ≤ i.n ≤ b.last.n then range ← [i.n, end[ else range ← [b.first.n, end[
add range to interval[i.n] // merging adjacent ranges
불행히도 이 PDF의 다른 버전은 OCR이 엉망이라 참혹한 경우가 많았고, 위에 링크한 버전을 찾으려면 꽤 삽질해야 했습니다.
이제 드디어 실제 레지스터 배정을 생각할 수 있겠습니다. 90년대로 돌아가 봅시다.
우리는 1 인터벌 == 1 구간을 충실히 유지했으므로, Poletto1999의 선형 스캔 알고리즘(겉보기엔 1997과 동일)을 재사용할 수 있습니다.
PDF와 코드를 나란히 보시길 권합니다. 구조를 최대한 비슷하게 유지했습니다.
LinearScanRegisterAllocation
active ← {}
foreach live interval i, in order of increasing start point
ExpireOldIntervals(i)
if length(active) = R then
SpillAtInterval(i)
else
register[i] ← a register removed from pool of free registers
add i to active, sorted by increasing end point
ExpireOldIntervals(i)
foreach interval j in active, in order of increasing end point
if endpoint[j] ≥ startpoint[i] then
return
remove j from active
add register[j] to pool of free registers
SpillAtInterval(i)
spill ← last interval in active
if endpoint[spill] > endpoint[i] then
register[i] ← register[spill]
location[spill] ← new stack location
remove spill from active
add i to active, sorted by increasing end point
else
location[i] ← new stack location
요즘 많은 프로그래밍 언어와 달리, 여기의 {}는 (해시)맵이 아니라 집합을 의미합니다.
Ruby 코드에서 우리는 active를 배열로 나타냅니다:
class Function
def ye_olde_linear_scan intervals, num_registers
if num_registers <= 0
raise ArgumentError, "Number of registers must be positive"
end
free_registers = Set.new 0...num_registers
active = [] # Active intervals, sorted by increasing end point
assignment = {} # Map from Interval to PReg|StackSlot
num_stack_slots = 0
# Iterate through intervals in order of increasing start point
# TODO(max): Build a deque for intervals, pushing to the front, so we
# automatically get this in sorted order
sorted_intervals = intervals.sort_by { |_, interval| interval.range.begin }
sorted_intervals.each do |_vreg, interval|
# expire_old_intervals(interval)
active.select! do |active_interval|
if active_interval.range.end > interval.range.begin
true
else
operand = assignment.fetch(active_interval)
raise "Should be assigned a register" unless operand.is_a?(PReg)
free_registers.add(operand.name)
false
end
end
if active.length == num_registers
# spill_at_interval(interval)
# Pick an interval to spill. Picking the longest-lived active one is
# a heuristic from the original linear scan paper.
spill = active.last
# In either case, we need to allocate a slot on the stack.
slot = StackSlot.new(num_stack_slots)
num_stack_slots += 1
if spill.range.end > interval.range.end
# The last active interval ends further away than the current
# interval; spill the last active interval.
assignment[interval] = assignment[spill]
raise "Should be assigned a register" unless assignment[interval].is_a?(PReg)
assignment[spill] = slot
active.pop # We know spill is the last one
# Insert interval into already-sorted active
insert_idx = active.bsearch_index { |i| i.range.end >= interval.range.end } || active.length
active.insert(insert_idx, interval)
else
# The current interval ends further away than the last active
# interval; spill the current interval.
assignment[interval] = slot
end
else
reg = free_registers.min
free_registers.delete(reg)
assignment[interval] = PReg.new(reg)
# Insert interval into already-sorted active
insert_idx = active.bsearch_index { |i| i.range.end >= interval.range.end } || active.length
active.insert(insert_idx, interval)
end
end
[assignment, num_stack_slots]
end
end
이해하는 데 시간이 좀 걸렸습니다. 대체로 세 가지 상태가 있습니다:
우리는 여기에 라이프타임 홀(인터벌 분할)을 추가하면서 점진적으로 수정해나가고 싶습니다.
저는 꽤 늦게 가서야 Poletto1999 선형 스캔이 가상 레지스터 하나에 단 하나의 위치만 배정한다는 것을 이해했습니다. “항상”입니다. 가상 레지스터가 처음엔 레지스터에 있다가 나중에 스택으로 옮겨진다고요? 아니요—그건 인터벌 분할이고, 나중에 다루길 바랍니다—스필되면 시작부터 끝까지 스택에만 있습니다.
이 사실은 버그(사실 버그가 아니었음)를 추적하다가 우연히 알게 되었습니다. Wimmer, Mössenböck의 Optimized Interval Splitting in a Linear Scan Register Allocator (PDF, 2005)의 다음 문장 덕분입니다:
하지만, 이 방법은 라이프타임 홀을 다루지 못하고 인터벌을 분할하지도 못하므로, 인터벌은 전 수명 동안 레지스터를 할당받거나 아예 완전히 스필되거나 둘 중 하나만 된다.
또한,
특히, 스필된 인터벌을 레지스터를 필요로 하는 명령에서 사용할 때는, 인터벌을 임시 레지스터로 재적재해야 하므로 임시 레지스터 하나를 반드시 확보해야 한다.
또한,
게다가, 호출 및 고정 레지스터를 요구하는 명령의 레지스터 제약은 별도로 처리해야 한다.
훌륭합니다.
코드 조각을 다시 봅시다. 아래는 레지스터 할당 전, 가상 레지스터를 쓰는 모습입니다:
16: label B1(R10, R11):
18: jmp B2($1, R11)
# vvvvvvvvvv #
20: label B2(R12, R13)
22: cmp R13, $1
24: branch lessThan B4()
26: label B3()
28: mul R12, R13 -> R14
30: sub R13, $1 -> R15
32: jump B2(R14, R15)
34: label B4()
# ^^^^^^^^^^ #
36: add R10, R12 -> R16
38: ret R16
물리 레지스터 수를 점차 줄여가며 레지스터 할당을 돌려보면 다음과 같은 배정을 얻습니다:
{R10: P0, R11: P1, R12: P1, R13: P2, R14: P3, R15: P2, R16: P0}{R10: Stack[0], R11: P1, R12: P1, R13: P2, R14: P0, R15: P2, R16: P0}{R10: Stack[0], R11: P1, R12: Stack[1], R13: P0, R14: P1, R15: P0, R16: P0}{R10: Stack[0], R11: P0, R12: Stack[1], R13: P0, R14: Stack[2], R15: P0, R16: P0}추가로 주목할 점:
심지어 “탐욕적으로” 레지스터를 배정하지 않는 것까지 고려할 수 있습니다. 그게 어떤 모습일까요? 저는 아직 모르겠습니다.
이는 약간 더 많은 정보와 시간을 요구하지만, 기본 휴리스틱보다 훨씬 더 좋은 코드를 생성한다고 합니다.
이곳에는 2개 레지스터로 선형 스캔을 실행해 만든 “슬라이드쇼” 예시가 있습니다. 방향키로 시간의 앞뒤로 이동할 수 있습니다4.
현재 우리는 레지스터 “할당”을 갖고 있습니다: 인터벌에서 물리 위치로의 해시 매핑을요. 좋습니다. 하지만 여전히 SSA 형태입니다: 하드웨어는 블록 인자를 가진 레이블 구역을 지원하지 않죠. SSA를 벗어나 현실 세계로 가는 코드를 작성해야 합니다.
여기서는 수정된 Wimmer2010을 훌륭한 출발점으로 삼을 수 있습니다. 그들은 우리가 지금 당장 필요로 하는 것(인터벌 분할)보다 더 많은 것을 다루는데, 우리는 단순화하겠습니다.
RESOLVE
for each control flow edge from predecessor to successor do
for each interval it live at begin of successor do
if it starts at begin of successor then
phi = phi function defining it
opd = phi.inputOf(predecessor)
if opd is a constant then
moveFrom = opd
else
moveFrom = location of intervals[opd] at end of predecessor
else
moveFrom = location of it at end of predecessor
moveTo = location of it at begin of successor
if moveFrom ≠ moveTo then
mapping.add(moveFrom, moveTo)
mapping.orderAndInsertMoves()
우리는 인터벌을 분할하지 않으므로, 블록 시작 시 라이브한 모든 인터벌은 다음 둘 중 하나입니다:
이 이유로 우리는 두 번째 경우만 처리해 SSA를 해소합니다. 라이프타임 홀(인터벌 분할)을 추가한다면 Wimmer의 전체 SSA 해소를 다시 적용해야 합니다.
즉, 모든 블록에서 모든 출구 엣지를 순회하고, 각 엣지에 병렬 이동을 삽입합니다.
class Function
def resolve_ssa intervals, assignments
# ...
@block_order.each do |predecessor|
outgoing_edges = predecessor.edges
num_successors = outgoing_edges.length
outgoing_edges.each do |edge|
mapping = []
successor = edge.block
edge.args.zip(successor.parameters).each do |moveFrom, moveTo|
if moveFrom != moveTo
mapping << [moveFrom, moveTo]
end
end
# predecessor.order_and_insert_moves(mapping)
# TODO: order_and_insert_moves
end
end
# Remove all block parameters and arguments; we have resolved SSA
@block_order.each do |block|
block.parameters.clear
block.edges.each do |edge|
edge.args.clear
end
end
end
end
이미 Wimmer2010의 RESOLVE와 꽤 비슷합니다. 문제는 Wimmer2010이 orderAndInsertMoves를 “이건 문헌에 이미 있음”이라며 손사래친다는 겁니다.
분명히 해야 할 점은, 이 하위 루틴이 문헌에서 오랫동안 많은 버그의 근원이 되어왔다는 사실입니다. 최근에서야 몇몇 분들이 와서(정당성이 입증된) 해결책을 제시했습니다:
이 덕분에 우리는 어떤 버그가 언제 어떻게 발생하는지 이해하려고 깊은 토끼굴로 들어갔습니다. Leroy와 Boissinot 알고리즘을 모두 구현했고, Boissinot2009, Boissinot2010, 그리고 해당 알고리즘을 따르는 SSA 책의 구현 사이에서 차이를 발견했습니다. Paul Sokolovsky의 버그 수정 구현도 찾았고, 같은 저장소에 대해 Dmitry Stogov의 머지되지 않은 PR도 발견했습니다.
Benoit Boissinot의 논문을 다시 살펴보다가 질문 메일을 보냈는데, 답장을 받았습니다! 심지어 수정한 알고리즘 버전을 Rust로 테스트와 퍼징까지 곁들여 공개해주셨습니다.
결론적으로, 이 문제는 여전히 사람들을 괴롭히며, 페이지 제한이 있음을 이해하지만 병렬 이동을 손사래치는 건 아쉽습니다.
우리는 최종적으로 Sokolovsky 저장소의 모든 테스트와 Boissinot 논문의 예시를 통과하는 구현을 얻었습니다(이메일에서 논의한 대로, 논문 속 예시 해법은 틀렸습니다5).
# copies contains an array of [src, dst] arrays
def sequentialize copies
ready = [] # Contains only destination regs ("available")
to_do = [] # Contains only destination regs
pred = {} # Map of destination reg -> what reg is written to it (its source)
loc = {} # Map of reg -> the current location where the initial value of reg is available ("resource")
result = []
emit_copy = -> (src, dst) {
# We add an arrow here just for clarity in reading this algorithm because
# different people do [src, dst] and [dst, src] depending on if they prefer
# Intel or AT&T
result << [src, "->", dst]
}
# In Ruby, loc[x] is nil if x not in loc, so this loop could be omitted
copies.each do |(src, dst)|
loc[dst] = nil
end
copies.each do |(src, dst)|
loc[src] = src
if pred.key? dst # Alternatively, to_do.include? dst
raise "Conflicting assignments to destination #{dst}, latest: #{[dst, src]}"
end
pred[dst] = src
to_do << dst
end
copies.each do |(src, dst)|
if !loc[dst]
# All destinations that are not also sources can be written to immediately (tree leaves)
ready << dst
end
end
while !to_do.empty?
while b = ready.pop
a = loc[pred[b]] # a in the paper
emit_copy.(a, b)
# pred[b] is now living at b
loc[pred[b]] = b
if to_do.include?(a)
to_do.delete a
end
if pred[b] == a && pred.include?(a)
ready << a
end
end
if to_do.empty?
break
end
dst = to_do.pop
if dst != loc[pred[dst]]
emit_copy.(dst, "tmp")
loc[dst] = "tmp"
ready << dst
end
end
result
end
Leroy의 알고리즘은 더 짧고 거의 모든 테스트를 통과합니다—단 하나의 테스트 케이스에서 Boissinot보다 임시 변수를 하나 더 씁니다. 왜 그런지는 깊게 보지 않았습니다.
def move_one i, src, dst, status, result
return if src[i] == dst[i]
status[i] = :being_moved
for j in 0...(src.length) do
if src[j] == dst[i]
case status[j]
when :to_move
move_one j, src, dst, status, result
when :being_moved
result << [src[j], "->", "tmp"]
src[j] = "tmp"
end
end
end
result << [src[i], "->", dst[i]]
status[i] = :moved
end
def leroy_sequentialize copies
src = copies.map { it[0] }
dst = copies.map { it[1] }
status = [:to_move] * src.length
result = []
status.each_with_index do |item, i|
if item == :to_move
move_one i, src, dst, status, result
end
end
result
end
어떤 알고리즘을 선택하든, 이제 어떤 레지스터들을 다른 레지스터들로 병렬 이동하는 방법을 갖게 되었습니다. “스왑 문제”를 피할 수 있습니다.
class Function
def resolve_ssa intervals, assignments
# ...
# predecessor.order_and_insert_moves(mapping)
sequence = sequentialize(mapping).map do |(src, _, dst)|
Insn.new(:mov, dst, [src])
end
# TODO: insert the moves!
# ...
end
end
좋습니다. 얽힌 그래프에서 순서 있는 명령 리스트를 생성할 수 있습니다. 그런데 어디에 넣을까요? “잃어버린 복사” 문제는 어떻게 할까요?
결국 우리는 크리티컬 엣지 분할을 처리해야 합니다. 블록 A -> B 사이의 엣지에 이동을 삽입한다는 것이 주변 CFG에 따라 무엇을 의미하는지 몇 가지 경우를 생각해 봅시다.
A -> BA -> B 그리고 A -> CA -> B 그리고 D -> BA -> B 그리고 A -> C 그리고 D -> B이 네 가지(사실상 세 가지) 경우를 만나게 됩니다.
경우 1에서는 A와 B 두 블록만 이웃하므로, 어느 쪽에 넣든 상관없습니다. A의 끝이나 B의 시작 모두 괜찮습니다.
경우 2에서 A에 두 개의 후속 블록이 있다면, 이동은 B의 시작에 삽입해야 합니다. 그래야 A -> C 엣지를 망치지 않습니다.
경우 3에서 B에 두 개의 선행 블록이 있다면, 이동은 A의 끝에 삽입해야 합니다. 그래야 D -> B 엣지를 망치지 않습니다.
경우 4가 가장 복잡합니다. 그래프 어딘가에 그대로 삽입할 수 있는 자리 자체가 없습니다. A에 넣으면 A -> C를 망치고, B에 넣으면 D -> B를 망칩니다. C나 D에 넣는 건 의미가 없습니다. 어떻게 해야 할까요?
경우 4는 크리티컬 엣지라고 합니다. 그리고 분할해야 합니다.
A -> B 엣지 중간에 새 블록 E를 삽입하고 거기에 이동을 넣을 수 있습니다! 그러면 다른 블록에 영향을 주지 않고 엣지 상에서 이동을 수행할 수 있습니다. 멋집니다.
Ruby 코드는 다음과 같습니다:
class Function
def resolve_ssa intervals, assignments
num_predecessors = Hash.new 0
@block_order.each do |block|
block.edges.each do |edge|
num_predecessors[edge.block] += 1
end
end
# ...
# predecessor.order_and_insert_moves(mapping)
sequence = ...
# If we don't have any moves to insert, we don't have any block to
# insert
next if sequence.empty?
if num_predecessors[successor] > 1 && num_successors > 1
# Make a new interstitial block
b = new_block
b.insert_moves_at_start sequence
b.instructions << Insn.new(:jump, nil, [Edge.new(successor, [])])
edge.block = b
elsif num_successors > 1
# Insert into the beginning of the block
successor.insert_moves_at_start sequence
else
# Insert into the end of the block... before the terminator
predecessor.insert_moves_at_end sequence
end
# ...
end
end
새 블록을 추가하면 캐시된 @block_order가 무효화되므로 다시 계산해야 합니다.
번호 매기기 전에 미리 크리티컬 엣지를 분할하는 방법도 있습니다. 그러면
resolve_ssa에 도착했을 때 빈 블록으로 향하는 분기를 정리하면 됩니다!
(Nick의 크리티컬 엣지 분할 글도 참고하세요. 여기에는 Faddegon의 학위 논문 링크도 있습니다. 저도 최소한 훑어보려 합니다.)
이제 끝입니다. 가상 레지스터를 갖는 SSA에서 물리 위치로 왔습니다. 이제 LIR 명령을 아주 비슷하게 생긴 기계 명령으로 바꾸기만 하면 되겠죠?
그렇게 간단하진 않습니다…
원조 선형 스캔 논문에는 호출이나 다른 레지스터 제약에 대한 언급이 없다는 것을 눈치채셨을지도 모릅니다. 저도 함수 호출을 만들고 싶어질 때까지는 깊게 생각하지 않았습니다. 이후 논문 저자들은 분명 이 점에 주목했죠. Wimmer2005는 Poletto1999에 대해 다음과 같이 씁니다:
스필된 인터벌을 레지스터를 요구하는 명령에서 사용할 때는, 인터벌을 임시 레지스터로 재적재해야 한다. 또한, 호출과 고정 레지스터를 요구하는 명령의 레지스터 제약은 별도로 처리해야 한다.
재미있군요. 우선 호출과 인자를 별도로 처리하는 방식으로 시작해 보겠습니다. 좋은 코드라고 하긴 어렵겠지만, 이후 레지스터 제약을 더 자연스럽게 다루는 논문들의 방식을 구현할 것입니다.
레지스터 할당 이후이되 SSA 해소 이전에 handle_caller_saved_regs라는 새 함수를 호출하겠습니다. 할당 이후에 하는 이유는 각 가상 레지스터의 위치를 알고 있기 위함이고, 해소 이전에 하는 이유는 아직 가상 레지스터 피연산자를 들여다볼 수 있어야 하기 때문입니다.
목표는 다음과 같습니다:
call 명령 주변에 특수한 push/pop을 삽입해, call 이후에도 사용되는 가상 레지스터를 보존합니다. 다만 이미 스택에 있는 값은 보존할 필요가 없고, 물리 레지스터에 들어있는 것만 보존합니다.call 명령의 출력 위치로 옮기도록 합니다.또한 이제 인자는 특정 레지스터로 직접 배치하므로 call의 피연산자 목록에서 인자를 제거합니다.
class Function
def handle_caller_saved_regs intervals, assignments, return_reg, param_regs
@block_order.each do |block|
x = block.instructions.flat_map do |insn|
if insn.name == :call
survivors = intervals.select { |_vreg, interval|
interval.survives?(insn.number)
}.map(&:first).select { |vreg|
assignments[intervals[vreg]].is_a?(PReg)
}
mov_input = insn.out
insn.out = return_reg
ins = insn.ins.drop(1)
raise if ins.length > param_regs.length
insn.ins.replace(insn.ins.first(1))
mapping = ins.zip(param_regs).to_h
sequence = sequentialize(mapping).map do |(src, _, dst)|
Insn.new(:mov, dst, [src])
end
survivors.map { |s| Insn.new(:push, nil, [s]) } +
sequence +
[insn, Insn.new(:mov, mov_input, [return_reg])] +
survivors.map { |s| Insn.new(:pop, nil, [s]) }.reverse
else
insn
end
end
block.instructions.replace(x)
end
end
end
(안타깝게도, 6번째 인자 이후 스택에 올려야 하는 ABI 같은 더 재미없는 부분은 비켜갑니다. 또한 ABI의 크기 제약도 완전히 무시합니다.)
눈치채셨겠지만, 우리는 아직 컴파일 중인 함수의 “들어오는 매개변수”에 대해서는 특별히 한 게 없습니다! 이것 또한 처리해야 합니다. 다행히, resolve_ssa의 마지막에서 또 하나의(와우!) 병렬 이동으로 처리할 수 있습니다.
class Function
def resolve_ssa intervals, assignments
# ...
# We're typically going to have more param regs than block parameters
# When we zip the param regs with block params, we'll end up with param
# regs mapping to nil. We filter those away by selecting for tuples
# that have a truthy second value
# [[x, y], [z, nil]].select(&:last) (reject the second tuple)
mapping = param_regs.zip(entry_block.parameters).select(&:last).to_h
sequence = sequentialize(mapping).map do |(src, _, dst)|
Insn.new(:mov, dst, [src])
end
entry_block.insert_moves_at_start(sequence)
end
end
다시 말하지만, 이후의 논문들은 이와 같은 사항을 더 우아하게 처리하고, 생성 코드의 질도 더 좋습니다.
하지만 이거 정말 멋집니다! 여기까지 같이 오셨다면, 우리는 1997년 수준까지 성공적으로 도달했습니다. 그 과정에서 SSA에 맞게 1997년의 연구를 각색했고, 길목마다 여러 심각한 버그 부류를 피해왔습니다.
우리는 방금 매우 복잡한 기계를 만들었습니다. 원조 선형 스캔만 가지고도 기계 장치가 많습니다. 모든 모양과 크기의 프로그램을 점검하는 테스트를 작성할 수는 있지만, 현장에서 나타나는 모든 에지 케이스를 예견하는 것은 매우 어렵습니다.
원래 알고리즘이 정당성이 입증되었다 하더라도, 구현은 미묘한 버그를 가질 수 있습니다. (예를 들어) 불변식이 살짝 다르거나, 필사 오류 때문일 수 있죠.
우리는 각종 증명 도구를 갖고 있습니다. 하나의 그래프에 대한 속성을 검증하는 추상 해석기를 작성할 수 있지만, 그래프 집합으로 확장하는 것은 매우 어렵습니다(불가능할 수도).
하지만 아마 그 정도면 충분할지도 모릅니다. 제가 좋아하는 블로그 글 중 하나에서 Chris Fallin은 추상 해석 기반 레지스터 할당 검증기를 씁니다. 이는 한 번에 하나의 구체적인 LIR 함수만 검증합니다. 디버그 빌드에서 상시 켜 두어도 될 만큼 빠릅니다. 이는 테스트, CI, 때로는 프로덕션 클러스터에서라도, 검증기를 통과한 모든 레지스터 할당이 특정 불변식을 만족한다는 강력한 신호를 자주 얻을 수 있음을 의미합니다.
더 나아가, 우리는 실제 코드에만 한정되지 않습니다. 퍼징이 발전하면서 레지스터 할당기를 망가뜨리려는 상시 퍼저를 상상할 수 있습니다. 검증기는 이 거대한 탐색 공간을 뒤지는 과정에서 나오는 버그를 잡아낼 수 있습니다.
Chris의 글을 본 뒤로 얼마 지나지 않아, V8에 동일한 것이 있다는 것을 알게 되었습니다!
이런 요소들이 정말 멋지다고 생각합니다. 병렬 이동에 대해서도 비슷한 일을 하는 Boissinot의 Rust 코드를 다시 언급합니다.
제어 흐름이 없는 트레이스에서는 역방향으로 선형 스캔을 할당하는 것도 가능합니다. 예를 들어 The Solid-State Register Allocator, LuaJIT 레지스터 할당기, Reverse Linear Scan Allocation is probably a good idea 등을 보세요. 이렇게 하면 라이브니스와 인터벌 계산을 피할 수도 있습니다. 다만 제어 흐름이 있는 프로그램에서도 잘 되는지는 확신이 없습니다.
SSA에서 동작하는 레지스터 할당기를 만들었습니다. 다음에는 라이프타임 홀, 인터벌 분할, 레지스터 힌트 같은 기능을 추가해보려 합니다.
전체 Ruby 코드는 아직 공개되지 않았지만 Apache 2 라이선스로 공개되었습니다.
업데이트: 라이프타임 홀 글을 참고하세요.
이 글에 피드백을 주신 Waleed Khan, Iain Ireland께 감사드립니다.
레지스터만의 문제가 아닙니다. 2016년, Facebook 엔지니어 Dave는 선형 스캔 레지스터 할당으로 회의실 예약을 전설적으로 처리했습니다↩
올해 초 소셜 미디어에 이렇게 썼습니다. “모든 AOT 컴파일러는 서로 닮았지만; 각 JIT 컴파일러는 제각각 엉망이다.”
JavaScript:
Java:
Python:
Ruby:
PHP:
Lua:
우리의 할당기는 SSA 형태에 의존하는데, 이는 데이터플로우 분석을 단순화하고 라이브 인터벌을 짧게 만드는 경향이 있다.
Hack, Grund, Goos의 Register allocation for programs in SSA-form (PDF, 2006)에서는 SSA 프로그램의 간섭 그래프가 코드럴(chordal)하여 2차 시간에 최적으로 채색될 수 있다고 합니다.
Pereira, Palsberg의 SSA Elimination after Register Allocation (PDF, 2008)에서는 이렇게 말합니다:
SSA 기반 레지스터 할당의 주요 장점 중 하나는 스필링과 레지스터 배정을 단계적으로 분리할 수 있다는 점이다.
Cliff Click (개인적 소통, 2025)은 이렇게 말합니다:
더 쉽다. 이미 가지고 있는데, 왜 버리나 […] 스필링은 항상 use/def와 def/use 엣지를 사용한다.
Rasmus Andersson의 그래프 채색 시각화에서 영감을 받았습니다↩
논문 속 예시는 다음 병렬 복사를 순차화하는 것입니다:
논문의 해법은 다음과 같습니다:
하지만 이는 잘못되었다고 생각합니다. 수작업으로 풀어본 우리의 해법은 다음과 같습니다:
이는 코드에서도 동일한 결과가 나옵니다↩