| //! Trivial copy propagation pass. |
| //! |
| //! This uses def-use analysis to remove values that have exactly one def and one use, which must |
| //! be an assignment. |
| //! |
| //! To give an example, we look for patterns that look like: |
| //! |
| //! DEST = SRC |
| //! ... |
| //! USE(DEST) |
| //! |
| //! where `DEST` and `SRC` are both locals of some form. We replace that with: |
| //! |
| //! NOP |
| //! ... |
| //! USE(SRC) |
| //! |
| //! The assignment `DEST = SRC` must be (a) the only mutation of `DEST` and (b) the only |
| //! (non-mutating) use of `SRC`. These restrictions are conservative and may be relaxed in the |
| //! future. |
| |
| use rustc::mir::{ |
| Constant, Local, LocalKind, Location, Place, Body, BodyAndCache, Operand, Rvalue, |
| StatementKind, read_only |
| }; |
| use rustc::mir::visit::MutVisitor; |
| use rustc::ty::TyCtxt; |
| use crate::transform::{MirPass, MirSource}; |
| use crate::util::def_use::DefUseAnalysis; |
| |
| pub struct CopyPropagation; |
| |
| impl<'tcx> MirPass<'tcx> for CopyPropagation { |
| fn run_pass( |
| &self, tcx: TyCtxt<'tcx>, _source: MirSource<'tcx>, body: &mut BodyAndCache<'tcx> |
| ) { |
| // We only run when the MIR optimization level is > 1. |
| // This avoids a slow pass, and messing up debug info. |
| if tcx.sess.opts.debugging_opts.mir_opt_level <= 1 { |
| return; |
| } |
| |
| let mut def_use_analysis = DefUseAnalysis::new(body); |
| loop { |
| def_use_analysis.analyze(read_only!(body)); |
| |
| if eliminate_self_assignments(body, &def_use_analysis) { |
| def_use_analysis.analyze(read_only!(body)); |
| } |
| |
| let mut changed = false; |
| for dest_local in body.local_decls.indices() { |
| debug!("considering destination local: {:?}", dest_local); |
| |
| let action; |
| let location; |
| { |
| // The destination must have exactly one def. |
| let dest_use_info = def_use_analysis.local_info(dest_local); |
| let dest_def_count = dest_use_info.def_count_not_including_drop(); |
| if dest_def_count == 0 { |
| debug!(" Can't copy-propagate local: dest {:?} undefined", |
| dest_local); |
| continue |
| } |
| if dest_def_count > 1 { |
| debug!(" Can't copy-propagate local: dest {:?} defined {} times", |
| dest_local, |
| dest_use_info.def_count()); |
| continue |
| } |
| if dest_use_info.use_count() == 0 { |
| debug!(" Can't copy-propagate local: dest {:?} unused", |
| dest_local); |
| continue |
| } |
| // Conservatively gives up if the dest is an argument, |
| // because there may be uses of the original argument value. |
| if body.local_kind(dest_local) == LocalKind::Arg { |
| debug!(" Can't copy-propagate local: dest {:?} (argument)", |
| dest_local); |
| continue; |
| } |
| let dest_place_def = dest_use_info.defs_not_including_drop().next().unwrap(); |
| location = dest_place_def.location; |
| |
| let basic_block = &body[location.block]; |
| let statement_index = location.statement_index; |
| let statement = match basic_block.statements.get(statement_index) { |
| Some(statement) => statement, |
| None => { |
| debug!(" Can't copy-propagate local: used in terminator"); |
| continue |
| } |
| }; |
| |
| // That use of the source must be an assignment. |
| match &statement.kind { |
| StatementKind::Assign(box(place, Rvalue::Use(operand))) => { |
| if let Some(local) = place.as_local() { |
| if local == dest_local { |
| let maybe_action = match operand { |
| Operand::Copy(ref src_place) | |
| Operand::Move(ref src_place) => { |
| Action::local_copy( |
| &body, |
| &def_use_analysis, |
| src_place) |
| } |
| Operand::Constant(ref src_constant) => { |
| Action::constant(src_constant) |
| } |
| }; |
| match maybe_action { |
| Some(this_action) => action = this_action, |
| None => continue, |
| } |
| } else { |
| debug!(" Can't copy-propagate local: source use is not an \ |
| assignment"); |
| continue |
| } |
| } else { |
| debug!(" Can't copy-propagate local: source use is not an \ |
| assignment"); |
| continue |
| } |
| } |
| _ => { |
| debug!(" Can't copy-propagate local: source use is not an \ |
| assignment"); |
| continue |
| } |
| } |
| } |
| |
| changed = action.perform(body, &def_use_analysis, dest_local, location, tcx) |
| || changed; |
| // FIXME(pcwalton): Update the use-def chains to delete the instructions instead of |
| // regenerating the chains. |
| break |
| } |
| if !changed { |
| break |
| } |
| } |
| } |
| } |
| |
| fn eliminate_self_assignments( |
| body: &mut Body<'_>, |
| def_use_analysis: &DefUseAnalysis, |
| ) -> bool { |
| let mut changed = false; |
| |
| for dest_local in body.local_decls.indices() { |
| let dest_use_info = def_use_analysis.local_info(dest_local); |
| |
| for def in dest_use_info.defs_not_including_drop() { |
| let location = def.location; |
| if let Some(stmt) = body[location.block].statements.get(location.statement_index) { |
| match &stmt.kind { |
| StatementKind::Assign(box (place, Rvalue::Use(Operand::Copy(src_place)))) |
| | StatementKind::Assign(box (place, Rvalue::Use(Operand::Move(src_place)))) => { |
| if let (Some(local), Some(src_local)) = |
| (place.as_local(), src_place.as_local()) |
| { |
| if local == dest_local && dest_local == src_local { |
| } else { |
| continue; |
| } |
| } else { |
| continue; |
| } |
| } |
| _ => { |
| continue; |
| } |
| } |
| } else { |
| continue; |
| } |
| debug!("deleting a self-assignment for {:?}", dest_local); |
| body.make_statement_nop(location); |
| changed = true; |
| } |
| } |
| |
| changed |
| } |
| |
| enum Action<'tcx> { |
| PropagateLocalCopy(Local), |
| PropagateConstant(Constant<'tcx>), |
| } |
| |
| impl<'tcx> Action<'tcx> { |
| fn local_copy(body: &Body<'tcx>, def_use_analysis: &DefUseAnalysis, src_place: &Place<'tcx>) |
| -> Option<Action<'tcx>> { |
| // The source must be a local. |
| let src_local = if let Some(local) = src_place.as_local() { |
| local |
| } else { |
| debug!(" Can't copy-propagate local: source is not a local"); |
| return None; |
| }; |
| |
| // We're trying to copy propagate a local. |
| // There must be exactly one use of the source used in a statement (not in a terminator). |
| let src_use_info = def_use_analysis.local_info(src_local); |
| let src_use_count = src_use_info.use_count(); |
| if src_use_count == 0 { |
| debug!(" Can't copy-propagate local: no uses"); |
| return None |
| } |
| if src_use_count != 1 { |
| debug!(" Can't copy-propagate local: {} uses", src_use_info.use_count()); |
| return None |
| } |
| |
| // Verify that the source doesn't change in between. This is done conservatively for now, |
| // by ensuring that the source has exactly one mutation. The goal is to prevent things |
| // like: |
| // |
| // DEST = SRC; |
| // SRC = X; |
| // USE(DEST); |
| // |
| // From being misoptimized into: |
| // |
| // SRC = X; |
| // USE(SRC); |
| let src_def_count = src_use_info.def_count_not_including_drop(); |
| // allow function arguments to be propagated |
| let is_arg = body.local_kind(src_local) == LocalKind::Arg; |
| if (is_arg && src_def_count != 0) || (!is_arg && src_def_count != 1) { |
| debug!( |
| " Can't copy-propagate local: {} defs of src{}", |
| src_def_count, |
| if is_arg { " (argument)" } else { "" }, |
| ); |
| return None |
| } |
| |
| Some(Action::PropagateLocalCopy(src_local)) |
| } |
| |
| fn constant(src_constant: &Constant<'tcx>) -> Option<Action<'tcx>> { |
| Some(Action::PropagateConstant((*src_constant).clone())) |
| } |
| |
| fn perform(self, |
| body: &mut BodyAndCache<'tcx>, |
| def_use_analysis: &DefUseAnalysis, |
| dest_local: Local, |
| location: Location, |
| tcx: TyCtxt<'tcx>) |
| -> bool { |
| match self { |
| Action::PropagateLocalCopy(src_local) => { |
| // Eliminate the destination and the assignment. |
| // |
| // First, remove all markers. |
| // |
| // FIXME(pcwalton): Don't do this. Merge live ranges instead. |
| debug!(" Replacing all uses of {:?} with {:?} (local)", |
| dest_local, |
| src_local); |
| for place_use in &def_use_analysis.local_info(dest_local).defs_and_uses { |
| if place_use.context.is_storage_marker() { |
| body.make_statement_nop(place_use.location) |
| } |
| } |
| for place_use in &def_use_analysis.local_info(src_local).defs_and_uses { |
| if place_use.context.is_storage_marker() { |
| body.make_statement_nop(place_use.location) |
| } |
| } |
| |
| // Replace all uses of the destination local with the source local. |
| def_use_analysis |
| .replace_all_defs_and_uses_with(dest_local, body, src_local, tcx); |
| |
| // Finally, zap the now-useless assignment instruction. |
| debug!(" Deleting assignment"); |
| body.make_statement_nop(location); |
| |
| true |
| } |
| Action::PropagateConstant(src_constant) => { |
| // First, remove all markers. |
| // |
| // FIXME(pcwalton): Don't do this. Merge live ranges instead. |
| debug!(" Replacing all uses of {:?} with {:?} (constant)", |
| dest_local, |
| src_constant); |
| let dest_local_info = def_use_analysis.local_info(dest_local); |
| for place_use in &dest_local_info.defs_and_uses { |
| if place_use.context.is_storage_marker() { |
| body.make_statement_nop(place_use.location) |
| } |
| } |
| |
| // Replace all uses of the destination local with the constant. |
| let mut visitor = ConstantPropagationVisitor::new(dest_local, |
| src_constant, |
| tcx); |
| for dest_place_use in &dest_local_info.defs_and_uses { |
| visitor.visit_location(body, dest_place_use.location) |
| } |
| |
| // Zap the assignment instruction if we eliminated all the uses. We won't have been |
| // able to do that if the destination was used in a projection, because projections |
| // must have places on their LHS. |
| let use_count = dest_local_info.use_count(); |
| if visitor.uses_replaced == use_count { |
| debug!(" {} of {} use(s) replaced; deleting assignment", |
| visitor.uses_replaced, |
| use_count); |
| body.make_statement_nop(location); |
| true |
| } else if visitor.uses_replaced == 0 { |
| debug!(" No uses replaced; not deleting assignment"); |
| false |
| } else { |
| debug!(" {} of {} use(s) replaced; not deleting assignment", |
| visitor.uses_replaced, |
| use_count); |
| true |
| } |
| } |
| } |
| } |
| } |
| |
| struct ConstantPropagationVisitor<'tcx> { |
| dest_local: Local, |
| constant: Constant<'tcx>, |
| tcx: TyCtxt<'tcx>, |
| uses_replaced: usize, |
| } |
| |
| impl<'tcx> ConstantPropagationVisitor<'tcx> { |
| fn new(dest_local: Local, constant: Constant<'tcx>, tcx: TyCtxt<'tcx>) |
| -> ConstantPropagationVisitor<'tcx> { |
| ConstantPropagationVisitor { |
| dest_local, |
| constant, |
| tcx, |
| uses_replaced: 0, |
| } |
| } |
| } |
| |
| impl<'tcx> MutVisitor<'tcx> for ConstantPropagationVisitor<'tcx> { |
| fn tcx(&self) -> TyCtxt<'tcx> { |
| self.tcx |
| } |
| |
| fn visit_operand(&mut self, operand: &mut Operand<'tcx>, location: Location) { |
| self.super_operand(operand, location); |
| |
| match operand { |
| Operand::Copy(place) | |
| Operand::Move(place) => { |
| if let Some(local) = place.as_local() { |
| if local == self.dest_local { |
| } else { |
| return; |
| } |
| } else { |
| return; |
| } |
| } |
| _ => return, |
| } |
| |
| *operand = Operand::Constant(box self.constant.clone()); |
| self.uses_replaced += 1 |
| } |
| } |