1 // Copyright 2012-2016 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.
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.
12 use rustc::middle::ty;
13 use rustc::mir::repr::{self, Mir, BasicBlock, Lvalue, Rvalue};
14 use rustc::mir::repr::{StatementKind, TerminatorKind};
15 use rustc::util::nodemap::FnvHashMap;
17 use std::cell::{Cell};
18 use std::collections::hash_map::Entry;
23 use super::dataflow::BitDenotation;
24 use super::abs_domain::{AbstractElem, Lift};
26 // This submodule holds some newtype'd Index wrappers that are using
27 // NonZero to ensure that Option<Index> occupies only a single word.
28 // They are in a submodule to impose privacy restrictions; namely, to
29 // ensure that other code does not accidentally access `index.0`
30 // (which is likely to yield a subtle off-by-one error).
32 use core::nonzero::NonZero;
34 macro_rules! new_index {
36 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
37 pub struct $Index(NonZero<usize>);
40 pub fn new(idx: usize) -> Self {
41 unsafe { $Index(NonZero::new(idx + 1)) }
43 pub fn idx(&self) -> usize {
50 /// Index into MovePathData.move_paths
51 new_index!(MovePathIndex);
53 /// Index into MoveData.moves.
54 new_index!(MoveOutIndex);
57 pub use self::indexes::MovePathIndex;
58 pub use self::indexes::MoveOutIndex;
60 /// `MovePath` is a canonicalized representation of a path that is
61 /// moved or assigned to.
63 /// It follows a tree structure.
65 /// Given `struct X { m: M, n: N }` and `x: X`, moves like `drop x.m;`
66 /// move *out* of the l-value `x.m`.
68 /// The MovePaths representing `x.m` and `x.n` are siblings (that is,
69 /// one of them will link to the other via the `next_sibling` field,
70 /// and the other will have no entry in its `next_sibling` field), and
71 /// they both have the MovePath representing `x` as their parent.
73 pub struct MovePath<'tcx> {
74 pub next_sibling: Option<MovePathIndex>,
75 pub first_child: Option<MovePathIndex>,
76 pub parent: Option<MovePathIndex>,
77 pub content: MovePathContent<'tcx>,
80 /// MovePaths usually represent a single l-value. The exceptions are
81 /// forms that arise due to erroneous input code: static data holds
82 /// l-values that we cannot actually move out of. Therefore we map
83 /// statics to a special marker value (`MovePathContent::Static`)
84 /// representing an invalid origin.
85 #[derive(Clone, Debug)]
86 pub enum MovePathContent<'tcx> {
91 /// During construction of the MovePath's, we use PreMovePath to
92 /// represent accumulated state while we are gathering up all the
93 /// children of each path.
95 struct PreMovePath<'tcx> {
96 pub next_sibling: Option<MovePathIndex>,
97 pub first_child: Cell<Option<MovePathIndex>>,
98 pub parent: Option<MovePathIndex>,
99 pub content: MovePathContent<'tcx>,
102 impl<'tcx> PreMovePath<'tcx> {
103 fn into_move_path(self) -> MovePath<'tcx> {
105 next_sibling: self.next_sibling,
107 content: self.content,
108 first_child: self.first_child.get(),
113 impl<'tcx> fmt::Debug for MovePath<'tcx> {
114 fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result {
115 write!(w, "MovePath {{")?;
116 if let Some(parent) = self.parent {
117 write!(w, " parent: {:?},", parent)?;
119 if let Some(first_child) = self.first_child {
120 write!(w, " first_child: {:?},", first_child)?;
122 if let Some(next_sibling) = self.next_sibling {
123 write!(w, " next_sibling: {:?}", next_sibling)?;
125 write!(w, " content: {:?} }}", self.content)
129 pub struct MoveData<'tcx> {
130 pub move_paths: MovePathData<'tcx>,
131 pub moves: Vec<MoveOut>,
133 pub path_map: PathMap,
134 pub rev_lookup: MovePathLookup<'tcx>,
138 /// Location-indexed (BasicBlock for outer index, index within BB
139 /// for inner index) map to list of MoveOutIndex's.
141 /// Each Location `l` is mapped to the MoveOut's that are effects
142 /// of executing the code at `l`. (There can be multiple MoveOut's
143 /// for a given `l` because each MoveOut is associated with one
144 /// particular path being moved.)
145 map: Vec<Vec<Vec<MoveOutIndex>>>,
148 impl Index<Location> for LocMap {
149 type Output = [MoveOutIndex];
150 fn index(&self, index: Location) -> &Self::Output {
151 assert!(index.block.index() < self.map.len());
152 assert!(index.index < self.map[index.block.index()].len());
153 &self.map[index.block.index()][index.index]
158 /// Path-indexed map to list of MoveOutIndex's.
160 /// Each Path `p` is mapped to the MoveOut's that move out of `p`.
161 map: Vec<Vec<MoveOutIndex>>,
164 impl Index<MovePathIndex> for PathMap {
165 type Output = [MoveOutIndex];
166 fn index(&self, index: MovePathIndex) -> &Self::Output {
167 &self.map[index.idx()]
171 /// `MoveOut` represents a point in a program that moves out of some
172 /// L-value; i.e., "creates" uninitialized memory.
174 /// With respect to dataflow analysis:
175 /// - Generated by moves and declaration of uninitialized variables.
176 /// - Killed by assignments to the memory.
177 #[derive(Copy, Clone)]
180 pub path: MovePathIndex,
182 pub source: Location,
185 impl fmt::Debug for MoveOut {
186 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
187 write!(fmt, "p{}@{:?}", self.path.idx(), self.source)
191 #[derive(Copy, Clone)]
192 pub struct Location {
193 /// block where action is located
194 pub block: BasicBlock,
195 /// index within above block; statement when < statments.len) or
196 /// the terminator (when = statements.len).
200 impl fmt::Debug for Location {
201 fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
202 write!(fmt, "{:?}[{}]", self.block, self.index)
206 pub struct MovePathData<'tcx> {
207 move_paths: Vec<MovePath<'tcx>>,
210 impl<'tcx> Index<MovePathIndex> for MovePathData<'tcx> {
211 type Output = MovePath<'tcx>;
212 fn index(&self, i: MovePathIndex) -> &MovePath<'tcx> {
213 &self.move_paths[i.idx()]
217 /// MovePathInverseMap maps from a uint in an lvalue-category to the
218 /// MovePathIndex for the MovePath for that lvalue.
219 type MovePathInverseMap = Vec<Option<MovePathIndex>>;
221 struct MovePathDataBuilder<'a, 'tcx: 'a> {
223 pre_move_paths: Vec<PreMovePath<'tcx>>,
224 rev_lookup: MovePathLookup<'tcx>,
227 /// Tables mapping from an l-value to its MovePathIndex.
228 pub struct MovePathLookup<'tcx> {
229 vars: MovePathInverseMap,
230 temps: MovePathInverseMap,
231 args: MovePathInverseMap,
233 /// The move path representing the return value is constructed
234 /// lazily when we first encounter it in the input MIR.
235 return_ptr: Option<MovePathIndex>,
237 /// A single move path (representing any static data referenced)
238 /// is constructed lazily when we first encounter statics in the
240 statics: Option<MovePathIndex>,
242 /// projections are made from a base-lvalue and a projection
243 /// elem. The base-lvalue will have a unique MovePathIndex; we use
244 /// the latter as the index into the outer vector (narrowing
245 /// subsequent search so that it is solely relative to that
246 /// base-lvalue). For the remaining lookup, we map the projection
247 /// elem to the associated MovePathIndex.
248 projections: Vec<FnvHashMap<AbstractElem<'tcx>, MovePathIndex>>,
250 /// Tracks the next index to allocate during construction of the
251 /// MovePathData. Unused after MovePathData is fully constructed.
252 next_index: MovePathIndex,
257 fn fill_to_with(&mut self, idx: usize, x: Self::T);
258 fn fill_to(&mut self, idx: usize) where Self::T: Default {
259 self.fill_to_with(idx, Default::default())
262 impl<T:Clone> FillTo for Vec<T> {
264 fn fill_to_with(&mut self, idx: usize, x: T) {
265 if idx >= self.len() {
266 let delta = idx + 1 - self.len();
267 assert_eq!(idx + 1, self.len() + delta);
268 self.extend(iter::repeat(x).take(delta))
270 debug_assert!(idx < self.len());
274 #[derive(Clone, Debug)]
275 enum LookupKind { Generate, Reuse }
276 struct Lookup<T>(LookupKind, T);
278 impl Lookup<MovePathIndex> {
279 fn idx(&self) -> usize { (self.1).idx() }
282 impl<'tcx> MovePathLookup<'tcx> {
291 next_index: MovePathIndex::new(0),
295 fn next_index(next: &mut MovePathIndex) -> MovePathIndex {
297 *next = MovePathIndex::new(i.idx() + 1);
301 fn lookup_or_generate(vec: &mut Vec<Option<MovePathIndex>>,
303 next_index: &mut MovePathIndex) -> Lookup<MovePathIndex> {
304 let idx = idx as usize;
305 vec.fill_to_with(idx, None);
306 let entry = &mut vec[idx];
309 let i = Self::next_index(next_index);
311 Lookup(LookupKind::Generate, i)
314 Lookup(LookupKind::Reuse, entry_idx)
319 fn lookup_var(&mut self, var_idx: u32) -> Lookup<MovePathIndex> {
320 Self::lookup_or_generate(&mut self.vars,
322 &mut self.next_index)
325 fn lookup_temp(&mut self, temp_idx: u32) -> Lookup<MovePathIndex> {
326 Self::lookup_or_generate(&mut self.temps,
328 &mut self.next_index)
331 fn lookup_arg(&mut self, arg_idx: u32) -> Lookup<MovePathIndex> {
332 Self::lookup_or_generate(&mut self.args,
334 &mut self.next_index)
337 fn lookup_static(&mut self) -> Lookup<MovePathIndex> {
340 Lookup(LookupKind::Reuse, mpi)
342 ref mut ret @ None => {
343 let mpi = Self::next_index(&mut self.next_index);
345 Lookup(LookupKind::Generate, mpi)
350 fn lookup_return_pointer(&mut self) -> Lookup<MovePathIndex> {
351 match self.return_ptr {
353 Lookup(LookupKind::Reuse, mpi)
355 ref mut ret @ None => {
356 let mpi = Self::next_index(&mut self.next_index);
358 Lookup(LookupKind::Generate, mpi)
363 fn lookup_proj(&mut self,
364 proj: &repr::LvalueProjection<'tcx>,
365 base: MovePathIndex) -> Lookup<MovePathIndex> {
366 let MovePathLookup { ref mut projections,
367 ref mut next_index, .. } = *self;
368 projections.fill_to(base.idx());
369 match projections[base.idx()].entry(proj.elem.lift()) {
370 Entry::Occupied(ent) => {
371 Lookup(LookupKind::Reuse, *ent.get())
373 Entry::Vacant(ent) => {
374 let mpi = Self::next_index(next_index);
376 Lookup(LookupKind::Generate, mpi)
382 impl<'tcx> MovePathLookup<'tcx> {
383 // Unlike the builder `fn move_path_for` below, this lookup
384 // alternative will *not* create a MovePath on the fly for an
385 // unknown l-value; it will simply panic.
386 pub fn find(&self, lval: &Lvalue<'tcx>) -> MovePathIndex {
388 Lvalue::Var(var_idx) => self.vars[var_idx as usize].unwrap(),
389 Lvalue::Temp(temp_idx) => self.temps[temp_idx as usize].unwrap(),
390 Lvalue::Arg(arg_idx) => self.args[arg_idx as usize].unwrap(),
391 Lvalue::Static(ref _def_id) => self.statics.unwrap(),
392 Lvalue::ReturnPointer => self.return_ptr.unwrap(),
393 Lvalue::Projection(ref proj) => {
394 let base_index = self.find(&proj.base);
395 self.projections[base_index.idx()][&proj.elem.lift()]
401 impl<'a, 'tcx> MovePathDataBuilder<'a, 'tcx> {
402 fn lookup(&mut self, lval: &Lvalue<'tcx>) -> Lookup<MovePathIndex> {
403 let proj = match *lval {
404 Lvalue::Var(var_idx) =>
405 return self.rev_lookup.lookup_var(var_idx),
406 Lvalue::Temp(temp_idx) =>
407 return self.rev_lookup.lookup_temp(temp_idx),
408 Lvalue::Arg(arg_idx) =>
409 return self.rev_lookup.lookup_arg(arg_idx),
410 Lvalue::Static(_def_id) =>
411 return self.rev_lookup.lookup_static(),
412 Lvalue::ReturnPointer =>
413 return self.rev_lookup.lookup_return_pointer(),
414 Lvalue::Projection(ref proj) => {
419 let base_index = self.move_path_for(&proj.base);
420 self.rev_lookup.lookup_proj(proj, base_index)
423 fn move_path_for(&mut self, lval: &Lvalue<'tcx>) -> MovePathIndex {
424 let lookup: Lookup<MovePathIndex> = self.lookup(lval);
426 // `lookup` is either the previously assigned index or a
427 // newly-allocated one.
428 debug_assert!(lookup.idx() <= self.pre_move_paths.len());
430 if let Lookup(LookupKind::Generate, mpi) = lookup {
433 // tracks whether content is Some non-static; statics map to None.
434 let content: Option<&Lvalue<'tcx>>;
437 Lvalue::Static(_) => {
443 Lvalue::Var(_) | Lvalue::Temp(_) | Lvalue::Arg(_) |
444 Lvalue::ReturnPointer => {
445 content = Some(lval);
449 Lvalue::Projection(ref proj) => {
450 content = Some(lval);
452 // Here, install new MovePath as new first_child.
454 // Note: `parent` previously allocated (Projection
455 // case of match above established this).
456 let idx = self.move_path_for(&proj.base);
459 let parent_move_path = &mut self.pre_move_paths[idx.idx()];
461 // At last: Swap in the new first_child.
462 sibling = parent_move_path.first_child.get();
463 parent_move_path.first_child.set(Some(mpi));
467 let content = match content {
468 Some(lval) => MovePathContent::Lvalue(lval.clone()),
469 None => MovePathContent::Static,
472 let move_path = PreMovePath {
473 next_sibling: sibling,
476 first_child: Cell::new(None),
479 self.pre_move_paths.push(move_path);
486 impl<'tcx> MoveData<'tcx> {
487 pub fn gather_moves(mir: &Mir<'tcx>, tcx: &ty::TyCtxt<'tcx>) -> Self {
488 gather_moves(mir, tcx)
494 Use, Repeat, Cast, BinaryOp, UnaryOp, Box,
495 Aggregate, Drop, CallFn, CallArg, Return,
498 fn gather_moves<'tcx>(mir: &Mir<'tcx>, tcx: &ty::TyCtxt<'tcx>) -> MoveData<'tcx> {
499 use self::StmtKind as SK;
501 let bbs = mir.all_basic_blocks();
502 let mut moves = Vec::with_capacity(bbs.len());
503 let mut loc_map: Vec<_> = iter::repeat(Vec::new()).take(bbs.len()).collect();
504 let mut path_map = Vec::new();
506 // this is mutable only because we will move it to and fro' the
507 // BlockContexts constructed on each iteration. (Moving is more
508 // straight-forward than mutable borrows in this instance.)
509 let mut builder = MovePathDataBuilder {
511 pre_move_paths: Vec::new(),
512 rev_lookup: MovePathLookup::new(),
516 let loc_map_bb = &mut loc_map[bb.index()];
517 let bb_data = mir.basic_block_data(bb);
519 debug_assert!(loc_map_bb.len() == 0);
520 let len = bb_data.statements.len();
521 loc_map_bb.fill_to(len);
522 debug_assert!(loc_map_bb.len() == len + 1);
524 let mut bb_ctxt = BlockContext {
528 path_map: &mut path_map,
529 loc_map_bb: loc_map_bb,
532 for (i, stmt) in bb_data.statements.iter().enumerate() {
533 let source = Location { block: bb, index: i };
535 StatementKind::Assign(ref lval, ref rval) => {
536 // ensure MovePath created for `lval`.
537 bb_ctxt.builder.move_path_for(lval);
540 Rvalue::Use(ref operand) => {
541 bb_ctxt.on_operand(SK::Use, operand, source)
543 Rvalue::Repeat(ref operand, ref _const) =>
544 bb_ctxt.on_operand(SK::Repeat, operand, source),
545 Rvalue::Cast(ref _kind, ref operand, ref _ty) =>
546 bb_ctxt.on_operand(SK::Cast, operand, source),
547 Rvalue::BinaryOp(ref _binop, ref operand1, ref operand2) => {
548 bb_ctxt.on_operand(SK::BinaryOp, operand1, source);
549 bb_ctxt.on_operand(SK::BinaryOp, operand2, source);
551 Rvalue::UnaryOp(ref _unop, ref operand) => {
552 bb_ctxt.on_operand(SK::UnaryOp, operand, source);
554 Rvalue::Box(ref _ty) => {
555 // this is creating uninitialized
556 // memory that needs to be initialized.
557 let deref_lval = Lvalue::Projection(Box::new( repr::Projection {
559 elem: repr::ProjectionElem::Deref,
561 bb_ctxt.on_move_out_lval(SK::Box, &deref_lval, source);
563 Rvalue::Aggregate(ref _kind, ref operands) => {
564 for operand in operands {
565 bb_ctxt.on_operand(SK::Aggregate, operand, source);
570 Rvalue::InlineAsm { .. } => {}
572 Rvalue::Slice {..} => {
573 bb_ctxt.tcx.sess.bug("cannot move out of slice");
580 match bb_data.terminator().kind {
581 TerminatorKind::Goto { target: _ } | TerminatorKind::Resume => { }
583 TerminatorKind::Return => {
584 let source = Location { block: bb,
585 index: bb_data.statements.len() };
586 let lval = &Lvalue::ReturnPointer.deref();
587 bb_ctxt.on_move_out_lval(SK::Return, lval, source);
590 TerminatorKind::If { ref cond, targets: _ } => {
591 // The `cond` is always of (copyable) type `bool`,
592 // so there will never be anything to move.
596 TerminatorKind::SwitchInt { switch_ty: _, values: _, targets: _, ref discr } |
597 TerminatorKind::Switch { adt_def: _, targets: _, ref discr } => {
598 // The `discr` is not consumed; that is instead
599 // encoded on specific match arms (and for
600 // SwitchInt`, it is always a copyable integer
605 TerminatorKind::Drop { value: ref lval, target: _, unwind: _ } => {
606 let source = Location { block: bb,
607 index: bb_data.statements.len() };
608 bb_ctxt.on_move_out_lval(SK::Drop, lval, source);
611 TerminatorKind::Call { ref func, ref args, ref destination, cleanup: _ } => {
612 let source = Location { block: bb,
613 index: bb_data.statements.len() };
614 bb_ctxt.on_operand(SK::CallFn, func, source);
616 bb_ctxt.on_operand(SK::CallArg, arg, source);
618 if let Some((ref destination, _bb)) = *destination {
619 // Create MovePath for `destination`, then
620 // discard returned index.
621 bb_ctxt.builder.move_path_for(destination);
626 builder = bb_ctxt.builder;
629 // At this point, we may have created some MovePaths that do not
630 // have corresponding entries in the path map.
632 // (For example, creating the path `a.b.c` may, as a side-effect,
633 // create a path for the parent path `a.b`.)
635 // All such paths were not referenced ...
637 // well you know, lets actually try just asserting that the path map *is* complete.
638 assert_eq!(path_map.len(), builder.pre_move_paths.len());
639 path_map.fill_to(builder.pre_move_paths.len() - 1);
641 let pre_move_paths = builder.pre_move_paths;
642 let move_paths: Vec<_> = pre_move_paths.into_iter()
643 .map(|p| p.into_move_path())
647 let mut seen: Vec<_> = move_paths.iter().map(|_| false).collect();
648 for (j, &MoveOut { ref path, ref source }) in moves.iter().enumerate() {
649 debug!("MovePathData moves[{}]: MoveOut {{ path: {:?} = {:?}, source: {:?} }}",
650 j, path, move_paths[path.idx()], source);
651 seen[path.idx()] = true;
653 for (j, path) in move_paths.iter().enumerate() {
655 debug!("MovePathData move_paths[{}]: {:?}", j, path);
658 "done dumping MovePathData"
662 move_paths: MovePathData { move_paths: move_paths, },
664 loc_map: LocMap { map: loc_map },
665 path_map: PathMap { map: path_map },
666 rev_lookup: builder.rev_lookup,
670 struct BlockContext<'b, 'a: 'b, 'tcx: 'a> {
671 tcx: &'b ty::TyCtxt<'tcx>,
672 moves: &'b mut Vec<MoveOut>,
673 builder: MovePathDataBuilder<'a, 'tcx>,
674 path_map: &'b mut Vec<Vec<MoveOutIndex>>,
675 loc_map_bb: &'b mut Vec<Vec<MoveOutIndex>>,
678 impl<'b, 'a: 'b, 'tcx: 'a> BlockContext<'b, 'a, 'tcx> {
679 fn on_move_out_lval(&mut self,
681 lval: &repr::Lvalue<'tcx>,
684 let lval_ty = self.builder.mir.lvalue_ty(tcx, lval);
686 // FIXME: does lvalue_ty ever return TyError, or is it
687 // guaranteed to always return non-Infer/non-Error values?
689 // This code is just trying to avoid creating a MoveOut
690 // entry for values that do not need move semantics.
692 // type_contents is imprecise (may claim needs drop for
693 // types that in fact have no destructor). But that is
694 // still usable for our purposes here.
695 let consumed = lval_ty.to_ty(tcx).type_contents(tcx).needs_drop(tcx);
698 debug!("ctxt: {:?} no consume of lval: {:?} of type {:?}",
699 stmt_kind, lval, lval_ty);
702 let i = source.index;
703 let index = MoveOutIndex::new(self.moves.len());
705 let path = self.builder.move_path_for(lval);
706 self.moves.push(MoveOut { path: path, source: source.clone() });
707 self.path_map.fill_to(path.idx());
709 debug!("ctxt: {:?} add consume of lval: {:?} \
711 to path_map for path: {:?} and \
712 to loc_map for loc: {:?}",
713 stmt_kind, lval, index, path, source);
715 debug_assert!(path.idx() < self.path_map.len());
716 // this is actually a questionable assert; at the very
717 // least, incorrect input code can probably cause it to
719 assert!(self.path_map[path.idx()].iter().find(|idx| **idx == index).is_none());
720 self.path_map[path.idx()].push(index);
722 debug_assert!(i < self.loc_map_bb.len());
723 debug_assert!(self.loc_map_bb[i].iter().find(|idx| **idx == index).is_none());
724 self.loc_map_bb[i].push(index);
727 fn on_operand(&mut self, stmt_kind: StmtKind, operand: &repr::Operand<'tcx>, source: Location) {
729 repr::Operand::Constant(..) => {} // not-a-move
730 repr::Operand::Consume(ref lval) => { // a move
731 self.on_move_out_lval(stmt_kind, lval, source);
737 impl<'tcx> BitDenotation for MoveData<'tcx>{
739 fn bits_per_block(&self) -> usize {
742 fn interpret(&self, idx: usize) -> &Self::Bit {