関数の中で a + b を 2 回書いたなら、コンパイラには 1 回だけ計算してほしいはずです。それが Global Value Numbering — LLVM の GVN パス — の約束であり、何を扱えるかを見始めると驚くほど強力です。同じオペランドの 2 つの add 命令？統合。同じポインタへの store の後の load？ロードをストアされた値で置き換え。ある制御フロー経路には存在するが別経路では「部分的に冗長」な計算？必要な場所に巻き上げて重複を削除。

この最後のケース — 部分冗長 — で GVN は単純なハッシュコンシングをやめて 部分冗長除去 (Partial Redundancy Elimination, PRE) を始めます。この記事は両方を追います: 値番号付けのコア、ロード転送のレイヤ、そして部分冗長を完全冗長に変えるための補償コードを挿入する PRE ロジックです。

行番号は全て llvm/lib/Transforms/Scalar/GVN.cpp のもの。ヘッダは llvm/include/llvm/Transforms/Scalar/GVN.h。

パート 1: 値番号付け

基本的なアイデアは単純です。関数内の各命令に 値番号 が割り当てられます — 同じ値番号を持つ 2 つの命令は同じ値を計算することが保証される整数です。同じ値番号の 2 つの命令が見つかり、片方が他方を支配していれば、支配される側を削除し、その使用を支配する側で置き換えられます。

メカニズムはハッシュコンシングされた式テーブルです。GVN は Expression 構造体を定義します（GVN.cpp:140-171）:

struct llvm::GVNPass::Expression {
  uint32_t Opcode;
  bool Commutative = false;
  Type *Ty = nullptr;
  SmallVector<uint32_t, 4> VarArgs;

  bool operator==(const Expression &Other) const { ... }
  friend hash_code hash_value(const Expression &Value) { ... }
};

注目: オペランドは値ではなく値番号として格納されます。これがスキームを推移的にする点です。%x = add i32 %a, %b が値番号 5 を得て、後で %y = add i32 %a, %b が現れたら、両方の %a と %b の値番号を探し、式 (Add, [VN(a), VN(b)]) を作り、ハッシュし、既に VN 5 でテーブルにあると分かり、%y も値番号 5 を持つと結論します。

ルックアップまたは追加のルーチンは lookupOrAdd（GVN.cpp:650+）:

uint32_t GVNPass::ValueTable::lookupOrAdd(Value *V) {
  DenseMap<Value *, uint32_t>::iterator VI = ValueNumbering.find(V);
  if (VI != ValueNumbering.end())
    return VI->second;

  auto *I = dyn_cast<Instruction>(V);
  if (!I) {
    ValueNumbering[V] = NextValueNumber;
    return NextValueNumber++;
  }

  Expression Exp = createExpr(I);
  uint32_t E = assignExpNewValueNum(Exp).first;
  ValueNumbering[V] = E;
  return E;
}

オペランドを通じた再帰が威力の源です。次のようなコードを考えてください:

%t1 = add i32 %a, %b
%t2 = mul i32 %t1, 2
%t3 = add i32 %a, %b
%t4 = mul i32 %t3, 2   ; %t2 と同じ!

%t3 は %t1 と同じ式にハッシュされるので、両方 VN 5 を得ます。すると %t4 の式は最初のオペランドに VN 5 を使い、%t2 と同じです。両方の mul が同じ VN を得ます。GVN は %t3 と %t4 を削除します。

リーダーテーブル

2 つの命令が同じ値番号を共有することを知るだけでは不十分です — どちらが他方を 支配 するかも知る必要があります。なぜなら置き換えに使えるのは支配する側だけだからです。それが LeaderTable（GVN.h:264-323）の役目です。各 VN を、その VN を持つ値のリストに各定義基本ブロックと共にマップします:

class LeaderMap {
  DenseMap<uint32_t, LeaderListNode> NumToLeaders;

  void insert(uint32_t N, Value *V, const BasicBlock *BB) { ... }
  iterator_range<leader_iterator> getLeaders(uint32_t N) { ... }
};

GVN が命令を以前の等価なもので置き換えたいとき、次のように問い合わせます:

Value *GVNPass::findLeader(const BasicBlock *BB, uint32_t Num) {
  auto Leaders = LeaderTable.getLeaders(Num);
  for (const auto &Entry : Leaders) {
    if (DT->dominates(Entry.BB, BB)) {
      return Entry.Val;
    }
  }
  return nullptr;
}

「値番号が Num で、定義ブロックが BB を支配する値をください」。1 つ存在すれば、BB 内の命令は置き換え可能です。

パート 2: 冗長ロード除去

値番号付けだけでは算術を扱えます。ロードはより難しい、値がメモリ状態に依存するためです — ポインタオペランドが同一の 2 つの load 命令は、間にストアがあれば同じ値を返すとは限りません。

GVN は processLoad（GVN.cpp:2161-2213）でロードを特別扱いします:

