これまでのブログ記事のほとんどは LLVM のミドルエンド — IR 上で動く解析と最適化 — についてでした。この記事はバックエンドに踏み込みます。最適化器が終わると、コンパイラは IR をターゲット固有のコードジェネレータに渡します。バックエンドが最初にやることの 1 つが SelectionDAG を構築し、リーガライゼーションを開始することです。

「リーガライズする」とは: DAG には最初、最適化器がターゲットがサポートするかに関係なく自由に生成した型と操作が含まれています。32-bit ARM は 2 つの i64 をネイティブに乗算できません。AVX なしの x86 は v3i32 加算ができません。それらのノードは、ターゲットの命令セットが実際に表現できる列に書き換えなければなりません。それがリーガライゼーションの仕事で、2 つの大きなフェーズで行われます: まず型リーガライゼーション、次に操作リーガライゼーション。

この記事はガイド付きツアーです。関連ファイルは全て llvm/lib/CodeGen/SelectionDAG/ 下: LegalizeTypes.cpp, LegalizeIntegerTypes.cpp, LegalizeVectorTypes.cpp, LegalizeDAG.cpp。ターゲット側のセットアップは llvm/include/llvm/CodeGen/TargetLowering.h と各ターゲットの *ISelLowering.cpp にあります。

背景: SelectionDAG

リーガライゼーションの前、命令選択の最初のステップが既に DAG を構築済みで、各ノードは操作（ISD::ADD, ISD::LOAD, ISD::CALL, …）に対応し、各値は Machine Value Type (MVT) を持ちます: i32, i64, v4i32 等。DAG は論理的にソースが計算したいもので、ターゲットに近いけれどまだターゲット独立な形です。

しかしターゲットは全ての ISD::* オペコードを全ての MVT 組み合わせでサポートしているとは限りません。v4i32 上の ISD::MUL は SSE4.1 付き x86 ではサポートされますがそれ以前ではされません。i32 上の ISD::CTPOP はあるターゲットでは 1 命令、別のターゲットではビット操作列です。f16 上の ISD::FADD は、ネイティブな半精度を持たないハードウェアでは f32 操作に展開される必要があるかもしれません。

リーガライゼーションの仕事は、残る全ての操作をターゲットが選択可能なものに DAG を変換することです。

4 つのアクション

全ての (opcode, type) ペアはターゲット視点で リーガライゼーションアクション を持ちます。enum は TargetLowering.h:203-208:

enum LegalizeAction : uint8_t {
  Legal,      // The target natively supports this operation.
  Promote,    // This operation should be executed in a larger type.
  Expand,     // Try to expand this to other ops, otherwise use a libcall.
  LibCall,    // Don't try to expand this to other ops, always use a libcall.
  Custom      // Use the LowerOperation hook to implement custom lowering.
};

ターゲットはこれらのアクションを、TargetLowering コンストラクタで setOperationAction() を使って起動時に宣言します。例えば X86ISelLowering.cpp から:

X86TargetLowering::X86TargetLowering(const X86TargetMachine &TM,
                                     const X86Subtarget &STI)
    : TargetLowering(TM, STI), Subtarget(STI) {
  // X86 は i64 からの truncating store をサポートしない
  setTruncStoreAction(MVT::i64, MVT::i32, Expand);
  setTruncStoreAction(MVT::i64, MVT::i16, Expand);
  setTruncStoreAction(MVT::i64, MVT::i8,  Expand);

  setOperationAction(ISD::CLEAR_CACHE, MVT::Other, Expand);
  // ... 数百続く ...
}

事実上これはターゲットのハードウェアマニュアルを C++ に翻訳したものです。リーガライザはこれを読んで各ノードをどうするかを決めます。

フェーズ 1: 型リーガライゼーション

最初のフェーズは DAG 内の全値が リーガルな型 — ターゲットがレジスタ（または既知のレジスタ組み合わせ）に保持できる型 — を持つようにします。エントリポイントは DAGTypeLegalizer::run()（LegalizeTypes.cpp:200-294）:

