1 //! Trivial copy propagation pass.
3 //! This uses def-use analysis to remove values that have exactly one def and one use, which must
6 //! To give an example, we look for patterns that look like:
12 //! where `DEST` and `SRC` are both locals of some form. We replace that with:
18 //! The assignment `DEST = SRC` must be (a) the only mutation of `DEST` and (b) the only
19 //! (non-mutating) use of `SRC`. These restrictions are conservative and may be relaxed in the
22 use crate::transform::{MirPass, MirSource};
23 use crate::util::def_use::DefUseAnalysis;
24 use rustc::mir::visit::MutVisitor;
26 read_only, Body, BodyAndCache, Constant, Local, LocalKind, Location, Operand, Place, Rvalue,
29 use rustc::ty::TyCtxt;
31 pub struct CopyPropagation;
33 impl<'tcx> MirPass<'tcx> for CopyPropagation {
34 fn run_pass(&self, tcx: TyCtxt<'tcx>, _source: MirSource<'tcx>, body: &mut BodyAndCache<'tcx>) {
35 // We only run when the MIR optimization level is > 1.
36 // This avoids a slow pass, and messing up debug info.
37 if tcx.sess.opts.debugging_opts.mir_opt_level <= 1 {
41 let mut def_use_analysis = DefUseAnalysis::new(body);
43 def_use_analysis.analyze(read_only!(body));
45 if eliminate_self_assignments(body, &def_use_analysis) {
46 def_use_analysis.analyze(read_only!(body));
49 let mut changed = false;
50 for dest_local in body.local_decls.indices() {
51 debug!("considering destination local: {:?}", dest_local);
56 // The destination must have exactly one def.
57 let dest_use_info = def_use_analysis.local_info(dest_local);
58 let dest_def_count = dest_use_info.def_count_not_including_drop();
59 if dest_def_count == 0 {
60 debug!(" Can't copy-propagate local: dest {:?} undefined", dest_local);
63 if dest_def_count > 1 {
65 " Can't copy-propagate local: dest {:?} defined {} times",
67 dest_use_info.def_count()
71 if dest_use_info.use_count() == 0 {
72 debug!(" Can't copy-propagate local: dest {:?} unused", dest_local);
75 // Conservatively gives up if the dest is an argument,
76 // because there may be uses of the original argument value.
77 if body.local_kind(dest_local) == LocalKind::Arg {
78 debug!(" Can't copy-propagate local: dest {:?} (argument)", dest_local);
81 let dest_place_def = dest_use_info.defs_not_including_drop().next().unwrap();
82 location = dest_place_def.location;
84 let basic_block = &body[location.block];
85 let statement_index = location.statement_index;
86 let statement = match basic_block.statements.get(statement_index) {
87 Some(statement) => statement,
89 debug!(" Can't copy-propagate local: used in terminator");
94 // That use of the source must be an assignment.
95 match &statement.kind {
96 StatementKind::Assign(box (place, Rvalue::Use(operand))) => {
97 if let Some(local) = place.as_local() {
98 if local == dest_local {
99 let maybe_action = match operand {
100 Operand::Copy(ref src_place)
101 | Operand::Move(ref src_place) => {
102 Action::local_copy(&body, &def_use_analysis, src_place)
104 Operand::Constant(ref src_constant) => {
105 Action::constant(src_constant)
109 Some(this_action) => action = this_action,
114 " Can't copy-propagate local: source use is not an \
121 " Can't copy-propagate local: source use is not an \
129 " Can't copy-propagate local: source use is not an \
138 action.perform(body, &def_use_analysis, dest_local, location, tcx) || changed;
139 // FIXME(pcwalton): Update the use-def chains to delete the instructions instead of
140 // regenerating the chains.
150 fn eliminate_self_assignments(body: &mut Body<'_>, def_use_analysis: &DefUseAnalysis) -> bool {
151 let mut changed = false;
153 for dest_local in body.local_decls.indices() {
154 let dest_use_info = def_use_analysis.local_info(dest_local);
156 for def in dest_use_info.defs_not_including_drop() {
157 let location = def.location;
158 if let Some(stmt) = body[location.block].statements.get(location.statement_index) {
160 StatementKind::Assign(box (place, Rvalue::Use(Operand::Copy(src_place))))
161 | StatementKind::Assign(box (place, Rvalue::Use(Operand::Move(src_place)))) => {
162 if let (Some(local), Some(src_local)) =
163 (place.as_local(), src_place.as_local())
165 if local == dest_local && dest_local == src_local {
180 debug!("deleting a self-assignment for {:?}", dest_local);
181 body.make_statement_nop(location);
190 PropagateLocalCopy(Local),
191 PropagateConstant(Constant<'tcx>),
194 impl<'tcx> Action<'tcx> {
197 def_use_analysis: &DefUseAnalysis,
198 src_place: &Place<'tcx>,
199 ) -> Option<Action<'tcx>> {
200 // The source must be a local.
201 let src_local = if let Some(local) = src_place.as_local() {
204 debug!(" Can't copy-propagate local: source is not a local");
208 // We're trying to copy propagate a local.
209 // There must be exactly one use of the source used in a statement (not in a terminator).
210 let src_use_info = def_use_analysis.local_info(src_local);
211 let src_use_count = src_use_info.use_count();
212 if src_use_count == 0 {
213 debug!(" Can't copy-propagate local: no uses");
216 if src_use_count != 1 {
217 debug!(" Can't copy-propagate local: {} uses", src_use_info.use_count());
221 // Verify that the source doesn't change in between. This is done conservatively for now,
222 // by ensuring that the source has exactly one mutation. The goal is to prevent things
229 // From being misoptimized into:
233 let src_def_count = src_use_info.def_count_not_including_drop();
234 // allow function arguments to be propagated
235 let is_arg = body.local_kind(src_local) == LocalKind::Arg;
236 if (is_arg && src_def_count != 0) || (!is_arg && src_def_count != 1) {
238 " Can't copy-propagate local: {} defs of src{}",
240 if is_arg { " (argument)" } else { "" },
245 Some(Action::PropagateLocalCopy(src_local))
248 fn constant(src_constant: &Constant<'tcx>) -> Option<Action<'tcx>> {
249 Some(Action::PropagateConstant((*src_constant).clone()))
254 body: &mut BodyAndCache<'tcx>,
255 def_use_analysis: &DefUseAnalysis,
261 Action::PropagateLocalCopy(src_local) => {
262 // Eliminate the destination and the assignment.
264 // First, remove all markers.
266 // FIXME(pcwalton): Don't do this. Merge live ranges instead.
267 debug!(" Replacing all uses of {:?} with {:?} (local)", dest_local, src_local);
268 for place_use in &def_use_analysis.local_info(dest_local).defs_and_uses {
269 if place_use.context.is_storage_marker() {
270 body.make_statement_nop(place_use.location)
273 for place_use in &def_use_analysis.local_info(src_local).defs_and_uses {
274 if place_use.context.is_storage_marker() {
275 body.make_statement_nop(place_use.location)
279 // Replace all uses of the destination local with the source local.
280 def_use_analysis.replace_all_defs_and_uses_with(dest_local, body, src_local, tcx);
282 // Finally, zap the now-useless assignment instruction.
283 debug!(" Deleting assignment");
284 body.make_statement_nop(location);
288 Action::PropagateConstant(src_constant) => {
289 // First, remove all markers.
291 // FIXME(pcwalton): Don't do this. Merge live ranges instead.
293 " Replacing all uses of {:?} with {:?} (constant)",
294 dest_local, src_constant
296 let dest_local_info = def_use_analysis.local_info(dest_local);
297 for place_use in &dest_local_info.defs_and_uses {
298 if place_use.context.is_storage_marker() {
299 body.make_statement_nop(place_use.location)
303 // Replace all uses of the destination local with the constant.
304 let mut visitor = ConstantPropagationVisitor::new(dest_local, src_constant, tcx);
305 for dest_place_use in &dest_local_info.defs_and_uses {
306 visitor.visit_location(body, dest_place_use.location)
309 // Zap the assignment instruction if we eliminated all the uses. We won't have been
310 // able to do that if the destination was used in a projection, because projections
311 // must have places on their LHS.
312 let use_count = dest_local_info.use_count();
313 if visitor.uses_replaced == use_count {
315 " {} of {} use(s) replaced; deleting assignment",
316 visitor.uses_replaced, use_count
318 body.make_statement_nop(location);
320 } else if visitor.uses_replaced == 0 {
321 debug!(" No uses replaced; not deleting assignment");
325 " {} of {} use(s) replaced; not deleting assignment",
326 visitor.uses_replaced, use_count
335 struct ConstantPropagationVisitor<'tcx> {
337 constant: Constant<'tcx>,
339 uses_replaced: usize,
342 impl<'tcx> ConstantPropagationVisitor<'tcx> {
345 constant: Constant<'tcx>,
347 ) -> ConstantPropagationVisitor<'tcx> {
348 ConstantPropagationVisitor { dest_local, constant, tcx, uses_replaced: 0 }
352 impl<'tcx> MutVisitor<'tcx> for ConstantPropagationVisitor<'tcx> {
353 fn tcx(&self) -> TyCtxt<'tcx> {
357 fn visit_operand(&mut self, operand: &mut Operand<'tcx>, location: Location) {
358 self.super_operand(operand, location);
361 Operand::Copy(place) | Operand::Move(place) => {
362 if let Some(local) = place.as_local() {
363 if local == self.dest_local {
374 *operand = Operand::Constant(box self.constant.clone());
375 self.uses_replaced += 1