src/librustc_mir/transform/const_prop.rs

   1 //! Propagates constants for early reporting of statically known
   2 //! assertion failures
   3
   4 use rustc::hir::def::DefKind;
   5 use rustc::mir::{
   6     AggregateKind, Constant, Location, Place, PlaceBase, Body, Operand, Rvalue,
   7     Local, NullOp, UnOp, StatementKind, Statement, LocalKind, Static, StaticKind,
   8     TerminatorKind, Terminator,  ClearCrossCrate, SourceInfo, BinOp, ProjectionElem,
   9     SourceScope, SourceScopeLocalData, LocalDecl, Promoted,
  10 };
  11 use rustc::mir::visit::{
  12     Visitor, PlaceContext, MutatingUseContext, MutVisitor, NonMutatingUseContext,
  13 };
  14 use rustc::mir::interpret::{InterpError, Scalar, GlobalId, InterpResult};
  15 use rustc::ty::{self, Instance, ParamEnv, Ty, TyCtxt};
  16 use syntax_pos::{Span, DUMMY_SP};
  17 use rustc::ty::subst::InternalSubsts;
  18 use rustc_data_structures::indexed_vec::IndexVec;
  19 use rustc::ty::layout::{
  20     LayoutOf, TyLayout, LayoutError, HasTyCtxt, TargetDataLayout, HasDataLayout, Size,
  21 };
  22
  23 use crate::interpret::{
  24     self, InterpretCx, ScalarMaybeUndef, Immediate, OpTy, ImmTy, MemoryKind,
  25 };
  26 use crate::const_eval::{
  27     CompileTimeInterpreter, error_to_const_error, eval_promoted, mk_eval_cx,
  28 };
  29 use crate::transform::{MirPass, MirSource};
  30
  31 pub struct ConstProp;
  32
  33 impl MirPass for ConstProp {
  34     fn run_pass<'tcx>(&self, tcx: TyCtxt<'tcx>, source: MirSource<'tcx>, body: &mut Body<'tcx>) {
  35         // will be evaluated by miri and produce its errors there
  36         if source.promoted.is_some() {
  37             return;
  38         }
  39
  40         use rustc::hir::map::blocks::FnLikeNode;
  41         let hir_id = tcx.hir().as_local_hir_id(source.def_id())
  42                               .expect("Non-local call to local provider is_const_fn");
  43
  44         let is_fn_like = FnLikeNode::from_node(tcx.hir().get_by_hir_id(hir_id)).is_some();
  45         let is_assoc_const = match tcx.def_kind(source.def_id()) {
  46             Some(DefKind::AssocConst) => true,
  47             _ => false,
  48         };
  49
  50         // Only run const prop on functions, methods, closures and associated constants
  51         if !is_fn_like && !is_assoc_const  {
  52             // skip anon_const/statics/consts because they'll be evaluated by miri anyway
  53             trace!("ConstProp skipped for {:?}", source.def_id());
  54             return
  55         }
  56
  57         trace!("ConstProp starting for {:?}", source.def_id());
  58
  59         // FIXME(oli-obk, eddyb) Optimize locals (or even local paths) to hold
  60         // constants, instead of just checking for const-folding succeeding.
  61         // That would require an uniform one-def no-mutation analysis
  62         // and RPO (or recursing when needing the value of a local).
  63         let mut optimization_finder = ConstPropagator::new(body, tcx, source);
  64         optimization_finder.visit_body(body);
  65
  66         // put back the data we stole from `mir`
  67         std::mem::replace(
  68             &mut body.source_scope_local_data,
  69             optimization_finder.source_scope_local_data
  70         );
  71         std::mem::replace(
  72             &mut body.promoted,
  73             optimization_finder.promoted
  74         );
  75
  76         trace!("ConstProp done for {:?}", source.def_id());
  77     }
  78 }
  79
  80 type Const<'tcx> = OpTy<'tcx>;
  81
  82 /// Finds optimization opportunities on the MIR.
  83 struct ConstPropagator<'mir, 'tcx> {
  84     ecx: InterpretCx<'mir, 'tcx, CompileTimeInterpreter<'mir, 'tcx>>,
  85     tcx: TyCtxt<'tcx>,
  86     source: MirSource<'tcx>,
  87     places: IndexVec<Local, Option<Const<'tcx>>>,
  88     can_const_prop: IndexVec<Local, bool>,
  89     param_env: ParamEnv<'tcx>,
  90     source_scope_local_data: ClearCrossCrate<IndexVec<SourceScope, SourceScopeLocalData>>,
  91     local_decls: IndexVec<Local, LocalDecl<'tcx>>,
  92     promoted: IndexVec<Promoted, Body<'tcx>>,
  93 }
  94
  95 impl<'mir, 'tcx> LayoutOf for ConstPropagator<'mir, 'tcx> {
  96     type Ty = Ty<'tcx>;
  97     type TyLayout = Result<TyLayout<'tcx>, LayoutError<'tcx>>;
  98
  99     fn layout_of(&self, ty: Ty<'tcx>) -> Self::TyLayout {
 100         self.tcx.layout_of(self.param_env.and(ty))
 101     }
 102 }
 103
 104 impl<'mir, 'tcx> HasDataLayout for ConstPropagator<'mir, 'tcx> {
 105     #[inline]
 106     fn data_layout(&self) -> &TargetDataLayout {
 107         &self.tcx.data_layout
 108     }
 109 }
 110
 111 impl<'mir, 'tcx> HasTyCtxt<'tcx> for ConstPropagator<'mir, 'tcx> {
 112     #[inline]
 113     fn tcx(&self) -> TyCtxt<'tcx> {
 114         self.tcx
 115     }
 116 }
 117
 118 impl<'mir, 'tcx> ConstPropagator<'mir, 'tcx> {
 119     fn new(
 120         body: &mut Body<'tcx>,
 121         tcx: TyCtxt<'tcx>,
 122         source: MirSource<'tcx>,
 123     ) -> ConstPropagator<'mir, 'tcx> {
 124         let param_env = tcx.param_env(source.def_id());
 125         let ecx = mk_eval_cx(tcx, tcx.def_span(source.def_id()), param_env);
 126         let can_const_prop = CanConstProp::check(body);
 127         let source_scope_local_data = std::mem::replace(
 128             &mut body.source_scope_local_data,
 129             ClearCrossCrate::Clear
 130         );
 131         let promoted = std::mem::replace(
 132             &mut body.promoted,
 133             IndexVec::new()
 134         );
 135
 136         ConstPropagator {
 137             ecx,
 138             tcx,
 139             source,
 140             param_env,
 141             can_const_prop,
 142             places: IndexVec::from_elem(None, &body.local_decls),
 143             source_scope_local_data,
 144             //FIXME(wesleywiser) we can't steal this because `Visitor::super_visit_body()` needs it
 145             local_decls: body.local_decls.clone(),
 146             promoted,
 147         }
 148     }
 149
 150     fn get_const(&self, local: Local) -> Option<Const<'tcx>> {
 151         self.places[local]
 152     }
 153
 154     fn set_const(&mut self, local: Local, c: Option<Const<'tcx>>) {
 155         self.places[local] = c;
 156     }
 157
 158     fn use_ecx<F, T>(
 159         &mut self,
 160         source_info: SourceInfo,
 161         f: F
 162     ) -> Option<T>
 163     where
 164         F: FnOnce(&mut Self) -> InterpResult<'tcx, T>,
 165     {
 166         self.ecx.tcx.span = source_info.span;
 167         let lint_root = match self.source_scope_local_data {
 168             ClearCrossCrate::Set(ref ivs) => {
 169                 //FIXME(#51314): remove this check
 170                 if source_info.scope.index() >= ivs.len() {
 171                     return None;
 172                 }
 173                 ivs[source_info.scope].lint_root
 174             },
 175             ClearCrossCrate::Clear => return None,
 176         };
 177         let r = match f(self) {
 178             Ok(val) => Some(val),
 179             Err(error) => {
 180                 let diagnostic = error_to_const_error(&self.ecx, error);
 181                 use rustc::mir::interpret::InterpError::*;
 182                 match diagnostic.error {
 183                     // don't report these, they make no sense in a const prop context
 184                     | MachineError(_)
 185                     | Exit(_)
 186                     // at runtime these transformations might make sense
 187                     // FIXME: figure out the rules and start linting
 188                     | FunctionAbiMismatch(..)
 189                     | FunctionArgMismatch(..)
 190                     | FunctionRetMismatch(..)
 191                     | FunctionArgCountMismatch
 192                     // fine at runtime, might be a register address or sth
 193                     | ReadBytesAsPointer
 194                     // fine at runtime
 195                     | ReadForeignStatic
 196                     | Unimplemented(_)
 197                     // don't report const evaluator limits
 198                     | StackFrameLimitReached
 199                     | NoMirFor(..)
 200                     | InlineAsm
 201                     => {},
 202
 203                     | InvalidMemoryAccess
 204                     | DanglingPointerDeref
 205                     | DoubleFree
 206                     | InvalidFunctionPointer
 207                     | InvalidBool
 208                     | InvalidDiscriminant(..)
 209                     | PointerOutOfBounds { .. }
 210                     | InvalidNullPointerUsage
 211                     | ValidationFailure(..)
 212                     | InvalidPointerMath
 213                     | ReadUndefBytes(_)
 214                     | DeadLocal
 215                     | InvalidBoolOp(_)
 216                     | DerefFunctionPointer
 217                     | ExecuteMemory
 218                     | Intrinsic(..)
 219                     | InvalidChar(..)
 220                     | AbiViolation(_)
 221                     | AlignmentCheckFailed{..}
 222                     | CalledClosureAsFunction
 223                     | VtableForArgumentlessMethod
 224                     | ModifiedConstantMemory
 225                     | ModifiedStatic
 226                     | AssumptionNotHeld
 227                     // FIXME: should probably be removed and turned into a bug! call
 228                     | TypeNotPrimitive(_)
 229                     | ReallocatedWrongMemoryKind(_, _)
 230                     | DeallocatedWrongMemoryKind(_, _)
 231                     | ReallocateNonBasePtr
 232                     | DeallocateNonBasePtr
 233                     | IncorrectAllocationInformation(..)
 234                     | UnterminatedCString(_)
 235                     | HeapAllocZeroBytes
 236                     | HeapAllocNonPowerOfTwoAlignment(_)
 237                     | Unreachable
 238                     | ReadFromReturnPointer
 239                     | GeneratorResumedAfterReturn
 240                     | GeneratorResumedAfterPanic
 241                     | ReferencedConstant
 242                     | InfiniteLoop
 243                     => {
 244                         // FIXME: report UB here
 245                     },
 246
 247                     | OutOfTls
 248                     | TlsOutOfBounds
 249                     | PathNotFound(_)
 250                     => bug!("these should not be in rustc, but in miri's machine errors"),
 251
 252                     | Layout(_)
 253                     | UnimplementedTraitSelection
 254                     | TypeckError
 255                     | TooGeneric
 256                     // these are just noise
 257                     => {},
 258
 259                     // non deterministic
 260                     | ReadPointerAsBytes
 261                     // FIXME: implement
 262                     => {},
 263
 264                     | Panic { .. }
 265                     | BoundsCheck{..}
 266                     | Overflow(_)
 267                     | OverflowNeg
 268                     | DivisionByZero
 269                     | RemainderByZero
 270                     => {
 271                         diagnostic.report_as_lint(
 272                             self.ecx.tcx,
 273                             "this expression will panic at runtime",
 274                             lint_root,
 275                             None,
 276                         );
 277                     }
 278                 }
 279                 None
 280             },
 281         };
 282         self.ecx.tcx.span = DUMMY_SP;
 283         r
 284     }
 285
 286     fn eval_constant(
 287         &mut self,
 288         c: &Constant<'tcx>,
 289     ) -> Option<Const<'tcx>> {
 290         self.ecx.tcx.span = c.span;
 291         match self.ecx.eval_const_to_op(c.literal, None) {
 292             Ok(op) => {
 293                 Some(op)
 294             },
 295             Err(error) => {
 296                 let err = error_to_const_error(&self.ecx, error);
 297                 err.report_as_error(self.ecx.tcx, "erroneous constant used");
 298                 None
 299             },
 300         }
 301     }
 302
 303     fn eval_place(&mut self, place: &Place<'tcx>, source_info: SourceInfo) -> Option<Const<'tcx>> {
 304         trace!("eval_place(place={:?})", place);
 305         place.iterate(|place_base, place_projection| {
 306             let mut eval = match place_base {
 307                 PlaceBase::Local(loc) => self.get_const(*loc).clone()?,
 308                 PlaceBase::Static(box Static {kind: StaticKind::Promoted(promoted), ..}) => {
 309                     let generics = self.tcx.generics_of(self.source.def_id());
 310                     if generics.requires_monomorphization(self.tcx) {
 311                         // FIXME: can't handle code with generics
 312                         return None;
 313                     }
 314                     let substs = InternalSubsts::identity_for_item(self.tcx, self.source.def_id());
 315                     let instance = Instance::new(self.source.def_id(), substs);
 316                     let cid = GlobalId {
 317                         instance,
 318                         promoted: Some(*promoted),
 319                     };
 320                     // cannot use `const_eval` here, because that would require having the MIR
 321                     // for the current function available, but we're producing said MIR right now
 322                     let res = self.use_ecx(source_info, |this| {
 323                         let body = &this.promoted[*promoted];
 324                         eval_promoted(this.tcx, cid, body, this.param_env)
 325                     })?;
 326                     trace!("evaluated promoted {:?} to {:?}", promoted, res);
 327                     res.into()
 328                 }
 329                 _ => return None,
 330             };
 331
 332             for proj in place_projection {
 333                 match proj.elem {
 334                     ProjectionElem::Field(field, _) => {
 335                         trace!("field proj on {:?}", proj.base);
 336                         eval = self.use_ecx(source_info, |this| {
 337                             this.ecx.operand_field(eval, field.index() as u64)
 338                         })?;
 339                     },
 340                     ProjectionElem::Deref => {
 341                         trace!("processing deref");
 342                         eval = self.use_ecx(source_info, |this| {
 343                             this.ecx.deref_operand(eval)
 344                         })?.into();
 345                     }
 346                     // We could get more projections by using e.g., `operand_projection`,
 347                     // but we do not even have the stack frame set up properly so
 348                     // an `Index` projection would throw us off-track.
 349                     _ => return None,
 350                 }
 351             }
 352
 353             Some(eval)
 354         })
 355     }
 356
 357     fn eval_operand(&mut self, op: &Operand<'tcx>, source_info: SourceInfo) -> Option<Const<'tcx>> {
 358         match *op {
 359             Operand::Constant(ref c) => self.eval_constant(c),
 360             | Operand::Move(ref place)
 361             | Operand::Copy(ref place) => self.eval_place(place, source_info),
 362         }
 363     }
 364
 365     fn const_prop(
 366         &mut self,
 367         rvalue: &Rvalue<'tcx>,
 368         place_layout: TyLayout<'tcx>,
 369         source_info: SourceInfo,
 370     ) -> Option<Const<'tcx>> {
 371         let span = source_info.span;
 372         match *rvalue {
 373             Rvalue::Use(ref op) => {
 374                 self.eval_operand(op, source_info)
 375             },
 376             Rvalue::Ref(_, _, ref place) => {
 377                 let src = self.eval_place(place, source_info)?;
 378                 let mplace = src.try_as_mplace().ok()?;
 379                 Some(ImmTy::from_scalar(mplace.ptr.into(), place_layout).into())
 380             },
 381             Rvalue::Repeat(..) |
 382             Rvalue::Aggregate(..) |
 383             Rvalue::NullaryOp(NullOp::Box, _) |
 384             Rvalue::Discriminant(..) => None,
 385
 386             Rvalue::Cast(kind, ref operand, _) => {
 387                 let op = self.eval_operand(operand, source_info)?;
 388                 self.use_ecx(source_info, |this| {
 389                     let dest = this.ecx.allocate(place_layout, MemoryKind::Stack);
 390                     this.ecx.cast(op, kind, dest.into())?;
 391                     Ok(dest.into())
 392                 })
 393             },
 394             Rvalue::Len(ref place) => {
 395                 let place = self.eval_place(&place, source_info)?;
 396                 let mplace = place.try_as_mplace().ok()?;
 397
 398                 if let ty::Slice(_) = mplace.layout.ty.sty {
 399                     let len = mplace.meta.unwrap().to_usize(&self.ecx).unwrap();
 400
 401                     Some(ImmTy {
 402                         imm: Immediate::Scalar(
 403                             Scalar::from_uint(
 404                                 len,
 405                                 Size::from_bits(
 406                                     self.tcx.sess.target.usize_ty.bit_width().unwrap() as u64
 407                                 )
 408                             ).into(),
 409                         ),
 410                         layout: self.tcx.layout_of(self.param_env.and(self.tcx.types.usize)).ok()?,
 411                     }.into())
 412                 } else {
 413                     trace!("not slice: {:?}", mplace.layout.ty.sty);
 414                     None
 415                 }
 416             },
 417             Rvalue::NullaryOp(NullOp::SizeOf, ty) => {
 418                 type_size_of(self.tcx, self.param_env, ty).and_then(|n| Some(
 419                     ImmTy {
 420                         imm: Immediate::Scalar(
 421                             Scalar::from_uint(n, self.tcx.data_layout.pointer_size).into()
 422                         ),
 423                         layout: self.tcx.layout_of(self.param_env.and(self.tcx.types.usize)).ok()?,
 424                     }.into()
 425                 ))
 426             }
 427             Rvalue::UnaryOp(op, ref arg) => {
 428                 let def_id = if self.tcx.is_closure(self.source.def_id()) {
 429                     self.tcx.closure_base_def_id(self.source.def_id())
 430                 } else {
 431                     self.source.def_id()
 432                 };
 433                 let generics = self.tcx.generics_of(def_id);
 434                 if generics.requires_monomorphization(self.tcx) {
 435                     // FIXME: can't handle code with generics
 436                     return None;
 437                 }
 438
 439                 let arg = self.eval_operand(arg, source_info)?;
 440                 let val = self.use_ecx(source_info, |this| {
 441                     let prim = this.ecx.read_immediate(arg)?;
 442                     match op {
 443                         UnOp::Neg => {
 444                             // Need to do overflow check here: For actual CTFE, MIR
 445                             // generation emits code that does this before calling the op.
 446                             if prim.to_bits()? == (1 << (prim.layout.size.bits() - 1)) {
 447                                 return err!(OverflowNeg);
 448                             }
 449                         }
 450                         UnOp::Not => {
 451                             // Cannot overflow
 452                         }
 453                     }
 454                     // Now run the actual operation.
 455                     this.ecx.unary_op(op, prim)
 456                 })?;
 457                 let res = ImmTy {
 458                     imm: Immediate::Scalar(val.into()),
 459                     layout: place_layout,
 460                 };
 461                 Some(res.into())
 462             }
 463             Rvalue::CheckedBinaryOp(op, ref left, ref right) |
 464             Rvalue::BinaryOp(op, ref left, ref right) => {
 465                 trace!("rvalue binop {:?} for {:?} and {:?}", op, left, right);
 466                 let right = self.eval_operand(right, source_info)?;
 467                 let def_id = if self.tcx.is_closure(self.source.def_id()) {
 468                     self.tcx.closure_base_def_id(self.source.def_id())
 469                 } else {
 470                     self.source.def_id()
 471                 };
 472                 let generics = self.tcx.generics_of(def_id);
 473                 if generics.requires_monomorphization(self.tcx) {
 474                     // FIXME: can't handle code with generics
 475                     return None;
 476                 }
 477
 478                 let r = self.use_ecx(source_info, |this| {
 479                     this.ecx.read_immediate(right)
 480                 })?;
 481                 if op == BinOp::Shr || op == BinOp::Shl {
 482                     let left_ty = left.ty(&self.local_decls, self.tcx);
 483                     let left_bits = self
 484                         .tcx
 485                         .layout_of(self.param_env.and(left_ty))
 486                         .unwrap()
 487                         .size
 488                         .bits();
 489                     let right_size = right.layout.size;
 490                     let r_bits = r.to_scalar().and_then(|r| r.to_bits(right_size));
 491                     if r_bits.ok().map_or(false, |b| b >= left_bits as u128) {
 492                         let source_scope_local_data = match self.source_scope_local_data {
 493                             ClearCrossCrate::Set(ref data) => data,
 494                             ClearCrossCrate::Clear => return None,
 495                         };
 496                         let dir = if op == BinOp::Shr {
 497                             "right"
 498                         } else {
 499                             "left"
 500                         };
 501                         let hir_id = source_scope_local_data[source_info.scope].lint_root;
 502                         self.tcx.lint_hir(
 503                             ::rustc::lint::builtin::EXCEEDING_BITSHIFTS,
 504                             hir_id,
 505                             span,
 506                             &format!("attempt to shift {} with overflow", dir));
 507                         return None;
 508                     }
 509                 }
 510                 let left = self.eval_operand(left, source_info)?;
 511                 let l = self.use_ecx(source_info, |this| {
 512                     this.ecx.read_immediate(left)
 513                 })?;
 514                 trace!("const evaluating {:?} for {:?} and {:?}", op, left, right);
 515                 let (val, overflow) = self.use_ecx(source_info, |this| {
 516                     this.ecx.binary_op(op, l, r)
 517                 })?;
 518                 let val = if let Rvalue::CheckedBinaryOp(..) = *rvalue {
 519                     Immediate::ScalarPair(
 520                         val.into(),
 521                         Scalar::from_bool(overflow).into(),
 522                     )
 523                 } else {
 524                     if overflow {
 525                         let err = InterpError::Overflow(op).into();
 526                         let _: Option<()> = self.use_ecx(source_info, |_| Err(err));
 527                         return None;
 528                     }
 529                     Immediate::Scalar(val.into())
 530                 };
 531                 let res = ImmTy {
 532                     imm: val,
 533                     layout: place_layout,
 534                 };
 535                 Some(res.into())
 536             },
 537         }
 538     }
 539
 540     fn operand_from_scalar(&self, scalar: Scalar, ty: Ty<'tcx>, span: Span) -> Operand<'tcx> {
 541         Operand::Constant(Box::new(
 542             Constant {
 543                 span,
 544                 ty,
 545                 user_ty: None,
 546                 literal: self.tcx.mk_const(*ty::Const::from_scalar(
 547                     self.tcx,
 548                     scalar,
 549                     ty,
 550                 ))
 551             }
 552         ))
 553     }
 554
 555     fn replace_with_const(
 556         &mut self,
 557         rval: &mut Rvalue<'tcx>,
 558         value: Const<'tcx>,
 559         source_info: SourceInfo,
 560     ) {
 561         trace!("attepting to replace {:?} with {:?}", rval, value);
 562         if let Err(e) = self.ecx.validate_operand(
 563             value,
 564             vec![],
 565             // FIXME: is ref tracking too expensive?
 566             Some(&mut interpret::RefTracking::empty()),
 567         ) {
 568             trace!("validation error, attempt failed: {:?}", e);
 569             return;
 570         }
 571
 572         // FIXME> figure out what tho do when try_read_immediate fails
 573         let imm = self.use_ecx(source_info, |this| {
 574             this.ecx.try_read_immediate(value)
 575         });
 576
 577         if let Some(Ok(imm)) = imm {
 578             match *imm {
 579                 interpret::Immediate::Scalar(ScalarMaybeUndef::Scalar(scalar)) => {
 580                     *rval = Rvalue::Use(
 581                         self.operand_from_scalar(scalar, value.layout.ty, source_info.span));
 582                 },
 583                 Immediate::ScalarPair(
 584                     ScalarMaybeUndef::Scalar(one),
 585                     ScalarMaybeUndef::Scalar(two)
 586                 ) => {
 587                     let ty = &value.layout.ty.sty;
 588                     if let ty::Tuple(substs) = ty {
 589                         *rval = Rvalue::Aggregate(
 590                             Box::new(AggregateKind::Tuple),
 591                             vec![
 592                                 self.operand_from_scalar(
 593                                     one, substs[0].expect_ty(), source_info.span
 594                                 ),
 595                                 self.operand_from_scalar(
 596                                     two, substs[1].expect_ty(), source_info.span
 597                                 ),
 598                             ],
 599                         );
 600                     }
 601                 },
 602                 _ => { }
 603             }
 604         }
 605     }
 606
 607     fn should_const_prop(&self) -> bool {
 608         self.tcx.sess.opts.debugging_opts.mir_opt_level >= 2
 609     }
 610 }
 611
 612 fn type_size_of<'tcx>(
 613     tcx: TyCtxt<'tcx>,
 614     param_env: ty::ParamEnv<'tcx>,
 615     ty: Ty<'tcx>,
 616 ) -> Option<u64> {
 617     tcx.layout_of(param_env.and(ty)).ok().map(|layout| layout.size.bytes())
 618 }
 619
 620 struct CanConstProp {
 621     can_const_prop: IndexVec<Local, bool>,
 622     // false at the beginning, once set, there are not allowed to be any more assignments
 623     found_assignment: IndexVec<Local, bool>,
 624 }
 625
 626 impl CanConstProp {
 627     /// returns true if `local` can be propagated
 628     fn check(body: &Body<'_>) -> IndexVec<Local, bool> {
 629         let mut cpv = CanConstProp {
 630             can_const_prop: IndexVec::from_elem(true, &body.local_decls),
 631             found_assignment: IndexVec::from_elem(false, &body.local_decls),
 632         };
 633         for (local, val) in cpv.can_const_prop.iter_enumerated_mut() {
 634             // cannot use args at all
 635             // cannot use locals because if x < y { y - x } else { x - y } would
 636             //        lint for x != y
 637             // FIXME(oli-obk): lint variables until they are used in a condition
 638             // FIXME(oli-obk): lint if return value is constant
 639             *val = body.local_kind(local) == LocalKind::Temp;
 640
 641             if !*val {
 642                 trace!("local {:?} can't be propagated because it's not a temporary", local);
 643             }
 644         }
 645         cpv.visit_body(body);
 646         cpv.can_const_prop
 647     }
 648 }
 649
 650 impl<'tcx> Visitor<'tcx> for CanConstProp {
 651     fn visit_local(
 652         &mut self,
 653         &local: &Local,
 654         context: PlaceContext,
 655         _: Location,
 656     ) {
 657         use rustc::mir::visit::PlaceContext::*;
 658         match context {
 659             // Constants must have at most one write
 660             // FIXME(oli-obk): we could be more powerful here, if the multiple writes
 661             // only occur in independent execution paths
 662             MutatingUse(MutatingUseContext::Store) => if self.found_assignment[local] {
 663                 trace!("local {:?} can't be propagated because of multiple assignments", local);
 664                 self.can_const_prop[local] = false;
 665             } else {
 666                 self.found_assignment[local] = true
 667             },
 668             // Reading constants is allowed an arbitrary number of times
 669             NonMutatingUse(NonMutatingUseContext::Copy) |
 670             NonMutatingUse(NonMutatingUseContext::Move) |
 671             NonMutatingUse(NonMutatingUseContext::Inspect) |
 672             NonMutatingUse(NonMutatingUseContext::Projection) |
 673             MutatingUse(MutatingUseContext::Projection) |
 674             NonUse(_) => {},
 675             _ => {
 676                 trace!("local {:?} can't be propagaged because it's used: {:?}", local, context);
 677                 self.can_const_prop[local] = false;
 678             },
 679         }
 680     }
 681 }
 682
 683 impl<'mir, 'tcx> MutVisitor<'tcx> for ConstPropagator<'mir, 'tcx> {
 684     fn visit_constant(
 685         &mut self,
 686         constant: &mut Constant<'tcx>,
 687         location: Location,
 688     ) {
 689         trace!("visit_constant: {:?}", constant);
 690         self.super_constant(constant, location);
 691         self.eval_constant(constant);
 692     }
 693
 694     fn visit_statement(
 695         &mut self,
 696         statement: &mut Statement<'tcx>,
 697         location: Location,
 698     ) {
 699         trace!("visit_statement: {:?}", statement);
 700         if let StatementKind::Assign(ref place, ref mut rval) = statement.kind {
 701             let place_ty: Ty<'tcx> = place
 702                 .ty(&self.local_decls, self.tcx)
 703                 .ty;
 704             if let Ok(place_layout) = self.tcx.layout_of(self.param_env.and(place_ty)) {
 705                 if let Some(value) = self.const_prop(rval, place_layout, statement.source_info) {
 706                     if let Place::Base(PlaceBase::Local(local)) = *place {
 707                         trace!("checking whether {:?} can be stored to {:?}", value, local);
 708                         if self.can_const_prop[local] {
 709                             trace!("storing {:?} to {:?}", value, local);
 710                             assert!(self.get_const(local).is_none());
 711                             self.set_const(local, Some(value));
 712
 713                             if self.should_const_prop() {
 714                                 self.replace_with_const(
 715                                     rval,
 716                                     value,
 717                                     statement.source_info,
 718                                 );
 719                             }
 720                         }
 721                     }
 722                 }
 723             }
 724         }
 725         self.super_statement(statement, location);
 726     }
 727
 728     fn visit_terminator(
 729         &mut self,
 730         terminator: &mut Terminator<'tcx>,
 731         location: Location,
 732     ) {
 733         self.super_terminator(terminator, location);
 734         let source_info = terminator.source_info;
 735         match &mut terminator.kind {
 736             TerminatorKind::Assert { expected, msg, ref mut cond, .. } => {
 737                 if let Some(value) = self.eval_operand(&cond, source_info) {
 738                     trace!("assertion on {:?} should be {:?}", value, expected);
 739                     let expected = ScalarMaybeUndef::from(Scalar::from_bool(*expected));
 740                     let value_const = self.ecx.read_scalar(value).unwrap();
 741                     if expected != value_const {
 742                         // poison all places this operand references so that further code
 743                         // doesn't use the invalid value
 744                         match cond {
 745                             Operand::Move(ref place) | Operand::Copy(ref place) => {
 746                                 let mut place = place;
 747                                 while let Place::Projection(ref proj) = *place {
 748                                     place = &proj.base;
 749                                 }
 750                                 if let Place::Base(PlaceBase::Local(local)) = *place {
 751                                     self.set_const(local, None);
 752                                 }
 753                             },
 754                             Operand::Constant(_) => {}
 755                         }
 756                         let span = terminator.source_info.span;
 757                         let hir_id = self
 758                             .tcx
 759                             .hir()
 760                             .as_local_hir_id(self.source.def_id())
 761                             .expect("some part of a failing const eval must be local");
 762                         use rustc::mir::interpret::InterpError::*;
 763                         let msg = match msg {
 764                             Overflow(_) |
 765                             OverflowNeg |
 766                             DivisionByZero |
 767                             RemainderByZero => msg.description().to_owned(),
 768                             BoundsCheck { ref len, ref index } => {
 769                                 let len = self
 770                                     .eval_operand(len, source_info)
 771                                     .expect("len must be const");
 772                                 let len = match self.ecx.read_scalar(len) {
 773                                     Ok(ScalarMaybeUndef::Scalar(Scalar::Raw {
 774                                         data, ..
 775                                     })) => data,
 776                                     other => bug!("const len not primitive: {:?}", other),
 777                                 };
 778                                 let index = self
 779                                     .eval_operand(index, source_info)
 780                                     .expect("index must be const");
 781                                 let index = match self.ecx.read_scalar(index) {
 782                                     Ok(ScalarMaybeUndef::Scalar(Scalar::Raw {
 783                                         data, ..
 784                                     })) => data,
 785                                     other => bug!("const index not primitive: {:?}", other),
 786                                 };
 787                                 format!(
 788                                     "index out of bounds: \
 789                                     the len is {} but the index is {}",
 790                                     len,
 791                                     index,
 792                                 )
 793                             },
 794                             // Need proper const propagator for these
 795                             _ => return,
 796                         };
 797                         self.tcx.lint_hir(
 798                             ::rustc::lint::builtin::CONST_ERR,
 799                             hir_id,
 800                             span,
 801                             &msg,
 802                         );
 803                     } else {
 804                         if self.should_const_prop() {
 805                             if let ScalarMaybeUndef::Scalar(scalar) = value_const {
 806                                 *cond = self.operand_from_scalar(
 807                                     scalar,
 808                                     self.tcx.types.bool,
 809                                     source_info.span,
 810                                 );
 811                             }
 812                         }
 813                     }
 814                 }
 815             },
 816             TerminatorKind::SwitchInt { ref mut discr, switch_ty, .. } => {
 817                 if self.should_const_prop() {
 818                     if let Some(value) = self.eval_operand(&discr, source_info) {
 819                         if let ScalarMaybeUndef::Scalar(scalar) =
 820                                 self.ecx.read_scalar(value).unwrap() {
 821                             *discr = self.operand_from_scalar(scalar, switch_ty, source_info.span);
 822                         }
 823                     }
 824                 }
 825             },
 826             //none of these have Operands to const-propagate
 827             TerminatorKind::Goto { .. } |
 828             TerminatorKind::Resume |
 829             TerminatorKind::Abort |
 830             TerminatorKind::Return |
 831             TerminatorKind::Unreachable |
 832             TerminatorKind::Drop { .. } |
 833             TerminatorKind::DropAndReplace { .. } |
 834             TerminatorKind::Yield { .. } |
 835             TerminatorKind::GeneratorDrop |
 836             TerminatorKind::FalseEdges { .. } |
 837             TerminatorKind::FalseUnwind { .. } => { }
 838             //FIXME(wesleywiser) Call does have Operands that could be const-propagated
 839             TerminatorKind::Call { .. } => { }
 840         }
 841     }
 842 }