KnownBits: LLVM 最適化器の半分が頼るビット単位の抽象ドメイン（日本語版）

LLVM の最適化パスを読む時間を費やすと、同じパターンに何度も出くわします: 畳み込みが次のようなもので始まる

KnownBits Known = computeKnownBits(X, DL, &AC, CxtI, &DT);
if ((SomeMask | Known.Zero).isAllOnes())
  return rewriteThing(...);

そして畳み込みが合法なのは Known が教えてくれたおかげです。KnownBits 構造体は LLVM の最もよく使われる内部抽象の 1 つです。InstCombine、InstructionSimplify、SelectionDAG の demanded-bits 解析、GlobalISel、DemandedBits、Attributor、そして他多くのパスに現れます。これは、実際に実行することなくビットレベルで整数値を推論するコンパイラの方法です。

この記事は KnownBits が何か、どう計算されるか、そして — 面白い部分 — 最適化器の残りがどう使うかを追います。いくつかのファイルから多くの実コードを引用します。InstCombine の記事 を読んでいれば、computeKnownBits が一度呼ばれるのを既に見ています。ここでは引いて全体像をお見せしたい。

行番号は全て /data/dev/llvm-project/ 下のファイルのもの。

構造体

llvm/include/llvm/Support/KnownBits.h、24 行目:

struct KnownBits {
  APInt Zero;
  APInt One;
  // ...
};

追跡される値と同じビット幅の 2 つの APInt。各ビット位置 i について:

• Zero[i] == 1 はビット i が 証明可能にゼロ
• One[i] == 1 はビット i が 証明可能に 1
• 両方 0 はビット i が 不明 — どちらでもあり得る
• 両方 1 は 衝突 — 値が矛盾、つまり到達不能

中心的な不変条件は Zero.intersects(One) == false。畳み込みがこの不変条件が違反されると証明したら、決して実行できないプログラム片を発見したことになります — それ自体が有用なシグナルで、構造体は hasConflict() として公開します（KnownBits.h:51）:

bool hasConflict() const { return Zero.intersects(One); }

InstructionSimplify は実際これを使って poison に畳み込みます — 後述。

公開 API

KnownBits.h は全体をざっと見る価値がありますが、いたるところで見る操作はこれら:

クエリ。 全て定数時間:

bool isZero()                 // 全ビットが証明可能にゼロ
bool isAllOnes()              // 全ビットが証明可能に 1
bool isConstant()             // 各ビットが既知
APInt getConstant()           // 定数を取得 (isConstant() をアサート)
bool isNegative()             // 符号ビットが 1 と判明
bool isNonNegative()          // 符号ビットが 0 と判明
APInt getMinValue()           // 不明ビットを 0 と仮定 → 可能な最小値
APInt getMaxValue()           // 不明ビットを 1 と仮定 → 可能な最大値
unsigned countMinTrailingZeros()   // 保証された末尾ゼロ
unsigned countMinLeadingZeros()    // 保証された先頭ゼロ
unsigned countMinPopulation()      // 保証された popcount (下限)

ミューテータ:

void setAllZero()             // 値はゼロ
void setAllOnes()             // 値は全 1（符号なし最大）
void makeConstant(const APInt &C)
void makeNegative()           // 符号ビットを 1 と判明にセット

2 つの KnownBits を合成する — 2 つの値、2 つのプログラム地点で、既知ビット集合を持つ。マージする:

// 両値が全既知ビットで一致する必要 → 交差
KnownBits intersectWith(const KnownBits &RHS) const;

// どちらの値も可能 → 和集合
KnownBits unionWith(const KnownBits &RHS) const;

intersectWith は phi ノードに使うもの — マージは各 incoming 値と整合する必要があります。unionWith は「これは X か Y のいずれか」を計算するためのもの — 例: ダイヤモンド if-then-else 後に値が何であり得るかを追跡。

静的セマンティック演算子。 これらは IR 操作のセマンティクスを 抽象ドメイン上で 実装します:

