命令の選択

コンピュータサイエンスにおいて、命令選択は、中間レベルの中間表現(IR) を低レベルの IR に変換するコンパイラバックエンドの段階です。一般的なコンパイラでは、命令選択は命令スケジューリングとレジスタ割り当ての両方に先行します。そのため、出力 IR には無限の疑似レジスタ (一時レジスタと呼ばれることが多い) があり、ピープホール最適化の対象となる可能性があり、通常は対象となります。それ以外の場合は、ターゲットのマシンコード、バイトコード、またはアセンブリ言語によく似ています。

例えば、次の中間レベルのIRコードのシーケンスの場合

t1 = α
t2 = ビット
t3 = t1 + t2
a = t3
t1 は

x86アーキテクチャに適した命令シーケンスは

MOV EAX 、a XCHG EAX 、b ADD a 、EAX  
  
  

指導選択に関する包括的な調査については、 ^{[1] [2]を参照。}

命令選択の最も単純なアプローチは、マクロ拡張^[3]または解釈型コード生成^{[4] [5] [6]}として知られています。マクロ拡張命令セレクタは、中間レベル IR 上でテンプレートを一致させることによって動作します。一致すると、対応するマクロが実行され、IR の一致した部分が入力として使用されて、適切なターゲット命令が発行されます。マクロ拡張は、中間レベル IR のテキスト表現に対して直接行うことができます^{[7] [8]}か、IR を最初にグラフィカル表現に変換してから深さ優先でトラバースすることもできます^[9] 。後者では、テンプレートはグラフ内の 1 つ以上の隣接ノードと一致します。

対象マシンが非常に単純でない限り、マクロ展開のみでは非効率的なコードが生成されることが多い。この制限を緩和するために、このアプローチを適用するコンパイラは通常、ピープホール最適化と組み合わせて、単純な命令の組み合わせをより複雑な同等のものに置き換え、パフォーマンスを向上させ、コードサイズを削減する。これはデイビッドソン・フレイザーアプローチとして知られ、現在GCCに適用されている。^[10]

もう 1 つのアプローチは、まず中間レベルの IR をグラフに変換し、次にパターンを使用してグラフをカバーすることです。パターンはグラフの一部に一致するテンプレートであり、ターゲット マシンによって提供される単一の命令で実装できます。目標は、選択したパターンの合計コストが最小になるようにグラフをカバーすることです。コストは通常​​、命令の実行にかかるサイクル数を表します。ツリー型グラフの場合、最小コストのカバーは動的計画法を使用して線形時間で見つけることができます^[11]が、DAGや本格的なグラフの場合、問題は NP 完全になるため、貪欲アルゴリズムまたは組み合わせ最適化の方法を使用して解決されることが最も多くあります。^{[12] [13] [14]}

• 異なる世代のコンピュータをサポートする代替方法^{[永久リンク切れ‍ ]}