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