命令選択

命令選択は、IR（中間表現）内の操作をターゲットの命令に整理するプロセスです。1つのIR操作は複数の命令に展開される場合があり、複数のIR計算が1つの命令に統合されることもあります。目標は単に操作名が一致することだけでなく、ビット幅、符号拡張、メモリ順序、例外、レジスタ制約などがセマンティクスに適合することも含まれます。

アドレスの折りたたみから理解を始める

base + index*4 + 8 から 32ビット値を読み取る場合、x86-64のアドレッシングモードでは、ベースレジスタ、スケール付きインデックス、ディスプレースメントを直接表現できるため、アドレス全体を一時レジスタに計算しておく必要がありません。

このパターンが利用可能かどうかは、スケール係数、ディスプレースメントの範囲、レジスタ制約に依存します。もしアドレスがその後の複数の操作で再利用される場合、アドレスを個別に計算する方が適していることもあります。LEA命令は特定のアドレス形式を計算できますが、そのアドレスのメモリ内容は読み取りません。両方とも角括弧で結果を出力するため混同しないでください。

木のカバリング：制約のあるモデル内での選択

純粋な式を一時的に木として扱い、マシンパターンが木内の操作セットをカバーし、他のパターンで生成する必要がある入力を残します。カバリングは、必要なすべての操作を実装し、各境界値の表現要件を満たす必要があります。単に葉が1回だけカバーされればよいわけではありません。

例えば add(mul(x,4),y) は、シフトと加算で実現することもできますし、適切なLEA命令1つで実現することもできます。各パターンにコストを割り当てることで、組み合わせ最適化問題が得られます。しかし、コストは命令数、バイト数、レイテンシ、その他の推定値を指す可能性があり、それらが必ずしも一貫しているわけではありません。

3つの選択方法

DPの状態には通常、結果の類別（例えば、部分木がレジスタ値、即値、または折りたたみ可能なメモリオペランドを生成するかどうか）を含める必要があります。cost[node] という1つの数値だけを使うと、親パターンが必要とする異なる形式の情報が失われる可能性があります。

再帰式は以下のように理解できます：

cost(node, result_kind) = min(パターンコスト + 各入力に必要な形式のコスト)。

計算終了後にパターンをバックトラックし、依存関係の順序に従ってコードを生成します。ルツ優先マッチングアルゴリズムであっても、結果を使用する命令を先に実行し、入力を生成する命令を後で実行することはできません。マッチング順序と実行順序は分離する必要があります。

BURSなどの手法は、部分的な木書き換えマッチングを事前に計算し、ランタイムでの選択をより効率的にします。これは、任意の産業用DAG選択器がDPの意味でのグローバル最適解を求めているわけではないことを意味します。

コストに数値を与えて、「大きなパターン」の価値を知る

add(mul(x,4),y) を考えます。xとyがすでにレジスタにあり、結果もレジスタに必要であると仮定します。対象のターゲットには4つの合法なパターンがあります：定数乗算 MUL4、左シフト SHL2、通常の ADD、そして式全体をカバーできる LEA4 です。ここでのコストは人為的に定義された加算重みであり、⁠特定のCPUのサイクル表ではありません⁠。

def select(cost):
    # mul(x,4) の部分木は2つのパターンで実現可能；葉はすでにレジスタにあるためコストは0。
    child_cost, child = min((cost[op], (op,)) for op in ("MUL4", "SHL2"))
    candidates = [
        (child_cost + cost["ADD"], child + ("ADD",)),
        (cost["LEA4"], ("LEA4",)),
    ]
    return min(candidates)


assert select({"MUL4": 3, "SHL2": 1, "ADD": 1, "LEA4": 3}) == (2, ("SHL2", "ADD"))
assert select({"MUL4": 3, "SHL2": 1, "ADD": 1, "LEA4": 1}) == (1, ("LEA4",))

