線形スキャンでレジスタを分け、マークしてスイープする

目標

仮想レジスターを使う中間コードで、値が生きている区間を求めて、線形スキャンで実際のレジスターk個に割り当て、ループのあるCFGの生存解析までを行います。続けて、ヒープのグラフでルートに届くオブジェクトだけを残すmark-sweepコレクターを作り、参照カウント方式が何を見逃すかを数えます。

なぜ重要なのか

-O0と-O2のいちばん大きな違いは、値をレジスターに置くかどうかで、その決定は「2つの値が同時に生きているか」にかかっています。ガベージコレクションは、その反対側、つまり実行中に作ったオブジェクトをいつ捨ててよいかを、同じ道具(グラフをたどって届くものを探す)で解きます。どちらも、規則の1文字(<と<=、再帰と反復)で間違えやすいものです。

ルール

중간 코드   명령 {"op", "def"(없을 수 있음), "use": [..]} 의 목록. 가상 레지스터마다 def 는 한 번(param 도 def)
liveness    명령마다 그 명령 **바로 뒤** 에 살아 있는 값(이름순 목록). 마지막 명령 뒤는 빈 목록
intervals   {값: [정의한 명령, 마지막으로 쓰는 명령]} (쓰지 않으면 [정의, 정의])
max_pressure 한 명령에서 쓰는 값 ∪ 정의하는 값 ∪ 그 뒤에 살아 있는 값 의 크기 가운데 최댓값
linear_scan(구간, k)  → {값: "r0".."r{k-1}" 또는 "spill"}
            시작 순(같으면 이름순)으로 훑는다. 새 구간 앞에서 끝 < 새 시작 인 활성 구간만 풀어 준다.
            빈 레지스터가 있으면 번호가 가장 작은 것. 없으면 활성 구간과 새 구간 가운데 끝이 가장 먼 것
            (끝이 같으면 이름이 큰 쪽)을 넘기고, 넘긴 것이 활성 구간이면 그 레지스터를 새 구간이 물려받는다
conflicts   같은 레지스터를 받은 두 구간이 겹치면(s1 ≤ e2 이고 s2 ≤ e1) [a, b](이름순), 목록도 정렬
block_liveness(blocks, succ)  → (live_in, live_out) 블록마다 이름순 목록. 고정점까지 되풀이
mark(heap, roots)   heap = {번호: [가리키는 번호…]}. 뿌리에서 닿는 번호(오름차순). 힙에 없는 뿌리는 무시.
                    재귀하지 않는다(10만 개짜리 연결 리스트도 받는다)
sweep(heap, marked) → (살아남은 힙, 치운 번호 오름차순)
refcount_leaks(heap, roots)  뿌리도 참조 하나로 센다. 0 인 것을 치우며 가리키던 것의 수를 줄이고 되풀이.
                    그래도 남았는데 뿌리에서 닿지 않는 번호(오름차순)
simulate(trace, capacity)  기록: ["alloc", n] · ["link", a, b] · ["unlink", a, b] · ["root", n] · ["unroot", n]
                    alloc 하려는데 힙이 capacity 개면 먼저 mark-sweep. 그래도 꽉 차면 "out of memory" 로 멈춘다.
                    → {"collections", "freed", "peak", "live"(끝의 번호 오름차순), "error"}

ステップ

/root/mini/regalloc.pyのliveness(code)を埋めます。
intervals(code)とmax_pressure(code)を埋めます。
linear_scan(ivs, k)を埋めます。採点ツールが、レジスター1・2・3・4・6個で突き合わせます。
conflicts(ivs, alloc)を埋めます。正しい割り当てで誤検知が出ないようにします。
block_liveness(blocks, succ)を埋めます。/opt/fixtures/mini/regalloc/loop.jsonに、ループの例があります。
/root/mini/heap.pyのmark(heap, roots)を埋めます。
sweep(heap, marked)とrefcount_leaks(heap, roots)を埋めます。
simulate(trace, capacity)を埋めます。/opt/fixtures/mini/regalloc/trace.jsonが、手でたどってみられる例です。

参考

材料は、/opt/fixtures/mini/regalloc/のstraight.json(手で計算してみる直線コード)・pressure.json(レジスターが足りないコード)・loop.json・trace.jsonです。
よくある間違いは、live-outの代わりにlive-inを返す、終わりが新しい開始と同じ区間を解放する、退避させるときに常に新しい区間を退避させる、CFGを1回しかたどらない、マークを再帰で書く、循環ですでに見たオブジェクトをもう一度見る、の6つです。
セッションは60分で始まり、＋時間で延ばせます。終わると/root/miniが消えます。

後ろから前へ: 生存解析

liveの集合を空にしておき、最後の命令から逆にたどります。命令ごとに、まず今のliveをその命令のlive-outとして書き、そのあとdefを引いてuseを足します(それが前の命令のlive-outになります)。

生存区間と同時に生きている数

defに出会ったら[i, i]で始め、useに出会うたびに、終わりをmax(終わり, i)に伸ばします。同時に生きている値の最大数は、命令ごとにuse・def・live-outを合わせた集合の大きさのうち、いちばん大きい値です。

線形スキャン

開始の順にたどりながら、アクティブな区間のリストを持ち歩きます。新しい区間ごとに、まず終わり < 新しい開始のものだけを解放して、レジスターを返してもらいます(同じならまだ使用中です)。空いているレジスターは、番号の小さいものから。なければ(終わり, 名前)がいちばん大きいものを退避させ、それが新しい区間でなければ、そのレジスターを新しい区間に渡します。

割り当てを検証する

spillでない値を名前順に並べて、すべての組を見ます。同じレジスターで、区間が重なれば(一方の開始 ≤ 他方の終わり、そして逆も)衝突です。終わりと開始が接しているものも重なりです。その命令が両方を使うからです。

ループのある生存解析

ブロックごとに、use(ブロックの中で定義される前に使われたもの)とdefを先に求めます。そのあと、live_out = 後続ブロックのlive_inの和集合、live_in = use ∪ (live_out − def)を、すべてのブロックに適用することを、1周のあいだ何も変わらなくなるまで繰り返します。

ルートから届くものにマークを付ける

再帰の代わりに、リストをスタックとして使います。ヒープにあるルートから始めて、取り出したオブジェクトがすでに見たものなら飛ばし、そうでなければマークを付けて、それが指しているオブジェクトたちを積みます。すでに見たものを飛ばすことで、循環でも終わります。

スイープ、そして参照カウントが見逃すもの

sweepは、マークされたものだけを新しい辞書に移します。refcount_leaksは、すべてのオブジェクトの入ってくる参照の数(ルートを含む)を数え、0のものを片付けながら、それが指していたものの数を減らすことを繰り返します。最後まで残ったのにmarkで届かないものが、漏れている分です。

割り当て記録をたどって動くコレクター

allocに出会ったときにすでにcapacity個なら、mark → sweepしたあと、収集の回数と片付けた数を足します。それでもcapacity個なら、errorを書いて止まります。peakは、alloc直後のオブジェクト数の最大値です。trace.jsonを手でたどってみると、規則が見えます。