LLVM の readonly、nocapture、nonnull はどこから来るのか（日本語版）

最適化済みの LLVM IR を見ると、いたるところに属性が散りばめられています:

declare void @memcpy(ptr noalias nocapture writeonly, ptr noalias nocapture readonly, i64) #0

これらの属性の一部は Clang 由来、一部はヘッダの関数シグネチャ由来、一部はソース中の __attribute__ 注釈由来です。しかし驚くほど多くが LLVM 自身によって 推論 されたものです。コンパイラは関数本体を見て、ある性質を証明し、下流パスが頼れる属性を関数にタグ付けします。

この記事はその推論がどう動くかについてです。LLVM にはそのための別個のインフラが 2 つあります: 古典的な FunctionAttrs パスと、新しくより強力な Attributor フレームワーク。証明できる属性は重なりますが、やり方はかなり異なります。

行番号は llvm/lib/Transforms/IPO/ 下のファイル: FunctionAttrs.cpp, Attributor.cpp, AttributorAttributes.cpp。

なぜこれらの属性が重要か

どう推論されるかに入る前に、なぜ誰かがこれを気にするのかを見ましょう。いくつかの属性とそれらが解き放つもの:

• readonly — 関数はメモリに書き込まない。ループ不変コードモーション を可能にする: readonly 関数を呼ぶループ本体は、引数が変わらなければ呼び出しをループ外に巻き上げられる。
• readnone — 関数はメモリを読みも書きもしない。readonly より強い。完全な CSE を可能にする。
• nocapture（ポインタ引数上） — 呼び出し先はポインタをどこにも保存せず、エスケープさせない。これが stack-move や call-slot 最適化（MemCpyOpt の記事 で書きました）を合法にします。
• noalias（戻り値上） — 返されるポインタはプログラム内の他の何ともエイリアスしない。malloc, calloc などのアロケータに付く属性。非常に積極的なエイリアス解析を可能にする。
• willreturn — 関数は常に return する。呼び出しが無限ループし得ないということ。コンパイラは停止挙動の変更を心配せずに呼び出しをループから外に動かせる。
• nonnull（戻り値または引数上） — ポインタは決して null ではない。null チェックを除去。
• nofree — 関数はメモリを解放しない。呼び出しをまたいだポインタ寿命の推論を可能にする。
• norecurse — 関数は自己呼び出しをしない（直接も推移的にも）。スタック使用解析を単純化。

これらの多くは伝播します: f が g を呼び g が readonly なら、f も readonly と推論できる可能性があります。推論パスはこの伝播を自動で行います。

FunctionAttrs: SCC ベースのポストオーダー

FunctionAttrs.cpp は古くて単純なパス。コールグラフ、特にその強連結成分 (SCC) を中心に構造化されています。パスは SCC をポストオーダー — 呼び出し先を先、呼び出し元を後 — に訪問するので、ある関数を見るときには、それが呼ぶ関数は全て解析済みです。

トップレベルエントリポイントは PostOrderFunctionAttrsPass::run（FunctionAttrs.cpp:2315）。deriveAttrsInPostOrder（FunctionAttrs.cpp:2273）に委譲します:

SmallPtrSet<Function *, 8> deriveAttrsInPostOrder(
    ArrayRef<Function *> Functions, ...) {
  SCCNodesResult Nodes = createSCCNodeSet(Functions);

  addArgumentReturnedAttrs(Nodes.SCCNodes, Changed);
  addMemoryAttrs(Nodes.SCCNodes, AARGetter, Changed);
  addArgumentAttrs(Nodes.SCCNodes, Changed, ...);
  addWillReturn(Nodes.SCCNodes, Changed);
  addNoAliasAttrs(Nodes.SCCNodes, Changed);
  addNonNullAttrs(Nodes.SCCNodes, Changed);
  addNoRecurseAttrs(Nodes.SCCNodes, Changed);
  // ...
  return Changed;
}

属性ごとに 1 つの関数、それぞれが SCC 全体を一度に操作。この最後の部分が微妙な設計決定です。

なぜ SCC 単位？ 相互再帰する関数は SCC を形成します。f の readonly を g（f が呼ぶ）が readonly か知らずに推論しようとして、g の解析が f について知る必要がある場合、行き詰まります。FunctionAttrs は SCC 全体を単位として扱うことで結び目をほどきます: 楽観的に SCC の 全 メンバーが性質を持つと仮定し、各々を解析し、どれかが失敗したら SCC 全体から性質を取り下げる。

