compiler/rustc_mir_dataflow/src/framework/engine.rs

   1 //! A solver for dataflow problems.
   2
   3 use crate::errors::{
   4     DuplicateValuesFor, PathMustEndInFilename, RequiresAnArgument, UnknownFormatter,
   5 };
   6 use crate::framework::BitSetExt;
   7
   8 use std::ffi::OsString;
   9 use std::path::PathBuf;
  10
  11 use rustc_ast as ast;
  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};
  21
  22 use super::fmt::DebugWithContext;
  23 use super::graphviz;
  24 use super::{
  25     visit_results, Analysis, Direction, GenKill, GenKillAnalysis, GenKillSet, JoinSemiLattice,
  26     ResultsCursor, ResultsVisitor,
  27 };
  28
  29 /// A dataflow analysis that has converged to fixpoint.
  30 pub struct Results<'tcx, A>
  31 where
  32     A: Analysis<'tcx>,
  33 {
  34     pub analysis: A,
  35     pub(super) entry_sets: IndexVec<BasicBlock, A::Domain>,
  36 }
  37
  38 impl<'tcx, A> Results<'tcx, A>
  39 where
  40     A: Analysis<'tcx>,
  41 {
  42     /// Creates a `ResultsCursor` that can inspect these `Results`.
  43     pub fn into_results_cursor<'mir>(
  44         self,
  45         body: &'mir mir::Body<'tcx>,
  46     ) -> ResultsCursor<'mir, 'tcx, A> {
  47         ResultsCursor::new(body, self)
  48     }
  49
  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]
  53     }
  54
  55     pub fn visit_with<'mir>(
  56         &self,
  57         body: &'mir mir::Body<'tcx>,
  58         blocks: impl IntoIterator<Item = BasicBlock>,
  59         vis: &mut impl ResultsVisitor<'mir, 'tcx, FlowState = A::Domain>,
  60     ) {
  61         visit_results(body, blocks, self, vis)
  62     }
  63
  64     pub fn visit_reachable_with<'mir>(
  65         &self,
  66         body: &'mir mir::Body<'tcx>,
  67         vis: &mut impl ResultsVisitor<'mir, 'tcx, FlowState = A::Domain>,
  68     ) {
  69         let blocks = mir::traversal::reachable(body);
  70         visit_results(body, blocks.map(|(bb, _)| bb), self, vis)
  71     }
  72 }
  73
  74 /// A solver for dataflow problems.
  75 pub struct Engine<'a, 'tcx, A>
  76 where
  77     A: Analysis<'tcx>,
  78 {
  79     tcx: TyCtxt<'tcx>,
  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>,
  84     analysis: A,
  85
  86     /// Cached, cumulative transfer functions for each block.
  87     //
  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)>>,
  93 }
  94
  95 impl<'a, 'tcx, A, D, T> Engine<'a, 'tcx, A>
  96 where
  97     A: GenKillAnalysis<'tcx, Idx = T, Domain = D>,
  98     D: Clone + JoinSemiLattice + GenKill<T> + BitSetExt<T>,
  99     T: Idx,
 100 {
 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).
 105         //
 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);
 109         }
 110
 111         // Otherwise, compute and store the cumulative transfer function for each block.
 112
 113         let identity = GenKillSet::identity(analysis.bottom_value(body).domain_size());
 114         let mut trans_for_block = IndexVec::from_elem(identity, &body.basic_blocks);
 115
 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);
 119         }
 120
 121         let apply_trans = Box::new(move |bb: BasicBlock, state: &mut A::Domain| {
 122             trans_for_block[bb].apply(state);
 123         });
 124
 125         Self::new(tcx, body, analysis, Some(apply_trans as Box<_>))
 126     }
 127 }
 128
 129 impl<'a, 'tcx, A, D> Engine<'a, 'tcx, A>
 130 where
 131     A: Analysis<'tcx, Domain = D>,
 132     D: Clone + JoinSemiLattice,
 133 {
 134     /// Creates a new `Engine` to solve a dataflow problem with an arbitrary transfer
 135     /// function.
 136     ///
 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)
 141     }
 142
 143     fn new(
 144         tcx: TyCtxt<'tcx>,
 145         body: &'a mir::Body<'tcx>,
 146         analysis: A,
 147         apply_trans_for_block: Option<Box<dyn Fn(BasicBlock, &mut A::Domain)>>,
 148     ) -> Self {
 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]);
 152
 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");
 155         }
 156
 157         Engine {
 158             analysis,
 159             tcx,
 160             body,
 161             dead_unwinds: None,
 162             pass_name: None,
 163             entry_sets,
 164             apply_trans_for_block,
 165         }
 166     }
 167
 168     /// Signals that we do not want dataflow state to propagate across unwind edges for these
 169     /// `BasicBlock`s.
 170     ///
 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);
 175         self
 176     }
 177
 178     /// Adds an identifier to the graphviz output for this particular run of a dataflow analysis.
 179     ///
 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);
 184         self
 185     }
 186
 187     /// Computes the fixpoint for this dataflow problem and returns it.
 188     pub fn iterate_to_fixpoint(self) -> Results<'tcx, A>
 189     where
 190         A::Domain: DebugWithContext<A>,
 191     {
 192         let Engine {
 193             analysis,
 194             body,
 195             dead_unwinds,
 196             mut entry_sets,
 197             tcx,
 198             apply_trans_for_block,
 199             pass_name,
 200             ..
 201         } = self;
 202
 203         let mut dirty_queue: WorkQueue<BasicBlock> = WorkQueue::with_none(body.basic_blocks.len());
 204
 205         if A::Direction::IS_FORWARD {
 206             for (bb, _) in traversal::reverse_postorder(body) {
 207                 dirty_queue.insert(bb);
 208             }
 209         } else {
 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);
 214             }
 215         }
 216
 217         // `state` is not actually used between iterations;
 218         // this is just an optimization to avoid reallocating
 219         // every iteration.
 220         let mut state = analysis.bottom_value(body);
 221         while let Some(bb) = dirty_queue.pop() {
 222             let bb_data = &body[bb];
 223
 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]);
 228
 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),
 233             }
 234
 235             A::Direction::join_state_into_successors_of(
 236                 &analysis,
 237                 tcx,
 238                 body,
 239                 dead_unwinds,
 240                 &mut state,
 241                 (bb, bb_data),
 242                 |target: BasicBlock, state: &A::Domain| {
 243                     let set_changed = entry_sets[target].join(state);
 244                     if set_changed {
 245                         dirty_queue.insert(target);
 246                     }
 247                 },
 248             );
 249         }
 250
 251         let results = Results { analysis, entry_sets };
 252
 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);
 256         }
 257
 258         results
 259     }
 260 }
 261
 262 // Graphviz
 263
 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>(
 267     tcx: TyCtxt<'tcx>,
 268     body: &mir::Body<'tcx>,
 269     results: &Results<'tcx, A>,
 270     pass_name: Option<&'static str>,
 271 ) -> std::io::Result<()>
 272 where
 273     A: Analysis<'tcx>,
 274     A::Domain: DebugWithContext<A>,
 275 {
 276     use std::fs;
 277     use std::io::{self, Write};
 278
 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`
 282         return Ok(());
 283     };
 284
 285     let mut file = match attrs.output_path(A::NAME) {
 286         Some(path) => {
 287             debug!("printing dataflow results for {:?} to {}", def_id, path.display());
 288             if let Some(parent) = path.parent() {
 289                 fs::create_dir_all(parent)?;
 290             }
 291             io::BufWriter::new(fs::File::create(&path)?)
 292         }
 293
 294         None if tcx.sess.opts.unstable_opts.dump_mir_dataflow
 295             && dump_enabled(tcx, A::NAME, def_id) =>
 296         {
 297             create_dump_file(tcx, ".dot", false, A::NAME, &pass_name.unwrap_or("-----"), body)?
 298         }
 299
 300         _ => return Ok(()),
 301     };
 302
 303     let style = match attrs.formatter {
 304         Some(sym::two_phase) => graphviz::OutputStyle::BeforeAndAfter,
 305         _ => graphviz::OutputStyle::AfterOnly,
 306     };
 307
 308     let mut buf = Vec::new();
 309
 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);
 315     }
 316     dot::render_opts(&graphviz, &mut buf, &render_opts)?;
 317
 318     file.write_all(&buf)?;
 319
 320     Ok(())
 321 }
 322
 323 #[derive(Default)]
 324 struct RustcMirAttrs {
 325     basename_and_suffix: Option<PathBuf>,
 326     formatter: Option<Symbol>,
 327 }
 328
 329 impl RustcMirAttrs {
 330     fn parse(tcx: TyCtxt<'_>, def_id: DefId) -> Result<Self, ()> {
 331         let mut result = Ok(());
 332         let mut ret = RustcMirAttrs::default();
 333
 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()));
 337
 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() {
 343                         Some(_) => Ok(path),
 344                         None => {
 345                             tcx.sess.emit_err(PathMustEndInFilename { span: attr.span() });
 346                             Err(())
 347                         }
 348                     }
 349                 })
 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),
 353                     _ => {
 354                         tcx.sess.emit_err(UnknownFormatter { span: attr.span() });
 355                         Err(())
 356                     }
 357                 })
 358             } else {
 359                 Ok(())
 360             };
 361
 362             result = result.and(attr_result);
 363         }
 364
 365         result.map(|()| ret)
 366     }
 367
 368     fn set_field<T>(
 369         field: &mut Option<T>,
 370         tcx: TyCtxt<'_>,
 371         attr: &ast::NestedMetaItem,
 372         mapper: impl FnOnce(Symbol) -> Result<T, ()>,
 373     ) -> Result<(), ()> {
 374         if field.is_some() {
 375             tcx.sess.emit_err(DuplicateValuesFor { span: attr.span(), name: 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.emit_err(RequiresAnArgument { span: attr.span(), name: attr.name_or_empty() });
 385             Err(())
 386         }
 387     }
 388
 389     /// Returns the path where dataflow results should be written, or `None`
 390     /// `borrowck_graphviz_postflow` was not specified.
 391     ///
 392     /// This performs the following transformation to the argument of `borrowck_graphviz_postflow`:
 393     ///
 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
 398
 399         let mut file_name: OsString = analysis_name.into();
 400         file_name.push("_");
 401         file_name.push(suffix);
 402         ret.set_file_name(file_name);
 403
 404         Some(ret)
 405     }
 406 }