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::repr::*;
  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 pub enum Candidate {
  70     /// Borrow of a constant temporary.
  71     Ref(Location),
  72
  73     /// Array of indices found in the third argument of
  74     /// a call to one of the simd_shuffleN intrinsics.
  75     ShuffleIndices(BasicBlock)
  76 }
  77
  78 struct TempCollector<'tcx> {
  79     temps: IndexVec<Local, TempState>,
  80     span: Span,
  81     mir: &'tcx Mir<'tcx>,
  82 }
  83
  84 impl<'tcx> Visitor<'tcx> for TempCollector<'tcx> {
  85     fn visit_lvalue(&mut self,
  86                     lvalue: &Lvalue<'tcx>,
  87                     context: LvalueContext<'tcx>,
  88                     location: Location) {
  89         self.super_lvalue(lvalue, context, location);
  90         if let Lvalue::Local(index) = *lvalue {
  91             // We're only interested in temporaries
  92             if self.mir.local_kind(index) != LocalKind::Temp {
  93                 return;
  94             }
  95
  96             // Ignore drops, if the temp gets promoted,
  97             // then it's constant and thus drop is noop.
  98             // Storage live ranges are also irrelevant.
  99             match context {
 100                 LvalueContext::Drop |
 101                 LvalueContext::StorageLive |
 102                 LvalueContext::StorageDead => return,
 103                 _ => {}
 104             }
 105
 106             let temp = &mut self.temps[index];
 107             if *temp == TempState::Undefined {
 108                 match context {
 109                     LvalueContext::Store |
 110                     LvalueContext::Call => {
 111                         *temp = TempState::Defined {
 112                             location: 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                 match context {
 121                     LvalueContext::Borrow {..} |
 122                     LvalueContext::Consume |
 123                     LvalueContext::Inspect => {
 124                         *uses += 1;
 125                         return;
 126                     }
 127                     _ => { /* mark as unpromotable below */ }
 128                 }
 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 (bb, stmt_idx) = match self.temps[temp] {
 194             TempState::Defined {
 195                 location: Location { block, statement_index },
 196                 uses
 197             } if uses > 0 => {
 198                 if uses > 1 {
 199                     self.keep_original = true;
 200                 }
 201                 (block, statement_index)
 202             }
 203             state =>  {
 204                 span_bug!(self.promoted.span, "{:?} not promotable: {:?}",
 205                           temp, state);
 206             }
 207         };
 208         if !self.keep_original {
 209             self.temps[temp] = TempState::PromotedOut;
 210         }
 211
 212         let no_stmts = self.source[bb].statements.len();
 213
 214         // First, take the Rvalue or Call out of the source MIR,
 215         // or duplicate it, depending on keep_original.
 216         let (mut rvalue, mut call) = (None, None);
 217         let source_info = if stmt_idx < no_stmts {
 218             let statement = &mut self.source[bb].statements[stmt_idx];
 219             let rhs = match statement.kind {
 220                 StatementKind::Assign(_, ref mut rhs) => rhs,
 221                 _ => {
 222                     span_bug!(statement.source_info.span, "{:?} is not an assignment",
 223                               statement);
 224                 }
 225             };
 226             if self.keep_original {
 227                 rvalue = Some(rhs.clone());
 228             } else {
 229                 let unit = Rvalue::Aggregate(AggregateKind::Tuple, vec![]);
 230                 rvalue = Some(mem::replace(rhs, unit));
 231             }
 232             statement.source_info
 233         } else if self.keep_original {
 234             let terminator = self.source[bb].terminator().clone();
 235             call = Some(terminator.kind);
 236             terminator.source_info
 237         } else {
 238             let terminator = self.source[bb].terminator_mut();
 239             let target = match terminator.kind {
 240                 TerminatorKind::Call {
 241                     destination: ref mut dest @ Some(_),
 242                     ref mut cleanup, ..
 243                 } => {
 244                     // No cleanup necessary.
 245                     cleanup.take();
 246
 247                     // We'll put a new destination in later.
 248                     dest.take().unwrap().1
 249                 }
 250                 ref kind => {
 251                     span_bug!(terminator.source_info.span, "{:?} not promotable", kind);
 252                 }
 253             };
 254             call = Some(mem::replace(&mut terminator.kind, TerminatorKind::Goto {
 255                 target: target
 256             }));
 257             terminator.source_info
 258         };
 259
 260         // Then, recurse for components in the Rvalue or Call.
 261         if stmt_idx < no_stmts {
 262             self.visit_rvalue(rvalue.as_mut().unwrap(), Location {
 263                 block: bb,
 264                 statement_index: stmt_idx
 265             });
 266         } else {
 267             self.visit_terminator_kind(bb, call.as_mut().unwrap(), Location {
 268                 block: bb,
 269                 statement_index: no_stmts
 270             });
 271         }
 272
 273         let new_temp = self.promoted.local_decls.push(
 274             LocalDecl::new_temp(self.source.local_decls[temp].ty));
 275
 276         // Inject the Rvalue or Call into the promoted MIR.
 277         if stmt_idx < no_stmts {
 278             self.assign(new_temp, rvalue.unwrap(), source_info.span);
 279         } else {
 280             let last = self.promoted.basic_blocks().last().unwrap();
 281             let new_target = self.new_block();
 282             let mut call = call.unwrap();
 283             match call {
 284                 TerminatorKind::Call { ref mut destination, ..}  => {
 285                     *destination = Some((Lvalue::Local(new_temp), new_target));
 286                 }
 287                 _ => bug!()
 288             }
 289             let terminator = self.promoted[last].terminator_mut();
 290             terminator.source_info.span = source_info.span;
 291             terminator.kind = call;
 292         }
 293
 294         // Restore the old duplication state.
 295         self.keep_original = old_keep_original;
 296
 297         new_temp
 298     }
 299
 300     fn promote_candidate(mut self, candidate: Candidate) {
 301         let span = self.promoted.span;
 302         let new_operand = Operand::Constant(Constant {
 303             span: span,
 304             ty: self.promoted.return_ty,
 305             literal: Literal::Promoted {
 306                 index: Promoted::new(self.source.promoted.len())
 307             }
 308         });
 309         let mut rvalue = match candidate {
 310             Candidate::Ref(Location { block: bb, statement_index: stmt_idx }) => {
 311                 let ref mut statement = self.source[bb].statements[stmt_idx];
 312                 match statement.kind {
 313                     StatementKind::Assign(_, ref mut rvalue) => {
 314                         mem::replace(rvalue, Rvalue::Use(new_operand))
 315                     }
 316                     _ => bug!()
 317                 }
 318             }
 319             Candidate::ShuffleIndices(bb) => {
 320                 match self.source[bb].terminator_mut().kind {
 321                     TerminatorKind::Call { ref mut args, .. } => {
 322                         Rvalue::Use(mem::replace(&mut args[2], new_operand))
 323                     }
 324                     _ => bug!()
 325                 }
 326             }
 327         };
 328         self.visit_rvalue(&mut rvalue, Location {
 329             block: BasicBlock::new(0),
 330             statement_index: usize::MAX
 331         });
 332
 333         self.assign(RETURN_POINTER, rvalue, span);
 334         self.source.promoted.push(self.promoted);
 335     }
 336 }
 337
 338 /// Replaces all temporaries with their promoted counterparts.
 339 impl<'a, 'tcx> MutVisitor<'tcx> for Promoter<'a, 'tcx> {
 340     fn visit_lvalue(&mut self,
 341                     lvalue: &mut Lvalue<'tcx>,
 342                     context: LvalueContext<'tcx>,
 343                     location: Location) {
 344         if let Lvalue::Local(ref mut temp) = *lvalue {
 345             if self.source.local_kind(*temp) == LocalKind::Temp {
 346                 *temp = self.promote_temp(*temp);
 347             }
 348         }
 349         self.super_lvalue(lvalue, context, location);
 350     }
 351 }
 352
 353 pub fn promote_candidates<'a, 'tcx>(mir: &mut Mir<'tcx>,
 354                                     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 355                                     mut temps: IndexVec<Local, TempState>,
 356                                     candidates: Vec<Candidate>) {
 357     // Visit candidates in reverse, in case they're nested.
 358     for candidate in candidates.into_iter().rev() {
 359         let (span, ty) = match candidate {
 360             Candidate::Ref(Location { block: bb, statement_index: stmt_idx }) => {
 361                 let statement = &mir[bb].statements[stmt_idx];
 362                 let dest = match statement.kind {
 363                     StatementKind::Assign(ref dest, _) => dest,
 364                     _ => {
 365                         span_bug!(statement.source_info.span,
 366                                   "expected assignment to promote");
 367                     }
 368                 };
 369                 if let Lvalue::Local(index) = *dest {
 370                     if temps[index] == TempState::PromotedOut {
 371                         // Already promoted.
 372                         continue;
 373                     }
 374                 }
 375                 (statement.source_info.span, dest.ty(mir, tcx).to_ty(tcx))
 376             }
 377             Candidate::ShuffleIndices(bb) => {
 378                 let terminator = mir[bb].terminator();
 379                 let ty = match terminator.kind {
 380                     TerminatorKind::Call { ref args, .. } => {
 381                         args[2].ty(mir, tcx)
 382                     }
 383                     _ => {
 384                         span_bug!(terminator.source_info.span,
 385                                   "expected simd_shuffleN call to promote");
 386                     }
 387                 };
 388                 (terminator.source_info.span, ty)
 389             }
 390         };
 391
 392         // Declare return pointer local
 393         let initial_locals = iter::once(LocalDecl::new_return_pointer(ty)).collect();
 394
 395         let mut promoter = Promoter {
 396             promoted: Mir::new(
 397                 IndexVec::new(),
 398                 Some(VisibilityScopeData {
 399                     span: span,
 400                     parent_scope: None
 401                 }).into_iter().collect(),
 402                 IndexVec::new(),
 403                 ty,
 404                 initial_locals,
 405                 0,
 406                 vec![],
 407                 span
 408             ),
 409             source: mir,
 410             temps: &mut temps,
 411             keep_original: false
 412         };
 413         assert_eq!(promoter.new_block(), START_BLOCK);
 414         promoter.promote_candidate(candidate);
 415     }
 416
 417     // Eliminate assignments to, and drops of promoted temps.
 418     let promoted = |index: Local| temps[index] == TempState::PromotedOut;
 419     for block in mir.basic_blocks_mut() {
 420         block.statements.retain(|statement| {
 421             match statement.kind {
 422                 StatementKind::Assign(Lvalue::Local(index), _) |
 423                 StatementKind::StorageLive(Lvalue::Local(index)) |
 424                 StatementKind::StorageDead(Lvalue::Local(index)) => {
 425                     !promoted(index)
 426                 }
 427                 _ => true
 428             }
 429         });
 430         let terminator = block.terminator_mut();
 431         match terminator.kind {
 432             TerminatorKind::Drop { location: Lvalue::Local(index), target, .. } => {
 433                 if promoted(index) {
 434                     terminator.kind = TerminatorKind::Goto {
 435                         target: target
 436                     };
 437                 }
 438             }
 439             _ => {}
 440         }
 441     }
 442 }