Auto merge of #36388 - pcwalton:copy-propagation, r=nikomatsakis

librustc_mir: Implement def-use chains and trivial copy propagation on MIR.

This only supports trivial cases in which there is exactly one def and
one use.

Currently, some random unrelated MIR tests are failing, probably just because they haven't been updated.

r? @eddyb

20 files changed, 593 insertions, 37 deletions

diff --git a/src/librustc/mir/repr.rs b/src/librustc/mir/repr.rs
index 53b6ccdbd53..be761c95b61 100644
--- a/src/librustc/mir/repr.rs
+++ b/src/librustc/mir/repr.rs
@@ -187,6 +187,32 @@ impl<'tcx> Mir<'tcx> {
         self.var_decls.len() +
         self.temp_decls.len() + 1
     }
+
+    pub fn format_local(&self, local: Local) -> String {
+        let mut index = local.index();
+        index = match index.checked_sub(self.arg_decls.len()) {
+            None => return format!("{:?}", Arg::new(index)),
+            Some(index) => index,
+        };
+        index = match index.checked_sub(self.var_decls.len()) {
+            None => return format!("{:?}", Var::new(index)),
+            Some(index) => index,
+        };
+        index = match index.checked_sub(self.temp_decls.len()) {
+            None => return format!("{:?}", Temp::new(index)),
+            Some(index) => index,
+        };
+        debug_assert!(index == 0);
+        return "ReturnPointer".to_string()
+    }
+
+    /// Changes a statement to a nop. This is both faster than deleting instructions and avoids
+    /// invalidating statement indices in `Location`s.
+    pub fn make_statement_nop(&mut self, location: Location) {
+        let block = &mut self[location.block];
+        debug_assert!(location.statement_index < block.statements.len());
+        block.statements[location.statement_index].make_nop()
+    }
 }
 
 impl<'tcx> Index<BasicBlock> for Mir<'tcx> {
@@ -686,6 +712,14 @@ pub struct Statement<'tcx> {
     pub kind: StatementKind<'tcx>,
 }
 
+impl<'tcx> Statement<'tcx> {
+    /// Changes a statement to a nop. This is both faster than deleting instructions and avoids
+    /// invalidating statement indices in `Location`s.
+    pub fn make_nop(&mut self) {
+        self.kind = StatementKind::Nop
+    }
+}
+
 #[derive(Clone, Debug, RustcEncodable, RustcDecodable)]
 pub enum StatementKind<'tcx> {
     /// Write the RHS Rvalue to the LHS Lvalue.
@@ -699,6 +733,9 @@ pub enum StatementKind<'tcx> {
 
     /// End the current live range for the storage of the local.
     StorageDead(Lvalue<'tcx>),
+
+    /// No-op. Useful for deleting instructions without affecting statement indices.
+    Nop,
 }
 
 impl<'tcx> Debug for Statement<'tcx> {
@@ -711,6 +748,7 @@ impl<'tcx> Debug for Statement<'tcx> {
             SetDiscriminant{lvalue: ref lv, variant_index: index} => {
                 write!(fmt, "discriminant({:?}) = {:?}", lv, index)
             }
+            Nop => write!(fmt, "nop"),
         }
     }
 }
@@ -824,6 +862,24 @@ impl<'tcx> Lvalue<'tcx> {
             elem: elem,
         }))
     }
+
+    pub fn from_local(mir: &Mir<'tcx>, local: Local) -> Lvalue<'tcx> {
+        let mut index = local.index();
+        index = match index.checked_sub(mir.arg_decls.len()) {
+            None => return Lvalue::Arg(Arg(index as u32)),
+            Some(index) => index,
+        };
+        index = match index.checked_sub(mir.var_decls.len()) {
+            None => return Lvalue::Var(Var(index as u32)),
+            Some(index) => index,
+        };
+        index = match index.checked_sub(mir.temp_decls.len()) {
+            None => return Lvalue::Temp(Temp(index as u32)),
+            Some(index) => index,
+        };
+        debug_assert!(index == 0);
+        Lvalue::ReturnPointer
+    }
 }
 
 impl<'tcx> Debug for Lvalue<'tcx> {
@@ -1258,3 +1314,13 @@ impl fmt::Debug for Location {
         write!(fmt, "{:?}[{}]", self.block, self.statement_index)
     }
 }
+
+impl Location {
+    pub fn dominates(&self, other: &Location, dominators: &Dominators<BasicBlock>) -> bool {
+        if self.block == other.block {
+            self.statement_index <= other.statement_index
+        } else {
+            dominators.is_dominated_by(other.block, self.block)
+        }
+    }
+}
diff --git a/src/librustc/mir/visit.rs b/src/librustc/mir/visit.rs
index 16e0b376f4b..2c58d35973e 100644
--- a/src/librustc/mir/visit.rs
+++ b/src/librustc/mir/visit.rs
@@ -150,7 +150,7 @@ macro_rules! make_mir_visitor {
 
             fn visit_lvalue(&mut self,
                             lvalue: & $($mutability)* Lvalue<'tcx>,
-                            context: LvalueContext,
+                            context: LvalueContext<'tcx>,
                             location: Location) {
                 self.super_lvalue(lvalue, context, location);
             }
@@ -346,6 +346,7 @@ macro_rules! make_mir_visitor {
                     StatementKind::StorageDead(ref $($mutability)* lvalue) => {
                         self.visit_lvalue(lvalue, LvalueContext::StorageDead, location);
                     }
+                    StatementKind::Nop => {}
                 }
             }
 
