2005年11月14日

MinCaml: 早期退避型レジスタ割り当ての後戻り解消

書いた後になってregAlloc.target-latespill.mlとして類似の構造が既にあったのに気が付いたので、説明は簡単にする。

MinCaml 0.0.9のオリジナルのregAlloc.mlはレジスタ溢れが発生するたびにToSpillを返して溢れた変数が定義された時点まで遡って処理をやり直す。 この構造は次の二点を目的としている。

  1. 変数定義の直後に、変数をスタックに記録するSave仮想命令を挿入する。
  2. (Forgetノードの効果) その命令の直後にForgetノードを挿入してレジスタから溢れる変数を以後使われないよう見せかけることで、やり直し時にレジスタ割り当てを意図したレジスタに行わせる。

Forgetは一見、挿入した直前の命令のみならずそれ以前の命令にも影響するように思えるが、溢れさせるレジスタの選択方式を考え合わせると実は影響がない。call命令直後に挿入するものは例外だが、これは自由変数の収集時にtargetと同じくcall命令より先は見ないという配慮をすれば不要にできる。

従ってやり直しはレジスタ溢れを起こした命令だけでよいので、後戻りなしでも同じレジスタ割り当てが可能である。

(上記は誤った理解に基いた記述であり、レジスタと変数の対応は変わり得る。コメント欄に頂いたご指摘及び改訂したMinCaml読解ノート: レジスタ割り当てを参照。ただしレジスタ溢れの発生回数については後戻りなしでも同じくすることがやはり可能であると考える。以後もそれを踏まえて読まれたい。)

この点を踏まえ、本変更では前述の二目的をそれぞれ次のように実現する。

  1. Save仮想命令を全ての変数について挿入しておき、そのうち不要なものを最後に一括して取り除く。要不要は変数がRestoreされるかどうかで決定できる。
  2. 次の命令に渡す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
後戻りなし。レジスタが不足したらコンパイルを断念する。レジスタ割り当ては次にどのレジスタに割り当てるのがよいかは考慮せず、空いているレジスタを番号の若いものから順に使う。

広告


この広告は60日以上更新がないブログに表示がされております。

以下のいずれかの方法で非表示にすることが可能です。

・記事の投稿、編集をおこなう
・マイブログの【設定】 > 【広告設定】 より、「60日間更新が無い場合」 の 「広告を表示しない」にチェックを入れて保存する。


×

この広告は1年以上新しい記事の投稿がないブログに表示されております。