src/librustc_mir/borrow_check/nll/type_check/liveness/liveness_map.rs

   1 // Copyright 2018 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 //! For the NLL computation, we need to compute liveness, but only for those
  12 //! local variables whose types contain regions. The others are not of interest
  13 //! to us. This file defines a new index type (LiveVar) that indexes into
  14 //! a list of "variables whose type contain regions". It also defines a map from
  15 //! Local to LiveVar and vice versa -- this map can be given to the
  16 //! liveness code so that it only operates over variables with regions in their
  17 //! types, instead of all variables.
  18
  19 use borrow_check::nll::ToRegionVid;
  20 use borrow_check::nll::facts::{AllFacts, AllFactsExt};
  21 use rustc::mir::{Local, Mir};
  22 use rustc::ty::{RegionVid, TyCtxt};
  23 use rustc_data_structures::fx::FxHashSet;
  24 use rustc_data_structures::indexed_vec::{Idx, IndexVec};
  25 use util::liveness::LiveVariableMap;
  26 use rustc_serialize::{Decodable, Decoder};
  27
  28 /// Map between Local and LiveVar indices: the purpose of this
  29 /// map is to define the subset of local variables for which we need
  30 /// to do a liveness computation. We only need to compute whether a
  31 /// variable `X` is live if that variable contains some region `R` in
  32 /// its type where `R` is not known to outlive a free region (i.e.,
  33 /// where `R` may be valid for just a subset of the fn body).
  34 crate struct NllLivenessMap {
  35     /// For each local variable, contains `Some(i)` if liveness is
  36     /// needed for this variable.
  37     pub from_local: IndexVec<Local, Option<LiveVar>>,
  38
  39     /// For each `LiveVar`, maps back to the original `Local` index.
  40     pub to_local: IndexVec<LiveVar, Local>,
  41 }
  42
  43 impl LiveVariableMap for NllLivenessMap {
  44     fn from_local(&self, local: Local) -> Option<Self::LiveVar> {
  45         self.from_local[local]
  46     }
  47
  48     type LiveVar = LiveVar;
  49
  50     fn from_live_var(&self, local: Self::LiveVar) -> Local {
  51         self.to_local[local]
  52     }
  53
  54     fn num_variables(&self) -> usize {
  55         self.to_local.len()
  56     }
  57 }
  58
  59 impl NllLivenessMap {
  60     crate fn compute(
  61         tcx: TyCtxt<'_, '_, 'tcx>,
  62         free_regions: &FxHashSet<RegionVid>,
  63         mir: &Mir<'tcx>,
  64     ) -> Self {
  65         let mut to_local = IndexVec::default();
  66         let facts_enabled = AllFacts::enabled(tcx);
  67         let from_local: IndexVec<Local, Option<_>> = mir.local_decls
  68             .iter_enumerated()
  69             .map(|(local, local_decl)| {
  70                 if tcx.all_free_regions_meet(&local_decl.ty, |r| {
  71                     free_regions.contains(&r.to_region_vid())
  72                 }) && !facts_enabled {
  73                     // If all the regions in the type are free regions
  74                     // (or there are no regions), then we don't need
  75                     // to track liveness for this variable.
  76                     None
  77                 } else {
  78                     Some(to_local.push(local))
  79                 }
  80             })
  81             .collect();
  82
  83         debug!("{} total variables", mir.local_decls.len());
  84         debug!("{} variables need liveness", to_local.len());
  85         debug!("{} regions outlive free regions", free_regions.len());
  86
  87         Self {
  88             from_local,
  89             to_local,
  90         }
  91     }
  92
  93     /// True if there are no local variables that need liveness computation.
  94     crate fn is_empty(&self) -> bool {
  95         self.to_local.is_empty()
  96     }
  97 }
  98
  99 /// Index given to each local variable for which we need to
 100 /// compute liveness information. For many locals, we are able to
 101 /// skip liveness information: for example, those variables whose
 102 /// types contain no regions.
 103 newtype_index! {
 104     pub struct LiveVar { .. }
 105 }