MemorySSA

はじめに

MemorySSA は、さまざまなメモリー操作間の相互作用を安価に推論できる分析です。その目標は、ほとんどの（すべてではないにしても）ユースケースで MemoryDependenceAnalysis を置き換えることです。これは、非常に注意しない限り、MemoryDependenceAnalysis を使用すると、LLVM で簡単に二次時間のアルゴリズムになる可能性があるためです。さらに、MemorySSA には MemoryDependenceAnalysis ほど多くの恣意的な制限がないため、より良い結果が得られるはずです。MemorySSA の一般的な用途の1つは、何かが絶対に起こり得ないことを迅速に突き止めることです（たとえば、ループからの巻き上げが起こり得ない理由を推論するなど）。

大まかに言うと、MemorySSA の目標の1つは、メモリーのSSAベースの形式を、def-useとuse-defチェーンを完備して提供し、ユーザーがメモリー操作の可能性があるdefとuseをすばやく見つけられるようにすることです。また、メモリーの完全な状態に安価にバージョンを与え、それらのバージョンにメモリー操作を関連付ける方法と考えることもできます。

このドキュメントでは、MemorySSA の構造と、MemorySSA がどのように機能するかについての基本的な直感について説明します。

MemorySSAに関する論文（GCCでの実装方法に関する注釈付き）はこちらにあります。ただし、比較的古いです。この論文では複数のメモリーパーティションが参照されていますが、GCCは最終的に、現在LLVMにあるように、1つだけを使用するように変更しました。GCCと同様に、LLVMのMemorySSAはプロシージャ内です。

MemorySSAの構造

MemorySSAは仮想IRです。構築後、MemorySSA には、Instruction を MemoryAccess にマッピングする構造が含まれます。これは、MemorySSA のLLVM Instruction に相当するものです。

各 MemoryAccess は、次の3つのタイプのいずれかになります。

• MemoryDef

• MemoryPhi

• MemoryUse

MemoryDef は、メモリーを変更する可能性のある操作、または何らかの順序制約を導入する操作です。MemoryDef の例としては、store、関数呼び出し、acquire （以上）の順序付け付きの load、揮発性操作、メモリフェンスなどがあります。 MemoryDef は常にメモリー全体の新しいバージョンを導入し、新しいバージョンがベースとするメモリーのバージョンである単一の MemoryDef/MemoryPhi にリンクされます。これは、すべての Def を直接的または間接的に接続する単一の Def チェーンがあることを意味します。たとえば、

b = MemoryDef(a)
c = MemoryDef(b)
d = MemoryDef(c)

d は c と直接接続され、b と間接的に接続されます。これは、d が c または b または 両方を潜在的にクロバー（後述）することを意味します。これは、ウォーカーを使用しない場合、最初はすべての MemoryDef が他のすべての MemoryDef をクロバーすることを意味します。

MemoryPhi は PhiNode ですが、メモリー操作用です。任意の時点で、BasicBlock に流れ込む可能性のある2つ（またはそれ以上）の MemoryDef がある場合、ブロックの最上位の MemoryAccess は MemoryPhi になります。 LLVM IRと同様に、MemoryPhi は具体的な操作に対応しません。そのため、BasicBlock は MemorySSA 内の MemoryPhi にマップされますが、Instruction は MemoryUse と MemoryDef にマップされます。

また、SSAでは、Phiノードはmust-reach定義（つまり、変数の新しいバージョンでなければならない定義）をマージします。MemorySSAでは、PHIノードはmay-reach定義をマージします（つまり、曖昧になるまで、phiノードに到達するバージョンは、特定の変数をクロバーする可能性も、しない可能性もあります）。

MemoryUse は、メモリーを使用するが変更しない操作です。MemoryUse の例としては、load、または readonly の関数呼び出しなどがあります。

存在するすべての関数には、liveOnEntry という特別な MemoryDef があります。これは、MemorySSA が実行されている関数内のすべての MemoryAccess を支配し、関数の先頭に到達したことを意味します。これは、LLVM IRで Instruction にマップされない唯一の MemoryDef です。liveOnEntry の使用は、使用されているメモリーが未定義であるか、関数が開始される前に定義されていることを意味します。

