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_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     results: &'a Results<'tcx, A>,
  36     style: OutputStyle,
  37 }
  38
  39 impl<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<'tcx>, 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<A> dot::Labeller<'_> for Formatter<'a, '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> 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).copied().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> 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{fmt}>"#, fmt = 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 { destination: 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 {
 235                 destination: Some((return_place, _)),
 236                 ref func,
 237                 ref args,
 238                 ..
 239             } => {
 240                 self.write_row(w, "", "(on successful return)", |this, w, fmt| {
 241                     let state_on_unwind = this.results.get().clone();
 242                     this.results.apply_custom_effect(|analysis, state| {
 243                         analysis.apply_call_return_effect(state, block, func, args, return_place);
 244                     });
 245
 246                     write!(
 247                         w,
 248                         r#"<td balign="left" colspan="{colspan}" {fmt} align="left">{diff}</td>"#,
 249                         colspan = this.style.num_state_columns(),
 250                         fmt = fmt,
 251                         diff = diff_pretty(
 252                             this.results.get(),
 253                             &state_on_unwind,
 254                             this.results.analysis()
 255                         ),
 256                     )
 257                 })?;
 258             }
 259
 260             mir::TerminatorKind::Yield { resume, resume_arg, .. } => {
 261                 self.write_row(w, "", "(on yield resume)", |this, w, fmt| {
 262                     let state_on_generator_drop = this.results.get().clone();
 263                     this.results.apply_custom_effect(|analysis, state| {
 264                         analysis.apply_yield_resume_effect(state, resume, resume_arg);
 265                     });
 266
 267                     write!(
 268                         w,
 269                         r#"<td balign="left" colspan="{colspan}" {fmt} align="left">{diff}</td>"#,
 270                         colspan = this.style.num_state_columns(),
 271                         fmt = fmt,
 272                         diff = diff_pretty(
 273                             this.results.get(),
 274                             &state_on_generator_drop,
 275                             this.results.analysis()
 276                         ),
 277                     )
 278                 })?;
 279             }
 280
 281             _ => {}
 282         };
 283
 284         write!(w, "</table>")
 285     }
 286
 287     fn write_block_header_simple(
 288         &mut self,
 289         w: &mut impl io::Write,
 290         block: BasicBlock,
 291     ) -> io::Result<()> {
 292         //   +-------------------------------------------------+
 293         // A |                      bb4                        |
 294         //   +-----------------------------------+-------------+
 295         // B |                MIR                |    STATE    |
 296         //   +-+---------------------------------+-------------+
 297         //   | |              ...                |             |
 298
 299         // A
 300         write!(
 301             w,
 302             concat!("<tr>", r#"<td colspan="3" sides="tl">bb{block_id}</td>"#, "</tr>",),
 303             block_id = block.index(),
 304         )?;
 305
 306         // B
 307         write!(
 308             w,
 309             concat!(
 310                 "<tr>",
 311                 r#"<td colspan="2" {fmt}>MIR</td>"#,
 312                 r#"<td {fmt}>STATE</td>"#,
 313                 "</tr>",
 314             ),
 315             fmt = format!("bgcolor=\"{}\" sides=\"tl\"", Self::HEADER_COLOR),
 316         )
 317     }
 318
 319     fn write_block_header_with_state_columns(
 320         &mut self,
 321         w: &mut impl io::Write,
 322         block: BasicBlock,
 323         state_column_names: &[&str],
 324     ) -> io::Result<()> {
 325         //   +------------------------------------+-------------+
 326         // A |                bb4                 |    STATE    |
 327         //   +------------------------------------+------+------+
 328         // B |                MIR                 |  GEN | KILL |
 329         //   +-+----------------------------------+------+------+
 330         //   | |              ...                 |      |      |
 331
 332         // A
 333         write!(
 334             w,
 335             concat!(
 336                 "<tr>",
 337                 r#"<td {fmt} colspan="2">bb{block_id}</td>"#,
 338                 r#"<td {fmt} colspan="{num_state_cols}">STATE</td>"#,
 339                 "</tr>",
 340             ),
 341             fmt = "sides=\"tl\"",
 342             num_state_cols = state_column_names.len(),
 343             block_id = block.index(),
 344         )?;
 345
 346         // B
 347         let fmt = format!("bgcolor=\"{}\" sides=\"tl\"", Self::HEADER_COLOR);
 348         write!(w, concat!("<tr>", r#"<td colspan="2" {fmt}>MIR</td>"#,), fmt = fmt,)?;
 349
 350         for name in state_column_names {
 351             write!(w, "<td {fmt}>{name}</td>", fmt = fmt, name = name)?;
 352         }
 353
 354         write!(w, "</tr>")
 355     }
 356
 357     fn write_statements_and_terminator(
 358         &mut self,
 359         w: &mut impl io::Write,
 360         body: &'a Body<'tcx>,
 361         block: BasicBlock,
 362     ) -> io::Result<()> {
 363         let diffs = StateDiffCollector::run(body, block, self.results.results(), self.style);
 364
 365         let mut befores = diffs.before.map(|v| v.into_iter());
 366         let mut afters = diffs.after.into_iter();
 367
 368         let next_in_dataflow_order = |it: &mut std::vec::IntoIter<_>| {
 369             if A::Direction::is_forward() { it.next().unwrap() } else { it.next_back().unwrap() }
 370         };
 371
 372         for (i, statement) in body[block].statements.iter().enumerate() {
 373             let statement_str = format!("{:?}", statement);
 374             let index_str = format!("{}", i);
 375
 376             let after = next_in_dataflow_order(&mut afters);
 377             let before = befores.as_mut().map(next_in_dataflow_order);
 378
 379             self.write_row(w, &index_str, &statement_str, |_this, w, fmt| {
 380                 if let Some(before) = before {
 381                     write!(w, r#"<td {fmt} align="left">{diff}</td>"#, fmt = fmt, diff = before)?;
 382                 }
 383
 384                 write!(w, r#"<td {fmt} align="left">{diff}</td>"#, fmt = fmt, diff = after)
 385             })?;
 386         }
 387
 388         let after = next_in_dataflow_order(&mut afters);
 389         let before = befores.as_mut().map(next_in_dataflow_order);
 390
 391         assert!(afters.is_empty());
 392         assert!(befores.as_ref().map_or(true, ExactSizeIterator::is_empty));
 393
 394         let terminator = body[block].terminator();
 395         let mut terminator_str = String::new();
 396         terminator.kind.fmt_head(&mut terminator_str).unwrap();
 397
 398         self.write_row(w, "T", &terminator_str, |_this, w, fmt| {
 399             if let Some(before) = before {
 400                 write!(w, r#"<td {fmt} align="left">{diff}</td>"#, fmt = fmt, diff = before)?;
 401             }
 402
 403             write!(w, r#"<td {fmt} align="left">{diff}</td>"#, fmt = fmt, diff = after)
 404         })
 405     }
 406
 407     /// Write a row with the given index and MIR, using the function argument to fill in the
 408     /// "STATE" column(s).
 409     fn write_row<W: io::Write>(
 410         &mut self,
 411         w: &mut W,
 412         i: &str,
 413         mir: &str,
 414         f: impl FnOnce(&mut Self, &mut W, &str) -> io::Result<()>,
 415     ) -> io::Result<()> {
 416         let bg = self.toggle_background();
 417         let valign = if mir.starts_with("(on ") && mir != "(on entry)" { "bottom" } else { "top" };
 418
 419         let fmt = format!("valign=\"{}\" sides=\"tl\" {}", valign, bg.attr());
 420
 421         write!(
 422             w,
 423             concat!(
 424                 "<tr>",
 425                 r#"<td {fmt} align="right">{i}</td>"#,
 426                 r#"<td {fmt} align="left">{mir}</td>"#,
 427             ),
 428             i = i,
 429             fmt = fmt,
 430             mir = dot::escape_html(mir),
 431         )?;
 432
 433         f(self, w, &fmt)?;
 434         write!(w, "</tr>")
 435     }
 436
 437     fn write_row_with_full_state(
 438         &mut self,
 439         w: &mut impl io::Write,
 440         i: &str,
 441         mir: &str,
 442     ) -> io::Result<()> {
 443         self.write_row(w, i, mir, |this, w, fmt| {
 444             let state = this.results.get();
 445             let analysis = this.results.analysis();
 446
 447             // FIXME: The full state vector can be quite long. It would be nice to split on commas
 448             // and use some text wrapping algorithm.
 449             write!(
 450                 w,
 451                 r#"<td colspan="{colspan}" {fmt} align="left">{state}</td>"#,
 452                 colspan = this.style.num_state_columns(),
 453                 fmt = fmt,
 454                 state = format!("{:?}", DebugWithAdapter { this: state, ctxt: analysis }),
 455             )
 456         })
 457     }
 458 }
 459
 460 struct StateDiffCollector<'a, 'tcx, A>
 461 where
 462     A: Analysis<'tcx>,
 463 {
 464     analysis: &'a A,
 465     prev_state: A::Domain,
 466     before: Option<Vec<String>>,
 467     after: Vec<String>,
 468 }
 469
 470 impl<A> StateDiffCollector<'a, 'tcx, A>
 471 where
 472     A: Analysis<'tcx>,
 473     A::Domain: DebugWithContext<A>,
 474 {
 475     fn run(
 476         body: &'a mir::Body<'tcx>,
 477         block: BasicBlock,
 478         results: &'a Results<'tcx, A>,
 479         style: OutputStyle,
 480     ) -> Self {
 481         let mut collector = StateDiffCollector {
 482             analysis: &results.analysis,
 483             prev_state: results.analysis.bottom_value(body),
 484             after: vec![],
 485             before: (style == OutputStyle::BeforeAndAfter).then_some(vec![]),
 486         };
 487
 488         results.visit_with(body, std::iter::once(block), &mut collector);
 489         collector
 490     }
 491 }
 492
 493 impl<A> ResultsVisitor<'a, 'tcx> for StateDiffCollector<'a, 'tcx, A>
 494 where
 495     A: Analysis<'tcx>,
 496     A::Domain: DebugWithContext<A>,
 497 {
 498     type FlowState = A::Domain;
 499
 500     fn visit_block_start(
 501         &mut self,
 502         state: &Self::FlowState,
 503         _block_data: &'mir mir::BasicBlockData<'tcx>,
 504         _block: BasicBlock,
 505     ) {
 506         if A::Direction::is_forward() {
 507             self.prev_state.clone_from(state);
 508         }
 509     }
 510
 511     fn visit_block_end(
 512         &mut self,
 513         state: &Self::FlowState,
 514         _block_data: &'mir mir::BasicBlockData<'tcx>,
 515         _block: BasicBlock,
 516     ) {
 517         if A::Direction::is_backward() {
 518             self.prev_state.clone_from(state);
 519         }
 520     }
 521
 522     fn visit_statement_before_primary_effect(
 523         &mut self,
 524         state: &Self::FlowState,
 525         _statement: &'mir mir::Statement<'tcx>,
 526         _location: Location,
 527     ) {
 528         if let Some(before) = self.before.as_mut() {
 529             before.push(diff_pretty(state, &self.prev_state, self.analysis));
 530             self.prev_state.clone_from(state)
 531         }
 532     }
 533
 534     fn visit_statement_after_primary_effect(
 535         &mut self,
 536         state: &Self::FlowState,
 537         _statement: &'mir mir::Statement<'tcx>,
 538         _location: Location,
 539     ) {
 540         self.after.push(diff_pretty(state, &self.prev_state, self.analysis));
 541         self.prev_state.clone_from(state)
 542     }
 543
 544     fn visit_terminator_before_primary_effect(
 545         &mut self,
 546         state: &Self::FlowState,
 547         _terminator: &'mir mir::Terminator<'tcx>,
 548         _location: Location,
 549     ) {
 550         if let Some(before) = self.before.as_mut() {
 551             before.push(diff_pretty(state, &self.prev_state, self.analysis));
 552             self.prev_state.clone_from(state)
 553         }
 554     }
 555
 556     fn visit_terminator_after_primary_effect(
 557         &mut self,
 558         state: &Self::FlowState,
 559         _terminator: &'mir mir::Terminator<'tcx>,
 560         _location: Location,
 561     ) {
 562         self.after.push(diff_pretty(state, &self.prev_state, self.analysis));
 563         self.prev_state.clone_from(state)
 564     }
 565 }
 566
 567 macro_rules! regex {
 568     ($re:literal $(,)?) => {{
 569         static RE: SyncOnceCell<regex::Regex> = SyncOnceCell::new();
 570         RE.get_or_init(|| Regex::new($re).unwrap())
 571     }};
 572 }
 573
 574 fn diff_pretty<T, C>(new: T, old: T, ctxt: &C) -> String
 575 where
 576     T: DebugWithContext<C>,
 577 {
 578     if new == old {
 579         return String::new();
 580     }
 581
 582     let re = regex!("\t?\u{001f}([+-])");
 583
 584     let raw_diff = format!("{:#?}", DebugDiffWithAdapter { new, old, ctxt });
 585
 586     // Replace newlines in the `Debug` output with `<br/>`
 587     let raw_diff = raw_diff.replace('\n', r#"<br align="left"/>"#);
 588
 589     let mut inside_font_tag = false;
 590     let html_diff = re.replace_all(&raw_diff, |captures: &regex::Captures<'_>| {
 591         let mut ret = String::new();
 592         if inside_font_tag {
 593             ret.push_str(r#"</font>"#);
 594         }
 595
 596         let tag = match &captures[1] {
 597             "+" => r#"<font color="darkgreen">+"#,
 598             "-" => r#"<font color="red">-"#,
 599             _ => unreachable!(),
 600         };
 601
 602         inside_font_tag = true;
 603         ret.push_str(tag);
 604         ret
 605     });
 606
 607     let mut html_diff = match html_diff {
 608         Cow::Borrowed(_) => return raw_diff,
 609         Cow::Owned(s) => s,
 610     };
 611
 612     if inside_font_tag {
 613         html_diff.push_str("</font>");
 614     }
 615
 616     html_diff
 617 }
 618
 619 /// The background color used for zebra-striping the table.
 620 #[derive(Clone, Copy)]
 621 enum Background {
 622     Light,
 623     Dark,
 624 }
 625
 626 impl Background {
 627     fn attr(self) -> &'static str {
 628         match self {
 629             Self::Dark => "bgcolor=\"#f0f0f0\"",
 630             Self::Light => "",
 631         }
 632     }
 633 }
 634
 635 impl ops::Not for Background {
 636     type Output = Self;
 637
 638     fn not(self) -> Self {
 639         match self {
 640             Self::Light => Self::Dark,
 641             Self::Dark => Self::Light,
 642         }
 643     }
 644 }