move the drop expansion code to rustc_mir

10 files changed, 766 insertions, 9 deletions

diff --git a/src/librustc_mir/lib.rs b/src/librustc_mir/lib.rs
index 2718a0204a1..590c6a430b9 100644
--- a/src/librustc_mir/lib.rs
+++ b/src/librustc_mir/lib.rs
@@ -49,13 +49,11 @@ pub mod diagnostics;
 
 pub mod build;
 pub mod callgraph;
-pub mod def_use;
-pub mod graphviz;
 mod hair;
 mod shim;
 pub mod mir_map;
-pub mod pretty;
 pub mod transform;
+pub mod util;
 
 use rustc::ty::maps::Providers;
 
diff --git a/src/librustc_mir/mir_map.rs b/src/librustc_mir/mir_map.rs
index 2d2b90235ca..8c138d779c1 100644
--- a/src/librustc_mir/mir_map.rs
+++ b/src/librustc_mir/mir_map.rs
@@ -23,8 +23,8 @@ use rustc::mir::Mir;
 use rustc::mir::transform::MirSource;
 use rustc::mir::visit::MutVisitor;
 use shim;
-use pretty;
 use hair::cx::Cx;
+use util as mir_util;
 
 use rustc::traits::Reveal;
 use rustc::ty::{self, Ty, TyCtxt};
@@ -175,7 +175,7 @@ fn build_mir<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId)
             mem::transmute::<Mir, Mir<'tcx>>(mir)
         };
 
-        pretty::dump_mir(tcx, "mir_map", &0, src, &mir);
+        mir_util::dump_mir(tcx, "mir_map", &0, src, &mir);
 
         tcx.alloc_mir(mir)
     })
@@ -234,7 +234,7 @@ fn create_constructor_shim<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                 mem::transmute::<Mir, Mir<'tcx>>(mir)
             };
 
-            pretty::dump_mir(tcx, "mir_map", &0, src, &mir);
+            mir_util::dump_mir(tcx, "mir_map", &0, src, &mir);
 
             tcx.alloc_mir(mir)
         })
diff --git a/src/librustc_mir/transform/copy_prop.rs b/src/librustc_mir/transform/copy_prop.rs
index 2194c20c2f4..5d127a5aed4 100644
--- a/src/librustc_mir/transform/copy_prop.rs
+++ b/src/librustc_mir/transform/copy_prop.rs
@@ -29,11 +29,11 @@
 //! (non-mutating) use of `SRC`. These restrictions are conservative and may be relaxed in the
 //! future.
 
-use def_use::DefUseAnalysis;
 use rustc::mir::{Constant, Local, LocalKind, Location, Lvalue, Mir, Operand, Rvalue, StatementKind};
 use rustc::mir::transform::{MirPass, MirSource, Pass};
 use rustc::mir::visit::MutVisitor;
 use rustc::ty::TyCtxt;
+use util::def_use::DefUseAnalysis;
 use transform::qualify_consts;
 
 pub struct CopyPropagation;
diff --git a/src/librustc_mir/transform/dump_mir.rs b/src/librustc_mir/transform/dump_mir.rs
index 035f33de91a..f22a71636a9 100644
--- a/src/librustc_mir/transform/dump_mir.rs
+++ b/src/librustc_mir/transform/dump_mir.rs
@@ -15,7 +15,7 @@ use std::fmt;
 use rustc::ty::TyCtxt;
 use rustc::mir::*;
 use rustc::mir::transform::{Pass, MirPass, MirPassHook, MirSource};
-use pretty;
+use util as mir_util;
 
 pub struct Marker<'a>(pub &'a str);
 
