compiler/rustc_mir/src/dataflow/framework/graphviz.rs

   1 //! A helpful diagram for debugging dataflow problems.
   2
   3 use std::borrow::Cow;
   4 use std::{io, ops, str};
   5
   6 use regex::Regex;
   7 use rustc_graphviz as dot;
   8 use rustc_hir::def_id::DefId;
   9 use rustc_middle::mir::{self, BasicBlock, Body, Location};
  10
  11 use super::fmt::{DebugDiffWithAdapter, DebugWithAdapter, DebugWithContext};
  12 use super::{Analysis, Direction, Results, ResultsRefCursor, ResultsVisitor};
  13 use crate::util::graphviz_safe_def_name;
  14
  15 #[derive(Clone, Copy, Debug, PartialEq, Eq)]
  16 pub enum OutputStyle {
  17     AfterOnly,
  18     BeforeAndAfter,
  19 }
  20
  21 impl OutputStyle {
  22     fn num_state_columns(&self) -> usize {
  23         match self {
  24             Self::AfterOnly => 1,
  25             Self::BeforeAndAfter => 2,
  26         }
  27     }
  28 }
  29
  30 pub struct Formatter<'a, 'tcx, A>
  31 where
  32     A: Analysis<'tcx>,
  33 {
  34     body: &'a Body<'tcx>,
  35     def_id: DefId,
  36     results: &'a Results<'tcx, A>,
  37     style: OutputStyle,
  38 }
  39
  40 impl<A> Formatter<'a, 'tcx, A>
  41 where
  42     A: Analysis<'tcx>,
  43 {
  44     pub fn new(
  45         body: &'a Body<'tcx>,
  46         def_id: DefId,
  47         results: &'a Results<'tcx, A>,
  48         style: OutputStyle,
  49     ) -> Self {
  50         Formatter { body, def_id, results, style }
  51     }
  52 }
  53
  54 /// A pair of a basic block and an index into that basic blocks `successors`.
  55 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
  56 pub struct CfgEdge {
  57     source: BasicBlock,
  58     index: usize,
  59 }
  60
  61 fn dataflow_successors(body: &Body<'tcx>, bb: BasicBlock) -> Vec<CfgEdge> {
  62     body[bb]
  63         .terminator()
  64         .successors()
  65         .enumerate()
  66         .map(|(index, _)| CfgEdge { source: bb, index })
  67         .collect()
  68 }
  69
  70 impl<A> dot::Labeller<'_> for Formatter<'a, 'tcx, A>
  71 where
  72     A: Analysis<'tcx>,
  73     A::Domain: DebugWithContext<A>,
  74 {
  75     type Node = BasicBlock;
  76     type Edge = CfgEdge;
  77
  78     fn graph_id(&self) -> dot::Id<'_> {
  79         let name = graphviz_safe_def_name(self.def_id);
  80         dot::Id::new(format!("graph_for_def_id_{}", name)).unwrap()
  81     }
  82
  83     fn node_id(&self, n: &Self::Node) -> dot::Id<'_> {
  84         dot::Id::new(format!("bb_{}", n.index())).unwrap()
  85     }
  86
  87     fn node_label(&self, block: &Self::Node) -> dot::LabelText<'_> {
  88         let mut label = Vec::new();
  89         let mut fmt = BlockFormatter {
  90             results: ResultsRefCursor::new(self.body, self.results),
  91             style: self.style,
  92             bg: Background::Light,
  93         };
  94
  95         fmt.write_node_label(&mut label, self.body, *block).unwrap();
  96         dot::LabelText::html(String::from_utf8(label).unwrap())
  97     }
  98
  99     fn node_shape(&self, _n: &Self::Node) -> Option<dot::LabelText<'_>> {
 100         Some(dot::LabelText::label("none"))
 101     }
 102
 103     fn edge_label(&self, e: &Self::Edge) -> dot::LabelText<'_> {
 104         let label = &self.body[e.source].terminator().kind.fmt_successor_labels()[e.index];
 105         dot::LabelText::label(label.clone())
 106     }
 107 }
 108
 109 impl<A> dot::GraphWalk<'a> for Formatter<'a, 'tcx, A>
 110 where
 111     A: Analysis<'tcx>,
 112 {
 113     type Node = BasicBlock;
 114     type Edge = CfgEdge;
 115
 116     fn nodes(&self) -> dot::Nodes<'_, Self::Node> {
 117         self.body.basic_blocks().indices().collect::<Vec<_>>().into()
 118     }
 119
 120     fn edges(&self) -> dot::Edges<'_, Self::Edge> {
 121         self.body
 122             .basic_blocks()
 123             .indices()
 124             .flat_map(|bb| dataflow_successors(self.body, bb))
 125             .collect::<Vec<_>>()
 126             .into()
 127     }
 128
 129     fn source(&self, edge: &Self::Edge) -> Self::Node {
 130         edge.source
 131     }
 132
 133     fn target(&self, edge: &Self::Edge) -> Self::Node {
 134         self.body[edge.source].terminator().successors().nth(edge.index).copied().unwrap()
 135     }
 136 }
 137
 138 struct BlockFormatter<'a, 'tcx, A>
 139 where
 140     A: Analysis<'tcx>,
 141 {
 142     results: ResultsRefCursor<'a, 'a, 'tcx, A>,
 143     bg: Background,
 144     style: OutputStyle,
 145 }
 146
 147 impl<A> BlockFormatter<'a, 'tcx, A>
 148 where
 149     A: Analysis<'tcx>,
 150     A::Domain: DebugWithContext<A>,
 151 {
 152     const HEADER_COLOR: &'static str = "#a0a0a0";
 153
 154     fn toggle_background(&mut self) -> Background {
 155         let bg = self.bg;
 156         self.bg = !bg;
 157         bg
 158     }
 159
 160     fn write_node_label(
 161         &mut self,
 162         w: &mut impl io::Write,
 163         body: &'a Body<'tcx>,
 164         block: BasicBlock,
 165     ) -> io::Result<()> {
 166         //   Sample output:
 167         //   +-+-----------------------------------------------+
 168         // A |                      bb4                        |
 169         //   +-+----------------------------------+------------+
 170         // B |                MIR                 |   STATE    |
 171         //   +-+----------------------------------+------------+
 172         // C | | (on entry)                       | {_0,_2,_3} |
 173         //   +-+----------------------------------+------------+
 174         // D |0| StorageLive(_7)                  |            |
 175         //   +-+----------------------------------+------------+
 176         //   |1| StorageLive(_8)                  |            |
 177         //   +-+----------------------------------+------------+
 178         //   |2| _8 = &mut _1                     | +_8        |
 179         //   +-+----------------------------------+------------+
 180         // E |T| _4 = const Foo::twiddle(move _2) | -_2        |
 181         //   +-+----------------------------------+------------+
 182         // F | | (on unwind)                      | {_0,_3,_8} |
 183         //   +-+----------------------------------+------------+
 184         //   | | (on successful return)           | +_4        |
 185         //   +-+----------------------------------+------------+
 186
 187         // N.B., Some attributes (`align`, `balign`) are repeated on parent elements and their
 188         // children. This is because `xdot` seemed to have a hard time correctly propagating
 189         // attributes. Make sure to test the output before trying to remove the redundancy.
 190         // Notably, `align` was found to have no effect when applied only to <table>.
 191
 192         let table_fmt = concat!(
 193             " border=\"1\"",
 194             " cellborder=\"1\"",
 195             " cellspacing=\"0\"",
 196             " cellpadding=\"3\"",
 197             " sides=\"rb\"",
 198         );
 199         write!(w, r#"<table{fmt}>"#, fmt = table_fmt)?;
 200
 201         // A + B: Block header
 202         match self.style {
 203             OutputStyle::AfterOnly => self.write_block_header_simple(w, block)?,
 204             OutputStyle::BeforeAndAfter => {
 205                 self.write_block_header_with_state_columns(w, block, &["BEFORE", "AFTER"])?
 206             }
 207         }
 208
 209         // C: State at start of block
 210         self.bg = Background::Light;
 211         self.results.seek_to_block_start(block);
 212         let block_start_state = self.results.get().clone();
 213         self.write_row_with_full_state(w, "", "(on start)")?;
 214
 215         // D + E: Statement and terminator transfer functions
 216         self.write_statements_and_terminator(w, body, block)?;
 217
 218         // F: State at end of block
 219
 220         let terminator = body[block].terminator();
 221
 222         // Write the full dataflow state immediately after the terminator if it differs from the
 223         // state at block entry.
 224         self.results.seek_to_block_end(block);
 225         if self.results.get() != &block_start_state || A::Direction::is_backward() {
 226             let after_terminator_name = match terminator.kind {
 227                 mir::TerminatorKind::Call { destination: Some(_), .. } => "(on unwind)",
 228                 _ => "(on end)",
 229             };
 230
 231             self.write_row_with_full_state(w, "", after_terminator_name)?;
 232         }
 233
 234         // Write any changes caused by terminator-specific effects.
 235         //
 236         // FIXME: These should really be printed as part of each outgoing edge rather than the node
 237         // for the basic block itself. That way, we could display terminator-specific effects for
 238         // backward dataflow analyses as well as effects for `SwitchInt` terminators.
 239         match terminator.kind {
 240             mir::TerminatorKind::Call {
 241                 destination: Some((return_place, _)),
 242                 ref func,
 243                 ref args,
 244                 ..
 245             } => {
 246                 self.write_row(w, "", "(on successful return)", |this, w, fmt| {
 247                     let state_on_unwind = this.results.get().clone();
 248                     this.results.apply_custom_effect(|analysis, state| {
 249                         analysis.apply_call_return_effect(state, block, func, args, return_place);
 250                     });
 251
 252                     write!(
 253                         w,
 254                         r#"<td balign="left" colspan="{colspan}" {fmt} align="left">{diff}</td>"#,
 255                         colspan = this.style.num_state_columns(),
 256                         fmt = fmt,
 257                         diff = diff_pretty(
 258                             this.results.get(),
 259                             &state_on_unwind,
 260                             this.results.analysis()
 261                         ),
 262                     )
 263                 })?;
 264             }
 265
 266             mir::TerminatorKind::Yield { resume, resume_arg, .. } => {
 267                 self.write_row(w, "", "(on yield resume)", |this, w, fmt| {
 268                     let state_on_generator_drop = this.results.get().clone();
 269                     this.results.apply_custom_effect(|analysis, state| {
 270                         analysis.apply_yield_resume_effect(state, resume, resume_arg);
 271                     });
 272
 273                     write!(
 274                         w,
 275                         r#"<td balign="left" colspan="{colspan}" {fmt} align="left">{diff}</td>"#,
 276                         colspan = this.style.num_state_columns(),
 277                         fmt = fmt,
 278                         diff = diff_pretty(
 279                             this.results.get(),
 280                             &state_on_generator_drop,
 281                             this.results.analysis()
 282                         ),
 283                     )
 284                 })?;
 285             }
 286
 287             _ => {}
 288         };
 289
 290         write!(w, "</table>")
 291     }
 292
 293     fn write_block_header_simple(
 294         &mut self,
 295         w: &mut impl io::Write,
 296         block: BasicBlock,
 297     ) -> io::Result<()> {
 298         //   +-------------------------------------------------+
 299         // A |                      bb4                        |
 300         //   +-----------------------------------+-------------+
 301         // B |                MIR                |    STATE    |
 302         //   +-+---------------------------------+-------------+
 303         //   | |              ...                |             |
 304
 305         // A
 306         write!(
 307             w,
 308             concat!("<tr>", r#"<td colspan="3" sides="tl">bb{block_id}</td>"#, "</tr>",),
 309             block_id = block.index(),
 310         )?;
 311
 312         // B
 313         write!(
 314             w,
 315             concat!(
 316                 "<tr>",
 317                 r#"<td colspan="2" {fmt}>MIR</td>"#,
 318                 r#"<td {fmt}>STATE</td>"#,
 319                 "</tr>",
 320             ),
 321             fmt = format!("bgcolor=\"{}\" sides=\"tl\"", Self::HEADER_COLOR),
 322         )
 323     }
 324
 325     fn write_block_header_with_state_columns(
 326         &mut self,
 327         w: &mut impl io::Write,
 328         block: BasicBlock,
 329         state_column_names: &[&str],
 330     ) -> io::Result<()> {
 331         //   +------------------------------------+-------------+
 332         // A |                bb4                 |    STATE    |
 333         //   +------------------------------------+------+------+
 334         // B |                MIR                 |  GEN | KILL |
 335         //   +-+----------------------------------+------+------+
 336         //   | |              ...                 |      |      |
 337
 338         // A
 339         write!(
 340             w,
 341             concat!(
 342                 "<tr>",
 343                 r#"<td {fmt} colspan="2">bb{block_id}</td>"#,
 344                 r#"<td {fmt} colspan="{num_state_cols}">STATE</td>"#,
 345                 "</tr>",
 346             ),
 347             fmt = "sides=\"tl\"",
 348             num_state_cols = state_column_names.len(),
 349             block_id = block.index(),
 350         )?;
 351
 352         // B
 353         let fmt = format!("bgcolor=\"{}\" sides=\"tl\"", Self::HEADER_COLOR);
 354         write!(w, concat!("<tr>", r#"<td colspan="2" {fmt}>MIR</td>"#,), fmt = fmt,)?;
 355
 356         for name in state_column_names {
 357             write!(w, "<td {fmt}>{name}</td>", fmt = fmt, name = name)?;
 358         }
 359
 360         write!(w, "</tr>")
 361     }
 362
 363     fn write_statements_and_terminator(
 364         &mut self,
 365         w: &mut impl io::Write,
 366         body: &'a Body<'tcx>,
 367         block: BasicBlock,
 368     ) -> io::Result<()> {
 369         let diffs = StateDiffCollector::run(body, block, self.results.results(), self.style);
 370
 371         let mut befores = diffs.before.map(|v| v.into_iter());
 372         let mut afters = diffs.after.into_iter();
 373
 374         let next_in_dataflow_order = |it: &mut std::vec::IntoIter<_>| {
 375             if A::Direction::is_forward() { it.next().unwrap() } else { it.next_back().unwrap() }
 376         };
 377
 378         for (i, statement) in body[block].statements.iter().enumerate() {
 379             let statement_str = format!("{:?}", statement);
 380             let index_str = format!("{}", i);
 381
 382             let after = next_in_dataflow_order(&mut afters);
 383             let before = befores.as_mut().map(next_in_dataflow_order);
 384
 385             self.write_row(w, &index_str, &statement_str, |_this, w, fmt| {
 386                 if let Some(before) = before {
 387                     write!(w, r#"<td {fmt} align="left">{diff}</td>"#, fmt = fmt, diff = before)?;
 388                 }
 389
 390                 write!(w, r#"<td {fmt} align="left">{diff}</td>"#, fmt = fmt, diff = after)
 391             })?;
 392         }
 393
 394         let after = next_in_dataflow_order(&mut afters);
 395         let before = befores.as_mut().map(next_in_dataflow_order);
 396
 397         assert!(afters.is_empty());
 398         assert!(befores.as_ref().map_or(true, ExactSizeIterator::is_empty));
 399
 400         let terminator = body[block].terminator();
 401         let mut terminator_str = String::new();
 402         terminator.kind.fmt_head(&mut terminator_str).unwrap();
 403
 404         self.write_row(w, "T", &terminator_str, |_this, w, fmt| {
 405             if let Some(before) = before {
 406                 write!(w, r#"<td {fmt} align="left">{diff}</td>"#, fmt = fmt, diff = before)?;
 407             }
 408
 409             write!(w, r#"<td {fmt} align="left">{diff}</td>"#, fmt = fmt, diff = after)
 410         })
 411     }
 412
 413     /// Write a row with the given index and MIR, using the function argument to fill in the
 414     /// "STATE" column(s).
 415     fn write_row<W: io::Write>(
 416         &mut self,
 417         w: &mut W,
 418         i: &str,
 419         mir: &str,
 420         f: impl FnOnce(&mut Self, &mut W, &str) -> io::Result<()>,
 421     ) -> io::Result<()> {
 422         let bg = self.toggle_background();
 423         let valign = if mir.starts_with("(on ") && mir != "(on entry)" { "bottom" } else { "top" };
 424
 425         let fmt = format!("valign=\"{}\" sides=\"tl\" {}", valign, bg.attr());
 426
 427         write!(
 428             w,
 429             concat!(
 430                 "<tr>",
 431                 r#"<td {fmt} align="right">{i}</td>"#,
 432                 r#"<td {fmt} align="left">{mir}</td>"#,
 433             ),
 434             i = i,
 435             fmt = fmt,
 436             mir = dot::escape_html(mir),
 437         )?;
 438
 439         f(self, w, &fmt)?;
 440         write!(w, "</tr>")
 441     }
 442
 443     fn write_row_with_full_state(
 444         &mut self,
 445         w: &mut impl io::Write,
 446         i: &str,
 447         mir: &str,
 448     ) -> io::Result<()> {
 449         self.write_row(w, i, mir, |this, w, fmt| {
 450             let state = this.results.get();
 451             let analysis = this.results.analysis();
 452
 453             // FIXME: The full state vector can be quite long. It would be nice to split on commas
 454             // and use some text wrapping algorithm.
 455             write!(
 456                 w,
 457                 r#"<td colspan="{colspan}" {fmt} align="left">{state}</td>"#,
 458                 colspan = this.style.num_state_columns(),
 459                 fmt = fmt,
 460                 state = format!("{:?}", DebugWithAdapter { this: state, ctxt: analysis }),
 461             )
 462         })
 463     }
 464 }
 465
 466 struct StateDiffCollector<'a, 'tcx, A>
 467 where
 468     A: Analysis<'tcx>,
 469 {
 470     analysis: &'a A,
 471     prev_state: A::Domain,
 472     before: Option<Vec<String>>,
 473     after: Vec<String>,
 474 }
 475
 476 impl<A> StateDiffCollector<'a, 'tcx, A>
 477 where
 478     A: Analysis<'tcx>,
 479     A::Domain: DebugWithContext<A>,
 480 {
 481     fn run(
 482         body: &'a mir::Body<'tcx>,
 483         block: BasicBlock,
 484         results: &'a Results<'tcx, A>,
 485         style: OutputStyle,
 486     ) -> Self {
 487         let mut collector = StateDiffCollector {
 488             analysis: &results.analysis,
 489             prev_state: results.analysis.bottom_value(body),
 490             after: vec![],
 491             before: (style == OutputStyle::BeforeAndAfter).then_some(vec![]),
 492         };
 493
 494         results.visit_with(body, std::iter::once(block), &mut collector);
 495         collector
 496     }
 497 }
 498
 499 impl<A> ResultsVisitor<'a, 'tcx> for StateDiffCollector<'a, 'tcx, A>
 500 where
 501     A: Analysis<'tcx>,
 502     A::Domain: DebugWithContext<A>,
 503 {
 504     type FlowState = A::Domain;
 505
 506     fn visit_block_start(
 507         &mut self,
 508         state: &Self::FlowState,
 509         _block_data: &'mir mir::BasicBlockData<'tcx>,
 510         _block: BasicBlock,
 511     ) {
 512         if A::Direction::is_forward() {
 513             self.prev_state.clone_from(state);
 514         }
 515     }
 516
 517     fn visit_block_end(
 518         &mut self,
 519         state: &Self::FlowState,
 520         _block_data: &'mir mir::BasicBlockData<'tcx>,
 521         _block: BasicBlock,
 522     ) {
 523         if A::Direction::is_backward() {
 524             self.prev_state.clone_from(state);
 525         }
 526     }
 527
 528     fn visit_statement_before_primary_effect(
 529         &mut self,
 530         state: &Self::FlowState,
 531         _statement: &'mir mir::Statement<'tcx>,
 532         _location: Location,
 533     ) {
 534         if let Some(before) = self.before.as_mut() {
 535             before.push(diff_pretty(state, &self.prev_state, self.analysis));
 536             self.prev_state.clone_from(state)
 537         }
 538     }
 539
 540     fn visit_statement_after_primary_effect(
 541         &mut self,
 542         state: &Self::FlowState,
 543         _statement: &'mir mir::Statement<'tcx>,
 544         _location: Location,
 545     ) {
 546         self.after.push(diff_pretty(state, &self.prev_state, self.analysis));
 547         self.prev_state.clone_from(state)
 548     }
 549
 550     fn visit_terminator_before_primary_effect(
 551         &mut self,
 552         state: &Self::FlowState,
 553         _terminator: &'mir mir::Terminator<'tcx>,
 554         _location: Location,
 555     ) {
 556         if let Some(before) = self.before.as_mut() {
 557             before.push(diff_pretty(state, &self.prev_state, self.analysis));
 558             self.prev_state.clone_from(state)
 559         }
 560     }
 561
 562     fn visit_terminator_after_primary_effect(
 563         &mut self,
 564         state: &Self::FlowState,
 565         _terminator: &'mir mir::Terminator<'tcx>,
 566         _location: Location,
 567     ) {
 568         self.after.push(diff_pretty(state, &self.prev_state, self.analysis));
 569         self.prev_state.clone_from(state)
 570     }
 571 }
 572
 573 fn diff_pretty<T, C>(new: T, old: T, ctxt: &C) -> String
 574 where
 575     T: DebugWithContext<C>,
 576 {
 577     if new == old {
 578         return String::new();
 579     }
 580
 581     let re = Regex::new("\t?\u{001f}([+-])").unwrap();
 582
 583     let raw_diff = format!("{:#?}", DebugDiffWithAdapter { new, old, ctxt });
 584
 585     // Replace newlines in the `Debug` output with `<br/>`
 586     let raw_diff = raw_diff.replace('\n', r#"<br align="left"/>"#);
 587
 588     let mut inside_font_tag = false;
 589     let html_diff = re.replace_all(&raw_diff, |captures: &regex::Captures<'_>| {
 590         let mut ret = String::new();
 591         if inside_font_tag {
 592             ret.push_str(r#"</font>"#);
 593         }
 594
 595         let tag = match &captures[1] {
 596             "+" => r#"<font color="darkgreen">+"#,
 597             "-" => r#"<font color="red">-"#,
 598             _ => unreachable!(),
 599         };
 600
 601         inside_font_tag = true;
 602         ret.push_str(tag);
 603         ret
 604     });
 605
 606     let mut html_diff = match html_diff {
 607         Cow::Borrowed(_) => return raw_diff,
 608         Cow::Owned(s) => s,
 609     };
 610
 611     if inside_font_tag {
 612         html_diff.push_str("</font>");
 613     }
 614
 615     html_diff
 616 }
 617
 618 /// The background color used for zebra-striping the table.
 619 #[derive(Clone, Copy)]
 620 enum Background {
 621     Light,
 622     Dark,
 623 }
 624
 625 impl Background {
 626     fn attr(self) -> &'static str {
 627         match self {
 628             Self::Dark => "bgcolor=\"#f0f0f0\"",
 629             Self::Light => "",
 630         }
 631     }
 632 }
 633
 634 impl ops::Not for Background {
 635     type Output = Self;
 636
 637     fn not(self) -> Self {
 638         match self {
 639             Self::Light => Self::Dark,
 640             Self::Dark => Self::Light,
 641         }
 642     }
 643 }