LLVM IR を -O2 の前後で見て、「%z = add i32 %x, %x がどうやって %z = shl i32 %x, 1 になったのか」とか、「add i32 %n, 1; add i32 %prev, 1; ... の連鎖が単一の add に畳まれたのか」と疑問に思ったことがあるなら、答えは InstCombine です。パイプラインで最も走るパスの 1 つで、概念的に単純なことをします: 関数を歩き、パターンをマッチさせ、より安価なものに書き換える。

悪魔は詳細に宿ります。InstCombine は攻撃的でありながら無限ループを避け、数百のパターン特有の畳み込みをスパゲッティにならずに扱い、畳み込みが known-bits の性質に依存できるよう value tracking と統合する必要があります。この記事はそれぞれを追います。

行番号は llvm/lib/Transforms/InstCombine/ 下のファイルを指します。主ドライバは InstructionCombining.cpp、パターンライブラリは llvm/include/llvm/IR/PatternMatch.h。

冒頭のコメント

何より先に、InstructionCombining.cpp のファイルヘッダ（9-31 行目）を読みましょう:

// InstructionCombining - Combine instructions to form fewer, simple
// instructions. This pass does not modify the CFG. This pass is where
// algebraic simplification happens.
//
// This pass combines things like:
//    %Y = add i32 %X, 1
//    %Z = add i32 %Y, 1
// into:
//    %Z = add i32 %X, 2
//
// This is a simple worklist driven algorithm.

このコメントには重要な約束が 2 つあります:

  1. 「CFG を変更しない」。 GVN や LICM と違い、InstCombine は基本ブロックを追加/削除/再配線しません。命令をその場で書き換えるだけです。この性質こそが、何度も走らせても安全である理由です — 他のパスが CFG ベースの解析をやり直す必要がありません。

  2. 「ワークリスト駆動アルゴリズム」。 設計は古典的なワークリスト: 命令を取り出し、畳み込もうとし、成功すれば影響を受けた命令を戻す。このパターンはコンパイラのあちこちにありますが、InstCombine には理解する価値のあるひねりがいくつかあります。

メインループ

パスの中核は InstCombinerImpl::run（InstructionCombining.cpp:5763-5950）。骨組みに絞ると:

bool InstCombinerImpl::run() {
  while (!Worklist.isEmpty()) {
    while (Instruction *I = Worklist.popDeferred()) {
      if (isInstructionTriviallyDead(I, &TLI)) {
        eraseInstFromFunction(*I);
        ++NumDeadInst;
        continue;
      }
      Worklist.push(I);
    }

    Instruction *I = Worklist.removeOne();
    if (I == nullptr) continue;

    // ... visit(*I) ...
  }
}

「Deferred」と「メイン」のリストは説明が必要です。

2 つのキュー: Deferred と Worklist

InstructionWorklist（llvm/include/llvm/Transforms/Utils/InstructionWorklist.h:25-130）は 2 つの格納エリアを持ちます:

なぜ 2 つ？動機は順序付けです。1 回の畳み込み中、多くの命令に触れるかもしれません: 畳み込まれる命令、そのオペランド、ユーザー。もし全てが直接メインスタックに行くと、処理順序が予測不能になります。代わりに Deferred に行き、それがトップレベル反復間で制御された順序（逆順、そうすれば互いに FIFO で出てくる）で吐き出されます。

実用上これが意味するのは: 畳み込みが新しい命令を生成したとき、それ自身とそのユーザーの両方がワークリストに入る、ということです:

// run ループ内、畳み込み成功後
Worklist.pushUsersToWorkList(*Result);
Worklist.push(Result);

こうして畳み込みのチェインがきれいに伝播します: add (add X, 1) 1 を add X, 2 に畳むと、元の外側 add のユーザーは今 add X, 2 を見ていて、さらに組み合わさる機会を得ます。

逆ポストオーダーでの初期化

