src/librustc_borrowck/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 //! 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.
  16
  17 use rustc::cfg;
  18 use rustc::cfg::CFGIndex;
  19 use rustc::ty::TyCtxt;
  20 use std::io;
  21 use std::mem;
  22 use std::usize;
  23 use syntax::print::pprust::PrintState;
  24
  25 use rustc_data_structures::graph::implementation::OUTGOING;
  26
  27 use rustc::util::nodemap::FxHashMap;
  28 use rustc::hir;
  29 use rustc::hir::intravisit::{self, IdRange};
  30 use rustc::hir::print as pprust;
  31
  32
  33 #[derive(Copy, Clone, Debug)]
  34 pub enum EntryOrExit {
  35     Entry,
  36     Exit,
  37 }
  38
  39 #[derive(Clone)]
  40 pub struct DataFlowContext<'a, 'tcx: 'a, O> {
  41     tcx: TyCtxt<'a, 'tcx, 'tcx>,
  42
  43     /// a name for the analysis using this dataflow instance
  44     analysis_name: &'static str,
  45
  46     /// the data flow operator
  47     oper: O,
  48
  49     /// number of bits to propagate per id
  50     bits_per_id: usize,
  51
  52     /// number of words we will use to store bits_per_id.
  53     /// equal to bits_per_id/usize::BITS rounded up.
  54     words_per_id: usize,
  55
  56     // mapping from node to cfg node index
  57     // FIXME (#6298): Shouldn't this go with CFG?
  58     local_id_to_index: FxHashMap<hir::ItemLocalId, Vec<CFGIndex>>,
  59
  60     // Bit sets per cfg node.  The following three fields (`gens`, `kills`,
  61     // and `on_entry`) all have the same structure. For each id in
  62     // `id_range`, there is a range of words equal to `words_per_id`.
  63     // So, to access the bits for any given id, you take a slice of
  64     // the full vector (see the method `compute_id_range()`).
  65
  66     /// bits generated as we exit the cfg node. Updated by `add_gen()`.
  67     gens: Vec<usize>,
  68
  69     /// bits killed as we exit the cfg node, or non-locally jump over
  70     /// it. Updated by `add_kill(KillFrom::ScopeEnd)`.
  71     scope_kills: Vec<usize>,
  72
  73     /// bits killed as we exit the cfg node directly; if it is jumped
  74     /// over, e.g. via `break`, the kills are not reflected in the
  75     /// jump's effects. Updated by `add_kill(KillFrom::Execution)`.
  76     action_kills: Vec<usize>,
  77
  78     /// bits that are valid on entry to the cfg node. Updated by
  79     /// `propagate()`.
  80     on_entry: Vec<usize>,
  81 }
  82
  83 pub trait BitwiseOperator {
  84     /// Joins two predecessor bits together, typically either `|` or `&`
  85     fn join(&self, succ: usize, pred: usize) -> usize;
  86 }
  87
  88 /// Parameterization for the precise form of data flow that is used.
  89 pub trait DataFlowOperator : BitwiseOperator {
  90     /// Specifies the initial value for each bit in the `on_entry` set
  91     fn initial_value(&self) -> bool;
  92 }
  93
  94 struct PropagationContext<'a, 'b: 'a, 'tcx: 'b, O: 'a> {
  95     dfcx: &'a mut DataFlowContext<'b, 'tcx, O>,
  96     changed: bool
  97 }
  98
  99 fn get_cfg_indices<'a>(id: hir::ItemLocalId,
 100                        index: &'a FxHashMap<hir::ItemLocalId, Vec<CFGIndex>>)
 101                        -> &'a [CFGIndex] {
 102     index.get(&id).map_or(&[], |v| &v[..])
 103 }
 104
 105 impl<'a, 'tcx, O:DataFlowOperator> DataFlowContext<'a, 'tcx, O> {
 106     fn has_bitset_for_local_id(&self, n: hir::ItemLocalId) -> bool {
 107         assert!(n != hir::DUMMY_ITEM_LOCAL_ID);
 108         self.local_id_to_index.contains_key(&n)
 109     }
 110 }
 111
 112 impl<'a, 'tcx, O:DataFlowOperator> pprust::PpAnn for DataFlowContext<'a, 'tcx, O> {
 113     fn nested(&self, state: &mut pprust::State, nested: pprust::Nested) -> io::Result<()> {
 114         pprust::PpAnn::nested(self.tcx.hir(), state, nested)
 115     }
 116     fn pre(&self,
 117            ps: &mut pprust::State,
 118            node: pprust::AnnNode) -> io::Result<()> {
 119         let id = match node {
 120             pprust::AnnNode::Name(_) => return Ok(()),
 121             pprust::AnnNode::Expr(expr) => expr.hir_id.local_id,
 122             pprust::AnnNode::Block(blk) => blk.hir_id.local_id,
 123             pprust::AnnNode::Item(_) |
 124             pprust::AnnNode::SubItem(_) => return Ok(()),
 125             pprust::AnnNode::Pat(pat) => pat.hir_id.local_id
 126         };
 127
 128         if !self.has_bitset_for_local_id(id) {
 129             return Ok(());
 130         }
 131
 132         assert!(self.bits_per_id > 0);
 133         let indices = get_cfg_indices(id, &self.local_id_to_index);
 134         for &cfgidx in indices {
 135             let (start, end) = self.compute_id_range(cfgidx);
 136             let on_entry = &self.on_entry[start.. end];
 137             let entry_str = bits_to_string(on_entry);
 138
 139             let gens = &self.gens[start.. end];
 140             let gens_str = if gens.iter().any(|&u| u != 0) {
 141                 format!(" gen: {}", bits_to_string(gens))
 142             } else {
 143                 String::new()
 144             };
 145
 146             let action_kills = &self.action_kills[start .. end];
 147             let action_kills_str = if action_kills.iter().any(|&u| u != 0) {
 148                 format!(" action_kill: {}", bits_to_string(action_kills))
 149             } else {
 150                 String::new()
 151             };
 152
 153             let scope_kills = &self.scope_kills[start .. end];
 154             let scope_kills_str = if scope_kills.iter().any(|&u| u != 0) {
 155                 format!(" scope_kill: {}", bits_to_string(scope_kills))
 156             } else {
 157                 String::new()
 158             };
 159
 160             ps.synth_comment(
 161                 format!("id {}: {}{}{}{}", id.as_usize(), entry_str,
 162                         gens_str, action_kills_str, scope_kills_str))?;
 163             ps.s.space()?;
 164         }
 165         Ok(())
 166     }
 167 }
 168
 169 fn build_local_id_to_index(body: Option<&hir::Body>,
 170                            cfg: &cfg::CFG)
 171                            -> FxHashMap<hir::ItemLocalId, Vec<CFGIndex>> {
 172     let mut index = FxHashMap::default();
 173
 174     // FIXME(#15020) Would it be better to fold formals from decl
 175     // into cfg itself?  i.e. introduce a fn-based flow-graph in
 176     // addition to the current block-based flow-graph, rather than
 177     // have to put traversals like this here?
 178     if let Some(body) = body {
 179         add_entries_from_fn_body(&mut index, body, cfg.entry);
 180     }
 181
 182     cfg.graph.each_node(|node_idx, node| {
 183         if let cfg::CFGNodeData::AST(id) = node.data {
 184             index.entry(id).or_default().push(node_idx);
 185         }
 186         true
 187     });
 188
 189     return index;
 190
 191     /// Add mappings from the ast nodes for the formal bindings to
 192     /// the entry-node in the graph.
 193     fn add_entries_from_fn_body(index: &mut FxHashMap<hir::ItemLocalId, Vec<CFGIndex>>,
 194                                 body: &hir::Body,
 195                                 entry: CFGIndex) {
 196         use rustc::hir::intravisit::Visitor;
 197
 198         struct Formals<'a> {
 199             entry: CFGIndex,
 200             index: &'a mut FxHashMap<hir::ItemLocalId, Vec<CFGIndex>>,
 201         }
 202         let mut formals = Formals { entry: entry, index: index };
 203         for arg in &body.arguments {
 204             formals.visit_pat(&arg.pat);
 205         }
 206         impl<'a, 'v> Visitor<'v> for Formals<'a> {
 207             fn nested_visit_map<'this>(&'this mut self) -> intravisit::NestedVisitorMap<'this, 'v> {
 208                 intravisit::NestedVisitorMap::None
 209             }
 210
 211             fn visit_pat(&mut self, p: &hir::Pat) {
 212                 self.index.entry(p.hir_id.local_id).or_default().push(self.entry);
 213                 intravisit::walk_pat(self, p)
 214             }
 215         }
 216     }
 217 }
 218
 219 /// Flag used by `add_kill` to indicate whether the provided kill
 220 /// takes effect only when control flows directly through the node in
 221 /// question, or if the kill's effect is associated with any
 222 /// control-flow directly through or indirectly over the node.
 223 #[derive(Copy, Clone, PartialEq, Debug)]
 224 pub enum KillFrom {
 225     /// A `ScopeEnd` kill is one that takes effect when any control
 226     /// flow goes over the node. A kill associated with the end of the
 227     /// scope of a variable declaration `let x;` is an example of a
 228     /// `ScopeEnd` kill.
 229     ScopeEnd,
 230
 231     /// An `Execution` kill is one that takes effect only when control
 232     /// flow goes through the node to completion. A kill associated
 233     /// with an assignment statement `x = expr;` is an example of an
 234     /// `Execution` kill.
 235     Execution,
 236 }
 237
 238 impl<'a, 'tcx, O:DataFlowOperator> DataFlowContext<'a, 'tcx, O> {
 239     pub fn new(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 240                analysis_name: &'static str,
 241                body: Option<&hir::Body>,
 242                cfg: &cfg::CFG,
 243                oper: O,
 244                id_range: IdRange,
 245                bits_per_id: usize) -> DataFlowContext<'a, 'tcx, O> {
 246         let usize_bits = mem::size_of::<usize>() * 8;
 247         let words_per_id = (bits_per_id + usize_bits - 1) / usize_bits;
 248         let num_nodes = cfg.graph.all_nodes().len();
 249
 250         debug!("DataFlowContext::new(analysis_name: {}, id_range={:?}, \
 251                                      bits_per_id={}, words_per_id={}) \
 252                                      num_nodes: {}",
 253                analysis_name, id_range, bits_per_id, words_per_id,
 254                num_nodes);
 255
 256         let entry = if oper.initial_value() { usize::MAX } else {0};
 257
 258         let zeroes = vec![0; num_nodes * words_per_id];
 259         let gens = zeroes.clone();
 260         let kills1 = zeroes.clone();
 261         let kills2 = zeroes;
 262         let on_entry = vec![entry; num_nodes * words_per_id];
 263
 264         let local_id_to_index = build_local_id_to_index(body, cfg);
 265
 266         DataFlowContext {
 267             tcx,
 268             analysis_name,
 269             words_per_id,
 270             local_id_to_index,
 271             bits_per_id,
 272             oper,
 273             gens,
 274             action_kills: kills1,
 275             scope_kills: kills2,
 276             on_entry,
 277         }
 278     }
 279
 280     pub fn add_gen(&mut self, id: hir::ItemLocalId, bit: usize) {
 281         //! Indicates that `id` generates `bit`
 282         debug!("{} add_gen(id={:?}, bit={})",
 283                self.analysis_name, id, bit);
 284         assert!(self.local_id_to_index.contains_key(&id));
 285         assert!(self.bits_per_id > 0);
 286
 287         let indices = get_cfg_indices(id, &self.local_id_to_index);
 288         for &cfgidx in indices {
 289             let (start, end) = self.compute_id_range(cfgidx);
 290             let gens = &mut self.gens[start.. end];
 291             set_bit(gens, bit);
 292         }
 293     }
 294
 295     pub fn add_kill(&mut self, kind: KillFrom, id: hir::ItemLocalId, bit: usize) {
 296         //! Indicates that `id` kills `bit`
 297         debug!("{} add_kill(id={:?}, bit={})",
 298                self.analysis_name, id, bit);
 299         assert!(self.local_id_to_index.contains_key(&id));
 300         assert!(self.bits_per_id > 0);
 301
 302         let indices = get_cfg_indices(id, &self.local_id_to_index);
 303         for &cfgidx in indices {
 304             let (start, end) = self.compute_id_range(cfgidx);
 305             let kills = match kind {
 306                 KillFrom::Execution => &mut self.action_kills[start.. end],
 307                 KillFrom::ScopeEnd =>  &mut self.scope_kills[start.. end],
 308             };
 309             set_bit(kills, bit);
 310         }
 311     }
 312
 313     fn apply_gen_kill(&self, cfgidx: CFGIndex, bits: &mut [usize]) {
 314         //! Applies the gen and kill sets for `cfgidx` to `bits`
 315         debug!("{} apply_gen_kill(cfgidx={:?}, bits={}) [before]",
 316                self.analysis_name, cfgidx, mut_bits_to_string(bits));
 317         assert!(self.bits_per_id > 0);
 318
 319         let (start, end) = self.compute_id_range(cfgidx);
 320         let gens = &self.gens[start.. end];
 321         bitwise(bits, gens, &Union);
 322         let kills = &self.action_kills[start.. end];
 323         bitwise(bits, kills, &Subtract);
 324         let kills = &self.scope_kills[start.. end];
 325         bitwise(bits, kills, &Subtract);
 326
 327         debug!("{} apply_gen_kill(cfgidx={:?}, bits={}) [after]",
 328                self.analysis_name, cfgidx, mut_bits_to_string(bits));
 329     }
 330
 331     fn compute_id_range(&self, cfgidx: CFGIndex) -> (usize, usize) {
 332         let n = cfgidx.node_id();
 333         let start = n * self.words_per_id;
 334         let end = start + self.words_per_id;
 335
 336         assert!(start < self.gens.len());
 337         assert!(end <= self.gens.len());
 338         assert!(self.gens.len() == self.action_kills.len());
 339         assert!(self.gens.len() == self.scope_kills.len());
 340         assert!(self.gens.len() == self.on_entry.len());
 341
 342         (start, end)
 343     }
 344
 345
 346     pub fn each_bit_on_entry<F>(&self, id: hir::ItemLocalId, mut f: F) -> bool where
 347         F: FnMut(usize) -> bool,
 348     {
 349         //! Iterates through each bit that is set on entry to `id`.
 350         //! Only useful after `propagate()` has been called.
 351         if !self.has_bitset_for_local_id(id) {
 352             return true;
 353         }
 354         let indices = get_cfg_indices(id, &self.local_id_to_index);
 355         for &cfgidx in indices {
 356             if !self.each_bit_for_node(EntryOrExit::Entry, cfgidx, |i| f(i)) {
 357                 return false;
 358             }
 359         }
 360         return true;
 361     }
 362
 363     pub fn each_bit_for_node<F>(&self, e: EntryOrExit, cfgidx: CFGIndex, f: F) -> bool where
 364         F: FnMut(usize) -> bool,
 365     {
 366         //! Iterates through each bit that is set on entry/exit to `cfgidx`.
 367         //! Only useful after `propagate()` has been called.
 368
 369         if self.bits_per_id == 0 {
 370             // Skip the surprisingly common degenerate case.  (Note
 371             // compute_id_range requires self.words_per_id > 0.)
 372             return true;
 373         }
 374
 375         let (start, end) = self.compute_id_range(cfgidx);
 376         let on_entry = &self.on_entry[start.. end];
 377         let temp_bits;
 378         let slice = match e {
 379             EntryOrExit::Entry => on_entry,
 380             EntryOrExit::Exit => {
 381                 let mut t = on_entry.to_vec();
 382                 self.apply_gen_kill(cfgidx, &mut t);
 383                 temp_bits = t;
 384                 &temp_bits[..]
 385             }
 386         };
 387         debug!("{} each_bit_for_node({:?}, cfgidx={:?}) bits={}",
 388                self.analysis_name, e, cfgidx, bits_to_string(slice));
 389         self.each_bit(slice, f)
 390     }
 391
 392     pub fn each_gen_bit<F>(&self, id: hir::ItemLocalId, mut f: F) -> bool where
 393         F: FnMut(usize) -> bool,
 394     {
 395         //! Iterates through each bit in the gen set for `id`.
 396         if !self.has_bitset_for_local_id(id) {
 397             return true;
 398         }
 399
 400         if self.bits_per_id == 0 {
 401             // Skip the surprisingly common degenerate case.  (Note
 402             // compute_id_range requires self.words_per_id > 0.)
 403             return true;
 404         }
 405
 406         let indices = get_cfg_indices(id, &self.local_id_to_index);
 407         for &cfgidx in indices {
 408             let (start, end) = self.compute_id_range(cfgidx);
 409             let gens = &self.gens[start.. end];
 410             debug!("{} each_gen_bit(id={:?}, gens={})",
 411                    self.analysis_name, id, bits_to_string(gens));
 412             if !self.each_bit(gens, |i| f(i)) {
 413                 return false;
 414             }
 415         }
 416         return true;
 417     }
 418
 419     fn each_bit<F>(&self, words: &[usize], mut f: F) -> bool where
 420         F: FnMut(usize) -> bool,
 421     {
 422         //! Helper for iterating over the bits in a bit set.
 423         //! Returns false on the first call to `f` that returns false;
 424         //! if all calls to `f` return true, then returns true.
 425
 426         let usize_bits = mem::size_of::<usize>() * 8;
 427         for (word_index, &word) in words.iter().enumerate() {
 428             if word != 0 {
 429                 let base_index = word_index * usize_bits;
 430                 for offset in 0..usize_bits {
 431                     let bit = 1 << offset;
 432                     if (word & bit) != 0 {
 433                         // NB: we round up the total number of bits
 434                         // that we store in any given bit set so that
 435                         // it is an even multiple of usize::BITS.  This
 436                         // means that there may be some stray bits at
 437                         // the end that do not correspond to any
 438                         // actual value.  So before we callback, check
 439                         // whether the bit_index is greater than the
 440                         // actual value the user specified and stop
 441                         // iterating if so.
 442                         let bit_index = base_index + offset as usize;
 443                         if bit_index >= self.bits_per_id {
 444                             return true;
 445                         } else if !f(bit_index) {
 446                             return false;
 447                         }
 448                     }
 449                 }
 450             }
 451         }
 452         return true;
 453     }
 454
 455     pub fn add_kills_from_flow_exits(&mut self, cfg: &cfg::CFG) {
 456         //! Whenever you have a `break` or `continue` statement, flow
 457         //! exits through any number of enclosing scopes on its way to
 458         //! the new destination. This function infers the kill bits of
 459         //! those control operators based on the kill bits associated
 460         //! with those scopes.
 461         //!
 462         //! This is usually called (if it is called at all), after
 463         //! all add_gen and add_kill calls, but before propagate.
 464
 465         debug!("{} add_kills_from_flow_exits", self.analysis_name);
 466         if self.bits_per_id == 0 {
 467             // Skip the surprisingly common degenerate case.  (Note
 468             // compute_id_range requires self.words_per_id > 0.)
 469             return;
 470         }
 471         cfg.graph.each_edge(|_edge_index, edge| {
 472             let flow_exit = edge.source();
 473             let (start, end) = self.compute_id_range(flow_exit);
 474             let mut orig_kills = self.scope_kills[start.. end].to_vec();
 475
 476             let mut changed = false;
 477             for &id in &edge.data.exiting_scopes {
 478                 let opt_cfg_idx = self.local_id_to_index.get(&id);
 479                 match opt_cfg_idx {
 480                     Some(indices) => {
 481                         for &cfg_idx in indices {
 482                             let (start, end) = self.compute_id_range(cfg_idx);
 483                             let kills = &self.scope_kills[start.. end];
 484                             if bitwise(&mut orig_kills, kills, &Union) {
 485                                 debug!("scope exits: scope id={:?} \
 486                                         (node={:?} of {:?}) added killset: {}",
 487                                        id, cfg_idx, indices,
 488                                        bits_to_string(kills));
 489                                 changed = true;
 490                             }
 491                         }
 492                     }
 493                     None => {
 494                         debug!("{} add_kills_from_flow_exits flow_exit={:?} \
 495                                 no cfg_idx for exiting_scope={:?}",
 496                                self.analysis_name, flow_exit, id);
 497                     }
 498                 }
 499             }
 500
 501             if changed {
 502                 let bits = &mut self.scope_kills[start.. end];
 503                 debug!("{} add_kills_from_flow_exits flow_exit={:?} bits={} [before]",
 504                        self.analysis_name, flow_exit, mut_bits_to_string(bits));
 505                 bits.copy_from_slice(&orig_kills[..]);
 506                 debug!("{} add_kills_from_flow_exits flow_exit={:?} bits={} [after]",
 507                        self.analysis_name, flow_exit, mut_bits_to_string(bits));
 508             }
 509             true
 510         });
 511     }
 512 }
 513
 514 impl<'a, 'tcx, O:DataFlowOperator+Clone+'static> DataFlowContext<'a, 'tcx, O> {
 515 //                                ^^^^^^^^^^^^^ only needed for pretty printing
 516     pub fn propagate(&mut self, cfg: &cfg::CFG, body: &hir::Body) {
 517         //! Performs the data flow analysis.
 518
 519         if self.bits_per_id == 0 {
 520             // Optimize the surprisingly common degenerate case.
 521             return;
 522         }
 523
 524         {
 525             let words_per_id = self.words_per_id;
 526             let mut propcx = PropagationContext {
 527                 dfcx: &mut *self,
 528                 changed: true
 529             };
 530
 531             let nodes_po = cfg.graph.nodes_in_postorder(OUTGOING, cfg.entry);
 532             let mut temp = vec![0; words_per_id];
 533             let mut num_passes = 0;
 534             while propcx.changed {
 535                 num_passes += 1;
 536                 propcx.changed = false;
 537                 propcx.reset(&mut temp);
 538                 propcx.walk_cfg(cfg, &nodes_po, &mut temp);
 539             }
 540             debug!("finished in {} iterations", num_passes);
 541         }
 542
 543         debug!("Dataflow result for {}:", self.analysis_name);
 544         debug!("{}", pprust::to_string(self, |s| {
 545             s.cbox(pprust::indent_unit)?;
 546             s.ibox(0)?;
 547             s.print_expr(&body.value)
 548         }));
 549     }
 550 }
 551
 552 impl<'a, 'b, 'tcx, O:DataFlowOperator> PropagationContext<'a, 'b, 'tcx, O> {
 553     fn walk_cfg(&mut self,
 554                 cfg: &cfg::CFG,
 555                 nodes_po: &[CFGIndex],
 556                 in_out: &mut [usize]) {
 557         debug!("DataFlowContext::walk_cfg(in_out={}) {}",
 558                bits_to_string(in_out), self.dfcx.analysis_name);
 559         assert!(self.dfcx.bits_per_id > 0);
 560
 561         // Iterate over nodes in reverse postorder
 562         for &node_index in nodes_po.iter().rev() {
 563             let node = cfg.graph.node(node_index);
 564             debug!("DataFlowContext::walk_cfg idx={:?} id={:?} begin in_out={}",
 565                    node_index, node.data.id(), bits_to_string(in_out));
 566
 567             let (start, end) = self.dfcx.compute_id_range(node_index);
 568
 569             // Initialize local bitvector with state on-entry.
 570             in_out.copy_from_slice(&self.dfcx.on_entry[start.. end]);
 571
 572             // Compute state on-exit by applying transfer function to
 573             // state on-entry.
 574             self.dfcx.apply_gen_kill(node_index, in_out);
 575
 576             // Propagate state on-exit from node into its successors.
 577             self.propagate_bits_into_graph_successors_of(in_out, cfg, node_index);
 578         }
 579     }
 580
 581     fn reset(&mut self, bits: &mut [usize]) {
 582         let e = if self.dfcx.oper.initial_value() {usize::MAX} else {0};
 583         for b in bits {
 584             *b = e;
 585         }
 586     }
 587
 588     fn propagate_bits_into_graph_successors_of(&mut self,
 589                                                pred_bits: &[usize],
 590                                                cfg: &cfg::CFG,
 591                                                cfgidx: CFGIndex) {
 592         for (_, edge) in cfg.graph.outgoing_edges(cfgidx) {
 593             self.propagate_bits_into_entry_set_for(pred_bits, edge);
 594         }
 595     }
 596
 597     fn propagate_bits_into_entry_set_for(&mut self,
 598                                          pred_bits: &[usize],
 599                                          edge: &cfg::CFGEdge) {
 600         let source = edge.source();
 601         let cfgidx = edge.target();
 602         debug!("{} propagate_bits_into_entry_set_for(pred_bits={}, {:?} to {:?})",
 603                self.dfcx.analysis_name, bits_to_string(pred_bits), source, cfgidx);
 604         assert!(self.dfcx.bits_per_id > 0);
 605
 606         let (start, end) = self.dfcx.compute_id_range(cfgidx);
 607         let changed = {
 608             // (scoping mutable borrow of self.dfcx.on_entry)
 609             let on_entry = &mut self.dfcx.on_entry[start.. end];
 610             bitwise(on_entry, pred_bits, &self.dfcx.oper)
 611         };
 612         if changed {
 613             debug!("{} changed entry set for {:?} to {}",
 614                    self.dfcx.analysis_name, cfgidx,
 615                    bits_to_string(&self.dfcx.on_entry[start.. end]));
 616             self.changed = true;
 617         }
 618     }
 619 }
 620
 621 fn mut_bits_to_string(words: &mut [usize]) -> String {
 622     bits_to_string(words)
 623 }
 624
 625 fn bits_to_string(words: &[usize]) -> String {
 626     let mut result = String::new();
 627     let mut sep = '[';
 628
 629     // Note: this is a little endian printout of bytes.
 630
 631     for &word in words {
 632         let mut v = word;
 633         for _ in 0..mem::size_of::<usize>() {
 634             result.push(sep);
 635             result.push_str(&format!("{:02x}", v & 0xFF));
 636             v >>= 8;
 637             sep = '-';
 638         }
 639     }
 640     result.push(']');
 641     return result
 642 }
 643
 644 #[inline]
 645 fn bitwise<Op:BitwiseOperator>(out_vec: &mut [usize],
 646                                in_vec: &[usize],
 647                                op: &Op) -> bool {
 648     assert_eq!(out_vec.len(), in_vec.len());
 649     let mut changed = false;
 650     for (out_elt, in_elt) in out_vec.iter_mut().zip(in_vec) {
 651         let old_val = *out_elt;
 652         let new_val = op.join(old_val, *in_elt);
 653         *out_elt = new_val;
 654         changed |= old_val != new_val;
 655     }
 656     changed
 657 }
 658
 659 fn set_bit(words: &mut [usize], bit: usize) -> bool {
 660     debug!("set_bit: words={} bit={}",
 661            mut_bits_to_string(words), bit_str(bit));
 662     let usize_bits = mem::size_of::<usize>() * 8;
 663     let word = bit / usize_bits;
 664     let bit_in_word = bit % usize_bits;
 665     let bit_mask = 1 << bit_in_word;
 666     debug!("word={} bit_in_word={} bit_mask={}", word, bit_in_word, bit_mask);
 667     let oldv = words[word];
 668     let newv = oldv | bit_mask;
 669     words[word] = newv;
 670     oldv != newv
 671 }
 672
 673 fn bit_str(bit: usize) -> String {
 674     let byte = bit >> 3;
 675     let lobits = 1 << (bit & 0b111);
 676     format!("[{}:{}-{:02x}]", bit, byte, lobits)
 677 }
 678
 679 struct Union;
 680 impl BitwiseOperator for Union {
 681     fn join(&self, a: usize, b: usize) -> usize { a | b }
 682 }
 683 struct Subtract;
 684 impl BitwiseOperator for Subtract {
 685     fn join(&self, a: usize, b: usize) -> usize { a & !b }
 686 }