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::{LvalueContext, 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     /// Array of indices found in the third argument of
  75     /// a call to one of the simd_shuffleN intrinsics.
  76     ShuffleIndices(BasicBlock)
  77 }
  78
  79 struct TempCollector<'tcx> {
  80     temps: IndexVec<Local, TempState>,
  81     span: Span,
  82     mir: &'tcx Mir<'tcx>,
  83 }
  84
  85 impl<'tcx> Visitor<'tcx> for TempCollector<'tcx> {
  86     fn visit_lvalue(&mut self,
  87                     lvalue: &Lvalue<'tcx>,
  88                     context: LvalueContext<'tcx>,
  89                     location: Location) {
  90         self.super_lvalue(lvalue, context, location);
  91         if let Lvalue::Local(index) = *lvalue {
  92             // We're only interested in temporaries
  93             if self.mir.local_kind(index) != LocalKind::Temp {
  94                 return;
  95             }
  96
  97             // Ignore drops, if the temp gets promoted,
  98             // then it's constant and thus drop is noop.
  99             // Storage live ranges are also irrelevant.
 100             if context.is_drop() || context.is_storage_marker() {
 101                 return;
 102             }
 103
 104             let temp = &mut self.temps[index];
 105             if *temp == TempState::Undefined {
 106                 match context {
 107                     LvalueContext::Store |
 108                     LvalueContext::Call => {
 109                         *temp = TempState::Defined {
 110                             location: location,
 111                             uses: 0
 112                         };
 113                         return;
 114                     }
 115                     _ => { /* mark as unpromotable below */ }
 116                 }
 117             } else if let TempState::Defined { ref mut uses, .. } = *temp {
 118                 // We always allow borrows, even mutable ones, as we need
 119                 // to promote mutable borrows of some ZSTs e.g. `&mut []`.
 120                 let allowed_use = match context {
 121                     LvalueContext::Borrow {..} => true,
 122                     _ => context.is_nonmutating_use()
 123                 };
 124                 if allowed_use {
 125                     *uses += 1;
 126                     return;
 127                 }
 128                 /* mark as unpromotable below */
 129             }
 130             *temp = TempState::Unpromotable;
 131         }
 132     }
 133
 134     fn visit_source_info(&mut self, source_info: &SourceInfo) {
 135         self.span = source_info.span;
 136     }
 137 }
 138
 139 pub fn collect_temps(mir: &Mir, rpo: &mut ReversePostorder) -> IndexVec<Local, TempState> {
 140     let mut collector = TempCollector {
 141         temps: IndexVec::from_elem(TempState::Undefined, &mir.local_decls),
 142         span: mir.span,
 143         mir: mir,
 144     };
 145     for (bb, data) in rpo {
 146         collector.visit_basic_block_data(bb, data);
 147     }
 148     collector.temps
 149 }
 150
 151 struct Promoter<'a, 'tcx: 'a> {
 152     source: &'a mut Mir<'tcx>,
 153     promoted: Mir<'tcx>,
 154     temps: &'a mut IndexVec<Local, TempState>,
 155
 156     /// If true, all nested temps are also kept in the
 157     /// source MIR, not moved to the promoted MIR.
 158     keep_original: bool
 159 }
 160
 161 impl<'a, 'tcx> Promoter<'a, 'tcx> {
 162     fn new_block(&mut self) -> BasicBlock {
 163         let span = self.promoted.span;
 164         self.promoted.basic_blocks_mut().push(BasicBlockData {
 165             statements: vec![],
 166             terminator: Some(Terminator {
 167                 source_info: SourceInfo {
 168                     span: span,
 169                     scope: ARGUMENT_VISIBILITY_SCOPE
 170                 },
 171                 kind: TerminatorKind::Return
 172             }),
 173             is_cleanup: false
 174         })
 175     }
 176
 177     fn assign(&mut self, dest: Local, rvalue: Rvalue<'tcx>, span: Span) {
 178         let last = self.promoted.basic_blocks().last().unwrap();
 179         let data = &mut self.promoted[last];
 180         data.statements.push(Statement {
 181             source_info: SourceInfo {
 182                 span: span,
 183                 scope: ARGUMENT_VISIBILITY_SCOPE
 184             },
 185             kind: StatementKind::Assign(Lvalue::Local(dest), rvalue)
 186         });
 187     }
 188
 189     /// Copy the initialization of this temp to the
 190     /// promoted MIR, recursing through temps.
 191     fn promote_temp(&mut self, temp: Local) -> Local {
 192         let old_keep_original = self.keep_original;
 193         let loc = match self.temps[temp] {
 194             TempState::Defined { location, uses } if uses > 0 => {
 195                 if uses > 1 {
 196                     self.keep_original = true;
 197                 }
 198                 location
 199             }
 200             state =>  {
 201                 span_bug!(self.promoted.span, "{:?} not promotable: {:?}",
 202                           temp, state);
 203             }
 204         };
 205         if !self.keep_original {
 206             self.temps[temp] = TempState::PromotedOut;
 207         }
 208
 209         let no_stmts = self.source[loc.block].statements.len();
 210         let new_temp = self.promoted.local_decls.push(
 211             LocalDecl::new_temp(self.source.local_decls[temp].ty,
 212                                 self.source.local_decls[temp].source_info.span));
 213
 214         debug!("promote({:?} @ {:?}/{:?}, {:?})",
 215                temp, loc, no_stmts, self.keep_original);
 216
 217         // First, take the Rvalue or Call out of the source MIR,
 218         // or duplicate it, depending on keep_original.
 219         if loc.statement_index < no_stmts {
 220             let (mut rvalue, source_info) = {
 221                 let statement = &mut self.source[loc.block].statements[loc.statement_index];
 222                 let rhs = match statement.kind {
 223                     StatementKind::Assign(_, ref mut rhs) => rhs,
 224                     _ => {
 225                         span_bug!(statement.source_info.span, "{:?} is not an assignment",
 226                                   statement);
 227                     }
 228                 };
 229
 230                 (if self.keep_original {
 231                     rhs.clone()
 232                 } else {
 233                     let unit = Rvalue::Aggregate(box AggregateKind::Tuple, vec![]);
 234                     mem::replace(rhs, unit)
 235                 }, statement.source_info)
 236             };
 237
 238             self.visit_rvalue(&mut rvalue, loc);
 239             self.assign(new_temp, rvalue, source_info.span);
 240         } else {
 241             let terminator = if self.keep_original {
 242                 self.source[loc.block].terminator().clone()
 243             } else {
 244                 let terminator = self.source[loc.block].terminator_mut();
 245                 let target = match terminator.kind {
 246                     TerminatorKind::Call { destination: Some((_, target)), .. } => target,
 247                     ref kind => {
 248                         span_bug!(terminator.source_info.span, "{:?} not promotable", kind);
 249                     }
 250                 };
 251                 Terminator {
 252                     source_info: terminator.source_info,
 253                     kind: mem::replace(&mut terminator.kind, TerminatorKind::Goto {
 254                         target: target
 255                     })
 256                 }
 257             };
 258
 259             match terminator.kind {
 260                 TerminatorKind::Call { mut func, mut args, .. } => {
 261                     self.visit_operand(&mut func, loc);
 262                     for arg in &mut args {
 263                         self.visit_operand(arg, loc);
 264                     }
 265
 266                     let last = self.promoted.basic_blocks().last().unwrap();
 267                     let new_target = self.new_block();
 268
 269                     *self.promoted[last].terminator_mut() = Terminator {
 270                         kind: TerminatorKind::Call {
 271                             func: func,
 272                             args: args,
 273                             cleanup: None,
 274                             destination: Some((Lvalue::Local(new_temp), new_target))
 275                         },
 276                         ..terminator
 277                     };
 278                 }
 279                 ref kind => {
 280                     span_bug!(terminator.source_info.span, "{:?} not promotable", kind);
 281                 }
 282             };
 283         };
 284
 285         self.keep_original = old_keep_original;
 286         new_temp
 287     }
 288
 289     fn promote_candidate(mut self, candidate: Candidate) {
 290         let span = self.promoted.span;
 291         let new_operand = Operand::Constant(box Constant {
 292             span: span,
 293             ty: self.promoted.return_ty,
 294             literal: Literal::Promoted {
 295                 index: Promoted::new(self.source.promoted.len())
 296             }
 297         });
 298         let mut rvalue = match candidate {
 299             Candidate::Ref(Location { block: bb, statement_index: stmt_idx }) => {
 300                 let ref mut statement = self.source[bb].statements[stmt_idx];
 301                 match statement.kind {
 302                     StatementKind::Assign(_, ref mut rvalue) => {
 303                         mem::replace(rvalue, Rvalue::Use(new_operand))
 304                     }
 305                     _ => bug!()
 306                 }
 307             }
 308             Candidate::ShuffleIndices(bb) => {
 309                 match self.source[bb].terminator_mut().kind {
 310                     TerminatorKind::Call { ref mut args, .. } => {
 311                         Rvalue::Use(mem::replace(&mut args[2], new_operand))
 312                     }
 313                     _ => bug!()
 314                 }
 315             }
 316         };
 317         self.visit_rvalue(&mut rvalue, Location {
 318             block: BasicBlock::new(0),
 319             statement_index: usize::MAX
 320         });
 321
 322         self.assign(RETURN_POINTER, rvalue, span);
 323         self.source.promoted.push(self.promoted);
 324     }
 325 }
 326
 327 /// Replaces all temporaries with their promoted counterparts.
 328 impl<'a, 'tcx> MutVisitor<'tcx> for Promoter<'a, 'tcx> {
 329     fn visit_lvalue(&mut self,
 330                     lvalue: &mut Lvalue<'tcx>,
 331                     context: LvalueContext<'tcx>,
 332                     location: Location) {
 333         if let Lvalue::Local(ref mut temp) = *lvalue {
 334             if self.source.local_kind(*temp) == LocalKind::Temp {
 335                 *temp = self.promote_temp(*temp);
 336             }
 337         }
 338         self.super_lvalue(lvalue, context, location);
 339     }
 340 }
 341
 342 pub fn promote_candidates<'a, 'tcx>(mir: &mut Mir<'tcx>,
 343                                     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 344                                     mut temps: IndexVec<Local, TempState>,
 345                                     candidates: Vec<Candidate>) {
 346     // Visit candidates in reverse, in case they're nested.
 347     debug!("promote_candidates({:?})", candidates);
 348     for candidate in candidates.into_iter().rev() {
 349         let (span, ty) = match candidate {
 350             Candidate::Ref(Location { block: bb, statement_index: stmt_idx }) => {
 351                 let statement = &mir[bb].statements[stmt_idx];
 352                 let dest = match statement.kind {
 353                     StatementKind::Assign(ref dest, _) => dest,
 354                     _ => {
 355                         span_bug!(statement.source_info.span,
 356                                   "expected assignment to promote");
 357                     }
 358                 };
 359                 if let Lvalue::Local(index) = *dest {
 360                     if temps[index] == TempState::PromotedOut {
 361                         // Already promoted.
 362                         continue;
 363                     }
 364                 }
 365                 (statement.source_info.span, dest.ty(mir, tcx).to_ty(tcx))
 366             }
 367             Candidate::ShuffleIndices(bb) => {
 368                 let terminator = mir[bb].terminator();
 369                 let ty = match terminator.kind {
 370                     TerminatorKind::Call { ref args, .. } => {
 371                         args[2].ty(mir, tcx)
 372                     }
 373                     _ => {
 374                         span_bug!(terminator.source_info.span,
 375                                   "expected simd_shuffleN call to promote");
 376                     }
 377                 };
 378                 (terminator.source_info.span, ty)
 379             }
 380         };
 381
 382         // Declare return pointer local
 383         let initial_locals = iter::once(LocalDecl::new_return_pointer(ty, span))
 384             .collect();
 385
 386         let mut promoter = Promoter {
 387             promoted: Mir::new(
 388                 IndexVec::new(),
 389                 Some(VisibilityScopeData {
 390                     span: span,
 391                     parent_scope: None
 392                 }).into_iter().collect(),
 393                 IndexVec::new(),
 394                 ty,
 395                 initial_locals,
 396                 0,
 397                 vec![],
 398                 span
 399             ),
 400             source: mir,
 401             temps: &mut temps,
 402             keep_original: false
 403         };
 404         assert_eq!(promoter.new_block(), START_BLOCK);
 405         promoter.promote_candidate(candidate);
 406     }
 407
 408     // Eliminate assignments to, and drops of promoted temps.
 409     let promoted = |index: Local| temps[index] == TempState::PromotedOut;
 410     for block in mir.basic_blocks_mut() {
 411         block.statements.retain(|statement| {
 412             match statement.kind {
 413                 StatementKind::Assign(Lvalue::Local(index), _) |
 414                 StatementKind::StorageLive(Lvalue::Local(index)) |
 415                 StatementKind::StorageDead(Lvalue::Local(index)) => {
 416                     !promoted(index)
 417                 }
 418                 _ => true
 419             }
 420         });
 421         let terminator = block.terminator_mut();
 422         match terminator.kind {
 423             TerminatorKind::Drop { location: Lvalue::Local(index), target, .. } => {
 424                 if promoted(index) {
 425                     terminator.kind = TerminatorKind::Goto {
 426                         target: target
 427                     };
 428                 }
 429             }
 430             _ => {}
 431         }
 432     }
 433 }