src/librustc_mir/transform/copy_prop.rs

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