1 //! A solver for dataflow problems.
4 DuplicateValuesFor, PathMustEndInFilename, RequiresAnArgument, UnknownFormatter,
6 use crate::framework::BitSetExt;
8 use std::ffi::OsString;
9 use std::path::PathBuf;
12 use rustc_data_structures::work_queue::WorkQueue;
13 use rustc_graphviz as dot;
14 use rustc_hir::def_id::DefId;
15 use rustc_index::bit_set::BitSet;
16 use rustc_index::vec::{Idx, IndexVec};
17 use rustc_middle::mir::{self, traversal, BasicBlock};
18 use rustc_middle::mir::{create_dump_file, dump_enabled};
19 use rustc_middle::ty::TyCtxt;
20 use rustc_span::symbol::{sym, Symbol};
22 use super::fmt::DebugWithContext;
25 visit_results, Analysis, Direction, GenKill, GenKillAnalysis, GenKillSet, JoinSemiLattice,
26 ResultsCursor, ResultsVisitor,
29 /// A dataflow analysis that has converged to fixpoint.
30 pub struct Results<'tcx, A>
35 pub(super) entry_sets: IndexVec<BasicBlock, A::Domain>,
38 impl<'tcx, A> Results<'tcx, A>
42 /// Creates a `ResultsCursor` that can inspect these `Results`.
43 pub fn into_results_cursor<'mir>(
45 body: &'mir mir::Body<'tcx>,
46 ) -> ResultsCursor<'mir, 'tcx, A> {
47 ResultsCursor::new(body, self)
50 /// Gets the dataflow state for the given block.
51 pub fn entry_set_for_block(&self, block: BasicBlock) -> &A::Domain {
52 &self.entry_sets[block]
55 pub fn visit_with<'mir>(
57 body: &'mir mir::Body<'tcx>,
58 blocks: impl IntoIterator<Item = BasicBlock>,
59 vis: &mut impl ResultsVisitor<'mir, 'tcx, FlowState = A::Domain>,
61 visit_results(body, blocks, self, vis)
64 pub fn visit_reachable_with<'mir>(
66 body: &'mir mir::Body<'tcx>,
67 vis: &mut impl ResultsVisitor<'mir, 'tcx, FlowState = A::Domain>,
69 let blocks = mir::traversal::reachable(body);
70 visit_results(body, blocks.map(|(bb, _)| bb), self, vis)
74 /// A solver for dataflow problems.
75 pub struct Engine<'a, 'tcx, A>
80 body: &'a mir::Body<'tcx>,
81 dead_unwinds: Option<&'a BitSet<BasicBlock>>,
82 entry_sets: IndexVec<BasicBlock, A::Domain>,
83 pass_name: Option<&'static str>,
86 /// Cached, cumulative transfer functions for each block.
88 // FIXME(ecstaticmorse): This boxed `Fn` trait object is invoked inside a tight loop for
89 // gen/kill problems on cyclic CFGs. This is not ideal, but it doesn't seem to degrade
90 // performance in practice. I've tried a few ways to avoid this, but they have downsides. See
91 // the message for the commit that added this FIXME for more information.
92 apply_trans_for_block: Option<Box<dyn Fn(BasicBlock, &mut A::Domain)>>,
95 impl<'a, 'tcx, A, D, T> Engine<'a, 'tcx, A>
97 A: GenKillAnalysis<'tcx, Idx = T, Domain = D>,
98 D: Clone + JoinSemiLattice + GenKill<T> + BitSetExt<T>,
101 /// Creates a new `Engine` to solve a gen-kill dataflow problem.
102 pub fn new_gen_kill(tcx: TyCtxt<'tcx>, body: &'a mir::Body<'tcx>, analysis: A) -> Self {
103 // If there are no back-edges in the control-flow graph, we only ever need to apply the
104 // transfer function for each block exactly once (assuming that we process blocks in RPO).
106 // In this case, there's no need to compute the block transfer functions ahead of time.
107 if !body.basic_blocks.is_cfg_cyclic() {
108 return Self::new(tcx, body, analysis, None);
111 // Otherwise, compute and store the cumulative transfer function for each block.
113 let identity = GenKillSet::identity(analysis.bottom_value(body).domain_size());
114 let mut trans_for_block = IndexVec::from_elem(identity, &body.basic_blocks);
116 for (block, block_data) in body.basic_blocks.iter_enumerated() {
117 let trans = &mut trans_for_block[block];
118 A::Direction::gen_kill_effects_in_block(&analysis, trans, block, block_data);
121 let apply_trans = Box::new(move |bb: BasicBlock, state: &mut A::Domain| {
122 trans_for_block[bb].apply(state);
125 Self::new(tcx, body, analysis, Some(apply_trans as Box<_>))
129 impl<'a, 'tcx, A, D> Engine<'a, 'tcx, A>
131 A: Analysis<'tcx, Domain = D>,
132 D: Clone + JoinSemiLattice,
134 /// Creates a new `Engine` to solve a dataflow problem with an arbitrary transfer
137 /// Gen-kill problems should use `new_gen_kill`, which will coalesce transfer functions for
138 /// better performance.
139 pub fn new_generic(tcx: TyCtxt<'tcx>, body: &'a mir::Body<'tcx>, analysis: A) -> Self {
140 Self::new(tcx, body, analysis, None)
145 body: &'a mir::Body<'tcx>,
147 apply_trans_for_block: Option<Box<dyn Fn(BasicBlock, &mut A::Domain)>>,
149 let bottom_value = analysis.bottom_value(body);
150 let mut entry_sets = IndexVec::from_elem(bottom_value.clone(), &body.basic_blocks);
151 analysis.initialize_start_block(body, &mut entry_sets[mir::START_BLOCK]);
153 if A::Direction::IS_BACKWARD && entry_sets[mir::START_BLOCK] != bottom_value {
154 bug!("`initialize_start_block` is not yet supported for backward dataflow analyses");
164 apply_trans_for_block,
168 /// Signals that we do not want dataflow state to propagate across unwind edges for these
171 /// You must take care that `dead_unwinds` does not contain a `BasicBlock` that *can* actually
172 /// unwind during execution. Otherwise, your dataflow results will not be correct.
173 pub fn dead_unwinds(mut self, dead_unwinds: &'a BitSet<BasicBlock>) -> Self {
174 self.dead_unwinds = Some(dead_unwinds);
178 /// Adds an identifier to the graphviz output for this particular run of a dataflow analysis.
180 /// Some analyses are run multiple times in the compilation pipeline. Give them a `pass_name`
181 /// to differentiate them. Otherwise, only the results for the latest run will be saved.
182 pub fn pass_name(mut self, name: &'static str) -> Self {
183 self.pass_name = Some(name);
187 /// Computes the fixpoint for this dataflow problem and returns it.
188 pub fn iterate_to_fixpoint(self) -> Results<'tcx, A>
190 A::Domain: DebugWithContext<A>,
198 apply_trans_for_block,
203 let mut dirty_queue: WorkQueue<BasicBlock> = WorkQueue::with_none(body.basic_blocks.len());
205 if A::Direction::IS_FORWARD {
206 for (bb, _) in traversal::reverse_postorder(body) {
207 dirty_queue.insert(bb);
210 // Reverse post-order on the reverse CFG may generate a better iteration order for
211 // backward dataflow analyses, but probably not enough to matter.
212 for (bb, _) in traversal::postorder(body) {
213 dirty_queue.insert(bb);
217 // `state` is not actually used between iterations;
218 // this is just an optimization to avoid reallocating
220 let mut state = analysis.bottom_value(body);
221 while let Some(bb) = dirty_queue.pop() {
222 let bb_data = &body[bb];
224 // Set the state to the entry state of the block.
225 // This is equivalent to `state = entry_sets[bb].clone()`,
226 // but it saves an allocation, thus improving compile times.
227 state.clone_from(&entry_sets[bb]);
229 // Apply the block transfer function, using the cached one if it exists.
230 match &apply_trans_for_block {
231 Some(apply) => apply(bb, &mut state),
232 None => A::Direction::apply_effects_in_block(&analysis, &mut state, bb, bb_data),
235 A::Direction::join_state_into_successors_of(
242 |target: BasicBlock, state: &A::Domain| {
243 let set_changed = entry_sets[target].join(state);
245 dirty_queue.insert(target);
251 let results = Results { analysis, entry_sets };
253 let res = write_graphviz_results(tcx, &body, &results, pass_name);
254 if let Err(e) = res {
255 error!("Failed to write graphviz dataflow results: {}", e);
264 /// Writes a DOT file containing the results of a dataflow analysis if the user requested it via
265 /// `rustc_mir` attributes.
266 fn write_graphviz_results<'tcx, A>(
268 body: &mir::Body<'tcx>,
269 results: &Results<'tcx, A>,
270 pass_name: Option<&'static str>,
271 ) -> std::io::Result<()>
274 A::Domain: DebugWithContext<A>,
277 use std::io::{self, Write};
279 let def_id = body.source.def_id();
280 let Ok(attrs) = RustcMirAttrs::parse(tcx, def_id) else {
281 // Invalid `rustc_mir` attrs are reported in `RustcMirAttrs::parse`
285 let mut file = match attrs.output_path(A::NAME) {
287 debug!("printing dataflow results for {:?} to {}", def_id, path.display());
288 if let Some(parent) = path.parent() {
289 fs::create_dir_all(parent)?;
291 io::BufWriter::new(fs::File::create(&path)?)
294 None if tcx.sess.opts.unstable_opts.dump_mir_dataflow
295 && dump_enabled(tcx, A::NAME, def_id) =>
297 create_dump_file(tcx, ".dot", false, A::NAME, &pass_name.unwrap_or("-----"), body)?
303 let style = match attrs.formatter {
304 Some(sym::two_phase) => graphviz::OutputStyle::BeforeAndAfter,
305 _ => graphviz::OutputStyle::AfterOnly,
308 let mut buf = Vec::new();
310 let graphviz = graphviz::Formatter::new(body, results, style);
311 let mut render_opts =
312 vec![dot::RenderOption::Fontname(tcx.sess.opts.unstable_opts.graphviz_font.clone())];
313 if tcx.sess.opts.unstable_opts.graphviz_dark_mode {
314 render_opts.push(dot::RenderOption::DarkTheme);
316 dot::render_opts(&graphviz, &mut buf, &render_opts)?;
318 file.write_all(&buf)?;
324 struct RustcMirAttrs {
325 basename_and_suffix: Option<PathBuf>,
326 formatter: Option<Symbol>,
330 fn parse(tcx: TyCtxt<'_>, def_id: DefId) -> Result<Self, ()> {
331 let mut result = Ok(());
332 let mut ret = RustcMirAttrs::default();
334 let rustc_mir_attrs = tcx
335 .get_attrs(def_id, sym::rustc_mir)
336 .flat_map(|attr| attr.meta_item_list().into_iter().flat_map(|v| v.into_iter()));
338 for attr in rustc_mir_attrs {
339 let attr_result = if attr.has_name(sym::borrowck_graphviz_postflow) {
340 Self::set_field(&mut ret.basename_and_suffix, tcx, &attr, |s| {
341 let path = PathBuf::from(s.to_string());
342 match path.file_name() {
345 tcx.sess.emit_err(PathMustEndInFilename { span: attr.span() });
350 } else if attr.has_name(sym::borrowck_graphviz_format) {
351 Self::set_field(&mut ret.formatter, tcx, &attr, |s| match s {
352 sym::gen_kill | sym::two_phase => Ok(s),
354 tcx.sess.emit_err(UnknownFormatter { span: attr.span() });
362 result = result.and(attr_result);
369 field: &mut Option<T>,
371 attr: &ast::NestedMetaItem,
372 mapper: impl FnOnce(Symbol) -> Result<T, ()>,
373 ) -> Result<(), ()> {
375 tcx.sess.emit_err(DuplicateValuesFor { span: attr.span(), name: attr.name_or_empty() });
380 if let Some(s) = attr.value_str() {
381 *field = Some(mapper(s)?);
384 tcx.sess.emit_err(RequiresAnArgument { span: attr.span(), name: attr.name_or_empty() });
389 /// Returns the path where dataflow results should be written, or `None`
390 /// `borrowck_graphviz_postflow` was not specified.
392 /// This performs the following transformation to the argument of `borrowck_graphviz_postflow`:
394 /// "path/suffix.dot" -> "path/analysis_name_suffix.dot"
395 fn output_path(&self, analysis_name: &str) -> Option<PathBuf> {
396 let mut ret = self.basename_and_suffix.as_ref().cloned()?;
397 let suffix = ret.file_name().unwrap(); // Checked when parsing attrs
399 let mut file_name: OsString = analysis_name.into();
401 file_name.push(suffix);
402 ret.set_file_name(file_name);