src/librustc_mir/borrow_check/nll/escaping_locals.rs

   1 // Copyright 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.
   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 //! Identify those variables whose entire value will eventually be
  12 //! returned from the fn via the RETURN_PLACE. As an optimization, we
  13 //! can skip computing liveness results for those variables. The idea
  14 //! is that the return type of the fn only ever contains free
  15 //! regions. Therefore, the types of those variables are going to
  16 //! ultimately be contrained to outlive those free regions -- since
  17 //! free regions are always live for the entire body, this implies
  18 //! that the liveness results are not important for those regions.
  19 //! This is most important in the "fns" that we create to represent static
  20 //! values, since those are often really quite large, and all regions in them
  21 //! will ultimately be constrained to be `'static`. Two examples:
  22 //!
  23 //! ```
  24 //! fn foo() -> &'static [u32] { &[] }
  25 //! static FOO: &[u32] = &[];
  26 //! ```
  27 //!
  28 //! In both these cases, the return value will only have static lifetime.
  29 //!
  30 //! NB: The simple logic here relies on the fact that outlives
  31 //! relations in our analysis don't have locations. Otherwise, we
  32 //! would have to restrict ourselves to values that are
  33 //! *unconditionally* returned (which would still cover the "big
  34 //! static value" case).
  35 //!
  36 //! The way that this code works is to use union-find -- we iterate
  37 //! over the MIR and union together two variables X and Y if all
  38 //! regions in the value of Y are going to be stored into X -- that
  39 //! is, if `typeof(X): 'a` requires that `typeof(Y): 'a`. This means
  40 //! that e.g. we can union together `x` and `y` if we have something
  41 //! like `x = (y, 22)`, but not something like `x = y.f` (since there
  42 //! may be regions in the type of `y` that do not appear in the field
  43 //! `f`).
  44
  45 use rustc::mir::visit::Visitor;
  46 use rustc::mir::*;
  47
  48 use rustc_data_structures::indexed_vec::Idx;
  49 use rustc_data_structures::unify as ut;
  50
  51 crate struct EscapingLocals {
  52     unification_table: ut::UnificationTable<ut::InPlace<AssignedLocal>>,
  53 }
  54
  55 impl EscapingLocals {
  56     crate fn compute(mir: &Mir<'tcx>) -> Self {
  57         let mut visitor = GatherAssignedLocalsVisitor::new();
  58         visitor.visit_mir(mir);
  59
  60         EscapingLocals {
  61             unification_table: visitor.unification_table,
  62         }
  63     }
  64
  65     /// True if `local` is known to escape into static
  66     /// memory.
  67     crate fn escapes_into_return(&mut self, local: Local) -> bool {
  68         let return_place = AssignedLocal::from(RETURN_PLACE);
  69         let other_place = AssignedLocal::from(local);
  70         self.unification_table.unioned(return_place, other_place)
  71     }
  72 }
  73
  74 /// The MIR visitor gathering the union-find of the locals used in
  75 /// assignments.
  76 struct GatherAssignedLocalsVisitor {
  77     unification_table: ut::UnificationTable<ut::InPlace<AssignedLocal>>,
  78 }
  79
  80 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
  81 struct AssignedLocal(u32);
  82
  83 impl ut::UnifyKey for AssignedLocal {
  84     type Value = ();
  85
  86     fn index(&self) -> u32 {
  87         self.0
  88     }
  89
  90     fn from_index(i: u32) -> AssignedLocal {
  91         AssignedLocal(i)
  92     }
  93
  94     fn tag() -> &'static str {
  95         "AssignedLocal"
  96     }
  97 }
  98
  99 impl From<Local> for AssignedLocal {
 100     fn from(item: Local) -> Self {
 101         // newtype_indexes use usize but are u32s.
 102         assert!(item.index() < ::std::u32::MAX as usize);
 103         AssignedLocal(item.index() as u32)
 104     }
 105 }
 106
 107 impl GatherAssignedLocalsVisitor {
 108     fn new() -> Self {
 109         Self {
 110             unification_table: ut::UnificationTable::new(),
 111         }
 112     }
 113
 114     fn union_locals_if_needed(&mut self, lvalue: Option<Local>, rvalue: Option<Local>) {
 115         if let Some(lvalue) = lvalue {
 116             if let Some(rvalue) = rvalue {
 117                 if lvalue != rvalue {
 118                     debug!("EscapingLocals: union {:?} and {:?}", lvalue, rvalue);
 119                     self.unification_table
 120                         .union(AssignedLocal::from(lvalue), AssignedLocal::from(rvalue));
 121                 }
 122             }
 123         }
 124     }
 125 }
 126
 127 // Returns the potential `Local` associated to this `Place` or `PlaceProjection`
 128 fn find_local_in_place(place: &Place) -> Option<Local> {
 129     match place {
 130         Place::Local(local) => Some(*local),
 131
 132         // If you do e.g. `x = a.f` then only *part* of the type of
 133         // `a` escapes into `x` (the part contained in `f`); if `a`'s
 134         // type has regions that don't appear in `f`, those might not
 135         // escape.
 136         Place::Projection(..) => None,
 137
 138         Place::Static { .. } | Place::Promoted { .. } => None,
 139     }
 140 }
 141
 142 // Returns the potential `Local` in this `Operand`.
 143 fn find_local_in_operand(op: &Operand) -> Option<Local> {
 144     // Conservatively check a subset of `Operand`s we know our
 145     // benchmarks track, for example `html5ever`.
 146     match op {
 147         Operand::Copy(place) | Operand::Move(place) => find_local_in_place(place),
 148         Operand::Constant(_) => None,
 149     }
 150 }
 151
 152 impl Visitor<'tcx> for GatherAssignedLocalsVisitor {
 153     fn visit_mir(&mut self, mir: &Mir<'tcx>) {
 154         // We need as many union-find keys as there are locals
 155         for _ in 0..mir.local_decls.len() {
 156             self.unification_table.new_key(());
 157         }
 158
 159         self.super_mir(mir);
 160     }
 161
 162     fn visit_assign(
 163         &mut self,
 164         block: BasicBlock,
 165         place: &Place<'tcx>,
 166         rvalue: &Rvalue<'tcx>,
 167         location: Location,
 168     ) {
 169         let local = find_local_in_place(place);
 170
 171         // Find those cases where there is a `Place` consumed by
 172         // `rvalue` and we know that all regions in its type will be
 173         // incorporated into `place`, the `Place` we are assigning to.
 174         match rvalue {
 175             // `x = y` is the simplest possible case.
 176             Rvalue::Use(op) => self.union_locals_if_needed(local, find_local_in_operand(op)),
 177
 178             // `X = &'r P` -- the type of `X` will be `&'r T_P`, where
 179             // `T_P` is the type of `P`.
 180             Rvalue::Ref(_, _, place) => {
 181                 // Special case: if you have `X = &*Y` (or `X = &**Y`
 182                 // etc), then the outlives relationships will ensure
 183                 // that all regions in `Y` are constrained by regions
 184                 // in `X` -- this is because the lifetimes of the
 185                 // references we deref through are required to outlive
 186                 // the borrow lifetime `'r` (which appears in `X`).
 187                 //
 188                 // (We don't actually need to check the type of `Y`:
 189                 // since `ProjectionElem::Deref` represents a built-in
 190                 // deref and not an overloaded deref, if the thing we
 191                 // deref through is not a reference, then it must be a
 192                 // `Box` or `*const`, in which case it contains no
 193                 // references.)
 194                 let mut place_ref = place;
 195                 while let Place::Projection(proj) = place_ref {
 196                     if let ProjectionElem::Deref = proj.elem {
 197                         place_ref = &proj.base;
 198                     } else {
 199                         break;
 200                     }
 201                 }
 202
 203                 self.union_locals_if_needed(local, find_local_in_place(place_ref))
 204             }
 205
 206             Rvalue::Cast(kind, op, _) => match kind {
 207                 CastKind::Unsize => {
 208                     // Casting a `&[T; N]` to `&[T]` or `&Foo` to `&Trait` --
 209                     // in both cases, no regions are "lost".
 210                     self.union_locals_if_needed(local, find_local_in_operand(op))
 211                 }
 212                 _ => (),
 213             },
 214
 215             // Constructing an aggregate like `(x,)` or `Foo { x }`
 216             // includes the full type of `x`.
 217             Rvalue::Aggregate(_, ops) => {
 218                 for rvalue in ops.iter().map(find_local_in_operand) {
 219                     self.union_locals_if_needed(local, rvalue);
 220                 }
 221             }
 222
 223             // For other things, be conservative and do not union.
 224             _ => (),
 225         };
 226
 227         self.super_assign(block, place, rvalue, location);
 228     }
 229 }