src/librustc_mir/transform/promote_consts.rs

   1 //! A pass that promotes borrows of constant rvalues.
   2 //!
   3 //! The rvalues considered constant are trees of temps,
   4 //! each with exactly one initialization, and holding
   5 //! a constant value with no interior mutability.
   6 //! They are placed into a new MIR constant body in
   7 //! `promoted` and the borrow rvalue is replaced with
   8 //! a `Literal::Promoted` using the index into `promoted`
   9 //! of that constant MIR.
  10 //!
  11 //! This pass assumes that every use is dominated by an
  12 //! initialization and can otherwise silence errors, if
  13 //! move analysis runs after promotion on broken MIR.
  14
  15 use rustc::hir::def_id::DefId;
  16 use rustc::mir::*;
  17 use rustc::mir::interpret::ConstValue;
  18 use rustc::mir::visit::{PlaceContext, MutatingUseContext, MutVisitor, Visitor};
  19 use rustc::mir::traversal::ReversePostorder;
  20 use rustc::ty::{self, List, TyCtxt};
  21 use rustc::ty::subst::InternalSubsts;
  22 use rustc::ty::cast::CastTy;
  23 use syntax::ast::LitKind;
  24 use syntax::symbol::sym;
  25 use syntax_pos::{Span, DUMMY_SP};
  26
  27 use rustc_index::vec::{IndexVec, Idx};
  28 use rustc_target::spec::abi::Abi;
  29
  30 use std::{iter, mem, usize};
  31
  32 use crate::transform::check_consts::{qualifs, Item, ConstKind, is_lang_panic_fn};
  33
  34 /// State of a temporary during collection and promotion.
  35 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
  36 pub enum TempState {
  37     /// No references to this temp.
  38     Undefined,
  39     /// One direct assignment and any number of direct uses.
  40     /// A borrow of this temp is promotable if the assigned
  41     /// value is qualified as constant.
  42     Defined {
  43         location: Location,
  44         uses: usize
  45     },
  46     /// Any other combination of assignments/uses.
  47     Unpromotable,
  48     /// This temp was part of an rvalue which got extracted
  49     /// during promotion and needs cleanup.
  50     PromotedOut
  51 }
  52
  53 impl TempState {
  54     pub fn is_promotable(&self) -> bool {
  55         debug!("is_promotable: self={:?}", self);
  56         if let TempState::Defined { .. } = *self {
  57             true
  58         } else {
  59             false
  60         }
  61     }
  62 }
  63
  64 /// A "root candidate" for promotion, which will become the
  65 /// returned value in a promoted MIR, unless it's a subset
  66 /// of a larger candidate.
  67 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
  68 pub enum Candidate {
  69     /// Borrow of a constant temporary.
  70     Ref(Location),
  71
  72     /// Promotion of the `x` in `[x; 32]`.
  73     Repeat(Location),
  74
  75     /// Currently applied to function calls where the callee has the unstable
  76     /// `#[rustc_args_required_const]` attribute as well as the SIMD shuffle
  77     /// intrinsic. The intrinsic requires the arguments are indeed constant and
  78     /// the attribute currently provides the semantic requirement that arguments
  79     /// must be constant.
  80     Argument { bb: BasicBlock, index: usize },
  81 }
  82
  83 impl Candidate {
  84     /// Returns `true` if we should use the "explicit" rules for promotability for this `Candidate`.
  85     fn forces_explicit_promotion(&self) -> bool {
  86         match self {
  87             Candidate::Ref(_) |
  88             Candidate::Repeat(_) => false,
  89             Candidate::Argument { .. } => true,
  90         }
  91     }
  92 }
  93
  94 fn args_required_const(tcx: TyCtxt<'_>, def_id: DefId) -> Option<Vec<usize>> {
  95     let attrs = tcx.get_attrs(def_id);
  96     let attr = attrs.iter().find(|a| a.check_name(sym::rustc_args_required_const))?;
  97     let mut ret = vec![];
  98     for meta in attr.meta_item_list()? {
  99         match meta.literal()?.kind {
 100             LitKind::Int(a, _) => { ret.push(a as usize); }
 101             _ => return None,
 102         }
 103     }
 104     Some(ret)
 105 }
 106
 107 struct Collector<'a, 'tcx> {
 108     tcx: TyCtxt<'tcx>,
 109     body: &'a Body<'tcx>,
 110     temps: IndexVec<Local, TempState>,
 111     candidates: Vec<Candidate>,
 112     span: Span,
 113 }
 114
 115 impl<'tcx> Visitor<'tcx> for Collector<'_, 'tcx> {
 116     fn visit_local(&mut self,
 117                    &index: &Local,
 118                    context: PlaceContext,
 119                    location: Location) {
 120         debug!("visit_local: index={:?} context={:?} location={:?}", index, context, location);
 121         // We're only interested in temporaries and the return place
 122         match self.body.local_kind(index) {
 123             | LocalKind::Temp
 124             | LocalKind::ReturnPointer
 125             => {},
 126             | LocalKind::Arg
 127             | LocalKind::Var
 128             => return,
 129         }
 130
 131         // Ignore drops, if the temp gets promoted,
 132         // then it's constant and thus drop is noop.
 133         // Non-uses are also irrelevent.
 134         if context.is_drop() || !context.is_use() {
 135             debug!(
 136                 "visit_local: context.is_drop={:?} context.is_use={:?}",
 137                 context.is_drop(), context.is_use(),
 138             );
 139             return;
 140         }
 141
 142         let temp = &mut self.temps[index];
 143         debug!("visit_local: temp={:?}", temp);
 144         if *temp == TempState::Undefined {
 145             match context {
 146                 PlaceContext::MutatingUse(MutatingUseContext::Store) |
 147                 PlaceContext::MutatingUse(MutatingUseContext::Call) => {
 148                     *temp = TempState::Defined {
 149                         location,
 150                         uses: 0
 151                     };
 152                     return;
 153                 }
 154                 _ => { /* mark as unpromotable below */ }
 155             }
 156         } else if let TempState::Defined { ref mut uses, .. } = *temp {
 157             // We always allow borrows, even mutable ones, as we need
 158             // to promote mutable borrows of some ZSTs e.g., `&mut []`.
 159             let allowed_use = context.is_borrow() || context.is_nonmutating_use();
 160             debug!("visit_local: allowed_use={:?}", allowed_use);
 161             if allowed_use {
 162                 *uses += 1;
 163                 return;
 164             }
 165             /* mark as unpromotable below */
 166         }
 167         *temp = TempState::Unpromotable;
 168     }
 169
 170     fn visit_rvalue(&mut self, rvalue: &Rvalue<'tcx>, location: Location) {
 171         self.super_rvalue(rvalue, location);
 172
 173         match *rvalue {
 174             Rvalue::Ref(..) => {
 175                 self.candidates.push(Candidate::Ref(location));
 176             }
 177             Rvalue::Repeat(..) if self.tcx.features().const_in_array_repeat_expressions => {
 178                 // FIXME(#49147) only promote the element when it isn't `Copy`
 179                 // (so that code that can copy it at runtime is unaffected).
 180                 self.candidates.push(Candidate::Repeat(location));
 181             }
 182             _ => {}
 183         }
 184     }
 185
 186     fn visit_terminator_kind(&mut self,
 187                              kind: &TerminatorKind<'tcx>,
 188                              location: Location) {
 189         self.super_terminator_kind(kind, location);
 190
 191         if let TerminatorKind::Call { ref func, .. } = *kind {
 192             if let ty::FnDef(def_id, _) = func.ty(self.body, self.tcx).kind {
 193                 let fn_sig = self.tcx.fn_sig(def_id);
 194                 if let Abi::RustIntrinsic | Abi::PlatformIntrinsic = fn_sig.abi() {
 195                     let name = self.tcx.item_name(def_id);
 196                     // FIXME(eddyb) use `#[rustc_args_required_const(2)]` for shuffles.
 197                     if name.as_str().starts_with("simd_shuffle") {
 198                         self.candidates.push(Candidate::Argument {
 199                             bb: location.block,
 200                             index: 2,
 201                         });
 202                     }
 203                 }
 204
 205                 if let Some(constant_args) = args_required_const(self.tcx, def_id) {
 206                     for index in constant_args {
 207                         self.candidates.push(Candidate::Argument { bb: location.block, index });
 208                     }
 209                 }
 210             }
 211         }
 212     }
 213
 214     fn visit_source_info(&mut self, source_info: &SourceInfo) {
 215         self.span = source_info.span;
 216     }
 217 }
 218
 219 pub fn collect_temps_and_candidates(
 220     tcx: TyCtxt<'tcx>,
 221     body: &Body<'tcx>,
 222     rpo: &mut ReversePostorder<'_, 'tcx>,
 223 ) -> (IndexVec<Local, TempState>, Vec<Candidate>) {
 224     let mut collector = Collector {
 225         tcx,
 226         body,
 227         temps: IndexVec::from_elem(TempState::Undefined, &body.local_decls),
 228         candidates: vec![],
 229         span: body.span,
 230     };
 231     for (bb, data) in rpo {
 232         collector.visit_basic_block_data(bb, data);
 233     }
 234     (collector.temps, collector.candidates)
 235 }
 236
 237 /// Checks whether locals that appear in a promotion context (`Candidate`) are actually promotable.
 238 ///
 239 /// This wraps an `Item`, and has access to all fields of that `Item` via `Deref` coercion.
 240 struct Validator<'a, 'tcx> {
 241     item: Item<'a, 'tcx>,
 242     temps: &'a IndexVec<Local, TempState>,
 243
 244     /// Explicit promotion happens e.g. for constant arguments declared via
 245     /// `rustc_args_required_const`.
 246     /// Implicit promotion has almost the same rules, except that disallows `const fn`
 247     /// except for those marked `#[rustc_promotable]`. This is to avoid changing
 248     /// a legitimate run-time operation into a failing compile-time operation
 249     /// e.g. due to addresses being compared inside the function.
 250     explicit: bool,
 251 }
 252
 253 impl std::ops::Deref for Validator<'a, 'tcx> {
 254     type Target = Item<'a, 'tcx>;
 255
 256     fn deref(&self) -> &Self::Target {
 257         &self.item
 258     }
 259 }
 260
 261 struct Unpromotable;
 262
 263 impl<'tcx> Validator<'_, 'tcx> {
 264     fn validate_candidate(&self, candidate: Candidate) -> Result<(), Unpromotable> {
 265         match candidate {
 266             Candidate::Ref(loc) => {
 267                 assert!(!self.explicit);
 268
 269                 let statement = &self.body[loc.block].statements[loc.statement_index];
 270                 match &statement.kind {
 271                     StatementKind::Assign(box(_, Rvalue::Ref(_, kind, place))) => {
 272                         match kind {
 273                             BorrowKind::Shared | BorrowKind::Mut { .. } => {}
 274
 275                             // FIXME(eddyb) these aren't promoted here but *could*
 276                             // be promoted as part of a larger value because
 277                             // `validate_rvalue`  doesn't check them, need to
 278                             // figure out what is the intended behavior.
 279                             BorrowKind::Shallow | BorrowKind::Unique => return Err(Unpromotable),
 280                         }
 281
 282                         // We can only promote interior borrows of promotable temps (non-temps
 283                         // don't get promoted anyway).
 284                         let base = match place.base {
 285                             PlaceBase::Local(local) => local,
 286                             _ => return Err(Unpromotable),
 287                         };
 288                         self.validate_local(base)?;
 289
 290                         if place.projection.contains(&ProjectionElem::Deref) {
 291                             return Err(Unpromotable);
 292                         }
 293
 294                         let mut has_mut_interior =
 295                             self.qualif_local::<qualifs::HasMutInterior>(base);
 296                         // HACK(eddyb) this should compute the same thing as
 297                         // `<HasMutInterior as Qualif>::in_projection` from
 298                         // `check_consts::qualifs` but without recursion.
 299                         if has_mut_interior {
 300                             // This allows borrowing fields which don't have
 301                             // `HasMutInterior`, from a type that does, e.g.:
 302                             // `let _: &'static _ = &(Cell::new(1), 2).1;`
 303                             let mut place_projection = &place.projection[..];
 304                             // FIXME(eddyb) use a forward loop instead of a reverse one.
 305                             while let [proj_base @ .., elem] = place_projection {
 306                                 // FIXME(eddyb) this is probably excessive, with
 307                                 // the exception of `union` member accesses.
 308                                 let ty =
 309                                     Place::ty_from(&place.base, proj_base, self.body, self.tcx)
 310                                         .projection_ty(self.tcx, elem)
 311                                         .ty;
 312                                 if ty.is_freeze(self.tcx, self.param_env, DUMMY_SP) {
 313                                     has_mut_interior = false;
 314                                     break;
 315                                 }
 316
 317                                 place_projection = proj_base;
 318                             }
 319                         }
 320
 321                         // FIXME(eddyb) this duplicates part of `validate_rvalue`.
 322                         if has_mut_interior {
 323                             return Err(Unpromotable);
 324                         }
 325                         if self.qualif_local::<qualifs::NeedsDrop>(base) {
 326                             return Err(Unpromotable);
 327                         }
 328
 329                         if let BorrowKind::Mut { .. } = kind {
 330                             let ty = place.ty(self.body, self.tcx).ty;
 331
 332                             // In theory, any zero-sized value could be borrowed
 333                             // mutably without consequences. However, only &mut []
 334                             // is allowed right now, and only in functions.
 335                             if self.const_kind == Some(ConstKind::StaticMut) {
 336                                 // Inside a `static mut`, &mut [...] is also allowed.
 337                                 match ty.kind {
 338                                     ty::Array(..) | ty::Slice(_) => {}
 339                                     _ => return Err(Unpromotable),
 340                                 }
 341                             } else if let ty::Array(_, len) = ty.kind {
 342                                 // FIXME(eddyb) the `self.is_non_const_fn` condition
 343                                 // seems unnecessary, given that this is merely a ZST.
 344                                 match len.try_eval_usize(self.tcx, self.param_env) {
 345                                     Some(0) if self.const_kind.is_none() => {},
 346                                     _ => return Err(Unpromotable),
 347                                 }
 348                             } else {
 349                                 return Err(Unpromotable);
 350                             }
 351                         }
 352
 353                         Ok(())
 354                     }
 355                     _ => bug!()
 356                 }
 357             }
 358             Candidate::Repeat(loc) => {
 359                 assert!(!self.explicit);
 360
 361                 let statement = &self.body[loc.block].statements[loc.statement_index];
 362                 match &statement.kind {
 363                     StatementKind::Assign(box(_, Rvalue::Repeat(ref operand, _))) => {
 364                         if !self.tcx.features().const_in_array_repeat_expressions {
 365                             return Err(Unpromotable);
 366                         }
 367
 368                         self.validate_operand(operand)
 369                     }
 370                     _ => bug!()
 371                 }
 372             },
 373             Candidate::Argument { bb, index } => {
 374                 assert!(self.explicit);
 375
 376                 let terminator = self.body[bb].terminator();
 377                 match &terminator.kind {
 378                     TerminatorKind::Call { args, .. } => {
 379                         self.validate_operand(&args[index])
 380                     }
 381                     _ => bug!()
 382                 }
 383             }
 384         }
 385     }
 386
 387     // FIXME(eddyb) maybe cache this?
 388     fn qualif_local<Q: qualifs::Qualif>(&self, local: Local) -> bool {
 389         let per_local = &|l| self.qualif_local::<Q>(l);
 390
 391         if let TempState::Defined { location: loc, .. } = self.temps[local] {
 392             let num_stmts = self.body[loc.block].statements.len();
 393
 394             if loc.statement_index < num_stmts {
 395                 let statement = &self.body[loc.block].statements[loc.statement_index];
 396                 match &statement.kind {
 397                     StatementKind::Assign(box(_, rhs)) => {
 398                         Q::in_rvalue(&self.item, per_local, rhs)
 399                     }
 400                     _ => {
 401                         span_bug!(statement.source_info.span, "{:?} is not an assignment",
 402                                 statement);
 403                     }
 404                 }
 405             } else {
 406                 let terminator = self.body[loc.block].terminator();
 407                 match &terminator.kind {
 408                     TerminatorKind::Call { func, args, .. } => {
 409                         let return_ty = self.body.local_decls[local].ty;
 410                         Q::in_call(&self.item, per_local, func, args, return_ty)
 411                     }
 412                     kind => {
 413                         span_bug!(terminator.source_info.span, "{:?} not promotable", kind);
 414                     }
 415                 }
 416             }
 417         } else {
 418             let span = self.body.local_decls[local].source_info.span;
 419             span_bug!(span, "{:?} not promotable, qualif_local shouldn't have been called", local);
 420         }
 421     }
 422
 423     // FIXME(eddyb) maybe cache this?
 424     fn validate_local(&self, local: Local) -> Result<(), Unpromotable> {
 425         if let TempState::Defined { location: loc, .. } = self.temps[local] {
 426             let num_stmts = self.body[loc.block].statements.len();
 427
 428             if loc.statement_index < num_stmts {
 429                 let statement = &self.body[loc.block].statements[loc.statement_index];
 430                 match &statement.kind {
 431                     StatementKind::Assign(box(_, rhs)) => self.validate_rvalue(rhs),
 432                     _ => {
 433                         span_bug!(statement.source_info.span, "{:?} is not an assignment",
 434                                 statement);
 435                     }
 436                 }
 437             } else {
 438                 let terminator = self.body[loc.block].terminator();
 439                 match &terminator.kind {
 440                     TerminatorKind::Call { func, args, .. } => self.validate_call(func, args),
 441                     kind => {
 442                         span_bug!(terminator.source_info.span, "{:?} not promotable", kind);
 443                     }
 444                 }
 445             }
 446         } else {
 447             Err(Unpromotable)
 448         }
 449     }
 450
 451     fn validate_place(&self, place: PlaceRef<'_, 'tcx>) -> Result<(), Unpromotable> {
 452         match place {
 453             PlaceRef {
 454                 base: PlaceBase::Local(local),
 455                 projection: [],
 456             } => self.validate_local(*local),
 457             PlaceRef {
 458                 base: PlaceBase::Static(box Static {
 459                     kind: StaticKind::Promoted { .. },
 460                     ..
 461                 }),
 462                 projection: [],
 463             } => bug!("qualifying already promoted MIR"),
 464             PlaceRef {
 465                 base: PlaceBase::Static(box Static {
 466                     kind: StaticKind::Static,
 467                     def_id,
 468                     ..
 469                 }),
 470                 projection: [],
 471             } => {
 472                 // Only allow statics (not consts) to refer to other statics.
 473                 // FIXME(eddyb) does this matter at all for promotion?
 474                 let is_static = self.const_kind.map_or(false, |k| k.is_static());
 475                 if !is_static {
 476                     return Err(Unpromotable);
 477                 }
 478
 479                 let is_thread_local = self.tcx.has_attr(*def_id, sym::thread_local);
 480                 if is_thread_local {
 481                     return Err(Unpromotable);
 482                 }
 483
 484                 Ok(())
 485             }
 486             PlaceRef {
 487                 base: _,
 488                 projection: [proj_base @ .., elem],
 489             } => {
 490                 match *elem {
 491                     ProjectionElem::Deref |
 492                     ProjectionElem::Downcast(..) => return Err(Unpromotable),
 493
 494                     ProjectionElem::ConstantIndex {..} |
 495                     ProjectionElem::Subslice {..} => {}
 496
 497                     ProjectionElem::Index(local) => {
 498                         self.validate_local(local)?;
 499                     }
 500
 501                     ProjectionElem::Field(..) => {
 502                         if self.const_kind.is_none() {
 503                             let base_ty =
 504                                 Place::ty_from(place.base, proj_base, self.body, self.tcx).ty;
 505                             if let Some(def) = base_ty.ty_adt_def() {
 506                                 // No promotion of union field accesses.
 507                                 if def.is_union() {
 508                                     return Err(Unpromotable);
 509                                 }
 510                             }
 511                         }
 512                     }
 513                 }
 514
 515                 self.validate_place(PlaceRef {
 516                     base: place.base,
 517                     projection: proj_base,
 518                 })
 519             }
 520         }
 521     }
 522
 523     fn validate_operand(&self, operand: &Operand<'tcx>) -> Result<(), Unpromotable> {
 524         match operand {
 525             Operand::Copy(place) |
 526             Operand::Move(place) => self.validate_place(place.as_ref()),
 527
 528             Operand::Constant(constant) => {
 529                 if let ConstValue::Unevaluated(def_id, _) = constant.literal.val {
 530                     if self.tcx.trait_of_item(def_id).is_some() {
 531                         // Don't peek inside trait associated constants.
 532                         // (see below what we do for other consts, for now)
 533                     } else {
 534                         // HACK(eddyb) ensure that errors propagate correctly.
 535                         // FIXME(eddyb) remove this once the old promotion logic
 536                         // is gone - we can always promote constants even if they
 537                         // fail to pass const-checking, as compilation would've
 538                         // errored independently and promotion can't change that.
 539                         let (bits, _) = self.tcx.at(constant.span).mir_const_qualif(def_id);
 540                         if bits == super::qualify_consts::QUALIF_ERROR_BIT {
 541                             self.tcx.sess.delay_span_bug(
 542                                 constant.span,
 543                                 "promote_consts: MIR had errors",
 544                             );
 545                             return Err(Unpromotable);
 546                         }
 547                     }
 548                 }
 549
 550                 Ok(())
 551             }
 552         }
 553     }
 554
 555     fn validate_rvalue(&self, rvalue: &Rvalue<'tcx>) -> Result<(), Unpromotable> {
 556         match *rvalue {
 557             Rvalue::Cast(CastKind::Misc, ref operand, cast_ty) if self.const_kind.is_none() => {
 558                 let operand_ty = operand.ty(self.body, self.tcx);
 559                 let cast_in = CastTy::from_ty(operand_ty).expect("bad input type for cast");
 560                 let cast_out = CastTy::from_ty(cast_ty).expect("bad output type for cast");
 561                 match (cast_in, cast_out) {
 562                     (CastTy::Ptr(_), CastTy::Int(_)) |
 563                     (CastTy::FnPtr, CastTy::Int(_)) => {
 564                         // in normal functions, mark such casts as not promotable
 565                         return Err(Unpromotable);
 566                     }
 567                     _ => {}
 568                 }
 569             }
 570
 571             Rvalue::BinaryOp(op, ref lhs, _) if self.const_kind.is_none() => {
 572                 if let ty::RawPtr(_) | ty::FnPtr(..) = lhs.ty(self.body, self.tcx).kind {
 573                     assert!(op == BinOp::Eq || op == BinOp::Ne ||
 574                             op == BinOp::Le || op == BinOp::Lt ||
 575                             op == BinOp::Ge || op == BinOp::Gt ||
 576                             op == BinOp::Offset);
 577
 578                     // raw pointer operations are not allowed inside promoteds
 579                     return Err(Unpromotable);
 580                 }
 581             }
 582
 583             Rvalue::NullaryOp(NullOp::Box, _) => return Err(Unpromotable),
 584
 585             _ => {}
 586         }
 587
 588         match rvalue {
 589             Rvalue::NullaryOp(..) => Ok(()),
 590
 591             Rvalue::Discriminant(place) |
 592             Rvalue::Len(place) => self.validate_place(place.as_ref()),
 593
 594             Rvalue::Use(operand) |
 595             Rvalue::Repeat(operand, _) |
 596             Rvalue::UnaryOp(_, operand) |
 597             Rvalue::Cast(_, operand, _) => self.validate_operand(operand),
 598
 599             Rvalue::BinaryOp(_, lhs, rhs) |
 600             Rvalue::CheckedBinaryOp(_, lhs, rhs) => {
 601                 self.validate_operand(lhs)?;
 602                 self.validate_operand(rhs)
 603             }
 604
 605             Rvalue::Ref(_, kind, place) => {
 606                 if let BorrowKind::Mut { .. } = kind {
 607                     let ty = place.ty(self.body, self.tcx).ty;
 608
 609                     // In theory, any zero-sized value could be borrowed
 610                     // mutably without consequences. However, only &mut []
 611                     // is allowed right now, and only in functions.
 612                     if self.const_kind == Some(ConstKind::StaticMut) {
 613                         // Inside a `static mut`, &mut [...] is also allowed.
 614                         match ty.kind {
 615                             ty::Array(..) | ty::Slice(_) => {}
 616                             _ => return Err(Unpromotable),
 617                         }
 618                     } else if let ty::Array(_, len) = ty.kind {
 619                         // FIXME(eddyb): We only return `Unpromotable` for `&mut []` inside a
 620                         // const context which seems unnecessary given that this is merely a ZST.
 621                         match len.try_eval_usize(self.tcx, self.param_env) {
 622                             Some(0) if self.const_kind.is_none() => {},
 623                             _ => return Err(Unpromotable),
 624                         }
 625                     } else {
 626                         return Err(Unpromotable);
 627                     }
 628                 }
 629
 630                 // Special-case reborrows to be more like a copy of the reference.
 631                 let mut place = place.as_ref();
 632                 if let [proj_base @ .., ProjectionElem::Deref] = &place.projection {
 633                     let base_ty =
 634                         Place::ty_from(&place.base, proj_base, self.body, self.tcx).ty;
 635                     if let ty::Ref(..) = base_ty.kind {
 636                         place = PlaceRef {
 637                             base: &place.base,
 638                             projection: proj_base,
 639                         };
 640                     }
 641                 }
 642
 643                 self.validate_place(place)?;
 644
 645                 // HACK(eddyb) this should compute the same thing as
 646                 // `<HasMutInterior as Qualif>::in_projection` from
 647                 // `check_consts::qualifs` but without recursion.
 648                 let mut has_mut_interior = match place.base {
 649                     PlaceBase::Local(local) => {
 650                         self.qualif_local::<qualifs::HasMutInterior>(*local)
 651                     }
 652                     PlaceBase::Static(_) => false,
 653                 };
 654                 if has_mut_interior {
 655                     let mut place_projection = place.projection;
 656                     // FIXME(eddyb) use a forward loop instead of a reverse one.
 657                     while let [proj_base @ .., elem] = place_projection {
 658                         // FIXME(eddyb) this is probably excessive, with
 659                         // the exception of `union` member accesses.
 660                         let ty = Place::ty_from(place.base, proj_base, self.body, self.tcx)
 661                             .projection_ty(self.tcx, elem)
 662                             .ty;
 663                         if ty.is_freeze(self.tcx, self.param_env, DUMMY_SP) {
 664                             has_mut_interior = false;
 665                             break;
 666                         }
 667
 668                         place_projection = proj_base;
 669                     }
 670                 }
 671                 if has_mut_interior {
 672                     return Err(Unpromotable);
 673                 }
 674
 675                 Ok(())
 676             }
 677
 678             Rvalue::Aggregate(_, ref operands) => {
 679                 for o in operands {
 680                     self.validate_operand(o)?;
 681                 }
 682
 683                 Ok(())
 684             }
 685         }
 686     }
 687
 688     fn validate_call(
 689         &self,
 690         callee: &Operand<'tcx>,
 691         args: &[Operand<'tcx>],
 692     ) -> Result<(), Unpromotable> {
 693         let fn_ty = callee.ty(self.body, self.tcx);
 694
 695         if !self.explicit && self.const_kind.is_none() {
 696             if let ty::FnDef(def_id, _) = fn_ty.kind {
 697                 // Never promote runtime `const fn` calls of
 698                 // functions without `#[rustc_promotable]`.
 699                 if !self.tcx.is_promotable_const_fn(def_id) {
 700                     return Err(Unpromotable);
 701                 }
 702             }
 703         }
 704
 705         let is_const_fn = match fn_ty.kind {
 706             ty::FnDef(def_id, _) => {
 707                 self.tcx.is_const_fn(def_id) ||
 708                 self.tcx.is_unstable_const_fn(def_id).is_some() ||
 709                 is_lang_panic_fn(self.tcx, self.def_id)
 710             }
 711             _ => false,
 712         };
 713         if !is_const_fn {
 714             return Err(Unpromotable);
 715         }
 716
 717         self.validate_operand(callee)?;
 718         for arg in args {
 719             self.validate_operand(arg)?;
 720         }
 721
 722         Ok(())
 723     }
 724 }
 725
 726 // FIXME(eddyb) remove the differences for promotability in `static`, `const`, `const fn`.
 727 pub fn validate_candidates(
 728     tcx: TyCtxt<'tcx>,
 729     body: &Body<'tcx>,
 730     def_id: DefId,
 731     temps: &IndexVec<Local, TempState>,
 732     candidates: &[Candidate],
 733 ) -> Vec<Candidate> {
 734     let mut validator = Validator {
 735         item: Item::new(tcx, def_id, body),
 736         temps,
 737         explicit: false,
 738     };
 739
 740     candidates.iter().copied().filter(|&candidate| {
 741         validator.explicit = candidate.forces_explicit_promotion();
 742
 743         // FIXME(eddyb) also emit the errors for shuffle indices
 744         // and `#[rustc_args_required_const]` arguments here.
 745
 746         validator.validate_candidate(candidate).is_ok()
 747     }).collect()
 748 }
 749
 750 struct Promoter<'a, 'tcx> {
 751     tcx: TyCtxt<'tcx>,
 752     source: &'a mut Body<'tcx>,
 753     promoted: Body<'tcx>,
 754     temps: &'a mut IndexVec<Local, TempState>,
 755
 756     /// If true, all nested temps are also kept in the
 757     /// source MIR, not moved to the promoted MIR.
 758     keep_original: bool,
 759 }
 760
 761 impl<'a, 'tcx> Promoter<'a, 'tcx> {
 762     fn new_block(&mut self) -> BasicBlock {
 763         let span = self.promoted.span;
 764         self.promoted.basic_blocks_mut().push(BasicBlockData {
 765             statements: vec![],
 766             terminator: Some(Terminator {
 767                 source_info: SourceInfo {
 768                     span,
 769                     scope: OUTERMOST_SOURCE_SCOPE
 770                 },
 771                 kind: TerminatorKind::Return
 772             }),
 773             is_cleanup: false
 774         })
 775     }
 776
 777     fn assign(&mut self, dest: Local, rvalue: Rvalue<'tcx>, span: Span) {
 778         let last = self.promoted.basic_blocks().last().unwrap();
 779         let data = &mut self.promoted[last];
 780         data.statements.push(Statement {
 781             source_info: SourceInfo {
 782                 span,
 783                 scope: OUTERMOST_SOURCE_SCOPE
 784             },
 785             kind: StatementKind::Assign(box(Place::from(dest), rvalue))
 786         });
 787     }
 788
 789     fn is_temp_kind(&self, local: Local) -> bool {
 790         self.source.local_kind(local) == LocalKind::Temp
 791     }
 792
 793     /// Copies the initialization of this temp to the
 794     /// promoted MIR, recursing through temps.
 795     fn promote_temp(&mut self, temp: Local) -> Local {
 796         let old_keep_original = self.keep_original;
 797         let loc = match self.temps[temp] {
 798             TempState::Defined { location, uses } if uses > 0 => {
 799                 if uses > 1 {
 800                     self.keep_original = true;
 801                 }
 802                 location
 803             }
 804             state =>  {
 805                 span_bug!(self.promoted.span, "{:?} not promotable: {:?}",
 806                           temp, state);
 807             }
 808         };
 809         if !self.keep_original {
 810             self.temps[temp] = TempState::PromotedOut;
 811         }
 812
 813         let num_stmts = self.source[loc.block].statements.len();
 814         let new_temp = self.promoted.local_decls.push(
 815             LocalDecl::new_temp(self.source.local_decls[temp].ty,
 816                                 self.source.local_decls[temp].source_info.span));
 817
 818         debug!("promote({:?} @ {:?}/{:?}, {:?})",
 819                temp, loc, num_stmts, self.keep_original);
 820
 821         // First, take the Rvalue or Call out of the source MIR,
 822         // or duplicate it, depending on keep_original.
 823         if loc.statement_index < num_stmts {
 824             let (mut rvalue, source_info) = {
 825                 let statement = &mut self.source[loc.block].statements[loc.statement_index];
 826                 let rhs = match statement.kind {
 827                     StatementKind::Assign(box(_, ref mut rhs)) => rhs,
 828                     _ => {
 829                         span_bug!(statement.source_info.span, "{:?} is not an assignment",
 830                                   statement);
 831                     }
 832                 };
 833
 834                 (if self.keep_original {
 835                     rhs.clone()
 836                 } else {
 837                     let unit = Rvalue::Aggregate(box AggregateKind::Tuple, vec![]);
 838                     mem::replace(rhs, unit)
 839                 }, statement.source_info)
 840             };
 841
 842             self.visit_rvalue(&mut rvalue, loc);
 843             self.assign(new_temp, rvalue, source_info.span);
 844         } else {
 845             let terminator = if self.keep_original {
 846                 self.source[loc.block].terminator().clone()
 847             } else {
 848                 let terminator = self.source[loc.block].terminator_mut();
 849                 let target = match terminator.kind {
 850                     TerminatorKind::Call { destination: Some((_, target)), .. } => target,
 851                     ref kind => {
 852                         span_bug!(terminator.source_info.span, "{:?} not promotable", kind);
 853                     }
 854                 };
 855                 Terminator {
 856                     source_info: terminator.source_info,
 857                     kind: mem::replace(&mut terminator.kind, TerminatorKind::Goto {
 858                         target,
 859                     })
 860                 }
 861             };
 862
 863             match terminator.kind {
 864                 TerminatorKind::Call { mut func, mut args, from_hir_call, .. } => {
 865                     self.visit_operand(&mut func, loc);
 866                     for arg in &mut args {
 867                         self.visit_operand(arg, loc);
 868                     }
 869
 870                     let last = self.promoted.basic_blocks().last().unwrap();
 871                     let new_target = self.new_block();
 872
 873                     *self.promoted[last].terminator_mut() = Terminator {
 874                         kind: TerminatorKind::Call {
 875                             func,
 876                             args,
 877                             cleanup: None,
 878                             destination: Some(
 879                                 (Place::from(new_temp), new_target)
 880                             ),
 881                             from_hir_call,
 882                         },
 883                         ..terminator
 884                     };
 885                 }
 886                 ref kind => {
 887                     span_bug!(terminator.source_info.span, "{:?} not promotable", kind);
 888                 }
 889             };
 890         };
 891
 892         self.keep_original = old_keep_original;
 893         new_temp
 894     }
 895
 896     fn promote_candidate(
 897         mut self,
 898         def_id: DefId,
 899         candidate: Candidate,
 900         next_promoted_id: usize,
 901     ) -> Option<Body<'tcx>> {
 902         let mut operand = {
 903             let promoted = &mut self.promoted;
 904             let promoted_id = Promoted::new(next_promoted_id);
 905             let tcx = self.tcx;
 906             let mut promoted_place = |ty, span| {
 907                 promoted.span = span;
 908                 promoted.local_decls[RETURN_PLACE] = LocalDecl::new_return_place(ty, span);
 909                 Place {
 910                     base: PlaceBase::Static(box Static {
 911                         kind:
 912                             StaticKind::Promoted(
 913                                 promoted_id,
 914                                 InternalSubsts::identity_for_item(tcx, def_id),
 915                             ),
 916                         ty,
 917                         def_id,
 918                     }),
 919                     projection: List::empty(),
 920                 }
 921             };
 922             let (blocks, local_decls) = self.source.basic_blocks_and_local_decls_mut();
 923             match candidate {
 924                 Candidate::Ref(loc) => {
 925                     let ref mut statement = blocks[loc.block].statements[loc.statement_index];
 926                     match statement.kind {
 927                         StatementKind::Assign(box(_, Rvalue::Ref(_, _, ref mut place))) => {
 928                             // Use the underlying local for this (necessarily interior) borrow.
 929                             let ty = place.base.ty(local_decls).ty;
 930                             let span = statement.source_info.span;
 931
 932                             Operand::Move(Place {
 933                                 base: mem::replace(
 934                                     &mut place.base,
 935                                     promoted_place(ty, span).base,
 936                                 ),
 937                                 projection: List::empty(),
 938                             })
 939                         }
 940                         _ => bug!()
 941                     }
 942                 }
 943                 Candidate::Repeat(loc) => {
 944                     let ref mut statement = blocks[loc.block].statements[loc.statement_index];
 945                     match statement.kind {
 946                         StatementKind::Assign(box(_, Rvalue::Repeat(ref mut operand, _))) => {
 947                             let ty = operand.ty(local_decls, self.tcx);
 948                             let span = statement.source_info.span;
 949                             mem::replace(
 950                                 operand,
 951                                 Operand::Copy(promoted_place(ty, span))
 952                             )
 953                         }
 954                         _ => bug!()
 955                     }
 956                 },
 957                 Candidate::Argument { bb, index } => {
 958                     let terminator = blocks[bb].terminator_mut();
 959                     match terminator.kind {
 960                         TerminatorKind::Call { ref mut args, .. } => {
 961                             let ty = args[index].ty(local_decls, self.tcx);
 962                             let span = terminator.source_info.span;
 963                             let operand = Operand::Copy(promoted_place(ty, span));
 964                             mem::replace(&mut args[index], operand)
 965                         }
 966                         // We expected a `TerminatorKind::Call` for which we'd like to promote an
 967                         // argument. `qualify_consts` saw a `TerminatorKind::Call` here, but
 968                         // we are seeing a `Goto`. That means that the `promote_temps` method
 969                         // already promoted this call away entirely. This case occurs when calling
 970                         // a function requiring a constant argument and as that constant value
 971                         // providing a value whose computation contains another call to a function
 972                         // requiring a constant argument.
 973                         TerminatorKind::Goto { .. } => return None,
 974                         _ => bug!()
 975                     }
 976                 }
 977             }
 978         };
 979
 980         assert_eq!(self.new_block(), START_BLOCK);
 981         self.visit_operand(&mut operand, Location {
 982             block: BasicBlock::new(0),
 983             statement_index: usize::MAX
 984         });
 985
 986         let span = self.promoted.span;
 987         self.assign(RETURN_PLACE, Rvalue::Use(operand), span);
 988         Some(self.promoted)
 989     }
 990 }
 991
 992 /// Replaces all temporaries with their promoted counterparts.
 993 impl<'a, 'tcx> MutVisitor<'tcx> for Promoter<'a, 'tcx> {
 994     fn tcx(&self) -> TyCtxt<'tcx> {
 995         self.tcx
 996     }
 997
 998     fn visit_local(&mut self,
 999                    local: &mut Local,
1000                    _: PlaceContext,
1001                    _: Location) {
1002         if self.is_temp_kind(*local) {
1003             *local = self.promote_temp(*local);
1004         }
1005     }
1006
1007     fn process_projection_elem(
1008         &mut self,
1009         elem: &PlaceElem<'tcx>,
1010     ) -> Option<PlaceElem<'tcx>> {
1011         match elem {
1012             PlaceElem::Index(local) if self.is_temp_kind(*local) => {
1013                 Some(PlaceElem::Index(self.promote_temp(*local)))
1014             }
1015             _ => None,
1016         }
1017     }
1018 }
1019
1020 pub fn promote_candidates<'tcx>(
1021     def_id: DefId,
1022     body: &mut Body<'tcx>,
1023     tcx: TyCtxt<'tcx>,
1024     mut temps: IndexVec<Local, TempState>,
1025     candidates: Vec<Candidate>,
1026 ) -> IndexVec<Promoted, Body<'tcx>> {
1027     // Visit candidates in reverse, in case they're nested.
1028     debug!("promote_candidates({:?})", candidates);
1029
1030     let mut promotions = IndexVec::new();
1031
1032     for candidate in candidates.into_iter().rev() {
1033         match candidate {
1034             Candidate::Repeat(Location { block, statement_index }) |
1035             Candidate::Ref(Location { block, statement_index }) => {
1036                 match &body[block].statements[statement_index].kind {
1037                     StatementKind::Assign(box(place, _)) => {
1038                         if let Some(local) = place.as_local() {
1039                             if temps[local] == TempState::PromotedOut {
1040                                 // Already promoted.
1041                                 continue;
1042                             }
1043                         }
1044                     }
1045                     _ => {}
1046                 }
1047             }
1048             Candidate::Argument { .. } => {}
1049         }
1050
1051
1052         // Declare return place local so that `mir::Body::new` doesn't complain.
1053         let initial_locals = iter::once(
1054             LocalDecl::new_return_place(tcx.types.never, body.span)
1055         ).collect();
1056
1057         let promoter = Promoter {
1058             promoted: Body::new(
1059                 IndexVec::new(),
1060                 // FIXME: maybe try to filter this to avoid blowing up
1061                 // memory usage?
1062                 body.source_scopes.clone(),
1063                 body.source_scope_local_data.clone(),
1064                 None,
1065                 initial_locals,
1066                 IndexVec::new(),
1067                 0,
1068                 vec![],
1069                 body.span,
1070                 vec![],
1071             ),
1072             tcx,
1073             source: body,
1074             temps: &mut temps,
1075             keep_original: false
1076         };
1077
1078         //FIXME(oli-obk): having a `maybe_push()` method on `IndexVec` might be nice
1079         if let Some(promoted) = promoter.promote_candidate(def_id, candidate, promotions.len()) {
1080             promotions.push(promoted);
1081         }
1082     }
1083
1084     // Eliminate assignments to, and drops of promoted temps.
1085     let promoted = |index: Local| temps[index] == TempState::PromotedOut;
1086     for block in body.basic_blocks_mut() {
1087         block.statements.retain(|statement| {
1088             match &statement.kind {
1089                 StatementKind::Assign(box(place, _)) => {
1090                     if let Some(index) = place.as_local() {
1091                         !promoted(index)
1092                     } else {
1093                         true
1094                     }
1095                 }
1096                 StatementKind::StorageLive(index) |
1097                 StatementKind::StorageDead(index) => {
1098                     !promoted(*index)
1099                 }
1100                 _ => true
1101             }
1102         });
1103         let terminator = block.terminator_mut();
1104         match &terminator.kind {
1105             TerminatorKind::Drop { location: place, target, .. } => {
1106                 if let Some(index) = place.as_local() {
1107                     if promoted(index) {
1108                         terminator.kind = TerminatorKind::Goto {
1109                             target: *target,
1110                         };
1111                     }
1112                 }
1113             }
1114             _ => {}
1115         }
1116     }
1117
1118     promotions
1119 }