src/librustc_mir/transform/check_consts/resolver.rs

   1 //! Propagate `Qualif`s between locals and query the results.
   2 //!
   3 //! This also contains the dataflow analysis used to track `Qualif`s on complex control-flow
   4 //! graphs.
   5
   6 use rustc::mir::visit::Visitor;
   7 use rustc::mir::{self, BasicBlock, Local, Location};
   8 use rustc_index::bit_set::BitSet;
   9
  10 use std::cell::RefCell;
  11 use std::marker::PhantomData;
  12
  13 use crate::dataflow::{self as old_dataflow, generic as dataflow};
  14 use super::{Item, Qualif};
  15 use self::old_dataflow::IndirectlyMutableLocals;
  16
  17 /// A `Visitor` that propagates qualifs between locals. This defines the transfer function of
  18 /// `FlowSensitiveAnalysis` as well as the logic underlying `TempPromotionResolver`.
  19 ///
  20 /// This transfer does nothing when encountering an indirect assignment. Consumers should rely on
  21 /// the `IndirectlyMutableLocals` dataflow pass to see if a `Local` may have become qualified via
  22 /// an indirect assignment or function call.
  23 struct TransferFunction<'a, 'mir, 'tcx, Q> {
  24     item: &'a Item<'mir, 'tcx>,
  25     qualifs_per_local: &'a mut BitSet<Local>,
  26
  27     _qualif: PhantomData<Q>,
  28 }
  29
  30 impl<Q> TransferFunction<'a, 'mir, 'tcx, Q>
  31 where
  32     Q: Qualif,
  33 {
  34     fn new(
  35         item: &'a Item<'mir, 'tcx>,
  36         qualifs_per_local: &'a mut BitSet<Local>,
  37     ) -> Self {
  38         TransferFunction {
  39             item,
  40             qualifs_per_local,
  41             _qualif: PhantomData,
  42         }
  43     }
  44
  45     fn initialize_state(&mut self) {
  46         self.qualifs_per_local.clear();
  47
  48         for arg in self.item.body.args_iter() {
  49             let arg_ty = self.item.body.local_decls[arg].ty;
  50             if Q::in_any_value_of_ty(self.item, arg_ty) {
  51                 self.qualifs_per_local.insert(arg);
  52             }
  53         }
  54     }
  55
  56     fn assign_qualif_direct(&mut self, place: &mir::Place<'tcx>, value: bool) {
  57         debug_assert!(!place.is_indirect());
  58
  59         match (value, place.as_ref()) {
  60             (true, mir::PlaceRef { base: &mir::PlaceBase::Local(local), .. }) => {
  61                 self.qualifs_per_local.insert(local);
  62             }
  63
  64             // For now, we do not clear the qualif if a local is overwritten in full by
  65             // an unqualified rvalue (e.g. `y = 5`). This is to be consistent
  66             // with aggregates where we overwrite all fields with assignments, which would not
  67             // get this feature.
  68             (false, mir::PlaceRef { base: &mir::PlaceBase::Local(_local), projection: &[] }) => {
  69                 // self.qualifs_per_local.remove(*local);
  70             }
  71
  72             _ => {}
  73         }
  74     }
  75
  76     fn apply_call_return_effect(
  77         &mut self,
  78         _block: BasicBlock,
  79         func: &mir::Operand<'tcx>,
  80         args: &[mir::Operand<'tcx>],
  81         return_place: &mir::Place<'tcx>,
  82     ) {
  83         let return_ty = return_place.ty(self.item.body, self.item.tcx).ty;
  84         let qualif = Q::in_call(
  85             self.item,
  86             &|l| self.qualifs_per_local.contains(l),
  87             func,
  88             args,
  89             return_ty,
  90         );
  91         if !return_place.is_indirect() {
  92             self.assign_qualif_direct(return_place, qualif);
  93         }
  94     }
  95 }
  96
  97 impl<Q> Visitor<'tcx> for TransferFunction<'_, '_, 'tcx, Q>
  98 where
  99     Q: Qualif,
 100 {
 101     fn visit_operand(&mut self, operand: &mir::Operand<'tcx>, location: Location) {
 102         self.super_operand(operand, location);
 103
 104         if !Q::IS_CLEARED_ON_MOVE {
 105             return;
 106         }
 107
 108         // If a local with no projections is moved from (e.g. `x` in `y = x`), record that
 109         // it no longer needs to be dropped.
 110         if let mir::Operand::Move(place) = operand {
 111             if let Some(local) = place.as_local() {
 112                 self.qualifs_per_local.remove(local);
 113             }
 114         }
 115     }
 116
 117     fn visit_assign(
 118         &mut self,
 119         place: &mir::Place<'tcx>,
 120         rvalue: &mir::Rvalue<'tcx>,
 121         location: Location,
 122     ) {
 123         let qualif = Q::in_rvalue(self.item, &|l| self.qualifs_per_local.contains(l), rvalue);
 124         if !place.is_indirect() {
 125             self.assign_qualif_direct(place, qualif);
 126         }
 127
 128         // We need to assign qualifs to the left-hand side before visiting `rvalue` since
 129         // qualifs can be cleared on move.
 130         self.super_assign(place, rvalue, location);
 131     }
 132
 133     fn visit_terminator_kind(&mut self, kind: &mir::TerminatorKind<'tcx>, location: Location) {
 134         // The effect of assignment to the return place in `TerminatorKind::Call` is not applied
 135         // here; that occurs in `apply_call_return_effect`.
 136
 137         if let mir::TerminatorKind::DropAndReplace { value, location: dest, .. } = kind {
 138             let qualif = Q::in_operand(self.item, &|l| self.qualifs_per_local.contains(l), value);
 139             if !dest.is_indirect() {
 140                 self.assign_qualif_direct(dest, qualif);
 141             }
 142         }
 143
 144         // We need to assign qualifs to the dropped location before visiting the operand that
 145         // replaces it since qualifs can be cleared on move.
 146         self.super_terminator_kind(kind, location);
 147     }
 148 }
 149
 150 /// Types that can compute the qualifs of each local at each location in a `mir::Body`.
 151 ///
 152 /// Code that wishes to use a `QualifResolver` must call `visit_{statement,terminator}` for each
 153 /// statement or terminator, processing blocks in reverse post-order beginning from the
 154 /// `START_BLOCK`. Calling code may optionally call `get` after visiting each statement or
 155 /// terminator to query the qualification state immediately before that statement or terminator.
 156 ///
 157 /// These conditions are much more restrictive than woud be required by `FlowSensitiveResolver`
 158 /// alone. This is to allow a linear, on-demand `TempPromotionResolver` that can operate
 159 /// efficiently on simple CFGs.
 160 pub trait QualifResolver<Q> {
 161     /// Get the qualifs of each local at the last location visited.
 162     ///
 163     /// This takes `&mut self` so qualifs can be computed lazily.
 164     fn get(&mut self) -> &BitSet<Local>;
 165
 166     /// A convenience method for `self.get().contains(local)`.
 167     fn contains(&mut self, local: Local) -> bool {
 168         self.get().contains(local)
 169     }
 170
 171     /// Resets the resolver to the `START_BLOCK`. This allows a resolver to be reused
 172     /// for multiple passes over a `mir::Body`.
 173     fn reset(&mut self);
 174 }
 175
 176 pub type IndirectlyMutableResults<'mir, 'tcx> =
 177     old_dataflow::DataflowResultsCursor<'mir, 'tcx, IndirectlyMutableLocals<'mir, 'tcx>>;
 178
 179 /// A resolver for qualifs that works on arbitrarily complex CFGs.
 180 ///
 181 /// As soon as a `Local` becomes writable through a reference (as determined by the
 182 /// `IndirectlyMutableLocals` dataflow pass), we must assume that it takes on all other qualifs
 183 /// possible for its type. This is because no effort is made to track qualifs across indirect
 184 /// assignments (e.g. `*p = x` or calls to opaque functions).
 185 ///
 186 /// It is possible to be more precise here by waiting until an indirect assignment actually occurs
 187 /// before marking a borrowed `Local` as qualified.
 188 pub struct FlowSensitiveResolver<'a, 'mir, 'tcx, Q>
 189 where
 190     Q: Qualif,
 191 {
 192     location: Location,
 193     indirectly_mutable_locals: &'a RefCell<IndirectlyMutableResults<'mir, 'tcx>>,
 194     cursor: dataflow::ResultsCursor<'mir, 'tcx, FlowSensitiveAnalysis<'a, 'mir, 'tcx, Q>>,
 195     qualifs_per_local: BitSet<Local>,
 196
 197     /// The value of `Q::in_any_value_of_ty` for each local.
 198     qualifs_in_any_value_of_ty: BitSet<Local>,
 199 }
 200
 201 impl<Q> FlowSensitiveResolver<'a, 'mir, 'tcx, Q>
 202 where
 203     Q: Qualif,
 204 {
 205     pub fn new(
 206         _: Q,
 207         item: &'a Item<'mir, 'tcx>,
 208         indirectly_mutable_locals: &'a RefCell<IndirectlyMutableResults<'mir, 'tcx>>,
 209         dead_unwinds: &BitSet<BasicBlock>,
 210     ) -> Self {
 211         let analysis = FlowSensitiveAnalysis {
 212             item,
 213             _qualif: PhantomData,
 214         };
 215         let results =
 216             dataflow::Engine::new(item.tcx, item.body, item.def_id, dead_unwinds, analysis)
 217                 .iterate_to_fixpoint();
 218         let cursor = dataflow::ResultsCursor::new(item.body, results);
 219
 220         let mut qualifs_in_any_value_of_ty = BitSet::new_empty(item.body.local_decls.len());
 221         for (local, decl) in item.body.local_decls.iter_enumerated() {
 222             if Q::in_any_value_of_ty(item, decl.ty) {
 223                 qualifs_in_any_value_of_ty.insert(local);
 224             }
 225         }
 226
 227         FlowSensitiveResolver {
 228             cursor,
 229             indirectly_mutable_locals,
 230             qualifs_per_local: BitSet::new_empty(item.body.local_decls.len()),
 231             qualifs_in_any_value_of_ty,
 232             location: Location { block: mir::START_BLOCK, statement_index: 0 },
 233         }
 234     }
 235 }
 236
 237 impl<Q> Visitor<'tcx> for FlowSensitiveResolver<'_, '_, 'tcx, Q>
 238 where
 239     Q: Qualif
 240 {
 241     fn visit_statement(&mut self, _: &mir::Statement<'tcx>, location: Location) {
 242         self.location = location;
 243     }
 244
 245     fn visit_terminator(&mut self, _: &mir::Terminator<'tcx>, location: Location) {
 246         self.location = location;
 247     }
 248 }
 249
 250 impl<Q> QualifResolver<Q> for FlowSensitiveResolver<'_, '_, '_, Q>
 251 where
 252     Q: Qualif
 253 {
 254     fn get(&mut self) -> &BitSet<Local> {
 255         let mut indirectly_mutable_locals = self.indirectly_mutable_locals.borrow_mut();
 256
 257         indirectly_mutable_locals.seek(self.location);
 258         self.cursor.seek_before(self.location);
 259
 260         self.qualifs_per_local.overwrite(indirectly_mutable_locals.get());
 261         self.qualifs_per_local.union(self.cursor.get());
 262         self.qualifs_per_local.intersect(&self.qualifs_in_any_value_of_ty);
 263         &self.qualifs_per_local
 264     }
 265
 266     fn contains(&mut self, local: Local) -> bool {
 267         // No need to update the cursor if we know that `Local` cannot possibly be qualified.
 268         if !self.qualifs_in_any_value_of_ty.contains(local) {
 269             return false;
 270         }
 271
 272         // Otherwise, return `true` if this local is qualified or was indirectly mutable at any
 273         // point before this statement.
 274         self.cursor.seek_before(self.location);
 275         if self.cursor.get().contains(local) {
 276             return true;
 277         }
 278
 279         let mut indirectly_mutable_locals = self.indirectly_mutable_locals.borrow_mut();
 280         indirectly_mutable_locals.seek(self.location);
 281         indirectly_mutable_locals.get().contains(local)
 282     }
 283
 284     fn reset(&mut self)  {
 285         self.location = Location { block: mir::START_BLOCK, statement_index: 0 };
 286     }
 287 }
 288
 289 /// The dataflow analysis used to propagate qualifs on arbitrary CFGs.
 290 pub(super) struct FlowSensitiveAnalysis<'a, 'mir, 'tcx, Q> {
 291     item: &'a Item<'mir, 'tcx>,
 292     _qualif: PhantomData<Q>,
 293 }
 294
 295 impl<'a, 'mir, 'tcx, Q> FlowSensitiveAnalysis<'a, 'mir, 'tcx, Q>
 296 where
 297     Q: Qualif,
 298 {
 299     fn transfer_function(
 300         &self,
 301         state: &'a mut BitSet<Local>,
 302     ) -> TransferFunction<'a, 'mir, 'tcx, Q> {
 303         TransferFunction::<Q>::new(self.item, state)
 304     }
 305 }
 306
 307 impl<Q> old_dataflow::BottomValue for FlowSensitiveAnalysis<'_, '_, '_, Q> {
 308     const BOTTOM_VALUE: bool = false;
 309 }
 310
 311 impl<Q> dataflow::Analysis<'tcx> for FlowSensitiveAnalysis<'_, '_, 'tcx, Q>
 312 where
 313     Q: Qualif,
 314 {
 315     type Idx = Local;
 316
 317     const NAME: &'static str = Q::ANALYSIS_NAME;
 318
 319     fn bits_per_block(&self, body: &mir::Body<'tcx>) -> usize {
 320         body.local_decls.len()
 321     }
 322
 323     fn initialize_start_block(&self, _body: &mir::Body<'tcx>, state: &mut BitSet<Self::Idx>) {
 324         self.transfer_function(state).initialize_state();
 325     }
 326
 327     fn apply_statement_effect(
 328         &self,
 329         state: &mut BitSet<Self::Idx>,
 330         statement: &mir::Statement<'tcx>,
 331         location: Location,
 332     ) {
 333         self.transfer_function(state).visit_statement(statement, location);
 334     }
 335
 336     fn apply_terminator_effect(
 337         &self,
 338         state: &mut BitSet<Self::Idx>,
 339         terminator: &mir::Terminator<'tcx>,
 340         location: Location,
 341     ) {
 342         self.transfer_function(state).visit_terminator(terminator, location);
 343     }
 344
 345     fn apply_call_return_effect(
 346         &self,
 347         state: &mut BitSet<Self::Idx>,
 348         block: BasicBlock,
 349         func: &mir::Operand<'tcx>,
 350         args: &[mir::Operand<'tcx>],
 351         return_place: &mir::Place<'tcx>,
 352     ) {
 353         self.transfer_function(state).apply_call_return_effect(block, func, args, return_place)
 354     }
 355 }