# 2^32 法則（符号なし）セマンティクスで、2つのカバリングの数値結果を検証。
mask = (1 << 32) - 1
for x in (0, 1, 1 << 30, mask):
    for y in (0, 7, mask):
        separate = (((x << 2) & mask) + y) & mask
        combined = (x * 4 + y) & mask
        assert separate == combined

第1のコストセットでは、ノードを最も多くカバーする LEA4 はコスト3ですが、2つの小さなパターンを合計するとわずか2です。第2のコストセットでは LEA4 のコストを1に変更するだけで、選択が反転します。DPの「最適」は、パターンセットとコスト定義と一緒に理解する必要があります。これは、命令が最も速いという前提を立ててから、選択器がそれを選ぶべきだと逆算してはならないことを示しています。

この小さなモデルは、レジスタ結果という1つの状態のみを保持しています。もし定数4が即値としてパターンに参加できる場合と、先にレジスタにロードされる場合の両方があれば、それぞれ別々に記録する必要があります。即値形式のコストは0かもしれませんが、レジスタのみを受け付ける親パターンはそれを直接消費できません。定数の実体化に必要な命令を追加する必要があり、部分木の最小値を無条件に加算してはいけません。

カバリングが大きいほど、必ずしも安価になるとは限らないか？

再帰式では、同じ結果形式を満たす完全な候補を比較する必要があります。ここでは、葉のレジスタコストを0と定め、命令数とCPUサイクルを混同しないよう、3つの合法なカバリングのみを比較します。LEAのコストを変更しても、木自体は変化しませんが、最小コストの方案は変わる可能性があります。より一般的な選択器では、reg、imm、memory などの結果形式ごとに別々に記録する必要があり、部分木の最小値を無条件に再利用することはできません。

$$C(n,r)=\underset{p\Rightarrow (n,r)}{\min }\left(w(p)+\sum _{(c,r_c)\in \mathrm{inputs}(p)}C(c,r_c)\right)$$

DAGと副作用：木モデルの外での作業

実際のIRには共有値がよくあります。xが2つの式で使用されている場合、DAGを2つの木にコピーすると計算が重複する可能性があります。もし重複するのがメモリアクセスや例外を発生させる可能性のある操作の場合、合法性はセマンティクスに依存します。複数の結果を返す命令も、複数のIR結果に対応する必要があります。

ロード、ストア、volatile、atomic、および呼び出しの間には、任意に変更できない依存関係があります。通常のloadを算術命令に折りたたむ場合、アクセス回数、実行パス、メモリセマンティクスが依然として合法であることを保証する必要があります。Atomic操作は、ターゲットに特定のビット幅の命令がないからといって、通常の読み書きに分解してはいけません。

合法化：まず、ターゲットがサポートできる能力で表現できるようにする

ターゲットが特定の整数幅、ベクトル型、または算術操作をサポートしていない場合、拡張、分割、他の操作への降格、またはランタイム補助関数の呼び出しが行われます。例えば、広域整数の加算は、下位ビットの加算とキャリー伝播に分割できます。メモリ分割の場合、エンディアン、アライメント、アトミック性を考慮する必要があります。

型合法化と操作合法化は互いに新たな機会や要求を生むことがあり、バックエンドはしばしば複数のマージと降格段階を持ちます。LLVMのSelectionDAGとGlobalISelは、異なる表現と段階の構成を提供しており、SelectionDAGを単に「産業用のグローバル最適DP」と呼ぶべきではありません。LLVMコード生成、GlobalISel

広域整数の分割：上下の半分を単に加えるだけでは不十分

2つの32ビットワードで64ビット符号なし整数を表します：下位 a_lo と上位 a_hi。下位和が32ビットを超えるとキャリーが発生し、それは上位計算に入らなければなりません。以下のモデルは mod 2^64 加法セマンティクスを選択しています。ソース言語でオーバーフローチェックが要求される場合、最終的なキャリーまたは対応するオーバーフロー条件を生成して処理する必要があります。

