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