LLVM の Type-Based Alias Analysis は実際どう動くのか（日本語版） || Packed Bits

Type-Based Alias Analysis (TBAA) は LLVM のなかでも目立たないが非常に重要な最適化の一つです。これがあることで、コンパイラは「float * と int * は同じメモリを指さない」と証明できるようになり、デッドストア削除、ロード転送、ベクトル化など多くの最適化が可能になります。-fno-strict-aliasing を付けると C のコードが遅くなる理由はまさにこの TBAA にあります。

この記事では、LLVM のソースツリーの中で TBAA が実際にどう動いているのかを追っていきます。実際のテストケースから出発し、Clang が生成するメタデータを追い、最後に解析コードを行単位で辿っていきます。読み終わる頃には、任意の !tbaa ノードを見て LLVM の結論を予測できるようになっているはずです。

本稿のソース参照は全て LLVM モノレポのものです。主要なファイルは次の通り:

llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp — 解析本体
llvm/include/llvm/Analysis/TypeBasedAliasAnalysis.h — 公開インタフェース
clang/lib/CodeGen/CodeGenTBAA.cpp — Clang 側のメタデータ生成
llvm/test/Analysis/TypeBasedAliasAnalysis/ — 例題として使う回帰テスト

TBAA が解こうとしている問題

次の C++ 断片を考えてみましょう:

struct foo { char v; };
struct bar { char v; };

char example(foo *a, bar *b) {
  char x = a->v;
  b->v = 0;
  char y = a->v;
  return x + y;
}

素朴なコンパイラは「b->v = 0 が a->v を上書きするかもしれない」と仮定せざるを得ないため、a->v を y にもう一度ロードする必要があります。しかし C と C++ には「厳密エイリアシング規則」があり、あるオブジェクトは互換性のある型の左辺値を通してしかアクセスできない（char* のような周知の例外を除く）と定めています。この規則のもとでは foo* と bar* はメモリ上で重ならないので、y は x に等しく、二度目のロードは冗長です。

TBAA は、この情報を Clang と LLVM の間で伝達する仕組みです。Clang は全てのロード/ストアに対して「そのメモリがどの型でアクセスされたか」を記述するメタデータを付与し、解析側は「この 2 つのアクセスは同じバイトを参照し得るか？」という問いに答えます。

最もシンプルなテストケース

llvm/test/Analysis/TypeBasedAliasAnalysis/aliastest.ll を開いてみましょう。最初の関数（7〜13 行目）:

; CHECK: @test0_yes
; CHECK: add i8 %x, %x
define i8 @test0_yes(ptr %a, ptr %b) nounwind {
  %x = load i8, ptr %a, !tbaa !1
  store i8 0, ptr %b, !tbaa !2
  %y = load i8, ptr %a, !tbaa !1
  %z = add i8 %x, %y
  ret i8 %z
}

CHECK 行は opt -passes=gvn 実行後に期待される結果を示しています。つまり、2 つのロードが 1 つに統合されて、加算が %x + %y ではなく %x + %x になる、ということです。これが起きるのは、TBAA が「%b へのストアは %a を壊さない」と証明できたときに限ります。

メタデータはファイル末尾（47〜68 行目）にあります:

; Root note.
!0 = !{ }
; Some type.
!1 = !{!7, !7, i64 0}
; Some other non-aliasing type.
!2 = !{!8, !8, i64 0}

!7 = !{ !"foo", !0 }
!8 = !{ !"bar", !0 }

登場するノードは 3 種類あります:

!0 は ルートノード — 「この下にあるのは一つの型ファミリー」という空のマーカーに過ぎない
!7 と !8 は スカラー型ノード — 名前と親ノードへのポインタを持つ
!1 と !2 は アクセスタグ — !tbaa が実際に指す先。「このアクセスは型 X で、ベース型 Y のオフセット Z からの読み書き」を表す

型ノードを親ポインタで繋いで描くと、木構造になります:

        !0   (root)
       /  \
     !7    !8
    (foo) (bar)

この記事を通して、この木を 型ツリー と呼ぶことにします。頭の中に残しておくべき絵はこれです。TBAA の仕事は、この木の 2 つの葉を比較して「それらが表すアクセスが同じメモリに触れ得るか」を判定することです。

