compiler/rustc_mir_dataflow/src/framework/graphviz.rs

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