1 // Copyright 2016 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 //! Trivial copy propagation pass.
13 //! This uses def-use analysis to remove values that have exactly one def and one use, which must
16 //! To give an example, we look for patterns that look like:
22 //! where `DEST` and `SRC` are both locals of some form. We replace that with:
28 //! The assignment `DEST = SRC` must be (a) the only mutation of `DEST` and (b) the only
29 //! (non-mutating) use of `SRC`. These restrictions are conservative and may be relaxed in the
32 use def_use::DefUseAnalysis;
33 use rustc::mir::{Constant, Local, LocalKind, Location, Lvalue, Mir, Operand, Rvalue, StatementKind};
34 use rustc::mir::transform::{MirPass, MirSource, Pass};
35 use rustc::mir::visit::MutVisitor;
36 use rustc::ty::TyCtxt;
37 use transform::qualify_consts;
39 pub struct CopyPropagation;
41 impl Pass for CopyPropagation {}
43 impl<'tcx> MirPass<'tcx> for CopyPropagation {
44 fn run_pass<'a>(&mut self,
45 tcx: TyCtxt<'a, 'tcx, 'tcx>,
47 mir: &mut Mir<'tcx>) {
49 MirSource::Const(_) => {
50 // Don't run on constants, because constant qualification might reject the
54 MirSource::Static(..) | MirSource::Promoted(..) => {
55 // Don't run on statics and promoted statics, because trans might not be able to
56 // evaluate the optimized IR.
59 MirSource::Fn(function_node_id) => {
60 if qualify_consts::is_const_fn(tcx, tcx.hir.local_def_id(function_node_id)) {
61 // Don't run on const functions, as, again, trans might not be able to evaluate
68 // We only run when the MIR optimization level is > 1.
69 // This avoids a slow pass, and messing up debug info.
70 if tcx.sess.opts.debugging_opts.mir_opt_level <= 1 {
75 let mut def_use_analysis = DefUseAnalysis::new(mir);
76 def_use_analysis.analyze(mir);
78 let mut changed = false;
79 for dest_local in mir.local_decls.indices() {
80 debug!("Considering destination local: {:?}", dest_local);
85 // The destination must have exactly one def.
86 let dest_use_info = def_use_analysis.local_info(dest_local);
87 let dest_def_count = dest_use_info.def_count_not_including_drop();
88 if dest_def_count == 0 {
89 debug!(" Can't copy-propagate local: dest {:?} undefined",
93 if dest_def_count > 1 {
94 debug!(" Can't copy-propagate local: dest {:?} defined {} times",
96 dest_use_info.def_count());
99 if dest_use_info.use_count() == 0 {
100 debug!(" Can't copy-propagate local: dest {:?} unused",
104 let dest_lvalue_def = dest_use_info.defs_and_uses.iter().filter(|lvalue_def| {
105 lvalue_def.context.is_mutating_use() && !lvalue_def.context.is_drop()
107 location = dest_lvalue_def.location;
109 let basic_block = &mir[location.block];
110 let statement_index = location.statement_index;
111 let statement = match basic_block.statements.get(statement_index) {
112 Some(statement) => statement,
114 debug!(" Can't copy-propagate local: used in terminator");
119 // That use of the source must be an assignment.
120 match statement.kind {
121 StatementKind::Assign(Lvalue::Local(local), Rvalue::Use(ref operand)) if
122 local == dest_local => {
123 let maybe_action = match *operand {
124 Operand::Consume(ref src_lvalue) => {
125 Action::local_copy(&mir, &def_use_analysis, src_lvalue)
127 Operand::Constant(ref src_constant) => {
128 Action::constant(src_constant)
132 Some(this_action) => action = this_action,
137 debug!(" Can't copy-propagate local: source use is not an \
144 changed = action.perform(mir, &def_use_analysis, dest_local, location) || changed;
145 // FIXME(pcwalton): Update the use-def chains to delete the instructions instead of
146 // regenerating the chains.
157 PropagateLocalCopy(Local),
158 PropagateConstant(Constant<'tcx>),
161 impl<'tcx> Action<'tcx> {
162 fn local_copy(mir: &Mir<'tcx>, def_use_analysis: &DefUseAnalysis, src_lvalue: &Lvalue<'tcx>)
163 -> Option<Action<'tcx>> {
164 // The source must be a local.
165 let src_local = if let Lvalue::Local(local) = *src_lvalue {
168 debug!(" Can't copy-propagate local: source is not a local");
172 // We're trying to copy propagate a local.
173 // There must be exactly one use of the source used in a statement (not in a terminator).
174 let src_use_info = def_use_analysis.local_info(src_local);
175 let src_use_count = src_use_info.use_count();
176 if src_use_count == 0 {
177 debug!(" Can't copy-propagate local: no uses");
180 if src_use_count != 1 {
181 debug!(" Can't copy-propagate local: {} uses", src_use_info.use_count());
185 // Verify that the source doesn't change in between. This is done conservatively for now,
186 // by ensuring that the source has exactly one mutation. The goal is to prevent things
193 // From being misoptimized into:
197 let src_def_count = src_use_info.def_count_not_including_drop();
198 // allow function arguments to be propagated
199 if src_def_count > 1 ||
200 (src_def_count == 0 && mir.local_kind(src_local) != LocalKind::Arg) {
201 debug!(" Can't copy-propagate local: {} defs of src",
202 src_use_info.def_count_not_including_drop());
206 Some(Action::PropagateLocalCopy(src_local))
209 fn constant(src_constant: &Constant<'tcx>) -> Option<Action<'tcx>> {
210 Some(Action::PropagateConstant((*src_constant).clone()))
215 def_use_analysis: &DefUseAnalysis<'tcx>,
220 Action::PropagateLocalCopy(src_local) => {
221 // Eliminate the destination and the assignment.
223 // First, remove all markers.
225 // FIXME(pcwalton): Don't do this. Merge live ranges instead.
226 debug!(" Replacing all uses of {:?} with {:?} (local)",
229 for lvalue_use in &def_use_analysis.local_info(dest_local).defs_and_uses {
230 if lvalue_use.context.is_storage_marker() {
231 mir.make_statement_nop(lvalue_use.location)
234 for lvalue_use in &def_use_analysis.local_info(src_local).defs_and_uses {
235 if lvalue_use.context.is_storage_marker() {
236 mir.make_statement_nop(lvalue_use.location)
240 // Replace all uses of the destination local with the source local.
241 let src_lvalue = Lvalue::Local(src_local);
242 def_use_analysis.replace_all_defs_and_uses_with(dest_local, mir, src_lvalue);
244 // Finally, zap the now-useless assignment instruction.
245 debug!(" Deleting assignment");
246 mir.make_statement_nop(location);
250 Action::PropagateConstant(src_constant) => {
251 // First, remove all markers.
253 // FIXME(pcwalton): Don't do this. Merge live ranges instead.
254 debug!(" Replacing all uses of {:?} with {:?} (constant)",
257 let dest_local_info = def_use_analysis.local_info(dest_local);
258 for lvalue_use in &dest_local_info.defs_and_uses {
259 if lvalue_use.context.is_storage_marker() {
260 mir.make_statement_nop(lvalue_use.location)
264 // Replace all uses of the destination local with the constant.
265 let mut visitor = ConstantPropagationVisitor::new(dest_local,
267 for dest_lvalue_use in &dest_local_info.defs_and_uses {
268 visitor.visit_location(mir, dest_lvalue_use.location)
271 // Zap the assignment instruction if we eliminated all the uses. We won't have been
272 // able to do that if the destination was used in a projection, because projections
273 // must have lvalues on their LHS.
274 let use_count = dest_local_info.use_count();
275 if visitor.uses_replaced == use_count {
276 debug!(" {} of {} use(s) replaced; deleting assignment",
277 visitor.uses_replaced,
279 mir.make_statement_nop(location);
281 } else if visitor.uses_replaced == 0 {
282 debug!(" No uses replaced; not deleting assignment");
285 debug!(" {} of {} use(s) replaced; not deleting assignment",
286 visitor.uses_replaced,
295 struct ConstantPropagationVisitor<'tcx> {
297 constant: Constant<'tcx>,
298 uses_replaced: usize,
301 impl<'tcx> ConstantPropagationVisitor<'tcx> {
302 fn new(dest_local: Local, constant: Constant<'tcx>)
303 -> ConstantPropagationVisitor<'tcx> {
304 ConstantPropagationVisitor {
305 dest_local: dest_local,
312 impl<'tcx> MutVisitor<'tcx> for ConstantPropagationVisitor<'tcx> {
313 fn visit_operand(&mut self, operand: &mut Operand<'tcx>, location: Location) {
314 self.super_operand(operand, location);
317 Operand::Consume(Lvalue::Local(local)) if local == self.dest_local => {}
321 *operand = Operand::Constant(self.constant.clone());
322 self.uses_replaced += 1