アセンブリへのコンパイル時のジャンプ量を最小限にする

Question

いくつかの抽象中間言語にいくつかのプログラムをコンパイルしたとします。プログラムは、次に実行する操作と決定（基本的にはツリー）のシーケンスです。例：

a(); 
if (bla) then c(); 
else b(); d(); 
e(); 

は今、我々はリニアメモリへの「パック」は、このシーケンスを必要とし、そうすることによって、我々のコードは、（条件付きとしない）分岐することがあります。例えば、可能性の1：

 CALL A 
     TEST bla 
     BRANCH else 
     CALL C 
     JMP esc 
else: CALL B 
     CALL D 
esc: CALL E 

は、これらのブロックを配置する方法についての複数の可能性は、線形メモリ内のコースがあり、それらはすべての支店/ジャンプの量が異なります。私たちの目標はそれらを最小化することです。
質問：
a）この問題をどのように呼びますか？それの一般的な名前はありますか？ （BDD構築のインスタンスですか？）
b）ジャンプ/分岐の量が最小限になるようなブロックの配置を見つけると、そのような問題の複雑さは何ですか？

Answer 1

あなたが持っているものは、各基本ブロックの終わりにあるものから別のものに制御を渡す一連の基本ブロックです。

これは有向グラフで簡単にモデル化できます。ノードは基本ブロックです。あるノードから別のノードへの指示されたアークは、あるブロックから別のブロックへの条件分岐（時には条件が「真」である）を表す（wlog）。発生した例外を分岐として考え、ハンドラをブロックとして捕捉するべきです。

一連のブロックを線形化することは、原則として一連のアークを選択することです。そのようなシーケンスは、ブランチを持たないブロックで終了する（例えば、関数戻りまたはアプリケーション終了を行う）。

あなたがしたいことは、残りの円弧（赤色を想像してみてください）が最小になるように、一連の円弧シーケンスを選択することです（これらの青色を描くと想像してください）。

複雑さは分かりませんが、各ノードに2つの選択肢があると思われるので、指数関数的に難しいようです。 （最悪の場合、完全に接続されたグラフを持つことができます。通常、このようなグラフについての推論は非常に高価です）。

私は貪欲な仕組みでこれを実装し、かなり良い結果を得ることができると期待しています。最も長い円弧シーケンスを繰り返し見つけて青色にします。

最大シーケンシングは、おそらくあなたが望むものではありません。プロファイリングデータ、アルゴリズムの知識、例外が稀である可能性が低いため、確率が低い、プログラマがヒントを提供するという仮定に基づいて、各アークに確率を付けるとします。今あなたが望むのは、確率の最も高い弧の長い鎖です。このような経路は文献では「痕跡」と呼ばれています。これにより、コード内のホットパスがメモリ内でシーケンシャルになり、命令キャッシュの価値を最大限に引き出します。このように定義されたオフシーケンスブランチは、低確率、例えばコールドパスである。

あなたはまだ同じ複雑さを選択しています。しかし、貪欲なスキームはもっとうまくいくかもしれません。シーケンス内の各ノードから最も高い確率のアークを選択するだけでシーケンスを形成します。

アークシーケンスを色分けして、「正しい」順序でコードを生成するのは簡単です。

このpaperは、トレースをより正式に使用して、具体的にはキャッシュミスのコストを削減するための「コード配置」について説明しています。それは、かなり良い結果を生み出す欲張りの選択プロセスと、優れた結果を生み出すより洗練されているがかなり時間がかかる「ローカル検索」スキームについて論じている。