レジスタの割り当てとスピル、簡単な方法は?

StackOverflow https://stackoverflow.com/questions/1960888

質問

ローカル変数をレジスタに割り当てる方法を探しています。私はそれを行うためのいくつかの本格的な方法を知っています（つまり、 ウィキペディアで）、しかし、「流出」がどのように達成されるかについて行き詰まっています。また、関連する文献は非常に恐ろしいものです。私の優先事項を満たす、もっとシンプルなものがあることを願っています。

  1. 正確性 -- ローカル変数の数に関係なく、正しいコードを生成するアルゴリズム。
  2. シンプルさ -- あまり多くの文献を読まなくても理解できること。
  3. 効率 -- 現在の方法よりも優れている必要があります。

オペレーションを翻訳する x = y # z に：

movl y, %eax
movl z, %ebx
op %ebx, %eax
movl %eax, x

Intel 386 をターゲットにしているため、関連する制約は次のとおりです。

  • バイナリ演算は 2 つの引数を取ります。そのうちの 1 つはソースと宛先です。単項演算は 1 つの引数を取ります。
  • 操作でアクセスできるのは 1 つのメモリ位置のみです。したがって、バイナリ演算にはレジスタに少なくとも 1 つの引数が必要です。
  • 最大 6 つのレジスタを使用できます。 %eax %ebx %ecx %edx %esi %edi. (%ebp 最後の手段として含めることもできます。）
  • 整数の除算や戻りレジスタなどの特殊なケースがありますが、ここでは無視してかまいません。

現時点でコンパイラーが実行するステップは 3 つあります。

  • i386化:すべての操作はフォームに変換されます 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, a 2 つのメモリアドレスを持ちます。オペランドの 1 つを一時的に保持するには別の予備のレジスタが必要になりますが、これは別の色をスピルすることを意味します。これは、次の一般的な方法を示唆しています。

  1. すべての変数に色を付けることができる場合 r 色、素晴らしい！
  2. それ以外の場合は、いくつかの色とそれに関連する変数をスピルします。
  3. 2 つのスピル変数にアクセスする操作が存在する場合は、別の色をスピルし、そのようなすべての操作の一時記憶域としてスペア レジスタを使用します。

この時点で、私は必要以上に多くのものが流出しているのではないかと疑い、変数そのものではなく変数の存続期間の一部を流出するなど、何かもっと賢い方法はないかと考えます。ここで使用できる簡単な（っぽい）テクニックはありますか?繰り返しますが、私は特に高い目標を掲げているわけではありません。確かに、深く読み込む必要があるほど高い目標ではありません。;-)

特定の問題

主な具体的な問題は次のとおりです。変数がスピルされた場合、生成された命令にどのような影響がありますか?その変数を使用するすべての命令は、メモリ内で (スタック位置から) 変数に直接アクセスする必要がありますか?操作で 2 つのスピル変数を使用する場合、これはどのように機能するでしょうか?(このアーキテクチャでは、命令が 2 つの異なるメモリ位置にアクセスすることは許可されていません。)

二次的な問題は次のとおりです。

  • 正確さ (そしてそれほど重要ではありませんが効率) のために、ロード/ストア命令を挿入する場所をどのように決定すればよいでしょうか?
  • 変数をすぐに使用しないときにその有効期間のその部分だけをスピルし、後でアンスピルすることはできますか?そのため、すべての命令はスピルされていないレジスターで動作します。変数は、異なる時点で異なるレジスタに存在する可能性があります。
  • 特殊なケースについてもう少し効率的にできないか。例えば、 %eax は戻り値に使用されるため、戻りが発生するまでに、返される変数がたまたまそのレジスタに割り当てられていれば良いのですが。同様に、一部のレジスタは「callee-save」であるため、関数呼び出し時にたまたまライブ状態の変数が少ない場合、それらの変数を非 callee-save レジスタに割り当てることで、それらのレジスタの格納を回避できます。
  • SSA フォームは (もしあったとしても) かなり役に立ちますか?共通の部分式を削除し、定数を評価できるようになれば、登録のプレッシャーが軽減される (?) かもしれませんが、そうでない場合は何らかの効果があるでしょうか?

私が（今のところ）気にしていない側面は次​​のとおりです。

  • スタックの割り当てと最適化:すでに素朴に実装されており、必要に応じて干渉グラフを使用して最適化できます。
  • 終了するまでのコンパイル時間の効率。(NP 完全性は、特定のアルゴリズムを回避する必要があることを意味するものではありません。)

アップデート

ダウンタイムが発生して申し訳ありません。私は与えられた答えについて考え、いくつかのアイデアを実装し始めるための簡単なアプローチを見つけようと努めてきました。正直、先延ばしにしてしまったのですが…:-\

非常に素晴らしいプレゼンテーションを見つけました (残念ながら PPT):

