問題タブ [compiler-theory]

いくつかのハッシュ テーブルの実装で、バケット内のアイテムに対して「転置」や「前面に移動」などのヒューリスティックの使用法を見てきました。

1. このようなヒューリスティックを使用する利点は何ですか? 私はそれを自分で理解できませんでした。
2. ハッシュ テーブル / バケット レベルで他にどのような最適化を行うことができますか?その理由と状況は?

ハッシュ関数の最適化はさておき。

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

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 サイクルが終了するかどうかです。

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

結果が引数の値のみに依存する場合に関数呼び出しを最適化できるおもちゃのコンパイラーを書いています。したがって、xorやconcatenateのような関数はそれらの入力のみに依存し、同じ入力でそれらを呼び出すと常に同じ出力が得られます。ただし、timeやrandなどの関数は「非表示」のプログラム状態に依存し、同じ入力でそれらを呼び出すと異なる出力が得られる場合があります。「同型」や「リエントラント」など、これら2つのタイプの機能を区別する形容詞が何であるかを理解しようとしています。誰かが私が探している言葉を教えてもらえますか？

私は Kenneth Louden の Compiler Construction book を使用していますが、例が不足しており、これがどのように行われるかを示すルールに従うのは非常に困難です。LR(1) 状態に移動する方法がわかりません。また、LR(1) 状態から LALR(1) 状態に移行する方法もわかりません。

たとえば、これらの LR(1) は次のように述べています。

「S -> .XX, $」がどのようにそこに到達したかは理解していますが、「X -> .aX, a/b」を見てください。$ がその一部ではないのはなぜですか? $を持つルールから生成されたのではないので、$を持つ必要はありませんか? そして、a/b はどのように現れましたか? この本によると、A -> alpha.Bgama,a で B が非終端記号の場合、B -> .beta, b がすべての B -> beta に追加されます。b は最初の (gamaalpha) にあります。だから、私が理解したことから：

S -> .XX, $ and X -> aX and X -> b => X -> aX, $ and X -> b, $
X -> .aX, $ and X -> b, $ => 何も起こらない
A -> .a, $ => 何も起こらない

しかし、上記の例を考えると、それは完全に間違っているようです。

来年の夏には修士論文を書き始めたいと思っています。私は今、興味を持っている主題のプールを持っています。最も印象的だったのは、小さな C コンパイラ (グラフの色付けまたは線形スキャン) 用のグローバル レジスタ アロケータの実装です。

それで、私は立ち寄って、これをやったことがある人はいるか、それは修士論文の実行可能な主題であるか、または難しすぎるかどうかを尋ねたいと思いました. また、このテーマに関する優れた文献を教えていただければ幸いです (私はすでにドラゴンブックを持っています)。

楽しみのためにこれを実行する：http ：//www.diku.dk/hjemmesider/ansatte/torbenm/Basics/

null許容型の計算例で、最初に固定小数点計算を使用します。（セクション3.8を参照）

私はSchemeで物事を行っており、再帰に大きく依存しています。

null許容型または最初に再帰を介して実装しようとすると、次のようなプロダクションで無限に再帰することは明らかです。

N -> N a b

ここで、Nは非終端記号であり、a、bは終端記号です。

これは、プロダクションルールの左側に表示される非終端記号のセットを維持し、一度説明した後でそれらを無視することによって、再帰的に解決できますか？

これはnull許容型で機能するようです。最初はどうですか？

編集：これは私が遊んで学んだことです。下部にあるソースコードのリンク。

非終端記号は、null許容でない限り、firstの計算で無視することはできません。

検討：

ここでは、がnull可能NでN aあるため、無視できます。のメンバーであるとN置き換えN -> N aてN -> a推測することができます。afirst(N)

ここでは無視できませんN：

Ninを無視した場合、それはfalseであるN -> N aと推測されます。代わりに、Nはnull許容ではないことがわかります。したがって、最初に計算するときに、RHSの最初のシンボルとして見つかった生成を省略できます。afirst(N)N

これにより、次のようになります。

これはb、にあることを示していfirst(N)ます。

ソースコード： http： //gist.github.com/287069

それで...これは大丈夫ですか？

私は両方のウィザードブックに精通しています：

コンピュータプログラムの構造と解釈

とドラゴンブック：

コンパイラ：原則テクニックとツール

しかし、他のどの古典的な学術教科書がプログラマーにとって不可欠な読書であると考えているのか知りたいです。

関数の戻り値は通常、スタックまたはレジスタに格納されます。しかし、大きな構造体の場合、スタック上になければなりません。このコードを実際のコンパイラでコピーする必要があるのはどれくらいですか? それとも最適化されていますか？

例えば：

(関数をインライン化できないと仮定します..)

オフサイド言語とは、

...その言語の宣言 (ブロック) の範囲は、インデントによって表されます。

そのような言語の例としては、Python、Boo、Nemerle、YAML などがあります。

だから私の質問はこれです:これらを実際に解析するにはどうすればよいですか? タブとスペースの問題を解決するにはどうすればよいですか (2 つのタブまたは 8 つのスペースは同等かどうか)? ここでパーサージェネレーターは役に立ちますか、それともレクサー/パーサーを自分でハンドコーディングする必要がありますか?

まず、次のコードを見てください (このコードの shape は基本クラスで、line は派生クラスです)。

このプログラムをコンパイルすると、最初に shape の draw メソッドが呼び出され、その後プログラムが終了します。なぜ終了するのですか？基本クラスのポインターまたは参照なしでポリモーフィズムを実装できないのはなぜですか?これの技術的な理由は何ですか? オブジェクトの配列でポリモーフィズムを実装しようとしている場合、コンパイラは何をしますか? 例を挙げてわかりやすく説明してください。とても感謝しています。