src/librustc_borrowck/dataflow.rs

   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.
   5
   6 use rustc::cfg;
   7 use rustc::cfg::CFGIndex;
   8 use rustc::ty::TyCtxt;
   9 use std::io;
  10 use std::mem;
  11 use std::usize;
  12 use syntax::print::pprust::PrintState;
  13 use log::debug;
  14
  15 use rustc_data_structures::graph::implementation::OUTGOING;
  16
  17 use rustc::util::nodemap::FxHashMap;
  18 use rustc::hir;
  19 use rustc::hir::intravisit;
  20 use rustc::hir::print as pprust;
  21
  22 #[derive(Copy, Clone, Debug)]
  23 pub enum EntryOrExit {
  24     Entry,
  25     Exit,
  26 }
  27
  28 #[derive(Clone)]
  29 pub struct DataFlowContext<'tcx, O> {
  30     tcx: TyCtxt<'tcx, 'tcx>,
  31
  32     /// a name for the analysis using this dataflow instance
  33     analysis_name: &'static str,
  34
  35     /// the data flow operator
  36     oper: O,
  37
  38     /// number of bits to propagate per id
  39     bits_per_id: usize,
  40
  41     /// number of words we will use to store bits_per_id.
  42     /// equal to bits_per_id/usize::BITS rounded up.
  43     words_per_id: usize,
  44
  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>>,
  48
  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()`).
  54
  55     /// bits generated as we exit the cfg node. Updated by `add_gen()`.
  56     gens: Vec<usize>,
  57
  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>,
  61
  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>,
  66
  67     /// bits that are valid on entry to the cfg node. Updated by
  68     /// `propagate()`.
  69     on_entry: Vec<usize>,
  70 }
  71
  72 pub trait BitwiseOperator {
  73     /// Joins two predecessor bits together, typically either `|` or `&`
  74     fn join(&self, succ: usize, pred: usize) -> usize;
  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, 'tcx, O> {
  84     dfcx: &'a mut DataFlowContext<'tcx, O>,
  85     changed: bool
  86 }
  87
  88 fn get_cfg_indices<'a>(id: hir::ItemLocalId,
  89                        index: &'a FxHashMap<hir::ItemLocalId, Vec<CFGIndex>>)
  90                        -> &'a [CFGIndex] {
  91     index.get(&id).map_or(&[], |v| &v[..])
  92 }
  93
  94 impl<'tcx, O: DataFlowOperator> DataFlowContext<'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)
  98     }
  99 }
 100
 101 impl<'tcx, O:DataFlowOperator> pprust::PpAnn for DataFlowContext<'tcx, O> {
 102     fn nested(&self, state: &mut pprust::State<'_>, nested: pprust::Nested) -> io::Result<()> {
 103         pprust::PpAnn::nested(self.tcx.hir(), state, nested)
 104     }
 105     fn pre(&self,
 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
 115         };
 116
 117         if !self.has_bitset_for_local_id(id) {
 118             return Ok(());
 119         }
 120
 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);
 127
 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))
 131             } else {
 132                 String::new()
 133             };
 134
 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))
 138             } else {
 139                 String::new()
 140             };
 141
 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))
 145             } else {
 146                 String::new()
 147             };
 148
 149             ps.synth_comment(
 150                 format!("id {}: {}{}{}{}", id.as_usize(), entry_str,
 151                         gens_str, action_kills_str, scope_kills_str))?;
 152             ps.s.space()?;
 153         }
 154         Ok(())
 155     }
 156 }
 157
 158 fn build_local_id_to_index(body: Option<&hir::Body>,
 159                            cfg: &cfg::CFG)
 160                            -> FxHashMap<hir::ItemLocalId, Vec<CFGIndex>> {
 161     let mut index = FxHashMap::default();
 162
 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);
 169     }
 170
 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);
 174         }
 175         true
 176     });
 177
 178     return index;
 179
 180     /// Adds 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>>,
 183                                 body: &hir::Body,
 184                                 entry: CFGIndex) {
 185         use rustc::hir::intravisit::Visitor;
 186
 187         struct Formals<'a> {
 188             entry: CFGIndex,
 189             index: &'a mut FxHashMap<hir::ItemLocalId, Vec<CFGIndex>>,
 190         }
 191         let mut formals = Formals { entry: entry, index: index };
 192         for arg in &body.arguments {
 193             formals.visit_pat(&arg.pat);
 194         }
 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
 198             }
 199
 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)
 203             }
 204         }
 205     }
 206 }
 207
 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)]
 213 pub enum KillFrom {
 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
 217     /// `ScopeEnd` kill.
 218     ScopeEnd,
 219
 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.
 224     Execution,
 225 }
 226
 227 impl<'tcx, O: DataFlowOperator> DataFlowContext<'tcx, O> {
 228     pub fn new(tcx: TyCtxt<'tcx, 'tcx>,
 229                analysis_name: &'static str,
 230                body: Option<&hir::Body>,
 231                cfg: &cfg::CFG,
 232                oper: O,
 233                bits_per_id: usize) -> DataFlowContext<'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();
 237
 238         debug!("DataFlowContext::new(analysis_name: {}, \
 239                                      bits_per_id={}, words_per_id={}) \
 240                                      num_nodes: {}",
 241                analysis_name, bits_per_id, words_per_id,
 242                num_nodes);
 243
 244         let entry = if oper.initial_value() { usize::MAX } else {0};
 245
 246         let zeroes = vec![0; num_nodes * words_per_id];
 247         let gens = zeroes.clone();
 248         let kills1 = zeroes.clone();
 249         let kills2 = zeroes;
 250         let on_entry = vec![entry; num_nodes * words_per_id];
 251
 252         let local_id_to_index = build_local_id_to_index(body, cfg);
 253
 254         DataFlowContext {
 255             tcx,
 256             analysis_name,
 257             words_per_id,
 258             local_id_to_index,
 259             bits_per_id,
 260             oper,
 261             gens,
 262             action_kills: kills1,
 263             scope_kills: kills2,
 264             on_entry,
 265         }
 266     }
 267
 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);
 274
 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];
 279             set_bit(gens, bit);
 280         }
 281     }
 282
 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);
 289
 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],
 296             };
 297             set_bit(kills, bit);
 298         }
 299     }
 300
 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);
 306
 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);
 314
 315         debug!("{} apply_gen_kill(cfgidx={:?}, bits={}) [after]",
 316                self.analysis_name, cfgidx, mut_bits_to_string(bits));
 317     }
 318
 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;
 323
 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());
 329
 330         (start, end)
 331     }
 332
 333
 334     pub fn each_bit_on_entry<F>(&self, id: hir::ItemLocalId, mut f: F) -> bool where
 335         F: FnMut(usize) -> bool,
 336     {
 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) {
 340             return true;
 341         }
 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)) {
 345                 return false;
 346             }
 347         }
 348         return true;
 349     }
 350
 351     pub fn each_bit_for_node<F>(&self, e: EntryOrExit, cfgidx: CFGIndex, f: F) -> bool where
 352         F: FnMut(usize) -> bool,
 353     {
 354         //! Iterates through each bit that is set on entry/exit to `cfgidx`.
 355         //! Only useful after `propagate()` has been called.
 356
 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.)
 360             return true;
 361         }
 362
 363         let (start, end) = self.compute_id_range(cfgidx);
 364         let on_entry = &self.on_entry[start.. end];
 365         let temp_bits;
 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);
 371                 temp_bits = t;
 372                 &temp_bits[..]
 373             }
 374         };
 375         debug!("{} each_bit_for_node({:?}, cfgidx={:?}) bits={}",
 376                self.analysis_name, e, cfgidx, bits_to_string(slice));
 377         self.each_bit(slice, f)
 378     }
 379
 380     pub fn each_gen_bit<F>(&self, id: hir::ItemLocalId, mut f: F) -> bool where
 381         F: FnMut(usize) -> bool,
 382     {
 383         //! Iterates through each bit in the gen set for `id`.
 384         if !self.has_bitset_for_local_id(id) {
 385             return true;
 386         }
 387
 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 true;
 392         }
 393
 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)) {
 401                 return false;
 402             }
 403         }
 404         return true;
 405     }
 406
 407     fn each_bit<F>(&self, words: &[usize], mut f: F) -> bool where
 408         F: FnMut(usize) -> bool,
 409     {
 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.
 413
 414         let usize_bits = mem::size_of::<usize>() * 8;
 415         for (word_index, &word) in words.iter().enumerate() {
 416             if word != 0 {
 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
 429                         // iterating if so.
 430                         let bit_index = base_index + offset as usize;
 431                         if bit_index >= self.bits_per_id {
 432                             return true;
 433                         } else if !f(bit_index) {
 434                             return false;
 435                         }
 436                     }
 437                 }
 438             }
 439         }
 440         return true;
 441     }
 442
 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.
 449         //!
 450         //! This is usually called (if it is called at all), after
 451         //! all add_gen and add_kill calls, but before propagate.
 452
 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.)
 457             return;
 458         }
 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();
 463
 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);
 467                 match opt_cfg_idx {
 468                     Some(indices) => {
 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));
 477                                 changed = true;
 478                             }
 479                         }
 480                     }
 481                     None => {
 482                         debug!("{} add_kills_from_flow_exits flow_exit={:?} \
 483                                 no cfg_idx for exiting_scope={:?}",
 484                                self.analysis_name, flow_exit, id);
 485                     }
 486                 }
 487             }
 488
 489             if changed {
 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));
 496             }
 497             true
 498         });
 499     }
 500 }
 501
 502 // N.B. `Clone + 'static` only needed for pretty printing.
 503 impl<'tcx, O: DataFlowOperator + Clone + 'static> DataFlowContext<'tcx, O> {
 504     pub fn propagate(&mut self, cfg: &cfg::CFG, body: &hir::Body) {
 505         //! Performs the data flow analysis.
 506
 507         if self.bits_per_id == 0 {
 508             // Optimize the surprisingly common degenerate case.
 509             return;
 510         }
 511
 512         {
 513             let words_per_id = self.words_per_id;
 514             let mut propcx = PropagationContext {
 515                 dfcx: &mut *self,
 516                 changed: true
 517             };
 518
 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 {
 523                 num_passes += 1;
 524                 propcx.changed = false;
 525                 propcx.reset(&mut temp);
 526                 propcx.walk_cfg(cfg, &nodes_po, &mut temp);
 527             }
 528             debug!("finished in {} iterations", num_passes);
 529         }
 530
 531         debug!("Dataflow result for {}:", self.analysis_name);
 532         debug!("{}", pprust::to_string(self, |s| {
 533             s.cbox(pprust::indent_unit)?;
 534             s.ibox(0)?;
 535             s.print_expr(&body.value)
 536         }));
 537     }
 538 }
 539
 540 impl<O: DataFlowOperator> PropagationContext<'_, 'tcx, O> {
 541     fn walk_cfg(&mut self,
 542                 cfg: &cfg::CFG,
 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);
 548
 549         // Iterate over nodes in reverse post-order.
 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));
 554
 555             let (start, end) = self.dfcx.compute_id_range(node_index);
 556
 557             // Initialize local bitvector with state on-entry.
 558             in_out.copy_from_slice(&self.dfcx.on_entry[start.. end]);
 559
 560             // Compute state on-exit by applying transfer function to
 561             // state on-entry.
 562             self.dfcx.apply_gen_kill(node_index, in_out);
 563
 564             // Propagate state on-exit from node into its successors.
 565             self.propagate_bits_into_graph_successors_of(in_out, cfg, node_index);
 566         }
 567     }
 568
 569     fn reset(&mut self, bits: &mut [usize]) {
 570         let e = if self.dfcx.oper.initial_value() {usize::MAX} else {0};
 571         for b in bits {
 572             *b = e;
 573         }
 574     }
 575
 576     fn propagate_bits_into_graph_successors_of(&mut self,
 577                                                pred_bits: &[usize],
 578                                                cfg: &cfg::CFG,
 579                                                cfgidx: CFGIndex) {
 580         for (_, edge) in cfg.graph.outgoing_edges(cfgidx) {
 581             self.propagate_bits_into_entry_set_for(pred_bits, edge);
 582         }
 583     }
 584
 585     fn propagate_bits_into_entry_set_for(&mut self,
 586                                          pred_bits: &[usize],
 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);
 593
 594         let (start, end) = self.dfcx.compute_id_range(cfgidx);
 595         let changed = {
 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)
 599         };
 600         if changed {
 601             debug!("{} changed entry set for {:?} to {}",
 602                    self.dfcx.analysis_name, cfgidx,
 603                    bits_to_string(&self.dfcx.on_entry[start.. end]));
 604             self.changed = true;
 605         }
 606     }
 607 }
 608
 609 fn mut_bits_to_string(words: &mut [usize]) -> String {
 610     bits_to_string(words)
 611 }
 612
 613 fn bits_to_string(words: &[usize]) -> String {
 614     let mut result = String::new();
 615     let mut sep = '[';
 616
 617     // Note: this is a little endian printout of bytes.
 618
 619     for &word in words {
 620         let mut v = word;
 621         for _ in 0..mem::size_of::<usize>() {
 622             result.push(sep);
 623             result.push_str(&format!("{:02x}", v & 0xFF));
 624             v >>= 8;
 625             sep = '-';
 626         }
 627     }
 628     result.push(']');
 629     return result
 630 }
 631
 632 #[inline]
 633 fn bitwise<Op: BitwiseOperator>(out_vec: &mut [usize],
 634                                 in_vec: &[usize],
 635                                 op: &Op) -> bool {
 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);
 641         *out_elt = new_val;
 642         changed |= old_val != new_val;
 643     }
 644     changed
 645 }
 646
 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;
 657     words[word] = newv;
 658     oldv != newv
 659 }
 660
 661 fn bit_str(bit: usize) -> String {
 662     let byte = bit >> 3;
 663     let lobits = 1 << (bit & 0b111);
 664     format!("[{}:{}-{:02x}]", bit, byte, lobits)
 665 }
 666
 667 struct Union;
 668 impl BitwiseOperator for Union {
 669     fn join(&self, a: usize, b: usize) -> usize { a | b }
 670 }
 671 struct Subtract;
 672 impl BitwiseOperator for Subtract {
 673     fn join(&self, a: usize, b: usize) -> usize { a & !b }
 674 }