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, Literal, 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::middle::const_val::{ConstVal, ConstEvalErr, ErrKind};
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 because they'll be evaluated by miri anyway
49 Some(Def::Static(..)) => return,
52 trace!("ConstProp starting for {:?}", source.def_id);
54 // FIXME(oli-obk, eddyb) Optimize locals (or even local paths) to hold
55 // constants, instead of just checking for const-folding succeeding.
56 // That would require an uniform one-def no-mutation analysis
57 // and RPO (or recursing when needing the value of a local).
58 let mut optimization_finder = ConstPropagator::new(mir, tcx, source);
59 optimization_finder.visit_mir(mir);
61 trace!("ConstProp done for {:?}", source.def_id);
65 type Const<'tcx> = (Value, ty::Ty<'tcx>, Span);
67 /// Finds optimization opportunities on the MIR.
68 struct ConstPropagator<'b, 'a, 'tcx:'a+'b> {
69 ecx: EvalContext<'a, 'b, 'tcx, CompileTimeEvaluator>,
71 tcx: TyCtxt<'a, 'tcx, 'tcx>,
73 places: IndexVec<Local, Option<Const<'tcx>>>,
74 can_const_prop: IndexVec<Local, bool>,
75 param_env: ParamEnv<'tcx>,
78 impl<'a, 'b, 'tcx> LayoutOf for &'a ConstPropagator<'a, 'b, 'tcx> {
79 type Ty = ty::Ty<'tcx>;
80 type TyLayout = Result<TyLayout<'tcx>, LayoutError<'tcx>>;
82 fn layout_of(self, ty: ty::Ty<'tcx>) -> Self::TyLayout {
83 self.tcx.layout_of(self.param_env.and(ty))
87 impl<'a, 'b, 'tcx> HasDataLayout for &'a ConstPropagator<'a, 'b, 'tcx> {
89 fn data_layout(&self) -> &TargetDataLayout {
94 impl<'a, 'b, 'tcx> HasTyCtxt<'tcx> for &'a ConstPropagator<'a, 'b, 'tcx> {
96 fn tcx<'c>(&'c self) -> TyCtxt<'c, 'tcx, 'tcx> {
101 impl<'b, 'a, 'tcx:'b> ConstPropagator<'b, 'a, 'tcx> {
104 tcx: TyCtxt<'a, 'tcx, 'tcx>,
106 ) -> ConstPropagator<'b, 'a, 'tcx> {
107 let param_env = tcx.param_env(source.def_id);
108 let substs = Substs::identity_for_item(tcx, source.def_id);
109 let instance = Instance::new(source.def_id, substs);
110 let ecx = mk_borrowck_eval_cx(tcx, instance, mir, DUMMY_SP).unwrap();
117 can_const_prop: CanConstProp::check(mir),
118 places: IndexVec::from_elem(None, &mir.local_decls),
124 source_info: SourceInfo,
128 F: FnOnce(&mut Self) -> EvalResult<'tcx, T>,
130 self.ecx.tcx.span = source_info.span;
131 let lint_root = match self.mir.source_scope_local_data {
132 ClearCrossCrate::Set(ref ivs) => {
133 use rustc_data_structures::indexed_vec::Idx;
134 //FIXME(#51314): remove this check
135 if source_info.scope.index() >= ivs.len() {
138 ivs[source_info.scope].lint_root
140 ClearCrossCrate::Clear => return None,
142 let r = match f(self) {
143 Ok(val) => Some(val),
145 let (frames, span) = self.ecx.generate_stacktrace(None);
146 let err = ConstEvalErr {
148 kind: ErrKind::Miri(err, frames).into(),
152 "this expression will panic at runtime",
158 self.ecx.tcx.span = DUMMY_SP;
162 fn const_eval(&mut self, cid: GlobalId<'tcx>, source_info: SourceInfo) -> Option<Const<'tcx>> {
163 let value = match self.tcx.const_eval(self.param_env.and(cid)) {
167 self.tcx.at(err.span),
168 "constant evaluation error",
173 let val = match value.val {
174 ConstVal::Value(v) => {
175 self.use_ecx(source_info, |this| this.ecx.const_value_to_value(v, value.ty))?
177 _ => bug!("eval produced: {:?}", value),
179 let val = (val, value.ty, source_info.span);
180 trace!("evaluated {:?} to {:?}", cid, val);
187 source_info: SourceInfo,
188 ) -> Option<Const<'tcx>> {
190 Literal::Value { value } => match value.val {
191 ConstVal::Value(v) => {
192 let v = self.use_ecx(source_info, |this| {
193 this.ecx.const_value_to_value(v, value.ty)
195 Some((v, value.ty, c.span))
197 ConstVal::Unevaluated(did, substs) => {
198 let instance = Instance::resolve(
208 self.const_eval(cid, source_info)
211 // evaluate the promoted and replace the constant with the evaluated result
212 Literal::Promoted { index } => {
213 let generics = self.tcx.generics_of(self.source.def_id);
214 if generics.requires_monomorphization(self.tcx) {
215 // FIXME: can't handle code with generics
218 let substs = Substs::identity_for_item(self.tcx, self.source.def_id);
219 let instance = Instance::new(self.source.def_id, substs);
222 promoted: Some(index),
224 // cannot use `const_eval` here, because that would require having the MIR
225 // for the current function available, but we're producing said MIR right now
226 let (value, _, ty) = self.use_ecx(source_info, |this| {
227 eval_promoted(&mut this.ecx, cid, this.mir, this.param_env)
229 let val = (value, ty, c.span);
230 trace!("evaluated {:?} to {:?}", c, val);
236 fn eval_place(&mut self, place: &Place<'tcx>, source_info: SourceInfo) -> Option<Const<'tcx>> {
238 Place::Local(loc) => self.places[loc].clone(),
239 Place::Projection(ref proj) => match proj.elem {
240 ProjectionElem::Field(field, _) => {
241 trace!("field proj on {:?}", proj.base);
242 let (base, ty, span) = self.eval_place(&proj.base, source_info)?;
243 let valty = self.use_ecx(source_info, |this| {
244 this.ecx.read_field(base, None, field, ty)
246 Some((valty.value, valty.ty, span))
254 fn eval_operand(&mut self, op: &Operand<'tcx>, source_info: SourceInfo) -> Option<Const<'tcx>> {
256 Operand::Constant(ref c) => self.eval_constant(c, source_info),
257 | Operand::Move(ref place)
258 | Operand::Copy(ref place) => self.eval_place(place, source_info),
264 rvalue: &Rvalue<'tcx>,
265 place_ty: ty::Ty<'tcx>,
266 source_info: SourceInfo,
267 ) -> Option<Const<'tcx>> {
268 let span = source_info.span;
270 // This branch exists for the sanity type check
271 Rvalue::Use(Operand::Constant(ref c)) => {
272 assert_eq!(c.ty, place_ty);
273 self.eval_constant(c, source_info)
275 Rvalue::Use(ref op) => {
276 self.eval_operand(op, source_info)
281 Rvalue::Aggregate(..) |
282 Rvalue::NullaryOp(NullOp::Box, _) |
283 Rvalue::Discriminant(..) => None,
284 // FIXME(oli-obk): evaluate static/constant slice lengths
285 Rvalue::Len(_) => None,
286 Rvalue::NullaryOp(NullOp::SizeOf, ty) => {
287 let param_env = self.tcx.param_env(self.source.def_id);
288 type_size_of(self.tcx, param_env, ty).map(|n| (
289 Value::Scalar(Scalar::Bits {
291 defined: self.tcx.data_layout.pointer_size.bits() as u8,
293 self.tcx.types.usize,
297 Rvalue::UnaryOp(op, ref arg) => {
298 let def_id = if self.tcx.is_closure(self.source.def_id) {
299 self.tcx.closure_base_def_id(self.source.def_id)
303 let generics = self.tcx.generics_of(def_id);
304 if generics.requires_monomorphization(self.tcx) {
305 // FIXME: can't handle code with generics
309 let val = self.eval_operand(arg, source_info)?;
310 let prim = self.use_ecx(source_info, |this| {
311 this.ecx.value_to_scalar(ValTy { value: val.0, ty: val.1 })
313 let val = self.use_ecx(source_info, |this| this.ecx.unary_op(op, prim, val.1))?;
314 Some((Value::Scalar(val), place_ty, span))
316 Rvalue::CheckedBinaryOp(op, ref left, ref right) |
317 Rvalue::BinaryOp(op, ref left, ref right) => {
318 trace!("rvalue binop {:?} for {:?} and {:?}", op, left, right);
319 let right = self.eval_operand(right, source_info)?;
320 let def_id = if self.tcx.is_closure(self.source.def_id) {
321 self.tcx.closure_base_def_id(self.source.def_id)
325 let generics = self.tcx.generics_of(def_id);
326 if generics.requires_monomorphization(self.tcx) {
327 // FIXME: can't handle code with generics
331 let r = self.use_ecx(source_info, |this| {
332 this.ecx.value_to_scalar(ValTy { value: right.0, ty: right.1 })
334 if op == BinOp::Shr || op == BinOp::Shl {
335 let left_ty = left.ty(self.mir, self.tcx);
338 .layout_of(self.param_env.and(left_ty))
342 let right_size = self.tcx.layout_of(self.param_env.and(right.1)).unwrap().size;
343 if r.to_bits(right_size).ok().map_or(false, |b| b >= left_bits as u128) {
344 let source_scope_local_data = match self.mir.source_scope_local_data {
345 ClearCrossCrate::Set(ref data) => data,
346 ClearCrossCrate::Clear => return None,
348 let dir = if op == BinOp::Shr {
353 let node_id = source_scope_local_data[source_info.scope].lint_root;
355 ::rustc::lint::builtin::EXCEEDING_BITSHIFTS,
358 &format!("attempt to shift {} with overflow", dir));
362 let left = self.eval_operand(left, source_info)?;
363 let l = self.use_ecx(source_info, |this| {
364 this.ecx.value_to_scalar(ValTy { value: left.0, ty: left.1 })
366 trace!("const evaluating {:?} for {:?} and {:?}", op, left, right);
367 let (val, overflow) = self.use_ecx(source_info, |this| {
368 this.ecx.binary_op(op, l, left.1, r, right.1)
370 let val = if let Rvalue::CheckedBinaryOp(..) = *rvalue {
373 Scalar::from_bool(overflow),
377 use rustc::mir::interpret::EvalErrorKind;
378 let err = EvalErrorKind::Overflow(op).into();
379 let _: Option<()> = self.use_ecx(source_info, |_| Err(err));
384 Some((val, place_ty, span))
390 fn type_size_of<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
391 param_env: ty::ParamEnv<'tcx>,
392 ty: ty::Ty<'tcx>) -> Option<u64> {
393 tcx.layout_of(param_env.and(ty)).ok().map(|layout| layout.size.bytes())
396 struct CanConstProp {
397 can_const_prop: IndexVec<Local, bool>,
398 // false at the beginning, once set, there are not allowed to be any more assignments
399 found_assignment: IndexVec<Local, bool>,
403 /// returns true if `local` can be propagated
404 fn check(mir: &Mir) -> IndexVec<Local, bool> {
405 let mut cpv = CanConstProp {
406 can_const_prop: IndexVec::from_elem(true, &mir.local_decls),
407 found_assignment: IndexVec::from_elem(false, &mir.local_decls),
409 for (local, val) in cpv.can_const_prop.iter_enumerated_mut() {
410 // cannot use args at all
411 // cannot use locals because if x < y { y - x } else { x - y } would
413 // FIXME(oli-obk): lint variables until they are used in a condition
414 // FIXME(oli-obk): lint if return value is constant
415 *val = mir.local_kind(local) == LocalKind::Temp;
422 impl<'tcx> Visitor<'tcx> for CanConstProp {
426 context: PlaceContext<'tcx>,
429 use rustc::mir::visit::PlaceContext::*;
431 // Constants must have at most one write
432 // FIXME(oli-obk): we could be more powerful here, if the multiple writes
433 // only occur in independent execution paths
434 Store => if self.found_assignment[local] {
435 self.can_const_prop[local] = false;
437 self.found_assignment[local] = true
439 // Reading constants is allowed an arbitrary number of times
441 StorageDead | StorageLive |
445 _ => self.can_const_prop[local] = false,
450 impl<'b, 'a, 'tcx> Visitor<'tcx> for ConstPropagator<'b, 'a, 'tcx> {
453 constant: &Constant<'tcx>,
456 trace!("visit_constant: {:?}", constant);
457 self.super_constant(constant, location);
458 let source_info = *self.mir.source_info(location);
459 self.eval_constant(constant, source_info);
465 statement: &Statement<'tcx>,
468 trace!("visit_statement: {:?}", statement);
469 if let StatementKind::Assign(ref place, ref rval) = statement.kind {
471 .ty(&self.mir.local_decls, self.tcx)
473 if let Some(value) = self.const_prop(rval, place_ty, statement.source_info) {
474 if let Place::Local(local) = *place {
475 trace!("checking whether {:?} can be stored to {:?}", value, local);
476 if self.can_const_prop[local] {
477 trace!("storing {:?} to {:?}", value, local);
478 assert!(self.places[local].is_none());
479 self.places[local] = Some(value);
484 self.super_statement(block, statement, location);
487 fn visit_terminator_kind(
490 kind: &TerminatorKind<'tcx>,
493 self.super_terminator_kind(block, kind, location);
494 let source_info = *self.mir.source_info(location);
495 if let TerminatorKind::Assert { expected, msg, cond, .. } = kind {
496 if let Some(value) = self.eval_operand(cond, source_info) {
497 trace!("assertion on {:?} should be {:?}", value, expected);
498 if Value::Scalar(Scalar::from_bool(*expected)) != value.0 {
499 // poison all places this operand references so that further code
500 // doesn't use the invalid value
502 Operand::Move(ref place) | Operand::Copy(ref place) => {
503 let mut place = place;
504 while let Place::Projection(ref proj) = *place {
507 if let Place::Local(local) = *place {
508 self.places[local] = None;
511 Operand::Constant(_) => {}
513 let span = self.mir[block]
522 .as_local_node_id(self.source.def_id)
523 .expect("some part of a failing const eval must be local");
524 use rustc::mir::interpret::EvalErrorKind::*;
525 let msg = match msg {
529 RemainderByZero => msg.description().to_owned(),
530 BoundsCheck { ref len, ref index } => {
532 .eval_operand(len, source_info)
533 .expect("len must be const");
534 let len = match len.0 {
535 Value::Scalar(Scalar::Bits { bits, ..}) => bits,
536 _ => bug!("const len not primitive: {:?}", len),
539 .eval_operand(index, source_info)
540 .expect("index must be const");
541 let index = match index.0 {
542 Value::Scalar(Scalar::Bits { bits, .. }) => bits,
543 _ => bug!("const index not primitive: {:?}", index),
546 "index out of bounds: \
547 the len is {} but the index is {}",
552 // Need proper const propagator for these
556 ::rustc::lint::builtin::CONST_ERR,