SROA: LLVM はどうやって構造体を消滅させるのか（日本語版）

-O2 の出力を眺めていて、丁寧に組んだ struct Point { int x, y; } が跡形もなく消えているのに気づいたことがあるなら、その犯人は SROA — Scalar Replacement of Aggregates（集約値のスカラー置換） です。SROA は構造体や配列の alloca を小さな断片（多くは個別のスカラー値）に分割し、それらを SSA レジスタに昇格させます。構造体はメモリ上から完全に消えます。

この記事では SROA がどうやってそれをやっているかを追います: スライス化アルゴリズム、パーティショニング、リライタ、そして mem2reg への受け渡しです。行番号は全て llvm/lib/Transforms/Scalar/SROA.cpp のもの。ヘッダは llvm/include/llvm/Transforms/Scalar/SROA.h。

問題

次の C コードを考えましょう:

struct Point { int x, y; };

int getX() {
  Point p;
  p.x = 10;
  p.y = 20;
  return p.x;
}

SROA 前、Clang はこう吐きます:

define i32 @getX() {
entry:
  %p = alloca { i32, i32 }
  %gep.x = getelementptr { i32, i32 }, ptr %p, i32 0, i32 0
  store i32 10, ptr %gep.x
  %gep.y = getelementptr { i32, i32 }, ptr %p, i32 0, i32 1
  store i32 20, ptr %gep.y
  %v.x = load i32, ptr %gep.x
  ret i32 %v.x
}

他の全ての最適化パスにとってこれは問題です: %p は 1 つの 8 バイト alloca で、フィールドは GEP 経由でアクセスされます。SROA なしでは、mem2reg のようなパスは alloca への部分アクセスを扱おうとしません — 全ロード/ストアがアロケーション全体をカバーする alloca しか昇格しないのです。だから %p はメモリに残り、最終バイナリは定数で済むはずのところにスタックトラフィックを持つことになります。

SROA 後:

define i32 @getX() {
entry:
  %p.x = alloca i32
  %p.y = alloca i32
  store i32 10, ptr %p.x
  store i32 20, ptr %p.y
  %v.x = load i32, ptr %p.x
  ret i32 %v.x
}

これで各フィールドが自前のスカラー alloca を持つようになりました。mem2reg はすぐに両方を SSA 値に昇格でき、デッドコード除去は %p.y へのストアを捨てます（誰も読まないので）。最終 IR は単に ret i32 10 になります。

これが変換の形です。記事の残りは、SROA が実際どうやってそこへ到達するかです。

メインループ

SROA は関数パスです。その外側ループ（SROA.cpp:6034-6057）は古典的なワークリストです:

do {
  while (!Worklist.empty()) {
    auto [IterationChanged, IterationCFGChanged] =
        runOnAlloca(*Worklist.pop_back_val());
    Changed |= IterationChanged;
    CFGChanged |= IterationCFGChanged;
    Changed |= deleteDeadInstructions(DeletedAllocas);
    if (!DeletedAllocas.empty()) {
      Worklist.set_subtract(DeletedAllocas);
      PostPromotionWorklist.set_subtract(DeletedAllocas);
      PromotableAllocas.set_subtract(DeletedAllocas);
      DeletedAllocas.clear();
    }
  }
  Changed |= promoteAllocas();
  Worklist = PostPromotionWorklist;
  PostPromotionWorklist.clear();
} while (!Worklist.empty());

このループは:

1. ワークリストから alloca を取り出し、runOnAlloca で処理する。
2. キューが尽きたら promoteAllocas を呼ぶ — 「昇格可能」とマークされたものを全て mem2reg に渡す。
3. 昇格後に新たな機会が現れるかもしれない（例: フィールド自体が構造体であった構造体 alloca）。それらは PostPromotionWorklist に入り、新たなパスを受ける。

この 2 段構造 — スライス/書き換え、そして昇格、そしてまたスライス — が、深くネストした集約で SROA が複数回発火する理由です。

ステップ 1: スライスを作る

最初の本番の仕事は、alloca への全アクセスを バイト範囲 として記述することです。それが Slice です（SROA.cpp:526-592）:

class Slice {
  uint64_t BeginOffset = 0;
  uint64_t EndOffset = 0;
  PointerIntPair<Use *, 1, bool> UseAndIsSplittable;
  Value *ProtectedFieldDisc;

