레지스터 할당의 첫걸음, 라이브니스 분석을 파헤치다
An ode to livelyness analysis; SSA to registers
프로그래밍 언어 purple-garden의 바이트코드 VM과 x86 JIT 컴파일러를 위한 레지스터 할당 작업 중, SSA IR에서 각 가상 레지스터의 생존 범위를 계산하는 라이브니스 분석을 소개한다. 블록 파라미터와 터미네이터를 사용하는 독자적 IR 구조를 설명하고, 블록을 역순으로 순회하며 정의와 사용을 관찰해 (lo, hi) 구간을 구하는 간단한 Rust 구현을 제시한다. 이 정보를 바탕으로 제한된 하드웨어 레지스터와 스택 슬롯에 값을 배정하는 사전 할당 단계로 이어진다.
레지스터 할당은 무한한 가상 레지스터를 하드웨어가 가진 제한된 저장 자원, 구체적으로는 범용 레지스터(gprs), 부동소수점 레지스터(fprs), 그리고 스택에 배정하는 일이다.