自作言語のレジスタ割り当てを支える、ライブネス解析の美しさ
An ode to livelyness analysis; SSA to registers
自作言語purple-gardenの作者が、SSA形式のIRからx86 JITやバイトコードVM向けにレジスタを割り当てる前段となるライブネス解析を解説する。各仮想レジスタの生存区間を(lo, hi)のタプルで捉え、ブロックを逆順に走査して定義と使用を観測するだけの簡潔な実装を、実際のRustコードとともに示す。phiノードではなくブロックパラメータと終端命令でデータフローを表現する独自IRの設計も興味深い。
レジスタ割り当てとは、無制限の仮想レジスタを、ハードウェアが持つ限られた記憶資源、具体的にはgpr（汎用レジスタ）、fpr（浮動小数点レジスタ）、そしてスタックに割り当てることだ。