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, Body, BodyCache, Operand, Rvalue,
  24     StatementKind
  25 };
  26 use rustc::mir::visit::MutVisitor;
  27 use rustc::ty::TyCtxt;
  28 use crate::transform::{MirPass, MirSource};
  29 use crate::util::def_use::DefUseAnalysis;
  30
  31 pub struct CopyPropagation;
  32
  33 impl<'tcx> MirPass<'tcx> for CopyPropagation {
  34     fn run_pass(&self, tcx: TyCtxt<'tcx>, _source: MirSource<'tcx>, body_cache: &mut BodyCache<'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(body_cache);
  42         loop {
  43             def_use_analysis.analyze(body_cache.read_only());
  44
  45             if eliminate_self_assignments(body_cache, &def_use_analysis) {
  46                 def_use_analysis.analyze(body_cache.read_only());
  47             }
  48
  49             let mut changed = false;
  50             for dest_local in body_cache.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 body_cache.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 = &body_cache[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(box(place, Rvalue::Use(operand))) => {
  98                             if let Some(local) = place.as_local() {
  99                                 if local == dest_local {
 100                                     let maybe_action = match operand {
 101                                         Operand::Copy(ref src_place) |
 102                                         Operand::Move(ref src_place) => {
 103                                             Action::local_copy(&body_cache, &def_use_analysis, src_place)
 104                                         }
 105                                         Operand::Constant(ref src_constant) => {
 106                                             Action::constant(src_constant)
 107                                         }
 108                                     };
 109                                     match maybe_action {
 110                                         Some(this_action) => action = this_action,
 111                                         None => continue,
 112                                     }
 113                                 } else {
 114                                     debug!("  Can't copy-propagate local: source use is not an \
 115                                     assignment");
 116                                     continue
 117                                 }
 118                             } else {
 119                                 debug!("  Can't copy-propagate local: source use is not an \
 120                                     assignment");
 121                                 continue
 122                             }
 123                         }
 124                         _ => {
 125                             debug!("  Can't copy-propagate local: source use is not an \
 126                                     assignment");
 127                             continue
 128                         }
 129                     }
 130                 }
 131
 132                 changed =
 133                     action.perform(body_cache, &def_use_analysis, dest_local, location, tcx) || changed;
 134                 // FIXME(pcwalton): Update the use-def chains to delete the instructions instead of
 135                 // regenerating the chains.
 136                 break
 137             }
 138             if !changed {
 139                 break
 140             }
 141         }
 142     }
 143 }
 144
 145 fn eliminate_self_assignments(
 146     body: &mut Body<'_>,
 147     def_use_analysis: &DefUseAnalysis,
 148 ) -> bool {
 149     let mut changed = false;
 150
 151     for dest_local in body.local_decls.indices() {
 152         let dest_use_info = def_use_analysis.local_info(dest_local);
 153
 154         for def in dest_use_info.defs_not_including_drop() {
 155             let location = def.location;
 156             if let Some(stmt) = body[location.block].statements.get(location.statement_index) {
 157                 match &stmt.kind {
 158                     StatementKind::Assign(box (place, Rvalue::Use(Operand::Copy(src_place))))
 159                     | StatementKind::Assign(box (place, Rvalue::Use(Operand::Move(src_place)))) => {
 160                         if let (Some(local), Some(src_local)) =
 161                             (place.as_local(), src_place.as_local())
 162                         {
 163                             if local == dest_local && dest_local == src_local {
 164                             } else {
 165                                 continue;
 166                             }
 167                         } else {
 168                             continue;
 169                         }
 170                     }
 171                     _ => {
 172                         continue;
 173                     }
 174                 }
 175             } else {
 176                 continue;
 177             }
 178             debug!("deleting a self-assignment for {:?}", dest_local);
 179             body.make_statement_nop(location);
 180             changed = true;
 181         }
 182     }
 183
 184     changed
 185 }
 186
 187 enum Action<'tcx> {
 188     PropagateLocalCopy(Local),
 189     PropagateConstant(Constant<'tcx>),
 190 }
 191
 192 impl<'tcx> Action<'tcx> {
 193     fn local_copy(body: &Body<'tcx>, def_use_analysis: &DefUseAnalysis, src_place: &Place<'tcx>)
 194                   -> Option<Action<'tcx>> {
 195         // The source must be a local.
 196         let src_local = if let Some(local) = src_place.as_local() {
 197             local
 198         } else {
 199             debug!("  Can't copy-propagate local: source is not a local");
 200             return None;
 201         };
 202
 203         // We're trying to copy propagate a local.
 204         // There must be exactly one use of the source used in a statement (not in a terminator).
 205         let src_use_info = def_use_analysis.local_info(src_local);
 206         let src_use_count = src_use_info.use_count();
 207         if src_use_count == 0 {
 208             debug!("  Can't copy-propagate local: no uses");
 209             return None
 210         }
 211         if src_use_count != 1 {
 212             debug!("  Can't copy-propagate local: {} uses", src_use_info.use_count());
 213             return None
 214         }
 215
 216         // Verify that the source doesn't change in between. This is done conservatively for now,
 217         // by ensuring that the source has exactly one mutation. The goal is to prevent things
 218         // like:
 219         //
 220         //     DEST = SRC;
 221         //     SRC = X;
 222         //     USE(DEST);
 223         //
 224         // From being misoptimized into:
 225         //
 226         //     SRC = X;
 227         //     USE(SRC);
 228         let src_def_count = src_use_info.def_count_not_including_drop();
 229         // allow function arguments to be propagated
 230         let is_arg = body.local_kind(src_local) == LocalKind::Arg;
 231         if (is_arg && src_def_count != 0) || (!is_arg && src_def_count != 1) {
 232             debug!(
 233                 "  Can't copy-propagate local: {} defs of src{}",
 234                 src_def_count,
 235                 if is_arg { " (argument)" } else { "" },
 236             );
 237             return None
 238         }
 239
 240         Some(Action::PropagateLocalCopy(src_local))
 241     }
 242
 243     fn constant(src_constant: &Constant<'tcx>) -> Option<Action<'tcx>> {
 244         Some(Action::PropagateConstant((*src_constant).clone()))
 245     }
 246
 247     fn perform(self,
 248                body_cache: &mut BodyCache<'tcx>,
 249                def_use_analysis: &DefUseAnalysis,
 250                dest_local: Local,
 251                location: Location,
 252                tcx: TyCtxt<'tcx>)
 253                -> bool {
 254         match self {
 255             Action::PropagateLocalCopy(src_local) => {
 256                 // Eliminate the destination and the assignment.
 257                 //
 258                 // First, remove all markers.
 259                 //
 260                 // FIXME(pcwalton): Don't do this. Merge live ranges instead.
 261                 debug!("  Replacing all uses of {:?} with {:?} (local)",
 262                        dest_local,
 263                        src_local);
 264                 for place_use in &def_use_analysis.local_info(dest_local).defs_and_uses {
 265                     if place_use.context.is_storage_marker() {
 266                         body_cache.make_statement_nop(place_use.location)
 267                     }
 268                 }
 269                 for place_use in &def_use_analysis.local_info(src_local).defs_and_uses {
 270                     if place_use.context.is_storage_marker() {
 271                         body_cache.make_statement_nop(place_use.location)
 272                     }
 273                 }
 274
 275                 // Replace all uses of the destination local with the source local.
 276                 def_use_analysis.replace_all_defs_and_uses_with(dest_local, body_cache, src_local, tcx);
 277
 278                 // Finally, zap the now-useless assignment instruction.
 279                 debug!("  Deleting assignment");
 280                 body_cache.make_statement_nop(location);
 281
 282                 true
 283             }
 284             Action::PropagateConstant(src_constant) => {
 285                 // First, remove all markers.
 286                 //
 287                 // FIXME(pcwalton): Don't do this. Merge live ranges instead.
 288                 debug!("  Replacing all uses of {:?} with {:?} (constant)",
 289                        dest_local,
 290                        src_constant);
 291                 let dest_local_info = def_use_analysis.local_info(dest_local);
 292                 for place_use in &dest_local_info.defs_and_uses {
 293                     if place_use.context.is_storage_marker() {
 294                         body_cache.make_statement_nop(place_use.location)
 295                     }
 296                 }
 297
 298                 // Replace all uses of the destination local with the constant.
 299                 let mut visitor = ConstantPropagationVisitor::new(dest_local,
 300                                                                   src_constant,
 301                                                                   tcx);
 302                 for dest_place_use in &dest_local_info.defs_and_uses {
 303                     visitor.visit_location(body_cache, dest_place_use.location)
 304                 }
 305
 306                 // Zap the assignment instruction if we eliminated all the uses. We won't have been
 307                 // able to do that if the destination was used in a projection, because projections
 308                 // must have places on their LHS.
 309                 let use_count = dest_local_info.use_count();
 310                 if visitor.uses_replaced == use_count {
 311                     debug!("  {} of {} use(s) replaced; deleting assignment",
 312                            visitor.uses_replaced,
 313                            use_count);
 314                     body_cache.make_statement_nop(location);
 315                     true
 316                 } else if visitor.uses_replaced == 0 {
 317                     debug!("  No uses replaced; not deleting assignment");
 318                     false
 319                 } else {
 320                     debug!("  {} of {} use(s) replaced; not deleting assignment",
 321                            visitor.uses_replaced,
 322                            use_count);
 323                     true
 324                 }
 325             }
 326         }
 327     }
 328 }
 329
 330 struct ConstantPropagationVisitor<'tcx> {
 331     dest_local: Local,
 332     constant: Constant<'tcx>,
 333     tcx: TyCtxt<'tcx>,
 334     uses_replaced: usize,
 335 }
 336
 337 impl<'tcx> ConstantPropagationVisitor<'tcx> {
 338     fn new(dest_local: Local, constant: Constant<'tcx>, tcx: TyCtxt<'tcx>)
 339            -> ConstantPropagationVisitor<'tcx> {
 340         ConstantPropagationVisitor {
 341             dest_local,
 342             constant,
 343             tcx,
 344             uses_replaced: 0,
 345         }
 346     }
 347 }
 348
 349 impl<'tcx> MutVisitor<'tcx> for ConstantPropagationVisitor<'tcx> {
 350     fn tcx(&self) -> TyCtxt<'tcx> {
 351         self.tcx
 352     }
 353
 354     fn visit_operand(&mut self, operand: &mut Operand<'tcx>, location: Location) {
 355         self.super_operand(operand, location);
 356
 357         match operand {
 358             Operand::Copy(place) |
 359             Operand::Move(place) => {
 360                 if let Some(local) = place.as_local() {
 361                     if local == self.dest_local {
 362                     } else {
 363                         return;
 364                     }
 365                 } else {
 366                     return;
 367                 }
 368             }
 369             _ => return,
 370         }
 371
 372         *operand = Operand::Constant(box self.constant.clone());
 373         self.uses_replaced += 1
 374     }
 375 }