レジスタは少なく値は多い — 寿命で分け、片付ける

一言でいうと

コンパイラーは、値ごとに名前(仮想レジスター)を際限なく作って使いますが、CPUのレジスターは16個しかありません。生存解析で値がいつからいつまで生きているかを求め、線形スキャンで重ならない値どうしに同じレジスターを分け合わせ、足りなければ一部をメモリへ退避します(spill)。プログラムが実行中に作ったオブジェクトは、反対に、だれからも指されなくなったら、ガベージコレクターがルートから届くものだけを残して片付けます。

なぜ必要なのか

モジュール8のコード生成器は、すべてのローカル変数をスタックスロットに置き、使うたびにメモリから読み書きします。間違いではありませんが、レジスターは1サイクルで読めるのに対し、メモリはキャッシュにあっても数サイクルかかります。gcc -O0と-O2の出力の違いのうち、いちばん大きな部分がこれ、つまり値をレジスターに置くかどうかです。

ところが、値は多く、レジスターは少ししかありません。2つの値が同時に生きていないなら、同じレジスターを使ってかまいません。「生きている」とは「この値をあとでもう一度読むことがある」という意味で、それをコードだけを見て計算するのが、生存解析です。

メモリの反対側にも、同じ問いがあります。モジュール5のクロージャは、呼び出しが終わった環境をつかんで生かしておきました。では、いつ捨ててもよいのでしょうか。だれにも届かなくなったときです。ガベージコレクターは、それを人の代わりに計算します。

どう動くのか

生存解析は後ろから前へ。命令iの直後に生きている値(live-out)がわかれば、その前(live-in)はuse ∪ (live_out − def)です。この命令が使う値は前でも生きている必要があり、この命令が定義する値は前にはまだありませんでした。最後の命令から逆にたどれば、1回で終わります。ループのあるCFGでは、後ろへ戻る辺のせいで1回では終わりません。ブロック単位でlive_out = 다음 블록들의 live_in 합집합(プレースホルダーは次のブロックたちのlive_inの和集合です)を、もう変わらなくなるまで繰り返します(モジュール7のドミネーターと同じ固定点計算です)。

線形スキャン。値ごとに[定義した命令, 最後に使う命令]の区間を作り、開始の順にたどりながらレジスターを割り当てます。

구간(명령 번호)          k = 2 개의 레지스터로
t1 [0 ──────── 4]        t1 → r0
t2   [1 ───────────── 6] t2 → r1
t3     [2 ──── 4]        t3: 빈 레지스터가 없다. 활성인 t1(끝 4)·t2(끝 6)와 t3(끝 4) 가운데
                             끝이 가장 먼 t2 를 넘기고, t3 가 t2 의 r1 을 물려받는다
t4        [3 ── 5]       t4: 여전히 꽉 참. t1·t3(끝 4)·t4(끝 5) 가운데 끝이 가장 먼 것은 t4 자신 → t4 를 넘긴다
t5          [4 ─ 5]      t5: 시작 4 — 끝이 4 인 t1·t3 는 아직 쓰는 중(같으면 풀지 않는다) → 넘긴다

終わりがいちばん遠いものを退避させる理由は、その値がレジスターをいちばん長く握り続けるからです。退避した値は、使うたびにメモリから読み書きします(モジュール8のスロットが、まさにその場所です)。新しい区間の前では、終わりが新しい開始より小さい区間だけを解放します。同じ命令で終わる値は、その命令がまだ読んでいる最中だからです。この1文字の違い(<と<=)が、いちばんよくある間違いです。

mark-sweep。ヒープを「オブジェクト → 指しているオブジェクトたち」のグラフと見ると、ルート(スタックとグローバルにある値)からたどって届くオブジェクトだけが生きています。マーク(mark)の段階は、ルートからグラフをたどって届くものに印を付け、スイープ(sweep)の段階は、印のないものをすべて片付けます。循環(A ↔ B)があっても、すでに印を付けたものは見直さないので終わり、ルートから切り離された循環は、丸ごと片付けられます。マークを再帰で書くと、10万個の連結リストで再帰の上限を超えるので、明示的なスタックでたどります。

参照カウントが見逃すもの。オブジェクトごとに「何か所が自分を指しているか」を数えて、0になったらすぐ片付ける方式(参照カウント)は、マークの段階なしにすぐ片付けるので、停止がありません。ただし、AとBが互いを指していると、ルートから切り離されても、数が1から下がらず、永遠に残ります。CPythonが参照カウントを基本にしながら、循環を探すコレクター(gcモジュール)を別に持っている理由です。

現場での姿

JITは線形スキャンを好みます。グラフ彩色(graph coloring)方式はレジスターをうまく使えますが、遅くなります。実行中にコンパイルしなければならないJIT(HotSpotのC1、V8の初期段階)は、速い線形スキャン系を使います。コンパイル時間が、そのままユーザーが待つ時間だからです。
GCの停止。mark-sweepは、マークしているあいだプログラムを止める必要があります(その間にポインターが変わると、マークが間違うからです)。ヒープが大きいと、この停止が数百ミリ秒になります。実際のJVMが、この停止をどのようにログに残し、何で減らすのかは、ヒープは余っていたのにサービスが止まったコースのGCログのモジュールが扱います。
GCなしで片付ける方法。Rustはコレクターなしで、「この値の持ち主が消える場所」をコンパイル時に決め、その場所に解放のコードを入れます。モジュール4のスコープ解析を値の寿命まで広げたものと言えます。Rust — コンパイラが止めるものコースが、その規則をエラーメッセージで読みます。

次のラボですること

regalloc.pyに、直線コードの生存解析、生存区間と同時に生きている値の最大数、線形スキャン、割り当ての検証器、ループのあるCFGのブロックごとの生存解析を作り、heap.pyに、マーク・スイープ、参照カウントが見逃すゴミの計算、割り当て記録をたどって動くコレクターを作ります。採点ツールは、ランダムなコード・グラフ・ヒープ・記録数百個で基準と突き合わせます。