1 //! A solver for dataflow problems.
3 use std::borrow::BorrowMut;
4 use std::ffi::OsString;
6 use std::path::PathBuf;
9 use rustc_data_structures::work_queue::WorkQueue;
10 use rustc_graphviz as dot;
11 use rustc_hir::def_id::DefId;
12 use rustc_index::bit_set::BitSet;
13 use rustc_index::vec::{Idx, IndexVec};
14 use rustc_middle::mir::{self, traversal, BasicBlock};
15 use rustc_middle::ty::{self, TyCtxt};
16 use rustc_span::symbol::{sym, Symbol};
18 use super::fmt::DebugWithContext;
21 visit_results, Analysis, Direction, GenKill, GenKillAnalysis, GenKillSet, JoinSemiLattice,
22 ResultsCursor, ResultsVisitor,
24 use crate::util::pretty::dump_enabled;
26 /// A dataflow analysis that has converged to fixpoint.
27 pub struct Results<'tcx, A>
32 pub(super) entry_sets: IndexVec<BasicBlock, A::Domain>,
35 impl<A> Results<'tcx, A>
39 /// Creates a `ResultsCursor` that can inspect these `Results`.
40 pub fn into_results_cursor(self, body: &'mir mir::Body<'tcx>) -> ResultsCursor<'mir, 'tcx, A> {
41 ResultsCursor::new(body, self)
44 /// Gets the dataflow state for the given block.
45 pub fn entry_set_for_block(&self, block: BasicBlock) -> &A::Domain {
46 &self.entry_sets[block]
51 body: &'mir mir::Body<'tcx>,
52 blocks: impl IntoIterator<Item = BasicBlock>,
53 vis: &mut impl ResultsVisitor<'mir, 'tcx, FlowState = A::Domain>,
55 visit_results(body, blocks, self, vis)
58 pub fn visit_reachable_with(
60 body: &'mir mir::Body<'tcx>,
61 vis: &mut impl ResultsVisitor<'mir, 'tcx, FlowState = A::Domain>,
63 let blocks = mir::traversal::reachable(body);
64 visit_results(body, blocks.map(|(bb, _)| bb), self, vis)
67 pub fn visit_in_rpo_with(
69 body: &'mir mir::Body<'tcx>,
70 vis: &mut impl ResultsVisitor<'mir, 'tcx, FlowState = A::Domain>,
72 let blocks = mir::traversal::reverse_postorder(body);
73 visit_results(body, blocks.map(|(bb, _)| bb), self, vis)
77 /// A solver for dataflow problems.
78 pub struct Engine<'a, 'tcx, A>
83 body: &'a mir::Body<'tcx>,
85 dead_unwinds: Option<&'a BitSet<BasicBlock>>,
86 entry_sets: IndexVec<BasicBlock, A::Domain>,
87 pass_name: Option<&'static str>,
90 /// Cached, cumulative transfer functions for each block.
92 // FIXME(ecstaticmorse): This boxed `Fn` trait object is invoked inside a tight loop for
93 // gen/kill problems on cyclic CFGs. This is not ideal, but it doesn't seem to degrade
94 // performance in practice. I've tried a few ways to avoid this, but they have downsides. See
95 // the message for the commit that added this FIXME for more information.
96 apply_trans_for_block: Option<Box<dyn Fn(BasicBlock, &mut A::Domain)>>,
99 impl<A, D, T> Engine<'a, 'tcx, A>
101 A: GenKillAnalysis<'tcx, Idx = T, Domain = D>,
102 D: Clone + JoinSemiLattice + GenKill<T> + BorrowMut<BitSet<T>>,
105 /// Creates a new `Engine` to solve a gen-kill dataflow problem.
108 body: &'a mir::Body<'tcx>,
112 // If there are no back-edges in the control-flow graph, we only ever need to apply the
113 // transfer function for each block exactly once (assuming that we process blocks in RPO).
115 // In this case, there's no need to compute the block transfer functions ahead of time.
116 if !body.is_cfg_cyclic() {
117 return Self::new(tcx, body, def_id, analysis, None);
120 // Otherwise, compute and store the cumulative transfer function for each block.
122 let identity = GenKillSet::identity(analysis.bottom_value(body).borrow().domain_size());
123 let mut trans_for_block = IndexVec::from_elem(identity, body.basic_blocks());
125 for (block, block_data) in body.basic_blocks().iter_enumerated() {
126 let trans = &mut trans_for_block[block];
127 A::Direction::gen_kill_effects_in_block(&analysis, trans, block, block_data);
130 let apply_trans = Box::new(move |bb: BasicBlock, state: &mut A::Domain| {
131 trans_for_block[bb].apply(state.borrow_mut());
134 Self::new(tcx, body, def_id, analysis, Some(apply_trans as Box<_>))
138 impl<A, D> Engine<'a, 'tcx, A>
140 A: Analysis<'tcx, Domain = D>,
141 D: Clone + JoinSemiLattice,
143 /// Creates a new `Engine` to solve a dataflow problem with an arbitrary transfer
146 /// Gen-kill problems should use `new_gen_kill`, which will coalesce transfer functions for
147 /// better performance.
150 body: &'a mir::Body<'tcx>,
154 Self::new(tcx, body, def_id, analysis, None)
159 body: &'a mir::Body<'tcx>,
162 apply_trans_for_block: Option<Box<dyn Fn(BasicBlock, &mut A::Domain)>>,
164 let bottom_value = analysis.bottom_value(body);
165 let mut entry_sets = IndexVec::from_elem(bottom_value.clone(), body.basic_blocks());
166 analysis.initialize_start_block(body, &mut entry_sets[mir::START_BLOCK]);
168 if A::Direction::is_backward() && entry_sets[mir::START_BLOCK] != bottom_value {
169 bug!("`initialize_start_block` is not yet supported for backward dataflow analyses");
180 apply_trans_for_block,
184 /// Signals that we do not want dataflow state to propagate across unwind edges for these
187 /// You must take care that `dead_unwinds` does not contain a `BasicBlock` that *can* actually
188 /// unwind during execution. Otherwise, your dataflow results will not be correct.
189 pub fn dead_unwinds(mut self, dead_unwinds: &'a BitSet<BasicBlock>) -> Self {
190 self.dead_unwinds = Some(dead_unwinds);
194 /// Adds an identifier to the graphviz output for this particular run of a dataflow analysis.
196 /// Some analyses are run multiple times in the compilation pipeline. Give them a `pass_name`
197 /// to differentiate them. Otherwise, only the results for the latest run will be saved.
198 pub fn pass_name(mut self, name: &'static str) -> Self {
199 self.pass_name = Some(name);
203 /// Computes the fixpoint for this dataflow problem and returns it.
204 pub fn iterate_to_fixpoint(self) -> Results<'tcx, A>
206 A::Domain: DebugWithContext<A>,
215 apply_trans_for_block,
220 let mut dirty_queue: WorkQueue<BasicBlock> =
221 WorkQueue::with_none(body.basic_blocks().len());
223 if A::Direction::is_forward() {
224 for (bb, _) in traversal::reverse_postorder(body) {
225 dirty_queue.insert(bb);
228 // Reverse post-order on the reverse CFG may generate a better iteration order for
229 // backward dataflow analyses, but probably not enough to matter.
230 for (bb, _) in traversal::postorder(body) {
231 dirty_queue.insert(bb);
235 let mut state = analysis.bottom_value(body);
236 while let Some(bb) = dirty_queue.pop() {
237 let bb_data = &body[bb];
239 // Apply the block transfer function, using the cached one if it exists.
240 state.clone_from(&entry_sets[bb]);
241 match &apply_trans_for_block {
242 Some(apply) => apply(bb, &mut state),
243 None => A::Direction::apply_effects_in_block(&analysis, &mut state, bb, bb_data),
246 A::Direction::join_state_into_successors_of(
253 |target: BasicBlock, state: &A::Domain| {
254 let set_changed = entry_sets[target].join(state);
256 dirty_queue.insert(target);
262 let results = Results { analysis, entry_sets };
264 let res = write_graphviz_results(tcx, def_id, &body, &results, pass_name);
265 if let Err(e) = res {
266 warn!("Failed to write graphviz dataflow results: {}", e);
275 /// Writes a DOT file containing the results of a dataflow analysis if the user requested it via
276 /// `rustc_mir` attributes.
277 fn write_graphviz_results<A>(
280 body: &mir::Body<'tcx>,
281 results: &Results<'tcx, A>,
282 pass_name: Option<&'static str>,
283 ) -> std::io::Result<()>
286 A::Domain: DebugWithContext<A>,
288 let attrs = match RustcMirAttrs::parse(tcx, def_id) {
291 // Invalid `rustc_mir` attrs are reported in `RustcMirAttrs::parse`
292 Err(()) => return Ok(()),
295 let path = match attrs.output_path(A::NAME) {
298 None if tcx.sess.opts.debugging_opts.dump_mir_dataflow
299 && dump_enabled(tcx, A::NAME, def_id) =>
301 // FIXME: Use some variant of `pretty::dump_path` for this
302 let mut path = PathBuf::from(&tcx.sess.opts.debugging_opts.dump_mir_dir);
304 let crate_name = tcx.crate_name(def_id.krate);
305 let item_name = ty::print::with_forced_impl_filename_line(|| {
306 tcx.def_path(def_id).to_filename_friendly_no_crate()
309 let pass_name = pass_name.map(|s| format!(".{}", s)).unwrap_or_default();
311 path.push(format!("{}.{}.{}{}.dot", crate_name, item_name, A::NAME, pass_name));
315 None => return Ok(()),
318 let style = match attrs.formatter {
319 Some(sym::two_phase) => graphviz::OutputStyle::BeforeAndAfter,
320 _ => graphviz::OutputStyle::AfterOnly,
323 debug!("printing dataflow results for {:?} to {}", def_id, path.display());
324 let mut buf = Vec::new();
326 let graphviz = graphviz::Formatter::new(body, def_id, results, style);
327 let mut render_opts =
328 vec![dot::RenderOption::Fontname(tcx.sess.opts.debugging_opts.graphviz_font.clone())];
329 if tcx.sess.opts.debugging_opts.graphviz_dark_mode {
330 render_opts.push(dot::RenderOption::DarkTheme);
332 dot::render_opts(&graphviz, &mut buf, &render_opts)?;
334 if let Some(parent) = path.parent() {
335 fs::create_dir_all(parent)?;
337 fs::write(&path, buf)?;
343 struct RustcMirAttrs {
344 basename_and_suffix: Option<PathBuf>,
345 formatter: Option<Symbol>,
349 fn parse(tcx: TyCtxt<'tcx>, def_id: DefId) -> Result<Self, ()> {
350 let attrs = tcx.get_attrs(def_id);
352 let mut result = Ok(());
353 let mut ret = RustcMirAttrs::default();
355 let rustc_mir_attrs = attrs
357 .filter(|attr| tcx.sess.check_name(attr, sym::rustc_mir))
358 .flat_map(|attr| attr.meta_item_list().into_iter().flat_map(|v| v.into_iter()));
360 for attr in rustc_mir_attrs {
361 let attr_result = if attr.has_name(sym::borrowck_graphviz_postflow) {
362 Self::set_field(&mut ret.basename_and_suffix, tcx, &attr, |s| {
363 let path = PathBuf::from(s.to_string());
364 match path.file_name() {
367 tcx.sess.span_err(attr.span(), "path must end in a filename");
372 } else if attr.has_name(sym::borrowck_graphviz_format) {
373 Self::set_field(&mut ret.formatter, tcx, &attr, |s| match s {
374 sym::gen_kill | sym::two_phase => Ok(s),
376 tcx.sess.span_err(attr.span(), "unknown formatter");
384 result = result.and(attr_result);
391 field: &mut Option<T>,
393 attr: &ast::NestedMetaItem,
394 mapper: impl FnOnce(Symbol) -> Result<T, ()>,
395 ) -> Result<(), ()> {
398 .span_err(attr.span(), &format!("duplicate values for `{}`", attr.name_or_empty()));
403 if let Some(s) = attr.value_str() {
404 *field = Some(mapper(s)?);
408 .span_err(attr.span(), &format!("`{}` requires an argument", attr.name_or_empty()));
413 /// Returns the path where dataflow results should be written, or `None`
414 /// `borrowck_graphviz_postflow` was not specified.
416 /// This performs the following transformation to the argument of `borrowck_graphviz_postflow`:
418 /// "path/suffix.dot" -> "path/analysis_name_suffix.dot"
419 fn output_path(&self, analysis_name: &str) -> Option<PathBuf> {
420 let mut ret = self.basename_and_suffix.as_ref().cloned()?;
421 let suffix = ret.file_name().unwrap(); // Checked when parsing attrs
423 let mut file_name: OsString = analysis_name.into();
425 file_name.push(suffix);
426 ret.set_file_name(file_name);