src/librustc_mir/dataflow/framework/engine.rs

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