From 2fb4c4472e4563a52e2dc544e47a01f564b9219e Mon Sep 17 00:00:00 2001 From: Dylan MacKenzie Date: Mon, 11 Nov 2019 11:48:47 -0800 Subject: [PATCH 1/1] Improve graphviz visualization for new framework --- src/librustc_mir/dataflow/generic/graphviz.rs | 518 ++++++++++++++---- src/librustc_span/symbol.rs | 3 + 2 files changed, 405 insertions(+), 116 deletions(-) diff --git a/src/librustc_mir/dataflow/generic/graphviz.rs b/src/librustc_mir/dataflow/generic/graphviz.rs index e843956a7a7..fdf86e7b53f 100644 --- a/src/librustc_mir/dataflow/generic/graphviz.rs +++ b/src/librustc_mir/dataflow/generic/graphviz.rs @@ -1,13 +1,14 @@ +//! A helpful diagram for debugging dataflow problems. + use std::cell::RefCell; -use std::io::{self, Write}; -use std::{ops, str}; +use std::{io, ops, str}; use rustc::mir::{self, BasicBlock, Body, Location}; use rustc_hir::def_id::DefId; use rustc_index::bit_set::{BitSet, HybridBitSet}; -use rustc_index::vec::Idx; +use rustc_index::vec::{Idx, IndexVec}; -use super::{Analysis, Results, ResultsRefCursor}; +use super::{Analysis, GenKillSet, Results, ResultsRefCursor}; use crate::util::graphviz_safe_def_name; pub struct Formatter<'a, 'tcx, A> @@ -25,11 +26,16 @@ impl Formatter<'a, 'tcx, A> where A: Analysis<'tcx>, { - pub fn new(body: &'a Body<'tcx>, def_id: DefId, results: &'a Results<'tcx, A>) -> Self { + pub fn new( + body: &'a Body<'tcx>, + def_id: DefId, + results: &'a Results<'tcx, A>, + state_formatter: &'a mut dyn StateFormatter<'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), + state_formatter, }; Formatter { body, def_id, block_formatter: RefCell::new(block_formatter) } @@ -117,15 +123,21 @@ struct BlockFormatter<'a, 'tcx, A> where A: Analysis<'tcx>, { - prev_state: BitSet, results: ResultsRefCursor<'a, 'a, 'tcx, A>, bg: Background, + state_formatter: &'a mut dyn StateFormatter<'tcx, A>, } impl BlockFormatter<'a, 'tcx, A> where A: Analysis<'tcx>, { + const HEADER_COLOR: &'static str = "#a0a0a0"; + + fn num_state_columns(&self) -> usize { + std::cmp::max(1, self.state_formatter.column_names().len()) + } + fn toggle_background(&mut self) -> Background { let bg = self.bg; self.bg = !bg; @@ -164,196 +176,470 @@ fn write_node_label( r#""#, )?; - // A: Block info - write!( - w, - r#" - - "#, - num_headers = 3, - block_id = block.index(), - )?; - - // B: Column headings - write!( - w, - r#" - - - "#, - fmt = r##"bgcolor="#a0a0a0" sides="tl""##, - )?; + // A + B: Block header + if self.state_formatter.column_names().is_empty() { + self.write_block_header_simple(w, block)?; + } else { + self.write_block_header_with_state_columns(w, block)?; + } // C: Entry state self.bg = Background::Light; self.results.seek_to_block_start(block); - self.write_row_with_curr_state(w, "", "(on entry)")?; - self.prev_state.overwrite(self.results.get()); + self.write_row_with_full_state(w, "", "(on_entry)")?; // 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()); + let statement_str = format!("{:?}", statement); + self.write_row_for_location(w, &i.to_string(), &statement_str, location)?; } // E: Terminator transfer function let terminator = body[block].terminator(); - let location = body.terminator_loc(block); + let terminator_loc = body.terminator_loc(block); + let mut terminator_str = String::new(); + terminator.kind.fmt_head(&mut terminator_str).unwrap(); - 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()); + self.write_row_for_location(w, "T", &terminator_str, terminator_loc)?; // F: Exit state + self.results.seek_after(terminator_loc); 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)")?; + self.write_row_with_full_state(w, "", "(on unwind)")?; + + let num_state_columns = self.num_state_columns(); + self.write_row(w, "", "(on successful return)", |this, w, fmt| { + write!( + w, + r#"") + })?; } else { - self.write_row_with_curr_state(w, "", "(on exit)")?; + self.write_row_with_full_state(w, "", "(on exit)")?; } write!(w, "
bb{block_id}
MIRSTATE
"#, + colspan = num_state_columns, + fmt = fmt, + )?; + + let state_on_unwind = this.results.get().clone(); + this.results.seek_after_assume_call_returns(terminator_loc); + write_diff(w, this.results.analysis(), &state_on_unwind, this.results.get())?; + + write!(w, "
") } - fn write_row_with_curr_state( + fn write_block_header_simple( &mut self, w: &mut impl io::Write, - i: &str, - mir: &str, + block: BasicBlock, ) -> io::Result<()> { - let bg = self.toggle_background(); + // +-------------------------------------------------+ + // A | bb4 | + // +-----------------------------------+-------------+ + // B | MIR | STATE | + // +-+---------------------------------+-------------+ + // | | ... | | - let mut out = Vec::new(); - write!(&mut out, "{{")?; - pretty_print_state_elems(&mut out, self.results.analysis(), self.results.get().iter())?; - write!(&mut out, "}}")?; + // A + write!( + w, + concat!("", r#"bb{block_id}"#, "",), + block_id = block.index(), + )?; + // B write!( w, - r#" - {i} - {mir} - {state} - "#, - fmt = &["sides=\"tl\"", bg.attr()].join(" "), - i = i, - mir = dot::escape_html(mir), - state = dot::escape_html(str::from_utf8(&out).unwrap()), + concat!( + "", + r#"MIR"#, + r#"STATE"#, + "", + ), + fmt = format!("bgcolor=\"{}\" sides=\"tl\"", Self::HEADER_COLOR), ) } - fn write_row_with_curr_diff( + fn write_block_header_with_state_columns( &mut self, w: &mut impl io::Write, - i: &str, - mir: &str, + block: BasicBlock, ) -> io::Result<()> { - let bg = self.toggle_background(); - let analysis = self.results.analysis(); + // +------------------------------------+-------------+ + // A | bb4 | STATE | + // +------------------------------------+------+------+ + // B | MIR | GEN | KILL | + // +-+----------------------------------+------+------+ + // | | ... | | | - let diff = BitSetDiff::compute(&self.prev_state, self.results.get()); + let state_column_names = self.state_formatter.column_names(); - let mut set = Vec::new(); - pretty_print_state_elems(&mut set, analysis, diff.set.iter())?; + // A + write!( + w, + concat!( + "", + r#"bb{block_id}"#, + r#"STATE"#, + "", + ), + fmt = "sides=\"tl\"", + num_state_cols = state_column_names.len(), + block_id = block.index(), + )?; + + // B + let fmt = format!("bgcolor=\"{}\" sides=\"tl\"", Self::HEADER_COLOR); + write!(w, concat!("", r#"MIR"#,), fmt = fmt,)?; - let mut clear = Vec::new(); - pretty_print_state_elems(&mut clear, analysis, diff.clear.iter())?; + for name in state_column_names { + write!(w, "{name}", fmt = fmt, name = name)?; + } + + write!(w, "") + } + + /// Write a row with the given index and MIR, using the function argument to fill in the + /// "STATE" column(s). + fn write_row( + &mut self, + w: &mut W, + i: &str, + mir: &str, + f: impl FnOnce(&mut Self, &mut W, &str) -> io::Result<()>, + ) -> io::Result<()> { + let bg = self.toggle_background(); + let fmt = format!("sides=\"tl\" {}", bg.attr()); write!( w, - r#" - {i} - {mir} - "#, + concat!( + "", + r#"{i}"#, + r#"{mir}"#, + ), i = i, - fmt = &["sides=\"tl\"", bg.attr()].join(" "), + fmt = fmt, mir = dot::escape_html(mir), )?; - if !set.is_empty() { + f(self, w, &fmt)?; + write!(w, "") + } + + fn write_row_with_full_state( + &mut self, + w: &mut impl io::Write, + i: &str, + mir: &str, + ) -> io::Result<()> { + self.write_row(w, i, mir, |this, w, fmt| { + let state = this.results.get(); + let analysis = this.results.analysis(); + write!( w, - r#"+{}"#, - dot::escape_html(str::from_utf8(&set).unwrap()), + r#"{{"#, + colspan = this.num_state_columns(), + fmt = fmt, )?; + pretty_print_state_elems(w, analysis, state.iter(), ",", LIMIT_40_ALIGN_1)?; + write!(w, "}}") + }) + } + + fn write_row_for_location( + &mut self, + w: &mut impl io::Write, + i: &str, + mir: &str, + location: Location, + ) -> io::Result<()> { + self.write_row(w, i, mir, |this, w, fmt| { + this.state_formatter.write_state_for_location(w, fmt, &mut this.results, location) + }) + } +} + +/// Controls what gets printed under the `STATE` header. +pub trait StateFormatter<'tcx, A> +where + A: Analysis<'tcx>, +{ + /// The columns that will get printed under `STATE`. + fn column_names(&self) -> &[&str]; + + fn write_state_for_location( + &mut self, + w: &mut dyn io::Write, + fmt: &str, + results: &mut ResultsRefCursor<'_, '_, 'tcx, A>, + location: Location, + ) -> io::Result<()>; +} + +/// Prints a single column containing the state vector immediately *after* each statement. +pub struct SimpleDiff { + prev_state: BitSet, + prev_loc: Location, +} + +impl SimpleDiff { + #![allow(unused)] + pub fn new(bits_per_block: usize) -> Self { + SimpleDiff { prev_state: BitSet::new_empty(bits_per_block), prev_loc: Location::START } + } +} + +impl StateFormatter<'tcx, A> for SimpleDiff +where + A: Analysis<'tcx>, +{ + fn column_names(&self) -> &[&str] { + &[] + } + + fn write_state_for_location( + &mut self, + mut w: &mut dyn io::Write, + fmt: &str, + results: &mut ResultsRefCursor<'_, '_, 'tcx, A>, + location: Location, + ) -> io::Result<()> { + if location.statement_index == 0 { + results.seek_to_block_start(location.block); + self.prev_state.overwrite(results.get()); + } else { + // Ensure that we are visiting statements in order, so `prev_state` is correct. + assert_eq!(self.prev_loc.successor_within_block(), location); + } + + self.prev_loc = location; + write!(w, r#""#, fmt = fmt)?; + results.seek_before(location); + let curr_state = results.get(); + write_diff(&mut w, results.analysis(), &self.prev_state, curr_state)?; + self.prev_state.overwrite(curr_state); + write!(w, "") + } +} + +/// Prints two state columns, one containing only the "before" effect of each statement and one +/// containing the full effect. +pub struct TwoPhaseDiff { + prev_state: BitSet, + prev_loc: Location, +} + +impl TwoPhaseDiff { + #![allow(unused)] + pub fn new(bits_per_block: usize) -> Self { + TwoPhaseDiff { prev_state: BitSet::new_empty(bits_per_block), prev_loc: Location::START } + } +} + +impl StateFormatter<'tcx, A> for TwoPhaseDiff +where + A: Analysis<'tcx>, +{ + fn column_names(&self) -> &[&str] { + &["ENTRY", " EXIT"] + } + + fn write_state_for_location( + &mut self, + mut w: &mut dyn io::Write, + fmt: &str, + results: &mut ResultsRefCursor<'_, '_, 'tcx, A>, + location: Location, + ) -> io::Result<()> { + if location.statement_index == 0 { + results.seek_to_block_start(location.block); + self.prev_state.overwrite(results.get()); + } else { + // Ensure that we are visiting statements in order, so `prev_state` is correct. + assert_eq!(self.prev_loc.successor_within_block(), location); } - if !set.is_empty() && !clear.is_empty() { - write!(w, " ")?; + self.prev_loc = location; + + // Entry + + write!(w, r#""#, fmt = fmt)?; + results.seek_before(location); + let curr_state = results.get(); + write_diff(&mut w, results.analysis(), &self.prev_state, curr_state)?; + self.prev_state.overwrite(curr_state); + write!(w, "")?; + + // Exit + + write!(w, r#""#, fmt = fmt)?; + results.seek_after(location); + let curr_state = results.get(); + write_diff(&mut w, results.analysis(), &self.prev_state, curr_state)?; + self.prev_state.overwrite(curr_state); + write!(w, "") + } +} + +/// Prints the gen/kill set for the entire block. +pub struct BlockTransferFunc<'a, 'tcx, T: Idx> { + body: &'a mir::Body<'tcx>, + trans_for_block: IndexVec>, +} + +impl BlockTransferFunc<'mir, 'tcx, T> { + #![allow(unused)] + pub fn new( + body: &'mir mir::Body<'tcx>, + trans_for_block: IndexVec>, + ) -> Self { + BlockTransferFunc { body, trans_for_block } + } +} + +impl StateFormatter<'tcx, A> for BlockTransferFunc<'mir, 'tcx, A::Idx> +where + A: Analysis<'tcx>, +{ + fn column_names(&self) -> &[&str] { + &["GEN", "KILL"] + } + + fn write_state_for_location( + &mut self, + mut w: &mut dyn io::Write, + fmt: &str, + results: &mut ResultsRefCursor<'_, '_, 'tcx, A>, + location: Location, + ) -> io::Result<()> { + // Only print a single row. + if location.statement_index != 0 { + return Ok(()); } - if !clear.is_empty() { + let block_trans = &self.trans_for_block[location.block]; + let rowspan = self.body.basic_blocks()[location.block].statements.len(); + + for set in &[&block_trans.gen, &block_trans.kill] { write!( w, - r#"-{}"#, - dot::escape_html(str::from_utf8(&clear).unwrap()), + r#""#, + fmt = fmt, + rowspan = rowspan )?; + + pretty_print_state_elems(&mut w, results.analysis(), set.iter(), "\n", None)?; + write!(w, "")?; } - write!(w, "") + Ok(()) } } -/// The operations required to transform one `BitSet` into another. -struct BitSetDiff { - set: HybridBitSet, - clear: HybridBitSet, -} +/// Writes two lines, one containing the added bits and one the removed bits. +fn write_diff>( + w: &mut impl io::Write, + analysis: &A, + from: &BitSet, + to: &BitSet, +) -> io::Result<()> { + 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: Implement a lazy iterator over the symmetric difference of two bitsets. + for i in (0..len).map(|i| A::Idx::new(i)) { + match (from.contains(i), to.contains(i)) { + (false, true) => set.insert(i), + (true, false) => clear.insert(i), + _ => continue, + }; + } -impl BitSetDiff { - fn compute(from: &BitSet, to: &BitSet) -> 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, - }; - } + if !set.is_empty() { + write!(w, r#"+"#)?; + pretty_print_state_elems(w, analysis, set.iter(), ",", LIMIT_40_ALIGN_1)?; + write!(w, r#""#)?; + } - BitSetDiff { set, clear } + if !set.is_empty() && !clear.is_empty() { + write!(w, "
")?; } + + if !clear.is_empty() { + write!(w, r#"-"#)?; + pretty_print_state_elems(w, analysis, clear.iter(), ",", LIMIT_40_ALIGN_1)?; + write!(w, r#""#)?; + } + + Ok(()) } -/// Formats each `elem` using the pretty printer provided by `analysis` into a comma-separated -/// list. +/// Line break policy that breaks at 40 characters and starts the next line with a single space. +const LIMIT_40_ALIGN_1: Option = Some(LineBreak { sequence: "
", limit: 40 }); + +struct LineBreak { + sequence: &'static str, + limit: usize, +} + +/// Formats each `elem` using the pretty printer provided by `analysis` into a list with the given +/// separator (`sep`). +/// +/// Optionally, it will break lines using the given character sequence (usually `
`) and +/// character limit. fn pretty_print_state_elems( w: &mut impl io::Write, analysis: &A, elems: impl Iterator, -) -> io::Result<()> + sep: &str, + line_break: Option, +) -> io::Result where A: Analysis<'tcx>, { + let sep_width = sep.chars().count(); + + let mut buf = Vec::new(); + let mut first = true; + let mut curr_line_width = 0; + let mut line_break_inserted = false; + for idx in elems { if first { first = false; } else { - write!(w, ",")?; + write!(w, "{}", sep)?; + curr_line_width += sep_width; + } + + buf.clear(); + analysis.pretty_print_idx(&mut buf, idx)?; + let idx_str = + str::from_utf8(&buf).expect("Output of `pretty_print_idx` must be valid UTF-8"); + let escaped = dot::escape_html(idx_str); + let escaped_width = escaped.chars().count(); + + if let Some(line_break) = &line_break { + if curr_line_width + sep_width + escaped_width > line_break.limit { + write!(w, "{}", line_break.sequence)?; + line_break_inserted = true; + curr_line_width = 0; + } } - analysis.pretty_print_idx(w, idx)?; + write!(w, "{}", escaped)?; + curr_line_width += escaped_width; } - Ok(()) + Ok(line_break_inserted) } /// The background color used for zebra-striping the table. diff --git a/src/librustc_span/symbol.rs b/src/librustc_span/symbol.rs index a8b2db300a4..138388d8719 100644 --- a/src/librustc_span/symbol.rs +++ b/src/librustc_span/symbol.rs @@ -167,6 +167,7 @@ bindings_after_at, block, bool, + borrowck_graphviz_format, borrowck_graphviz_postflow, borrowck_graphviz_preflow, box_patterns, @@ -337,6 +338,7 @@ FxHashSet, FxHashMap, gen_future, + gen_kill, generators, generic_associated_types, generic_param_attrs, @@ -735,6 +737,7 @@ try_trait, tt, tuple_indexing, + two_phase, Ty, ty, type_alias_impl_trait, -- 2.44.0