@@ -580,7 +581,7 @@ macro_rules! make_mir_visitor {
 
             fn super_lvalue(&mut self,
                             lvalue: & $($mutability)* Lvalue<'tcx>,
-                            context: LvalueContext,
+                            context: LvalueContext<'tcx>,
                             location: Location) {
                 match *lvalue {
                     Lvalue::Var(_) |
@@ -605,7 +606,12 @@ macro_rules! make_mir_visitor {
                     ref $($mutability)* base,
                     ref $($mutability)* elem,
                 } = *proj;
-                self.visit_lvalue(base, LvalueContext::Projection, location);
+                let context = if context.is_mutating_use() {
+                    LvalueContext::Projection(Mutability::Mut)
+                } else {
+                    LvalueContext::Projection(Mutability::Not)
+                };
+                self.visit_lvalue(base, context, location);
                 self.visit_projection_elem(elem, context, location);
             }
 
@@ -750,6 +756,21 @@ macro_rules! make_mir_visitor {
 
             fn super_const_usize(&mut self, _substs: & $($mutability)* ConstUsize) {
             }
+
+            // Convenience methods
+
+            fn visit_location(&mut self, mir: & $($mutability)* Mir<'tcx>, location: Location) {
+                let basic_block = & $($mutability)* mir[location.block];
+                if basic_block.statements.len() == location.statement_index {
+                    if let Some(ref $($mutability)* terminator) = basic_block.terminator {
+                        self.visit_terminator(location.block, terminator, location)
+                    }
+                } else {
+                    let statement = & $($mutability)*
+                        basic_block.statements[location.statement_index];
+                    self.visit_statement(location.block, statement, location)
+                }
+            }
         }
     }
 }
@@ -774,8 +795,20 @@ pub enum LvalueContext<'tcx> {
     // Being borrowed
     Borrow { region: &'tcx Region, kind: BorrowKind },
 
-    // Used as base for another lvalue, e.g. `x` in `x.y`
-    Projection,
+    // Used as base for another lvalue, e.g. `x` in `x.y`.
+    //
+    // The `Mutability` argument specifies whether the projection is being performed in order to
+    // (potentially) mutate the lvalue. For example, the projection `x.y` is marked as a mutation
+    // in these cases:
+    //
+    //     x.y = ...;
+    //     f(&mut x.y);
+    //
+    // But not in these cases:
+    //
+    //     z = x.y;
+    //     f(&x.y);
+    Projection(Mutability),
 
     // Consumed as part of an operand
     Consume,
@@ -784,3 +817,69 @@ pub enum LvalueContext<'tcx> {
     StorageLive,
     StorageDead,
 }
+
+impl<'tcx> LvalueContext<'tcx> {
+    /// Returns true if this lvalue context represents a drop.
+    pub fn is_drop(&self) -> bool {
+        match *self {
+            LvalueContext::Drop => true,
+            _ => false,
+        }
+    }
+
+    /// Returns true if this lvalue context represents a storage live or storage dead marker.
+    pub fn is_storage_marker(&self) -> bool {
+        match *self {
+            LvalueContext::StorageLive | LvalueContext::StorageDead => true,
+            _ => false,
+        }
+    }
+
+    /// Returns true if this lvalue context represents a storage live marker.
+    pub fn is_storage_live_marker(&self) -> bool {
+        match *self {
+            LvalueContext::StorageLive => true,
+            _ => false,
+        }
+    }
+
+    /// Returns true if this lvalue context represents a storage dead marker.
+    pub fn is_storage_dead_marker(&self) -> bool {
+        match *self {
+            LvalueContext::StorageDead => true,
+            _ => false,
+        }
+    }
+
+    /// Returns true if this lvalue context represents a use that potentially changes the value.
+    pub fn is_mutating_use(&self) -> bool {
+        match *self {
+            LvalueContext::Store | LvalueContext::Call |
+            LvalueContext::Borrow { kind: BorrowKind::Mut, .. } |
+            LvalueContext::Projection(Mutability::Mut) |
+            LvalueContext::Drop => true,
+            LvalueContext::Inspect |
+            LvalueContext::Borrow { kind: BorrowKind::Shared, .. } |
+            LvalueContext::Borrow { kind: BorrowKind::Unique, .. } |
+            LvalueContext::Projection(Mutability::Not) | LvalueContext::Consume |
+            LvalueContext::StorageLive | LvalueContext::StorageDead => false,
+        }
+    }
+
+    /// Returns true if this lvalue context represents a use that does not change the value.
+    pub fn is_nonmutating_use(&self) -> bool {
+        match *self {
+            LvalueContext::Inspect | LvalueContext::Borrow { kind: BorrowKind::Shared, .. } |
+            LvalueContext::Borrow { kind: BorrowKind::Unique, .. } |
+            LvalueContext::Projection(Mutability::Not) | LvalueContext::Consume => true,
+            LvalueContext::Borrow { kind: BorrowKind::Mut, .. } | LvalueContext::Store |
+            LvalueContext::Call | LvalueContext::Projection(Mutability::Mut) |
+            LvalueContext::Drop | LvalueContext::StorageLive | LvalueContext::StorageDead => false,
+        }
+    }
+
+    pub fn is_use(&self) -> bool {
+        self.is_mutating_use() || self.is_nonmutating_use()
+    }
+}
+
diff --git a/src/librustc_borrowck/borrowck/mir/dataflow/impls.rs b/src/librustc_borrowck/borrowck/mir/dataflow/impls.rs
index 8ac59c60396..55dda8eda3a 100644
--- a/src/librustc_borrowck/borrowck/mir/dataflow/impls.rs
+++ b/src/librustc_borrowck/borrowck/mir/dataflow/impls.rs
@@ -455,7 +455,8 @@ impl<'a, 'tcx> BitDenotation for MovingOutStatements<'a, 'tcx> {
                                      });
             }
             repr::StatementKind::StorageLive(_) |
