1 //! A framework that can express both [gen-kill] and generic dataflow problems.
3 //! To actually use this framework, you must implement either the `Analysis` or the
4 //! `GenKillAnalysis` trait. If your transfer function can be expressed with only gen/kill
5 //! operations, prefer `GenKillAnalysis` since it will run faster while iterating to fixpoint. The
6 //! `impls` module contains several examples of gen/kill dataflow analyses.
8 //! Create an `Engine` for your analysis using the `into_engine` method on the `Analysis` trait,
9 //! then call `iterate_to_fixpoint`. From there, you can use a `ResultsCursor` to inspect the
10 //! fixpoint solution to your dataflow problem, or implement the `ResultsVisitor` interface and use
11 //! `visit_results`. The following example uses the `ResultsCursor` approach.
13 //! ```ignore(cross-crate-imports)
14 //! use rustc_mir::dataflow::Analysis; // Makes `into_engine` available.
16 //! fn do_my_analysis(tcx: TyCtxt<'tcx>, body: &mir::Body<'tcx>) {
17 //! let analysis = MyAnalysis::new()
18 //! .into_engine(tcx, body)
19 //! .iterate_to_fixpoint()
20 //! .into_results_cursor(body);
22 //! // Print the dataflow state *after* each statement in the start block.
23 //! for (_, statement_index) in body.block_data[START_BLOCK].statements.iter_enumerated() {
24 //! cursor.seek_after(Location { block: START_BLOCK, statement_index });
25 //! let state = cursor.get();
26 //! println!("{:?}", state);
31 //! [gen-kill]: https://en.wikipedia.org/wiki/Data-flow_analysis#Bit_vector_problems
33 use std::borrow::BorrowMut;
34 use std::cmp::Ordering;
36 use rustc_index::bit_set::{BitSet, HybridBitSet};
37 use rustc_index::vec::Idx;
38 use rustc_middle::mir::{self, BasicBlock, Location};
39 use rustc_middle::ty::TyCtxt;
49 pub use self::cursor::{ResultsCursor, ResultsRefCursor};
50 pub use self::direction::{Backward, Direction, Forward};
51 pub use self::engine::{Engine, Results};
52 pub use self::lattice::{JoinSemiLattice, MeetSemiLattice};
53 pub use self::visitor::{visit_results, ResultsVisitor};
54 pub use self::visitor::{BorrowckFlowState, BorrowckResults};
56 /// Define the domain of a dataflow problem.
58 /// This trait specifies the lattice on which this analysis operates (the domain) as well as its
59 /// initial value at the entry point of each basic block.
60 pub trait AnalysisDomain<'tcx> {
61 /// The type that holds the dataflow state at any given point in the program.
62 type Domain: Clone + JoinSemiLattice;
64 /// The direction of this analysis. Either `Forward` or `Backward`.
65 type Direction: Direction = Forward;
67 /// A descriptive name for this analysis. Used only for debugging.
69 /// This name should be brief and contain no spaces, periods or other characters that are not
70 /// suitable as part of a filename.
71 const NAME: &'static str;
73 /// The initial value of the dataflow state upon entry to each basic block.
74 fn bottom_value(&self, body: &mir::Body<'tcx>) -> Self::Domain;
76 /// Mutates the initial value of the dataflow state upon entry to the `START_BLOCK`.
78 /// For backward analyses, initial state besides the bottom value is not yet supported. Trying
79 /// to mutate the initial state will result in a panic.
81 // FIXME: For backward dataflow analyses, the initial state should be applied to every basic
82 // block where control flow could exit the MIR body (e.g., those terminated with `return` or
83 // `resume`). It's not obvious how to handle `yield` points in generators, however.
84 fn initialize_start_block(&self, body: &mir::Body<'tcx>, state: &mut Self::Domain);
87 /// A dataflow problem with an arbitrarily complex transfer function.
91 /// When implementing this trait directly (not via [`GenKillAnalysis`]), it's possible to choose a
92 /// transfer function such that the analysis does not reach fixpoint. To guarantee convergence,
93 /// your transfer functions must maintain the following invariant:
95 /// > If the dataflow state **before** some point in the program changes to be greater
96 /// than the prior state **before** that point, the dataflow state **after** that point must
97 /// also change to be greater than the prior state **after** that point.
99 /// This invariant guarantees that the dataflow state at a given point in the program increases
100 /// monotonically until fixpoint is reached. Note that this monotonicity requirement only applies
101 /// to the same point in the program at different points in time. The dataflow state at a given
102 /// point in the program may or may not be greater than the state at any preceding point.
103 pub trait Analysis<'tcx>: AnalysisDomain<'tcx> {
104 /// Updates the current dataflow state with the effect of evaluating a statement.
105 fn apply_statement_effect(
107 state: &mut Self::Domain,
108 statement: &mir::Statement<'tcx>,
112 /// Updates the current dataflow state with an effect that occurs immediately *before* the
115 /// This method is useful if the consumer of the results of this analysis needs only to observe
116 /// *part* of the effect of a statement (e.g. for two-phase borrows). As a general rule,
117 /// analyses should not implement this without implementing `apply_statement_effect`.
118 fn apply_before_statement_effect(
120 _state: &mut Self::Domain,
121 _statement: &mir::Statement<'tcx>,
126 /// Updates the current dataflow state with the effect of evaluating a terminator.
128 /// The effect of a successful return from a `Call` terminator should **not** be accounted for
129 /// in this function. That should go in `apply_call_return_effect`. For example, in the
130 /// `InitializedPlaces` analyses, the return place for a function call is not marked as
131 /// initialized here.
132 fn apply_terminator_effect(
134 state: &mut Self::Domain,
135 terminator: &mir::Terminator<'tcx>,
139 /// Updates the current dataflow state with an effect that occurs immediately *before* the
140 /// given terminator.
142 /// This method is useful if the consumer of the results of this analysis needs only to observe
143 /// *part* of the effect of a terminator (e.g. for two-phase borrows). As a general rule,
144 /// analyses should not implement this without implementing `apply_terminator_effect`.
145 fn apply_before_terminator_effect(
147 _state: &mut Self::Domain,
148 _terminator: &mir::Terminator<'tcx>,
153 /* Edge-specific effects */
155 /// Updates the current dataflow state with the effect of a successful return from a `Call`
158 /// This is separate from `apply_terminator_effect` to properly track state across unwind
160 fn apply_call_return_effect(
162 state: &mut Self::Domain,
164 func: &mir::Operand<'tcx>,
165 args: &[mir::Operand<'tcx>],
166 return_place: mir::Place<'tcx>,
169 /// Updates the current dataflow state with the effect of resuming from a `Yield` terminator.
171 /// This is similar to `apply_call_return_effect` in that it only takes place after the
172 /// generator is resumed, not when it is dropped.
174 /// By default, no effects happen.
175 fn apply_yield_resume_effect(
177 _state: &mut Self::Domain,
178 _resume_block: BasicBlock,
179 _resume_place: mir::Place<'tcx>,
183 /// Updates the current dataflow state with the effect of taking a particular branch in a
184 /// `SwitchInt` terminator.
186 /// Unlike the other edge-specific effects, which are allowed to mutate `Self::Domain`
187 /// directly, overriders of this method must pass a callback to
188 /// `SwitchIntEdgeEffects::apply`. The callback will be run once for each outgoing edge and
189 /// will have access to the dataflow state that will be propagated along that edge.
191 /// This interface is somewhat more complex than the other visitor-like "effect" methods.
192 /// However, it is both more ergonomic—callers don't need to recompute or cache information
193 /// about a given `SwitchInt` terminator for each one of its edges—and more efficient—the
194 /// engine doesn't need to clone the exit state for a block unless
195 /// `SwitchIntEdgeEffects::apply` is actually called.
197 /// FIXME: This class of effects is not supported for backward dataflow analyses.
198 fn apply_switch_int_edge_effects(
201 _discr: &mir::Operand<'tcx>,
202 _apply_edge_effects: &mut impl SwitchIntEdgeEffects<Self::Domain>,
206 /* Extension methods */
208 /// Creates an `Engine` to find the fixpoint for this dataflow problem.
210 /// You shouldn't need to override this outside this module, since the combination of the
211 /// default impl and the one for all `A: GenKillAnalysis` will do the right thing.
212 /// Its purpose is to enable method chaining like so:
214 /// ```ignore(cross-crate-imports)
215 /// let results = MyAnalysis::new(tcx, body)
216 /// .into_engine(tcx, body, def_id)
217 /// .iterate_to_fixpoint()
218 /// .into_results_cursor(body);
220 fn into_engine(self, tcx: TyCtxt<'tcx>, body: &'mir mir::Body<'tcx>) -> Engine<'mir, 'tcx, Self>
224 Engine::new_generic(tcx, body, self)
228 /// A gen/kill dataflow problem.
230 /// Each method in this trait has a corresponding one in `Analysis`. However, these methods only
231 /// allow modification of the dataflow state via "gen" and "kill" operations. By defining transfer
232 /// functions for each statement in this way, the transfer function for an entire basic block can
233 /// be computed efficiently.
235 /// `Analysis` is automatically implemented for all implementers of `GenKillAnalysis`.
236 pub trait GenKillAnalysis<'tcx>: Analysis<'tcx> {
239 /// See `Analysis::apply_statement_effect`.
242 trans: &mut impl GenKill<Self::Idx>,
243 statement: &mir::Statement<'tcx>,
247 /// See `Analysis::apply_before_statement_effect`.
248 fn before_statement_effect(
250 _trans: &mut impl GenKill<Self::Idx>,
251 _statement: &mir::Statement<'tcx>,
256 /// See `Analysis::apply_terminator_effect`.
257 fn terminator_effect(
259 trans: &mut impl GenKill<Self::Idx>,
260 terminator: &mir::Terminator<'tcx>,
264 /// See `Analysis::apply_before_terminator_effect`.
265 fn before_terminator_effect(
267 _trans: &mut impl GenKill<Self::Idx>,
268 _terminator: &mir::Terminator<'tcx>,
273 /* Edge-specific effects */
275 /// See `Analysis::apply_call_return_effect`.
276 fn call_return_effect(
278 trans: &mut impl GenKill<Self::Idx>,
280 func: &mir::Operand<'tcx>,
281 args: &[mir::Operand<'tcx>],
282 return_place: mir::Place<'tcx>,
285 /// See `Analysis::apply_yield_resume_effect`.
286 fn yield_resume_effect(
288 _trans: &mut impl GenKill<Self::Idx>,
289 _resume_block: BasicBlock,
290 _resume_place: mir::Place<'tcx>,
294 /// See `Analysis::apply_switch_int_edge_effects`.
295 fn switch_int_edge_effects<G: GenKill<Self::Idx>>(
298 _discr: &mir::Operand<'tcx>,
299 _edge_effects: &mut impl SwitchIntEdgeEffects<G>,
304 impl<A> Analysis<'tcx> for A
306 A: GenKillAnalysis<'tcx>,
307 A::Domain: GenKill<A::Idx> + BorrowMut<BitSet<A::Idx>>,
309 fn apply_statement_effect(
311 state: &mut A::Domain,
312 statement: &mir::Statement<'tcx>,
315 self.statement_effect(state, statement, location);
318 fn apply_before_statement_effect(
320 state: &mut A::Domain,
321 statement: &mir::Statement<'tcx>,
324 self.before_statement_effect(state, statement, location);
327 fn apply_terminator_effect(
329 state: &mut A::Domain,
330 terminator: &mir::Terminator<'tcx>,
333 self.terminator_effect(state, terminator, location);
336 fn apply_before_terminator_effect(
338 state: &mut A::Domain,
339 terminator: &mir::Terminator<'tcx>,
342 self.before_terminator_effect(state, terminator, location);
345 /* Edge-specific effects */
347 fn apply_call_return_effect(
349 state: &mut A::Domain,
351 func: &mir::Operand<'tcx>,
352 args: &[mir::Operand<'tcx>],
353 return_place: mir::Place<'tcx>,
355 self.call_return_effect(state, block, func, args, return_place);
358 fn apply_yield_resume_effect(
360 state: &mut A::Domain,
361 resume_block: BasicBlock,
362 resume_place: mir::Place<'tcx>,
364 self.yield_resume_effect(state, resume_block, resume_place);
367 fn apply_switch_int_edge_effects(
370 discr: &mir::Operand<'tcx>,
371 edge_effects: &mut impl SwitchIntEdgeEffects<A::Domain>,
373 self.switch_int_edge_effects(block, discr, edge_effects);
376 /* Extension methods */
378 fn into_engine(self, tcx: TyCtxt<'tcx>, body: &'mir mir::Body<'tcx>) -> Engine<'mir, 'tcx, Self>
382 Engine::new_gen_kill(tcx, body, self)
386 /// The legal operations for a transfer function in a gen/kill problem.
388 /// This abstraction exists because there are two different contexts in which we call the methods in
389 /// `GenKillAnalysis`. Sometimes we need to store a single transfer function that can be efficiently
390 /// applied multiple times, such as when computing the cumulative transfer function for each block.
391 /// These cases require a `GenKillSet`, which in turn requires two `BitSet`s of storage. Oftentimes,
392 /// however, we only need to apply an effect once. In *these* cases, it is more efficient to pass the
393 /// `BitSet` representing the state vector directly into the `*_effect` methods as opposed to
394 /// building up a `GenKillSet` and then throwing it away.
395 pub trait GenKill<T> {
396 /// Inserts `elem` into the state vector.
397 fn gen(&mut self, elem: T);
399 /// Removes `elem` from the state vector.
400 fn kill(&mut self, elem: T);
402 /// Calls `gen` for each element in `elems`.
403 fn gen_all(&mut self, elems: impl IntoIterator<Item = T>) {
409 /// Calls `kill` for each element in `elems`.
410 fn kill_all(&mut self, elems: impl IntoIterator<Item = T>) {
417 /// Stores a transfer function for a gen/kill problem.
419 /// Calling `gen`/`kill` on a `GenKillSet` will "build up" a transfer function so that it can be
420 /// applied multiple times efficiently. When there are multiple calls to `gen` and/or `kill` for
421 /// the same element, the most recent one takes precedence.
423 pub struct GenKillSet<T> {
424 gen: HybridBitSet<T>,
425 kill: HybridBitSet<T>,
428 impl<T: Idx> GenKillSet<T> {
429 /// Creates a new transfer function that will leave the dataflow state unchanged.
430 pub fn identity(universe: usize) -> Self {
432 gen: HybridBitSet::new_empty(universe),
433 kill: HybridBitSet::new_empty(universe),
437 pub fn apply(&self, state: &mut BitSet<T>) {
438 state.union(&self.gen);
439 state.subtract(&self.kill);
443 impl<T: Idx> GenKill<T> for GenKillSet<T> {
444 fn gen(&mut self, elem: T) {
445 self.gen.insert(elem);
446 self.kill.remove(elem);
449 fn kill(&mut self, elem: T) {
450 self.kill.insert(elem);
451 self.gen.remove(elem);
455 impl<T: Idx> GenKill<T> for BitSet<T> {
456 fn gen(&mut self, elem: T) {
460 fn kill(&mut self, elem: T) {
465 impl<T: Idx> GenKill<T> for lattice::Dual<BitSet<T>> {
466 fn gen(&mut self, elem: T) {
470 fn kill(&mut self, elem: T) {
475 // NOTE: DO NOT CHANGE VARIANT ORDER. The derived `Ord` impls rely on the current order.
476 #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
478 /// The "before" effect (e.g., `apply_before_statement_effect`) for a statement (or
482 /// The "primary" effect (e.g., `apply_statement_effect`) for a statement (or terminator).
487 pub const fn at_index(self, statement_index: usize) -> EffectIndex {
488 EffectIndex { effect: self, statement_index }
492 #[derive(Clone, Copy, Debug, PartialEq, Eq)]
493 pub struct EffectIndex {
494 statement_index: usize,
499 fn next_in_forward_order(self) -> Self {
501 Effect::Before => Effect::Primary.at_index(self.statement_index),
502 Effect::Primary => Effect::Before.at_index(self.statement_index + 1),
506 fn next_in_backward_order(self) -> Self {
508 Effect::Before => Effect::Primary.at_index(self.statement_index),
509 Effect::Primary => Effect::Before.at_index(self.statement_index - 1),
513 /// Returns `true` if the effect at `self` should be applied eariler than the effect at `other`
514 /// in forward order.
515 fn precedes_in_forward_order(self, other: Self) -> bool {
518 .cmp(&other.statement_index)
519 .then_with(|| self.effect.cmp(&other.effect));
520 ord == Ordering::Less
523 /// Returns `true` if the effect at `self` should be applied earlier than the effect at `other`
524 /// in backward order.
525 fn precedes_in_backward_order(self, other: Self) -> bool {
528 .cmp(&self.statement_index)
529 .then_with(|| self.effect.cmp(&other.effect));
530 ord == Ordering::Less
534 pub struct SwitchIntTarget {
535 pub value: Option<u128>,
536 pub target: BasicBlock,
539 /// A type that records the edge-specific effects for a `SwitchInt` terminator.
540 pub trait SwitchIntEdgeEffects<D> {
541 /// Calls `apply_edge_effect` for each outgoing edge from a `SwitchInt` terminator and
542 /// records the results.
543 fn apply(&mut self, apply_edge_effect: impl FnMut(&mut D, SwitchIntTarget));