ワークリストは適当に埋められるわけではありません。prepareWorklist（InstructionCombining.cpp:6009-6140）は関数を 逆ポストオーダー で走査します:

for (BasicBlock *BB : RPOT) {
  // 命令を集め、定数畳み込みし、デッドエッジを除去
}

理由: オペランドが定数畳み込み・カノニカライズされた後に命令を処理したい。逆ポストオーダーは、各ブロックを、そこから到達可能なブロックより先に訪問します — つまり支配木の意味で def が use より先です。歩くにつれて定数が自然に伝播します。

書かれざる「正味の簡約」ルール

これが InstCombine の最重要不変条件で、ヘッダコメントで例によって文書化されています。全ての畳み込みは、命令数を 厳密に 減らすか、明らかに良いカノニカル形を生成するかでなければなりません — 単に等価な形同士を入れ替えるだけは決して許されません。

なぜ？2 つの可能な畳み込みを考えます:

もし InstCombine が両方を実装したら、永遠に振動します。一方の畳み込みが他方を取り消し、ワークリストは空になりません。解決策は、カノニカル形を選び、そちらに向かってだけ 畳むこと。

InstructionCombining.cpp の冒頭コメント（22-31 行目）はいくつかのカノニカライゼーションルールを列挙しています:

//    1. If a binary operator has a constant operand, it is moved to the RHS
//    2. Bitwise operators with constant operands are always grouped so that
//       shifts are performed first, then or's, then and's, then xor's.
//    3. Compare instructions are converted from <,>,<=,>= to ==,!= if possible
//    4. All cmp instructions on boolean values are replaced with logical ops
//    5. add X, X is represented as (X*2) => (X << 1)
//    6. Multiplies with a power-of-two constant argument are transformed into shifts.

これらのルールがパスの羅針盤です。新しい畳み込みを追加するなら、問う必要があります: それは命令数を減らすか？そうでないなら、カノニカル的に好ましい形を生成するか？どちらでもなければ追加できません。

PatternMatch: 宣言的 IR マッチング

InstCombine の畳み込みは PatternMatch.h — IR パターンを宣言的にマッチする C++ テンプレートライブラリ — に対して書かれます。こう書く代わりに:

if (auto *BO = dyn_cast<BinaryOperator>(V)) {
  if (BO->getOpcode() == Instruction::Neg) {
    Value *Inner = BO->getOperand(0);
    if (auto *Add = dyn_cast<BinaryOperator>(Inner)) {
      if (Add->getOpcode() == Instruction::Add) {
        // ...
      }
    }
  }
}

こう書きます:

Value *X, *Y;
if (match(V, m_Neg(m_Add(m_Value(X), m_Value(Y))))) {
  // X and Y are now bound to the add's operands
}

下地となるテンプレート機構は PatternMatch.h:1230-1277 にあります。BinaryOp_match は本質的に:

template <typename LHS_t, typename RHS_t, unsigned Opcode,
          bool Commutable = false>
struct BinaryOp_match {
  LHS_t L;
  RHS_t R;

  template <typename OpTy> inline bool match(unsigned Opc, OpTy *V) const {
    if (V->getValueID() == Value::InstructionVal + Opc) {
      auto *I = cast<BinaryOperator>(V);
      return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
             (Commutable && L.match(I->getOperand(1)) &&
              R.match(I->getOperand(0)));
    }
    return false;
  }
};

そして m_Add は単なる便利ファクトリです（PatternMatch.h:1256-1277）:

template <typename LHS, typename RHS>
inline BinaryOp_match<LHS, RHS, Instruction::Add> m_Add(const LHS &L,
                                                        const RHS &R) {
  return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R);
}

こうしたマッチャが何百も存在します: m_Value, m_ConstantInt, m_APInt, m_Specific, m_OneUse, m_Neg, m_Not, m_Select, m_c_Add（可換版）などなど。組み合わせると、畳み込みは実装している数学的恒等式のように読めます。