-            repr::StatementKind::StorageDead(_) => {}
+            repr::StatementKind::StorageDead(_) |
+            repr::StatementKind::Nop => {}
         }
     }
 
diff --git a/src/librustc_borrowck/borrowck/mir/dataflow/sanity_check.rs b/src/librustc_borrowck/borrowck/mir/dataflow/sanity_check.rs
index 88f6d5fef56..aeb91f06a9a 100644
--- a/src/librustc_borrowck/borrowck/mir/dataflow/sanity_check.rs
+++ b/src/librustc_borrowck/borrowck/mir/dataflow/sanity_check.rs
@@ -105,7 +105,8 @@ fn each_block<'a, 'tcx, O>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                 (lvalue, rvalue)
             }
             repr::StatementKind::StorageLive(_) |
-            repr::StatementKind::StorageDead(_) => continue,
+            repr::StatementKind::StorageDead(_) |
+            repr::StatementKind::Nop => continue,
             repr::StatementKind::SetDiscriminant{ .. } =>
                 span_bug!(stmt.source_info.span,
                           "sanity_check should run before Deaggregator inserts SetDiscriminant"),
diff --git a/src/librustc_borrowck/borrowck/mir/gather_moves.rs b/src/librustc_borrowck/borrowck/mir/gather_moves.rs
index bd38f554dc9..6346c1e5889 100644
--- a/src/librustc_borrowck/borrowck/mir/gather_moves.rs
+++ b/src/librustc_borrowck/borrowck/mir/gather_moves.rs
@@ -438,6 +438,7 @@ impl<'a, 'tcx> MoveDataBuilder<'a, 'tcx> {
                 span_bug!(stmt.source_info.span,
                           "SetDiscriminant should not exist during borrowck");
             }
+            StatementKind::Nop => {}
         }
     }
 
diff --git a/src/librustc_borrowck/borrowck/mir/mod.rs b/src/librustc_borrowck/borrowck/mir/mod.rs
index 5b5d782bc83..f26afdc2b85 100644
--- a/src/librustc_borrowck/borrowck/mir/mod.rs
+++ b/src/librustc_borrowck/borrowck/mir/mod.rs
@@ -389,7 +389,8 @@ fn drop_flag_effects_for_location<'a, 'tcx, F>(
                                        |moi| callback(moi, DropFlagState::Present))
             }
             repr::StatementKind::StorageLive(_) |