  Slice(uint64_t BeginOffset, uint64_t EndOffset, Use *U, bool IsSplittable,
        Value *ProtectedFieldDisc)
      : BeginOffset(BeginOffset), EndOffset(EndOffset),
        UseAndIsSplittable(U, IsSplittable),
        ProtectedFieldDisc(ProtectedFieldDisc) {}
};

各スライスは次を記録します:

• BeginOffset / EndOffset — このアクセスが触れる alloca 内のバイト範囲 [Begin, End)
• Use * — 実際の IR での使用箇所（ロード、ストア、memcpy 等のオペランド）
• IsSplittable — memcpy のような大きな一括操作がパーティション境界で分割できるか

スライスリストを作るため、SROA は alloca ポインタの到達可能な全使用箇所を歩きます。このウォークは PtrUseVisitor を継承した SliceBuilder というビジタ（SROA.cpp:1033-1470）として実装されています。関連する各命令がスライスを貢献します:

void visitLoadInst(LoadInst &LI) {
  if (!IsOffsetKnown)
    return PI.setEscapedReadOnly(&LI);

  TypeSize Size = DL.getTypeStoreSize(LI.getType());
  // ... スケーラブルベクトル処理は省略 ...
  return handleLoadOrStore(LI.getType(), LI, Offset, Size.getFixedValue(),
                           LI.isVolatile());
}

オフセット 0 の load i32, ptr %gep.x に対して、これはロードのポインタオペランドを指すスライス [0, 4) を生成します。オフセット 4 のロードに対しては [4, 8) を生成。memcpy(dst, src, 8) で dst が alloca の場合は、分割可能とマークされた単一のスライス [0, 8) を生成します（memcpy は後でパーティションごとの断片に分割できるので）。

ウォーク終了時、スライスはオフセット順にソートされて AllocaSlices に格納されます（SROA.cpp:1454-1477）:

AllocaSlices::AllocaSlices(const DataLayout &DL, AllocaInst &AI) {
  SliceBuilder PB(DL, AI, *this);
  SliceBuilder::PtrInfo PtrI = PB.visitPtr(AI);
  if (PtrI.isEscaped() || PtrI.isAborted()) {
    PointerEscapingInstr = PtrI.getEscapingInst() ? PtrI.getEscapingInst()
                                                  : PtrI.getAbortingInst();
    return;
  }
  // ...
  llvm::erase_if(Slices, [](const Slice &S) { return S.isDead(); });
  llvm::stable_sort(Slices);
}

isEscaped() チェックが重要です: alloca のアドレスがメモリに保存されたり、未知の関数に渡されたり、SROA が追えない方法で使われたりした場合、alloca は「エスケープ」し、SROA は完全に諦めます。関数外から観測可能なアドレスを持つ alloca は安全に分割できません — 他のコードが構造体レイアウトに依存するポインタを持っているかもしれないからです。

ステップ 2: パーティションを形成

スライスが揃ったら、SROA はそれらを パーティション にグループ化します — 重なり合うアクセスがあるため分離できない alloca の連続領域です（SROA.cpp:743-806）:

class Partition {
  uint64_t BeginOffset = 0, EndOffset = 0;
  iterator SI, SJ;
  SmallVector<Slice *, 4> SplitTails;

  uint64_t size() const {
    assert(BeginOffset < EndOffset);
    return EndOffset - BeginOffset;
  }
};

パーティションはウィンドウ [Begin, End) とその中に完全に収まるスライスの部分集合です。2 つのスライスが重なっているなら — たとえばオフセット 0 の store i64 とオフセット 4 の load i32 — それらは同じパーティションに入ります。別々の alloca にきれいに分割できないからです。

上の Point の例では、スライスは [0, 4)（x へのストア）、[4, 8)（y へのストア）、[0, 4)（x からのロード）です。自然に 2 つのパーティション [0, 4) と [4, 8) を形成します。各パーティションが独自の新しい alloca になります。

ステップ 3: 書き換え

各パーティションに対して rewritePartition（SROA.cpp:5234-5360）は新しく小さな alloca を作り、そのパーティションの全スライスを歩いて IR を古い alloca ではなく新しい alloca を指すように更新します:

