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