]> git.proxmox.com Git - rustc.git/blame - src/librustc/middle/dataflow.rs
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / src / librustc / middle / dataflow.rs
CommitLineData
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
54a0048b
SL
17use cfg;
18use cfg::CFGIndex;
19use ty::TyCtxt;
c34b1796 20use std::io;
9cc50fc6 21use std::mem;
85aaf69f 22use std::usize;
970d7e83 23use syntax::ast;
e9174d1e 24use syntax::print::pp;
b039eaaf 25use syntax::print::pprust::PrintState;
1a4d82fc 26use util::nodemap::NodeMap;
54a0048b
SL
27use hir;
28use hir::intravisit::{self, IdRange};
29use hir::print as pprust;
e9174d1e 30
1a4d82fc 31
c34b1796 32#[derive(Copy, Clone, Debug)]
1a4d82fc
JJ
33pub enum EntryOrExit {
34 Entry,
35 Exit,
36}
970d7e83 37
1a4d82fc
JJ
38#[derive(Clone)]
39pub struct DataFlowContext<'a, 'tcx: 'a, O> {
54a0048b 40 tcx: &'a TyCtxt<'tcx>,
1a4d82fc
JJ
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
82pub 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 88pub 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
93struct PropagationContext<'a, 'b: 'a, 'tcx: 'b, O: 'a> {
94 dfcx: &'a mut DataFlowContext<'b, 'tcx, O>,
95 changed: bool
96}
970d7e83 97
c34b1796
AL
98fn 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
103impl<'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
110impl<'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
54a0048b 154 ps.synth_comment(
9346a6ac 155 format!("id {}: {}{}{}{}", id, entry_str,
54a0048b
SL
156 gens_str, action_kills_str, scope_kills_str))?;
157 pp::space(&mut ps.s)?;
1a4d82fc
JJ
158 }
159 Ok(())
160 }
970d7e83
LB
161}
162
e9174d1e 163fn 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)]
210pub 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 224impl<'a, 'tcx, O:DataFlowOperator> DataFlowContext<'a, 'tcx, O> {
54a0048b 225 pub fn new(tcx: &'a TyCtxt<'tcx>,
1a4d82fc 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> {
9cc50fc6
SL
232 let usize_bits = mem::size_of::<usize>() * 8;
233 let words_per_id = (bits_per_id + usize_bits - 1) / usize_bits;
1a4d82fc
JJ
234 let num_nodes = cfg.graph.all_nodes().len();
235
236 debug!("DataFlowContext::new(analysis_name: {}, id_range={:?}, \
237 bits_per_id={}, words_per_id={}) \
238 num_nodes: {}",
239 analysis_name, id_range, bits_per_id, words_per_id,
240 num_nodes);
970d7e83 241
85aaf69f 242 let entry = if oper.initial_value() { usize::MAX } else {0};
970d7e83 243
c1a9b12d
SL
244 let zeroes = vec![0; num_nodes * words_per_id];
245 let gens = zeroes.clone();
246 let kills1 = zeroes.clone();
247 let kills2 = zeroes;
248 let on_entry = vec![entry; num_nodes * words_per_id];
1a4d82fc
JJ
249
250 let nodeid_to_index = build_nodeid_to_index(decl, cfg);
970d7e83
LB
251
252 DataFlowContext {
253 tcx: tcx,
1a4d82fc 254 analysis_name: analysis_name,
970d7e83 255 words_per_id: words_per_id,
1a4d82fc 256 nodeid_to_index: nodeid_to_index,
970d7e83
LB
257 bits_per_id: bits_per_id,
258 oper: oper,
259 gens: gens,
9346a6ac
AL
260 action_kills: kills1,
261 scope_kills: kills2,
970d7e83
LB
262 on_entry: on_entry
263 }
264 }
265
c34b1796 266 pub fn add_gen(&mut self, id: ast::NodeId, bit: usize) {
970d7e83 267 //! Indicates that `id` generates `bit`
1a4d82fc
JJ
268 debug!("{} add_gen(id={}, bit={})",
269 self.analysis_name, id, bit);
270 assert!(self.nodeid_to_index.contains_key(&id));
271 assert!(self.bits_per_id > 0);
970d7e83 272
c34b1796
AL
273 let indices = get_cfg_indices(id, &self.nodeid_to_index);
274 for &cfgidx in indices {
275 let (start, end) = self.compute_id_range(cfgidx);
276 let gens = &mut self.gens[start.. end];
277 set_bit(gens, bit);
278 }
970d7e83
LB
279 }
280
9346a6ac 281 pub fn add_kill(&mut self, kind: KillFrom, id: ast::NodeId, bit: usize) {
970d7e83 282 //! Indicates that `id` kills `bit`
1a4d82fc
JJ
283 debug!("{} add_kill(id={}, bit={})",
284 self.analysis_name, id, bit);
285 assert!(self.nodeid_to_index.contains_key(&id));
286 assert!(self.bits_per_id > 0);
970d7e83 287
c34b1796
AL
288 let indices = get_cfg_indices(id, &self.nodeid_to_index);
289 for &cfgidx in indices {
290 let (start, end) = self.compute_id_range(cfgidx);
9346a6ac
AL
291 let kills = match kind {
292 KillFrom::Execution => &mut self.action_kills[start.. end],
293 KillFrom::ScopeEnd => &mut self.scope_kills[start.. end],
294 };
c34b1796
AL
295 set_bit(kills, bit);
296 }
970d7e83
LB
297 }
298
c34b1796 299 fn apply_gen_kill(&self, cfgidx: CFGIndex, bits: &mut [usize]) {
1a4d82fc
JJ
300 //! Applies the gen and kill sets for `cfgidx` to `bits`
301 debug!("{} apply_gen_kill(cfgidx={:?}, bits={}) [before]",
302 self.analysis_name, cfgidx, mut_bits_to_string(bits));
303 assert!(self.bits_per_id > 0);
970d7e83 304
1a4d82fc 305 let (start, end) = self.compute_id_range(cfgidx);
85aaf69f 306 let gens = &self.gens[start.. end];
1a4d82fc 307 bitwise(bits, gens, &Union);
9346a6ac
AL
308 let kills = &self.action_kills[start.. end];
309 bitwise(bits, kills, &Subtract);
310 let kills = &self.scope_kills[start.. end];
1a4d82fc 311 bitwise(bits, kills, &Subtract);
970d7e83 312
1a4d82fc
JJ
313 debug!("{} apply_gen_kill(cfgidx={:?}, bits={}) [after]",
314 self.analysis_name, cfgidx, mut_bits_to_string(bits));
970d7e83
LB
315 }
316
c34b1796 317 fn compute_id_range(&self, cfgidx: CFGIndex) -> (usize, usize) {
1a4d82fc 318 let n = cfgidx.node_id();
970d7e83
LB
319 let start = n * self.words_per_id;
320 let end = start + self.words_per_id;
970d7e83
LB
321
322 assert!(start < self.gens.len());
323 assert!(end <= self.gens.len());
9346a6ac
AL
324 assert!(self.gens.len() == self.action_kills.len());
325 assert!(self.gens.len() == self.scope_kills.len());
970d7e83
LB
326 assert!(self.gens.len() == self.on_entry.len());
327
328 (start, end)
329 }
330
331
c34b1796
AL
332 pub fn each_bit_on_entry<F>(&self, id: ast::NodeId, mut f: F) -> bool where
333 F: FnMut(usize) -> bool,
1a4d82fc 334 {
970d7e83
LB
335 //! Iterates through each bit that is set on entry to `id`.
336 //! Only useful after `propagate()` has been called.
1a4d82fc 337 if !self.has_bitset_for_nodeid(id) {
970d7e83
LB
338 return true;
339 }
c34b1796
AL
340 let indices = get_cfg_indices(id, &self.nodeid_to_index);
341 for &cfgidx in indices {
92a42be0 342 if !self.each_bit_for_node(EntryOrExit::Entry, cfgidx, |i| f(i)) {
c34b1796
AL
343 return false;
344 }
345 }
346 return true;
970d7e83
LB
347 }
348
1a4d82fc 349 pub fn each_bit_for_node<F>(&self, e: EntryOrExit, cfgidx: CFGIndex, f: F) -> bool where
c34b1796 350 F: FnMut(usize) -> bool,
1a4d82fc
JJ
351 {
352 //! Iterates through each bit that is set on entry/exit to `cfgidx`.
970d7e83
LB
353 //! Only useful after `propagate()` has been called.
354
1a4d82fc
JJ
355 if self.bits_per_id == 0 {
356 // Skip the surprisingly common degenerate case. (Note
357 // compute_id_range requires self.words_per_id > 0.)
358 return true;
359 }
360
361 let (start, end) = self.compute_id_range(cfgidx);
85aaf69f 362 let on_entry = &self.on_entry[start.. end];
1a4d82fc
JJ
363 let temp_bits;
364 let slice = match e {
92a42be0
SL
365 EntryOrExit::Entry => on_entry,
366 EntryOrExit::Exit => {
1a4d82fc 367 let mut t = on_entry.to_vec();
85aaf69f 368 self.apply_gen_kill(cfgidx, &mut t);
1a4d82fc 369 temp_bits = t;
85aaf69f 370 &temp_bits[..]
1a4d82fc
JJ
371 }
372 };
373 debug!("{} each_bit_for_node({:?}, cfgidx={:?}) bits={}",
374 self.analysis_name, e, cfgidx, bits_to_string(slice));
375 self.each_bit(slice, f)
970d7e83
LB
376 }
377
c34b1796
AL
378 pub fn each_gen_bit<F>(&self, id: ast::NodeId, mut f: F) -> bool where
379 F: FnMut(usize) -> bool,
1a4d82fc 380 {
970d7e83 381 //! Iterates through each bit in the gen set for `id`.
1a4d82fc
JJ
382 if !self.has_bitset_for_nodeid(id) {
383 return true;
384 }
970d7e83 385
1a4d82fc
JJ
386 if self.bits_per_id == 0 {
387 // Skip the surprisingly common degenerate case. (Note
388 // compute_id_range requires self.words_per_id > 0.)
970d7e83
LB
389 return true;
390 }
1a4d82fc 391
c34b1796
AL
392 let indices = get_cfg_indices(id, &self.nodeid_to_index);
393 for &cfgidx in indices {
394 let (start, end) = self.compute_id_range(cfgidx);
395 let gens = &self.gens[start.. end];
396 debug!("{} each_gen_bit(id={}, gens={})",
397 self.analysis_name, id, bits_to_string(gens));
398 if !self.each_bit(gens, |i| f(i)) {
399 return false;
400 }
401 }
402 return true;
970d7e83
LB
403 }
404
c34b1796
AL
405 fn each_bit<F>(&self, words: &[usize], mut f: F) -> bool where
406 F: FnMut(usize) -> bool,
1a4d82fc 407 {
970d7e83 408 //! Helper for iterating over the bits in a bit set.
1a4d82fc
JJ
409 //! Returns false on the first call to `f` that returns false;
410 //! if all calls to `f` return true, then returns true.
970d7e83 411
9cc50fc6 412 let usize_bits = mem::size_of::<usize>() * 8;
1a4d82fc 413 for (word_index, &word) in words.iter().enumerate() {
970d7e83 414 if word != 0 {
9cc50fc6
SL
415 let base_index = word_index * usize_bits;
416 for offset in 0..usize_bits {
970d7e83
LB
417 let bit = 1 << offset;
418 if (word & bit) != 0 {
419 // NB: we round up the total number of bits
420 // that we store in any given bit set so that
85aaf69f 421 // it is an even multiple of usize::BITS. This
970d7e83
LB
422 // means that there may be some stray bits at
423 // the end that do not correspond to any
424 // actual value. So before we callback, check
425 // whether the bit_index is greater than the
426 // actual value the user specified and stop
427 // iterating if so.
c34b1796 428 let bit_index = base_index + offset as usize;
970d7e83
LB
429 if bit_index >= self.bits_per_id {
430 return true;
431 } else if !f(bit_index) {
432 return false;
433 }
434 }
435 }
436 }
437 }
438 return true;
439 }
970d7e83 440
1a4d82fc
JJ
441 pub fn add_kills_from_flow_exits(&mut self, cfg: &cfg::CFG) {
442 //! Whenever you have a `break` or `continue` statement, flow
443 //! exits through any number of enclosing scopes on its way to
444 //! the new destination. This function infers the kill bits of
445 //! those control operators based on the kill bits associated
446 //! with those scopes.
447 //!
448 //! This is usually called (if it is called at all), after
449 //! all add_gen and add_kill calls, but before propagate.
970d7e83 450
1a4d82fc 451 debug!("{} add_kills_from_flow_exits", self.analysis_name);
970d7e83 452 if self.bits_per_id == 0 {
1a4d82fc
JJ
453 // Skip the surprisingly common degenerate case. (Note
454 // compute_id_range requires self.words_per_id > 0.)
970d7e83
LB
455 return;
456 }
1a4d82fc
JJ
457 cfg.graph.each_edge(|_edge_index, edge| {
458 let flow_exit = edge.source();
459 let (start, end) = self.compute_id_range(flow_exit);
9346a6ac 460 let mut orig_kills = self.scope_kills[start.. end].to_vec();
1a4d82fc
JJ
461
462 let mut changed = false;
85aaf69f 463 for &node_id in &edge.data.exiting_scopes {
c34b1796 464 let opt_cfg_idx = self.nodeid_to_index.get(&node_id);
1a4d82fc 465 match opt_cfg_idx {
c34b1796
AL
466 Some(indices) => {
467 for &cfg_idx in indices {
468 let (start, end) = self.compute_id_range(cfg_idx);
9346a6ac 469 let kills = &self.scope_kills[start.. end];
c34b1796 470 if bitwise(&mut orig_kills, kills, &Union) {
9346a6ac
AL
471 debug!("scope exits: scope id={} \
472 (node={:?} of {:?}) added killset: {}",
473 node_id, cfg_idx, indices,
474 bits_to_string(kills));
c34b1796
AL
475 changed = true;
476 }
1a4d82fc 477 }
970d7e83 478 }
1a4d82fc
JJ
479 None => {
480 debug!("{} add_kills_from_flow_exits flow_exit={:?} \
481 no cfg_idx for exiting_scope={}",
482 self.analysis_name, flow_exit, node_id);
970d7e83
LB
483 }
484 }
970d7e83
LB
485 }
486
1a4d82fc 487 if changed {
9346a6ac 488 let bits = &mut self.scope_kills[start.. end];
1a4d82fc
JJ
489 debug!("{} add_kills_from_flow_exits flow_exit={:?} bits={} [before]",
490 self.analysis_name, flow_exit, mut_bits_to_string(bits));
7453a54e 491 bits.copy_from_slice(&orig_kills[..]);
1a4d82fc
JJ
492 debug!("{} add_kills_from_flow_exits flow_exit={:?} bits={} [after]",
493 self.analysis_name, flow_exit, mut_bits_to_string(bits));
970d7e83 494 }
1a4d82fc
JJ
495 true
496 });
497 }
498}
970d7e83 499
1a4d82fc
JJ
500impl<'a, 'tcx, O:DataFlowOperator+Clone+'static> DataFlowContext<'a, 'tcx, O> {
501// ^^^^^^^^^^^^^ only needed for pretty printing
e9174d1e 502 pub fn propagate(&mut self, cfg: &cfg::CFG, blk: &hir::Block) {
1a4d82fc 503 //! Performs the data flow analysis.
970d7e83 504
1a4d82fc
JJ
505 if self.bits_per_id == 0 {
506 // Optimize the surprisingly common degenerate case.
507 return;
970d7e83
LB
508 }
509
1a4d82fc
JJ
510 {
511 let words_per_id = self.words_per_id;
512 let mut propcx = PropagationContext {
513 dfcx: &mut *self,
514 changed: true
515 };
970d7e83 516
c1a9b12d 517 let mut temp = vec![0; words_per_id];
1a4d82fc
JJ
518 while propcx.changed {
519 propcx.changed = false;
85aaf69f
SL
520 propcx.reset(&mut temp);
521 propcx.walk_cfg(cfg, &mut temp);
970d7e83
LB
522 }
523 }
970d7e83 524
1a4d82fc
JJ
525 debug!("Dataflow result for {}:", self.analysis_name);
526 debug!("{}", {
c34b1796
AL
527 let mut v = Vec::new();
528 self.pretty_print_to(box &mut v, blk).unwrap();
7453a54e 529 String::from_utf8(v).unwrap()
1a4d82fc 530 });
970d7e83
LB
531 }
532
c34b1796 533 fn pretty_print_to<'b>(&self, wr: Box<io::Write + 'b>,
e9174d1e 534 blk: &hir::Block) -> io::Result<()> {
92a42be0 535 let mut ps = pprust::rust_printer_annotated(wr, self, None);
54a0048b
SL
536 ps.cbox(pprust::indent_unit)?;
537 ps.ibox(0)?;
538 ps.print_block(blk)?;
1a4d82fc 539 pp::eof(&mut ps.s)
970d7e83 540 }
1a4d82fc 541}
970d7e83 542
1a4d82fc
JJ
543impl<'a, 'b, 'tcx, O:DataFlowOperator> PropagationContext<'a, 'b, 'tcx, O> {
544 fn walk_cfg(&mut self,
545 cfg: &cfg::CFG,
c34b1796 546 in_out: &mut [usize]) {
1a4d82fc
JJ
547 debug!("DataFlowContext::walk_cfg(in_out={}) {}",
548 bits_to_string(in_out), self.dfcx.analysis_name);
549 assert!(self.dfcx.bits_per_id > 0);
970d7e83 550
1a4d82fc
JJ
551 cfg.graph.each_node(|node_index, node| {
552 debug!("DataFlowContext::walk_cfg idx={:?} id={} begin in_out={}",
c34b1796 553 node_index, node.data.id(), bits_to_string(in_out));
970d7e83 554
1a4d82fc 555 let (start, end) = self.dfcx.compute_id_range(node_index);
970d7e83 556
1a4d82fc 557 // Initialize local bitvector with state on-entry.
7453a54e 558 in_out.copy_from_slice(&self.dfcx.on_entry[start.. end]);
970d7e83 559
1a4d82fc
JJ
560 // Compute state on-exit by applying transfer function to
561 // state on-entry.
562 self.dfcx.apply_gen_kill(node_index, in_out);
970d7e83 563
1a4d82fc
JJ
564 // Propagate state on-exit from node into its successors.
565 self.propagate_bits_into_graph_successors_of(in_out, cfg, node_index);
566 true // continue to next node
567 });
970d7e83
LB
568 }
569
c34b1796 570 fn reset(&mut self, bits: &mut [usize]) {
85aaf69f
SL
571 let e = if self.dfcx.oper.initial_value() {usize::MAX} else {0};
572 for b in bits {
1a4d82fc
JJ
573 *b = e;
574 }
970d7e83
LB
575 }
576
1a4d82fc 577 fn propagate_bits_into_graph_successors_of(&mut self,
c34b1796 578 pred_bits: &[usize],
1a4d82fc
JJ
579 cfg: &cfg::CFG,
580 cfgidx: CFGIndex) {
d9579d0f 581 for (_, edge) in cfg.graph.outgoing_edges(cfgidx) {
1a4d82fc 582 self.propagate_bits_into_entry_set_for(pred_bits, edge);
d9579d0f 583 }
970d7e83
LB
584 }
585
1a4d82fc 586 fn propagate_bits_into_entry_set_for(&mut self,
c34b1796 587 pred_bits: &[usize],
1a4d82fc
JJ
588 edge: &cfg::CFGEdge) {
589 let source = edge.source();
590 let cfgidx = edge.target();
591 debug!("{} propagate_bits_into_entry_set_for(pred_bits={}, {:?} to {:?})",
592 self.dfcx.analysis_name, bits_to_string(pred_bits), source, cfgidx);
593 assert!(self.dfcx.bits_per_id > 0);
594
595 let (start, end) = self.dfcx.compute_id_range(cfgidx);
596 let changed = {
597 // (scoping mutable borrow of self.dfcx.on_entry)
85aaf69f 598 let on_entry = &mut self.dfcx.on_entry[start.. end];
1a4d82fc 599 bitwise(on_entry, pred_bits, &self.dfcx.oper)
970d7e83
LB
600 };
601 if changed {
1a4d82fc
JJ
602 debug!("{} changed entry set for {:?} to {}",
603 self.dfcx.analysis_name, cfgidx,
85aaf69f 604 bits_to_string(&self.dfcx.on_entry[start.. end]));
970d7e83
LB
605 self.changed = true;
606 }
607 }
608}
609
c34b1796 610fn mut_bits_to_string(words: &mut [usize]) -> String {
1a4d82fc 611 bits_to_string(words)
970d7e83
LB
612}
613
c34b1796 614fn bits_to_string(words: &[usize]) -> String {
1a4d82fc 615 let mut result = String::new();
970d7e83
LB
616 let mut sep = '[';
617
618 // Note: this is a little endian printout of bytes.
619
85aaf69f 620 for &word in words {
970d7e83 621 let mut v = word;
9cc50fc6 622 for _ in 0..mem::size_of::<usize>() {
1a4d82fc 623 result.push(sep);
c34b1796 624 result.push_str(&format!("{:02x}", v & 0xFF));
970d7e83
LB
625 v >>= 8;
626 sep = '-';
627 }
628 }
1a4d82fc
JJ
629 result.push(']');
630 return result
970d7e83
LB
631}
632
633#[inline]
c34b1796
AL
634fn bitwise<Op:BitwiseOperator>(out_vec: &mut [usize],
635 in_vec: &[usize],
1a4d82fc 636 op: &Op) -> bool {
970d7e83
LB
637 assert_eq!(out_vec.len(), in_vec.len());
638 let mut changed = false;
62682a34 639 for (out_elt, in_elt) in out_vec.iter_mut().zip(in_vec) {
1a4d82fc
JJ
640 let old_val = *out_elt;
641 let new_val = op.join(old_val, *in_elt);
642 *out_elt = new_val;
643 changed |= old_val != new_val;
970d7e83 644 }
1a4d82fc 645 changed
970d7e83
LB
646}
647
c34b1796 648fn set_bit(words: &mut [usize], bit: usize) -> bool {
1a4d82fc
JJ
649 debug!("set_bit: words={} bit={}",
650 mut_bits_to_string(words), bit_str(bit));
9cc50fc6
SL
651 let usize_bits = mem::size_of::<usize>() * 8;
652 let word = bit / usize_bits;
653 let bit_in_word = bit % usize_bits;
970d7e83 654 let bit_mask = 1 << bit_in_word;
54a0048b 655 debug!("word={} bit_in_word={} bit_mask={}", word, bit_in_word, bit_mask);
970d7e83
LB
656 let oldv = words[word];
657 let newv = oldv | bit_mask;
658 words[word] = newv;
659 oldv != newv
660}
661
c34b1796 662fn bit_str(bit: usize) -> String {
970d7e83 663 let byte = bit >> 8;
85aaf69f 664 let lobits = 1 << (bit & 0xFF);
1a4d82fc 665 format!("[{}:{}-{:02x}]", bit, byte, lobits)
970d7e83
LB
666}
667
1a4d82fc
JJ
668struct Union;
669impl BitwiseOperator for Union {
c34b1796 670 fn join(&self, a: usize, b: usize) -> usize { a | b }
1a4d82fc
JJ
671}
672struct Subtract;
673impl BitwiseOperator for Subtract {
c34b1796 674 fn join(&self, a: usize, b: usize) -> usize { a & !b }
970d7e83 675}