1 //! A framework that can express both [gen-kill] and generic dataflow problems.
3 //! To use this framework, 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_const_eval::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::cmp::Ordering;
35 use rustc_index::bit_set::{BitSet, ChunkedBitSet, HybridBitSet};
36 use rustc_index::vec::Idx;
37 use rustc_middle::mir::{self, BasicBlock, Location};
38 use rustc_middle::ty::TyCtxt;
48 pub use self::cursor::{ResultsCursor, ResultsRefCursor};
49 pub use self::direction::{Backward, Direction, Forward};
50 pub use self::engine::{Engine, Results};
51 pub use self::lattice::{JoinSemiLattice, MeetSemiLattice};
52 pub use self::visitor::{visit_results, ResultsVisitable, ResultsVisitor};
54 /// Analysis domains are all bitsets of various kinds. This trait holds
55 /// operations needed by all of them.
56 pub trait BitSetExt<T> {
57 fn domain_size(&self) -> usize;
58 fn contains(&self, elem: T) -> bool;
59 fn union(&mut self, other: &HybridBitSet<T>);
60 fn subtract(&mut self, other: &HybridBitSet<T>);
63 impl<T: Idx> BitSetExt<T> for BitSet<T> {
64 fn domain_size(&self) -> usize {
68 fn contains(&self, elem: T) -> bool {
72 fn union(&mut self, other: &HybridBitSet<T>) {
76 fn subtract(&mut self, other: &HybridBitSet<T>) {
81 impl<T: Idx> BitSetExt<T> for ChunkedBitSet<T> {
82 fn domain_size(&self) -> usize {
86 fn contains(&self, elem: T) -> bool {
90 fn union(&mut self, other: &HybridBitSet<T>) {
94 fn subtract(&mut self, other: &HybridBitSet<T>) {
99 /// Defines the domain of a dataflow problem.
101 /// This trait specifies the lattice on which this analysis operates (the domain) as well as its
102 /// initial value at the entry point of each basic block.
103 pub trait AnalysisDomain<'tcx> {
104 /// The type that holds the dataflow state at any given point in the program.
105 type Domain: Clone + JoinSemiLattice;
107 /// The direction of this analysis. Either `Forward` or `Backward`.
108 type Direction: Direction = Forward;
110 /// A descriptive name for this analysis. Used only for debugging.
112 /// This name should be brief and contain no spaces, periods or other characters that are not
113 /// suitable as part of a filename.
114 const NAME: &'static str;
116 /// Returns the initial value of the dataflow state upon entry to each basic block.
117 fn bottom_value(&self, body: &mir::Body<'tcx>) -> Self::Domain;
119 /// Mutates the initial value of the dataflow state upon entry to the `START_BLOCK`.
121 /// For backward analyses, initial state (besides the bottom value) is not yet supported. Trying
122 /// to mutate the initial state will result in a panic.
124 // FIXME: For backward dataflow analyses, the initial state should be applied to every basic
125 // block where control flow could exit the MIR body (e.g., those terminated with `return` or
126 // `resume`). It's not obvious how to handle `yield` points in generators, however.
127 fn initialize_start_block(&self, body: &mir::Body<'tcx>, state: &mut Self::Domain);
130 /// A dataflow problem with an arbitrarily complex transfer function.
134 /// When implementing this trait directly (not via [`GenKillAnalysis`]), it's possible to choose a
135 /// transfer function such that the analysis does not reach fixpoint. To guarantee convergence,
136 /// your transfer functions must maintain the following invariant:
138 /// > If the dataflow state **before** some point in the program changes to be greater
139 /// than the prior state **before** that point, the dataflow state **after** that point must
140 /// also change to be greater than the prior state **after** that point.
142 /// This invariant guarantees that the dataflow state at a given point in the program increases
143 /// monotonically until fixpoint is reached. Note that this monotonicity requirement only applies
144 /// to the same point in the program at different points in time. The dataflow state at a given
145 /// point in the program may or may not be greater than the state at any preceding point.
146 pub trait Analysis<'tcx>: AnalysisDomain<'tcx> {
147 /// Updates the current dataflow state with the effect of evaluating a statement.
148 fn apply_statement_effect(
150 state: &mut Self::Domain,
151 statement: &mir::Statement<'tcx>,
155 /// Updates the current dataflow state with an effect that occurs immediately *before* the
158 /// This method is useful if the consumer of the results of this analysis only needs to observe
159 /// *part* of the effect of a statement (e.g. for two-phase borrows). As a general rule,
160 /// analyses should not implement this without also implementing `apply_statement_effect`.
161 fn apply_before_statement_effect(
163 _state: &mut Self::Domain,
164 _statement: &mir::Statement<'tcx>,
169 /// Updates the current dataflow state with the effect of evaluating a terminator.
171 /// The effect of a successful return from a `Call` terminator should **not** be accounted for
172 /// in this function. That should go in `apply_call_return_effect`. For example, in the
173 /// `InitializedPlaces` analyses, the return place for a function call is not marked as
174 /// initialized here.
175 fn apply_terminator_effect(
177 state: &mut Self::Domain,
178 terminator: &mir::Terminator<'tcx>,
182 /// Updates the current dataflow state with an effect that occurs immediately *before* the
183 /// given terminator.
185 /// This method is useful if the consumer of the results of this analysis needs only to observe
186 /// *part* of the effect of a terminator (e.g. for two-phase borrows). As a general rule,
187 /// analyses should not implement this without also implementing `apply_terminator_effect`.
188 fn apply_before_terminator_effect(
190 _state: &mut Self::Domain,
191 _terminator: &mir::Terminator<'tcx>,
196 /* Edge-specific effects */
198 /// Updates the current dataflow state with the effect of a successful return from a `Call`
201 /// This is separate from `apply_terminator_effect` to properly track state across unwind
203 fn apply_call_return_effect(
205 state: &mut Self::Domain,
207 return_places: CallReturnPlaces<'_, 'tcx>,
210 /// Updates the current dataflow state with the effect of resuming from a `Yield` terminator.
212 /// This is similar to `apply_call_return_effect` in that it only takes place after the
213 /// generator is resumed, not when it is dropped.
215 /// By default, no effects happen.
216 fn apply_yield_resume_effect(
218 _state: &mut Self::Domain,
219 _resume_block: BasicBlock,
220 _resume_place: mir::Place<'tcx>,
224 /// Updates the current dataflow state with the effect of taking a particular branch in a
225 /// `SwitchInt` terminator.
227 /// Unlike the other edge-specific effects, which are allowed to mutate `Self::Domain`
228 /// directly, overriders of this method must pass a callback to
229 /// `SwitchIntEdgeEffects::apply`. The callback will be run once for each outgoing edge and
230 /// will have access to the dataflow state that will be propagated along that edge.
232 /// This interface is somewhat more complex than the other visitor-like "effect" methods.
233 /// However, it is both more ergonomic—callers don't need to recompute or cache information
234 /// about a given `SwitchInt` terminator for each one of its edges—and more efficient—the
235 /// engine doesn't need to clone the exit state for a block unless
236 /// `SwitchIntEdgeEffects::apply` is actually called.
237 fn apply_switch_int_edge_effects(
240 _discr: &mir::Operand<'tcx>,
241 _apply_edge_effects: &mut impl SwitchIntEdgeEffects<Self::Domain>,
245 /* Extension methods */
247 /// Creates an `Engine` to find the fixpoint for this dataflow problem.
249 /// You shouldn't need to override this outside this module, since the combination of the
250 /// default impl and the one for all `A: GenKillAnalysis` will do the right thing.
251 /// Its purpose is to enable method chaining like so:
253 /// ```ignore (cross-crate-imports)
254 /// let results = MyAnalysis::new(tcx, body)
255 /// .into_engine(tcx, body, def_id)
256 /// .iterate_to_fixpoint()
257 /// .into_results_cursor(body);
260 fn into_engine<'mir>(
263 body: &'mir mir::Body<'tcx>,
264 ) -> Engine<'mir, 'tcx, Self>
268 Engine::new_generic(tcx, body, self)
272 /// A gen/kill dataflow problem.
274 /// Each method in this trait has a corresponding one in `Analysis`. However, these methods only
275 /// allow modification of the dataflow state via "gen" and "kill" operations. By defining transfer
276 /// functions for each statement in this way, the transfer function for an entire basic block can
277 /// be computed efficiently.
279 /// `Analysis` is automatically implemented for all implementers of `GenKillAnalysis`.
280 pub trait GenKillAnalysis<'tcx>: Analysis<'tcx> {
283 /// See `Analysis::apply_statement_effect`.
286 trans: &mut impl GenKill<Self::Idx>,
287 statement: &mir::Statement<'tcx>,
291 /// See `Analysis::apply_before_statement_effect`.
292 fn before_statement_effect(
294 _trans: &mut impl GenKill<Self::Idx>,
295 _statement: &mir::Statement<'tcx>,
300 /// See `Analysis::apply_terminator_effect`.
301 fn terminator_effect(
303 trans: &mut impl GenKill<Self::Idx>,
304 terminator: &mir::Terminator<'tcx>,
308 /// See `Analysis::apply_before_terminator_effect`.
309 fn before_terminator_effect(
311 _trans: &mut impl GenKill<Self::Idx>,
312 _terminator: &mir::Terminator<'tcx>,
317 /* Edge-specific effects */
319 /// See `Analysis::apply_call_return_effect`.
320 fn call_return_effect(
322 trans: &mut impl GenKill<Self::Idx>,
324 return_places: CallReturnPlaces<'_, 'tcx>,
327 /// See `Analysis::apply_yield_resume_effect`.
328 fn yield_resume_effect(
330 _trans: &mut impl GenKill<Self::Idx>,
331 _resume_block: BasicBlock,
332 _resume_place: mir::Place<'tcx>,
336 /// See `Analysis::apply_switch_int_edge_effects`.
337 fn switch_int_edge_effects<G: GenKill<Self::Idx>>(
340 _discr: &mir::Operand<'tcx>,
341 _edge_effects: &mut impl SwitchIntEdgeEffects<G>,
346 impl<'tcx, A> Analysis<'tcx> for A
348 A: GenKillAnalysis<'tcx>,
349 A::Domain: GenKill<A::Idx> + BitSetExt<A::Idx>,
351 fn apply_statement_effect(
353 state: &mut A::Domain,
354 statement: &mir::Statement<'tcx>,
357 self.statement_effect(state, statement, location);
360 fn apply_before_statement_effect(
362 state: &mut A::Domain,
363 statement: &mir::Statement<'tcx>,
366 self.before_statement_effect(state, statement, location);
369 fn apply_terminator_effect(
371 state: &mut A::Domain,
372 terminator: &mir::Terminator<'tcx>,
375 self.terminator_effect(state, terminator, location);
378 fn apply_before_terminator_effect(
380 state: &mut A::Domain,
381 terminator: &mir::Terminator<'tcx>,
384 self.before_terminator_effect(state, terminator, location);
387 /* Edge-specific effects */
389 fn apply_call_return_effect(
391 state: &mut A::Domain,
393 return_places: CallReturnPlaces<'_, 'tcx>,
395 self.call_return_effect(state, block, return_places);
398 fn apply_yield_resume_effect(
400 state: &mut A::Domain,
401 resume_block: BasicBlock,
402 resume_place: mir::Place<'tcx>,
404 self.yield_resume_effect(state, resume_block, resume_place);
407 fn apply_switch_int_edge_effects(
410 discr: &mir::Operand<'tcx>,
411 edge_effects: &mut impl SwitchIntEdgeEffects<A::Domain>,
413 self.switch_int_edge_effects(block, discr, edge_effects);
416 /* Extension methods */
418 fn into_engine<'mir>(
421 body: &'mir mir::Body<'tcx>,
422 ) -> Engine<'mir, 'tcx, Self>
426 Engine::new_gen_kill(tcx, body, self)
430 /// The legal operations for a transfer function in a gen/kill problem.
432 /// This abstraction exists because there are two different contexts in which we call the methods in
433 /// `GenKillAnalysis`. Sometimes we need to store a single transfer function that can be efficiently
434 /// applied multiple times, such as when computing the cumulative transfer function for each block.
435 /// These cases require a `GenKillSet`, which in turn requires two `BitSet`s of storage. Oftentimes,
436 /// however, we only need to apply an effect once. In *these* cases, it is more efficient to pass the
437 /// `BitSet` representing the state vector directly into the `*_effect` methods as opposed to
438 /// building up a `GenKillSet` and then throwing it away.
439 pub trait GenKill<T> {
440 /// Inserts `elem` into the state vector.
441 fn gen(&mut self, elem: T);
443 /// Removes `elem` from the state vector.
444 fn kill(&mut self, elem: T);
446 /// Calls `gen` for each element in `elems`.
447 fn gen_all(&mut self, elems: impl IntoIterator<Item = T>) {
453 /// Calls `kill` for each element in `elems`.
454 fn kill_all(&mut self, elems: impl IntoIterator<Item = T>) {
461 /// Stores a transfer function for a gen/kill problem.
463 /// Calling `gen`/`kill` on a `GenKillSet` will "build up" a transfer function so that it can be
464 /// applied multiple times efficiently. When there are multiple calls to `gen` and/or `kill` for
465 /// the same element, the most recent one takes precedence.
467 pub struct GenKillSet<T> {
468 gen: HybridBitSet<T>,
469 kill: HybridBitSet<T>,
472 impl<T: Idx> GenKillSet<T> {
473 /// Creates a new transfer function that will leave the dataflow state unchanged.
474 pub fn identity(universe: usize) -> Self {
476 gen: HybridBitSet::new_empty(universe),
477 kill: HybridBitSet::new_empty(universe),
481 pub fn apply(&self, state: &mut impl BitSetExt<T>) {
482 state.union(&self.gen);
483 state.subtract(&self.kill);
487 impl<T: Idx> GenKill<T> for GenKillSet<T> {
488 fn gen(&mut self, elem: T) {
489 self.gen.insert(elem);
490 self.kill.remove(elem);
493 fn kill(&mut self, elem: T) {
494 self.kill.insert(elem);
495 self.gen.remove(elem);
499 impl<T: Idx> GenKill<T> for BitSet<T> {
500 fn gen(&mut self, elem: T) {
504 fn kill(&mut self, elem: T) {
509 impl<T: Idx> GenKill<T> for ChunkedBitSet<T> {
510 fn gen(&mut self, elem: T) {
514 fn kill(&mut self, elem: T) {
519 impl<T: Idx> GenKill<T> for lattice::Dual<BitSet<T>> {
520 fn gen(&mut self, elem: T) {
524 fn kill(&mut self, elem: T) {
529 // NOTE: DO NOT CHANGE VARIANT ORDER. The derived `Ord` impls rely on the current order.
530 #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
532 /// The "before" effect (e.g., `apply_before_statement_effect`) for a statement (or
536 /// The "primary" effect (e.g., `apply_statement_effect`) for a statement (or terminator).
541 pub const fn at_index(self, statement_index: usize) -> EffectIndex {
542 EffectIndex { effect: self, statement_index }
546 #[derive(Clone, Copy, Debug, PartialEq, Eq)]
547 pub struct EffectIndex {
548 statement_index: usize,
553 fn next_in_forward_order(self) -> Self {
555 Effect::Before => Effect::Primary.at_index(self.statement_index),
556 Effect::Primary => Effect::Before.at_index(self.statement_index + 1),
560 fn next_in_backward_order(self) -> Self {
562 Effect::Before => Effect::Primary.at_index(self.statement_index),
563 Effect::Primary => Effect::Before.at_index(self.statement_index - 1),
567 /// Returns `true` if the effect at `self` should be applied earlier than the effect at `other`
568 /// in forward order.
569 fn precedes_in_forward_order(self, other: Self) -> bool {
572 .cmp(&other.statement_index)
573 .then_with(|| self.effect.cmp(&other.effect));
574 ord == Ordering::Less
577 /// Returns `true` if the effect at `self` should be applied earlier than the effect at `other`
578 /// in backward order.
579 fn precedes_in_backward_order(self, other: Self) -> bool {
582 .cmp(&self.statement_index)
583 .then_with(|| self.effect.cmp(&other.effect));
584 ord == Ordering::Less
588 pub struct SwitchIntTarget {
589 pub value: Option<u128>,
590 pub target: BasicBlock,
593 /// A type that records the edge-specific effects for a `SwitchInt` terminator.
594 pub trait SwitchIntEdgeEffects<D> {
595 /// Calls `apply_edge_effect` for each outgoing edge from a `SwitchInt` terminator and
596 /// records the results.
597 fn apply(&mut self, apply_edge_effect: impl FnMut(&mut D, SwitchIntTarget));
600 /// List of places that are written to after a successful (non-unwind) return
601 /// from a `Call` or `InlineAsm`.
602 pub enum CallReturnPlaces<'a, 'tcx> {
603 Call(mir::Place<'tcx>),
604 InlineAsm(&'a [mir::InlineAsmOperand<'tcx>]),
607 impl<'tcx> CallReturnPlaces<'_, 'tcx> {
608 pub fn for_each(&self, mut f: impl FnMut(mir::Place<'tcx>)) {
610 Self::Call(place) => f(place),
611 Self::InlineAsm(operands) => {
614 mir::InlineAsmOperand::Out { place: Some(place), .. }
615 | mir::InlineAsmOperand::InOut { out_place: Some(place), .. } => f(place),