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