diff options
Diffstat (limited to 'compiler/rustc_mir_transform')
| -rw-r--r-- | compiler/rustc_mir_transform/src/const_goto.rs | 128 | ||||
| -rw-r--r-- | compiler/rustc_mir_transform/src/lib.rs | 7 | ||||
| -rw-r--r-- | compiler/rustc_mir_transform/src/separate_const_switch.rs | 343 |
3 files changed, 0 insertions, 478 deletions
diff --git a/compiler/rustc_mir_transform/src/const_goto.rs b/compiler/rustc_mir_transform/src/const_goto.rs deleted file mode 100644 index cb5b66b314d..00000000000 --- a/compiler/rustc_mir_transform/src/const_goto.rs +++ /dev/null @@ -1,128 +0,0 @@ -//! This pass optimizes the following sequence -//! ```rust,ignore (example) -//! bb2: { -//! _2 = const true; -//! goto -> bb3; -//! } -//! -//! bb3: { -//! switchInt(_2) -> [false: bb4, otherwise: bb5]; -//! } -//! ``` -//! into -//! ```rust,ignore (example) -//! bb2: { -//! _2 = const true; -//! goto -> bb5; -//! } -//! ``` - -use rustc_middle::mir::*; -use rustc_middle::ty::TyCtxt; -use rustc_middle::{mir::visit::Visitor, ty::ParamEnv}; - -use super::simplify::{simplify_cfg, simplify_locals}; - -pub struct ConstGoto; - -impl<'tcx> MirPass<'tcx> for ConstGoto { - fn is_enabled(&self, sess: &rustc_session::Session) -> bool { - // This pass participates in some as-of-yet untested unsoundness found - // in https://github.com/rust-lang/rust/issues/112460 - sess.mir_opt_level() >= 2 && sess.opts.unstable_opts.unsound_mir_opts - } - - fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) { - trace!("Running ConstGoto on {:?}", body.source); - let param_env = tcx.param_env_reveal_all_normalized(body.source.def_id()); - let mut opt_finder = - ConstGotoOptimizationFinder { tcx, body, optimizations: vec![], param_env }; - opt_finder.visit_body(body); - let should_simplify = !opt_finder.optimizations.is_empty(); - for opt in opt_finder.optimizations { - let block = &mut body.basic_blocks_mut()[opt.bb_with_goto]; - block.statements.extend(opt.stmts_move_up); - let terminator = block.terminator_mut(); - let new_goto = TerminatorKind::Goto { target: opt.target_to_use_in_goto }; - debug!("SUCCESS: replacing `{:?}` with `{:?}`", terminator.kind, new_goto); - terminator.kind = new_goto; - } - - // if we applied optimizations, we potentially have some cfg to cleanup to - // make it easier for further passes - if should_simplify { - simplify_cfg(body); - simplify_locals(body, tcx); - } - } -} - -impl<'tcx> Visitor<'tcx> for ConstGotoOptimizationFinder<'_, 'tcx> { - fn visit_basic_block_data(&mut self, block: BasicBlock, data: &BasicBlockData<'tcx>) { - if data.is_cleanup { - // Because of the restrictions around control flow in cleanup blocks, we don't perform - // this optimization at all in such blocks. - return; - } - self.super_basic_block_data(block, data); - } - - fn visit_terminator(&mut self, terminator: &Terminator<'tcx>, location: Location) { - let _: Option<_> = try { - let target = terminator.kind.as_goto()?; - // We only apply this optimization if the last statement is a const assignment - let last_statement = self.body.basic_blocks[location.block].statements.last()?; - - if let (place, Rvalue::Use(Operand::Constant(_const))) = - last_statement.kind.as_assign()? - { - // We found a constant being assigned to `place`. - // Now check that the target of this Goto switches on this place. - let target_bb = &self.body.basic_blocks[target]; - - // The `StorageDead(..)` statement does not affect the functionality of mir. - // We can move this part of the statement up to the predecessor. - let mut stmts_move_up = Vec::new(); - for stmt in &target_bb.statements { - if let StatementKind::StorageDead(..) = stmt.kind { - stmts_move_up.push(stmt.clone()) - } else { - None?; - } - } - - let target_bb_terminator = target_bb.terminator(); - let (discr, targets) = target_bb_terminator.kind.as_switch()?; - if discr.place() == Some(*place) { - let switch_ty = place.ty(self.body.local_decls(), self.tcx).ty; - debug_assert_eq!(switch_ty, _const.ty()); - // We now know that the Switch matches on the const place, and it is statementless - // Now find which value in the Switch matches the const value. - let const_value = _const.const_.try_eval_bits(self.tcx, self.param_env)?; - let target_to_use_in_goto = targets.target_for_value(const_value); - self.optimizations.push(OptimizationToApply { - bb_with_goto: location.block, - target_to_use_in_goto, - stmts_move_up, - }); - } - } - Some(()) - }; - - self.super_terminator(terminator, location); - } -} - -struct OptimizationToApply<'tcx> { - bb_with_goto: BasicBlock, - target_to_use_in_goto: BasicBlock, - stmts_move_up: Vec<Statement<'tcx>>, -} - -pub struct ConstGotoOptimizationFinder<'a, 'tcx> { - tcx: TyCtxt<'tcx>, - body: &'a Body<'tcx>, - param_env: ParamEnv<'tcx>, - optimizations: Vec<OptimizationToApply<'tcx>>, -} diff --git a/compiler/rustc_mir_transform/src/lib.rs b/compiler/rustc_mir_transform/src/lib.rs index 8e5d69605aa..281bf3d44e6 100644 --- a/compiler/rustc_mir_transform/src/lib.rs +++ b/compiler/rustc_mir_transform/src/lib.rs @@ -59,7 +59,6 @@ mod remove_place_mention; mod add_subtyping_projections; pub mod cleanup_post_borrowck; mod const_debuginfo; -mod const_goto; mod const_prop; mod const_prop_lint; mod copy_prop; @@ -103,7 +102,6 @@ mod remove_unneeded_drops; mod remove_zsts; mod required_consts; mod reveal_all; -mod separate_const_switch; mod shim; mod ssa; // This pass is public to allow external drivers to perform MIR cleanup @@ -590,7 +588,6 @@ fn run_optimization_passes<'tcx>(tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) { // Has to run after `slice::len` lowering &normalize_array_len::NormalizeArrayLen, - &const_goto::ConstGoto, &ref_prop::ReferencePropagation, &sroa::ScalarReplacementOfAggregates, &match_branches::MatchBranchSimplification, @@ -601,10 +598,6 @@ fn run_optimization_passes<'tcx>(tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) { &dead_store_elimination::DeadStoreElimination::Initial, &gvn::GVN, &simplify::SimplifyLocals::AfterGVN, - // Perform `SeparateConstSwitch` after SSA-based analyses, as cloning blocks may - // destroy the SSA property. It should still happen before const-propagation, so the - // latter pass will leverage the created opportunities. - &separate_const_switch::SeparateConstSwitch, &dataflow_const_prop::DataflowConstProp, &const_debuginfo::ConstDebugInfo, &o1(simplify_branches::SimplifyConstCondition::AfterConstProp), diff --git a/compiler/rustc_mir_transform/src/separate_const_switch.rs b/compiler/rustc_mir_transform/src/separate_const_switch.rs deleted file mode 100644 index 7120ef72142..00000000000 --- a/compiler/rustc_mir_transform/src/separate_const_switch.rs +++ /dev/null @@ -1,343 +0,0 @@ -//! A pass that duplicates switch-terminated blocks -//! into a new copy for each predecessor, provided -//! the predecessor sets the value being switched -//! over to a constant. -//! -//! The purpose of this pass is to help constant -//! propagation passes to simplify the switch terminator -//! of the copied blocks into gotos when some predecessors -//! statically determine the output of switches. -//! -//! ```text -//! x = 12 --- ---> something -//! \ / 12 -//! --> switch x -//! / \ otherwise -//! x = y --- ---> something else -//! ``` -//! becomes -//! ```text -//! x = 12 ---> switch x ------> something -//! \ / 12 -//! X -//! / \ otherwise -//! x = y ---> switch x ------> something else -//! ``` -//! so it can hopefully later be turned by another pass into -//! ```text -//! x = 12 --------------------> something -//! / 12 -//! / -//! / otherwise -//! x = y ---- switch x ------> something else -//! ``` -//! -//! This optimization is meant to cover simple cases -//! like `?` desugaring. For now, it thus focuses on -//! simplicity rather than completeness (it notably -//! sometimes duplicates abusively). - -use rustc_middle::mir::*; -use rustc_middle::ty::TyCtxt; -use smallvec::SmallVec; - -pub struct SeparateConstSwitch; - -impl<'tcx> MirPass<'tcx> for SeparateConstSwitch { - fn is_enabled(&self, sess: &rustc_session::Session) -> bool { - // This pass participates in some as-of-yet untested unsoundness found - // in https://github.com/rust-lang/rust/issues/112460 - sess.mir_opt_level() >= 2 && sess.opts.unstable_opts.unsound_mir_opts - } - - fn run_pass(&self, _: TyCtxt<'tcx>, body: &mut Body<'tcx>) { - // If execution did something, applying a simplification layer - // helps later passes optimize the copy away. - if separate_const_switch(body) > 0 { - super::simplify::simplify_cfg(body); - } - } -} - -/// Returns the amount of blocks that were duplicated -pub fn separate_const_switch(body: &mut Body<'_>) -> usize { - let mut new_blocks: SmallVec<[(BasicBlock, BasicBlock); 6]> = SmallVec::new(); - let predecessors = body.basic_blocks.predecessors(); - 'block_iter: for (block_id, block) in body.basic_blocks.iter_enumerated() { - if let TerminatorKind::SwitchInt { - discr: Operand::Copy(switch_place) | Operand::Move(switch_place), - .. - } = block.terminator().kind - { - // If the block is on an unwind path, do not - // apply the optimization as unwind paths - // rely on a unique parent invariant - if block.is_cleanup { - continue 'block_iter; - } - - // If the block has fewer than 2 predecessors, ignore it - // we could maybe chain blocks that have exactly one - // predecessor, but for now we ignore that - if predecessors[block_id].len() < 2 { - continue 'block_iter; - } - - // First, let's find a non-const place - // that determines the result of the switch - if let Some(switch_place) = find_determining_place(switch_place, block) { - // We now have an input place for which it would - // be interesting if predecessors assigned it from a const - - let mut predecessors_left = predecessors[block_id].len(); - 'predec_iter: for predecessor_id in predecessors[block_id].iter().copied() { - let predecessor = &body.basic_blocks[predecessor_id]; - - // First we make sure the predecessor jumps - // in a reasonable way - match &predecessor.terminator().kind { - // The following terminators are - // unconditionally valid - TerminatorKind::Goto { .. } | TerminatorKind::SwitchInt { .. } => {} - - TerminatorKind::FalseEdge { real_target, .. } => { - if *real_target != block_id { - continue 'predec_iter; - } - } - - // The following terminators are not allowed - TerminatorKind::UnwindResume - | TerminatorKind::Drop { .. } - | TerminatorKind::Call { .. } - | TerminatorKind::Assert { .. } - | TerminatorKind::FalseUnwind { .. } - | TerminatorKind::Yield { .. } - | TerminatorKind::UnwindTerminate(_) - | TerminatorKind::Return - | TerminatorKind::Unreachable - | TerminatorKind::InlineAsm { .. } - | TerminatorKind::CoroutineDrop => { - continue 'predec_iter; - } - } - - if is_likely_const(switch_place, predecessor) { - new_blocks.push((predecessor_id, block_id)); - predecessors_left -= 1; - if predecessors_left < 2 { - // If the original block only has one predecessor left, - // we have nothing left to do - break 'predec_iter; - } - } - } - } - } - } - - // Once the analysis is done, perform the duplication - let body_span = body.span; - let copied_blocks = new_blocks.len(); - let blocks = body.basic_blocks_mut(); - for (pred_id, target_id) in new_blocks { - let new_block = blocks[target_id].clone(); - let new_block_id = blocks.push(new_block); - let terminator = blocks[pred_id].terminator_mut(); - - match terminator.kind { - TerminatorKind::Goto { ref mut target } => { - *target = new_block_id; - } - - TerminatorKind::FalseEdge { ref mut real_target, .. } => { - if *real_target == target_id { - *real_target = new_block_id; - } - } - - TerminatorKind::SwitchInt { ref mut targets, .. } => { - targets.all_targets_mut().iter_mut().for_each(|x| { - if *x == target_id { - *x = new_block_id; - } - }); - } - - TerminatorKind::UnwindResume - | TerminatorKind::UnwindTerminate(_) - | TerminatorKind::Return - | TerminatorKind::Unreachable - | TerminatorKind::CoroutineDrop - | TerminatorKind::Assert { .. } - | TerminatorKind::FalseUnwind { .. } - | TerminatorKind::Drop { .. } - | TerminatorKind::Call { .. } - | TerminatorKind::InlineAsm { .. } - | TerminatorKind::Yield { .. } => { - span_bug!( - body_span, - "basic block terminator had unexpected kind {:?}", - &terminator.kind - ) - } - } - } - - copied_blocks -} - -/// This function describes a rough heuristic guessing -/// whether a place is last set with a const within the block. -/// Notably, it will be overly pessimistic in cases that are already -/// not handled by `separate_const_switch`. -fn is_likely_const<'tcx>(mut tracked_place: Place<'tcx>, block: &BasicBlockData<'tcx>) -> bool { - for statement in block.statements.iter().rev() { - match &statement.kind { - StatementKind::Assign(assign) => { - if assign.0 == tracked_place { - match assign.1 { - // These rvalues are definitely constant - Rvalue::Use(Operand::Constant(_)) - | Rvalue::Ref(_, _, _) - | Rvalue::AddressOf(_, _) - | Rvalue::Cast(_, Operand::Constant(_), _) - | Rvalue::NullaryOp(_, _) - | Rvalue::ShallowInitBox(_, _) - | Rvalue::UnaryOp(_, Operand::Constant(_)) => return true, - - // These rvalues make things ambiguous - Rvalue::Repeat(_, _) - | Rvalue::ThreadLocalRef(_) - | Rvalue::Len(_) - | Rvalue::BinaryOp(_, _) - | Rvalue::CheckedBinaryOp(_, _) - | Rvalue::Aggregate(_, _) => return false, - - // These rvalues move the place to track - Rvalue::Cast(_, Operand::Copy(place) | Operand::Move(place), _) - | Rvalue::Use(Operand::Copy(place) | Operand::Move(place)) - | Rvalue::CopyForDeref(place) - | Rvalue::UnaryOp(_, Operand::Copy(place) | Operand::Move(place)) - | Rvalue::Discriminant(place) => tracked_place = place, - } - } - } - - // If the discriminant is set, it is always set - // as a constant, so the job is done. - // As we are **ignoring projections**, if the place - // we are tracking sees its discriminant be set, - // that means we had to be tracking the discriminant - // specifically (as it is impossible to switch over - // an enum directly, and if we were switching over - // its content, we would have had to at least cast it to - // some variant first) - StatementKind::SetDiscriminant { place, .. } => { - if **place == tracked_place { - return true; - } - } - - // These statements have no influence on the place - // we are interested in - StatementKind::FakeRead(_) - | StatementKind::Deinit(_) - | StatementKind::StorageLive(_) - | StatementKind::Retag(_, _) - | StatementKind::AscribeUserType(_, _) - | StatementKind::PlaceMention(..) - | StatementKind::Coverage(_) - | StatementKind::StorageDead(_) - | StatementKind::Intrinsic(_) - | StatementKind::ConstEvalCounter - | StatementKind::Nop => {} - } - } - - // If no good reason for the place to be const is found, - // give up. We could maybe go up predecessors, but in - // most cases giving up now should be sufficient. - false -} - -/// Finds a unique place that entirely determines the value -/// of `switch_place`, if it exists. This is only a heuristic. -/// Ideally we would like to track multiple determining places -/// for some edge cases, but one is enough for a lot of situations. -fn find_determining_place<'tcx>( - mut switch_place: Place<'tcx>, - block: &BasicBlockData<'tcx>, -) -> Option<Place<'tcx>> { - for statement in block.statements.iter().rev() { - match &statement.kind { - StatementKind::Assign(op) => { - if op.0 != switch_place { - continue; - } - - match op.1 { - // The following rvalues move the place - // that may be const in the predecessor - Rvalue::Use(Operand::Move(new) | Operand::Copy(new)) - | Rvalue::UnaryOp(_, Operand::Copy(new) | Operand::Move(new)) - | Rvalue::CopyForDeref(new) - | Rvalue::Cast(_, Operand::Move(new) | Operand::Copy(new), _) - | Rvalue::Repeat(Operand::Move(new) | Operand::Copy(new), _) - | Rvalue::Discriminant(new) - => switch_place = new, - - // The following rvalues might still make the block - // be valid but for now we reject them - Rvalue::Len(_) - | Rvalue::Ref(_, _, _) - | Rvalue::BinaryOp(_, _) - | Rvalue::CheckedBinaryOp(_, _) - | Rvalue::Aggregate(_, _) - - // The following rvalues definitely mean we cannot - // or should not apply this optimization - | Rvalue::Use(Operand::Constant(_)) - | Rvalue::Repeat(Operand::Constant(_), _) - | Rvalue::ThreadLocalRef(_) - | Rvalue::AddressOf(_, _) - | Rvalue::NullaryOp(_, _) - | Rvalue::ShallowInitBox(_, _) - | Rvalue::UnaryOp(_, Operand::Constant(_)) - | Rvalue::Cast(_, Operand::Constant(_), _) => return None, - } - } - - // These statements have no influence on the place - // we are interested in - StatementKind::FakeRead(_) - | StatementKind::Deinit(_) - | StatementKind::StorageLive(_) - | StatementKind::StorageDead(_) - | StatementKind::Retag(_, _) - | StatementKind::AscribeUserType(_, _) - | StatementKind::PlaceMention(..) - | StatementKind::Coverage(_) - | StatementKind::Intrinsic(_) - | StatementKind::ConstEvalCounter - | StatementKind::Nop => {} - - // If the discriminant is set, it is always set - // as a constant, so the job is already done. - // As we are **ignoring projections**, if the place - // we are tracking sees its discriminant be set, - // that means we had to be tracking the discriminant - // specifically (as it is impossible to switch over - // an enum directly, and if we were switching over - // its content, we would have had to at least cast it to - // some variant first) - StatementKind::SetDiscriminant { place, .. } => { - if **place == switch_place { - return None; - } - } - } - } - - Some(switch_place) -} |