1 //! Propagates constants for early reporting of statically known
4 use rustc::hir::def::Def;
6 Constant, Location, Place, PlaceBase, Mir, Operand, Rvalue, Local,
7 NullOp, UnOp, StatementKind, Statement, LocalKind, Static, StaticKind,
8 TerminatorKind, Terminator, ClearCrossCrate, SourceInfo, BinOp, ProjectionElem,
9 SourceScope, SourceScopeLocalData, LocalDecl, Promoted,
11 use rustc::mir::visit::{Visitor, PlaceContext, MutatingUseContext, NonMutatingUseContext};
12 use rustc::mir::interpret::{InterpError, Scalar, GlobalId, EvalResult};
13 use rustc::ty::{self, Instance, ParamEnv, Ty, TyCtxt};
14 use syntax::source_map::DUMMY_SP;
15 use rustc::ty::subst::InternalSubsts;
16 use rustc_data_structures::indexed_vec::IndexVec;
17 use rustc::ty::layout::{
18 LayoutOf, TyLayout, LayoutError,
19 HasTyCtxt, TargetDataLayout, HasDataLayout,
22 use crate::interpret::{InterpretCx, ScalarMaybeUndef, Immediate, OpTy, ImmTy, MemoryKind};
23 use crate::const_eval::{
24 CompileTimeInterpreter, error_to_const_error, eval_promoted, mk_eval_cx,
26 use crate::transform::{MirPass, MirSource};
30 impl MirPass for ConstProp {
31 fn run_pass<'a, 'tcx>(&self,
32 tcx: TyCtxt<'a, 'tcx, 'tcx>,
33 source: MirSource<'tcx>,
34 mir: &mut Mir<'tcx>) {
35 // will be evaluated by miri and produce its errors there
36 if source.promoted.is_some() {
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");
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.describe_def(source.def_id()) {
46 Some(Def::AssociatedConst(_)) => true,
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());
57 trace!("ConstProp starting for {:?}", source.def_id());
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(mir, tcx, source);
64 optimization_finder.visit_mir(mir);
66 // put back the data we stole from `mir`
68 &mut mir.source_scope_local_data,
69 optimization_finder.source_scope_local_data
73 optimization_finder.promoted
76 trace!("ConstProp done for {:?}", source.def_id());
80 type Const<'tcx> = OpTy<'tcx>;
82 /// Finds optimization opportunities on the MIR.
83 struct ConstPropagator<'a, 'mir, 'tcx:'a+'mir> {
84 ecx: InterpretCx<'a, 'mir, 'tcx, CompileTimeInterpreter<'a, 'mir, 'tcx>>,
85 tcx: TyCtxt<'a, 'tcx, '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, Mir<'tcx>>,
95 impl<'a, 'b, 'tcx> LayoutOf for ConstPropagator<'a, 'b, 'tcx> {
97 type TyLayout = Result<TyLayout<'tcx>, LayoutError<'tcx>>;
99 fn layout_of(&self, ty: Ty<'tcx>) -> Self::TyLayout {
100 self.tcx.layout_of(self.param_env.and(ty))
104 impl<'a, 'b, 'tcx> HasDataLayout for ConstPropagator<'a, 'b, 'tcx> {
106 fn data_layout(&self) -> &TargetDataLayout {
107 &self.tcx.data_layout
111 impl<'a, 'b, 'tcx> HasTyCtxt<'tcx> for ConstPropagator<'a, 'b, 'tcx> {
113 fn tcx<'c>(&'c self) -> TyCtxt<'c, 'tcx, 'tcx> {
118 impl<'a, 'mir, 'tcx> ConstPropagator<'a, 'mir, 'tcx> {
121 tcx: TyCtxt<'a, 'tcx, 'tcx>,
122 source: MirSource<'tcx>,
123 ) -> ConstPropagator<'a, '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(mir);
127 let source_scope_local_data = std::mem::replace(
128 &mut mir.source_scope_local_data,
129 ClearCrossCrate::Clear
131 let promoted = std::mem::replace(
142 places: IndexVec::from_elem(None, &mir.local_decls),
143 source_scope_local_data,
144 //FIXME(wesleywiser) we can't steal this because `Visitor::super_visit_mir()` needs it
145 local_decls: mir.local_decls.clone(),
152 source_info: SourceInfo,
156 F: FnOnce(&mut Self) -> EvalResult<'tcx, T>,
158 self.ecx.tcx.span = source_info.span;
159 let lint_root = match self.source_scope_local_data {
160 ClearCrossCrate::Set(ref ivs) => {
161 //FIXME(#51314): remove this check
162 if source_info.scope.index() >= ivs.len() {
165 ivs[source_info.scope].lint_root
167 ClearCrossCrate::Clear => return None,
169 let r = match f(self) {
170 Ok(val) => Some(val),
172 let diagnostic = error_to_const_error(&self.ecx, error);
173 use rustc::mir::interpret::InterpError::*;
174 match diagnostic.error {
175 // don't report these, they make no sense in a const prop context
178 // at runtime these transformations might make sense
179 // FIXME: figure out the rules and start linting
180 | FunctionAbiMismatch(..)
181 | FunctionArgMismatch(..)
182 | FunctionRetMismatch(..)
183 | FunctionArgCountMismatch
184 // fine at runtime, might be a register address or sth
189 // don't report const evaluator limits
190 | StackFrameLimitReached
195 | InvalidMemoryAccess
196 | DanglingPointerDeref
198 | InvalidFunctionPointer
200 | InvalidDiscriminant(..)
201 | PointerOutOfBounds { .. }
202 | InvalidNullPointerUsage
203 | ValidationFailure(..)
208 | DerefFunctionPointer
213 | AlignmentCheckFailed{..}
214 | CalledClosureAsFunction
215 | VtableForArgumentlessMethod
216 | ModifiedConstantMemory
219 // FIXME: should probably be removed and turned into a bug! call
220 | TypeNotPrimitive(_)
221 | ReallocatedWrongMemoryKind(_, _)
222 | DeallocatedWrongMemoryKind(_, _)
223 | ReallocateNonBasePtr
224 | DeallocateNonBasePtr
225 | IncorrectAllocationInformation(..)
226 | UnterminatedCString(_)
228 | HeapAllocNonPowerOfTwoAlignment(_)
230 | ReadFromReturnPointer
231 | GeneratorResumedAfterReturn
232 | GeneratorResumedAfterPanic
236 // FIXME: report UB here
242 => bug!("these should not be in rustc, but in miri's machine errors"),
245 | UnimplementedTraitSelection
248 // these are just noise
263 diagnostic.report_as_lint(
265 "this expression will panic at runtime",
274 self.ecx.tcx.span = DUMMY_SP;
281 ) -> Option<Const<'tcx>> {
282 self.ecx.tcx.span = c.span;
283 match self.ecx.eval_const_to_op(*c.literal, None) {
288 let err = error_to_const_error(&self.ecx, error);
289 err.report_as_error(self.ecx.tcx, "erroneous constant used");
295 fn eval_place(&mut self, place: &Place<'tcx>, source_info: SourceInfo) -> Option<Const<'tcx>> {
297 Place::Base(PlaceBase::Local(loc)) => self.places[loc].clone(),
298 Place::Projection(ref proj) => match proj.elem {
299 ProjectionElem::Field(field, _) => {
300 trace!("field proj on {:?}", proj.base);
301 let base = self.eval_place(&proj.base, source_info)?;
302 let res = self.use_ecx(source_info, |this| {
303 this.ecx.operand_field(base, field.index() as u64)
307 // We could get more projections by using e.g., `operand_projection`,
308 // but we do not even have the stack frame set up properly so
309 // an `Index` projection would throw us off-track.
313 PlaceBase::Static(box Static {kind: StaticKind::Promoted(promoted), ..})
315 let generics = self.tcx.generics_of(self.source.def_id());
316 if generics.requires_monomorphization(self.tcx) {
317 // FIXME: can't handle code with generics
320 let substs = InternalSubsts::identity_for_item(self.tcx, self.source.def_id());
321 let instance = Instance::new(self.source.def_id(), substs);
324 promoted: Some(promoted),
326 // cannot use `const_eval` here, because that would require having the MIR
327 // for the current function available, but we're producing said MIR right now
328 let res = self.use_ecx(source_info, |this| {
329 let mir = &this.promoted[promoted];
330 eval_promoted(this.tcx, cid, mir, this.param_env)
332 trace!("evaluated promoted {:?} to {:?}", promoted, res);
339 fn eval_operand(&mut self, op: &Operand<'tcx>, source_info: SourceInfo) -> Option<Const<'tcx>> {
341 Operand::Constant(ref c) => self.eval_constant(c),
342 | Operand::Move(ref place)
343 | Operand::Copy(ref place) => self.eval_place(place, source_info),
349 rvalue: &Rvalue<'tcx>,
350 place_layout: TyLayout<'tcx>,
351 source_info: SourceInfo,
352 ) -> Option<Const<'tcx>> {
353 let span = source_info.span;
355 Rvalue::Use(ref op) => {
356 self.eval_operand(op, source_info)
360 Rvalue::Aggregate(..) |
361 Rvalue::NullaryOp(NullOp::Box, _) |
362 Rvalue::Discriminant(..) => None,
364 Rvalue::Cast(kind, ref operand, _) => {
365 let op = self.eval_operand(operand, source_info)?;
366 self.use_ecx(source_info, |this| {
367 let dest = this.ecx.allocate(place_layout, MemoryKind::Stack);
368 this.ecx.cast(op, kind, dest.into())?;
373 // FIXME(oli-obk): evaluate static/constant slice lengths
374 Rvalue::Len(_) => None,
375 Rvalue::NullaryOp(NullOp::SizeOf, ty) => {
376 type_size_of(self.tcx, self.param_env, ty).and_then(|n| Some(
378 imm: Immediate::Scalar(
381 size: self.tcx.data_layout.pointer_size.bytes() as u8,
384 layout: self.tcx.layout_of(self.param_env.and(self.tcx.types.usize)).ok()?,
388 Rvalue::UnaryOp(op, ref arg) => {
389 let def_id = if self.tcx.is_closure(self.source.def_id()) {
390 self.tcx.closure_base_def_id(self.source.def_id())
394 let generics = self.tcx.generics_of(def_id);
395 if generics.requires_monomorphization(self.tcx) {
396 // FIXME: can't handle code with generics
400 let arg = self.eval_operand(arg, source_info)?;
401 let val = self.use_ecx(source_info, |this| {
402 let prim = this.ecx.read_immediate(arg)?;
405 // Need to do overflow check here: For actual CTFE, MIR
406 // generation emits code that does this before calling the op.
407 if prim.to_bits()? == (1 << (prim.layout.size.bits() - 1)) {
408 return err!(OverflowNeg);
415 // Now run the actual operation.
416 this.ecx.unary_op(op, prim)
419 imm: Immediate::Scalar(val.into()),
420 layout: place_layout,
424 Rvalue::CheckedBinaryOp(op, ref left, ref right) |
425 Rvalue::BinaryOp(op, ref left, ref right) => {
426 trace!("rvalue binop {:?} for {:?} and {:?}", op, left, right);
427 let right = self.eval_operand(right, source_info)?;
428 let def_id = if self.tcx.is_closure(self.source.def_id()) {
429 self.tcx.closure_base_def_id(self.source.def_id())
433 let generics = self.tcx.generics_of(def_id);
434 if generics.requires_monomorphization(self.tcx) {
435 // FIXME: can't handle code with generics
439 let r = self.use_ecx(source_info, |this| {
440 this.ecx.read_immediate(right)
442 if op == BinOp::Shr || op == BinOp::Shl {
443 let left_ty = left.ty(&self.local_decls, self.tcx);
446 .layout_of(self.param_env.and(left_ty))
450 let right_size = right.layout.size;
451 let r_bits = r.to_scalar().and_then(|r| r.to_bits(right_size));
452 if r_bits.ok().map_or(false, |b| b >= left_bits as u128) {
453 let source_scope_local_data = match self.source_scope_local_data {
454 ClearCrossCrate::Set(ref data) => data,
455 ClearCrossCrate::Clear => return None,
457 let dir = if op == BinOp::Shr {
462 let hir_id = source_scope_local_data[source_info.scope].lint_root;
464 ::rustc::lint::builtin::EXCEEDING_BITSHIFTS,
467 &format!("attempt to shift {} with overflow", dir));
471 let left = self.eval_operand(left, source_info)?;
472 let l = self.use_ecx(source_info, |this| {
473 this.ecx.read_immediate(left)
475 trace!("const evaluating {:?} for {:?} and {:?}", op, left, right);
476 let (val, overflow) = self.use_ecx(source_info, |this| {
477 this.ecx.binary_op(op, l, r)
479 let val = if let Rvalue::CheckedBinaryOp(..) = *rvalue {
480 Immediate::ScalarPair(
482 Scalar::from_bool(overflow).into(),
486 let err = InterpError::Overflow(op).into();
487 let _: Option<()> = self.use_ecx(source_info, |_| Err(err));
490 Immediate::Scalar(val.into())
494 layout: place_layout,
502 fn type_size_of<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
503 param_env: ty::ParamEnv<'tcx>,
504 ty: Ty<'tcx>) -> Option<u64> {
505 tcx.layout_of(param_env.and(ty)).ok().map(|layout| layout.size.bytes())
508 struct CanConstProp {
509 can_const_prop: IndexVec<Local, bool>,
510 // false at the beginning, once set, there are not allowed to be any more assignments
511 found_assignment: IndexVec<Local, bool>,
515 /// returns true if `local` can be propagated
516 fn check(mir: &Mir<'_>) -> IndexVec<Local, bool> {
517 let mut cpv = CanConstProp {
518 can_const_prop: IndexVec::from_elem(true, &mir.local_decls),
519 found_assignment: IndexVec::from_elem(false, &mir.local_decls),
521 for (local, val) in cpv.can_const_prop.iter_enumerated_mut() {
522 // cannot use args at all
523 // cannot use locals because if x < y { y - x } else { x - y } would
525 // FIXME(oli-obk): lint variables until they are used in a condition
526 // FIXME(oli-obk): lint if return value is constant
527 *val = mir.local_kind(local) == LocalKind::Temp;
534 impl<'tcx> Visitor<'tcx> for CanConstProp {
538 context: PlaceContext,
541 use rustc::mir::visit::PlaceContext::*;
543 // Constants must have at most one write
544 // FIXME(oli-obk): we could be more powerful here, if the multiple writes
545 // only occur in independent execution paths
546 MutatingUse(MutatingUseContext::Store) => if self.found_assignment[local] {
547 self.can_const_prop[local] = false;
549 self.found_assignment[local] = true
551 // Reading constants is allowed an arbitrary number of times
552 NonMutatingUse(NonMutatingUseContext::Copy) |
553 NonMutatingUse(NonMutatingUseContext::Move) |
554 NonMutatingUse(NonMutatingUseContext::Inspect) |
555 NonMutatingUse(NonMutatingUseContext::Projection) |
556 MutatingUse(MutatingUseContext::Projection) |
558 _ => self.can_const_prop[local] = false,
563 impl<'b, 'a, 'tcx> Visitor<'tcx> for ConstPropagator<'b, 'a, 'tcx> {
566 constant: &Constant<'tcx>,
569 trace!("visit_constant: {:?}", constant);
570 self.super_constant(constant, location);
571 self.eval_constant(constant);
576 statement: &Statement<'tcx>,
579 trace!("visit_statement: {:?}", statement);
580 if let StatementKind::Assign(ref place, ref rval) = statement.kind {
581 let place_ty: Ty<'tcx> = place
582 .ty(&self.local_decls, self.tcx)
584 if let Ok(place_layout) = self.tcx.layout_of(self.param_env.and(place_ty)) {
585 if let Some(value) = self.const_prop(rval, place_layout, statement.source_info) {
586 if let Place::Base(PlaceBase::Local(local)) = *place {
587 trace!("checking whether {:?} can be stored to {:?}", value, local);
588 if self.can_const_prop[local] {
589 trace!("storing {:?} to {:?}", value, local);
590 assert!(self.places[local].is_none());
591 self.places[local] = Some(value);
597 self.super_statement(statement, location);
602 terminator: &Terminator<'tcx>,
605 self.super_terminator(terminator, location);
606 let source_info = terminator.source_info;;
607 if let TerminatorKind::Assert { expected, msg, cond, .. } = &terminator.kind {
608 if let Some(value) = self.eval_operand(&cond, source_info) {
609 trace!("assertion on {:?} should be {:?}", value, expected);
610 let expected = ScalarMaybeUndef::from(Scalar::from_bool(*expected));
611 if expected != self.ecx.read_scalar(value).unwrap() {
612 // poison all places this operand references so that further code
613 // doesn't use the invalid value
615 Operand::Move(ref place) | Operand::Copy(ref place) => {
616 let mut place = place;
617 while let Place::Projection(ref proj) = *place {
620 if let Place::Base(PlaceBase::Local(local)) = *place {
621 self.places[local] = None;
624 Operand::Constant(_) => {}
626 let span = terminator.source_info.span;
630 .as_local_hir_id(self.source.def_id())
631 .expect("some part of a failing const eval must be local");
632 use rustc::mir::interpret::InterpError::*;
633 let msg = match msg {
637 RemainderByZero => msg.description().to_owned(),
638 BoundsCheck { ref len, ref index } => {
640 .eval_operand(len, source_info)
641 .expect("len must be const");
642 let len = match self.ecx.read_scalar(len) {
643 Ok(ScalarMaybeUndef::Scalar(Scalar::Bits {
646 other => bug!("const len not primitive: {:?}", other),
649 .eval_operand(index, source_info)
650 .expect("index must be const");
651 let index = match self.ecx.read_scalar(index) {
652 Ok(ScalarMaybeUndef::Scalar(Scalar::Bits {
655 other => bug!("const index not primitive: {:?}", other),
658 "index out of bounds: \
659 the len is {} but the index is {}",
664 // Need proper const propagator for these
668 ::rustc::lint::builtin::CONST_ERR,