src/librustc_mir/transform/copy_prop.rs

   1 // Copyright 2016 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! Trivial copy propagation pass.
  12 //!
  13 //! This uses def-use analysis to remove values that have exactly one def and one use, which must
  14 //! be an assignment.
  15 //!
  16 //! To give an example, we look for patterns that look like:
  17 //!
  18 //!     DEST = SRC
  19 //!     ...
  20 //!     USE(DEST)
  21 //!
  22 //! where `DEST` and `SRC` are both locals of some form. We replace that with:
  23 //!
  24 //!     NOP
  25 //!     ...
  26 //!     USE(SRC)
  27 //!
  28 //! The assignment `DEST = SRC` must be (a) the only mutation of `DEST` and (b) the only
  29 //! (non-mutating) use of `SRC`. These restrictions are conservative and may be relaxed in the
  30 //! future.
  31
  32 use rustc::hir;
  33 use rustc::mir::{Constant, Local, LocalKind, Location, Lvalue, Mir, Operand, Rvalue, StatementKind};
  34 use rustc::mir::visit::MutVisitor;
  35 use rustc::ty::TyCtxt;
  36 use transform::{MirPass, MirSource};
  37 use util::def_use::DefUseAnalysis;
  38
  39 pub struct CopyPropagation;
  40
  41 impl MirPass for CopyPropagation {
  42     fn run_pass<'a, 'tcx>(&self,
  43                           tcx: TyCtxt<'a, 'tcx, 'tcx>,
  44                           source: MirSource,
  45                           mir: &mut Mir<'tcx>) {
  46         // Don't run on constant MIR, because trans might not be able to
  47         // evaluate the modified MIR.
  48         // FIXME(eddyb) Remove check after miri is merged.
  49         let id = tcx.hir.as_local_node_id(source.def_id).unwrap();
  50         match (tcx.hir.body_owner_kind(id), source.promoted) {
  51             (_, Some(_)) |
  52             (hir::BodyOwnerKind::Const, _) |
  53             (hir::BodyOwnerKind::Static(_), _) => return,
  54
  55             (hir::BodyOwnerKind::Fn, _) => {
  56                 if tcx.is_const_fn(source.def_id) {
  57                     // Don't run on const functions, as, again, trans might not be able to evaluate
  58                     // the optimized IR.
  59                     return
  60                 }
  61             }
  62         }
  63
  64         // We only run when the MIR optimization level is > 1.
  65         // This avoids a slow pass, and messing up debug info.
  66         if tcx.sess.opts.debugging_opts.mir_opt_level <= 1 {
  67             return;
  68         }
  69
  70         let mut def_use_analysis = DefUseAnalysis::new(mir);
  71         loop {
  72             def_use_analysis.analyze(mir);
  73
  74             if eliminate_self_assignments(mir, &def_use_analysis) {
  75                 def_use_analysis.analyze(mir);
  76             }
  77
  78             let mut changed = false;
  79             for dest_local in mir.local_decls.indices() {
  80                 debug!("Considering destination local: {:?}", dest_local);
  81
  82                 let action;
  83                 let location;
  84                 {
  85                     // The destination must have exactly one def.
  86                     let dest_use_info = def_use_analysis.local_info(dest_local);
  87                     let dest_def_count = dest_use_info.def_count_not_including_drop();
  88                     if dest_def_count == 0 {
  89                         debug!("  Can't copy-propagate local: dest {:?} undefined",
  90                                dest_local);
  91                         continue
  92                     }
  93                     if dest_def_count > 1 {
  94                         debug!("  Can't copy-propagate local: dest {:?} defined {} times",
  95                                dest_local,
  96                                dest_use_info.def_count());
  97                         continue
  98                     }
  99                     if dest_use_info.use_count() == 0 {
 100                         debug!("  Can't copy-propagate local: dest {:?} unused",
 101                                dest_local);
 102                         continue
 103                     }
 104                     // Conservatively gives up if the dest is an argument,
 105                     // because there may be uses of the original argument value.
 106                     if mir.local_kind(dest_local) == LocalKind::Arg {
 107                         debug!("  Can't copy-propagate local: dest {:?} (argument)",
 108                             dest_local);
 109                         continue;
 110                     }
 111                     let dest_lvalue_def = dest_use_info.defs_not_including_drop().next().unwrap();
 112                     location = dest_lvalue_def.location;
 113
 114                     let basic_block = &mir[location.block];
 115                     let statement_index = location.statement_index;
 116                     let statement = match basic_block.statements.get(statement_index) {
 117                         Some(statement) => statement,
 118                         None => {
 119                             debug!("  Can't copy-propagate local: used in terminator");
 120                             continue
 121                         }
 122                     };
 123
 124                     // That use of the source must be an assignment.
 125                     match statement.kind {
 126                         StatementKind::Assign(Lvalue::Local(local), Rvalue::Use(ref operand)) if
 127                                 local == dest_local => {
 128                             let maybe_action = match *operand {
 129                                 Operand::Consume(ref src_lvalue) => {
 130                                     Action::local_copy(&mir, &def_use_analysis, src_lvalue)
 131                                 }
 132                                 Operand::Constant(ref src_constant) => {
 133                                     Action::constant(src_constant)
 134                                 }
 135                             };
 136                             match maybe_action {
 137                                 Some(this_action) => action = this_action,
 138                                 None => continue,
 139                             }
 140                         }
 141                         _ => {
 142                             debug!("  Can't copy-propagate local: source use is not an \
 143                                     assignment");
 144                             continue
 145                         }
 146                     }
 147                 }
 148
 149                 changed = action.perform(mir, &def_use_analysis, dest_local, location) || changed;
 150                 // FIXME(pcwalton): Update the use-def chains to delete the instructions instead of
 151                 // regenerating the chains.
 152                 break
 153             }
 154             if !changed {
 155                 break
 156             }
 157         }
 158     }
 159 }
 160
 161 fn eliminate_self_assignments<'tcx>(
 162     mir: &mut Mir<'tcx>,
 163     def_use_analysis: &DefUseAnalysis<'tcx>,
 164 ) -> bool {
 165     let mut changed = false;
 166
 167     for dest_local in mir.local_decls.indices() {
 168         let dest_use_info = def_use_analysis.local_info(dest_local);
 169
 170         for def in dest_use_info.defs_not_including_drop() {
 171             let location = def.location;
 172             if let Some(stmt) = mir[location.block].statements.get(location.statement_index) {
 173                 match stmt.kind {
 174                     StatementKind::Assign(
 175                         Lvalue::Local(local),
 176                         Rvalue::Use(Operand::Consume(Lvalue::Local(src_local))),
 177                     ) if local == dest_local && dest_local == src_local => {}
 178                     _ => {
 179                         continue;
 180                     }
 181                 }
 182             } else {
 183                 continue;
 184             }
 185             debug!("Deleting a self-assignment for {:?}", dest_local);
 186             mir.make_statement_nop(location);
 187             changed = true;
 188         }
 189     }
 190
 191     changed
 192 }
 193
 194 enum Action<'tcx> {
 195     PropagateLocalCopy(Local),
 196     PropagateConstant(Constant<'tcx>),
 197 }
 198
 199 impl<'tcx> Action<'tcx> {
 200     fn local_copy(mir: &Mir<'tcx>, def_use_analysis: &DefUseAnalysis, src_lvalue: &Lvalue<'tcx>)
 201                   -> Option<Action<'tcx>> {
 202         // The source must be a local.
 203         let src_local = if let Lvalue::Local(local) = *src_lvalue {
 204             local
 205         } else {
 206             debug!("  Can't copy-propagate local: source is not a local");
 207             return None;
 208         };
 209
 210         // We're trying to copy propagate a local.
 211         // There must be exactly one use of the source used in a statement (not in a terminator).
 212         let src_use_info = def_use_analysis.local_info(src_local);
 213         let src_use_count = src_use_info.use_count();
 214         if src_use_count == 0 {
 215             debug!("  Can't copy-propagate local: no uses");
 216             return None
 217         }
 218         if src_use_count != 1 {
 219             debug!("  Can't copy-propagate local: {} uses", src_use_info.use_count());
 220             return None
 221         }
 222
 223         // Verify that the source doesn't change in between. This is done conservatively for now,
 224         // by ensuring that the source has exactly one mutation. The goal is to prevent things
 225         // like:
 226         //
 227         //     DEST = SRC;
 228         //     SRC = X;
 229         //     USE(DEST);
 230         //
 231         // From being misoptimized into:
 232         //
 233         //     SRC = X;
 234         //     USE(SRC);
 235         let src_def_count = src_use_info.def_count_not_including_drop();
 236         // allow function arguments to be propagated
 237         if src_def_count > 1 ||
 238             (src_def_count == 0 && mir.local_kind(src_local) != LocalKind::Arg) {
 239             debug!("  Can't copy-propagate local: {} defs of src",
 240                    src_use_info.def_count_not_including_drop());
 241             return None
 242         }
 243
 244         Some(Action::PropagateLocalCopy(src_local))
 245     }
 246
 247     fn constant(src_constant: &Constant<'tcx>) -> Option<Action<'tcx>> {
 248         Some(Action::PropagateConstant((*src_constant).clone()))
 249     }
 250
 251     fn perform(self,
 252                mir: &mut Mir<'tcx>,
 253                def_use_analysis: &DefUseAnalysis<'tcx>,
 254                dest_local: Local,
 255                location: Location)
 256                -> bool {
 257         match self {
 258             Action::PropagateLocalCopy(src_local) => {
 259                 // Eliminate the destination and the assignment.
 260                 //
 261                 // First, remove all markers.
 262                 //
 263                 // FIXME(pcwalton): Don't do this. Merge live ranges instead.
 264                 debug!("  Replacing all uses of {:?} with {:?} (local)",
 265                        dest_local,
 266                        src_local);
 267                 for lvalue_use in &def_use_analysis.local_info(dest_local).defs_and_uses {
 268                     if lvalue_use.context.is_storage_marker() {
 269                         mir.make_statement_nop(lvalue_use.location)
 270                     }
 271                 }
 272                 for lvalue_use in &def_use_analysis.local_info(src_local).defs_and_uses {
 273                     if lvalue_use.context.is_storage_marker() {
 274                         mir.make_statement_nop(lvalue_use.location)
 275                     }
 276                 }
 277
 278                 // Replace all uses of the destination local with the source local.
 279                 def_use_analysis.replace_all_defs_and_uses_with(dest_local, mir, src_local);
 280
 281                 // Finally, zap the now-useless assignment instruction.
 282                 debug!("  Deleting assignment");
 283                 mir.make_statement_nop(location);
 284
 285                 true
 286             }
 287             Action::PropagateConstant(src_constant) => {
 288                 // First, remove all markers.
 289                 //
 290                 // FIXME(pcwalton): Don't do this. Merge live ranges instead.
 291                 debug!("  Replacing all uses of {:?} with {:?} (constant)",
 292                        dest_local,
 293                        src_constant);
 294                 let dest_local_info = def_use_analysis.local_info(dest_local);
 295                 for lvalue_use in &dest_local_info.defs_and_uses {
 296                     if lvalue_use.context.is_storage_marker() {
 297                         mir.make_statement_nop(lvalue_use.location)
 298                     }
 299                 }
 300
 301                 // Replace all uses of the destination local with the constant.
 302                 let mut visitor = ConstantPropagationVisitor::new(dest_local,
 303                                                                   src_constant);
 304                 for dest_lvalue_use in &dest_local_info.defs_and_uses {
 305                     visitor.visit_location(mir, dest_lvalue_use.location)
 306                 }
 307
 308                 // Zap the assignment instruction if we eliminated all the uses. We won't have been
 309                 // able to do that if the destination was used in a projection, because projections
 310                 // must have lvalues on their LHS.
 311                 let use_count = dest_local_info.use_count();
 312                 if visitor.uses_replaced == use_count {
 313                     debug!("  {} of {} use(s) replaced; deleting assignment",
 314                            visitor.uses_replaced,
 315                            use_count);
 316                     mir.make_statement_nop(location);
 317                     true
 318                 } else if visitor.uses_replaced == 0 {
 319                     debug!("  No uses replaced; not deleting assignment");
 320                     false
 321                 } else {
 322                     debug!("  {} of {} use(s) replaced; not deleting assignment",
 323                            visitor.uses_replaced,
 324                            use_count);
 325                     true
 326                 }
 327             }
 328         }
 329     }
 330 }
 331
 332 struct ConstantPropagationVisitor<'tcx> {
 333     dest_local: Local,
 334     constant: Constant<'tcx>,
 335     uses_replaced: usize,
 336 }
 337
 338 impl<'tcx> ConstantPropagationVisitor<'tcx> {
 339     fn new(dest_local: Local, constant: Constant<'tcx>)
 340            -> ConstantPropagationVisitor<'tcx> {
 341         ConstantPropagationVisitor {
 342             dest_local,
 343             constant,
 344             uses_replaced: 0,
 345         }
 346     }
 347 }
 348
 349 impl<'tcx> MutVisitor<'tcx> for ConstantPropagationVisitor<'tcx> {
 350     fn visit_operand(&mut self, operand: &mut Operand<'tcx>, location: Location) {
 351         self.super_operand(operand, location);
 352
 353         match *operand {
 354             Operand::Consume(Lvalue::Local(local)) if local == self.dest_local => {}
 355             _ => return,
 356         }
 357
 358         *operand = Operand::Constant(box self.constant.clone());
 359         self.uses_replaced += 1
 360     }
 361 }