レジスタ割り当ては、高レベルのコンパイル中に使用される無制限の仮想レジスタを、x86汎用レジスタ（GPR）や浮動小数点レジスタ（FPR）など、ハードウェアによって提供される有限の物理ストレージリソースにマッピングする重要なプロセスです。これを効率的に行うために、コンパイラはまず「生存期間解析（liveliness analysis）」を実行し、値が正確にいつ「生存（alive）」しており、いつ安全に破棄または上書きできるかを判断する必要があります。
生存期間解析の仕組み
この解析は、コードの基本ブロックを走査し、仮想レジスタが定義または使用されるすべてのポイントを観察することで機能します。提供された実装では、コンパイラはブロックを走査し、まずターミネータを訪問してすべての最終的な使用を確認し、次に命令を逆順に訪問して定義と中間的な使用を捉えます。
各仮想レジスタについて、システムは(lo, hi)の位置のタプルを保持します。「lo」位置は使用のたびに更新され、「hi」位置は最後の使用ポイントで一度だけ設定されます。これにより、プログラム内のすべての値に対して明確な「生存期間」のウィンドウが作成されます。
この表は生存期間セットを視覚的に表しており、コンパイラが値のアクティブ範囲の開始点と終了点をどのように追跡しているかを示しています。
「レジスタ割り当てとは、無制限の仮想レジスタを、ハードウェアが持つ限られたストレージリソース、具体的にはGPR（汎用レジスタ）、FPR（浮動小数点レジスタ）、およびスタックに割り当てることである」
— An ode to livelyness analysis; SSA to registers
SSAとレジスタマッピングの統合
このプロジェクトではStatic Single Assignment（SSA）形式を使用しており、すべての仮想レジスタ（%vNと表記）が正確に一度だけ割り当てられるため、解析が簡素化されます。phiノードを使用する一部のIRとは異なり、この特定の実装では、ブロックパラメータとターミネータを使用してブロック間データフローを促進します。
生存期間セット（livelinetset）を計算することで、コンパイラは事前割り当てパスを実行できます。これにより、バックエンドは、値がハードウェアレジスタに滞在できるか、あるいはスタックスロットに配置する必要があるかを決定でき、ローワーリングプロセス中の値のスピルと復元の複雑さを効果的に抽象化できます。
実装とトレードオフ
開発者は、Rustのマクロを使用して加算、乗算、比較などの異なる命令タイプを処理しながら、バイナリ演算をバイトコードにローワーリングする様子を実演しています。このプロセスにより、複雑な操作であっても、事前に計算された生存期間セットに基づいて、正しいレジスタまたはスタック位置にマッピングされることが保証されます。
このコードスニペットは、命令を処理しレジスタマッピングを管理するために使用されるロジックの具体的な例を提供します。
このシステムにおける主なトレードオフは「スピル」の管理です。アクティブな仮想レジスタの数が利用可能なハードウェアレジスタを超えた場合、コンパイラは値をスタックに移動させなければなりません。生存期間解析は、プログラムのロジックを壊すことなく移動しても安全な値がどれであるかをコンパイラに正確に伝えるため、この管理を可能にします。