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