src/librustc_codegen_ssa/mir/analyze.rs

   1 //! An analysis to determine which locals require allocas and
   2 //! which do not.
   3
   4 use rustc_data_structures::bit_set::BitSet;
   5 use rustc_data_structures::graph::dominators::Dominators;
   6 use rustc_data_structures::indexed_vec::{Idx, IndexVec};
   7 use rustc::mir::{self, Location, TerminatorKind};
   8 use rustc::mir::visit::{Visitor, PlaceContext, MutatingUseContext, NonMutatingUseContext};
   9 use rustc::mir::traversal;
  10 use rustc::ty;
  11 use rustc::ty::layout::{LayoutOf, HasTyCtxt};
  12 use super::FunctionCx;
  13 use crate::traits::*;
  14
  15 pub fn non_ssa_locals<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>>(
  16     fx: &FunctionCx<'a, 'tcx, Bx>,
  17 ) -> BitSet<mir::Local> {
  18     let mir = fx.mir;
  19     let mut analyzer = LocalAnalyzer::new(fx);
  20
  21     analyzer.visit_body(mir);
  22
  23     for (index, ty) in mir.local_decls.iter().map(|l| l.ty).enumerate() {
  24         let ty = fx.monomorphize(&ty);
  25         debug!("local {} has type {:?}", index, ty);
  26         let layout = fx.cx.layout_of(ty);
  27         if fx.cx.is_backend_immediate(layout) {
  28             // These sorts of types are immediates that we can store
  29             // in an Value without an alloca.
  30         } else if fx.cx.is_backend_scalar_pair(layout) {
  31             // We allow pairs and uses of any of their 2 fields.
  32         } else {
  33             // These sorts of types require an alloca. Note that
  34             // is_llvm_immediate() may *still* be true, particularly
  35             // for newtypes, but we currently force some types
  36             // (e.g., structs) into an alloca unconditionally, just so
  37             // that we don't have to deal with having two pathways
  38             // (gep vs extractvalue etc).
  39             analyzer.not_ssa(mir::Local::new(index));
  40         }
  41     }
  42
  43     analyzer.non_ssa_locals
  44 }
  45
  46 struct LocalAnalyzer<'mir, 'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> {
  47     fx: &'mir FunctionCx<'a, 'tcx, Bx>,
  48     dominators: Dominators<mir::BasicBlock>,
  49     non_ssa_locals: BitSet<mir::Local>,
  50     // The location of the first visited direct assignment to each
  51     // local, or an invalid location (out of bounds `block` index).
  52     first_assignment: IndexVec<mir::Local, Location>,
  53 }
  54
  55 impl<Bx: BuilderMethods<'a, 'tcx>> LocalAnalyzer<'mir, 'a, 'tcx, Bx> {
  56     fn new(fx: &'mir FunctionCx<'a, 'tcx, Bx>) -> Self {
  57         let invalid_location =
  58             mir::BasicBlock::new(fx.mir.basic_blocks().len()).start_location();
  59         let mut analyzer = LocalAnalyzer {
  60             fx,
  61             dominators: fx.mir.dominators(),
  62             non_ssa_locals: BitSet::new_empty(fx.mir.local_decls.len()),
  63             first_assignment: IndexVec::from_elem(invalid_location, &fx.mir.local_decls)
  64         };
  65
  66         // Arguments get assigned to by means of the function being called
  67         for arg in fx.mir.args_iter() {
  68             analyzer.first_assignment[arg] = mir::START_BLOCK.start_location();
  69         }
  70
  71         analyzer
  72     }
  73
  74     fn first_assignment(&self, local: mir::Local) -> Option<Location> {
  75         let location = self.first_assignment[local];
  76         if location.block.index() < self.fx.mir.basic_blocks().len() {
  77             Some(location)
  78         } else {
  79             None
  80         }
  81     }
  82
  83     fn not_ssa(&mut self, local: mir::Local) {
  84         debug!("marking {:?} as non-SSA", local);
  85         self.non_ssa_locals.insert(local);
  86     }
  87
  88     fn assign(&mut self, local: mir::Local, location: Location) {
  89         if self.first_assignment(local).is_some() {
  90             self.not_ssa(local);
  91         } else {
  92             self.first_assignment[local] = location;
  93         }
  94     }
  95
  96     fn process_place(&mut self,
  97                      place_ref: &mir::PlaceRef<'_, 'tcx>,
  98                      context: PlaceContext,
  99                      location: Location) {
 100         let cx = self.fx.cx;
 101
 102         if let Some(proj) = place_ref.projection {
 103             // Allow uses of projections that are ZSTs or from scalar fields.
 104             let is_consume = match context {
 105                 PlaceContext::NonMutatingUse(NonMutatingUseContext::Copy) |
 106                 PlaceContext::NonMutatingUse(NonMutatingUseContext::Move) => true,
 107                 _ => false
 108             };
 109             if is_consume {
 110                 let base_ty =
 111                     mir::Place::ty_from(place_ref.base, &proj.base, self.fx.mir, cx.tcx());
 112                 let base_ty = self.fx.monomorphize(&base_ty);
 113
 114                 // ZSTs don't require any actual memory access.
 115                 let elem_ty = base_ty
 116                     .projection_ty(cx.tcx(), &proj.elem)
 117                     .ty;
 118                 let elem_ty = self.fx.monomorphize(&elem_ty);
 119                 if cx.layout_of(elem_ty).is_zst() {
 120                     return;
 121                 }
 122
 123                 if let mir::ProjectionElem::Field(..) = proj.elem {
 124                     let layout = cx.layout_of(base_ty.ty);
 125                     if cx.is_backend_immediate(layout) || cx.is_backend_scalar_pair(layout) {
 126                         // Recurse with the same context, instead of `Projection`,
 127                         // potentially stopping at non-operand projections,
 128                         // which would trigger `not_ssa` on locals.
 129                         self.process_place(
 130                             &mir::PlaceRef {
 131                                 base: place_ref.base,
 132                                 projection: &proj.base,
 133                             },
 134                             context,
 135                             location,
 136                         );
 137                         return;
 138                     }
 139                 }
 140             }
 141
 142             // A deref projection only reads the pointer, never needs the place.
 143             if let mir::ProjectionElem::Deref = proj.elem {
 144                 self.process_place(
 145                     &mir::PlaceRef {
 146                         base: place_ref.base,
 147                         projection: &proj.base,
 148                     },
 149                     PlaceContext::NonMutatingUse(NonMutatingUseContext::Copy),
 150                     location
 151                 );
 152                 return;
 153             }
 154         }
 155
 156         // FIXME this is super_place code, is repeated here to avoid cloning place or changing
 157         // visit_place API
 158         let mut context = context;
 159
 160         if place_ref.projection.is_some() {
 161             context = if context.is_mutating_use() {
 162                 PlaceContext::MutatingUse(MutatingUseContext::Projection)
 163             } else {
 164                 PlaceContext::NonMutatingUse(NonMutatingUseContext::Projection)
 165             };
 166         }
 167
 168         self.visit_place_base(place_ref.base, context, location);
 169
 170         if let Some(box proj) = place_ref.projection {
 171             self.visit_projection(place_ref.base, proj, context, location);
 172         }
 173     }
 174
 175 }
 176
 177 impl<'mir, 'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> Visitor<'tcx>
 178     for LocalAnalyzer<'mir, 'a, 'tcx, Bx>
 179 {
 180     fn visit_assign(&mut self,
 181                     place: &mir::Place<'tcx>,
 182                     rvalue: &mir::Rvalue<'tcx>,
 183                     location: Location) {
 184         debug!("visit_assign(place={:?}, rvalue={:?})", place, rvalue);
 185
 186         if let mir::Place {
 187             base: mir::PlaceBase::Local(index),
 188             projection: None,
 189         } = *place {
 190             self.assign(index, location);
 191             if !self.fx.rvalue_creates_operand(rvalue) {
 192                 self.not_ssa(index);
 193             }
 194         } else {
 195             self.visit_place(
 196                 place,
 197                 PlaceContext::MutatingUse(MutatingUseContext::Store),
 198                 location
 199             );
 200         }
 201
 202         self.visit_rvalue(rvalue, location);
 203     }
 204
 205     fn visit_terminator_kind(&mut self,
 206                              kind: &mir::TerminatorKind<'tcx>,
 207                              location: Location) {
 208         let check = match *kind {
 209             mir::TerminatorKind::Call {
 210                 func: mir::Operand::Constant(ref c),
 211                 ref args, ..
 212             } => match c.ty.sty {
 213                 ty::FnDef(did, _) => Some((did, args)),
 214                 _ => None,
 215             },
 216             _ => None,
 217         };
 218         if let Some((def_id, args)) = check {
 219             if Some(def_id) == self.fx.cx.tcx().lang_items().box_free_fn() {
 220                 // box_free(x) shares with `drop x` the property that it
 221                 // is not guaranteed to be statically dominated by the
 222                 // definition of x, so x must always be in an alloca.
 223                 if let mir::Operand::Move(ref place) = args[0] {
 224                     self.visit_place(
 225                         place,
 226                         PlaceContext::MutatingUse(MutatingUseContext::Drop),
 227                         location
 228                     );
 229                 }
 230             }
 231         }
 232
 233         self.super_terminator_kind(kind, location);
 234     }
 235
 236     fn visit_place(&mut self,
 237                    place: &mir::Place<'tcx>,
 238                    context: PlaceContext,
 239                    location: Location) {
 240         debug!("visit_place(place={:?}, context={:?})", place, context);
 241         self.process_place(&place.as_place_ref(), context, location);
 242     }
 243
 244     fn visit_local(&mut self,
 245                    &local: &mir::Local,
 246                    context: PlaceContext,
 247                    location: Location) {
 248         match context {
 249             PlaceContext::MutatingUse(MutatingUseContext::Call) => {
 250                 self.assign(local, location);
 251             }
 252
 253             PlaceContext::NonUse(_) |
 254             PlaceContext::MutatingUse(MutatingUseContext::Retag) => {}
 255
 256             PlaceContext::NonMutatingUse(NonMutatingUseContext::Copy) |
 257             PlaceContext::NonMutatingUse(NonMutatingUseContext::Move) => {
 258                 // Reads from uninitialized variables (e.g., in dead code, after
 259                 // optimizations) require locals to be in (uninitialized) memory.
 260                 // N.B., there can be uninitialized reads of a local visited after
 261                 // an assignment to that local, if they happen on disjoint paths.
 262                 let ssa_read = match self.first_assignment(local) {
 263                     Some(assignment_location) => {
 264                         assignment_location.dominates(location, &self.dominators)
 265                     }
 266                     None => false
 267                 };
 268                 if !ssa_read {
 269                     self.not_ssa(local);
 270                 }
 271             }
 272
 273             PlaceContext::NonMutatingUse(NonMutatingUseContext::Inspect) |
 274             PlaceContext::MutatingUse(MutatingUseContext::Store) |
 275             PlaceContext::MutatingUse(MutatingUseContext::AsmOutput) |
 276             PlaceContext::MutatingUse(MutatingUseContext::Borrow) |
 277             PlaceContext::MutatingUse(MutatingUseContext::Projection) |
 278             PlaceContext::NonMutatingUse(NonMutatingUseContext::SharedBorrow) |
 279             PlaceContext::NonMutatingUse(NonMutatingUseContext::UniqueBorrow) |
 280             PlaceContext::NonMutatingUse(NonMutatingUseContext::ShallowBorrow) |
 281             PlaceContext::NonMutatingUse(NonMutatingUseContext::Projection) => {
 282                 self.not_ssa(local);
 283             }
 284
 285             PlaceContext::MutatingUse(MutatingUseContext::Drop) => {
 286                 let ty = self.fx.mir.local_decls[local].ty;
 287                 let ty = self.fx.monomorphize(&ty);
 288
 289                 // Only need the place if we're actually dropping it.
 290                 if self.fx.cx.type_needs_drop(ty) {
 291                     self.not_ssa(local);
 292                 }
 293             }
 294         }
 295     }
 296 }
 297
 298 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
 299 pub enum CleanupKind {
 300     NotCleanup,
 301     Funclet,
 302     Internal { funclet: mir::BasicBlock }
 303 }
 304
 305 impl CleanupKind {
 306     pub fn funclet_bb(self, for_bb: mir::BasicBlock) -> Option<mir::BasicBlock> {
 307         match self {
 308             CleanupKind::NotCleanup => None,
 309             CleanupKind::Funclet => Some(for_bb),
 310             CleanupKind::Internal { funclet } => Some(funclet),
 311         }
 312     }
 313 }
 314
 315 pub fn cleanup_kinds(mir: &mir::Body<'_>) -> IndexVec<mir::BasicBlock, CleanupKind> {
 316     fn discover_masters<'tcx>(result: &mut IndexVec<mir::BasicBlock, CleanupKind>,
 317                               mir: &mir::Body<'tcx>) {
 318         for (bb, data) in mir.basic_blocks().iter_enumerated() {
 319             match data.terminator().kind {
 320                 TerminatorKind::Goto { .. } |
 321                 TerminatorKind::Resume |
 322                 TerminatorKind::Abort |
 323                 TerminatorKind::Return |
 324                 TerminatorKind::GeneratorDrop |
 325                 TerminatorKind::Unreachable |
 326                 TerminatorKind::SwitchInt { .. } |
 327                 TerminatorKind::Yield { .. } |
 328                 TerminatorKind::FalseEdges { .. } |
 329                 TerminatorKind::FalseUnwind { .. } => {
 330                     /* nothing to do */
 331                 }
 332                 TerminatorKind::Call { cleanup: unwind, .. } |
 333                 TerminatorKind::Assert { cleanup: unwind, .. } |
 334                 TerminatorKind::DropAndReplace { unwind, .. } |
 335                 TerminatorKind::Drop { unwind, .. } => {
 336                     if let Some(unwind) = unwind {
 337                         debug!("cleanup_kinds: {:?}/{:?} registering {:?} as funclet",
 338                                bb, data, unwind);
 339                         result[unwind] = CleanupKind::Funclet;
 340                     }
 341                 }
 342             }
 343         }
 344     }
 345
 346     fn propagate<'tcx>(result: &mut IndexVec<mir::BasicBlock, CleanupKind>,
 347                        mir: &mir::Body<'tcx>) {
 348         let mut funclet_succs = IndexVec::from_elem(None, mir.basic_blocks());
 349
 350         let mut set_successor = |funclet: mir::BasicBlock, succ| {
 351             match funclet_succs[funclet] {
 352                 ref mut s @ None => {
 353                     debug!("set_successor: updating successor of {:?} to {:?}",
 354                            funclet, succ);
 355                     *s = Some(succ);
 356                 },
 357                 Some(s) => if s != succ {
 358                     span_bug!(mir.span, "funclet {:?} has 2 parents - {:?} and {:?}",
 359                               funclet, s, succ);
 360                 }
 361             }
 362         };
 363
 364         for (bb, data) in traversal::reverse_postorder(mir) {
 365             let funclet = match result[bb] {
 366                 CleanupKind::NotCleanup => continue,
 367                 CleanupKind::Funclet => bb,
 368                 CleanupKind::Internal { funclet } => funclet,
 369             };
 370
 371             debug!("cleanup_kinds: {:?}/{:?}/{:?} propagating funclet {:?}",
 372                    bb, data, result[bb], funclet);
 373
 374             for &succ in data.terminator().successors() {
 375                 let kind = result[succ];
 376                 debug!("cleanup_kinds: propagating {:?} to {:?}/{:?}",
 377                        funclet, succ, kind);
 378                 match kind {
 379                     CleanupKind::NotCleanup => {
 380                         result[succ] = CleanupKind::Internal { funclet };
 381                     }
 382                     CleanupKind::Funclet => {
 383                         if funclet != succ {
 384                             set_successor(funclet, succ);
 385                         }
 386                     }
 387                     CleanupKind::Internal { funclet: succ_funclet } => {
 388                         if funclet != succ_funclet {
 389                             // `succ` has 2 different funclet going into it, so it must
 390                             // be a funclet by itself.
 391
 392                             debug!("promoting {:?} to a funclet and updating {:?}", succ,
 393                                    succ_funclet);
 394                             result[succ] = CleanupKind::Funclet;
 395                             set_successor(succ_funclet, succ);
 396                             set_successor(funclet, succ);
 397                         }
 398                     }
 399                 }
 400             }
 401         }
 402     }
 403
 404     let mut result = IndexVec::from_elem(CleanupKind::NotCleanup, mir.basic_blocks());
 405
 406     discover_masters(&mut result, mir);
 407     propagate(&mut result, mir);
 408     debug!("cleanup_kinds: result={:?}", result);
 409     result
 410 }