1 // Copyright 2012-2014 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.
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.
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.
18 use middle::cfg::CFGIndex;
23 use syntax::ast_util::IdRange;
24 use syntax::print::pp;
25 use syntax::print::pprust::PrintState;
26 use util::nodemap::NodeMap;
28 use rustc_front::intravisit;
29 use rustc_front::print::pprust;
32 #[derive(Copy, Clone, Debug)]
33 pub enum EntryOrExit {
39 pub struct DataFlowContext<'a, 'tcx: 'a, O> {
40 tcx: &'a ty::ctxt<'tcx>,
42 /// a name for the analysis using this dataflow instance
43 analysis_name: &'static str,
45 /// the data flow operator
48 /// number of bits to propagate per id
51 /// number of words we will use to store bits_per_id.
52 /// equal to bits_per_id/usize::BITS rounded up.
55 // mapping from node to cfg node index
56 // FIXME (#6298): Shouldn't this go with CFG?
57 nodeid_to_index: NodeMap<Vec<CFGIndex>>,
59 // Bit sets per cfg node. The following three fields (`gens`, `kills`,
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()`).
65 /// bits generated as we exit the cfg node. Updated by `add_gen()`.
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>,
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>,
77 /// bits that are valid on entry to the cfg node. Updated by
82 pub trait BitwiseOperator {
83 /// Joins two predecessor bits together, typically either `|` or `&`
84 fn join(&self, succ: usize, pred: usize) -> usize;
87 /// Parameterization for the precise form of data flow that is used.
88 pub trait DataFlowOperator : BitwiseOperator {
89 /// Specifies the initial value for each bit in the `on_entry` set
90 fn initial_value(&self) -> bool;
93 struct PropagationContext<'a, 'b: 'a, 'tcx: 'b, O: 'a> {
94 dfcx: &'a mut DataFlowContext<'b, 'tcx, O>,
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(&[])
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)
110 impl<'a, 'tcx, O:DataFlowOperator> pprust::PpAnn for DataFlowContext<'a, 'tcx, O> {
112 ps: &mut pprust::State,
113 node: pprust::AnnNode) -> io::Result<()> {
114 let id = match node {
115 pprust::NodeName(_) => 0,
116 pprust::NodeExpr(expr) => expr.id,
117 pprust::NodeBlock(blk) => blk.id,
118 pprust::NodeItem(_) | pprust::NodeSubItem(_) => 0,
119 pprust::NodePat(pat) => pat.id
122 if !self.has_bitset_for_nodeid(id) {
126 assert!(self.bits_per_id > 0);
127 let indices = get_cfg_indices(id, &self.nodeid_to_index);
128 for &cfgidx in indices {
129 let (start, end) = self.compute_id_range(cfgidx);
130 let on_entry = &self.on_entry[start.. end];
131 let entry_str = bits_to_string(on_entry);
133 let gens = &self.gens[start.. end];
134 let gens_str = if gens.iter().any(|&u| u != 0) {
135 format!(" gen: {}", bits_to_string(gens))
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))
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))
154 try!(ps.synth_comment(
155 format!("id {}: {}{}{}{}", id, entry_str,
156 gens_str, action_kills_str, scope_kills_str)));
157 try!(pp::space(&mut ps.s));
163 fn build_nodeid_to_index(decl: Option<&hir::FnDecl>,
164 cfg: &cfg::CFG) -> NodeMap<Vec<CFGIndex>> {
165 let mut index = NodeMap();
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?
173 Some(decl) => add_entries_from_fn_decl(&mut index, decl, cfg.entry)
176 cfg.graph.each_node(|node_idx, node| {
177 if let cfg::CFGNodeData::AST(id) = node.data {
178 index.entry(id).or_insert(vec![]).push(node_idx);
185 fn add_entries_from_fn_decl(index: &mut NodeMap<Vec<CFGIndex>>,
188 //! add mappings from the ast nodes for the formal bindings to
189 //! the entry-node in the graph.
192 index: &'a mut NodeMap<Vec<CFGIndex>>,
194 let mut formals = Formals { entry: entry, index: index };
195 intravisit::walk_fn_decl(&mut formals, decl);
196 impl<'a, 'v> intravisit::Visitor<'v> for Formals<'a> {
197 fn visit_pat(&mut self, p: &hir::Pat) {
198 self.index.entry(p.id).or_insert(vec![]).push(self.entry);
199 intravisit::walk_pat(self, p)
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)]
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
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.
224 impl<'a, 'tcx, O:DataFlowOperator> DataFlowContext<'a, 'tcx, O> {
225 pub fn new(tcx: &'a ty::ctxt<'tcx>,
226 analysis_name: &'static str,
227 decl: Option<&hir::FnDecl>,
231 bits_per_id: usize) -> DataFlowContext<'a, 'tcx, O> {
232 let words_per_id = (bits_per_id + usize::BITS - 1) / usize::BITS;
233 let num_nodes = cfg.graph.all_nodes().len();
235 debug!("DataFlowContext::new(analysis_name: {}, id_range={:?}, \
236 bits_per_id={}, words_per_id={}) \
238 analysis_name, id_range, bits_per_id, words_per_id,
241 let entry = if oper.initial_value() { usize::MAX } else {0};
243 let zeroes = vec![0; num_nodes * words_per_id];
244 let gens = zeroes.clone();
245 let kills1 = zeroes.clone();
247 let on_entry = vec![entry; num_nodes * words_per_id];
249 let nodeid_to_index = build_nodeid_to_index(decl, cfg);
253 analysis_name: analysis_name,
254 words_per_id: words_per_id,
255 nodeid_to_index: nodeid_to_index,
256 bits_per_id: bits_per_id,
259 action_kills: kills1,
265 pub fn add_gen(&mut self, id: ast::NodeId, bit: usize) {
266 //! Indicates that `id` generates `bit`
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);
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];
280 pub fn add_kill(&mut self, kind: KillFrom, id: ast::NodeId, bit: usize) {
281 //! Indicates that `id` kills `bit`
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);
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);
290 let kills = match kind {
291 KillFrom::Execution => &mut self.action_kills[start.. end],
292 KillFrom::ScopeEnd => &mut self.scope_kills[start.. end],
298 fn apply_gen_kill(&self, cfgidx: CFGIndex, bits: &mut [usize]) {
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);
304 let (start, end) = self.compute_id_range(cfgidx);
305 let gens = &self.gens[start.. end];
306 bitwise(bits, gens, &Union);
307 let kills = &self.action_kills[start.. end];
308 bitwise(bits, kills, &Subtract);
309 let kills = &self.scope_kills[start.. end];
310 bitwise(bits, kills, &Subtract);
312 debug!("{} apply_gen_kill(cfgidx={:?}, bits={}) [after]",
313 self.analysis_name, cfgidx, mut_bits_to_string(bits));
316 fn compute_id_range(&self, cfgidx: CFGIndex) -> (usize, usize) {
317 let n = cfgidx.node_id();
318 let start = n * self.words_per_id;
319 let end = start + self.words_per_id;
321 assert!(start < self.gens.len());
322 assert!(end <= self.gens.len());
323 assert!(self.gens.len() == self.action_kills.len());
324 assert!(self.gens.len() == self.scope_kills.len());
325 assert!(self.gens.len() == self.on_entry.len());
331 pub fn each_bit_on_entry<F>(&self, id: ast::NodeId, mut f: F) -> bool where
332 F: FnMut(usize) -> bool,
334 //! Iterates through each bit that is set on entry to `id`.
335 //! Only useful after `propagate()` has been called.
336 if !self.has_bitset_for_nodeid(id) {
339 let indices = get_cfg_indices(id, &self.nodeid_to_index);
340 for &cfgidx in indices {
341 if !self.each_bit_for_node(EntryOrExit::Entry, cfgidx, |i| f(i)) {
348 pub fn each_bit_for_node<F>(&self, e: EntryOrExit, cfgidx: CFGIndex, f: F) -> bool where
349 F: FnMut(usize) -> bool,
351 //! Iterates through each bit that is set on entry/exit to `cfgidx`.
352 //! Only useful after `propagate()` has been called.
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.)
360 let (start, end) = self.compute_id_range(cfgidx);
361 let on_entry = &self.on_entry[start.. end];
363 let slice = match e {
364 EntryOrExit::Entry => on_entry,
365 EntryOrExit::Exit => {
366 let mut t = on_entry.to_vec();
367 self.apply_gen_kill(cfgidx, &mut t);
372 debug!("{} each_bit_for_node({:?}, cfgidx={:?}) bits={}",
373 self.analysis_name, e, cfgidx, bits_to_string(slice));
374 self.each_bit(slice, f)
377 pub fn each_gen_bit<F>(&self, id: ast::NodeId, mut f: F) -> bool where
378 F: FnMut(usize) -> bool,
380 //! Iterates through each bit in the gen set for `id`.
381 if !self.has_bitset_for_nodeid(id) {
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.)
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)) {
404 fn each_bit<F>(&self, words: &[usize], mut f: F) -> bool where
405 F: FnMut(usize) -> bool,
407 //! Helper for iterating over the bits in a bit set.
408 //! Returns false on the first call to `f` that returns false;
409 //! if all calls to `f` return true, then returns true.
411 for (word_index, &word) in words.iter().enumerate() {
413 let base_index = word_index * usize::BITS;
414 for offset in 0..usize::BITS {
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
419 // it is an even multiple of usize::BITS. This
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
426 let bit_index = base_index + offset as usize;
427 if bit_index >= self.bits_per_id {
429 } else if !f(bit_index) {
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.
446 //! This is usually called (if it is called at all), after
447 //! all add_gen and add_kill calls, but before propagate.
449 debug!("{} add_kills_from_flow_exits", self.analysis_name);
450 if self.bits_per_id == 0 {
451 // Skip the surprisingly common degenerate case. (Note
452 // compute_id_range requires self.words_per_id > 0.)
455 cfg.graph.each_edge(|_edge_index, edge| {
456 let flow_exit = edge.source();
457 let (start, end) = self.compute_id_range(flow_exit);
458 let mut orig_kills = self.scope_kills[start.. end].to_vec();
460 let mut changed = false;
461 for &node_id in &edge.data.exiting_scopes {
462 let opt_cfg_idx = self.nodeid_to_index.get(&node_id);
465 for &cfg_idx in indices {
466 let (start, end) = self.compute_id_range(cfg_idx);
467 let kills = &self.scope_kills[start.. end];
468 if bitwise(&mut orig_kills, kills, &Union) {
469 debug!("scope exits: scope id={} \
470 (node={:?} of {:?}) added killset: {}",
471 node_id, cfg_idx, indices,
472 bits_to_string(kills));
478 debug!("{} add_kills_from_flow_exits flow_exit={:?} \
479 no cfg_idx for exiting_scope={}",
480 self.analysis_name, flow_exit, node_id);
486 let bits = &mut self.scope_kills[start.. end];
487 debug!("{} add_kills_from_flow_exits flow_exit={:?} bits={} [before]",
488 self.analysis_name, flow_exit, mut_bits_to_string(bits));
489 bits.clone_from_slice(&orig_kills[..]);
490 debug!("{} add_kills_from_flow_exits flow_exit={:?} bits={} [after]",
491 self.analysis_name, flow_exit, mut_bits_to_string(bits));
498 impl<'a, 'tcx, O:DataFlowOperator+Clone+'static> DataFlowContext<'a, 'tcx, O> {
499 // ^^^^^^^^^^^^^ only needed for pretty printing
500 pub fn propagate(&mut self, cfg: &cfg::CFG, blk: &hir::Block) {
501 //! Performs the data flow analysis.
503 if self.bits_per_id == 0 {
504 // Optimize the surprisingly common degenerate case.
509 let words_per_id = self.words_per_id;
510 let mut propcx = PropagationContext {
515 let mut temp = vec![0; words_per_id];
516 while propcx.changed {
517 propcx.changed = false;
518 propcx.reset(&mut temp);
519 propcx.walk_cfg(cfg, &mut temp);
523 debug!("Dataflow result for {}:", self.analysis_name);
525 let mut v = Vec::new();
526 self.pretty_print_to(box &mut v, blk).unwrap();
527 println!("{}", String::from_utf8(v).unwrap());
532 fn pretty_print_to<'b>(&self, wr: Box<io::Write + 'b>,
533 blk: &hir::Block) -> io::Result<()> {
534 let mut ps = pprust::rust_printer_annotated(wr, self, None);
535 try!(ps.cbox(pprust::indent_unit));
537 try!(ps.print_block(blk));
542 impl<'a, 'b, 'tcx, O:DataFlowOperator> PropagationContext<'a, 'b, 'tcx, O> {
543 fn walk_cfg(&mut self,
545 in_out: &mut [usize]) {
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);
550 cfg.graph.each_node(|node_index, node| {
551 debug!("DataFlowContext::walk_cfg idx={:?} id={} begin in_out={}",
552 node_index, node.data.id(), bits_to_string(in_out));
554 let (start, end) = self.dfcx.compute_id_range(node_index);
556 // Initialize local bitvector with state on-entry.
557 in_out.clone_from_slice(&self.dfcx.on_entry[start.. end]);
559 // Compute state on-exit by applying transfer function to
561 self.dfcx.apply_gen_kill(node_index, in_out);
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
569 fn reset(&mut self, bits: &mut [usize]) {
570 let e = if self.dfcx.oper.initial_value() {usize::MAX} else {0};
576 fn propagate_bits_into_graph_successors_of(&mut self,
580 for (_, edge) in cfg.graph.outgoing_edges(cfgidx) {
581 self.propagate_bits_into_entry_set_for(pred_bits, edge);
585 fn propagate_bits_into_entry_set_for(&mut self,
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);
594 let (start, end) = self.dfcx.compute_id_range(cfgidx);
596 // (scoping mutable borrow of self.dfcx.on_entry)
597 let on_entry = &mut self.dfcx.on_entry[start.. end];
598 bitwise(on_entry, pred_bits, &self.dfcx.oper)
601 debug!("{} changed entry set for {:?} to {}",
602 self.dfcx.analysis_name, cfgidx,
603 bits_to_string(&self.dfcx.on_entry[start.. end]));
609 fn mut_bits_to_string(words: &mut [usize]) -> String {
610 bits_to_string(words)
613 fn bits_to_string(words: &[usize]) -> String {
614 let mut result = String::new();
617 // Note: this is a little endian printout of bytes.
621 for _ in 0..usize::BYTES {
623 result.push_str(&format!("{:02x}", v & 0xFF));
633 fn bitwise<Op:BitwiseOperator>(out_vec: &mut [usize],
636 assert_eq!(out_vec.len(), in_vec.len());
637 let mut changed = false;
638 for (out_elt, in_elt) in out_vec.iter_mut().zip(in_vec) {
639 let old_val = *out_elt;
640 let new_val = op.join(old_val, *in_elt);
642 changed |= old_val != new_val;
647 fn set_bit(words: &mut [usize], bit: usize) -> bool {
648 debug!("set_bit: words={} bit={}",
649 mut_bits_to_string(words), bit_str(bit));
650 let word = bit / usize::BITS;
651 let bit_in_word = bit % usize::BITS;
652 let bit_mask = 1 << bit_in_word;
653 debug!("word={} bit_in_word={} bit_mask={}", word, bit_in_word, word);
654 let oldv = words[word];
655 let newv = oldv | bit_mask;
660 fn bit_str(bit: usize) -> String {
662 let lobits = 1 << (bit & 0xFF);
663 format!("[{}:{}-{:02x}]", bit, byte, lobits)
667 impl BitwiseOperator for Union {
668 fn join(&self, a: usize, b: usize) -> usize { a | b }
671 impl BitwiseOperator for Subtract {
672 fn join(&self, a: usize, b: usize) -> usize { a & !b }