LLVM IRにオーバーレイされたこれらすべての例（opt -passes='print<memoryssa>' -disable-output を .ll ファイルで実行して取得）は以下のとおりです。この例を表示するときは、クロバーの観点から表示すると役立つ場合があります。特定の MemoryAccess のオペランドはすべて、上記の MemoryAccess の（潜在的な）クロバーであり、MemoryAccess によって生成された値は、他の MemoryAccess のクロバーとして機能できます。

ある MemoryAccess が別の MemoryAccess のクロバーである場合、これらの2つの MemoryAccess が同じメモリーにアクセスする可能性があることを意味します。たとえば、x = MemoryDef(y) は、x が y が変更/制約する（または変更/制約した）メモリーを潜在的に変更することを意味します。同様に、a = MemoryPhi({BB1,b},{BB2,c}) は、a を使用するすべての人が、b または c （または両方）によって潜在的に変更/制約されたメモリーにアクセスしていることを意味します。最後に、MemoryUse(x) は、このuseが x が変更/制約したメモリーにアクセスすることを意味します（例として、x = MemoryDef(...) と MemoryUse(x) が同じループにある場合、useは単独で外に巻き上げることができないと考えてください）。

それを別の有用な見方で見るのは、メモリーバージョンの観点からです。その観点では、特定の MemoryAccess のオペランドは、操作前のメモリー全体のバージョンであり、アクセスが値を生成する場合（つまり、MemoryDef/MemoryPhi）、値は操作後のメモリーの新しいバージョンです。

define void @foo() {
entry:
  %p1 = alloca i8
  %p2 = alloca i8
  %p3 = alloca i8
  ; 1 = MemoryDef(liveOnEntry)
  store i8 0, ptr %p3
  br label %while.cond

while.cond:
  ; 6 = MemoryPhi({entry,1},{if.end,4})
  br i1 undef, label %if.then, label %if.else

if.then:
  ; 2 = MemoryDef(6)
  store i8 0, ptr %p1
  br label %if.end

if.else:
  ; 3 = MemoryDef(6)
  store i8 1, ptr %p2
  br label %if.end

if.end:
  ; 5 = MemoryPhi({if.then,2},{if.else,3})
  ; MemoryUse(5)
  %1 = load i8, ptr %p1
  ; 4 = MemoryDef(5)
  store i8 2, ptr %p2
  ; MemoryUse(1)
  %2 = load i8, ptr %p3
  br label %while.cond
}

上から順番に見ていきましょう。

• 6 = MemoryPhi({entry,1},{if.end,4}) は、while.cond に入る際、到達定義が 1 または 4 のいずれかであることを示しています。この MemoryPhi は、テキストIRでは数値 6 で参照されます。

• 2 = MemoryDef(6) は、store i8 0, ptr %p1 が定義であり、その直前の到達定義が 6、つまり while.cond の後の MemoryPhi であることを示しています。（この MemoryDef が、分離された、明確化された MemoryPhi にリンクされていない理由については、以下のUse and Defの最適化と精度のセクションを参照してください。）

• 3 = MemoryDef(6) は、store i8 0, ptr %p2 が定義であることを示しており、その到達定義も 6 です。

• 5 = MemoryPhi({if.then,2},{if.else,3}) は、このブロックの前の破壊が 2 または 3 のいずれかである可能性があることを示しています。

• MemoryUse(5) は、load i8, ptr %p1 がメモリの使用であり、5 によって破壊されていることを示しています。

• 4 = MemoryDef(5) は、store i8 2, ptr %p2 が定義であり、その到達定義が 5 であることを示しています。

• MemoryUse(1) は、load i8, ptr %p3 が単なるメモリのユーザーであり、この使用を破壊する可能性のある最後のものが while.cond の上にある（例えば、%p3 へのストア）ことを示しています。メモリバージョニングの言葉で言えば、実際にはメモリバージョン1にのみ依存し、それ以降に生成された新しいメモリバージョンには影響されません。

余談ですが、MemoryAccess は主に便宜上の理由から Value であり、LLVM IRと相互作用するためのものではありません。

MemorySSAの設計

