演算に汎用レジスタも使うコードを生成するように修正した。 汎用レジスタへの割付はリニアスキャンという方法で行った。
リポジトリはこちら：https://github.com/tyfkda/xcc
追記・未来の記事：コンパイラでもっとレジスタを活用するために行った対策
モチベーション
「低レイヤ」コンパイラで出力するコードはスタックマシン方式という、計算途中の値がスタックに積まれていて、現在の値がスタックトップに格納された状態となるように計算するコードを生成する。 スタックマシン方式は抽象構文木と非常に相性がよくて、パーサで生成した構文木をたどる順番でコードを生成できるので比較的簡単にコード生成ができる。
ただそれだとコンパイル先のプロセッサ(x86-64)が汎用レジスタをたくさん持っていてもまるで活かしきれない。 そして変数や計算途中の値へのアクセスはすべてメモリを通すので遅くなってしまう。 これでは「Cコンパイラで生成したコードは遅いから使えない、やっぱアセンブリで書かないと」と、性能厨に罵倒されてしまう。
そこでレジスタ割付を実装した。
変更手順
スタックマシン方式から汎用レジスタを使用するコードを出力するレジスタマシン方式への変更は以下のような段階を踏んで進めた：
- 中間表現生成（スタックマシン方式のまま）
- 中間表現の命令セットをレジスタを使用する方式に変更（レジスタの確保／解放は逐次）
- 基本ブロックへの分割、生存期間の判定
- リニアスキャンレジスタ割付実装
中間表現化
スタックマシン方式は構文木と相性がいいので、コード生成で構文木をそのまま使って直接アセンブリコードを出力していて、わざわざ中間表現(Intermediate Representation, IR)を生成していなかった。 しかしレジスタ割付を行うには、それぞれの値が使用される期間を調べるために命令列を見る必要がある。 命令列はターゲットCPUの命令セットそのままではなく、もうちょっと扱いやすい形にしておくとやりやすい。 なので構文木からいったん中間表現を出力し、それを実際のCPUの命令に変換して出力する、という具合にする。
前提としてすでにスタックマシン方式を出力する動いているコンパイラがあるため、いきなりレジスタマシン方式の中間表現を生成する方式に変更するのは難しい。 まずは中間表現もスタックマシン方式のままの命令セットで実装する。 いままで直接x86-64のアセンブリコードを出力していたのを、それに似た中間表現の命令を用意してやってそれを出力し、それをx86に変換してやるという二段構えにする。
中間表現の命令セットをレジスタ方式に変更
今まで計算の途中結果をスタックで管理していたのを、レジスタで扱うような命令セットに変更する。 中間表現に仮想レジスタというものを導入して、演算を仮想レジスタ間で行うようにする。 仮想レジスタは好きな数だけ自由に扱えるものとして新しい値が登場するごとに新規に仮想レジスタを追加して使用し、中間表現ができあがったらその後に実際のプロセッサで使える有限個の物理レジスタに割り付けてやる。
ひとまず物理レジスタに割り付ける値は式の途中で発生する中間結果だけとする。 なのでレジスタの生存範囲は高々1つの式の間だけですみ、短命になる。 ひとまずのところ、使えるレジスタがなくなったら単にコンパイルエラーで中断させる。
ローカル変数はこれまで通りスタックフレームに割り付けておいて、値の参照で仮想レジスタに読み出し、代入で仮想レジスタから書き出す。
仮想レジスタの生存管理は、中間表現を頭からたどりながら逐次行う。 新しい仮想レジスタが出てきたら、空いている物理レジスタに割り付ける（空いてなかったらエラーで終了する）。 仮想レジスタは演算などで使われたらその場で廃棄され、使用していた物理レジスタを解放する。
x86-64では汎用レジスタが16本あって、そのうち自由に使えないスタックポインタrspとベースポインタrbp、また関数の引数用として使われる6個（rdi, rsi, rdx, rcx, r8, r9）と戻り値や乗除算で使われるraxを除いた残りの、7個を使用可能な演算用物理レジスタとする：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|
| +0 | rbx | |||||||
| +8 | r10 | r11 | r12 | r13 | r14 | r15 |
基本ブロックへの分割
ローカル変数も物理レジスタに割り付けられるようにするための準備として、仮想レジスタの生存期間を調べる。 そして生存期間を調べやすくするために基本ブロックというものを導入する。 基本ブロック(Basic Block, BB)というのは内部にジャンプ命令がなく、また途中にジャンプで入ってこられない、一連の命令列のことをいう。
基本ブロックへの切り分けは中間表現の出力と同時に行うことができる。
if文などの条件分岐やfor文などのループ構文での飛び先としてラベルを使用していたのを、基本ブロックに変更する。
でジャンプ命令が現れたら中間表現の追加先を次の基本ブロックに変更してやる。
基本ブロックの内部にはジャンプ命令がなくて通常はブロックの終わりで次の基本ブロックに遷移するんだけど、 条件分岐の場合にはブロックの最後に条件分岐命令がきて条件が成り立てばそちらに、成り立たなければ次のブロックにと、飛び先は高々2つとなる。
ループで戻る場合やbreak、continue、returnなどは基本ブロックの最後での無条件分岐となる。
仮想レジスタの生存期間を調べる
式の中間結果だけをレジスタ上で扱えるようにしたが、ローカル変数もできるだけレジスタに配置したい。 そうすると値の生存期間が１つの式を超えて延びる可能性があって、逐次での物理レジスタへの割付／解放では無理がある。 関数内の命令列で個々の値がどの範囲で使用されているかを調べて、どの値をどの物理レジスタに割り付けるか、というレジスタ割付を行う。 それをするためには各レジスタの生存期間を調べる必要がある。
仮想レジスタの生存期間を調べるにはまず中間表現の命令を順に見ていって、最初と最後の使用位置を調べてやる。 ただそれだけだとループで戻ってくる場合におかしくなる。 中間表現の命令順的にはその後使われてないから別のレジスタに明け渡してしまうけど、ループで戻ってくるのでその間も他の値で上書きされないよう保持しておかなければならないということが起こり得る。
そこで基本ブロックのフローを調べて生存期間を更新する。 基本ブロックごとに入力レジスタと出力レジスタを割り出す。
基本ブロック内で使用されるレジスタは、その基本ブロックに入力されるレジスタとなる。 そしてある基本ブロックAが要求する入力レジスタは、Aに遷移する基本ブロックが出力する必要があるレジスタとなる。 出力する必要ができたレジスタは、基本ブロック内で代入されていればそれが出力されるのでよし、 そうでなければさらに入力として伝播してやって、確定するまで続ける。
各基本ブロックからの出力となったレジスタは、その基本ブロックの末尾まで生きているものとしてやることで生存期間が決定する。
レジスタ割付（リニアスキャン）
各レジスタの生存期間を割り出したら、どの仮想レジスタをどの物理レジスタに割り当てるか、というレジスタ割り付けを行う。 レジスタ割り付けのアルゴリズムは、有名なものではグラフ彩色とリニアスキャンという方法がある。
グラフ彩色では仮想レジスタをノードと考える。 生存範囲が重なっているレジスタ同士は干渉といって、ノード同士を結ぶ。 結ばれたノード同士は同時に生存する必要があるので、物理レジスタを割り付ける場合には異なるレジスタにする必要がある。 物理レジスタを「色」と考えると、グラフのつながるノード同士は別の色で塗り分ける「彩色問題」と考えることができる、というわけ。
塗り分けるのに必要な色の数が物理レジスタ数を超えると、そのすべてを同時に物理レジスタに割り当てることができない。 その場合はどれかをスタックフレームに逃がしてやる（これをspillという）。 spillされたレジスタの値はスタックのpush/popで一時的に退避/復帰、とかじゃなく常にスタックフレームからの取り出し/格納になる。
グラフ彩色で生成されるコードのクオリティは高いが、コンパイル時の計算量が最悪仮想レジスタ数の2乗に比例するとのことで、計算量が線形でまた比較的簡単に実装できるというリニアスキャンという方法を試してみた。
リニアスキャンではレジスタの生存期間を調べる。 生存範囲では間が抜けるケースも扱えるけど、生存期間では抜けている間も構わずに使用しているとみなす。 で命令を順に見ていって物理レジスタに割り付けていくんだけど、物理レジスタが足りなくなったら今新たに追加しようとしているレジスタか、またはすでに割り付けているレジスタの中で最後まで生存するレジスタのどちらか長く生存する方をspillしてやる。 これを頭から最後まで命令列を1回たどればレジスタ割付が完了する。
論文に示されているリニアスキャンの擬似コード：
C言語の特徴として&で変数のアドレスを扱うことができる。
その変数がレジスタに割り付けられるとなると難しいことになるので、強制的にspillさせる。
またワードとして扱えない型、配列や構造体もレジスタに割り付けないものとする。
関数の仮引数もひとまずはspill扱いにする（x86-64ではレジスタ渡しで受け取れるのでメモリを介さずにレジスタ上だけでそのまま扱えればベストだが、今後の課題）。
spillされた値の取り扱い
spillされた仮想レジスタはスタックフレーム上に配置する。
中間表現の命令としては仮想レジスタを対象にしているが、それが物理レジスタに割り付けられたか、それともspillされているかによって出力するコードを変えるのはかなり大変になる。 そこで対処として、使用できる物理レジスタをいくつか減らしてspill用として予約しておいて、spillされたレジスタだったら命令前/命令後にスタックフレームからの読み出し/書き戻しを挿入してやるようにする。 そうすることで中間表現からアセンブリを出力する際にspillされているかどうかを気にしなくて済むようになる。 （x86ではレジスタ間だけじゃなく間接アドレッシングでメモリ上の値との演算もできるので、spillされた値の場合には出力するコードを変えてやれば効率がいいと思うが、今後の課題。）
spill用に確保するレジスタは、入力が最大2つなので2つ必要になる。 ただそうするとspillされたレジスタの読み出し先も管理する必要があって面倒なので、そういう事が起きる可能性がある命令には新規の仮想レジスタに移動させる命令を生成してやることで対処した。 その仮想レジスタはその命令間でしか使われないので必ず物理レジスタに乗るはずなのでspillは高々1個でおさまるはず、という回避方法。
9ccでは1つしか確保していないが、どうやって回避しているのかよくわからなかった…。
今後の課題
以上でレジスタ割付を行うCコンパイラが動作するようになった。今後の課題としては、
- 関数の引数もレジスタ割付可能にする
- 呼び出し規約で使用するレジスタや
%raxも利用できるようにする - SSA形式化
参考
- rui314/9cc: A Small C Compiler
- Linear Scan Register Allocation, MASSIMILIANO POLETTO and VIVEK SARKAR
追記：
- compilium v2 (in progress)の工夫点 - /var/log/hikalium 中間結果のみをレジスタで計算する