std::pair<AllocaInst *, uint64_t>
SROA::rewritePartition(AllocaInst &AI, AllocaSlices &AS, Partition &P) {
  const DataLayout &DL = AI.getDataLayout();
  auto [PartitionTy, IsIntegerWideningViable, VecTy] =
      selectPartitionType(P, DL, AI, *C);

  AllocaInst *NewAI;
  if (PartitionTy == AI.getAllocatedType() && P.beginOffset() == 0) {
    NewAI = &AI;
  } else {
    const Align Alignment = commonAlignment(AI.getAlign(), P.beginOffset());
    NewAI = new AllocaInst(
        PartitionTy, AI.getAddressSpace(), nullptr,
        /* alignment logic */,
        AI.getName() + ".sroa." + Twine(P.begin() - AS.begin()),
        AI.getIterator());
    ++NumNewAllocas;
  }

  AllocaSliceRewriter Rewriter(DL, AS, *this, AI, *NewAI, PartitionTy, ...);
  // スライスを歩いて各々を書き換える
}

重労働は AllocaSliceRewriter（SROA.cpp:2721-3000+）にあります。これは InstVisitor で、命令種類ごとに visit メソッドがあります。ポインタオペランドが元の alloca への GEP である StoreInst に遭遇したら、そのアクセスの新 alloca ベースからの相対オフセットを計算してオペランドを書き換えます。LoadInst も同じ扱い。パーティションをまたぐ MemCpyInst はパーティションごとに小さな memcpy 2 つに分割されます。等々。

リライタが問い続ける重要な問いは: 「このパーティションを書き換えた後、新 alloca の全使用は昇格に適するか？」です。つまり、ポインタのエスケープなし、変な型パニングなし、SROA が扱えないアドレス取得された PHI ノードなし。答えが yes なら、新 alloca は PromotableAllocas に追加されます。

ステップ 4: 新 alloca の型を選ぶ

rewritePartition が新 alloca を作るとき、型を選ぶ必要があります。これが selectPartitionType（SROA.cpp:5145-5221）:

auto [CommonUseTy, LargestIntTy] =
    findCommonType(P.begin(), P.end(), P.endOffset());
if (CommonUseTy) {
  TypeSize CommonUseSize = DL.getTypeAllocSize(CommonUseTy);
  if (CommonUseSize.isFixed() && CommonUseSize.getFixedValue() >= P.size()) {
    if (VecTy)
      return {VecTy, false, VecTy};
    return {CommonUseTy, isIntegerWideningViable(P, CommonUseTy, DL),
            nullptr};
  }
}

SROA はパーティション内の全アクセスの型を見ます。全て同じ型を使っていれば — 例えば [0, 4) の全ロード/ストアが i32 — それを選びます。あるものは i32 で別のものは float なら、その領域の「カノニカル」な型はどれか推論しなければなりません。最悪ケース（型が互換でない）では [N x i8] にフォールバックしこのパーティションの昇格は諦めますが、正しさは保たれます。

ここがパーティションを integer widening（整数幅拡大）としてマークする場所でもあります — これは [0, 4) が i32 としても 2 つの i16 としてもアクセスされるようなパターンを 1 つの i32 alloca に書き換え、i16 アクセスをシフトとマスクに変えるトリックです。これで alloca を昇格可能に保てます。

ステップ 5: mem2reg に渡す

全パーティションが書き換えられた後、SROA は promoteAllocas を呼びます（SROA.cpp:5996-6010）:

bool SROA::promoteAllocas() {
  if (PromotableAllocas.empty())
    return false;

  if (SROASkipMem2Reg) {
    LLVM_DEBUG(dbgs() << "Not promoting allocas with mem2reg!\n");
  } else {
    LLVM_DEBUG(dbgs() << "Promoting allocas with mem2reg...\n");
    NumPromoted += PromotableAllocas.size();
    PromoteMemToReg(PromotableAllocas.getArrayRef(), DTU->getDomTree(), AC);
  }

  PromotableAllocas.clear();
  return true;
}

