最近の記事 3 つは MemorySSA に大きく依存していました — TBAA の記事は暗黙に使い、MemCpyOpt と GVN の記事はほぼ毎ページ言及していました。この記事はそれ専用です。モダンな LLVM パスが「この呼び出しとそのロードの間で同じメモリに書き込むストアは？」のような問いに安価に答えられる理由を理解したいなら、MemorySSA を理解したくなるはずです。

ここでの行番号は全て llvm/lib/Analysis/MemorySSA.cpp と llvm/include/llvm/Analysis/MemorySSA.h のもの。テストケースは llvm/test/Analysis/MemorySSA/ から取ります。

MemorySSA が解く問題

通常の SSA は値のデータフローグラフを与えてくれます。%y = add i32 %x, 1 を見れば、%x を定義した命令が直ちにわかります — 定義はただ一つで、use-def リンクがそこにあります。

メモリには IR 上でそのような性質がありません。ロードには「私が読んでいる値を作ったストア」へのポインタは付いていません。関連するストアは関数内のどこか前方にあり得ます — phi の後ろ、呼び出しチェーンの後ろ、GEP を通じたエイリアシングの先、など。古典的には、そのストアを見つけるには介在する全メモリ操作を後方に歩いて、エイリアス解析に「これは私を clobber するか？」と毎回聞く必要があります。

その後方ウォークは正しいけれど高価です。数千のメモリ操作とサイクルを持つ関数では、それを問い合わせる全パスのボトルネックになりがちです。

MemorySSA はこれを解決するため、メモリ 自体の上に SSA 形の表現を構築します: 全てのメモリ接触命令は MemoryAccess ノードになり、マージ点は MemoryPhi ノードになり、キャッシュ付きウォーカーが「これを clobber するのは？」という問いに償却定数時間で答えます。

3 種類のノード

関数内の全てのメモリ接触命令は、次のいずれか 1 つだけを持ちます（MemorySSA.h:140-661）:

センチネル LiveOnEntryDef もあります — 「この関数が開始したとき存在したメモリ」を表す合成 MemoryDef です。関数内に可視の先行ストアがないロードはこれを指します。

ヘッダ（MemorySSA.h:20-53）を読むと、注釈付き IR の例があります:

define i32 @main() {
entry:
  ; 1 = MemoryDef(liveOnEntry)
  %call = call noalias i8* @_Znwm(i64 4)
  ; 2 = MemoryDef(1)
  store i32 5, i32* %0, align 4
  ; MemoryUse(2)
  %2 = load i32* %0, align 4
  ret i32 %2
}

; 1 = MemoryDef(...) や ; MemoryUse(...) のコメントは、-passes=print<memoryssa> が解析をダンプするときに IR に追加するものです。数字（1, 2）はバージョンで、括弧内のオペランドはこの MemoryAccess が依存するアクセスです。注釈を読むとこう分かります: 「ロードはストア（バージョン 2）を見る。それはアロケーション（バージョン 1）の後に来て、そのアロケーションは live-on-entry から始まった」。

構築はどう動くか

MemorySSA は通常の SSA と全く同じアルゴリズム — 支配境界とリネーム — を使って、個別の値ではなくメモリに適用して構築されます。エントリポイントは buildMemorySSA（MemorySSA.cpp:1529-1598）。

フェーズ 1: センチネルを作る（MemorySSA.cpp:1537-1538）:

LiveOnEntryDef.reset(new MemoryDef(StartingPoint.getContext(), nullptr,
                                   nullptr, &StartingPoint, NextID++));

LiveOnEntryDef は IR 上のどの命令にも付いていません。バージョン 0 の仮想 MemoryDef で、関数エントリ時点で可視のメモリ（引数、グローバル、先行呼び出し元で行われたアロケーション）を表します。

フェーズ 2: 命令をスキャン（MemorySSA.cpp:1546-1567）:

for (BasicBlock &B : Blocks) {
  for (Instruction &I : B) {
    MemoryUseOrDef *MUD = createNewAccess(&I, &BAA);
    if (!MUD) continue;
    Accesses->push_back(MUD);
    if (isa<MemoryDef>(MUD)) {
      DefiningBlocks.insert(&B);
    }
  }
}

各命令に「メモリに触れるか？」を問います。Yes なら MemoryUse か MemoryDef が作られます。少なくとも 1 つの MemoryDef を含むブロックは DefiningBlocks に集められます — フェーズ 3 で必要です。

