問題タブ [register-allocation]

私はドラゴンブックとMLでのModernCompilerImplementationを持っています。コンパイラでのコード生成に関する他の優れたリソースを探しています。何かお勧めできますか？

C では & を使用してレジスタ変数のアドレスを見つけることはできませんが、C++ では同じことができます。C++では合法なのにCでは合法でないのはなぜですか? 誰かがこの概念を詳しく説明してください。

ローカル変数をレジスタに割り当てる方法を探しています。それを行うためのいくつかの深刻な方法（つまり、ウィキペディアで言及されているもの）を知っていますが、「こぼれ」がどのように達成されるかについては固執しています。また、関連する文献は非常に威圧的です。私の優先事項を満たすもっと簡単なものがあることを願っています：

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

x = y # z操作を次のように変換します。

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

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

現時点で、コンパイラーが通過する 3 つのステップがあります。

• i386ification: すべての演算はフォームa = a # b(またはa = #a単項演算) に変換されます。
• ライブネス分析: 各操作の前後のライブ変数のセットが決定されます。
• 登録割り当て: 干渉グラフが作成され、色付けされます。

そして、コンパイラはクレヨンを空中に投げ、次に何をすべきかわかりません。

例

これは、関数のかなりきれいな干渉グラフと、活性情報を含む CFG です。残念ながら、CFG 画像には垂直方向のスクロールが必要です。

• 14 変数の関数の干渉グラフ
• 活性情報を含む関数の制御フロー グラフ

7色使用しました。それらの1つ（またはその色が割り当てられた変数のセット）をこぼしたいと思います。あまり重要ではない選択方法。こぼれた変数をどのように処理するかは、注意が必要です。

t変数のセット$t4である「ピンク」をこぼしたとしましょう$t7。これは、これらの変数の 1 つを参照する操作は、レジスターではなく、スタック フレーム上のその位置からアクセスすることを意味します。これは、この例では機能するはずです。

しかし、プログラムが次の場合はどうでしょう。

両方aとbもこぼれなければなりませんでしたか？addl b, a2 つのメモリ アドレスを持つ命令を発行できません。オペランドの 1 つを一時的に保持する別のスペア レジスタが必要です。これは、別の色をこぼすことを意味します。これは、次の一般的な方法を示唆しています。

1. すべての変数に色を付けることができればr、すばらしいことです。
2. それ以外の場合は、いくつかの色とそれに関連する変数をスピルします。
3. スピルされた 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 サイクルが終了するかどうかです。

すぐに実際の作業を行い、うまくいけば質問を閉じます。

干渉グラフを作成してレジスタ割り当てに使用するにはどうすればよいですか? ライブ範囲を決定するにはどうすればよいですか?

私は独自のコンパイラを構築してきましたが、その大部分は明らかにレジスタ アロケータであり、一時変数とマシン レジスタを可能な限り効率的に一致させます。x86 などのアーキテクチャでは、多くのレジスタがないため、変数をメモリ (スタック) に格納する必要がある多数のスピルがあります。大きすぎてレジスタに収まらないため、メモリに格納される変数もあります。

レジスタ アロケータが実際に再度呼び出され、メモリ内の変数が効率的に割り当てられるため、できるだけ多くのスペースが共有されます。本当の問題は、レジスタ アロケータがメモリ内の 2 つの変数を隣り合わせに配置するように制約する方法がないことです (これは、レジスタ アロケータが小さい変数をいくつかの小さい変数として割り当てることができるためです)。より大きな変数が収まるように、これを処理するアルゴリズムがあるかどうか疑問に思っています。それ以外の場合は、メモリを異なる領域に分割し、それぞれが異なるサイズの変数を保持する必要があります。

これを示す例を次に示します。

この例では、変数が最適化されていないこと、c が定義されると a と b が役に立たなくなること、すべての変数がスタック メモリに割り当てられることを前提としています。明らかに、'c' が 'a' および 'b' が使用したのと同じメモリを使用するため、8 バイトのみを割り当てる必要がありますが、現在のバージョンのコンパイラでは 16 バイトが完全に割り当てられます。

私の質問は、さまざまなサイズのメモリに変数を効率的に割り当てるにはどうすればよいですか?

グラフの色付けを使用してレジスタ割り当てに関する研究/プロジェクトを実行しようとしています。ここでは、さまざまなシナリオでさまざまな最適化レジスタ割り当てアルゴリズムの効率をテストしています。

どうすれば始められますか? それらをテストできる前提条件と根拠は何ですか? どのアルゴリズムを使用できますか?

追加：

私は実際にこれを手っ取り早く解決したいと思っています。詳細な調査は行っていませんが、「効率」に少し重点を置いて、すぐに利用できる分析をプロジェクトに (恥知らずに) 提出したいと考えています。つまり、さまざまなタスク/コンパイラ/インタプリタに最適な最適化手法の種類は何か。

したがって、私の主な仕事は、プログラムにレジスタ割り当てを (どのように) 実装するかです。Core2 Duo マシンで 64 ビット Linux システムを使用しています。私は C、C++、および Java を知っています。

ありがとうございました！

gcc でアセンブリをインライン化するとき、前のブロックで変数を有効にしておくために、定期的に空の asm ブロックを追加する必要があることに気付きます。たとえば、次のようになります。

奇妙さのもう 1 つの例は、以下のコードが最適化なしで問題なく動作することですが、-O3 を使用するとセグ フォールトが発生します。

非常に多くのレジスタを使用しているという事実に関係していると思います。ここに欠けているものはありますか、それとも gcc インライン アセンブリでレジスタ割り当てに本当にバグがありますか?

ARM インライン アセンブラ コードをいくつか作成しました。
Semaphore.s を見ると、gcc が "success" と "change" の 2 つの変数の両方にレジスタ r3 を使用していることがわかります。私の制約に問題があるのだろうか？
最も関連性の高い最初のコード行:

asm インライン:

制約:

シンボル ファイル:

ソースと生成されたシンボルの詳細を以下に示します。

シンボル ファイルからの関連テキスト: