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 rustc::mir::{Constant, Local, LocalKind, Location, Lvalue, Mir, Operand, Rvalue, StatementKind};
33 use rustc::mir::transform::{MirPass, MirSource};
34 use rustc::mir::visit::MutVisitor;
35 use rustc::ty::TyCtxt;
36 use util::def_use::DefUseAnalysis;
37 use transform::qualify_consts;
39 pub struct CopyPropagation;
41 impl MirPass for CopyPropagation {
42 fn run_pass<'a, 'tcx>(&self,
43 tcx: TyCtxt<'a, 'tcx, 'tcx>,
45 mir: &mut Mir<'tcx>) {
47 MirSource::Const(_) => {
48 // Don't run on constants, because constant qualification might reject the
52 MirSource::Static(..) | MirSource::Promoted(..) => {
53 // Don't run on statics and promoted statics, because trans might not be able to
54 // evaluate the optimized IR.
57 MirSource::Fn(function_node_id) => {
58 if qualify_consts::is_const_fn(tcx, tcx.hir.local_def_id(function_node_id)) {
59 // Don't run on const functions, as, again, trans might not be able to evaluate
66 // We only run when the MIR optimization level is > 1.
67 // This avoids a slow pass, and messing up debug info.
68 if tcx.sess.opts.debugging_opts.mir_opt_level <= 1 {
73 let mut def_use_analysis = DefUseAnalysis::new(mir);
74 def_use_analysis.analyze(mir);
76 let mut changed = false;
77 for dest_local in mir.local_decls.indices() {
78 debug!("Considering destination local: {:?}", dest_local);
83 // The destination must have exactly one def.
84 let dest_use_info = def_use_analysis.local_info(dest_local);
85 let dest_def_count = dest_use_info.def_count_not_including_drop();
86 if dest_def_count == 0 {
87 debug!(" Can't copy-propagate local: dest {:?} undefined",
91 if dest_def_count > 1 {
92 debug!(" Can't copy-propagate local: dest {:?} defined {} times",
94 dest_use_info.def_count());
97 if dest_use_info.use_count() == 0 {
98 debug!(" Can't copy-propagate local: dest {:?} unused",
102 let dest_lvalue_def = dest_use_info.defs_and_uses.iter().filter(|lvalue_def| {
103 lvalue_def.context.is_mutating_use() && !lvalue_def.context.is_drop()
105 location = dest_lvalue_def.location;
107 let basic_block = &mir[location.block];
108 let statement_index = location.statement_index;
109 let statement = match basic_block.statements.get(statement_index) {
110 Some(statement) => statement,
112 debug!(" Can't copy-propagate local: used in terminator");
117 // That use of the source must be an assignment.
118 match statement.kind {
119 StatementKind::Assign(Lvalue::Local(local), Rvalue::Use(ref operand)) if
120 local == dest_local => {
121 let maybe_action = match *operand {
122 Operand::Consume(ref src_lvalue) => {
123 Action::local_copy(&mir, &def_use_analysis, src_lvalue)
125 Operand::Constant(ref src_constant) => {
126 Action::constant(src_constant)
130 Some(this_action) => action = this_action,
135 debug!(" Can't copy-propagate local: source use is not an \
142 changed = action.perform(mir, &def_use_analysis, dest_local, location) || changed;
143 // FIXME(pcwalton): Update the use-def chains to delete the instructions instead of
144 // regenerating the chains.
155 PropagateLocalCopy(Local),
156 PropagateConstant(Constant<'tcx>),
159 impl<'tcx> Action<'tcx> {
160 fn local_copy(mir: &Mir<'tcx>, def_use_analysis: &DefUseAnalysis, src_lvalue: &Lvalue<'tcx>)
161 -> Option<Action<'tcx>> {
162 // The source must be a local.
163 let src_local = if let Lvalue::Local(local) = *src_lvalue {
166 debug!(" Can't copy-propagate local: source is not a local");
170 // We're trying to copy propagate a local.
171 // There must be exactly one use of the source used in a statement (not in a terminator).
172 let src_use_info = def_use_analysis.local_info(src_local);
173 let src_use_count = src_use_info.use_count();
174 if src_use_count == 0 {
175 debug!(" Can't copy-propagate local: no uses");
178 if src_use_count != 1 {
179 debug!(" Can't copy-propagate local: {} uses", src_use_info.use_count());
183 // Verify that the source doesn't change in between. This is done conservatively for now,
184 // by ensuring that the source has exactly one mutation. The goal is to prevent things
191 // From being misoptimized into:
195 let src_def_count = src_use_info.def_count_not_including_drop();
196 // allow function arguments to be propagated
197 if src_def_count > 1 ||
198 (src_def_count == 0 && mir.local_kind(src_local) != LocalKind::Arg) {
199 debug!(" Can't copy-propagate local: {} defs of src",
200 src_use_info.def_count_not_including_drop());
204 Some(Action::PropagateLocalCopy(src_local))
207 fn constant(src_constant: &Constant<'tcx>) -> Option<Action<'tcx>> {
208 Some(Action::PropagateConstant((*src_constant).clone()))
213 def_use_analysis: &DefUseAnalysis<'tcx>,
218 Action::PropagateLocalCopy(src_local) => {
219 // Eliminate the destination and the assignment.
221 // First, remove all markers.
223 // FIXME(pcwalton): Don't do this. Merge live ranges instead.
224 debug!(" Replacing all uses of {:?} with {:?} (local)",
227 for lvalue_use in &def_use_analysis.local_info(dest_local).defs_and_uses {
228 if lvalue_use.context.is_storage_marker() {
229 mir.make_statement_nop(lvalue_use.location)
232 for lvalue_use in &def_use_analysis.local_info(src_local).defs_and_uses {
233 if lvalue_use.context.is_storage_marker() {
234 mir.make_statement_nop(lvalue_use.location)
238 // Replace all uses of the destination local with the source local.
239 let src_lvalue = Lvalue::Local(src_local);
240 def_use_analysis.replace_all_defs_and_uses_with(dest_local, mir, src_lvalue);
242 // Finally, zap the now-useless assignment instruction.
243 debug!(" Deleting assignment");
244 mir.make_statement_nop(location);
248 Action::PropagateConstant(src_constant) => {
249 // First, remove all markers.
251 // FIXME(pcwalton): Don't do this. Merge live ranges instead.
252 debug!(" Replacing all uses of {:?} with {:?} (constant)",
255 let dest_local_info = def_use_analysis.local_info(dest_local);
256 for lvalue_use in &dest_local_info.defs_and_uses {
257 if lvalue_use.context.is_storage_marker() {
258 mir.make_statement_nop(lvalue_use.location)
262 // Replace all uses of the destination local with the constant.
263 let mut visitor = ConstantPropagationVisitor::new(dest_local,
265 for dest_lvalue_use in &dest_local_info.defs_and_uses {
266 visitor.visit_location(mir, dest_lvalue_use.location)
269 // Zap the assignment instruction if we eliminated all the uses. We won't have been
270 // able to do that if the destination was used in a projection, because projections
271 // must have lvalues on their LHS.
272 let use_count = dest_local_info.use_count();
273 if visitor.uses_replaced == use_count {
274 debug!(" {} of {} use(s) replaced; deleting assignment",
275 visitor.uses_replaced,
277 mir.make_statement_nop(location);
279 } else if visitor.uses_replaced == 0 {
280 debug!(" No uses replaced; not deleting assignment");
283 debug!(" {} of {} use(s) replaced; not deleting assignment",
284 visitor.uses_replaced,
293 struct ConstantPropagationVisitor<'tcx> {
295 constant: Constant<'tcx>,
296 uses_replaced: usize,
299 impl<'tcx> ConstantPropagationVisitor<'tcx> {
300 fn new(dest_local: Local, constant: Constant<'tcx>)
301 -> ConstantPropagationVisitor<'tcx> {
302 ConstantPropagationVisitor {
303 dest_local: dest_local,
310 impl<'tcx> MutVisitor<'tcx> for ConstantPropagationVisitor<'tcx> {
311 fn visit_operand(&mut self, operand: &mut Operand<'tcx>, location: Location) {
312 self.super_operand(operand, location);
315 Operand::Consume(Lvalue::Local(local)) if local == self.dest_local => {}
319 *operand = Operand::Constant(self.constant.clone());
320 self.uses_replaced += 1