flowistry/mir/
engine.rs

1//! This module re-implements [`rustc_mir_dataflow::Engine`](https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir_dataflow/struct.Engine.html) for performance reasons.
2//!
3//! The Engine implementation in rustc optimizes for minimizing memory usage
4//! by only materializing results at the start of basic blocks, and recomputing
5//! the analysis when visiting results. However, this strategy involves a lot of
6//! creation and deletion of the [analysis domain](https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir_dataflow/trait.AnalysisDomain.html).
7//!
8//! The information flow analysis has a large domain of size `O(|places| * |locations|)`.
9//! Profiling showed that a significant portion of analysis time was just the engine
10//! allocating / cloning / dropping the domain, not doing computation. Therefore this
11//! engine improves performance but increases memory usage by up-front materializing
12//! the domain at every [`Location`].
13
14use std::rc::Rc;
15
16use either::Either;
17use indexical::ToIndex;
18use rustc_data_structures::{graph::Successors, work_queue::WorkQueue};
19use rustc_index::IndexVec;
20use rustc_middle::{
21  mir::{Body, Location, traversal},
22  ty::TyCtxt,
23};
24use rustc_mir_dataflow::{Analysis, Direction, JoinSemiLattice};
25use rustc_utils::{
26  BodyExt,
27  mir::location_or_arg::{
28    LocationOrArg,
29    index::{LocationOrArgDomain, LocationOrArgIndex},
30  },
31};
32
33/// An alternative implementation of
34/// [`rustc_mir_dataflow::Results`](https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir_dataflow/struct.Results.html).
35pub struct AnalysisResults<'tcx, A: Analysis<'tcx>> {
36  /// The underlying analysis that was used to generate the results.
37  pub analysis: A,
38  location_domain: Rc<LocationOrArgDomain>,
39  state: IndexVec<LocationOrArgIndex, Rc<A::Domain>>,
40}
41
42impl<'tcx, A: Analysis<'tcx>> AnalysisResults<'tcx, A> {
43  /// Gets the computed [`AnalysisDomain`](https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir_dataflow/trait.AnalysisDomain.html)
44  /// at a given [`Location`].
45  pub fn state_at(&self, location: Location) -> &A::Domain {
46    &self.state[location.to_index(&self.location_domain)]
47  }
48}
49
50/// Runs a given [`Analysis`](https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir_dataflow/trait.Analysis.html) to a fixpoint over the given [`Body`].
51///
52/// A reimplementation of [`rustc_mir_dataflow::framework::engine::iterate_to_fixpoint`](https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir_dataflow/framework/engine/struct.Engine.html#method.iterate_to_fixpoint).
53pub fn iterate_to_fixpoint<'tcx, A: Analysis<'tcx>>(
54  _tcx: TyCtxt<'tcx>,
55  body: &Body<'tcx>,
56  location_domain: Rc<LocationOrArgDomain>,
57  mut analysis: A,
58) -> AnalysisResults<'tcx, A> {
59  let bottom_value = analysis.bottom_value(body);
60
61  // `state` materializes the analysis domain for *every* location, which is the crux
62  // of this implementation strategy.
63  let num_locs = body.all_locations().count();
64  let mut state = IndexVec::from_elem_n(bottom_value, num_locs);
65
66  analysis
67    .initialize_start_block(body, &mut state[Location::START.to_index(&location_domain)]);
68
69  let mut dirty_queue: WorkQueue<LocationOrArgIndex> = WorkQueue::with_none(num_locs);
70  if A::Direction::IS_FORWARD {
71    for (block, data) in traversal::reverse_postorder(body) {
72      for statement_index in 0 ..= data.statements.len() {
73        let location = Location {
74          block,
75          statement_index,
76        };
77        dirty_queue.insert(location.to_index(&location_domain));
78      }
79    }
80  }
81
82  while let Some(loc_index) = dirty_queue.pop() {
83    let LocationOrArg::Location(location) = *location_domain.value(loc_index) else {
84      unreachable!()
85    };
86    let next_locs = match body.stmt_at(location) {
87      Either::Left(statement) => {
88        analysis.apply_primary_statement_effect(
89          &mut state[loc_index],
90          statement,
91          location,
92        );
93        vec![location.successor_within_block()]
94      }
95      Either::Right(terminator) => {
96        analysis.apply_primary_terminator_effect(
97          &mut state[loc_index],
98          terminator,
99          location,
100        );
101        body
102          .basic_blocks
103          .successors(location.block)
104          .map(|block| Location {
105            block,
106            statement_index: 0,
107          })
108          .collect::<Vec<_>>()
109      }
110    };
111
112    for next_loc in next_locs {
113      let next_loc_index = location_domain.index(&LocationOrArg::Location(next_loc));
114      let (cur_state, next_state) = state.pick2_mut(loc_index, next_loc_index);
115      let changed = next_state.join(cur_state);
116      if changed {
117        dirty_queue.insert(next_loc_index);
118      }
119    }
120  }
121
122  let state = state.into_iter().map(Rc::new).collect();
123
124  AnalysisResults {
125    analysis,
126    location_domain,
127    state,
128  }
129}
flowistry/mir/engine.rs

flowistry/mir/
engine.rs
