diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/librustc_mir/dataflow/generic.rs | 129 | ||||
| -rw-r--r-- | src/librustc_mir/dataflow/generic/graphviz.rs | 412 | ||||
| -rw-r--r-- | src/librustc_mir/transform/check_consts/qualifs.rs | 5 | ||||
| -rw-r--r-- | src/librustc_mir/transform/check_consts/resolver.rs | 5 | ||||
| -rw-r--r-- | src/librustc_mir/transform/check_consts/validation.rs | 4 |
5 files changed, 535 insertions, 20 deletions
diff --git a/src/librustc_mir/dataflow/generic.rs b/src/librustc_mir/dataflow/generic.rs index 6f598469e9d..dd6238b80d1 100644 --- a/src/librustc_mir/dataflow/generic.rs +++ b/src/librustc_mir/dataflow/generic.rs @@ -16,16 +16,24 @@ //! [gk]: https://en.wikipedia.org/wiki/Data-flow_analysis#Bit_vector_problems //! [#64566]: https://github.com/rust-lang/rust/pull/64566 +use std::borrow::Borrow; use std::cmp::Ordering; -use std::ops; +use std::ffi::OsString; +use std::path::{Path, PathBuf}; +use std::{fs, io, ops}; +use rustc::hir::def_id::DefId; use rustc::mir::{self, traversal, BasicBlock, Location}; +use rustc::ty::{self, TyCtxt}; +use rustc_data_structures::work_queue::WorkQueue; use rustc_index::bit_set::BitSet; use rustc_index::vec::{Idx, IndexVec}; -use rustc_data_structures::work_queue::WorkQueue; +use syntax::symbol::sym; use crate::dataflow::BottomValue; +mod graphviz; + /// A specific kind of dataflow analysis. /// /// To run a dataflow analysis, one must set the initial state of the `START_BLOCK` via @@ -62,6 +70,13 @@ pub trait Analysis<'tcx>: BottomValue { /// and try to keep it short. const NAME: &'static str; + /// How each element of your dataflow state will be displayed during debugging. + /// + /// By default, this is the `fmt::Debug` representation of `Self::Idx`. + fn pretty_print_idx(&self, w: &mut impl io::Write, idx: Self::Idx) -> io::Result<()> { + write!(w, "{:?}", idx) + } + /// The size of each bitvector allocated for each block. fn bits_per_block(&self, body: &mir::Body<'tcx>) -> usize; @@ -77,7 +92,7 @@ pub trait Analysis<'tcx>: BottomValue { location: Location, ); - /// Updates the current dataflow state with the effect of evaluating a statement. + /// Updates the current dataflow state with the effect of evaluating a terminator. /// /// Note that the effect of a successful return from a `Call` terminator should **not** be /// acounted for in this function. That should go in `apply_call_return_effect`. For example, @@ -180,17 +195,20 @@ impl CursorPosition { } } +type ResultsRefCursor<'a, 'mir, 'tcx, A> = + ResultsCursor<'mir, 'tcx, A, &'a Results<'tcx, A>>; + /// Inspect the results of dataflow analysis. /// /// This cursor has linear performance when visiting statements in a block in order. Visiting /// statements within a block in reverse order is `O(n^2)`, where `n` is the number of statements /// in that block. -pub struct ResultsCursor<'mir, 'tcx, A> +pub struct ResultsCursor<'mir, 'tcx, A, R = Results<'tcx, A>> where A: Analysis<'tcx>, { body: &'mir mir::Body<'tcx>, - results: Results<'tcx, A>, + results: R, state: BitSet<A::Idx>, pos: CursorPosition, @@ -202,24 +220,29 @@ where is_call_return_effect_applied: bool, } -impl<'mir, 'tcx, A> ResultsCursor<'mir, 'tcx, A> +impl<'mir, 'tcx, A, R> ResultsCursor<'mir, 'tcx, A, R> where A: Analysis<'tcx>, + R: Borrow<Results<'tcx, A>>, { /// Returns a new cursor for `results` that points to the start of the `START_BLOCK`. - pub fn new(body: &'mir mir::Body<'tcx>, results: Results<'tcx, A>) -> Self { + pub fn new(body: &'mir mir::Body<'tcx>, results: R) -> Self { ResultsCursor { body, pos: CursorPosition::AtBlockStart(mir::START_BLOCK), is_call_return_effect_applied: false, - state: results.entry_sets[mir::START_BLOCK].clone(), + state: results.borrow().entry_sets[mir::START_BLOCK].clone(), results, } } + pub fn analysis(&self) -> &A { + &self.results.borrow().analysis + } + /// Resets the cursor to the start of the given `block`. pub fn seek_to_block_start(&mut self, block: BasicBlock) { - self.state.overwrite(&self.results.entry_sets[block]); + self.state.overwrite(&self.results.borrow().entry_sets[block]); self.pos = CursorPosition::AtBlockStart(block); self.is_call_return_effect_applied = false; } @@ -275,7 +298,7 @@ where } = &term.kind { if !self.is_call_return_effect_applied { self.is_call_return_effect_applied = true; - self.results.analysis.apply_call_return_effect( + self.results.borrow().analysis.apply_call_return_effect( &mut self.state, target.block, func, @@ -316,7 +339,7 @@ where }; let block_data = &self.body.basic_blocks()[target_block]; - self.results.analysis.apply_partial_block_effect( + self.results.borrow().analysis.apply_partial_block_effect( &mut self.state, target_block, block_data, @@ -349,7 +372,9 @@ where { analysis: A, bits_per_block: usize, + tcx: TyCtxt<'tcx>, body: &'a mir::Body<'tcx>, + def_id: DefId, dead_unwinds: &'a BitSet<BasicBlock>, entry_sets: IndexVec<BasicBlock, BitSet<A::Idx>>, } @@ -359,7 +384,9 @@ where A: Analysis<'tcx>, { pub fn new( + tcx: TyCtxt<'tcx>, body: &'a mir::Body<'tcx>, + def_id: DefId, dead_unwinds: &'a BitSet<BasicBlock>, analysis: A, ) -> Self { @@ -377,7 +404,9 @@ where Engine { analysis, bits_per_block, + tcx, body, + def_id, dead_unwinds, entry_sets, } @@ -413,10 +442,26 @@ where ); } - Results { - analysis: self.analysis, - entry_sets: self.entry_sets, + let Engine { + tcx, + body, + def_id, + analysis, + entry_sets, + .. + } = self; + + let results = Results { analysis, entry_sets }; + + let attrs = tcx.get_attrs(def_id); + if let Some(path) = get_dataflow_graphviz_output_path(tcx, attrs, A::NAME) { + let result = write_dataflow_graphviz_results(body, def_id, &path, &results); + if let Err(e) = result { + warn!("Failed to write dataflow results to {}: {}", path.display(), e); + } } + + results } fn propagate_bits_into_graph_successors_of( @@ -510,3 +555,59 @@ where } } } + +/// Looks for attributes like `#[rustc_mir(borrowck_graphviz_postflow="./path/to/suffix.dot")]` and +/// extracts the path with the given analysis name prepended to the suffix. +/// +/// Returns `None` if no such attribute exists. +fn get_dataflow_graphviz_output_path( + tcx: TyCtxt<'tcx>, + attrs: ty::Attributes<'tcx>, + analysis: &str, +) -> Option<PathBuf> { + let mut rustc_mir_attrs = attrs + .into_iter() + .filter(|attr| attr.check_name(sym::rustc_mir)) + .flat_map(|attr| attr.meta_item_list().into_iter().flat_map(|v| v.into_iter())); + + let borrowck_graphviz_postflow = rustc_mir_attrs + .find(|attr| attr.check_name(sym::borrowck_graphviz_postflow))?; + + let path_and_suffix = match borrowck_graphviz_postflow.value_str() { + Some(p) => p, + None => { + tcx.sess.span_err( + borrowck_graphviz_postflow.span(), + "borrowck_graphviz_postflow requires a path", + ); + + return None; + } + }; + + // Change "path/suffix.dot" to "path/analysis_name_suffix.dot" + let mut ret = PathBuf::from(path_and_suffix.to_string()); + let suffix = ret.file_name().unwrap(); + + let mut file_name: OsString = analysis.into(); + file_name.push("_"); + file_name.push(suffix); + ret.set_file_name(file_name); + + Some(ret) +} + +fn write_dataflow_graphviz_results<A: Analysis<'tcx>>( + body: &mir::Body<'tcx>, + def_id: DefId, + path: &Path, + results: &Results<'tcx, A> +) -> io::Result<()> { + debug!("printing dataflow results for {:?} to {}", def_id, path.display()); + + let mut buf = Vec::new(); + let graphviz = graphviz::Formatter::new(body, def_id, results); + + dot::render(&graphviz, &mut buf)?; + fs::write(path, buf) +} diff --git a/src/librustc_mir/dataflow/generic/graphviz.rs b/src/librustc_mir/dataflow/generic/graphviz.rs new file mode 100644 index 00000000000..2a08feff9e7 --- /dev/null +++ b/src/librustc_mir/dataflow/generic/graphviz.rs @@ -0,0 +1,412 @@ +use std::cell::RefCell; +use std::io::{self, Write}; +use std::{ops, str}; + +use rustc::hir::def_id::DefId; +use rustc::mir::{self, BasicBlock, Body, Location}; +use rustc_index::bit_set::{BitSet, HybridBitSet}; +use rustc_index::vec::Idx; + +use crate::util::graphviz_safe_def_name; +use super::{Analysis, Results, ResultsRefCursor}; + +pub struct Formatter<'a, 'tcx, A> +where + A: Analysis<'tcx>, +{ + body: &'a Body<'tcx>, + def_id: DefId, + + // This must be behind a `RefCell` because `dot::Labeller` takes `&self`. + block_formatter: RefCell<BlockFormatter<'a, 'tcx, A>>, +} + +impl<A> Formatter<'a, 'tcx, A> +where + A: Analysis<'tcx>, +{ + pub fn new( + body: &'a Body<'tcx>, + def_id: DefId, + results: &'a Results<'tcx, A>, + ) -> Self { + let block_formatter = BlockFormatter { + bg: Background::Light, + prev_state: BitSet::new_empty(results.analysis.bits_per_block(body)), + results: ResultsRefCursor::new(body, results), + }; + + Formatter { + body, + def_id, + block_formatter: RefCell::new(block_formatter), + } + } +} + +/// A pair of a basic block and an index into that basic blocks `successors`. +#[derive(Copy, Clone, PartialEq, Eq, Debug)] +pub struct CfgEdge { + source: BasicBlock, + index: usize, +} + +fn outgoing_edges(body: &Body<'_>, bb: BasicBlock) -> Vec<CfgEdge> { + body[bb] + .terminator() + .successors() + .enumerate() + .map(|(index, _)| CfgEdge { source: bb, index }) + .collect() +} + +impl<A> dot::Labeller<'_> for Formatter<'a, 'tcx, A> +where + A: Analysis<'tcx>, +{ + type Node = BasicBlock; + type Edge = CfgEdge; + + fn graph_id(&self) -> dot::Id<'_> { + let name = graphviz_safe_def_name(self.def_id); + dot::Id::new(format!("graph_for_def_id_{}", name)).unwrap() + } + + fn node_id(&self, n: &Self::Node) -> dot::Id<'_> { + dot::Id::new(format!("bb_{}", n.index())).unwrap() + } + + fn node_label(&self, block: &Self::Node) -> dot::LabelText<'_> { + let mut label = Vec::new(); + self.block_formatter + .borrow_mut() + .write_node_label(&mut label, self.body, *block) + .unwrap(); + dot::LabelText::html(String::from_utf8(label).unwrap()) + } + + fn node_shape(&self, _n: &Self::Node) -> Option<dot::LabelText<'_>> { + Some(dot::LabelText::label("none")) + } + + fn edge_label(&self, e: &Self::Edge) -> dot::LabelText<'_> { + let label = &self.body + [e.source] + .terminator() + .kind + .fmt_successor_labels() + [e.index]; + dot::LabelText::label(label.clone()) + } +} + +impl<A> dot::GraphWalk<'a> for Formatter<'a, 'tcx, A> +where + A: Analysis<'tcx>, +{ + type Node = BasicBlock; + type Edge = CfgEdge; + + fn nodes(&self) -> dot::Nodes<'_, Self::Node> { + self.body + .basic_blocks() + .indices() + .collect::<Vec<_>>() + .into() + } + + fn edges(&self) -> dot::Edges<'_, Self::Edge> { + self.body + .basic_blocks() + .indices() + .flat_map(|bb| outgoing_edges(self.body, bb)) + .collect::<Vec<_>>() + .into() + } + + fn source(&self, edge: &Self::Edge) -> Self::Node { + edge.source + } + + fn target(&self, edge: &Self::Edge) -> Self::Node { + self.body + [edge.source] + .terminator() + .successors() + .nth(edge.index) + .copied() + .unwrap() + } +} + +struct BlockFormatter<'a, 'tcx, A> +where + A: Analysis<'tcx>, +{ + prev_state: BitSet<A::Idx>, + results: ResultsRefCursor<'a, 'a, 'tcx, A>, + bg: Background, +} + +impl<A> BlockFormatter<'a, 'tcx, A> +where + A: Analysis<'tcx>, +{ + fn toggle_background(&mut self) -> Background { + let bg = self.bg; + self.bg = !bg; + bg + } + + fn write_node_label( + &mut self, + w: &mut impl io::Write, + body: &'a Body<'tcx>, + block: BasicBlock, + ) -> io::Result<()> { + // Sample output: + // +-+--------------------------------------------------+ + // A | bb4 | + // +-+----------------------------------+---------------+ + // B | MIR | STATE | + // +-+----------------------------------+---------------+ + // C | | (on entry) | {_0,_2,_3} | + // +-+----------------------------------+---------------+ + // D |0| 0: StorageLive(_7) | | + // +-+----------------------------------+---------------+ + // |1| 1: StorageLive(_8) | | + // +-+----------------------------------+---------------+ + // |2| 2: _8 = &mut _1 | +_8 | + // +-+----------------------------------+---------------+ + // E |T| _7 = const Foo::twiddle(move _8) | -_8 | + // +-+----------------------------------+---------------+ + // F | | (on unwind) | {_0,_2,_3,_7} | + // +-+----------------------------------+---------------+ + // | | (on successful return) | +_7 | + // +-+----------------------------------+---------------+ + + write!( + w, + r#"<table border="1" cellborder="1" cellspacing="0" cellpadding="3" sides="rb">"#, + )?; + + // A: Block info + write!( + w, + r#"<tr> + <td colspan="{num_headers}" sides="tl">bb{block_id}</td> + </tr>"#, + num_headers = 3, + block_id = block.index(), + )?; + + // B: Column headings + write!( + w, + r#"<tr> + <td colspan="2" {fmt}>MIR</td> + <td {fmt}>STATE</td> + </tr>"#, + fmt = r##"bgcolor="#a0a0a0" sides="tl""##, + )?; + + // C: Entry state + self.results.seek_to_block_start(block); + self.write_row_with_curr_state(w, "", "(on entry)")?; + self.prev_state.overwrite(self.results.get()); + + // D: Statement transfer functions + for (i, statement) in body[block].statements.iter().enumerate() { + let location = Location { block, statement_index: i }; + + let mir_col = format!("{:?}", statement); + let i_col = i.to_string(); + + self.results.seek_after(location); + self.write_row_with_curr_diff(w, &i_col, &mir_col)?; + self.prev_state.overwrite(self.results.get()); + } + + // E: Terminator transfer function + let terminator = body[block].terminator(); + let location = body.terminator_loc(block); + + let mut mir_col = String::new(); + terminator.kind.fmt_head(&mut mir_col).unwrap(); + + self.results.seek_after(location); + self.write_row_with_curr_diff(w, "T", &mir_col)?; + self.prev_state.overwrite(self.results.get()); + + // F: Exit state + if let mir::TerminatorKind::Call { destination: Some(_), .. } = &terminator.kind { + self.write_row_with_curr_state(w, "", "(on unwind)")?; + + self.results.seek_after_assume_call_returns(location); + self.write_row_with_curr_diff(w, "", "(on successful return)")?; + } else { + self.write_row_with_curr_state(w, "", "(on exit)")?; + } + + write!(w, "</table>") + } + + fn write_row_with_curr_state( + &mut self, + w: &mut impl io::Write, + i: &str, + mir: &str, + ) -> io::Result<()> { + let bg = self.toggle_background(); + + let mut out = Vec::new(); + write!(&mut out, "{{")?; + pretty_print_state_elems(&mut out, self.results.analysis(), self.results.get().iter())?; + write!(&mut out, "}}")?; + + write!( + w, + r#"<tr> + <td {fmt} align="right">{i}</td> + <td {fmt} align="left">{mir}</td> + <td {fmt} align="left">{state}</td> + </tr>"#, + fmt = &["sides=\"tl\"", bg.attr()].join(" "), + i = i, + mir = dot::escape_html(mir), + state = dot::escape_html(str::from_utf8(&out).unwrap()), + ) + } + + fn write_row_with_curr_diff( + &mut self, + w: &mut impl io::Write, + i: &str, + mir: &str, + ) -> io::Result<()> { + let bg = self.toggle_background(); + let analysis = self.results.analysis(); + + let diff = BitSetDiff::compute(&self.prev_state, self.results.get()); + + let mut set = Vec::new(); + pretty_print_state_elems(&mut set, analysis, diff.set.iter())?; + + let mut clear = Vec::new(); + pretty_print_state_elems(&mut clear, analysis, diff.clear.iter())?; + + write!( + w, + r#"<tr> + <td {fmt} align="right">{i}</td> + <td {fmt} align="left">{mir}</td> + <td {fmt} align="left">"#, + i = i, + fmt = &["sides=\"tl\"", bg.attr()].join(" "), + mir = dot::escape_html(mir), + )?; + + if !set.is_empty() { + write!( + w, + r#"<font color="darkgreen">+{}</font>"#, + dot::escape_html(str::from_utf8(&set).unwrap()), + )?; + } + + if !set.is_empty() && !clear.is_empty() { + write!(w, " ")?; + } + + if !clear.is_empty() { + write!( + w, + r#"<font color="red">-{}</font>"#, + dot::escape_html(str::from_utf8(&clear).unwrap()), + )?; + } + + write!(w, "</td></tr>") + } +} + +/// The operations required to transform one `BitSet` into another. +struct BitSetDiff<T: Idx> { + set: HybridBitSet<T>, + clear: HybridBitSet<T>, +} + +impl<T: Idx> BitSetDiff<T> { + fn compute(from: &BitSet<T>, to: &BitSet<T>) -> Self { + assert_eq!(from.domain_size(), to.domain_size()); + let len = from.domain_size(); + + let mut set = HybridBitSet::new_empty(len); + let mut clear = HybridBitSet::new_empty(len); + + // FIXME: This could be made faster if `BitSet::xor` were implemented. + for i in (0..len).map(|i| T::new(i)) { + match (from.contains(i), to.contains(i)) { + (false, true) => set.insert(i), + (true, false) => clear.insert(i), + _ => continue, + }; + } + + BitSetDiff { + set, + clear, + } + } +} + +/// Formats each `elem` using the pretty printer provided by `analysis` into a comma-separated +/// list. +fn pretty_print_state_elems<A>( + w: &mut impl io::Write, + analysis: &A, + elems: impl Iterator<Item = A::Idx>, +) -> io::Result<()> +where + A: Analysis<'tcx>, +{ + let mut first = true; + for idx in elems { + if first { + first = false; + } else { + write!(w, ",")?; + } + + analysis.pretty_print_idx(w, idx)?; + } + + Ok(()) +} + +/// The background color used for zebra-striping the table. +#[derive(Clone, Copy)] +enum Background { + Light, + Dark, +} + +impl Background { + fn attr(self) -> &'static str { + match self { + Self::Dark => "bgcolor=\"#f0f0f0\"", + Self::Light => "", + } + } +} + +impl ops::Not for Background { + type Output = Self; + + fn not(self) -> Self { + match self { + Self::Light => Self::Dark, + Self::Dark => Self::Light, + } + } +} diff --git a/src/librustc_mir/transform/check_consts/qualifs.rs b/src/librustc_mir/transform/check_consts/qualifs.rs index 0c6468309dc..40007eb3c4a 100644 --- a/src/librustc_mir/transform/check_consts/qualifs.rs +++ b/src/librustc_mir/transform/check_consts/qualifs.rs @@ -27,6 +27,9 @@ impl QualifSet { pub trait Qualif { const IDX: usize; + /// The name of the file used to debug the dataflow analysis that computes this qualif. + const ANALYSIS_NAME: &'static str; + /// Whether this `Qualif` is cleared when a local is moved from. const IS_CLEARED_ON_MOVE: bool = false; @@ -207,6 +210,7 @@ pub struct HasMutInterior; impl Qualif for HasMutInterior { const IDX: usize = 0; + const ANALYSIS_NAME: &'static str = "flow_has_mut_interior"; fn in_any_value_of_ty(cx: &ConstCx<'_, 'tcx>, ty: Ty<'tcx>) -> bool { !ty.is_freeze(cx.tcx, cx.param_env, DUMMY_SP) @@ -264,6 +268,7 @@ pub struct NeedsDrop; impl Qualif for NeedsDrop { const IDX: usize = 1; + const ANALYSIS_NAME: &'static str = "flow_needs_drop"; const IS_CLEARED_ON_MOVE: bool = true; fn in_any_value_of_ty(cx: &ConstCx<'_, 'tcx>, ty: Ty<'tcx>) -> bool { diff --git a/src/librustc_mir/transform/check_consts/resolver.rs b/src/librustc_mir/transform/check_consts/resolver.rs index f95b240195b..4fa4eba4c23 100644 --- a/src/librustc_mir/transform/check_consts/resolver.rs +++ b/src/librustc_mir/transform/check_consts/resolver.rs @@ -208,7 +208,8 @@ where _qualif: PhantomData, }; let results = - dataflow::Engine::new(item.body, dead_unwinds, analysis).iterate_to_fixpoint(); + dataflow::Engine::new(item.tcx, item.body, item.def_id, dead_unwinds, analysis) + .iterate_to_fixpoint(); let cursor = dataflow::ResultsCursor::new(item.body, results); let mut qualifs_in_any_value_of_ty = BitSet::new_empty(item.body.local_decls.len()); @@ -308,7 +309,7 @@ where { type Idx = Local; - const NAME: &'static str = "flow_sensitive_qualif"; + const NAME: &'static str = Q::ANALYSIS_NAME; fn bits_per_block(&self, body: &mir::Body<'tcx>) -> usize { body.local_decls.len() diff --git a/src/librustc_mir/transform/check_consts/validation.rs b/src/librustc_mir/transform/check_consts/validation.rs index e74b22b4352..3045239d7a7 100644 --- a/src/librustc_mir/transform/check_consts/validation.rs +++ b/src/librustc_mir/transform/check_consts/validation.rs @@ -467,8 +467,6 @@ impl Visitor<'tcx> for Validator<'_, 'mir, 'tcx> { self.qualifs.needs_drop.visit_statement(statement, location); self.qualifs.has_mut_interior.visit_statement(statement, location); - debug!("needs_drop: {:?}", self.qualifs.needs_drop.get()); - debug!("has_mut_interior: {:?}", self.qualifs.has_mut_interior.get()); match statement.kind { StatementKind::Assign(..) => { @@ -494,8 +492,6 @@ impl Visitor<'tcx> for Validator<'_, 'mir, 'tcx> { self.qualifs.needs_drop.visit_terminator(terminator, location); self.qualifs.has_mut_interior.visit_terminator(terminator, location); - debug!("needs_drop: {:?}", self.qualifs.needs_drop.get()); - debug!("has_mut_interior: {:?}", self.qualifs.has_mut_interior.get()); self.super_terminator(terminator, location); } |