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