-            repr::StatementKind::StorageDead(_) => {}
+            repr::StatementKind::StorageDead(_) |
+            repr::StatementKind::Nop => {}
         },
         None => {
             debug!("drop_flag_effects: replace {:?}", block.terminator());
diff --git a/src/librustc_driver/driver.rs b/src/librustc_driver/driver.rs
index c02c5f18b4c..55892801247 100644
--- a/src/librustc_driver/driver.rs
+++ b/src/librustc_driver/driver.rs
@@ -1028,6 +1028,7 @@ pub fn phase_4_translate_to_llvm<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
         // No lifetime analysis based on borrowing can be done from here on out.
         passes.push_pass(box mir::transform::instcombine::InstCombine::new());
         passes.push_pass(box mir::transform::deaggregator::Deaggregator);
+        passes.push_pass(box mir::transform::copy_prop::CopyPropagation);
 
         passes.push_pass(box mir::transform::add_call_guards::AddCallGuards);
         passes.push_pass(box mir::transform::dump_mir::Marker("PreTrans"));
diff --git a/src/librustc_mir/def_use.rs b/src/librustc_mir/def_use.rs
new file mode 100644
index 00000000000..7329a20c497
--- /dev/null
+++ b/src/librustc_mir/def_use.rs
@@ -0,0 +1,197 @@
+// Copyright 2016 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+//! Def-use analysis.
+
+use rustc::mir::repr::{Local, Location, Lvalue, Mir};
+use rustc::mir::visit::{LvalueContext, MutVisitor, Visitor};
+use rustc_data_structures::indexed_vec::{Idx, IndexVec};
+use std::marker::PhantomData;
+use std::mem;
+
+pub struct DefUseAnalysis<'tcx> {
+    info: IndexVec<Local, Info<'tcx>>,
+    mir_summary: MirSummary,
+}
+
+#[derive(Clone)]
+pub struct Info<'tcx> {
+    pub defs_and_uses: Vec<Use<'tcx>>,
+}
+
+#[derive(Clone)]
+pub struct Use<'tcx> {
+    pub context: LvalueContext<'tcx>,
+    pub location: Location,
+}
+
+impl<'tcx> DefUseAnalysis<'tcx> {
+    pub fn new(mir: &Mir<'tcx>) -> DefUseAnalysis<'tcx> {
+        DefUseAnalysis {
+            info: IndexVec::from_elem_n(Info::new(), mir.count_locals()),
+            mir_summary: MirSummary::new(mir),
+        }
+    }
+
+    pub fn analyze(&mut self, mir: &Mir<'tcx>) {
+        let mut finder = DefUseFinder {
+            info: mem::replace(&mut self.info, IndexVec::new()),
+            mir_summary: self.mir_summary,
+        };
+        finder.visit_mir(mir);
+        self.info = finder.info
+    }
+
+    pub fn local_info(&self, local: Local) -> &Info<'tcx> {
+        &self.info[local]
+    }
+
+    pub fn local_info_mut(&mut self, local: Local) -> &mut Info<'tcx> {
+        &mut self.info[local]
+    }
+
+    fn mutate_defs_and_uses<F>(&self, local: Local, mir: &mut Mir<'tcx>, mut callback: F)
+                               where F: for<'a> FnMut(&'a mut Lvalue<'tcx>,
+                                                      LvalueContext<'tcx>,
+                                                      Location) {
+        for lvalue_use in &self.info[local].defs_and_uses {
+            MutateUseVisitor::new(local,
+                                  &mut callback,
+                                  self.mir_summary,
+                                  mir).visit_location(mir, lvalue_use.location)
+        }
+    }
+
+    /// FIXME(pcwalton): This should update the def-use chains.
+    pub fn replace_all_defs_and_uses_with(&self,
+                                          local: Local,
+                                          mir: &mut Mir<'tcx>,
+                                          new_lvalue: Lvalue<'tcx>) {
+        self.mutate_defs_and_uses(local, mir, |lvalue, _, _| *lvalue = new_lvalue.clone())
+    }
+}
+
+struct DefUseFinder<'tcx> {
+    info: IndexVec<Local, Info<'tcx>>,
+    mir_summary: MirSummary,
+}
+
+impl<'tcx> DefUseFinder<'tcx> {
+    fn lvalue_mut_info(&mut self, lvalue: &Lvalue<'tcx>) -> Option<&mut Info<'tcx>> {
+        let info = &mut self.info;
+        self.mir_summary.local_index(lvalue).map(move |local| &mut info[local])
+    }
+}
+
+impl<'tcx> Visitor<'tcx> for DefUseFinder<'tcx> {
+    fn visit_lvalue(&mut self,
+                    lvalue: &Lvalue<'tcx>,
+                    context: LvalueContext<'tcx>,
+                    location: Location) {
+        if let Some(ref mut info) = self.lvalue_mut_info(lvalue) {
+            info.defs_and_uses.push(Use {
+                context: context,
+                location: location,
+            })
+        }
+        self.super_lvalue(lvalue, context, location)
+    }
+}
+
+impl<'tcx> Info<'tcx> {
+    fn new() -> Info<'tcx> {
+        Info {
+            defs_and_uses: vec![],
+        }
+    }
+
+    pub fn def_count(&self) -> usize {
+        self.defs_and_uses.iter().filter(|lvalue_use| lvalue_use.context.is_mutating_use()).count()
+    }
+
+    pub fn def_count_not_including_drop(&self) -> usize {
+        self.defs_and_uses.iter().filter(|lvalue_use| {
+            lvalue_use.context.is_mutating_use() && !lvalue_use.context.is_drop()
+        }).count()
+    }
+
+    pub fn use_count(&self) -> usize {
+        self.defs_and_uses.iter().filter(|lvalue_use| {
+            lvalue_use.context.is_nonmutating_use()
+        }).count()
+    }
+}
+
+struct MutateUseVisitor<'tcx, F> {
+    query: Local,
+    callback: F,
+    mir_summary: MirSummary,
+    phantom: PhantomData<&'tcx ()>,
+}
+
+impl<'tcx, F> MutateUseVisitor<'tcx, F> {
+    fn new(query: Local, callback: F, mir_summary: MirSummary, _: &Mir<'tcx>)
+           -> MutateUseVisitor<'tcx, F>
+           where F: for<'a> FnMut(&'a mut Lvalue<'tcx>, LvalueContext<'tcx>, Location) {
+        MutateUseVisitor {
+            query: query,
+            callback: callback,
+            mir_summary: mir_summary,
+            phantom: PhantomData,
+        }
+    }
+}
+
+impl<'tcx, F> MutVisitor<'tcx> for MutateUseVisitor<'tcx, F>
+              where F: for<'a> FnMut(&'a mut Lvalue<'tcx>, LvalueContext<'tcx>, Location) {
+    fn visit_lvalue(&mut self,
+                    lvalue: &mut Lvalue<'tcx>,
+                    context: LvalueContext<'tcx>,
+                    location: Location) {
+        if self.mir_summary.local_index(lvalue) == Some(self.query) {
+            (self.callback)(lvalue, context, location)
+        }
+        self.super_lvalue(lvalue, context, location)
+    }
+}
+
+/// A small structure that enables various metadata of the MIR to be queried
+/// without a reference to the MIR itself.
+#[derive(Clone, Copy)]
+struct MirSummary {
+    arg_count: usize,
+    var_count: usize,
+    temp_count: usize,
+}
+
+impl MirSummary {
+    fn new(mir: &Mir) -> MirSummary {
+        MirSummary {
+            arg_count: mir.arg_decls.len(),
+            var_count: mir.var_decls.len(),
+            temp_count: mir.temp_decls.len(),
+        }
+    }
+
+    fn local_index<'tcx>(&self, lvalue: &Lvalue<'tcx>) -> Option<Local> {
+        match *lvalue {
+            Lvalue::Arg(arg) => Some(Local::new(arg.index())),
+            Lvalue::Var(var) => Some(Local::new(var.index() + self.arg_count)),
+            Lvalue::Temp(temp) => {
+                Some(Local::new(temp.index() + self.arg_count + self.var_count))
+            }
+            Lvalue::ReturnPointer => {
+                Some(Local::new(self.arg_count + self.var_count + self.temp_count))
+            }
+            _ => None,
+        }
+    }
+}
+
diff --git a/src/librustc_mir/lib.rs b/src/librustc_mir/lib.rs
index f580ceeee5d..12f1eb8535a 100644
--- a/src/librustc_mir/lib.rs
+++ b/src/librustc_mir/lib.rs
@@ -46,8 +46,10 @@ extern crate rustc_const_eval;
 pub mod diagnostics;
 
 pub mod build;