static KnownBits add(const KnownBits &LHS, const KnownBits &RHS, bool NSW, bool NUW);
static KnownBits sub(const KnownBits &LHS, const KnownBits &RHS, bool NSW, bool NUW);
static KnownBits mul(const KnownBits &LHS, const KnownBits &RHS, bool NUW);
static KnownBits shl(const KnownBits &LHS, const KnownBits &RHS, bool NUW, bool NSW, bool ShAmtNonZero);
static KnownBits lshr(const KnownBits &LHS, const KnownBits &RHS, ...);
static KnownBits ashr(...);

これが重要な部分です。KnownBits::shl(X, C) は「これらの既知ビットを持つ値を、これらの既知ビットを持つシフト量だけ左シフトしたら、結果の既知ビットはこうなる」と言います。全ての微妙さを扱います: シフト量自身が不明のとき、結果は可能な各シフトからの可能性を合成します。

述語版もあります — KnownBits::ult, KnownBits::sgt など — std::optional<bool> を返す。両オペランドが示す範囲が指定の比較で完全に互いに素なら、答えは決定的な true か false。重なっていれば nullopt（不明）。

computeKnownBits は実際にどう計算するか

計算は llvm/lib/Analysis/ValueTracking.cpp にあります。トップレベルエントリ（ValueTracking.cpp:141-150）:

void llvm::computeKnownBits(const Value *V, KnownBits &Known,
                            const SimplifyQuery &Q, unsigned Depth) {
  auto *FVTy = dyn_cast<FixedVectorType>(V->getType());
  APInt DemandedElts =
      FVTy ? APInt::getAllOnes(FVTy->getNumElements()) : APInt(1, 1);
  ::computeKnownBits(V, DemandedElts, Known, Q, Depth);
}

SimplifyQuery は DataLayout、AssumptionCache、DominatorTree、コンテキスト命令を運びます。それらを合わせて、解析が「この特定のプログラム地点で V について何が分かっているか」に答えられるようになります。同じ SSA 値が CFG の異なる地点で異なる KnownBits を持ち得ます（下の @llvm.assume セクション参照）。

計算の心臓は computeKnownBitsFromOperator（ValueTracking.cpp:1403-1702）で、命令オペコードに対する大きな switch です。アイデアを固めるためのいくつかのケース:

Instruction::Add（ValueTracking.cpp:1673-1678）:

case Instruction::Add: {
  bool NSW = Q.IIQ.hasNoSignedWrap(cast<OverflowingBinaryOperator>(I));
  bool NUW = Q.IIQ.hasNoUnsignedWrap(cast<OverflowingBinaryOperator>(I));
  computeKnownBitsAddSub(true, I->getOperand(0), I->getOperand(1), NSW, NUW,
                         DemandedElts, Known, Known2, Q, Depth);
  break;
}

両オペランドの KnownBits を再帰的に計算し、セマンティック演算子 KnownBits::computeForAddSub を呼ぶ。NSW / NUW フラグは結果を鋭くする — add がオーバーフローしないなら、より厳しい境界を導出できます。

Instruction::Shl（ValueTracking.cpp:1627-1640）:

case Instruction::Shl: {
  bool NUW = Q.IIQ.hasNoUnsignedWrap(cast<OverflowingBinaryOperator>(I));
  bool NSW = Q.IIQ.hasNoSignedWrap(cast<OverflowingBinaryOperator>(I));
  auto KF = [NUW, NSW](const KnownBits &KnownVal, const KnownBits &KnownAmt,
                       bool ShAmtNonZero) {
    return KnownBits::shl(KnownVal, KnownAmt, NUW, NSW, ShAmtNonZero);
  };
  computeKnownBitsFromShiftOperator(I, DemandedElts, Known, Known2, Q, Depth, KF);
  const APInt *C;
  if (match(I->getOperand(0), m_APInt(C)))
    Known.Zero.setLowBits(C->countr_zero());
  break;
}