フェーズ 3: MemoryPhi を配置（MemorySSA.cpp:1515-1526）。古典的な Cytron ら の SSA 配置アルゴリズムを使います: defining blocks の集合の反復支配境界（IDF）を計算し、IDF の各ブロックに phi を配置します。

void MemorySSA::placePHINodes(const SmallPtrSetImpl<BasicBlock *> &DefiningBlocks) {
  ForwardIDFCalculator IDFs(*DT);
  IDFs.setDefiningBlocks(DefiningBlocks);
  SmallVector<BasicBlock *, 32> IDFBlocks;
  IDFs.calculate(IDFBlocks);

  for (auto &BB : IDFBlocks)
    createMemoryPhi(BB);
}

これが「スパース SSA」の「スパース」たる所以です: CFG の全マージ点に MemoryPhi が入るわけではなく、2 つの異なるメモリ定義が到達し得るマージ点にだけ入ります。3 つの先行ブロックを持つブロックでも、全てが同じ MemoryDef を通るなら phi は不要です。

フェーズ 4: リネーム（MemorySSA.cpp:1570-1598）。標準の SSA リネームパスが支配木を歩き、各経路の「現在のメモリ定義」を保持します。各 MemoryUse で、そのアクセスの defining access を現在の def に設定。各 MemoryDef で現在の def を更新。MemoryPhi のオペランドは先行ブロックの現在の def から埋められます。

終了時には、全 MemoryUse は正確に 1 つの MemoryAccess（MemoryDef、MemoryPhi、または LiveOnEntryDef）を指します。各 MemoryDef は前に来るアクセスへの “defining access” ポインタを 1 つ持ちます。

でも “defining access” は clobber ではない

ここが長い間しみ込まなかった微妙な点です。MemoryUse の defining access は必ずしもそれを clobber するものではありません — それは単に def チェーン上の最新のメモリ操作です。

次を考えます:

; 1 = MemoryDef(liveOnEntry)
store i32 1, ptr %x
; 2 = MemoryDef(1)
store i32 2, ptr %y   ; %x とエイリアス? たぶんしない。
; MemoryUse(2)
%v = load i32, ptr %x

構築後、ロードの defining access は 2 — プログラム順で最新の MemoryDef です。しかし 2 のストアは %x ではなく %y に書きます。ロードの 真の clobber は 1 です。その真の clobber を見つけるのが ウォーカー の仕事です。

キャッシュ付き clobber ウォーカー

ウォーカーは CachingWalker（MemorySSA.cpp:1022-1063）です。メインエントリポイントは getClobberingMemoryAccess:

MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA,
                                        BatchAAResults &BAA) override {
  unsigned UpwardWalkLimit = MaxCheckLimit;
  return getClobberingMemoryAccess(MA, BAA, UpwardWalkLimit);
}

内部では defining-access チェーンを上方に歩き、各 MemoryDef でエイリアス解析に「あなたは実際に私のロケーションを clobber するか？」と問います。最初に yes と答えたものを返します。大まかに（MemorySSA.cpp:557-596）:

UpwardsWalkResult walkToPhiOrClobber(DefPath &Desc, ...) const {
  for (MemoryAccess *Current : def_chain(Desc.Last)) {
    if (auto *MD = dyn_cast<MemoryDef>(Current)) {
      if (!--*UpwardWalkLimit) return {Current, true};

      if (instructionClobbersQuery(MD, Desc.Loc, Query->Inst, *AA))
        return {MD, true};
    }
  }
  return {Desc.Last, false};
}

病的なウォークを防ぐため MaxCheckLimit（デフォルト 100）があります。ウォーカーが 100 ステップ以内に答えを見つけられなければ、保守的に返します。

ウォークが MemoryPhi に当たると、アルゴリズムは各 incoming 値で再帰し、各経路の clobber を見つけて結果を合成する必要があります。これが tryOptimizePhi（MemorySSA.cpp:771+）。全ての incoming 経路が同じ clobber で終わるなら、phi はショートサーキットされます — ウォーカーはその clobber を直接返し phi をスキップします。

キャッシュ部分。 MemoryDef の真の clobber は def 自身の「最適化済みアクセス」スロットに保存されます（MemorySSA.h:392-395）:

void setOptimized(MemoryAccess *MA) {
  setOperand(1, MA);
  OptimizedID = MA->getID();
}