+pub mod def_use;
 pub mod graphviz;
 mod hair;
 pub mod mir_map;
 pub mod pretty;
 pub mod transform;
+
diff --git a/src/librustc_mir/transform/copy_prop.rs b/src/librustc_mir/transform/copy_prop.rs
new file mode 100644
index 00000000000..33f3d6d8842
--- /dev/null
+++ b/src/librustc_mir/transform/copy_prop.rs
@@ -0,0 +1,180 @@
+// Copyright 2016 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+//! Trivial copy propagation pass.
+//!
+//! This uses def-use analysis to remove values that have exactly one def and one use, which must
+//! be an assignment.
+//!
+//! To give an example, we look for patterns that look like:
+//!
+//!     DEST = SRC
+//!     ...
+//!     USE(DEST)
+//!
+//! where `DEST` and `SRC` are both locals of some form. We replace that with:
+//!
+//!     NOP
+//!     ...
+//!     USE(SRC)
+//!
+//! The assignment `DEST = SRC` must be (a) the only mutation of `DEST` and (b) the only
+//! (non-mutating) use of `SRC`. These restrictions are conservative and may be relaxed in the
+//! future.
+
+use def_use::DefUseAnalysis;
+use rustc::mir::repr::{Local, Lvalue, Mir, Operand, Rvalue, StatementKind};
+use rustc::mir::transform::{MirPass, MirSource, Pass};
+use rustc::ty::TyCtxt;
+use rustc_data_structures::indexed_vec::Idx;
+
+pub struct CopyPropagation;
+
+impl Pass for CopyPropagation {}
+
+impl<'tcx> MirPass<'tcx> for CopyPropagation {
+    fn run_pass<'a>(&mut self, _: TyCtxt<'a, 'tcx, 'tcx>, _: MirSource, mir: &mut Mir<'tcx>) {
+        loop {
+            let mut def_use_analysis = DefUseAnalysis::new(mir);
+            def_use_analysis.analyze(mir);
+
+            let mut changed = false;
+            for dest_local_index in 0..mir.count_locals() {
+                let dest_local = Local::new(dest_local_index);
+                debug!("Considering destination local: {}", mir.format_local(dest_local));
+
+                let src_local;
+                let location;
+                {
+                    // The destination must have exactly one def.
+                    let dest_use_info = def_use_analysis.local_info(dest_local);
+                    let dest_def_count = dest_use_info.def_count_not_including_drop();
+                    if dest_def_count == 0 {
+                        debug!("  Can't copy-propagate local: dest {} undefined",
+                               mir.format_local(dest_local));
+                        continue
+                    }
+                    if dest_def_count > 1 {
+                        debug!("  Can't copy-propagate local: dest {} defined {} times",
+                               mir.format_local(dest_local),
+                               dest_use_info.def_count());
+                        continue
+                    }
+                    if dest_use_info.use_count() == 0 {
+                        debug!("  Can't copy-propagate local: dest {} unused",
+                               mir.format_local(dest_local));
+                        continue
+                    }
+                    let dest_lvalue_def = dest_use_info.defs_and_uses.iter().filter(|lvalue_def| {
+                        lvalue_def.context.is_mutating_use() && !lvalue_def.context.is_drop()
+                    }).next().unwrap();
+                    location = dest_lvalue_def.location;
+
+                    let basic_block = &mir[location.block];
+                    let statement_index = location.statement_index;
+                    let statement = match basic_block.statements.get(statement_index) {
+                        Some(statement) => statement,
+                        None => {
+                            debug!("  Can't copy-propagate local: used in terminator");
+                            continue
+                        }
+                    };
+
+                    // That use of the source must be an assignment.
+                    let src_lvalue = match statement.kind {
+                        StatementKind::Assign(
+                                ref dest_lvalue,
+                                Rvalue::Use(Operand::Consume(ref src_lvalue)))
+                                if Some(dest_local) == mir.local_index(dest_lvalue) => {
+                            src_lvalue
+                        }
+                        _ => {
+                            debug!("  Can't copy-propagate local: source use is not an \
+                                    assignment");
+                            continue
+                        }
+                    };
+                    src_local = match mir.local_index(src_lvalue) {
+                        Some(src_local) => src_local,
+                        None => {
+                            debug!("  Can't copy-propagate local: source is not a local");
+                            continue
+                        }
+                    };
+
+                    // There must be exactly one use of the source used in a statement (not in a
+                    // terminator).
+                    let src_use_info = def_use_analysis.local_info(src_local);
+                    let src_use_count = src_use_info.use_count();
+                    if src_use_count == 0 {
+                        debug!("  Can't copy-propagate local: no uses");
+                        continue
+                    }
+                    if src_use_count != 1 {
+                        debug!("  Can't copy-propagate local: {} uses", src_use_info.use_count());
+                        continue
+                    }
+
+                    // Verify that the source doesn't change in between. This is done
+                    // conservatively for now, by ensuring that the source has exactly one
+                    // mutation. The goal is to prevent things like:
+                    //
+                    //     DEST = SRC;
+                    //     SRC = X;
+                    //     USE(DEST);
+                    //
+                    // From being misoptimized into:
+                    //
+                    //     SRC = X;
+                    //     USE(SRC);
+                    let src_def_count = src_use_info.def_count_not_including_drop();
+                    if src_def_count != 1 {
+                        debug!("  Can't copy-propagate local: {} defs of src",
+                               src_use_info.def_count_not_including_drop());
+                        continue
+                    }
+                }
+
+                // If all checks passed, then we can eliminate the destination and the assignment.
+                //
+                // First, remove all markers.
+                //
+                // FIXME(pcwalton): Don't do this. Merge live ranges instead.
+                debug!("  Replacing all uses of {}", mir.format_local(dest_local));
+                for lvalue_use in &def_use_analysis.local_info(dest_local).defs_and_uses {
+                    if lvalue_use.context.is_storage_marker() {
+                        mir.make_statement_nop(lvalue_use.location)
+                    }
+                }
+                for lvalue_use in &def_use_analysis.local_info(src_local).defs_and_uses {
+                    if lvalue_use.context.is_storage_marker() {
+                        mir.make_statement_nop(lvalue_use.location)
+                    }
+                }
+
+                // Now replace all uses of the destination local with the source local.
+                let src_lvalue = Lvalue::from_local(mir, src_local);
+                def_use_analysis.replace_all_defs_and_uses_with(dest_local, mir, src_lvalue);
+
+                // Finally, zap the now-useless assignment instruction.
+                mir.make_statement_nop(location);
+
+                changed = true;
+                // FIXME(pcwalton): Update the use-def chains to delete the instructions instead of
+                // regenerating the chains.
+                break
+            }
+            if !changed {
+                break
+            }
+        }
+    }
+}
+
diff --git a/src/librustc_mir/transform/mod.rs b/src/librustc_mir/transform/mod.rs
index e99b7a976e3..7bcb89b5895 100644
--- a/src/librustc_mir/transform/mod.rs
+++ b/src/librustc_mir/transform/mod.rs
@@ -19,4 +19,4 @@ pub mod qualify_consts;
 pub mod dump_mir;
 pub mod deaggregator;
 pub mod instcombine;
