rustc_mir_dataflow/framework/mod.rs
1//! A framework that can express both [gen-kill] and generic dataflow problems.
2//!
3//! To use this framework, implement the [`Analysis`] trait. There used to be a `GenKillAnalysis`
4//! alternative trait for gen-kill analyses that would pre-compute the transfer function for each
5//! block. It was intended as an optimization, but it ended up not being any faster than
6//! `Analysis`.
7//!
8//! The `impls` module contains several examples of dataflow analyses.
9//!
10//! Then call `iterate_to_fixpoint` on your type that impls `Analysis` to get a `Results`. From
11//! there, you can use a `ResultsCursor` to inspect the fixpoint solution to your dataflow problem
12//! (good for inspecting a small number of locations), or implement the `ResultsVisitor` interface
13//! and use `visit_results` (good for inspecting many or all locations). The following example uses
14//! the `ResultsCursor` approach.
15//!
16//! ```ignore (cross-crate-imports)
17//! use rustc_const_eval::dataflow::Analysis; // Makes `iterate_to_fixpoint` available.
18//!
19//! fn do_my_analysis(tcx: TyCtxt<'tcx>, body: &mir::Body<'tcx>) {
20//! let analysis = MyAnalysis::new()
21//! .iterate_to_fixpoint(tcx, body, None)
22//! .into_results_cursor(body);
23//!
24//! // Print the dataflow state *after* each statement in the start block.
25//! for (_, statement_index) in body.block_data[START_BLOCK].statements.iter_enumerated() {
26//! cursor.seek_after(Location { block: START_BLOCK, statement_index });
27//! let state = cursor.get();
28//! println!("{:?}", state);
29//! }
30//! }
31//! ```
32//!
33//! [gen-kill]: https://en.wikipedia.org/wiki/Data-flow_analysis#Bit_vector_problems
34
35use std::cmp::Ordering;
36
37use rustc_data_structures::work_queue::WorkQueue;
38use rustc_index::bit_set::{DenseBitSet, MixedBitSet};
39use rustc_index::{Idx, IndexVec};
40use rustc_middle::bug;
41use rustc_middle::mir::{
42 self, BasicBlock, CallReturnPlaces, Location, SwitchTargetValue, TerminatorEdges, traversal,
43};
44use rustc_middle::ty::TyCtxt;
45use tracing::error;
46
47use self::graphviz::write_graphviz_results;
48use super::fmt::DebugWithContext;
49
50mod cursor;
51mod direction;
52pub mod fmt;
53pub mod graphviz;
54pub mod lattice;
55mod results;
56mod visitor;
57
58pub use self::cursor::ResultsCursor;
59pub use self::direction::{Backward, Direction, Forward};
60pub use self::lattice::{JoinSemiLattice, MaybeReachable};
61pub(crate) use self::results::AnalysisAndResults;
62pub use self::results::Results;
63pub use self::visitor::{ResultsVisitor, visit_reachable_results, visit_results};
64
65/// Analysis domains are all bitsets of various kinds. This trait holds
66/// operations needed by all of them.
67pub trait BitSetExt<T> {
68 fn contains(&self, elem: T) -> bool;
69}
70
71impl<T: Idx> BitSetExt<T> for DenseBitSet<T> {
72 fn contains(&self, elem: T) -> bool {
73 self.contains(elem)
74 }
75}
76
77impl<T: Idx> BitSetExt<T> for MixedBitSet<T> {
78 fn contains(&self, elem: T) -> bool {
79 self.contains(elem)
80 }
81}
82
83/// A dataflow problem with an arbitrarily complex transfer function.
84///
85/// This trait specifies the lattice on which this analysis operates (the domain), its
86/// initial value at the entry point of each basic block, and various operations.
87///
88/// # Convergence
89///
90/// When implementing this trait it's possible to choose a transfer function such that the analysis
91/// does not reach fixpoint. To guarantee convergence, your transfer functions must maintain the
92/// following invariant:
93///
94/// > If the dataflow state **before** some point in the program changes to be greater
95/// than the prior state **before** that point, the dataflow state **after** that point must
96/// also change to be greater than the prior state **after** that point.
97///
98/// This invariant guarantees that the dataflow state at a given point in the program increases
99/// monotonically until fixpoint is reached. Note that this monotonicity requirement only applies
100/// to the same point in the program at different points in time. The dataflow state at a given
101/// point in the program may or may not be greater than the state at any preceding point.
102pub trait Analysis<'tcx> {
103 /// The type that holds the dataflow state at any given point in the program.
104 type Domain: Clone + JoinSemiLattice;
105
106 /// The direction of this analysis. Either `Forward` or `Backward`.
107 type Direction: Direction = Forward;
108
109 /// Auxiliary data used for analyzing `SwitchInt` terminators, if necessary.
110 type SwitchIntData = !;
111
112 /// A descriptive name for this analysis. Used only for debugging.
113 ///
114 /// This name should be brief and contain no spaces, periods or other characters that are not
115 /// suitable as part of a filename.
116 const NAME: &'static str;
117
118 /// Returns the initial value of the dataflow state upon entry to each basic block.
119 fn bottom_value(&self, body: &mir::Body<'tcx>) -> Self::Domain;
120
121 /// Mutates the initial value of the dataflow state upon entry to the `START_BLOCK`.
122 ///
123 /// For backward analyses, initial state (besides the bottom value) is not yet supported. Trying
124 /// to mutate the initial state will result in a panic.
125 //
126 // FIXME: For backward dataflow analyses, the initial state should be applied to every basic
127 // block where control flow could exit the MIR body (e.g., those terminated with `return` or
128 // `resume`). It's not obvious how to handle `yield` points in coroutines, however.
129 fn initialize_start_block(&self, body: &mir::Body<'tcx>, state: &mut Self::Domain);
130
131 /// Updates the current dataflow state with an "early" effect, i.e. one
132 /// that occurs immediately before the given statement.
133 ///
134 /// This method is useful if the consumer of the results of this analysis only needs to observe
135 /// *part* of the effect of a statement (e.g. for two-phase borrows). As a general rule,
136 /// analyses should not implement this without also implementing
137 /// `apply_primary_statement_effect`.
138 fn apply_early_statement_effect(
139 &mut self,
140 _state: &mut Self::Domain,
141 _statement: &mir::Statement<'tcx>,
142 _location: Location,
143 ) {
144 }
145
146 /// Updates the current dataflow state with the effect of evaluating a statement.
147 fn apply_primary_statement_effect(
148 &mut self,
149 state: &mut Self::Domain,
150 statement: &mir::Statement<'tcx>,
151 location: Location,
152 );
153
154 /// Updates the current dataflow state with an effect that occurs immediately *before* the
155 /// given terminator.
156 ///
157 /// This method is useful if the consumer of the results of this analysis needs only to observe
158 /// *part* of the effect of a terminator (e.g. for two-phase borrows). As a general rule,
159 /// analyses should not implement this without also implementing
160 /// `apply_primary_terminator_effect`.
161 fn apply_early_terminator_effect(
162 &mut self,
163 _state: &mut Self::Domain,
164 _terminator: &mir::Terminator<'tcx>,
165 _location: Location,
166 ) {
167 }
168
169 /// Updates the current dataflow state with the effect of evaluating a terminator.
170 ///
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_primary_terminator_effect<'mir>(
176 &mut self,
177 _state: &mut Self::Domain,
178 terminator: &'mir mir::Terminator<'tcx>,
179 _location: Location,
180 ) -> TerminatorEdges<'mir, 'tcx> {
181 terminator.edges()
182 }
183
184 /* Edge-specific effects */
185
186 /// Updates the current dataflow state with the effect of a successful return from a `Call`
187 /// terminator.
188 ///
189 /// This is separate from `apply_primary_terminator_effect` to properly track state across
190 /// unwind edges.
191 fn apply_call_return_effect(
192 &mut self,
193 _state: &mut Self::Domain,
194 _block: BasicBlock,
195 _return_places: CallReturnPlaces<'_, 'tcx>,
196 ) {
197 }
198
199 /// Used to update the current dataflow state with the effect of taking a particular branch in
200 /// a `SwitchInt` terminator.
201 ///
202 /// Unlike the other edge-specific effects, which are allowed to mutate `Self::Domain`
203 /// directly, overriders of this method must return a `Self::SwitchIntData` value (wrapped in
204 /// `Some`). The `apply_switch_int_edge_effect` method will then be called once for each
205 /// outgoing edge and will have access to the dataflow state that will be propagated along that
206 /// edge, and also the `Self::SwitchIntData` value.
207 ///
208 /// This interface is somewhat more complex than the other visitor-like "effect" methods.
209 /// However, it is both more ergonomic—callers don't need to recompute or cache information
210 /// about a given `SwitchInt` terminator for each one of its edges—and more efficient—the
211 /// engine doesn't need to clone the exit state for a block unless
212 /// `get_switch_int_data` is actually called.
213 fn get_switch_int_data(
214 &mut self,
215 _block: mir::BasicBlock,
216 _discr: &mir::Operand<'tcx>,
217 ) -> Option<Self::SwitchIntData> {
218 None
219 }
220
221 /// See comments on `get_switch_int_data`.
222 fn apply_switch_int_edge_effect(
223 &mut self,
224 _data: &mut Self::SwitchIntData,
225 _state: &mut Self::Domain,
226 _value: SwitchTargetValue,
227 ) {
228 unreachable!();
229 }
230
231 /* Extension methods */
232
233 /// Finds the fixpoint for this dataflow problem.
234 ///
235 /// You shouldn't need to override this. Its purpose is to enable method chaining like so:
236 ///
237 /// ```ignore (cross-crate-imports)
238 /// let results = MyAnalysis::new(tcx, body)
239 /// .iterate_to_fixpoint(tcx, body, None)
240 /// .into_results_cursor(body);
241 /// ```
242 /// You can optionally add a `pass_name` to the graphviz output for this particular run of a
243 /// dataflow analysis. Some analyses are run multiple times in the compilation pipeline.
244 /// Without a `pass_name` to differentiates them, only the results for the latest run will be
245 /// saved.
246 fn iterate_to_fixpoint<'mir>(
247 mut self,
248 tcx: TyCtxt<'tcx>,
249 body: &'mir mir::Body<'tcx>,
250 pass_name: Option<&'static str>,
251 ) -> AnalysisAndResults<'tcx, Self>
252 where
253 Self: Sized,
254 Self::Domain: DebugWithContext<Self>,
255 {
256 let mut results = IndexVec::from_fn_n(|_| self.bottom_value(body), body.basic_blocks.len());
257 self.initialize_start_block(body, &mut results[mir::START_BLOCK]);
258
259 if Self::Direction::IS_BACKWARD && results[mir::START_BLOCK] != self.bottom_value(body) {
260 bug!("`initialize_start_block` is not yet supported for backward dataflow analyses");
261 }
262
263 let mut dirty_queue: WorkQueue<BasicBlock> = WorkQueue::with_none(body.basic_blocks.len());
264
265 if Self::Direction::IS_FORWARD {
266 for (bb, _) in traversal::reverse_postorder(body) {
267 dirty_queue.insert(bb);
268 }
269 } else {
270 // Reverse post-order on the reverse CFG may generate a better iteration order for
271 // backward dataflow analyses, but probably not enough to matter.
272 for (bb, _) in traversal::postorder(body) {
273 dirty_queue.insert(bb);
274 }
275 }
276
277 // `state` is not actually used between iterations;
278 // this is just an optimization to avoid reallocating
279 // every iteration.
280 let mut state = self.bottom_value(body);
281 while let Some(bb) = dirty_queue.pop() {
282 // Set the state to the entry state of the block. This is equivalent to `state =
283 // results[bb].clone()`, but it saves an allocation, thus improving compile times.
284 state.clone_from(&results[bb]);
285
286 Self::Direction::apply_effects_in_block(
287 &mut self,
288 body,
289 &mut state,
290 bb,
291 &body[bb],
292 |target: BasicBlock, state: &Self::Domain| {
293 let set_changed = results[target].join(state);
294 if set_changed {
295 dirty_queue.insert(target);
296 }
297 },
298 );
299 }
300
301 if tcx.sess.opts.unstable_opts.dump_mir_dataflow {
302 let res = write_graphviz_results(tcx, body, &mut self, &results, pass_name);
303 if let Err(e) = res {
304 error!("Failed to write graphviz dataflow results: {}", e);
305 }
306 }
307
308 AnalysisAndResults { analysis: self, results }
309 }
310}
311
312/// The legal operations for a transfer function in a gen/kill problem.
313pub trait GenKill<T> {
314 /// Inserts `elem` into the state vector.
315 fn gen_(&mut self, elem: T);
316
317 /// Removes `elem` from the state vector.
318 fn kill(&mut self, elem: T);
319
320 /// Calls `gen` for each element in `elems`.
321 fn gen_all(&mut self, elems: impl IntoIterator<Item = T>) {
322 for elem in elems {
323 self.gen_(elem);
324 }
325 }
326
327 /// Calls `kill` for each element in `elems`.
328 fn kill_all(&mut self, elems: impl IntoIterator<Item = T>) {
329 for elem in elems {
330 self.kill(elem);
331 }
332 }
333}
334
335impl<T: Idx> GenKill<T> for DenseBitSet<T> {
336 fn gen_(&mut self, elem: T) {
337 self.insert(elem);
338 }
339
340 fn kill(&mut self, elem: T) {
341 self.remove(elem);
342 }
343}
344
345impl<T: Idx> GenKill<T> for MixedBitSet<T> {
346 fn gen_(&mut self, elem: T) {
347 self.insert(elem);
348 }
349
350 fn kill(&mut self, elem: T) {
351 self.remove(elem);
352 }
353}
354
355impl<T, S: GenKill<T>> GenKill<T> for MaybeReachable<S> {
356 fn gen_(&mut self, elem: T) {
357 match self {
358 // If the state is not reachable, adding an element does nothing.
359 MaybeReachable::Unreachable => {}
360 MaybeReachable::Reachable(set) => set.gen_(elem),
361 }
362 }
363
364 fn kill(&mut self, elem: T) {
365 match self {
366 // If the state is not reachable, killing an element does nothing.
367 MaybeReachable::Unreachable => {}
368 MaybeReachable::Reachable(set) => set.kill(elem),
369 }
370 }
371}
372
373// NOTE: DO NOT CHANGE VARIANT ORDER. The derived `Ord` impls rely on the current order.
374#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
375enum Effect {
376 /// The "early" effect (e.g., `apply_early_statement_effect`) for a statement/terminator.
377 Early,
378
379 /// The "primary" effect (e.g., `apply_primary_statement_effect`) for a statement/terminator.
380 Primary,
381}
382
383impl Effect {
384 const fn at_index(self, statement_index: usize) -> EffectIndex {
385 EffectIndex { effect: self, statement_index }
386 }
387}
388
389#[derive(Clone, Copy, Debug, PartialEq, Eq)]
390pub struct EffectIndex {
391 statement_index: usize,
392 effect: Effect,
393}
394
395impl EffectIndex {
396 fn next_in_forward_order(self) -> Self {
397 match self.effect {
398 Effect::Early => Effect::Primary.at_index(self.statement_index),
399 Effect::Primary => Effect::Early.at_index(self.statement_index + 1),
400 }
401 }
402
403 fn next_in_backward_order(self) -> Self {
404 match self.effect {
405 Effect::Early => Effect::Primary.at_index(self.statement_index),
406 Effect::Primary => Effect::Early.at_index(self.statement_index - 1),
407 }
408 }
409
410 /// Returns `true` if the effect at `self` should be applied earlier than the effect at `other`
411 /// in forward order.
412 fn precedes_in_forward_order(self, other: Self) -> bool {
413 let ord = self
414 .statement_index
415 .cmp(&other.statement_index)
416 .then_with(|| self.effect.cmp(&other.effect));
417 ord == Ordering::Less
418 }
419
420 /// Returns `true` if the effect at `self` should be applied earlier than the effect at `other`
421 /// in backward order.
422 fn precedes_in_backward_order(self, other: Self) -> bool {
423 let ord = other
424 .statement_index
425 .cmp(&self.statement_index)
426 .then_with(|| self.effect.cmp(&other.effect));
427 ord == Ordering::Less
428 }
429}
430
431#[cfg(test)]
432mod tests;