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: 'a, 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_mir(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: 'mir, 'tcx: 'a, 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
  97 impl<'mir, 'a: 'mir, 'tcx: 'a, Bx: BuilderMethods<'a, 'tcx>> Visitor<'tcx>
  98     for LocalAnalyzer<'mir, 'a, 'tcx, Bx> {
  99     fn visit_assign(&mut self,
 100                     block: mir::BasicBlock,
 101                     place: &mir::Place<'tcx>,
 102                     rvalue: &mir::Rvalue<'tcx>,
 103                     location: Location) {
 104         debug!("visit_assign(block={:?}, place={:?}, rvalue={:?})", block, place, rvalue);
 105
 106         if let mir::Place::Base(mir::PlaceBase::Local(index)) = *place {
 107             self.assign(index, location);
 108             if !self.fx.rvalue_creates_operand(rvalue) {
 109                 self.not_ssa(index);
 110             }
 111         } else {
 112             self.visit_place(
 113                 place,
 114                 PlaceContext::MutatingUse(MutatingUseContext::Store),
 115                 location
 116             );
 117         }
 118
 119         self.visit_rvalue(rvalue, location);
 120     }
 121
 122     fn visit_terminator_kind(&mut self,
 123                              block: mir::BasicBlock,
 124                              kind: &mir::TerminatorKind<'tcx>,
 125                              location: Location) {
 126         let check = match *kind {
 127             mir::TerminatorKind::Call {
 128                 func: mir::Operand::Constant(ref c),
 129                 ref args, ..
 130             } => match c.ty.sty {
 131                 ty::FnDef(did, _) => Some((did, args)),
 132                 _ => None,
 133             },
 134             _ => None,
 135         };
 136         if let Some((def_id, args)) = check {
 137             if Some(def_id) == self.fx.cx.tcx().lang_items().box_free_fn() {
 138                 // box_free(x) shares with `drop x` the property that it
 139                 // is not guaranteed to be statically dominated by the
 140                 // definition of x, so x must always be in an alloca.
 141                 if let mir::Operand::Move(ref place) = args[0] {
 142                     self.visit_place(
 143                         place,
 144                         PlaceContext::MutatingUse(MutatingUseContext::Drop),
 145                         location
 146                     );
 147                 }
 148             }
 149         }
 150
 151         self.super_terminator_kind(block, kind, location);
 152     }
 153
 154     fn visit_place(&mut self,
 155                    place: &mir::Place<'tcx>,
 156                    context: PlaceContext<'tcx>,
 157                    location: Location) {
 158         debug!("visit_place(place={:?}, context={:?})", place, context);
 159         let cx = self.fx.cx;
 160
 161         if let mir::Place::Projection(ref proj) = *place {
 162             // Allow uses of projections that are ZSTs or from scalar fields.
 163             let is_consume = match context {
 164                 PlaceContext::NonMutatingUse(NonMutatingUseContext::Copy) |
 165                 PlaceContext::NonMutatingUse(NonMutatingUseContext::Move) => true,
 166                 _ => false
 167             };
 168             if is_consume {
 169                 let base_ty = proj.base.ty(self.fx.mir, cx.tcx());
 170                 let base_ty = self.fx.monomorphize(&base_ty);
 171
 172                 // ZSTs don't require any actual memory access.
 173                 let elem_ty = base_ty
 174                     .projection_ty(cx.tcx(), &proj.elem)
 175                     .ty;
 176                 let elem_ty = self.fx.monomorphize(&elem_ty);
 177                 if cx.layout_of(elem_ty).is_zst() {
 178                     return;
 179                 }
 180
 181                 if let mir::ProjectionElem::Field(..) = proj.elem {
 182                     let layout = cx.layout_of(base_ty.ty);
 183                     if cx.is_backend_immediate(layout) || cx.is_backend_scalar_pair(layout) {
 184                         // Recurse with the same context, instead of `Projection`,
 185                         // potentially stopping at non-operand projections,
 186                         // which would trigger `not_ssa` on locals.
 187                         self.visit_place(&proj.base, context, location);
 188                         return;
 189                     }
 190                 }
 191             }
 192
 193             // A deref projection only reads the pointer, never needs the place.
 194             if let mir::ProjectionElem::Deref = proj.elem {
 195                 return self.visit_place(
 196                     &proj.base,
 197                     PlaceContext::NonMutatingUse(NonMutatingUseContext::Copy),
 198                     location
 199                 );
 200             }
 201         }
 202
 203         self.super_place(place, context, location);
 204     }
 205
 206     fn visit_local(&mut self,
 207                    &local: &mir::Local,
 208                    context: PlaceContext<'tcx>,
 209                    location: Location) {
 210         match context {
 211             PlaceContext::MutatingUse(MutatingUseContext::Call) => {
 212                 self.assign(local, location);
 213             }
 214
 215             PlaceContext::NonUse(_) |
 216             PlaceContext::MutatingUse(MutatingUseContext::Retag) => {}
 217
 218             PlaceContext::NonMutatingUse(NonMutatingUseContext::Copy) |
 219             PlaceContext::NonMutatingUse(NonMutatingUseContext::Move) => {
 220                 // Reads from uninitialized variables (e.g., in dead code, after
 221                 // optimizations) require locals to be in (uninitialized) memory.
 222                 // N.B., there can be uninitialized reads of a local visited after
 223                 // an assignment to that local, if they happen on disjoint paths.
 224                 let ssa_read = match self.first_assignment(local) {
 225                     Some(assignment_location) => {
 226                         assignment_location.dominates(location, &self.dominators)
 227                     }
 228                     None => false
 229                 };
 230                 if !ssa_read {
 231                     self.not_ssa(local);
 232                 }
 233             }
 234
 235             PlaceContext::NonMutatingUse(NonMutatingUseContext::Inspect) |
 236             PlaceContext::MutatingUse(MutatingUseContext::Store) |
 237             PlaceContext::MutatingUse(MutatingUseContext::AsmOutput) |
 238             PlaceContext::MutatingUse(MutatingUseContext::Borrow(..)) |
 239             PlaceContext::MutatingUse(MutatingUseContext::Projection) |
 240             PlaceContext::NonMutatingUse(NonMutatingUseContext::SharedBorrow(..)) |
 241             PlaceContext::NonMutatingUse(NonMutatingUseContext::UniqueBorrow(..)) |
 242             PlaceContext::NonMutatingUse(NonMutatingUseContext::ShallowBorrow(..)) |
 243             PlaceContext::NonMutatingUse(NonMutatingUseContext::Projection) => {
 244                 self.not_ssa(local);
 245             }
 246
 247             PlaceContext::MutatingUse(MutatingUseContext::Drop) => {
 248                 let ty = mir::Place::Base(mir::PlaceBase::Local(local)).ty(self.fx.mir,
 249                                                                            self.fx.cx.tcx());
 250                 let ty = self.fx.monomorphize(&ty.ty);
 251
 252                 // Only need the place if we're actually dropping it.
 253                 if self.fx.cx.type_needs_drop(ty) {
 254                     self.not_ssa(local);
 255                 }
 256             }
 257         }
 258     }
 259 }
 260
 261 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
 262 pub enum CleanupKind {
 263     NotCleanup,
 264     Funclet,
 265     Internal { funclet: mir::BasicBlock }
 266 }
 267
 268 impl CleanupKind {
 269     pub fn funclet_bb(self, for_bb: mir::BasicBlock) -> Option<mir::BasicBlock> {
 270         match self {
 271             CleanupKind::NotCleanup => None,
 272             CleanupKind::Funclet => Some(for_bb),
 273             CleanupKind::Internal { funclet } => Some(funclet),
 274         }
 275     }
 276 }
 277
 278 pub fn cleanup_kinds<'a, 'tcx>(mir: &mir::Mir<'tcx>) -> IndexVec<mir::BasicBlock, CleanupKind> {
 279     fn discover_masters<'tcx>(result: &mut IndexVec<mir::BasicBlock, CleanupKind>,
 280                               mir: &mir::Mir<'tcx>) {
 281         for (bb, data) in mir.basic_blocks().iter_enumerated() {
 282             match data.terminator().kind {
 283                 TerminatorKind::Goto { .. } |
 284                 TerminatorKind::Resume |
 285                 TerminatorKind::Abort |
 286                 TerminatorKind::Return |
 287                 TerminatorKind::GeneratorDrop |
 288                 TerminatorKind::Unreachable |
 289                 TerminatorKind::SwitchInt { .. } |
 290                 TerminatorKind::Yield { .. } |
 291                 TerminatorKind::FalseEdges { .. } |
 292                 TerminatorKind::FalseUnwind { .. } => {
 293                     /* nothing to do */
 294                 }
 295                 TerminatorKind::Call { cleanup: unwind, .. } |
 296                 TerminatorKind::Assert { cleanup: unwind, .. } |
 297                 TerminatorKind::DropAndReplace { unwind, .. } |
 298                 TerminatorKind::Drop { unwind, .. } => {
 299                     if let Some(unwind) = unwind {
 300                         debug!("cleanup_kinds: {:?}/{:?} registering {:?} as funclet",
 301                                bb, data, unwind);
 302                         result[unwind] = CleanupKind::Funclet;
 303                     }
 304                 }
 305             }
 306         }
 307     }
 308
 309     fn propagate<'tcx>(result: &mut IndexVec<mir::BasicBlock, CleanupKind>,
 310                        mir: &mir::Mir<'tcx>) {
 311         let mut funclet_succs = IndexVec::from_elem(None, mir.basic_blocks());
 312
 313         let mut set_successor = |funclet: mir::BasicBlock, succ| {
 314             match funclet_succs[funclet] {
 315                 ref mut s @ None => {
 316                     debug!("set_successor: updating successor of {:?} to {:?}",
 317                            funclet, succ);
 318                     *s = Some(succ);
 319                 },
 320                 Some(s) => if s != succ {
 321                     span_bug!(mir.span, "funclet {:?} has 2 parents - {:?} and {:?}",
 322                               funclet, s, succ);
 323                 }
 324             }
 325         };
 326
 327         for (bb, data) in traversal::reverse_postorder(mir) {
 328             let funclet = match result[bb] {
 329                 CleanupKind::NotCleanup => continue,
 330                 CleanupKind::Funclet => bb,
 331                 CleanupKind::Internal { funclet } => funclet,
 332             };
 333
 334             debug!("cleanup_kinds: {:?}/{:?}/{:?} propagating funclet {:?}",
 335                    bb, data, result[bb], funclet);
 336
 337             for &succ in data.terminator().successors() {
 338                 let kind = result[succ];
 339                 debug!("cleanup_kinds: propagating {:?} to {:?}/{:?}",
 340                        funclet, succ, kind);
 341                 match kind {
 342                     CleanupKind::NotCleanup => {
 343                         result[succ] = CleanupKind::Internal { funclet };
 344                     }
 345                     CleanupKind::Funclet => {
 346                         if funclet != succ {
 347                             set_successor(funclet, succ);
 348                         }
 349                     }
 350                     CleanupKind::Internal { funclet: succ_funclet } => {
 351                         if funclet != succ_funclet {
 352                             // `succ` has 2 different funclet going into it, so it must
 353                             // be a funclet by itself.
 354
 355                             debug!("promoting {:?} to a funclet and updating {:?}", succ,
 356                                    succ_funclet);
 357                             result[succ] = CleanupKind::Funclet;
 358                             set_successor(succ_funclet, succ);
 359                             set_successor(funclet, succ);
 360                         }
 361                     }
 362                 }
 363             }
 364         }
 365     }
 366
 367     let mut result = IndexVec::from_elem(CleanupKind::NotCleanup, mir.basic_blocks());
 368
 369     discover_masters(&mut result, mir);
 370     propagate(&mut result, mir);
 371     debug!("cleanup_kinds: result={:?}", result);
 372     result
 373 }