シフト量自身が不明であり得ます。ヘルパーがそれを扱います。下の追加 — 「シフトされるものが定数なら末尾ゼロビットを直接セットできる」 — は多くの小さな機会主義的洗練の 1 つです。

範囲メタデータ付きの Instruction::Load（ValueTracking.cpp:1413-1416）:

case Instruction::Load:
  if (MDNode *MD =
          Q.IIQ.getMetadata(cast<LoadInst>(I), LLVMContext::MD_range))
    computeKnownBitsFromRangeMetadata(*MD, Known);
  break;

ロードが例えば !0 = !{i32 0, i32 256} と言う !range !0 メタデータを持つとき、computeKnownBitsFromRangeMetadata（ValueTracking.cpp:580-607）は既知ビットを直接抽出します:

unsigned CommonPrefixBits =
    (Range.getUnsignedMax() ^ Range.getUnsignedMin()).countl_zero();
APInt Mask = APInt::getHighBitsSet(BitWidth, CommonPrefixBits);
APInt UnsignedMax = Range.getUnsignedMax().zextOrTrunc(BitWidth);
Known.One &= UnsignedMax & Mask;
Known.Zero &= ~UnsignedMax & Mask;

[0, 256) について: 0 と 255 の共通プレフィックスは先頭 24 ゼロビット。だから高位 24 ビットはゼロと判明。下位 8 ビットは値が何であれ — 不明。

全 IR オペコードがケースを持ちます。80 以上あり、それぞれが同じ種類の仕事をします: 再帰的にオペランドビットを計算、セマンティック演算子を実行、返す。強制された深さ制限（デフォルトで MaxRecursionDepth = 6）が境界を保ちます。

コンテキスト: 分岐と @llvm.assume

同じ SSA 値が異なるプログラム地点で異なる既知ビットを持ち得ます — 支配する分岐や @llvm.assume 呼び出しが可能性を狭められるから。これは computeKnownBitsFromContext（ValueTracking.cpp:1049-1074）が処理します:

void llvm::computeKnownBitsFromContext(const Value *V, KnownBits &Known,
                                       const SimplifyQuery &Q, unsigned Depth) {
  if (Q.CC && Q.CC->AffectedValues.contains(V))
    computeKnownBitsFromCond(V, Q.CC->Cond, Known, Q, Q.CC->Invert, Depth);

  if (Q.DC && Q.DT) {
    for (CondBrInst *BI : Q.DC->conditionsFor(V)) {
      BasicBlockEdge Edge0(BI->getParent(), BI->getSuccessor(0));
      if (Q.DT->dominates(Edge0, Q.CxtI->getParent()))
        computeKnownBitsFromCond(V, BI->getCondition(), Known, Q,
                                 /*Invert*/ false, Depth);
      // ... Invert=true での Edge1 も同様
    }
  }

  if (!Q.AC)
    return;
  for (AssumptionCache::ResultElem &Elem : Q.AC->assumptionsFor(V)) {
    // ... @llvm.assume intrinsic を処理
  }
}

ビットを絞り込むコンテキストの 3 つのソース:

1. 「cond コンテキスト」（Q.CC） — 現在の簡略化が条件分岐のアームの中で起きている。分岐条件を使って絞り込み。
2. 支配する分岐 — 条件が V に言及する支配チェーン内の全条件分岐を反復。どちら側にいるかに基づいて洗練。
3. 仮定 — @llvm.assume(cond) は「ここから先 cond が成り立つと仮定」と等価。AssumptionCache がこれらを値でインデックス。

再帰的な computeKnownBitsFromCond（ValueTracking.cpp:1006-1047）は複合条件を and/or 木で扱い、最終的に ICmpInst などで底を打ちます。だから if ((x & 15) == 0) { ...; use(x); } のような分岐は then アーム内の computeKnownBits(x) に下位 4 ビットがゼロだと分からせます。

アラインメント仮定は特別扱いを受けます。ValueTracking.cpp:1084-1100 より:

if (RetainedKnowledge RK = getKnowledgeFromBundle(...)) {
  if (RK.WasOn == V && RK.AttrKind == Attribute::Alignment &&
      isPowerOf2_64(RK.ArgValue) &&
      isValidAssumeForContext(I, Q.CxtI, Q.DT, /*AllowEphemerals*/ true))
    Known.Zero.setLowBits(Log2_64(RK.ArgValue));
}

@llvm.assume(ptr align(64)) → アラインメント 64 → ポインタの下位 6 ビットがゼロと判明。これは KnownBits 表現にビットレベルの事実として直接差し込まれます。

このコンテキスト統合こそが @llvm.assume を単なるコンパイラ側コメントではなく有用な最適化ヒントにしているものです。assert(x < 256) を書いてアサート有効でコンパイルすると、その assertion は assume になり、それが KnownBits の事実になり、それが「x の高位 24 ビットはゼロ」を利用できる全下流畳み込みを解き放ちます。

姉妹解析

KnownBits と並んで見るいくつかのいとこ:

MaskedValueIsZero（ValueTracking.cpp:318-323）:

bool llvm::MaskedValueIsZero(const Value *V, const APInt &Mask,
                             const SimplifyQuery &SQ, unsigned Depth) {
  KnownBits Known(Mask.getBitWidth());
  computeKnownBits(V, Known, SQ, Depth);
  return Mask.isSubsetOf(Known.Zero);
}

「これらの特定のビットはゼロと判明か？」の便利ラッパー。常に使われます。

isKnownNonZero(V) — KnownBits が V != 0 を示せば true を返す。Known.One にビットがセットされているか、値がそれ以外の構造的再帰解析で証明可能に非ゼロ。

isKnownToBeAPowerOfTwo(V) — ちょうど 1 ビットがセットされていれば true。除算をシフトに置換したい InstCombine パターンが使用。

ComputeNumSignBits（ValueTracking.cpp:4238） — 異なる 表現。各ビットのゼロ/1 状態を追跡する代わりに、「先頭ビットのうちいくつが符号ビットと等しいと保証されるか？」を問います。i17 に収まると判明している値に対しては、ComputeNumSignBits は 15 を返します（上位 15 ビットが符号ビットと一致）。これは粗い表現ですが、多くの算術パターン — sign-extend-in-register、ashr 畳み込み — には安くて十分です。KnownBits と NumSignBits は補完的で、ほとんどのパスは両方を問い合わせます。

消費者 1: InstCombine

ここが自分の読書で最初に computeKnownBits が呼ばれるのを見た場所です。ほとんどの InstCombine 畳み込みは KnownBits の前提条件でガードされます。3 つの実例。

add (xor X, MASK), C → sub (MASK + C), X

InstCombineAddSub.cpp:954-960 より:

if (C2->isMask()) {
  KnownBits LHSKnown = computeKnownBits(X, &Add);
  if ((*C2 | LHSKnown.Zero).isAllOnes())
    return BinaryOperator::CreateSub(ConstantInt::get(Ty, *C2 + *C), X);
}

入力:

%xor = xor i32 %X, 15   ; C2 = 15 = 0b1111 (マスク)
%add = add i32 %xor, 2  ; C = 2

出力（KnownBits チェックが通れば）:

%sub = sub i32 17, %X

なぜチェックが必須か。 恒等式 (X xor mask) + C == (mask + C) - X が成り立つのは、X が mask 外にビットをセットしていないときのみ。X がより高位ビットをセットしていたら、xor はそれらをそのまま残しますが、右辺の減算は完全に異なる結果を与えます。チェック (*C2 | LHSKnown.Zero).isAllOnes() はまさにそれを問います: 全ビットが C2 内にある（xor がそれを反転）か X でゼロと判明している（何も変わらない）。このチェックを通れば代数的恒等式は有効です。

KnownBits なしでは、InstCombine は全入力で保守的にこの畳み込みをスキップせねばなりません。KnownBits があれば、前提条件を証明できるときに適用されます。

高位ビットがゼロのとき or X, C → xor X, C