MemorySSA は、任意の関数に対して構築できる解析です。構築されると、関数のIRをパスしてMemoryAccessのマッピングを構築します。その後、MemorySSA に、MemoryAccess 間の支配関係などの情報を問い合わせたり、特定の Instruction の MemoryAccess を取得したりできます。

MemorySSA の構築が完了すると、使用できる MemorySSAWalker も渡されます（下記参照）。

ウォーカー

MemorySSA がそのジョブを実行するのに役立つ構造体が MemorySSAWalker、または略してウォーカーです。ウォーカーの目的は、MemoryAccess によって直接表現される範囲を超えた、破壊クエリへの答えを提供することです。例えば、以下が与えられたとします。

define void @foo() {
  %a = alloca i8
  %b = alloca i8

  ; 1 = MemoryDef(liveOnEntry)
  store i8 0, ptr %a
  ; 2 = MemoryDef(1)
  store i8 0, ptr %b
}

%a へのストアは、明らかに %b へのストアの破壊ではありません。ウォーカーの目標はこれを解明し、MemoryAccess 2 の破壊について問い合わせたときに liveOnEntry を返すことです。

デフォルトでは、MemorySSA は、使用しているエイリアス解析スタックを参照して、MemoryDef と MemoryUse を最適化できるウォーカーを提供します。ただし、ウォーカーは柔軟に構築されているため、より特化したウォーカー（例えば、GlobalsAA を具体的に照会するもの、常に MemoryPhi ノードで停止するものなど）を作成することは完全に合理的であり（また期待されています）。

デフォルトのウォーカーAPI

ウォーカーを使用して破壊アクセスを取得するために使用される主なAPIが2つあります。

• MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA); は、MA の破壊メモリアクセスを返します。途中で計算されたすべての中間結果を、照会された各アクセスの一部としてキャッシュします。

• MemoryAccess *getClobberingMemoryAccess(MemoryAccess *MA, const MemoryLocation &Loc); は、MA から開始して、メモリロケーション Loc を破壊するアクセスを返します。このAPIは特定のメモリアクセスの破壊アクセスを要求しないため、キャッシュできる結果はありません。

自分で破壊を見つける

独自のウォーカーを作成する場合、MemoryAccess を支配するすべての MemoryDef をウォークすることで、MemoryAccess の破壊を見つけることができます。MemoryDef の構造により、これは比較的簡単になります。最終的に、最適化しようとしている MemoryAccess を支配するすべての破壊のリンクされたリストを形成します。言い換えれば、MemoryDef の definingAccess は常に、その MemoryDef の最も近い支配的な MemoryDef または MemoryPhi です。

Use and Defの最適化

MemoryUse は、その定義または最適化されたアクセスである単一のオペランドを保持します。従来、MemorySSA は、指定されたしきい値まで、構築時に MemoryUse を最適化していました。具体的には、すべての MemoryUse のオペランドは、その MemoryUse の実際の破壊を指すように最適化されていました。これは上記の例で見ることができます。if.end の 2 番目の MemoryUse は、エントリブロックからの MemoryDef である 1 のオペランドを持っています。これは、ウォーク、値の番号付けなどをより速く、より簡単にするために行われます。このリビジョン以降、パスでウォークが必要ない場合にコンパイル時間を短縮するオプションを提供するために、デフォルトでは構築時に使用を最適化しないように変更されました。ほとんどのユーザーは、以前の動作を維持し、事前にこれが行われていない場合は MemoryUse の 1 回限りの最適化を行うために、新しい API ensureOptimizedUses() を呼び出します。新しいパスユーザーは ensureOptimizedUses() を呼び出すことをお勧めします。

当初、MemorySSA をアクセスごとに 1 つのオペランドに制限していたため、同じ方法で MemoryDef を最適化することはできませんでした。これが変更され、MemoryDef は 2 つのオペランドを保持するようになりました。1 つ目のオペランドである定義アクセスは、常に同じ基本ブロック内の前の MemoryDef または MemoryPhi、または現在のブロックにメモリに書き込む他のアクセスがない場合は、支配的な先行ブロックの最後のアクセスです。これは、Defチェーンをウォークするために必要です。2 番目のオペランドは、ウォーカーの getClobberingMemoryAccess(MA) で以前に呼び出しがあった場合の最適化されたアクセスです。このAPIは、MA の一部として情報をキャッシュします。すべての MemoryDef を最適化すると、二次時間複雑度になり、デフォルトでは実行されません。

