compiler/rustc_mir_dataflow/src/framework/engine.rs

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