次に同じ def についてウォーカーが問われると、キャッシュされた結果を直ちに返します。これがウォーカーを償却 O(1) にしているものです: 各 MemoryDef の clobber は多くクエリされても高々 1 回しか計算されません。

MemorySSA のプリント形式

注釈付きフォーマットはまさに opt -passes='print<memoryssa>' が出すものです。llvm/test/Analysis/MemorySSA/print-walker.ll より:

; 1 = MemoryDef(liveOnEntry)->liveOnEntry - clobbered by liveOnEntry
store i8 42, ptr %a1

; 2 = MemoryDef(1)->liveOnEntry - clobbered by liveOnEntry
store i8 42, ptr %a2

; MemoryUse(1) - clobbered by 1 = MemoryDef(liveOnEntry)->liveOnEntry
%l1 = load i8, ptr %a1

これらの行を読むと:

「def チェーン」（MemoryUse → defining access）と「clobber チェーン」（MemoryUse → ウォーカー結果）は 2 つの異なるもので、プリンタは両方を表示します。

小さな実例

llvm/test/Analysis/MemorySSA/function-clobber.ll より:

@g = external global i32
declare void @modifyG()

define i32 @foo(i1 %arg) {
; CHECK: MemoryUse(liveOnEntry)
; CHECK-NEXT: %1 = load i32
  %1 = load i32, ptr @g

; CHECK: 1 = MemoryDef(liveOnEntry)
; CHECK-NEXT: store i32 4
  store i32 4, ptr @g, align 4

; CHECK: 2 = MemoryDef(1)
; CHECK-NEXT: call void @modifyG()
  call void @modifyG()

; CHECK: MemoryUse(2)
; CHECK-NEXT: %2 = load i32
  %2 = load i32, ptr @g

  %3 = add i32 %2, %1
  ret i32 %3
}

追っていくと:

  1. 最初の load は関数内に先行する def がないので、defining access は liveOnEntry。その clobber も liveOnEntry — この関数内でまだ @g に書いたものはない。
  2. store は 1 = MemoryDef(liveOnEntry)。最初の def。
  3. @modifyG() への呼び出しは @g を含む任意のグローバルを変更し得る。2 = MemoryDef(1) として記録される。
  4. 2 番目の load は MemoryUse(2)。「このロードを clobber するのは？」と問うと、ウォーカーは 2 から開始し、「@modifyG() は @g に書く可能性があるか？」をチェック、エイリアス解析が yes と言うので、2 が返される。

「2 番目のロードは最初のロードと同じ値か？」と決めたい GVN のような最適化にとって、答えは: clobber が異なる（liveOnEntry と 2）ので no — そして GVN は正しく両ロードを残します。MemorySSA なしでは、GVN は 2 つのロード間の全命令を歩いて各々をエイリアスチェックせねばなりません。MemorySSA があれば 1 回のルックアップで済みます。

スパース設計の重要性

MemorySSA の 2 つの性質が立ち止まる価値があります:

スパースである。 100 万命令の関数でメモリに触れるのがその内 100 だけなら、MemorySSA は約 100 の MemoryUse/Def ノードとわずかな MemoryPhi を持ちます。メモリ操作にだけコストを払い、関数の残りには払いません。

キャッシュされる。 全 clobber クエリは開始ノードでメモ化されます。同じ関数で 100 万回クエリするパスは、最初のクエリのコストの約 10 倍、100 万倍ではなく、を払います。

これを古典的な代替 — 「各ロードに対して全命令を後方に歩き、各ステップでエイリアス解析に問う」 — と比べてください。最悪 O(N²) でキャッシュのストーリーはありません。MemCpyOpt、DSE、LICM、そして現代形の GVN のようなパスは、全てこのスケールで問い合わせ可能な MemorySSA に依存しています。ミドルエンドの基盤的インフラです。

次に読むもの

MemorySSA 自体を続けて読むなら、MemorySSA.h:9-83 のヘッダコメントは LLVM 内でも良く書かれたものの 1 つです — 動機とアルゴリズムの両方が書かれています。その後は:

MemorySSA を 使って いるところを見たければ、MemCpyOpt の記事 にいくつかの writtenBetween(MSSA, ...) 呼び出しがあり、そのセマンティクスがもう謎ではなくなっているはずです。それらはどれも内部では clobber ウォーカーのクエリです。