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, Place, Mir, Operand, Rvalue, StatementKind};
  33 use rustc::mir::visit::MutVisitor;
  34 use rustc::ty::TyCtxt;
  35 use transform::{MirPass, MirSource};
  36 use util::def_use::DefUseAnalysis;
  37
  38 pub struct CopyPropagation;
  39
  40 impl MirPass for CopyPropagation {
  41     fn run_pass<'a, 'tcx>(&self,
  42                           tcx: TyCtxt<'a, 'tcx, 'tcx>,
  43                           _source: MirSource,
  44                           mir: &mut Mir<'tcx>) {
  45         // We only run when the MIR optimization level is > 1.
  46         // This avoids a slow pass, and messing up debug info.
  47         if tcx.sess.opts.debugging_opts.mir_opt_level <= 1 {
  48             return;
  49         }
  50
  51         let mut def_use_analysis = DefUseAnalysis::new(mir);
  52         loop {
  53             def_use_analysis.analyze(mir);
  54
  55             if eliminate_self_assignments(mir, &def_use_analysis) {
  56                 def_use_analysis.analyze(mir);
  57             }
  58
  59             let mut changed = false;
  60             for dest_local in mir.local_decls.indices() {
  61                 debug!("Considering destination local: {:?}", dest_local);
  62
  63                 let action;
  64                 let location;
  65                 {
  66                     // The destination must have exactly one def.
  67                     let dest_use_info = def_use_analysis.local_info(dest_local);
  68                     let dest_def_count = dest_use_info.def_count_not_including_drop();
  69                     if dest_def_count == 0 {
  70                         debug!("  Can't copy-propagate local: dest {:?} undefined",
  71                                dest_local);
  72                         continue
  73                     }
  74                     if dest_def_count > 1 {
  75                         debug!("  Can't copy-propagate local: dest {:?} defined {} times",
  76                                dest_local,
  77                                dest_use_info.def_count());
  78                         continue
  79                     }
  80                     if dest_use_info.use_count() == 0 {
  81                         debug!("  Can't copy-propagate local: dest {:?} unused",
  82                                dest_local);
  83                         continue
  84                     }
  85                     // Conservatively gives up if the dest is an argument,
  86                     // because there may be uses of the original argument value.
  87                     if mir.local_kind(dest_local) == LocalKind::Arg {
  88                         debug!("  Can't copy-propagate local: dest {:?} (argument)",
  89                             dest_local);
  90                         continue;
  91                     }
  92                     let dest_place_def = dest_use_info.defs_not_including_drop().next().unwrap();
  93                     location = dest_place_def.location;
  94
  95                     let basic_block = &mir[location.block];
  96                     let statement_index = location.statement_index;
  97                     let statement = match basic_block.statements.get(statement_index) {
  98                         Some(statement) => statement,
  99                         None => {
 100                             debug!("  Can't copy-propagate local: used in terminator");
 101                             continue
 102                         }
 103                     };
 104
 105                     // That use of the source must be an assignment.
 106                     match statement.kind {
 107                         StatementKind::Assign(Place::Local(local), Rvalue::Use(ref operand)) if
 108                                 local == dest_local => {
 109                             let maybe_action = match *operand {
 110                                 Operand::Copy(ref src_place) |
 111                                 Operand::Move(ref src_place) => {
 112                                     Action::local_copy(&mir, &def_use_analysis, src_place)
 113                                 }
 114                                 Operand::Constant(ref src_constant) => {
 115                                     Action::constant(src_constant)
 116                                 }
 117                             };
 118                             match maybe_action {
 119                                 Some(this_action) => action = this_action,
 120                                 None => continue,
 121                             }
 122                         }
 123                         _ => {
 124                             debug!("  Can't copy-propagate local: source use is not an \
 125                                     assignment");
 126                             continue
 127                         }
 128                     }
 129                 }
 130
 131                 changed = action.perform(mir, &def_use_analysis, dest_local, location) || changed;
 132                 // FIXME(pcwalton): Update the use-def chains to delete the instructions instead of
 133                 // regenerating the chains.
 134                 break
 135             }
 136             if !changed {
 137                 break
 138             }
 139         }
 140     }
 141 }
 142
 143 fn eliminate_self_assignments<'tcx>(
 144     mir: &mut Mir<'tcx>,
 145     def_use_analysis: &DefUseAnalysis<'tcx>,
 146 ) -> bool {
 147     let mut changed = false;
 148
 149     for dest_local in mir.local_decls.indices() {
 150         let dest_use_info = def_use_analysis.local_info(dest_local);
 151
 152         for def in dest_use_info.defs_not_including_drop() {
 153             let location = def.location;
 154             if let Some(stmt) = mir[location.block].statements.get(location.statement_index) {
 155                 match stmt.kind {
 156                     StatementKind::Assign(
 157                         Place::Local(local),
 158                         Rvalue::Use(Operand::Copy(Place::Local(src_local))),
 159                     ) |
 160                     StatementKind::Assign(
 161                         Place::Local(local),
 162                         Rvalue::Use(Operand::Move(Place::Local(src_local))),
 163                     ) if local == dest_local && dest_local == src_local => {}
 164                     _ => {
 165                         continue;
 166                     }
 167                 }
 168             } else {
 169                 continue;
 170             }
 171             debug!("Deleting a self-assignment for {:?}", dest_local);
 172             mir.make_statement_nop(location);
 173             changed = true;
 174         }
 175     }
 176
 177     changed
 178 }
 179
 180 enum Action<'tcx> {
 181     PropagateLocalCopy(Local),
 182     PropagateConstant(Constant<'tcx>),
 183 }
 184
 185 impl<'tcx> Action<'tcx> {
 186     fn local_copy(mir: &Mir<'tcx>, def_use_analysis: &DefUseAnalysis, src_place: &Place<'tcx>)
 187                   -> Option<Action<'tcx>> {
 188         // The source must be a local.
 189         let src_local = if let Place::Local(local) = *src_place {
 190             local
 191         } else {
 192             debug!("  Can't copy-propagate local: source is not a local");
 193             return None;
 194         };
 195
 196         // We're trying to copy propagate a local.
 197         // There must be exactly one use of the source used in a statement (not in a terminator).
 198         let src_use_info = def_use_analysis.local_info(src_local);
 199         let src_use_count = src_use_info.use_count();
 200         if src_use_count == 0 {
 201             debug!("  Can't copy-propagate local: no uses");
 202             return None
 203         }
 204         if src_use_count != 1 {
 205             debug!("  Can't copy-propagate local: {} uses", src_use_info.use_count());
 206             return None
 207         }
 208
 209         // Verify that the source doesn't change in between. This is done conservatively for now,
 210         // by ensuring that the source has exactly one mutation. The goal is to prevent things
 211         // like:
 212         //
 213         //     DEST = SRC;
 214         //     SRC = X;
 215         //     USE(DEST);
 216         //
 217         // From being misoptimized into:
 218         //
 219         //     SRC = X;
 220         //     USE(SRC);
 221         let src_def_count = src_use_info.def_count_not_including_drop();
 222         // allow function arguments to be propagated
 223         let is_arg = mir.local_kind(src_local) == LocalKind::Arg;
 224         if (is_arg && src_def_count != 0) || (!is_arg && src_def_count != 1) {
 225             debug!(
 226                 "  Can't copy-propagate local: {} defs of src{}",
 227                 src_def_count,
 228                 if is_arg { " (argument)" } else { "" },
 229             );
 230             return None
 231         }
 232
 233         Some(Action::PropagateLocalCopy(src_local))
 234     }
 235
 236     fn constant(src_constant: &Constant<'tcx>) -> Option<Action<'tcx>> {
 237         Some(Action::PropagateConstant((*src_constant).clone()))
 238     }
 239
 240     fn perform(self,
 241                mir: &mut Mir<'tcx>,
 242                def_use_analysis: &DefUseAnalysis<'tcx>,
 243                dest_local: Local,
 244                location: Location)
 245                -> bool {
 246         match self {
 247             Action::PropagateLocalCopy(src_local) => {
 248                 // Eliminate the destination and the assignment.
 249                 //
 250                 // First, remove all markers.
 251                 //
 252                 // FIXME(pcwalton): Don't do this. Merge live ranges instead.
 253                 debug!("  Replacing all uses of {:?} with {:?} (local)",
 254                        dest_local,
 255                        src_local);
 256                 for place_use in &def_use_analysis.local_info(dest_local).defs_and_uses {
 257                     if place_use.context.is_storage_marker() {
 258                         mir.make_statement_nop(place_use.location)
 259                     }
 260                 }
 261                 for place_use in &def_use_analysis.local_info(src_local).defs_and_uses {
 262                     if place_use.context.is_storage_marker() {
 263                         mir.make_statement_nop(place_use.location)
 264                     }
 265                 }
 266
 267                 // Replace all uses of the destination local with the source local.
 268                 def_use_analysis.replace_all_defs_and_uses_with(dest_local, mir, src_local);
 269
 270                 // Finally, zap the now-useless assignment instruction.
 271                 debug!("  Deleting assignment");
 272                 mir.make_statement_nop(location);
 273
 274                 true
 275             }
 276             Action::PropagateConstant(src_constant) => {
 277                 // First, remove all markers.
 278                 //
 279                 // FIXME(pcwalton): Don't do this. Merge live ranges instead.
 280                 debug!("  Replacing all uses of {:?} with {:?} (constant)",
 281                        dest_local,
 282                        src_constant);
 283                 let dest_local_info = def_use_analysis.local_info(dest_local);
 284                 for place_use in &dest_local_info.defs_and_uses {
 285                     if place_use.context.is_storage_marker() {
 286                         mir.make_statement_nop(place_use.location)
 287                     }
 288                 }
 289
 290                 // Replace all uses of the destination local with the constant.
 291                 let mut visitor = ConstantPropagationVisitor::new(dest_local,
 292                                                                   src_constant);
 293                 for dest_place_use in &dest_local_info.defs_and_uses {
 294                     visitor.visit_location(mir, dest_place_use.location)
 295                 }
 296
 297                 // Zap the assignment instruction if we eliminated all the uses. We won't have been
 298                 // able to do that if the destination was used in a projection, because projections
 299                 // must have places on their LHS.
 300                 let use_count = dest_local_info.use_count();
 301                 if visitor.uses_replaced == use_count {
 302                     debug!("  {} of {} use(s) replaced; deleting assignment",
 303                            visitor.uses_replaced,
 304                            use_count);
 305                     mir.make_statement_nop(location);
 306                     true
 307                 } else if visitor.uses_replaced == 0 {
 308                     debug!("  No uses replaced; not deleting assignment");
 309                     false
 310                 } else {
 311                     debug!("  {} of {} use(s) replaced; not deleting assignment",
 312                            visitor.uses_replaced,
 313                            use_count);
 314                     true
 315                 }
 316             }
 317         }
 318     }
 319 }
 320
 321 struct ConstantPropagationVisitor<'tcx> {
 322     dest_local: Local,
 323     constant: Constant<'tcx>,
 324     uses_replaced: usize,
 325 }
 326
 327 impl<'tcx> ConstantPropagationVisitor<'tcx> {
 328     fn new(dest_local: Local, constant: Constant<'tcx>)
 329            -> ConstantPropagationVisitor<'tcx> {
 330         ConstantPropagationVisitor {
 331             dest_local,
 332             constant,
 333             uses_replaced: 0,
 334         }
 335     }
 336 }
 337
 338 impl<'tcx> MutVisitor<'tcx> for ConstantPropagationVisitor<'tcx> {
 339     fn visit_operand(&mut self, operand: &mut Operand<'tcx>, location: Location) {
 340         self.super_operand(operand, location);
 341
 342         match *operand {
 343             Operand::Copy(Place::Local(local)) |
 344             Operand::Move(Place::Local(local)) if local == self.dest_local => {}
 345             _ => return,
 346         }
 347
 348         *operand = Operand::Constant(box self.constant.clone());
 349         self.uses_replaced += 1
 350     }
 351 }