src/librustc_mir/dataflow/graphviz.rs

   1 // Copyright 2012-2016 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! Hook into libgraphviz for rendering dataflow graphs for MIR.
  12
  13 use syntax::ast::NodeId;
  14 use rustc::mir::{BasicBlock, Mir};
  15 use rustc_data_structures::bitslice::bits_to_string;
  16 use rustc_data_structures::indexed_vec::Idx;
  17
  18 use dot;
  19 use dot::IntoCow;
  20
  21 use std::fs;
  22 use std::io;
  23 use std::marker::PhantomData;
  24 use std::path::Path;
  25
  26 use super::{BitDenotation, DataflowState};
  27 use super::DataflowBuilder;
  28 use super::DebugFormatted;
  29
  30 pub trait MirWithFlowState<'tcx> {
  31     type BD: BitDenotation;
  32     fn node_id(&self) -> NodeId;
  33     fn mir(&self) -> &Mir<'tcx>;
  34     fn flow_state(&self) -> &DataflowState<Self::BD>;
  35 }
  36
  37 impl<'a, 'tcx, BD> MirWithFlowState<'tcx> for DataflowBuilder<'a, 'tcx, BD>
  38     where BD: BitDenotation
  39 {
  40     type BD = BD;
  41     fn node_id(&self) -> NodeId { self.node_id }
  42     fn mir(&self) -> &Mir<'tcx> { self.flow_state.mir() }
  43     fn flow_state(&self) -> &DataflowState<Self::BD> { &self.flow_state.flow_state }
  44 }
  45
  46 struct Graph<'a, 'tcx, MWF:'a, P> where
  47     MWF: MirWithFlowState<'tcx>
  48 {
  49     mbcx: &'a MWF,
  50     phantom: PhantomData<&'tcx ()>,
  51     render_idx: P,
  52 }
  53
  54 pub(crate) fn print_borrowck_graph_to<'a, 'tcx, BD, P>(
  55     mbcx: &DataflowBuilder<'a, 'tcx, BD>,
  56     path: &Path,
  57     render_idx: P)
  58     -> io::Result<()>
  59     where BD: BitDenotation,
  60           P: Fn(&BD, BD::Idx) -> DebugFormatted
  61 {
  62     let g = Graph { mbcx, phantom: PhantomData, render_idx };
  63     let mut v = Vec::new();
  64     dot::render(&g, &mut v)?;
  65     debug!("print_borrowck_graph_to path: {} node_id: {}",
  66            path.display(), mbcx.node_id);
  67     fs::write(path, v)
  68 }
  69
  70 pub type Node = BasicBlock;
  71
  72 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
  73 pub struct Edge { source: BasicBlock, index: usize }
  74
  75 fn outgoing(mir: &Mir, bb: BasicBlock) -> Vec<Edge> {
  76     (0..mir[bb].terminator().successors().count())
  77         .map(|index| Edge { source: bb, index: index}).collect()
  78 }
  79
  80 impl<'a, 'tcx, MWF, P> dot::Labeller<'a> for Graph<'a, 'tcx, MWF, P>
  81     where MWF: MirWithFlowState<'tcx>,
  82           P: Fn(&MWF::BD, <MWF::BD as BitDenotation>::Idx) -> DebugFormatted,
  83 {
  84     type Node = Node;
  85     type Edge = Edge;
  86     fn graph_id(&self) -> dot::Id {
  87         dot::Id::new(format!("graph_for_node_{}",
  88                              self.mbcx.node_id()))
  89             .unwrap()
  90     }
  91
  92     fn node_id(&self, n: &Node) -> dot::Id {
  93         dot::Id::new(format!("bb_{}", n.index()))
  94             .unwrap()
  95     }
  96
  97     fn node_label(&self, n: &Node) -> dot::LabelText {
  98         // Node label is something like this:
  99         // +---------+----------------------------------+------------------+------------------+
 100         // | ENTRY   | MIR                              | GEN              | KILL             |
 101         // +---------+----------------------------------+------------------+------------------+
 102         // |         |  0: StorageLive(_7)              | bb3[2]: reserved | bb2[0]: reserved |
 103         // |         |  1: StorageLive(_8)              | bb3[2]: active   | bb2[0]: active   |
 104         // |         |  2: _8 = &mut _1                 |                  | bb4[2]: reserved |
 105         // |         |                                  |                  | bb4[2]: active   |
 106         // |         |                                  |                  | bb9[0]: reserved |
 107         // |         |                                  |                  | bb9[0]: active   |
 108         // |         |                                  |                  | bb10[0]: reserved|
 109         // |         |                                  |                  | bb10[0]: active  |
 110         // |         |                                  |                  | bb11[0]: reserved|
 111         // |         |                                  |                  | bb11[0]: active  |
 112         // +---------+----------------------------------+------------------+------------------+
 113         // | [00-00] | _7 = const Foo::twiddle(move _8) | [0c-00]          | [f3-0f]          |
 114         // +---------+----------------------------------+------------------+------------------+
 115         let mut v = Vec::new();
 116         self.node_label_internal(n, &mut v, *n, self.mbcx.mir()).unwrap();
 117         dot::LabelText::html(String::from_utf8(v).unwrap())
 118     }
 119
 120
 121     fn node_shape(&self, _n: &Node) -> Option<dot::LabelText> {
 122         Some(dot::LabelText::label("none"))
 123     }
 124
 125     fn edge_label(&'a self, e: &Edge) -> dot::LabelText<'a> {
 126         let term = self.mbcx.mir()[e.source].terminator();
 127         let label = &term.kind.fmt_successor_labels()[e.index];
 128         dot::LabelText::label(label.clone())
 129     }
 130 }
 131
 132 impl<'a, 'tcx, MWF, P> Graph<'a, 'tcx, MWF, P>
 133 where MWF: MirWithFlowState<'tcx>,
 134       P: Fn(&MWF::BD, <MWF::BD as BitDenotation>::Idx) -> DebugFormatted,
 135 {
 136     /// Generate the node label
 137     fn node_label_internal<W: io::Write>(&self,
 138                                          n: &Node,
 139                                          w: &mut W,
 140                                          block: BasicBlock,
 141                                          mir: &Mir) -> io::Result<()> {
 142         // Header rows
 143         const HDRS: [&'static str; 4] = ["ENTRY", "MIR", "BLOCK GENS", "BLOCK KILLS"];
 144         const HDR_FMT: &'static str = "bgcolor=\"grey\"";
 145         write!(w, "<table><tr><td rowspan=\"{}\">", HDRS.len())?;
 146         write!(w, "{:?}", block.index())?;
 147         write!(w, "</td></tr><tr>")?;
 148         for hdr in &HDRS {
 149             write!(w, "<td {}>{}</td>", HDR_FMT, hdr)?;
 150         }
 151         write!(w, "</tr>")?;
 152
 153         // Data row
 154         self.node_label_verbose_row(n, w, block, mir)?;
 155         self.node_label_final_row(n, w, block, mir)?;
 156         write!(w, "</table>")?;
 157
 158         Ok(())
 159     }
 160
 161     /// Build the verbose row: full MIR data, and detailed gen/kill/entry sets
 162     fn node_label_verbose_row<W: io::Write>(&self,
 163                                             n: &Node,
 164                                             w: &mut W,
 165                                             block: BasicBlock,
 166                                             mir: &Mir)
 167                                             -> io::Result<()> {
 168         let i = n.index();
 169
 170         macro_rules! dump_set_for {
 171             ($set:ident) => {
 172                 write!(w, "<td>")?;
 173
 174                 let flow = self.mbcx.flow_state();
 175                 let entry_interp = flow.interpret_set(&flow.operator,
 176                                                       flow.sets.$set(i),
 177                                                       &self.render_idx);
 178                 for e in &entry_interp {
 179                     write!(w, "{:?}<br/>", e)?;
 180                 }
 181                 write!(w, "</td>")?;
 182             }
 183         }
 184
 185         write!(w, "<tr>")?;
 186         // Entry
 187         dump_set_for!(on_entry_set_for);
 188
 189         // MIR statements
 190         write!(w, "<td>")?;
 191         {
 192             let data = &mir[block];
 193             for (i, statement) in data.statements.iter().enumerate() {
 194                 write!(w, "{}<br align=\"left\"/>",
 195                        dot::escape_html(&format!("{:3}: {:?}", i, statement)))?;
 196             }
 197         }
 198         write!(w, "</td>")?;
 199
 200         // Gen
 201         dump_set_for!(gen_set_for);
 202
 203         // Kill
 204         dump_set_for!(kill_set_for);
 205
 206         write!(w, "</tr>")?;
 207
 208         Ok(())
 209     }
 210
 211     /// Build the summary row: terminator, gen/kill/entry bit sets
 212     fn node_label_final_row<W: io::Write>(&self,
 213                                           n: &Node,
 214                                           w: &mut W,
 215                                           block: BasicBlock,
 216                                           mir: &Mir)
 217                                           -> io::Result<()> {
 218         let i = n.index();
 219
 220         macro_rules! dump_set_for {
 221             ($set:ident) => {
 222                 let flow = self.mbcx.flow_state();
 223                 let bits_per_block = flow.sets.bits_per_block();
 224                 let set = flow.sets.$set(i);
 225                 write!(w, "<td>{:?}</td>",
 226                        dot::escape_html(&bits_to_string(set.words(), bits_per_block)))?;
 227             }
 228         }
 229
 230         write!(w, "<tr>")?;
 231         // Entry
 232         dump_set_for!(on_entry_set_for);
 233
 234         // Terminator
 235         write!(w, "<td>")?;
 236         {
 237             let data = &mir[block];
 238             let mut terminator_head = String::new();
 239             data.terminator().kind.fmt_head(&mut terminator_head).unwrap();
 240             write!(w, "{}", dot::escape_html(&terminator_head))?;
 241         }
 242         write!(w, "</td>")?;
 243
 244         // Gen
 245         dump_set_for!(gen_set_for);
 246
 247         // Kill
 248         dump_set_for!(kill_set_for);
 249
 250         write!(w, "</tr>")?;
 251
 252         Ok(())
 253     }
 254 }
 255
 256 impl<'a, 'tcx, MWF, P> dot::GraphWalk<'a> for Graph<'a, 'tcx, MWF, P>
 257     where MWF: MirWithFlowState<'tcx>
 258 {
 259     type Node = Node;
 260     type Edge = Edge;
 261     fn nodes(&self) -> dot::Nodes<Node> {
 262         self.mbcx.mir()
 263             .basic_blocks()
 264             .indices()
 265             .collect::<Vec<_>>()
 266             .into_cow()
 267     }
 268
 269     fn edges(&self) -> dot::Edges<Edge> {
 270         let mir = self.mbcx.mir();
 271         // base initial capacity on assumption every block has at
 272         // least one outgoing edge (Which should be true for all
 273         // blocks but one, the exit-block).
 274         let mut edges = Vec::with_capacity(mir.basic_blocks().len());
 275         for bb in mir.basic_blocks().indices() {
 276             let outgoing = outgoing(mir, bb);
 277             edges.extend(outgoing.into_iter());
 278         }
 279         edges.into_cow()
 280     }
 281
 282     fn source(&self, edge: &Edge) -> Node {
 283         edge.source
 284     }
 285
 286     fn target(&self, edge: &Edge) -> Node {
 287         let mir = self.mbcx.mir();
 288         *mir[edge.source].terminator().successors().nth(edge.index).unwrap()
 289     }
 290 }