InstCombineAndOrXor.cpp:2536-2544 より:

if (match(Op0, m_APInt(Op0C))) {
  if (Op0C->isMask()) {
    KnownBits RHSKnown = llvm::computeKnownBits(
        Op1, SQ.getWithInstruction(&I).getWithoutDomCondCache());
    if ((*Op0C | RHSKnown.Zero).isAllOnes())
      return BinaryOperator::CreateXor(Op1, Op0);
  }
}

入力:

%or = or i32 %Y, 255

出力（チェックが通れば）:

%xor = xor i32 %Y, 255

なぜ。 or X, MASK と xor X, MASK が同じ結果を生むのは、MASK の全ビットが X で既にゼロのとき かつそのときに限り。xor 形が好まれるのは、カノニカルだから、そして xor が後続の畳み込みにとって良い代数的性質を持つから（自己逆元、xor X, MASK, MASK == X）。

ペアになった 2 のべき乗ビットテスト

InstCombineAndOrXor.cpp:708-718 より:

if (Mask & Mask_NotAllZeros &&
    isKnownToBeAPowerOfTwo(B, /*OrZero=*/false, Q) &&
    isKnownToBeAPowerOfTwo(D, /*OrZero=*/false, Q)) {
  Value *Mask = Builder.CreateOr(B, D);
  Value *Masked = Builder.CreateAnd(A, Mask);
  return Builder.CreateICmp(NewCC, Masked, Mask);
}

入力:

%ab = and i32 %A, %B             ; B は 2 のべき乗と判明
%cmpb = icmp ne i32 %ab, 0
%ad = and i32 %A, %D             ; D は 2 のべき乗と判明
%cmpd = icmp ne i32 %ad, 0
%result = and i1 %cmpb, %cmpd    ; 両ビットがセット?

出力:

%Mask = or i32 %B, %D
%Masked = and i32 %A, %Mask
%result = icmp eq i32 %Masked, %Mask

5 つではなく 3 つの命令。なぜ KnownBits ガードが重要か: 変換は B と D の各々が単一ビットであることを要求します。もし B に 2 つのビットがセットされていたら、(A & B) != 0 は「これら 2 つのビットの少なくとも 1 つが A でセット」を意味しますが、書き換えは「B の両ビットが A でセット」をチェックします。isKnownToBeAPowerOfTwo なしでは保証がありません。

消費者 2: InstructionSimplify

InstructionSimplify.cpp は「新しい命令を作らずに、これがより単純な値に帰着するか証明しようとする」パス。シフト畳み込みに KnownBits を大量に使います。InstructionSimplify.cpp:1340-1365 より:

KnownBits KnownAmt = computeKnownBits(Op1, Q);
if (KnownAmt.getMinValue().uge(KnownAmt.getBitWidth()))
  return PoisonValue::get(Op0->getType());

unsigned NumValidShiftBits = Log2_32_Ceil(KnownAmt.getBitWidth());
if (KnownAmt.countMinTrailingZeros() >= NumValidShiftBits)
  return Op0;  // 0 によるシフトは恒等

if (IsNSW) {
  KnownBits KnownVal = computeKnownBits(Op0, Q);
  KnownBits KnownShl = KnownBits::shl(KnownVal, KnownAmt);
  if (KnownShl.hasConflict())
    return PoisonValue::get(Op0->getType());
}

KnownBits から抽出される 3 つの異なる事実:

1. シフト量がビット幅以上と保証される → poison。 シフトしすぎは未定義動作、結果は poison。
2. シフト量の下位ビットが全てゼロと判明 → 0 によるシフト、恒等畳み込み。
3. nsw shl が矛盾するビットを作るだろう → hasConflict() → poison。

最後のが面白い。nsw は「符号付きラップなし」を約束 — 符号ビットが予期せず反転し得ない。解析が符号ビットが 0 と 1 の両方でなければならないと証明できれば（例: 元の符号ビットがシフトアウトされ次のビットが 1 でなければならないから）、nsw の約束は全可能な入力で違反され、操作全体が poison です。hasConflict() がこれを直接表出させます。

