src/librustc_mir/dataflow/generic/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::mir::{self, traversal, BasicBlock, Location};
   8 use rustc::ty::{self, TyCtxt};
   9 use rustc_data_structures::work_queue::WorkQueue;
  10 use rustc_hir::def_id::DefId;
  11 use rustc_index::bit_set::BitSet;
  12 use rustc_index::vec::IndexVec;
  13 use rustc_span::symbol::{sym, Symbol};
  14 use syntax::ast;
  15
  16 use super::graphviz;
  17 use super::{Analysis, GenKillAnalysis, GenKillSet, Results};
  18
  19 /// A solver for dataflow problems.
  20 pub struct Engine<'a, 'tcx, A>
  21 where
  22     A: Analysis<'tcx>,
  23 {
  24     bits_per_block: usize,
  25     tcx: TyCtxt<'tcx>,
  26     body: &'a mir::Body<'tcx>,
  27     def_id: DefId,
  28     dead_unwinds: Option<&'a BitSet<BasicBlock>>,
  29     entry_sets: IndexVec<BasicBlock, BitSet<A::Idx>>,
  30     analysis: A,
  31
  32     /// Cached, cumulative transfer functions for each block.
  33     trans_for_block: Option<IndexVec<BasicBlock, GenKillSet<A::Idx>>>,
  34 }
  35
  36 impl<A> Engine<'a, 'tcx, A>
  37 where
  38     A: GenKillAnalysis<'tcx>,
  39 {
  40     /// Creates a new `Engine` to solve a gen-kill dataflow problem.
  41     pub fn new_gen_kill(
  42         tcx: TyCtxt<'tcx>,
  43         body: &'a mir::Body<'tcx>,
  44         def_id: DefId,
  45         analysis: A,
  46     ) -> Self {
  47         // If there are no back-edges in the control-flow graph, we only ever need to apply the
  48         // transfer function for each block exactly once (assuming that we process blocks in RPO).
  49         //
  50         // In this case, there's no need to compute the block transfer functions ahead of time.
  51         if !body.is_cfg_cyclic() {
  52             return Self::new(tcx, body, def_id, analysis, None);
  53         }
  54
  55         // Otherwise, compute and store the cumulative transfer function for each block.
  56
  57         let bits_per_block = analysis.bits_per_block(body);
  58         let mut trans_for_block =
  59             IndexVec::from_elem(GenKillSet::identity(bits_per_block), body.basic_blocks());
  60
  61         for (block, block_data) in body.basic_blocks().iter_enumerated() {
  62             let trans = &mut trans_for_block[block];
  63
  64             for (i, statement) in block_data.statements.iter().enumerate() {
  65                 let loc = Location { block, statement_index: i };
  66                 analysis.before_statement_effect(trans, statement, loc);
  67                 analysis.statement_effect(trans, statement, loc);
  68             }
  69
  70             let terminator = block_data.terminator();
  71             let loc = Location { block, statement_index: block_data.statements.len() };
  72             analysis.before_terminator_effect(trans, terminator, loc);
  73             analysis.terminator_effect(trans, terminator, loc);
  74         }
  75
  76         Self::new(tcx, body, def_id, analysis, Some(trans_for_block))
  77     }
  78 }
  79
  80 impl<A> Engine<'a, 'tcx, A>
  81 where
  82     A: Analysis<'tcx>,
  83 {
  84     /// Creates a new `Engine` to solve a dataflow problem with an arbitrary transfer
  85     /// function.
  86     ///
  87     /// Gen-kill problems should use `new_gen_kill`, which will coalesce transfer functions for
  88     /// better performance.
  89     pub fn new_generic(
  90         tcx: TyCtxt<'tcx>,
  91         body: &'a mir::Body<'tcx>,
  92         def_id: DefId,
  93         analysis: A,
  94     ) -> Self {
  95         Self::new(tcx, body, def_id, analysis, None)
  96     }
  97
  98     fn new(
  99         tcx: TyCtxt<'tcx>,
 100         body: &'a mir::Body<'tcx>,
 101         def_id: DefId,
 102         analysis: A,
 103         trans_for_block: Option<IndexVec<BasicBlock, GenKillSet<A::Idx>>>,
 104     ) -> Self {
 105         let bits_per_block = analysis.bits_per_block(body);
 106
 107         let bottom_value_set = if A::BOTTOM_VALUE {
 108             BitSet::new_filled(bits_per_block)
 109         } else {
 110             BitSet::new_empty(bits_per_block)
 111         };
 112
 113         let mut entry_sets = IndexVec::from_elem(bottom_value_set, body.basic_blocks());
 114         analysis.initialize_start_block(body, &mut entry_sets[mir::START_BLOCK]);
 115
 116         Engine {
 117             analysis,
 118             bits_per_block,
 119             tcx,
 120             body,
 121             def_id,
 122             dead_unwinds: None,
 123             entry_sets,
 124             trans_for_block,
 125         }
 126     }
 127
 128     /// Signals that we do not want dataflow state to propagate across unwind edges for these
 129     /// `BasicBlock`s.
 130     ///
 131     /// You must take care that `dead_unwinds` does not contain a `BasicBlock` that *can* actually
 132     /// unwind during execution. Otherwise, your dataflow results will not be correct.
 133     pub fn dead_unwinds(mut self, dead_unwinds: &'a BitSet<BasicBlock>) -> Self {
 134         self.dead_unwinds = Some(dead_unwinds);
 135         self
 136     }
 137
 138     /// Computes the fixpoint for this dataflow problem and returns it.
 139     pub fn iterate_to_fixpoint(mut self) -> Results<'tcx, A> {
 140         let mut temp_state = BitSet::new_empty(self.bits_per_block);
 141
 142         let mut dirty_queue: WorkQueue<BasicBlock> =
 143             WorkQueue::with_none(self.body.basic_blocks().len());
 144
 145         for (bb, _) in traversal::reverse_postorder(self.body) {
 146             dirty_queue.insert(bb);
 147         }
 148
 149         // Add blocks that are not reachable from START_BLOCK to the work queue. These blocks will
 150         // be processed after the ones added above.
 151         for bb in self.body.basic_blocks().indices() {
 152             dirty_queue.insert(bb);
 153         }
 154
 155         while let Some(bb) = dirty_queue.pop() {
 156             let bb_data = &self.body[bb];
 157             let on_entry = &self.entry_sets[bb];
 158
 159             temp_state.overwrite(on_entry);
 160             self.apply_whole_block_effect(&mut temp_state, bb, bb_data);
 161
 162             self.propagate_bits_into_graph_successors_of(
 163                 &mut temp_state,
 164                 (bb, bb_data),
 165                 &mut dirty_queue,
 166             );
 167         }
 168
 169         let Engine { tcx, body, def_id, trans_for_block, entry_sets, analysis, .. } = self;
 170         let results = Results { analysis, entry_sets };
 171
 172         let res = write_graphviz_results(tcx, def_id, body, &results, trans_for_block);
 173         if let Err(e) = res {
 174             warn!("Failed to write graphviz dataflow results: {}", e);
 175         }
 176
 177         results
 178     }
 179
 180     /// Applies the cumulative effect of an entire block, excluding the call return effect if one
 181     /// exists.
 182     fn apply_whole_block_effect(
 183         &self,
 184         state: &mut BitSet<A::Idx>,
 185         block: BasicBlock,
 186         block_data: &mir::BasicBlockData<'tcx>,
 187     ) {
 188         // Use the cached block transfer function if available.
 189         if let Some(trans_for_block) = &self.trans_for_block {
 190             trans_for_block[block].apply(state);
 191             return;
 192         }
 193
 194         // Otherwise apply effects one-by-one.
 195
 196         for (statement_index, statement) in block_data.statements.iter().enumerate() {
 197             let location = Location { block, statement_index };
 198             self.analysis.apply_before_statement_effect(state, statement, location);
 199             self.analysis.apply_statement_effect(state, statement, location);
 200         }
 201
 202         let terminator = block_data.terminator();
 203         let location = Location { block, statement_index: block_data.statements.len() };
 204         self.analysis.apply_before_terminator_effect(state, terminator, location);
 205         self.analysis.apply_terminator_effect(state, terminator, location);
 206     }
 207
 208     fn propagate_bits_into_graph_successors_of(
 209         &mut self,
 210         in_out: &mut BitSet<A::Idx>,
 211         (bb, bb_data): (BasicBlock, &'a mir::BasicBlockData<'tcx>),
 212         dirty_list: &mut WorkQueue<BasicBlock>,
 213     ) {
 214         use mir::TerminatorKind::*;
 215
 216         match bb_data.terminator().kind {
 217             Return | Resume | Abort | GeneratorDrop | Unreachable => {}
 218
 219             Goto { target }
 220             | Assert { target, cleanup: None, .. }
 221             | Yield { resume: target, drop: None, .. }
 222             | Drop { target, location: _, unwind: None }
 223             | DropAndReplace { target, value: _, location: _, unwind: None } => {
 224                 self.propagate_bits_into_entry_set_for(in_out, target, dirty_list)
 225             }
 226
 227             Yield { resume: target, drop: Some(drop), .. } => {
 228                 self.propagate_bits_into_entry_set_for(in_out, target, dirty_list);
 229                 self.propagate_bits_into_entry_set_for(in_out, drop, dirty_list);
 230             }
 231
 232             Assert { target, cleanup: Some(unwind), .. }
 233             | Drop { target, location: _, unwind: Some(unwind) }
 234             | DropAndReplace { target, value: _, location: _, unwind: Some(unwind) } => {
 235                 self.propagate_bits_into_entry_set_for(in_out, target, dirty_list);
 236                 if self.dead_unwinds.map_or(true, |bbs| !bbs.contains(bb)) {
 237                     self.propagate_bits_into_entry_set_for(in_out, unwind, dirty_list);
 238                 }
 239             }
 240
 241             SwitchInt { ref targets, ref values, ref discr, .. } => {
 242                 self.propagate_bits_into_switch_int_successors(
 243                     in_out,
 244                     (bb, bb_data),
 245                     dirty_list,
 246                     discr,
 247                     &*values,
 248                     &*targets,
 249                 );
 250             }
 251
 252             Call { cleanup, ref destination, ref func, ref args, .. } => {
 253                 if let Some(unwind) = cleanup {
 254                     if self.dead_unwinds.map_or(true, |bbs| !bbs.contains(bb)) {
 255                         self.propagate_bits_into_entry_set_for(in_out, unwind, dirty_list);
 256                     }
 257                 }
 258
 259                 if let Some((ref dest_place, dest_bb)) = *destination {
 260                     // N.B.: This must be done *last*, otherwise the unwind path will see the call
 261                     // return effect.
 262                     self.analysis.apply_call_return_effect(in_out, bb, func, args, dest_place);
 263                     self.propagate_bits_into_entry_set_for(in_out, dest_bb, dirty_list);
 264                 }
 265             }
 266
 267             FalseEdges { real_target, imaginary_target } => {
 268                 self.propagate_bits_into_entry_set_for(in_out, real_target, dirty_list);
 269                 self.propagate_bits_into_entry_set_for(in_out, imaginary_target, dirty_list);
 270             }
 271
 272             FalseUnwind { real_target, unwind } => {
 273                 self.propagate_bits_into_entry_set_for(in_out, real_target, dirty_list);
 274                 if let Some(unwind) = unwind {
 275                     if self.dead_unwinds.map_or(true, |bbs| !bbs.contains(bb)) {
 276                         self.propagate_bits_into_entry_set_for(in_out, unwind, dirty_list);
 277                     }
 278                 }
 279             }
 280         }
 281     }
 282
 283     fn propagate_bits_into_entry_set_for(
 284         &mut self,
 285         in_out: &BitSet<A::Idx>,
 286         bb: BasicBlock,
 287         dirty_queue: &mut WorkQueue<BasicBlock>,
 288     ) {
 289         let entry_set = &mut self.entry_sets[bb];
 290         let set_changed = self.analysis.join(entry_set, &in_out);
 291         if set_changed {
 292             dirty_queue.insert(bb);
 293         }
 294     }
 295
 296     fn propagate_bits_into_switch_int_successors(
 297         &mut self,
 298         in_out: &mut BitSet<A::Idx>,
 299         (bb, bb_data): (BasicBlock, &mir::BasicBlockData<'tcx>),
 300         dirty_list: &mut WorkQueue<BasicBlock>,
 301         switch_on: &mir::Operand<'tcx>,
 302         values: &[u128],
 303         targets: &[BasicBlock],
 304     ) {
 305         match bb_data.statements.last().map(|stmt| &stmt.kind) {
 306             // Look at the last statement to see if it is an assignment of an enum discriminant to
 307             // the local that determines the target of a `SwitchInt` like so:
 308             //   _42 = discriminant(..)
 309             //   SwitchInt(_42, ..)
 310             Some(mir::StatementKind::Assign(box (lhs, mir::Rvalue::Discriminant(enum_))))
 311                 if Some(lhs) == switch_on.place() =>
 312             {
 313                 let adt = match enum_.ty(self.body, self.tcx).ty.kind {
 314                     ty::Adt(def, _) => def,
 315                     _ => bug!("Switch on discriminant of non-ADT"),
 316                 };
 317
 318                 // MIR building adds discriminants to the `values` array in the same order as they
 319                 // are yielded by `AdtDef::discriminants`. We rely on this to match each
 320                 // discriminant in `values` to its corresponding variant in linear time.
 321                 let mut tmp = BitSet::new_empty(in_out.domain_size());
 322                 let mut discriminants = adt.discriminants(self.tcx);
 323                 for (value, target) in values.iter().zip(targets.iter().copied()) {
 324                     let (variant_idx, _) =
 325                         discriminants.find(|&(_, discr)| discr.val == *value).expect(
 326                             "Order of `AdtDef::discriminants` differed \
 327                                  from that of `SwitchInt::values`",
 328                         );
 329
 330                     tmp.overwrite(in_out);
 331                     self.analysis.apply_discriminant_switch_effect(
 332                         &mut tmp,
 333                         bb,
 334                         enum_,
 335                         adt,
 336                         variant_idx,
 337                     );
 338                     self.propagate_bits_into_entry_set_for(&tmp, target, dirty_list);
 339                 }
 340
 341                 std::mem::drop(tmp);
 342
 343                 // Propagate dataflow state along the "otherwise" edge.
 344                 let otherwise = targets.last().copied().unwrap();
 345                 self.propagate_bits_into_entry_set_for(&in_out, otherwise, dirty_list);
 346             }
 347
 348             _ => {
 349                 for target in targets.iter().copied() {
 350                     self.propagate_bits_into_entry_set_for(&in_out, target, dirty_list);
 351                 }
 352             }
 353         }
 354     }
 355 }
 356
 357 // Graphviz
 358
 359 /// Writes a DOT file containing the results of a dataflow analysis if the user requested it via
 360 /// `rustc_mir` attributes.
 361 fn write_graphviz_results<A>(
 362     tcx: TyCtxt<'tcx>,
 363     def_id: DefId,
 364     body: &mir::Body<'tcx>,
 365     results: &Results<'tcx, A>,
 366     block_transfer_functions: Option<IndexVec<BasicBlock, GenKillSet<A::Idx>>>,
 367 ) -> std::io::Result<()>
 368 where
 369     A: Analysis<'tcx>,
 370 {
 371     let attrs = match RustcMirAttrs::parse(tcx, def_id) {
 372         Ok(attrs) => attrs,
 373
 374         // Invalid `rustc_mir` attrs will be reported using `span_err`.
 375         Err(()) => return Ok(()),
 376     };
 377
 378     let path = match attrs.output_path(A::NAME) {
 379         Some(path) => path,
 380         None => return Ok(()),
 381     };
 382
 383     let bits_per_block = results.analysis.bits_per_block(body);
 384
 385     let mut formatter: Box<dyn graphviz::StateFormatter<'tcx, _>> = match attrs.formatter {
 386         Some(sym::two_phase) => Box::new(graphviz::TwoPhaseDiff::new(bits_per_block)),
 387         Some(sym::gen_kill) => {
 388             if let Some(trans_for_block) = block_transfer_functions {
 389                 Box::new(graphviz::BlockTransferFunc::new(body, trans_for_block))
 390             } else {
 391                 Box::new(graphviz::SimpleDiff::new(bits_per_block))
 392             }
 393         }
 394
 395         // Default to the `SimpleDiff` output style.
 396         _ => Box::new(graphviz::SimpleDiff::new(bits_per_block)),
 397     };
 398
 399     debug!("printing dataflow results for {:?} to {}", def_id, path.display());
 400     let mut buf = Vec::new();
 401
 402     let graphviz = graphviz::Formatter::new(body, def_id, results, &mut *formatter);
 403     dot::render_opts(&graphviz, &mut buf, &[dot::RenderOption::Monospace])?;
 404     fs::write(&path, buf)?;
 405     Ok(())
 406 }
 407
 408 #[derive(Default)]
 409 struct RustcMirAttrs {
 410     basename_and_suffix: Option<PathBuf>,
 411     formatter: Option<Symbol>,
 412 }
 413
 414 impl RustcMirAttrs {
 415     fn parse(tcx: TyCtxt<'tcx>, def_id: DefId) -> Result<Self, ()> {
 416         let attrs = tcx.get_attrs(def_id);
 417
 418         let mut result = Ok(());
 419         let mut ret = RustcMirAttrs::default();
 420
 421         let rustc_mir_attrs = attrs
 422             .into_iter()
 423             .filter(|attr| attr.check_name(sym::rustc_mir))
 424             .flat_map(|attr| attr.meta_item_list().into_iter().flat_map(|v| v.into_iter()));
 425
 426         for attr in rustc_mir_attrs {
 427             let attr_result = if attr.check_name(sym::borrowck_graphviz_postflow) {
 428                 Self::set_field(&mut ret.basename_and_suffix, tcx, &attr, |s| {
 429                     let path = PathBuf::from(s.to_string());
 430                     match path.file_name() {
 431                         Some(_) => Ok(path),
 432                         None => {
 433                             tcx.sess.span_err(attr.span(), "path must end in a filename");
 434                             Err(())
 435                         }
 436                     }
 437                 })
 438             } else if attr.check_name(sym::borrowck_graphviz_format) {
 439                 Self::set_field(&mut ret.formatter, tcx, &attr, |s| match s {
 440                     sym::gen_kill | sym::two_phase => Ok(s),
 441                     _ => {
 442                         tcx.sess.span_err(attr.span(), "unknown formatter");
 443                         Err(())
 444                     }
 445                 })
 446             } else {
 447                 Ok(())
 448             };
 449
 450             result = result.and(attr_result);
 451         }
 452
 453         result.map(|()| ret)
 454     }
 455
 456     fn set_field<T>(
 457         field: &mut Option<T>,
 458         tcx: TyCtxt<'tcx>,
 459         attr: &ast::NestedMetaItem,
 460         mapper: impl FnOnce(Symbol) -> Result<T, ()>,
 461     ) -> Result<(), ()> {
 462         if field.is_some() {
 463             tcx.sess
 464                 .span_err(attr.span(), &format!("duplicate values for `{}`", attr.name_or_empty()));
 465
 466             return Err(());
 467         }
 468
 469         if let Some(s) = attr.value_str() {
 470             *field = Some(mapper(s)?);
 471             Ok(())
 472         } else {
 473             tcx.sess
 474                 .span_err(attr.span(), &format!("`{}` requires an argument", attr.name_or_empty()));
 475             Err(())
 476         }
 477     }
 478
 479     /// Returns the path where dataflow results should be written, or `None`
 480     /// `borrowck_graphviz_postflow` was not specified.
 481     ///
 482     /// This performs the following transformation to the argument of `borrowck_graphviz_postflow`:
 483     ///
 484     /// "path/suffix.dot" -> "path/analysis_name_suffix.dot"
 485     fn output_path(&self, analysis_name: &str) -> Option<PathBuf> {
 486         let mut ret = self.basename_and_suffix.as_ref().cloned()?;
 487         let suffix = ret.file_name().unwrap(); // Checked when parsing attrs
 488
 489         let mut file_name: OsString = analysis_name.into();
 490         file_name.push("_");
 491         file_name.push(suffix);
 492         ret.set_file_name(file_name);
 493
 494         Some(ret)
 495     }
 496 }