src/librustc_borrowck/borrowck/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::repr::{BasicBlock, Mir};
  15
  16 use dot;
  17 use dot::IntoCow;
  18
  19 use std::fmt::Debug;
  20 use std::fs::File;
  21 use std::io;
  22 use std::io::prelude::*;
  23 use std::marker::PhantomData;
  24 use std::mem;
  25 use std::path::Path;
  26
  27 use super::super::MoveDataParamEnv;
  28 use super::super::MirBorrowckCtxtPreDataflow;
  29 use bitslice::bits_to_string;
  30 use indexed_set::{Idx, IdxSet};
  31 use super::{BitDenotation, DataflowState};
  32
  33 impl<O: BitDenotation> DataflowState<O> {
  34     fn each_bit<F>(&self, ctxt: &O::Ctxt, words: &IdxSet<O::Idx>, mut f: F)
  35         where F: FnMut(O::Idx) {
  36         //! Helper for iterating over the bits in a bitvector.
  37
  38         let bits_per_block = self.operator.bits_per_block(ctxt);
  39         let usize_bits: usize = mem::size_of::<usize>() * 8;
  40
  41         for (word_index, &word) in words.words().iter().enumerate() {
  42             if word != 0 {
  43                 let base_index = word_index * usize_bits;
  44                 for offset in 0..usize_bits {
  45                     let bit = 1 << offset;
  46                     if (word & bit) != 0 {
  47                         // NB: we round up the total number of bits
  48                         // that we store in any given bit set so that
  49                         // it is an even multiple of usize::BITS. This
  50                         // means that there may be some stray bits at
  51                         // the end that do not correspond to any
  52                         // actual value; that's why we first check
  53                         // that we are in range of bits_per_block.
  54                         let bit_index = base_index + offset as usize;
  55                         if bit_index >= bits_per_block {
  56                             return;
  57                         } else {
  58                             f(O::Idx::new(bit_index));
  59                         }
  60                     }
  61                 }
  62             }
  63         }
  64     }
  65
  66     pub fn interpret_set<'c, P>(&self,
  67                                 ctxt: &'c O::Ctxt,
  68                                 words: &IdxSet<O::Idx>,
  69                                 render_idx: &P)
  70                                 -> Vec<&'c Debug>
  71         where P: for <'b> Fn(&'b O::Ctxt, O::Idx) -> &'b Debug
  72     {
  73         let mut v = Vec::new();
  74         self.each_bit(ctxt, words, |i| {
  75             v.push(render_idx(ctxt, i));
  76         });
  77         v
  78     }
  79 }
  80
  81 pub trait MirWithFlowState<'tcx> {
  82     type BD: BitDenotation<Ctxt=MoveDataParamEnv<'tcx>>;
  83     fn node_id(&self) -> NodeId;
  84     fn mir(&self) -> &Mir<'tcx>;
  85     fn analysis_ctxt(&self) -> &<Self::BD as BitDenotation>::Ctxt;
  86     fn flow_state(&self) -> &DataflowState<Self::BD>;
  87 }
  88
  89 impl<'a, 'tcx: 'a, BD> MirWithFlowState<'tcx> for MirBorrowckCtxtPreDataflow<'a, 'tcx, BD>
  90     where 'a, 'tcx: 'a, BD: BitDenotation<Ctxt=MoveDataParamEnv<'tcx>>
  91 {
  92     type BD = BD;
  93     fn node_id(&self) -> NodeId { self.node_id }
  94     fn mir(&self) -> &Mir<'tcx> { self.flow_state.mir() }
  95     fn analysis_ctxt(&self) -> &BD::Ctxt { &self.flow_state.ctxt }
  96     fn flow_state(&self) -> &DataflowState<Self::BD> { &self.flow_state.flow_state }
  97 }
  98
  99 struct Graph<'a, 'tcx, MWF:'a, P> where
 100     MWF: MirWithFlowState<'tcx>
 101 {
 102     mbcx: &'a MWF,
 103     phantom: PhantomData<&'tcx ()>,
 104     render_idx: P,
 105 }
 106
 107 pub fn print_borrowck_graph_to<'a, 'tcx, BD, P>(
 108     mbcx: &MirBorrowckCtxtPreDataflow<'a, 'tcx, BD>,
 109     path: &Path,
 110     render_idx: P)
 111     -> io::Result<()>
 112     where BD: BitDenotation<Ctxt=MoveDataParamEnv<'tcx>>,
 113           P: for <'b> Fn(&'b BD::Ctxt, BD::Idx) -> &'b Debug
 114 {
 115     let g = Graph { mbcx: mbcx, phantom: PhantomData, render_idx: render_idx };
 116     let mut v = Vec::new();
 117     dot::render(&g, &mut v)?;
 118     debug!("print_borrowck_graph_to path: {} node_id: {}",
 119            path.display(), mbcx.node_id);
 120     File::create(path).and_then(|mut f| f.write_all(&v))
 121 }
 122
 123 pub type Node = BasicBlock;
 124
 125 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 126 pub struct Edge { source: BasicBlock, index: usize }
 127
 128 fn outgoing(mir: &Mir, bb: BasicBlock) -> Vec<Edge> {
 129     let succ_len = mir.basic_block_data(bb).terminator().successors().len();
 130     (0..succ_len).map(|index| Edge { source: bb, index: index}).collect()
 131 }
 132
 133 impl<'a, 'tcx, MWF, P> dot::Labeller<'a> for Graph<'a, 'tcx, MWF, P>
 134     where MWF: MirWithFlowState<'tcx>,
 135           P: for <'b> Fn(&'b <MWF::BD as BitDenotation>::Ctxt,
 136                          <MWF::BD as BitDenotation>::Idx)
 137                          -> &'b Debug,
 138 {
 139     type Node = Node;
 140     type Edge = Edge;
 141     fn graph_id(&self) -> dot::Id {
 142         dot::Id::new(format!("graph_for_node_{}",
 143                              self.mbcx.node_id()))
 144             .unwrap()
 145     }
 146
 147     fn node_id(&self, n: &Node) -> dot::Id {
 148         dot::Id::new(format!("bb_{}", n.index()))
 149             .unwrap()
 150     }
 151
 152     fn node_label(&self, n: &Node) -> dot::LabelText {
 153         // A standard MIR label, as generated by write_node_label, is
 154         // presented in a single column in a table.
 155         //
 156         // The code below does a bunch of formatting work to format a
 157         // node (i.e. MIR basic-block) label with extra
 158         // dataflow-enriched information.  In particular, the goal is
 159         // to add extra columns that present the three dataflow
 160         // bitvectors, and the data those bitvectors represent.
 161         //
 162         // It presents it in the following format (where I am
 163         // presenting the table rendering via ASCII art, one line per
 164         // row of the table, and a chunk size of 3 rather than 5):
 165         //
 166         // ------  -----------------------  ------------  --------------------
 167         //                    [e1, e3, e4]
 168         //             [e8, e9] "= ENTRY:"  <ENTRY-BITS>
 169         // ------  -----------------------  ------------  --------------------
 170         // Left
 171         // Most
 172         // Column
 173         // Is
 174         // Just
 175         // Normal
 176         // Series
 177         // Of
 178         // MIR
 179         // Stmts
 180         // ------  -----------------------  ------------  --------------------
 181         //           [g1, g4, g5] "= GEN:"  <GEN-BITS>
 182         // ------  -----------------------  ------------  --------------------
 183         //                         "KILL:"  <KILL-BITS>   "=" [k1, k3, k8]
 184         //                                                [k9]
 185         // ------  -----------------------  ------------  --------------------
 186         //
 187         // (In addition, the added dataflow is rendered with a colored
 188         // background just so it will stand out compared to the
 189         // statements.)
 190         let mut v = Vec::new();
 191         let i = n.index();
 192         let chunk_size = 5;
 193         const BG_FLOWCONTENT: &'static str = r#"bgcolor="pink""#;
 194         const ALIGN_RIGHT: &'static str = r#"align="right""#;
 195         const FACE_MONOSPACE: &'static str = r#"FACE="Courier""#;
 196         fn chunked_present_left<W:io::Write>(w: &mut W,
 197                                              interpreted: &[&Debug],
 198                                              chunk_size: usize)
 199                                              -> io::Result<()>
 200         {
 201             // This function may emit a sequence of <tr>'s, but it
 202             // always finishes with an (unfinished)
 203             // <tr><td></td><td>
 204             //
 205             // Thus, after being called, one should finish both the
 206             // pending <td> as well as the <tr> itself.
 207             let mut seen_one = false;
 208             for c in interpreted.chunks(chunk_size) {
 209                 if seen_one {
 210                     // if not the first row, finish off the previous row
 211                     write!(w, "</td><td></td><td></td></tr>")?;
 212                 }
 213                 write!(w, "<tr><td></td><td {bg} {align}>{objs:?}",
 214                        bg = BG_FLOWCONTENT,
 215                        align = ALIGN_RIGHT,
 216                        objs = c)?;
 217                 seen_one = true;
 218             }
 219             if !seen_one {
 220                 write!(w, "<tr><td></td><td {bg} {align}>[]",
 221                        bg = BG_FLOWCONTENT,
 222                        align = ALIGN_RIGHT)?;
 223             }
 224             Ok(())
 225         }
 226         ::rustc_mir::graphviz::write_node_label(
 227             *n, self.mbcx.mir(), &mut v, 4,
 228             |w| {
 229                 let ctxt = self.mbcx.analysis_ctxt();
 230                 let flow = self.mbcx.flow_state();
 231                 let entry_interp = flow.interpret_set(ctxt,
 232                                                       flow.sets.on_entry_set_for(i),
 233                                                       &self.render_idx);
 234                 chunked_present_left(w, &entry_interp[..], chunk_size)?;
 235                 let bits_per_block = flow.sets.bits_per_block();
 236                 let entry = flow.sets.on_entry_set_for(i);
 237                 debug!("entry set for i={i} bits_per_block: {bpb} entry: {e:?} interp: {ei:?}",
 238                        i=i, e=entry, bpb=bits_per_block, ei=entry_interp);
 239                 write!(w, "= ENTRY:</td><td {bg}><FONT {face}>{entrybits:?}</FONT></td>\
 240                                         <td></td></tr>",
 241                        bg = BG_FLOWCONTENT,
 242                        face = FACE_MONOSPACE,
 243                        entrybits=bits_to_string(entry.words(), bits_per_block))
 244             },
 245             |w| {
 246                 let ctxt = self.mbcx.analysis_ctxt();
 247                 let flow = self.mbcx.flow_state();
 248                 let gen_interp =
 249                     flow.interpret_set(ctxt, flow.sets.gen_set_for(i), &self.render_idx);
 250                 let kill_interp =
 251                     flow.interpret_set(ctxt, flow.sets.kill_set_for(i), &self.render_idx);
 252                 chunked_present_left(w, &gen_interp[..], chunk_size)?;
 253                 let bits_per_block = flow.sets.bits_per_block();
 254                 {
 255                     let gen = flow.sets.gen_set_for(i);
 256                     debug!("gen set for i={i} bits_per_block: {bpb} gen: {g:?} interp: {gi:?}",
 257                            i=i, g=gen, bpb=bits_per_block, gi=gen_interp);
 258                     write!(w, " = GEN:</td><td {bg}><FONT {face}>{genbits:?}</FONT></td>\
 259                                            <td></td></tr>",
 260                            bg = BG_FLOWCONTENT,
 261                            face = FACE_MONOSPACE,
 262                            genbits=bits_to_string(gen.words(), bits_per_block))?;
 263                 }
 264
 265                 {
 266                     let kill = flow.sets.kill_set_for(i);
 267                     debug!("kill set for i={i} bits_per_block: {bpb} kill: {k:?} interp: {ki:?}",
 268                            i=i, k=kill, bpb=bits_per_block, ki=kill_interp);
 269                     write!(w, "<tr><td></td><td {bg} {align}>KILL:</td>\
 270                                             <td {bg}><FONT {face}>{killbits:?}</FONT></td>",
 271                            bg = BG_FLOWCONTENT,
 272                            align = ALIGN_RIGHT,
 273                            face = FACE_MONOSPACE,
 274                            killbits=bits_to_string(kill.words(), bits_per_block))?;
 275                 }
 276
 277                 // (chunked_present_right)
 278                 let mut seen_one = false;
 279                 for k in kill_interp.chunks(chunk_size) {
 280                     if !seen_one {
 281                         // continuation of row; this is fourth <td>
 282                         write!(w, "<td {bg}>= {kill:?}</td></tr>",
 283                                bg = BG_FLOWCONTENT,
 284                                kill=k)?;
 285                     } else {
 286                         // new row, with indent of three <td>'s
 287                         write!(w, "<tr><td></td><td></td><td></td><td {bg}>{kill:?}</td></tr>",
 288                                bg = BG_FLOWCONTENT,
 289                                kill=k)?;
 290                     }
 291                     seen_one = true;
 292                 }
 293                 if !seen_one {
 294                     write!(w, "<td {bg}>= []</td></tr>",
 295                            bg = BG_FLOWCONTENT)?;
 296                 }
 297
 298                 Ok(())
 299             })
 300             .unwrap();
 301         dot::LabelText::html(String::from_utf8(v).unwrap())
 302     }
 303
 304     fn node_shape(&self, _n: &Node) -> Option<dot::LabelText> {
 305         Some(dot::LabelText::label("none"))
 306     }
 307 }
 308
 309 impl<'a, 'tcx, MWF, P> dot::GraphWalk<'a> for Graph<'a, 'tcx, MWF, P>
 310     where MWF: MirWithFlowState<'tcx>
 311 {
 312     type Node = Node;
 313     type Edge = Edge;
 314     fn nodes(&self) -> dot::Nodes<Node> {
 315         self.mbcx.mir().all_basic_blocks().into_cow()
 316     }
 317
 318     fn edges(&self) -> dot::Edges<Edge> {
 319         let mir = self.mbcx.mir();
 320         let blocks = mir.all_basic_blocks();
 321         // base initial capacity on assumption every block has at
 322         // least one outgoing edge (Which should be true for all
 323         // blocks but one, the exit-block).
 324         let mut edges = Vec::with_capacity(blocks.len());
 325         for bb in blocks {
 326             let outgoing = outgoing(mir, bb);
 327             edges.extend(outgoing.into_iter());
 328         }
 329         edges.into_cow()
 330     }
 331
 332     fn source(&self, edge: &Edge) -> Node {
 333         edge.source
 334     }
 335
 336     fn target(&self, edge: &Edge) -> Node {
 337         let mir = self.mbcx.mir();
 338         mir.basic_block_data(edge.source).terminator().successors()[edge.index]
 339     }
 340 }