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