メモリ属性の推論

addMemoryAttrs（FunctionAttrs.cpp:276-313）は良い代表例です:

template <typename AARGetterT>
static void addMemoryAttrs(const SCCNodeSet &SCCNodes, ...) {
  MemoryEffects ME = MemoryEffects::none();

  for (Function *F : SCCNodes) {
    AAResults &AAR = AARGetter(*F);
    auto [FnME, FnRecursiveArgME] =
        checkFunctionMemoryAccess(*F, F->hasExactDefinition(), AAR, SCCNodes);
    ME |= FnME;
  }

  for (Function *F : SCCNodes) {
    MemoryEffects OldME = F->getMemoryEffects();
    MemoryEffects NewME = ME & OldME;
    if (NewME != OldME) {
      ++NumMemoryAttr;
      F->setMemoryEffects(NewME);
      Changed.insert(F);
    }
  }
}

SCC を 2 回走査:

1. 収集。 各関数について、全命令をスキャンしてどんなメモリにアクセスするかを集める。ロードは Ref（読み取り）に、ストアは Mod（書き込み）に貢献、呼び出しは自身の属性を通じて主張するものを貢献。SCC 内 の呼び出しは最初のパスでは無視 — 再帰は保守的に扱う。
2. 適用。 SCC 全体のメモリ効果の和集合をとる。SCC 内の全関数にその和集合で属性を付ける。和集合が「読み取りのみ」なら、SCC 内の全関数は readonly。「何もない」なら全て readnone。各関数が既に持つものより強いものがあれば設定。

ここで「単位としての SCC」戦略が効いてきます。相互再帰する readonly 関数のサイクルは、全てが同時に readonly と解析されます。

nonnull の推論

addNonNullAttrs（FunctionAttrs.cpp:1639-1693）は似た形ですが「推測してから検証する」ひねりがあります:

static void addNonNullAttrs(const SCCNodeSet &SCCNodes, ...) {
  bool SCCReturnsNonNull = true;

  for (Function *F : SCCNodes) {
    if (!isReturnNonNull(F, SCCNodes, Speculative))
      SCCReturnsNonNull = false;
  }

  if (SCCReturnsNonNull) {
    for (Function *F : SCCNodes) {
      F->addRetAttr(Attribute::NonNull);
      Changed.insert(F);
    }
  }
}

isReturnNonNull は各 return 文を歩き、返される値を phi、select、呼び出しを通して遡ります。全ての戻り値が non-null と証明できれば（SCC 内の再帰呼び出しは 推測的に non-null を返すと仮定）、関数の戻りは nonnull。SCC 内の 1 つでも関数がチェックを失敗したら、SCC 全体が失格。

推測こそ再帰ケースを機能させるものです。そうでなければ次のような関数:

int *recursive(int n) {
  if (n == 0) return &global_int;
  return recursive(n - 1);
}

は行き詰まります: 戻りが nonnull と証明するには再帰呼び出しが nonnull を返すと知る必要があり、それには戻りが nonnull と既に知る必要がある。FunctionAttrs は楽観的に仮定してから検証することでこれを扱います。仮定が間違っていたなら「どれかの関数が失敗」チェックが捕まえます。

FunctionAttrs の限界

FunctionAttrs は「SCC 順に各関数を一度見る」で計算できる属性にはよく機能します。しかし一部の属性はもっと複雑な形で互いに依存します:

• 引数が nocapture と知れば関数が readonly と結論できるかもしれない。
• 関数が readonly と知れば引数が nocapture と結論できるかもしれない（ポインタのストアは書き込みになるから）。

FunctionAttrs はパス内である程度これを行いますが、任意の依存パターンで複数の属性と複数の関数をまたいで伝播することは苦手です。ここで Attributor の出番です。

Attributor: 不動点による抽象解釈

Attributor フレームワーク（Attributor.cpp, AttributorAttributes.cpp）は異なる構造です。属性ごとに 1 つの関数ではなく、各属性は 抽象属性 (AA) です — IR の一片のある性質についてコンパイラの現在の最良の知識を表す C++ オブジェクト。

主要クラスは Attributor.h にあります:

struct AbstractAttribute {
  virtual ChangeStatus updateImpl(Attributor &A) = 0;

