compiler/rustc_mir/src/dataflow/framework/engine.rs

   1 //! A solver for dataflow problems.
   2
   3 use std::borrow::BorrowMut;
   4 use std::ffi::OsString;
   5 use std::fs;
   6 use std::path::PathBuf;
   7
   8 use rustc_ast as ast;
   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};
  17
  18 use super::fmt::DebugWithContext;
  19 use super::graphviz;
  20 use super::{
  21     visit_results, Analysis, Direction, GenKill, GenKillAnalysis, GenKillSet, JoinSemiLattice,
  22     ResultsCursor, ResultsVisitor,
  23 };
  24 use crate::util::pretty::dump_enabled;
  25
  26 /// A dataflow analysis that has converged to fixpoint.
  27 pub struct Results<'tcx, A>
  28 where
  29     A: Analysis<'tcx>,
  30 {
  31     pub analysis: A,
  32     pub(super) entry_sets: IndexVec<BasicBlock, A::Domain>,
  33 }
  34
  35 impl<A> Results<'tcx, A>
  36 where
  37     A: Analysis<'tcx>,
  38 {
  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)
  42     }
  43
  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]
  47     }
  48
  49     pub fn visit_with(
  50         &self,
  51         body: &'mir mir::Body<'tcx>,
  52         blocks: impl IntoIterator<Item = BasicBlock>,
  53         vis: &mut impl ResultsVisitor<'mir, 'tcx, FlowState = A::Domain>,
  54     ) {
  55         visit_results(body, blocks, self, vis)
  56     }
  57
  58     pub fn visit_reachable_with(
  59         &self,
  60         body: &'mir mir::Body<'tcx>,
  61         vis: &mut impl ResultsVisitor<'mir, 'tcx, FlowState = A::Domain>,
  62     ) {
  63         let blocks = mir::traversal::reachable(body);
  64         visit_results(body, blocks.map(|(bb, _)| bb), self, vis)
  65     }
  66
  67     pub fn visit_in_rpo_with(
  68         &self,
  69         body: &'mir mir::Body<'tcx>,
  70         vis: &mut impl ResultsVisitor<'mir, 'tcx, FlowState = A::Domain>,
  71     ) {
  72         let blocks = mir::traversal::reverse_postorder(body);
  73         visit_results(body, blocks.map(|(bb, _)| bb), self, vis)
  74     }
  75 }
  76
  77 /// A solver for dataflow problems.
  78 pub struct Engine<'a, 'tcx, A>
  79 where
  80     A: Analysis<'tcx>,
  81 {
  82     tcx: TyCtxt<'tcx>,
  83     body: &'a mir::Body<'tcx>,
  84     def_id: DefId,
  85     dead_unwinds: Option<&'a BitSet<BasicBlock>>,
  86     entry_sets: IndexVec<BasicBlock, A::Domain>,
  87     pass_name: Option<&'static str>,
  88     analysis: A,
  89
  90     /// Cached, cumulative transfer functions for each block.
  91     //
  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)>>,
  97 }
  98
  99 impl<A, D, T> Engine<'a, 'tcx, A>
 100 where
 101     A: GenKillAnalysis<'tcx, Idx = T, Domain = D>,
 102     D: Clone + JoinSemiLattice + GenKill<T> + BorrowMut<BitSet<T>>,
 103     T: Idx,
 104 {
 105     /// Creates a new `Engine` to solve a gen-kill dataflow problem.
 106     pub fn new_gen_kill(
 107         tcx: TyCtxt<'tcx>,
 108         body: &'a mir::Body<'tcx>,
 109         def_id: DefId,
 110         analysis: A,
 111     ) -> Self {
 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).
 114         //
 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);
 118         }
 119
 120         // Otherwise, compute and store the cumulative transfer function for each block.
 121
 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());
 124
 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);
 128         }
 129
 130         let apply_trans = Box::new(move |bb: BasicBlock, state: &mut A::Domain| {
 131             trans_for_block[bb].apply(state.borrow_mut());
 132         });
 133
 134         Self::new(tcx, body, def_id, analysis, Some(apply_trans as Box<_>))
 135     }
 136 }
 137
 138 impl<A, D> Engine<'a, 'tcx, A>
 139 where
 140     A: Analysis<'tcx, Domain = D>,
 141     D: Clone + JoinSemiLattice,
 142 {
 143     /// Creates a new `Engine` to solve a dataflow problem with an arbitrary transfer
 144     /// function.
 145     ///
 146     /// Gen-kill problems should use `new_gen_kill`, which will coalesce transfer functions for
 147     /// better performance.
 148     pub fn new_generic(
 149         tcx: TyCtxt<'tcx>,
 150         body: &'a mir::Body<'tcx>,
 151         def_id: DefId,
 152         analysis: A,
 153     ) -> Self {
 154         Self::new(tcx, body, def_id, analysis, None)
 155     }
 156
 157     fn new(
 158         tcx: TyCtxt<'tcx>,
 159         body: &'a mir::Body<'tcx>,
 160         def_id: DefId,
 161         analysis: A,
 162         apply_trans_for_block: Option<Box<dyn Fn(BasicBlock, &mut A::Domain)>>,
 163     ) -> Self {
 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]);
 167
 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");
 170         }
 171
 172         Engine {
 173             analysis,
 174             tcx,
 175             body,
 176             def_id,
 177             dead_unwinds: None,
 178             pass_name: None,
 179             entry_sets,
 180             apply_trans_for_block,
 181         }
 182     }
 183
 184     /// Signals that we do not want dataflow state to propagate across unwind edges for these
 185     /// `BasicBlock`s.
 186     ///
 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);
 191         self
 192     }
 193
 194     /// Adds an identifier to the graphviz output for this particular run of a dataflow analysis.
 195     ///
 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);
 200         self
 201     }
 202
 203     /// Computes the fixpoint for this dataflow problem and returns it.
 204     pub fn iterate_to_fixpoint(self) -> Results<'tcx, A>
 205     where
 206         A::Domain: DebugWithContext<A>,
 207     {
 208         let Engine {
 209             analysis,
 210             body,
 211             dead_unwinds,
 212             def_id,
 213             mut entry_sets,
 214             tcx,
 215             apply_trans_for_block,
 216             pass_name,
 217             ..
 218         } = self;
 219
 220         let mut dirty_queue: WorkQueue<BasicBlock> =
 221             WorkQueue::with_none(body.basic_blocks().len());
 222
 223         if A::Direction::is_forward() {
 224             for (bb, _) in traversal::reverse_postorder(body) {
 225                 dirty_queue.insert(bb);
 226             }
 227         } else {
 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);
 232             }
 233         }
 234
 235         let mut state = analysis.bottom_value(body);
 236         while let Some(bb) = dirty_queue.pop() {
 237             let bb_data = &body[bb];
 238
 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),
 244             }
 245
 246             A::Direction::join_state_into_successors_of(
 247                 &analysis,
 248                 tcx,
 249                 body,
 250                 dead_unwinds,
 251                 &mut state,
 252                 (bb, bb_data),
 253                 |target: BasicBlock, state: &A::Domain| {
 254                     let set_changed = entry_sets[target].join(state);
 255                     if set_changed {
 256                         dirty_queue.insert(target);
 257                     }
 258                 },
 259             );
 260         }
 261
 262         let results = Results { analysis, entry_sets };
 263
 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);
 267         }
 268
 269         results
 270     }
 271 }
 272
 273 // Graphviz
 274
 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>(
 278     tcx: TyCtxt<'tcx>,
 279     def_id: DefId,
 280     body: &mir::Body<'tcx>,
 281     results: &Results<'tcx, A>,
 282     pass_name: Option<&'static str>,
 283 ) -> std::io::Result<()>
 284 where
 285     A: Analysis<'tcx>,
 286     A::Domain: DebugWithContext<A>,
 287 {
 288     let attrs = match RustcMirAttrs::parse(tcx, def_id) {
 289         Ok(attrs) => attrs,
 290
 291         // Invalid `rustc_mir` attrs are reported in `RustcMirAttrs::parse`
 292         Err(()) => return Ok(()),
 293     };
 294
 295     let path = match attrs.output_path(A::NAME) {
 296         Some(path) => path,
 297
 298         None if tcx.sess.opts.debugging_opts.dump_mir_dataflow
 299             && dump_enabled(tcx, A::NAME, def_id) =>
 300         {
 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);
 303
 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()
 307             });
 308
 309             let pass_name = pass_name.map(|s| format!(".{}", s)).unwrap_or_default();
 310
 311             path.push(format!("{}.{}.{}{}.dot", crate_name, item_name, A::NAME, pass_name));
 312             path
 313         }
 314
 315         None => return Ok(()),
 316     };
 317
 318     let style = match attrs.formatter {
 319         Some(sym::two_phase) => graphviz::OutputStyle::BeforeAndAfter,
 320         _ => graphviz::OutputStyle::AfterOnly,
 321     };
 322
 323     debug!("printing dataflow results for {:?} to {}", def_id, path.display());
 324     let mut buf = Vec::new();
 325
 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);
 331     }
 332     dot::render_opts(&graphviz, &mut buf, &render_opts)?;
 333
 334     if let Some(parent) = path.parent() {
 335         fs::create_dir_all(parent)?;
 336     }
 337     fs::write(&path, buf)?;
 338
 339     Ok(())
 340 }
 341
 342 #[derive(Default)]
 343 struct RustcMirAttrs {
 344     basename_and_suffix: Option<PathBuf>,
 345     formatter: Option<Symbol>,
 346 }
 347
 348 impl RustcMirAttrs {
 349     fn parse(tcx: TyCtxt<'tcx>, def_id: DefId) -> Result<Self, ()> {
 350         let attrs = tcx.get_attrs(def_id);
 351
 352         let mut result = Ok(());
 353         let mut ret = RustcMirAttrs::default();
 354
 355         let rustc_mir_attrs = attrs
 356             .iter()
 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()));
 359
 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() {
 365                         Some(_) => Ok(path),
 366                         None => {
 367                             tcx.sess.span_err(attr.span(), "path must end in a filename");
 368                             Err(())
 369                         }
 370                     }
 371                 })
 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),
 375                     _ => {
 376                         tcx.sess.span_err(attr.span(), "unknown formatter");
 377                         Err(())
 378                     }
 379                 })
 380             } else {
 381                 Ok(())
 382             };
 383
 384             result = result.and(attr_result);
 385         }
 386
 387         result.map(|()| ret)
 388     }
 389
 390     fn set_field<T>(
 391         field: &mut Option<T>,
 392         tcx: TyCtxt<'tcx>,
 393         attr: &ast::NestedMetaItem,
 394         mapper: impl FnOnce(Symbol) -> Result<T, ()>,
 395     ) -> Result<(), ()> {
 396         if field.is_some() {
 397             tcx.sess
 398                 .span_err(attr.span(), &format!("duplicate values for `{}`", attr.name_or_empty()));
 399
 400             return Err(());
 401         }
 402
 403         if let Some(s) = attr.value_str() {
 404             *field = Some(mapper(s)?);
 405             Ok(())
 406         } else {
 407             tcx.sess
 408                 .span_err(attr.span(), &format!("`{}` requires an argument", attr.name_or_empty()));
 409             Err(())
 410         }
 411     }
 412
 413     /// Returns the path where dataflow results should be written, or `None`
 414     /// `borrowck_graphviz_postflow` was not specified.
 415     ///
 416     /// This performs the following transformation to the argument of `borrowck_graphviz_postflow`:
 417     ///
 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
 422
 423         let mut file_name: OsString = analysis_name.into();
 424         file_name.push("_");
 425         file_name.push(suffix);
 426         ret.set_file_name(file_name);
 427
 428         Some(ret)
 429     }
 430 }