命令の選択

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

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

t1 = a t2 = b t3 = t1 + t2 a = t3 b = 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 つ以上の隣接するノードに一致します。

ターゲットマシンが非常に単純な場合を除き、マクロ展開を単独で行うと、通常は非効率的なコードが生成されます。この制限を軽減するために、このアプローチを採用するコンパイラは通常、これをピーフホール最適化と組み合わせて、単純な命令の組み合わせを、パフォーマンスを向上させコードサイズを削減するより複雑な同等の命令に置き換えます。これは、Davidson-Fraser アプローチとして知られており、現在GCCで採用されています。^{[ 10 ]}

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

• 異なる世代のコンピュータをサポートする代替手段