（厳密に言うと、後述する struct-path TBAA を導入すると一部のノードが複数経路から到達可能になるので、技術的には木ではなく DAG です。ただしエイリアスを判定する親方向の探索ロジックにおいては「木」というイメージがぴったりです。）

この簡略化されたテストでは、各アクセスタグのベース型とアクセス型が同一です（これが {!7, !7, i64 0} という 3 つ組の意味です）。実際の Clang 生成メタデータも同じ形をしていますが、構造体フィールドアクセスではベース型とアクセス型が異なる場合が多くあります。

Clang はこのメタデータをどう生成するか

clang/lib/CodeGen/CodeGenTBAA.cpp がこれらのノードを構築する場所です。注目すべき関数は 3 つあります。

ルートノード（CodeGenTBAA.cpp:47-58）:

llvm::MDNode *CodeGenTBAA::getRoot() {
  if (!Root) {
    if (Features.CPlusPlus)
      Root = MDHelper.createTBAARoot("Simple C++ TBAA");
    else
      Root = MDHelper.createTBAARoot("Simple C/C++ TBAA");
  }
  return Root;
}

各翻訳単位はルートを 1 つだけ持ちます。別のフロントエンド（例えば LLVM IR を生成する Rust コンパイラ）は別のルート文字列を選ぶので、TBAA はその違いを「この 2 つの型ツリーは無関係」のシグナルとして使います。すぐ後でこれが効いてくる場面を見ます。

「万能 char」ノード（CodeGenTBAA.cpp:63-68）:

llvm::MDNode *CodeGenTBAA::getChar() {
  if (!Char)
    Char = createScalarTypeNode("omnipotent char", getRoot(), 1);
  return Char;
}

これは C99 §6.5p7 の特例実装です。つまり「文字型の左辺値はどんなオブジェクトの格納値にもアクセスしてよい」というルールです。型ツリー上で char はルートのすぐ下に位置し、事実上全てのスカラー型の親になります。つまり全スカラー型は char の子孫です。なぜ子孫関係によって char 型アクセスが全てとエイリアスするのか、すぐに見ていきます。

現実的な Clang の生成する木はだいたいこんな感じです:

           root ("Simple C++ TBAA")
            |
           char ("omnipotent char")
          / |  \
        int short long ...

各スカラー型の親ポインタを辿ると、必ず char を経由してルートに行き着きます。

スカラー型（CodeGenTBAA.cpp:159-371、getTypeInfoHelper）:

if (const BuiltinType *BTy = dyn_cast<BuiltinType>(Ty)) {
  switch (BTy->getKind()) {
  case BuiltinType::Char_U:
  case BuiltinType::Char_S:
  case BuiltinType::UChar:
  case BuiltinType::SChar:
    return getChar();
  case BuiltinType::UShort:
    return getTypeInfo(Context.ShortTy);
  case BuiltinType::UInt:
    return getTypeInfo(Context.IntTy);
  // ... etc.
  }
}

2 つの設計上の決定に注目してください: (1) char の各種バリアントは全て同じノードに潰される（全部があらゆるものとエイリアスする）。(2) 符号なし整数型は対応する符号付きと同じノードを共有する（C が int と unsigned int はエイリアスしうると定めているため）。

アクセスタグ（CodeGenTBAA.cpp:629-655、getAccessTagInfo）:

llvm::MDNode *CodeGenTBAA::getAccessTagInfo(TBAAAccessInfo Info) {
  ...
  if (Info.isMayAlias())
    Info = TBAAAccessInfo(getChar(), Info.Size);
  ...
  return N = MDHelper.createTBAAStructTagNode(
      Info.BaseType, Info.AccessType, Info.Offset);
}

出力が最終的に load や store 命令に付加される関数です。冒頭の逃げ道に注目: アクセスが may_alias タグ付き（例えば C ソースで __attribute__((may_alias)) が使われた場合）なら、アクセス型は万能 char に置き換えられ、そのアクセスについては TBAA が実質的に無効化されます。

解析が呼ばれる場所