for (unsigned i = 0, NumResults = N->getNumValues(); i < NumResults; ++i) {
  EVT ResultVT = N->getValueType(i);
  switch (getTypeAction(ResultVT)) {
  case TargetLowering::TypeLegal:
    break;
  case TargetLowering::TypePromoteInteger:
    PromoteIntegerResult(N, i);
    Changed = true;
    goto NodeDone;
  case TargetLowering::TypeExpandInteger:
    ExpandIntegerResult(N, i);
    Changed = true;
    goto NodeDone;
  case TargetLowering::TypeSplitVector:
    SplitVectorResult(N, i);
    Changed = true;
    goto NodeDone;
  case TargetLowering::TypeWidenVector:
    WidenVectorResult(N, i);
    Changed = true;
    goto NodeDone;
  // ... soften float, expand float, scalarize vector ...
  }
}

型アクションはいくつかのファミリに分かれます:

Promote — 小さな型がより大きなリーガル型になる。例: i1 → i8、またはワードサイズのレジスタしか持たないターゲットで i8 → i32。操作はより広い幅で実行され、結果は必要に応じて（暗黙または明示的に）切り詰められます。

Expand — 大きな整数が断片に分割される。例: 32-bit ターゲットで i64 → 2 つの i32。DAG は再構成され、各 i64 値が i32 のペア (Lo, Hi) として表現されます。

Split vector — 広すぎるベクトルがより細い 2 つのベクトルになる。例: v8i32 → 2 つの v4i32。

Widen vector — 小さすぎるベクトルが次のリーガルサイズまでパディングされる。例: v3i32 → v4i32、余ったレーンは undef。

Soften float — ターゲットが直接扱えない浮動小数点がその整数ビットパターンとして表現される（例: f16 → i16）。操作は compiler-rt 関数（__mulsf3 など）の呼び出しになります。

各アクションはオペコードでパターンマッチするディスパッチャを持ちます。PromoteIntegerResult が模範です（LegalizeIntegerTypes.cpp:42）:

void DAGTypeLegalizer::PromoteIntegerResult(SDNode *N, unsigned ResNo) {
  LLVM_DEBUG(dbgs() << "Promote integer result: "; N->dump(&DAG));
  SDValue Res = SDValue();

  if (CustomLowerNode(N, N->getValueType(ResNo), true)) {
    LLVM_DEBUG(dbgs() << "Node has been custom expanded, done\n");
    return;
  }

  switch (N->getOpcode()) {
  case ISD::BITCAST:     Res = PromoteIntRes_BITCAST(N); break;
  case ISD::BSWAP:       Res = PromoteIntRes_BSWAP(N); break;
  case ISD::CTPOP:       Res = PromoteIntRes_CTPOP_PARITY(N); break;
  case ISD::LOAD:        Res = PromoteIntRes_LOAD(cast<LoadSDNode>(N)); break;
  // ... 80+ opcodes ...
  }

  ReplaceNodeWith(N, Res);
}

オペコードごとに 1 つのヘルパーがあり、それぞれがその操作を昇格された型で書き換えます。add を昇格するとは、両オペランドをゼロ拡張または符号拡張し、より広い幅で add を行い、結果が「本当は」狭いと覚えることです。

例: 32-bit ターゲット上の i64 乗算

ExpandIntegerResult（LegalizeIntegerTypes.cpp:3048）は expand ケースを、元の値の下位半分と上位半分という 2 つの SDValue を返して処理します:

void DAGTypeLegalizer::ExpandIntegerResult(SDNode *N, unsigned ResNo) {
  SDValue Lo, Hi;
  Lo = Hi = SDValue();

  switch (N->getOpcode()) {
  case ISD::ADD:
  case ISD::SUB: ExpandIntRes_ADDSUB(N, Lo, Hi); break;
  case ISD::MUL:         ExpandIntRes_MUL(N, Lo, Hi); break;
  // ...
  }
}

乗算の具体的な実装（LegalizeIntegerTypes.cpp:4528）:

void DAGTypeLegalizer::ExpandIntRes_MUL(SDNode *N,
                                        SDValue &Lo, SDValue &Hi) {
  EVT VT = N->getValueType(0);
  EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);

  SDValue LL, LH, RL, RH;
  GetExpandedInteger(N->getOperand(0), LL, LH);
  GetExpandedInteger(N->getOperand(1), RL, RH);

  if (TLI.expandMUL(N, Lo, Hi, NVT, DAG, ..., LL, LH, RL, RH))
    return;

  RTLIB::Libcall LC = RTLIB::getMUL(VT);
  // __muldi3 への libcall にフォールスルー
}