任意のMemoryDefの使用状況のウォークは、それが最適化されたアクセスを見つけることができます。そのようなウォークのコードスニペットは次のようになります。

MemoryDef *Def;  // find who's optimized or defining for this MemoryDef
for (auto &U : Def->uses()) {
  MemoryAccess *MA = cast<MemoryAccess>(U.getUser());
  if (auto *DefUser = dyn_cast<MemoryDef>(MA))
    if (DefUser->isOptimized() && DefUser->getOptimized() == Def) {
      // User who is optimized to Def
    } else {
      // User who's defining access is Def; optimized to something else or not optimized.
    }
}

MemoryUse が最適化されている場合、特定のストアについては、そのストアによって破壊されるすべてのロードを、そのストアの直接的および推移的な使用をウォークすることで見つけることができます。

checkUses(MemoryAccess *Def) { // Def can be a MemoryDef or a MemoryPhi.
  for (auto &U : Def->uses()) {
    MemoryAccess *MA = cast<MemoryAccess>(U.getUser());
    if (auto *MU = dyn_cast<MemoryUse>(MA)) {
      // Process MemoryUse as needed.
    } else {
      // Process MemoryDef or MemoryPhi as needed.

      // As a user can come up twice, as an optimized access and defining
      // access, keep a visited list.

      // Check transitive uses as needed
      checkUses(MA); // use a worklist for an iterative algorithm
    }
  }
}

同様のトラバーサルの例は、DeadStoreEliminationパスにあります。

無効化と更新

MemorySSA は LLVM IR を追跡するため、IR が更新されるたびに更新する必要があります。この場合の「更新」には、Instructions の追加、削除、移動が含まれます。更新 API は必要に応じて作成されています。例が必要な場合は、GVNHoist および LICM が MemorySSA の更新 API のユーザーです。新しい MemoryDef ( insertDef を呼び出すことによって) の追加は、新しいアクセスが多くの MemoryPhi の挿入と多くの MemoryAccesses の名前変更 (最適化の無効化) をトリガーする場合、時間のかかる更新になる可能性があることに注意してください。

Phi の配置

MemorySSA は、実際に必要な場所にのみ MemoryPhi を配置します。つまり、LLVM の SSA 形式と同様に、プルーニングされた SSA 形式です。たとえば、次のような例を考えてみましょう。

define void @foo() {
entry:
  %p1 = alloca i8
  %p2 = alloca i8
  %p3 = alloca i8
  ; 1 = MemoryDef(liveOnEntry)
  store i8 0, ptr %p3
  br label %while.cond

while.cond:
  ; 3 = MemoryPhi({%0,1},{if.end,2})
  br i1 undef, label %if.then, label %if.else

if.then:
  br label %if.end

if.else:
  br label %if.end

if.end:
  ; MemoryUse(1)
  %1 = load i8, ptr %p1
  ; 2 = MemoryDef(3)
  store i8 2, ptr %p2
  ; MemoryUse(1)
  %2 = load i8, ptr %p3
  br label %while.cond
}

if.then および if.else からストアを削除したため、if.end の MemoryPhi は無意味になるため、配置しません。したがって、if.then または if.else に MemoryDef を配置する必要がある場合は、if.end 用の MemoryPhi も作成する必要があります。

これが大きな負担になる場合は、どこにでも MemoryPhi を配置することができます。上記の phi を最適化できる Walker があるため、そうしても最適化が禁止されることはありません。

非目標

MemorySSA は、メモリ操作間の関係を推論し、より迅速なクエリを可能にすることを目的としています。すべての潜在的なメモリ関連の最適化のための唯一の真実の情報源となることを目的としたものではありません。特に、次のように、アトミックまたは揮発性の操作について推論するために MemorySSA を使用しようとする場合は注意が必要です。