最適化器は TBAA を直接呼びません。代わりに集約された AAResults オブジェクトに問い合わせ、それが複数のエイリアス解析プロバイダをチェーンします。TBAA はそのプロバイダの一つです。エントリポイントは TypeBasedAAResult::alias（TypeBasedAliasAnalysis.cpp:376-387）:

AliasResult TypeBasedAAResult::alias(const MemoryLocation &LocA,
                                     const MemoryLocation &LocB,
                                     AAQueryInfo &AAQI, const Instruction *) {
  if (!shouldUseTBAA())
    return AliasResult::MayAlias;

  if (Aliases(LocA.AATags.TBAA, LocB.AATags.TBAA))
    return AliasResult::MayAlias;

  // Otherwise return a definitive result.
  return AliasResult::NoAlias;
}

この関数の形はよく見る価値があります: TBAA は 否定の証明 です。非エイリアシングを証明できたときにだけ NoAlias を返し、そうでなければ MayAlias にフォールバックして他の解析に任せます。

Aliases() は matchAccessTags の 1 行ラッパーです（TypeBasedAliasAnalysis.cpp:728-730）:

bool TypeBasedAAResult::Aliases(const MDNode *A, const MDNode *B) const {
  return matchAccessTags(A, B);
}

`matchAccessTags` を追う

本当の仕事はここで行われます。関数は TypeBasedAliasAnalysis.cpp:679-724 にあります。簡略化すると:

static bool matchAccessTags(const MDNode *A, const MDNode *B,
                            const MDNode **GenericTag) {
  if (A == B) {                           // ①
    if (GenericTag) *GenericTag = A;
    return true;
  }

  if (!A || !B) {                         // ②
    if (GenericTag) *GenericTag = nullptr;
    return true;
  }

  TBAAStructTagNode TagA(A), TagB(B);
  const MDNode *CommonType = getLeastCommonType(
      TagA.getAccessType(), TagB.getAccessType());   // ③

  if (!CommonType) {                      // ④
    if (GenericTag) *GenericTag = nullptr;
    return true;
  }

  bool MayAlias;
  if (mayBeAccessToSubobjectOf(TagA, TagB, CommonType, GenericTag, MayAlias) || // ⑤
      mayBeAccessToSubobjectOf(TagB, TagA, CommonType, GenericTag, MayAlias))
    return MayAlias;

  if (GenericTag) *GenericTag = createAccessTag(CommonType);   // ⑥
  return false;
}

aliastest.ll の 2 つの関数をこれで追ってみましょう。

`test0_yes` のトレース

入力: A = !1 = {!7, !7, 0}（型 foo）、B = !2 = {!8, !8, 0}（型 bar）。!7 と !8 の親はどちらも !0（同じルート）。

ステップ ①: !1 != !2、スキップ。
ステップ ②: 両方 non-null、スキップ。
ステップ ③: !7（foo）と !8（bar）の最小共通型を計算。

LCA の計算は TypeBasedAliasAnalysis.cpp:503-540 にあります:

static const MDNode *getLeastCommonType(const MDNode *A, const MDNode *B) {
  if (!A || !B) return nullptr;
  if (A == B) return A;

  SmallSetVector<const MDNode *, 4> PathA;
  TBAANode TA(A);
  while (TA.getNode()) {
    if (!PathA.insert(TA.getNode()))
      report_fatal_error("Cycle found in TBAA metadata.");
    TA = TA.getParent();
  }
  SmallSetVector<const MDNode *, 4> PathB;
  TBAANode TB(B);
  while (TB.getNode()) {
    if (!PathB.insert(TB.getNode()))
      report_fatal_error("Cycle found in TBAA metadata.");
    TB = TB.getParent();
  }

  int IA = PathA.size() - 1;
  int IB = PathB.size() - 1;
  const MDNode *Ret = nullptr;
  while (IA >= 0 && IB >= 0) {
    if (PathA[IA] == PathB[IB]) Ret = PathA[IA];
    else break;
    --IA; --IB;
  }
  return Ret;
}

トレース:

PathA = [!7(foo), !0(root)]
PathB = [!8(bar), !0(root)]
ルート側から比較: PathA[1] == PathB[1]（両方 !0）→ Ret = !0。次に PathA[0] != PathB[0]（foo と bar）→ break。
!0（ルートが共通先祖）を返す。

