src/librustc_mir/transform/copy_prop.rs

   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.
   4 //
   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.
  10
  11 //! Trivial copy propagation pass.
  12 //!
  13 //! This uses def-use analysis to remove values that have exactly one def and one use, which must
  14 //! be an assignment.
  15 //!
  16 //! To give an example, we look for patterns that look like:
  17 //!
  18 //!     DEST = SRC
  19 //!     ...
  20 //!     USE(DEST)
  21 //!
  22 //! where `DEST` and `SRC` are both locals of some form. We replace that with:
  23 //!
  24 //!     NOP
  25 //!     ...
  26 //!     USE(SRC)
  27 //!
  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
  30 //! future.
  31
  32 use rustc::mir::{Constant, Local, LocalKind, Location, Lvalue, Mir, Operand, Rvalue, StatementKind};
  33 use rustc::mir::transform::{MirPass, MirSource, Pass};
  34 use rustc::mir::visit::MutVisitor;
  35 use rustc::ty::TyCtxt;
  36 use util::def_use::DefUseAnalysis;
  37 use transform::qualify_consts;
  38
  39 pub struct CopyPropagation;
  40
  41 impl Pass for CopyPropagation {}
  42
  43 impl<'tcx> MirPass<'tcx> for CopyPropagation {
  44     fn run_pass<'a>(&mut self,
  45                     tcx: TyCtxt<'a, 'tcx, 'tcx>,
  46                     source: MirSource,
  47                     mir: &mut Mir<'tcx>) {
  48         match source {
  49             MirSource::Const(_) => {
  50                 // Don't run on constants, because constant qualification might reject the
  51                 // optimized IR.
  52                 return
  53             }
  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.
  57                 return
  58             }
  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
  62                     // the optimized IR.
  63                     return
  64                 }
  65             }
  66         }
  67
  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 {
  71             return;
  72         }
  73
  74         loop {
  75             let mut def_use_analysis = DefUseAnalysis::new(mir);
  76             def_use_analysis.analyze(mir);
  77
  78             let mut changed = false;
  79             for dest_local in mir.local_decls.indices() {
  80                 debug!("Considering destination local: {:?}", dest_local);
  81
  82                 let action;
  83                 let location;
  84                 {
  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",
  90                                dest_local);
  91                         continue
  92                     }
  93                     if dest_def_count > 1 {
  94                         debug!("  Can't copy-propagate local: dest {:?} defined {} times",
  95                                dest_local,
  96                                dest_use_info.def_count());
  97                         continue
  98                     }
  99                     if dest_use_info.use_count() == 0 {
 100                         debug!("  Can't copy-propagate local: dest {:?} unused",
 101                                dest_local);
 102                         continue
 103                     }
 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()
 106                     }).next().unwrap();
 107                     location = dest_lvalue_def.location;
 108
 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,
 113                         None => {
 114                             debug!("  Can't copy-propagate local: used in terminator");
 115                             continue
 116                         }
 117                     };
 118
 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)
 126                                 }
 127                                 Operand::Constant(ref src_constant) => {
 128                                     Action::constant(src_constant)
 129                                 }
 130                             };
 131                             match maybe_action {
 132                                 Some(this_action) => action = this_action,
 133                                 None => continue,
 134                             }
 135                         }
 136                         _ => {
 137                             debug!("  Can't copy-propagate local: source use is not an \
 138                                     assignment");
 139                             continue
 140                         }
 141                     }
 142                 }
 143
 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.
 147                 break
 148             }
 149             if !changed {
 150                 break
 151             }
 152         }
 153     }
 154 }
 155
 156 enum Action<'tcx> {
 157     PropagateLocalCopy(Local),
 158     PropagateConstant(Constant<'tcx>),
 159 }
 160
 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 {
 166             local
 167         } else {
 168             debug!("  Can't copy-propagate local: source is not a local");
 169             return None;
 170         };
 171
 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");
 178             return None
 179         }
 180         if src_use_count != 1 {
 181             debug!("  Can't copy-propagate local: {} uses", src_use_info.use_count());
 182             return None
 183         }
 184
 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
 187         // like:
 188         //
 189         //     DEST = SRC;
 190         //     SRC = X;
 191         //     USE(DEST);
 192         //
 193         // From being misoptimized into:
 194         //
 195         //     SRC = X;
 196         //     USE(SRC);
 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());
 203             return None
 204         }
 205
 206         Some(Action::PropagateLocalCopy(src_local))
 207     }
 208
 209     fn constant(src_constant: &Constant<'tcx>) -> Option<Action<'tcx>> {
 210         Some(Action::PropagateConstant((*src_constant).clone()))
 211     }
 212
 213     fn perform(self,
 214                mir: &mut Mir<'tcx>,
 215                def_use_analysis: &DefUseAnalysis<'tcx>,
 216                dest_local: Local,
 217                location: Location)
 218                -> bool {
 219         match self {
 220             Action::PropagateLocalCopy(src_local) => {
 221                 // Eliminate the destination and the assignment.
 222                 //
 223                 // First, remove all markers.
 224                 //
 225                 // FIXME(pcwalton): Don't do this. Merge live ranges instead.
 226                 debug!("  Replacing all uses of {:?} with {:?} (local)",
 227                        dest_local,
 228                        src_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)
 232                     }
 233                 }
 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)
 237                     }
 238                 }
 239
 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);
 243
 244                 // Finally, zap the now-useless assignment instruction.
 245                 debug!("  Deleting assignment");
 246                 mir.make_statement_nop(location);
 247
 248                 true
 249             }
 250             Action::PropagateConstant(src_constant) => {
 251                 // First, remove all markers.
 252                 //
 253                 // FIXME(pcwalton): Don't do this. Merge live ranges instead.
 254                 debug!("  Replacing all uses of {:?} with {:?} (constant)",
 255                        dest_local,
 256                        src_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)
 261                     }
 262                 }
 263
 264                 // Replace all uses of the destination local with the constant.
 265                 let mut visitor = ConstantPropagationVisitor::new(dest_local,
 266                                                                   src_constant);
 267                 for dest_lvalue_use in &dest_local_info.defs_and_uses {
 268                     visitor.visit_location(mir, dest_lvalue_use.location)
 269                 }
 270
 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,
 278                            use_count);
 279                     mir.make_statement_nop(location);
 280                     true
 281                 } else if visitor.uses_replaced == 0 {
 282                     debug!("  No uses replaced; not deleting assignment");
 283                     false
 284                 } else {
 285                     debug!("  {} of {} use(s) replaced; not deleting assignment",
 286                            visitor.uses_replaced,
 287                            use_count);
 288                     true
 289                 }
 290             }
 291         }
 292     }
 293 }
 294
 295 struct ConstantPropagationVisitor<'tcx> {
 296     dest_local: Local,
 297     constant: Constant<'tcx>,
 298     uses_replaced: usize,
 299 }
 300
 301 impl<'tcx> ConstantPropagationVisitor<'tcx> {
 302     fn new(dest_local: Local, constant: Constant<'tcx>)
 303            -> ConstantPropagationVisitor<'tcx> {
 304         ConstantPropagationVisitor {
 305             dest_local: dest_local,
 306             constant: constant,
 307             uses_replaced: 0,
 308         }
 309     }
 310 }
 311
 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);
 315
 316         match *operand {
 317             Operand::Consume(Lvalue::Local(local)) if local == self.dest_local => {}
 318             _ => return,
 319         }
 320
 321         *operand = Operand::Constant(self.constant.clone());
 322         self.uses_replaced += 1
 323     }
 324 }