書いた後になってregAlloc.target-latespill.mlとして類似の構造が既にあったのに気が付いたので、説明は簡単にする。
MinCaml 0.0.9のオリジナルのregAlloc.mlはレジスタ溢れが発生するたびにToSpillを返して溢れた変数が定義された時点まで遡って処理をやり直す。
この構造は次の二点を目的としている。
- 変数定義の直後に、変数をスタックに記録する
Save仮想命令を挿入する。 - (
Forgetノードの効果) その命令の直後にForgetノードを挿入してレジスタから溢れる変数を以後使われないよう見せかけることで、やり直し時にレジスタ割り当てを意図したレジスタに行わせる。
Forgetは一見、挿入した直前の命令のみならずそれ以前の命令にも影響するように思えるが、溢れさせるレジスタの選択方式を考え合わせると実は影響がない。call命令直後に挿入するものは例外だが、これは自由変数の収集時にtargetと同じくcall命令より先は見ないという配慮をすれば不要にできる。
従ってやり直しはレジスタ溢れを起こした命令だけでよいので、後戻りなしでも同じレジスタ割り当てが可能である。
(上記は誤った理解に基いた記述であり、レジスタと変数の対応は変わり得る。コメント欄に頂いたご指摘及び改訂したMinCaml読解ノート: レジスタ割り当てを参照。ただしレジスタ溢れの発生回数については後戻りなしでも同じくすることがやはり可能であると考える。以後もそれを踏まえて読まれたい。)
この点を踏まえ、本変更では前述の二目的をそれぞれ次のように実現する。
Save仮想命令を全ての変数について挿入しておき、そのうち不要なものを最後に一括して取り除く。要不要は変数がRestoreされるかどうかで決定できる。- 次の命令に渡す
regenv(レジスタと変数の割り当て表)を直接操作する。また、割り当てるレジスタを決定するときに、自由変数の収集を関数呼び出しより先は考慮しないようにする(targetが既に行っているのと同じ配慮)。
ソースファイルはregAlloc.target-earlyspill-nobacktrack.ml。前述のようにオリジナルのregAlloc.mlよりもregAlloc.target-latespill.mlに近く、わかりやすさはそれとほぼ同じ。
比較
ほとんどのケースで0.0.9のオリジナルのものと同等のコードを出力する。唯一、test/non-tail-if.sでは僅かによいコードを出力した。
追記: テストプログラムはないもののレジスタ割り当てが悪化するケースもあるとの指摘を頂いた。コメント欄参照。
応用
余分に挿入しておいて後から不要なものを削除する、若しくは必要なものを後から挿入するという手法はRestoreにも応用できる。
関数呼び出しによりレジスタが全て破壊されるが、ここで適当な変数を仮にRestoreしてしまうことで、その後に分岐があり一方の枝と分岐の合流後でその変数を参照するような場合にロードを削減できる場合がある。余分な仮のRestoreは最後に削除する。但しtargettingを阻害しないよう仮Restoreするレジスタには条件がつく。
regAlloc.mlのバリアント
最後に、MinCaml 0.0.9に含まれるregAlloc.mlのバリアントを簡単に紹介する。後のものほど前のものよりデグレードされている。
- regAlloc.target-earlyspill.ml
- regAlloc.mlと同一。
- regAlloc.target-latespill.ml
- 後戻りなし。変数の退避を、レジスタから溢れる直前に行う。同じ変数が二度三度退避されることが起こり得る。また、割り当てるレジスタの決定では関数呼び出しより先の参照を考慮してしまう弱点が存在する(
Forgetを使わないにも関わらず、前述のtargetと同様の配慮がなされないため)。 - regAlloc.target-nospill.ml
- 後戻りなし。レジスタが不足したらコンパイルを断念する。
- regAlloc.notarget-nospill.ml
- 後戻りなし。レジスタが不足したらコンパイルを断念する。レジスタ割り当ては次にどのレジスタに割り当てるのがよいかは考慮せず、空いているレジスタを番号の若いものから順に使う。
> Forgetは一見、挿入した直前の命令のみならずそれ以前の命令にも影響するように思えるが、溢れさせるレジスタの選択方式を考え合わせると実は影響がない。
↓みたいな例を考えると、必ずしもそうとは限らないです（ものすごくテキトーに作った例ですが）。いずれにせよ性能にはほとんど影響しないので、backtrackして複雑にする理由はないんですが…(^^;
let x = f () in
let y = 12345 in
let z0 = z.(0) in
let z1 = z0 + z0 in
let z2 = z1 + z1 in
let z3 = z2 + z2 in
let z4 = z3 + z3 in
let z5 = z4 + z4 in
let z6 = z5 + z5 in
let z7 = z6 + z6 in
let z8 = z7 + z7 in
let z9 = z8 + z8 in
let z10 = z9 + z9 in
let z11 = z10 + z10 in
let z12 = z11 + z11 in
let z13 = z12 + z12 in
let z14 = z13 + z13 in
let z15 = z14 + z14 in
print_int
(if z.(1) = 0 then
(z0 + z1 + z2 + z3 + z4 + z5 + z6 + z7 +
z8 + z9 + z10 + z11 + z12 + z13 + z14 + z15 + g y)
else
x)
> Save仮想命令を全ての変数について挿入しておき、そのうち不要なものを最後に一括して取り除く。要不要は変数がRestoreされるかどうかで決定できる。
この考え方だと、thenかelseの一方でしかSaveする必要のない変数が定義の直後にSaveされてしまうとか、ifのあたりで少し困らないでしょうか。
let x = 12345 in print_int (if y.(0) = 0 then f () + x else 123)
という例で試すと、
https://smpl.up.seesaa.net/mincaml/regAlloc.target-earlyspill-nobacktrack.ml.gz
の実装は結果がちょっとよくわからないのですが…
前者は難しそうです。とりあえず後者についてだけ考えさせて下さい。
まず、g'_ifの回りは多少甘いですが、むしろ分岐前にSaveするべきものを分岐後にそれぞれSaveする可能性があると思っています(g'_ifが呼ぶg_startはSaveの挿入も行います)。
ご指摘の例がよくわからないことになっているのは、yをallocしたときに上書きされたxをregenvが忘れていなかったことが原因のバグです。
それを修正すると、ご指摘のようにxのSaveが定義直後に入ってしまいます。これはyのalloc時に関数呼び出し以降の自由変数を無視してしまっているためxが上書きされるというのが直接の原因です。
これでも分岐がなければ問題ないが、分岐があるためにSaveを遅延させるといいことがある(かも知れない)。そのためにはレジスタが余っているなら上書きされぬ方がよい、というのが問題であろうかと思います。
そうすると、allocにおいて関数呼び出し以後の自由変数を無視していたのをやめると元に戻ります。やめるだけでは性能が落ちますので、空きレジスタの検索をtargetting対象とそれ以外に分け、全レジスタから空きを探す際はまず全自由変数を考慮、それで失敗したらSpillの前に無視してもう一度、というのでどうでしょうか。対症療法的になりつつあるきらいはありますが。
ひとまず、regAlloc.target-earlyspill-nobacktrack.ml.gzを以上を踏まえ更新してみました。