実際の畳み込みを詳しく読む

InstCombineAddSub.cpp:1583-1602 の visitAdd の断片:

Value *A, *B;
if (match(LHS, m_Neg(m_Value(A)))) {
  // -A + -B --> -(A + B)
  if (match(RHS, m_Neg(m_Value(B))))
    return BinaryOperator::CreateNeg(Builder.CreateAdd(A, B));

  // -A + B --> B - A
  auto *Sub = BinaryOperator::CreateSub(RHS, A);
  auto *OB0 = cast<OverflowingBinaryOperator>(LHS);
  Sub->setHasNoSignedWrap(I.hasNoSignedWrap() && OB0->hasNoSignedWrap());
  return Sub;
}

// A + -B  -->  A - B
if (match(RHS, m_Neg(m_Value(B)))) {
  auto *Sub = BinaryOperator::CreateSub(LHS, B);
  // ...
  return Sub;
}

上から下に読むと:

setHasNoSignedWrap のビットに注目: InstCombine は畳み込みをまたいでオーバーフローフラグを保存します。元の add が nsw で元の否定もオーバーフローできなかったなら、新しい sub は nsw フラグを継承します。これは整数ラップを推論する下流パスにとって重要な、注意深い詳細レベルの仕事です。

ComputeKnownBits: 前提条件を持つ畳み込み

一部の畳み込みは、値のビットについて何かを証明できる場合にのみ有効です。InstCombine はこれに ValueTracking ユーティリティを使います。

InstCombineAddSub.cpp:954-960 の例:

// X has no high-bits set above an xor mask なら:
// add (xor X, LowMaskC), C --> sub (LowMaskC + C), X
if (C2->isMask()) {
  KnownBits LHSKnown = computeKnownBits(X, &Add);
  if ((*C2 | LHSKnown.Zero).isAllOnes())
    return BinaryOperator::CreateSub(ConstantInt::get(Ty, *C2 + *C), X);
}

畳み込み add (xor X, MASK), C → sub (MASK+C), X が合法なのは、X の（マスク上の）高ビットが証明可能にゼロである場合のみです。そうでなければ xor がマスク外のビットを反転させる可能性があり、算術が一致しません。

computeKnownBits は Zero（ゼロと判明しているビット）と One（1 と判明しているビット）を含む KnownBits 構造体を返します。チェック (*C2 | LHSKnown.Zero).isAllOnes() は: 「マスクのビットと known-zero ビットを合わせると全ビットをカバーするか？」と問います。そうなら X のマスク外のビットはセットされ得ず、畳み込みは安全です。

他の value-tracking 関数も同様に使われます: isKnownNonZero, ComputeNumSignBits, MaskedValueIsZero。全て、IR が前提条件を保証するとき InstCombine がより積極的な畳み込みを適用するための前提チェックです。

DCE はワークリスト内で生きる

InstCombine はインラインのデッドコード除去を行います。3 箇所（InstructionCombining.cpp:5767-5776, 5784-5789, 5937-5942）:

// Deferred のドレイン開始時
if (isInstructionTriviallyDead(I, &TLI)) {
  eraseInstFromFunction(*I);
  ++NumDeadInst;
  continue;
}

// 命令を visit する前
if (isInstructionTriviallyDead(I, &TLI)) {
  eraseInstFromFunction(*I);
  ++NumDeadInst;
  continue;
}

// combine 後、Result 自身がデッドになった場合

「自明にデッド」とは、命令がユーザーを持たず副作用もないことを意味します。ロード、ストア、呼び出し、volatile 演算は決して自明にはデッドになりません。add, and, gep などは候補です。

インライン DCE の利点は、畳み込みが 1 命令を削除/置換した後、そのオペランドがユーザーを失ってデッドになり得ることです。すぐに削除することで、後続のワークリスト反復は消えかけているものを畳み込もうとする時間を無駄にしません。

