]> git.lizzy.rs Git - rust.git/blob - src/librustc_mir/transform/const_prop.rs
Rollup merge of #51099 - Crazycolorz5:expectedcloseparen, r=estebank
[rust.git] / src / librustc_mir / transform / const_prop.rs
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.
4 //
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.
10
11 //! Propagates constants for early reporting of statically known
12 //! assertion failures
13
14
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,
34 };
35
36 pub struct ConstProp;
37
38 impl MirPass for ConstProp {
39     fn run_pass<'a, 'tcx>(&self,
40                           tcx: TyCtxt<'a, 'tcx, 'tcx>,
41                           source: MirSource,
42                           mir: &mut Mir<'tcx>) {
43         // will be evaluated by miri and produce its errors there
44         if source.promoted.is_some() {
45             return;
46         }
47         match tcx.describe_def(source.def_id) {
48             // skip statics because they'll be evaluated by miri anyway
49             Some(Def::Static(..)) => return,
50             _ => {},
51         }
52         trace!("ConstProp starting for {:?}", source.def_id);
53
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);
60
61         trace!("ConstProp done for {:?}", source.def_id);
62     }
63 }
64
65 type Const<'tcx> = (Value, ty::Ty<'tcx>, Span);
66
67 /// Finds optimization opportunities on the MIR.
68 struct ConstPropagator<'b, 'a, 'tcx:'a+'b> {
69     ecx: EvalContext<'a, 'b, 'tcx, CompileTimeEvaluator>,
70     mir: &'b Mir<'tcx>,
71     tcx: TyCtxt<'a, 'tcx, 'tcx>,
72     source: MirSource,
73     places: IndexVec<Local, Option<Const<'tcx>>>,
74     can_const_prop: IndexVec<Local, bool>,
75     param_env: ParamEnv<'tcx>,
76 }
77
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>>;
81
82     fn layout_of(self, ty: ty::Ty<'tcx>) -> Self::TyLayout {
83         self.tcx.layout_of(self.param_env.and(ty))
84     }
85 }
86
87 impl<'a, 'b, 'tcx> HasDataLayout for &'a ConstPropagator<'a, 'b, 'tcx> {
88     #[inline]
89     fn data_layout(&self) -> &TargetDataLayout {
90         &self.tcx.data_layout
91     }
92 }
93
94 impl<'a, 'b, 'tcx> HasTyCtxt<'tcx> for &'a ConstPropagator<'a, 'b, 'tcx> {
95     #[inline]
96     fn tcx<'c>(&'c self) -> TyCtxt<'c, 'tcx, 'tcx> {
97         self.tcx
98     }
99 }
100
101 impl<'b, 'a, 'tcx:'b> ConstPropagator<'b, 'a, 'tcx> {
102     fn new(
103         mir: &'b Mir<'tcx>,
104         tcx: TyCtxt<'a, 'tcx, 'tcx>,
105         source: MirSource,
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();
111         ConstPropagator {
112             ecx,
113             mir,
114             tcx,
115             source,
116             param_env,
117             can_const_prop: CanConstProp::check(mir),
118             places: IndexVec::from_elem(None, &mir.local_decls),
119         }
120     }
121
122     fn use_ecx<F, T>(
123         &mut self,
124         source_info: SourceInfo,
125         f: F
126     ) -> Option<T>
127     where
128         F: FnOnce(&mut Self) -> EvalResult<'tcx, T>,
129     {
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() {
136                     return None;
137                 }
138                 ivs[source_info.scope].lint_root
139             },
140             ClearCrossCrate::Clear => return None,
141         };
142         let r = match f(self) {
143             Ok(val) => Some(val),
144             Err(err) => {
145                 let (frames, span) = self.ecx.generate_stacktrace(None);
146                 let err = ConstEvalErr {
147                     span,
148                     kind: ErrKind::Miri(err, frames).into(),
149                 };
150                 err.report_as_lint(
151                     self.ecx.tcx,
152                     "this expression will panic at runtime",
153                     lint_root,
154                 );
155                 None
156             },
157         };
158         self.ecx.tcx.span = DUMMY_SP;
159         r
160     }
161
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)) {
164             Ok(val) => val,
165             Err(err) => {
166                 err.report_as_error(
167                     self.tcx.at(err.span),
168                     "constant evaluation error",
169                 );
170                 return None;
171             },
172         };
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))?
176             },
177             _ => bug!("eval produced: {:?}", value),
178         };
179         let val = (val, value.ty, source_info.span);
180         trace!("evaluated {:?} to {:?}", cid, val);
181         Some(val)
182     }
183
184     fn eval_constant(
185         &mut self,
186         c: &Constant<'tcx>,
187         source_info: SourceInfo,
188     ) -> Option<Const<'tcx>> {
189         match c.literal {
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)
194                     })?;
195                     Some((v, value.ty, c.span))
196                 },
197                 ConstVal::Unevaluated(did, substs) => {
198                     let instance = Instance::resolve(
199                         self.tcx,
200                         self.param_env,
201                         did,
202                         substs,
203                     )?;
204                     let cid = GlobalId {
205                         instance,
206                         promoted: None,
207                     };
208                     self.const_eval(cid, source_info)
209                 },
210             },
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
216                     return None;
217                 }
218                 let substs = Substs::identity_for_item(self.tcx, self.source.def_id);
219                 let instance = Instance::new(self.source.def_id, substs);
220                 let cid = GlobalId {
221                     instance,
222                     promoted: Some(index),
223                 };
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)
228                 })?;
229                 let val = (value, ty, c.span);
230                 trace!("evaluated {:?} to {:?}", c, val);
231                 Some(val)
232             }
233         }
234     }
235
236     fn eval_place(&mut self, place: &Place<'tcx>, source_info: SourceInfo) -> Option<Const<'tcx>> {
237         match *place {
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)
245                     })?;
246                     Some((valty.value, valty.ty, span))
247                 },
248                 _ => None,
249             },
250             _ => None,
251         }
252     }
253
254     fn eval_operand(&mut self, op: &Operand<'tcx>, source_info: SourceInfo) -> Option<Const<'tcx>> {
255         match *op {
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),
259         }
260     }
261
262     fn const_prop(
263         &mut self,
264         rvalue: &Rvalue<'tcx>,
265         place_ty: ty::Ty<'tcx>,
266         source_info: SourceInfo,
267     ) -> Option<Const<'tcx>> {
268         let span = source_info.span;
269         match *rvalue {
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)
274             },
275             Rvalue::Use(ref op) => {
276                 self.eval_operand(op, source_info)
277             },
278             Rvalue::Repeat(..) |
279             Rvalue::Ref(..) |
280             Rvalue::Cast(..) |
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 {
290                         bits: n as u128,
291                         defined: self.tcx.data_layout.pointer_size.bits() as u8,
292                     }),
293                     self.tcx.types.usize,
294                     span,
295                 ))
296             }
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)
300                 } else {
301                     self.source.def_id
302                 };
303                 let generics = self.tcx.generics_of(def_id);
304                 if generics.requires_monomorphization(self.tcx) {
305                     // FIXME: can't handle code with generics
306                     return None;
307                 }
308
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 })
312                 })?;
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))
315             }
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)
322                 } else {
323                     self.source.def_id
324                 };
325                 let generics = self.tcx.generics_of(def_id);
326                 if generics.requires_monomorphization(self.tcx) {
327                     // FIXME: can't handle code with generics
328                     return None;
329                 }
330
331                 let r = self.use_ecx(source_info, |this| {
332                     this.ecx.value_to_scalar(ValTy { value: right.0, ty: right.1 })
333                 })?;
334                 if op == BinOp::Shr || op == BinOp::Shl {
335                     let left_ty = left.ty(self.mir, self.tcx);
336                     let left_bits = self
337                         .tcx
338                         .layout_of(self.param_env.and(left_ty))
339                         .unwrap()
340                         .size
341                         .bits();
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,
347                         };
348                         let dir = if op == BinOp::Shr {
349                             "right"
350                         } else {
351                             "left"
352                         };
353                         let node_id = source_scope_local_data[source_info.scope].lint_root;
354                         self.tcx.lint_node(
355                             ::rustc::lint::builtin::EXCEEDING_BITSHIFTS,
356                             node_id,
357                             span,
358                             &format!("attempt to shift {} with overflow", dir));
359                         return None;
360                     }
361                 }
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 })
365                 })?;
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)
369                 })?;
370                 let val = if let Rvalue::CheckedBinaryOp(..) = *rvalue {
371                     Value::ScalarPair(
372                         val,
373                         Scalar::from_bool(overflow),
374                     )
375                 } else {
376                     if overflow {
377                         use rustc::mir::interpret::EvalErrorKind;
378                         let err = EvalErrorKind::Overflow(op).into();
379                         let _: Option<()> = self.use_ecx(source_info, |_| Err(err));
380                         return None;
381                     }
382                     Value::Scalar(val)
383                 };
384                 Some((val, place_ty, span))
385             },
386         }
387     }
388 }
389
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())
394 }
395
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>,
400 }
401
402 impl CanConstProp {
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),
408         };
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
412             //        lint for x != y
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;
416         }
417         cpv.visit_mir(mir);
418         cpv.can_const_prop
419     }
420 }
421
422 impl<'tcx> Visitor<'tcx> for CanConstProp {
423     fn visit_local(
424         &mut self,
425         &local: &Local,
426         context: PlaceContext<'tcx>,
427         _: Location,
428     ) {
429         use rustc::mir::visit::PlaceContext::*;
430         match context {
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;
436             } else {
437                 self.found_assignment[local] = true
438             },
439             // Reading constants is allowed an arbitrary number of times
440             Copy | Move |
441             StorageDead | StorageLive |
442             Validate |
443             Projection(_) |
444             Inspect => {},
445             _ => self.can_const_prop[local] = false,
446         }
447     }
448 }
449
450 impl<'b, 'a, 'tcx> Visitor<'tcx> for ConstPropagator<'b, 'a, 'tcx> {
451     fn visit_constant(
452         &mut self,
453         constant: &Constant<'tcx>,
454         location: Location,
455     ) {
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);
460     }
461
462     fn visit_statement(
463         &mut self,
464         block: BasicBlock,
465         statement: &Statement<'tcx>,
466         location: Location,
467     ) {
468         trace!("visit_statement: {:?}", statement);
469         if let StatementKind::Assign(ref place, ref rval) = statement.kind {
470             let place_ty = place
471                 .ty(&self.mir.local_decls, self.tcx)
472                 .to_ty(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);
480                     }
481                 }
482             }
483         }
484         self.super_statement(block, statement, location);
485     }
486
487     fn visit_terminator_kind(
488         &mut self,
489         block: BasicBlock,
490         kind: &TerminatorKind<'tcx>,
491         location: Location,
492     ) {
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
501                     match cond {
502                         Operand::Move(ref place) | Operand::Copy(ref place) => {
503                             let mut place = place;
504                             while let Place::Projection(ref proj) = *place {
505                                 place = &proj.base;
506                             }
507                             if let Place::Local(local) = *place {
508                                 self.places[local] = None;
509                             }
510                         },
511                         Operand::Constant(_) => {}
512                     }
513                     let span = self.mir[block]
514                         .terminator
515                         .as_ref()
516                         .unwrap()
517                         .source_info
518                         .span;
519                     let node_id = self
520                         .tcx
521                         .hir
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 {
526                         Overflow(_) |
527                         OverflowNeg |
528                         DivisionByZero |
529                         RemainderByZero => msg.description().to_owned(),
530                         BoundsCheck { ref len, ref index } => {
531                             let len = self
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),
537                             };
538                             let index = self
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),
544                             };
545                             format!(
546                                 "index out of bounds: \
547                                 the len is {} but the index is {}",
548                                 len,
549                                 index,
550                             )
551                         },
552                         // Need proper const propagator for these
553                         _ => return,
554                     };
555                     self.tcx.lint_node(
556                         ::rustc::lint::builtin::CONST_ERR,
557                         node_id,
558                         span,
559                         &msg,
560                     );
561                 }
562             }
563         }
564     }
565 }