  virtual ChangeStatus manifest(Attributor &A) {
    return ChangeStatus::UNCHANGED;
  }

  virtual void trackStatistics() const = 0;
};

AA は持ちます:

• 状態 — 悲観的（全てが悪いかも）から楽観的（証明可能に良い）に洗練されていく。例えば AANoCapture は値がメモリで、整数表現で、または戻りを通じてキャプチャされるかを追跡。
• updateImpl メソッド — 解析を再実行する。他の AA を問い合わせ、IR を読み、エイリアス解析を呼び、必要なことは何でもできる。状態がより精密になれば CHANGED を返す。
• manifest メソッド — 推論された属性を最後に IR に書き込む。

不動点ループ

ドライバは Attributor::runTillFixpoint（Attributor.cpp:2119-2258）:

void Attributor::runTillFixpoint() {
  SetVector<AbstractAttribute *> Worklist;
  Worklist.insert_range(DG.SyntheticRoot);

  unsigned IterationCounter = 1;
  do {
    LLVM_DEBUG(dbgs() << "\n[Attributor] #Iteration: " << IterationCounter << "\n");

    for (AbstractAttribute *AA : Worklist) {
      if (!AA->getState().isAtFixpoint())
        if (updateAA(*AA) == ChangeStatus::CHANGED)
          ChangedAAs.push_back(AA);
    }

    Worklist.clear();
    Worklist.insert_range(ChangedAAs);

  } while (!Worklist.empty() && (IterationCounter++ < MaxIterations));
}

古典的なワークリスト不動点反復:

1. 全 AA をワークリストで開始。
2. 各々を更新。状態が変わったものは ChangedAAs に。
3. 次の反復のワークリストは、変わったものに依存していた AA（別の場所で追跡）。
4. 変化がなくなるかハード反復制限に達するまで繰り返し。

この設計の威力は、AA X が変わるとそれを問い合わせた全 AA が自動的に再追加されることです。こんなチェインが作れます:

1. AAMemoryLocation が関数 F を readonly と証明。
2. 次の反復、F の引数の AANoCapture が F は readonly と気づき、ポインタのストアは不可能、だから引数は nocapture。
3. その次の反復、AANonNull が引数は nocapture と気づき、null 解析をさらに洗練。

これらは全て依存追跡によって自動で起き、順序を明示的に調整する必要はありません。

例となる AA: AANoCapture

AttributorAttributes.cpp:5923-6128 より:

struct AANoCaptureImpl : public AANoCapture {
  ChangeStatus updateImpl(Attributor &A) override {
    if (AA::isAssumedReadOnly(A, FnPos, *this, IsKnown)) {
      T.addKnownBits(NOT_CAPTURED_IN_MEM);
    }

    auto UseCheck = [&](const Use &U, bool &Follow) -> bool {
      return checkUse(A, T, U, Follow);
    };

    if (!A.checkForAllUses(UseCheck, *this, *V))
      return indicatePessimisticFixpoint();

    auto Assumed = S.getAssumed();
    S.intersectAssumedBits(T.getAssumed());
    return (Assumed == S.getAssumed()) ? ChangeStatus::UNCHANGED
                                       : ChangeStatus::CHANGED;
  }
};

上から下に読むと:

1. Attributor に問い合わせ: 包含関数は readonly と判明しているか？（これは別の AA、AAMemoryLocation への問い合わせ。）Yes なら、我々のポインタのストアは不可能、だからメモリ経由でキャプチャされ得ないと分かる。
2. ポインタの全使用を歩く。checkForAllUses が各々に checkUse を呼び、その使用が no-capture 性質を保つか決定する（例: ロードアドレスとして使うのは OK、グローバルに保存するのはキャプチャ）。
3. どれかの使用が安全と示せなければ、諦めて悲観的不動点を取る。
4. さもなくば、実行中の状態 S を新情報 T と交差。変化があれば CHANGED を返す。

ステップ 1 の問い合わせが依存を作るものです。もし我々の関数の AAMemoryLocation が後で洗練されれば（例: 引数経由で書き込みしないと決定）、我々の updateImpl が再呼び出しされます。

Manifest フェーズ

不動点ループが落ち着いた後、Attributor は manifest フェーズに入ります（Attributor.cpp:2647-2677）:

