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