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
23 Constant, Local, LocalKind, Location, Place, PlaceBase, Body, Operand, Rvalue, StatementKind
25 use rustc::mir::visit::MutVisitor;
26 use rustc::ty::TyCtxt;
27 use crate::transform::{MirPass, MirSource};
28 use crate::util::def_use::DefUseAnalysis;
30 pub struct CopyPropagation;
32 impl MirPass for CopyPropagation {
33 fn run_pass<'tcx>(&self,
34 tcx: TyCtxt<'tcx, 'tcx, 'tcx>,
35 _source: MirSource<'tcx>,
36 body: &mut Body<'tcx>) {
37 // We only run when the MIR optimization level is > 1.
38 // This avoids a slow pass, and messing up debug info.
39 if tcx.sess.opts.debugging_opts.mir_opt_level <= 1 {
43 let mut def_use_analysis = DefUseAnalysis::new(body);
45 def_use_analysis.analyze(body);
47 if eliminate_self_assignments(body, &def_use_analysis) {
48 def_use_analysis.analyze(body);
51 let mut changed = false;
52 for dest_local in body.local_decls.indices() {
53 debug!("Considering destination local: {:?}", dest_local);
58 // The destination must have exactly one def.
59 let dest_use_info = def_use_analysis.local_info(dest_local);
60 let dest_def_count = dest_use_info.def_count_not_including_drop();
61 if dest_def_count == 0 {
62 debug!(" Can't copy-propagate local: dest {:?} undefined",
66 if dest_def_count > 1 {
67 debug!(" Can't copy-propagate local: dest {:?} defined {} times",
69 dest_use_info.def_count());
72 if dest_use_info.use_count() == 0 {
73 debug!(" Can't copy-propagate local: dest {:?} unused",
77 // Conservatively gives up if the dest is an argument,
78 // because there may be uses of the original argument value.
79 if body.local_kind(dest_local) == LocalKind::Arg {
80 debug!(" Can't copy-propagate local: dest {:?} (argument)",
84 let dest_place_def = dest_use_info.defs_not_including_drop().next().unwrap();
85 location = dest_place_def.location;
87 let basic_block = &body[location.block];
88 let statement_index = location.statement_index;
89 let statement = match basic_block.statements.get(statement_index) {
90 Some(statement) => statement,
92 debug!(" Can't copy-propagate local: used in terminator");
97 // That use of the source must be an assignment.
98 match statement.kind {
99 StatementKind::Assign(
100 Place::Base(PlaceBase::Local(local)),
101 box Rvalue::Use(ref operand)
102 ) if local == dest_local => {
103 let maybe_action = match *operand {
104 Operand::Copy(ref src_place) |
105 Operand::Move(ref src_place) => {
106 Action::local_copy(&body, &def_use_analysis, src_place)
108 Operand::Constant(ref src_constant) => {
109 Action::constant(src_constant)
113 Some(this_action) => action = this_action,
118 debug!(" Can't copy-propagate local: source use is not an \
125 changed = action.perform(body, &def_use_analysis, dest_local, location) || changed;
126 // FIXME(pcwalton): Update the use-def chains to delete the instructions instead of
127 // regenerating the chains.
137 fn eliminate_self_assignments(
139 def_use_analysis: &DefUseAnalysis,
141 let mut changed = false;
143 for dest_local in body.local_decls.indices() {
144 let dest_use_info = def_use_analysis.local_info(dest_local);
146 for def in dest_use_info.defs_not_including_drop() {
147 let location = def.location;
148 if let Some(stmt) = body[location.block].statements.get(location.statement_index) {
150 StatementKind::Assign(
151 Place::Base(PlaceBase::Local(local)),
152 box Rvalue::Use(Operand::Copy(Place::Base(PlaceBase::Local(src_local)))),
154 StatementKind::Assign(
155 Place::Base(PlaceBase::Local(local)),
156 box Rvalue::Use(Operand::Move(Place::Base(PlaceBase::Local(src_local)))),
157 ) if local == dest_local && dest_local == src_local => {}
165 debug!("Deleting a self-assignment for {:?}", dest_local);
166 body.make_statement_nop(location);
175 PropagateLocalCopy(Local),
176 PropagateConstant(Constant<'tcx>),
179 impl<'tcx> Action<'tcx> {
180 fn local_copy(body: &Body<'tcx>, def_use_analysis: &DefUseAnalysis, src_place: &Place<'tcx>)
181 -> Option<Action<'tcx>> {
182 // The source must be a local.
183 let src_local = if let Place::Base(PlaceBase::Local(local)) = *src_place {
186 debug!(" Can't copy-propagate local: source is not a local");
190 // We're trying to copy propagate a local.
191 // There must be exactly one use of the source used in a statement (not in a terminator).
192 let src_use_info = def_use_analysis.local_info(src_local);
193 let src_use_count = src_use_info.use_count();
194 if src_use_count == 0 {
195 debug!(" Can't copy-propagate local: no uses");
198 if src_use_count != 1 {
199 debug!(" Can't copy-propagate local: {} uses", src_use_info.use_count());
203 // Verify that the source doesn't change in between. This is done conservatively for now,
204 // by ensuring that the source has exactly one mutation. The goal is to prevent things
211 // From being misoptimized into:
215 let src_def_count = src_use_info.def_count_not_including_drop();
216 // allow function arguments to be propagated
217 let is_arg = body.local_kind(src_local) == LocalKind::Arg;
218 if (is_arg && src_def_count != 0) || (!is_arg && src_def_count != 1) {
220 " Can't copy-propagate local: {} defs of src{}",
222 if is_arg { " (argument)" } else { "" },
227 Some(Action::PropagateLocalCopy(src_local))
230 fn constant(src_constant: &Constant<'tcx>) -> Option<Action<'tcx>> {
231 Some(Action::PropagateConstant((*src_constant).clone()))
235 body: &mut Body<'tcx>,
236 def_use_analysis: &DefUseAnalysis,
241 Action::PropagateLocalCopy(src_local) => {
242 // Eliminate the destination and the assignment.
244 // First, remove all markers.
246 // FIXME(pcwalton): Don't do this. Merge live ranges instead.
247 debug!(" Replacing all uses of {:?} with {:?} (local)",
250 for place_use in &def_use_analysis.local_info(dest_local).defs_and_uses {
251 if place_use.context.is_storage_marker() {
252 body.make_statement_nop(place_use.location)
255 for place_use in &def_use_analysis.local_info(src_local).defs_and_uses {
256 if place_use.context.is_storage_marker() {
257 body.make_statement_nop(place_use.location)
261 // Replace all uses of the destination local with the source local.
262 def_use_analysis.replace_all_defs_and_uses_with(dest_local, body, src_local);
264 // Finally, zap the now-useless assignment instruction.
265 debug!(" Deleting assignment");
266 body.make_statement_nop(location);
270 Action::PropagateConstant(src_constant) => {
271 // First, remove all markers.
273 // FIXME(pcwalton): Don't do this. Merge live ranges instead.
274 debug!(" Replacing all uses of {:?} with {:?} (constant)",
277 let dest_local_info = def_use_analysis.local_info(dest_local);
278 for place_use in &dest_local_info.defs_and_uses {
279 if place_use.context.is_storage_marker() {
280 body.make_statement_nop(place_use.location)
284 // Replace all uses of the destination local with the constant.
285 let mut visitor = ConstantPropagationVisitor::new(dest_local,
287 for dest_place_use in &dest_local_info.defs_and_uses {
288 visitor.visit_location(body, dest_place_use.location)
291 // Zap the assignment instruction if we eliminated all the uses. We won't have been
292 // able to do that if the destination was used in a projection, because projections
293 // must have places on their LHS.
294 let use_count = dest_local_info.use_count();
295 if visitor.uses_replaced == use_count {
296 debug!(" {} of {} use(s) replaced; deleting assignment",
297 visitor.uses_replaced,
299 body.make_statement_nop(location);
301 } else if visitor.uses_replaced == 0 {
302 debug!(" No uses replaced; not deleting assignment");
305 debug!(" {} of {} use(s) replaced; not deleting assignment",
306 visitor.uses_replaced,
315 struct ConstantPropagationVisitor<'tcx> {
317 constant: Constant<'tcx>,
318 uses_replaced: usize,
321 impl<'tcx> ConstantPropagationVisitor<'tcx> {
322 fn new(dest_local: Local, constant: Constant<'tcx>)
323 -> ConstantPropagationVisitor<'tcx> {
324 ConstantPropagationVisitor {
332 impl<'tcx> MutVisitor<'tcx> for ConstantPropagationVisitor<'tcx> {
333 fn visit_operand(&mut self, operand: &mut Operand<'tcx>, location: Location) {
334 self.super_operand(operand, location);
337 Operand::Copy(Place::Base(PlaceBase::Local(local))) |
338 Operand::Move(Place::Base(PlaceBase::Local(local))) if local == self.dest_local => {}
342 *operand = Operand::Constant(box self.constant.clone());
343 self.uses_replaced += 1