ローカル変数をレジスタに割り当てる方法を探しています。それを行うためのいくつかの深刻な方法（つまり、ウィキペディアで言及されているもの）を知っていますが、「こぼれ」がどのように達成されるかについては固執しています。また、関連する文献は非常に威圧的です。私の優先事項を満たすもっと簡単なものがあることを願っています：
- 正しさ -- ローカル変数の数に関係なく、正しいコードを生成するアルゴリズム。
- シンプルさ -- あまり文献を読まなくても理解できるもの。
- 効率 -- 次のような現在の方法よりも優れている必要があります。
x = y # z操作を次のように変換します。
movl y, %eax
movl z, %ebx
op %ebx, %eax
movl %eax, x
Intel 386 をターゲットにしているため、関連する制約は次のとおりです。
- 二項演算は 2 つの引数を取り、そのうちの 1 つはソースと宛先です。単項演算は単一の引数を取ります。
- 操作は 1 つのメモリ ロケーションにのみアクセスできます。したがって、二項演算には、レジスタに少なくとも 1 つの引数が必要です。
- 使用できるレジスタは最大 6 つです
%eax%ebx%ecx%edx%esi%edi。(%ebp最後の手段として含めることもできます。) - 整数除算や戻りレジスタなどの特殊なケースもありますが、今のところ無視できます。
現時点で、コンパイラーが通過する 3 つのステップがあります。
- i386ification: すべての演算はフォーム
a = a # b(またはa = #a単項演算) に変換されます。 - ライブネス分析: 各操作の前後のライブ変数のセットが決定されます。
- 登録割り当て: 干渉グラフが作成され、色付けされます。
そして、コンパイラはクレヨンを空中に投げ、次に何をすべきかわかりません。
例
public int mf(int cr, int ci) {
int i = 0;
int zr = 0;
int zi = 0;
while (i < 100 && zr*zr + zi*zi < 4) {
int t = zr * zr - zi * zi + cr;
zi = 2 * zr * zi + ci;
zr = t;
i = i + 1;
}
return i;
}
これは、関数のかなりきれいな干渉グラフと、活性情報を含む CFG です。残念ながら、CFG 画像には垂直方向のスクロールが必要です。
7色使用しました。それらの1つ（またはその色が割り当てられた変数のセット）をこぼしたいと思います。あまり重要ではない選択方法。こぼれた変数をどのように処理するかは、注意が必要です。
t変数のセット$t4である「ピンク」をこぼしたとしましょう$t7。これは、これらの変数の 1 つを参照する操作は、レジスターではなく、スタック フレーム上のその位置からアクセスすることを意味します。これは、この例では機能するはずです。
しかし、プログラムが次の場合はどうでしょう。
...
a = a + b
...
両方aとbもこぼれなければなりませんでしたか？addl b, a2 つのメモリ アドレスを持つ命令を発行できません。オペランドの 1 つを一時的に保持する別のスペア レジスタが必要です。これは、別の色をこぼすことを意味します。これは、次の一般的な方法を示唆しています。
- すべての変数に色を付けることができれば
r、すばらしいことです。 - それ以外の場合は、いくつかの色とそれに関連する変数をスピルします。
- スピルされた 2 つの変数にアクセスする操作が存在する場合は、別の色をスピルし、そのようなすべての操作の一時記憶域としてスペア レジスタを使用します。
この時点で、必要以上に多くのものがこぼれているのではないかと思います。変数自体ではなく、変数の有効期間の一部をこぼすなど、何か賢い方法でこぼす方法はないかと考えています。ここで使用できる簡単な（っぽい）テクニックはありますか？繰り返しますが、私は特に高いところを目指しているわけではありません。確かに、何かを深く読む必要があるほど高くはありません。;-)
特定の問題
具体的な主な問題は、変数がスピルされた場合、生成される命令にどのような影響があるかということです。その変数を使用するすべての命令は、(スタック位置から) メモリ内で直接アクセスする必要がありますか? 操作が 2 つのスピルされた変数を使用する場合、これはどのように機能しますか? (アーキテクチャでは、命令が 2 つの異なるメモリ位置にアクセスすることはできません。)
二次的な問題は次のとおりです。
- 正確さ (そしてそれほど重要ではありませんが効率) のために、ロード/ストア命令を挿入する場所を決定するにはどうすればよいですか?
- 変数がすぐに使用されない場合に、その有効期間のその部分だけをスピルし、後でアンスピルすることはできますか? すべての命令がスピルされていないレジスタで動作するようにします。変数は、異なる時点で異なるレジスターに存在する可能性があります。
- 特殊なケースでもう少し効率的にできますか。例えば
%eax戻り値には が使われているので、たまたま戻り値が出るまでにそのレジスタに戻り値の変数が割り当てられていればいいのですが。同様に、一部のレジスタは「callee-save」であるため、関数呼び出し時にアクティブな変数が少ない場合、それらを呼び出し先保存以外のレジスタに割り当てると、それらのレジスタの格納を回避できます。 - SSAフォームは（もしあれば）大いに役立ちますか？一般的な部分式を削除して定数を評価できるようになれば、レジスタの負担が軽減 (?) される可能性がありますが、それ以外の場合は効果がありますか?
私が（今のところ）気にしていない側面は次のとおりです。
- スタックの割り当てと最適化: すでに単純に実装されており、必要に応じて干渉グラフを使用して最適化できます。
- 終了する限り、コンパイル時の効率。(NP 完全性は、特定のアルゴリズムを避ける必要があることを意味するものではありません。)
アップデート
ダウンタイムについて申し訳ありません-私は与えられた答えについて考えていて、いくつかのアイデアの実装を開始するための簡単なアプローチを見つけようとしています. 正直、先延ばしにしていました... :-\
とても素敵なプレゼンテーションを見つけました (PPT、悲しいことに):
http://www.cs.princeton.edu/courses/archive/spr05/cos320/notes/Register%20Allocation.ppt
これは、特定の操作のニーズに対処する方法に関する質問に答えます (ソースと宛先に同じレジスタを使用する、または一部の操作に特定のレジスタを必要とするなど)。私が確信していないのは、Liveness-Coloring-Allocation サイクルが終了するかどうかです。
すぐに実際の作業を行い、うまくいけば質問を閉じます。