Rat's Register Allocator

rat's register allocator 2026年10月7日 ratは、私の小さなコンパイラバックエンド（半機能的なC99フロントエンド付き）です。そのx86-64コードジェネレータは、中間表現（IR）をx86-64命令に変換します。これらは無制限の数の仮想レジスタ（vreg）を使用します。レジスタアロケータは、各vregを物理レジスタにマッピングします。汎用レジスタ（12個使用可能）またはxmmレジスタ（Linuxでは14個）です。レジスタが空いていない場合、vregをスタック・スロットにマッピングします。 長らくratは線形スキャンアロケータを使用していましたが、これはプログラム順にライブレンジを訪問します。それは機能しましたが、1つの修正が1つずつ増え、1392行になりました。そこで、どの部分が役立ったかを測定し、残りを捨てて、584行で優先度ビンパッキングアロケータを書き直しました。これはライブレンジを重要度順に訪問し、各レンジを最初に適合するレジスタに入れます。これはLLVMのグリーディアルロケータと同じファミリーですが、難しい部分のほとんどを取り除いており、より良いコードを生成します。 値は、それが書き込まれた場所から最後に読み取られた場所までライブです。2つの値は、同時にライブにならない場合にのみレジスタを共有できます。ある時点でライブな値が多すぎると、一部はメモリにスピルされます。スピルはストアとロードのコストがかかります。最適な割り当てを見つけることはNP困難²であるため、すべての実用的なアロケータはヒューリスティックを使用します。 呼び出し規約は2つのルールを追加します。呼び出しは、呼び出し元保存レジスタ（Linuxではrax rcx rdx rsi rdi r8-r11およびすべてのxmmレジスタ）を上書きする可能性があります。関数は、戻る前に呼び出し先保存レジスタ（rbx rbp r12-r15）を復元する必要があります。 例として、この関数は呼び出しをまたいでyをライブに保ちます。 long g(long); long h(long x, long y) { long t = g(x); return t + y; } 割り当て前、rdi、rsi、raxは呼び出し規約によって固定され、v1-v4はvregです。 0 v1 = copy rdi ; x 1 v2 = copy rsi ; y 2 rdi = copy v1 ; gの引数 3 call g ; 呼び出し元保存レジスタを破壊 4 v3 = copy rax ; t 5 v4 = copy v3 6 v4 = add v4, v2 7 rax = copy v4 8 ret x86のaddは最初のオペランド（2オペランド命令）を上書きするため、命令5はまずコピーします。 割り当て後、-O1で： push rbp mov rbp, rsp sub rsp, 0x8 push rbx ; rbxは呼び出し先保存レジスタ：保存する mov rbx, rsi ; y call g ; xは既にrdiにある add rax, rbx ; tはraxに残る pop rbx leave ret 6つのコピーのうち5つがなくなり、yは呼び出し先保存レジスタに移動しました。アロケータのコードには、「呼び出しをまたぐ値を呼び出し先保存レジスタに入れる」という指示はありません。これは設計から自然に発生するもので、私の好きな部分です。 5つのステップ アロケータは関数ごとに5つのステップを実行します。 ライブレンジ：命令に番号を付け、各vregがどこでライブであるかを見つけます。 固定レジスタ：コードが物理レジスタを直接使用する場所をマークします。 合体（Coalescing）：コピーで接続されたvregを1つのグループ（バンドル³）に結合し、コピーをなくせるようにします。 レジスタの選択：各バンドルにレジスタを割り当てます。最も重要度の高いものから順に。 スピル：レジスタがないバンドルにスタック・スロットを割り当て、コードを書き直します。 各バンドルは、その全ライフタイムにわたってレジスタまたはスタック・スロットを保持します。 アロケータは決して行わないこと： バンドルからレジスタを取り戻さない（エビクションなし） レンジをレジスタとメモリの間で分割しない ステップを2回実行しない これらの部分は、実際のアロケータを大きくします。私の測定によると、ratはそれらをあまり逃していません。 ライブレンジ スロット 命令iは2つのスロットを取得します。オペランドを2iで読み取り、結果を2i+1で書き込みます。ライブレンジは、[開始、終了]スロットセグメントのソートされたリストです。ソースの終了位置は命令に依存します。 コピー：ソースは読み取りスロットで終了し、宛先は書き込みスロットで開始します。命令2（rdi = copy v1）では、v1はスロット4で終了し、rdiはスロット5で開始します。これらは重複しないため、レジスタを共有でき、コピーはノーオペレーションになります。 その他の命令：ソースは書き込みスロットまでライブであり続けるため、結果は別のオペランドを上書きすることはありません。v2は命令1で書き込まれ、命令6のaddで最後に読み取られるため、[3, 13]でライブです。 ライブアウトセット ratは、各ブロックのライブアウトであるvregを見つけます。後続のブロックはそれらをまだ読み取ることができます。多くのコンパイラは、ブロックごとに1つのビットセットと固定点ループでこれを行います。ratは代わりに1つのvregずつ処理します。 vregは、それを書き込む前に読み取る各ブロックにライブインします。そのような各ブロックから、ワークリストが先行ブロックを遡り、各ブロックでvregをライブアウトとしてマークします。ウォークはvregを定義するブロックで停止します。コストは、各vregがライブであるブロック数に比例し、ブロック数×vreg数ではありません。⁴ セグメントと重み 次にratは、ライブアウトセットから各ブロックを逆方向にウォークし、セグメントを作成します。同じウォークで、vregあたりの重み（スピルのコスト）を合計します。各定義と各使用は、ループの深さ（最大11）にdを掛けた値に3dを加算します。 defまたはuse 直線コードでは1 ループでは3 二重ネストループでは9 穴（Holes） ライブレンジには穴（vregがデッドなギャップ）がある場合があります。ブロックはコード順に番号付けされるため、ブロックをスキップするレンジにはそこに穴があります。 long f(long* a, long n) { for(long i = 0; i < n; ++i) if(a[i] < 0) a[i] = 0; return n * 3; } ループの終了ブロックはループブロックの間にあります。 mov eax, 0x0 ; offset 8*i, raxはループ内 cmp rdx, rdi jl loop exit: lea rax, [rdi+rdi*2] ; ホール内のn*3（rax） ret loop: mov rcx, r8 add rcx, rax ... add rax, 0x8 cmp rdx, rdi jl loop jmp exit raxのオフセットは終了ブロックではデッドなので、n*3（1回のlea命令）は、戻り値レジスタでもあるraxを使用できます。ブロック順序からのフリーな勝利です。 固定レジスタ ratはレジスタを1から40まで番号付けするため、1つのU64でセットを保持できます。各スロットは1つのマスク（busy[slot]）を取得します。ビットがセットされている場合、そのレジスタはそのスロットでビジーであることを意味します。同じ逆方向ウォークが、コードが直接使用する物理レジスタをマークします。 レジスタの使用 ビジー 引数 コピーがそれを読み取るまで、引数レジスタ 呼び出し引数 それを設定するコピーから呼び出しまでの引数レジスタ 呼び出し 呼び出しからそれを読み取るコピーまでのすべての呼び出し元保存レジスタ 除算 rax rcx rdx rax rcxを読み取り、rax rdxを書き込む hのマスクとレンジ： instr 0 1 2 3 4 5 6 7 8 slot rw rw rw rw rw rw rw rw rw rdi #. .. .#### .. .. .. .. .. rsi ####. .. ## .. .. .. .. .. rax .. .. .. ####. .. .. .#### others .. .. .. ## .. .. .. .. .. v1 x .======. .. .. .. .. .. .. v2 y .. .================ .. .. v3+v4 t .. .. .. .. .=========. .. rは読み取り、wは書き込みスロットです。#はビジー、=はライブレンジ、.はフリーです。バーは命令間のギャップを横切って続きます。「others」は、他のすべての呼び出し元保存レジスタです。バンドルがレジスタを取得すると、ratはそのレジスタのビットをそのライブレンジのすべてのスロットに設定します。その後、vregと固定レジスタは同じマスク内のビットになります。64スロットの各グループには、64個のマスクのORであるサマリーマスクもあり、長いレンジは一度に64スロットをスキップできます。 合体（Coalescing） 同じクラスの2つのvreg間のコピーは、合体の候補です。これらのコピーは、以下から生じます。 2オペランド命令 phiノード：異なるブロックから結合ポイントに値が来る場合 2つのライブレンジが重複しない場合、vregは1つのバンドルになります。それは、マージされたセグメントと合計された重みを持つことになります。ratは、バンドル内のコピーを削除します。 hでは、v3は[9, 10]で、v4は[11, 14]なので、それらはマージされます。 ratは、コピーをループの深さでソートし、最も深いものから順に処理します。ホットなコピーは、コールドなコピーがそれらをブロックする前にマージされます。バンドルはユニオンファインドで保持されます。マージは、まず両方のセグメントリストをウォークして重複を確認します。ratは、2つのバンドルを合わせたセグメント数が256を超える場合、マージをスキップします。 vregと物理レジスタ間のコピーは、代わりにヒントを設定します。バンドルはそのレジスタが空いている場合、そのレジスタを優先します。 レジスタの選択 各バンドルは優先度を受け取ります。 priority = weight / sqrt(length in slots) 短くホットなレンジが最初にきます。それらは最も重要であり、配置が最も容易です。長くコールドなレンジが最後にきて、スピルされます。sqrtは、長いループカウンターが優先度を大幅に失うのを防ぎます。 ratは各バンドルを優先度順に呼び出します。 // cls: register class, gp or xmm PhysReg pick(VReg v) { U64 blocked = ~allocatable[cls]; for(auto [start, end] : segs[v]) for(I32 s = start; s <= end; ++s) blocked |= busy[s]; // or 64 at a time if(hint[v] != kNoReg && !(blocked >> hint[v] & 1)) return hint[v]; // ca