assemblyコンパイラパフォーマンス

ネズミのレジスタアロケータ

小さなレジスタアロケータを、ライブインターバルと衝突から固定レジスタとスピルまで段階的に解説する。この設計はスループットよりも明快さを重視しており、ライブラリとしてではなくレシピとして読むことを意図している。

hexrathexrat約 13 分

日本語
中文日本語
コピー

2026 年 10 月 7 日

rat は私が書いた小さなコンパイラバックエンド（おまけに半分ほど動く C99 フロントエンド付き）だ。x86-64 コード生成器が中間表現（IR）を x86-64 命令に変換する。命令が使う仮想レジスタ（vreg）の数に制限はない。レジスタ割り当て器が各 vreg を物理レジスタに写す。汎用レジスタが 12 個、xmm レジスタが Linux では 14 個 1。空きがなければスタックに割り当てる。

長い間 rat は線形スキャン割り当て器を使っていて、プログラム順に生存区間をたどっていた。動きはしたが、継ぎ足しを重ねて育った末に 1392 行になった。そこでどの部分が実際に効いているのか測って、残りは捨て、584 行の優先度付きビンパッキング割り当て器を書いた。重要な順に生存区間をたどり、入る余地のある最初のレジスタに詰めていく。LLVM の貪欲割り当て器と同じ分類で、難しい部分のほとんどを削り、しかも生成されるコードは良くなった。

値は書き込まれた地点から最後に読まれる地点まで生存している。2 つの値が同じレジスタを共有できるのは、生存期間が重ならないときだけだ。

ある地点で生存している値が多すぎると、一部はメモリに置くしかない。スピルである。スピル 1 回につき store と load が 1 つずつ増える。最適割り当ては NP-hard なので 2、実用的な割り当て器はどれもヒューリスティクスを使う。

呼び出し規約が規則を 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      ; argument of g
3  call g             ; clobbers caller-saved
4  v3 = copy rax      ; t
5  v4 = copy v3
6  v4 = add v4, v2
7  rax = copy v4
8  ret

x86 の add は最初のオペランドを上書きする（2 アドレス形式）ので、命令 5 は先に t をコピーする。-O1 で割り当てた後：

push rbp
mov  rbp, rsp
sub  rsp, 0x8
push rbx              ; rbx is callee-saved: save it
mov  rbx, rsi         ; y
call g                ; x is already in rdi
add  rax, rbx         ; t stays in rax
pop  rbx
leave
ret

6 個のコピーのうち 5 個が消え、y は呼び出し先保存レジスタに入った。割り当て器のどこにも「呼び出しをまたぐ値は呼び出し先保存レジスタに置く」と書いたコードはない。設計から自然に出てくる結果で、これが一番気に入っている。

5 つのステップ

割り当て器は関数ごとに 5 つのステップを踏む：

  1. 生存区間：命令に番号を振り、各 vreg がどこで生存しているかを見つける。
  2. 固定レジスタ：コードが物理レジスタを直接使う箇所を印付ける。
  3. 合併：コピー命令でつながれた vreg を 1 つの組（バンドル3）にまとめ、コピー命令を消せるようにする。
  4. レジスタ選択：各バンドルにレジスタを割り当てる。重要なものから順に。
  5. スピル：レジスタが取れなかったバンドルにスタックを割り当て、コードを書き換える。

各バンドルはその生存期間を通じて、自分のレジスタかスタックを保持し続ける。割り当て器は決して：

  • バンドルからレジスタを取り上げない（追い出しがない）
  • 1 つの区間をレジスタとメモリに分割しない
  • 同じステップを 2 回走らせない

本物の割り当て器を巨大にしているのは、まさにこれらの部分だ。私の測定では、rat にこれらが欠けていることの影響は小さい。

生存区間

スロット

命令 i にはスロットが 2 つある。2i でオペランドを読み、2i+1 で結果を書く。生存区間は整列した [start, end] スロットの列である。

ソースオペランドがどこで終わるかは命令によって変わる：

  • コピー命令： ソースは読み取りスロットで終わり、デスティネーションは書き込みスロットで始まる。命令 2 の rdi = copy v1 では、v1 はスロット 4 で終わり、rdi はスロット 5 で始まる。重ならないので同じレジスタを共有でき、コピー命令は何もしなくなる。
  • その他の命令： ソースオペランドは書き込みスロットまで生存するので、結果が別のオペランドを上書きすることはない。v2 は命令 1 で書かれ、命令 6 の add で最後に読まれるので、[3, 13] で生存する。

生存出口集合

rat は各基本ブロックの生存出口（live-out）にある vreg を求める。後の基本ブロックがまだ読む可能性があるものだ。多くのコンパイラはブロックごとのビットセットと不動点ループでこれをやる。rat は vreg を 1 つずつ処理する：

  1. ある基本ブロックがその vreg を書く前に読むなら、その vreg はこのブロックの入口で生存している。
  2. そうしたブロックのそれぞれから、ワークリストが先行ブロックをさかのぼり、各先行ブロックの生存出口にその vreg を印付ける。
  3. さかのぼりはその vreg を定義するブロックで止まる。

