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