消費者 3: SelectionDAG と SimplifyDemandedBits

バックエンドは Value ではなく SDNode 上で動作する KnownBits の独自パラレルユニバースを持ちます。同じ表現、異なる IR。llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp:3340-3350 より:

KnownBits SelectionDAG::computeKnownBits(SDValue Op, const APInt &DemandedElts,
                                         unsigned Depth) const {
  unsigned BitWidth = Op.getScalarValueSizeInBits();
  KnownBits Known(BitWidth);

  if (auto OptAPInt = Op->bitcastToAPInt()) {
    return KnownBits::makeConstant(*std::move(OptAPInt));
  }

  if (Depth >= MaxRecursionDepth)
    return Known;
  // ... SDNode オペコードでディスパッチ ...
}

並列インフラ、同じ原理。ターゲットは TargetLowering::computeKnownBitsForTargetNode 経由で独自ケースを追加でき、ターゲット固有命令について事実を表現できます（例: AArch64 の「この命令は常にゼロ拡張された値を生成する」）。

本当に興味深いバックエンド消費者は SimplifyDemandedBits — KnownBits の双対です。Known bits は値が何を 生成する かを教え、demanded bits はそのユーザーが 実際に何を見る かを教えます。ユーザーが下位 16 ビットだけ読むなら、生成命令はもっと生成できても、その 16 ビットだけ生成するよう絞り込めます。TargetLowering.cpp:658-705 より:

bool TargetLowering::SimplifyDemandedBits(SDValue Op, const APInt &DemandedBits,
                                          DAGCombinerInfo &DCI) const {
  SelectionDAG &DAG = DCI.DAG;
  TargetLoweringOpt TLO(DAG, !DCI.isBeforeLegalize(),
                        !DCI.isBeforeLegalizeOps());
  KnownBits Known;

  bool Simplified = SimplifyDemandedBits(Op, DemandedBits, Known, TLO);
  if (Simplified) {
    DCI.AddToWorklist(Op.getNode());
    DCI.CommitTargetLoweringOpt(TLO);
  }
  return Simplified;
}

完全な SimplifyDemandedBits 実装はオペコードディスパッチで数百行です。各 SDNode 種類について、出力の需要に応じてどの入力ビットが必要かを知り、入力を再帰的に簡略化し、結果の KnownBits を使ってノードが置換可能と証明します。

古典的な例: trunc i32 %x to i16 は %x の下位 16 ビットだけを需要する。%x が 2 つの値の add で、それらの値の高位 16 ビットがゼロと判明しているなら、add は i16 に絞り込める。demand-bits 解析がこの書き換えを駆動し、KnownBits が安全と証明します。

GlobalISel — 新しいバックエンドコード生成フレームワーク — は Machine IR 上で動く同じインフラを GISelKnownBits（llvm/lib/CodeGen/GlobalISel/GISelKnownBits.cpp）に持ちます。

消費者 4: DemandedBits 解析

ミドルエンドは自身の demanded-bits パスを持ちます: llvm/lib/Analysis/DemandedBits.cpp。ヘッダコメント（1-19 行目）が私が見た中で最も明快な説明です:

// This pass implements a demanded bits analysis. A demanded bit is one that
// contributes to a result; bits that are not demanded can be either zero or
// one without affecting control or data flow. For example in this sequence:
//
//   %1 = add i32 %x, %y
//   %2 = trunc i32 %1 to i16
//
// Only the lowest 16 bits of %1 are demanded; the rest are removed by the trunc.

核で KnownBits を使います（DemandedBits.cpp:52-78）:

auto ComputeKnownBits =
    [&](unsigned BitWidth, const Value *V1, const Value *V2) {
      if (KnownBitsComputed) return;
      KnownBitsComputed = true;

      Known = KnownBits(BitWidth);
      computeKnownBits(V1, Known, DL, &AC, UserI, &DT);

      if (V2) {
        Known2 = KnownBits(BitWidth);
        computeKnownBits(V2, Known2, DL, &AC, UserI, &DT);
      }
    };