-
+pub mod copy_prop;
diff --git a/src/librustc_mir/transform/promote_consts.rs b/src/librustc_mir/transform/promote_consts.rs
index f864f1678f2..57de68fce1d 100644
--- a/src/librustc_mir/transform/promote_consts.rs
+++ b/src/librustc_mir/transform/promote_consts.rs
@@ -328,7 +328,7 @@ impl<'a, 'tcx> Promoter<'a, 'tcx> {
 impl<'a, 'tcx> MutVisitor<'tcx> for Promoter<'a, 'tcx> {
     fn visit_lvalue(&mut self,
                     lvalue: &mut Lvalue<'tcx>,
-                    context: LvalueContext,
+                    context: LvalueContext<'tcx>,
                     location: Location) {
         if let Lvalue::Temp(ref mut temp) = *lvalue {
             *temp = self.promote_temp(*temp);
diff --git a/src/librustc_mir/transform/qualify_consts.rs b/src/librustc_mir/transform/qualify_consts.rs
index a3f8f7a63ee..c3a22853f84 100644
--- a/src/librustc_mir/transform/qualify_consts.rs
+++ b/src/librustc_mir/transform/qualify_consts.rs
@@ -475,7 +475,10 @@ impl<'a, 'tcx> Qualifier<'a, 'tcx, 'tcx> {
 /// For functions (constant or not), it also records
 /// candidates for promotion in promotion_candidates.
 impl<'a, 'tcx> Visitor<'tcx> for Qualifier<'a, 'tcx, 'tcx> {
-    fn visit_lvalue(&mut self, lvalue: &Lvalue<'tcx>, context: LvalueContext, location: Location) {
+    fn visit_lvalue(&mut self,
+                    lvalue: &Lvalue<'tcx>,
+                    context: LvalueContext<'tcx>,
+                    location: Location) {
         match *lvalue {
             Lvalue::Arg(_) => {
                 self.add(Qualif::FN_ARGUMENT);
@@ -910,7 +913,8 @@ impl<'a, 'tcx> Visitor<'tcx> for Qualifier<'a, 'tcx, 'tcx> {
                 }
                 StatementKind::SetDiscriminant { .. } |
                 StatementKind::StorageLive(_) |
-                StatementKind::StorageDead(_) => {}
+                StatementKind::StorageDead(_) |
+                StatementKind::Nop => {}
             }
         });
     }
diff --git a/src/librustc_mir/transform/type_check.rs b/src/librustc_mir/transform/type_check.rs
index 7fda658185e..412759cd5b2 100644
--- a/src/librustc_mir/transform/type_check.rs
+++ b/src/librustc_mir/transform/type_check.rs
@@ -385,6 +385,7 @@ impl<'a, 'gcx, 'tcx> TypeChecker<'a, 'gcx, 'tcx> {
                     }
                 }
             }
+            StatementKind::Nop => {}
         }
     }
 
