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.
13 * A module for propagating forward dataflow information. The analysis
14 * assumes that the items to be propagated can be represented as bits
15 * and thus uses bitvectors. Your job is simply to specify the so-called
16 * GEN and KILL bits for each expression.
21 use middle::cfg::CFGIndex;
26 use syntax::ast_util::IdRange;
28 use syntax::print::{pp, pprust};
29 use util::nodemap::NodeMap;
32 pub enum EntryOrExit { Entry, Exit }
35 pub struct DataFlowContext<'a, 'tcx: 'a, O> {
36 tcx: &'a ty::ctxt<'tcx>,
38 /// a name for the analysis using this dataflow instance
39 analysis_name: &'static str,
41 /// the data flow operator
44 /// number of bits to propagate per id
47 /// number of words we will use to store bits_per_id.
48 /// equal to bits_per_id/uint::BITS rounded up.
51 // mapping from node to cfg node index
52 // FIXME (#6298): Shouldn't this go with CFG?
53 nodeid_to_index: NodeMap<CFGIndex>,
55 // Bit sets per cfg node. The following three fields (`gens`, `kills`,
56 // and `on_entry`) all have the same structure. For each id in
57 // `id_range`, there is a range of words equal to `words_per_id`.
58 // So, to access the bits for any given id, you take a slice of
59 // the full vector (see the method `compute_id_range()`).
61 /// bits generated as we exit the cfg node. Updated by `add_gen()`.
64 /// bits killed as we exit the cfg node. Updated by `add_kill()`.
67 /// bits that are valid on entry to the cfg node. Updated by
72 pub trait BitwiseOperator {
73 /// Joins two predecessor bits together, typically either `|` or `&`
74 fn join(&self, succ: uint, pred: uint) -> uint;
77 /// Parameterization for the precise form of data flow that is used.
78 pub trait DataFlowOperator : BitwiseOperator {
79 /// Specifies the initial value for each bit in the `on_entry` set
80 fn initial_value(&self) -> bool;
83 struct PropagationContext<'a, 'b: 'a, 'tcx: 'b, O: 'a> {
84 dfcx: &'a mut DataFlowContext<'b, 'tcx, O>,
88 fn to_cfgidx_or_die(id: ast::NodeId, index: &NodeMap<CFGIndex>) -> CFGIndex {
89 let opt_cfgindex = index.find(&id).map(|&i|i);
90 opt_cfgindex.unwrap_or_else(|| {
91 fail!("nodeid_to_index does not have entry for NodeId {}", id);
95 impl<'a, 'tcx, O:DataFlowOperator> DataFlowContext<'a, 'tcx, O> {
96 fn has_bitset_for_nodeid(&self, n: ast::NodeId) -> bool {
97 assert!(n != ast::DUMMY_NODE_ID);
98 self.nodeid_to_index.contains_key(&n)
102 impl<'a, 'tcx, O:DataFlowOperator> pprust::PpAnn for DataFlowContext<'a, 'tcx, O> {
104 ps: &mut pprust::State,
105 node: pprust::AnnNode) -> io::IoResult<()> {
106 let id = match node {
107 pprust::NodeIdent(_) | pprust::NodeName(_) => 0,
108 pprust::NodeExpr(expr) => expr.id,
109 pprust::NodeBlock(blk) => blk.id,
110 pprust::NodeItem(_) => 0,
111 pprust::NodePat(pat) => pat.id
114 if self.has_bitset_for_nodeid(id) {
115 assert!(self.bits_per_id > 0);
116 let cfgidx = to_cfgidx_or_die(id, &self.nodeid_to_index);
117 let (start, end) = self.compute_id_range(cfgidx);
118 let on_entry = self.on_entry.slice(start, end);
119 let entry_str = bits_to_string(on_entry);
121 let gens = self.gens.slice(start, end);
122 let gens_str = if gens.iter().any(|&u| u != 0) {
123 format!(" gen: {}", bits_to_string(gens))
128 let kills = self.kills.slice(start, end);
129 let kills_str = if kills.iter().any(|&u| u != 0) {
130 format!(" kill: {}", bits_to_string(kills))
135 try!(ps.synth_comment(format!("id {}: {}{}{}", id, entry_str,
136 gens_str, kills_str)));
137 try!(pp::space(&mut ps.s));
143 fn build_nodeid_to_index(decl: Option<&ast::FnDecl>,
144 cfg: &cfg::CFG) -> NodeMap<CFGIndex> {
145 let mut index = NodeMap::new();
147 // FIXME (#6298): Would it be better to fold formals from decl
148 // into cfg itself? i.e. introduce a fn-based flow-graph in
149 // addition to the current block-based flow-graph, rather than
150 // have to put traversals like this here?
153 Some(decl) => add_entries_from_fn_decl(&mut index, decl, cfg.entry)
156 cfg.graph.each_node(|node_idx, node| {
157 if node.data.id != ast::DUMMY_NODE_ID {
158 index.insert(node.data.id, node_idx);
165 fn add_entries_from_fn_decl(index: &mut NodeMap<CFGIndex>,
168 //! add mappings from the ast nodes for the formal bindings to
169 //! the entry-node in the graph.
172 index: &'a mut NodeMap<CFGIndex>,
174 let mut formals = Formals { entry: entry, index: index };
175 visit::walk_fn_decl(&mut formals, decl);
176 impl<'a, 'v> visit::Visitor<'v> for Formals<'a> {
177 fn visit_pat(&mut self, p: &ast::Pat) {
178 self.index.insert(p.id, self.entry);
179 visit::walk_pat(self, p)
185 impl<'a, 'tcx, O:DataFlowOperator> DataFlowContext<'a, 'tcx, O> {
186 pub fn new(tcx: &'a ty::ctxt<'tcx>,
187 analysis_name: &'static str,
188 decl: Option<&ast::FnDecl>,
192 bits_per_id: uint) -> DataFlowContext<'a, 'tcx, O> {
193 let words_per_id = (bits_per_id + uint::BITS - 1) / uint::BITS;
194 let num_nodes = cfg.graph.all_nodes().len();
196 debug!("DataFlowContext::new(analysis_name: {:s}, id_range={:?}, \
197 bits_per_id={:?}, words_per_id={:?}) \
199 analysis_name, id_range, bits_per_id, words_per_id,
202 let entry = if oper.initial_value() { uint::MAX } else {0};
204 let gens = Vec::from_elem(num_nodes * words_per_id, 0);
205 let kills = Vec::from_elem(num_nodes * words_per_id, 0);
206 let on_entry = Vec::from_elem(num_nodes * words_per_id, entry);
208 let nodeid_to_index = build_nodeid_to_index(decl, cfg);
212 analysis_name: analysis_name,
213 words_per_id: words_per_id,
214 nodeid_to_index: nodeid_to_index,
215 bits_per_id: bits_per_id,
223 pub fn add_gen(&mut self, id: ast::NodeId, bit: uint) {
224 //! Indicates that `id` generates `bit`
225 debug!("{:s} add_gen(id={:?}, bit={:?})",
226 self.analysis_name, id, bit);
227 assert!(self.nodeid_to_index.contains_key(&id));
228 assert!(self.bits_per_id > 0);
230 let cfgidx = to_cfgidx_or_die(id, &self.nodeid_to_index);
231 let (start, end) = self.compute_id_range(cfgidx);
232 let gens = self.gens.mut_slice(start, end);
236 pub fn add_kill(&mut self, id: ast::NodeId, bit: uint) {
237 //! Indicates that `id` kills `bit`
238 debug!("{:s} add_kill(id={:?}, bit={:?})",
239 self.analysis_name, id, bit);
240 assert!(self.nodeid_to_index.contains_key(&id));
241 assert!(self.bits_per_id > 0);
243 let cfgidx = to_cfgidx_or_die(id, &self.nodeid_to_index);
244 let (start, end) = self.compute_id_range(cfgidx);
245 let kills = self.kills.mut_slice(start, end);
249 fn apply_gen_kill(&self, cfgidx: CFGIndex, bits: &mut [uint]) {
250 //! Applies the gen and kill sets for `cfgidx` to `bits`
251 debug!("{:s} apply_gen_kill(cfgidx={}, bits={}) [before]",
252 self.analysis_name, cfgidx, mut_bits_to_string(bits));
253 assert!(self.bits_per_id > 0);
255 let (start, end) = self.compute_id_range(cfgidx);
256 let gens = self.gens.slice(start, end);
257 bitwise(bits, gens, &Union);
258 let kills = self.kills.slice(start, end);
259 bitwise(bits, kills, &Subtract);
261 debug!("{:s} apply_gen_kill(cfgidx={}, bits={}) [after]",
262 self.analysis_name, cfgidx, mut_bits_to_string(bits));
265 fn compute_id_range(&self, cfgidx: CFGIndex) -> (uint, uint) {
266 let n = cfgidx.node_id();
267 let start = n * self.words_per_id;
268 let end = start + self.words_per_id;
270 assert!(start < self.gens.len());
271 assert!(end <= self.gens.len());
272 assert!(self.gens.len() == self.kills.len());
273 assert!(self.gens.len() == self.on_entry.len());
279 pub fn each_bit_on_entry(&self,
283 //! Iterates through each bit that is set on entry to `id`.
284 //! Only useful after `propagate()` has been called.
285 if !self.has_bitset_for_nodeid(id) {
288 let cfgidx = to_cfgidx_or_die(id, &self.nodeid_to_index);
289 self.each_bit_for_node(Entry, cfgidx, f)
292 pub fn each_bit_for_node(&self,
297 //! Iterates through each bit that is set on entry/exit to `cfgidx`.
298 //! Only useful after `propagate()` has been called.
300 if self.bits_per_id == 0 {
301 // Skip the surprisingly common degenerate case. (Note
302 // compute_id_range requires self.words_per_id > 0.)
306 let (start, end) = self.compute_id_range(cfgidx);
307 let on_entry = self.on_entry.slice(start, end);
309 let slice = match e {
312 let mut t = on_entry.to_vec();
313 self.apply_gen_kill(cfgidx, t.as_mut_slice());
318 debug!("{:s} each_bit_for_node({}, cfgidx={}) bits={}",
319 self.analysis_name, e, cfgidx, bits_to_string(slice));
320 self.each_bit(slice, f)
323 pub fn each_gen_bit(&self, id: ast::NodeId, f: |uint| -> bool)
325 //! Iterates through each bit in the gen set for `id`.
326 if !self.has_bitset_for_nodeid(id) {
330 if self.bits_per_id == 0 {
331 // Skip the surprisingly common degenerate case. (Note
332 // compute_id_range requires self.words_per_id > 0.)
336 let cfgidx = to_cfgidx_or_die(id, &self.nodeid_to_index);
337 let (start, end) = self.compute_id_range(cfgidx);
338 let gens = self.gens.slice(start, end);
339 debug!("{:s} each_gen_bit(id={:?}, gens={})",
340 self.analysis_name, id, bits_to_string(gens));
341 self.each_bit(gens, f)
344 fn each_bit(&self, words: &[uint], f: |uint| -> bool) -> bool {
345 //! Helper for iterating over the bits in a bit set.
346 //! Returns false on the first call to `f` that returns false;
347 //! if all calls to `f` return true, then returns true.
349 for (word_index, &word) in words.iter().enumerate() {
351 let base_index = word_index * uint::BITS;
352 for offset in range(0u, uint::BITS) {
353 let bit = 1 << offset;
354 if (word & bit) != 0 {
355 // NB: we round up the total number of bits
356 // that we store in any given bit set so that
357 // it is an even multiple of uint::BITS. This
358 // means that there may be some stray bits at
359 // the end that do not correspond to any
360 // actual value. So before we callback, check
361 // whether the bit_index is greater than the
362 // actual value the user specified and stop
364 let bit_index = base_index + offset;
365 if bit_index >= self.bits_per_id {
367 } else if !f(bit_index) {
377 pub fn add_kills_from_flow_exits(&mut self, cfg: &cfg::CFG) {
378 //! Whenever you have a `break` or `continue` statement, flow
379 //! exits through any number of enclosing scopes on its way to
380 //! the new destination. This function infers the kill bits of
381 //! those control operators based on the kill bits associated
382 //! with those scopes.
384 //! This is usually called (if it is called at all), after
385 //! all add_gen and add_kill calls, but before propagate.
387 debug!("{:s} add_kills_from_flow_exits", self.analysis_name);
388 if self.bits_per_id == 0 {
389 // Skip the surprisingly common degenerate case. (Note
390 // compute_id_range requires self.words_per_id > 0.)
393 cfg.graph.each_edge(|_edge_index, edge| {
394 let flow_exit = edge.source();
395 let (start, end) = self.compute_id_range(flow_exit);
396 let mut orig_kills = self.kills.slice(start, end).to_vec();
398 let mut changed = false;
399 for &node_id in edge.data.exiting_scopes.iter() {
400 let opt_cfg_idx = self.nodeid_to_index.find(&node_id).map(|&i|i);
403 let (start, end) = self.compute_id_range(cfg_idx);
404 let kills = self.kills.slice(start, end);
405 if bitwise(orig_kills.as_mut_slice(), kills, &Union) {
410 debug!("{:s} add_kills_from_flow_exits flow_exit={} \
411 no cfg_idx for exiting_scope={:?}",
412 self.analysis_name, flow_exit, node_id);
418 let bits = self.kills.mut_slice(start, end);
419 debug!("{:s} add_kills_from_flow_exits flow_exit={} bits={} [before]",
420 self.analysis_name, flow_exit, mut_bits_to_string(bits));
421 bits.copy_from(orig_kills.as_slice());
422 debug!("{:s} add_kills_from_flow_exits flow_exit={} bits={} [after]",
423 self.analysis_name, flow_exit, mut_bits_to_string(bits));
430 impl<'a, 'tcx, O:DataFlowOperator+Clone+'static> DataFlowContext<'a, 'tcx, O> {
431 // ^^^^^^^^^^^^^ only needed for pretty printing
432 pub fn propagate(&mut self, cfg: &cfg::CFG, blk: &ast::Block) {
433 //! Performs the data flow analysis.
435 if self.bits_per_id == 0 {
436 // Optimize the surprisingly common degenerate case.
441 let words_per_id = self.words_per_id;
442 let mut propcx = PropagationContext {
447 let mut temp = Vec::from_elem(words_per_id, 0u);
448 while propcx.changed {
449 propcx.changed = false;
450 propcx.reset(temp.as_mut_slice());
451 propcx.walk_cfg(cfg, temp.as_mut_slice());
455 debug!("Dataflow result for {:s}:", self.analysis_name);
457 self.pretty_print_to(box io::stderr(), blk).unwrap();
462 fn pretty_print_to(&self, wr: Box<io::Writer+'static>,
463 blk: &ast::Block) -> io::IoResult<()> {
464 let mut ps = pprust::rust_printer_annotated(wr, self);
465 try!(ps.cbox(pprust::indent_unit));
467 try!(ps.print_block(blk));
472 impl<'a, 'b, 'tcx, O:DataFlowOperator> PropagationContext<'a, 'b, 'tcx, O> {
473 fn walk_cfg(&mut self,
475 in_out: &mut [uint]) {
476 debug!("DataFlowContext::walk_cfg(in_out={}) {:s}",
477 bits_to_string(in_out), self.dfcx.analysis_name);
478 assert!(self.dfcx.bits_per_id > 0);
480 cfg.graph.each_node(|node_index, node| {
481 debug!("DataFlowContext::walk_cfg idx={} id={} begin in_out={}",
482 node_index, node.data.id, bits_to_string(in_out));
484 let (start, end) = self.dfcx.compute_id_range(node_index);
486 // Initialize local bitvector with state on-entry.
487 in_out.copy_from(self.dfcx.on_entry.slice(start, end));
489 // Compute state on-exit by applying transfer function to
491 self.dfcx.apply_gen_kill(node_index, in_out);
493 // Propagate state on-exit from node into its successors.
494 self.propagate_bits_into_graph_successors_of(in_out, cfg, node_index);
495 true // continue to next node
499 fn reset(&mut self, bits: &mut [uint]) {
500 let e = if self.dfcx.oper.initial_value() {uint::MAX} else {0};
501 for b in bits.mut_iter() {
506 fn propagate_bits_into_graph_successors_of(&mut self,
510 cfg.graph.each_outgoing_edge(cfgidx, |_e_idx, edge| {
511 self.propagate_bits_into_entry_set_for(pred_bits, edge);
516 fn propagate_bits_into_entry_set_for(&mut self,
518 edge: &cfg::CFGEdge) {
519 let source = edge.source();
520 let cfgidx = edge.target();
521 debug!("{:s} propagate_bits_into_entry_set_for(pred_bits={}, {} to {})",
522 self.dfcx.analysis_name, bits_to_string(pred_bits), source, cfgidx);
523 assert!(self.dfcx.bits_per_id > 0);
525 let (start, end) = self.dfcx.compute_id_range(cfgidx);
527 // (scoping mutable borrow of self.dfcx.on_entry)
528 let on_entry = self.dfcx.on_entry.mut_slice(start, end);
529 bitwise(on_entry, pred_bits, &self.dfcx.oper)
532 debug!("{:s} changed entry set for {:?} to {}",
533 self.dfcx.analysis_name, cfgidx,
534 bits_to_string(self.dfcx.on_entry.slice(start, end)));
540 fn mut_bits_to_string(words: &mut [uint]) -> String {
541 bits_to_string(words)
544 fn bits_to_string(words: &[uint]) -> String {
545 let mut result = String::new();
548 // Note: this is a little endian printout of bytes.
550 for &word in words.iter() {
552 for _ in range(0u, uint::BYTES) {
553 result.push_char(sep);
554 result.push_str(format!("{:02x}", v & 0xFF).as_slice());
559 result.push_char(']');
564 fn bitwise<Op:BitwiseOperator>(out_vec: &mut [uint],
567 assert_eq!(out_vec.len(), in_vec.len());
568 let mut changed = false;
569 for (out_elt, in_elt) in out_vec.mut_iter().zip(in_vec.iter()) {
570 let old_val = *out_elt;
571 let new_val = op.join(old_val, *in_elt);
573 changed |= old_val != new_val;
578 fn set_bit(words: &mut [uint], bit: uint) -> bool {
579 debug!("set_bit: words={} bit={}",
580 mut_bits_to_string(words), bit_str(bit));
581 let word = bit / uint::BITS;
582 let bit_in_word = bit % uint::BITS;
583 let bit_mask = 1 << bit_in_word;
584 debug!("word={} bit_in_word={} bit_mask={}", word, bit_in_word, word);
585 let oldv = words[word];
586 let newv = oldv | bit_mask;
591 fn bit_str(bit: uint) -> String {
593 let lobits = 1u << (bit & 0xFF);
594 format!("[{}:{}-{:02x}]", bit, byte, lobits)
598 impl BitwiseOperator for Union {
599 fn join(&self, a: uint, b: uint) -> uint { a | b }
602 impl BitwiseOperator for Subtract {
603 fn join(&self, a: uint, b: uint) -> uint { a & !b }