bool GVNPass::processLoad(LoadInst *L) {
  if (!MD) return false;

  MemDepResult Dep = MD->getDependency(L);

  if (Dep.isNonLocal())
    return processNonLocalLoad(L);

  auto AV = AnalyzeLoadAvailability(L, Dep, L->getPointerOperand());
  if (!AV) return false;

  Value *AvailableValue = AV->MaterializeAdjustedValue(L, L);
  L->replaceAllUsesWith(AvailableValue);
  salvageAndRemoveInstruction(L);
  ++NumGVNLoad;
  return true;
}

ここの仕組みは MemoryDependenceAnalysis（新しい経路では MemorySSA）です。「このロードが依存する最も近いメモリ操作は？」に答えます。依存先が同じアドレスへのストアなら、ロードを直接転送できます:

; Before
store i32 42, ptr %p
%x = load i32, ptr %p

; GVN 後
store i32 42, ptr %p
%x = ... (値 42 を直接使う)

AnalyzeLoadAvailability（GVN.cpp:1331-1471）は共通ケースを処理します:

3 番目のケースが関数を 100 行以上にする理由です: オフセットを算出し、エンディアンを処理し、正しい抽出コードを生成する必要があります。

パート 3: 部分冗長除去

ここから面白くなります。次を考えます:

entry:
  %a = ...
  %b = ...
  br i1 %cond, label %then, label %else

then:
  %x = add i32 %a, %b
  ...
  br label %merge

else:
  ; ここには add なし
  br label %merge

merge:
  %y = add i32 %a, %b     ; 部分冗長!

merge の add は then 経路では冗長（既に計算済み）ですが、else 経路では冗長ではない（そこでは計算されない）。だから単に削除はできません。しかし、add を else に巻き上げて merge で完全に利用可能にし、merge の冗長な add を phi で除去する、ということは できます。

それが PRE です。出力はこうなります:

entry:
  br i1 %cond, label %then, label %else

then:
  %x = add i32 %a, %b
  br label %merge

else:
  %x.pre = add i32 %a, %b  ; 挿入
  br label %merge

merge:
  %y = phi i32 [ %x, %then ], [ %x.pre, %else ]

then 経路で 2 つではなく各経路で 1 回の計算。ホットパスの実効命令数が減り、phi はタダです。

スカラー用 PRE

スカラー版は performScalarPRE（GVN.cpp:2942-3106）。コードの主な形:

bool GVNPass::performScalarPRE(Instruction *CurInst) {
  uint32_t ValNo = VN.lookup(CurInst);

  unsigned NumWith = 0;
  unsigned NumWithout = 0;
  BasicBlock *PREPred = nullptr;

  for (BasicBlock *P : predecessors(CurrentBlock)) {
    uint32_t TValNo = VN.phiTranslate(P, CurrentBlock, ValNo, *this);
    Value *PredV = findLeader(P, TValNo);

    if (!PredV) {
      PREPred = P;
      ++NumWithout;
    } else {
      ++NumWith;
    }
  }

  if (NumWithout > 1 || NumWith == 0)
    return false;

  if (NumWithout != 0) {
    PREInstr = CurInst->clone();
    performScalarPREInsertion(PREInstr, PREPred, CurrentBlock, ValNo);
  }

  PHINode *Phi = PHINode::Create(CurInst->getType(), PredMap.size(), ...);
  for (auto &[V, BB] : PredMap) {
    if (V) Phi->addIncoming(V, BB);
    else   Phi->addIncoming(PREInstr, PREPred);
  }

  CurInst->replaceAllUsesWith(Phi);
  removeInstruction(CurInst);
  return true;
}

追っていくと: 現在のブロックの各先行ブロックに対し、計算しようとしている値が既にそこで利用可能か（findLeader 経由で）チェック。ちょうど 1 つの先行が欠けていれば、そこが補償を挿入する場所です。2 つ以上が欠けていれば PRE は諦めます — ヒューリスティックは「2 箇所以上には挿入しない」。各挿入が収益的なのは、ほとんどの経路が既に計算している場合だけだからです。

phiTranslate の呼び出しは微妙です: 先行ブロック P から現在のブロックに渡るとき、phi ノードであるオペランドは P の incoming 値で置き換える必要があります。これにより PRE は phi 境界をまたいで動作します。

ロード用 PRE

ロード PRE はより野心的です、「欠けている」値が算術オペレーションではなくロードだからです。次を考えます:

block1:
  br i1 %C, label %block2, label %block3

block2:
  br label %block4

block3:
  store i32 0, ptr %p
  br label %block4

block4:
  %PRE = load i32, ptr %p

block3 経路では、ロードが何を返すか分かっています: 0（ストアされた値）。block2 経路では分かりません — そこにはストアがありません。だから block2 に load を挿入して phi で統合します。

ロード PRE 後:

block2:
  %pre.pre = load i32, ptr %p   ; 挿入
  br label %block4

block3:
  store i32 0, ptr %p
  br label %block4

block4:
  %PRE = phi i32 [ 0, %block3 ], [ %pre.pre, %block2 ]

block4 の元のロードは消えました。両経路は値を高々 1 回計算し、phi がマージをタダで行います。