概念的に、i64 × i64 → i64 乗算は、2 つの i32 半分 L = (LL, LH) と R = (RL, RH) に分解すると次のようになります:

result = LL*RL + (LL*RH + LH*RL) << 32
       + (LH*RH) << 64     // 上位 64 ビット、64-bit 結果では破棄

各部分積は i32×i32 操作（ターゲット上でリーガル）です。3 つの 32-bit 乗算といくつかの加算が単一の i64 乗算を置き換えます。リーガライザはその算術の DAG を生成し、結果は i32 SDValue のペアです。呼び出しコンテキストが後で「この乗算の i64 結果」を読むとき、両半分を透過的に読みます。

ターゲットが適切な i32 操作すら持たないなら — 非常に小さなチップでは — expandMUL は false を返し、libcall にフォールスルーします。

ベクトル操作

ベクトルリーガライゼーションは精神的に似ていますがより手が込んでいます。SplitVectorResult（LegalizeVectorTypes.cpp:1248）は広すぎるベクトルを半分に分割します:

void DAGTypeLegalizer::SplitVectorResult(SDNode *N, unsigned ResNo) {
  switch (N->getOpcode()) {
  case ISD::ADD:
  case ISD::SUB:
    // オペランドを再帰的に分割し、各半分で op を実行
    break;
  case ISD::EXTRACT_VECTOR_ELT:
    R = SplitVecRes_EXTRACT_VECTOR_ELT(N);
    break;
  // ... 60+ opcodes
  }
}

WidenVectorResult（LegalizeVectorTypes.cpp:4955）は小さすぎるベクトルを次のリーガルサイズまでパディングします、通常は未使用レーンに poison で。ほとんどの算術では、余ったレーンは最初の N レーンしか使わないので正しさに影響しません。

フェーズ 2: 操作リーガライゼーション

全値がリーガル型を持ったら、フェーズ 2 は全ての 操作 が実際に実行できることを確保します。それが SelectionDAGLegalize::Legalize()（LegalizeDAG.cpp:985-1401）:

void SelectionDAGLegalize::LegalizeOp(SDNode *Node) {
  // ... このノードのアクションを決定 ...

  switch (Action) {
  case TargetLowering::Legal:
    LLVM_DEBUG(dbgs() << "Legal node: nothing to do\n");
    return;

  case TargetLowering::Custom:
    LLVM_DEBUG(dbgs() << "Trying custom legalization\n");
    if (SDValue Res = TLI.LowerOperation(SDValue(Node, 0), DAG)) {
      ReplaceNode(SDValue(Node, 0), Res);
      return;
    }
    [[fallthrough]];

  case TargetLowering::Expand:
    if (ExpandNode(Node))
      return;
    [[fallthrough]];

  case TargetLowering::Promote:
    PromoteNode(Node);
    return;

  case TargetLowering::LibCall:
    ConvertNodeToLibcall(Node);
    return;
  }
}

switch のフォールスルーが重要です: Custom はカスタムハンドラが拒否したら Expand にフォールスルー。Expand はターゲット独立な展開が利用できなければ Promote にフォールスルー。LibCall はランタイム呼び出しを生成。最もターゲット固有なものから最もターゲット汎用なものへの滝です。

ExpandNode 汎用展開

ExpandNode（LegalizeDAG.cpp:3236-3400+）は多くのオペコードについてターゲット独立な実装を持ちます。例えば ISD::CTPOP（population count、つまり「セットされているビット数」）:

case ISD::CTPOP:
  if ((Tmp1 = TLI.expandCTPOP(Node, DAG)))
    Results.push_back(Tmp1);
  break;

TargetLowering.cpp の expandCTPOP は古典的なビット操作列を実装しています:

x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
x = x * 0x01010101 >> 24;   // 全バイトを上位バイトに合計

つまり popcnt 命令がないターゲットでは、単一の ISD::CTPOP ノードがシフト、マスク、加算の連鎖になります。全てリーガルで、基本的な整数算術を持つ任意のターゲットでサポートされています。

カスタムローワリング

setOperationAction(..., ..., Custom) が宣言されているとき、リーガライザは TargetLowering::LowerOperation() を呼びます。各ターゲットはこれを大きな switch として実装します:

SDValue X86TargetLowering::LowerOperation(SDValue Op, SelectionDAG &DAG) const {
  switch (Op.getOpcode()) {
  // ... 200+ cases ...
  case ISD::MUL:
    return LowerMUL(Op, Subtarget, DAG);
  // ...
  }
}

x86 の LowerMUL は 100 行を超えるロジックで、オペランドの型、定数、サブターゲット機能に応じて IMUL、LEA ベースの定数乗算パターン、SSE/AVX 列、libcall のいずれかを選択します。ここにターゲットが手でチューンしたローワリングルールをエンコードします。

Libcall

展開できないものもあります — ライブラリ関数を呼ぶ必要がある。典型例は FPU のないチップでの浮動小数点操作です。ConvertNodeToLibcall（LegalizeDAG.cpp:4954）がランタイム呼び出しを生成します:

// サポートされない FP の場合: 両オペランドで __addsf3（compiler-rt から）を呼び、
// 結果を同じ幅の整数として受け取り、それを f32 として扱う。

各ターゲットはどのランタイムライブラリを期待するかを設定します。compiler-rt, libgcc, MSVCRT が通常の関数を提供します。

実例: x86 での v3i32 add

小さなものを追ってみましょう。LLVM IR:

define <3 x i32> @add3(<3 x i32> %a, <3 x i32> %b) {
  %r = add <3 x i32> %a, %b
  ret <3 x i32> %r
}

命令選択の初期 DAG 構築後、操作は v3i32 型上の ISD::ADD です。x86 はネイティブな v3i32 を持ちません — SSE ベクトル型は 128 ビット（v4i32）、256（v8i32）等の幅です。

フェーズ 1（型）。 x86 の TargetLowering は v3i32 を TypeWidenVector として宣言。リーガライザは WidenVectorResult を呼び、次をします:

フェーズ 2（操作）。 今ノードは v4i32 上の ISD::ADD。SSE2 付き x86 はこれにネイティブな paddd 命令を持つので、アクションは Legal。何もしない。

結果 DAG: 1 つのリーガルな v4i32 add、周囲にパッド/トリム操作。命令選択はこれを PADDD xmm, xmm にマッチします。

この関数の DAG レベルでの「前」と「後」はだいたいこんな感じ:

リーガライゼーション前:
  ISD::ADD (v3i32, v3i32) -> v3i32

型リーガライゼーション後:
  ISD::CONCAT_VECTORS pad %a to v4i32
  ISD::CONCAT_VECTORS pad %b to v4i32
  ISD::ADD (v4i32, v4i32) -> v4i32
  ISD::EXTRACT_SUBVECTOR back to v3i32 (または最初の 3 レーンのみを使用)

操作リーガライゼーション後:
  (更なる変更なし — v4i32 ADD はリーガル)

より複雑なケース — 32-bit ターゲット上の v3i64 を想像 — では、両フェーズが大きな仕事をします: 型リーガライゼーションは各レーンを (Lo, Hi) に分割し、次にベクトルを widen するかもしれず、操作リーガライゼーションは乗算を libcall に展開するかもしれません。パイプラインは任意の非リーガル連鎖を扱えるほど反復的です。

なぜこのアーキテクチャが機能するか

2 フェーズ設計 — 型が先、操作が後 — が正しい分割なのは:

このアーキテクチャのコストは、SelectionDAG バックエンドが大きいことです。LegalizeDAG.cpp と仲間合わせて数万行。しかしスケールします: 新ターゲットを追加するのは、TargetLowering のフックを実装して setOperationAction 呼び出しの束を書くことがほとんどで、汎用リーガライゼーション機構は全て無料で手に入ります。

次に来るもの

リーガライゼーション後、DAG はリーガル型とリーガル操作のみを持ちます。次のフェーズは 命令選択本体: DAG をターゲットの命令定義（TableGen で書かれる）に対してパターンマッチし、実際のマシン命令を発行。次にスケジューリング、レジスタ割り当て、エミッション。

しかしリーガライゼーションこそ、最適化器の抽象的な「プログラムが計算するもの」ビューと、スケジューラの具体的な「このチップが実行できるもの」ビューを繋ぐものです。これを理解することが LLVM のバックエンドを読む鍵を開きます。

次に読むもの