vreg の生存コストは、それが生存しているブロックで決まり、blocks * vregs では決まらない。4

セグメントと重み

次に rat は各ブロックの live-out 集合から逆向きにたどり、セグメントを切り出す。同じ走査で各 vreg に重み、つまりスピルのコストも積み上げる。

各 def と各 use に 3d を加算する。ここで d はループの深さ（最大 11）を表す。

def または use の位置加算値
直線コード1
ループ 1 段3
ループ 2 段の入れ子9

空洞

live range には空洞が生じうる。つまり、vreg が死んでいる隙間のことだ。ブロックにはコード順に番号を振るので、ブロックを 1 つ飛ばす range にはそこに空洞ができる:

long f(long* a, long n) {
	for(long i = 0; i < n; ++i)
		if(a[i] < 0)
			a[i] = 0;
	return n * 3;
}

exit ブロックはループのブロックに挟まれている:

mov  eax, 0x0         ; offset 8*i, rax in the loop
cmp  rdx, rdi
jl   loop
exit:
lea  rax, [rdi+rdi*2] ; n*3 in the hole of rax
ret
loop:
mov  rcx, r8
add  rcx, rax
...
add  rax, 0x8
cmp  rdx, rdi
jl   loop
jmp  exit

rax のオフセットは exit ブロックでは死んでいるので、n*3（lea）は rax を使える。これは戻り値レジスタでもある。ブロックの順序がただで与えてくれる利点だ。

固定レジスタ

rat は自身のレジスタに 1 から 40 までの番号を振るので、U64 ひとつでレジスタ 1 組を収められる。各スロットはマスク busy[slot] に対応する。ビットが立っていれば、そのレジスタはそのスロットで使用中だ。

同じ逆方向の走査で、コードが直接使う物理レジスタにも印を付ける:

用途レジスタ使用中の区間
引数の受け渡し引数レジスタそれを読むコピーまで
呼び出しの引数引数レジスタそれを設定するコピーから呼び出しまで
呼び出しcaller-saved すべて呼び出しの 2 スロット
戻り値rax呼び出しからそれを読むコピーまで
除算rax rcx rdxrax rcx を読み、rax rdx を書く

h のマスクと range:

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 はそれぞれ読みスロットと書きスロット。# は使用中、= は live range、. は空き。縦線は命令間の隙間を越えて続く。"others" は残りすべての caller-saved レジスタを指す。

bundle がレジスタを確保すると、rat はその live range の各スロットで対応するビットを立てる。以降、vreg と固定レジスタは同じマスクのビットになる。64 スロットごとに集約マスク、つまりこの 64 個のマスクの OR も持つので、長い range は 64 スロットをまとめて飛ばせる。

合併

同じカテゴリの 2 つの vreg 間のコピーは合併の候補になる。こうしたコピーの出どころは:

  • 2 アドレス命令
  • phi ノード: 合流点に来る、異なる基本ブロックからの値

2 つの live range が重ならなければ、対応する vreg は 1 つの bundle に合併され、断片は統合され、重みは加算される。rat は同じ bundle 内のコピーを削除する。h では v3 が [9, 10]、v4 が [11, 14] なので、これらは合併する。

  • rat はコピーをループの深さで並べ替え、深いものを先頭にする。熱いコピーを先に合併し、冷たいコピーに邪魔されないようにする。
  • bundle はUnion-Findで管理する。
  • 合併の前に 2 つの断片リストを走査して重なりを調べる。2 つの bundle を合わせて 256 個を超える断片になるなら、rat はこの合併を見送る。

vreg と物理レジスタの間のコピーでは代わりに hint を設定する。そのレジスタが空いていれば、bundle はそれを優先して選ぶ。

レジスタの選択

各 bundle には優先度がある:

priority = weight / sqrt(length in slots)
  • 短くて熱い range が先頭に来る。最も重要で、最も割り当てやすい。
  • 長くて冷たい range は後ろに回り、スタックにスピルされる。
  • sqrt により、ループカウンタのような長い range も優先度をそれほど落とさずに済む。

rat は優先度の順に各 bundle に対して pick を呼ぶ:

// 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];
	// caller-saved first, callee-saved last
	return firstFree(order[cls], blocked);
}

h での選択

bundlehint結果
v1rdirdi
v3+v4raxrax
v2rsirbx

図では rdi は v1 の前後でしか使われないので、v1 がそれを得る。2 つのコピーはどちらも mov rdi, rdi になり、peephole 最適化が割り当て後にそれらを削除する。

v2 は呼び出しをまたぐ。呼び出しスロットでは caller-saved レジスタがすべて使用中なので、最初の空きレジスタは rbx、つまり最初の callee-saved レジスタになる。プロローグが保存するのは rat が使った callee-saved レジスタだけだ。