DemandedBits は KnownBits クエリをキャッシュし、各オペランドについてどのビットが実際に最終結果に伝播するかを決めるのに使います。下流パス（BDCE、具体的には「bit-tracking DCE」）は DemandedBits を使って、結果が実際に観測されない命令を削除します。

消費者 5: ビットテストと整数絞り込み

InstCombine は MaskedValueIsZero を高価な等価物と安価な等価物の間で選ぶために大いに使います。1 つの例（InstCombineAddSub.cpp:974-978）:

if (ShAmt &&
    MaskedValueIsZero(X, APInt::getHighBitsSet(BitWidth, ShAmt), &Add)) {
  Constant *ShAmtC = ConstantInt::get(Ty, ShAmt);
  Value *NewShl = Builder.CreateShl(X, ShAmtC, "sext");
  return BinaryOperator::CreateAShr(NewShl, ShAmtC);
}

これは sign-extend-in-register の書き換え: X の高位 ShAmt ビットがゼロなら、符号拡張を ashr(shl(X, ShAmt), ShAmt) としてモデル化できます。そのパターンはカノニカルで、しばしば単一のハードウェア命令（x86 の MOVSX 種類など）にマップされます。

パターン: 次を見たら:

if (MaskedValueIsZero(V, SomeMask, Q)) { ... }

実際に問うているのは「V の SomeMask 内のビットをゼロと仮定できるか？」。答えは「yes、KnownBits がこのプログラム地点でそれを証明すれば」。それ以外ではアドホックな証明が必要な性質に対する 1 行チェックです。

エンドツーエンド: KnownBits を通じた最適化のトレース

llvm/test/Transforms/InstCombine/all-bits-shift.ll のテストケースを歩いてみましょう。入力:

define signext i32 @main() {
  %a = load i32, ptr @a
  %cond = icmp eq i32 %a, 0
  %shift_amt = zext i1 %cond to i32   ; 0 or 1
  %shr1 = lshr i32 2072, %shift_amt
  %shr2 = lshr i32 %shr1, 7
  %and = and i32 %shr2, 1
  ret i32 %and
}

最適化器は %and が定数と証明したい。KnownBits 推論をトレース:

1. %shift_amt は zext i1 ... to i32。i1 の zext は高位 31 ビットがゼロと判明、低位ビットが不明。だから %shift_amt の KnownBits は: Zero = 0xFFFFFFFE, One = 0。
2. %shr1 = lshr 2072, %shift_amt。2072 = 0b100000011000。KnownBits::lshr(const, unknown_in_{0,1}) を適用:
   • 0 でシフト: 0b100000011000
   • 1 でシフト: 0b010000001100
   • 可能性の和集合: Zero = 0xFFFFF003, One = 0（いずれかの経路で 1 になり得るビットがある。常に 1 のビットはない）。
3. %shr2 = lshr %shr1, 7。KnownBits::lshr(step 2 の known, const 7)。ステップ 2 の高位ビットの下位 7 ビットが位置にシフト。どちらの経路でも値の上位ビットはゼロなので、7 右シフト後、高位ビットは確実にゼロ。下位ビットは… %shr1 のビット 7 以降に依存、ステップ 2 によればほとんどの位置でゼロと判明。結果は高位ビットゼロ、低位ビット不明。
4. %and = and %shr2, 1。KnownBits::and(shr2_known, 1_known)。ビット 0 について、両オペランドがビット 0 に潜在的にセットを持つ。ビット 1 以降について、1 の KnownBits は Zero = 0xFFFFFFFE。既知ゼロビットとの AND は既知ゼロを生成。

全て終わって: %and は高位 31 ビットゼロで低位ビットは… うーん、もっと注意深く見ると — シフトの連鎖後、%shr2 のビット 0 は両経路で 0（2072 » 7 = 16 = 0b10000 はビット 0 = 0、1036 » 7 = 8 = 0b1000 はビット 0 = 0）。だからビット 0 もゼロと判明。したがって %and は全 32 ビットがゼロと判明、つまり %and == 0。

