X-Git-Url: https://git.lizzy.rs/?a=blobdiff_plain;f=compiler%2Frustc_mir_transform%2Fsrc%2Fdataflow_const_prop.rs;h=e9027387413cfe1e97425a7992e74e33384fbfb3;hb=ea23585c91a3bbe38162b967ecf6838b50ae369a;hp=1cc4201a94982f5ee66a32df557e2b5704f8c560;hpb=fe84bbf844cec89db7726f835517151e08ff2597;p=rust.git diff --git a/compiler/rustc_mir_transform/src/dataflow_const_prop.rs b/compiler/rustc_mir_transform/src/dataflow_const_prop.rs index 1cc4201a949..e9027387413 100644 --- a/compiler/rustc_mir_transform/src/dataflow_const_prop.rs +++ b/compiler/rustc_mir_transform/src/dataflow_const_prop.rs @@ -1,37 +1,62 @@ +//! A constant propagation optimization pass based on dataflow analysis. +//! +//! Currently, this pass only propagates scalar values. + use rustc_const_eval::interpret::{ConstValue, ImmTy, Immediate, InterpCx, Scalar}; use rustc_data_structures::fx::FxHashMap; use rustc_middle::mir::visit::{MutVisitor, Visitor}; use rustc_middle::mir::*; -use rustc_middle::ty::{self, ScalarInt, Ty, TyCtxt}; -use rustc_mir_dataflow::value_analysis::{ - Map, ProjElem, State, ValueAnalysis, ValueOrPlace, ValueOrPlaceOrRef, -}; +use rustc_middle::ty::{self, Ty, TyCtxt}; +use rustc_mir_dataflow::value_analysis::{Map, State, TrackElem, ValueAnalysis, ValueOrPlace}; use rustc_mir_dataflow::{lattice::FlatSet, Analysis, ResultsVisitor, SwitchIntEdgeEffects}; use rustc_span::DUMMY_SP; use crate::MirPass; +// These constants are somewhat random guesses and have not been optimized. +// If `tcx.sess.mir_opt_level() >= 4`, we ignore the limits (this can become very expensive). +const BLOCK_LIMIT: usize = 100; +const PLACE_LIMIT: usize = 100; + pub struct DataflowConstProp; impl<'tcx> MirPass<'tcx> for DataflowConstProp { fn is_enabled(&self, sess: &rustc_session::Session) -> bool { - // Choose different minimum level? - sess.mir_opt_level() >= 4 + sess.mir_opt_level() >= 3 } + #[instrument(skip_all level = "debug")] fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) { + if tcx.sess.mir_opt_level() < 4 && body.basic_blocks.len() > BLOCK_LIMIT { + debug!("aborted dataflow const prop due too many basic blocks"); + return; + } + // Decide which places to track during the analysis. - let mut map = Map::new(); - map.register_with_filter(tcx, body, 3, |ty| ty.is_scalar() && !ty.is_unsafe_ptr()); + let map = Map::from_filter(tcx, body, Ty::is_scalar); + + // We want to have a somewhat linear runtime w.r.t. the number of statements/terminators. + // Let's call this number `n`. Dataflow analysis has `O(h*n)` transfer function + // applications, where `h` is the height of the lattice. Because the height of our lattice + // is linear w.r.t. the number of tracked places, this is `O(tracked_places * n)`. However, + // because every transfer function application could traverse the whole map, this becomes + // `O(num_nodes * tracked_places * n)` in terms of time complexity. Since the number of + // map nodes is strongly correlated to the number of tracked places, this becomes more or + // less `O(n)` if we place a constant limit on the number of tracked places. + if tcx.sess.mir_opt_level() < 4 && map.tracked_places() > PLACE_LIMIT { + debug!("aborted dataflow const prop due to too many tracked places"); + return; + } // Perform the actual dataflow analysis. let analysis = ConstAnalysis::new(tcx, body, map); - let results = analysis.wrap().into_engine(tcx, body).iterate_to_fixpoint(); + let results = debug_span!("analyze") + .in_scope(|| analysis.wrap().into_engine(tcx, body).iterate_to_fixpoint()); // Collect results and patch the body afterwards. let mut visitor = CollectAndPatch::new(tcx, &results.analysis.0.map); - results.visit_reachable_with(body, &mut visitor); - visitor.visit_body(body); + debug_span!("collect").in_scope(|| results.visit_reachable_with(body, &mut visitor)); + debug_span!("patch").in_scope(|| visitor.visit_body(body)); } } @@ -43,7 +68,7 @@ struct ConstAnalysis<'tcx> { } impl<'tcx> ValueAnalysis<'tcx> for ConstAnalysis<'tcx> { - type Value = FlatSet>; + type Value = FlatSet>; const NAME: &'static str = "ConstAnalysis"; @@ -66,23 +91,33 @@ fn handle_assign( state.flood_idx(target, self.map()); } - let value_target = target.and_then(|target| { - self.map().apply_elem(target, ProjElem::Field(0_u32.into())) - }); - let overflow_target = target.and_then(|target| { - self.map().apply_elem(target, ProjElem::Field(1_u32.into())) - }); + let value_target = target + .and_then(|target| self.map().apply(target, TrackElem::Field(0_u32.into()))); + let overflow_target = target + .and_then(|target| self.map().apply(target, TrackElem::Field(1_u32.into()))); if value_target.is_some() || overflow_target.is_some() { let (val, overflow) = self.binary_op(state, *op, left, right); if let Some(value_target) = value_target { - state.assign_idx(value_target, ValueOrPlaceOrRef::Value(val), self.map()); + state.assign_idx(value_target, ValueOrPlace::Value(val), self.map()); } if let Some(overflow_target) = overflow_target { + let overflow = match overflow { + FlatSet::Top => FlatSet::Top, + FlatSet::Elem(overflow) => { + if overflow { + // Overflow cannot be reliably propagated. See: https://github.com/rust-lang/rust/pull/101168#issuecomment-1288091446 + FlatSet::Top + } else { + self.wrap_scalar(Scalar::from_bool(false), self.tcx.types.bool) + } + } + FlatSet::Bottom => FlatSet::Bottom, + }; state.assign_idx( overflow_target, - ValueOrPlaceOrRef::Value(overflow), + ValueOrPlace::Value(overflow), self.map(), ); } @@ -96,32 +131,42 @@ fn handle_rvalue( &self, rvalue: &Rvalue<'tcx>, state: &mut State, - ) -> ValueOrPlaceOrRef { + ) -> ValueOrPlace { match rvalue { - Rvalue::Cast(CastKind::Misc, operand, ty) => { - let operand = self.eval_operand(operand, state); - match operand { - FlatSet::Elem(operand) => self - .ecx - .misc_cast(&operand, *ty) - .map(|result| ValueOrPlaceOrRef::Value(self.wrap_immediate(result, *ty))) - .unwrap_or(ValueOrPlaceOrRef::Unknown), - _ => ValueOrPlaceOrRef::Unknown, + Rvalue::Cast( + kind @ (CastKind::IntToInt + | CastKind::FloatToInt + | CastKind::FloatToFloat + | CastKind::IntToFloat), + operand, + ty, + ) => match self.eval_operand(operand, state) { + FlatSet::Elem(op) => match kind { + CastKind::IntToInt | CastKind::IntToFloat => { + self.ecx.int_to_int_or_float(&op, *ty) + } + CastKind::FloatToInt | CastKind::FloatToFloat => { + self.ecx.float_to_float_or_int(&op, *ty) + } + _ => unreachable!(), } - } + .map(|result| ValueOrPlace::Value(self.wrap_immediate(result, *ty))) + .unwrap_or(ValueOrPlace::top()), + _ => ValueOrPlace::top(), + }, Rvalue::BinaryOp(op, box (left, right)) => { + // Overflows must be ignored here. let (val, _overflow) = self.binary_op(state, *op, left, right); - // FIXME: Just ignore overflow here? - ValueOrPlaceOrRef::Value(val) + ValueOrPlace::Value(val) } Rvalue::UnaryOp(op, operand) => match self.eval_operand(operand, state) { FlatSet::Elem(value) => self .ecx .unary_op(*op, &value) - .map(|val| ValueOrPlaceOrRef::Value(self.wrap_immty(val))) - .unwrap_or(ValueOrPlaceOrRef::Value(FlatSet::Top)), - FlatSet::Bottom => ValueOrPlaceOrRef::Value(FlatSet::Bottom), - FlatSet::Top => ValueOrPlaceOrRef::Value(FlatSet::Top), + .map(|val| ValueOrPlace::Value(self.wrap_immty(val))) + .unwrap_or(ValueOrPlace::Value(FlatSet::Top)), + FlatSet::Bottom => ValueOrPlace::Value(FlatSet::Bottom), + FlatSet::Top => ValueOrPlace::Value(FlatSet::Top), }, _ => self.super_rvalue(rvalue, state), } @@ -136,8 +181,7 @@ fn handle_constant( .literal .eval(self.tcx, self.param_env) .try_to_scalar() - .and_then(|scalar| scalar.try_to_int().ok()) - .map(|value| FlatSet::Elem(Const::Scalar(value, constant.ty()))) + .map(|value| FlatSet::Elem(ScalarTy(value, constant.ty()))) .unwrap_or(FlatSet::Top) } @@ -157,12 +201,12 @@ fn handle_switch_int( let value = match self.handle_operand(discr, state) { ValueOrPlace::Value(value) => value, ValueOrPlace::Place(place) => state.get_idx(place, self.map()), - ValueOrPlace::Unknown => FlatSet::Top, }; let result = match value { FlatSet::Top => FlatSet::Top, - FlatSet::Elem(Const::Scalar(scalar, _)) => { - FlatSet::Elem(scalar.assert_bits(scalar.size())) + FlatSet::Elem(ScalarTy(scalar, _)) => { + let int = scalar.assert_int(); + FlatSet::Elem(int.assert_bits(int.size())) } FlatSet::Bottom => FlatSet::Bottom, }; @@ -188,52 +232,39 @@ fn handle_switch_int( } #[derive(Clone, PartialEq, Eq)] -enum Const<'tcx> { - // FIXME: If there won't be any other cases, make it a struct. - Scalar(ScalarInt, Ty<'tcx>), -} +struct ScalarTy<'tcx>(Scalar, Ty<'tcx>); -impl<'tcx> std::fmt::Debug for Const<'tcx> { +impl<'tcx> std::fmt::Debug for ScalarTy<'tcx> { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { - match *self { - Self::Scalar(scalar, ty) => { - std::fmt::Display::fmt(&ConstantKind::Val(ConstValue::Scalar(scalar.into()), ty), f) - } - } + // This is used for dataflow visualization, so we return something more concise. + std::fmt::Display::fmt(&ConstantKind::Val(ConstValue::Scalar(self.0), self.1), f) } } impl<'tcx> ConstAnalysis<'tcx> { pub fn new(tcx: TyCtxt<'tcx>, body: &Body<'tcx>, map: Map) -> Self { + let param_env = tcx.param_env(body.source.def_id()); Self { map, tcx, - ecx: InterpCx::new(tcx, DUMMY_SP, ty::ParamEnv::empty(), DummyMachine), - param_env: tcx.param_env(body.source.def_id()), + ecx: InterpCx::new(tcx, DUMMY_SP, param_env, DummyMachine), + param_env: param_env, } } fn binary_op( &self, - state: &mut State>>, + state: &mut State>>, op: BinOp, left: &Operand<'tcx>, right: &Operand<'tcx>, - ) -> (FlatSet>, FlatSet>) { + ) -> (FlatSet>, FlatSet) { let left = self.eval_operand(left, state); let right = self.eval_operand(right, state); match (left, right) { (FlatSet::Elem(left), FlatSet::Elem(right)) => { match self.ecx.overflowing_binary_op(op, &left, &right) { - Ok((val, overflow, ty)) => { - let val = val - .try_to_int() - .ok() - .map(|val| self.wrap_scalar(val, ty)) - .unwrap_or(FlatSet::Top); - let overflow = self.wrap_scalar(overflow.into(), self.tcx.types.bool); - (val, overflow) - } + Ok((val, overflow, ty)) => (self.wrap_scalar(val, ty), FlatSet::Elem(overflow)), _ => (FlatSet::Top, FlatSet::Top), } } @@ -248,38 +279,35 @@ fn binary_op( fn eval_operand( &self, op: &Operand<'tcx>, - state: &mut State>>, + state: &mut State>>, ) -> FlatSet> { let value = match self.handle_operand(op, state) { ValueOrPlace::Value(value) => value, ValueOrPlace::Place(place) => state.get_idx(place, &self.map), - ValueOrPlace::Unknown => FlatSet::Top, }; match value { FlatSet::Top => FlatSet::Top, - FlatSet::Elem(Const::Scalar(value, ty)) => { - let layout = self - .tcx - .layout_of(ty::ParamEnv::empty().and(ty)) - .expect("this should not happen"); // FIXME - FlatSet::Elem(ImmTy::from_scalar(value.into(), layout)) - } + FlatSet::Elem(ScalarTy(scalar, ty)) => self + .tcx + .layout_of(self.param_env.and(ty)) + .map(|layout| FlatSet::Elem(ImmTy::from_scalar(scalar, layout))) + .unwrap_or(FlatSet::Top), FlatSet::Bottom => FlatSet::Bottom, } } - fn wrap_scalar(&self, scalar: ScalarInt, ty: Ty<'tcx>) -> FlatSet> { - FlatSet::Elem(Const::Scalar(scalar, ty)) + fn wrap_scalar(&self, scalar: Scalar, ty: Ty<'tcx>) -> FlatSet> { + FlatSet::Elem(ScalarTy(scalar, ty)) } - fn wrap_immediate(&self, imm: Immediate, ty: Ty<'tcx>) -> FlatSet> { + fn wrap_immediate(&self, imm: Immediate, ty: Ty<'tcx>) -> FlatSet> { match imm { - Immediate::Scalar(Scalar::Int(scalar)) => self.wrap_scalar(scalar, ty), + Immediate::Scalar(scalar) => self.wrap_scalar(scalar, ty), _ => FlatSet::Top, } } - fn wrap_immty(&self, val: ImmTy<'tcx>) -> FlatSet> { + fn wrap_immty(&self, val: ImmTy<'tcx>) -> FlatSet> { self.wrap_immediate(*val, val.layout.ty) } } @@ -287,8 +315,14 @@ fn wrap_immty(&self, val: ImmTy<'tcx>) -> FlatSet> { struct CollectAndPatch<'tcx, 'map> { tcx: TyCtxt<'tcx>, map: &'map Map, - before_effect: FxHashMap<(Location, Place<'tcx>), Const<'tcx>>, - assignments: FxHashMap>, + + /// For a given MIR location, this stores the values of the operands used by that location. In + /// particular, this is before the effect, such that the operands of `_1 = _1 + _2` are + /// properly captured. (This may become UB soon, but it is currently emitted even by safe code.) + before_effect: FxHashMap<(Location, Place<'tcx>), ScalarTy<'tcx>>, + + /// Stores the assigned values for assignments where the Rvalue is constant. + assignments: FxHashMap>, } impl<'tcx, 'map> CollectAndPatch<'tcx, 'map> { @@ -296,18 +330,17 @@ fn new(tcx: TyCtxt<'tcx>, map: &'map Map) -> Self { Self { tcx, map, before_effect: FxHashMap::default(), assignments: FxHashMap::default() } } - fn make_operand(&self, constant: Const<'tcx>) -> Operand<'tcx> { - let Const::Scalar(scalar, ty) = constant; + fn make_operand(&self, scalar: ScalarTy<'tcx>) -> Operand<'tcx> { Operand::Constant(Box::new(Constant { span: DUMMY_SP, user_ty: None, - literal: ConstantKind::Val(ConstValue::Scalar(scalar.into()), ty), + literal: ConstantKind::Val(ConstValue::Scalar(scalar.0), scalar.1), })) } } impl<'mir, 'tcx, 'map> ResultsVisitor<'mir, 'tcx> for CollectAndPatch<'tcx, 'map> { - type FlowState = State>>; + type FlowState = State>>; fn visit_statement_before_primary_effect( &mut self, @@ -330,13 +363,16 @@ fn visit_statement_after_primary_effect( location: Location, ) { match statement.kind { + StatementKind::Assign(box (_, Rvalue::Use(Operand::Constant(_)))) => { + // Don't overwrite the assignment if it already uses a constant (to keep the span). + } StatementKind::Assign(box (place, _)) => match state.get(place.as_ref(), self.map) { FlatSet::Top => (), FlatSet::Elem(value) => { self.assignments.insert(location, value); } FlatSet::Bottom => { - // This statement is not reachable. Do nothing, it will (hopefully) be removed. + // This assignment is either unreachable, or an uninitialized value is assigned. } }, _ => (), @@ -384,7 +420,7 @@ fn visit_operand(&mut self, operand: &mut Operand<'tcx>, location: Location) { } struct OperandCollector<'tcx, 'map, 'a> { - state: &'a State>>, + state: &'a State>>, visitor: &'a mut CollectAndPatch<'tcx, 'map>, } @@ -397,9 +433,7 @@ fn visit_operand(&mut self, operand: &Operand<'tcx>, location: Location) { FlatSet::Elem(value) => { self.visitor.before_effect.insert((location, *place), value); } - FlatSet::Bottom => { - // This only happens if this location is unreachable. - } + FlatSet::Bottom => (), } } _ => (), @@ -459,7 +493,7 @@ fn binary_ptr_op( _left: &rustc_const_eval::interpret::ImmTy<'tcx, Self::Provenance>, _right: &rustc_const_eval::interpret::ImmTy<'tcx, Self::Provenance>, ) -> interpret::InterpResult<'tcx, (interpret::Scalar, bool, Ty<'tcx>)> { - unimplemented!() + throw_unsup!(Unsupported("".into())) } fn expose_ptr(