1 //! A module for propagating forward dataflow information. The analysis
2 //! assumes that the items to be propagated can be represented as bits
3 //! and thus uses bitvectors. Your job is simply to specify the so-called
4 //! GEN and KILL bits for each expression.
7 use rustc::cfg::CFGIndex;
12 use syntax::print::pprust::PrintState;
14 use rustc_data_structures::graph::implementation::OUTGOING;
16 use rustc::util::nodemap::FxHashMap;
18 use rustc::hir::intravisit;
19 use rustc::hir::print as pprust;
22 #[derive(Copy, Clone, Debug)]
23 pub enum EntryOrExit {
29 pub struct DataFlowContext<'a, 'tcx: 'a, O> {
30 tcx: TyCtxt<'a, 'tcx, 'tcx>,
32 /// a name for the analysis using this dataflow instance
33 analysis_name: &'static str,
35 /// the data flow operator
38 /// number of bits to propagate per id
41 /// number of words we will use to store bits_per_id.
42 /// equal to bits_per_id/usize::BITS rounded up.
45 // mapping from node to cfg node index
46 // FIXME (#6298): Shouldn't this go with CFG?
47 local_id_to_index: FxHashMap<hir::ItemLocalId, Vec<CFGIndex>>,
49 // Bit sets per cfg node. The following three fields (`gens`, `kills`,
50 // and `on_entry`) all have the same structure. For each id in
51 // `id_range`, there is a range of words equal to `words_per_id`.
52 // So, to access the bits for any given id, you take a slice of
53 // the full vector (see the method `compute_id_range()`).
55 /// bits generated as we exit the cfg node. Updated by `add_gen()`.
58 /// bits killed as we exit the cfg node, or non-locally jump over
59 /// it. Updated by `add_kill(KillFrom::ScopeEnd)`.
60 scope_kills: Vec<usize>,
62 /// bits killed as we exit the cfg node directly; if it is jumped
63 /// over, e.g., via `break`, the kills are not reflected in the
64 /// jump's effects. Updated by `add_kill(KillFrom::Execution)`.
65 action_kills: Vec<usize>,
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: usize, pred: usize) -> usize;
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 get_cfg_indices<'a>(id: hir::ItemLocalId,
89 index: &'a FxHashMap<hir::ItemLocalId, Vec<CFGIndex>>)
91 index.get(&id).map_or(&[], |v| &v[..])
94 impl<'a, 'tcx, O:DataFlowOperator> DataFlowContext<'a, 'tcx, O> {
95 fn has_bitset_for_local_id(&self, n: hir::ItemLocalId) -> bool {
96 assert!(n != hir::DUMMY_ITEM_LOCAL_ID);
97 self.local_id_to_index.contains_key(&n)
101 impl<'a, 'tcx, O:DataFlowOperator> pprust::PpAnn for DataFlowContext<'a, 'tcx, O> {
102 fn nested(&self, state: &mut pprust::State, nested: pprust::Nested) -> io::Result<()> {
103 pprust::PpAnn::nested(self.tcx.hir(), state, nested)
106 ps: &mut pprust::State,
107 node: pprust::AnnNode) -> io::Result<()> {
108 let id = match node {
109 pprust::AnnNode::Name(_) => return Ok(()),
110 pprust::AnnNode::Expr(expr) => expr.hir_id.local_id,
111 pprust::AnnNode::Block(blk) => blk.hir_id.local_id,
112 pprust::AnnNode::Item(_) |
113 pprust::AnnNode::SubItem(_) => return Ok(()),
114 pprust::AnnNode::Pat(pat) => pat.hir_id.local_id
117 if !self.has_bitset_for_local_id(id) {
121 assert!(self.bits_per_id > 0);
122 let indices = get_cfg_indices(id, &self.local_id_to_index);
123 for &cfgidx in indices {
124 let (start, end) = self.compute_id_range(cfgidx);
125 let on_entry = &self.on_entry[start.. end];
126 let entry_str = bits_to_string(on_entry);
128 let gens = &self.gens[start.. end];
129 let gens_str = if gens.iter().any(|&u| u != 0) {
130 format!(" gen: {}", bits_to_string(gens))
135 let action_kills = &self.action_kills[start .. end];
136 let action_kills_str = if action_kills.iter().any(|&u| u != 0) {
137 format!(" action_kill: {}", bits_to_string(action_kills))
142 let scope_kills = &self.scope_kills[start .. end];
143 let scope_kills_str = if scope_kills.iter().any(|&u| u != 0) {
144 format!(" scope_kill: {}", bits_to_string(scope_kills))
150 format!("id {}: {}{}{}{}", id.as_usize(), entry_str,
151 gens_str, action_kills_str, scope_kills_str))?;
158 fn build_local_id_to_index(body: Option<&hir::Body>,
160 -> FxHashMap<hir::ItemLocalId, Vec<CFGIndex>> {
161 let mut index = FxHashMap::default();
163 // FIXME(#15020) Would it be better to fold formals from decl
164 // into cfg itself? i.e., introduce a fn-based flow-graph in
165 // addition to the current block-based flow-graph, rather than
166 // have to put traversals like this here?
167 if let Some(body) = body {
168 add_entries_from_fn_body(&mut index, body, cfg.entry);
171 cfg.graph.each_node(|node_idx, node| {
172 if let cfg::CFGNodeData::AST(id) = node.data {
173 index.entry(id).or_default().push(node_idx);
180 /// Add mappings from the ast nodes for the formal bindings to
181 /// the entry-node in the graph.
182 fn add_entries_from_fn_body(index: &mut FxHashMap<hir::ItemLocalId, Vec<CFGIndex>>,
185 use rustc::hir::intravisit::Visitor;
189 index: &'a mut FxHashMap<hir::ItemLocalId, Vec<CFGIndex>>,
191 let mut formals = Formals { entry: entry, index: index };
192 for arg in &body.arguments {
193 formals.visit_pat(&arg.pat);
195 impl<'a, 'v> Visitor<'v> for Formals<'a> {
196 fn nested_visit_map<'this>(&'this mut self) -> intravisit::NestedVisitorMap<'this, 'v> {
197 intravisit::NestedVisitorMap::None
200 fn visit_pat(&mut self, p: &hir::Pat) {
201 self.index.entry(p.hir_id.local_id).or_default().push(self.entry);
202 intravisit::walk_pat(self, p)
208 /// Flag used by `add_kill` to indicate whether the provided kill
209 /// takes effect only when control flows directly through the node in
210 /// question, or if the kill's effect is associated with any
211 /// control-flow directly through or indirectly over the node.
212 #[derive(Copy, Clone, PartialEq, Debug)]
214 /// A `ScopeEnd` kill is one that takes effect when any control
215 /// flow goes over the node. A kill associated with the end of the
216 /// scope of a variable declaration `let x;` is an example of a
220 /// An `Execution` kill is one that takes effect only when control
221 /// flow goes through the node to completion. A kill associated
222 /// with an assignment statement `x = expr;` is an example of an
223 /// `Execution` kill.
227 impl<'a, 'tcx, O:DataFlowOperator> DataFlowContext<'a, 'tcx, O> {
228 pub fn new(tcx: TyCtxt<'a, 'tcx, 'tcx>,
229 analysis_name: &'static str,
230 body: Option<&hir::Body>,
233 bits_per_id: usize) -> DataFlowContext<'a, 'tcx, O> {
234 let usize_bits = mem::size_of::<usize>() * 8;
235 let words_per_id = (bits_per_id + usize_bits - 1) / usize_bits;
236 let num_nodes = cfg.graph.all_nodes().len();
238 debug!("DataFlowContext::new(analysis_name: {}, \
239 bits_per_id={}, words_per_id={}) \
241 analysis_name, bits_per_id, words_per_id,
244 let entry = if oper.initial_value() { usize::MAX } else {0};
246 let zeroes = vec![0; num_nodes * words_per_id];
247 let gens = zeroes.clone();
248 let kills1 = zeroes.clone();
250 let on_entry = vec![entry; num_nodes * words_per_id];
252 let local_id_to_index = build_local_id_to_index(body, cfg);
262 action_kills: kills1,
268 pub fn add_gen(&mut self, id: hir::ItemLocalId, bit: usize) {
269 //! Indicates that `id` generates `bit`
270 debug!("{} add_gen(id={:?}, bit={})",
271 self.analysis_name, id, bit);
272 assert!(self.local_id_to_index.contains_key(&id));
273 assert!(self.bits_per_id > 0);
275 let indices = get_cfg_indices(id, &self.local_id_to_index);
276 for &cfgidx in indices {
277 let (start, end) = self.compute_id_range(cfgidx);
278 let gens = &mut self.gens[start.. end];
283 pub fn add_kill(&mut self, kind: KillFrom, id: hir::ItemLocalId, bit: usize) {
284 //! Indicates that `id` kills `bit`
285 debug!("{} add_kill(id={:?}, bit={})",
286 self.analysis_name, id, bit);
287 assert!(self.local_id_to_index.contains_key(&id));
288 assert!(self.bits_per_id > 0);
290 let indices = get_cfg_indices(id, &self.local_id_to_index);
291 for &cfgidx in indices {
292 let (start, end) = self.compute_id_range(cfgidx);
293 let kills = match kind {
294 KillFrom::Execution => &mut self.action_kills[start.. end],
295 KillFrom::ScopeEnd => &mut self.scope_kills[start.. end],
301 fn apply_gen_kill(&self, cfgidx: CFGIndex, bits: &mut [usize]) {
302 //! Applies the gen and kill sets for `cfgidx` to `bits`
303 debug!("{} apply_gen_kill(cfgidx={:?}, bits={}) [before]",
304 self.analysis_name, cfgidx, mut_bits_to_string(bits));
305 assert!(self.bits_per_id > 0);
307 let (start, end) = self.compute_id_range(cfgidx);
308 let gens = &self.gens[start.. end];
309 bitwise(bits, gens, &Union);
310 let kills = &self.action_kills[start.. end];
311 bitwise(bits, kills, &Subtract);
312 let kills = &self.scope_kills[start.. end];
313 bitwise(bits, kills, &Subtract);
315 debug!("{} apply_gen_kill(cfgidx={:?}, bits={}) [after]",
316 self.analysis_name, cfgidx, mut_bits_to_string(bits));
319 fn compute_id_range(&self, cfgidx: CFGIndex) -> (usize, usize) {
320 let n = cfgidx.node_id();
321 let start = n * self.words_per_id;
322 let end = start + self.words_per_id;
324 assert!(start < self.gens.len());
325 assert!(end <= self.gens.len());
326 assert!(self.gens.len() == self.action_kills.len());
327 assert!(self.gens.len() == self.scope_kills.len());
328 assert!(self.gens.len() == self.on_entry.len());
334 pub fn each_bit_on_entry<F>(&self, id: hir::ItemLocalId, mut f: F) -> bool where
335 F: FnMut(usize) -> bool,
337 //! Iterates through each bit that is set on entry to `id`.
338 //! Only useful after `propagate()` has been called.
339 if !self.has_bitset_for_local_id(id) {
342 let indices = get_cfg_indices(id, &self.local_id_to_index);
343 for &cfgidx in indices {
344 if !self.each_bit_for_node(EntryOrExit::Entry, cfgidx, |i| f(i)) {
351 pub fn each_bit_for_node<F>(&self, e: EntryOrExit, cfgidx: CFGIndex, f: F) -> bool where
352 F: FnMut(usize) -> bool,
354 //! Iterates through each bit that is set on entry/exit to `cfgidx`.
355 //! Only useful after `propagate()` has been called.
357 if self.bits_per_id == 0 {
358 // Skip the surprisingly common degenerate case. (Note
359 // compute_id_range requires self.words_per_id > 0.)
363 let (start, end) = self.compute_id_range(cfgidx);
364 let on_entry = &self.on_entry[start.. end];
366 let slice = match e {
367 EntryOrExit::Entry => on_entry,
368 EntryOrExit::Exit => {
369 let mut t = on_entry.to_vec();
370 self.apply_gen_kill(cfgidx, &mut t);
375 debug!("{} each_bit_for_node({:?}, cfgidx={:?}) bits={}",
376 self.analysis_name, e, cfgidx, bits_to_string(slice));
377 self.each_bit(slice, f)
380 pub fn each_gen_bit<F>(&self, id: hir::ItemLocalId, mut f: F) -> bool where
381 F: FnMut(usize) -> bool,
383 //! Iterates through each bit in the gen set for `id`.
384 if !self.has_bitset_for_local_id(id) {
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.)
394 let indices = get_cfg_indices(id, &self.local_id_to_index);
395 for &cfgidx in indices {
396 let (start, end) = self.compute_id_range(cfgidx);
397 let gens = &self.gens[start.. end];
398 debug!("{} each_gen_bit(id={:?}, gens={})",
399 self.analysis_name, id, bits_to_string(gens));
400 if !self.each_bit(gens, |i| f(i)) {
407 fn each_bit<F>(&self, words: &[usize], mut f: F) -> bool where
408 F: FnMut(usize) -> bool,
410 //! Helper for iterating over the bits in a bit set.
411 //! Returns false on the first call to `f` that returns false;
412 //! if all calls to `f` return true, then returns true.
414 let usize_bits = mem::size_of::<usize>() * 8;
415 for (word_index, &word) in words.iter().enumerate() {
417 let base_index = word_index * usize_bits;
418 for offset in 0..usize_bits {
419 let bit = 1 << offset;
420 if (word & bit) != 0 {
421 // N.B., we round up the total number of bits
422 // that we store in any given bit set so that
423 // it is an even multiple of usize::BITS. This
424 // means that there may be some stray bits at
425 // the end that do not correspond to any
426 // actual value. So before we callback, check
427 // whether the bit_index is greater than the
428 // actual value the user specified and stop
430 let bit_index = base_index + offset as usize;
431 if bit_index >= self.bits_per_id {
433 } else if !f(bit_index) {
443 pub fn add_kills_from_flow_exits(&mut self, cfg: &cfg::CFG) {
444 //! Whenever you have a `break` or `continue` statement, flow
445 //! exits through any number of enclosing scopes on its way to
446 //! the new destination. This function infers the kill bits of
447 //! those control operators based on the kill bits associated
448 //! with those scopes.
450 //! This is usually called (if it is called at all), after
451 //! all add_gen and add_kill calls, but before propagate.
453 debug!("{} add_kills_from_flow_exits", self.analysis_name);
454 if self.bits_per_id == 0 {
455 // Skip the surprisingly common degenerate case. (Note
456 // compute_id_range requires self.words_per_id > 0.)
459 cfg.graph.each_edge(|_edge_index, edge| {
460 let flow_exit = edge.source();
461 let (start, end) = self.compute_id_range(flow_exit);
462 let mut orig_kills = self.scope_kills[start.. end].to_vec();
464 let mut changed = false;
465 for &id in &edge.data.exiting_scopes {
466 let opt_cfg_idx = self.local_id_to_index.get(&id);
469 for &cfg_idx in indices {
470 let (start, end) = self.compute_id_range(cfg_idx);
471 let kills = &self.scope_kills[start.. end];
472 if bitwise(&mut orig_kills, kills, &Union) {
473 debug!("scope exits: scope id={:?} \
474 (node={:?} of {:?}) added killset: {}",
475 id, cfg_idx, indices,
476 bits_to_string(kills));
482 debug!("{} add_kills_from_flow_exits flow_exit={:?} \
483 no cfg_idx for exiting_scope={:?}",
484 self.analysis_name, flow_exit, id);
490 let bits = &mut self.scope_kills[start.. end];
491 debug!("{} add_kills_from_flow_exits flow_exit={:?} bits={} [before]",
492 self.analysis_name, flow_exit, mut_bits_to_string(bits));
493 bits.copy_from_slice(&orig_kills[..]);
494 debug!("{} add_kills_from_flow_exits flow_exit={:?} bits={} [after]",
495 self.analysis_name, flow_exit, mut_bits_to_string(bits));
502 impl<'a, 'tcx, O:DataFlowOperator+Clone+'static> DataFlowContext<'a, 'tcx, O> {
503 // ^^^^^^^^^^^^^ only needed for pretty printing
504 pub fn propagate(&mut self, cfg: &cfg::CFG, body: &hir::Body) {
505 //! Performs the data flow analysis.
507 if self.bits_per_id == 0 {
508 // Optimize the surprisingly common degenerate case.
513 let words_per_id = self.words_per_id;
514 let mut propcx = PropagationContext {
519 let nodes_po = cfg.graph.nodes_in_postorder(OUTGOING, cfg.entry);
520 let mut temp = vec![0; words_per_id];
521 let mut num_passes = 0;
522 while propcx.changed {
524 propcx.changed = false;
525 propcx.reset(&mut temp);
526 propcx.walk_cfg(cfg, &nodes_po, &mut temp);
528 debug!("finished in {} iterations", num_passes);
531 debug!("Dataflow result for {}:", self.analysis_name);
532 debug!("{}", pprust::to_string(self, |s| {
533 s.cbox(pprust::indent_unit)?;
535 s.print_expr(&body.value)
540 impl<'a, 'b, 'tcx, O:DataFlowOperator> PropagationContext<'a, 'b, 'tcx, O> {
541 fn walk_cfg(&mut self,
543 nodes_po: &[CFGIndex],
544 in_out: &mut [usize]) {
545 debug!("DataFlowContext::walk_cfg(in_out={}) {}",
546 bits_to_string(in_out), self.dfcx.analysis_name);
547 assert!(self.dfcx.bits_per_id > 0);
549 // Iterate over nodes in reverse postorder
550 for &node_index in nodes_po.iter().rev() {
551 let node = cfg.graph.node(node_index);
552 debug!("DataFlowContext::walk_cfg idx={:?} id={:?} begin in_out={}",
553 node_index, node.data.id(), bits_to_string(in_out));
555 let (start, end) = self.dfcx.compute_id_range(node_index);
557 // Initialize local bitvector with state on-entry.
558 in_out.copy_from_slice(&self.dfcx.on_entry[start.. end]);
560 // Compute state on-exit by applying transfer function to
562 self.dfcx.apply_gen_kill(node_index, in_out);
564 // Propagate state on-exit from node into its successors.
565 self.propagate_bits_into_graph_successors_of(in_out, cfg, node_index);
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..mem::size_of::<usize>() {
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 usize_bits = mem::size_of::<usize>() * 8;
651 let word = bit / usize_bits;
652 let bit_in_word = bit % usize_bits;
653 let bit_mask = 1 << bit_in_word;
654 debug!("word={} bit_in_word={} bit_mask={}", word, bit_in_word, bit_mask);
655 let oldv = words[word];
656 let newv = oldv | bit_mask;
661 fn bit_str(bit: usize) -> String {
663 let lobits = 1 << (bit & 0b111);
664 format!("[{}:{}-{:02x}]", bit, byte, lobits)
668 impl BitwiseOperator for Union {
669 fn join(&self, a: usize, b: usize) -> usize { a | b }
672 impl BitwiseOperator for Subtract {
673 fn join(&self, a: usize, b: usize) -> usize { a & !b }