Linux では callee-saved の xmm レジスタは存在しないので、呼び出しをまたぐ浮動小数点値は必ずスタックを通る。

スピル

空きレジスタが見つからない bundle は、その生存期間全体にわたってスピルされる。次に rat はこうする:

  1. スピルする bundle を開始位置で並べ替える。スタックスロットの最後の bundle がすでに終わっていれば、それを再利用する。
  2. コードを書き換える。レジスタを確保した bundle の vreg は、そのレジスタに置き換える。
  3. 各命令の前に、スピルした各オペランドを一時レジスタにロードする。命令の後に、スピルした各結果を書き戻す。

一時レジスタは r10 または r11（浮動小数点なら xmm14 または xmm15）。どの bundle もこれらを取れない。両方とも埋まっていれば、rat はその命令の位置で最初の空きレジスタを取る。

一時レジスタが要らない場面は 2 つある。レジスタとスピル済み bundle の間のコピーは、そのまま load か store になる。呼び出しがスピル済みのスタック引数を読むときは、そのスタック slot から直接読む。

p では、同時に 14 個の値が生きている：

void p(long* a) {
	long x0 = a[0], x1 = a[1], ..., x13 = a[13];
	a[0] = x0 * x13; a[1] = x1 * x12; a[2] = x2 * x11;
	a[3] = x3 * x10; a[4] = x4 * x9;  a[5] = x5 * x8;
	a[6] = x6 * x7;
}

16 個のレジスタから rsp、rbp、r10、r11、rdi（a を保持している）を引くと、14 個の値に対して 11 個しか残らない。x0-x6 は積（二アドレス imul）も保持するので、使用はさらに増える。x7-x13 のうち、区間が最も長い 3 つがスタックに落ちる。

peephole の前：

mov  r12, [rdi+0x30]  ; x6, in a register
mov  r10, [rdi+0x38]  ; x7, spilled
mov  [rbp-0x8], r10
mov  r10, [rdi+0x40]  ; x8, spilled
mov  [rbp-0x10], r10
mov  r10, [rdi+0x48]  ; x9, spilled
mov  [rbp-0x18], r10
...
mov  r10, [rbp-0x18]  ; reload x9
imul r9, r10
mov  r10, [rbp-0x10]  ; reload x8
imul rbx, r10
mov  r10, [rbp-0x8]   ; reload x7
imul r12, r10

x9 の store からその reload までの間に、r10 を書く命令はない。そこで peephole が reload を消す。その後、そのスタック slot を読むものはないので、store も消える。

馬鹿げていることもある

追い出しがなければ、初期の決定が最終決定になる。次の例が一番腹立たしい：

long sum(long* a, long n) {
	long s = 0;
	for(long i = 0; i < n; ++i)
		s += a[i];
	return s;
}

rat はこれをこうコンパイルする：

mov  r9, rdi          ; a: rdi was taken by a[i]
mov  r8, rsi          ; n: rsi was taken by s
...
exit:
mov  rax, rsi         ; s: rax was taken by a+8*i
ret
loop:
mov  rax, r9
add  rax, rcx         ; rax = a + 8*i
mov  rdi, [rax]       ; rdi = a[i]
add  rsi, rdi
...

ループ内の値は区間が短くホットなので、先に割り当てられる：

  1. アドレス a+8*i が rax を得る。
  2. s はヒント rax を捨てて rsi を得る。
  3. a[i] が rdi を得る。
  4. a と n は最後に回され、それぞれのヒントも捨てる。

結果は 3 つの mov で、いずれもループの外。5 追い出しのあるアロケータならこの連鎖を直せる。3 つのコールド mov のためにそのコードを書く価値はないと判断した。

数字

旧アロケータとの比較：

指標変化
アロケータのソースコード-58%
生成命令数-3.6%
生成 store 数-22%
アロケータの所要時間、sqlite を -O0 で-77%
総コンパイル時間、sqlite を -O0 で-43%

機能ごとの貢献

書き直す前に、旧機能を 1 つずつ切ってコードを測った。プロジェクト全体で最も価値のある 1 時間だった：

機能削減できた命令新アロケータ
コピー合併とコピーヒント約 3 分の 1維持
ライブ区間の穴10%維持
使用回数による重み付きスピル選択5.5%維持
物理レジスタを指すヒント1%維持
スピル済み区間への楽観的な二度目の試行（アロケータ時間の 37%）0.01%削除
再実体化（再ロードではなく再計算）測定不能削除
スピル slot のキャッシュ測定不能削除

まとめ

追い出しも分割も二度目のパスもなしで、新しいアロケータは旧アロケータに勝った。品質の向上は主に安上がりな仕組みから来ている。合併、ヒント、穴、重みだ。

教訓はこうだ。旧コードを移植する前に、まず測れ。旧アロケータの仕事の大半は何もしていなかった。

参考文献の完全なリストは原論文を参照。

出典: hexrat← ホームへ戻る