src/librustc_mir/transform/promote_consts.rs

   1 // Copyright 2016 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 //! A pass that promotes borrows of constant rvalues.
  12 //!
  13 //! The rvalues considered constant are trees of temps,
  14 //! each with exactly one initialization, and holding
  15 //! a constant value with no interior mutability.
  16 //! They are placed into a new MIR constant body in
  17 //! `promoted` and the borrow rvalue is replaced with
  18 //! a `Literal::Promoted` using the index into `promoted`
  19 //! of that constant MIR.
  20 //!
  21 //! This pass assumes that every use is dominated by an
  22 //! initialization and can otherwise silence errors, if
  23 //! move analysis runs after promotion on broken MIR.
  24
  25 use rustc::mir::*;
  26 use rustc::mir::visit::{PlaceContext, MutVisitor, Visitor};
  27 use rustc::mir::traversal::ReversePostorder;
  28 use rustc::ty::TyCtxt;
  29 use syntax_pos::Span;
  30
  31 use rustc_data_structures::indexed_vec::{IndexVec, Idx};
  32
  33 use std::iter;
  34 use std::mem;
  35 use std::usize;
  36
  37 /// State of a temporary during collection and promotion.
  38 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
  39 pub enum TempState {
  40     /// No references to this temp.
  41     Undefined,
  42     /// One direct assignment and any number of direct uses.
  43     /// A borrow of this temp is promotable if the assigned
  44     /// value is qualified as constant.
  45     Defined {
  46         location: Location,
  47         uses: usize
  48     },
  49     /// Any other combination of assignments/uses.
  50     Unpromotable,
  51     /// This temp was part of an rvalue which got extracted
  52     /// during promotion and needs cleanup.
  53     PromotedOut
  54 }
  55
  56 impl TempState {
  57     pub fn is_promotable(&self) -> bool {
  58         if let TempState::Defined { uses, .. } = *self {
  59             uses > 0
  60         } else {
  61             false
  62         }
  63     }
  64 }
  65
  66 /// A "root candidate" for promotion, which will become the
  67 /// returned value in a promoted MIR, unless it's a subset
  68 /// of a larger candidate.
  69 #[derive(Debug)]
  70 pub enum Candidate {
  71     /// Borrow of a constant temporary.
  72     Ref(Location),
  73
  74     /// Currently applied to function calls where the callee has the unstable
  75     /// `#[rustc_args_required_const]` attribute as well as the SIMD shuffle
  76     /// intrinsic. The intrinsic requires the arguments are indeed constant and
  77     /// the attribute currently provides the semantic requirement that arguments
  78     /// must be constant.
  79     Argument { bb: BasicBlock, index: usize },
  80 }
  81
  82 struct TempCollector<'tcx> {
  83     temps: IndexVec<Local, TempState>,
  84     span: Span,
  85     mir: &'tcx Mir<'tcx>,
  86 }
  87
  88 impl<'tcx> Visitor<'tcx> for TempCollector<'tcx> {
  89     fn visit_local(&mut self,
  90                    &index: &Local,
  91                    context: PlaceContext<'tcx>,
  92                    location: Location) {
  93         // We're only interested in temporaries
  94         if self.mir.local_kind(index) != LocalKind::Temp {
  95             return;
  96         }
  97
  98         // Ignore drops, if the temp gets promoted,
  99         // then it's constant and thus drop is noop.
 100         // Storage live ranges are also irrelevant.
 101         if context.is_drop() || context.is_storage_marker() {
 102             return;
 103         }
 104
 105         let temp = &mut self.temps[index];
 106         if *temp == TempState::Undefined {
 107             match context {
 108                 PlaceContext::Store |
 109                 PlaceContext::AsmOutput |
 110                 PlaceContext::Call => {
 111                     *temp = TempState::Defined {
 112                         location,
 113                         uses: 0
 114                     };
 115                     return;
 116                 }
 117                 _ => { /* mark as unpromotable below */ }
 118             }
 119         } else if let TempState::Defined { ref mut uses, .. } = *temp {
 120             // We always allow borrows, even mutable ones, as we need
 121             // to promote mutable borrows of some ZSTs e.g. `&mut []`.
 122             let allowed_use = match context {
 123                 PlaceContext::Borrow {..} => true,
 124                 _ => context.is_nonmutating_use()
 125             };
 126             if allowed_use {
 127                 *uses += 1;
 128                 return;
 129             }
 130             /* mark as unpromotable below */
 131         }
 132         *temp = TempState::Unpromotable;
 133     }
 134
 135     fn visit_source_info(&mut self, source_info: &SourceInfo) {
 136         self.span = source_info.span;
 137     }
 138 }
 139
 140 pub fn collect_temps(mir: &Mir, rpo: &mut ReversePostorder) -> IndexVec<Local, TempState> {
 141     let mut collector = TempCollector {
 142         temps: IndexVec::from_elem(TempState::Undefined, &mir.local_decls),
 143         span: mir.span,
 144         mir,
 145     };
 146     for (bb, data) in rpo {
 147         collector.visit_basic_block_data(bb, data);
 148     }
 149     collector.temps
 150 }
 151
 152 struct Promoter<'a, 'tcx: 'a> {
 153     source: &'a mut Mir<'tcx>,
 154     promoted: Mir<'tcx>,
 155     temps: &'a mut IndexVec<Local, TempState>,
 156
 157     /// If true, all nested temps are also kept in the
 158     /// source MIR, not moved to the promoted MIR.
 159     keep_original: bool
 160 }
 161
 162 impl<'a, 'tcx> Promoter<'a, 'tcx> {
 163     fn new_block(&mut self) -> BasicBlock {
 164         let span = self.promoted.span;
 165         self.promoted.basic_blocks_mut().push(BasicBlockData {
 166             statements: vec![],
 167             terminator: Some(Terminator {
 168                 source_info: SourceInfo {
 169                     span,
 170                     scope: ARGUMENT_VISIBILITY_SCOPE
 171                 },
 172                 kind: TerminatorKind::Return
 173             }),
 174             is_cleanup: false
 175         })
 176     }
 177
 178     fn assign(&mut self, dest: Local, rvalue: Rvalue<'tcx>, span: Span) {
 179         let last = self.promoted.basic_blocks().last().unwrap();
 180         let data = &mut self.promoted[last];
 181         data.statements.push(Statement {
 182             source_info: SourceInfo {
 183                 span,
 184                 scope: ARGUMENT_VISIBILITY_SCOPE
 185             },
 186             kind: StatementKind::Assign(Place::Local(dest), rvalue)
 187         });
 188     }
 189
 190     /// Copy the initialization of this temp to the
 191     /// promoted MIR, recursing through temps.
 192     fn promote_temp(&mut self, temp: Local) -> Local {
 193         let old_keep_original = self.keep_original;
 194         let loc = match self.temps[temp] {
 195             TempState::Defined { location, uses } if uses > 0 => {
 196                 if uses > 1 {
 197                     self.keep_original = true;
 198                 }
 199                 location
 200             }
 201             state =>  {
 202                 span_bug!(self.promoted.span, "{:?} not promotable: {:?}",
 203                           temp, state);
 204             }
 205         };
 206         if !self.keep_original {
 207             self.temps[temp] = TempState::PromotedOut;
 208         }
 209
 210         let no_stmts = self.source[loc.block].statements.len();
 211         let new_temp = self.promoted.local_decls.push(
 212             LocalDecl::new_temp(self.source.local_decls[temp].ty,
 213                                 self.source.local_decls[temp].source_info.span));
 214
 215         debug!("promote({:?} @ {:?}/{:?}, {:?})",
 216                temp, loc, no_stmts, self.keep_original);
 217
 218         // First, take the Rvalue or Call out of the source MIR,
 219         // or duplicate it, depending on keep_original.
 220         if loc.statement_index < no_stmts {
 221             let (mut rvalue, source_info) = {
 222                 let statement = &mut self.source[loc.block].statements[loc.statement_index];
 223                 let rhs = match statement.kind {
 224                     StatementKind::Assign(_, ref mut rhs) => rhs,
 225                     _ => {
 226                         span_bug!(statement.source_info.span, "{:?} is not an assignment",
 227                                   statement);
 228                     }
 229                 };
 230
 231                 (if self.keep_original {
 232                     rhs.clone()
 233                 } else {
 234                     let unit = Rvalue::Aggregate(box AggregateKind::Tuple, vec![]);
 235                     mem::replace(rhs, unit)
 236                 }, statement.source_info)
 237             };
 238
 239             self.visit_rvalue(&mut rvalue, loc);
 240             self.assign(new_temp, rvalue, source_info.span);
 241         } else {
 242             let terminator = if self.keep_original {
 243                 self.source[loc.block].terminator().clone()
 244             } else {
 245                 let terminator = self.source[loc.block].terminator_mut();
 246                 let target = match terminator.kind {
 247                     TerminatorKind::Call { destination: Some((_, target)), .. } => target,
 248                     ref kind => {
 249                         span_bug!(terminator.source_info.span, "{:?} not promotable", kind);
 250                     }
 251                 };
 252                 Terminator {
 253                     source_info: terminator.source_info,
 254                     kind: mem::replace(&mut terminator.kind, TerminatorKind::Goto {
 255                         target,
 256                     })
 257                 }
 258             };
 259
 260             match terminator.kind {
 261                 TerminatorKind::Call { mut func, mut args, .. } => {
 262                     self.visit_operand(&mut func, loc);
 263                     for arg in &mut args {
 264                         self.visit_operand(arg, loc);
 265                     }
 266
 267                     let last = self.promoted.basic_blocks().last().unwrap();
 268                     let new_target = self.new_block();
 269
 270                     *self.promoted[last].terminator_mut() = Terminator {
 271                         kind: TerminatorKind::Call {
 272                             func,
 273                             args,
 274                             cleanup: None,
 275                             destination: Some((Place::Local(new_temp), new_target))
 276                         },
 277                         ..terminator
 278                     };
 279                 }
 280                 ref kind => {
 281                     span_bug!(terminator.source_info.span, "{:?} not promotable", kind);
 282                 }
 283             };
 284         };
 285
 286         self.keep_original = old_keep_original;
 287         new_temp
 288     }
 289
 290     fn promote_candidate(mut self, candidate: Candidate) {
 291         let span = self.promoted.span;
 292         let new_operand = Operand::Constant(box Constant {
 293             span,
 294             ty: self.promoted.return_ty(),
 295             literal: Literal::Promoted {
 296                 index: Promoted::new(self.source.promoted.len())
 297             }
 298         });
 299         let mut rvalue = match candidate {
 300             Candidate::Ref(Location { block: bb, statement_index: stmt_idx }) => {
 301                 let ref mut statement = self.source[bb].statements[stmt_idx];
 302                 match statement.kind {
 303                     StatementKind::Assign(_, ref mut rvalue) => {
 304                         mem::replace(rvalue, Rvalue::Use(new_operand))
 305                     }
 306                     _ => bug!()
 307                 }
 308             }
 309             Candidate::Argument { bb, index } => {
 310                 match self.source[bb].terminator_mut().kind {
 311                     TerminatorKind::Call { ref mut args, .. } => {
 312                         Rvalue::Use(mem::replace(&mut args[index], new_operand))
 313                     }
 314                     _ => bug!()
 315                 }
 316             }
 317         };
 318         self.visit_rvalue(&mut rvalue, Location {
 319             block: BasicBlock::new(0),
 320             statement_index: usize::MAX
 321         });
 322
 323         self.assign(RETURN_PLACE, rvalue, span);
 324         self.source.promoted.push(self.promoted);
 325     }
 326 }
 327
 328 /// Replaces all temporaries with their promoted counterparts.
 329 impl<'a, 'tcx> MutVisitor<'tcx> for Promoter<'a, 'tcx> {
 330     fn visit_local(&mut self,
 331                    local: &mut Local,
 332                    _: PlaceContext<'tcx>,
 333                    _: Location) {
 334         if self.source.local_kind(*local) == LocalKind::Temp {
 335             *local = self.promote_temp(*local);
 336         }
 337     }
 338 }
 339
 340 pub fn promote_candidates<'a, 'tcx>(mir: &mut Mir<'tcx>,
 341                                     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 342                                     mut temps: IndexVec<Local, TempState>,
 343                                     candidates: Vec<Candidate>) {
 344     // Visit candidates in reverse, in case they're nested.
 345     debug!("promote_candidates({:?})", candidates);
 346     for candidate in candidates.into_iter().rev() {
 347         let (span, ty) = match candidate {
 348             Candidate::Ref(Location { block: bb, statement_index: stmt_idx }) => {
 349                 let statement = &mir[bb].statements[stmt_idx];
 350                 let dest = match statement.kind {
 351                     StatementKind::Assign(ref dest, _) => dest,
 352                     _ => {
 353                         span_bug!(statement.source_info.span,
 354                                   "expected assignment to promote");
 355                     }
 356                 };
 357                 if let Place::Local(index) = *dest {
 358                     if temps[index] == TempState::PromotedOut {
 359                         // Already promoted.
 360                         continue;
 361                     }
 362                 }
 363                 (statement.source_info.span, dest.ty(mir, tcx).to_ty(tcx))
 364             }
 365             Candidate::Argument { bb, index } => {
 366                 let terminator = mir[bb].terminator();
 367                 let ty = match terminator.kind {
 368                     TerminatorKind::Call { ref args, .. } => {
 369                         args[index].ty(mir, tcx)
 370                     }
 371                     _ => {
 372                         span_bug!(terminator.source_info.span,
 373                                   "expected call argument to promote");
 374                     }
 375                 };
 376                 (terminator.source_info.span, ty)
 377             }
 378         };
 379
 380         // Declare return place local
 381         let initial_locals = iter::once(LocalDecl::new_return_place(ty, span))
 382             .collect();
 383
 384         let mut promoter = Promoter {
 385             promoted: Mir::new(
 386                 IndexVec::new(),
 387                 // FIXME: maybe try to filter this to avoid blowing up
 388                 // memory usage?
 389                 mir.visibility_scopes.clone(),
 390                 mir.visibility_scope_info.clone(),
 391                 IndexVec::new(),
 392                 None,
 393                 initial_locals,
 394                 0,
 395                 vec![],
 396                 span
 397             ),
 398             source: mir,
 399             temps: &mut temps,
 400             keep_original: false
 401         };
 402         assert_eq!(promoter.new_block(), START_BLOCK);
 403         promoter.promote_candidate(candidate);
 404     }
 405
 406     // Eliminate assignments to, and drops of promoted temps.
 407     let promoted = |index: Local| temps[index] == TempState::PromotedOut;
 408     for block in mir.basic_blocks_mut() {
 409         block.statements.retain(|statement| {
 410             match statement.kind {
 411                 StatementKind::Assign(Place::Local(index), _) |
 412                 StatementKind::StorageLive(index) |
 413                 StatementKind::StorageDead(index) => {
 414                     !promoted(index)
 415                 }
 416                 _ => true
 417             }
 418         });
 419         let terminator = block.terminator_mut();
 420         match terminator.kind {
 421             TerminatorKind::Drop { location: Place::Local(index), target, .. } => {
 422                 if promoted(index) {
 423                     terminator.kind = TerminatorKind::Goto {
 424                         target,
 425                     };
 426                 }
 427             }
 428             _ => {}
 429         }
 430     }
 431 }