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::path::PathBuf;
   6
   7 use rustc_ast as ast;
   8 use rustc_data_structures::work_queue::WorkQueue;
   9 use rustc_graphviz as dot;
  10 use rustc_hir::def_id::DefId;
  11 use rustc_index::bit_set::BitSet;
  12 use rustc_index::vec::{Idx, IndexVec};
  13 use rustc_middle::mir::{self, traversal, BasicBlock};
  14 use rustc_middle::ty::TyCtxt;
  15 use rustc_span::symbol::{sym, Symbol};
  16
  17 use super::fmt::DebugWithContext;
  18 use super::graphviz;
  19 use super::{
  20     visit_results, Analysis, Direction, GenKill, GenKillAnalysis, GenKillSet, JoinSemiLattice,
  21     ResultsCursor, ResultsVisitor,
  22 };
  23 use crate::util::pretty::{create_dump_file, dump_enabled};
  24
  25 /// A dataflow analysis that has converged to fixpoint.
  26 pub struct Results<'tcx, A>
  27 where
  28     A: Analysis<'tcx>,
  29 {
  30     pub analysis: A,
  31     pub(super) entry_sets: IndexVec<BasicBlock, A::Domain>,
  32 }
  33
  34 impl<A> Results<'tcx, A>
  35 where
  36     A: Analysis<'tcx>,
  37 {
  38     /// Creates a `ResultsCursor` that can inspect these `Results`.
  39     pub fn into_results_cursor(self, body: &'mir mir::Body<'tcx>) -> ResultsCursor<'mir, 'tcx, A> {
  40         ResultsCursor::new(body, self)
  41     }
  42
  43     /// Gets the dataflow state for the given block.
  44     pub fn entry_set_for_block(&self, block: BasicBlock) -> &A::Domain {
  45         &self.entry_sets[block]
  46     }
  47
  48     pub fn visit_with(
  49         &self,
  50         body: &'mir mir::Body<'tcx>,
  51         blocks: impl IntoIterator<Item = BasicBlock>,
  52         vis: &mut impl ResultsVisitor<'mir, 'tcx, FlowState = A::Domain>,
  53     ) {
  54         visit_results(body, blocks, self, vis)
  55     }
  56
  57     pub fn visit_reachable_with(
  58         &self,
  59         body: &'mir mir::Body<'tcx>,
  60         vis: &mut impl ResultsVisitor<'mir, 'tcx, FlowState = A::Domain>,
  61     ) {
  62         let blocks = mir::traversal::reachable(body);
  63         visit_results(body, blocks.map(|(bb, _)| bb), self, vis)
  64     }
  65 }
  66
  67 /// A solver for dataflow problems.
  68 pub struct Engine<'a, 'tcx, A>
  69 where
  70     A: Analysis<'tcx>,
  71 {
  72     tcx: TyCtxt<'tcx>,
  73     body: &'a mir::Body<'tcx>,
  74     dead_unwinds: Option<&'a BitSet<BasicBlock>>,
  75     entry_sets: IndexVec<BasicBlock, A::Domain>,
  76     pass_name: Option<&'static str>,
  77     analysis: A,
  78
  79     /// Cached, cumulative transfer functions for each block.
  80     //
  81     // FIXME(ecstaticmorse): This boxed `Fn` trait object is invoked inside a tight loop for
  82     // gen/kill problems on cyclic CFGs. This is not ideal, but it doesn't seem to degrade
  83     // performance in practice. I've tried a few ways to avoid this, but they have downsides. See
  84     // the message for the commit that added this FIXME for more information.
  85     apply_trans_for_block: Option<Box<dyn Fn(BasicBlock, &mut A::Domain)>>,
  86 }
  87
  88 impl<A, D, T> Engine<'a, 'tcx, A>
  89 where
  90     A: GenKillAnalysis<'tcx, Idx = T, Domain = D>,
  91     D: Clone + JoinSemiLattice + GenKill<T> + BorrowMut<BitSet<T>>,
  92     T: Idx,
  93 {
  94     /// Creates a new `Engine` to solve a gen-kill dataflow problem.
  95     pub fn new_gen_kill(tcx: TyCtxt<'tcx>, body: &'a mir::Body<'tcx>, analysis: A) -> Self {
  96         // If there are no back-edges in the control-flow graph, we only ever need to apply the
  97         // transfer function for each block exactly once (assuming that we process blocks in RPO).
  98         //
  99         // In this case, there's no need to compute the block transfer functions ahead of time.
 100         if !body.is_cfg_cyclic() {
 101             return Self::new(tcx, body, analysis, None);
 102         }
 103
 104         // Otherwise, compute and store the cumulative transfer function for each block.
 105
 106         let identity = GenKillSet::identity(analysis.bottom_value(body).borrow().domain_size());
 107         let mut trans_for_block = IndexVec::from_elem(identity, body.basic_blocks());
 108
 109         for (block, block_data) in body.basic_blocks().iter_enumerated() {
 110             let trans = &mut trans_for_block[block];
 111             A::Direction::gen_kill_effects_in_block(&analysis, trans, block, block_data);
 112         }
 113
 114         let apply_trans = Box::new(move |bb: BasicBlock, state: &mut A::Domain| {
 115             trans_for_block[bb].apply(state.borrow_mut());
 116         });
 117
 118         Self::new(tcx, body, analysis, Some(apply_trans as Box<_>))
 119     }
 120 }
 121
 122 impl<A, D> Engine<'a, 'tcx, A>
 123 where
 124     A: Analysis<'tcx, Domain = D>,
 125     D: Clone + JoinSemiLattice,
 126 {
 127     /// Creates a new `Engine` to solve a dataflow problem with an arbitrary transfer
 128     /// function.
 129     ///
 130     /// Gen-kill problems should use `new_gen_kill`, which will coalesce transfer functions for
 131     /// better performance.
 132     pub fn new_generic(tcx: TyCtxt<'tcx>, body: &'a mir::Body<'tcx>, analysis: A) -> Self {
 133         Self::new(tcx, body, analysis, None)
 134     }
 135
 136     fn new(
 137         tcx: TyCtxt<'tcx>,
 138         body: &'a mir::Body<'tcx>,
 139         analysis: A,
 140         apply_trans_for_block: Option<Box<dyn Fn(BasicBlock, &mut A::Domain)>>,
 141     ) -> Self {
 142         let bottom_value = analysis.bottom_value(body);
 143         let mut entry_sets = IndexVec::from_elem(bottom_value.clone(), body.basic_blocks());
 144         analysis.initialize_start_block(body, &mut entry_sets[mir::START_BLOCK]);
 145
 146         if A::Direction::is_backward() && entry_sets[mir::START_BLOCK] != bottom_value {
 147             bug!("`initialize_start_block` is not yet supported for backward dataflow analyses");
 148         }
 149
 150         Engine {
 151             analysis,
 152             tcx,
 153             body,
 154             dead_unwinds: None,
 155             pass_name: None,
 156             entry_sets,
 157             apply_trans_for_block,
 158         }
 159     }
 160
 161     /// Signals that we do not want dataflow state to propagate across unwind edges for these
 162     /// `BasicBlock`s.
 163     ///
 164     /// You must take care that `dead_unwinds` does not contain a `BasicBlock` that *can* actually
 165     /// unwind during execution. Otherwise, your dataflow results will not be correct.
 166     pub fn dead_unwinds(mut self, dead_unwinds: &'a BitSet<BasicBlock>) -> Self {
 167         self.dead_unwinds = Some(dead_unwinds);
 168         self
 169     }
 170
 171     /// Adds an identifier to the graphviz output for this particular run of a dataflow analysis.
 172     ///
 173     /// Some analyses are run multiple times in the compilation pipeline. Give them a `pass_name`
 174     /// to differentiate them. Otherwise, only the results for the latest run will be saved.
 175     pub fn pass_name(mut self, name: &'static str) -> Self {
 176         self.pass_name = Some(name);
 177         self
 178     }
 179
 180     /// Computes the fixpoint for this dataflow problem and returns it.
 181     pub fn iterate_to_fixpoint(self) -> Results<'tcx, A>
 182     where
 183         A::Domain: DebugWithContext<A>,
 184     {
 185         let Engine {
 186             analysis,
 187             body,
 188             dead_unwinds,
 189             mut entry_sets,
 190             tcx,
 191             apply_trans_for_block,
 192             pass_name,
 193             ..
 194         } = self;
 195
 196         let mut dirty_queue: WorkQueue<BasicBlock> =
 197             WorkQueue::with_none(body.basic_blocks().len());
 198
 199         if A::Direction::is_forward() {
 200             for (bb, _) in traversal::reverse_postorder(body) {
 201                 dirty_queue.insert(bb);
 202             }
 203         } else {
 204             // Reverse post-order on the reverse CFG may generate a better iteration order for
 205             // backward dataflow analyses, but probably not enough to matter.
 206             for (bb, _) in traversal::postorder(body) {
 207                 dirty_queue.insert(bb);
 208             }
 209         }
 210
 211         let mut state = analysis.bottom_value(body);
 212         while let Some(bb) = dirty_queue.pop() {
 213             let bb_data = &body[bb];
 214
 215             // Apply the block transfer function, using the cached one if it exists.
 216             state.clone_from(&entry_sets[bb]);
 217             match &apply_trans_for_block {
 218                 Some(apply) => apply(bb, &mut state),
 219                 None => A::Direction::apply_effects_in_block(&analysis, &mut state, bb, bb_data),
 220             }
 221
 222             A::Direction::join_state_into_successors_of(
 223                 &analysis,
 224                 tcx,
 225                 body,
 226                 dead_unwinds,
 227                 &mut state,
 228                 (bb, bb_data),
 229                 |target: BasicBlock, state: &A::Domain| {
 230                     let set_changed = entry_sets[target].join(state);
 231                     if set_changed {
 232                         dirty_queue.insert(target);
 233                     }
 234                 },
 235             );
 236         }
 237
 238         let results = Results { analysis, entry_sets };
 239
 240         let res = write_graphviz_results(tcx, &body, &results, pass_name);
 241         if let Err(e) = res {
 242             error!("Failed to write graphviz dataflow results: {}", e);
 243         }
 244
 245         results
 246     }
 247 }
 248
 249 // Graphviz
 250
 251 /// Writes a DOT file containing the results of a dataflow analysis if the user requested it via
 252 /// `rustc_mir` attributes.
 253 fn write_graphviz_results<A>(
 254     tcx: TyCtxt<'tcx>,
 255     body: &mir::Body<'tcx>,
 256     results: &Results<'tcx, A>,
 257     pass_name: Option<&'static str>,
 258 ) -> std::io::Result<()>
 259 where
 260     A: Analysis<'tcx>,
 261     A::Domain: DebugWithContext<A>,
 262 {
 263     use std::fs;
 264     use std::io::{self, Write};
 265
 266     let def_id = body.source.def_id();
 267     let attrs = match RustcMirAttrs::parse(tcx, def_id) {
 268         Ok(attrs) => attrs,
 269
 270         // Invalid `rustc_mir` attrs are reported in `RustcMirAttrs::parse`
 271         Err(()) => return Ok(()),
 272     };
 273
 274     let mut file = match attrs.output_path(A::NAME) {
 275         Some(path) => {
 276             debug!("printing dataflow results for {:?} to {}", def_id, path.display());
 277             if let Some(parent) = path.parent() {
 278                 fs::create_dir_all(parent)?;
 279             }
 280             io::BufWriter::new(fs::File::create(&path)?)
 281         }
 282
 283         None if tcx.sess.opts.debugging_opts.dump_mir_dataflow
 284             && dump_enabled(tcx, A::NAME, def_id) =>
 285         {
 286             create_dump_file(
 287                 tcx,
 288                 ".dot",
 289                 None,
 290                 A::NAME,
 291                 &pass_name.unwrap_or("-----"),
 292                 body.source,
 293             )?
 294         }
 295
 296         _ => return Ok(()),
 297     };
 298
 299     let style = match attrs.formatter {
 300         Some(sym::two_phase) => graphviz::OutputStyle::BeforeAndAfter,
 301         _ => graphviz::OutputStyle::AfterOnly,
 302     };
 303
 304     let mut buf = Vec::new();
 305
 306     let graphviz = graphviz::Formatter::new(body, results, style);
 307     let mut render_opts =
 308         vec![dot::RenderOption::Fontname(tcx.sess.opts.debugging_opts.graphviz_font.clone())];
 309     if tcx.sess.opts.debugging_opts.graphviz_dark_mode {
 310         render_opts.push(dot::RenderOption::DarkTheme);
 311     }
 312     dot::render_opts(&graphviz, &mut buf, &render_opts)?;
 313
 314     file.write_all(&buf)?;
 315
 316     Ok(())
 317 }
 318
 319 #[derive(Default)]
 320 struct RustcMirAttrs {
 321     basename_and_suffix: Option<PathBuf>,
 322     formatter: Option<Symbol>,
 323 }
 324
 325 impl RustcMirAttrs {
 326     fn parse(tcx: TyCtxt<'tcx>, def_id: DefId) -> Result<Self, ()> {
 327         let attrs = tcx.get_attrs(def_id);
 328
 329         let mut result = Ok(());
 330         let mut ret = RustcMirAttrs::default();
 331
 332         let rustc_mir_attrs = attrs
 333             .iter()
 334             .filter(|attr| tcx.sess.check_name(attr, sym::rustc_mir))
 335             .flat_map(|attr| attr.meta_item_list().into_iter().flat_map(|v| v.into_iter()));
 336
 337         for attr in rustc_mir_attrs {
 338             let attr_result = if attr.has_name(sym::borrowck_graphviz_postflow) {
 339                 Self::set_field(&mut ret.basename_and_suffix, tcx, &attr, |s| {
 340                     let path = PathBuf::from(s.to_string());
 341                     match path.file_name() {
 342                         Some(_) => Ok(path),
 343                         None => {
 344                             tcx.sess.span_err(attr.span(), "path must end in a filename");
 345                             Err(())
 346                         }
 347                     }
 348                 })
 349             } else if attr.has_name(sym::borrowck_graphviz_format) {
 350                 Self::set_field(&mut ret.formatter, tcx, &attr, |s| match s {
 351                     sym::gen_kill | sym::two_phase => Ok(s),
 352                     _ => {
 353                         tcx.sess.span_err(attr.span(), "unknown formatter");
 354                         Err(())
 355                     }
 356                 })
 357             } else {
 358                 Ok(())
 359             };
 360
 361             result = result.and(attr_result);
 362         }
 363
 364         result.map(|()| ret)
 365     }
 366
 367     fn set_field<T>(
 368         field: &mut Option<T>,
 369         tcx: TyCtxt<'tcx>,
 370         attr: &ast::NestedMetaItem,
 371         mapper: impl FnOnce(Symbol) -> Result<T, ()>,
 372     ) -> Result<(), ()> {
 373         if field.is_some() {
 374             tcx.sess
 375                 .span_err(attr.span(), &format!("duplicate values for `{}`", attr.name_or_empty()));
 376
 377             return Err(());
 378         }
 379
 380         if let Some(s) = attr.value_str() {
 381             *field = Some(mapper(s)?);
 382             Ok(())
 383         } else {
 384             tcx.sess
 385                 .span_err(attr.span(), &format!("`{}` requires an argument", attr.name_or_empty()));
 386             Err(())
 387         }
 388     }
 389
 390     /// Returns the path where dataflow results should be written, or `None`
 391     /// `borrowck_graphviz_postflow` was not specified.
 392     ///
 393     /// This performs the following transformation to the argument of `borrowck_graphviz_postflow`:
 394     ///
 395     /// "path/suffix.dot" -> "path/analysis_name_suffix.dot"
 396     fn output_path(&self, analysis_name: &str) -> Option<PathBuf> {
 397         let mut ret = self.basename_and_suffix.as_ref().cloned()?;
 398         let suffix = ret.file_name().unwrap(); // Checked when parsing attrs
 399
 400         let mut file_name: OsString = analysis_name.into();
 401         file_name.push("_");
 402         file_name.push(suffix);
 403         ret.set_file_name(file_name);
 404
 405         Some(ret)
 406     }
 407 }