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