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::mir::interpret::{ConstVal, ConstEvalErr};
  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                     error: err,
 149                     stacktrace: frames,
 150                 };
 151                 err.report_as_lint(
 152                     self.ecx.tcx,
 153                     "this expression will panic at runtime",
 154                     lint_root,
 155                 );
 156                 None
 157             },
 158         };
 159         self.ecx.tcx.span = DUMMY_SP;
 160         r
 161     }
 162
 163     fn const_eval(&mut self, cid: GlobalId<'tcx>, source_info: SourceInfo) -> Option<Const<'tcx>> {
 164         let value = match self.tcx.const_eval(self.param_env.and(cid)) {
 165             Ok(val) => val,
 166             Err(err) => {
 167                 err.report_as_error(
 168                     self.tcx.at(err.span),
 169                     "constant evaluation error",
 170                 );
 171                 return None;
 172             },
 173         };
 174         let val = match value.val {
 175             ConstVal::Value(v) => {
 176                 self.use_ecx(source_info, |this| this.ecx.const_value_to_value(v, value.ty))?
 177             },
 178             _ => bug!("eval produced: {:?}", value),
 179         };
 180         let val = (val, value.ty, source_info.span);
 181         trace!("evaluated {:?} to {:?}", cid, val);
 182         Some(val)
 183     }
 184
 185     fn eval_constant(
 186         &mut self,
 187         c: &Constant<'tcx>,
 188         source_info: SourceInfo,
 189     ) -> Option<Const<'tcx>> {
 190         match c.literal {
 191             Literal::Value { value } => match value.val {
 192                 ConstVal::Value(v) => {
 193                     let v = self.use_ecx(source_info, |this| {
 194                         this.ecx.const_value_to_value(v, value.ty)
 195                     })?;
 196                     Some((v, value.ty, c.span))
 197                 },
 198                 ConstVal::Unevaluated(did, substs) => {
 199                     let instance = Instance::resolve(
 200                         self.tcx,
 201                         self.param_env,
 202                         did,
 203                         substs,
 204                     )?;
 205                     let cid = GlobalId {
 206                         instance,
 207                         promoted: None,
 208                     };
 209                     self.const_eval(cid, source_info)
 210                 },
 211             },
 212             // evaluate the promoted and replace the constant with the evaluated result
 213             Literal::Promoted { index } => {
 214                 let generics = self.tcx.generics_of(self.source.def_id);
 215                 if generics.requires_monomorphization(self.tcx) {
 216                     // FIXME: can't handle code with generics
 217                     return None;
 218                 }
 219                 let substs = Substs::identity_for_item(self.tcx, self.source.def_id);
 220                 let instance = Instance::new(self.source.def_id, substs);
 221                 let cid = GlobalId {
 222                     instance,
 223                     promoted: Some(index),
 224                 };
 225                 // cannot use `const_eval` here, because that would require having the MIR
 226                 // for the current function available, but we're producing said MIR right now
 227                 let (value, _, ty) = self.use_ecx(source_info, |this| {
 228                     eval_promoted(&mut this.ecx, cid, this.mir, this.param_env)
 229                 })?;
 230                 let val = (value, ty, c.span);
 231                 trace!("evaluated {:?} to {:?}", c, val);
 232                 Some(val)
 233             }
 234         }
 235     }
 236
 237     fn eval_place(&mut self, place: &Place<'tcx>, source_info: SourceInfo) -> Option<Const<'tcx>> {
 238         match *place {
 239             Place::Local(loc) => self.places[loc].clone(),
 240             Place::Projection(ref proj) => match proj.elem {
 241                 ProjectionElem::Field(field, _) => {
 242                     trace!("field proj on {:?}", proj.base);
 243                     let (base, ty, span) = self.eval_place(&proj.base, source_info)?;
 244                     let valty = self.use_ecx(source_info, |this| {
 245                         this.ecx.read_field(base, None, field, ty)
 246                     })?;
 247                     Some((valty.value, valty.ty, span))
 248                 },
 249                 _ => None,
 250             },
 251             _ => None,
 252         }
 253     }
 254
 255     fn eval_operand(&mut self, op: &Operand<'tcx>, source_info: SourceInfo) -> Option<Const<'tcx>> {
 256         match *op {
 257             Operand::Constant(ref c) => self.eval_constant(c, source_info),
 258             | Operand::Move(ref place)
 259             | Operand::Copy(ref place) => self.eval_place(place, source_info),
 260         }
 261     }
 262
 263     fn const_prop(
 264         &mut self,
 265         rvalue: &Rvalue<'tcx>,
 266         place_ty: ty::Ty<'tcx>,
 267         source_info: SourceInfo,
 268     ) -> Option<Const<'tcx>> {
 269         let span = source_info.span;
 270         match *rvalue {
 271             // This branch exists for the sanity type check
 272             Rvalue::Use(Operand::Constant(ref c)) => {
 273                 assert_eq!(c.ty, place_ty);
 274                 self.eval_constant(c, source_info)
 275             },
 276             Rvalue::Use(ref op) => {
 277                 self.eval_operand(op, source_info)
 278             },
 279             Rvalue::Repeat(..) |
 280             Rvalue::Ref(..) |
 281             Rvalue::Cast(..) |
 282             Rvalue::Aggregate(..) |
 283             Rvalue::NullaryOp(NullOp::Box, _) |
 284             Rvalue::Discriminant(..) => None,
 285             // FIXME(oli-obk): evaluate static/constant slice lengths
 286             Rvalue::Len(_) => None,
 287             Rvalue::NullaryOp(NullOp::SizeOf, ty) => {
 288                 let param_env = self.tcx.param_env(self.source.def_id);
 289                 type_size_of(self.tcx, param_env, ty).map(|n| (
 290                     Value::Scalar(Scalar::Bits {
 291                         bits: n as u128,
 292                         defined: self.tcx.data_layout.pointer_size.bits() as u8,
 293                     }),
 294                     self.tcx.types.usize,
 295                     span,
 296                 ))
 297             }
 298             Rvalue::UnaryOp(op, ref arg) => {
 299                 let def_id = if self.tcx.is_closure(self.source.def_id) {
 300                     self.tcx.closure_base_def_id(self.source.def_id)
 301                 } else {
 302                     self.source.def_id
 303                 };
 304                 let generics = self.tcx.generics_of(def_id);
 305                 if generics.requires_monomorphization(self.tcx) {
 306                     // FIXME: can't handle code with generics
 307                     return None;
 308                 }
 309
 310                 let val = self.eval_operand(arg, source_info)?;
 311                 let prim = self.use_ecx(source_info, |this| {
 312                     this.ecx.value_to_scalar(ValTy { value: val.0, ty: val.1 })
 313                 })?;
 314                 let val = self.use_ecx(source_info, |this| this.ecx.unary_op(op, prim, val.1))?;
 315                 Some((Value::Scalar(val), place_ty, span))
 316             }
 317             Rvalue::CheckedBinaryOp(op, ref left, ref right) |
 318             Rvalue::BinaryOp(op, ref left, ref right) => {
 319                 trace!("rvalue binop {:?} for {:?} and {:?}", op, left, right);
 320                 let right = self.eval_operand(right, source_info)?;
 321                 let def_id = if self.tcx.is_closure(self.source.def_id) {
 322                     self.tcx.closure_base_def_id(self.source.def_id)
 323                 } else {
 324                     self.source.def_id
 325                 };
 326                 let generics = self.tcx.generics_of(def_id);
 327                 if generics.requires_monomorphization(self.tcx) {
 328                     // FIXME: can't handle code with generics
 329                     return None;
 330                 }
 331
 332                 let r = self.use_ecx(source_info, |this| {
 333                     this.ecx.value_to_scalar(ValTy { value: right.0, ty: right.1 })
 334                 })?;
 335                 if op == BinOp::Shr || op == BinOp::Shl {
 336                     let left_ty = left.ty(self.mir, self.tcx);
 337                     let left_bits = self
 338                         .tcx
 339                         .layout_of(self.param_env.and(left_ty))
 340                         .unwrap()
 341                         .size
 342                         .bits();
 343                     let right_size = self.tcx.layout_of(self.param_env.and(right.1)).unwrap().size;
 344                     if r.to_bits(right_size).ok().map_or(false, |b| b >= left_bits as u128) {
 345                         let source_scope_local_data = match self.mir.source_scope_local_data {
 346                             ClearCrossCrate::Set(ref data) => data,
 347                             ClearCrossCrate::Clear => return None,
 348                         };
 349                         let dir = if op == BinOp::Shr {
 350                             "right"
 351                         } else {
 352                             "left"
 353                         };
 354                         let node_id = source_scope_local_data[source_info.scope].lint_root;
 355                         self.tcx.lint_node(
 356                             ::rustc::lint::builtin::EXCEEDING_BITSHIFTS,
 357                             node_id,
 358                             span,
 359                             &format!("attempt to shift {} with overflow", dir));
 360                         return None;
 361                     }
 362                 }
 363                 let left = self.eval_operand(left, source_info)?;
 364                 let l = self.use_ecx(source_info, |this| {
 365                     this.ecx.value_to_scalar(ValTy { value: left.0, ty: left.1 })
 366                 })?;
 367                 trace!("const evaluating {:?} for {:?} and {:?}", op, left, right);
 368                 let (val, overflow) = self.use_ecx(source_info, |this| {
 369                     this.ecx.binary_op(op, l, left.1, r, right.1)
 370                 })?;
 371                 let val = if let Rvalue::CheckedBinaryOp(..) = *rvalue {
 372                     Value::ScalarPair(
 373                         val,
 374                         Scalar::from_bool(overflow),
 375                     )
 376                 } else {
 377                     if overflow {
 378                         use rustc::mir::interpret::EvalErrorKind;
 379                         let err = EvalErrorKind::Overflow(op).into();
 380                         let _: Option<()> = self.use_ecx(source_info, |_| Err(err));
 381                         return None;
 382                     }
 383                     Value::Scalar(val)
 384                 };
 385                 Some((val, place_ty, span))
 386             },
 387         }
 388     }
 389 }
 390
 391 fn type_size_of<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 392                           param_env: ty::ParamEnv<'tcx>,
 393                           ty: ty::Ty<'tcx>) -> Option<u64> {
 394     tcx.layout_of(param_env.and(ty)).ok().map(|layout| layout.size.bytes())
 395 }
 396
 397 struct CanConstProp {
 398     can_const_prop: IndexVec<Local, bool>,
 399     // false at the beginning, once set, there are not allowed to be any more assignments
 400     found_assignment: IndexVec<Local, bool>,
 401 }
 402
 403 impl CanConstProp {
 404     /// returns true if `local` can be propagated
 405     fn check(mir: &Mir) -> IndexVec<Local, bool> {
 406         let mut cpv = CanConstProp {
 407             can_const_prop: IndexVec::from_elem(true, &mir.local_decls),
 408             found_assignment: IndexVec::from_elem(false, &mir.local_decls),
 409         };
 410         for (local, val) in cpv.can_const_prop.iter_enumerated_mut() {
 411             // cannot use args at all
 412             // cannot use locals because if x < y { y - x } else { x - y } would
 413             //        lint for x != y
 414             // FIXME(oli-obk): lint variables until they are used in a condition
 415             // FIXME(oli-obk): lint if return value is constant
 416             *val = mir.local_kind(local) == LocalKind::Temp;
 417         }
 418         cpv.visit_mir(mir);
 419         cpv.can_const_prop
 420     }
 421 }
 422
 423 impl<'tcx> Visitor<'tcx> for CanConstProp {
 424     fn visit_local(
 425         &mut self,
 426         &local: &Local,
 427         context: PlaceContext<'tcx>,
 428         _: Location,
 429     ) {
 430         use rustc::mir::visit::PlaceContext::*;
 431         match context {
 432             // Constants must have at most one write
 433             // FIXME(oli-obk): we could be more powerful here, if the multiple writes
 434             // only occur in independent execution paths
 435             Store => if self.found_assignment[local] {
 436                 self.can_const_prop[local] = false;
 437             } else {
 438                 self.found_assignment[local] = true
 439             },
 440             // Reading constants is allowed an arbitrary number of times
 441             Copy | Move |
 442             StorageDead | StorageLive |
 443             Validate |
 444             Projection(_) |
 445             Inspect => {},
 446             _ => self.can_const_prop[local] = false,
 447         }
 448     }
 449 }
 450
 451 impl<'b, 'a, 'tcx> Visitor<'tcx> for ConstPropagator<'b, 'a, 'tcx> {
 452     fn visit_constant(
 453         &mut self,
 454         constant: &Constant<'tcx>,
 455         location: Location,
 456     ) {
 457         trace!("visit_constant: {:?}", constant);
 458         self.super_constant(constant, location);
 459         let source_info = *self.mir.source_info(location);
 460         self.eval_constant(constant, source_info);
 461     }
 462
 463     fn visit_statement(
 464         &mut self,
 465         block: BasicBlock,
 466         statement: &Statement<'tcx>,
 467         location: Location,
 468     ) {
 469         trace!("visit_statement: {:?}", statement);
 470         if let StatementKind::Assign(ref place, ref rval) = statement.kind {
 471             let place_ty = place
 472                 .ty(&self.mir.local_decls, self.tcx)
 473                 .to_ty(self.tcx);
 474             if let Some(value) = self.const_prop(rval, place_ty, statement.source_info) {
 475                 if let Place::Local(local) = *place {
 476                     trace!("checking whether {:?} can be stored to {:?}", value, local);
 477                     if self.can_const_prop[local] {
 478                         trace!("storing {:?} to {:?}", value, local);
 479                         assert!(self.places[local].is_none());
 480                         self.places[local] = Some(value);
 481                     }
 482                 }
 483             }
 484         }
 485         self.super_statement(block, statement, location);
 486     }
 487
 488     fn visit_terminator_kind(
 489         &mut self,
 490         block: BasicBlock,
 491         kind: &TerminatorKind<'tcx>,
 492         location: Location,
 493     ) {
 494         self.super_terminator_kind(block, kind, location);
 495         let source_info = *self.mir.source_info(location);
 496         if let TerminatorKind::Assert { expected, msg, cond, .. } = kind {
 497             if let Some(value) = self.eval_operand(cond, source_info) {
 498                 trace!("assertion on {:?} should be {:?}", value, expected);
 499                 if Value::Scalar(Scalar::from_bool(*expected)) != value.0 {
 500                     // poison all places this operand references so that further code
 501                     // doesn't use the invalid value
 502                     match cond {
 503                         Operand::Move(ref place) | Operand::Copy(ref place) => {
 504                             let mut place = place;
 505                             while let Place::Projection(ref proj) = *place {
 506                                 place = &proj.base;
 507                             }
 508                             if let Place::Local(local) = *place {
 509                                 self.places[local] = None;
 510                             }
 511                         },
 512                         Operand::Constant(_) => {}
 513                     }
 514                     let span = self.mir[block]
 515                         .terminator
 516                         .as_ref()
 517                         .unwrap()
 518                         .source_info
 519                         .span;
 520                     let node_id = self
 521                         .tcx
 522                         .hir
 523                         .as_local_node_id(self.source.def_id)
 524                         .expect("some part of a failing const eval must be local");
 525                     use rustc::mir::interpret::EvalErrorKind::*;
 526                     let msg = match msg {
 527                         Overflow(_) |
 528                         OverflowNeg |
 529                         DivisionByZero |
 530                         RemainderByZero => msg.description().to_owned(),
 531                         BoundsCheck { ref len, ref index } => {
 532                             let len = self
 533                                 .eval_operand(len, source_info)
 534                                 .expect("len must be const");
 535                             let len = match len.0 {
 536                                 Value::Scalar(Scalar::Bits { bits, ..}) => bits,
 537                                 _ => bug!("const len not primitive: {:?}", len),
 538                             };
 539                             let index = self
 540                                 .eval_operand(index, source_info)
 541                                 .expect("index must be const");
 542                             let index = match index.0 {
 543                                 Value::Scalar(Scalar::Bits { bits, .. }) => bits,
 544                                 _ => bug!("const index not primitive: {:?}", index),
 545                             };
 546                             format!(
 547                                 "index out of bounds: \
 548                                 the len is {} but the index is {}",
 549                                 len,
 550                                 index,
 551                             )
 552                         },
 553                         // Need proper const propagator for these
 554                         _ => return,
 555                     };
 556                     self.tcx.lint_node(
 557                         ::rustc::lint::builtin::CONST_ERR,
 558                         node_id,
 559                         span,
 560                         &msg,
 561                     );
 562                 }
 563             }
 564         }
 565     }
 566 }