matchAccessTags に戻ると:

ステップ ④: CommonType = !0 は non-null、スキップ。
ステップ ⑤: mayBeAccessToSubobjectOf(foo, bar, root, ...) を呼ぶ。

その関数（TypeBasedAliasAnalysis.cpp:607-674）は「一方のアクセスが他方のサブフィールドに到達し得るか」を証明しようとします。フィールドを持たないスカラー型の場合、getField() を 1 回歩いて何も得られず、そのままあきらめます。どちらの方向も成功しません。

ステップ ⑥: ここに到達。false を返す。

matchAccessTags が false → Aliases が false → alias() が NoAlias を返します。これで GVN は最初のロードを 2 番目に転送でき、%z = add i8 %x, %x となります。まさにテストが期待する結果です。

`test0_no` のトレース

test0_yes と同じ形ですが、2 つのアクセスは 異なるルート の下にあります — つまり無関係な 2 つの型ツリーに属しています:

!3 = !{!9, !9, i64 0}
!4 = !{!10, !10, i64 0}
!9  = !{ !"foo", !0 }      ; !0 に根ざす
!10 = !{ !"bar", !12 }     ; 別のルートに根ざす
!12 = !{!"different"}

getLeastCommonType(!9, !10) を実行:

PathA = [!9, !0]
PathB = [!10, !12]
先頭から比較: !0 != !12 — 一致せず即座に break。
nullptr を返す。

するとステップ ④ が発動します:

if (!CommonType) return true;

matchAccessTags が true（エイリアスし得る）を返し、alias() が MayAlias を返し、GVN は両方のロードをそのまま残します。テストの CHECK: add i8 %x, %y アサーションが通ります。

教訓: 異なるツリーのノードは比較不可能 — 共通の先祖がない場合、TBAA はあきらめて「エイリアスしうる」と言います。これが、異なるフロントエンドから IR をリンクしたときに「Rust の i32 は C++ の int とエイリアスしない」と誤って結論づけないためのセーフティネットです。

Struct-path TBAA: バイトオフセットの導入

aliastest.ll の例は古い「スカラー」形式を使っています。実際の C++ コードは struct-path TBAA を使い、フィールドオフセットを追加することで StructA.f32 と StructB.f16 のような比較を精密に扱えます。

llvm/test/Analysis/TypeBasedAliasAnalysis/tbaa-path-new.ll:271-290 のメタデータ側を見てみましょう:

!2 = !{!3, !3, i64 0, i64 4}              ; access tag: uint32_t
!3 = !{!4, i64 4, !"int"}                 ; scalar type: int, parent=char
!4 = !{!5, i64 1, !"omnipotent char"}     ; omnipotent char, parent=root
!5 = !{!"Simple C++ TBAA"}                ; root

!6 = !{!7, !3, i64 4, i64 4}              ; access tag: StructA.f32 (offset 4, size 4)
!7 = !{!4, i64 16, !"_ZTS7StructA",
       !8, i64 0, i64 2,                  ; short f16 @ offset 0
       !3, i64 4, i64 4,                  ; int   f32 @ offset 4
       !8, i64 8, i64 2,
       !3, i64 12, i64 4}

型ノードは全体サイズと (フィールド型, オフセット, サイズ) の 3 つ組のリストを持つようになりました。アクセスタグはベース型、アクセス型、オフセット、アクセスサイズを含みます。マングル名 _ZTS7StructA（Itanium C++ ABI）が翻訳単位をまたいだ構造体同一性を保証しており、これが LTO 下で TBAA が機能する鍵です。

これらのタグのマッチングコードは mayBeAccessToSubobjectOf（TypeBasedAliasAnalysis.cpp:607-674）です。中核ループはこれ:

TBAAStructTypeNode BaseType(BaseTag.getBaseType());
uint64_t OffsetInBase = BaseTag.getOffset();

for (;;) {
  if (!BaseType.getNode()) break;

  if (BaseType.getNode() == SubobjectTag.getBaseType()) {
    MayAlias = OffsetInBase == SubobjectTag.getOffset() ||
               BaseType.getNode() == BaseTag.getAccessType() ||
               SubobjectTag.getBaseType() == SubobjectTag.getAccessType();
    return true;
  }

  if (NewFormat && BaseType.getNode() == BaseTag.getAccessType())
    break;

  BaseType = BaseType.getField(OffsetInBase);
}