実装は PerformLoadPRE（GVN.cpp:1659-1907）で、スカラー PRE よりかなり長いです。次をする必要があるからです:

  1. 各先行ブロックをチェック — ロード値はそこで利用可能か（ストア経由、先行ロード経由、など）?
  2. 利用可能でない先行ブロックには、補償ロードを挿入。
  3. phi を通るポインタ変換を扱う（ロードのアドレスが phi に依存するなら、各 incoming 経路でアドレスが違う）。
  4. マージする phi ノードを構築して配線。
  5. MemorySSA が生きていれば更新。

クリティカルエッジ

ときに「値を欠いている」先行ブロックが クリティカルエッジ 上にあります — 複数の後続ブロックを持つブロックから、複数の先行ブロックを持つブロックへのエッジです。ソースブロックにコードを挿入することはできません、そのソースには計算を必要としない他の後続ブロックがあるからです。そして宛先に挿入することもできません、そこが削除したい場所だからです。

解決策はクリティカルエッジを分割すること: 両者の間に新しいブロックを挿入し、そこに補償コードを置く。splitCriticalEdges（GVN.cpp:3137-3149）は薄いラッパーです:

BasicBlock *GVNPass::splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ) {
  BasicBlock *BB = SplitCriticalEdge(
      Pred, Succ,
      CriticalEdgeSplittingOptions(DT, LI, MSSAU)
          .unsetPreserveLoopSimplify());

  if (BB) {
    if (MD)
      MD->invalidateCachedPredecessors();
    InvalidBlockRPONumbers = true;
  }
  return BB;
}

分割後、PRE が挿入しようとしていた「先行ブロック」は実際には新しい中間ブロックで、構造上ちょうど 1 つの後続 — 宛先 — を持ちます。綺麗な挿入点です。

ロード PRE は明示的に必要性を検出します（GVN.cpp:1746-1774）:

if (Pred->getTerminator()->getNumSuccessors() != 1) {
  // クリティカルエッジ: この pred に巻き上げられるロードを探すか、分割。
  if (LoadInst *LI = findLoadToHoistIntoPred(Pred, LoadBB, Load))
    CriticalEdgePredAndLoad[Pred] = LI;
  else
    CriticalEdgePredSplit.push_back(Pred);
}

for (BasicBlock *OrigPred : CriticalEdgePredSplit) {
  BasicBlock *NewPred = splitCriticalEdges(OrigPred, LoadBB);
  PredLoads[NewPred] = nullptr;
}

最初の試みは、pred の他の後続の中から巻き上げ可能なロードを探すこと（一種の「共有部分をシンクする」プレイ）。それが失敗したら、クリティカルエッジ分割にフォールバック。

まとめると

GVN パスのトップレベルループは iterateOnFunction（GVN.cpp:3173）。各基本ブロックを歩き、各命令について次を試します:

  1. 単純な値番号付け。 リーダーテーブルで調べる。支配する等価物があれば置き換えて削除。
  2. ロード転送。 ロードなら、processLoad にストアまたは先行ロードが値を提供するか問い合わせ。
  3. PRE。 命令がスカラー PRE（全オペランドが利用可能な二項演算）またはロード PRE の候補なら、補償コードの巻き上げを試みる。

プロセスは変化がなくなるまで反復します — 多くの LLVM パスと同様、GVN は不動点まで走ります。

シンプルな PRE トレース

llvm/test/Transforms/GVN/PRE/pre-basic-add.ll から:

; Before
entry:
  %0 = load i32, @H
  br i1 %cond, label %bb, label %bb1

bb:
  %3 = add i32 %0, 42
  store %3, @G
  br %bb1

bb1:
  %4 = add i32 %0, 42    ; 部分的: bb で行われ、entry->bb1 では行われない
  store %4, @H

GVN は %4 が %3 と同じ値番号を持つことに気づきます。bb1 の先行ブロックを歩くと:

NumWithout == 1 なので PRE は進みます。エッジ entry → bb1 をチェック: クリティカルエッジ（entry は 2 つの後続、bb1 は 2 つの pred）なので分割。分割ブロックに補償を挿入し、マージ phi を構築:

; PRE 後
entry:
  %0 = load i32, @H
  br i1 %cond, label %bb, label %entry.bb1_crit_edge

entry.bb1_crit_edge:
  %.pre = add i32 %0, 42     ; ここに挿入
  br %bb1

bb:
  %3 = add i32 %0, 42
  store %3, @G
  br %bb1

bb1:
  %.pre.phi = phi i32 [ %.pre, entry.bb1_crit_edge ], [ %3, bb ]
  store %.pre.phi, @H

各経路に 1 つの add、マージで安価な phi。元の %4 は消えました。

なぜこれが重要か

GVN は LLVM ミドルエンドで最も重労働をこなすものの一つです。-O2 コンパイルは全てこれを走らせ、行う変換 — 特にロード転送と PRE — はほぼ全ての他の最適化と相互作用します:

GVN.h のヘッダを読み、次に iterateOnFunction と processLoad、最後に performScalarPRE を読みましょう。注意深く読めば約 2 時間でパス全体の地図ができ上がり、フロントエンドの多くの手書き最適化が単に「いくつかカノニカライズして GVN に掃除させる」ものである理由が分かるはずです。

次に読むもの