コードシンク（オプション）

-instcombine-code-sinking（InstructionCombining.cpp:5794-5862）の下、InstCombine はシンク先がより小さなスコープの場合、命令をユーザーに近づける — シンクする — ことも試みます。これは更なる畳み込みの機会を露出させます。シンクされた命令は通常、より狭いブロック集合から見え、そこでは定数がより具体的でパターンがマッチしやすくなります。

代表的なテストケース

llvm/test/Transforms/InstCombine/add.ll より:

; Test 8: disjoint masks
define i32 @test8(i32 %A, i32 %B) {
  %A1 = and i32 %A, 7
  %B1 = and i32 %B, 128
  %C = add i32 %A1, %B1
  ret i32 %C
}

InstCombine 後:

define i32 @test8(i32 %A, i32 %B) {
  %A1 = and i32 %A, 7
  %B1 = and i32 %B, 128
  %C = or disjoint i32 %A1, %B1
  ret i32 %C
}

何が起きたか: (A & 7) + (B & 128) — 7 & 128 == 0 なので 2 つの値は重なるビットを持ち得ない。2 つのオペランドが互いに素のビットパターンを持つとき、加算はビット単位 or と等価です。畳み込みは add を or で置き換え、その or を disjoint と注釈します（オペランドが共有ビットを持たないと下流パスが知るよう）。

命令数は変わりませんが、新しい形はカノニカル（disjoint なら OR が好まれる）で、下流パスにとって推論しやすい — 桁上がりを伴う可能性のある算術ではなく、純粋なビットレベル操作になりました。

同じファイルからのもう一つの例:

; Test 6: 定数畳み込み + 強度削減
define i32 @test6(i32 %A) {
  %B = mul i32 7, %A
  %C = add i32 %B, %A   ; 7*A + A = 8*A
  ret i32 %C
}

; InstCombine 後
define i32 @test6(i32 %A) {
  %C = shl i32 %A, 3    ; 8*A = A << 3
  ret i32 %C
}

連続する 2 つの畳み込み:

  1. 7*A + A = (7+1)*A = 8*A（分配則パターン、mul+add を 1 つの mul に畳む）
  2. mul A, 8 で 8 は 2 のべき乗 → shl A, 3（強度削減）

3 命令が 1 命令になり、結果のシフトはほとんどのアーキテクチャで安価です。

アーキテクチャまとめ

入力関数
   ↓
prepareWorklist (RPOT 走査、定数畳み込み、初期 DCE)
   ↓
メインループ:
   Worklist から命令を取り出す
      ↓
   自明にデッドなら DCE
      ↓
   必要に応じてユーザー近くへシンク
      ↓
   visit する (visitAdd, visitAnd, visitLoad などへディスパッチ)
      ↓
   各 visitor は PatternMatch + KnownBits で畳み込みを探す
      ↓
   畳み込まれた場合:
      - ユーザーを Worklist に戻す
      - 新しい Result を Worklist に push
      - 古い命令を削除
   Worklist が空になるまで繰り返し
   ↓
外側の不動点チェック: 変化があれば反復。

なぜ InstCombine が特別か

他のどの LLVM パスよりも、InstCombine はカノニカライザです。他のパスはその出力に依存します:

だから InstCombine を見て「この畳み込みは自明に見える」と思ったら — 個別では実際そうです。しかし数千の小さなカノニカライゼーションの累積効果で、ミドルエンドの残りを書くのが格段に簡単になります。各パスは入力がカノニカル形であると仮定でき、つまり各パスは書くケースが少なくなります。

これが InstCombine が標準パイプラインで複数回走る理由でもあります: インライン化後、SROA 後、ループアンロール後など。これらの変換はまだカノニカルでない IR を生成するので、InstCombine は次の重量級パスが走る前に再び掃除のチャンスを得ます。

次に読むもの