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
;
24 use std
::iter
::repeat
;
26 use syntax
::ast_util
::IdRange
;
28 use syntax
::print
::{pp, pprust}
;
29 use util
::nodemap
::NodeMap
;
32 pub enum EntryOrExit
{
38 pub struct DataFlowContext
<'a
, 'tcx
: 'a
, O
> {
39 tcx
: &'a ty
::ctxt
<'tcx
>,
41 /// a name for the analysis using this dataflow instance
42 analysis_name
: &'
static str,
44 /// the data flow operator
47 /// number of bits to propagate per id
50 /// number of words we will use to store bits_per_id.
51 /// equal to bits_per_id/uint::BITS rounded up.
54 // mapping from node to cfg node index
55 // FIXME (#6298): Shouldn't this go with CFG?
56 nodeid_to_index
: NodeMap
<CFGIndex
>,
58 // Bit sets per cfg node. The following three fields (`gens`, `kills`,
59 // and `on_entry`) all have the same structure. For each id in
60 // `id_range`, there is a range of words equal to `words_per_id`.
61 // So, to access the bits for any given id, you take a slice of
62 // the full vector (see the method `compute_id_range()`).
64 /// bits generated as we exit the cfg node. Updated by `add_gen()`.
67 /// bits killed as we exit the cfg node. Updated by `add_kill()`.
70 /// bits that are valid on entry to the cfg node. Updated by
75 pub trait BitwiseOperator
{
76 /// Joins two predecessor bits together, typically either `|` or `&`
77 fn join(&self, succ
: uint
, pred
: uint
) -> uint
;
80 /// Parameterization for the precise form of data flow that is used.
81 pub trait DataFlowOperator
: BitwiseOperator
{
82 /// Specifies the initial value for each bit in the `on_entry` set
83 fn initial_value(&self) -> bool
;
86 struct PropagationContext
<'a
, 'b
: 'a
, 'tcx
: 'b
, O
: 'a
> {
87 dfcx
: &'a
mut DataFlowContext
<'b
, 'tcx
, O
>,
91 fn to_cfgidx_or_die(id
: ast
::NodeId
, index
: &NodeMap
<CFGIndex
>) -> CFGIndex
{
92 let opt_cfgindex
= index
.get(&id
).map(|&i
|i
);
93 opt_cfgindex
.unwrap_or_else(|| {
94 panic
!("nodeid_to_index does not have entry for NodeId {}", id
);
98 impl<'a
, 'tcx
, O
:DataFlowOperator
> DataFlowContext
<'a
, 'tcx
, O
> {
99 fn has_bitset_for_nodeid(&self, n
: ast
::NodeId
) -> bool
{
100 assert
!(n
!= ast
::DUMMY_NODE_ID
);
101 self.nodeid_to_index
.contains_key(&n
)
105 impl<'a
, 'tcx
, O
:DataFlowOperator
> pprust
::PpAnn
for DataFlowContext
<'a
, 'tcx
, O
> {
107 ps
: &mut pprust
::State
,
108 node
: pprust
::AnnNode
) -> io
::IoResult
<()> {
109 let id
= match node
{
110 pprust
::NodeIdent(_
) | pprust
::NodeName(_
) => 0,
111 pprust
::NodeExpr(expr
) => expr
.id
,
112 pprust
::NodeBlock(blk
) => blk
.id
,
113 pprust
::NodeItem(_
) => 0,
114 pprust
::NodePat(pat
) => pat
.id
117 if self.has_bitset_for_nodeid(id
) {
118 assert
!(self.bits_per_id
> 0);
119 let cfgidx
= to_cfgidx_or_die(id
, &self.nodeid_to_index
);
120 let (start
, end
) = self.compute_id_range(cfgidx
);
121 let on_entry
= self.on_entry
.slice(start
, end
);
122 let entry_str
= bits_to_string(on_entry
);
124 let gens
= self.gens
.slice(start
, end
);
125 let gens_str
= if gens
.iter().any(|&u
| u
!= 0) {
126 format
!(" gen: {}", bits_to_string(gens
))
131 let kills
= self.kills
.slice(start
, end
);
132 let kills_str
= if kills
.iter().any(|&u
| u
!= 0) {
133 format
!(" kill: {}", bits_to_string(kills
))
138 try
!(ps
.synth_comment(format
!("id {}: {}{}{}", id
, entry_str
,
139 gens_str
, kills_str
)));
140 try
!(pp
::space(&mut ps
.s
));
146 fn build_nodeid_to_index(decl
: Option
<&ast
::FnDecl
>,
147 cfg
: &cfg
::CFG
) -> NodeMap
<CFGIndex
> {
148 let mut index
= NodeMap
::new();
150 // FIXME (#6298): Would it be better to fold formals from decl
151 // into cfg itself? i.e. introduce a fn-based flow-graph in
152 // addition to the current block-based flow-graph, rather than
153 // have to put traversals like this here?
156 Some(decl
) => add_entries_from_fn_decl(&mut index
, decl
, cfg
.entry
)
159 cfg
.graph
.each_node(|node_idx
, node
| {
160 if node
.data
.id
!= ast
::DUMMY_NODE_ID
{
161 index
.insert(node
.data
.id
, node_idx
);
168 fn add_entries_from_fn_decl(index
: &mut NodeMap
<CFGIndex
>,
171 //! add mappings from the ast nodes for the formal bindings to
172 //! the entry-node in the graph.
175 index
: &'a
mut NodeMap
<CFGIndex
>,
177 let mut formals
= Formals { entry: entry, index: index }
;
178 visit
::walk_fn_decl(&mut formals
, decl
);
179 impl<'a
, 'v
> visit
::Visitor
<'v
> for Formals
<'a
> {
180 fn visit_pat(&mut self, p
: &ast
::Pat
) {
181 self.index
.insert(p
.id
, self.entry
);
182 visit
::walk_pat(self, p
)
188 impl<'a
, 'tcx
, O
:DataFlowOperator
> DataFlowContext
<'a
, 'tcx
, O
> {
189 pub fn new(tcx
: &'a ty
::ctxt
<'tcx
>,
190 analysis_name
: &'
static str,
191 decl
: Option
<&ast
::FnDecl
>,
195 bits_per_id
: uint
) -> DataFlowContext
<'a
, 'tcx
, O
> {
196 let words_per_id
= (bits_per_id
+ uint
::BITS
- 1) / uint
::BITS
;
197 let num_nodes
= cfg
.graph
.all_nodes().len();
199 debug
!("DataFlowContext::new(analysis_name: {}, id_range={:?}, \
200 bits_per_id={}, words_per_id={}) \
202 analysis_name
, id_range
, bits_per_id
, words_per_id
,
205 let entry
= if oper
.initial_value() { uint::MAX }
else {0}
;
207 let gens
: Vec
<_
> = repeat(0).take(num_nodes
* words_per_id
).collect();
208 let kills
: Vec
<_
> = repeat(0).take(num_nodes
* words_per_id
).collect();
209 let on_entry
: Vec
<_
> = repeat(entry
).take(num_nodes
* words_per_id
).collect();
211 let nodeid_to_index
= build_nodeid_to_index(decl
, cfg
);
215 analysis_name
: analysis_name
,
216 words_per_id
: words_per_id
,
217 nodeid_to_index
: nodeid_to_index
,
218 bits_per_id
: bits_per_id
,
226 pub fn add_gen(&mut self, id
: ast
::NodeId
, bit
: uint
) {
227 //! Indicates that `id` generates `bit`
228 debug
!("{} add_gen(id={}, bit={})",
229 self.analysis_name
, id
, bit
);
230 assert
!(self.nodeid_to_index
.contains_key(&id
));
231 assert
!(self.bits_per_id
> 0);
233 let cfgidx
= to_cfgidx_or_die(id
, &self.nodeid_to_index
);
234 let (start
, end
) = self.compute_id_range(cfgidx
);
235 let gens
= self.gens
.slice_mut(start
, end
);
239 pub fn add_kill(&mut self, id
: ast
::NodeId
, bit
: uint
) {
240 //! Indicates that `id` kills `bit`
241 debug
!("{} add_kill(id={}, bit={})",
242 self.analysis_name
, id
, bit
);
243 assert
!(self.nodeid_to_index
.contains_key(&id
));
244 assert
!(self.bits_per_id
> 0);
246 let cfgidx
= to_cfgidx_or_die(id
, &self.nodeid_to_index
);
247 let (start
, end
) = self.compute_id_range(cfgidx
);
248 let kills
= self.kills
.slice_mut(start
, end
);
252 fn apply_gen_kill(&self, cfgidx
: CFGIndex
, bits
: &mut [uint
]) {
253 //! Applies the gen and kill sets for `cfgidx` to `bits`
254 debug
!("{} apply_gen_kill(cfgidx={:?}, bits={}) [before]",
255 self.analysis_name
, cfgidx
, mut_bits_to_string(bits
));
256 assert
!(self.bits_per_id
> 0);
258 let (start
, end
) = self.compute_id_range(cfgidx
);
259 let gens
= self.gens
.slice(start
, end
);
260 bitwise(bits
, gens
, &Union
);
261 let kills
= self.kills
.slice(start
, end
);
262 bitwise(bits
, kills
, &Subtract
);
264 debug
!("{} apply_gen_kill(cfgidx={:?}, bits={}) [after]",
265 self.analysis_name
, cfgidx
, mut_bits_to_string(bits
));
268 fn compute_id_range(&self, cfgidx
: CFGIndex
) -> (uint
, uint
) {
269 let n
= cfgidx
.node_id();
270 let start
= n
* self.words_per_id
;
271 let end
= start
+ self.words_per_id
;
273 assert
!(start
< self.gens
.len());
274 assert
!(end
<= self.gens
.len());
275 assert
!(self.gens
.len() == self.kills
.len());
276 assert
!(self.gens
.len() == self.on_entry
.len());
282 pub fn each_bit_on_entry
<F
>(&self, id
: ast
::NodeId
, f
: F
) -> bool
where
283 F
: FnMut(uint
) -> bool
,
285 //! Iterates through each bit that is set on entry to `id`.
286 //! Only useful after `propagate()` has been called.
287 if !self.has_bitset_for_nodeid(id
) {
290 let cfgidx
= to_cfgidx_or_die(id
, &self.nodeid_to_index
);
291 self.each_bit_for_node(Entry
, cfgidx
, f
)
294 pub fn each_bit_for_node
<F
>(&self, e
: EntryOrExit
, cfgidx
: CFGIndex
, f
: F
) -> bool
where
295 F
: FnMut(uint
) -> bool
,
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
!("{} 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
<F
>(&self, id
: ast
::NodeId
, f
: F
) -> bool
where
324 F
: FnMut(uint
) -> bool
,
326 //! Iterates through each bit in the gen set for `id`.
327 if !self.has_bitset_for_nodeid(id
) {
331 if self.bits_per_id
== 0 {
332 // Skip the surprisingly common degenerate case. (Note
333 // compute_id_range requires self.words_per_id > 0.)
337 let cfgidx
= to_cfgidx_or_die(id
, &self.nodeid_to_index
);
338 let (start
, end
) = self.compute_id_range(cfgidx
);
339 let gens
= self.gens
.slice(start
, end
);
340 debug
!("{} each_gen_bit(id={}, gens={})",
341 self.analysis_name
, id
, bits_to_string(gens
));
342 self.each_bit(gens
, f
)
345 fn each_bit
<F
>(&self, words
: &[uint
], mut f
: F
) -> bool
where
346 F
: FnMut(uint
) -> bool
,
348 //! Helper for iterating over the bits in a bit set.
349 //! Returns false on the first call to `f` that returns false;
350 //! if all calls to `f` return true, then returns true.
352 for (word_index
, &word
) in words
.iter().enumerate() {
354 let base_index
= word_index
* uint
::BITS
;
355 for offset
in range(0u, uint
::BITS
) {
356 let bit
= 1 << offset
;
357 if (word
& bit
) != 0 {
358 // NB: we round up the total number of bits
359 // that we store in any given bit set so that
360 // it is an even multiple of uint::BITS. This
361 // means that there may be some stray bits at
362 // the end that do not correspond to any
363 // actual value. So before we callback, check
364 // whether the bit_index is greater than the
365 // actual value the user specified and stop
367 let bit_index
= base_index
+ offset
;
368 if bit_index
>= self.bits_per_id
{
370 } else if !f(bit_index
) {
380 pub fn add_kills_from_flow_exits(&mut self, cfg
: &cfg
::CFG
) {
381 //! Whenever you have a `break` or `continue` statement, flow
382 //! exits through any number of enclosing scopes on its way to
383 //! the new destination. This function infers the kill bits of
384 //! those control operators based on the kill bits associated
385 //! with those scopes.
387 //! This is usually called (if it is called at all), after
388 //! all add_gen and add_kill calls, but before propagate.
390 debug
!("{} add_kills_from_flow_exits", self.analysis_name
);
391 if self.bits_per_id
== 0 {
392 // Skip the surprisingly common degenerate case. (Note
393 // compute_id_range requires self.words_per_id > 0.)
396 cfg
.graph
.each_edge(|_edge_index
, edge
| {
397 let flow_exit
= edge
.source();
398 let (start
, end
) = self.compute_id_range(flow_exit
);
399 let mut orig_kills
= self.kills
.slice(start
, end
).to_vec();
401 let mut changed
= false;
402 for &node_id
in edge
.data
.exiting_scopes
.iter() {
403 let opt_cfg_idx
= self.nodeid_to_index
.get(&node_id
).map(|&i
|i
);
406 let (start
, end
) = self.compute_id_range(cfg_idx
);
407 let kills
= self.kills
.slice(start
, end
);
408 if bitwise(orig_kills
.as_mut_slice(), kills
, &Union
) {
413 debug
!("{} add_kills_from_flow_exits flow_exit={:?} \
414 no cfg_idx for exiting_scope={}",
415 self.analysis_name
, flow_exit
, node_id
);
421 let bits
= self.kills
.slice_mut(start
, end
);
422 debug
!("{} add_kills_from_flow_exits flow_exit={:?} bits={} [before]",
423 self.analysis_name
, flow_exit
, mut_bits_to_string(bits
));
424 bits
.clone_from_slice(&orig_kills
[]);
425 debug
!("{} add_kills_from_flow_exits flow_exit={:?} bits={} [after]",
426 self.analysis_name
, flow_exit
, mut_bits_to_string(bits
));
433 impl<'a
, 'tcx
, O
:DataFlowOperator
+Clone
+'
static> DataFlowContext
<'a
, 'tcx
, O
> {
434 // ^^^^^^^^^^^^^ only needed for pretty printing
435 pub fn propagate(&mut self, cfg
: &cfg
::CFG
, blk
: &ast
::Block
) {
436 //! Performs the data flow analysis.
438 if self.bits_per_id
== 0 {
439 // Optimize the surprisingly common degenerate case.
444 let words_per_id
= self.words_per_id
;
445 let mut propcx
= PropagationContext
{
450 let mut temp
: Vec
<_
> = repeat(0u).take(words_per_id
).collect();
451 while propcx
.changed
{
452 propcx
.changed
= false;
453 propcx
.reset(temp
.as_mut_slice());
454 propcx
.walk_cfg(cfg
, temp
.as_mut_slice());
458 debug
!("Dataflow result for {}:", self.analysis_name
);
460 self.pretty_print_to(box io
::stderr(), blk
).unwrap();
465 fn pretty_print_to(&self, wr
: Box
<io
::Writer
+'
static>,
466 blk
: &ast
::Block
) -> io
::IoResult
<()> {
467 let mut ps
= pprust
::rust_printer_annotated(wr
, self);
468 try
!(ps
.cbox(pprust
::indent_unit
));
470 try
!(ps
.print_block(blk
));
475 impl<'a
, 'b
, 'tcx
, O
:DataFlowOperator
> PropagationContext
<'a
, 'b
, 'tcx
, O
> {
476 fn walk_cfg(&mut self,
478 in_out
: &mut [uint
]) {
479 debug
!("DataFlowContext::walk_cfg(in_out={}) {}",
480 bits_to_string(in_out
), self.dfcx
.analysis_name
);
481 assert
!(self.dfcx
.bits_per_id
> 0);
483 cfg
.graph
.each_node(|node_index
, node
| {
484 debug
!("DataFlowContext::walk_cfg idx={:?} id={} begin in_out={}",
485 node_index
, node
.data
.id
, bits_to_string(in_out
));
487 let (start
, end
) = self.dfcx
.compute_id_range(node_index
);
489 // Initialize local bitvector with state on-entry.
490 in_out
.clone_from_slice(self.dfcx
.on_entry
.slice(start
, end
));
492 // Compute state on-exit by applying transfer function to
494 self.dfcx
.apply_gen_kill(node_index
, in_out
);
496 // Propagate state on-exit from node into its successors.
497 self.propagate_bits_into_graph_successors_of(in_out
, cfg
, node_index
);
498 true // continue to next node
502 fn reset(&mut self, bits
: &mut [uint
]) {
503 let e
= if self.dfcx
.oper
.initial_value() {uint::MAX}
else {0}
;
504 for b
in bits
.iter_mut() {
509 fn propagate_bits_into_graph_successors_of(&mut self,
513 cfg
.graph
.each_outgoing_edge(cfgidx
, |_e_idx
, edge
| {
514 self.propagate_bits_into_entry_set_for(pred_bits
, edge
);
519 fn propagate_bits_into_entry_set_for(&mut self,
521 edge
: &cfg
::CFGEdge
) {
522 let source
= edge
.source();
523 let cfgidx
= edge
.target();
524 debug
!("{} propagate_bits_into_entry_set_for(pred_bits={}, {:?} to {:?})",
525 self.dfcx
.analysis_name
, bits_to_string(pred_bits
), source
, cfgidx
);
526 assert
!(self.dfcx
.bits_per_id
> 0);
528 let (start
, end
) = self.dfcx
.compute_id_range(cfgidx
);
530 // (scoping mutable borrow of self.dfcx.on_entry)
531 let on_entry
= self.dfcx
.on_entry
.slice_mut(start
, end
);
532 bitwise(on_entry
, pred_bits
, &self.dfcx
.oper
)
535 debug
!("{} changed entry set for {:?} to {}",
536 self.dfcx
.analysis_name
, cfgidx
,
537 bits_to_string(self.dfcx
.on_entry
.slice(start
, end
)));
543 fn mut_bits_to_string(words
: &mut [uint
]) -> String
{
544 bits_to_string(words
)
547 fn bits_to_string(words
: &[uint
]) -> String
{
548 let mut result
= String
::new();
551 // Note: this is a little endian printout of bytes.
553 for &word
in words
.iter() {
555 for _
in range(0u, uint
::BYTES
) {
557 result
.push_str(&format
!("{:02x}", v
& 0xFF)[]);
567 fn bitwise
<Op
:BitwiseOperator
>(out_vec
: &mut [uint
],
570 assert_eq
!(out_vec
.len(), in_vec
.len());
571 let mut changed
= false;
572 for (out_elt
, in_elt
) in out_vec
.iter_mut().zip(in_vec
.iter()) {
573 let old_val
= *out_elt
;
574 let new_val
= op
.join(old_val
, *in_elt
);
576 changed
|= old_val
!= new_val
;
581 fn set_bit(words
: &mut [uint
], bit
: uint
) -> bool
{
582 debug
!("set_bit: words={} bit={}",
583 mut_bits_to_string(words
), bit_str(bit
));
584 let word
= bit
/ uint
::BITS
;
585 let bit_in_word
= bit
% uint
::BITS
;
586 let bit_mask
= 1 << bit_in_word
;
587 debug
!("word={} bit_in_word={} bit_mask={}", word
, bit_in_word
, word
);
588 let oldv
= words
[word
];
589 let newv
= oldv
| bit_mask
;
594 fn bit_str(bit
: uint
) -> String
{
596 let lobits
= 1u << (bit
& 0xFF);
597 format
!("[{}:{}-{:02x}]", bit
, byte
, lobits
)
601 impl BitwiseOperator
for Union
{
602 fn join(&self, a
: uint
, b
: uint
) -> uint { a | b }
605 impl BitwiseOperator
for Subtract
{
606 fn join(&self, a
: uint
, b
: uint
) -> uint { a & !b }