データフロー解析

MIR に取り組む場合、さまざまな種類のデータフロー解析に頻繁に出くわすことになります。rustc はデータフローを使用して、未初期化変数を見つけたり、generator の yield 文をまたいでどの変数が生存しているかを判定したり、制御フローグラフ内の特定の時点でどの Place が借用されているかを計算したりします。データフロー解析は現代のコンパイラにおける基本的な概念であり、この主題に関する知識は、将来のコントリビューターにとって役立つでしょう。

ただし、このドキュメントはデータフロー解析の一般的な入門ではありません。これは、rustc でこれらの解析を定義するために使用されるフレームワークの説明にすぎません。このドキュメントは、読者が中核となる考え方や、「転送関数」、「不動点」、「束」といった基本的な用語に精通していることを前提としています。これらの用語になじみがない場合や、手早く復習したい場合は、Anders Møller と Michael I. Schwartzbach による Static Program Analysis が、無料で利用できる優れた教科書です。視聴覚による学習を好む方には、以前は Goethe University Frankfurt による YouTube の短い講義シリーズを推奨していましたが、その後削除されました。背景についてはこの PR を、代替講義についてはこのコメントを参照してください。

データフロー解析の定義

データフロー解析は Analysis トレイトによって定義されます。データフロー状態の型に加えて、このトレイトは各ブロックへの入口におけるその状態の初期値と、解析の方向（順方向または逆方向）を定義します。データフロー解析のドメインは、適切に振る舞う join 演算子を持つ束（厳密には結合半束）でなければなりません。詳細については、lattice モジュールのドキュメント、および JoinSemiLattice トレイトを参照してください。

転送関数と効果

rustc のデータフローフレームワークでは、基本ブロック内の各文（および終端子）が独自の転送関数を定義できます。簡潔にするため、これら個々の転送関数は「効果」と呼ばれます。各効果はデータフロー順に順次適用され、それらが合わさって基本ブロック全体の転送関数を定義します。一部の終端子の特定の出力エッジに対して効果を定義することも可能です（例: Call 終端子の success エッジに対する apply_call_return_effect）。これらはまとめて「エッジごとの効果」と呼ばれます。

「前」効果

ドキュメントを注意深く読んだ読者は、各文と終端子には実際には 2 つ の可能な効果、すなわち「前」効果と、接頭辞なし（または「主要」）効果があることに気づくかもしれません。「前」効果は、解析の方向に関係なく、接頭辞なし効果の直前に適用されます。言い換えると、逆方向解析は、順方向解析と同様に、基本ブロックの転送関数を計算するときに「前」効果を適用し、その後「主要」効果を適用します。

解析の大多数は、接頭辞なし効果のみを使用すべきです。各文に複数の効果があると、利用者にとってどこを見るべきかが分かりにくくなります。ただし、「前」バリアントは、代入文の右辺の効果を左辺とは別に考慮しなければならない場合など、いくつかのシナリオで有用です。

収束

解析は「不動点」に収束しなければなりません。そうでなければ、永遠に実行され続けます。不動点に収束するとは、「平衡に達する」と言い換えることができます。平衡に達するためには、解析はいくつかの法則に従わなければなりません。従わなければならない法則の 1 つは、ボトム値¹ と他の値を結合すると、その 2 つ目の値に等しくなるというものです。式で表すと、次のようになります。

bottom join x = x

もう 1 つの法則は、解析が「トップ値」を持たなければならないというもので、次のようになります。

top join x = top

トップ値があることで、半束が有限の高さを持つことが保証されます。また、上に述べた法則により、データフロー状態がいったんトップに達すると、それ以上変化しなくなることが保証されます（不動点はトップになります）。

簡単な例

このセクションでは、単純なデータフロー解析の簡単な例を高レベルで示します。知っておく必要のあるすべてを説明するわけではありませんが、このページの残りの部分をより明確に理解できるようになることを期待しています。

プログラム内のある時点までに mem::transmute が呼び出された可能性があるかどうかを調べる、単純な解析を行いたいとしましょう。解析ドメインは、これまでに transmute が呼び出されたかどうかを記録する bool だけにします。デフォルトでは transmute は呼び出されていないため、ボトム値は false になります。transmute が呼び出されたと判定した時点で解析は完了するため、トップ値は true になります。結合演算子は単に論理 OR（||）演算子にします。AND ではなく OR を使用するのは、次のようなケースがあるためです。

#![allow(unused)]
fn main() {
unsafe fn example(some_cond: bool) {
let x = if some_cond {
    std::mem::transmute::<i32, u32>(0_i32) // transmute が呼び出された！
} else {
    1_u32 // transmute は呼び出されていない
};

// この時点までに transmute は呼び出されたか？ 保守的に yes と近似する。
// そのため、OR 演算子を使用する。
println!("x: {}", x);
}
}

データフロー解析の結果を調べる

解析を構築したら、iterate_to_fixpoint を呼び出す必要があります。これは Results を返し、Results には各ブロックの入口における不動点でのデータフロー状態が含まれています。Results が得られたら、CFG 内の任意の時点で、不動点におけるデータフロー状態を調べることができます。少数の位置（例: 各 Drop 終端子）でのみ状態が必要な場合は、ResultsCursor を使用します。すべての位置で状態が必要な場合は、ResultsVisitor の方が効率的です。

                         Analysis
                            |
                            | iterate_to_fixpoint()
                            |
                         Results
                         /     \
 into_results_cursor(…) /       \  visit_with(…)
                       /         \
               ResultsCursor  ResultsVisitor

たとえば、次のコードは ResultsVisitor を使用します…

// `MyVisitor` が `ResultsVisitor<FlowState = MyAnalysis::Domain>` を実装していると仮定する...
let mut my_visitor = MyVisitor::new();

// RPO 内のすべてのブロック内のすべての位置について、不動点状態を調べる。
let results = MyAnalysis::new()
    .iterate_to_fixpoint(tcx, body, None);
results.visit_with(body, &mut my_visitor);`

一方、このコードは ResultsCursor を使用します。

let mut results = MyAnalysis::new()
    .iterate_to_fixpoint(tcx, body, None);
    .into_results_cursor(body);

// 各 `Drop` 終端子の直前の不動点状態を調べる。
for (bb, block) in body.basic_blocks().iter_enumerated() {
    if let TerminatorKind::Drop { .. } = block.terminator().kind {
        results.seek_before_primary_effect(body.terminator_loc(bb));
        let state = results.get();
        println!("state before drop: {:#?}", state);
    }
}

Graphviz 図

データフロー解析の結果が期待どおりでない場合、それらを可視化すると役に立つことがよくあります。これは Debugging MIR で説明されている -Z dump-mir フラグを使って行えます。まずは -Z dump-mir=F -Z dump-mir-dataflow から始めてください。ここで F は “all”、または関心のある MIR 本体の名前です。

これらの .dot ファイルは mir_dump ディレクトリに保存され、ファイル名の一部として解析の NAME（例: maybe_inits）を含みます。各可視化では、各ブロックの入口と出口における完全なデータフロー状態に加えて、各文およびターミネータで発生するあらゆる変更が表示されます。以下の例を参照してください。

データフロー解析の graphviz ダイアグラム

ボトム値の主な目的は、初期データフロー状態としての役割です。各基本ブロックの入口状態は、解析開始前にボトムに初期化されます。 ↩

Keyboard shortcuts

Rust Compiler Development Guide