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.
17 pub use self::EntryOrExit
::*;
20 use middle
::cfg
::CFGIndex
;
25 use syntax
::ast_util
::IdRange
;
27 use syntax
::print
::{pp, pprust}
;
28 use util
::nodemap
::NodeMap
;
30 #[derive(Copy, Clone, Debug)]
31 pub enum EntryOrExit
{
37 pub struct DataFlowContext
<'a
, 'tcx
: 'a
, O
> {
38 tcx
: &'a ty
::ctxt
<'tcx
>,
40 /// a name for the analysis using this dataflow instance
41 analysis_name
: &'
static str,
43 /// the data flow operator
46 /// number of bits to propagate per id
49 /// number of words we will use to store bits_per_id.
50 /// equal to bits_per_id/usize::BITS rounded up.
53 // mapping from node to cfg node index
54 // FIXME (#6298): Shouldn't this go with CFG?
55 nodeid_to_index
: NodeMap
<Vec
<CFGIndex
>>,
57 // Bit sets per cfg node. The following three fields (`gens`, `kills`,
58 // and `on_entry`) all have the same structure. For each id in
59 // `id_range`, there is a range of words equal to `words_per_id`.
60 // So, to access the bits for any given id, you take a slice of
61 // the full vector (see the method `compute_id_range()`).
63 /// bits generated as we exit the cfg node. Updated by `add_gen()`.
66 /// bits killed as we exit the cfg node, or non-locally jump over
67 /// it. Updated by `add_kill(KillFrom::ScopeEnd)`.
68 scope_kills
: Vec
<usize>,
70 /// bits killed as we exit the cfg node directly; if it is jumped
71 /// over, e.g. via `break`, the kills are not reflected in the
72 /// jump's effects. Updated by `add_kill(KillFrom::Execution)`.
73 action_kills
: Vec
<usize>,
75 /// bits that are valid on entry to the cfg node. Updated by
80 pub trait BitwiseOperator
{
81 /// Joins two predecessor bits together, typically either `|` or `&`
82 fn join(&self, succ
: usize, pred
: usize) -> usize;
85 /// Parameterization for the precise form of data flow that is used.
86 pub trait DataFlowOperator
: BitwiseOperator
{
87 /// Specifies the initial value for each bit in the `on_entry` set
88 fn initial_value(&self) -> bool
;
91 struct PropagationContext
<'a
, 'b
: 'a
, 'tcx
: 'b
, O
: 'a
> {
92 dfcx
: &'a
mut DataFlowContext
<'b
, 'tcx
, O
>,
96 fn get_cfg_indices
<'a
>(id
: ast
::NodeId
, index
: &'a NodeMap
<Vec
<CFGIndex
>>) -> &'a
[CFGIndex
] {
97 let opt_indices
= index
.get(&id
);
98 opt_indices
.map(|v
| &v
[..]).unwrap_or(&[])
101 impl<'a
, 'tcx
, O
:DataFlowOperator
> DataFlowContext
<'a
, 'tcx
, O
> {
102 fn has_bitset_for_nodeid(&self, n
: ast
::NodeId
) -> bool
{
103 assert
!(n
!= ast
::DUMMY_NODE_ID
);
104 self.nodeid_to_index
.contains_key(&n
)
108 impl<'a
, 'tcx
, O
:DataFlowOperator
> pprust
::PpAnn
for DataFlowContext
<'a
, 'tcx
, O
> {
110 ps
: &mut pprust
::State
,
111 node
: pprust
::AnnNode
) -> io
::Result
<()> {
112 let id
= match node
{
113 pprust
::NodeIdent(_
) | pprust
::NodeName(_
) => 0,
114 pprust
::NodeExpr(expr
) => expr
.id
,
115 pprust
::NodeBlock(blk
) => blk
.id
,
116 pprust
::NodeItem(_
) | pprust
::NodeSubItem(_
) => 0,
117 pprust
::NodePat(pat
) => pat
.id
120 if !self.has_bitset_for_nodeid(id
) {
124 assert
!(self.bits_per_id
> 0);
125 let indices
= get_cfg_indices(id
, &self.nodeid_to_index
);
126 for &cfgidx
in indices
{
127 let (start
, end
) = self.compute_id_range(cfgidx
);
128 let on_entry
= &self.on_entry
[start
.. end
];
129 let entry_str
= bits_to_string(on_entry
);
131 let gens
= &self.gens
[start
.. end
];
132 let gens_str
= if gens
.iter().any(|&u
| u
!= 0) {
133 format
!(" gen: {}", bits_to_string(gens
))
138 let action_kills
= &self.action_kills
[start
.. end
];
139 let action_kills_str
= if action_kills
.iter().any(|&u
| u
!= 0) {
140 format
!(" action_kill: {}", bits_to_string(action_kills
))
145 let scope_kills
= &self.scope_kills
[start
.. end
];
146 let scope_kills_str
= if scope_kills
.iter().any(|&u
| u
!= 0) {
147 format
!(" scope_kill: {}", bits_to_string(scope_kills
))
152 try
!(ps
.synth_comment(
153 format
!("id {}: {}{}{}{}", id
, entry_str
,
154 gens_str
, action_kills_str
, scope_kills_str
)));
155 try
!(pp
::space(&mut ps
.s
));
161 fn build_nodeid_to_index(decl
: Option
<&ast
::FnDecl
>,
162 cfg
: &cfg
::CFG
) -> NodeMap
<Vec
<CFGIndex
>> {
163 let mut index
= NodeMap();
165 // FIXME (#6298): Would it be better to fold formals from decl
166 // into cfg itself? i.e. introduce a fn-based flow-graph in
167 // addition to the current block-based flow-graph, rather than
168 // have to put traversals like this here?
171 Some(decl
) => add_entries_from_fn_decl(&mut index
, decl
, cfg
.entry
)
174 cfg
.graph
.each_node(|node_idx
, node
| {
175 if let cfg
::CFGNodeData
::AST(id
) = node
.data
{
176 index
.entry(id
).or_insert(vec
![]).push(node_idx
);
183 fn add_entries_from_fn_decl(index
: &mut NodeMap
<Vec
<CFGIndex
>>,
186 //! add mappings from the ast nodes for the formal bindings to
187 //! the entry-node in the graph.
190 index
: &'a
mut NodeMap
<Vec
<CFGIndex
>>,
192 let mut formals
= Formals { entry: entry, index: index }
;
193 visit
::walk_fn_decl(&mut formals
, decl
);
194 impl<'a
, 'v
> visit
::Visitor
<'v
> for Formals
<'a
> {
195 fn visit_pat(&mut self, p
: &ast
::Pat
) {
196 self.index
.entry(p
.id
).or_insert(vec
![]).push(self.entry
);
197 visit
::walk_pat(self, p
)
203 /// Flag used by `add_kill` to indicate whether the provided kill
204 /// takes effect only when control flows directly through the node in
205 /// question, or if the kill's effect is associated with any
206 /// control-flow directly through or indirectly over the node.
207 #[derive(Copy, Clone, PartialEq, Debug)]
209 /// A `ScopeEnd` kill is one that takes effect when any control
210 /// flow goes over the node. A kill associated with the end of the
211 /// scope of a variable declaration `let x;` is an example of a
215 /// An `Execution` kill is one that takes effect only when control
216 /// flow goes through the node to completion. A kill associated
217 /// with an assignment statement `x = expr;` is an example of an
218 /// `Execution` kill.
222 impl<'a
, 'tcx
, O
:DataFlowOperator
> DataFlowContext
<'a
, 'tcx
, O
> {
223 pub fn new(tcx
: &'a ty
::ctxt
<'tcx
>,
224 analysis_name
: &'
static str,
225 decl
: Option
<&ast
::FnDecl
>,
229 bits_per_id
: usize) -> DataFlowContext
<'a
, 'tcx
, O
> {
230 let words_per_id
= (bits_per_id
+ usize::BITS
- 1) / usize::BITS
;
231 let num_nodes
= cfg
.graph
.all_nodes().len();
233 debug
!("DataFlowContext::new(analysis_name: {}, id_range={:?}, \
234 bits_per_id={}, words_per_id={}) \
236 analysis_name
, id_range
, bits_per_id
, words_per_id
,
239 let entry
= if oper
.initial_value() { usize::MAX }
else {0}
;
241 let zeroes
= vec
![0; num_nodes
* words_per_id
];
242 let gens
= zeroes
.clone();
243 let kills1
= zeroes
.clone();
245 let on_entry
= vec
![entry
; num_nodes
* words_per_id
];
247 let nodeid_to_index
= build_nodeid_to_index(decl
, cfg
);
251 analysis_name
: analysis_name
,
252 words_per_id
: words_per_id
,
253 nodeid_to_index
: nodeid_to_index
,
254 bits_per_id
: bits_per_id
,
257 action_kills
: kills1
,
263 pub fn add_gen(&mut self, id
: ast
::NodeId
, bit
: usize) {
264 //! Indicates that `id` generates `bit`
265 debug
!("{} add_gen(id={}, bit={})",
266 self.analysis_name
, id
, bit
);
267 assert
!(self.nodeid_to_index
.contains_key(&id
));
268 assert
!(self.bits_per_id
> 0);
270 let indices
= get_cfg_indices(id
, &self.nodeid_to_index
);
271 for &cfgidx
in indices
{
272 let (start
, end
) = self.compute_id_range(cfgidx
);
273 let gens
= &mut self.gens
[start
.. end
];
278 pub fn add_kill(&mut self, kind
: KillFrom
, id
: ast
::NodeId
, bit
: usize) {
279 //! Indicates that `id` kills `bit`
280 debug
!("{} add_kill(id={}, bit={})",
281 self.analysis_name
, id
, bit
);
282 assert
!(self.nodeid_to_index
.contains_key(&id
));
283 assert
!(self.bits_per_id
> 0);
285 let indices
= get_cfg_indices(id
, &self.nodeid_to_index
);
286 for &cfgidx
in indices
{
287 let (start
, end
) = self.compute_id_range(cfgidx
);
288 let kills
= match kind
{
289 KillFrom
::Execution
=> &mut self.action_kills
[start
.. end
],
290 KillFrom
::ScopeEnd
=> &mut self.scope_kills
[start
.. end
],
296 fn apply_gen_kill(&self, cfgidx
: CFGIndex
, bits
: &mut [usize]) {
297 //! Applies the gen and kill sets for `cfgidx` to `bits`
298 debug
!("{} apply_gen_kill(cfgidx={:?}, bits={}) [before]",
299 self.analysis_name
, cfgidx
, mut_bits_to_string(bits
));
300 assert
!(self.bits_per_id
> 0);
302 let (start
, end
) = self.compute_id_range(cfgidx
);
303 let gens
= &self.gens
[start
.. end
];
304 bitwise(bits
, gens
, &Union
);
305 let kills
= &self.action_kills
[start
.. end
];
306 bitwise(bits
, kills
, &Subtract
);
307 let kills
= &self.scope_kills
[start
.. end
];
308 bitwise(bits
, kills
, &Subtract
);
310 debug
!("{} apply_gen_kill(cfgidx={:?}, bits={}) [after]",
311 self.analysis_name
, cfgidx
, mut_bits_to_string(bits
));
314 fn compute_id_range(&self, cfgidx
: CFGIndex
) -> (usize, usize) {
315 let n
= cfgidx
.node_id();
316 let start
= n
* self.words_per_id
;
317 let end
= start
+ self.words_per_id
;
319 assert
!(start
< self.gens
.len());
320 assert
!(end
<= self.gens
.len());
321 assert
!(self.gens
.len() == self.action_kills
.len());
322 assert
!(self.gens
.len() == self.scope_kills
.len());
323 assert
!(self.gens
.len() == self.on_entry
.len());
329 pub fn each_bit_on_entry
<F
>(&self, id
: ast
::NodeId
, mut f
: F
) -> bool
where
330 F
: FnMut(usize) -> bool
,
332 //! Iterates through each bit that is set on entry to `id`.
333 //! Only useful after `propagate()` has been called.
334 if !self.has_bitset_for_nodeid(id
) {
337 let indices
= get_cfg_indices(id
, &self.nodeid_to_index
);
338 for &cfgidx
in indices
{
339 if !self.each_bit_for_node(Entry
, cfgidx
, |i
| f(i
)) {
346 pub fn each_bit_for_node
<F
>(&self, e
: EntryOrExit
, cfgidx
: CFGIndex
, f
: F
) -> bool
where
347 F
: FnMut(usize) -> bool
,
349 //! Iterates through each bit that is set on entry/exit to `cfgidx`.
350 //! Only useful after `propagate()` has been called.
352 if self.bits_per_id
== 0 {
353 // Skip the surprisingly common degenerate case. (Note
354 // compute_id_range requires self.words_per_id > 0.)
358 let (start
, end
) = self.compute_id_range(cfgidx
);
359 let on_entry
= &self.on_entry
[start
.. end
];
361 let slice
= match e
{
364 let mut t
= on_entry
.to_vec();
365 self.apply_gen_kill(cfgidx
, &mut t
);
370 debug
!("{} each_bit_for_node({:?}, cfgidx={:?}) bits={}",
371 self.analysis_name
, e
, cfgidx
, bits_to_string(slice
));
372 self.each_bit(slice
, f
)
375 pub fn each_gen_bit
<F
>(&self, id
: ast
::NodeId
, mut f
: F
) -> bool
where
376 F
: FnMut(usize) -> bool
,
378 //! Iterates through each bit in the gen set for `id`.
379 if !self.has_bitset_for_nodeid(id
) {
383 if self.bits_per_id
== 0 {
384 // Skip the surprisingly common degenerate case. (Note
385 // compute_id_range requires self.words_per_id > 0.)
389 let indices
= get_cfg_indices(id
, &self.nodeid_to_index
);
390 for &cfgidx
in indices
{
391 let (start
, end
) = self.compute_id_range(cfgidx
);
392 let gens
= &self.gens
[start
.. end
];
393 debug
!("{} each_gen_bit(id={}, gens={})",
394 self.analysis_name
, id
, bits_to_string(gens
));
395 if !self.each_bit(gens
, |i
| f(i
)) {
402 fn each_bit
<F
>(&self, words
: &[usize], mut f
: F
) -> bool
where
403 F
: FnMut(usize) -> bool
,
405 //! Helper for iterating over the bits in a bit set.
406 //! Returns false on the first call to `f` that returns false;
407 //! if all calls to `f` return true, then returns true.
409 for (word_index
, &word
) in words
.iter().enumerate() {
411 let base_index
= word_index
* usize::BITS
;
412 for offset
in 0..usize::BITS
{
413 let bit
= 1 << offset
;
414 if (word
& bit
) != 0 {
415 // NB: we round up the total number of bits
416 // that we store in any given bit set so that
417 // it is an even multiple of usize::BITS. This
418 // means that there may be some stray bits at
419 // the end that do not correspond to any
420 // actual value. So before we callback, check
421 // whether the bit_index is greater than the
422 // actual value the user specified and stop
424 let bit_index
= base_index
+ offset
as usize;
425 if bit_index
>= self.bits_per_id
{
427 } else if !f(bit_index
) {
437 pub fn add_kills_from_flow_exits(&mut self, cfg
: &cfg
::CFG
) {
438 //! Whenever you have a `break` or `continue` statement, flow
439 //! exits through any number of enclosing scopes on its way to
440 //! the new destination. This function infers the kill bits of
441 //! those control operators based on the kill bits associated
442 //! with those scopes.
444 //! This is usually called (if it is called at all), after
445 //! all add_gen and add_kill calls, but before propagate.
447 debug
!("{} add_kills_from_flow_exits", self.analysis_name
);
448 if self.bits_per_id
== 0 {
449 // Skip the surprisingly common degenerate case. (Note
450 // compute_id_range requires self.words_per_id > 0.)
453 cfg
.graph
.each_edge(|_edge_index
, edge
| {
454 let flow_exit
= edge
.source();
455 let (start
, end
) = self.compute_id_range(flow_exit
);
456 let mut orig_kills
= self.scope_kills
[start
.. end
].to_vec();
458 let mut changed
= false;
459 for &node_id
in &edge
.data
.exiting_scopes
{
460 let opt_cfg_idx
= self.nodeid_to_index
.get(&node_id
);
463 for &cfg_idx
in indices
{
464 let (start
, end
) = self.compute_id_range(cfg_idx
);
465 let kills
= &self.scope_kills
[start
.. end
];
466 if bitwise(&mut orig_kills
, kills
, &Union
) {
467 debug
!("scope exits: scope id={} \
468 (node={:?} of {:?}) added killset: {}",
469 node_id
, cfg_idx
, indices
,
470 bits_to_string(kills
));
476 debug
!("{} add_kills_from_flow_exits flow_exit={:?} \
477 no cfg_idx for exiting_scope={}",
478 self.analysis_name
, flow_exit
, node_id
);
484 let bits
= &mut self.scope_kills
[start
.. end
];
485 debug
!("{} add_kills_from_flow_exits flow_exit={:?} bits={} [before]",
486 self.analysis_name
, flow_exit
, mut_bits_to_string(bits
));
487 bits
.clone_from_slice(&orig_kills
[..]);
488 debug
!("{} add_kills_from_flow_exits flow_exit={:?} bits={} [after]",
489 self.analysis_name
, flow_exit
, mut_bits_to_string(bits
));
496 impl<'a
, 'tcx
, O
:DataFlowOperator
+Clone
+'
static> DataFlowContext
<'a
, 'tcx
, O
> {
497 // ^^^^^^^^^^^^^ only needed for pretty printing
498 pub fn propagate(&mut self, cfg
: &cfg
::CFG
, blk
: &ast
::Block
) {
499 //! Performs the data flow analysis.
501 if self.bits_per_id
== 0 {
502 // Optimize the surprisingly common degenerate case.
507 let words_per_id
= self.words_per_id
;
508 let mut propcx
= PropagationContext
{
513 let mut temp
= vec
![0; words_per_id
];
514 while propcx
.changed
{
515 propcx
.changed
= false;
516 propcx
.reset(&mut temp
);
517 propcx
.walk_cfg(cfg
, &mut temp
);
521 debug
!("Dataflow result for {}:", self.analysis_name
);
523 let mut v
= Vec
::new();
524 self.pretty_print_to(box &mut v
, blk
).unwrap();
525 println
!("{}", String
::from_utf8(v
).unwrap());
530 fn pretty_print_to
<'b
>(&self, wr
: Box
<io
::Write
+ 'b
>,
531 blk
: &ast
::Block
) -> io
::Result
<()> {
532 let mut ps
= pprust
::rust_printer_annotated(wr
, self);
533 try
!(ps
.cbox(pprust
::indent_unit
));
535 try
!(ps
.print_block(blk
));
540 impl<'a
, 'b
, 'tcx
, O
:DataFlowOperator
> PropagationContext
<'a
, 'b
, 'tcx
, O
> {
541 fn walk_cfg(&mut self,
543 in_out
: &mut [usize]) {
544 debug
!("DataFlowContext::walk_cfg(in_out={}) {}",
545 bits_to_string(in_out
), self.dfcx
.analysis_name
);
546 assert
!(self.dfcx
.bits_per_id
> 0);
548 cfg
.graph
.each_node(|node_index
, node
| {
549 debug
!("DataFlowContext::walk_cfg idx={:?} id={} begin in_out={}",
550 node_index
, node
.data
.id(), bits_to_string(in_out
));
552 let (start
, end
) = self.dfcx
.compute_id_range(node_index
);
554 // Initialize local bitvector with state on-entry.
555 in_out
.clone_from_slice(&self.dfcx
.on_entry
[start
.. end
]);
557 // Compute state on-exit by applying transfer function to
559 self.dfcx
.apply_gen_kill(node_index
, in_out
);
561 // Propagate state on-exit from node into its successors.
562 self.propagate_bits_into_graph_successors_of(in_out
, cfg
, node_index
);
563 true // continue to next node
567 fn reset(&mut self, bits
: &mut [usize]) {
568 let e
= if self.dfcx
.oper
.initial_value() {usize::MAX}
else {0}
;
574 fn propagate_bits_into_graph_successors_of(&mut self,
578 for (_
, edge
) in cfg
.graph
.outgoing_edges(cfgidx
) {
579 self.propagate_bits_into_entry_set_for(pred_bits
, edge
);
583 fn propagate_bits_into_entry_set_for(&mut self,
585 edge
: &cfg
::CFGEdge
) {
586 let source
= edge
.source();
587 let cfgidx
= edge
.target();
588 debug
!("{} propagate_bits_into_entry_set_for(pred_bits={}, {:?} to {:?})",
589 self.dfcx
.analysis_name
, bits_to_string(pred_bits
), source
, cfgidx
);
590 assert
!(self.dfcx
.bits_per_id
> 0);
592 let (start
, end
) = self.dfcx
.compute_id_range(cfgidx
);
594 // (scoping mutable borrow of self.dfcx.on_entry)
595 let on_entry
= &mut self.dfcx
.on_entry
[start
.. end
];
596 bitwise(on_entry
, pred_bits
, &self.dfcx
.oper
)
599 debug
!("{} changed entry set for {:?} to {}",
600 self.dfcx
.analysis_name
, cfgidx
,
601 bits_to_string(&self.dfcx
.on_entry
[start
.. end
]));
607 fn mut_bits_to_string(words
: &mut [usize]) -> String
{
608 bits_to_string(words
)
611 fn bits_to_string(words
: &[usize]) -> String
{
612 let mut result
= String
::new();
615 // Note: this is a little endian printout of bytes.
619 for _
in 0..usize::BYTES
{
621 result
.push_str(&format
!("{:02x}", v
& 0xFF));
631 fn bitwise
<Op
:BitwiseOperator
>(out_vec
: &mut [usize],
634 assert_eq
!(out_vec
.len(), in_vec
.len());
635 let mut changed
= false;
636 for (out_elt
, in_elt
) in out_vec
.iter_mut().zip(in_vec
) {
637 let old_val
= *out_elt
;
638 let new_val
= op
.join(old_val
, *in_elt
);
640 changed
|= old_val
!= new_val
;
645 fn set_bit(words
: &mut [usize], bit
: usize) -> bool
{
646 debug
!("set_bit: words={} bit={}",
647 mut_bits_to_string(words
), bit_str(bit
));
648 let word
= bit
/ usize::BITS
;
649 let bit_in_word
= bit
% usize::BITS
;
650 let bit_mask
= 1 << bit_in_word
;
651 debug
!("word={} bit_in_word={} bit_mask={}", word
, bit_in_word
, word
);
652 let oldv
= words
[word
];
653 let newv
= oldv
| bit_mask
;
658 fn bit_str(bit
: usize) -> String
{
660 let lobits
= 1 << (bit
& 0xFF);
661 format
!("[{}:{}-{:02x}]", bit
, byte
, lobits
)
665 impl BitwiseOperator
for Union
{
666 fn join(&self, a
: usize, b
: usize) -> usize { a | b }
669 impl BitwiseOperator
for Subtract
{
670 fn join(&self, a
: usize, b
: usize) -> usize { a & !b }