mask32, mask64 = (1 << 32) - 1, (1 << 64) - 1


def add64_split(a, b):
    low_sum = (a & mask32) + (b & mask32)
    low, carry = low_sum & mask32, low_sum >> 32
    high = ((a >> 32) + (b >> 32) + carry) & mask32
    return (high << 32) | low


values = (0, 1, mask32, 1 << 32, mask64)
for a in values:
    for b in values:
        assert add64_split(a, b) == (a + b) & mask64
assert add64_split(mask32, 1) == 1 << 32

最後のアサートは最も見落としがちな境界ケースです：下位半分が全1から0に変わるとき、上位半分は1を加算する必要があります。キャリーチェーンをサポートするターゲットでは、ADD/ADC などの命令を選択できます。他のターゲットでは、比較によってキャリーを生成し、その後加算を行うことがあります。合法化は必要なセマンティクスを提供しますが、具体的な命令シーケンスはターゲットの能力によって決定されます。

ここで分割されているのは純粋なレジスタ算術であり、64ビットのアトミック加算を2つの通常の32ビットストアとして実装できることを意味しません。後者の操作は、他のスレッドから観察可能なアトミック性も担っており、通常はターゲットのアトミックシーケンスまたはランタイムサポートが必要です。LLVM Legalizer

広域加算を2つに分割する場合、キャリーはどこへ行くべきか？

下位和は、「残る下位ビット」と「上位に送られるキャリー」に一意に分割できます。ビット幅を2つの8ビットに縮小すると、この分解は数値テーブルで直接検証できます。意図的に下位キャリーの列を省いて反例を構成することは、2番目の合法な実装ではありません。最終的な上位キャリーを破棄できるかどうかは、このモデルで明確に選択された mod 2¹⁶ セマンティクスによって決定されます。

$$a_l+b_l=2^{8}c+l,0\le l<2^8,h=(a_h+b_h+c)\mathrm{mod}{2}^8$$

レジスタ割り当ておよびスケジューリングとの連携

x86のいくつかの操作には入力と出力のバインディングがあり、除算などの命令は暗黙的に固定レジスタを使用します。命令選択時に仮想レジスタを使用する場合でも、これらのハードウェア制約を無視することはできません。

複雑な命令を1つ選ぶと命令数は減りますが、クリティカルパスのレイテンシが増加する可能性があります。計算を早期に行うことでレイテンシを隠せますが、値のアクティブ範囲が延長され、スパイル（メモリへの退避）を引き起こす可能性があります。後続のレジスタ割り当てで挿入されるload/store命令は、最終的なパフォーマンスを変更します。したがって、局所的なパターンコストは推定値に過ぎず、実際のプロセッサ時間に対する完全な証明ではありません。

観測可能なコンパイル実験

unsigned load_element(const unsigned *a, unsigned long i) {
    return a[i + 2];
}

clang -O2 -S -masm=intel load_element.c -o load_element.s

一般的なデータレイアウトを採用するx86-64 Linuxターゲットでは、アドレス内のスケール4とディスプレースメント8がロード命令にマージされているかどうかを観察できます。要素型、アクセス形式、またはターゲットアーキテクチャを変更して生成結果を比較すると、選択とターゲット能力の関係が見えてきます。アセンブリの具体的な書式はバージョンやオプションによって変化するため、唯一の答えとしてハードコーディングすべきではありません。

チェックリスト

選択が妥当かどうかを確認するには、次の項目を順に確認します：セマンティクスの同等性、エンコーディングの合法性、入力出力レジスタ制約、共有値と副作用、コスト目標、およびレジスタ割り当て後の最終結果。

関連セクション：レジスタ割り当て、ターゲットコードとABI。

参考文献

• LLVM Target-Independent Code Generator。
• LLVM GlobalISel。

キーワード: 命令選択, 木のカバリング, DAG, マキシマルマンチ, BURS, 合法化, アドレッシングモード, コストモデル