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