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 /*!
  13  * A module for propagating forward dataflow information. The analysis
  14  * assumes that the items to be propagated can be represented as bits
  15  * and thus uses bitvectors. Your job is simply to specify the so-called
  16  * GEN and KILL bits for each expression.
  17  */
  18
  19
  20 use std::io;
  21 use std::uint;
  22 use std::vec;
  23 use std::vec_ng::Vec;
  24 use syntax::ast;
  25 use syntax::ast_util;
  26 use syntax::ast_util::IdRange;
  27 use syntax::print::{pp, pprust};
  28 use middle::ty;
  29 use middle::typeck;
  30 use util::ppaux::Repr;
  31 use util::nodemap::NodeMap;
  32
  33 #[deriving(Clone)]
  34 pub struct DataFlowContext<'a, O> {
  35     priv tcx: &'a ty::ctxt,
  36     priv method_map: typeck::MethodMap,
  37
  38     /// the data flow operator
  39     priv oper: O,
  40
  41     /// number of bits to propagate per id
  42     priv bits_per_id: uint,
  43
  44     /// number of words we will use to store bits_per_id.
  45     /// equal to bits_per_id/uint::BITS rounded up.
  46     priv words_per_id: uint,
  47
  48     // mapping from node to bitset index.
  49     priv nodeid_to_bitset: NodeMap<uint>,
  50
  51     // Bit sets per id.  The following three fields (`gens`, `kills`,
  52     // and `on_entry`) all have the same structure. For each id in
  53     // `id_range`, there is a range of words equal to `words_per_id`.
  54     // So, to access the bits for any given id, you take a slice of
  55     // the full vector (see the method `compute_id_range()`).
  56
  57     /// bits generated as we exit the scope `id`. Updated by `add_gen()`.
  58     priv gens: Vec<uint> ,
  59
  60     /// bits killed as we exit the scope `id`. Updated by `add_kill()`.
  61     priv kills: Vec<uint> ,
  62
  63     /// bits that are valid on entry to the scope `id`. Updated by
  64     /// `propagate()`.
  65     priv on_entry: Vec<uint> }
  66
  67 /// Parameterization for the precise form of data flow that is used.
  68 pub trait DataFlowOperator {
  69     /// Specifies the initial value for each bit in the `on_entry` set
  70     fn initial_value(&self) -> bool;
  71
  72     /// Joins two predecessor bits together, typically either `|` or `&`
  73     fn join(&self, succ: uint, pred: uint) -> uint;
  74 }
  75
  76 struct PropagationContext<'a, 'b, O> {
  77     dfcx: &'a mut DataFlowContext<'b, O>,
  78     changed: bool
  79 }
  80
  81 struct LoopScope<'a> {
  82     loop_id: ast::NodeId,
  83     break_bits: Vec<uint>
  84 }
  85
  86 impl<'a, O:DataFlowOperator> pprust::PpAnn for DataFlowContext<'a, O> {
  87     fn pre(&self,
  88            ps: &mut pprust::State<DataFlowContext<'a, O>>,
  89            node: pprust::AnnNode) -> io::IoResult<()> {
  90         let id = match node {
  91             pprust::NodeExpr(expr) => expr.id,
  92             pprust::NodeBlock(blk) => blk.id,
  93             pprust::NodeItem(_) => 0,
  94             pprust::NodePat(pat) => pat.id
  95         };
  96
  97         if self.nodeid_to_bitset.contains_key(&id) {
  98             let (start, end) = self.compute_id_range_frozen(id);
  99             let on_entry = self.on_entry.slice(start, end);
 100             let entry_str = bits_to_str(on_entry);
 101
 102             let gens = self.gens.slice(start, end);
 103             let gens_str = if gens.iter().any(|&u| u != 0) {
 104                 format!(" gen: {}", bits_to_str(gens))
 105             } else {
 106                 ~""
 107             };
 108
 109             let kills = self.kills.slice(start, end);
 110             let kills_str = if kills.iter().any(|&u| u != 0) {
 111                 format!(" kill: {}", bits_to_str(kills))
 112             } else {
 113                 ~""
 114             };
 115
 116             try!(ps.synth_comment(format!("id {}: {}{}{}", id, entry_str,
 117                                           gens_str, kills_str)));
 118             try!(pp::space(&mut ps.s));
 119         }
 120         Ok(())
 121     }
 122 }
 123
 124 impl<'a, O:DataFlowOperator> DataFlowContext<'a, O> {
 125     pub fn new(tcx: &'a ty::ctxt,
 126                method_map: typeck::MethodMap,
 127                oper: O,
 128                id_range: IdRange,
 129                bits_per_id: uint) -> DataFlowContext<'a, O> {
 130         let words_per_id = (bits_per_id + uint::BITS - 1) / uint::BITS;
 131
 132         debug!("DataFlowContext::new(id_range={:?}, bits_per_id={:?}, words_per_id={:?})",
 133                id_range, bits_per_id, words_per_id);
 134
 135         let gens = Vec::new();
 136         let kills = Vec::new();
 137         let on_entry = Vec::new();
 138
 139         DataFlowContext {
 140             tcx: tcx,
 141             method_map: method_map,
 142             words_per_id: words_per_id,
 143             nodeid_to_bitset: NodeMap::new(),
 144             bits_per_id: bits_per_id,
 145             oper: oper,
 146             gens: gens,
 147             kills: kills,
 148             on_entry: on_entry
 149         }
 150     }
 151
 152     pub fn add_gen(&mut self, id: ast::NodeId, bit: uint) {
 153         //! Indicates that `id` generates `bit`
 154
 155         debug!("add_gen(id={:?}, bit={:?})", id, bit);
 156         let (start, end) = self.compute_id_range(id);
 157         {
 158             let gens = self.gens.mut_slice(start, end);
 159             set_bit(gens, bit);
 160         }
 161     }
 162
 163     pub fn add_kill(&mut self, id: ast::NodeId, bit: uint) {
 164         //! Indicates that `id` kills `bit`
 165
 166         debug!("add_kill(id={:?}, bit={:?})", id, bit);
 167         let (start, end) = self.compute_id_range(id);
 168         {
 169             let kills = self.kills.mut_slice(start, end);
 170             set_bit(kills, bit);
 171         }
 172     }
 173
 174     fn apply_gen_kill(&mut self, id: ast::NodeId, bits: &mut [uint]) {
 175         //! Applies the gen and kill sets for `id` to `bits`
 176
 177         debug!("apply_gen_kill(id={:?}, bits={}) [before]",
 178                id, mut_bits_to_str(bits));
 179         let (start, end) = self.compute_id_range(id);
 180         let gens = self.gens.slice(start, end);
 181         bitwise(bits, gens, |a, b| a | b);
 182         let kills = self.kills.slice(start, end);
 183         bitwise(bits, kills, |a, b| a & !b);
 184
 185         debug!("apply_gen_kill(id={:?}, bits={}) [after]",
 186                id, mut_bits_to_str(bits));
 187     }
 188
 189     fn apply_kill(&mut self, id: ast::NodeId, bits: &mut [uint]) {
 190         debug!("apply_kill(id={:?}, bits={}) [before]",
 191                id, mut_bits_to_str(bits));
 192         let (start, end) = self.compute_id_range(id);
 193         let kills = self.kills.slice(start, end);
 194         bitwise(bits, kills, |a, b| a & !b);
 195         debug!("apply_kill(id={:?}, bits={}) [after]",
 196                id, mut_bits_to_str(bits));
 197     }
 198
 199     fn compute_id_range_frozen(&self, id: ast::NodeId) -> (uint, uint) {
 200         let n = *self.nodeid_to_bitset.get(&id);
 201         let start = n * self.words_per_id;
 202         let end = start + self.words_per_id;
 203         (start, end)
 204     }
 205
 206     fn compute_id_range(&mut self, id: ast::NodeId) -> (uint, uint) {
 207         let mut expanded = false;
 208         let len = self.nodeid_to_bitset.len();
 209         let n = self.nodeid_to_bitset.find_or_insert_with(id, |_| {
 210             expanded = true;
 211             len
 212         });
 213         if expanded {
 214             let entry = if self.oper.initial_value() { uint::MAX } else {0};
 215             for _ in range(0, self.words_per_id) {
 216                 self.gens.push(0);
 217                 self.kills.push(0);
 218                 self.on_entry.push(entry);
 219             }
 220         }
 221         let start = *n * self.words_per_id;
 222         let end = start + self.words_per_id;
 223
 224         assert!(start < self.gens.len());
 225         assert!(end <= self.gens.len());
 226         assert!(self.gens.len() == self.kills.len());
 227         assert!(self.gens.len() == self.on_entry.len());
 228
 229         (start, end)
 230     }
 231
 232
 233     pub fn each_bit_on_entry_frozen(&self,
 234                                     id: ast::NodeId,
 235                                     f: |uint| -> bool)
 236                                     -> bool {
 237         //! Iterates through each bit that is set on entry to `id`.
 238         //! Only useful after `propagate()` has been called.
 239         if !self.nodeid_to_bitset.contains_key(&id) {
 240             return true;
 241         }
 242         let (start, end) = self.compute_id_range_frozen(id);
 243         let on_entry = self.on_entry.slice(start, end);
 244         debug!("each_bit_on_entry_frozen(id={:?}, on_entry={})",
 245                id, bits_to_str(on_entry));
 246         self.each_bit(on_entry, f)
 247     }
 248
 249     pub fn each_bit_on_entry(&mut self,
 250                              id: ast::NodeId,
 251                              f: |uint| -> bool)
 252                              -> bool {
 253         //! Iterates through each bit that is set on entry to `id`.
 254         //! Only useful after `propagate()` has been called.
 255
 256         let (start, end) = self.compute_id_range(id);
 257         let on_entry = self.on_entry.slice(start, end);
 258         debug!("each_bit_on_entry(id={:?}, on_entry={})",
 259                id, bits_to_str(on_entry));
 260         self.each_bit(on_entry, f)
 261     }
 262
 263     pub fn each_gen_bit(&mut self, id: ast::NodeId, f: |uint| -> bool)
 264                         -> bool {
 265         //! Iterates through each bit in the gen set for `id`.
 266
 267         let (start, end) = self.compute_id_range(id);
 268         let gens = self.gens.slice(start, end);
 269         debug!("each_gen_bit(id={:?}, gens={})",
 270                id, bits_to_str(gens));
 271         self.each_bit(gens, f)
 272     }
 273
 274     pub fn each_gen_bit_frozen(&self, id: ast::NodeId, f: |uint| -> bool)
 275                                -> bool {
 276         //! Iterates through each bit in the gen set for `id`.
 277         if !self.nodeid_to_bitset.contains_key(&id) {
 278             return true;
 279         }
 280         let (start, end) = self.compute_id_range_frozen(id);
 281         let gens = self.gens.slice(start, end);
 282         debug!("each_gen_bit(id={:?}, gens={})",
 283                id, bits_to_str(gens));
 284         self.each_bit(gens, f)
 285     }
 286
 287     fn each_bit(&self, words: &[uint], f: |uint| -> bool) -> bool {
 288         //! Helper for iterating over the bits in a bit set.
 289
 290         for (word_index, &word) in words.iter().enumerate() {
 291             if word != 0 {
 292                 let base_index = word_index * uint::BITS;
 293                 for offset in range(0u, uint::BITS) {
 294                     let bit = 1 << offset;
 295                     if (word & bit) != 0 {
 296                         // NB: we round up the total number of bits
 297                         // that we store in any given bit set so that
 298                         // it is an even multiple of uint::BITS.  This
 299                         // means that there may be some stray bits at
 300                         // the end that do not correspond to any
 301                         // actual value.  So before we callback, check
 302                         // whether the bit_index is greater than the
 303                         // actual value the user specified and stop
 304                         // iterating if so.
 305                         let bit_index = base_index + offset;
 306                         if bit_index >= self.bits_per_id {
 307                             return true;
 308                         } else if !f(bit_index) {
 309                             return false;
 310                         }
 311                     }
 312                 }
 313             }
 314         }
 315         return true;
 316     }
 317 }
 318
 319 impl<'a, O:DataFlowOperator+Clone+'static> DataFlowContext<'a, O> {
 320 //                          ^^^^^^^^^^^^^ only needed for pretty printing
 321     pub fn propagate(&mut self, blk: &ast::Block) {
 322         //! Performs the data flow analysis.
 323
 324         if self.bits_per_id == 0 {
 325             // Optimize the surprisingly common degenerate case.
 326             return;
 327         }
 328
 329         {
 330             let mut propcx = PropagationContext {
 331                 dfcx: &mut *self,
 332                 changed: true
 333             };
 334
 335             let mut temp = vec::from_elem(self.words_per_id, 0u);
 336             let mut loop_scopes = Vec::new();
 337
 338             while propcx.changed {
 339                 propcx.changed = false;
 340                 propcx.reset(temp);
 341                 propcx.walk_block(blk, temp, &mut loop_scopes);
 342             }
 343         }
 344
 345         debug!("Dataflow result:");
 346         debug!("{}", {
 347             self.pretty_print_to(~io::stderr(), blk).unwrap();
 348             ""
 349         });
 350     }
 351
 352     fn pretty_print_to(&self, wr: ~io::Writer,
 353                        blk: &ast::Block) -> io::IoResult<()> {
 354         let mut ps = pprust::rust_printer_annotated(wr, self);
 355         try!(ps.cbox(pprust::indent_unit));
 356         try!(ps.ibox(0u));
 357         try!(ps.print_block(blk));
 358         pp::eof(&mut ps.s)
 359     }
 360 }
 361
 362 impl<'a, 'b, O:DataFlowOperator> PropagationContext<'a, 'b, O> {
 363     fn tcx(&self) -> &'b ty::ctxt {
 364         self.dfcx.tcx
 365     }
 366
 367     fn walk_block(&mut self,
 368                   blk: &ast::Block,
 369                   in_out: &mut [uint],
 370                   loop_scopes: &mut Vec<LoopScope> ) {
 371         debug!("DataFlowContext::walk_block(blk.id={}, in_out={})",
 372                blk.id, bits_to_str(in_out));
 373
 374         self.merge_with_entry_set(blk.id, in_out);
 375
 376         for &stmt in blk.stmts.iter() {
 377             self.walk_stmt(stmt, in_out, loop_scopes);
 378         }
 379
 380         self.walk_opt_expr(blk.expr, in_out, loop_scopes);
 381
 382         self.dfcx.apply_gen_kill(blk.id, in_out);
 383     }
 384
 385     fn walk_stmt(&mut self,
 386                  stmt: @ast::Stmt,
 387                  in_out: &mut [uint],
 388                  loop_scopes: &mut Vec<LoopScope> ) {
 389         match stmt.node {
 390             ast::StmtDecl(decl, _) => {
 391                 self.walk_decl(decl, in_out, loop_scopes);
 392             }
 393
 394             ast::StmtExpr(expr, _) | ast::StmtSemi(expr, _) => {
 395                 self.walk_expr(expr, in_out, loop_scopes);
 396             }
 397
 398             ast::StmtMac(..) => {
 399                 self.tcx().sess.span_bug(stmt.span, "unexpanded macro");
 400             }
 401         }
 402     }
 403
 404     fn walk_decl(&mut self,
 405                  decl: @ast::Decl,
 406                  in_out: &mut [uint],
 407                  loop_scopes: &mut Vec<LoopScope> ) {
 408         match decl.node {
 409             ast::DeclLocal(local) => {
 410                 self.walk_opt_expr(local.init, in_out, loop_scopes);
 411                 self.walk_pat(local.pat, in_out, loop_scopes);
 412             }
 413
 414             ast::DeclItem(_) => {}
 415         }
 416     }
 417
 418     fn walk_expr(&mut self,
 419                  expr: &ast::Expr,
 420                  in_out: &mut [uint],
 421                  loop_scopes: &mut Vec<LoopScope> ) {
 422         debug!("DataFlowContext::walk_expr(expr={}, in_out={})",
 423                expr.repr(self.dfcx.tcx), bits_to_str(in_out));
 424
 425         self.merge_with_entry_set(expr.id, in_out);
 426
 427         match expr.node {
 428             ast::ExprFnBlock(..) | ast::ExprProc(..) => {
 429             }
 430
 431             ast::ExprIf(cond, then, els) => {
 432                 //
 433                 //     (cond)
 434                 //       |
 435                 //       v
 436                 //      ( )
 437                 //     /   \
 438                 //    |     |
 439                 //    v     v
 440                 //  (then)(els)
 441                 //    |     |
 442                 //    v     v
 443                 //   (  succ  )
 444                 //
 445                 self.walk_expr(cond, in_out, loop_scopes);
 446
 447                 let mut then_bits = in_out.to_owned();
 448                 self.walk_block(then, then_bits, loop_scopes);
 449
 450                 self.walk_opt_expr(els, in_out, loop_scopes);
 451                 join_bits(&self.dfcx.oper, then_bits, in_out);
 452             }
 453
 454             ast::ExprWhile(cond, blk) => {
 455                 //
 456                 //     (expr) <--+
 457                 //       |       |
 458                 //       v       |
 459                 //  +--(cond)    |
 460                 //  |    |       |
 461                 //  |    v       |
 462                 //  v  (blk) ----+
 463                 //       |
 464                 //    <--+ (break)
 465                 //
 466
 467                 self.walk_expr(cond, in_out, loop_scopes);
 468
 469                 let mut body_bits = in_out.to_owned();
 470                 loop_scopes.push(LoopScope {
 471                     loop_id: expr.id,
 472                     break_bits: Vec::from_slice(in_out)
 473                 });
 474                 self.walk_block(blk, body_bits, loop_scopes);
 475                 self.add_to_entry_set(expr.id, body_bits);
 476                 let new_loop_scope = loop_scopes.pop().unwrap();
 477                 copy_bits(new_loop_scope.break_bits.as_slice(), in_out);
 478             }
 479
 480             ast::ExprForLoop(..) => fail!("non-desugared expr_for_loop"),
 481
 482             ast::ExprLoop(blk, _) => {
 483                 //
 484                 //     (expr) <--+
 485                 //       |       |
 486                 //       v       |
 487                 //     (blk) ----+
 488                 //       |
 489                 //    <--+ (break)
 490                 //
 491
 492                 let mut body_bits = in_out.to_owned();
 493                 self.reset(in_out);
 494                 loop_scopes.push(LoopScope {
 495                     loop_id: expr.id,
 496                     break_bits: Vec::from_slice(in_out)
 497                 });
 498                 self.walk_block(blk, body_bits, loop_scopes);
 499                 self.add_to_entry_set(expr.id, body_bits);
 500
 501                 let new_loop_scope = loop_scopes.pop().unwrap();
 502                 assert_eq!(new_loop_scope.loop_id, expr.id);
 503                 copy_bits(new_loop_scope.break_bits.as_slice(), in_out);
 504             }
 505
 506             ast::ExprMatch(discr, ref arms) => {
 507                 //
 508                 //    (discr)
 509                 //     / | \
 510                 //    |  |  |
 511                 //    v  v  v
 512                 //   (..arms..)
 513                 //    |  |  |
 514                 //    v  v  v
 515                 //   (  succ  )
 516                 //
 517                 //
 518                 self.walk_expr(discr, in_out, loop_scopes);
 519
 520                 let mut guards = in_out.to_owned();
 521
 522                 // We know that exactly one arm will be taken, so we
 523                 // can start out with a blank slate and just union
 524                 // together the bits from each arm:
 525                 self.reset(in_out);
 526
 527                 for arm in arms.iter() {
 528                     // in_out reflects the discr and all guards to date
 529                     self.walk_opt_expr(arm.guard, guards, loop_scopes);
 530
 531                     // determine the bits for the body and then union
 532                     // them into `in_out`, which reflects all bodies to date
 533                     let mut body = guards.to_owned();
 534                     self.walk_pat_alternatives(arm.pats.as_slice(),
 535                                                body,
 536                                                loop_scopes);
 537                     self.walk_expr(arm.body, body, loop_scopes);
 538                     join_bits(&self.dfcx.oper, body, in_out);
 539                 }
 540             }
 541
 542             ast::ExprRet(o_e) => {
 543                 self.walk_opt_expr(o_e, in_out, loop_scopes);
 544                 self.reset(in_out);
 545             }
 546
 547             ast::ExprBreak(label) => {
 548                 let scope = self.find_scope(expr, label, loop_scopes);
 549                 self.break_from_to(expr, scope, in_out);
 550                 self.reset(in_out);
 551             }
 552
 553             ast::ExprAgain(label) => {
 554                 let scope = self.find_scope(expr, label, loop_scopes);
 555                 self.pop_scopes(expr, scope, in_out);
 556                 self.add_to_entry_set(scope.loop_id, in_out);
 557                 self.reset(in_out);
 558             }
 559
 560             ast::ExprAssign(l, r) |
 561             ast::ExprAssignOp(_, l, r) => {
 562                 self.walk_expr(r, in_out, loop_scopes);
 563                 self.walk_expr(l, in_out, loop_scopes);
 564             }
 565
 566             ast::ExprVec(ref exprs, _) => {
 567                 self.walk_exprs(exprs.as_slice(), in_out, loop_scopes)
 568             }
 569
 570             ast::ExprRepeat(l, r, _) => {
 571                 self.walk_expr(l, in_out, loop_scopes);
 572                 self.walk_expr(r, in_out, loop_scopes);
 573             }
 574
 575             ast::ExprStruct(_, ref fields, with_expr) => {
 576                 for field in fields.iter() {
 577                     self.walk_expr(field.expr, in_out, loop_scopes);
 578                 }
 579                 self.walk_opt_expr(with_expr, in_out, loop_scopes);
 580             }
 581
 582             ast::ExprCall(f, ref args) => {
 583                 self.walk_expr(f, in_out, loop_scopes);
 584                 self.walk_call(expr.id, args.as_slice(), in_out, loop_scopes);
 585             }
 586
 587             ast::ExprMethodCall(_, _, ref args) => {
 588                 self.walk_call(expr.id, args.as_slice(), in_out, loop_scopes);
 589             }
 590
 591             ast::ExprIndex(l, r) |
 592             ast::ExprBinary(_, l, r) if self.is_method_call(expr) => {
 593                 self.walk_call(expr.id, [l, r], in_out, loop_scopes);
 594             }
 595
 596             ast::ExprUnary(_, e) if self.is_method_call(expr) => {
 597                 self.walk_call(expr.id, [e], in_out, loop_scopes);
 598             }
 599
 600             ast::ExprTup(ref exprs) => {
 601                 self.walk_exprs(exprs.as_slice(), in_out, loop_scopes);
 602             }
 603
 604             ast::ExprBinary(op, l, r) if ast_util::lazy_binop(op) => {
 605                 self.walk_expr(l, in_out, loop_scopes);
 606                 let temp = in_out.to_owned();
 607                 self.walk_expr(r, in_out, loop_scopes);
 608                 join_bits(&self.dfcx.oper, temp, in_out);
 609             }
 610
 611             ast::ExprIndex(l, r) |
 612             ast::ExprBinary(_, l, r) => {
 613                 self.walk_exprs([l, r], in_out, loop_scopes);
 614             }
 615
 616             ast::ExprLit(..) |
 617             ast::ExprPath(..) => {}
 618
 619             ast::ExprAddrOf(_, e) |
 620             ast::ExprCast(e, _) |
 621             ast::ExprUnary(_, e) |
 622             ast::ExprParen(e) |
 623             ast::ExprVstore(e, _) |
 624             ast::ExprField(e, _, _) => {
 625                 self.walk_expr(e, in_out, loop_scopes);
 626             }
 627
 628             ast::ExprBox(s, e) => {
 629                 self.walk_expr(s, in_out, loop_scopes);
 630                 self.walk_expr(e, in_out, loop_scopes);
 631             }
 632
 633             ast::ExprInlineAsm(ref inline_asm) => {
 634                 for &(_, expr) in inline_asm.inputs.iter() {
 635                     self.walk_expr(expr, in_out, loop_scopes);
 636                 }
 637                 for &(_, expr) in inline_asm.outputs.iter() {
 638                     self.walk_expr(expr, in_out, loop_scopes);
 639                 }
 640             }
 641
 642             ast::ExprBlock(blk) => {
 643                 self.walk_block(blk, in_out, loop_scopes);
 644             }
 645
 646             ast::ExprMac(..) => {
 647                 self.tcx().sess.span_bug(expr.span, "unexpanded macro");
 648             }
 649         }
 650
 651         self.dfcx.apply_gen_kill(expr.id, in_out);
 652     }
 653
 654     fn pop_scopes(&mut self,
 655                   from_expr: &ast::Expr,
 656                   to_scope: &mut LoopScope,
 657                   in_out: &mut [uint]) {
 658         //! Whenever you have a `break` or a `loop` statement, flow
 659         //! exits through any number of enclosing scopes on its
 660         //! way to the new destination. This function applies the kill
 661         //! sets of those enclosing scopes to `in_out` (those kill sets
 662         //! concern items that are going out of scope).
 663
 664         let tcx = self.tcx();
 665
 666         debug!("pop_scopes(from_expr={}, to_scope={:?}, in_out={})",
 667                from_expr.repr(tcx), to_scope.loop_id,
 668                bits_to_str(in_out));
 669
 670         let mut id = from_expr.id;
 671         while id != to_scope.loop_id {
 672             self.dfcx.apply_kill(id, in_out);
 673
 674             match tcx.region_maps.opt_encl_scope(id) {
 675                 Some(i) => { id = i; }
 676                 None => {
 677                     tcx.sess.span_bug(
 678                         from_expr.span,
 679                         format!("pop_scopes(from_expr={}, to_scope={:?}) \
 680                               to_scope does not enclose from_expr",
 681                              from_expr.repr(tcx), to_scope.loop_id));
 682                 }
 683             }
 684         }
 685     }
 686
 687     fn break_from_to(&mut self,
 688                      from_expr: &ast::Expr,
 689                      to_scope: &mut LoopScope,
 690                      in_out: &mut [uint]) {
 691         self.pop_scopes(from_expr, to_scope, in_out);
 692         self.dfcx.apply_kill(from_expr.id, in_out);
 693         join_bits(&self.dfcx.oper,
 694                   in_out,
 695                   to_scope.break_bits.as_mut_slice());
 696         debug!("break_from_to(from_expr={}, to_scope={}) final break_bits={}",
 697                from_expr.repr(self.tcx()),
 698                to_scope.loop_id,
 699                bits_to_str(in_out));
 700     }
 701
 702     fn walk_exprs(&mut self,
 703                   exprs: &[@ast::Expr],
 704                   in_out: &mut [uint],
 705                   loop_scopes: &mut Vec<LoopScope> ) {
 706         for &expr in exprs.iter() {
 707             self.walk_expr(expr, in_out, loop_scopes);
 708         }
 709     }
 710
 711     fn walk_opt_expr(&mut self,
 712                      opt_expr: Option<@ast::Expr>,
 713                      in_out: &mut [uint],
 714                      loop_scopes: &mut Vec<LoopScope> ) {
 715         for &expr in opt_expr.iter() {
 716             self.walk_expr(expr, in_out, loop_scopes);
 717         }
 718     }
 719
 720     fn walk_call(&mut self,
 721                  call_id: ast::NodeId,
 722                  args: &[@ast::Expr],
 723                  in_out: &mut [uint],
 724                  loop_scopes: &mut Vec<LoopScope> ) {
 725         self.walk_exprs(args, in_out, loop_scopes);
 726
 727         // FIXME(#6268) nested method calls
 728         // self.merge_with_entry_set(in_out);
 729         // self.dfcx.apply_gen_kill(in_out);
 730
 731         let return_ty = ty::node_id_to_type(self.tcx(), call_id);
 732         let fails = ty::type_is_bot(return_ty);
 733         if fails {
 734             self.reset(in_out);
 735         }
 736     }
 737
 738     fn walk_pat(&mut self,
 739                 pat: @ast::Pat,
 740                 in_out: &mut [uint],
 741                 _loop_scopes: &mut Vec<LoopScope> ) {
 742         debug!("DataFlowContext::walk_pat(pat={}, in_out={})",
 743                pat.repr(self.dfcx.tcx), bits_to_str(in_out));
 744
 745         ast_util::walk_pat(pat, |p| {
 746             debug!("  p.id={} in_out={}", p.id, bits_to_str(in_out));
 747             self.merge_with_entry_set(p.id, in_out);
 748             self.dfcx.apply_gen_kill(p.id, in_out);
 749             true
 750         });
 751     }
 752
 753     fn walk_pat_alternatives(&mut self,
 754                              pats: &[@ast::Pat],
 755                              in_out: &mut [uint],
 756                              loop_scopes: &mut Vec<LoopScope> ) {
 757         if pats.len() == 1 {
 758             // Common special case:
 759             return self.walk_pat(pats[0], in_out, loop_scopes);
 760         }
 761
 762         // In the general case, the patterns in `pats` are
 763         // alternatives, so we must treat this like an N-way select
 764         // statement.
 765         let initial_state = in_out.to_owned();
 766         for &pat in pats.iter() {
 767             let mut temp = initial_state.clone();
 768             self.walk_pat(pat, temp, loop_scopes);
 769             join_bits(&self.dfcx.oper, temp, in_out);
 770         }
 771     }
 772
 773     fn find_scope<'a,'b>(
 774                   &self,
 775                   expr: &ast::Expr,
 776                   label: Option<ast::Ident>,
 777                   loop_scopes: &'a mut Vec<LoopScope<'b>>)
 778                   -> &'a mut LoopScope<'b> {
 779         let index = match label {
 780             None => {
 781                 let len = loop_scopes.len();
 782                 len - 1
 783             }
 784
 785             Some(_) => {
 786                 let def_map = self.tcx().def_map.borrow();
 787                 match def_map.get().find(&expr.id) {
 788                     Some(&ast::DefLabel(loop_id)) => {
 789                         match loop_scopes.iter().position(|l| l.loop_id == loop_id) {
 790                             Some(i) => i,
 791                             None => {
 792                                 self.tcx().sess.span_bug(
 793                                     expr.span,
 794                                     format!("no loop scope for id {:?}", loop_id));
 795                             }
 796                         }
 797                     }
 798
 799                     r => {
 800                         self.tcx().sess.span_bug(
 801                             expr.span,
 802                             format!("bad entry `{:?}` in def_map for label", r));
 803                     }
 804                 }
 805             }
 806         };
 807
 808         loop_scopes.get_mut(index)
 809     }
 810
 811     fn is_method_call(&self, expr: &ast::Expr) -> bool {
 812         let method_call = typeck::MethodCall::expr(expr.id);
 813         self.dfcx.method_map.borrow().get().contains_key(&method_call)
 814     }
 815
 816     fn reset(&mut self, bits: &mut [uint]) {
 817         let e = if self.dfcx.oper.initial_value() {uint::MAX} else {0};
 818         for b in bits.mut_iter() { *b = e; }
 819     }
 820
 821     fn add_to_entry_set(&mut self, id: ast::NodeId, pred_bits: &[uint]) {
 822         debug!("add_to_entry_set(id={:?}, pred_bits={})",
 823                id, bits_to_str(pred_bits));
 824         let (start, end) = self.dfcx.compute_id_range(id);
 825         let changed = { // FIXME(#5074) awkward construction
 826             let on_entry = self.dfcx.on_entry.mut_slice(start, end);
 827             join_bits(&self.dfcx.oper, pred_bits, on_entry)
 828         };
 829         if changed {
 830             debug!("changed entry set for {:?} to {}",
 831                    id, bits_to_str(self.dfcx.on_entry.slice(start, end)));
 832             self.changed = true;
 833         }
 834     }
 835
 836     fn merge_with_entry_set(&mut self,
 837                             id: ast::NodeId,
 838                             pred_bits: &mut [uint]) {
 839         debug!("merge_with_entry_set(id={:?}, pred_bits={})",
 840                id, mut_bits_to_str(pred_bits));
 841         let (start, end) = self.dfcx.compute_id_range(id);
 842         let changed = { // FIXME(#5074) awkward construction
 843             let on_entry = self.dfcx.on_entry.mut_slice(start, end);
 844             let changed = join_bits(&self.dfcx.oper, pred_bits, on_entry);
 845             copy_bits(on_entry, pred_bits);
 846             changed
 847         };
 848         if changed {
 849             debug!("changed entry set for {:?} to {}",
 850                    id, bits_to_str(self.dfcx.on_entry.slice(start, end)));
 851             self.changed = true;
 852         }
 853     }
 854 }
 855
 856 fn mut_bits_to_str(words: &mut [uint]) -> ~str {
 857     bits_to_str(words)
 858 }
 859
 860 fn bits_to_str(words: &[uint]) -> ~str {
 861     let mut result = ~"";
 862     let mut sep = '[';
 863
 864     // Note: this is a little endian printout of bytes.
 865
 866     for &word in words.iter() {
 867         let mut v = word;
 868         for _ in range(0u, uint::BYTES) {
 869             result.push_char(sep);
 870             result.push_str(format!("{:02x}", v & 0xFF));
 871             v >>= 8;
 872             sep = '-';
 873         }
 874     }
 875     result.push_char(']');
 876     return result;
 877 }
 878
 879 fn copy_bits(in_vec: &[uint], out_vec: &mut [uint]) -> bool {
 880     bitwise(out_vec, in_vec, |_, b| b)
 881 }
 882
 883 fn join_bits<O:DataFlowOperator>(oper: &O,
 884                                  in_vec: &[uint],
 885                                  out_vec: &mut [uint]) -> bool {
 886     bitwise(out_vec, in_vec, |a, b| oper.join(a, b))
 887 }
 888
 889 #[inline]
 890 fn bitwise(out_vec: &mut [uint], in_vec: &[uint], op: |uint, uint| -> uint)
 891            -> bool {
 892     assert_eq!(out_vec.len(), in_vec.len());
 893     let mut changed = false;
 894     for (out_elt, in_elt) in out_vec.mut_iter().zip(in_vec.iter()) {
 895         let old_val = *out_elt;
 896         let new_val = op(old_val, *in_elt);
 897         *out_elt = new_val;
 898         changed |= old_val != new_val;
 899     }
 900     changed
 901 }
 902
 903 fn set_bit(words: &mut [uint], bit: uint) -> bool {
 904     debug!("set_bit: words={} bit={}",
 905            mut_bits_to_str(words), bit_str(bit));
 906     let word = bit / uint::BITS;
 907     let bit_in_word = bit % uint::BITS;
 908     let bit_mask = 1 << bit_in_word;
 909     debug!("word={} bit_in_word={} bit_mask={}", word, bit_in_word, word);
 910     let oldv = words[word];
 911     let newv = oldv | bit_mask;
 912     words[word] = newv;
 913     oldv != newv
 914 }
 915
 916 fn bit_str(bit: uint) -> ~str {
 917     let byte = bit >> 8;
 918     let lobits = 1 << (bit & 0xFF);
 919     format!("[{}:{}-{:02x}]", bit, byte, lobits)
 920 }