src/librustc_trans/mir/analyze.rs

   1 // Copyright 2012-2014 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 //! An analysis to determine which locals require allocas and
  12 //! which do not.
  13
  14 use rustc_data_structures::bitvec::BitVector;
  15 use rustc_data_structures::indexed_vec::{Idx, IndexVec};
  16 use rustc::mir::repr as mir;
  17 use rustc::mir::repr::TerminatorKind;
  18 use rustc::mir::repr::Location;
  19 use rustc::mir::visit::{Visitor, LvalueContext};
  20 use rustc::mir::traversal;
  21 use common::{self, Block, BlockAndBuilder};
  22 use glue;
  23 use std::iter;
  24 use super::rvalue;
  25
  26 pub fn lvalue_locals<'bcx, 'tcx>(bcx: Block<'bcx,'tcx>,
  27                                  mir: &mir::Mir<'tcx>) -> BitVector {
  28     let bcx = bcx.build();
  29     let mut analyzer = LocalAnalyzer::new(mir, &bcx);
  30
  31     analyzer.visit_mir(mir);
  32
  33     let local_types = mir.arg_decls.iter().map(|a| a.ty)
  34                .chain(mir.var_decls.iter().map(|v| v.ty))
  35                .chain(mir.temp_decls.iter().map(|t| t.ty))
  36                .chain(iter::once(mir.return_ty));
  37     for (index, ty) in local_types.enumerate() {
  38         let ty = bcx.monomorphize(&ty);
  39         debug!("local {} has type {:?}", index, ty);
  40         if ty.is_scalar() ||
  41             ty.is_unique() ||
  42             ty.is_region_ptr() ||
  43             ty.is_simd() ||
  44             common::type_is_zero_size(bcx.ccx(), ty)
  45         {
  46             // These sorts of types are immediates that we can store
  47             // in an ValueRef without an alloca.
  48             assert!(common::type_is_immediate(bcx.ccx(), ty) ||
  49                     common::type_is_fat_ptr(bcx.tcx(), ty));
  50         } else if common::type_is_imm_pair(bcx.ccx(), ty) {
  51             // We allow pairs and uses of any of their 2 fields.
  52         } else if !analyzer.seen_assigned.contains(index) {
  53             // No assignment has been seen, which means that
  54             // either the local has been marked as lvalue
  55             // already, or there is no possible initialization
  56             // for the local, making any reads invalid.
  57             // This is useful in weeding out dead temps.
  58         } else {
  59             // These sorts of types require an alloca. Note that
  60             // type_is_immediate() may *still* be true, particularly
  61             // for newtypes, but we currently force some types
  62             // (e.g. structs) into an alloca unconditionally, just so
  63             // that we don't have to deal with having two pathways
  64             // (gep vs extractvalue etc).
  65             analyzer.mark_as_lvalue(mir::Local::new(index));
  66         }
  67     }
  68
  69     analyzer.lvalue_locals
  70 }
  71
  72 struct LocalAnalyzer<'mir, 'bcx: 'mir, 'tcx: 'bcx> {
  73     mir: &'mir mir::Mir<'tcx>,
  74     bcx: &'mir BlockAndBuilder<'bcx, 'tcx>,
  75     lvalue_locals: BitVector,
  76     seen_assigned: BitVector
  77 }
  78
  79 impl<'mir, 'bcx, 'tcx> LocalAnalyzer<'mir, 'bcx, 'tcx> {
  80     fn new(mir: &'mir mir::Mir<'tcx>,
  81            bcx: &'mir BlockAndBuilder<'bcx, 'tcx>)
  82            -> LocalAnalyzer<'mir, 'bcx, 'tcx> {
  83         let local_count = mir.count_locals();
  84         LocalAnalyzer {
  85             mir: mir,
  86             bcx: bcx,
  87             lvalue_locals: BitVector::new(local_count),
  88             seen_assigned: BitVector::new(local_count)
  89         }
  90     }
  91
  92     fn mark_as_lvalue(&mut self, local: mir::Local) {
  93         debug!("marking {:?} as lvalue", local);
  94         self.lvalue_locals.insert(local.index());
  95     }
  96
  97     fn mark_assigned(&mut self, local: mir::Local) {
  98         if !self.seen_assigned.insert(local.index()) {
  99             self.mark_as_lvalue(local);
 100         }
 101     }
 102 }
 103
 104 impl<'mir, 'bcx, 'tcx> Visitor<'tcx> for LocalAnalyzer<'mir, 'bcx, 'tcx> {
 105     fn visit_assign(&mut self,
 106                     block: mir::BasicBlock,
 107                     lvalue: &mir::Lvalue<'tcx>,
 108                     rvalue: &mir::Rvalue<'tcx>,
 109                     location: Location) {
 110         debug!("visit_assign(block={:?}, lvalue={:?}, rvalue={:?})", block, lvalue, rvalue);
 111
 112         if let Some(index) = self.mir.local_index(lvalue) {
 113             self.mark_assigned(index);
 114             if !rvalue::rvalue_creates_operand(self.mir, self.bcx, rvalue) {
 115                 self.mark_as_lvalue(index);
 116             }
 117         } else {
 118             self.visit_lvalue(lvalue, LvalueContext::Store, location);
 119         }
 120
 121         self.visit_rvalue(rvalue, location);
 122     }
 123
 124     fn visit_terminator_kind(&mut self,
 125                              block: mir::BasicBlock,
 126                              kind: &mir::TerminatorKind<'tcx>,
 127                              location: Location) {
 128         match *kind {
 129             mir::TerminatorKind::Call {
 130                 func: mir::Operand::Constant(mir::Constant {
 131                     literal: mir::Literal::Item { def_id, .. }, ..
 132                 }),
 133                 ref args, ..
 134             } if Some(def_id) == self.bcx.tcx().lang_items.box_free_fn() => {
 135                 // box_free(x) shares with `drop x` the property that it
 136                 // is not guaranteed to be statically dominated by the
 137                 // definition of x, so x must always be in an alloca.
 138                 if let mir::Operand::Consume(ref lvalue) = args[0] {
 139                     self.visit_lvalue(lvalue, LvalueContext::Drop, location);
 140                 }
 141             }
 142             _ => {}
 143         }
 144
 145         self.super_terminator_kind(block, kind, location);
 146     }
 147
 148     fn visit_lvalue(&mut self,
 149                     lvalue: &mir::Lvalue<'tcx>,
 150                     context: LvalueContext,
 151                     location: Location) {
 152         debug!("visit_lvalue(lvalue={:?}, context={:?})", lvalue, context);
 153
 154         // Allow uses of projections of immediate pair fields.
 155         if let mir::Lvalue::Projection(ref proj) = *lvalue {
 156             if self.mir.local_index(&proj.base).is_some() {
 157                 let ty = proj.base.ty(self.mir, self.bcx.tcx());
 158
 159                 let ty = self.bcx.monomorphize(&ty.to_ty(self.bcx.tcx()));
 160                 if common::type_is_imm_pair(self.bcx.ccx(), ty) {
 161                     if let mir::ProjectionElem::Field(..) = proj.elem {
 162                         if let LvalueContext::Consume = context {
 163                             return;
 164                         }
 165                     }
 166                 }
 167             }
 168         }
 169
 170         if let Some(index) = self.mir.local_index(lvalue) {
 171             match context {
 172                 LvalueContext::Call => {
 173                     self.mark_assigned(index);
 174                 }
 175
 176                 LvalueContext::StorageLive |
 177                 LvalueContext::StorageDead |
 178                 LvalueContext::Consume => {}
 179
 180                 LvalueContext::Store |
 181                 LvalueContext::Inspect |
 182                 LvalueContext::Borrow { .. } |
 183                 LvalueContext::Slice { .. } |
 184                 LvalueContext::Projection => {
 185                     self.mark_as_lvalue(index);
 186                 }
 187
 188                 LvalueContext::Drop => {
 189                     let ty = lvalue.ty(self.mir, self.bcx.tcx());
 190                     let ty = self.bcx.monomorphize(&ty.to_ty(self.bcx.tcx()));
 191
 192                     // Only need the lvalue if we're actually dropping it.
 193                     if glue::type_needs_drop(self.bcx.tcx(), ty) {
 194                         self.mark_as_lvalue(index);
 195                     }
 196                 }
 197             }
 198         }
 199
 200         // A deref projection only reads the pointer, never needs the lvalue.
 201         if let mir::Lvalue::Projection(ref proj) = *lvalue {
 202             if let mir::ProjectionElem::Deref = proj.elem {
 203                 return self.visit_lvalue(&proj.base, LvalueContext::Consume, location);
 204             }
 205         }
 206
 207         self.super_lvalue(lvalue, context, location);
 208     }
 209 }
 210
 211 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
 212 pub enum CleanupKind {
 213     NotCleanup,
 214     Funclet,
 215     Internal { funclet: mir::BasicBlock }
 216 }
 217
 218 pub fn cleanup_kinds<'bcx,'tcx>(_bcx: Block<'bcx,'tcx>,
 219                                 mir: &mir::Mir<'tcx>)
 220                                 -> IndexVec<mir::BasicBlock, CleanupKind>
 221 {
 222     fn discover_masters<'tcx>(result: &mut IndexVec<mir::BasicBlock, CleanupKind>,
 223                               mir: &mir::Mir<'tcx>) {
 224         for (bb, data) in mir.basic_blocks().iter_enumerated() {
 225             match data.terminator().kind {
 226                 TerminatorKind::Goto { .. } |
 227                 TerminatorKind::Resume |
 228                 TerminatorKind::Return |
 229                 TerminatorKind::Unreachable |
 230                 TerminatorKind::If { .. } |
 231                 TerminatorKind::Switch { .. } |
 232                 TerminatorKind::SwitchInt { .. } => {
 233                     /* nothing to do */
 234                 }
 235                 TerminatorKind::Call { cleanup: unwind, .. } |
 236                 TerminatorKind::Assert { cleanup: unwind, .. } |
 237                 TerminatorKind::DropAndReplace { unwind, .. } |
 238                 TerminatorKind::Drop { unwind, .. } => {
 239                     if let Some(unwind) = unwind {
 240                         debug!("cleanup_kinds: {:?}/{:?} registering {:?} as funclet",
 241                                bb, data, unwind);
 242                         result[unwind] = CleanupKind::Funclet;
 243                     }
 244                 }
 245             }
 246         }
 247     }
 248
 249     fn propagate<'tcx>(result: &mut IndexVec<mir::BasicBlock, CleanupKind>,
 250                        mir: &mir::Mir<'tcx>) {
 251         let mut funclet_succs = IndexVec::from_elem(None, mir.basic_blocks());
 252
 253         let mut set_successor = |funclet: mir::BasicBlock, succ| {
 254             match funclet_succs[funclet] {
 255                 ref mut s @ None => {
 256                     debug!("set_successor: updating successor of {:?} to {:?}",
 257                            funclet, succ);
 258                     *s = Some(succ);
 259                 },
 260                 Some(s) => if s != succ {
 261                     span_bug!(mir.span, "funclet {:?} has 2 parents - {:?} and {:?}",
 262                               funclet, s, succ);
 263                 }
 264             }
 265         };
 266
 267         for (bb, data) in traversal::reverse_postorder(mir) {
 268             let funclet = match result[bb] {
 269                 CleanupKind::NotCleanup => continue,
 270                 CleanupKind::Funclet => bb,
 271                 CleanupKind::Internal { funclet } => funclet,
 272             };
 273
 274             debug!("cleanup_kinds: {:?}/{:?}/{:?} propagating funclet {:?}",
 275                    bb, data, result[bb], funclet);
 276
 277             for &succ in data.terminator().successors().iter() {
 278                 let kind = result[succ];
 279                 debug!("cleanup_kinds: propagating {:?} to {:?}/{:?}",
 280                        funclet, succ, kind);
 281                 match kind {
 282                     CleanupKind::NotCleanup => {
 283                         result[succ] = CleanupKind::Internal { funclet: funclet };
 284                     }
 285                     CleanupKind::Funclet => {
 286                         set_successor(funclet, succ);
 287                     }
 288                     CleanupKind::Internal { funclet: succ_funclet } => {
 289                         if funclet != succ_funclet {
 290                             // `succ` has 2 different funclet going into it, so it must
 291                             // be a funclet by itself.
 292
 293                             debug!("promoting {:?} to a funclet and updating {:?}", succ,
 294                                    succ_funclet);
 295                             result[succ] = CleanupKind::Funclet;
 296                             set_successor(succ_funclet, succ);
 297                             set_successor(funclet, succ);
 298                         }
 299                     }
 300                 }
 301             }
 302         }
 303     }
 304
 305     let mut result = IndexVec::from_elem(CleanupKind::NotCleanup, mir.basic_blocks());
 306
 307     discover_masters(&mut result, mir);
 308     propagate(&mut result, mir);
 309     debug!("cleanup_kinds: result={:?}", result);
 310     result
 311 }