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