レジスタ割り当て(regAlloc.ml)

 

[2008917日更新: 現在のバージョンのレジスタ割り当てでは、以下の「さかのぼってSaveを挿入する」処理(ToSpillNoSpillなど)が省略されています。実装がより単純で、レジスタ割り当て自体が高速になり、コンパイルされたプログラムの性能はほとんど変化しないためです。]

 

MinCamlコンパイラでもっとも複雑な処理が、無限個の変数を有限個のレジスタで実現するレジスタ割り当てです。

 

まず関数呼び出し規約として、引数は番号の小さいレジスタから順に割り当てていくことにします(レジスタで渡しきれないほど数の多い引数は、プログラマが組などで置き換えることとし、MinCamlコンパイラではサポートしません)。返値は第一レジスタにセットすることにします。これらは関数のレジスタ割り当てRegAlloc.hで処理されます。

 

その上で、関数の本体やメインルーチンについてレジスタ割り当てをしていきます。RegAlloc.gは、今のレジスタ割り当てを表す(変数からレジスタへの)写像regenvと、命令列とを受け取り、レジスタ割り当てを行って返します。レジスタ割り当ての基本方針は、「まだ生きている(これから使われる)変数が割り当てられているレジスタは避ける」ことです。「まだ生きている変数」はSparcAsm.fvにより計算されます。ただし、Let(x, e1, e2)e1をレジスタ割り当てする際には、現在の式e1だけでなく、その「後」にくる命令列e2も「これから使われる変数」の計算に含めなければいけません。そのためにRegAlloc.gや、式をレジスタ割り当てする関数RegAlloc.g'では、「これから後」にくる命令列contも引数として受け取り、生きている変数の計算に用いています。

 

しかし、変数は無限にあってもレジスタは有限なので、どうしても生きているレジスタしか割り当てられないこともあります。その場合は、現在のレジスタの値をメモリに退避する必要があります。これをレジスタ溢れ(register spilling)といいます。命令型言語と違って、関数型言語では変数の値が後から変わることはないので、どうせ退避するならできるだけ早く行うのが得策です。それだけ早くレジスタに空きができるからです。

 

そこでRegAlloc.gでは、変数xの退避が必要になったら、そのことを表すデータ型ToSpillを返し、xの定義までさかのぼって退避命令Saveを挿入します。また、退避が必要になった時点でxは「生きている変数」から除外したいので、その部分にForgetという仮想命令を挿入して自由変数の集合から除外します。そのためにToSpillは退避すべき変数(のリスト)だけでなく、Forget挿入後の命令列eも保持しています。x Saveした後はeに対してレジスタ割り当てをやり直すわけです。

 

退避が必要になるのは、レジスタが不足した場合だけではなく、関数呼び出しもあります。MinCamlではいわゆるcaller saveの慣習を採用しており、関数を呼び出したらレジスタの値は失われます。したがって、その時点で生きている変数の値は、すべて退避する必要があります。ToSpillが一個ではなく複数の変数を(リストとして)保持しているのは、このためです。

 

なお、もし退避が必要にならなかった場合は、レジスタ割り当てされた命令列e'と、新しいregenvをデータ型NoSpillとして返します。

 

退避された変数は、いずれまた使用されます。しかしregenvを引いてもレジスタが見つからないので、RegAlloc.g'式をレジスタ割り当てする関数で例外が発生します。この例外は関数RegAlloc.g'_and_restoreにより処理され、メモリからレジスタへ変数を復帰する仮想命令Restoreが挿入されます。

 

レジスタを割り当てるときは、単に「生きているレジスタを避ける」だけでなく、「将来の無駄なmovを削減する」努力もしています(register targetingないしregister coalescingといいます)。たとえば、定義された変数が関数呼び出しの第二引数になるのであれば、できるだけ第二レジスタに割り当てるようにします。また、関数の返値となる変数は、できるだけ第一レジスタに割り当てるようにします。これらを実装したのがRegAlloc.targetです。この処理のためにRegAlloc.gRegAlloc.g'は、計算結果(関数の返値)を格納するレジスタdestも引数として要求・使用しています。

 

次へ進む