diff --git a/src/librustc_trans/collector.rs b/src/librustc_trans/collector.rs
index a58de71ca41..6648944540e 100644
--- a/src/librustc_trans/collector.rs
+++ b/src/librustc_trans/collector.rs
@@ -523,7 +523,7 @@ impl<'a, 'tcx> MirVisitor<'tcx> for MirNeighborCollector<'a, 'tcx> {
 
     fn visit_lvalue(&mut self,
                     lvalue: &mir::Lvalue<'tcx>,
-                    context: mir_visit::LvalueContext,
+                    context: mir_visit::LvalueContext<'tcx>,
                     location: Location) {
         debug!("visiting lvalue {:?}", *lvalue);
 
diff --git a/src/librustc_trans/mir/analyze.rs b/src/librustc_trans/mir/analyze.rs
index e13da253102..5de59b9f6bd 100644
--- a/src/librustc_trans/mir/analyze.rs
+++ b/src/librustc_trans/mir/analyze.rs
@@ -147,7 +147,7 @@ impl<'mir, 'bcx, 'tcx> Visitor<'tcx> for LocalAnalyzer<'mir, 'bcx, 'tcx> {
 
     fn visit_lvalue(&mut self,
                     lvalue: &mir::Lvalue<'tcx>,
-                    context: LvalueContext,
+                    context: LvalueContext<'tcx>,
                     location: Location) {
         debug!("visit_lvalue(lvalue={:?}, context={:?})", lvalue, context);
 
@@ -180,7 +180,7 @@ impl<'mir, 'bcx, 'tcx> Visitor<'tcx> for LocalAnalyzer<'mir, 'bcx, 'tcx> {
                 LvalueContext::Store |
                 LvalueContext::Inspect |
                 LvalueContext::Borrow { .. } |
-                LvalueContext::Projection => {
+                LvalueContext::Projection(..) => {
                     self.mark_as_lvalue(index);
                 }
 
diff --git a/src/librustc_trans/mir/constant.rs b/src/librustc_trans/mir/constant.rs
index e9f324c0b08..70d0a618404 100644
--- a/src/librustc_trans/mir/constant.rs
+++ b/src/librustc_trans/mir/constant.rs
@@ -292,7 +292,8 @@ impl<'a, 'tcx> MirConstContext<'a, 'tcx> {
                         }
                     }
                     mir::StatementKind::StorageLive(_) |
-                    mir::StatementKind::StorageDead(_) => {}
+                    mir::StatementKind::StorageDead(_) |
+                    mir::StatementKind::Nop => {}
                     mir::StatementKind::SetDiscriminant{ .. } => {
                         span_bug!(span, "SetDiscriminant should not appear in constants?");
                     }
diff --git a/src/librustc_trans/mir/statement.rs b/src/librustc_trans/mir/statement.rs
index 11672089553..325bd655266 100644
--- a/src/librustc_trans/mir/statement.rs
+++ b/src/librustc_trans/mir/statement.rs
@@ -78,6 +78,7 @@ impl<'bcx, 'tcx> MirContext<'bcx, 'tcx> {
             mir::StatementKind::StorageDead(ref lvalue) => {
                 self.trans_storage_liveness(bcx, lvalue, base::Lifetime::End)
             }
+            mir::StatementKind::Nop => bcx,
         }
     }
 
diff --git a/src/test/codegen/refs.rs b/src/test/codegen/refs.rs
index 49ed2229fcd..891ca03cc4d 100644
--- a/src/test/codegen/refs.rs
+++ b/src/test/codegen/refs.rs
@@ -23,9 +23,9 @@ fn helper(_: usize) {
 pub fn ref_dst(s: &[u8]) {
     // We used to generate an extra alloca and memcpy to ref the dst, so check that we copy
     // directly to the alloca for "x"
-// CHECK: [[X0:%[0-9]+]] = getelementptr {{.*}} { i8*, [[USIZE]] }* %x, i32 0, i32 0
+// CHECK: [[X0:%[0-9]+]] = getelementptr {{.*}} { i8*, [[USIZE]] }* %s, i32 0, i32 0
 // CHECK: store i8* %0, i8** [[X0]]
-// CHECK: [[X1:%[0-9]+]] = getelementptr {{.*}} { i8*, [[USIZE]] }* %x, i32 0, i32 1
+// CHECK: [[X1:%[0-9]+]] = getelementptr {{.*}} { i8*, [[USIZE]] }* %s, i32 0, i32 1
 // CHECK: store [[USIZE]] %1, [[USIZE]]* [[X1]]
 
     let x = &*s;
diff --git a/src/test/mir-opt/storage_ranges.rs b/src/test/mir-opt/storage_ranges.rs
index f93447b642a..8782dcf8898 100644
--- a/src/test/mir-opt/storage_ranges.rs
+++ b/src/test/mir-opt/storage_ranges.rs
@@ -21,27 +21,27 @@ fn main() {
 // END RUST SOURCE
 // START rustc.node4.PreTrans.after.mir
 //     bb0: {
-//         StorageLive(var0);               // scope 0 at storage_ranges.rs:12:9: 12:10
-//         var0 = const 0i32;               // scope 0 at storage_ranges.rs:12:13: 12:14
-//         StorageLive(var1);               // scope 1 at storage_ranges.rs:14:13: 14:14
-//         StorageLive(tmp1);               // scope 1 at storage_ranges.rs:14:18: 14:25
-//         StorageLive(tmp2);               // scope 1 at storage_ranges.rs:14:23: 14:24
-//         tmp2 = var0;                     // scope 1 at storage_ranges.rs:14:23: 14:24
-//         tmp1 = std::option::Option<i32>::Some(tmp2,); // scope 1 at storage_ranges.rs:14:18: 14:25
-//         var1 = &tmp1;                    // scope 1 at storage_ranges.rs:14:17: 14:25
-//         StorageDead(tmp2);               // scope 1 at storage_ranges.rs:14:23: 14:24
-//         tmp0 = ();                       // scope 2 at storage_ranges.rs:13:5: 15:6
-//         StorageDead(tmp1);               // scope 1 at storage_ranges.rs:14:18: 14:25
-//         StorageDead(var1);               // scope 1 at storage_ranges.rs:14:13: 14:14
-//         StorageLive(var2);               // scope 1 at storage_ranges.rs:16:9: 16:10
-//         var2 = const 1i32;               // scope 1 at storage_ranges.rs:16:13: 16:14
-//         return = ();                     // scope 3 at storage_ranges.rs:11:11: 17:2
-//         StorageDead(var2);               // scope 1 at storage_ranges.rs:16:9: 16:10
-//         StorageDead(var0);               // scope 0 at storage_ranges.rs:12:9: 12:10
-//         goto -> bb1;                     // scope 0 at storage_ranges.rs:11:1: 17:2
+//         nop;                             // scope 0 at storage_ranges.rs:14:9: 14:10
+//         var0 = const 0i32;               // scope 0 at storage_ranges.rs:14:13: 14:14
+//         StorageLive(var1);               // scope 1 at storage_ranges.rs:16:13: 16:14
+//         StorageLive(tmp1);               // scope 1 at storage_ranges.rs:16:18: 16:25
+//         nop;                             // scope 1 at storage_ranges.rs:16:23: 16:24
+//         nop;                             // scope 1 at storage_ranges.rs:16:23: 16:24
+//         tmp1 = std::option::Option<i32>::Some(var0,); // scope 1 at storage_ranges.rs:16:18: 16:25
+//         var1 = &tmp1;                    // scope 1 at storage_ranges.rs:16:17: 16:25
+//         nop;                             // scope 1 at storage_ranges.rs:16:23: 16:24
+//         tmp0 = ();                       // scope 2 at storage_ranges.rs:15:5: 17:6
+//         StorageDead(tmp1);               // scope 1 at storage_ranges.rs:16:18: 16:25
+//         StorageDead(var1);               // scope 1 at storage_ranges.rs:16:13: 16:14
+//         StorageLive(var2);               // scope 1 at storage_ranges.rs:18:9: 18:10
+//         var2 = const 1i32;               // scope 1 at storage_ranges.rs:18:13: 18:14
+//         return = ();                     // scope 3 at storage_ranges.rs:13:11: 19:2
+//         StorageDead(var2);               // scope 1 at storage_ranges.rs:18:9: 18:10
+//         nop;                             // scope 0 at storage_ranges.rs:14:9: 14:10
+//         goto -> bb1;                     // scope 0 at storage_ranges.rs:13:1: 19:2
 //     }
 //
 //     bb1: {
-//         return;                          // scope 0 at storage_ranges.rs:11:1: 17:2
+//         return;                          // scope 0 at storage_ranges.rs:13:1: 19:2
 //     }
 // END rustc.node4.PreTrans.after.mir