1 // Copyright 2017 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 //! Propagates constants for early reporting of statically known
12 //! assertion failures
15 use rustc::hir::def::Def;
16 use rustc::mir::{Constant, Location, Place, Mir, Operand, Rvalue, Local};
17 use rustc::mir::{NullOp, StatementKind, Statement, BasicBlock, LocalKind};
18 use rustc::mir::{TerminatorKind, ClearCrossCrate, SourceInfo, BinOp, ProjectionElem};
19 use rustc::mir::visit::{Visitor, PlaceContext};
20 use rustc::mir::interpret::{ConstEvalErr, EvalErrorKind, ScalarMaybeUndef};
21 use rustc::ty::{TyCtxt, self, Instance};
22 use rustc::mir::interpret::{Value, Scalar, GlobalId, EvalResult};
23 use interpret::EvalContext;
24 use interpret::CompileTimeEvaluator;
25 use interpret::{eval_promoted, mk_borrowck_eval_cx, ValTy};
26 use transform::{MirPass, MirSource};
27 use syntax::codemap::{Span, DUMMY_SP};
28 use rustc::ty::subst::Substs;
29 use rustc_data_structures::indexed_vec::IndexVec;
30 use rustc::ty::ParamEnv;
31 use rustc::ty::layout::{
32 LayoutOf, TyLayout, LayoutError,
33 HasTyCtxt, TargetDataLayout, HasDataLayout,
38 impl MirPass for ConstProp {
39 fn run_pass<'a, 'tcx>(&self,
40 tcx: TyCtxt<'a, 'tcx, 'tcx>,
42 mir: &mut Mir<'tcx>) {
43 // will be evaluated by miri and produce its errors there
44 if source.promoted.is_some() {
47 match tcx.describe_def(source.def_id) {
48 // skip statics/consts because they'll be evaluated by miri anyway
49 Some(Def::Const(..)) |
50 Some(Def::Static(..)) => return,
51 // we still run on associated constants, because they might not get evaluated
52 // within the current crate
55 trace!("ConstProp starting for {:?}", source.def_id);
57 // FIXME(oli-obk, eddyb) Optimize locals (or even local paths) to hold
58 // constants, instead of just checking for const-folding succeeding.
59 // That would require an uniform one-def no-mutation analysis
60 // and RPO (or recursing when needing the value of a local).
61 let mut optimization_finder = ConstPropagator::new(mir, tcx, source);
62 optimization_finder.visit_mir(mir);
64 trace!("ConstProp done for {:?}", source.def_id);
68 type Const<'tcx> = (Value, TyLayout<'tcx>, Span);
70 /// Finds optimization opportunities on the MIR.
71 struct ConstPropagator<'b, 'a, 'tcx:'a+'b> {
72 ecx: EvalContext<'a, 'b, 'tcx, CompileTimeEvaluator>,
74 tcx: TyCtxt<'a, 'tcx, 'tcx>,
76 places: IndexVec<Local, Option<Const<'tcx>>>,
77 can_const_prop: IndexVec<Local, bool>,
78 param_env: ParamEnv<'tcx>,
81 impl<'a, 'b, 'tcx> LayoutOf for &'a ConstPropagator<'a, 'b, 'tcx> {
82 type Ty = ty::Ty<'tcx>;
83 type TyLayout = Result<TyLayout<'tcx>, LayoutError<'tcx>>;
85 fn layout_of(self, ty: ty::Ty<'tcx>) -> Self::TyLayout {
86 self.tcx.layout_of(self.param_env.and(ty))
90 impl<'a, 'b, 'tcx> HasDataLayout for &'a ConstPropagator<'a, 'b, 'tcx> {
92 fn data_layout(&self) -> &TargetDataLayout {
97 impl<'a, 'b, 'tcx> HasTyCtxt<'tcx> for &'a ConstPropagator<'a, 'b, 'tcx> {
99 fn tcx<'c>(&'c self) -> TyCtxt<'c, 'tcx, 'tcx> {
104 impl<'b, 'a, 'tcx:'b> ConstPropagator<'b, 'a, 'tcx> {
107 tcx: TyCtxt<'a, 'tcx, 'tcx>,
109 ) -> ConstPropagator<'b, 'a, 'tcx> {
110 let param_env = tcx.param_env(source.def_id);
111 let substs = Substs::identity_for_item(tcx, source.def_id);
112 let instance = Instance::new(source.def_id, substs);
113 let ecx = mk_borrowck_eval_cx(tcx, instance, mir, DUMMY_SP).unwrap();
120 can_const_prop: CanConstProp::check(mir),
121 places: IndexVec::from_elem(None, &mir.local_decls),
127 source_info: SourceInfo,
131 F: FnOnce(&mut Self) -> EvalResult<'tcx, T>,
133 self.ecx.tcx.span = source_info.span;
134 let lint_root = match self.mir.source_scope_local_data {
135 ClearCrossCrate::Set(ref ivs) => {
136 use rustc_data_structures::indexed_vec::Idx;
137 //FIXME(#51314): remove this check
138 if source_info.scope.index() >= ivs.len() {
141 ivs[source_info.scope].lint_root
143 ClearCrossCrate::Clear => return None,
145 let r = match f(self) {
146 Ok(val) => Some(val),
148 let (stacktrace, span) = self.ecx.generate_stacktrace(None);
149 let diagnostic = ConstEvalErr { span, error, stacktrace };
150 use rustc::mir::interpret::EvalErrorKind::*;
151 match diagnostic.error.kind {
152 // don't report these, they make no sense in a const prop context
154 // at runtime these transformations might make sense
155 // FIXME: figure out the rules and start linting
156 | FunctionPointerTyMismatch(..)
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 | MemoryLockViolation { .. }
177 | MemoryAcquireConflict { .. }
178 | ValidationFailure(..)
179 | InvalidMemoryLockRelease { .. }
180 | DeallocatedLockedMemory { .. }
185 | DerefFunctionPointer
190 | AlignmentCheckFailed{..}
191 | CalledClosureAsFunction
192 | VtableForArgumentlessMethod
193 | ModifiedConstantMemory
195 // FIXME: should probably be removed and turned into a bug! call
196 | TypeNotPrimitive(_)
197 | ReallocatedWrongMemoryKind(_, _)
198 | DeallocatedWrongMemoryKind(_, _)
199 | ReallocateNonBasePtr
200 | DeallocateNonBasePtr
201 | IncorrectAllocationInformation(..)
202 | UnterminatedCString(_)
204 | HeapAllocNonPowerOfTwoAlignment(_)
206 | ReadFromReturnPointer
207 | GeneratorResumedAfterReturn
208 | GeneratorResumedAfterPanic
209 | ReferencedConstant(_)
212 // FIXME: report UB here
218 => bug!("these should not be in rustc, but in miri's machine errors"),
221 | UnimplementedTraitSelection
225 // these are just noise
240 diagnostic.report_as_lint(
242 "this expression will panic at runtime",
250 self.ecx.tcx.span = DUMMY_SP;
257 source_info: SourceInfo,
258 ) -> Option<Const<'tcx>> {
259 self.ecx.tcx.span = source_info.span;
260 match self.ecx.const_to_value(c.literal.val) {
262 let layout = self.tcx.layout_of(self.param_env.and(c.literal.ty)).ok()?;
263 Some((val, layout, c.span))
266 let (stacktrace, span) = self.ecx.generate_stacktrace(None);
267 let err = ConstEvalErr {
273 self.tcx.at(source_info.span),
274 "could not evaluate constant",
281 fn eval_place(&mut self, place: &Place<'tcx>, source_info: SourceInfo) -> Option<Const<'tcx>> {
283 Place::Local(loc) => self.places[loc].clone(),
284 Place::Projection(ref proj) => match proj.elem {
285 ProjectionElem::Field(field, _) => {
286 trace!("field proj on {:?}", proj.base);
287 let (base, layout, span) = self.eval_place(&proj.base, source_info)?;
288 let valty = self.use_ecx(source_info, |this| {
289 this.ecx.read_field(base, None, field, layout)
291 Some((valty.0, valty.1, span))
295 Place::Promoted(ref promoted) => {
296 let generics = self.tcx.generics_of(self.source.def_id);
297 if generics.requires_monomorphization(self.tcx) {
298 // FIXME: can't handle code with generics
301 let substs = Substs::identity_for_item(self.tcx, self.source.def_id);
302 let instance = Instance::new(self.source.def_id, substs);
305 promoted: Some(promoted.0),
307 // cannot use `const_eval` here, because that would require having the MIR
308 // for the current function available, but we're producing said MIR right now
309 let (value, _, ty) = self.use_ecx(source_info, |this| {
310 eval_promoted(&mut this.ecx, cid, this.mir, this.param_env)
312 let val = (value, ty, source_info.span);
313 trace!("evaluated promoted {:?} to {:?}", promoted, val);
320 fn eval_operand(&mut self, op: &Operand<'tcx>, source_info: SourceInfo) -> Option<Const<'tcx>> {
322 Operand::Constant(ref c) => self.eval_constant(c, source_info),
323 | Operand::Move(ref place)
324 | Operand::Copy(ref place) => self.eval_place(place, source_info),
330 rvalue: &Rvalue<'tcx>,
331 place_layout: TyLayout<'tcx>,
332 source_info: SourceInfo,
333 ) -> Option<Const<'tcx>> {
334 let span = source_info.span;
336 Rvalue::Use(ref op) => {
337 self.eval_operand(op, source_info)
341 Rvalue::Aggregate(..) |
342 Rvalue::NullaryOp(NullOp::Box, _) |
343 Rvalue::Discriminant(..) => None,
345 Rvalue::Cast(kind, ref operand, _) => {
346 let (value, layout, span) = self.eval_operand(operand, source_info)?;
347 self.use_ecx(source_info, |this| {
348 let dest_ptr = this.ecx.alloc_ptr(place_layout)?;
349 let place_align = place_layout.align;
350 let dest = ::interpret::Place::from_ptr(dest_ptr, place_align);
351 this.ecx.cast(ValTy { value, ty: layout.ty }, kind, place_layout.ty, dest)?;
353 Value::ByRef(dest_ptr.into(), place_align),
360 // FIXME(oli-obk): evaluate static/constant slice lengths
361 Rvalue::Len(_) => None,
362 Rvalue::NullaryOp(NullOp::SizeOf, ty) => {
363 type_size_of(self.tcx, self.param_env, ty).and_then(|n| Some((
364 Value::Scalar(Scalar::Bits {
366 size: self.tcx.data_layout.pointer_size.bytes() as u8,
368 self.tcx.layout_of(self.param_env.and(self.tcx.types.usize)).ok()?,
372 Rvalue::UnaryOp(op, ref arg) => {
373 let def_id = if self.tcx.is_closure(self.source.def_id) {
374 self.tcx.closure_base_def_id(self.source.def_id)
378 let generics = self.tcx.generics_of(def_id);
379 if generics.requires_monomorphization(self.tcx) {
380 // FIXME: can't handle code with generics
384 let val = self.eval_operand(arg, source_info)?;
385 let prim = self.use_ecx(source_info, |this| {
386 this.ecx.value_to_scalar(ValTy { value: val.0, ty: val.1.ty })
388 let val = self.use_ecx(source_info, |this| this.ecx.unary_op(op, prim, val.1))?;
389 Some((Value::Scalar(val.into()), place_layout, span))
391 Rvalue::CheckedBinaryOp(op, ref left, ref right) |
392 Rvalue::BinaryOp(op, ref left, ref right) => {
393 trace!("rvalue binop {:?} for {:?} and {:?}", op, left, right);
394 let right = self.eval_operand(right, source_info)?;
395 let def_id = if self.tcx.is_closure(self.source.def_id) {
396 self.tcx.closure_base_def_id(self.source.def_id)
400 let generics = self.tcx.generics_of(def_id);
401 if generics.requires_monomorphization(self.tcx) {
402 // FIXME: can't handle code with generics
406 let r = self.use_ecx(source_info, |this| {
407 this.ecx.value_to_scalar(ValTy { value: right.0, ty: right.1.ty })
409 if op == BinOp::Shr || op == BinOp::Shl {
410 let left_ty = left.ty(self.mir, self.tcx);
413 .layout_of(self.param_env.and(left_ty))
417 let right_size = right.1.size;
418 if r.to_bits(right_size).ok().map_or(false, |b| b >= left_bits as u128) {
419 let source_scope_local_data = match self.mir.source_scope_local_data {
420 ClearCrossCrate::Set(ref data) => data,
421 ClearCrossCrate::Clear => return None,
423 let dir = if op == BinOp::Shr {
428 let node_id = source_scope_local_data[source_info.scope].lint_root;
430 ::rustc::lint::builtin::EXCEEDING_BITSHIFTS,
433 &format!("attempt to shift {} with overflow", dir));
437 let left = self.eval_operand(left, source_info)?;
438 let l = self.use_ecx(source_info, |this| {
439 this.ecx.value_to_scalar(ValTy { value: left.0, ty: left.1.ty })
441 trace!("const evaluating {:?} for {:?} and {:?}", op, left, right);
442 let (val, overflow) = self.use_ecx(source_info, |this| {
443 this.ecx.binary_op(op, l, left.1.ty, r, right.1.ty)
445 let val = if let Rvalue::CheckedBinaryOp(..) = *rvalue {
448 Scalar::from_bool(overflow).into(),
452 let err = EvalErrorKind::Overflow(op).into();
453 let _: Option<()> = self.use_ecx(source_info, |_| Err(err));
456 Value::Scalar(val.into())
458 Some((val, place_layout, span))
464 fn type_size_of<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
465 param_env: ty::ParamEnv<'tcx>,
466 ty: ty::Ty<'tcx>) -> Option<u64> {
467 tcx.layout_of(param_env.and(ty)).ok().map(|layout| layout.size.bytes())
470 struct CanConstProp {
471 can_const_prop: IndexVec<Local, bool>,
472 // false at the beginning, once set, there are not allowed to be any more assignments
473 found_assignment: IndexVec<Local, bool>,
477 /// returns true if `local` can be propagated
478 fn check(mir: &Mir) -> IndexVec<Local, bool> {
479 let mut cpv = CanConstProp {
480 can_const_prop: IndexVec::from_elem(true, &mir.local_decls),
481 found_assignment: IndexVec::from_elem(false, &mir.local_decls),
483 for (local, val) in cpv.can_const_prop.iter_enumerated_mut() {
484 // cannot use args at all
485 // cannot use locals because if x < y { y - x } else { x - y } would
487 // FIXME(oli-obk): lint variables until they are used in a condition
488 // FIXME(oli-obk): lint if return value is constant
489 *val = mir.local_kind(local) == LocalKind::Temp;
496 impl<'tcx> Visitor<'tcx> for CanConstProp {
500 context: PlaceContext<'tcx>,
503 use rustc::mir::visit::PlaceContext::*;
505 // Constants must have at most one write
506 // FIXME(oli-obk): we could be more powerful here, if the multiple writes
507 // only occur in independent execution paths
508 Store => if self.found_assignment[local] {
509 self.can_const_prop[local] = false;
511 self.found_assignment[local] = true
513 // Reading constants is allowed an arbitrary number of times
515 StorageDead | StorageLive |
519 _ => self.can_const_prop[local] = false,
524 impl<'b, 'a, 'tcx> Visitor<'tcx> for ConstPropagator<'b, 'a, 'tcx> {
527 constant: &Constant<'tcx>,
530 trace!("visit_constant: {:?}", constant);
531 self.super_constant(constant, location);
532 let source_info = *self.mir.source_info(location);
533 self.eval_constant(constant, source_info);
539 statement: &Statement<'tcx>,
542 trace!("visit_statement: {:?}", statement);
543 if let StatementKind::Assign(ref place, ref rval) = statement.kind {
544 let place_ty: ty::Ty<'tcx> = place
545 .ty(&self.mir.local_decls, self.tcx)
547 if let Ok(place_layout) = self.tcx.layout_of(self.param_env.and(place_ty)) {
548 if let Some(value) = self.const_prop(rval, place_layout, statement.source_info) {
549 if let Place::Local(local) = *place {
550 trace!("checking whether {:?} can be stored to {:?}", value, local);
551 if self.can_const_prop[local] {
552 trace!("storing {:?} to {:?}", value, local);
553 assert!(self.places[local].is_none());
554 self.places[local] = Some(value);
560 self.super_statement(block, statement, location);
563 fn visit_terminator_kind(
566 kind: &TerminatorKind<'tcx>,
569 self.super_terminator_kind(block, kind, location);
570 let source_info = *self.mir.source_info(location);
571 if let TerminatorKind::Assert { expected, msg, cond, .. } = kind {
572 if let Some(value) = self.eval_operand(cond, source_info) {
573 trace!("assertion on {:?} should be {:?}", value, expected);
574 if Value::Scalar(Scalar::from_bool(*expected).into()) != value.0 {
575 // poison all places this operand references so that further code
576 // doesn't use the invalid value
578 Operand::Move(ref place) | Operand::Copy(ref place) => {
579 let mut place = place;
580 while let Place::Projection(ref proj) = *place {
583 if let Place::Local(local) = *place {
584 self.places[local] = None;
587 Operand::Constant(_) => {}
589 let span = self.mir[block]
598 .as_local_node_id(self.source.def_id)
599 .expect("some part of a failing const eval must be local");
600 use rustc::mir::interpret::EvalErrorKind::*;
601 let msg = match msg {
605 RemainderByZero => msg.description().to_owned(),
606 BoundsCheck { ref len, ref index } => {
608 .eval_operand(len, source_info)
609 .expect("len must be const");
610 let len = match len.0 {
611 Value::Scalar(ScalarMaybeUndef::Scalar(Scalar::Bits {
614 _ => bug!("const len not primitive: {:?}", len),
617 .eval_operand(index, source_info)
618 .expect("index must be const");
619 let index = match index.0 {
620 Value::Scalar(ScalarMaybeUndef::Scalar(Scalar::Bits {
623 _ => bug!("const index not primitive: {:?}", index),
626 "index out of bounds: \
627 the len is {} but the index is {}",
632 // Need proper const propagator for these
636 ::rustc::lint::builtin::CONST_ERR,