最適化器は関数全体を ret i32 0 で置換します。

これが KnownBits インフラを持てば純粋に機械的になる種類の推論です。各ステップは 1 つの KnownBits::someOp 呼び出し。抽象解釈を組み上げれば証明が落ちてきます。KnownBits なしだと、これを証明するには連鎖の各命令について手書きの特殊ケース推論が必要で — それこそ最適化器で書きたくないコードです。

なぜ KnownBits が正しい抽象か

評価に値する設計選択をいくつか:

格子である。 「全ビット不明」がトップ、「特定の定数」がボトム（衝突前の）。全操作は単調 — 入力情報が増えれば出力情報が減ることはない。これはまさに抽象解釈が必要とする形。

衝突がボトム。 Zero.intersects(One) のとき、値が矛盾していると、つまりそのコード地点が到達不能と証明しています。同じ KnownBits 構造体が「既知のデッドコード」をコストなしで自然にエンコードします。

きれいに合成できる。 静的演算子（KnownBits::add, ::shl など）は抽象ドメインの純粋関数。IR コンテキストを必要としない。自由に合成できます: KnownBits::add(KnownBits::shl(a, 2), b) で OK。これにより同じインフラを IR パス、SelectionDAG、GlobalISel から使うのが簡単になります。全て異なるメモリ内表現を持ちますが算術セマンティクスは同一です。

厳しいコスト上限を持つ。 computeKnownBits は深さ制限（デフォルト 6）を持ちます。それを超えると「全不明」を返します。これが退化した入力でも解析を境界付きに保ちます。

ドミネータ、assume、メタデータと統合される。 ビットを読む同じ呼び出しサイトが分岐条件、@llvm.assume、範囲メタデータ、アラインメントバンドルなどで豊かになります。ユーザーは「このプログラム地点で この値が持てるビット」を得る、ほぼ常に彼らが欲しかったものです。

なぜこんなに多くの消費者？

LLVM のほぼ全ての最適化は、あるレベルで「変換するためにこの値について十分証明できるか？」に帰着します。KnownBits はその問いに対する最も汎用的な答えの 1 つなので、あちこちに現れます。追った消費者の大まかな分類:

LLVM パスを読んでいてビットレベルに感じる前提条件チェック — 「でも高位ビットがゼロのときだけ」「でも 2 のべき乗のときだけ」「でもオーバーフローし得ないときだけ」 — を見たら、下に KnownBits クエリがある可能性が高いです。

次に読むもの

• 構造体のヘッダ（KnownBits.h）は短くコメントが良い。最初から最後まで読んでください。
• ValueTracking.cpp の大きなオペコード switch（computeKnownBitsFromOperator）は長いが定型的。12 ケースほど読めばスタイルを内面化できます。
• KnownBits の使用を見たい: InstCombineAddSub.cpp に興味深い使用が最も密集しています。foldAdd* や foldSub* と名の付いた各関数に少なくとも 1 つあります。
• @llvm.assume 統合は LangRef の「Intrinsic Functions」→「Intrinsics for Optimizations」の下でカバーされます。短くて読む価値あり。
• 以前の InstCombine の記事 では computeKnownBits の簡単な言及がありました。今は実際に何をするか分かりました。Attributor の記事 は手続き間属性推論に触れており、一部の抽象属性は単に「KnownBits、しかし関数境界を越えて拡張されたもの」です。

1 つ持ち帰るものがあるとすれば: LLVM のミドルエンドは、一次近似で、computeKnownBits を順番に尋ねるパスのパイプラインです。その関数が精密であるほど、各パスはよりよく機能します。それを拡張する — 新しいオペコードケースや新しいコンテキストソースを追加する — ことは、下流パスが気づかなくても全て恩恵を受ける、稀な変更の 1 つです。