1 //! Propagates constants for early reporting of statically known
5 use rustc::hir::def::Def;
6 use rustc::mir::{Constant, Location, Place, PlaceBase, Mir, Operand, Rvalue, Local};
7 use rustc::mir::{NullOp, UnOp, StatementKind, Statement, BasicBlock, LocalKind};
8 use rustc::mir::{TerminatorKind, ClearCrossCrate, SourceInfo, BinOp, ProjectionElem};
9 use rustc::mir::visit::{Visitor, PlaceContext, MutatingUseContext, NonMutatingUseContext};
10 use rustc::mir::interpret::{EvalErrorKind, Scalar, GlobalId, EvalResult};
11 use rustc::ty::{TyCtxt, self, Instance};
12 use syntax::source_map::{Span, DUMMY_SP};
13 use rustc::ty::subst::InternalSubsts;
14 use rustc_data_structures::indexed_vec::IndexVec;
15 use rustc::ty::ParamEnv;
16 use rustc::ty::layout::{
17 LayoutOf, TyLayout, LayoutError,
18 HasTyCtxt, TargetDataLayout, HasDataLayout,
21 use crate::interpret::{EvalContext, ScalarMaybeUndef, Immediate, OpTy, ImmTy, MemoryKind};
22 use crate::const_eval::{
23 CompileTimeInterpreter, error_to_const_error, eval_promoted, mk_eval_cx,
25 use crate::transform::{MirPass, MirSource};
29 impl MirPass for ConstProp {
30 fn run_pass<'a, 'tcx>(&self,
31 tcx: TyCtxt<'a, 'tcx, 'tcx>,
32 source: MirSource<'tcx>,
33 mir: &mut Mir<'tcx>) {
34 // will be evaluated by miri and produce its errors there
35 if source.promoted.is_some() {
39 use rustc::hir::map::blocks::FnLikeNode;
40 let hir_id = tcx.hir().as_local_hir_id(source.def_id())
41 .expect("Non-local call to local provider is_const_fn");
43 let is_fn_like = FnLikeNode::from_node(tcx.hir().get_by_hir_id(hir_id)).is_some();
44 let is_assoc_const = match tcx.describe_def(source.def_id()) {
45 Some(Def::AssociatedConst(_)) => true,
49 // Only run const prop on functions, methods, closures and associated constants
50 if !is_fn_like && !is_assoc_const {
51 // skip anon_const/statics/consts because they'll be evaluated by miri anyway
52 trace!("ConstProp skipped for {:?}", source.def_id());
56 trace!("ConstProp starting for {:?}", source.def_id());
58 // FIXME(oli-obk, eddyb) Optimize locals (or even local paths) to hold
59 // constants, instead of just checking for const-folding succeeding.
60 // That would require an uniform one-def no-mutation analysis
61 // and RPO (or recursing when needing the value of a local).
62 let mut optimization_finder = ConstPropagator::new(mir, tcx, source);
63 optimization_finder.visit_mir(mir);
65 trace!("ConstProp done for {:?}", source.def_id());
69 type Const<'tcx> = (OpTy<'tcx>, Span);
71 /// Finds optimization opportunities on the MIR.
72 struct ConstPropagator<'a, 'mir, 'tcx:'a+'mir> {
73 ecx: EvalContext<'a, 'mir, 'tcx, CompileTimeInterpreter<'a, 'mir, 'tcx>>,
75 tcx: TyCtxt<'a, 'tcx, 'tcx>,
76 source: MirSource<'tcx>,
77 places: IndexVec<Local, Option<Const<'tcx>>>,
78 can_const_prop: IndexVec<Local, bool>,
79 param_env: ParamEnv<'tcx>,
82 impl<'a, 'b, 'tcx> LayoutOf for ConstPropagator<'a, 'b, 'tcx> {
83 type Ty = ty::Ty<'tcx>;
84 type TyLayout = Result<TyLayout<'tcx>, LayoutError<'tcx>>;
86 fn layout_of(&self, ty: ty::Ty<'tcx>) -> Self::TyLayout {
87 self.tcx.layout_of(self.param_env.and(ty))
91 impl<'a, 'b, 'tcx> HasDataLayout for ConstPropagator<'a, 'b, 'tcx> {
93 fn data_layout(&self) -> &TargetDataLayout {
98 impl<'a, 'b, 'tcx> HasTyCtxt<'tcx> for ConstPropagator<'a, 'b, 'tcx> {
100 fn tcx<'c>(&'c self) -> TyCtxt<'c, 'tcx, 'tcx> {
105 impl<'a, 'mir, 'tcx> ConstPropagator<'a, 'mir, 'tcx> {
107 mir: &'mir Mir<'tcx>,
108 tcx: TyCtxt<'a, 'tcx, 'tcx>,
109 source: MirSource<'tcx>,
110 ) -> ConstPropagator<'a, 'mir, 'tcx> {
111 let param_env = tcx.param_env(source.def_id());
112 let ecx = mk_eval_cx(tcx, tcx.def_span(source.def_id()), param_env);
119 can_const_prop: CanConstProp::check(mir),
120 places: IndexVec::from_elem(None, &mir.local_decls),
126 source_info: SourceInfo,
130 F: FnOnce(&mut Self) -> EvalResult<'tcx, T>,
132 self.ecx.tcx.span = source_info.span;
133 let lint_root = match self.mir.source_scope_local_data {
134 ClearCrossCrate::Set(ref ivs) => {
135 //FIXME(#51314): remove this check
136 if source_info.scope.index() >= ivs.len() {
139 ivs[source_info.scope].lint_root
141 ClearCrossCrate::Clear => return None,
143 let r = match f(self) {
144 Ok(val) => Some(val),
146 let diagnostic = error_to_const_error(&self.ecx, error);
147 use rustc::mir::interpret::EvalErrorKind::*;
148 match diagnostic.error {
149 // don't report these, they make no sense in a const prop context
151 // at runtime these transformations might make sense
152 // FIXME: figure out the rules and start linting
153 | FunctionAbiMismatch(..)
154 | FunctionArgMismatch(..)
155 | FunctionRetMismatch(..)
156 | FunctionArgCountMismatch
157 // fine at runtime, might be a register address or sth
162 // don't report const evaluator limits
163 | StackFrameLimitReached
168 | InvalidMemoryAccess
169 | DanglingPointerDeref
171 | InvalidFunctionPointer
173 | InvalidDiscriminant(..)
174 | PointerOutOfBounds { .. }
175 | InvalidNullPointerUsage
176 | ValidationFailure(..)
181 | DerefFunctionPointer
186 | AlignmentCheckFailed{..}
187 | CalledClosureAsFunction
188 | VtableForArgumentlessMethod
189 | ModifiedConstantMemory
192 // FIXME: should probably be removed and turned into a bug! call
193 | TypeNotPrimitive(_)
194 | ReallocatedWrongMemoryKind(_, _)
195 | DeallocatedWrongMemoryKind(_, _)
196 | ReallocateNonBasePtr
197 | DeallocateNonBasePtr
198 | IncorrectAllocationInformation(..)
199 | UnterminatedCString(_)
201 | HeapAllocNonPowerOfTwoAlignment(_)
203 | ReadFromReturnPointer
204 | GeneratorResumedAfterReturn
205 | GeneratorResumedAfterPanic
209 // FIXME: report UB here
215 => bug!("these should not be in rustc, but in miri's machine errors"),
218 | UnimplementedTraitSelection
221 // these are just noise
236 diagnostic.report_as_lint(
238 "this expression will panic at runtime",
246 self.ecx.tcx.span = DUMMY_SP;
253 source_info: SourceInfo,
254 ) -> Option<Const<'tcx>> {
255 self.ecx.tcx.span = source_info.span;
256 match self.ecx.eval_const_to_op(*c.literal, None) {
261 let err = error_to_const_error(&self.ecx, error);
262 err.report_as_error(self.ecx.tcx, "erroneous constant used");
268 fn eval_place(&mut self, place: &Place<'tcx>, source_info: SourceInfo) -> Option<Const<'tcx>> {
269 use rustc::mir::Static;
271 Place::Base(PlaceBase::Local(loc)) => self.places[loc].clone(),
272 Place::Projection(ref proj) => match proj.elem {
273 ProjectionElem::Field(field, _) => {
274 trace!("field proj on {:?}", proj.base);
275 let (base, span) = self.eval_place(&proj.base, source_info)?;
276 let res = self.use_ecx(source_info, |this| {
277 this.ecx.operand_field(base, field.index() as u64)
281 // We could get more projections by using e.g., `operand_projection`,
282 // but we do not even have the stack frame set up properly so
283 // an `Index` projection would throw us off-track.
286 Place::Base(PlaceBase::Static(box Static {promoted: Some(promoted), ty: _, ..})) => {
287 let generics = self.tcx.generics_of(self.source.def_id());
288 if generics.requires_monomorphization(self.tcx) {
289 // FIXME: can't handle code with generics
292 let substs = InternalSubsts::identity_for_item(self.tcx, self.source.def_id());
293 let instance = Instance::new(self.source.def_id(), substs);
296 promoted: Some(promoted),
298 // cannot use `const_eval` here, because that would require having the MIR
299 // for the current function available, but we're producing said MIR right now
300 let res = self.use_ecx(source_info, |this| {
301 eval_promoted(this.tcx, cid, this.mir, this.param_env)
303 trace!("evaluated promoted {:?} to {:?}", promoted, res);
304 Some((res.into(), source_info.span))
310 fn eval_operand(&mut self, op: &Operand<'tcx>, source_info: SourceInfo) -> Option<Const<'tcx>> {
312 Operand::Constant(ref c) => self.eval_constant(c, source_info),
313 | Operand::Move(ref place)
314 | Operand::Copy(ref place) => self.eval_place(place, source_info),
320 rvalue: &Rvalue<'tcx>,
321 place_layout: TyLayout<'tcx>,
322 source_info: SourceInfo,
323 ) -> Option<Const<'tcx>> {
324 let span = source_info.span;
326 Rvalue::Use(ref op) => {
327 self.eval_operand(op, source_info)
331 Rvalue::Aggregate(..) |
332 Rvalue::NullaryOp(NullOp::Box, _) |
333 Rvalue::Discriminant(..) => None,
335 Rvalue::Cast(kind, ref operand, _) => {
336 let (op, span) = self.eval_operand(operand, source_info)?;
337 self.use_ecx(source_info, |this| {
338 let dest = this.ecx.allocate(place_layout, MemoryKind::Stack);
339 this.ecx.cast(op, kind, dest.into())?;
340 Ok((dest.into(), span))
344 // FIXME(oli-obk): evaluate static/constant slice lengths
345 Rvalue::Len(_) => None,
346 Rvalue::NullaryOp(NullOp::SizeOf, ty) => {
347 type_size_of(self.tcx, self.param_env, ty).and_then(|n| Some((
349 imm: Immediate::Scalar(
352 size: self.tcx.data_layout.pointer_size.bytes() as u8,
355 layout: self.tcx.layout_of(self.param_env.and(self.tcx.types.usize)).ok()?,
360 Rvalue::UnaryOp(op, ref arg) => {
361 let def_id = if self.tcx.is_closure(self.source.def_id()) {
362 self.tcx.closure_base_def_id(self.source.def_id())
366 let generics = self.tcx.generics_of(def_id);
367 if generics.requires_monomorphization(self.tcx) {
368 // FIXME: can't handle code with generics
372 let (arg, _) = self.eval_operand(arg, source_info)?;
373 let val = self.use_ecx(source_info, |this| {
374 let prim = this.ecx.read_immediate(arg)?;
377 // Need to do overflow check here: For actual CTFE, MIR
378 // generation emits code that does this before calling the op.
379 if prim.to_bits()? == (1 << (prim.layout.size.bits() - 1)) {
380 return err!(OverflowNeg);
387 // Now run the actual operation.
388 this.ecx.unary_op(op, prim)
391 imm: Immediate::Scalar(val.into()),
392 layout: place_layout,
394 Some((res.into(), span))
396 Rvalue::CheckedBinaryOp(op, ref left, ref right) |
397 Rvalue::BinaryOp(op, ref left, ref right) => {
398 trace!("rvalue binop {:?} for {:?} and {:?}", op, left, right);
399 let right = self.eval_operand(right, source_info)?;
400 let def_id = if self.tcx.is_closure(self.source.def_id()) {
401 self.tcx.closure_base_def_id(self.source.def_id())
405 let generics = self.tcx.generics_of(def_id);
406 if generics.requires_monomorphization(self.tcx) {
407 // FIXME: can't handle code with generics
411 let r = self.use_ecx(source_info, |this| {
412 this.ecx.read_immediate(right.0)
414 if op == BinOp::Shr || op == BinOp::Shl {
415 let left_ty = left.ty(self.mir, self.tcx);
418 .layout_of(self.param_env.and(left_ty))
422 let right_size = right.0.layout.size;
423 let r_bits = r.to_scalar().and_then(|r| r.to_bits(right_size));
424 if r_bits.ok().map_or(false, |b| b >= left_bits as u128) {
425 let source_scope_local_data = match self.mir.source_scope_local_data {
426 ClearCrossCrate::Set(ref data) => data,
427 ClearCrossCrate::Clear => return None,
429 let dir = if op == BinOp::Shr {
434 let hir_id = source_scope_local_data[source_info.scope].lint_root;
436 ::rustc::lint::builtin::EXCEEDING_BITSHIFTS,
439 &format!("attempt to shift {} with overflow", dir));
443 let left = self.eval_operand(left, source_info)?;
444 let l = self.use_ecx(source_info, |this| {
445 this.ecx.read_immediate(left.0)
447 trace!("const evaluating {:?} for {:?} and {:?}", op, left, right);
448 let (val, overflow) = self.use_ecx(source_info, |this| {
449 this.ecx.binary_op(op, l, r)
451 let val = if let Rvalue::CheckedBinaryOp(..) = *rvalue {
452 Immediate::ScalarPair(
454 Scalar::from_bool(overflow).into(),
458 let err = EvalErrorKind::Overflow(op).into();
459 let _: Option<()> = self.use_ecx(source_info, |_| Err(err));
462 Immediate::Scalar(val.into())
466 layout: place_layout,
468 Some((res.into(), span))
474 fn type_size_of<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
475 param_env: ty::ParamEnv<'tcx>,
476 ty: ty::Ty<'tcx>) -> Option<u64> {
477 tcx.layout_of(param_env.and(ty)).ok().map(|layout| layout.size.bytes())
480 struct CanConstProp {
481 can_const_prop: IndexVec<Local, bool>,
482 // false at the beginning, once set, there are not allowed to be any more assignments
483 found_assignment: IndexVec<Local, bool>,
487 /// returns true if `local` can be propagated
488 fn check(mir: &Mir<'_>) -> IndexVec<Local, bool> {
489 let mut cpv = CanConstProp {
490 can_const_prop: IndexVec::from_elem(true, &mir.local_decls),
491 found_assignment: IndexVec::from_elem(false, &mir.local_decls),
493 for (local, val) in cpv.can_const_prop.iter_enumerated_mut() {
494 // cannot use args at all
495 // cannot use locals because if x < y { y - x } else { x - y } would
497 // FIXME(oli-obk): lint variables until they are used in a condition
498 // FIXME(oli-obk): lint if return value is constant
499 *val = mir.local_kind(local) == LocalKind::Temp;
506 impl<'tcx> Visitor<'tcx> for CanConstProp {
510 context: PlaceContext<'tcx>,
513 use rustc::mir::visit::PlaceContext::*;
515 // Constants must have at most one write
516 // FIXME(oli-obk): we could be more powerful here, if the multiple writes
517 // only occur in independent execution paths
518 MutatingUse(MutatingUseContext::Store) => if self.found_assignment[local] {
519 self.can_const_prop[local] = false;
521 self.found_assignment[local] = true
523 // Reading constants is allowed an arbitrary number of times
524 NonMutatingUse(NonMutatingUseContext::Copy) |
525 NonMutatingUse(NonMutatingUseContext::Move) |
526 NonMutatingUse(NonMutatingUseContext::Inspect) |
527 NonMutatingUse(NonMutatingUseContext::Projection) |
528 MutatingUse(MutatingUseContext::Projection) |
530 _ => self.can_const_prop[local] = false,
535 impl<'b, 'a, 'tcx> Visitor<'tcx> for ConstPropagator<'b, 'a, 'tcx> {
538 constant: &Constant<'tcx>,
541 trace!("visit_constant: {:?}", constant);
542 self.super_constant(constant, location);
543 let source_info = *self.mir.source_info(location);
544 self.eval_constant(constant, source_info);
550 statement: &Statement<'tcx>,
553 trace!("visit_statement: {:?}", statement);
554 if let StatementKind::Assign(ref place, ref rval) = statement.kind {
555 let place_ty: ty::Ty<'tcx> = place
556 .ty(&self.mir.local_decls, self.tcx)
558 if let Ok(place_layout) = self.tcx.layout_of(self.param_env.and(place_ty)) {
559 if let Some(value) = self.const_prop(rval, place_layout, statement.source_info) {
560 if let Place::Base(PlaceBase::Local(local)) = *place {
561 trace!("checking whether {:?} can be stored to {:?}", value, local);
562 if self.can_const_prop[local] {
563 trace!("storing {:?} to {:?}", value, local);
564 assert!(self.places[local].is_none());
565 self.places[local] = Some(value);
571 self.super_statement(block, statement, location);
574 fn visit_terminator_kind(
577 kind: &TerminatorKind<'tcx>,
580 self.super_terminator_kind(block, kind, location);
581 let source_info = *self.mir.source_info(location);
582 if let TerminatorKind::Assert { expected, msg, cond, .. } = kind {
583 if let Some(value) = self.eval_operand(cond, source_info) {
584 trace!("assertion on {:?} should be {:?}", value, expected);
585 let expected = ScalarMaybeUndef::from(Scalar::from_bool(*expected));
586 if expected != self.ecx.read_scalar(value.0).unwrap() {
587 // poison all places this operand references so that further code
588 // doesn't use the invalid value
590 Operand::Move(ref place) | Operand::Copy(ref place) => {
591 let mut place = place;
592 while let Place::Projection(ref proj) = *place {
595 if let Place::Base(PlaceBase::Local(local)) = *place {
596 self.places[local] = None;
599 Operand::Constant(_) => {}
601 let span = self.mir[block]
610 .as_local_hir_id(self.source.def_id())
611 .expect("some part of a failing const eval must be local");
612 use rustc::mir::interpret::EvalErrorKind::*;
613 let msg = match msg {
617 RemainderByZero => msg.description().to_owned(),
618 BoundsCheck { ref len, ref index } => {
620 .eval_operand(len, source_info)
621 .expect("len must be const");
622 let len = match self.ecx.read_scalar(len.0) {
623 Ok(ScalarMaybeUndef::Scalar(Scalar::Bits {
626 other => bug!("const len not primitive: {:?}", other),
629 .eval_operand(index, source_info)
630 .expect("index must be const");
631 let index = match self.ecx.read_scalar(index.0) {
632 Ok(ScalarMaybeUndef::Scalar(Scalar::Bits {
635 other => bug!("const index not primitive: {:?}", other),
638 "index out of bounds: \
639 the len is {} but the index is {}",
644 // Need proper const propagator for these
648 ::rustc::lint::builtin::CONST_ERR,