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