TBAAStructTypeNode::getField(Offset&)（TypeBasedAliasAnalysis.cpp:306-362）は Offset を含むフィールドを見つけ、その中に降りていき、Offset をそのフィールドからの相対値に調整します。これにより解析は StructB.a.f32 をバイト単位で文字通り辿れます: StructB にオフセット 8 で入り、4 を引き（StructB 内で a が始まる位置）、StructA 内のオフセット 4 に着地し、int フィールドを見つける。この包含連鎖のどこかで相手のオフセットを正当化できなければ、mayBeAccessToSubobjectOf は false を返して NoAlias となります。

tbaa-path-new.ll の 2 番目のテストは、この精度が何を買ってくれるかを示しています:

store i32 1, ptr %s, align 4, !tbaa !2    ; int を書き込み
store i16 4, ptr %A, align 4, !tbaa !9    ; short を書き込み
ret i32 1

2 つのアクセスはアドレスが重なっていますが、アクセス型が異なります。型ツリー上で int と short はどちらも char の子 — 互いに兄弟であり、先祖・子孫関係にはない。どちらも相手の型を「通り抜けて」到達することはできないので、matchAccessTags は NoAlias と結論します。すると store i32 1 は store i16 4 を生きたまま横切れることが分かり、定数伝播で戻り値を 1 に畳むことができます。

あちこちに出てくるヘルパークラス

小さなラッパークラスをいくつか（TypeBasedAliasAnalysis.cpp:150-362）:

template<typename MDNodeTy>
class TBAANodeImpl {
  MDNodeTy *Node = nullptr;
public:
  TBAANodeImpl<MDNodeTy> getParent() const {
    if (isNewFormat())
      return TBAANodeImpl(cast<MDNodeTy>(Node->getOperand(0)));
    if (Node->getNumOperands() < 2)
      return TBAANodeImpl<MDNodeTy>();
    MDNodeTy *P = dyn_cast_or_null<MDNodeTy>(Node->getOperand(1));
    return TBAANodeImpl<MDNodeTy>(P);
  }

  bool isTypeImmutable() const {
    if (Node->getNumOperands() < 3) return false;
    ConstantInt *CI = mdconst::dyn_extract<ConstantInt>(Node->getOperand(2));
    return CI && CI->getValue()[0];
  }
};

TBAANode は汎用的な走査ヘルパーです — getLeastCommonType が使っているのはこれ。TBAAStructTagNode はアクセスタグ用に同じことをします（ベース型、アクセス型、オフセット、サイズを読む）。TBAAStructTypeNode は mayBeAccessToSubobjectOf が使うフィールドナビゲーションを提供します。LLVM の他の場所で TBAA を扱う A->getOperand(2) 風のコードを見かけたら、ほぼ必ずこれらのラッパーを経由しています。

頭に入れておくべきこと

次の 4 点を覚えて帰ってください:

TBAA は NoAlias の証明である。 解析が役に立つのは非エイリアシングを決定的に証明できたときだけ。あいまいなら全て MayAlias になる。
型はフロントエンドごとのルートに根ざした木を形成する。 char はルートのすぐ下にあり、ほぼ全てのスカラー型の先祖 — これが C の文字アクセス特例のエンコード方法です。ある型から親方向に辿ると必ず char を通る。
最適化器が比較するのは型ではなくアクセスタグ。 タグは {ベース型, アクセス型, オフセット, サイズ} で、全ての load と store に付与されている。
Struct-path TBAA はオフセットを追加する。 2 つの struct-path アクセスタグの比較は、それらのオフセットに従って構造体レイアウトを下に辿ることに帰着する。辿れない場合、2 つのアクセスは互いに素と証明される。

さらにソースを読みたい場合、手で辿る価値がある関数は 3 つ: matchAccessTags（ディスパッチャ）、getLeastCommonType（比較可能性チェック）、mayBeAccessToSubobjectOf（精度のエンジン）。他は全て簿記とメタデータ配管です。

LLVM の Type-Based Alias Analysis は実際どう動くのか（日本語版）