]>
Commit | Line | Data |
---|---|---|
1a4d82fc | 1 | // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT |
970d7e83 LB |
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 | ||
1a4d82fc JJ |
12 | //! A module for propagating forward dataflow information. The analysis |
13 | //! assumes that the items to be propagated can be represented as bits | |
14 | //! and thus uses bitvectors. Your job is simply to specify the so-called | |
15 | //! GEN and KILL bits for each expression. | |
970d7e83 | 16 | |
1a4d82fc JJ |
17 | use middle::cfg; |
18 | use middle::cfg::CFGIndex; | |
19 | use middle::ty; | |
c34b1796 | 20 | use std::io; |
85aaf69f | 21 | use std::usize; |
970d7e83 | 22 | use syntax::ast; |
1a4d82fc | 23 | use syntax::ast_util::IdRange; |
e9174d1e | 24 | use syntax::print::pp; |
b039eaaf | 25 | use syntax::print::pprust::PrintState; |
1a4d82fc | 26 | use util::nodemap::NodeMap; |
e9174d1e | 27 | use rustc_front::hir; |
92a42be0 | 28 | use rustc_front::intravisit; |
e9174d1e SL |
29 | use rustc_front::print::pprust; |
30 | ||
1a4d82fc | 31 | |
c34b1796 | 32 | #[derive(Copy, Clone, Debug)] |
1a4d82fc JJ |
33 | pub enum EntryOrExit { |
34 | Entry, | |
35 | Exit, | |
36 | } | |
970d7e83 | 37 | |
1a4d82fc JJ |
38 | #[derive(Clone)] |
39 | pub struct DataFlowContext<'a, 'tcx: 'a, O> { | |
40 | tcx: &'a ty::ctxt<'tcx>, | |
41 | ||
42 | /// a name for the analysis using this dataflow instance | |
43 | analysis_name: &'static str, | |
970d7e83 LB |
44 | |
45 | /// the data flow operator | |
1a4d82fc | 46 | oper: O, |
970d7e83 LB |
47 | |
48 | /// number of bits to propagate per id | |
c34b1796 | 49 | bits_per_id: usize, |
970d7e83 LB |
50 | |
51 | /// number of words we will use to store bits_per_id. | |
85aaf69f | 52 | /// equal to bits_per_id/usize::BITS rounded up. |
c34b1796 | 53 | words_per_id: usize, |
970d7e83 | 54 | |
1a4d82fc JJ |
55 | // mapping from node to cfg node index |
56 | // FIXME (#6298): Shouldn't this go with CFG? | |
c34b1796 | 57 | nodeid_to_index: NodeMap<Vec<CFGIndex>>, |
970d7e83 | 58 | |
1a4d82fc | 59 | // Bit sets per cfg node. The following three fields (`gens`, `kills`, |
970d7e83 LB |
60 | // and `on_entry`) all have the same structure. For each id in |
61 | // `id_range`, there is a range of words equal to `words_per_id`. | |
62 | // So, to access the bits for any given id, you take a slice of | |
63 | // the full vector (see the method `compute_id_range()`). | |
64 | ||
1a4d82fc | 65 | /// bits generated as we exit the cfg node. Updated by `add_gen()`. |
c34b1796 | 66 | gens: Vec<usize>, |
970d7e83 | 67 | |
9346a6ac AL |
68 | /// bits killed as we exit the cfg node, or non-locally jump over |
69 | /// it. Updated by `add_kill(KillFrom::ScopeEnd)`. | |
70 | scope_kills: Vec<usize>, | |
71 | ||
72 | /// bits killed as we exit the cfg node directly; if it is jumped | |
73 | /// over, e.g. via `break`, the kills are not reflected in the | |
74 | /// jump's effects. Updated by `add_kill(KillFrom::Execution)`. | |
75 | action_kills: Vec<usize>, | |
970d7e83 | 76 | |
1a4d82fc | 77 | /// bits that are valid on entry to the cfg node. Updated by |
970d7e83 | 78 | /// `propagate()`. |
c34b1796 | 79 | on_entry: Vec<usize>, |
1a4d82fc JJ |
80 | } |
81 | ||
82 | pub trait BitwiseOperator { | |
83 | /// Joins two predecessor bits together, typically either `|` or `&` | |
c34b1796 | 84 | fn join(&self, succ: usize, pred: usize) -> usize; |
970d7e83 LB |
85 | } |
86 | ||
87 | /// Parameterization for the precise form of data flow that is used. | |
1a4d82fc | 88 | pub trait DataFlowOperator : BitwiseOperator { |
970d7e83 LB |
89 | /// Specifies the initial value for each bit in the `on_entry` set |
90 | fn initial_value(&self) -> bool; | |
1a4d82fc | 91 | } |
970d7e83 | 92 | |
1a4d82fc JJ |
93 | struct PropagationContext<'a, 'b: 'a, 'tcx: 'b, O: 'a> { |
94 | dfcx: &'a mut DataFlowContext<'b, 'tcx, O>, | |
95 | changed: bool | |
96 | } | |
970d7e83 | 97 | |
c34b1796 AL |
98 | fn get_cfg_indices<'a>(id: ast::NodeId, index: &'a NodeMap<Vec<CFGIndex>>) -> &'a [CFGIndex] { |
99 | let opt_indices = index.get(&id); | |
100 | opt_indices.map(|v| &v[..]).unwrap_or(&[]) | |
970d7e83 LB |
101 | } |
102 | ||
1a4d82fc JJ |
103 | impl<'a, 'tcx, O:DataFlowOperator> DataFlowContext<'a, 'tcx, O> { |
104 | fn has_bitset_for_nodeid(&self, n: ast::NodeId) -> bool { | |
105 | assert!(n != ast::DUMMY_NODE_ID); | |
106 | self.nodeid_to_index.contains_key(&n) | |
107 | } | |
970d7e83 LB |
108 | } |
109 | ||
1a4d82fc JJ |
110 | impl<'a, 'tcx, O:DataFlowOperator> pprust::PpAnn for DataFlowContext<'a, 'tcx, O> { |
111 | fn pre(&self, | |
112 | ps: &mut pprust::State, | |
c34b1796 | 113 | node: pprust::AnnNode) -> io::Result<()> { |
1a4d82fc | 114 | let id = match node { |
b039eaaf | 115 | pprust::NodeName(_) => 0, |
1a4d82fc JJ |
116 | pprust::NodeExpr(expr) => expr.id, |
117 | pprust::NodeBlock(blk) => blk.id, | |
c34b1796 | 118 | pprust::NodeItem(_) | pprust::NodeSubItem(_) => 0, |
1a4d82fc JJ |
119 | pprust::NodePat(pat) => pat.id |
120 | }; | |
121 | ||
c34b1796 AL |
122 | if !self.has_bitset_for_nodeid(id) { |
123 | return Ok(()); | |
124 | } | |
125 | ||
126 | assert!(self.bits_per_id > 0); | |
127 | let indices = get_cfg_indices(id, &self.nodeid_to_index); | |
128 | for &cfgidx in indices { | |
1a4d82fc | 129 | let (start, end) = self.compute_id_range(cfgidx); |
85aaf69f | 130 | let on_entry = &self.on_entry[start.. end]; |
1a4d82fc JJ |
131 | let entry_str = bits_to_string(on_entry); |
132 | ||
85aaf69f | 133 | let gens = &self.gens[start.. end]; |
1a4d82fc JJ |
134 | let gens_str = if gens.iter().any(|&u| u != 0) { |
135 | format!(" gen: {}", bits_to_string(gens)) | |
136 | } else { | |
137 | "".to_string() | |
138 | }; | |
139 | ||
9346a6ac AL |
140 | let action_kills = &self.action_kills[start .. end]; |
141 | let action_kills_str = if action_kills.iter().any(|&u| u != 0) { | |
142 | format!(" action_kill: {}", bits_to_string(action_kills)) | |
143 | } else { | |
144 | "".to_string() | |
145 | }; | |
146 | ||
147 | let scope_kills = &self.scope_kills[start .. end]; | |
148 | let scope_kills_str = if scope_kills.iter().any(|&u| u != 0) { | |
149 | format!(" scope_kill: {}", bits_to_string(scope_kills)) | |
1a4d82fc JJ |
150 | } else { |
151 | "".to_string() | |
152 | }; | |
970d7e83 | 153 | |
9346a6ac AL |
154 | try!(ps.synth_comment( |
155 | format!("id {}: {}{}{}{}", id, entry_str, | |
156 | gens_str, action_kills_str, scope_kills_str))); | |
1a4d82fc JJ |
157 | try!(pp::space(&mut ps.s)); |
158 | } | |
159 | Ok(()) | |
160 | } | |
970d7e83 LB |
161 | } |
162 | ||
e9174d1e | 163 | fn build_nodeid_to_index(decl: Option<&hir::FnDecl>, |
c34b1796 | 164 | cfg: &cfg::CFG) -> NodeMap<Vec<CFGIndex>> { |
85aaf69f | 165 | let mut index = NodeMap(); |
1a4d82fc JJ |
166 | |
167 | // FIXME (#6298): Would it be better to fold formals from decl | |
168 | // into cfg itself? i.e. introduce a fn-based flow-graph in | |
169 | // addition to the current block-based flow-graph, rather than | |
170 | // have to put traversals like this here? | |
171 | match decl { | |
172 | None => {} | |
173 | Some(decl) => add_entries_from_fn_decl(&mut index, decl, cfg.entry) | |
174 | } | |
175 | ||
176 | cfg.graph.each_node(|node_idx, node| { | |
c34b1796 AL |
177 | if let cfg::CFGNodeData::AST(id) = node.data { |
178 | index.entry(id).or_insert(vec![]).push(node_idx); | |
1a4d82fc JJ |
179 | } |
180 | true | |
181 | }); | |
182 | ||
183 | return index; | |
184 | ||
c34b1796 | 185 | fn add_entries_from_fn_decl(index: &mut NodeMap<Vec<CFGIndex>>, |
e9174d1e | 186 | decl: &hir::FnDecl, |
1a4d82fc JJ |
187 | entry: CFGIndex) { |
188 | //! add mappings from the ast nodes for the formal bindings to | |
189 | //! the entry-node in the graph. | |
190 | struct Formals<'a> { | |
191 | entry: CFGIndex, | |
c34b1796 | 192 | index: &'a mut NodeMap<Vec<CFGIndex>>, |
1a4d82fc JJ |
193 | } |
194 | let mut formals = Formals { entry: entry, index: index }; | |
92a42be0 SL |
195 | intravisit::walk_fn_decl(&mut formals, decl); |
196 | impl<'a, 'v> intravisit::Visitor<'v> for Formals<'a> { | |
e9174d1e | 197 | fn visit_pat(&mut self, p: &hir::Pat) { |
c34b1796 | 198 | self.index.entry(p.id).or_insert(vec![]).push(self.entry); |
92a42be0 | 199 | intravisit::walk_pat(self, p) |
1a4d82fc JJ |
200 | } |
201 | } | |
202 | } | |
970d7e83 LB |
203 | } |
204 | ||
9346a6ac AL |
205 | /// Flag used by `add_kill` to indicate whether the provided kill |
206 | /// takes effect only when control flows directly through the node in | |
207 | /// question, or if the kill's effect is associated with any | |
208 | /// control-flow directly through or indirectly over the node. | |
209 | #[derive(Copy, Clone, PartialEq, Debug)] | |
210 | pub enum KillFrom { | |
211 | /// A `ScopeEnd` kill is one that takes effect when any control | |
212 | /// flow goes over the node. A kill associated with the end of the | |
213 | /// scope of a variable declaration `let x;` is an example of a | |
214 | /// `ScopeEnd` kill. | |
215 | ScopeEnd, | |
216 | ||
217 | /// An `Execution` kill is one that takes effect only when control | |
218 | /// flow goes through the node to completion. A kill associated | |
219 | /// with an assignment statement `x = expr;` is an example of an | |
220 | /// `Execution` kill. | |
221 | Execution, | |
222 | } | |
223 | ||
1a4d82fc JJ |
224 | impl<'a, 'tcx, O:DataFlowOperator> DataFlowContext<'a, 'tcx, O> { |
225 | pub fn new(tcx: &'a ty::ctxt<'tcx>, | |
226 | analysis_name: &'static str, | |
e9174d1e | 227 | decl: Option<&hir::FnDecl>, |
1a4d82fc | 228 | cfg: &cfg::CFG, |
970d7e83 | 229 | oper: O, |
1a4d82fc | 230 | id_range: IdRange, |
c34b1796 | 231 | bits_per_id: usize) -> DataFlowContext<'a, 'tcx, O> { |
9346a6ac | 232 | let words_per_id = (bits_per_id + usize::BITS - 1) / usize::BITS; |
1a4d82fc JJ |
233 | let num_nodes = cfg.graph.all_nodes().len(); |
234 | ||
235 | debug!("DataFlowContext::new(analysis_name: {}, id_range={:?}, \ | |
236 | bits_per_id={}, words_per_id={}) \ | |
237 | num_nodes: {}", | |
238 | analysis_name, id_range, bits_per_id, words_per_id, | |
239 | num_nodes); | |
970d7e83 | 240 | |
85aaf69f | 241 | let entry = if oper.initial_value() { usize::MAX } else {0}; |
970d7e83 | 242 | |
c1a9b12d SL |
243 | let zeroes = vec![0; num_nodes * words_per_id]; |
244 | let gens = zeroes.clone(); | |
245 | let kills1 = zeroes.clone(); | |
246 | let kills2 = zeroes; | |
247 | let on_entry = vec![entry; num_nodes * words_per_id]; | |
1a4d82fc JJ |
248 | |
249 | let nodeid_to_index = build_nodeid_to_index(decl, cfg); | |
970d7e83 LB |
250 | |
251 | DataFlowContext { | |
252 | tcx: tcx, | |
1a4d82fc | 253 | analysis_name: analysis_name, |
970d7e83 | 254 | words_per_id: words_per_id, |
1a4d82fc | 255 | nodeid_to_index: nodeid_to_index, |
970d7e83 LB |
256 | bits_per_id: bits_per_id, |
257 | oper: oper, | |
258 | gens: gens, | |
9346a6ac AL |
259 | action_kills: kills1, |
260 | scope_kills: kills2, | |
970d7e83 LB |
261 | on_entry: on_entry |
262 | } | |
263 | } | |
264 | ||
c34b1796 | 265 | pub fn add_gen(&mut self, id: ast::NodeId, bit: usize) { |
970d7e83 | 266 | //! Indicates that `id` generates `bit` |
1a4d82fc JJ |
267 | debug!("{} add_gen(id={}, bit={})", |
268 | self.analysis_name, id, bit); | |
269 | assert!(self.nodeid_to_index.contains_key(&id)); | |
270 | assert!(self.bits_per_id > 0); | |
970d7e83 | 271 | |
c34b1796 AL |
272 | let indices = get_cfg_indices(id, &self.nodeid_to_index); |
273 | for &cfgidx in indices { | |
274 | let (start, end) = self.compute_id_range(cfgidx); | |
275 | let gens = &mut self.gens[start.. end]; | |
276 | set_bit(gens, bit); | |
277 | } | |
970d7e83 LB |
278 | } |
279 | ||
9346a6ac | 280 | pub fn add_kill(&mut self, kind: KillFrom, id: ast::NodeId, bit: usize) { |
970d7e83 | 281 | //! Indicates that `id` kills `bit` |
1a4d82fc JJ |
282 | debug!("{} add_kill(id={}, bit={})", |
283 | self.analysis_name, id, bit); | |
284 | assert!(self.nodeid_to_index.contains_key(&id)); | |
285 | assert!(self.bits_per_id > 0); | |
970d7e83 | 286 | |
c34b1796 AL |
287 | let indices = get_cfg_indices(id, &self.nodeid_to_index); |
288 | for &cfgidx in indices { | |
289 | let (start, end) = self.compute_id_range(cfgidx); | |
9346a6ac AL |
290 | let kills = match kind { |
291 | KillFrom::Execution => &mut self.action_kills[start.. end], | |
292 | KillFrom::ScopeEnd => &mut self.scope_kills[start.. end], | |
293 | }; | |
c34b1796 AL |
294 | set_bit(kills, bit); |
295 | } | |
970d7e83 LB |
296 | } |
297 | ||
c34b1796 | 298 | fn apply_gen_kill(&self, cfgidx: CFGIndex, bits: &mut [usize]) { |
1a4d82fc JJ |
299 | //! Applies the gen and kill sets for `cfgidx` to `bits` |
300 | debug!("{} apply_gen_kill(cfgidx={:?}, bits={}) [before]", | |
301 | self.analysis_name, cfgidx, mut_bits_to_string(bits)); | |
302 | assert!(self.bits_per_id > 0); | |
970d7e83 | 303 | |
1a4d82fc | 304 | let (start, end) = self.compute_id_range(cfgidx); |
85aaf69f | 305 | let gens = &self.gens[start.. end]; |
1a4d82fc | 306 | bitwise(bits, gens, &Union); |
9346a6ac AL |
307 | let kills = &self.action_kills[start.. end]; |
308 | bitwise(bits, kills, &Subtract); | |
309 | let kills = &self.scope_kills[start.. end]; | |
1a4d82fc | 310 | bitwise(bits, kills, &Subtract); |
970d7e83 | 311 | |
1a4d82fc JJ |
312 | debug!("{} apply_gen_kill(cfgidx={:?}, bits={}) [after]", |
313 | self.analysis_name, cfgidx, mut_bits_to_string(bits)); | |
970d7e83 LB |
314 | } |
315 | ||
c34b1796 | 316 | fn compute_id_range(&self, cfgidx: CFGIndex) -> (usize, usize) { |
1a4d82fc | 317 | let n = cfgidx.node_id(); |
970d7e83 LB |
318 | let start = n * self.words_per_id; |
319 | let end = start + self.words_per_id; | |
970d7e83 LB |
320 | |
321 | assert!(start < self.gens.len()); | |
322 | assert!(end <= self.gens.len()); | |
9346a6ac AL |
323 | assert!(self.gens.len() == self.action_kills.len()); |
324 | assert!(self.gens.len() == self.scope_kills.len()); | |
970d7e83 LB |
325 | assert!(self.gens.len() == self.on_entry.len()); |
326 | ||
327 | (start, end) | |
328 | } | |
329 | ||
330 | ||
c34b1796 AL |
331 | pub fn each_bit_on_entry<F>(&self, id: ast::NodeId, mut f: F) -> bool where |
332 | F: FnMut(usize) -> bool, | |
1a4d82fc | 333 | { |
970d7e83 LB |
334 | //! Iterates through each bit that is set on entry to `id`. |
335 | //! Only useful after `propagate()` has been called. | |
1a4d82fc | 336 | if !self.has_bitset_for_nodeid(id) { |
970d7e83 LB |
337 | return true; |
338 | } | |
c34b1796 AL |
339 | let indices = get_cfg_indices(id, &self.nodeid_to_index); |
340 | for &cfgidx in indices { | |
92a42be0 | 341 | if !self.each_bit_for_node(EntryOrExit::Entry, cfgidx, |i| f(i)) { |
c34b1796 AL |
342 | return false; |
343 | } | |
344 | } | |
345 | return true; | |
970d7e83 LB |
346 | } |
347 | ||
1a4d82fc | 348 | pub fn each_bit_for_node<F>(&self, e: EntryOrExit, cfgidx: CFGIndex, f: F) -> bool where |
c34b1796 | 349 | F: FnMut(usize) -> bool, |
1a4d82fc JJ |
350 | { |
351 | //! Iterates through each bit that is set on entry/exit to `cfgidx`. | |
970d7e83 LB |
352 | //! Only useful after `propagate()` has been called. |
353 | ||
1a4d82fc JJ |
354 | if self.bits_per_id == 0 { |
355 | // Skip the surprisingly common degenerate case. (Note | |
356 | // compute_id_range requires self.words_per_id > 0.) | |
357 | return true; | |
358 | } | |
359 | ||
360 | let (start, end) = self.compute_id_range(cfgidx); | |
85aaf69f | 361 | let on_entry = &self.on_entry[start.. end]; |
1a4d82fc JJ |
362 | let temp_bits; |
363 | let slice = match e { | |
92a42be0 SL |
364 | EntryOrExit::Entry => on_entry, |
365 | EntryOrExit::Exit => { | |
1a4d82fc | 366 | let mut t = on_entry.to_vec(); |
85aaf69f | 367 | self.apply_gen_kill(cfgidx, &mut t); |
1a4d82fc | 368 | temp_bits = t; |
85aaf69f | 369 | &temp_bits[..] |
1a4d82fc JJ |
370 | } |
371 | }; | |
372 | debug!("{} each_bit_for_node({:?}, cfgidx={:?}) bits={}", | |
373 | self.analysis_name, e, cfgidx, bits_to_string(slice)); | |
374 | self.each_bit(slice, f) | |
970d7e83 LB |
375 | } |
376 | ||
c34b1796 AL |
377 | pub fn each_gen_bit<F>(&self, id: ast::NodeId, mut f: F) -> bool where |
378 | F: FnMut(usize) -> bool, | |
1a4d82fc | 379 | { |
970d7e83 | 380 | //! Iterates through each bit in the gen set for `id`. |
1a4d82fc JJ |
381 | if !self.has_bitset_for_nodeid(id) { |
382 | return true; | |
383 | } | |
970d7e83 | 384 | |
1a4d82fc JJ |
385 | if self.bits_per_id == 0 { |
386 | // Skip the surprisingly common degenerate case. (Note | |
387 | // compute_id_range requires self.words_per_id > 0.) | |
970d7e83 LB |
388 | return true; |
389 | } | |
1a4d82fc | 390 | |
c34b1796 AL |
391 | let indices = get_cfg_indices(id, &self.nodeid_to_index); |
392 | for &cfgidx in indices { | |
393 | let (start, end) = self.compute_id_range(cfgidx); | |
394 | let gens = &self.gens[start.. end]; | |
395 | debug!("{} each_gen_bit(id={}, gens={})", | |
396 | self.analysis_name, id, bits_to_string(gens)); | |
397 | if !self.each_bit(gens, |i| f(i)) { | |
398 | return false; | |
399 | } | |
400 | } | |
401 | return true; | |
970d7e83 LB |
402 | } |
403 | ||
c34b1796 AL |
404 | fn each_bit<F>(&self, words: &[usize], mut f: F) -> bool where |
405 | F: FnMut(usize) -> bool, | |
1a4d82fc | 406 | { |
970d7e83 | 407 | //! Helper for iterating over the bits in a bit set. |
1a4d82fc JJ |
408 | //! Returns false on the first call to `f` that returns false; |
409 | //! if all calls to `f` return true, then returns true. | |
970d7e83 | 410 | |
1a4d82fc | 411 | for (word_index, &word) in words.iter().enumerate() { |
970d7e83 | 412 | if word != 0 { |
9346a6ac | 413 | let base_index = word_index * usize::BITS; |
85aaf69f | 414 | for offset in 0..usize::BITS { |
970d7e83 LB |
415 | let bit = 1 << offset; |
416 | if (word & bit) != 0 { | |
417 | // NB: we round up the total number of bits | |
418 | // that we store in any given bit set so that | |
85aaf69f | 419 | // it is an even multiple of usize::BITS. This |
970d7e83 LB |
420 | // means that there may be some stray bits at |
421 | // the end that do not correspond to any | |
422 | // actual value. So before we callback, check | |
423 | // whether the bit_index is greater than the | |
424 | // actual value the user specified and stop | |
425 | // iterating if so. | |
c34b1796 | 426 | let bit_index = base_index + offset as usize; |
970d7e83 LB |
427 | if bit_index >= self.bits_per_id { |
428 | return true; | |
429 | } else if !f(bit_index) { | |
430 | return false; | |
431 | } | |
432 | } | |
433 | } | |
434 | } | |
435 | } | |
436 | return true; | |
437 | } | |
970d7e83 | 438 | |
1a4d82fc JJ |
439 | pub fn add_kills_from_flow_exits(&mut self, cfg: &cfg::CFG) { |
440 | //! Whenever you have a `break` or `continue` statement, flow | |
441 | //! exits through any number of enclosing scopes on its way to | |
442 | //! the new destination. This function infers the kill bits of | |
443 | //! those control operators based on the kill bits associated | |
444 | //! with those scopes. | |
445 | //! | |
446 | //! This is usually called (if it is called at all), after | |
447 | //! all add_gen and add_kill calls, but before propagate. | |
970d7e83 | 448 | |
1a4d82fc | 449 | debug!("{} add_kills_from_flow_exits", self.analysis_name); |
970d7e83 | 450 | if self.bits_per_id == 0 { |
1a4d82fc JJ |
451 | // Skip the surprisingly common degenerate case. (Note |
452 | // compute_id_range requires self.words_per_id > 0.) | |
970d7e83 LB |
453 | return; |
454 | } | |
1a4d82fc JJ |
455 | cfg.graph.each_edge(|_edge_index, edge| { |
456 | let flow_exit = edge.source(); | |
457 | let (start, end) = self.compute_id_range(flow_exit); | |
9346a6ac | 458 | let mut orig_kills = self.scope_kills[start.. end].to_vec(); |
1a4d82fc JJ |
459 | |
460 | let mut changed = false; | |
85aaf69f | 461 | for &node_id in &edge.data.exiting_scopes { |
c34b1796 | 462 | let opt_cfg_idx = self.nodeid_to_index.get(&node_id); |
1a4d82fc | 463 | match opt_cfg_idx { |
c34b1796 AL |
464 | Some(indices) => { |
465 | for &cfg_idx in indices { | |
466 | let (start, end) = self.compute_id_range(cfg_idx); | |
9346a6ac | 467 | let kills = &self.scope_kills[start.. end]; |
c34b1796 | 468 | if bitwise(&mut orig_kills, kills, &Union) { |
9346a6ac AL |
469 | debug!("scope exits: scope id={} \ |
470 | (node={:?} of {:?}) added killset: {}", | |
471 | node_id, cfg_idx, indices, | |
472 | bits_to_string(kills)); | |
c34b1796 AL |
473 | changed = true; |
474 | } | |
1a4d82fc | 475 | } |
970d7e83 | 476 | } |
1a4d82fc JJ |
477 | None => { |
478 | debug!("{} add_kills_from_flow_exits flow_exit={:?} \ | |
479 | no cfg_idx for exiting_scope={}", | |
480 | self.analysis_name, flow_exit, node_id); | |
970d7e83 LB |
481 | } |
482 | } | |
970d7e83 LB |
483 | } |
484 | ||
1a4d82fc | 485 | if changed { |
9346a6ac | 486 | let bits = &mut self.scope_kills[start.. end]; |
1a4d82fc JJ |
487 | debug!("{} add_kills_from_flow_exits flow_exit={:?} bits={} [before]", |
488 | self.analysis_name, flow_exit, mut_bits_to_string(bits)); | |
85aaf69f | 489 | bits.clone_from_slice(&orig_kills[..]); |
1a4d82fc JJ |
490 | debug!("{} add_kills_from_flow_exits flow_exit={:?} bits={} [after]", |
491 | self.analysis_name, flow_exit, mut_bits_to_string(bits)); | |
970d7e83 | 492 | } |
1a4d82fc JJ |
493 | true |
494 | }); | |
495 | } | |
496 | } | |
970d7e83 | 497 | |
1a4d82fc JJ |
498 | impl<'a, 'tcx, O:DataFlowOperator+Clone+'static> DataFlowContext<'a, 'tcx, O> { |
499 | // ^^^^^^^^^^^^^ only needed for pretty printing | |
e9174d1e | 500 | pub fn propagate(&mut self, cfg: &cfg::CFG, blk: &hir::Block) { |
1a4d82fc | 501 | //! Performs the data flow analysis. |
970d7e83 | 502 | |
1a4d82fc JJ |
503 | if self.bits_per_id == 0 { |
504 | // Optimize the surprisingly common degenerate case. | |
505 | return; | |
970d7e83 LB |
506 | } |
507 | ||
1a4d82fc JJ |
508 | { |
509 | let words_per_id = self.words_per_id; | |
510 | let mut propcx = PropagationContext { | |
511 | dfcx: &mut *self, | |
512 | changed: true | |
513 | }; | |
970d7e83 | 514 | |
c1a9b12d | 515 | let mut temp = vec![0; words_per_id]; |
1a4d82fc JJ |
516 | while propcx.changed { |
517 | propcx.changed = false; | |
85aaf69f SL |
518 | propcx.reset(&mut temp); |
519 | propcx.walk_cfg(cfg, &mut temp); | |
970d7e83 LB |
520 | } |
521 | } | |
970d7e83 | 522 | |
1a4d82fc JJ |
523 | debug!("Dataflow result for {}:", self.analysis_name); |
524 | debug!("{}", { | |
c34b1796 AL |
525 | let mut v = Vec::new(); |
526 | self.pretty_print_to(box &mut v, blk).unwrap(); | |
527 | println!("{}", String::from_utf8(v).unwrap()); | |
1a4d82fc JJ |
528 | "" |
529 | }); | |
970d7e83 LB |
530 | } |
531 | ||
c34b1796 | 532 | fn pretty_print_to<'b>(&self, wr: Box<io::Write + 'b>, |
e9174d1e | 533 | blk: &hir::Block) -> io::Result<()> { |
92a42be0 | 534 | let mut ps = pprust::rust_printer_annotated(wr, self, None); |
1a4d82fc | 535 | try!(ps.cbox(pprust::indent_unit)); |
85aaf69f | 536 | try!(ps.ibox(0)); |
1a4d82fc JJ |
537 | try!(ps.print_block(blk)); |
538 | pp::eof(&mut ps.s) | |
970d7e83 | 539 | } |
1a4d82fc | 540 | } |
970d7e83 | 541 | |
1a4d82fc JJ |
542 | impl<'a, 'b, 'tcx, O:DataFlowOperator> PropagationContext<'a, 'b, 'tcx, O> { |
543 | fn walk_cfg(&mut self, | |
544 | cfg: &cfg::CFG, | |
c34b1796 | 545 | in_out: &mut [usize]) { |
1a4d82fc JJ |
546 | debug!("DataFlowContext::walk_cfg(in_out={}) {}", |
547 | bits_to_string(in_out), self.dfcx.analysis_name); | |
548 | assert!(self.dfcx.bits_per_id > 0); | |
970d7e83 | 549 | |
1a4d82fc JJ |
550 | cfg.graph.each_node(|node_index, node| { |
551 | debug!("DataFlowContext::walk_cfg idx={:?} id={} begin in_out={}", | |
c34b1796 | 552 | node_index, node.data.id(), bits_to_string(in_out)); |
970d7e83 | 553 | |
1a4d82fc | 554 | let (start, end) = self.dfcx.compute_id_range(node_index); |
970d7e83 | 555 | |
1a4d82fc | 556 | // Initialize local bitvector with state on-entry. |
85aaf69f | 557 | in_out.clone_from_slice(&self.dfcx.on_entry[start.. end]); |
970d7e83 | 558 | |
1a4d82fc JJ |
559 | // Compute state on-exit by applying transfer function to |
560 | // state on-entry. | |
561 | self.dfcx.apply_gen_kill(node_index, in_out); | |
970d7e83 | 562 | |
1a4d82fc JJ |
563 | // Propagate state on-exit from node into its successors. |
564 | self.propagate_bits_into_graph_successors_of(in_out, cfg, node_index); | |
565 | true // continue to next node | |
566 | }); | |
970d7e83 LB |
567 | } |
568 | ||
c34b1796 | 569 | fn reset(&mut self, bits: &mut [usize]) { |
85aaf69f SL |
570 | let e = if self.dfcx.oper.initial_value() {usize::MAX} else {0}; |
571 | for b in bits { | |
1a4d82fc JJ |
572 | *b = e; |
573 | } | |
970d7e83 LB |
574 | } |
575 | ||
1a4d82fc | 576 | fn propagate_bits_into_graph_successors_of(&mut self, |
c34b1796 | 577 | pred_bits: &[usize], |
1a4d82fc JJ |
578 | cfg: &cfg::CFG, |
579 | cfgidx: CFGIndex) { | |
d9579d0f | 580 | for (_, edge) in cfg.graph.outgoing_edges(cfgidx) { |
1a4d82fc | 581 | self.propagate_bits_into_entry_set_for(pred_bits, edge); |
d9579d0f | 582 | } |
970d7e83 LB |
583 | } |
584 | ||
1a4d82fc | 585 | fn propagate_bits_into_entry_set_for(&mut self, |
c34b1796 | 586 | pred_bits: &[usize], |
1a4d82fc JJ |
587 | edge: &cfg::CFGEdge) { |
588 | let source = edge.source(); | |
589 | let cfgidx = edge.target(); | |
590 | debug!("{} propagate_bits_into_entry_set_for(pred_bits={}, {:?} to {:?})", | |
591 | self.dfcx.analysis_name, bits_to_string(pred_bits), source, cfgidx); | |
592 | assert!(self.dfcx.bits_per_id > 0); | |
593 | ||
594 | let (start, end) = self.dfcx.compute_id_range(cfgidx); | |
595 | let changed = { | |
596 | // (scoping mutable borrow of self.dfcx.on_entry) | |
85aaf69f | 597 | let on_entry = &mut self.dfcx.on_entry[start.. end]; |
1a4d82fc | 598 | bitwise(on_entry, pred_bits, &self.dfcx.oper) |
970d7e83 LB |
599 | }; |
600 | if changed { | |
1a4d82fc JJ |
601 | debug!("{} changed entry set for {:?} to {}", |
602 | self.dfcx.analysis_name, cfgidx, | |
85aaf69f | 603 | bits_to_string(&self.dfcx.on_entry[start.. end])); |
970d7e83 LB |
604 | self.changed = true; |
605 | } | |
606 | } | |
607 | } | |
608 | ||
c34b1796 | 609 | fn mut_bits_to_string(words: &mut [usize]) -> String { |
1a4d82fc | 610 | bits_to_string(words) |
970d7e83 LB |
611 | } |
612 | ||
c34b1796 | 613 | fn bits_to_string(words: &[usize]) -> String { |
1a4d82fc | 614 | let mut result = String::new(); |
970d7e83 LB |
615 | let mut sep = '['; |
616 | ||
617 | // Note: this is a little endian printout of bytes. | |
618 | ||
85aaf69f | 619 | for &word in words { |
970d7e83 | 620 | let mut v = word; |
85aaf69f | 621 | for _ in 0..usize::BYTES { |
1a4d82fc | 622 | result.push(sep); |
c34b1796 | 623 | result.push_str(&format!("{:02x}", v & 0xFF)); |
970d7e83 LB |
624 | v >>= 8; |
625 | sep = '-'; | |
626 | } | |
627 | } | |
1a4d82fc JJ |
628 | result.push(']'); |
629 | return result | |
970d7e83 LB |
630 | } |
631 | ||
632 | #[inline] | |
c34b1796 AL |
633 | fn bitwise<Op:BitwiseOperator>(out_vec: &mut [usize], |
634 | in_vec: &[usize], | |
1a4d82fc | 635 | op: &Op) -> bool { |
970d7e83 LB |
636 | assert_eq!(out_vec.len(), in_vec.len()); |
637 | let mut changed = false; | |
62682a34 | 638 | for (out_elt, in_elt) in out_vec.iter_mut().zip(in_vec) { |
1a4d82fc JJ |
639 | let old_val = *out_elt; |
640 | let new_val = op.join(old_val, *in_elt); | |
641 | *out_elt = new_val; | |
642 | changed |= old_val != new_val; | |
970d7e83 | 643 | } |
1a4d82fc | 644 | changed |
970d7e83 LB |
645 | } |
646 | ||
c34b1796 | 647 | fn set_bit(words: &mut [usize], bit: usize) -> bool { |
1a4d82fc JJ |
648 | debug!("set_bit: words={} bit={}", |
649 | mut_bits_to_string(words), bit_str(bit)); | |
9346a6ac AL |
650 | let word = bit / usize::BITS; |
651 | let bit_in_word = bit % usize::BITS; | |
970d7e83 | 652 | let bit_mask = 1 << bit_in_word; |
1a4d82fc | 653 | debug!("word={} bit_in_word={} bit_mask={}", word, bit_in_word, word); |
970d7e83 LB |
654 | let oldv = words[word]; |
655 | let newv = oldv | bit_mask; | |
656 | words[word] = newv; | |
657 | oldv != newv | |
658 | } | |
659 | ||
c34b1796 | 660 | fn bit_str(bit: usize) -> String { |
970d7e83 | 661 | let byte = bit >> 8; |
85aaf69f | 662 | let lobits = 1 << (bit & 0xFF); |
1a4d82fc | 663 | format!("[{}:{}-{:02x}]", bit, byte, lobits) |
970d7e83 LB |
664 | } |
665 | ||
1a4d82fc JJ |
666 | struct Union; |
667 | impl BitwiseOperator for Union { | |
c34b1796 | 668 | fn join(&self, a: usize, b: usize) -> usize { a | b } |
1a4d82fc JJ |
669 | } |
670 | struct Subtract; | |
671 | impl BitwiseOperator for Subtract { | |
c34b1796 | 672 | fn join(&self, a: usize, b: usize) -> usize { a & !b } |
970d7e83 | 673 | } |