http://www.cs.princeton.edu/courses/archive/spr05/cos320/notes/Register%20Allocation.ppt

これは、特定の操作ニーズ (ソースとデスティネーションに同じレジスタを使用するなど) にどのように対処するかという質問に答えます。または一部の操作には特定のレジスタが必要です)。よくわからないのは、Liveness-Coloring-Allocation サイクルが終了するかどうかです。

近いうちに実際に作業してみますので、質問を終わりたいと思います。

役に立ちましたか？

解決

私はかなりうまくいっている、いったんJVMアロケータで貪欲なアプローチを使用しました。基本的には、スタックに保存されているすべての値を持つ基本ブロックの先頭に開始します。それからちょうど値が含まれているレジスタのリストを維持し、前方の指示をスキャンし、その値は汚い（バックを書き込む必要がある）であるかどうか。命令は、レジスタ内（または正しくないレジスタに）ない値を使用している場合は、命令の前に無料のレジスタにそれを置くために、負荷（または移動）を発行。命令は値を書き込んだ場合、それはレジスタであることを確認し、命令の後に汚れをマークします。

あなたは今までにレジスタが必要な場合は、それから値を割り当て解除し、それが汚れやライブである場合、スタックにそれを書き込むことによって、使用するレジスタをこぼします。基本ブロックの終わりには、任意の汚れやライブレジスタを書き戻します。

あなたが行くように

このスキームは、すべてのロード/ストアが行く場所を正確にそれがクリアになり、あなたはそれらを生成します。これは、メモリ内の値をとる命令に簡単に適応可能である、またはメモリ内に二つの引数のいずれかかかることが、両方はできません。

あなたはすべての基本ブロック境界でスタック上のすべてのデータを持つているOK、このスキームはかなりうまく動作する場合。それは基本的に非常によく似たものがそうであるようにそれは、基本ブロック内スキャン線形と同様の結果を与える必要があります。

あなたは、任意にこぼれ、どのレジスタに割り当てるためにどの値を決定する方法については複雑になることができます。いくつかの先読みは、（例えば、EAXシフト量の戻り値、またはECXのために）、それは基本ブロックの中でいくつかの点でにする必要がある登録したときに値そのレジスタを好む特定の各値をマーキングすることによって、例えば、有用であり得ます最初の割り当て（及び他の割り当てのためにそのレジスタを回避）されます。しかし、改善ヒューリスティックから、アルゴリズムの正しさを分離することは容易である。

私はSSAコンパイラ、YMMVでこのアロケータを使用しました。

他のヒント

初め：賢い方法はありません。問題は NP 完全です ;-)

流出はどのように行われるか:

レジスタ割り当てアルゴリズムを実行し、スピルする必要がある変数のリストを取得します。これで、関数の先頭でスタックにスペースを割り当てることができます。流出したすべての変数もスタック上の場所にリンクします。重複しないライブ範囲でメモリをスマートに結合したい場合。レジスタをスピルする必要がある場合は、レジスタをメモリに保存し、再度必要になったときにロードします。

eaxの扱い方：

レジスターを充填済みとしてマークしますが、レジスターには変数を保管しません (事前割り当て)。これにより、コード ジェネレーターはそのレジスタをクリアします。有益であれば、値を別のレジスタに保存するのが賢明です。

こぼれた場合の簡単で正しい方法:

すべてをこぼすだけです。これは、すべての変数の有効範囲がプログラム全体であることを前提としています。これは、LRU や使用カウントなどを使用して、どのレジスタを解放するかを選択することで強化できます。

次に最善の策はおそらく リニアスキャンレジスタの割り当て. 。事前割り当てを使用する場合でも実装は非常に簡単です。リンク先の論文を調べてみることをお勧めします。

具体的な回答

  1. あなたにとって正しさは何を意味しますか？単純な割り当てアルゴリズムでも、プログラミング エラーがなければ正しいものになります。（数学的）正しさを証明することははるかに困難です。値/レジスタが再度必要になる前に、ロードとストアの両方を挿入する必要があります。どちらも、値の保存/作成後に挿入する必要があります。

  2. はい。そのようにプログラムすれば。アルゴリズムがライブタイム中に複数のレジスタの値を処理できる場合は、それらの最適化を使用できます。

  3. 特定の改善を実装するかどうかは、やはりあなた次第です。1 つの可能性は、プログラム全体ではなく、必要な場合にのみ eax をブロックすることです。

  4. 特定の条件下では SSA が役に立ちます。SSA コードの推論グラフは常に 和音の, これは、3 つを超えるノードを持つサイクルがないことを意味します。これはグラフの色付けの特殊なケースであり、多項式時間で最小限の色付けが見つかります。SSA への変換は、必ずしもレジスタープレッシャーの多かれ少なかれを意味するわけではありません。通常、SSA 形式にはより多くの変数がありますが、ライブタイムは短くなる傾向があります。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top