src/librustc/middle/dataflow.rs

   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.
   4 //
   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.
  10
  11
  12 /*!
  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.
  17  */
  18
  19
  20 use middle::cfg;
  21 use middle::cfg::CFGIndex;
  22 use middle::ty;
  23 use std::io;
  24 use std::uint;
  25 use syntax::ast;
  26 use syntax::ast_util::IdRange;
  27 use syntax::visit;
  28 use syntax::print::{pp, pprust};
  29 use util::nodemap::NodeMap;
  30
  31 #[deriving(Show)]
  32 pub enum EntryOrExit { Entry, Exit }
  33
  34 #[deriving(Clone)]
  35 pub struct DataFlowContext<'a, O> {
  36     tcx: &'a ty::ctxt,
  37
  38     /// a name for the analysis using this dataflow instance
  39     analysis_name: &'static str,
  40
  41     /// the data flow operator
  42     oper: O,
  43
  44     /// number of bits to propagate per id
  45     bits_per_id: uint,
  46
  47     /// number of words we will use to store bits_per_id.
  48     /// equal to bits_per_id/uint::BITS rounded up.
  49     words_per_id: uint,
  50
  51     // mapping from node to cfg node index
  52     // FIXME (#6298): Shouldn't this go with CFG?
  53     nodeid_to_index: NodeMap<CFGIndex>,
  54
  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()`).
  60
  61     /// bits generated as we exit the cfg node. Updated by `add_gen()`.
  62     gens: Vec<uint>,
  63
  64     /// bits killed as we exit the cfg node. Updated by `add_kill()`.
  65     kills: Vec<uint>,
  66
  67     /// bits that are valid on entry to the cfg node. Updated by
  68     /// `propagate()`.
  69     on_entry: Vec<uint>,
  70 }
  71
  72 pub trait BitwiseOperator {
  73     /// Joins two predecessor bits together, typically either `|` or `&`
  74     fn join(&self, succ: uint, pred: uint) -> uint;
  75 }
  76
  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;
  81 }
  82
  83 struct PropagationContext<'a, 'b:'a, O:'a> {
  84     dfcx: &'a mut DataFlowContext<'b, O>,
  85     changed: bool
  86 }
  87
  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);
  92     })
  93 }
  94
  95 impl<'a, O:DataFlowOperator> DataFlowContext<'a, 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)
  99     }
 100 }
 101
 102 impl<'a, O:DataFlowOperator> pprust::PpAnn for DataFlowContext<'a, O> {
 103     fn pre(&self,
 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
 112         };
 113
 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);
 120
 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))
 124             } else {
 125                 "".to_string()
 126             };
 127
 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))
 131             } else {
 132                 "".to_string()
 133             };
 134
 135             try!(ps.synth_comment(format!("id {}: {}{}{}", id, entry_str,
 136                                           gens_str, kills_str)));
 137             try!(pp::space(&mut ps.s));
 138         }
 139         Ok(())
 140     }
 141 }
 142
 143 fn build_nodeid_to_index(decl: Option<&ast::FnDecl>,
 144                          cfg: &cfg::CFG) -> NodeMap<CFGIndex> {
 145     let mut index = NodeMap::new();
 146
 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?
 151     match decl {
 152         None => {}
 153         Some(decl) => add_entries_from_fn_decl(&mut index, decl, cfg.entry)
 154     }
 155
 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);
 159         }
 160         true
 161     });
 162
 163     return index;
 164
 165     fn add_entries_from_fn_decl(index: &mut NodeMap<CFGIndex>,
 166                                 decl: &ast::FnDecl,
 167                                 entry: CFGIndex) {
 168         //! add mappings from the ast nodes for the formal bindings to
 169         //! the entry-node in the graph.
 170         struct Formals<'a> {
 171             entry: CFGIndex,
 172             index: &'a mut NodeMap<CFGIndex>,
 173         }
 174         let mut formals = Formals { entry: entry, index: index };
 175         visit::walk_fn_decl(&mut formals, decl, ());
 176         impl<'a> visit::Visitor<()> for Formals<'a> {
 177             fn visit_pat(&mut self, p: &ast::Pat, e: ()) {
 178                 self.index.insert(p.id, self.entry);
 179                 visit::walk_pat(self, p, e)
 180             }
 181         }
 182     }
 183 }
 184
 185 impl<'a, O:DataFlowOperator> DataFlowContext<'a, O> {
 186     pub fn new(tcx: &'a ty::ctxt,
 187                analysis_name: &'static str,
 188                decl: Option<&ast::FnDecl>,
 189                cfg: &cfg::CFG,
 190                oper: O,
 191                id_range: IdRange,
 192                bits_per_id: uint) -> DataFlowContext<'a, O> {
 193         let words_per_id = (bits_per_id + uint::BITS - 1) / uint::BITS;
 194         let num_nodes = cfg.graph.all_nodes().len();
 195
 196         debug!("DataFlowContext::new(analysis_name: {:s}, id_range={:?}, \
 197                                      bits_per_id={:?}, words_per_id={:?}) \
 198                                      num_nodes: {}",
 199                analysis_name, id_range, bits_per_id, words_per_id,
 200                num_nodes);
 201
 202         let entry = if oper.initial_value() { uint::MAX } else {0};
 203
 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);
 207
 208         let nodeid_to_index = build_nodeid_to_index(decl, cfg);
 209
 210         DataFlowContext {
 211             tcx: tcx,
 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,
 216             oper: oper,
 217             gens: gens,
 218             kills: kills,
 219             on_entry: on_entry
 220         }
 221     }
 222
 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);
 229
 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);
 233         set_bit(gens, bit);
 234     }
 235
 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);
 242
 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);
 246         set_bit(kills, bit);
 247     }
 248
 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);
 254
 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);
 260
 261         debug!("{:s} apply_gen_kill(cfgidx={}, bits={}) [after]",
 262                self.analysis_name, cfgidx, mut_bits_to_string(bits));
 263     }
 264
 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;
 269
 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());
 274
 275         (start, end)
 276     }
 277
 278
 279     pub fn each_bit_on_entry(&self,
 280                              id: ast::NodeId,
 281                              f: |uint| -> bool)
 282                              -> bool {
 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) {
 286             return true;
 287         }
 288         let cfgidx = to_cfgidx_or_die(id, &self.nodeid_to_index);
 289         self.each_bit_for_node(Entry, cfgidx, f)
 290     }
 291
 292     pub fn each_bit_for_node(&self,
 293                              e: EntryOrExit,
 294                              cfgidx: CFGIndex,
 295                              f: |uint| -> bool)
 296                              -> bool {
 297         //! Iterates through each bit that is set on entry/exit to `cfgidx`.
 298         //! Only useful after `propagate()` has been called.
 299
 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.)
 303             return true;
 304         }
 305
 306         let (start, end) = self.compute_id_range(cfgidx);
 307         let on_entry = self.on_entry.slice(start, end);
 308         let temp_bits;
 309         let slice = match e {
 310             Entry => on_entry,
 311             Exit => {
 312                 let mut t = on_entry.to_vec();
 313                 self.apply_gen_kill(cfgidx, t.as_mut_slice());
 314                 temp_bits = t;
 315                 temp_bits.as_slice()
 316             }
 317         };
 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)
 321     }
 322
 323     pub fn each_gen_bit(&self, id: ast::NodeId, f: |uint| -> bool)
 324                         -> bool {
 325         //! Iterates through each bit in the gen set for `id`.
 326         if !self.has_bitset_for_nodeid(id) {
 327             return true;
 328         }
 329
 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.)
 333             return true;
 334         }
 335
 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)
 342     }
 343
 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.
 348
 349         for (word_index, &word) in words.iter().enumerate() {
 350             if word != 0 {
 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
 363                         // iterating if so.
 364                         let bit_index = base_index + offset;
 365                         if bit_index >= self.bits_per_id {
 366                             return true;
 367                         } else if !f(bit_index) {
 368                             return false;
 369                         }
 370                     }
 371                 }
 372             }
 373         }
 374         return true;
 375     }
 376
 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.
 383         //!
 384         //! This is usually called (if it is called at all), after
 385         //! all add_gen and add_kill calls, but before propagate.
 386
 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.)
 391             return;
 392         }
 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();
 397
 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);
 401                 match opt_cfg_idx {
 402                     Some(cfg_idx) => {
 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) {
 406                             changed = true;
 407                         }
 408                     }
 409                     None => {
 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);
 413                     }
 414                 }
 415             }
 416
 417             if changed {
 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));
 424             }
 425             true
 426         });
 427     }
 428 }
 429
 430 impl<'a, O:DataFlowOperator+Clone+'static> DataFlowContext<'a, 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.
 434
 435         if self.bits_per_id == 0 {
 436             // Optimize the surprisingly common degenerate case.
 437             return;
 438         }
 439
 440         {
 441             let words_per_id = self.words_per_id;
 442             let mut propcx = PropagationContext {
 443                 dfcx: &mut *self,
 444                 changed: true
 445             };
 446
 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());
 452             }
 453         }
 454
 455         debug!("Dataflow result for {:s}:", self.analysis_name);
 456         debug!("{}", {
 457             self.pretty_print_to(box io::stderr(), blk).unwrap();
 458             ""
 459         });
 460     }
 461
 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));
 466         try!(ps.ibox(0u));
 467         try!(ps.print_block(blk));
 468         pp::eof(&mut ps.s)
 469     }
 470 }
 471
 472 impl<'a, 'b, O:DataFlowOperator> PropagationContext<'a, 'b, O> {
 473     fn walk_cfg(&mut self,
 474                 cfg: &cfg::CFG,
 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);
 479
 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));
 483
 484             let (start, end) = self.dfcx.compute_id_range(node_index);
 485
 486             // Initialize local bitvector with state on-entry.
 487             in_out.copy_from(self.dfcx.on_entry.slice(start, end));
 488
 489             // Compute state on-exit by applying transfer function to
 490             // state on-entry.
 491             self.dfcx.apply_gen_kill(node_index, in_out);
 492
 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
 496         });
 497     }
 498
 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() {
 502             *b = e;
 503         }
 504     }
 505
 506     fn propagate_bits_into_graph_successors_of(&mut self,
 507                                                pred_bits: &[uint],
 508                                                cfg: &cfg::CFG,
 509                                                cfgidx: CFGIndex) {
 510         cfg.graph.each_outgoing_edge(cfgidx, |_e_idx, edge| {
 511             self.propagate_bits_into_entry_set_for(pred_bits, edge);
 512             true
 513         });
 514     }
 515
 516     fn propagate_bits_into_entry_set_for(&mut self,
 517                                          pred_bits: &[uint],
 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);
 524
 525         let (start, end) = self.dfcx.compute_id_range(cfgidx);
 526         let changed = {
 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)
 530         };
 531         if changed {
 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)));
 535             self.changed = true;
 536         }
 537     }
 538 }
 539
 540 fn mut_bits_to_string(words: &mut [uint]) -> String {
 541     bits_to_string(words)
 542 }
 543
 544 fn bits_to_string(words: &[uint]) -> String {
 545     let mut result = String::new();
 546     let mut sep = '[';
 547
 548     // Note: this is a little endian printout of bytes.
 549
 550     for &word in words.iter() {
 551         let mut v = word;
 552         for _ in range(0u, uint::BYTES) {
 553             result.push_char(sep);
 554             result.push_str(format!("{:02x}", v & 0xFF).as_slice());
 555             v >>= 8;
 556             sep = '-';
 557         }
 558     }
 559     result.push_char(']');
 560     return result
 561 }
 562
 563 #[inline]
 564 fn bitwise<Op:BitwiseOperator>(out_vec: &mut [uint],
 565                                in_vec: &[uint],
 566                                op: &Op) -> bool {
 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);
 572         *out_elt = new_val;
 573         changed |= old_val != new_val;
 574     }
 575     changed
 576 }
 577
 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;
 587     words[word] = newv;
 588     oldv != newv
 589 }
 590
 591 fn bit_str(bit: uint) -> String {
 592     let byte = bit >> 8;
 593     let lobits = 1u << (bit & 0xFF);
 594     format!("[{}:{}-{:02x}]", bit, byte, lobits)
 595 }
 596
 597 struct Union;
 598 impl BitwiseOperator for Union {
 599     fn join(&self, a: uint, b: uint) -> uint { a | b }
 600 }
 601 struct Subtract;
 602 impl BitwiseOperator for Subtract {
 603     fn join(&self, a: uint, b: uint) -> uint { a & !b }
 604 }