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