ChangeStatus Attributor::run() {
  Phase = AttributorPhase::UPDATE;
  runTillFixpoint();

  Phase = AttributorPhase::MANIFEST;
  ChangeStatus ManifestChange = manifestAttributes();

  Phase = AttributorPhase::CLEANUP;
  ChangeStatus CleanupChange = cleanupIR();

  return ManifestChange | CleanupChange;
}

manifestAttributes は全 AA を歩き、「良い」不動点にあるものについて対応する属性を IR に書き込みます。AANoCapture は F->addParamAttr(ArgNo, Attribute::NoCapture) を呼び、AANonNull は F->addRetAttr(Attribute::NonNull) を呼ぶ、等。

update と manifest の分離は重要です: update 中は IR が変更されていないので、AA は「生の」コードを問い合わせて安定状態に基づいた結論に到達できます。全てが収束して初めて実際に属性を発行します。

具体的なテストケース

llvm/test/Transforms/FunctionAttrs/nocapture.ll より:

; 属性推論前
define void @c2(ptr %q) {
  store ptr %q, ptr @g
  ret void
}

define void @c3(ptr %q) {
  call void @c2(ptr %q)
  ret void
}

結論したいこと:

• @c2 は引数をグローバルに保存するが読まない。だから @g に関して writeonly で、引数 %q はキャプチャされる（@g にエスケープ）。しかし @c2 自身はポインタから読まないので、引数属性は writeonly。
• @c3 は @c2 に転送するだけ。@c2 の引数が writeonly で、@c3 内で他に %q に触れるものがなければ、@c3 の引数も writeonly。

FunctionAttrs パス（とその上の Attributor）を走らせた後:

define void @c2(ptr nofree writeonly %q) {
  store ptr %q, ptr @g
  ret void
}

define void @c3(ptr %q) memory(write) {
  call void @c2(ptr nofree writeonly %q)
  ret void
}

いくつか推論が行われた:

• @c2 の %q は writeonly と nofree を得た。
• @c2 全体は、本体が示す以上のメモリ属性は得ていない（@g に書き込む）。
• @c3 は memory(write) を得た — 関数全体が書き込みのみで、単一の呼び出しの効果と整合。
• 呼び出しサイト call void @c2(...) も writeonly と nofree を得て、呼び出し元自身の解析に情報を与える。

実務での FunctionAttrs vs Attributor

両パスとも標準 LLVM パイプラインで走ります。FunctionAttrs は高速で一般ケースを扱います。Attributor は遅いがより精密、特に循環依存のある属性で。通常は FunctionAttrs が先に走り、その後 Attributor が締め上げます。

実務的な意味: 最適化済み IR で引数の nocapture を見たら、解析が単純だったなら FunctionAttrs が、反復洗練が必要だったなら Attributor が置いた可能性が高いです。ほとんどの C/C++ コードでは両方が同じ結論に達し、FunctionAttrs で十分です。多くの小さな関数が互いを呼ぶ重度にテンプレート化された C++ では Attributor の反復アプローチが勝ちます。

大きな絵

関数属性推論こそ、手続き間最適化を機能させるものです。これなしでは、多くの下流パスは呼ばれる関数について最悪を仮定せねばなりません — 何でも読む、何でも書く、何でも解放する、渡されたポインタを何でもキャプチャする。推論された属性があれば、パスは狙いを定めた仮定をして積極的に走れます。

依存チェインはしばしば次のように見えます:

1. 単純な算術関数が readnone と推論される。
2. 呼び出し元が readonly と推論可能に。
3. LICM が呼び出しをループから外に巻き上げ可能に。
4. 別関数のインライン化条件を満たす形にコードの形状が変化。
5. インライン化後、SROA がクリーンな alloca を見てさらにメモリを除去。
6. GVN が結果のコードを掃除。

これら全ては、FunctionAttrs が 1 ミリ秒未満で推論した 1 つの readnone 属性から始まります。手続き間属性は威力の増幅器です。

次に読むもの

• Attributor.h のコメントは濃密だが徹底的 — 抽象属性のライフサイクルと依存グラフの機構を説明しています。
• llvm/test/Transforms/FunctionAttrs/ には数百の小さなテストがあり、それぞれ 1 つの推論シナリオを試します。.ll ファイルを読んで、パスが何を理解できて何を理解できないかの直観を構築してください。
• MemCpyOpt の記事 には、nocapture や writeonly が変換を合法にする理由である場所がいくつかあります。属性推論こそ、それらの変換を実コードの大部分に届かせるものです。