diff options
| author | bors <bors@rust-lang.org> | 2023-12-30 03:45:58 +0000 |
|---|---|---|
| committer | bors <bors@rust-lang.org> | 2023-12-30 03:45:58 +0000 |
| commit | 8d76d076665f862ec9619f2de68d6d9ca1db4601 (patch) | |
| tree | e8e677eac08c9779819b5c046d8ee9c1d2b37f68 /compiler/rustc_mir_transform/src | |
| parent | 03b50195ab61a0dc9fc8de43d1de92769c4e6f23 (diff) | |
| parent | 6d7f0632ede023c71ebcd03c791166c716273b20 (diff) | |
| download | rust-8d76d076665f862ec9619f2de68d6d9ca1db4601.tar.gz rust-8d76d076665f862ec9619f2de68d6d9ca1db4601.zip | |
Auto merge of #116012 - cjgillot:gvn-const, r=oli-obk
Implement constant propagation on top of MIR SSA analysis This implements the idea I proposed in https://github.com/rust-lang/rust/pull/110719#issuecomment-1718324700 Based on https://github.com/rust-lang/rust/pull/109597 The value numbering "GVN" pass formulates each rvalue that appears in MIR with an abstract form (the `Value` enum), and assigns an integer `VnIndex` to each. This abstract form can be used to deduplicate values, reusing an earlier local that holds the same value instead of recomputing. This part is proposed in #109597. From this abstract representation, we can perform more involved simplifications, for example in https://github.com/rust-lang/rust/pull/111344. With the abstract representation `Value`, we can also attempt to evaluate each to a constant using the interpreter. This builds a `VnIndex -> OpTy` map. From this map, we can opportunistically replace an operand or a rvalue with a constant if their value has an associated `OpTy`. The most relevant commit is [Evaluated computed values to constants.](https://github.com/rust-lang/rust/commit/2767c4912ea249c2f613a9cedcd6c13ea1237e54)" r? `@oli-obk`
Diffstat (limited to 'compiler/rustc_mir_transform/src')
| -rw-r--r-- | compiler/rustc_mir_transform/src/const_prop.rs | 526 | ||||
| -rw-r--r-- | compiler/rustc_mir_transform/src/gvn.rs | 2 | ||||
| -rw-r--r-- | compiler/rustc_mir_transform/src/lib.rs | 1 |
3 files changed, 12 insertions, 517 deletions
diff --git a/compiler/rustc_mir_transform/src/const_prop.rs b/compiler/rustc_mir_transform/src/const_prop.rs index e66d5e0a9f9..c5824c30770 100644 --- a/compiler/rustc_mir_transform/src/const_prop.rs +++ b/compiler/rustc_mir_transform/src/const_prop.rs @@ -1,29 +1,22 @@ //! Propagates constants for early reporting of statically known //! assertion failures -use either::Right; -use rustc_const_eval::ReportErrorExt; +use rustc_const_eval::interpret::{ + self, compile_time_machine, AllocId, ConstAllocation, FnArg, Frame, ImmTy, InterpCx, + InterpResult, OpTy, PlaceTy, Pointer, +}; use rustc_data_structures::fx::FxHashSet; -use rustc_hir::def::DefKind; use rustc_index::bit_set::BitSet; -use rustc_index::{IndexSlice, IndexVec}; -use rustc_middle::mir::visit::{ - MutVisitor, MutatingUseContext, NonMutatingUseContext, PlaceContext, Visitor, -}; +use rustc_index::IndexVec; +use rustc_middle::mir::visit::{MutatingUseContext, NonMutatingUseContext, PlaceContext, Visitor}; use rustc_middle::mir::*; use rustc_middle::query::TyCtxtAt; -use rustc_middle::ty::layout::{LayoutError, LayoutOf, LayoutOfHelpers, TyAndLayout}; -use rustc_middle::ty::{self, GenericArgs, Instance, ParamEnv, Ty, TyCtxt, TypeVisitableExt}; -use rustc_span::{def_id::DefId, Span}; -use rustc_target::abi::{self, HasDataLayout, Size, TargetDataLayout}; +use rustc_middle::ty::layout::TyAndLayout; +use rustc_middle::ty::{self, ParamEnv, TyCtxt}; +use rustc_span::def_id::DefId; +use rustc_target::abi::Size; use rustc_target::spec::abi::Abi as CallAbi; -use crate::dataflow_const_prop::Patch; -use rustc_const_eval::interpret::{ - self, compile_time_machine, AllocId, ConstAllocation, FnArg, Frame, ImmTy, Immediate, InterpCx, - InterpResult, MemoryKind, OpTy, PlaceTy, Pointer, Scalar, StackPopCleanup, -}; - /// The maximum number of bytes that we'll allocate space for a local or the return value. /// Needed for #66397, because otherwise we eval into large places and that can cause OOM or just /// Severely regress performance. @@ -56,62 +49,7 @@ pub(crate) macro throw_machine_stop_str($($tt:tt)*) {{ throw_machine_stop!(Zst) }} -pub struct ConstProp; - -impl<'tcx> MirPass<'tcx> for ConstProp { - fn is_enabled(&self, sess: &rustc_session::Session) -> bool { - sess.mir_opt_level() >= 2 - } - - #[instrument(skip(self, tcx), level = "debug")] - fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) { - // will be evaluated by miri and produce its errors there - if body.source.promoted.is_some() { - return; - } - - let def_id = body.source.def_id().expect_local(); - let def_kind = tcx.def_kind(def_id); - let is_fn_like = def_kind.is_fn_like(); - let is_assoc_const = def_kind == DefKind::AssocConst; - - // Only run const prop on functions, methods, closures and associated constants - if !is_fn_like && !is_assoc_const { - // skip anon_const/statics/consts because they'll be evaluated by miri anyway - trace!("ConstProp skipped for {:?}", def_id); - return; - } - - // FIXME(welseywiser) const prop doesn't work on coroutines because of query cycles - // computing their layout. - if tcx.is_coroutine(def_id.to_def_id()) { - trace!("ConstProp skipped for coroutine {:?}", def_id); - return; - } - - trace!("ConstProp starting for {:?}", def_id); - - // FIXME(oli-obk, eddyb) Optimize locals (or even local paths) to hold - // constants, instead of just checking for const-folding succeeding. - // That would require a uniform one-def no-mutation analysis - // and RPO (or recursing when needing the value of a local). - let mut optimization_finder = ConstPropagator::new(body, tcx); - - // Traverse the body in reverse post-order, to ensure that `FullConstProp` locals are - // assigned before being read. - for &bb in body.basic_blocks.reverse_postorder() { - let data = &body.basic_blocks[bb]; - optimization_finder.visit_basic_block_data(bb, data); - } - - let mut patch = optimization_finder.patch; - patch.visit_body_preserves_cfg(body); - - trace!("ConstProp done for {:?}", def_id); - } -} - -pub struct ConstPropMachine<'mir, 'tcx> { +pub(crate) struct ConstPropMachine<'mir, 'tcx> { /// The virtual call stack. stack: Vec<Frame<'mir, 'tcx>>, pub written_only_inside_own_block_locals: FxHashSet<Local>, @@ -267,297 +205,6 @@ impl<'mir, 'tcx> interpret::Machine<'mir, 'tcx> for ConstPropMachine<'mir, 'tcx> } } -/// Finds optimization opportunities on the MIR. -struct ConstPropagator<'mir, 'tcx> { - ecx: InterpCx<'mir, 'tcx, ConstPropMachine<'mir, 'tcx>>, - tcx: TyCtxt<'tcx>, - param_env: ParamEnv<'tcx>, - local_decls: &'mir IndexSlice<Local, LocalDecl<'tcx>>, - patch: Patch<'tcx>, -} - -impl<'tcx> LayoutOfHelpers<'tcx> for ConstPropagator<'_, 'tcx> { - type LayoutOfResult = Result<TyAndLayout<'tcx>, LayoutError<'tcx>>; - - #[inline] - fn handle_layout_err(&self, err: LayoutError<'tcx>, _: Span, _: Ty<'tcx>) -> LayoutError<'tcx> { - err - } -} - -impl HasDataLayout for ConstPropagator<'_, '_> { - #[inline] - fn data_layout(&self) -> &TargetDataLayout { - &self.tcx.data_layout - } -} - -impl<'tcx> ty::layout::HasTyCtxt<'tcx> for ConstPropagator<'_, 'tcx> { - #[inline] - fn tcx(&self) -> TyCtxt<'tcx> { - self.tcx - } -} - -impl<'tcx> ty::layout::HasParamEnv<'tcx> for ConstPropagator<'_, 'tcx> { - #[inline] - fn param_env(&self) -> ty::ParamEnv<'tcx> { - self.param_env - } -} - -impl<'mir, 'tcx> ConstPropagator<'mir, 'tcx> { - fn new(body: &'mir Body<'tcx>, tcx: TyCtxt<'tcx>) -> ConstPropagator<'mir, 'tcx> { - let def_id = body.source.def_id(); - let args = &GenericArgs::identity_for_item(tcx, def_id); - let param_env = tcx.param_env_reveal_all_normalized(def_id); - - let can_const_prop = CanConstProp::check(tcx, param_env, body); - let mut ecx = InterpCx::new( - tcx, - tcx.def_span(def_id), - param_env, - ConstPropMachine::new(can_const_prop), - ); - - let ret_layout = ecx - .layout_of(body.bound_return_ty().instantiate(tcx, args)) - .ok() - // Don't bother allocating memory for large values. - // I don't know how return types can seem to be unsized but this happens in the - // `type/type-unsatisfiable.rs` test. - .filter(|ret_layout| { - ret_layout.is_sized() && ret_layout.size < Size::from_bytes(MAX_ALLOC_LIMIT) - }) - .unwrap_or_else(|| ecx.layout_of(tcx.types.unit).unwrap()); - - let ret = ecx - .allocate(ret_layout, MemoryKind::Stack) - .expect("couldn't perform small allocation") - .into(); - - ecx.push_stack_frame( - Instance::new(def_id, args), - body, - &ret, - StackPopCleanup::Root { cleanup: false }, - ) - .expect("failed to push initial stack frame"); - - for local in body.local_decls.indices() { - // Mark everything initially live. - // This is somewhat dicey since some of them might be unsized and it is incoherent to - // mark those as live... We rely on `local_to_place`/`local_to_op` in the interpreter - // stopping us before those unsized immediates can cause issues deeper in the - // interpreter. - ecx.frame_mut().locals[local].make_live_uninit(); - } - - let patch = Patch::new(tcx); - ConstPropagator { ecx, tcx, param_env, local_decls: &body.local_decls, patch } - } - - fn get_const(&self, place: Place<'tcx>) -> Option<OpTy<'tcx>> { - let op = match self.ecx.eval_place_to_op(place, None) { - Ok(op) => { - if op - .as_mplace_or_imm() - .right() - .is_some_and(|imm| matches!(*imm, Immediate::Uninit)) - { - // Make sure nobody accidentally uses this value. - return None; - } - op - } - Err(e) => { - trace!("get_const failed: {:?}", e.into_kind().debug()); - return None; - } - }; - - // Try to read the local as an immediate so that if it is representable as a scalar, we can - // handle it as such, but otherwise, just return the value as is. - Some(match self.ecx.read_immediate_raw(&op) { - Ok(Right(imm)) => imm.into(), - _ => op, - }) - } - - /// Remove `local` from the pool of `Locals`. Allows writing to them, - /// but not reading from them anymore. - fn remove_const(ecx: &mut InterpCx<'mir, 'tcx, ConstPropMachine<'mir, 'tcx>>, local: Local) { - ecx.frame_mut().locals[local].make_live_uninit(); - ecx.machine.written_only_inside_own_block_locals.remove(&local); - } - - fn check_rvalue(&mut self, rvalue: &Rvalue<'tcx>) -> Option<()> { - // Perform any special handling for specific Rvalue types. - // Generally, checks here fall into one of two categories: - // 1. Additional checking to provide useful lints to the user - // - In this case, we will do some validation and then fall through to the - // end of the function which evals the assignment. - // 2. Working around bugs in other parts of the compiler - // - In this case, we'll return `None` from this function to stop evaluation. - match rvalue { - // Do not try creating references (#67862) - Rvalue::AddressOf(_, place) | Rvalue::Ref(_, _, place) => { - trace!("skipping AddressOf | Ref for {:?}", place); - - // This may be creating mutable references or immutable references to cells. - // If that happens, the pointed to value could be mutated via that reference. - // Since we aren't tracking references, the const propagator loses track of what - // value the local has right now. - // Thus, all locals that have their reference taken - // must not take part in propagation. - Self::remove_const(&mut self.ecx, place.local); - - return None; - } - Rvalue::ThreadLocalRef(def_id) => { - trace!("skipping ThreadLocalRef({:?})", def_id); - - return None; - } - // There's no other checking to do at this time. - Rvalue::Aggregate(..) - | Rvalue::Use(..) - | Rvalue::CopyForDeref(..) - | Rvalue::Repeat(..) - | Rvalue::Len(..) - | Rvalue::Cast(..) - | Rvalue::ShallowInitBox(..) - | Rvalue::Discriminant(..) - | Rvalue::NullaryOp(..) - | Rvalue::UnaryOp(..) - | Rvalue::BinaryOp(..) - | Rvalue::CheckedBinaryOp(..) => {} - } - - // FIXME we need to revisit this for #67176 - if rvalue.has_param() { - trace!("skipping, has param"); - return None; - } - if !rvalue - .ty(&self.ecx.frame().body.local_decls, *self.ecx.tcx) - .is_sized(*self.ecx.tcx, self.param_env) - { - // the interpreter doesn't support unsized locals (only unsized arguments), - // but rustc does (in a kinda broken way), so we have to skip them here - return None; - } - - Some(()) - } - - // Attempt to use algebraic identities to eliminate constant expressions - fn eval_rvalue_with_identities( - &mut self, - rvalue: &Rvalue<'tcx>, - place: Place<'tcx>, - ) -> Option<()> { - match rvalue { - Rvalue::BinaryOp(op, box (left, right)) - | Rvalue::CheckedBinaryOp(op, box (left, right)) => { - let l = self.ecx.eval_operand(left, None).and_then(|x| self.ecx.read_immediate(&x)); - let r = - self.ecx.eval_operand(right, None).and_then(|x| self.ecx.read_immediate(&x)); - - let const_arg = match (l, r) { - (Ok(x), Err(_)) | (Err(_), Ok(x)) => x, // exactly one side is known - (Err(_), Err(_)) => return None, // neither side is known - (Ok(_), Ok(_)) => return self.ecx.eval_rvalue_into_place(rvalue, place).ok(), // both sides are known - }; - - if !matches!(const_arg.layout.abi, abi::Abi::Scalar(..)) { - // We cannot handle Scalar Pair stuff. - // No point in calling `eval_rvalue_into_place`, since only one side is known - return None; - } - - let arg_value = const_arg.to_scalar().to_bits(const_arg.layout.size).ok()?; - let dest = self.ecx.eval_place(place).ok()?; - - match op { - BinOp::BitAnd if arg_value == 0 => { - self.ecx.write_immediate(*const_arg, &dest).ok() - } - BinOp::BitOr - if arg_value == const_arg.layout.size.truncate(u128::MAX) - || (const_arg.layout.ty.is_bool() && arg_value == 1) => - { - self.ecx.write_immediate(*const_arg, &dest).ok() - } - BinOp::Mul if const_arg.layout.ty.is_integral() && arg_value == 0 => { - if let Rvalue::CheckedBinaryOp(_, _) = rvalue { - let val = Immediate::ScalarPair( - const_arg.to_scalar(), - Scalar::from_bool(false), - ); - self.ecx.write_immediate(val, &dest).ok() - } else { - self.ecx.write_immediate(*const_arg, &dest).ok() - } - } - _ => None, - } - } - _ => self.ecx.eval_rvalue_into_place(rvalue, place).ok(), - } - } - - fn replace_with_const(&mut self, place: Place<'tcx>) -> Option<Const<'tcx>> { - // This will return None if the above `const_prop` invocation only "wrote" a - // type whose creation requires no write. E.g. a coroutine whose initial state - // consists solely of uninitialized memory (so it doesn't capture any locals). - let value = self.get_const(place)?; - if !self.tcx.consider_optimizing(|| format!("ConstantPropagation - {value:?}")) { - return None; - } - trace!("replacing {:?} with {:?}", place, value); - - // FIXME: figure out what to do when read_immediate_raw fails - let imm = self.ecx.read_immediate_raw(&value).ok()?; - - let Right(imm) = imm else { return None }; - match *imm { - Immediate::Scalar(scalar) if scalar.try_to_int().is_ok() => { - Some(Const::from_scalar(self.tcx, scalar, value.layout.ty)) - } - Immediate::ScalarPair(l, r) if l.try_to_int().is_ok() && r.try_to_int().is_ok() => { - let alloc_id = self - .ecx - .intern_with_temp_alloc(value.layout, |ecx, dest| { - ecx.write_immediate(*imm, dest) - }) - .ok()?; - - Some(Const::Val( - ConstValue::Indirect { alloc_id, offset: Size::ZERO }, - value.layout.ty, - )) - } - // Scalars or scalar pairs that contain undef values are assumed to not have - // successfully evaluated and are thus not propagated. - _ => None, - } - } - - fn ensure_not_propagated(&self, local: Local) { - if cfg!(debug_assertions) { - assert!( - self.get_const(local.into()).is_none() - || self - .layout_of(self.local_decls[local].ty) - .map_or(true, |layout| layout.is_zst()), - "failed to remove values for `{local:?}`, value={:?}", - self.get_const(local.into()), - ) - } - } -} - /// The mode that `ConstProp` is allowed to run in for a given `Local`. #[derive(Clone, Copy, Debug, PartialEq)] pub enum ConstPropMode { @@ -677,154 +324,3 @@ impl<'tcx> Visitor<'tcx> for CanConstProp { } } } - -impl<'tcx> Visitor<'tcx> for ConstPropagator<'_, 'tcx> { - fn visit_operand(&mut self, operand: &Operand<'tcx>, location: Location) { - self.super_operand(operand, location); - if let Some(place) = operand.place() - && let Some(value) = self.replace_with_const(place) - { - self.patch.before_effect.insert((location, place), value); - } - } - - fn visit_projection_elem( - &mut self, - _: PlaceRef<'tcx>, - elem: PlaceElem<'tcx>, - _: PlaceContext, - location: Location, - ) { - if let PlaceElem::Index(local) = elem - && let Some(value) = self.replace_with_const(local.into()) - { - self.patch.before_effect.insert((location, local.into()), value); - } - } - - fn visit_assign(&mut self, place: &Place<'tcx>, rvalue: &Rvalue<'tcx>, location: Location) { - self.super_assign(place, rvalue, location); - - let Some(()) = self.check_rvalue(rvalue) else { - trace!("rvalue check failed, removing const"); - Self::remove_const(&mut self.ecx, place.local); - return; - }; - - match self.ecx.machine.can_const_prop[place.local] { - // Do nothing if the place is indirect. - _ if place.is_indirect() => {} - ConstPropMode::NoPropagation => self.ensure_not_propagated(place.local), - ConstPropMode::OnlyInsideOwnBlock | ConstPropMode::FullConstProp => { - if let Some(()) = self.eval_rvalue_with_identities(rvalue, *place) { - // If this was already an evaluated constant, keep it. - if let Rvalue::Use(Operand::Constant(c)) = rvalue - && let Const::Val(..) = c.const_ - { - trace!( - "skipping replace of Rvalue::Use({:?} because it is already a const", - c - ); - } else if let Some(operand) = self.replace_with_const(*place) { - self.patch.assignments.insert(location, operand); - } - } else { - // Const prop failed, so erase the destination, ensuring that whatever happens - // from here on, does not know about the previous value. - // This is important in case we have - // ```rust - // let mut x = 42; - // x = SOME_MUTABLE_STATIC; - // // x must now be uninit - // ``` - // FIXME: we overzealously erase the entire local, because that's easier to - // implement. - trace!( - "propagation into {:?} failed. - Nuking the entire site from orbit, it's the only way to be sure", - place, - ); - Self::remove_const(&mut self.ecx, place.local); - } - } - } - } - - fn visit_statement(&mut self, statement: &Statement<'tcx>, location: Location) { - trace!("visit_statement: {:?}", statement); - - // We want to evaluate operands before any change to the assigned-to value, - // so we recurse first. - self.super_statement(statement, location); - - match statement.kind { - StatementKind::SetDiscriminant { ref place, .. } => { - match self.ecx.machine.can_const_prop[place.local] { - // Do nothing if the place is indirect. - _ if place.is_indirect() => {} - ConstPropMode::NoPropagation => self.ensure_not_propagated(place.local), - ConstPropMode::FullConstProp | ConstPropMode::OnlyInsideOwnBlock => { - if self.ecx.statement(statement).is_ok() { - trace!("propped discriminant into {:?}", place); - } else { - Self::remove_const(&mut self.ecx, place.local); - } - } - } - } - StatementKind::StorageLive(local) => { - Self::remove_const(&mut self.ecx, local); - } - // We do not need to mark dead locals as such. For `FullConstProp` locals, - // this allows to propagate the single assigned value in this case: - // ``` - // let x = SOME_CONST; - // if a { - // f(copy x); - // StorageDead(x); - // } else { - // g(copy x); - // StorageDead(x); - // } - // ``` - // - // This may propagate a constant where the local would be uninit or dead. - // In both cases, this does not matter, as those reads would be UB anyway. - _ => {} - } - } - - fn visit_basic_block_data(&mut self, block: BasicBlock, data: &BasicBlockData<'tcx>) { - self.super_basic_block_data(block, data); - - // We remove all Locals which are restricted in propagation to their containing blocks and - // which were modified in the current block. - // Take it out of the ecx so we can get a mutable reference to the ecx for `remove_const`. - let mut written_only_inside_own_block_locals = - std::mem::take(&mut self.ecx.machine.written_only_inside_own_block_locals); - - // This loop can get very hot for some bodies: it check each local in each bb. - // To avoid this quadratic behaviour, we only clear the locals that were modified inside - // the current block. - for local in written_only_inside_own_block_locals.drain() { - debug_assert_eq!( - self.ecx.machine.can_const_prop[local], - ConstPropMode::OnlyInsideOwnBlock - ); - Self::remove_const(&mut self.ecx, local); - } - self.ecx.machine.written_only_inside_own_block_locals = - written_only_inside_own_block_locals; - - if cfg!(debug_assertions) { - for (local, &mode) in self.ecx.machine.can_const_prop.iter_enumerated() { - match mode { - ConstPropMode::FullConstProp => {} - ConstPropMode::NoPropagation | ConstPropMode::OnlyInsideOwnBlock => { - self.ensure_not_propagated(local); - } - } - } - } - } -} diff --git a/compiler/rustc_mir_transform/src/gvn.rs b/compiler/rustc_mir_transform/src/gvn.rs index c747cff89e7..2551c8aca88 100644 --- a/compiler/rustc_mir_transform/src/gvn.rs +++ b/compiler/rustc_mir_transform/src/gvn.rs @@ -109,7 +109,7 @@ pub struct GVN; impl<'tcx> MirPass<'tcx> for GVN { fn is_enabled(&self, sess: &rustc_session::Session) -> bool { - sess.mir_opt_level() >= 4 + sess.mir_opt_level() >= 2 } #[instrument(level = "trace", skip(self, tcx, body))] diff --git a/compiler/rustc_mir_transform/src/lib.rs b/compiler/rustc_mir_transform/src/lib.rs index 9d03bab4844..5562ae7f3bd 100644 --- a/compiler/rustc_mir_transform/src/lib.rs +++ b/compiler/rustc_mir_transform/src/lib.rs @@ -588,7 +588,6 @@ fn run_optimization_passes<'tcx>(tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) { // destroy the SSA property. It should still happen before const-propagation, so the // latter pass will leverage the created opportunities. &separate_const_switch::SeparateConstSwitch, - &const_prop::ConstProp, &gvn::GVN, &simplify::SimplifyLocals::AfterGVN, &dataflow_const_prop::DataflowConstProp, |
