1 //! Propagates constants for early reporting of statically known
6 use rustc::hir::def::DefKind;
8 AggregateKind, Constant, Location, Place, PlaceBase, Body, Operand, Rvalue,
9 Local, NullOp, UnOp, StatementKind, Statement, LocalKind, Static, StaticKind,
10 TerminatorKind, Terminator, ClearCrossCrate, SourceInfo, BinOp, ProjectionElem,
11 SourceScope, SourceScopeLocalData, LocalDecl, Promoted,
13 use rustc::mir::visit::{
14 Visitor, PlaceContext, MutatingUseContext, MutVisitor, NonMutatingUseContext,
16 use rustc::mir::interpret::{InterpError, Scalar, GlobalId, InterpResult};
17 use rustc::ty::{self, Instance, ParamEnv, Ty, TyCtxt};
18 use syntax_pos::{Span, DUMMY_SP};
19 use rustc::ty::subst::InternalSubsts;
20 use rustc_data_structures::indexed_vec::IndexVec;
21 use rustc::ty::layout::{
22 LayoutOf, TyLayout, LayoutError, HasTyCtxt, TargetDataLayout, HasDataLayout, Size,
25 use crate::interpret::{
26 self, InterpretCx, ScalarMaybeUndef, Immediate, OpTy,
27 ImmTy, MemoryKind, StackPopCleanup, LocalValue, LocalState,
29 use crate::const_eval::{
30 CompileTimeInterpreter, error_to_const_error, eval_promoted, mk_eval_cx,
32 use crate::transform::{MirPass, MirSource};
36 impl MirPass for ConstProp {
37 fn run_pass<'tcx>(&self, tcx: TyCtxt<'tcx>, source: MirSource<'tcx>, body: &mut Body<'tcx>) {
38 // will be evaluated by miri and produce its errors there
39 if source.promoted.is_some() {
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");
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,
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());
60 trace!("ConstProp starting for {:?}", source.def_id());
62 // steal some data we need from `body`
63 let source_scope_local_data = std::mem::replace(
64 &mut body.source_scope_local_data,
65 ClearCrossCrate::Clear
67 let promoted = std::mem::replace(
74 body.basic_blocks().clone(),
76 ClearCrossCrate::Clear,
79 body.local_decls.clone(),
83 tcx.def_span(source.def_id()),
87 // FIXME(oli-obk, eddyb) Optimize locals (or even local paths) to hold
88 // constants, instead of just checking for const-folding succeeding.
89 // That would require an uniform one-def no-mutation analysis
90 // and RPO (or recursing when needing the value of a local).
91 let mut optimization_finder = ConstPropagator::new(
94 source_scope_local_data,
99 optimization_finder.visit_body(body);
101 // put back the data we stole from `mir`
102 let (source_scope_local_data, promoted) = optimization_finder.release_stolen_data();
104 &mut body.source_scope_local_data,
105 source_scope_local_data
112 trace!("ConstProp done for {:?}", source.def_id());
116 type Const<'tcx> = OpTy<'tcx>;
118 /// Finds optimization opportunities on the MIR.
119 struct ConstPropagator<'mir, 'tcx> {
120 ecx: InterpretCx<'mir, 'tcx, CompileTimeInterpreter<'mir, 'tcx>>,
122 source: MirSource<'tcx>,
123 can_const_prop: IndexVec<Local, bool>,
124 param_env: ParamEnv<'tcx>,
125 source_scope_local_data: ClearCrossCrate<IndexVec<SourceScope, SourceScopeLocalData>>,
126 local_decls: IndexVec<Local, LocalDecl<'tcx>>,
127 promoted: IndexVec<Promoted, Body<'tcx>>,
130 impl<'mir, 'tcx> LayoutOf for ConstPropagator<'mir, 'tcx> {
132 type TyLayout = Result<TyLayout<'tcx>, LayoutError<'tcx>>;
134 fn layout_of(&self, ty: Ty<'tcx>) -> Self::TyLayout {
135 self.tcx.layout_of(self.param_env.and(ty))
139 impl<'mir, 'tcx> HasDataLayout for ConstPropagator<'mir, 'tcx> {
141 fn data_layout(&self) -> &TargetDataLayout {
142 &self.tcx.data_layout
146 impl<'mir, 'tcx> HasTyCtxt<'tcx> for ConstPropagator<'mir, 'tcx> {
148 fn tcx(&self) -> TyCtxt<'tcx> {
153 impl<'mir, 'tcx> ConstPropagator<'mir, 'tcx> {
156 dummy_body: &'mir Body<'tcx>,
157 source_scope_local_data: ClearCrossCrate<IndexVec<SourceScope, SourceScopeLocalData>>,
158 promoted: IndexVec<Promoted, Body<'tcx>>,
160 source: MirSource<'tcx>,
161 ) -> ConstPropagator<'mir, 'tcx> {
162 let def_id = source.def_id();
163 let param_env = tcx.param_env(def_id);
164 let span = tcx.def_span(def_id);
165 let mut ecx = mk_eval_cx(tcx, span, param_env);
166 let can_const_prop = CanConstProp::check(body);
168 ecx.push_stack_frame(
169 Instance::new(def_id, &InternalSubsts::identity_for_item(tcx, def_id)),
173 StackPopCleanup::None {
176 ).expect("failed to push initial stack frame");
184 source_scope_local_data,
185 //FIXME(wesleywiser) we can't steal this because `Visitor::super_visit_body()` needs it
186 local_decls: body.local_decls.clone(),
191 fn release_stolen_data(self) ->
192 (ClearCrossCrate<IndexVec<SourceScope, SourceScopeLocalData>>,
193 IndexVec<Promoted, Body<'tcx>>)
195 (self.source_scope_local_data, self.promoted)
198 fn get_const(&self, local: Local) -> Option<Const<'tcx>> {
199 let l = &self.ecx.frame().locals[local];
200 if l.value == LocalValue::Uninitialized || l.value == LocalValue::Dead {
204 self.ecx.access_local(self.ecx.frame(), local, None).ok()
207 fn set_const(&mut self, local: Local, c: Option<Const<'tcx>>) {
208 self.ecx.frame_mut().locals[local] =
210 Some(op_ty) => LocalState {
211 value: LocalValue::Live(*op_ty),
212 layout: Cell::new(Some(op_ty.layout)),
214 None => LocalState { value: LocalValue::Uninitialized, layout: Cell::new(None) },
220 source_info: SourceInfo,
224 F: FnOnce(&mut Self) -> InterpResult<'tcx, T>,
226 self.ecx.tcx.span = source_info.span;
227 let lint_root = match self.source_scope_local_data {
228 ClearCrossCrate::Set(ref ivs) => {
229 //FIXME(#51314): remove this check
230 if source_info.scope.index() >= ivs.len() {
233 ivs[source_info.scope].lint_root
235 ClearCrossCrate::Clear => return None,
237 let r = match f(self) {
238 Ok(val) => Some(val),
240 let diagnostic = error_to_const_error(&self.ecx, error);
241 use rustc::mir::interpret::InterpError::*;
242 match diagnostic.error {
243 // don't report these, they make no sense in a const prop context
246 // at runtime these transformations might make sense
247 // FIXME: figure out the rules and start linting
248 | FunctionAbiMismatch(..)
249 | FunctionArgMismatch(..)
250 | FunctionRetMismatch(..)
251 | FunctionArgCountMismatch
252 // fine at runtime, might be a register address or sth
257 // don't report const evaluator limits
258 | StackFrameLimitReached
263 | InvalidMemoryAccess
264 | DanglingPointerDeref
266 | InvalidFunctionPointer
268 | InvalidDiscriminant(..)
269 | PointerOutOfBounds { .. }
270 | InvalidNullPointerUsage
271 | ValidationFailure(..)
276 | DerefFunctionPointer
281 | AlignmentCheckFailed{..}
282 | CalledClosureAsFunction
283 | VtableForArgumentlessMethod
284 | ModifiedConstantMemory
287 // FIXME: should probably be removed and turned into a bug! call
288 | TypeNotPrimitive(_)
289 | ReallocatedWrongMemoryKind(_, _)
290 | DeallocatedWrongMemoryKind(_, _)
291 | ReallocateNonBasePtr
292 | DeallocateNonBasePtr
293 | IncorrectAllocationInformation(..)
294 | UnterminatedCString(_)
296 | HeapAllocNonPowerOfTwoAlignment(_)
298 | ReadFromReturnPointer
299 | GeneratorResumedAfterReturn
300 | GeneratorResumedAfterPanic
304 // FIXME: report UB here
310 => bug!("these should not be in rustc, but in miri's machine errors"),
313 | UnimplementedTraitSelection
316 // these are just noise
331 diagnostic.report_as_lint(
333 "this expression will panic at runtime",
342 self.ecx.tcx.span = DUMMY_SP;
349 ) -> Option<Const<'tcx>> {
350 self.ecx.tcx.span = c.span;
351 match self.ecx.eval_const_to_op(c.literal, None) {
356 let err = error_to_const_error(&self.ecx, error);
357 err.report_as_error(self.ecx.tcx, "erroneous constant used");
363 fn eval_place(&mut self, place: &Place<'tcx>, source_info: SourceInfo) -> Option<Const<'tcx>> {
364 trace!("eval_place(place={:?})", place);
365 place.iterate(|place_base, place_projection| {
366 let mut eval = match place_base {
367 PlaceBase::Local(loc) => self.get_const(*loc).clone()?,
368 PlaceBase::Static(box Static {kind: StaticKind::Promoted(promoted), ..}) => {
369 let generics = self.tcx.generics_of(self.source.def_id());
370 if generics.requires_monomorphization(self.tcx) {
371 // FIXME: can't handle code with generics
374 let substs = InternalSubsts::identity_for_item(self.tcx, self.source.def_id());
375 let instance = Instance::new(self.source.def_id(), substs);
378 promoted: Some(*promoted),
380 // cannot use `const_eval` here, because that would require having the MIR
381 // for the current function available, but we're producing said MIR right now
382 let res = self.use_ecx(source_info, |this| {
383 let body = &this.promoted[*promoted];
384 eval_promoted(this.tcx, cid, body, this.param_env)
386 trace!("evaluated promoted {:?} to {:?}", promoted, res);
392 for proj in place_projection {
394 ProjectionElem::Field(field, _) => {
395 trace!("field proj on {:?}", proj.base);
396 eval = self.use_ecx(source_info, |this| {
397 this.ecx.operand_field(eval, field.index() as u64)
400 ProjectionElem::Deref => {
401 trace!("processing deref");
402 eval = self.use_ecx(source_info, |this| {
403 this.ecx.deref_operand(eval)
406 // We could get more projections by using e.g., `operand_projection`,
407 // but we do not even have the stack frame set up properly so
408 // an `Index` projection would throw us off-track.
417 fn eval_operand(&mut self, op: &Operand<'tcx>, source_info: SourceInfo) -> Option<Const<'tcx>> {
419 Operand::Constant(ref c) => self.eval_constant(c),
420 | Operand::Move(ref place)
421 | Operand::Copy(ref place) => self.eval_place(place, source_info),
427 rvalue: &Rvalue<'tcx>,
428 place_layout: TyLayout<'tcx>,
429 source_info: SourceInfo,
430 ) -> Option<Const<'tcx>> {
431 let span = source_info.span;
433 Rvalue::Use(ref op) => {
434 self.eval_operand(op, source_info)
436 Rvalue::Ref(_, _, ref place) => {
437 let src = self.eval_place(place, source_info)?;
438 let mplace = src.try_as_mplace().ok()?;
439 Some(ImmTy::from_scalar(mplace.ptr.into(), place_layout).into())
442 Rvalue::Aggregate(..) |
443 Rvalue::NullaryOp(NullOp::Box, _) |
444 Rvalue::Discriminant(..) => None,
446 Rvalue::Cast(kind, ref operand, _) => {
447 let op = self.eval_operand(operand, source_info)?;
448 self.use_ecx(source_info, |this| {
449 let dest = this.ecx.allocate(place_layout, MemoryKind::Stack);
450 this.ecx.cast(op, kind, dest.into())?;
454 Rvalue::Len(ref place) => {
455 let place = self.eval_place(&place, source_info)?;
456 let mplace = place.try_as_mplace().ok()?;
458 if let ty::Slice(_) = mplace.layout.ty.sty {
459 let len = mplace.meta.unwrap().to_usize(&self.ecx).unwrap();
462 imm: Immediate::Scalar(
466 self.tcx.sess.target.usize_ty.bit_width().unwrap() as u64
470 layout: self.tcx.layout_of(self.param_env.and(self.tcx.types.usize)).ok()?,
473 trace!("not slice: {:?}", mplace.layout.ty.sty);
477 Rvalue::NullaryOp(NullOp::SizeOf, ty) => {
478 type_size_of(self.tcx, self.param_env, ty).and_then(|n| Some(
480 imm: Immediate::Scalar(
481 Scalar::from_uint(n, self.tcx.data_layout.pointer_size).into()
483 layout: self.tcx.layout_of(self.param_env.and(self.tcx.types.usize)).ok()?,
487 Rvalue::UnaryOp(op, ref arg) => {
488 let def_id = if self.tcx.is_closure(self.source.def_id()) {
489 self.tcx.closure_base_def_id(self.source.def_id())
493 let generics = self.tcx.generics_of(def_id);
494 if generics.requires_monomorphization(self.tcx) {
495 // FIXME: can't handle code with generics
499 let arg = self.eval_operand(arg, source_info)?;
500 let val = self.use_ecx(source_info, |this| {
501 let prim = this.ecx.read_immediate(arg)?;
504 // Need to do overflow check here: For actual CTFE, MIR
505 // generation emits code that does this before calling the op.
506 if prim.to_bits()? == (1 << (prim.layout.size.bits() - 1)) {
507 return err!(OverflowNeg);
514 // Now run the actual operation.
515 this.ecx.unary_op(op, prim)
518 imm: Immediate::Scalar(val.into()),
519 layout: place_layout,
523 Rvalue::CheckedBinaryOp(op, ref left, ref right) |
524 Rvalue::BinaryOp(op, ref left, ref right) => {
525 trace!("rvalue binop {:?} for {:?} and {:?}", op, left, right);
526 let right = self.eval_operand(right, source_info)?;
527 let def_id = if self.tcx.is_closure(self.source.def_id()) {
528 self.tcx.closure_base_def_id(self.source.def_id())
532 let generics = self.tcx.generics_of(def_id);
533 if generics.requires_monomorphization(self.tcx) {
534 // FIXME: can't handle code with generics
538 let r = self.use_ecx(source_info, |this| {
539 this.ecx.read_immediate(right)
541 if op == BinOp::Shr || op == BinOp::Shl {
542 let left_ty = left.ty(&self.local_decls, self.tcx);
545 .layout_of(self.param_env.and(left_ty))
549 let right_size = right.layout.size;
550 let r_bits = r.to_scalar().and_then(|r| r.to_bits(right_size));
551 if r_bits.ok().map_or(false, |b| b >= left_bits as u128) {
552 let source_scope_local_data = match self.source_scope_local_data {
553 ClearCrossCrate::Set(ref data) => data,
554 ClearCrossCrate::Clear => return None,
556 let dir = if op == BinOp::Shr {
561 let hir_id = source_scope_local_data[source_info.scope].lint_root;
563 ::rustc::lint::builtin::EXCEEDING_BITSHIFTS,
566 &format!("attempt to shift {} with overflow", dir));
570 let left = self.eval_operand(left, source_info)?;
571 let l = self.use_ecx(source_info, |this| {
572 this.ecx.read_immediate(left)
574 trace!("const evaluating {:?} for {:?} and {:?}", op, left, right);
575 let (val, overflow) = self.use_ecx(source_info, |this| {
576 this.ecx.binary_op(op, l, r)
578 let val = if let Rvalue::CheckedBinaryOp(..) = *rvalue {
579 Immediate::ScalarPair(
581 Scalar::from_bool(overflow).into(),
585 let err = InterpError::Overflow(op).into();
586 let _: Option<()> = self.use_ecx(source_info, |_| Err(err));
589 Immediate::Scalar(val.into())
593 layout: place_layout,
600 fn operand_from_scalar(&self, scalar: Scalar, ty: Ty<'tcx>, span: Span) -> Operand<'tcx> {
601 Operand::Constant(Box::new(
606 literal: self.tcx.mk_const(*ty::Const::from_scalar(
615 fn replace_with_const(
617 rval: &mut Rvalue<'tcx>,
619 source_info: SourceInfo,
621 trace!("attepting to replace {:?} with {:?}", rval, value);
622 if let Err(e) = self.ecx.validate_operand(
625 // FIXME: is ref tracking too expensive?
626 Some(&mut interpret::RefTracking::empty()),
628 trace!("validation error, attempt failed: {:?}", e);
632 // FIXME> figure out what tho do when try_read_immediate fails
633 let imm = self.use_ecx(source_info, |this| {
634 this.ecx.try_read_immediate(value)
637 if let Some(Ok(imm)) = imm {
639 interpret::Immediate::Scalar(ScalarMaybeUndef::Scalar(scalar)) => {
641 self.operand_from_scalar(scalar, value.layout.ty, source_info.span));
643 Immediate::ScalarPair(
644 ScalarMaybeUndef::Scalar(one),
645 ScalarMaybeUndef::Scalar(two)
647 let ty = &value.layout.ty.sty;
648 if let ty::Tuple(substs) = ty {
649 *rval = Rvalue::Aggregate(
650 Box::new(AggregateKind::Tuple),
652 self.operand_from_scalar(
653 one, substs[0].expect_ty(), source_info.span
655 self.operand_from_scalar(
656 two, substs[1].expect_ty(), source_info.span
667 fn should_const_prop(&self) -> bool {
668 self.tcx.sess.opts.debugging_opts.mir_opt_level >= 2
672 fn type_size_of<'tcx>(
674 param_env: ty::ParamEnv<'tcx>,
677 tcx.layout_of(param_env.and(ty)).ok().map(|layout| layout.size.bytes())
680 struct CanConstProp {
681 can_const_prop: IndexVec<Local, bool>,
682 // false at the beginning, once set, there are not allowed to be any more assignments
683 found_assignment: IndexVec<Local, bool>,
687 /// returns true if `local` can be propagated
688 fn check(body: &Body<'_>) -> IndexVec<Local, bool> {
689 let mut cpv = CanConstProp {
690 can_const_prop: IndexVec::from_elem(true, &body.local_decls),
691 found_assignment: IndexVec::from_elem(false, &body.local_decls),
693 for (local, val) in cpv.can_const_prop.iter_enumerated_mut() {
694 // cannot use args at all
695 // cannot use locals because if x < y { y - x } else { x - y } would
697 // FIXME(oli-obk): lint variables until they are used in a condition
698 // FIXME(oli-obk): lint if return value is constant
699 *val = body.local_kind(local) == LocalKind::Temp;
702 trace!("local {:?} can't be propagated because it's not a temporary", local);
705 cpv.visit_body(body);
710 impl<'tcx> Visitor<'tcx> for CanConstProp {
714 context: PlaceContext,
717 use rustc::mir::visit::PlaceContext::*;
719 // Constants must have at most one write
720 // FIXME(oli-obk): we could be more powerful here, if the multiple writes
721 // only occur in independent execution paths
722 MutatingUse(MutatingUseContext::Store) => if self.found_assignment[local] {
723 trace!("local {:?} can't be propagated because of multiple assignments", local);
724 self.can_const_prop[local] = false;
726 self.found_assignment[local] = true
728 // Reading constants is allowed an arbitrary number of times
729 NonMutatingUse(NonMutatingUseContext::Copy) |
730 NonMutatingUse(NonMutatingUseContext::Move) |
731 NonMutatingUse(NonMutatingUseContext::Inspect) |
732 NonMutatingUse(NonMutatingUseContext::Projection) |
733 MutatingUse(MutatingUseContext::Projection) |
736 trace!("local {:?} can't be propagaged because it's used: {:?}", local, context);
737 self.can_const_prop[local] = false;
743 impl<'mir, 'tcx> MutVisitor<'tcx> for ConstPropagator<'mir, 'tcx> {
746 constant: &mut Constant<'tcx>,
749 trace!("visit_constant: {:?}", constant);
750 self.super_constant(constant, location);
751 self.eval_constant(constant);
756 statement: &mut Statement<'tcx>,
759 trace!("visit_statement: {:?}", statement);
760 if let StatementKind::Assign(ref place, ref mut rval) = statement.kind {
761 let place_ty: Ty<'tcx> = place
762 .ty(&self.local_decls, self.tcx)
764 if let Ok(place_layout) = self.tcx.layout_of(self.param_env.and(place_ty)) {
765 if let Some(value) = self.const_prop(rval, place_layout, statement.source_info) {
766 if let Place::Base(PlaceBase::Local(local)) = *place {
767 trace!("checking whether {:?} can be stored to {:?}", value, local);
768 if self.can_const_prop[local] {
769 trace!("storing {:?} to {:?}", value, local);
770 assert!(self.get_const(local).is_none());
771 self.set_const(local, Some(value));
773 if self.should_const_prop() {
774 self.replace_with_const(
777 statement.source_info,
785 self.super_statement(statement, location);
790 terminator: &mut Terminator<'tcx>,
793 self.super_terminator(terminator, location);
794 let source_info = terminator.source_info;
795 match &mut terminator.kind {
796 TerminatorKind::Assert { expected, msg, ref mut cond, .. } => {
797 if let Some(value) = self.eval_operand(&cond, source_info) {
798 trace!("assertion on {:?} should be {:?}", value, expected);
799 let expected = ScalarMaybeUndef::from(Scalar::from_bool(*expected));
800 let value_const = self.ecx.read_scalar(value).unwrap();
801 if expected != value_const {
802 // poison all places this operand references so that further code
803 // doesn't use the invalid value
805 Operand::Move(ref place) | Operand::Copy(ref place) => {
806 let mut place = place;
807 while let Place::Projection(ref proj) = *place {
810 if let Place::Base(PlaceBase::Local(local)) = *place {
811 self.set_const(local, None);
814 Operand::Constant(_) => {}
816 let span = terminator.source_info.span;
820 .as_local_hir_id(self.source.def_id())
821 .expect("some part of a failing const eval must be local");
822 use rustc::mir::interpret::InterpError::*;
823 let msg = match msg {
827 RemainderByZero => msg.description().to_owned(),
828 BoundsCheck { ref len, ref index } => {
830 .eval_operand(len, source_info)
831 .expect("len must be const");
832 let len = match self.ecx.read_scalar(len) {
833 Ok(ScalarMaybeUndef::Scalar(Scalar::Raw {
836 other => bug!("const len not primitive: {:?}", other),
839 .eval_operand(index, source_info)
840 .expect("index must be const");
841 let index = match self.ecx.read_scalar(index) {
842 Ok(ScalarMaybeUndef::Scalar(Scalar::Raw {
845 other => bug!("const index not primitive: {:?}", other),
848 "index out of bounds: \
849 the len is {} but the index is {}",
854 // Need proper const propagator for these
858 ::rustc::lint::builtin::CONST_ERR,
864 if self.should_const_prop() {
865 if let ScalarMaybeUndef::Scalar(scalar) = value_const {
866 *cond = self.operand_from_scalar(
876 TerminatorKind::SwitchInt { ref mut discr, switch_ty, .. } => {
877 if self.should_const_prop() {
878 if let Some(value) = self.eval_operand(&discr, source_info) {
879 if let ScalarMaybeUndef::Scalar(scalar) =
880 self.ecx.read_scalar(value).unwrap() {
881 *discr = self.operand_from_scalar(scalar, switch_ty, source_info.span);
886 //none of these have Operands to const-propagate
887 TerminatorKind::Goto { .. } |
888 TerminatorKind::Resume |
889 TerminatorKind::Abort |
890 TerminatorKind::Return |
891 TerminatorKind::Unreachable |
892 TerminatorKind::Drop { .. } |
893 TerminatorKind::DropAndReplace { .. } |
894 TerminatorKind::Yield { .. } |
895 TerminatorKind::GeneratorDrop |
896 TerminatorKind::FalseEdges { .. } |
897 TerminatorKind::FalseUnwind { .. } => { }
898 //FIXME(wesleywiser) Call does have Operands that could be const-propagated
899 TerminatorKind::Call { .. } => { }