@@ -56,7 +56,7 @@ impl<'tcx> MirPassHook<'tcx> for DumpMir {
         pass: &Pass,
         is_after: bool)
     {
-        pretty::dump_mir(
+        mir_util::dump_mir(
             tcx,
             &*pass.name(),
             &Disambiguator {
diff --git a/src/librustc_mir/def_use.rs b/src/librustc_mir/util/def_use.rs
index d20d50c5611..d20d50c5611 100644
--- a/src/librustc_mir/def_use.rs
+++ b/src/librustc_mir/util/def_use.rs
diff --git a/src/librustc_mir/util/elaborate_drops.rs b/src/librustc_mir/util/elaborate_drops.rs
new file mode 100644
index 00000000000..ce6debab9a4
--- /dev/null
+++ b/src/librustc_mir/util/elaborate_drops.rs
@@ -0,0 +1,561 @@
+// Copyright 2017 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.
+
+use std::fmt;
+use rustc::mir::*;
+use rustc::middle::lang_items;
+use rustc::ty::{self, Ty};
+use rustc::ty::subst::{Kind, Subst, Substs};
+use rustc::ty::util::IntTypeExt;
+use rustc_data_structures::indexed_vec::Idx;
+use util::patch::MirPatch;
+
+use std::iter;
+
+#[derive(Debug, PartialEq, Eq, Copy, Clone)]
+pub enum DropFlagState {
+    Present, // i.e. initialized
+    Absent, // i.e. deinitialized or "moved"
+}
+
+impl DropFlagState {
+    pub fn value(self) -> bool {
+        match self {
+            DropFlagState::Present => true,
+            DropFlagState::Absent => false
+        }
+    }
+}
+
+#[derive(Debug)]
+pub enum DropStyle {
+    Dead,
+    Static,
+    Conditional,
+    Open,
+}
+
+#[derive(Debug)]
+pub enum DropFlagMode {
+    Shallow,
+    Deep
+}
+
+pub trait DropElaborator<'a, 'tcx: 'a> : fmt::Debug {
+    type Path : Copy + fmt::Debug;
+
+    fn patch(&mut self) -> &mut MirPatch<'tcx>;
+    fn mir(&self) -> &'a Mir<'tcx>;
+    fn tcx(&self) -> ty::TyCtxt<'a, 'tcx, 'tcx>;
+    fn param_env(&self) -> &'a ty::ParameterEnvironment<'tcx>;
+
+    fn drop_style(&self, path: Self::Path, mode: DropFlagMode) -> DropStyle;
+    fn get_drop_flag(&mut self, path: Self::Path) -> Option<Operand<'tcx>>;
+    fn clear_drop_flag(&mut self, location: Location, path: Self::Path, mode: DropFlagMode);
+
+
+    fn field_subpath(&self, path: Self::Path, field: Field) -> Option<Self::Path>;
+    fn deref_subpath(&self, path: Self::Path) -> Option<Self::Path>;
+    fn downcast_subpath(&self, path: Self::Path, variant: usize) -> Option<Self::Path>;
+}
+
+#[derive(Debug)]
+struct DropCtxt<'l, 'b: 'l, 'tcx: 'b, D>
+    where D : DropElaborator<'b, 'tcx> + 'l
+{
+    elaborator: &'l mut D,
+
+    source_info: SourceInfo,
+    is_cleanup: bool,
+
+    lvalue: &'l Lvalue<'tcx>,
+    path: D::Path,
+    succ: BasicBlock,
+    unwind: Option<BasicBlock>,
+}
+
+pub fn elaborate_drop<'b, 'tcx, D>(
+    elaborator: &mut D,
+    source_info: SourceInfo,
+    is_cleanup: bool,
+    lvalue: &Lvalue<'tcx>,
+    path: D::Path,
+    succ: BasicBlock,
+    unwind: Option<BasicBlock>,
+    bb: BasicBlock)
+    where D: DropElaborator<'b, 'tcx>
+{
+    DropCtxt {
+        elaborator, source_info, is_cleanup, lvalue, path, succ, unwind
+    }.elaborate_drop(bb)
+}
+
+impl<'l, 'b, 'tcx, D> DropCtxt<'l, 'b, 'tcx, D>
+    where D: DropElaborator<'b, 'tcx>
+{
+    fn lvalue_ty(&self, lvalue: &Lvalue<'tcx>) -> Ty<'tcx> {
+        lvalue.ty(self.elaborator.mir(), self.tcx()).to_ty(self.tcx())
+    }
+
+    fn tcx(&self) -> ty::TyCtxt<'b, 'tcx, 'tcx> {
+        self.elaborator.tcx()
+    }
+
+    /// This elaborates a single drop instruction, located at `bb`, and
+    /// patches over it.
+    ///
+    /// The elaborated drop checks the drop flags to only drop what
+    /// is initialized.
+    ///
+    /// In addition, the relevant drop flags also need to be cleared
+    /// to avoid double-drops. However, in the middle of a complex
+    /// drop, one must avoid clearing some of the flags before they
+    /// are read, as that would cause a memory leak.
+    ///
+    /// In particular, when dropping an ADT, multiple fields may be
+    /// joined together under the `rest` subpath. They are all controlled
+    /// by the primary drop flag, but only the last rest-field dropped
+    /// should clear it (and it must also not clear anything else).
+    ///
+    /// FIXME: I think we should just control the flags externally
+    /// and then we do not need this machinery.
+    pub fn elaborate_drop<'a>(&mut self, bb: BasicBlock) {
+        debug!("elaborate_drop({:?})", self);
+        let style = self.elaborator.drop_style(self.path, DropFlagMode::Deep);
+        debug!("elaborate_drop({:?}): live - {:?}", self, style);
+        match style {
+            DropStyle::Dead => {
+                self.elaborator.patch().patch_terminator(bb, TerminatorKind::Goto {
+                    target: self.succ
+                });
+            }
+            DropStyle::Static => {
+                let loc = self.terminator_loc(bb);
+                self.elaborator.clear_drop_flag(loc, self.path, DropFlagMode::Deep);
+                self.elaborator.patch().patch_terminator(bb, TerminatorKind::Drop {
+                    location: self.lvalue.clone(),
+                    target: self.succ,
+                    unwind: self.unwind
+                });
+            }
+            DropStyle::Conditional => {
+                let drop_bb = self.complete_drop(Some(DropFlagMode::Deep));
+                self.elaborator.patch().patch_terminator(bb, TerminatorKind::Goto {
+                    target: drop_bb
+                });
+            }
+            DropStyle::Open => {
+                let drop_bb = self.open_drop();
+                self.elaborator.patch().patch_terminator(bb, TerminatorKind::Goto {
+                    target: drop_bb
+                });
+            }
+        }
+    }
+
+    /// Return the lvalue and move path for each field of `variant`,
+    /// (the move path is `None` if the field is a rest field).
+    fn move_paths_for_fields(&self,
+                             base_lv: &Lvalue<'tcx>,
+                             variant_path: D::Path,
+                             variant: &'tcx ty::VariantDef,
+                             substs: &'tcx Substs<'tcx>)
+                             -> Vec<(Lvalue<'tcx>, Option<D::Path>)>
+    {
+        variant.fields.iter().enumerate().map(|(i, f)| {
+            let field = Field::new(i);
+            let subpath = self.elaborator.field_subpath(variant_path, field);
+
+            let field_ty =
+                self.tcx().normalize_associated_type_in_env(
+                    &f.ty(self.tcx(), substs),
+                    self.elaborator.param_env()
+                );
+            (base_lv.clone().field(field, field_ty), subpath)
+        }).collect()
+    }
+
+    fn drop_subpath(&mut self,
+                    is_cleanup: bool,
+                    lvalue: &Lvalue<'tcx>,
+                    path: Option<D::Path>,
+                    succ: BasicBlock,
+                    unwind: Option<BasicBlock>)
+                    -> BasicBlock
+    {
+        if let Some(path) = path {
+            debug!("drop_subpath: for std field {:?}", lvalue);
+
+            DropCtxt {
+                elaborator: self.elaborator,
+                source_info: self.source_info,
+                path, lvalue, succ, unwind, is_cleanup
+            }.elaborated_drop_block()
+        } else {
+            debug!("drop_subpath: for rest field {:?}", lvalue);
+
+            DropCtxt {
+                elaborator: self.elaborator,
+                source_info: self.source_info,
+                lvalue, succ, unwind, is_cleanup,
+                // Using `self.path` here to condition the drop on
+                // our own drop flag.
+                path: self.path
+            }.complete_drop(None)
+        }
+    }
+
+    /// Create one-half of the drop ladder for a list of fields, and return
+    /// the list of steps in it in reverse order.
+    ///
+    /// `unwind_ladder` is such a list of steps in reverse order,
+    /// which is called instead of the next step if the drop unwinds
+    /// (the first field is never reached). If it is `None`, all
+    /// unwind targets are left blank.
+    fn drop_halfladder<'a>(&mut self,
+                           unwind_ladder: Option<Vec<BasicBlock>>,
+                           succ: BasicBlock,
+                           fields: &[(Lvalue<'tcx>, Option<D::Path>)],
+                           is_cleanup: bool)
+                           -> Vec<BasicBlock>
+    {
+        let mut unwind_succ = if is_cleanup {
+            None
+        } else {
+            self.unwind
+        };
+
+        let goto = TerminatorKind::Goto { target: succ };
+        let mut succ = self.new_block(is_cleanup, goto);
+
+        // Always clear the "master" drop flag at the bottom of the
+        // ladder. This is needed because the "master" drop flag
+        // protects the ADT's discriminant, which is invalidated
+        // after the ADT is dropped.
+        let succ_loc = Location { block: succ, statement_index: 0 };
+        self.elaborator.clear_drop_flag(succ_loc, self.path, DropFlagMode::Shallow);
+
+        fields.iter().rev().enumerate().map(|(i, &(ref lv, path))| {
+            succ = self.drop_subpath(is_cleanup, lv, path, succ, unwind_succ);
+            unwind_succ = unwind_ladder.as_ref().map(|p| p[i]);
+            succ
+        }).collect()
+    }
+
+    /// Create a full drop ladder, consisting of 2 connected half-drop-ladders
+    ///
+    /// For example, with 3 fields, the drop ladder is
+    ///
+    /// .d0:
+    ///     ELAB(drop location.0 [target=.d1, unwind=.c1])
+    /// .d1:
+    ///     ELAB(drop location.1 [target=.d2, unwind=.c2])
+    /// .d2:
+    ///     ELAB(drop location.2 [target=`self.succ`, unwind=`self.unwind`])
+    /// .c1:
+    ///     ELAB(drop location.1 [target=.c2])
+    /// .c2:
+    ///     ELAB(drop location.2 [target=`self.unwind])
+    fn drop_ladder<'a>(&mut self,
+                       fields: Vec<(Lvalue<'tcx>, Option<D::Path>)>)
+                       -> BasicBlock
+    {
+        debug!("drop_ladder({:?}, {:?})", self, fields);
+
+        let mut fields = fields;
+        fields.retain(|&(ref lvalue, _)| {
+            self.tcx().type_needs_drop_given_env(
+                self.lvalue_ty(lvalue), self.elaborator.param_env())
+        });
+
+        debug!("drop_ladder - fields needing drop: {:?}", fields);
+
+        let unwind_ladder = if self.is_cleanup {
+            None
+        } else {
+            let unwind = self.unwind.unwrap(); // FIXME(#6393)
+            Some(self.drop_halfladder(None, unwind, &fields, true))
+        };
+
+        let succ = self.succ; // FIXME(#6393)
+        let is_cleanup = self.is_cleanup;
+        self.drop_halfladder(unwind_ladder, succ, &fields, is_cleanup)
+            .last().cloned().unwrap_or(succ)
+    }
+
+    fn open_drop_for_tuple<'a>(&mut self, tys: &[Ty<'tcx>])
+                               -> BasicBlock
+    {
+        debug!("open_drop_for_tuple({:?}, {:?})", self, tys);
+
+        let fields = tys.iter().enumerate().map(|(i, &ty)| {
+            (self.lvalue.clone().field(Field::new(i), ty),
+             self.elaborator.field_subpath(self.path, Field::new(i)))
+        }).collect();
+
+        self.drop_ladder(fields)
+    }
+
+    fn open_drop_for_box<'a>(&mut self, ty: Ty<'tcx>) -> BasicBlock
+    {
+        debug!("open_drop_for_box({:?}, {:?})", self, ty);
+
+        let interior = self.lvalue.clone().deref();
+        let interior_path = self.elaborator.deref_subpath(self.path);
+
+        let succ = self.succ; // FIXME(#6393)
+        let is_cleanup = self.is_cleanup;
+        let succ = self.box_free_block(ty, succ, is_cleanup);
+        let unwind_succ = self.unwind.map(|u| {
+            self.box_free_block(ty, u, true)
+        });
+
+        self.drop_subpath(is_cleanup, &interior, interior_path, succ, unwind_succ)
+    }
+
+    fn open_drop_for_adt<'a>(&mut self, adt: &'tcx ty::AdtDef, substs: &'tcx Substs<'tcx>)
+                             -> BasicBlock {
+        debug!("open_drop_for_adt({:?}, {:?}, {:?})", self, adt, substs);
+
+        match adt.variants.len() {
+            1 => {
+                let fields = self.move_paths_for_fields(
+                    self.lvalue,
+                    self.path,
+                    &adt.variants[0],
+                    substs
+                );
+                self.drop_ladder(fields)
+            }
+            _ => {
+                let mut values = Vec::with_capacity(adt.variants.len());
+                let mut blocks = Vec::with_capacity(adt.variants.len());
+                let mut otherwise = None;
+                for (variant_index, discr) in adt.discriminants(self.tcx()).enumerate() {
+                    let subpath = self.elaborator.downcast_subpath(
+                        self.path, variant_index);
+                    if let Some(variant_path) = subpath {
+                        let base_lv = self.lvalue.clone().elem(
+                            ProjectionElem::Downcast(adt, variant_index)
+                        );
+                        let fields = self.move_paths_for_fields(
+                            &base_lv,
+                            variant_path,
+                            &adt.variants[variant_index],
+                            substs);
+                        values.push(discr);
+                        blocks.push(self.drop_ladder(fields));
+                    } else {
+                        // variant not found - drop the entire enum
+                        if let None = otherwise {
+                            otherwise =
+                                Some(self.complete_drop(Some(DropFlagMode::Shallow)));
+                        }
+                    }
+                }
+                if let Some(block) = otherwise {
+                    blocks.push(block);
+                } else {
+                    values.pop();
+                }
+                // If there are multiple variants, then if something
+                // is present within the enum the discriminant, tracked
+                // by the rest path, must be initialized.
+                //
+                // Additionally, we do not want to switch on the
+                // discriminant after it is free-ed, because that
+                // way lies only trouble.
+                let discr_ty = adt.repr.discr_type().to_ty(self.tcx());
+                let discr = Lvalue::Local(self.new_temp(discr_ty));
+                let discr_rv = Rvalue::Discriminant(self.lvalue.clone());
+                let switch_block = self.elaborator.patch().new_block(BasicBlockData {
+                    statements: vec![
+                        Statement {
+                            source_info: self.source_info,
+                            kind: StatementKind::Assign(discr.clone(), discr_rv),
+                        }
+                    ],
+                    terminator: Some(Terminator {
+                        source_info: self.source_info,
+                        kind: TerminatorKind::SwitchInt {
+                            discr: Operand::Consume(discr),
+                            switch_ty: discr_ty,
+                            values: From::from(values),
+                            targets: blocks,
+                        }
+                    }),
+                    is_cleanup: self.is_cleanup,
+                });
+                self.drop_flag_test_block(switch_block)
+            }
+        }
+    }
+
+    /// The slow-path - create an "open", elaborated drop for a type
+    /// which is moved-out-of only partially, and patch `bb` to a jump
+    /// to it. This must not be called on ADTs with a destructor,
+    /// as these can't be moved-out-of, except for `Box<T>`, which is
+    /// special-cased.
+    ///
+    /// This creates a "drop ladder" that drops the needed fields of the
+    /// ADT, both in the success case or if one of the destructors fail.
+    fn open_drop<'a>(&mut self) -> BasicBlock {
+        let ty = self.lvalue_ty(self.lvalue);
+        match ty.sty {
+            ty::TyClosure(def_id, substs) => {
+                let tys : Vec<_> = substs.upvar_tys(def_id, self.tcx()).collect();
+                self.open_drop_for_tuple(&tys)
+            }
+            ty::TyTuple(tys, _) => {
+                self.open_drop_for_tuple(tys)
+            }
+            ty::TyAdt(def, _) if def.is_box() => {
+                self.open_drop_for_box(ty.boxed_ty())
+            }
+            ty::TyAdt(def, substs) => {
+                self.open_drop_for_adt(def, substs)
+            }
+            _ => bug!("open drop from non-ADT `{:?}`", ty)
+        }
+    }
+
+    /// Return a basic block that drop an lvalue using the context
+    /// and path in `c`. If `mode` is something, also clear `c`
+    /// according to it.
+    ///
+    /// if FLAG(self.path)
+    ///     if let Some(mode) = mode: FLAG(self.path)[mode] = false
+    ///     drop(self.lv)
+    fn complete_drop<'a>(&mut self, drop_mode: Option<DropFlagMode>) -> BasicBlock
+    {
+        debug!("complete_drop({:?},{:?})", self, drop_mode);
+
+        let drop_block = self.drop_block();
+        if let Some(mode) = drop_mode {
+            let block_start = Location { block: drop_block, statement_index: 0 };
+            self.elaborator.clear_drop_flag(block_start, self.path, mode);
+        }
+
+        self.drop_flag_test_block(drop_block)
+    }
+
+    fn elaborated_drop_block<'a>(&mut self) -> BasicBlock {
+        debug!("elaborated_drop_block({:?})", self);
+        let blk = self.drop_block();
+        self.elaborate_drop(blk);
+        blk
+    }
+
+    fn box_free_block<'a>(
+        &mut self,
+        ty: Ty<'tcx>,
+        target: BasicBlock,
+        is_cleanup: bool
+    ) -> BasicBlock {
+        let block = self.unelaborated_free_block(ty, target, is_cleanup);
+        self.drop_flag_test_block_with_succ(is_cleanup, block, target)
+    }
+
+    fn unelaborated_free_block<'a>(
+        &mut self,
+        ty: Ty<'tcx>,
+        target: BasicBlock,
+        is_cleanup: bool
+    ) -> BasicBlock {
+        let tcx = self.tcx();
+        let unit_temp = Lvalue::Local(self.new_temp(tcx.mk_nil()));
+        let free_func = tcx.require_lang_item(lang_items::BoxFreeFnLangItem);
+        let substs = tcx.mk_substs(iter::once(Kind::from(ty)));
+        let fty = tcx.item_type(free_func).subst(tcx, substs);
+
+        let free_block = self.elaborator.patch().new_block(BasicBlockData {
+            statements: vec![],
+            terminator: Some(Terminator {
+                source_info: self.source_info, kind: TerminatorKind::Call {
+                    func: Operand::Constant(Constant {
+                        span: self.source_info.span,
+                        ty: fty,
+                        literal: Literal::Item {
+                            def_id: free_func,
+                            substs: substs
+                        }
+                    }),
+                    args: vec![Operand::Consume(self.lvalue.clone())],
+                    destination: Some((unit_temp, target)),
+                    cleanup: None
+                }
+            }),
+            is_cleanup: is_cleanup
+        });
+        let block_start = Location { block: free_block, statement_index: 0 };
+        self.elaborator.clear_drop_flag(block_start, self.path, DropFlagMode::Shallow);
+        free_block
+    }
+
+    fn drop_block<'a>(&mut self) -> BasicBlock {
+        let block = TerminatorKind::Drop {
+            location: self.lvalue.clone(),
+            target: self.succ,
+            unwind: self.unwind
+        };
+        let is_cleanup = self.is_cleanup; // FIXME(#6393)
+        self.new_block(is_cleanup, block)
+    }
+
+    fn drop_flag_test_block<'a>(&mut self, on_set: BasicBlock) -> BasicBlock {
+        let is_cleanup = self.is_cleanup;
+        let succ = self.succ; // FIXME(#6393)
+        self.drop_flag_test_block_with_succ(is_cleanup, on_set, succ)
+    }
+
+    fn drop_flag_test_block_with_succ<'a>(&mut self,
+                                          is_cleanup: bool,
+                                          on_set: BasicBlock,
+                                          on_unset: BasicBlock)
+                                          -> BasicBlock
+    {
+        let style = self.elaborator.drop_style(self.path, DropFlagMode::Shallow);
+        debug!("drop_flag_test_block({:?},{:?},{:?}) - {:?}",
+               self, is_cleanup, on_set, style);
+
+        match style {
+            DropStyle::Dead => on_unset,
+            DropStyle::Static => on_set,
+            DropStyle::Conditional | DropStyle::Open => {
+                let flag = self.elaborator.get_drop_flag(self.path).unwrap();
+                let term = TerminatorKind::if_(self.tcx(), flag, on_set, on_unset);
+                self.new_block(is_cleanup, term)
+            }
+        }
+    }
+
+    fn new_block<'a>(&mut self,
+                     is_cleanup: bool,
+                     k: TerminatorKind<'tcx>)
+                     -> BasicBlock
+    {
+        self.elaborator.patch().new_block(BasicBlockData {
+            statements: vec![],
+            terminator: Some(Terminator {
+                source_info: self.source_info, kind: k
+            }),
+            is_cleanup: is_cleanup
+        })
+    }
+
+    fn new_temp(&mut self, ty: Ty<'tcx>) -> Local {
+        self.elaborator.patch().new_temp(ty)
+    }
+
+    fn terminator_loc(&mut self, bb: BasicBlock) -> Location {
+        let mir = self.elaborator.mir();
+        self.elaborator.patch().terminator_loc(mir, bb)
+    }
+}
diff --git a/src/librustc_mir/graphviz.rs b/src/librustc_mir/util/graphviz.rs
index 91600b947c6..91600b947c6 100644
--- a/src/librustc_mir/graphviz.rs
+++ b/src/librustc_mir/util/graphviz.rs
diff --git a/src/librustc_mir/util/mod.rs b/src/librustc_mir/util/mod.rs
new file mode 100644
index 00000000000..cafc5bca76a
--- /dev/null
+++ b/src/librustc_mir/util/mod.rs
@@ -0,0 +1,20 @@
+// Copyright 2017 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.
+
+pub mod elaborate_drops;
+pub mod def_use;
+pub mod patch;
+
+mod graphviz;
+mod pretty;
+
+pub use self::pretty::{dump_mir, write_mir_pretty};
+pub use self::graphviz::{write_mir_graphviz};
+pub use self::graphviz::write_node_label as write_graphviz_node_label;
diff --git a/src/librustc_mir/util/patch.rs b/src/librustc_mir/util/patch.rs
new file mode 100644
index 00000000000..19f240da730
--- /dev/null
+++ b/src/librustc_mir/util/patch.rs
@@ -0,0 +1,178 @@
+// 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.
+
+use rustc::ty::Ty;
+use rustc::mir::*;
+use rustc_data_structures::indexed_vec::{IndexVec, Idx};
+
+/// This struct represents a patch to MIR, which can add
+/// new statements and basic blocks and patch over block
+/// terminators.
+pub struct MirPatch<'tcx> {
+    patch_map: IndexVec<BasicBlock, Option<TerminatorKind<'tcx>>>,
+    new_blocks: Vec<BasicBlockData<'tcx>>,
+    new_statements: Vec<(Location, StatementKind<'tcx>)>,
+    new_locals: Vec<LocalDecl<'tcx>>,
+    resume_block: BasicBlock,
+    next_local: usize,
+}
+
+impl<'tcx> MirPatch<'tcx> {
+    pub fn new(mir: &Mir<'tcx>) -> Self {
+        let mut result = MirPatch {
+            patch_map: IndexVec::from_elem(None, mir.basic_blocks()),
+            new_blocks: vec![],
+            new_statements: vec![],
+            new_locals: vec![],
+            next_local: mir.local_decls.len(),
+            resume_block: START_BLOCK
+        };
+
+        // make sure the MIR we create has a resume block. It is
+        // completely legal to convert jumps to the resume block
+        // to jumps to None, but we occasionally have to add
+        // instructions just before that.
+
+        let mut resume_block = None;
+        let mut resume_stmt_block = None;
+        for (bb, block) in mir.basic_blocks().iter_enumerated() {
+            if let TerminatorKind::Resume = block.terminator().kind {
+                if block.statements.len() > 0 {
+                    resume_stmt_block = Some(bb);
+                } else {
+                    resume_block = Some(bb);
+                }
+                break
+            }
+        }
+        let resume_block = resume_block.unwrap_or_else(|| {
+            result.new_block(BasicBlockData {
+                statements: vec![],
+                terminator: Some(Terminator {
+                    source_info: SourceInfo {
+                        span: mir.span,
+                        scope: ARGUMENT_VISIBILITY_SCOPE
+                    },
+                    kind: TerminatorKind::Resume
+                }),
+                is_cleanup: true
+            })});
+        result.resume_block = resume_block;
+        if let Some(resume_stmt_block) = resume_stmt_block {
+            result.patch_terminator(resume_stmt_block, TerminatorKind::Goto {
+                target: resume_block
+            });
+        }
+        result
+    }
+
+    pub fn resume_block(&self) -> BasicBlock {
+        self.resume_block
+    }
+
+    pub fn is_patched(&self, bb: BasicBlock) -> bool {
+        self.patch_map[bb].is_some()
+    }
+
+    pub fn terminator_loc(&self, mir: &Mir<'tcx>, bb: BasicBlock) -> Location {
+        let offset = match bb.index().checked_sub(mir.basic_blocks().len()) {
+            Some(index) => self.new_blocks[index].statements.len(),
+            None => mir[bb].statements.len()
+        };
+        Location {
+            block: bb,
+            statement_index: offset
+        }
+    }
+
+    pub fn new_temp(&mut self, ty: Ty<'tcx>) -> Local {
+        let index = self.next_local;
+        self.next_local += 1;
+        self.new_locals.push(LocalDecl::new_temp(ty));
+        Local::new(index as usize)
+    }
+
+    pub fn new_block(&mut self, data: BasicBlockData<'tcx>) -> BasicBlock {
+        let block = BasicBlock::new(self.patch_map.len());
+        debug!("MirPatch: new_block: {:?}: {:?}", block, data);
+        self.new_blocks.push(data);
+        self.patch_map.push(None);
+        block
+    }
+
+    pub fn patch_terminator(&mut self, block: BasicBlock, new: TerminatorKind<'tcx>) {
+        assert!(self.patch_map[block].is_none());
+        debug!("MirPatch: patch_terminator({:?}, {:?})", block, new);
+        self.patch_map[block] = Some(new);
+    }
+
+    pub fn add_statement(&mut self, loc: Location, stmt: StatementKind<'tcx>) {
+        debug!("MirPatch: add_statement({:?}, {:?})", loc, stmt);
+        self.new_statements.push((loc, stmt));
+    }
+
+    pub fn add_assign(&mut self, loc: Location, lv: Lvalue<'tcx>, rv: Rvalue<'tcx>) {
+        self.add_statement(loc, StatementKind::Assign(lv, rv));
+    }
+
+    pub fn apply(self, mir: &mut Mir<'tcx>) {
+        debug!("MirPatch: {:?} new temps, starting from index {}: {:?}",
+               self.new_locals.len(), mir.local_decls.len(), self.new_locals);
+        debug!("MirPatch: {} new blocks, starting from index {}",
+               self.new_blocks.len(), mir.basic_blocks().len());
+        mir.basic_blocks_mut().extend(self.new_blocks);
+        mir.local_decls.extend(self.new_locals);
+        for (src, patch) in self.patch_map.into_iter_enumerated() {
+            if let Some(patch) = patch {
+                debug!("MirPatch: patching block {:?}", src);
+                mir[src].terminator_mut().kind = patch;
+            }
+        }
+
+        let mut new_statements = self.new_statements;
+        new_statements.sort_by(|u,v| u.0.cmp(&v.0));
+
+        let mut delta = 0;
+        let mut last_bb = START_BLOCK;
+        for (mut loc, stmt) in new_statements {
+            if loc.block != last_bb {
+                delta = 0;
+                last_bb = loc.block;
+            }
+            debug!("MirPatch: adding statement {:?} at loc {:?}+{}",
+                   stmt, loc, delta);
+            loc.statement_index += delta;
+            let source_info = Self::source_info_for_index(
+                &mir[loc.block], loc
+            );
+            mir[loc.block].statements.insert(
+                loc.statement_index, Statement {
+                    source_info: source_info,
+                    kind: stmt
+                });
+            delta += 1;
+        }
+    }
+
+    pub fn source_info_for_index(data: &BasicBlockData, loc: Location) -> SourceInfo {
+        match data.statements.get(loc.statement_index) {
+            Some(stmt) => stmt.source_info,
+            None => data.terminator().source_info
+        }
+    }
+
+    pub fn source_info_for_location(&self, mir: &Mir, loc: Location) -> SourceInfo {
+        let data = match loc.block.index().checked_sub(mir.basic_blocks().len()) {
+            Some(new) => &self.new_blocks[new],
+            None => &mir[loc.block]
+        };
+        Self::source_info_for_index(data, loc)
+    }
+}
diff --git a/src/librustc_mir/pretty.rs b/src/librustc_mir/util/pretty.rs
index 35734dcce2b..35734dcce2b 100644
--- a/src/librustc_mir/pretty.rs
+++ b/src/librustc_mir/util/pretty.rs