define i8 @foo(ptr %a) {
entry:
  br i1 undef, label %if.then, label %if.end

if.then:
  ; 1 = MemoryDef(liveOnEntry)
  %0 = load volatile i8, ptr %a
  br label %if.end

if.end:
  %av = phi i8 [0, %entry], [%0, %if.then]
  ret i8 %av
}

MemorySSA の分析のみに基づいて考えると、load を entry にホイストするのは合法に見えるかもしれません。しかし、揮発性ロードであるため、そうではありません。

設計上のトレードオフ

精度

LLVM の MemorySSA は、意図的に速度のために精度を犠牲にしています。メモリ変数を、メモリの分離されたパーティションであるかのように考えてみましょう（つまり、上記のように1つの変数がある場合、それはメモリ全体を表し、複数の変数がある場合、それぞれがメモリのいくつかの分離された部分を表します）。

まず、エイリアス解析の結果は互いに競合し、各結果が解析で必要なものである可能性があるため（つまり、TBAAはエイリアスがないと判断し、別のものがエイリアスする必要があると判断する可能性があります）、すべての最適化が望むようにメモリをパーティション分割することはできません。次に、一部のエイリアス解析の結果は推移的ではありません（つまり、AはBのエイリアスではなく、BはCのエイリアスではない場合でも、AがCのエイリアスではないとは限りません）。したがって、可能なエイリアスのすべてのペアを表す変数なしに、すべての場合に正確なパーティショニングを考案することはできません。したがって、正確にパーティショニングするには、少なくとも N^2 個の新しい仮想変数、phi ノードなどを導入する必要がある場合があります。

これらの各変数は、複数の def サイトで上書きされる可能性があります。

例を挙げると、構造体のフィールドを個々の変数に分割すると、複数の構造体のフィールドを定義する可能性のあるすべてのエイリアス操作は、それらのうちの複数個を定義する可能性があります。これは非常に一般的です（呼び出し、コピー、フィールドストアなど）。

他のコンパイラでのメモリの SSA 形式の経験から、これを正確に行うことは単純に不可能であることが示されています。実際、正確に行うことは価値がありません。なぜなら、すべての最適化が膨大な数の仮想変数と phi ノードを処理する必要があるためです。

そこで、パーティション分割を行います。パーティション分割を行う時点で、繰り返しますが、1つ以上の変数にパーティション分割しても意味がないことが経験からわかっています。IR が増えるだけで、最適化ではいずれにしてもさらにあいまいさを解消するためにクエリを実行する必要があります。

その結果、LLVM は1つの変数にパーティション分割します。

実践における精度

実際には、LLVM には、MemorySSA によって提供される結果の精度にも影響を与える実装の詳細があります。たとえば、AliasAnalysis には、phi を介して調べる際にさまざまな上限または制限があり、MemorySSA が推論できることに影響を与える可能性があります。異なるパスによって行われた変更により、MemorySSA が「過度に最適化される」（スクラッチから再計算した場合よりも正確な結果を提供できる）か、「最適化不足」（再計算した場合にさらに推論できる可能性がある）になる可能性があります。これにより、複数の後続のパスによって更新されたために MemorySSA が取得した状態に結果が依存する場合に、単一パスで分離して結果を再現することが困難になる可能性があります。MemorySSA を使用および更新するパスは、MemorySSAUpdater によって提供される API を使用するか、Walker での呼び出しを通じて行う必要があります。MemorySSA への直接的な最適化は許可されていません。現在、DSE（DeadStoreElimination）がストアの最適化されたアクセスを更新する、狭い範囲の例外が1つあります。これは、トラバーサルが最適化が正しいことを保証した後に行われます。これは、トラバーサルと推論が MemorySSA が行うことを超えており、それらが「無料」（つまり、DSEはいずれにしてもそれらを行う）であるためのみ許可されています。この例外は、フラグ（“-dse-optimize-memoryssa”）の下に設定されており、最適化を個別に再現するのに役立つように無効にすることができます。

LLVM 開発者会議での発表

• 2016 LLVM 開発者会議：G. Burgess - MemorySSA in Five Minutes.

• 2020 LLVM 開発者会議：S. Baziotis & S. Moll - Finding Your Way Around the LLVM Dependence Analysis Zoo