PromoteMemToReg（llvm/Transforms/Utils/PromoteMemToReg.h 由来）は古典的な mem2reg アルゴリズムです: 支配境界に phi ノードを挿入し、各ロードを incoming SSA 値で置き換え、alloca を削除する。これはロードとストアが各々アロケーション全体をカバーする alloca でしか動きませんが — SROA のスライス化のおかげで新 alloca はまさにその性質を持っています。

これが鍵となる設計思想です: SROA は SSA 構築を自分ではやろうとしません。散らかった集約 alloca を綺麗なスカラー alloca に整形し、既存の十分テストされた mem2reg 機構に任せます。

小さな実例

llvm/test/Transforms/SROA/basictest.ll から最もシンプルなテスト:

define i32 @test1() {
entry:
  %X = alloca { i32, float }
  %Y = getelementptr { i32, float }, ptr %X, i64 0, i32 0
  store i32 0, ptr %Y
  %Z = load i32, ptr %Y
  ret i32 %Z
}

追ってみましょう:

1. スライス化。 オフセット 0 の GEP に i32 のストアとロードが続く。[0, 4) の 2 つのスライス、両方 i32 型。float フィールドには誰も触れない。
2. パーティショニング。 1 つのパーティションが [0, 4) をカバー。float フィールドは誰も読まないデッドスペースにあるので、パーティションを生成しない。
3. 書き換え。 新しい alloca i32 が { i32, float } alloca を置き換える。GEP は畳まれる（GEP 恒等式になる）。ストアとロードは新 alloca を直接ターゲットする。
4. 昇格。 新 alloca はフル幅のロードとストアしか持たず、全て同じブロック、エスケープなし。mem2reg は自明にロードをストア値（0）で置き換え alloca を削除する。
5. 結果: ret i32 0。

スタックアロケーション、GEP、ストア、ロードの全てが消えます。これが SROA が mem2reg 後の最初の最適化パスの一つである理由です — 下流全てへの巨大な準備ステップなのです。

SROA が拒否すること

SROA の安全性側は、攻めの側よりも面白いかもしれません。いくつかが諦めの引き金になります:

• エスケープ。 alloca のアドレスがメモリに保存されたり、不透明な関数に渡されたり、他の形で SROA が追跡できない範囲に漏れたりすると、スライス化フェーズはそれをエスケープ済みとマークし、runOnAlloca は諦めます。SliceBuilder 内のチェックで見られます — エスケープらしきものは PointerEscapingInstr を反転させ、パーティションパスは実行されません。
• 変な型パニング。 パーティションが i32 としてもあるポインタ型としてもアクセスされる場合、SROA は一般に全使用でビットパターンを保存する共通型を選べません。バイト配列にフォールバックし、そのパーティションの昇格可能性を失います。
• volatile とアトミック演算。 これらはスライスとしては許可されますが、昇格をブロックします（mem2reg がそれらを SSA に移せないため）。パーティションはメモリ上の alloca のまま残ります。
• 読み取り専用エスケープ。 AS.isEscapedReadOnly() は特別な中間状態（SROA.cpp:5873-5876）: ポインタはエスケープするが、読むだけのコードへ。この場合 SROA は限定的な store-to-load 転送はしますが分割はしません。

これらは恣意的な制限ではありません — それぞれが C/C++ オブジェクトモデルの、フィールドを素朴に分離すれば壊れる何かに対応しています。

パイプライン順序がなぜ重要か

SROA は早く走ります、最初のラウンドの mem2reg のすぐ後です。理由は、ほぼ全ての下流パス — GVN、InstCombine、LICM、LoopVectorize — が集約 alloca ではなくスカラーで作業することを仮定するからです。構造体フィールドアクセスを生きた alloca への getelementptr として残すと、それらのパスは GEP を通してエイリアス解析をせねばならず、そのほとんどはそれをやりません。

だから SROA の仕事は従来的な意味での「最適化」ではないのです。カノニカライゼーションです: レジスタにできる小さなメモリ片が全てレジスタになるようにすること。実際の高速化はその後クリーンな SSA で走るパスから来ます。

役立つメンタルモデル: SROA はフロントエンドの「変数はメモリに生き、名前付きフィールドを持つ」という世界観と、最適化器の「変数はデータフローグラフを流れる SSA 値」という世界観を繋ぐ配管です。これがなければ、LLVM のミドルエンドのほとんどは構造体フィールドが見えないままでしょう。