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